VVVVVV??? VVVVVV!!! :)

в 7:36, , рубрики: bugs, c++, code analysis, game development, Gamedev, pvs-studio, static code analysis, VVVVVV, Блог компании PVS-Studio, Программирование, разработка игр

Если вы читаете этот текст – значит, вы либо подумали, что с заголовком статьи что-то не то, либо увидели в нём название знакомой компьютерной игры. VVVVVV – это инди-игра в жанре «платформер», завоевавшая сердца многих игроков своей приятной внешней простотой и не менее приятной внутренней сложностью. Несколько дней назад VVVVVV исполнилось 10 лет, и автор игры – Terry Cavanagh – отметил этот праздник публикацией её исходного кода. Что же «вкусненького» можно в нём найти? Ответ читайте в данной статье.

Рисунок 1

Введение

Ох, VVVVVV… Помню, как наткнулся на неё вскоре после релиза, и, будучи большим любителем пиксельных ретро-игр, с радостью установил её себе на компьютер. Помню свои первые впечатления: «И что, это всё? Просто бегать по квадратным комнатам?» – подумал я после нескольких минут игры. Я тогда еще не знал, что меня ждёт. Стоило мне выйти из стартовой локации, как я оказался в небольшом, но запутанном и витиеватом двумерном мире, полном необычных ландшафтов и неизвестных мне пиксельных артефактов.

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

Вернемся к исходному коду, выложенному в честь юбилея игры.

На данный момент я являюсь C++-разработчиком в команде PVS-Studio – статического анализатора кода для C, C++, C# и Java. Помимо непосредственно разработки, мы также занимаемся и продвижением нашего продукта. Для нас одним из лучших способов делать это является написание статей о проверке проектов с открытым исходным кодом. Наши читатели получают интересные статьи на тематику программирования, а мы получаем возможность наглядно продемонстрировать возможности PVS-Studio. Поэтому, узнав об открытии исходного кода VVVVVV, я просто не смог пройти мимо.

В данной статье мы рассмотрим некоторые интересные ошибки, найденные анализатором PVS-Studio в коде VVVVVV, а также проведём детальный разбор этих ошибок. Возвращайте вектор гравитации в положение «вниз» и усаживайтесь поудобнее: мы начинаем!

Обзор предупреждений, выданных анализатором

Предупреждение 1

V512 A call of the 'sprintf' function will lead to overflow of the buffer 'fileSearch'. FileSystemUtils.cpp 307

#define MAX_PATH          260

....

void PLATFORM_migrateSaveData(char *output)
{
  char oldLocation[MAX_PATH];
  char newLocation[MAX_PATH];
  char oldDirectory[MAX_PATH]; 
  char fileSearch[MAX_PATH];

  ....

  /* Same place, different layout. */
  strcpy(oldDirectory, output);

  sprintf(fileSearch, "%s\*.vvvvvv", oldDirectory);
  
  ....
}

Как можно заметить, строки fileSearch и oldDirectory имеют одинаковый размер: 260 символов. Строка форматирования (третий аргумент sprintf) после подстановки в нее содержимого строки oldDirectory будет иметь вид:

<i>содержимое_oldDirectory*.vvvvvv</i>

Эта строка на 9 символов длиннее, чем исходное значение oldDirectory. Именно эта последовательность символов и будет далее записана в fileSearch. Что же случится, если длина строки oldDirectory будет больше 251? Результирующая строка окажется длиннее, чем сможет вместить в себя fileSearch, что приведет к записи за пределы массива. Какие данные в оперативной памяти могут быть повреждены и к какому результату это приведет – это вопрос риторический :)

Предупреждение 2

V519 The 'background' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 1367, 1373. Map.cpp 1373

void mapclass::loadlevel(....)
{
  ....

  case 4: //The Warpzone
    tmap = warplevel.loadlevel(rx, ry, game, obj);
    fillcontent(tmap);
    roomname = warplevel.roomname;
    tileset = 1;
    background = 3;                    // <=
    dwgfx.rcol = warplevel.rcol;
    dwgfx.backgrounddrawn = false;

    warpx = warplevel.warpx;
    warpy = warplevel.warpy;
    background = 5;                    // <=
    if (warpy) background = 4;
    if (warpx) background = 3;
    if (warpx && warpy) background = 5;
    break;

  ....
}

Одной и той же переменной два раза подряд присваивается какое-то значение. При этом между присвоениями эта переменная нигде не используется. Странно… Возможно, такая последовательность не нарушает логику работы программы, но такие присвоения сами по себе говорят о некоторой путанице при написании кода. Является ли это ошибкой на самом деле – сможет сказать только автор. Хотя в коде есть и более яркие примеры этой ошибки:

