Как стать автором
Обновить
3270.72
RUVDS.com
VDS/VPS-хостинг. Скидка 15% по коду HABR15

Такого «Посетителя» вы ещё не видели — Visitor.NET

Уровень сложностиСредний
Время на прочтение12 мин
Количество просмотров5.5K


«Посетитель» (visitor) — один из самых сложных паттернов Банды Четырёх.

На языке C# для него можно создать множество реализаций, однако все они так или иначе имеют ограничения из-за возникающего динамического приведения типов.

В рамках статьи вы погрузитесь в проблематику мультиметодов и увидите новую реализацию паттерна, лишённую озвученных недостатков и открывающую возможность к написанию по-настоящему гибкого и типобезопасного кода!

Поскольку ты читаешь эту статью, то я уверен, что ты знаком с такими вещами, как ООП, паттерны, полиморфизм и хотя бы раз в жизни слышал слово Visitor.

Казалось бы, паттерн «Посетитель», да что тут можно придумать? Прямо сейчас я покажу тебе, как изобрёл его новую и абсолютно уникальную реализацию.

Пара слов о Visitor


Где вы столкнётесь с необходимостью использовать этот паттерн?

  • Самое очевидное применение — конструирование компиляторов, поскольку это самый лучший способ обрабатывать Abstract Syntax Tree.
  • Работа с Expressions API или Roslyn API — опять же прямая работа с объектной моделью синтаксиса.
  • Паттерн «Компоновщик», он же Composite — рекурсивная древовидная структура данных.

Отдельным пунктом выделю создание DSL, поскольку здесь стоит прикрепить интересный доклад о практическом применении DSL в кровавом энтерпрайзе:

Я столкнулся с ними при обучении в ВУЗе. Дело в том, что моя кафедра, ИУ-9 МГТУ им. Н. Э. Баумана, специализируется на конструировании компиляторов, что определило тему диплома — создание интерпретируемого языка программирования.

Соответственно, я брал некий исходный код, парсил его в AST, а потом обходил дерево и генерировал список инструкций для виртуальной машины, совершая приблизительно такое преобразование:



Вообще, AST в этой предметной области — такой же базовый кирпич, как JSON в промышленной разработке — вокруг него слишком много фундаментальных задач:

  • Инициализация областей видимости и таблиц символов
  • Статический анализ
  • Предварительная оптимизация
  • Кодогенерация
  • И многое другое

Поэтому вопрос удобной и эффективной работы с подобными структурами данных стоит остро!

▍ Интрузивный подход


Это причина, по которой паттерн появился. Такой ошибочный подход означает расширение функционала рекурсивной структуры данных через наследование и полиморфизм подтипов:

public abstract class AbstractSyntaxTreeNode
{
    public virtual List<Instruction> ToInstructions(int start) => new();
}

Последствиями такого недальновидного проектирования будут трудноисправляемые и неотлаживаемые баги. Также ограничивается возможность развития системы — сложность реализации новых фич растёт экспоненциально из-за неправильного распределения ответственностей компонентов.

Например, в моём случае интрузивно реализованная кодогенерация присваивала инструкциям некорректный адрес, из-за чего виртуальная машина либо попадала в бесконечный цикл, либо создавался runtime exception:



Насколько всё плохо, станет понятно, как только вы посмотрите на код, генерирующий некоторые инструкции до «Посетителя»:

public override List<Instruction> ToInstructions(int start, string temp)
{
    var instructions = new List<Instruction>();

    (IValue left, IValue right) right = (null, null);
    if (_expression.Primary())
    {
        right.right = ((PrimaryExpression) _expression).ToValue();
    }
    else
    {
        instructions.AddRange(_expression.ToInstructions(start, temp));
        if (_expression is MemberExpression member && member.Any())
        {
            var i = start + instructions.Count;
            var dest = "_t" + i;
            var src = instructions.Any()
                ? instructions.OfType<Simple>().Last().Left
                : member.Id;
            var instruction = member.AccessChain.Tail switch
            {
                DotAccess dot => new Simple(dest, (new Name(src), new Constant(dot.Id, dot.Id)), ".", i),
                IndexAccess index => new Simple(dest, (new Name(src), index.Expression.ToValue()), "[]", i),
                _ => throw new NotImplementedException()
            };
            instructions.Add(instruction);
        }
        right.right = new Name(instructions.OfType<Simple>().Last().Left);
    }

    var number = instructions.Any() ? instructions.Last().Number + 1 : start;

    instructions.Add(new Simple(
        temp + number, right, _operator, number
    ));
    return instructions;
}

