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