Epiforge.Extensions.Expressions 7.0.0

This library has useful tools for dealing with expressions:

• ExpressionEqualityComparer - Defines methods to support the comparison of expression trees for equality
• ExpressionExtensions, providing:
  • Duplicate - Duplicates the specified expression tree
  • SubstituteMethods - Recursively scans an expression tree to replace invocations of specific methods with replacement methods

Observable Expressions

An ExpressionObserver accepts a LambdaExpression and arguments to pass to it, dissects the lambda's body, and hooks into change notification events for properties (INotifyPropertyChanged), collections (INotifyCollectionChanged), and dictionaries (Epiforge.Extensions.Collections.INotifyDictionaryChanged).

// Employee implements INotifyPropertyChanged
var elizabeth = Employee.GetByName("Elizabeth");
var observer = new ExpressionObserver();
var expr = observer.Observe(e => e.Name.Length, elizabeth);
// expr subscribed to elizabeth's PropertyChanged

Following Changes

As anything the expression reads changes, the expression re-evaluates, and its Evaluation property may change with it.

var elizabeth = Employee.GetByName("Elizabeth");
var observer = new ExpressionObserver();
var expr = observer.Observe(e => e.Name.Length, elizabeth);
// expr.Evaluation.Result == 9
elizabeth.Name = "Lizzy";
// expr.Evaluation.Result == 5

An observable expression raises property change events of its own, and listening for them is the point of having one.

var elizabeth = Employee.GetByName("Elizabeth");
var observer = new ExpressionObserver();
var expr = observer.Observe(e => e.Name.Length, elizabeth);
expr.PropertyChanged += (sender, e) =>
{
    if (e.PropertyName == "Evaluation")
    {
        var (fault, result) = expr.Evaluation;
        if (fault is not null)
        {
            // handle the fault
        }
        else
        {
            // use the result
        }
    }
};

While an expression is working out its new value it can pass through results that were never simultaneously true of its inputs; an addition whose two operands both derive from the same property has to compute one of them before the other. You are not told about those. Every event you receive carries a value the expression genuinely held, so a subscriber that redraws or broadcasts on one does that work once rather than twice, the second time only to correct the first.

Nor are you told anything at all when a change leaves the value where it found it. That is decided by a comparison, using the same equality the expression uses everywhere else, and it happens before PropertyChanging rather than after — so a handler for that event still reads the previous value, and a pair of events always means the value really moved.

When Evaluation Fails

An exception can arise long after an observable expression was created, because something it reads changed. It is not thrown; it becomes the Fault of the expression's evaluation.

var elizabeth = Employee.GetByName("Elizabeth");
var observer = new ExpressionObserver();
var expr = observer.Observe(e => e.Name.Length, elizabeth);
// expr.Evaluation.Fault is null
elizabeth.Name = null;
// expr.Evaluation.Fault is NullReferenceException

An expression tree built at run time can also catch a fault with Expression.TryCatch, which C# will not write in a lambda. The body is evaluated first; while it faults, the first catch block whose type the fault is supplies the value instead, and that block is evaluated only then. A catch block whose body is Expression.Rethrow lets the fault through, so faults which should always spread can be listed ahead of one catching Exception. Catch blocks with a variable or a filter, and finally and fault blocks, are not supported.

Disposing of an Observation

When you dispose of an observable expression, it disconnects from all the events it subscribed to.

var elizabeth = Employee.GetByName("Elizabeth");
var observer = new ExpressionObserver();
using (var expr = observer.Observe(e => e.Name.Length, elizabeth))
{
    // expr subscribed to elizabeth's PropertyChanged
}
// expr unsubscribed from elizabeth's PropertyChanged

Observable expressions also try to dispose of disposable objects they create in the course of their evaluation, when and where it makes sense. Use the ExpressionObserverOptions class for more direct control over this behavior.

Changes From Other Threads

A source can change on any thread, including while an observation of it is being built or evaluated on another. No change is lost: once the changes stop, every observation settles on what its expression gives over its sources as they then stand. You can dispose of an observation on any thread, too, even while another thread is evaluating it.

