!topic LSN on Tag Propagation and Dispatching
!key LSN-1031 $Revision: 1.2 $ on Tag Propagation and Dispatching
!reference MS-3.4.2;4.6
!reference 92-1066.a Randy Brukardt 92-05-22 (Dispatching on multiple types)
!reference 92-1124.a Randy Brukardt 92-06-04 (Tag propagation for assignments)
!reference 92-1138.a Randy Brukardt 92-06-04 (Equality Tag Checking)
!from Tucker Taft $Date: 92/06/13 07:47:10 $
!discussion

There have been several questions relating to "tag propagation,"
by which we mean determining what is the controlling tag value
for a call on a dispatching operation (see MS-3.4.2;4.6).

In particular, Randy Brukardt has identified the following issues:

  1) the revised rules allowing a single operation to be 
     primitive for more than one tagged type (92-1066.a) makes
     tag propagation more difficult, and complicates the symbol-table
     representation of dispatching operations;

  2) it is not clear what should be done for a function with 
     a controlling result, but no controlling operands, when used
     to initialize a tagged class-wide variable (92-1124.a);

  3) it is not clear how the special case for "=" and "/="
     relates to tag propagation, particularly in the case of:
       F + A = F + B
     where F has a controlling result, and A and B are class-wide
     objects (92-1138.a).

This LSN will attempt to address these issues.

First of all, we had originally outlawed having a single
operation being primitive on two tagged types (see MS-3.4.2(3);4.0).
Then, when we saw an example in a message from Ted Baker that
had two private types, both of which turned out to be tagged in
the private part, we realized there was a usability issue.
We therefore decided to allow declarations of such operations,
but disallow calls that would have controlling
class-wide operands of two different types.

However, Randy has pointed out how this significantly complicates
implementation.  Furthermore, there is a usability issue that
the error is not detected until a call is attempted.
It might be better to force the designer of the package,
rather than the clients, to deal with the issue.  In particular,
in most cases, one of the two tagged types can normally
be changed to a class-wide type, producing a more generally
useful routine in the process.

Given all of this, we now think it makes sense to revert to the
older rule (no operation may be primitive on two different
tagged types).  What this means is that even if the operation
is declared in a visible part where one of types is not
visibly tagged, if in the private part both are tagged,
then the error must be detected and reported.  Since dispatching
tables must be built for both tagged types anyway, it will probably
be quite easy at that point to notice that a single operation
is about to appear in two different dispatching tables, and
at that point report the error.

This hopefully resolves issue (1).

Issue (2) and issue (3) depend on the detailed formulation
of the rules for tag propagation given in MS-3.4.2.  The current
wording leaves something to be desired, so most of the remainder of this
LSN will analyze the wording issues of this section.  

First, however, let us try to further motivate the special case for 
"=" and "/=" with respect to tag checking:

  In Ada 83, there are several places where relationals in general,
  or equality operators in specific, are given special treatment.
  This reflects their inherent semantics.  They are not just like
  any other operators.  First of all, they return BOOLEAN rather
  than their operand type.  Second, they *never* raise CONSTRAINT_ERROR
  (though of course the evaluation of their operands might).
  Third, "=" and "/=" are defined to be "perfect" complements
  of one another, i.e., for all A, B, (A=B) = not(A /= B).
  
  Note that these special properties of "=" (whether predefined
  or user-defined) as well as other predefined relationals
  are in contrast to the properties of other operators.  
  For example, on boolean arrays, "A (predefined relational) B" does 
  not raise CONSTRAINT_ERROR on length mismatch, 
  whereas "A and B" and "A := B" do.  Similarly, on variant records, 
  "A = B" does not raise constraint error on a discriminant 
  mismatch, whereas "A := B;" does (presuming A is constrained).
  
  Since we anticipate that users of variant records may transition
  toward using tagged class-wide types, it seems important that existing
  uses of "=" and "/=" not suddenly start resulting in run-time
  errors.

Given the above motivation, let us see how the rules for tag propagation
can be formulated so that they provide good usability, without
creating overly complex rules (either from a semantics or implementation
point of view).

First, some terminology:

   *) Given a primitive (dispatching) operation of a tagged type T,
      a "controlling operand" is an actual parameter corresponding
      to a formal parameter of type T, or the object designated
      by an actual parameter corresponding to a formal access parameter
      designating T.

   *) An operand is a "controlling result" if it is the result of a 
      call on a primitive operation of type T with a return type T;
      in addition, a parenthesized or qualified expression is a controlling
      result if its operand is a controlling result.

   *) The "controlling tag value" for a call on a dispatching operation
      is the tag value that determines which implementation of the operation
      is performed.  

   *) An operand is called "tag-indeterminate" if it is the 
      the controlling result of on operation whose
      tag must be determined by context, that is, all of whose controlling 
      operands (if any) are tag-indeterminate.

   *) An operand is called "dynamically tagged" if its tag is dynamically
      determined "internally," that is, if it is of a class-wide 
      tagged type, or is the controlling result of an
      operation one of whose controlling operands 
      is dynamically tagged (and whose other controlling operands,
      if any, are dynamically tagged or tag-indeterminate -- this part
      is a ramification of legality rule (2) below).

