пятница, 30 апреля 2010 г.

Visitor revisited

Сегодня я покажу свое видение паттерна Visitor. У меня складывается впечатление о том что в значительном количестве источников он представлен не самым удачным образом.

Рассмотрим пример из википедии. К сожалению, это типичный такой примерчик посетителя не без недостатков. Я бы даже сказал с ошибками.
Первая и не самая серьезная ошибка примера – то что вложенные элементы Car хранятся в массиве и паттерн Visitor – не лучший способ для перебора этих элементов. Куда проще и нагляднее было бы прикрутить паттерн Composite.
Вторая ошибка серьезнее – обход структуры заложен в методах accept. Я не считаю метод accept подходящим местом для расположения логики обхода структуры.
Я обозначил их для того, чтобы пробегая дальше по определениям сосредотачивать внимание именно на этом аспекте.

Вернемся к началу статьи в Wikipedia:
In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure it operates on. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures.
Т.е. нам обещают что операции можно прикручивать на существующую структуру. Однако пример демонстрирует что мы не можем прикрутить обход извне. Более того, расположенная логика обхода в методе accept мешает выполнять другие операции над одиночными элементами структуры. Будучи примененный к Car посетитель CarElementPrintVisitor неизбежно выведет в консоль имена всех элементов машины, хотим мы этого или нет. Любая новая операция обречена выполняться над всей структурой. И об этом ничего не сказано в “определении”. В определении вообще ни слова про обход структуры, но как видно из примера, ничего кроме обхода паттерн делать не умеет. Но зато умеет их делать по-разному.

GoF
Назначение
Описывает операцию, выполняемую с каждым объектом из некоторый структуры. Паттерн посетитель позволяет определить новую операцию, не изменяя классы этих объектов.
Опять ничего про обход в назначении паттерна. Зато об обходе написано далее:
Результаты
  • Упрощает добавление новых операций. …
  • Объединяет родственные операции и отсекает те, которые не имеют к ним отношения. …
  • добавление новых классов ConcreteElement затруднено …
  • Посещение различных иерархий классов.
Аж на 4-м месте в списке результатов применения после отрицательного результата.
И далее:
Реализация
….
Какой участник несет ответственность за обход структуры. Посетитель должен обойти каждый элемент структуры объектов. Вопрос в том, как туда попасть.
Вот как, должен? А как же операции, не связанные с обходом?
Ответственность за обход можно возложить на саму структуру объектов, на посетителя и на отдельный объект итератор.
На саму структуру объектов – мы уже видели как это делается и к чему приводит.
Другое решение – воспользоваться итератором для посещения элементов. … Поскольку внутренние итераторы реализуются самой структурой объектов, то работа с ними во многом напоминает предыдущее решение, когда за обход отвечает структура.
Ну а почему тогда не композит?
Можно даже поместить алгоритмы обхода в посетитель, хотя закончится это дублированием кода обхода в каждом классе ConcreteVisitor для каждого агрегата ConcreteElement. Основная причина такого решения – необходимость реализовать особо сложную стратегию обхода (?!?!?!?), зависящую от результатов операций над объектами структуры. Этот случай рассматривается в разделе “Пример Кода”.
Если честно, то я не понимаю, откуда дублирование. И в разделе “Пример Кода” обход реализован в методах accept.

Джошуа Кериевски (Рефакторинг с использованием шаблонов) считает что все знакомы с назначением паттерна и пишет просто:
Переместить задачу накопления в реализацию шаблона Visitor, который для накопления информации может посетить каждый класс.
Да и рассматривает он Visitor только лишь в аспекте Move Accumulation to Visitor.

Роберт К. Мартин (Быстрая разработка программ. Принципы, примеры, практика)
Семейство Visitor позволяет добавлять к существующим иерархиям новые методы без обновления этих иерархий.
Отлично, новые методы без обновления этих иерархий! Кстати, чуть ли не единственный случай, где пример Visitor-а не содержит обхода. СОВСЕМ НЕ СОДЕРЖИТ.

The Visitor pattern and multiple dispatch
Its purpose is to provide new operations on a class or set of related classes without actually altering the classes involved.
Пример тоже не содержит обхода.

Попытаемся осмыслить

Итак, все рассмотренные источники (кроме Д. Кериевски) утверждают что паттерн предназначен для обеспечения новых операций без изменений классов структуры объектов. Для меня это ключевая особенность паттерна. Вот почему:

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

Какие еще бывают зайцы кроме обхода?
  • Валидация объектов (существуют разные причины по которым валидацию следует рассматривать как внешнюю по отношению к объектам операцию)
  • Вызов метода сохранения объекта в БД, Log файл, рисование на специализированных устройствах
  • Размазывание объектов по View-шкам GUI и собирание информации с вьюшек обратно в объект (это только пример, совсем не значит что я так делаю)
  • Получение локализованного наименования объекта
В общем все то, что нужно делать специальным способом в зависимости от типа объекта, но что по каким-то причинам не следует вставлять в методы объекта(ов).