void Game::loadquick(....)
{
  ....

  else if (pKey == "frames")
  {
    frames = atoi(pText);
    frames = 0;
  }

  ....
}

Здесь уже точно понятно, что где-то здесь кроется либо ошибка в логике, либо, как минимум, лишнее присвоение. Возможно вторая строчка была написана временно для отладки, а затем её забыли удалить. Всего PVS-Studio выдал 8 предупреждений о подобных ситуациях.

Предупреждение 3

V808 'pKey' object of 'basic_string' type was created but was not utilized. editor.cpp 1866

void editorclass::load(std::string &_path)
{
  ....

  std::string pKey(pElem->Value());

  ....

  if (pKey == "edEntities")
  {
    int i = 0;
    for (TiXmlElement *edEntityEl = pElem->FirstChildElement();
         edEntityEl;
         edEntityEl = edEntityEl->NextSiblingElement())
    {
      std::string pKey(edEntityEl->Value());                         // <=
      //const char* pText = edEntityEl->GetText() ;
      if (edEntityEl->GetText() != NULL)
      {
        edentity[i].scriptname = std::string(edEntityEl->GetText());
      }
      edEntityEl->QueryIntAttribute("x", &edentity[i].x);
      edEntityEl->QueryIntAttribute("y", &edentity[i].y);
      edEntityEl->QueryIntAttribute("t", &edentity[i].t);

      edEntityEl->QueryIntAttribute("p1", &edentity[i].p1);
      edEntityEl->QueryIntAttribute("p2", &edentity[i].p2);
      edEntityEl->QueryIntAttribute("p3", &edentity[i].p3);
      edEntityEl->QueryIntAttribute("p4", &edentity[i].p4);
      edEntityEl->QueryIntAttribute("p5", &edentity[i].p5);
      edEntityEl->QueryIntAttribute("p6", &edentity[i].p6);

      i++;

    }

    EditorData::GetInstance().numedentities = i;
  }

  ....
}

Очень странный код. Анализатор предупреждает о созданной, но не использованной переменной pKey, но на деле проблема оказалась интереснее. Я специально отметил стрелкой строку, на которую было выдано предупреждение, потому что данная функция содержит более одного определения строки с именем pKey. Да-да, внутри цикла for объявляется еще одна такая переменная, и своим именем она перекрывает ту, что объявлена вне цикла.

Таким образом, если вы обратитесь к значению строки pKey вне цикла for, вы получите значение, равное pElem->Value(), но если сделать то же самое уже внутри цикла, то вы получите значение, равное edEntityEl->Value(). Перекрытие имён – это достаточно грубая ошибка, которую бывает весьма тяжело отыскать самостоятельно в ходе обзора кода.

Предупреждение 4

V805 Decreased performance. It is inefficient to identify an empty string by using 'strlen(str) > 0' construct. A more efficient way is to check: str[0] != ''. physfs.c 1604

static char *prefDir = NULL;

....

const char *PHYSFS_getPrefDir(const char *org, const char *app)
{
  ....

  assert(strlen(prefDir) > 0);

  ...

  return prefDir;
} /* PHYSFS_getPrefDir */

Анализатор обнаружил место для потенциальной микрооптимизации. В нем для проверки C-style строки на пустоту используется функция strlen. Эта функция «пробегает» все элементы строки и проверяет каждый из них на равенство нуль-терминалу (''). Если на вход подается большая строка, то каждый её символ всё равно будет сравнён со строковым нулём.

Но ведь нам нужно только проверить, что строка непустая! Для этого достаточно только узнать, является ли первый символ строки нуль-терминалом. Поэтому для оптимизации данной проверки внутри assert стоит написать:

str[0] != ''

Именно такую рекомендацию и даёт нам анализатор. Конечно, вызов функции strlen находится в условии макроса assert, поэтому он будет выполняться только в отладочной версии, где скорость не столь важна. В релизной версии вызов функции исчезнет и код будет работать быстро. Тем не менее, мне хотелось продемонстрировать возможности анализатора по предложению микрооптимизаций.

Предупреждение 5

Чтобы показать следующую ошибку, мне необходимо прикрепить сюда два участка кода: объявление класса entclass и его конструктор. Начнем с объявления:

class entclass
{
public:
  entclass();

  void clear();

  bool outside();

public:
  //Fundamentals
  bool active, invis;
  int type, size, tile, rule;
  int state, statedelay;
  int behave, animate;
  float para;
  int life, colour;

  //Position and velocity
  int oldxp, oldyp;
  float ax, ay, vx, vy;
  int cx, cy, w, h;
  float newxp, newyp;
  bool isplatform;
  int x1, y1, x2, y2;
  //Collision Rules
  int onentity;
  bool harmful;
  int onwall, onxwall, onywall;

