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