Victoria Khanieva

Apr 25 2019

Tags:

#Cpp #GameDev

Cataclysm Dark Days Ahead: Static Analysis and Roguelike Games

Apr 25 2019

Author: Victoria Khanieva

Logic
Digression I
Micro-optimizations
Digression II
Overriding the assignment operator
Digression III
Details that matter
Digression IV
Conclusion

You must have already guessed from the title that today's article will be focusing on bugs in software source code. But not only that. If you are not only interested in C++ and in reading about bugs in other developers' code but also dig unusual video games and wonder what "roguelikes" are and how you play them, then welcome to read on!

While searching for unusual games, I stumbled upon Cataclysm Dark Days Ahead, which stands out among other games thanks to its graphics based on ASCII characters of various colors arranged on the black background.

One thing that amazes you about this and other similar games is how much functionality is built into them. Particularly in Cataclysm, for instance, you can't even create a character without feeling an urge to google some guides because of the dozens of parameters, traits, and initial scenarios available, not to mention the multiple variations of events occurring throughout the game.

Since it's a game with open-source code, and one written in C++, we couldn't walk by without checking it with our static code analyzer PVS-Studio, in the development of which I am actively participating. The project's code is surprisingly high-quality, but it still has some minor defects, some of which I will talk about in this article.

Quite a lot of games have been checked with PVS-Studio already. You can find some examples in our article "Static Analysis in Video Game Development: Top 10 Software Bugs".

Logic

Example 1:

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 ....
  } 
  ....
}

This condition is logically correct, but it's overcomplicated. Whoever wrote this code should have taken pity on their fellow programmers who will be maintaining it. It could be rewritten in a simpler form: if( left_fav == right_fav ) .

Another similar error:

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

Digression I

I was surprised to discover that games going by the name of "roguelikes" today are only more moderate representatives of the old genre of roguelike games. It all started with the cult game Rogue of 1980, which inspired many students and programmers to create their own games with similar elements. I guess a lot of influence also came from the community of the tabletop game DnD and its variations.

Micro-optimizations

Example 2:

Warnings of this group point to spots that could potentially be optimized rather than bugs.

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;
}

In this code, itype_id is actually a disguised std::string. Since the argument is passed as a constant anyway, which means it's immutable, simply passing a reference to the variable would help to enhance performance and save computational resources by avoiding the copy operation. And even though the string is unlikely to be a long one, copying it every time without good reason is a bad idea - all the more so because this function is called by various callers, which, in turn, also get type from outside and have to copy it.

Digression II

Some of the classic roguelike games are still in active development. If you check the GitHub repositories of Cataclysm DDA or NetHack, you'll see that changes are submitted every day. NetHack is actually the oldest game that's still being developed: it released in July 1987, and the last version dates back to 2018.

Dwarf Fortress is one of the most popular - though younger - games of the genre. The development started in 2002 and the first version was released in 2006. Its motto "Losing is fun" reflects the fact that it's impossible to win in this game. In 2007, Dwarf Fortress was awarded "Best Roguelike Game of the Year" by voting held annually on the ASCII GAMES site.

By the way, fans might be glad to know that Dwarf Fortress is coming to Steam with enhanced 32-bit graphics added by two experienced modders. The premium-version will also get additional music tracks and Steam Workshop support. Owners of paid copies will be able to switch to the old ASCII graphics if they wish. More.

Overriding the assignment operator

Examples 4, 5:

Here's a couple of interesting warnings.

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()
  {
    ....
  }
  ....
}

This class has a copy constructor and a destructor but doesn't override the assignment operator. The problem is that an automatically generated assignment operator can assign the pointer only to JsonIn. As a result, both objects of class JsonObject would be pointing to the same JsonIn. I can't say for sure if such a situation could occur in the current version, but somebody will surely fall into this trap one day.

The next class has a similar problem.

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 danger of not overriding the assignment operator in a complex class is explained in detail in the article "The Law of The Big Two".

Examples 6, 7:

These two also deal with assignment operator overriding, but this time specific implementations of it.

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 implementation has no protection against potential self-assignment, which is unsafe practice. That is, passing a *this reference to this operator may cause a memory leak.

