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