An observation is evaluated on the thread which raised the change, unless another thread is evaluating it at that moment, in which case that thread evaluates it again before it finishes and the thread which raised the change carries on without waiting. So the PropertyChanged which follows a change can arrive on a different thread from the change, and a setter can return before an observation reflects it.

Two things stay yours. While changes arrive on several threads at once, an observation can briefly report a value computed from reads taken at different moments, as any code reading shared state without a lock would, and it settles once they stop. And the observer reads your sources on whichever thread is evaluating, so a source must be safe to read while another thread changes it. ObservableCollection<T> is not: read in the middle of a change, it can throw, the observation reports that fault until the change's notification has it read again, and a ConditionAsync waiting on it completes with the fault.

If nothing an observer's observations read changes while another thread builds, evaluates or disposes of one of them, as when all of it happens on a user interface thread, you can say so by setting IsThreadSafe to false in the options you hand the observer. It then evaluates without the interlocked operations the promises above cost: a raise against a thousand observations of one object costs 0.50x what it otherwise would, and a property change in a filtered view of a thousand 0.73x. It is true by default, and setting it where changes do cross threads gives those promises up: a change can be lost, an observation can be evaluated before it is built, and observations disposed of on several threads at once can leave parts of themselves cached.

Fields Are Read Once

Whatever a field held when an observation began is what that observation goes on using — a captured local, a field of your own class, and a static field alike. Assigning it afterward does not reach an observation that already exists. Static properties behave the same way, so e => e.Hired < DateTime.Now compares against the moment it was created for as long as it lives.

var threshold = low;
using var expr = observer.Observe(e => e.Salary > threshold.Amount, elizabeth);
threshold = high;    // expr is still comparing against low
low.Amount = 50000;  // expr re-evaluates
high.Amount = 90000; // expr does not

If you want the comparison to follow the value, do not assign the field — make the thing it points at a property of an object that notifies, and read that instead.

Optimizing Expressions

The Optimizer property of ExpressionObserverOptions specifies an optimization method to invoke automatically while an observable expression is being created. We recommend Tuomas Hietanen's Linq.Expression.Optimizer, the use of which looks like this:

var options = new ExpressionObserverOptions { Optimizer = ExpressionOptimizer.tryVisit };

var a = Expression.Parameter(typeof(bool));
var b = Expression.Parameter(typeof(bool));

var lambda = Expression.Lambda<Func<bool, bool, bool>>
(
    Expression.AndAlso
    (
        Expression.Not(a),
        Expression.Not(b)
    ),
    a,
    b
); // lambda explicitly defined as (a, b) => !a && !b

var observer = new ExpressionObserver(options);
var expr = observer.Observe<bool>(lambda, false, false);
// optimizer has intervened and defined expr as (a, b) => !(a || b)
// (because Augustus De Morgan said they're essentially the same thing, but this involves less steps)

Linq.Expression.Optimizer does not handle Expression.TryCatch, and tryVisit leaves any lambda containing one entirely unoptimized.

How an Expression Gets Observed

Observe takes a shortcut when it can and builds a graph when it cannot, deciding once when the observation is created. You receive the same values through the same events either way; the shortcut is just faster and lighter.

The shortcut handles an expression built from these:

• the argument, constants, and captured locals
• fields, on anything above — including static fields
• static properties
• properties and indexers whose target is one of the above
• a property read through something which can change, such as e => e.Name.Length or e => e.Manager.Rank, which follows the value as it moves and re-subscribes where it lands
• ?:, &&, || and ??, whose deferred operands take their subscriptions the first time an evaluation reaches them, which is where the graph attaches its nodes for them
• a try built with Expression.TryCatch, whose catch blocks take their subscriptions the first time a fault selects them
• a call to the get method of a property or an indexer, which is how an indexer written in C# arrives, read as the member or index access it stands for
• object construction, object initializers and array initializers, including construction of a value the observer disposes of when nothing the constructor is given can change, made once and disposed once
• an invocation of a literal lambda, as a formula or rule engine building expression trees at run time commonly emits, reduced to the body it would have evaluated when each parameter is read exactly once and, unless its argument is a constant or the argument, not inside a deferred operand or a try
• method calls and operators resolved to a method, unless the observer disposes of what one returned and what it is made on or given can change
• a property whose change notifications you have told the observer to ignore, when nothing it is read through can change, read once and kept

