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