1use std::{mem, ops::Range, sync::Arc};
2
3/// When incrementally updating excerpts, we try to expand new ranges to match
4/// overlapping existing excerpts so we can reuse them (avoiding rewrap churn).
5/// But if an existing excerpt is much larger than the new range, blindly
6/// expanding creates huge excerpts with many irrelevant lines above/below the
7/// actual matches. This constant caps how many extra rows we allow on each
8/// side of the *original* new range when expanding toward an existing excerpt.
9const MAX_EXCERPT_EXPANSION_ROWS: u32 = 10;
10
11use collections::HashSet;
12use gpui::{App, AppContext, Context, Entity};
13use itertools::Itertools;
14use language::{Buffer, BufferSnapshot};
15use rope::Point;
16use text::{Bias, OffsetRangeExt, locator::Locator};
17use util::{post_inc, rel_path::RelPath};
18use ztracing::instrument;
19
20use crate::{
21 Anchor, ExcerptId, ExcerptRange, ExpandExcerptDirection, MultiBuffer, build_excerpt_ranges,
22};
23
24struct ExistingExcerpt {
25 id: ExcerptId,
26 range: Range<Point>,
27}
28
29struct ExpandedExcerpts {
30 ranges: Vec<ExcerptRange<Point>>,
31 counts: Vec<usize>,
32 /// Existing excerpts that overlap new ranges but are too large to expand
33 /// to within `MAX_EXCERPT_EXPANSION_ROWS`. These must be removed before
34 /// `update_path_excerpts` runs, so the new ranges get inserted fresh
35 /// instead of being unioned back to the old size by the partial-overlap
36 /// branch.
37 stale_excerpt_ids: Vec<ExcerptId>,
38}
39
40#[derive(Debug, Clone)]
41pub struct PathExcerptInsertResult {
42 pub inserted_ranges: Vec<Range<Anchor>>,
43 pub excerpt_ids: Vec<ExcerptId>,
44 pub added_new_excerpt: bool,
45}
46
47#[derive(PartialEq, Eq, Ord, PartialOrd, Clone, Hash, Debug)]
48pub struct PathKey {
49 // Used by the derived PartialOrd & Ord
50 pub sort_prefix: Option<u64>,
51 pub path: Arc<RelPath>,
52}
53
54impl PathKey {
55 pub fn sorted(sort_prefix: u64) -> Self {
56 Self {
57 sort_prefix: Some(sort_prefix),
58 path: RelPath::empty().into_arc(),
59 }
60 }
61 pub fn with_sort_prefix(sort_prefix: u64, path: Arc<RelPath>) -> Self {
62 Self {
63 sort_prefix: Some(sort_prefix),
64 path,
65 }
66 }
67
68 pub fn for_buffer(buffer: &Entity<Buffer>, cx: &App) -> Self {
69 if let Some(file) = buffer.read(cx).file() {
70 Self::with_sort_prefix(file.worktree_id(cx).to_proto(), file.path().clone())
71 } else {
72 Self {
73 sort_prefix: None,
74 path: RelPath::unix(&buffer.entity_id().to_string())
75 .unwrap()
76 .into_arc(),
77 }
78 }
79 }
80}
81
82impl MultiBuffer {
83 pub fn paths(&self) -> impl Iterator<Item = &PathKey> + '_ {
84 self.excerpts_by_path.keys()
85 }
86
87 pub fn excerpts_for_path(&self, path: &PathKey) -> impl '_ + Iterator<Item = ExcerptId> {
88 self.excerpts_by_path
89 .get(path)
90 .map(|excerpts| excerpts.as_slice())
91 .unwrap_or_default()
92 .iter()
93 .copied()
94 }
95
96 pub fn path_for_excerpt(&self, excerpt: ExcerptId) -> Option<PathKey> {
97 self.paths_by_excerpt.get(&excerpt).cloned()
98 }
99
100 pub fn remove_excerpts_for_path(&mut self, path: PathKey, cx: &mut Context<Self>) {
101 if let Some(to_remove) = self.excerpts_by_path.remove(&path) {
102 self.remove_excerpts(to_remove, cx)
103 }
104 }
105
106 pub fn buffer_for_path(&self, path: &PathKey, cx: &App) -> Option<Entity<Buffer>> {
107 let excerpt_id = self.excerpts_by_path.get(path)?.first()?;
108 let snapshot = self.read(cx);
109 let excerpt = snapshot.excerpt(*excerpt_id)?;
110 self.buffer(excerpt.buffer_id)
111 }
112
113 pub fn location_for_path(&self, path: &PathKey, cx: &App) -> Option<Anchor> {
114 let excerpt_id = self.excerpts_by_path.get(path)?.first()?;
115 let snapshot = self.read(cx);
116 let excerpt = snapshot.excerpt(*excerpt_id)?;
117 Some(Anchor::in_buffer(excerpt.id, excerpt.range.context.start))
118 }
119
120 pub fn set_excerpts_for_buffer(
121 &mut self,
122 buffer: Entity<Buffer>,
123 ranges: impl IntoIterator<Item = Range<Point>>,
124 context_line_count: u32,
125 cx: &mut Context<Self>,
126 ) -> (Vec<Range<Anchor>>, bool) {
127 let path = PathKey::for_buffer(&buffer, cx);
128 self.set_excerpts_for_path(path, buffer, ranges, context_line_count, cx)
129 }
130
131 /// Sets excerpts, returns `true` if at least one new excerpt was added.
132 #[instrument(skip_all)]
133 pub fn set_excerpts_for_path(
134 &mut self,
135 path: PathKey,
136 buffer: Entity<Buffer>,
137 ranges: impl IntoIterator<Item = Range<Point>>,
138 context_line_count: u32,
139 cx: &mut Context<Self>,
140 ) -> (Vec<Range<Anchor>>, bool) {
141 let buffer_snapshot = buffer.read(cx).snapshot();
142 let excerpt_ranges = build_excerpt_ranges(ranges, context_line_count, &buffer_snapshot);
143
144 let (new, counts) = Self::merge_excerpt_ranges(&excerpt_ranges);
145 let excerpt_insertion_result = self.set_merged_excerpt_ranges_for_path(
146 path,
147 buffer,
148 excerpt_ranges,
149 &buffer_snapshot,
150 new,
151 counts,
152 cx,
153 );
154 (
155 excerpt_insertion_result.inserted_ranges,
156 excerpt_insertion_result.added_new_excerpt,
157 )
158 }
159
160 pub fn set_excerpt_ranges_for_path(
161 &mut self,
162 path: PathKey,
163 buffer: Entity<Buffer>,
164 buffer_snapshot: &BufferSnapshot,
165 excerpt_ranges: Vec<ExcerptRange<Point>>,
166 cx: &mut Context<Self>,
167 ) -> (Vec<Range<Anchor>>, bool) {
168 let (new, counts) = Self::merge_excerpt_ranges(&excerpt_ranges);
169 let excerpt_insertion_result = self.set_merged_excerpt_ranges_for_path(
170 path,
171 buffer,
172 excerpt_ranges,
173 buffer_snapshot,
174 new,
175 counts,
176 cx,
177 );
178 (
179 excerpt_insertion_result.inserted_ranges,
180 excerpt_insertion_result.added_new_excerpt,
181 )
182 }
183
184 pub fn set_anchored_excerpts_for_path(
185 &self,
186 path_key: PathKey,
187 buffer: Entity<Buffer>,
188 ranges: Vec<Range<text::Anchor>>,
189 context_line_count: u32,
190 cx: &Context<Self>,
191 ) -> impl Future<Output = Vec<Range<Anchor>>> + use<> {
192 let buffer_snapshot = buffer.read(cx).snapshot();
193 let multi_buffer = cx.weak_entity();
194 let mut app = cx.to_async();
195 async move {
196 let snapshot = buffer_snapshot.clone();
197 let (excerpt_ranges, new, counts) = app
198 .background_spawn(async move {
199 let ranges = ranges.into_iter().map(|range| range.to_point(&snapshot));
200 let excerpt_ranges =
201 build_excerpt_ranges(ranges, context_line_count, &snapshot);
202 let (new, counts) = Self::merge_excerpt_ranges(&excerpt_ranges);
203 (excerpt_ranges, new, counts)
204 })
205 .await;
206
207 multi_buffer
208 .update(&mut app, move |multi_buffer, cx| {
209 let excerpt_insertion_result = multi_buffer.set_merged_excerpt_ranges_for_path(
210 path_key,
211 buffer,
212 excerpt_ranges,
213 &buffer_snapshot,
214 new,
215 counts,
216 cx,
217 );
218 excerpt_insertion_result.inserted_ranges
219 })
220 .ok()
221 .unwrap_or_default()
222 }
223 }
224
225 pub(super) fn expand_excerpts_with_paths(
226 &mut self,
227 ids: impl IntoIterator<Item = ExcerptId>,
228 line_count: u32,
229 direction: ExpandExcerptDirection,
230 cx: &mut Context<Self>,
231 ) {
232 let mut sorted_ids: Vec<ExcerptId> = ids.into_iter().collect();
233 sorted_ids.sort_by(|a, b| {
234 let path_a = self.paths_by_excerpt.get(a);
235 let path_b = self.paths_by_excerpt.get(b);
236 path_a.cmp(&path_b)
237 });
238 let grouped = sorted_ids
239 .into_iter()
240 .chunk_by(|id| self.paths_by_excerpt.get(id).cloned())
241 .into_iter()
242 .filter_map(|(k, v)| Some((k?, v.into_iter().collect::<Vec<_>>())))
243 .collect::<Vec<_>>();
244 let snapshot = self.snapshot(cx);
245
246 for (path, ids) in grouped.into_iter() {
247 let Some(excerpt_ids) = self.excerpts_by_path.get(&path) else {
248 continue;
249 };
250
251 let ids_to_expand = HashSet::from_iter(ids);
252 let mut excerpt_id_ = None;
253 let expanded_ranges = excerpt_ids.iter().filter_map(|excerpt_id| {
254 let excerpt = snapshot.excerpt(*excerpt_id)?;
255 let excerpt_id = excerpt.id;
256 if excerpt_id_.is_none() {
257 excerpt_id_ = Some(excerpt_id);
258 }
259
260 let mut context = excerpt.range.context.to_point(&excerpt.buffer);
261 if ids_to_expand.contains(&excerpt_id) {
262 match direction {
263 ExpandExcerptDirection::Up => {
264 context.start.row = context.start.row.saturating_sub(line_count);
265 context.start.column = 0;
266 }
267 ExpandExcerptDirection::Down => {
268 context.end.row =
269 (context.end.row + line_count).min(excerpt.buffer.max_point().row);
270 context.end.column = excerpt.buffer.line_len(context.end.row);
271 }
272 ExpandExcerptDirection::UpAndDown => {
273 context.start.row = context.start.row.saturating_sub(line_count);
274 context.start.column = 0;
275 context.end.row =
276 (context.end.row + line_count).min(excerpt.buffer.max_point().row);
277 context.end.column = excerpt.buffer.line_len(context.end.row);
278 }
279 }
280 }
281
282 Some(ExcerptRange {
283 context,
284 primary: excerpt.range.primary.to_point(&excerpt.buffer),
285 })
286 });
287 let mut merged_ranges: Vec<ExcerptRange<Point>> = Vec::new();
288 for range in expanded_ranges {
289 if let Some(last_range) = merged_ranges.last_mut()
290 && last_range.context.end >= range.context.start
291 {
292 last_range.context.end = range.context.end;
293 continue;
294 }
295 merged_ranges.push(range)
296 }
297 let Some(excerpt_id) = excerpt_id_ else {
298 continue;
299 };
300 let Some(buffer_id) = &snapshot.buffer_id_for_excerpt(excerpt_id) else {
301 continue;
302 };
303
304 let Some(buffer) = self.buffers.get(buffer_id).map(|b| b.buffer.clone()) else {
305 continue;
306 };
307
308 let buffer_snapshot = buffer.read(cx).snapshot();
309 self.update_path_excerpts(path.clone(), buffer, &buffer_snapshot, merged_ranges, cx);
310 }
311 }
312
313 /// Sets excerpts, returns `true` if at least one new excerpt was added.
314 pub fn set_merged_excerpt_ranges_for_path(
315 &mut self,
316 path: PathKey,
317 buffer: Entity<Buffer>,
318 ranges: Vec<ExcerptRange<Point>>,
319 buffer_snapshot: &BufferSnapshot,
320 new: Vec<ExcerptRange<Point>>,
321 counts: Vec<usize>,
322 cx: &mut Context<Self>,
323 ) -> PathExcerptInsertResult {
324 let expanded = self.expand_new_ranges_to_existing(&path, buffer_snapshot, new, counts, cx);
325 if !expanded.stale_excerpt_ids.is_empty() {
326 if let Some(existing) = self.excerpts_by_path.get_mut(&path) {
327 existing.retain(|id| !expanded.stale_excerpt_ids.contains(id));
328 }
329 for &id in &expanded.stale_excerpt_ids {
330 self.paths_by_excerpt.remove(&id);
331 }
332 self.remove_excerpts(expanded.stale_excerpt_ids, cx);
333 }
334 let (excerpt_ids, added_new_excerpt) =
335 self.update_path_excerpts(path, buffer, buffer_snapshot, expanded.ranges, cx);
336
337 let mut inserted_ranges = Vec::new();
338 let mut ranges = ranges.into_iter();
339 for (&excerpt_id, range_count) in excerpt_ids.iter().zip(expanded.counts.into_iter()) {
340 for range in ranges.by_ref().take(range_count) {
341 let range = Anchor::range_in_buffer(
342 excerpt_id,
343 buffer_snapshot.anchor_before(&range.primary.start)
344 ..buffer_snapshot.anchor_after(&range.primary.end),
345 );
346 inserted_ranges.push(range)
347 }
348 }
349
350 PathExcerptInsertResult {
351 inserted_ranges,
352 excerpt_ids,
353 added_new_excerpt,
354 }
355 }
356
357 /// Expand each new merged range to encompass any overlapping existing
358 /// excerpt, then re-merge. This turns "partial overlap where the union
359 /// equals the existing range" into an exact match, avoiding unnecessary
360 /// remove+insert churn that floods the wrap map with edits.
361 fn expand_new_ranges_to_existing(
362 &self,
363 path: &PathKey,
364 buffer_snapshot: &BufferSnapshot,
365 mut new: Vec<ExcerptRange<Point>>,
366 counts: Vec<usize>,
367 cx: &App,
368 ) -> ExpandedExcerpts {
369 let existing = self.excerpts_by_path.get(path).cloned().unwrap_or_default();
370 if existing.is_empty() || new.is_empty() {
371 return ExpandedExcerpts {
372 ranges: new,
373 counts,
374 stale_excerpt_ids: Vec::new(),
375 };
376 }
377
378 let snapshot = self.snapshot(cx);
379 let buffer_id = buffer_snapshot.remote_id();
380 let existing_excerpts = existing
381 .iter()
382 .filter_map(|&id| {
383 let excerpt = snapshot.excerpt(id)?;
384 (excerpt.buffer_id == buffer_id).then(|| ExistingExcerpt {
385 id,
386 range: excerpt.range.context.to_point(buffer_snapshot),
387 })
388 })
389 .collect::<Vec<_>>();
390
391 let mut changed = false;
392 let mut stale_excerpt_ids = Vec::new();
393 for new_range in &mut new {
394 let original_start_row = new_range.context.start.row;
395 let original_end_row = new_range.context.end.row;
396 for existing in &existing_excerpts {
397 let overlaps = new_range.context.start <= existing.range.end
398 && new_range.context.end >= existing.range.start;
399 if !overlaps {
400 continue;
401 }
402
403 let start_excess = original_start_row.saturating_sub(existing.range.start.row);
404 let end_excess = existing.range.end.row.saturating_sub(original_end_row);
405
406 if start_excess <= MAX_EXCERPT_EXPANSION_ROWS
407 && end_excess <= MAX_EXCERPT_EXPANSION_ROWS
408 {
409 if existing.range.start < new_range.context.start {
410 new_range.context.start = existing.range.start;
411 changed = true;
412 }
413 if existing.range.end > new_range.context.end {
414 new_range.context.end = existing.range.end;
415 changed = true;
416 }
417 } else {
418 stale_excerpt_ids.push(existing.id);
419 }
420 }
421 }
422
423 if !changed && stale_excerpt_ids.is_empty() {
424 return ExpandedExcerpts {
425 ranges: new,
426 counts,
427 stale_excerpt_ids: Vec::new(),
428 };
429 }
430
431 let mut result_ranges: Vec<ExcerptRange<Point>> = Vec::new();
432 let mut result_counts: Vec<usize> = Vec::new();
433 for (range, count) in new.into_iter().zip(counts) {
434 if let Some(last) = result_ranges.last_mut() {
435 if last.context.end >= range.context.start
436 || last.context.end.row + 1 == range.context.start.row
437 {
438 last.context.end = last.context.end.max(range.context.end);
439 *result_counts.last_mut().unwrap() += count;
440 continue;
441 }
442 }
443 result_ranges.push(range);
444 result_counts.push(count);
445 }
446
447 ExpandedExcerpts {
448 ranges: result_ranges,
449 counts: result_counts,
450 stale_excerpt_ids,
451 }
452 }
453
454 fn update_path_excerpts(
455 &mut self,
456 path: PathKey,
457 buffer: Entity<Buffer>,
458 buffer_snapshot: &BufferSnapshot,
459 new: Vec<ExcerptRange<Point>>,
460 cx: &mut Context<Self>,
461 ) -> (Vec<ExcerptId>, bool) {
462 let mut insert_after = self
463 .excerpts_by_path
464 .range(..path.clone())
465 .next_back()
466 .and_then(|(_, value)| value.last().copied())
467 .unwrap_or(ExcerptId::min());
468
469 let existing = self
470 .excerpts_by_path
471 .get(&path)
472 .cloned()
473 .unwrap_or_default();
474 let mut new_iter = new.into_iter().peekable();
475 let mut existing_iter = existing.into_iter().peekable();
476
477 let mut excerpt_ids = Vec::new();
478 let mut to_remove = Vec::new();
479 let mut to_insert: Vec<(ExcerptId, ExcerptRange<Point>)> = Vec::new();
480 let mut added_a_new_excerpt = false;
481 let snapshot = self.snapshot(cx);
482
483 let mut next_excerpt_id =
484 if let Some(last_entry) = self.snapshot.get_mut().excerpt_ids.last() {
485 last_entry.id.0 + 1
486 } else {
487 1
488 };
489
490 let mut next_excerpt_id = move || ExcerptId(post_inc(&mut next_excerpt_id));
491
492 let mut excerpts_cursor = snapshot.excerpts.cursor::<Option<&Locator>>(());
493 excerpts_cursor.next();
494
495 loop {
496 let existing = if let Some(&existing_id) = existing_iter.peek() {
497 let locator = snapshot.excerpt_locator_for_id(existing_id);
498 excerpts_cursor.seek_forward(&Some(locator), Bias::Left);
499 if let Some(excerpt) = excerpts_cursor.item() {
500 if excerpt.buffer_id != buffer_snapshot.remote_id() {
501 to_remove.push(existing_id);
502 existing_iter.next();
503 continue;
504 }
505 Some((existing_id, excerpt.range.context.to_point(buffer_snapshot)))
506 } else {
507 None
508 }
509 } else {
510 None
511 };
512
513 let new = new_iter.peek();
514 // Try to merge the next new range or existing excerpt into the last
515 // queued insert.
516 if let Some((last_id, last)) = to_insert.last_mut() {
517 // Next new range overlaps the last queued insert: absorb it by
518 // extending the insert's end.
519 if let Some(new) = new
520 && last.context.end >= new.context.start
521 {
522 last.context.end = last.context.end.max(new.context.end);
523 excerpt_ids.push(*last_id);
524 new_iter.next();
525 continue;
526 }
527 // Next existing excerpt overlaps the last queued insert: absorb
528 // it by extending the insert's end, and record the existing
529 // excerpt as replaced so anchors in it resolve to the new one.
530 if let Some((existing_id, existing_range)) = &existing
531 && last.context.end >= existing_range.start
532 {
533 last.context.end = last.context.end.max(existing_range.end);
534 to_remove.push(*existing_id);
535 Arc::make_mut(&mut self.snapshot.get_mut().replaced_excerpts)
536 .insert(*existing_id, *last_id);
537 existing_iter.next();
538 continue;
539 }
540 }
541
542 match (new, existing) {
543 (None, None) => break,
544
545 // No more new ranges; remove the remaining existing excerpt.
546 (None, Some((existing_id, _))) => {
547 existing_iter.next();
548 to_remove.push(existing_id);
549 }
550
551 // No more existing excerpts; queue the new range for insertion.
552 (Some(_), None) => {
553 added_a_new_excerpt = true;
554 let new_id = next_excerpt_id();
555 excerpt_ids.push(new_id);
556 to_insert.push((new_id, new_iter.next().unwrap()));
557 }
558
559 // Existing excerpt ends before the new range starts, so it
560 // has no corresponding new range and must be removed. Flush
561 // pending inserts and advance `insert_after` past it so that
562 // future inserts receive locators *after* this excerpt's
563 // locator, preserving forward ordering.
564 (Some(new), Some((_, existing_range)))
565 if existing_range.end < new.context.start =>
566 {
567 self.insert_excerpts_with_ids_after(
568 insert_after,
569 buffer.clone(),
570 mem::take(&mut to_insert),
571 cx,
572 );
573 insert_after = existing_iter.next().unwrap();
574 to_remove.push(insert_after);
575 }
576 // New range ends before the existing excerpt starts, so the
577 // new range has no corresponding existing excerpt. Queue it
578 // for insertion at the current `insert_after` position
579 // (before the existing excerpt), which is the correct
580 // spatial ordering.
581 (Some(new), Some((_, existing_range)))
582 if existing_range.start > new.context.end =>
583 {
584 let new_id = next_excerpt_id();
585 excerpt_ids.push(new_id);
586 to_insert.push((new_id, new_iter.next().unwrap()));
587 }
588 // Exact match: keep the existing excerpt in place, flush
589 // any pending inserts before it, and use it as the new
590 // `insert_after` anchor.
591 (Some(new), Some((_, existing_range)))
592 if existing_range.start == new.context.start
593 && existing_range.end == new.context.end =>
594 {
595 self.insert_excerpts_with_ids_after(
596 insert_after,
597 buffer.clone(),
598 mem::take(&mut to_insert),
599 cx,
600 );
601 insert_after = existing_iter.next().unwrap();
602 excerpt_ids.push(insert_after);
603 new_iter.next();
604 }
605
606 // Partial overlap: replace the existing excerpt with a new
607 // one whose range is the union of both, and record the
608 // replacement so that anchors in the old excerpt resolve to
609 // the new one.
610 (Some(_), Some((_, existing_range))) => {
611 let existing_id = existing_iter.next().unwrap();
612 let new_id = next_excerpt_id();
613 Arc::make_mut(&mut self.snapshot.get_mut().replaced_excerpts)
614 .insert(existing_id, new_id);
615 to_remove.push(existing_id);
616 let mut range = new_iter.next().unwrap();
617 range.context.start = range.context.start.min(existing_range.start);
618 range.context.end = range.context.end.max(existing_range.end);
619 excerpt_ids.push(new_id);
620 to_insert.push((new_id, range));
621 }
622 };
623 }
624
625 self.insert_excerpts_with_ids_after(insert_after, buffer, to_insert, cx);
626 // todo(lw): There is a logic bug somewhere that causes the to_remove vector to be not ordered correctly
627 to_remove.sort_by_cached_key(|&id| snapshot.excerpt_locator_for_id(id));
628 self.remove_excerpts(to_remove, cx);
629
630 if excerpt_ids.is_empty() {
631 self.excerpts_by_path.remove(&path);
632 } else {
633 let snapshot = &*self.snapshot.get_mut();
634 let excerpt_ids = excerpt_ids
635 .iter()
636 .dedup()
637 .cloned()
638 // todo(lw): There is a logic bug somewhere that causes excerpt_ids to not necessarily be in order by locator
639 .sorted_by_cached_key(|&id| snapshot.excerpt_locator_for_id(id))
640 .collect();
641 for &excerpt_id in &excerpt_ids {
642 self.paths_by_excerpt.insert(excerpt_id, path.clone());
643 }
644 self.excerpts_by_path.insert(path, excerpt_ids);
645 }
646
647 (excerpt_ids, added_a_new_excerpt)
648 }
649}