1use std::{
2 cmp::{self, Ordering},
3 collections::BTreeMap,
4 mem,
5 sync::atomic::{AtomicUsize, Ordering::SeqCst},
6};
7
8use buffer::{Anchor, Bias, Edit, Point, Rope, TextSummary, ToOffset, ToPoint};
9use gpui::{fonts::HighlightStyle, AppContext, ModelHandle};
10use language::Buffer;
11use parking_lot::Mutex;
12use sum_tree::SumTree;
13use util::post_inc;
14
15#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Ord, PartialOrd)]
16pub struct InjectionId(usize);
17
18pub struct InjectionMap {
19 buffer: ModelHandle<Buffer>,
20 transforms: Mutex<SumTree<Transform>>,
21 injections: SumTree<Injection>,
22 injection_sites: SumTree<InjectionSite>,
23 version: AtomicUsize,
24 last_sync: Mutex<SyncState>,
25 next_injection_id: usize,
26}
27
28pub struct Snapshot {
29 transforms: SumTree<Transform>,
30 injections: SumTree<Injection>,
31 buffer_snapshot: language::Snapshot,
32 pub version: usize,
33}
34
35pub struct InjectionMapWriter<'a>(&'a mut InjectionMap);
36
37#[derive(Clone)]
38struct SyncState {
39 version: clock::Global,
40 parse_count: usize,
41 diagnostics_update_count: usize,
42}
43
44#[derive(Clone, Debug)]
45struct InjectionSummary {
46 min_id: InjectionId,
47 max_id: InjectionId,
48 min_position: Anchor,
49 max_position: Anchor,
50}
51
52#[derive(Clone, Debug)]
53struct Injection {
54 id: InjectionId,
55 text: Rope,
56 runs: Vec<(usize, HighlightStyle)>,
57}
58
59#[derive(Clone, Debug)]
60pub struct InjectionProps {
61 text: Rope,
62 runs: Vec<(usize, HighlightStyle)>,
63 disposition: Disposition,
64}
65
66#[derive(Clone, Debug)]
67pub enum Disposition {
68 BeforeLine,
69 AfterLine,
70}
71
72#[derive(Clone, Debug)]
73struct InjectionSite {
74 injection_id: InjectionId,
75 position: Anchor,
76 disposition: Disposition,
77}
78
79#[derive(Clone, Debug)]
80struct InjectionSitePosition(Anchor);
81
82#[derive(Clone, Debug, Eq, PartialEq)]
83struct InjectionSiteSummary {
84 min_injection_id: InjectionId,
85 max_injection_id: InjectionId,
86 min_position: Anchor,
87 max_position: Anchor,
88}
89
90#[derive(Clone, Debug, Default, PartialEq)]
91struct Transform {
92 input: TextSummary,
93 output: TextSummary,
94 injection_id: Option<InjectionId>,
95}
96
97#[derive(Clone, Debug, Default, Eq, PartialEq)]
98struct TransformSummary {
99 input: TextSummary,
100 output: TextSummary,
101 min_injection_id: InjectionId,
102 max_injection_id: InjectionId,
103}
104
105#[derive(Copy, Clone, Debug, Default)]
106pub struct InjectionOffset(usize);
107
108impl sum_tree::Summary for InjectionId {
109 type Context = ();
110
111 fn add_summary(&mut self, summary: &Self, cx: &Self::Context) {
112 *self = *summary
113 }
114}
115
116impl InjectionMap {
117 pub fn new(buffer_handle: ModelHandle<Buffer>, cx: &AppContext) -> (Self, Snapshot) {
118 let buffer = buffer_handle.read(cx);
119 let this = Self {
120 buffer: buffer_handle,
121 injections: Default::default(),
122 injection_sites: Default::default(),
123 transforms: Mutex::new(SumTree::from_item(
124 Transform::isomorphic(buffer.text_summary()),
125 &(),
126 )),
127 last_sync: Mutex::new(SyncState {
128 version: buffer.version(),
129 parse_count: buffer.parse_count(),
130 diagnostics_update_count: buffer.diagnostics_update_count(),
131 }),
132 version: AtomicUsize::new(0),
133 next_injection_id: 0,
134 };
135 let (snapshot, _) = this.read(cx);
136 (this, snapshot)
137 }
138
139 pub fn read(&self, cx: &AppContext) -> (Snapshot, Vec<Edit<InjectionOffset>>) {
140 let edits = self.sync(cx);
141 // self.check_invariants(cx);
142 let snapshot = Snapshot {
143 transforms: self.transforms.lock().clone(),
144 injections: self.injections.clone(),
145 buffer_snapshot: self.buffer.read(cx).snapshot(),
146 version: self.version.load(SeqCst),
147 };
148 (snapshot, edits)
149 }
150
151 pub fn write(
152 &mut self,
153 cx: &AppContext,
154 ) -> (InjectionMapWriter, Snapshot, Vec<Edit<InjectionOffset>>) {
155 let (snapshot, edits) = self.read(cx);
156 (InjectionMapWriter(self), snapshot, edits)
157 }
158
159 fn sync(&self, cx: &AppContext) -> Vec<Edit<InjectionOffset>> {
160 let buffer = self.buffer.read(cx);
161 let last_sync = mem::replace(
162 &mut *self.last_sync.lock(),
163 SyncState {
164 version: buffer.version(),
165 parse_count: buffer.parse_count(),
166 diagnostics_update_count: buffer.diagnostics_update_count(),
167 },
168 );
169 let edits = buffer
170 .edits_since(&last_sync.version)
171 .map(Into::into)
172 .collect::<Vec<_>>();
173 if edits.is_empty() {
174 if last_sync.parse_count != buffer.parse_count()
175 || last_sync.diagnostics_update_count != buffer.diagnostics_update_count()
176 {
177 self.version.fetch_add(1, SeqCst);
178 }
179 Vec::new()
180 } else {
181 self.apply_edits(edits, cx)
182 }
183 }
184
185 fn apply_edits(
186 &self,
187 buffer_edits: Vec<buffer::Edit<Point>>,
188 cx: &AppContext,
189 ) -> Vec<Edit<InjectionOffset>> {
190 let buffer = self.buffer.read(cx);
191 let mut buffer_edits_iter = buffer_edits.iter().cloned().peekable();
192
193 let mut new_transforms = SumTree::<Transform>::new();
194 let mut transforms = self.transforms.lock();
195 let old_max_point = transforms.summary().input.lines;
196 let new_max_point = buffer.max_point();
197 let mut cursor = transforms.cursor::<Point>();
198 let mut injection_sites = self.injection_sites.cursor::<InjectionSitePosition>();
199 let mut pending_after_injections: Vec<InjectionId> = Vec::new();
200
201 while let Some(mut edit) = buffer_edits_iter.next() {
202 dbg!(&edit);
203 // Expand this edit to line boundaries.
204 edit.old.start.column = 0;
205 edit.old.end += Point::new(1, 0);
206 edit.new.start.column = 0;
207 edit.new.end += Point::new(1, 0);
208
209 // Push any transforms preceding the edit.
210 new_transforms.push_tree(cursor.slice(&edit.old.start, Bias::Left, &()), &());
211
212 // Snap edits to row boundaries of intersecting transforms.
213 loop {
214 if cmp::min(edit.old.end, old_max_point) <= cursor.end(&()) {
215 cursor.seek(&edit.old.end, Bias::Left, &());
216 cursor.next(&());
217 let new_old_end = *cursor.start() + Point::new(1, 0);
218 edit.new.end += new_old_end - edit.old.end;
219 edit.old.end = new_old_end;
220 }
221
222 if buffer_edits_iter.peek().map_or(false, |next_edit| {
223 edit.old.end.row >= next_edit.old.start.row
224 }) {
225 let next_edit = buffer_edits_iter.next().unwrap();
226 edit.old.end = cmp::max(edit.old.end, next_edit.old.end + Point::new(1, 0));
227 let row_delta = (next_edit.new.end.row as i32 - next_edit.new.start.row as i32)
228 - (next_edit.old.end.row as i32 - next_edit.old.start.row as i32);
229 edit.new.end.row = (edit.new.end.row as i32 + row_delta) as u32;
230 } else {
231 break;
232 }
233 }
234
235 dbg!(&edit);
236
237 // Find and insert all injections on the lines spanned by the edit, interleaved with isomorphic regions
238 injection_sites.seek(
239 &InjectionSitePosition(buffer.anchor_before(edit.new.start)),
240 Bias::Right,
241 buffer,
242 );
243 let mut last_injection_row: Option<u32> = None;
244 while let Some(site) = injection_sites.item() {
245 let injection_row = site.position.to_point(buffer).row;
246
247 if injection_row > edit.new.end.row {
248 break;
249 }
250
251 // If we've moved on to a new injection row, ensure that any pending injections with an after
252 // disposition are inserted after their target row
253 if let Some(last_injection_row) = last_injection_row {
254 if injection_row != last_injection_row {
255 let injection_point = Point::new(last_injection_row + 1, 0);
256 if injection_point > new_transforms.summary().input.lines {
257 let injection_offset = injection_point.to_offset(buffer);
258 new_transforms.push(
259 Transform::isomorphic(buffer.text_summary_for_range(
260 new_transforms.summary().input.bytes..injection_offset,
261 )),
262 &(),
263 );
264 }
265 for injection_id in pending_after_injections.drain(..) {
266 new_transforms.push(
267 Transform::for_injection(
268 self.injections.get(&injection_id, &()).unwrap(),
269 ),
270 &(),
271 )
272 }
273 }
274 }
275
276 match site.disposition {
277 Disposition::AfterLine => pending_after_injections.push(site.injection_id),
278 Disposition::BeforeLine => {
279 let injection_point = Point::new(injection_row, 0);
280 if injection_point > new_transforms.summary().input.lines {
281 let injection_offset = injection_point.to_offset(buffer);
282 new_transforms.push(
283 Transform::isomorphic(buffer.text_summary_for_range(
284 new_transforms.summary().input.bytes..injection_offset,
285 )),
286 &(),
287 );
288 }
289 new_transforms.push(
290 Transform::for_injection(
291 self.injections.get(&site.injection_id, &()).unwrap(),
292 ),
293 &(),
294 );
295 }
296 }
297
298 last_injection_row = Some(injection_row);
299 }
300
301 if let Some(last_injection_row) = last_injection_row {
302 let injection_point = Point::new(last_injection_row + 1, 0);
303 if injection_point > new_transforms.summary().input.lines {
304 let injection_offset = injection_point.to_offset(buffer);
305 new_transforms.push(
306 Transform::isomorphic(buffer.text_summary_for_range(
307 new_transforms.summary().input.bytes..injection_offset,
308 )),
309 &(),
310 );
311 }
312 for injection_id in pending_after_injections.drain(..) {
313 new_transforms.push(
314 Transform::for_injection(self.injections.get(&injection_id, &()).unwrap()),
315 &(),
316 )
317 }
318 }
319
320 let sum = new_transforms.summary();
321 let new_end = cmp::min(edit.new.end, new_max_point);
322 if sum.input.lines < new_end {
323 let text_summary =
324 buffer.text_summary_for_range(sum.input.bytes..new_end.to_offset(buffer));
325 new_transforms.push(Transform::isomorphic(text_summary), &());
326 }
327 }
328 new_transforms.push_tree(cursor.suffix(&()), &());
329 drop(cursor);
330
331 *transforms = new_transforms;
332 Vec::new()
333 }
334}
335
336impl<'a> InjectionMapWriter<'a> {
337 pub fn insert<'b, T, U>(
338 &mut self,
339 injections: T,
340 cx: &AppContext,
341 ) -> (Vec<InjectionId>, Snapshot, Vec<Edit<InjectionOffset>>)
342 where
343 T: IntoIterator<Item = (Anchor, InjectionProps)>,
344 {
345 let buffer = self.0.buffer.read(cx);
346 let mut cursor = self.0.injection_sites.cursor::<InjectionSitePosition>();
347 let mut new_sites = SumTree::new();
348 let mut injection_ids = Vec::new();
349 let mut edits = Vec::new();
350
351 for (position, props) in injections {
352 let point = position.to_point(buffer);
353 edits.push(Edit {
354 old: point..point,
355 new: point..point,
356 });
357
358 let id = InjectionId(post_inc(&mut self.0.next_injection_id));
359 injection_ids.push(id);
360 new_sites.push_tree(
361 cursor.slice(
362 &InjectionSitePosition(position.clone()),
363 Bias::Right,
364 buffer,
365 ),
366 buffer,
367 );
368 new_sites.push(
369 InjectionSite {
370 injection_id: id,
371 position,
372 disposition: props.disposition,
373 },
374 buffer,
375 );
376 self.0.injections.push(
377 Injection {
378 id,
379 text: props.text,
380 runs: props.runs,
381 },
382 &(),
383 );
384 }
385 new_sites.push_tree(cursor.suffix(buffer), buffer);
386
387 drop(cursor);
388 self.0.injection_sites = new_sites;
389
390 let edits = self.0.apply_edits(edits, cx);
391 let snapshot = Snapshot {
392 transforms: self.0.transforms.lock().clone(),
393 injections: self.0.injections.clone(),
394 buffer_snapshot: buffer.snapshot(),
395 version: self.0.version.load(SeqCst),
396 };
397
398 (injection_ids, snapshot, edits)
399 }
400}
401
402impl sum_tree::Item for Injection {
403 type Summary = InjectionId;
404
405 fn summary(&self) -> Self::Summary {
406 self.id
407 }
408}
409
410impl sum_tree::KeyedItem for Injection {
411 type Key = InjectionId;
412
413 fn key(&self) -> Self::Key {
414 self.id
415 }
416}
417
418impl sum_tree::Item for InjectionSite {
419 type Summary = InjectionSiteSummary;
420
421 fn summary(&self) -> Self::Summary {
422 InjectionSiteSummary {
423 min_injection_id: self.injection_id,
424 max_injection_id: self.injection_id,
425 min_position: self.position.clone(),
426 max_position: self.position.clone(),
427 }
428 }
429}
430
431impl Default for InjectionSitePosition {
432 fn default() -> Self {
433 Self(Anchor::min())
434 }
435}
436
437impl sum_tree::Summary for InjectionSiteSummary {
438 type Context = buffer::Buffer;
439
440 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
441 self.min_injection_id = cmp::min(self.min_injection_id, summary.min_injection_id);
442 self.max_injection_id = cmp::max(self.max_injection_id, summary.max_injection_id);
443 self.max_position = summary.max_position.clone();
444 }
445}
446
447impl<'a> sum_tree::Dimension<'a, InjectionSiteSummary> for InjectionSitePosition {
448 fn add_summary(&mut self, summary: &'a InjectionSiteSummary, _: &buffer::Buffer) {
449 self.0 = summary.max_position.clone();
450 }
451}
452
453impl<'a> sum_tree::SeekTarget<'a, InjectionSiteSummary, Self> for InjectionSitePosition {
454 fn cmp(&self, cursor_location: &Self, snapshot: &buffer::Buffer) -> Ordering {
455 self.0.cmp(&cursor_location.0, snapshot).unwrap()
456 }
457}
458
459impl Default for InjectionSiteSummary {
460 fn default() -> Self {
461 Self {
462 min_injection_id: InjectionId(usize::MAX),
463 max_injection_id: InjectionId(0),
464 min_position: Anchor::max(),
465 max_position: Anchor::min(),
466 }
467 }
468}
469
470impl Transform {
471 fn isomorphic(text_summary: TextSummary) -> Self {
472 Self {
473 input: text_summary.clone(),
474 output: text_summary,
475 injection_id: None,
476 }
477 }
478
479 fn for_injection(injection: &Injection) -> Self {
480 Self {
481 input: Default::default(),
482 output: injection.text.summary(),
483 injection_id: Some(injection.id),
484 }
485 }
486}
487
488impl sum_tree::Item for Transform {
489 type Summary = TransformSummary;
490
491 fn summary(&self) -> Self::Summary {
492 let min_injection_id;
493 let max_injection_id;
494 if let Some(id) = self.injection_id {
495 min_injection_id = id;
496 max_injection_id = id;
497 } else {
498 min_injection_id = InjectionId(usize::MAX);
499 max_injection_id = InjectionId(0);
500 }
501
502 TransformSummary {
503 input: self.input.clone(),
504 output: self.output.clone(),
505 min_injection_id,
506 max_injection_id,
507 }
508 }
509}
510
511impl sum_tree::Summary for TransformSummary {
512 type Context = ();
513
514 fn add_summary(&mut self, other: &Self, _: &()) {
515 self.input += &other.input;
516 self.output += &other.output;
517 }
518}
519
520impl<'a> sum_tree::Dimension<'a, TransformSummary> for usize {
521 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
522 *self += summary.input.bytes
523 }
524}
525
526impl<'a> sum_tree::Dimension<'a, TransformSummary> for Point {
527 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
528 *self += summary.input.lines
529 }
530}
531
532impl<'a> sum_tree::Dimension<'a, TransformSummary> for InjectionOffset {
533 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
534 self.0 += summary.output.bytes
535 }
536}
537
538#[cfg(test)]
539mod tests {
540 use std::env;
541
542 use super::*;
543 use buffer::RandomCharIter;
544 use rand::prelude::*;
545
546 #[gpui::test(iterations = 1000)]
547 fn test_random(cx: &mut gpui::MutableAppContext, mut rng: StdRng) {
548 let operations = env::var("OPERATIONS")
549 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
550 .unwrap_or(1);
551
552 let buffer = cx.add_model(|cx| {
553 let len = rng.gen_range(0..10);
554 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
555 Buffer::new(0, text, cx)
556 });
557 let (map, initial_snapshot) = InjectionMap::new(buffer.clone(), cx.as_ref());
558 assert_eq!(
559 initial_snapshot.transforms.summary().input,
560 buffer.read(cx).text_summary()
561 );
562
563 for _ in 0..operations {
564 log::info!("text: {:?}", buffer.read(cx).text());
565 match rng.gen_range(0..=100) {
566 _ => {
567 let edits = buffer.update(cx, |buffer, _| {
568 let start_version = buffer.version.clone();
569 let edit_count = rng.gen_range(1..=5);
570 buffer.randomly_edit(&mut rng, edit_count);
571 buffer
572 .edits_since::<Point>(&start_version)
573 .collect::<Vec<_>>()
574 });
575 log::info!("editing {:?}", edits);
576 }
577 }
578
579 let (snapshot, edits) = map.read(cx.as_ref());
580 assert_eq!(
581 snapshot.transforms.summary().input,
582 buffer.read(cx).text_summary()
583 );
584 }
585 }
586}