diff mbox

[Ada] Change semantics of partial iteration

Message ID 20111123110540.GA22384@adacore.com
State New
Headers show

Commit Message

Arnaud Charlet Nov. 23, 2011, 11:05 a.m. UTC 
There were several issues with the implementation of the map iterator.

(1) Ordered maps support reverse iteration, so the type returned by the
iterator factory function was changed from Forward_Iterator'Class to
Reversible_Iterator'Class.

(2) The concrete type Iterator was declared as limited, because there is no
need for assignment for iterator objects.

(3) The First and Last selector functions return a value that depends on
whether this is complete or partial iteration. For complete iteration, the
selector function returns the logical beginning of the entire sequence of items
in the container. (To be specific, Container.First for a forward iterator, and
Container.Last for a reverse iterator.) For partial iteration, the selector
function returns the start position value specified when the iterator object
was constructed (in this case, both First and Last return the same value).

(4) The Next and Previous operations vet the cursor parameter to ensure that it
designates a node in the same container as the iterator. The function then
forwards to the call to the analogous cursor-based operation.

(5) Iterate constructs an iterator object whose state indicates whether this is
complete or partial iteration. There was also change in the semantics of the
partial iterator (per the ARG meeting in Denver on 2011/11): if the start
position equals No_Element, then it raises Constraint_Error; otherwise, it
constructs an iterator object to indicate the position from which the iteration
begins (which is in turn used by the selector functions First and Last).

Tested on x86_64-pc-linux-gnu, committed on trunk

2011-11-23  Matthew Heaney  <heaney@adacore.com>

	* a-coorma.ads, a-ciorma.ads, a-cborma.ads (Iterate): Returns
	type Reversible_Iterator'Class.
	* a-coorma.adb, a-ciorma.adb, a-cborma.adb (Iterator):
	Declare type as limited.
	(First, Last): Return value depends on iterator's start node value.
	(Next, Previous): Call corresponding Cursor-based operation.
	(Iterate): Indicate whether complete or partial iteration
diff mbox

Patch

Index: a-coorma.adb
===================================================================
--- a-coorma.adb	(revision 181654)
+++ a-coorma.adb	(working copy)
@@ -39,7 +39,7 @@ 
 
 package body Ada.Containers.Ordered_Maps is
 
-   type Iterator is new
+   type Iterator is limited new
      Map_Iterator_Interfaces.Reversible_Iterator with record
         Container : Map_Access;
         Node      : Node_Access;
@@ -518,13 +518,24 @@ 
    end First;
 
    function First (Object : Iterator) return Cursor is
-      M : constant Map_Access  := Object.Container;
-      N : constant Node_Access := M.Tree.First;
    begin
-      if N = null then
-         return No_Element;
+      --  The value of the iterator object's Node component influences the
+      --  behavior of the First (and Last) selector function.
+
+      --  When the Node component is null, this means the iterator object was
+      --  constructed without a start expression, in which case the (forward)
+      --  iteration starts from the (logical) beginning of the entire sequence
+      --  of items (corresponding to Container.First, for a forward iterator).
+
+      --  Otherwise, this is iteration over a partial sequence of items. When
+      --  the Node component is non-null, the iterator object was constructed
+      --  with a start expression, that specifies the position from which the
+      --  (forward) partial iteration begins.
+
+      if Object.Node = null then
+         return Object.Container.First;
       else
-         return Cursor'(Object.Container.all'Unchecked_Access, N);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end First;
 
@@ -534,7 +545,6 @@ 
 
    function First_Element (Container : Map) return Element_Type is
       T : Tree_Type renames Container.Tree;
-
    begin
       if T.First = null then
          raise Constraint_Error with "map is empty";
@@ -827,21 +837,60 @@ 
    end Iterate;
 
    function Iterate
