Version 1.6 of ai05s/ai05-0160-1.txt

Unformatted version of ai05s/ai05-0160-1.txt version 1.6
Other versions for file ai05s/ai05-0160-1.txt

!standard A.18.2(249/2)          10-06-07 AI05-0160-1/03
!standard A.18.2(251/2)
!standard A.18.3(154/2)
!standard A.18.3(156/2)
!standard A.18.4(77/2)
!standard A.18.4(79/2)
!standard A.18.7(98/2)
!standard A.18.7(100/2)
!standard A.18.19(9/3)
!standard A.18.20(13/3)
!standard A.18.21(14/3)
!standard A.18.22(11/3)
!standard A.18.23(14/3)
!standard A.18.24(11/3)
!class binding interpretation 09-07-06
!status Amendment 201Z 09-12-17
!status WG9 Approved 10-06-18
!status ARG Approved 9-0-2 09-11-08
!status work item 09-07-06
!status received 09-06-27
!priority Medium
!difficulty Easy
!qualifier Omission
!subject Additional ways to invalidate cursors
!summary
For any container, all cursors designating elements in the target object of an assignment_statement or Assign procedure become invalid.
For lists, all cursors designating elements in the source list of a three parameter Splice call with a Source parameter become invalid. All cursors designating the source element in the source list (but not in the target list) in the four parameter Splice become invalid.
For all bounded containers, it is a bounded error to assign a container object while a tampering check is required.
!question
(1) When an assignment_statement modifies its target object, it is possible that cursors designating elements in it are left pointing to nothing.
For instance, for a list, one reasonable implementation is to deallocate the existing nodes and allocate new ones. In this case, the old cursors are dangling. Similarly, if the target length is longer than the source length, some nodes could be deallocated. And even if the nodes still exist, they hold a different element after the assignment.
A similar concern exists for the new Assign procedure (added by AI05-0001-1).
This is the sort of problem that the concept of invalid cursors was invented to handle. But assignments are not in the list of reasons that a cursor becomes invalid; should they be added? (Yes.)
(2) Similarly, when a Splice moves a node from one list to another, any cursors pointing at that node need to become invalid. That's because cursors include an indication of the enclosing container; and clearly that has changed. For the single node Splice, the actual cursor passed in is redirected, but any copies of the original cursor should be invalid. For the entire list Splice, all of the cursors that designate elements of the source list should be invalid. Should this be fixed? (Of course.)
(3) When a bounded container is assigned while the source is in a state where tampering checks are required, that state will be copied to the target object. Unbounded forms can use an Adjust routine to clear that state, but a bounded form (which is not controlled) cannot clear the state. In that case, the tampering state will be permanently set on the target object and it will not be writable. This is the reason that the Assign procedure was added in AI05-0001-1 to all of the forms of containers. Should we add some sort of rule to handle this case? (Yes.)
!recommendation
(See Summary.)
!wording
Add the following after A.18.2(249/2):
* The vector that contains the element it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement;
Modify A.18.2(251/2):
* The element it designates has been deleted {or removed from the vector that contains the element}.
[Editor's note: We need to talk about which vector it was removed from so that
in the case of Move the fact that it still is in some vector is not important.]
AARM Ramification: An element can be removed via calls to Set_Length, Clear, and Merge; and indirectly via calls to Assign and Move.
[Editor's note: With the AI05-0001-1 definition of Move, we don't need the Move bullet
anymore. It has been marked redundant. Note that we still need the rules for maps and sets, though.]
Add the following after A.18.3(154/2):
* The list that contains the element it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement;
Modify A.18.3(156/2):
* The element it designates has been [deleted]{removed from the list that contains the element}.
[Editor's note: We need to talk about which list it was removed from so that
in the case of Splice or Move the fact that it still is in some list is not important.]
AARM To Be Honest: The cursor modified by the four parameter Splice is not invalid, even though the element it designates has been removed from the source list, because that cursor has been modified to designate that element in a different list.
AARM Ramification: This can happen directly via calls to Delete, Delete_Last, Clear, Splice with a Source parameter, and Merge; and indirectly via calls to Delete_First, Assign, and Move.
[Editor's note: With the AI05-0001-1 definition of Move, we don't need the Move bullet
anymore. It has been marked Redundant.]
Add the following after A.18.4(77/2):
* The map that contains the node it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement;
Modify A.18.4(79/2):
* The node it designates has been [deleted]{removed} from the map{ that contains the node}.
[Editor's note: We talk about which map it was removed from so that this
wording is consistent with that of other containers.]
AARM Ramification: This can happen directly via calls to Clear, Exclude, and Delete.
[Editor's note: Unlike the vectors and lists, Assign (and thus the target of Move)
are not defined in terms of Clear, and thus we need all of the rules as written here.]
Add the following after A.18.7(98/2):
* The set that contains the element it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement;
Modify A.18.7(100/2):
* The element it designates has been [deleted]{removed} from the set{ that contains the element}.
[Editor's note: We talk about which set it was removed from so that this
wording is consistent with that of other containers.]
AARM Ramification: Removing can happen directly via calls to Clear, Exclude, Delete, and Update_Element_Preserving_Key, and indirectly via calls to procedures Intersection, Difference, and Symmetric_Difference.
[Editor's note: Unlike the vectors and lists, Assign (and thus the target of Move)
are not defined in terms of Clear, and thus we need all of the rules as written here.]
Add after A.18.19(9/3) [from AI05-0001-1]
Bounded Errors
It is a bounded error to use a bounded vector if it was the target of an assignment_statement whose source was in the middle of an operation that disallows tampering with elements [Redundant: or cursors]. Either Program_Error is raised, or the operation proceeds as defined.
Add after A.18.20(13/3) [from AI05-0001-1]
Bounded Errors
It is a bounded error to use a bounded list if it was the target of an assignment_statement whose source was in the middle of an operation that disallows tampering with elements [Redundant: or cursors]. Either Program_Error is raised, or the operation proceeds as defined.
Add after A.18.21(14/3) [from AI05-0001-1]
Bounded Errors
It is a bounded error to use a bounded map if it was the target of an assignment_statement whose source was in the middle of an operation that disallows tampering with elements [Redundant: or cursors]. Either Program_Error is raised, or the operation proceeds as defined.
Add after A.18.22(10/3) [from AI05-0001-1]
Bounded Errors
It is a bounded error to use a bounded map if it was the target of an assignment_statement whose source was in the middle of an operation that disallows tampering with elements [Redundant: or cursors]. Either Program_Error is raised, or the operation proceeds as defined.
Add after A.18.23(14/3) [from AI05-0001-1]
Bounded Errors
It is a bounded error to use a bounded set if it was the target of an assignment_statement whose source was in the middle of an operation that disallows tampering with elements [Redundant: or cursors]. Either Program_Error is raised, or the operation proceeds as defined.
Add after A.18.24(11/3) [from AI05-0001-1]
Bounded Errors
It is a bounded error to use a bounded set if it was the target of an assignment_statement whose source was in the middle of an operation that disallows tampering with elements [Redundant: or cursors]. Either Program_Error is raised, or the operation proceeds as defined.
!discussion
For question (2), the problem is that the wording of the various operations on lists talk about "removing elements" from lists, while A.18.3(156/2) talks about "deleting elements". So we just need to change A.18.3(156/2) to talk about "removing elements" and then Clear, Splice, and Merge are clearly covered. So are Assign and Move (with its AI05-0001-1 definition, not the original one) - as they both reference Clear, but not an assignment_statement (so we still need new wording for that case).
Note that vectors have a similar problem, as Clear, Set_Length, and Merge are defined in terms of "removing" elements, rather than deleting them. The different terminology is disturbing. Similar comments apply to maps and sets, too.
!corrigendum A.18.2(249/2)
Insert after the paragraph:
the new paragraph:
!corrigendum A.18.2(251/2)
Replace the paragraph:
by:
!corrigendum A.18.3(154/2)
Insert after the paragraph:
the new paragraph:
!corrigendum A.18.3(156/2)
Replace the paragraph:
by:
!corrigendum A.18.4(77/2)
Insert after the paragraph:
the new paragraph:
!corrigendum A.18.4(79/2)
Replace the paragraph:
by:
!corrigendum A.18.7(98/2)
Insert after the paragraph:
the new paragraph:
!corrigendum A.18.7(100/2)
Replace the paragraph:
by:
!corrigendum A.18.19(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!corrigendum A.18.20(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!corrigendum A.18.21(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!corrigendum A.18.22(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!corrigendum A.18.23(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!corrigendum A.18.24(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!ACATS Test
Using invalid cursors causes erroneous execution, so those rules cannot be tested. The bounded error rules could be tested, but it isn't interesting as it represents a program bug.
!appendix

From: Randy Brukardt
Date: Saturday, June 27, 2009  12:02 AM

Here are a couple of issues I noticed while putting part of the bounded containers AI
into the consolidated Standard:

There seems to be a missing rule having to do with invaliding the cursors of the Target
of an Assign operation.

It is easy to see that this is necessary: imagine a list object and a list cursor
referencing it (which is most likely a pointer at a node). When an assignment is done,
one reasonable implementation would be to deallocate the old nodes and then create new
ones to hold the new elements. In this case, the list cursor is dangling afterwards.
Even if the nodes are reused, if the Source is shorter than the old Target, there is
a chance that the list cursor is pointing to nothing.

It occurs to me that this also could occur for an assignment_statement (which means
that this is an existing issue in the standard).

We need a statement like:

    * The list that contains the element it designates has been used as the Target of
      a call to Assign, or as the target of an assignment_statement;

added to every container. Correct?

Should this be done as a separate AI (since it appears to be an existing issue), or
should we just add it to AI05-0001-1? (We do have an appropriate other AI to add this
to, since I have an action item to fix a similar problem with Splice. So maybe it ought
to go there and be a Binding Interpretation.)

---

Related in a way is the behavior of assignment_statements for the bounded forms. (This
is an old issue that Matt brought up long ago.) The reason that we added Assign is that
an assignment_statement will misbehave for a bounded form in various ways. If the source
list is assigned while it is in some context where a tampering check is required, the target
is going to have whatever triggers that check (probably a flag or counter) set. But it
will never clear that flag or counter because it itself is not in the tampering context.

For the unbounded form, we can use an Adjust routine to fix this problem, but the bounded
form has no such crutch.

Because of this, we need some rule about the use of the assignment statement for a bounded
form. The easiest rule is that it is bounded error to use a bounded container that has been
the target of an assignment statement. Either it works or Program_Error is raised. But that
seems overly broad; it would be better to tie the rule to the state of the source.
Unfortunately, we don't have the concept of a tampering context (even though we talk about
it all the time). So we would have to say something like:

* It is a bounded error to use a list L if it was the target list of an assignment_statement
  whose source list was being used in such a way that a check for tampering with cursors
  or tampering with elements could be required. Either Program_Error is raised, or the
  operation works as defined.

AARM Reason: Since bounded lists are not controlled types, it is not possible to reset the
indication that a tampering check is needed as part of an assignment if it is currently set
in a source list. Thus, future operations on such a list could raise a tampering exception
even if there is no requirement to detect tampering at the time of the operation. This rule
makes that OK. Note that this can only happen when the source list is actively being used
in a context where tampering checks are needed, such as inside of the Process routine of
Iterate or during the lifetime of an object of type Reference_Type.

Again, this would need to be added to definition of every bounded form. This is directly
related to the definition of the bounded form, so it makes sense to add it directly to
AI05-0001-1. But then do we need to send the AI back to the ARG?

Any comments on the wording suggestions?

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

From: Tucker Taft
Date: Saturday, June 27, 2009  1:32 PM

I would create a separate AI for these assignment-related issues.

Other comments below...

> ...
> So we would have to say something like:
> 
> * It is a bounded error to use a list L if it was the target list of 
> an assignment_statement whose source list was being used in such a way 
> that a check for tampering with cursors or tampering with elements 
> could be required. Either Program_Error is raised, or the operation works as defined.

I think saying "list" so many times doesn't help.  Isn't this adequate:

  * It is a bounded error to use a list L if it was the target of an
    assignment_statement whose source was in the middle of an operation
    that disallows tampering with elements [Redundant: or cursors].
    Either Program_Error is raised, or the operation proceeds as defined.

Note that saying "disallows tampering with cursors" is adequate, since tampering
with cursors is included in the definition of what it means to tamper with elements.

...
> Again, this would need to be added to definition of every bounded 
> form. This is directly related to the definition of the bounded form, 
> so it makes sense to add it directly to AI05-0001-1. But then do we 
> need to send the AI back to the ARG?

Make it a new AI.
 
> Any comments on the wording suggestions?

See above.

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

Questions? Ask the ACAA Technical Agent