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