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