Cataclysm Dark Days Ahead, статический анализ и рогалики

Скорее всего, из названия статьи вы уже догадались, что в центре внимания ошибки в исходном коде. Но это вовсе не единственное, о чем пойдет речь в этой статье. Если кроме С++ и ошибок в чужом коде вас привлекают необычные игры и вам интересно узнать, что это такие за «рогалики» и с чем их едят, добро пожаловать под кат!

В своем поиске необычных игр я наткнулась на игру Cataclysm Dark Days Ahead, отличающуюся от других необычной графикой: она реализована с помощью разноцветных символов ASCII на черном фоне.

Что поражает в этой игре и ей подобных, это сколько всего в них реализовано. Конкретно в Cataclysm, например, даже для создания персонажа хочется поискать гайды, так как разных параметров, особенностей и начальных сюжетов десятки, не говоря уже о вариациях событий в самой игре.

Это игра с открытым исходным кодом, и, к тому же, написана на С++. Так что невозможно было пройти мимо и не прогнать этот проект через статический анализатор PVS-Studio, в разработке которого я сейчас принимаю активное участие. Сам проект удивил высоким качеством кода, однако, в нем все равно находятся некоторые недоработки и несколько из них я рассмотрю в этой статье.

К настоящему моменту с помощью PVS-Studio было проверено уже достаточно много игр. Например, вы можете ознакомиться с другой нашей статьей "Статический анализ в видеоигровой индустрии: топ-10 программных ошибок".

Логика

Пример 1:

Следующий пример представляет собой типичную ошибку копирования.

V501 There are identical sub-expressions to the left and to the right of the '||' operator: rng(2, 7) < abs(z) || rng(2, 7) < abs(z) overmap.cpp 1503

bool overmap::generate_sub( const int z )
{
  ....
if( rng( 2, 7 ) < abs( z ) || rng( 2, 7 ) < abs( z ) )
{
  ....
  }
  ....
}

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

Аналогичное предупреждение:

• V501 There are identical sub-expressions 'one_in(100000 / to_turns <int> (dur))' to the left and to the right of the '&&' operator. player_hardcoded_effects.cpp 547

Пример 2:

V728 An excessive check can be simplified. The '(A && B) || (!A && !B)' expression is equivalent to the 'bool(A) == bool(B)' expression. inventory_ui.cpp 199

bool inventory_selector_preset::sort_compare( .... ) const
{
  ....
  const bool left_fav  = g->u.inv.assigned.count( lhs.location->invlet );
  const bool right_fav = g->u.inv.assigned.count( rhs.location->invlet );
  if( ( left_fav && right_fav ) || ( !left_fav && !right_fav ) ) {
    return ....
  } 
  ....
}

Ошибки в условии нет, но оно излишне усложнено. Стоило бы сжалиться над тем, кому придется разбирать это условие, и написать проще if( left_fav == right_fav ).

Аналогичное предупреждение:

• V728 An excessive check can be simplified. The '(A && !B) || (!A && B)' expression is equivalent to the 'bool(A) != bool(B)' expression. iuse_actor.cpp 2653

Отступление I

Для меня оказалось открытием, что игры, которые на сегодняшний день называют «рогаликами» — это лишь достаточно лайтовые последователи старого жанра roguelike игр. Началось все с культовой игры Rogue 1980 года, ставшей образцом для подражания и вдохновившей множество студентов и программистов на создание собственных игр. Полагаю, многое также привнесло сообщество настольной ролевой игры DnD и её вариаций.

Микрооптимизации

Пример 3:

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

V801 Decreased performance. It is better to redefine the second function argument as a reference. Consider replacing 'const… type' with 'const… &type'. map.cpp 4644

template <typename Stack>
std::list<item> use_amount_stack( Stack stack, const itype_id type )
{
  std::list<item> ret;
  for( auto a = stack.begin(); a != stack.end() && quantity > 0; ) {
      if( a->use_amount( type, ret ) ) {
          a = stack.erase( a );
      } else {
          ++a;
      }
  }
  return ret;
}

Здесь за itype_id скрывается std::string. Так как аргумент все равно передается константным, что не позволит его изменить, быстрее было бы просто передать в функцию ссылку на переменную и не тратить ресурсы на копирование. И хотя, скорее всего, строка там будет совсем небольшая, но постоянное копирование без видимой на то причины излишне. Тем более, что эта функция вызывается из разных мест, многие из которых, в свою очередь, также получают type извне и копируют его.

