vcs: build_trend per-point build re-walks the first-parent timeline (stale O(commits)-lookup comment)

[dekobon]

Summary

git::build_trend computes a single shared first-parent timeline "so each point is an O(commits) lookup rather than its own walk", but since the #648 --as-of re-anchoring landed in build, every per-point build call now performs its own full first-parent walk — defeating the optimization the comment describes and making that comment stale.

Location

• src/vcs/git/trend.rs:57-67 (the shared-timeline comment and drop(repo) / per-point build loop)
• Interacts with src/vcs/git/mod.rs:101-119 (resolve_anchor → first_parent_timeline whenever options.as_of.is_some())

Evidence

build_trend builds the timeline once and explains the intent:

// One first-parent walk of the base reference yields every mainline
// tip and its time, so each point is an O(commits) lookup rather than
// its own walk.
let OpenRepo { repo, .. } = repo::open(root)?;
let tip = repo::resolve_commit(&repo, &base.reference)?.id;
let timeline = first_parent_timeline(&repo, tip)?;
drop(repo);
...
for &at in &stamps {
    let Some(oid) = tip_at_or_before(&timeline, at) else { ... };
    let index = build(root, &snapshot_options(base, oid, at))?;  // re-walks!
    ...
}

snapshot_options always sets as_of = Some(at) (src/vcs/git/trend.rs:95-101). In build, any as_of triggers resolve_anchor, which unconditionally re-walks the first-parent timeline (src/vcs/git/mod.rs:106-110):

let Some(as_of) = options.as_of else { return Ok(Some(tip)); };
let timeline = trend::first_parent_timeline(repo, tip.id)?;   // P extra walks
let Some(anchor) = trend::tip_at_or_before(&timeline, as_of) else { ... };

Git history confirms the comment is stale: at the trend feature's introduction (9624098b) build had no resolve_anchor/first_parent_timeline and did not re-walk, so "an O(commits) lookup rather than its own walk" was accurate. The #648 fix (cb12db79) added the per-as_of re-anchoring walk afterwards, defeating the shared-timeline optimization without updating the trend comment.

Net effect for P points: 1 + P first-parent walks instead of the documented 1. (The first-parent walk is cheap relative to each point's window walk in collect_events, so this is wasted work rather than a correctness defect.)

Expected Behavior

Either:

1. Pass the already-resolved historical anchor oid through to build so it skips the redundant first_parent_timeline re-walk (the comment then becomes true again), or
2. Correct the comment to state that each point still performs its own first-parent walk inside build.

Actual Behavior

build_trend resolves the timeline once and every per-point build resolves it again, while the comment claims the per-point work is only an O(commits) lookup.

Impact

VCS-git trend consumers (bca vcs --trend, web /vcs/trend, Python vcs.trend). The shared timeline gives no run-time benefit it claims to; a reader trusting the comment would mis-model the cost, and the redundant walks scale linearly with the requested point count (up to MAX_TREND_POINTS = 120).

---

Resolution

Corrected the stale trend.rs comment: the shared timeline only resolves each point's tip oid; each per-point build re-walks the first-parent timeline (O(points x commits) since #648). Commit a7e35ad.

[dekobon]

General Plan for Fix

Root Cause

build_trend was written (commit 9624098b) when build anchored
directly at options.reference without re-walking. The #648 fix
(cb12db79) later added resolve_anchor, which re-walks the
first-parent timeline whenever options.as_of.is_some(). Because
snapshot_options always sets as_of, every per-point build now
re-resolves the timeline that build_trend already computed once,
contradicting the in-source comment.

Implementation Steps (preferred: option 1 — eliminate the redundant walk)

1. Give build a way to accept an already-resolved anchor so it can
   skip resolve_anchor. Two low-risk shapes:
   • Add an internal build_at(root, options, anchor_oid) that anchors
     directly at anchor_oid (re-resolving it to an owned Commit),
     skips first_parent_timeline/tip_at_or_before, and keeps the
     rest of build identical; have build_trend call it with the
     oid it already resolved, and have build delegate to it after
     running resolve_anchor.
   • Or factor the post-anchor body of build into a shared helper
     taking the resolved Commit, called by both build and
     build_trend.
2. In build_trend, replace the build(root, &snapshot_options(...))
   call with the new anchor-aware entry point, passing the per-point
   oid directly. as_of is still set on the options for the window
   arithmetic (now = at), but no second timeline walk occurs.
3. Update the build_trend comment so it remains accurate.

Alternative (option 2 — comment-only)

If the redundant walk is judged acceptable (it is cheap relative to the
per-point window walk), just correct the comment in trend.rs:57-59 to
state that each point performs its own first-parent walk inside build,
and drop the "rather than its own walk" claim.

Tests to Add/Update

• A trend integration test (under the existing vcs-git git-fixture
  harness) asserting trend values are unchanged after the refactor —
  the anchor-aware path must produce byte-identical Trend output to
  the current build-via-snapshot_options path for the same repo.
• Keep snapshot_options_anchors_reference_and_as_of passing; if the
  new path no longer routes through snapshot_options, retain a unit
  test that the per-point anchor equals tip_at_or_before(timeline, at).

Verification

• cargo test -p big-code-analysis --features vcs-git passes
• cargo clippy -p big-code-analysis --features vcs-git clean
• Manual: run bca vcs --trend --points N on a repo with clock-skewed
  history and confirm identical output before/after the change

[dekobon]

Fixed in commit a7e35ad. The trend.rs comment no longer claims each point is an O(commits) lookup rather than its own walk. It now notes the shared timeline is used only to resolve each point's tip oid, while every per-point build re-anchors and re-walks the first-parent timeline itself (an O(points x commits) cost since #648). Doc-only; a follow-up could hoist the walk.

[dekobon]

Fixed and merged to main in #957. GitHub did not auto-close this from the batched commit's single Fixes #a #b #c … trailer (only the first referenced issue auto-closes); closing manually. See the Resolution section in the body for details.