objects/util/line_diff/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Scratch-budgeted equal-run LCS used by native blame and Git-overlay blame.
3
4mod compact;
5mod emit;
6mod myers;
7mod myers_search;
8mod scan;
9mod scratch;
10mod visit;
11
12#[cfg(test)]
13mod tests;
14
15use super::budget::{BudgetExceeded, ResourceUsage};
16
17pub use scratch::scratch_bytes_for_line_counts;
18pub use visit::visit_lcs_equal_runs;
19
20/// Split UTF-8 content into the same logical lines used by blame.
21pub fn split_text_lines(bytes: &[u8]) -> Option<Vec<String>> {
22    let content = std::str::from_utf8(bytes).ok()?;
23    Some(content.lines().map(str::to_string).collect())
24}
25
26/// Admission caps for one equal-run LCS visit.
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub struct LineDiffLimits {
29    pub scratch_bytes: u64,
30    pub max_lines: u64,
31    pub max_work: u64,
32}
33
34impl LineDiffLimits {
35    pub fn unlimited() -> Self {
36        Self {
37            scratch_bytes: u64::MAX,
38            max_lines: u64::MAX,
39            max_work: u64::MAX,
40        }
41    }
42
43    pub fn budget(self, scratch_len: usize) -> crate::util::ResourceBudget {
44        crate::util::ResourceBudget::new(crate::util::ResourceUsage {
45            scratch_bytes: self.scratch_bytes.min(scratch_len as u64),
46            lines: self.max_lines,
47            work: self.max_work,
48            states: u64::MAX,
49            decoded_bytes: u64::MAX,
50        })
51    }
52}
53
54/// One inclusive-length run of equal lines in Myers order.
55#[derive(Debug, Clone, Copy, PartialEq, Eq)]
56pub struct EqualRun {
57    pub old_start: usize,
58    pub new_start: usize,
59    pub len: usize,
60}
61
62/// Typed LCS failure. [`BudgetExceeded`] is distinct from UTF-8 rejection
63/// and from a visitor that cancelled.
64#[derive(Debug)]
65pub enum LineDiffError<E = std::convert::Infallible> {
66    InvalidUtf8,
67    BudgetExceeded(BudgetExceeded),
68    Visitor(E),
69}
70
71impl<E> LineDiffError<E> {
72    pub fn from_budget(error: BudgetExceeded) -> Self {
73        Self::BudgetExceeded(error)
74    }
75}
76
77impl<E: std::fmt::Display> std::fmt::Display for LineDiffError<E> {
78    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
79        match self {
80            Self::InvalidUtf8 => f.write_str("input is not valid UTF-8"),
81            Self::BudgetExceeded(error) => write!(f, "{error}"),
82            Self::Visitor(error) => write!(f, "lcs visitor: {error}"),
83        }
84    }
85}
86
87impl<E: std::error::Error + 'static> std::error::Error for LineDiffError<E> {
88    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
89        match self {
90            Self::BudgetExceeded(error) => Some(error),
91            Self::Visitor(error) => Some(error),
92            Self::InvalidUtf8 => None,
93        }
94    }
95}
96
97impl<E> From<BudgetExceeded> for LineDiffError<E> {
98    fn from(error: BudgetExceeded) -> Self {
99        Self::BudgetExceeded(error)
100    }
101}
102
103/// Successful visit: equal runs were emitted and usage is observable.
104pub type LcsVisitResult<E> = Result<ResourceUsage, LineDiffError<E>>;
objects/util/line_diff/mod.rs

objects/util/line_diff/
mod.rs
