AI22-0164-2
!standard X.Y(PP) 26-07-15 AI22-0164-2/02
!standard A.B(PP)
!class Amendment 26-05-25
!status work item 26-05-25
!status received 26-05-25
!assigned author Tucker Taft
!submitter Tucker Taft
!priority Medium
!difficulty Medium
!subject Move and Swap operations
Provide support for Move (A =< B) and Swap (A >=< B)[a][b][c][d][e][f][g] operations that take advantage of the implicit level of indirection which will often be used for optional and expandable objects, as proposed in AIs AI22-0152-1 and AI22-0148-1. Also allow the programmer to specify, using the Storage_Pool aspect, that the storage for an object should be allocated from the same storage area associated with a preexisting object, with the intent of later swapping or moving the new object into some part of the preexisting object.
Presuming that one or both of the "optional objects" AI and the "expandable objects" AI are approved, it would be very useful to have operations that recognize that such objects are often represented with a level of indirection, and at least in some cases, the manipulation of implicit pointers can avoid an expensive recursive copy operation.
We recommend that we add support for two operations that take advantage of the implicit level of indirection when possible. The two operations are Move and Swap. Move presumes that the source is an optional object, and it moves the content of the RHS into the LHS, leaving a null behind in the RHS.[h][i] Constraint_Error will be raised if the target does not allow null, but the prior value of the source is null. Swap, on the other hand, works whether both or neither of the objects are optional. It exchanges the content of the two objects. Both Move and Swap would take advantage of the level of indirection if possible, by using (implicit) pointer manipulation rather than physical copying so long as the LHS and the RHS can use the same storage area.
In addition to these two new operations, we propose to generalize the Storage_Pool aspect so that it can be specified when declaring a standalone object, to indicate that it should be allocated from the same storage area as some preexisting object, with the intent of later swapping or moving some part of the new object into some part of the preexisting object. We originally proposed a different aspect (simply "Storage"), but if we want users to be able to create their own storage managers for stand-alone objects, it seems OK to reuse the notion of Storage_Pools. Allocate, Deallocate, and Storage_Size are still the fundamental operations needed, and there is no particular reason that a storage pool type designed for managing a heap couldn't be used for managing the subcomponents of a stand-alone object.
At the syntax level, we propose that Move is performed as an assignment operation that occurs as part of an assignment statement, object initialization, parameter passing, function return, or aggregate initialization, using the syntax "=<". Move makes a logical copy of the value of the RHS object, then the RHS is set to null, and finally that logical copy is assigned, passed, or returned. Here are four contexts where the Move operation could be used, as each is, effectively, the source of an assignment:
Y : T =< Z; -- Z is null afterward
begin
X.Left =< Y.Right; -- Y.Right is null afterward
Y =< (Y.Value, Left =< Y.Right, Right =< Y.Left);
-- Note that this presumes the aggregate is built up before
-- moving the aggregate into the LHS of the statement.
-- That is consistent with the usual rule for evaluating the RHS first.
-- Think of the "tartar" example in RM 5.2(27).
-- But in this case, the evaluation of the RHS actually has side
-- effects on the LHS, due to the Move semantics, so by the time
-- the Move to Y takes place, Y.Left and Y.Right have already been
-- set to null.
List =< (New_Item, Next =< List);
-- Prepend New_Item onto the front of a linked list.
return =< Z.Left; -- Return value of Z.Left, leaving Z.Left null.
-- Function must not
have an aliased result ...
Copying and setting to null as part of the Move operation is meant to be equivalent to invoking a function Move with one in-out parameter, with a body of approximately:
function Move (B : in out null or T)
return null or T is
Result : constant null or T := B;
begin
B := null;
return Result;
end Move;
So given "A =< B", by treating it as equivalent to "A := Move(B)" or "A => Move(B)", then afterward B is null, and the value assigned/passed in A is the prior value of B.
The Swap operation would be similar to an assignment statement, but using the syntax "A >=< B;", with the effect of swapping the contents of the LHS and the RHS. As an example:
Y.Left >=< Y.Right; -- This is a more direct way to swap subtrees.
If we declare the Storage_Pool aspect of Y to refer to X, then the Move of Y.Right into X.Left above would be able to use pointer manipulation rather than copying:
Y : T with Storage_Pool => X'Storage_Pool;
-- This indicates that Y will be associated with the same
-- storage area as X, so Move and Swap can avoid making copies.
-- When Y goes out of scope, if it is not already null,
-- it is set to null as part of its finalization, ensuring its
-- space is reclaimed (if the storage area does reclamation).
If T is a limited type, specifying the Storage_Pool aspect will be required to allow the use of Move or Swap between X and Y, because copying is not permitted for limited types, and only by specifying the Storage_Pool aspect can Move and Swap be guaranteed to not require copying. Furthermore, the limited objects will need to be declared as optional, so the compiler will know to implement them with a level of indirection. Note that the compiler can still avoid copying in other cases by noticing that a given variable is always Moved or Swapped with (part of) some other variable, but that would be considered an optional optimization.
No Storage_Pool aspect would need to be specified when moving from one component of an object to a different component of the same object (as in, say, X.Right =< X.Right.Left) or when swapping two components of the same object (as in Y.Left >=< Y.Right), since they would necessarily be associated with the same storage area.
Although the examples above with aggregates as the RHS use =< rather than regular assignment, in fact if the RHS is an aggregate or a (non-aliased-result) function call, there really shouldn't be a difference between the Move semantics and regular assignment, since the RHS is just a temporary object, and its storage should be reclaimed[j][k] whether or not it ends up as "officially" null afterward. So these two examples could have been:
Y := (Y.Value, Left =< Y.Right, Right =< Y.Left);
-- Swap Right and Left subtrees.
List := (New_Item, Next =< List);
-- Prepend New_Item onto the front of a linked list.
(TBD.)
The prior version of this AI (AI22-0164-1) proposed the use of 'Move and 'Swap attributes. This made some reviewers uncomfortable because of the side-effect on the prefix of the 'Move attribute, and the asymmetry of the 'Swap attribute. So this version goes for some new syntax, which by fiat has the desired side effects, and also provides a symmetric syntax for Swap. The attribute syntax clearly requires less syntactic invention, but perhaps that is a bug rather than a feature given that the semantics is significantly different from existing attributes.
The =< syntax for Move and the >=< syntax for Swap were chosen because they didn't come with any existing "baggage" from some other operation or other language, and the syntaxes provide a hint as to the direction of data flow. Also, =< works pretty well for parameter passing and aggregate components, because it simply inverts the '>' in "=>", so A => B becomes A =< B when Move semantics are desired for the parameter or aggregate[l][m] component. Other syntax or other approaches could clearly be considered for one or both operations.
As mentioned above, we earlier suggested having a new attribute Storage for specifying that one object should be allocated in the same storage area as another, to ensure Move and Swap can be performed with pointer manipulation. However, it seems that it would be simpler to reuse the Storage_Pool aspect for specifying where to allocate the subcomponents of a stand-alone object. This implies that all stand-alone objects, and probably all component objects, have a Storage_Pool aspect, which might generally refer to an implementation-defined storage pool of some sort, and might have various special implementation-defined properties.
See the !recommendation above.
TBD.
See ARG GitHub issue #149 for some discussion of these operations.
[a]I find these operator symbols (=<, >=<) a bit confusing visually, perhaps because the characters =, <, > are used so much for other operators. How about ":-" for Move, and ":=:" for Swap? Using the single line "-" instead of the double line "=" suggests that there is only one object, not two equal objects. On the other hand, perhaps ":-" and ":=" and ":=:" are too similar.
[b]I think we will should discuss the choice of operation notation in an ARG meeting, given how many possibilities there are.
[c]Oh oh, it seems I activated a control to overstrike my text... I hope it can still be read. I wonder what I did...
I agree that the operation notation is for discussion.
[d]I will write an e-mail to the ARG list that proposes using the normal ":=" for both Move and Swap, but in an extended form of the assignment statement. It is a bit weird, though...
[e]You can edit your own comments, in general, in case you want to remove the strike-through.
[f]The text was not overstruck when I wrote it, nor in "edit" mode. It seems the string (-) triggered overstriking, which ended with the string ":-". Let's see what happens to this reply... yep, same thing, the text between those strings is overstruck. I modified those strings in my original comment, and that got rid of the overstrike. I wonder if this is documented somewhere :-)
[g]Fascinating. I have sometimes wanted to format comments, but have not been able to. A quick Google/Gemini search provided:
You can format text in Google Docs comments (like making it bold, italics, or strikethrough) by using simple markdown shortcuts. There are no drop-down menus or buttons for this, so you just type the following symbols directly before and after the text you want to format:
Bold: Put an asterisk * before and after the text (e.g., *important*).
Italics: Put an underscore _ before and after the text (e.g., _check this_).
Strikethrough: Put a hyphen - before and after the text (e.g., -old text-).
Combined formatting: You can combine them, like _*bold and italics*_.
Important Tips
No spaces: Make sure there are no spaces between the formatting symbol and the first or last letter of your text. For example, *bold text* will work, but * bold text * will not.
Colors: You cannot customize the background or text color of your comments.
Tagging: Don't forget that you can type @ or + followed by a person's name to tag them and assign them an action item directly in the comment.
[h]I suggest that Move be generalized to apply to all non-limited types, and defined to leave the RHS as default-initialized, rather than always null. This will not change the effect for optional objects, but will be useful for access types and types that may need implicit pointers, even if not optional.
[i]I worry about going too far. Many objects don't have well-defined default initial values. Also, this proposal will already work for access subtypes that allow null, so that seems to be the large majority of access subtypes.
[j]The temporary object for the RHS contains implicit pointers to Y.Right and Y.Left. I assume, then, that the reclamation of the storage for the temporary object does not include deallocating the objects designated by those implicit pointers, right?
What happens if such an aggregate RHS evaluates some Move operations, but then raises an exception before the temporary object is completely built and assigned to the LHS. Now the implicit pointers in the temporary object are the only pointers to Y.Right and Y.Left, so their designates should be deallocated, I assume, to avoid memory leaks.
[k]This is similar to what happens when you have multiple allocators in an initialization expression and then an exception is raised. Storage reclamation is expected, but the ACATS tests are unlikely to enforce it.
[l]Is Move possible only when named association is used in a call or aggregate? Or can we use "(..., =< B, ...)" in positional association?
[m]Named notation only in this proposal!