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

objects/util/line_diff/
visit.rs
