Parsing querystring into dynamic sql (LINQ)

Question

I don't visit nor ask things on here too much, so I hope this question is allowed.

I've been assigned a task, to implement a REST service, where the GET endpoint would basically work as an OData service. But not exactly. I tried convincing the project owner than just implementing a straight on OData service would be the better solution, but I was shot down.

I've attempted this already using brute force string parsing, and a very large cumbersome switch statement, but it's messy. And I'm wondering what would be a better approach for this type of thing.

Here are the specifics:

GET /store?query=<expr>
    assume <expr> is URLEncoded

EQUAL(field, val)
    field = table field name
    val = can be either a string or an int depending on the field
    
AND(expr1, expr2)
    expr1/exprr2 = any of valid functions, such as EQUAL(), NOT(), GREATER_THAN(), and LESS_THAN()
    
OR(expr1, expr2)
    expr1/exprr2 = any of valid functions, such as EQUAL(), NOT(), GREATER_THAN(), and LESS_THAN()
    
NOT(expr)
    expr1 = any of valid functions, such as EQUAL(), GREATER_THAN(), and LESS_THAN()
    
GREATER_THAN(field, val)
    field = table field name (must be an int field)
    val = int value to look for 
    
LESS_THAN(field, val)
    field = table field name (must be an int field)
    val = int value to look for 

Examples

Assume a List<StoreData> for the data itself:

public class StoreData 
{
    [Required]
    public string id { get; set; }
    [Required]
    public string title { get; set; }
    [Required]
    public string content { get; set; }
    [Required]
    public int views { get; set; }
    [Required]
    public int timestamp { set; get; }
}

GET /store?query=EQUAL(id, "100")                                   
  -> should fail, improper parameter type

GET /store?query=EQUAL(id, 100)                                     
  -> should be successful
 
GET /store?query=EQUAL(views, 5)                                    
  -> should be successful

