Reordering test conditions in for-loop: compiler error?

Question

I have a tree stored in an array, and I'm trying to find a specific node:

std::vector<Node> nodes = ... const unsigned short sentinel = -1; unsigned short index = 0; for (Node* node = &nodes[index]; // root node index != sentinel; node = &nodes[index]) { if (foo(*node)) { index = node->left; } else { index = node->right; } } 

Nothing special, in other words. However, MSVC 2012 does not work with an attempt to access nodes[sentinel] , which is out of range. Turns out he first computes &nodes[index] , then checks index . (Debug mode, without optimization).

For me, it looks like a code generation error, but I have not seen such errors, at least for a decade. This is a simple non-optimized code. Of course, even with permutation, node is not actually used until index tested, and on x86 it is not very dangerous to have such a pointer outside the limits, but MSVC vector<> rightly claims that it is an illegal index.

Made a clean assembly and checked the assembly again; he repeats. The tree is also not empty, there is always a root node.

Am I forgetting something or is this really a serious compiler error?

Answer 1

Your code rewritten in a while loop looks like

 Node* node = &nodes[index]; // root node while(index != sentinel) { { if (foo(*node)) { index = node->left; } else { index = node->right; } } node = &nodes[index]; } 

The last line may be access to nodes [-1].

I rewrote your loop in

 unsigned short index = 0; do { Node* node = &nodes[index]; if (foo(*node)) { index = node->left; } else { index = node->right; } } while(index != sentinel); 

Answer 2

If you have a loop like this:

 for (init; cond; step) { body; } 

Then this is the order of execution of the expressions / statements:

• Init
• cond; stop on false otherwise
• Body
• step
• cond; stop on false otherwise
• Body
• step
• ...

In other words, it is a synonym for this:

 { init; while (cond) { body; step; } } 

In your case, it may happen that the body sets the index to sentinel . Then you expect cond to execute and break the loop, but notice that after each execution of the body, the step is executed before cond. This means that node = &nodes[index] will indeed be executed with the new index value, which is equal to sentinel . Therefore, VS produces what it should.

Your loop seems completely different from the traditional for loop; I think it would be more appropriate to turn it into an explicit while . If I were to review the code for your code, I would definitely ask for it.

Answer 3

"select" Not broken .; -)

See how the loop executes.

• Initializing Node* node = &nodes[index]

• Check index != sentinel . Exit?

• Body loop. This changes the index !

• node = &nodes[index]

• Return to 2.

When after step 3 index == -1 you get access to out of range in step 4.

Answer 4

In the expression for (init; check; step) { body } order goes: init , check , and then it continues to repeat the cycle body , step , check , so step occurs before checking.

However, your loop here is weird because you don't need node participate outside the body!

You can easily rewrite it:

 const unsigned short sentinel = -1; std::vector<Node> nodes = ... for (unsigned short index = 0; // root node index != sentinel; ) { Node& node = nodes[index]; if (foo(node)) { index = node.left; } else { index = node.right; } } 

which is not only shorter, but also has a stiffer value for variables :)

Answer 5

There may be a mistake (if the author did not want this behavior) with a sentinel: unsigned short cannot be -1; It should be short ... or something signed