Version 1.8 of ai05s/ai05-0022-1.txt

Unformatted version of ai05s/ai05-0022-1.txt version 1.8
Other versions for file ai05s/ai05-0022-1.txt

!standard A.18.2(239/2)          08-04-09 AI05-0022-1/04
!standard A.18.3(152/2)
!standard A.18.4(75/2)
!standard A.18.7(96/2)
!class binding interpretation 06-11-10
!status Amendment 201Z 08-11-26
!status WG9 Approved 08-06-20
!status ARG Approved 9-0-1 06-11-09
!status work item 06-11-10
!status received 06-10-13
!priority Medium
!difficulty Easy
!qualifier Error
!subject Container tampering should be checked for formal subprograms
!summary
Calls to generic formal subprograms of the containers packages either are protected with tampering checks, or otherwise prevent erroneousness when tampering occurs.
!question
There appears to be an interesting problem if the actual function passed to the generic tampers with (cursors or elements) of the container. Say that the "=" operator deletes an element from some globally visible list L, and that we are calling Find (L, ...). Presumably the implementation of Find keeps internally a pointer designating some node of L, and if that designates the element node that was deleted, the pointer will be left dangling, which is a recipe for erroneousness.
We say that the behavior of Find with a misbehaving "=" is unspecified, but A.18(4.v/2) explains that we don't intend that erroneous execution be allowed.
!recommendation
(See Summary.)
!wording
Add after A.18.2(239/2):
It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any Vector parameter to the operation. Either Program_Error is raised, or the operation works as defined on the value of the Vector either prior to, or subsequent to, some or all of the modifications to the Vector.
Corresponding statements need to appear after A.18.3(152/2), A.18.4(75/2), and A.18.7(96/2).
!discussion
Some operations in some implementations can handle ongoing changes to a container, and these should be allowed to do so. However most operations in most implementations will be significantly simplified if they can preclude any ongoing changes to the container during the operation. These will need to check for tampering. Since generic actual subprograms in these cases will often be intrinsic operators or small inlineable subprograms, the check need not be a significant overhead for "macro"-expanded generics, since the optimizer can probably determine whether the state of the tampering flag, whatever it is, changes as a result of the call. If the call on the formal subprogram is not being inlined, then the overhead is already sufficiently great that a tampering check is probably not going to add to it significantly.
!corrigendum A.18.2(239/2)
Insert after the paragraph:
Calling Merge in an instance of Generic_Sorting with either Source or Target not ordered smallest first using the provided generic formal "<" operator is a bounded error. Either Program_Error is raised after Target is updated as described for Merge, or the operation works as defined.
the new paragraph:
It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any Vector parameter to the operation. Either Program_Error is raised, or the operation works as defined on the value of the Vector either prior to, or subsequent to, some or all of the modifications to the Vector.
!corrigendum A.18.3(152/2)
Insert after the paragraph:
Calling Merge in an instance of Generic_Sorting with either Source or Target not ordered smallest first using the provided generic formal "<" operator is a bounded error. Either Program_Error is raised after Target is updated as described for Merge, or the operation works as defined.
the new paragraph:
It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any List parameter to the operation. Either Program_Error is raised, or the operation works as defined on the value of the List either prior to, or subsequent to, some or all of the modifications to the List.
!corrigendum A.18.4(75/2)
Insert after the paragraph:
Iterate calls Process.all with a cursor that designates each node in Container, starting with the first node and moving the cursor according to the successor relation. Program_Error is propagated if Process.all tampers with the cursors of Container. Any exception raised by Process.all is propagated.
the new paragraphs:
Bounded Error

It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of a map package, to tamper with elements of any map parameter to the operation. Either Program_Error is raised, or the operation works as defined on the value of the map either prior to, or subsequent to, some or all of the modifications to the map.
!corrigendum A.18.7(96/2)
Insert after the paragraph:
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
the new paragraphs:
Bounded Error