Пример: есть Order и Product, которые не знают своих имен, но их надо как-то назвать чтобы представить пользователю. Операция получения названия объекта – внешняя по отношению к Order-у. Все к тому, чтобы воспользоваться посетителем еще раз (если он уже есть). Но если в методе accept класса Order-а реализован обход, то получить название Order-а мы сможем только в случае когда у Order-а нет вложенных объектов.

Если нужен обход структуры, то я за то, чтобы сделать его одной из операций, так чтобы можно было совмещать обход с другими операциями, либо выполнять другие операции отдельно от обхода. Так же выделение обхода в отдельную операцию приведет к возможности менять алгоритм обхода.

Приведу исходный код примера из википедии, но на C# и значительно упрощенный так, чтобы в нем осталась лишь суть паттерна и ничего более:
interface ICarElementVisitor
{
    void Visit(Wheel wheel);
    void Visit(Engine engine);
}

interface ICarElement
{
    void Accept(ICarElementVisitor visitor);
}

class Wheel : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class Engine : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class CarElementPrintVisitor : ICarElementVisitor 
{
    public void Visit(Wheel wheel)
    {
        Console.WriteLine("wheel");
    }
    public void Visit(Engine engine)
    {
        Console.WriteLine("engine");
    }
}

class Test
{
    public static void TestVisitor()
    {
        var elements = new ICarElement[] {new Engine(), new Wheel()};
        var visitor = new CarElementPrintVisitor();
        foreach (var carElement in elements)
        {
            carElement.Accept(visitor);
        }
    }
} 
Выше приведена квинтэссенция классического посетителя, лишенная недостатков примера из википедии. Ну конечно, некоторой функциональности я его тоже лишил (ниже я ее восстановлю).

Что мне еще не нравится в этом коде?
Метод
void Visit(Wheel wheel);
не позволяет получить результат применения паттерна напрямую. Единственный способ что-то получить – накопить это что-то в конкретном классе посетителя, либо извне (например в глобальной переменной) и потом забрать значение. Было бы лучше, если бы визитор умел возвращать результат операции. Но опять-таки, если операции разные, то и типы результатов у них будут разные. Тип возвращаемого результата должен передаваться generic параметром интерфейса (а не метода!!! Важно, чтобы все методы Visit интерфейса посетителя меняли тип результата синхронно, а не по отдельности):
TResult Visit(Wheel wheel);

Отлично. Еще бы уметь передать дополнительный аргумент. Хотя это как раз лишнее. Аргумент можно передать непосредственно в класс посетителя.

Итак, интерфейс посетителя будет выглядеть так:
interface ICarElementVisitor<out TResult> 
{
    TResult Visit(Wheel wheel);
    TResult Visit(Engine engine);
    TResult Visit(Car car); 
}
А лучше чуть по-другому:
interface IVisitor<in TVisitable, out TResult>
{
    TResult Visit(TVisitable visitable);
}

interface ICarElementVisitor<out TResult> :
    IVisitor<Wheel, TResult>,
    IVisitor<Engine, TResult>,
    IVisitor<Car, TResult>
{
    //TResult Visit(Wheel visitable);
    //TResult Visit(Engine visitable);
    //TResult Visit(Car visitable);
}
Функционально разницы никакой, просто я побаиваюсь напутать что-то с сигнатурой одного из методов, а вынесение метода Visit в отдельный интерфейс позволяет исключить некоторые ошибки.
(+) ключевые слова in/out в объявлении интерфейса

Если кого-то смущают ключевые слова in и out в списке generic параметров интерфейса, то об этом можно почитать здесь. Для этой статьи они никакой роли не играют и должны быть удалены при использовании кода в версиях языка C# 2.0-3.0
(-) ключевые слова in/out

Интерфейс элемента напротив не должен зависеть от generic параметров, но метод Accept должен уметь работать с разными типами посетителей:
interface ICarElement
{
    TResult Accept<TResult>(ICarElementVisitor<TResult> visitor);
}

Вот собственно реализация конкретного элемента паттерна:
class Wheel : ICarElement
{
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}
Ничего кроме метода Accept! Все как и в стандартных примерах, только угловых скобочек побольше.

Дальше будет элемент посложнее. Помните, в определениях говорилось о том, что паттерн visitor можно применять к существующим структурам не модифицируя их? Покажу как это можно сделать не модифицируя элемент совсем (с помощью адаптера).
class Engine
{
}

class EngineAdapter : ICarElement
{
    public EngineAdapter(Engine engine)
    {
        Engine = engine;
    }
    public Engine Engine { get; private set; }

    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(Engine);
    }
}
Можно было интерфейс ICarElementVisitor замкнуть на EngineAdapter вместо Engine, если бы это играло какую-то роль.

Теперь составной элемент Car. Обратите внимание на то, что метод Accept не содержит логики обхода!
class Car : ICarElement
{
    public Wheel[] Wheels = Enumerable.Range(1, 4).Select(_ => new Wheel()).ToArray();
    public Engine Engine = new Engine();
        
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}

Дальше код визитора, достающего имена объектов:
class GetNameVisitor : ICarElementVisitor<string>
{
    public string Visit(Wheel visitable)
    {
        return "wheel";
    }

