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