Показаны сообщения с ярлыком Generics. Показать все сообщения
Показаны сообщения с ярлыком Generics. Показать все сообщения

вторник, 8 июня 2010 г.

Посещение чуждых иерархий или посетитель, которого не ждут

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

На той же предметной области, что и в прошлом посте, покажу в чем проблема: требовалось класс Engine, который ничего не знает о посетителе, привести к интерфейсу ICarElement, который обеспечивает метод Accept, обращающийся к методу посетителя ICarElementVisitor<TResult>, соответствующий типу Engine. Адаптер решал эту проблему, однако, при необходимости адаптировать к интерфейсу ICarElement значительное количество классов (даже 10), без кодогенератора будет скучно. Каждый адаптер – 12 линий кода. 120 линий кода для адаптации 10 классов – явный перебор, если есть другие решения. А они есть!

Восстановим и упростим предметную область примера:
class CarElement
{ 
}

class Wheel : CarElement
{
}

class Engine : CarElement
{
}
    
class Car : CarElement
{
    public Wheel[] Wheels = Enumerable.Range(1, 4).Select(_ => new Wheel()).ToArray();
    public Engine Engine = new Engine();
}
Я оставил супертип у иерархии частей машины. Он играет только роль обобщающего типа. Если супертипа в вашей иерархии нет - можно вместо него использовать System.Object. Никакой ответственности на супертип CarElement не накладывается. Никаких методов типа Accept он не предоставляет. Считаем, что создатель этой иерархии не задумывался о применении паттерна посетитель.

Но нам хочется воспользоваться паттерном посетитель. Воспроизведу код из предыдущего поста. Единственное отличие – для класса Engine не используется адаптер.
interface ICarElementVisitor<out TResult>
{
    TResult Visit(Wheel visitable);
    TResult Visit(Engine visitable);
    TResult Visit(Car visitable);
}

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<CarElement>>
{
    public IEnumerable<CarElement> Visit(Wheel visitable)
    {
        yield break;
    }

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

    public IEnumerable<CarElement> Visit(Car visitable)
    {
        yield return visitable.Engine;
        foreach (var wheel in visitable.Wheels)
        {
            yield return wheel;
        }
    }
}
Еще раз хочу обратить внимание на то что код конкретных посетителей не зависит от способа диспетчеризации вызовов, и потому инвариантен к диспетчеризации. За диспетчеризацию будет отвечать следующий метод-расширение:
static class CarElementExtensions
{
    public static T Accept<T>(this CarElement element, ICarElementVisitor<T> visitor)
    {
        var wheel = element as Wheel;
        if(wheel != null)
            return visitor.Visit(wheel);

        var engine = element as Engine;
        if (engine != null)
            return visitor.Visit(engine);

        var car = element as Car;
        if (car != null)
            return visitor.Visit(car);

        throw new NotSupportedException();
    }
}
Осталось повторить код теста. Он остался неизменен.
static class Test
{
    public static void TestVisitor()
    {
        var childrenVisitor = new GetChildrenVisitor();
        var nameVisitor = new GetNameVisitor();

        CarElement 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);
        }
    }

    public 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);
    }
}
Таким образом, для того чтобы добавить обход по некоторому классу, достаточно внести его в интерфейс посетителя ICarElementVisitor и добавить несколько строк в метод расширение Accept. Этот подход существенно экономнее, чем написание адаптеров к непослушным классам. Осталось только сделать замечание, что представленный в этом посте подход нельзя называть классическим посетителем.

Еще один штрих будет полезен тем, кто уже перешел на .NET 4, либо собирается переходить на него. Написание метода-расширения Accept можно водрузить на рантайм! Вот так:
static class CarElementExtensions
{
    public static T Accept<T>(this CarElement element, ICarElementVisitor<T> visitor)
    {
        return visitor.Visit((dynamic)element);
    }
}
Решение о том, какой из методов интерфейса ICarElementVisitor нужно вызывать для конкретного объекта CarElement, будет принято прямо во время выполнения программы. Полагаю, что это несколько снизит производительность, возможно стоит относиться к этому осторожно при посещении больших иерархий.

Последняя деталь – в связи с неожиданным поведением RuntimeBinder-а, не получается использовать следующую форму объявления интерфейса посетителя:
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);
}
Binder считает что у интерфейса ICarElementVisitor нет методов Visit. Это действительно так, но такое поведение отличается от поведения компилятора C#. Подозрение о том что это баг есть не только у меня.

Код с динамической диспетчеризацией вполне работоспособен с первым объявлением интерфейса ICarElementVisitor в этом посте.

пятница, 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 более эффективно.

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

понедельник, 12 апреля 2010 г.

LINQ-ом по деревьям (часть 2)

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

Walk

С прошлого поста заменил Enumerable.Repeat(root, 1) на new [] {root}.
public 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);
}

Walk2

Слегка оптимизированная версия Walk, где методы SelectMany и Concat развернуты в конечный автомат yield return:
public static IEnumerable<T> Walk2<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    yield return root;
    foreach (var child in next(root))
    {
        foreach (var node in Walk2(child, next))
        {
            yield return node;
        }
    }
}
Эта версия Walk метода покажет нам ценность такого переписывания. Я не буду пропагандировать ни за ни против, просто предоставлю данные, а решать пусть будет каждый сам за себя, пользоваться ли высокоуровневыми методами, либо эквивалентными циклами.

WalkS

WalkS – обход с помощью структуры Stack<T>. Это самый простой способ преобразования callstack-а в структуру данных.
public static IEnumerable<T> WalkS<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current).Reverse())
        {
            stack.Push(x);
        }
    }
}
Здесь использован метод Enumerable.Reverse чисто для сохранения порядка обхода в соответствии с оригинальным методом Walk. Но гоняться в бенчмарке будет немного другой метод:

WalkS2

У этой модификации используется 2 стека (Stack<T>). Второй заменяет Enumerable.Reverse.
public static IEnumerable<T> WalkS2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    var stack2 = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current))
        {
            stack2.Push(x);
        }
        foreach (var x in stack2)
        {
            stack.Push(x);
        }
        stack2.Clear();
    }
}

WalkL

В очередной модификации вместо Stack<T> используется односвязный список.
class ListNode<T>
{
    public T Value { get; private set; }
    public ListNode<T> Next { get; private set; }

    public ListNode(T value, ListNode<T> next)
    {
        Value = value;
        Next = next;
    }
}
public static IEnumerable<T> WalkL<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var current = list;
        list = list.Next;
        yield return current.Value;

        foreach (var x in next(current.Value).Reverse())
        {
            list = new ListNode<T>(x, list);
        }
    }
}
Но воевать будет не она, а та что использует 2 односвязных списка:

WalkL2

Последняя модификация, учавствующая в бенчмарке использует один список для замены callstack-а, другой вместо Enumerable.Reverse().
public static IEnumerable<T> WalkL2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var currentNode = list;
        var nextNode = list.Next;
        yield return currentNode.Value;

        ListNode<T> tmpList = null;
        foreach (var v in next(currentNode.Value))
        {
            tmpList = new ListNode<T>(v, tmpList);
        }

        if(tmpList != null)
        {
            for (; tmpList != null; tmpList = tmpList.Next)
            {
                nextNode = new ListNode<T>(tmpList.Value, nextNode);
            }
        }
        list = nextNode;
    }
}

Depth

В бенчмарке учавствует еще один метод, который тоже обходит дерево, но при этом не пытается выпрямить его узлы в последовательность. Подсчет глубины конкретного двоичного дерева в чисто рекурсивной форме. Этот метод будет эталоном скорости.
Вслед за методом GetDepth привел класс узла дерева, на котором проходил бенчмарк.
public static int GetDepth<T>(this Node<T> node)
{
    return (node == null)
        ? 0
        : 1 + Math.Max(
            node.Left.GetDepth(),
            node.Right.GetDepth());
}

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
}

Забег №1

Случайным образом перемешанный массив индексов [0..N] подается на вход алгоритму, строящему двоичное дерево (без балансировки). Полученное дерево скармливается вышеуказанным методам Walk* и у полученного IEnumerable<int> извлекается последний элемент Enumerable.Last ().
Результаты первого забега (по оси x кол-во элементов, по y – время обхода в секундах):

