Index snapshot topology once when ranking find matches

[thymikee]

Plan 007: Index snapshot topology once when ranking find matches

Executor instructions: Follow this plan step by step. Run every
verification command and confirm the expected result before moving to the
next step. If anything in the "STOP conditions" section occurs, stop and
report — do not improvise. A reviewer maintains the plan index for this
execution; do not create or edit plans/README.md.

Drift check (run first):
git diff --stat 13bc70f24..HEAD -- src/daemon/handlers/find.ts src/daemon/handlers/find-match-ranking.ts src/daemon/handlers/__tests__/find-match-ranking.test.ts src/core/actionable-touch-topology.ts src/core/actionable-touch-topology.test.ts src/core/interaction-targeting.ts src/core/interaction-targeting.test.ts src/snapshot/snapshot-processing.ts
If any in-scope file changed since this plan was written, compare the
"Current state" excerpts against the live code before proceeding; on a
mismatch, treat it as a STOP condition.

Status

• Priority: P2
• Effort: M
• Risk: MED
• Depends on: none
• Category: perf
• Planned at: commit 13bc70f24, 2026-08-08

Why this matters

A mutating find ... click|fill|focus|type ranks every candidate before it
narrows with --first/--last or returns AMBIGUOUS_MATCH. Each candidate
currently triggers multiple full-snapshot traversals: descendant discovery
filters all nodes, ancestor lookup rebuilds the index map, and viewport-root
resolution filters all nodes again. With m matches in an n-node capture,
those paths perform O(m × n) full-tree work before the action or refusal. This
plan builds one immutable topology index per multi-match ranking pass and
threads it through the existing actionability policy without changing match
ordering, candidate details, ambiguity behavior, or single-target callers.

Current state

Relevant files and their roles:

• src/daemon/handlers/find.ts — mutating-find orchestration and current
  on-screen preference. It is already 624 lines, so scoring must be extracted
  into a focused sibling; this file retains the small per-ranking-pass wrapper
  that builds and passes one topology.
• src/daemon/handlers/find-match-ranking.ts — new focused module to own
  actionability scoring, stable tie-breaking, and root interaction-container
  classification.
• src/core/actionable-touch-topology.ts — new concrete one-pass topology
  builder shared by ranking and actionability resolution. It is an internal
  source module, not a package/public API or a generic adapter abstraction.
• src/core/interaction-targeting.ts — canonical touch-target promotion
  policy. It must accept an optional prebuilt topology while preserving the
  current no-topology call shape for ordinary one-target interactions.
• src/snapshot/snapshot-processing.ts — canonical nearest-ancestor helper;
  it currently builds its node map internally on every call.
• src/daemon/handlers/__tests__/find.test.ts — existing end-to-end handler
  tests for candidate ordering, ambiguity, and --first. It is 1,232 lines;
  run it, but do not add more cases to it.

Ranking occurs before ambiguity rejection or explicit positional narrowing:

// src/daemon/handlers/find.ts:293-305
matches = preferOnscreenMatches(matches, nodes);

if (matches.length > 1) {
  assertRejectsCandidates(policy);
  const narrowed = narrowMultipleMatches(matches, flags);
  if (!narrowed) {
    return { ok: false, response: buildAmbiguousMatchError(matches, locator, query) };
  }
  matches = narrowed;
}

Every candidate is scored independently:

// src/daemon/handlers/find.ts:345-365
function rankInteractiveMatches(
  matches: SnapshotState['nodes'],
  nodes: SnapshotState['nodes'],
): SnapshotState['nodes'] {
  if (matches.length < 2) return matches;
  return matches
    .map((node, index) => ({ node, index, score: interactiveMatchScore(node, nodes) }))
    .sort(/* score, rect area, original index */)
    .map((entry) => entry.node);
}

function interactiveMatchScore(node, nodes): number {
  const resolution = resolveActionableTouchResolution(nodes, node);
  // ...
}

There are three distinct per-candidate full-tree paths. All three must use the
same prebuilt topology; optimizing only the first two leaves the Android/
nonsemantic ancestor path quadratic.

// src/core/interaction-targeting.ts:49-69,77-103
export function resolveActionableTouchResolution(nodes, node) {
  // ...
  const descendant = findPreferredActionableDescendant(nodes, node);
  // ...
  const ancestor = findNearestHittableAncestor(nodes, node);
  // ...
}

