What makes the pattern-matching mechanism so powerful in functional languages is its ability to match many sorts of data structures, amongst which are tuples.

Defining a match expression on a tuple or 2 values in F# can be done this way :

let result =
    match input with
    | 1, 1 -> 1
    | 2, _ -> 2
    | _, 3 -> 3
    | a, b when a > 4 -> 4
    | _ -> 5

This sample shows some interesting cases. A tuple of 2 values can be matched with several expressions, each value of the tuple being compared with individual patterns.

In part 1 of this series, we stated these individual patterns:

• a constant pattern,
• a conditional pattern,
• a default pattern, known as the wildcard pattern (the underscore in F#).

Now, we have to handle every possible combination of these patterns!

The following sample translated in C# in my experimental syntax is the following:

var tupleSample =
    PatternMatcher.CreateSwitch<int, int, int>()
    .Case(1         , 1, (a, b) => 1)
    .Case(2         , _, (a, b) => 2)
    .Case(_         , 3, (a, b) => 3)
    .Case(a => a > 4, _, (a, b) => 4)
    .Case(_         , _, (a, b) => 5);

Welcome to the parenthesis hell. Soon it will like like Lisp if we go on… But how do we enable that syntax ?

In order to handle gracefully the wildcard (“_”) pattern, I have used a non-generic MatchCase class with a static field called Any:

public class MatchCase
{
    public static readonly MatchCase Any;

    static MatchCase()
    {
        Any = new MatchCase();
    }

    private MatchCase()
    {
    }
}

This trick allows me to define methods with a MatchCase-typed parameter to handle the wildcard pattern case. Moreover, if I add the following line before my patterns definitions :

var _ = MatchCase.Any;

I’m then able to use a simple “_” to represent the “any” case.

The method used previously to build the pattern matching Func and its invocation in the Eval method doesn’t change: only the “recording” process is impacted. The pain point here is that we need to define each necessary overload of the Case extension method, in order to handle all the patterns. These extensions methods are all based on the following model:

public static PatternMatcher<Tuple<T1, T2>, TResult>
    Case<T1, T2, TResult>(
    this PatternMatcher<Tuple<T1, T2>, TResult> pattern,
    {arg1},
    {arg2},
    Expression<Func<T1, T2, TResult>> selector)

where the {arg1} and {arg2} placeholders are replaced with :

• T1 testValue1, T2 testValue2
• T1 testValue1, Expression<Func<T2, bool>> testExpression2
• T1 testValue1, MatchCase any2
• Expression<Func<T1, bool>> testExpression1, T2 testValue2
• Expression<Func<T1, bool>> testExpression1, Expression<Func<T2, bool>> testExpression2
• Expression<Func<T1, bool>> testExpression1, MatchCase any2
• MatchCase any1, T2 testValue2
• MatchCase any1, Expression<Func<T2, bool>> testExpression2
• MatchCase any1, MatchCase any2

The implementation of each method follows the same pattern as in the previous post, and builds an expression that determines whether a given tuple matches the pattern, returning, and evaluates the selector expression when there is a match.

But if we want to handle tuples with more values… do we have to write all the overloads ?!

In order to handle match expressions where none of the expressions would match a given candidate, I decided to use an option type. This allows the generation of this type of expressions:

Func<double, Option<double>> matchSomeOrNone =
    (double d) =>
        (d > 0.0)
        ? Option<double>.Some(d)
        : Option<double>.None();

Given this these options, the translation of last time’s sample code:

var stringPattern = PatternMatcher
    .CreateSwitch<string, double>()
    .Case("TEST"                        , s => Math.PI)
    .Case("TEST_1"                      , s => Math.E)
    .Case((string)null                  , s => 0.0)
    .Case(s => s.StartsWith("TEST__")   , s => Math.E * 2)
    .CaseElse(                            s => s.Length);

would become:

Func<string, Option<double>> generatedFuncOption =
    (string s) =>
        (s == "TEST")
            ? Option<double>.Some(Math.PI)
            : (s == "TEST_1")
                ? Option<double>.Some(Math.E)
                : (s == null)
                    ? Option<double>.Some(0.0)
                    : s.StartsWith("TEST__")
                        ? Option<double>.Some(Math.E * 2)
                        : Option<double>.Some(s.Length);

In order to instantiate option types in LINQ expressions, I have to use the corresponding MethodInfo instances, obtained from reflexion :

MethodInfo createSomeMethodInfo =
    typeof(Option<TResult>)
        .GetMethod(
            "Some",
            BindingFlags.Public | BindingFlags.Static);

MethodInfo createNoneMethodInfo =
    typeof(Option<TResult>)
        .GetMethod(
            "None",
            BindingFlags.Public | BindingFlags.Static);

And then, in order to finally build a matching expression, I loop over the match conditions and result selector expressions the following way:

private Func<TSource, Option<TResult>> BuildPatternMatchingFunc()
{
    ParameterExpression parameter =
        Expression.Parameter(typeof(TSource));

    Expression noneExpression = Expression.Call(
        createNoneMethodInfo);

    Expression caseExpression = noneExpression;

    foreach (var matchCase in this.cases.Reverse())
    {
        caseExpression =
            Expression.Condition(
                Expression.Invoke(
                    matchCase.TestExpression,
                    parameter),
                Expression.Call(
                    createSomeMethodInfo,
                    Expression.Invoke(
                        matchCase.SelectorExpression,
                        parameter)),
                caseExpression);
    }

    return Expression
        .Lambda<Func<TSource, Option<TResult>>>(
            caseExpression,
            parameter)
        .Compile();
}

The createNoneMethodInfo and createSomeMethodInfo are the MethodInfo corresponding to the generic Option<T>.None() and Option<T>.Some() methods obtained by reflection.

Debugging this kind of expression building can be complicated, particularly without the ability to visualize clearly the expression tree… Hopefully, I have built an expression tree visualizer in the past (I could also have used the easy path and install the classical one) ! From the C# sample again, I can produce the following expression tree:

This tree may seem wide, but is is just a succession of conditional expressions… Finally, the the function that evaluates the result of the pattern-matching expression is the following one:

public TResult Eval(TSource candidate)
{
    if (this.patternMatchingFunc == null)
    {
        this.patternMatchingFunc = BuildPatternMatchingFunc();
    }

    Option<TResult> matchResult = patternMatchingFunc
                                    .Invoke(candidate);

    if (!matchResult.IsSome)
        throw new NoMatchFoundException();

    return matchResult.Value;
}

As you can see, it’s a wrapper around the expression evaluation invocation. It first generates the expression  instantiates upon the first call (in a non-threadsafe way, but who cares !) and handles “nothing matches” case by throwing an exception. And this works !

Now, you might say that matching a single value in of very limited interest. I can’t deny it. Why don’t we try to match several values, then ?

let test str =
    match str with
    | "TEST" -> Math.PI
    | "TEST_1" -> Math.E
    | null -> 0.0
    | s when s.StartsWith("TEST__") -> Math.E * 2.0
    | s -> float s.Length

If we analyse these patterns, we see 3 different cases:

• a constant pattern (including the null value),
• a conditional pattern (the lambda one)
• a default pattern (the else case).

So in C#, what I’ve managed to build is the following:

var stringPattern = PatternMatcher
.CreateSwitch<string, double>()
.Case("TEST"                        , s => Math.PI)
.Case("TEST_1"                      , s => Math.E)
.Case((string)null                  , s => 0.0)
.Case(s => s.StartsWith("TEST__")   , s => Math.E * 2)
.CaseElse(                            s => s.Length);

What is difficult here is to write something that is valid C#, because:

1. I can’t change the compiler,
2. To keep things simple, I don’t want to use Roslyn in the first attempt (although that might come later).

Recording expressions for individual tests

This solution is mainly based upon a generic class called PatternMatcher<TSource, TResult>, which represents the match expression being built. Each Case overload builds an instance of a MatchCase class. As with many “fluent” syntax nowadays, in order to chain the calls in a single statement, each Case overload returns a new instance of the PatternMatcher, which keeps track of all the cases registered so far.

The MatchCase’s sole purpose is to encapsulate two expressions:

• a test expression that will be used to determine if a particular source value matches the case: this will be an expression of Func<TSource, bool>,
• a selector expression that will be used to produce the result of the match expression when the input value matches this particular case: this will be an expression of Func<TSource, TResult>.

Getting an Expression of a given Func type is nothing more that changing the type of a variable. The compiler will change its work accordingly, and produce an Expression from a given lambda-expression, instead of a typed delegate.

The most general case is the conditional pattern. Let’s take a look at the following extension method:

public static PatternMatcher<TSource, TResult>
    Case<TSource, TResult>(
        this PatternMatcher<TSource, TResult> pattern,
        Expression<Func<TSource, bool>> testExpression,
        Expression<Func<TSource, TResult>> selector)

You can see that the testExpression and selector parameters are already the types that my MatchCase class needs. From this values, I just have to instantiate the class and store it for later use.

The two other  cases (constant and default) will also provide directly the selector expression, only the test expression will have to be provided:

• as an expression that tests equality with a given constant, for the constant pattern,
• as an expression that is always true, for the default pattern.

These cases are just special cases of the previous one, called with an appropriate lambda, which will be converted to the test expression.

Building an expression tree

Of course, what we want to do is more that just record the expressions ! The next step is to combine them in a global match expression.

The kind of code I would like to produce, for the previous sample, would be the following:

Func<string, double> generatedFunc =
(string s) =>
    {
        if (s == "TEST") return Math.PI;
        if (s == "TEST_1") return Math.E;
        if (s == null) return 0.0;
        if (s.StartsWith("TEST__")) return Math.E * 2;
        return s.Length;
    };

Or even “better”, the same, but with conditional expressions instead of if and return statements:

Func<string, double> generatedFuncNoIf =
    (string s) =>
        (s == "TEST")
            ? Math.PI
            : (s == "TEST_1")
                ? Math.E
                : (s == null)
                    ? 0.0
                    : s.StartsWith("TEST__")
                        ? Math.E * 2
                        : s.Length;

An expression corresponding to the previous code could be generated, but I also want to handle an additional case: when there is no match. This means that my expression has to be able to return some result or… none. Some or none ? Isn’t there a type for that ? We’ll see how to use it next time.

[1] I know this sample is useless and theoretical, but isn’t this whole series ? If you really want to use match expressions, embrace F#, not C# !

What is pattern matching ?

From the MSDN entry on Pattern matching :

Patterns are rules for transforming input data. They are used throughout the F# language to compare data with a logical structure or structures, decompose data into constituent parts, or extract information from data in various ways.

The point I want to focus on is in fact the F# match expression. The match expression is a powerful way to express conditions over data. It is often described as a “switch statement on steroids”. Its characteristics are the following :

• Just like a switch, it takes a value as its input,
• Unlike a switch, the value is not limited only to enums or built-in value types.
• It has a return type. If there is nothing to return, F# uses a special unit type, but there is no void as a return type neither a null value.
• If the values to return can be of different types depending on the input, Discriminated Unions (DUs) can be used as return types.

I’ll start with a simple F# sample, to show what a discriminated union is :

type Shape =
    | Point
    | Circle of float
    | Rectangle of float * float

In this sample, a type Shape is defined, that can be either a Point, a Circle or a Rectangle. Although the Point could be considered a simple enum value, the Circle and Rectangle cases, unlike enums, carry data. For instance :

let p = Point
let c = Circle(5.0)
let r = Rectangle(10.0, 20.0)

If we want to extract the data components of a particular union type, we use pattern-matching in the following way :

let Rectangle(w, h) = r

This expression binds the value of w and h to the data elements of the r Rectangle defined earlier. But my purpose in the blog series is to introduce in C# a syntax that would look like a match expression, which in F# is the following :

let getArea s =
    match s with
    | Point -> 0.0
    | Circle(r) -> r * r * System.Math.PI
    | Rectangle(w, h) -> w * h

In this attempt, I first consider matching simple values (which has no practical interest of any sort), then matching tuples, and I’ll finish with matching against some sort of Discriminated Union, although DUs are not a native C# construct.

First, let’s consider what we want to build. From the sample above, we can see that what we get from the match expression is a “getArea” that takes an instance of the union type as input, and gives a float as output. As this is just the definition of a function, it looks like we’re trying to build a construct that generates instances of the generic Func<TInput, TOutput> delegate.

In F#, match expressions can also be used to perform actions, and in this case will return the special unit type. To perform actions in C# we have the Action<T> delegate type. In this series I’ll consider only the functions, but actions could be built exactly the same way.

In the next part, I’ll show my first naive attempt to deal with simple values, before targeting any tuples or discriminated union types.

I’ve already played with an Irreleventable<T> type in the past, and the implementation of it is quite the same as what I’ll do today, but the semantics are different, and I don’t want to re-use this type in a misleading way.

So today, I bring you “yet another option type” in C# :

public struct Option<T>
{
    private readonly bool isSome;
    public bool IsSome
    {
        get
        {
            return isSome;
        }
    }

    private readonly T value;
    public T Value
    {
        get
        {
            if (!isSome) throw new NotSupportedException();
            return value;
        }
    }

    private Option(bool isSome, T value)
    {
        this.isSome = isSome;
        this.value = value;
    }

    public static Option<T> Some(T value)
    {
        return new Option<T>(true, value);
    }

    public static Option<T> None()
    {
        return new Option<T>(false, default(T));
    }

    public override int GetHashCode()
    {
        return isSome
            ? value.GetHashCode()
            : -1;
    }

    public override bool Equals(object other)
    {
        if (!(other is Option<T>))
            return false;

        Option<T> otherOption = (Option<T>)other;

        return IsSome
            ? (value == null && otherOption.Value == null)
                || value.Equals(otherOption.Value)
            : !otherOption.IsSome;
    }

    public override string ToString()
    {
        return this.IsSome
            ? this.value.ToString()
            : String.Empty;
    }
}

The only noticeable differences with the Irreleventable type are the (chosen) lack of conversion operators, and the equality comparison, as an Option<T> will never be considered equal to an instance of T (unlike the Irreleventable).

Why would I write a blog post simply to introduce this type, without any context ? More to come soon.

One of the questions that was raised during the evening was the following : Is the “Software Craftsmanship” movement elitist or is it a way to democratize good practices ? After a great deal of discussion, we agreed on the fact that it can be seen the both ways. Let’s face it : we meet in the evening to talk about programming… We’re part of the “10 percent alpha-geeks”. And yes, there is some kind of elitism about it.

On one hand, to someone that comes for the first time, all the practices, languages and tools we talk about might seem too complex, and frighten him (or her). On the other hand, realizing that there are so many things that we don’t know is the first step to getting better, isn’t it ? To my mind, this whole question of “raising the bar” instead of letting the average level go low, is not specific to programming but is true for any kind of teaching/learning topic. What makes it so important in programming is that we can’t stop learning during our career, if we want to stay up-to-date…

But if our goal is to “raise the bar”, how do we do it on a day-to-day basis ? If we want to show our colleagues some tricks, so that they ask for more, not that they run away…

Let’s illustrate that with an example from real life. A couple days ago I wanted extract from several data series the dates that were common to all these series. This might seem quite simple, but there are numerous ways to do that, and I find it a good case study of how to balance readability and (perceived) complexity…

<YAK-SHAVING>My Visual Studio 2012 RC has expired… I’m switching to MonoDevelop in order to write my sample code…</YAK-SHAVING>

Let’s consider several collections of points, where a point is simply a date and a decimal value :

public class Point
{
    public DateTime Date { get; set; }
    public decimal Value { get; set; }
}

And now imagine that I have a collection of series of points, represented as such :

IEnumerable<IEnumerable<Point>> series

Now the point is to get the dates that are common to all these series. With a straight implementation, this could go this way :

[Test()]
public void TestStraightLoops()
{
    IEnumerable<IEnumerable<Point>> series =
        DataSeries.GetSeries(2013);

    List<DateTime> commonDates = new List<DateTime> ();
    bool first = true;
    foreach (var serie in series)
    {
        if(first)
        {
            foreach(var point in serie)
            {
                commonDates.Add(point.Date);
            }
        }
        else
        {
            List<DateTime> datesToRemove = new List<DateTime>();
            foreach(var commonDate in commonDates)
            {
                bool found = false;
                foreach(var point in serie)
                {
                    if(commonDate == point.Date)
                    {
                        found = true;
                        break;
                    }
                }

                if(!found)
                {
                    datesToRemove.Add(commonDate);
                }
            }

            foreach(var dateToRemove in datesToRemove)
            {
                commonDates.Remove(dateToRemove);
            }
        }
        first = false;
    }

    Assert.AreEqual(76, commonDates.Count);
}

OK, this works. How long does it take to read it and understand it ? What if, instead, I chose to use my basic knowledge of LINQ ? I’ll skip a few steps, but what if came up with this :

[Test()]
public void TestForEachIntersect ()
{
    IEnumerable<IEnumerable<Point>> series =
        DataSeries.GetSeries(2013);

    IEnumerable<DateTime> commonDates = null;

    foreach (var serie in series)
    {
        var dates = serie.Select(p => p.Date);

        commonDates = (commonDates == null)
            ? dates
            : commonDates.Intersect(dates);
    }

    Assert.AreEqual(76, commonDates.Count());
}

This is obviously shorter. Is it more or less difficult to read and maintain ? Should I stop here ? What if wrote the following, using Aggregate to do the same thing as above, but inside an extension method ?

public static IEnumerable<TResult> IntersectMany<T, TResult>
    (this IEnumerable<IEnumerable<T>> source,
     Func<T, TResult> selector)
{
    return source.Aggregate(
        (IEnumerable<TResult>)null,
        (a, s) => a == null
                ? s.Select(selector)
                : a.Intersect(s.Select(selector)));

}

Obviously this method is less readable… But the consumer code is now the following :

[Test()]
public void TestIntersectMany()
{
    IEnumerable<IEnumerable<Point>> series =
        DataSeries.GetSeries(2013);
    
    var commonDates = series
        .IntersectMany(p => p.Date);
    
    Assert.AreEqual(76, commonDates.Count());
}

And… I kind of like the expressiveness of it. So where must we stop ? To my mind, we must stop when it can be maintained. Aren’t we pragmatic programmers, after all ?

I think that Software Craftsmanship is very well summed-up in Sandro Mancuso’s book title : “Software Craftsmanship : Professionalism, Pragmatism, Pride”. Those words are in the right order. Pride is part of it, but it come only third.

Anyone bored and have an android phone?play.google.com/store/apps/det…

— Leonard Hofstadter (@TheRealLeonardH) November 22, 2012

If you follow the link, you’ll get to a Google Play application that allows you to play the (in-)famous RPSLS (Rock-paper-scissors-lizard-Spock) game. Why that tweet stroke me is that I had already played (with code !) around that game a few months ago…

Although this is just a variant of the classical rock-paper-scissors game, the two additional gestures shift the number of gesture combinations to 25, as shown on this matrix:

(image taken from http://en.wikipedia.org/wiki/File:Normal_form_matrix_of_Rock-paper-scissors-lizard-Spock.jpg)

There could be several ways to test these different combinations, for instance using the previous matrix as a reference, but… come on…. a closed set of values, and a simple behaviour… That’s just a perfect candidate for an enum ! And the best part is that I have actually implemented this as a test two months ago (proof on Github !).

Let’s first define the possible game outcomes :

public class GameOutcome : PolymorphicEnum<GameOutcome>
{
    public static GameOutcome WIN = Register();
    public static GameOutcome LOSE = Register();
    public static GameOutcome DRAW = Register();
}

Then we define the Gesture class and its values :

public class GeekGesture : PolymorphicEnum<GeekGesture>
{
    public static GeekGesture ROCK = Register();
    public static GeekGesture PAPER = Register();
    public static GeekGesture SCISSORS = Register();
    public static GeekGesture SPOCK = Register();
    public static GeekGesture LIZARD = Register();
    [...]

The trick here is that I changed the order of the values int the enum from Rock – paper – scissors – lizard – Spock to Rock – paper – scissors – Spock – lizard. This way, each values beats its predecessor and its second successor, and loses against its successor and second predecessor…

The behaviour can then be simply implemented based on the integer values of the enums :

// we can use the int representation and a modulo trick !
public GameOutcome PlayAgainst(GeekGesture other)
{
    return this == other
        ? GameOutcome.DRAW
        : (GameOutcome)(((other + 5 - this) % 5) % 2);
}

Now we can write the tests in a very expressive way :

[TestMethod]
public void gesture_against_2nd_next_is_a_win()
{
    Assert.AreEqual(GameOutcome.WIN,
        GeekGesture.ROCK.PlayAgainst(GeekGesture.SCISSORS));
    Assert.AreEqual(GameOutcome.WIN,
        GeekGesture.PAPER.PlayAgainst(GeekGesture.SPOCK));
    Assert.AreEqual(GameOutcome.WIN,
        GeekGesture.SCISSORS.PlayAgainst(GeekGesture.LIZARD));
    Assert.AreEqual(GameOutcome.WIN,
        GeekGesture.SPOCK.PlayAgainst(GeekGesture.ROCK));
    Assert.AreEqual(GameOutcome.WIN,
        GeekGesture.LIZARD.PlayAgainst(GeekGesture.PAPER));
}

So… here is my answer to Leonard :

@therealleonardh I have and android phone, but when I’m bored I think about software, and sometimes blog about it : pirrmann.net/rpsls-rock-pap…

— Pierre Irrmann (@pirrmann) November 22, 2012

var ints = Enumerable.Range(1, 4);
var longs = Enumerable.Range(1, 3).Select(i => (long)i);

var products = from i in ints
    from l in longs
    select i * l;

When I write LINQ queries, I tend to use more often the fluent syntax, as it is more powerful, and allows me to use a wider range of operators. I also try not to mix both syntaxes, because I find it quite confusing. When I want to perform, inside of a more complex query, a simple cross-product as the previous one, the “fluent” equivalent syntax is the following :

var products = ints.SelectMany(i => longs.Select(l => i * l));

In fact, this syntax works very well, but I don’t find it as expressive as the first one. And if you go one step further and add a third sequence to the party…

var ints = Enumerable.Range(1, 4);
var longs = Enumerable.Range(1, 3).Select(i => (long)i);
var strings = new[] { "a", "b", "c" };

var classic = from i in ints
    from l in longs
    from s in strings
    select (i * l).ToString() + s;

The “fluent” syntax gets even more confusing (at least to me) :

var fluent = ints.SelectMany(
    i => longs.SelectMany(
    l => strings.Select(s => (i * l).ToString() + s)));

I think that what bothers me might be the ever-increasing number of unclosed parenthesis… Anyway, as usual, I played with extensions methods and here is what I came up with, using a new “Cross” method, for the 2 sequences cross-product :

var results = ints
    .Cross(longs)
    .Select((i, l) => i * l);

And the same syntax for the 3 sequences cross product :

var results = ints
    .Cross(longs)
    .Cross(strings)
    .Select((i, l, s) => (i * l).ToString() + s);

Don’t you find it more expressive ?

Finally, here are the extensions methods implementations :

public static IEnumerable<Tuple<TLeft, TRight>> Cross<TLeft, TRight>(
    this IEnumerable<TLeft> left, IEnumerable<TRight> right)
{
    return left.SelectMany(l => right.Select(r => Tuple.Create(l, r)));
}

public static IEnumerable<Tuple<TLeft1, TLeft2, TRight>> Cross<TLeft1, TLeft2, TRight>(
    this IEnumerable<Tuple<TLeft1, TLeft2>> left, IEnumerable<TRight> right)
{
    return left.SelectMany(l => right.Select(r => Tuple.Create(l.Item1, l.Item2, r)));
}

public static IEnumerable<TResult> Select<T1, T2, TResult>(
    this IEnumerable<Tuple<T1, T2>> source, Func<T1, T2, TResult> selector)
{
    return source.Select(t => selector(t.Item1, t.Item2));
}

public static IEnumerable<TResult> Select<T1, T2, T3, TResult>(
    this IEnumerable<Tuple<T1, T2, T3>> source, Func<T1, T2, T3, TResult> selector)
{
    return source.Select(t => selector(t.Item1, t.Item2, t.Item3));
}

I must admit that those generic methods signatures are horrible, though…

In a previous post, as an answer to @cyriux’s one, I showed how we could try to use a polymorphic enum in C# in order to mimic the Java ones. I have ported to C# the Java samples, using a base class called PolymorphicEnum. In this post, I’m going to give details about the implementation of this class.

The very first objectives are :

1. To create an enum that derives from a base PolymorphicEnum.
2. This derived enum must be able to define a set of values.

Getting started

What I want to be able to write is something like :

public class SomeEnum : PolymorphicEnum
{
    public static SomeEnum FirstValue;
    public static SomeEnum SecondValue;
}

As I can’t change the compiler behaviour, the two values declared in the previous sample must be instantiated somehow. The declaration then becomes :

public class SomeEnum : PolymorphicEnum
{
    public static SomeEnum FirstValue = Register();
    public static SomeEnum SecondValue = Register();
}

In order to be able to write such code, here is what I can do :

1. First, the class I want to define is only meant to be derived from, so it must be abstract. Therefore, it can only be a class, and not a struct. So I’ll have to override the Equals and GetHashCode methods in order to get a value comparison behaviour for two different instances of enums. But if the singleton-ness is implemented properly… I should never have two instances !
2. The class will have a generic Ordinal read-only property, where T is a value type. If not provided, this type will be an int by default.
3. In order to instantiate enum values, the base class will have to expose a static protected method “Register”.

This leads us to this basic definition :

public abstract class PolymorphicEnum<T>
    where T : struct, IComparable<T>, IConvertible
{
    public T Ordinal { get; private set; }
    public string Name { get; private set; }

    protected PolymorphicEnum()
    {
    }

    public override string ToString()
    {
        return this.Name;
    }
}

And in order to get an int as the default underlying type, we define a derived class :

public abstract class PolymorphicEnum : PolymorphicEnum<int>
{
}

Adding registration

Ok, this has been quite simple. Now, we want the base class to allow its children to register instances. This means the base class will be responsible for instantiating, registering and tracking these instances. In order for the base class to instantiate the derived classes, we need to know their type in the method. To to this, we introduce a generic type parameter. We also want this method to accept an optional “ordinal” parameter, to handle the case where the ordinal values are defined by user-code. What we need is a method of the form :

protected static TEnumInstance Register<TEnumInstance>(
    Nullable<T> ordinal = null)
where TEnumInstance : new()

Notice the “new()” generic constraint on the type parameter : the given type has to have a parameter-less constructor, which we’ll use to instantiate it. But as we go towards the polymorphic behaviour, the enum class that we’ll have to instantiate can be a sub-class from the actual enum type ! For instance, if we take the first sample from the previous post, we have the following inheritance :

Because we do not want to give both of these type arguments on each Register call, the TEnum type argument moves up to the class level, and the class definition and Register method signature shift the following way:

public abstract class PolymorphicEnum<T>
    where T : struct, IComparable<T>, IConvertible  

public abstract class PolymorphicEnum<T, TEnum>
where T : struct, IComparable<T>, IConvertible
where TEnum : PolymorphicEnum<T, TEnum>, new()

protected static TEnumInstance Register<TEnumInstance>(
    Nullable<T> ordinal = null)
where TEnumInstance : new()

protected static TEnum Register<TEnumInstance>(
    Nullable<T> ordinal = null)
where TEnumInstance : TEnum, new()

The registration of the enum values is performed in a static dictionary, so here is at last the register method :

protected static TEnum Register<TEnumInstance>(
        Nullable<T> ordinal = null)
    where TEnumInstance : TEnum, new()
{
    if (!ordinal.HasValue)
    {
        ordinal = registeredInstances.Any()
            ? registeredInstances.Keys.Max().PlusOne()
            : default(T);
    }

    TEnum instance = new TEnumInstance();
    instance.Ordinal = ordinal.Value;

    registeredInstances.Add(ordinal.Value, instance);

    return instance;
}

Comment : how to implement a “PlusOne” extension method, that could increment any of the underlying types supported by an enum, has been a puzzle of its own… See this post for my solution !

Simplifying registration

From now on we can register enum value the following way :

public class SomeEnum : PolymorphicEnum<SomeEnum>
{
    public static SomeEnum FirstValue = Register<SomeEnum>();
    public static SomeEnum SecondValue = Register<SomeEnum>();
}

Wait !? Why must we provide the type to the Register method, if that is the same as the generic argument of the class ? Let’s move forward and define an additional Register method :

protected static TEnum Register(Nullable<T> ordinal = null)
{
    return Register<TEnum>(ordinal);
}

And the registration gets simpler again :

public class SomeEnum : PolymorphicEnum<SomeEnum>
{
    public static SomeEnum FirstValue = Register();
    public static SomeEnum SecondValue = Register();
}

Finding the names

So now we can register enum values, optionally specifying the ordinal value… but we’re not done yet ! I mean, aren’t we supposed to be able to convert enums from and to strings ? From the previous steps, we have a Name property with a private setter, and an overridden ToString() method. But the Name property is never set ! In my first implementations, providing the Register method with the string to associate with the value was mandatory. I was not satisfied with this solution, and I came up with the following replacement solution :

1. I added a static field to the class :

   private static bool namesInitialized = false;

2. I replaced the Name property implementation with this new one :

   private string name = null;
   private string Name
   {
       get
       {
           EnsureNamesInitialized();
           return this.name;
       }
       set
       {
           this.name = value;
       }
   }

3. I implemented the EnsureNamesInitialized method :

   protected void EnsureNamesInitialized()
   {
       if (!namesInitialized)
       {
           MemberInfo[] enumMembers = typeof(TEnum).GetMembers(
                   BindingFlags.Public
                   | BindingFlags.Static
                   | BindingFlags.GetField);
   
           foreach (FieldInfo enumMember in enumMembers)
           {
               TEnum enumValue =
                   enumMember.GetValue(null) as TEnum;
   
               if (enumValue != null)
                   enumValue.Name = enumMember.Name;
           }
           namesInitialized = true;
       }
   }

4. And finally I added this line at the end or the register method, just before the “return instance” statement :

   namesInitialized = false;

This mechanism ensures that the enum names are all computed using reflection. It assigns each enum value the name of the public static member to which it has been assigned (given the member has already been assigned and is of the correct type).

Serializing and deserializing

Nice ! We’ve made progress, really. Now we want to be able to serialize and deserialize the values from and to strings, as well as from the underlying primitive type.

Serializing to a string has been implemented from the start by the ToString() method. Deserializing will imply 4 methods signatures :

• bool TryParse(string value, out TEnum result)
• bool TryParse(string value, bool ignoreCase, out TEnum result)
• TEnum Parse(string value)
• TEnum Parse(string value, bool ignoreCase)

In the end the implementation is the following :

public static bool TryParse(string value,
                            bool ignoreCase,
                            out TEnum result)
{
    TEnum[] instances = registeredInstances
        .Values
        .Where(
            e => e.Name.Equals(
                value,
                ignoreCase
                    ? StringComparison.InvariantCultureIgnoreCase
                    : StringComparison.InvariantCulture))
        .ToArray();

    if (instances.Length == 1)
    {
        result = instances[0];
        return true;
    }
    else
    {
        result = default(TEnum);
        return false;
    }
}

The 3 other signatures simply rely on the previous method.

Concerning the other type of conversion (i.e. from and to the underlying primitive type), to stay as close as possible as how classical enums work, I have defined the following operator :

public static implicit operator T(PolymorphicEnum<T, TEnum> x)
{
    return x.Ordinal;
}

And the second one :

public static explicit operator PolymorphicEnum<T, TEnum>(T x)
{
    TEnum enumInstance;
    if (!registeredInstances.TryGetValue(x, out enumInstance))
        throw new ArgumentException(
            string.Format("Enum value {0} not found", x, "x"));

    return enumInstance;
}

Embedding data

Now we’re going to add an extra requirement : we want to embed data in the enum values. In order to store this values, I’ll be as open as I can and add an extra property typed as “object” :

protected object Data { get; private set; }

I’ll also add an extra optional parameter in the two Register methods, that become :

protected static TEnum Register(
    Nullable<T> ordinal = null,
    object data = null)
{
    return Register<TEnum>(ordinal, data);
}

and :

protected static TEnum Register<TEnumInstance>(
    Nullable<T> ordinal = null,
    object data = null)
where TEnumInstance : TEnum, new()
{
    if (!ordinal.HasValue)
    {
        ordinal = registeredInstances.Any()
            ? registeredInstances.Keys.Max().PlusOne()
            : default(T);
    }

    TEnum instance = new TEnumInstance();
    instance.Ordinal = ordinal.Value;
    instance.Data = data;

    registeredInstances.Add(ordinal.Value, instance);

    namesInitialized = false;

    return instance;
}

As you can see, not much as changed, but that is all there is to do ! A single point to mention is that nothing prevents the derived classes to change the state of the objects stored in the “Data” property. So when writing these derived classes, the developer has to be careful to enforce immutability.

Enforcing consistency

OK, I’ll soon stop this never-ending post, but there is a last detail that I wanted to explain, that is how I take care that once the set of values of an enum has been defined, it cannot be extended from any other class.

In order to register new values, you have to add new enum instances in the registeredInstances member. The way to do this is to call one of the two overloads or the Register method. If you wanted to bypass these methods, you would need to have access to the registeredInstances member, which is private in the base class, so that settles this point. But what prevents you from calling the Register methods in weird situations ? Let’s take a look at the following inheritance :

Put in code, it becomes :

public class SomeEnum : PolymorphicEnum<SomeEnum>
{
    public static SomeEnum FirstValue = Register();
    public static SomeEnum SecondValue = Register();
}

public class OtherEnum : PolymorphicEnum<SomeEnum>
{
    public static SomeEnum ThirdValueAttempt = Register();
}

public class OtherChildEnum : SomeEnum
{
    public static SomeEnum FourthValueAttempt = Register();
}

The above code is valid, and compiles without any warning. The register method is a protected method, so it can be called :

• from any class deriving from the same base classe PolymorphicEnum<T> (with the same T type), for instance here the OtherEnum class,
• from any sub-class, for instance here the OtherChildEnum class.

To prevent the registration of invalid values, we check at the very beginning of the Register method that the type which called the method is the same as the type being registered. To do so, we take a look at the call stack, either at the first or the second stack frame, depending on the overload of Register that was called :

StackFrame frame = new StackFrame(1);
if (frame.GetMethod().Name == "Register")
    frame = new StackFrame(2);

MethodBase enumConstructor = frame.GetMethod();
if (enumConstructor.DeclaringType != typeof(TEnum))
    throw new EnumInitializationException(
        "Enum members cannot be registered from other enums.");

This prevents the user code from registering undesired values. But there is still an edge case to be handled, pointed to me be @cyriux…

Let me show you what’s wrong… Remember the very first sample about the gestures ? Don’t look back ! Here is the code again :

/** PolymorphicEnum have behavior! **/
public class Gesture : PolymorphicEnum<Gesture>
{
    public static Gesture ROCK = Register<RockGesture>();
    public static Gesture PAPER = Register();
    public static Gesture SCISSORS = Register();

    // we can implement with the integer representation
    public virtual bool Beats(Gesture other)
    {
        return this.Ordinal - other.Ordinal == 1;
    }

    private class RockGesture : Gesture
    {
        public override bool Beats(Gesture other)
        {
            return other == SCISSORS;
        }
    }
}

The problem with this implementation is maybe not that obvious, but what if I write the following code ?

public class Godzilla : Gesture
{
    public static Godzilla Instance = new Godzilla();

    public override bool Beats(Gesture other)
    {
        return true;
    }
}

Yes, this is valid code. And the following test is green !

[TestMethod]
public void godzilla_beats_all()
{
    Assert.IsTrue(Godzilla.Instance.Beats(Gesture.ROCK));
    Assert.IsTrue(Godzilla.Instance.Beats(Gesture.PAPER));
    Assert.IsTrue(Godzilla.Instance.Beats(Gesture.SCISSORS));
}

Now imagine if the Gesture enum was part of a library… Nothing would prevent user code from providing a Godzilla instance wherever a Gesture is asked…

There are several ways to secure this implementation :

1. The logic could be provided as embedded data in the registration or the enum (using a lambda expression). Although this is the solution I would prefer (“composition over inheritance”, see the Manifesto for Not Only Object-Oriented Development), this would not be a real polymorphic behaviour anymore !
2. If we want to solve this using polymorphism, this is what I came up with. I added the following two “Checked” methods and the IsRegistered property in the base class :

private bool IsRegistered
{
    get { return registeredInstances.Values.Contains(this); }
}

protected TEnum Checked(TEnum value)
{
    if (!value.IsRegistered)
        throw new UnregisteredEnumException(
            "This enum is not registered");

    return value;
}

protected void Checked(Action a)
{
    if (!IsRegistered)
        throw new UnregisteredEnumException(
            "This enum is not registered");

    a.Invoke();
}

protected TReturn Checked<TReturn>(Func<TReturn> f)
{
    if (!IsRegistered)
        throw new UnregisteredEnumException(
            "This enum is not registered");

    return f.Invoke();
}

Using these new methods, here is how we could rewrite the previous “Godzilla” sample :

public class CheckedGesture : PolymorphicEnum<CheckedGesture>
{
    public static CheckedGesture ROCK = Register<RockGesture>();
    public static CheckedGesture PAPER = Register();
    public static CheckedGesture SCISSORS = Register();

    // we can implement with the integer representation
    public bool Beats(CheckedGesture other)
    {
        return Checked(() => this.BeatsImpl(Checked(other)));
    }

    protected virtual bool BeatsImpl(CheckedGesture other)
    {
        return this.Ordinal - other.Ordinal == 1;
    }

    private class RockGesture : CheckedGesture
    {
        protected override bool BeatsImpl(CheckedGesture other)
        {
            return other == SCISSORS;
        }
    }
}

And the method that can be overridden in the new Godzilla class in now the BeatsImpl one :

public class CagedGodzilla : CheckedGesture
{
    public static CagedGodzilla Instance = new CagedGodzilla();

    protected override bool BeatsImpl(CheckedGesture other)
    {
        return true;
    }
}

This now works correctly and the CagedGodzilla can’t be used in place of a CheckedGesture without throwing an UnregisteredEnumException. But this seems a little bit over-engineered, isn’t it ?

All of this horrible mess is available on my GitHub, along with the unit tests and the different steps of the implementation, which I’ve described in this post.

From the MSDN documentation, the allowed underlying types for enum types are the following (although other value types such as char are eligible, their use is not recommended) :

In order to enable the ordinal parameter to be optional in the registration of enum values, I had to find a way to compute an automatic value. The rule I wanted to apply was very simple : if there is no value already register, use zero, else use the maximum value already registered, plus one. But how do you write such code without checking the type in an ugly fashion ?

Generic constraints are somehow limited : I can force the ordinal type to be a value type by using a “where T : struct” constraints, but there is no such thing as a “IPrimitiveNumericValue” interface !

Here is where I got to, using generics and lambdas…

public static class Incrementer
{
    private static Func<T, T> GetFunc<T>(Func<T, T> f)
    {
        return f;
    }
    [...]

I first define static class and a private static helper function that take a Func<T, T> and returns… the unmodified argument. This is just a hint for the compiler, because I’m going to use lambdas and as you might know, a lambda can either be converted to a delegate (code) or to an expression tree representing the lambda (data). Without any indication, the compiler can’t infer the expected type, so we have to help him…

Then, the class defines a static field and initialises it in its static constructor :

private static Dictionary<Type, object> incrementers;

static Incrementer()
{
    incrementers = new Dictionary<Type, object>();
    incrementers.Add(typeof(sbyte), GetFunc<sbyte>(i => (sbyte)(i + 1)));
    incrementers.Add(typeof(byte), GetFunc<byte>(i => (byte)(i + 1)));
    incrementers.Add(typeof(short), GetFunc<short>(i => (short)(i + 1)));
    incrementers.Add(typeof(ushort), GetFunc<ushort>(i => (ushort)(i + 1)));
    incrementers.Add(typeof(int), GetFunc<int>(i => i + 1));
    incrementers.Add(typeof(uint), GetFunc<uint>(i => i + 1));
    incrementers.Add(typeof(long), GetFunc<long>(i => i + 1));
    incrementers.Add(typeof(ulong), GetFunc<ulong>(i => i + 1));
}

At this point, all the required incrementing functions are expressed as lambdas and registered in a dictionary.

The only method left to write is the PlusOne method :

public static T PlusOne<T>(this T value)
    where T : struct
{
    object incrementer;
    if (!incrementers.TryGetValue(typeof(T), out incrementer))
        throw new NotSupportedException(
            "This type is not supported.");

    return ((Func<T, T>)incrementer).Invoke(value);
}

Type checking and dictionary lookup. That’s it !

A few weeks ago, I read this post by @cyriux, describing how you could use polymorphic enums in Java. Actually, I had already heard him telling that enums in C# were nothing like the ones in Java. And even if he’s sometimes trolling, he’s really got a point there. Then I thought to myself : I know I won’t be able to add this syntax to C#, because I can’t change the compiler, but how clause could I get to polymorphic enums ? Let’s try that…

First, what are the common characteristics of an enum ?

• enums bind together a scalar value and a string representation, so enums can be converted to and parsed from strings
• for the same reason, enums can be casted to and from scalar values (int, long, short…),
• enums should be immutable (in fact, unless you introduce some mutable state in them, they already are),
• enums cannot be extended by other types : once defined, their set of values is closed and cannot be modified.

I haven’t checked for Java, but here are some other characteristics of C# enums :

• enums are a value types,
• enums implement the following interfaces : IComparable, IFormattable, IConvertible

In order to build a type that behaves like an enum, I’ve made the following decisions :

• I want to build a base type from which actual enums will derive. As there is nothing in C# as an abstract struct (value type), I have to implement a class and not a struct.
• In order to obtain a value type behaviour (value comparison instead of instance equality), I’ll will have to implement it.
• I will implement interfaces IComparable and IConvertible, but I haven’t really seen any use case where I would use IFormattable, so I chose not to implement it.
• Enums in C# don’t have an Ordinal property, but I’ll introduce one, so that I can write unit tests as close as possible as @cyriux’s ones. It will look a little bit Java-ish… but of course I’ll keep the C# casing convention.
• The underlying type used to represent an enum is an integer by default, but other types can be used, such as a long or an unsigned short. I will try to make the enums definitions as short a possible, so I’ll use generics and take advantage of the type inference system.

My C# enum has behaviour

Enough text there ! Directly inspired from @cyriux’s post’s first sample “Rock – paper – scissors”, here is the test cases that I want to execute :

[TestMethod]
public void paper_beats_rock()
{
    Assert.IsTrue(Gesture.PAPER.Beats(Gesture.ROCK));
    Assert.IsFalse(Gesture.ROCK.Beats(Gesture.PAPER));
}

[TestMethod]
public void scissors_beats_paper()
{
    Assert.IsTrue(Gesture.SCISSORS.Beats(Gesture.PAPER));
    Assert.IsFalse(Gesture.PAPER.Beats(Gesture.SCISSORS));
}

[TestMethod]
public void rock_beats_scissors()
{
    Assert.IsTrue(Gesture.ROCK.Beats(Gesture.SCISSORS));
    Assert.IsFalse(Gesture.SCISSORS.Beats(Gesture.ROCK));
}

And here is the implementation of the enum, built upon my PolymorphicEnum class :

/** PolymorphicEnum have behavior! **/
public class Gesture : PolymorphicEnum<Gesture>
{
    public static Gesture ROCK = Register<RockGesture>();
    public static Gesture PAPER = Register();
    public static Gesture SCISSORS = Register();

    // we can implement with the integer representation
    public virtual bool Beats(Gesture other)
    {
        return this.Ordinal - other.Ordinal == 1;
    }

    private class RockGesture : Gesture
    {
        public override bool Beats(Gesture other)
        {
            return other == SCISSORS;
        }
    }
}

As you can see in the implementation, it is now possible to define a Gesture enum, that exposes 3 static properties of type Gesture. One of these properties, ROCK, is in fact an instance of RockGesture, which is a Gesture that overrides the behaviour of Beats method.

Strategy Pattern

All the Java sample from the post can now be ported to C# ! The next one was the Eurovision contest, where an abstract method was defined in the base enum, and overridden in each enum instance, in order to implement a strategy pattern. This is where I admit I couldn’t get the same behaviour, as for internal implementations reasons I needed my base class to not be abstract… So I had to define a default behaviour :

public class EurovisionNotification
    : PolymorphicEnum<EurovisionNotification>
{
    /** Default behavior : I don't want to know ! */
    public virtual bool MustNotify(String eventCity,
                                   String userCity)
    {
        return false;
    }

    /** I love Eurovision, don't want to miss it, never! */
    private class EurovisionNotificationAlways
        : EurovisionNotification
    {
        public override bool MustNotify(string eventCity,
                                        string userCity)
        {
             return true;
        }
    }

    /**
     * I only want to know about Eurovision if it takes place
     * in my city, so that I can take holidays elsewhere at
     * the same time
     */
    private class EurovisionNotificationOnlyCity
        : EurovisionNotification
    {
        public override bool MustNotify(string eventCity,
                                        string userCity)
        {
             return eventCity.Equals(
                userCity,
                StringComparison.InvariantCultureIgnoreCase);
        }
    }

    public static EurovisionNotification ALWAYS =
        Register<EurovisionNotificationAlways>();
    public static EurovisionNotification ONLY_IN_MY_CITY =
        Register<EurovisionNotificationOnlyCity>();
    public static EurovisionNotification NEVER =
        Register();
}

State Pattern

The next sample is the one where a baby is represented as a state machine :

public class BabyState : PolymorphicEnum<BabyState>
{
    public static BabyState POOP = Register();

    public static BabyState SLEEP =
        Register(data: new { Next = POOP });

    public static BabyState EAT =
        Register(data: new { Next = SLEEP });

    public static BabyState CRY =
        Register(data: new { Next = EAT });

    public BabyState Next(bool discomfort)
    {
        if (discomfort)
            return CRY;

        return this.Data == null
            ? EAT
            : (BabyState)((dynamic)this.Data).Next;
    }
}

Just as for the Java enums, “we can reference enum constants between them, with the restriction that only constants defined before can be referenced”. The workaround here, as @cyriux wrote in his post, is to open the cycle. This builds allows us to build the graph on the right.

We can notice here that in order to embed data in an enum value, I have introduced an extra parameter “data” in the Enum method, which is responsible for the Enum values registration. Using this extra parameter, we can go back to the Eurovision sample and rewrite this way :

using Policy = System.Func<string, string, bool>;

public class EurovisionNotificationLambda
    : PolymorphicEnum<EurovisionNotificationLambda>
{
    private static Policy Policy(Policy f) { return f; }

    public static EurovisionNotificationLambda ALWAYS =
        Register(data: Policy((eventCity, userCity) => true));

    public static EurovisionNotificationLambda ONLY_IN_MY_CITY =
        Register(data: Policy((eventCity, userCity) =>
            eventCity.Equals(
                userCity,
                StringComparison.InvariantCultureIgnoreCase)));

    public static EurovisionNotificationLambda NEVER =
        Register(data: Policy((eventCity, userCity) => false));

    public bool MustNotify(String eventCity, String userCity)
    {
        return ((Policy)this.Data).Invoke(eventCity, userCity);
    }
}

In this implementation, each enum value owns its notification policy, in the form of a types delegate, which is declared using a lambda expression.

Enum-non-optimized collections

Ok, I haven’t gone so far as implementing optimized collections that take advantage of the integer nature of enums ! So not all the arguments listed by @cyriux apply to my C# implementation… But I still get polymorphism, the correct Equals, GetHashCode, ToString, string or integer serialization, and singleton-ness for free, with very little code ! Feel free to experiment with it if you want, the whole project will be available on my GitHub very soon.

In a next post, I’m going to talk about some points of interest in my PolymorphicEnum implementation.

SpecFlow is a testing component / framework / Visual Studio plug-in, which allows you to write your tests in a natural fashion, and run these tests using your favourite test-runner. As quoted from their web site :

SpecFlow aims at bridging the communication gap between domain experts and developers by binding business readable behavior specifications to the underlying implementation. Our mission is to provide a pragmatic and frictionless approach to Acceptance Test Driven Development and Behavior Driven Development for .NET projects today.

SpecFlow is build upon the Gherkin syntax, which is a grammar that has been designed to write behaviour specifications. This syntax first emerged in the Ruby community, and is linked to a project called Cucumber. For more details, you can check out http://cukes.info :

Cucumber is Aslak Hellesøy’s rewrite of RSpec’s “Story runner”, which was originally written by Dan North. (Which again was a rewrite of his first implementation – RBehave. RBehave was his Ruby port of JBehave)…

Gherkin is Cucumber’s DSL (Domain Specific Language) and as such, is not linked to a particular language or technology. It can therefore be used in .NET by using SpecFlow. It has very few keywords, yet is very powerful. The best way to explain how it works is to show an example of a test scenario :

Scenario: Filter on age
    Given I have written a query against the provider
    And I have added a Age >= 36 where clause
    Given The people finder service filters on Age >= 36
    When I execute the query
    Then The service parameter should be Age IsGreaterThan 36
    And The result count should be 3
    And The result should validate the servicePredicate

From now on, you might have noticed that I’m working on my Linq provider again… but in this post I’ll talk only about testing and using SpecFlow, so don’t run away, even if you’re sick of expression trees !

What SpecFlow allows you to do, is to write your specifications and tests cases in plain text, and generate tests classes from it. It has several nice features that help you organize your tests and examples, which I’ll describe soon.

In order to use SpecFlow in your project, the easiest way is to add a reference to it in your test project, using the NuGet package manager. To get Visual Studio integration, you should also install the “SpecFlow integration for Visual Studio extension”.

When doing BDD, the tests are written in order to tests features. For each feature of an application (or component, or class), you can create a feature file. As you can see from the previous example, tests will be organised around the concept of “scenario”. Each feature file can contain several scenarios. The binding between a scenario and the actual tests implementation will be done on a line-by-line basis. Each line of the scenario will end up as a method call :

• the “Given” and associated “And” clauses will correspond to methods that set up the tests,
• the “When” clause will trigger some action or event that drives the behaviour that is aimed to be tested,
• the “Then” and associated “And” clauses will perform the assertions that determine the outcome of the test.

In order to do the matching between lines in the scenario and methods in the test class, the methods are marked with the appropriate SpecFlow attributes, that take the model of the expected sentence as an argument. This model can include groups of capturing expressions, that are used to populate the method parameters at run time.

[Given(@"I have added a (.*) where clause")]
public void GivenIHaveAddedAWhereClause(string predicate)

If we go back to the test scenario shown earlier, the best way to see how the test is executed is to look at the generated test output:

Given I have written a query against the provider
-> done: FeaturesTest.GivenIHaveWrittenAQuery() (0,0s)
And I have added a Age >= 36 where clause
-> done: FeaturesTest.GivenIHaveAddedAWhereClause("Age >= 36") (0,0s)
Given The people finder service filters on Age >= 36
-> done: FeaturesTest.GivenThePeopleFinderServiceFiltersOn("Age >= 36") (0,0s)
When I execute the query
-> done: FeaturesTest.WhenIExecuteTheQuery() (0,1s)
Then The service parameter should be Age IsGreaterThan 36
-> done: FeaturesTest.ThenTheServiceParameter("Age IsGreaterThan 36") (0,0s)
And The result count should be 3
-> done: FeaturesTest.ThenTheResultCount(3) (0,0s)
And The result should validate the servicePredicate
-> done: FeaturesTest.ThenTheResultShouldValidatetheServicePredicate() (0,0s)

We can see that each line of the scenario is used to call a method. In order to “accumulate” the conditions and perform the assertions on the results, we use a class that defines the test context :

public class ServiceContext
{
    // Data context
    public IEnumerable<Person> AllPeople { get; set; }

    // Input
    public List<string> Query { get; set; }
    public List<string> ServiceLambdas { get; set; }

    // Service predicate, built upon the ServiceLambdas
    public Expression<Func<Person, bool>>
                            ServicePredicate {get; set;}

    // Output
    public List<Person> Results { get; set; }
    public SearchCriteria PassedCriteria { get; set; }
}

Using this context class, the methods corresponding to the “Given” populate the properties used as the test input, the “When” performs the action, which populates the output based on the input, and the “Then” make assertions on the output.

The next step is to add additional test cases. A simple way could be to simply copy-paste the previous scenario, and change the parameters. But as we always want to void duplication, we’ll use a very handful feature here and use a “Scenario Outline” and examples :

Scenario Outline: Filter on a single criterion
    Given I have written a query against the provider
    And I have added a <predicate> where clause
    Given The people finder service filters on <servicePredicate>
    When I execute the query
    Then The service parameter should be <serviceParameter>
    And The result count should be <resultsCount>
    And The result should validate the servicePredicate
    Examples: 
    | predicate                     | servicePredicate              | serviceParameter            | resultsCount |
    | Age >= 36                     | Age >= 36                     | Age IsGreaterThan 36        | 3            |
    | Age >= 36                     |                               | Age IsGreaterThan 36        | 6            |
    | FirstName.StartsWith("Scar")  | FirstName.StartsWith("Scar")  | FirstName StartsWith Scar   | 1            |
    | LastName == Alba              |                               | LastName Equals Alba        | 6            |

The main advantage of this syntax is that it is self-explanatory ! Once the scenario outline is prepared, we list all the cases that we want to test.

If you’ve read the post carefully up to this point, you might have noticed that my scenario makes assertions on the number of results, but that there is nothing that sets-up the test data. In fact, there is a hidden “Given” clause that is used across the whole feature file. The way to to this is by using the keyword “Background”:

Background: 
    Given The people are
    | FirstName | LastName    | Age | Id                                     |
    | Scarlett  | Johansson   | 27  | {8c319634-935d-4681-adcc-02d5347fe6c4} |
    | Jessica   | Alba        | 31  | {32a84597-8c3d-44bc-a1a5-6538188e9d25} |
    | Penelope  | Cruz        | 38  | {5aa0eb59-3961-472f-b829-7d54ac8eeeef} |
    | Reese     | Witherspoon | 36  | {77fcd741-3839-4692-925f-a3a0eb19cf42} |
    | Charlize  | Theron      | 36  | {e37290f6-d376-44e2-944d-d0af13c1a75c} |
    | Mouloud   | Achour      | 31  | {18af541a-a5dc-41d2-af47-479b1c06e216} |

One last thing : although parsing the lambda given as arguments in the scenario is a topic of its own and could be discussed further, setting up the test data from the previous “Given” clause is delightfully easy, and I couldn’t help not showing you the code :

[Given(@"The people are")]
public void GivenThePeopleAre(Table people)
{
    this.context.AllPeople = people.CreateSet<Person>();
}

As a conclusion, I strongly recommend to give SpecFlow a try, you won’t regret it !

All the source code from this post and the Linq Provider Series is now available on my Github at https://github.com/pirrmann/LinqToService. Please feel free to fork and/or contribute, and I’d also be really happy to get feedback !

Just a month ago, I’ve had the opportunity to get feedback from @cyriux and Jérôme during the monthly @ArollaFr’s Code Jam, and we made important changes in the code.

The concept of a Code Jam is simple : we meet once a month to practice our coding skills, emphasizing practices such as TDD and pair-programming.
For more details (in French) : http://www.arolla.fr/evenements-2/jams-de-code/

June’s theme was “Testing things that are difficult to test”. The session started with a “Lightning talk” by @cyriux, describing several situations where testing can be quite complicated, as for instance :

• When time is involved
• When parallelization and multi-threading is involved
• When architecture is involved (network bandwidth, fault-tolerant systems)
• Testing security (SQL injection, various kinds of exploits)
• When the host is difficult to emulate (as example: how to test an eclipse plug-in ?)
• Testing with non-trivial outputs/inputs: images, sounds, documents, reports, big messages…
• Testing with large configuration problems: realistic search index, social algorithms, time series for financial analytics…

After this introduction, we were looking for a practical example of such a situation, and I suggested we could take a look at my implementation of this Linq provider. I haven’t gone very far yet, but my goal with this Linq to web service provider is to make the service return filtered data based on the Linq query. This means that I want the filtering to happen inside the web service, and not on the client side. And this is of course a behaviour that I want to test:

After some discussion, @cyriux pointed to me that there were several false assumptions in the way I was testing things. I assumed I would be testing the provider by using it against a service that I had built myself… but I had no need for an actual web service implementation ! The service and the provider are two separate features, and mustn’t be unit-tested at the same time.

I have not completely given up the idea of implementing the service, but it is now a separate objective that has nothing to do with the provider implementation. And the fact that the service is a web service is just an implementation detail. My vision of the way to organize the project is now the following :

The solution is now only composed of 3 assemblies :

• PeopleFinder, which defines the service interface (i.e. the contract) and POCOs used as simple Data Transfer Objects,
• LinqToService, which contains the actual implementation of the Linq provider,
• UnitTests, which contains the tests and a “lambda-based” implementation of the PeopleFinder interface.

This organisation allows us to test only the behaviour of the provider, providing our own implementation of the service. To do so, we introduced a PeopleFinderLocator class. This might change in the future, but is quite out of scope here…

Given a query expression, the Linq provider’s goal is just to give the service the good parameters, and perform additional work that the service cannot handle. Here, the service knows how to filter the people based on their age. Let’s consider the following query :

var query = new QueryableServiceData<Person>()
    .Where(p => p.Age >= 36);

When executing it, the provider must call the service with the appropriate parameter, and mustn’t do any additional work except handling the result back to the caller. The situation should be the following :

And here is a test corresponding to this situation :

[TestMethod]
public void GivenAProviderWhenIFilterOnAgeGT36ThenItFilters()
{
    LambdaBasedPeopleFinder peopleFinder =
        new LambdaBasedPeopleFinder(p => p.Age >= 36);
    PeopleFinderLocator.Instance = peopleFinder;

    QueryableServiceData<Person> people =
        new QueryableServiceData<Person>();

    var query = people
        .Where(p => p.Age >= 36);

    var results = query.ToList();

    Assert.IsTrue(results.All(p => p.Age >= 36));
    Assert.AreEqual(
        new IntCriterion()
            {
                FilterType = NumericFilterType.IsGreaterThan,
                Value = 36
            },
            peopleFinder.PassedCriteria.Age);
}

In the previous test, we use a LambdaBasedPeopleFinder implementation of the service, that actually filters some sample data based on a predicate. In some way we rely on this implementation because we test that the results are correctly filtered. But we can even test that the provider doesn’t do the service’s work !

If we adapt the previous test by replacing the lambda by p => true, the results returned by the service will not be filtered, and we can test that the provider correctly delegates the work to the service, and doesn’t filter the data.

[TestMethod]
public void WhenIFilterOnAgeGT36ThenTheProviderDoesntFilter()
{
    LambdaBasedPeopleFinder peopleFinder =
        new LambdaBasedPeopleFinder(p => true);
    PeopleFinderLocator.Instance = peopleFinder;

    QueryableServiceData<Person> people =
        new QueryableServiceData<Person>();

    var query = people
        .Where(p => p.Age >= 36);

    var results = query.ToList();

    Assert.IsFalse(results.All(p => p.Age >= 36));
    Assert.AreEqual(
        new IntCriterion()
        {
            FilterType = NumericFilterType.IsGreaterThan,
            Value = 36
        },
        peopleFinder.PassedCriteria.Age);
}

Finally, testing the provider was not a complicated question. My problem was not “how to test”, but rather “what to test”.

To finish, here are the next things that I want to do about this project :

• Use SpecFlow to transform all my tests and use the Gherkin syntax,
• Handle more complex queries, list all the type of nodes that can be found and handle them, ensuring the correctness of the returned data. If needed, any unhandled node type would result in using a blank SearchCriteria object and performing all the work using Linq to Objects,
• Implement the service, even if it’s not necessary, just for the sake of it,
• Get stuck manipulating expression tress,
• Push the whole thing to a Github repository,
• Get help from anyone motivated.

In the last two posts, I included sample visualizations of expression trees. I’ve built these using a visitor pattern, that produces HTML markup. This is a good example of the use of this pattern, so I’ll try to explain how it allows us to work with expression trees.

The expression tree visualization that I build is based on HTML / CSS3, using the code provided at http://thecodeplayer.com/walkthrough/css3-family-tree. Basically, the markup is formed of unordered lists (“ul / li” tags) that contains nested lists. You can view the generated HTML source by inspecting the DOM in the previous post.

The visualization builder is a class called TreeVisualizer, inheriting from ExpressionVisitor :

internal class TreeVisualizer : ExpressionVisitor
{
    private StringBuilder builder;
    private HtmlTextWriter writer;

    private TreeVisualizer()
    {
        this.builder = new StringBuilder();
        this.writer = new HtmlTextWriter(
            new StringWriter(
                this.builder,
                CultureInfo.InvariantCulture),
            "    ");
    } [...]

The constructor is private, the only way to use this class is through a static method called BuildVisualization :

internal static string BuildVisualization(Expression expression)
{
    TreeVisualizer visualizer = new TreeVisualizer();
    visualizer.Visit(expression);
    return visualizer.Visualization;
}

The returned property, Visualization, is defined this way :

public string Visualization
{
    get
    {
        return this.builder.ToString();
    }
}

The class uses also two utility methods :

• GetSimplifiedType, which gives a user-friendly string representation of a given type.

private string GetSimplifiedType(Type type)
{
    if (!type.IsGenericType)
        return type.Name;

    string genericName = type.Name.Split('`').First();

    string genericArguments = string.Join(
        ", ",
        type.GenericTypeArguments.Select(
            t => GetSimplifiedType(t)));

    return string.Format(
        "{0}<{1}>",
        genericName,
        genericArguments);
}

• VisitAndBuildTree, which adds content to the HtmlTextWriter based on the tree nodes that it visits :

private Expression VisitAndBuildTree(
    string nodeName,
    string nodeType,
    string nodeDescription,
    Func<Expression> childrenVisitorFunction = null)
{
    this.writer.RenderBeginTag("li");
    this.writer.WriteLine();
    this.writer.Indent++;

    this.writer.AddAttribute("href", "#");
    this.writer.RenderBeginTag("a");

    this.writer.AddAttribute("class", "node-name");
    this.writer.RenderBeginTag("span");
    this.writer.WriteEncodedText(nodeName);
    this.writer.RenderEndTag();
    this.writer.WriteBreak();

    if (!string.IsNullOrEmpty(nodeType))
    {
        this.writer.AddAttribute("class", "node-type");
        this.writer.RenderBeginTag("span");
        this.writer.WriteEncodedText(nodeType);
        this.writer.RenderEndTag();
        this.writer.WriteBreak();
    }

    this.writer.WriteEncodedText(nodeDescription);
    this.writer.RenderEndTag();
    this.writer.WriteLine();

    Expression baseReturn = null;
    if (childrenVisitorFunction != null)
    {
        this.writer.RenderBeginTag("ul");
        this.writer.WriteLine();
        this.writer.Indent++;

        baseReturn = childrenVisitorFunction();

        this.writer.Indent--;
        this.writer.RenderEndTag();
        this.writer.WriteLine();

    }

    this.writer.Indent--;
    this.writer.RenderEndTag();
    this.writer.WriteLine();

    return baseReturn;
}

With the two previous functions, we can now override each VisitSomeTypeOfNode method and insert the appropriate details in the HTML. For instance :

protected override Expression VisitBinary(
    BinaryExpression node)
{
    return VisitAndBuildTree(
        "Binary",
        string.Empty,
        node.NodeType.ToString(),
        () => base.VisitBinary(node));
}

protected override Expression VisitLambda<T>(
    Expression<T> node)
{
    return VisitAndBuildTree(
        "Lambda",
        GetSimplifiedType(node.Type),
        node.ToString(),
        () => base.VisitLambda<T>(node));
}

protected override Expression VisitMethodCall(
    MethodCallExpression node)
{
    return VisitAndBuildTree(
        "Call",
        GetSimplifiedType(node.Type),
        node.Method.Name,
        () => base.VisitMethodCall(node));
}

There are many methods, I’m not going to show them all here. I’ll just finish with a special one, VisitConstant. For this one, I just handled two special cases, when the constant is an IEnumerable, or when it is a string. This allows us to see the constants values for simple types in the tree, and a simplified type description if it is a generic IEnumerable.

protected override Expression VisitConstant(
    ConstantExpression node)
{
    string type = GetSimplifiedType(node.Type);

    string value;
    if (node.Type.IsGenericType
        && node.Type.FindInterfaces(
            (t, o) => t.Name.StartsWith("IEnumerable"),
            true).Any())
    {
        value = type;
    }
    else if(type == "String")
    {
        value = string.Concat(
            "\"",
            ((string)node.Value).Replace("\"", "\\\""),
            "\"");
    }
    else
    {
        value = node.Value.ToString();
    }

    VisitAndBuildTree(
        "Constant",
        type,
        value);
    return base.VisitConstant(node);
}

That’s all for tonight !

Using the Visitor pattern to manipulate expression trees

In the previous posts of this series, I started to describe a partial implementation of a Linq provider. The aim of this provider is to get data from a service, and in order to actually return that data to the caller, it implies some expression tree manipulations. After we obtained the data from the service, we want to inject an access to that actual data in the query expression tree, instead of the QueryableDummyData<Person> instance, which is in fact only a placeholder.

In order to replace that QueryableDummyData<Person> by a Person[] array, we use a class called ExpressionTreeConstantReplacer, which derives from the .NET 4.0 built-in ExpressionVisitor class, which in turn is based upon the Visitor pattern.

Applied to expression trees, the Visitor pattern can be used to generate an expression tree from the visited one, to accumulate some data while visiting the tree, or even both at the same time. Each visit method overload returns an expression, which is by default the unchanged expression it has just visited. It can return a new tree, but is should not modify the visited expression. This approach has the advantage to have no side-effect on the visited expression tree.

As a sample, the visitor pattern can be used to transform the following expression tree :

to this expression tree, which is the same but without the p => p.Age >= 21 where clause :

The ExpressionVisitor class is meant to be derived from, in order to create tree-manipulation classes. When the ExpressionVisitor’s Visit method is called, it determines the type of the node given as an entry parameter, and recursively visits the node and all his children, using each time the method corresponding to the node’s type.

This allows the developer of a derived class to override only the methods that needs to be. For instance, as we want to replace a Constant node with an other one, the class ExpressionTreeConstantReplacer derives from ExpressionVisitor and overrides the method VisitConstant.

internal class ExpressionTreeConstantReplacer<TReplacement>
    : ExpressionVisitor
{
    private Type originalType;
    private TReplacement replacementConstant;

    internal ExpressionTreeConstantReplacer(
        Type originalType, TReplacement replacementConstant)
    {
        this.originalType = originalType;
        this.replacementConstant = replacementConstant;
    }

    protected override Expression VisitConstant(
        ConstantExpression c)
    {
        if (c.Type == this.originalType)
            return Expression.Constant(this.replacementConstant);
        else
            return c;
    }
}

The constructor of this class takes two arguments : the type of the original constant to replace, and the new value. Then during the expression tree visiting process, when a node of type Constant is detected, the VisitConstant method is called, and if its type matches the type to replace, a new Constant node encapsulating the replacement value is returned.

In order to make the replacement call more expressive, a helper class is also introduced, in order to take advantage of C#’s type inference, which is available on static methods but not on constructors :

internal class ExpressionTreeConstantReplacer
{
    internal static Expression CopyAndReplace<TReplacement>(
        Expression expression,
        Type originalType,
        TReplacement replacementConstant)
    {
        var modifier =
            new ExpressionTreeConstantReplacer<TReplacement>(
                originalType,
                replacementConstant);
        return modifier.Visit(expression);
    }
}

This is what allows us to write the final replacement call this way :

Expression finalExpressionTree =
    ExpressionTreeConstantReplacer
        .CopyAndReplace(
            filteredExpressionTree,
            typeof(QueryableDummyData<Person>),
            queryablePersons);

Next time, I’ll describe the TreeVisualizer class I wrote to generate the expression trees visualizations in this post.