next up previous contents index
Next: 13. Expansion of Tagged-Types Up: III. Third Part: Expansion Previous: 11. Expansion of Protected   Contents   Index

Subsections


12. Expansion of Controlled-Types

Controlled-types12.1 are tagged types that support automatic initialization and reclamation. As such, they provide capabilities analogous to constructors and destructors in C++. Automatic reclamation of complex objects with dynamically allocated components goes a long way to compensate for the absence of real garbage collection in Ada95. During the design phase of the language, it was proposed that all tagged types should provide this capability. For various technical reasons, this ambitious proposal was abandoned, and controlled types where placed in a special category: all controlled types derive from a predefined tagged type, and as such all of them inherit three operations: Initialize, Adjust, and Finalize [AAR95, Section 7.6]. The predefined library package Ada.Finalization declares the root type Controlled and its three primitive operations. The package also includes Limited_Controlled, a type whose descendants are all limited, and which only have the primitive operations Initialize and Finalize. The language semantics specifies that Initialize is automatically invoked upon the declaration of an object of a controlled type, if the declaration does not include an explicit initialization; Finalize is automatically invoked when the object is about to go out of scope, i.e. when the scope that declares it is about to be completed. Finalize performs whatever clean-ups are desired (for example, deallocation of indirect structures, release of locks, closing of files, etc.). Finally, Adjust is called on the left-hand-side of an assignment-statement Obj1 := Obj2, after Obj1 is finalized, and the new value Obj2 has been copied into Obj1. Adjust is not defined for limited controlled types. The invocation of these operations is an important part of the expansion phase of the compiler.

When a scope contains several controlled-type objects, each object is initialized in the order of its declaration within the scope. Upon scope exit the objects are finalized in the reverse order. This reverse order is important, since later objects may contain references to earlier objects. If an exception occurs during initialization, then only those controlled objects that have been initialized so far will be finalized.

The primitive operations of controlled types apply not only to stand-alone declared objects, but also to dynamically-allocated objects and controlled components of composite objects. A dynamically allocated object is finalized either when the scope of its associated access-type is exited, or when the programmer explicitly deallocates it. In the case of controlled components of a composite object, the controlled components are finalized in the reverse order of their initialization within the containing object. In addition, Adjust is called when the controlled components are either assigned individually, or upon assignment to their enclosing object. If a controlled object includes controlled components, Initialize or Adjust is first invoked on the components and then on the enclosing object; Finalize is called in the reverse order. Finalization actions also occur for anonymous objects such as aggregates and function results. For these special objects, the finalization will occur upon completion of execution of the smallest enclosing construct, once the value of the aggregate or function result is no longer needed.

12.1 Implementation Overview

The rules described above immediately suggest that the run-time must include some data structure that groups all controlled objects in a given scope. This structure must be dynamic (i.e. a list) because the front-end cannot ascertain statically how many controlled objects will be created in a given scope. Therefore, for each scope that contains declarations of controlled objects (or objects with controlled components) the front-end creates a local variable that holds the head of the list. The front-end then generates code that attaches each controlled object to this list. Finally the front-end generates clean-up code for each such scope. The clean-up code traverses the list in order to perform the appropriate finalization operations on each object. This mechanism requires that controlled objects have some compiler-generated component that holds a pointer to next object in the list (this is in addition to the tag component that is generated for all objects of a tagged type). In fact, finalization lists are doubly-linked, because deletions must at times be performed on them. The two link components are inherited from the root type of all controlled types.

The finalization of objects with controlled components requires additional machinery within the object itself. Consider a variant record, some of whose components may be controlled. It is necessary to locate those components from the enclosing object itself to finalize them when the enclosing object is finalized. As a result, such records include an additional component, called Controller, that anchors the local list of controlled components. The finalization code must traverse this local list as well.

Not surprisingly, there are some complex interactions between finalization and other languages features. In the following sections we discuss the most interesting of these issues, and subsequently discuss their solution in GNAT.

12.1.1 Exceptional Block Exit

