next up previous contents index
Next: IV. Fourth Part: Run-Time Up: III. Third Part: Expansion Previous: 12. Expansion of Controlled-Types   Contents   Index

Subsections


13. Expansion of Tagged-Types

Tagged-types give linguistic support to the two basic object-oriented concepts: type-extension and inheritance. In Ada95, a tagged-type defines a class that designates a set of types derived from a common root, thus sharing properties and enabling class-wide programming. Note that the word class has a slightly different meaning in most other object-oriented languages, where it is used to designate a single type and not a hierarchy of types.

It is important to distinguish clearly between primitive operations of a tagged type, which have one or more parameters of their associated type (or an anonymous access to it), and subprograms operating on class-wide objects (or access to class-wide objects). The former are inherited when the type is extended, and may be redefined in an extension, each version applying to its specific type only. By contrast, subprograms with class-wide formals have a single definition and apply to all members of the class. Dynamic dispatching occurs whenever a primitive operation is called and (at least) one of its formal parameters has a specific tagged-type and its corresponding actual is class-wide; this parameter is called a controlling argument. The tag of the actual determines which version of the primitive operation is to be called.

Most of the implementation of tagged types in GNAT follow the ideas discussed in [Dis92] and [CP94]. This chapter presents the main aspects of this model.


13.1 Tagged and Polymorphic Objects

The intuitive idea behind tagged-types is that values of such a type carry a tag which is used, among other things, to relate the run-time value to its original type and to the operations that apply to it. This tag allows the simple implementation of run-time type-specific actions, such as dynamic dispatching and membership testing. Let us consider the following declaration of a root tagged-type:

\begin{figure}\begin{lstlisting}{}
type My_Tagged is abstract tagged
record
...
end record;
\end{lstlisting}\end{figure}

It is transformed by the GNAT front-end by the addition of a new component, whose predefined type appears in Ada.Tags:

\begin{figure}\begin{lstlisting}{}
type My_Tagged is abstract tagged
record
_Tag : Tags.Tag;
...
end record;
\end{lstlisting}\end{figure}

Each tagged-type has its own tag. A copy of the tag is inserted into every object of the type. The value of the tag is a pointer to a type-specific data area, that includes first and foremost a table of primitive operations of the tagged-type. This table is built at the point the type is frozen. The tag of an object is constant, and cannot be modified after the object is created. (Note that a conversion cannot affect the tag of an object, its purpose is to allow the object to be viewed as another member of the class - a view conversion - but does not actually change the value of the tag stored in the object).

By definition a type extension inherits all the components of its parent. We could describe the type extension by copying explicitly all the component declarations of the parent and appending the components in the extension. It turns out to be simpler to describe all the inherited components as being part of a single inherited collective component, called _Parent. The following type extension:

\begin{figure}\begin{lstlisting}{}
type My_Ext_Tagged is new My_Tagged with
record
...
end record;
\end{lstlisting}\end{figure}

It is expanded as follows:

\begin{figure}\begin{lstlisting}{}
type My_Ext_Tagged is
record
_Tag : Tags.Tag;
_Parent : My_Tagged;
...
end record;
\end{lstlisting}\end{figure}

The main advantage of this technique is that it transforms record extensions into regular records.

For many reasons, it turns out to be mandatory that any field in a tagged type keep the same location within the record in any descendant type. To start with, dynamic dispatching depends on the value of the tag, and thus the tag must appear at the same location in all tagged types. Additionally, for a class-wide object whose actual type is not known until run-time, selecting any component would be impossible (or prohibitively inefficient) if the position of the field depended on the type. By having all the inherited components appear conceptually as part of a single _Parent component type insures that the layout of the parent is respected. This component is inserted at the beginning of the record. Components of the extension follow.

13.2 The Dispatch Table

A dispatching call consists in selecting and calling the version of a primitive operation that applies to the type of its controlling argument. Recall that in Ada95, unlike C++, whether a call is dispatching or not depends on whether there is a class-wide actual. If the actuals are statically tagged, the compiler can determine the operation to be called. If an actual is dynamically tagged, the run-time call must be indirect: the proper operation must be selected from the dispatch table of the type of the actual. The dispatch table is a table of subprogram addresses, and a dispatching call is an indirect call through an entry in the table. The position of each primitive operation in the table is established by the compiler, so the call uses a static offset to determine the address of the subprogram to be called. (cf. Figure 13.1).

Figure 13.1: Dispatch Table Example.
\begin{figure}\centerline{\psfig{figure=figures/tagged_types/dispatch_table.eps,
width=13.5cm}}\end{figure}

The left side of figure 13.1 shows the declaration of a tagged-type, some user-defined primitive subprograms for it (My_Primitive_OpN), one non-primitive dispatching subprogram (My_Class_Op1), one object declaration of the type (Obj), and a non-dispatching call to one primitive operations. On the right side we display the expanded code produced by the GNAT front-end. The tagged-type generates a data structure that is essentially an array of addresses, of which the dispatch table is the central component (we discuss later the other components of the type-specific data). The front-end also generates code to initialize the dispatch table, by storing in it the addresses of the primitive subprograms of the type. In an object, the tag component is a pointer to the dispatch table.

