John Barnes

# 4.2 Mutually dependent types

For many programmers the solution of the problem of mutually dependent types will be the single most important improvement introduced in Ada 2005.
This topic was discussed in the Introduction using an example of two mutually dependent types, Point and Line. Each type needed to refer to the other in its declaration and of course the solution to this problem is to use incomplete types. In Ada 95 there are three stages. We first declare the incomplete types
type Point;    -- incomplete types
type Line;
Suppose for simplicity that we wish to study patterns of points and lines such that each point has exactly three lines through it and that each line has exactly three points on it. (This is not so stupid. The two most fundamental theorems of projective geometry, those of Pappus and Desargues, concern such structures and so does the simplest of finite geometries, the Fano plane.)
Using the incomplete types we can then declare
type Point_Ptr is access Point;    -- use incomplete types
type Line_Ptr is access Line;
and finally we can complete the type declarations thus
type Point is    -- complete the types
record
L, M, N: Line_Ptr;
end record;
type Line is
record
P, Q, R: Point_Ptr;
end record;
Of course, in Ada 2005, as discussed in the previous chapter (see 3.3), we can use anonymous access types more freely so that the second stage can be omitted in this example. As a consequence the complete declarations are simply
type Point is    -- complete the types
record
L, M, N: access Line;
end record;
type Line is
record
P, Q, R: access Point;
end record;
This has the important advantage that we do not have to invent irritating identifiers such as Point_Ptr.
But we will stick to Ada 95 for the moment. In Ada 95 there are two rules
the incomplete type can only be used in the definition of access types;
the complete type declaration must be in the same declarative region as the incomplete type.
The first rule does actually permit
type T;
type A is access procedure (X: in out T);
Note that we are here using the incomplete type T for a parameter. This is not normally allowed, but in this case the procedure itself is being used in an access type. The additional level of indirection means that the fact that the parameter mechanism for T is not known yet does not matter.
Apart from this, it is not possible to use an incomplete type for a parameter in a subprogram in Ada 95 except in the case of an access parameter. Thus we cannot have
function Is_Point_On_Line(P: Point; L: Line) return Boolean;
before the complete type declarations.
It is also worth pointing out that the problem of mutually dependent types (within a single unit) can often be solved by using private types thus
type Point is private;
type Point_Ptr is access Point;
type Line is private;
type Line_Ptr is access Line;
private
type Point is
record
L, M, N: Line_Ptr;
end record;
type Line is
record
P, Q, R: Point_Ptr;
end record;
But we need to use incomplete types if we want the user to see the full view of a type so the situation is somewhat different.
As an aside, remember that if an incomplete type is declared in a private part then the complete type can be deferred to the body (this is the so-called Taft Amendment in Ada 83). In this case neither the user nor indeed the compiler can see the complete type and this is the main reason why we cannot have parameters of incomplete types whereas we can for private types.
We will now introduce what has become a canonical example for discussing this topic. This concerns employees and the departments of the organization in which they work. The information about employees needs to refer to the departments and the departments need to refer to the employees. We assume that the material regarding employees and departments is quite large so that we naturally wish to declare the two types in distinct packages Employees and Departments. So we would like to say
with Departments; use Departments;
package Employees is
type Employee is private;
procedure Assign_Employee(E: in out Employee; D: in out Department);
type Dept_Ptr is access all Department;
function Current_Department(E: Employee) return Dept_Ptr;
...
end Employees;
with Employees; use Employees;
package Departments is
type Department is private;
procedure Choose_Manager(D: in out Department; M: in out Employee);
...
end Departments;
We cannot write this because each package has a with clause for the other and they cannot both be declared (or entered into the library) first.
We assume of course that the type Employee includes information about the Department for whom the Employee works and the type Department contains information regarding the manager of the department and presumably a list of the other employees as well – note that the manager is naturally also an Employee.
So in Ada 95 we are forced to put everything into one package thus
package Workplace is
type Employee is private;
type Department is private;
procedure Assign_Employee(E: in out Employee; D: in out Department);
type Dept_Ptr is access all Department;
function Current_Department(E: Employee) return Dept_Ptr;
procedure Choose_Manager(D: in out Department; M: in out Employee);
private
...
end Workplace;
Not only does this give rise to huge cumbersome packages but it also prevents us from using the proper abstractions. Thus the types Employee and Department have to be declared in the same private part and so are not protected from each other's operations.
Ada 2005 solves this by introducing a variation of the with clause – the limited with clause. A limited with clause enables a library unit to have an incomplete view of all the visible types in another package. We can now write
limited with Departments;
package Employees is
type Employee is private;
procedure Assign_Employee(E: in out Employee; D: access Departments.Department);
type Dept_Ptr is access all Departments.Department;
function Current_Department(E: Employee) return Dept_Ptr;
...
end Employees;
limited with Employees;
package Departments is
type Department is private;
procedure Choose_Manager(D: in out Department; M: access Employees.Employee);
...
end Departments;
It is important to understand that a limited with clause does not impose a dependence. Thus if a package A has a limited with clause for B, then A does not depend on B as it would with a normal with clause, and so B does not have to be compiled before A or placed into the library before A.
If we have a cycle of packages we only have to put limited with on one package since that is sufficient to break the cycle of dependences. However, for symmetry, in this example we have made them both have a limited view of each other.
Note the terminology: we say that we have a limited view of a package if the view is provided through a limited with clause. So a limited view of a package provides an incomplete view of its visible types. And by an incomplete view we mean as if they were incomplete types.
In the example, because an incomplete view of a type cannot generally be used as a parameter, we have had to change one parameter of each of Assign_Employee and Choose_Manager to be an access parameter.
Having broken the circularity we can then put normal with clauses for each other on the two package bodies.
There are a number of rules necessary to avoid problems. A natural one is that we cannot have both a limited with clause and a normal with clause for the same package in the same context clause (a normal with clause is now officially referred to as a nonlimited with clause). An important and perhaps unexpected rule is that we cannot have a use package clause with a limited view because severe surprises might happen.
To understand how this could be possible it is important to realise that a limited with clause provides a very restricted view of a package. It just makes visible
the name of the package and packages nested within,
an incomplete view of the types declared in the visible parts of the packages.
Nothing else is visible at all. Now consider
package A is
X: Integer := 99;
end A;
package B is
X: Integer := 111;
end B;
limited with A, B;
package P is
...    -- neither X visible here
end P;
Within package P we cannot access A.X or B.X because they are not types but objects. But we could declare a child package with its own with clause thus
with A;
package P.C is
Y: Integer := A.X;
end P.C;
The nonlimited with clause on the child "overrides" the limited with clause on the parent so that A.X is visible.
Now suppose we were allowed to add a use package clause to the parent package; since a use clause on a parent applies to a child this means that we could refer to A.X as just X within the child so we would have
limited with A, B;
use A, B;    -- illegal
package P is
...    -- neither X visible here
end P;
with A;
package P.C is
Y: Integer := X;    -- A.X now visible as just X
end P.C;
If we were now to change the with clause on the child to refer to B instead of A, then X would refer to B.X rather than A.X. This would not be at all obvious because the use clause that permits this is on the parent and we are not changing the context clause of the parent at all. This would clearly be unacceptable and so use package clauses are forbidden if we only have a limited view of the package.
Here is a reasonably complete list of the rules designed to prevent misadventure when using limited with clauses
a use package clause cannot refer to a package with a limited view as illustrated above,
limited with P; use P;    -- illegal
package Q is ...
the rule also prevents
limited with P;
package Q is
use P;    -- illegal
a limited with clause can only appear on a specification – it cannot appear on a body or a subunit,
limited with P;    -- illegal
package body Q is ...
a limited with clause and a nonlimited with clause for the same package may not appear in the same context clause,
limited with P; with P;    -- illegal
a limited with clause and a use clause for the same package or one of its children may not appear in the same context clause,
limited with P; use P.C;    -- illegal
a limited with clause may not appear in the context clause applying to itself,
limited with P;    -- illegal
package P is ...
a limited with clause may not appear on a child unit if a nonlimited with clause for the same package applies to its parent or grandparent etc,
with Q;
package P is ...
limited with Q;    -- illegal
package P.C is ...
but note that the reverse is allowed as mentioned above
limited with Q;
package P is ...
with Q;    -- OK
package P.C is ...
a limited with clause may not appear in the scope of a use clause which names the unit or one of its children,
with A;
package P is
package R renames A;
end P;
with P;
package Q is
use P.R;    -- applies to A
end Q;
limited with A;    -- illegal
package Q.C is ...
without this specific rule, the use clause in Q which actually refers to A would clash with the limited with clause for A.
Finally note that a limited with clause can only refer to a package declaration and not to a subprogram, generic declaration or instantiation, or to a package renaming.
We will now return to the rules for incomplete types. As noted above the rules for incomplete types are quite strict in Ada 95 and apart from the curious case of an access to subprogram type it is not possible to use an incomplete type for a parameter other than in an access parameter.
Ada 2005 enables some relaxation of these rules by introducing tagged incomplete types. We can write
type T is tagged;
and then the complete type must be a tagged type. Of course the reverse does not hold. If we have just
type T;
then the complete type T might be tagged or not.
A curious feature of Ada 95 was mentioned in the Introduction. In Ada 95 we can write
type T;
...
type T_Ptr is access all T'Class;
By using the attribute Class, this promises in a rather sly way that the complete type T will be tagged. This is strictly obsolescent in Ada 2005 and moved to Annex J. In Ada 2005 we should write
type T is tagged;
...
type T_Ptr is access all T'Class;
The big advantage of introducing tagged incomplete types is that we know that tagged types are always passed by reference and so we are allowed to use tagged incomplete types for parameters.
This advantage extends to the incomplete view obtained from a limited with clause. If a type in a package is visibly tagged then the incomplete view obtained is tagged incomplete and so the type can then be used for parameters.
Returning to the packages Employees and Departments it probably makes sense to make both types tagged since it is likely that the types Employee and Department form a hierarchy. So we can write
limited with Departments;
package Employees is
type Employee is tagged private;
procedure Assign_Employee(E: in out Employee; D: in out Departments.Department'Class);
type Dept_Ptr is access all Departments.Department'Class;
function Current_Department(E: Employee) return Dept_Ptr;
...
end Employees;
limited with Employees;
package Departments is
type Department is tagged private;
procedure Choose_Manager(D: in out Department; M: in out Employees.Employee'Class);
...
end Departments;
The text is a bit cumbersome now with Class sprinkled liberally around but we can introduce some subtypes in order to shorten the names. We can also avoid the introduction of the type Dept_Ptr since we can use an anonymous access type for the function result as mentioned in the previous chapter (see 3.3). So we get
limited with Departments;
package Employees is
type Employee is tagged private;
subtype Dept is Departments.Department;
procedure Assign_Employee(E: in out Employee; D: in out Dept'Class);
function Current_Department(E: Employee) return access Dept'Class;
...
end Employees;
limited with Employees;
package Departments is
type Department is tagged private;
subtype Empl is Employees.Employee;
procedure Choose_Manager(D: in out Department; M: in out Empl'Class);
...
end Departments;
Observe that in Ada 2005 we can use a simple subtype as an abbreviation for an incomplete type thus
subtype Dept is Departments.Department;
but such a subtype cannot have a constraint or a null exclusion. In essence it is just a renaming. Remember that we cannot have a use clause with a limited view. Moreover, many projects forbid use clauses anyway but permit renamings and subtypes for local abbreviations. It would be a pain if such abbreviations were not also available when using a limited with clause.
It's a pity we cannot also write
subtype A_Dept is Departments.Department'Class;
but then you cannot have everything in life.
A similar situation arises with the names of nested packages. They can be renamed in order to provide an abbreviation.
The mechanism for breaking cycles of dependences by introducing limited with clauses does not mean that the implementation does not check everything thoroughly in a rigorous Ada way. It is just that some checks might have to be deferred. The details depend upon the implementation.
For the human reader it is very helpful that use clauses are not allowed in conjunction with limited with clauses since it eliminates any doubt about the location of types involved. It probably helps the poor compilers as well.
Readers might be interested to know that this topic was one of the most difficult to solve satisfactorily in the design of Ada 2005. Altogether seven different versions of AI-217 were developed. This chosen solution is on reflection by far the best and was in fact number 6.
A number of loopholes in Ada 95 regarding incomplete types are also closed in Ada 2005.
One such loophole is illustrated by the following (this is Ada 95)
package P is
...
private
type T;    -- an incomplete type
type ATC is access all T'Class;    -- it must be tagged
X: ATC;
procedure Op(X: access T);    -- primitive operation
...
end P;
The incomplete type T is declared in the private part of the package P. The access type ACT is then declared and since it is class wide this implies that the type T must be tagged (the reader will recall from the discussion above that this odd feature is banished to Annex J in Ada 2005). The full type T is then declared in the body. We also declare a primitive operation Op of the type T in the private part.
However, before the body of P is declared, nothing in Ada 95 prevents us from writing a private child thus
private package P.C is
procedure Naughty;
end P.C;
package body P.C is
procedure Naughty is
begin
Op(X);    -- a dispatching call
end Naughty;
end P.C;
and the procedure Naughty can call the dispatching operation Op. The problem is that we are required to be able to compile this call before the type T is completed and thus before the location of its tag is known.
This problem is prevented in Ada 2005 by a rule that if an incomplete type declared in a private part has primitive operations then the completion cannot be deferred to the body.
type T;
type A is access procedure (X: in out T);
In Ada 2005, the completion of T cannot be deferred to a body. Nor can we declare such an access to subprogram type if we only have an incomplete view of T arising from a limited with clause.
Another change in Ada 2005 can be illustrated by the Departments and Employees example. We can write
limited with Departments;
package Employees is
type Employee is tagged private;
procedure Assign_Employee(E: in out Employee; D: in out Departments.Department'Class);
type Dept_Ptr is access all Departments.Department'Class;
...
end Employees;
with Employees; use Employees;
procedure Recruit(D: Dept_Ptr; E: in out Employee) is
begin
Assign_Employee(E, D.all);
end Recruit;
Ada 95 has a rule that says "thou shalt not dereference an incomplete type". This would prevent the call of Assign_Employee which is clearly harmless. It would be odd to require Recruit to have a nonlimited with clause for Departments to allow the call of Assign_Employee. Accordingly the rule is changed in Ada 2005 so that dereferencing an incomplete view is only forbidden when used as a prefix as, for example, in D'Size.

© 2005, 2006, 2007 John Barnes Informatics.