А как хорошо стало после применения паттерна, видно в следующем сниппете — код читается подобно тексту на английском языке:

public AddressedInstructions Visit(UnaryExpression visitable)
{
    if (visitable.Expression is PrimaryExpression primary)
        return [new Simple(visitable.Operator, _valueDtoConverter.Convert(primary.ToValueDto()))];
    
    var result = visitable.Expression.Accept(This);
    var last = new Name(result.OfType<Simple>().Last().Left!);
    result.Add(new Simple(visitable.Operator, last));
    
    return result;
}

В чём же магия новой архитектуры и почему это работает? Вернёмся к истокам и освежим в памяти

▍ Классический Visitor


Иллюстрировать это проще в виде картинок, чтобы ставить друг напротив друга посещаемые элементы и их посетители. Есть некая иерархия элементов, и её нужно обработать. Для этого в каждом члене иерархии добавляется виртуальный метод обработки. Этот метод принимает на вход обработчика, который имеет метод обработки элемента с перегрузкой на каждый тип элемента:



Ключевые особенности этого паттерна можно обобщить следующим образом:

  • Решает проблему интрузивного подхода — операция отделена от данных через класс «Посетителя».
  • Работает по схеме double dispatch — полиморфизм подтипов + перегрузка методов (ad-hoc полиморфизм). То есть сначала на абстрактном элементе выбирается нужное переопределение в иерархии, а затем внутри конкретной реализации определяется конкретная перегрузка.
  • Возможно, неочевидно, но можно возвращать значения. Вместо void никто не запрещает написать, например, string.

▍ Недостатки классического Visitor


Нетрудно заметить, что мы мигом получили циклическую зависимость — класс Visitor знает всё про иерархию наследников Element.



Из этого вытекает необходимость постоянного доступа к исходникам обеих иерархий, поскольку любое изменение иерархии посетителей повлечёт за собой изменение иерархии посетителей. Почему я говорю про иерархию посетителей, если на картинке один класс Visitor?

abstract class Element
{
    abstract void Accept(IVisitor visitor);
}

interface IVisitor
{
    void Visit(ElementA elementA);

    void Visit(ElementB elementB);
}

class VisitorOne : IVisitor
{
    public void Visit(ElementA elementA) {}

    public void Visit(ElementB elementB) {}
}

class VisitorTwo : IVisitor
{
    public void Visit(ElementA elementA) {}

    public void Visit(ElementB elementB) {}
}

▍ Ациклический Visitor


Устраняет недостатки классического варианта, связанные с возникающей циклической зависимостью. Вводятся две новые абстракции для посетителя, которые проводят архитектурную границу, отделяя контракт от реализации. Одна абстракция используется на принимающей стороне, а вторая нужна для «сборки» своего кастомного посетителя. Такой декларативный подход позволяет с помощью системы типов описать, какие элементы умеет посещать тот или иной посетитель. Буквально, конструктор LEGO.



Теперь стало гораздо лучше — иерархия элементов ничего не знает про иерархию обработчиков и то, как её могут обрабатывать, а конкретные обработчики выбирают только определённые элементы. Однако мы получаем новую проблему.

public class ElementA : Element
{
    public override void Accept(IVisitor visitor)
    {
        if (visitor is IVisitor<ElementA> typed)
            typed.Visit(this);
    }
}

Конечно же, речь про потерю типобезопасности в compile-time и перенос проверки типов в runtime.

▍ Проблема downcasting


Игнорируя полиморфизма подтипов, мы теряем его суть — отсутствие необходимости задумываться о конкретном типе объекта. Подобные явные приведения сигнализируют о возможно плохой архитектуре (недостаточно объектно-ориентированной или слишком противоречивой). Ну и, конечно, такой код является лазейкой для трудноуловимых багов, которые проявляются только при запуске приложения.

