heddle-objects 0.15.0

An AI-native version control system
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

// SPDX-License-Identifier: Apache-2.0
//! Caller-scratch layout for line offsets, Myers V arrays, and the conquer stack.

use std::mem::{align_of, size_of};

use super::super::budget::{BudgetExceeded, ResourceKind};
use super::scan::LineOff;

#[repr(C)]
#[derive(Clone, Copy)]
pub(super) struct ConquerJob {
    pub old_lo: u32,
    pub old_hi: u32,
    pub new_lo: u32,
    pub new_hi: u32,
    pub kind: u8,
    pub eq_old: u32,
    pub eq_new: u32,
    pub eq_len: u32,
}

pub(super) const JOB_RANGE: u8 = 0;
pub(super) const JOB_EQUAL: u8 = 1;

pub fn max_scratch_align() -> usize {
    align_of::<LineOff>()
        .max(align_of::<usize>())
        .max(align_of::<ConquerJob>())
}

pub fn scratch_bytes_for_line_counts(old_lines: usize, new_lines: usize) -> usize {
    let (needed, _) = layout_sizes(old_lines, new_lines);
    needed.saturating_add(max_scratch_align().saturating_sub(1))
}

#[cfg(test)]
pub(super) fn aligned_layout_bytes(old_lines: usize, new_lines: usize) -> usize {
    let (needed, _) = layout_sizes(old_lines, new_lines);
    needed
}

/// Shift `scratch` so the returned suffix starts at [`max_scratch_align`].
///
/// The pad is computed from the actual pointer, not from a layout that
/// assumed the slice was already aligned.
pub(super) fn align_scratch(scratch: &mut [u8]) -> Result<(&mut [u8], usize), BudgetExceeded> {
    let align = max_scratch_align();
    let addr = scratch.as_mut_ptr() as usize;
    let pad = if align <= 1 {
        0
    } else {
        (align - (addr % align)) % align
    };
    if pad > scratch.len() {
        return Err(BudgetExceeded {
            kind: ResourceKind::ScratchBytes,
            limit: scratch.len() as u64,
            needed: (pad as u64).saturating_add(1),
        });
    }
    Ok((&mut scratch[pad..], pad))
}

pub(super) struct ScratchLayout {
    pub old_off: usize,
    pub new_off: usize,
    pub vf: usize,
    pub vb: usize,
    pub jobs: usize,
    pub old_off_bytes: usize,
    pub new_off_bytes: usize,
    pub vf_bytes: usize,
    pub vb_bytes: usize,
    pub jobs_bytes: usize,
}

pub(super) fn layout_sizes(old_lines: usize, new_lines: usize) -> (usize, ScratchLayout) {
    let max_d = max_d(old_lines, new_lines);
    let v_len = 2 * max_d + 1;
    let job_cap = old_lines.saturating_add(new_lines).saturating_add(8);

    let mut cursor = 0usize;
    let old_off = align_up(cursor, align_of::<LineOff>());
    let old_off_bytes = old_lines.saturating_mul(size_of::<LineOff>());
    cursor = old_off.saturating_add(old_off_bytes);

    let new_off = align_up(cursor, align_of::<LineOff>());
    let new_off_bytes = new_lines.saturating_mul(size_of::<LineOff>());
    cursor = new_off.saturating_add(new_off_bytes);

    let vf = align_up(cursor, align_of::<usize>());
    let vf_bytes = v_len.saturating_mul(size_of::<usize>());
    cursor = vf.saturating_add(vf_bytes);

    let vb = align_up(cursor, align_of::<usize>());
    let vb_bytes = v_len.saturating_mul(size_of::<usize>());
    cursor = vb.saturating_add(vb_bytes);

    let jobs = align_up(cursor, align_of::<ConquerJob>());
    let jobs_bytes = job_cap.saturating_mul(size_of::<ConquerJob>());
    cursor = jobs.saturating_add(jobs_bytes);

    (
        cursor,
        ScratchLayout {
            old_off,
            new_off,
            vf,
            vb,
            jobs,
            old_off_bytes,
            new_off_bytes,
            vf_bytes,
            vb_bytes,
            jobs_bytes,
        },
    )
}

pub(super) fn max_d(old_lines: usize, new_lines: usize) -> usize {
    old_lines
        .saturating_add(new_lines)
        .div_ceil(2)
        .saturating_add(1)
}

fn align_up(value: usize, align: usize) -> usize {
    if align <= 1 {
        return value;
    }
    let rem = value % align;
    if rem == 0 {
        value
    } else {
        value + (align - rem)
    }
}

pub(super) fn require_scratch(scratch_len: usize, needed: usize) -> Result<(), BudgetExceeded> {
    if needed > scratch_len {
        return Err(BudgetExceeded {
            kind: ResourceKind::ScratchBytes,
            limit: scratch_len as u64,
            needed: needed as u64,
        });
    }
    Ok(())
}