objects/worktree/
source_line_map.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Shared capture position maps using the existing Histogram diff engine.
3
4use crate::object::{
5    Blob,
6    source_target::{SourceLineEdit, SourceLineEditMap, SourceTargetError},
7};
8
9#[derive(Clone, Debug, PartialEq, Eq)]
10pub enum SourceLineMapBuild {
11    Ready(SourceLineEditMap),
12    UnsupportedEncoding,
13    BudgetExceeded,
14}
15
16/// Build once for an old/new blob pair, regardless of how many ranges refer to
17/// that file. Limits apply before parsing and before admitting the edit map.
18/// No elapsed-time fallback changes the resulting coordinate decisions.
19pub fn source_line_edit_map(
20    old: &Blob,
21    new: &Blob,
22    max_bytes: usize,
23    max_edits: usize,
24) -> Result<SourceLineMapBuild, SourceTargetError> {
25    if old.content().len().saturating_add(new.content().len()) > max_bytes {
26        return Ok(SourceLineMapBuild::BudgetExceeded);
27    }
28    let (Some(old_text), Some(new_text)) = (old.content_str(), new.content_str()) else {
29        return Ok(SourceLineMapBuild::UnsupportedEncoding);
30    };
31    let diff = similar::TextDiff::configure()
32        .algorithm(similar::Algorithm::Histogram)
33        .diff_lines(old_text, new_text);
34    let mut edits: Vec<SourceLineEdit> = Vec::new();
35    for operation in diff.ops() {
36        if operation.tag() == similar::DiffTag::Equal {
37            continue;
38        }
39        let old_range = operation.old_range();
40        let new_range = operation.new_range();
41        let edit = SourceLineEdit {
42            old_start: line_count(old_range.start)?,
43            old_end: line_count(old_range.end)?,
44            new_start: line_count(new_range.start)?,
45            new_end: line_count(new_range.end)?,
46        };
47        if let Some(previous) = edits.last_mut()
48            && previous.old_end == edit.old_start
49            && previous.new_end == edit.new_start
50        {
51            previous.old_end = edit.old_end;
52            previous.new_end = edit.new_end;
53        } else {
54            if edits.len() >= max_edits.min(65_536) {
55                return Ok(SourceLineMapBuild::BudgetExceeded);
56            }
57            edits.push(edit);
58        }
59    }
60    Ok(SourceLineMapBuild::Ready(SourceLineEditMap::new(
61        line_count(diff.old_len())?,
62        line_count(diff.new_len())?,
63        edits,
64    )?))
65}
66
67fn line_count(count: usize) -> Result<u32, SourceTargetError> {
68    u32::try_from(count)
69        .map_err(|_| SourceTargetError::Invalid("source exceeds line coordinate range".into()))
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75    use crate::object::source_target::{SourceAffinity, SourceLineRange, SourceRangeProjection};
76
77    #[test]
78    fn actual_text_diff_tracks_insertions_and_preserves_original_line_content() {
79        let old = Blob::new(b"head\nselected one\nselected two\ntail\n".to_vec());
80        let new = Blob::new(b"new head\nhead\nselected one\nselected two\ntail\n".to_vec());
81        let SourceLineMapBuild::Ready(map) =
82            source_line_edit_map(&old, &new, 1024, 10).expect("map")
83        else {
84            panic!("small UTF-8 sources must have a map");
85        };
86        assert_eq!(map.edits().len(), 1);
87        let range = SourceLineRange {
88            start: 1,
89            end: 3,
90            start_affinity: SourceAffinity::After,
91            end_affinity: SourceAffinity::Before,
92        };
93        assert_eq!(
94            map.project(range).expect("project"),
95            SourceRangeProjection::Resolved {
96                range: SourceLineRange {
97                    start: 2,
98                    end: 4,
99                    ..range
100                },
101                changed: false,
102            }
103        );
104        let old_lines = old.content_str().expect("text").lines().collect::<Vec<_>>();
105        let new_lines = new.content_str().expect("text").lines().collect::<Vec<_>>();
106        assert_eq!(&old_lines[1..3], &new_lines[2..4]);
107    }
108
109    #[test]
110    fn source_limits_and_binary_content_are_explicit() {
111        let old = Blob::new(b"before\n".to_vec());
112        let new = Blob::new(b"after\n".to_vec());
113        assert_eq!(
114            source_line_edit_map(&old, &new, 1, 10).expect("budget"),
115            SourceLineMapBuild::BudgetExceeded
116        );
117        assert_eq!(
118            source_line_edit_map(&old, &new, 1024, 0).expect("edit budget"),
119            SourceLineMapBuild::BudgetExceeded
120        );
121        assert_eq!(
122            source_line_edit_map(&old, &Blob::new(vec![0xff]), 1024, 10).expect("binary"),
123            SourceLineMapBuild::UnsupportedEncoding
124        );
125        let empty = Blob::new(Vec::new());
126        let SourceLineMapBuild::Ready(map) =
127            source_line_edit_map(&empty, &old, 1024, 10).expect("empty source")
128        else {
129            panic!("new text is supported");
130        };
131        assert_eq!(
132            map.edits(),
133            &[SourceLineEdit {
134                old_start: 0,
135                old_end: 0,
136                new_start: 0,
137                new_end: 1
138            }]
139        );
140    }
141}
objects/worktree/source_line_map.rs

objects/worktree/
source_line_map.rs
