The Application
This is a pet project I have created in order to better understand the inner working on LINQ. It basically exposes a LINQ query interface for Google Image Search. The reason for selecting Image Search over the more popular Web Search is because Image Search is more "structured". i.e., you can search images based on its Size, Color or File Format.
Since there is not much documentation of "LINQ" as yet, most of the implementation is based on examining DLINQ assembly with "Reflector". And needless to say, the solution file is created with Beta version of Visual C# Express (Orcas), and there may be changes in the final release of the product.
For example, the application is capable of executing the following LINQ query:
var test = from img in ImageSearch.Instance
where (img.RelatesTo("SQL")
|| img.RelatesTo("Windows"))
&& img.RelatesTo("Microsoft")
&& !img.RelatesTo("2005")
&& img.Size == ImageSize.Small
&& img.Format == ImageFormat.GIF
&& img.Domain == "www.microsoft.com"
orderby img.Rank
select img
A list of Image objects that match the search conditions will be returned and can then be iterated through via foreach statement. In this case, the search condition is: Small GIF format images that must relate to "Microsoft", and relate to either "SQL" or "Windows", but not relate to "2005", inside "www.microsoft.com" domain.
And here is the definition of Image class:
namespace MChen.Linq.Google
{
public enum ImageFormat
{
Any, JPG, PNG, GIF
}
public enum ImageSize
{
Any, Large, Medium, Small
}
public enum ImageColor
{
Any, BlackWhite, Greyscale, Color
}
public class Image
{
public int Rank { get; internal set; }
public Uri Url { get; internal set; }
public string Domain { get; internal set; }
public string Description { get; internal set; }
public ImageFormat Format { get; internal set; }
public ImageSize Size { get; internal set; }
public ImageColor Color { get; internal set; }
public int Width { get; internal set; }
public int Height { get; internal set; }
public int FileSize { get; internal set; }
public string ThumbnailURL { get; internal set; }
public int ThumbnailWidth { get; internal set; }
public int ThumbnailHeight { get; internal set; }
}
}
However, not every field of the Image class can be used as a query condition. The functionality of the query is limited by the search capacity available on Google. As an example, you CAN'T search images of a specific Width or Height, nor can you sort the result by FileSize. If you try any of these queries, it's likely that you will get a "Not Supported" exception.
Google doesn't expose any API for its Image search (or at least I wasn't able to find any), so the Search function is implemented via sending a HTTP request and then parsing the result with "Regular Expression". Since LINQ is the focus of this exercise, I will not get into the details of request and extract results from Google. You can look into the source code if interested.
IQueryable Chain and Expression Tree
At the heart of LINQ is the concept of Expression Tree, as well as the IQueryable interface. IQueryable is a special interface which the compiler has intimate knowledge of. When the compiler sees that a class instance that implements IQueryable is used in the from clause of a LINQ query, it automatically converts each part of the rest of the query into an expression tree (Had the object only implemented IEnumerable, the code generated would have been quite different, much simply, in fact). Familiar to those who have studied Compiler theory, an expression tree is essentially a data structure that represents a piece of source code, in this case the LINQ query. A compiler or interpreter can then traverse the expression tree to produce the actual machine instructions or simply interpret and execute the expressions. As a quick example, statement "x + 3" can be translated into a BinaryExpression, whose operator is Add, and the two operands are a variable "x" and a constant value "3".
There are two reasons why Expression tree is used as a intermediate data structure: first, it isolates the translation of source code and underlying machine code generation. In the "x + 3" example, the same BinaryExpression can then be used to produce Intel X86, MSIL or JVM instructions. a second reason is that many optimization techniques are much easier to implement with expression tree. For example, if the compiler finds two expression trees in the same code snippet with the same structure, it will create a temp variable to hold the result of the expression tree, and reuse it in both places.
In our sample LINQ query above, two expression trees are generated to represent the Where and the Order By portion of the query. Another expression tree should also have been generated to represent Select, but since we are not doing much in Select, the compiler is smart enough to optimize that away. Had we put a projection operator there, a Select expression tree would be present:
The query is then translated into:
Expression<...> whereClause = ...;
Expression<...> orderByClause = ...;
IQueryable<Image> whereResult
= ImageSearch.Instance.CreateQuery(whereClause);
IQueryable<Image> orderByResult
= whereResult.CreateQuery(orderByClause);
As we can see, the compiler chains the two IQueryable together with CreateQuery function call. The first call to CreateQuery of ImageSearch.Instance (a singleton class that implements IQueryable<Image>) with whereClause expression yields yet another IQueryable<Image>. The orderByClause expression is then passed to the returned interface, a third IQueryable<Image> is returned and used as the final result of the entire LINQ query. As we shall see shortly, this chained IQueryable structure ensures the query conditions defined in the prior query clauses (Where) get passed on to the later clauses.
Anatomy of IQueryable
IQueryable<T> interface defines three methods (each has one generic and one non-generic version). These can be categorized into three purposes:
IEnumerable.GetEnumerator: IQueryable inherits from IEnumerable. In the last section, we have seen that IQueryables are chained together and the last in the chain is returned as the result of the query. It's likely that the client will then intend to iterate through the query result with foreach. In order to accomplish this, at least the last IQueryable object in the chain must implement the GetEnumerator method to return a valid IEnumerator to iterate through the query result. On the other hand, for these IQueryable classes that will never be used as the last in the chain, it's not necessary to implement this. Execute method: This method is called when the result for the query is scalar (For example, Count, Sum, etc). Since our Google Image search doesn't support any of the scalar queries, we simply throw an exception in the implementation of this method. CreateQuery method: For queries that return a list of results, this is where all the magic happens. This method traverses the expression tree and produces the final executable. In the case of DLINQ, this would be the SQL statement. And for our Google Image LINQ, this is the actual URL we will send to request for search result. It then returns an IQueryable object that encapsulates this "executable" information. If that's the final link in the chain, the "executable" will actually be executed when the client iterates through the result (go back to GetEnumerator); if there are further links down the chain, this IQueryable will then incorporate its own expression tree information into the "executable" and pass it on.
Another member of IQueryable worth noting is the Expression property. This property basically asks the IQueryable to wrap itself as an expression, the LINQ framework can then put this expression into the expression tree and pass it along up the chain. A simple and standard implementation of the property is to wrap itself into a ConstantExpression:
public System.Linq.Expressions.Expression Expression
{
get { return Expression.Constant(this); }
}
If you check the printout for the expression tree, this ConstantExpression is located at the first parameter of the root node.
Implement IQueryable.CreateQuery
A Google Image search request can be summarized by the following structure, which is a direct mapping of Advanced Image search web page on Google:
internal class ImageQueryInfo
{
public List<string> AllWords = new List<string>();
public List<string> OrWords = new List<string>();
public List<string> NotWords = new List<string>();
public ImageSize Size { get; set; }
public ImageFormat Format { get; set; }
public ImageColor Color { get; set; }
public string Domain { get; set; }
}
The task of the CreateQuery method is simply to translate the expression tree passed in into an equivalent ImageQueryInfo object. This is accomplished by recursively traversing the expression tree, processing the nodes one by one and filling the relevant information into ImageQueryInfo object:
public ImageQueryInfo BuildQuery(Expression exp)
{
ImageQueryInfo qinfo = new ImageQueryInfo();
return Visit(exp, qinfo);
}
private ImageQueryInfo Visit(Expression node, ImageQueryInfo qinfo)
{
switch (node.NodeType)
{
case ExpressionType.AndAlso:
return VisitAnd((BinaryExpression)node, qinfo);
case ExpressionType.OrElse:
return VisitOr((BinaryExpression)node, qinfo);
case ExpressionType.Equal:
return VisitEquals((BinaryExpression)node, qinfo);
case ExpressionType.Call:
return VisitMethodCall(
(MethodCallExpression)node, qinfo, false, false
);
case ExpressionType.Lambda:
return VisitLambda((LambdaExpression)node, qinfo);
case ExpressionType.Not:
return VisitNot((UnaryExpression)node, qinfo);
}
}
private ImageQueryInfo VisitAnd(BinaryExpression node, ImageQueryInfo qinfo)
{
if (node.NodeType != ExpressionType.AndAlso)
throw new ArgumentException("Argument is not AND.", "node");
qinfo = Visit(node.Left, qinfo);
qinfo = Visit(node.Right, qinfo);
return qinfo;
}
When processing the leaf nodes of the expression tree, we can be very concrete in dealing with the specifics. For example, since we handle only one method call "RelatesTo", we can check the method name and generate an exception when it can't be handled:
Type declaringType = node.Method.DeclaringType;
if (declaringType == typeof(Image))
{
if (node.Method.Name == "RelatesTo")
{
if (node.Arguments.Count != 1 ||
node.Arguments[0].NodeType != ExpressionType.Constant)
throw new ArgumentException
( "Only constant search terms are supported.");
ConstantExpression cont =
node.Arguments[0] as ConstantExpression;
string term = cont.Value.ToString();
if (forceNot) qinfo.NotWords.Add(term);
else if (forceOr) qinfo.OrWords.Add(term);
else qinfo.AllWords.Add(term);
}
else
{
throw new ArgumentException(
string.Format(
"Method {0} is not supported.", node.Method.Name));
}
}
else
{
throw new ArgumentException(
string.Format("Method {0} is not supported.", node.Method.Name));
}
return qinfo;
Implement IQueryable.GetEnumerator
Once we have the ImageQueryInfo object that contains all the query conditions, all we need to do is to send the right request, fetch the response and extract image search results. This logic is implemented in IQueryable.GetEnumerator method. With the help of yield statement, the implementation is quite straight forward (RequestForPage method constructs the request URL, fetches the response and then parses it with a regular expression):
public IEnumerator<T> GetEnumerator()
{
int cnt = 1;
while (true)
{
IList<T> batch = RequestForPage(cnt);
foreach (var img in batch)
{
cnt++;
yield return img;
}
if (batch.Count == 0) break;
}
}
LambdaExpression.Compile
One thing that makes LambdaExpression stands out from other expression types is its Compile method. As the name suggests, a call to Compile converts the data representation of the expression tree into actually executable code, represented as a delegate. In the following code, for example:
Expression<Func<int, int>> expr = a => a + 3;
Func<int, int> func = expr.Compile();
Console.WriteLine(func(5));
Expression (a+3) is actually compiled at runtime, a delegate to the compiled method is returned as Func<int, int>. Then we can call the delegate to "execute the expression".
But what doesn't this have to do with our LINQ implementation? In the next section, we will see that LambdaExpression.Compile gives us a quick and easy way to support some query constructs that we otherwise would spend sleepless nights to implement.
Query Parametization and Projection
Our Google Image query is simple and functional. But it doesn't really get us far enough. For example, it couldn't handle a parameterized query such as:
string param = ...;
var test = from img in Google.Images
where img.RelatesTo("microsoft")
&& img.Format == (ImageFormat)
Enum.Parse(typeof(ImageFormat), param)
&& img.Domain == "www.microsoft.com"
orderby img.Rank
select img;
Notice the Format part of the query result is passed as a variable and must be evaluated with Enum.Parse. Ordinarily this wouldn't be much of an issue as it's no more than just a regular runtime method call. But in LINQ land, the compiler DOES NOT generate the MSIL for the method call, instead, the method call is converted as part of the expression tree, just as the rest part of the query.
This poses a serious problem for our LINQ implementation because now we're forced to handle practically all .NET language constructs: you might see arithmetic operations, method call and even object creation in the expression tree and you must handle ALL of them to make the query language complete. We're almost writing the second half of a C# compiler! (the first, syntax parsing is already done by the real C# compiler as we have an expression tree on hand).
LambdaExpression.Compile comes to the rescue. When we don't plan to handle the expression in our query, we can always convert it into a LambdaExpression and ask .NET to compile and execute it on our behalf. When we handle the equals operator in our LINQ implementation, we always expect one side of the operator be a direct member access on Image class, the other side be a constant expression, or now, something that can be evaluated to a constant expression before the query can be executed. This can be achieved with the following method:
internal static ConstantExpression
ProduceConstantExpression<X>(Expression exp)
{
try
{
return Expression.Constant(
Expression.Lambda<Func<X>>(exp, null).Compile().Invoke());
}
catch (Exception ex)
{
return null;
}
}
The type parameter X is the expected return type from the LambdaExpression. For enum types such as ImageFormat, it would be the underlying value type Int32. This is extremely cool: with the ease of a function call, we now can handle ANY expression, as long as it can be evaluated into a constant at runtime before the query execution.
The idea behind implementing Projection operator is quite similar. The difference is that Projection operator can only be evaluated AFTER query execution, when Image objects are readily available:
var test = from img in Google.Images
where img.RelatesTo("microsoft")
select new { img.Rank, img.Url };
The anonymous type {img.Rank, img.Url} is generated at compile time, not part of the expression tree. The Select portion of the query is actually translated into a MemberInit expression, which takes an Image object as its parameter and creates an instance of the anonymous type.
To support this, we can create an adapter class that implements IQueryable, wrap it around our ImageSearcher and execute the MemberInit expression via LambdaExpression.Compile on the result Image objects:
internal sealed class Projector<T, S> :
IQueryable<T>, IOrderedQueryable<T>
{
private IQueryable<S> _chain = null;
private Func<S, T> _delegate = null;
public Projector(MethodCallExpression expr)
{
Diagnostic.DebugExpressionTree(expr);
if (expr.Method.Name == "Select" &&
expr.Arguments.Count == 2 &&
ExpressionUtil.IsLambda(expr.Arguments[1]))
{
ConstantExpression cont = (ConstantExpression)expr.Arguments[0];
_chain = (IQueryable<S>)cont.Value;
LambdaExpression lambda =
ExpressionUtil.GetLambda(expr.Arguments[1]);
if (lambda.Parameters.Count == 1 &&
lambda.Parameters[0].Type == typeof(S))
{
_delegate = (Func<S, T>)lambda.Compile();
return;
}
}
throw new NotSupportedException(
string.Format("Only projection base on type {0} is supported.",
typeof(S)));
}
public IEnumerator<T> GetEnumerator()
{
foreach (S s in _chain)
{
yield return _delegate(s);
}
}
}
And that's it! Now you can perform Google Image Search in your application with the ease of a simple and intuitive LINQ query. And it supports cool features such as projection too! Pretty nice, isn't it?
History
- Update on 5/8/2007
- Added the use of
LambdaExpression and implementation of parameterized query and projection operator.
- Source code has been restructured and now supports Google Groups query as well.