function findPreferredActionableDescendant(nodes, node) {
  // For every step in a same-rect chain:
  const sameRectChildren = nodes.filter((candidate) => {
    if (candidate.parentIndex !== current.index || !candidate.hittable /* ... */) return false;
    // ...
  });
}

// src/core/interaction-targeting.ts:127-169
function isOverlyBroadAncestor(node, ancestor, nodes): boolean {
  // ...
  const rootViewportRect = resolveRootViewportRect(nodes, nodeRect);
  // ...
}

function resolveRootViewportRect(nodes, targetRect): Rect | null {
  const viewportRects = nodes
    .filter(isViewportRootNode)
    .map((node) => normalizeRect(node.rect))
    .filter((rect): rect is Rect => rect !== null);
  // ...
}

Ancestor lookup constructs another full map per candidate:

// src/snapshot/snapshot-processing.ts:86-105
export function findNearestHittableAncestor(nodes, node) {
  if (node.hittable) return node;
  return findNearestAncestor(nodes, node, (parent) => parent.hittable === true);
}

export function findNearestAncestor(nodes, node, predicate) {
  const nodesByIndex = buildSnapshotNodeMap(nodes);
  return findSnapshotAncestor(nodes, node, nodesByIndex, (parent) =>
    predicate(parent) ? parent : null,
  );
}

Repository patterns and constraints to preserve:

• Build parent adjacency in one pass, matching
  src/daemon/snapshot-presentation/ios/web.ts:93-101: a Map keyed by
  parentIndex, append each child once, and do not filter the whole tree per parent.
• Node identity and ancestors are keyed by node.index, not array position.
  packages/contracts/src/snapshot-tree.ts:3-31 supplies
  buildSnapshotNodeMap/findSnapshotAncestor and preserves an array-offset
  fallback plus cycle protection. Do not weaken that behavior.
• Viewport roots must continue to use the canonical isViewportRootNode
  predicate. This plan only precomputes its candidates. It must not change the
  current resolveRootViewportRect selection algorithm or add the separately
  known Android largest-containing-rect fallback.
• src/daemon/handlers/__tests__/find.test.ts:667-722 pins the public contract:
  ambiguous selector-shaped finds refuse with candidates, while explicit
  --first selects the first element in the established ranked order.
• docs/agents/testing.md:68-75 requires a regression test to be observed red
  against the pre-fix production path. For performance work, use operation
  counts and a real production builder spy; do not use a wall-clock threshold.
• Do not add a test-only DI parameter. preferOnscreenMatches remains the real
  production wrapper called by resolveFindMatch; exporting that wrapper gives
  the focused regression a direct policy seam without adding injectable state.

Commands you will need

Purpose	Command	Expected on success
Inspect handler impact	pnpm depgraph affected src/daemon/handlers/find.ts --limit 25	exit 0; bounded dependents, gates, and command owners are printed
Inspect shared-policy impact	pnpm depgraph affected src/core/interaction-targeting.ts --limit 25	exit 0; bounded dependents, gates, and command owners are printed
Focused tests	pnpm exec vitest run src/daemon/handlers/__tests__/find-match-ranking.test.ts src/daemon/handlers/__tests__/find.test.ts src/core/actionable-touch-topology.test.ts src/core/interaction-targeting.test.ts src/utils/__tests__/snapshot-processing.test.ts src/daemon/__tests__/snapshot-processing.test.ts	all selected files pass
Fast static gate	pnpm check:quick	exit 0; lint and typecheck pass
Format	pnpm format	exit 0; only intended in-scope source/test formatting changes remain
Affected gate	pnpm check:affected --run	exit 0; selected local gates pass and CI-owned gates are reported
Broad deterministic gate	pnpm check	exit 0; tooling, fallow, unit, and smoke aggregates pass

The repository requires pnpm 11.17.0 and Node >=22.12. Do not create or
restore package-lock.json. No native/Apple build is required because all
in-scope changes are TypeScript; follow pnpm check:affected --run if the
actual diff selects an additional authoritative lane.

Scope

In scope (the only implementation/test files to modify or create):