The initialization/finalization mechanism must be robust in the presence of exceptions: one of the purposes of finalization is to avoid any memory leaks from the creation of local objects. This purpose must be realized as well in the presence of an abnormal scope termination, such as when an exception is raised, or when the task containing the block is aborted, there may exist objects which have not yet been created and received proper initialization. For this objects, Finalize must not be called. For instance in the folowing code:

\begin{figure}\begin{lstlisting}{}
declare
S1 : Some_Controlled_Type;
X : Pos ...
...ised.
S2 ; Some_Controlled_Type;
begin
null;
end;
\end{lstlisting}\end{figure}

S1 is initialized, but S2 might not be. Consequently finalization should always occur for S1 whereas S2 should be finalized only if it has been initialized. Thus an implementation which expands calls to Finalize at the end of the block is inadequate. As a further complication, note that exceptions may be raised during initialization of composite object containing controlled components, in which case only the initialized components of the object needs finalization.

12.1.2 Finalization of Anonymous Objects

Finalization actions for anonymous objects must occur upon completion of execution of the smallest enclosing construct, that is, as soon as their value is no longer needed. Again, this mechanism has to work even if an exception is raised in the middle of executing the construct. The following code present two examples. Empty is a function returning a controlled object, and Exists is a function that takes such an object as a parameter. The call to Empty creates an anonymous object that must be finalized when the enclosing call to Exists returns:

\begin{figure}\begin{lstlisting}{}
declare
X : Boolean := Exists (1, Empty);
-...
...xecution of either branch of the if statement.
end;
\end{lstlisting}\end{figure}

12.1.3 Finalization of Dynamically Allocated Objects

Recall that dynamically objects can be reclaimed when the corresponding access type goes out of scope. This rule extends to controlled objects: if an object is allocated dynamically, it must be finalized when the the scope of the access type is completed. Of course, if a dynamic object is deallocated explicitly, it must be finalized before the final storage reclamation. The implementation must then attach dynamically allocated objects to the finalization list of the scope of the type itself. The expanded code for any use of Unchecked_Deallocation must include an invocation of Finalize when the designated object is controlled.

12.1.4 Problems Related to Mutable Objects

A variable of a discriminated type with defaulted distriminants may contain differing numbers of controlled components at different times. This possibility introduces an asymmetry between elaboration and finalization. In the following example no controlled components are present at the beginning of the execution, but after the assignment, X will contain three such components:

\begin{figure}\begin{lstlisting}{}
declare
type T_Table is array (Natural range...
...1 .. 3 => Empty)); -- 3 Controlled components.
end;
\end{lstlisting}\end{figure}

This example makes it clear that objects with controlled components must include some additional data-structures to keep track of their changeable controllable contents. In addition, such objects are not necessarily controlled themselves, so, the chaining mechanism must include some level of indirection to denote these objects, given that they do not have the link field of controlled objects. Arrays of controlled objects are yet another complication, because there is nowhere to place additional pointers to link the components.

12.1.5 Controlled Class-Wide Objects

Type extensions can introduce additional controlled components. Given that a class-wide object can denote any descendant of a given type, we must assume that in general it may include controlled components, even if the ancestor type does not. This forces the compiler to make a worst-case assumption for class-wide objects and parameters. Consider the following case:

\begin{figure}\begin{lstlisting}{}
package Test is
type T is tagged null record...
...ntaining controlled components?
begin
...
end Try;
\end{lstlisting}\end{figure}

The expanded code must assume that Try is a scope that needs finalization. Therefore it must create a finalization list, and generate code to attach the anonymous object returned by the call to F to this list, in some indirect fashion because the object might not be controlled after all.


12.2 Expansion Activities for Controlled-Types

For each block that contains objects, the expander generates a Finalization Chain. When a controlled object is elaborated, it is first Initialized or Adjusted (depending on whether an initial value was present or not), then attached at the beginning of this chain. For example, let us assume the following declarations:

