dogfood
Jump to…
snowcorepublic2 bookmarks
snowinitial commitqoxwzsukwmkx1mo
mainroot / crates / df-index / src / indexer.rsBlameRaw
1//! The indexing pipeline (spec §4).
2//!
3//! ```text
4//! worker: IndexPush
5//! 1. walk new commits reachable from updated refs
6//! 2. extract change ids
7//! 3. upsert changes and revisions
8//! 4. recompute stack edges for affected changes
9//! 5. detect conflict state
10//! 6. rebase comment anchors onto the new revision
11//! 7. recompute change states vs target bookmarks
12//! 8. emit timeline events
13//! 9. NOTIFY so open pages can refresh
14//! ```
15//!
16//! The indexer must be **idempotent and re-runnable** — running it twice over
17//! the same repository must produce the same rows, because every change to
18//! indexing logic means reindexing live repositories.
19//!
20//! This module holds the pure decision logic. The database and storage calls
21//! live in `df-worker`, so the interesting parts are testable without either.
22
23use std::collections::{HashMap, HashSet};
24
25use crate::ChangeId;
26
27/// A commit as the indexer sees it, independent of any Git library.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub struct IndexedCommit {
30 pub rev: String,
31 pub change_id: Option<ChangeId>,
32 pub parents: Vec<String>,
33 pub author_name: String,
34 pub author_email: String,
35 pub authored_at: chrono::DateTime<chrono::Utc>,
36 pub message: String,
37 pub conflicted: bool,
38 pub conflict_sides: Vec<String>,
39 pub conflict_bases: Vec<String>,
40}
41
42impl IndexedCommit {
43 pub fn summary(&self) -> &str {
44 self.message.lines().next().unwrap_or("").trim()
45 }
46}
47
48/// A stack edge: `parent` sits immediately below `child`.
49#[derive(Debug, Clone, PartialEq, Eq, Hash)]
50pub struct StackEdge {
51 pub parent: String,
52 pub child: String,
53}
54
55/// Compute stack edges over a set of commits.
56///
57/// Spec §4: "A stack is a chain of changes where each is a parent of the next
58/// and none has yet merged into the target bookmark."
59///
60/// Edges are between *changes*, not revisions — that is what makes a stack
61/// survive a rebase. `merged` names changes already on the target bookmark;
62/// they terminate a stack rather than extending it.
63///
64/// Walks parent links transitively through commits whose change is already
65/// merged, so a stack is not severed by an intervening landed change.
66pub fn stack_edges(
67 commits: &[IndexedCommit],
68 merged: &HashSet<String>,
69) -> HashSet<StackEdge> {
70 // rev -> change id, for the commits in scope.
71 let by_rev: HashMap<&str, &IndexedCommit> =
72 commits.iter().map(|c| (c.rev.as_str(), c)).collect();
73
74 let change_of = |rev: &str| -> Option<String> {
75 by_rev
76 .get(rev)
77 .and_then(|c| c.change_id.as_ref())
78 .map(|c| c.as_str().to_owned())
79 };
80
81 let mut edges = HashSet::new();
82
83 for c in commits {
84 let Some(child) = c.change_id.as_ref().map(|c| c.as_str().to_owned()) else {
85 continue;
86 };
87 if merged.contains(&child) {
88 continue;
89 }
90
91 // Walk up until we find an unmerged ancestor change, or run out.
92 let mut frontier: Vec<String> = c.parents.clone();
93 let mut seen: HashSet<String> = HashSet::new();
94
95 while let Some(rev) = frontier.pop() {
96 if !seen.insert(rev.clone()) {
97 continue;
98 }
99 let Some(parent_change) = change_of(&rev) else {
100 // Outside the indexed set: stop this branch.
101 continue;
102 };
103
104 if parent_change == child {
105 // Same change appearing twice in the walk; not an edge.
106 continue;
107 }
108
109 if merged.contains(&parent_change) {
110 // Landed: look further up rather than ending the stack here.
111 if let Some(p) = by_rev.get(rev.as_str()) {
112 frontier.extend(p.parents.iter().cloned());
113 }
114 continue;
115 }
116
117 edges.insert(StackEdge {
118 parent: parent_change,
119 child: child.clone(),
120 });
121 }
122 }
123
124 edges
125}
126
127/// Decide the new state of a change.
128///
129/// Spec §4 step 7, and the draft decision: `draft` is set by the author in the
130/// UI and must never be overwritten by indexing.
131#[derive(Debug, Clone, Copy, PartialEq, Eq)]
132pub enum ChangeState {
133 Draft,
134 Open,
135 Merged,
136 Abandoned,
137}
138
139pub fn next_state(current: ChangeState, on_target_bookmark: bool) -> ChangeState {
140 match current {
141 // The author's explicit choice wins over anything inferred.
142 ChangeState::Draft => ChangeState::Draft,
143 // Abandoned is also explicit; a re-push does not silently reopen it.
144 ChangeState::Abandoned => ChangeState::Abandoned,
145 _ if on_target_bookmark => ChangeState::Merged,
146 // A change that was merged and is no longer reachable from the target
147 // has been reverted or the bookmark was rewound; reopen it.
148 ChangeState::Merged => ChangeState::Open,
149 ChangeState::Open => ChangeState::Open,
150 }
151}
152
153/// Where a comment anchor ended up after a new revision landed.
154///
155/// Spec §5: "This is the mechanism that makes stable change identity actually
156/// pay off for reviewers, and it is the single most valuable piece of logic in
157/// the product."
158#[derive(Debug, Clone, PartialEq, Eq)]
159pub enum AnchorOutcome {
160 /// Line is unchanged; keep `current`, update the anchor revision.
161 Unchanged,
162 /// Line moved; keep `current`, update the line number.
163 Moved { new_line: u32 },
164 /// The line's content changed; mark `outdated`, retain the original text.
165 Outdated,
166 /// The file or hunk is gone; mark `orphaned` and surface in the timeline.
167 Orphaned,
168}
169
170/// One line of the new version of a file, for anchor rebasing.
171#[derive(Debug, Clone)]
172pub struct NewLine {
173 pub number: u32,
174 pub content: String,
175 /// The line number this came from in the old version, when it is a
176 /// carried-over (context) line.
177 pub from_old: Option<u32>,
178}
179
180/// Re-anchor a comment onto a new revision.
181///
182/// `old_line` is where the comment sat; `anchor_context` is the text of that
183/// line when the comment was written — the thing we match on, because line
184/// numbers move but content is what the reviewer was talking about.
185pub fn rebase_anchor(
186 old_line: u32,
187 anchor_context: Option<&str>,
188 new_lines: &[NewLine],
189 file_still_exists: bool,
190) -> AnchorOutcome {
191 if !file_still_exists {
192 return AnchorOutcome::Orphaned;
193 }
194
195 // 1. The line survived at a known position.
196 if let Some(l) = new_lines.iter().find(|l| l.from_old == Some(old_line)) {
197 // Its content may still have changed (whitespace, a rewrite).
198 if let Some(ctx) = anchor_context {
199 if l.content != ctx {
200 return AnchorOutcome::Outdated;
201 }
202 }
203 return if l.number == old_line {
204 AnchorOutcome::Unchanged
205 } else {
206 AnchorOutcome::Moved { new_line: l.number }
207 };
208 }
209
210 // 2. The mapping is gone, but identical text still exists — the line was
211 // moved rather than edited. Only trust this when the content is
212 // distinctive: matching on a blank line or a lone `}` would anchor the
213 // comment somewhere arbitrary, which is worse than admitting it is
214 // outdated.
215 if let Some(ctx) = anchor_context.filter(|c| is_distinctive(c)) {
216 let matches: Vec<&NewLine> = new_lines.iter().filter(|l| l.content == ctx).collect();
217 if matches.len() == 1 {
218 return AnchorOutcome::Moved {
219 new_line: matches[0].number,
220 };
221 }
222 }
223
224 // 3. The line is gone from the file.
225 AnchorOutcome::Outdated
226}
227
228/// Whether a line's content is specific enough to re-anchor on.
229fn is_distinctive(s: &str) -> bool {
230 let t = s.trim();
231 // Structural punctuation and blank lines repeat throughout a file.
232 t.len() >= 4 && t.chars().any(|c| c.is_alphanumeric())
233}
234
235/// Build the old→new line mapping for a file across a rewrite.
236///
237/// [`rebase_anchor`] needs to know, for each line of the new file, which line of
238/// the old file it came from. A diff's hunks only carry that for the lines near
239/// a change, and a comment can sit anywhere — so the mapping is computed over
240/// the whole file rather than read out of a hunk.
241///
242/// Uses `similar`'s line diff, the same algorithm `df-store` renders diffs with,
243/// so the mapping a comment is rebased through agrees with the diff a reviewer
244/// is looking at.
245pub fn line_map(old: &str, new: &str) -> Vec<NewLine> {
246 use similar::{ChangeTag, TextDiff};
247
248 let diff = TextDiff::from_lines(old, new);
249 let mut out = Vec::new();
250
251 for change in diff.iter_all_changes() {
252 // Only lines that exist in the new file get an entry; a deleted line is
253 // absent from the mapping, which is exactly what makes `rebase_anchor`
254 // fall through to its content search.
255 let Some(new_index) = change.new_index() else {
256 continue;
257 };
258 out.push(NewLine {
259 number: new_index as u32 + 1,
260 content: change.value().trim_end_matches('\n').to_owned(),
261 from_old: match change.tag() {
262 // An inserted line came from nowhere.
263 ChangeTag::Insert => None,
264 _ => change.old_index().map(|i| i as u32 + 1),
265 },
266 });
267 }
268
269 out
270}
271
272#[cfg(test)]
273mod tests {
274 use super::*;
275
276 fn commit(rev: &str, change: &str, parents: &[&str]) -> IndexedCommit {
277 IndexedCommit {
278 rev: rev.into(),
279 change_id: ChangeId::parse(change),
280 parents: parents.iter().map(|s| s.to_string()).collect(),
281 author_name: "A".into(),
282 author_email: "a@b.c".into(),
283 authored_at: chrono::Utc::now(),
284 message: "msg".into(),
285 conflicted: false,
286 conflict_sides: vec![],
287 conflict_bases: vec![],
288 }
289 }
290
291 /// 32 chars in the reverse-hex alphabet.
292 fn cid(seed: char) -> String {
293 std::iter::repeat(seed).take(32).collect()
294 }
295
296 // ─── stacks ──────────────────────────────────────────────────────────────
297
298 #[test]
299 fn a_linear_chain_produces_a_chain_of_edges() {
300 let (a, b, c) = (cid('k'), cid('l'), cid('m'));
301 let commits = vec![
302 commit("r1", &a, &[]),
303 commit("r2", &b, &["r1"]),
304 commit("r3", &c, &["r2"]),
305 ];
306 let edges = stack_edges(&commits, &HashSet::new());
307
308 assert!(edges.contains(&StackEdge { parent: a.clone(), child: b.clone() }));
309 assert!(edges.contains(&StackEdge { parent: b, child: c }));
310 assert_eq!(edges.len(), 2);
311 }
312
313 #[test]
314 fn merged_changes_do_not_appear_in_stacks() {
315 let (a, b) = (cid('k'), cid('l'));
316 let commits = vec![commit("r1", &a, &[]), commit("r2", &b, &["r1"])];
317
318 let mut merged = HashSet::new();
319 merged.insert(a);
320
321 let edges = stack_edges(&commits, &merged);
322 assert!(
323 edges.is_empty(),
324 "a landed parent must not anchor a stack: {edges:?}"
325 );
326 }
327
328 #[test]
329 fn a_stack_is_not_severed_by_a_landed_change_in_the_middle() {
330 // a (merged) <- b (merged) <- c: c should still connect upward to
331 // nothing, but a <- b <- c with only b merged must yield a -> c.
332 let (a, b, c) = (cid('k'), cid('l'), cid('m'));
333 let commits = vec![
334 commit("r1", &a, &[]),
335 commit("r2", &b, &["r1"]),
336 commit("r3", &c, &["r2"]),
337 ];
338 let mut merged = HashSet::new();
339 merged.insert(b.clone());
340
341 let edges = stack_edges(&commits, &merged);
342 assert!(
343 edges.contains(&StackEdge { parent: a, child: c }),
344 "walk must pass through the landed change: {edges:?}"
345 );
346 }
347
348 #[test]
349 fn commits_without_a_change_id_do_not_produce_edges() {
350 let a = cid('k');
351 let mut plain = commit("r1", &a, &[]);
352 plain.change_id = None;
353 let commits = vec![plain, commit("r2", &cid('l'), &["r1"])];
354
355 let edges = stack_edges(&commits, &HashSet::new());
356 assert!(edges.is_empty(), "got {edges:?}");
357 }
358
359 #[test]
360 fn is_idempotent_over_repeated_runs() {
361 // The indexer must be re-runnable (spec §4).
362 let commits = vec![
363 commit("r1", &cid('k'), &[]),
364 commit("r2", &cid('l'), &["r1"]),
365 ];
366 let first = stack_edges(&commits, &HashSet::new());
367 let second = stack_edges(&commits, &HashSet::new());
368 assert_eq!(first, second);
369 }
370
371 #[test]
372 fn a_cycle_does_not_hang_the_walk() {
373 // Impossible in Git, but the indexer must not be the thing that hangs
374 // if the graph is ever malformed.
375 let (a, b) = (cid('k'), cid('l'));
376 let commits = vec![
377 commit("r1", &a, &["r2"]),
378 commit("r2", &b, &["r1"]),
379 ];
380 let _ = stack_edges(&commits, &HashSet::new());
381 }
382
383 #[test]
384 fn a_merge_commit_links_to_both_parents() {
385 let (a, b, m) = (cid('k'), cid('l'), cid('m'));
386 let commits = vec![
387 commit("r1", &a, &[]),
388 commit("r2", &b, &[]),
389 commit("r3", &m, &["r1", "r2"]),
390 ];
391 let edges = stack_edges(&commits, &HashSet::new());
392 assert!(edges.contains(&StackEdge { parent: a, child: m.clone() }));
393 assert!(edges.contains(&StackEdge { parent: b, child: m }));
394 }
395
396 // ─── state ───────────────────────────────────────────────────────────────
397
398 #[test]
399 fn indexing_never_overwrites_draft() {
400 // The decided behaviour: draft is the author's, set in the UI.
401 assert_eq!(next_state(ChangeState::Draft, true), ChangeState::Draft);
402 assert_eq!(next_state(ChangeState::Draft, false), ChangeState::Draft);
403 }
404
405 #[test]
406 fn indexing_never_reopens_an_abandoned_change() {
407 assert_eq!(
408 next_state(ChangeState::Abandoned, false),
409 ChangeState::Abandoned
410 );
411 assert_eq!(
412 next_state(ChangeState::Abandoned, true),
413 ChangeState::Abandoned
414 );
415 }
416
417 #[test]
418 fn a_change_on_the_target_bookmark_becomes_merged() {
419 assert_eq!(next_state(ChangeState::Open, true), ChangeState::Merged);
420 }
421
422 #[test]
423 fn a_rewound_bookmark_reopens_a_merged_change() {
424 assert_eq!(next_state(ChangeState::Merged, false), ChangeState::Open);
425 }
426
427 // ─── anchor rebasing (spec §5) ───────────────────────────────────────────
428
429 fn lines(spec: &[(u32, &str, Option<u32>)]) -> Vec<NewLine> {
430 spec.iter()
431 .map(|(n, c, f)| NewLine {
432 number: *n,
433 content: (*c).to_string(),
434 from_old: *f,
435 })
436 .collect()
437 }
438
439 #[test]
440 fn an_unchanged_line_stays_current() {
441 let new = lines(&[(1, "let x = 1;", Some(1))]);
442 assert_eq!(
443 rebase_anchor(1, Some("let x = 1;"), &new, true),
444 AnchorOutcome::Unchanged
445 );
446 }
447
448 #[test]
449 fn a_line_pushed_down_by_an_insertion_moves() {
450 // Someone added a line above; the comment follows its line.
451 let new = lines(&[
452 (1, "// new comment", None),
453 (2, "let x = 1;", Some(1)),
454 ]);
455 assert_eq!(
456 rebase_anchor(1, Some("let x = 1;"), &new, true),
457 AnchorOutcome::Moved { new_line: 2 }
458 );
459 }
460
461 #[test]
462 fn an_edited_line_becomes_outdated() {
463 let new = lines(&[(1, "let x = 2;", Some(1))]);
464 assert_eq!(
465 rebase_anchor(1, Some("let x = 1;"), &new, true),
466 AnchorOutcome::Outdated
467 );
468 }
469
470 #[test]
471 fn a_deleted_file_orphans_the_comment() {
472 assert_eq!(
473 rebase_anchor(1, Some("anything"), &[], false),
474 AnchorOutcome::Orphaned
475 );
476 }
477
478 #[test]
479 fn a_deleted_line_becomes_outdated_not_orphaned() {
480 // The file still exists, so the comment belongs in the diff view marked
481 // outdated rather than being exiled to the timeline.
482 let new = lines(&[(1, "something else entirely", None)]);
483 assert_eq!(
484 rebase_anchor(5, Some("let x = 1;"), &new, true),
485 AnchorOutcome::Outdated
486 );
487 }
488
489 #[test]
490 fn a_moved_line_is_found_by_its_distinctive_content() {
491 // A rebase reordered the file; the mapping is gone but the text is
492 // unique, so the comment follows it.
493 let new = lines(&[
494 (1, "unrelated", None),
495 (2, "fn interesting_function() {", None),
496 ]);
497 assert_eq!(
498 rebase_anchor(50, Some("fn interesting_function() {"), &new, true),
499 AnchorOutcome::Moved { new_line: 2 }
500 );
501 }
502
503 #[test]
504 fn ambiguous_content_does_not_move_the_anchor() {
505 // Two identical lines: guessing would put the comment in the wrong
506 // place, which is worse than marking it outdated.
507 let new = lines(&[
508 (1, " return None;", None),
509 (2, " return None;", None),
510 ]);
511 assert_eq!(
512 rebase_anchor(9, Some(" return None;"), &new, true),
513 AnchorOutcome::Outdated
514 );
515 }
516
517 #[test]
518 fn structural_lines_are_not_used_to_re_anchor() {
519 // Matching on `}` or a blank line would anchor almost anywhere.
520 let new = lines(&[(1, "}", None)]);
521 assert_eq!(
522 rebase_anchor(9, Some("}"), &new, true),
523 AnchorOutcome::Outdated
524 );
525 assert_eq!(
526 rebase_anchor(9, Some(" "), &new, true),
527 AnchorOutcome::Outdated
528 );
529 }
530
531 #[test]
532 fn whitespace_only_reindentation_marks_outdated_not_moved() {
533 // The line is the same code, but its text changed. Marking it outdated
534 // keeps the original text visible to the reviewer (spec §5 step 4).
535 let new = lines(&[(1, " let x = 1;", Some(1))]);
536 assert_eq!(
537 rebase_anchor(1, Some("let x = 1;"), &new, true),
538 AnchorOutcome::Outdated
539 );
540 }
541
542 #[test]
543 fn a_comment_with_no_stored_context_follows_the_line_mapping() {
544 // Older comments predate anchor_context; they still rebase by position.
545 let new = lines(&[(7, "whatever", Some(3))]);
546 assert_eq!(
547 rebase_anchor(3, None, &new, true),
548 AnchorOutcome::Moved { new_line: 7 }
549 );
550 }
551
552 #[test]
553 fn survives_five_successive_rewrites() {
554 // Spec §5: "a change that is rewritten five times".
555 let mut line = 10u32;
556 let context = "fn the_function_under_review() {";
557
558 for shift in 1..=5u32 {
559 let new = lines(&[(line + shift, context, Some(line))]);
560 match rebase_anchor(line, Some(context), &new, true) {
561 AnchorOutcome::Moved { new_line } => line = new_line,
562 other => panic!("rewrite {shift} lost the anchor: {other:?}"),
563 }
564 }
565 assert_eq!(line, 25, "anchor should have tracked every shift");
566 }
567
568 // ─── line mapping ────────────────────────────────────────────────────────
569
570 #[test]
571 fn line_map_carries_unchanged_lines_through() {
572 let m = line_map("a\nb\nc\n", "a\nb\nc\n");
573 assert_eq!(m.len(), 3);
574 for (i, l) in m.iter().enumerate() {
575 assert_eq!(l.number, i as u32 + 1);
576 assert_eq!(l.from_old, Some(i as u32 + 1), "identical files map 1:1");
577 }
578 }
579
580 #[test]
581 fn an_inserted_line_shifts_the_ones_below_it() {
582 let m = line_map("a\nb\n", "new\na\nb\n");
583 assert_eq!(m[0].from_old, None, "the inserted line came from nowhere");
584 assert_eq!(m[1].from_old, Some(1));
585 assert_eq!(m[1].number, 2, "`a` moved from line 1 to line 2");
586 }
587
588 #[test]
589 fn a_deleted_line_is_absent_from_the_mapping() {
590 let m = line_map("a\nb\nc\n", "a\nc\n");
591 assert!(
592 !m.iter().any(|l| l.from_old == Some(2)),
593 "the deleted line must not appear: {m:?}"
594 );
595 assert_eq!(m.iter().find(|l| l.content == "c").unwrap().from_old, Some(3));
596 }
597
598 /// The end-to-end property this exists for: a comment on a line survives an
599 /// insertion above it.
600 #[test]
601 fn a_comment_follows_its_line_through_a_real_rewrite() {
602 let old = "fn a() {}\nfn the_reviewed_function() {}\nfn c() {}\n";
603 let new = "use std::io;\n\nfn a() {}\nfn the_reviewed_function() {}\nfn c() {}\n";
604 let m = line_map(old, new);
605 assert_eq!(
606 rebase_anchor(2, Some("fn the_reviewed_function() {}"), &m, true),
607 AnchorOutcome::Moved { new_line: 4 }
608 );
609 }
610
611 #[test]
612 fn a_file_emptied_by_a_rewrite_outdates_rather_than_panicking() {
613 let m = line_map("a\nb\n", "");
614 assert_eq!(rebase_anchor(1, Some("a"), &m, true), AnchorOutcome::Outdated);
615 }
616}

616 lines · Rust