-     (Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'class
+     (Container : Map) return Map_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      Node : constant Node_Access := Container.Tree.First;
-      It   : constant Iterator := (Container'Unrestricted_Access, Node);
+   begin
+      --  The value of the Node component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Node
+      --  component is null (as is the case here), this means the iterator
+      --  object was constructed without a start expression. This is a
+      --  complete iterator, meaning that the iteration starts from the
+      --  (logical) beginning of the sequence of items.
 
-   begin
-      return It;
+      --  Note: For a forward iterator, Container.First is the beginning, and
+      --  for a reverse iterator, Container.Last is the beginning.
+
+      return Iterator'(Container'Unrestricted_Access, Node => null);
    end Iterate;
 
    function Iterate (Container : Map; Start : Cursor)
-      return Map_Iterator_Interfaces.Reversible_Iterator'class
+      return Map_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      It : constant Iterator := (Container'Unrestricted_Access, Start.Node);
    begin
-      return It;
+      --  It was formerly the case that when Start = No_Element, the partial
+      --  iterator was defined to behave the same as for a complete iterator,
+      --  and iterate over the entire sequence of items. However, those
+      --  semantics were unintuitive and arguably error-prone (it is too easy
+      --  to accidentally create an endless loop), and so they were changed,
+      --  per the ARG meeting in Denver on 2011/11. However, there was no
+      --  consensus about what positive meaning this corner case should have,
+      --  and so it was decided to simply raise an exception. This does imply,
+      --  however, that it is not possible to use a partial iterator to specify
+      --  an empty sequence of items.
+
+      if Start = No_Element then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      if Start.Container /= Container'Unrestricted_Access then
+         raise Program_Error with
+           "Start cursor of Iterate designates wrong map";
+      end if;
+
+      pragma Assert (Vet (Container.Tree, Start.Node),
+                     "Start cursor of Iterate is bad");
+
+      --  The value of the Node component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Node
+      --  component is non-null (as is the case here), it means that this
+      --  is a partial iteration, over a subset of the complete sequence of
+      --  items. The iterator object was constructed with a start expression,
+      --  indicating the position from which the iteration begins. Note that
+      --  the start position has the same value irrespective of whether this
+      --  is a forward or reverse iteration.
+
+      return Iterator'(Container'Unrestricted_Access, Node => Start.Node);
    end Iterate;
 
    ---------
@@ -876,13 +925,24 @@ 
    end Last;
 
    function Last (Object : Iterator) return Cursor is
-      M : constant Map_Access  := Object.Container;
-      N : constant Node_Access := M.Tree.Last;
    begin
-      if N = null then
-         return No_Element;
+      --  The value of the iterator object's Node component influences the
+      --  behavior of the Last (and First) selector function.
+
+      --  When the Node component is null, this means the iterator object was
+      --  constructed without a start expression, in which case the (reverse)
+      --  iteration starts from the (logical) beginning of the entire sequence
+      --  (corresponding to Container.Last, for a reverse iterator).
+
+      --  Otherwise, this is iteration over a partial sequence of items. When
+      --  the Node component is non-null, the iterator object was constructed
+      --  with a start expression, that specifies the position from which the
+      --  (reverse) partial iteration begins.
+
+      if Object.Node = null then
+         return Object.Container.Last;
       else
-         return Cursor'(Object.Container.all'Unchecked_Access, N);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end Last;
 
@@ -980,11 +1040,16 @@ 
       Position : Cursor) return Cursor
    is
    begin
-      if Position.Node = null then
+      if Position.Container = null then
          return No_Element;
-      else
-         return (Object.Container, Tree_Operations.Next (Position.Node));
       end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Next designates wrong map";
+      end if;
+
+      return Next (Position);
    end Next;
 
    ------------
@@ -1032,12 +1097,18 @@ 
       Position : Cursor) return Cursor
    is
    begin
-      if Position.Node = null then
+      if Position.Container = null then
          return No_Element;
-      else
-         return (Object.Container, Tree_Operations.Previous (Position.Node));
       end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Previous designates wrong map";
+      end if;
+
+      return Previous (Position);
    end Previous;
+
    -------------------
    -- Query_Element --
    -------------------
Index: a-coorma.ads
===================================================================
--- a-coorma.ads	(revision 181654)
+++ a-coorma.ads	(working copy)
@@ -203,19 +203,23 @@ 
      (Container : Map;
       Process   : not null access procedure (Position : Cursor));
 
+   procedure Reverse_Iterate
+     (Container : Map;
+      Process   : not null access procedure (Position : Cursor));
+
+   --  The map container supports iteration in both the forward and reverse
+   --  directions, hence these constructor functions return an object that
+   --  supports the Reversible_Iterator interface.
+
    function Iterate
      (Container : Map)
-      return Map_Iterator_Interfaces.Forward_Iterator'class;
+      return Map_Iterator_Interfaces.Reversible_Iterator'class;
 
    function Iterate
      (Container : Map;
       Start     : Cursor)
       return Map_Iterator_Interfaces.Reversible_Iterator'class;
 
-   procedure Reverse_Iterate
-     (Container : Map;
-      Process   : not null access procedure (Position : Cursor));
-
 private
 
    pragma Inline (Next);
Index: a-cborma.adb
===================================================================
--- a-cborma.adb	(revision 181654)
+++ a-cborma.adb	(working copy)
@@ -39,7 +39,7 @@ 
 
 package body Ada.Containers.Bounded_Ordered_Maps is
 
