Коварная строка

Сегодня долго искал ошибку в таком коде

1. const char * const names[] =
2. {
3. ...
4.     "Return",
5.     "If" 
6.     "For",
7.     "Break",
8. ...
9. };

проявлялась она тем, что читалось неверное имя по номеру идентификатора. Потом заметил что вместо “If” печатается “IfFor”.

Списки типов

Давно я тут ничего не писал, хотя было много поводов. Теперь я работаю в Ubisoft, живу в Киеве. Перед уходом из Gameloft мы закончили Tom Clancy's Rainbow Six®: Shadow Vanguard, собственно работа над проектом и привела к задержке моего перехода, который я планировал совершить на полгода раньше. В Ubisoft я уже успел поработать над Assassin’s Creed: Revelations, побывать в Румынии, получить несколько футболок с логотипом игры и несколько дисков, один из которых подарочный. Но сегодняшний пост не об этом.

Когда мы заканчивали AC:R у нас было много времени и мало багов, в такой ситуации каждый уважающий себя программист начинает работать над расширением своего мировоззрения. Меня почему-то заинтересовало написание своего скриптового языка. Я выбрал синтаксис похожий на JavaScript, в качестве лексера re2c, парсер lemon и начал при помощи этих инструментов собирать синтаксическое дерево.

Я не большой любитель полиморфизма, особенно там где он не нужен, поэтому в качестве ноды дерева выбрал такую структуру:

1. class Node
2. {
3. public:
4.     enum
5.     {
6.         kChildrenCount = 4
7.     };
8. private:
9.     Node*   m_child[kChildrenCount];
10.     Node*   m_next;
12.     int     m_type;
13.     std::string m_name;
14. public:
15.     Node(int type, const std::string& name);
16.     ~Node();
18.     static Node* Create( int type, Node* child0 = 0, Node* child1 = 0, Node* child2 = 0, Node* child3 = 0 );
19.     static Node* Create( int type, const std::string& name, Node* child0 = 0, Node* child1 = 0, Node* child2 = 0, Node* child3 = 0 );
20.     static void Destroy( Node*& node );
21.     static void DestroyList( Node*& node );
22.     static Node* Join( Node* n1, Node* n2 );
23.    
24.     Node* GetChild(int i) const { return m_child[i]; }
25.     int GetType() const { return m_type; }
26.     Node* GetNext() const { return m_next; }
27.     const std::string& GetName() const { return m_name; }
28. };

Структурка довольно простая, типичное ее использование раньше было таким:

1. 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 оно выглядит так:

1. struct If
2. {
3.     enum
4.     {
5.         Condition,
6.         ThenStatement,
7.         ElseStatement,
8.     };
9. };
10.  

Потом я подумал, а почему бы не добавить в каждую из таких структур функцию по созданию ноды. В коде парсера, вместо безликих Node::Create появились вполне симпатичные If::Create которое списком параметрров подсказывает что и где оно ждет, а при компиляции я получаю детей ноды по вполне симпатичным идентификаторам типа node->GetChild(If::Condition), хотя ошибки все еще возможны, код в целом стал более наглядным.

Но на этом я не успокоился. тут я вспомнил про список типов из книги Александреску. Книги под рукой не было, поэтому решил написать его сам, меня очень удивило то, что написание списка типов это не такая уж и сложная задача. Все что мне нужно было, это получение по типу номера в списке, для того чтоб избавиться от enum’a с константами типов ноды.

Собственно сам список:

1. template<typename Left, typename Right>
2. struct TypeList
3. {
4.     typedef Left Value;
5.     typedef Right Next;
6. };

Я не стал делать красивые дефайны для заполнения списка, поэтому заполнил его обычным typedef

1. struct Empty
2. {
3. };
5. typedef TypeList<None,
6.         ...
7.         TypeList<If,
8.         TypeList<For,
9.         ...
10.         Empty > ... > > .. >  NodeTypes;

Вот шаблоны для поиска и сравнения:

