1use std::cmp;
2
3use super::wrap_map::{Edit as WrapEdit, Snapshot as WrapSnapshot};
4use buffer::Bias;
5use parking_lot::Mutex;
6use sum_tree::SumTree;
7
8struct BlockMap {
9 transforms: Mutex<SumTree<Transform>>,
10}
11
12struct BlockMapWriter<'a>(&'a mut BlockMap);
13
14struct BlockSnapshot {
15 transforms: SumTree<Transform>,
16}
17
18#[derive(Clone)]
19struct Transform {
20 summary: TransformSummary,
21}
22
23#[derive(Copy, Clone, Debug, Default)]
24struct TransformSummary {
25 input_rows: u32,
26 output_rows: u32,
27}
28
29#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
30struct InputRow(u32);
31
32#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
33struct OutputRow(u32);
34
35impl BlockMap {
36 fn new(wrap_snapshot: WrapSnapshot) -> Self {
37 Self {
38 transforms: Mutex::new(SumTree::from_item(
39 Transform::isomorphic(wrap_snapshot.max_point().row() + 1),
40 &(),
41 )),
42 }
43 }
44
45 fn read(&self, wrap_snapshot: WrapSnapshot, edits: Vec<WrapEdit>) -> BlockSnapshot {
46 self.sync(wrap_snapshot, edits);
47 BlockSnapshot {
48 transforms: self.transforms.lock().clone(),
49 }
50 }
51
52 fn write(&mut self, wrap_snapshot: WrapSnapshot, edits: Vec<WrapEdit>) -> BlockMapWriter {
53 self.sync(wrap_snapshot, edits);
54 BlockMapWriter(self)
55 }
56
57 fn sync(&self, wrap_snapshot: WrapSnapshot, edits: Vec<WrapEdit>) {
58 let mut transforms = self.transforms.lock();
59 let mut new_transforms = SumTree::new();
60 let mut cursor = transforms.cursor::<InputRow>();
61 let mut edits = edits.into_iter().peekable();
62 while let Some(mut edit) = edits.next() {
63 new_transforms.push_tree(
64 cursor.slice(&InputRow(edit.old.start), Bias::Left, &()),
65 &(),
66 );
67
68 let transform_start = cursor.start().0;
69 edit.new.start -= edit.old.start - transform_start;
70 edit.old.start = transform_start;
71
72 loop {
73 if edit.old.end > cursor.start().0 {
74 cursor.seek(&InputRow(edit.old.end), Bias::Left, &());
75 cursor.next(&());
76 let transform_end = cursor.start().0;
77 edit.new.end += transform_end - edit.old.end;
78 edit.old.end = transform_end;
79 }
80
81 if let Some(next_edit) = edits.peek() {
82 if edit.old.end >= next_edit.old.start {
83 let delta = next_edit.new.len() as i32 - next_edit.old.len() as i32;
84 edit.old.end = cmp::max(next_edit.old.end, edit.old.end);
85 edit.new.end = (edit.new.end as i32 + delta) as u32;
86 edits.next();
87 } else {
88 break;
89 }
90 } else {
91 break;
92 }
93 }
94
95 // TODO: process injections
96
97 let new_transforms_end = new_transforms.summary().input_rows;
98 if new_transforms_end < edit.new.end {
99 new_transforms.push(
100 Transform::isomorphic(edit.new.end - new_transforms_end),
101 &(),
102 );
103 }
104 }
105 new_transforms.push_tree(cursor.suffix(&()), &());
106 drop(cursor);
107 *transforms = new_transforms;
108 }
109}
110
111impl Transform {
112 fn isomorphic(rows: u32) -> Self {
113 Self {
114 summary: TransformSummary {
115 input_rows: rows,
116 output_rows: rows,
117 },
118 }
119 }
120}
121
122impl sum_tree::Item for Transform {
123 type Summary = TransformSummary;
124
125 fn summary(&self) -> Self::Summary {
126 self.summary
127 }
128}
129
130impl sum_tree::Summary for TransformSummary {
131 type Context = ();
132
133 fn add_summary(&mut self, summary: &Self, _: &()) {
134 self.input_rows += summary.input_rows;
135 self.output_rows += summary.output_rows;
136 }
137}
138
139impl<'a> sum_tree::Dimension<'a, TransformSummary> for InputRow {
140 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
141 self.0 += summary.input_rows;
142 }
143}
144
145impl<'a> sum_tree::Dimension<'a, TransformSummary> for OutputRow {
146 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
147 self.0 += summary.output_rows;
148 }
149}
150
151#[cfg(test)]
152mod tests {
153 use super::BlockMap;
154 use crate::display_map::{fold_map::FoldMap, tab_map::TabMap, wrap_map::WrapMap};
155 use buffer::RandomCharIter;
156 use language::Buffer;
157 use rand::prelude::*;
158 use std::env;
159
160 #[gpui::test(iterations = 100)]
161 fn test_random(cx: &mut gpui::MutableAppContext, mut rng: StdRng) {
162 let operations = env::var("OPERATIONS")
163 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
164 .unwrap_or(10);
165
166 let wrap_width = Some(rng.gen_range(0.0..=1000.0));
167 let tab_size = 1;
168 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
169 let font_id = cx
170 .font_cache()
171 .select_font(family_id, &Default::default())
172 .unwrap();
173 let font_size = 14.0;
174
175 log::info!("Tab size: {}", tab_size);
176 log::info!("Wrap width: {:?}", wrap_width);
177
178 let buffer = cx.add_model(|cx| {
179 let len = rng.gen_range(0..10);
180 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
181 Buffer::new(0, text, cx)
182 });
183 let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
184 let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), tab_size);
185 let (wrap_map, wraps_snapshot) =
186 WrapMap::new(tabs_snapshot, font_id, font_size, wrap_width, cx);
187 let block_map = BlockMap::new(wraps_snapshot);
188
189 for _ in 0..operations {
190 match rng.gen_range(0..=100) {
191 0..=19 => {
192 let wrap_width = if rng.gen_bool(0.2) {
193 None
194 } else {
195 Some(rng.gen_range(0.0..=1000.0))
196 };
197 log::info!("Setting wrap width to {:?}", wrap_width);
198 wrap_map.update(cx, |map, cx| map.set_wrap_width(wrap_width, cx));
199 }
200 _ => {
201 buffer.update(cx, |buffer, _| buffer.randomly_edit(&mut rng, 5));
202 }
203 }
204
205 let (folds_snapshot, fold_edits) = fold_map.read(cx);
206 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
207 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
208 wrap_map.sync(tabs_snapshot, tab_edits, cx)
209 });
210 let blocks_snapshot = block_map.read(wraps_snapshot.clone(), wrap_edits);
211 assert_eq!(
212 blocks_snapshot.transforms.summary().input_rows,
213 wraps_snapshot.max_point().row() + 1
214 );
215 }
216 }
217}