Cataclysm Dark Days Ahead, static analysis and bagels

Most likely, from the title of the article you have already guessed that the focus of the error in the source code. But this is not the only thing that will be discussed in this article. If besides C ++ and errors in someone else's code you are attracted to unusual games and you are interested to find out what these bagels are and what they eat with, welcome to the cat!

In my search for unusual games, I stumbled upon the game Cataclysm Dark Days Ahead, which is different from other unusual graphics: it is implemented using the multi-colored ASCII characters on a black background.

What is striking in this game and others like it is how much is implemented in them. Specifically, in Cataclysm, for example, even for character creation, I want to look for guides, since there are dozens of different parameters, features and initial plots, not to mention variations of events in the game itself.

This is an open source game, and is also written in C ++. So it was impossible to pass by and not drive this project through the PVS-Studio static analyzer, in the development of which I now take an active part. The project itself was surprised by the high quality of the code, however, there are still some flaws in it and I will discuss a few of them in this article.
')
To date, quite a lot of games have already been tested using PVS-Studio. For example, you can read our other article, Static Analysis in the Video Game Industry: Top 10 Software Errors .

Logics

Example 1:

The following example is a typical copy error.

V501 There are identical to the left and 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 ) ) { .... } .... } 

Here the same condition is checked twice. Most likely, the expression was copied and forgotten to change something in it. I find it difficult to say whether this error is significant, but the check does not work as intended.

Similar warning:

• 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

Example 2:

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

There are no errors in the condition, but it is unnecessarily complicated. It would be worth taking pity on those who will have to deal with this condition, and it is simpler to write if (left_fav == right_fav) .

Similar warning:

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

Retreat i

For me, it turned out to be a discovery that the games that today are called “bagels” are only fairly light followers of the old genre of roguelike games. It all began with the cult game Rogue in 1980, which became a role model and inspired many students and programmers to create their own games. I think a lot has also been introduced by the community of the board role-playing game DnD and its variations.

Micro-optimizations

Example 3:

The next group of analyzer warnings indicates not the error, but the possibility of micro-optimization of the program code.

V801 Decreased performance. It is better to redefine the second function. 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; } 

Here, std :: string is hidden behind itype_id . Since the argument is still passed to the constant, which will not allow it to be changed, it would be faster to simply pass the variable reference to the function and not waste resources on copying. And although, most likely, the line there will be very small, but continuous copying for no apparent reason is unnecessary. Moreover, this function is called from different places, many of which, in turn, also receive a type from the outside and copy it.

Similar warnings:

• V801 Decreased performance. It is better to redefine. Consider replacing 'const ... evt_filter' with 'const ... & evt_filter'. input.cpp 691
• V801 Decreased performance. It is better to redefine it. Consider replacing 'const ... color' with 'const ... & color'. output.h 207
• In total, the analyzer issued 32 such warnings.

Example 4:

V813 Decreased performance. The 'str' argument shouldn’t have to 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, '\0' ); .... 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; } 

In this case, though the argument is not constant, it does not change in the body of the function. Therefore, for optimization, it would be good to pass it via a constant link, and not to force the compiler to create local copies.

This warning was also not a single one, there were 26 such cases.


Similar warnings:

• V813 Decreased performance. The 'message' argument shouldn’t necessarily be a reference. json.cpp 1452
• V813 Decreased performance. The 's' argument should not necessarily be a reference. catacharset.cpp 218
• And so on...

Retreat II

Some of the classic roguelike games are still being actively developed. If you go to the GitHub Cataclysm DDA or NetHack repositories, you can see that changes are being actively made every day. NetHack is generally the oldest game that is still being developed: its release took place in July 1987, and the latest version dates back to 2018.

One of the more famous games of this genre, however, is Dwarf Fortress, which has been developed since 2002 and first released in 2006. "Losing is fun" ("Play fun") - the motto of the game, exactly reflecting its essence, since it is impossible to win in it. This game in 2007 earned the title of the best roguelike game of the year as a result of a vote that is held annually on the ASCII GAMES website.


By the way, those who are interested in this game may be interested in the next news. Dwarf Fortress will be released on Steam with improved 32-bit graphics. With the updated picture, on which two experienced moderators of the game are working, the premium version of Dwarf Fortress will receive additional music tracks and Steam Workshop support. But if that, owners of the paid version of Dwarf Fortress will be able to change the updated graphics to the previous form in ASCII. More details .

Reassignment of the assignment operator

Examples 5, 6:

Also found an interesting pair of similar 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 destructor, however, there is no overloading of the assignment operator for it. The problem here is that the automatically generated assignment statement can only assign a pointer to JsonIn . As a result, both objects of the JsonObject class point to the same JsonIn . It is not known whether such a situation can arise somewhere now, but in any case, this is a rake, which sooner or later someone will step on.

