In a Lisp dialect, I've implemented ANSI-CL-like support for printing objects such that their circular and shared structure is encoded. This is enabled by the special variable *print-circle*. Similarly to ANSI-CL, I have it working when it traverses objects that have custom print methods. But there are tricky corner cases.
For reference, let's make this diagram. Object X is the thing being printed, and the pyramid underneath it represents the dependent tree of constituent objects: nested lists, and whatever. Object O is a constituent which is an OOP object with a custom print method. When this is invoked, it can print various objects such as objects R and NR. R is reachable through one or more of the slots of object O. Object NR is not reachable that way: the print method pulls it from a global variable or whatever:
X
|
/ \
/ \
/ \
/ \
/ \
<_________O_>
|
/ print
,-' `---.
| |
R NR
| |
/ \ / \
<___> <___>
Now I developed an algorithm which works in two passes. When the printer is called out of the blue to print X (not a recursive call) and circle printing is enabled, it creates a new circle printing context which contains a hash table for cycle detection. Before doing anything else, the function walks the entire graph rooted at X, which reaches O and recurses into R. It then knows all the duplicate objects and cycles, and can proceed to walk the structure and generate the circular notation. It has no knowledge of NR. However, when object O's print method is called, and recurses into the printer to print the object NR, the printer will supplement the hash table by walking the object NR at that point. Everything is cool if NR is self-contained: it can have internal cycles and shared substructure. What we ensure is that the label numbering for the objects occurring in NR doesn't conflict. If X and R use labels 1 through 21, then any labels under NR start at 22.
The troublesome case is this one:
X
|
/ \
/ Y < ----------.
/ \ |
/ \ |
/ \ |
<_________O_> |
| |
/ print |
,-' `---. |
| | |
R NR |
| | |
/ \ / \ |
<___> < >--'
Suppose NR contains a backpointer into the previously traversed structure, either X or R, to some object Y. The algorithm will break down; if that referenced object Y does not appear two or more times in the originally traversed structure, then it was not noted by the algorithm as requiring the special label def/ref notation. It cannot be correctly rendered as a #<n># reference. (If Y did appear two or more times prior to processing NR, then the occurrence of it encountered via NR is just another occurrence that will be rendered correctly. For instance if Y is represented as label 17, it will turn into #17#.) If Y appeared once, though, we can no longer go back and patch the #17= label definition in front of it in the output that we already printed; by the time we call the print method which recurses into NR, prior structure has already been printed.
Good sub-case of bad case:
X
|
/ \ rendered as #17=Y
/ Y < ----------.
/ \ |
/ \ |
/ \ |
<_________O_> |
| |
/ print |
,-' `---. |
| | |
R NR |
| | |
/ \ / \ |
<_Y_> <__Y>---'
Rendered as #17# Also rendered as #17#: lucky!
If the second occurrence of Y under R is missing, then the top Y is just rendered as itself without the #17= label. When printing NR, we therefore cannot render Y as #17#; that would be a dangling label ref. We might render Y as a new object, say number 256: #256=(...) which might recurse into NR again, where the second printing of Y becomes #256#. Or we could recognize the situation and throw an exception: a print method pitched us a curve ball unsupported by *print-circle*.
The question is: is it a requirement in ANSI Common Lisp to handle that case? Can print methods procure absolutely any existing object from the image, pass it to the printer recursively, and must it be handled properly, no matter that it is unrelated to the object O and not reachable through that object's slots?
