!standard 6.1.3(0) 19-06-09 AI12-0240-6/03 !class Amendment 19-04-08 !status work item 19-04-08 !status received 19-04-07 !priority High !difficulty Hard !subject Global aspect and access types used to implement Abstract Data Types !summary We introduce the Compound and Internal aspects in order to tame the needed Global contracts for Abstract Data Types. These aspects allow treating the subordinate heap-allocated objects which are used internally to represent the ADT as though they were direct components of a compound object, for the purpose of checking Global contracts. We also augment the Glabal aspect to handle Implicit_Dereference functions and to allow X.all as an object_name to handle inherently indirect types like Text_IO.File_Type and *_Random.Generator. !problem Assuming that we have some sort of data-race checks (AI12-0267-1), it is important that the Global aspects of abstract data type (ADT) operations introduce as few conflicts as possible. In particular, the Global aspects of the container operations need to imply a minimal use of shared variables. Otherwise, they could not be used safely in any sort of multi-threaded situation. Currently, the only way to describe the dereferencing of an access object in the context of a Global aspect is by the "X.all", "access T", or "" forms of specification. The latter two of these will tend to lump together all objects of the same container type, when in fact two distinct objects of a container type almost certainly share no storage. We believe we need some better way to define the global side effects of ADT operations which reflects the true amount of data sharing, or lack thereof, between objects of an ADT that uses pointers internally. Furthermore, typically the access types used within the representation won't be declared in the visible part, so about the only recourse will be the "" form of Global aspect. Beyond concerns about data races, more general concerns about "aliasing" (that is, might two different names actually denote the same object at run time) are also relevant to almost any sort of static analysis. Pointers make the determination of possible aliasing much more difficult. It would be very valuable to adopt some approach to "taming" pointers so that aliasing can be more precisely determined, even in the presence of pointer-based data structures. Two related issues associated with providing useful Global aspects for operations of Abstract Data Types are that we don't have a good way of handling operations like Put on Text_IO.File_Type, because the parameter mode is IN but the state of the file is being changed, and we don't have a good way to deal with functions that return objects of an Implicit_Dereference type. !proposal Define the notion of a "compound" object which is an object whose "logical" representation includes its "root" object plus zero or more heap-resident "subordinate" objects. Allow an individual access object to have an "Internal" aspect which, if true, means that its dereferences are *not* considered Global effects, but are rather considered simply a way to reach various parts of the logical representation of some compound object. In addition to specifying the Internal aspect directly on an access object or component, an access subtype may be specified with Internal => True, in which case any object of the subtype has its Internal aspect by default True. A full type may be specified as Compound (i.e. aspect Compound => True), in which case it must be controlled or have only limited partial views. All objects of such a type are considered compound objects. We want these to be controlled or have only limited partial views, since the predefined assignment won't be implicitly copying all of the subordinate objects of the compound object. When checking the Global aspect of a subprogram, the compiler will ignore dereferences of an internal access object, so long as there is at least one compound object passed as a parameter of an enclosing callable entity, designated by an access parameter, or mentioned in the Global aspect for an enclosing callable entity and whose mode "covers" the kind of access being performed via the dereference. An "in out" or "out" mode, or "access" parameter covers any sort of access, while an "in" mode or "access constant" parameter covers only read accesses via the dereference. An internal access object is presumed to designate a (subordinate) object that is "reachable" from exactly one (root) compound object, though the implementation is not required to check for this (though some advanced implementation might attempt to verify this at compile time). We propose to augment the rules for the Global aspect of a function that returns an object of an Implicit_Dereference type, so that it must incorporate the effects of dereferencing the result, including reading or updating (if permitted) the designated object, if these effects are over and above what is implied by the aliased parameters of the function. The function returning the implicitly-dereferenceable result is in a better position to specify these effects, and usually the aliased parameters already cover the possible effects so nothing needs to be added to the Global aspect. This permits the caller of such a function to always dereference the result without worrying about whether it is covered by its own Global aspect, since it already incorporates the effects of calling the function. We further augment the Name Resolution rules of the Global aspect to permit an object_name to be of the form prefix.ALL, where the prefix statically denotes an object, including possibly a parameter, of an access or composite type, with the meaning being the set of objects designated by any part of the denoted object. This is useful for operations like Text_IO.Put_Line and Discrete_Random.Random. We considered various alternatives to using ".all" for composite types, because there was concern that this might be confusing. Unfortunately, none of these alternatives worked out as we had hoped. Here are the rejected alternatives: 1. Have a separate aspect "Modifies" which would be used to indicate that an "in" parameter, like File in Text_IO.Put_Line. * This was a problem because "Modifies" traditionally indicates *all* of the objects modified by a subprogram, including both parameters and globals. (For reference, look up "Requires Modifies Effects.") We wanted something that was additive to what had already been specified as parameter modes or the Global aspect. 2. Use a different name, such as "Updates" which we could define to be additive. * This was a problem because of generic formal subprograms, which already have 'Global and 'Nonblocking attributes so they can be combined into the corresponding aspects of a subprogram within the generic that calls the formal subprogram. We didn't want to have yet another attribute 'Updates on formal subprograms, which would need to be used on the off chance that the formal subprogram had one of these "modifiable" in parameters. 3. Use a global_mode_qualifier, analogous to "synchronized" such as "indirect," as in: Global => indirect in out File for Text_IO.Put_Line. * The wording was difficult, as currently an object_name used as a global_name is supposed to denote a global variable. To allow it to denote a formal parameter only if the qualifier "indirect" was present made the wording a bit of mess. Furthermore, the qualifiers (such as "synchronized") were defined as simply restricting the global set defined by the global_name, not totally changing its interpretation. Finally, the rule of 6.1.2(36/5) also became more complicated, since it said that a given entity shall be named only once in a global aspect. But with indirect, it would be reasonable to mention the same global entity twice, once with "indirect in out" and once with simply "in", for example. * There is also added complexity and potential redundancy, presuming we still wanted to be able to use ".all" for access parameters. So ultimately we decided to stick with using ".all" to indicate indirect update to something like a File_Type. One change we did make was to allow any composite type, in addition to access types, with ".all". Originally we had allowed only access and private types, but limiting something to private types always creates some issues, and at a minimum we would probably at least want to allow private extensions. Ultimately we decided to allow access types and any composite type. Effectively "X.all" can be seen as a short-hand for ".all" of each of the access-type parts of X, including those possibly not visible to the caller. !wording Modify RM 6.1.2(15/5): A global_name that does not have the reserved word ACCESS{, and is not an /object_/name of the form prefix.ALL,} shall resolve to statically denote an object, a package (including a limited view of a package), or an access-to-variable subtype.[Redundant: The subtype_mark of a global_name that has the reserved word ACCESS shall resolve to denote a subtype (possibly an incomplete type).]{ The prefix of a global_name of the form prefix.ALL shall resolve to statically denote an object [Redundant: (including a formal parameter)] of a composite type or an access-to-object type.} Modify RM 6.1.2(32/5): * object_name {that is not of the form prefix.ALL} identifies the specified global variable (or nonpreelaborable constant); {* object_name of the form prefix.ALL identifies the set of objects designated by any part of the object denoted by the prefix;} Modify RM 6.1.2(37/5): If an entity has a Global aspect other than in out all, then the associated operation(s) shall read only those variables global to the entity that are within the global variable set associated with the in, in out, or out modes, and the operation(s) shall update only those variables global to the entity that are within the global variable set associated with either the in out or out global_modes. This includes any calls occurring during the execution of the operation, presuming those calls read and update all global variables permitted by their Global aspect (or Global'Class aspect, if a dispatching call). {For the purposes of this check, if a function returns an object of a type for which the Implicit_Dereference aspect is True (see 4.1.5), the Global aspect of the function shall reflect the effects of dereferencing the result of the function, if these are over and above reads or updates of aliased formal parameters passed to the function. The effects to be reflected include reading the designated object, and updating the designated object in the case of an Implicit_Dereference result with an access-to-variable access discriminant.} {AARM Reason: The function is in a better position than the caller to enumerate the objects affected by dereferencing the result. Because the access discriminant is often of an anonymous type, there is no other place to declare these effects. In most cases, these effects will already be reflected in the aliased parameters passed to the function, so nothing need be added to the Global aspect for these.} Add the following new subclause: 6.1.3 Compound Objects and Internal Access Objects A /compound/ object is an object whose logical representation is composed of multiple physical objects. /Internal/ access objects are used to connect the various physical objects that make up such a compound object, and to navigate between these (/subordinate/) objects while manipulating a compound object. Static Semantics For an access-to-object subtype, or an object (including a component) of an access-to-object type, the following aspect is defined: Internal For an object (including a component), this specifies whether this object is an /internal access/ object. For an access subtype, this specifies the default for objects of the subtype. The default for the first subtype of an access type is False. The default for a subtype defined by a subtype_indication is the value of the Internal aspect of the subtype identified by the subtype_mark of the subtype_indication. An object of an access-to-object type that is not an internal access object, and is not the null literal or an allocator, is an /external access/ object. Redundant: [A reference to the Move attribute (see below) is an internal access object.] Discussion: Note that this aspect may be specified for an object of an anonymous access-to-object type. For a [Redundant: full] type, the following representation aspect is defined: Compound This specifies whether this type is a /compound/ type. An object of a compound type is a /compound/ object. The logical representation of a compound object is composed of the (/root/) compound object itself, and zero or more /subordinate/ objects connected to the root via internal access objects. Reason: We declare this to be a representation aspect so that it can't be given on partial views. Discussion: There might be more than one type of subordinate object comprising a compound object, and there might be multiple types of internal access objects connecting the various objects together. The root object itself might be a single (internal) access object. The following attribute is defined for a prefix X that denotes a variable that is an internal access object: X'Move X'Move saves a copy of the value of X, sets X to the null value, and then returns the saved value. The result of X'Move is an internal access object. An object created by an allocator is *reachable* from a compound object C if: * the object is designated by a part of C that is an internal access object; or * the object is designated by a part of an object reachable from C that is an internal access object. An object that is reachable from a compound object is called a /subordinate/ of that object. Legality Rules If Compound is specified to be True for a type, the type shall be controlled, or have only a limited partial view (if any). AARM Reason: We don't want a nonlimited partial view that is not controlled, because the predefined assignment is not going to do the right thing. We allow the full type to be nonlimited since we presume the implementor of the abstract data type knows what is needed to preserve the desired properties of the type. Requiring the full type to be limited would not really guarantee anything anyway, unless we require every subordinate object to also be limited, which could interfere with existing practice. Nothwithstanding what this Standard says elsewhere, a read of an object via a dereference of an internal access object is considered a read of some part of a visible compound object. Similarly, an update of an object via a dereference of an internal access object is considered a write of some part of a visible compound object. Such a read or update is allowed so long as there is at least one visible compound object that allows the read or update, and that compound object is either: * local to the immediately enclosing entity in which the read or update occurs (including a formal parameter if it is a callable entity), or * is within the set of global objects identified as readable or updatable (as appropriate) by the Global aspect (see 6.1.2) of that entity. Ramification: Parameters of a subprogram are considered "local" for this purpose, and do not need to appear in the Global aspect for the subprogram. Thus, if one or more formal parameters of a subprogram are compound objects, the subprogram will allow any reads of dereferences of internal access types, and if any of those parameters are variables, any sort of dereference of an internal access will be allowed. In particular, nothing about the access type being dereferenced need appear in the Global aspect (as would normally be required). An external access value shall not be converted to an access subtype that has the Internal aspect True, nor be assigned to an internal access object. An internal access value of a pool-specific type shall not be converted to an access subtype that is also pool-specific and has the Internal aspect False, nor be assigned to an external access object of a pool-specific type. Ramification: We do not allow an external access value to be assigned or converted to be an internal access to ensure that internal access objects never point outside the compound object with which they are associated. We do not allow an internal access object to be assigned or converted to be an external access of a pool-specific type, as the presumption of a pool-specific type is that it only points to objects within its pool and never points at a component of another object. But given a compound object, an internal access object might in fact point to something that is logically considered a component of the compound object. Converting such an internal access to be a pool-specific external access would be misleading, since one might presume that such a pool-specific external access could not possibly be pointing at any part of a compound object whose type does not match the designated type of the external access. This might interfere with correct determination of whether a dereference of the external access might conflict with use of the compound object. Erroneous Execution Execution is erroneous if an object X is read or updated via a dereference of an internal access object, and at that point: * X is not reachable from a visible compound object that permits the given mode of access (taking restrictions imposed by Global aspects into account), or * X is reachable from two different compound objects neither of which is a subordinate of the other. !discussion The Compound and Internal aspects are designed to provide a minimal framework upon which more elaborate "ownership"-based mechanisms could be defined. As defined, Compound and Internal provide useful documentation of the fact that an Abstract Data Type is implemented using multiple physical objects connected via access objects. They also eliminate the need to "broadcast," within a Global aspect, the manipulation of pointers performed within a given operation on such an ADT. They impose minimal implementation burden, since the net effect is only to cause the implementation to ignore most dereferences of Internal access objects when checking for Global aspect violations. We believe this framework will remain useful, even as more elaborate ownership mechanisms are defined, because many users will choose to stick with existing implementation approaches that might not conform to such ownership rules. But they would still like to get the benefit of using Global aspects, which this minimal framework makes very easy. We have chosen the term "Internal" to refer to access objects that are used to connect the various parts of a conceptual "Compound" object together, as well as to navigate between then. The term "Local" was already used for another purpose and was felt to be potentially confusing. We considered the term "Connector," but it was not felt to be as appropriate for pointers used for navigating within a compound object. We have tried to pare the erroneous execution rules down to the bare minimum. We incorporate the restriction to heap-resident subordinate objects in our definition of "reachable." We try to impose as few restrictions as possible, because we would like this framework to support various approaches to implementing compound types. In particular, we allow Internal => True to be specified on individual access objects, to permit approaches that use anonymous access types to walk the various subordinate objects of a Compound object, and for cases where the same access type is used for some objects or subtypes that are internal, and for some that are not. We allow the "root" compound object to be a single (internal) access object. We allow the "full" compound type to be nonlimited, even if it is not controlled, so long as the partial view is limited, since we trust the implementor of the ADT to do the right thing when copying such objects. Particular implementations could provide more restrictive versions of this overall approach, either with a pragma Restrictions or simply by defining additional aspects that imply a more restrictive model. If the implementation defines additional aspects, the presence of those aspects on a given object or type could imply appropriate defaults for the Compound or Internal aspects, freeing the user from specifying both the implementation-specific aspect and these standard Compound and Internal aspects on a single entity. This AI is focused on making Global aspects more usable for operations on abstract data types. As such, in addition to the introduction of the Compound and Internal aspects, we have made two modest augmentations to the Global aspect itself. The first is to allow global_names of the form "X.all". These were allowed syntactically, but were not allowed by the Name Resolution rules, because the Name Resolution rules required that the object_name statically denote an object. X.all does not statically denote anything. However, X.all is useful for indicating that the object designated by, for example, an access parameter is read or updated. Also, by allowing the prefix to denote an object of a composite type (including a private type), we can handle the case of types like Text_IO.File_Type as used by Text_IO.Put, where clearly there is an implicit level of indirection of the File IN parameter, given that Put alters the column associated with the file, and the eventual content of the external file. We considered introducing a Modifies or Updates aspect for this case, or using an "indirect" global_mode_qualifier, but for the reasons given in the !proposal, allowing X.all seemed like the better approach. The second addition is to require that the implicit dereference of the call on a function that returns a result of an Implicit_Dereference type be covered by the Global aspect of the function itself, if the mode(s) of the aliased parameter(s) of the function itself do not already cover the effect. In the typical case of a function that returns an Implicit_Dereference result, there will be an aliased parameter and the object designated by implicitly dereferencing the result is a part of that parameter. It would only be when such a function returns an Implicit_Dereference object that points elsewhere that the function would need to explicitly identify that designated object with its Global aspect. !examples For a singly linked list type, we might have declarations like the following in the private part: private type Node; type Node_Ptr is access Node; type Node is limited record Elem : Element_Type; Next : Node_Ptr with Internal; end record with Compound; type List is ... with record Head : Node_Ptr with Internal; ... end record with Compound; (Note: List is the visible private type, which must have a limited partial view, or be controlled.) If the implementation wanted to have a free list of nodes, it could declare the following (probably as a component of a protected object with Compound True): Free_List : Node_Ptr with Internal; Then moving a Node_Ptr to this object would have the effect of moving the designated Node to be subordinate of the global protected object (dereferencing such a pointer would require the Global aspect to mention this protected object). With the above Compound and Internal aspect specifications, it is possible to walk the linked list in some operation on a List object, without having to mention in the Global aspect for the operation, any of the dereferences involved in the walk, so long as the List object is covered either as a parameter or as a declared Global. We could have specified "with Internal" on the type declaration for Node_Ptr, and then the "with Internal" on the individual components of type Node_Ptr could have been omitted. We provide a doubly-linked list example after the Hashed_Maps example given below. --- Here is a more complex example, for a hashed map package: generic ... package Hashed_Maps is -- Here we show a typical hashed Map, and various operations whose -- Global aspects take advantage of Compound and Internal aspects type Map is private with ...; type Cursor is private; ... procedure Insert (Container : in out Map; Key : Key_Type; Element : Element_Type) -- Inserts an element with the given Key into the map with Global => Key_Type'Global & Element_Type'Global; -- We have to allow for global side-effects of copying Key -- and Element, but we don't have to mention dereferencing -- ownership-based pointers that occur within the Container. function Find (Container : Map; Key : Key_Type) return Cursor -- Returns a cursor identifying the element associated with the Key with Global => null; -- despite internal access value derefs function Element (Container : Map; Position : Cursor) return Element_Type -- Takes a Cursor and the map and returns the contents of the element -- at that cursor. with Global => Element_Type'Global; -- We have to allow for global side-effects of copying an -- Element, but we don't have to mention dereferencing -- ownership-based pointers that occur within the Container. type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; function Reference (Container : aliased in out Map; Key : Key_Type) return Reference_Type with Global => null; -- Returns a reference to the element associated with the given Key -- allowing it to be updated upon return. -- The Global aspect being null means that dereferencing -- the returned reference only reads or updates some part of the -- compound object Container, given the change proposed in 6.1.2 above -- for the meaning of the Global aspect of such a function. ... private type Node; type Node_Ptr is access Node with Internal; -- All Node_Ptrs are by default internal access objects type Node is limited record Key : Key_Type; Element : aliased Element_Type; Next : Node_Ptr; -- This defaults to being an internal access object end record; type Table is array(Natural range <>) of Node_Ptr with Compound; -- Specifying Table as Compound is optional -- but it will allow us to use a parameter of type -- Table to "cover" any internal access object dereferences. type Table_Ptr is access Table with Internal; -- All Table_Ptrs are by default internal access objects Initial_Size : constant := 19; -- a modest-sized prime number type Map is new Finalization.Controlled with record Backbone : Table_Ptr := new Table(0 .. Initial_Size - 1) -- This is by default an internal access object, thanks -- to its type having Internal specified. Count : Natural := 0; end record with Compound; -- This is the crucial specification of Compound -- since there will be Map parameters that need -- to "cover" dereferences of Node_Ptrs and Table_Ptrs. type Map_Const_Ptr is access constant Map; -- Values of this type are used to identify the container -- associated with a given Cursor. -- It is *not* an internal access object, so cannot be -- dereferenced without being mentioned in Global, -- but can be compared (which is all we are doing with it in -- the Element function below). type Cursor is record Container : Map_Const_Ptr := null; Node : Node_Ptr; -- This is an Internal access object, but can only -- be dereferenced when inside the scope of a Compound -- object (Cursor itself is not Compound). end record; type Reference_Type (Element : not null access Element_Type) is null record with Implicit_Dereference => Element; ... end Hashed_Maps; package body Hashed_Maps is ... procedure Insert (Container : in out Map; Key : Key_Type; Element : Element_Type) is -- Inserts an element with the given Key into the map Index : Natural := Hash (Key) mod Container.Backbone'Length; First : Node_Ptr renames Container.Backbone (Index); -- rename of an internal access object. -- We can dereference because Container is in scope (and writable) begin if First /= null then declare Walker : Node_Ptr := First; -- Because of its type, Walker is also considered -- an internal access object, and can be dereferenced -- in the scope of a Compound object (such as Container) -- without having to mention the dereference in a Global -- aspect. begin while Walker /= null loop -- Dereferences, including updates, are OK below since -- we have a writable Compound object (Container) in scope. if Walker.Key = Key then -- Replace Walker.Element := Element; return; -- All done end if; Walker := Walker.Next; end loop; end; end if; -- Insert at head of chain First := new Node'(Key => Key, Element => Element, Next => First'Move); -- We are initializing the internal access object First using -- an allocator, and the internal access component Next -- using the 'Move attribute reference. Container.Count := @ + 1; end Insert; function Find (Container : Map; Key : Key_Type) return Cursor is -- Returns a cursor identifying the element associated with the Key Index : Natural := Hash (Key) mod Container.Backbone'Length; Walker : Node_Ptr := Container.Backbone (Index); begin while Walker /= null loop -- Can dereference Walker below because Container is in scope, -- but cannot update object designated by Walker because -- Container is an IN parameter. if Walker.Key = Key then -- Found it return Cursor '(Container => Container'Unchecked_Access, Node => Walker); end if; Walker := Walker.Next; -- OK to assign an internal access object (Walker.Next) -- to an internal access object (Walker). end loop; return Cursor '(Container => Container'Unchecked_Access, Node => null); end Find; function Element (Container : Map; Position : Cursor) return Element_Type -- Takes a Cursor and the map and returns the contents of the element -- at that cursor. pragma Assert (Position.Container = Container'Unchecked_Access); -- Make sure the cursor matches the map -- May not dereference Position.Container without mentioning it -- in Global, since it is *not* an internal access object, but it -- is fine to compare it against Container'Unchecked_Access Node : constant Node_Ptr := Position.Node; begin return Node.Element; -- dereference of Node need not be mentioned in Global aspect -- thanks to it being an internal access object end Element; function Reference (Container : aliased in out Map; Key : Key_Type) return Reference_Type is -- Returns a reference to the element associated with the given Key -- allowing it to be updated upon return. -- NOTE: Unlike the standard Ada Map containers, this function creates a -- default-initialized element indexed by Key if such an element doesn't -- already exist. Hence "Map[Key] := X;" can have the effect -- of expanding the Map if Map[Key] doesn't already exist. Index : Natural := Hash (Key) mod Container.Backbone'Length; First : Node_Ptr renames Container.Backbone (Index); begin if First /= null then declare Walker : Node_Ptr := First with Owner => Container; begin while Walker /= null loop if Walker.Key = Key then -- Found it return Reference_Type'(Element => Walker.Element'Access); end if; Walker := Walker.Next; end loop; end; end if; -- Insert a default-init'ed element at head of chain First := new Node'(Key => Key, Element => <>, Next => First'Move); -- We use 'Move to produce an internal access value to initialize -- the Next component in the newly created Node. -- Note that the semantics of 'Move are that the value is -- returned after nulling out the object denoted by the prefix. Container.Count := @ + 1; -- Return a reference to the default-init'ed element return Reference_Type'(Element => First.Element'Access); end Reference; end Hashed_Maps; --- Here is an example of a doubly-linked list, using multiple internal access components in a single node. type Node; type Node_Ptr is access Node with Internal; -- By default all objects of Node_Ptr type are internal access objects type Node is limited record Elem : Element_Type; Prev : Node_Ptr; Next : Node_Ptr; end record; type List; type List_Const_Ptr is access constant List; type Cursor (List : List_Const_Ptr := null) is record Node : Node_Ptr; end record; type List is limited ... with record First : Node_Ptr; Last : Node_Ptr; -- points to last element of list, if any ... end record with Compound; ... procedure Insert (Container : in out List; Before : in Cursor; New_Item : in Element_Type) is -- Insert New_Item into list, before the item identified -- by Before. If Before is No_Element, then append to list. pragma Assert (Before.List = Container'Unchecked_Access or else Before.List = null); -- Make sure we have a valid Cursor New_Node : constant Node_Ptr := new Node'(Elem => New_Item, Prev => null, Next => null); begin if Before.Node = null then -- Insert at end if Container.Last = null then -- List is empty; New_Node becomes the first and last element pragma Assert (Container.First = null); -- Verify existing linkages Container.First := New_Node; Container.Last := Container.First; else -- Append to end of list, and update Tail_Cursor declare Last : constant Node_Ptr := Container.Last; begin Last.Next := New_Node; Last.Next.Prev := Last; Container.Last := Last.Next; end; end if; else -- Add immediately prior to "Before" declare Follower : constant Node_Ptr := Before.Node; Preceder : constant Node_Ptr := Follower.Prev; begin if Preceder = null then -- This is a new first element of list pragma Assert (Container.First = Follower); -- Verify proper existing linkages New_Node.Next := Container.First'Move; -- Assign the internal access object "Next" of the new -- node, effectively attaching remainder of list to it. Container.First := New_Node; -- Link the new node as new head of list Follower.Prev := Container.First; -- Set up new "back" pointer in Follower else -- Inserting into the middle of the list pragma Assert (Preceder.Next = Follower); -- Verify proper existing linkages New_Node.Next := Preceder.Next'Move; -- Assign the internal access object of the new node -- effectively attaching the remainder of list to it. Preceder.Next := New_Node; -- Link the new node into the list Preceder.Next.Prev := Preceder; -- Set up the "back" pointer for new node. Follower.Prev := Preceder.Next; -- Set up new "back" pointer in Follower end if; end; end if; end Insert; To illustrate a use of the Global => ... prefix.ALL, here is what the Global aspect for Text_IO.Put might be: procedure Put (File : in File_Type; Item : String) with Global => in out File.all; !ASIS No new syntax, though the Name_Resolution is less restrictive for the Global aspect, so unclear whether any new ASIS APIs are needed. !ACATS test ACATS B- and C-Tests are needed to check that the new capabilities are supported. !appendix From: Richard Wai Sent: Tuesday, April 9, 2019 12:15 AM Wanted to get infront with some of my thoughts on this one ahead of tomorrow First a small typo - 6.1.3 -> Static Semantics -> Compund aspect -> Discussion: " There might be more than one local access type used with a single compound type, and more than one compound type can [used]{use} a single access type." Next, I have two small ideas, and one crazy one: 1. The legality rules, together with the static semantics, require that Compound types have subcomponents of a "Local" access type. However, since Local is a Boolean aspect, it is easy to have one "local" access type be owned by different Compound types. I don't see any check for that mentioned, so it should probably be stated in the legality rules. However, I think it might be better if the "Local" aspect be a subtype mark for the associated Compound type. I.e. type My_ADT is limited private with Compound; type ADT_Node_Access is access My_Data with Local => My_ADT; This way the compiler can statically check that for any given "local" access type object, the associated "Compound" object is always the appropriate type. It also makes "Local" work better (if we want to stick with that) since it naturally reads "local to/for My_ADT" (at least to me). I think this approach brings some intuitive readability to the concept. Also, Local (see my second point) reads much more intuitively: type ADT_Node_Access is access My_Data with Subordinate => My_ADT; This reads as if My_ADT is the "subordinate" of the access type! 2. If #1 is not acceptable, then I'm left pretty uncomfortable with the use of "Local". I don't think this really captures the purpose or meaning of access types with that aspect. I understand that Local makes sense in relation to "Global", but it seems to be more about defining the "glue" of an ADT. I just think it might be better to make that the key idea instead of framing it against Global, which could possibly be confusing. When we're talking about global variables, local variables would usually refer to something declared in the immediately enclosing sequence of statements, but that is nothing like what this aspect means. I'd suggest "Subordinate" instead of Local. 3. I find the laissez-faire dismissal of potential "mistakes" leading to erroneous execution to be concerning. I've had this discomfort with container types. I understand that these facilities are intended for the implementation of the standard container packages, but they are useful generally. Where Ada has originally been very strict on checking for programmer mistakes (unlike most other languages), the container library, and this AI's dismissal of "mistakes" that cause erroneous execution, seems very un-Ada-like. "Objects of a local access subtype are expected to be reachable from exactly one object of a compound type. They can be reachable from other objects as well, so long as as the "parent" compound object is also available. We do not try to detect violations of this rule, but any such violations make execution erroneous, so neither clients nor compilers need to worry about such mistakes." To me this reads "if the programmer needs to implement their ADT correctly, and if they don't, it's their fault". That to me is very C-like "undefined behaviour", and I'm fundamentally against that approach. I recognise that this is a difficult problem, and that efficient containers are a priority, but I also think that Ada has a pedigree worth fighting for in this space. Users will use container types to build specialized ADTs because it is extremely useful (We've done this a few times). ADTs can be complex, and can be error-prone to develop. I think we should really think more carefully about adding at least some checking. By explicitly associating a "Local" access type with a "Compound" type, there might be more opportunities for efficient checking of the more common mistakes (such as cursor copying). **** My radical and half-baked idea **** 1. Restrict "Local" access type to be pool-specific only. 2. Change "Compound" to "Compound_With_Subpools", which then takes an object of Root_Storage_Pool_With_Subpools'Class. The type owns the pool - no other "compound" type may use the same pool. - compile time check 3. Local access types _shall_ also designate the same pool as the defined for the Compound type. - compile-time check. 4. Initialization of any compound type makes a call to the owned pool's Create_Subpool to obtain a subpool specific to that Compound object. The handle for this subpool can be obtained by a new aspect 'Compound_Subpool. 5. When using an allocator for a "Local" access type, a subpool of the parent type's pool must be specified. - compile-time check 6. When allocating to a "Local" access type, the owner of the subpool must be writable from the innermost enclosing region from which the allocation is made. The object owning the subpool can be identified from the subpool handle. By doing it this way, dangling cursors can only ever happen with Unchecked_Deallocation, or Unchecked_Deallocate_Subpool, and so this is really a classic Ada consideration (much better than just assuming the user gets it right by default). The pool must exist before the type is defined, which means that all ADTs using that compound type can only refer to objects allocated from the pool. The subpool to which a specific compound object is allocated lives at least as long as the object, unless Unchecked_Deallocate_Subpool is called (compiler warnings should be fairly easy for this also). Though it will be possible to assign an object allocated from one compound object to the local access pointer in another, it would be awkward to do, and would very hard to do "by mistake" I note that it is trivial to create unbounded storage-pools, so this method can support non-heap allocated ADTs also. Example: type ADT is private with Compound_With_Subpools => My_ADT_Pool; type Node_Access is access Node with Storage_Pool => My_ADT_Pool, Local => My_ADT; My_Tree: ADT; -- Subpool automatically allocated function Add_Node (Tree: in out ADT; Item: in Node) is New_Node: Node_Access := new (Tree'Compound_Subpool) Node'(Item); -- Static check passes: Tree'Compound_Subpool is the subpool of Node_Access's pool, which is the "local" compound object's pool. -- The subpool identifies a specific compound object of ADT (Tree), and Tree is writable. We could also have Tree as a -- Global in out aspect Begin ... -- Add the newly allocated node to Tree End Add_Node; **************************************************************** From: Tucker Taft Sent: Tuesday, April 9, 2019 8:50 AM I recommend we not worry about wording issues on this in the upcoming meeting. I would like to focus on the goal, which was to incur nearly zero implementation effort while establishing the framework for more elaborate ownership mechanisms later. It was at least my intent that the compiler should do *no* extra checking. The net effect of this AI should be to *suppress* certain dereferences from being considered "Global" side effects, but not require any checks beyond that. Any "extra" checks would be left to future proposals, or simply to implementations trying to detect what is described as "Erroneous Execution" in this AI. Because of the complexity of this issue, we believe we need to prototype more before selecting the best way to statically prevent ownership violations. This AI is merely about allowing the containers or other ADTs to be declared without having to reveal any use of "local" access objects. Randy and I didn't really finalize the wording before this was sent out, so I would suggest we not debate any such details. In the upcoming meeting, we would focus strictly on the "intent" of establishing a minimal framework which can be filled in later. **************************************************************** From: Tucker Taft Sent: Tuesday, April 9, 2019 9:20 AM Note that I did not comment on your specific suggestions because we have already had several quite elaborate proposals on this topic (e.g. AI12-0240-{1..5}). Our current challenge is to come up with a *minimal* framework that incurs nearly zero implementation burden, and leaves all of the cleverness to advanced implementations and/or future Ada revisions. **************************************************************** From: Richard Wai Sent: Tuesday, April 9, 2019 9:30 AM Fair enough, the background on this topic is somewhat overwhelming as a ARG newbie! :P **************************************************************** From: Randy Brukardt Sent: Tuesday, April 9, 2019 9:48 AM > Next, I have two small ideas, and one crazy one: > > 1. The legality rules, together with the static semantics, require > that Compound types have subcomponents of a "Local" > access type. However, since Local is a Boolean aspect, it is easy to > have one "local" access type be owned by different Compound types. I > don't see any check for that mentioned, so it should probably be > stated in the legality rules. Why would one want a check? This is a many-to-many relationship. It makes perfect sense for a single compound type to be associated with many "local" access types. Moreover, the reverse is also true (that you might have multiple compound types associated with a single "local" access type). For instance, consider a node manager that supports a tree container. That should probably be a different (protected) type than the container type, and it would need to hold a list of nodes that are not currently in use for any container. (An object of a "local" access type has to be reachable from some compound type at all times, so the storage manager also needs to be compound if it is going to exist between calls.) For the rest of it, I'll leave that to Tuck's response. I disagree with him about the wording, but only in the sense that I wanted to show that it isn't very long or complex. And in the sense that we're supposed to be finished with this Standard now, and starting something from scratch at this point isn't possible -- we need to have a full proposal last month. :-) **************************************************************** From: Richard Wai Sent: Tuesday, April 9, 2019 9:56 AM > Why would one want a check? This is a many-to-many relationship. It > makes perfect sense for a single compound type to be associated with > many "local" access types. I mostly agree here - my point was more about sanity checking for the implementation of an ADT such that some kinds of common errors are caught by the compiler. > (An object of a "local" access type has to be reachable from some > compound type at all times, so the storage manager also needs to be > compound if it is going to exist between calls.) I think my proposal achieves these need through the use of the existing storage pool subpool functionality, and by having the root "compound" type own a pool, and for the objects of that type to own their own subpool. **************************************************************** From: Randy Brukardt Sent: Tuesday, April 9, 2019 9:11 PM A thought on a point that you made repeatedly during the meeting. You said (if I am remembering it properly) that you'd like to mark this feature in some way that would allow us to change it incompatibly in the future. Tucker's vision, as I understand it, is to provide a *replacement* for it, where various new features would implicitly set the Compound and *mumble* (some term TBD to replace local) aspects. The way we've handled this sort of compatibility problem in the past is to provide Restrictions. For instance, we have No_Anonymous_Allocators since memory is usually not recoverable for such allocators (other than Coextensions - bletch - and access parameters, which is nearly useless since the object only lives as long as the call). (Still looking for No_Anonymous_Access_or_other_mistaken_features, though. ;-) In this case, we could have a restriction which prevented naming the Compound and *mumble* aspects directly, thus only allowing the checked aspects to be used. Projects that already are using the Compound and *mumble* aspects directly (possibly with third-party tools or special compiler support) could continue to do so. **************************************************************** From: Richard Wai Sent: Tuesday, April 9, 2019 9:40 PM > You said (if I am remembering it properly) that you'd like to mark > this feature in some way that would allow us to change it incompatibly in > the future. My issue had a lot to do with the understanding that this feature is there specifically for implementation the standard library container packages. So to me it is kind of an "internal" stop-gap until we figure out a better way to handle the ADT problem at-large. So since we are doing something like that, which many others also felt uncomfortable with, I was suggesting that we make it clear to the general user (programmer) that these features are really not intended for general use. The idea is to say - if you really want to use this, you accept that your code may become illegal in later revision of the standard. > The way we've handled this sort of compatibility problem in the past > is to provide Restrictions. For instance, we have > No_Anonymous_Allocators since memory is usually not recoverable for > such allocators (other than Coextensions - bletch - and access > parameters, which is nearly useless since > the object only lives as long as the call). (Still looking for > No_Anonymous_Access_or_other_mistaken_features, though. ;-) So for this, I could find this agreeable in theory, but only if this new restriction is specified to be on by default. This way the user has to explicitly enable that to use these features - signing the waiver, as it were. Obviously this doesn't seem to be how the restriction pragmas work.. I feel it is really different than something like No_Anonymous_Allocators - because that is a mistake that, say, a java programmer coming over to Ada could naturally end up doing everywhere and sinking the ship with memory leaks. > In this case, we could have a restriction which prevented naming the > Compound and *mumble* aspects directly, thus only allowing the checked > aspects to be used. Projects that already are using the Compound and > *mumble* aspects directly (possibly with third-party tools or special > compiler support) could continue to do so. So to summarize, I really felt putting a disclaimer into the RM made sense in this case just out of recognition of that fact that the feature is really there to support the standard containers library, and that general use should be avoided if future compatibility is a concern, since a more restrictive approach is expected. I just really want us to be able to make "local" (or whatever) pointers something that cannot be defined willy-nilly in the future, especially considering how much checking goes into access types in Ada. It seems like a step in the wrong direction. For any of the few users who end up having to refactor their ADTs, I think it is a price they should bear, rather than the language. **************************************************************** From: Randy Brukardt Sent: Tuesday, April 9, 2019 10:30 PM ... > So to summarize, I really felt putting a disclaimer into the RM made > sense in this case just out of recognition of that fact that the > feature is really there to support the standard containers library, > and that general use should be avoided if future compatibility is a > concern, since a more restrictive approach is expected. One of us is misunderstanding the purpose here. We do not need anything to support the standard containers library, as there is no requirement that it be written in Standard Ada, and indeed, pretty much everyone that I know of uses special switches to compile the runtime anyway. It would be really easy to build a mode in which all Global legality rules were ignored and use that to compile the runtime library. Janus/Ada already has a similar mode that ignores all Pure legality rules so we can compile the core runtime (which has plenty of state!) which all units depend upon. The problem is that users need the ability to be able to create their own containers and other ADTs. If the language will not allow users to create their own custom containers with essentially the same capabilities as the regular containers, then the language is broken and unfinished. Ergo, the entire point of defining a feature is so that users have a way to write their own containers. It completely defeats the purpose to tell people not to use the feature. Perhaps we could try to limit the feature to ADTs or something like that, although it's unclear how much restriction could be added to it without causing other issues. **************************************************************** From: Richard Wai Sent: Tuesday, April 9, 2019 10:43 PM > Ergo, the entire point of defining a feature is so that users have a > way to write their own containers. It completely defeats the purpose to tell > people not to use the feature. If that is the case, then I would find myself firmly in the camp that this should not be in the standard until it is fully baked.. Not that I have acquired much say in the matter yet :P **************************************************************** From: Tucker Taft Sent: Wednesday, April 10, 2019 3:42 PM The goal is to establish a standardized framework in which one or more "ownership" approaches might be provided which could be implementation-dependent or could appear in some future revision of Ada. I don't believe this framework is "half-baked." I believe it represents the lower limit of what is needed to make the Global aspect useful in the presence of pointers, without restricting exactly how those pointers might be used. It doesn't try to solve other problems, since we are pretty sure that the solutions to the more complex problems *are* half-baked at this stage. But if we don't standardize some basic framework like this, there will be no portability at all, and the Global aspect will be pretty much useless for any interesting abstract data type. There is a precedent in the history of Ada of having relatively simple frameworks, which are elaborated over time as revisions proceed. The whole storage-pool thing was an Ada 95 invention. The storage sub-pools appeared in Ada 2012. Basic containers were introduced in Ada 2005. Additional kinds of containers and generalized iterators over containers were introduced in Ada 2012. I see this Compound/Local framework as a simple starting point which captures the fundamental notion that "logical" objects are made up of multiple "physical" objects connected via access values, but leaves for future revisions more elaborate models that could enforce a particular way of doing things, perhaps provide automatic storage reclamation, prevent aliasing, etc. If you look at the history of this AI, you can see that we have plenty of ideas how to do all of these more sophisticated things, but we have come to an agreement that it is premature to pick one of these more complex approaches. What we are doing in this version is allowing the programmer to indicate that this ADT uses compound objects, and these access objects are being used to connect the physical objects together, but imposing no rules about how the pointers are actually used. This provides ultimate flexibility for one or more approaches to emerge, allowing us to later pick one (or more) which seems worth standardizing. But based on thinking about and working on these various approaches for the past five years, I believe this Compound/Local framework is compatible with any of these approaches, and imposes no limitations on our future creativity. **************************************************************** From: Randy Brukardt Sent: Friday, April 12, 2019 12:53 AM ... > There is a precedent in the history of Ada of having relatively simple > frameworks, which are elaborated over time as revisions proceed. The > whole storage-pool thing was an Ada 95 invention. The storage > sub-pools appeared in Ada 2012. Basic containers were introduced in > Ada 2005. > Additional kinds of containers and generalized iterators over > containers were introduced in Ada 2012. Perhaps a more relevant framework is "potentially blocking". This was defined in Ada 95 as a Bounded Error (where the bounds allow deadlocks and other pestilence, so it's almost the same as Erroneous Execution). Ada 2005 added pragma Detect_Blocking, which forces Program_Error to be raised. No Ada program should be compiled without it. (Well, in Janus/Ada we always raise Program_Error anyway, except for the I/O cases, which work, so it isn't necessary.) Ada 2020 is adding the Nonblocking contract, which is probably the way it should have been handled in the first place (but that would not have been politically possible for Ada 95, where all of the pressure was on "scope reduction" to make the changes smaller). The downside is obviously that we can't change the default until "Better Ada" (which very well may never happen). (Nonblocking should be the default, it's rare that code needs to block.) This framework seems to be likely to have the same progression, down to the reasons for starting small (pressure to get Ada 2020 out on time). A dynamic check (to cover most erroneous execution cases) for this framework doesn't seem hard to define (although I should note that Detect_Blocking had a nonsense definition until we were working on Nonblocking and realized that :-). The problem is that it would be expensive (in time), not the feasibility. (I'd probably implement something like it for Janus/Ada if and when I implemented this framework.) Probably a good project for a Technical Specification or for Corrigendum 1. Static checks are the holy grail, but I doubt that they could ever be applied to the existing containers. (The cursor definition requires dangling cursors to be possible -- runtime detection is allowed, but static detection would most likely prevent either the container definition from compiling, or many existing programs. Neither seems great. Still, it may be useful to have static checks for user-defined stuff, particularly for new code. **************************************************************** From: Richard Wai Sent: Tuesday, April 16, 2019 10:11 AM > ... > > There is a precedent in the history of Ada of having relatively > > simple frameworks, which are elaborated over time as revisions > > proceed. The whole storage-pool thing was an Ada 95 invention. The > > storage sub-pools appeared in Ada 2012. Basic containers were > > introduced in Ada 2005. > > Additional kinds of containers and generalized iterators over > > containers were introduced in Ada 2012. > > Perhaps a more relevant framework is "potentially blocking". This was > defined in Ada 95 as a Bounded Error (where the bounds allow deadlocks > and other pestilence, so its almost the same as Erroneous Execution). > > (Randy writes) > Ada 2005 added pragma Detect_Blocking, which forces Program_Error to > be raised. No Ada program should be compiled without it. (Well, in > Janus/Ada we always raise Program_Error anyway, except for the I/O > cases, which work, so it isn't necessary.) > This is interesting context and really makes a good case for the framework approach. > Static checks are the holy grail, but I doubt that they could ever be > applied to the existing containers. (The cursor definition requires dangling > cursors to be possible -- runtime detection is allowed, but static detection > would most likely prevent either the container definition from compiling, or > many existing programs. Neither seems great. Still, it may be useful to have > static checks for user-defined stuff, particularly for new code. In light of the earlier suggestion by Randy of a potential for a later pragma to enforce that the Compound aspect cannot be alone for a given type, I wonder if it might be an interesting idea (AI) in the future to add another "profile" like with Ravenscar, defining a set of configuration pragmas that turns on all available strict checking. **************************************************************** From: Randy Brukardt Sent: Monday, June 10, 2019 9:31 PM [This is an outgrowth of private mail between Tucker, Steve, and I over the last month. I'm putting this on the record so that we'll have access to it during the meeting. The AI I'm referencing will be posted in the next hour or so. - RLB] --- For an implicit dereference, Tucker has: For the purposes of this check, if a function returns an object of a type for which the Implicit_Dereference aspect is True (see 4.1.5), the Global aspect of the function shall reflect the effects of dereferencing the result of the function, if these are over and above reads or updates of aliased formal parameters passed to the function. The effects to be reflected include reading the designated object, and updating the designated object in the case of an Implicit_Dereference result with an access-to-variable access discriminant. This is associated with the function, which is fine by itself. But I don't understand how that applies to the resulting object, particularly if that object exists for a long time after the function call. And I don't understand how the object is supposed to be declared, given that it also will have to cover the global references of it's components (which necessarily includes the discriminant). Tucker made the claim that the dereference will always be in the same unit as the function call, and that is *almost* true (it's true for renames and parameter passing) -- but it's not true for allocators. For instance, if someone has a global container and a global access type, the following is legal and does not raise an exception (all of the accessibility checks pass): P := new Reference_Type'(Reference(Global_Container, ...)); and the discriminant of P can be used anywhere in the program, until the object is deallocated. (Yes, the tampering check remains during all of that time. Probably not smart, but that's not the topic of discussion :-). We had talked about this case, but it doesn't seem to be addressed. Or if it is supposed to be addressed via the type declaration, then I don't see how the function definition helps anything. --- I don't think that the proposed .all notation for Global works, and beyond that it is confusing. Let me hit a few specific points and outline an alternative. Steve had previously commented that .all is confusing for an object that not an access type. I'd go further and say it doesn't make any sense for an object that doesn't have an access type. The formal definition given by Tucker is: > object_name of the form prefix.ALL identifies the set of objects > designated by any part of the object denoted by the prefix; For an object of an access type, this is exactly equivalent (statically) to "access designated_type". One wonders what the extra value of prefix.ALL has here. For an object of a non-access type, however, we don't know the designated types. So the only thing a caller could possibly assume is that every object in the universe could be read and/or written (depending on the mode). This is a useless declaration! We could try to specify that the caller doesn't need to make these assumptions if the object is a compound object. But that information is not available to the caller (compound objects are an implementation issue). We could of course add additional rules on the usage of such an object. But that is *exactly* what the point of compound objects are. We don't want an additional set of similar rules that apply only to a handful of objects, and introduce additional erroneous execution possibilities. So I strongly believe that we don't want any special rules here for non-compound objects. The problem we're trying to solve here is a compound object passed as an "in" parameter that has indirect parts that (possibly) get modified. In all other cases, we want this declaration to mean nothing at all; the objects being referenced have to be given in the Global declaration anyway. So I don't think that prefix.all has the right effect, in addition to be confusing. --- Tucker had proposed a much more appealing syntax of "indirect in out ". He makes the following claims in the AI: > * The wording was difficult, as currently an object_name used as a > global_name is supposed to denote a global variable. To allow it > to denote a formal parameter only if the qualifier "indirect" was > present made the wording a bit of mess. Perhaps, but this seems (ahem) trumped-up. A global "variable" already can designate any constant. I don't see much problem allowing it to designate any visible object, with the notation that an object that isn't global has no effect on the global set. > Furthermore, the > qualifiers (such as "synchronized") were defined as simply > restricting the global set defined by the global_name, not > totally changing its interpretation. This seems more like a problem with the definition of "qualifiers" than it is with the idea here. One wants maximum flexibility for implementation-defined stuff, so if anything like this is defined restrictively, it's likely to get in the way of future enhancements as well as this idea. I'd just fix this by saying that it "modifies" the global set (perhaps they should be called modifiers??), and then we're good to go. > Finally, the rule of > 6.1.2(36/5) also became more complicated, since it said that a > given entity shall be named only once in a global aspect. But > with indirect, it would be reasonable to mention the same global > entity twice, once with "indirect in out" and once with simply > "in", for example. This does not seem reasonable to me at all. If we postulate my previous suggestion, then a parameter name in a Global (outside of "indirect") has no effect. So why would anyone want to mention it?? There's no need. I don't think that "indirect" is the right name; this is really declaring the *real* parameter mode (while still allowing constants to be passed). That is, the objects in these cases are really in out objects, but the parameter passing has to follow "in" parameter rules. I don't have a great idea for a name here: "real_mode" is my best idea and it isn't very appealing. > * There is also added complexity and potential redundancy, presuming we > still wanted to be able to use ".all" for access parameters. As currently defined, this doesn't provide any useful static information, so I think we could do without them. I suppose some future enhancement might get a better use out of this information (by additional restrictions on the access types), but I don't think we need to cover every possible future idea. ===== Thus I propose the following much simpler scheme for this problem (dropping all sign of ".all"). As noted above, "qualifiers" => "modifiers". Global_Name allows any statically denoted object. Unless otherwise specified, a local object (such as a parameter name) has no effect on the global set. Modifier "real_mode" is defined; its only allowed to be specified in Global for a callable entity. The Global_Name for "real_mode" has to be a parameter of the callable entity. The mode for real_mode has to match that of the original parameter, or be "in out". If Real_mode is specified for a parameter, the mode of the real_mode reference is considered to be the mode of the parameter for the evaluation of all Global rules. In particular, the Notwithstanding Rule of the Legality Rules of 6.1.3 would use the "real_mode" rather than the actual parameter mode to determine whether an appropriate object is available. ****************************************************************