Skip to content

Guard self-referential spills, and adopt the incremental-vs-full differential generator #945

Description

@hhimanshu

Summary

Two things, both from an independent review of #942 that verified incremental ≡ full across 24,000 randomized workbooks.

1. Self-referential spills need a guard

#942's four tests cannot distinguish the correct seeding order from the broken one. With seed_spill_sensitive moved back below the closure drain, all four still pass — yet the reviewer's differential corpus found 3 divergences in 6,000 workbooks.

The class is a cell that reads a cell inside its own spill footprint. Minimal shape:

B5 = ={8;4}          spills onto B5:B6
C1 = =C2+B5          C1's own array spills into C2 — so C1 reads inside its own footprint
E5 = =IF(D6>2,C2,3)
A4 = =E5+1

Incremental converged at C1 = [[228],[224]]; a full recalc gives [[116],[112]] — an exact doubling, one extra fixed-point iteration. Two further seeds showed the same signature (721 vs 481, 160 vs 109).

Mechanism: with the correct ordering, the first widen pass recomputes the complete closure — which is what a full recalc's single topological pass does — so it converges immediately. Under the wrong ordering, pass one recomputes a partial set and the late-seeded queue forces a second pass, and therefore a second iteration of the self-referential cell.

So stage ordering is load-bearing for byte-identity, not for speed — the opposite of what #942 originally claimed. The shipped code is correct; what is missing is a test that would notice if someone reordered it again.

Add a guard using this shape, asserting the workbook equals a fresh full recalc.

2. Adopt the differential generator

The review built three randomized generators comparing recalc_incremental against a fresh full recalc on a clone, as canonical JSON. Discrimination on the pre-#942 base:

generator divergences on base
plain 13 / 2000
spill-heavy 9 / 2000
conditional arrays 650 / 2000

The third is the sharpest — arrays whose footprint changes mid-recalc (=IF(cond,{1,2,3},{1,2})). All three pass 8,000 seeds each on #942.

This is worth having in the repo rather than living in a review transcript. It is the only instrument that has reliably caught this defect class, and #922 established that the value-asserting suites structurally cannot.

Coverage it should include: two sheets, cross-sheet references, defined names and retargeting, ranges, TODAY/RAND, array anchors, conditional arrays, clear, and formula↔literal↔array edits.

Provenance

Found by an independent review of #942, verified by execution.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions