Webinar: C++ semantics - 06.11
In February 2014, the Argentinian studio OKAM made public the source code of their multi-platform game engine Godot Engine and not so long ago, version 1.0 was released. As you have already guessed, in this article we will talk about the analysis of this project's source code and its results. Analysis was done with the PVS-Studio static code analyzer. Besides the introductory purpose, this article also pursues some practical aims: the readers can learn something new while the project developers can fix errors and bottlenecks. But first things first.
Before discussing the analysis results, I'd like to tell you in brief about the object of our analysis. Godot Engine is an open-source and cross-platform game engine developed by the Argentinian studio OKAM in 2001 and used solely for the internal purposes of the studio. In 2014, Godot Engine was released under the MIT license. The engine allows creating both 2D and 3D video games. The list of supported platforms is very impressive: Windows, OS X, Linux, Android, iOS, BlackBerry 10, HTML5, flash, NaCl, PlayStation 3, PlayStation Vita, and 3DS. You can download the engine's source code from the corresponding repository at GitHub.
I'd like to note right away that only some of the warnings generated by the analyzer will be mentioned in this article. I have picked only the most interesting ones and commented briefly on each.
The article has turned out pretty large, so be patient and get yourself some coffee and biscuits. And don't forget to put on some nice background music. Enjoy reading, and let's go!
A strange subtitle, isn't it? Well, both yes and no. While it is true in everyday life, it's not that straightforward in the area of programming. Sometimes duplicated variables or subexpressions can be way more dangerous than it may seem at first sight. Why? Read on.
Let's start with a pretty common error - identical subexpressions within one expression. Such constructs usually result from copy-paste or programmer's carelessness. Note that not only this project but others as well are abundant in strange (superfluous/incorrect - underline as appropriate) comparisons.
Here's a classic example:
int ssl3_read_bytes(....)
{
....
if ((type && (type != SSL3_RT_APPLICATION_DATA)
&& (type != SSL3_RT_HANDSHAKE) && type)
|| (peek && (type != SSL3_RT_APPLICATION_DATA)))
{
....
}
....
}
PVS-Studio's diagnostic message: V501 There are identical sub-expressions 'type' to the left and to the right of the '&&' operator. s3_pkt.c 971
To make it more transparent, let's single out the fragment of the subexpression where the error is found:
(type && (....) && (....) && type)
One and the same variable 'type' is repeated twice in this expression. This code is not dangerous but the double use of the variable doesn't make any sense. If 'type' or some other subexpression is 'false', it won't even get to the last check. So the code is excessive. But it's another kind of thing if, instead of 'type', some other variable or subexpression (similar to 'type != SSL3_RT_APPLICATION_DATA' or 'type != SSL3_RT_HANDSHAKE') was meant. Then this code won't be as harmless, so never underestimate the possible danger of code like this.
There was another similar code fragment. I won't cite it, but here's the analyzer's warning for it: V501 There are identical sub-expressions 'type' to the left and to the right of the '&&' operator. d1_pkt.c 761
A similar case but with a different subexpression: V501 There are identical sub-expressions 'rs >= 4' to the left and to the right of the '&&' operator. http_client.cpp 290
The next example of a bug of this kind:
void Collada::_parse_curve_geometry(....)
{
....
String section = parser.get_node_name();
....
if (section == "source")
{
....
} else if (section=="float_array" || section=="array" ||
section=="float_array")
{
....
}
....
}
PVS-Studio's diagnostic message: V501 There are identical sub-expressions 'section == "float_array"' to the left and to the right of the '||' operator. collada.cpp 982
I guess everything is clear from the message text. The expression contains two identical checks that the 'section' variable stores the "float_array" string. The question is only if it is just an excessive comparison or the programmer really meant something else - for example (let's use our imagination) "double_array"? I can't say for sure how deep the rabbit hole is but you ought to be careful.
By the way, I encountered this bug twice. Here's the message for the second one:
The next error:
void TextEdit::_input_event(const InputEvent& p_input_event)
{
....
if (k.mod.command || k.mod.shift || k.mod.alt || k.mod.command)
break;
....
}
PVS-Studio's diagnostic message: V501 There are identical sub-expressions 'k.mod.command' to the left and to the right of the '||' operator. text_edit.cpp 1565
Again, we are dealing with two identical subexpressions within one expression. If something else was meant instead of the last subexpression, then the seemingly harmless code turns into something potentially dangerous.
Another example of strange comparisons:
int ASN1_PRINTABLE_type(const unsigned char *s, int len)
{
int c;
....
if (!( ((c >= 'a') && (c <= 'z')) ||
((c >= 'A') && (c <= 'Z')) ||
(c == ' ') ||
((c >= '0') && (c <= '9')) ||
(c == ' ') || (c == '\'') ||
(c == '(') || (c == ')') ||
(c == '+') || (c == ',') ||
(c == '-') || (c == '.') ||
(c == '/') || (c == ':') ||
(c == '=') || (c == '?')))
....
}
PVS-Studio's diagnostic message: V501 There are identical sub-expressions '(c == ' ')' to the left and to the right of the '||' operator. a_print.c 76
As you can see from the code, the '(c == ' ')' subexpression is used twice. Perhaps one of them is just excessive but another possible explanation is that the comparison operation should have been done over some other entity instead of the whitespace character.
You probably think we are out of suspicious comparisons now? No. I warned you there would plenty of them. So here's another one:
int WINAPI WinMain(....,LPSTR lpCmdLine, ....)
{
....
char* arg;
arg = lpCmdLine;
....
while (arg[0] != 0 && arg[0] == ' ')
{
arg++;
}
....
}
PVS-Studio's diagnostic message: V590 Consider inspecting the 'arg[0] != 0 && arg[0] == ' '' expression. The expression is excessive or contains a misprint. godot_win.cpp 175
As for this case, I can say for sure that it is safe. However, the expression is still excessive; the code could do with the (arg[0] == ' ') condition alone.
Figure 1. Godot has its own scripting language called GDScript, which is similar to Python language. It's a high level, dynamically typed programming language.
You must be tired of duplicated comparisons by now and willing to switch over to other things. If so, well, I've good news for you.
Now welcome to examine a mistake pretty common with newbie programmers. Professionals, though, will also make it every now and then. Take a look at the following code and a few declarations:
enum ShapeType {
SHAPE_LINE,
SHAPE_RAY,
SHAPE_SEGMENT,
SHAPE_CIRCLE,
SHAPE_RECTANGLE,
SHAPE_CAPSULE,
SHAPE_CONVEX_POLYGON,
SHAPE_CONCAVE_POLYGON,
SHAPE_CUSTOM,
};
BodyShapeData body_shape_data[6];
void _create_body_shape_data()
{
....
body_shape_data[Physics2DServer::SHAPE_CONVEX_POLYGON].image
=vs->texture_create_from_image(image);
....
}
PVS-Studio's diagnostic message: V557 Array overrun is possible. The 'Physics2DServer::SHAPE_CONVEX_POLYGON' index is pointing beyond array bound. test_physics_2d.cpp 194
It's not without reason that I've cited the declarations of the 'body_shape_data' array and 'ShapeType' enumeration as it is these lines where the bug is born. Some may have already guessed - my congratulations to you! All the rest, read on for the explanation. As you can see from the definition, the size of the 'body_shape_data' array is 6. Considering that indexes are numbered starting with 0, the last item's index is 5. Now let's check the 'ShapeType' enumeration. In enumerations, item indexing also starts with 0, so the 'SHAPE_CONVEX_POLYGON' item has index 6. The result is an array overrun.
Another bug of the same kind: V557 Array overrun is possible. The 'Physics2DServer::SHAPE_CONVEX_POLYGON' index is pointing beyond array bound. test_physics_2d.cpp 209
If you look closely into the code, you will notice that the source of the bug is found in the same enumeration and even the same item. It's no wonder, for when you don't have a slightest suspicion that some code block is incorrect, you'll be cloning it throughout the rest of the program. And after that you'll have to reap what you have sown.
The next code sample is highly suspicious. Take a look at it:
void* MemoryPoolStaticMalloc::_realloc(void *p_memory, size_t p_bytes)
{
....
if (p_bytes<=0)
{
this->free(p_memory);
ERR_FAIL_COND_V( p_bytes < 0 , NULL );
return NULL;
}
....
}
PVS-Studio's diagnostic message: V547 Expression 'p_bytes < 0' is always false. Unsigned type value is never < 0. memory_pool_static_malloc.cpp 159
The cause of the bug is the 'p_bytes' argument having the unsigned type 'size_t'. The smallest value it can take is 0. It means that the p_bytes < 0 condition will always be false. At the same time, the nearby condition p_bytes <= 0 will be true in only one case - when p_bytes==0. Put simply, this code probably contains a bug.
A similar example.
_FORCE_INLINE_ static float _rand_from_seed(uint32_t *seed)
{
....
uint32_t s = (*seed);
....
if (s < 0)
s += 2147483647;
....
}
PVS-Studio's diagnostic message: V547 Expression 's < 0' is always false. Unsigned type value is never < 0. particles_2d.cpp 230
The 's' variable is unsigned, therefore, it can never take a negative value. The (s < 0) condition will always be false and the 's' variable will fail to increment by 2147483647.
There was also the following code fragment:
Variant Tween::_run_equation(InterpolateData& p_data)
{
....
Variant result;
....
switch(initial_val.get_type())
{
case Variant::BOOL:
result = ((int) _run_equation(....)) >= 0.5;
break;
....
}
....
}
PVS-Studio's diagnostic message: V674 The '0.5' literal of the 'double' type is compared to a value of the 'int' type. tween.cpp 272
This is what the declaration of the '_run_equation' function looks like:
real_t _run_equation(...);
So, the function has returned a value expressed by a floating-point type. This value is explicitly cast to the integer type 'int', after which it is suddenly compared to the constant 0.5. Something is not right here.
A possible explanation is that parentheses were put incorrectly and the correct version of this code should be as follows:
result = (int)(_run_equation(....) >= 0.5);
Figure 2. Godot has a sophisticated animation system.
Finding a typo is not always easy. Especially when code is syntactically flawless and doesn't trigger compiler warnings. On the other hand, such code lacks logic. Take a look at the following code fragment:
Array PhysicsDirectSpaceState::_cast_motion(....)
{
....
Array ret(true);
ret.resize(2);
ret[0]=closest_safe;
ret[0]=closest_unsafe;
return ret;
}
PVS-Studio's diagnostic message: V519 The 'ret[0]' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 305, 306. physics_server.cpp 306
It would not be easy to notice the trap among so many code lines as it originally was in this code. But we have abridged the function to make the mistake clearly visible. One and the same array item is assigned different values twice on end. There's not much sense in that, of course. But note that the array is incremented up to 2 before that, so the typo is very prominent: one of the indexes should be 1.
I found one more similar error in the code. This is the corresponding PVS-Studio's diagnostic message: V519 The 'ret[0]' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 287, 288. physics_2d_server.cpp 288
Now let's check an example dealing with copy-paste:
void ScrollBar::_input_event(InputEvent p_event)
{
....
if (b.button_index==5 && b.pressed)
{
if (orientation==VERTICAL)
set_val( get_val() + get_page() / 4.0 );
else
set_val( get_val() + get_page() / 4.0 );
accept_event();
}
if (b.button_index==4 && b.pressed)
{
if (orientation==HORIZONTAL)
set_val( get_val() - get_page() / 4.0 );
else
set_val( get_val() - get_page() / 4.0 );
accept_event();
}
....
}
PVS-Studio's diagnostic messages:
It's an interesting case indeed. Both branches of the 'if' operator have identical bodies, and this code block is repeated twice on end. I can't say for sure what the programmer really intended to do here. Maybe there must be the '-' character instead of '+' in one of the branches, or maybe not. Personally I, being totally unfamiliar with this code, find it hard to figure out. But the code's authors will certainly get the idea right away about what the analyzer doesn't like and how to fix it.
Here's another interesting type of typos causing infinite loops:
Dictionary ScenePreloader::_get_bundled_scene() const
{
....
Vector<int> rconns;
....
for(int i=0;i<connections.size();i++)
{
....
for(int j=0;j<cd.binds.size();i++)
rconns.push_back(cd.binds[j]);
}
....
}
PVS-Studio's diagnostic message: V533 It is likely that a wrong variable is being incremented inside the 'for' operator. Consider reviewing 'i'. scene_preloader.cpp 410
This typo is unfortunately far from harmless and will sooner or later cause heap exhaustion. As you can see from the code, the 'i' variable is incremented in the second loop, though it is the 'j' variable that is used in the loop termination condition and should be incremented instead. As a result, we get an infinitely iterating loop. Due to the fact that items are added to the 'rconns' vector in the loop body, this process may take quite a while but end badly anyway.
One should be as careful as possible when handling pointers, otherwise you may end up with a big mess. The next example is not as critical as the previous one but still it is pretty suspicious. I found several cases when pointers were used in the following way:
static const TRexChar *trex_matchnode(...., const TRexChar *str, ....)
{
....
case OP_DOT:
{
*str++;
}
return str;
....
}
PVS-Studio's diagnostic message: V532 Consider inspecting the statement of '*pointer++' pattern. Probably meant: '(*pointer)++'. trex.c 506
I found 4 more instances of code like that in the same file. Also, similar code was many times detected in other projects as well, which indicates that this bug pattern is very common.
The point is that in such code, a pointer is dereferenced and then incremented. At the same time, the value obtained after dereferencing is not used in any way. Then the question is: why did the programmer execute 2 operations at once? If they needed to increment the pointer's value, then they should have omitted the dereferencing operation, and if they needed to change the value, they should have put parentheses. Most likely, it was the former and the asterisk was just added by mistake. Perhaps it's not an error at all, but the code still ought to be checked and fixed.
Going on with pointers. The next "dish" is sort of "delicacy" - null pointer dereferencing. Less talk, more code:
Node* MeshInstance::create_trimesh_collision_node()
{
if (mesh.is_null())
return NULL;
Ref<Shape> shape = mesh->create_trimesh_shape();
if (shape.is_null())
return NULL;
StaticBody * static_body = memnew( StaticBody );
static_body->add_shape( shape );
return static_body;
return NULL;
}
void MeshInstance::create_trimesh_collision()
{
StaticBody* static_body =
create_trimesh_collision_node()->cast_to<StaticBody>();
ERR_FAIL_COND(!static_body);
static_body->set_name( String(get_name()) + "_col" );
....
}
PVS-Studio's diagnostic message: V522 Dereferencing of the null pointer 'create_trimesh_collision_node()' might take place. mesh_instance.cpp 177
Before passing on to the diagnostic message, note one interesting thing in the body of the 'create_trimesh_collision_node' method - particularly the last line that will never be executed. I wonder what for was it written? Anyway, it looks interesting.
But going back to the bug, as you can see from the code fragment above, the 'create_trimesh_collision_node' method can sometimes return a null pointer and attempting to dereference it with the -> operator will cause undefined behavior.
Another similar error: V522 Dereferencing of the null pointer 'create_convex_collision_node()' might take place. mesh_instance.cpp 211
Figure 3. Godot supports deployment to multiple platforms. Within a project, developers have control over delivery to mobiles, web, desktops, and consoles.
Since we started talking about undefined behavior, let's discuss a few more examples from this category:
void AnimationKeyEditor::_track_editor_input_event(....)
{
....
if (v_scroll->is_visible() && p_input.is_action("ui_page_up"))
selected_track=selected_track--;;
....
}
PVS-Studio's diagnostic message: V567 Undefined behavior. The 'selected_track' variable is modified while being used twice between sequence points. animation_editor.cpp 1378
Don't mind the excessive semicolon: it's probably just a typo without any serious implications. What's of more interest to us is the expression to the left, with the operations of postfix decrement and assignment. A construct like this will cause undefined behavior. Why didn't the programmer leave just the decrement operation?
selected_track--;
Another example from the same category:
static real_t out(real_t t, real_t b, real_t c, real_t d)
{
return c * ((t = t / d - 1) * t * t + 1) + b;
}
PVS-Studio's diagnostic message: V567 Undefined behavior. The 't' variable is modified while being used twice between sequence points. tween_interpolaters.cpp 265
This code could be split into 2 lines, making it simpler and easier to understand and also getting rid of undefined behavior. The programmer just should have written the following expression separately:
t = t / d - 1;
But in its original version, it executes as a subexpression. So it turns out that there are the (t = t / d - 1) and (t) subexpressions to the left and to the right of the multiplication operator. It's unknown which of the two will be evaluated first but the order does affect the result. To learn more about undefined behavior, sequence points, and other related issues, see the description of diagnostic V567.
Here are two more warnings pointing out code fragments with similar bugs:
I find that set expressions like this serve very well as subtitles in articles - even those dealing with programming and programmer mistakes. Why? Because you really need to re-review your code several times lest you miss something or, say, declare excessive variables. Let's start.
Here's the first example - declaring variables that won't be used anywhere. Even if it doesn't have serious consequences, such code is simply meaningless. But the pit may appear deeper than you think if you intended to work with variables with a broader scope while it is actually freshly declared ones that are used instead.
Take a look at this fragment:
void EditorExportPlatformAndroid::_fix_manifest(....)
{
....
uint32_t string_count;
uint32_t styles_count;
uint32_t string_flags;
uint32_t string_data_offset;
....
switch(chunk)
{
case CHUNK_STRINGS:
{
int iofs=ofs+8;
uint32_t string_count=decode_uint32(&p_manifest[iofs]);
uint32_t styles_count=decode_uint32(&p_manifest[iofs+4]);
uint32_t string_flags=decode_uint32(&p_manifest[iofs+8]);
uint32_t string_data_offset=decode_uint32(&p_manifest[iofs+12]);
uint32_t styles_offset=decode_uint32(&p_manifest[iofs+16]);
....
}
....
}
....
}
PVS-Studio's diagnostic message: V561 It's probably better to assign value to 'styles_count' variable than to declare it anew. Previous declaration: export.cpp, line 610. export.cpp 633
As you can see, in the body of the 'switch' operator (or, to be more exact, in one of its branches), some variables are declared that have the same types and names as those in the external scope. At the same time, it is the former which are handled further on, while the external ones are not used anywhere. Errors like this can sometimes lead to very sad issues because there is a risk of handling a different variable than intended. Such errors are sometimes pretty difficult to find and fix, especially in a large-scope project.
One more similar yet not as harmful case. There won't be any critical consequences here but only until the code gets modified. Once it is done, the veiled bug will pop up and it'll be a tough job trying to catch it after that...
ShaderLanguage::Node* ShaderLanguage::validate_function_call(....)
{
....
bool all_const=true;
for(int i=1;i<p_func->arguments.size();i++)
{
if (p_func->arguments[i]->type!=Node::TYPE_CONSTANT)
all_const=false;
args.push_back(compute_node_type(p_func->arguments[i]));
}
....
if (p_func->op==OP_CONSTRUCT && all_const)
{
bool all_const=false;
....
}
....
}
PVS-Studio's diagnostic message: V561 It's probably better to assign value to 'all_const' variable than to declare it anew. Previous declaration: shader_language.cpp, line 1225. shader_language.cpp 1274
As I already said, this case is similar to the previous one. Two variables are declared, having the same names and types but different scopes. The first variable is used within the method but the second is not used at all (the code is pretty large, so I haven't included it, but please take my word for it). Since this variable is declared inside the 'if' operator, its scope will be the code fragment between its declaration and the end of the 'if' block. And this is where the danger is lurking. Sure, there's nothing dangerous about the code in its current form: it's just that an excessive variable is declared and not used in any way in its scope and then gets successfully deleted - doesn't look neat, but it's nothing to worry at. But once you have modified the code, adding some code using this variable, you'll immediately get into troubles if you meant to work with the variable of a broader scope. The conclusion is: You should avoid cases like this even if they look harmless at first glance.
Another case is when undefined values are returned from functions or methods. For a start, take a look at the following code:
const char* CPPlayer::get_voice_sample_name(int p_voice)
{
const char *name;
if (!voice[p_voice].sample_ptr)
name=voice[p_voice].sample_ptr->get_name();
return name;
}
PVS-Studio's diagnostic message: V614 Potentially uninitialized pointer 'name' used. cp_player_data_control.cpp 244
In some cases, 'name' will contain meaningless values. The 'if' operator lacks 'else', so the programmer should add 'else' and assign 'NULL' or something else to 'name'.
There was another error of this kind: V614 Potentially uninitialized pointer 'name' used. cp_player_data_control.cpp 313
Going on with our overview. Check the following fragment:
void Generic6DOFJointSW::set_param(....)
{
ERR_FAIL_INDEX(p_axis,3);
switch(p_param)
{
case PhysicsServer::G6DOF_JOINT_LINEAR_LOWER_LIMIT:
{
m_linearLimits.m_lowerLimit[p_axis]=p_value;
} break;
case PhysicsServer::G6DOF_JOINT_LINEAR_UPPER_LIMIT:
{
m_linearLimits.m_upperLimit[p_axis]=p_value;
} break;
....
case PhysicsServer::G6DOF_JOINT_ANGULAR_LIMIT_SOFTNESS:
{
m_angularLimits[p_axis].m_limitSoftness; <<<<====
} break;
case PhysicsServer::G6DOF_JOINT_ANGULAR_DAMPING:
{
m_angularLimits[p_axis].m_damping=p_value;
} break;
....
}
}
PVS-Studio's diagnostic message: V607 Ownerless expression 'm_angularLimits[p_axis].m_limitSoftness'. generic_6dof_joint_sw.cpp 539
There is obviously a missing assignment operation in the 'case' branch pointed out by the analyzer. It's the only branch in the body of this 'switch' operator where assignment isn't executed. I guess the correct code should look like in the previous case:
m_angularLimits[p_axis].m_limitSoftness=p_value;
Another example with a similar error:
Variant Variant::get(const Variant& p_index, bool *r_valid) const
{
....
if (ie.type == InputEvent::ACTION)
{
if (str =="action")
{
valid=true;
return ie.action.action;
}
else if (str == "pressed")
{
valid=true;
ie.action.pressed;
}
}
....
}
PVS-Studio's diagnostic message: V607 Ownerless expression 'ie.action.pressed'. variant_op.cpp 2410
In this method, a certain value is returned, depending on the value of the 'str' variable. But as you can see from this code, there is the missing 'return' operator in one of the conditional branches, which results in the 'ie.action.pressed' value failing to be returned from the method.
Another example - this time, it is an incorrect use of a function:
void EditorSampleImportPlugin::_compress_ima_adpcm(....)
{
....
if (xm_sample==32767 || xm_sample==-32768)
printf("clippy!\n",xm_sample);
....
}
PVS-Studio's diagnostic message: V576 Incorrect format. A different number of actual arguments is expected while calling 'printf' function. Expected: 1. Present: 2. editor_sample_import_plugin.cpp 705
No special comments are needed here. As the message text reads, the reason is in the 'printf' function, or to be more exact, in the incorrect format string. As a result, printing of the 'xm_sample' variable will fail.
Figure 4. The graphics engine uses OpenGL ES 2 for all supported platforms, and an upgrade to OpenGL ES 3.0 is in the roadmap.
If you have read until this place - I do mean "read", not just "scanned through" - my congratulations and respect for being patient! It has turned out pretty voluminous even considering that I cited only some part of all the errors found. I hope you have learned something new and will be more careful from now on when working with code fragments like the ones shown above.
Besides the code samples and comments discussed here, I wanted to communicate to you one more idea - particularly how important it is to use static code analyzers in large-scope projects. One way or another, bottlenecks or errors are always present in code but they may be so trickily disguised that you may have a hard time trying to figure them out - the later, the harder. So the sooner you manage to catch and fix a bug, the cheaper it is to fix it. Integrating tools like the PVS-Studio static analyzer I've used for writing this article simplifies the development process by advancing the detection and fixing of errors and bottlenecks in projects, which helps increase the overall product quality.
0