• src/daemon/handlers/find.ts
• src/daemon/handlers/find-match-ranking.ts (create)
• src/daemon/handlers/__tests__/find-match-ranking.test.ts (create)
• src/core/actionable-touch-topology.ts (create)
• src/core/actionable-touch-topology.test.ts (create)
• src/core/interaction-targeting.ts
• src/core/interaction-targeting.test.ts
• src/snapshot/snapshot-processing.ts

Out of scope (do NOT touch, even though they are related):

• src/daemon/handlers/__tests__/find.test.ts — this legacy 1,232-line file
  remains authoritative handler coverage but must not grow in this plan.
• Selector parsing/resolution, fuzzy locator scoring, findAct policy,
  buildAmbiguousMatchError, candidate payload rendering, --first/--last
  semantics, and public response shapes.
• packages/contracts/src/snapshot-visibility.ts and Android viewport fallback
  behavior. The known resolver divergence is not part of this performance fix.
• Interaction occlusion, semantic-role classification, press retargeting,
  ref-frame admission, replay guards, capture freshness, or snapshot caching.
• Package/public barrels and exports. Import the new internal module directly;
  do not add it to the npm package surface.
• A generic repository-wide tree-index abstraction. This plan has one concrete
  actionability topology with real consumers in find ranking and touch resolution.
• README, website, CLI help, or skill behavior guidance. No user-facing behavior
  or command surface is intended to change.
• plans/README.md and every other plan file.

Git workflow

• Suggested branch: advisor/007-index-find-ranking-topology
• Keep the behavior-preserving ranking extraction separate from the indexed
  implementation if the operator wants reviewable commits.
• Suggested commit messages:
  • refactor(find): isolate match ranking policy
  • perf(find): index snapshot topology during match ranking
• Commit messages follow the repository's conventional prefixes. Do not push
  or open a PR unless the operator explicitly instructs it.

Steps

Step 1: Extract ranking without changing behavior

Create src/daemon/handlers/find-match-ranking.ts and move the coherent ranking
question out of the already oversized handler:

• rankInteractiveMatches
• interactiveMatchScore
• resolvedTouchScore
• rectArea
• isRootInteractionContainer
• rectsMatch

Export rankInteractiveMatches and isRootInteractionContainer because
find.ts is their real production caller. Keep the other moved helpers private.
Retain preferOnscreenMatches in find.ts, export it as the focused production
wrapper, and have it call the extracted rankInteractiveMatches. Remove imports
used only by the moved code. Do not move locator matching, ambiguity-response
construction, node fetching, or action dispatch. At the end of this step, the
extracted ranking must still call resolveActionableTouchResolution(nodes, node)
with no topology, so this is a pure move that establishes a testable seam before
optimization.

Run the existing handler and targeting tests before proceeding. Candidate order,
candidate rendering, AMBIGUOUS_MATCH, and explicit --first must be identical.

Verify:
pnpm exec vitest run src/daemon/handlers/__tests__/find.test.ts src/core/interaction-targeting.test.ts src/utils/__tests__/snapshot-processing.test.ts src/daemon/__tests__/snapshot-processing.test.ts
→ all pass with the behavior-preserving extraction only.

Step 2: Add the concrete one-pass topology builder

Create src/core/actionable-touch-topology.ts with a narrow production type and
builder. Use durable domain names such as:

type ActionableTouchTopology = {
  nodesByIndex: ReadonlyMap<number, SnapshotNode>;
  childrenByParentIndex: ReadonlyMap<number, readonly SnapshotNode[]>;
  viewportRootNodes: readonly SnapshotNode[];
};

buildActionableTouchTopology(nodes: readonly SnapshotNode[]): ActionableTouchTopology

Construct all three collections in one for...of pass:

1. add every node by node.index;
2. append nodes with numeric parentIndex to that parent's children array; and
3. append nodes satisfying canonical isViewportRootNode to
   viewportRootNodes.

The topology is immutable by convention for the duration of one ranking pass;
do not mutate snapshot nodes or cache it on a session. Do not use nodes.filter
or nodes.map inside this builder — the regression test will instrument those
operations to prove the full tree is not rescanned per candidate. No package
barrel export is needed.

