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

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;

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;

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 first rule does actually permit

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

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

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

Nothing else is visible at all. Now consider

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

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;

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

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

and then the complete type must be a tagged type. Of course the reverse does not hold. If we have just

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

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

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

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

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

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 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.

Similar problems arise with access to subprogram types. Thus, as mentioned above, Ada 95 permits

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

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.

Rationale for Ada 2005

4.2 Mutually dependent types