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