November 2008 - Posts

Introduction

On last week’s TechEd EMEA Developers 2008 conference in Spain I redelivered my talk on writing custom LINQ providers, showing off implementations of LINQ to AD and LINQ to SharePoint. One of the questions I received afterwards went along the lines of this blog post’s title: “Dude, where’s my LINQ DML statement support?”. The stock answer to this kind of question points out that it’s up to individual LINQ providers to provide reasonable support for updating data source entries based on the O/whatever mapping they establish. The typical way this is done is through change tracking of entity objects that have been new’ed up by the provider upon execution of the query through LINQ.

However, there are cases where this kind of updating is unsatisfactory, especially when dealing with batch updates that don’t require client-side input or computation. For example, when dealing with interactive users, the change tracking driven solution works great, but when updating a set op records based on a certain update pattern (e.g. increase the price of each product with 5%) there’s no need to suck in all entity objects from the data source only to send them back with updates that could well be executed by the target database. Obviously it all depends on the richness of the underlying database’s DML statements, but assuming it’s flexible enough, how to deal with this in the context of LINQ?

 

Updateable LINQ to Objects

In order to set the scene, let’s investigate what it would take to make LINQ to Objects update-capable. In other words, we want to be able to execute a query and update the retrieved objects in a declarative fashion, i.e. without manual iteration over the query results. To tackle this problem, we can rely on extension methods over IEnumerable<T> in order to provide a method that can apply a certain update-action to each individual object in the sequence. Here’s a possible implementation.

public static void Update<T>(this IEnumerable<T> source, params Action<T>[] updates)
{
    if (source == null)
        throw new ArgumentNullException("source");

    if (updates == null)
        throw new ArgumentNullException("updates");

    foreach (T item in source)
    {
        foreach (Action<T> update in updates)
        {
            update(item);
        }
    }
}

This particular implementation will break the IEnumerable<T> chain as the method is void-returning, but it’s not hard to make it an iterator, yield returning the original sequence elements from the outer loop after the updates have taken place. However, using an iterator in this case might not be the best idea, as the update won’t go through till you start iterating over the resulting sequence because of the lazy nature iterators have. So, let’s stick with void. Next, you might wonder why I chose to pass in an array of update actions instead of a just a single update action. It turns out this doesn’t really matter that much for the in-memory LINQ to Objects case (and indeed, if you just specify a single update action, it will just work fine) but as we’ll see further on, having more manageable individual update actions is a good idea to remote the DML statement. However, in this particular case there’s no way to have more control over the nature of updates, as an Action<T> can be used to point at any procedure, e.g. specified using a statement lambda. Below, I’m illustrating the use of the Update method with more granular update actions:

List<Product> products = new List<Product>() {
    new Product { Name = "Chai", Price = 123m },
    new Product { Name = "Chang", Price = 234m },
};

(from p in products
 where p.Price > 100
 select p).Update(
    p => p.Price *= 0.95,
    p => p.Name = p.Name.ToUpper()
);

foreach (var p in products)
    Console.WriteLine(p.Name + " - " + p.Price);

Notice how other LINQ to Objects operators are used indirectly through query comprehension syntax, more specifically we filter out the items to be updated using a where clause first. As Update performs eager evaluation, enumerating over the source sequence straight away, the results will be visible immediately when iterating over the (now updated) source sequence after the Update invocation. But let’s take a closer look at how we’re specifying the updates above:

p => p.Price *= 0.95

Here we’re using lambda syntax but notice how the specified lambda doesn’t have a statement body. We’re simply leveraging the fact any value can be ‘converted’ to void, so the lambda above which is of type Product –> decimal can be assigned to an Action<T> where T is Product or, in functional signature syntax, a Product –> void. But there’s nothing that keeps us from writing a far more complex statement body:

p => {
   decimal oldPrice = p.Price;
   string oldName = p.Name;
   p.Price = oldPrice * 0.95;
   p.Name = oldName.ToUpper();
}

Just let your imagination work. Why is this a relevant fact? Our original set of update actions are far more “comprehensible” at runtime for introspection (well, if we turn them in something else than Action<T> which doesn’t produce just plain old IL code) because of their declarative nature.

There are still quite a few things lacking from our simplistic LINQ to Objects update support mechanism, such as transactional integrity (e.g. assume one of the update actions blows up, how to roll back previous applied updates?) but you get the overall idea.

 

Updateable remotable LINQ

Now, let’s turn the scene and focus on remotable kinds of LINQ, where we want to send off the DML statement to a remote component, e.g. a DBMS system, to execute the update statement. In order to accomplish this goal, we need a way to represent the update statement in some form that we can inspect at runtime to cross-translate it into the remote DML language, e.g. SQL. Luckily we have such a capability in the framework today, with expression trees.

But what’s in a name? Yes, expression trees. So, we don’t have the ability to represent arbitrary pieces of procedural statement-driven code like we have above with Action<T>:

Action<int> a = i => { Console.WriteLine(i); }; // works
Expression<Action<int>> e = i => { Console.WriteLine(i); } // fails to compile

On the one hand, this is a pity as it limits our expressiveness, but on the other hand it’s a good thing as analyzing arbitrary statement trees would significantly boost the complexity of the translator we’re about to write. However, there’s one significant limitation imposed by this: our update ‘actions’ cannot contain an assignment operator as this can’t be expressed by an expression tree:

Expression<…> e = p => p.Price *= 0.95;

So, even if we’d find a way to specify expression trees to build up a DML statement (see further), we can’t make assignments which obviously is a pretty basic piece of functionality when dealing with updates. So, how to work around this? What about the following? Instead of representing an update ‘action’ as one function, we could represent it as two functions: one that acts as a “update target selector” denoting which entity property to update (e.g. p => p.Price) and one that calculates the new value (e.g. p => p.Price * 0.95). Together these two carry enough information to express the intent of the update:

Expression<Func<Product, decimal>> extract = p => p.Price;
Expression<Func<Product, decimal>> update = p => p.Price * 0.95;

This is a little unfortunate and although there are alternatives (e.g. cooking up some “Updater” object that carries both extractor and updater) most of these yield syntactical clutter, so the bets of having a signature as easy as the following are off:

public static void Update<T>(this IEnumerable<T> source, params Expression<Action<T>>[] updates)

Using an Updater object, we’d end up with:

public static void Update<T, R>(this IEnumerable<T> source, params Updater<T, R>[] updates)

but calling it would be cumbersome:

Update(
    new Updater<Product, decimal>(p => p.Price, p => p.Price * 0.95),
    new Updater<Product, string>(p => p.Name, p => p.Name.ToUpper())
)

where Update has a constructor taking in:

class Updater<T, R>
{
    public Updater(Expression<Func<T,R>> extract, Expression<Func<T,R>> update)

Ideally, we’d have a way to use tuples to keep the two function expression trees together at all times, also being able to use them in a params:

public static void Update<T, R>(this IEnumerable<T> source, params Tuple<Expression<Func<T, R>> /* extract */, Expression<Func<T, R>> /* update */>[] updates)

and hence the ability to call them easily using some hypothetical call-site syntax:

Update(
    (p => p.Price, p => p.Price * 0.95),
    (p => p.Name, p => p.Name.ToUpper())
)

or even without the additional parentheses pairs (at this time I’m even not thinking about disambiguation, overload resolution, betterness rules, and all this goodness). Or, we could lift the common Expression part out of the tuples, ending up with:

public static void Update<T, R>(this IEnumerable<T> source, params Expression<Func<T, Tuple<R /* extract */, R /* update */>>>[] updates)

Internally, the Update method could now inspect the way the Tuple<R,R> is instantiated, extracting the expression trees for the extract and update parts. However, we’re not all too pleased with the calling syntax that would need to new up tuple objects, obfuscating the intent of the code.

Let’s go over our needs and observations one more time before we settle on some design:

  • We’re bound to the limitations of expression trees; hence:
    • we cannot express an individual update action as one expression (no assignment operation supported);
    • so, an update action needs to be split into an extract and update phase;
    • and, by extension, an update action can only target one value on the entity object at a time.
  • It should be possible to specify multiple update actions at a time to execute them as one unit:
    • this supports transactional updates;
    • we need a way to batch up update actions.

 

Introducing IUpdateable<T>

By now, we all know about the mysterious IQueryable<T> interface of LINQ. I’ve blogged about it several times, but here’s the key take-away: IQueryable<T> represents a query, wrapping an expression tree denoting the semantics of the intended query, and providing iteration facilities by means of its IEnumerable<T> parent. This, however, only tells half of the story, namely the “IQuery” part. The other half, the “able” part, is not visible on the interface per se, and allows users to extend the query by applying additional query operators that are supplied by means of the extension method in the Queryable class, each of which represents a query operator, like Where, Select, OrderBy, etc. This design allows the implementer of the interface to focus on the query execution part rather than the query construction part which is totally done on behalf of the implementer by means of the extension methods.

One way to think about IQueryable<T> in general is as a giant state machine. Most of the IQueryable<T> extension methods return an IQueryable<T>, so applying the method (i.e. some query operator) puts us back in the domain of a (new) IQueryable<T>. However, there are other methods like AsEnumerable that allow us to switch to another world, the one of IEnumerable<T>, where we have similar extension methods. To provide update support, we can play a similar trick:

  • Users write the base query (typically only using filtering) to extract the records that need to be updated – this happens in the IQueryable<T> domain.
  • Next, we transition out of the IQueryable<T> into the IUpdateable<T> domain to provide update support.
  • In IUpdateable<T>, updates can be batched up by calls to a Set method, specifying individual update actions, returning a new IUpdateable<T>.
  • Once all update actions have been specified, an Update method can be called to execute the batch of updates.

A few questions and remarks:

