Давно я тут ничего не писал, хотя было много поводов. Теперь я работаю в 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 секунд, хотя это может быть вполне связано с увеличившимся количеством файлов для компиляции.
Ну вот вроде и все что хотел рассказать. Надеюсь теперь я буду писать сюда чаще.