В программировании нередко возникает необходимость формирования сложных структур данных, вложенных друг в друга. Например, при построении деревьев синтаксического разбора. С решением этой задачи помогает справиться паттерн Компоновщик (Composite).
Ключевая идея паттерна Компоновщик заключается в его рекурсивной природе. В основе иерархии классов, реализующих этот паттерн, лежит абстрактный класс. Для него достаточно определить две операции:
- Добавить вложенный элемент;
- Извлечь результат.
Сначала дерево компонуется из составных частей с помощью операции добавления. А затем для элемента, находящегося на вершине полученного дерева, извлекается результат. Причем, вершина дерева зависит от вложенных в него узлов. А эти узлы зависят от вложенных в них узлов. И так до самого низа, т.е. до листьев дерева.
Косвенно мы уже сталкивались с Компоновщиком, когда рассматривали паттерн Строитель. В тот раз мы занимались генерацией XML-кода. Сам Компоновщик был скрыт за интерфейсом стандартной библиотеки QtXml.
Пример использования паттерна Компоновщик
Создадим приложение, способное генерировать простой код на C++ следующего вида:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class MyClass { public: void testFunc1() { } virtual void testFunc3() const { } protected: static void testFunc4() { printf( "Hello, world!\n" ); } private: static void testFunc2() { } }; |
Следует понимать, что полноценный компилятор — это очень сложная программа. Чтобы не увязнуть в деталях, и сконцентрироваться на самом Компоновщике, мы существенно упростим задачу. Обойдемся без проверки корректности синтаксиса. А также оставим всего три элемента языка: класс, функция-член и операция вывода на консоль.
Нарисуем дерево синтаксического разбора, соответствующее фрагменту кода выше:
Базовый класс элемента синтаксиса
Определим абстрактный класс Unit, представляющий некую языковую конструкцию:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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() всего лишь возвращает строку, состоящую из нужного числа пробелов. Результат зависит от уровня вложенности.
Реализация элемента Класс
Вот одна из возможных реализаций класса, представляющего Класс:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
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. А затем помещает добавляемый элемент в нужный вектор.
Процесс «компиляции» Класса достаточно линеен, поэтому не требует особых объяснений. Единственное, обратите внимание на этот фрагмент:
|
1 2 3 |
for( const auto& f : m_fields[ i ] ) { result += f->compile( level + 1 ); } |
В процессе компоновки происходит последовательный обход всех полей. Для них также вызывается функция compile() с уровнем level на единицу больше. А сформированный фрагмент кода присоединяется в конец результатирующей строки result.
Реализация элемента Метод
Представление Функции-члена реализуем в виде следующего класса:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
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.
Реализация элемента «Оператор печати»
А здесь все совсем просто:
|
1 2 3 4 5 6 7 8 9 10 11 |
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; }; |
Думаю, комментарии излишни. Идем дальше.
Компоновщик в действии
А теперь скомпонуем программу, которую собирались изначально:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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(); } |
Осталось только вызвать эту функцию:
|
1 2 3 4 |
int main() { std::cout << generateProgram() << std::endl; return 0; } |
После запуска приложения на консоль будет выведено ровно то, что мы и хотели.
Сейчас мы компонуем синтаксическое дерево вручную. В реальном приложении мы бы могли придумать свой высокоуровневый (по сравнению с C++) синтаксис для решения каких-то специфических задач. А затем использовать рассмотренный подход для трансляции нашего упрощенного кода в код C++. Мы затрагивали подобные идеи, когда обсуждали принцип DRY.
С учетом наших допущений получилось не так уж и плохо. Но остается серьезный недостаток. Сейчас функция generateProgram() жестко привязана к формированию кода на C++. Однако при определенных ограничениях мы могли бы обеспечить генерацию кода и на других языках программирования. Этим мы займемся в следующий раз. А поможет нам в этом паттерн Абстрактная фабрика.
