OXYGENHUB
# 73d592e763ab oxygen / crates / oxy-core / src / lines.rs
4.6 KiB · Rust · last changed Keep an insert's lines in one shared buffer 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 
    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
68 
    /// Lines `range` as lines of their own.
69 
    pub fn slice(&self, range: std::ops::Range<usize>) -> Lines {
70 
        self.iter().skip(range.start).take(range.len()).collect()
71 
    }
72
73 
    /// The lines as owned vectors, for code that edits them one by one.
74 
    pub fn to_vec(&self) -> Vec<Vec<u8>> {
75 
        self.iter().map(<[u8]>::to_vec).collect()
76 
    }
77 
}
78
79 
impl std::ops::Index<usize> for Lines {
80 
    type Output = [u8];
81 
    fn index(&self, i: usize) -> &[u8] {
82 
        self.get(i).expect("line index out of range")
83 
    }
84 
}
85
86 
impl<'a> FromIterator<&'a [u8]> for Lines {
87 
    fn from_iter<I: IntoIterator<Item = &'a [u8]>>(iter: I) -> Lines {
88 
        let mut inner = Inner::default();
89 
        for l in iter {
90 
            inner.buf.extend_from_slice(l);
91 
            inner.ends.push(inner.buf.len() as u64);
92 
        }
93 
        Lines(Arc::new(inner))
94 
    }
95 
}
96
97 
impl FromIterator<Vec<u8>> for Lines {
98 
    fn from_iter<I: IntoIterator<Item = Vec<u8>>>(iter: I) -> Lines {
99 
        let mut inner = Inner::default();
100 
        for l in iter {
101 
            inner.buf.extend_from_slice(&l);
102 
            inner.ends.push(inner.buf.len() as u64);
103 
        }
104 
        Lines(Arc::new(inner))
105 
    }
106 
}
107
108 
impl From<Vec<Vec<u8>>> for Lines {
109 
    fn from(v: Vec<Vec<u8>>) -> Lines {
110 
        v.into_iter().collect()
111 
    }
112 
}
113
114 
impl std::fmt::Debug for Lines {
115 
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
116 
        f.debug_list()
117 
            .entries(self.iter().map(String::from_utf8_lossy))
118 
            .finish()
119 
    }
120 
}
121
122 
/// One line of a [`Lines`], held by a file graph's atom.
123 
#[derive(Clone, Debug, PartialEq, Eq)]
124 
pub struct LineRef {
125 
    lines: Lines,
126 
    index: u32,
127 
}
128
129 
impl LineRef {
130 
    pub fn new(lines: Lines, index: u32) -> LineRef {
131 
        LineRef { lines, index }
132 
    }
133
134 
    pub fn bytes(&self) -> &[u8] {
135 
        &self.lines[self.index as usize]
136 
    }
137 
}
138
139 
#[cfg(test)]
140 
mod tests {
141 
    use super::*;
142
143 
    #[test]
144 
    fn lines_split_index_and_join_as_the_line_rule_says() {
145 
        for text in [&b""[..], b"a\n", b"a\nb", b"a\n\nb\n", b"\n", b"no end"] {
146 
            let l = Lines::split(text);
147 
            let want = crate::diff::split_lines(text);
148 
            assert_eq!(l.len(), want.len(), "{text:?}");
149 
            assert_eq!(l.iter().collect::<Vec<_>>(), want);
150 
            assert_eq!(l.bytes(), text);
151 
            let v: Lines = want.iter().copied().collect();
152 
            assert_eq!(v, l);
153 
            assert_eq!(Lines::from(l.to_vec()), l);
154 
        }
155 
        let l = Lines::split(b"a\nb\nc\n");
156 
        assert_eq!(&l[1], b"b\n");
157 
        assert_eq!(
158 
            l.slice(1..3).to_vec(),
159 
            vec![b"b\n".to_vec(), b"c\n".to_vec()]
160 
        );
161 
        assert_eq!(LineRef::new(l.clone(), 2).bytes(), b"c\n");
162 
    }
163 
}