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