diff mbox

[Ada] Fixed bugs in iterators for vector containers

Message ID 20111212112918.GA31421@adacore.com
State New
Headers show

Commit Message

Arnaud Charlet Dec. 12, 2011, 11:29 a.m. UTC 
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).

The Next and Previous iterator 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.

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-12-12  Matthew Heaney  <heaney@adacore.com>

	* a-convec.adb, a-coinve.adb, a-cobove.adb (Iterator): Use
	subtype Index_Type'Base for Index component (Finalize): Remove
	unnecessary access check (First, Last): Cursor return value
	depends on iterator index value (Iterate): Use start position as
	iterator index value (Next, Previous): Forward to corresponding
	cursor-based operation.
	* a-cborma.adb (Iterate): Properly initialize iterator object (with 0
	as node index).
diff mbox

Patch

Index: a-cborma.adb
===================================================================
--- a-cborma.adb	(revision 182223)
+++ a-cborma.adb	(working copy)
@@ -935,7 +935,7 @@ 
       return It : constant Iterator :=
                     (Limited_Controlled with
                        Container => Container'Unrestricted_Access,
-                       Node      => Container.First)
+                       Node      => 0)
       do
          B := B + 1;
       end return;
Index: a-cobove.adb
===================================================================
--- a-cobove.adb	(revision 182223)
+++ a-cobove.adb	(working copy)
@@ -38,7 +38,7 @@ 
      Vector_Iterator_Interfaces.Reversible_Iterator with
    record
       Container : Vector_Access;
-      Index     : Index_Type;
+      Index     : Index_Type'Base;
    end record;
 
    overriding procedure Finalize (Object : in out Iterator);
@@ -667,14 +667,9 @@ 
    --------------
 
    procedure Finalize (Object : in out Iterator) is
+      B : Natural renames Object.Container.Busy;
    begin
-      if Object.Container /= null then
-         declare
-            B : Natural renames Object.Container.all.Busy;
-         begin
-            B := B - 1;
-         end;
-      end if;
+      B := B - 1;
    end Finalize;
 
    ----------
@@ -740,10 +735,24 @@ 
 
    function First (Object : Iterator) return Cursor is
    begin
-      if Is_Empty (Object.Container.all) then
-         return No_Element;
+      --  The value of the iterator object's Index component influences the
+      --  behavior of the First (and Last) selector function.
+
+      --  When the Index component is No_Index, 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 Index component isn't No_Index, the iterator object was
+      --  constructed with a start expression, that specifies the position from
+      --  which the (forward) partial iteration begins.
+
+      if Object.Index = No_Index then
+         return First (Object.Container.all);
       else
-         return  Cursor'(Object.Container, Index_Type'First);
+         return Cursor'(Object.Container, Object.Index);
       end if;
    end First;
 
@@ -1648,12 +1657,24 @@ 
      (Container : Vector)
       return Vector_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      B : Natural renames Container'Unrestricted_Access.all.Busy;
+      V : constant Vector_Access := Container'Unrestricted_Access;
+      B : Natural renames V.Busy;
+
    begin
