Fix unbounded stack usage when dropping long list values

[BobAdamsEE]

Reading large S-expression files appears to create a stack overflow when using from_reader() or from_reader_custome()

The code below will overflow the stack when pointing to a large (~2MB) file of S-Expression data (ECAD circuit board format, Kicad PCB Board File Format). The code would overflow at the commented out parsed_file assignment.

fn parse_kicad_file(file_path: &PathBuf) /*-> Value*/{
    let display = file_path.display();
    let opened_file = match File::open(&file_path) {
        Err(why) => panic!("couldn't open {}: {}",display,why),
        Ok(file) => file,
    };

    let reader = BufReader::new(opened_file);
    let parse_options = lexpr::parse::Options::elisp();
    //let parsed_file = lexpr::from_reader_custom(reader,parse_options).expect("This doesn't seem like a valid s-expression");
    //parsed_file
}

An example of this file type can be found on projects like the BitAxe Ultra - https://github.com/skot/bitaxe/blob/master/bitaxeUltra.kicad_pcb

I have not figured out a workaround but I'm a rust novice!

2024-06-04 Update: It does not seem to matter if I pass in a BufReader or a File. It also doesn't matter if I try to wrap the return in Box::new()

[rotty]

I'm sorry, but I cannot reproduce the issue:

1) The input file you provided is not parseable by lexpr (tried with the latest release, 0.2.7):

thread 'main' panicked at src/bin/parse-sexp.rs:13:10:
This doesn't seem like a valid s-expression: Error("invalid number", line: 2109, column: 16)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

This is due to not supporting symbols that start with a digit; as this feature has been requested before to be able to be read Kicad-style S-expressions (see #64), I've now, as this has come up again in this issue, changed my mind about including this feature, and am working on providing it.

2) When tested against a patched version that includes support for parsing the "naked" UUIDs contained in the kicad data file, I can parse and print that file successfully (using the wip/transpose git branch, currently commit 0d58543):

$ cargo run --bin lexpr-transpose -- -f kicad -t r6rs ~/src/_readonly/bitaxe/bitaxeUltra.kicad_sch | wc -c
70807

What version of lexpr do you use (released crate version, or git commit) to run into this stack overflow?

Edit: Given the file size (~2MB) you mentioned, I'm guessing you did not try with the mentioned file, but another, bigger one, with the same general format. It would be very helpful if you could provide the actual data file you encounter the stack overflow with. Right now, the parser is not limiting recursion depth, which makes this sort of problem possible. However, if we had a (configurable) recursion depth limit, it would still fail, either with a "limit exhausted" runtime error, or (again) with a stack overflow, should the limit be configured beyond what can be accommodated by the processes' stack size. I agree that not limiting recursion depth is bug (or missing feature) in the current implementation of the parser, but I still wonder what real-world data would cause this, as the stack overflow should only happen given extremely deep nesting. If it's not nesting, but just mere file size causing this, it indeed would be a serious bug, hence the need for a reproducing input file, so this can be triaged.

[BobAdamsEE]

What version of lexpr do you use (released crate version, or git commit) to run into this stack overflow?

I tested using the latest release, 0.2.7 configured in my toml file

You're right, I gave you the wrong file. I forked that file and made some changes in my repo, and they included an upgrade to KiCAD 8. I haven't looked under the hood for the differences, but perhaps they fixed the symbols issue, or my circuit design just incidentally changed the symbols to items that are considered valid.

https://github.com/BobAdamsEE/bitaxePD/blob/master/bitaxeUltra.kicad_pcb

This is the file that I was getting the stack overflow on, but there are some caveats I discovered later:

• Stack overflow only appears with Windows in the main thread, Linux is OK.
• On Windows, it only occurs on the debug release. If I do cargo build --release it is OK, presumably from additional compiler optimizations
• Feedback I received from a more seasoned programmer than myself was:

  I looked into why the stack overflow occurs, and it turns-out it's only due to the dropping of lexpr::Value​ which, when it's an s- expr list (a deep chain of Conss), does much function-call recursion, and when a list is longer there is a lot of this drop recursion and this blows the stack. Currently, lexpr::Value is being dropped by the default compiler-inserted implicit drop handling, which does this recursion.

[rotty]

dropping of lexpr::Value when it's an s-expr list

Ah, indeed -- I didn't think of this, but this is indeed a bug more severe than the lack of recursion limits in the parser. I've now adjusted the issue title accordingly.

[DerickEddington]

• Feedback I received

That was from me. Bob had emailed me about this stack overflow.

• Stack overflow only appears with Windows in the main thread, Linux is OK.

That was because Windows has a smaller default stack size (1 MB, it seemed) than Linux (8 MB, for me), for the main thread. Linux with a 1 MB stack (ulimit -S -s $((1 * 2**10))) also encountered the same stack overflow with the same ~2MB input file.

• On Windows, it only occurs on the debug release. If I do cargo build --release it is OK, presumably from additional compiler optimizations

That's because debug builds often use more stack space per function call and do more function calls, versus optimized release builds that use less stack space to do the same thing (more efficient usages per call, and less calls due to inlining).