Build CRDT ops using move-aware matching.
(ctx: &RecipeContext<'_>)
| 48 | |
| 49 | /// Build CRDT ops using move-aware matching. |
| 50 | pub fn build_ops(ctx: &RecipeContext<'_>) -> (FileOps, CrdtBuildStats) { |
| 51 | // Fall back to the in-place recipe when we have no CRDT state to |
| 52 | // match against. Pure move detection needs the existing branches. |
| 53 | let existing_branches = match ctx.existing_branches { |
| 54 | Some(b) if !b.is_empty() => b, |
| 55 | _ => return super::in_place_edit::build_ops(ctx), |
| 56 | }; |
| 57 | |
| 58 | let _placeholder_change = NodeId::new(0); |
| 59 | let placeholder_trunk = TrunkId::new(NodeId::new(0), 0); |
| 60 | |
| 61 | // Tokenize. |
| 62 | let old_lines: Vec<&[u8]> = ctx.old_content.split_inclusive(|&b| b == b'\n').collect(); |
| 63 | let new_lines: Vec<&[u8]> = ctx.new_content.split_inclusive(|&b| b == b'\n').collect(); |
| 64 | |
| 65 | // Index old lines by content hash so we can find moves in O(N). |
| 66 | let mut old_idx = LineHashIndex::from_lines(&old_lines); |
| 67 | // Track which old positions got consumed (for the Delete sweep). |
| 68 | let mut matched_old: Vec<bool> = vec![false; old_lines.len()]; |
| 69 | |
| 70 | // For each new line, find an old position with matching content. |
| 71 | // `new_to_old[i] = Some(j)` means new_line[i] was old_line[j]. |
| 72 | let mut new_to_old: Vec<Option<usize>> = Vec::with_capacity(new_lines.len()); |
| 73 | for new_line in &new_lines { |
| 74 | match old_idx.consume(new_line) { |
| 75 | Some(oi) => { |
| 76 | matched_old[oi] = true; |
| 77 | new_to_old.push(Some(oi)); |
| 78 | } |
| 79 | None => new_to_old.push(None), |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | // Build line ops. |
| 84 | let mut next_branch_idx: u32 = 0; |
| 85 | let mut alloc_branch = || { |
| 86 | let id = BranchId::new(NodeId::new(0), next_branch_idx); |
| 87 | next_branch_idx += 1; |
| 88 | id |
| 89 | }; |
| 90 | let mut next_leaf_idx: u32 = 0; |
| 91 | let mut alloc_leaf = || { |
| 92 | let id = crate::crdt::LeafId::new(NodeId::new(0), next_leaf_idx); |
| 93 | next_leaf_idx += 1; |
| 94 | id |
| 95 | }; |
| 96 | |
| 97 | let mut file_ops = BuilderFileOps::new(placeholder_trunk, ctx.path.to_string(), None); |
| 98 | let mut stats = CrdtBuildStats::new(); |
| 99 | let mut prev_emitted: Option<BranchId> = None; |
| 100 | |
| 101 | for (new_idx, &maybe_old) in new_to_old.iter().enumerate() { |
| 102 | match maybe_old { |
| 103 | Some(old_idx) if old_idx < existing_branches.len() => { |
| 104 | let branch_id = existing_branches[old_idx]; |
| 105 | |
| 106 | // Decide between "Equal" (no op) and "Reparent" (move). |
| 107 | // |
no test coverage detected