Version 1.3 of ai12s/ai12-0240-4.txt

[Editor's note: This private conversation is being posted here in case anyone is
interested in fleshing out this proposal. It was abandoned due to lack of time
rather than any technical problems.]

From: Tucker Taft
Sent: Thursday, December 20, 2018  2:29 PM

Here is a pretty complete re-write, based on some recent brainstorming between
Tuck and Randy.  Probably the biggest change was due to Randy's recognition that
anything short of implicit deep copy on assignment was going to cause real
headaches for any attempt to write an Adjust procedure for composite types with
ownership-based access types as components.  Saying that all such composite
types use deep copy on assignment also allows us to eliminate essentially all of
the complex rules associated with such types, treating them as we would any Ada
type with a controlled subcomponent.

The other big change, also suggested by Randy, was to recognize that we have
four distinct kinds of subtypes of these types, Owner, Borrower, Observer, and
Unmanaged.  I have taken this as a starting point, and produced what I believe
is a cleaner proposal.  I'd like you two to spend some time reviewing this
before we consider sending it out to the whole ARG.  I don't really expect any
feedback until after the holidays, especially from Randy, who I believe has
burned through his 2018 budget completely.  If you guys like it, I'll do the
wording.  If not, well we can always do another complete rewrite! ;-)

[This is version /01 of the AI - Editor.]

****************************************************************

From: Steve Baird
Sent: Monday, January 7, 2019  7:23 PM

I like this better than previous versions. I like the subtypes stuff, as opposed
to depending on anonymous access types.

I also think the presentation in terms of Globals and treating designated
objects as components makes the motivation clearer than some earlier versions.

And the semi-managed (I'll give you the protector object, but you'll have to
take my word for it) stuff needed for cursors seems like a nice solution.

I couldn't resist mentioning (probably prematurely) some details below.

> Handling pointer dereferences has always been a challenge for formal
> analysis, with approaches such as "separation logic" generally
> requiring more formalism than would be appropriate even for a skilled programmer.
> The concept of "pointer ownership" or "object ownership" represents a
> simpler alternative approach, and reflects a typical way in which most
> pointers are actually used in the implementation of many ADTs. When
> pointers have "ownership," this means that the heap object they
> designate has exactly one "owning" pointer, and when the owning
> pointer is set to null, the heap object can be safely reclaimed.
> Although there might be other pointers designating the heap object
> under certain circumstances, these other pointers are recognized as being "secondary"
> references, which can be managed in a way to ensure that no such
> secondary references are usable after the "owning" pointer is set to
> null.
>

This is just !proposal text, so it is ok if it is less precise. Still, it seems
confusing to me to (twice) talk about an owning object being "set to null". This
ignores the case where the object is assigned a different non-null value and
also the finalization case (although that case is handled later when we say that
finalization effectively involves assigning the value null to the finalized
object.

> We propose to add "ownership-based" access types to the language, with
> aspect Ownership => True, and with four distinct kinds of subtypes of
> such access types, as determined by an Access_Kind aspect, specifiable
> on an object or subtype declaration:
>   * Access_Kind => Owner -- owner subtypes
>   * Access_Kind => Borrower -- borrower subtypes
>   * Access_Kind => Observer -- observer subtypes
>   * Access_Kind => Unmanaged -- unmanaged subtypes
>
> Operations that reference or update a heap object designated by an
> ownership-based access object may treat the designated object as
> though it were a subcomponent of the composite object containing the
> object's owning pointer.  An object is "directly owned" by its owning
> pointer, and simply "owned" by both its direct owner as well as by the
> owner(s) of the (heap) object of which the owning pointer is a
> subcomponent. What this means as far as the Global aspect is that
> there is no need to use "access T" or "<package_name>" to recognize
> dereferences of ownership-based access objects.  Instead, the Global
> aspect should recognize that these dereferences are equivalent to
> referencing subcomponents of the owner(s), and including an object
> containing an owner in the global variable set for the IN, IN OUT, or
> OUT mode implicitly includes all the objects owned, directly or
> indirectly, by this owner.
>
> Any composite type with an owning object as a subcomponent becomes a
> by-reference type, much like any composite type with a tagged,
> inherently limited, or volatile subcomponent is a by-reference type.
> This simplifies various rules by eliminating implicit copying of
> objects containing owning pointers.
>
> Explicit copying of objects containing owning pointers (e.g. on
> assignment or function return) automatically performs a "deep" copy,
> reflecting the model that an object designated by an owning pointer is
> treated like a component.  Similarly streaming an owning pointer is
> defined to stream the designated object.
>

Presumably deep copying is illegal if the designated type is limited (although
perhaps it could be defined to be ok if streaming attributes are available).
Similarly, streaming of an owning access value is presumably illegal if the
designated type doesn't have streaming attributes available.

> Because owning pointers themselves are of an access type, they are
> implicitly copied as part of by-copy parameter passing.  They are
> also, of course, copied as part of an assignment or function return.
> Unlike the case of a composite object with one of these as a
> component, we don't have the option of making them into a by-reference
> type, and thereby eliminating cases of implicit copying.

Note that in the case of a function return, a by-reference result type does not
eliminate any copying associated with the assignment to the function result
object.

> Furthermore, even in an
> assignment statement, it is not always clear that you would want to do
> a deep copy when such an access object is assigned to another.  It
> depends heavily on the context.  For example, if you wanted to create
> a pointer that was to walk over an existing tree structure, you
> certainly wouldn't want the creation of that temporary pointer to
> result in the creation of a copy of the tree.  This leads us to define
> the four kinds of ownership-based access subtypes mentioned above, and
> also to define some attributes to be used for specifying explicitly
> how the copying of an access-object is to be performed.
>
> The first case to consider is a "simple" assignment from an owner
> access object to another owner access object.  There are two
> interesting
> alternatives:
>    1) Assign a deep copy of the RHS into the LHS; or
>    2) Move the ownership from the RHS to the LHS, and null-out the RHS.
>
> In both cases, if the LHS already designated an object, we would want
> to finalize and reclaim the storage for that object before overwriting
> the LHS.  (Alternatively, we could require that the LHS be null before
> the assignment, forcing the user to explicitly set it to null first.)
>
> To distinguish these two cases we propose the use of an explicit
> attribute, either 'Copy or 'Move:
>    1) LHS := RHS'Copy;  --  Deep copy
>    2) LHS := RHS'Move;  --  Move; set RHS to null We don't think there
> is a safe, obvious default, so we propose that the attribute is
> required.  Simple assignment from one owner object to another would
> not be permitted without specifying such an attribute.

Generic body contract issues? Do we always need to know statically whether the
LHS/RHS-type of an assignment is an owning type? If so, then class-wide
assignment also needs to be considered.

RHS'Copy indeed seems preferable to T'Copy (RHS), even though the former syntax
may require qualification in the case where RHS is not a name.

RHS'Move is presumably illegal if RHS is a constant that will outlive the
assignment statement (but OK if, for example, RHS is a function call).

> Either 'Copy or 'Move must also be used when initializing an owner
> component of an aggregate as a copy of another owner object, or when
> returning an owner object from a function.  An allocator could be
> thought of as a short-lived owner object, from which 'Move semantics
> is implicit. Any owner object that is non-null when it is finalized
> will be effectively set to null, causing finalization and reclamation
> of its designated object.
>
> The next case to consider is when you want to create a temporary
> pointer to "walk" a data structure, either with read/write or read-only access.
> Here we introduce the notion of a "borrower" and an "observer."  A
> "borrower" is an access object that provides read/write access to the
> designated object, and recursively has read/write access to the whole
> object "tree" through owner subcomponents of the designated object.
> An "observer" is an access object that provides read-only access to
> the designated object, and recursively has read-only access through
> owner subcomponents of the designated object to the object tree.
>
> To create such a temporary pointer via an assignment, we require that
> the LHS be declared as part of the assignment, that it be of the
> appropriate Access_Kind (Borrower or Observer), and that an attribute
> ('Borrow or 'Observe) is used on the RHS to indicate what sort of
> operation is being performed.  Hence:
>
>    1) LHS : Acc_T with Access_Kind => Borrower := RHS'Borrow;
>             --  create a borrower; RHS must be owner or borrower
>    2) LHS : Acc_T with Access_Kind => Observer := RHS'Observe;
>             --  create an observer; RHS may be owner, borrower, or
> observer
>
> We could relax the requirement for specifying the 'Borrow or 'Observe
> attribute in cases where only one would be permitted based on the
> subtype of the LHS, but we believe it should be possible to be
> explicit if desired.
>
> To provide a modicum of safety, during the scope of a borrower, the
> RHS from which it originated is frozen, and cannot be dereferenced or
> changed. Similarly, during the scope of an observer, the RHS and any
> borrowers derived from it also effectively become observers, providing
> only read access to the object tree.
>

Do we want more detail at this point, or just wait for wording? When we say, for
example, that an object cannot be modified, that includes a prohibition on
calling a subprogram that might modify it (right?). So we are depending on
Globals here.

> An observer object may be assigned a new value after its declaration,
> but only if the RHS of the assignment is another observer that is
> declared in the same or an outer scope, or is an owner component that
> is in the object "tree" rooted at the object designated by such an
> observer. In other words, observers can walk "down" an object tree, or
> jump over to another object tree that is being observed at least as
> long as the tree the observer is associated with.
>
> Similarly, a borrower object may be assigned a new value if the RHS is
> an owner component within the object tree rooted at the object
> currently designated by the borrower.  This means a borrower can also
> walk down its object tree.  Unlike an observer, it is not permitted to
> "jump" to some other tree.
>

Am I right in thinking that "jumping" is ok in one case but not in the other
because of CREW (concurrent readers, exclusive writers)? Fleshing out the
rationale at some point (but perhaps not yet) would be useful because I was
unsure about this.

> Formal parameters of an ownership-based access type are treated
> specially -- their Access_Kind has a default.  An IN-OUT or OUT
> parameter of an ownership-based access type is treated as Access_Kind
> Owner.  An IN parameter is by default treated as Access_Kind Borrower,
> but this can be overridden by using a formal parameter subtype with
> Access_Kind Observer.  As implied by the Access_Kind of an [IN] OUT
> parameter being Owner, passing an owner object to an [IN] OUT
> parameter automatically uses "'Move" semantics, both ways, meaning
> that the actual is set to null during the execution of the subprogram.
> This allows the formal parameter to be assigned a new value, including
> null, with the appropriate semantics.  For an IN parameter, "'Borrow" or "'Observe"
> semantics, are used as determined by the Access_Kind of the formal. An
> [IN] OUT formal parameter needs to be set to null implicitly when a
> subprogram ends abnormally (due to propagating an exception or being
> aborted), to avoid storage leakage.
>
> An access object of an ownership-based access type can be passed to a
> subprogram with an access parameter (i.e. a formal parameter of an
> anonymous access type) only if the subprogram as a whole has its
> Ownership aspect specified as True.  In that case, an
> access-to-variable parameter automatically has Access_Kind Borrower,
> and an access-to-constant parameter automatically has Access_Kind Observer.
> Similarly, the result type may be of an anonymous access type (i.e.,
> an "access result"), and the Access_Kind is Borrower or Observer
> according to whether it is access-to-variable or access-to-constant.
>
> The 'Borrow and 'Observe attributes can be used on function return,
> but only if the prefix of the attribute reference is derived from a
> formal parameter that is of the corresponding Access_Kind, and the
> result subtype has the corresponding Access_Kind.