GET /store?query=EQUAL(views, "190)                                 
  -> should fail, improper parameter type

GET /store?query=GREATER_THAN(views, 500)                           
  -> should be successful

GET /store?query=GREATER_THAN(views, "500")                         
  -> should fail, improper parameter type

GET /store?query=AND(EQUAL(id,"666"), EQUAL(views,100))             
  -> should be successful

GET /store?query=AND(NOT(EQUAL(id,"666")),EQUAL(views,100))         
  -> should be successful

GET /store?query=AND(EQUAL(id,"666"),GREATER_THAN(views,0))         
  -> should be successful

GET /store?query=AND(GREATER_THAN(views,"100"), EQUAL(id,"666"))    
  -> should fail, improper parameter type

GET /store?query=OR(EQUAL(id,"100"),EQUAL(id,"666"))                
  -> should be successful

GET /store?query=OR(EQUAL(id,100),GREATER_THAN(views,66))           
  -> should be successful

GET /store?query=NOT(EQUAL(id,"666"))                               
  -> should be successful

GET /store?query=EQUAL(title, "Title 756")                          
  -> should be successful

GET /store?query=EQUAL(TITLE, "TITLE 756")                          
  -> should be successful, just ensuring it's case insensitive

GET /store?query=EQUAL(blah, 100)                                   
  -> should fail, unrecognized field

Other than brute force, my thought was some type of lexical parser, but I know next to nothing about how to proceed.

Someone asked about the brute force parsing I've already done, so here it is... the main parsing logic

    // Ideally a whole expression parsing engine should be built, but I'm on a limited time frame
    // After working all night, and struggling on the OR, I added DynamicLinq thru NuGet, which made the OR
    // sooooooooo much easier.  I really wish I had to time to re-write this entire thing using that DynamicLinq
    // for everything... but on a time constraint here.  I wonder if the "customer" would accept a delay?  :)
    public List<StoreData> GetData(string sQueryString)
    {
        int iPos1 = sQueryString.IndexOf('(');
        int iPos2 = sQueryString.LastIndexOf(')');
        string firstAction = sQueryString.Substring(0, iPos1);

        // ideally if this were a database, this would be handled completely different with a EF dbContext
        // but this list is relatively small. In a production app, monitor this performance.
        // we build is as an IQueryable so we can add to the WHERE condition before running the SQL
        var theData = Startup.MockData.AsQueryable();

        // short cut for these first few types...
        // for functions that are not nested, _params.Length should equal 2
        // nested functions will produce _params.Length would be more, depending on the nesting level
        string[] _params = sQueryString.Substring(iPos1 + 1, (iPos2 - iPos1) - 1).Split(',');

        // since we're starting with the easy direct field functions first, we know there'll be 2 elements in _params
        string fieldName = _params[0].Trim();
        string fieldValue = _params[1].Trim();
        int iVal = 0;

        // EQUAL(field, val)
        // AND(expr1, expr2)
        //      AND(EQUAL(field, val), EQUAL(field, val))
        //      AND(EQUAL(field, val), NOT(EQUAL(field, val)))
        //      AND(EQUAL(field, val), GREATER_THAN(field, val))
        // OR(expr1, expr2)
        //      OR(EQUAL(field, val), EQUAL(field, val))
        //      OR(EQUAL(field, val), NOT(EQUAL(field, val)))
        //      OR(EQUAL(field, val), GREATER_THAN(field, val))
        // NOT(expr)
        // GREATER_THAN(field, val)
        // LESS_THAN(field, val)
        //
        // functions with expression parameters (expr<x>) can be any of the functions directly operating on fields

        switch (firstAction.ToUpper())
        {
            // these first 3 should be the easiest to deal with initially since the operate
            // directly on fields and values as opposed to an expression
            case "EQUAL":
                theData = HandleEQUAL(theData, fieldName, fieldValue);
                break;

            case "GREATER_THAN":
            case "LESS_THAN":
                iVal = -1;
                if(!int.TryParse(fieldValue.Trim(), out iVal))
                {
                    throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                }

                if (iVal == -1)
                {
                }

                if(!_intProperties.Any(x => x.ToUpper() == fieldName.ToUpper()))
                {
                    throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                }

                if(firstAction.ToUpper() == "GREATER_THAN")
                {
                    theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) > iVal);
                }
                else if (firstAction.ToUpper() == "LESS_THAN")
                {
                    theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) < iVal);
                }
                break;

            // I'm not sure how many different permutations there can be with this command
            // but for now only handling EQUAL as the parameter.  It doesn't make much sense to
            // handle a NOT(GREATER_THAN()) or NOT(LESS_THAN()) because they have mutually exclusive
            // selection commands already.  a NOT(GREATER_THAN()) is basically the same as LESS_THAN(),
            // and a NOT(LESS_THAN()) is a GREATER_THAN()
            //
            // do I need to worry about a NOT(AND(EQUAL(id, "1"), NOT(EQUAL(views, 666))) ?
            // or how about NOT(NOT(EQUAL(id, "100")) ??
            case "NOT":
                fieldName = fieldName.Replace("EQUAL(", "", StringComparison.OrdinalIgnoreCase).Trim();
                fieldValue = fieldValue.Replace(")", "").Trim();
                theData = theData.Where(x => ((string)x.GetValueByName(fieldName)) != fieldValue.Replace("\"", ""));
                break;

            // these are the painful ones, with many permutations
            // these 2 can be combined in many different statements, using a mixture of any of the top level commands
            // AND(EQUAL(id,"666"),EQUAL(views,100)) - shouldn't be too difficult
            // AND(NOT(EQUAL(id, "666")), EQUAL(views, 100)) - ARGH!!! 
            // AND(EQUAL(id,"666"),GREATER_THAN(views,100)) - 
            case "AND":
                #region Handles EQUAL() and NOT(EQUAL())
                // 1st expression in the AND(expr1, expr2) function call
                if (_params[0].Contains("EQUAL(", StringComparison.OrdinalIgnoreCase))
                { 
                    fieldName = _params[0].Replace("EQUAL(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    fieldValue = _params[1].Replace(")", "").Trim();

                    if(_stringProperties.Any(x => x.ToUpper() == fieldName.ToUpper()))
                    {
                        if (_params[0].Contains("NOT(", StringComparison.OrdinalIgnoreCase))
                        {
                            theData = HandleNOT_EQUAL(theData, fieldName, fieldValue);
                        }
                        else
                        {
                            theData = HandleEQUAL(theData, fieldName, fieldValue);
                        }
                    }
                    else if (_intProperties.Any(x => x.ToUpper() == fieldName.ToUpper()))
                    {
                        iVal = -1;
                        if(!Int32.TryParse(fieldValue.Trim(), out iVal))
                        {
                            throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                        }

                        if (_params[0].Contains("NOT(", StringComparison.OrdinalIgnoreCase))
                        {
                            theData = theData.Where(x => ((int) x.GetValueByName(fieldName)) != iVal);
                        }
                        else
                        {
                            theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) == iVal);
                        }
                    }

                }

                // 2nd expression in the AND(expr1, expr2) function call
                if (_params[2].Contains("EQUAL(", StringComparison.OrdinalIgnoreCase))
                {
                    fieldName = _params[2].Replace("EQUAL(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    fieldValue = _params[3].Replace(")", "").Trim();

                    if(_stringProperties.Any(x => x.ToUpper() == fieldName.ToUpper()))
                    {
                        if (_params[2].Contains("NOT(", StringComparison.OrdinalIgnoreCase))
                        {
                            theData = HandleNOT_EQUAL(theData, fieldName, fieldValue);
                        }
                        else
                        {
                            theData = HandleEQUAL(theData, fieldName, fieldValue);
                        }
                    }
                    else if (_intProperties.Any(x => x.ToUpper() == fieldName.ToUpper()))
                    {
                        iVal = -1;
                        if (!Int32.TryParse(fieldValue.Trim(), out iVal))
                        {
                            throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                        }

                        if (_params[0].Contains("NOT(", StringComparison.OrdinalIgnoreCase))
                        {
                            theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) != iVal);
                        }
                        else
                        {
                            theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) == iVal);
                        }
                    }
                }
                #endregion

                #region Handles GREATER_THAN() and LESS_THAN()
                if(_params[0].Contains("GREATER_THAN(", StringComparison.OrdinalIgnoreCase))
                {
                    fieldName = _params[0].Replace("GREATER_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    fieldValue = _params[1].Replace(")", "").Trim();

                    iVal = -1;
                    if (!Int32.TryParse(fieldValue.Trim(), out iVal))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    if (!_intProperties.Any(x => x.ToUpper() == (fieldName.ToUpper())))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) > iVal);
                }

                if (_params[2].Contains("GREATER_THAN(", StringComparison.OrdinalIgnoreCase))
                {
                    fieldName = _params[2].Replace("GREATER_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    fieldValue = _params[3].Replace(")", "").Trim();

                    iVal = -1;
                    if (!Int32.TryParse(fieldValue.Trim(), out iVal))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    if (!_intProperties.Any(x => x.ToUpper() == (fieldName.ToUpper())))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) > iVal);
                }

                if (_params[0].Contains("LESS_THAN(", StringComparison.OrdinalIgnoreCase))
                {
                    fieldName = _params[0].Replace("LESS_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    fieldValue = _params[1].Replace(")", "").Trim();

                    iVal = -1;

                    if (!Int32.TryParse(fieldValue.Trim(), out iVal))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    if (!_intProperties.Any(x => x.ToUpper() == (fieldName.ToUpper())))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) < iVal);
                }

                if (_params[2].Contains("LESS_THAN(", StringComparison.OrdinalIgnoreCase))
                {
                    fieldName = _params[2].Replace("LESS_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    fieldValue = _params[3].Replace(")", "").Trim();

                    iVal = -1;
                    if (!Int32.TryParse(fieldValue.Trim(), out iVal))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    if (!_intProperties.Any(x => x.ToUpper() == (fieldName.ToUpper())))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }

                    theData = theData.Where(x => ((int)x.GetValueByName(fieldName)) < iVal);
                }
                #endregion

                break;

            // the most challenging combination because adding onto an IQueryable is an AND, there is no alternative for an OR
            case "OR":
                // this one is gonna take some brute force
                // so I added Dynaimc LINQ via NuGet, which helped tremendously with this OR condition
                // seriously debating re-writing this entire thing using the functionality of the dynamic LINQ
                // while the code I wrote last night is far from elegant, it's working for the time being.  If
                // this were indeed a legitimate customer requested project, I would go back through and clean it
                // up significantly, but time is of the essence for the turn in on this project.
                int iVal1 = -1;
                int iVal2 = -1;

                ORCondition exprConditions = new ORCondition();

                #region Handles EQUAL() and NOT(EQUAL())
                if (_params[0].Contains("EQUAL(", StringComparison.OrdinalIgnoreCase))
                { 
                    exprConditions.Field1 = _params[0].Replace("EQUAL(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    exprConditions.Value1 = _params[1].Replace(")", "").Trim();
                    exprConditions.Operator1 = "==";

                    if(_stringProperties.Any(x => x.ToUpper() == exprConditions.Field1.ToUpper()) && !exprConditions.Value1.Contains("\""))
                    {
                        throw new Exception($"Malformed Query {exprConditions.Field1} parameter must be a string type");
                    }

                    if(_intProperties.Any(x => x.ToUpper() == exprConditions.Field1.ToUpper()) && exprConditions.Value1.Contains("\""))
                    {
                        throw new Exception($"Malformed Query {exprConditions.Field1} parameter must be an inttype");
                    }                            

                    if (_params[0].Contains("(NOT(", StringComparison.OrdinalIgnoreCase))
                    {
                        exprConditions.Not1 = true;
                        exprConditions.Operator1 = "!=";
                    }
                }

                if(_params[2].Contains("EQUAL(", StringComparison.OrdinalIgnoreCase))
                {
                    exprConditions.Field2 = _params[2].Replace("EQUAL(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    exprConditions.Value2 = _params[3].Replace(")", "").Trim();
                    exprConditions.Operator2 = "==";

                    if (_stringProperties.Any(x => x.ToUpper() == exprConditions.Field2.ToUpper()) && !exprConditions.Value2.Contains("\""))
                    {
                        throw new Exception($"Malformed Query {exprConditions.Field2} parameter must be a string type");
                    }

                    if (_intProperties.Any(x => x.ToUpper() == exprConditions.Field2.ToUpper()) && exprConditions.Value2.Contains("\""))
                    {
                        throw new Exception($"Malformed Query {exprConditions.Field2} parameter must be an inttype");
                    }

                    if (_params[2].Contains("(NOT(", StringComparison.OrdinalIgnoreCase))
                    {
                        exprConditions.Not2 = true;
                        exprConditions.Operator1 = "!=";
                    }
                }
                #endregion

                #region Handles GREATER_THAN() and LESS_THAN()
                if(_params[0].Contains("GREATER_THAN)", StringComparison.OrdinalIgnoreCase))
                {
                    exprConditions.Field1 = _params[0].Replace("GREATER_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    exprConditions.Value1 = _params[1].Replace(")", "").Trim();
                    exprConditions.Operator1 = ">";

                    // technically, there shouldn'ty be NOT(GREATER_THAN()) because that would
                    // pretty much be the same as LESS_THAN()
                    //if (_params[0].Contains("(NOT(", StringComparison.OrdinalIgnoreCase))
                    //{
                    //    exprConditions.Not1 = true;
                    //}

                    iVal1 = -1;
                    if (!Int32.TryParse(exprConditions.Value1, out iVal1))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }
                }

                if (_params[2].Contains("GREATER_THAN", StringComparison.OrdinalIgnoreCase))
                {
                    exprConditions.Field2 = _params[2].Replace("GREATER_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    exprConditions.Value2 = _params[3].Replace(")", "").Trim();
                    exprConditions.Operator2 = ">";

                    iVal2 = -1;
                    if (!Int32.TryParse(exprConditions.Value2, out iVal2))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }
                }

                if (_params[0].Contains("LESS_THAN(", StringComparison.OrdinalIgnoreCase))
                {
                    exprConditions.Field1 = _params[0].Replace("LESS_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    exprConditions.Value1 = _params[1].Replace(")", "").Trim();
                    exprConditions.Operator1 = "<";

                    iVal1 = -1;
                    if (!Int32.TryParse(exprConditions.Value1, out iVal1))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }
                }

                if (_params[2].Contains("LESS_THAN(", StringComparison.OrdinalIgnoreCase))
                {
                    exprConditions.Field2 = _params[2].Replace("LESS_THAN(", "", StringComparison.OrdinalIgnoreCase).Trim();
                    exprConditions.Value2 = _params[3].Replace(")", "").Trim();
                    exprConditions.Operator2 = "<";

                    iVal2 = -1;
                    if (!Int32.TryParse(exprConditions.Value2, out iVal2))
                    {
                        throw new Exception($"Malformed Query Parameter: {fieldName} parameter must be an int type");
                    }
                }
                #endregion

                exprConditions.Value1 = exprConditions.Value1.Replace("\"", "");
                exprConditions.Value2 = exprConditions.Value2.Replace("\"", "");

                // we should have everything parsed and the ORCondition populated with the appropriate
                // flags to help build the LINQ statement
                #region let's try this thing
                string dQuery = $"{exprConditions.Field1} {exprConditions.Operator1} ";

                if(_stringProperties.Any(x => x.ToUpper() == exprConditions.Field1.ToUpper()))
                {
                    dQuery += $"\"{exprConditions.Value1}\" OR ";
                }
                else if (_intProperties.Any(x => x.ToUpper() == exprConditions.Field1.ToUpper()))
                {
                    dQuery += $"{exprConditions.Value1} OR ";
                }

                dQuery += $"{exprConditions.Field2} {exprConditions.Operator2} ";

                if(_stringProperties.Any(x => x.ToUpper() == exprConditions.Field2.ToUpper()))
                {
                    dQuery += $"\"{exprConditions.Value2}\"";
                }
                else if(_intProperties.Any(x => x.ToUpper() == exprConditions.Field2.ToUpper()))
                {
                    dQuery += $"{exprConditions.Value2}";
                }

                theData = theData.Where(dQuery);
                #endregion

                break;

            default:
                throw new Exception($"Malformed Query Parameter: {firstAction} not a recognized function");
        }

        return theData.ToList();
    }

