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