-   type Iterator is new
+   type Iterator is limited new
      Map_Iterator_Interfaces.Reversible_Iterator with record
         Container : Map_Access;
         Node      : Count_Type;
@@ -579,12 +579,24 @@ 
    end First;
 
    function First (Object : Iterator) return Cursor is
-      F : constant Count_Type := Object.Container.First;
    begin
-      if F = 0 then
-         return No_Element;
+      --  The value of the iterator object's Node component influences the
+      --  behavior of the First (and Last) selector function.
+
+      --  When the Node component is 0, this means the iterator object was
+      --  constructed without a start expression, in which case the (forward)
+      --  iteration starts from the (logical) beginning of the entire sequence
+      --  of items (corresponding to Container.First, for a forward iterator).
+
+      --  Otherwise, this is iteration over a partial sequence of items. When
+      --  the Node component is positive, the iterator object was constructed
+      --  with a start expression, that specifies the position from which the
+      --  (forward) partial iteration begins.
+
+      if Object.Node = 0 then
+         return Bounded_Ordered_Maps.First (Object.Container.all);
       else
-         return Cursor'(Object.Container.all'Unchecked_Access, F);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end First;
 
@@ -886,22 +898,62 @@ 
    end Iterate;
 
    function Iterate
-     (Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'class
+     (Container : Map) return Map_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      It : constant Iterator :=
-             (Container'Unrestricted_Access, Container.First);
    begin
-      return It;
+      --  The value of the Node component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Node
+      --  component is 0 (as is the case here), this means the iterator object
+      --  was constructed without a start expression. This is a complete
+      --  iterator, meaning that the iteration starts from the (logical)
+      --  beginning of the sequence of items.
+
+      --  Note: For a forward iterator, Container.First is the beginning, and
+      --  for a reverse iterator, Container.Last is the beginning.
+
+      return Iterator'(Container'Unrestricted_Access, Node => 0);
    end Iterate;
 
    function Iterate
      (Container : Map;
       Start     : Cursor)
-      return Map_Iterator_Interfaces.Reversible_Iterator'class
+      return Map_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      It : constant Iterator := (Container'Unrestricted_Access, Start.Node);
    begin
-      return It;
+
+      --  iterator was defined to behave the same as for a complete iterator,
+      --  and iterate over the entire sequence of items. However, those
+      --  semantics were unintuitive and arguably error-prone (it is too easy
+      --  to accidentally create an endless loop), and so they were changed,
+      --  per the ARG meeting in Denver on 2011/11. However, there was no
+      --  consensus about what positive meaning this corner case should have,
+      --  and so it was decided to simply raise an exception. This does imply,
+      --  however, that it is not possible to use a partial iterator to specify
+      --  an empty sequence of items.
+
+      if Start = No_Element then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      if Start.Container /= Container'Unrestricted_Access then
+         raise Program_Error with
+           "Start cursor of Iterate designates wrong map";
+      end if;
+
+      pragma Assert (Vet (Container, Start.Node),
+                     "Start cursor of Iterate is bad");
+
+      --  The value of the Node component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Node
+      --  component is positive (as is the case here), it means that this
+      --  is a partial iteration, over a subset of the complete sequence of
+      --  items. The iterator object was constructed with a start expression,
+      --  indicating the position from which the iteration begins. (Note that
+      --  the start position has the same value irrespective of whether this
+      --  is a forward or reverse iteration.)
+
+      return Iterator'(Container'Unrestricted_Access, Node => Start.Node);
    end Iterate;
 
    ---------
@@ -935,12 +987,24 @@ 
    end Last;
 
    function Last (Object : Iterator) return Cursor is
-      F : constant Count_Type := Object.Container.Last;
    begin
-      if F = 0 then
-         return No_Element;
+      --  The value of the iterator object's Node component influences the
+      --  behavior of the Last (and First) selector function.
+
+      --  When the Node component is 0, this means the iterator object was
+      --  constructed without a start expression, in which case the (reverse)
+      --  iteration starts from the (logical) beginning of the entire sequence
+      --  (corresponding to Container.Last, for a reverse iterator).
+
+      --  Otherwise, this is iteration over a partial sequence of items. When
+      --  the Node component is positive, the iterator object was constructed
+      --  with a start expression, that specifies the position from which the
+      --  (reverse) partial iteration begins.
+
+      if Object.Node = 0 then
+         return Bounded_Ordered_Maps.Last (Object.Container.all);
       else
-         return Cursor'(Object.Container.all'Unchecked_Access, F);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end Last;
 