При каких обстоятельствах стоит рассмотреть downcasting?

  • Есть 100% корректное знание о конкретном типе объекта в указанном месте программы во время её выполнения (нет).
  • Знание этого факта позволит получить преимущество за счёт использования возможностей объекта, недоступных на этапе компиляции (отчасти).
  • Привести тип на порядок быстрее и проще, чем отрефакторить код с целью удаления явного приведения (нет).

Также появляется и другая проблема — отсутствие возможности юнит-тестирования подобной системы. Например, в метод Accept определённого элемента добавился сквозной функционал, однако в такой конфигурации мокирование просто не скомпилируется:



Дело в том, что обработчик данного элемента неприводим к типу IVisitor, а сам IVisitor является маркерным интерфейсом без каких-либо членов:



Возникает болезненная ситуация.

Язык ОО, паттерн ОО, а код не ОО


(ОО — объектно-ориентированный)

Почему всё ломается, когда хочется немного выйти за рамки учебников и немного обобщить существующий подход? Поставим задачу это починить. Требования следующие:

  • Сохранить все преимущества ациклического варианта (гибкость, избирательность, декларативность, удовлетворение OCP и LSP и так далее).
  • Оставить все проверки типов на этапе компиляции (воспользоваться полноценно преимуществами статической типизации).

Внезапно, в решении поставленной задачи нам поможет вариантность формальных типовых параметров в C#.

▍ Контравариантность


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

interface IFooIn<in TInputType>
{
    void Bar(TInputType input);
}

Пример из стандартной библиотеки — IComparable, где благодаря контравариантности можно сделать так:

IComparable<IEnumerable<char>> charEnumerableComparable = // ...;

// ...

IComparable<string> stringComparable = charEnumerableComparable;

▍ Ковариантность


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

interface IFooOut<out TOutputType>
{
    TOutputType Baz();
}

Пример из стандартной библиотеки — IEnumerable, где благодаря ковариантности можно сделать так:

IEnumerable<Task<object>> tasksWithResults = // ...;

// ...

IEnumerable<Task> tasks = tasksWithResults;

▍ Чем это полезно?


Во-первых, первую и вторую вариантность можно совмещать в рамках одного типа данных:

interface IFooInOut<in TInputType, out TOutputType>
{
    TOutputType Foo(TInputType input);
}

Во-вторых, это, конечно же, производительность при вариантном приведении типов, как было показано в примерах со стандартной библиотекой. Дело в том, что при использовании вариантности никаких дополнительных IL инструкций не генерируется.

Вообще, какие способы приведения типов у нас есть?

  • Прямое (Direct) приведение, когда оба выражения имеют одинаковый тип.
  • Неявное (Implicit) приведение, когда тип одного из выражений эквивалентен типу другого выражения.
  • Явное (Explicit) приведение через оператор явного приведения (Type). В таком случае в IL генерируется инструкция castclass.
  • Безопасное (As) приведение через оператор as, когда в отличие от явного приведения при неудаче получим null вместо исключения. В таком случае в IL генерируется инструкция isinst.
  • Динамическое (Dynamic) приведение через определение типа во время выполнения программы с помощью ключевого слова dynamic. Соответственно, определение типа переходит на уровень IL.

Мне стало интересно, какова производительность каждого из указанных сценариев приведения типов? Я составил бенчмарк, который её проверяет, код можно найти под спойлером:

Код бенчмарка
using System.Diagnostics.CodeAnalysis;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<CastingBenchmarks>();

