git.iko.soy/helix
on 376c19e help sign in
helix/helix-vcs/src/diff/line_cache.rs
130 lines 5.8 kB history raw
1//! This modules encapsulates a tiny bit of unsafe code that
2//! makes diffing significantly faster and more ergonomic to implement.
3//! This code is necessary because diffing requires quick random
4//! access to the lines of the text that is being diffed.
5//!
6//! Therefore it is best to collect the `Rope::lines` iterator into a vec
7//! first because access to the vec is `O(1)` where `Rope::line` is `O(log N)`.
8//! However this process can allocate a (potentially quite large) vector.
9//!
10//! To avoid reallocation for every diff, the vector is reused.
11//! However the RopeSlice references the original rope and therefore forms a self-referential data structure.
12//! A transmute is used to change the lifetime of the slice to static to circumvent that project.
13use std::mem::transmute;
15use helix_core::{Rope, RopeSlice};
16use imara_diff::intern::{InternedInput, Interner};
18use super::{MAX_DIFF_BYTES, MAX_DIFF_LINES};
20/// A cache that stores the `lines` of a rope as a vector.
21/// It allows safely reusing the allocation of the vec when updating the rope
22pub(crate) struct InternedRopeLines {
23 diff_base: Rope,
24 doc: Rope,
25 num_tokens_diff_base: u32,
26 interned: InternedInput<RopeSlice<'static>>,
29impl InternedRopeLines {
30 pub fn new(diff_base: Rope, doc: Rope) -> InternedRopeLines {
31 let mut res = InternedRopeLines {
32 interned: InternedInput {
33 before: Vec::with_capacity(diff_base.len_lines()),
34 after: Vec::with_capacity(doc.len_lines()),
35 interner: Interner::new(diff_base.len_lines() + doc.len_lines()),
36 },
37 diff_base,
38 doc,
39 // will be populated by update_diff_base_impl
40 num_tokens_diff_base: 0,
41 };
42 res.update_diff_base_impl();
43 res
44 }
46 /// Updates the `diff_base` and optionally the document if `doc` is not None
47 pub fn update_diff_base(&mut self, diff_base: Rope, doc: Option<Rope>) {
48 self.interned.clear();
49 self.diff_base = diff_base;
50 if let Some(doc) = doc {
51 self.doc = doc
52 }
53 if !self.is_too_large() {
54 self.update_diff_base_impl();
55 }
56 }
58 /// Updates the `doc` without reinterning the `diff_base`, this function
59 /// is therefore significantly faster than `update_diff_base` when only the document changes.
60 pub fn update_doc(&mut self, doc: Rope) {
61 // Safety: we clear any tokens that were added after
62 // the interning of `self.diff_base` finished so
63 // all lines that refer to `self.doc` have been purged.
65 self.interned
66 .interner
67 .erase_tokens_after(self.num_tokens_diff_base.into());
69 self.doc = doc;
70 if self.is_too_large() {
71 self.interned.after.clear();
72 } else {
73 self.update_doc_impl();
74 }
75 }
77 fn update_diff_base_impl(&mut self) {
78 // Safety: This transmute is safe because it only transmutes a lifetime, which has no effect.
79 // The backing storage for the RopeSlices referred to by the lifetime is stored in `self.diff_base`.
80 // Therefore as long as `self.diff_base` is not dropped/replaced this memory remains valid.
81 // `self.diff_base` is only changed in `self.update_diff_base`, which clears the interner.
82 // When the interned lines are exposed to consumer in `self.diff_input`, the lifetime is bounded to a reference to self.
83 // That means that on calls to update there exist no references to `self.interned`.
84 let before = self
85 .diff_base
86 .lines()
87 .map(|line: RopeSlice| -> RopeSlice<'static> { unsafe { transmute(line) } });
88 self.interned.update_before(before);
89 self.num_tokens_diff_base = self.interned.interner.num_tokens();
90 // the has to be interned again because the interner was fully cleared
91 self.update_doc_impl()
92 }
94 fn update_doc_impl(&mut self) {
95 // Safety: This transmute is save because it only transmutes a lifetime, which has no effect.
96 // The backing storage for the RopeSlices referred to by the lifetime is stored in `self.doc`.
97 // Therefore as long as `self.doc` is not dropped/replaced this memory remains valid.
98 // `self.doc` is only changed in `self.update_doc`, which clears the interner.
99 // When the interned lines are exposed to consumer in `self.diff_input`, the lifetime is bounded to a reference to self.
100 // That means that on calls to update there exist no references to `self.interned`.
101 let after = self
102 .doc
103 .lines()
104 .map(|line: RopeSlice| -> RopeSlice<'static> { unsafe { transmute(line) } });
105 self.interned.update_after(after);
106 }
108 fn is_too_large(&self) -> bool {
109 // bound both lines and bytes to avoid huge files with few (but huge) lines
110 // or huge file with tiny lines. While this makes no difference to
111 // diff itself (the diff performance only depends on the number of tokens)
112 // the interning runtime depends mostly on filesize and is actually dominant
113 // for large files
114 self.doc.len_lines() > MAX_DIFF_LINES
115 || self.diff_base.len_lines() > MAX_DIFF_LINES
116 || self.doc.len_bytes() > MAX_DIFF_BYTES
117 || self.diff_base.len_bytes() > MAX_DIFF_BYTES
118 }
120 /// Returns the `InternedInput` for performing the diff.
121 /// If `diff_base` or `doc` is so large that performing a diff could slow the editor
122 /// this function returns `None`.
123 pub fn interned_lines(&self) -> Option<&InternedInput<RopeSlice>> {
124 if self.is_too_large() {
125 None
126 } else {
127 Some(&self.interned)
128 }
129 }