the polish and tarnish (reverse polish) solution

[Mark S. Miller <vlad!mark>]

Some nits:

   Date: Tue, 17 Jul 90 10:54:27 PDT
   From: xanadu!tribble (Eric Dean Tribble)

   ...

   How do we change the class of an object?  Each convertible object
   class has a special single-argument constructor that takes an object
   from which to convert.  It then constructs itself in place without
   initializing any of the instance variable.  (Actually the constructor
   has two arguemnts: the object to convert from, and a constant like
   TCSJ that designates a become operation).  ...

Actually, the constructor *only* takes the TCSJ-like constant (as well
as TCSJ itself?).  It doesn't need the object it's constructing on top
of, as that is already in the "this" pointer.  The object to convert
from *is* an argument to an overloading of operator new.  Also, for
certain individual platforms we almost definitely will implement a
non-portable more efficient version which just smashes the vtable
directly.  For any cfront-derived platform we already know how to do
this (as Mr. Hill figured out for TombStones).

We also agreed not to call the above operation "become", instead
reserving that for the operation where the previous resident is
destructed and the new resident is constructed (with his own data
state).

   ... Likewise,
   some other points in the algorithms may know that they just stopped
   using an object, and so polish it (the splay routine, for example,
   knows when it's done with an object, and knowns that no other part of
   the algorithm can be using it).  This last trick is relatively unsafe
   in the face of changing code, so we will avoid it unless we really
   need it.

Here is a way which accomplishes the above when it is safe to do so,
but works correctly regardless.  Currently the relevent splay method
(SplitLoaf::actualSplay) has the form:

.. SplitLoaf::actualSplay (....)
{
    .. myIn->splay (...);
    .. myOut->splay (...);
    ... lots of stuff ...
}

If we turn it into:

.. SplitLoaf::actualSplay (....)
{
    .. myIn->splay (...);
    .. myOut->splay (...);
    this->splayBody (...);
}

.. SplitLoaf::splayBody (....)
{
    ... lots of stuff ...
}

and declare SplitLoaf::actualSplay to be safe (which it indeed is),
then should the object in question already be polished, it'll stay
polished during the recursive calls (which will tarnish/polish the
children).  Then during the call to splayBody, it'll automatically
tarnish/polish the object itself, thereby affecting the behavior Dean
outlined above--that only one loaf at a time is tarnished.

However, let's say that the code changes in such a way (and for some
unrelated reason) that there may be an unsafe method higher up on the
stack which has already tarnished the object.  In this case, the
entire execution of actualSplay happens with the object properly
tarnished, and leaves it properly tarnished.  We thereby avoid the
potential unsafety of the mechanism Dean outlined above.

(As this suggestion appears in the form of a reply to Dean, I should
mention that he actually thought up most of it.)

In writing this up, I realize that it is NOT appropriate to
automatically declare as safe all routines which may be safe.  Rather
it is appropriate to have a tool (probably XLint) prevent us from
accidently declaring as safe any routine which isn't.  We may want not
to declare a safe routine safe in order to trade off execution time
(at what granularity do we polish/tarnish) versus storage management
considerations (how many objects are available for purging).

   Finally, we realized that the disk storage stuff I've been building
   probably has enough information to know when it's going to fill up the
   URDI buffers, so we don't need a currently unimplemented feature of
   URDI to handle 'mayCommit' operations that commit a consistent state
   without waiting for it to go to disk.

We instead need a different currently unimplemented URDI feature:
being able to ask if I could dirty N more snarfs without causing a
jackpot.  Fortunately, this is at least as easy (and far more useful)
as the URDI feature it replaces.