google / google/go-jsonnet

Array slicing isn't properly tail recursive

Open
#831 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
1.8k
Forks
263
PR merge metrics
No merged PRs in 30d

Description

When I run [this Jsonnet program](https://github.com/flwyd/adventofcode/blob/main/2025/day10/day10.jsonnet) on the following input with a stack size lower than about 3000, I get a stack overflow error which consists mostly of lines like `:231:22-42 thunk from >>`. The [build function in std](https://github.com/google/jsonnet/blob/f45e01d632b29e4c0757ec7ba188ce759298e6d3/stdlib/std.jsonnet#L223) uses `tailstrict` for recursive calls, but it doesn't seem to be working in this case. Maybe the `+` operation in the arguments is causing the issue? `tailstrict` is working in general; when run with a stack size of `3000` this program completes successfully, but if the `tailstrict` calls within the program are removed, it overflows even that stack size, with lots of `bifurcate` instances in the stack.

The `bifurcate` function recursively passes a stack of work to perform as the last argument to the function. `local cur = stack[0]` examines the top item on the stack; if it doesn't need to recurse further then it updates a cache and recurses with `stack[1:]`. If `cur` needs additional work, its sub-problems are put into an array and it recurses with `next + stack`. This is a Lisp `cons` style approach, but Jsonnet arrays aren't single-linked lists, so I'm not surprised that it's inefficient, just that the intended tail call elimination isn't happening.

Input (/tmp/day10/line7.txt), which is one challenging line of input from https://adventofcode.com/2025/day/10:
```
[.#.....##.] (0,3,6,9) (1,2,4,6,7,8,9) (0,5,9) (0,1,2,4,7,8) (0,6,7,8,9) (3,4,5,6,7,8) (0,3,5,7) (2,3,4,6,7) (2,3,4,5,6,7,8) (1,2,6,9) (2,7,8) (0) (0,2,3,4,5,6,7,9) {71,46,95,181,172,148,199,205,151,71}
```

Run: `jsonnet -t 128 -s 1000 -S ./runner.jsonnet --tla-code-file 'solve=day10/day10.jsonnet' --tla-code 'files=[{name:'\''/tmp/day10/line7.txt'\'', content:importstr '\''/tmp/day10/line7.txt'\'', },]'`

Output:
```
RUNTIME ERROR: max stack frames exceeded.
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
...
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
:231:22-42 thunk from >>
day10/day10.jsonnet:83:17-25 thunk from >
day10/day10.jsonnet:84:32-35
day10/day10.jsonnet:66:80-82 thunk from >
day10/day10.jsonnet:66:38-83
day10/day10.jsonnet:66:25-84 function
day10/day10.jsonnet:84:20-43 thunk from >
day10/day10.jsonnet:85:43-49 thunk from from >>
:1545:24-25 thunk from >
:1545:5-33 function
day10/day10.jsonnet:85:21-50 thunk from >
day10/day10.jsonnet:90:16-20 thunk from >
day10/day10.jsonnet:(86:20)-(90:77)
day10/day10.jsonnet:91:54-60 thunk from >
day10/day10.jsonnet:91:16-61
:1642:24-27 thunk from >
:32:25-26 thunk from >
:32:16-27 function
:1642:12-28 function
day10/day10.jsonnet:91:8-62 function
day10/day10.jsonnet:95:7-54 function
day10/day10.jsonnet:102:3-101 function
day10/day10.jsonnet:109:12-33 object
day10/day10.jsonnet:114:15-22 thunk from >>
day10/day10.jsonnet:29:47-48 function
day10/day10.jsonnet:29:18-57 function
day10/day10.jsonnet:114:10-43 object
runner.jsonnet:56:54-71 thunk from >
runner.jsonnet:57:25-51 object
runner.jsonnet:61:38-73 function
:259:50-62 function

runner.jsonnet:61:3-82 function
Top-level function call
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.