Bug 3821 – writeln doesn't detect recursive data structures yet

import std.stdio, std.boxer; void main() { auto a = new Box[1]; a[0] = box(a); writeln(a); // Error: Stack Overflow } Produces a stack overflow, the writeln isn't able to detect loops yet. In Python the print is able to detect loops: >>> l = [1, 2] >>> l[1] = l >>> print l [1, [...]]

Got a newer example maybe? std.boxer is long gone.

Simple example: import std.stdio; import std.string; class A { B b; override string toString() { return format("A(%s)", b.toString()); } } class B { A a; override string toString() { return format("B(%s)", a.toString()); } } void main() { auto a = new A; auto b = new B; a.b = b; b.a = a; writeln(a); } But why is this set for Druntime and to Sean Kelly? This is a Phobos issue imo.

(In reply to comment #2) > But why is this set for Druntime and to Sean Kelly? This is a Phobos issue imo. Maybe I was ignorant. Fixed.

Andrej: your updated example is invalid--two functions calling each other should result in a stack overflow.

(In reply to Andrej Mitrovic from comment #1) > Got a newer example maybe? std.boxer is long gone. Is this good enough? void main() { import std.stdio, std.variant; auto a = new Variant[1]; a[0] = a; writeln(a); // Error: Stack Overflow }

This looks like a Variant toString bug rather than a writeln bug. A phobos issue never-the-less.

Meanwhile I get a segmentation fault. Doesn't make it better though...

(In reply to safety0ff.bugz from comment #6) > This looks like a Variant toString bug rather than a writeln bug. I don't think so, because it's not limited to Variant. Every recursive data structure cannot be printed. See the example of Andrej. (Which IMHO isn't invalid.) The problem is a recursive call to formatValue in std.format, which might have intemediate steps that are outside of std.format, but lead back there. To fix this, it would be necessary to keep somehow a (static) record, which items (*) where processed by formatValue and just return "*** recursion ***" or something like this, when one is to be printed again. (*) Only items need to be considered, that could contain a recursion.

This is generalized detection of infinite recursion. In order for format to detect this, it would have to instrument the entire set of objects being printed, and that is a lot of overhead for detecting something that already throws a major error (Stack overflow). Not only that, but it depends on it being recursive on format, and not some other mechanism to display items. Note that a better "solution" is to update everything to calling the delegate version of toString, which should actually output something (in the case of writeln), before segfaulting. This gives you a hint of your error. i.e.: struct List1 { int x; List1 *next; void toString(void delegate(const(char)[]) dg) const { import std.format; formattedWrite(dg, "%s ->", x); if(next is null) dg("null"); else next.toString(dg); } } struct List2 { int x; List2 *next; string toString() const { import std.conv; string result = x.to!string; if(next is null) return result ~ " -> null"; else return result ~ " -> " ~ next.toString; } } List1 when self-referencing will print e.g. 5 -> 5 -> 5 ... forever until it segfaults. List2 just segfaults because it never finishes building the string. Note how in List2 I show that this does not recurse on format at all, so such a case still wouldn't be detectable -- all the recursion is in toString. (In reply to berni44 from comment #7) > Meanwhile I get a segmentation fault. Doesn't make it better though... This is a stack overflow. Segfault happens in the case of stack overflow on many platforms. (In reply to bearophile_hugs from comment #0) > In Python the print is able to detect loops: Python is a managed language, and has the possibility of doing whatever it wants to the data types (i.e. it might be able to reserve a bit of data on each object for this purpose), D cannot do this.

(In reply to Steven Schveighoffer from comment #9) > (In reply to bearophile_hugs from comment #0) > > In Python the print is able to detect loops: > > Python is a managed language, and has the possibility of doing whatever it > wants to the data types (i.e. it might be able to reserve a bit of data on > each object for this purpose), D cannot do this. IMHO it would be possible with D too (just instead of the reserve bit on each object an additional list of allready printed items), but purity is blocking this.

It's possible, but at a huge cost. Just to see if you are printing infinitely recursively, something that you may not expect to actually work. And also impossible to know the state of the object, it could use things outside the object to print (i.e. even though it's printing the same object, maybe it terminates anyway). Just don't print something that recurses infinitely. Note that there's nothing stopping a type which MIGHT print recursively from figuring this out in its toString function. e.g.: struct List1 { int x; List1 *next; private bool printing = false; void toString(void delegate(const(char)[]) dg) const { if(printing) { dg("..."); return; } printing = true; scope(exit) printing = false; import std.format; formattedWrite(dg, "%s ->", x); if(next is null) dg("null"); else next.toString(dg); } } Solving it in format is the wrong answer, IMO.