chapter 10 virtual methods.htm

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

<P>Notice how in the layout for class <TT>W</TT> in figure {MEMVW} is arranged 
into groups. The main group for the instance is arranged in memory much like 
class <TT>R</TT> in figure {MEMVRST}. 
<CENTER><IMG src="Chapter 10 Virtual Methods.files/MEMVW.gif"></CENTER><!-------------------------------------------------------------------------------->
<H2>10.3 Implementation of Virtual Procedures and Functions</H2><!-------------------------------------------------------------------------------->The 
implementation of virtual functions tends to be rather involved, as one might 
imagine. The <TT>SAL-Class.CPP</TT> file has utilities that take care of most of 
the difficult parts for us. Also, all of the utilities to manage virtual methods 
at the group level are within the symbol table. 
<H3>10.3.1 Parsing for Virtual Procedures and Functions</H3><!-------------------------------------------------------------------------------->The 
only modification to the parser that is necessary is the addition of one new 
keywords in rule ProcDeclaraion and rule FuncDeclaration, <TT>virtual</TT>. If 
you encounter the keyword <TT>virtual</TT>, you set a boolean variable isVirtual 
to true to pass on to RuleProcHeading or RuleFuncHeading. This is shown in grey 
in figures {RULE58P} and {RULE59P} 
<MENU><IMG src="Chapter 10 Virtual Methods.files/RULE58P.gif">
  <P><FONT face=arial size=-1><B>Figure {RULE58P}</B> </FONT></P></MENU>
<MENU><IMG src="Chapter 10 Virtual Methods.files/RULE59P.gif">
  <P><FONT face=arial size=-1><B>Figure {RULE59P}</B> </FONT></P></MENU>
<H3>10.3.2 Symbol Tables for Virtual Procedures and Functions</H3><!-------------------------------------------------------------------------------->This 
is where most of the real work happens. We begin with <TT>RuleExtends()</TT> in 
the compiler. In chapter 9, section 9.2.6 we have already done some of the work. 
<PRE>      RuleExtends(Set follow, Symbol last, ClassBlock* classblock, int &amp;totalsize, int &amp;vProcCount, bool&amp; First)
      var
        bident: Ident;
        base: BaseIdent;
        btref: ClassBlock;

        curroffs: card;
        <B>First: bool;</B>

      begin
        curroffs:= 0;
        <B>// First:= true;</B> &lt;-- this was here before it is now initialized in Rule Class Type

        . . .
         
        bident:=RulePredeclaredType(...); 

        . . . 
       
        //*** Add a new base class to the class's block
        base := table.Append_Base (bident-&gt;getName(),bident-&gt;getSize(),

        bident-&gt;getExtra()); //*** Get the block information for the base
        class  btref=bident-&gt;getExtra()-&gt;toClassBlock();

        <B>// Reserve space for our vtable (will not be shared with virtual base class)
        if Shared and First then     
          curroffs:= curroffs+4;
        end if;
        First = FALSE;</B>

          //*** Set some information for this
        baseclass
        base-&gt;setOffset(curroffs);base-&gt;setIsShared(Shared);

        //*** Update the size of the class
        if Shared then
          curroffs:=  curroffs + 4;
          classblock-&gt;AddGroupItem (btref);
        else
          curroffs:=  curroffs +btref-&gt;getGroupSize();
          <B>base-&gt;setVtblOffset(vProcCount);                     // set the vtable offset for base class
          vProcCount:=  vProcCount +btref-&gt;getVtblGroupSize(); // update the current virtual index</B>
        end if;
        
        classblock-&gt;MergeGroupList (btref);
</PRE>Above, we have the listing from section 9.2.6 with some extra lines added 
to set up virtual functions. The first thing that we have to take into account 
is a tricky little fix to get virtual functions to work with shared inheritance. 
Suppose we have two classes, A and B, and B inherits from A. Both classes will 
share the same vtable pointer and the same vtable. However, if B inherits a 
shared instance of A, they cannot. We need to set up an instance of B so that it 
has its own vtable entry, and not try to share one for A.
<P>Let's look at some examples in figure {MEMCMP}. In the first two examples, we 
can see the differences between class B inheriting a unique versus shared copy 
of class A. In c) and d), we can see this diference a little more dramatically 
when the order of classes A and B are reversed for class C. In c), Three 
pointers are required, whereas in d), there are only two, since class C can 
share its vtable pointer with B.
<P>
<MENU><IMG src="Chapter 10 Virtual Methods.files/MEMCMP.gif">
  <P><FONT face=arial size=-1><B>Figure {MEMCMP}</B> Differences in memory 
  layout when one or more base classes are shared. <B>a)</B> Two classes with 
  standard inheritance. A and B both share their vtable pointer. <B>b)</B> In 
  this example, A is shared, and has its own section in the vtable. B has its 
  own vtable pointer, too. <B>c)</B> When Class A is inherited first, C cannot 
  share B's vtable pointer because of B's position in the heirarchy. By the 
  leftmost-rule, a class can only share its vtable pointer with the leftmost 
  base class. In this case, the leftmost class is shared. <B>d)</B> C shares its 
  vtable pointer with B.</FONT></P></MENU>This little fix is necessary only when a 
