Schon seit .NET Framework 3.5 steht in C# und weiteren .NET-Programmiersprachen die Querysyntax zur Verfügung. Sie bietet Entwickler:innen eine sehr deklarative Möglichkeit, viele Informationsbedürfnisse durch gut les- und wartbare Querys zu formulieren, ähnlich prägnant wie Datenbankabfragen, aber geprüft vom Compiler.

Um beispielsweise eine priorisierte Liste von Aufgaben zu ermitteln, bei der die Aufgaben einer Reihe von Projekten zugeordnet sind, lässt sich die in Listing 1 gezeigte Abfrage verwenden: Eine Query nach den unerledigten To-dos aller aktiven Projekte (nicht „on hold“), sortiert nach Priorität und Deadline (falls gesetzt), lässt sich wohl kaum prägnanter ausdrücken.

from p in Projects
where !p.IsOnHold
from t in p.Todos
where !t.IsDone
orderby t.Priority descending, t.Deadline ?? EndOfTime
select t

Von Anfang an war es ein wichtiges Ziel, diese Abfragen analysieren zu können, um daraus beispielsweise SQL-Statements zu generieren – ein Ansatz, der mit dem Entity Framework Core im Grunde seither unverändert eine sehr hohe Verbreitung gefunden hat. Doch während die Querysyntax aus Datenbankabfragen kaum mehr wegzudenken ist, hat sie bei der Implementierung von Nutzerschnittstellen kaum Einzug gehalten.

Das ist schade, denn solche Abfragen wären auch bei der Entwicklung grafischer Benutzeroberflächen nützlich. In einer Anwendung zur Aufgabenverwaltung wäre es beispielsweise dienlich, eine priorisierte Liste von Aufgaben angezeigt zu bekommen, die sich sofort aktualisiert, wenn der Nutzer Änderungen vornimmt, die sich auf die Reihenfolge der Aufgaben auswirken.

Auch abseits von Nutzerschnittstellen möchte man manchmal wissen, wann und wie sich das Ergebnis einer Query ändert, um automatisiert Maßnahmen anstoßen zu können. Beispielsweise könnte man durch eine Query ermittelte Defekte automatisch korrigieren oder eine KPI in einem definierten Zielkorridor halten wollen.

Ein Beispiel für eine Bibliothek, die genau diese Funktionalität ermöglicht und sowohl .NET 8, 9 und 10 als auch .NET Standard 2.0 und somit auch das .NET-Framework unterstützt, ist die unter New-BSD lizenzierte Open-Source-Bibliothek NMF Expressions[1], [2]. In diesem Artikel wird beschrieben, wie diese Bibliothek funktioniert und wie sie dabei helfen kann, Data Binding gegen Querys zu ermöglichen.

INotifyPropertyChanged und INotifyCollectionChanged

Der Grund, warum Queries trotz ihrer guten Les- und Wartbarkeit nicht bei Nutzeroberflächen eingesetzt werden, ist meist, dass die XAML-basierten UI-Frameworks in .NET (WPF, MAUI, Avalonia, Uno) auf die Schnittstellen INotifyPropertyChanged und INotifyCollectionChanged angewiesen sind, um zu erkennen, welche Teile der UI wann aktualisiert werden müssen. Die Schnittstelle INotifyPropertyChanged erlaubt es hierbei, sich per Event benachrichtigen zu lassen, wenn sich das Ergebnis einer Eigenschaft ändert, wohingegen INotifyCollectionChanged über Änderungen an Auflistungen informiert. Beide Schnittstellen sind bereits seit dem .NET-Framework 3.0 Teil der Basisklassenbibliothek; es gibt sie sogar schon länger als die Querysyntax. Um die Implementierung von INotifyPropertyChanged für eigene Klassen zu unterstützen, gibt es seit einiger Zeit auch das MVVM Community Toolkit, das den notwendigen Boilerplate-Code zur Unterstützung von INotifyPropertyChanged generieren kann. Doch was ist mit INotifyCollectionChanged?

Für diese Schnittstelle gibt es im Framework nur genau eine einzige Implementierung: die ObservableCollection. Das Problem aber ist, dass LINQ-to-Objects-Querys diese nicht verwenden und Querys daher nicht für Data Binding genutzt werden können.