I know what you mean, but this use of "derived" is confusing.

...

****************************************************************

From: Randy Brukardt
Sent: Monday, January 7, 2019  8:28 PM

[After reading the whole thing.] I've put a few thoughts into the body below. In
general, this looks promising -- most of the things I hated about the earlier
proposals are gone, and the stuff I don't like about this I can definitely live
with. So I suggest pressing forward -- as you said before, the devil is in the
details, and there are a *lot* of details.

-----

> !standard 3.10.3(0)                             18-12-20 AI12-0240-4/01
> !class Amendment 18-06-14
> !status work item 18-06-14
> !status received 18-06-14
> !priority Low
> !difficulty Hard
> !subject Pointer ownership for Abstract Data Types !summary
>
> We introduce the notion of "pointer ownership" to allow us to define
> the "Global" aspects of the visible operations of an abstract data
> type, without being concerned with appropriately-managed internal uses
> of access types.  We call these properly managed internal access
> types, "ownership-based" access types for now. A more concise term
> might be adopted at some point.

...if we could agree on something that isn't misleading. Not much luck so far.
:-)

> !problem
>
> Assuming that we have static 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 "access T" or
> "<package_name>"
> form of specification, which 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.

Sounds good.

> !proposal
>
> Handling pointer dereferences has always been a challenge for formal
> analysis, with approaches such as "separation logic"
> generally requiring more formalism than would be appropriate even for
> a skilled programmer.
> The concept of "pointer ownership" or "object ownership"
> represents a simpler alternative approach, and reflects a typical way
> in which most pointers are actually used in the implementation of many
> ADTs. When pointers have "ownership,"
> this means that the heap object they designate has exactly one
> "owning" pointer, and when the owning pointer is set to null, the heap
> object can be safely reclaimed.  Although there might be other
> pointers designating the heap object under certain circumstances,
> these other pointers are recognized as being "secondary"
> references, which can be managed in a way to ensure that no such
> secondary references are usable after the "owning"
> pointer is set to null.
>
> We propose to add "ownership-based" access types to the language, with
> aspect Ownership => True, and with four distinct kinds of subtypes of
> such access types, as determined by an Access_Kind aspect, specifiable
> on an object or subtype declaration:
>  * Access_Kind => Owner -- owner subtypes
>  * Access_Kind => Borrower -- borrower subtypes
>  * Access_Kind => Observer -- observer subtypes
>  * Access_Kind => Unmanaged -- unmanaged subtypes

There probably isn't any real need for borrowers or observers to implement the
containers; they probably will help in some circumstances, but most of the time
you just need owners and unmanaged. I only mention this because if there is
still too much complexity for some, we could split that part out.

> Operations that reference or update a heap object designated by an
> ownership-based access object may treat the designated object as
> though it were a subcomponent of the composite object containing the
> object's owning pointer.  An object is "directly owned" by its owning
> pointer, and simply "owned" by both its direct owner as well as by the
> owner(s) of the
> (heap) object of which the owning pointer is a subcomponent.
> What this means as far as the Global aspect is that there is no need
> to use "access T" or "<package_name>" to recognize dereferences of
> ownership-based access objects.  Instead, the Global aspect should
> recognize that these dereferences are equivalent to referencing
> subcomponents of the owner(s), and including an object containing an
> owner in the global variable set for the IN, IN OUT, or OUT mode
> implicitly includes all the objects owned, directly or indirectly, by
> this owner.

Somehow I lost you in this paragraph even though I know what the model is.

> Any composite type with an owning object as a subcomponent becomes a
> by-reference type, much like any composite type with a tagged,
> inherently limited, or volatile subcomponent is a by-reference type.
> This simplifies various rules by eliminating implicit copying of
> objects containing owning pointers.

"By-reference" being a dynamic concept helps here, as we don't have to worry
about privacy. I probably should have thought of that myself.

> Explicit copying of objects containing owning pointers (e.g.
> on assignment or function return) automatically performs a "deep"
> copy, reflecting the model that an object designated by an owning
> pointer is treated like a component.  Similarly streaming an owning
> pointer is defined to stream the designated object.

Cool. Never thought about streaming.

> Because owning pointers themselves are of an access type, they are
> implicitly copied as part of by-copy parameter passing.  They are
> also, of course, copied as part of an assignment or function return.
> Unlike the case of a composite object with one of these as a
> component, we don't have the option of making them into a by-reference
> type, and thereby eliminating cases of implicit copying.  Furthermore,
> even in an assignment statement, it is not always clear that you would
> want to do a deep copy when such an access object is assigned to
> another.  It depends heavily on the context.
> For example, if you wanted to create a pointer that was to walk over
> an existing tree structure, you certainly wouldn't want the creation
> of that temporary pointer to result in the creation of a copy of the
> tree.  This leads us to define the four kinds of ownership-based
> access subtypes mentioned above, and also to define some attributes to
> be used for specifying explicitly how the copying of an access-object
> is to be performed.
>
> The first case to consider is a "simple" assignment from an owner
> access object to another owner access object.  There are two
> interesting
> alternatives:
>   1) Assign a deep copy of the RHS into the LHS; or
>   2) Move the ownership from the RHS to the LHS, and null-out the RHS.
>
> In both cases, if the LHS already designated an object, we would want
> to finalize and reclaim the storage for that object before overwriting
> the LHS.  (Alternatively, we could require that the LHS be null before
> the assignment, forcing the user to explicitly set it to null first.)
>
> To distinguish these two cases we propose the use of an explicit
> attribute, either 'Copy or 'Move:
>   1) LHS := RHS'Copy;  --  Deep copy
>   2) LHS := RHS'Move;  --  Move; set RHS to null We don't think there
> is a safe, obvious default, so we propose that the attribute is
> required.  Simple assignment from one owner object to another would
> not be permitted without specifying such an attribute.
> Either 'Copy or 'Move must also be used when initializing an owner
> component of an aggregate as a copy of another owner object, or when
> returning an owner object from a function.
> An allocator could be thought of as a short-lived owner object, from
> which 'Move semantics is implicit. Any owner object that is non-null
> when it is finalized will be effectively set to null, causing
> finalization and reclamation of its designated object.

How are these attributes defined? As attributes of objects of "ownership-based"
access types? Or something else? I wonder because typically elementary type
assignment is of values, and we have to deal with assignment of null and
allocators as well. Presumably, those (null, allocators) wouldn't require some
attribute reference, although that suggests that the Legality Rule banning
direct assignments will be interesting to word.

> The next case to consider is when you want to create a temporary
> pointer to "walk" a data structure, either with read/write or
> read-only access.
> Here we introduce the notion of a "borrower" and an "observer."  A
> "borrower" is an access object that provides read/write access to the
> designated object, and recursively has read/write access to the whole
> object "tree" through owner subcomponents of the designated object.
> An "observer"
> is an access object that provides read-only access to the designated
> object, and recursively has read-only access through owner
> subcomponents of the designated object to the object tree.
>
> To create such a temporary pointer via an assignment, we require that
> the LHS be declared as part of the assignment, that it be of the
> appropriate Access_Kind (Borrower or Observer), and that an attribute
> ('Borrow or 'Observe) is used on the RHS to indicate what sort of
> operation is being performed.  Hence:
>
>   1) LHS : Acc_T with Access_Kind => Borrower := RHS'Borrow;
>            --  create a borrower; RHS must be owner or borrower
>   2) LHS : Acc_T with Access_Kind => Observer := RHS'Observe;
>            --  create an observer; RHS may be owner, borrower, or
> observer
>
> We could relax the requirement for specifying the 'Borrow or 'Observe
> attribute in cases where only one would be permitted based on the
> subtype of the LHS, but we believe it should be possible to be
> explicit if desired.

This does seem to be a bit of overkill, since the kind is implicit/explicit in
the declaration of the LHS. There aren't any objects of Acc_T without an
Access_Kind, right? I suppose it is harmless to allow it, but requiring it seems
to violate DRY (you are saying the same thing twice).

> To provide a modicum of safety, during the scope of a borrower, the
> RHS from which it originated is frozen, and cannot be dereferenced or
> changed. Similarly, during the scope of an observer, the RHS and any
> borrowers derived from it also effectively become observers, providing
> only read access to the object tree.

I've long wondered how this works in the case of a Borrower or Observer
parameter. And if the answer is that you can't have such things, that seems to
force everything to be built monolitically (since you certainly can't pass an
Owner as a parameter, that would be taking the data structure apart or copying
it, neither which seem like a good idea) or using only Unmanaged values.

> An observer object may be assigned a new value after its declaration,
> but only if the RHS of the assignment is another observer that is
> declared in the same or an outer scope, or is an owner component that
> is in the object "tree" rooted at the object designated by such an
> observer. In other words, observers can walk "down" an object tree, or
> jump over to another object tree that is being observed at least as
> long as the tree the observer is associated with.
>
> Similarly, a borrower object may be assigned a new value if the RHS is
> an owner component within the object tree rooted at the object
> currently designated by the borrower.  This means a borrower can also
> walk down its object tree.  Unlike an observer, it is not permitted to
> "jump" to some other tree.
>
> Formal parameters of an ownership-based access type are treated
> specially -- their Access_Kind has a default.  An IN-OUT or OUT
> parameter of an ownership-based access type is treated as Access_Kind
> Owner.  An IN parameter is by default treated as Access_Kind Borrower,
> but this can be overridden by using a formal parameter subtype with
> Access_Kind Observer.  As implied by the Access_Kind of an [IN] OUT
> parameter being Owner, passing an owner object to an [IN] OUT
> parameter automatically uses "'Move" semantics, both ways, meaning
> that the actual is set to null during the execution of the subprogram.
> This allows the formal parameter to be assigned a new value, including
> null, with the appropriate semantics.  For an IN parameter, "'Borrow"
> or "'Observe"
> semantics, are used as determined by the Access_Kind of the formal. An
> [IN] OUT formal parameter needs to be set to null implicitly when a
> subprogram ends abnormally (due to propagating an exception or being
> aborted), to avoid storage leakage.

