Skip to content

test(toc): replace wall-clock complexity guards with operation-counting #385

Open

Description

@Kuldeep2822k

Problem

The TOC-chain complexity guards in test/engine-toc-chain.test.ts assert an upper bound on wall-clock time to prove the scanner stays linear (e.g. elapsed < 2000ms for the label, destination, and angle-destination rescan guards).

Wall-clock assertions are inherently flaky on shared CI runners:

  • The sibling guard already went red once on a loaded Windows runner that cleared the linear scan in 261ms against a 250ms bound (fixed in 46b94a5 by widening to 2000ms).
  • The angle-destination guard was recently bumped from 10 000 → 20 000 reps (197f64f) only to widen the margin between the defect time and the clock bound — a band-aid, not a cure.

Widening the bound trades one flake risk (false red on a slow runner) for another (false green: a reintroduced quadratic walk that happens to finish under the generous bound on a fast runner).

Durable fix

Make the guards assert operations, not time. Instrument the scanner (e.g. a counter of characters visited / findLabelEnd + readDestination steps) and assert the count grows linearly in input size rather than measuring elapsed ms. An operation count is deterministic across runners and catches a regression regardless of machine speed, so the rep counts and time bounds can all come back down.

Affected tests

test/engine-toc-chain.test.ts:

  • does not rescan every label when one stray ] defeats the no-closer bail
  • does not rescan every destination when none of them balances
  • does not rescan every angle destination when none of them closes
  • stays linear on a pathological run of stray brackets

Notes

  • Correctness is already pinned by the output-based differential tests; this issue is purely about making the performance guards deterministic.
  • Deferred out of the current review pass because it is a larger change (touches src/engine/toc-chain.ts to expose an operation counter) than the flake-mitigation bump that shipped.

Activity

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions