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