Syntax tree and LINQ alternative when interacting with SQL databases

In this article, using the example of simple logical expressions, it will be shown what an abstract syntax tree is and what you can do with it. An alternative to LINQ expressions for executing queries against SQL databases will also be considered.

Developer's story

It was a Legacy project and I was asked to improve its "advanced" filtering capabilities.

They used to have something like this:

And they wanted something like this:

, «» :

CREATE PROCEDURE dbo.SomeContextUserFind
    (@ContextId int, @Filter nvarchar(max)) AS
BEGIN

DECLARE @sql nvarchar(max) = 
    N'SELECT U.UserId, U.FirstName, U.LastName
    FROM [User] U
    INNER JOIN [SomeContext] [C]
      ON ....
    WHERE [C].ContextId = @p1 AND ' + @Filter;

EXEC sp_executesql 

    @sql,
    N'@p1 int',
    @p1=@ContextId
END

, , :

string BuildFilter(IEnumerable<FilterItem> items)
{
    var builder = new StringBuilder();
    foreach (var item in items)
    {
        builder.Append(item.Field);
        bool isLike = false;
        switch (item.Operation)
        {
            case Operation.Equals:
                builder.Append(" = ");
                break;
            case Operation.Like:
                isLike = true;
                builder.Append(" LIKE ");
                break;
            //...
        }
        builder.Append('\'');
        if (isLike)
            builder.Append('%');
        builder.Append(Escape(item.Value));
        if (isLike)
            builder.Append('%');
        builder.Append('\'');
    }
    return builder.ToString();
}

, , - , , , ( ) . , , , - .

, , — «FilterItem» , , , .

« », , , , , .

-, , , :