OK, I see that you are in fact destroying the data structure for an Owner
parameter; I guess I can see how that would make sense for an "in out" or "out"
parameter.

But I don't understand how one can enforce the restrictions on the original RHS
inside of a subprogram. If it is aliased somehow, how would the compiler know
what to make illegal?

If you had:
    procedure Do_Something (Obj : in out Some_Container; Loc : Acc_T)
        -- Use Loc to find some data and then replace Obj.Data with that.

and a call:
  LHS : Acc_T with Access_Kind => Borrower := My_Container.Data;

  Do_Something (My_Container, LHS);

How do we determine that this call (or something) should be illegal as it
attempts to modify a "locked" object?

> An access object of an ownership-based access type can be passed to a
> subprogram with an access parameter (i.e. a formal parameter of an
> anonymous access type) only if the subprogram as a whole has its
> Ownership aspect specified as True.

??? Since when do subprograms have Ownership aspects? Something is confused
here.

> In that case, an access-to-variable parameter automatically has
> Access_Kind Borrower, and an access-to-constant parameter
> automatically has Access_Kind Observer.
> Similarly, the result type may be of an anonymous access type (i.e.,
> an "access result"), and the Access_Kind is Borrower or Observer
> according to whether it is access-to-variable or access-to-constant.
>
> The 'Borrow and 'Observe attributes can be used on function return,
> but only if the prefix of the attribute reference is derived from a
> formal parameter that is of the corresponding Access_Kind, and the
> result subtype has the corresponding Access_Kind.  Such a function is
> called a "traversal function," in that it is used to traverse down an
> object tree, returning an observer or borrower reference to a point
> somewhere within the tree.  Such traversal functions could be used to
> search within a tree, or just do some sort of systematic walk down the
> tree.
>
> Passing a composite object that has an owner access object as a
> subcomponent implicitly observes or borrows that owner object,
> depending on whether it is passed as an IN parameter, or as an [IN]
> OUT parameter, respectively. This is only of concern in places where
> the caller has visibility on the components.  Presuming the composite
> type is a private type, no special rules would apply where this
> partial view is all that is visible, because the objects designated by
> the owner objects are effectively treated like any other non-visible
> subcomponent of the composite object.

Maybe this is the answer, but doesn't that cause issues if one is just using
unmanaged accesses (as in container cursors)? This seesm to imply that a
subprogram can't modify owned components -- which is a problem for an ADT,
'cause what other way is there to do that?

> A component of a composite type is not permitted to be of a Borrower
> or Observer subtype.  Borrowers or observers can only be stand-alone
> objects or formal parameters.  On the other hand, components can be of
> Access_Kind Owner or Unmanaged.  Owner objects are described above.
> Unmanaged objects are intended for use as back pointers, cursors, or
> other sorts of secondary references.
>
> To lessen the possibility of misuse of unmanaged access objects, we do
> not allow them to be directly dereferenced.
> Instead, they must be used to initialize an observer or borrower,
> using an 'Observe or 'Borrow attribute, but where the attribute has an
> operand that identifies the unmanaged object whose value is to be
> used, but is protected by the object that is being observed or
> borrowed. By "protecting" we mean that the protector is an owner, or
> derived from an owner access object that owns, directly or indirectly,
> the object designated by the unmanaged access object.  This ensures
> that the unmanaged access object is not pointing off into thin air.
> For example, here is a possible implementation of a Hashed_Map using
> ownership-based access types, and using two unmanaged access objects
> to implement a cursor:
>
>    function Element (Container : Map;
>                      Position : Cursor)
>       return Element_Type
>       with Global => null;
>    ...
> private
>    type Node;
>    type Node_Ptr is access Node with Ownership;
>    subtype Owning_Node_Ptr is Node_Ptr with Access_Kind => Owner;
>
>    type Node is record
>       Element : Element_Type;
>       Next : Owning_Node_Ptr;
>    end record;
>
>    type Table is array(Natural range <>) of Owning_Node_Ptr;
>    type Table_Ptr is access Table with Ownership;
>
>    type Cursor is record
>       Backbone : Table_Ptr with Access_Kind => Unmanaged;
>       Node : Node_Ptr with Access_Kind => Unmanaged;
>    end record;
>
>    type Map is record
>       Backbone : Table_Ptr with Access_Kind => Owner;
>       Count : Natural := 0;
>    end record;
>    ...
>    function Element (Container : Map;
>                      Position : Cursor)
>         return Element_Type is
>       pragma Assert (Position.Backbone = Container.Backbone);
>          -- Make sure the cursor matches the map