\begin{figure}\begin{lstlisting}{}
declare
X : Some_Controlled_Type;
Y : Some_...
...d_Type := X;
begin
<< Additional user code >>
end;
\end{lstlisting}\end{figure}

This fragment is expanded as follows:

\begin{figure}\begin{lstlisting}{}
declare
F : GNARL.Finalizable_Ptr;
begin
X ...
... user code >>
at end
GNARL.Finalize_List (F);
end;
\end{lstlisting}\end{figure}

Finalizable_Ptr is an access to the class representing all controlled objects. Since objects are inserted at the beginning of the list, the ordering of the chain is exactly correct for the required sequence of finalization actions. The fact that the chain is built dynamically ensures that only successfully elaborated objects are dealt with in case of exceptional exit. Upon scope exit, the at-end statement ensures that Finalize_List is called whether the scope was successfully executed or not. Finalize_List is a run-time subprogram that finalizes all objects on the list, by dispatching to the Finalize procedure of each. The list is of course heterogeneous because Finalize_Ptr is an access-to-class-wide type, and any object whose type is derived from Controlled can be attached to this list.


12.2.1 Expansion of Assignment

At a first sight, the expansion of the the assignment statement Obj1 := Obj2 might be:

\begin{figure}\begin{lstlisting}{}
Finalize (Obj1); -- discard old value
Obj1...
...t (Obj1); -- remove accidental sharing on new value
\end{lstlisting}\end{figure}

However, various problems make such an implementation unworkable. First, Obj1 may refer to objects present in Obj2 and thus cannot be finalized before Obj2 is evaluated. Second, the assignment itself must be specialized since copying the hidden pointers that attach objects to finalization lists is clearly nonsensical. Third, the self-assignment (X := X), although not a particularly useful construct, does not work, because it would finalize the target of the assignment as well. This case must be addressed specially, either by introducing a temporary object or by avoiding the execution of any finalization actions. Thus, the front-end expands assignment as follows, which works in the general case and can be often be optimized:

\begin{figure}\begin{lstlisting}{}
Anon1 : Some_Controlled_Type renames Obj1;
An...
... (Anon2.all, to => Anon1);
Adjust (Anon1);
end if;
\end{lstlisting}\end{figure}

Note that the target object, even though it has been finalized, remains in the finalization list because it still need to be finalized upon scope exit. In general finalization is idempotent, i.e. finalizing an object twice is a no-op.


12.2.2 Expansion of Anonymous Controlled Objects

Some constructs such as aggregates and functions generate anonymous objects that are part of some enclosing expression or construct. When such objects are controlled, they must be finalized as soon as they are no longer needed, that is to say before the beginning of the next statement. The GNAT expander generates transient blocks to handle anonymous objects; these blocks are placed around the construct that uses the intermediate objects. Such blocks will contain the declaration of a finalization list, and will cause the generation of finalization code as for user-declared constructs. Consider the previous example: function Empty yields a controlled value that is only used during the execution of Exists:

\begin{figure}\begin{lstlisting}{}
X := Exists (1, Inside => Empty);
\end{lstlisting}\end{figure}

GNAT expands this code as follows:

\begin{figure}\begin{lstlisting}{}
declare
Anon : Some_Controlled_Type := Empty;
begin
X := Exists (1, Inside => Anon);
end;
\end{lstlisting}\end{figure}

An intermediate block can be introduced without changing the semantics of the program in order to make the anonymous object and the corresponding finalization list explicit. This new block contains a controlled object and thus will be expanded using the scheme discussed above (cf. Section 12.2). The same mechanism can be extended to deal with anonymous objects that appear in flow-of-control structures (such as if and while statements).

The problem is a bit more complex when controlled anonymous objects appear in a declaration, since blocks are not allowed in such a context. To handle this case, the anonymous object is attached to an intermediate finalization list which is finalized right after the declaration. For example:

\begin{figure}\begin{lstlisting}{}
declare
B : Boolean := Exists (1, Empty);
begin
...
end;
\end{lstlisting}\end{figure}

It is expanded into:

