jq: del() through a slice piped into repeated .. deletes the wrong element

[newhoggy]

Severity: Low (found by a differential sweep while fixing #2909; pre-existing and unrelated to it)

Summary

del() over a path that pipes a slice into .. twice deletes more, or different, elements
than jq. Present on main and on the #2909 merge-base alike, and reproduces with no ?
anywhere, which is what rules out #2909's ?-group scope as the cause.

Repro

Captured live against /usr/bin/jq 1.7.1:

$ echo '[1,2,3]' | jq -c 'del((.[0:1] | .. | ..)?)'
[2,3]
$ echo '[1,2,3]' | succinctly jq -c 'del((.[0:1] | .. | ..)?)'
[3]

$ echo '[1,2,3]' | jq -c 'del(.[0:1] | .. | ..)'     # no `?` at all
[2,3]
$ echo '[1,2,3]' | succinctly jq -c 'del(.[0:1] | .. | ..)'
[3]

More rows, same shape:

input	jq 1.7.1	succinctly
[true,false]	[false]	[]
[[1,2],[3]]	[[3]]	[]
[{"a":1},5,{"a":3}]	[5,{"a":3}]	[{"a":3}]

A single .. agrees; it takes two.

Root cause

Not investigated. The shape is a slice component followed by two recursive descents, which
produces overlapping and nested resolved paths — so the likely area is how the deletion trie
interns paths that are prefixes of one another after a slice step, rather than the descent
itself.

Why this is separate from #2909

#2909 is about a ? over a group being distributed onto the group's components instead of
scoping the whole group. This reproduces without a ?, and diverges identically on the
merge-base — the #2909 sweep (2,400 combinations) found these 8 rows and no others, and they
were unchanged by that fix.

Suggested fix direction

Start from del(.[0:1] | ..) (agrees) versus del(.[0:1] | .. | ..) (diverges) and diff the
resolved path lists the two produce, before looking at the trie. Capture the oracle for the
one-.., two-.. and three-.. forms over array, object and scalar-element inputs first —
the table will say whether this is about path count, path order, or prefix interning.

Refs #2909.

[newhoggy]

Triage plan (2026-09-17)

Premise check (main @ b509a8019, oracle /usr/bin/jq 1.7.1, yq v4.53.3)

The premise is confirmed and wider than filed. Every row below was run through both binaries (succinctly jq -c, release build of that commit).

Two corrections to the issue text:

• "A single .. agrees" is false on current main. del(.[0:1] | ..) also gives [3].
• Path count, path order and prefix interning are not the cause. succinctly's [path(.[0:1] | .. | ..)] is byte-identical to jq's: [[{"start":0,"end":1}],[{"start":0,"end":1},0],[{"start":0,"end":1},0]]. The trie deduplicates the repeated path correctly. The bug is in how the trie is applied, and it reproduces without .. at all.

A. A path that deletes a key outright should subsume longer paths under it. The trie still walks into them.

#	Doc	Filter	jq	succinctly (main)
A1	[1,2,3]	del(.[0:1] | ..)	[2,3]	[3]
A2	[1,2,3]	del(.[0:1] | .. | ..)	[2,3]	[3]
A3	[true,false]	del(.[0:1] | .. | ..)	[false]	[]
A4	[[1,2],[3]]	del(.[0:1] | .. | ..)	[[3]]	[]
A5	{"a":[1,2,3]}	del(.a[0:1] | .. | ..)	{"a":[2,3]}	{"a":[3]}
A6	[1,2,3]	del(.[0:1], .[0:1][0])	[2,3]	[3]
A7	[1,2,3]	del(.[0:1][0], .[0:1])	[2,3]	[3]
A8	[1,2,3,4]	del(.[0:2], .[0:2][0])	[3,4]	[4]
A9	[[1,2,3]]	del(.[0][0:1], .[0][0:1][0])	[[2,3]]	[[3]]
A10	["ab",2]	del(.[0:1], .[0:1][0][0:1])	[2]	error Cannot delete fields from string
A11	{"a":"ab"}	del(.a, .a[0:1])	{}	error Cannot delete fields from string
A12	["ab"]	del(.[0], .[0][0:1])	[]	error Cannot delete fields from string
A13	{"a":{"b":"ab"}}	del(.a, .a.b[0:1])	{}	error Cannot delete fields from string

A10–A13 show that this is not only about slices. Under a whole-key delete through a field or an index, succinctly raises an error that jq never raises.

B. Array continuations run in first-seen order. jq runs them in sorted key order. Only a slice continuation is observable, because deleting inside a slice splices a shorter sub-array back and shifts every later position.

#	Doc	Filter	jq	succinctly (main)
B1	[1,2,3,4,5]	del(.[3:5][0], .[0:2][0])	[2,3,4]	[2,3,5]
B2	[1,2,3,4,5]	del(.[1:3][0], .[0:3][0])	[2,4,5]	[3,4,5]
B3	[1,2,3,4,5]	del(.[0:2][0], .[1:][0])	[3,4,5]	[2,4,5]
B4	[1,2,3,4,5]	del(.[:2][0], .[3:][0])	[2,3,5]	[2,3,4]
B5	[1,{"x":1},3]	del(.[0:2][0], .[1].x)	[{},3]	[{"x":1},3]
B6	[{"x":1},2,{"x":3}]	del(.[0:2][1], .[2].x)	[{"x":1},{}]	[{"x":1},{"x":3}]

Each row's mirror argument order already agrees, so the difference is order alone.

Rows that must not change (agree today):

#	Doc	Filter / mode	Reference
K1	{"a":"s"}	jq del(.a, .a[0])	error Cannot index string with number
K2	{"a":5,"b":"s"}	jq del(.a, .b.x, .a.y)	error Cannot index string with string "x"
K3	{"a":"s"}	jq del(.a, (.a[0])?)	{}
K4	[]	jq del(.[0], .[1:2].b?[2:3]) (#2049)	[]
K5	[1,2,3,4]	jq del(.[0:2], .[1:3][0])	[4]
K6	[1,2,3,4]	jq del(.[0], .[0:2][1])	[3,4]
K7	"hi"	jq del(.[0:1], .[1:2]) (#504)	error Cannot delete fields from string
Y1	[]	yq del(.[3], .[3].a)	[null,null,null]
Y2	[[1,2]]	yq del(.[0], .[0][-5])	error index [-5] out of range, array size is 2
Y3	[1,2,3,4,5]	yq del(.[0:1] | ..), del(.[3:5][0], .[0:2][0])	unchanged input (slice del is a no-op in yq)

K1 and K2 are the two #1690 tests (test_del_trie_preserves_group_order_and_terminal_recursion_1690) that look like they depend on the trie walking into a doomed key. They don't: [path(.a, .a[0])] and [path(.a, .b.x, .a.y)] raise the same errors, so the error already comes from path resolution, before any trie exists. Y2 is the opposite case. yq does raise from inside a doomed key, which is why fix A must be jq-only.

Root cause (confirmed)

jq's del(f) is delpaths([path(f)]), and jq's delpaths_sorted (src/jv_aux.c) makes two decisions per container:

1. A key whose shortest path ends here goes into delkeys, and jq never recurses into it ("deleting this entire key, we don't care about any more specific deletions").
2. Groups are visited in jv_sort order of the key: numbers ascending, then objects. Slice descriptors {"start":s,"end":e} compare on end first ("end" < "start"), then start, with null < number.

succinctly's delpaths builtin already implements both (delete_paths_sorted in src/jq/eval.rs). delpaths([[{"start":0,"end":1}],[{"start":0,"end":1},0]]) and B3's delpaths spelling both match jq. The DeleteTrie apply walk that del() uses implements neither:

• delete_trie_object and delete_trie_array loop over every field_groups/index_groups child, including children that are themselves terminal, and write each result back. Only then do they batch the terminal keys into delete_keys. For a slice child, the write-back is arr.splice(range, shorter). The terminal delete_keys then resolves .[0:1] against the shrunk array and deletes the next element. That is A1–A9. For a string under the doomed key, the walk raises. That is A10–A13.
• index_groups is in first-continuation order (jq: del() is O(n²) with a computed key ahead of a trailing iterate #1301's error-priority ordering), not jq's sorted order. That is B1–B6.

The DeleteTrieNode::terminal doc comment argues for the opposite ("short-circuiting on terminal would silently swallow" del(.a, .a[0])'s error). That rationale is wrong: the error comes from resolution (K1). A10–A13 are the counterexample it missed.

Plan

All changes are in src/jq/eval.rs. eval_generic.rs only classifies Builtin::Del as Keeps, and both evaluators reach builtin_del.

1. Skip terminal children in jq mode (fix A). In delete_trie_object's field_groups loop and in delete_trie_array's index_groups loop, continue when !yq_mode && trie.node(child).terminal. The child is still collected into doomed below, so it is deleted wholesale, exactly like jq's delkey. Keep yq mode walking. Y1 and Y2 show real yq observes the walk (it pads, and it raises index out of range).

• The two null-value loops (delete_trie_object's and delete_trie_array's delete_trie_through_absent calls) cannot raise per that function's doc comment. Applying the same skip there is optional. If you add it, add it to both loops.
• Rewrite the DeleteTrieNode::terminal doc comment. Say jq never walks into a doomed key, jq-mode errors for that shape come from resolve_del_path_branches, and yq mode still walks (Y2).

2. Visit array groups in jq's key order when a slice continuation is present (fix B). At the top of delete_trie_array's index_groups loop, when !yq_mode and any group step is ArrayStep::Slice, iterate a sorted copy of the slots instead of index_groups directly. Use this comparator on ArrayStep, with no OwnedValue allocation:

• Index(a) vs Index(b): a.cmp(b)
• Index(_) < Slice(..)
• Slice(s1, e1) vs Slice(s2, e2): compare e1 with e2, then s1 with s2, where None < Some(n) and numbers compare numerically. Option<i64>'s derived Ord is exactly this.

A stable sort keeps index-only nodes on the existing order. Index-only continuations never shift the array, so their order is unobservable except for error priority, and #1690's K2-style tests pin that order. Gating on "has a slice group" also keeps the #1690 filtered-descent shapes (millions of Index groups) off the sort.

3. Doc comments. Update delete_trie_array's slice arm comment ("Deleting through a slice…") to note that it now runs in jq key order and never under a doomed key. Update the DeleteTrie "Fidelity" section to name the two delpaths_sorted rules it now mirrors.

Tests

• tests/jq_computed_key_tests.rs (check runs both evaluators): add test_del_trie_terminal_subsumes_continuations_2929 with A1–A13 and test_del_trie_array_groups_follow_jq_key_order_2929 with B1–B6. Put each row next to its mirror argument order, so a regression to "first-seen order" can't pass by accident.
• Keep test_del_trie_preserves_group_order_and_terminal_recursion_1690 green without editing its expectations. Rewrite its point (2) doc comment: the error comes from resolution, not the trie walk. Add K3–K7.
• tests/yq_cli_tests.rs: add Y1–Y3 as must-not-change rows for the jq-only gate.
• Differential fuzz before merging. A hand-picked matrix is biased. Generate del(p1, p2[, p3]) over 2–4-element arrays and objects nested 2 deep, where each p is drawn from .[i], .[a:b], .[a:], .[:b], .k, with 0–2 further steps and optional ?/| ... Compare succinctly jq -c against /usr/bin/jq, and triage every difference against a baseline binary from b509a8019 so pre-existing ones aren't charged to this fix. Validate the harness first: reverting fix B alone must make it report B-shaped rows.

Docs

No user-facing docs change. del() now matches jq, so nothing goes in docs/compliance/jq/limitations.md. If fix A's yq-mode gate is kept, no yq limitation is added either, because yq behaviour is untouched.

Risks

• Error priority. Fix A removes a walk that K1 and K2 appeared to need. Resolution raises those errors first, as checked above. The fuzz step is what catches a walk-only error that jq does raise and resolution does not.
• yq mode. Both fixes are gated !yq_mode. yq rewrites or no-ops every slice del() before the trie (Y3), so fix B cannot reach it anyway.
• Perf. Fix A strictly removes work. Fix B sorts only at nodes that already have a slice continuation, which is O(g log g) over a handful of groups. No A/B needed; the perf-guard CI check covers the rest.

Out of scope (follow-up)

Filed as #3039. The yq-mode {"a":"ab"} | del(.a, .a[0]) divergence is not about a doomed key. Any comma-grouped yq del() with a branch that steps into a scalar raises, e.g. del(.c, .a[0]), while the single-path form already no-ops. The cause is in the resolver (the del() half of #1419's plan), so this issue's jq-only gate stays as planned.

Dependencies

None.

Class: Sonnet (was Opus)

• Localised: two loops in two functions of one file, one evaluator (builtin_del serves both), no ADR, no representation change.
• Oracle-pinned: both rules are jq's delpaths_sorted, which succinctly already mirrors in delete_paths_sorted. The comparator is fully specified, and every row above is captured.
• The judgement Opus was filed for is done here: the prefix-interning hypothesis is ruled out, the perf(jq): del() filtered-descent (non-root match set) still O(d²) after #1651's root-only fix #1690 error-ordering doubt is settled (K1/K2 come from resolution), and the yq split is decided (Y1/Y2 → gate to jq).
• Residual risk is a walk-only error jq also raises. The fuzz step is a mechanical check for it, not a design decision.

[newhoggy]

🔧 Claimed by agent Amanda — branch issue-2929-del-trie-slice-order