Back to Programming techniques
In this section we will define the iterator debugging problem, and show that it has no solutions.
Suppose the following class hierachy:
class Node { /*...*/ };
class End_Node : public Node { /*...*/ };
class Data_Node : public Node { /*...*/ };
A doubly-linked list has two types of nodes, the End_Node, and the Data_Node, with a common base-type Node. The End_Node is used as a sentinel node, and contains optional user-defined end-data. The Data_Node is used for an actual element of the list, and contains optional user-defined data. The base-class Node contains the links.
Which type of a node pointer should a list’s iterator contain? The Node* surely works, but then it is not possible to directly examine the possible user-data in a node through the debugger. A better choice seems to be Data_Node*, although it would still not be possible to examine the end-data.
The iterator debugging problem is the following: is it possible to portably refer to the fields of Node through Data_Node*, when the underlying object is actually of type End_Node?
We will begin with a concrete program, testing two casting strategies; one with reinterpret_cast, and one with two static_casts. These casting strategies cover all the possibilities. The dynamic_cast would fail, because it would detect that the casted object is not of the target type, the C-style cast would reduce to a reinterpret_cast, and const_cast would not be applicable here.
#include <iostream>
class Node
{
public:
int i = 0;
int j = 1;
};
class End_Node : public Node
{
public:
virtual void f() {}
};
class Data_Node : public Node {};
int main()
{
End_Node* end = new End_Node;
{
// Casting strategy 1: double static-casts
Data_Node* data = static_cast<Data_Node*>(static_cast<Node*>(end));
std::cout << data->i << " " << data->j << std::endl;
}
{
// Casting strategy 2: a reinterpret cast
Data_Node* data = reinterpret_cast<Data_Node*>(end);
std::cout << data->i << " " << data->j << std::endl;
}
delete end;
return 0;
}
The output of this program is similar on both Visual Studio 2013, gcc, and clang:
0 1
15785072 0
While the static_casts work as expected, the reinterpret_cast does not work. The reason is that, due to the virtual f in End_Node, these compilers place the virtual table pointer at the start of the End_Node. The data->i then refers to the virtual table pointer, rather than to Node::i. In general, the memory layout of objects is implementation defined. The above behavior is defined in the Itanium ABI (2.4 Non-POD class types), adopted by gcc and clang.
On the other hand, the claim holds for the Itanium ABI, and possibly for Visual Studio, when polymorphic behavior is not present. However, without a guarantee from the C++ Standard, this is not portable. Therefore the reinterpret_cast does not work here.
The above program provides hope that the double static cast could work. However, the C++ Standard states the following (5.2.9 Static cast 11):
A prvalue of type "pointer to cv1 B," where B is a class type,
can be converted to a prvalue of type "pointer to cv2 D," where
D is a class derived (Clause 10) from B, if a valid standard
conversion from "pointer to D" to "pointer to B" exists (4.10),
cv2 is the same cv-qualification as, or greater cv-qualification
than, cv1, and B is neither a virtual base class of D nor a base
class of a virtual base class of D. The null pointer value (4.10)
is converted to the null pointer value of the destination type.
If the prvalue of type "pointer to cv1 B" points to a B that is
actually a subobject of an object of type D, the resulting pointer
points to the enclosing object of type D. Otherwise, the behavior
is undefined.
The last two sentences are the relevant ones. Since in our double static cast the pointer does not actually point to Data_Node, the behavior is undefined. Intuitively, it seems almost sure that the compilers do the right thing here, and that the double static casting works. However, without a guarantee from the C++ Standard, this is not portable. Therefore the double static cast does not work either.
It is not possible to portably refer to the fields of Node through Data_Node*, when the underlying type is actually End_Node.
This has consequences for the debugging of the data-structures implemented in Pastel. All of the node-based data-structures, such as the doubly-linked list, the red-black tree, and the skip-list, are subject to the iterator debugging problem, because of their ability to associate user-data in the sentinel nodes. Because of the above result, an iterator must refer to lowest base-class Node, which cannot be directly used to inspect the node’s user-data in the debugger. The capability of associating user-data in the sentinel nodes is fundamental for building some more advanced data-structures on top of the existing ones, and so cannot be taken away. It follows that the node user-data has to be inspected by ways other than the debugger (e.g. printing it to the screen).