lines.rs 94.9%

148 of 156 lines run, 60 of 71 functions · run #339 on proposal/124 · run missed

//! The lines of an insert (spec §7.4) held as one buffer and where each
//! line ends, shared by the change and the file graph it builds: a tree of
//! forty million lines is then a few allocations per insert, not one per
//! line, and a graph's atoms point into their insert's buffer rather than
//! copying it.

use std::sync::Arc;

#[derive(Default, PartialEq, Eq, Hash)]
struct Inner {
    /// Shared with the file it was read from, when there was one.
    buf: Arc<Vec<u8>>,
    /// The end offset of each line in `buf`.
    ends: Ends,
}

/// Line end offsets, four bytes each unless the buffer is over 4 GiB: a
/// first commit of the Linux tree holds 36 million of them at once. Which
/// form follows from the buffer's length alone, so equal lines compare
/// equal.
#[derive(PartialEq, Eq, Hash)]
enum Ends {
    Small(Vec<u32>),
    Large(Vec<u64>),
}

impl Default for Ends {
    fn default() -> Self {
        Ends::Small(Vec::new())
    }
}

impl Ends {
    fn from_u64(ends: Vec<u64>, buf_len: usize) -> Ends {
        if u32::try_from(buf_len).is_ok() {
            Ends::Small(ends.into_iter().map(|e| e as u32).collect())
        } else {
            Ends::Large(ends)
        }
    }

    fn len(&self) -> usize {
        match self {
            Ends::Small(v) => v.len(),
            Ends::Large(v) => v.len(),
        }
    }

    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    fn get(&self, i: usize) -> Option<usize> {
        match self {
            Ends::Small(v) => v.get(i).map(|&e| e as usize),
            Ends::Large(v) => v.get(i).map(|&e| e as usize),
        }
    }
}

/// An insert's lines. Cloning is cheap: the buffer is shared.
#[derive(Clone, Default, PartialEq, Eq, Hash)]
pub struct Lines(Arc<Inner>);

impl Lines {
    /// Lines from their bytes, each keeping its terminator; a final
    /// unterminated line is its own line (the rule of
    /// [`crate::diff::split_lines`]).
    pub fn split(content: &[u8]) -> Lines {
        Lines::split_shared(Arc::new(content.to_vec()))
    }

    /// [`Lines::split`] of a buffer held elsewhere too (a file's content),
    /// shared rather than copied.
    pub fn split_shared(buf: Arc<Vec<u8>>) -> Lines {
        let content = &buf[..];
        // Counted first, so the offsets take exactly their room.
        let newlines = memchr::memchr_iter(b'\n', content).count();
        let unterminated = content.last().is_some_and(|&c| c != b'\n');
        let n = newlines + usize::from(unterminated);
        let ends_at = memchr::memchr_iter(b'\n', content)
            .map(|i| i + 1)
            .chain(unterminated.then_some(content.len()));
        let ends = if u32::try_from(content.len()).is_ok() {
            let mut v = Vec::with_capacity(n);
            v.extend(ends_at.map(|e| e as u32));
            Ends::Small(v)
        } else {
            let mut v = Vec::with_capacity(n);
            v.extend(ends_at.map(|e| e as u64));
            Ends::Large(v)
        };
        Lines(Arc::new(Inner { buf, ends }))
    }

    pub fn len(&self) -> usize {
        self.0.ends.len()
    }

    pub fn is_empty(&self) -> bool {
        self.0.ends.is_empty()
    }

    /// Line `i`, with its terminator.
    pub fn get(&self, i: usize) -> Option<&[u8]> {
        let end = self.0.ends.get(i)?;
        let start = if i == 0 { 0 } else { self.0.ends.get(i - 1)? };
        Some(&self.0.buf[start..end])
    }

