3 ms·

Happens a fair bit of time when parsing deeply nested structures (e.g. parsing deeply nested JSON structures) using mutually recursive parsers. I've generally r

Happens a fair bit of time when parsing deeply nested structures (e.g. parsing deeply nested JSON structures) using mutually recursive parsers. I've generally resorted to either trampolining or explicit stacks.

kragen 4y ago
This is usually a case where TCE doesn't help, in my experience, because most of the calls to sub-parsers aren't in tail position. This is especially unpleasant when you get bug reports of mysterious segfaults that turn out to be stack overflows...
- remexre 4y ago
  Yep, a basic security check for any endpoint that accepts JSON: what happens when you hand it 4KiB of '[' characters
robocat 4y ago
> parsing deeply nested JSON structures How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me. It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.
- dataangel 4y ago
  It’s a security/DOS vulnerability if the object depth can be used to trigger stack overflow.
- epidemian 4y ago
  > How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? Not that unlikely i'd say, at lest if the stack size is unreasonably small. For example, on nodejs, JSON.stringify() chokes with a nested array of 10K depth: > N=10_000; JSON.stringify(JSON.parse("[".repeat(N) + "]".repeat(N))) Uncaught RangeError: Maximum call stack size exceeded at JSON.stringify (<anonymous>) Curiously, JSON.parse() is OK with arrays of 10M depth (and probably more). A difference of over 3 orders of magnitude between functions that seem pretty symmetrical at first glance. Imagine that you build some software that lets users nest things —e.g., a circuit designer, a visual programming language, a UI builder, etc— and you wanna save these nested structures as JSON, or process them recursively. Pretty natural fit i'd say. Now, as a user, i'd be pretty upset if my magnum opus of a very complex circuit, or giant visual program, or very busy beast of UI art, starts creashing the program when exceeding a mere 10K elements. My computer has gigabytes of memory! And, presumably, there's a lot still available. But nope, a meager stack can ruin all the fun. I personally think this is a pretty silly limitation to have on software, especially given today's memory sizes.
  - foldr 4y ago
    TCO likely wouldn’t help here, as the parser is probably using non-tail recursion to build the nested arrays. (I haven’t looked at the code, but that’s the natural way to do it with a recursive descent algorithm.)

kragen 4y ago

This is usually a case where TCE doesn't help, in my experience, because most of the calls to sub-parsers aren't in tail position. This is especially unpleasant when you get bug reports of mysterious segfaults that turn out to be stack overflows...

remexre 4y ago
Yep, a basic security check for any endpoint that accepts JSON: what happens when you hand it 4KiB of '[' characters

robocat 4y ago

> parsing deeply nested JSON structures How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me. It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.

dataangel 4y ago
It’s a security/DOS vulnerability if the object depth can be used to trigger stack overflow.
epidemian 4y ago
> How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? Not that unlikely i'd say, at lest if the stack size is unreasonably small. For example, on nodejs, JSON.stringify() chokes with a nested array of 10K depth: > N=10_000; JSON.stringify(JSON.parse("[".repeat(N) + "]".repeat(N))) Uncaught RangeError: Maximum call stack size exceeded at JSON.stringify (<anonymous>) Curiously, JSON.parse() is OK with arrays of 10M depth (and probably more). A difference of over 3 orders of magnitude between functions that seem pretty symmetrical at first glance. Imagine that you build some software that lets users nest things —e.g., a circuit designer, a visual programming language, a UI builder, etc— and you wanna save these nested structures as JSON, or process them recursively. Pretty natural fit i'd say. Now, as a user, i'd be pretty upset if my magnum opus of a very complex circuit, or giant visual program, or very busy beast of UI art, starts creashing the program when exceeding a mere 10K elements. My computer has gigabytes of memory! And, presumably, there's a lot still available. But nope, a meager stack can ruin all the fun. I personally think this is a pretty silly limitation to have on software, especially given today's memory sizes.
- foldr 4y ago
  TCO likely wouldn’t help here, as the parser is probably using non-tail recursion to build the nested arrays. (I haven’t looked at the code, but that’s the natural way to do it with a recursive descent algorithm.)