What builds the graph instead: a kind of expression not in that list, such as a lambda passed as an argument or an array built from bounds; an invocation of a literal lambda whose parameter is read other than exactly once, or is read inside a deferred operand or a try when its argument could fault, because the graph evaluates every argument first; an indexer whose target can change; a member read on a value type which can notify; a call or operator whose return value the observer disposes of and whose target or arguments can change; a construction whose value the observer disposes of and whose arguments can change; a read of a property or an indexer you have registered for disposal, whatever it is read through, because the property can announce and the graph replaces and disposes of its value when it does; a read of an ignored property through something which can change; and an expression deferring more than 64 operands.

To find out about a particular expression, ask:

var analysis = new DirectSubscriptionAnalyzer(options).Analyze(expression.Body);
// analysis.IsEligible says whether the shortcut handles it
// analysis.Ineligibility says why not, such as DirectSubscriptionIneligibility.ValueRequiresDisposal
// analysis.IneligibleExpression is the part responsible

Hand the analyzer the same options you hand the observer, since some of them decide what gets subscribed to at all. Set UseDirectSubscription to false if you would rather always have the graph; it is true by default.

Observable Queries

This library provides re-implementations of LINQ operations, but instead of returning IEnumerable<T>s and simple values, these return IObservableCollectionQuery<T>s, IObservableDictionaryQuery<TKey, TValue>s, and IObservableScalarQuery<T>s. This is because, unlike traditional LINQ operations, these implementations continuously update their results until those results are disposed. What they hand back is a read-only view of the source: change the source, and the query brings itself up to date. Queries do not implement the mutating range collection and dictionary interfaces, because a query result is not somewhere you put things.

A query updates when:

• the source is enumerable, implements INotifyCollectionChanged, and raises a CollectionChanged event
• the source is a dictionary, implements Epiforge.Extensions.Collections.INotifyDictionaryChanged<TKey, TValue>, and raises a DictionaryChanged event
• the elements in the enumerable (or the values in the dictionary) implement INotifyPropertyChanged and raise a PropertyChanged event
• a reference enclosed by a selector or a predicate passed to the method implements INotifyCollectionChanged, Epiforge.Extensions.Collections.INotifyDictionaryChanged<TKey, TValue>, or INotifyPropertyChanged and raises one of their events

That last one might be a little surprising, but it is because every selector and predicate passed to an Observable Query method becomes an observable expression (see above). This means that you cannot pass one that an ExpressionObserver cannot observe (for example, a lambda expression that cannot be converted to an expression tree or that contains nodes that are unsupported). In exchange, all of the notification plumbing is handled for you.

Suppose, for example, you're working on an app that displays a list of notes and you want the notes to be shown in descending order of when they were last edited.

var notes = new ObservableCollection<Note>();
var collectionObserver = new CollectionObserver();

var observedNotes = collectionObserver.ObserveReadOnlyList(notes);
var orderedNotes = observedNotes.ObserveOrderBy(note => note.LastEdited, isDescending: true);
notesViewControl.ItemsSource = orderedNotes;

From then on, as you add Notes to the notes observable collection, the IObservableCollectionQuery<Note> named orderedNotes will be kept ordered so that notesViewControl displays them in the preferred order.

Since queries subscribe to events for you, you need to call Dispose on them when you no longer need them.

void Page_Unload(object? sender, EventArgs e)
{
    orderedNotes.Dispose();
    observedNotes.Dispose();
}

Since the ExpressionObserver has a number of options governing its behavior, you may pass one you've made to the constructor of CollectionObserver to ensure those options are obeyed when observable expressions are created for your queries.

How Observable Queries Work and When to Use Them

It is worth being plain about what kind of thing this is, because "LINQ, but observable" undersells it and sets the wrong expectations.

A LINQ query is a description of a computation you run. Run it again and it does all of the work again. An Observable Query is not re-run. It is a small machine that holds the answer and repairs it, so when something changes, only the parts of the answer that depended on that thing are recomputed. The work is proportional to what changed rather than to how much data you have. If you want the name the literature uses for this idea, it is incremental, or self-adjusting, computation.