    public string Visit(Engine visitable)
    {
        return "engine";
    }

    public string Visit(Car visitable)
    {
        return "car";
    }
}

Дальше чуть сложнее. Посетитель, который из элементов достает наборы вложенных элементов:
class GetChildrenVisitor : ICarElementVisitor<IEnumerable<ICarElement>>
{
    public IEnumerable<ICarElement> Visit(Wheel visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Engine visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Car visitable)
    {
        yield return new EngineAdapter(visitable.Engine);
        foreach (var wheel in visitable.Wheels)
        {
            yield return wheel;
        }
    }
}
Здесь следует обратить на метод посещения составного объекта Car. Проходя по engine элементу он возвращает не сам элемент, а адаптер.

Ну и в конце-концов метод, который демонстрирует поведение паттерна:
public static void TestVisitor()
{
    var childrenVisitor = new GetChildrenVisitor();
    var nameVisitor = new GetNameVisitor();

    ICarElement car = new Car();

    var elements = car.Walk(e => e.Accept(childrenVisitor));
    var elementNames = elements.Select(e => e.Accept(nameVisitor));

    foreach (var elementName in elementNames)
    {
        Console.WriteLine(elementName);
    }
}

static IEnumerable<T> Walk<T>(this T root, Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new[] { root }.Concat(q);
}
Во-первых создаются экземпляры посетителей и составного элемента Car. Далее с помощью метода Walk, представляющего дерево в виде одиночной последовательности и описанного в предыдущем посте, а так же посетителя GetChildrenVisitor, строится набор элементов. Затем набор элементов преобразовывается в набор имен с помощью GetNameVisitor и выводится в консоль циклом foreach.

Итог

Итак, я восстановил функциональность примера из википедии, но избежал недостатков. Перечислю еще раз достоинства такого подхода:
  • метод accept не содержит логики обхода (это достоинство само по себе, как и вытекающие из него следствия);
  • логика обхода содержится снаружи иерархии, и это позволяет менять ее не изменяя объектов иерархии;
  • внешний обход не мешает выполнению других операций, реализованных с помощью паттерна, и более того, позволяет комбинирование обхода с другими операциями;
  • посетитель, возвращающий результат, позволяет избавиться от накопления данных внутри объектов либо внутри самого посетителя и использовать мощь LINQ в обходе иерархии;
  • посетитель, возвращающий generic результат, позволяет удобно совмещать одним паттерном множество разнотипных операций.
Замечу так же, что никакого дублирования логики обхода в каждом классе ConcreteVisitor, как это было написано в GoF, не намечается.

Надеюсь, что моя статья позволит читателям использовать паттерн Visitor более эффективно.

З.Ы.
Респект тем кто дочитал до конца.

5 комментариев:

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

    ОтветитьУдалить
  2. Источники нужно выбирать правильные: http://rsdn.ru/article/patterns/VisitorPattern.xml ;о)

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

    А красоту реализации всё-таки портит отсутствие проверок на null (в реализации Accept, например) :о(

    ОтветитьУдалить
  3. _FRED_>Источники нужно выбирать правильные
    Спасибо за ссылку, примеров там действительно больше, чем в других источниках, по которым я ходил. Но ничего нового для себя я там не нашел.
    Те примеры с обходом в посетителе плохи тем что обход требуется совмещать с другими функциями, даже в том случае когда он вынесен в супертип. Менять обход невозможно без переписывания иерархии. Считаю что отделить обход от котлет у автора не получилось.

    _FRED_>Там ещё интересный вариант визитора с контекстом, который оказывается более общим, чем с возвращаемым значением и позволяет передавать не только получать данные из визитора, но и передавать их в него.
    Прикрутить дополнительный контекст к моему примеру несложно. И я делал это, но потом отказался от такого подхода, т.к. передать контекст можно непосредственно в экземпляр посетителя. Необходимо передавать его в метод Accept только лишь в случае накопления информации в контексте и одновременном стремлении к иммутабельности, т.е в качестве агрегирующего параметра. Но в таком случае Accept-у потребуется результат. Да и забирать результат работы через результат Accept гораздо удобнее, чем забирать его у контекста или посетителя.

    _FRED_>А красоту реализации всё-таки портит отсутствие проверок на null (в реализации Accept, например) :о(
    Последнее время я не пытаюсь в блогах вставлять продакшн код для copy&use. Вместо этого я пытаюсь акцентировать внимание на идее, полагая что читатели добавят все необходимое (вроде проверок на null) сами. Да и в статье
    на rsdn
    тоже нет ни одной проверки на null.

    З.Ы. приятно видеть в своих читателях эксперта с rsdn.

    ОтветитьУдалить
  4. Лёш, у тебя там опечатка в листинге "Покажу как это можно сделать не модифицируя элемент совсем (с помощью адаптера)." в строке 15 аргумент должен быть Engine, а не Element

    ОтветитьУдалить
  5. Спасибо, не пойму как прокралась... Прям Соколинный Глаз!

    ОтветитьУдалить