This is part of the precondition for the language-defined containers. It might
be better to show it that way (of course, that's encapsulated in another routine
whose name I don't recall at the moment).

>       Node : constant Node_Ptr with Access_Kind => Observer :=
>          Container.Backbone'Observe (Position.Node);
>            --  We are observing Container.Backbone, but starting
>            --  at the object designated by Position.Node.

Again, I'm wondering what the definition of this attribute is going to be.
Otherwise, this seems fine to me (might be nasty to figure out which of Borrower
or Observer that is needed, but we'll all figure it out eventually). Annoying to
have to declare an extra pointer for every use, but I suppose that's the cost of
extra safety.

>    begin
>       return Node.Element;
>    end Element;
>
> Unmanaged access objects can be created by copying an object of any
> other Access_Kind, by applying the 'Unmanaged attribute.  E.g.:
>
>     Position := Cursor'(Backbone => Map.Backbone'Unmanaged,
>                         Node => Some_Node'Unmanaged);
>
> We could relax the requirement to use 'Unmanaged on creation of such a
> value if the target is of Access_Kind Unmanaged, but it seems helpful
> to allow an explicit use of the attribute.

As previously mentioned, this can violate DRY, maybe not as much here. There's
obviously an advantage here as simple tools can enforce limitations on creation
of Unmanaged values.

> It is erroneous to use an unmanaged access object as the operand of
> <prefix>'Borrow(...) or <prefix>'Observe(...) if it does not designate
> an object within the object tree designated by the prefix.
>
> For operations that need to dereference an unmanaged access object,
> but do not have a formal parameter that can be used as the "protector"
> of the unmanaged object, we provide 'Unchecked_Borrow and
> 'Unchecked_Observe which can be applied to an unmanaged object to
> produce a borrower or an observer.
> It is erroneous to use such an attribute if the designated object no
> longer exists, or if some dynamically enclosing caller of the
> operation does not have an access object with corresponding access to
> the object, directly or indirectly.
> Also, such an operation must have a Global aspect that indicates
> "access T" or "<package_name>" because there is no formal parameter
> that can
> "carry" the side effects of the operation.   For example:
>
>    function Element (Position : Cursor)
>         return Element_Type
>       with Global => in Hashed_Map;
>    ...
>    function Element (Position : Cursor)
>         return Element_Type is
>       Node : Node_Ptr with Access_Kind => Observer :=
>         Position.Node'Unchecked_Observe;
>    begin
>       return Node.Element;
>    end Element;

If the cursor directly carries a general access-to-container value, you could
implement this as (showing the dereferences for clarity:

    function Element (Position : Cursor)
         return Element_Type is
       Node : Node_Ptr with Access_Kind => Observer :=
         Position.My_Container.all(Position.Node)'Observe;
    begin
       return Node.Element;
    end Element;

I believe (without checking) that the Ada.Containers never require using the
associated container for any purpose except implementing these operations and
making the ownership check (which doesn't require a dereference - it's a ptr
compare). With this formulation, the needed Global falls out automatically. And
the access-to-container does NOT need to have ownership.

Which is a long-winded way of saying that Unchecked_Observe/Unchecked_Borrow
doesn't seem to be necessary for implementing the Ada.Containers. It might still
be useful (and surely would add flexibility and might be needed for SPARK), but
I don't see how to explain/require the needed Global setting for these.

---

Two things I didn't see here:
  (1) Rules to prevent conversions to/from other access types. Is derivation
      from such a type allowed? (I banned it 'cause I didn't want to think about
      it, which probably isn't a good reason. :-)

  (2) Rules for generics? I presume that we're requiring Ownership to match for
      formal access types.

  (3) Accessibility rules, or at least some rules to allow the use of these
      (somehow) with access discriminants, as we need to be able to implement
      Reference/Constant_Reference (more generally, user-defined dereferences).

Well, that's three. :-)

> !wording
>
> TBD
>
> !discussion
>
> See !problem and !proposal for much of the rationale for what we
> propose. Here we will try to provide a rationale for what we chose
> *not* to do.
>
> We have required the explicit use of 'Move or 'Copy on owner-object
> assignments.  We originally had proposed that "move" semantics were
> the default, but we have come to feel that that is too error prone and
> potentially confusing.
> Also, "move" semantics have a side-effect of nulling out the RHS, but
> that is quite different from how normal assignments work, including
> that it requires the RHS to be a variable.

Yup.

> We have made deep copy implicit in assignments of composite objects
> containing owner objects.  We originally had "move"
> semantics here as well, but it was pointed out that this had real
> problems in the context of controlled types, because if the user
> wanted to implement deep copy on their own using Adjust, it would sort
> of be "too late" since either the RHS has already had nulls written
> all over it, or if we suppress that, we pass an object to Adjust that
> we want to do deep copy "in place" but any attempt to assign a new
> value to an owner component would immediately reclaim the old value.
> All in all a bit of a mess.  By instead making deep copy implicit for
> composite objects containing owner objects (even if they are
> controlled), Adjust can be used merely to do any other operations that
> are needed beyond this deep copying.

Also yup.

> More generally, we had some complex rules relating to composite
> objects with Ownership True.  We have eliminated all of those.  The
> implicit deep copy effectively allows a tree of objects to be treated
> as a "flat"
> object, without much of any further special concerns.
>
> We considered requiring that these ownership-based access types be
> declared in a private part, but that doesn't really accomplish much
> given that you can define a private child with full visibility on the
> private part of its parent.
>
> We considered requiring that an ownership-based access type identify
> all of the externally visible composite types where it was allowed to
> be used as a component.  But that smacks of the "come from" approach
> to control flow, and creates annoying maintenance headaches. The main
> use for this list of composite-type "users" was to have reasonable
> semantics for the use of unmanaged access objects.  But now that we
> disallow direct dereferencing of unmanaged objects, and provide
> various attributes to convert them to observers or borrowers, we
> believe there is no need to identify the composite types where owner
> components are permitted.

I tend to agree. It does make things rather wordy, but perhaps that is the sort
of incentive to avoid "unmanaged" objects that is necessary.

> We considered requiring composite types with owner components be
> by-reference types due to being tagged or immutably limited, but
> instead we concluded that it is simpler to just say that having an
> owner access object as a subcomponent should by itself cause a type to
> be by-reference.  We already do this with volatile subcomponents, so
> it seems simple enough to have owner subcomponents have the same
> effect.

I hadn't remembered that or I would have probably done the same.

****************************************************************

From: Randy Brukardt
Sent: Monday, January 7, 2019  8:50 PM

...
> > Explicit copying of objects containing owning pointers (e.g. on
> > assignment or function return) automatically performs a "deep" copy,
> > reflecting the model that an object designated by an owning pointer
> > is treated like a component.  Similarly streaming an owning pointer
> > is defined to stream the designated object.
>
> Presumably deep copying is illegal if the designated type is limited
> (although perhaps it could be defined to be ok if streaming attributes
> are available).

There is no alternative if any of the owner types (that is, the types containing
the owned pointers) allow copying. (We've already determined that all of the
alternatives lead directly to madness.) In keeping with the model that these
work roughly like components, if the designated object is limited, the owner
type has to be limited as well. Then we could ban 'Copy for access-to-limited
types (it's not enough alone).

> Similarly, streaming of an owning access value is presumably illegal
> if the designated type doesn't have streaming attributes available.

Yup.

> > Because owning pointers themselves are of an access type, they are
> > implicitly copied as part of by-copy parameter passing.  They are
> > also, of course, copied as part of an assignment or function return.
> > Unlike the case of a composite object with one of these as a
> > component, we don't have the option of making them into a
> > by-reference type, and thereby eliminating cases of implicit copying.
>
> Note that in the case of a function return, a by-reference result type
> does not eliminate any copying associated with the assignment to the
> function result object.

Humm. Build-in-place is formally copying, even though no copying is involved. Is
there any cases where a by-reference type is not built-in-place? (Not doing that
would seem to be a problem for objects with volatile components; do we really
want volatile temporary objects??)

...
> > To distinguish these two cases we propose the use of an explicit
> > attribute, either 'Copy or 'Move:
> >    1) LHS := RHS'Copy;  --  Deep copy
> >    2) LHS := RHS'Move;  --  Move; set RHS to null We don't think
> > there is a safe, obvious default, so we propose that the attribute
> > is required.  Simple assignment from one owner object to another
> > would not be permitted without specifying such an attribute.
>
> Generic body contract issues? Do we always need to know statically
> whether the LHS/RHS-type of an assignment is an owning type?

I think so; I believe the requirement is that Ownership is an exact match for
any generic formal access type. That is, generics that work on ordinary access
types don't work with Ownership-based access types and vice versa. The rules are
too different for these cases.

I worried a bit about formal derived types, which is why I banned derivation
associated with ownership-based access types (didn't want to go there). Tucker
may (or may not) be planning to do the same.

> If so, then class-wide assignment also needs to be considered.

How so? Deep-copy semantics is purely dynamic. (I know how to implement that in
Janus/Ada, so I can't see how there is a problem.) That is the entire point of
this model, is that there is no visible semantic change outside of the ADT
package itself (assuming it doesn't leak the types).

> RHS'Copy indeed seems preferable to T'Copy (RHS), even though the
> former syntax may require qualification in the case where RHS is not a
> name.
>
> RHS'Move is presumably illegal if RHS is a constant that will outlive
> the assignment statement (but OK if, for example, RHS is a function
> call).

I thought that, but someone ought to write it down. :-)

...
> > To provide a modicum of safety, during the scope of a borrower, the
> > RHS from which it originated is frozen, and cannot be dereferenced
> > or changed. Similarly, during the scope of an observer, the RHS and
> > any borrowers derived from it also effectively become observers,
> > providing only read access to the object tree.
>
> Do we want more detail at this point, or just wait for wording?
> When we say, for example, that an object cannot be modified, that
> includes a prohibition on calling a subprogram that might modify it
> (right?). So we are depending on Globals here.

We need a *lot* more detail here, but wording is probably the best way to get
it. See my comments.

...
> > The 'Borrow and 'Observe attributes can be used on function return,
> > but only if the prefix of the attribute reference is derived from a
> > formal parameter that is of the corresponding Access_Kind, and the
> > result subtype has the corresponding Access_Kind.
>
> I know what you mean, but this use of "derived" is confusing.

I'm not sure I do know what he meant -- I rather skipped over this part 'cause
it wasn't making a lot of sense and I have no clear idea of how Borrowers and
Observers work anyway. I probably would use them as little as possible (mostly
so I could dereference my unmanaged pointers). They're the sort of thing that it
seems best to get used to using slowly.

****************************************************************

From: Tucker Taft
Sent: Monday, January 7, 2019  9:42 PM

> [After reading the whole thing.] I've put a few thoughts into the body
> below. In general, this looks promising -- most of the things I hated
> about the earlier proposals are gone, and the stuff I don't like about
> this I can definitely live with. So I suggest pressing forward -- as
> you said before, the devil is in the details, and there are a *lot* of details.

OK, great, I'll press on.  Further comments on your comments below.  Thanks for
your careful review.  It feels like we are beginning to converge.

...
>> We propose to add "ownership-based" access types to the language,
>> with aspect Ownership => True, and with four distinct kinds of
>> subtypes of such access types, as determined by an Access_Kind
>> aspect, specifiable on an object or subtype declaration:
>> * Access_Kind => Owner -- owner subtypes
>> * Access_Kind => Borrower -- borrower subtypes
>> * Access_Kind => Observer -- observer subtypes
>> * Access_Kind => Unmanaged -- unmanaged subtypes
>
> There probably isn't any real need for borrowers or observers to
> implement the containers; they probably will help in some
> circumstances, but most of the time you just need owners and
> unmanaged. I only mention this because if there is still too much complexity for some, we could split that part out.

I don't know how you walk a linked list or tree without an observer or a
borrower.  You could do everything like that with unmanaged pointers, I suppose,
but as you see below, in fact we require that you convert an unmanaged pointer
into an observer or a borrower before you use it.

>
>> Operations that reference or update a heap object designated by an
>> ownership-based access object may treat the designated object as
>> though it were a subcomponent of the composite object containing the
>> object's owning pointer.  An object is "directly owned" by its owning
>> pointer, and simply "owned" by both its direct owner as well as by
>> the owner(s) of the
>> (heap) object of which the owning pointer is a subcomponent.
>> What this means as far as the Global aspect is that there is no need
>> to use "access T" or "<package_name>" to recognize dereferences of
>> ownership-based access objects.  Instead, the Global aspect should
>> recognize that these dereferences are equivalent to referencing
>> subcomponents of the owner(s), and including an object containing an
>> owner in the global variable set for the IN, IN OUT, or OUT mode
>> implicitly includes all the objects owned, directly or indirectly, by
>> this owner.
>
> Somehow I lost you in this paragraph even though I know what the model is.

The point is that since we are treating objects designated by owning pointers as
subcomponents, you can ignore them as far as global side effects, presuming the
"root" of the object tree has been mentioned in Global, or is a formal parameter
with an appropriate parameter mode.

>> Any composite type with an owning object as a subcomponent becomes a
>> by-reference type, much like any composite type with a tagged,
>> inherently limited, or volatile subcomponent is a by-reference type.
>> This simplifies various rules by eliminating implicit copying of
>> objects containing owning pointers.
>
> "By-reference" being a dynamic concept helps here, as we don't have to
> worry about privacy. I probably should have thought of that myself.

Yes, I think this simplifies things.

>> Explicit copying of objects containing owning pointers (e.g.
>> on assignment or function return) automatically performs a "deep"
>> copy, reflecting the model that an object designated by an owning
>> pointer is treated like a component.  Similarly streaming an owning
>> pointer is defined to stream the designated object.
>
> Cool. Never thought about streaming.
>
>> Because owning pointers themselves are of an access type, they are
>> implicitly copied as part of by-copy parameter passing.  They are
>> also, of course, copied as part of an assignment or function return.
>> Unlike the case of a composite object with one of these as a
>> component, we don't have the option of making them into a
>> by-reference type, and thereby eliminating cases of implicit copying.
>> Furthermore, even in an assignment statement, it is not always clear
>> that you would want to do a deep copy when such an access object is
>> assigned to another.  It depends heavily on the context.
>> For example, if you wanted to create a pointer that was to walk over
>> an existing tree structure, you certainly wouldn't want the creation
>> of that temporary pointer to result in the creation of a copy of the
>> tree.  This leads us to define the four kinds of ownership-based
>> access subtypes mentioned above, and also to define some attributes
>> to be used for specifying explicitly how the copying of an
>> access-object is to be performed.
>>
>> The first case to consider is a "simple" assignment from an owner
>> access object to another owner access object.  There are two
>> interesting
>> alternatives:
>>  1) Assign a deep copy of the RHS into the LHS; or
>>  2) Move the ownership from the RHS to the LHS, and null-out the RHS.
>>
>> In both cases, if the LHS already designated an object, we would want
>> to finalize and reclaim the storage for that object before
>> overwriting the LHS.  (Alternatively, we could require that the LHS
>> be null before the assignment, forcing the user to explicitly set it
>> to null first.)
>>
>> To distinguish these two cases we propose the use of an explicit
>> attribute, either 'Copy or 'Move:
>>  1) LHS := RHS'Copy;  --  Deep copy
>>  2) LHS := RHS'Move;  --  Move; set RHS to null We don't think there
>> is a safe, obvious default, so we propose that the attribute is
>> required.  Simple assignment from one owner object to another would
>> not be permitted without specifying such an attribute.
>> Either 'Copy or 'Move must also be used when initializing an owner
>> component of an aggregate as a copy of another owner object, or when
>> returning an owner object from a function.
>> An allocator could be thought of as a short-lived owner object, from
>> which 'Move semantics is implicit. Any owner object that is non-null
>> when it is finalized will be effectively set to null, causing
>> finalization and reclamation of its designated object.
>
> How are these attributes defined? As attributes of objects of
> "ownership-based" access types?

"Move" requires a name of a variable as a prefix.  "Copy" requires merely a name
denoting a value as a prefix.

> Or something else? I wonder because
> typically elementary type assignment is of values, and we have to deal
> with assignment of null and allocators as well. Presumably, those
> (null,
> allocators) wouldn't require some attribute reference, although that
> suggests that the Legality Rule banning direct assignments will be
> interesting to word.

Good point.  No need for an attribute when the RHS is null, an allocator, or a
function call with result subtype of kind Owner.

>> The next case to consider is when you want to create a temporary
>> pointer to "walk" a data structure, either with read/write or
>> read-only access.
>> Here we introduce the notion of a "borrower" and an "observer."  A
>> "borrower" is an access object that provides read/write access to the
>> designated object, and recursively has read/write access to the whole
>> object "tree" through owner subcomponents of the designated object.
>> An "observer"
>> is an access object that provides read-only access to the designated
>> object, and recursively has read-only access through owner
>> subcomponents of the designated object to the object tree.
>>
>> To create such a temporary pointer via an assignment, we require that
>> the LHS be declared as part of the assignment, that it be of the
>> appropriate Access_Kind (Borrower or Observer), and that an attribute
>> ('Borrow or 'Observe) is used on the RHS to indicate what sort of
>> operation is being performed.  Hence:
>>
>>  1) LHS : Acc_T with Access_Kind => Borrower := RHS'Borrow;
>>           --  create a borrower; RHS must be owner or borrower
>>  2) LHS : Acc_T with Access_Kind => Observer := RHS'Observe;
>>           --  create an observer; RHS may be owner, borrower, or
>> observer
>>
>> We could relax the requirement for specifying the 'Borrow or 'Observe
>> attribute in cases where only one would be permitted based on the
>> subtype of the LHS, but we believe it should be possible to be
>> explicit if desired.
>
> This does seem to be a bit of overkill, since the kind is
> implicit/explicit in the declaration of the LHS. There aren't any
> objects of Acc_T without an Access_Kind, right? I suppose it is
> harmless to allow it, but requiring it seems to violate DRY (you are saying the same thing twice).