Three things that might otherwise look like arbitrary restrictions fall straight out of that:

1. Your selectors and predicates have to be expression trees rather than delegates because the machine has to read them to find out what they depend on. A delegate is opaque; there is nothing in it to subscribe to.
2. You have to dispose of a query because it is holding subscriptions to everything it depends on, and those subscriptions are the entire reason the answer stays right.
3. Faults reach you through OperationFault instead of being thrown, because the evaluation that failed happened later, on whichever thread evaluated the change. By then there is no call of yours left on the stack to throw out of.

What is not free is construction. Building the machine means building an observable expression for every element the query touches, and that is proportional to the size of the collection. So build a query once and hold onto it. Do not build one per frame, per request, or per keystroke. The bargain is that you pay up front and then stop paying to read.

The same goes for the lambdas you hand it. The observer optimizes, analyzes and compiles a lambda once and remembers the result by the instance you gave it, not by what the lambda says, and a lambda written inline is a new instance every time that line runs. So when you build queries over many collections, a query per row or per entity, keep each selector and predicate in a static readonly field and pass the same one every time. Over 256 one-element collections, ObserveWhere given a held predicate took 118 μs, and given the same predicate written inline, 14,229 μs, a figure which varied by about a third from one process to the next where the held one barely moved.

Reading is also cheaper than being told. A query subscribes to the one it is built on only while something is subscribed to it, and a filtered query works out where a change landed, and describes it, only when something will receive that description. So subscribe when you need to be told what changed, and simply read the query when you only need its answer to be right.

Which is also how to decide whether you want one. If you compute a result once and move on, plain LINQ is cheaper and simpler, and you should use it. If a result has to stay correct across a long run of small changes, such as a list someone is looking at, a running total, or a filter someone is typing into, that is what these are for.

When a Query Faults

The observable expressions a query builds are not yours to see, so their faults reach you through the query instead: every Observable Query has an OperationFault property. Subscribe to its PropertyChanging and PropertyChanged events to be told when one of its observable expressions, or the query as a whole, runs into a problem. If there is more than one fault in play, the value of OperationFault is an AggregateException.

Keys and Order

Dictionary queries adopt the key comparer of the dictionary they observe, discovering it through Epiforge.Extensions.Collections.Generic.IHashKeys<TKey> or a Dictionary<TKey, TValue>'s own Comparer, so a query over a case-insensitive dictionary is itself case-insensitive.

ObserveGroupBy, ObserveToLookup, and ObserveDistinct do not order their results the way LINQ does. Groupings are ordered by when they were created and the elements of a grouping by when they were added, rather than by where they occur in the source. This is deliberate: holding a grouping at the position of its key's first occurrence would mean moving that grouping every time an element was inserted ahead of it, announcing a change to something whose membership did not change, which is the opposite of what an Observable Query is for. Call ObserveOrderBy on the query, or on a grouping, when you want a defined order.

Enumerate Rather Than Index

Reach for foreach rather than the indexer, because the difference between them is larger than it looks and grows with the collection. An enumeration takes the query's lock once and then walks a list, while the indexer takes that lock again for every element you ask for; on a large collection it must also find each one in a tree, because a query keeps its elements' positions in one so that a change repairs only what it touched. A query does remember the position it handed out last and searches outward from there, so asking for positions in order, or near one another, costs a fraction of asking for them at random, and what remains is mostly the repeated locking rather than the search. Walking ten thousand elements by index instead of by enumerator measured 25x to 50x slower in order, and 120x to 150x out of order; at a hundred elements it was 10x to 15x, and there the repeated locking is the whole of it. Where you do need elements by position more than once, copy the query's contents and index the copy.

Choosing Between Observable Queries and DynamicData

DynamicData is the nearest thing to this in .NET, and it is a good library. Both keep a derived collection correct as your data changes — filter, sort, group, project, aggregate — and both update the result when an element's property changes rather than only when the collection does. Here is how to tell which one you want.

