Marking objects for graph traversals.

[Dawid Weiss]

Hi there,

I realize the answer is probably "your jvm will core dump", but I
can't resist to ask nonetheless...

There are many problems that process object graphs in which a "accept
each object once" idiom is required. An example in the standard
library would be Arrays#deepToString but virtually any graph-scanning
(including garbage collectors) will face the same problem of detecting
whether a node has been traversed or not.

Typically one just uses a "Set<Object> visited" and shoves references
in there as they are traversed but this requires a lot of memory for
larger graphs.

I admit I intellectually exercised the idea of fiddling with oops and
somehow "tainting" object references in-place with the possibility of
reverting them after the traversal... Would this be possible at all
(given the possibility of a safepoint and gc at any time)? Yes, I
realize it's beyond dirty -- I am looking for theoretical options
rather than something that could be run on production machines.

Or maybe there are other ways of doing this?

Dawid