These attributes are more important when used with a parameter that is an
unmanaged pointer (as discussed below).  When parameterless, I agree they could
be optional.

>> To provide a modicum of safety, during the scope of a borrower, the
>> RHS from which it originated is frozen, and cannot be dereferenced or
>> changed. Similarly, during the scope of an observer, the RHS and any
>> borrowers derived from it also effectively become observers,
>> providing only read access to the object tree.
>
> I've long wondered how this works in the case of a Borrower or
> Observer parameter. And if the answer is that you can't have such
> things, that seems to force everything to be built monolitically
> (since you certainly can't pass an Owner as a parameter, that would be
> taking the data structure apart or copying it, neither which seem like
> a good idea) or using only Unmanaged values.

This brings up the whole issue of aliasing.  SPARK disallows aliasing between
parameters, and between parameters to a routine and the globals used by it.
Originally this proposal included something to disallow aliasing (in annex H).
AI12-0267/0298 worries about race conditions, and perhaps we ought to include
anti-aliasing checks in the stricter conflict checking policies, since clearly
if two by-ref formal parameters are in fact aliased, race conditions are quite
possible.

>> An observer object may be assigned a new value after its declaration,
>> but only if the RHS of the assignment is another observer that is
>> declared in the same or an outer scope, or is an owner component that
>> is in the object "tree" rooted at the object designated by such an
>> observer. In other words, observers can walk "down" an object tree,
>> or jump over to another object tree that is being observed at least
>> as long as the tree the observer is associated with.
>>
>> Similarly, a borrower object may be assigned a new value if the RHS
>> is an owner component within the object tree rooted at the object
>> currently designated by the borrower.  This means a borrower can also
>> walk down its object tree.  Unlike an observer, it is not permitted
>> to "jump" to some other tree.
>>
>> Formal parameters of an ownership-based access type are treated
>> specially -- their Access_Kind has a default.  An IN-OUT or OUT
>> parameter of an ownership-based access type is treated as Access_Kind
>> Owner.  An IN parameter is by default treated as Access_Kind
>> Borrower, but this can be overridden by using a formal parameter
>> subtype with Access_Kind Observer.  As implied by the Access_Kind of
>> an [IN] OUT parameter being Owner, passing an owner object to an [IN]
>> OUT parameter automatically uses "'Move" semantics, both ways,
>> meaning that the actual is set to null during the execution of the
>> subprogram.  This allows the formal parameter to be assigned a new
>> value, including null, with the appropriate semantics.  For an IN
>> parameter, "'Borrow" or "'Observe"
>> semantics, are used as determined by the Access_Kind of the formal.
>> An [IN] OUT formal parameter needs to be set to null implicitly when
>> a subprogram ends abnormally (due to propagating an exception or
>> being aborted), to avoid storage leakage.
>
> OK, I see that you are in fact destroying the data structure for an
> Owner parameter; I guess I can see how that would make sense for an
> "in out" or "out" parameter.
>
> But I don't understand how one can enforce the restrictions on the
> original RHS inside of a subprogram. If it is aliased somehow, how
> would the compiler know what to make illegal?
>
> If you had:
>    procedure Do_Something (Obj : in out Some_Container; Loc : Acc_T)
>        -- Use Loc to find some data and then replace Obj.Data with that.
>
> and a call:
>  LHS : Acc_T with Access_Kind => Borrower := My_Container.Data;
>
>  Do_Something (My_Container, LHS);
>
> How do we determine that this call (or something) should be illegal as
> it attempts to modify a "locked" object?

Again, this is an aliasing issue, and we probably do need to have some way of
disallowing aliasing.  We could say that aliasing is disallowed when using
ownership-based types, since that would be upward compatible.  We would use the
Global aspect to determine whether aliasing with a global is an issue, but that
presumes the Global aspects are pretty precise.  But I suppose one of the goals
of ownership-based access types is to allow more precise Global aspects.  This
really means that using ownership-based access types and writing more precise
Global aspects goes hand-in-hand.

>> An access object of an ownership-based access type can be passed to a
>> subprogram with an access parameter (i.e. a formal parameter of an
>> anonymous access type) only if the subprogram as a whole has its
>> Ownership aspect specified as True.
>
> ??? Since when do subprograms have Ownership aspects? Something is
> confused here.

If we want to allow the use of anonymous access types as parameters, we need
some way to know that is OK.  The idea is to allow an Ownership aspect (it is a
simple Boolean aspect in this proposal, remember) on subprograms, with the
effect of meaning the anonymous access types that appear in the subprogram
profile themselves have Ownership True.  So it is essentially setting a default
for the anonymous access types (similar to the way a Convention on a subprogram
provides the default convention for anonymous-access-type parameters).

>> In that case, an access-to-variable parameter automatically has
>> Access_Kind Borrower, and an access-to-constant parameter
>> automatically has Access_Kind Observer.
>> Similarly, the result type may be of an anonymous access type (i.e.,
>> an "access result"), and the Access_Kind is Borrower or Observer
>> according to whether it is access-to-variable or access-to-constant.
>>
>> The 'Borrow and 'Observe attributes can be used on function return,
>> but only if the prefix of the attribute reference is derived from a
>> formal parameter that is of the corresponding Access_Kind, and the
>> result subtype has the corresponding Access_Kind.  Such a function is
>> called a "traversal function," in that it is used to traverse down an
>> object tree, returning an observer or borrower reference to a point
>> somewhere within the tree.  Such traversal functions could be used to
>> search within a tree, or just do some sort of systematic walk down
>> the tree.
>>
>> Passing a composite object that has an owner access object as a
>> subcomponent implicitly observes or borrows that owner object,
>> depending on whether it is passed as an IN parameter, or as an [IN]
>> OUT parameter, respectively. This is only of concern in places where
>> the caller has visibility on the components.  Presuming the composite
>> type is a private type, no special rules would apply where this
>> partial view is all that is visible, because the objects designated
>> by the owner objects are effectively treated like any other
>> non-visible subcomponent of the composite object.
>
> Maybe this is the answer, but doesn't that cause issues if one is just
> using unmanaged accesses (as in container cursors)? This seesm to
> imply that a subprogram can't modify owned components -- which is a
> problem for an ADT, 'cause what other way is there to do that?

Good point.  I didn't express this correctly.  The owner subcomponents need to
be modifiable if the parameter is of mode [in] out.  So there is no "implicit"
borrowing happening on the subcomponents of an [in] out parameter.  But there is
implicit "observing" happening on the owner subcomponents of an "in" composite
parameter, which makes the object tree rooted at the passed object read-only all
the way down.  And there is implicit borrowing happening if the actual parameter
is of the form "X.all" where X is itself an owner or a borrower.  X is
effectively borrowed by passing any part of the object it designates as an
in-out parameter.

I'll need to work on how to express this elegantly.  This implicit observing or
borrowing will help to eliminate some of the problematic aliasing, by the way.

