Stack overflow in `CPCTPlus::collect_repairs()`

[bendrissou]

Hi,

lrpar’s CPCT+ recovery code can crash with a stack overflow when enumerating repair sequences in CPCTPlus::collect_repairs(). The overflow happens in the recursive helper traverse() in cpctplus.rs, which walks the Cactus<RepairMerge<_>> parent chain recursively and also recursively explores merge branches.

With pathological input (example attached), the repair structure can become deep and/or highly branched enough to exhaust the thread stack and abort the process.

Input:
test.php

php.y

php.y.txt

php.l

php.l.txt

Execution output:

# ./php_repair test.php

thread 'main' (28119) has overflowed its stack
fatal runtime error: stack overflow, aborting
Aborted

GDB backtrace output:

Program received signal SIGSEGV, Segmentation fault.
__GI___clock_gettime (clock_id=1, tp=0xfffff5d53010) at ../sysdeps/unix/sysv/linux/clock_gettime.c:38
38      ../sysdeps/unix/sysv/linux/clock_gettime.c: No such file or directory.
(gdb) bt
#0  __GI___clock_gettime (clock_id=1, tp=0xfffff5d53010)
    at ../sysdeps/unix/sysv/linux/clock_gettime.c:38
#1  0x0000aaaac6d9c404 in std::sys::pal::unix::time::Timespec::now ()
    at library/std/src/sys/pal/unix/time.rs:131
#2  0x0000aaaac6cf03a8 in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d531e0) at /home/grmtools/lrpar/src/lib/cpctplus.rs:396
#3  0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53300) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#4  0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53420) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#5  0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53540) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#6  0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53660) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#7  0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53780) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#8  0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d538a0) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#9  0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d539c0) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#10 0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53ae0) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#11 0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53c00) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402
#12 0x0000aaaac6cf05bc in lrpar::cpctplus::CPCTPlus<StorageT,LexerTypesT,ActionT,ParamT>::collect_repairs::traverse (finish_by=..., rm=0xfffff5d53d20) at /home/grmtools/lrpar/src/lib/cpctplus.rs:402

commit: bbb0343

[ratmice]

I quickly looked into whether we could just use the tailcall crate slapping the #[tailcall] attribute and tailcall::call! macro to the traverse function, but it definitely is going to require more persuasion in the sense of actually making the traverse function tail recursive, it also looks like we could no longer use ?.

It definitely seemed like it was going to require more elaborate changes than just slapping the attributes on it before that crate could ensure tail call optimization however.

I'm not sure if it wouldn't be simpler to try and just make an iterative looping version than make the current one tail recursive..

[ltratt]

I'm not sure if it wouldn't be simpler to try and just make an iterative looping version than make the current one tail recursive..

Yes, I think that would be the right solution. From memory, I don't think there's any ordering requirements in that function (those are handled in ranking), so a simple queue-based iterative solution will probably work. I'd very happily accept a PR for this!