IT Notes

Паттерн Компоновщик на C++

В программировании нередко возникает необходимость формирования сложных структур данных, вложенных друг в друга. Например, при построении деревьев синтаксического разбора. С решением этой задачи помогает справиться паттерн Компоновщик (Composite).

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

  1. Добавить вложенный элемент;
  2. Извлечь результат.

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

Косвенно мы уже сталкивались с Компоновщиком, когда рассматривали паттерн Строитель. В тот раз мы занимались генерацией XML-кода. Сам Компоновщик был скрыт за интерфейсом стандартной библиотеки QtXml.

Пример использования паттерна Компоновщик

Создадим приложение, способное генерировать простой код на C++ следующего вида:

class MyClass {
public:
    void testFunc1() {
    }
    virtual void testFunc3() const {
    }

protected:
    static void testFunc4() {
        printf( "Hello, world!\n" );
    }

private:
    static void testFunc2() {
    }

};

Следует понимать, что полноценный компилятор - это очень сложная программа. Чтобы не увязнуть в деталях, и сконцентрироваться на самом Компоновщике, мы существенно упростим задачу. Обойдемся без проверки корректности синтаксиса. А также оставим всего три элемента языка: класс, функция-член и операция вывода на консоль.

Нарисуем дерево синтаксического разбора, соответствующее фрагменту кода выше:

composite-pattern-example-diagram-thumbnail

Реклама

Базовый класс элемента синтаксиса

Определим абстрактный класс Unit, представляющий некую языковую конструкцию:

class Unit {
public:
    using Flags = unsigned int;

public:
    virtual ~Unit() = default;

    virtual void add( const std::shared_ptr< Unit >& /* unit */, Flags /* flags */ ) {
        throw std::runtime_error( "Not supported" );
    }

    virtual std::string compile( unsigned int level = 0 ) const = 0;

protected:
    virtual std::string generateShift( unsigned int level ) const {
        static const auto DEFAULT_SHIFT = "    ";
        std::string result;
        for( unsigned int i = 0; i < level; ++i ) {
            result += DEFAULT_SHIFT;
        }
        return result;
    }
};

Виртуальная функция-член add() предназначена для добавления вложенных элементов (передача происходит через умный указатель std::shared_ptr). Также эта функция принимает параметр Flags. Совсем скоро мы посмотрим на его применение. По умолчанию add() выбрасывает исключение.

Функция compile() генерирует код на C++, соответствующий содержимому элемента. Результат возвращается в виде строки std::string. В качестве аргумента функция принимает параметр level, указывающий на уровень вложенности узла дерева. Это требуется для корректной расстановки отступов в начале строк генерируемого кода.

Вспомогательная функция-член generateShift() всего лишь возвращает строку, состоящую из нужного числа пробелов. Результат зависит от уровня вложенности.

Реклама

Реализация элемента Класс

Вот одна из возможных реализаций класса, представляющего Класс:

class ClassUnit : public Unit {
public:
    enum AccessModifier {
        PUBLIC,
        PROTECTED,
        PRIVATE
    };

    static const std::vector< std::string > ACCESS_MODIFIERS;

public:
    explicit ClassUnit( const std::string& name ) : m_name( name ) {
        m_fields.resize( ACCESS_MODIFIERS.size() );
    }

    void add( const std::shared_ptr< Unit >& unit, Flags flags ) {
        int accessModifier = PRIVATE;
        if( flags < ACCESS_MODIFIERS.size() ) {
            accessModifier = flags;
        }

        m_fields[ accessModifier ].push_back( unit );
    }

    std::string compile( unsigned int level = 0 ) const {
        std::string result = generateShift( level ) + "class " + m_name + " {\n";
        for( size_t i = 0; i < ACCESS_MODIFIERS.size(); ++i ) {
            if( m_fields[ i ].empty() ) {
                continue;
            }

            result += ACCESS_MODIFIERS[ i ] + ":\n";
            for( const auto& f : m_fields[ i ] ) {
                result += f->compile( level + 1 );
            }

            result += "\n";
        }
        result += generateShift( level ) + "};\n";

        return result;
    }

private:
    std::string m_name;

    using Fields = std::vector< std::shared_ptr< Unit > >;
    std::vector< Fields > m_fields;

};
const std::vector< std::string > ClassUnit::ACCESS_MODIFIERS = { "public", "protected", "private" };

Имя Класса указывается при его создании через аргумент конструктора. При этом Класс хранит все свои поля в векторе std::vector. Обратите внимание, что используется не просто вектор, а вектор из трех векторов. По одному на каждый модификатор области видимости: public, protected и private.

Элемент Класса сам распределяет свои поля по областям видимости. Поэтому в качестве флага функция add() ожидает получить одно из значений нашего перечисления ClassUnit::AccessModifier. А затем помещает добавляемый элемент в нужный вектор.

Процесс "компиляции" Класса достаточно линеен, поэтому не требует особых объяснений. Единственное, обратите внимание на этот фрагмент:

for( const auto& f : m_fields[ i ] ) {
    result += f->compile( level + 1 );
}

В процессе компоновки происходит последовательный обход всех полей. Для них также вызывается функция compile() с уровнем level на единицу больше. А сформированный фрагмент кода присоединяется в конец результатирующей строки result.

Реализация элемента Метод

