How do you build a recursive Expression tree in Entity Framework Core?

Question

We are using EFCore.SqlServer.HierarchyId to represent a hierarchy in our data.

My goal is to return the descendants of an object with a particular path of indeterminate length, e.g. given a tree with the hierarchy one->two->three->four, the path one/two/three would return four

Knowing the length of the path, I can make a query like this:

var collections = await context.Collections.Where(c => c.CollectionHierarchyid.IsDescendantOf(
    context.Collections.FirstOrDefault(c1 => c1.FriendlyId == "three" &&
        context.Collections.Any(c2 => c2.CollectionHierarchyid == c1.CollectionHierarchyid.GetAncestor(1) && c2.FriendlyId == "two" &&
            context.Collections.Any(c3 => c3.CollectionHierarchyid == c2.CollectionHierarchyid.GetAncestor(1) && c3.FriendlyId == "one")
        )
    ).CollectionHierarchyid
)).ToListAsync();

But how would you go about this if the length of the path is unknown? I can't call a recursive function from the expression because it won't compile from Linq to Entity Sql.

I know the answer lies somewhere in using System.Linq.Expressions to build the expression, but I am not sure where to start.

Answer 1

The problem can be solved without dynamic expression tree generation, at least not directly, but using standard LINQ query operators.

Let say you have a hierarchical entity like this

public class Entity
{
    public HierarchyId Id { get; set; }
   // other properties...
}

Given a subquery returning the full set

IQueryable<Entity> fullSet = context.Set<Entity>();

and subquery defining some filtered subset containing the desired ancestors

IQueryable<Entity> ancestors = ...;

Now getting all direct and indirect descendants can easily be achieved with

IQueryable<Entity> descendants = fullSet
    .Where(d => ancestors.Any(a => d.Id.IsDescendantOf(a.Id));

So the question is how to build ancestors subquery dynamically.

Applying some filter to the full set and retrieving the direct ancestors filtered by another criteria can be done by using simple join operator

from p in fullSet.Where(condition1)
join c in fullSet.Where(condition2)
on p.Id equals c.Id.GetAncestor(1)
select c

Hence all you need is to apply that recursively, e.g. having

IEnumerable<TArg> args = ...;

representing the filtering criteria arguments ordered by level, then the query can be built as follows

var ancestors = args
    .Select(arg => fullSet.Where(e => Predicate(e, arg)))
    .Aggregate((prevSet, nextSet) =>
        from p in prevSet join c in nextSet on p.Id equals c.Id.GetAncestor(1) select c);

With that being said, applying it to your example:

IEnumerable<string> friendlyIds = new [] { "one", "two", "three" };

var fullSet = context.Collections.AsQueryable();

var ancestors = friendlyIds
    .Select(friendlyId => fullSet.Where(e => e.FriendlyId == friendlyId))
    .Aggregate((prevSet, nextSet) =>
        from p in prevSet join c in nextSet on p.CollectionHierarchyid equals c.CollectionHierarchyid.GetAncestor(1) select c);

var descendants = fullSet
    .Where(d => ancestors.Any(a => d.CollectionHierarchyid.IsDescendantOf(a.CollectionHierarchyid));