Data Binding an eine Query erfordert manuelle Synchronisation

Um das Ergebnis einer Query also in einer Nutzerschnittstelle anzeigen zu können, müssen die Ergebnisse manuell in einer ObservableCollection gepuffert werden. Bei jeder Änderung von Daten müssen Entwickler:innen also dafür sorgen, dass dieser Puffer aktualisiert wird. Dabei zählt Cache Invalidation nach Phil Karlton zu den schwierigsten Dingen der Informatik, da es kaum möglich ist, sicherzustellen, dass dies richtig erfolgt. Wenn der Puffer zu häufig aktualisiert wird, ist das eine Verschwendung von Ressourcen. Wenn er zu selten aktualisiert wird, können die Daten darin unter Umständen falsch sein. Hinzu kommt, dass sich in der Regel eine Vielzahl von Änderungen auf die Ergebnisse einer Query auswirken können. Wann immer ein Projekt oder To-do hinzugefügt oder gelöscht wird, ein Projekt auf „on hold“ gesetzt oder reaktiviert wird oder sich die Prioritäten oder Deadlines der einzelnen To-dos ändern, muss der Puffer entsprechend aktualisiert werden. All diese Szenarien müssen gut getestet werden. Die größte Gefahr besteht jedoch darin, irgendeine Art von Änderungen, die sich auf das Ergebnis der Query auswirken, zu vergessen.

SIE LIEBEN C#?

Entdecken Sie die BASTA! Tracks

Mehr erfahren

Inkrementalisierung

Wie lässt sich nun dieses Problem lösen, wie lassen sich Querys auch für Data Binding einsetzen, ohne dass Änderungen an der Query selbst vorgenommen werden müssen? Wenn sich eine Änderung im Modell ergibt, was genau soll dann neu berechnet werden? Neben der Frage nach dem Wann stellt sich auch die, wie die Puffer aktualisiert werden müssen – auch im Hinblick auf die algorithmische Komplexität. In manchen Fällen kann es zeitkritisch sein, nach der Änderung der eigentlichen Daten auch die aktualisierten Queryergebnisse zur Verfügung zu haben. Es kann schlicht zu lange dauern, dann immer die gesamte Query neu zu berechnen, gerade wenn sich nur ein sehr kleiner Teil der Daten geändert hat und die Teilergebnisse der Query eigentlich noch aktuell wären.

Wenn aber immer nur Teilergebnisse neu berechnet werden, bezeichnet man das als inkrementelle Ausführung, weil sich die Datenstruktur an inkrementell auftretende Änderungen anpassen muss. In der Algorithmik spricht man in diesem Zusammenhang auch von dynamischen Algorithmen, weil die Änderungen auch bedeuten können, dass Elemente gelöscht werden. Wenn sich ein solcher inkrementeller bzw. dynamischer Algorithmus ohne Zutun des Entwicklers von einer Spezifikation, beispielsweise einer Query, ableiten lässt, handelt es sich um eine implizite Inkrementalisierung; das Ergebnis ist eine implizit inkrementelle Query.

Damit das Ergebnis einer inkrementellen Query wohldefiniert ist, dürfen die eingesetzten Prädikate keine Seiteneffekte haben, die die Berechnung anderer Teilergebnisse beeinflussen, denn andernfalls wäre unklar, welche Seiteneffekte nach einer Änderung der zugrundeliegenden Daten ausgeführt wurden. Prädikate wie Filterbedingungen dürfen daher keine von außen sichtbaren Variablen oder andere Zustände verändern. Das ist bei Querys ohnehin eine übliche Annahme. Auch wenn man mittels PLINQ eine Query parallel ausführen möchte, sind seiteneffektbehaftete Prädikate keine gute Idee, da man sich sonst mit Thread-Synchronisation auseinandersetzen muss.

Als Nächstes müssen wir überlegen, welche API wir haben wollen. Das Ergebnis einer Query kann entweder ein einzelner Wert oder eine Auflistung sein. Während Auflistungen gewöhnlich ohnehin schon von Schnittstellen repräsentiert werden, kann ein einzelner Wert kaum für sich selbst die Schnittstelle INotifyPropertyChanged implementieren und muss daher in einer separaten Schnittstelle gekapselt werden.