>> A component of a composite type is not permitted to be of a Borrower
>> or Observer subtype.  Borrowers or observers can only be stand-alone
>> objects or formal parameters.  On the other hand, components can be
>> of Access_Kind Owner or Unmanaged.  Owner objects are described
>> above.
>> Unmanaged objects are intended for use as back pointers, cursors, or
>> other sorts of secondary references.
>>
>> To lessen the possibility of misuse of unmanaged access objects, we
>> do not allow them to be directly dereferenced.
>> Instead, they must be used to initialize an observer or borrower,
>> using an 'Observe or 'Borrow attribute, but where the attribute has
>> an operand that identifies the unmanaged object whose value is to be
>> used, but is protected by the object that is being observed or
>> borrowed. By "protecting" we mean that the protector is an owner, or
>> derived from an owner access object that owns, directly or
>> indirectly, the object designated by the unmanaged access object.
>> This ensures that the unmanaged access object is not pointing off
>> into thin air. For example, here is a possible implementation of a
>> Hashed_Map using ownership-based access types, and using two
>> unmanaged access objects to implement a cursor:
>>
>>   function Element (Container : Map;
>>                     Position : Cursor)
>>      return Element_Type
>>      with Global => null;
>>   ...
>> private
>>   type Node;
>>   type Node_Ptr is access Node with Ownership;
>>   subtype Owning_Node_Ptr is Node_Ptr with Access_Kind => Owner;
>>
>>   type Node is record
>>      Element : Element_Type;
>>      Next : Owning_Node_Ptr;
>>   end record;
>>
>>   type Table is array(Natural range <>) of Owning_Node_Ptr;
>>   type Table_Ptr is access Table with Ownership;
>>
>>   type Cursor is record
>>      Backbone : Table_Ptr with Access_Kind => Unmanaged;
>>      Node : Node_Ptr with Access_Kind => Unmanaged;
>>   end record;
>>
>>   type Map is record
>>      Backbone : Table_Ptr with Access_Kind => Owner;
>>      Count : Natural := 0;
>>   end record;
>>   ...
>>   function Element (Container : Map;
>>                     Position : Cursor)
>>        return Element_Type is
>>      pragma Assert (Position.Backbone = Container.Backbone);
>>         -- Make sure the cursor matches the map
>
> This is part of the precondition for the language-defined containers.
> It might be better to show it that way (of course, that's encapsulated
> in another routine whose name I don't recall at the moment).
>
>>      Node : constant Node_Ptr with Access_Kind => Observer :=
>>         Container.Backbone'Observe (Position.Node);
>>           --  We are observing Container.Backbone, but starting
>>           --  at the object designated by Position.Node.
>
> Again, I'm wondering what the definition of this attribute is going to be.
> Otherwise, this seems fine to me (might be nasty to figure out which
> of Borrower or Observer that is needed, but we'll all figure it out
> eventually).

Not sure why that is complicated.  Borrower if you need write access, Observer
if you can live with read-only access.

>  to have to declare an extra pointer for every use, but I suppose
> that's the cost of extra safety.
>
>>   begin
>>      return Node.Element;
>>   end Element;
>>
>> Unmanaged access objects can be created by copying an object of any
>> other Access_Kind, by applying the 'Unmanaged attribute.  E.g.:
>>
>>    Position := Cursor'(Backbone => Map.Backbone'Unmanaged,
>>                        Node => Some_Node'Unmanaged);
>>
>> We could relax the requirement to use 'Unmanaged on creation of such
>> a value if the target is of Access_Kind Unmanaged, but it seems
>> helpful to allow an explicit use of the attribute.
>
> As previously mentioned, this can violate DRY, maybe not as much here.
> There's obviously an advantage here as simple tools can enforce
> limitations on creation of Unmanaged values.
>
>> It is erroneous to use an unmanaged access object as the operand of
>> <prefix>'Borrow(...) or <prefix>'Observe(...) if it does not
>> designate an object within the object tree designated by the prefix.
>>
>> For operations that need to dereference an unmanaged access object,
>> but do not have a formal parameter that can be used as the
>> "protector" of the unmanaged object, we provide 'Unchecked_Borrow and
>> 'Unchecked_Observe which can be applied to an unmanaged object to
>> produce a borrower or an observer.
>> It is erroneous to use such an attribute if the designated object no
>> longer exists, or if some dynamically enclosing caller of the
>> operation does not have an access object with corresponding access to
>> the object, directly or indirectly.
>> Also, such an operation must have a Global aspect that indicates
>> "access T" or "<package_name>" because there is no formal parameter
>> that can
>> "carry" the side effects of the operation.   For example:
>>
>>   function Element (Position : Cursor)
>>        return Element_Type
>>      with Global => in Hashed_Map;
>>   ...
>>   function Element (Position : Cursor)
>>        return Element_Type is
>>      Node : Node_Ptr with Access_Kind => Observer :=
>>        Position.Node'Unchecked_Observe;
>>   begin
>>      return Node.Element;
>>   end Element;
>
> If the cursor directly carries a general access-to-container value,

As opposed to an officially "unmanaged" pointer to the backbone.

> you
> could implement this as (showing the dereferences for clarity:
>
>    function Element (Position : Cursor)
>         return Element_Type is
>       Node : Node_Ptr with Access_Kind => Observer :=
>         Position.My_Container.all(Position.Node)'Observe;

Actually, you would probably need to write:
          Position.My_Container.Backbone'Observe(Position.Node);

since at this point the 'Observe attribute is defined only on "managed"
pointers.

>    begin
>       return Node.Element;
>    end Element;
>
> I believe (without checking) that the Ada.Containers never require
> using the associated container for any purpose except implementing
> these operations and making the ownership check (which doesn't require
> a dereference - it's a ptr compare). With this formulation, the needed
> Global falls out automatically. And the access-to-container does NOT need to have ownership.

Yes, that works nicely.

> Which is a long-winded way of saying that
> Unchecked_Observe/Unchecked_Borrow
> doesn't seem to be necessary for implementing the Ada.Containers. It
> might still be useful (and surely would add flexibility and might be
> needed for SPARK), but I don't see how to explain/require the needed
> Global setting for these.

Good point.  Perhaps we could live without them, and let someone use
unchecked-conversion if they are desperate.  I just wanted to be sure the word
"Unchecked_" got in there if we were really saying "caveat programmer" as far as
safety.

>
> ---
>
> Two things I didn't see here:
>  (1) Rules to prevent conversions to/from other access types. Is
> derivation from such a type allowed? (I banned it 'cause I didn't want
> to think about it, which probably isn't a good reason. :-)

Well pool-specific access types don't permit much in the way of conversions.
But we do need rules to prevent conversions between subtypes of different
Access_Kinds.

>  (2) Rules for generics? I presume that we're requiring Ownership to
> match for formal access types.

Sounds wise.  ;-)

>  (3) Accessibility rules, or at least some rules to allow the use of
> these (somehow) with access discriminants, as we need to be able to
> implement Reference/Constant_Reference (more generally, user-defined dereferences).

Yes, good point.

> Well, that's three. :-)

****************************************************************

From: Tucker Taft
Sent: Monday, January 7, 2019  10:15 PM

>I like this better than previous versions. I like the subtypes stuff,
>as opposed to depending on anonymous access types.
>
>I also think the presentation in terms of Globals and treating
>designated objects as components makes the motivation clearer
>than some earlier versions.
>
>And the semi-managed (I'll give you the protector object, but you'll
>have to take my word for it) stuff needed for cursors seems like a nice
>solution.
>
>I couldn't resist mentioning (probably prematurely) some details below.

Thanks for reviewing it.  It sounds like I should take a shot at wording.
Comments on your comments below...

>>Handling pointer dereferences has always been a challenge for formal
>>analysis, with approaches such as "separation logic" generally requiring
>>more formalism than would be appropriate even for a skilled programmer.
>>The concept of "pointer ownership" or "object ownership" represents a
>>simpler alternative approach, and reflects a typical way in which most
>>pointers are actually used in the implementation of many ADTs. When
>>pointers have "ownership," this means that the heap object they
>>designate has exactly one "owning" pointer, and when the owning pointer
>>is set to null, the heap object can be safely reclaimed.  Although there
>>might be other pointers designating the heap object under certain
>>circumstances, these other pointers are recognized as being "secondary"
>>references, which can be managed in a way to ensure that no such
>>secondary references are usable after the "owning" pointer is set to
>>null.
>
>This is just !proposal text, so it is ok if it is less precise. Still,
>it seems confusing to me to (twice) talk about an owning object being
>"set to null". This ignores the case where the object is assigned a
>different non-null value and also the finalization case (although
>that case is handled later when we say that finalization effectively
>involves assigning the value null to the finalized object.

Good point.  Set to any new value will trigger finalization.

>>We propose to add "ownership-based" access types to the language, with
>>aspect Ownership => True, and with four distinct kinds of subtypes of
>>such access types, as determined by an Access_Kind aspect, specifiable
>>on an object or subtype declaration:
>> * Access_Kind => Owner -- owner subtypes
>> * Access_Kind => Borrower -- borrower subtypes
>> * Access_Kind => Observer -- observer subtypes
>> * Access_Kind => Unmanaged -- unmanaged subtypes
>>Operations that reference or update a heap object designated by an
>>ownership-based access object may treat the designated object as though
>>it were a subcomponent of the composite object containing the object's
>>owning pointer.  An object is "directly owned" by its owning pointer,
>>and simply "owned" by both its direct owner as well as by the owner(s)
>>of the (heap) object of which the owning pointer is a subcomponent. What
>>this means as far as the Global aspect is that there is no need to use
>>"access T" or "<package_name>" to recognize dereferences of
>>ownership-based access objects.  Instead, the Global aspect should
>>recognize that these dereferences are equivalent to referencing
>>subcomponents of the owner(s), and including an object containing an
>>owner in the global variable set for the IN, IN OUT, or OUT mode
>>implicitly includes all the objects owned, directly or indirectly, by
>>this owner.
>>Any composite type with an owning object as a subcomponent becomes a
>>by-reference type, much like any composite type with a tagged,
>>inherently limited, or volatile subcomponent is a by-reference type.
>>This simplifies various rules by eliminating implicit copying of objects
>>containing owning pointers.
>>Explicit copying of objects containing owning pointers (e.g. on
>>assignment or function return) automatically performs a "deep" copy,
>>reflecting the model that an object designated by an owning pointer is
>>treated like a component.  Similarly streaming an owning pointer is
>>defined to stream the designated object.
>
>Presumably deep copying is illegal if the designated type is limited
>(although perhaps it could be defined to be ok if streaming attributes
>are available).

Gack, I don't think so.  I would say that we should not allow an owning object
of an access-to-limited type as a component of a composite type that is not
itself inherently limited.

>Similarly, streaming of an owning access value is presumably illegal
>if the designated type doesn't have streaming attributes available.

Agreed.

>>Because owning pointers themselves are of an access type, they are
>>implicitly copied as part of by-copy parameter passing.  They are also,
>>of course, copied as part of an assignment or function return.  Unlike
>>the case of a composite object with one of these as a component, we
>>don't have the option of making them into a by-reference type, and
>>thereby eliminating cases of implicit copying.

>Note that in the case of a function return, a by-reference result type
>does not eliminate any copying associated with the assignment to
>the function result object.

If it is inherently limited, we are talking build-in-place.  Otherwise, a "move"
from a local object or a "deep copy" of a longer-lived object would both be
fine.  I think we want to permit the implementation to turn deep copies into
moves whenever it is the last use of an object.

>>Furthermore, even in an
>>assignment statement, it is not always clear that you would want to do a
>>deep copy when such an access object is assigned to another.  It depends
>>heavily on the context.  For example, if you wanted to create a pointer
>>that was to walk over an existing tree structure, you certainly wouldn't
>>want the creation of that temporary pointer to result in the creation of
>>a copy of the tree.  This leads us to define the four kinds of
>>ownership-based access subtypes mentioned above, and also to define some
>>attributes to be used for specifying explicitly how the copying of an
>>access-object is to be performed.
>>The first case to consider is a "simple" assignment from an owner access
>>object to another owner access object.  There are two interesting
>>alternatives:
>>  1) Assign a deep copy of the RHS into the LHS; or
>>  2) Move the ownership from the RHS to the LHS, and null-out the RHS.
>>  In both cases, if the LHS already designated an object, we would want
>>to finalize and reclaim the storage for that object before overwriting
>>the LHS.  (Alternatively, we could require that the LHS be null before
>>the assignment, forcing the user to explicitly set it to null first.)
>>To distinguish these two cases we propose the use of an explicit
>>attribute, either 'Copy or 'Move:
>>  1) LHS := RHS'Copy;  --  Deep copy
>>  2) LHS := RHS'Move;  --  Move; set RHS to null
>>We don't think there is a safe, obvious default, so we propose that the
>>attribute is required.  Simple assignment from one owner object to
>>another would not be permitted without specifying such an attribute.

>Generic body contract issues? Do we always need to know statically
>whether the LHS/RHS-type of an assignment is an owning type?
>If so, then class-wide assignment also needs to be considered.

We don't care about composite objects.  Nothing special there, so I don't see
any problem with class-wide assignment.  The only special rules have to do with
assigning access objects.  I do think the actual and formal access type need to
agree on ownership, and perhaps on Access_Kind as well.  And have to worry about
formal objects as well, presumably!

