Wednesday, August 20, 2008 8:04 PM bart

What Do VB 9.0 Error “BC36593: Expression of type ‘X’ is not queryable.” And C# 3.0 Error “CS1936: Could not find an implementation of the query pattern for source type ‘X’.” Really Mean?

While preparing for another one of my posts, soon to be published, I received the following:

image

What can one do when observing such a message? Since watching a grown man cry is both a pathetic and embarrassing situation, downloading the language specification is a good start. Here are my findings. Section 11.21 on Query Expressions says:

A query expression is an expression that applies a series of query operators to the elements of a queryable collection.

Query operators are what I’m playing with – as will become apparent later on – but what’s supposed to be a “queryable collection”? Somewhere further, in paragraph 11.21.2 on Queryable Types the following is said:

Query expressions are implemented by translating the expression into calls to well-known methods on a collection type. These well-defined methods define the element type of the queryable collection as well as the result types of query operators executed on the collection. Each query operator specifies the method or methods that the query operator is generally translated into, although the specific translation is implementation dependent.

Right, but what makes up a “queryable collection”? Where not getting closer yet but somewhere further in the same paragraph one can make a little jump in the air to express a joyful mood:

A queryable collection type must satisfy one of the following conditions, in order of preference:

  • It must define a conforming Select method.
  • It must have have one of the following methods

    Function AsEnumerable() As CT
    Function AsQueryable() As CT

    which can be called to obtain a queryable collection. If both methods are provided, AsQueryable is preferred over AsEnumerable.
  • It must have a method

    Function Cast(Of T)() As CT

    which can be called with the type of the range variable to produce a queryable collection.

In here CT stands for a (queryable) collection with elements of type T. The definition is actually recursive: one of the three bullets needs to be satisfied in order for something to be “queryable CT”. It’s clear that the latter two act as (the recursive case) escape valves to turn something “non-queryable” into something queryable because their result type is denoted as CT. So, all the power lies ultimately in the first bullet (the base case) on a “conforming Select method”. A bit further in the paragraph we read:

It is not necessary for a collection object to implement all of the methods needed by all the query operators, although every collection object must at least support the Select query operator.

Why this restriction? The VB 9.0 spec doesn’t really tell but actually C# does have a similar rule, which is more explanatory. In the C# 3.0 Specification there’s a paragraph 7.15.2.3 on so-called “Degenerate query expressions”:

A degenerate query expression is one that trivially selects the elements of the source. (…) It is important (…) to ensure that the result of a query expression is never the source object itself, as that would reveal the type and identity of the source to the client of the query. Therefore this step protected degenerate queries written directly in source code by explicitly calling Select on the source. (…)

In other words, something like

from c in customers select s

translates into

customers.Select(c => c)

which looks as unnecessary (in the end the lambda passed in is the identity function) but it makes sure that a query can never degenerate in its original source, which ensures the source is kept hidden (some form of encapsulation if you want) from the query consumer. Indeed, the paragraph continues:

It is then up to the implementers of Select and other query operators to ensure that these methods never return the source object itself.

Let’s turn it into practice. Assume we have the following class definitions:

class Bar
{
    public Foo Where(Func<object, bool> predicate)
    {
        // …
    }
}

class Foo
{
    // …
}

then the following query would translate fine:

var res = from b in new Bar() where true select b;

which strictly speaking translates into

var res = new Bar().Where(b => true).Select(b => b);

but Where already “hides” the original source, so the degenerate Select can be trimmed away:

var res = new Bar().Where(b => true);

The fact the result of b.Where, an instance of Foo, doesn’t have a Select method won’t bit us in this case (notice that Where(b => true) could be treated as a degenerate case as well; however, the compiler doesn’t treat it that way and leaves the Where call in). However, when the query is the following:

var res = from b in new Bar() select b;

the translation would look like

var res = new Bar().Select(b => b)

Dropping Select would make the result equal to the source, which is a violation of the rules in 7.15.2.3, so the compiler complains about the non-existence of Select on class Bar (trivial question: why not on Foo this time?) in this case:

image

So, implementing Select is a bare minimum for query provider implementations (that do not go through IQueryable<T> because those already “inherit” a Select implementation). Here’s the resulting code in VB:

Module W
    Sub Main
        Dim res = From b In New Bar Where True
    End Sub
End Module

Class Bar
    Public Function Where(p As Func(Of Object, Boolean)) As Foo
        Return Nothing
    End Function


    Public Function [Select](s As Func(Of Object, Object)) As Bar
        Return Nothing
    End Function

End Class

Class Foo
End Class

that makes the compiler happy. Notice VB doesn’t require you to say “Select b”, a little but handy feature although it makes degenerate queries even more hidden. Why? Tell me what the following means:

Dim res = From b In New Bar

Indeed, the compiler will insert a Select method call for you (hence the reason it needs a Select method in order to be able to do this):

image

where the referenced lambda is as trivial as you can imagine.

Conclusion: We don’t allow degenerate queries to occur; both compiler errors are manifestations of that rule. Obviously this relies on a trust relationship with query providers to play according to the rules; those should never return the original query source when applying a query on it, even if that query just selects all elements from the source. Why? The source object may contain things such as connection strings that you don’t want to leak across the border established by a query over that source object. Providers like LINQ to Objects (returns an iterator yielding all elements in the input source when presented with a degenerate select), LINQ to SQL (establishes some Query<T> object over a Table<T> even when presented with a degenerate select) and LINQ to XML (which is just LINQ to Objects with a special API powering it) play according to those rules.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: , ,

Comments

# C# 3.0 Query Expression Translation Cheat Sheet

Saturday, August 30, 2008 1:29 AM by B# .NET Blog

As a reference for some planned and unplanned future posts, I wanted to share out my “cheat sheet” for

# LINQ to Z3 – Theorem Solving on Steroids – Part 0

Sunday, April 19, 2009 3:31 PM by B# .NET Blog

Introduction Last time around in this blog category we looked at using Z3 for testing satisfiability