Create src/core/actionable-touch-topology.test.ts. Using makeSnapshotState
from the shared test-utils barrel, assert one mixed tree produces the expected:

• node-by-index entries, including non-contiguous indexes;
• child lists for two different parents in input order; and
• viewport-root list using type, role, or subrole through the canonical predicate.

Keep this test structural to the builder's real production output; do not add a
test-only counter or injectable builder.

Verify:
pnpm exec vitest run src/core/actionable-touch-topology.test.ts
→ the new builder tests pass.

Step 3: Add a deterministic red proof for one build and zero full rescans

Create src/daemon/handlers/__tests__/find-match-ranking.test.ts. Test the
production export preferOnscreenMatches; do not reach a private helper or add
test-only DI.

Use Vitest's module mocking to wrap the real
buildActionableTouchTopology export with vi.fn(actualBuilder). The mock must
delegate to the real builder so the test exercises production topology data,
not a test double. Import preferOnscreenMatches from ../find.ts only after
the hoisted/partial mock is declared, following existing
vi.mock(..., importOriginal) patterns in the repository. Import the mocked
builder export too so each case can clear and inspect the real wrapper's call
history; do not add a production counter or DI argument.

Build a duplicate-heavy but small deterministic tree:

• one hittable Application root with a finite viewport rect;
• at least 32 nonsemantic, nonhittable rectangular children that all qualify as
  matches and therefore require descendant, ancestor, and overly-broad-root
  checks in the old implementation; and
• a distinct matches array so its legitimate on-screen .filter is not
  confused with a full-tree scan.

Wrap only the full nodes array in a Proxy that counts calls to its filter
and map methods, then call preferOnscreenMatches(matches, observedNodes).
Assert:

1. the real topology builder was called exactly once for the multi-match
   ranking pass;
2. the observed full tree had zero .filter calls after the one-pass builder;
3. the observed full tree had zero .map calls after the one-pass builder; and
4. the ranked result contains the same refs in the same stable order expected
   from the current scoring/tie-break rules.

The test is intentionally about operation counts, not elapsed milliseconds.
Before Step 4, the behavior-preserving extracted ranking does not call the
builder and still performs per-candidate full-tree filter/map operations.
Run it now and record the exact failing counts. It must fail on the builder
count and/or scan-count assertions, never on a timeout.

Also add a one-candidate case that asserts the builder is not called: the
existing fast return for fewer than two matches must remain allocation-free.

Verify (red, before topology wiring):
pnpm exec vitest run src/daemon/handlers/__tests__/find-match-ranking.test.ts
→ exits nonzero on the expected builder/full-tree operation-count assertions;
record the failing numbers in the PR or handoff.

Step 4: Thread one topology through every candidate score

Wire the production topology without changing existing required call shapes:

1. In find.ts, keep the on-screen preference in preferOnscreenMatches, then
   return immediately when the preferred set has fewer than two nodes. For a
   real multi-match ranking pass, call buildActionableTouchTopology(nodes)
   exactly once and pass it to rankInteractiveMatches. This is the only
   topology build site for the pass. Preserve the existing no-viewport early
   return too: when nodes[0]?.rect is absent, return matches without ranking
   or building an index, exactly as today.
2. In find-match-ranking.ts, accept that topology as a third argument and
   pass the same object to every interactiveMatchScore and then every
   resolveActionableTouchResolution call. Permit undefined at this internal
   seam so the unindexed behavior remains directly comparable and the focused
   red proof can disable only the caller wiring; the final production caller
   must always supply the topology for two or more preferred matches.
3. In interaction-targeting.ts, add an optional third
   ActionableTouchTopology argument to resolveActionableTouchResolution.
   Keep resolveActionableTouchNode(nodes, node) and all existing two-argument
   callers valid and behaviorally unchanged.
4. Update findPreferredActionableDescendant to read only
   topology.childrenByParentIndex.get(current.index) when topology is present.
   Preserve its exact hittable, blocked, same-rect, unique-child, and cycle
   rules. When topology is absent, retain the current scan path for ordinary
   one-off callers rather than building a full topology unconditionally.
5. Extend findNearestHittableAncestor/findNearestAncestor in
   snapshot-processing.ts with an optional prebuilt nodesByIndex argument
   (placed so existing call sites remain source-compatible). Use the supplied
   map when present; otherwise build the map exactly as today. Pass
   topology.nodesByIndex from actionability resolution.