class's <I>first base class</I> is shared. So we pass in a boolean variable 
FIRST. This gets initialized to <TT>true</TT> in RuleClassType. This is to avoid 
problems with multiple extends statements The only remaining work to be done in 
<TT>RuleExtends()</TT> is for unique base classes. We need to set the start of 
the base class's vtable in the current vtable. Next, we need to update the count 
of virtual functions from the base class, so that we can properly begin 
numbering the virtual functions for the current class.
<P>In RuleClassBlock, we have a handful of additional requirements. First is 
that we maintain a variable to keep track of the current virtual index. At 
first, this index will be the sum of all virtual procedures from all base 
classes in the current group. Later, when we begin declaring virtual functions, 
we use this number to set the virtual index for each one. 
<MENU><IMG src="Chapter 10 Virtual Methods.files/RULE13S.gif">
  <P><FONT face=arial size=-1><B>Figure {RULE13S}</B> </FONT></P></MENU>In 
addition to the changes shown in figure {RULE13S} two lines have to be added to 
the end of <TT>RuleClassType()</TT> before the call to 
<TT>ClassBlock::AllocateShares()</TT> or <TT>BuildConstructor()</TT> <PRE> 
   classblock-&gt;setVtblGroupSize(vprocNum); // Set the size for our vtable
   if(classblock-&gt;getVtblSize()) then
       classblock-&gt;setVtblProcnum(++procNum); // Set the vtable procnum 
   else
       classblock-&gt;setVtblProcnum(0xFFFF);
   end if;
</PRE>In SAL, the vtable for each class type is stored in memory as a procedure. 
This is for a number of reasons. First of all, by its nature, a virtual table is 
procedure-related. Second, this provides some measure of protection from rogue 
pointers or array overflows. Third, and probably the most important reason is 
that calling a virtual function is equivalent to calling an external function. 
This necessitates a module number/procedure number pair. Module numbers are not 
known until runtime, and need to be fixed up. It is not possible under the SAL 
VM's specification to do module fixups on data segments. Only on a code segment 
can we do module number fixups. For these three reasons, we store all vtables in 
the code segment, and give them a procedure number.
<P>The next thing that has to be done is a modification to 
<TT>RuleProcHeading()</TT> and <TT>RuleFuncHeading()</TT> 
<MENU><IMG src="Chapter 10 Virtual Methods.files/RULE5657S.gif">
  <P><FONT face=arial size=-1><B>Figure {RULE5657S}</B> </FONT></P></MENU>We can 
see in figure {RULE5657S} that we need to make a call to tell the current 
procedure that it is virtual. Finally, before exiting either rule, we need to 
check to see if the procedure/function is a class method, and if so, does it 
match a base class method that was declared as virtual? If this is the case, 
then the call to <TT>FindVirtualMatch()</TT> will set the appropriate flags in 
the current method, making it also virtual.
<P>The next modification that we need is to <TT>RuleMemberField</TT>. Virtual 
calls can be overridden if/when scope resolution is used. Suppose a class named 
A had a virtual function called foo(). With a pointer to A, any call to foo() 
will be through the virtual function table. <PRE>      a-&gt;foo();   // call through vtable, may be A::foo(), or some other class's foo().
</PRE>However, we can override this behavior in SAL by using the scope 
resolution operator: <PRE>      a-&gt;A::foo();   // A::foo() will definately be called.
</PRE>In order to help enforce this behavior, the <TT>TraceInheritance()</TT> 
function takes an additional parameter called <TT>Scoped</TT>, which is a 
Boolean. In section 9.2.6 of chapter 9, we passed in a dummy variable. We need 
to actually get this value, and pass it into <TT>RuleProcFuncCall()</TT>. 
<MENU><IMG src="Chapter 10 Virtual Methods.files/RULE20S.gif">
  <P><FONT face=arial size=-1><B>Figure {RULE20S}</B> </FONT></P></MENU>For this, 