>RHS'Copy indeed seems preferable to T'Copy (RHS), even though the
>former syntax may require qualification in the case where RHS is not
>a name.

That seems OK.  Access values don't generally show up as anything but a name,
except for null and allocators.  For those two, 'Move and 'Copy are pretty much
equivalent, so I would not want to have to provide an attribute.

>RHS'Move is presumably illegal if RHS is a constant that will outlive
>the assignment statement (but OK if, for example, RHS is a function
>call).

Function call results will either be of Access_Kind Owner, Borrower, or
Observer.  For owner, I think we assume 'Move.  For Borrower or Observer, we
should allow 'Copy but by default they are 'Borrow and 'Observer respectively.

...
>>To provide a modicum of safety, during the scope of a borrower, the RHS
>>from which it originated is frozen, and cannot be dereferenced or
>>changed. Similarly, during the scope of an observer, the RHS and any
>>borrowers derived from it also effectively become observers, providing
>>only read access to the object tree.

>Do we want more detail at this point, or just wait for wording?
>When we say, for example, that an object cannot be modified, that
>includes a prohibition on calling a subprogram that might modify it
>(right?). So we are depending on Globals here.

Yes.  Clearly more details are needed here with respect to the use of the Global
aspect.  As mentioned in my reply to Randy, I think the Global aspect and
ownership will go hand-in-hand, where we use ownership to allow the use of more
precise Global aspects, and we require more precise Global aspects to enforce
the rules of ownership.

>>An observer object may be assigned a new value after its declaration,
>>but only if the RHS of the assignment is another observer that is
>>declared in the same or an outer scope, or is an owner component that is
>>in the object "tree" rooted at the object designated by such an
>>observer. In other words, observers can walk "down" an object tree, or
>>jump over to another object tree that is being observed at least as long
>>as the tree the observer is associated with.
>>Similarly, a borrower object may be assigned a new value if the RHS is
>>an owner component within the object tree rooted at the object currently
>>designated by the borrower.  This means a borrower can also walk down
>>its object tree.  Unlike an observer, it is not permitted to "jump" to
>>some other tree.

>Am I right in thinking that "jumping" is ok in one case but not in the
>other because of CREW (concurrent readers, exclusive writers)?

Yes.  It is OK to have two observers walking the same data structure.  It is
definitely not OK to have two borrowers walking the same data structure.

>Fleshing out the rationale at some point (but perhaps not yet)
>would be useful because I was unsure about this.

Hopefully a sentence or two will make that clearer.

>>Formal parameters of an ownership-based access type are treated
>>specially -- their Access_Kind has a default.  An IN-OUT or OUT
>>parameter of an ownership-based access type is treated as Access_Kind
>>Owner.  An IN parameter is by default treated as Access_Kind Borrower,
>>but this can be overridden by using a formal parameter subtype with
>>Access_Kind Observer.  As implied by the Access_Kind of an [IN] OUT
>>parameter being Owner, passing an owner object to an [IN] OUT parameter
>>automatically uses "'Move" semantics, both ways, meaning that the actual
>>is set to null during the execution of the subprogram.  This allows the
>>formal parameter to be assigned a new value, including null, with the
>>appropriate semantics.  For an IN parameter, "'Borrow" or "'Observe"
>>semantics, are used as determined by the Access_Kind of the formal. An
>>[IN] OUT formal parameter needs to be set to null implicitly when a
>>subprogram ends abnormally (due to propagating an exception or
>>being aborted), to avoid storage leakage.
>>An access object of an ownership-based access type can be passed to a
>>subprogram with an access parameter (i.e. a formal parameter of an
>>anonymous access type) only if the subprogram as a whole has its
>>Ownership aspect specified as True.  In that case, an access-to-variable
>>parameter automatically has Access_Kind Borrower, and an
>>access-to-constant parameter automatically has Access_Kind Observer.
>>Similarly, the result type may be of an anonymous access type (i.e.,
>>an "access result"), and the Access_Kind is Borrower or Observer
>>according to whether it is access-to-variable or access-to-constant.
>>The 'Borrow and 'Observe attributes can be used on function return, but
>>only if the prefix of the attribute reference is derived from a formal
>>parameter that is of the corresponding Access_Kind, and the result
>>subtype has the corresponding Access_Kind.
>
>I know what you mean, but this use of "derived" is confusing.

Yes, bad word choice ...

****************************************************************

From: Randy Brukardt
Sent: Monday, January 7, 2019 10:44 PM

>...
> > and a call:
> >  LHS : Acc_T with Access_Kind => Borrower := My_Container.Data;
> >
> >  Do_Something (My_Container, LHS);
> >
> > How do we determine that this call (or something) should be illegal
> > as it attempts to modify a "locked" object?
>
> Again, this is an aliasing issue, and we probably do need to have some
> way of disallowing aliasing.  We could say that aliasing is disallowed
> when using ownership-based types, since that would be upward
> compatible.  We would use the Global aspect to determine whether
> aliasing with a global is an issue, but that presumes the Global
> aspects are pretty precise.  But I suppose one of the goals of
> ownership-based access types is to allow more precise Global aspects.
> This really means that using ownership-based access types and writing
> more precise Global aspects goes hand-in-hand.

...which is why I was ignoring Observers and Borrowers and just planning to use
unmanaged access values for everything. It's these guys that drag in many of the
ugly complications.

We've looked at aliasing checks in the past, and they aren't practical in Ada.
The 20 pages of definition in your 240-1 convinced me that you haven't found a
breakthough on that point.

I don't think we can afford that complication this late in the process, so I
think we have to do without that for now. That essentially means that a
subprogram like the above one would have to be illegal to declare because of its
possibility of doing something bad. That's probably OK, and a future Ada could
allow it with aliasing restrictions if those were defined.

> >> An access object of an ownership-based access type can be passed to
> >> a subprogram with an access parameter (i.e. a formal parameter of
> >> an anonymous access type) only if the subprogram as a whole has its
> >> Ownership aspect specified as True.
> >
> > ??? Since when do subprograms have Ownership aspects? Something is
> > confused here.
>
> If we want to allow the use of anonymous access types as parameters,
> we need some way to know that is OK.  The idea is to allow an
> Ownership aspect (it is a simple Boolean aspect in this proposal,
> remember) on subprograms, with the effect of meaning the anonymous
> access types that appear in the subprogram profile themselves have
> Ownership True.  So it is essentially setting a default for the
> anonymous access types (similar to the way a Convention on a
> subprogram provides the default convention for anonymous-access-type
> parameters).

Sounds like a hack to me. I'd much rather find a way to allow the interesting
anonymous access properties to be available for named access types, which then
could have the appropriate contracts. There's little reason that one couldn't
have a subtype of a named access type with dynamic accessibility, for instance,
even if we only allowed the subtype to be used to declare a parameter. The same
seems to go for dispatching.

I suppose this is too late for this time around.

I'm especially uncomfortable with allowing ownership access values to be put
into anonymous access types, as that seems to allow them to be converted to any
other type (which we would not allow directly) -- and how to prevent that seems
to add a lot of complications (since this is a resolution issue). The
discriminant case is OK only because the lifetime is too short to be able to do
anything with it (which was the whole reason for using discriminants that way in
the first place - we wanted an ultrashort lifetime).

Anyway, more discussion needed.

...
> > Maybe this is the answer, but doesn't that cause issues if one is
> > just using unmanaged accesses (as in container cursors)? This seems
> > to imply that a subprogram can't modify owned components -- which is
> > a problem for an ADT, 'cause what other way is there to do that?
>
> Good point.  I didn't express this correctly.  ....
>
> I'll need to work on how to express this elegantly.  This implicit
> observing or borrowing will help to eliminate some of the problematic
> aliasing, by the way.

Yes, that was my point with "maybe this is the answer"; I was thinking of the aliasing issues.

...
> >>      Node : constant Node_Ptr with Access_Kind => Observer :=
> >>         Container.Backbone'Observe (Position.Node);
> >>           --  We are observing Container.Backbone, but starting
> >>           --  at the object designated by Position.Node.
> >
> > Again, I'm wondering what the definition of this attribute is going to be.
> > Otherwise, this seems fine to me (might be nasty to figure out which
> > of Borrower or Observer that is needed, but we'll all figure it out
> > eventually).
>
> Not sure why that is complicated.  Borrower if you need write access,
> Observer if you can live with read-only access.

I don't (today) have any inherent understanding of which is which. I assume that
will come with use.

...

> >> Also, such an operation must have a Global aspect that indicates
> >> "access T" or "<package_name>" because there is no formal parameter
> >> that can
> >> "carry" the side effects of the operation.   For example:
> >>
> >>   function Element (Position : Cursor)
> >>        return Element_Type
> >>      with Global => in Hashed_Map;
> >>   ...
> >>   function Element (Position : Cursor)
> >>        return Element_Type is
> >>      Node : Node_Ptr with Access_Kind => Observer :=
> >>        Position.Node'Unchecked_Observe;
> >>   begin
> >>      return Node.Element;
> >>   end Element;
> >
> > If the cursor directly carries a general access-to-container value,
>
> As opposed to an officially "unmanaged" pointer to the backbone.

Right. There's no "backbone" in a list or vector or tree container, or probably
an ordered map or set either. One could always use such a thing if you had to
have it, but that's again additional complication.