@@ -1044,8 +1108,16 @@ 
      (Object   : Iterator;
       Position : Cursor) return Cursor
    is
-      pragma Unreferenced (Object);
    begin
+      if Position.Container = null then
+         return No_Element;
+      end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Next designates wrong map";
+      end if;
+
       return Next (Position);
    end Next;
 
@@ -1095,8 +1167,16 @@ 
      (Object   : Iterator;
       Position : Cursor) return Cursor
    is
-      pragma Unreferenced (Object);
    begin
+      if Position.Container = null then
+         return No_Element;
+      end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Previous designates wrong map";
+      end if;
+
       return Previous (Position);
    end Previous;
 
Index: a-cborma.ads
===================================================================
--- a-cborma.ads	(revision 181654)
+++ a-cborma.ads	(working copy)
@@ -227,18 +227,19 @@ 
      (Container : Map;
       Process   : not null access procedure (Position : Cursor));
 
+   procedure Reverse_Iterate
+     (Container : Map;
+      Process   : not null access procedure (Position : Cursor));
+
    function Iterate
-     (Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'class;
+     (Container : Map)
+      return Map_Iterator_Interfaces.Reversible_Iterator'Class;
 
    function Iterate
      (Container : Map;
       Start     : Cursor)
-      return Map_Iterator_Interfaces.Reversible_Iterator'class;
+      return Map_Iterator_Interfaces.Reversible_Iterator'Class;
 
-   procedure Reverse_Iterate
-     (Container : Map;
-      Process   : not null access procedure (Position : Cursor));
-
 private
 
    pragma Inline (Next);
Index: a-ciorma.adb
===================================================================
--- a-ciorma.adb	(revision 181654)
+++ a-ciorma.adb	(working copy)
@@ -40,7 +40,7 @@ 
 package body Ada.Containers.Indefinite_Ordered_Maps is
    pragma Suppress (All_Checks);
 
-   type Iterator is new
+   type Iterator is limited new
      Map_Iterator_Interfaces.Reversible_Iterator with record
         Container : Map_Access;
         Node      : Node_Access;
@@ -558,11 +558,25 @@ 
    end First;
 
    function First (Object : Iterator) return Cursor is
-      M : constant Map_Access  := Object.Container;
-      N : constant Node_Access := M.Tree.First;
    begin
-      return (if N = null then No_Element
-              else Cursor'(Object.Container.all'Unchecked_Access, N));
+      --  The value of the iterator object's Node component influences the
+      --  behavior of the First (and Last) selector function.
+
+      --  When the Node component is null, this means the iterator object was
+      --  constructed without a start expression, in which case the (forward)
+      --  iteration starts from the (logical) beginning of the entire sequence
+      --  of items (corresponding to Container.First for a forward iterator).
+
+      --  Otherwise, this is iteration over a partial sequence of items. When
+      --  the Node component is non-null, the iterator object was constructed
+      --  with a start expression, that specifies the position from which the
+      --  (forward) partial iteration begins.
+
+      if Object.Node = null then
+         return Object.Container.First;
+      else
+         return Cursor'(Object.Container, Object.Node);
+      end if;
    end First;
 
    -------------------
@@ -571,13 +585,12 @@ 
 
    function First_Element (Container : Map) return Element_Type is
       T : Tree_Type renames Container.Tree;
-
    begin
       if T.First = null then
          raise Constraint_Error with "map is empty";
+      else
+         return T.First.Element.all;
       end if;
-
-      return T.First.Element.all;
    end First_Element;
 
    ---------------
@@ -586,13 +599,12 @@ 
 
    function First_Key (Container : Map) return Key_Type is
       T : Tree_Type renames Container.Tree;
-
    begin
       if T.First = null then
          raise Constraint_Error with "map is empty";
+      else
+         return T.First.Key.all;
       end if;
-
-      return T.First.Key.all;
    end First_Key;
 
    -----------
@@ -864,22 +876,62 @@ 
    end Iterate;
 
    function Iterate