Следующим образом выглядит таблица времен обхода дерева из 10М элементов:
Метод обхода
Время
Walk
00:00:24.7759974
Walk2 00:00:10.8108170
WalkS2 00:00:03.5185059
WalkL2 00:00:02.7030328
Depth 00:00:01.0753161
Что-то здесь не так. Судя по графику, нерекурсивные методы значительно быстрее, но я не увидел зависимости графиков рекурсивных методов от глубины дерева… И деревья-то подсовывались не слишком глубокие. Глубина дерева из случайно перемешанного набора из 20М индексов не превышала 60. При таком подходе, увеличивая вдвое число элементов, мы будем получать увеличение глубины дерева лишь на единицу. Геометрическая, блин, прогрессия! Страшно подумать, сколько нужно элементов, для того чтобы достичь глубины 1000 :(
Но кое-какие выводы можно сделать и из этого забега:
  • Методы Walk и Walk2 идут ноздря в ноздрю и значительного перевеса не наблюдается, хотя и foreach-и немного опережают высокоуровневые методы SelectMany+Concat.
  • Нерекурсивные методы WalkS2 и WalkL2 достаточно близки к эталонному Depth
  • Односвязные списки немного шустрее чем Stack<T>.

Забег №2

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

Что интересно, рекурсивные методы Walk и Walk2 не осилили дерево глубиной 12000 и отвалились с StackOverflowException. Однако метод GetDepth работал стабильно (полагаю что JIT распознал хвостовую рекурсию и преобразовал рекурсию в цикл это не так, спасибо Пельмешко за внимательность. GetDepth-у для исключения нужно глубину 65000).


Этот эксперимент показывает нелинейную зависимость рекурсивных методов Walk и Walk2 от глубины дерева и совершенно ничего не показывает о нерекурсивных методах WalkS2, WalkL2 и рекурсивном но преобразованном в цикл методе GetDepth. Т.е. их зависимость от глубины на этом графике не видна. Время, которое показывали три последних метода на обходе 10000 элементов не превышало 0.001 секунды.

Итого:

Рекурсивная комбинация перечислителей представляет опасность переполнения стека на глубинах дерева от 10К. На глубинах дерева до 1000 рекурсивными перечислителями вполне можно пользоваться и их производительность хоть и уступает нерекурсивным методам,  но может быть вполне приемлема для множества задач.

P.S.

На RSDN Sinix-ом был приведен другой метод выпрямления рекурсивных комбинаций перечислителей. Нетрудно увидеть схожесть его метода с представленными мной. Отличия в сигнатуре (принимает коллекцию узлов), в порядке обхода (нет Reverse), да и в стек он помещает не узлы, а перечислители узлов. Не знаю, в чем фокус, но его метод работает примерно в 2 раза медленнее WalkS2, представленного мной (с Reverse-ом с помощью дополнительного стека). Ну и собственно название, UngroupRecurseEnumerator сбивает с толку. Это тот же самый обход дерева.

P.P.S.

В этой статье упоминается Range через yield foreach:
static IEnumerable<int> FromTo(int b, int e)
{
    if (b > e)
        yield break;
    yield return b;
    yield foreach FromTo(b + 1, e);
}
А вот и наш ответ Чемберлену
static IEnumerable<int> FromTo(int b, int e)
{
    return b.WalkL2(i =>
         (i < e)
            ? new int[] { i+1 } 
            : new int[] {});
}
Не столь красивый, но не требующий изменения языка.
А yield foreach все-таки сила!

Upd.

Я таки написал версию GetDepth с хвостовой рекурсией:
public static int GetDepthC<T>(this Node<T> node)
{
    return GetDepthCps(node, d => d);
}

static int GetDepthCps<T>(Node<T> node, Func<int, int> cont)
{
    return (node == null)
       ? cont(1)
       : GetDepthCps(node.Left, leftDepth =>
            GetDepthCps(node.Right, rightDepth =>
                cont(Math.Max(leftDepth, rightDepth))));
}
Естественно я не ожидал что C# ее выпрямит в цикл. А вот F# выпрямляет!
Если будут пожелания, можно в другой раз написать что-то вроде "CPS для чайников". Толку, правда, будет немного в рамках C#. Но разжевать предмет можно попробовать.

суббота, 3 апреля 2010 г.

LINQ-ом по деревьям

Сегодня покажу универсальный код обхода любых деревьев с однотипными узлами.
public static class TreeWalker
{
    public static IEnumerable<T> Walk<T>(T root, Func<T, IEnumerable<T>> next)
    {
        var q = next(root).SelectMany(n => Walk(n, next));
        return Enumerable.Repeat(root, 1).Concat(q);
    }
}

За исключением нескольких отличий, этот метод похож на Enumerable.SelectMany. Отличия:
  1. В качестве первого аргумента принимается один элемент (корень дерева), а не последовательность.
  2. Метод рекурсивно применяется ко всем элементам, полученным с помощью делегата next из исходного.

Области применения


Для начала прогуляемся по дереву каталогов файловой системы:

foreach(var dir in TreeWalker.Walk(@"d:\Test", Directory.GetDirectories))
{
     Console.WriteLine(dir);
}

Однако, гулять – не главный бенефит этого метода. Главный – “выпрямлять” деревья для того чтобы по ним можно было гулять LINQ-ом.

Еще один пример - собрать только листовые узлы у TreeView можно такой конструкцией

var q = from rootNode in treeVew1.Nodes.Cast<TreeNode>()
        from node in TreeWalker.Walk(rootNode, n => n.Nodes.Cast<TreeNode>())
        where node.Nodes.Count == 0
        select node;

Совсем не обязательно обходить дерево целиком. Например, при работе с двоичными деревьями поиска, с помощью метода Walk можно находить минимальный, максимальный элемент и даже делать поиск конкретного элемента за время соразмерное  высоте дерева (при сбалансированном дереве – O(log N)).

Пусть у нас есть дерево из узлов следующего вида:

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; private set; }
    public Node<T> Left { get; private set; }
    public Node<T> Right { get; private set; }
}

Тогда для поиска минимального элемента потребуется следующий вспомогательный метод:

public static IEnumerable<Node<T>> NextLeft<T>(this Node<T> root)
{
    if (root.Left != null)
        yield return root.Left;
}

Тогда найти узел с минимальным элементом двоичного дерева можно следующей конструкцией:

TreeWalker.Walk(root, r => r.NextLeft()).Last();

Для поиска узла с конкретным элементом потребуется более хитрая вспомогательная функция, которая будет возвращать подузлы Left или Right в зависимости от результата сравнения значения текущего узла с искомым значением.

А если к функции получения дочерних узлов добавить маркировку пройденных узлов, то из метода Walk получится алгоритм “поиск в глубину” для графов.

Особенности реализации


Вместо Enumerable.Repeat(root, 1) можно было сделать new [] { root}, но я хотел сделать акцент на другом.

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

next(root).SelectMany добавляет в цепочку свои перечислители (полагаю что больше одного, лениво лезть в рефлектор). Над ним надстраивается Сoncat перечислитель.

Даже если дерево состоит только лишь из одного корневого элемента, вызовы IEnumerator<T>.MoveNext(), IEnumerator<T>.Current будут выполнены каскадно через 2-3 (а может и больше) перечислителей.

Итого, обход дерева высотой в несколько сот тысяч элементов с хорошей вероятностью может завершиться StackOverflowException (udated: 12000 элементов достаточно)… Даже если не завершится, цена вызова по цепочке перечислителей длиной в несколько глубин дерева может серьезно сказаться на производительности приложения. Ведь для получения очередного элемента нужно сделать два таких сверхглубоких вызова (MoveNext и Current).

Естественно, ситуацию можно изменить за счет переписывания метода Walk с какой-нибудь структурой данных, эмулирующей стек вызовов (например, Stack<T>). Но я пока в этом необходимости не испытываю. StackOverflowException я видел только на тестовых данных (двоичное дерево из миллиона элементов). А на тех данных, с которыми приходилось работать методу Walk, проблем с производительностью или с переполнением стека нет. Даже не было повода замеров производительности метода Walk с целью выявить зависимость времени выполнения от глубины дерева.

Если кому-то вопрос производительности и/или нерекурсивный вариант Walk метода окажется интересным, дайте знать в комментариях. А пока будем считать что я поделился красивым но не очень быстрым способом обхода деревьев с помощью LINQ-а.

P.S.


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

четверг, 30 апреля 2009 г.