Eine solche Schnittstelle ist in etwa in Listing 2 skizziert. Die einfachste denkbare Implementierung hierfür ist natürlich eine Konstante, bei der also Value immer genau den Wert der Konstante zurückliefert und das Event ValueChanged nie ausgelöst wird.

public interface INotifyValue<out T>
{
  T Value { get; }
  event EventHandler ValueChanged;
}

Generische Schnittstellen sind dabei ein Weg, mathematische Funktoren zu implementieren. Collections sind ein Beispiel für Funktoren, die in vielen Programmiersprachen auftreten. Da Schnittstellen andere Schnittstellen erben können, lässt sich der Funktor IEnumerable beispielsweise mit der Schnittstelle INotifyCollectionChanged kombinieren. In NMF heißt das Ergebnis INotifyEnumerable.

Ein Funktor besteht jedoch nicht nur aus einer Abbildung von Typen (wie string auf INotifyValue<string>), sondern auch aus einer Abbildung von Funktionen/Methoden. So muss es beispielsweise aus einer Funktion Func<string, int> eine Abbildung nach Func<INotifyValue<string>,INotifyValue<int>> geben. Für den Funktor IEnumerable übernimmt diese Abbildung der Queryoperator Select. Den ganzen Funktor für INotifyValue und INotifyEnumerable, also die Typabbildung und die Abbildung von Methoden, sowie die Abbildung Value zurück auf den derzeitigen Wert (in der Mathematik ist das eine natürliche Transformation), nennt man Inkrementalisierungssystem.

Um von einer Collection, die InotifyCollectionChanged, aber nicht INotifyEnumerable implementiert, auf letztere zu kommen, braucht man einen Adapter. In NMF Expressions nennt sich die Methode, die einen solchen Adapter erzeugen kann, WithUpdates.

Doch wie erreicht man eine solche Methodenabbildung für INotifyValue und INotifyEnumerable?

Dynamische Abhängigkeitsgraphen

Um immer nur die von einer Änderung tatsächlich betroffenen Teilergebnisse aktualisieren zu müssen, liegt es nahe, einen Abhängigkeitsgraphen zu halten, um entscheiden zu können, wann welche Teilergebnisse neu berechnet werden müssen. Um eine einheitliche Schnittstelle zu schaffen, verwenden die Teilergebnisse dieselben Schnittstellen wie die Endergebnisse, also INotifyValue und INotifyEnumerable. Da sich die Teilergebnisse normalerweise auf Teile der Daten beziehen (z. B., ob ein To-do noch unerledigt ist), variiert ihre Menge mit den Daten, ist also dynamisch; daher der Name „dynamischer Abhängigkeitsgraph“ [3].

Die einfachste Methode, um einen solchen dynamischen Abhängigkeitsgraphen zu erzeugen, besteht darin, eine Teilfunktion in ihre einzelnen Bestandteile, also die einzelnen syntaktischen Elemente, zu zerlegen. Auf dieser Ebene lässt sich leicht entscheiden, wann sich das Ergebnis ändert. Ändert sich beispielsweise das Bezugsobjekt für den Zugriff auf eine Property oder löst das aktuelle Bezugsobjekt ein Event über die INotifyPropertyChanged-Schnittstelle aus, dann könnte sich auch der Wert für den Zugriff auf die Property geändert haben. Doch wie kann man zur Laufzeit eine Funktion in ihre Bestandteile aufteilen?

Expression Trees als Grundlage für implizite Inkrementalisierung

In .NET lässt sich eine solche Dekomposition mit denselben Technologien bewerkstelligen, die ursprünglich für LINQ entwickelt wurden: Expression Trees erlauben es, zur Laufzeit auf den abstrakten Syntaxbaum einer Funktion zuzugreifen anstatt auf deren Kompilat. Dazu können Lambda-Ausdrücke vom Compiler nicht nur in Delegattypen wie Func<string> gecastet werden, sondern auch in Expression-Typen davon, wie Expression<Func<string>>. Im Entity Framework (Core) wird dieses Syntaxfeature, das nicht nur in C#, sondern auch in vielen anderen .NET-Sprachen existiert, dazu verwendet, aus einer Query SQL-Statements zu generieren. Mit Expression Trees lassen sich jedoch auch dynamische Abhängigkeitsgraphen erstellen.