[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Doe')

:

, , , :

abstract class Expr
{ }

class ExprColumn : Expr
{
    public string Name;
}

class ExprStr : Expr
{
    public string Value;
}

abstract class ExprBoolean : Expr
{ }

class ExprEqPredicate : ExprBoolean
{
    public ExprColumn Column;
    public ExprStr Value;
}

class ExprAnd : ExprBoolean
{
    public ExprBoolean Left;
    public ExprBoolean Right;
}

class ExprOr : ExprBoolean
{
    public ExprBoolean Left;
    public ExprBoolean Right;
}

, , :

var filterExpression = new ExprAnd
{
    Left = new ExprEqPredicate
    {
        Column = new ExprColumn
        {
            Name = "FirstName"
        },
        Value = new ExprStr
        {
            Value = "John"
        }
    },
    Right = new ExprOr
    {
        Left = new ExprEqPredicate
        {
            Column = new ExprColumn
            {
                Name = "LastName"
            },
            Value = new ExprStr
            {
                Value = "Smith"
            }
        },
        Right = new ExprEqPredicate
        {
            Column = new ExprColumn
            {
                Name = "LastName"
            },
            Value = new ExprStr
            {
                Value = "Doe"
            }
        }
    }
};

, , « », , «», .

« » — ( ) ( ) . . , ( ) :

<eqPredicate> ::= <column> = <str>
<or> ::= <eqPredicate>|or|<and> OR <eqPredicate>|or|<and>
<and> ::= <eqPredicate>|(<or>)|<and> AND <eqPredicate>|(<or>)|<and>

: «» , , , , . .

— , , , , .

SQL

, , .

— (Pattern Matching), :

var filterExpression = ...;

StringBuilder stringBuilder = new StringBuilder();
Match(filterExpression);

void Match(Expr expr)
{
    switch (expr)
    {
        case ExprColumn col:
            stringBuilder.Append('[' + Escape(col.Name, ']') + ']');
            break;
        case ExprStr str:
            stringBuilder.Append('\'' + Escape(str.Value, '\'') + '\'');
            break;
        case ExprEqPredicate predicate:
            Match(predicate.Column);
            stringBuilder.Append('=');
            Match(predicate.Value);
            break;
        case ExprOr or:
            Match(or.Left);
            stringBuilder.Append(" OR ");
            Match(or.Right);
            break;
        case ExprAnd and:
            ParenthesisForOr(and.Left);
            stringBuilder.Append(" AND ");
            ParenthesisForOr(and.Right);
            break;
    }
}

void ParenthesisForOr(ExprBoolean expr)
{
    if (expr is ExprOr)
    {
        stringBuilder.Append('(');
        Match(expr);
        stringBuilder.Append(')');
    }
    else
    {
        Match(expr);
    }
}

:

[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Joe')

, !

""

, - — « (Visitor)». , , ( ), , . :

interface IExprVisitor
{
    void VisitColumn(ExprColumn column);
    void VisitStr(ExprStr str);
    void VisitEqPredicate(ExprEqPredicate eqPredicate);
    void VisitOr(ExprOr or);
    void VisitAnd(ExprAnd and);
}

( ) :

abstract class Expr
{
    public abstract void Accept(IExprVisitor visitor);
}

class ExprColumn : Expr
{
    public string Name;

    public override void Accept(IExprVisitor visitor)
        => visitor.VisitColumn(this);
}

class ExprStr : Expr
{
    public string Value;

    public override void Accept(IExprVisitor visitor)
        => visitor.VisitStr(this);
}
...

sql :

class SqlBuilder : IExprVisitor
{
    private readonly StringBuilder _stringBuilder 
        = new StringBuilder();

    public string GetResult()
        => this._stringBuilder.ToString();

    public void VisitColumn(ExprColumn column)
    {
        this._stringBuilder
            .Append('[' + Escape(column.Name, ']') + ']');
    }

    public void VisitStr(ExprStr str)
    {
        this._stringBuilder
            .Append('\'' + Escape(str.Value, '\'') + '\'');
    }

    public void VisitEqPredicate(ExprEqPredicate eqPredicate)
    {
        eqPredicate.Column.Accept(this);
        this._stringBuilder.Append('=');
        eqPredicate.Value.Accept(this);
    }

    public void VisitAnd(ExprAnd and)
    {
        and.Left.Accept(this);
        this._stringBuilder.Append(" AND ");
        and.Right.Accept(this);
    }

    public void VisitOr(ExprOr or)
    {
        ParenthesisForOr(or.Left);
        this._stringBuilder.Append(" OR ");
        ParenthesisForOr(or.Right);
    }

    void ParenthesisForOr(ExprBoolean expr)
    {
        if (expr is ExprOr)
        {
            this._stringBuilder.Append('(');
            expr.Accept(this);
            this._stringBuilder.Append(')');
        }
        else
        {
            expr.Accept(this);
        }
    }

    private static string Escape(string str, char ch)
    {
        ...
    }
}

:

var filterExpression = BuildFilter();

var sqlBuilder = new SqlBuilder();
filterExpression.Accept(sqlBuilder);
string sql = sqlBuilder.GetResult();

:

[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Joe')

" (Visitor)" . , , , IExprVisitor , , ( ).

, .

-, ?

, , sql :

, , .

-, ?

, . «» , «» — . , . ( ), .

, , “NotEqual”, () , :

class ExprNotEqPredicate : ExprBoolean
{
    public ExprColumn Column;
    public ExprStr Value;

    public override void Accept(IExprVisitor visitor)
        => visitor.VisitNotEqPredicate(this);
}

, , SQL:

public void VisitNotEqPredicate(ExprNotEqPredicate exprNotEqPredicate)
{
    exprNotEqPredicate.Column.Accept(this);
    this._stringBuilder.Append("!=");
    exprNotEqPredicate.Value.Accept(this);
}

, , MS SQL , , , .

, SQL Server SQL, :

, . C#. :

class ExprColumn : Expr
{
    ...
    public static ExprBoolean operator==(ExprColumn column, string value)
        => new ExprEqPredicate 
        {
            Column = column, Value = new ExprStr {Value = value}
        };

    public static ExprBoolean operator !=(ExprColumn column, string value)
        => new ExprNotEqPredicate
        {
            Column = column, Value = new ExprStr {Value = value}
        };
}

abstract class ExprBoolean : Expr
{
    public static ExprBoolean operator &(ExprBoolean left, ExprBoolean right)
        => new ExprAnd{Left = left, Right = right};

    public static ExprBoolean operator |(ExprBoolean left, ExprBoolean right)
        => new ExprOr { Left = left, Right = right };
}

:

ExprColumn firstName = new ExprColumn{Name = "FirstName"};
ExprColumn lastName = new ExprColumn{Name = "LastName"};

var expr = firstName == "John" & (lastName == "Smith" | lastName == "Doe");

var builder = new SqlBuilder();
expr.Accept(builder);
var sql = builder.GetResult();

:

[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Doe')

: C# && ||, , , ( true || ....), ( SQL).

, , ? - - (View Derived Table) ( ) .

! SQL SELECT:

, , (, ), , SQL.

LINQ

, , LINQ, . C# , , Entity Framework «LINQ to SQL», SQL.

, C#, SQL! C# SQL – , .

— C# SQL. , .

, , , . , , intellisense - . … , LEFT JOIN LINQ)

, (INSERT, UPDATE, DELETE MERGE) , .

Just an example of what can be done using real SQL syntax as a basis ( taken from here ):

await InsertInto(tCustomer, tCustomer.UserId)
    .From(
        Select(tUser.UserId)
            .From(tUser)
            .Where(!Exists(
                SelectOne()
                    .From(tSubCustomer)
                    .Where(tSubCustomer.UserId == tUser.UserId))))
    .Exec(database);

Conclusion

The syntax tree is a very powerful data structure that you are likely to come across sooner or later. Maybe it will be LINQ expressions, or maybe you need to create a Roslyn parser, or maybe you want to create your own syntax yourself, as I did a few years ago, to refactor one legacy project. In any case, it is important to understand this structure and be able to work with it.

Link to SqExpress is a project that partially includes the code from this article.