SAFEty and the Cross Referencing of BLASTs

[Mark S. Miller <vlad!mark>]

Date: Sat, 1 Dec 90 16:24:37 PST
   From: xanadu!roland (Roland King)
   Subject: Documentation of Blasts

   Would you summarize for me just what you need?  ...


Collecting the possible BLASTs out of a [member] function is a
probably a job for X4Ref, as it is a property of a program as a whole
and has little to do with an individual module.  As the job should
bottom out where it encounters SAFE declarations, and there's been
some question about these lately, I'll first document SAFE, and then
what XLint should do with it.

All the below is tentative.  It is intended as a first stab at what
these tools should do.


			Better SAFE than ...

An ideal definition of SAFE would be: "If a [member] function is
declared SAFE, then it may not allocate any memory, it may not
(transitively) call anything which allocates memory, it may not BLAST
anything which it doesn't catch, and it may not call anything which
(transitively) calls anything which may BLAST anything it doesn't
catch."  However, SAFEty should be locally checkable (by XLint) for a
single module, so we modify the definition as follows:

If a [member] function is declared SAFE, then it may not allocate any
memory, it may not BLAST anything which it doesn't catch, and it may
only call [member] function which are themselves declared SAFE.
Otherwise XLint complains (unless the complaint is explicitly turned
off in the standard XLint way).  In order for XLint to do even this,
it will need to do proper overload resolution (we knew this day would
come).

A perfectly adequate (though imperfect :-)) version of this feature in
XLint could drop the "which it doesn't catch" clause from the above
spec.

There is unfortunately an ambiguity as to what is being declared SAFE
when a method declaration is declared SAFE.  Is it this particular
method or is it the message?  Unfortunately, we may need both.
Consider:


CLASS(Foo,Heaper) {
  PUBLIC:
    virtual void zip ();
};

CLASS(Bar,Foo) {
  PUBLIC:
    virtual void zip () SAFE;
};

CLASS(Baz,Bar) {
  PUBLIC:
    virtual void zip ();
};

I propose that the above implies that both Bar::zip() and Baz::zip()
are SAFE (but not Foo::zip())---anyone sending the zip() message to
anything which is known to be a kind of Bar has a right to assume
safety.  Types are contracts, and sub-types inherit all the
obligations of their super types.

X++ semantics point (optional): The specification of a message (e.g.,
in terms of pre-conditions and post-conditions ala Eiffel) without a
SAFE declaration only states a conditional obligation: Here is what
those who claim to implement this type must do if they return normally
from this request.  However, in the absence of a clause in the
contract to the contrary, the implementor always has the option to
BLAST instead (for example, because there is no memory left).  "SAFE"
is the machine-checkable form of a "clause in the contract to the
contrary" which makes the obligation (in the message spec)
unconditional.  More complex clauses are not in general expected to be
machine checkable, anymore than a type checker could check all notions
of types as contracts.

Unfortunately, it is sometimes possible to know when Bar::zip()
specifically is being invoked, and therefore conceivably useful to
know that this method specifically is SAFE even if the zip() message
starting at Bar is not in general SAFE.  I have an idea how one would
accomodate this case, but unless anyone feels it is likely to be
needed I will keep this complex wrinkle to myself.

We have SAFE appear at the right of a [member] function declaration so
that eventually it can expand to "throw()" (see Bjarne's exception
handling proposal).  They are not synonyms--SAFE is more restrictive
than "throw()" (therefore SAFE does imply "throw()").


		Some Implications of SAFE Declarations:

Most construction can probably be written so that unSAFE computation
happens ahead of time in the pseudo-constructor, and then the
constructor itself can frequently be declared SAFE.  Note that XLint
must include in its analysis of constructor safety the (possibly)
implicit call to the superclass constructor, and all the (probably)
implicit calls to member object constructors.  This latter can
currently be ignored for pure X++ code, as the only member objects are
IntegerVars and CheckPtrVars, both of whose constructors are known to
be SAFE.  Also, member objects whose construction is not SAFE cannot
be made to work (as far as we can figure out) without exception
handling being provided directly by the language.  We should
remember that we are making this assumption here.

