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