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