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