> > you
> > could implement this as (showing the dereferences for clarity:
> >
> >    function Element (Position : Cursor)
> >         return Element_Type is
> >       Node : Node_Ptr with Access_Kind => Observer :=
> >         Position.My_Container.all(Position.Node)'Observe;
>
> Actually, you would probably need to write:
>           Position.My_Container.Backbone'Observe(Position.Node);
>
> since at this point the 'Observe attribute is defined only on
> "managed" pointers.

Humm, I was imagining that the object here was an owner object (that is, some
object that contains owned components). It's the owner object that we're
interested in declaring to the world, because it's usually the one that the
world sees, and it's the one that we would (often) be willing to talk about in
the Global aspect. Here, for instance, the Global is "access Map". We can't talk
about "Backbone" even if we wanted to, and using "package Containers.Maps" is
more general than necessary.

> >    begin
> >       return Node.Element;
> >    end Element;
> >
> > I believe (without checking) that the Ada.Containers never require
> > using the associated container for any purpose except implementing
> > these operations and making the ownership check (which doesn't
> > require a dereference - it's a ptr compare). With this formulation,
> > the needed Global falls out automatically. And the
> > access-to-container does NOT need to have ownership.
>
> Yes, that works nicely.
> >
> > Which is a long-winded way of saying that
> > Unchecked_Observe/Unchecked_Borrow
> > doesn't seem to be necessary for implementing the Ada.Containers. It
> > might still be useful (and surely would add flexibility and might be
> > needed for SPARK), but I don't see how to explain/require the needed
> > Global setting for these.
>
> Good point.  Perhaps we could live without them, and let someone use
> unchecked-conversion if they are desperate.  I just wanted to be sure
> the word "Unchecked_" got in there if we were really saying "caveat
> programmer" as far as safety.

I certainly agree with that.

 > ---
> >
> > Two things I didn't see here:
> >  (1) Rules to prevent conversions to/from other access types. Is
> > derivation from such a type allowed? (I banned it 'cause I didn't
> > want to think about it, which probably isn't a good reason. :-)
>
> Well pool-specific access types don't permit much in the way of
> conversions.  But we do need rules to prevent conversions between
> subtypes of different Access_Kinds.

But you can convert to a derived type. I definitely don't want to see Steve's
favorite:

    type Node_Access is access Node;

    type Owned_Node_Access is new Node_Access with Ownership;

because then he'll start griping about all of the fun things he can do with
formal derived types. And these two types are interconvertable. Maybe there's no
problem if both types have the same value for Ownership, but what about subtypes
with the various kinds??

****************************************************************

From: Tucker Taft
Sent: Monday, January 7, 2019 11:16 PM

>> ...
>>> and a call:
>>> LHS : Acc_T with Access_Kind => Borrower := My_Container.Data;
>>>
>>> Do_Something (My_Container, LHS);
>>>
>>> How do we determine that this call (or something) should be illegal
>>> as it attempts to modify a "locked" object?
>>
>> Again, this is an aliasing issue, and we probably do need to have
>> some way of disallowing aliasing.  We could say that aliasing is
>> disallowed when using ownership-based types, since that would be
>> upward compatible.  We would use the Global aspect to determine
>> whether aliasing with a global is an issue, but that presumes the
>> Global aspects are pretty precise.  But I suppose one of the goals of
>> ownership-based access types is to allow more precise Global aspects.
>> This really means that using ownership-based access types and writing
>> more precise Global aspects goes hand-in-hand.
>
> ...which is why I was ignoring Observers and Borrowers and just
> planning to use unmanaged access values for everything. It's these
> guys that drag in many of the ugly complications.

Perhaps, but then you really get no protection at all, as far as I can tell.
>
> We've looked at aliasing checks in the past, and they aren't practical
> in Ada. The 20 pages of definition in your 240-1 convinced me that you
> haven't found a breakthough on that point.

I'll try again, but I'll definitely keep it separate so we can evaluate it
separately.

> I don't think we can afford that complication this late in the
> process, so I think we have to do without that for now. That
> essentially means that a subprogram like the above one would have to
> be illegal to declare because of its possibility of doing something
> bad. That's probably OK, and a future Ada could allow it with aliasing restrictions if those were defined.
>
>>>> An access object of an ownership-based access type can be passed to
>>>> a subprogram with an access parameter (i.e. a formal parameter of
>>>> an anonymous access type) only if the subprogram as a whole has its
>>>> Ownership aspect specified as True.
>>>
>>> ??? Since when do subprograms have Ownership aspects? Something is
>>> confused here.
>>
>> If we want to allow the use of anonymous access types as parameters,
>> we need some way to know that is OK.  The idea is to allow an
>> Ownership aspect (it is a simple Boolean aspect in this proposal,
>> remember) on subprograms, with the effect of meaning the anonymous
>> access types that appear in the subprogram profile themselves have
>> Ownership True.  So it is essentially setting a default for the
>> anonymous access types (similar to the way a Convention on a
>> subprogram provides the default convention for anonymous-access-type
>> parameters).
>
> Sounds like a hack to me. I'd much rather find a way to allow the
> interesting anonymous access properties to be available for named
> access types, which then could have the appropriate contracts. There's
> little reason that one couldn't have a subtype of a named access type
> with dynamic accessibility, for instance, even if we only allowed the
> subtype to be used to declare a parameter. The same seems to go for dispatching.
>
> I suppose this is too late for this time around.
>
> I'm especially uncomfortable with allowing ownership access values to
> be put into anonymous access types, as that seems to allow them to be
> converted to any other type (which we would not allow directly) -- and
> how to prevent that seems to add a lot of complications (since this is a resolution issue).
> The discriminant case is OK only because the lifetime is too short to
> be able to do anything with it (which was the whole reason for using
> discriminants that way in the first place - we wanted an ultrashort
> lifetime).
>
> Anyway, more discussion needed.

Again, I'll try to keep the rules as simple as possible.  I am also not sure we
need these anonymous access parameters.  You seem to be mostly worried about
access discriminants, so I'll focus on those.

> ...
>>> Maybe this is the answer, but doesn't that cause issues if one is
>>> just using unmanaged accesses (as in container cursors)? This seems
>>> to imply that a subprogram can't modify owned components -- which is
>>> a problem for an ADT, 'cause what other way is there to do that?
>>
>> Good point.  I didn't express this correctly.  ....
>>
>> I'll need to work on how to express this elegantly.  This implicit
>> observing or borrowing will help to eliminate some of the problematic
>> aliasing, by the way.
>
> Yes, that was my point with "maybe this is the answer"; I was thinking
> of the aliasing issues.

Yes, if we can make the borrowing and observing rules provide the necessary
aliasing checks, I think we kill two birds with one stone.

> ...
>>>>     Node : constant Node_Ptr with Access_Kind => Observer :=
>>>>        Container.Backbone'Observe (Position.Node);
>>>>          --  We are observing Container.Backbone, but starting
>>>>          --  at the object designated by Position.Node.
>>>
>>> Again, I'm wondering what the definition of this attribute is going
>>> to
> be.
>>> Otherwise, this seems fine to me (might be nasty to figure out which
>>> of Borrower or Observer that is needed, but we'll all figure it out
>>> eventually).
>>
>> Not sure why that is complicated.  Borrower if you need write access,
>> Observer if you can live with read-only access.
>
> I don't (today) have any inherent understanding of which is which. I
> assume that will come with use.

The idea is that a borrower has the object in their hot little hands, and have exclusive access to it, while an observer is to some extent witnessing the object from afar, which allows for many observers.  Think of a bird.  The borrower takes the bird.  Th
e observer watches the bird through their binoculars.
>
> ...
>
>>>> Also, such an operation must have a Global aspect that indicates
>>>> "access T" or "<package_name>" because there is no formal parameter
>>>> that can
>>>> "carry" the side effects of the operation.   For example:
>>>>
>>>>  function Element (Position : Cursor)
>>>>       return Element_Type
>>>>     with Global => in Hashed_Map;
>>>>  ...
>>>>  function Element (Position : Cursor)
>>>>       return Element_Type is
>>>>     Node : Node_Ptr with Access_Kind => Observer :=
>>>>       Position.Node'Unchecked_Observe;  begin
>>>>     return Node.Element;
>>>>  end Element;
>>>
>>> If the cursor directly carries a general access-to-container value,
>>
>> As opposed to an officially "unmanaged" pointer to the backbone.
>
> Right. There's no "backbone" in a list or vector or tree container, or
> probably an ordered map or set either. One could always use such a
> thing if you had to have it, but that's again additional complication.

Good point.  I like the general-access-to-Container approach.  It does mean the
container needs to be aliased in the context where you create the cursor object,
but they are all tagged at the moment.

>>> you
>>> could implement this as (showing the dereferences for clarity:
>>>
>>>   function Element (Position : Cursor)
>>>        return Element_Type is
>>>      Node : Node_Ptr with Access_Kind => Observer :=
>>>        Position.My_Container.all(Position.Node)'Observe;
>>
>> Actually, you would probably need to write:
>>          Position.My_Container.Backbone'Observe(Position.Node);
>>
>> since at this point the 'Observe attribute is defined only on
>> "managed" pointers.
>
> Humm, I was imagining that the object here was an owner object (that
> is, some object that contains owned components). It's the owner object
> that we're interested in declaring to the world, because it's usually
> the one that the world sees, and it's the one that we would (often) be
> willing to talk about in the Global aspect.

Agreed, though normally it is a parameter anyway, so need to mention it further
in the Global aspect.

> Here, for instance, the Global is "access Map". We can't talk about
> "Backbone" even if we wanted to, and using "package Containers.Maps"
> is more general than necessary.

Agreed, but the code above was in the body of Element, so it was using the
access-to-Container value to gain access to an owning pointer that gave it
access to the Element.  We need to know what is the root of the tree into which
the cursor pointer is pointing.  In this case it is
Position.My_Container.Backbone.  For a different data structure, it might be
something else.  But clearly there is a "root" pointer (or pointers), and we
should be able to figure out in which root pointer we will find the object.

On the other hand, we could generalize the 'Observe to work on any object with
subcomponents that are owning pointers, but I was trying to avoid pulling
composite objects into the mix.  But perhaps it is inevitable, since there are
composite objects within the object tree.

>>>   begin
>>>      return Node.Element;
>>>   end Element;
>>>
>>> I believe (without checking) that the Ada.Containers never require
>>> using the associated container for any purpose except implementing
>>> these operations and making the ownership check (which doesn't
>>> require a dereference - it's a ptr compare). With this formulation,
>>> the needed Global falls out automatically. And the
>>> access-to-container does NOT need to have ownership.
>>
>> Yes, that works nicely.
>>>
>>> Which is a long-winded way of saying that
>>> Unchecked_Observe/Unchecked_Borrow
>>> doesn't seem to be necessary for implementing the Ada.Containers. It
>>> might still be useful (and surely would add flexibility and might be
>>> needed for SPARK), but I don't see how to explain/require the needed
>>> Global setting for these.
>>
>> Good point.  Perhaps we could live without them, and let someone use
>> unchecked-conversion if they are desperate.  I just wanted to be sure
>> the word "Unchecked_" got in there if we were really saying "caveat
>> programmer" as far as safety.
>
> I certainly agree with that.
>
>> ---
>>>
>>> Two things I didn't see here:
>>> (1) Rules to prevent conversions to/from other access types. Is
>>> derivation from such a type allowed? (I banned it 'cause I didn't
>>> want to think about it, which probably isn't a good reason. :-)
>>
>> Well pool-specific access types don't permit much in the way of
>> conversions.  But we do need rules to prevent conversions between
>> subtypes of different Access_Kinds.
>
> But you can convert to a derived type. I definitely don't want to see
> Steve's favorite:
>
>    type Node_Access is access Node;
>
>    type Owned_Node_Access is new Node_Access with Ownership;
>
> because then he'll start griping about all of the fun things he can do
> with formal access types. And these two types are interconvertable.
> Maybe there's no problem if both types have the same value for
> Ownership, but what about subtypes with the various kinds??

Fair enough.  We need rules to deal with conversions, because of derived types,
and because we have multiple Access_Kinds.

****************************************************************