+      --  The value of its Index component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Index
+      --  component is No_Index (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 It : constant Iterator :=
-                    Iterator'(Limited_Controlled with
-                                Container => Container'Unrestricted_Access,
-                                Index     => Index_Type'First)
+                    (Limited_Controlled with
+                       Container => V,
+                       Index     => No_Index)
       do
          B := B + 1;
       end return;
@@ -1662,14 +1683,51 @@ 
    function Iterate
      (Container : Vector;
       Start     : Cursor)
-      return Vector_Iterator_Interfaces.Reversible_Iterator'class
+      return Vector_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      B : Natural renames Container'Unrestricted_Access.all.Busy;
+      V : constant Vector_Access := Container'Unrestricted_Access;
+      B : Natural renames V.Busy;
+
    begin
+      --  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.Container = null then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      if Start.Container /= V then
+         raise Program_Error with
+           "Start cursor of Iterate designates wrong vector";
+      end if;
+
+      if Start.Index > V.Last then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      --  The value of its Index component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Index
+      --  component is not No_Index (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 It : constant Iterator :=
-                    Iterator'(Limited_Controlled with
-                                Container => Container'Unrestricted_Access,
-                                Index     => Start.Index)
+                    (Limited_Controlled with
+                       Container => V,
+                       Index     => Start.Index)
       do
          B := B + 1;
       end return;
@@ -1690,10 +1748,23 @@ 
 
    function Last (Object : Iterator) return Cursor is
    begin
-      if Is_Empty (Object.Container.all) then
-         return No_Element;
+      --  The value of the iterator object's Index component influences the
+      --  behavior of the Last (and First) selector function.
+
+      --  When the Index component is No_Index, 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 Index component is not No_Index, the iterator object was
+      --  constructed with a start expression, that specifies the position from
+      --  which the (reverse) partial iteration begins.
+
+      if Object.Index = No_Index then
+         return Last (Object.Container.all);
       else
-         return Cursor'(Object.Container, Object.Container.Last);
+         return Cursor'(Object.Container, Object.Index);
       end if;
    end Last;
 
@@ -1811,11 +1882,16 @@ 
 
    function Next (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Index = Object.Container.Last then
-         return  No_Element;
-      else
-         return (Object.Container, Position.Index + 1);
+      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 vector";
+      end if;
+
+      return Next (Position);
    end Next;
 
    procedure Next (Position : in out Cursor) is
@@ -1884,11 +1960,16 @@ 
 
    function Previous (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Index > Index_Type'First then
-         return (Object.Container, Position.Index - 1);
-      else
+      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 vector";
+      end if;
+
+      return Previous (Position);
    end Previous;
 
    -------------------
Index: a-coinve.adb
===================================================================
--- a-coinve.adb	(revision 182223)
+++ a-coinve.adb	(working copy)
@@ -44,7 +44,7 @@ 
      Vector_Iterator_Interfaces.Reversible_Iterator with
    record
       Container : Vector_Access;
-      Index     : Index_Type;
+      Index     : Index_Type'Base;
    end record;
 
    overriding procedure Finalize (Object : in out Iterator);
@@ -1109,14 +1109,9 @@ 
    end Finalize;
 
    procedure Finalize (Object : in out Iterator) is
+      B : Natural renames Object.Container.Busy;
    begin
-      if Object.Container /= null then
-         declare
-            B : Natural renames Object.Container.all.Busy;
-         begin
-            B := B - 1;
-         end;
-      end if;
+      B := B - 1;
    end Finalize;
 
    ----------
@@ -1185,9 +1180,26 @@ 
    end First;
 
    function First (Object : Iterator) return Cursor is
-      C : constant Cursor := (Object.Container, Index_Type'First);
    begin
-      return C;
+      --  The value of the iterator object's Index component influences the
+      --  behavior of the First (and Last) selector function.
+
+      --  When the Index component is No_Index, 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 Index component isn't No_Index, the iterator object was
+      --  constructed with a start expression, that specifies the position from
+      --  which the (forward) partial iteration begins.
+
+      if Object.Index = No_Index then
+         return First (Object.Container.all);
+      else
+         return Cursor'(Object.Container, Object.Index);
+      end if;
    end First;
 
    -------------------
@@ -2552,15 +2564,26 @@ 
    end Iterate;
 
    function Iterate (Container : Vector)
-      return Vector_Iterator_Interfaces.Reversible_Iterator'class
+      return Vector_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      B  : Natural renames Container'Unrestricted_Access.all.Busy;
+      V : constant Vector_Access := Container'Unrestricted_Access;
+      B : Natural renames V.Busy;
 
    begin
+      --  The value of its Index component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Index
+      --  component is No_Index (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 It : constant Iterator :=
                     (Limited_Controlled with
-                       Container => Container'Unrestricted_Access,
-                       Index     => Index_Type'First)
+                       Container => V,
+                       Index     => No_Index)
       do
          B := B + 1;
       end return;
@@ -2569,14 +2592,50 @@ 
    function Iterate
      (Container : Vector;
       Start     : Cursor)
-      return Vector_Iterator_Interfaces.Reversible_Iterator'class
+      return Vector_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      B  : Natural renames Container'Unrestricted_Access.all.Busy;
+      V : constant Vector_Access := Container'Unrestricted_Access;
+      B : Natural renames V.Busy;
 
    begin
+      --  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.Container = null then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      if Start.Container /= V then
+         raise Program_Error with
+           "Start cursor of Iterate designates wrong vector";
+      end if;
+
+      if Start.Index > V.Last then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      --  The value of its Index component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Index
+      --  component is not No_Index (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 It : constant Iterator :=
                     (Limited_Controlled with
-                       Container => Container'Unrestricted_Access,
+                       Container => V,
                        Index     => Start.Index)
       do
          B := B + 1;
@@ -2597,9 +2656,25 @@ 
    end Last;
 
    function Last (Object : Iterator) return Cursor is
-      C : constant Cursor := (Object.Container, Object.Container.Last);
    begin
-      return C;
+      --  The value of the iterator object's Index component influences the
+      --  behavior of the Last (and First) selector function.
+
+      --  When the Index component is No_Index, 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 Index component is not No_Index, the iterator object was
+      --  constructed with a start expression, that specifies the position from
+      --  which the (reverse) partial iteration begins.
+
+      if Object.Index = No_Index then
+         return Last (Object.Container.all);
+      else
+         return Cursor'(Object.Container, Object.Index);
+      end if;
    end Last;
 
    -----------------
@@ -2718,11 +2793,16 @@ 
 
    function Next (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Index = Object.Container.Last then
-         return  No_Element;
-      else
-         return (Object.Container, Position.Index + 1);
+      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 vector";
+      end if;
+
+      return Next (Position);
    end Next;
 
    procedure Next (Position : in out Cursor) is
@@ -2791,11 +2871,16 @@ 
 
    function Previous (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Index > Index_Type'First then
-         return (Object.Container, Position.Index - 1);
-      else
+      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 vector";
+      end if;
+
+      return Previous (Position);
    end Previous;
 
    -------------------
Index: a-convec.adb
===================================================================
--- a-convec.adb	(revision 182223)
+++ a-convec.adb	(working copy)
@@ -41,16 +41,18 @@ 
      Vector_Iterator_Interfaces.Reversible_Iterator with
    record
       Container : Vector_Access;
-      Index     : Index_Type;
+      Index     : Index_Type'Base;
    end record;
 
    overriding procedure Finalize (Object : in out Iterator);
 
    overriding function First (Object : Iterator) return Cursor;
    overriding function Last  (Object : Iterator) return Cursor;
+
    overriding function Next
-     (Object : Iterator;
+     (Object   : Iterator;
       Position : Cursor) return Cursor;
+
    overriding function Previous
      (Object   : Iterator;
       Position : Cursor) return Cursor;
@@ -782,14 +784,9 @@ 
    end Finalize;
 
    procedure Finalize (Object : in out Iterator) is
+      B : Natural renames Object.Container.Busy;
    begin
-      if Object.Container /= null then
-         declare
-            B : Natural renames Object.Container.all.Busy;
-         begin
-            B := B - 1;
-         end;
-      end if;
+      B := B - 1;
    end Finalize;
 
    ----------
@@ -855,10 +852,24 @@ 
 
    function First (Object : Iterator) return Cursor is
    begin
-      if Is_Empty (Object.Container.all) then
-         return No_Element;
+      --  The value of the iterator object's Index component influences the
+      --  behavior of the First (and Last) selector function.
+
+      --  When the Index component is No_Index, 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 Index component isn't No_Index, the iterator object was
+      --  constructed with a start expression, that specifies the position from
+      --  which the (forward) partial iteration begins.
+
+      if Object.Index = No_Index then
+         return First (Object.Container.all);
       else
-         return (Object.Container, Index_Type'First);
+         return Cursor'(Object.Container, Object.Index);
       end if;
    end First;
 
@@ -2124,13 +2135,24 @@ 
      (Container : Vector)
       return Vector_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      B  : Natural renames Container'Unrestricted_Access.all.Busy;
+      V : constant Vector_Access := Container'Unrestricted_Access;
+      B : Natural renames V.Busy;
 
    begin
+      --  The value of its Index component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Index
+      --  component is No_Index (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 It : constant Iterator :=
                     (Limited_Controlled with
-                       Container => Container'Unrestricted_Access,
-                       Index     => Index_Type'First)
+                       Container => V,
+                       Index     => No_Index)
       do
          B := B + 1;
       end return;
@@ -2141,12 +2163,48 @@ 
       Start     : Cursor)
       return Vector_Iterator_Interfaces.Reversible_Iterator'class
    is
-      B  : Natural renames Container'Unrestricted_Access.all.Busy;
+      V : constant Vector_Access := Container'Unrestricted_Access;
+      B : Natural renames V.Busy;
 
    begin
+      --  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.Container = null then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      if Start.Container /= V then
+         raise Program_Error with
+           "Start cursor of Iterate designates wrong vector";
+      end if;
+
+      if Start.Index > V.Last then
+         raise Constraint_Error with
+           "Start position for iterator equals No_Element";
+      end if;
+
+      --  The value of its Index component influences the behavior of the First
+      --  and Last selector functions of the iterator object. When the Index
+      --  component is not No_Index (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 It : constant Iterator :=
                     (Limited_Controlled with
-                       Container => Container'Unrestricted_Access,
+                       Container => V,
                        Index     => Start.Index)
       do
          B := B + 1;
@@ -2168,10 +2226,23 @@ 
 
    function Last (Object : Iterator) return Cursor is
    begin
-      if Is_Empty (Object.Container.all) then
-         return No_Element;
+      --  The value of the iterator object's Index component influences the
+      --  behavior of the Last (and First) selector function.
+
+      --  When the Index component is No_Index, 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 Index component is not No_Index, the iterator object was
+      --  constructed with a start expression, that specifies the position from
+      --  which the (reverse) partial iteration begins.
+
+      if Object.Index = No_Index then
+         return Last (Object.Container.all);
       else
-         return (Object.Container, Object.Container.Last);
+         return Cursor'(Object.Container, Object.Index);
       end if;
    end Last;
 
@@ -2282,11 +2353,16 @@ 
 
    function Next (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Index < Object.Container.Last then
-         return (Object.Container, Position.Index + 1);
-      else
+      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 vector";
+      end if;
+
+      return Next (Position);
    end Next;
 
    procedure Next (Position : in out Cursor) is
@@ -2338,11 +2414,16 @@ 
 
    function Previous (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Index > Index_Type'First then
-         return (Object.Container, Position.Index - 1);
-      else
+      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 vector";
+      end if;
+
+      return Previous (Position);
    end Previous;
 
    procedure Previous (Position : in out Cursor) is