!standard A.18(5/3) 13-10-07 AI12-0035-1/05 !standard A.18.11(8/2) !standard A.18.12(7/2) !standard A.18.13(8/2) !standard A.18.14(8/2) !standard A.18.15(4/2) !standard A.18.16(4/2) !standard A.18.17(7/3) !standard A.18.18(39/3) !standard A.18.18(47/3) !class binding interpretation 12-06-08 !status Corrigendum 2014 13-07-08 !status WG9 Approved 13-11-15 !status ARG Approved 9-0-0 13-06-14 !status work item 12-06-08 !status received 12-06-07 !priority Medium !difficulty Medium !subject Accessibility checks for indefinite elements of containers !summary Certain operations of instances of the indefinite container packages require accessibility checks to prevent dangling references. This is specified in terms of the checks that would be required for executing an initialized allocator for a notional access type with the designated type of the element type of the instance. !question There appears to be a hole in the indefinite container semantics. Consider the following case: The Indefinite_Holders container is instantiated with a class-wide type, and a value of an object of a more deeply nested tagged type is saved in a container of the outer-level instance via a call to Replace_Element. If this procedure is implemented in Ada, using an allocator, the allocator would fail a run-time accessibility check, thus raising Program_Error. This appears to be the behavior we want, as otherwise it would be possible to store a value of a type whose scope has exited within a longer-lived container, and that surely shouldn't be permitted. (Such an object within a container could be referred to as "dangling", in that its tag refers to a type that no longer exists.) Should this be fixed? (Yes.) !recommendation See summary. !wording Add after A.18(5/3): Certain subprograms declared within instances of some of the generic packages presented in this clause are said to *perform indefinite insertion*. These subprograms are those corresponding (in the sense of the copying described in subclause 12.3) to subprograms that have formal parameters of a generic formal indefinite type and that are identified as performing indefinite insertion in the subclause defining the generic package. If a subprogram performs indefinite insertion, then certain run-time checks are performed as part of a call to the subprogram; if any of these checks fail, then the resulting exception is propagated to the caller and the container is not modified by the call. These checks are performed for each parameter corresponding (in the sense of the copying described in 12.3) to a parameter in the corresponding generic whose type is a generic formal indefinite type. The checks performed for a given parameter are those checks explicitly specified in subclause 4.8 that would be performed as part of the evaluation of an initialized allocator whose access type is declared immediately within the instance, where: - the value of the qualified_expression is that of the parameter; and - the designated subtype of the access type is the subtype of the parameter; and - finalization of the collection of the access type has started if and only if the finalization of the instance has started. AARM Discussion: The phrase "explicitly specified" means those checks for which subclause 4.8 includes the phrase " is raised if ...". It does not refer, for example, to any checks performed as part of any subtype conversion. In particular, this wording includes the checks described in subclause 4.8 to be performed in the case of a class-wide designated type, and of a designated subtype that has access discriminant parts. These checks are needed to prevent containers from outliving their contained (Element_Type or Key_Type) values. AARM Implementation note: These rules have a dual purpose. Mainly, we are *requiring* checks needed to prevent dangling references. As a side effect, we are also *allowing* checks needed to permit an implementation of a container generic to make use of access types in a straightforward way. As an example of the second purpose, suppose that an implementation does declare such an access type and suppose further that the finalization of the collection of the access type has started. These rules allow Program_Error to be propagated in this case (as specified in 4.8); this is necessary to allow an all-Ada implementation of these packages. Add after A.18.11(8/2) (Containers.Indefinite_Vectors): * The operations "&", Append, Insert, Prepend, Replace_Element, and To_Vector that have a formal parameter of type Element_Type perform indefinite insertion (see A.18). Add after A.18.12(7/2) (Containers.Indefinite_Doubly_Linked_Lists): * The operations Append, Insert, Prepend, and Replace_Element that have a formal parameter of type Element_Type perform indefinite insertion (see A.18). Add after A.18.13(8/2) (Containers.Indefinite_Hashed_Maps): * The operations Include, Insert, Replace, and Replace_Element that have a formal parameter of type Element_Type perform indefinite insertion (see A.18). AARM Discussion: Some of the named operations also have a formal of the indefinite formal type Key_Type and perform indefinite insertion using that value, but it's sufficient to mention the formal of type Element_Type. Add after A.18.14(8/2) (Containers.Indefinite_Ordered_Maps): * The operations Include, Insert, Replace, and Replace_Element that have a formal parameter of type Element_Type perform indefinite insertion (see A.18). AARM Discussion: Some of the named operations also have a formal of the indefinite formal type Key_Type and perform indefinite insertion using that value, but it's sufficient to mention the formal of type Element_Type. Add after A.18.15(4/2) (Containers.Indefinite_Hashed_Sets): * The operations Include, Insert, Replace, Replace_Element, and To_Set that have a formal parameter of type Element_Type perform indefinite insertion (see A.18). AARM Ramification: This includes the procedure Replace declared in the nested generic package Generic_Keys, as well as the routines declared directly in the Containers.Indefinite_Hashed_Sets package. Add after A.18.16(4/2) (Containers.Indefinite_Ordered_Sets): * The operations Include, Insert, Replace, Replace_Element, and To_Set that have a formal parameter of type Element_Type perform indefinite insertion (see A.18). AARM Ramification: This includes the procedure Replace declared in the nested generic package Generic_Keys, as well as the routines declared directly in the Containers.Indefinite_Ordered_Sets package. Add after A.18.17(7/3) (Containers.Indefinite_Multiway_Trees): * The operations Append_Child, Insert_Child, Prepend_Child, and Replace_Element that have a formal parameter of type Element_Type perform indefinite insertion (see A.18). Modify A.18.18(39/3) (Containers.Indefinite_Holders): Returns a nonempty holder containing an element initialized to New_Item. {To_Holder performs indefinite insertion (see A.18).} Modify A.18.18(47/3) (Containers.Indefinite_Holders): Replace_Element assigns the value New_Item into Container, replacing any preexisting content of Container{; Replace_Element performs indefinite insertion (see A.18)}. Container is not empty after a successful call to Replace_Element. !discussion Randy wrote the following as background for this AI: We want to be able to write the implementation of containers packages in Ada, and we expect the implementation to use allocators. As such, it would be odd if some of the reasons that those allocators could fail were not reflected in the specification. A grocery list of considerations for this solution: (1) The problem occurs for any indefinite container, and occurs anytime an element is created in a container. That is not just Replace_Element but also Insert_Element and Append_Element (and possibly others, I didn't check carefully). That means that there are a number of places that we need new rules. (2) Indefinite containers are just a "simple" modification of the definite ones. Not sure if we have to modify the definite containers to deal with this or not (most of the complex rules are designed to apply to all of the container forms). In particular, I cannot be sure that it is impossible to cause the access discriminant check to fail for a definite subtype, as it applies to parts and constrained subtypes. Therefore, it would be safer to cover all containers, even though the check is unlikely to fail in a definite container. (3) The idea of repeating the rules for accessibility for an allocator gives me uncontrollable shakes. We'd never get the right; they'd always be a version behind the allocator rules. We have to find some way to explain this in terms of a hypothetical allocator. The best I can do would be something like: "Program_Error is propagated by Replace_Element if an initialized allocator for the element value where the access type designates the element type and is declared at the point of the instantiation of the container package would fail an accessibility check." This is too hard to parse, I fear. (4) We probably don't need any static rules for this problem. For an allocator of a generic formal type used in a generic body, these rules are checked only dynamically. The implementation of the container can (and ought to) avoid putting any allocators into the specification. (5) This check might be very expensive to implement. But the implementability should be no easier or harder than the checks for any allocator given in a generic body. Whether *any* of these checks are really implementable is the subject of AI12-0016-1, and if we make changes based on that AI, they should apply here, too. (6) It would be nice to have some sort of blanket rule that covers all container types and operations, but we rarely do that for the containers and it is not at all clear how it could be written in order to ensure that the right routines are covered and not any others. -------------- The checks are only required on certain operations declared within certain instances of the indefinite containers. Specifically, they're needed when the actual types for the indefinite formal types (the Element_Type and Key_Type types) are class-wide types or indefinite subtypes with access discriminants, and for the operations that have parameters of those actual types that create and initialize container elements using those parameters. Those are the cases where dangling references could potentially be created, and are precisely the cases where an implementation that uses access types and allocators would naturally apply the accessibility checks required for allocators in subclause 4.8. Unfortunately there doesn't seem to be a simple way to characterize the set of operations (for example, it's a different set in each indefinite container), which is why the subclause that defines each of the indefinite containers gives a list of the operations that perform indefinite allocation. Of course, the downside of specifically identifying the operations is that when any new such operations are added, the list will need to be updated to include them. One might wonder whether it's possible to stream in something whose accessibility is too shallow for the container. The check is against the element type of the container instance, and the contents have to live at least as long as that element type. Thus, anything we can stream out has already been checked. And thus anything that we can stream in is already OK. (Recall that we only promise to be able to stream in stuff that we stream out, not anything in general.) And we don't promise any extra interoperability for streaming of indefinite containers. (We do for the bounded and unbounded forms, but that doesn't apply to the indefinite forms.) If there were an interoperability promise, a less nested instance could cause trouble. !example Here's an example of how such violations can occur for instantiations of indefinite containers with class-wide element types: with Ada.Containers.Indefinite_Holders; with Ada.Text_IO; use Ada.Text_IO; procedure Dangling_Container is package Pkg is type Abst is abstract tagged null record; procedure Print_Obj (Obj : Abst) is abstract; end Pkg; use Pkg; package Holder is new Ada.Containers.Indefinite_Holders (Element_Type => Abst'Class); Factory : Holder.Holder := Holder.Empty_Holder; procedure Set_Factory is type Deeper_Type is new Pkg.Abst with record C : Integer; end record; procedure Print_Obj (Obj : Deeper_Type); A : Deeper_Type := (C => 123); procedure Print_Obj (Obj : Deeper_Type) is begin Put_Line ("In Print_Obj for Deeper_Type, Obj.C =" & Integer'Image (Obj.C)); A := Obj; -- Assign to possibly nonexistent object; may damage stack end Print_Obj; begin Factory.Replace_Element (A); -- Raises Program_Error because of new rules end Set_Factory; begin Set_Factory; Print_Obj (Factory.Element); -- The program should never get this far! Put_Line ("Returned from call to out of scope primitive, ending program"); end Dangling_Container; and here's a program illustrating the access discriminant case: with Ada.Containers.Indefinite_Holders; with Ada.Text_IO; use Ada.Text_IO; procedure Dangling_Acc_Discrim is type Acc_Discrim_Rec (D : access Integer) is record C : Integer; end record; package Holder is new Ada.Containers.Indefinite_Holders (Element_Type => Acc_Discrim_Rec); Factory : Holder.Holder := Holder.Empty_Holder; procedure Set_Factory is Aliased_Int : aliased Integer := 123; Nested_Obj : Acc_Discrim_Rec (D => Aliased_Int'access); begin Nested_Obj.C := 456; Factory.Replace_Element (Nested_Obj); -- Raises Program_Error because of new rules end Set_Factory; procedure Print_Obj (Obj : Acc_Discrim_Rec) is begin Put_Line ("In Print_Obj, Obj.D.all =" & Integer'Image (Obj.D.all) & ", Obj.C =" & Integer'Image (Obj.C)); Obj.D.all := Obj.D.all + Obj.C; -- Assignment to nonexistent object might damage stack end Print_Obj; begin Set_Factory; Print_Obj (Factory.Element); Put_Line ("After first call to Print_Obj"); Print_Obj (Factory.Element); Put_Line ("After second call to Print_Obj"); end Dangling_Acc_Discrim; !corrigendum A.18(5/3) @dinsa When a formal function is used to provide an ordering for a container, it is generally required to define a strict weak ordering. A function "<" defines a @i if it is irreflexive, asymmetric, transitive, and in addition, if @i < @i for any values @i and @i, then for all other values @i, (@i < @i) or (@i < @i). @dinss @s8<@i> Certain subprograms declared within instances of some of the generic packages presented in this clause are said to @i. These subprograms are those corresponding (in the sense of the copying described in subclause 12.3) to subprograms that have formal parameters of a generic formal indefinite type and that are identified as performing indefinite insertion in the subclause defining the generic package. If a subprogram performs indefinite insertion, then certain run-time checks are performed as part of a call to the subprogram; if any of these checks fail, then the resulting exception is propagated to the caller and the container is not modified by the call. These checks are performed for each parameter corresponding (in the sense of the copying described in 12.3) to a parameter in the corresponding generic whose type is a generic formal indefinite type. The checks performed for a given parameter are those checks explicitly specified in subclause 4.8 that would be performed as part of the evaluation of an initialized allocator whose access type is declared immediately within the instance, where: @xbullet is that of the parameter; and> @xbullet @xbullet !corrigendum A.18.11(8/2) @dinsa @xbullet @dinst @xbullet !corrigendum A.18.12(7/2) @dinsa @xbullet @dinst @xbullet !corrigendum A.18.13(8/2) @dinsa @xbullet @dinst @xbullet !corrigendum A.18.14(8/2) @dinsa @xbullet @dinst @xbullet !corrigendum A.18.15(4/2) @dinsa @xbullet @dinst @xbullet !corrigendum A.18.16(4/2) @dinsa @xbullet @dinst @xbullet !corrigendum A.18.17(7/3) @dinsa @xbullet @dinst @xbullet !corrigendum A.18.18(39/3) @drepl @xindent @dby @xindent !corrigendum A.18.18(47/3) @drepl @xindent @dby @xindent !ASIS No ASIS effect. !ACATS test ACATS C-Tests should be constructed to check that the required checks are made (particularly in cases like the examples -- where the inserted object would have been dangling if the check is not made). !appendix From: Gary Dismukes Sent: Thursday, June 7, 2012 1:15 AM A recent problem report from an AdaCore customer caused me to notice what seems to be a hole in the indefinite container semantics. The customer was using the Indefinite_Holders container, instantiating it with a class-wide type, and saving the value of an object of a more deeply nested tagged type in a container of the outer-level instance (via a call to Replace_Element). They ran into an accessibility violation in one of their own functions that returned a call to the holder's Element function. Although this failed check appears to be correct behavior, it occurred to me that the accessibility error should have been detected earlier, at the call to Replace_Element. The GNAT implementation of Replace_Element uses an allocator (not too surprisingly), and that allocator should have resulted in an accessibility violation, per the first rule in 4.8(10.1/3). That is arguably just a bug that needs to be fixed, however there doesn't appear to be anything in the RM that actually specifies that a call to an operation such as Replace_Element should raise an exception if passed an object of a too-deep type. In whatever way that operation is implemented, whether in Ada using an allocator, or in some other language by some other means, such calls should fail, because otherwise it would be possible to store a value of a type whose scope has exited within a longer-lived container, and that surely shouldn't be permitted. (Such an object within a container could be referred to as "dangling", in that its tag refers to a type that no longer exists.) So, it seems that this is a real vulnerability that the language should address. A related case can arise for types with access discriminants (a case raised by Steve), where violations of the second rule of 4.8(10.1/3) could occur, but again there's nothing in the semantics of indefinite containers that would appear to prevent such a violation. Assuming it's agreed that this is a real RM gap, then an AI should be created, and it's perhaps a candidate for the agenda for the upcoming meeting (if you're short on agenda items:-). Here's an example of how such violations can occur for instantiations of indefinite containers with class-wide element types: with Ada.Containers.Indefinite_Holders; with Ada.Text_IO; use Ada.Text_IO; procedure Dangling_Container is package Pkg is type Abst is abstract tagged null record; procedure Print_Obj (Obj : Abst) is abstract; end Pkg; use Pkg; package Holder is new Ada.Containers.Indefinite_Holders (Element_Type => Abst'Class); Factory : Holder.Holder := Holder.Empty_Holder; procedure Set_Factory is type Deeper_Type is new Pkg.Abst with record C : Integer; end record; procedure Print_Obj (Obj : Deeper_Type); A : Deeper_Type := (C => 123); procedure Print_Obj (Obj : Deeper_Type) is begin Put_Line ("In Print_Obj for Deeper_Type, Obj.C =" & Integer'Image (Obj.C)); A := Obj; -- Assign to possibly nonexistent object; may damage stack end Print_Obj; begin Factory.Replace_Element (A); -- This call should presumably fail end Set_Factory; begin Set_Factory; Print_Obj (Factory.Element); -- The program should never get this far! Put_Line ("Returned from call to out of scope primitive, ending program"); end Dangling_Container; and here's a program illustrating the access discriminant case: with Ada.Containers.Indefinite_Holders; with Ada.Text_IO; use Ada.Text_IO; procedure Dangling_Acc_Discrim is type Acc_Discrim_Rec (D : access Integer) is record C : Integer; end record; package Holder is new Ada.Containers.Indefinite_Holders (Element_Type => Acc_Discrim_Rec); Factory : Holder.Holder := Holder.Empty_Holder; procedure Set_Factory is Aliased_Int : aliased Integer := 123; Nested_Obj : Acc_Discrim_Rec (D => Aliased_Int'access); begin Nested_Obj.C := 456; Factory.Replace_Element (Nested_Obj); -- This call should presumably fail end Set_Factory; procedure Print_Obj (Obj : Acc_Discrim_Rec) is begin Put_Line ("In Print_Obj, Obj.D.all =" & Integer'Image (Obj.D.all) & ", Obj.C =" & Integer'Image (Obj.C)); Obj.D.all := Obj.D.all + Obj.C; -- Assignment to nonexistent object might damage stack end Print_Obj; begin Set_Factory; Print_Obj (Factory.Element); Put_Line ("After first call to Print_Obj"); Print_Obj (Factory.Element); Put_Line ("After second call to Print_Obj"); end Dangling_Acc_Discrim; **************************************************************** From: Tucker Taft Sent: Thursday, June 7, 2012 11:05 AM > A recent problem report from an AdaCore customer caused me to notice > what seems to be a hole in the indefinite container semantics. The > customer was using the Indefinite_Holders container, instantiating it > with a class-wide type, and saving the value of an object of a more > deeply nested tagged type in a container of the outer-level instance > (via a call to Replace_Element). They ran into an accessibility > violation in one of their own functions that returned a call to the > holder's Element function. Although this failed check appears to be > correct behavior, it occurred to me that the accessibility error > should have been detected earlier, at the call to Replace_Element. ... I agree we should say something. The idea is that a container is roughly equivalent to the collection associated with an access type declared at the same level as the container type, and inserting an object in a container is analogous to an allocator, and the same kinds of accessibility checks should apply. **************************************************************** From: Randy Brukardt Sent: Thursday, June 7, 2012 11:39 PM > > A recent problem report from an AdaCore customer caused me to notice > > what seems to be a hole in the indefinite container semantics. The > > customer was using the Indefinite_Holders container, instantiating > > it with a class-wide type, and saving the value of an object of a > > more deeply nested tagged type in a container of the outer-level > > instance (via a call to Replace_Element). Good to see someone using the Indefinite containers as they were intended, even if they managed to misuse them a bit. > > ... They ran into an accessibility violation in one of their own > > functions that returned a call to the holder's Element function. > > Although this failed check appears to be correct behavior, it > > occurred to me that the accessibility error should have been > > detected earlier, at the call to Replace_Element. ... > > I agree we should say something. The idea is that a container is > roughly equivalent to the collection associated with an access type > declared at the same level as the container type, and inserting an > object in a container is analogous to an allocator, and the same kinds > of accessibility checks should apply. I agree as well, although exactly *what* we need to say is not that obvious. Several points: (1) The problem occurs anytime an element is created in the container. That is not just Replace_Element but also Insert_Element and Append_Element (and possibly others, I didn't check carefully). That means that there are a number of places that we need new rules. (2) Indefinite containers are just a "simple" modification of the definite ones. Not sure if we have to modify the definite containers to deal with this or not (most of the complex rules are designed to apply to all of the container forms). (3) The idea of repeating the rules for accessibility for an allocator gives me uncontrollable shakes. We'd never get the right; they'd always be a version behind the allocator rules. We have to find some way to explain this in terms of a hypothetical allocator. Obviously, the easiest way to deal with this is some sort of blanket rule that covers all container types, but we rarely do that for the containers and it is not at all clear how it could be written in order to ensure that the right routines are covered. So this looks difficult but necessary (and I'm not going to try to come up with wording before the meeting). **************************************************************** From: Gary Dismukes Sent: Monday, December 3, 2012 12:53 AM This AI was worked on jointly by Steve and me, and addresses the issue of specifying that accessiblity checks get done for certain operations of indefinite containers. [Followed by version /02 of the AI - Editor.] **************************************************************** From: Gary Dismukes Sent: Monday, June 10, 2013 1:45 AM Attached is the revision of AI12-0035 [This is version /03 of this AI - Editor], following the request of the last ARG meeting, eliminating the list of affected operations in A.18 and naming the sets of operations that perform indefinite allocation in the subclauses of each of the indefinite containers. I added those to the !wording as Dynamic Semantics, but perhaps they should simply be part of the Static Semantics in those subclauses, since they just state a property of the operations. I also revised the last paragraphs of the !discussion to reflect the choice of putting a list with each indefinite container, but I left the part at the beginning with the "grocery list" of considerations that Randy wrote. I'm not sure if that should be retained as is or rewritten. I also added a paragraph at the end of !discussion discussing the question about streams that was included in the minutes, explaining why streams aren't a problem. **************************************************************** From: Randy Brukardt Sent: Monday, June 10, 2013 4:56 PM FYI, we almost never put the semantics of language-defined packages into Dynamic Semantics, it always goes into Static Semantics. Don't ask me to explain that (because I can't), but that's the way the RM is structured. So these should just be additional bullets at the end of the existing list. ****************************************************************