chapter 9 designing classes.htm

英文版编译器设计：里面详细介绍啦C编译器的设计

<H4>9.2.3.1 Shared Groups</H4><!-------------------------------------------------------------------------------->In 
order to properly understand the implementation of shared inheritance, it is 
important to understand a concept called shared grouping. A shared group is a 
set of superclass and subclass instances within a hierarchy, none of which are 
shared. All instances within a shared group contain one most-derived class, and 
each group is named after this class.
<P>Any class has one or more shared groups internally. The simplest of all 
groups is a single class, which inherits from nothing. That class is a group all 
by itself. If that class were to directly inherit from one or more superclasses 
each of which was a unique instance, all classes, i.e., the superclass(es) and 
the single subclass would be in the same shared group. The superclasses may also 
in their turn inherit unique instances of other superclasses, and all classes 
within the hierarchy will be included in the same shared group.
<P>Group division occurs whenever a class inherits a shared instance of another 
class. At that point, two shared groups are formed. One for the subclass and all 
remaining superclasses which are unique, and another for the shared superclass 
and all of its unique superclasses. Figure {GRPEXA} has five examples that 
visually demonstrate this system.
<P>
<MENU><IMG src="Chapter 9 Designing Classes.files/GRPEXA.gif">
  <P><FONT face=arial size=-1><B>Figure {GRPEXA}</B> Examples of several class 
  hierarchies and their internal groups. In these examples, thick arrows denote 
  shared inheritance. Thin arrows denote unique inheritance. Dashed lines mark 
  the edges of group boundaries. a) A single class is contained in a single 
  group. b) Single and multiple inheritance hierarchies without any shared 
  inheritance are contained in the same group. c) A single inheritance hierarchy 
  employing shared inheritance. Z inherits a shared instance of A, and both are 
  in their own group. d) A more complex hierarchy with two groups. Class C 
  inherits a shared instance of class R, and a unique instance of class B. R is 
  placed into its own group, and B becomes a part of C's group. e) A complex 
  hierarchy with three internal groups. Notice that group R is shared by classes 
  from two different groups. Class X has inherited a shared instance of R, which 
  is shared with class C. The most derived class, Y, has also inherited a shared 
  instance of C. </FONT></P></MENU>The list of shared groups for each instance is 
kept in a set. Single classes with no base class have an empty set. Sets are 
propagated from superclass to subclass according to these rules: 
<OL>
  <LI>A class begins with an empty set. 
  <LI>A class performs a union of all sets belonging to its superclasses. 
  <LI>A class adds an entry for each superclass that is shared. </LI></OL>
<P>The result is the list of shared groups for an instance of the derived class. 
Figure {PASGRP} demonstrates an example of this process. 
<MENU><IMG src="Chapter 9 Designing Classes.files/PASGRP.gif">
  <P><FONT face=arial size=-1><B>Figure {PASGRP}</B> This figure represents 
  passing sets of shared groups at each stage of declaration. a) A single class 
  A is contained in its own group, called <I>A</I>, and its set of shared groups 
  is empty. b) Classes B and C both inherit shared instances of A. They each add 
  a group for A to their set. Since the set for group <I>A</I> is empty, nothing 
  more can be added. c) Class E inherits unique instances of classes B and C, 
  and a shared instance of another class D. A new entry for D's group is added 
  to Class E's set, as well as the union of all the groups in the sets for B and 
  C. The final set of shared groups for an instance of class E is {A, D}. 
  </FONT></P></MENU>
