Tuesday, April 10, 2007 3:14 PM
bart
The IQueryable tales - LINQ to LDAP - Part 4: Parsing and executing queries
Introduction
Welcome back to the LINQ-to-LDAP series. So far, we've been discussing:
In the previous post, we entered the domain of implementing a custom query provider for LINQ. More specifically, we did discuss the need for entities and came up with a class definition that maps an object from the underlying data source, which is Active Directory in our case. Such an entity has the following shape:
An entity type for user objects in Active Directory -
Copy Code 1 [DirectorySchema("user")]
2 public class User
3 {
4 [DirectoryAttribute("givenName")]
5 public string FirstName { get; set; }
6
7 [DirectoryAttribute("sn")]
8 public string LastName { get; set; }
9
10 [DirectoryAttribute("physicalDeliveryOfficeName")]
11 public string Office { get; set; }
12 }
Today we (finally) take it another stpe forward, focusing on the LINQ-to-LDAP translation when writing queries like:
A LINQ query against Active Directory -
Copy Code1 DirectorySource<User> users = new DirectorySource<User>(...);
2 var res = from usr in users
3 where usr.Office == "Building 10 - 1.25"
4 select usr.FirstName + " " + usr.LastName;
In technical terms, we'll make a first implementation of IQueryable<T>: DirectorySource<T>.
Back to the attributes
In the previous post, two custom attributes were introduced to perform the mapping between entities and the underlying directory objects. Before moving on, I want to extend those a little more to support more complex data types. For instance, attributes like pwdLastSet are retrieved by DirectoryEntry's Properties collections as a COM-object. We could try to do a conversion to the more convenient DateTime BCL type ourselves, but instead a COM library called "Active DS Type Library" proves handy since it exposes properties in the right .NET type. To use this library, add a reference to the Active DS Type Library via Add Reference..., tab COM.
When you take a look inside the library using the Object Browser, you'll find a series of interfaces starting with IADs. One of these is IADsUser:
As you can see, the PasswordLastChanges property is of type System.DateType, allowing us to use it right away without having to mess around with COM-to-.NET conversions for complex types. You might wonder why we don't just use this class for all our entity stuff. The answer is that we want to provide the end-users with the maximum level of flexibility. Therefore, we'll both support "LDAP attribute names" as well as property names from the IADs* interfaces. So, how can we reflect these feature requests in the custom attribute definitions? The answer is below.
Note: In future posts, we'll talk even more about entities, when we want to support updates too. In order to make this possible, we'll have to track changes to retrieved objects in order to feed these back when making an Update call to the DirectorySource<T> data source. However, some properties don't support updating because of their read-only nature (PasswordLastChanged is one like this). Therefore, the entity type will need to reflect this.
Mapping custom attributes for entity objects -
Copy Code 1 /// <summary>
2 /// Specifies the directory schema to query.
3 /// </summary>
4 [AttributeUsage(AttributeTargets.Class, AllowMultiple = false)]
5 public class DirectorySchemaAttribute : Attribute
6 {
7 private string schema;
8 private Type helper;
9
10 /// <summary>
11 /// Creates a new schema indicator attribute.
12 /// </summary>
13 /// <param name="schema">Name of the schema to query for.</param>
14 public DirectorySchemaAttribute(string schema)
15 {
16 this.schema = schema;
17 }
18
19 /// <summary>
20 /// Creates a new schema indicator attribute.
21 /// </summary>
22 /// <param name="schema">Name of the schema to query for.</param>
23 /// <param name="activeDsHelperType">Helper type for Active DS object properties.</param>
24 public DirectorySchemaAttribute(string schema, Type activeDsHelperType)
25 {
26 this.schema = schema;
27 this.helper = activeDsHelperType;
28 }
29
30 /// <summary>
31 /// Name of the schema to query for.
32 /// </summary>
33 public string Schema
34 {
35 get { return schema; }
36 set { schema = value; }
37 }
38
39 /// <summary>
40 /// Helper type for Active DS object properties.
41 /// </summary>
42 public Type ActiveDsHelperType
43 {
44 get { return helper; }
45 set { helper = value; }
46 }
47 }
48
49 /// <summary>
50 /// Specifies the underlying attribute to query for in the directory.
51 /// </summary>
52 [AttributeUsage(AttributeTargets.Property, AllowMultiple = false)]
53 public class DirectoryAttributeAttribute : Attribute
54 {
55 private string attribute;
56 private DirectoryAttributeType type;
57
58 /// <summary>
59 /// Creates a new attribute binding attribute for a entity class field or property.
60 /// </summary>
61 /// <param name="attribute">Name of the attribute to query for.</param>
62 public DirectoryAttributeAttribute(string attribute)
63 {
64 this.attribute = attribute;
65 this.type = DirectoryAttributeType.Ldap;
66 }
67
68 /// <summary>
69 /// Creates a new attribute binding attribute for a entity class field or property.
70 /// </summary>
71 /// <param name="attribute">Name of the attribute to query for.</param>
72 /// <param name="type">Type of the underlying query source to get the attribute from.</param>
73 public DirectoryAttributeAttribute(string attribute, DirectoryAttributeType type)
74 {
75 this.attribute = attribute;
76 this.type = type;
77 }
78
79 /// <summary>
80 /// Name of the attribute to query for.
81 /// </summary>
82 public string Attribute
83 {
84 get { return attribute; }
85 set { attribute = value; }
86 }
87
88 /// <summary>
89 /// Type of the underlying query source to get the attribute from.
90 /// </summary>
91 public DirectoryAttributeType Type
92 {
93 get { return type; }
94 set { type = value; }
95 }
96 }
97
98 /// <summary>
99 /// Type of the query source to perform queries with.
100 /// </summary>
101 public enum DirectoryAttributeType
102 {
103 /// <summary>
104 /// Default value. Uses the Properties collection of DirectoryEntry to get data from.
105 /// </summary>
106 Ldap,
107
108 /// <summary>
109 /// Uses Active DS Helper IADs* objects to get data from.
110 /// </summary>
111 ActiveDs
112 }
The custom attribute definition from above allows us to write things like this:
An entity with complex mapping -
Copy Code 1 [DirectorySchema("user", typeof(IADsUser))]
2 public class User
3 {
4 [DirectoryAttribute("givenName")]
5 public string FirstName { get; set; }
6
7 [DirectoryAttribute("sn")]
8 public string LastName { get; set; }
9
10 [DirectoryAttribute("physicalDeliveryOfficeName")]
11 public string Office { get; set; }
12
13 [DirectoryAttribute("PasswordLastChanged", DirectoryAttributeType.ActiveDs)]
14 public DateTime PasswordLastSet { get; set; }
15 }
In this sample, a property has been defined (line 13-14) that relies on the ActiveDs property name instead of the LDAP property name, which has been indicated using DirectoryAttributeType.ActiveDs. Notice that the PasswordLastSet property has both a getter and setter accessor defined although it is read-only in the underlying IADsUser type definition; the setter is required for our framework to assign the retrieved value to it. In order for the framework to find the corresponding IADs* type for the entity object, an additional parameter has been added to the DirectorySchema attribute in line 1 (typeof(IADsUser)). This set of information will be enough to compose the query and get the values back via the desired "channel".
Furthermore, we'll also allow entity types to omit the DirectoryAttribute decorations if no renaming has to happen:
Copy Code1 [DirectorySchema("user")]
2 public class User
3 {
4 public string GivenName { get; set; }
5 public string Sn { get; set; }
6 }
In here, the GivenName and Sn properties have the same name as their LDAP attribute name equivalent (which is case-insensitive by the way), so the system can figure out the mapping on its own. We'll support such an automatic mapping only for LDAP attribute names, not for IADs* property names.
The skeleton
On to the real work now; the DirectorySource<T> implementation. Let's start by revisiting our IQueryable<T> skeleton implementation. Since we won't support sorting right now, we won't derive from IOrderedQueryable<T>. An implementation of sorting is possible though, using a IQueryable<T>-to-IEnumerable<T> translation, followed by LINQ-to-Objects sorting, when yielding the results back. This discussion would lead us too far, so let's move on with the basics for now:
Basic skeleton of IQueryable<T> implementation -
Copy Code 1 /// <summary>
2 /// Represents an LDAP data source. Allows for querying the LDAP data source via LINQ.
3 /// </summary>
4 /// <typeparam name="T">Entity type in the underlying source.</typeparam>
5 public class DirectorySource<T> : IQueryable<T>
6 {
7 /// <summary>
8 /// Constructs an IQueryable object that can evaluate the query represented by the specified expression tree.
9 /// </summary>
10 /// <param name="expression">Expression representing the LDAP query.</param>
11 /// <returns>IQueryable object that can evaluate the query represented by the specified expression tree.</returns>
12 public IQueryable CreateQuery(Expression expression)
13 {
14 return CreateQuery<T>(expression);
15 }
16
17 /// <summary>
18 /// Constructs an IQueryable object that can evaluate the query represented by the specified expression tree.
19 /// </summary>
20 /// <param name="expression">Expression representing the LDAP query.</param>
21 /// <typeparam name="TElement">The type of the elements of the IQueryable that is returned.</typeparam>
22 /// <returns>IQueryable object that can evaluate the query represented by the specified expression tree.</returns>
23 public IQueryable<TElement> CreateQuery<TElement>(Expression expression)
24 {
25 //
26 // TODO
27 //
28 }
29
30 #region Execution (not implemented)
31
32 public object Execute(Expression expression)
33 {
34 throw new NotImplementedException();
35 }
36
37 public TResult Execute<TResult>(Expression expression)
38 {
39 throw new NotImplementedException();
40 }
41
42 #endregion
43
44 #region Enumeration
45
46 IEnumerator IEnumerable.GetEnumerator()
47 {
48 return GetEnumerator();
49 }
50
51 public IEnumerator<T> GetEnumerator()
52 {
53 //
54 // TODO
55 //
56 }
57
58 #endregion
59
60 public Type ElementType
61 {
62 get { return typeof(T); }
63 }
64
65 public Expression Expression
66 {
67 get { return Expression.Constant(this); }
68 }
69 }
This basic skeleton is based on the one shown in Part 2 of this series.
A first concern is the constructor, which should collect enough information to be able sending the query to AD. In order to allow a maximum level of flexibility, we're going to support passing in a DirectoryEntry representing the node to start the search from (remember that directory services implementations are tree based, in which distinguished names - aka DNs - are put together by various parts representing domain names, OUs, etc) together with a SearchScope. The latter argument is required to allows users to specify how the search has to be performed; it can be a base-level search (in which only the current node is searched, so at maximum one result - the node itself - can be returned; maybe not that useful) or a subtree search (the whole subtree below the current node) or a "one level" deep search (only searching the childs of the current node). The constructor is defined below:
Constructor for DirectorySource<T> -
Copy Code 1 /// <summary>
2 /// Creates a new data source instance for the given directory search root and with a given search scope.
3 /// </summary>
4 /// <param name="searchRoot">Root location in the directory to start all searches from.</param>
5 /// <param name="searchScope">Search scope for all queries performed through this data source.</param>
6 public DirectorySource(DirectoryEntry searchRoot, SearchScope searchScope)
7 {
8 this.searchRoot = searchRoot;
9 this.searchScope = searchScope;
10 }
This requires two member attributes:
Private members related to the constructor's parameterization -
Copy Code1 #region Directory information
2
3 private DirectoryEntry searchRoot;
4 private SearchScope searchScope;
5
6 #endregion
As another part of the "skeleton", let's add a property to support logging, in a similar fashion as the LINQ-to-SQL API does:
Logger support -
Copy Code 1 private TextWriter logger;
2
3 /// <summary>
4 /// Used to configure a logger to print diagnostic information about the query performed.
5 /// </summary>
6 public TextWriter Log
7 {
8 get { return logger; }
9 set { logger = value; }
10 }
Implementing the parsing logic
Next, we move on to the CreateQuery<TElement> implementation itself. In part 2 of this series, we've shown the rationale behind CreateQuery and how several query-related operations result in a chain of CreateQuery calls to be made. The signature of CreateQuery is shown below as a quick refresh:
// Summary:
// Constructs an System.Linq.IQueryable<T> object that can evaluate the query
// represented by the specified expression tree.
//
// Parameters:
// expression:
// The System.Linq.Expressions.Expression representing the query to be encompassed.
//
// Returns:
// An System.Linq.IQueryable<T> that can evaluate the query represented by the
// specified expression tree.
IQueryable<TElement> CreateQuery<TElement>(Expression expression);
This method is part of IQueryable<T> and transforms it into a new IQueryable<TElement>. For example, when doing filtering with a Where clause, T and TElement will be the same because of the Queryable.Where's signature:
//
// Summary:
// Filters a sequence of values based on a predicate.
//
// Parameters:
// predicate:
// An System.Linq.Expressions.Expression<TDelegate> that represents a function
// that takes a value of type TSource and returns a System.Boolean to use to
// test each element.
//
// source:
// A System.Linq.IQueryable<T> to filter.
//
// Returns:
// An System.Linq.IQueryable<T> that contains elements from the input sequence
// which satisfy the condition specified by predicate.
public static IQueryable<TSource> Where<TSource>(this IQueryable<TSource> source, Expression<Func<TSource, bool>> predicate);
However, when doing a projection, T and TElement will differ, as illustrated below by inspection of the Select method:
//
// Summary:
// Projects each element of a sequence into a new form.
//
// Parameters:
// source:
// A sequence of values to invoke a selector function on.
//
// selector:
// An System.Linq.Expressions.Expression<TDelegate> that represents a generic
// function to apply to each element.
//
// Returns:
// An System.Linq.IQueryable<T> whose elements are the result of invoking a
// selector function on each element of source.
public static IQueryable<TResult> Select<TSource, TResult>(this IQueryable<TSource> source, Expression<Func<TSource, TResult>> selector);
During the chain of CreateQuery calls we need to gather enough information to carry out the query when asked to do so, in the GetEnumerator method. Each time CreateQuery is called, we'll create a new instance of the DirectorySource<TElement> class that will gather additional information about the query. Enough theory, let's introduce a few private class members that carry query information:
Query information members -
Copy Code 1 #region Query information
2
3 private string query;
4
5 #endregion
6
7 #region Projection information
8
9 private HashSet<string> properties = new HashSet<string>();
10 private Delegate project;
11
12 #endregion
13
14 private Type originalType = typeof(T);
The query member will capture the LDAP filter expression that needs to be sent to the AD server to perform the query. To optimize the query, we'll collect all of the AD object attributes that will make up the propertiesToLoad parameter to the DirectorySearcher type, in the properties set. Furthermore, a delegate to dynamically compiled code for the projection is kept in project and finally we keep track of the original type of the query objects, as we'll discuss later. We'll start with the CreateQuery method definition now:
CreateQuery implementation -
Copy Code 1 /// <summary>
2 /// Constructs an IQueryable object that can evaluate the query represented by the specified expression tree.
3 /// </summary>
4 /// <param name="expression">Expression representing the LDAP query.</param>
5 /// <typeparam name="TElement">The type of the elements of the IQueryable that is returned.</typeparam>
6 /// <returns>IQueryable object that can evaluate the query represented by the specified expression tree.</returns>
7 public IQueryable<TElement> CreateQuery<TElement>(Expression expression)
8 {
9 //
10 // Create a new queryable object based on the current one. A copy is needed to guarantee uniqueness across multiple queries.
11 //
12 DirectorySource<TElement> d = new DirectorySource<TElement>(searchRoot, searchScope);
13 d.query = query;
14 d.project = project;
15 d.properties = properties;
16 d.originalType = originalType;
17 d.logger = logger;
18
19 //
20 // We expect a method call expression for the chain of LINQ query operator method calls.
21 //
22 MethodCallExpression call = expression as MethodCallExpression;
23 if (call != null)
24 {
25 //
26 // First parameter to the method call represents the (unary) lambda in LINQ style.
27 // E.g. (user => user.Name == "Bart") for a Where clause
28 // (user => new { user.Name }) for a Select clause
29 //
30 switch (call.Method.Name)
31 {
32 //
33 // Builds the query LDAP expression.
34 //
35 case "Where":
36 d.BuildQuery(((UnaryExpression)call.Arguments[1]).Operand as LambdaExpression);
37 break;
38 //
39 // Builds the projection and filters the required properties.
40 //
41 case "Select":
42 d.BuildProjection(((UnaryExpression)call.Arguments[1]).Operand as LambdaExpression);
43 break;
44 }
45 }
46
47 return d;
48 }
A quick analysis:
- On lines 12 to 17, we create a new instance of DirectorySource for the TElement "output".
- As discussed in Part 2, all of the CreateQuery calls originate from the Queryable.* methods that add themselves as method call expressions to the expression tree. On line 22 we obtain that call expression.
- Next, we switch on the method call being made, which we expect to be either "Where" or "Select" for basic queries. If you want to provide some way to support sorting, you could also capture method calls to OrderBy, ThenBy, OrderByDescending and ThenByDescending. Similarly, you could intercept all method call expressions for all of the Queryable-methods. Finally, calls are made to BuildQuery or BuildProjection on the newly created object, as explained below.
Translating filters to LDAP query expressions
Now, let's move our focus on the query parsing itself, i.e. the Select case. The BuildQuery method takes care of this:
BuildQuery method -
Copy Code 1 /// <summary>
2 /// Helper method to build the LDAP query.
3 /// </summary>
4 /// <param name="q">Lambda expression to be translated to LDAP.</param>
5 private void BuildQuery(LambdaExpression q)
6 {
7 StringBuilder sb = new StringBuilder();
8
9 //
10 // Recursive tree traversal to build the LDAP query (prefix notation).
11 //
12 ParseQuery(q.Body, sb);
13
14 query = sb.ToString();
15 }
This method prepares an "accumulator" object in the form of a string builder. The ParseQuery method will build the query recursively, spitting its output in the StringBuilder instance, and the result is finally kept in the query private member of the object, ready for comsumption at a later stage when GetEnumerator is called (see further). Here's ParseQuery:
Recursive query parsing -
Copy Code 1 /// <summary>
2 /// Recursive helper method for query parsing based on the given expression tree.
3 /// </summary>
4 /// <param name="e">Expression tree to be translated to LDAP.</param>
5 /// <param name="sb">Accummulative query string used in recursion.</param>
6 private void ParseQuery(Expression e, StringBuilder sb)
7 {
8 sb.Append("(");
9 //
10 // Support for boolean operators & and |. Support for "raw" conditions (like equality).
11 //
12 if (e is BinaryExpression)
13 {
14 BinaryExpression c = e as BinaryExpression;
15 switch (c.NodeType)
16 {
17 case ExpressionType.AndAlso:
18 sb.Append("&");
19 ParseQuery(c.Left, sb);
20 ParseQuery(c.Right, sb);
21 break;
22 case ExpressionType.OrElse:
23 sb.Append("|");
24 ParseQuery(c.Left, sb);
25 ParseQuery(c.Right, sb);
26 break;
27 default: //E.g. Equal, NotEqual, GreaterThan
28 sb.Append(GetCondition(c));
29 break;
30 }
31 }
32 //
33 // Support for boolean negation.
34 //
35 else if (e is UnaryExpression)
36 {
37 UnaryExpression c = e as UnaryExpression;
38 if (c.NodeType == ExpressionType.Not)
39 {
40 sb.Append("!");
41 ParseQuery(c.Operand, sb);
42 }
43 else
44 throw new NotSupportedException("Unsupported query operator detected: " + c.NodeType);
45 }
46 //
47 // Support for string operations.
48 //
49 else if (e is MethodCallExpression)
50 {
51 MethodCallExpression m = e as MethodCallExpression;
52 MemberExpression o = (m.Object as MemberExpression);
53 if (m.Method.DeclaringType == typeof(string))
54 {
55 switch (m.Method.Name)
56 {
57 case "Contains":
58 {
59 ConstantExpression c = m.Arguments[0] as ConstantExpression;
60 sb.AppendFormat("{0}=*{1}*", GetFieldName(o.Member), c.Value);
61 break;
62 }
63 case "StartsWith":
64 {
65 ConstantExpression c = m.Arguments[0] as ConstantExpression;
66 sb.AppendFormat("{0}={1}*", GetFieldName(o.Member), c.Value);
67 break;
68 }
69 case "EndsWith":
70 {
71 ConstantExpression c =