NMF Expressions macht genau das: Es verwendet den Aufbau von Lambdaausdrücken, um daraus einen dynamischen Abhängigkeitsgraphen zu erzeugen und so die Schnittstellen INotifyValue und INotifyCollectionChanged zu implementieren.

SIE LIEBEN .NET?

Entdecken Sie die BASTA! Tracks

Mehr erfahren

Explizite Inkrementalisierung von Queryoperatoren

Dynamische Abhängigkeitsgraphen auf Basis einzelner Instruktionen haben zwei Nachteile: Zum einen werden sie sehr schnell sehr groß, zum anderen ist es nicht immer sinnvoll, auf Ebene der einzelnen Instruktionen zu überlegen, welche Instruktionen von einer Änderung genau betroffen sind. Stattdessen gibt es für einige Probleme dedizierte dynamische Algorithmen, die häufig deutlich effizienter sind, als es ein instruktionsbasierter Ansatz sein kann. Um beispielsweise die Summe oder den Mittelwert einer Menge von Zahlen dynamisch zu berechnen, ist es ausreichend, sich die aktuelle Summe (und im Fall des Mittelwerts zusätzlich die aktuelle Anzahl) zu merken und sie beim Hinzufügen oder Löschen einer Zahl entsprechend zu aktualisieren. Auf diese Weise lassen sich für viele Query-Operatoren sehr effiziente dynamische Algorithmen finden, insbesondere wenn die Reihenfolge der Ergebnisse keine Rolle spielt.

Die Bibliothek NMF Expressions bietet für viele der Standardqueryoperatoren (SQO) eine explizite Inkrementierung. Die SQO sind diejenigen Queryoperatoren, die von einigen Programmiersprachen mit einer eigenen Syntax versehen sind. Ob eine Programmiersprache für einen SQO eine spezielle Syntax anbietet, ist je nach Sprache verschieden. So bildet VB.NET den Operator Aggregate in einer eigenen Syntax ab, C# aber nicht.

Die Faustregel besagt, dass es für alle Queryoperatoren, die nicht indexbasiert sind, eine inkrementelle Variante gibt. Der Grund dafür ist, dass sich Indizes zu häufig ändern. Wenn ein neues Element eingefügt wird, ändert sich nämlich der Index für alle nachfolgenden Elemente. Eine so inkrementalisierte Query hätte daher wahrscheinlich eine schlechte Performance. Um das zu vermeiden, wird diese Funktionalität erst gar nicht angeboten.

Doch wie implementiert man eine explizite Inkrementalisierung einer Methode in NMF Expressions?

Eigene Funktionen explizit inkrementalisieren

Im Unterschied zu Lambdaausdrücken kann die Implementierung einer Methode nicht ohne Weiteres eingesehen werden, da sie per Reflection nur als Bytecode abrufbar ist. Daher benötigt ein Inkrementalisierungssystem eine Heuristik, wann sich das Ergebnis eines Methodenaufrufs potenziell ändert. Eine gute erste Heuristik ist, dass sich die Rückgabe einer Methode dann ändern könnte, wenn sich die Parameter ändern.

Wenn nun Teile einer Query in separate Methoden ausgelagert werden, ist das für Technologien, die auf Expression Trees beruhen, daher grundsätzlich problematisch. So könnte das Entity Framework (Core) ein so ausgelagertes Prädikat beispielsweise nicht mehr nach SQL übersetzen, sondern wäre gezwungen, das Prädikat und alles, was danach kommt, auf dem Client auszuwerten. Im Fall der Inkrementalisierung kann das aber nützlich sein, um den Abhängigkeitsgraphen zu verkleinern. Denn für die Ausführung einer Methode gibt es im Abhängigkeitsgraphen zunächst nur genau einen Knoten. Wenn die Heuristik zutrifft, beispielsweise weil die Argumente der Methode alle unveränderlich sind, führt das zu einer effizienteren und speicherschonenderen Abarbeitung. Das ist der Fall, wenn die Methode ausschließlich mit Zahlen, Zeichenketten oder Record Structs arbeitet. Was aber, wenn nicht alle Parameter unveränderlich sind?