Вывод типов с помощью Fake функций

Рассмотрим один прием, помогающий выводить типы (на авторство не претендую) на примере мемоизации. В двух словах, если кто не вкурсе, мемоизация – это техника оптимизации (подвид кэширования), используемая для избежания вызовов функций с повторяющимися аргументами. Множество примеров реализации мемоизации на C# можно найти здесь. Оттолкнемся от мемоизации функции одного аргумента, описанного Wes Dyer-ом, одним из разработчиков компилятора C#.

public static Func<TKey, TResult> Memoize<TKey, TResult>(this Func<TKey, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new Dictionary<TKey, TResult>();
 TResult result;

 return key => (cache.TryGetValue(key, out result))
     ? result
     : (cache[key] = func(key));
}
Мой вариант отличается только тем, что я переменную result внес в замыкание вместо того, чтобы объявить ее внутри тела возвращаемой функции. Сделал я это только для того, чтобы не писать фигурные скобки в определении тела функции. Все красиво и наглядно, но допустим возникла необходимость мемоизации функции двух переменных.
Мемоизация функции двух аргументов
Решать можно по-разному. Например, модифицировать реализацию мемоизации функции одной переменной, т.е. фактически переписать ее заново:
public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new object[0].ToDictionary(
     x => new { k1 = default(T1), k2 = default(T2) },
     x => default(TResult));

 return (k1, k2) =>
 {
     TResult result;
     var key = new { k1, k2 };

     return (cache.TryGetValue(key, out result))
         ? result
         : (cache[key] = func(k1, k2));
 };
}
Здесь я воспользовался тем, что анонимный тип, который генерируется компилятором обладает всем необходимым для того, чтобы использовать его в качестве ключа словаря. Небольшая сложность заключалась в том, чтобы объявить переменную словаря с анонимным типом ключа, но выручил метод Enumerable.ToDictionary. Но душа захотела реюза описанного ранее метода мемоизации функции одного аргумента. Мне пока известно два способа сделать реюз:
  1. Применить последовательно мемоизацию к каждому аргументу, что привлечет к появлению множества экземпляров словарей (не интересно для дальнейшего обсуждения)
  2. Применить мемоизацию к методу, который принимает аргумент-комбинацию двух аргументов, а возвращает результат вызова метода func, полученный по соответствующей паре аргументов. Далее будем обсуждать метод этот вариант.
Итого, требуется применить мемоизацию к следующему методу (записанному условно):
Func<?, TResult> func2 = (? x) => func(x.t1, x.t2);
Проблема здесь в том, что комбинированный аргумент представлен анонимным типом, указать который проблематично. Стандартных Tuple-ов нет, да и неизвестно, будут ли они обладать теми же свойствами, что и анонимные типы, будет ли возможность использовать их в качестве ключа словаря?

Итого, есть метод с сигнатурой Func<?, TResult>, записать тело которого мы можем, но не можем сказать компилятору, что за тип кроется за знаком “?” (достаточно было бы указать тип хотя бы в одном из мест, отмеченных знаком “?” в определении анонимного метода).

Вот тут-то и выручит нас метод, который ничего не делает:
static Func<T, TResult> MakeFunc<T, TResult>(T _, Func<T, TResult> func)
{
 return func;
}
Метод MakeFunc абсолютно бесполезен во времени выполнения. Однако он помогает вывести тип “?”. Записать этот тип в коде мы все равно не сможем, но это и не требуется.

Вот как компилятор теперь может выявить тип метода: первым аргументом MakeFunc мы указываем экземпляр анонимного типа, а т.к. тип T первого аргумента совпадает с типом аргумента метода Func<T, TResult> второго аргумента метода MakeFunc, то компилятор теперь знает, что подразумевается под типом T в выражении Func<T, TResult>.

Теперь следующее выражение
var func2 = MakeFunc(
 new { A1 = default(T1), A2 = default(T2) },
 x => func(x.A1, x.A2));

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

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var func2 = MakeFunc(
     new { A1 = default(T1), A2 = default(T2) },
     x => func(x.A1, x.A2));

 var func2m = func2.Memoize();

 return (t1, t2) => func2m(new { A1 = t1, A2 = t2 });
}
Здесь находится топик обсуждения мемоизации функции двух аргументов на RSDN (автор – я). Обратите внимание, как легко и изящно решается проблема на языке F#. Вышеописанный метод производит мемоизацию функции аргумента анонимного типа, затем возвращает метод, комбинирующий аргументы в анонимный тип, и передающий экземпляр анонимного типа в мемоизированную функцию.
Вообще говоря, я не думаю, что кому-то из читателей пригодится мемоизация функции двух и более аргументов… Пост немного о другом (как следует из его названия). Пост о том, как можно помочь компилятору вывести необходимый тип, в котором каким-то образом участвуют анонимные типы.
Потому еще один пример, где описанный мной прием может пригодитсья:
Вывод типа IEqualityComparer<?> для анонимного типа.
Преамбула проста: когда-то не так давно я решил, что если не заморачиваться на эффективности, то можно не писать классы компареров каждый раз, а создать адаптер, который бы принимал функции GetHashCode и Equals и представлял бы их экземпляром IEqualityComparer<T>. Выглядит это чудо так:
public static IEqualityComparer<T> CreateAdapter<T>(
 Func<T, T, bool> equals,
 Func<T, int> getHashCode)
{
 if (equals == null)
     throw new ArgumentNullException("equals");

 if (getHashCode == null)
     throw new ArgumentNullException("getHashCode");

 return new EqualityComparerAdapter<T>(equals, getHashCode);
}

class EqualityComparerAdapter<T> : IEqualityComparer<T>
{
 readonly Func<T, T, bool> _equals;
 readonly Func<T, int> _getHashCode;

 public EqualityComparerAdapter(Func<T, T, bool> equals, Func<T, int> getHashCode)
 {
     _equals = equals;
     _getHashCode = getHashCode;
 }

 public bool Equals(T x, T y)
 {
     return _equals(x, y);
 }

 public int GetHashCode(T obj)
 {
     return _getHashCode(obj);
 }
}
Между делом – довольно удобная штука, позволяющая экономить на описании класса, но не в случае когда тип T – анонимный. Вот такой вспомогательный метод
static IEqualityComparer<T> InferComparer<T>(
 T _,
 Func<T, T, bool> equals,
 Func<T, int> gethashCode)
{
 return CreateAdapter(equals, gethashCode);
}
позволяет вывести тип компарера для анонимного типа.
var pairComparer = InferComparer(
 pair,
 (x, y) => x.Key.SequenceEqual(y.Key),
 x => x.Key.Aggregate(0, (h, s) => h ^ s.GetHashCode()));
Эта конструкция создает IEqualityComparer для анонимного типа, свойство Key которого является коллекцией строк. Таким образом сравниваются экземпляры по совпадению коллекций строк, и хэшкод вычисляется по набору строк свойства Key анонимного типа. Далее этот компарер используется для построения словаря.

пятница, 10 апреля 2009 г.

Comparer с обобщенными методами

