objects/util/line_diff/
visit.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Public visitor entry for scratch-budgeted equal-run LCS.
3
4use std::mem::align_of;
5
6use super::{
7    super::budget::{ResourceBudget, ResourceKind},
8    EqualRun, LcsVisitResult, LineDiffError,
9    myers::{LineView, emit_equal_runs},
10    scan::{LineOff, count_text_lines, fill_line_offsets},
11    scratch::{ConquerJob, align_scratch, layout_sizes, require_scratch},
12};
13
14/// Visit equal index ranges in deterministic Myers order.
15///
16/// Line scanning writes offsets into `scratch`. The algorithm never builds
17/// `Vec<String>` inputs or a `Vec<(usize, usize)>` match set. Work is the
18/// number of Myers line comparisons actually performed. A visitor `Err`
19/// stops promptly.
20pub fn visit_lcs_equal_runs<E>(
21    old_bytes: &[u8],
22    new_bytes: &[u8],
23    scratch: &mut [u8],
24    budget: &mut ResourceBudget,
25    visit: impl FnMut(EqualRun) -> Result<(), E>,
26) -> LcsVisitResult<E> {
27    let old_lines = count_text_lines(old_bytes).map_err(|_| LineDiffError::InvalidUtf8)?;
28    let new_lines = count_text_lines(new_bytes).map_err(|_| LineDiffError::InvalidUtf8)?;
29    budget.require(ResourceKind::Lines, old_lines as u64)?;
30    budget.require(ResourceKind::Lines, new_lines as u64)?;
31
32    let (aligned, pad) = align_scratch(scratch)?;
33    let (needed, layout) = layout_sizes(old_lines, new_lines);
34    budget.require(ResourceKind::ScratchBytes, (pad + needed) as u64)?;
35    require_scratch(aligned.len(), needed)?;
36    let scratch = &mut aligned[..needed];
37    scratch.fill(0);
38
39    let parts = unsafe { partition(scratch, &layout)? };
40    let filled_old =
41        fill_line_offsets(old_bytes, parts.old_offs).map_err(|_| LineDiffError::InvalidUtf8)?;
42    let filled_new =
43        fill_line_offsets(new_bytes, parts.new_offs).map_err(|_| LineDiffError::InvalidUtf8)?;
44    if filled_old != old_lines || filled_new != new_lines {
45        return Err(LineDiffError::InvalidUtf8);
46    }
47
48    emit_equal_runs(
49        LineView {
50            bytes: old_bytes,
51            offs: parts.old_offs,
52        },
53        LineView {
54            bytes: new_bytes,
55            offs: parts.new_offs,
56        },
57        parts.vf,
58        parts.vb,
59        parts.jobs,
60        budget,
61        visit,
62    )?;
63    Ok(budget.used())
64}
65
66struct ScratchParts<'a> {
67    old_offs: &'a mut [LineOff],
68    new_offs: &'a mut [LineOff],
69    vf: &'a mut [usize],
70    vb: &'a mut [usize],
71    jobs: &'a mut [ConquerJob],
72}
73
74/// Split caller scratch into disjoint typed regions.
75///
76/// Safety: `scratch` starts at [`super::scratch::max_scratch_align`] (proven
77/// from the actual pointer by [`align_scratch`]). `layout` offsets were
78/// produced by [`layout_sizes`] relative to that aligned base, do not overlap,
79/// and each region start is checked against `align_of::<T>()` before the
80/// cast. A misaligned region is a typed [`super::LineDiffError::BudgetExceeded`],
81/// not UB.
82unsafe fn partition<'a>(
83    scratch: &'a mut [u8],
84    layout: &super::scratch::ScratchLayout,
85) -> Result<ScratchParts<'a>, super::super::budget::BudgetExceeded> {
86    let base = scratch.as_mut_ptr();
87    unsafe {
88        Ok(ScratchParts {
89            old_offs: raw_slice(base, layout.old_off, layout.old_off_bytes)?,
90            new_offs: raw_slice(base, layout.new_off, layout.new_off_bytes)?,
91            vf: raw_slice(base, layout.vf, layout.vf_bytes)?,
92            vb: raw_slice(base, layout.vb, layout.vb_bytes)?,
93            jobs: raw_slice(base, layout.jobs, layout.jobs_bytes)?,
94        })
95    }
96}
97
98unsafe fn raw_slice<'a, T>(
99    base: *mut u8,
100    start: usize,
101    bytes: usize,
102) -> Result<&'a mut [T], super::super::budget::BudgetExceeded> {
103    let ptr = unsafe { base.add(start) };
104    let addr = ptr as usize;
105    if !addr.is_multiple_of(align_of::<T>()) {
106        return Err(super::super::budget::BudgetExceeded {
107            kind: ResourceKind::ScratchBytes,
108            limit: addr as u64,
109            needed: align_of::<T>() as u64,
110        });
111    }
112    let count = if std::mem::size_of::<T>() == 0 {
113        0
114    } else {
115        bytes / std::mem::size_of::<T>()
116    };
117    Ok(unsafe { std::slice::from_raw_parts_mut(ptr.cast::<T>(), count) })
118}
objects/util/line_diff/visit.rs

objects/util/line_diff/
visit.rs
