OXYGENHUB
# 8b3c9b2ba502 oxygen / crates / oxy-core / src / lines.rs
7.8 KiB · Rust · last changed First commit: 12 s and 2.1 GB on the Linux tree (refs #41) 1 month ago source blame history raw
1 
//! The lines of an insert (spec §7.4) held as one buffer and where each
2 
//! line ends, shared by the change and the file graph it builds: a tree of
3 
//! forty million lines is then a few allocations per insert, not one per
4 
//! line, and a graph's atoms point into their insert's buffer rather than
5 
//! copying it.
6
7 
use std::sync::Arc;
8
9 
#[derive(Default, PartialEq, Eq, Hash)]
10 
struct Inner {
11 
    /// Shared with the file it was read from, when there was one.
12 
    buf: Arc<Vec<u8>>,
13 
    /// The end offset of each line in `buf`.
14 
    ends: Ends,
15 
}
16
17 
/// Line end offsets, four bytes each unless the buffer is over 4 GiB: a
18 
/// first commit of the Linux tree holds 36 million of them at once. Which
19 
/// form follows from the buffer's length alone, so equal lines compare
20 
/// equal.
21 
#[derive(PartialEq, Eq, Hash)]
22 
enum Ends {
23 
    Small(Vec<u32>),
24 
    Large(Vec<u64>),
25 
}
26
27 
impl Default for Ends {
28 
    fn default() -> Self {
29 
        Ends::Small(Vec::new())
30 
    }
31 
}
32
33 
impl Ends {
34 
    fn from_u64(ends: Vec<u64>, buf_len: usize) -> Ends {
35 
        if u32::try_from(buf_len).is_ok() {
36 
            Ends::Small(ends.into_iter().map(|e| e as u32).collect())
37 
        } else {
38 
            Ends::Large(ends)
39 
        }
40 
    }
41
42 
    fn len(&self) -> usize {
43 
        match self {
44 
            Ends::Small(v) => v.len(),
45 
            Ends::Large(v) => v.len(),
46 
        }
47 
    }
48
49 
    fn is_empty(&self) -> bool {
50 
        self.len() == 0
51 
    }
52
53 
    fn get(&self, i: usize) -> Option<usize> {
54 
        match self {
55 
            Ends::Small(v) => v.get(i).map(|&e| e as usize),
56 
            Ends::Large(v) => v.get(i).map(|&e| e as usize),
57 
        }
58 
    }
59 
}
60
61 
/// An insert's lines. Cloning is cheap: the buffer is shared.
62 
#[derive(Clone, Default, PartialEq, Eq, Hash)]
63 
pub struct Lines(Arc<Inner>);
64
65 
impl Lines {
66 
    /// Lines from their bytes, each keeping its terminator; a final
67 
    /// unterminated line is its own line (the rule of
68 
    /// [`crate::diff::split_lines`]).
69 
    pub fn split(content: &[u8]) -> Lines {
70 
        Lines::split_shared(Arc::new(content.to_vec()))
71 
    }
72
73 
    /// [`Lines::split`] of a buffer held elsewhere too (a file's content),
74 
    /// shared rather than copied.
75 
    pub fn split_shared(buf: Arc<Vec<u8>>) -> Lines {
76 
        let content = &buf[..];
77 
        // Counted first, so the offsets take exactly their room.
78 
        let newlines = memchr::memchr_iter(b'\n', content).count();
79 
        let unterminated = content.last().is_some_and(|&c| c != b'\n');
80 
        let n = newlines + usize::from(unterminated);
81 
        let ends_at = memchr::memchr_iter(b'\n', content)
82 
            .map(|i| i + 1)
83 
            .chain(unterminated.then_some(content.len()));
84 
        let ends = if u32::try_from(content.len()).is_ok() {
85 
            let mut v = Vec::with_capacity(n);
86 
            v.extend(ends_at.map(|e| e as u32));
87 
            Ends::Small(v)
88 
        } else {
89 
            let mut v = Vec::with_capacity(n);
90 
            v.extend(ends_at.map(|e| e as u64));
91 
            Ends::Large(v)
92 
        };
93 
        Lines(Arc::new(Inner { buf, ends }))
94 
    }
95
96 
    pub fn len(&self) -> usize {
97 
        self.0.ends.len()
98 
    }
99
100 
    pub fn is_empty(&self) -> bool {
101 
        self.0.ends.is_empty()
102 
    }
103
104 
    /// Line `i`, with its terminator.
105 
    pub fn get(&self, i: usize) -> Option<&[u8]> {
106 
        let end = self.0.ends.get(i)?;
107 
        let start = if i == 0 { 0 } else { self.0.ends.get(i - 1)? };
108 
        Some(&self.0.buf[start..end])
109 
    }
110
111 
    pub fn iter(&self) -> impl ExactSizeIterator<Item = &[u8]> + Clone + '_ {
112 
        (0..self.len()).map(move |i| self.get(i).unwrap())
113 
    }
114
115 
    /// Every line, joined: the bytes they were split from.
116 
    pub fn bytes(&self) -> &[u8] {
117 
        &self.0.buf
118 
    }
119
120 
    /// Whether splitting [`Lines::bytes`] by the line rule gives these lines
121 
    /// back: every line but the last ends in a newline and none holds
122 
    /// another. Every insert oxy makes is so, and such lines are stored as
123 
    /// their bytes alone (spec §7.4).
124 
    pub fn is_split_form(&self) -> bool {
125 
        let buf = &self.0.buf;
126 
        let mut start = 0usize;
127 
        for i in 0..self.0.ends.len() {
128 
            let end = self.0.ends.get(i).unwrap_or(start);
129 
            let line = &buf[start..end];
130 
            if line.is_empty() {
131 
                return false;
132 
            }
133 
            let last = i + 1 == self.0.ends.len();
134 
            let body = if last && !line.ends_with(b"\n") {
135 
                line
136 
            } else if line.ends_with(b"\n") {
137 
                &line[..line.len() - 1]
138 
            } else {
139 
                return false;
140 
            };
141 
            if body.contains(&b'\n') {
142 
                return false;
143 
            }
144 
            start = end;
145 
        }
146 
        true
147 
    }
148
149 
    /// Lines `range` as lines of their own.
150 
    pub fn slice(&self, range: std::ops::Range<usize>) -> Lines {
151 
        self.iter().skip(range.start).take(range.len()).collect()
152 
    }
153
154 
    /// The lines as owned vectors, for code that edits them one by one.
155 
    pub fn to_vec(&self) -> Vec<Vec<u8>> {
156 
        self.iter().map(<[u8]>::to_vec).collect()
157 
    }
158 
}
159
160 
impl std::ops::Index<usize> for Lines {
161 
    type Output = [u8];
162 
    fn index(&self, i: usize) -> &[u8] {
163 
        self.get(i).expect("line index out of range")
164 
    }
165 
}
166
167 
impl<'a> FromIterator<&'a [u8]> for Lines {
168 
    fn from_iter<I: IntoIterator<Item = &'a [u8]>>(iter: I) -> Lines {
169 
        let (mut buf, mut ends) = (Vec::new(), Vec::new());
170 
        for l in iter {
171 
            buf.extend_from_slice(l);
172 
            ends.push(buf.len() as u64);
173 
        }
174 
        let ends = Ends::from_u64(ends, buf.len());
175 
        Lines(Arc::new(Inner {
176 
            buf: Arc::new(buf),
177 
            ends,
178 
        }))
179 
    }