Answer 1

Although I'm no expert in parsers and creating Domain Specific Languages (other than the little introduction back when studying), I definitely think the solution you're looking for is a proper parser as also suggested in the comments.

Sprache, as someone already suggested, is one example of a library I stumbled upon that should be able to do the job for you. Most examples of Sprache using combinators/operators show the operator in-between the operands. Like-wise the Sprache helper function ChainOperator seems to expect the operator to appear in-between the operands which I didn't find an easy alternative for. This made finding a working recursive pattern a little difficult, but a fun challenge nonetheless.

Since you seem to be working on List-like structures, I expect it would be suitable to use expressions as the result of the parsing. These you can use like you've already been doing in the Linq based approach. So, what I came up with (with inspiration from different sources linked below) is something like what I have below.

To make it a little easier to wrap my head around how to structure the definitions in Sprache, I started out trying to write up the grammar definition in EBNF (a little simplified):

Term        := Comparer | Combinator

Combinator  := OperatorId,  '(',  Term,  ',',  Term,  ')'
OperatorId  := 'AND' | 'OR'

Comparer    := ComparerId,  '(',  Word,  ',',  Value,  ')'
ComparerId  := 'EQUAL' | 'GREATER_THAN' | 'LESS_THAN'

Value       := Number | String
Number      := { Digit };
String      := Quote, Word, Quote;
Word        := { Letter }
Letter      := 'a' | 'b' | 'c' ...;
Digit       := '1' | '2' | '3' ...;
Quote       := '"'