Аналогичные предупреждения:

• V801 Decreased performance. It is better to redefine the third function argument as a reference. Consider replacing 'const… evt_filter' with 'const… &evt_filter'. input.cpp 691
• V801 Decreased performance. It is better to redefine the fifth function argument as a reference. Consider replacing 'const… color' with 'const… &color'. output.h 207
• В целом, анализатор выдал 32 таких предупреждения.

Пример 4:

V813 Decreased performance. The 'str' argument should probably be rendered as a constant reference. catacharset.cpp 256

std::string base64_encode( std::string str )
{
  if( str.length() > 0 && str[0] == '#' ) {
    return str;
  }
  int input_length = str.length();
  std::string encoded_data( output_length, '' );
  ....
  for( int i = 0, j = 0; i < input_length; ) {
    ....
  }
  for( int i = 0; i < mod_table[input_length % 3]; i++ ) {
    encoded_data[output_length - 1 - i] = '=';
  }
  return "#" + encoded_data;
}

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

Это предупреждение также было не единичным, всего таких случаев нашлось 26.

Аналогичные предупреждения:

• V813 Decreased performance. The 'message' argument should probably be rendered as a constant reference. json.cpp 1452
• V813 Decreased performance. The 's' argument should probably be rendered as a constant reference. catacharset.cpp 218
• И так далее...

Отступление II

Некоторые из классических roguelike игр до сих пор активно развиваются. Если зайти в репозитории GitHub Cataclysm DDA или NetHack, то можно увидеть, что изменения активно вносятся каждый день. NetHack вообще является самой старой игрой, разработка которой идет до сих пор: её релиз произошел в июле 1987 года, а последняя версия датируется 2018 годом.

Одной из известных, однако, более поздних игр этого жанра является Dwarf Fortress, разрабатываемая с 2002 года и впервые выпущенная в 2006 году. «Losing is fun» («Проигрывать весело») — девиз игры, в точности отражающий её суть, так как победить в ней невозможно. Эта игра в 2007 году заслужила звание лучшей roguelike игры года в результате голосования, которое ежегодно проводится на сайте ASCII GAMES.

Кстати, тем, кто интересуется этой игрой, возможно будет интересна следующая новость. Dwarf Fortress выйдет в Steam с улучшенной 32-битной графикой. С обновлённой картинкой, над которой работают два опытных модера игры, премиум-версия Dwarf Fortress получит дополнительные музыкальные треки и поддержку Steam Workshop. Но если что, владельцы платной версии Dwarf Fortress смогут поменять обновлённую графику на прежний вид в ASCII. Подробнее.

Переопределение оператора присваивания

Примеры 5, 6:

Также нашлась интересная пара сходных предупреждений.

V690 The 'JsonObject' class implements a copy constructor, but lacks the '=' operator. It is dangerous to use such a class. json.h 647

class JsonObject
{
  private:
  ....
  JsonIn *jsin;
  ....

  public:
  JsonObject( JsonIn &jsin );
  JsonObject( const JsonObject &jsobj );
  JsonObject() : positions(), start( 0 ), end( 0 ), jsin( NULL ) {}
  ~JsonObject() {
    finish();
  }
  void finish(); // moves the stream to the end of the object
  ....
  void JsonObject::finish()
  {
    ....
  }
  ....
}

Этот класс обладает конструктором копирования и деструктором, однако, для него отсутствует перегрузка оператора присваивания. Проблема здесь состоит в том, что автоматически сгенерированный оператор присваивания может лишь присвоить указатель к JsonIn. В результате оба объекта класса JsonObject указывают на один тот же JsonIn. Неизвестно, может ли где-то сейчас возникнуть такая ситуация, но, в любом случае, это — грабли, на которые рано или поздно кто-то наступит.

Аналогичная проблема присутствует в следующем классе.

V690 The 'JsonArray' class implements a copy constructor, but lacks the '=' operator. It is dangerous to use such a class. json.h 820

class JsonArray
{
  private:
  ....
  JsonIn *jsin;
  ....

  public:
  JsonArray( JsonIn &jsin );
  JsonArray( const JsonArray &jsarr );
  JsonArray() : positions(), ...., jsin( NULL ) {};
  ~JsonArray() {
    finish();
  }

