org.erights.e.elib.tables
Class Equalizer

java.lang.Object
  |
  +--org.erights.e.elib.tables.Equalizer

public final class Equalizer
extends Object

Untamed: Implements E's sameness semantics, which should be used only through the Ref class.

The static methods are the recursive cycle-breaking sameness algorithm. An Equalizer instance is a hypothetical comparison pair as used by the algorithm. Equalizer instances are honorary Selfless objects, so that their .equals() and .hashCode() will be used to compare them.

Author:
Mark S. Miller
See Also:
org.erights.e.elib.ref.Ref

Field Summary
private static int HASH_DEPTH
          A random guess at a good value.
private static int INITIAL_SIZE
           
private  Object[] myLefts
           
private  int myMaxSofar
           
private  Object[] myRights
           
private static String[][] Simplifications
          All instances of the left hand (key) types simplify (for purposes of sameness comparison) to instances of the right hand (value) types.
private static SynchQueue TheCachedEqualizers
           
private static Hashtable TheSimplifications
          Maps fq class names to the fqn of the classes they simplify to.
 
Constructor Summary
private Equalizer()
           
 
Method Summary
private  void clear()
           
private  boolean findSofar(Object left, Object right, int sofar)
           
static boolean isSameEver(Object left, Object right)
          Enabled: The implementation of Ref.isSameEver(left, right)
static boolean isSameYet(Object left, Object right)
          Enabled:
static boolean isSettled(Object obj)
          Enabled: The implementation of 'Ref isSettled(ref)'
static Equalizer make()
          Enabled:
 Boolean optSame(Object left, Object right)
          Enabled: The implementation of Ref.same(left, right)
private  Boolean optSame(Object left, Object right, int sofar)
           
static Class OptSimplification(Class clazz)
          Enabled: Map a class to the class it simplifies to, or null if none
private  int pushSofar(Object left, Object right, int sofar)
           
 boolean sameEver(Object left, Object right)
          Enabled:
private static boolean samenessFringe(Object original, IdentityMap optFringe)
          Parallels the recursive logic of same/3, except that we make things more efficient by leaving objects in sofar.
private static boolean samenessFringe(Object original, IdentityMap sofar, IdentityMap optFringe)
           
(package private) static int samenessHash(Object obj)
          Two settled objects that are the same() must have the same samenessHash().
private static int samenessHash(Object obj, int hashDepth, IdentityMap optFringe)
          Parallels the recursive logic of same/3, except that we make things more efficient by leaving objects in sofar.
 boolean sameYet(Object left, Object right)
          Enabled:
(package private) static int sameYetHash(Object obj, IdentityMap fringe)
          With this method, unsettled objects may be hashed; but their hash only lasts until they settle further.
private static Object simplify(Object ref)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

HASH_DEPTH

private static final int HASH_DEPTH
A random guess at a good value.


Simplifications

private static final String[][] Simplifications
All instances of the left hand (key) types simplify (for purposes of sameness comparison) to instances of the right hand (value) types.

This is much like ScriptMaker.Promotions, but with some differences.

XXX Should ConstLists simplify into arrays, rather than just describing themselves (using Selfless.getSpreadUncall()) using arrays? The corrent code probably doesn't judge an array and a corresponding ConstList as the same. They probably should be judged to be the same.


TheSimplifications

private static Hashtable TheSimplifications
Maps fq class names to the fqn of the classes they simplify to.

TheSimplifications is initialized lazily in order to avoid possible circular static initialization dependencies. Uses legacy Hashtable rather than EMap in order to avoid a circular dependency, and to get thread safety for mutable static cache state.


INITIAL_SIZE

private static final int INITIAL_SIZE

TheCachedEqualizers

private static final SynchQueue TheCachedEqualizers

myLefts

private Object[] myLefts

myRights

private Object[] myRights

myMaxSofar

private int myMaxSofar
Constructor Detail

Equalizer

private Equalizer()
Method Detail

OptSimplification

public static Class OptSimplification(Class clazz)
Enabled: Map a class to the class it simplifies to, or null if none


