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.

Answer 3

It all depends how you weight what is equal, what is more important when comparing expressions etc. For example if you have completely different filter than you won't possibly know query difference before actually executing it.

To keep full control over your comparison create a filter class with some properties which can be used for filtering and then build expressions and compare using this class instead of using visitors. You can prepare common function for comparing ints, int pairs (for ranges) etc.

I did not check the code below but it should be a good start.

public class PersonFilter:  IComparable<PersonFilter>
{
    public int? MinAge { get; set; }

    public int? MaxAge { get; set; }

    public string NamePrefix { get; set; }

    public Expression<Predicate<Person>> Filter
    {
        return people => people.Where(person => (!MinAge.HasValue || person.Age > MinAge.Value) && 
            (!MaxAge.HasValue || person.Age < MaxAge.Value) && 
            (string.IsNullOrEmpty(NamePrefix) || person.FullName.StartsWith(NamePrefix))
    }

    // -1 if this filter is filtering more than the other
    public int CompareTo(PersonFilter other)
    {
        var balance = 0; // equal
        if(MinAge.HasValue != other.MinAge.HasValue)
        {
            balance += MinAge.HasValue ? -1 : 1;
        }
        else if(MinAge.HasValue)
        {
            balance += MinAge.Value.CompareTo(other.MinAge.Value) ?
        }
        if(string.IsNullOrEmpty(NamePrefix) != string.IsNullOrEmpty(other.NamePrefix))
        {
            balance += string.IsNullOrEmpty(NamePrefix) ? -1 : 1;
        }
        else if(!string.IsNullOrEmpty(NamePrefix))
        {
            if(NamePrefix.StartsWith(other.NamePrefix))
            {
                balance -= 1;
            }
            else if(other.NamePrefix.StartsWith(NamePrefix))
            {
                balance += 1;
            }
            else
            {
                // if NamePrefix is the same or completely different let's assume both filters are equal
            }
        }
        return balance;
    }

    public bool IsSubsetOf(PersonFilter other)
    {
        if(MinAge.HasValue != other.MinAge.HasValue)
        {
            if(other.MinAge.HasValue)
            {
                return false;
            }
        }
        else if(MinAge.HasValue && MinAge.Value < other.MinAge.Value)
        {
            return false;
        }

        if(string.IsNullOrEmpty(NamePrefix) != string.IsNullOrEmpty(other.NamePrefix))
        {
            if(!string.IsNullOrEmpty(other.NamePrefix))
            {
                return false;
            }
        }
        else if(!string.IsNullOrEmpty(NamePrefix))
        {
            if(!NamePrefix.StartsWith(other.NamePrefix))
            {
            return false;
            }
        }

        return true;
    }
}

Answer 4

Have a look at the Specification design pattern

Once it's implemented then your specification in this case becomes

public class PersonNamedOlderThanSpecification : CompositeSpecification<Person>
{
    private string name;
    private int age;

    public PersonNamedOlderThanSpecification(string name, int age)
    {
        this.name = name;
        this.age = age;
    }


    public override bool IsSatisfiedBy(Person entity)
    {
        return (entity.Name.Contains(this.name)) && (entity.Age > age);
    }
}

Then you can use it like this:

var personSpecs = new PersonNamedOlderThanSpecification("So", 28);
var personSpecs2 = new PersonNamedOlderThanSpecification("Some", 36);

var filtered = people.FindAll(x => personSpecs.IsSatisfiedBy(x));
var adjusted = people.FindAll(x => personSpecs2.IsSatisfiedBy(x));

Answer 5

You can try this:

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"));

var intersection = filtered.Intersect(narrowlyFiltered);
if (intersection != null)
{
    if (intersection.Count() > 0)
    {
        //narrowlyFiltered is subset of filtered
    }
}