[SuppressMessage("ReSharper", "ReturnValueOfPureMethodIsNotUsed")]
[SuppressMessage("Performance", "CA1822:Пометьте члены как статические")]
#pragma warning disable CA1050
public class CastingBenchmarks
#pragma warning restore CA1050
{
    private static readonly ICovariant<Task<object>> SpecificCovariant = new Covariant<Task<object>>();
    private static readonly ICovariant<Task> GeneralCovariant = SpecificCovariant;

    private static readonly IContravariant<IEnumerable<char>> GeneralContravariant = new Contravariant<IEnumerable<char>>();
    private static readonly IContravariant<string> SpecificContravariant = GeneralContravariant;

    [Benchmark(Baseline = true)]
    public void Direct()
    {
        SpecificCovariantMethod(SpecificCovariant);
        GeneralContravariantMethod(GeneralContravariant);
    }

    [Benchmark]
    public void Implicit()
    {
        GeneralCovariantMethod(SpecificCovariant);
        SpecificContravariantMethod(GeneralContravariant);
    }

    [Benchmark]
    public void Explicit()
    {
        SpecificCovariantMethod((ICovariant<Task<object>>)GeneralCovariant);
        GeneralContravariantMethod((IContravariant<IEnumerable<char>>)SpecificContravariant);
    }

    [Benchmark]
    public void As()
    {
        SpecificCovariantMethod((GeneralCovariant as ICovariant<Task<object>>)!);
        GeneralContravariantMethod((SpecificContravariant as IContravariant<IEnumerable<char>>)!);
    }

    [Benchmark]
    public void Dynamic()
    {
        SpecificCovariantMethod((dynamic)GeneralCovariant);
        GeneralContravariantMethod((dynamic)SpecificContravariant);
    }

    // ReSharper disable once UnusedTypeParameter
    private interface ICovariant<out T>;

    private class Covariant<T> : ICovariant<T>;

    private static void SpecificCovariantMethod(ICovariant<Task<object>> input) =>
        input.ToString();

    private static void GeneralCovariantMethod(ICovariant<Task> input) =>
        input.ToString();

    // ReSharper disable once UnusedTypeParameter
    private interface IContravariant<in T>;

    private class Contravariant<T> : IContravariant<T>;

    private static void SpecificContravariantMethod(IContravariant<string> input) =>
        input.ToString();

    private static void GeneralContravariantMethod(IContravariant<IEnumerable<char>> input) =>
        input.ToString();
}


Моя гипотеза была следующей: Dynamic самый медленный, Implicit и Direct чуть быстрее Explicit и As. Результат её подтвердил:

BenchmarkDotNet v0.13.11, macOS Ventura 13.7.2 (22H313) [Darwin 22.6.0]
Apple M1 Pro, 1 CPU, 10 logical and 10 physical cores
.NET SDK 9.0.200
  [Host]   : .NET 9.0.2 (9.0.225.6610), Arm64 RyuJIT AdvSIMD
  ShortRun : .NET 9.0.2 (9.0.225.6610), Arm64 RyuJIT AdvSIMD

Job=ShortRun  IterationCount=3  LaunchCount=1  
WarmupCount=3

Method Mean Ratio
Direct 5.226 ns 1.00
Implicit 5.234 ns 1.00
Explicit 5.266 ns 1.01
As 5.261 ns 1.01
Dynamic 14.278 ns 2.73

Решение — Visitor.NET


Совмещение контравариантности и ковариантности открыло для меня новые возможности в проектировании абстракций. Я пошёл дальше оригинальной идеи ациклической версии паттерна и ввёл абстракцию для посещаемого элемента — IVisitable. Итоговые контракты вышли следующими:

public interface IVisitable<out TVisitable>
    where TVisitable : IVisitable<TVisitable>
{
    TReturn Accept<TReturn>(IVisitor<TVisitable, TReturn> visitor);
}

public interface IVisitor<in TVisitable, out TReturn>
    where TVisitable : IVisitable<TVisitable>
{
    TReturn Visit(TVisitable visitable);
}

Во-первых, теперь элемент может принимать только тот обработчик, который умеет его обрабатывать — больше никакого downcasting.

Во-вторых, благодаря контравариантности мы можем оперировать через публичные базовые контракты, исключая необходимость знания об обоих иерархиях.

Получается схема triple dispatch:

  1. В иерархии элементов полиморфно выбирается нужный наследник Accept.
  2. В Accept был передан «базовый» визитор для корня иерархии, и благодаря контравариантности он отправляется в перегрузку Accept наследника, где он превратится в посетителя этого конкретного наследника.
  3. Внутри конкретной перегрузки Accept вызывается перегрузка Visit согласно типу элемента.

