Conversations: Roots

Copyright ©, Jim Hyslop and Herb Sutter

The obelisk was larger than it had seemed over video.

I stood at the lip of a man-made escarpment, at the edge of the excavation into a surface of slightly brownish-tinted ice. The side of the obelisk facing me appeared to be pure crystal, with a kind of sheen on the surface; it rose upward to its tapered peak about a dozen meters above my head, as though a pointer to where, still further above, the light gray inner surface of the dome covered us and enclosed the entire area.

There was the distant hum of heating units, but despite my clothes I felt cold. Our breath lingered quietly in the air before us. The temperature was bearable, but still kept well below freezing; it would not be good for the ice to melt.

Below me, widening slightly as it went, the obelisk plunged another two dozen meters to where it connected to the top, only partly excavated and visible, of a wider structure which I knew to be the roof of a building still nearly completely embedded in the ice. With only the roof visible below me, the building's size was impossible to judge visually, but I knew from soundings that it went deep indeed, probably to the surface under the ice.

"The entrance is down on the far side," my escort said. "Buster?" My thoughts returned to the present, and I nodded, giving her a brief smile. We made our way down to the floor of the excavated area and walked around parked machinery and people at work in twos and threes.

The entrance at the base of the obelisk was the only thing that was man-made. Its rough edges where until recently a wall had been were clearly not part of the ancient building's original design.

The entrance way was somewhat dark, but temporary lighting had been installed not far beyond. I must have hesitated, because my escort's hand found and squeezed my arm reassuringly. "Well," I smiled back to Jeannine, "I did always want to get to the base of things."

"Yes. Ah, here's our controller."

"I'll see you at lunch, then," I said to Anna, my new girlfriend, and hung up the phone. We had been going out long enough that I was comfortable with the fact that she was the Guru's daughter — something I hadn't known when we'd started dating.

"Hey, Junior!" Bob's voice interrupted my pleasant musings. "I thought I told you not to break the build."

Turning, I said in my best patient voice: "Bob, as you'll recall, the last time I 'broke the build' it was because of some... shall we say, less than ideal code in your module." Yep, sipping away at his latte as usual.

"Yeah, well it's your problem this time, Junior." Slurp. "My code keeps crashing because of the changes you made."

I sighed, not wanting to argue with him. "OK, Bob, just tell me where the problem is, and I'll look into it."

"That's more like it," Bob smiled unpleasantly. "Just remember who's got more experience around here, kid. Don't think that sucking up to Her Weirdness is gonna help, either — her authority around me is quite limited." He wrote down the name of the file that was causing him problems and left. I resigned myself to the inevitable and checked out the module.

An hour later, I was still struggling with it. "Oh, man, this is too weird for me," I complained to no one in particular. It did appear to be a problem with my code — Bob's code worked fine for the original class, but not with the revisions I had made.

The class hierarchy was fairly simple at this point:

class parent
{
public:
  virtual void f();
// etc...
};

class child : public virtual parent
{
public:
  void f();
};

One of my modifications was to make child inherit virtually from parent, for use elsewhere in the hierarchy.

I had tried my best, but it was looking like I had no choice — I was going to have to dig into Bob's code. "Once more unto the breach, dear friends," I muttered as I set a breakpoint and prepared to step into the function. After half an hour in the crucible of debugging, I had burned away the excess and had found the root of the problem:

void parentPtrPtr(parent **b)
{
  (*b)->f();
}

void childPtrPtr(child **d)
{
  parentPtrPtr(reinterpret_cast<parent **>(d));
}

I had my suspicions about the last function. I had learned to be wary of casting, especially reinterpret_cast. I removed the reinterpret_cast, and sure enough the compiler balked at that line, complaining that parent ** and child ** were unrelated types.

"Your suspicions are correct, my apprentice." For once, the Guru's soft voice behind me did not startle me. Well, not much. "A pointer-to-pointer-to-child," she continued, "cannot be implicitly converted to a pointer-to-pointer-to-base."

I kicked back and stretched. "I thought so. Looks like Bob was doing whatever it took to shut the compiler up. I don't understand why it worked for the original class, though, and crashes now. Heck, I don't even understand why the compiler can't do the implicit conversion."

"The crash you are experiencing is the very reason for the prohibition," the Guru brushed a lock of silvering hair behind her ear. "Your derived class inherits virtually from the base class." My deer-in-the-headlights stare quickly let her know that I didn't understand. "Consider a case of simple inheritance," she said, picked up a marker, and began writing on my whiteboard:

class parent { /* whatever, including at least one virtual function */ };
class child : public parent { /* whatever */ };</b></p>

"In a typical implementation of virtual functions," she continued, "the compiler will lay out the class in memory with the pointer to the virtual function table (the vptr) first, followed by the parent class data, followed by the child class data:"

"Wait a second," I interrupted. "Aren't you always telling me that the virtual function table is not required by the Standard, and therefore it's an implementation detail?"

