Давно я тут ничего не писал, хотя было много поводов. Теперь я работаю в Ubisoft, живу в Киеве. Перед уходом из Gameloft мы закончили Tom Clancy's Rainbow Six®: Shadow Vanguard, собственно работа над проектом и привела к задержке моего перехода, который я планировал совершить на полгода раньше. В Ubisoft я уже успел поработать над Assassin’s Creed: Revelations, побывать в Румынии, получить несколько футболок с логотипом игры и несколько дисков, один из которых подарочный. Но сегодняшний пост не об этом.
Когда мы заканчивали AC:R у нас было много времени и мало багов, в такой ситуации каждый уважающий себя программист начинает работать над расширением своего мировоззрения. Меня почему-то заинтересовало написание своего скриптового языка. Я выбрал синтаксис похожий на JavaScript, в качестве лексера re2c, парсер lemon и начал при помощи этих инструментов собирать синтаксическое дерево.
Я не большой любитель полиморфизма, особенно там где он не нужен, поэтому в качестве ноды дерева выбрал такую структуру:
- class Node
- {
- public:
- enum
- {
- kChildrenCount = 4
- };
- private:
- Node* m_child[kChildrenCount];
- Node* m_next;
- int m_type;
- std::string m_name;
- public:
- Node(int type, const std::string& name);
- ~Node();
- static Node* Create( int type, Node* child0 = 0, Node* child1 = 0, Node* child2 = 0, Node* child3 = 0 );
- static Node* Create( int type, const std::string& name, Node* child0 = 0, Node* child1 = 0, Node* child2 = 0, Node* child3 = 0 );
- static void Destroy( Node*& node );
- static void DestroyList( Node*& node );
- static Node* Join( Node* n1, Node* n2 );
-
- Node* GetChild(int i) const { return m_child[i]; }
- int GetType() const { return m_type; }
- Node* GetNext() const { return m_next; }
- const std::string& GetName() const { return m_name; }
- };
Структурка довольно простая, типичное ее использование раньше было таким:
- ifStatement(RET) ::= If LParan expression(EXPR) RParan statement(THEN). { RET = Node::Create( NodeType::kIf, EXPR, THEN ); }
Это пример создания блока if-then в парсере. Как видно у меня есть enum с константами соответствующими типу ноды, в 0 ребенка я записываю дерево с выражением, в 1 дерево с командами. все бы ничего но при обработке мне все это нужно помнить. то есть достать из ноды 0 потомка и скомпилировать его как выражение, потом достать из ноды 1 потомка и скомпилировать его как команду (либо блок команд), проверить есть ли блок else и скомпилировать его. Когда подобные действия делаются 1 раз, на наглядность никто не обратит внимания, но когда функций Compile* становится много, эти магические цифры начинают мешать.
Для этого я добавил структуры которые хранят именованные константы для каждого блока. Для блока If оно выглядит так:
- struct If
- {
- enum
- {
- Condition,
- ThenStatement,
- ElseStatement,
- };
- };
-
Потом я подумал, а почему бы не добавить в каждую из таких структур функцию по созданию ноды. В коде парсера, вместо безликих Node::Create появились вполне симпатичные If::Create которое списком параметрров подсказывает что и где оно ждет, а при компиляции я получаю детей ноды по вполне симпатичным идентификаторам типа node->GetChild(If::Condition), хотя ошибки все еще возможны, код в целом стал более наглядным.
Но на этом я не успокоился. тут я вспомнил про список типов из книги Александреску. Книги под рукой не было, поэтому решил написать его сам, меня очень удивило то, что написание списка типов это не такая уж и сложная задача. Все что мне нужно было, это получение по типу номера в списке, для того чтоб избавиться от enum’a с константами типов ноды.
Собственно сам список:
- template<typename Left, typename Right>
- struct TypeList
- {
- typedef Left Value;
- typedef Right Next;
- };
Я не стал делать красивые дефайны для заполнения списка, поэтому заполнил его обычным typedef
- struct Empty
- {
- };
- typedef TypeList<None,
- ...
- TypeList<If,
- TypeList<For,
- ...
- Empty > ... > > .. > NodeTypes;
Вот шаблоны для поиска и сравнения:
- template<typename Left, typename Right>
- struct Compare
- {
- private:
- typedef int one;
- typedef char two;
- static_assert( sizeof(one) != sizeof(two), "one and two must be types with different size" );
- static one compare( Left left, Left right );
- static two compare( Left left, ... );
- public:
- enum
- {
- Value = sizeof(one) == sizeof(compare( (Left()), (Right()) )) ? 1 : 0,
- };
- };
- template<typename TList, typename Val, int depth = 0>
- struct Find
- {
- enum
- {
- Value = Compare<typename TList::Value, Val>::Value ? depth : Find<typename TList::Next, Val, depth + 1>::Value,
- };
- };
- template<typename Val, int depth>
- struct Find<Empty, Val, depth>
- {
- enum
- {
- Value = -1
- };
- };
Они компилируются в VC++2010EE, и я думаю они скомпилируются в gcc (разве что static_assert нужно будет убрать). О работе шаблона Compare можно почитать в книге Александреску, а Find рекурсивно проходит по списку и если находит нужный элемент возвращает его номер, иначе –1.
Для упрощения поиска типа в списке я написал такой макрос и пример его использования:
- #define ID(type) (Find<NodeTypes, type>::Value)
- if ( node->GetType() == ID(If) ) ...
Когда С++11 будет лучше поддерживаться студийным компилятором, я заменю этот макрос на constexpr.
В результате всего этого функция создания ноды стала выглядеть так:
- Node* If::Create( Node* condition, Node* thenStatements, Node* elseStatements )
- {
- static_assert( ID(If) != -1, "Type should be registered in NodeTypes list" );
- return Node::Create( ID(If) , condition, thenStatements, elseStatements );
- }
Если добавить в каждую структуру тайпдеф который будет указывать сам на свой тип то код функции станет более пригодным для “копипаст” программирования:
- struct If
- {
- typedef If self;
- enum
- {
- Condition,
- ThenStatement,
- ElseStatement,
- };
- static Node* Create( Node* condition, Node* thenStatements, Node* elseStatements = 0 );
- };
- Node* If::Create( Node* condition, Node* thenStatements, Node* elseStatements )
- {
- static_assert( ID(self) != -1, "Type should be registered in NodeTypes list" );
- return Node::Create( ID(self) , condition, thenStatements, elseStatements );
- }
Но и на этом я не успокоился. В самом начале, когда я привел структуру ноды, в ней был указан размер массива детей ноды:
kChildrenCount = 4
оно было получено эмпирическим путем, нодой в которой будет заполнено максимальное количество детей должен быть for, но при помощи списка типов можно эту константу посчитать. Для этого в структуру каждого типа была добавлена константа Total, которая говорит о том сколько детей нужно конкретному типу ноды. Шаблон который находит максимальное количество детей выглядит так:
- template<typename TList>
- struct TMax
- {
- private:
- enum
- {
- Current = TList::Value::Total,
- Max = TMax<typename TList::Next>::Value
- };
- public:
- enum
- {
- Value = (Current > Max) ? Current : Max
- };
- };
- template<>
- struct TMax<Empty>
- {
- enum
- {
- Value = 0
- };
- };
- // использование
- enum
- {
- kChildrenCount = TMax<NodeTypes>::Value
- };
В данный момент не знаю как написать более универсальный вариант этого шаблона, сейчас он ищет максимум только по полю Total и для того чтоб задать другое поле нужно менять шаблон.
Вот еще шаблон который возвращает длину списка типов:
- template<typename TList>
- struct Len
- {
- enum
- {
- Value = Len<typename TList::Next>::Value + 1
- };
- };
- template<>
- struct Len<Empty>
- {
- enum
- {
- Value = 0
- };
- };
Ну и шаблон поиска типа по номеру в списке:
- template<typename TList, int i>
- struct At
- {
- typedef typename At<typename TList::Next, i-1>::Value Value;
- };
- template<typename TList>
- struct At<TList,0>
- {
- typedef typename TList::Value Value;
- };
его я пока нигде не использовал, но он у меня уже написан, поэтому я его и выложил.
Некоторых наверное волнует скорость компиляции. В моем случае она увеличилось с 5 до 6 секунд, хотя это может быть вполне связано с увеличившимся количеством файлов для компиляции.
Ну вот вроде и все что хотел рассказать. Надеюсь теперь я буду писать сюда чаще.
Комментариев нет:
Отправить комментарий