Последнее время часто использую методы с обобщенными аргументами. Довольно часто приходится сравнивать значения обобщенных типов между собой, сравнивать с default(T). Конструкции типа
while (!EqualityComparer<T>.Default.Equals(t, default(t))
{
    // do something
}
довольно сильно утомляют глаз. Следующий класс здорово облегчает жизнь:
public static class Comparer
{
    public static int Compare<T>(T a, T b)
    {
        return Comparer<T>.Default.Compare(a, b);
    }

    public static bool Equals<T>(T a, T b)
    {
        return EqualityComparer<T>.Default.Equals(a, b);
    }

    public static bool IsNullOrDefault<T>(T value)
    {
        return Equals(default(T), value);
    }
}
Теперь можно писать так:
while (!Comparer.Equals(t, default(t))
{
    // do something
}
И даже так:
while (!Comparer.IsNullOrDefault(t))
{
    // do something
}
Естественно, это имеет смысл только для сравнения компарером по-умолчанию.

воскресенье, 16 ноября 2008 г.

Хранилище записей фиксированной длины (часть III)

Хранилище записей фиксированной длины Хранилище записей фиксированной длины (часть II) Извиняюсь, что затянул с продолжением, совершенно не было времени и сил, особенно после праздников. Напомню, что в предыдущих постах была описана реализация хранилища записей фиксированной длины, выполненного в качестве обертки над Stream-ом с прямым доступом к полям записей. В этот раз опишу как прикрутить к нему простой индекс.
Предварительно хочу сделать акцент на том, что я не пытался создать библиотеку для решения общего случая, а решал конкретную задачу, но как можно более общим образом. В той конкретной задаче, которую я решал, достаточно индекса по одному полю, который бы искал записи по точному совпадению ключа. Уот таким я увидел интерфейс индекса хранилища:
public interface IStorageIndex<TKey>
{
    void Initialize(IEnumerable<TKey> keys, Func<int, TKey> readKeyFunc);

    int GetIndex(TKey key);

    void InsertIndex(TKey key, int rowIndex);
}
Метод инициализации индекса принимает последовательность всех ключей (забегая вперед отмечу, что ленивую последовательность), и метод получения ключа по заданному индексу. Полагаю, что такой метод инициализации должен удовлетворить некоторое кол-во реализаций индексов (строящихся в памяти, или на диске). Метод GetIndex - собственно то, ради чего и задумывался индекс. Он должен вернуть индекс записи с указанным ключем. Метод InsertIndex добавляет в индекс информацию о положении новой записи. Простоты ради я избавился от метода удаления записи из индекса. Простейшая реализация индекса выглядит так (комментировать не буду):
public class DictionaryIndex<TKey> : IStorageIndex<TKey>
{
    private readonly Dictionary<TKey, int> _indices = new Dictionary<TKey, int>();

    public void Initialize(IEnumerable<TKey> keys, Func<int, TKey> readKeyFunc)
    {
        int index = 0;
        foreach(TKey key in keys)
        {
            _indices[key] = index++;
        }
    }

    public int GetIndex(TKey key)
    {
        int result;
        return _indices.TryGetValue(key, out result)
            ? result
            : -1;
    }

    public void InsertIndex(TKey key, int rowIndex)
    {
        _indices.Add(key, rowIndex);
    }
}
Кстати, именно подобный индекс основанный на словаре успешно трудится уже около двух месяцев в некоторых заведениях ;) страны. Теперь опишу базовый класс индексированного хранилища записей. Для индесированного по одной колонке хранилища нам потребуется еще один generic параметр TKey, который будет представлять тип колонки, по которой проводится индексирование. Конструктор индексированного хранилища принимает дополнительные параметры - колонку, по которой проводится индексирование и реализацию индекса:
public class IndexedStorage<THeader, TRow, TKey> : StreamStorage<THeader, TRow>
    where THeader : RowBase<THeader>
    where TRow : RowBase<TRow>
{
    private readonly Column<TKey> _keyColumn;
    private readonly IStorageIndex<TKey> _index;

    protected IndexedStorage(Stream stream, Encoding encoding, Column<TKey> keyColumn, IStorageIndex<TKey> index)
        : base(stream, encoding)
    {
        if(index == null)
        {
            throw new ArgumentNullException("index");
        }
        if(keyColumn == null)
        {
            throw new ArgumentNullException("keyColumn");
        }
   
        if(keyColumn.Columns != RowBase<TRow>.ColumnCollection)
        {
            throw new ArgumentException();
        }
        _keyColumn = keyColumn;
        _index = index;
    }
    ...
}
Методы, потребующиеся для инициализации индекса (чтение ключа записи по указанному номеру и чтение последовательности ключей всех записей)
private TKey ReadKey(int index)
{
    return ReadValue(_keyColumn, index);
}

private IEnumerable<TKey> LoadKeys()
{
    int length = Length;

    using (var notOwnedStream = new NotOwnedStreamProxy(Stream))
    using (var bufferedStream = new BufferedStream(notOwnedStream))
    using (var reader = new BinaryReader(bufferedStream))
    {                   
        byte[] buffer =
            new byte[RowBase<TRow>.ColumnCollection.Size - _keyColumn.Size];
         bufferedStream.Position = RowBase<THeader>.ColumnCollection.Size + _keyColumn.Offset;

        for (int i = 0; i < length; i++)
        {
            yield return _keyColumn.ReadValue(reader);
         
            if (i < length - 1)
            {
                reader.ReadBytes(buffer.Length);
            }
        }
    }
}
второй метод потребует комментариев. Дело в том, что я его изуродовал, пытаясь выжать производительность. Самая простая его реализация - вызов в цикле вышеописанного метода ReadKey(int index) безобразно долго работает. Дело в том, что при таком подходе потребуется большое (по числу записей) количество операций Seek. Хоть изменения позиции и небольшие, но сама операция на FileStream (а это основной сценарий использования этого хранилища) все равно занимает значительное время. Вместо операции Seek я решил использовать чтение в буфер, размер которого равен размеру записи без ключевого поля. Т.е. прочитав первый ключ и вчитав в этот буфер дальнейшее содержимое, позиция потока оказывается ровно перед ключем следующего поля. Еще одна оптимизация - использование буферизованного потока дает небольшое преимущество перед чтением напрямую. Небольшое, но я решил им все же воспользоваться. Потому потребовался другой экземпляр BinaryReader. Вся эта оптимизация привела к следующей проблеме: при освобождении BufferedStream, равно как и BinaryReader-а для чтения из буферизованного стрима, освобождается несущий стрим хранилища. Решений может быть несколько: постараться не освобождать эти сущности (хранить их в полях класса), либо оградить несущий стрим от деструктивных воздействий вспомогательных сущностей. Я предпочел второе, хоть и пришлось много постучать по кнопкам: пришлось реализовать хитрый proxy для класса Stream, который делегирует все методы и свойства низлежащему стриму, за исключением метода Close(). Этот класс я худобедно назвал NotOwnedStreamProxy. Полные его исходники приводить не буду, ограничусь выбранными наугад методами (остальные выглядят похожим образом):
public override void Close()
{
    // BaseStream.Close(); ВСЕ РАДИ ТОГО, ЧТОБЫ НЕ ДОПУСТИТЬ ВЫЗОВ ЭТОГО!!!
    base.Close();
}

public override int EndRead(IAsyncResult asyncResult)
{
    return BaseStream.EndRead(asyncResult);
}

public override void EndWrite(IAsyncResult asyncResult)
{
    BaseStream.EndWrite(asyncResult);
}

public override int ReadByte()
{
    return BaseStream.ReadByte();
}
И не говорите! Сам не в восторге. Метод инициализации базового индексированного хранилища теперь выглядит так:
protected override void Initialize()
{
    lock (SyncRoot)
    {
        base.Initialize();

        _index.Initialize(LoadKeys(), ReadKey);
    }
}
Еще пара нехитрых методов базового индексированного хранилища:
protected int GetIndex(TKey key)
{
    lock(SyncRoot)
    {
        return _index.GetIndex(key);
    }
}

protected TRow InsertRow(TKey key)
{
    int newRowIndex;
    lock(SyncRoot)
    {
        newRowIndex = Length;

        _index.InsertIndex(key, newRowIndex);

        Length += 1;
        WriteValue(_keyColumn, newRowIndex, key);
    }

    return GetRow(newRowIndex);
}
Осталось чуть-чуть. Уже добрались до конкретного индексированного хранилища:
class IndexedStorage : IndexedStorage<TestHeader, TestRow, Guid>
{
    public IndexedStorage(Stream stream)
        : base(
            stream,
            Encoding.Default,
            TestRow.IdColumn,
            new DictionaryIndex<Guid>())
    {
        base.Initialize();
    }

    public TestRow AddNewRow(Guid id)
    {
        return InsertRow(id);
    }

    public TestRow GetRow(Guid id)
    {
        return GetRow(GetIndex(id));
    }
}
Класс TestRow описан в конце первого поста о хранилище записей.
В следующий раз приведу результаты стресс-тестирования этого безобразия в сравнении с SQLite.

вторник, 4 ноября 2008 г.

Хранилище записей фиксированной длины (часть II)

В предыдущем посте (Хранилище записей фиксированной длины) было описано все необходимое для класса хранилища. Теперь можно приступать к реализации хранилища.

Напомню: хранилище - надстройка над классом Stream для хранения типизированных записей фиксированной длины и некого заголовка. Класс хранилища параметризован двумя generic параметрами: типом заголовка хранилища и типом записи хранилища:
public class StreamStorage<THeader, TRow> : StreamStorage, IDisposable
    where THeader : RowBase<THeader>
    where TRow : RowBase<TRow>
{
    private readonly object _syncRoot = new object();
    private readonly Stream _stream;
    private readonly BinaryWriter _writer;
    private readonly BinaryReader _reader;
    private int _length;

    protected StreamStorage(
        Stream stream,
        Encoding encoding)
    {
        _stream = stream;
        encoding = encoding ?? Encoding.Default;

        if (stream.CanWrite)
        {
            _writer = new BinaryWriter(_stream, encoding);
        }
        if (stream.CanRead)
        {
            _reader = new BinaryReader(_stream, encoding);
        }
    }

    public void Dispose()
    {
        if (_writer != null)
        {
            _writer.Close();
        }
        if(_reader != null)
        {
            _reader.Close();
        }
        _stream.Close();
    }
Конструктор хранилища принимает поток данных, в котором хрянятся записи и кодировку для записи строковых полей (реализацию строковых колонок я пока не приводил). Метод Dispose() освобождает ресурсы. Следом короткая форма доступа к экземплярам коллекций колонок заголовка и записи хранилища:
static ColumnCollection HeaderColumns
    {
        get { return RowBase<THeader>.ColumnCollection; }
    }

    static ColumnCollection RowColumns
    {
        get { return RowBase<TRow>.ColumnCollection; }
    }
Затем доступ к ридеру, райтеру и собственно потоку данных:
protected BinaryWriter Writer
    {
        get
        {
            if (_writer == null)
            {
                throw new NotSupportedException();
            }
            return _writer;
        }
    }

    protected BinaryReader Reader
    {
        get
        {
            if (_reader == null)
            {
                throw new NotSupportedException();
            }
            return _reader;
        }
    }

    protected Stream Stream
    {
        get { return _stream; }
    }

    protected object SyncRoot { get { return _syncRoot; } }
Далее серия методов, производящих строки. Есть небольшие проблемы в том каким образом создавать экземпляры TRow и THeader, ведь экземпляры строк требуют экземпляр хранилища и свой индекс при создании, т.е. мы не можем воспользоваться их конструктором по умолчанию.

Можно было параметризовать хранилище фабрикой строк и фабрикой заголовка, но я пришел к решению предусмотреть расширение через Template Method.
protected virtual TRow CreateRowInstance(int index)
    {
        return CreateRowInstance<TRow>(this, index);
    }

    protected virtual THeader CreateHeaderInstance()
    {
        return CreateRowInstance<THeader>(this, 0);
    }

    private static T CreateRowInstance<T>(StreamStorage storage, int index)
        where T : RowBase<T>
    {
        return (T)Activator.CreateInstance(typeof(T), storage, index);
    }

    protected TRow GetRow(int index)
    {
        lock (SyncRoot)
        {
            return CreateRowInstance(index);
        }
    }

    public THeader Header { get; private set; }
Такое решение позволит без дополнительных усилий создавать экземпляры строк, которые принимают в конструкторе экземпляр хранилища и индекс. Пример строки TestRow из предыдущего поста принимает именно такой набор параметров. Если потребуется изменить сигнатуру конструктора записи, то производный класс хранилища сможет перекрыть методы CreateRowInstance и CreateHeaderInstance.

Далее способ управления размером хранилища:
protected int Length
    {
        get
        {
            return _length;
        }
        set
        {
            if (value < 0)
            {
                throw new ArgumentOutOfRangeException("value");
            }

            long streamLength = HeaderColumns.Size + RowColumns.Size * value;

            lock (SyncRoot)
            {
                Stream.SetLength(streamLength);

                _length = value;
            }
        }
    }
Реализация свойства Length практически не нуждается в комментариях. Она устанавливает длину потока данных руководствуясь размером заголовка, размером записи и требуемым кол-вом записей. Метод установки позиции потока для чтения или записи значения:
private void SetPosition(int rowIndex, Column column)
    {
        if (column == null)
        {
            throw new ArgumentNullException("column");
        }

        int pos;
        if (ReferenceEquals(column.Columns, HeaderColumns))
        {
            pos = column.Offset;
        }
        else
        {
            if (ReferenceEquals(column.Columns, RowColumns))
            {
                if (rowIndex < 0 || rowIndex >= Length)
                {
                    throw new ArgumentOutOfRangeException("rowIndex");
                }
                pos = HeaderColumns.Size + RowColumns.Size * rowIndex + column.Offset;
            }
            else
            {
                throw new ArgumentException("", "column");
            }
        }

        if (Stream.Position != pos)
        {
            Stream.Position = pos;
        }
    }
Написано много, но смысл простой: если колонка относится к заголовку, то установить позицию потока к смещению колонки. Если колонка относится к типу записи - установить позицию потока руководствуясь размером заголовка, размером записи, индексом записи и смещением колонки.

Следует заметить, что этот метод не будет работать адекватно при идентичных типах TRow и THeader. Проверку на такое совпадение я опустил. Если потребуется сделать что-то подобное, то лучше указать тип заголовка без колонок.

Теперь сердце хранилища - методы чтения и записи значений:
public override T ReadValue<T>(Column<T> column, int rowIndex)
    {
        if (column == null)
        {
            throw new ArgumentNullException("column");
        }
        lock (SyncRoot)
        {
            SetPosition(rowIndex, column);
            return column.ReadValue(Reader);
        }
    }

    public override void WriteValue<T>(Column<T> column, int rowIndex, T value)
    {
        if (column == null)
        {
            throw new ArgumentNullException("column");
        }
        lock (SyncRoot)
        {
            SetPosition(rowIndex, column);
            column.WriteValue(Writer, value);
        }
    }
Осталось всего ничего - код инициализации хранилища:
protected virtual void Initialize()
    {
        Header = CreateHeaderInstance();

        if (RowColumns.Size == 0)
        {
            CreateRowInstance(0); // вызвать инициализацию колонок записи.
        }

        int headerSize = HeaderColumns.Size;
        if (Stream.Length == 0)
        {
            Stream.SetLength(headerSize);
            Header.Initialize();
        }
        else
        {
            _length = (int)((Stream.Length - headerSize) / RowColumns.Size);

            if (headerSize + Length * RowColumns.Size != Stream.Length)
            {
                throw new InvalidOperationException("Unexpected stream length.");
            }
        }
    }
Сам по себе этот код не сложен, но тащит за собой одну проблему: кто-то его должен вызывать. Но это не может быть конструктор хранилища, потому как метод инициализации использует виртуальные методы. В отличие от C++, в C# виртуальные методы могут быть вызваны из конструктора базового класса, но существует опасность что перекрытые методы могут использовать поля производного класса, которые еще не будут проинициализированы. Потому из конструктора StreamStorage этот метод я вызывать не стал. Не нравится мне так же решение с отложенной инициализацией, где пришлось бы чуть ли не во всех методах вставлять проверку на наличие инициализации. Отказ от Template Method в пользу параметризации хранилища фабриками строк тоже не идеальное решение. Ведь одно из очевидных решений - реализация фабрик в классе произвольного хранилища. Но тогда будут сложности с передачей таких фабрик через конструктор класса StreamStorage.

 Хорошим решением этой проблемы стало бы решение сделать класс StreamStorage не расширяемым (sealed), опубликовать методы GetRow(int index), свойство Length и при необходимости расширения использовать композицию... Но, при реализации индексированного хранилища потребуется доступ к BinaryReader, BinaryWriter, Stream-у и даже к корню синхронизации. Не хотелось бы делать эти вещи общедоступными, потому было принято решение расширять хранилище через наследование (вариант понапихать всю необходимую функциональность в один класс кажется мне скверным).

Итого обязанность вызова метода Initialize назначается на классы, расширяющие StreamStorage. Резюме: в итоге этого поста завершена реализация хранилища записей с фиксированной длинной, с доступом к записям по индексу, с потокобезопасным доступом к полям записей. Для того, чтобы воспользоваться хранилищем, нужно определить два типа записей (один для заголовка) примерно как TestRow в предыдущем посте, определить свой класс хранилища, унаследовавшись от StreamStorage<THeader, TRow> и предоставить доступ к методам GetRow(int index) и способу управления размером хранилища.

При необходимости производное хранилище может реализовать интерфейс списка (IList), организовать кэширование записей и вести себя как полноценная коллекция. Напомню, что методы ReadValue и WriteValue у хранилища чисто вспомогательные, что они нужны для базового класса RowBase, и что обращение к полям по задумке должно происходить через свойства класса записи, например как в TestRow из предыдущего поста. Впрочем, методы ReadValue и WriteValue не мешают, а даже немного дополняют функциональность хранилища возможностью получать доступ к значениям не создавая экземпляры записей, потому я не стал предпринимать попыток скрыть эти методы.

В следующем посте расскажу о способах индексации этого хранилища.

четверг, 30 октября 2008 г.

Хранилище записей фиксированной длины

Хранилище записей фиксированной длины (часть II) Случилось вдруг создать такой велосипед, который хранил бы в файле записи фиксированной длины и позволял бы ими оперировать.  Почему бы не воспользоваться базой данных? На самом деле этот велосипед должен предоставлять локальный кэш одной из таблиц центральной БД в системе, в разработке которой я принимаю участие. Требования к нему специфические:
  • производительность, настроенная на чтение-запись отдельных полей записей;
  • доступ только по индексу записи, либо по её ключу (никаких запросов и выборок);
  • отказоустойчивость может быть принесена в жертву (это лишь кэш);
  • размеры файла могут достигать нескольких гигобайт (записи маленькие, но их мно-о-о-ого);
  • доступ к записям производится в случайном порядке (т.е. любое кэширование мало что даст);
Впрочем, это все оправдания. Мне же хотелось показать идею и её реализацию, а точнее прототип кода, адаптированный к блогу.
Организацию хранилища записей я позаимствовал у классов ADO. Таблица - набор записей, у таблицы есть набор колонок, доступ к значению поля записи определен на пересечении таблицы, колонки и записи (точнее ее индекса в таблице).
Отличия от класса DataTable в способе хранения данных. Данные хранятся в физическом потоке (Stream) и доступ к ним осуществляется через классы BinaryReader/BinaryWriter.
Начну, пожалуй, с реализации базового класса нетипизированной колонки. Будут и типизированные, но нетипизированные нужны для складывания их в коллекцию колонок:
public class Column
   {
       private readonly int _offset;
       private readonly int _size;
       private readonly ColumnCollection _columns;

       protected Column(ColumnCollection columns, int offset, int size)
       {
           if (columns == null)
           {
               throw new ArgumentNullException("columns");
           }
           _columns = columns;
           _offset = offset;
           _size = size;
       }

       public int Offset { get { return _offset; } }

       public int Size { get { return _size; } }

       public ColumnCollection Columns { get { return _columns; } }
   }
Здесь все просто. Каждая колонка знает размер значения в байтах, свою коллекцию колонок и смещение относительно начала записи. Все это запоминается в констуркторе колонки. Далее класс типизированной колонки. Типизированная колонка абстрактная, т.к. читать и писать данные придется с помощью BinaryReader/BinaryWriter-а, а они не имеют generic методов для чтения/записи значений.
public abstract class Column<T> : Column
    {
        protected Column(ColumnCollection columns, int offset, int size)
            : base(columns, offset, size)
        {
        }

        public abstract T ReadValue(BinaryReader reader);
        public abstract void WriteValue(BinaryWriter writer, T value);
    }
Типичный класс колонки:
class Int32Column : Column<int>
    {
        public Int32Column(ColumnCollection columns, int offset)
            : base(columns, offset, 4)
        {
        }

        public override int ReadValue(BinaryReader reader)
        {
            return reader.ReadInt32();
        }

        public override void WriteValue(BinaryWriter writer, int value)
        {
            writer.Write(value);
        }
    }
Таких классов несколько, не буду приводить код каждого из них, все они подобны. Немного отличается только класс строковой колонки, но о ней возможно позже. Обратите внимание, что класс типизированной колонки скрытый! Это объясняется тем, что я не собираюсь предоставлять возможность создания колонок сложных типов. Ограничусь лишь некоторыми примитивными. Класс коллекции колонок содержит в себе список колонок и число байт, требуемое для записи данных во всех колонках.
public class ColumnCollection
    {
        private readonly List<Column> _columns = new List<Column>();
        private int _size;

        public Column<int> AddInt32Column()
        {
            return AddInt32Column(this.Size);
        }

        public Column<int> AddInt32Column(int offset)
        {
            return AddColumn(new Int32Column(this, offset));
        }

        private Column<T> AddColumn<T>(Column<T> column)
        {
            _size = Math.Max(_size, column.Offset + column.Size);
            _columns.Add(column);
            return column;
        }

        public int Size { get { return _size; } }
    }
Коллекция колонок является так же производящим классом для типизированных колонок. Для каждого типа колонки (а их у меня чуть больше, чем только Int32Column) определено два метода создания экземпляра колонки: первый метод добавляет колонку в конец записи (указывает Offset, равный текущему размеру коллекции колонок в байтах), а второй - позволяет указать Offset вручную. Это потребуется для так называемых union полей.

Вот что из себя представляет базовый тип хранилища:
public abstract class StreamStorage
    {
        public abstract T ReadValue<T>(Column<T> column, int rowIndex);
        public abstract void WriteValue<T>(Column<T> column, int rowIndex, T value);
    }
Всего лишь два абстрактных метода, позволяющий писать и читать значения, соответствующие указанным колонкам и индексу записи. Этот базовый тип нужен для объявления базового типа записи. Хотел я параметризовать тип записи типом хранилища и тип хранилища типом записи, и возможно смог бы это сделать, но меня посетила идея, что у файла должен быть заголовок. И что заголовок - это второй тип записи. Т.е. хранилище надо параметризовывать двумя типами записи, но тогда каждую запись надо будет параметризовывать типом хранилища, в котором 2 типа записи... Но это все лишнее. Записи от хранилища не нужно ничего, кроме возможности обратиться к вышеуказанным методам. Потому базовый тип хранилища не имеет generic параметров. А базовый тип записи имеет generic параметр - конкретный тип записи:
public class RowBase<TRow>
        where TRow : RowBase<TRow>
    {
        private static readonly ColumnCollection s_columns = new ColumnCollection();
        public static ColumnCollection ColumnCollection { get { return s_columns; } }

        private readonly int _index;
        private readonly StreamStorage _storage;

        protected RowBase(StreamStorage storage, int index)
        {
            _storage = storage;
            _index = index;
        }

        public virtual void Initialize()
        {
        }

        public int GetIndex()
        {
            return _index;
        }

        public StreamStorage GetStorage()
        {
            return _storage;
        }

        protected T ReadValue<T>(Column<T> column)
        {
            return _storage.ReadValue(column, GetIndex());
        }

        protected void WriteValue<T>(Column<T> column, T value)
        {
            _storage.WriteValue(column, GetIndex(), value);
        }
    }
Базовый класс записи со спецификацией типа (т.е. все записи одного типа) привязаны к одному экземпляру коллекции колонок. Сделано это лишь для проверок. Для работоспособности хранилища интересен лишь размер записи, который определен в коллекции колонок и смещения самих колонок относительно записи. Но хранилище так же будет знать экземпляр коллекции колонок для проверки экземпляров колонок, которые приходят на публичные методы чтения и записи значений. Базовый класс записи содержит в себе ссылку на экземпляр хранилища, свой индекс, и определяет защищенные методы для чтения и записи значений.

Надеюсь, что код конкретной записи прояснит все что не ясно:
public class TestRow : RowBase<TestRow>
    {
        private static readonly Column<Guid> s_GuidColumn = ColumnCollection.AddGuidColumn();
        private static readonly Column<int> s_Int32Column = ColumnCollection.AddInt32Column();

        public TestRow(StreamStorage storage, int index)
            : base(storage, index)
        {
        }

        public Guid GuidValue
        {
            get { return ReadValue(s_GuidColumn); }
            set { WriteValue(s_GuidColumn , value); }
        }

        public int Int32Value
        {
            get { return ReadValue(s_Int32Column); }
            set { WriteValue(s_Int32Column, value); }
        }

        public override void Initialize()
        {
            base.Initialize();
            GuidValue = Guid.NewGuid();
            Int32Value = 0;
        }
    }
Итак, тип конкретной записи определяет колонки (статические поля), которые создает обращаясь к статической коллекции колонок, определенной у базового типа записи. Тип конкретной записи определяет свойства экземпляра записи. Реализация каждого свойства обращается к базовым методам чтения/записи значения и передает соответствующий экземпляр колонки. При обращении к свойству записи происходит передача колонки и номера записи хранилищу и вызывается метод чтения либо записи значения из хранилища.

О том, как устроено хранилище - в другой раз. Впрочем, наверняка идея уже ясна.

суббота, 30 августа 2008 г.

Расширения для System.Enum

Довольно странно, что языковые средства расширяются от версии к версии платформы, однако нововведения как-правило не затрагивают те части FCL, что знакомы нам с .NET 1.0. Речь пойдет о способах скрыть неуклюжие обращения к методам класса System.Enum, и добавить кое-какую функциональность. Определимся со списком целей:
  • метод object Enum.Parse(Type, string): приходится дважды указывать тип перечислителя (один раз аргументом метода, другой для приведения результата). Попытаемся подсахарить;
  • метод bool Enum.IsDefined(Type, object) так же требует указания типа перечислителя. В случае, когда тип перечислителя уже зашит в аргументе это лишнее. Например, когда требуется проверить принадлежность значения перечислителя к набору констант перечислителя без применения конструкции switch. Подсахарить;
  • проверка на наличие установленного флага выглядит слишком громоздко для использования в операторах ветвления:
    if(FileAccess.Read == (fileAccess & FileAccess.Read)) { ... }
    Еще хуже выглядит проверка на наличие сразу нескольких флагов. Определим метод, который с небольшим оверхедом по производительности скрасит конструкцию. (Наверняка, в Nemerle есть соответствующие макросы)
Для реализации задуманного потребуется два класса. Один - generic класс, в котором будут определены методы для работы с перечислителями а так же кое-какие статические поля, обеспечивающие работу этих методов:
public static class EnumExtensions<TEnum>
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
}
Обратите внимание на ограничения параметра типа. Я постарался выбрать ограничения, максимально близкие к типу enum, просто для того, чтобы компилятор и intellisense не позволяли использовать этот класс для других типов. На самом деле ни одно из ограничений не понадобится для реализации требуемой функциональности. Они фиктивны. К сожалению, не удалось исключить создание типов аля EnumExtensions<int>. При создании таких типов можно добиться двух эффектов: исключения TypeInitializationException, либо ограниченной работоспособности. В данном конкретном случае предпочитаю избежать TypeInitializationException.

Второй класс нужен только для объявления extension-методов, т.к. они не могут быть определены в generic-классах:
public static class EnumExtensions
{
}
Начнем с метода Parse. В generic-классе определим следующий метод:
public static TEnum Parse(string value)
{
   return (TEnum)Enum.Parse(typeof(TEnum), value);
}
В классе для extension методов определим метод-обертку для вышеописанного:
public static TEnum Parse<TEnum>(this string value)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.Parse(value);
}
Обращаться к методу-расширению можно в следующей форме:
var mode = modeString.Parse<FileMode>();
Для реализации метода IsDefined(TEnum value) потребуется хранение набора констант, полученных с помощью метода Enum.GetValues(Type). Дело в том, что подглядев реализацию метода Enum.IsDefined(Type, object), я понял что меня не устраивает такое количество выполняемого кода для проверки значения на допустимость. Даже цена получения массива значений в Enum.GetValues(Type) слишком высока для обращения к этому методу более одного раза! Добавим в generic-класс следующий код:
private static readonly TEnum[] s_values = GetValues();

