Pattern matching in C# – part 2

Last time, I just stopped before generating any real expression tree… Now is the perfect time to continue the process !

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 ?