"That is true, my child. The Holy Standard does not require virtual function tables — indeed, it does not even mention them. However, one of the goals of the blessed members of the standards committee was to codify practices of existing compilers. Allowing an implicit conversion from child ** to parent ** would cause problems on many existing compilers — in particular, the ones that behave as I am about to describe. If I might be allowed to continue, that is." She fixed me with a stern glare. I subsided.

"This layout means that the address pointed to by this can be the same for both the base class and the derived class. With our hypothetical compiler, this always points to the vptr. Member functions of the derived class can determine the address of member data by simply taking this and adding an offset that consists of the size of the base class data and the size of the vptr.

"The situation becomes more complicated, however, when you add virtual inheritance into the mix. Consider:"

class parent { /* whatever */ };
class child1 : public virtual parent { /* whatever */ };
class child2 : public virtual parent { /* whatever */ };
class multi : public child1, public child2 { /* whatever */ };

"Clearly, the compiler cannot lay out the intermediate classes child1 and child2 in the same manner as it did class child, above, with the parent class data immediately followed by the child class data, because the virtual inheritance specifies that only one copy of the base class data should appear. The solution — or rather, a solution — is to put a vptr at the beginning of each subobject, like this:"

"Then, as the compiler invokes various member functions, it can dynamically adjust the implicit this parameter so that member functions can access the member data properly."

"Oh, I get you," I said. "When you have a multi object, a pointer to it will have slightly different values depending on whether it's pointing to a parent subobject or a child1 subobject. Say, that also explains why the intermediate class has to use the virtual keyword — I always thought it was a mistake, and that multi should be the class to use virtual. So, anyway, back to the problem at hand. This means that... um... No, I don't get you. How does this apply to pointers-to-pointers?"

"Let us," she intoned, "assign arbitrary memory addresses to these values and assume that each class contains exactly one integer, that the size of an integer and the size of a pointer are each four bytes, and that there are no padding or alignment issues. Let us also add some code to instantiate a multi class:"

void f()
{
  multi m;
  multi *pm = &m;
  multi **ppm = ±
//...

"The compiler uses the address of the first byte of the multi object as the multi pointer, that is, 0x1000. Now, suppose you add another couple of variables to this function:"

//...
  child1 * pc1 = &m;
  child1 ** ppc1 = &pc1;
//...

"The compiler simply takes the address of m, adjusts it to the correct subobject — in this case, the start of the child1 subobject — and assigns it to pc1. ppc1 simply contains the address of pc1:"

"But suppose, now, you want to assign ppm to ppc1:"

//...
  ppc1=ppm; // How to handle this?
//...

"Suppose the compiler allowed you to assign the value contained in ppm directly to ppc1. ppc1 would then be set to the value 0x1020 — which is the address of pm, which in turn points to the base address of multi, 0x1000. When you dereference ppc1, you would expect to get a pointer-to-child1. However, you would actually get a pointer-to-parent (or multi, as they share the same base address in our hypothetical compiler)."

"I get it," I exclaimed. "But wait — how come it worked before?"

"With non-virtual inheritance, this particular compiler assigned the same base address to the child and parent subobjects. In essence, the bit-patterns of the two addresses happened to be identical, so the reinterpret_cast happened to do the right thing."

"Great," I replied. "I understand the theory. Now how do I fix the problem?"

"Remember these words: 'Every problem can be solved with an extra layer of indirection.' In this case, my child, we have too many layers of indirection."

"Too many layers," I pondered. Then, the penny dropped. "Remove a layer of indirection!" I scribbled some code on the whiteboard:

void
childPtrPtr(child **d)
{
  parent *pp = *d;
  parentPtrPtr(&pp);
}

"Very good, my child. The adjustment to the this parameter occurs when you assign from the child* to the parent*. The parentPtrPtr function now receives a true pointer-to-pointer-to-parent."

"And just in time, too," I said, as I spied Anna approaching. "Here comes my lunch date." The Guru made a graceful exit. Just then, Bob wandered up, on his way to get a fresh latte. He greeted Anna.

"Hey, sugar, what brings you in? Are we having lunch today?"

"Maybe next time, Dad. I'm going to lunch with my boyfriend," Anna pointed at me.

I stared at Bob, aghast. He stared back. Both of us turned to Anna, blurting "He's your what?!"

"He's our what?" I blinked.

"Our controller," Jeannine waved at a sergeant who was coming out to join us. "We'll have to report through him."

"Hello, Doctor Carruthers," the sergeant said to Jeannine. "This is—?" Jeannine nodded and introduced me. "Your suits are here inside,"the sergeant said, leading us in. "The protocol is that you'll always have to wear them down there with helmets closed, even in pressurized rooms."

Inside the obelisk, the lighted area turned out to be a medium-sized room with suits on the walls, and in the center a large hole ringed with a mesh fence. "Put your hand there to sign in," the sergeant instructed; "then let's get those suits on and checked." As we did so, a platform ascended from inside the hole and stopped level with the floor; we entered through a gate in the fence, paused, and then the elevator started to descend.

Jim Hyslop is a senior software designer at Leitch Technology International Inc. He can be reached at [email protected].

Herb Sutter is an independent consultant and secretary of the ISO/ANSI C++ standards committee. He can be reached at [email protected].