Infinite loop when pretty-printing nesting-is-fun test case

[djrieger]

When running mj++ without --print-ast, the compiler returns with exit code 0. When run with --print-ast, it never terminates. Debugging revealed that IfStatement.toString() is calling Block.toString() which again calls IfStatement.toString() and this never terminates.

My attempts at debugging showed that both functions are apparently called 10000 times, which would match the 10000 if's in the test case. This happens quite fast, but then the program is stuck.

Here is an excerpt from my backtrace:

Program received signal SIGINT, Interrupt.
0x00007fff8ea05442 in _platform_memmove$VARIANT$Nehalem () from /usr/lib/system/libsystem_platform.dylib
(gdb) bt
#0  0x00007fff8ea05442 in _platform_memmove$VARIANT$Nehalem () from /usr/lib/system/libsystem_platform.dylib
#1  0x00007fff93bebe6a in std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::__grow_by_and_replace(unsigned long, unsigned long, unsigned long, unsigned long, unsigned long, unsigned long, char const*)
    () from /usr/lib/libc++.1.dylib
#2  0x00007fff93bebd23 in std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::append(char const*, unsigned long) () from /usr/lib/libc++.1.dylib
#3  0x000000010000315c in ast::Block::toString (this=<optimized out>, indent=<optimized out>)
    at /Library/Developer/CommandLineTools/usr/bin/../include/c++/v1/string:1683
#4  0x0000000100004778 in ast::IfStatement::toString (this=0xacb401, indent=117440512) at ast/IfStatement.cpp:23
#5  0x0000000100003081 in ast::Block::toString (this=<optimized out>, indent=11318273) at ast/Block.cpp:19
#6  0x0000000100004778 in ast::IfStatement::toString (this=0xacb401, indent=117440512) at ast/IfStatement.cpp:23
#7  0x0000000100003081 in ast::Block::toString (this=<optimized out>, indent=11318273) at ast/Block.cpp:19
#8  0x0000000100004778 in ast::IfStatement::toString (this=0xacb401, indent=117440512) at ast/IfStatement.cpp:23
#9  0x0000000100003081 in ast::Block::toString (this=<optimized out>, indent=11318273) at ast/Block.cpp:19

Trying again yields these indent values:

#4  0x0000000100004778 in ast::IfStatement::toString (this=0x638e08, indent=343498752) at ast/IfStatement.cpp:23
#5  0x0000000100003081 in ast::Block::toString (this=<optimized out>, indent=6524424) at ast/Block.cpp:19
#6  0x0000000100004778 in ast::IfStatement::toString (this=0x638e08, indent=343498752) at ast/IfStatement.cpp:23
#7  0x0000000100003081 in ast::Block::toString (this=<optimized out>, indent=6524424) at ast/Block.cpp:19

[ratefuchs]

Cannot reproduce. Terminates at my computer (commit 08abcd3). Has a long runtime, though (something like 10 minutes? Didn't time it). The program currently seems to have quadratic runtime in the nesting depth. Created issue #6 (feature request for more efficient ast printer) as result.

[djrieger]

Alright, didn't leave it running that long. Trying again and not interrupting it prematurely resulted in what looks like correct output, after 18 minutes of running.

[BigPeet]

Wofür braucht das denn 18 Minuten? Am 15.11.2014 14:46 schrieb "David Rieger" notifications@github.com:

Alright, didn't leave it running that long. Trying again and not interrupting it prematurely resulted in what looks like correct output, after 18 minutes of running.

— Reply to this email directly or view it on GitHub https://github.com/djrieger/mjplusplus/issues/5#issuecomment-63172851.

[djrieger]

No idea.

[ratefuchs]

See #6. Generating indentation string every time. The fill-constructor of string seems to be linear in the number of chars. This summed up for all levels is quadratic... The result file of the printing contains 96 MB...

[djrieger]

6 reduced those 18 minutes to 1 minute on my machine (with console output). Without console output I have 9 seconds instead of 1 minute.