1use crate::{
2 Grammar, InjectionConfig, Language, LanguageRegistry, QueryCursorHandle, TextProvider,
3 ToTreeSitterPoint,
4};
5use std::{
6 borrow::Cow,
7 cell::RefCell,
8 cmp::{Ordering, Reverse},
9 collections::BinaryHeap,
10 iter::Peekable,
11 ops::{DerefMut, Range},
12 sync::Arc,
13};
14use sum_tree::{Bias, SeekTarget, SumTree};
15use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point, Rope, ToOffset, ToPoint};
16use tree_sitter::{
17 Node, Parser, Query, QueryCapture, QueryCaptures, QueryCursor, QueryMatch, QueryMatches, Tree,
18};
19
20thread_local! {
21 static PARSER: RefCell<Parser> = RefCell::new(Parser::new());
22}
23
24#[derive(Default)]
25pub struct SyntaxMap {
26 parsed_version: clock::Global,
27 interpolated_version: clock::Global,
28 snapshot: SyntaxSnapshot,
29 language_registry: Option<Arc<LanguageRegistry>>,
30}
31
32#[derive(Clone, Default)]
33pub struct SyntaxSnapshot {
34 layers: SumTree<SyntaxLayer>,
35}
36
37pub struct SyntaxMapCaptures<'a> {
38 layers: Vec<SyntaxMapCapturesLayer<'a>>,
39}
40
41pub struct SyntaxMapMatches<'a> {
42 layers: Vec<SyntaxMapMatchesLayer<'a>>,
43}
44
45pub struct SyntaxMapCapture<'a> {
46 pub grammar: &'a Grammar,
47 pub depth: usize,
48 pub node: Node<'a>,
49 pub index: u32,
50}
51
52pub struct SyntaxMapMatch<'a> {
53 pub grammar: &'a Grammar,
54 pub depth: usize,
55 pub pattern_index: usize,
56 pub captures: &'a [QueryCapture<'a>],
57}
58
59struct SyntaxMapCapturesLayer<'a> {
60 depth: usize,
61 captures: Peekable<QueryCaptures<'a, 'a, TextProvider<'a>>>,
62 grammar: &'a Grammar,
63 _query_cursor: QueryCursorHandle,
64}
65
66struct SyntaxMapMatchesLayer<'a> {
67 depth: usize,
68 matches: Peekable<QueryMatches<'a, 'a, TextProvider<'a>>>,
69 grammar: &'a Grammar,
70 _query_cursor: QueryCursorHandle,
71}
72
73#[derive(Clone)]
74struct SyntaxLayer {
75 depth: usize,
76 range: Range<Anchor>,
77 tree: tree_sitter::Tree,
78 language: Arc<Language>,
79}
80
81#[derive(Debug, Clone)]
82struct SyntaxLayerSummary {
83 max_depth: usize,
84 range: Range<Anchor>,
85 last_layer_range: Range<Anchor>,
86}
87
88#[derive(Clone, Debug)]
89struct DepthAndRange(usize, Range<Anchor>);
90
91#[derive(Clone, Debug)]
92struct DepthAndMaxPosition(usize, Anchor);
93
94#[derive(Clone, Debug)]
95struct DepthAndRangeOrMaxPosition(DepthAndRange, DepthAndMaxPosition);
96
97struct ReparseStep {
98 depth: usize,
99 language: Arc<Language>,
100 ranges: Vec<tree_sitter::Range>,
101 range: Range<Anchor>,
102}
103
104#[derive(Debug, PartialEq, Eq)]
105struct ChangedRegion {
106 depth: usize,
107 range: Range<Anchor>,
108}
109
110#[derive(Default)]
111struct ChangeRegionSet(Vec<ChangedRegion>);
112
113impl SyntaxMap {
114 pub fn new() -> Self {
115 Self::default()
116 }
117
118 pub fn set_language_registry(&mut self, registry: Arc<LanguageRegistry>) {
119 self.language_registry = Some(registry);
120 }
121
122 pub fn snapshot(&self) -> SyntaxSnapshot {
123 self.snapshot.clone()
124 }
125
126 pub fn interpolate(&mut self, text: &BufferSnapshot) {
127 self.snapshot.interpolate(&self.interpolated_version, text);
128 self.interpolated_version = text.version.clone();
129 }
130
131 pub fn reparse(&mut self, language: Arc<Language>, text: &BufferSnapshot) {
132 if !self.interpolated_version.observed_all(&text.version) {
133 self.interpolate(text);
134 }
135
136 self.snapshot.reparse(
137 &self.parsed_version,
138 text,
139 self.language_registry.clone(),
140 language,
141 );
142 self.parsed_version = text.version.clone();
143 }
144}
145
146impl SyntaxSnapshot {
147 pub fn interpolate(&mut self, from_version: &clock::Global, text: &BufferSnapshot) {
148 let edits = text
149 .edits_since::<(usize, Point)>(&from_version)
150 .collect::<Vec<_>>();
151 if edits.is_empty() {
152 return;
153 }
154
155 let mut layers = SumTree::new();
156 let mut edits_for_depth = &edits[..];
157 let mut cursor = self.layers.cursor::<SyntaxLayerSummary>();
158 cursor.next(text);
159
160 'outer: loop {
161 let depth = cursor.end(text).max_depth;
162
163 // Preserve any layers at this depth that precede the first edit.
164 if let Some(first_edit) = edits_for_depth.first() {
165 let target = DepthAndMaxPosition(depth, text.anchor_before(first_edit.new.start.0));
166 if target.cmp(&cursor.start(), text).is_gt() {
167 let slice = cursor.slice(&target, Bias::Left, text);
168 layers.push_tree(slice, text);
169 }
170 }
171 // If this layer follows all of the edits, then preserve it and any
172 // subsequent layers at this same depth.
173 else {
174 let slice = cursor.slice(
175 &DepthAndRange(depth + 1, Anchor::MIN..Anchor::MAX),
176 Bias::Left,
177 text,
178 );
179 layers.push_tree(slice, text);
180 edits_for_depth = &edits[..];
181 continue;
182 };
183
184 let layer = if let Some(layer) = cursor.item() {
185 layer
186 } else {
187 break;
188 };
189
190 let mut endpoints = text
191 .summaries_for_anchors::<(usize, Point), _>([&layer.range.start, &layer.range.end]);
192 let layer_range = endpoints.next().unwrap()..endpoints.next().unwrap();
193 let start_byte = layer_range.start.0;
194 let start_point = layer_range.start.1;
195 let end_byte = layer_range.end.0;
196
197 // Ignore edits that end before the start of this layer, and don't consider them
198 // for any subsequent layers at this same depth.
199 loop {
200 if let Some(edit) = edits_for_depth.first() {
201 if edit.new.end.0 < start_byte {
202 edits_for_depth = &edits_for_depth[1..];
203 } else {
204 break;
205 }
206 } else {
207 continue 'outer;
208 }
209 }
210
211 let mut layer = layer.clone();
212 for edit in edits_for_depth {
213 // Ignore any edits that follow this layer.
214 if edit.new.start.0 > end_byte {
215 break;
216 }
217
218 // Apply any edits that intersect this layer to the layer's syntax tree.
219 let tree_edit = if edit.new.start.0 >= start_byte {
220 tree_sitter::InputEdit {
221 start_byte: edit.new.start.0 - start_byte,
222 old_end_byte: edit.new.start.0 - start_byte
223 + (edit.old.end.0 - edit.old.start.0),
224 new_end_byte: edit.new.end.0 - start_byte,
225 start_position: (edit.new.start.1 - start_point).to_ts_point(),
226 old_end_position: (edit.new.start.1 - start_point
227 + (edit.old.end.1 - edit.old.start.1))
228 .to_ts_point(),
229 new_end_position: (edit.new.end.1 - start_point).to_ts_point(),
230 }
231 } else {
232 tree_sitter::InputEdit {
233 start_byte: 0,
234 old_end_byte: edit.new.end.0 - start_byte,
235 new_end_byte: 0,
236 start_position: Default::default(),
237 old_end_position: (edit.new.end.1 - start_point).to_ts_point(),
238 new_end_position: Default::default(),
239 }
240 };
241
242 layer.tree.edit(&tree_edit);
243 if edit.new.start.0 < start_byte {
244 break;
245 }
246 }
247
248 layers.push(layer, text);
249 cursor.next(text);
250 }
251
252 layers.push_tree(cursor.suffix(&text), &text);
253 drop(cursor);
254 self.layers = layers;
255 }
256
257 pub fn reparse(
258 &mut self,
259 from_version: &clock::Global,
260 text: &BufferSnapshot,
261 registry: Option<Arc<LanguageRegistry>>,
262 language: Arc<Language>,
263 ) {
264 let edits = text.edits_since::<usize>(from_version).collect::<Vec<_>>();
265 if edits.is_empty() {
266 return;
267 }
268
269 let max_depth = self.layers.summary().max_depth;
270 let mut cursor = self.layers.cursor::<SyntaxLayerSummary>();
271 cursor.next(&text);
272 let mut layers = SumTree::new();
273
274 let mut changed_regions = ChangeRegionSet::default();
275 let mut queue = BinaryHeap::new();
276 queue.push(ReparseStep {
277 depth: 0,
278 language: language.clone(),
279 ranges: Vec::new(),
280 range: Anchor::MIN..Anchor::MAX,
281 });
282
283 loop {
284 let step = queue.pop();
285 let (depth, range) = if let Some(step) = &step {
286 (step.depth, step.range.clone())
287 } else {
288 (max_depth + 1, Anchor::MAX..Anchor::MAX)
289 };
290
291 let target = DepthAndRange(depth, range.clone());
292 let mut done = cursor.item().is_none();
293 while !done && target.cmp(&cursor.end(text), &text).is_gt() {
294 done = true;
295
296 let bounded_target =
297 DepthAndRangeOrMaxPosition(target.clone(), changed_regions.start_position());
298 if bounded_target.cmp(&cursor.start(), &text).is_gt() {
299 let slice = cursor.slice(&bounded_target, Bias::Left, text);
300 if !slice.is_empty() {
301 layers.push_tree(slice, &text);
302 if changed_regions.prune(cursor.end(text), text) {
303 done = false;
304 }
305 }
306 }
307
308 while target.cmp(&cursor.end(text), text).is_gt() {
309 let layer = if let Some(layer) = cursor.item() {
310 layer
311 } else {
312 break;
313 };
314
315 if changed_regions.intersects(&layer, text) {
316 changed_regions.insert(
317 ChangedRegion {
318 depth: depth + 1,
319 range: layer.range.clone(),
320 },
321 text,
322 );
323 } else {
324 layers.push(layer.clone(), text);
325 }
326
327 cursor.next(text);
328 if changed_regions.prune(cursor.end(text), text) {
329 done = false;
330 }
331 }
332 }
333
334 let (ranges, language) = if let Some(step) = step {
335 (step.ranges, step.language)
336 } else {
337 break;
338 };
339
340 let start_point;
341 let start_byte;
342 let end_byte;
343 if let Some((first, last)) = ranges.first().zip(ranges.last()) {
344 start_point = first.start_point;
345 start_byte = first.start_byte;
346 end_byte = last.end_byte;
347 } else {
348 start_point = Point::zero().to_ts_point();
349 start_byte = 0;
350 end_byte = text.len();
351 };
352
353 let mut old_layer = cursor.item();
354 if let Some(layer) = old_layer {
355 if layer.range.to_offset(text) == (start_byte..end_byte) {
356 cursor.next(&text);
357 } else {
358 old_layer = None;
359 }
360 }
361
362 let grammar = if let Some(grammar) = language.grammar.as_deref() {
363 grammar
364 } else {
365 continue;
366 };
367
368 let tree;
369 let changed_ranges;
370 if let Some(old_layer) = old_layer {
371 tree = parse_text(
372 grammar,
373 text.as_rope(),
374 Some(old_layer.tree.clone()),
375 ranges,
376 );
377 changed_ranges = join_ranges(
378 edits
379 .iter()
380 .map(|e| e.new.clone())
381 .filter(|range| range.start < end_byte && range.end > start_byte),
382 old_layer
383 .tree
384 .changed_ranges(&tree)
385 .map(|r| start_byte + r.start_byte..start_byte + r.end_byte),
386 );
387 } else {
388 tree = parse_text(grammar, text.as_rope(), None, ranges);
389 changed_ranges = vec![start_byte..end_byte];
390 }
391
392 layers.push(
393 SyntaxLayer {
394 depth,
395 range,
396 tree: tree.clone(),
397 language: language.clone(),
398 },
399 &text,
400 );
401
402 if let (Some((config, registry)), false) = (
403 grammar.injection_config.as_ref().zip(registry.as_ref()),
404 changed_ranges.is_empty(),
405 ) {
406 let depth = depth + 1;
407 for range in &changed_ranges {
408 changed_regions.insert(
409 ChangedRegion {
410 depth,
411 range: text.anchor_before(range.start)..text.anchor_after(range.end),
412 },
413 text,
414 );
415 }
416 get_injections(
417 config,
418 text,
419 tree.root_node_with_offset(start_byte, start_point),
420 registry,
421 depth,
422 &changed_ranges,
423 &mut queue,
424 );
425 }
426 }
427
428 drop(cursor);
429 self.layers = layers;
430 }
431
432 pub fn captures<'a>(
433 &'a self,
434 range: Range<usize>,
435 buffer: &'a BufferSnapshot,
436 query: impl Fn(&Grammar) -> Option<&Query>,
437 ) -> SyntaxMapCaptures {
438 let mut result = SyntaxMapCaptures { layers: Vec::new() };
439 for (grammar, depth, node) in self.layers_for_range(range.clone(), buffer) {
440 let query = if let Some(query) = query(grammar) {
441 query
442 } else {
443 continue;
444 };
445
446 let mut query_cursor = QueryCursorHandle::new();
447
448 // TODO - add a Tree-sitter API to remove the need for this.
449 let cursor = unsafe {
450 std::mem::transmute::<_, &'static mut QueryCursor>(query_cursor.deref_mut())
451 };
452
453 cursor.set_byte_range(range.clone());
454 let captures = cursor.captures(query, node, TextProvider(buffer.as_rope()));
455 let mut layer = SyntaxMapCapturesLayer {
456 depth,
457 grammar,
458 captures: captures.peekable(),
459 _query_cursor: query_cursor,
460 };
461
462 if let Some(key) = layer.sort_key() {
463 let mut ix = 0;
464 while let Some(next_layer) = result.layers.get_mut(ix) {
465 if let Some(next_key) = next_layer.sort_key() {
466 if key > next_key {
467 ix += 1;
468 continue;
469 }
470 }
471 break;
472 }
473 result.layers.insert(ix, layer);
474 }
475 }
476 result
477 }
478
479 pub fn matches<'a>(
480 &'a self,
481 range: Range<usize>,
482 buffer: &'a BufferSnapshot,
483 query: impl Fn(&Grammar) -> Option<&Query>,
484 ) -> SyntaxMapMatches {
485 let mut result = SyntaxMapMatches { layers: Vec::new() };
486 for (grammar, depth, node) in self.layers_for_range(range.clone(), buffer) {
487 let query = if let Some(query) = query(grammar) {
488 query
489 } else {
490 continue;
491 };
492
493 let mut query_cursor = QueryCursorHandle::new();
494
495 // TODO - add a Tree-sitter API to remove the need for this.
496 let cursor = unsafe {
497 std::mem::transmute::<_, &'static mut QueryCursor>(query_cursor.deref_mut())
498 };
499
500 cursor.set_byte_range(range.clone());
501 let matches = cursor.matches(query, node, TextProvider(buffer.as_rope()));
502 let mut layer = SyntaxMapMatchesLayer {
503 depth,
504 grammar,
505 matches: matches.peekable(),
506 _query_cursor: query_cursor,
507 };
508
509 if let Some(key) = layer.sort_key() {
510 let mut ix = 0;
511 while let Some(next_layer) = result.layers.get_mut(ix) {
512 if let Some(next_key) = next_layer.sort_key() {
513 if key > next_key {
514 ix += 1;
515 continue;
516 }
517 }
518 break;
519 }
520 result.layers.insert(ix, layer);
521 }
522 }
523 result
524 }
525
526 pub fn layers(&self, buffer: &BufferSnapshot) -> Vec<(&Grammar, Node)> {
527 self.layers
528 .iter()
529 .filter_map(|layer| {
530 if let Some(grammar) = &layer.language.grammar {
531 Some((
532 grammar.as_ref(),
533 layer.tree.root_node_with_offset(
534 layer.range.start.to_offset(buffer),
535 layer.range.start.to_point(buffer).to_ts_point(),
536 ),
537 ))
538 } else {
539 None
540 }
541 })
542 .collect()
543 }
544
545 pub fn layers_for_range<'a, T: ToOffset>(
546 &self,
547 range: Range<T>,
548 buffer: &BufferSnapshot,
549 ) -> Vec<(&Grammar, usize, Node)> {
550 let start = buffer.anchor_before(range.start.to_offset(buffer));
551 let end = buffer.anchor_after(range.end.to_offset(buffer));
552
553 let mut cursor = self.layers.filter::<_, ()>(|summary| {
554 let is_before_start = summary.range.end.cmp(&start, buffer).is_lt();
555 let is_after_end = summary.range.start.cmp(&end, buffer).is_gt();
556 !is_before_start && !is_after_end
557 });
558
559 let mut result = Vec::new();
560 cursor.next(buffer);
561 while let Some(layer) = cursor.item() {
562 if let Some(grammar) = &layer.language.grammar {
563 result.push((
564 grammar.as_ref(),
565 layer.depth,
566 layer.tree.root_node_with_offset(
567 layer.range.start.to_offset(buffer),
568 layer.range.start.to_point(buffer).to_ts_point(),
569 ),
570 ));
571 }
572 cursor.next(buffer)
573 }
574
575 result
576 }
577}
578
579impl<'a> Iterator for SyntaxMapCaptures<'a> {
580 type Item = SyntaxMapCapture<'a>;
581
582 fn next(&mut self) -> Option<Self::Item> {
583 let layer = self.layers.first_mut()?;
584 let (mat, ix) = layer.captures.next()?;
585
586 let capture = mat.captures[ix as usize];
587 let grammar = layer.grammar;
588 let depth = layer.depth;
589
590 if let Some(key) = layer.sort_key() {
591 let mut i = 1;
592 while let Some(later_layer) = self.layers.get_mut(i) {
593 if let Some(later_key) = later_layer.sort_key() {
594 if key > later_key {
595 i += 1;
596 continue;
597 }
598 }
599 break;
600 }
601 if i > 1 {
602 self.layers[0..i].rotate_left(1);
603 }
604 } else {
605 self.layers.remove(0);
606 }
607
608 Some(SyntaxMapCapture {
609 grammar,
610 depth,
611 node: capture.node,
612 index: capture.index,
613 })
614 }
615}
616
617impl<'a> SyntaxMapCapturesLayer<'a> {
618 fn sort_key(&mut self) -> Option<(usize, Reverse<usize>, usize)> {
619 let (mat, ix) = self.captures.peek()?;
620 let range = &mat.captures[*ix].node.byte_range();
621 Some((range.start, Reverse(range.end), self.depth))
622 }
623}
624
625impl<'a> SyntaxMapMatchesLayer<'a> {
626 fn sort_key(&mut self) -> Option<(usize, Reverse<usize>, usize)> {
627 let mat = self.matches.peek()?;
628 let range = mat.captures.first()?.node.start_byte()..mat.captures.last()?.node.end_byte();
629 Some((range.start, Reverse(range.end), self.depth))
630 }
631}
632
633fn join_ranges(
634 a: impl Iterator<Item = Range<usize>>,
635 b: impl Iterator<Item = Range<usize>>,
636) -> Vec<Range<usize>> {
637 let mut result = Vec::<Range<usize>>::new();
638 let mut a = a.peekable();
639 let mut b = b.peekable();
640 loop {
641 let range = match (a.peek(), b.peek()) {
642 (Some(range_a), Some(range_b)) => {
643 if range_a.start < range_b.start {
644 a.next().unwrap()
645 } else {
646 b.next().unwrap()
647 }
648 }
649 (None, Some(_)) => b.next().unwrap(),
650 (Some(_), None) => a.next().unwrap(),
651 (None, None) => break,
652 };
653
654 if let Some(last) = result.last_mut() {
655 if range.start <= last.end {
656 last.end = last.end.max(range.end);
657 continue;
658 }
659 }
660 result.push(range);
661 }
662 result
663}
664
665fn parse_text(
666 grammar: &Grammar,
667 text: &Rope,
668 old_tree: Option<Tree>,
669 mut ranges: Vec<tree_sitter::Range>,
670) -> Tree {
671 let (start_byte, start_point) = ranges
672 .first()
673 .map(|range| (range.start_byte, Point::from_ts_point(range.start_point)))
674 .unwrap_or_default();
675
676 for range in &mut ranges {
677 range.start_byte -= start_byte;
678 range.end_byte -= start_byte;
679 range.start_point = (Point::from_ts_point(range.start_point) - start_point).to_ts_point();
680 range.end_point = (Point::from_ts_point(range.end_point) - start_point).to_ts_point();
681 }
682
683 PARSER.with(|parser| {
684 let mut parser = parser.borrow_mut();
685 let mut chunks = text.chunks_in_range(start_byte..text.len());
686 parser
687 .set_included_ranges(&ranges)
688 .expect("overlapping ranges");
689 parser
690 .set_language(grammar.ts_language)
691 .expect("incompatible grammar");
692 parser
693 .parse_with(
694 &mut move |offset, _| {
695 chunks.seek(start_byte + offset);
696 chunks.next().unwrap_or("").as_bytes()
697 },
698 old_tree.as_ref(),
699 )
700 .expect("invalid language")
701 })
702}
703
704fn get_injections(
705 config: &InjectionConfig,
706 text: &BufferSnapshot,
707 node: Node,
708 language_registry: &LanguageRegistry,
709 depth: usize,
710 query_ranges: &[Range<usize>],
711 queue: &mut BinaryHeap<ReparseStep>,
712) -> bool {
713 let mut result = false;
714 let mut query_cursor = QueryCursorHandle::new();
715 let mut prev_match = None;
716 for query_range in query_ranges {
717 query_cursor.set_byte_range(query_range.start..query_range.end);
718 for mat in query_cursor.matches(&config.query, node, TextProvider(text.as_rope())) {
719 let content_ranges = mat
720 .nodes_for_capture_index(config.content_capture_ix)
721 .map(|node| node.range())
722 .collect::<Vec<_>>();
723 if content_ranges.is_empty() {
724 continue;
725 }
726
727 // Avoid duplicate matches if two changed ranges intersect the same injection.
728 let content_range =
729 content_ranges.first().unwrap().start_byte..content_ranges.last().unwrap().end_byte;
730 if let Some((last_pattern_ix, last_range)) = &prev_match {
731 if mat.pattern_index == *last_pattern_ix && content_range == *last_range {
732 continue;
733 }
734 }
735 prev_match = Some((mat.pattern_index, content_range.clone()));
736
737 let language_name = config.languages_by_pattern_ix[mat.pattern_index]
738 .as_ref()
739 .map(|s| Cow::Borrowed(s.as_ref()))
740 .or_else(|| {
741 let ix = config.language_capture_ix?;
742 let node = mat.nodes_for_capture_index(ix).next()?;
743 Some(Cow::Owned(text.text_for_range(node.byte_range()).collect()))
744 });
745
746 if let Some(language_name) = language_name {
747 if let Some(language) = language_registry.get_language(language_name.as_ref()) {
748 result = true;
749 let range = text.anchor_before(content_range.start)
750 ..text.anchor_after(content_range.end);
751 queue.push(ReparseStep {
752 depth,
753 language,
754 ranges: content_ranges,
755 range,
756 })
757 }
758 }
759 }
760 }
761 result
762}
763
764impl std::ops::Deref for SyntaxMap {
765 type Target = SyntaxSnapshot;
766
767 fn deref(&self) -> &Self::Target {
768 &self.snapshot
769 }
770}
771
772impl PartialEq for ReparseStep {
773 fn eq(&self, _: &Self) -> bool {
774 false
775 }
776}
777
778impl Eq for ReparseStep {}
779
780impl PartialOrd for ReparseStep {
781 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
782 Some(self.cmp(&other))
783 }
784}
785
786impl Ord for ReparseStep {
787 fn cmp(&self, other: &Self) -> Ordering {
788 let range_a = self.range();
789 let range_b = other.range();
790 Ord::cmp(&other.depth, &self.depth)
791 .then_with(|| Ord::cmp(&range_b.start, &range_a.start))
792 .then_with(|| Ord::cmp(&range_a.end, &range_b.end))
793 }
794}
795
796impl ReparseStep {
797 fn range(&self) -> Range<usize> {
798 let start = self.ranges.first().map_or(0, |r| r.start_byte);
799 let end = self.ranges.last().map_or(0, |r| r.end_byte);
800 start..end
801 }
802}
803
804impl ChangedRegion {
805 fn cmp(&self, other: &Self, buffer: &BufferSnapshot) -> Ordering {
806 let range_a = &self.range;
807 let range_b = &other.range;
808 Ord::cmp(&self.depth, &other.depth)
809 .then_with(|| range_a.start.cmp(&range_b.start, buffer))
810 .then_with(|| range_b.end.cmp(&range_a.end, buffer))
811 }
812}
813
814impl ChangeRegionSet {
815 fn start_position(&self) -> DepthAndMaxPosition {
816 self.0
817 .first()
818 .map_or(DepthAndMaxPosition(usize::MAX, Anchor::MAX), |region| {
819 DepthAndMaxPosition(region.depth, region.range.start)
820 })
821 }
822
823 fn intersects(&self, layer: &SyntaxLayer, text: &BufferSnapshot) -> bool {
824 for region in &self.0 {
825 if region.depth < layer.depth {
826 continue;
827 }
828 if region.depth > layer.depth {
829 break;
830 }
831 if region.range.end.cmp(&layer.range.start, text).is_le() {
832 continue;
833 }
834 if region.range.start.cmp(&layer.range.end, text).is_ge() {
835 break;
836 }
837 return true;
838 }
839 false
840 }
841
842 fn insert(&mut self, region: ChangedRegion, text: &BufferSnapshot) {
843 if let Err(ix) = self.0.binary_search_by(|probe| probe.cmp(®ion, text)) {
844 self.0.insert(ix, region);
845 }
846 }
847
848 fn prune(&mut self, summary: SyntaxLayerSummary, text: &BufferSnapshot) -> bool {
849 let prev_len = self.0.len();
850 self.0.retain(|region| {
851 region.depth > summary.max_depth
852 || (region.depth == summary.max_depth
853 && region
854 .range
855 .end
856 .cmp(&summary.last_layer_range.start, text)
857 .is_gt())
858 });
859 self.0.len() < prev_len
860 }
861}
862
863impl Default for SyntaxLayerSummary {
864 fn default() -> Self {
865 Self {
866 max_depth: 0,
867 range: Anchor::MAX..Anchor::MIN,
868 last_layer_range: Anchor::MIN..Anchor::MAX,
869 }
870 }
871}
872
873impl sum_tree::Summary for SyntaxLayerSummary {
874 type Context = BufferSnapshot;
875
876 fn add_summary(&mut self, other: &Self, buffer: &Self::Context) {
877 if other.max_depth > self.max_depth {
878 *self = other.clone();
879 } else {
880 if other.range.start.cmp(&self.range.start, buffer).is_lt() {
881 self.range.start = other.range.start;
882 }
883 if other.range.end.cmp(&self.range.end, buffer).is_gt() {
884 self.range.end = other.range.end;
885 }
886 self.last_layer_range = other.last_layer_range.clone();
887 }
888 }
889}
890
891impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary> for DepthAndRange {
892 fn cmp(&self, cursor_location: &SyntaxLayerSummary, buffer: &BufferSnapshot) -> Ordering {
893 Ord::cmp(&self.0, &cursor_location.max_depth)
894 .then_with(|| {
895 self.1
896 .start
897 .cmp(&cursor_location.last_layer_range.start, buffer)
898 })
899 .then_with(|| {
900 cursor_location
901 .last_layer_range
902 .end
903 .cmp(&self.1.end, buffer)
904 })
905 }
906}
907
908impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary> for DepthAndMaxPosition {
909 fn cmp(&self, cursor_location: &SyntaxLayerSummary, text: &BufferSnapshot) -> Ordering {
910 Ord::cmp(&self.0, &cursor_location.max_depth)
911 .then_with(|| self.1.cmp(&cursor_location.range.end, text))
912 }
913}
914
915impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary> for DepthAndRangeOrMaxPosition {
916 fn cmp(&self, cursor_location: &SyntaxLayerSummary, buffer: &BufferSnapshot) -> Ordering {
917 if self.1.cmp(cursor_location, buffer).is_le() {
918 return Ordering::Less;
919 } else {
920 self.0.cmp(cursor_location, buffer)
921 }
922 }
923}
924
925impl sum_tree::Item for SyntaxLayer {
926 type Summary = SyntaxLayerSummary;
927
928 fn summary(&self) -> Self::Summary {
929 SyntaxLayerSummary {
930 max_depth: self.depth,
931 range: self.range.clone(),
932 last_layer_range: self.range.clone(),
933 }
934 }
935}
936
937impl std::fmt::Debug for SyntaxLayer {
938 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
939 f.debug_struct("SyntaxLayer")
940 .field("depth", &self.depth)
941 .field("range", &self.range)
942 .field("tree", &self.tree)
943 .finish()
944 }
945}
946
947#[cfg(test)]
948mod tests {
949 use super::*;
950 use crate::LanguageConfig;
951 use text::{Buffer, Point};
952 use tree_sitter::Query;
953 use unindent::Unindent as _;
954 use util::test::marked_text_ranges;
955
956 #[gpui::test]
957 fn test_syntax_map_layers_for_range() {
958 let registry = Arc::new(LanguageRegistry::test());
959 let language = Arc::new(rust_lang());
960 registry.add(language.clone());
961
962 let mut buffer = Buffer::new(
963 0,
964 0,
965 r#"
966 fn a() {
967 assert_eq!(
968 b(vec![C {}]),
969 vec![d.e],
970 );
971 println!("{}", f(|_| true));
972 }
973 "#
974 .unindent(),
975 );
976
977 let mut syntax_map = SyntaxMap::new();
978 syntax_map.set_language_registry(registry.clone());
979 syntax_map.reparse(language.clone(), &buffer);
980
981 assert_layers_for_range(
982 &syntax_map,
983 &buffer,
984 Point::new(2, 0)..Point::new(2, 0),
985 &[
986 "...(function_item ... (block (expression_statement (macro_invocation...",
987 "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
988 ],
989 );
990 assert_layers_for_range(
991 &syntax_map,
992 &buffer,
993 Point::new(2, 14)..Point::new(2, 16),
994 &[
995 "...(function_item ...",
996 "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
997 "...(array_expression (struct_expression ...",
998 ],
999 );
1000 assert_layers_for_range(
1001 &syntax_map,
1002 &buffer,
1003 Point::new(3, 14)..Point::new(3, 16),
1004 &[
1005 "...(function_item ...",
1006 "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
1007 "...(array_expression (field_expression ...",
1008 ],
1009 );
1010 assert_layers_for_range(
1011 &syntax_map,
1012 &buffer,
1013 Point::new(5, 12)..Point::new(5, 16),
1014 &[
1015 "...(function_item ...",
1016 "...(call_expression ... (arguments (closure_expression ...",
1017 ],
1018 );
1019
1020 // Replace a vec! macro invocation with a plain slice, removing a syntactic layer.
1021 let macro_name_range = range_for_text(&buffer, "vec!");
1022 buffer.edit([(macro_name_range, "&")]);
1023 syntax_map.interpolate(&buffer);
1024 syntax_map.reparse(language.clone(), &buffer);
1025
1026 assert_layers_for_range(
1027 &syntax_map,
1028 &buffer,
1029 Point::new(2, 14)..Point::new(2, 16),
1030 &[
1031 "...(function_item ...",
1032 "...(tuple_expression (call_expression ... arguments: (arguments (reference_expression value: (array_expression...",
1033 ],
1034 );
1035
1036 // Put the vec! macro back, adding back the syntactic layer.
1037 buffer.undo();
1038 syntax_map.interpolate(&buffer);
1039 syntax_map.reparse(language.clone(), &buffer);
1040
1041 assert_layers_for_range(
1042 &syntax_map,
1043 &buffer,
1044 Point::new(2, 14)..Point::new(2, 16),
1045 &[
1046 "...(function_item ...",
1047 "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
1048 "...(array_expression (struct_expression ...",
1049 ],
1050 );
1051 }
1052
1053 #[gpui::test]
1054 fn test_typing_multiple_new_injections() {
1055 let (buffer, syntax_map) = test_edit_sequence(&[
1056 "fn a() { dbg }",
1057 "fn a() { dbg«!» }",
1058 "fn a() { dbg!«()» }",
1059 "fn a() { dbg!(«b») }",
1060 "fn a() { dbg!(b«.») }",
1061 "fn a() { dbg!(b.«c») }",
1062 "fn a() { dbg!(b.c«()») }",
1063 "fn a() { dbg!(b.c(«vec»)) }",
1064 "fn a() { dbg!(b.c(vec«!»)) }",
1065 "fn a() { dbg!(b.c(vec!«[]»)) }",
1066 "fn a() { dbg!(b.c(vec![«d»])) }",
1067 "fn a() { dbg!(b.c(vec![d«.»])) }",
1068 "fn a() { dbg!(b.c(vec![d.«e»])) }",
1069 ]);
1070
1071 assert_capture_ranges(
1072 &syntax_map,
1073 &buffer,
1074 &["field"],
1075 "fn a() { dbg!(b.«c»(vec![d.«e»])) }",
1076 );
1077 }
1078
1079 #[gpui::test]
1080 fn test_pasting_new_injection_line_between_others() {
1081 let (buffer, syntax_map) = test_edit_sequence(&[
1082 "
1083 fn a() {
1084 b!(B {});
1085 c!(C {});
1086 d!(D {});
1087 e!(E {});
1088 f!(F {});
1089 g!(G {});
1090 }
1091 ",
1092 "
1093 fn a() {
1094 b!(B {});
1095 c!(C {});
1096 d!(D {});
1097 « h!(H {});
1098 » e!(E {});
1099 f!(F {});
1100 g!(G {});
1101 }
1102 ",
1103 ]);
1104
1105 assert_capture_ranges(
1106 &syntax_map,
1107 &buffer,
1108 &["struct"],
1109 "
1110 fn a() {
1111 b!(«B {}»);
1112 c!(«C {}»);
1113 d!(«D {}»);
1114 h!(«H {}»);
1115 e!(«E {}»);
1116 f!(«F {}»);
1117 g!(«G {}»);
1118 }
1119 ",
1120 );
1121 }
1122
1123 #[gpui::test]
1124 fn test_joining_injections_with_child_injections() {
1125 let (buffer, syntax_map) = test_edit_sequence(&[
1126 "
1127 fn a() {
1128 b!(
1129 c![one.two.three],
1130 d![four.five.six],
1131 );
1132 e!(
1133 f![seven.eight],
1134 );
1135 }
1136 ",
1137 "
1138 fn a() {
1139 b!(
1140 c![one.two.three],
1141 d![four.five.six],
1142 ˇ f![seven.eight],
1143 );
1144 }
1145 ",
1146 ]);
1147
1148 assert_capture_ranges(
1149 &syntax_map,
1150 &buffer,
1151 &["field"],
1152 "
1153 fn a() {
1154 b!(
1155 c![one.«two».«three»],
1156 d![four.«five».«six»],
1157 f![seven.«eight»],
1158 );
1159 }
1160 ",
1161 );
1162 }
1163
1164 #[gpui::test]
1165 fn test_editing_edges_of_injection() {
1166 test_edit_sequence(&[
1167 "
1168 fn a() {
1169 b!(c!())
1170 }
1171 ",
1172 "
1173 fn a() {
1174 «d»!(c!())
1175 }
1176 ",
1177 "
1178 fn a() {
1179 «e»d!(c!())
1180 }
1181 ",
1182 "
1183 fn a() {
1184 ed!«[»c!()«]»
1185 }
1186 ",
1187 ]);
1188 }
1189
1190 #[gpui::test]
1191 fn test_edits_preceding_and_intersecting_injection() {
1192 test_edit_sequence(&[
1193 //
1194 "const aaaaaaaaaaaa: B = c!(d(e.f));",
1195 "const aˇa: B = c!(d(eˇ));",
1196 ]);
1197 }
1198
1199 #[gpui::test]
1200 fn test_non_local_changes_create_injections() {
1201 test_edit_sequence(&[
1202 "
1203 // a! {
1204 static B: C = d;
1205 // }
1206 ",
1207 "
1208 ˇa! {
1209 static B: C = d;
1210 ˇ}
1211 ",
1212 ]);
1213 }
1214
1215 #[gpui::test]
1216 fn test_creating_many_injections_in_one_edit() {
1217 test_edit_sequence(&[
1218 "
1219 fn a() {
1220 one(Two::three(3));
1221 four(Five::six(6));
1222 seven(Eight::nine(9));
1223 }
1224 ",
1225 "
1226 fn a() {
1227 one«!»(Two::three(3));
1228 four«!»(Five::six(6));
1229 seven«!»(Eight::nine(9));
1230 }
1231 ",
1232 "
1233 fn a() {
1234 one!(Two::three«!»(3));
1235 four!(Five::six«!»(6));
1236 seven!(Eight::nine«!»(9));
1237 }
1238 ",
1239 ]);
1240 }
1241
1242 #[gpui::test]
1243 fn test_editing_across_injection_boundary() {
1244 test_edit_sequence(&[
1245 "
1246 fn one() {
1247 two();
1248 three!(
1249 three.four,
1250 five.six,
1251 );
1252 }
1253 ",
1254 "
1255 fn one() {
1256 two();
1257 th«irty_five![»
1258 three.four,
1259 five.six,
1260 « seven.eight,
1261 ];»
1262 }
1263 ",
1264 ]);
1265 }
1266
1267 fn test_edit_sequence(steps: &[&str]) -> (Buffer, SyntaxMap) {
1268 let registry = Arc::new(LanguageRegistry::test());
1269 let language = Arc::new(rust_lang());
1270 registry.add(language.clone());
1271 let mut buffer = Buffer::new(0, 0, Default::default());
1272
1273 let mut mutated_syntax_map = SyntaxMap::new();
1274 mutated_syntax_map.set_language_registry(registry.clone());
1275 mutated_syntax_map.reparse(language.clone(), &buffer);
1276
1277 for (i, marked_string) in steps.into_iter().enumerate() {
1278 edit_buffer(&mut buffer, &marked_string.unindent());
1279
1280 // Reparse the syntax map
1281 mutated_syntax_map.interpolate(&buffer);
1282 mutated_syntax_map.reparse(language.clone(), &buffer);
1283
1284 // Create a second syntax map from scratch
1285 let mut reference_syntax_map = SyntaxMap::new();
1286 reference_syntax_map.set_language_registry(registry.clone());
1287 reference_syntax_map.reparse(language.clone(), &buffer);
1288
1289 // Compare the mutated syntax map to the new syntax map
1290 let mutated_layers = mutated_syntax_map.layers(&buffer);
1291 let reference_layers = reference_syntax_map.layers(&buffer);
1292 assert_eq!(
1293 mutated_layers.len(),
1294 reference_layers.len(),
1295 "wrong number of layers at step {i}"
1296 );
1297 for (edited_layer, reference_layer) in
1298 mutated_layers.into_iter().zip(reference_layers.into_iter())
1299 {
1300 assert_eq!(
1301 edited_layer.1.to_sexp(),
1302 reference_layer.1.to_sexp(),
1303 "different layer at step {i}"
1304 );
1305 assert_eq!(
1306 edited_layer.1.range(),
1307 reference_layer.1.range(),
1308 "different layer at step {i}"
1309 );
1310 }
1311 }
1312
1313 (buffer, mutated_syntax_map)
1314 }
1315
1316 fn rust_lang() -> Language {
1317 Language::new(
1318 LanguageConfig {
1319 name: "Rust".into(),
1320 path_suffixes: vec!["rs".to_string()],
1321 ..Default::default()
1322 },
1323 Some(tree_sitter_rust::language()),
1324 )
1325 .with_highlights_query(
1326 r#"
1327 (field_identifier) @field
1328 (struct_expression) @struct
1329 "#,
1330 )
1331 .unwrap()
1332 .with_injection_query(
1333 r#"
1334 (macro_invocation
1335 (token_tree) @content
1336 (#set! "language" "rust"))
1337 "#,
1338 )
1339 .unwrap()
1340 }
1341
1342 fn range_for_text(buffer: &Buffer, text: &str) -> Range<usize> {
1343 let start = buffer.as_rope().to_string().find(text).unwrap();
1344 start..start + text.len()
1345 }
1346
1347 fn assert_layers_for_range(
1348 syntax_map: &SyntaxMap,
1349 buffer: &BufferSnapshot,
1350 range: Range<Point>,
1351 expected_layers: &[&str],
1352 ) {
1353 let layers = syntax_map.layers_for_range(range, &buffer);
1354 assert_eq!(
1355 layers.len(),
1356 expected_layers.len(),
1357 "wrong number of layers"
1358 );
1359 for (i, ((_, _, node), expected_s_exp)) in
1360 layers.iter().zip(expected_layers.iter()).enumerate()
1361 {
1362 let actual_s_exp = node.to_sexp();
1363 assert!(
1364 string_contains_sequence(
1365 &actual_s_exp,
1366 &expected_s_exp.split("...").collect::<Vec<_>>()
1367 ),
1368 "layer {i}:\n\nexpected: {expected_s_exp}\nactual: {actual_s_exp}",
1369 );
1370 }
1371 }
1372
1373 fn assert_capture_ranges(
1374 syntax_map: &SyntaxMap,
1375 buffer: &BufferSnapshot,
1376 highlight_query_capture_names: &[&str],
1377 marked_string: &str,
1378 ) {
1379 let mut actual_ranges = Vec::<Range<usize>>::new();
1380 for capture in syntax_map.captures(0..buffer.len(), buffer, |grammar| {
1381 grammar.highlights_query.as_ref()
1382 }) {
1383 let name = &capture
1384 .grammar
1385 .highlights_query
1386 .as_ref()
1387 .unwrap()
1388 .capture_names()[capture.index as usize];
1389 dbg!(capture.node, capture.index, name);
1390 if highlight_query_capture_names.contains(&name.as_str()) {
1391 actual_ranges.push(capture.node.byte_range());
1392 }
1393 }
1394
1395 let (text, expected_ranges) = marked_text_ranges(&marked_string.unindent(), false);
1396 assert_eq!(text, buffer.text());
1397 assert_eq!(actual_ranges, expected_ranges);
1398 }
1399
1400 fn edit_buffer(buffer: &mut Buffer, marked_string: &str) {
1401 let old_text = buffer.text();
1402 let (new_text, mut ranges) = marked_text_ranges(marked_string, false);
1403 if ranges.is_empty() {
1404 ranges.push(0..new_text.len());
1405 }
1406
1407 assert_eq!(
1408 old_text[..ranges[0].start],
1409 new_text[..ranges[0].start],
1410 "invalid edit"
1411 );
1412
1413 let mut delta = 0;
1414 let mut edits = Vec::new();
1415 let mut ranges = ranges.into_iter().peekable();
1416
1417 while let Some(inserted_range) = ranges.next() {
1418 let new_start = inserted_range.start;
1419 let old_start = (new_start as isize - delta) as usize;
1420
1421 let following_text = if let Some(next_range) = ranges.peek() {
1422 &new_text[inserted_range.end..next_range.start]
1423 } else {
1424 &new_text[inserted_range.end..]
1425 };
1426
1427 let inserted_len = inserted_range.len();
1428 let deleted_len = old_text[old_start..]
1429 .find(following_text)
1430 .expect("invalid edit");
1431
1432 let old_range = old_start..old_start + deleted_len;
1433 edits.push((old_range, new_text[inserted_range].to_string()));
1434 delta += inserted_len as isize - deleted_len as isize;
1435 }
1436
1437 assert_eq!(
1438 old_text.len() as isize + delta,
1439 new_text.len() as isize,
1440 "invalid edit"
1441 );
1442
1443 buffer.edit(edits);
1444 }
1445
1446 pub fn string_contains_sequence(text: &str, parts: &[&str]) -> bool {
1447 let mut last_part_end = 0;
1448 for part in parts {
1449 if let Some(start_ix) = text[last_part_end..].find(part) {
1450 last_part_end = start_ix + part.len();
1451 } else {
1452 return false;
1453 }
1454 }
1455 true
1456 }
1457}