A generic unit is a parameterized template for a subprogram or package whose parameters can be types, variables, subprograms and packages. Generic units must be instantiated, by suppling specific actuals for the parameters. Each instantiation conceptually creates a copy of the specification and body of the generic unit, which are appropriately customized by the actual parameters.
The semantics of Ada specify that the legality of generic templates is established at the point of declaration of the generic, and not at the point of instantiation. Therefore, a generic unit must be fully analyzed at the place it appears. For an instantiation, the main legality checks involve verifying that the actuals provided in the instance match the generic formal parameters. The so-called ``contract model'' [AAR95, Section 12.3.1(a)] states that if the generic declaration is legal, and the actuals match the formals, then the instantiation is known to be legal, and semantic checks need not be performed on it.
The legality checks on a generic unit are similar to those of a regular, non-generic unit. They mainly involve name resolution and type checking. Given that the semantics of the generic are established at the point of definition, name resolution involves global name capture: a reference to an entity that is external to the generic is established when the generic is analyzed, and must be retained for each instantiation. On the other hand, entities local to the generic will have a different meaning in each instance.
Traditionally, there are two implementation techniques for generic instantiation [SB94]: in-line expansion (often called Macro Expansion) and direct compilation of generic units (also known as Shared Generics). The latter model is known to be fraught with difficulties and GNAT, like most other compilers, implements generics by expansion. Therefore, each instantiation of a given generic produces a copy of the generic code, suitably decorated with semantic information from captured global entities and actual parameters. Note that this is quite distinct from the macro-expansion of older programming languages, which is typically a pure textual substitution with no semantic legality checks on the macro itself.
After analysis, a generic unit contains partial semantic information. At the point of instantiation, the semantic information must be completed. This does require a full pass of semantic analysis over the instance. In addition, code expansion must be performed. Note that expansion cannot be performed on the generic itself, because expansion typically depends on type information that is not available until the actual types are known. Given that semantic analysis and expansion are inextricably linked in GNAT, we must perform full semantic analysis of the instance, even though the contract model would indicate that some of it is superfluous.
The requirements of global name capture determine the architecture described in this chapter. This architecture is complicated by two related aspects of Ada: nested generic units (and instantiations within generic units) and generic child units. In addition, private types complicate visibility analysis and require some special machinery to insure that name resolution is consistent between the point of generic definition and the points of instantiation.
This chapter is structured as follows: Section 7.1 presents the main details of the GNAT approach to the analysis and instantiation of simple generic units. This section also describes parameter matching and private types handling. Section 7.2 discusses the analysis and instantiation of nested generic units; Section 7.3 presents the analysis and instantiation of generic child units; Section 7.4 describes the instantiation of bodies in a separate phase, and Section 7.5 briefly discusses the mechanisms used to detect instantiation circularities. We close with a brief summary of the contents of this chapter.
Generic specifications are analyzed wherever they appear. If a generic unit is mentioned in a context clause of some unit U, it is analyzed before the unit U itself. The result of this analysis is an Abstract Syntax Tree (AST) annotated with partial semantic information. The analysis of a generic package or subprogram specification involves the following sequence of actions:
At the point of generic instantiation, the original generic tree for the generic unit is copied, and the relevant semantic information from the copy is retrieved and added to it (cf. Figure 7.4). The new tree is treated as a regular (non-generic) unit which is analyzed and for which code is now generated. Non-local references are not analyzed anew (name resolution does not modify an entity reference that already denotes an entity, see Find_Direct_Name). To each local entity in the generic there corresponds a local entity in each instance, and name resolution for these is performed as for non-generic units.
The conventional model of instantiation is to replace each reference to a formal parameter by a reference to the matching actual. This is usually carried out by establishing a mapping from one set to the other, and applying this mapping to a copy of the generic template. This mapping approach is complex and expensive when nested generics are present, and GNAT follows a different approach, which closely reflects the semantics of instantiation. To indicate that a reference to a formal type is really a reference to the actual, the front-end inserts renaming declarations within the instance so that any use of the name of a formal resolves to the corresponding actual. The nature of the renaming declaration depends on the generic parameter: object, type, formal subprogram or formal package. Thanks to this mechanism, the analysis of the instance can proceed as if the copy had been inserted literally at the point of instantiation, even though the visibility environment at this point bears no relation to the visibility at the point of generic declaration.
To give the right visibility to the entities introduced by these renamings, GNAT uses a different scheme for package and subprogram instantiations:
The GNAT front-end generates the AST equivalent of the following code for the instantiation:
Line (1) is the constant declaration corresponding to the in parameter; line (2) is the renaming of the in out parameter; line (3) is the subtype declaration used to rename the generic formal type T_Data. Finally, line (4) introduces a renaming for the generic unit itself. This corresponds to the fact that within the generic, the name of the generic denotes the name of the current instance. The need for this last renaming is made evident by the declaration in line (5), which references a type that is originally local to the generic, and now designates a type local to the current instance.
In this case the GNAT front-end carries out the following transformation:
Line (5) is the subprogram renaming which makes the subprogram visible in the current scope. The reader should note that this renaming declaration can not be replaced by an Ada use_clause on the wrapper package, because this would render visible all the renamings associated with formal parameters (not only the instantiated subprogram), which would be illegal.
If the subprogram instantiation is a compilation unit, the front-end gives the wrapper package the name of the subprogram instance. This ensures that the elaboration procedure called by the GNAT Binder, using the compilation unit name, calls in fact the elaboration procedure for the package.
The analysis of a generic unit leaves all non-local references decorated to ensure that the proper entity is referenced to in the instantiations (cf. Section 7.1.1). However, for private types this by itself does not insure that the proper View of the entity is used (the full type may be visible at the point of generic definition, but not at instantiation time, or vice-versa). To solve this problem the semantic analyzer saves both views. At time of instantiation, the front-end checks which view is required, and exchanges declarations, if necessary, to restore the correct visibility. (cf. Chapter 4). After completing the instantiation, the front-end restores the current visibility.
The model presented in the previous section extends naturally to nested generics. If a generic unit G2 is nested within G1, the analysis of G1 generates a copy CG1 of the tree for G1. Later, when G2 is analyzed, the front-end makes a copy CG2 of the tree for G2, and establishes links between this copy and the original tree for G2 within CG1. An instantiation of G2 within G1 will use the information collected in CG2. To see this in detail, consider the scheme in Figure 7.5 (Ada elements which reference entities in the AST have been emphasized in Figure 7.5 with bold letters).
This example shows a non-generic package (Example) with two nested generic packages (Gen_Pkg_1 and Gen_Pkg_2). Data type T_Global is external (global) to the generic packages; data type T_Semi_Global is local to Gen_Pkg_1 but external to Gen_Pkg_2. In addition, some objects of these data types are created in each generic package (A_1, B_1, A_2, B_2 and C_2).
To do the semantic analysis of Gen_Pkg_1 the GNAT front-end makes a copy of its AST and links the nodes which reference entities with their copy (cf. Figure 7.6). The semantic analysis of Gen_Pkg_1 captures all occurrences of local and non-local entities (see the arrows from A_1 to T_Global, and from B_1 to T_Semi_Global).
To analyze Gen_Pkg_2 the front-end repeats the process: makes a new copy of Gent_Pkg_2 AST and links the nodes which reference entities with their new copy (cf. Figure 7.7). Again, its semantic analysis captures all occurrences of local and non-local entities.
After the analysis of the nested generic units the front-end removes all the local references in the original copy of the nested generic units (cf. Left side in Figure 7.8). References to T_Semi_Global are not preserved because, in the general case, they may depend on generic formal parameters of G1.
If a generic unit G2 is nested within G1, the Ada programmer must first instantiate G1 (say IG1) and then instantiate the nested generic unit G2 which is inside IG1.The instantiation of G1 produces a full copy of its AST, including the inner generic G2.
Continuing with our previous example, let us consider the following instances of our generic packages Gen_Pkg_1 and Gen_Pkg_2:
At point 1 (instantiation of Gen_Pkg_1), the analysis of this instantiation includes the analysis of the nested generic, which produces a generic copy of Gen_Pkg_2, which will include global references to entities declared in the instance. The instantiation at point 2 requires no special treatment (the front-end produces a copy of the generic unit Gen_Pkg_2 in the instance My_Pkg_1 and instantiates it as usual).
Figure 7.9 presents the resulting code for this example. The Ada source lines which instantiate the generic units have been kept in the figure as Ada comments to help the reader see the corresponding instantiation (inside dotted rectangles). The first dotted rectangle is the instantiation of My_Pkg_1; the second dotted rectangle is the instantiation of the generic unit in the instance My_Pkg_1.
The analysis of generic child units adds no additional complexity to the mechanisms described in the previous sections. Conceptually the child unit has an implicit with_clause to its parents. Therefore the analysis of a generic child unit recursively loads and analyzes its parents. For example, to analyze R (child of P.Q) the front-end loads and analyzes P, then Q and finally R. This is identical to what is done for non-generic units. Of course, the analysis of the generics ends with the recovery of global names. References to entities declared in a generic ancestor are not preserved, because at instantiation time they will resolve to the corresponding entities declared in the instance of the ancestor.
Let us assume P is a generic library package, and P.C is a generic child package of P. Conceptually, an instance I of P is a package that contains a nested generic unit called I.C[AAR95, Section 10.1.1(19)]. A generic child unit can only be instantiated in the context of an instantiation of its parent, because of course it will in general depend on the actuals and the local entities of the parent. This clause of the RM simply indicates that a partially parameterized child generic unit is implicitly declared within the instantiation of the parent. Nevertheless, given that library packages are in general written in separate source files (this is mandatory in the GNAT compilation model [Dew94]), the compilation of P does not really contain information concerning I.C, and the front-end must handle generic child units with care to find the proper sources. Let us examine this mechanism in detail, and indicate how the proper visibility is established at the point of instantiation.
The RM paragraph just quoted allows generic child units to be instantiated both as local packages and as independent compilation units. A common idiom is to have an instantiation hierarchy that duplicates the generic hierarchy, but it is also possible to instantiate several members of a generic hierarchy within a common scope. Let us consider the following generic units in each case:
First note that the name of the generic unit in the second instance (line 5) is that of the implicit child in the instance of the parent, and not that of generic child unit that was actually analyzed. The first step in processing the instantiation is to retrieve the name of the generic parent, and from there to recognize that the child unit that we are about to instantiate is Parent.Child.
To analyze the instantiation of Parent.Child, we must place the tree for this unit in the context of the instantiation of the Parent. This is so that a name in the child that resolved to an entity in the parent will now resolve to an entity in the instance of the parent. As a result, after producing the required copy of the analyzed generic unit for Parent.Child, the front-end places Parent_Instance on the scope stack. The analysis of the child instance will now resolve correctly. After analysis, the front-end removes Parent_Instance from the scope stack, to restore the proper environment for the rest of the declarative part.
The RM rule requires that the parent instance be visible at the point of instantiation of the child, so it must appear in a with_clause of the current unit, together with a with_clause for the generic child unit itself.
The with_clause for the child (line 1) makes the implicit child visible within the instantiation of the parent [Bar95, Section 10.1.3]. The instantiation at line 3 names this implicit child.
Using a similar approach to the previous case, the front-end retrieves the generic parent, verifies that a child unit of the given name is present in the context, and retrieves the analyzed generic unit. Its analysis must again be performed in the scope of the parent instance. Even though the parent instance was separately compiled, all semantic information is available because it appears in the context. Therefore the front-end places it on the scope stack (as before), and performs the analysis the child instance, after which the parent instance is unstacked.
Clearly, more that one ancestor may be involved, and all of them have to be placed on the scope stack in the proper order before analyzing the child instance.
Figure 7.10 represents the sequence followed by the GNAT front-end to instantiate Child_Instance (according to our previous example):
The front-end instantiates generic bodies in a separate pass, after it completes all semantic analysis of the main unit. By delaying the instantiation of bodies, GNAT is able to compile legal programs that include cross-dependences among several package declarations and bodies. Such dependences present difficult problems in the order of elaboration to other compilers. For example, consider the following Ada code:
Conventional compilation schemes either reject these instantiations as circular (even though they are not) or are forced to use an indirect linking approach to the instances, which is inefficient. In GNAT, the instantiated bodies are placed in-line in the tree. This can only be done after regular semantic analysis of the main unit is completed. Up to that point, only the declarations of instances have been created and analyzed. It is worth noting that instantiations can appear before the corresponding generic body, which indicates that the body of the corresponding instance cannot be place at the same place as its specification, because it may depend on entities defined after the point of instantiation. In that case, a delicate analysis is required to locate the correct point at which an instance body must be inserted.
A circular chain of instantiations is a static error which must be detected at compile time. The detection of these circularities is carried out at the point that the front-end creates a generic instance specification or body. The circularity is detected using one of several strategies. If there is a circularity between two compilation units, where each contains an instance of the other, then the analysis of the offending unit will eventually result in trying to load the same unit again, and the parser detects this problem as it analyzes the package instantiation for the second time. If a unit contains an instantiation of itself, the front-end detects the circularity by noticing that the scope stack currently holds another instance of the generic. If the circularity involves subunits, it is detected using a local data structure that lists, for each generic unit, the instances that it declares.
A generic unit is essentially a macro for a subprogram or package, whose parameters can be types, variables, subprograms and packages. Generic units must be instantiated, by suppling specific actuals for the parameters. This conceptually creates a copy of the specification and body which are appropriately customized.
There are two main implementation techniques for generic instantiation known as Macro Expansion and Shared Generics. GNAT implements generics by expansion. Because the GNAT compilation model generates neither code nor intermediate representation in case of generic specifications, they are analyzed each time they are found in an Ada context clause. This analysis involves the creation of a copy of the fragment of the AST corresponding to the generic specification. The front-end analyzes this copy and updates in the original fragment of the AST all the non-local references to entities (the modified original tree). For each instance of the generic unit the front-end generates a new copy of this modified fragment of the AST, adds some renaming declarations to handle actual parameters, and analyzes and expands this copy. The GNAT front-end incorporates extensions to this mechanism to analyze and instantiate nested generic units and generic child units.