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