make

public static Equalizer make()
Enabled:


simplify

private static Object simplify(Object ref)

isSameEver

public static boolean isSameEver(Object left,
                                 Object right)
                          throws NotSettledException
Enabled: The implementation of Ref.isSameEver(left, right)

NotSettledException
See Also:
org.erights.e.elib.ref.Ref#isSameEver

isSameYet

public static boolean isSameYet(Object left,
                                Object right)
Enabled:


isSettled

public static boolean isSettled(Object obj)
Enabled: The implementation of 'Ref isSettled(ref)'

See Also:
org.erights.e.elib.ref.Ref#isSettled(Object)

samenessHash

static int samenessHash(Object obj)
Two settled objects that are the same() must have the same samenessHash().

Only settled objects may be hashed with this method.


sameYetHash

static int sameYetHash(Object obj,
                       IdentityMap fringe)
With this method, unsettled objects may be hashed; but their hash only lasts until they settle further.

This is useless for many purposes, but is good enough to build a TraversalKey wrapper, which can be used as a key in tables in order to finitely walk cyclic unsettled structures without a linear search.


samenessHash

private static int samenessHash(Object obj,
                                int hashDepth,
                                IdentityMap optFringe)
                         throws NotSettledException
Parallels the recursive logic of same/3, except that we make things more efficient by leaving objects in sofar.

In all cases, if obj is settled, then we return a hashCode for it such that x == y implies hash(x) == hash(y). This must be true even in the presence of cycles, and even if one is wound more tightly than the other. In this case, the optFringe argument is ignored.

If optFringe is null, then we require that obj is settled: If obj isn't settled, we throw a NotSettledException.

If optFringe isn't null and obj is not settled, then the Java == identity of the promises at the current fringe of obj are placed in optFringe, and a hash is returned taking this current fringe into account. Should any of the promises at the fringe of x later be forwarded, even to another promise, a sameHash of obj then should return a different hash, and must return a different fringe. Otherwise, TraversalKey cannot satisfy the contract for stable settled sameness.

NotSettledException

samenessFringe

private static boolean samenessFringe(Object original,
                                      IdentityMap optFringe)
                               throws NotSettledException
Parallels the recursive logic of same/3, except that we make things more efficient by leaving objects in sofar.

In all cases, if original is settled, then we return true, even in the presence of cycles. In this case, the optFringe argument is ignored.

In all cases, if original is unsettled, then we return false.

If optFringe is null and original isn't settled, then we should return false as soon as possible -- when we encounter the first unresolved promise.

If optFringe isn't null and original is not settled, then the Java == identity of the promises at the current fringe of original are placed in optFringe. Should any of the promises at the fringe of later be forwarded, even to another promise, a samenessFringe of original afterwards must accumulate a different fringe. Otherwise, TraversalKey cannot satisfy the contract for stable settled sameness.

Parameters:
original -
optFringe -
Returns:
Throws:
NotSettledException

samenessFringe

private static boolean samenessFringe(Object original,
                                      IdentityMap sofar,
                                      IdentityMap optFringe)
                               throws NotSettledException
Parameters:
original -
sofar -
optFringe -
Returns:
Throws:
NotSettledException

clear

private void clear()

findSofar

private boolean findSofar(Object left,
                          Object right,
                          int sofar)
Parameters:
left -
right -
sofar -
Returns:

pushSofar

private int pushSofar(Object left,
                      Object right,
                      int sofar)
Parameters:
left -
right -
sofar -
Returns:

sameEver

public boolean sameEver(Object left,
                        Object right)
                 throws NotSettledException
Enabled:

NotSettledException

sameYet

public boolean sameYet(Object left,
                       Object right)
Enabled:

Parameters:
left -
right -
Returns:

optSame

public Boolean optSame(Object left,
                       Object right)
Enabled: The implementation of Ref.same(left, right)

See Also:
org.erights.e.elib.ref.Ref#isSameEver

optSame

private Boolean optSame(Object left,
                        Object right,
                        int sofar)


comments?