  • Why starting for IQueryable<T>? In quite some cases, users will want to filter records before applying updates. Right, so what about just having a Where method on IUpdateable<T>? Well, it turns out other operators might be useful as well, such as ordering in case the update would be used to number items based on their ordering (left to the reader as an exercise to think about ways to provide this capability in IUpdateable<T>). Similarly, things like Take could be translated into TOP clauses to apply the update only to the first number of items. And so on. In the end, providing all IQueryable<T> operators first, allowing the user to transition into IUpdateable<T> seems beneficial although some operators likely don’t make much sense (like Select, which would result in updating a projection…).
  • How to iterate over the resulting records, after the update has been applied? This kind of combined approach seems attractive too, but we won’t go there in the scope of the blog post. However, providing this feature shouldn’t be too hard, by means of an AsQueryable method, or by making IUpdateable<T> also IEnumerable<T>, where an iteration triggers execution of the update followed by iteration over the original query that got captured by AsUpdateable originally. This too is left as an exercise for the reader.

Time to present our new interface:

interface IUpdateable<T>
{
    Expression Expression { get; }
    IUpdateProvider Provider { get; }
}

It pretty much follows the design of IQueryable<T> where the Expression property captures the expression tree for the update so far, and the Provider property is used by the extension methods to gain access to a factory method to new up new IUpdateable<T> objects:

interface IUpdateProvider
{
    IUpdateable<T> CreateUpdate<T>(Expression expression);
    int Update(Expression expression);
}

In addition, the provider supplies an Update method that will take in the constructed updateable object’s expression tree, carrying out the update and returning the number of affected records. This one can be compared to the Execute method on IQueryProvider. So, how to use those two interfaces now? All of the direct uses will be provided by means of extension methods:

public static class Updateable
{
    public static IUpdateable<T> AsUpdateable<T>(this IQueryable<T> source)
    {
        IUpdateProvider updateProvider = source.Provider as IUpdateProvider;
        if (updateProvider == null)
            throw new InvalidOperationException("Update operations not supported by this query provider.");

        return updateProvider.CreateUpdate<T>(
            Expression.Call(
                null,
                ((MethodInfo)MethodBase.GetCurrentMethod()).MakeGenericMethod(typeof(T)),
                new Expression[] { source.Expression }
            )
        );
    }

    public static IUpdateable<T> Set<T, R>(this IUpdateable<T> source, Expression<Func<T, R>> extract, Expression<Func<T, R>> update)
    {
        return source.Provider.CreateUpdate<T>(
            Expression.Call(
                null,
                ((MethodInfo)MethodBase.GetCurrentMethod()).MakeGenericMethod(typeof(T), typeof(R)),
                new Expression[] { source.Expression, extract, update }
            )
        );
    }