Представление Функции-члена реализуем в виде следующего класса:

class MethodUnit : public Unit {
public:
    enum Modifier {
        STATIC      = 1,
        CONST       = 1 << 1,
        VIRTUAL     = 1 << 2
    };

public:
    MethodUnit( const std::string& name, const std::string& returnType, Flags flags ) :
        m_name( name ), m_returnType( returnType ), m_flags( flags ) { }

    void add( const std::shared_ptr< Unit >& unit, Flags /* flags */ = 0 ) {
        m_body.push_back( unit );
    }

    std::string compile( unsigned int level = 0 ) const {
        std::string result = generateShift( level );
        if( m_flags & STATIC ) {
            result += "static ";
        } else if( m_flags & VIRTUAL ) {
            result += "virtual ";
        }

        result += m_returnType + " ";
        result += m_name + "()";

        if( m_flags & CONST ) {
            result += " const";
        }

        result += " {\n";

        for( const auto& b : m_body ) {
            result += b->compile( level + 1 );
        }

        result += generateShift( level ) + "}\n";

        return result;
    }

private:
    std::string m_name;
    std::string m_returnType;
    Flags m_flags;

    std::vector< std::shared_ptr< Unit > > m_body;
};

Конструктор класса MethodUnit принимает имя функции, тип возвращаемого значения и флаги. Использование std::string в качестве типа - не самое удачное решение (сойдет только для примера). В полноценной системе Тип тоже должен быть представлен отдельным классом, наследующим Unit.

Для Функции-члена мы предусмотрели три возможных модификатора: STATIC, CONST и VIRTUAL. Они определены в перечислении Modifier в виде битовых флагов. Их комбинацию мы и ожидаем получать в качестве третьего аргумента конструктора flags.

При добавлении элементов с помощью add() не требуется указывать дополнительные флаги. Мы просто помещаем все в конец вектора m_body, заполняя тело Функции.

Генерация кода в compile() напоминает то, что мы уже видели для элемента Класса. Конечно, со своим специфическим синтаксисом. Например, обратите внимание на то, как используются битовые флаги модификатора m_flags.

Реализация элемента "Оператор печати"

А здесь все совсем просто:

class PrintOperatorUnit : public Unit {
public:
    explicit PrintOperatorUnit( const std::string& text ) : m_text( text ) { }

    std::string compile( unsigned int level = 0 ) const {
        return generateShift( level ) + "printf( \"" + m_text + "\" );\n";
    }

private:
    std::string m_text;
};

Думаю, комментарии излишни. Идем дальше.

Компоновщик в действии

А теперь скомпонуем программу, которую собирались изначально:

std::string generateProgram() {
    ClassUnit myClass( "MyClass" );
    myClass.add(
        std::make_shared< MethodUnit >( "testFunc1", "void", 0 ),
        ClassUnit::PUBLIC
    );
    myClass.add(
        std::make_shared< MethodUnit >( "testFunc2", "void", MethodUnit::STATIC ),
        ClassUnit::PRIVATE
    );
    myClass.add(
        std::make_shared< MethodUnit >( "testFunc3", "void", MethodUnit::VIRTUAL | MethodUnit::CONST ),
        ClassUnit::PUBLIC
    );

    auto method = std::make_shared< MethodUnit >( "testFunc4", "void", MethodUnit::STATIC );
    method->add( std::make_shared< PrintOperatorUnit >( R"(Hello, world!\n)" ) );
    myClass.add( method, ClassUnit::PROTECTED );

    return myClass.compile();
}

Осталось только вызвать эту функцию:

int main() {
    std::cout << generateProgram() << std::endl;
    return 0;
}

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

Сейчас мы компонуем синтаксическое дерево вручную. В реальном приложении мы бы могли придумать свой высокоуровневый (по сравнению с C++) синтаксис для решения каких-то специфических задач. А затем использовать рассмотренный подход для трансляции нашего упрощенного кода в код C++. Мы затрагивали подобные идеи, когда обсуждали принцип DRY.

С учетом наших допущений получилось не так уж и плохо. Но остается серьезный недостаток. Сейчас функция generateProgram() жестко привязана к формированию кода на C++. Однако при определенных ограничениях мы могли бы обеспечить генерацию кода и на других языках программирования. Этим мы займемся в следующий раз. А поможет нам в этом паттерн Абстрактная фабрика...

Понравилась статья?
Не забудь поделиться ей с друзьями!
Реклама

Похожие публикации

Комментарии

норм

Интересно!

Браво, браво! Все очень здорово, понравилось! ;) Для компоновщика можно, наверное, использовать массив vector<unique_ptr<Unit>> вместо vector<shared_ptr<Unit>> . Ну и перемещать указатели в контейнер...

Еще раз - браво, браво! ;)

Lapsha:

Браво, браво! Все очень здорово, понравилось! ;) Для компоновщика можно, наверное, использовать массив vector<unique_ptr<Unit>> вместо vector<shared_ptr<Unit>> . Ну и перемещать указатели в контейнер...

Еще раз - браво, браво! ;)

Здравствуйте. Спасибо за комментарий!

Относительно использования unique_ptr - зависит от модели использования. Потенциально объекты Unit могут быть разделяемыми (при компоновке нескольких независимых иерархий), поэтому строгий контроль может стать ограничением.

RSS RSS-рассылка

Популярное