6. Thread the optional topology into isOverlyBroadAncestor and
   resolveRootViewportRect. When present, derive normalized viewport rects
   from topology.viewportRootNodes; do not run nodes.filter(isViewportRootNode).
   When absent, retain the current implementation.

Do not cache a topology outside the call. The tree is a fresh operational
observation, and an index that survives into another capture would be stale.
Do not change isViewportRootNode, viewport selection, root-container
classification, score values, area tie-breaking, original-index tie-breaking,
or covered-node handling.

Verify:
pnpm exec vitest run src/daemon/handlers/__tests__/find-match-ranking.test.ts src/core/actionable-touch-topology.test.ts src/core/interaction-targeting.test.ts src/utils/__tests__/snapshot-processing.test.ts src/daemon/__tests__/snapshot-processing.test.ts
→ all pass; multi-match ranking builds once and performs no instrumented
full-tree filter/map, while the one-match case builds zero times.

Step 5: Prove indexed and unindexed policy parity

Extend src/core/interaction-targeting.test.ts with one focused parity test.
Create a mixed tree containing:

• a same-rect actionable descendant;
• a semantic touch target;
• a nonhittable leaf under a hittable ancestor;
• a scrolling or viewport-sized overly broad ancestor;
• a covered node; and
• a node with no usable target.

Build one topology, resolve every relevant node once without the optional
argument and once with it, and deep-compare the complete { node, reason }
results. This is a behavior pin, not a second implementation of score rules.
Existing property/example tests remain untouched.

After the full change is green, mechanically prove the new ranking test is
load-bearing: temporarily disable only the production topology-build/pass-through
hunk in find.ts (pass undefined to the extracted ranking exactly as the
pre-wiring path did), rerun the new ranking test, and record the failure showing
the builder count changed from one to zero and the full-tree scan counts became
nonzero. Do not change find-match-ranking.ts or the topology builder for this
proof. Restore the find.ts hunk and rerun green. Do not use a timing assertion
as substitute evidence.

Verify:
pnpm exec vitest run src/daemon/handlers/__tests__/find-match-ranking.test.ts src/daemon/handlers/__tests__/find.test.ts src/core/actionable-touch-topology.test.ts src/core/interaction-targeting.test.ts src/utils/__tests__/snapshot-processing.test.ts src/daemon/__tests__/snapshot-processing.test.ts
→ all pass after restoring the optimized production hunk.

Step 6: Tighten and run repository gates

Review the final diff for duplicated tree maps, unused exports, stale imports,
or ranking logic left behind in find.ts. Confirm the new topology module
answers only the concrete indexing question and is imported directly rather
than added to a package/internal barrel. Confirm no fallback, viewport, or
candidate-order behavior was opportunistically changed.

Run formatting, focused tests, fast static checks, the affected selector, and
the broad deterministic gate. If formatting touches unrelated files, do not
include that drift.

Verify:

pnpm format
pnpm exec vitest run src/daemon/handlers/__tests__/find-match-ranking.test.ts src/daemon/handlers/__tests__/find.test.ts src/core/actionable-touch-topology.test.ts src/core/interaction-targeting.test.ts src/utils/__tests__/snapshot-processing.test.ts src/daemon/__tests__/snapshot-processing.test.ts
pnpm check:quick
pnpm check:affected --run
pnpm check

→ every command exits 0. git diff --name-only lists only the in-scope
implementation/test files plus an authorized plan-status update.

Test plan

• src/core/actionable-touch-topology.test.ts:
  • indexes non-contiguous node indexes;
  • groups children by parent in input order;
  • collects canonical viewport roots from emitted root vocabulary.
• src/daemon/handlers/__tests__/find-match-ranking.test.ts:
  • multi-match ranking calls the real topology builder exactly once;
  • single-match ranking calls it zero times;
  • the full snapshot array sees no per-candidate filter or map calls;
  • stable score/area/input-order ranking is unchanged.
• src/core/interaction-targeting.test.ts:
  • indexed and unindexed actionability resolution produce identical nodes and reasons
    across every current decision branch.
