OXYGENHUB
# 4f264d6f20b6 oxygen / crates / oxy-core / src / lines.rs
6.3 KiB · Rust · last changed A new file's lines share its content 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: Vec<u64>,
15 
}
16
17 
/// An insert's lines. Cloning is cheap: the buffer is shared.
18 
#[derive(Clone, Default, PartialEq, Eq, Hash)]
19 
pub struct Lines(Arc<Inner>);
20
21 
impl Lines {
22 
    /// Lines from their bytes, each keeping its terminator; a final
23 
    /// unterminated line is its own line (the rule of
24 
    /// [`crate::diff::split_lines`]).
25 
    pub fn split(content: &[u8]) -> Lines {
26 
        Lines::split_shared(Arc::new(content.to_vec()))
27 
    }
28
29 
    /// [`Lines::split`] of a buffer held elsewhere too (a file's content),
30 
    /// shared rather than copied.
31 
    pub fn split_shared(buf: Arc<Vec<u8>>) -> Lines {
32 
        let content = &buf[..];
33 
        let mut ends = Vec::new();
34 
        for (i, &c) in content.iter().enumerate() {
35 
            if c == b'\n' {
36 
                ends.push(i as u64 + 1);
37 
            }
38 
        }
39 
        if ends.last().copied().unwrap_or(0) as usize != content.len() {
40 
            ends.push(content.len() as u64);
41 
        }
42 
        Lines(Arc::new(Inner { buf, ends }))
43 
    }
44
45 
    pub fn len(&self) -> usize {
46 
        self.0.ends.len()
47 
    }
48
49 
    pub fn is_empty(&self) -> bool {
50 
        self.0.ends.is_empty()
51 
    }
52
53 
    /// Line `i`, with its terminator.
54 
    pub fn get(&self, i: usize) -> Option<&[u8]> {
55 
        let end = *self.0.ends.get(i)? as usize;
56 
        let start = if i == 0 {
57 
            0
58 
        } else {
59 
            self.0.ends[i - 1] as usize
60 
        };
61 
        Some(&self.0.buf[start..end])
62 
    }
63
64 
    pub fn iter(&self) -> impl ExactSizeIterator<Item = &[u8]> + Clone + '_ {
65 
        (0..self.len()).map(move |i| self.get(i).unwrap())
66 
    }
67
68 
    /// Every line, joined: the bytes they were split from.
69 
    pub fn bytes(&self) -> &[u8] {
70 
        &self.0.buf
71 
    }
72
73 
    /// Whether splitting [`Lines::bytes`] by the line rule gives these lines
74 
    /// back: every line but the last ends in a newline and none holds
75 
    /// another. Every insert oxy makes is so, and such lines are stored as
76 
    /// their bytes alone (spec §7.4).
77 
    pub fn is_split_form(&self) -> bool {
78 
        let buf = &self.0.buf;
79 
        let mut start = 0usize;
80 
        for (i, &end) in self.0.ends.iter().enumerate() {
81 
            let line = &buf[start..end as usize];
82 
            if line.is_empty() {
83 
                return false;
84 
            }
85 
            let last = i + 1 == self.0.ends.len();
86 
            let body = if last && !line.ends_with(b"\n") {
87 
                line
88 
            } else if line.ends_with(b"\n") {
89 
                &line[..line.len() - 1]
90 
            } else {
91 
                return false;
92 
            };
93 
            if body.contains(&b'\n') {
94 
                return false;
95 
            }
96 
            start = end as usize;
97 
        }
98 
        true
99 
    }
100
101 
    /// Lines `range` as lines of their own.
102 
    pub fn slice(&self, range: std::ops::Range<usize>) -> Lines {
103 
        self.iter().skip(range.start).take(range.len()).collect()
104 
    }
105
106 
    /// The lines as owned vectors, for code that edits them one by one.
107 
    pub fn to_vec(&self) -> Vec<Vec<u8>> {
108 
        self.iter().map(<[u8]>::to_vec).collect()
109 
    }