Die Idee der expliziten Inkrementalisierung besteht nun darin, in diese Heuristik einzugreifen und sie zu überschreiben. NMF Expressions verwendet hierfür Attribute, genauso wie das Entity Framework, das seit jeher Attribute nutzt, um Methodenaufrufe in den Aufruf von Stored Procedures in der Datenbank umzuwandeln. Das verwendete Attribut in NMF Expressions nennt sich ObservableProxy. Da man in ein Attribut keine Methode eintragen kann, muss man in das Attribut den Namen einer öffentlichen Proxymethode eintragen, sowie (falls abweichend) die Klasse, in der die Methode deklariert ist. Wenn die Proxymethode nicht öffentlich sichtbar sein soll, empfiehlt es sich, eine interne oder private Hilfsklasse dafür anzulegen.

Eine solche Proxymethode wird von NMF Expressions anstelle der eigentlichen Methode aufgerufen. Dazu muss sie dieselben Typparameter haben; außerdem muss es für jeden Parameter einen Parameter geben, bei dem der Typ in INotifyValue geschachtelt ist, ebenso für den Rückgabetyp. Da die Datenstrukturen häufig auch komplett neu aufgebaut werden müssen, wenn sich Parameter ändern, dürfen die Parametertypen der Proxymethode auch die originalen Parametertypen sein. In diesem Fall kümmert sich NMF Expressions darum, die Methode erneut aufzurufen, wenn sich die übergebenen Argumente ändern.

Ein Beispiel, das zeigt, wie das Prädikat, ob ein To-do weiterhin relevant ist, in eine Methode ausgelagert werden kann, ist in Listing 3 dargestellt. Zu Demonstrationszwecken wird hier als Implementierung der Schnittstelle INotifyValue wiederum NMF Expressions verwendet, aber natürlich sind auch eigene Implementierungen möglich, wodurch sich beliebige dynamische Algorithmen umsetzen lassen.

[ObservableProxy(nameof(IsRelevantInc1))] // alternativ nameof(IsRelevantInc2)
public bool IsRelevant(Todo todo) => !todo.IsDone;

public INotifyValue<bool> IsRelevantInc1(INotifyValue<Todo> todo)
   => Observable.Expression(() => !todo.Value.IsDone);

public INotifyValue<bool> IsRelevantInc2(Todo todo)
   => Observable.Expression(() => !todo.IsDone);

Integration in UI-Technologien

Obwohl es laut den Architekturrichtlinien von .NET für Schnittstellen immer mindestens zwei denkbare Implementierungen geben muss, existiert für INotifyCollectionChanged in der Basisklassenbibliothek, wie schon erwähnt, nur eine Implementierung, nämlich ObservableCollection. Das hat anscheinend zur Folge, dass die meisten XAML-basierten UI-Bibliotheken davon ausgehen, dass es sich bei einer Implementierung von INotifyCollection um die ObservableCollection handeln muss, obwohl die Schnittstelle eigentlich allgemeiner entworfen wurde. So kann man bei einem CollectionChanged-Ereignis den Index eines geänderten, hinzugefügten oder gelöschten Elements angeben oder eine -1 eintragen, falls der Typ der Collection keine Indizes unterstützt, wie beispielsweise bei Mengentypen wie HashSet, die keine Ordnung der Elemente garantieren.

Leider wird bei UI-Bibliotheken weder die Möglichkeit berücksichtigt, dass eine Implementierung von INotifyCollectionChanged von einem Index -1 Gebrauch machen könnte, noch die Möglichkeit, dass in einer Collection mehrere Elemente auf einmal verändert werden oder nach einem Reset Elemente übrigbleiben könnten. Auch wenn sich die Fehlermeldungen je nach UI-Technologie durchaus unterscheiden, implementieren alle großen UI-Bibliotheken immer nur genau das, was für die ObservableCollection benötigt wird.

Wie macht man also eine inkrementelle Query kompatibel für Data Binding in UI-Bibliotheken? In NMF Expressions existiert hierfür die spezielle Methode RestoreIndices, die die inkrementelle Query puffert, Änderungen vereinzelt und Indizes wiederherstellt. Damit lässt sich die Query aus Listing 1 wie in Listing 4 in die Oberfläche einbinden.

