Beagle SCM

JS-072 HIGH: patchscope.lca returns a stale (non-recent) merge base

patchscope.resolve pins the 3-way fork for be patch via lca(ours, theirs) (patchscope.js:139); patch.js:354 consumes sc.fork as the common base of the merge. But lca() walks theirs with a LIFO stack and returns the FIRST popped sha present in ancestorSet(ours) — DFS pop order has no relation to recency, so a diamond/merge history can hand back an older shared ancestor as the base. A too-old fork yields a noisier, wrong 3-way merge. Both walks are also uncapped. Method: Issues.

Input

Context

• patchscope.js:101-119 lca(reader,a,b): DFS-pops b, returns the

  first sha in ancestorSet(a) — pop order is arbitrary, not recency.

• The header comment patchscope.js:104-105 says "BFS … in ts order is

  overkill; a DFS that returns the first b-ancestor … is the merge base" — wrong: a DFS first-hit is NOT the most-recent common ancestor.

• patchscope.js:82-100 ancestorSet: unbounded stack.pop() DFS over

  commitParents, no WALK_CAP. lca adds a second unbounded DFS.

• patch.js:354: treeMap(reader, sc.fork) is the 3-way base; a stale

  fork makes file-level merges take/keep the wrong side (noise/conflicts).

• Contrast PATCH's dag.js: ancestors BFS is WALK_CAP-bounded

  (dag.js:30,43), the divergence is recency-ordered by commit ts.

Goals

• lca() returns the MOST-RECENT common ancestor on a diamond/merge

  graph (a recency-aware merge base), not a DFS first-hit.

• Both ancestor walks are bounded by a WALK_CAP (no unbounded DFS).
• be patch over a merged-side-branch history picks the recent base.

Constraints

• Keep lca returning undefined for no-shared-history (the caller

  drops to an empty base — patchscope.js:122-123,139).

• Prefer delegating to dag.js (WALK_CAP + ts recency already there) over

  a third local walk; keep the no-dag-cycle note honest if kept local.

• Same {scope,branch,ours,theirs,fork} shape; scope to patchscope.js.

WIP

Design decisions

• Recency-aware base: BFS by commit ts, or a two-colour generation LCA

  matching dag.js's parent-edge model (first-parent + merge parents).

• Reuse dag.ancestors/dag.isAncestor (WALK_CAP-bounded) instead of

  the local ancestorSet DFS, removing the unbounded-walk hazard.

TODOs

• Repro-first parity test/js/patch/*: a merge-side-branch-then-patch

  graph asserting lca returns the RECENT base, not the old ancestor.

• Replace the DFS first-hit with a recency-aware merge base + WALK_CAP.
• Re-run the existing patch parity suite (no regression on linear DAGs).

Blockers and bummers

• Confirm dag.commitParents parent set matches patchscope's intent

  (foster/rebase edges excluded — dag.js:18-24) before delegating.

• 2026-07-07 audit: STILL OPEN — shared/patchscope.js:101 lca is the DFS first-hit

  (comment :104-105 still says "a DFS that returns the first b-ancestor … is the merge base"); ancestorSet:83 and lca are both uncapped stack.pop() walks.

Outcome

• (pending)