Here's a similar example of an improperly overridden assignment operator with a peculiar side effect:

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;
}

This code has no check against self-assignment either, and in addition, it has a vector to be filled. With this implementation of the assignment operator, assigning an object to itself will result in doubling the vector in the targets field, with some of the elements getting corrupted. However, transform is preceded by clear, which will clear the object's vector, thus leading to data loss.

Digression III

In 2008, roguelikes even got a formal definition known under the epic title "Berlin Interpretation". According to it, all such games share the following elements:

Randomly generated world, which increases replayability;
Permadeath: if your character dies, they die for good, and all of their items are lost;
Turn-based gameplay: any changes occur only along with the player's actions; the flow of time is suspended until the player performs an action;
Survival: resources are scant.

Finally, the most important feature of roguelikes is focusing mainly on exploring the world, finding new uses for items, and dungeon crawling.

It's a common situation in Cataclysm DDA for you character to end up frozen to the bone, starving, thirsty, and, to top it all off, having their two legs replaced with six tentacles.

Details that matter

Example 8:

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 ) )
    {
      ....
    }
    ....
  }
....
}

It looks like the programmer wanted to take precautions against an overflow. However, promoting the type of the sum won't make any difference because the overflow will occur before that, at the step of adding the values, and promotion will be done over a meaningless value. To avoid this, only one of the arguments should be cast to a wider type: (static_cast<size_t> (start) + larger).

Example 9:

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;
}

There's one trick for cases like this. If you end up with an unused variable and you want to suppress the compiler warning, simply write (void)world_name instead of calling methods on that variable.

Example 10:

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;
                      } )
  {
    ....
  }
  ....
}

The fact that count is compared with zero suggests that the programmer wanted to find out if activity contained at least one required element. But count has to walk through the whole container as it counts all occurrences of the element. The job could be done faster by using find, which stops once the first occurrence has been found.

Example 11:

This bug is easy to find if you know one tricky detail about the char type.

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) {
  ....
}

This is one of the errors that you won't spot easily unless you know that EOF is defined as -1. Therefore, when comparing it with a variable of type signed char, the condition evaluates to false in almost every case. The only exception is with the character whose code is 0xFF (255). When used in a comparison, it will turn to -1, thus making the condition true.

Example 12:

This small bug may become critical someday. There are good reasons, after all, that it's found on the CWE list as CWE-834. Note that the project has triggered this warning five times.

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() ) {
    ....
  }
}

As the warning says, it's not enough to check for EOF when reading from the file - you also have to check for an input failure by calling cin.fail(). Let's fix the code to make it safer:

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

The purpose of keymap_txt.clear() is to clear the error state (flag) on the stream after a read error occurs so that you could read the rest of the text. Calling keymap_txt.ignore with the parameters numeric_limits<streamsize>::max() and newline character allows you to skip the remaining part of the string.

There's a much simpler way to stop the read:

while( !keymap_txt )
{
  ....
}

When put in logic context, the stream will convert itself into a value equivalent to true until EOF is reached.

Digression IV

The most popular roguelike-related games of our time combine the elements of original roguelikes and other genres such as platformers, strategies, and so on. Such games have become known as "roguelike-like" or "roguelite". Among these are such famous titles as Don't Starve, The Binding of Isaac, FTL: Faster Than Light, Darkest Dungeon, and even Diablo.

However, the distinction between roguelike and roguelite can at times be so tiny that you can't tell for sure which category the game belongs in. Some argue that Dwarf Fortress is not a roguelike in the strict sense, while others believe Diablo is a classic roguelike game.

Conclusion

Even though the project proved to be generally high-quality, with only a few serious defects, it doesn't mean it can do without static analysis. The power of static analysis is in regular use rather than one-time checks like those that we do for popularization. When used regularly, static analyzers help you detect bugs at the earliest development stage and, therefore, make them cheaper to fix. Example calculations.

The game is still being intensely developed, with an active modder community working on it. By the way, it has been ported to multiple platforms, including iOS and Android. So, if you are interested, do give it a try!

#Cpp #GameDev