вторник, 10 апреля 2012 г.

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

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

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

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

воскресенье, 8 апреля 2012 г.

Списки типов

Давно я тут ничего не писал, хотя было много поводов. Теперь я работаю в 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;
  11.     int     m_type;
  12.     std::string m_name;
  13. public:
  14.     Node(int type, const std::string& name);
  15.     ~Node();
  16.     static Node* Create( int type, Node* child0 = 0, Node* child1 = 0, Node* child2 = 0, Node* child3 = 0 );
  17.     static Node* Create( int type, const std::string& name, Node* child0 = 0, Node* child1 = 0, Node* child2 = 0, Node* child3 = 0 );
  18.     static void Destroy( Node*& node );
  19.     static void DestroyList( Node*& node );
  20.     static Node* Join( Node* n1, Node* n2 );
  21.    
  22.     Node* GetChild(int i) const { return m_child[i]; }
  23.     int GetType() const { return m_type; }
  24.     Node* GetNext() const { return m_next; }
  25.     const std::string& GetName() const { return m_name; }
  26. };

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

  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. };
  4. typedef TypeList<None,
  5.         ...
  6.         TypeList<If,
  7.         TypeList<For,
  8.         ...
  9.         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. };
  16. template<typename TList, typename Val, int depth = 0>
  17. struct Find
  18. {
  19.     enum
  20.     {
  21.         Value = Compare<typename TList::Value, Val>::Value ? depth : Find<typename TList::Next, Val, depth + 1>::Value,
  22.     };
  23. };
  24. template<typename Val, int depth>
  25. struct Find<Empty, Val, depth>
  26. {
  27.     enum
  28.     {
  29.         Value = -1
  30.     };
  31. };

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

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

  1. #define ID(type) (Find<NodeTypes, type>::Value)
  2. 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;
  4.     enum
  5.     {
  6.         Condition,
  7.         ThenStatement,
  8.         ElseStatement,
  9.     };
  10.     static Node* Create( Node* condition, Node* thenStatements, Node* elseStatements = 0 );
  11. };
  12. Node* If::Create( Node* condition, Node* thenStatements, Node* elseStatements )
  13. {
  14.     static_assert( ID(self) != -1, "Type should be registered in NodeTypes list" );
  15.     return Node::Create( ID(self) , condition, thenStatements, elseStatements );
  16. }

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

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. };
  16. template<>
  17. struct TMax<Empty>
  18. {
  19.     enum
  20.     {
  21.         Value = 0
  22.     };
  23. };
  24. // использование
  25. enum
  26. {
  27.     kChildrenCount = TMax<NodeTypes>::Value
  28. };

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

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

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

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

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

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

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

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