  //Platforming specific
  bool jumping;
  bool gravity;
  int onground, onroof;
  int jumpframe;
  //Animation
  int framedelay, drawframe, walkingframe, dir, actionframe;
  int yp; int xp;
};

Конструктор этого класса выглядит вот так:

entclass::entclass()
{
  clear();
}

void entclass::clear()
{
  // Set all values to a default,
  // required for creating a new entity
  active = false;
  invis = false;
  type = 0;
  size = 0;
  tile = 0;
  rule = 0;
  state = 0;
  statedelay = 0;
  life = 0;
  colour = 0;
  para = 0;
  behave = 0;
  animate = 0;

  xp = 0;
  yp = 0;
  ax = 0;
  ay = 0;
  vx = 0;
  vy = 0;
  w = 16;
  h = 16;
  cx = 0;
  cy = 0;
  newxp = 0;
  newyp = 0;

  x1 = 0;
  y1 = 0;
  x2 = 320;
  y2 = 240;

  jumping = false;
  gravity = false;
  onground = 0;
  onroof = 0;
  jumpframe = 0;

  onentity = 0;
  harmful = false;
  onwall = 0;
  onxwall = 0;
  onywall = 0;
  isplatform = false;

  framedelay = 0;
  drawframe = 0;
  walkingframe = 0;
  dir = 0;
  actionframe = 0;
}

Достаточно много полей, не правда ли? Неудивительно, что здесь затаилась ошибка, на которую PVS-Studio выдал предупреждение:

V730 It is possible that not all members of a class are initialized inside the constructor. Consider inspecting: oldxp, oldyp. Ent.cpp 3

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

Рисунок 2

Предупреждение 6

Рассмотрим код:

void mapclass::loadlevel(....)
{
  ....

  std::vector<std::string> tmap;

  ....

  tmap = otherlevel.loadlevel(rx, ry, game, obj);
  fillcontent(tmap);

  .... // Вектор tmap изменяется еще много раз.
}

Предупреждение PVS-studio: V688 The 'tmap' local variable possesses the same name as one of the class members, which can result in a confusion. Map.cpp 1192

Действительно, если заглянуть внутрь класса mapclass, то можно обнаружить там такой же вектор с таким же именем:

class mapclass
{
public:
  ....

    std::vector <int> roomdeaths;
    std::vector <int> roomdeathsfinal;
    std::vector <int> areamap;
    std::vector <int> contents;
    std::vector <int> explored;
    std::vector <int> vmult;
    std::vector <std::string> tmap;       // <=

  ....
};

К сожалению, объявление вектора с таким же именем внутри функции делает невидимым вектор, объявленный в классе. Получается, что на протяжении всей функции loadlevel вектор tmap изменяется только внутри функции. Вектор, объявленный в классе, остается неизменным!

Занимательно, что PVS-Studio обнаружил аж целых 20 таких фрагментов кода! По большей части они связаны со временными переменными, которые «для удобства» были объявлены, как члены класса. Автор игры (и единственный её разработчик) сам писал, что раньше имел эту плохую привычку. Вы можете прочитать об этом в посте, ссылку на который я прикрепил в начале этой статьи.

Также он отмечает, что подобные именования приводили к вредным и сложно отлавливаемым багам. Что ж, такие баги действительно могут быть вредными, а вот с помощью статического анализа отловить их не составит большого труда :)

Предупреждение 7

V601 The integer type is implicitly cast to the char type. Game.cpp 4997

void Game::loadquick(....)
{
  ....

  else if (pKey == "totalflips")
  {
      totalflips = atoi(pText);
  }
  else if (pKey == "hardestroom")
  {
      hardestroom = atoi(pText);        // <=
  }
  else if (pKey == "hardestroomdeaths")
  {
      hardestroomdeaths = atoi(pText);
  }

  ....
}

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

//Some stats:
int totalflips;
std::string hardestroom;
int hardestroomdeaths;

Переменные totalflips и hardestroomdeaths имеют целочисленный тип, и поэтому присвоить в них результат функции atoi – совершенно нормально. Но что будет, если присвоить целочисленное значение в std::string? Оказывается, с точки зрения языка такое присвоение совершенно валидно. В итоге в переменную hardestroom будет записано какое-то непонятное значение!

Предупреждение 8

V1004 The 'pElem' pointer was used unsafely after it was verified against nullptr. Check lines: 1739, 1744. editor.cpp 1744