Here are some legality rules:

   1) A non-controlling operand expected to be of a specific type
      must not be dynamically tagged.
        [Note: This is basically a methodological restriction, to ensure
        that truncation (conversion) to a specific type is only performed
        when explicitly requested.]

   2) If one controlling operand of an operation is dynamically 
      tagged, then all controlling operands must be dynamically tagged
      or tag-indeterminate.
        [Note: This is another methodological restriction, to minimize
        user confusion over whether or not the dynamically tagged operands
        are implicitly converted (truncated) to the specific type, or are
        checked against the statically known tag.]

   3) The initial expression for a tagged class-wide object declaration
      must be dynamically tagged.
        [Note: There is no tag check in this case, since the tag of the
        object is taken from the initial value.]

   4) The controlling tag value for a call on an abstract dispatching
      operation of type T must not be T'TAG.  
        [Note: This is a compile-time check;
        see below for tag propagation rules.]

Here are the tag checking and propagation rules:

   a) If a call on a dispatching operation of T has any dynamically tagged
      controlling operands, then their tags are checked at run-time
      to ensure they are all the same (presuming there is more than one),
      and their common tag is the controlling tag value for the call.
      If the tags differ between dynamically tagged controlling operands, 
      then CONSTRAINT_ERROR is raised except if the designator for the 
      call is "=" or "/=" and the result type is BOOLEAN,
      in which case inequality is indicated.
        [Note: Legality rule (2) above implies that all controlling
        operands in this case will either be dynamically tagged or 
        indeterminate.]

   b) If a call on a dispatching operation has no dynamically tagged
      controlling operands, and it is not itself a tag-indeterminate 
      controlling operand, then the controlling tag value for the call 
      is T'TAG.  (This is normal "static" binding.)

   c) If a call on a dispatching operation is itself a tag-indeterminate
      controlling operand, then its controlling tag value is 
      that of the enclosing call, as determined by these rules.

DISCUSSION AND EXAMPLES

The above rules imply that only the tags of dynamically 
tagged operands are checked for equality.  Tag-indeterminate 
operands are never checked; they instead inherit the controlling tag
from the nearest enclosing non-tag-indeterminate context.

The algorithm for propagating tags is pretty straightforward;
a bottom-up walk followed by a top-down walk is sufficient.

On the way up, you keep track of whether each sub-expression
is dynamically tagged, or tag-indeterminate, and enforce the
legality rules (1) to (3).  On the way down, you only need to revisit
tag-indeterminate operands, to tell them either they have a statically
determined tag (with a check on legality rule (4)), or where 
they can find their dynamically determined tag.  

In the generated code, the code for evaluating
tag-indeterminate controlling operands whose tag is not
determined at compile-time, must necessarily follow
the evaluation of the dynamically-tagged operand whose tag
they inherit.

Looking at some of Randy's example, we see the following:

   Assume "A, B: T'CLASS := ...;"
   "X, Y : T;"
   and a primitive "function F return T;"

   A : T'CLASS := F;  -- Disallowed by rule (3)

   B : T'CLASS := X;  -- Disallowed by rule (2)

   if A = B then   -- yields FALSE if A'TAG /= B'TAG (rule (a))

   if A = F then   -- controlling tag for F taken from A (rule (c))

   if X = F then   -- controlling tag for F is statically T'TAG (rule (c))

   A := B;         -- CONSTRAINT_ERROR if A'TAG /= B'TAG (rule (a))

   if A = B + F then -- controlling tag for F comes from B (rule (c))
                     -- FALSE if A'TAG /= B'TAG (rule (a))

   if A + F = B + F then -- controlling tag for F#1 comes from A, (rule (c))
                         -- controlling tag for F#2 comes from B  (rule (c))
                         -- FALSE if A'TAG /= B'TAG  (rule (a))

   if A + B = F then  -- CONSTRAINT_ERROR if A'TAG /= B'TAG (rule (a))
                      -- controlling tag for F comes from either A or B
                      --   (rule (c))

   if F = F then      -- controlling tag for F's is T'TAG (rule (b))


These rules seem to give pretty reasonable answers in all cases.
"Default tags" are only used when the expression has no class-wide operands
around, to be consistent with normal Ada '83 rules.  This means that
"tagged" can be added to a type without introducing tag-propagation 
illegalities.  Default tags are not used when initializing a class-wide
object.

Comments welcomed!
-Tuck