Parsing a single-statement boolean expression tree

Question

MSDN documentation has a nice example of parsing an expression tree:

// Create an expression tree.
Expression<Func<int, bool>> exprTree = num => num < 5;

// Decompose the expression tree.
ParameterExpression param = (ParameterExpression)exprTree.Parameters[0];
BinaryExpression operation = (BinaryExpression)exprTree.Body;
ParameterExpression left = (ParameterExpression)operation.Left;
ConstantExpression right = (ConstantExpression)operation.Right;

Console.WriteLine("Decomposed expression: {0} => {1} {2} {3}",
              param.Name, left.Name, operation.NodeType, right.Value);

But I've not seen an example of how to parse something like this:

MyDomainObject foo;
Expression<Func<bool>> exprTree = () => ((foo.Scale < 5 || foo.Scale > 20) && foo.Scale <> -100) || foo.IsExempt;

My goal is to find or build a utility that can (1) handle any level of parenthetical nestings and (2) produces a string containing an equivalent SQL "where" clause as a product of parsing the expression tree. Anyone have a code snippet that may help or know a nuget package that addresses this?

For the nested expression I have above, assuming a DB table called 'MyDomainObject', the correct SQL where clause string output would be:

(( Scale < 5 or Scale > 20) and Scale != -100) or IsExempt = true

Obviously my imagined parser makes the assumption, in the absence of a binary operator, to simply assert 'true', as in the case of "IsExempt = true"

Answer 1

Here is an implementation that will at least transform your input into a valid SQL expression. You need to implement more expression types yourself but it gives you an idea of how it works.

This answer happens to be very similar to Kazetsukai's answer but it uses Expression.NodeType to find the operators since there will be no MethodInfos in the expression tree.

Also be aware that this produces more parentheses than actually needed. To reduce the number of parentheses the expression needs to be analysed further considering the operator precedence in SQL.

public static string GetSqlExpression(Expression expression)
{
    if (expression is BinaryExpression)
    {
        return string.Format("({0} {1} {2})",
            GetSqlExpression(((BinaryExpression)expression).Left),
            GetBinaryOperator((BinaryExpression)expression),
            GetSqlExpression(((BinaryExpression)expression).Right));
    }

    if (expression is MemberExpression)
    {
        MemberExpression member = (MemberExpression)expression;

        // it is somewhat naive to make a bool member into "Member = TRUE"
        // since the expression "Member == true" will turn into "(Member = TRUE) = TRUE"
        if (member.Type == typeof(bool))
        {
            return string.Format("([{0}] = TRUE)", member.Member.Name);
        }

        return string.Format("[{0}]", member.Member.Name);
    }

    if (expression is ConstantExpression)
    {
        ConstantExpression constant = (ConstantExpression)expression;

        // create a proper SQL representation for each type
        if (constant.Type == typeof(int) ||
            constant.Type == typeof(string))
        {
            return constant.Value.ToString();
        }

        if (constant.Type == typeof(bool))
        {
            return (bool)constant.Value ? "TRUE" : "FALSE";
        }

        throw new ArgumentException();
    }

    throw new ArgumentException();
}

public static string GetBinaryOperator(BinaryExpression expression)
{
    switch (expression.NodeType)
    {
        case ExpressionType.Equal:
            return "=";
        case ExpressionType.NotEqual:
            return "<>";
        case ExpressionType.OrElse:
            return "OR";
        case ExpressionType.AndAlso:
            return "AND";
        case ExpressionType.LessThan:
            return "<";
        case ExpressionType.GreaterThan:
            return ">";
        default:
            throw new ArgumentException();
    }
}

The result is:

(((([Scale] < 5) OR ([Scale] > 20)) AND ([Scale] <> -100)) OR ([IsExempt] = TRUE))

Call the method like this:

string sqlExpression = GetSqlExpression(exprTree.Body);

I would suggest to build the expression tree in a more functional way. Instead of building a Func<bool> using a concrete foo you should use a Func<Foo, bool>. However, it will work anyway. It just doesn't look right.

Expression<Func<Foo, bool>> exprTree =
    (foo) => ((foo.Scale < 5 || foo.Scale > 20) && foo.Scale != -100) || foo.IsExempt == true;

Obviously it is usually not needed to build a SQL text yourself when you can use LINQ to Entities. Both LINQ to entities and expression trees require .NET 3.5 and you can actually Translate LINQ to sql statement.

I'm not sure if an expression like IsExempt = TRUE will work on SQL Server. I think it should be IsExempt = 1 since the datatype is bit. Also expressions like Value == null or Value != null need to be handled seperately since you cannot use Value = NULL or Value <> NULL in a SQL expression. It must be Value IS NULL or Value IS NOT NULL.

Answer 2

So it sounds like your problem is not 'parsing' as such (since the expression has already been parsed as a C# expression), what you want is to traverse the expression tree and output a SQL expression.

I wouldn't recommend rolling your own code for it if you can avoid it. For most people, LINQ to Entities would probably be the better way to go as it basically does this for you, whilst hiding the SQL altogether.

If you have other requirements (like lower .NET version, or you MUST have the SQL string), and are willing to write the code yourself, you could do this with a recursive function. This function could take an expression and return the SQL clause as a string.

Something along the lines of (haven't tested this, treat it as pseudocode):

public string WriteClause(Expression exp)
{
    if (exp is ParameterExpression)
    {
        return (exp as ParameterExpression).Name;
    }
    else if (exp is BinaryExpression)
    {
        var binaryExpression = exp as BinaryExpression;

        return "(" +
               WriteClause(binaryExpression.Left) + " "
               GetSqlOperator(binaryExpression.Method) + " "
               WriteClause(binaryExpression.Right) +
               ")";
    }
    else if...

    ...etc...

}

public string GetSqlOperator(MethodInfo method)
{
    switch (method.Name)
    {
        case "Add":
            return "+";
        case "Or":
            return "or";

        ...etc...
    }
}

Being recursive means this approach should handle any level of parenthetical depth. It is a little naïve, so it will put in more parentheses than you need.