  void finish(); // move the stream position to the end of the array
  void JsonArray::finish()
  {
    ....
  }
}

Более подробно об опасности нехватки перегрузки оператора присваивания для сложного класса можно почитать в статье "The Law of The Big Two" (или в переводе этой статьи "CИ++: Закон Большой Двойки").

Примеры 7, 8:

Еще один пример, связанный с перегруженным оператором присваивания, но на этот раз речь о его конкретной реализации.

V794 The assignment operator should be protected from the case of 'this == &other'. mattack_common.h 49

class StringRef {
  public:
    ....
  private:
    friend struct StringRefTestAccess;
    char const* m_start;
    size_type m_size;
    char* m_data = nullptr;
    ....
auto operator = ( StringRef const &other ) noexcept -> StringRef& {
  delete[] m_data;
  m_data = nullptr;
  m_start = other.m_start;
  m_size = other.m_size;
  return *this;
}

Проблема в том, что данная реализация не защищена от присвоения объекта самому себе, что является небезопасной практикой. То есть, если этому оператору будет передана ссылка на *this, может произойти утечка памяти.

Схожий пример ошибочной перегрузки оператора присваивания с интересным побочным эффектом:

V794 The assignment operator should be protected from the case of 'this == &rhs'. player_activity.cpp 38

player_activity &player_activity::operator=( const player_activity &rhs )
{
  type = rhs.type;
  ....
  targets.clear();
  targets.reserve( rhs.targets.size() );

  std::transform( rhs.targets.begin(),
                  rhs.targets.end(),
                  std::back_inserter( targets ),
                  []( const item_location & e ) {
                    return e.clone();
                  } );

  return *this;
}

В этом случае точно так же отсутствует проверка на присваивание объекта самому себе. Но в дополнение заполняется вектор. Если попытаться такой перегрузкой присвоить объект самому себе, то в поле targets получим удвоенный вектор, часть элементов которого испорчена. Однако здесь перед transform присутствует clear, что очистит вектор объекта и данные будут потеряны.

Отступление III

В 2008 году рогалики даже обзавелись формальным определением, которое получило эпичное название «Берлинская интерпретация». Согласно этому определению, основными чертами таких игр являются:

• Случайно сгенерированный мир, что увеличивает реиграбельность;
• Permadeath: если ваш персонаж умирает — он умирает навсегда и все предметы теряются;
• Пошаговость: изменения происходят только вместе с действием игрока, пока действие не произведено — время останавливается;
• Выживание: ресурсы крайне ограничены.

Ну и самое главное: рогалики нацелены прежде всего на исследование и открытие мира, поиск новых способов использования предметов и прохождения подземелий.

Обычная ситуация в Cataclysm DDA: промерзли и голодны до смерти, вас мучает жажда, да и вообще у вас вместо ног шесть тентаклей.

Немаловажные детали

Пример 9:

V1028 Possible overflow. Consider casting operands of the 'start + larger' operator to the 'size_t' type, not the result. worldfactory.cpp 638

void worldfactory::draw_mod_list( int &start, .... )
{
  ....
  int larger = ....;
  unsigned int iNum = ....;  
  ....
  for( .... )
  {
    if(   iNum >= static_cast<size_t>( start )
       && iNum < static_cast<size_t>( start + larger ) )
    {
      ....
    }
    ....
  }
....
}

Похоже, программист хотел избежать переполнения. Но приведение результата сложения в таком случае бессмысленно, так как переполнение возникнет уже при сложении чисел, и расширение типов произведется над бессмысленным результатом. Для того, чтобы избежать этой ситуации, необходимо привести лишь один из аргументов к большему типу: (static_cast<size_t> (start) + larger).

Пример 10:

V530 The return value of function 'size' is required to be utilized. worldfactory.cpp 1340

bool worldfactory::world_need_lua_build( std::string world_name )
{
#ifndef LUA
....
#endif
    // Prevent unused var error when LUA and RELEASE enabled.
    world_name.size();
    return false;
}

Для таких случаев существует небольшая хитрость. Если переменная оказывается неиспользованной, вместо того, чтобы пытаться вызвать какой-либо метод, можно просто написать (void)world_name для подавления предупреждения компилятора.

Пример 11:

V812 Decreased performance. Ineffective use of the 'count' function. It can possibly be replaced by the call to the 'find' function. player.cpp 9600

bool player::read( int inventory_position, const bool continuous )
{
  ....
  player_activity activity;

  if(   !continuous
     || !std::all_of( learners.begin(),
                      learners.end(), 
                      [&]( std::pair<npc *, std::string> elem )
                      {
                        return std::count( activity.values.begin(),
                                           activity.values.end(), 
                                           elem.first->getID() ) != 0;
                      } )
  {
    ....
  }
  ....
}

Судя по тому, что результат count сравнивается с нулем, идея в том, чтобы понять, есть ли хоть один требуемый элемент среди activity. Но count вынужден проходить по всему контейнеру, так как он считает все вхождения элемента. В этой ситуации будет быстрее использовать find, который останавливается после первого же найденного совпадения.

Пример 12:

Следующая ошибка легко обнаруживается, если знать об одной тонкости.

V739 EOF should not be compared with a value of the 'char' type. The 'ch' should be of the 'int' type. json.cpp 762

void JsonIn::skip_separator()
{
  signed char ch;
  ....
  if (ch == ',') {
    if( ate_separator ) {
      ....
    }
    ....
  } else if (ch == EOF) {
  ....
}

Это одна из тех ошибок, которые бывает сложно заметить, если не знать, что EOF определен как -1. Соответственно, если пытаться сравнивать его с переменной типа signed char, условие почти всегда оказывается false. Единственное исключение, это если кодом символа будет 0xFF (255). При сравнении такой символ превратится в -1 и условие окажется верным.

Пример 13:

Следующая небольшая ошибка однажды может стать критической. Не зря она есть в списке CWE как CWE-834. А их, кстати, было целых пять.

V663 Infinite loop is possible. The 'cin.eof()' condition is insufficient to break from the loop. Consider adding the 'cin.fail()' function call to the conditional expression. action.cpp 46

void parse_keymap( std::istream &keymap_txt, .... )
  {
    while( !keymap_txt.eof() ) {
    ....
  }
}

Как сказано в предупреждении, проверки на достижение конца файла при чтении недостаточно, необходимо также проводить проверку на ошибку считывания cin.fail(). Изменим код для более безопасного считывания:

while( !keymap_txt.eof() )
{
  if(keymap_txt.fail())
  {
    keymap_txt.clear();
    keymap_txt.ignore(numeric_limits<streamsize>::max(),'n');
    break;
  }
  ....
}

keymap_txt.clear() нужен для того, чтобы при ошибке считывания из файла убрать из потока состояние (флажок) ошибки, иначе дальше считать текст будет нельзя. keymap_txt.ignore с параметрами numeric_limits<streamsize>::max() и управляющим символом перевода строки позволяет пропустить оставшуюся часть строки.

Есть и гораздо более простой способ остановки считывания:

while( !keymap_txt )
{
  ....
}

Если использовать поток в контексте логики, он конвертирует себя в значение эквивалентное true, пока не будет достигнут EOF.

Отступление IV

Сейчас наибольшую популярность имеют игры, которые сочетают в себе признаки roguelike игр и других жанров: платформеров, стратегий и др. Такие игры стали называть roguelike-like или roguelite. К таким играм относят такие известные тайтлы, как Don't Starve, The Binding of Isaac, FTL:Faster Than Light, Darkest Dungeon и даже Diablo.

Хотя временами разница между roguelike и roguelite столь мала, что не понятно, к какому жанру отнести игру. Кто-то считает, что Dwarf Fortress уже не roguelike, а для кого-то и Diablo — классический рогалик.

Заключение

Хоть проект в целом и является примером качественного кода, и не удалось найти много серьёзных ошибок, это не значит, что использование статического анализа для него является избыточным. Суть не в разовых проверках, которые делаем с целью популяризации методологии статического анализа кода, а в регулярном использовании анализатора. Тогда многие ошибки можно выявить на самом раннем этапе и, следовательно, сократить стоимость их исправления. Пример расчётов.

Над рассмотренной игрой и сейчас ведется активная работа, и существует активное сообщество моддеров. Причем она портирована на множество платформ, в том числе iOS и Android. Так что, если вас заинтересовала эта игра, рекомендую попробовать!

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Victoria Khanieva. Cataclysm Dark Days Ahead: Static Analysis and Roguelike Games

Автор: vkhanieva

Источник