From patchwork Wed Nov 23 11:05:40 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Arnaud Charlet X-Patchwork-Id: 127265 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id CFFA51007D2 for ; Wed, 23 Nov 2011 22:06:04 +1100 (EST) Received: (qmail 7411 invoked by alias); 23 Nov 2011 11:06:02 -0000 Received: (qmail 7394 invoked by uid 22791); 23 Nov 2011 11:05:58 -0000 X-SWARE-Spam-Status: No, hits=-0.4 required=5.0 tests=AWL, BAYES_00, FILL_THIS_FORM, FILL_THIS_FORM_LOAN X-Spam-Check-By: sourceware.org Received: from rock.gnat.com (HELO rock.gnat.com) (205.232.38.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 23 Nov 2011 11:05:41 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id B63AE2BB366; Wed, 23 Nov 2011 06:05:40 -0500 (EST) Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id eysse-trW6au; Wed, 23 Nov 2011 06:05:40 -0500 (EST) Received: from kwai.gnat.com (kwai.gnat.com [205.232.38.4]) by rock.gnat.com (Postfix) with ESMTP id 998CF2BB343; Wed, 23 Nov 2011 06:05:40 -0500 (EST) Received: by kwai.gnat.com (Postfix, from userid 4192) id 980C93FEE8; Wed, 23 Nov 2011 06:05:40 -0500 (EST) Date: Wed, 23 Nov 2011 06:05:40 -0500 From: Arnaud Charlet To: gcc-patches@gcc.gnu.org Cc: Matthew Heaney Subject: [Ada] Change semantics of partial iteration Message-ID: <20111123110540.GA22384@adacore.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 * 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 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