C#
May 2014 16

Ещё один Pattern Matching на C#

From Sandbox
Последнее время в процессе работы с языком C# я стал всё острее и острее нуждаться в механизме сопоставления с образцом, который присутствует во многих современных мультипарадигмальных языках (F#, Scala и т.д.), но отсутвует в C#. Найденые благодаря получасу гугления реализации (Пример) предлагали конструировать match-выражения посредством fluent-интерфейсов, что, на мой взгляд, довольно громоздко синтаксически. Вторым, уже более существенным для реального использования, недостатком является overhead на перебор предикатов в цикле, происходящий «под капотом» в таких мэтчерах. В общем, я задался целью написать собственную реализацию сопоставления с образцом, руководствуюсь двумя основными принципами:
  • Синтаксически приблизится к «нормальным» конструкциям как в F#/Scala
  • Приблизиться по производительности к коду с if/else if/else насколько это возможно


За тем, что получилось — прошу под кат


Внешний вид


Изначально мне хотелось сделать конструкцию мэтчера похожей на «настоящую», избежав цепочных вызовов методов. Решено было использовать список пар «предикат — функция». Для того, чтобы можно было использовать сокращённый синтаксис инициализации списка, класс Matcher реализует IEnumerable, а также имеет метод Add. Для удобства использования (например, для передачи в Select), в класс был добавлен метод неявного приведения к Func<>

Вот как это выглядит при использовании:
Func<string, int> match = new Matcher<string, int>
{
    {s => string.IsNullOrEmpty(s), s => 0},
    {s => true, s => s.Length}
};

int len1 = match(null); // 0
int len2 = match("abc"); // 3


Реализация


Первая реализация, написанная в процессе поиска синтаксиса, была «наивной» и, так же как и найденые, производила поочерёдное выполнение предикатов с передаваемым в Match параметром. Когда код начал удовлетворять по первому пункту (быть внешне не громоздким), я переписал мэтчер с использованием Expression<>:

public class ExprMatcher<TIn, TOut> : IEnumerable<Pair<Expression<Predicate<TIn>>, Expression<Func<TIn, TOut>>>>
    {
        private Func<TIn, TOut> _matcher;

        private Func<TIn, TOut> Matcher
        {
            get { return _matcher ?? (_matcher = CompileMatcher()); }
        } 
        private readonly List<Pair<Expression<Predicate<TIn>>, Expression<Func<TIn, TOut>>>> _caseList = new List<Pair<Expression<Predicate<TIn>>, Expression<Func<TIn, TOut>>>>();

        public void Add(Expression<Predicate<TIn>> predicate, Expression<Func<TIn, TOut>> function)
        {
            _caseList.Add(new Pair<Expression<Predicate<TIn>>, Expression<Func<TIn, TOut>>>(predicate, function));
        }

        private Func<TIn, TOut> CompileMatcher()
        {
            var reverted = Enumerable.Reverse(_caseList).ToList();

            var arg = Expression.Parameter(typeof(TIn));
            var retVal = Expression.Label(typeof(TOut));
            var matcher = Expression.Block(
                        Expression.Throw(Expression.Constant(new MatchException("Provided value was not matched with any case"))),
                        Expression.Label(retVal, Expression.Constant(default(TOut)))
                    );
            
            foreach (var pair in reverted)
            {
                retVal = Expression.Label(typeof(TOut));
                var condition = Expression.Invoke(pair.First, arg);
                var action = Expression.Return(retVal, Expression.Invoke(pair.Second, arg));

                matcher = Expression.Block(
                    Expression.IfThenElse(condition, action, Expression.Return(retVal, matcher)),
                    Expression.Label(retVal, Expression.Constant(default(TOut)))
                    );
            }

            return Expression.Lambda<Func<TIn, TOut>>(matcher, arg).Compile();
        }

        public TOut Match(TIn value)
        {
            return Matcher(value);
        }

        public static implicit operator Func<TIn, TOut>(ExprMatcher<TIn, TOut> matcher)
        {
            return matcher.Match;
        }

        public IEnumerator<Pair<Expression<Predicate<TIn>>, Expression<Func<TIn, TOut>>>> GetEnumerator()
        {
            return _caseList.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }


При вызове метода Match() или при приведении к Func создаётся цепочное выражение, выбрасывающее MatchException в случае, если аргумент не удовлетворяет ни одному из предикатов. В результате получаем только оверхед в виде времени компиляции Expression.

Алгебраические типы


Другим неудобством использования C# для меня было отсутсвие типов-объединений в нём. Хотелось добавить их, но при этом сделать их использование настолько безопасным (на предмет NPE), насколько это возможно.
Для начала было реализовано объединение двух типов:
public sealed class Union<T1, T2>
{
	public object Value { get; private set; }
	public T1 Value1 { get; private set; }
	public T2 Value2 { get; private set; }
		
	public Union(T1 value)
        {
                Value1 = value;
	        Value = value;
        }
	public Union(T2 value)
        {
                Value2 = value;
		Value = value;
        }
		
	public static explicit operator T1(Union<T1, T2> value)
        {
                return value.Value1;
        }
	public static explicit operator T2(Union<T1, T2> value)
        {
                return value.Value2;
        }
		
        public static implicit operator Union<T1, T2>(T1 value)
        {
                return new Union<T1, T2>(value);
        }
        public static implicit operator Union<T1, T2>(T2 value)
        {
               return new Union<T1, T2>(value);
        }
}

В зависимости от передаваемого в конструктор параметра, в экземпляре инициализируется либо свойство Value1, либо Value2, при этом также инициализируется Value. Это позволяет сравнивать проверять тип Value в предикате c помощью is, не беспокоясь о том, что значение примет какой-либо иной тип кроме T1 и T2. С помощью шаблонизатора t4 были сгенерированы перегрузки Union до 17 типов.
Так-же для упрощения инициализации мэтчеров были написаны наследники Matcher и ExprMatcher:
public class ExprMatcher<T1, T2, T3> : ExprMatcher<T1, Union<T2, T3>> {}


Для полноты картины был написан также довольно тривиальный Option.

Надеюсь, что мой мэтчер будет кому-нибудь полезен:
Проект на bitbucket
Nuget пакет

Спасибо за внимание!
+18
16.5k 113
Comments 14