With inspiration from everywhere, that lead me to this structure in code:

public static class QueryGrammar<T>
{
    // We're parsing the query and translating it into an expression in the form
    // of a lambda function taking a parameter of type T as input
    static readonly ParameterExpression Param = Expression.Parameter(typeof(T));
    
    // The only public member
    public static Expression<Func<T, bool>> ParseCondition(string input)
    {
        // Parse a Term (recursively) until the end of the input is reached.
        // Convert the output expression body into a lambda function that can
        // be applied to an object of type T returning a bool (predicate)
        return Term.End()
            .Select(body => Expression.Lambda<Func<T, bool>>(body, Param))
            .Parse(input);
    }
    
    // For escaping a character (such as ")
    static Parser<char> EscapingChar => Parse.Char('\\');
    // Pick the character that was escaped
    static Parser<char> EscapedChar =>
        from _ in EscapingChar
        from c in Parse.AnyChar
        select c;
        
    static Parser<char> QuoteChar => Parse.Char('"');
    static Parser<char> NonQuoteChar =>
        Parse.AnyChar.Except(QuoteChar);
    
    // Pick text in-between double qoutes
    static Parser<string> QuotedText =>
        from open in QuoteChar
        from content in EscapedChar.Or(NonQuoteChar).Many().Text()
        from close in QuoteChar
        select content;
    