When allocating an object through a SAFE constructor, one can directly
use "new" instead of relying on the various CONSTRUCT macros, as we
know there is neither a garbage collection issue (SAFE routines cannot
trigger collection activity) nor a finalization issue (as the
constructor cannot BLAST).  In fact, XLint should warn exactly about
uses of "new" in calling constructors not declared SAFE.  Perhaps it
should even warn (to point out the unnecessary overhead) of uses of a
CONSTRUCT macro to invoke a SAFE constructor?  (probably not)

Inside the Server, SAFE methods of Shepherds would not have to lock
the server into memory, as nothing the method does may trigger an
attempt to purge Shepherds from memory.  SAFE methods should also not
fault (since faulting may allocate memory), so the SAFE declaration on
Shepherd methods probably occurs below the patriarch in the class
hierarchy (which is sufficient to suppress locking).  Hmm... I'm
suddenly confused about this one (especially the interactions between
SAFE and NO_FAULT).  Michael and Dean: any thoughts?  In any case, my
confusion here should not affect what you need to do, Roland.

Finally, in calculating transitive BLASTs in X4Ref, the process
bottoms out when one reaches routines declared to be SAFE.  Speaking
of which...


			Transitive BLASTs in X4Ref

The first and most important job of our cross referencing tool (X4Ref)
is in gathering together all the BLASTs which may possibly result from
a given call.  It is very tempting to make a closed-world assumption
here (that we have all the source code for a given program), but we
must resist that (because it won't be true).  Instead, we can define
X4Ref recursively.  We define what X4Ref outputs for an individual
module, and then what it outputs for any group of modules given it's
output for the individual modules.  When we don't have source code for
a module, we can hand write a declaration of our understanding of the
blasting behavior of that module, or leave it open.

The blast section of the output for X4Ref should be a file each line
of which is of the form:

<[member] function declaration> MAY_BLAST( <list of blast specs> )

For example, given the declarations above and a cxx file with:

void Foo::zip ()
{
    ...
        BLAST(INVALID_SHNERGLE);
    ...
    CONSTRUCT(....);
    ...
    SPTR(Fnog) f;
    ...
    f->zap();
    ...
}

X4Ref on this module may output:

void Foo::zip() MAY_BLAST(INVALID_SHNERGLE, OUT_OF_ROOM, BLASTS_OF(Fnog::zap()));
void Bar::zip() MAY_BLAST();
void Baz::zip() MAY_BLAST();


The "BLASTS_OF" construct is how X4Ref would handle BLASTs which may
be caused by modules outside its current view.  Unfortunately, I lied
above.  Since X4Ref has no way of knowing that there are not other
subclasses of Foo lurking in other modules, it cannot really be
confident that the above is all the BLASTs which the Foo::zip()
message may cause.  Therefore, we introduce the new construct
BLASTS_UNDER.  The above output would actually be:

void Foo::zip() MAY_BLAST(INVALID_SHNERGLE, OUT_OF_ROOM, \
	BLASTS_OF(Fnog::zap()), BLASTS_UNDER(Foo::zip()));
void Bar::zip() MAY_BLAST();
void Baz::zip() MAY_BLAST();

Anything which calls Foo::zip() in an unprotected way would have the
above MAY_BLASTS unioned into its own.  This problem doesn't arise for
Bar::zip() or Baz::zip() because they are declared SAFE.

When doing an X4Ref on a group of modules (probably all the modules in
one directory), one first does an X4Ref on each individual module
accumulating output such as the above.  (The single module analyzer
should probably be a different tool than the group analyzer, but I
can't think of another name :-).)  Then the group analyzer reads in
all these outputs and resolves BLASTS_OF and BLASTS_UNDER as far as
possible.  

For example, if it sees in another file a MAY_BLAST list for
Fnog::zap(), it'll replace all occurrences of BLASTS_OF(Fnog::zap())
with that list.  Such replacement should continue until there is none
left to do (of course, any algorithm with the equivalent effect is
fine).  In order to do this job, the group analyzer also needs from
the module analyzer what the class inheritance hierarchy is.

In order to prevent an unreasonable explosion of BLASTS_UNDER in the
output, we need information about who may subclass a class.  If in
analyzing a group we know we have seen all possible subclasses of Foo,
then we can remove any BLASTS_UNDER(Foo::<anything>) that remain after
the above trasitive propogation process.  I think this will be an
important wrinkle, but is modularly separable from the rest of X4Ref's
job, and is complicated.  Therefore we should postpone this piece
until we've made progress on the rest of the above.

What do y'all think?