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

	* a-cdlili.adb, a-cidlli.adb, a-cbdlli.adb (Iterator): Declared
	Iterator type as limited (First, Last): Cursor return value
	depends on iterator node value (Iterate): Use start position as
	iterator node value (Next, Previous): Forward to corresponding
	cursor-based operation.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@181667 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 293 insertions, 69 deletions

diff --git a/gcc/ada/ChangeLog b/gcc/ada/ChangeLog
index 42021e58a20..b462d0a14f1 100644
--- a/gcc/ada/ChangeLog
+++ b/gcc/ada/ChangeLog
@@ -1,5 +1,13 @@
 2011-11-23  Matthew Heaney  <heaney@adacore.com>
 
+	* a-cdlili.adb, a-cidlli.adb, a-cbdlli.adb (Iterator): Declared
+	Iterator type as limited (First, Last): Cursor return value
+	depends on iterator node value (Iterate): Use start position as
+	iterator node value (Next, Previous): Forward to corresponding
+	cursor-based operation.
+
+2011-11-23  Matthew Heaney  <heaney@adacore.com>
+
 	* a-coorse.ads, a-ciorse.ads, a-cborse.ads (Set_Iterator_Interfaces):
 	Renamed from Ordered_Set_Iterator_Interfaces.
 	* a-coorse.adb, a-ciorse.adb, a-cborse.adb (Iterator): Declared
diff --git a/gcc/ada/a-cbdlli.adb b/gcc/ada/a-cbdlli.adb
index 5a3169eee50..85ead8aef0c 100644
--- a/gcc/ada/a-cbdlli.adb
+++ b/gcc/ada/a-cbdlli.adb
@@ -30,7 +30,8 @@
 with System;  use type System.Address;
 
 package body Ada.Containers.Bounded_Doubly_Linked_Lists is
-   type Iterator is new
+
+   type Iterator is limited new
      List_Iterator_Interfaces.Reversible_Iterator with record
         Container : List_Access;
         Node      : Count_Type;
@@ -544,10 +545,23 @@ package body Ada.Containers.Bounded_Doubly_Linked_Lists is
 
    function First (Object : Iterator) return Cursor is
    begin
-      if Object.Container = 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 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_Doubly_Linked_Lists.First (Object.Container.all);
       else
-         return (Object.Container, Object.Container.First);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end First;
 
@@ -1075,14 +1089,20 @@ package body Ada.Containers.Bounded_Doubly_Linked_Lists is
 
    function Iterate
      (Container : List)
-      return List_Iterator_Interfaces.Reversible_Iterator'class
+      return List_Iterator_Interfaces.Reversible_Iterator'Class
    is
    begin
-      if Container.Length = 0 then
-         return Iterator'(null, Count_Type'First);
-      else
-         return Iterator'(Container'Unrestricted_Access, Container.First);
-      end if;
+      --  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
@@ -1090,9 +1110,40 @@ package body Ada.Containers.Bounded_Doubly_Linked_Lists is
       Start     : Cursor)
       return List_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 list";
+      end if;
+
+      pragma Assert (Vet (Start), "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;
 
    ----------
@@ -1110,10 +1161,23 @@ package body Ada.Containers.Bounded_Doubly_Linked_Lists is
 
    function Last (Object : Iterator) return Cursor is
    begin
-      if Object.Container = 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 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_Doubly_Linked_Lists.Last (Object.Container.all);
       else
-         return (Object.Container, Object.Container.Last);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end Last;
 
@@ -1260,14 +1324,17 @@ package body Ada.Containers.Bounded_Doubly_Linked_Lists is
      (Object   : Iterator;
       Position : Cursor) return Cursor
    is
-      Nodes : Node_Array renames Position.Container.Nodes;
-      Node  : constant Count_Type := Nodes (Position.Node).Next;
    begin
-      if Position.Node = Object.Container.Last then
+      if Position.Container = null then
          return No_Element;
-      else
-         return (Object.Container, Node);
       end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Next designates wrong list";
+      end if;
+
+      return Next (Position);
    end Next;
 
    -------------
@@ -1316,14 +1383,17 @@ package body Ada.Containers.Bounded_Doubly_Linked_Lists is
      (Object   : Iterator;
       Position : Cursor) return Cursor
    is
-      Nodes : Node_Array renames Position.Container.Nodes;
-      Node  : constant Count_Type := Nodes (Position.Node).Prev;
    begin
-      if Position.Node = 0 then
+      if Position.Container = null then
          return No_Element;
-      else
-         return (Object.Container, Node);
       end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Previous designates wrong list";
+      end if;
+
+      return Previous (Position);
    end Previous;
 
    -------------------
diff --git a/gcc/ada/a-cdlili.adb b/gcc/ada/a-cdlili.adb
index 8b513222ef8..63cae28aefe 100644
--- a/gcc/ada/a-cdlili.adb
+++ b/gcc/ada/a-cdlili.adb
@@ -32,7 +32,8 @@ with System;  use type System.Address;
 with Ada.Unchecked_Deallocation;
 
 package body Ada.Containers.Doubly_Linked_Lists is
-   type Iterator is new
+
+   type Iterator is limited new
      List_Iterator_Interfaces.Reversible_Iterator with record
         Container : List_Access;
         Node      : Node_Access;
@@ -445,10 +446,23 @@ package body Ada.Containers.Doubly_Linked_Lists is
 
    function First (Object : Iterator) return Cursor is
    begin
-      if Object.Container = 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 Doubly_Linked_Lists.First (Object.Container.all);
       else
-         return (Object.Container, Object.Container.First);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end First;
 
@@ -866,22 +880,59 @@ package body Ada.Containers.Doubly_Linked_Lists is
    end Iterate;
 
    function Iterate (Container : List)
-     return List_Iterator_Interfaces.Reversible_Iterator'class
+     return List_Iterator_Interfaces.Reversible_Iterator'Class
    is
    begin
-      if Container.Length = 0 then
-         return Iterator'(null, null);
-      else
-         return Iterator'(Container'Unchecked_Access, Container.First);
-      end if;
+      --  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 : List; Start : Cursor)
-     return List_Iterator_Interfaces.Reversible_Iterator'class
+     return List_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      It : constant Iterator := (Container'Unchecked_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 list";
+      end if;
+
+      pragma Assert (Vet (Start), "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;
 
    ----------
@@ -899,10 +950,23 @@ package body Ada.Containers.Doubly_Linked_Lists is
 
    function Last (Object : Iterator) return Cursor is
    begin
-      if Object.Container = 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 Doubly_Linked_Lists.Last (Object.Container.all);
       else
-         return (Object.Container, Object.Container.Last);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end Last;
 
@@ -992,11 +1056,16 @@ package body Ada.Containers.Doubly_Linked_Lists is
       Position : Cursor) return Cursor
    is
    begin
-      if Position.Node = Object.Container.Last then
+      if Position.Container = null then
          return No_Element;
-      else
-         return (Object.Container, Position.Node.Next);
       end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Next designates wrong list";
+      end if;
+
+      return Next (Position);
    end Next;
 
    -------------
@@ -1046,11 +1115,16 @@ package body Ada.Containers.Doubly_Linked_Lists is
       Position : Cursor) return Cursor
    is
    begin
