1use super::wrap_map::{self, Edit as WrapEdit, Snapshot as WrapSnapshot, WrapPoint};
   2use buffer::{rope, Anchor, Bias, Edit, Point, Rope, ToOffset, ToPoint as _};
   3use gpui::{fonts::HighlightStyle, AppContext, ModelHandle};
   4use language::{Buffer, HighlightedChunk};
   5use parking_lot::Mutex;
   6use std::{
   7    cmp::{self, Ordering},
   8    collections::HashSet,
   9    iter,
  10    ops::Range,
  11    slice,
  12    sync::{
  13        atomic::{AtomicUsize, Ordering::SeqCst},
  14        Arc,
  15    },
  16};
  17use sum_tree::SumTree;
  18
  19pub struct BlockMap {
  20    buffer: ModelHandle<Buffer>,
  21    next_block_id: AtomicUsize,
  22    wrap_snapshot: Mutex<WrapSnapshot>,
  23    blocks: Vec<Arc<Block>>,
  24    transforms: Mutex<SumTree<Transform>>,
  25}
  26
  27pub struct BlockMapWriter<'a>(&'a mut BlockMap);
  28
  29pub struct BlockSnapshot {
  30    wrap_snapshot: WrapSnapshot,
  31    transforms: SumTree<Transform>,
  32}
  33
  34#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
  35pub struct BlockId(usize);
  36
  37#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
  38pub struct BlockPoint(pub super::Point);
  39
  40#[derive(Debug)]
  41struct Block {
  42    id: BlockId,
  43    position: Anchor,
  44    text: Rope,
  45    runs: Vec<(usize, HighlightStyle)>,
  46    disposition: BlockDisposition,
  47}
  48
  49#[derive(Clone)]
  50pub struct BlockProperties<P, T>
  51where
  52    P: Clone,
  53    T: Clone,
  54{
  55    position: P,
  56    text: T,
  57    runs: Vec<(usize, HighlightStyle)>,
  58    disposition: BlockDisposition,
  59}
  60
  61#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
  62enum BlockDisposition {
  63    Above,
  64    Below,
  65}
  66
  67#[derive(Clone, Debug)]
  68struct Transform {
  69    summary: TransformSummary,
  70    block: Option<Arc<Block>>,
  71}
  72
  73#[derive(Clone, Debug, Default)]
  74struct TransformSummary {
  75    input: Point,
  76    output: Point,
  77}
  78
  79pub struct HighlightedChunks<'a> {
  80    transforms: sum_tree::Cursor<'a, Transform, (BlockPoint, WrapPoint)>,
  81    input_chunks: wrap_map::HighlightedChunks<'a>,
  82    input_chunk: HighlightedChunk<'a>,
  83    block_chunks: Option<BlockChunks<'a>>,
  84    output_position: BlockPoint,
  85    max_output_position: BlockPoint,
  86}
  87
  88struct BlockChunks<'a> {
  89    chunks: rope::Chunks<'a>,
  90    runs: iter::Peekable<slice::Iter<'a, (usize, HighlightStyle)>>,
  91    chunk: Option<&'a str>,
  92    run_start: usize,
  93    offset: usize,
  94}
  95
  96impl BlockMap {
  97    pub fn new(buffer: ModelHandle<Buffer>, wrap_snapshot: WrapSnapshot) -> Self {
  98        Self {
  99            buffer,
 100            next_block_id: AtomicUsize::new(0),
 101            blocks: Vec::new(),
 102            transforms: Mutex::new(SumTree::from_item(
 103                Transform::isomorphic(wrap_snapshot.text_summary().lines),
 104                &(),
 105            )),
 106            wrap_snapshot: Mutex::new(wrap_snapshot),
 107        }
 108    }
 109
 110    pub fn read(
 111        &self,
 112        wrap_snapshot: WrapSnapshot,
 113        edits: Vec<WrapEdit>,
 114        cx: &AppContext,
 115    ) -> BlockSnapshot {
 116        self.sync(&wrap_snapshot, edits, cx);
 117        *self.wrap_snapshot.lock() = wrap_snapshot.clone();
 118        BlockSnapshot {
 119            wrap_snapshot,
 120            transforms: self.transforms.lock().clone(),
 121        }
 122    }
 123
 124    pub fn write(
 125        &mut self,
 126        wrap_snapshot: WrapSnapshot,
 127        edits: Vec<WrapEdit>,
 128        cx: &AppContext,
 129    ) -> BlockMapWriter {
 130        self.sync(&wrap_snapshot, edits, cx);
 131        *self.wrap_snapshot.lock() = wrap_snapshot;
 132        BlockMapWriter(self)
 133    }
 134
 135    pub fn sync(&self, wrap_snapshot: &WrapSnapshot, edits: Vec<WrapEdit>, cx: &AppContext) {
 136        if edits.is_empty() {
 137            return;
 138        }
 139
 140        let buffer = self.buffer.read(cx);
 141        let mut transforms = self.transforms.lock();
 142        let mut new_transforms = SumTree::new();
 143        let old_max_point = WrapPoint(transforms.summary().input);
 144        let new_max_point = wrap_snapshot.max_point();
 145        let mut cursor = transforms.cursor::<WrapPoint>();
 146        let mut last_block_ix = 0;
 147        let mut blocks_in_edit = Vec::new();
 148        let mut edits = edits.into_iter().peekable();
 149
 150        while let Some(edit) = edits.next() {
 151            // Preserve any old transforms that precede this edit.
 152            let old_start = WrapPoint::new(edit.old.start, 0);
 153            let new_start = WrapPoint::new(edit.new.start, 0);
 154            new_transforms.push_tree(cursor.slice(&old_start, Bias::Left, &()), &());
 155
 156            // Preserve any portion of an old transform that precedes this edit.
 157            let extent_before_edit = old_start.0 - cursor.start().0;
 158            if !extent_before_edit.is_zero() {
 159                push_isomorphic(&mut new_transforms, extent_before_edit);
 160            }
 161
 162            // Skip over any old transforms that intersect this edit.
 163            let mut old_end = WrapPoint::new(edit.old.end, 0);
 164            let mut new_end = WrapPoint::new(edit.new.end, 0);
 165            cursor.seek(&old_end, Bias::Left, &());
 166            cursor.next(&());
 167
 168            // Combine this edit with any subsequent edits that intersect the same transform.
 169            while let Some(next_edit) = edits.peek() {
 170                if next_edit.old.start <= cursor.start().row() {
 171                    old_end = WrapPoint::new(next_edit.old.end, 0);
 172                    new_end = WrapPoint::new(next_edit.new.end, 0);
 173                    cursor.seek(&old_end, Bias::Left, &());
 174                    cursor.next(&());
 175                    edits.next();
 176                } else {
 177                    break;
 178                }
 179            }
 180
 181            // Find the blocks within this edited region.
 182            let new_start = wrap_snapshot.to_point(new_start, Bias::Left);
 183            let start_anchor = buffer.anchor_before(new_start);
 184            let start_block_ix = match self.blocks[last_block_ix..].binary_search_by(|probe| {
 185                probe
 186                    .position
 187                    .cmp(&start_anchor, buffer)
 188                    .unwrap()
 189                    .then(Ordering::Greater)
 190            }) {
 191                Ok(ix) | Err(ix) => last_block_ix + ix,
 192            };
 193            let end_block_ix = if new_end.row() > wrap_snapshot.max_point().row() {
 194                self.blocks.len()
 195            } else {
 196                let new_end = wrap_snapshot.to_point(new_end, Bias::Left);
 197                let end_anchor = buffer.anchor_before(new_end);
 198                match self.blocks[start_block_ix..].binary_search_by(|probe| {
 199                    probe
 200                        .position
 201                        .cmp(&end_anchor, buffer)
 202                        .unwrap()
 203                        .then(Ordering::Greater)
 204                }) {
 205                    Ok(ix) | Err(ix) => start_block_ix + ix,
 206                }
 207            };
 208            last_block_ix = end_block_ix;
 209            blocks_in_edit.clear();
 210            blocks_in_edit.extend(
 211                self.blocks[start_block_ix..end_block_ix]
 212                    .iter()
 213                    .map(|block| {
 214                        let mut position = block.position.to_point(buffer);
 215                        match block.disposition {
 216                            BlockDisposition::Above => position.column = 0,
 217                            BlockDisposition::Below => {
 218                                position.column = buffer.line_len(position.row)
 219                            }
 220                        }
 221                        let position = wrap_snapshot.from_point(position, Bias::Left);
 222                        (position.row(), block)
 223                    }),
 224            );
 225            blocks_in_edit.sort_unstable_by_key(|(row, block)| (*row, block.disposition, block.id));
 226
 227            // For each of these blocks, insert a new isomorphic transform preceding the block,
 228            // and then insert the block itself.
 229            for (block_row, block) in blocks_in_edit.iter().copied() {
 230                let new_transforms_end = new_transforms.summary().input;
 231                if block.disposition.is_above() {
 232                    if block_row > new_transforms_end.row {
 233                        push_isomorphic(
 234                            &mut new_transforms,
 235                            Point::new(block_row, 0) - new_transforms_end,
 236                        )
 237                    }
 238                } else {
 239                    if block_row >= new_transforms_end.row {
 240                        push_isomorphic(
 241                            &mut new_transforms,
 242                            Point::new(block_row, wrap_snapshot.line_len(block_row))
 243                                - new_transforms_end,
 244                        );
 245                    }
 246                }
 247
 248                new_transforms.push(Transform::block(block.clone()), &());
 249            }
 250
 251            old_end = old_end.min(old_max_point);
 252            new_end = new_end.min(new_max_point);
 253
 254            // Insert an isomorphic transform after the final block.
 255            let extent_after_last_block = new_end.0 - new_transforms.summary().input;
 256            if !extent_after_last_block.is_zero() {
 257                push_isomorphic(&mut new_transforms, extent_after_last_block);
 258            }
 259
 260            // Preserve any portion of the old transform after this edit.
 261            let extent_after_edit = cursor.start().0 - old_end.0;
 262            if !extent_after_edit.is_zero() {
 263                push_isomorphic(&mut new_transforms, extent_after_edit);
 264            }
 265        }
 266
 267        new_transforms.push_tree(cursor.suffix(&()), &());
 268        debug_assert_eq!(new_transforms.summary().input, wrap_snapshot.max_point().0);
 269
 270        drop(cursor);
 271        *transforms = new_transforms;
 272    }
 273}
 274
 275fn push_isomorphic(tree: &mut SumTree<Transform>, extent: Point) {
 276    let mut extent = Some(extent);
 277    tree.update_last(
 278        |last_transform| {
 279            if last_transform.is_isomorphic() {
 280                let extent = extent.take().unwrap();
 281                last_transform.summary.input += &extent;
 282                last_transform.summary.output += &extent;
 283            }
 284        },
 285        &(),
 286    );
 287    if let Some(extent) = extent {
 288        tree.push(Transform::isomorphic(extent), &());
 289    }
 290}
 291
 292impl BlockPoint {
 293    fn new(row: u32, column: u32) -> Self {
 294        Self(Point::new(row, column))
 295    }
 296}
 297
 298impl std::ops::Deref for BlockPoint {
 299    type Target = Point;
 300
 301    fn deref(&self) -> &Self::Target {
 302        &self.0
 303    }
 304}
 305
 306impl std::ops::DerefMut for BlockPoint {
 307    fn deref_mut(&mut self) -> &mut Self::Target {
 308        &mut self.0
 309    }
 310}
 311
 312impl<'a> BlockMapWriter<'a> {
 313    pub fn insert<P, T>(
 314        &mut self,
 315        blocks: impl IntoIterator<Item = BlockProperties<P, T>>,
 316        cx: &AppContext,
 317    ) -> Vec<BlockId>
 318    where
 319        P: ToOffset + Clone,
 320        T: Into<Rope> + Clone,
 321    {
 322        let buffer = self.0.buffer.read(cx);
 323        let mut ids = Vec::new();
 324        let mut edits = Vec::<Edit<u32>>::new();
 325        let wrap_snapshot = &*self.0.wrap_snapshot.lock();
 326
 327        for block in blocks {
 328            let id = BlockId(self.0.next_block_id.fetch_add(1, SeqCst));
 329            ids.push(id);
 330
 331            let position = buffer.anchor_before(block.position);
 332            let point = position.to_point(buffer);
 333            let start_row = wrap_snapshot
 334                .from_point(Point::new(point.row, 0), Bias::Left)
 335                .row();
 336            let end_row = if point.row == buffer.max_point().row {
 337                wrap_snapshot.max_point().row() + 1
 338            } else {
 339                wrap_snapshot
 340                    .from_point(Point::new(point.row + 1, 0), Bias::Left)
 341                    .row()
 342            };
 343
 344            let block_ix = match self
 345                .0
 346                .blocks
 347                .binary_search_by(|probe| probe.position.cmp(&position, buffer).unwrap())
 348            {
 349                Ok(ix) | Err(ix) => ix,
 350            };
 351            let mut text = block.text.into();
 352            if block.disposition.is_above() {
 353                text.push("\n");
 354            } else {
 355                text.push_front("\n");
 356            }
 357
 358            self.0.blocks.insert(
 359                block_ix,
 360                Arc::new(Block {
 361                    id,
 362                    position,
 363                    text,
 364                    runs: block.runs,
 365                    disposition: block.disposition,
 366                }),
 367            );
 368
 369            if let Err(edit_ix) = edits.binary_search_by_key(&start_row, |edit| edit.old.start) {
 370                edits.insert(
 371                    edit_ix,
 372                    Edit {
 373                        old: start_row..end_row,
 374                        new: start_row..end_row,
 375                    },
 376                );
 377            }
 378        }
 379
 380        self.0.sync(wrap_snapshot, edits, cx);
 381        ids
 382    }
 383
 384    pub fn remove(&mut self, block_ids: HashSet<BlockId>, cx: &AppContext) {
 385        let buffer = self.0.buffer.read(cx);
 386        let wrap_snapshot = &*self.0.wrap_snapshot.lock();
 387        let mut edits = Vec::new();
 388        let mut last_block_buffer_row = None;
 389        self.0.blocks.retain(|block| {
 390            if block_ids.contains(&block.id) {
 391                let buffer_row = block.position.to_point(buffer).row;
 392                if last_block_buffer_row != Some(buffer_row) {
 393                    last_block_buffer_row = Some(buffer_row);
 394                    let start_row = wrap_snapshot
 395                        .from_point(Point::new(buffer_row, 0), Bias::Left)
 396                        .row();
 397                    let end_row = wrap_snapshot
 398                        .from_point(
 399                            Point::new(buffer_row, buffer.line_len(buffer_row)),
 400                            Bias::Left,
 401                        )
 402                        .row()
 403                        + 1;
 404                    edits.push(Edit {
 405                        old: start_row..end_row,
 406                        new: start_row..end_row,
 407                    })
 408                }
 409                false
 410            } else {
 411                true
 412            }
 413        });
 414        self.0.sync(wrap_snapshot, edits, cx);
 415    }
 416}
 417
 418impl BlockSnapshot {
 419    #[cfg(test)]
 420    fn text(&mut self) -> String {
 421        self.highlighted_chunks_for_rows(0..self.max_point().0.row + 1)
 422            .map(|chunk| chunk.text)
 423            .collect()
 424    }
 425
 426    pub fn highlighted_chunks_for_rows(&mut self, rows: Range<u32>) -> HighlightedChunks {
 427        let max_output_position = self.max_point().min(BlockPoint::new(rows.end, 0));
 428        let mut cursor = self.transforms.cursor::<(BlockPoint, WrapPoint)>();
 429        let output_position = BlockPoint::new(rows.start, 0);
 430        cursor.seek(&output_position, Bias::Right, &());
 431        let (input_start, output_start) = cursor.start();
 432        let row_overshoot = rows.start - output_start.0.row;
 433        let input_start_row = input_start.0.row + row_overshoot;
 434        let input_end_row = self.to_wrap_point(BlockPoint::new(rows.end, 0)).row();
 435        let input_chunks = self
 436            .wrap_snapshot
 437            .highlighted_chunks_for_rows(input_start_row..input_end_row);
 438        HighlightedChunks {
 439            input_chunks,
 440            input_chunk: Default::default(),
 441            block_chunks: None,
 442            transforms: cursor,
 443            output_position,
 444            max_output_position,
 445        }
 446    }
 447
 448    pub fn max_point(&self) -> BlockPoint {
 449        BlockPoint(self.transforms.summary().output)
 450    }
 451
 452    pub fn clip_point(&self, point: BlockPoint, bias: Bias) -> BlockPoint {
 453        let mut cursor = self.transforms.cursor::<(BlockPoint, WrapPoint)>();
 454        cursor.seek(&point, Bias::Right, &());
 455        if let Some(transform) = cursor.prev_item() {
 456            if transform.is_isomorphic() && point == cursor.start().0 {
 457                return point;
 458            }
 459        }
 460        if let Some(transform) = cursor.item() {
 461            if transform.is_isomorphic() {
 462                let (output_start, input_start) = cursor.start();
 463                let output_overshoot = point.0 - output_start.0;
 464                let input_point = self
 465                    .wrap_snapshot
 466                    .clip_point(WrapPoint(input_start.0 + output_overshoot), bias);
 467                let input_overshoot = input_point.0 - input_start.0;
 468                BlockPoint(output_start.0 + input_overshoot)
 469            } else {
 470                if bias == Bias::Left && cursor.start().1 .0 > Point::zero()
 471                    || cursor.end(&()).1 == self.wrap_snapshot.max_point()
 472                {
 473                    loop {
 474                        cursor.prev(&());
 475                        let transform = cursor.item().unwrap();
 476                        if transform.is_isomorphic() {
 477                            return BlockPoint(cursor.end(&()).0 .0);
 478                        }
 479                    }
 480                } else {
 481                    loop {
 482                        cursor.next(&());
 483                        let transform = cursor.item().unwrap();
 484                        if transform.is_isomorphic() {
 485                            return BlockPoint(cursor.start().0 .0);
 486                        }
 487                    }
 488                }
 489            }
 490        } else {
 491            self.max_point()
 492        }
 493    }
 494
 495    pub fn to_block_point(&self, wrap_point: WrapPoint) -> BlockPoint {
 496        let mut cursor = self.transforms.cursor::<(WrapPoint, BlockPoint)>();
 497        cursor.seek(&wrap_point, Bias::Right, &());
 498        while let Some(item) = cursor.item() {
 499            if item.is_isomorphic() {
 500                break;
 501            }
 502            cursor.next(&());
 503        }
 504        let (input_start, output_start) = cursor.start();
 505        let input_overshoot = wrap_point.0 - input_start.0;
 506        BlockPoint(output_start.0 + input_overshoot)
 507    }
 508
 509    pub fn to_wrap_point(&self, block_point: BlockPoint) -> WrapPoint {
 510        let mut cursor = self.transforms.cursor::<(BlockPoint, WrapPoint)>();
 511        cursor.seek(&block_point, Bias::Right, &());
 512        let (output_start, input_start) = cursor.start();
 513        let output_overshoot = block_point.0 - output_start.0;
 514        WrapPoint(input_start.0 + output_overshoot)
 515    }
 516}
 517
 518impl Transform {
 519    fn isomorphic(lines: Point) -> Self {
 520        Self {
 521            summary: TransformSummary {
 522                input: lines,
 523                output: lines,
 524            },
 525            block: None,
 526        }
 527    }
 528
 529    fn block(block: Arc<Block>) -> Self {
 530        Self {
 531            summary: TransformSummary {
 532                input: Default::default(),
 533                output: block.text.summary().lines,
 534            },
 535            block: Some(block),
 536        }
 537    }
 538
 539    fn is_isomorphic(&self) -> bool {
 540        self.block.is_none()
 541    }
 542}
 543
 544impl<'a> Iterator for HighlightedChunks<'a> {
 545    type Item = HighlightedChunk<'a>;
 546
 547    fn next(&mut self) -> Option<Self::Item> {
 548        if self.output_position >= self.max_output_position {
 549            return None;
 550        }
 551
 552        if let Some(block_chunks) = self.block_chunks.as_mut() {
 553            if let Some(block_chunk) = block_chunks.next() {
 554                self.output_position.0 += Point::from_str(block_chunk.text);
 555                return Some(block_chunk);
 556            } else {
 557                self.block_chunks.take();
 558            }
 559        }
 560
 561        let transform = self.transforms.item()?;
 562        if let Some(block) = transform.block.as_ref() {
 563            let block_start = self.transforms.start().0 .0;
 564            let block_end = self.transforms.end(&()).0 .0;
 565            let start_in_block = self.output_position.0 - block_start;
 566            let end_in_block = cmp::min(self.max_output_position.0, block_end) - block_start;
 567            self.transforms.next(&());
 568            let mut block_chunks = BlockChunks::new(block, start_in_block..end_in_block);
 569            if let Some(block_chunk) = block_chunks.next() {
 570                self.output_position.0 += Point::from_str(block_chunk.text);
 571                return Some(block_chunk);
 572            }
 573        }
 574
 575        if self.input_chunk.text.is_empty() {
 576            if let Some(input_chunk) = self.input_chunks.next() {
 577                self.input_chunk = input_chunk;
 578            }
 579        }
 580
 581        let transform_end = self.transforms.end(&()).0 .0;
 582        let (prefix_lines, prefix_bytes) = offset_for_point(
 583            self.input_chunk.text,
 584            transform_end - self.output_position.0,
 585        );
 586        self.output_position.0 += prefix_lines;
 587        let (prefix, suffix) = self.input_chunk.text.split_at(prefix_bytes);
 588        self.input_chunk.text = suffix;
 589        if self.output_position.0 == transform_end {
 590            self.transforms.next(&());
 591        }
 592
 593        Some(HighlightedChunk {
 594            text: prefix,
 595            ..self.input_chunk
 596        })
 597    }
 598}
 599
 600impl<'a> BlockChunks<'a> {
 601    fn new(block: &'a Block, point_range: Range<Point>) -> Self {
 602        let offset_range = block.text.point_to_offset(point_range.start)
 603            ..block.text.point_to_offset(point_range.end);
 604
 605        let mut runs = block.runs.iter().peekable();
 606        let mut run_start = 0;
 607        while let Some((run_len, _)) = runs.peek() {
 608            let run_end = run_start + run_len;
 609            if run_end <= offset_range.start {
 610                run_start = run_end;
 611                runs.next();
 612            } else {
 613                break;
 614            }
 615        }
 616
 617        Self {
 618            chunk: None,
 619            run_start,
 620            chunks: block.text.chunks_in_range(offset_range.clone()),
 621            runs,
 622            offset: offset_range.start,
 623        }
 624    }
 625}
 626
 627impl<'a> Iterator for BlockChunks<'a> {
 628    type Item = HighlightedChunk<'a>;
 629
 630    fn next(&mut self) -> Option<Self::Item> {
 631        if self.chunk.is_none() {
 632            self.chunk = self.chunks.next();
 633        }
 634
 635        let chunk = self.chunk?;
 636        let mut chunk_len = chunk.len();
 637        // let mut highlight_style = None;
 638        if let Some((run_len, _)) = self.runs.peek() {
 639            // highlight_style = Some(style.clone());
 640            let run_end_in_chunk = self.run_start + run_len - self.offset;
 641            if run_end_in_chunk <= chunk_len {
 642                chunk_len = run_end_in_chunk;
 643                self.run_start += run_len;
 644                self.runs.next();
 645            }
 646        }
 647
 648        self.offset += chunk_len;
 649        let (chunk, suffix) = chunk.split_at(chunk_len);
 650        self.chunk = if suffix.is_empty() {
 651            None
 652        } else {
 653            Some(suffix)
 654        };
 655
 656        Some(HighlightedChunk {
 657            text: chunk,
 658            highlight_id: Default::default(),
 659            diagnostic: None,
 660        })
 661    }
 662}
 663
 664impl sum_tree::Item for Transform {
 665    type Summary = TransformSummary;
 666
 667    fn summary(&self) -> Self::Summary {
 668        self.summary.clone()
 669    }
 670}
 671
 672impl sum_tree::Summary for TransformSummary {
 673    type Context = ();
 674
 675    fn add_summary(&mut self, summary: &Self, _: &()) {
 676        self.input += summary.input;
 677        self.output += summary.output;
 678    }
 679}
 680
 681impl<'a> sum_tree::Dimension<'a, TransformSummary> for WrapPoint {
 682    fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
 683        self.0 += summary.input;
 684    }
 685}
 686
 687impl<'a> sum_tree::Dimension<'a, TransformSummary> for BlockPoint {
 688    fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
 689        self.0 += summary.output;
 690    }
 691}
 692
 693impl BlockDisposition {
 694    fn is_above(&self) -> bool {
 695        matches!(self, BlockDisposition::Above)
 696    }
 697}
 698
 699// Count the number of bytes prior to a target point. If the string doesn't contain the target
 700// point, return its total extent. Otherwise return the target point itself.
 701fn offset_for_point(s: &str, target: Point) -> (Point, usize) {
 702    let mut point = Point::zero();
 703    let mut offset = 0;
 704    for (row, line) in s.split('\n').enumerate().take(target.row as usize + 1) {
 705        let row = row as u32;
 706        if row > 0 {
 707            offset += 1;
 708        }
 709        point.row = row;
 710        point.column = if row == target.row {
 711            cmp::min(line.len() as u32, target.column)
 712        } else {
 713            line.len() as u32
 714        };
 715        offset += point.column as usize;
 716    }
 717    (point, offset)
 718}
 719
 720#[cfg(test)]
 721mod tests {
 722    use super::*;
 723    use crate::display_map::{fold_map::FoldMap, tab_map::TabMap, wrap_map::WrapMap};
 724    use buffer::RandomCharIter;
 725    use language::Buffer;
 726    use rand::prelude::*;
 727    use std::env;
 728
 729    #[gpui::test]
 730    fn test_basic_blocks(cx: &mut gpui::MutableAppContext) {
 731        let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
 732        let font_id = cx
 733            .font_cache()
 734            .select_font(family_id, &Default::default())
 735            .unwrap();
 736
 737        let text = "aaa\nbbb\nccc\nddd";
 738
 739        let buffer = cx.add_model(|cx| Buffer::new(0, text, cx));
 740        let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
 741        let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), 1);
 742        let (wrap_map, wraps_snapshot) = WrapMap::new(tabs_snapshot, font_id, 14.0, None, cx);
 743        let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot.clone());
 744
 745        let mut writer = block_map.write(wraps_snapshot.clone(), vec![], cx);
 746        writer.insert(
 747            vec![
 748                BlockProperties {
 749                    position: Point::new(1, 0),
 750                    text: "BLOCK 1",
 751                    disposition: BlockDisposition::Above,
 752                    runs: vec![],
 753                },
 754                BlockProperties {
 755                    position: Point::new(1, 2),
 756                    text: "BLOCK 2",
 757                    disposition: BlockDisposition::Above,
 758                    runs: vec![],
 759                },
 760                BlockProperties {
 761                    position: Point::new(3, 2),
 762                    text: "BLOCK 3",
 763                    disposition: BlockDisposition::Below,
 764                    runs: vec![],
 765                },
 766            ],
 767            cx,
 768        );
 769
 770        let mut snapshot = block_map.read(wraps_snapshot, vec![], cx);
 771        assert_eq!(
 772            snapshot.text(),
 773            "aaa\nBLOCK 1\nBLOCK 2\nbbb\nccc\nddd\nBLOCK 3"
 774        );
 775        assert_eq!(
 776            snapshot.to_block_point(WrapPoint::new(1, 0)),
 777            BlockPoint::new(3, 0)
 778        );
 779        assert_eq!(
 780            snapshot.clip_point(BlockPoint::new(1, 0), Bias::Left),
 781            BlockPoint::new(1, 0)
 782        );
 783        assert_eq!(
 784            snapshot.clip_point(BlockPoint::new(1, 0), Bias::Right),
 785            BlockPoint::new(1, 0)
 786        );
 787        assert_eq!(
 788            snapshot.clip_point(BlockPoint::new(1, 1), Bias::Left),
 789            BlockPoint::new(1, 0)
 790        );
 791        assert_eq!(
 792            snapshot.clip_point(BlockPoint::new(1, 1), Bias::Right),
 793            BlockPoint::new(3, 0)
 794        );
 795        assert_eq!(
 796            snapshot.clip_point(BlockPoint::new(3, 0), Bias::Left),
 797            BlockPoint::new(3, 0)
 798        );
 799        assert_eq!(
 800            snapshot.clip_point(BlockPoint::new(3, 0), Bias::Right),
 801            BlockPoint::new(3, 0)
 802        );
 803        assert_eq!(
 804            snapshot.clip_point(BlockPoint::new(5, 3), Bias::Left),
 805            BlockPoint::new(5, 3)
 806        );
 807        assert_eq!(
 808            snapshot.clip_point(BlockPoint::new(5, 3), Bias::Right),
 809            BlockPoint::new(5, 3)
 810        );
 811        assert_eq!(
 812            snapshot.clip_point(BlockPoint::new(6, 0), Bias::Left),
 813            BlockPoint::new(5, 3)
 814        );
 815        assert_eq!(
 816            snapshot.clip_point(BlockPoint::new(6, 0), Bias::Right),
 817            BlockPoint::new(5, 3)
 818        );
 819
 820        // Insert a line break, separating two block decorations into separate
 821        // lines.
 822        buffer.update(cx, |buffer, cx| {
 823            buffer.edit([Point::new(1, 1)..Point::new(1, 1)], "!!!\n", cx)
 824        });
 825
 826        let (folds_snapshot, fold_edits) = fold_map.read(cx);
 827        let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
 828        let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
 829            wrap_map.sync(tabs_snapshot, tab_edits, cx)
 830        });
 831        let mut snapshot = block_map.read(wraps_snapshot, wrap_edits, cx);
 832        assert_eq!(
 833            snapshot.text(),
 834            "aaa\nBLOCK 1\nb!!!\nBLOCK 2\nbb\nccc\nddd\nBLOCK 3"
 835        );
 836    }
 837
 838    #[gpui::test]
 839    fn test_blocks_on_wrapped_lines(cx: &mut gpui::MutableAppContext) {
 840        let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
 841        let font_id = cx
 842            .font_cache()
 843            .select_font(family_id, &Default::default())
 844            .unwrap();
 845
 846        let text = "one two three\nfour five six\nseven eight";
 847
 848        let buffer = cx.add_model(|cx| Buffer::new(0, text, cx));
 849        let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
 850        let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), 1);
 851        let (wrap_map, wraps_snapshot) = WrapMap::new(tabs_snapshot, font_id, 14.0, Some(60.), cx);
 852        let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot.clone());
 853
 854        let mut writer = block_map.write(wraps_snapshot.clone(), vec![], cx);
 855        writer.insert(
 856            vec![
 857                BlockProperties {
 858                    position: Point::new(1, 12),
 859                    text: "BLOCK 1",
 860                    disposition: BlockDisposition::Above,
 861                    runs: vec![],
 862                },
 863                BlockProperties {
 864                    position: Point::new(1, 1),
 865                    text: "BLOCK 2",
 866                    disposition: BlockDisposition::Below,
 867                    runs: vec![],
 868                },
 869            ],
 870            cx,
 871        );
 872
 873        // Blocks with an 'above' disposition go above their corresponding buffer line.
 874        // Blocks with a 'below' disposition go below their corresponding buffer line.
 875        let mut snapshot = block_map.read(wraps_snapshot, vec![], cx);
 876        assert_eq!(
 877            snapshot.text(),
 878            "one two \nthree\nBLOCK 1\nfour five \nsix\nBLOCK 2\nseven \neight"
 879        );
 880    }
 881
 882    #[gpui::test(iterations = 100)]
 883    fn test_random_blocks(cx: &mut gpui::MutableAppContext, mut rng: StdRng) {
 884        let operations = env::var("OPERATIONS")
 885            .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
 886            .unwrap_or(10);
 887
 888        let wrap_width = if rng.gen_bool(0.2) {
 889            None
 890        } else {
 891            Some(rng.gen_range(0.0..=100.0))
 892        };
 893        let tab_size = 1;
 894        let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
 895        let font_id = cx
 896            .font_cache()
 897            .select_font(family_id, &Default::default())
 898            .unwrap();
 899        let font_size = 14.0;
 900
 901        log::info!("Wrap width: {:?}", wrap_width);
 902
 903        let buffer = cx.add_model(|cx| {
 904            let len = rng.gen_range(0..10);
 905            let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
 906            log::info!("initial buffer text: {:?}", text);
 907            Buffer::new(0, text, cx)
 908        });
 909        let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
 910        let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), tab_size);
 911        let (wrap_map, wraps_snapshot) =
 912            WrapMap::new(tabs_snapshot, font_id, font_size, wrap_width, cx);
 913        let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot);
 914        let mut expected_blocks = Vec::new();
 915
 916        for _ in 0..operations {
 917            match rng.gen_range(0..=100) {
 918                0..=19 => {
 919                    let wrap_width = if rng.gen_bool(0.2) {
 920                        None
 921                    } else {
 922                        Some(rng.gen_range(0.0..=100.0))
 923                    };
 924                    log::info!("Setting wrap width to {:?}", wrap_width);
 925                    wrap_map.update(cx, |map, cx| map.set_wrap_width(wrap_width, cx));
 926                }
 927                20..=39 => {
 928                    let block_count = rng.gen_range(1..=1);
 929                    let block_properties = (0..block_count)
 930                        .map(|_| {
 931                            let buffer = buffer.read(cx);
 932                            let position = buffer.anchor_before(rng.gen_range(0..=buffer.len()));
 933
 934                            let len = rng.gen_range(0..10);
 935                            let text = Rope::from(
 936                                RandomCharIter::new(&mut rng)
 937                                    .take(len)
 938                                    .collect::<String>()
 939                                    .as_str(),
 940                            );
 941                            let disposition = if rng.gen() {
 942                                BlockDisposition::Above
 943                            } else {
 944                                BlockDisposition::Below
 945                            };
 946                            log::info!(
 947                                "inserting block {:?} {:?} with text {:?}",
 948                                disposition,
 949                                position.to_point(buffer),
 950                                text.to_string()
 951                            );
 952                            BlockProperties {
 953                                position,
 954                                text,
 955                                runs: Vec::<(usize, HighlightStyle)>::new(),
 956                                disposition,
 957                            }
 958                        })
 959                        .collect::<Vec<_>>();
 960
 961                    let (folds_snapshot, fold_edits) = fold_map.read(cx);
 962                    let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
 963                    let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
 964                        wrap_map.sync(tabs_snapshot, tab_edits, cx)
 965                    });
 966                    let mut block_map = block_map.write(wraps_snapshot, wrap_edits, cx);
 967                    let block_ids = block_map.insert(block_properties.clone(), cx);
 968                    for (block_id, props) in block_ids.into_iter().zip(block_properties) {
 969                        expected_blocks.push((block_id, props));
 970                    }
 971                }
 972                40..=59 if !expected_blocks.is_empty() => {
 973                    let block_count = rng.gen_range(1..=4.min(expected_blocks.len()));
 974                    let block_ids_to_remove = (0..block_count)
 975                        .map(|_| {
 976                            expected_blocks
 977                                .remove(rng.gen_range(0..expected_blocks.len()))
 978                                .0
 979                        })
 980                        .collect();
 981
 982                    let (folds_snapshot, fold_edits) = fold_map.read(cx);
 983                    let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
 984                    let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
 985                        wrap_map.sync(tabs_snapshot, tab_edits, cx)
 986                    });
 987                    let mut block_map = block_map.write(wraps_snapshot, wrap_edits, cx);
 988                    block_map.remove(block_ids_to_remove, cx);
 989                }
 990                _ => {
 991                    buffer.update(cx, |buffer, _| {
 992                        buffer.randomly_edit(&mut rng, 1);
 993                        log::info!("buffer text: {:?}", buffer.text());
 994                    });
 995                }
 996            }
 997
 998            let (folds_snapshot, fold_edits) = fold_map.read(cx);
 999            let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1000            let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1001                wrap_map.sync(tabs_snapshot, tab_edits, cx)