<P>The shared group concept is crucial to the way classes are organized in SAL. 
It is used in implementing every feature of classes. Some of these uses are in 
determining how classes are laid out in memory, how classes are initialized by 
constructors, how they are finalized by destructors, and how virtual functions 
operate.
<P>
<H4>9.2.3.1 Memory Layout</H4><!-------------------------------------------------------------------------------->Aside 
from shared inheritance, we can prove that every instance of a class, including 
those that are contained within another class as a superclass look identical. 
Refer again to figure {CLSAMEM} in section 9.2.2. Instances of class A and B 
look the same reguardless of where they appear in memory; even if they are a 
part of class C, they look the same as if they were discrete (stand-alone) 
instances. The same would go for every instance of class C, reguardless of 
whether each one appeared as a superclass of some other, or stood alone as 
discrete instance, every instance of C would always look the same. C's two base 
classes, A and B will always be at their same offsets from the start of C, and 
C's members will always be in the same place. Nothing ever has to be moved.
<P>A shared group represents a set of all class instances that can be placed 
together in one block of memory. At the beginning of section 9.2.2 we explained 
the memory layout of classes, and that inheritance meant including the members 
of all superclasses at the beginning of the subclass, in the order that they 
were listed in the subclass's declaration. A significant problem arises with 
shared inheritance.
<P>Let's refer back to figure {MVI}, and listings {UMI} and {SMI} at the start 
of section 9.2.3. Using the methods of inclusion discussed in section 9.2.2, an 
instance of class A from listing {UMI} (see figure {MVI}-a) would be laid out in 
memory in a manner as shown in figure {UMIMEM}. 
<MENU><IMG src="Chapter 9 Designing Classes.files/UMIMEM.gif">
  <P><FONT face=arial size=-1><B>Figure {UMIMEM}</B> Memory layout for an 
  instance of class D in listing {UMI}. Notice that classes B and C have 
  included their own instance of A. </FONT></P></MENU>Notice that if class D were 
to be shared, there would be no way to guarantee from class B and class C's 
point of view that it would be in the same place. We might move the single 
shared instance to another spot, but this would be unique only to instances of 
class A. Furthermore, the problem potentially compounds itself when A is in turn 
subclassed and other classes want to share D as well. In short, D would have to 
be placed in a unique spot for each class.
<P>This problem quickly goes out of control due to the fact that the need to 
know a base class's location arises at run time. The location of all of a 
class's superclasses must remain <I>constant</I> in some way or another.
<P>The solution to this problem makes use of shared groups. When laying out 
instances containing shared groups in memory, we partition the block of memory 
into segments, one for each group. When a class inherits a shared instance of a 
superclass, it places an offset in the position where the base class would 
normally be included. This iffset points to the segment of the memory block 
where the base class's shared group resides. We can see in figure {BCMEM} how 
this is done with classes B and C of listing {SMI} 
<MENU><IMG src="Chapter 9 Designing Classes.files/BCMEM.gif">
  <P><FONT face=arial size=-1><B>Figure {BCMEM}</B> Arrangements of classes B 
  and C of figure {SMI}. The memory is partitioned into segments where each 
  separate group resides. Both B and C have a four-byte offset in the place of 
  class A, which points to the start of the segment for A's group. 
</FONT></P></MENU>Notice that the main group is always first; however, the rest 
of the groups may follow in <B>any arbitrary order</B>. In SAL, the deltas are 
32 always bits. Depending on the language and the complier, they can be 16 bits 
(limiting the size of a class somewhat), or they may be actual pointers instead 
of deltas.
<P>In figure {SMIMEM} we can see the layout of an instance of class D. 
<MENU><IMG src="Chapter 9 Designing Classes.files/SMIMEM.gif">
  <P><FONT face=arial size=-1><B>Figure {SMIMEM}</B> The memory layout of class 
  D from listing {SMI}. </FONT></P></MENU>For the sake of simplicity in 
calculating the position of a shared group's segment, the deltas are offsets 
from the beginning of the class, itself, and not from the offset's position 
within the class. For instance, if some class A were to inherit a unique 
instance of P and a shared instance of Q, the main group for A would contain an 
instance of P, and an offset to a group containing Q; the remaining portion of 
the segment would contain the members of A. For any instance of A, the offset to 
Q's group segment would always be from the start of that instance, reguardless 
of whether the instance is alone or an integrated part of another class 
hierarchy. Generally, for any class <I>Y</I> that inherits a shared instance of 
<I>X</I>, <I>Y</I> will maintain an offset in the place of <I>X</I>, the offset 
being from the beginning of <I>Y</I> to the start of <I>X</I>'s group.
<P>
<H4>9.2.3.1 Initialization</H4><!-------------------------------------------------------------------------------->One 
might ask the question, how does each delta get initialized? The answer might 
seem obvious at first: the constructor. However, this is not entirely true. A 
problem arises when we consider that it is important for each group to be 
initialized once and only once. The real question then becomes, "How do we let a 
particular constructor know that one of its shared groups groups has already 
been initialized?" We could place a flag at the start of each shared group, but 
that then brings up the question of "who is going to initialize that flag?" It 
quickly becomes obvious that we have a chicken-vs-egg problem. The constructor 
could initialize the flag, but that only works when no other class inherits from 
the current one.
<P>It turns out that (as in all things in computer science) that there are many 
solutions to the problem. One would be for all class constructors to take an 
additional parameter (besides self), which acts as a boolean flag, saying 
whether or not this instance of self is <I>the</I> base class of the entire 
instance. If so, the constructor will go ahead and initialize the flags at the 
start of each group.
<P>Another solution would be for the memory manager to zero out the memory for 
the entire class and all its shared groups. This method is nice and gives us the 
advantage of pre-initialized arrays and records as well, but it has the drawback 
of being somewhat inefficient, especially for large structures. In SAL we use 
another solution, and arguably it has its advantages. We use what is called a 
meta-constructor. The meta-constructor actually has many jobs: 
<OL>
  <LI>Initialize the deltas for shared groups 
  <LI>Initialize the init-flags for shared groups 
  <LI>Build the virtual tables 
  <LI>Initialize the pointers to the virtual tables 
  <LI>Call the meta-constructor for any member classes 
  <LI>Call the constructor for the most derived class </LI></OL>The 