    public static int Update<T>(this IUpdateable<T> updateable)
    {
        return updateable.Provider.Update(updateable.Expression);
    }
}

Here the first method, AsUpdateable, captures an existing IQueryable<T> and checks whether its provider (of type IQueryProvider) supports updates. This piggybacking on top of the existing provider infrastructure is a good thing in general as implementers of an update-capable provider will need to talk to the query provider in order to translate the query portion of the update statement (e.g. a WHERE clause). Being the flip side of it, this means it’s not really possible to sprinkle update support on top of an existing query provider without modifying that provider. You could imagine an additional overload to AsUpdateable that takes in an IUpdateProvider object, and though this would work you’d end up implementing some of the query operators yourself again (e.g. to support filtering). If you know the original query provider’s concrete class and you know it exposes a way to take in an expression tree representing a query, getting back the translated query, there might be a way to avoid duplication (provided the target query language is compositional in nature):

var provider = (SomeSqlQueryProvider)source.Provider;
string sql = provider.GetSqlStatement(source);

string update = “UPDATE “ + … + “ FROM (“ + sql + “)”; // pseudo-SQL

But let’s ignore this for now. Other than this, AsUpdateable is straightforward, it takes the original expression tree and wraps it in a MethodCallExpression for the current method. Just like IQueryable<T> does this, the original expression tree gets extended with information about the applied operators represented as method calls.

The Set method, representing an individual update action, is completely similar. More interesting is its signature: besides of an IUpdateable<T> object, it takes in both the extract and update functions as expression trees, using the principle we talked about earlier.

Finally, Update is just syntactical sugar on top of an IUpdateable<T> to call into the underlying provider to carry out the update, allowing for a fluent interface design. Ultimately, all of this can be used as follows:

(from p in new Table<Product>()
 where p.Price > 100
 select p).AsUpdateable()
    .Set(p => p.Price, p => p.Price * 0.95)
    .Set(p => p.Name, p => p.Name.ToUpper())
.Update();

Going out in the woods we could start dreaming about integrated syntax that looks like this:

from p in new Table<Product>()
where p.Price > 100
update p.Price *= 0.95,
       p.Name = p.Name.ToUpper();

which might automatically become eager, i.e. the Update call is implicit, or stays lazy (which would mean one can reuse the query/update comprehension expression). VB syntax could be very similar, optionally using the With keyword (Update p With …).

Enough dreaming for now, this whole expression (more specifically everything before the .Update() part) translates into an expression tree, constructed at runtime with the aid of the Queryable query operators and Updateable update operators, that can be represented as follows using ToString notation:

expression = {value(Table`1[Product]).Where(p => (p.Price > 100)).AsUpdateable().Set(p => p.Price, p => p.Price * 0.95).Set(p => p.Name, p => p.Name.ToUpper())}

Now the update provider can go ahead and cross-translate this expression tree into a statement the target data source understands, e.g. a SQL DML statement for UPDATE (I’m not a SQL language expert, so treat the following as conceptual code):

UPDATE Products WHERE Price > 100 SET Price *= 0.95, Name = TOUPPER(Name)

I’ll leave a concrete implementation of an update provider to the inspired reader; a basic prototype for SQL (only allowing columns to be updated with constant string or integer values) worked like a charm. In addition, the reader should feel free to think about how it would be possible (if desirable at all, something to think about as well) to make the “LINQ to Objects with update support” case similar to the remotable case, in terms of used operators (i.e. our current LINQ to Object implementation in the first paragraph doesn’t use Set method calls and isn’t lazy at all).

Enjoy!

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

Why this is not a C# 4.0 blog post…

By now most of you have probably heard about the dynamic capabilities that will be added to the C# 4.0 language. Search engines start to fill their databases with lots of descriptions of and discussions about the feature, but for now I won’t (yet) contribute to this (although at the time of fetching the previous link, my post on DynCalc was mistakenly on that list). Not yet, as it will get covered in my C# 4.0 Feature Focus series in the foreseeable future, but let me give away my take on it:

Today’s code is surrounded by an increasing number of dynamic environments and data sources. Targeting these is way too hard today. Think of interactions with JavaScript, loosely typed XML documents, calling into libraries written in dynamic languages, etc. It’s not because you’ve chosen for a statically typed environment like the CLR you should be punished when trying to reach out to any of these environments or data sources. So, dynamic is a good thing when used properly, so the motto should be “static wherever possible, dynamic if necessary”.

So, what’s this post about then? To set the context for further posts on the C# 4.0 dynamic feature and other DLR related topics, I want to highlight a few basic principles of dynamic dispatching first. A while ago, in the context of framework testing frameworks and general DLR-related stuff, I came up with the (not so original) concept of a “ducktaper”. While it’s easy to reach out to a static world from within a dynamic fortress (e.g. PowerShell, IronRuby, IronPython, etc calling into BCL functionality) the reverse, calling dynamic objects as if they were static, is like rowing against the current. The way people dealt with this problem for a long time is by creating statically typed wrappers around dynamic objects, which is a compile-time task as opposed to a runtime tasks. Doing this as a runtime task is what the “ducktaper” is all about.

To wet your appetite, here’s what it’s meant to look like:

object dynamicDuck = GetDuckFrom(DuckSource.Pond);
IDuck duck = dynamicDuck.AsIf<IDuck>();
duck.Walking += (o, e) => { Console.WriteLine(“Duck is walking”); };
duck.Walk(); // How can a static duck walk <g>?
Console.WriteLine(duck.Quack(“Bart”));
duck.Walk();

This post is not only about how to make such a thing work – and there are really a variety of ways to do this; I’ll only present the outcome of the last prototype – but also why this is or isn’t a good idea. Though I intend to keep this to one post (albeit a lengthy one I can already predict now), it might get a tail somehow :-). Notice no guarantees are made about the code, use it at your own risk – it’s merely meant as a brain-dump on dynamic dispatching techniques.

 

What’s in a name?

Well, two parts really: duck and tape. Etymological discussions don’t agree about the origin of the word “duct tape”, but duck is more appropriate in this context. A breakdown:

  • duck refers to “duck typing”, a programming language concept that allows developers to concentrate on the use of an object rather than its type. A typical way to refer to it is: “If it walks like a duck and quacks like a duck, I would call it a duck.”, so as long as an object accepts (and responds to) Walk and Quack messages, we’re okay to send those messages.
  • tape, when applied, has the characteristic of putting pieces of stuff together. In this case we’re binding dynamic objects to statically typed contracts, so you can consider it to be type-tape. The glue operator is called AsIf and will be described in a lengthy fashion in this post.

 

Where to get it?

With all the usual aforementioned restrictions and warnings applied, here’s where you can grab the complete project, including:

  • Library code for the DuckTaper
  • Sample use in a console application
  • Unit tests

The solution and projects are created in Visual Studio 2008.

 

How does it work?

Starting from a macroscopic level, let’s examine what the following call really looks like from the outside:

IDuck duck = dynamicDuck.AsIf<IDuck>();

The object on which we call AsIf<T> can be anything, so its type ought to be System.Object in order to yield this flexibility. As the System.Object type doesn’t have such a method, we need to cook our own (if it had such a method, this blog post wouldn’t have a reason to exist), so that’s where extension methods enter the picture. This is merely an implementation detail and I won’t even bother discussing whether or not it’s a good idea to put extension methods on the mother of all types (why not?), so I’ll leave the judgment to the reader. More relevant is the generic parameter that accepts an interface type, which becomes the return type. Putting the pieces together, we end up with this signature:

public static T AsIf<T>(this object target) where T : class

Generic constraints (Partition II – 10.1.7) don’t have the expressive power to limit T to be an interface type, so we’ll need a runtime check as well. Our entry-point function ultimately looks like:

public static T AsIf<T>(this object target) where T : class
{
    Type targetType = typeof(T);

    //
    // Check target is an interface.
    //
    if (!targetType.IsInterface)
        throw new InvalidOperationException("Target type of AsIf<T> cast should be an interface.");

    return AsIfInternal<T>(target, targetType, true);
}

What’s behind the scenes in AsIfInternal will follow soon. But let’s elaborate on an important point here first: why does T need to be an interface? Ultimately what our implementation needs to do is generating an object type at runtime that’s “compatible” with the type specified in generic parameter T. Allowing concrete types for T will make matters much more complicated, for lots of reasons (e.g. what if the type is sealed). But also from a philosophical point of view, we desire to “morph” the original object to a given operational contract, so all we want here is some sort of (weak – to be explained below) contract that’s a description of the intended “interface” that’s to be layered on top of the existing object.

For example, assume the retrieved duck object looks as follows (remember, for now we’re not considering arbitrary dynamic objects, so we’ll use plain C# class definition syntax here), omitting member definitions for clarity and brevity:

class Duck
{
    public void Walk();
    public void Walk(int steps);
    public string Quack(object name);
    public ConsoleColor Color { get; set; }
    public event EventHandler Walking;
}

Next, consider the following desired “weak contract”:

weak contract IDuck
{
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
}

Notice I’m not using the interface keyword above. We’re entering the realm of a hypothetical C# look-a-like. Going even further down the road of hypothetism, what we’re really looking for here is some kind of asif keyword that can “cast” an object to a weak contract, handing back a wrapper object that behaves like the contract but dispatches to the underling original object underneath:

IDuck duck = dynamicDuck asif IDuck;

- or even -

IDuck duck = dynamicDuck asif {
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
};

which is to be read as: “as if it were” or “as if it adhered to”. But why referring to this as a weak contract? Interfaces, as we know them in C#, represent a strong contract. To the CLI, it doesn’t matter that much (Partition I – 8.2.3):

A type fully describes a value if it unambiguously defines the value’s representation and the operations defined on that value. (…) Some types are only a partial description; for example, interface types. (…)

The word contract doesn’t enter the picture here. However, languages like C# state things in a stronger manner (C# 3.0 specification, chapter 13):

An interface describes a contract. A class or struct that implements an interface must adhere to its contract. (…)

Both the provider of the interface and all of its consumers agree upon the contract and implementing an interface is like signing a strong mutual contract. In here, the consumer agrees to adhere to the contract in its implementation, while the provider guarantees the contract is kept stable (with no room for small print). An interface embodies more than typing: interfaces often act as protocols between different parties, which are not expressible in the type system. For instance, the contract might require you to call Initialize first, followed by anything else as long as Dispose isn’t called. In practice this means interfaces cannot be changed, both on the type-level (messing with interface methods, adding/removing them, etc) and the semantic level. Changing stuff means creating a new interface – typically with a version number suffix – and having consumers sign the new contract.

Why is this relevant in this context? Notice the Duck class above, it doesn’t implement IDuck (and assume IDuck is a strong contract – i.e. an interface in realistic C# terms – for now) in an explicit manner. This means it’s not participating in the strong contract IDuck provides and we can only guess that the Duck object behaves like the IDuck specification. That’s what duck typing is about: the object looks like a duck, so there’s a chance it’s really a duck. The hypothetical asif operator expresses taking the bet that the duck object really is a duck. In the sample case, the bet has little chances to be wrong, but we don’t have guarantees.

To illustrate this, consider the following:

object dynamicDuck = GetDuckFrom(DuckSource.Oven);
IDuck duck = dynamicDuck.AsIf<IDuck>();
duck.Walk();

Most likely a baked duck will throw a NotSupportedException (or a more plastic exception type, depending on your imagination) when calling Walk, but what if IDuck assumes a living duck and doesn’t indicate NotSupportedException as a possible exception? Or what if the Quack method on IDuck specifies a specific duck language dialect to be spoken by the duck (although that could be expressed in the type system)? The duck implementer did never explicitly say his duck implementation adheres to the rules of IDuck, and there can be a variety of reasons for this: maybe the implementer didn’t know about the IDuck interface, or maybe his duck isn’t compliant with the IDuck contract.

Sometimes making a guess is relatively safe though. C# already does this to a limited extent:

both without a specific interface requirement. In the case of LINQ, requiring an interface to be used would result in a gigantic interface (containing all query operators) no-one would be interested in to implement (for more information on how to resolve this tension, see The Most Funny Interface Of The Year … IQueryable<T>). Another place with similar flexibility rules is the C# 3.0 collection initializers feature that require an Add method on an IEnumerable object (no, not an ICollection, this is not a typo – see paragraph 7.5.10.3 of the C# 3.0 specification).

However, weak contracts are not a supported runtime or language construct at this point, so the best we can get is something that mimics a “collection of members” pretty well: interfaces. And this is an important caveat to point out: we’re piggybacking on strong contracts to realize weak contracts, which is not ideal. (It turns out it will get even a bit messier in the implementation in terms of visibility, see further…) Actually, we can put a band-aid mitigation in place as well, by sprinkling a custom attribute on interfaces indicating they’re used as a weak contract, and refusing to use any non-marked-as-such interfaces in the context of AsIf<T> (but as you realize, this is a uni-directional fix-up as it doesn’t avoid weak contracts to be used as a strong one). This strategy is implemented in the code that’s available for download:

weak contract IBar
{
    void Foo();
}

is indicated as

[WeakContract]
interface
IBar
{
    void Foo();
}

 

How does it really work?

Now that we’ve pointed out a few important aspects of the implementation philosophy and restrictions imposed by the runtime and language concepts at hand, we can turn our attention to more implementation details. Our internal entry-point looks like this:

/// <summary>
/// Creates a wrapper object of type <typeparamref name="T">T</typeparamref> around the specified <paramref name="target">target</paramref> object.
/// </summary>
/// <typeparam name="T">Target type.</typeparam>
/// <param name="target">Object to be wrapped.</param>
/// <param name="targetType">Target type (avoids having to call typeof again).</param>
/// <param name="shortCircuit">Indicates whether or not short-circuiting is allows if the object already implements the specified interface.</param>
/// <returns>Wrapper around the specified object.</returns>
private static T AsIfInternal<T>(object target, Type targetType, bool shortCircuit) where T : class

‘All’ we have to do in here is creating something that looks like T while really acting as target. The first part of the equation translates into type generation, the second part into dispatching calls. Putting the pieces together we end up with type generation of a wrapper dispatching to the original object. This is where System.Reflection.Emit kicks in. By itself this has a few caveats:

  • A feature known as “restricted skip visibility” (see DynamicMethod on MSDN) is not available at this level, nor is it applicable (Why did I refer to it anyway? Well, because in philosophy it’s the same as what we need.) in our case. Since we’re implementing T (which, remember, denotes an interface type), what this really means is that the interface type should be public in order to have a dynamically emitted type in a dynamically emitted assembly implement it.
  • Loading a dynamically generated assembly into the current application domain makes it impossible to unload it; marshalling it across application domain boundaries would introduce its own set of problems. Actually the dynamic assembly (and module) is a side-effect of what we really need: just a dynamically generated type. On this field though, things will improve in .NET Framework 4.0 (but also for other reasons, making large parts of this blog post’s exercise dispatchable to the CLR/DLR synergy).

Remember this is a proof of concept implemented in today’s world of .NET, so we’ll ignore those issues for now. So, what are we up to? Some IL generation for sure, but let’s try to minimize the amount of IL that needs to be generated. As we’re wrapping an object – and not extending it in any way (for reasons outlined earlier) – we have the luxury to pull off a wrapper type that can derive from a base class. This has the additional benefit of having a way to determine statically whether an object is a dynamic object wrapper or not, by checking whether it derives from that particular wrapper base class (just an “is” or “as” suffices). Let us call this base class type Dynamic, then what we need to do translates into the following (in pseudo-meta-code):

class <NameForTheWrapperObject> : Dynamic, T
{
    <%
        foreach (MemberInfo member in typeof(T).GetMembers())
            ImplementInterfaceMember(member);
    %>
}

The relevant piece here is the type hierarchy, creating a subtype of Dynamic while implementing interface T. Yet another reason why we need T to be an interface as multiple inheritance is banned from our world (for good enough reasons, but that’s a different discussion). A few remarks on this meta-code:

  • GetMembers is considered to do a recursive scan of all members in the type hierarchy denoted by T. It’s possible that the interface T “inherits from” other interfaces, so we need to cover all members in the entire tree starting from T.
  • Interface members can be methods, properties, indexers (which are really a special kind of properties) and events.
  • Implementation of interface members will be the most complicated part obviously and will not only involve implementing the method with some stock code that does the dispatch but we’ll also need some fields to make everything work, see further.

But let’s start at the root: Dynamic. What does the Dynamic class need to be capable of doing? Here are its basic tasks:

  • It holds the wrapped object.
  • It has a way to dispatch invocations from the (to-be-implemented-by-subclass) interface members to the underlying wrapped objects.

To speed up dispatching we can introduce an intermediate concept that maintains a cache of possible invocation dispatch targets on a per-member basis. Doing so opens up for opportunities to provide fast paths when an invocation is repeated and have method overload resolution mechanisms decentralized from the wrapper object’s code and Dynamic base class’s code itself. Such a concept is often referred to as a “call site”, so let’s call that guy a CallSite. Although we won’t implement it in an advanced way, I still want to have it around to explain a few concepts. In fact you could well live without it, having the wrapper call into the base on some “InvokeMember” method that does the dispatch and implements caching strategies by itself. Here we enter the domain of what the DLR excels at, but we’ll avoid all of that complexity for the purposes of this blog post.

Putting the pieces together, here’s what we end up with for Dynamic:

/// <summary>
/// Base class for dynamic objects.
/// </summary>
public abstract class Dynamic
{
    /// <summary>
    /// Target object.
    /// </summary>
    private object _target;

    /// <summary>
    /// Creates a new dynamic object wrapping the specified <paramref name="target">target object</paramref>.
    /// </summary>
    /// <param name="target">Wrapped target object.</param>
    protected Dynamic(object target)
    {
        this._target = target;
    }

    /// <summary>
    /// Gets the wrapped target object.
    /// </summary>
    public object Target
    {
        get
        {
            return _target;
        }
    }

    /// <summary>
    /// Determines whether the wrapped object refers to the same object as the object wrapped by the passed in dynamic object.
    /// </summary>
    /// <param name="obj">Object to compare to.</param>
    /// <returns>true if the wrapped object refers to the same object as the object wrapped by the passed in dynamic object; false otherwise.</returns>
    /// <remarks>Equality between a dynamic wrapped object and a non-wrapped object object always returns false as we can't guarantee commutativity.</remarks>
    public override bool Equals(object obj)
    {
        Dynamic dynamic = obj as Dynamic;

        if (dynamic == null)
            return false;

        return object.ReferenceEquals(dynamic._target, this._target);
    }

    /// <summary>
    /// Returns the hash code of the wrapped object.
    /// </summary>
    /// <returns>Hash code of the wrapped object.</returns>
    public override int GetHashCode()
    {
        return _target.GetHashCode();
    }

    /// <summary>
    /// Returns the string representation of the wrapped object.
    /// </summary>
    /// <returns>String representation of the wrapped object.</returns>
    public override string ToString()
    {
        return _target.ToString();
    }

    /// <summary>
    /// Creates a call-site for the specified <paramref name="member">member</paramref>.
    /// </summary>
    /// <param name="member">Member to create a call-site for.</param>
    /// <returns>Call-site for the specified <paramref name="member">member</paramref>.</returns>
    protected CallSite GetCallSite(string member)
    {
        return new CallSite(this._target, member);
    }
}

Notice how Dynamic is a tiny wrapper around a System.Object instance also just forwarding methods like ToString and GetHashCode to the wrapped object. Equals is defined in terms of referential equality of the wrapped object too. Other than that, there are two pieces meant for use by the generated subclasses: the constructor (notice how the _target field is hidden from the subclasses – those subclasses don’t call into the Target getter either but you’ll have to take my word for it just for now) and the GetCallSite method.

This GetCallSite method is of particular interest. The subtype of Dynamic will hold a CallSite field for every method implemented for the requested interface type. Notice I’m saying every method which is not the same as every member, because properties/indexers can have one or two methods (getter and/or setter) and so do events (add and/or remove methods). Those call site objects will be created lazily: on the first call to an implemented method, they are retrieved and stored in a private field. In other words, methods are resolved through call sites as they are called. This has pros and cons, which you can think about for a while (tip: early binding versus late binding; take the real dynamic nature of dynamic objects and expandos into account as well). Time to move on to CallSite. As mentioned before this is really a rudimentary implementation and DLR / C# 4.0 mechanisms would be very appropriate here, which I’ll talk about another time:

/// <summary>
/// Call site used to dispatch method calls on a thunk type instance to the underlying wrapped type.
/// </summary>
public class CallSite
{
    /// <summary>
    /// Object being wrapped by the thunk this call-site belongs to.
    /// </summary>
    private object _target;

    /// <summary>
    /// Name of the member to dispatch. CLI naming conventions are followed for special-name methods.
    /// </summary>
    private string _member;

    /// <summary>
    /// Creates a call-site to invoke the specified <paramref name="member">member</paramref> on the specified <paramref name="target">target object</paramref>.
    /// </summary>
    /// <param name="target">Target object to dispatch to.</param>
    /// <param name="member">Member to invoke.</param>
    public CallSite(object target, string member)
    {
        _target = target;
        _member = member;
        Invoke = ResolveCall;
    }

    /// <summary>
    /// Helper method to resolve a call the first time it's made through the call-site.
    /// </summary>
    /// <param name="args">Arguments to call the member with.</param>
    /// <returns>Return value from the dispatched call.</returns>
    private object ResolveCall(object[] args)
    {
        //
        // TODO: Richer dispatching techniques, using DLR and C# 4.0 technologies.
        //

        //
        // Simplistic bind and invoke. Ideally we should call specialized binders here,
        // figure out whether the member is available and throw if it isn't. Once we
        // have the target member, we can set up the fast path by overwriting Invoke.
        //
        Invoke = arguments => _target.GetType().InvokeMember(_member, BindingFlags.InvokeMethod, null, _target, args, CultureInfo.InvariantCulture);

        //
        // First time call.
        //
        return Invoke(args);
    }

    /// <summary>
    /// Invocation function used by the emitted code in the thunk to dispatch to the target method wrapped by this call-site.
    /// </summary>
    public Func<object[], object> Invoke { get; private set; }
}

One key concept is illustrated here: thunking. As the call site object is created, the Invoke member (which will be called by the emitted wrapper object, see further) is initially set to ResolveCall. When Invoke is called for the first time, the ResolveCall method it’s pointing at does all the (omitted/simplified in the code above) magic it needs to do in order to resolve the call (what’s in a name?), ultimately replacing Invoke by a new function that calls directly into the underlying member. Again there are pros and cons with regards to caching and the flexibility to do a re-resolve at a later time, so once more: this just illustrates one way of approaching things.

Keep in mind where the CallSite corresponds to in the emitted object: an individual interface method implementation. This means the number of arguments passed in through the args array will always be the same, which is relevant for the call dispatch resolution as well since multiple overloads of the same method on the target interface will each have their own call site object. The way we solve the binding and dispatching here is in the most lame way imaginable: Type.InvokeMember with the default binder. More flexibility, including calling through expando objects, IDynamicObject, etc can be obtained by switching to DLR mechanics (with or without a different call site approach). Obviously you could experiment a little with your own logic in ResolveCall, for example to handle IExpando objects.

Thunking is a technique used in a variety of places, including the CLR’s JIT infrastructure. The way it works there is as follows: upon loading an assembly and its types (assuming the non-ngen case), MethodTable structures in the EE will be filled with entries to a so-called pre-stub helper that invokes the JIT compiler for that method’s associated IL stream when called for the first time. The JIT compiler carries out IL-to-native translation, generating the native code on the heap and patching up the MethodTable entry with an address pointing at the start of the emitted native code. From that point on, for that method, the JIT compiler is out of the picture for the lifetime of the type in memory.

 

How we cook our wrapper type

Now that we know the macroscopic structure, it’s time to dive into the microscopic world, and how better to start this than looking at what the emitted code should look like? Here’s the hypothetical target code, where the contract is really implemented as an interface of type IDuck:

IDuck duck = dynamicDuck asif {
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
};

Goal is to define the wrapper type now. We already reached an agreement on its type declaration before, i.e.:

class <NameForTheWrapperObject> : Dynamic, IDuck
{
    <%
        foreach (MemberInfo member in typeof(IDuck).GetMembers())
            ImplementInterfaceMember(member);
    %>
}

Now what does an individual member of the interface look like? In this case IDuck stands by itself, so the call to GetMembers results in the degenerate case where no recursion is required, but in the general case we need recursion. Creating such a recursive method without getting stuck in cycles isn’t too hard, so let’s skip that technicality in this write-up as you can read the code yourself. What’s more interesting is how an individual interface member is implemented like. Starting with the base case of a method, here’s what we intend to do:

object Quack(string name);

becomes

private CallSite _site1;

public object
Quack(string name)
{
    if (_site1 == null)
        _site1 = base.GetCallSite(“Walk”);

    return (object)_site1.Invoke(new object[] { name });
}

Here we make sure the field representing the call site for this particular method (overload) is initialized, followed by a call through the site’s Invoke delegate passing in all parameters as an object array and casting the return value back to the return type on the interface member (which turns out to be object anyhow).

As we don’t have the compiler as a service just yet, we need to cook our own IL emission here, so this calls for System.Reflection.Emit magic. As we’re building a type we can’t get away with the DynamicMethod class, so we need to buy in to the entire stack of builder types that provide the chain of “assembly contains modules contains types contains members”. We can short-circuit stuff a bit by limiting ourselves to one assembly containing one module which will contain all the built wrapper types during the execution of the program (actually on a per appdomain level, but let’s ignore that for now).

First we need to have all the machinery to ensure a singleton ModuleBuilder instance:

/// <summary>
/// Ensures the module builder singleton is available.
/// </summary>
private static void EnsureModuleBuilder()
{
    if (s_moduleBuilder == null)
    {
        AssemblyBuilder assemblyBuilder = AppDomain.CurrentDomain.DefineDynamicAssembly(new AssemblyName("DuckTaperGen"), AssemblyBuilderAccess.Run);
        s_moduleBuilder = assemblyBuilder.DefineDynamicModule("Thunks");
    }
}

One relevant thing here is the AssemblyBuilderAccess enum value passed in. We’ll only emit the assembly to run it in memory, but with RunAndSave we could save our thunk-types for reuse as well (I’m overloading the word “thunk” here to indicate a type that acts as a thunk around the wrapped object, feel free to substitute thunk with wrapper in what follows – with some goodwill, the thunking part of it is actually the fact it fills in call sites lazily). Now we have this, it’s time to new up the required TypeBuilder for our thunk type:

/// <summary>
/// Gets a type builder for a type with the specified <paramref name="thunkTypeName">type name</paramref>.
/// </summary>
/// <param name="thunkTypeName">Name of the type to create a type builder for.</param>
/// <returns>Type builder for the specified <paramref name="thunkTypeName">name</paramref>.</returns>
private static TypeBuilder GetTypeBuilder(string thunkTypeName)
{
    return s_moduleBuilder.DefineType(thunkTypeName, TypeAttributes.Class | TypeAttributes.Public | TypeAttributes.AutoLayout | TypeAttributes.AnsiClass | TypeAttributes.Sealed | TypeAttributes.BeforeFieldInit);
}

Here we follow the metadata flags used on classes emitted by the C# compiler, all of which you can find the meaning for in ECMA 335: public, sealed and class are straightforward, others have to do with the type layout, string treatment and initialization guarantees. How will we name our thunk type? It definitely needs to be unique and it’s auto-generated so let’s make it a little obscure:

/// <summary>
/// Gets a unique name for the thunk created for the specified <paramref name="targetType">target type</paramref>.
/// </summary>
/// <param name="targetType">Target type to get a unique thunk type name for.</param>
/// <returns>Thunk type name for the specified <paramref name="targetType">target type</paramref>.</returns>
private static string GetThunkTypeName(Type targetType)
{
    return "<>__Thunks." + targetType.FullName;
}

Remember the CLR doesn’t know about namespaces at all, so the FullName of the passed in type will contain the namespace as well as the prefix (looking as the top namespace), so we’re sure to have a unique name. Given those pieces of glue, we can start moving (back) on to the entry point and take it from there:

/// <summary>
/// Creates a wrapper object of type <typeparamref name="T">T</typeparamref> around the specified <paramref name="target">target</paramref> object.
/// </summary>
/// <typeparam name="T">Target type.</typeparam>
/// <param name="target">Object to be wrapped.</param>
/// <param name="targetType">Target type (avoids having to call typeof again).</param>
/// <param name="shortCircuit">Indicates whether or not short-circuiting is allows if the object already implements the specified interface.</param>
/// <returns>Wrapper around the specified object.</returns>
[SuppressMessage("Microsoft.Design", "CA1004:GenericMethodsShouldProvideTypeParameter", Justification = "By design.")]
private static T AsIfInternal<T>(object target, Type targetType, bool shortCircuit) where T : class
{
    //
    // Short-circuit objects that already implement the interface.
    //
    if (shortCircuit)
    {
        T targetAsT = target as T;
        if (targetAsT != null)
            return targetAsT;
    }

    //
    // Singleton module builder.
    //
    EnsureModuleBuilder();

    //
    // Get the thunk type.
    //
    Type thunkType = GetThunk(targetType);

    //
    // Create and return the thunk instance.
    //
    return (T)Activator.CreateInstance(thunkType, target);
}

/// <summary>
/// Gets the thunk type definition for the specified target type.
/// </summary>
/// <param name="targetType">Target type to get a thunk type definition for.</param>
/// <returns>Thunk type definition for the specified target type.</returns>
/// <remarks>If a thunk type has already been created for the target type, the same type definition will be returned.</remarks>
private static Type GetThunk(Type targetType)
{
    string thunkTypeName = GetThunkTypeName(targetType);

    //
    // Don't regenerate the thunk type if it already exists for the specified target type.
    //
    Type thunkType = s_moduleBuilder.GetType(thunkTypeName, false, false);
    if (thunkType == null)
    {
        thunkType = BuildThunkType(targetType, thunkTypeName);
    }

    return thunkType;
}

Notice how we reuse thunk types in GetThunk if they were already created for the target interface. Thunk types are generic on a per-interface basis as their underlying code deals with a weakly typed object they dispatch to; the individual instances of the thunk type have the opportunity to diverge in terms of their generated call sites in order to provide the fastest possible dispatch to the underlying object for that object’s concrete runtime type. So, the type definition is the same, but the runtime instance can and will vary.

/// <summary>
/// Builds a thunk type definition with the specified <paramref name="thunkTypeName">name</paramref> for the specified <paramref name="targetType">target type</paramref>.
/// </summary>
/// <param name="targetType">Target type to create a thunk type definition for.</param>
/// <param name="thunkTypeName">Name to be used for the created thunk type definition.</param>
/// <returns>Thunk type definition for the specified <paramref name="targetType">target type</paramref>.</returns>
private static Type BuildThunkType(Type targetType, string thunkTypeName)
{
    TypeBuilder typeBuilder = GetTypeBuilder(thunkTypeName);

    //
    // Set the parent type to Dynamic.
    //
    typeBuilder.SetParent(typeof(Dynamic));

    //
    // Implement constructor for thunked object.
    //
    ImplementConstructor(typeBuilder);

    //
    // Implement all interfaces.
    //
    int siteCounter = 0;
    foreach (Type interfaceType in GetInterfaces(targetType))
    {
        ImplementInterface(interfaceType, typeBuilder, ref siteCounter);
    }

    return typeBuilder.CreateType();
}

In BuildThunkType we do the real work in case a thunk hasn’t been created yet. First we set the parent to be Dynamic, next we implement the constructor and finally we implement all interfaces specified by the target type, where we take the closure of all interfaces required. Skipping ImplementConstructor for a while (see next paragraph) and ignoring the recursive definition for GetInterfaces, here’s how ImplementInterface looks like:

/// <summary>
/// Implements the specified <paramref name="interfaceType">interface type</paramref>.
/// </summary>
/// <param name="interfaceType">Interface type to implement.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterface(Type interfaceType, TypeBuilder typeBuilder, ref int siteCounter)
{
    //
    // Add implements clause.
    //
    typeBuilder.AddInterfaceImplementation(interfaceType);

    //
    // Implement all members.
    //
    foreach (MemberInfo member in interfaceType.GetMembers())
    {
        ImplementInterfaceMember(member, typeBuilder, ref siteCounter);
    }
}

Besides the base class set through SetParent, all interfaces end up as base types (in CLI-style speak) and make up the type definition. For every to-be-implemented interface we finally implement every single member in it (otherwise the type would, naturally, be invalid and the CLR would refuse to new it up in the CreateType call). Notice the AddInterfaceImplementation will require the interface to be public as it will be part of another dynamically generated assembly, which is another limitation to our duck taper implementation, since such a weak contract interface is not really meant to be public in most circumstances. Oh well…

 

Where IL generation kicks in

ImplementConstructor and ImplementInterfaceMember are the remaining pieces of code needed in order to make up the thunk type definition at runtime. The constructor is almost a triviality: simply call the base constructor on Dynamic and return:

/// <summary>
/// Implements the constructor for a thunk type definition.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
private static void ImplementConstructor(TypeBuilder typeBuilder)
{
    //
    // public <class>(object @object) : base(@object)
    // {
    // }
    //
    ConstructorBuilder ctorBuilder = typeBuilder.DefineConstructor(MethodAttributes.Public | MethodAttributes.HideBySig | MethodAttributes.SpecialName | MethodAttributes.RTSpecialName, CallingConventions.Standard, new Type[] { typeof(object) });
    ILGenerator ctorILGen = ctorBuilder.GetILGenerator();
    ctorILGen.Emit(OpCodes.Ldarg_0);
    ctorILGen.Emit(OpCodes.Ldarg_1);
    ctorILGen.Emit(OpCodes.Call, typeof(Dynamic).GetConstructor(BindingFlags.Instance | BindingFlags.NonPublic, null, new Type[] { typeof(object) }, null));
    ctorILGen.Emit(OpCodes.Ret);
}

Recall the zero’th argument on an instance method represents the current instance, so Ldarg_1 and above fetch the real arguments. The base constructor we’re calling takes the same argument, i.e. the wrapped object. Ultimately, AsIf calls this constructor passing in the target object that needs to be AsIf’d:

//
// Create and return the thunk instance.
//
return (T)Activator.CreateInstance(thunkType, target);

Now the real work: ImplementInterfaceMember. Here we dispatch based on the type of the member to be implemented:

/// <summary>
/// Implements the specified <paramref name="member">interface member</paramref>.
/// </summary>
/// <param name="member">Member to generate an implementation for.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterfaceMember(MemberInfo member, TypeBuilder typeBuilder, ref int siteCounter)
{
    switch (member.MemberType)
    {
        case MemberTypes.Method:
            ImplementInterfaceMethod(member as MethodInfo, typeBuilder, ref siteCounter);
            break;
        case MemberTypes.Property:
            ImplementInterfaceProperty(member as PropertyInfo, typeBuilder, ref siteCounter);
            break;
        case MemberTypes.Event:
            ImplementInterfaceEvent(member as EventInfo, typeBuilder, ref siteCounter);
            break;
        case MemberTypes.NestedType:
            //
            // Nested interfaces are supported in VB. We ignore the nested interfaces and just implement the top-level interface.
            // This is fine as the nested interface isn't really part of the outer contract (and not an implementation requirement
            // in terms of CLI), but is merely a syntactic convenience method to structure types that belong together.
            //
            break;
        default:
            throw new InvalidOperationException("Unexpected interface member type encountered: " + member.MemberType);
    }
}

I won’t cover all of the three member types individually here. The key take-away is that all are implemented very similarly and ultimately resort to the implementation of methods (properties have getters and setters, events have adders and removers), all of which are the same:

  • A call site field.
  • Code to ensure the call site field is initialized (lazy on-demand call site creation) and to call through it.

 

How to dispatch calls?

The code to dispatch a call isn’t that hard either, but let’s introduce it piece-meal:

/// <summary>
/// Emits a thunk method with the specified <paramref name="methodName">name</paramref>, <paramref name="parameterTypes">parameter types</paramref> and <paramref name="returnType">return type</paramref>.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="methodName">Name for the generated method.</param>
/// <param name="parameterTypes">Parameter types for the generated method, or an empty array for no parameters.</param>
/// <param name="returnType">Return type for the generated method. Use typeof(void) for a void-returning method.</param>
/// <param name="targetMethodName">Target method name to call on the object being thunked.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
/// <param name="specialName">Indicates whether or not the emitted method should be marked as a special name method. Used for properties and events.</param>
/// <returns>Method builder for the generated method.</returns>
private static MethodBuilder EmitMethod(TypeBuilder typeBuilder, string methodName, Type[] parameterTypes, Type returnType, string targetMethodName, ref int siteCounter, bool specialName)
{
    //
    // Method attributes.
    //
    MethodAttributes attributes = MethodAttributes.Public | MethodAttributes.HideBySig | MethodAttributes.NewSlot | MethodAttributes.Virtual | MethodAttributes.Final;
    if (specialName)
        attributes |= MethodAttributes.SpecialName;

Notice draw the distinction between method name and target method name. The former is the one that needs to be implemented on the generated thunk, i.e. the one used in the interface, while the latter denotes the target to call on the wrapped object. This opens up for the possibility to have target method mappings using custom attribute metadata:

public interface IFoo
{
    [TargetMember("Fo")]
    int Foo { get; set; }
}

I won’t elaborate on this mechanism as it’s pretty straightforward to implement, refer to the code for more information. Back to our EmitMethod definition, focusing on a few remaining interesting arguments:

  • siteCounter is used to number the call site fields on the thunk type; as all our methods here are static we’re threading this around (an attractive alternative in case we’d have more state to drag around would be to have a ThunkBuilder class);
  • specialName is set to true for “special name methods” such as getters, setters, adders and removers.

Other metadata flags have to do with the vtable dispatching (NewSlot, Virtual) and such. Again, for more information, refer to the CLI spec ECMA 335. Now we start to build the real code:

//
// Define the method.
//
MethodBuilder methodBuilder = typeBuilder.DefineMethod(methodName, attributes, CallingConventions.HasThis, returnType, parameterTypes);
ILGenerator methodILGen = methodBuilder.GetILGenerator();

//
// Get method header to retrieve a reference to the call-site for this method.
//
FieldBuilder callSiteField = EmitGetCallSite(typeBuilder, ref siteCounter, targetMethodName, methodILGen);

First we declare the method, with HasThis calling convention (we’re writing an instance method, so the first argument is to be treated as “this”) and the indicated signature. The first thing we do is emitting the code responsible to ensure the call site object is not null and to create the backing field for it. First the field generation:

/// <summary>
/// Declares a call-site field associated with the target interface method and emits the code for retrieval of the call-site field in the method being generated.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
/// <param name="targetMethodName">Target method name for the method to dispatch to.</param>
/// <param name="methodILGen">IL generator for the method being generated.</param>
/// <returns>Field builder for the emitted call-site field.</returns>
private static FieldBuilder EmitGetCallSite(TypeBuilder typeBuilder, ref int siteCounter, string targetMethodName, ILGenerator methodILGen)
{
    //
    // Add call-site field.
    //
    FieldBuilder callSiteField = GetNewCallSiteField(typeBuilder, ref siteCounter);

    //
    // Ensure the call-site is initialized.
    //
    EmitCallSiteNullCheckAndInit(callSiteField, targetMethodName, methodILGen);

    //
    // Return field for further reference.
    //
    return callSiteField;
}
/// <summary>
/// Defines a new call-site field.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
/// <returns>New call-site field.</returns>
private static FieldBuilder GetNewCallSiteField(TypeBuilder typeBuilder, ref int siteCounter)
{
    return typeBuilder.DefineField("_site" + (++siteCounter), typeof(CallSite), FieldAttributes.Private);
}

Here we add a field to our type and increment our global site counter. Now we can refer to it in our method to ensure the field is initialized before calling the Invoke delegate:

/// <summary>
/// Emits code to populate the specified <paramref name="callSiteField">call-site field</paramref> (if not done already) and to retrieve it.
/// </summary>
/// <param name="callSiteField">Call-site field to populate and retrieve.</param>
/// <param name="methodName">Name for the method being generated.</param>
/// <param name="methodILGen">IL generator for the method being generated.</param>
private static void EmitCallSiteNullCheckAndInit(FieldBuilder callSiteField, string methodName, ILGenerator methodILGen)
{
    //
    // if (<callSiteField> == null)
    //     <callSiteField> = base.GetCallSite(<methodName>);
    //
    Label makeCall = methodILGen.DefineLabel();
    methodILGen.Emit(OpCodes.Ldarg_0);
    methodILGen.Emit(OpCodes.Ldfld, callSiteField);
    methodILGen.Emit(OpCodes.Brtrue, makeCall);
    methodILGen.Emit(OpCodes.Ldarg_0);
    methodILGen.Emit(OpCodes.Ldarg_0);
    methodILGen.Emit(OpCodes.Ldstr, methodName);
    methodILGen.Emit(OpCodes.Call, typeof(Dynamic).GetMethod("GetCallSite", BindingFlags.Instance | BindingFlags.NonPublic, null, new Type[] { typeof(string) }, null));
    methodILGen.Emit(OpCodes.Stfld, callSiteField);

    //
    // Target of conditional jump in case call-site was already initialzed; fall-through otherwise.
    //
    methodILGen.MarkLabel(makeCall);
}

Recall our (simplistic) GetCallSite method on Dynamic? Here we call this one in case the current call site field is null. The generated IL goes as follows (_|_ stands for bottom of the stack frame, { … } indicates equivalent C# code executed at that point):

    ldarg_0                      // _|_, this
    ldfld _site1                 // _|_, this._site
    brtrue MakeCall              // _|_  { if (this._site != null) goto MakeCall }
    ldarg_0                     // _|_, this
    ldarg_0                      // _|_, this, this
    ldstr “TargetMethod”         // _|_, this, this, “TargetMethod”
    callvirt Dynamic.GetCallSite // _|_, this, base.GetCallSite(“TargetMethod”)
    stfld _site1                 // _|_  { this._site = base.GetCallSite(“TargetMethod”) }

MakeCall:
    …

Next comes the real work, where we pack up the arguments for the member call and dispatch to our Invoke delegate on the CallSite object. Recall the Invoke delegate is our source of major flexibility: here we yield control to the CallSite implementation to do whatever it sees fit to make the call as efficient as possible. For instance, if it comes to the conclusion you’re invoking a statically defined member on an object, there’s no good reason not to cache the invocation path, maybe on its turn by means of IL generation in a DynamicMethod. We’re lame though and just implement the bare minimum dispatch mechanism, but we still need to make sure we get there, so that’s where calling through the delegate comes in, continuing in our EmitMethod implementation. First we get the delegate:

//
// Func<object[], object> <invoke> = <callSiteField>.Invoke;
//
methodILGen.Emit(OpCodes.Ldarg_0);
methodILGen.Emit(OpCodes.Ldfld, callSiteField);
methodILGen.Emit(OpCodes.Callvirt, typeof(CallSite).GetProperty("Invoke").GetGetMethod());

or, in terms of the generated IL,

    ldarg_0                      // _|_, this
    ldfld _site1                 // _|_, this._site
    callvirt get_Invoke          // _|_, base.Invoke

We even don’t store the delegate instance in a local variable and just keep it on top of our stack. Next we need to pack the arguments to our method in an object array that becomes the argument to the call through Invoke. This is a bit tricky as we might have value types that need to get boxed.

//
// object[] <args> = new object[<number_of_params>];
//
LocalBuilder args = methodILGen.DeclareLocal(typeof(object[]));
methodILGen.Emit(OpCodes.Ldc_I4, parameterTypes.Length);
methodILGen.Emit(OpCodes.Newarr, typeof(object));
methodILGen.Emit(OpCodes.Stloc, args);

//
// <args>[0] = <param_1>;
// <args>[1] = <param_2>;
// ...
// <args>[n] = <param_n+1>;
//
int i = 0;
foreach (Type paramType in parameterTypes)
{
    methodILGen.Emit(OpCodes.Ldloc, args);
    methodILGen.Emit(OpCodes.Ldc_I4, i);
    methodILGen.Emit(OpCodes.Ldarg, i + 1);
    if (paramType.IsValueType)
        methodILGen.Emit(OpCodes.Box, paramType);
    methodILGen.Emit(OpCodes.Stelem_Ref);
    i++;
}

First we declare a local of type object[]. We need this one as we constantly need to load it to store the arguments in one-by-one in the foreach loop below. The dimension of the array is determined by the number of parameters on the member. For methods this count is trivial, for property setters this will include the “value” parameter but also all of the possible indexer arguments. However, we don’t see those complexities in EmitMethod, so I’ll elaborate on this a little further. The IL to create the array and store it in the local variable should be clear. Next we iterate over all of the parameters and implement code to fetch the corresponding argument from the current method call and stick it in the array. Notice the ldarg instruction:

methodILGen.Emit(OpCodes.Ldarg, i + 1);

Here we use i + 1, as the first argument to the method call will be the this pointer and we don’t need that one as an argument to our dispatched method call. Another point of attention is the conditional emission of a boxing instruction when adding a value type to the parameters array. Here’s a typical run in IL including stack transitions, for a method call to Bar(string name, int age):

    ldc_i4 2                     // _|_, 2
    newarr                       // _|_, new object[2]
    stloc args                   // _|_ { args = new object[2] }
    ldloc args                   // _|_, args
    ldc_i4 0                     // _|_, args, 0
    ldarg 1                      // _|_, args, 0, name
    stelem_ref                   // _|_ { args[0] = name }
    ldloc args                   // _|_, args
    ldc_i4 1                     // _|_, args, 1
    ldarg 2                      // _|_, args, 1, age
    box                          // _|_, args, 1, (object)age
    stelem_ref                   // _|_ { args[1] = (object)age }

Now we have packed up the arguments to the call, the next step is to call through the delegate to dispatch the call to the target method through the CallSite thunking mechanisms. The code to emit the IL is very simple:

//
// object <res> = <invoke>(<args>);
//
methodILGen.Emit(OpCodes.Ldloc, args);
methodILGen.Emit(OpCodes.Callvirt, typeof(Func<object[], object>).GetMethod("Invoke"));

which simply calls the delegate’s Invoke method. Finally, if the method is not void-returning, we need to bubble up the return value to the caller, possibly unboxing the return value in case it’s a value type (as the delegate returns us an object). The pop instruction below is required to keep the stack balanced (in the case of ret from a void method):

//
// return <res>;
//
if (returnType != typeof(void))
{
    if (returnType.IsValueType)
        methodILGen.Emit(OpCodes.Unbox_Any, returnType);
}
else
    methodILGen.Emit(OpCodes.Pop);

methodILGen.Emit(OpCodes.Ret);

return methodBuilder;

That’s it – we now how our IL tool arsenal ready to dispatch any call to the underlying object.

 

How to deal with properties and events

Properties and events are just a little more than regular methods – they also have metadata containing type information and references to the associated methods. If you wonder about indexers, they’re merely the same as properties but with additional arguments. As events are quite similar to properties, we’ll just stick with properties. In a top-down approach, we start by creating a PropertyBuilder:

/// <summary>
/// Implements the specified <paramref name="propertyInfo">property</paramref>.
/// </summary>
/// <param name="propertyInfo">Property to generate an implementation for.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterfaceProperty(PropertyInfo propertyInfo, TypeBuilder typeBuilder, ref int siteCounter)
{
    //
    // Reconstruction of the signature.
    //
    Type returnType = propertyInfo.PropertyType;
    Type[] parameterTypes = propertyInfo.GetIndexParameters().Select(parameter => parameter.ParameterType).ToArray();

    //
    // Get the full name for the member.
    //
    string propertyName = GetTargetMemberName(propertyInfo);

    //
    // Define the property.
    //
    PropertyBuilder propertyBuilder = typeBuilder.DefineProperty(propertyName, PropertyAttributes.None, returnType, parameterTypes);

    //
    // Getter.
    //
    if (propertyInfo.CanRead)
        ImplementInterfacePropertyGetter(propertyInfo, typeBuilder, propertyBuilder, parameterTypes, ref siteCounter);

    //
    // Setter.
    //
    if (propertyInfo.CanWrite)
        ImplementInterfacePropertySetter(propertyInfo, typeBuilder, propertyBuilder, parameterTypes, ref siteCounter);
}

First we determine the “signature of the property”, which is relevant for indexed properties (indexers in C# lingo). Next, we perform the mapping between the interface member and the underlying property name to dispatch to. In the regular case this will be a one-on-one mapping, but using TargetMemberAttribute one can change that default:

public interface IFoo
{
    [TargetMember("Fo")]
    int Foo { get; set; }
}

GetTargetMemberName is the one that performs this mapping resolution using custom attributes. Finally we define the property and add a getter and/or setter to it depending on what the interface requires. Here we get in the terrain of our old EmitMethod friend, but with some intermediate work left to do in order to resolve the underlying method name (like get_, set_, etc):

/// <summary>
/// Emits the method definition for a property getter.
/// </summary>
/// <param name="propertyInfo">Property to generate a property getter implementation for.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="propertyBuilder">Property builder to associate the getter method with.</param>
/// <param name="parameterTypes">Parameters used for indexed properties, or an empty array for regular properties.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterfacePropertyGetter(PropertyInfo propertyInfo, TypeBuilder typeBuilder, PropertyBuilder propertyBuilder, Type[] parameterTypes, ref int siteCounter)
{
    const string GETPREFIX = "get_";

    //
    // Get thunk-to-target name mapping.
    //
    string methodName;
    string targetMethodName;
    GetMethodNamesForThunkAndTarget(propertyInfo, GETPREFIX, out methodName, out targetMethodName);

    //
    // Emit the getter.
    //
    MethodBuilder methodBuilder = EmitMethod(typeBuilder, methodName, parameterTypes, propertyBuilder.PropertyType, targetMethodName, ref siteCounter, true);

    //
    // Set the getter.
    //
    propertyBuilder.SetGetMethod(methodBuilder);
}

The only piece of glue here is a method called GetMethodNamesForThunkAndTarget that constructs the names of both the source method (e.g. get_Price, on the interface) and the target method (e.g. get_UnitPrice, on the target object). One other relevant thing here is the last parameter to EmitMethod, which is set to true, indicating the fact the emitted method is a “special name” one.

 

What’s the result?

To make all this IL voodoo concrete, here’s the corresponding C# code for the class generated on our original sample:

IDuck duck = dynamicDuck asif {
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
};

becomes

IDuck duck = new <>__Thunks.IDuck(dynamicDuck);

where

namespace <>__Thunks
{
    public sealed class IDuck : Dynamic, TheNamespaceWhereIDuckLives.IDuck
    {
        public IDuck(object o) : base(o) { }

        private CallSite _site1;

        public void Walk()
        {
            if (_site1 == null)
                _site1 = base.GetCallSite(“Walk”);
            _site1.Invoke(new object[0]);
        }

        private CallSite _site2;

        public void Walk(int steps)
        {
            if (_site2 == null)
                _site2 = base.GetCallSite(“Walk”);
            _site2.Invoke(new object[] { steps });
        }

        private CallSite _site3;

        public object Quack(string name)
        {
            if (_site3 == null)
                _site3 = base.GetCallSite(“Quack”);
            return _site3.Invoke(new object[] { name });
        }

        private CallSite _site4;
        private CallSite _site5;

        public ConsoleColor Color
        {
            get
            {
                if (_site4 == null)
                    _site4 = base.GetCallSite(“get_Color”);
                return _site4.Invoke(new object[0]);
            }

            set
            {
                if (_site5 == null)
                    _site5 = base.GetCallSite(“set_Color”);
                return (ConsoleColor)_site5.Invoke(new object[] { value });
            }
        }

        private CallSite _site6;
        private CallSite _site7;

        public EventHandler Walking
        {
            add
            {
                if (_site6 == null)
                    _site6 = base.GetCallSite(“add_Walking”);
                _site6.Invoke(new object[] { value });
            }

            remove
            {
                if (_site7 == null)
                    _site7 = base.GetCallSite(“remove_Walking”);
                _site7.Invoke(new object[] { value });
            }
        }
    }
}

 

How’s performance doing?

Now that we have our new toy, time to evaluate how we’re doing at this stage from a performance point of view. Before we discuss though, it’s important to emphasize the fact we’re focusing on a dynamic casting operation, i.e. it should work regardless of the object passed in (assuming that method implements the right members). What we have now is a degenerate case though, where we have CallSites that are only aware about the possibility to dispatch to a static type in a late-bound way. Additional tests, such as checking for expandos or IDynamicObjects, would be required to get the desired level of flexibility and will definitely incur a runtime cost. However, with our simplified code we can set a baseline on what to expect.

Here’s a very simple test that compares the performance of calling through a vtable directly based on static type knowledge, versus dispatching through our duck taper:

static void TestDucks()
{
    MeasureDuckPerformance("Static duck", () => new Duck2());
    MeasureDuckPerformance("Dynamic duck", () => GetDuck().AsIf<IDuck>());
}

static void MeasureDuckPerformance(string description, Func<IDuck> duckGetter)
{
    TimeSpan performance = DuckTest(duckGetter, 10000, duck =>
    {
        duck.Color = ConsoleColor.Blue;
        duck.Walking += duck_Walking;
        duck.Walk();
        duck.Quack("Bart");
        duck.Walk(3);
        duck.Walking -= duck_Walking;
    });

    Console.WriteLine(description + ": " + performance);
}

static TimeSpan DuckTest(Func<IDuck> duckGetter, int count, Action<IDuck> duckTest)
{
    IDuck duck = duckGetter();

    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < count; i++)
        duckTest(duck);
    sw.Stop();

    return sw.Elapsed;
}

The results looks as follows:

Dynamic duck: 00:00:01.1504488
Static duck: 00:00:02.2274213

A factor two the difference, not too bad after all. This should be enough to satisfy our curiosity around dynamic dispatch mechanisms. There’s a lot of additional possibilities here, ranging from controlling dispatch behavior (early or late binding), optimizing with caching strategies, and so on. In future posts I might delve into the details of more flexible dispatching mechanisms, advanced ways to do caching and the technique of implementing “fast paths”. But then I might as well start talking about the crossroads where DLR and C# 4.0 meet, and we’re back to our promise: “why this is not a C# 4.0 blog post”.

Have fun!

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

After named parameters and optional parameters, we'll take a little breadth and deviate a bit from the language specifics to present a new LINQ operator: Zip. Just like a zipper zips two streams of materials together, LINQ's Zip operator can zip together two sequences. Here's the signature of the new method:

public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func);

 

Sample

Given two sequences and a function that combines two elements from both sequences, a sequence of zipped pairs is produced. Here's a sample:

string[] names = { "Bart", "John" };
int[] ages = { 25, 60 };

names.Zip(ages, (name, age) => name + " is " + age + " years old.");

This produces a sequence with the sentences "Bart is 25 years old." and "John is 60 years old.". The lambda syntax for the passed-in function should speak for itself, and notice we're using extension method invocation here, so names is propagated to become the left-hand side of the method call.

 

How Zip works

Previously I've implemented the Standard Query Operators for reference purposes on the Codeplex site at http://www.codeplex.com/LINQSQO. I won't update that sample library just yet, but here's an illustration on how easy Zip is to implement, ignoring exception handling (which is more subtle than you might think, see further):

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();

        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

The Zip operation is implemented using iterators inside ("yield return") and stops as soon as one of the sequences runs out of juice (the case of the asymmetric zipper).

 

Zip without Zip?

As a curiosity, is it actually possible to build Zip out of existing LINQ operators, ignoring performance worries? Unsurprisingly, it turns out this is the case. Here's how:

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        return first.Select((x, i) => new { X = x, I = i }).Join(second.Select((x, i) => new { X = x, I = i }), o => o.I, i => i.I, (o, i) => func(o.X, i.X));
    }
}

(Exercise for the reader: think of more alternatives.) How does this work? To explain this we need a bit of vocabulary, so let's refer to Wikipedia for a second and apply an isomorphism between textile sciences and computer sciences (something in me screams "zip, zipper, zippest"):

The bulk signature of a zipper Zip consists of two strips sequences of fabric element taypes, each affixed to one of the two pieces sequence instances to be joined, carrying tens or hundreds or anything below OutOfMemoryException conditions of specially regularly shaped allocated metal reference- or plastic value-typed teeth elements. (...) The slider Func<TFirst, TSecond, TResult> delegate, operated by hand executing Zip, moves along the rows sequences of teeth elements. Inside the slider Func<TFirst, TSecond, TResult> delegate is a Y-shaped strongly-typed channel function that meshes together or separates the opposing rows sequences of teeth elements, depending on the direction of its movement. The friction binding and vibration application of the slider Func<TFirst, TSecond, TResult> delegate against on the teeth elements causes a characteristic buzzing callvirt'ing noise, which is probably not the origin of the name zipper. The name also may have originated in the greater speed and ease with which the two sides of a zipper Zip can be joined, compared to the time needed for fastening executing laces or buttons the method above.

Well, that's exactly what happens: opposing rows sequences of teeth elements are combined by a Y-shaped strongly-typed channel function. How to determine opposing sequence elements? Using Select's overload that provides (besides the element itself) an index denoting the element's position in the original sequence. Matching the opposing elements is a matter of joining both sequences, extracting the keys (marked as I in the anonymous type) and combining the selected pairs of elements from both sequences (marked as X in the anonymous type) by feeding them in to the slider Func<TFirst, TSecond, TResult> delegate. I told you the explanation was straightforward, or did I?

 

Iterators and exceptions

Most of the LINQ operators are implemented using iterators. You might wonder this this is relevant at all. Obviously we need it as LINQ operators need to be lazy. Only when you start fetching results by iterating of the sequence, the internal machinery should kick in. Declaring a query doesn't cause any execution whatsoever. Internally iterators are implemented as state machines. Every state can do on "yield", after which the state machine is suspended till the consumer asks for the next element in the sequence being produced by calling MoveNext on the IEnumerator<T> object.

Our Zip implementation above is turned into an equivalent piece of code (slightly simplified for illustrative purposes):

public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
{
    return new ZipIterator<TFirst, TSecond, TResult>(first, second, func);
}

private sealed class ZipIterator<TFirst, TSecond, TResult> : IEnumerable<TResult>, IEnumerator<TResult>
{
    //
    // Captured iterator method parameters.
    //

    private IEnumerable<TFirst> _first;
    private Func<TFirst, TSecond, TResult> _func;
    private IEnumerable<TSecond> _second;

    //
    // Iterator's enumerator state and thread affinity.
    //

    private State _state;
    private int _initialThreadId;

    //
    // Value currently yielded by the iterator's enumerator.
    //

    private TResult _current;

    //
    // Local variables used by the iterator's enumerator.
    //
    private IEnumerator<TFirst> _ieFirst;
    private IEnumerator<TSecond> _ieSecond;

    //
    // Captured iterator method parameters used by enumerator.
    //
    private IEnumerable<TFirst> first;
    private Func<TFirst, TSecond, TResult> func;
    private IEnumerable<TSecond> second;

    //
    // Public constructor to create an iterator in the initial ready state.
    //
    public ZipIterator(IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
        : this()
    {
        this._first = first;
        this._second = second;
        this._func = func;
    }

    //
    // Private constructor to set state and thread affinity.
    //
    private ZipIterator()
    {
        this._state = State.Before;
        this._initialThreadId = Thread.CurrentThread.ManagedThreadId;
    }

    //
    // Gets a new enumerator over the iterator.
    //
    IEnumerator<TResult> IEnumerable<TResult>.GetEnumerator()
    {
        ZipIterator<TFirst, TSecond, TResult> iterator;

        //
        // Can reuse the current enumerator if thread affinity and state permit it.
        //
        if (Thread.CurrentThread.ManagedThreadId == _initialThreadId && _state == State.Before)
        {
            iterator = this;
        }
        else
        {
            iterator = new ZipIterator<TFirst, TSecond, TResult>();
        }

        iterator.first = this._first;
        iterator.second = this._second;
        iterator.func = this._func;

        return iterator;
    }

    //
    // Gets a new enumerator over the iterator.
    //
    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<TResult>)this).GetEnumerator();
    }

    //
    // Advances the iterator one yield return at a time.
    //
    bool IEnumerator.MoveNext()
    {
        switch (this._state)
        {
            case State.Before:
                this._ieFirst = this.first.GetEnumerator();
                this._ieSecond = this.second.GetEnumerator();
                goto case State.Suspended;

            case State.Suspended:
                if (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
                {
                    this._current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                    this._state = State.Suspended;
                    return true;
                }

                break;
        }

        this._state = State.After;
        return false;
    }

    //
    // Retting the iterator enumerator is not supported; create a new one instead by calling GetEnumerator.
    // The foreach statement does this anyway.
    //
    void IEnumerator.Reset()
    {
        throw new NotSupportedException();
    }

    //
    // Gets the value currently yielded from the iterator.
    //
    TResult IEnumerator<TResult>.Current
    {
        get
        {
            return _current;
        }
    }

    //
    // Gets the value currently yielded from the iterator.
    //
    object IEnumerator.Current
    {
        get
        {
            return _current;
        }
    }

    //
    // IDisposable implementation.
    //
 
   void IDisposable.Dispose()
    {
    }

    //
    // Internal iterator enumerator states.
    //
    private enum State
    {
        Before,
        Running,
        Suspended,
        After
    }

}

Notice that the code above holds the middle between the specification (paragraph 10.14 of the C# 3.0 specification) and the actual implementation in the Visual C# 2008 compiler. More specifically, I've made the discrete states (which are internally represented as integers) match the ones in the specification, but haven't gone all the way in matching the code up with the

Of all this machinery, the MoveNext method is the most interesting one from the iterator's point of view. Here a state machine is built, rewriting the original iterator block by splitting it into discrete blocks. To perform this transformation, yield return statements are replaced as follows:

 yield a;

becomes

this._current = a;
this._state = State.Suspended;
return true;

Similar rewrites happen for yield break statements, but that's not relevant here. Furthermore all the iterator block code is placed in a MoveNext method, switching on the current state. The specification only mentions the four states I've implemented above, but we're lucky the number of states for our sample matches up with the number of states that's specified. In cases where there are more yield statements, more states are needed to suspend the machine and resume at the same point during the next MoveNext call. Other transformations needed include rewriting of loops (things like while don't really play well with suspension points and need to be rewritten in terms of if/goto, where gotos require additional states). Applying all those tricks gives us:

bool IEnumerator.MoveNext()
{
Begin:
    switch (this._state)
    {
        case State.Before:
            this._ieFirst = this.first.GetEnumerator();
            this._ieSecond = this.second.GetEnumerator();
            this._state = State.Running;
            goto Begin;

        case State.Running:
        case State.Suspended:
            if (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
            {
                this._current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                this._state = State.Suspended;
                return true;
            }

            break;
    }

    this._state = State.After;
    return false;
}

Here the local variables used in the iterator block are captured in the initial pass through MoveNext, when state is still set to Before. Strictly speaking we move from Before to Running all the way to the first point where the code gets suspended, but in our case states can be merged quite a bit. In fact the code really produced by the compiler looks like this:

bool IEnumerator.MoveNext()
{
    switch (this._state)
    {
        case 0:
            this._state = -1;
            this._ieFirst = this.first.GetEnumerator();
            this._ieSecond = this.second.GetEnumerator();
            while (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
            {
                this.current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                this._state = 1;
                return true;
            Resume:
                this._state = -1;
            }
            break;

        case 1:
            goto Resume;
    }
    return false;
}

But why am I telling you all this? Because it's fascinating? Yes, for that reason too. But I promised to tell you something about exceptions, right? Let me quote from the C# 3.0 specification paragraph 10.14.4.1 first:

(...) The precise action performed by MoveNext depends on the state of the enumerator object when MoveNext is invoked:

  • If the state of the enumerator object is 'before', invoking MoveNext:
    • Changes the state to 'running'.
    • Initializes the parameters (including this) of the iterator block to the argument values and instance value saved when the enumerator object was initialized.
    • Executes the iterator block from the beginning until execution is interrupted (as described below).

(...)

The red line is what's of interest to us, and you should read it in reverse:

The code from the beginning of the iterator block till the place where execution is interrupted (i.e. a yield occurs) is executed by MoveNext when transitioning from 'before' to 'running'.

What if that code contains exception throwing statements?

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        if (first == null)
            throw new ArgumentNullException("first");

        if (second == null)
            throw new ArgumentNullException("second");

        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();

        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

As you can guess, this code won't get executed till the very first passage through the iterator's enumerator object's MoveNext method. Recall what foreach corresponds to:

foreach (V v in x) embedded-statement

becomes (with C the collection type, E the enumerator type, V the local variable type and T the element type)

{
    E e = ((C)(x)).GetEnumerator();
    try {
        V v;
        while (e.MoveNext()) {
            v = (V)(T)e.Current;
            embedded-statement
        }
    }
    finally {
        ...
    }
}

So just calling the iterator does nothing that can cause the exceptions to be thrown, until a call is made to MoveNext, e.g. by using a foreach loop. As we want the exception to be thrown straight away when calling Zip with invalid arguments, the right way to implement our Zip method is:

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        if (first == null)
            throw new ArgumentNullException("first");

        if (second == null)
            throw new ArgumentNullException("second");

        return ZipInternal(first, second, func);
    }

    private static IEnumerable<TResult> ZipInternal<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {

        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();

        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

 

Conclusion

The addition of Zip to LINQ is a nice one, but not a mind-blower. So I hope you'll accept my apologies for using this as a lame excuse to nag about the implementation of iterators and their subtle impact on exceptions. Next time: generics co- and contra-variance in C# 4.0.

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

In the previous episode of this feature focus series we talked about optional parameters. Today we'll cover another feature introduced in C# 4.0, named parameters. One of the most applicable places for optional and named parameters is when dealing with COM interop such as interaction with the Office automation APIs, but they can also be used as a stand-alone language feature. Just like optional parameters, named parameters are a symmetric feature: you can both consume and declare them.

 

The syntax

Assume the following simple subtraction method is defined:

static int Subtract(int a, int b)
{
    return a - b;
}

The typical way to call this method is obviously by specifying the parameters in order, like Subtract(5, 3). However, with named parameters it's possible to write the following:

static void Main()
{
    Console.WriteLine(Subtract(b: 3, a: 5));
}

Ultimately this translates into a call to Subtract(5, 3). It's clear the sample above is not very realistic (but you have to admit it's simplistic). Typically named parameters are used where optional parameters appear in the target method, but you're not interested in lots of those:

static void Bar(int a = 1, string b = null, bool c = false)
{
    // ...
}

Now assume you're only interested in the last parameter, without the named parameter feature you'd have to write Bar(1, null, ...) but now you can go ahead and write:

Bar(c: true);

You might wonder why the syntax uses a colon (:) instead of an assignment equals character (=). The answer is straightforward: assignments have a value and can be used everywhere a value is expected:

bool c = false;
Bar(c = true);

This will assign true to the local variable c and feed that value in as the first argument of Bar. So colon is the way to go (and I'm not going to start religious debates about the spacing around the :, I'll leave that to the C/C++ community as those people are experienced in this kind of discussions, trying to reach an agreement on the totally irrelevant placing for the * character <g>).

 

The implementation

It should be clear that the implementation only affects the call site, not the caller. Here's how the Main method from above looks like:

.method private hidebysig static void  Main() cil managed
{
  .entrypoint
  // Code size       19 (0x13)
  .maxstack  2
  .locals init (int32 V_0,
           int32 V_1)
  IL_0000:  nop
  IL_0001:  ldc.i4.3
  IL_0002:  stloc.0
  IL_0003:  ldc.i4.5
  IL_0004:  stloc.1
  IL_0005:  ldloc.1
  IL_0006:  ldloc.0
  IL_0007:  call       int32 Program::Subtract(int32,
                                               int32)
  IL_000c:  call       void [mscorlib]System.Console::WriteLine(int32)
  IL_0011:  nop
  IL_0012:  ret
} // end of method Program::Main

First of all, notice the names of parameters don't appear in the call site in any way (they never have, that's not the way IL works). Ultimately we simply call Subtract with the parameters supplied in the right order. But how we get there is important to take a closer look at:

  IL_0001:  ldc.i4.3
  IL_0002:  stloc.0
  IL_0003: 
ldc.i4.5
  IL_0004:  stloc.1
  IL_0005: 
ldloc.1
  IL_0006:  ldloc.0

The thing to notice here are the mirrored stloc (store to local variable) versus ldloc (load from local variable) instructions. On lines IL_0002 and IL_0004 values are stored to variables 0 and 1, while on lines IL_0005 and IL_0006 they're read out in reverse order. What's happening here is that arguments to the method call are evaluated in lexical order, something that boils down to a one-liner in section 14.4.1 of the C# specification (ECMA-334):

14.4.1    Argument lists
...
The expressions of an argument list are always evaluated in the order they are written.

[Example: Thus, the example

class Test
{
  static void F(int x, int y, int z) {
    System.Console.WriteLine("x = {0}, y = {1}, z = {2}", x, y, z);
  }

  static void Main() {
    int i = 0;
    F(i++, i++, i++);
  }
}

produces the output

x = 0, y = 1, z = 2

end example]

This becomes relevant in the context of side-effects but it should be clear by now that it's better not to rely on those kind of side-effects at all. Nevertheless, consistency is a must and hence the named parameters invocation syntax follows those rules as well. Here's the new sample you can predict the output for based on the previous observations:

class Test
{
  static void F(int x, int y, int z) {
    System.Console.WriteLine("x = {0}, y = {1}, z = {2}", x, y, z);
  }

  static void Main() {
    int i = 0;
    F(z: i++, x: i++, y: i++);
  }
}

 

The caveat

This time the caveat is trivial: don't rename parameters on public methods as they might be used in conjunction with the named parameter feature. Here's a sample.

Step 1: Compile the following (csc /t:library namedlib.cs)

public static class NamedLib
{
    public static int Subtract(int a, int b)
    {
        return a - b;
    }
}

Step 2: Compile the following (csc named.cs /r:namedlib.dll)

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine(NamedLib.Subtract(b: 3, a: 5));
    }
}

Step 3: Run named.exe

> named.exe
2

Step 4: Change the library and recompile

public static class NamedLib
{
    public static int Subtract(int x, int y)
    {
        return x - y;
    }
}

Step 5: Recompile the application

named.cs(7,27): error CS1739: The best overload for 'Subtract' does not have a parameter named 'b'

Names matter. Obviously reordering parameters of the same type without recompiling consumers is a breaking change too (the types of the parameters in the signature doesn't change, so the overload is still valid but semantics of the parameters have changed), but that's unrelated to the use of named parameters.

 

Conclusion

Named parameters provide an easy way to omit ("skip over") optional parameters and are typically used in conjunction with that particular feature. However, they can be used in isolation as well. Once more, library designers should be cautious about messing with the public methods they provide. In particular, make sure names on publicly exposed methods are stable as changes to those have the potential of breaking callers. Another reason to spend time on XML documenting public members, as you'll double-check (I hope) the <param /> tag for its name.

Oh, and did you notice the parallels with concepts in PowerShell on positional and named cmdlet arguments? The only piece missing are aliases ;-).

Next time, before we dive into more language-specific features, a short intermezzo in LINQ with a new operator: Zip. Enjoy!

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

More Posts