Ephemerons solve the key-in-value problem for weak key/value pairs. It
seems that it's not possible to solve that problem with weak pointers or
finalizers. Basically we want a weak key/value pair that implements the
rule:
The value is reachable, if the key is reachable.
The key-in-value problem occurs if all paths to the key go through the
value. In this situation, the key is considered reachable only if the
value is "externally reachable", i.e. the value is reachable through a
path other than through the weak pair.
Such weak pairs seem to need an extra phase in the GC algorithm. See
[1] for some variants of the algorithm.
https://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html
* mps/code/mpmst.h (SegStruct): Add fields propagationNeeded,
marksChanged, and propagationFinished.
* mps/code/mpmtypes.h (RANK_LIST): Add EPHEMERON rank.
* mps/code/mps.s (mps_rank_ephemeron): New prototype.
* mps/code/mpscawl.h (mps_class_aeph, mps_fix_weak_pair)
(mps_fix_weak_or_pair, mps_fix_weak_and_pair): New prototypes.
* mps/code/mpsi.c (mps_rank_ephemeron): New function.
* mps/code/poolawl.c (AEPHSegStruct, AEPHPoolStruct): New. The
implementation the ephemeron pool.
* mps/code/seg.c (segAbsInit): Initialize propagationNeeded,
marksChanged, and propagationFinished.
* mps/code/trace.c (traceBandRetreat, tracePropagateToLowerRanks)
(moveSegToEndOfGreyRing): New helpers.
(TraceRankForAccess): Handle the RankEPHEMERON.
(traceFindGrey, traceScanSegRes): Add special handling for ephemeron
segments.
* mps/test/function/eph1.c: New test file.
* mps/test/function/eph2.c: New test file.
* mps/test/function/eph3.c: New test file.
* mps/test/function/eph4.c: New test file.
* mps/test/test/testlib/ephfmt.c: New file.
* mps/test/test/testlib/ephfmt.h: New file.
* mps/test/test/testlib/manifest: Add ephfmt.c.
* mps/test/testsets/passing: Include eph{1,2,3,4}.c.