1002            });
1003            let mut blocks_snapshot = block_map.read(wraps_snapshot.clone(), wrap_edits, cx);
1004            assert_eq!(
1005                blocks_snapshot.transforms.summary().input,
1006                wraps_snapshot.max_point().0
1007            );
1008            log::info!("blocks text: {:?}", blocks_snapshot.text());
1009
1010            let buffer = buffer.read(cx);
1011            let mut sorted_blocks = expected_blocks
1012                .iter()
1013                .cloned()
1014                .map(|(id, block)| {
1015                    let mut position = block.position.to_point(buffer);
1016                    match block.disposition {
1017                        BlockDisposition::Above => {
1018                            position.column = 0;
1019                        }
1020                        BlockDisposition::Below => {
1021                            position.column = buffer.line_len(position.row);
1022                        }
1023                    };
1024                    let row = wraps_snapshot.from_point(position, Bias::Left).row();
1025                    (
1026                        id,
1027                        BlockProperties {
1028                            position: row,
1029                            text: block.text,
1030                            runs: block.runs,
1031                            disposition: block.disposition,
1032                        },
1033                    )
1034                })
1035                .collect::<Vec<_>>();
1036            sorted_blocks
1037                .sort_unstable_by_key(|(id, block)| (block.position, block.disposition, *id));
1038            let mut sorted_blocks = sorted_blocks.into_iter().peekable();
1039
1040            let mut expected_text = String::new();
1041            let input_text = wraps_snapshot.text();
1042            for (row, input_line) in input_text.split('\n').enumerate() {
1043                let row = row as u32;
1044                if row > 0 {
1045                    expected_text.push('\n');
1046                }
1047
1048                while let Some((_, block)) = sorted_blocks.peek() {
1049                    if block.position == row && block.disposition == BlockDisposition::Above {
1050                        expected_text.extend(block.text.chunks());
1051                        expected_text.push('\n');
1052                        sorted_blocks.next();
1053                    } else {
1054                        break;
1055                    }
1056                }
1057
1058                expected_text.push_str(input_line);
1059
1060                while let Some((_, block)) = sorted_blocks.peek() {
1061                    if block.position == row && block.disposition == BlockDisposition::Below {
1062                        expected_text.push('\n');
1063                        expected_text.extend(block.text.chunks());
1064                        sorted_blocks.next();
1065                    } else {
1066                        break;
1067                    }
1068                }
1069            }
1070
1071            assert_eq!(blocks_snapshot.text(), expected_text);
1072        }
1073    }
1074}