meta-constructor's main purpose is to set up the most basic features of a class 
instance, and assure that the constructor for each instance can be safely 
called. It can be said that a meta-constructor's job is to format the instance's 
memory in much the same way that a floppy disk is formatted prior to storing 
data on it.
<P>The only real item on the list that needs to be discussed at this point is 
numbers 1 and 2. At declaration time, the compiler makes use of an assortment of 
procedures to manage shared groups and precalculate all their sizes. One of 
these features also generates a meta-constructor for the class. Generating a 
meta-constructor is a recursive process. Although the shared groups are laid out 
in a serial fashion, all the references to those groups must be found, and they 
can be scattered throughout the class. References are initialized by traversing 
the heirarchy in a depth-first fashion, and then generating code to store the 
appropriate delta.
<P>The addition of an initialization flag at the start of memory alters our 
class model slightly. Offsets to shared groups still point to the start of the 
group's data, but they no longer point to the start of the segment for the 
group. Below in figure {GRPFLG} we have an instance of class B from listing 
{SMI} as it is really laid out in memory. 
<MENU><IMG src="Chapter 9 Designing Classes.files/GRPFLG.gif">
  <P><FONT face=arial size=-1><B>Figure {GRPFLG}</B> An instance of class B from 
  listing {SMI} with the initialization flag. Notice that the offset still 
  points to the start of the member data for A. The byte for initialization is 
  placed immediately at the start of the group segment. Thus, the data is still 
  at the offset given for the shared group's segment, and the group's 
  initialization flag is at that offset minus one. </FONT></P></MENU>A 
meta-constructor is created to initialize a particular instance of a class only, 
and each meta-constructor initializes all base classes within that instance. 
meta-constructors do not call eachother. Consider listing {SMI}. The 
meta-constructor used to initialize an instance of class D will initialize B, C, 
and A. It will not call the meta-constructors for classes B, C, or A, it will 
initialize (pre-format) these itself. The only time that one meta-constructor 
will call another is when one structure contains another, which has a 
meta-constructor that must be called. For instance, if class A were to have a 
member that was an instance of some other class Z, the meta-constructor for 
class D would also need to invoke the meta-constructor for A::Z.
<P><I>Addendum:</I> The meta-constructor approach is certainly not the only 
approach, but among all our options it certainly is one of the more general. 
This idea can easily be expanded for any structured item that needs to be 
initialized. In SAL, meta-constructors are also used for records that contain 
classes, arrays of classes, and classes that contain member classes. Moreover, 
the meta-constructor makes the implementation of standard class constructors 
much easier, removing most of the complexity. In fact, without 
meta-constructors, we would not be able to implement multiple inheritance until 
standard constructors had been developed. Whether or not this approach is used 
in a compiler is a matter of design, and its use can certainly be debated. 
Reguardless, the task of meta-construction <I>must</I> be performed by any 
language that has the type of inheritance discussed here, such as C++. 
Unfortunately, references to how commercial compilers perform their internal 
tasks are often gurarded as trade secrets, and are not published.
<P>There are hints available, however. In <I>The Annotated C++ Reference 
Manual</I>, M. Ellis makes mention that it is against the C++ standard to allow 
a pointer to a class constructor. The reason for this is that the constructor is 
meant to convert a block of memory from raw, random bits into a structure that 
we know as a class. Additionally, the compiler may have constructors take