    pub fn iter(&self) -> impl ExactSizeIterator<Item = &[u8]> + Clone + '_ {
        (0..self.len()).map(move |i| self.get(i).unwrap())
    }

    /// Every line, joined: the bytes they were split from.
    pub fn bytes(&self) -> &[u8] {
        &self.0.buf
    }

    /// Whether splitting [`Lines::bytes`] by the line rule gives these lines
    /// back: every line but the last ends in a newline and none holds
    /// another. Every insert oxy makes is so, and such lines are stored as
    /// their bytes alone (spec §7.4).
    pub fn is_split_form(&self) -> bool {
        let buf = &self.0.buf;
        let mut start = 0usize;
        for i in 0..self.0.ends.len() {
            let end = self.0.ends.get(i).unwrap_or(start);
            let line = &buf[start..end];
            if line.is_empty() {
                return false;
            }
            let last = i + 1 == self.0.ends.len();
            let body = if last && !line.ends_with(b"\n") {
                line
            } else if line.ends_with(b"\n") {
                &line[..line.len() - 1]
            } else {
                return false;
            };
            if body.contains(&b'\n') {
                return false;
            }
            start = end;
        }
        true
    }

    /// Lines `range` as lines of their own.
    pub fn slice(&self, range: std::ops::Range<usize>) -> Lines {
        self.iter().skip(range.start).take(range.len()).collect()
    }

    /// The lines as owned vectors, for code that edits them one by one.
    pub fn to_vec(&self) -> Vec<Vec<u8>> {
        self.iter().map(<[u8]>::to_vec).collect()
    }
}

impl std::ops::Index<usize> for Lines {
    type Output = [u8];
    fn index(&self, i: usize) -> &[u8] {
        self.get(i).expect("line index out of range")
    }
}

impl<'a> FromIterator<&'a [u8]> for Lines {
    fn from_iter<I: IntoIterator<Item = &'a [u8]>>(iter: I) -> Lines {
        let (mut buf, mut ends) = (Vec::new(), Vec::new());
        for l in iter {
            buf.extend_from_slice(l);
            ends.push(buf.len() as u64);
        }
        let ends = Ends::from_u64(ends, buf.len());
        Lines(Arc::new(Inner {
            buf: Arc::new(buf),
            ends,
        }))
    }
}

impl FromIterator<Vec<u8>> for Lines {
    fn from_iter<I: IntoIterator<Item = Vec<u8>>>(iter: I) -> Lines {
        let (mut buf, mut ends) = (Vec::new(), Vec::new());
        for l in iter {
            buf.extend_from_slice(&l);
            ends.push(buf.len() as u64);
        }
        let ends = Ends::from_u64(ends, buf.len());
        Lines(Arc::new(Inner {
            buf: Arc::new(buf),
            ends,
        }))
    }
}

impl From<Vec<Vec<u8>>> for Lines {
    fn from(v: Vec<Vec<u8>>) -> Lines {
        v.into_iter().collect()
    }
}

impl std::fmt::Debug for Lines {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_list()
            .entries(self.iter().map(String::from_utf8_lossy))
            .finish()
    }
}

/// One line of a [`Lines`], held by a file graph's atom.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct LineRef {
    lines: Lines,
    index: u32,
}

impl LineRef {
    pub fn new(lines: Lines, index: u32) -> LineRef {
        LineRef { lines, index }
    }