-     (Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'class
+     (Container : Map) return Map_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      Node : constant Node_Access := Container.Tree.First;
-      It   : constant Iterator := (Container'Unrestricted_Access, Node);
    begin
-      return It;
+      --  The value of the Node component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Node
+      --  component is null (as is the case here), this means the iterator
+      --  object was constructed without a start expression. This is a complete
+      --  iterator, meaning that the iteration starts from the (logical)
+      --  beginning of the sequence of items.
+
+      --  Note: For a forward iterator, Container.First is the beginning, and
+      --  for a reverse iterator, Container.Last is the beginning.
+
+      return Iterator'(Container'Unrestricted_Access, Node => null);
    end Iterate;
 
    function Iterate
      (Container : Map;
       Start     : Cursor)
-      return Map_Iterator_Interfaces.Reversible_Iterator'class
+      return Map_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      It : constant Iterator := (Container'Unrestricted_Access, Start.Node);
    begin
-      return It;
+      --  It was formerly the case that when Start = No_Element, the partial
+      --  iterator was defined to behave the same as for a complete iterator,
+      --  and iterate over the entire sequence of items. However, those
+      --  semantics were unintuitive and arguably error-prone (it is too easy
+      --  to accidentally create an endless loop), and so they were changed,
+      --  per the ARG meeting in Denver on 2011/11. However, there was no
+      --  consensus about what positive meaning this corner case should have,
+      --  and so it was decided to simply raise an exception. This does imply,
+      --  however, that it is not possible to use a partial iterator to specify
+      --  an empty sequence of items.
+
+      if Start = No_Element then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      if Start.Container /= Container'Unrestricted_Access then
+         raise Program_Error with
+           "Start cursor of Iterate designates wrong map";
+      end if;
+
+      pragma Assert (Vet (Container.Tree, Start.Node),
+                     "Start cursor of Iterate is bad");
+
+      --  The value of the Node component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Node
+      --  component is non-null (as is the case here), it means that this
+      --  is a partial iteration, over a subset of the complete sequence of
+      --  items. The iterator object was constructed with a start expression,
+      --  indicating the position from which the iteration begins. Note that
+      --  the start position has the same value irrespective of whether this
+      --  is a forward or reverse iteration.
+
+      return Iterator'(Container'Unrestricted_Access, Node => Start.Node);
    end Iterate;
 
    ---------
@@ -916,11 +968,25 @@ 
    end Last;
 
    function Last (Object : Iterator) return Cursor is
-      M : constant Map_Access  := Object.Container;
-      N : constant Node_Access := M.Tree.Last;
    begin
-      return (if N = null then No_Element
-              else Cursor'(Object.Container.all'Unchecked_Access, N));
+      --  The value of the iterator object's Node component influences the
+      --  behavior of the Last (and First) selector function.
+
+      --  When the Node component is null, this means the iterator object was
+      --  constructed without a start expression, in which case the (reverse)
+      --  iteration starts from the (logical) beginning of the entire sequence
+      --  (corresponding to Container.Last, for a reverse iterator).
+
+      --  Otherwise, this is iteration over a partial sequence of items. When
+      --  the Node component is non-null, the iterator object was constructed
+      --  with a start expression, that specifies the position from which the
+      --  (reverse) partial iteration begins.
+
+      if Object.Node = null then
+         return Object.Container.Last;
+      else
+         return Cursor'(Object.Container, Object.Node);
+      end if;
    end Last;
 
    ------------------
@@ -1017,8 +1083,16 @@ 
       Position : Cursor) return Cursor
    is
    begin
-      return (if Position.Node = null then No_Element
-              else (Object.Container, Tree_Operations.Next (Position.Node)));
+      if Position.Container = null then
+         return No_Element;
+      end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Next designates wrong map";
+      end if;
+
+      return Next (Position);
    end Next;
 
    ------------
@@ -1065,9 +1139,16 @@ 
       Position : Cursor) return Cursor
    is
    begin
-      return
-        (if Position.Node = null then No_Element
-         else (Object.Container, Tree_Operations.Previous (Position.Node)));
+      if Position.Container = null then
+         return No_Element;
+      end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Previous designates wrong map";
+      end if;
+
+      return Previous (Position);
    end Previous;
 
    -------------------
@@ -1490,4 +1571,5 @@ 
    begin
       raise Program_Error with "attempt to stream reference";
    end Write;
+
 end Ada.Containers.Indefinite_Ordered_Maps;
Index: a-ciorma.ads
===================================================================
--- a-ciorma.ads	(revision 181654)
+++ a-ciorma.ads	(working copy)
@@ -201,14 +201,18 @@ 
      (Container : Map;
       Process   : not null access procedure (Position : Cursor));
 
+   --  The map container supports iteration in both the forward and reverse
+   --  directions, hence these constructor functions return an object that
+   --  supports the Reversible_Iterator interface.
+
    function Iterate
      (Container : Map)
-      return Map_Iterator_Interfaces.Forward_Iterator'class;
+      return Map_Iterator_Interfaces.Reversible_Iterator'Class;
 
    function Iterate
      (Container : Map;
       Start     : Cursor)
-      return Map_Iterator_Interfaces.Reversible_Iterator'class;
+      return Map_Iterator_Interfaces.Reversible_Iterator'Class;
 
 private