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