    pub fn bytes(&self) -> &[u8] {
        &self.lines[self.index as usize]
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn lines_split_index_and_join_as_the_line_rule_says() {
        for text in [&b""[..], b"a\n", b"a\nb", b"a\n\nb\n", b"\n", b"no end"] {
            let l = Lines::split(text);
            let want = crate::diff::split_lines(text);
            assert_eq!(l.len(), want.len(), "{text:?}");
            assert_eq!(l.iter().collect::<Vec<_>>(), want);
            assert_eq!(l.bytes(), text);
            let v: Lines = want.iter().copied().collect();
            assert_eq!(v, l);
            assert_eq!(Lines::from(l.to_vec()), l);
        }
        let l = Lines::split(b"a\nb\nc\n");
        assert!(l.is_split_form());
        assert!(!Lines::from(vec![b"a".to_vec(), b"b\n".to_vec()]).is_split_form());
        assert!(!Lines::from(vec![b"a\nb\n".to_vec()]).is_split_form());
        assert!(!Lines::from(vec![Vec::new()]).is_split_form());
        assert!(Lines::from(vec![b"a\n".to_vec(), b"end".to_vec()]).is_split_form());
        assert_eq!(&l[1], b"b\n");
        assert_eq!(
            l.slice(1..3).to_vec(),
            vec![b"b\n".to_vec(), b"c\n".to_vec()]
        );
        assert_eq!(LineRef::new(l.clone(), 2).bytes(), b"c\n");
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

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	51524×	fn default() -> Self {
29	51524×	Ends::Small(Vec::new())
30	51524×	}
31		}
32
33		impl Ends {
34	44261×	fn from_u64(ends: Vec<u64>, buf_len: usize) -> Ends {
35	44261×	if u32::try_from(buf_len).is_ok() {
36	90200×	Ends::Small(ends.into_iter().map(\|e\| e as u32).collect())
37		} else {
38	0×	Ends::Large(ends)
39		}
40	44261×	}
41
42	363438×	fn len(&self) -> usize {
43	363438×	match self {
44	363438×	Ends::Small(v) => v.len(),
45	0×	Ends::Large(v) => v.len(),
46		}
47	363438×	}
48
49	136380×	fn is_empty(&self) -> bool {
50	136380×	self.len() == 0
51	136380×	}
52
53	938785×	fn get(&self, i: usize) -> Option<usize> {
54	938785×	match self {
55	938785×	Ends::Small(v) => v.get(i).map(\|&e\| e as usize),
56	0×	Ends::Large(v) => v.get(i).map(\|&e\| e as usize),
57		}
58	938785×	}
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	141×	pub fn split(content: &[u8]) -> Lines {
70	141×	Lines::split_shared(Arc::new(content.to_vec()))
71	141×	}
72
73		/// [`Lines::split`] of a buffer held elsewhere too (a file's content),
74		/// shared rather than copied.
75	6044×	pub fn split_shared(buf: Arc<Vec<u8>>) -> Lines {
76	6044×	let content = &buf[..];
77		// Counted first, so the offsets take exactly their room.
78	6044×	let newlines = memchr::memchr_iter(b'\n', content).count();
79	6044×	let unterminated = content.last().is_some_and(\|&c\| c != b'\n');
80	6044×	let n = newlines + usize::from(unterminated);
81	6044×	let ends_at = memchr::memchr_iter(b'\n', content)
82	198348×	.map(\|i\| i + 1)
83	6044×	.chain(unterminated.then_some(content.len()));
84	6044×	let ends = if u32::try_from(content.len()).is_ok() {
85	6044×	let mut v = Vec::with_capacity(n);
86	198482×	v.extend(ends_at.map(\|e\| e as u32));
87	6044×	Ends::Small(v)
88		} else {
89	0×	let mut v = Vec::with_capacity(n);
90	0×	v.extend(ends_at.map(\|e\| e as u64));
91	0×	Ends::Large(v)
92		};
93	6044×	Lines(Arc::new(Inner { buf, ends }))
94	6044×	}
95
96	192418×	pub fn len(&self) -> usize {
97	192418×	self.0.ends.len()
98	192418×	}
99
100	136380×	pub fn is_empty(&self) -> bool {
101	136380×	self.0.ends.is_empty()
102	136380×	}
103
104		/// Line `i`, with its terminator.
105	487416×	pub fn get(&self, i: usize) -> Option<&[u8]> {
106	487416×	let end = self.0.ends.get(i)?;
107	487416×	let start = if i == 0 { 0 } else { self.0.ends.get(i - 1)? };
108	487416×	Some(&self.0.buf[start..end])
109	487416×	}
110
111	39158×	pub fn iter(&self) -> impl ExactSizeIterator<Item = &[u8]> + Clone + '_ {
112	311611×	(0..self.len()).map(move \|i\| self.get(i).unwrap())
113	39158×	}
114
115		/// Every line, joined: the bytes they were split from.
116	5703×	pub fn bytes(&self) -> &[u8] {
117	5703×	&self.0.buf
118	5703×	}
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	79×	pub fn is_split_form(&self) -> bool {
125	79×	let buf = &self.0.buf;
126	79×	let mut start = 0usize;
127	34562×	for i in 0..self.0.ends.len() {
128	34562×	let end = self.0.ends.get(i).unwrap_or(start);
129	34562×	let line = &buf[start..end];
130	34562×	if line.is_empty() {
131	1×	return false;
132	34561×	}
133	34561×	let last = i + 1 == self.0.ends.len();
134	34561×	let body = if last && !line.ends_with(b"\n") {
135	53×	line
136	34508×	} else if line.ends_with(b"\n") {
137	34505×	&line[..line.len() - 1]
138		} else {
139	3×	return false;
140		};
141	34558×	if body.contains(&b'\n') {
142	1×	return false;
143	34557×	}
144	34557×	start = end;
145		}
146	74×	true
147	79×	}
148
149		/// Lines `range` as lines of their own.
150	1×	pub fn slice(&self, range: std::ops::Range<usize>) -> Lines {
151	1×	self.iter().skip(range.start).take(range.len()).collect()
152	1×	}
153
154		/// The lines as owned vectors, for code that edits them one by one.
155	17×	pub fn to_vec(&self) -> Vec<Vec<u8>> {
156	17×	self.iter().map(<[u8]>::to_vec).collect()
157	17×	}
158		}
159
160		impl std::ops::Index<usize> for Lines {
161		type Output = [u8];
162	175805×	fn index(&self, i: usize) -> &[u8] {
163	175805×	self.get(i).expect("line index out of range")
164	175805×	}
165		}
166
167		impl<'a> FromIterator<&'a [u8]> for Lines {
168	44197×	fn from_iter<I: IntoIterator<Item = &'a [u8]>>(iter: I) -> Lines {
169	44197×	let (mut buf, mut ends) = (Vec::new(), Vec::new());
170	81920×	for l in iter {
171	81920×	buf.extend_from_slice(l);
172	81920×	ends.push(buf.len() as u64);
173	81920×	}
174	44197×	let ends = Ends::from_u64(ends, buf.len());
175	44197×	Lines(Arc::new(Inner {
176	44197×	buf: Arc::new(buf),
177	44197×	ends,
178	44197×	}))
179	44197×	}
180		}
181
182		impl FromIterator<Vec<u8>> for Lines {
183	64×	fn from_iter<I: IntoIterator<Item = Vec<u8>>>(iter: I) -> Lines {
184	64×	let (mut buf, mut ends) = (Vec::new(), Vec::new());
185	8280×	for l in iter {
186	8280×	buf.extend_from_slice(&l);
187	8280×	ends.push(buf.len() as u64);
188	8280×	}
189	64×	let ends = Ends::from_u64(ends, buf.len());
190	64×	Lines(Arc::new(Inner {
191	64×	buf: Arc::new(buf),
192	64×	ends,
193	64×	}))
194	64×	}
195		}
196
197		impl From<Vec<Vec<u8>>> for Lines {
198	53×	fn from(v: Vec<Vec<u8>>) -> Lines {
199	53×	v.into_iter().collect()
200	53×	}
201		}
202
203		impl std::fmt::Debug for Lines {
204	6654×	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
205	6654×	f.debug_list()
206	6654×	.entries(self.iter().map(String::from_utf8_lossy))
207	6654×	.finish()
208	6654×	}
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	181665×	pub fn new(lines: Lines, index: u32) -> LineRef {
220	181665×	LineRef { lines, index }
221	181665×	}
222
223	175804×	pub fn bytes(&self) -> &[u8] {
224	175804×	&self.lines[self.index as usize]
225	175804×	}
226		}
227
228		#[cfg(test)]
229		mod tests {
230		use super::*;
231
232		#[test]
233	1×	fn lines_split_index_and_join_as_the_line_rule_says() {
234	6×	for text in [&b""[..], b"a\n", b"a\nb", b"a\n\nb\n", b"\n", b"no end"] {
235	6×	let l = Lines::split(text);
236	6×	let want = crate::diff::split_lines(text);
237	6×	assert_eq!(l.len(), want.len(), "{text:?}");
238	6×	assert_eq!(l.iter().collect::<Vec<_>>(), want);
239	6×	assert_eq!(l.bytes(), text);
240	6×	let v: Lines = want.iter().copied().collect();
241	6×	assert_eq!(v, l);
242	6×	assert_eq!(Lines::from(l.to_vec()), l);
243		}
244	1×	let l = Lines::split(b"a\nb\nc\n");
245	1×	assert!(l.is_split_form());
246	1×	assert!(!Lines::from(vec![b"a".to_vec(), b"b\n".to_vec()]).is_split_form());
247	1×	assert!(!Lines::from(vec![b"a\nb\n".to_vec()]).is_split_form());
248	1×	assert!(!Lines::from(vec![Vec::new()]).is_split_form());
249	1×	assert!(Lines::from(vec![b"a\n".to_vec(), b"end".to_vec()]).is_split_form());
250	1×	assert_eq!(&l[1], b"b\n");
251	1×	assert_eq!(
252	1×	l.slice(1..3).to_vec(),
253	1×	vec![b"b\n".to_vec(), b"c\n".to_vec()]
254		);
255	1×	assert_eq!(LineRef::new(l.clone(), 2).bytes(), b"c\n");
256	1×	}
257		}

Coverage / crates/oxy-core/src/lines.rs 94.9%

Keyboard