    // Create an expression that "calls the getter of a property on a object of type T"
    private static Expression GetProperty(string propName)
    {
        var memInfo = typeof(T).GetMember(propName,
            MemberTypes.Property,
            BindingFlags.Instance | BindingFlags.Public)
            .FirstOrDefault();
            
        if (memInfo == null)
            throw new ParseException($"Property with name '{propName}' not found on type '{typeof(T)}'");
            
        return Expression.MakeMemberAccess(Param, memInfo);
    }
    
    // Match a word without quotes, in order to match a field/property name
    static Parser<Expression> FieldToken =>
        Parse.Letter.AtLeastOnce().Text().Token()
        .Select(name => GetProperty(name));
    // Match a value. Either an integer or a quoted string
    static Parser<Expression> ValueToken =>
        (from strNum in Parse.Number
        select Expression.Constant(int.Parse(strNum)))
        .Or(QuotedText.Select(t => Expression.Constant(t)))
        .Token();
        
    // Common parser for all terms
    static Parser<Expression> Term =>
        EqualTerm
        .Or(GreaterThanTerm)
        .Or(OrTerm)
        .Or(AndTerm);
    
    static Parser<Expression> EqualTerm =>
        (from tuple in Comparer("EQUAL")
         select Expression.Equal(tuple.Field, tuple.Value))
        .Token();
    static Parser<Expression> GreaterThanTerm =>
        (from tuple in Comparer("GREATER_THAN")
         select Expression.GreaterThan(tuple.Field, tuple.Value))
        .Token();
        