private static TEnum[] GetValues()
{
   return (typeof(TEnum).IsEnum)
       ? (TEnum[])Enum.GetValues(typeof(TEnum))
       : new TEnum[]{};
}

public static int IndexOf(TEnum value)
{
   return Array.IndexOf(s_values, value);
}

public static bool IsDefined(TEnum value)
{
   return IndexOf(value) > -1;
}
В порядке объявления: s_values - статическое поле для хранения массива величин типа TEnum. Инициализируется в объявлении. Статический метод GetValues проверяет, является ли тип TEnum перечислителем, и возвращает массив значений перечислителя, либо пустой массив, избегая исключения TypeInitializationException (оно непременно возникнет при возбуждении исключения ArgumentException при обращении к методу Enum.GetValues(Type) во время инициализации типа ExtensionMethods<TEnum>). Методы IndexOf и IsDefined тривиальны.

Отмечу только, что я не гарантирую их работоспособность при использовании типов, отличных от enum, которые смогли пролезть через набор ограничений Type-параметра (примитивные типы int, long,... и некоторые пользовательские типы). Уверен, что при желании читатель сможет самостоятельно реализовать достойное поведение этих методов для типов, отличных от enum. Думаю, что самым достойным здесь будет возбуждение исключения NotSupportedException.

Да, метод GetIndex(TEnum) получился в качестве бонуса, и я не вижу необходимости скрывать его. Может оказаться полезным. Добавим соответствующие extension-методы в класс EnumExtensions (не generic-класс):
public static int GetIndex<TEnum>(this TEnum value)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.IndexOf(value);
}

