1use crate::{
   2    multi_buffer::{MultiBufferChunks, MultiBufferRows},
   3    Anchor, InlayId, MultiBufferSnapshot, ToOffset,
   4};
   5use collections::{BTreeSet, HashMap};
   6use gpui::fonts::HighlightStyle;
   7use language::{Chunk, Edit, Point, Rope, TextSummary};
   8use std::{
   9    cmp,
  10    ops::{Add, AddAssign, Range, Sub, SubAssign},
  11};
  12use sum_tree::{Bias, Cursor, SumTree};
  13use text::Patch;
  14
  15pub struct InlayMap {
  16    snapshot: InlaySnapshot,
  17    inlays_by_id: HashMap<InlayId, Inlay>,
  18    inlays: Vec<Inlay>,
  19}
  20
  21#[derive(Clone)]
  22pub struct InlaySnapshot {
  23    pub buffer: MultiBufferSnapshot,
  24    transforms: SumTree<Transform>,
  25    pub version: usize,
  26}
  27
  28#[derive(Clone, Debug)]
  29enum Transform {
  30    Isomorphic(TextSummary),
  31    Inlay(Inlay),
  32}
  33
  34#[derive(Debug, Clone)]
  35pub struct Inlay {
  36    pub id: InlayId,
  37    pub position: Anchor,
  38    pub text: text::Rope,
  39}
  40
  41#[derive(Debug, Clone)]
  42pub struct InlayProperties<T> {
  43    pub position: Anchor,
  44    pub text: T,
  45}
  46
  47impl sum_tree::Item for Transform {
  48    type Summary = TransformSummary;
  49
  50    fn summary(&self) -> Self::Summary {
  51        match self {
  52            Transform::Isomorphic(summary) => TransformSummary {
  53                input: summary.clone(),
  54                output: summary.clone(),
  55            },
  56            Transform::Inlay(inlay) => TransformSummary {
  57                input: TextSummary::default(),
  58                output: inlay.text.summary(),
  59            },
  60        }
  61    }
  62}
  63
  64#[derive(Clone, Debug, Default)]
  65struct TransformSummary {
  66    input: TextSummary,
  67    output: TextSummary,
  68}
  69
  70impl sum_tree::Summary for TransformSummary {
  71    type Context = ();
  72
  73    fn add_summary(&mut self, other: &Self, _: &()) {
  74        self.input += &other.input;
  75        self.output += &other.output;
  76    }
  77}
  78
  79pub type InlayEdit = Edit<InlayOffset>;
  80
  81#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
  82pub struct InlayOffset(pub usize);
  83
  84impl Add for InlayOffset {
  85    type Output = Self;
  86
  87    fn add(self, rhs: Self) -> Self::Output {
  88        Self(self.0 + rhs.0)
  89    }
  90}
  91
  92impl Sub for InlayOffset {
  93    type Output = Self;
  94
  95    fn sub(self, rhs: Self) -> Self::Output {
  96        Self(self.0 - rhs.0)
  97    }
  98}
  99
 100impl AddAssign for InlayOffset {
 101    fn add_assign(&mut self, rhs: Self) {
 102        self.0 += rhs.0;
 103    }
 104}
 105
 106impl SubAssign for InlayOffset {
 107    fn sub_assign(&mut self, rhs: Self) {
 108        self.0 -= rhs.0;
 109    }
 110}
 111
 112impl<'a> sum_tree::Dimension<'a, TransformSummary> for InlayOffset {
 113    fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
 114        self.0 += &summary.output.len;
 115    }
 116}
 117
 118#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
 119pub struct InlayPoint(pub Point);
 120
 121impl Add for InlayPoint {
 122    type Output = Self;
 123
 124    fn add(self, rhs: Self) -> Self::Output {
 125        Self(self.0 + rhs.0)
 126    }
 127}
 128
 129impl Sub for InlayPoint {
 130    type Output = Self;
 131
 132    fn sub(self, rhs: Self) -> Self::Output {
 133        Self(self.0 - rhs.0)
 134    }
 135}
 136
 137impl<'a> sum_tree::Dimension<'a, TransformSummary> for InlayPoint {
 138    fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
 139        self.0 += &summary.output.lines;
 140    }
 141}
 142
 143impl<'a> sum_tree::Dimension<'a, TransformSummary> for usize {
 144    fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
 145        *self += &summary.input.len;
 146    }
 147}
 148
 149impl<'a> sum_tree::Dimension<'a, TransformSummary> for Point {
 150    fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
 151        *self += &summary.input.lines;
 152    }
 153}
 154
 155#[derive(Clone)]
 156pub struct InlayBufferRows<'a> {
 157    transforms: Cursor<'a, Transform, (InlayPoint, Point)>,
 158    buffer_rows: MultiBufferRows<'a>,
 159    inlay_row: u32,
 160    max_buffer_row: u32,
 161}
 162
 163pub struct InlayChunks<'a> {
 164    transforms: Cursor<'a, Transform, (InlayOffset, usize)>,
 165    buffer_chunks: MultiBufferChunks<'a>,
 166    buffer_chunk: Option<Chunk<'a>>,
 167    inlay_chunks: Option<text::Chunks<'a>>,
 168    output_offset: InlayOffset,
 169    max_output_offset: InlayOffset,
 170    highlight_style: Option<HighlightStyle>,
 171    snapshot: &'a InlaySnapshot,
 172}
 173
 174impl<'a> InlayChunks<'a> {
 175    pub fn seek(&mut self, offset: InlayOffset) {
 176        self.transforms.seek(&offset, Bias::Right, &());
 177
 178        let buffer_offset = self.snapshot.to_buffer_offset(offset);
 179        self.buffer_chunks.seek(buffer_offset);
 180        self.inlay_chunks = None;
 181        self.buffer_chunk = None;
 182        self.output_offset = offset;
 183    }
 184
 185    pub fn offset(&self) -> InlayOffset {
 186        self.output_offset
 187    }
 188}
 189
 190impl<'a> Iterator for InlayChunks<'a> {
 191    type Item = Chunk<'a>;
 192
 193    fn next(&mut self) -> Option<Self::Item> {
 194        if self.output_offset == self.max_output_offset {
 195            return None;
 196        }
 197
 198        let chunk = match self.transforms.item()? {
 199            Transform::Isomorphic(_) => {
 200                let chunk = self
 201                    .buffer_chunk
 202                    .get_or_insert_with(|| self.buffer_chunks.next().unwrap());
 203                if chunk.text.is_empty() {
 204                    *chunk = self.buffer_chunks.next().unwrap();
 205                }
 206
 207                let (prefix, suffix) = chunk.text.split_at(cmp::min(
 208                    self.transforms.end(&()).0 .0 - self.output_offset.0,
 209                    chunk.text.len(),
 210                ));
 211
 212                chunk.text = suffix;
 213                self.output_offset.0 += prefix.len();
 214                Chunk {
 215                    text: prefix,
 216                    ..chunk.clone()
 217                }
 218            }
 219            Transform::Inlay(inlay) => {
 220                let inlay_chunks = self.inlay_chunks.get_or_insert_with(|| {
 221                    let start = self.output_offset - self.transforms.start().0;
 222                    let end = cmp::min(self.max_output_offset, self.transforms.end(&()).0)
 223                        - self.transforms.start().0;
 224                    inlay.text.chunks_in_range(start.0..end.0)
 225                });
 226
 227                let chunk = inlay_chunks.next().unwrap();
 228                self.output_offset.0 += chunk.len();
 229                Chunk {
 230                    text: chunk,
 231                    highlight_style: self.highlight_style,
 232                    ..Default::default()
 233                }
 234            }
 235        };
 236
 237        if self.output_offset == self.transforms.end(&()).0 {
 238            self.inlay_chunks = None;
 239            self.transforms.next(&());
 240        }
 241
 242        Some(chunk)
 243    }
 244}
 245
 246impl<'a> InlayBufferRows<'a> {
 247    pub fn seek(&mut self, row: u32) {
 248        let inlay_point = InlayPoint::new(row, 0);
 249        self.transforms.seek(&inlay_point, Bias::Left, &());
 250
 251        let mut buffer_point = self.transforms.start().1;
 252        let buffer_row = if row == 0 {
 253            0
 254        } else {
 255            match self.transforms.item() {
 256                Some(Transform::Isomorphic(_)) => {
 257                    buffer_point += inlay_point.0 - self.transforms.start().0 .0;
 258                    buffer_point.row
 259                }
 260                _ => cmp::min(buffer_point.row + 1, self.max_buffer_row),
 261            }
 262        };
 263        self.inlay_row = inlay_point.row();
 264        self.buffer_rows.seek(buffer_row);
 265    }
 266}
 267
 268impl<'a> Iterator for InlayBufferRows<'a> {
 269    type Item = Option<u32>;
 270
 271    fn next(&mut self) -> Option<Self::Item> {
 272        let buffer_row = if self.inlay_row == 0 {
 273            self.buffer_rows.next().unwrap()
 274        } else {
 275            match self.transforms.item()? {
 276                Transform::Inlay(_) => None,
 277                Transform::Isomorphic(_) => self.buffer_rows.next().unwrap(),
 278            }
 279        };
 280
 281        self.inlay_row += 1;
 282        self.transforms
 283            .seek_forward(&InlayPoint::new(self.inlay_row, 0), Bias::Left, &());
 284
 285        Some(buffer_row)
 286    }
 287}
 288
 289impl InlayPoint {
 290    pub fn new(row: u32, column: u32) -> Self {
 291        Self(Point::new(row, column))
 292    }
 293
 294    pub fn row(self) -> u32 {
 295        self.0.row
 296    }
 297}
 298
 299impl InlayMap {
 300    pub fn new(buffer: MultiBufferSnapshot) -> (Self, InlaySnapshot) {
 301        let version = 0;
 302        let snapshot = InlaySnapshot {
 303            buffer: buffer.clone(),
 304            transforms: SumTree::from_item(Transform::Isomorphic(buffer.text_summary()), &()),
 305            version,
 306        };
 307
 308        (
 309            Self {
 310                snapshot: snapshot.clone(),
 311                inlays_by_id: HashMap::default(),
 312                inlays: Vec::new(),
 313            },
 314            snapshot,
 315        )
 316    }
 317
 318    pub fn sync(
 319        &mut self,
 320        buffer_snapshot: MultiBufferSnapshot,
 321        mut buffer_edits: Vec<text::Edit<usize>>,
 322    ) -> (InlaySnapshot, Vec<InlayEdit>) {
 323        let mut snapshot = &mut self.snapshot;
 324
 325        if buffer_edits.is_empty() {
 326            if snapshot.buffer.trailing_excerpt_update_count()
 327                != buffer_snapshot.trailing_excerpt_update_count()
 328            {
 329                buffer_edits.push(Edit {
 330                    old: snapshot.buffer.len()..snapshot.buffer.len(),
 331                    new: buffer_snapshot.len()..buffer_snapshot.len(),
 332                });
 333            }
 334        }
 335
 336        if buffer_edits.is_empty() {
 337            if snapshot.buffer.edit_count() != buffer_snapshot.edit_count()
 338                || snapshot.buffer.parse_count() != buffer_snapshot.parse_count()
 339                || snapshot.buffer.diagnostics_update_count()
 340                    != buffer_snapshot.diagnostics_update_count()
 341                || snapshot.buffer.git_diff_update_count()
 342                    != buffer_snapshot.git_diff_update_count()
 343                || snapshot.buffer.trailing_excerpt_update_count()
 344                    != buffer_snapshot.trailing_excerpt_update_count()
 345            {
 346                snapshot.version += 1;
 347            }
 348
 349            snapshot.buffer = buffer_snapshot;
 350            (snapshot.clone(), Vec::new())
 351        } else {
 352            let mut inlay_edits = Patch::default();
 353            let mut new_transforms = SumTree::new();
 354            let mut cursor = snapshot.transforms.cursor::<(usize, InlayOffset)>();
 355            let mut buffer_edits_iter = buffer_edits.iter().peekable();
 356            while let Some(buffer_edit) = buffer_edits_iter.next() {
 357                new_transforms.append(cursor.slice(&buffer_edit.old.start, Bias::Left, &()), &());
 358                if let Some(Transform::Isomorphic(transform)) = cursor.item() {
 359                    if cursor.end(&()).0 == buffer_edit.old.start {
 360                        new_transforms.push(Transform::Isomorphic(transform.clone()), &());
 361                        cursor.next(&());
 362                    }
 363                }
 364
 365                // Remove all the inlays and transforms contained by the edit.
 366                let old_start =
 367                    cursor.start().1 + InlayOffset(buffer_edit.old.start - cursor.start().0);
 368                cursor.seek(&buffer_edit.old.end, Bias::Right, &());
 369                let old_end =
 370                    cursor.start().1 + InlayOffset(buffer_edit.old.end - cursor.start().0);
 371
 372                // Push the unchanged prefix.
 373                let prefix_start = new_transforms.summary().input.len;
 374                let prefix_end = buffer_edit.new.start;
 375                push_isomorphic(
 376                    &mut new_transforms,
 377                    buffer_snapshot.text_summary_for_range(prefix_start..prefix_end),
 378                );
 379                let new_start = InlayOffset(new_transforms.summary().output.len);
 380
 381                let start_ix = match self.inlays.binary_search_by(|probe| {
 382                    probe
 383                        .position
 384                        .to_offset(&buffer_snapshot)
 385                        .cmp(&buffer_edit.new.start)
 386                        .then(std::cmp::Ordering::Greater)
 387                }) {
 388                    Ok(ix) | Err(ix) => ix,
 389                };
 390
 391                for inlay in &self.inlays[start_ix..] {
 392                    let buffer_offset = inlay.position.to_offset(&buffer_snapshot);
 393                    if buffer_offset > buffer_edit.new.end {
 394                        break;
 395                    }
 396
 397                    let prefix_start = new_transforms.summary().input.len;
 398                    let prefix_end = buffer_offset;
 399                    push_isomorphic(
 400                        &mut new_transforms,
 401                        buffer_snapshot.text_summary_for_range(prefix_start..prefix_end),
 402                    );
 403
 404                    if inlay.position.is_valid(&buffer_snapshot) {
 405                        new_transforms.push(Transform::Inlay(inlay.clone()), &());
 406                    }
 407                }
 408
 409                // Apply the rest of the edit.
 410                let transform_start = new_transforms.summary().input.len;
 411                push_isomorphic(
 412                    &mut new_transforms,
 413                    buffer_snapshot.text_summary_for_range(transform_start..buffer_edit.new.end),
 414                );
 415                let new_end = InlayOffset(new_transforms.summary().output.len);
 416                inlay_edits.push(Edit {
 417                    old: old_start..old_end,
 418                    new: new_start..new_end,
 419                });
 420
 421                // If the next edit doesn't intersect the current isomorphic transform, then
 422                // we can push its remainder.
 423                if buffer_edits_iter
 424                    .peek()
 425                    .map_or(true, |edit| edit.old.start >= cursor.end(&()).0)
 426                {
 427                    let transform_start = new_transforms.summary().input.len;
 428                    let transform_end =
 429                        buffer_edit.new.end + (cursor.end(&()).0 - buffer_edit.old.end);
 430                    push_isomorphic(
 431                        &mut new_transforms,
 432                        buffer_snapshot.text_summary_for_range(transform_start..transform_end),
 433                    );
 434                    cursor.next(&());
 435                }
 436            }
 437
 438            new_transforms.append(cursor.suffix(&()), &());
 439            if new_transforms.first().is_none() {
 440                new_transforms.push(Transform::Isomorphic(Default::default()), &());
 441            }
 442
 443            drop(cursor);
 444            snapshot.transforms = new_transforms;
 445            snapshot.version += 1;
 446            snapshot.buffer = buffer_snapshot;
 447            snapshot.check_invariants();
 448
 449            (snapshot.clone(), inlay_edits.into_inner())
 450        }
 451    }
 452
 453    pub fn splice<T: Into<Rope>>(
 454        &mut self,
 455        to_remove: Vec<InlayId>,
 456        to_insert: Vec<(InlayId, InlayProperties<T>)>,
 457    ) -> (InlaySnapshot, Vec<InlayEdit>) {
 458        let snapshot = &mut self.snapshot;
 459        let mut edits = BTreeSet::new();
 460
 461        self.inlays.retain(|inlay| !to_remove.contains(&inlay.id));
 462        for inlay_id in to_remove {
 463            if let Some(inlay) = self.inlays_by_id.remove(&inlay_id) {
 464                let offset = inlay.position.to_offset(&snapshot.buffer);
 465                edits.insert(offset);
 466            }
 467        }
 468
 469        for (existing_id, properties) in to_insert {
 470            let inlay = Inlay {
 471                id: existing_id,
 472                position: properties.position,
 473                text: properties.text.into(),
 474            };
 475
 476            // Avoid inserting empty inlays.
 477            if inlay.text.is_empty() {
 478                continue;
 479            }
 480
 481            self.inlays_by_id.insert(inlay.id, inlay.clone());
 482            match self
 483                .inlays
 484                .binary_search_by(|probe| probe.position.cmp(&inlay.position, &snapshot.buffer))
 485            {
 486                Ok(ix) | Err(ix) => {
 487                    self.inlays.insert(ix, inlay.clone());
 488                }
 489            }
 490
 491            let offset = inlay.position.to_offset(&snapshot.buffer);
 492            edits.insert(offset);
 493        }
 494
 495        let buffer_edits = edits
 496            .into_iter()
 497            .map(|offset| Edit {
 498                old: offset..offset,
 499                new: offset..offset,
 500            })
 501            .collect();
 502        let buffer_snapshot = snapshot.buffer.clone();
 503        drop(snapshot);
 504        let (snapshot, edits) = self.sync(buffer_snapshot, buffer_edits);
 505        (snapshot, edits)
 506    }
 507
 508    pub fn current_inlays(&self) -> impl Iterator<Item = &Inlay> {
 509        self.inlays.iter()
 510    }
 511
 512    #[cfg(test)]
 513    pub(crate) fn randomly_mutate(
 514        &mut self,
 515        next_inlay_id: &mut usize,
 516        rng: &mut rand::rngs::StdRng,
 517    ) -> (InlaySnapshot, Vec<InlayEdit>) {
 518        use rand::prelude::*;
 519        use util::post_inc;
 520
 521        let mut to_remove = Vec::new();
 522        let mut to_insert = Vec::new();
 523        let snapshot = &mut self.snapshot;
 524        for _ in 0..rng.gen_range(1..=5) {
 525            if self.inlays.is_empty() || rng.gen() {
 526                let position = snapshot.buffer.random_byte_range(0, rng).start;
 527                let bias = if rng.gen() { Bias::Left } else { Bias::Right };
 528                let len = if rng.gen_bool(0.01) {
 529                    0
 530                } else {
 531                    rng.gen_range(1..=5)
 532                };
 533                let text = util::RandomCharIter::new(&mut *rng)
 534                    .filter(|ch| *ch != '\r')
 535                    .take(len)
 536                    .collect::<String>();
 537                log::info!(
 538                    "creating inlay at buffer offset {} with bias {:?} and text {:?}",
 539                    position,
 540                    bias,
 541                    text
 542                );
 543                to_insert.push((
 544                    InlayId(post_inc(next_inlay_id)),
 545                    InlayProperties {
 546                        position: snapshot.buffer.anchor_at(position, bias),
 547                        text,
 548                    },
 549                ));
 550            } else {
 551                to_remove.push(*self.inlays_by_id.keys().choose(rng).unwrap());
 552            }
 553        }
 554        log::info!("removing inlays: {:?}", to_remove);
 555
 556        drop(snapshot);
 557        let (snapshot, edits) = self.splice(to_remove, to_insert);
 558        (snapshot, edits)
 559    }
 560}
 561
 562impl InlaySnapshot {
 563    pub fn to_point(&self, offset: InlayOffset) -> InlayPoint {
 564        let mut cursor = self
 565            .transforms
 566            .cursor::<(InlayOffset, (InlayPoint, usize))>();
 567        cursor.seek(&offset, Bias::Right, &());
 568        let overshoot = offset.0 - cursor.start().0 .0;
 569        match cursor.item() {
 570            Some(Transform::Isomorphic(_)) => {
 571                let buffer_offset_start = cursor.start().1 .1;
 572                let buffer_offset_end = buffer_offset_start + overshoot;
 573                let buffer_start = self.buffer.offset_to_point(buffer_offset_start);
 574                let buffer_end = self.buffer.offset_to_point(buffer_offset_end);
 575                InlayPoint(cursor.start().1 .0 .0 + (buffer_end - buffer_start))
 576            }
 577            Some(Transform::Inlay(inlay)) => {
 578                let overshoot = inlay.text.offset_to_point(overshoot);
 579                InlayPoint(cursor.start().1 .0 .0 + overshoot)
 580            }
 581            None => self.max_point(),
 582        }
 583    }
 584
 585    pub fn len(&self) -> InlayOffset {
 586        InlayOffset(self.transforms.summary().output.len)
 587    }
 588
 589    pub fn max_point(&self) -> InlayPoint {
 590        InlayPoint(self.transforms.summary().output.lines)
 591    }
 592
 593    pub fn to_offset(&self, point: InlayPoint) -> InlayOffset {
 594        let mut cursor = self
 595            .transforms
 596            .cursor::<(InlayPoint, (InlayOffset, Point))>();
 597        cursor.seek(&point, Bias::Right, &());
 598        let overshoot = point.0 - cursor.start().0 .0;
 599        match cursor.item() {
 600            Some(Transform::Isomorphic(_)) => {
 601                let buffer_point_start = cursor.start().1 .1;
 602                let buffer_point_end = buffer_point_start + overshoot;
 603                let buffer_offset_start = self.buffer.point_to_offset(buffer_point_start);
 604                let buffer_offset_end = self.buffer.point_to_offset(buffer_point_end);
 605                InlayOffset(cursor.start().1 .0 .0 + (buffer_offset_end - buffer_offset_start))
 606            }
 607            Some(Transform::Inlay(inlay)) => {
 608                let overshoot = inlay.text.point_to_offset(overshoot);
 609                InlayOffset(cursor.start().1 .0 .0 + overshoot)
 610            }
 611            None => self.len(),
 612        }
 613    }
 614
 615    pub fn to_buffer_point(&self, point: InlayPoint) -> Point {
 616        let mut cursor = self.transforms.cursor::<(InlayPoint, Point)>();
 617        cursor.seek(&point, Bias::Right, &());
 618        match cursor.item() {
 619            Some(Transform::Isomorphic(_)) => {
 620                let overshoot = point.0 - cursor.start().0 .0;
 621                cursor.start().1 + overshoot
 622            }
 623            Some(Transform::Inlay(_)) => cursor.start().1,
 624            None => self.buffer.max_point(),
 625        }
 626    }
 627
 628    pub fn to_buffer_offset(&self, offset: InlayOffset) -> usize {
 629        let mut cursor = self.transforms.cursor::<(InlayOffset, usize)>();
 630        cursor.seek(&offset, Bias::Right, &());
 631        match cursor.item() {
 632            Some(Transform::Isomorphic(_)) => {
 633                let overshoot = offset - cursor.start().0;
 634                cursor.start().1 + overshoot.0
 635            }
 636            Some(Transform::Inlay(_)) => cursor.start().1,
 637            None => self.buffer.len(),
 638        }
 639    }
 640
 641    pub fn to_inlay_offset(&self, offset: usize) -> InlayOffset {
 642        let mut cursor = self.transforms.cursor::<(usize, InlayOffset)>();
 643        cursor.seek(&offset, Bias::Left, &());
 644        match cursor.item() {
 645            Some(Transform::Isomorphic(_)) => {
 646                let overshoot = offset - cursor.start().0;
 647                InlayOffset(cursor.start().1 .0 + overshoot)
 648            }
 649            Some(Transform::Inlay(_)) => cursor.start().1,
 650            None => self.len(),
 651        }
 652    }
 653
 654    pub fn to_inlay_point(&self, point: Point) -> InlayPoint {
 655        let mut cursor = self.transforms.cursor::<(Point, InlayPoint)>();
 656        cursor.seek(&point, Bias::Left, &());
 657        match cursor.item() {
 658            Some(Transform::Isomorphic(_)) => {
 659                let overshoot = point - cursor.start().0;
 660                InlayPoint(cursor.start().1 .0 + overshoot)
 661            }
 662            Some(Transform::Inlay(_)) => cursor.start().1,
 663            None => self.max_point(),
 664        }
 665    }
 666
 667    pub fn clip_point(&self, point: InlayPoint, bias: Bias) -> InlayPoint {
 668        let mut cursor = self.transforms.cursor::<(InlayPoint, Point)>();
 669        cursor.seek(&point, Bias::Left, &());
 670
 671        let mut bias = bias;
 672        let mut skipped_inlay = false;
 673        loop {
 674            match cursor.item() {
 675                Some(Transform::Isomorphic(transform)) => {
 676                    let overshoot = if skipped_inlay {
 677                        match bias {
 678                            Bias::Left => transform.lines,
 679                            Bias::Right => {
 680                                if transform.first_line_chars == 0 {
 681                                    Point::new(1, 0)
 682                                } else {
 683                                    Point::new(0, 1)
 684                                }
 685                            }
 686                        }
 687                    } else {
 688                        point.0 - cursor.start().0 .0
 689                    };
 690                    let buffer_point = cursor.start().1 + overshoot;
 691                    let clipped_buffer_point = self.buffer.clip_point(buffer_point, bias);
 692                    let clipped_overshoot = clipped_buffer_point - cursor.start().1;
 693                    return InlayPoint(cursor.start().0 .0 + clipped_overshoot);
 694                }
 695                Some(Transform::Inlay(_)) => skipped_inlay = true,
 696                None => match bias {
 697                    Bias::Left => return Default::default(),
 698                    Bias::Right => bias = Bias::Left,
 699                },
 700            }
 701
 702            if bias == Bias::Left {
 703                cursor.prev(&());
 704            } else {
 705                cursor.next(&());
 706            }
 707        }
 708    }
 709
 710    pub fn text_summary(&self) -> TextSummary {
 711        self.transforms.summary().output.clone()
 712    }
 713
 714    pub fn text_summary_for_range(&self, range: Range<InlayOffset>) -> TextSummary {
 715        let mut summary = TextSummary::default();
 716
 717        let mut cursor = self.transforms.cursor::<(InlayOffset, usize)>();
 718        cursor.seek(&range.start, Bias::Right, &());
 719
 720        let overshoot = range.start.0 - cursor.start().0 .0;
 721        match cursor.item() {
 722            Some(Transform::Isomorphic(_)) => {
 723                let buffer_start = cursor.start().1;
 724                let suffix_start = buffer_start + overshoot;
 725                let suffix_end =
 726                    buffer_start + (cmp::min(cursor.end(&()).0, range.end).0 - cursor.start().0 .0);
 727                summary = self.buffer.text_summary_for_range(suffix_start..suffix_end);
 728                cursor.next(&());
 729            }
 730            Some(Transform::Inlay(inlay)) => {
 731                let suffix_start = overshoot;
 732                let suffix_end = cmp::min(cursor.end(&()).0, range.end).0 - cursor.start().0 .0;
 733                summary = inlay.text.cursor(suffix_start).summary(suffix_end);
 734                cursor.next(&());
 735            }
 736            None => {}
 737        }
 738
 739        if range.end > cursor.start().0 {
 740            summary += cursor
 741                .summary::<_, TransformSummary>(&range.end, Bias::Right, &())
 742                .output;
 743
 744            let overshoot = range.end.0 - cursor.start().0 .0;
 745            match cursor.item() {
 746                Some(Transform::Isomorphic(_)) => {
 747                    let prefix_start = cursor.start().1;
 748                    let prefix_end = prefix_start + overshoot;
 749                    summary += self
 750                        .buffer
 751                        .text_summary_for_range::<TextSummary, _>(prefix_start..prefix_end);
 752                }
 753                Some(Transform::Inlay(inlay)) => {
 754                    let prefix_end = overshoot;
 755                    summary += inlay.text.cursor(0).summary::<TextSummary>(prefix_end);
 756                }
 757                None => {}
 758            }
 759        }
 760
 761        summary
 762    }
 763
 764    pub fn buffer_rows<'a>(&'a self, row: u32) -> InlayBufferRows<'a> {
 765        let mut cursor = self.transforms.cursor::<(InlayPoint, Point)>();
 766        let inlay_point = InlayPoint::new(row, 0);
 767        cursor.seek(&inlay_point, Bias::Left, &());
 768
 769        let max_buffer_row = self.buffer.max_point().row;
 770        let mut buffer_point = cursor.start().1;
 771        let buffer_row = if row == 0 {
 772            0
 773        } else {
 774            match cursor.item() {
 775                Some(Transform::Isomorphic(_)) => {
 776                    buffer_point += inlay_point.0 - cursor.start().0 .0;
 777                    buffer_point.row
 778                }
 779                _ => cmp::min(buffer_point.row + 1, max_buffer_row),
 780            }
 781        };
 782
 783        InlayBufferRows {
 784            transforms: cursor,
 785            inlay_row: inlay_point.row(),
 786            buffer_rows: self.buffer.buffer_rows(buffer_row),
 787            max_buffer_row,
 788        }
 789    }
 790
 791    pub fn line_len(&self, row: u32) -> u32 {
 792        let line_start = self.to_offset(InlayPoint::new(row, 0)).0;
 793        let line_end = if row >= self.max_point().row() {
 794            self.len().0
 795        } else {
 796            self.to_offset(InlayPoint::new(row + 1, 0)).0 - 1
 797        };
 798        (line_end - line_start) as u32
 799    }
 800
 801    pub fn chunks<'a>(
 802        &'a self,
 803        range: Range<InlayOffset>,
 804        language_aware: bool,
 805        inlay_highlight_style: Option<HighlightStyle>,
 806    ) -> InlayChunks<'a> {
 807        let mut cursor = self.transforms.cursor::<(InlayOffset, usize)>();
 808        cursor.seek(&range.start, Bias::Right, &());
 809
 810        let buffer_range = self.to_buffer_offset(range.start)..self.to_buffer_offset(range.end);
 811        let buffer_chunks = self.buffer.chunks(buffer_range, language_aware);
 812
 813        InlayChunks {
 814            transforms: cursor,
 815            buffer_chunks,
 816            inlay_chunks: None,
 817            buffer_chunk: None,
 818            output_offset: range.start,
 819            max_output_offset: range.end,
 820            highlight_style: inlay_highlight_style,
 821            snapshot: self,
 822        }
 823    }
 824
 825    #[cfg(test)]
 826    pub fn text(&self) -> String {
 827        self.chunks(Default::default()..self.len(), false, None)
 828            .map(|chunk| chunk.text)
 829            .collect()
 830    }
 831
 832    fn check_invariants(&self) {
 833        #[cfg(any(debug_assertions, feature = "test-support"))]
 834        {
 835            assert_eq!(self.transforms.summary().input, self.buffer.text_summary());
 836        }
 837    }
 838}
 839
 840fn push_isomorphic(sum_tree: &mut SumTree<Transform>, summary: TextSummary) {
 841    if summary.len == 0 {
 842        return;
 843    }
 844
 845    let mut summary = Some(summary);
 846    sum_tree.update_last(
 847        |transform| {
 848            if let Transform::Isomorphic(transform) = transform {
 849                *transform += summary.take().unwrap();
 850            }
 851        },
 852        &(),
 853    );
 854
 855    if let Some(summary) = summary {
 856        sum_tree.push(Transform::Isomorphic(summary), &());
 857    }
 858}
 859
 860#[cfg(test)]
 861mod tests {
 862    use super::*;
 863    use crate::{InlayId, MultiBuffer};
 864    use gpui::AppContext;
 865    use rand::prelude::*;
 866    use settings::SettingsStore;
 867    use std::env;
 868    use text::Patch;
 869    use util::post_inc;
 870
 871    #[gpui::test]
 872    fn test_basic_inlays(cx: &mut AppContext) {
 873        let buffer = MultiBuffer::build_simple("abcdefghi", cx);
 874        let buffer_edits = buffer.update(cx, |buffer, _| buffer.subscribe());
 875        let (mut inlay_map, inlay_snapshot) = InlayMap::new(buffer.read(cx).snapshot(cx));
 876        assert_eq!(inlay_snapshot.text(), "abcdefghi");
 877        let mut next_inlay_id = 0;
 878
 879        let (inlay_snapshot, _) = inlay_map.splice(
 880            Vec::new(),
 881            vec![(
 882                InlayId(post_inc(&mut next_inlay_id)),
 883                InlayProperties {
 884                    position: buffer.read(cx).snapshot(cx).anchor_after(3),
 885                    text: "|123|",
 886                },
 887            )],
 888        );
 889        assert_eq!(inlay_snapshot.text(), "abc|123|defghi");
 890        assert_eq!(
 891            inlay_snapshot.to_inlay_point(Point::new(0, 0)),
 892            InlayPoint::new(0, 0)
 893        );
 894        assert_eq!(
 895            inlay_snapshot.to_inlay_point(Point::new(0, 1)),
 896            InlayPoint::new(0, 1)
 897        );
 898        assert_eq!(
 899            inlay_snapshot.to_inlay_point(Point::new(0, 2)),
 900            InlayPoint::new(0, 2)
 901        );
 902        assert_eq!(
 903            inlay_snapshot.to_inlay_point(Point::new(0, 3)),
 904            InlayPoint::new(0, 3)
 905        );
 906        assert_eq!(
 907            inlay_snapshot.to_inlay_point(Point::new(0, 4)),
 908            InlayPoint::new(0, 9)
 909        );
 910        assert_eq!(
 911            inlay_snapshot.to_inlay_point(Point::new(0, 5)),
 912            InlayPoint::new(0, 10)
 913        );
 914        assert_eq!(
 915            inlay_snapshot.clip_point(InlayPoint::new(0, 0), Bias::Left),
 916            InlayPoint::new(0, 0)
 917        );
 918        assert_eq!(
 919            inlay_snapshot.clip_point(InlayPoint::new(0, 0), Bias::Right),
 920            InlayPoint::new(0, 0)
 921        );
 922        assert_eq!(
 923            inlay_snapshot.clip_point(InlayPoint::new(0, 3), Bias::Left),
 924            InlayPoint::new(0, 3)
 925        );
 926        assert_eq!(
 927            inlay_snapshot.clip_point(InlayPoint::new(0, 3), Bias::Right),
 928            InlayPoint::new(0, 3)
 929        );
 930        assert_eq!(
 931            inlay_snapshot.clip_point(InlayPoint::new(0, 4), Bias::Left),
 932            InlayPoint::new(0, 3)
 933        );
 934        assert_eq!(
 935            inlay_snapshot.clip_point(InlayPoint::new(0, 4), Bias::Right),
 936            InlayPoint::new(0, 9)
 937        );
 938
 939        // Edits before or after the inlay should not affect it.
 940        buffer.update(cx, |buffer, cx| {
 941            buffer.edit([(2..3, "x"), (3..3, "y"), (4..4, "z")], None, cx)
 942        });
 943        let (inlay_snapshot, _) = inlay_map.sync(
 944            buffer.read(cx).snapshot(cx),
 945            buffer_edits.consume().into_inner(),
 946        );
 947        assert_eq!(inlay_snapshot.text(), "abxy|123|dzefghi");
 948
 949        // An edit surrounding the inlay should invalidate it.
 950        buffer.update(cx, |buffer, cx| buffer.edit([(4..5, "D")], None, cx));
 951        let (inlay_snapshot, _) = inlay_map.sync(
 952            buffer.read(cx).snapshot(cx),
 953            buffer_edits.consume().into_inner(),
 954        );
 955        assert_eq!(inlay_snapshot.text(), "abxyDzefghi");
 956
 957        let (inlay_snapshot, _) = inlay_map.splice(
 958            Vec::new(),
 959            vec![
 960                (
 961                    InlayId(post_inc(&mut next_inlay_id)),
 962                    InlayProperties {
 963                        position: buffer.read(cx).snapshot(cx).anchor_before(3),
 964                        text: "|123|",
 965                    },
 966                ),
 967                (
 968                    InlayId(post_inc(&mut next_inlay_id)),
 969                    InlayProperties {
 970                        position: buffer.read(cx).snapshot(cx).anchor_after(3),
 971                        text: "|456|",
 972                    },
 973                ),
 974            ],
 975        );
 976        assert_eq!(inlay_snapshot.text(), "abx|123||456|yDzefghi");
 977
 978        // Edits ending where the inlay starts should not move it if it has a left bias.
 979        buffer.update(cx, |buffer, cx| buffer.edit([(3..3, "JKL")], None, cx));
 980        let (inlay_snapshot, _) = inlay_map.sync(
 981            buffer.read(cx).snapshot(cx),
 982            buffer_edits.consume().into_inner(),
 983        );
 984        assert_eq!(inlay_snapshot.text(), "abx|123|JKL|456|yDzefghi");
 985
 986        // The inlays can be manually removed.
 987        let (inlay_snapshot, _) = inlay_map
 988            .splice::<String>(inlay_map.inlays_by_id.keys().copied().collect(), Vec::new());
 989        assert_eq!(inlay_snapshot.text(), "abxJKLyDzefghi");
 990    }
 991
 992    #[gpui::test]
 993    fn test_inlay_buffer_rows(cx: &mut AppContext) {
 994        let buffer = MultiBuffer::build_simple("abc\ndef\nghi", cx);
 995        let (mut inlay_map, inlay_snapshot) = InlayMap::new(buffer.read(cx).snapshot(cx));
 996        assert_eq!(inlay_snapshot.text(), "abc\ndef\nghi");
 997        let mut next_inlay_id = 0;
 998
 999        let (inlay_snapshot, _) = inlay_map.splice(
1000            Vec::new(),
1001            vec![
1002                (
1003                    InlayId(post_inc(&mut next_inlay_id)),
1004                    InlayProperties {
1005                        position: buffer.read(cx).snapshot(cx).anchor_before(0),
1006                        text: "|123|\n",
1007                    },
1008                ),
1009                (
1010                    InlayId(post_inc(&mut next_inlay_id)),
1011                    InlayProperties {
1012                        position: buffer.read(cx).snapshot(cx).anchor_before(4),
1013                        text: "|456|",
1014                    },
1015                ),
1016                (
1017                    InlayId(post_inc(&mut next_inlay_id)),
1018                    InlayProperties {
1019                        position: buffer.read(cx).snapshot(cx).anchor_before(7),
1020                        text: "\n|567|\n",
1021                    },
1022                ),
1023            ],
1024        );
1025        assert_eq!(inlay_snapshot.text(), "|123|\nabc\n|456|def\n|567|\n\nghi");
1026        assert_eq!(
1027            inlay_snapshot.buffer_rows(0).collect::<Vec<_>>(),
1028            vec![Some(0), None, Some(1), None, None, Some(2)]
1029        );
1030    }
1031
1032    #[gpui::test(iterations = 100)]
1033    fn test_random_inlays(cx: &mut AppContext, mut rng: StdRng) {
1034        init_test(cx);
1035
1036        let operations = env::var("OPERATIONS")
1037            .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1038            .unwrap_or(10);
1039
1040        let len = rng.gen_range(0..30);
1041        let buffer = if rng.gen() {
1042            let text = util::RandomCharIter::new(&mut rng)
1043                .take(len)
1044                .collect::<String>();
1045            MultiBuffer::build_simple(&text, cx)
1046        } else {
1047            MultiBuffer::build_random(&mut rng, cx)
1048        };
1049        let mut buffer_snapshot = buffer.read(cx).snapshot(cx);
1050        let mut next_inlay_id = 0;
1051        log::info!("buffer text: {:?}", buffer_snapshot.text());
1052
1053        let (mut inlay_map, mut inlay_snapshot) = InlayMap::new(buffer_snapshot.clone());
1054        for _ in 0..operations {
1055            let mut inlay_edits = Patch::default();
1056
1057            let mut prev_inlay_text = inlay_snapshot.text();
1058            let mut buffer_edits = Vec::new();
1059            match rng.gen_range(0..=100) {
1060                0..=50 => {
1061                    let (snapshot, edits) = inlay_map.randomly_mutate(&mut next_inlay_id, &mut rng);
1062                    log::info!("mutated text: {:?}", snapshot.text());
1063                    inlay_edits = Patch::new(edits);
1064                }
1065                _ => buffer.update(cx, |buffer, cx| {
1066                    let subscription = buffer.subscribe();
1067                    let edit_count = rng.gen_range(1..=5);
1068                    buffer.randomly_mutate(&mut rng, edit_count, cx);
1069                    buffer_snapshot = buffer.snapshot(cx);
1070                    let edits = subscription.consume().into_inner();
1071                    log::info!("editing {:?}", edits);
1072                    buffer_edits.extend(edits);
1073                }),
1074            };
1075
1076            let (new_inlay_snapshot, new_inlay_edits) =
1077                inlay_map.sync(buffer_snapshot.clone(), buffer_edits);
1078            inlay_snapshot = new_inlay_snapshot;
1079            inlay_edits = inlay_edits.compose(new_inlay_edits);
1080
1081            log::info!("buffer text: {:?}", buffer_snapshot.text());
1082            log::info!("inlay text: {:?}", inlay_snapshot.text());
1083
1084            let inlays = inlay_map
1085                .inlays
1086                .iter()
1087                .filter(|inlay| inlay.position.is_valid(&buffer_snapshot))
1088                .map(|inlay| {
1089                    let offset = inlay.position.to_offset(&buffer_snapshot);
1090                    (offset, inlay.clone())
1091                })
1092                .collect::<Vec<_>>();
1093            let mut expected_text = Rope::from(buffer_snapshot.text().as_str());
1094            for (offset, inlay) in inlays.into_iter().rev() {
1095                expected_text.replace(offset..offset, &inlay.text.to_string());
1096            }
1097            assert_eq!(inlay_snapshot.text(), expected_text.to_string());
1098
1099            let expected_buffer_rows = inlay_snapshot.buffer_rows(0).collect::<Vec<_>>();
1100            assert_eq!(
1101                expected_buffer_rows.len() as u32,
1102                expected_text.max_point().row + 1
1103            );
1104            for row_start in 0..expected_buffer_rows.len() {
1105                assert_eq!(
1106                    inlay_snapshot
1107                        .buffer_rows(row_start as u32)
1108                        .collect::<Vec<_>>(),
1109                    &expected_buffer_rows[row_start..],
1110                    "incorrect buffer rows starting at {}",
1111                    row_start
1112                );
1113            }
1114
1115            for _ in 0..5 {
1116                let mut end = rng.gen_range(0..=inlay_snapshot.len().0);
1117                end = expected_text.clip_offset(end, Bias::Right);
1118                let mut start = rng.gen_range(0..=end);
1119                start = expected_text.clip_offset(start, Bias::Right);
1120
1121                let actual_text = inlay_snapshot
1122                    .chunks(InlayOffset(start)..InlayOffset(end), false, None)
1123                    .map(|chunk| chunk.text)
1124                    .collect::<String>();
1125                assert_eq!(
1126                    actual_text,
1127                    expected_text.slice(start..end).to_string(),
1128                    "incorrect text in range {:?}",
1129                    start..end
1130                );
1131
1132                assert_eq!(
1133                    inlay_snapshot.text_summary_for_range(InlayOffset(start)..InlayOffset(end)),
1134                    expected_text.slice(start..end).summary()
1135                );
1136            }
1137
1138            for edit in inlay_edits {
1139                prev_inlay_text.replace_range(
1140                    edit.new.start.0..edit.new.start.0 + edit.old_len().0,
1141                    &inlay_snapshot.text()[edit.new.start.0..edit.new.end.0],
1142                );
1143            }
1144            assert_eq!(prev_inlay_text, inlay_snapshot.text());
1145
1146            assert_eq!(expected_text.max_point(), inlay_snapshot.max_point().0);
1147            assert_eq!(expected_text.len(), inlay_snapshot.len().0);
1148
1149            let mut inlay_point = InlayPoint::default();
1150            let mut inlay_offset = InlayOffset::default();
1151            for ch in expected_text.chars() {
1152                assert_eq!(
1153                    inlay_snapshot.to_offset(inlay_point),
1154                    inlay_offset,
1155                    "invalid to_offset({:?})",
1156                    inlay_point
1157                );
1158                assert_eq!(
1159                    inlay_snapshot.to_point(inlay_offset),
1160                    inlay_point,
1161                    "invalid to_point({:?})",
1162                    inlay_offset
1163                );
1164                assert_eq!(
1165                    inlay_snapshot.to_inlay_point(inlay_snapshot.to_buffer_point(inlay_point)),
1166                    inlay_snapshot.clip_point(inlay_point, Bias::Left),
1167                    "to_buffer_point({:?}) = {:?}",
1168                    inlay_point,
1169                    inlay_snapshot.to_buffer_point(inlay_point),
1170                );
1171
1172                let mut bytes = [0; 4];
1173                for byte in ch.encode_utf8(&mut bytes).as_bytes() {
1174                    inlay_offset.0 += 1;
1175                    if *byte == b'\n' {
1176                        inlay_point.0 += Point::new(1, 0);
1177                    } else {
1178                        inlay_point.0 += Point::new(0, 1);
1179                    }
1180
1181                    let clipped_left_point = inlay_snapshot.clip_point(inlay_point, Bias::Left);
1182                    let clipped_right_point = inlay_snapshot.clip_point(inlay_point, Bias::Right);
1183                    assert!(
1184                        clipped_left_point <= clipped_right_point,
1185                        "clipped left point {:?} is greater than clipped right point {:?}",
1186                        clipped_left_point,
1187                        clipped_right_point
1188                    );
1189
1190                    // Ensure the clipped points are at valid text locations.
1191                    assert_eq!(
1192                        clipped_left_point.0,
1193                        expected_text.clip_point(clipped_left_point.0, Bias::Left)
1194                    );
1195                    assert_eq!(
1196                        clipped_right_point.0,
1197                        expected_text.clip_point(clipped_right_point.0, Bias::Right)
1198                    );
1199
1200                    // Ensure the clipped points never overshoot the end of the map.
1201                    assert!(clipped_left_point <= inlay_snapshot.max_point());
1202                    assert!(clipped_right_point <= inlay_snapshot.max_point());
1203                }
1204            }
1205        }
1206    }
1207
1208    fn init_test(cx: &mut AppContext) {
1209        cx.set_global(SettingsStore::test(cx));
1210        theme::init((), cx);
1211    }
1212}