• Existing find.test.ts remains the handler-level contract for ambiguous
  candidates and explicit --first; run it but do not add to the oversized file.
• Existing src/utils/__tests__/snapshot-processing.test.ts and
  src/daemon/__tests__/snapshot-processing.test.ts remain the
  ancestor/index and nearest-hittable behavior pins and must pass with the
  optional map signature.
• Red-before-fix proof: after extraction and before wiring, run the new ranking
  test and record its non-timing count failures. After green, revert only the
  topology wiring hunk, reproduce red, restore, and rerun green.

Done criteria

ALL must hold:

• The focused ranking regression was observed red without the production
  topology wiring, and exact builder/operation counts are recorded in the
  PR or handoff.
• A multi-match ranking pass calls buildActionableTouchTopology exactly once.
• A zero/one-match pass does not build the topology.
• The duplicate-heavy regression observes zero full-tree .filter and
  .map calls during candidate scoring; no elapsed-time threshold is used.
• Descendant lookup, ancestor lookup, and viewport-root candidate lookup
  all consume the same per-pass topology when it is present.
• Indexed and unindexed actionability resolutions are deeply equal for the
  mixed policy fixture.
• Existing ambiguous-candidate and --first handler tests pass unchanged.
• pnpm exec vitest run src/daemon/handlers/__tests__/find-match-ranking.test.ts src/daemon/handlers/__tests__/find.test.ts src/core/actionable-touch-topology.test.ts src/core/interaction-targeting.test.ts src/utils/__tests__/snapshot-processing.test.ts src/daemon/__tests__/snapshot-processing.test.ts
  exits 0.
• pnpm check:quick exits 0.
• pnpm check:affected --run exits 0.
• pnpm check exits 0.
• No source/test files outside the Scope list are modified.
• No package barrel, selector policy, public response, viewport fallback,
  README, website, CLI-help, or skill behavior file is changed.
• Docs/skills are intentionally unchanged because this is an internal
  complexity improvement with no intended user-facing semantic change.
• plans/README.md and every other plan file are unchanged by the executor.

STOP conditions

Stop and report back; do not improvise if:

• Any in-scope current-state excerpt no longer matches after the drift check.
• The behavior-preserving extraction changes ranked refs, candidate details,
  ambiguity refusal, explicit --first/--last, or action target selection.
• A deterministic red proof cannot intercept the real topology builder through
  the production preferOnscreenMatches wrapper without adding test-only DI.
  Do not replace it with a wall-clock performance assertion or expose the
  helper through a package/public barrel.
• Eliminating the full scans appears to require changing selector resolution,
  locator scoring, semantic touch roles, occlusion, or viewport fallback policy.
• The optimized root lookup would add the Android largest-containing-rect
  fallback or otherwise differ from the current resolveRootViewportRect result.
• The topology would need to persist on SessionState, cross a capture boundary,
  or mutate snapshot nodes. It must be per ranking pass and read-only.
• Preserving findSnapshotAncestor's non-contiguous-index fallback or cycle
  behavior requires a packages/contracts change.
• A new generic abstraction or package export has only this one concrete use.
• A verification command fails twice after one reasonable, in-scope correction.
• Completion appears to require any source/test file outside Scope.

Maintenance notes

• Build the topology from the exact fresh node array being ranked and discard it
  with that pass. Snapshot freshness is an observable contract; never reuse an
  index across captures merely because the session name is unchanged.
• Future batch consumers of resolveActionableTouchResolution should build one
  topology and pass it to every resolution. One-off interaction callers may
  continue omitting it to avoid an unnecessary whole-tree allocation.
• viewportRootNodes must remain derived from canonical isViewportRootNode;
  new backend root vocabulary should update the canonical predicate, not add a
  ranking-only spelling.
• Reviewers should scrutinize the operation-count test, the no-build fast path,
  and indexed/unindexed parity. A builder call that is ignored by one of the
  three old scan sites is not a complete fix.
• Sorting remains O(m log m), and actionability still walks relevant parent or
  unique-child chains. This plan removes repeated full-tree scans; it does not
  introduce memoization for adversarial deeply nested same-rect chains. Treat
  that as a separate measured finding rather than expanding this scope.
• No docs or skills update is expected because public find semantics and output
  remain unchanged.