    // Generally the comparer terms consist of:
    // COMPARER_NAME + ( + FIELD_NAME + , + VALUE + )
    static Parser<(Expression Field, Expression Value)> Comparer(string comparison) =>
        (from startsWith in Parse.String(comparison).Text().Token()
         from openParen in Parse.Char('(')
         from field in FieldToken
         from comma in Parse.Char(',')
         from value in ValueToken
         from closeParen in Parse.Char(')')
         select (field, value))
        .Token();
        
        
    static Parser<Expression> AndTerm =>
        (from tuple in Combinator("AND")
         select Expression.AndAlso(tuple.Left, tuple.Right))
        .Token();
    static Parser<Expression> OrTerm =>
        (from tuple in Combinator("OR")
         select Expression.OrElse(tuple.Left, tuple.Right))
        .Token();
        
    // Generally combinators consist of:
    // COMBINATOR_NAME + ( + TERM + , + TERM + )
    // A term can be either a comparer of another combinator as seem above
    static Parser<(Expression Left, Expression Right)> Combinator(string combination) =>
        (from startsWith in Parse.String(combination).Text().Token()
         from openParen in Parse.Char('(')
         from lTerm in Term
         from comma in Parse.Char(',')
         from rTerm in Term
         from closeParen in Parse.Char(')')
         select (lTerm, rTerm))
        .Token();
}

You then use it as follows (of course you can remove all the line breaks and spaces from the query):

