Introduction
This is an alternative to the original Tip Dynamically generate a LINQ query with a custom property.
The original post follows the concept of tweaking with the client of of a query to allow dynamic queries. I find that quite intrusive and not re-usable for future use as I commented on the original post.
I outline here how you can re-invent your own Dynamic Linq version. I present some parsing techniques that might be helpful for other simple parser tasks. For "real" parser works, I strongly recommend using a parser generator like Coco/R or like ANTLR.
The functionality:
create from an expression that is given in a string a function that can be used in a LINQ query, e.g.
IEnumerable<MySourceElement> items = ...;
...
string s = GetUserEntry();
...
var pred = SimpleExpression.PredicateParser<MySourceElement>.Parse(s);
var f = pred.Compile();
var query = from e in items where f(e) select e;
...
Using the code
This is a very dense code that shows how you could write your own Dynamic LINQ parser:
- the scanner is from line 11 to line 54
- the code generator is from line 57 to line 108
- the parser from is line 109 to line 149
The implemented features:
- names as properties or fields of the lambda parameter
- double or int numbers
- strings
- nested expressions
- numeric, string, boolean type system with numeric type promotion
- operators ||, &&, ==, !=, <, <=, >=, >, !
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Linq.Expressions;
5 using System.Text.RegularExpressions;
6
7 namespace SimpleExpression
8 {
9 public abstract class PredicateParser
10 {
11 #region scanner
12 private static readonly string _pattern = @"\s*(" + string.Join("|", new string[]
14 {
15
16 string.Join("|", new string[] { "||", "&&", "==", "!=", "<=", ">=" }.Select(e => Regex.Escape(e))),
17 @"""(?:\\.|[^""])*""",
18 @"\d+(?:\.\d+)?",
19 @"\w+",
20 @"\S",
21 }) + @")\s*";
22 private char Ch { get { return string.IsNullOrEmpty(Curr) ? ' ' : Curr[0]; } }
24 private bool Move() { return _tokens.MoveNext(); }
26 private IEnumerator<string> _tokens;
28 protected PredicateParser(string s)
30 {
31 _tokens = Regex.Matches(s, _pattern, RegexOptions.Compiled).Cast<Match>()
32 .Select(m => m.Groups[1].Value).GetEnumerator();
33 Move();
34 }
35 protected bool IsNumber { get { return char.IsNumber(Ch); } }
36 protected bool IsDouble { get { return IsNumber && Curr.Contains('.'); } }
37 protected bool IsString { get { return Ch == '"'; } }
38 protected bool IsIdent { get { char c = Ch; return char.IsLower(c) || char.IsUpper(c) || c == '_'; } }
39 protected void Abort(string msg) { throw new ArgumentException("Error: " + (msg ?? "unknown error")); }
41 protected string Curr { get { return _tokens.Current ?? string.Empty; }}
43 protected string CurrAndNext { get { string s = Curr; if (!Move()) Abort("data expected"); return s; } }
45 protected string CurrOptNext { get { string s = Curr; Move(); return s; } }
47 protected string CurrOpAndNext(params string[] ops)
49 {
50 string s = ops.Contains(Curr) ? Curr : null;
51 if (s != null && !Move()) Abort("data expected");
52 return s;
53 }
54 #endregion
55 }
56 public class PredicateParser<TData>: PredicateParser
57 {
58 #region code generator
59 private static readonly Type _bool = typeof(bool);
60 private static readonly Type[] _prom = new Type[]
61 { typeof(decimal), typeof(double), typeof(float), typeof(ulong), typeof(long), typeof(uint),
62 typeof(int), typeof(ushort), typeof(char), typeof(short), typeof(byte), typeof(sbyte) };
63 private static Expression Coerce(Expression expr, Type type)
65 {
66 return expr.Type == type ? expr : Expression.Convert(expr, type);
67 }
68 private static Expression Coerce(Expression expr, Expression sibling)
70 {
71 if (expr.Type != sibling.Type)
72 {
73 Type maxType = MaxType(expr.Type, sibling.Type);
74 if (maxType != expr.Type) expr = Expression.Convert(expr, maxType);
75 }
76 return expr;
77 }
78 private static Type MaxType(Type a, Type b) { return a==b?a:(_prom.FirstOrDefault(t=>t==a||t==b)??a); }
80 private static readonly Dictionary<string, Func<Expression, Expression, Expression>> _binOp =
84 new Dictionary<string,Func<Expression,Expression,Expression>>()
85 {
86 { "||", (a,b)=>Expression.OrElse(Coerce(a, _bool), Coerce(b, _bool)) },
87 { "&&", (a,b)=>Expression.AndAlso(Coerce(a, _bool), Coerce(b, _bool)) },
88 { "==", (a,b)=>Expression.Equal(Coerce(a,b), Coerce(b,a)) },
89 { "!=", (a,b)=>Expression.NotEqual(Coerce(a,b), Coerce(b,a)) },
90 { "<", (a,b)=>Expression.LessThan(Coerce(a,b), Coerce(b,a)) },
91 { "<=", (a,b)=>Expression.LessThanOrEqual(Coerce(a,b), Coerce(b,a)) },
92 { ">=", (a,b)=>Expression.GreaterThanOrEqual(Coerce(a,b), Coerce(b,a)) },
93 { ">", (a,b)=>Expression.GreaterThan(Coerce(a,b), Coerce(b,a)) },
94 };
95 private static readonly Dictionary<string, Func<Expression, Expression>> _unOp =
96 new Dictionary<string, Func<Expression, Expression>>()
97 {
98 { "!", a=>Expression.Not(Coerce(a, _bool)) },
99 };
100 private static ConstantExpression Const(object v) { return Expression.Constant(v); }
102 private MemberExpression ParameterMember(string s) { return Expression.PropertyOrField(_param, s); }
104 private Expression<Func<TData, bool>> Lambda(Expression expr) { return Expression.Lambda<Func<TData, bool>>(expr, _param); }
106 private readonly ParameterExpression _param = Expression.Parameter(typeof(TData), "_p_");
108 #endregion
109 #region parser
110 private PredicateParser(string s): base(s) { }
112 public static Expression<Func<TData, bool>> Parse(string s) { return new PredicateParser<TData>(s).Parse(); }
114 private Expression<Func<TData, bool>> Parse() { return Lambda(ParseExpression()); }
115 private Expression ParseExpression() { return ParseOr(); }
116 private Expression ParseOr() { return ParseBinary(ParseAnd, "||"); }
117 private Expression ParseAnd() { return ParseBinary(ParseEquality, "&&"); }
118 private Expression ParseEquality() { return ParseBinary(ParseRelation, "==", "!="); }
119 private Expression ParseRelation() { return ParseBinary(ParseUnary, "<", "<=", ">=", ">"); }
120 private Expression ParseUnary() { return CurrOpAndNext("!") != null ? _unOp["!"](ParseUnary())
121 : ParsePrimary(); }
122 private Expression ParseIdent() { return ParameterMember(CurrOptNext); }
123 private Expression ParseString() { return Const(Regex.Replace(CurrOptNext, "^\"(.*)\"$",
124 m => m.Groups[1].Value)); }
125 private Expression ParseNumber() { if (IsDouble) return Const(double.Parse(CurrOptNext));
126 return Const(int.Parse(CurrOptNext)); }
127 private Expression ParsePrimary()
128 {
129 if (IsIdent) return ParseIdent();
130 if (IsString) return ParseString();
131 if (IsNumber) return ParseNumber();
132 return ParseNested();
133 }
134 private Expression ParseNested()
135 {
136 if (CurrAndNext != "(") Abort("(...) expected");
137 Expression expr = ParseExpression();
138 if (CurrOptNext != ")") Abort("')' expected");
139 return expr;
140 }
141 private Expression ParseBinary(Func<Expression> parse, params string[] ops)
143 {
144 Expression expr = parse();
145 string op;
146 while ((op = CurrOpAndNext(ops)) != null) expr = _binOp[op](expr, parse());
147 return expr;
148 }
149 #endregion
150 }
151 }
This program calls the entry point of the parser above and runs various queries employing the calculated expression:
1 static void Main(string[] args)
2 {
3 var items = new List<Element>()
4 {
5 new Element("a", 1000),
6 new Element("b", 900),
7 new Element("c", 800),
8 new Element("d", 700),
9 new Element("e", 600),
10 new Element("x", 500),
11 new Element("y", 400),
12 new Element("z", 300),
13 };
14
15 string s = "Name == \"x\" || Number >= 800";
16 var pred = SimpleExpression.PredicateParser<Element>.Parse(s);
17 Console.WriteLine("User Entry: {0}", s);
18 Console.WriteLine("Expr Tree: {0}", pred.ToString());
19 var f = pred.Compile();
20 Console.WriteLine("### mark affectd items ###");
21 foreach (var item in items)
22 {
23 Console.WriteLine("{2} Name = {0}, Number = {1}", item.Name, item.Number, f(item) ? "x" : " ");
24 }
25 Console.WriteLine("### where-select ###");
26 var q = from e in items where f(e) select e;
27 foreach (var item in q)
28 {
29 Console.WriteLine(" Name = {0}, Number = {1}", item.Name, item.Number);
30 }
31 }
The output is:
User Entry: Name == "x" || Number >= 800
Expr Tree: _p_ => ((_p_.Name == "x") OrElse (Convert(_p_.Number) >= 800))
### mark affectd items ###
x Name = a, Number = 1000
x Name = b, Number = 900
x Name = c, Number = 800
Name = d, Number = 700
Name = e, Number = 600
x Name = x, Number = 500
Name = y, Number = 400
Name = z, Number = 300
### where-select ###
Name = a, Number = 1000
Name = b, Number = 900
Name = c, Number = 800
Name = x, Number = 500
Points of Interest
As mentioned, check out the available parser generators to do real work with parsers.
LINQ Expression Tree
Dynamic LINQ
To extend the parser: You may easily add more to the expressions, especially new operators is a simple thing:
- to add
+
and -
binary operators, add them to the _binOp
dictionary (similar to ==
, e.g. , ("+":
Expression.Add(...)
, "-":
Expression.Subtract(...)
) create ParseSum()
as a copy of ParseRelation
, pass "+", "-"
as ops, pass ParseSum
to ParseRelation
(in place of the ParseUnary
), pass ParseUnary
to ParseSum
. That's it. - likewise for
"*", "/", "%"
: make ParseMul
as copy of the above mentioned ParseSum
, pass the right ParseXXX
actions, add the respective Expression factories to the _binOps
dictionary. Done. - An unary
"-"
is to be added in the _unOps
dictionary (no coercion needed). The parsing is done in the ParseUnary()
function, e.g.
...
93 { ">", (a,b)=>Expression.GreaterThan(Coerce(a,b), Coerce(b,a)) },
94 { "+", (a,b)=>Expression.Add(Coerce(a,b), Coerce(b,a)) },
95 { "-", (a,b)=>Expression.Subtract(Coerce(a,b), Coerce(b,a)) },
96 { "*", (a,b)=>Expression.Multiply(Coerce(a,b), Coerce(b,a)) },
97 { "/", (a,b)=>Expression.Divide(Coerce(a,b), Coerce(b,a)) },
98 { "%", (a,b)=>Expression.Modulo(Coerce(a,b), Coerce(b,a)) },
99 };
100 private static readonly Dictionary<string, Func<Expression, Expression>> _unOp =
101 new Dictionary<string, Func<Expression, Expression>>()
102 {
103 { "!", a=>Expression.Not(Coerce(a, _bool)) },
104 { "-", a=>Expression.Negate(a) },
105 };
...
119 private Expression ParseRelation() { return ParseBinary(ParseSum, "<", "<=", ">=", ">"); }
120 private Expression ParseSum() { return ParseBinary(ParseMul, "+", "-"); }
121 private Expression ParseMul() { return ParseBinary(ParseUnary, "*", "/", "%"); }
122 private Expression ParseUnary()
123 {
124 if (CurrOpAndNext("!") != null) return _unOp["!"](ParseUnary());
125 if (CurrOpAndNext("-") != null) return _unOp["-"](ParseUnary());
126 return ParsePrimary();
127 }
If you like this alternative to the tip, please rate it ;-)
Any feedback is very much appreciated.
Please note: this is meant as alternative to the given tip. This alternative does not require the data provider to use special kind of properties or fields. For real work on this, checkout the available Dynamic LINQ implementaiton.
Have fun!
Andi
History
V1.0 | 2012-03-28 | First version
|
V1.1 | 2012-03-29 | fix typo on line 107, simplified ParsePrimary, fixed ParseNumber to correctly distinguish between int and double, some minor code formatting adjustments, add sources download link, update tags (.NET4)
|
V1.2 | 2012-03-29 | added sample code for showing how easily extending the expression parser early adopter of the brand new code rendering feature:
<pre ... countlines="true" countstart="93">... (thanks Chris Maunder[^] for adding this feature[^] so quickly!)
|
V1.3 | 2012-04-06 | Fix Regex for string (properly handles embedded double quotes) and number (decimal part is optional)
|