1#[cfg(test)]
2mod syntax_map_tests;
3
4use crate::{Grammar, InjectionConfig, Language, LanguageRegistry};
5use collections::HashMap;
6use futures::FutureExt;
7use parking_lot::Mutex;
8use std::{
9 borrow::Cow,
10 cmp::{self, Ordering, Reverse},
11 collections::BinaryHeap,
12 fmt, iter,
13 ops::{Deref, DerefMut, Range},
14 sync::Arc,
15};
16use sum_tree::{Bias, SeekTarget, SumTree};
17use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point, Rope, ToOffset, ToPoint};
18use tree_sitter::{Node, Query, QueryCapture, QueryCaptures, QueryCursor, QueryMatches, Tree};
19
20use super::PARSER;
21
22static QUERY_CURSORS: Mutex<Vec<QueryCursor>> = Mutex::new(vec![]);
23
24#[derive(Default)]
25pub struct SyntaxMap {
26 snapshot: SyntaxSnapshot,
27 language_registry: Option<Arc<LanguageRegistry>>,
28}
29
30#[derive(Clone, Default)]
31pub struct SyntaxSnapshot {
32 layers: SumTree<SyntaxLayer>,
33 parsed_version: clock::Global,
34 interpolated_version: clock::Global,
35 language_registry_version: usize,
36}
37
38#[derive(Default)]
39pub struct SyntaxMapCaptures<'a> {
40 layers: Vec<SyntaxMapCapturesLayer<'a>>,
41 active_layer_count: usize,
42 grammars: Vec<&'a Grammar>,
43}
44
45#[derive(Default)]
46pub struct SyntaxMapMatches<'a> {
47 layers: Vec<SyntaxMapMatchesLayer<'a>>,
48 active_layer_count: usize,
49 grammars: Vec<&'a Grammar>,
50}
51
52#[derive(Debug)]
53pub struct SyntaxMapCapture<'a> {
54 pub depth: usize,
55 pub node: Node<'a>,
56 pub index: u32,
57 pub grammar_index: usize,
58}
59
60#[derive(Debug)]
61pub struct SyntaxMapMatch<'a> {
62 pub depth: usize,
63 pub pattern_index: usize,
64 pub captures: &'a [QueryCapture<'a>],
65 pub grammar_index: usize,
66}
67
68struct SyntaxMapCapturesLayer<'a> {
69 depth: usize,
70 captures: QueryCaptures<'a, 'a, TextProvider<'a>, &'a [u8]>,
71 next_capture: Option<QueryCapture<'a>>,
72 grammar_index: usize,
73 _query_cursor: QueryCursorHandle,
74}
75
76struct SyntaxMapMatchesLayer<'a> {
77 depth: usize,
78 next_pattern_index: usize,
79 next_captures: Vec<QueryCapture<'a>>,
80 has_next: bool,
81 matches: QueryMatches<'a, 'a, TextProvider<'a>, &'a [u8]>,
82 grammar_index: usize,
83 _query_cursor: QueryCursorHandle,
84}
85
86#[derive(Clone)]
87struct SyntaxLayer {
88 depth: usize,
89 range: Range<Anchor>,
90 content: SyntaxLayerContent,
91}
92
93#[derive(Clone)]
94enum SyntaxLayerContent {
95 Parsed {
96 tree: tree_sitter::Tree,
97 language: Arc<Language>,
98 },
99 Pending {
100 language_name: Arc<str>,
101 },
102}
103
104impl SyntaxLayerContent {
105 fn language_id(&self) -> Option<usize> {
106 match self {
107 SyntaxLayerContent::Parsed { language, .. } => language.id(),
108 SyntaxLayerContent::Pending { .. } => None,
109 }
110 }
111
112 fn tree(&self) -> Option<&Tree> {
113 match self {
114 SyntaxLayerContent::Parsed { tree, .. } => Some(tree),
115 SyntaxLayerContent::Pending { .. } => None,
116 }
117 }
118}
119
120#[derive(Debug)]
121pub struct SyntaxLayerInfo<'a> {
122 pub depth: usize,
123 pub language: &'a Arc<Language>,
124 tree: &'a Tree,
125 offset: (usize, tree_sitter::Point),
126}
127
128#[derive(Clone)]
129pub struct OwnedSyntaxLayerInfo {
130 pub depth: usize,
131 pub language: Arc<Language>,
132 tree: tree_sitter::Tree,
133 offset: (usize, tree_sitter::Point),
134}
135
136#[derive(Debug, Clone)]
137struct SyntaxLayerSummary {
138 min_depth: usize,
139 max_depth: usize,
140 range: Range<Anchor>,
141 last_layer_range: Range<Anchor>,
142 last_layer_language: Option<usize>,
143 contains_unknown_injections: bool,
144}
145
146#[derive(Clone, Debug)]
147struct SyntaxLayerPosition {
148 depth: usize,
149 range: Range<Anchor>,
150 language: Option<usize>,
151}
152
153#[derive(Clone, Debug)]
154struct ChangeStartPosition {
155 depth: usize,
156 position: Anchor,
157}
158
159#[derive(Clone, Debug)]
160struct SyntaxLayerPositionBeforeChange {
161 position: SyntaxLayerPosition,
162 change: ChangeStartPosition,
163}
164
165struct ParseStep {
166 depth: usize,
167 language: ParseStepLanguage,
168 range: Range<Anchor>,
169 included_ranges: Vec<tree_sitter::Range>,
170 mode: ParseMode,
171}
172
173#[derive(Debug)]
174enum ParseStepLanguage {
175 Loaded { language: Arc<Language> },
176 Pending { name: Arc<str> },
177}
178
179impl ParseStepLanguage {
180 fn id(&self) -> Option<usize> {
181 match self {
182 ParseStepLanguage::Loaded { language } => language.id(),
183 ParseStepLanguage::Pending { .. } => None,
184 }
185 }
186}
187
188enum ParseMode {
189 Single,
190 Combined {
191 parent_layer_range: Range<usize>,
192 parent_layer_changed_ranges: Vec<Range<usize>>,
193 },
194}
195
196#[derive(Debug, PartialEq, Eq)]
197struct ChangedRegion {
198 depth: usize,
199 range: Range<Anchor>,
200}
201
202#[derive(Default)]
203struct ChangeRegionSet(Vec<ChangedRegion>);
204
205struct TextProvider<'a>(&'a Rope);
206
207struct ByteChunks<'a>(text::Chunks<'a>);
208
209struct QueryCursorHandle(Option<QueryCursor>);
210
211impl SyntaxMap {
212 pub fn new() -> Self {
213 Self::default()
214 }
215
216 pub fn set_language_registry(&mut self, registry: Arc<LanguageRegistry>) {
217 self.language_registry = Some(registry);
218 }
219
220 pub fn snapshot(&self) -> SyntaxSnapshot {
221 self.snapshot.clone()
222 }
223
224 pub fn language_registry(&self) -> Option<Arc<LanguageRegistry>> {
225 self.language_registry.clone()
226 }
227
228 pub fn interpolate(&mut self, text: &BufferSnapshot) {
229 self.snapshot.interpolate(text);
230 }
231
232 #[cfg(test)]
233 pub fn reparse(&mut self, language: Arc<Language>, text: &BufferSnapshot) {
234 self.snapshot
235 .reparse(text, self.language_registry.clone(), language);
236 }
237
238 pub fn did_parse(&mut self, snapshot: SyntaxSnapshot) {
239 self.snapshot = snapshot;
240 }
241
242 pub fn clear(&mut self) {
243 self.snapshot = SyntaxSnapshot::default();
244 }
245}
246
247impl SyntaxSnapshot {
248 pub fn is_empty(&self) -> bool {
249 self.layers.is_empty()
250 }
251
252 fn interpolate(&mut self, text: &BufferSnapshot) {
253 let edits = text
254 .anchored_edits_since::<(usize, Point)>(&self.interpolated_version)
255 .collect::<Vec<_>>();
256 self.interpolated_version = text.version().clone();
257
258 if edits.is_empty() {
259 return;
260 }
261
262 let mut layers = SumTree::new();
263 let mut first_edit_ix_for_depth = 0;
264 let mut prev_depth = 0;
265 let mut cursor = self.layers.cursor::<SyntaxLayerSummary>();
266 cursor.next(text);
267
268 'outer: loop {
269 let depth = cursor.end(text).max_depth;
270 if depth > prev_depth {
271 first_edit_ix_for_depth = 0;
272 prev_depth = depth;
273 }
274
275 // Preserve any layers at this depth that precede the first edit.
276 if let Some((_, edit_range)) = edits.get(first_edit_ix_for_depth) {
277 let target = ChangeStartPosition {
278 depth,
279 position: edit_range.start,
280 };
281 if target.cmp(&cursor.start(), text).is_gt() {
282 let slice = cursor.slice(&target, Bias::Left, text);
283 layers.append(slice, text);
284 }
285 }
286 // If this layer follows all of the edits, then preserve it and any
287 // subsequent layers at this same depth.
288 else if cursor.item().is_some() {
289 let slice = cursor.slice(
290 &SyntaxLayerPosition {
291 depth: depth + 1,
292 range: Anchor::MIN..Anchor::MAX,
293 language: None,
294 },
295 Bias::Left,
296 text,
297 );
298 layers.append(slice, text);
299 continue;
300 };
301
302 let Some(layer) = cursor.item() else { break };
303 let (start_byte, start_point) = layer.range.start.summary::<(usize, Point)>(text);
304
305 // Ignore edits that end before the start of this layer, and don't consider them
306 // for any subsequent layers at this same depth.
307 loop {
308 let Some((_, edit_range)) = edits.get(first_edit_ix_for_depth) else {
309 continue 'outer;
310 };
311 if edit_range.end.cmp(&layer.range.start, text).is_le() {
312 first_edit_ix_for_depth += 1;
313 } else {
314 break;
315 }
316 }
317
318 let mut layer = layer.clone();
319 if let SyntaxLayerContent::Parsed { tree, .. } = &mut layer.content {
320 for (edit, edit_range) in &edits[first_edit_ix_for_depth..] {
321 // Ignore any edits that follow this layer.
322 if edit_range.start.cmp(&layer.range.end, text).is_ge() {
323 break;
324 }
325
326 // Apply any edits that intersect this layer to the layer's syntax tree.
327 let tree_edit = if edit_range.start.cmp(&layer.range.start, text).is_ge() {
328 tree_sitter::InputEdit {
329 start_byte: edit.new.start.0 - start_byte,
330 old_end_byte: edit.new.start.0 - start_byte
331 + (edit.old.end.0 - edit.old.start.0),
332 new_end_byte: edit.new.end.0 - start_byte,
333 start_position: (edit.new.start.1 - start_point).to_ts_point(),
334 old_end_position: (edit.new.start.1 - start_point
335 + (edit.old.end.1 - edit.old.start.1))
336 .to_ts_point(),
337 new_end_position: (edit.new.end.1 - start_point).to_ts_point(),
338 }
339 } else {
340 let node = tree.root_node();
341 tree_sitter::InputEdit {
342 start_byte: 0,
343 old_end_byte: node.end_byte(),
344 new_end_byte: 0,
345 start_position: Default::default(),
346 old_end_position: node.end_position(),
347 new_end_position: Default::default(),
348 }
349 };
350
351 tree.edit(&tree_edit);
352 }
353
354 debug_assert!(
355 tree.root_node().end_byte() <= text.len(),
356 "tree's size {}, is larger than text size {}",
357 tree.root_node().end_byte(),
358 text.len(),
359 );
360 }
361
362 layers.push(layer, text);
363 cursor.next(text);
364 }
365
366 layers.append(cursor.suffix(&text), &text);
367 drop(cursor);
368 self.layers = layers;
369 }
370
371 pub fn reparse(
372 &mut self,
373 text: &BufferSnapshot,
374 registry: Option<Arc<LanguageRegistry>>,
375 root_language: Arc<Language>,
376 ) {
377 let edit_ranges = text
378 .edits_since::<usize>(&self.parsed_version)
379 .map(|edit| edit.new)
380 .collect::<Vec<_>>();
381 self.reparse_with_ranges(text, root_language.clone(), edit_ranges, registry.as_ref());
382
383 if let Some(registry) = registry {
384 if registry.version() != self.language_registry_version {
385 let mut resolved_injection_ranges = Vec::new();
386 let mut cursor = self
387 .layers
388 .filter::<_, ()>(|summary| summary.contains_unknown_injections);
389 cursor.next(text);
390 while let Some(layer) = cursor.item() {
391 let SyntaxLayerContent::Pending { language_name } = &layer.content else {
392 unreachable!()
393 };
394 if registry
395 .language_for_name_or_extension(language_name)
396 .now_or_never()
397 .and_then(|language| language.ok())
398 .is_some()
399 {
400 resolved_injection_ranges.push(layer.range.to_offset(text));
401 }
402
403 cursor.next(text);
404 }
405 drop(cursor);
406
407 if !resolved_injection_ranges.is_empty() {
408 self.reparse_with_ranges(
409 text,
410 root_language,
411 resolved_injection_ranges,
412 Some(®istry),
413 );
414 }
415 self.language_registry_version = registry.version();
416 }
417 }
418 }
419
420 fn reparse_with_ranges(
421 &mut self,
422 text: &BufferSnapshot,
423 root_language: Arc<Language>,
424 invalidated_ranges: Vec<Range<usize>>,
425 registry: Option<&Arc<LanguageRegistry>>,
426 ) {
427 log::trace!("reparse. invalidated ranges:{:?}", invalidated_ranges);
428
429 let max_depth = self.layers.summary().max_depth;
430 let mut cursor = self.layers.cursor::<SyntaxLayerSummary>();
431 cursor.next(&text);
432 let mut layers = SumTree::new();
433
434 let mut changed_regions = ChangeRegionSet::default();
435 let mut queue = BinaryHeap::new();
436 let mut combined_injection_ranges = HashMap::default();
437 queue.push(ParseStep {
438 depth: 0,
439 language: ParseStepLanguage::Loaded {
440 language: root_language,
441 },
442 included_ranges: vec![tree_sitter::Range {
443 start_byte: 0,
444 end_byte: text.len(),
445 start_point: Point::zero().to_ts_point(),
446 end_point: text.max_point().to_ts_point(),
447 }],
448 range: Anchor::MIN..Anchor::MAX,
449 mode: ParseMode::Single,
450 });
451
452 loop {
453 let step = queue.pop();
454 let position = if let Some(step) = &step {
455 SyntaxLayerPosition {
456 depth: step.depth,
457 range: step.range.clone(),
458 language: step.language.id(),
459 }
460 } else {
461 SyntaxLayerPosition {
462 depth: max_depth + 1,
463 range: Anchor::MAX..Anchor::MAX,
464 language: None,
465 }
466 };
467
468 let mut done = cursor.item().is_none();
469 while !done && position.cmp(&cursor.end(text), &text).is_gt() {
470 done = true;
471
472 let bounded_position = SyntaxLayerPositionBeforeChange {
473 position: position.clone(),
474 change: changed_regions.start_position(),
475 };
476 if bounded_position.cmp(&cursor.start(), &text).is_gt() {
477 let slice = cursor.slice(&bounded_position, Bias::Left, text);
478 if !slice.is_empty() {
479 layers.append(slice, &text);
480 if changed_regions.prune(cursor.end(text), text) {
481 done = false;
482 }
483 }
484 }
485
486 while position.cmp(&cursor.end(text), text).is_gt() {
487 let Some(layer) = cursor.item() else { break };
488
489 if changed_regions.intersects(&layer, text) {
490 if let SyntaxLayerContent::Parsed { language, .. } = &layer.content {
491 log::trace!(
492 "discard layer. language:{}, range:{:?}. changed_regions:{:?}",
493 language.name(),
494 LogAnchorRange(&layer.range, text),
495 LogChangedRegions(&changed_regions, text),
496 );
497 }
498
499 changed_regions.insert(
500 ChangedRegion {
501 depth: layer.depth + 1,
502 range: layer.range.clone(),
503 },
504 text,
505 );
506 } else {
507 layers.push(layer.clone(), text);
508 }
509
510 cursor.next(text);
511 if changed_regions.prune(cursor.end(text), text) {
512 done = false;
513 }
514 }
515 }
516
517 let Some(step) = step else { break };
518 let (step_start_byte, step_start_point) =
519 step.range.start.summary::<(usize, Point)>(text);
520 let step_end_byte = step.range.end.to_offset(text);
521
522 let mut old_layer = cursor.item();
523 if let Some(layer) = old_layer {
524 if layer.range.to_offset(text) == (step_start_byte..step_end_byte)
525 && layer.content.language_id() == step.language.id()
526 {
527 cursor.next(&text);
528 } else {
529 old_layer = None;
530 }
531 }
532
533 let content = match step.language {
534 ParseStepLanguage::Loaded { language } => {
535 let Some(grammar) = language.grammar() else {
536 continue;
537 };
538 let tree;
539 let changed_ranges;
540
541 let mut included_ranges = step.included_ranges;
542 for range in &mut included_ranges {
543 range.start_byte -= step_start_byte;
544 range.end_byte -= step_start_byte;
545 range.start_point = (Point::from_ts_point(range.start_point)
546 - step_start_point)
547 .to_ts_point();
548 range.end_point = (Point::from_ts_point(range.end_point)
549 - step_start_point)
550 .to_ts_point();
551 }
552
553 if let Some((SyntaxLayerContent::Parsed { tree: old_tree, .. }, layer_start)) =
554 old_layer.map(|layer| (&layer.content, layer.range.start))
555 {
556 log::trace!(
557 "existing layer. language:{}, start:{:?}, ranges:{:?}",
558 language.name(),
559 LogPoint(layer_start.to_point(&text)),
560 LogIncludedRanges(&old_tree.included_ranges())
561 );
562
563 if let ParseMode::Combined {
564 mut parent_layer_changed_ranges,
565 ..
566 } = step.mode
567 {
568 for range in &mut parent_layer_changed_ranges {
569 range.start = range.start.saturating_sub(step_start_byte);
570 range.end = range.end.saturating_sub(step_start_byte);
571 }
572
573 let changed_indices;
574 (included_ranges, changed_indices) = splice_included_ranges(
575 old_tree.included_ranges(),
576 &parent_layer_changed_ranges,
577 &included_ranges,
578 );
579 insert_newlines_between_ranges(
580 changed_indices,
581 &mut included_ranges,
582 &text,
583 step_start_byte,
584 step_start_point,
585 );
586 }
587
588 if included_ranges.is_empty() {
589 included_ranges.push(tree_sitter::Range {
590 start_byte: 0,
591 end_byte: 0,
592 start_point: Default::default(),
593 end_point: Default::default(),
594 });
595 }
596
597 log::trace!(
598 "update layer. language:{}, start:{:?}, included_ranges:{:?}",
599 language.name(),
600 LogAnchorRange(&step.range, text),
601 LogIncludedRanges(&included_ranges),
602 );
603
604 tree = parse_text(
605 grammar,
606 text.as_rope(),
607 step_start_byte,
608 included_ranges,
609 Some(old_tree.clone()),
610 );
611 changed_ranges = join_ranges(
612 invalidated_ranges.iter().cloned().filter(|range| {
613 range.start <= step_end_byte && range.end >= step_start_byte
614 }),
615 old_tree.changed_ranges(&tree).map(|r| {
616 step_start_byte + r.start_byte..step_start_byte + r.end_byte
617 }),
618 );
619 } else {
620 if matches!(step.mode, ParseMode::Combined { .. }) {
621 insert_newlines_between_ranges(
622 0..included_ranges.len(),
623 &mut included_ranges,
624 text,
625 step_start_byte,
626 step_start_point,
627 );
628 }
629
630 if included_ranges.is_empty() {
631 included_ranges.push(tree_sitter::Range {
632 start_byte: 0,
633 end_byte: 0,
634 start_point: Default::default(),
635 end_point: Default::default(),
636 });
637 }
638
639 log::trace!(
640 "create layer. language:{}, range:{:?}, included_ranges:{:?}",
641 language.name(),
642 LogAnchorRange(&step.range, text),
643 LogIncludedRanges(&included_ranges),
644 );
645
646 tree = parse_text(
647 grammar,
648 text.as_rope(),
649 step_start_byte,
650 included_ranges,
651 None,
652 );
653 changed_ranges = vec![step_start_byte..step_end_byte];
654 }
655
656 if let (Some((config, registry)), false) = (
657 grammar.injection_config.as_ref().zip(registry.as_ref()),
658 changed_ranges.is_empty(),
659 ) {
660 for range in &changed_ranges {
661 changed_regions.insert(
662 ChangedRegion {
663 depth: step.depth + 1,
664 range: text.anchor_before(range.start)
665 ..text.anchor_after(range.end),
666 },
667 text,
668 );
669 }
670 get_injections(
671 config,
672 text,
673 step.range.clone(),
674 tree.root_node_with_offset(
675 step_start_byte,
676 step_start_point.to_ts_point(),
677 ),
678 registry,
679 step.depth + 1,
680 &changed_ranges,
681 &mut combined_injection_ranges,
682 &mut queue,
683 );
684 }
685
686 SyntaxLayerContent::Parsed { tree, language }
687 }
688 ParseStepLanguage::Pending { name } => SyntaxLayerContent::Pending {
689 language_name: name,
690 },
691 };
692
693 layers.push(
694 SyntaxLayer {
695 depth: step.depth,
696 range: step.range,
697 content,
698 },
699 &text,
700 );
701 }
702
703 drop(cursor);
704 self.layers = layers;
705 self.interpolated_version = text.version.clone();
706 self.parsed_version = text.version.clone();
707 #[cfg(debug_assertions)]
708 self.check_invariants(text);
709 }
710
711 #[cfg(debug_assertions)]
712 fn check_invariants(&self, text: &BufferSnapshot) {
713 let mut max_depth = 0;
714 let mut prev_range: Option<Range<Anchor>> = None;
715 for layer in self.layers.iter() {
716 if layer.depth == max_depth {
717 if let Some(prev_range) = prev_range {
718 match layer.range.start.cmp(&prev_range.start, text) {
719 Ordering::Less => panic!("layers out of order"),
720 Ordering::Equal => {
721 assert!(layer.range.end.cmp(&prev_range.end, text).is_ge())
722 }
723 Ordering::Greater => {}
724 }
725 }
726 } else if layer.depth < max_depth {
727 panic!("layers out of order")
728 }
729 max_depth = layer.depth;
730 prev_range = Some(layer.range.clone());
731 }
732 }
733
734 pub fn single_tree_captures<'a>(
735 range: Range<usize>,
736 text: &'a Rope,
737 tree: &'a Tree,
738 language: &'a Arc<Language>,
739 query: fn(&Grammar) -> Option<&Query>,
740 ) -> SyntaxMapCaptures<'a> {
741 SyntaxMapCaptures::new(
742 range.clone(),
743 text,
744 [SyntaxLayerInfo {
745 language,
746 tree,
747 depth: 0,
748 offset: (0, tree_sitter::Point::new(0, 0)),
749 }]
750 .into_iter(),
751 query,
752 )
753 }
754
755 pub fn captures<'a>(
756 &'a self,
757 range: Range<usize>,
758 buffer: &'a BufferSnapshot,
759 query: fn(&Grammar) -> Option<&Query>,
760 ) -> SyntaxMapCaptures {
761 SyntaxMapCaptures::new(
762 range.clone(),
763 buffer.as_rope(),
764 self.layers_for_range(range, buffer).into_iter(),
765 query,
766 )
767 }
768
769 pub fn matches<'a>(
770 &'a self,
771 range: Range<usize>,
772 buffer: &'a BufferSnapshot,
773 query: fn(&Grammar) -> Option<&Query>,
774 ) -> SyntaxMapMatches {
775 SyntaxMapMatches::new(
776 range.clone(),
777 buffer.as_rope(),
778 self.layers_for_range(range, buffer).into_iter(),
779 query,
780 )
781 }
782
783 #[cfg(test)]
784 pub fn layers<'a>(&'a self, buffer: &'a BufferSnapshot) -> Vec<SyntaxLayerInfo> {
785 self.layers_for_range(0..buffer.len(), buffer).collect()
786 }
787
788 pub fn layers_for_range<'a, T: ToOffset>(
789 &'a self,
790 range: Range<T>,
791 buffer: &'a BufferSnapshot,
792 ) -> impl 'a + Iterator<Item = SyntaxLayerInfo> {
793 let start_offset = range.start.to_offset(buffer);
794 let end_offset = range.end.to_offset(buffer);
795 let start = buffer.anchor_before(start_offset);
796 let end = buffer.anchor_after(end_offset);
797
798 let mut cursor = self.layers.filter::<_, ()>(move |summary| {
799 if summary.max_depth > summary.min_depth {
800 true
801 } else {
802 let is_before_start = summary.range.end.cmp(&start, buffer).is_lt();
803 let is_after_end = summary.range.start.cmp(&end, buffer).is_gt();
804 !is_before_start && !is_after_end
805 }
806 });
807
808 cursor.next(buffer);
809 iter::from_fn(move || {
810 while let Some(layer) = cursor.item() {
811 let mut info = None;
812 if let SyntaxLayerContent::Parsed { tree, language } = &layer.content {
813 let layer_start_offset = layer.range.start.to_offset(buffer);
814 let layer_start_point = layer.range.start.to_point(buffer).to_ts_point();
815
816 info = Some(SyntaxLayerInfo {
817 tree,
818 language,
819 depth: layer.depth,
820 offset: (layer_start_offset, layer_start_point),
821 });
822 }
823 cursor.next(buffer);
824 if info.is_some() {
825 return info;
826 }
827 }
828 None
829 })
830 }
831
832 pub fn contains_unknown_injections(&self) -> bool {
833 self.layers.summary().contains_unknown_injections
834 }
835
836 pub fn language_registry_version(&self) -> usize {
837 self.language_registry_version
838 }
839}
840
841impl<'a> SyntaxMapCaptures<'a> {
842 fn new(
843 range: Range<usize>,
844 text: &'a Rope,
845 layers: impl Iterator<Item = SyntaxLayerInfo<'a>>,
846 query: fn(&Grammar) -> Option<&Query>,
847 ) -> Self {
848 let mut result = Self {
849 layers: Vec::new(),
850 grammars: Vec::new(),
851 active_layer_count: 0,
852 };
853 for layer in layers {
854 let grammar = match &layer.language.grammar {
855 Some(grammar) => grammar,
856 None => continue,
857 };
858 let query = match query(&grammar) {
859 Some(query) => query,
860 None => continue,
861 };
862
863 let mut query_cursor = QueryCursorHandle::new();
864
865 // TODO - add a Tree-sitter API to remove the need for this.
866 let cursor = unsafe {
867 std::mem::transmute::<_, &'static mut QueryCursor>(query_cursor.deref_mut())
868 };
869
870 cursor.set_byte_range(range.clone());
871 let captures = cursor.captures(query, layer.node(), TextProvider(text));
872 let grammar_index = result
873 .grammars
874 .iter()
875 .position(|g| g.id == grammar.id())
876 .unwrap_or_else(|| {
877 result.grammars.push(grammar);
878 result.grammars.len() - 1
879 });
880 let mut layer = SyntaxMapCapturesLayer {
881 depth: layer.depth,
882 grammar_index,
883 next_capture: None,
884 captures,
885 _query_cursor: query_cursor,
886 };
887
888 layer.advance();
889 if layer.next_capture.is_some() {
890 let key = layer.sort_key();
891 let ix = match result.layers[..result.active_layer_count]
892 .binary_search_by_key(&key, |layer| layer.sort_key())
893 {
894 Ok(ix) | Err(ix) => ix,
895 };
896 result.layers.insert(ix, layer);
897 result.active_layer_count += 1;
898 } else {
899 result.layers.push(layer);
900 }
901 }
902
903 result
904 }
905
906 pub fn grammars(&self) -> &[&'a Grammar] {
907 &self.grammars
908 }
909
910 pub fn peek(&self) -> Option<SyntaxMapCapture<'a>> {
911 let layer = self.layers[..self.active_layer_count].first()?;
912 let capture = layer.next_capture?;
913 Some(SyntaxMapCapture {
914 depth: layer.depth,
915 grammar_index: layer.grammar_index,
916 index: capture.index,
917 node: capture.node,
918 })
919 }
920
921 pub fn advance(&mut self) -> bool {
922 let layer = if let Some(layer) = self.layers[..self.active_layer_count].first_mut() {
923 layer
924 } else {
925 return false;
926 };
927
928 layer.advance();
929 if layer.next_capture.is_some() {
930 let key = layer.sort_key();
931 let i = 1 + self.layers[1..self.active_layer_count]
932 .iter()
933 .position(|later_layer| key < later_layer.sort_key())
934 .unwrap_or(self.active_layer_count - 1);
935 self.layers[0..i].rotate_left(1);
936 } else {
937 self.layers[0..self.active_layer_count].rotate_left(1);
938 self.active_layer_count -= 1;
939 }
940
941 true
942 }
943
944 pub fn set_byte_range(&mut self, range: Range<usize>) {
945 for layer in &mut self.layers {
946 layer.captures.set_byte_range(range.clone());
947 if let Some(capture) = &layer.next_capture {
948 if capture.node.end_byte() > range.start {
949 continue;
950 }
951 }
952 layer.advance();
953 }
954 self.layers.sort_unstable_by_key(|layer| layer.sort_key());
955 self.active_layer_count = self
956 .layers
957 .iter()
958 .position(|layer| layer.next_capture.is_none())
959 .unwrap_or(self.layers.len());
960 }
961}
962
963impl<'a> SyntaxMapMatches<'a> {
964 fn new(
965 range: Range<usize>,
966 text: &'a Rope,
967 layers: impl Iterator<Item = SyntaxLayerInfo<'a>>,
968 query: fn(&Grammar) -> Option<&Query>,
969 ) -> Self {
970 let mut result = Self::default();
971 for layer in layers {
972 let grammar = match &layer.language.grammar {
973 Some(grammar) => grammar,
974 None => continue,
975 };
976 let query = match query(&grammar) {
977 Some(query) => query,
978 None => continue,
979 };
980
981 let mut query_cursor = QueryCursorHandle::new();
982
983 // TODO - add a Tree-sitter API to remove the need for this.
984 let cursor = unsafe {
985 std::mem::transmute::<_, &'static mut QueryCursor>(query_cursor.deref_mut())
986 };
987
988 cursor.set_byte_range(range.clone());
989 let matches = cursor.matches(query, layer.node(), TextProvider(text));
990 let grammar_index = result
991 .grammars
992 .iter()
993 .position(|g| g.id == grammar.id())
994 .unwrap_or_else(|| {
995 result.grammars.push(grammar);
996 result.grammars.len() - 1
997 });
998 let mut layer = SyntaxMapMatchesLayer {
999 depth: layer.depth,
1000 grammar_index,
1001 matches,
1002 next_pattern_index: 0,
1003 next_captures: Vec::new(),
1004 has_next: false,
1005 _query_cursor: query_cursor,
1006 };
1007
1008 layer.advance();
1009 if layer.has_next {
1010 let key = layer.sort_key();
1011 let ix = match result.layers[..result.active_layer_count]
1012 .binary_search_by_key(&key, |layer| layer.sort_key())
1013 {
1014 Ok(ix) | Err(ix) => ix,
1015 };
1016 result.layers.insert(ix, layer);
1017 result.active_layer_count += 1;
1018 } else {
1019 result.layers.push(layer);
1020 }
1021 }
1022 result
1023 }
1024
1025 pub fn grammars(&self) -> &[&'a Grammar] {
1026 &self.grammars
1027 }
1028
1029 pub fn peek(&self) -> Option<SyntaxMapMatch> {
1030 let layer = self.layers.first()?;
1031 if !layer.has_next {
1032 return None;
1033 }
1034 Some(SyntaxMapMatch {
1035 depth: layer.depth,
1036 grammar_index: layer.grammar_index,
1037 pattern_index: layer.next_pattern_index,
1038 captures: &layer.next_captures,
1039 })
1040 }
1041
1042 pub fn advance(&mut self) -> bool {
1043 let layer = if let Some(layer) = self.layers.first_mut() {
1044 layer
1045 } else {
1046 return false;
1047 };
1048
1049 layer.advance();
1050 if layer.has_next {
1051 let key = layer.sort_key();
1052 let i = 1 + self.layers[1..self.active_layer_count]
1053 .iter()
1054 .position(|later_layer| key < later_layer.sort_key())
1055 .unwrap_or(self.active_layer_count - 1);
1056 self.layers[0..i].rotate_left(1);
1057 } else {
1058 self.layers[0..self.active_layer_count].rotate_left(1);
1059 self.active_layer_count -= 1;
1060 }
1061
1062 true
1063 }
1064}
1065
1066impl<'a> SyntaxMapCapturesLayer<'a> {
1067 fn advance(&mut self) {
1068 self.next_capture = self.captures.next().map(|(mat, ix)| mat.captures[ix]);
1069 }
1070
1071 fn sort_key(&self) -> (usize, Reverse<usize>, usize) {
1072 if let Some(capture) = &self.next_capture {
1073 let range = capture.node.byte_range();
1074 (range.start, Reverse(range.end), self.depth)
1075 } else {
1076 (usize::MAX, Reverse(0), usize::MAX)
1077 }
1078 }
1079}
1080
1081impl<'a> SyntaxMapMatchesLayer<'a> {
1082 fn advance(&mut self) {
1083 if let Some(mat) = self.matches.next() {
1084 self.next_captures.clear();
1085 self.next_captures.extend_from_slice(&mat.captures);
1086 self.next_pattern_index = mat.pattern_index;
1087 self.has_next = true;
1088 } else {
1089 self.has_next = false;
1090 }
1091 }
1092
1093 fn sort_key(&self) -> (usize, Reverse<usize>, usize) {
1094 if self.has_next {
1095 let captures = &self.next_captures;
1096 if let Some((first, last)) = captures.first().zip(captures.last()) {
1097 return (
1098 first.node.start_byte(),
1099 Reverse(last.node.end_byte()),
1100 self.depth,
1101 );
1102 }
1103 }
1104 (usize::MAX, Reverse(0), usize::MAX)
1105 }
1106}
1107
1108impl<'a> Iterator for SyntaxMapCaptures<'a> {
1109 type Item = SyntaxMapCapture<'a>;
1110
1111 fn next(&mut self) -> Option<Self::Item> {
1112 let result = self.peek();
1113 self.advance();
1114 result
1115 }
1116}
1117
1118fn join_ranges(
1119 a: impl Iterator<Item = Range<usize>>,
1120 b: impl Iterator<Item = Range<usize>>,
1121) -> Vec<Range<usize>> {
1122 let mut result = Vec::<Range<usize>>::new();
1123 let mut a = a.peekable();
1124 let mut b = b.peekable();
1125 loop {
1126 let range = match (a.peek(), b.peek()) {
1127 (Some(range_a), Some(range_b)) => {
1128 if range_a.start < range_b.start {
1129 a.next().unwrap()
1130 } else {
1131 b.next().unwrap()
1132 }
1133 }
1134 (None, Some(_)) => b.next().unwrap(),
1135 (Some(_), None) => a.next().unwrap(),
1136 (None, None) => break,
1137 };
1138
1139 if let Some(last) = result.last_mut() {
1140 if range.start <= last.end {
1141 last.end = last.end.max(range.end);
1142 continue;
1143 }
1144 }
1145 result.push(range);
1146 }
1147 result
1148}
1149
1150fn parse_text(
1151 grammar: &Grammar,
1152 text: &Rope,
1153 start_byte: usize,
1154 ranges: Vec<tree_sitter::Range>,
1155 old_tree: Option<Tree>,
1156) -> Tree {
1157 PARSER.with(|parser| {
1158 let mut parser = parser.borrow_mut();
1159 let mut chunks = text.chunks_in_range(start_byte..text.len());
1160 parser
1161 .set_included_ranges(&ranges)
1162 .expect("overlapping ranges");
1163 parser
1164 .set_language(&grammar.ts_language)
1165 .expect("incompatible grammar");
1166 parser
1167 .parse_with(
1168 &mut move |offset, _| {
1169 chunks.seek(start_byte + offset);
1170 chunks.next().unwrap_or("").as_bytes()
1171 },
1172 old_tree.as_ref(),
1173 )
1174 .expect("invalid language")
1175 })
1176}
1177
1178fn get_injections(
1179 config: &InjectionConfig,
1180 text: &BufferSnapshot,
1181 outer_range: Range<Anchor>,
1182 node: Node,
1183 language_registry: &Arc<LanguageRegistry>,
1184 depth: usize,
1185 changed_ranges: &[Range<usize>],
1186 combined_injection_ranges: &mut HashMap<Arc<Language>, Vec<tree_sitter::Range>>,
1187 queue: &mut BinaryHeap<ParseStep>,
1188) {
1189 let mut query_cursor = QueryCursorHandle::new();
1190 let mut prev_match = None;
1191
1192 // Ensure that a `ParseStep` is created for every combined injection language, even
1193 // if there currently no matches for that injection.
1194 combined_injection_ranges.clear();
1195 for pattern in &config.patterns {
1196 if let (Some(language_name), true) = (pattern.language.as_ref(), pattern.combined) {
1197 if let Some(language) = language_registry
1198 .language_for_name_or_extension(language_name)
1199 .now_or_never()
1200 .and_then(|language| language.ok())
1201 {
1202 combined_injection_ranges.insert(language, Vec::new());
1203 }
1204 }
1205 }
1206
1207 for query_range in changed_ranges {
1208 query_cursor.set_byte_range(query_range.start.saturating_sub(1)..query_range.end + 1);
1209 for mat in query_cursor.matches(&config.query, node, TextProvider(text.as_rope())) {
1210 let content_ranges = mat
1211 .nodes_for_capture_index(config.content_capture_ix)
1212 .map(|node| node.range())
1213 .collect::<Vec<_>>();
1214 if content_ranges.is_empty() {
1215 continue;
1216 }
1217
1218 let content_range =
1219 content_ranges.first().unwrap().start_byte..content_ranges.last().unwrap().end_byte;
1220
1221 // Avoid duplicate matches if two changed ranges intersect the same injection.
1222 if let Some((prev_pattern_ix, prev_range)) = &prev_match {
1223 if mat.pattern_index == *prev_pattern_ix && content_range == *prev_range {
1224 continue;
1225 }
1226 }
1227
1228 prev_match = Some((mat.pattern_index, content_range.clone()));
1229 let combined = config.patterns[mat.pattern_index].combined;
1230
1231 let mut language_name = None;
1232 let mut step_range = content_range.clone();
1233 if let Some(name) = config.patterns[mat.pattern_index].language.as_ref() {
1234 language_name = Some(Cow::Borrowed(name.as_ref()))
1235 } else if let Some(language_node) = config
1236 .language_capture_ix
1237 .and_then(|ix| mat.nodes_for_capture_index(ix).next())
1238 {
1239 step_range.start = cmp::min(content_range.start, language_node.start_byte());
1240 step_range.end = cmp::max(content_range.end, language_node.end_byte());
1241 language_name = Some(Cow::Owned(
1242 text.text_for_range(language_node.byte_range()).collect(),
1243 ))
1244 };
1245
1246 if let Some(language_name) = language_name {
1247 let language = language_registry
1248 .language_for_name_or_extension(&language_name)
1249 .now_or_never()
1250 .and_then(|language| language.ok());
1251 let range = text.anchor_before(step_range.start)..text.anchor_after(step_range.end);
1252 if let Some(language) = language {
1253 if combined {
1254 combined_injection_ranges
1255 .entry(language.clone())
1256 .or_default()
1257 .extend(content_ranges);
1258 } else {
1259 queue.push(ParseStep {
1260 depth,
1261 language: ParseStepLanguage::Loaded { language },
1262 included_ranges: content_ranges,
1263 range,
1264 mode: ParseMode::Single,
1265 });
1266 }
1267 } else {
1268 queue.push(ParseStep {
1269 depth,
1270 language: ParseStepLanguage::Pending {
1271 name: language_name.into(),
1272 },
1273 included_ranges: content_ranges,
1274 range,
1275 mode: ParseMode::Single,
1276 });
1277 }
1278 }
1279 }
1280 }
1281
1282 for (language, mut included_ranges) in combined_injection_ranges.drain() {
1283 included_ranges.sort_unstable_by(|a, b| {
1284 Ord::cmp(&a.start_byte, &b.start_byte).then_with(|| Ord::cmp(&a.end_byte, &b.end_byte))
1285 });
1286 queue.push(ParseStep {
1287 depth,
1288 language: ParseStepLanguage::Loaded { language },
1289 range: outer_range.clone(),
1290 included_ranges,
1291 mode: ParseMode::Combined {
1292 parent_layer_range: node.start_byte()..node.end_byte(),
1293 parent_layer_changed_ranges: changed_ranges.to_vec(),
1294 },
1295 })
1296 }
1297}
1298
1299/// Update the given list of included `ranges`, removing any ranges that intersect
1300/// `removed_ranges`, and inserting the given `new_ranges`.
1301///
1302/// Returns a new vector of ranges, and the range of the vector that was changed,
1303/// from the previous `ranges` vector.
1304pub(crate) fn splice_included_ranges(
1305 mut ranges: Vec<tree_sitter::Range>,
1306 removed_ranges: &[Range<usize>],
1307 new_ranges: &[tree_sitter::Range],
1308) -> (Vec<tree_sitter::Range>, Range<usize>) {
1309 let mut removed_ranges = removed_ranges.iter().cloned().peekable();
1310 let mut new_ranges = new_ranges.into_iter().cloned().peekable();
1311 let mut ranges_ix = 0;
1312 let mut changed_portion = usize::MAX..0;
1313 loop {
1314 let next_new_range = new_ranges.peek();
1315 let next_removed_range = removed_ranges.peek();
1316
1317 let (remove, insert) = match (next_removed_range, next_new_range) {
1318 (None, None) => break,
1319 (Some(_), None) => (removed_ranges.next().unwrap(), None),
1320 (Some(next_removed_range), Some(next_new_range)) => {
1321 if next_removed_range.end < next_new_range.start_byte {
1322 (removed_ranges.next().unwrap(), None)
1323 } else {
1324 let mut start = next_new_range.start_byte;
1325 let mut end = next_new_range.end_byte;
1326
1327 while let Some(next_removed_range) = removed_ranges.peek() {
1328 if next_removed_range.start > next_new_range.end_byte {
1329 break;
1330 }
1331 let next_removed_range = removed_ranges.next().unwrap();
1332 start = cmp::min(start, next_removed_range.start);
1333 end = cmp::max(end, next_removed_range.end);
1334 }
1335
1336 (start..end, Some(new_ranges.next().unwrap()))
1337 }
1338 }
1339 (None, Some(next_new_range)) => (
1340 next_new_range.start_byte..next_new_range.end_byte,
1341 Some(new_ranges.next().unwrap()),
1342 ),
1343 };
1344
1345 let mut start_ix = ranges_ix
1346 + match ranges[ranges_ix..].binary_search_by_key(&remove.start, |r| r.end_byte) {
1347 Ok(ix) => ix,
1348 Err(ix) => ix,
1349 };
1350 let mut end_ix = ranges_ix
1351 + match ranges[ranges_ix..].binary_search_by_key(&remove.end, |r| r.start_byte) {
1352 Ok(ix) => ix + 1,
1353 Err(ix) => ix,
1354 };
1355
1356 // If there are empty ranges, then there may be multiple ranges with the same
1357 // start or end. Expand the splice to include any adjacent ranges that touch
1358 // the changed range.
1359 while start_ix > 0 {
1360 if ranges[start_ix - 1].end_byte == remove.start {
1361 start_ix -= 1;
1362 } else {
1363 break;
1364 }
1365 }
1366 while let Some(range) = ranges.get(end_ix) {
1367 if range.start_byte == remove.end {
1368 end_ix += 1;
1369 } else {
1370 break;
1371 }
1372 }
1373
1374 changed_portion.start = changed_portion.start.min(start_ix);
1375 changed_portion.end = changed_portion.end.max(if insert.is_some() {
1376 start_ix + 1
1377 } else {
1378 start_ix
1379 });
1380
1381 ranges.splice(start_ix..end_ix, insert);
1382 ranges_ix = start_ix;
1383 }
1384
1385 if changed_portion.end < changed_portion.start {
1386 changed_portion = 0..0;
1387 }
1388
1389 (ranges, changed_portion)
1390}
1391
1392/// Ensure there are newline ranges in between content range that appear on
1393/// different lines. For performance, only iterate through the given range of
1394/// indices. All of the ranges in the array are relative to a given start byte
1395/// and point.
1396fn insert_newlines_between_ranges(
1397 indices: Range<usize>,
1398 ranges: &mut Vec<tree_sitter::Range>,
1399 text: &text::BufferSnapshot,
1400 start_byte: usize,
1401 start_point: Point,
1402) {
1403 let mut ix = indices.end + 1;
1404 while ix > indices.start {
1405 ix -= 1;
1406 if 0 == ix || ix == ranges.len() {
1407 continue;
1408 }
1409
1410 let range_b = ranges[ix].clone();
1411 let range_a = &mut ranges[ix - 1];
1412 if range_a.end_point.column == 0 {
1413 continue;
1414 }
1415
1416 if range_a.end_point.row < range_b.start_point.row {
1417 let end_point = start_point + Point::from_ts_point(range_a.end_point);
1418 let line_end = Point::new(end_point.row, text.line_len(end_point.row));
1419 if end_point.column as u32 >= line_end.column {
1420 range_a.end_byte += 1;
1421 range_a.end_point.row += 1;
1422 range_a.end_point.column = 0;
1423 } else {
1424 let newline_offset = text.point_to_offset(line_end);
1425 ranges.insert(
1426 ix,
1427 tree_sitter::Range {
1428 start_byte: newline_offset - start_byte,
1429 end_byte: newline_offset - start_byte + 1,
1430 start_point: (line_end - start_point).to_ts_point(),
1431 end_point: ((line_end - start_point) + Point::new(1, 0)).to_ts_point(),
1432 },
1433 )
1434 }
1435 }
1436 }
1437}
1438
1439impl OwnedSyntaxLayerInfo {
1440 pub fn node(&self) -> Node {
1441 self.tree
1442 .root_node_with_offset(self.offset.0, self.offset.1)
1443 }
1444}
1445
1446impl<'a> SyntaxLayerInfo<'a> {
1447 pub fn to_owned(&self) -> OwnedSyntaxLayerInfo {
1448 OwnedSyntaxLayerInfo {
1449 tree: self.tree.clone(),
1450 offset: self.offset,
1451 depth: self.depth,
1452 language: self.language.clone(),
1453 }
1454 }
1455
1456 pub fn node(&self) -> Node<'a> {
1457 self.tree
1458 .root_node_with_offset(self.offset.0, self.offset.1)
1459 }
1460
1461 pub(crate) fn override_id(&self, offset: usize, text: &text::BufferSnapshot) -> Option<u32> {
1462 let text = TextProvider(text.as_rope());
1463 let config = self.language.grammar.as_ref()?.override_config.as_ref()?;
1464
1465 let mut query_cursor = QueryCursorHandle::new();
1466 query_cursor.set_byte_range(offset..offset);
1467
1468 let mut smallest_match: Option<(u32, Range<usize>)> = None;
1469 for mat in query_cursor.matches(&config.query, self.node(), text) {
1470 for capture in mat.captures {
1471 if !config.values.contains_key(&capture.index) {
1472 continue;
1473 }
1474
1475 let range = capture.node.byte_range();
1476 if offset <= range.start || offset >= range.end {
1477 continue;
1478 }
1479
1480 if let Some((_, smallest_range)) = &smallest_match {
1481 if range.len() < smallest_range.len() {
1482 smallest_match = Some((capture.index, range))
1483 }
1484 continue;
1485 }
1486
1487 smallest_match = Some((capture.index, range));
1488 }
1489 }
1490
1491 smallest_match.map(|(index, _)| index)
1492 }
1493}
1494
1495impl std::ops::Deref for SyntaxMap {
1496 type Target = SyntaxSnapshot;
1497
1498 fn deref(&self) -> &Self::Target {
1499 &self.snapshot
1500 }
1501}
1502
1503impl PartialEq for ParseStep {
1504 fn eq(&self, _: &Self) -> bool {
1505 false
1506 }
1507}
1508
1509impl Eq for ParseStep {}
1510
1511impl PartialOrd for ParseStep {
1512 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1513 Some(self.cmp(&other))
1514 }
1515}
1516
1517impl Ord for ParseStep {
1518 fn cmp(&self, other: &Self) -> Ordering {
1519 let range_a = self.range();
1520 let range_b = other.range();
1521 Ord::cmp(&other.depth, &self.depth)
1522 .then_with(|| Ord::cmp(&range_b.start, &range_a.start))
1523 .then_with(|| Ord::cmp(&range_a.end, &range_b.end))
1524 .then_with(|| self.language.id().cmp(&other.language.id()))
1525 }
1526}
1527
1528impl ParseStep {
1529 fn range(&self) -> Range<usize> {
1530 if let ParseMode::Combined {
1531 parent_layer_range, ..
1532 } = &self.mode
1533 {
1534 parent_layer_range.clone()
1535 } else {
1536 let start = self.included_ranges.first().map_or(0, |r| r.start_byte);
1537 let end = self.included_ranges.last().map_or(0, |r| r.end_byte);
1538 start..end
1539 }
1540 }
1541}
1542
1543impl ChangedRegion {
1544 fn cmp(&self, other: &Self, buffer: &BufferSnapshot) -> Ordering {
1545 let range_a = &self.range;
1546 let range_b = &other.range;
1547 Ord::cmp(&self.depth, &other.depth)
1548 .then_with(|| range_a.start.cmp(&range_b.start, buffer))
1549 .then_with(|| range_b.end.cmp(&range_a.end, buffer))
1550 }
1551}
1552
1553impl ChangeRegionSet {
1554 fn start_position(&self) -> ChangeStartPosition {
1555 self.0.first().map_or(
1556 ChangeStartPosition {
1557 depth: usize::MAX,
1558 position: Anchor::MAX,
1559 },
1560 |region| ChangeStartPosition {
1561 depth: region.depth,
1562 position: region.range.start,
1563 },
1564 )
1565 }
1566
1567 fn intersects(&self, layer: &SyntaxLayer, text: &BufferSnapshot) -> bool {
1568 for region in &self.0 {
1569 if region.depth < layer.depth {
1570 continue;
1571 }
1572 if region.depth > layer.depth {
1573 break;
1574 }
1575 if region.range.end.cmp(&layer.range.start, text).is_le() {
1576 continue;
1577 }
1578 if region.range.start.cmp(&layer.range.end, text).is_ge() {
1579 break;
1580 }
1581 return true;
1582 }
1583 false
1584 }
1585
1586 fn insert(&mut self, region: ChangedRegion, text: &BufferSnapshot) {
1587 if let Err(ix) = self.0.binary_search_by(|probe| probe.cmp(®ion, text)) {
1588 self.0.insert(ix, region);
1589 }
1590 }
1591
1592 fn prune(&mut self, summary: SyntaxLayerSummary, text: &BufferSnapshot) -> bool {
1593 let prev_len = self.0.len();
1594 self.0.retain(|region| {
1595 region.depth > summary.max_depth
1596 || (region.depth == summary.max_depth
1597 && region
1598 .range
1599 .end
1600 .cmp(&summary.last_layer_range.start, text)
1601 .is_gt())
1602 });
1603 self.0.len() < prev_len
1604 }
1605}
1606
1607impl Default for SyntaxLayerSummary {
1608 fn default() -> Self {
1609 Self {
1610 max_depth: 0,
1611 min_depth: 0,
1612 range: Anchor::MAX..Anchor::MIN,
1613 last_layer_range: Anchor::MIN..Anchor::MAX,
1614 last_layer_language: None,
1615 contains_unknown_injections: false,
1616 }
1617 }
1618}
1619
1620impl sum_tree::Summary for SyntaxLayerSummary {
1621 type Context = BufferSnapshot;
1622
1623 fn add_summary(&mut self, other: &Self, buffer: &Self::Context) {
1624 if other.max_depth > self.max_depth {
1625 self.max_depth = other.max_depth;
1626 self.range = other.range.clone();
1627 } else {
1628 if self.range == (Anchor::MAX..Anchor::MAX) {
1629 self.range.start = other.range.start;
1630 }
1631 if other.range.end.cmp(&self.range.end, buffer).is_gt() {
1632 self.range.end = other.range.end;
1633 }
1634 }
1635 self.last_layer_range = other.last_layer_range.clone();
1636 self.last_layer_language = other.last_layer_language;
1637 self.contains_unknown_injections |= other.contains_unknown_injections;
1638 }
1639}
1640
1641impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary> for SyntaxLayerPosition {
1642 fn cmp(&self, cursor_location: &SyntaxLayerSummary, buffer: &BufferSnapshot) -> Ordering {
1643 Ord::cmp(&self.depth, &cursor_location.max_depth)
1644 .then_with(|| {
1645 self.range
1646 .start
1647 .cmp(&cursor_location.last_layer_range.start, buffer)
1648 })
1649 .then_with(|| {
1650 cursor_location
1651 .last_layer_range
1652 .end
1653 .cmp(&self.range.end, buffer)
1654 })
1655 .then_with(|| self.language.cmp(&cursor_location.last_layer_language))
1656 }
1657}
1658
1659impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary> for ChangeStartPosition {
1660 fn cmp(&self, cursor_location: &SyntaxLayerSummary, text: &BufferSnapshot) -> Ordering {
1661 Ord::cmp(&self.depth, &cursor_location.max_depth)
1662 .then_with(|| self.position.cmp(&cursor_location.range.end, text))
1663 }
1664}
1665
1666impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary>
1667 for SyntaxLayerPositionBeforeChange
1668{
1669 fn cmp(&self, cursor_location: &SyntaxLayerSummary, buffer: &BufferSnapshot) -> Ordering {
1670 if self.change.cmp(cursor_location, buffer).is_le() {
1671 return Ordering::Less;
1672 } else {
1673 self.position.cmp(cursor_location, buffer)
1674 }
1675 }
1676}
1677
1678impl sum_tree::Item for SyntaxLayer {
1679 type Summary = SyntaxLayerSummary;
1680
1681 fn summary(&self) -> Self::Summary {
1682 SyntaxLayerSummary {
1683 min_depth: self.depth,
1684 max_depth: self.depth,
1685 range: self.range.clone(),
1686 last_layer_range: self.range.clone(),
1687 last_layer_language: self.content.language_id(),
1688 contains_unknown_injections: matches!(self.content, SyntaxLayerContent::Pending { .. }),
1689 }
1690 }
1691}
1692
1693impl std::fmt::Debug for SyntaxLayer {
1694 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1695 f.debug_struct("SyntaxLayer")
1696 .field("depth", &self.depth)
1697 .field("range", &self.range)
1698 .field("tree", &self.content.tree())
1699 .finish()
1700 }
1701}
1702
1703impl<'a> tree_sitter::TextProvider<&'a [u8]> for TextProvider<'a> {
1704 type I = ByteChunks<'a>;
1705
1706 fn text(&mut self, node: tree_sitter::Node) -> Self::I {
1707 ByteChunks(self.0.chunks_in_range(node.byte_range()))
1708 }
1709}
1710
1711impl<'a> Iterator for ByteChunks<'a> {
1712 type Item = &'a [u8];
1713
1714 fn next(&mut self) -> Option<Self::Item> {
1715 self.0.next().map(str::as_bytes)
1716 }
1717}
1718
1719impl QueryCursorHandle {
1720 pub(crate) fn new() -> Self {
1721 let mut cursor = QUERY_CURSORS.lock().pop().unwrap_or_else(QueryCursor::new);
1722 cursor.set_match_limit(64);
1723 QueryCursorHandle(Some(cursor))
1724 }
1725}
1726
1727impl Deref for QueryCursorHandle {
1728 type Target = QueryCursor;
1729
1730 fn deref(&self) -> &Self::Target {
1731 self.0.as_ref().unwrap()
1732 }
1733}
1734
1735impl DerefMut for QueryCursorHandle {
1736 fn deref_mut(&mut self) -> &mut Self::Target {
1737 self.0.as_mut().unwrap()
1738 }
1739}
1740
1741impl Drop for QueryCursorHandle {
1742 fn drop(&mut self) {
1743 let mut cursor = self.0.take().unwrap();
1744 cursor.set_byte_range(0..usize::MAX);
1745 cursor.set_point_range(Point::zero().to_ts_point()..Point::MAX.to_ts_point());
1746 QUERY_CURSORS.lock().push(cursor)
1747 }
1748}
1749
1750pub(crate) trait ToTreeSitterPoint {
1751 fn to_ts_point(self) -> tree_sitter::Point;
1752 fn from_ts_point(point: tree_sitter::Point) -> Self;
1753}
1754
1755impl ToTreeSitterPoint for Point {
1756 fn to_ts_point(self) -> tree_sitter::Point {
1757 tree_sitter::Point::new(self.row as usize, self.column as usize)
1758 }
1759
1760 fn from_ts_point(point: tree_sitter::Point) -> Self {
1761 Point::new(point.row as u32, point.column as u32)
1762 }
1763}
1764
1765struct LogIncludedRanges<'a>(&'a [tree_sitter::Range]);
1766struct LogPoint(Point);
1767struct LogAnchorRange<'a>(&'a Range<Anchor>, &'a text::BufferSnapshot);
1768struct LogChangedRegions<'a>(&'a ChangeRegionSet, &'a text::BufferSnapshot);
1769
1770impl<'a> fmt::Debug for LogIncludedRanges<'a> {
1771 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1772 f.debug_list()
1773 .entries(self.0.iter().map(|range| {
1774 let start = range.start_point;
1775 let end = range.end_point;
1776 (start.row, start.column)..(end.row, end.column)
1777 }))
1778 .finish()
1779 }
1780}
1781
1782impl<'a> fmt::Debug for LogAnchorRange<'a> {
1783 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1784 let range = self.0.to_point(self.1);
1785 (LogPoint(range.start)..LogPoint(range.end)).fmt(f)
1786 }
1787}
1788
1789impl<'a> fmt::Debug for LogChangedRegions<'a> {
1790 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1791 f.debug_list()
1792 .entries(
1793 self.0
1794 .0
1795 .iter()
1796 .map(|region| LogAnchorRange(®ion.range, self.1)),
1797 )
1798 .finish()
1799 }
1800}
1801
1802impl fmt::Debug for LogPoint {
1803 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1804 (self.0.row, self.0.column).fmt(f)
1805 }
1806}