In addition to dispatching calls, a predefined operation that requires run-time type information is the membership test: X in T. When T is a specific tagged-type, this test consists simply of verifying that X's tag points to the dispatch table for the type T (for convenience, the tag of T is also present in the type-specific data for T). When the test is of the form X in T'Class, the problem is more complex, because the tag of X can be a pointer to any descendant of T. Two implementations are possible for this test. One can store in the type-specific data a pointer to the dispatch table of the immediate ancestor. In this case the membership test consists of traversing the list of ancestors' dispatch tables, and return True if the dispatch table for T is found during the traversal. The other implementation stores the tags of all the ancestors in the type-specific data, along with the inheritance depth (the total number of ancestors of the type, i.e. the distance to the root in the type hierarchy). The difference in depths between the type of X and T gives the actual location where T must be found in the table of ancestor tags for the membership to succeed. GNAT implements this later approach because it ensures that the evaluation of the membership test takes constant time (see details in  13.3).


13.3 Primitive Operations

The following subprograms are present for all tagged types, and provide the results of the corresponding attributes. The bodies of these subprograms are generated by the front-end, at the point at which the type is frozen. These subprograms must in general be dispatching, since they can apply to class-wide objects, and the value produced will vary with the actual object subtype: _Alignment, _Size, _Read, _Write, _Input, and _Output. In addition, the following subprograms are present for non-limited tagged-types, and implement additional dispatching operations for predefined operations: _equality, _assign, _deep_finalize, and _deep_adjust. The latter two are empty procedures, unless the type contains some controlled components that require finalization actions (the deep in the name refers to the fact that the action applies recursively to controlled components, cf. Chapter 12).

For example, let us assume the following tagged-type declaration:

\begin{figure}\begin{lstlisting}{}
type My_Record is tagged
record
My_Data : Integer;
end record;
\end{lstlisting}\end{figure}

The GNAT front-end generates the equivalent of the following expanded code from it:

\begin{figure}\begin{lstlisting}{}
-- Declaration of the type-specific data
type...
... String := ''My_Object''; -- Debug info
end record;
\end{lstlisting}\end{figure}

\begin{figure}\begin{lstlisting}{}
function _Alignment
(X : My_record) return I...
...dress;
My_Record_Data.DT (2) := _Size'Address;
...
\end{lstlisting}\end{figure}

The format of GNAT's dispatch table is customizable in order to match the format used by other object-oriented languages. GNAT supports programs that use two different dispatch table formats at the same time: the native format, that supports Ada 95 tagged types and which is described in Ada.Tags, and a foreign format for types that are imported from some other language (typically C++) which is described in interfaces.cpp. Several pragmas are provided to allow the user to specify the position of the tag in the foreign layout. The boolean field (_F) is used for elaboration purposes. Finally the name of the tagged-type is expanded in a string-type field (_E). This field is used by the debugger.

After the record type, the expander creates the bodies of the default primitive operations. By default, the bodies of _Read, _Write, _Deep_Adjust, and _Deep_Finalize are empty. The other subprograms are expanded as follows:

\begin{figure}\begin{lstlisting}{}
function _Alignment (X : My_Record) return In...
...ARL.Undefer.all;
raise Program_Error;
end _Assign;
\end{lstlisting}\end{figure}

_Alignment and _Size return the value of the corresponding attribute applied t to the object; _Input and _Ouput call the corresponding _Read and _Write primitives (both being null by default, this does nothing); ``='' is expanded into the required code to compare all the user-defined components of the tagged-type. Finally, the body of the primitive operation _Assign would seem to be just X:=Y. However, the expanded code protects the user from self assignment (X:=X), which is incorrect if the object is controlled (the finalization of the old value of the left-hand side would end up destroying the object itself). Finally, in order to handle correctly an assignment whose right-hand side is a conversion, the assignment must first preserve the tag of the target, perform the assignment, and finally reset the tag. Let us examine the following example:

\begin{figure}\begin{lstlisting}{}
declare
type My_Record is tagged
record
So...
...j1 := My_Record (Obj2); -- Explicit conversion
end;
\end{lstlisting}\end{figure}

After the elaboration of the two objects, the tag of Obj1 points to the dispatching table of My_Record and the tag of Obj2 points to the dispatching table of My_Extension. The conversion does not change the tag of Obj2, but simply indicates that Obj2 is to be regarded as having the ancestor type in the context of the assignment. If the compiler were to implement the assignment as a copy of the whole contents, the tag of Obj1 would point to the dispatching table of My_Extension which would be clearly incorrect.

13.4 Summary

Objects of a tagged-type include a tag which is used at run-time to implement object-oriented notions of polymorphism and dynamic dispatching. The GNAT expander translates tagged-types into record types with a dispatch table; the tag in an object is a pointer to the dispatch table of the type. Objects of a type extension include a collective component that corresponds to all the components inherited from the parent. The GNAT front-end generates a number of dispatching primitive operations for several type attributes, and generates code to initialize the dispatch table by placing in it the addresses of all primitive operations.


next up previous contents index
Next: IV. Fourth Part: Run-Time Up: III. Third Part: Expansion Previous: 12. Expansion of Controlled-Types   Contents   Index
(C) Javier Miranda and Edmond Schonberg, 2004