!standard A.18.18(47/3) 12-12-02 AI12-0035-1/02 !class binding interpretation 12-06-08 !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 an access type associated with 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 at the end of A.18: Certain subprograms declared within instances of some of the generic packages presented in this clause are said to "require indefinite allocation". These subprograms are those corresponding (in the sense of the copying described in section 12.3) to the following subprograms that have formal parameters of a generic formal indefinite type: Containers.Indefinite_Doubly_Linked_Lists.Append Containers.Indefinite_Doubly_Linked_Lists.Insert Containers.Indefinite_Doubly_Linked_Lists.Prepend Containers.Indefinite_Doubly_Linked_Lists.Replace_Element Containers.Indefinite_Hashed_Maps.Include Containers.Indefinite_Hashed_Maps.Insert Containers.Indefinite_Hashed_Maps.Replace Containers.Indefinite_Hashed_Maps.Replace_Element Containers.Indefinite_Hashed_Sets.Insert Containers.Indefinite_Hashed_Sets.Include Containers.Indefinite_Hashed_Sets.Replace Containers.Indefinite_Hashed_Sets.Replace_Element Containers.Indefinite_Hashed_Sets.To_Set Containers.Indefinite_Hashed_Sets.Generic_Keys.Replace Containers.Indefinite_Multiway_Trees.Append_Child Containers.Indefinite_Multiway_Trees.Insert_Child Containers.Indefinite_Multiway_Trees.Prepend_Child Containers.Indefinite_Multiway_Trees.Replace_Element Containers.Indefinite_Ordered_Maps.Include Containers.Indefinite_Ordered_Maps.Insert Containers.Indefinite_Ordered_Maps.Replace Containers.Indefinite_Ordered_Maps.Replace_Element Containers.Indefinite_Ordered_Multisets.Insert Containers.Indefinite_Ordered_Multisets.Replace_Element Containers.Indefinite_Ordered_Multisets.To_Set Containers.Indefinite_Ordered_Sets.Include Containers.Indefinite_Ordered_Sets.Insert Containers.Indefinite_Ordered_Sets.Replace Containers.Indefinite_Ordered_Sets.Replace_Element Containers.Indefinite_Ordered_Sets.To_Set Containers.Indefinite_Ordered_Sets.Generic_Keys.Replace Containers.Indefinite_Holders.Replace_Element Containers.Indefinite_Holders.To_Holder Containers.Indefinite_Vectors."&" Containers.Indefinite_Vectors.Append Containers.Indefinite_Vectors.Insert Containers.Indefinite_Vectors.Prepend Containers.Indefinite_Vectors.Replace_Element Containers.Indefinite_Vectors.To_Vector If a subprogram requires indefinite allocation, 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 no container is 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 section 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 initial value is the value 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. [Question: Do we need to worry about accessibility checks on container stream input in this AI?] [Editor's comment: This sounds suspiciously Bairdian. ;-)] AARM note: The phrase "explicitly specified" means those checks for which section 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 section 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. Discussion: We are doing two things here. 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. Following that second path, suppose that an implementation does declare such an access type and suppose further that the access type's collection's finalization has started. We want to allow Program_Error to be propagated in this case (as specified in 4.8(10.2/2,11.1/2)). !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 relected 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 section 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 we have given a list of them. An alternative would be to add wording to each such operation in its respective section, but that still requires identifying them, and would seem to add unnecessary verbiage. 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. !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); -- 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; !ACATS test ** TBD. !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.] ****************************************************************