1use crate::{buffer, Buffer, Chunk};
2use collections::HashMap;
3use gpui::{AppContext, Entity, ModelContext, ModelHandle};
4use parking_lot::Mutex;
5use smallvec::{smallvec, SmallVec};
6use std::{cmp, iter, ops::Range};
7use sum_tree::{Bias, Cursor, SumTree};
8use text::{
9 subscription::{Subscription, Topic},
10 Anchor, AnchorRangeExt, Edit, Patch, TextSummary,
11};
12use theme::SyntaxTheme;
13
14const NEWLINES: &'static [u8] = &[b'\n'; u8::MAX as usize];
15
16pub trait ToOffset {
17 fn to_offset<'a>(&self, content: &Snapshot) -> usize;
18}
19
20pub type ExcerptId = Location;
21
22#[derive(Default)]
23pub struct ExcerptList {
24 snapshot: Mutex<Snapshot>,
25 buffers: HashMap<usize, BufferState>,
26 subscriptions: Topic,
27}
28
29#[derive(Debug)]
30struct BufferState {
31 buffer: ModelHandle<Buffer>,
32 last_sync: clock::Global,
33 excerpts: Vec<ExcerptId>,
34}
35
36#[derive(Clone, Default)]
37pub struct Snapshot {
38 excerpts: SumTree<Excerpt>,
39}
40
41pub struct ExcerptProperties<'a, T> {
42 buffer: &'a ModelHandle<Buffer>,
43 range: Range<T>,
44 header_height: u8,
45}
46
47#[derive(Clone)]
48struct Excerpt {
49 id: ExcerptId,
50 buffer: buffer::Snapshot,
51 range: Range<Anchor>,
52 text_summary: TextSummary,
53 header_height: u8,
54}
55
56#[derive(Clone, Debug, Default)]
57struct EntrySummary {
58 excerpt_id: ExcerptId,
59 text: TextSummary,
60}
61
62#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
63pub struct Location(SmallVec<[u8; 4]>);
64
65pub struct Chunks<'a> {
66 range: Range<usize>,
67 cursor: Cursor<'a, Excerpt, usize>,
68 header_height: u8,
69 entry_chunks: Option<buffer::Chunks<'a>>,
70 theme: Option<&'a SyntaxTheme>,
71}
72
73impl ExcerptList {
74 pub fn new() -> Self {
75 Self::default()
76 }
77
78 pub fn snapshot(&self, cx: &AppContext) -> Snapshot {
79 self.sync(cx);
80 self.snapshot.lock().clone()
81 }
82
83 pub fn subscribe(&mut self) -> Subscription {
84 self.subscriptions.subscribe()
85 }
86
87 pub fn push<O>(&mut self, props: ExcerptProperties<O>, cx: &mut ModelContext<Self>) -> ExcerptId
88 where
89 O: text::ToOffset,
90 {
91 self.sync(cx);
92
93 let buffer = props.buffer.read(cx);
94 let range = buffer.anchor_before(props.range.start)..buffer.anchor_after(props.range.end);
95 let mut snapshot = self.snapshot.lock();
96 let prev_id = snapshot.excerpts.last().map(|e| &e.id);
97 let id = ExcerptId::between(prev_id.unwrap_or(&ExcerptId::min()), &ExcerptId::max());
98
99 let edit_start = snapshot.excerpts.summary().text.bytes;
100 let excerpt = Excerpt::new(id.clone(), buffer.snapshot(), range, props.header_height);
101 let edit = Edit {
102 old: edit_start..edit_start,
103 new: edit_start..edit_start + excerpt.text_summary.bytes,
104 };
105 snapshot.excerpts.push(excerpt, &());
106 self.buffers
107 .entry(props.buffer.id())
108 .or_insert_with(|| BufferState {
109 buffer: props.buffer.clone(),
110 last_sync: buffer.version(),
111 excerpts: Default::default(),
112 })
113 .excerpts
114 .push(id.clone());
115
116 self.subscriptions.publish_mut([edit]);
117
118 id
119 }
120
121 fn sync(&self, cx: &AppContext) {
122 let mut snapshot = self.snapshot.lock();
123 let mut excerpts_to_edit = Vec::new();
124 for buffer_state in self.buffers.values() {
125 if buffer_state
126 .buffer
127 .read(cx)
128 .version()
129 .gt(&buffer_state.last_sync)
130 {
131 excerpts_to_edit.extend(
132 buffer_state
133 .excerpts
134 .iter()
135 .map(|excerpt_id| (excerpt_id, buffer_state)),
136 );
137 }
138 }
139 excerpts_to_edit.sort_unstable_by_key(|(excerpt_id, _)| *excerpt_id);
140
141 let mut patch = Patch::<usize>::default();
142 let mut new_excerpts = SumTree::new();
143 let mut cursor = snapshot.excerpts.cursor::<(ExcerptId, usize)>();
144
145 for (id, buffer_state) in excerpts_to_edit {
146 new_excerpts.push_tree(cursor.slice(id, Bias::Left, &()), &());
147 let old_excerpt = cursor.item().unwrap();
148 let buffer = buffer_state.buffer.read(cx);
149 new_excerpts.push(
150 Excerpt::new(
151 id.clone(),
152 buffer.snapshot(),
153 old_excerpt.range.clone(),
154 old_excerpt.header_height,
155 ),
156 &(),
157 );
158
159 let edits = buffer
160 .edits_since_in_range::<usize>(
161 old_excerpt.buffer.version(),
162 old_excerpt.range.clone(),
163 )
164 .map(|mut edit| {
165 let excerpt_old_start = cursor.start().1;
166 let excerpt_new_start = new_excerpts.summary().text.bytes;
167 edit.old.start += excerpt_old_start;
168 edit.old.end += excerpt_old_start;
169 edit.new.start += excerpt_new_start;
170 edit.new.end += excerpt_new_start;
171 edit
172 });
173 patch = patch.compose(edits);
174
175 cursor.next(&());
176 }
177 new_excerpts.push_tree(cursor.suffix(&()), &());
178
179 drop(cursor);
180 snapshot.excerpts = new_excerpts;
181
182 self.subscriptions.publish(&patch);
183 }
184}
185
186impl Entity for ExcerptList {
187 type Event = ();
188}
189
190impl Snapshot {
191 pub fn text(&self) -> String {
192 self.chunks(0..self.len(), None)
193 .map(|chunk| chunk.text)
194 .collect()
195 }
196
197 pub fn len(&self) -> usize {
198 self.excerpts.summary().text.bytes
199 }
200
201 pub fn chunks<'a, T: ToOffset>(
202 &'a self,
203 range: Range<T>,
204 theme: Option<&'a SyntaxTheme>,
205 ) -> Chunks<'a> {
206 let range = range.start.to_offset(self)..range.end.to_offset(self);
207 let mut cursor = self.excerpts.cursor::<usize>();
208 cursor.seek(&range.start, Bias::Right, &());
209
210 let entry_chunks = cursor.item().map(|entry| {
211 let buffer_range = entry.range.to_offset(&entry.buffer);
212 let buffer_start = buffer_range.start + (range.start - cursor.start());
213 let buffer_end = cmp::min(
214 buffer_range.end,
215 buffer_range.start + (range.end - cursor.start()),
216 );
217 entry.buffer.chunks(buffer_start..buffer_end, theme)
218 });
219 let header_height = cursor.item().map_or(0, |entry| entry.header_height);
220
221 Chunks {
222 range,
223 cursor,
224 header_height,
225 entry_chunks,
226 theme,
227 }
228 }
229}
230
231impl Excerpt {
232 fn new(
233 id: ExcerptId,
234 buffer: buffer::Snapshot,
235 range: Range<Anchor>,
236 header_height: u8,
237 ) -> Self {
238 let mut text_summary = buffer.text_summary_for_range::<TextSummary, _>(range.clone());
239 if header_height > 0 {
240 text_summary.first_line_chars = 0;
241 text_summary.lines.row += header_height as u32;
242 text_summary.lines_utf16.row += header_height as u32;
243 text_summary.bytes += header_height as usize;
244 }
245 Excerpt {
246 id,
247 buffer,
248 range,
249 text_summary,
250 header_height,
251 }
252 }
253}
254
255impl sum_tree::Item for Excerpt {
256 type Summary = EntrySummary;
257
258 fn summary(&self) -> Self::Summary {
259 EntrySummary {
260 excerpt_id: self.id.clone(),
261 text: self.text_summary.clone(),
262 }
263 }
264}
265
266impl sum_tree::Summary for EntrySummary {
267 type Context = ();
268
269 fn add_summary(&mut self, summary: &Self, _: &()) {
270 debug_assert!(summary.excerpt_id > self.excerpt_id);
271 self.excerpt_id = summary.excerpt_id.clone();
272 self.text.add_summary(&summary.text, &());
273 }
274}
275
276impl<'a> sum_tree::Dimension<'a, EntrySummary> for usize {
277 fn add_summary(&mut self, summary: &'a EntrySummary, _: &()) {
278 *self += summary.text.bytes;
279 }
280}
281
282impl<'a> sum_tree::Dimension<'a, EntrySummary> for Location {
283 fn add_summary(&mut self, summary: &'a EntrySummary, _: &()) {
284 debug_assert!(summary.excerpt_id > *self);
285 *self = summary.excerpt_id.clone();
286 }
287}
288
289impl<'a> Iterator for Chunks<'a> {
290 type Item = Chunk<'a>;
291
292 fn next(&mut self) -> Option<Self::Item> {
293 if self.header_height > 0 {
294 let chunk = Chunk {
295 text: unsafe {
296 std::str::from_utf8_unchecked(&NEWLINES[..self.header_height as usize])
297 },
298 ..Default::default()
299 };
300 self.header_height = 0;
301 return Some(chunk);
302 }
303
304 if let Some(entry_chunks) = self.entry_chunks.as_mut() {
305 if let Some(chunk) = entry_chunks.next() {
306 return Some(chunk);
307 } else {
308 self.entry_chunks.take();
309 }
310 }
311
312 self.cursor.next(&());
313 let entry = self.cursor.item()?;
314 let buffer_range = entry.range.to_offset(&entry.buffer);
315 let buffer_end = cmp::min(
316 buffer_range.end,
317 buffer_range.start + (self.range.end - self.cursor.start()),
318 );
319
320 self.header_height = entry.header_height;
321 self.entry_chunks = Some(
322 entry
323 .buffer
324 .chunks(buffer_range.start..buffer_end, self.theme),
325 );
326
327 Some(Chunk {
328 text: "\n",
329 ..Default::default()
330 })
331 }
332}
333
334impl ToOffset for usize {
335 fn to_offset<'a>(&self, _: &Snapshot) -> usize {
336 *self
337 }
338}
339
340impl Default for Location {
341 fn default() -> Self {
342 Self::min()
343 }
344}
345
346impl Location {
347 pub fn min() -> Self {
348 Self(smallvec![u8::MIN])
349 }
350
351 pub fn max() -> Self {
352 Self(smallvec![u8::MAX])
353 }
354
355 pub fn between(lhs: &Self, rhs: &Self) -> Self {
356 let lhs = lhs.0.iter().copied().chain(iter::repeat(u8::MIN));
357 let rhs = rhs.0.iter().copied().chain(iter::repeat(u8::MAX));
358 let mut location = SmallVec::new();
359 for (lhs, rhs) in lhs.zip(rhs) {
360 let mid = lhs + (rhs.saturating_sub(lhs)) / 2;
361 location.push(mid);
362 if mid > lhs {
363 break;
364 }
365 }
366 Self(location)
367 }
368}
369
370#[cfg(test)]
371mod tests {
372 use super::*;
373 use crate::Buffer;
374 use gpui::MutableAppContext;
375 use rand::prelude::*;
376 use std::{env, mem};
377 use text::{Point, RandomCharIter};
378 use util::test::sample_text;
379
380 #[gpui::test]
381 fn test_excerpt_buffer(cx: &mut MutableAppContext) {
382 let buffer_1 = cx.add_model(|cx| Buffer::new(0, sample_text(6, 6, 'a'), cx));
383 let buffer_2 = cx.add_model(|cx| Buffer::new(0, sample_text(6, 6, 'g'), cx));
384
385 let list = cx.add_model(|cx| ExcerptList::new());
386
387 let subscription = list.update(cx, |list, cx| {
388 let subscription = list.subscribe();
389 list.push(
390 ExcerptProperties {
391 buffer: &buffer_1,
392 range: Point::new(1, 2)..Point::new(2, 5),
393 header_height: 2,
394 },
395 cx,
396 );
397 assert_eq!(
398 subscription.consume().into_inner(),
399 [Edit {
400 old: 0..0,
401 new: 0..12
402 }]
403 );
404
405 list.push(
406 ExcerptProperties {
407 buffer: &buffer_1,
408 range: Point::new(3, 3)..Point::new(4, 4),
409 header_height: 1,
410 },
411 cx,
412 );
413 list.push(
414 ExcerptProperties {
415 buffer: &buffer_2,
416 range: Point::new(3, 1)..Point::new(3, 3),
417 header_height: 3,
418 },
419 cx,
420 );
421 assert_eq!(
422 subscription.consume().into_inner(),
423 [Edit {
424 old: 12..12,
425 new: 12..26
426 }]
427 );
428
429 subscription
430 });
431
432 assert_eq!(
433 list.read(cx).snapshot(cx).text(),
434 concat!(
435 "\n", // Preserve newlines
436 "\n", //
437 "bbbb\n", //
438 "ccccc\n", //
439 "\n", //
440 "ddd\n", //
441 "eeee\n", //
442 "\n", //
443 "\n", //
444 "\n", //
445 "jj" //
446 )
447 );
448
449 buffer_1.update(cx, |buffer, cx| {
450 buffer.edit(
451 [
452 Point::new(0, 0)..Point::new(0, 0),
453 Point::new(2, 1)..Point::new(2, 3),
454 ],
455 "\n",
456 cx,
457 );
458 });
459
460 assert_eq!(
461 list.read(cx).snapshot(cx).text(),
462 concat!(
463 "\n", // Preserve newlines
464 "\n", //
465 "bbbb\n", //
466 "c\n", //
467 "cc\n", //
468 "\n", //
469 "ddd\n", //
470 "eeee\n", //
471 "\n", //
472 "\n", //
473 "\n", //
474 "jj" //
475 )
476 );
477
478 assert_eq!(
479 subscription.consume().into_inner(),
480 [Edit {
481 old: 17..19,
482 new: 17..18
483 }]
484 );
485 }
486
487 #[gpui::test(iterations = 100)]
488 fn test_random(cx: &mut MutableAppContext, mut rng: StdRng) {
489 let operations = env::var("OPERATIONS")
490 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
491 .unwrap_or(10);
492
493 let mut buffers: Vec<ModelHandle<Buffer>> = Vec::new();
494 let list = cx.add_model(|_| ExcerptList::new());
495 let mut excerpt_ids = Vec::new();
496 let mut expected_excerpts = Vec::new();
497
498 for _ in 0..operations {
499 match rng.gen_range(0..100) {
500 0..=19 if !buffers.is_empty() => {
501 let buffer = buffers.choose(&mut rng).unwrap();
502 buffer.update(cx, |buf, cx| buf.randomly_edit(&mut rng, 5, cx));
503 }
504 _ => {
505 let buffer_handle = if buffers.is_empty() || rng.gen_bool(0.4) {
506 let base_text = RandomCharIter::new(&mut rng).take(10).collect::<String>();
507 buffers.push(cx.add_model(|cx| Buffer::new(0, base_text, cx)));
508 buffers.last().unwrap()
509 } else {
510 buffers.choose(&mut rng).unwrap()
511 };
512
513 let buffer = buffer_handle.read(cx);
514 let end_ix = buffer.clip_offset(rng.gen_range(0..=buffer.len()), Bias::Right);
515 let start_ix = buffer.clip_offset(rng.gen_range(0..=end_ix), Bias::Left);
516 let header_height = rng.gen_range(0..=5);
517 let anchor_range = buffer.anchor_before(start_ix)..buffer.anchor_after(end_ix);
518 log::info!(
519 "Pushing excerpt for buffer {}: {:?}[{:?}] = {:?}",
520 buffer_handle.id(),
521 buffer.text(),
522 start_ix..end_ix,
523 &buffer.text()[start_ix..end_ix]
524 );
525
526 let excerpt_id = list.update(cx, |list, cx| {
527 list.push(
528 ExcerptProperties {
529 buffer: &buffer_handle,
530 range: start_ix..end_ix,
531 header_height,
532 },
533 cx,
534 )
535 });
536 excerpt_ids.push(excerpt_id);
537 expected_excerpts.push((buffer_handle.clone(), anchor_range, header_height));
538 }
539 }
540
541 let snapshot = list.read(cx).snapshot(cx);
542 let mut expected_text = String::new();
543 for (buffer, range, header_height) in &expected_excerpts {
544 let buffer = buffer.read(cx);
545 if !expected_text.is_empty() {
546 expected_text.push('\n');
547 }
548
549 for _ in 0..*header_height {
550 expected_text.push('\n');
551 }
552 expected_text.extend(buffer.text_for_range(range.clone()));
553 }
554 assert_eq!(snapshot.text(), expected_text);
555 }
556 }
557
558 #[gpui::test(iterations = 100)]
559 fn test_location(mut rng: StdRng) {
560 let mut lhs = Default::default();
561 let mut rhs = Default::default();
562 while lhs == rhs {
563 lhs = Location(
564 (0..rng.gen_range(1..=5))
565 .map(|_| rng.gen_range(0..=100))
566 .collect(),
567 );
568 rhs = Location(
569 (0..rng.gen_range(1..=5))
570 .map(|_| rng.gen_range(0..=100))
571 .collect(),
572 );
573 }
574
575 if lhs > rhs {
576 mem::swap(&mut lhs, &mut rhs);
577 }
578
579 let middle = Location::between(&lhs, &rhs);
580 assert!(middle > lhs);
581 assert!(middle < rhs);
582 for ix in 0..middle.0.len() - 1 {
583 assert!(
584 middle.0[ix] == *lhs.0.get(ix).unwrap_or(&0)
585 || middle.0[ix] == *rhs.0.get(ix).unwrap_or(&0)
586 );
587 }
588 }
589}