<TT>RuleProcFuncCall()</TT> needs to be modified for the addition of one more 
parameter. <PRE>      proc RuleProcFuncCall(follow: Set; funcName: ^ident; self: ^type; <TT>scoped: bool</TT>);
</PRE>This parameter is only use at the end of the rule, when we emit code for 
the procedure/function call.
<P><TT>RuleProcFuncCall()</TT> needs only one additional modification at the 
symbol level. In SAL, when a function takes a class as a parameter passed by 
reference or by pointer, we have the ability to pass in any deriving class, as 
well. This gives SAL some of the benefits of polymorphism. This does not work 
using pass by value. Suppose we have a class A, and a function foo() that takes 
an instance of A passed by reference. We should be able to also pass in to foo() 
any instance of another class B that inherits from A.
<P>This is accomplished by utilizing the two functions, 
<TT>FindBaseClass()</TT>, and <TT>GenMemberAddr()</TT>. We saw these functions 
earlier in chapter 9 when we talked about inheritance. <TT>FindBaseClass()</TT> 
takes two paramters, the first is the type that we want to convert to, and the 
second is the type that we want to convert from. If <TT>FindBaseClass()</TT> 
returns successfully, we can then obtain a pointer to the block for the given 
class, and call <TT>GenMemberAddr()</TT>, converting it to the desired class.
<P>
<MENU><IMG src="Chapter 10 Virtual Methods.files/RULE21S.gif">
  <P><FONT face=arial size=-1><B>Figure {RULE21S}</B> </FONT></P></MENU>Reid's 
Note: <FONT color=green>CS531 Students, I would to this in VerifyParameter 
adding this in an extra <TT>else ifident-&gt;getDatatype() == classtyp</TT> 
section.</FONT> 
<P>We must also make a similar change to rule assignment. This will allow us to 
make an assignment of a derived class to a base class. We can make this change 
in Rule assignment as follows (new code in green): <PRE>		if(ltype.getPlev() &gt; 0) then
			<FONT color=green>
			if(ltype.getPlev() == 1 &amp;&amp; ltype.getType() == classtyp &amp;&amp; rtype.getPlev()&lt;&gt; NULL_PLEV) then
				if(FindBaseClass(ltype, rtype)) then
					ClassBlock *cblock = rtype.getExtra()-&gt;toClassBlock();
					GenMemberAddr(cblock);
				else
					SemanticErrorMsg("Class-casting must be performed explicitly in this case");
				end if
			end if</FONT>
			Emit(xSSD,0);
		end if;


</PRE>
<H3>10.3.3 Code Generation for Virtual Procedures and Functions</H3><!-------------------------------------------------------------------------------->At 
the end of <TT>RuleProcFuncCall()</TT> there should already be a call to a 
function called <TT>EmitCx()</TT>, which takes the ident that was passed in to 
the rule. If our function is virtual and no scope resolution was used in the 
call, then we do <I>not</I> want to have the function called in this manner. We 
will emit the call directly. If the identifier passed in is a virtual function, 
and if no scope resolution is used, and finally if the self parameter is a 
reference (i.e., passed by reference) we need to emit the virtual call directly. 

<MENU><IMG src="Chapter 10 Virtual Methods.files/RULE21C.gif">
  <P><FONT face=arial size=-1><B>Figure {RULE21C}</B> </FONT></P></MENU>For a 
better description of the <TT>CV</TT> instruction, refer to the document, 
<I>"SAL VM Instruction Set"</I> in the reference section at the end of the table 
of contents.
<P><!-------------------------------------------------------------------------------->
<H2>10.4 Conclusion and Further Reading</H2><!-------------------------------------------------------------------------------->Virtual 
functions are invoked only through a pointer or a reference to a class. In order 
for a method of a deriving class to override the method of a base class, the 
prototype of the method of the deriving class must exactly match the prototype 
of the method in the base class.
<P>Virtual tables are used to resolve virtual function calls at runtime. A 
virtual table, or vtable is a list of ordered pairs containing function pointers 
and deltas. A deriving class shares its vtable pointer with the first base class 
listed in its declaration. All other base classes have their own vtable pointer. 
The function pointer points to the true function that is to be invoked. The 
delta is used in multiple and shared inheritance to modify the address to self. 
In a call to a virtual method, the address of the overriding class might not be 
the same as the address of the calling class. The delta is a signed number that 
is added to the address of the calling class to promote the reference or pointer 
to that of the called class.
<P>Virtual indexing is used to find the function that should be called. A call 
to a virtual method is performed by using the method's virtual index and looking 
up the proper method and delta in the vtable. Classes begin their virtual 
indexing by adding together the sizes of all vtables of the base classes within 
their group. Vtables are orgainzed into groups in the same way instances are.
<P>For further reading, the reader should consult the Annotated C++ Reference 
Manual by Margret Ellis, or the Third addition of (the C++ Programmer's Manual) 
by Bjarne Stroustrup.
<P><!-------------------------------------------------------------------------------->
<H2>Exercises</H2><!-------------------------------------------------------------------------------->
<OL>
  <LI>Given the complexities that multiple inheritance introduces and the added 
  complexity of groups in shared inheritance, what might have been the thinking 
  behind the design of inheritance in the Java language? Explain. How would the 
  vtables in a java class be laid out?
  <P></P>
  <LI>An abstract base class is one that contains no member variables of its 
  own, and whose methods have no implementations (i.e., no function bodies). It 
  is therefore impossible to have a pure instance of an abstract base class. 
  Aside from the certain occaisional necessity to utilize multiple inheritance, 
  why might the designers of Java included abstract base classes (called 
  interfaces) in Java inheritance?
  <P></P></LI></OL></BODY></HTML>