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