public static bool IsDefined<TEnum>(this TEnum value)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.IsDefined(value);
}
Вот код, проверяющий работу метода IsDefined и демонстрирующий обращение к нему через extension-метод:
Assert.IsTrue(FileMode.Open.IsDefined());

Assert.IsFalse(((FileMode)1000).IsDefined());
Получился весьма элегантный способ проверки значений на принадлежность к набору констант. Приступим к реализации метода bool HasFlags(TEnum value, TEnum flags). Не сложно реализовать такой метод с помощью обращения к методу ulong IConvertible.ToUInt64(IFormatProvider), однако производительность такого решения будет не на высоте (как минимум 4 операции boxing-а, 2 обращения к extern методам, 2 unboxing-а). Так же этот метод будет оперировать 64-х разрядными величинами, даже в тех случаях, когда перечислитель основан на более коротких типах.

Недавно пришло в голову, что динамически сгенерированный метод для соответствующего enum-типа может быть вполне приемлемым по производительности решением. Следующий метод определяет динамический метод DynamicMethod и делегирует генерацию кода переданному в качестве аргумента методу.
private static DynamicMethod BuildHasFlagsMethod(Type enumType, Action<ILGenerator> ilGenAction)
{
   var method = new DynamicMethod(
       "HasFlagMethod",
       typeof(bool),
       new Type[] { enumType, enumType },
       typeof(EnumExtensions).Module);

   var il = method.GetILGenerator();
   ilGenAction(il);
   return method;
}
Я не зря параметризовал этот метод параметром Type, в то время как в generic-классе известен тип TEnum. Для оптимизации работы JIT-компилятора и объема генерируемого им машинного кода следует выносить методы, не использующие явно типы generic аргументов, в не generic-классы. В рамках этого поста я буду располагать такие методы в generic-классе, но буду подразумевать, что читатель вынесет их во вспомогательный класс (если, конечно, статья окажется полезной для него, и он решит воспроизвести код).

