В программировании нередко возникает необходимость формирования сложных структур данных, вложенных друг в друга. Например, при построении деревьев синтаксического разбора. С решением этой задачи помогает справиться паттерн Компоновщик (Composite).
Ключевая идея паттерна Компоновщик заключается в его рекурсивной природе. В основе иерархии классов, реализующих этот паттерн, лежит абстрактный класс. Для него достаточно определить две операции:
Сначала дерево компонуется из составных частей с помощью операции добавления. А затем для элемента, находящегося на вершине полученного дерева, извлекается результат. Причем, вершина дерева зависит от вложенных в него узлов. А эти узлы зависят от вложенных в них узлов. И так до самого низа, т.е. до листьев дерева.
Косвенно мы уже сталкивались с Компоновщиком, когда рассматривали паттерн Строитель. В тот раз мы занимались генерацией XML-кода. Сам Компоновщик был скрыт за интерфейсом стандартной библиотеки QtXml.
Создадим приложение, способное генерировать простой код на C++ следующего вида:
class MyClass {
public:
void testFunc1() {
}
virtual void testFunc3() const {
}
protected:
static void testFunc4() {
printf( "Hello, world!\n" );
}
private:
static void testFunc2() {
}
};
Следует понимать, что полноценный компилятор - это очень сложная программа. Чтобы не увязнуть в деталях, и сконцентрироваться на самом Компоновщике, мы существенно упростим задачу. Обойдемся без проверки корректности синтаксиса. А также оставим всего три элемента языка: класс, функция-член и операция вывода на консоль.
Нарисуем дерево синтаксического разбора, соответствующее фрагменту кода выше:
Определим абстрактный класс 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 могут быть разделяемыми (при компоновке нескольких независимых иерархий), поэтому строгий контроль может стать ограничением.
Anonymous
норм