TodosInOrder = (from p in Projects.WithUpdates()
                where !p.IsOnHold
                from t in p.Todos
                where !t.IsDone
                orderby t.Priority descending, t.Deadline ?? EndOfTime
                select t).RestoreIndices();

In [4] habe ich ein Repository erstellt, das die Verwendung von NMF Expressions in Verbindung mit dem MVVM Community Toolkit für das Eingangsbeispiel der To-do-Liste für WPF, MAUI und Avalonia demonstriert.

GraphQL

Die meisten XAML-basierten Technologien wie WPF, MAUI oder Avalonia arbeiten innerhalb desselben Prozesses, weshalb sich das UI bequem an die über INotifyPropertyChanged und INotifyCollectionChanged zur Verfügung gestellten Ereignisse auf Änderungen des Modells registrieren kann, um Data Binding zu ermöglichen. Das funktioniert natürlich nicht mehr, wenn das UI in einem anderen Prozess liegt, wie es beispielsweise bei Webanwendungen der Fall ist. Um sich hier auch über Änderungen benachrichtigen zu lassen, müssen Events explizit als Subscriptions hinterlegt werden. In [4] habe ich das exemplarisch auch für eine GraphQL-Version derselben To-do-Liste verwendet.

Performancegewinne hängen von der Anwendung ab

Eine Frage, die sich förmlich aufdrängt, ist die nach der Performance. Natürlich verbraucht der dynamische Abhängigkeitsgraph Speicher. Mehr Speicher ist allerdings häufig einfacher zu bekommen als mehr CPU-Zeit. Hinzu kommt, dass manche Queryoperatoren wie Orderby bei jeder Ausführung Speicher benötigen, während eine inkrementelle Query einen balancierten Suchbaum im Speicher hält und diesen permanent beibehält. Daher wird bei einer Abfrage der Ergebnisse kein neuer Speicher allokiert. Die Performance der Änderungsausbreitung kann jedoch auch von der Beschaffenheit konkreter Änderungen abhängen. So ist es im Beispiel natürlich aufwendiger zu propagieren, wenn in einem Projekt viele To-dos von „on hold“ wieder auf aktiv gesetzt werden, als wenn diesem Projekt gar keine To-dos zugeordnet gewesen wären. Diese Beispiele illustrieren, dass eine allgemeine Aussage kaum möglich ist.

In guten Fällen kann es allerdings auch zu sehr hohen Beschleunigungen kommen, solange der dynamische Abhängigkeitsgraph in den Speicher passt. So konnten in einigen Benchmarks auch schon Beschleunigungen von mehreren Größenordnungen gemessen werden [5]. Insbesondere wenn die Änderungen nur kleine Teile der Query betreffen, ist der Aufwand für die Propagation in einer viel günstigeren Komplexitätsklasse, als wenn komplett alles neu berechnet und anschließend noch verglichen werden müsste, was genau sich denn geändert hat.

Zusammenfassung

Mit Hilfe von dynamischen Abhängigkeitsgraphen lassen sich Querys in .NET nicht nur automatisch in Datenbankabfragen konvertieren. Die angebotenen Abstraktionen eignen sich auch dazu, automatisiert zu erfassen, wann sich das Ergebnis einer Query ändert. Auf diese Weise können deklarative Querys mit NMF Expressions beispielsweise für das Data Binding von XAML-basierten UI-Technologien eingesetzt werden.

Links & Literatur

[1] https://nmfcode.github.io/expressions/index.html

[2] Hinkel, G.; Heinrich, R.; Reussner, R.: „An extensible approach to implicit incremental model analyses“; in: Software & Systems Modeling 18, 2019

[3] Acar, U.: „Self-adjusting computation:(an overview)“: in: „Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation“, 2009

[4] https://github.com/georghinkel/expressions-demo

[5] Szárnyas, G.; Semeráth, O.; Ráth, I.: „The TTC 2015 Train Benchmark Case for Incremental Model Validation“; in: „Proceedings of the 8th Transformation Tool Contest“, 2015