void editorclass::load(std::string &_path)
{
  ....

  TiXmlHandle hDoc(&doc);
  TiXmlElement *pElem;
  TiXmlHandle hRoot(0);
  version = 0;

  {
    pElem = hDoc.FirstChildElement().Element();
    // should always have a valid root
    // but handle gracefully if it does
    if (!pElem)
    {
      printf("No valid root! Corrupt level file?n");
    }

    pElem->QueryIntAttribute("version", &version);    // <=
    // save this for later
    hRoot = TiXmlHandle(pElem);
  }

  ....
}

Анализатор предупреждает, что указатель pElem небезопасно используется сразу после того, как он был проверен на nullptr. Чтобы убедиться, что анализатор прав, заглянем в определение функции Element(), возвращаемым значением которой инициализируется указатель pElem:

/** @deprecated use ToElement.
  Return the handle as a TiXmlElement. This may return null.
*/
TiXmlElement *Element() const
{
  return ToElement();
}

Как видно по комментарию, эта функция может вернуть null.

Теперь представим, что это действительно произошло. Что случится в этом случае? Дело в том, что такая ситуация никак не будет обработана. Да, будет выведено сообщение о том, что что-то пошло не так, но буквально строчкой ниже некорректный указатель будет разыменован. Такое разыменование, в свою очередь, приведет либо к падению программы, либо к неопределенному поведению. Это довольно серьезная ошибка.

Предупреждение 9

На следующий участок кода PVS-Studio выдал четыре предупреждения:

  • V560 A part of conditional expression is always true: x >= 0. editor.cpp 1137
  • V560 A part of conditional expression is always true: y >= 0. editor.cpp 1137
  • V560 A part of conditional expression is always true: x < 40. editor.cpp 1137
  • V560 A part of conditional expression is always true: y < 30. editor.cpp 1137

int editorclass::at( int x, int y )
{
  if(x<0) return at(0,y);
  if(y<0) return at(x,0);
  if(x>=40) return at(39,y);
  if(y>=30) return at(x,29);

  if(x>=0 && y>=0 && x<40 && y<30)
  {
      return contents[x+(levx*40)+vmult[y+(levy*30)]];
  }
  return 0;
}

Все предупреждения относятся к последнему if-выражению. Проблема в том, что все четыре проверки, которые в нём выполняются, всегда будут возвращать true. Не сказал бы, что это серьезная ошибка, но получилось довольно забавно. Автор решил отнестись к этой функции серьезно и на всякий случай проверил каждую переменную еще раз :)

Данную проверку можно убрать, т.к. поток выполнения всё равно никогда не дойдет до выражения "return 0;". Хоть это и не изменит логики программы, но освободит её от лишних проверок и мертвого кода.

Предупреждение 10

В своей статье про юбилей игры Терри с иронией рассказывает, что одним из элементов, управляющих логикой игры, был огромный switch из функции Game::updatestate(), отвечающий сразу за большое количество различных состояний игры. И было довольно ожидаемо, что обнаружу следующее предупреждение:

V2008 Cyclomatic complexity: 548. Consider refactoring the 'Game::updatestate' function. Game.cpp 612

Да, вы все правильно поняли: PVS-Studio оценил цикломатическую сложность функции в 548 единиц. Пятьсот сорок восемь!!! Вот это я понимаю – «опрятный код». И это при том, что, по сути, кроме switch-выражения в функции ничего больше нет. В самом switch я насчитал более 300 case-выражений.

У нас в офисе идет небольшое соревнование между авторами за самую длинную статью. Я бы с радостью привел сюда весь код функции (3450 строк), но такая победа была бы нечестной, поэтому я ограничусь просто ссылкой на громадный switch. Рекомендую перейти по ней и оценить весь масштаб самостоятельно! Кстати, помимо Game::updatestate(), PVS-Studio нашел еще целых 44 функции с завышенной цикломатической сложностью, 10 из которых имеют сложность более 200.

Рисунок 3

Заключение

Думаю, выписанных ошибок достаточно для статьи. Да, ошибок в проекте оказалось немало, но в этом как раз и фишка: выложив свой код, Terry Cavanagh показал, что не обязательно быть хорошим программистом, чтобы сделать хорошую игру. Сейчас, спустя 10 лет, Терри вспоминает те времена с иронией. Важно уметь учиться на своих ошибках, и практика – лучший способ делать это. А если ваша практика еще может породить такую игру, как VVVVVV, то это вообще шикарно! Эхх… пойду-ка я, наверное, еще в неё поиграю :)

Это были не все ошибки, найденные в коде игры. Если вы хотите самостоятельно посмотреть, что еще можно найти – предлагаю скачать и попробовать PVS-Studio! Также не забываете, что для открытых проектов мы предоставляем бесплатную лицензию.

Автор: Георгий Грибков

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js