Следующие два метода генерируют код реализации метода HasFlags. Первый генерирует хорошую реализацию, а второй - реализацию, которая выбрасывает исключение NotSupportedException. Вторая реализация пригодится для перечислителей без атрибута [Flags], либо для типов, не являющихся enum-ами.
static void EmitHasFlags(ILGenerator il)
{
   il.Emit(OpCodes.Ldarg_1);
   il.Emit(OpCodes.Ldarg_0);
   il.Emit(OpCodes.Ldarg_1);
   il.Emit(OpCodes.And);
   il.Emit(OpCodes.Ceq);
   il.Emit(OpCodes.Ret);
}

static void EmitThrowException(ILGenerator il)
{
   var ctor = typeof(NotSupportedException).GetConstructor(new Type[] { });
   il.Emit(OpCodes.Newobj, ctor);
   il.Emit(OpCodes.Throw);
}
Метод EmitHasFlags записывает два аргумента в стек для выполнения операций логического умножения и сравнения результата со втрорым аргументом, выполняет операции умножения и сравнения, затем возвращает результат. Операция логического умножения может быть выполнена только над примитивными типами, потому необходимо гарантировать обращение к этому методу генерации только при корректном generic-аргументе.
private static readonly Func<TEnum, TEnum, bool> s_hasFlagsMethod;

public static bool IsFlags { get; private set; }

