1use super::wrap_map::{self, Edit as WrapEdit, Snapshot as WrapSnapshot, WrapPoint};
2use buffer::{rope, Anchor, Bias, Point, Rope, ToOffset};
3use gpui::fonts::HighlightStyle;
4use language::HighlightedChunk;
5use parking_lot::Mutex;
6use std::{borrow::Borrow, cmp, collections::HashSet, iter, ops::Range, slice, sync::Arc};
7use sum_tree::SumTree;
8
9struct BlockMap {
10 blocks: Vec<(BlockId, Arc<Block>)>,
11 transforms: Mutex<SumTree<Transform>>,
12}
13
14struct BlockMapWriter<'a>(&'a mut BlockMap);
15
16struct BlockSnapshot {
17 wrap_snapshot: WrapSnapshot,
18 transforms: SumTree<Transform>,
19}
20
21#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
22struct BlockId(usize);
23
24#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
25pub struct BlockPoint(super::Point);
26
27struct Block {
28 id: BlockId,
29 position: Anchor,
30 text: Rope,
31 runs: Vec<(usize, HighlightStyle)>,
32 disposition: BlockDisposition,
33}
34
35#[derive(Clone)]
36struct BlockProperties<P, T>
37where
38 P: Clone,
39 T: Clone,
40{
41 position: P,
42 text: T,
43 runs: Vec<(usize, HighlightStyle)>,
44 disposition: BlockDisposition,
45}
46
47#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
48enum BlockDisposition {
49 Above,
50 Below,
51}
52
53#[derive(Clone)]
54struct Transform {
55 summary: TransformSummary,
56 block: Option<Arc<Block>>,
57}
58
59#[derive(Copy, Clone, Debug, Default)]
60struct TransformSummary {
61 input_rows: u32,
62 output_rows: u32,
63}
64
65struct HighlightedChunks<'a> {
66 transform_cursor: sum_tree::Cursor<'a, Transform, (OutputRow, InputRow)>,
67 input_chunks: wrap_map::HighlightedChunks<'a>,
68 input_chunk: Option<HighlightedChunk<'a>>,
69 block_chunks: Option<BlockChunks<'a>>,
70 output_position: BlockPoint,
71 max_output_row: u32,
72}
73
74struct BlockChunks<'a> {
75 chunks: rope::Chunks<'a>,
76 runs: iter::Peekable<slice::Iter<'a, (usize, HighlightStyle)>>,
77 chunk: Option<&'a str>,
78 run_start: usize,
79 offset: usize,
80}
81
82#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
83struct InputRow(u32);
84
85#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
86struct OutputRow(u32);
87
88impl BlockMap {
89 fn new(wrap_snapshot: WrapSnapshot) -> Self {
90 Self {
91 blocks: Vec::new(),
92 transforms: Mutex::new(SumTree::from_item(
93 Transform::isomorphic(wrap_snapshot.max_point().row() + 1),
94 &(),
95 )),
96 }
97 }
98
99 fn read(&self, wrap_snapshot: WrapSnapshot, edits: Vec<WrapEdit>) -> BlockSnapshot {
100 self.sync(&wrap_snapshot, edits);
101 BlockSnapshot {
102 wrap_snapshot,
103 transforms: self.transforms.lock().clone(),
104 }
105 }
106
107 fn write(&mut self, wrap_snapshot: WrapSnapshot, edits: Vec<WrapEdit>) -> BlockMapWriter {
108 self.sync(&wrap_snapshot, edits);
109 BlockMapWriter(self)
110 }
111
112 fn sync(&self, wrap_snapshot: &WrapSnapshot, edits: Vec<WrapEdit>) {
113 let mut transforms = self.transforms.lock();
114 let mut new_transforms = SumTree::new();
115 let mut cursor = transforms.cursor::<InputRow>();
116 let mut edits = edits.into_iter().peekable();
117 while let Some(mut edit) = edits.next() {
118 new_transforms.push_tree(
119 cursor.slice(&InputRow(edit.old.start), Bias::Left, &()),
120 &(),
121 );
122
123 let transform_start = cursor.start().0;
124 edit.new.start -= edit.old.start - transform_start;
125 edit.old.start = transform_start;
126
127 loop {
128 if edit.old.end > cursor.start().0 {
129 cursor.seek(&InputRow(edit.old.end), Bias::Left, &());
130 cursor.next(&());
131 let transform_end = cursor.start().0;
132 edit.new.end += transform_end - edit.old.end;
133 edit.old.end = transform_end;
134 }
135
136 if let Some(next_edit) = edits.peek() {
137 if edit.old.end >= next_edit.old.start {
138 let delta = next_edit.new.len() as i32 - next_edit.old.len() as i32;
139 edit.old.end = cmp::max(next_edit.old.end, edit.old.end);
140 edit.new.end = (edit.new.end as i32 + delta) as u32;
141 edits.next();
142 } else {
143 break;
144 }
145 } else {
146 break;
147 }
148 }
149
150 // TODO: process injections
151
152 let new_transforms_end = new_transforms.summary().input_rows;
153 if new_transforms_end < edit.new.end {
154 new_transforms.push(
155 Transform::isomorphic(edit.new.end - new_transforms_end),
156 &(),
157 );
158 }
159 }
160 new_transforms.push_tree(cursor.suffix(&()), &());
161 drop(cursor);
162 *transforms = new_transforms;
163 }
164}
165
166impl<'a> BlockMapWriter<'a> {
167 pub fn insert<P, T>(
168 &self,
169 blocks: impl IntoIterator<Item = BlockProperties<P, T>>,
170 ) -> Vec<BlockId>
171 where
172 P: ToOffset + Clone,
173 T: Into<Rope> + Clone,
174 {
175 vec![]
176 }
177
178 pub fn remove(&self, ids: HashSet<BlockId>) {
179 //
180 }
181}
182
183impl BlockSnapshot {
184 #[cfg(test)]
185 fn text(&mut self) -> String {
186 self.highlighted_chunks_for_rows(0..(self.max_point().0.row + 1))
187 .map(|chunk| chunk.text)
188 .collect()
189 }
190
191 pub fn highlighted_chunks_for_rows(&mut self, rows: Range<u32>) -> HighlightedChunks {
192 let mut cursor = self.transforms.cursor::<(OutputRow, InputRow)>();
193 cursor.seek(&OutputRow(rows.start), Bias::Right, &());
194 let (input_start, output_start) = cursor.start();
195 let row_overshoot = rows.start - output_start.0;
196 let input_row = input_start.0 + row_overshoot;
197 let input_end = self.to_wrap_point(BlockPoint(Point::new(rows.end, 0)));
198 let input_chunks = self
199 .wrap_snapshot
200 .highlighted_chunks_for_rows(input_row..input_end.row());
201 HighlightedChunks {
202 input_chunks,
203 input_chunk: None,
204 block_chunks: None,
205 transform_cursor: cursor,
206 output_position: BlockPoint(Point::new(rows.start, 0)),
207 max_output_row: rows.end,
208 }
209 }
210
211 pub fn max_point(&self) -> BlockPoint {
212 self.to_block_point(self.wrap_snapshot.max_point())
213 }
214
215 pub fn to_block_point(&self, wrap_point: WrapPoint) -> BlockPoint {
216 let mut cursor = self.transforms.cursor::<(InputRow, OutputRow)>();
217 cursor.seek(&InputRow(wrap_point.row()), Bias::Left, &());
218 while let Some(item) = cursor.item() {
219 if item.is_isomorphic() {
220 break;
221 }
222 cursor.next(&());
223 }
224 let (input_start, output_start) = cursor.start();
225 let row_overshoot = wrap_point.row() - input_start.0;
226 BlockPoint(Point::new(
227 output_start.0 + row_overshoot,
228 wrap_point.column(),
229 ))
230 }
231
232 pub fn to_wrap_point(&self, block_point: BlockPoint) -> WrapPoint {
233 let mut cursor = self.transforms.cursor::<(OutputRow, InputRow)>();
234 cursor.seek(&OutputRow(block_point.0.row), Bias::Right, &());
235 let (output_start, input_start) = cursor.start();
236 let row_overshoot = block_point.0.row - output_start.0;
237 WrapPoint::new(input_start.0 + row_overshoot, block_point.0.column)
238 }
239}
240
241impl Transform {
242 fn isomorphic(rows: u32) -> Self {
243 Self {
244 summary: TransformSummary {
245 input_rows: rows,
246 output_rows: rows,
247 },
248 block: None,
249 }
250 }
251
252 fn is_isomorphic(&self) -> bool {
253 self.block.is_none()
254 }
255}
256
257impl<'a> Iterator for HighlightedChunks<'a> {
258 type Item = HighlightedChunk<'a>;
259
260 fn next(&mut self) -> Option<Self::Item> {
261 if let Some(current_block) = self.block_chunks.as_mut() {
262 if let Some(chunk) = current_block.next() {
263 return Some(chunk);
264 } else {
265 self.block_chunks.take();
266 }
267 }
268
269 let transform = if let Some(item) = self.transform_cursor.item() {
270 item
271 } else {
272 return None;
273 };
274
275 if let Some(block) = &transform.block {
276 let of
277 }
278
279 None
280 }
281}
282
283impl<'a> BlockChunks<'a> {
284 fn new(block: &'a Block, range: Range<usize>) -> Self {
285 let mut runs = block.runs.iter().peekable();
286 let mut run_start = 0;
287 while let Some((run_len, _)) = runs.peek() {
288 let run_end = run_start + run_len;
289 if run_end <= range.start {
290 run_start = run_end;
291 runs.next();
292 } else {
293 break;
294 }
295 }
296
297 Self {
298 chunk: None,
299 run_start,
300 chunks: block.text.chunks_in_range(range.clone()),
301 runs,
302 offset: range.start,
303 }
304 }
305}
306
307impl<'a> Iterator for BlockChunks<'a> {
308 type Item = HighlightedChunk<'a>;
309
310 fn next(&mut self) -> Option<Self::Item> {
311 if self.chunk.is_none() {
312 self.chunk = self.chunks.next();
313 }
314
315 let chunk = self.chunk?;
316 let mut chunk_len = chunk.len();
317 let mut highlight_style = None;
318 if let Some((run_len, style)) = self.runs.peek() {
319 highlight_style = Some(style.clone());
320 let run_end_in_chunk = self.run_start + run_len - self.offset;
321 if run_end_in_chunk <= chunk_len {
322 chunk_len = run_end_in_chunk;
323 self.run_start += run_len;
324 self.runs.next();
325 }
326 }
327
328 self.offset += chunk_len;
329 let (chunk, suffix) = chunk.split_at(chunk_len);
330 self.chunk = if suffix.is_empty() {
331 None
332 } else {
333 Some(suffix)
334 };
335
336 Some(HighlightedChunk {
337 text: chunk,
338 highlight_id: Default::default(),
339 diagnostic: None,
340 })
341 }
342}
343
344impl sum_tree::Item for Transform {
345 type Summary = TransformSummary;
346
347 fn summary(&self) -> Self::Summary {
348 self.summary
349 }
350}
351
352impl sum_tree::Summary for TransformSummary {
353 type Context = ();
354
355 fn add_summary(&mut self, summary: &Self, _: &()) {
356 self.input_rows += summary.input_rows;
357 self.output_rows += summary.output_rows;
358 }
359}
360
361impl<'a> sum_tree::Dimension<'a, TransformSummary> for InputRow {
362 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
363 self.0 += summary.input_rows;
364 }
365}
366
367impl<'a> sum_tree::Dimension<'a, TransformSummary> for OutputRow {
368 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
369 self.0 += summary.output_rows;
370 }
371}
372
373#[cfg(test)]
374mod tests {
375 use super::*;
376 use crate::display_map::{fold_map::FoldMap, tab_map::TabMap, wrap_map::WrapMap};
377 use buffer::{RandomCharIter, ToPoint as _};
378 use language::Buffer;
379 use rand::prelude::*;
380 use std::env;
381
382 #[gpui::test(iterations = 100)]
383 fn test_random(cx: &mut gpui::MutableAppContext, mut rng: StdRng) {
384 let operations = env::var("OPERATIONS")
385 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
386 .unwrap_or(10);
387
388 let wrap_width = Some(rng.gen_range(0.0..=1000.0));
389 let tab_size = 1;
390 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
391 let font_id = cx
392 .font_cache()
393 .select_font(family_id, &Default::default())
394 .unwrap();
395 let font_size = 14.0;
396
397 log::info!("Tab size: {}", tab_size);
398 log::info!("Wrap width: {:?}", wrap_width);
399
400 let buffer = cx.add_model(|cx| {
401 let len = rng.gen_range(0..10);
402 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
403 Buffer::new(0, text, cx)
404 });
405 let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
406 let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), tab_size);
407 let (wrap_map, wraps_snapshot) =
408 WrapMap::new(tabs_snapshot, font_id, font_size, wrap_width, cx);
409 let mut block_map = BlockMap::new(wraps_snapshot);
410 let mut expected_blocks = Vec::new();
411
412 for _ in 0..operations {
413 match rng.gen_range(0..=100) {
414 0..=19 => {
415 let wrap_width = if rng.gen_bool(0.2) {
416 None
417 } else {
418 Some(rng.gen_range(0.0..=1000.0))
419 };
420 log::info!("Setting wrap width to {:?}", wrap_width);
421 wrap_map.update(cx, |map, cx| map.set_wrap_width(wrap_width, cx));
422 }
423 20..=39 => {
424 let block_count = rng.gen_range(1..=4);
425 let block_properties = (0..block_count)
426 .map(|_| {
427 let buffer = buffer.read(cx);
428 let position = buffer.anchor_before(rng.gen_range(0..=buffer.len()));
429
430 let len = rng.gen_range(0..10);
431 let text = Rope::from(
432 RandomCharIter::new(&mut rng)
433 .take(len)
434 .collect::<String>()
435 .as_str(),
436 );
437 BlockProperties {
438 position,
439 text,
440 runs: Vec::<(usize, HighlightStyle)>::new(),
441 disposition: if rng.gen() {
442 BlockDisposition::Above
443 } else {
444 BlockDisposition::Below
445 },
446 }
447 })
448 .collect::<Vec<_>>();
449
450 let (folds_snapshot, fold_edits) = fold_map.read(cx);
451 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
452 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
453 wrap_map.sync(tabs_snapshot, tab_edits, cx)
454 });
455 let block_map = block_map.write(wraps_snapshot, wrap_edits);
456
457 expected_blocks.extend(
458 block_map
459 .insert(block_properties.clone())
460 .into_iter()
461 .zip(block_properties),
462 );
463 }
464 40..=59 => {
465 let block_count = rng.gen_range(1..=4.min(expected_blocks.len()));
466 let block_ids_to_remove = (0..block_count)
467 .map(|_| {
468 expected_blocks
469 .remove(rng.gen_range(0..expected_blocks.len()))
470 .0
471 })
472 .collect();
473
474 let (folds_snapshot, fold_edits) = fold_map.read(cx);
475 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
476 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
477 wrap_map.sync(tabs_snapshot, tab_edits, cx)
478 });
479 let block_map = block_map.write(wraps_snapshot, wrap_edits);
480
481 block_map.remove(block_ids_to_remove);
482 }
483 _ => {
484 buffer.update(cx, |buffer, _| buffer.randomly_edit(&mut rng, 5));
485 }
486 }
487
488 let (folds_snapshot, fold_edits) = fold_map.read(cx);
489 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
490 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
491 wrap_map.sync(tabs_snapshot, tab_edits, cx)
492 });
493 let mut blocks_snapshot = block_map.read(wraps_snapshot.clone(), wrap_edits);
494 assert_eq!(
495 blocks_snapshot.transforms.summary().input_rows,
496 wraps_snapshot.max_point().row() + 1
497 );
498
499 let buffer = buffer.read(cx);
500 let mut sorted_blocks = expected_blocks
501 .iter()
502 .cloned()
503 .map(|(_, block)| BlockProperties {
504 position: block.position.to_point(buffer),
505 text: block.text,
506 runs: block.runs,
507 disposition: block.disposition,
508 })
509 .collect::<Vec<_>>();
510 sorted_blocks.sort_unstable_by_key(|block| (block.position.row, block.disposition));
511 let mut sorted_blocks = sorted_blocks.into_iter().peekable();
512
513 let mut expected_text = String::new();
514 let input_text = wraps_snapshot.text();
515 for (row, input_line) in input_text.split('\n').enumerate() {
516 let row = row as u32;
517 if row > 0 {
518 expected_text.push('\n');
519 }
520
521 while let Some(block) = sorted_blocks.peek() {
522 if block.position.row == row && block.disposition == BlockDisposition::Above {
523 expected_text.extend(block.text.chunks());
524 expected_text.push('\n');
525 sorted_blocks.next();
526 } else {
527 break;
528 }
529 }
530
531 expected_text.push_str(input_line);
532
533 while let Some(block) = sorted_blocks.peek() {
534 if block.position.row == row && block.disposition == BlockDisposition::Below {
535 expected_text.push('\n');
536 expected_text.extend(block.text.chunks());
537 sorted_blocks.next();
538 } else {
539 break;
540 }
541 }
542 }
543
544 assert_eq!(blocks_snapshot.text(), expected_text);
545 }
546 }
547}