1. template<typename Left, typename Right>
2. struct Compare
3. {
4. private:
5.     typedef int one;
6.     typedef char two;
7.     static_assert( sizeof(one) != sizeof(two), "one and two must be types with different size" );
8.     static one compare( Left left, Left right );
9.     static two compare( Left left, ... );
10. public:
11.     enum
12.     {
13.         Value = sizeof(one) == sizeof(compare( (Left()), (Right()) )) ? 1 : 0,
14.     };
15. };
17. template<typename TList, typename Val, int depth = 0>
18. struct Find
19. {
20.     enum
21.     {
22.         Value = Compare<typename TList::Value, Val>::Value ? depth : Find<typename TList::Next, Val, depth + 1>::Value,
23.     };
24. };
26. template<typename Val, int depth>
27. struct Find<Empty, Val, depth>
28. {
29.     enum
30.     {
31.         Value = -1
32.     };
33. };

Они компилируются в VC++2010EE, и я думаю они скомпилируются в gcc (разве что static_assert нужно будет убрать). О работе шаблона Compare можно почитать в книге Александреску, а Find рекурсивно проходит по списку и если находит нужный элемент возвращает его номер, иначе –1.

Для упрощения поиска типа в списке я написал такой макрос и пример его использования:

1. #define ID(type) (Find<NodeTypes, type>::Value)
3. if ( node->GetType() == ID(If) ) ...

Когда С++11 будет лучше поддерживаться студийным компилятором, я заменю этот макрос на constexpr.

В результате всего этого функция создания ноды стала выглядеть так:

1. Node* If::Create( Node* condition, Node* thenStatements, Node* elseStatements )
2. {
3.     static_assert( ID(If) != -1, "Type should be registered in NodeTypes list" );
4.     return Node::Create( ID(If) , condition, thenStatements, elseStatements );
5. }

Если добавить в каждую структуру тайпдеф который будет указывать сам на свой тип то код функции станет более пригодным для “копипаст” программирования:

1. struct If
2. {
3.     typedef If  self;
5.     enum
6.     {
7.         Condition,
8.         ThenStatement,
9.         ElseStatement,
10.     };
11.     static Node* Create( Node* condition, Node* thenStatements, Node* elseStatements = 0 );
12. };
14. Node* If::Create( Node* condition, Node* thenStatements, Node* elseStatements )
15. {
16.     static_assert( ID(self) != -1, "Type should be registered in NodeTypes list" );
17.     return Node::Create( ID(self) , condition, thenStatements, elseStatements );
18. }

Но и на этом я не успокоился. В самом начале, когда я привел структуру ноды, в ней был указан размер массива детей ноды:

kChildrenCount = 4

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

1. template<typename TList>
2. struct TMax
3. {
4. private:
5.     enum
6.     {
7.         Current = TList::Value::Total,
8.         Max = TMax<typename TList::Next>::Value
9.     };
10. public:
11.     enum
12.     {
13.         Value = (Current > Max) ? Current : Max
14.     };
15. };
17. template<>
18. struct TMax<Empty>
19. {
20.     enum
21.     {
22.         Value = 0
23.     };
24. };
26. // использование
27. enum
28. {
29.     kChildrenCount = TMax<NodeTypes>::Value
30. };

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

Вот еще шаблон который возвращает длину списка типов:

1. template<typename TList>
2. struct Len
3. {
4.     enum
5.     {
6.         Value = Len<typename TList::Next>::Value + 1
7.     };
8. };
10. template<>
11. struct Len<Empty>
12. {
13.     enum
14.     {
15.         Value = 0
16.     };
17. };

Ну и шаблон поиска типа по номеру в списке:

1. template<typename TList, int i>
2. struct At
3. {
4.     typedef typename At<typename TList::Next, i-1>::Value Value;
5. };
7. template<typename TList>
8. struct At<TList,0>
9. {
10.     typedef typename TList::Value Value;
11. };

его я пока нигде не использовал, но он у меня уже написан, поэтому я его и выложил.

Некоторых наверное волнует скорость компиляции. В моем случае она увеличилось с 5 до 6 секунд, хотя это может быть вполне связано с увеличившимся количеством файлов для компиляции.

Ну вот вроде и все что хотел рассказать. Надеюсь теперь я буду писать сюда чаще.