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

Последнее время в процессе работы с языком 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 пакет

Спасибо за внимание!
Поделиться публикацией

Комментарии 14

    +2
    Весьма и весьма красиво! Я сам любитель навертеть чего-нибудь удобного и необычного на синтаксических фишках языка.
    Одно предложение: добавьте, пожалуйста, экстеншн метод аля ToFunc, чтобы можно было объявлять матчеры через var, а то много пользователей, среди которых я, пишут сначала new Matcher...., а потом жмут introduce variable в решарпере. В этом случае можно написать .ToFunc и тип станет функцией:

      public static class MatcherEx
      {
        public static Func<T1, T2> ToFunc<T1, T2>(this Matcher<T1, T2> matcher)
        {
          return matcher;
        }
      }
      ...
      var matcher = new Matcher<string, int>
      {
        {s => true, s => s.Length}
      }.ToFunc();
    
      var i = matcher("asd");
    
    
      +2
      Отличная идея! Честно говоря, долго думал, как же сделать возможность не указывать явно полную сигнатуру Func. Обновил пакет
      +1
      При всем моем уважении, это не pattern matching ни разу. Все что угодно, но не _сопоставление с образцом_.
        0
        Вас смущает отсутствие готовых дискриминаторов для коллекций?
          0
          Нет конечно :-)
          В первую очередь, меня «смущает» отсутствие _образца_ как такового. Предикат не является образцом, и не может таковым быть. По той простой причине, что предикат не способен определить контекст, связывающий… кхм… скажем так… «правую» и «левую» части «выражения» сопоставления.
            0
            Вы правы, но единственный способ так сделать, который мне удалось придумать — объединять предикат и функцию в объект «дискриминатор», что выглядит уже не так красиво

            У меня была изначально идея сделать что-то вроде
            s => string.IsNullOrEmpty(s) => 0
            

            Но C# не позволяет писать такие выражения.
              +4
              Да дело-то не в этом.

              Каким именно образом будет задаваться _образец_ дело конечно важное, но не настолько.

              Проблема как раз в том, что результат сопоставления — это — грубо говоря — не true/false. Результат сопоставления — это контекст. Сам процесс сопоставления — это, по большому счету, процесс построения контекста. Удалось построить — сопоставление удалось. Не удалось — результатом будет контекст, определяющий исключительную ситуацию в том или ином виде.

              Если «на пальцах» — то в вашем случае, вычисление правого выражения пары, должно происходить в контексте, полученном в результате вычисления левого выражения пары. Т.е. левое выражение должно быть не предикатом, а функцией возвращающей, например, Expression.
          0
          Вроде в C# есть замыкания. Объединение легко делается как замыкание, получающее параметрами две функции, и вызывающая одну из них с параметром нужного типа.
            0
            Добрый день, скажите а почему вам не подошли похожие решения вроде May(http://twistedoakstudios.com/blog/Post1130_when-null-is-not-enough-an-option-type-for-c) или Scalesque(http://noelkennedy.github.io/scalesque/)?
              0
              Здравствуйте. Scalesque не использует деревьев выражений, что порождает оверхед на вызовы функций при сопоставлении. May я не находил ранее, но судя по коду он работает схожим со Scalesque образом
                0
                Понятно, т.е. вы бы не рекомендовали ваше решение тем для кого быстродействие критично? Вопрос без подвоха.
                  0
                  -
                    0
                    Моё решение по сути генерирует код, эквивалентный цепочным if'ам. Единственное, что стоит учитывать — время компиляции Expression, но она происходит лишь однажды — при первом сопоставлении либо при приведении к Func.
                    По крайней мере, при использовании ExprMatcher в продакшене деградации производительности по сравнению с цепочным if'ом замечено не было

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое