LINQ to Custom Query Language?

Question

I'm writing a tool that requires data from a source. This source will be user specified, and may be things like an SQL back-end, a proprietary database, flat file system, who knows.

I'd like my interface into fetching these types of query, to use Linq, as it seems the most C# friendly, and can leverage a lot of .NET code.

I've been doing some research, and have started by building an IQueryProvider through the great tutorial here. It's gotten me a large part of the way, but now I'm confused as to the best way of having the users convert the expression tree into their custom code.

I'm trying to figure out the best way to provide an easy interface for users to specify how to turn an expression tree into custom "code" (i.e., "SQL"), and it seems rather cumbersome and complex -- I imagine because it is exactly that.

My question is, what is the best way to go about converting an expression tree into a custom language?

Nearest I can tell is that I am to use the 'Context' class to do my custom parsing logic, but the API I use seems rather low level - are there any higher level operations I can do to simply map operations to strings?

Answer 1

So, I did investigate the visitor pattern, but I couldn't get it to work the way I liked, so I kinda hacked a solution. :/

I've used the base sample to create a base QueryContext that parses the tree and builds up a collections of strings. What I ended up with was something like this. It's by no means complete, but it's a decent start:

    public object Execute(Expression expression, bool IsEnumerable)
    {
        // Find the call to Where() and get the lambda expression predicate.
        InnermostWhereFinder whereFinder = new InnermostWhereFinder();
        MethodCallExpression whereExpression = whereFinder.GetInnermostWhere(expression);
        LambdaExpression lambdaExpression = (LambdaExpression)((UnaryExpression)(whereExpression.Arguments[1])).Operand;

        // Send the lambda expression through the partial evaluator.
        lambdaExpression = (LambdaExpression)Evaluator.PartialEval(lambdaExpression);

        // Assemble the strings necessary to build this.
        var strings = new List<string>();

        GetStrings(lambdaExpression.Body, strings);

        var query = String.Join(" ", strings);

        return ExecuteQuery(query);
    }

    public abstract object ExecuteQuery(string whereClause);

    public abstract Dictionary<ExpressionType, string> ExpressionTypeToStringMap { get; }

    public abstract string FormatFieldName(string fieldName);
    public abstract string FormatConstant(string constant);

    void GetStrings(System.Linq.Expressions.Expression expression, List<string> toReturn)
    {
        if (expression is BinaryExpression)
        {
            // Binary expression.  Recurse and add to the list.
            GetStrings((BinaryExpression)(expression), toReturn);
        }
        else if (expression is MemberExpression)
        {
            var e = (MemberExpression)(expression);
            toReturn.Add(FormatFieldName(e.Member.Name));
        }
        else if (expression is ConstantExpression)
        {
            var e = (ConstantExpression)(expression);
            toReturn.Add(FormatConstant((string)(e.Value)));
        }
        else
        {
            throw new NotImplementedException("Unaware of how to handle type " + expression.GetType().ToString());
        }
    }

    string NodeTypeToString(ExpressionType type)
    {
        var map = ExpressionTypeToStringMap;

        if(map.ContainsKey(type))
        {
            return map[type];
        }

        throw new NotImplementedException("Type '" + type.ToString() + "' not implemented in ExpressionTypeToStringMap.");
    }

    void GetStrings(BinaryExpression expression, List<string> toReturn)
    {
        toReturn.Add("(");

        if (expression.Left != null)
            GetStrings(expression.Left, toReturn);

        toReturn.Add(NodeTypeToString(expression.NodeType));

        if (expression.Right != null)
            GetStrings(expression.Right, toReturn);

        toReturn.Add(")");
    }

Better implementations are welcome, but for now at least I'm unblocked.

Answer 2

In general, the best way to convert a Tree structure into some other form is to use the visitor pattern.

Specifically check out the ExpressionVisitor class on msdn.

Answer 3

There is no easy or straight forward way of converting expression tree in to your custom query language. You might want to give LinqExtender a try

http://mehfuzh.github.com/LinqExtender/

Which implements a visitor pattern for converting between linq and your dsl.

LinqExtender is a toolkit for building custom LINQ providers. It provides an abstracted layer over the original IQyeryable and IQueryProvider implementation and provides a simplified syntax tree. Moreover, it covers things like projection , method calls , ordery by , member parsing, etc internally. Therefore developer can focus more on his main task minus the complexity

.