180 
}
181
182 
impl FromIterator<Vec<u8>> for Lines {
183 
    fn from_iter<I: IntoIterator<Item = Vec<u8>>>(iter: I) -> Lines {
184 
        let (mut buf, mut ends) = (Vec::new(), Vec::new());
185 
        for l in iter {
186 
            buf.extend_from_slice(&l);
187 
            ends.push(buf.len() as u64);
188 
        }
189 
        let ends = Ends::from_u64(ends, buf.len());
190 
        Lines(Arc::new(Inner {
191 
            buf: Arc::new(buf),
192 
            ends,
193 
        }))
194 
    }
195 
}
196
197 
impl From<Vec<Vec<u8>>> for Lines {
198 
    fn from(v: Vec<Vec<u8>>) -> Lines {
199 
        v.into_iter().collect()
200 
    }
201 
}
202
203 
impl std::fmt::Debug for Lines {
204 
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
205 
        f.debug_list()
206 
            .entries(self.iter().map(String::from_utf8_lossy))
207 
            .finish()
208 
    }
209 
}
210
211 
/// One line of a [`Lines`], held by a file graph's atom.
212 
#[derive(Clone, Debug, PartialEq, Eq)]
213 
pub struct LineRef {
214 
    lines: Lines,
215 
    index: u32,
216 
}
217
218 
impl LineRef {
219 
    pub fn new(lines: Lines, index: u32) -> LineRef {
220 
        LineRef { lines, index }
221 
    }
222
223 
    pub fn bytes(&self) -> &[u8] {
224 
        &self.lines[self.index as usize]
225 
    }
226 
}
227
228 
#[cfg(test)]
229 
mod tests {
230 
    use super::*;
231
232 
    #[test]
233 
    fn lines_split_index_and_join_as_the_line_rule_says() {
234 
        for text in [&b""[..], b"a\n", b"a\nb", b"a\n\nb\n", b"\n", b"no end"] {
235 
            let l = Lines::split(text);
236 
            let want = crate::diff::split_lines(text);
237 
            assert_eq!(l.len(), want.len(), "{text:?}");
238 
            assert_eq!(l.iter().collect::<Vec<_>>(), want);
239 
            assert_eq!(l.bytes(), text);
240 
            let v: Lines = want.iter().copied().collect();
241 
            assert_eq!(v, l);
242 
            assert_eq!(Lines::from(l.to_vec()), l);
243 
        }
244 
        let l = Lines::split(b"a\nb\nc\n");
245 
        assert!(l.is_split_form());
246 
        assert!(!Lines::from(vec![b"a".to_vec(), b"b\n".to_vec()]).is_split_form());
247 
        assert!(!Lines::from(vec![b"a\nb\n".to_vec()]).is_split_form());
248 
        assert!(!Lines::from(vec![Vec::new()]).is_split_form());
249 
        assert!(Lines::from(vec![b"a\n".to_vec(), b"end".to_vec()]).is_split_form());
250 
        assert_eq!(&l[1], b"b\n");
251 
        assert_eq!(
252 
            l.slice(1..3).to_vec(),
253 
            vec![b"b\n".to_vec(), b"c\n".to_vec()]
254 
        );
255 
        assert_eq!(LineRef::new(l.clone(), 2).bytes(), b"c\n");
256 
    }
257 
}