110 
}
111
112 
impl std::ops::Index<usize> for Lines {
113 
    type Output = [u8];
114 
    fn index(&self, i: usize) -> &[u8] {
115 
        self.get(i).expect("line index out of range")
116 
    }
117 
}
118
119 
impl<'a> FromIterator<&'a [u8]> for Lines {
120 
    fn from_iter<I: IntoIterator<Item = &'a [u8]>>(iter: I) -> Lines {
121 
        let (mut buf, mut ends) = (Vec::new(), Vec::new());
122 
        for l in iter {
123 
            buf.extend_from_slice(l);
124 
            ends.push(buf.len() as u64);
125 
        }
126 
        Lines(Arc::new(Inner {
127 
            buf: Arc::new(buf),
128 
            ends,
129 
        }))
130 
    }
131 
}
132
133 
impl FromIterator<Vec<u8>> for Lines {
134 
    fn from_iter<I: IntoIterator<Item = Vec<u8>>>(iter: I) -> Lines {
135 
        let (mut buf, mut ends) = (Vec::new(), Vec::new());
136 
        for l in iter {
137 
            buf.extend_from_slice(&l);
138 
            ends.push(buf.len() as u64);
139 
        }
140 
        Lines(Arc::new(Inner {
141 
            buf: Arc::new(buf),
142 
            ends,
143 
        }))
144 
    }
145 
}
146
147 
impl From<Vec<Vec<u8>>> for Lines {
148 
    fn from(v: Vec<Vec<u8>>) -> Lines {
149 
        v.into_iter().collect()
150 
    }
151 
}
152
153 
impl std::fmt::Debug for Lines {
154 
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
155 
        f.debug_list()
156 
            .entries(self.iter().map(String::from_utf8_lossy))
157 
            .finish()
158 
    }
159 
}
160
161 
/// One line of a [`Lines`], held by a file graph's atom.
162 
#[derive(Clone, Debug, PartialEq, Eq)]
163 
pub struct LineRef {
164 
    lines: Lines,
165 
    index: u32,
166 
}
167
168 
impl LineRef {
169 
    pub fn new(lines: Lines, index: u32) -> LineRef {
170 
        LineRef { lines, index }
171 
    }
172
173 
    pub fn bytes(&self) -> &[u8] {
174 
        &self.lines[self.index as usize]
175 
    }
176 
}
177
178 
#[cfg(test)]
179 
mod tests {
180 
    use super::*;
181
182 
    #[test]
183 
    fn lines_split_index_and_join_as_the_line_rule_says() {
184 
        for text in [&b""[..], b"a\n", b"a\nb", b"a\n\nb\n", b"\n", b"no end"] {
185 
            let l = Lines::split(text);
186 
            let want = crate::diff::split_lines(text);
187 
            assert_eq!(l.len(), want.len(), "{text:?}");
188 
            assert_eq!(l.iter().collect::<Vec<_>>(), want);
189 
            assert_eq!(l.bytes(), text);
190 
            let v: Lines = want.iter().copied().collect();
191 
            assert_eq!(v, l);
192 
            assert_eq!(Lines::from(l.to_vec()), l);
193 
        }
194 
        let l = Lines::split(b"a\nb\nc\n");
195 
        assert!(l.is_split_form());
196 
        assert!(!Lines::from(vec![b"a".to_vec(), b"b\n".to_vec()]).is_split_form());
197 
        assert!(!Lines::from(vec![b"a\nb\n".to_vec()]).is_split_form());
198 
        assert!(!Lines::from(vec![Vec::new()]).is_split_form());
199 
        assert!(Lines::from(vec![b"a\n".to_vec(), b"end".to_vec()]).is_split_form());
200 
        assert_eq!(&l[1], b"b\n");
201 
        assert_eq!(
202 
            l.slice(1..3).to_vec(),
203 
            vec![b"b\n".to_vec(), b"c\n".to_vec()]
204 
        );
205 
        assert_eq!(LineRef::new(l.clone(), 2).bytes(), b"c\n");
206 
    }
207 
}