-      if Position.Node = Position.Container.First then
+      if Position.Container = null then
          return No_Element;
-      else
-         return (Object.Container, Position.Node.Prev);
       end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Previous designates wrong list";
+      end if;
+
+      return Previous (Position);
    end Previous;
 
    -------------------
diff --git a/gcc/ada/a-cidlli.adb b/gcc/ada/a-cidlli.adb
index dbdc6de47d4..764325e4bdc 100644
--- a/gcc/ada/a-cidlli.adb
+++ b/gcc/ada/a-cidlli.adb
@@ -35,7 +35,7 @@ package body Ada.Containers.Indefinite_Doubly_Linked_Lists is
    procedure Free is
      new Ada.Unchecked_Deallocation (Element_Type, Element_Access);
 
-   type Iterator is new
+   type Iterator is limited new
      List_Iterator_Interfaces.Reversible_Iterator with record
         Container : List_Access;
         Node      : Node_Access;
@@ -483,10 +483,23 @@ package body Ada.Containers.Indefinite_Doubly_Linked_Lists is
 
    function First (Object : Iterator) return Cursor is
    begin
-      if Object.Container = 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 Indefinite_Doubly_Linked_Lists.First (Object.Container.all);
       else
-         return Cursor'(Object.Container, Object.Container.First);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end First;
 
@@ -895,24 +908,61 @@ package body Ada.Containers.Indefinite_Doubly_Linked_Lists is
 
    function Iterate
      (Container : List)
-      return List_Iterator_Interfaces.Reversible_Iterator'class
+      return List_Iterator_Interfaces.Reversible_Iterator'Class
    is
    begin
-      if Container.Length = 0 then
-         return Iterator'(null, null);
-      else
-         return Iterator'(Container'Unchecked_Access, Container.First);
-      end if;
+      --  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 : List;
       Start     : Cursor)
-      return List_Iterator_Interfaces.Reversible_Iterator'class
+      return List_Iterator_Interfaces.Reversible_Iterator'Class
    is
-      It : constant Iterator := (Container'Unchecked_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 list";
+      end if;
+
+      pragma Assert (Vet (Start), "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;
 
    ----------
@@ -930,10 +980,23 @@ package body Ada.Containers.Indefinite_Doubly_Linked_Lists is
 
    function Last (Object : Iterator) return Cursor is
    begin
-      if Object.Container = 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 Indefinite_Doubly_Linked_Lists.Last (Object.Container.all);
       else
-         return Cursor'(Object.Container, Object.Container.Last);
+         return Cursor'(Object.Container, Object.Node);
       end if;
    end Last;
 
@@ -1016,12 +1079,16 @@ package body Ada.Containers.Indefinite_Doubly_Linked_Lists is
 
    function Next (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Node = Object.Container.Last then
+      if Position.Container = null then
          return No_Element;
+      end if;
 
-      else
-         return (Object.Container, Position.Node.Next);
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Next designates wrong list";
       end if;
+
+      return Next (Position);
    end Next;
 
    -------------
@@ -1067,11 +1134,16 @@ package body Ada.Containers.Indefinite_Doubly_Linked_Lists is
 
    function Previous (Object : Iterator; Position : Cursor) return Cursor is
    begin
-      if Position.Node = Position.Container.First then
+      if Position.Container = null then
          return No_Element;
-      else
-         return (Object.Container, Position.Node.Prev);
       end if;
+
+      if Position.Container /= Object.Container then
+         raise Program_Error with
+           "Position cursor of Previous designates wrong list";
+      end if;
+
+      return Previous (Position);
    end Previous;
 
    -------------------