C# Expression Comparison

Question

Let's say I have following expressions on a collection:

var people = new List<Person>
{
     new Person {FullName = "Some Dude", Age = 45},
     new Person {FullName = "Another Dude", Age = 28},
     new Person {FullName = "Some Other Dude", Age = 36}
 };

var filtered = people.Where(person => person.Age > 28 && person.FullName.StartsWith("So"));
var narrowlyFiltered = people.Where(person => person.Age > 36 && person.FullName.StartsWith("Some"));

Is there a way to compare these two expressions and deduce that second expression is subset of first one on runtime? Without enumerating or anything else. I just have expressions and I am trying to find out if these expressions intersect or contains one another.

Answer 1

You will have to decompose each Expression into all the possible inherited types (MethodCallExpression, ConditionalExpression, etc.), then walk each decomposition in parallel and check each possible parameters... It will be a little long to code... You can inspire yourself from ExpressionEqualityComparer

Answer 2

In case you can enumerate your collections, you can first put the elements in a HashSet<T> and then run the HashSet<T>.IsSubSet on it:

HashSet<T> hs = new HashSet<T>(filtered);
HashSet<T> hs2 = new HashSet<T>(narrowlyFiltered);
hs.IsSubSetOf(hs2); //<- booleans saying true or false

Otherwise, this problems is an undecidable problem in general. Although there are heuristics that can work for many cases. You could for instance try to use code contracts that aim to deduce this at compile time.

Proof:

The formal variant is: given two Turing machines (methods, delegates, pointers), does every string contained in the first language is contained in the second?
Undecidable
proof: given it was decidable, EQ_TM would be decidable: simply first validate whether the first Turing machine is a subset of the second and vice versa. If both are subsets, we know they accept the same set of strings.

In other words, if you could do that, you could also deduce if two functions produce the same result, which cannot be implemented.