A similar problem is present in the next class.

V690 The 'JsonArray' class implements a copy constructor, but there isn’t 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() { .... } } 

For more information about the danger of the lack of overloading of an assignment operator for a complex class, see the article " The Law of The Big Two " (or in the translation of this article " C ++: The Law of the Big Two ").

Examples 7, 8:

Another example related to the overloaded assignment operator, but this time is about its concrete implementation.

V794 The assignment operator should not 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; } 

The problem is that this implementation is not protected from assigning the object to itself, which is unsafe practice. That is, if the operator is given a link to * this , a memory leak may occur.

A similar example of mistakenly overloading an assignment operator with an interesting side effect:

V794 The assignment operator should not 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; } 

In this case, there is also no check for assigning an object to itself. But in addition the vector is filled. If you try to assign an object to yourself by such an overload, then in the targets field you will get a doubled vector, some of whose elements are corrupted. However, there is clear before the transform , which will clear the object's vector and data will be lost.

Retreat III

In 2008, the bagels even acquired a formal definition, which received the epic title “Berlin Interpretation”. According to this definition, the main features of such games are:

• Randomly generated world, which increases replayability;
• Permadeath: if your character dies - he dies forever and all items are lost;
• Stepwise: changes occur only with the player's action, until the action is made - time stops;
• Survival: resources are extremely limited.

And the most important thing: bagels are aimed primarily at exploring and discovering the world, searching for new ways of using objects and passing dungeons.

The usual situation in Cataclysm DDA is: you are cold and hungry to death, you are thirsty, and indeed you have six tentacles instead of your legs.

Important details

Example 9:

V1028 Possible overflow. Consider casting operands of the 'start + larger' 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 seems that the programmer wanted to avoid overflow. But bringing the result of addition in such a case is meaningless, since overflow will arise as soon as numbers are added, and the extension of types will be made over the meaningless result. In order to avoid this situation, it is necessary to bring only one of the arguments to a larger type: (static_cast <size_t> (start) + larger) .

Example 10:

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

For such cases, there is a little trick. If the variable is unused, instead of trying to call any method, you can simply write (void) world_name to suppress the compiler warning.

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

Judging by the fact that the result of count is compared with zero, the idea is to understand whether there is at least one required element among the activity . But count is forced to go through the entire container, since it counts all occurrences of the element. In this situation, it will be faster to use find , which stops after the first match found.

Example 12:

The following error is easily detected if you know about one subtlety.

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 those errors that can be difficult to notice if you don’t know that EOF is defined as -1. Accordingly, if you try to compare it with a signed char type variable, the condition is almost always false . The only exception is if the character code is 0xFF (255). When comparing such a symbol will turn into -1 and the condition will be true.

Example 13:

The next small mistake may one day become critical. No wonder it is in the CWE list as CWE-834 . And by the way, there were five of them.

V663 Infinite loop is possible. The 'cin.eof ()' condition is not a loop 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 stated in the warning, checking for the end of the file when reading is not enough, you must also check for read error cin.fail () . Change the code for a safer reading:

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

keymap_txt.clear () is needed so that when an error is read from the file, the state (flag) of the error is removed from the stream, otherwise the text will not be readable anymore . keymap_txt.ignore with numeric_limits <streamsize> :: max () parameters and a control newline character allows you to skip the rest of the line.

There is a much easier way to stop reading:

 while( !keymap_txt ) { .... } 

If you use a stream in the context of logic, it converts itself to a value equivalent to true until it reaches EOF .

Retreat IV

Now the most popular are games that combine the signs of roguelike games and other genres: platformers, strategies, etc. Such games began to be called roguelike-like or roguelite. Such games include such famous titles as Don't Starve, The Binding of Isaac, FTL: Faster Than Light, Darkest Dungeon and even Diablo.

Although at times the difference between roguelike and roguelite is so small that it is not clear what genre the game belongs to. Someone thinks that Dwarf Fortress is no longer a roguelike, but for someone, and Diablo is a classic bagel.

Conclusion

Although the project as a whole is an example of high-quality code, and it was not possible to find many serious errors, this does not mean that the use of static analysis is redundant for it. The point is not in one-time checks, which we are doing to popularize the methodology of static code analysis, but in regular use of the analyzer. Then many errors can be identified at an early stage and, therefore, reduce the cost of correcting them. An example of calculations.


Over the considered game and is now under active work, and there is an active community of modders. And it is ported to many platforms, including iOS and Android. So, if you are interested in this game, I recommend to try it!