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)