Start with what you already know. If you know INotifyPropertyChanged, ObservableCollection<T> and LINQ, this library asks you to learn almost nothing else: you point it at the collection you already have, write ObserveWhere(person => person.Rank > 0), and bind the result. If you already know Rx, or you use ReactiveUI, DynamicData will feel like home and this library will feel like an unfamiliar dialect — and it is probably already somewhere in your dependency graph. Most of the rest follows from that one answer.

Use DynamicData if you are already in Rx; you need to combine several collections by set operations; you need live paging, virtualization, size limits or expiry; you need asynchronous projections; or you want the reassurance of a large and long-established user base.

Use this library if you want a live view of a collection you already have, with the least new vocabulary, and you care about what an individual property change costs.

Measured Against DynamicData

These are from the benchmarks in this repository, against DynamicData 9.4.33 at a thousand elements unless stated otherwise. Each propagation figure is per property change, above what the same changes cost with nothing observing them at all.

The zero is exact rather than rounded: a property change that does not move an element in or out of a filtered view allocates nothing here, at a thousand, ten thousand and a hundred thousand elements alike. This library re-evaluates the predicate in place and stays silent when the answer has not moved; DynamicData's model is a stream of change sets, so a refresh has to materialize one. Neither is a defect. One library pays per change and the other pays per change that matters.

Two of those rows move with the size of the view, in opposite directions, and this is the part worth reading twice.

• Sorting. DynamicData's cost per move grows with the collection while this library's barely does, so the two cross at about 1,500 elements. Below that DynamicData is 1.30x faster; at four thousand this library is 1.79x faster and at ten thousand 2.97x.
• Grouping. The reverse. DynamicData's cost per migration is flat while this library's grows, so the two cross at about 8,300 elements. Below that this library is 2.57x faster; at ten thousand DynamicData is 1.15x faster — though it holds 1.95x the memory to do it, 1,954 B per element against 1,003.

The grouping crossover is a trade rather than an oversight, and knowing which side of it you want is more useful than the number. A grouping here keeps its elements in the order they were added, so moving one out of its old group means finding it first, which is work proportional to the size of that group. DynamicData's groups are keyed rather than positional, so a removal is a dictionary operation and costs the same whatever the group holds. If you need the elements of a group in a stable order, that is what you are paying for. If you do not, DynamicData's shape is cheaper once groups get large. A lookup built with ObserveToLookup is the same shape as a grouping here and behaves the same way.

What decides both is the size of the view the operator sees, not the size of your collection. Filter ten thousand elements down to a thousand and then sort, and you are on the small-view side of the sorting crossover, where DynamicData wins; grouping that same thousand puts you well on this library's side of the grouping one.

Allocation does not cross. At every size measured, this library allocates less for the same work: nothing at all for a filtered view, 0.31x DynamicData's for grouping, 0.71x for sorting.

The propagation advantage is largest at the sizes most applications use, and it narrows above them. Per property change above the floor, this library costs 13.9 ns at a thousand elements, 15.9 ns at ten thousand and 65.0 ns at a hundred thousand, against 200.8, 224.5 and 331.0 ns — a lead of 14.4x, then 14.2x, then 5.1x. The allocation figure is unchanged across all three sizes; the time figure is not. A hundred thousand observations do not fit in cache, and a library which has driven its own per-change work to near zero has nothing left to hide a cache miss behind. The advantage shrinks from very large to large.

Composition behaves. Ordering or grouping a filtered view costs each library close to the sum of its parts rather than more, so a chain does not change which one to prefer — only the size of the view arriving at each stage does.

Two more things worth knowing before you weigh any of the above.

A live view is not free in either library. One over ten thousand elements holds about 9 MB here and about 19 MB in DynamicData, against 960 KB for the elements themselves. Building a view is likewise proportional to the size of the collection in both. Build one and keep it; neither library rewards building views casually.

ToObservableChangeSet() over an existing ObservableCollection<T> costs DynamicData about 210x what its own SourceCache does for the same property changes. That is the path you land on if you adopt it without changing where your data lives, and it is worth knowing about before you do.

These comparisons were written by someone who does not use DynamicData, which is a real limitation on them. The harness is in this repository, the workloads are ordinary ones, and corrections are welcome.