static EnumExtensions()
{
   IsFlags = HasFlagsAttribute(typeof(TEnum));

   Action<ILGenerator> ilGenAction;
   if(IsFlags)
       ilGenAction = EmitHasFlags;
   else
       ilGenAction = EmitThrowException;

   var method = BuildHasFlagsMethod(typeof(TEnum), ilGenAction);

   s_hasFlagsMethod = (Func<TEnum, TEnum, bool>)method.CreateDelegate(
       typeof(Func<TEnum, TEnum, bool>));
}

internal static bool HasFlagsAttribute(Type enumType)
{
   return enumType.GetCustomAttributes(typeof(FlagsAttribute), false).Length > 0;
}

public static bool HasFlags(TEnum value, TEnum flags)
{
   return s_hasFlagsMethod(value, flags);
}
В порядке объявления: s_hasFlagsMethod - делегат для сгенерированного метода; IsFlags - свойство, указывающее на наличие атрибута [Flags] у типа TEnum. Это еще один полезный бонус, который можно оставить опубликованным; далее - статический конструктор.

Остановимся на нем подробнее: Первым делом он инициирует свойство IsFlags значением, возвращаенным методом HasFlagsAttribute(Type). Затем выбирается метод для генерации кода. При значении свойства IsFlags, равном true, можно гарантировать, что TEnum - enum тип, т.к. компилятор не даст применить атрибут [Flags] к любому другому типу, кроме enum. Однако, варьируя условие выбора метода генерации IL кода, можно добиться генерации рабочего метода для целых типов TEnum, при необходимости. Я, правда, такой необходимости не вижу. Для целых методов нет нужды обращаться к динамически сгенерированному коду, потому как можно определить методы обычным образом.

Наконец, реализация метода HasFlags(TEnum, TEnum), которая делегирует динамически сгенерированному методу. Объявление соответствующего extension-метода:
public static bool HasFlags<TEnum>(this TEnum value, TEnum flags)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.HasFlags(value, flags);
}
Использование этого метода может быть например таким:
if(fileAccess.HasFlags(FileAccess.Read)) { ... }
Предлагаю сравнить этот кусок кода с аналогичным выше. Думаю, что этот информативнее. Однако, не следует использовать этот метод в критичном по производительности коде.

P.S. Код для проверки флагов в типе int может выглядеть так:
public static bool HasFlags(this int value, int flags)
{
   return flags == (value & flags);
}

...
if(myIntValue.HasFlags(0x80)) { ... }
P.P.S Пробовал сгенерировать код с помощью Expression. Вот что вышло:
var valueParam = Expression.Parameter(typeof(TEnum), "value");
var flagsParam = Expression.Parameter(typeof(TEnum), "flags");
Expression body = Expression.Equal(
    flagsParam,
    Expression.And(valueParam, flagsParam));
В последней строке получил исключение: System.InvalidOperationException: The binary operator And is not defined for the types 'System.IO.FileAccess' and 'System.IO.FileAccess'.. Получается, что il.Emit(OpCodes.And); можно выполнить над Enum-ом, а Expression.And - нет. Был искренне удивлен.

вторник, 12 августа 2008 г.

Трюк с generic-ами.

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

Приведу случай из реальной жизни. В системе, в разработке которой я принимаю участие, требуется довольно много разных данных сохранять в xml. Поначалу мы много использовали xml сериализацию. Требовалось уметь сериализовывать и десериализовывать 5 или 6 типов графов. Единственное, что было общее у этих графов - необходимость сериализации в файл, в строку. Вполне естевственно, что после появления второй иерархии объектов для сериализации, возникло желание использовать общий код для сериализации и десериализации графов. Приходила в голову идея использовать внешнюю утилиту, однако использование внешней утилиты показалось не очень красивым (требовалась передача типа корня сериализации во внешний метод):
Foo foo = XmlUtils.DeserializeFromFile(typeof(Foo), "Foo.xml");
или
Foo foo = XmlUtils.DeserializeFromFile<Foo>("Foo.xml");
а душе хотелось полета:
Foo foo = Foo.DeserializeFromFile("Foo.xml");
Таким образом, требуется определить статический метод, который бы для типа Foo возвращал результат типа Foo, а для типа Bar возвращал бы результат типа Bar. Есть средство. Определим хитрый базовый класс:
public class XmlSerializationRoot<TRoot>
   where TRoot : XmlSerializationRoot<TRoot>
{
   public static TRoot DeserializeFrom(TextReader reader)
   {
       if (reader == null)
           throw new ArgumentNullException("reader");

       return (TRoot)CreateSerializer().Deserialize(reader);
   }

   public static TRoot DeserializeFrom(Stream stream)
   {
       if (stream == null)
           throw new ArgumentNullException("stream");

       using (StreamReader reader = new StreamReader(stream))
           return DeserializeFrom(reader);
   }

   public static TRoot DeserializeFromString(string xml)
   {
       using (TextReader reader = new StringReader(xml))
           return DeserializeFrom(reader);
   }

   public static TRoot DeserializeFromFile(string fileName)
   {
       using (TextReader reader = File.OpenText(fileName))
           return DeserializeFrom(reader);
   }

   private static XmlSerializer CreateSerializer()
   {
       return new XmlSerializer(typeof(TRoot));
   }

   public void SerializeTo(TextWriter writer)
   {
       if (writer == null)
           throw new ArgumentNullException("writer");

       CreateSerializer().Serialize(writer, this);
   }

   public string SerializeToString()
   {
       StringBuilder builder = new StringBuilder();
       using (StringWriter writer = new StringWriter(builder))
           this.SerializeTo(writer);

       return builder.ToString();
   }

   public void SerializeToFile(string fileName)
   {
       using (StreamWriter writer = File.CreateText(fileName))
           this.SerializeTo(writer);
   }

   public void SerializeTo(Stream stream)
   {
       using (StreamWriter writer = new StreamWriter(stream))
           this.SerializeTo(writer);
   }
}
Особый интерес представляют статические методы десериализации. Методы сериализации были внесены до кучи, чтобы пример был полным. Вообще говоря, класс XmlSerializationRoot не будет являться базовым классом для классов с возможностью сериализации. Базовым классом для них будет XmlSerializationRoot<T>. Т.е. при следующем объявлении класса Foo
class Foo : XmlSerializationRoot<Foo>
{
}
мы получим ситуацию, где класс Foo наследует определенные у класса XmlSerializationRoot<Foo> методы. Теперь можно пользоваться этими методами через идентификатор типа Foo:
Foo foo = Foo.DeserializeFromFile("foo.xml");
В качестве завершающего штриха предлагаю выделить интерфейс
public interface IXmlSerializable
{
   void SerializeTo(TextWriter writer);
   void SerializeToFile(string fileName);
   void SerializeTo(Stream stream);
   string SerializeToString();
}
и поддержать его классом XmlSerializationRoot. Теперь мы сможем вызывать методы сериализации не зная типа сохраняемого объекта. Теперь буду писать гадости про этот подход.
  1. Данный подход навязывает ограничение наследования на разрабатываемые классы. При необходимости наследования классов от другого класса, использование усложняется, однако, можно объявить собственные методы и делегировать их вспомогательному классу. Например:
    class Foo : SomeBaseClass // наследуемся от чего-то другого
    {
       public static Foo DeserializeFromFile(string fileName)
       {
           return XmlSerializationRoot<Foo>.DeserializeFromFile(fileName);
       }
    }
    В данном случае потребуется убрать constraint у класса XmlSerializationRoot. В принципе, он объявлен формально для контроля за способом использования функциональности, и не требуется для компиляции методов класса.
  2. Resharper ругается на использование методов базового класса через идентификатор производного типа. Можно подкрутить его настройки, вставить управляющий комментарий, либо просто игнорировать данные сообщения.
  3. Пользуясь этим подходом мы не можем прочитать что-то из файла, а потом разобраться, что это было. Но в этом виноват не только сей подход, а так же устройство XML сериализации в FCL.
  4. Если требуется объявить только статические методы, то мы не сможем объявить базовый класс с модификатором static. Если объявим, то не сможем унаследовать от него.
Хоть область применения данного подхода не широка, но иногда это то что надо. Например, при необходимости подсчета экземпляров классов разного типа.

P.S. Хочу обратить внимание, что в данном посте не шла речь о корректности данного подхода к сериализации в архитектурном плане. Это лишь пример издевательства над языком. Однако, данный код отлично работал и был удобно используемым, пока мы не перешли на более тяжелый (но более гибкий) способ сериализации через XmlDocument.