public abstract class Element : IVisitable<Element>
{
    public abstract TReturn Accept<TReturn>(
        IVisitor<Element, TReturn> visitor);
}

public class ElementA : Element, IVisitable<ElementA>
{
    public override TReturn Accept<TReturn>(
        IVisitor<Element, TReturn> visitor) =>
        Accept(visitor);

    public TReturn Accept<TReturn>(
        IVisitor<ElementA, TReturn> visitor) =>
        visitor.Visit(this);
}

Мне даже не нужно описывать пример посетителя, чтобы донести суть — всё строится на контрактах и абстракциях. Всё же, с точки зрения самого визитора ничего не поменялось, всё такой же ациклический.

public class ElementVisitor : VisitorNoReturnBase<Element>,
    IVisitor<ElementA>
{
    public VisitUnit Visit(ElementA visitable)
    {
        return default;
    }
}

▍ Visitor.NET + SourceGenerators!


Вы могли заметить недостаток — для каждого элемента иерархии необходимо реализовывать две перегрузки метода Accept с достаточно трудночитаемой сигнатурой из-за дженериков. Однако этот недостаток уже решён с помощью Source Generators!

Теперь на наследников достаточно повесить атрибут [AutoVisitable] с указанием корня иерархии в угловых скобках:

[AutoVisitable<Element>]
public partial class ElementA : Element;

[AutoVisitable<Element>]
public partial class ElementB : Element;

Можно ли без указания корня иерархии? Нет, поскольку это сильно затруднило бы разработку генератора. Дело в том, что разработчик может проектировать «промежуточные ступени» иерархии, вынося некий общий функционал в абстрактные подклассы:

[AutoVisitable<Element>]
public partial class ElementA : ParticularElement;

public abstract class ParticularElement : Element;

▍ А мультиметоды?


Когда я рассказал про библиотеку в своём Телеграм-канале, один подписчик задал интересный вопрос:



Что такое вообще мультиметоды? Мультиметод — это механизм динамического определения нужной функции в зависимости от типа переданных значений, расширяющий полиморфизм подтипов.

Начнём с того, что в C# такой функции нет, её можно эмулировать с помощью ключевого слова dynamic. Допустим есть некая абстракция над числом, тогда мультиметод обеспечит работу абстрактного метода сложения.

public interface INumber
{
    INumber Add(INumber number);
}

record MyInt(int Val) : INumber;
record MyRational(int Num, int Den) : INumber;

По сути, нам нужно подобрать перегрузку в рантайме, что можно было бы сделать так:

record MyInt(int Val) : INumber
{
    public INumber Add(INumber number) => Add((dynamic)number);

    private INumber Add(MyInt myInt) => new MyInt(Val + myInt.Val);

    private INumber Add(MyRational myRational) =>
        myRational with { Num = Val * myRational.Den + myRational.Num };
}

Этот подход не удовлетворяет поставленным условиям задачи, а также имеет низкую производительность из-за динамического приведения типов, как было показано в бенчмарке выше. Поэтому подобный вариант мной не рассматривается.

Итоги


  • Освежили свои знания о паттерне Visitor.
  • Познакомились с кейсами его применения.
  • Увидели абсолютно новую ациклическую версию паттерна без downcasting’а.
  • Погрузились в проблематику мультиметодов.
  • Вспомнили, что вариантность работает быстро, так как отсутствует приведение типов.
  • Ну и, конечно, на Джаве такого не напишешь!

Поставить звезду GitHub репозиторию проекта можно по ссылке: github.com/stepami/visitor-net.

Ссылки на NuGet пакеты:


Ещё я веду Telegram-канал StepOne, куда выкладываю много интересного контента про коммерческую разработку на C#, даю карьерные советы, рассказываю истории из личного опыта и раскрываю все тайны IT-индустрии.

© 2025 ООО «МТ ФИНАНС»

Telegram-канал со скидками, розыгрышами призов и новостями IT 💻
Теги:
Хабы:
+46
Комментарии11

Публикации

Информация

Сайт
ruvds.com
Дата регистрации
Дата основания
Численность
11–30 человек
Местоположение
Россия
Представитель
ruvds