It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of a set package, to tamper with elements of any set parameter to the operation. Either Program_Error is raised, or the operation works as defined on the value of the set either prior to, or subsequent to, some or all of the modifications to the set.
!ACATS test
ACATS C-Tests should be constructed to check this rule. In particular, Constraint_Error should not be raised (and the test program should not crash).
!ASIS
No ASIS impact.
!appendix

From: Pascal Leroy
Date: Monday, August 14, 2006  3:27 AM

A.18.2(231) says that "<" "should not
modify Container", but it's unclear what Container we are talking about.
Presumably it's the one passed to Is_Sorted, Sort, etc. but a more precise
formulation would not harm.

Observe that "modifying a container" is not a technical term.  Also
observe that we really don't expect "<" (or "=") to modify any container,
not just the one passed to Sort.  So I think we should add a phrase to the
rules that describe "good behavior" for the generic formal operators as
follows:

"The actual function for the generic formal function "foo" ... should not
tamper with the elements of any object of type Container".

Note that I am not proposing that we ask an implementation to detect this
kind of tampering (although the question arose because it can be difficult
to avoid doing the check, depending on the details of your
implementation).  But at least we should express it as a requirement on
the user.

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

From: Pascal Leroy
Date: Friday, October 13, 2006  5:43 AM

The description of the each container package has a clause (eg,
A.18.3(55/2)) that say that if the formal "=" operator misbehaves, the
effect of function Find (among others) is "unspecified".  There are
similar clauses regarding the formal "<" in the nested sorting generics.

AARM A.18(4.v/2) explains that when we say "unspecified" in the
description of the containers, we really mean "unspecified but not
erroneous".  If we mean "erroneous", we say it explicitly.

There appears to be an interesting problem if the actual function passed
to the generic tampers with (cursors or elements) of the container.  Say
that the "=" operator finalizes some globally visible list L, and that we
are calling Find (L, ...).  Presumably the implementation of Find keeps
internally a pointer designating some node of L, and when L gets
finalized, that pointer is left dangling, which is recipe for
erroneousness.  Not good.

The situation is actually not so bad because the implementation of the
containers has to be prepared to perform a "tampering check" in at least
some cases (eg, when calling Iterate).  It would be straightforward enough
(and cheap enough) to set the "tampering lock" when entering the Find
subprogram, and that would automatically detect any tampering and raise
P_E.  So it is possible to prevent erroneousness after all.

Having demonstrated that there is a simple implementation that avoids
erroneousness, I am arguing that we should be changing the definition of
the containers to require a tampering check on Find (and all the
operations that call formal operators).

PS: I realize that one possible option for "unspecified" is "raise P_E" so
an implementation that does the tampering check is certainly legal.  But
since I can't see how the erroneousness can be eliminated without
performing the check, I believe that it should be *required*.

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

From: Matthew Heaney
Date: Thursday, November  9, 2006  2:33 PM

> There appears to be an interesting problem if the actual function passed to
> the generic tampers with (cursors or elements) of the container.  Say that
> the "=" operator finalizes some globally visible list L, and that we are
> calling Find (L, ...).  Presumably the implementation of Find keeps
> internally a pointer designating some node of L, and when L gets finalized,
> that pointer is left dangling, which is recipe for erroneousness.  Not good.

Yes, Find is similar to Iterate, so yes, the same checks should probably apply.

> The situation is actually not so bad because the implementation of the
> containers has to be prepared to perform a "tampering check" in at least some
> cases (eg, when calling Iterate).  It would be straightforward enough (and
> cheap enough) to set the "tampering lock" when entering the Find subprogram,
> and that would automatically detect any tampering and raise P_E.  So it is
> possible to prevent erroneousness after all.

Right.

> Having demonstrated that there is a simple implementation that avoids
> erroneousness, I am arguing that we should be changing the definition of
> the containers to require a tampering check on Find (and all the
> operations that call formal operators).

Yes, that makes sense.

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



Questions? Ask the ACAA Technical Agent