\begin{figure}\begin{lstlisting}{}
declare
Aux_L : GNARL.List_Controller;
Ano...
...ze here, not at the
-- end of the block
...
end;
\end{lstlisting}\end{figure}

List_Controller is itself a controlled type. Thus, an object of that type is attached to the enclosing scope's finalization chain, ensuring that the anonymous object will be finalized even if an exception is raised between its definition and the finalize call. In the normal case, the List_Controller is finalized twice, once right after the declaration, and once again upon scope exit. Therefore the run-time Finalize routine makes sure that the second finalization has no effect.


12.2.3 Objects with Controlled Components

Composite type such as records and arrays can contain controlled components, and the expander must take care of calling the proper Initialize, Adjust and Finalize routines on their components. For this purpose the expander generates implicit procedures called _Deep_Initialize, _Deep_Adjust and _Deep_Finalize that are used in a manner similar to their counterparts for regular controlled types. These procedures are specialized according as to whether they handle records or arrays. Here is the body of _Deep_Adjust for a type T that is a one-dimensional array of controlled objects:

\begin{figure}\begin{lstlisting}{}
procedure _Deep_Adjust (V : in out T;
C : Fi...
...t (C, V (J));
end if;
end loop;
end _Deep_Adjust;
\end{lstlisting}\end{figure}

Note that the deep procedures have a conditional mechanism to attach objects to the finalization chain so that the same procedure can be used in a context where attachment is required, such as explicit initialization, as well as when it is not needed, such as in the assignment case. Note also the recursive nature of the above definition: Deep_Adjust on an array is defined in term of Deep_Adjust of its components. Ultimately, if the component type is a simple controlled type with no controlled components Deep_Adjust ends up just begin a call to the user-defined Adjust subprogram.

A similar approach could have been used for records. In that case, deep procedures would have been implicitly defined to perform the finalization actions on the controlled components in the right order, depending of the structure of the type itself. The controlled components would have been stored on the finalization list of the enclosing scope. Unfortunately such a model makes the assignment of mutable objects quite difficult: the number of objects on the finalization list may be different before and after the assignment, so all the controlled components of the target would need to be removed from it before the assignment and afterwards put back at the same place on the list. To avoid such a problem as well as to simplify the definition of deep procedures for records a different approach has been used. Records are considered as scopes and they have their own internal finalization chain on which all controlled components are chained. This is achieved by inserting a hidden Record_Controller component within the record itself. For example:

\begin{figure}\begin{lstlisting}{}
type Rec (N : Index := 0) is record
_Control...
....Record_Controller;
T : Sets (1 .. N);
end record;
\end{lstlisting}\end{figure}

Record_Controller plays a role equivalent to List_Controller: it introduces an indirection in the enclosing finalization list. The finalization list of controlled components is local to the object. So, upon assignment the number of controlled components may vary without affecting the enclosing finalization list. This provides a simple solution to the mutable record problem.

Class-wide objects present a interesting challenge since the compiler doesn't know how many, if any, controlled components are present in such objects. To address this problem, class-wide types are considered ``potentially'' controlled and calls to the deep procedures are always generated for initializations and assignments. Dispatching is used to ensure that the appropriate deep procedure is called.

12.3 Summary

Controlled-types introduce interesting implementation problems that impose a close cooperation between compile-time and run-time activities. The expander generates declarations for data structures at the scope level and at the type level, that are used to create run-time lists that hold controlled objects. The expander also generates calls to initialization and finalization routines. The run-time includes general purpose finalization routines that traverse these lists and dispatch to type-specific finalization operations. The expander adds blocks around the use of anonymous controlled objects, to ensure that they are finalized in a timely fashion. The resulting mechanism handles dynamically allocated objects and objects with controlled components as well.



Footnotes

...Controlled-types12.1
The contents of this chapter are based on the paper [CDG95].

next up previous contents index
Next: 13. Expansion of Tagged-Types Up: III. Third Part: Expansion Previous: 11. Expansion of Protected   Contents   Index
(C) Javier Miranda and Edmond Schonberg, 2004