Gem #128 : Iterators in Ada 2012 - Part 2
Let's get started...
In Part 1, we discussed the basic forms of iterators in Ada 2012 and gave some simple examples. This part goes into greater detail, showing how to create iterators for your own data structures. We'll start by learning about two supporting features introduced in Ada 2012.
The first is the new generic package Ada.Iterator_Interfaces. This package defines two abstract types Forward_Iterator and Reverse_Iterator. The intent is that each container should declare extensions of these and provide concrete implementations for their primitive operations. Briefly, an iterator encapsulates a cursor and a container, and hides the First, Has_Element, and Next operations.
The second new feature is that of a reference type. A reference type is a record with an access discriminant that defines the "Implicit_Dereference" aspect. This is the actual type manipulated by the container element iterators, and the aspect eliminates the need to write ".all" every time an element is referenced.
Here is an example of such a declaration, taken from the standard package Ada.Containers.Doubly_Linked_Lists:
type Constant_Reference_Type
(Element : not null access constant Element_Type)
is private with Implicit_Dereference => Element;Whenever we have such a reference, for example E of type Constant_Reference_Type, we can just use the name "E", and this is automatically interpreted as "E.Element.all". Another advantage of this type over a simple access to element is that it ensures the user cannot accidentally free the element.
Now that we understand what iterators and references are, we can start applying them to our own data structures.
Let's assume we are creating our own data structure (such as a graph, a queue, or anything that is not a direct instantiation of an Ada 2005 container). The following examples are framed as a "list", but this really applies to any data structure. Let's also assume that the container holds unconstrained elements of type "T'Class", giving us a more realistic and interesting example than the Part 1 example that just contained Integers.
To provide iterators for this data structure, we need to define a number of Ada 2012 aspects, described in more detail below.
type T is tagged null record; -- any type
type T_List is ... -- a structure of such types
with Default_Iterator => Iterate,
Iterator_Element => T'Class,
Constant_Indexing => Element_Value;
type Cursor is private;
function Has_Element (Pos : Cursor) return Boolean;
-- As for Ada 2005 containers
package List_Iterators is
new Ada.Iterator_Interfaces (Cursor, Has_Element);
function Iterate (Container : T_List)
return List_Iterators.Forward_Iterator'Class;
-- Returns our own iterator, which in general will be defined in the
-- private part or the body.
function Element_Value (Container : T_List; Pos : Cursor)
return T'Class;
-- Could also return a reference type as defined in the Part 1 Gem
For those unfamiliar with aspects in Ada 2012, it's worth noting that they can be forward references: in the case above, for instance, the aspect "Default_Iterator" is defined before Iterate is declared (and we could not declare it first in any case, since the function Iterate needs to know about T_List).
To understand the aspects, let's look at how the generalized iterators are expanded by the compiler.
This loop:
for C in List.Iterate loop -- C is a cursor
declare
E : T'Class := Element (C);
begin
...
end;
end loop;
is expanded into:
declare
Iter : Forward_Iterator'Class :=
List.Iterate; -- Default_Iterator aspect
C : Cursor := Iter.First; -- Primitive operation of iterator
begin
while Has_Element (C) loop -- From Iterator_Interfaces instance
declare
E : T'Class := List.Element_Value (C);
-- Constant_Indexing aspect
begin
...
end;
C := Iter.Next (C); -- Primitive operation of iterator
end loop;
end;
The subprogram Iterate, referenced in the "Default_Iterator" aspect, creates and returns a new iterator. In general, it will also hold a reference to the container itself to ensure the container lives at least as long as the iterator.
The iterator is then used to get and manipulate a cursor. Retrieving an element from the cursor is done via the function defined in the "Constant_Indexing" aspect. (A similar aspect "Variable_Indexing" is used when the loop needs to write the element, but we will not demonstrate that here.)
The function Element_Value is written here in its simplest form: it directly returns a copy of the element contained in the data structure. We could choose instead to return a reference type as explained in the Part 1 Gem, to avoid copies of the elements. (Note that in the case of Variable_Indexing, the function's result type must be a reference type.)
The container element iterators are expanded similarly. The only difference is that the cursor C is not visible.
For the actual implementation of Iterate and Element_Value, we recommend looking at the implementation for the standard containers, such as Doubly_linked_Lists. All of the Ada 2005 containers were enhanced to support iterators, and these provide various examples of code that can be reused for your own applications.
Finally, let's look at a code pattern that might be useful. The test case is the following: we have implemented a complex data structure that contains elements of type T'Class. When we use the container element iterators, E is thus of type T'Class, which we can express with the following syntax:
for E : T'Class of List loop
...
end loop;
Now let's consider a type TChild that extends T. We can still store elements of type TChild in the data structure, but we then need explicit conversions in the loop above to cast E to TChild'Class. We would like to minimize the amount of code needed to create a container that holds TChild'Class elements. For instance:
type TChild_List is <see full type below>;
Child_List : TChild_List;
for E of Child_List loop
-- E is of type TChild'Class, so no conversion is needed.
end loop;
Of course, one possibility is to make our container generic and instantiate it once for T'Class, once for TChild'Class, and so on. That's certainly a minimal amount of Ada source code, but it can still represent a significant amount of compiled code and will increase the size of the final executable. In fact, we can simply mirror the T / TChild hierarchy in the containers themselves and redefine only a minimal number of aspects to achieve the goal.
type TChild_List is new T_List with null record
with Constant_Indexing => Child_Value,
Default_Iterator => Iterate, -- inherited from T_List
Iterator_Element => TChild'Class;
function Child_Value (Self : TChild_List; Pos : Cursor'Class);
return TChild'Class is
begin
return TChild'Class (Element_Value (Self, Pos));
end Child_Value;
The amount of additional code is minimal (just one extra function, which is likely to be inlined), and now we can write the container element loop with no need for conversions. Since the containers themselves are now organized as a hierarchy, we can have subprograms that work on a T_List that also work on a TChild_List (the usual reuse of object-oriented code).
However, the new structure is not perfect. One caveat is that it's possible to insert an object of type T in a TChild_List (because the list contains T'Class elements). The consequence is that the iterator will raise Constraint_Error in the implicit call to Child_Value in the expanded code.
We hope that this Gem has helped to explain some of the "magic" behind the Ada 2012 iterators and containers, and will enable you to use them more effectively in your own code. Even though they do require quite a lot of boilerplate code, written once up front for a container, they definitely make code in clients of the container easier to read and understand.
One final note: the examples in this Gem require a fairly recent version of the compiler, which includes a number of adjustments to reflect recent clarifications in the Ada 2012 rules.