var expr = QueryGrammar<StoreData>.ParseCondition(@"
    OR(
        AND(
            EQUAL(title, ""Foo""),
            AND(
                GREATER_THAN(views, 50),
                EQUAL(timestamp, 123456789)
            )
        ),
        EQUAL(id, ""123"")
    )");
Console.WriteLine(expr);
var func = expr.Compile();
var result = func(new StoreData
            {
                id = "321",
                title = "Foo",
                views = 51,
                timestamp = 123456789
            });
Console.WriteLine(result);

A working example can be found here: https://dotnetfiddle.net/3STNYm

Now you just need to extend it a bit. E.g. I didn't write the NOT and LESS_THAN terms and you might need to check that whitespace is handled correctly (both inside and outside the string values) as well as other corner cases you can think of (negative numbers, numbers higher than int.MaxValue) and error handling/reporting (do you need to return a proper message if the query is invalid?). Fortunately, it seems fairly easy to write unit tests for this library to check that parsing works as expected.

A little credit is due:

• Parsing to expressions and building recursive patters (by Corey): https://stackoverflow.com/a/51738050/3034273
• Introduction-like article about Sprache (by Nicholas Blumhardt): https://nblumhardt.com/2010/01/building-an-external-dsl-in-c/
• Example with mathematical expressions: https://github.com/sprache/Sprache/blob/develop/samples/LinqyCalculator/ExpressionParser.cs

Final note: in case it's not already obvious to your PO it's probably worth making them aware that this solution is not cheap compared to using some ready-made tools like OData as you suggested. Parser code (even using a library like Sprache) is complicated, difficult to maintain, difficult to reason about (for non-parser experts at least), requires extensive testing and is more likely to leave bugs and vulnerabilities that are hard to find before it's too late, compared to a popular and well-maintained tool. On the other hand it gives you more freedom and possibilities to extend in the future.

Answer 2

I like @Xerillio answer, but here is another approach which might be simpler to maintain as requirements evolve.

So here is how I approach these kinds of problems:

First figure out the grammar, the simpler the better IMHO. Here is what I came up with.

ex := op '(' pr ')'             //expression
pr := id ',' lt | ex (',' ex)*  //parameter (* means zero or more)
op := string                    //operator
id := string                    //id
lt := quoted-string | number    //literal

Then create a parse tree (Parser) based on that grammar, should mirror the grammar as much as possible.

Then walk that parse tree to calculate the result (Calc).

Note: The Parser user Sprache and Calc is pretty straight forward using recursion.

Caveat Emptor, might be buggy...

https://dotnetfiddle.net/Widget/pgsbjb

using System;
using Sprache;
using System.Linq;
using System.Collections.Generic;

namespace dotnet_parser
{
    class Program
    {
        /*
            ex := op '(' pr ')'             //expression
            pr := id ',' lt | ex (',' ex)*  //parameter (* means zero or more)
            op := string                    //operator
            id := string                    //id
            lt := quoted-string | number    //literal
        */

        static void Main(string[] args)
        {
            var ex = Parser.getEx().Parse(@"
                                            OR(
                                                AND(
                                                    EQUAL(title, ""Foo""),
                                                    AND(
                                                        GREATER_THAN(views, 50),
                                                        EQUAL(timestamp, 123456789)
                                                    )
                                                ),
                                                EQUAL(id, ""123"")
                                            )");
            
            var sd =
                new StoreData
                {
                    id = "321",
                    title = "Foo",
                    views = 49,
                    timestamp = 123456789
                };

            var res = Calc.Run(ex, sd);

            Console.WriteLine($"result {res}");
        }

        public class StoreData 
        {
            public string id { get; set; }
            public string title { get; set; }
            public string content { get; set; }
            public int views { get; set; }
            public int timestamp { set; get; }
        }

        public class Calc {
            public static bool Run<T>(Parser.Ex ex, T t) {

                switch(ex.Op) {
                    case "NOT":
                    {
                        if(ex.Pr is Parser.PrEx exPr && exPr.Ex.Length == 1) {
                            return Run(exPr.Ex[0], t);
                        }
                        else {
                            throw new Exception($"invalid parameters to {ex.Op}");
                        }
                    }
                    case "AND":
                    case "OR":
                    {
                        if(ex.Pr is Parser.PrEx exPr && exPr.Ex.Length == 2) {
                            var l = Run(exPr.Ex[0], t);
                            var r = Run(exPr.Ex[1], t);
                            switch(ex.Op) {
                                case "AND": return l && r;
                                case "OR" : return l || r;
                                default:
                                    throw new Exception();
                            }
                        }
                        else {
                            throw new Exception($"invalid parameters to {ex.Op}");
                        }
                    }
                    case "EQUAL":
                    case "GREATER_THAN":
                    case "LESS_THAN":
                    {
                        if(ex.Pr is Parser.PrIdLt exIdLt) {
                            var tt = typeof(T);
                            var p = tt.GetProperty(exIdLt.Id);

                            if(p == null) throw new Exception($"no property {exIdLt.Id} on {tt.Name}");


                            if(p.PropertyType == typeof(string) && exIdLt.Lt is Parser.LtQuotedString ltQuotedString){
                                var pval = p.GetValue(t) as string;
                                switch(ex.Op){
                                    case "EQUAL":
                                        return pval == ltQuotedString.Val;
                                    default:
                                        throw new Exception($"{ex.Op} invalid operator for string");
                                }
                            }
                            else if(p.PropertyType == typeof(int) && exIdLt.Lt is Parser.LtNumber ltNumber){
                                var pval = (int)p.GetValue(t);

                                int lval;
                                if(!int.TryParse(ltNumber.Val, out lval)) throw new Exception($"{ex.Op} {exIdLt.Id} {ltNumber.Val} is not a number");

                                switch(ex.Op){
                                    case "EQUAL"       : return pval == lval;
                                    case "GREATER_THAN": return pval >  lval;
                                    case "LESS_THAN"   : return pval <  lval;
                                    default:
                                        throw new Exception($"{ex.Op} invalid operator for string");
                                }
                            }
                            else {
                                throw new Exception($"{ex.Op} {exIdLt.Id} invalid type");
                            }
                        }
                        else {
                            throw new Exception($"invalid parameters to {ex.Op}");
                        }
                    }
                    default:
                        throw new Exception($"{ex.Op} unknown operator");
                }
            }
        }

        public class Parser {
            public class Ex {
                public string Op { get; set; }
                public Pr Pr { get; set; }
            }

            public interface Pr { }
            public class PrIdLt : Pr { 
                public string Id { get; set; }
                public Lt Lt { get; set; }
            }
            public class PrEx : Pr {
                public Ex[] Ex { get; set; }
            }

            public interface Lt { }
            public class LtQuotedString : Lt { public string Val { get; set; } }
            public class LtNumber       : Lt { public string Val { get; set; } }

            public static Parser<Ex> getEx(){
                return
                    from o in getOp()
                    from p in getPr().Contained(Parse.Char('('), Parse.Char(')')).Token()
                    select new Ex { Op = o, Pr = p };

            }
            public static Parser<Pr> getPr(){
                var a =
                    from i in getId()
                    from c in Parse.Char(',').Token()
                    from l in getLt()
                    select new PrIdLt { Id = i, Lt = l };

                var b =
                    from ex in Parse.Ref(() => getEx())
                    from em in Parse.Char(',').Token().Then(_ => Parse.Ref(() => getEx())).Many()
                    select new PrEx { Ex = em.Prepend(ex).ToArray() };

                return a.Or<Pr>(b);
            }
            public static Parser<string> getOp() => Parse.Letter.Or(Parse.Char('_')).AtLeastOnce().Text().Token();
            public static Parser<string> getId() => Parse.Identifier(Parse.Letter, Parse.LetterOrDigit).Token();
            public static Parser<Lt> getLt(){
                var quoted_string =
                    from open in Parse.Char('"')
                    from value in Parse.CharExcept('"').Many().Text()
                    from close in Parse.Char('"')
                    select value;

                return
                    quoted_string.Select(a => new LtQuotedString { Val = a })
                    .Or<Lt>(Parse.Number.Select(a => new LtNumber(){ Val = a })).Token();
            }
        }
    }
}