1use crate::{Grammar, InjectionConfig, Language, LanguageRegistry};
   2use collections::HashMap;
   3use lazy_static::lazy_static;
   4use parking_lot::Mutex;
   5use std::{
   6    borrow::Cow,
   7    cell::RefCell,
   8    cmp::{Ordering, Reverse},
   9    collections::BinaryHeap,
  10    ops::{Deref, DerefMut, Range},
  11    sync::Arc,
  12};
  13use sum_tree::{Bias, SeekTarget, SumTree};
  14use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point, Rope, ToOffset, ToPoint};
  15use tree_sitter::{
  16    Node, Parser, Query, QueryCapture, QueryCaptures, QueryCursor, QueryMatches, Tree,
  17};
  18
  19thread_local! {
  20    static PARSER: RefCell<Parser> = RefCell::new(Parser::new());
  21}
  22
  23lazy_static! {
  24    static ref QUERY_CURSORS: Mutex<Vec<QueryCursor>> = Default::default();
  25}
  26
  27#[derive(Default)]
  28pub struct SyntaxMap {
  29    parsed_version: clock::Global,
  30    interpolated_version: clock::Global,
  31    snapshot: SyntaxSnapshot,
  32    language_registry: Option<Arc<LanguageRegistry>>,
  33}
  34
  35#[derive(Clone, Default)]
  36pub struct SyntaxSnapshot {
  37    layers: SumTree<SyntaxLayer>,
  38}
  39
  40#[derive(Default)]
  41pub struct SyntaxMapCaptures<'a> {
  42    layers: Vec<SyntaxMapCapturesLayer<'a>>,
  43    active_layer_count: usize,
  44    grammars: Vec<&'a Grammar>,
  45}
  46
  47#[derive(Default)]
  48pub struct SyntaxMapMatches<'a> {
  49    layers: Vec<SyntaxMapMatchesLayer<'a>>,
  50    active_layer_count: usize,
  51    grammars: Vec<&'a Grammar>,
  52}
  53
  54#[derive(Debug)]
  55pub struct SyntaxMapCapture<'a> {
  56    pub depth: usize,
  57    pub node: Node<'a>,
  58    pub index: u32,
  59    pub grammar_index: usize,
  60}
  61
  62#[derive(Debug)]
  63pub struct SyntaxMapMatch<'a> {
  64    pub depth: usize,
  65    pub pattern_index: usize,
  66    pub captures: &'a [QueryCapture<'a>],
  67    pub grammar_index: usize,
  68}
  69
  70struct SyntaxMapCapturesLayer<'a> {
  71    depth: usize,
  72    captures: QueryCaptures<'a, 'a, TextProvider<'a>>,
  73    next_capture: Option<QueryCapture<'a>>,
  74    grammar_index: usize,
  75    _query_cursor: QueryCursorHandle,
  76}
  77
  78struct SyntaxMapMatchesLayer<'a> {
  79    depth: usize,
  80    next_pattern_index: usize,
  81    next_captures: Vec<QueryCapture<'a>>,
  82    has_next: bool,
  83    matches: QueryMatches<'a, 'a, TextProvider<'a>>,
  84    grammar_index: usize,
  85    _query_cursor: QueryCursorHandle,
  86}
  87
  88#[derive(Clone)]
  89struct SyntaxLayer {
  90    depth: usize,
  91    range: Range<Anchor>,
  92    tree: tree_sitter::Tree,
  93    language: Arc<Language>,
  94}
  95
  96#[derive(Debug)]
  97pub struct SyntaxLayerInfo<'a> {
  98    pub depth: usize,
  99    pub node: Node<'a>,
 100    pub language: &'a Arc<Language>,
 101}
 102
 103#[derive(Debug, Clone)]
 104struct SyntaxLayerSummary {
 105    min_depth: usize,
 106    max_depth: usize,
 107    range: Range<Anchor>,
 108    last_layer_range: Range<Anchor>,
 109    last_layer_language: Option<usize>,
 110}
 111
 112#[derive(Clone, Debug)]
 113struct SyntaxLayerPosition {
 114    depth: usize,
 115    range: Range<Anchor>,
 116    language: Option<usize>,
 117}
 118
 119#[derive(Clone, Debug)]
 120struct ChangeStartPosition {
 121    depth: usize,
 122    position: Anchor,
 123}
 124
 125#[derive(Clone, Debug)]
 126struct SyntaxLayerPositionBeforeChange {
 127    position: SyntaxLayerPosition,
 128    change: ChangeStartPosition,
 129}
 130
 131struct ParseStep {
 132    depth: usize,
 133    language: Arc<Language>,
 134    range: Range<Anchor>,
 135    included_ranges: Vec<tree_sitter::Range>,
 136    mode: ParseMode,
 137}
 138
 139enum ParseMode {
 140    Single,
 141    Combined {
 142        parent_layer_range: Range<usize>,
 143        parent_layer_changed_ranges: Vec<Range<usize>>,
 144    },
 145}
 146
 147#[derive(Debug, PartialEq, Eq)]
 148struct ChangedRegion {
 149    depth: usize,
 150    range: Range<Anchor>,
 151}
 152
 153#[derive(Default)]
 154struct ChangeRegionSet(Vec<ChangedRegion>);
 155
 156struct TextProvider<'a>(&'a Rope);
 157
 158struct ByteChunks<'a>(text::Chunks<'a>);
 159
 160struct QueryCursorHandle(Option<QueryCursor>);
 161
 162impl SyntaxMap {
 163    pub fn new() -> Self {
 164        Self::default()
 165    }
 166
 167    pub fn set_language_registry(&mut self, registry: Arc<LanguageRegistry>) {
 168        self.language_registry = Some(registry);
 169    }
 170
 171    pub fn snapshot(&self) -> SyntaxSnapshot {
 172        self.snapshot.clone()
 173    }
 174
 175    pub fn language_registry(&self) -> Option<Arc<LanguageRegistry>> {
 176        self.language_registry.clone()
 177    }
 178
 179    pub fn parsed_version(&self) -> clock::Global {
 180        self.parsed_version.clone()
 181    }
 182
 183    pub fn interpolate(&mut self, text: &BufferSnapshot) {
 184        self.snapshot.interpolate(&self.interpolated_version, text);
 185        self.interpolated_version = text.version.clone();
 186    }
 187
 188    #[cfg(test)]
 189    pub fn reparse(&mut self, language: Arc<Language>, text: &BufferSnapshot) {
 190        self.snapshot.reparse(
 191            &self.parsed_version,
 192            text,
 193            self.language_registry.clone(),
 194            language,
 195        );
 196        self.parsed_version = text.version.clone();
 197        self.interpolated_version = text.version.clone();
 198    }
 199
 200    pub fn did_parse(&mut self, snapshot: SyntaxSnapshot, version: clock::Global) {
 201        self.interpolated_version = version.clone();
 202        self.parsed_version = version;
 203        self.snapshot = snapshot;
 204    }
 205
 206    pub fn clear(&mut self) {
 207        self.snapshot = SyntaxSnapshot::default();
 208    }
 209}
 210
 211impl SyntaxSnapshot {
 212    pub fn is_empty(&self) -> bool {
 213        self.layers.is_empty()
 214    }
 215
 216    pub fn interpolate(&mut self, from_version: &clock::Global, text: &BufferSnapshot) {
 217        let edits = text
 218            .anchored_edits_since::<(usize, Point)>(&from_version)
 219            .collect::<Vec<_>>();
 220        if edits.is_empty() {
 221            return;
 222        }
 223
 224        let mut layers = SumTree::new();
 225        let mut first_edit_ix_for_depth = 0;
 226        let mut prev_depth = 0;
 227        let mut cursor = self.layers.cursor::<SyntaxLayerSummary>();
 228        cursor.next(text);
 229
 230        'outer: loop {
 231            let depth = cursor.end(text).max_depth;
 232            if depth > prev_depth {
 233                first_edit_ix_for_depth = 0;
 234                prev_depth = depth;
 235            }
 236
 237            // Preserve any layers at this depth that precede the first edit.
 238            if let Some((_, edit_range)) = edits.get(first_edit_ix_for_depth) {
 239                let target = ChangeStartPosition {
 240                    depth,
 241                    position: edit_range.start,
 242                };
 243                if target.cmp(&cursor.start(), text).is_gt() {
 244                    let slice = cursor.slice(&target, Bias::Left, text);
 245                    layers.push_tree(slice, text);
 246                }
 247            }
 248            // If this layer follows all of the edits, then preserve it and any
 249            // subsequent layers at this same depth.
 250            else if cursor.item().is_some() {
 251                let slice = cursor.slice(
 252                    &SyntaxLayerPosition {
 253                        depth: depth + 1,
 254                        range: Anchor::MIN..Anchor::MAX,
 255                        language: None,
 256                    },
 257                    Bias::Left,
 258                    text,
 259                );
 260                layers.push_tree(slice, text);
 261                continue;
 262            };
 263
 264            let Some(layer) = cursor.item() else { break };
 265            let (start_byte, start_point) = layer.range.start.summary::<(usize, Point)>(text);
 266
 267            // Ignore edits that end before the start of this layer, and don't consider them
 268            // for any subsequent layers at this same depth.
 269            loop {
 270                let Some((_, edit_range)) = edits.get(first_edit_ix_for_depth) else { continue 'outer };
 271                if edit_range.end.cmp(&layer.range.start, text).is_le() {
 272                    first_edit_ix_for_depth += 1;
 273                } else {
 274                    break;
 275                }
 276            }
 277
 278            let mut layer = layer.clone();
 279            for (edit, edit_range) in &edits[first_edit_ix_for_depth..] {
 280                // Ignore any edits that follow this layer.
 281                if edit_range.start.cmp(&layer.range.end, text).is_ge() {
 282                    break;
 283                }
 284
 285                // Apply any edits that intersect this layer to the layer's syntax tree.
 286                let tree_edit = if edit_range.start.cmp(&layer.range.start, text).is_ge() {
 287                    tree_sitter::InputEdit {
 288                        start_byte: edit.new.start.0 - start_byte,
 289                        old_end_byte: edit.new.start.0 - start_byte
 290                            + (edit.old.end.0 - edit.old.start.0),
 291                        new_end_byte: edit.new.end.0 - start_byte,
 292                        start_position: (edit.new.start.1 - start_point).to_ts_point(),
 293                        old_end_position: (edit.new.start.1 - start_point
 294                            + (edit.old.end.1 - edit.old.start.1))
 295                            .to_ts_point(),
 296                        new_end_position: (edit.new.end.1 - start_point).to_ts_point(),
 297                    }
 298                } else {
 299                    let node = layer.tree.root_node();
 300                    tree_sitter::InputEdit {
 301                        start_byte: 0,
 302                        old_end_byte: node.end_byte(),
 303                        new_end_byte: 0,
 304                        start_position: Default::default(),
 305                        old_end_position: node.end_position(),
 306                        new_end_position: Default::default(),
 307                    }
 308                };
 309
 310                layer.tree.edit(&tree_edit);
 311            }
 312
 313            debug_assert!(
 314                layer.tree.root_node().end_byte() <= text.len(),
 315                "tree's size {}, is larger than text size {}",
 316                layer.tree.root_node().end_byte(),
 317                text.len(),
 318            );
 319
 320            layers.push(layer, text);
 321            cursor.next(text);
 322        }
 323
 324        layers.push_tree(cursor.suffix(&text), &text);
 325        drop(cursor);
 326        self.layers = layers;
 327    }
 328
 329    pub fn reparse(
 330        &mut self,
 331        from_version: &clock::Global,
 332        text: &BufferSnapshot,
 333        registry: Option<Arc<LanguageRegistry>>,
 334        root_language: Arc<Language>,
 335    ) {
 336        let edits = text.edits_since::<usize>(from_version).collect::<Vec<_>>();
 337        let max_depth = self.layers.summary().max_depth;
 338        let mut cursor = self.layers.cursor::<SyntaxLayerSummary>();
 339        cursor.next(&text);
 340        let mut layers = SumTree::new();
 341
 342        let mut changed_regions = ChangeRegionSet::default();
 343        let mut queue = BinaryHeap::new();
 344        let mut combined_injection_ranges = HashMap::default();
 345        queue.push(ParseStep {
 346            depth: 0,
 347            language: root_language.clone(),
 348            included_ranges: vec![tree_sitter::Range {
 349                start_byte: 0,
 350                end_byte: text.len(),
 351                start_point: Point::zero().to_ts_point(),
 352                end_point: text.max_point().to_ts_point(),
 353            }],
 354            range: Anchor::MIN..Anchor::MAX,
 355            mode: ParseMode::Single,
 356        });
 357
 358        loop {
 359            let step = queue.pop();
 360            let position = if let Some(step) = &step {
 361                SyntaxLayerPosition {
 362                    depth: step.depth,
 363                    range: step.range.clone(),
 364                    language: step.language.id(),
 365                }
 366            } else {
 367                SyntaxLayerPosition {
 368                    depth: max_depth + 1,
 369                    range: Anchor::MAX..Anchor::MAX,
 370                    language: None,
 371                }
 372            };
 373
 374            let mut done = cursor.item().is_none();
 375            while !done && position.cmp(&cursor.end(text), &text).is_gt() {
 376                done = true;
 377
 378                let bounded_position = SyntaxLayerPositionBeforeChange {
 379                    position: position.clone(),
 380                    change: changed_regions.start_position(),
 381                };
 382                if bounded_position.cmp(&cursor.start(), &text).is_gt() {
 383                    let slice = cursor.slice(&bounded_position, Bias::Left, text);
 384                    if !slice.is_empty() {
 385                        layers.push_tree(slice, &text);
 386                        if changed_regions.prune(cursor.end(text), text) {
 387                            done = false;
 388                        }
 389                    }
 390                }
 391
 392                while position.cmp(&cursor.end(text), text).is_gt() {
 393                    let Some(layer) = cursor.item() else { break };
 394
 395                    if changed_regions.intersects(&layer, text) {
 396                        changed_regions.insert(
 397                            ChangedRegion {
 398                                depth: layer.depth + 1,
 399                                range: layer.range.clone(),
 400                            },
 401                            text,
 402                        );
 403                    } else {
 404                        layers.push(layer.clone(), text);
 405                    }
 406
 407                    cursor.next(text);
 408                    if changed_regions.prune(cursor.end(text), text) {
 409                        done = false;
 410                    }
 411                }
 412            }
 413
 414            let Some(step) = step else { break };
 415            let (step_start_byte, step_start_point) =
 416                step.range.start.summary::<(usize, Point)>(text);
 417            let step_end_byte = step.range.end.to_offset(text);
 418            let Some(grammar) = step.language.grammar.as_deref() else { continue };
 419
 420            let mut old_layer = cursor.item();
 421            if let Some(layer) = old_layer {
 422                if layer.range.to_offset(text) == (step_start_byte..step_end_byte)
 423                    && layer.language.id() == step.language.id()
 424                {
 425                    cursor.next(&text);
 426                } else {
 427                    old_layer = None;
 428                }
 429            }
 430
 431            let tree;
 432            let changed_ranges;
 433            let mut included_ranges = step.included_ranges;
 434            if let Some(old_layer) = old_layer {
 435                if let ParseMode::Combined {
 436                    parent_layer_changed_ranges,
 437                    ..
 438                } = step.mode
 439                {
 440                    included_ranges = splice_included_ranges(
 441                        old_layer.tree.included_ranges(),
 442                        &parent_layer_changed_ranges,
 443                        &included_ranges,
 444                    );
 445                }
 446
 447                tree = parse_text(
 448                    grammar,
 449                    text.as_rope(),
 450                    step_start_byte,
 451                    step_start_point,
 452                    included_ranges,
 453                    Some(old_layer.tree.clone()),
 454                );
 455                changed_ranges = join_ranges(
 456                    edits.iter().map(|e| e.new.clone()).filter(|range| {
 457                        range.start <= step_end_byte && range.end >= step_start_byte
 458                    }),
 459                    old_layer
 460                        .tree
 461                        .changed_ranges(&tree)
 462                        .map(|r| step_start_byte + r.start_byte..step_start_byte + r.end_byte),
 463                );
 464            } else {
 465                tree = parse_text(
 466                    grammar,
 467                    text.as_rope(),
 468                    step_start_byte,
 469                    step_start_point,
 470                    included_ranges,
 471                    None,
 472                );
 473                changed_ranges = vec![step_start_byte..step_end_byte];
 474            }
 475
 476            layers.push(
 477                SyntaxLayer {
 478                    depth: step.depth,
 479                    range: step.range,
 480                    tree: tree.clone(),
 481                    language: step.language.clone(),
 482                },
 483                &text,
 484            );
 485
 486            if let (Some((config, registry)), false) = (
 487                grammar.injection_config.as_ref().zip(registry.as_ref()),
 488                changed_ranges.is_empty(),
 489            ) {
 490                for range in &changed_ranges {
 491                    changed_regions.insert(
 492                        ChangedRegion {
 493                            depth: step.depth + 1,
 494                            range: text.anchor_before(range.start)..text.anchor_after(range.end),
 495                        },
 496                        text,
 497                    );
 498                }
 499                get_injections(
 500                    config,
 501                    text,
 502                    tree.root_node_with_offset(step_start_byte, step_start_point.to_ts_point()),
 503                    registry,
 504                    step.depth + 1,
 505                    &changed_ranges,
 506                    &mut combined_injection_ranges,
 507                    &mut queue,
 508                );
 509            }
 510        }
 511
 512        drop(cursor);
 513        self.layers = layers;
 514    }
 515
 516    pub fn single_tree_captures<'a>(
 517        range: Range<usize>,
 518        text: &'a Rope,
 519        tree: &'a Tree,
 520        language: &'a Arc<Language>,
 521        query: fn(&Grammar) -> Option<&Query>,
 522    ) -> SyntaxMapCaptures<'a> {
 523        SyntaxMapCaptures::new(
 524            range.clone(),
 525            text,
 526            [SyntaxLayerInfo {
 527                language,
 528                depth: 0,
 529                node: tree.root_node(),
 530            }]
 531            .into_iter(),
 532            query,
 533        )
 534    }
 535
 536    pub fn captures<'a>(
 537        &'a self,
 538        range: Range<usize>,
 539        buffer: &'a BufferSnapshot,
 540        query: fn(&Grammar) -> Option<&Query>,
 541    ) -> SyntaxMapCaptures {
 542        SyntaxMapCaptures::new(
 543            range.clone(),
 544            buffer.as_rope(),
 545            self.layers_for_range(range, buffer).into_iter(),
 546            query,
 547        )
 548    }
 549
 550    pub fn matches<'a>(
 551        &'a self,
 552        range: Range<usize>,
 553        buffer: &'a BufferSnapshot,
 554        query: fn(&Grammar) -> Option<&Query>,
 555    ) -> SyntaxMapMatches {
 556        SyntaxMapMatches::new(
 557            range.clone(),
 558            buffer.as_rope(),
 559            self.layers_for_range(range, buffer).into_iter(),
 560            query,
 561        )
 562    }
 563
 564    #[cfg(test)]
 565    pub fn layers<'a>(&'a self, buffer: &'a BufferSnapshot) -> Vec<SyntaxLayerInfo> {
 566        self.layers_for_range(0..buffer.len(), buffer).collect()
 567    }
 568
 569    pub fn layers_for_range<'a, T: ToOffset>(
 570        &'a self,
 571        range: Range<T>,
 572        buffer: &'a BufferSnapshot,
 573    ) -> impl 'a + Iterator<Item = SyntaxLayerInfo> {
 574        let start = buffer.anchor_before(range.start.to_offset(buffer));
 575        let end = buffer.anchor_after(range.end.to_offset(buffer));
 576
 577        let mut cursor = self.layers.filter::<_, ()>(move |summary| {
 578            if summary.max_depth > summary.min_depth {
 579                true
 580            } else {
 581                let is_before_start = summary.range.end.cmp(&start, buffer).is_lt();
 582                let is_after_end = summary.range.start.cmp(&end, buffer).is_gt();
 583                !is_before_start && !is_after_end
 584            }
 585        });
 586
 587        cursor.next(buffer);
 588        std::iter::from_fn(move || {
 589            if let Some(layer) = cursor.item() {
 590                let info = SyntaxLayerInfo {
 591                    language: &layer.language,
 592                    depth: layer.depth,
 593                    node: layer.tree.root_node_with_offset(
 594                        layer.range.start.to_offset(buffer),
 595                        layer.range.start.to_point(buffer).to_ts_point(),
 596                    ),
 597                };
 598                cursor.next(buffer);
 599                Some(info)
 600            } else {
 601                None
 602            }
 603        })
 604    }
 605}
 606
 607impl<'a> SyntaxMapCaptures<'a> {
 608    fn new(
 609        range: Range<usize>,
 610        text: &'a Rope,
 611        layers: impl Iterator<Item = SyntaxLayerInfo<'a>>,
 612        query: fn(&Grammar) -> Option<&Query>,
 613    ) -> Self {
 614        let mut result = Self {
 615            layers: Vec::new(),
 616            grammars: Vec::new(),
 617            active_layer_count: 0,
 618        };
 619        for SyntaxLayerInfo {
 620            language,
 621            depth,
 622            node,
 623        } in layers
 624        {
 625            let grammar = match &language.grammar {
 626                Some(grammer) => grammer,
 627                None => continue,
 628            };
 629            let query = match query(&grammar) {
 630                Some(query) => query,
 631                None => continue,
 632            };
 633
 634            let mut query_cursor = QueryCursorHandle::new();
 635
 636            // TODO - add a Tree-sitter API to remove the need for this.
 637            let cursor = unsafe {
 638                std::mem::transmute::<_, &'static mut QueryCursor>(query_cursor.deref_mut())
 639            };
 640
 641            cursor.set_byte_range(range.clone());
 642            let captures = cursor.captures(query, node, TextProvider(text));
 643            let grammar_index = result
 644                .grammars
 645                .iter()
 646                .position(|g| g.id == grammar.id())
 647                .unwrap_or_else(|| {
 648                    result.grammars.push(grammar);
 649                    result.grammars.len() - 1
 650                });
 651            let mut layer = SyntaxMapCapturesLayer {
 652                depth,
 653                grammar_index,
 654                next_capture: None,
 655                captures,
 656                _query_cursor: query_cursor,
 657            };
 658
 659            layer.advance();
 660            if layer.next_capture.is_some() {
 661                let key = layer.sort_key();
 662                let ix = match result.layers[..result.active_layer_count]
 663                    .binary_search_by_key(&key, |layer| layer.sort_key())
 664                {
 665                    Ok(ix) | Err(ix) => ix,
 666                };
 667                result.layers.insert(ix, layer);
 668                result.active_layer_count += 1;
 669            } else {
 670                result.layers.push(layer);
 671            }
 672        }
 673
 674        result
 675    }
 676
 677    pub fn grammars(&self) -> &[&'a Grammar] {
 678        &self.grammars
 679    }
 680
 681    pub fn peek(&self) -> Option<SyntaxMapCapture<'a>> {
 682        let layer = self.layers[..self.active_layer_count].first()?;
 683        let capture = layer.next_capture?;
 684        Some(SyntaxMapCapture {
 685            depth: layer.depth,
 686            grammar_index: layer.grammar_index,
 687            index: capture.index,
 688            node: capture.node,
 689        })
 690    }
 691
 692    pub fn advance(&mut self) -> bool {
 693        let layer = if let Some(layer) = self.layers[..self.active_layer_count].first_mut() {
 694            layer
 695        } else {
 696            return false;
 697        };
 698
 699        layer.advance();
 700        if layer.next_capture.is_some() {
 701            let key = layer.sort_key();
 702            let i = 1 + self.layers[1..self.active_layer_count]
 703                .iter()
 704                .position(|later_layer| key < later_layer.sort_key())
 705                .unwrap_or(self.active_layer_count - 1);
 706            self.layers[0..i].rotate_left(1);
 707        } else {
 708            self.layers[0..self.active_layer_count].rotate_left(1);
 709            self.active_layer_count -= 1;
 710        }
 711
 712        true
 713    }
 714
 715    pub fn set_byte_range(&mut self, range: Range<usize>) {
 716        for layer in &mut self.layers {
 717            layer.captures.set_byte_range(range.clone());
 718            if let Some(capture) = &layer.next_capture {
 719                if capture.node.end_byte() > range.start {
 720                    continue;
 721                }
 722            }
 723            layer.advance();
 724        }
 725        self.layers.sort_unstable_by_key(|layer| layer.sort_key());
 726        self.active_layer_count = self
 727            .layers
 728            .iter()
 729            .position(|layer| layer.next_capture.is_none())
 730            .unwrap_or(self.layers.len());
 731    }
 732}
 733
 734impl<'a> SyntaxMapMatches<'a> {
 735    fn new(
 736        range: Range<usize>,
 737        text: &'a Rope,
 738        layers: impl Iterator<Item = SyntaxLayerInfo<'a>>,
 739        query: fn(&Grammar) -> Option<&Query>,
 740    ) -> Self {
 741        let mut result = Self::default();
 742        for SyntaxLayerInfo {
 743            language,
 744            depth,
 745            node,
 746        } in layers
 747        {
 748            let grammar = match &language.grammar {
 749                Some(grammer) => grammer,
 750                None => continue,
 751            };
 752            let query = match query(&grammar) {
 753                Some(query) => query,
 754                None => continue,
 755            };
 756
 757            let mut query_cursor = QueryCursorHandle::new();
 758
 759            // TODO - add a Tree-sitter API to remove the need for this.
 760            let cursor = unsafe {
 761                std::mem::transmute::<_, &'static mut QueryCursor>(query_cursor.deref_mut())
 762            };
 763
 764            cursor.set_byte_range(range.clone());
 765            let matches = cursor.matches(query, node, TextProvider(text));
 766            let grammar_index = result
 767                .grammars
 768                .iter()
 769                .position(|g| g.id == grammar.id())
 770                .unwrap_or_else(|| {
 771                    result.grammars.push(grammar);
 772                    result.grammars.len() - 1
 773                });
 774            let mut layer = SyntaxMapMatchesLayer {
 775                depth,
 776                grammar_index,
 777                matches,
 778                next_pattern_index: 0,
 779                next_captures: Vec::new(),
 780                has_next: false,
 781                _query_cursor: query_cursor,
 782            };
 783
 784            layer.advance();
 785            if layer.has_next {
 786                let key = layer.sort_key();
 787                let ix = match result.layers[..result.active_layer_count]
 788                    .binary_search_by_key(&key, |layer| layer.sort_key())
 789                {
 790                    Ok(ix) | Err(ix) => ix,
 791                };
 792                result.layers.insert(ix, layer);
 793                result.active_layer_count += 1;
 794            } else {
 795                result.layers.push(layer);
 796            }
 797        }
 798        result
 799    }
 800
 801    pub fn grammars(&self) -> &[&'a Grammar] {
 802        &self.grammars
 803    }
 804
 805    pub fn peek(&self) -> Option<SyntaxMapMatch> {
 806        let layer = self.layers.first()?;
 807        if !layer.has_next {
 808            return None;
 809        }
 810        Some(SyntaxMapMatch {
 811            depth: layer.depth,
 812            grammar_index: layer.grammar_index,
 813            pattern_index: layer.next_pattern_index,
 814            captures: &layer.next_captures,
 815        })
 816    }
 817
 818    pub fn advance(&mut self) -> bool {
 819        let layer = if let Some(layer) = self.layers.first_mut() {
 820            layer
 821        } else {
 822            return false;
 823        };
 824
 825        layer.advance();
 826        if layer.has_next {
 827            let key = layer.sort_key();
 828            let i = 1 + self.layers[1..self.active_layer_count]
 829                .iter()
 830                .position(|later_layer| key < later_layer.sort_key())
 831                .unwrap_or(self.active_layer_count - 1);
 832            self.layers[0..i].rotate_left(1);
 833        } else {
 834            self.layers[0..self.active_layer_count].rotate_left(1);
 835            self.active_layer_count -= 1;
 836        }
 837
 838        true
 839    }
 840}
 841
 842impl<'a> SyntaxMapCapturesLayer<'a> {
 843    fn advance(&mut self) {
 844        self.next_capture = self.captures.next().map(|(mat, ix)| mat.captures[ix]);
 845    }
 846
 847    fn sort_key(&self) -> (usize, Reverse<usize>, usize) {
 848        if let Some(capture) = &self.next_capture {
 849            let range = capture.node.byte_range();
 850            (range.start, Reverse(range.end), self.depth)
 851        } else {
 852            (usize::MAX, Reverse(0), usize::MAX)
 853        }
 854    }
 855}
 856
 857impl<'a> SyntaxMapMatchesLayer<'a> {
 858    fn advance(&mut self) {
 859        if let Some(mat) = self.matches.next() {
 860            self.next_captures.clear();
 861            self.next_captures.extend_from_slice(&mat.captures);
 862            self.next_pattern_index = mat.pattern_index;
 863            self.has_next = true;
 864        } else {
 865            self.has_next = false;
 866        }
 867    }
 868
 869    fn sort_key(&self) -> (usize, Reverse<usize>, usize) {
 870        if self.has_next {
 871            let captures = &self.next_captures;
 872            if let Some((first, last)) = captures.first().zip(captures.last()) {
 873                return (
 874                    first.node.start_byte(),
 875                    Reverse(last.node.end_byte()),
 876                    self.depth,
 877                );
 878            }
 879        }
 880        (usize::MAX, Reverse(0), usize::MAX)
 881    }
 882}
 883
 884impl<'a> Iterator for SyntaxMapCaptures<'a> {
 885    type Item = SyntaxMapCapture<'a>;
 886
 887    fn next(&mut self) -> Option<Self::Item> {
 888        let result = self.peek();
 889        self.advance();
 890        result
 891    }
 892}
 893
 894fn join_ranges(
 895    a: impl Iterator<Item = Range<usize>>,
 896    b: impl Iterator<Item = Range<usize>>,
 897) -> Vec<Range<usize>> {
 898    let mut result = Vec::<Range<usize>>::new();
 899    let mut a = a.peekable();
 900    let mut b = b.peekable();
 901    loop {
 902        let range = match (a.peek(), b.peek()) {
 903            (Some(range_a), Some(range_b)) => {
 904                if range_a.start < range_b.start {
 905                    a.next().unwrap()
 906                } else {
 907                    b.next().unwrap()
 908                }
 909            }
 910            (None, Some(_)) => b.next().unwrap(),
 911            (Some(_), None) => a.next().unwrap(),
 912            (None, None) => break,
 913        };
 914
 915        if let Some(last) = result.last_mut() {
 916            if range.start <= last.end {
 917                last.end = last.end.max(range.end);
 918                continue;
 919            }
 920        }
 921        result.push(range);
 922    }
 923    result
 924}
 925
 926fn parse_text(
 927    grammar: &Grammar,
 928    text: &Rope,
 929    start_byte: usize,
 930    start_point: Point,
 931    mut ranges: Vec<tree_sitter::Range>,
 932    old_tree: Option<Tree>,
 933) -> Tree {
 934    for range in &mut ranges {
 935        range.start_byte -= start_byte;
 936        range.end_byte -= start_byte;
 937        range.start_point = (Point::from_ts_point(range.start_point) - start_point).to_ts_point();
 938        range.end_point = (Point::from_ts_point(range.end_point) - start_point).to_ts_point();
 939    }
 940
 941    PARSER.with(|parser| {
 942        let mut parser = parser.borrow_mut();
 943        let mut chunks = text.chunks_in_range(start_byte..text.len());
 944        parser
 945            .set_included_ranges(&ranges)
 946            .expect("overlapping ranges");
 947        parser
 948            .set_language(grammar.ts_language)
 949            .expect("incompatible grammar");
 950        parser
 951            .parse_with(
 952                &mut move |offset, _| {
 953                    chunks.seek(start_byte + offset);
 954                    chunks.next().unwrap_or("").as_bytes()
 955                },
 956                old_tree.as_ref(),
 957            )
 958            .expect("invalid language")
 959    })
 960}
 961
 962fn get_injections(
 963    config: &InjectionConfig,
 964    text: &BufferSnapshot,
 965    node: Node,
 966    language_registry: &LanguageRegistry,
 967    depth: usize,
 968    changed_ranges: &[Range<usize>],
 969    combined_injection_ranges: &mut HashMap<Arc<Language>, Vec<tree_sitter::Range>>,
 970    queue: &mut BinaryHeap<ParseStep>,
 971) -> bool {
 972    let mut result = false;
 973    let mut query_cursor = QueryCursorHandle::new();
 974    let mut prev_match = None;
 975
 976    combined_injection_ranges.clear();
 977    for pattern in &config.patterns {
 978        if let (Some(language_name), true) = (pattern.language.as_ref(), pattern.combined) {
 979            if let Some(language) = language_registry.language_for_name(language_name) {
 980                combined_injection_ranges.insert(language, Vec::new());
 981            }
 982        }
 983    }
 984
 985    for query_range in changed_ranges {
 986        query_cursor.set_byte_range(query_range.start.saturating_sub(1)..query_range.end + 1);
 987        for mat in query_cursor.matches(&config.query, node, TextProvider(text.as_rope())) {
 988            let content_ranges = mat
 989                .nodes_for_capture_index(config.content_capture_ix)
 990                .map(|node| node.range())
 991                .collect::<Vec<_>>();
 992            if content_ranges.is_empty() {
 993                continue;
 994            }
 995
 996            // Avoid duplicate matches if two changed ranges intersect the same injection.
 997            let content_range =
 998                content_ranges.first().unwrap().start_byte..content_ranges.last().unwrap().end_byte;
 999            if let Some((last_pattern_ix, last_range)) = &prev_match {
1000                if mat.pattern_index == *last_pattern_ix && content_range == *last_range {
1001                    continue;
1002                }
1003            }
1004            prev_match = Some((mat.pattern_index, content_range.clone()));
1005
1006            let combined = config.patterns[mat.pattern_index].combined;
1007            let language_name = config.patterns[mat.pattern_index]
1008                .language
1009                .as_ref()
1010                .map(|s| Cow::Borrowed(s.as_ref()))
1011                .or_else(|| {
1012                    let ix = config.language_capture_ix?;
1013                    let node = mat.nodes_for_capture_index(ix).next()?;
1014                    Some(Cow::Owned(text.text_for_range(node.byte_range()).collect()))
1015                });
1016
1017            if let Some(language_name) = language_name {
1018                if let Some(language) = language_registry.language_for_name(language_name.as_ref())
1019                {
1020                    result = true;
1021                    let range = text.anchor_before(content_range.start)
1022                        ..text.anchor_after(content_range.end);
1023                    if combined {
1024                        combined_injection_ranges
1025                            .get_mut(&language.clone())
1026                            .unwrap()
1027                            .extend(content_ranges);
1028                    } else {
1029                        queue.push(ParseStep {
1030                            depth,
1031                            language,
1032                            included_ranges: content_ranges,
1033                            range,
1034                            mode: ParseMode::Single,
1035                        });
1036                    }
1037                }
1038            }
1039        }
1040    }
1041
1042    for (language, mut included_ranges) in combined_injection_ranges.drain() {
1043        included_ranges.sort_unstable();
1044        let range = text.anchor_before(node.start_byte())..text.anchor_after(node.end_byte());
1045        queue.push(ParseStep {
1046            depth,
1047            language,
1048            range,
1049            included_ranges,
1050            mode: ParseMode::Combined {
1051                parent_layer_range: node.start_byte()..node.end_byte(),
1052                parent_layer_changed_ranges: changed_ranges.to_vec(),
1053            },
1054        })
1055    }
1056
1057    result
1058}
1059
1060fn splice_included_ranges(
1061    mut ranges: Vec<tree_sitter::Range>,
1062    changed_ranges: &[Range<usize>],
1063    new_ranges: &[tree_sitter::Range],
1064) -> Vec<tree_sitter::Range> {
1065    let mut changed_ranges = changed_ranges.into_iter().peekable();
1066    let mut new_ranges = new_ranges.into_iter().peekable();
1067    let mut ranges_ix = 0;
1068    loop {
1069        let new_range = new_ranges.peek();
1070        let mut changed_range = changed_ranges.peek();
1071
1072        // Remove ranges that have changed before inserting any new ranges
1073        // into those ranges.
1074        if let Some((changed, new)) = changed_range.zip(new_range) {
1075            if new.end_byte < changed.start {
1076                changed_range = None;
1077            }
1078        }
1079
1080        if let Some(changed) = changed_range {
1081            let mut start_ix = ranges_ix
1082                + match ranges[ranges_ix..].binary_search_by_key(&changed.start, |r| r.end_byte) {
1083                    Ok(ix) | Err(ix) => ix,
1084                };
1085            let mut end_ix = ranges_ix
1086                + match ranges[ranges_ix..].binary_search_by_key(&changed.end, |r| r.start_byte) {
1087                    Ok(ix) => ix + 1,
1088                    Err(ix) => ix,
1089                };
1090
1091            // If there are empty ranges, then there may be multiple ranges with the same
1092            // start or end. Expand the splice to include any adjacent ranges that touch
1093            // the changed range.
1094            while start_ix > 0 {
1095                if ranges[start_ix - 1].end_byte == changed.start {
1096                    start_ix -= 1;
1097                } else {
1098                    break;
1099                }
1100            }
1101            while let Some(range) = ranges.get(end_ix) {
1102                if range.start_byte == changed.end {
1103                    end_ix += 1;
1104                } else {
1105                    break;
1106                }
1107            }
1108
1109            if end_ix > start_ix {
1110                ranges.splice(start_ix..end_ix, []);
1111            }
1112            changed_ranges.next();
1113            ranges_ix = start_ix;
1114        } else if let Some(new_range) = new_range {
1115            let ix = ranges_ix
1116                + match ranges[ranges_ix..]
1117                    .binary_search_by_key(&new_range.start_byte, |r| r.start_byte)
1118                {
1119                    Ok(ix) | Err(ix) => ix,
1120                };
1121            ranges.insert(ix, **new_range);
1122            new_ranges.next();
1123            ranges_ix = ix + 1;
1124        } else {
1125            break;
1126        }
1127    }
1128    ranges
1129}
1130
1131impl<'a> SyntaxLayerInfo<'a> {
1132    pub(crate) fn override_id(&self, offset: usize, text: &text::BufferSnapshot) -> Option<u32> {
1133        let text = TextProvider(text.as_rope());
1134        let config = self.language.grammar.as_ref()?.override_config.as_ref()?;
1135
1136        let mut query_cursor = QueryCursorHandle::new();
1137        query_cursor.set_byte_range(offset..offset);
1138
1139        let mut smallest_match: Option<(u32, Range<usize>)> = None;
1140        for mat in query_cursor.matches(&config.query, self.node, text) {
1141            for capture in mat.captures {
1142                if !config.values.contains_key(&capture.index) {
1143                    continue;
1144                }
1145
1146                let range = capture.node.byte_range();
1147                if offset <= range.start || offset >= range.end {
1148                    continue;
1149                }
1150
1151                if let Some((_, smallest_range)) = &smallest_match {
1152                    if range.len() < smallest_range.len() {
1153                        smallest_match = Some((capture.index, range))
1154                    }
1155                    continue;
1156                }
1157
1158                smallest_match = Some((capture.index, range));
1159            }
1160        }
1161
1162        smallest_match.map(|(index, _)| index)
1163    }
1164}
1165
1166impl std::ops::Deref for SyntaxMap {
1167    type Target = SyntaxSnapshot;
1168
1169    fn deref(&self) -> &Self::Target {
1170        &self.snapshot
1171    }
1172}
1173
1174impl PartialEq for ParseStep {
1175    fn eq(&self, _: &Self) -> bool {
1176        false
1177    }
1178}
1179
1180impl Eq for ParseStep {}
1181
1182impl PartialOrd for ParseStep {
1183    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1184        Some(self.cmp(&other))
1185    }
1186}
1187
1188impl Ord for ParseStep {
1189    fn cmp(&self, other: &Self) -> Ordering {
1190        let range_a = self.range();
1191        let range_b = other.range();
1192        Ord::cmp(&other.depth, &self.depth)
1193            .then_with(|| Ord::cmp(&range_b.start, &range_a.start))
1194            .then_with(|| Ord::cmp(&range_a.end, &range_b.end))
1195            .then_with(|| self.language.id().cmp(&other.language.id()))
1196    }
1197}
1198
1199impl ParseStep {
1200    fn range(&self) -> Range<usize> {
1201        if let ParseMode::Combined {
1202            parent_layer_range, ..
1203        } = &self.mode
1204        {
1205            parent_layer_range.clone()
1206        } else {
1207            let start = self.included_ranges.first().map_or(0, |r| r.start_byte);
1208            let end = self.included_ranges.last().map_or(0, |r| r.end_byte);
1209            start..end
1210        }
1211    }
1212}
1213
1214impl ChangedRegion {
1215    fn cmp(&self, other: &Self, buffer: &BufferSnapshot) -> Ordering {
1216        let range_a = &self.range;
1217        let range_b = &other.range;
1218        Ord::cmp(&self.depth, &other.depth)
1219            .then_with(|| range_a.start.cmp(&range_b.start, buffer))
1220            .then_with(|| range_b.end.cmp(&range_a.end, buffer))
1221    }
1222}
1223
1224impl ChangeRegionSet {
1225    fn start_position(&self) -> ChangeStartPosition {
1226        self.0.first().map_or(
1227            ChangeStartPosition {
1228                depth: usize::MAX,
1229                position: Anchor::MAX,
1230            },
1231            |region| ChangeStartPosition {
1232                depth: region.depth,
1233                position: region.range.start,
1234            },
1235        )
1236    }
1237
1238    fn intersects(&self, layer: &SyntaxLayer, text: &BufferSnapshot) -> bool {
1239        for region in &self.0 {
1240            if region.depth < layer.depth {
1241                continue;
1242            }
1243            if region.depth > layer.depth {
1244                break;
1245            }
1246            if region.range.end.cmp(&layer.range.start, text).is_le() {
1247                continue;
1248            }
1249            if region.range.start.cmp(&layer.range.end, text).is_ge() {
1250                break;
1251            }
1252            return true;
1253        }
1254        false
1255    }
1256
1257    fn insert(&mut self, region: ChangedRegion, text: &BufferSnapshot) {
1258        if let Err(ix) = self.0.binary_search_by(|probe| probe.cmp(&region, text)) {
1259            self.0.insert(ix, region);
1260        }
1261    }
1262
1263    fn prune(&mut self, summary: SyntaxLayerSummary, text: &BufferSnapshot) -> bool {
1264        let prev_len = self.0.len();
1265        self.0.retain(|region| {
1266            region.depth > summary.max_depth
1267                || (region.depth == summary.max_depth
1268                    && region
1269                        .range
1270                        .end
1271                        .cmp(&summary.last_layer_range.start, text)
1272                        .is_gt())
1273        });
1274        self.0.len() < prev_len
1275    }
1276}
1277
1278impl Default for SyntaxLayerSummary {
1279    fn default() -> Self {
1280        Self {
1281            max_depth: 0,
1282            min_depth: 0,
1283            range: Anchor::MAX..Anchor::MIN,
1284            last_layer_range: Anchor::MIN..Anchor::MAX,
1285            last_layer_language: None,
1286        }
1287    }
1288}
1289
1290impl sum_tree::Summary for SyntaxLayerSummary {
1291    type Context = BufferSnapshot;
1292
1293    fn add_summary(&mut self, other: &Self, buffer: &Self::Context) {
1294        if other.max_depth > self.max_depth {
1295            self.max_depth = other.max_depth;
1296            self.range = other.range.clone();
1297        } else {
1298            if other.range.start.cmp(&self.range.start, buffer).is_lt() {
1299                self.range.start = other.range.start;
1300            }
1301            if other.range.end.cmp(&self.range.end, buffer).is_gt() {
1302                self.range.end = other.range.end;
1303            }
1304        }
1305        self.last_layer_range = other.last_layer_range.clone();
1306        self.last_layer_language = other.last_layer_language;
1307    }
1308}
1309
1310impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary> for SyntaxLayerPosition {
1311    fn cmp(&self, cursor_location: &SyntaxLayerSummary, buffer: &BufferSnapshot) -> Ordering {
1312        Ord::cmp(&self.depth, &cursor_location.max_depth)
1313            .then_with(|| {
1314                self.range
1315                    .start
1316                    .cmp(&cursor_location.last_layer_range.start, buffer)
1317            })
1318            .then_with(|| {
1319                cursor_location
1320                    .last_layer_range
1321                    .end
1322                    .cmp(&self.range.end, buffer)
1323            })
1324            .then_with(|| self.language.cmp(&cursor_location.last_layer_language))
1325    }
1326}
1327
1328impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary> for ChangeStartPosition {
1329    fn cmp(&self, cursor_location: &SyntaxLayerSummary, text: &BufferSnapshot) -> Ordering {
1330        Ord::cmp(&self.depth, &cursor_location.max_depth)
1331            .then_with(|| self.position.cmp(&cursor_location.range.end, text))
1332    }
1333}
1334
1335impl<'a> SeekTarget<'a, SyntaxLayerSummary, SyntaxLayerSummary>
1336    for SyntaxLayerPositionBeforeChange
1337{
1338    fn cmp(&self, cursor_location: &SyntaxLayerSummary, buffer: &BufferSnapshot) -> Ordering {
1339        if self.change.cmp(cursor_location, buffer).is_le() {
1340            return Ordering::Less;
1341        } else {
1342            self.position.cmp(cursor_location, buffer)
1343        }
1344    }
1345}
1346
1347impl sum_tree::Item for SyntaxLayer {
1348    type Summary = SyntaxLayerSummary;
1349
1350    fn summary(&self) -> Self::Summary {
1351        SyntaxLayerSummary {
1352            min_depth: self.depth,
1353            max_depth: self.depth,
1354            range: self.range.clone(),
1355            last_layer_range: self.range.clone(),
1356            last_layer_language: self.language.id(),
1357        }
1358    }
1359}
1360
1361impl std::fmt::Debug for SyntaxLayer {
1362    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1363        f.debug_struct("SyntaxLayer")
1364            .field("depth", &self.depth)
1365            .field("range", &self.range)
1366            .field("tree", &self.tree)
1367            .finish()
1368    }
1369}
1370
1371impl<'a> tree_sitter::TextProvider<'a> for TextProvider<'a> {
1372    type I = ByteChunks<'a>;
1373
1374    fn text(&mut self, node: tree_sitter::Node) -> Self::I {
1375        ByteChunks(self.0.chunks_in_range(node.byte_range()))
1376    }
1377}
1378
1379impl<'a> Iterator for ByteChunks<'a> {
1380    type Item = &'a [u8];
1381
1382    fn next(&mut self) -> Option<Self::Item> {
1383        self.0.next().map(str::as_bytes)
1384    }
1385}
1386
1387impl QueryCursorHandle {
1388    pub(crate) fn new() -> Self {
1389        let mut cursor = QUERY_CURSORS.lock().pop().unwrap_or_else(QueryCursor::new);
1390        cursor.set_match_limit(64);
1391        QueryCursorHandle(Some(cursor))
1392    }
1393}
1394
1395impl Deref for QueryCursorHandle {
1396    type Target = QueryCursor;
1397
1398    fn deref(&self) -> &Self::Target {
1399        self.0.as_ref().unwrap()
1400    }
1401}
1402
1403impl DerefMut for QueryCursorHandle {
1404    fn deref_mut(&mut self) -> &mut Self::Target {
1405        self.0.as_mut().unwrap()
1406    }
1407}
1408
1409impl Drop for QueryCursorHandle {
1410    fn drop(&mut self) {
1411        let mut cursor = self.0.take().unwrap();
1412        cursor.set_byte_range(0..usize::MAX);
1413        cursor.set_point_range(Point::zero().to_ts_point()..Point::MAX.to_ts_point());
1414        QUERY_CURSORS.lock().push(cursor)
1415    }
1416}
1417
1418pub(crate) trait ToTreeSitterPoint {
1419    fn to_ts_point(self) -> tree_sitter::Point;
1420    fn from_ts_point(point: tree_sitter::Point) -> Self;
1421}
1422
1423impl ToTreeSitterPoint for Point {
1424    fn to_ts_point(self) -> tree_sitter::Point {
1425        tree_sitter::Point::new(self.row as usize, self.column as usize)
1426    }
1427
1428    fn from_ts_point(point: tree_sitter::Point) -> Self {
1429        Point::new(point.row as u32, point.column as u32)
1430    }
1431}
1432
1433#[cfg(test)]
1434mod tests {
1435    use super::*;
1436    use crate::LanguageConfig;
1437    use rand::rngs::StdRng;
1438    use std::env;
1439    use text::Buffer;
1440    use unindent::Unindent as _;
1441    use util::test::marked_text_ranges;
1442
1443    #[test]
1444    fn test_splice_included_ranges() {
1445        let ranges = vec![ts_range(20..30), ts_range(50..60), ts_range(80..90)];
1446
1447        let new_ranges = splice_included_ranges(
1448            ranges.clone(),
1449            &[54..56, 58..68],
1450            &[ts_range(50..54), ts_range(59..67)],
1451        );
1452        assert_eq!(
1453            new_ranges,
1454            &[
1455                ts_range(20..30),
1456                ts_range(50..54),
1457                ts_range(59..67),
1458                ts_range(80..90),
1459            ]
1460        );
1461
1462        let new_ranges = splice_included_ranges(ranges.clone(), &[70..71, 91..100], &[]);
1463        assert_eq!(
1464            new_ranges,
1465            &[ts_range(20..30), ts_range(50..60), ts_range(80..90)]
1466        );
1467
1468        let new_ranges =
1469            splice_included_ranges(ranges.clone(), &[], &[ts_range(0..2), ts_range(70..75)]);
1470        assert_eq!(
1471            new_ranges,
1472            &[
1473                ts_range(0..2),
1474                ts_range(20..30),
1475                ts_range(50..60),
1476                ts_range(70..75),
1477                ts_range(80..90)
1478            ]
1479        );
1480
1481        let new_ranges = splice_included_ranges(ranges.clone(), &[30..50], &[ts_range(25..55)]);
1482        assert_eq!(new_ranges, &[ts_range(25..55), ts_range(80..90)]);
1483
1484        fn ts_range(range: Range<usize>) -> tree_sitter::Range {
1485            tree_sitter::Range {
1486                start_byte: range.start,
1487                start_point: tree_sitter::Point {
1488                    row: 0,
1489                    column: range.start,
1490                },
1491                end_byte: range.end,
1492                end_point: tree_sitter::Point {
1493                    row: 0,
1494                    column: range.end,
1495                },
1496            }
1497        }
1498    }
1499
1500    #[gpui::test]
1501    fn test_syntax_map_layers_for_range() {
1502        let registry = Arc::new(LanguageRegistry::test());
1503        let language = Arc::new(rust_lang());
1504        registry.add(language.clone());
1505
1506        let mut buffer = Buffer::new(
1507            0,
1508            0,
1509            r#"
1510                fn a() {
1511                    assert_eq!(
1512                        b(vec![C {}]),
1513                        vec![d.e],
1514                    );
1515                    println!("{}", f(|_| true));
1516                }
1517            "#
1518            .unindent(),
1519        );
1520
1521        let mut syntax_map = SyntaxMap::new();
1522        syntax_map.set_language_registry(registry.clone());
1523        syntax_map.reparse(language.clone(), &buffer);
1524
1525        assert_layers_for_range(
1526            &syntax_map,
1527            &buffer,
1528            Point::new(2, 0)..Point::new(2, 0),
1529            &[
1530                "...(function_item ... (block (expression_statement (macro_invocation...",
1531                "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
1532            ],
1533        );
1534        assert_layers_for_range(
1535            &syntax_map,
1536            &buffer,
1537            Point::new(2, 14)..Point::new(2, 16),
1538            &[
1539                "...(function_item ...",
1540                "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
1541                "...(array_expression (struct_expression ...",
1542            ],
1543        );
1544        assert_layers_for_range(
1545            &syntax_map,
1546            &buffer,
1547            Point::new(3, 14)..Point::new(3, 16),
1548            &[
1549                "...(function_item ...",
1550                "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
1551                "...(array_expression (field_expression ...",
1552            ],
1553        );
1554        assert_layers_for_range(
1555            &syntax_map,
1556            &buffer,
1557            Point::new(5, 12)..Point::new(5, 16),
1558            &[
1559                "...(function_item ...",
1560                "...(call_expression ... (arguments (closure_expression ...",
1561            ],
1562        );
1563
1564        // Replace a vec! macro invocation with a plain slice, removing a syntactic layer.
1565        let macro_name_range = range_for_text(&buffer, "vec!");
1566        buffer.edit([(macro_name_range, "&")]);
1567        syntax_map.interpolate(&buffer);
1568        syntax_map.reparse(language.clone(), &buffer);
1569
1570        assert_layers_for_range(
1571            &syntax_map,
1572            &buffer,
1573            Point::new(2, 14)..Point::new(2, 16),
1574            &[
1575                "...(function_item ...",
1576                "...(tuple_expression (call_expression ... arguments: (arguments (reference_expression value: (array_expression...",
1577            ],
1578        );
1579
1580        // Put the vec! macro back, adding back the syntactic layer.
1581        buffer.undo();
1582        syntax_map.interpolate(&buffer);
1583        syntax_map.reparse(language.clone(), &buffer);
1584
1585        assert_layers_for_range(
1586            &syntax_map,
1587            &buffer,
1588            Point::new(2, 14)..Point::new(2, 16),
1589            &[
1590                "...(function_item ...",
1591                "...(tuple_expression (call_expression ... arguments: (arguments (macro_invocation...",
1592                "...(array_expression (struct_expression ...",
1593            ],
1594        );
1595    }
1596
1597    #[gpui::test]
1598    fn test_typing_multiple_new_injections() {
1599        let (buffer, syntax_map) = test_edit_sequence(
1600            "Rust",
1601            &[
1602                "fn a() { dbg }",
1603                "fn a() { dbg«!» }",
1604                "fn a() { dbg!«()» }",
1605                "fn a() { dbg!(«b») }",
1606                "fn a() { dbg!(b«.») }",
1607                "fn a() { dbg!(b.«c») }",
1608                "fn a() { dbg!(b.c«()») }",
1609                "fn a() { dbg!(b.c(«vec»)) }",
1610                "fn a() { dbg!(b.c(vec«!»)) }",
1611                "fn a() { dbg!(b.c(vec!«[]»)) }",
1612                "fn a() { dbg!(b.c(vec![«d»])) }",
1613                "fn a() { dbg!(b.c(vec![d«.»])) }",
1614                "fn a() { dbg!(b.c(vec![d.«e»])) }",
1615            ],
1616        );
1617
1618        assert_capture_ranges(
1619            &syntax_map,
1620            &buffer,
1621            &["field"],
1622            "fn a() { dbg!(b.«c»(vec![d.«e»])) }",
1623        );
1624    }
1625
1626    #[gpui::test]
1627    fn test_pasting_new_injection_line_between_others() {
1628        let (buffer, syntax_map) = test_edit_sequence(
1629            "Rust",
1630            &[
1631                "
1632                    fn a() {
1633                        b!(B {});
1634                        c!(C {});
1635                        d!(D {});
1636                        e!(E {});
1637                        f!(F {});
1638                        g!(G {});
1639                    }
1640                ",
1641                "
1642                    fn a() {
1643                        b!(B {});
1644                        c!(C {});
1645                        d!(D {});
1646                    «    h!(H {});
1647                    »    e!(E {});
1648                        f!(F {});
1649                        g!(G {});
1650                    }
1651                ",
1652            ],
1653        );
1654
1655        assert_capture_ranges(
1656            &syntax_map,
1657            &buffer,
1658            &["struct"],
1659            "
1660            fn a() {
1661                b!(«B {}»);
1662                c!(«C {}»);
1663                d!(«D {}»);
1664                h!(«H {}»);
1665                e!(«E {}»);
1666                f!(«F {}»);
1667                g!(«G {}»);
1668            }
1669            ",
1670        );
1671    }
1672
1673    #[gpui::test]
1674    fn test_joining_injections_with_child_injections() {
1675        let (buffer, syntax_map) = test_edit_sequence(
1676            "Rust",
1677            &[
1678                "
1679                    fn a() {
1680                        b!(
1681                            c![one.two.three],
1682                            d![four.five.six],
1683                        );
1684                        e!(
1685                            f![seven.eight],
1686                        );
1687                    }
1688                ",
1689                "
1690                    fn a() {
1691                        b!(
1692                            c![one.two.three],
1693                            d![four.five.six],
1694                        ˇ    f![seven.eight],
1695                        );
1696                    }
1697                ",
1698            ],
1699        );
1700
1701        assert_capture_ranges(
1702            &syntax_map,
1703            &buffer,
1704            &["field"],
1705            "
1706            fn a() {
1707                b!(
1708                    c![one.«two».«three»],
1709                    d![four.«five».«six»],
1710                    f![seven.«eight»],
1711                );
1712            }
1713            ",
1714        );
1715    }
1716
1717    #[gpui::test]
1718    fn test_editing_edges_of_injection() {
1719        test_edit_sequence(
1720            "Rust",
1721            &[
1722                "
1723                    fn a() {
1724                        b!(c!())
1725                    }
1726                ",
1727                "
1728                    fn a() {
1729                        «d»!(c!())
1730                    }
1731                ",
1732                "
1733                    fn a() {
1734                        «e»d!(c!())
1735                    }
1736                ",
1737                "
1738                    fn a() {
1739                        ed!«[»c!()«]»
1740                    }
1741            ",
1742            ],
1743        );
1744    }
1745
1746    #[gpui::test]
1747    fn test_edits_preceding_and_intersecting_injection() {
1748        test_edit_sequence(
1749            "Rust",
1750            &[
1751                //
1752                "const aaaaaaaaaaaa: B = c!(d(e.f));",
1753                "const aˇa: B = c!(d(eˇ));",
1754            ],
1755        );
1756    }
1757
1758    #[gpui::test]
1759    fn test_non_local_changes_create_injections() {
1760        test_edit_sequence(
1761            "Rust",
1762            &[
1763                "
1764                    // a! {
1765                        static B: C = d;
1766                    // }
1767                ",
1768                "
1769                    ˇa! {
1770                        static B: C = d;
1771                    ˇ}
1772                ",
1773            ],
1774        );
1775    }
1776
1777    #[gpui::test]
1778    fn test_creating_many_injections_in_one_edit() {
1779        test_edit_sequence(
1780            "Rust",
1781            &[
1782                "
1783                    fn a() {
1784                        one(Two::three(3));
1785                        four(Five::six(6));
1786                        seven(Eight::nine(9));
1787                    }
1788                ",
1789                "
1790                    fn a() {
1791                        one«!»(Two::three(3));
1792                        four«!»(Five::six(6));
1793                        seven«!»(Eight::nine(9));
1794                    }
1795                ",
1796                "
1797                    fn a() {
1798                        one!(Two::three«!»(3));
1799                        four!(Five::six«!»(6));
1800                        seven!(Eight::nine«!»(9));
1801                    }
1802                ",
1803            ],
1804        );
1805    }
1806
1807    #[gpui::test]
1808    fn test_editing_across_injection_boundary() {
1809        test_edit_sequence(
1810            "Rust",
1811            &[
1812                "
1813                    fn one() {
1814                        two();
1815                        three!(
1816                            three.four,
1817                            five.six,
1818                        );
1819                    }
1820                ",
1821                "
1822                    fn one() {
1823                        two();
1824                        th«irty_five![»
1825                            three.four,
1826                            five.six,
1827                        «   seven.eight,
1828                        ];»
1829                    }
1830                ",
1831            ],
1832        );
1833    }
1834
1835    #[gpui::test]
1836    fn test_removing_injection_by_replacing_across_boundary() {
1837        test_edit_sequence(
1838            "Rust",
1839            &[
1840                "
1841                    fn one() {
1842                        two!(
1843                            three.four,
1844                        );
1845                    }
1846                ",
1847                "
1848                    fn one() {
1849                        t«en
1850                            .eleven(
1851                            twelve,
1852                        »
1853                            three.four,
1854                        );
1855                    }
1856                ",
1857            ],
1858        );
1859    }
1860
1861    #[gpui::test]
1862    fn test_combined_injections() {
1863        let (buffer, syntax_map) = test_edit_sequence(
1864            "ERB",
1865            &[
1866                "
1867                    <body>
1868                        <% if @one %>
1869                            <div class=one>
1870                        <% else %>
1871                            <div class=two>
1872                        <% end %>
1873                        </div>
1874                    </body>
1875                ",
1876                "
1877                    <body>
1878                        <% if @one %>
1879                            <div class=one>
1880                        ˇ else ˇ
1881                            <div class=two>
1882                        <% end %>
1883                        </div>
1884                    </body>
1885                ",
1886                "
1887                    <body>
1888                        <% if @one «;» end %>
1889                        </div>
1890                    </body>
1891                ",
1892            ],
1893        );
1894
1895        assert_capture_ranges(
1896            &syntax_map,
1897            &buffer,
1898            &["tag", "ivar"],
1899            "
1900                <«body»>
1901                    <% if «@one» ; end %>
1902                    </«div»>
1903                </«body»>
1904            ",
1905        );
1906    }
1907
1908    #[gpui::test]
1909    fn test_combined_injections_empty_ranges() {
1910        test_edit_sequence(
1911            "ERB",
1912            &[
1913                "
1914                    <% if @one %>
1915                    <% else %>
1916                    <% end %>
1917                ",
1918                "
1919                    <% if @one %>
1920                    ˇ<% end %>
1921                ",
1922            ],
1923        );
1924    }
1925
1926    #[gpui::test]
1927    fn test_combined_injections_edit_edges_of_ranges() {
1928        let (buffer, syntax_map) = test_edit_sequence(
1929            "ERB",
1930            &[
1931                "
1932                    <%= one @two %>
1933                    <%= three @four %>
1934                ",
1935                "
1936                    <%= one @two %ˇ
1937                    <%= three @four %>
1938                ",
1939                "
1940                    <%= one @two %«>»
1941                    <%= three @four %>
1942                ",
1943            ],
1944        );
1945
1946        assert_capture_ranges(
1947            &syntax_map,
1948            &buffer,
1949            &["tag", "ivar"],
1950            "
1951                <%= one «@two» %>
1952                <%= three «@four» %>
1953            ",
1954        );
1955    }
1956
1957    #[gpui::test]
1958    fn test_combined_injections_splitting_some_injections() {
1959        let (_buffer, _syntax_map) = test_edit_sequence(
1960            "ERB",
1961            &[
1962                r#"
1963                      <%A if b(:c) %>
1964                        d
1965                      <% end %>
1966                      eee
1967                      <% f %>
1968                "#,
1969                r#"
1970                      <%« AAAAAAA %>
1971                        hhhhhhh
1972                      <%=» if b(:c) %>
1973                        d
1974                      <% end %>
1975                      eee
1976                      <% f %>
1977                "#,
1978            ],
1979        );
1980    }
1981
1982    #[gpui::test(iterations = 50)]
1983    fn test_random_syntax_map_edits(mut rng: StdRng) {
1984        let operations = env::var("OPERATIONS")
1985            .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1986            .unwrap_or(10);
1987
1988        let text = r#"
1989            fn test_something() {
1990                let vec = vec![5, 1, 3, 8];
1991                assert_eq!(
1992                    vec
1993                        .into_iter()
1994                        .map(|i| i * 2)
1995                        .collect::<Vec<usize>>(),
1996                    vec![
1997                        5 * 2, 1 * 2, 3 * 2, 8 * 2
1998                    ],
1999                );
2000            }
2001        "#
2002        .unindent()
2003        .repeat(2);
2004
2005        let registry = Arc::new(LanguageRegistry::test());
2006        let language = Arc::new(rust_lang());
2007        registry.add(language.clone());
2008        let mut buffer = Buffer::new(0, 0, text);
2009
2010        let mut syntax_map = SyntaxMap::new();
2011        syntax_map.set_language_registry(registry.clone());
2012        syntax_map.reparse(language.clone(), &buffer);
2013
2014        let mut reference_syntax_map = SyntaxMap::new();
2015        reference_syntax_map.set_language_registry(registry.clone());
2016
2017        log::info!("initial text:\n{}", buffer.text());
2018
2019        for _ in 0..operations {
2020            let prev_buffer = buffer.snapshot();
2021            let prev_syntax_map = syntax_map.snapshot();
2022
2023            buffer.randomly_edit(&mut rng, 3);
2024            log::info!("text:\n{}", buffer.text());
2025
2026            syntax_map.interpolate(&buffer);
2027            check_interpolation(&prev_syntax_map, &syntax_map, &prev_buffer, &buffer);
2028
2029            syntax_map.reparse(language.clone(), &buffer);
2030
2031            reference_syntax_map.clear();
2032            reference_syntax_map.reparse(language.clone(), &buffer);
2033        }
2034
2035        for i in 0..operations {
2036            let i = operations - i - 1;
2037            buffer.undo();
2038            log::info!("undoing operation {}", i);
2039            log::info!("text:\n{}", buffer.text());
2040
2041            syntax_map.interpolate(&buffer);
2042            syntax_map.reparse(language.clone(), &buffer);
2043
2044            reference_syntax_map.clear();
2045            reference_syntax_map.reparse(language.clone(), &buffer);
2046            assert_eq!(
2047                syntax_map.layers(&buffer).len(),
2048                reference_syntax_map.layers(&buffer).len(),
2049                "wrong number of layers after undoing edit {i}"
2050            );
2051        }
2052
2053        let layers = syntax_map.layers(&buffer);
2054        let reference_layers = reference_syntax_map.layers(&buffer);
2055        for (edited_layer, reference_layer) in layers.into_iter().zip(reference_layers.into_iter())
2056        {
2057            assert_eq!(edited_layer.node.to_sexp(), reference_layer.node.to_sexp());
2058            assert_eq!(edited_layer.node.range(), reference_layer.node.range());
2059        }
2060    }
2061
2062    #[gpui::test(iterations = 50)]
2063    fn test_random_syntax_map_edits_with_combined_injections(mut rng: StdRng) {
2064        let operations = env::var("OPERATIONS")
2065            .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
2066            .unwrap_or(10);
2067
2068        let text = r#"
2069          <div id="main">
2070            <% if one?(:two) %>
2071              <p class="three" four>
2072                <%= yield :five %>
2073              </p>
2074            <% elsif Six.seven(8) %>
2075              <p id="three" four>
2076                <%= yield :five %>
2077              </p>
2078            <% else %>
2079              <span>Ok</span>
2080            <% end %>
2081          </div>
2082        "#
2083        .unindent()
2084        .repeat(8);
2085
2086        let registry = Arc::new(LanguageRegistry::test());
2087        let language = Arc::new(erb_lang());
2088        registry.add(language.clone());
2089        registry.add(Arc::new(ruby_lang()));
2090        registry.add(Arc::new(html_lang()));
2091        let mut buffer = Buffer::new(0, 0, text);
2092
2093        let mut syntax_map = SyntaxMap::new();
2094        syntax_map.set_language_registry(registry.clone());
2095        syntax_map.reparse(language.clone(), &buffer);
2096
2097        let mut reference_syntax_map = SyntaxMap::new();
2098        reference_syntax_map.set_language_registry(registry.clone());
2099
2100        log::info!("initial text:\n{}", buffer.text());
2101
2102        for _ in 0..operations {
2103            let prev_buffer = buffer.snapshot();
2104            let prev_syntax_map = syntax_map.snapshot();
2105
2106            buffer.randomly_edit(&mut rng, 3);
2107            log::info!("text:\n{}", buffer.text());
2108
2109            syntax_map.interpolate(&buffer);
2110            check_interpolation(&prev_syntax_map, &syntax_map, &prev_buffer, &buffer);
2111
2112            syntax_map.reparse(language.clone(), &buffer);
2113
2114            reference_syntax_map.clear();
2115            reference_syntax_map.reparse(language.clone(), &buffer);
2116        }
2117
2118        for i in 0..operations {
2119            let i = operations - i - 1;
2120            buffer.undo();
2121            log::info!("undoing operation {}", i);
2122            log::info!("text:\n{}", buffer.text());
2123
2124            syntax_map.interpolate(&buffer);
2125            syntax_map.reparse(language.clone(), &buffer);
2126
2127            reference_syntax_map.clear();
2128            reference_syntax_map.reparse(language.clone(), &buffer);
2129            assert_eq!(
2130                syntax_map.layers(&buffer).len(),
2131                reference_syntax_map.layers(&buffer).len(),
2132                "wrong number of layers after undoing edit {i}"
2133            );
2134        }
2135
2136        let layers = syntax_map.layers(&buffer);
2137        let reference_layers = reference_syntax_map.layers(&buffer);
2138        for (edited_layer, reference_layer) in layers.into_iter().zip(reference_layers.into_iter())
2139        {
2140            assert_eq!(edited_layer.node.to_sexp(), reference_layer.node.to_sexp());
2141            assert_eq!(edited_layer.node.range(), reference_layer.node.range());
2142        }
2143    }
2144
2145    fn check_interpolation(
2146        old_syntax_map: &SyntaxSnapshot,
2147        new_syntax_map: &SyntaxSnapshot,
2148        old_buffer: &BufferSnapshot,
2149        new_buffer: &BufferSnapshot,
2150    ) {
2151        let edits = new_buffer
2152            .edits_since::<usize>(&old_buffer.version())
2153            .collect::<Vec<_>>();
2154
2155        for (old_layer, new_layer) in old_syntax_map
2156            .layers
2157            .iter()
2158            .zip(new_syntax_map.layers.iter())
2159        {
2160            assert_eq!(old_layer.range, new_layer.range);
2161            let old_start_byte = old_layer.range.start.to_offset(old_buffer);
2162            let new_start_byte = new_layer.range.start.to_offset(new_buffer);
2163            let old_start_point = old_layer.range.start.to_point(old_buffer).to_ts_point();
2164            let new_start_point = new_layer.range.start.to_point(new_buffer).to_ts_point();
2165            let old_node = old_layer
2166                .tree
2167                .root_node_with_offset(old_start_byte, old_start_point);
2168            let new_node = new_layer
2169                .tree
2170                .root_node_with_offset(new_start_byte, new_start_point);
2171            check_node_edits(
2172                old_layer.depth,
2173                &old_layer.range,
2174                old_node,
2175                new_node,
2176                old_buffer,
2177                new_buffer,
2178                &edits,
2179            );
2180        }
2181
2182        fn check_node_edits(
2183            depth: usize,
2184            range: &Range<Anchor>,
2185            old_node: Node,
2186            new_node: Node,
2187            old_buffer: &BufferSnapshot,
2188            new_buffer: &BufferSnapshot,
2189            edits: &[text::Edit<usize>],
2190        ) {
2191            assert_eq!(old_node.kind(), new_node.kind());
2192
2193            let old_range = old_node.byte_range();
2194            let new_range = new_node.byte_range();
2195
2196            let is_edited = edits
2197                .iter()
2198                .any(|edit| edit.new.start < new_range.end && edit.new.end > new_range.start);
2199            if is_edited {
2200                assert!(
2201                    new_node.has_changes(),
2202                    concat!(
2203                        "failed to mark node as edited.\n",
2204                        "layer depth: {}, old layer range: {:?}, new layer range: {:?},\n",
2205                        "node kind: {}, old node range: {:?}, new node range: {:?}",
2206                    ),
2207                    depth,
2208                    range.to_offset(old_buffer),
2209                    range.to_offset(new_buffer),
2210                    new_node.kind(),
2211                    old_range,
2212                    new_range,
2213                );
2214            }
2215
2216            if !new_node.has_changes() {
2217                assert_eq!(
2218                    old_buffer
2219                        .text_for_range(old_range.clone())
2220                        .collect::<String>(),
2221                    new_buffer
2222                        .text_for_range(new_range.clone())
2223                        .collect::<String>(),
2224                    concat!(
2225                        "mismatched text for node\n",
2226                        "layer depth: {}, old layer range: {:?}, new layer range: {:?},\n",
2227                        "node kind: {}, old node range:{:?}, new node range:{:?}",
2228                    ),
2229                    depth,
2230                    range.to_offset(old_buffer),
2231                    range.to_offset(new_buffer),
2232                    new_node.kind(),
2233                    old_range,
2234                    new_range,
2235                );
2236            }
2237
2238            for i in 0..new_node.child_count() {
2239                check_node_edits(
2240                    depth,
2241                    range,
2242                    old_node.child(i).unwrap(),
2243                    new_node.child(i).unwrap(),
2244                    old_buffer,
2245                    new_buffer,
2246                    edits,
2247                )
2248            }
2249        }
2250    }
2251
2252    fn test_edit_sequence(language_name: &str, steps: &[&str]) -> (Buffer, SyntaxMap) {
2253        let registry = Arc::new(LanguageRegistry::test());
2254        registry.add(Arc::new(rust_lang()));
2255        registry.add(Arc::new(ruby_lang()));
2256        registry.add(Arc::new(html_lang()));
2257        registry.add(Arc::new(erb_lang()));
2258        let language = registry.language_for_name(language_name).unwrap();
2259        let mut buffer = Buffer::new(0, 0, Default::default());
2260
2261        let mut mutated_syntax_map = SyntaxMap::new();
2262        mutated_syntax_map.set_language_registry(registry.clone());
2263        mutated_syntax_map.reparse(language.clone(), &buffer);
2264
2265        for (i, marked_string) in steps.into_iter().enumerate() {
2266            buffer.edit_via_marked_text(&marked_string.unindent());
2267
2268            // Reparse the syntax map
2269            mutated_syntax_map.interpolate(&buffer);
2270            mutated_syntax_map.reparse(language.clone(), &buffer);
2271
2272            // Create a second syntax map from scratch
2273            let mut reference_syntax_map = SyntaxMap::new();
2274            reference_syntax_map.set_language_registry(registry.clone());
2275            reference_syntax_map.reparse(language.clone(), &buffer);
2276
2277            // Compare the mutated syntax map to the new syntax map
2278            let mutated_layers = mutated_syntax_map.layers(&buffer);
2279            let reference_layers = reference_syntax_map.layers(&buffer);
2280            assert_eq!(
2281                mutated_layers.len(),
2282                reference_layers.len(),
2283                "wrong number of layers at step {i}"
2284            );
2285            for (edited_layer, reference_layer) in
2286                mutated_layers.into_iter().zip(reference_layers.into_iter())
2287            {
2288                assert_eq!(
2289                    edited_layer.node.to_sexp(),
2290                    reference_layer.node.to_sexp(),
2291                    "different layer at step {i}"
2292                );
2293                assert_eq!(
2294                    edited_layer.node.range(),
2295                    reference_layer.node.range(),
2296                    "different layer at step {i}"
2297                );
2298            }
2299        }
2300
2301        (buffer, mutated_syntax_map)
2302    }
2303
2304    fn html_lang() -> Language {
2305        Language::new(
2306            LanguageConfig {
2307                name: "HTML".into(),
2308                path_suffixes: vec!["html".to_string()],
2309                ..Default::default()
2310            },
2311            Some(tree_sitter_html::language()),
2312        )
2313        .with_highlights_query(
2314            r#"
2315                (tag_name) @tag
2316                (erroneous_end_tag_name) @tag
2317                (attribute_name) @property
2318            "#,
2319        )
2320        .unwrap()
2321    }
2322
2323    fn ruby_lang() -> Language {
2324        Language::new(
2325            LanguageConfig {
2326                name: "Ruby".into(),
2327                path_suffixes: vec!["rb".to_string()],
2328                ..Default::default()
2329            },
2330            Some(tree_sitter_ruby::language()),
2331        )
2332        .with_highlights_query(
2333            r#"
2334                ["if" "do" "else" "end"] @keyword
2335                (instance_variable) @ivar
2336            "#,
2337        )
2338        .unwrap()
2339    }
2340
2341    fn erb_lang() -> Language {
2342        Language::new(
2343            LanguageConfig {
2344                name: "ERB".into(),
2345                path_suffixes: vec!["erb".to_string()],
2346                ..Default::default()
2347            },
2348            Some(tree_sitter_embedded_template::language()),
2349        )
2350        .with_highlights_query(
2351            r#"
2352                ["<%" "%>"] @keyword
2353            "#,
2354        )
2355        .unwrap()
2356        .with_injection_query(
2357            r#"
2358                ((code) @content
2359                 (#set! "language" "ruby")
2360                 (#set! "combined"))
2361
2362                 ((content) @content
2363                 (#set! "language" "html")
2364                 (#set! "combined"))
2365            "#,
2366        )
2367        .unwrap()
2368    }
2369
2370    fn rust_lang() -> Language {
2371        Language::new(
2372            LanguageConfig {
2373                name: "Rust".into(),
2374                path_suffixes: vec!["rs".to_string()],
2375                ..Default::default()
2376            },
2377            Some(tree_sitter_rust::language()),
2378        )
2379        .with_highlights_query(
2380            r#"
2381                (field_identifier) @field
2382                (struct_expression) @struct
2383            "#,
2384        )
2385        .unwrap()
2386        .with_injection_query(
2387            r#"
2388                (macro_invocation
2389                    (token_tree) @content
2390                    (#set! "language" "rust"))
2391            "#,
2392        )
2393        .unwrap()
2394    }
2395
2396    fn range_for_text(buffer: &Buffer, text: &str) -> Range<usize> {
2397        let start = buffer.as_rope().to_string().find(text).unwrap();
2398        start..start + text.len()
2399    }
2400
2401    fn assert_layers_for_range(
2402        syntax_map: &SyntaxMap,
2403        buffer: &BufferSnapshot,
2404        range: Range<Point>,
2405        expected_layers: &[&str],
2406    ) {
2407        let layers = syntax_map
2408            .layers_for_range(range, &buffer)
2409            .collect::<Vec<_>>();
2410        assert_eq!(
2411            layers.len(),
2412            expected_layers.len(),
2413            "wrong number of layers"
2414        );
2415        for (i, (SyntaxLayerInfo { node, .. }, expected_s_exp)) in
2416            layers.iter().zip(expected_layers.iter()).enumerate()
2417        {
2418            let actual_s_exp = node.to_sexp();
2419            assert!(
2420                string_contains_sequence(
2421                    &actual_s_exp,
2422                    &expected_s_exp.split("...").collect::<Vec<_>>()
2423                ),
2424                "layer {i}:\n\nexpected: {expected_s_exp}\nactual:   {actual_s_exp}",
2425            );
2426        }
2427    }
2428
2429    fn assert_capture_ranges(
2430        syntax_map: &SyntaxMap,
2431        buffer: &BufferSnapshot,
2432        highlight_query_capture_names: &[&str],
2433        marked_string: &str,
2434    ) {
2435        let mut actual_ranges = Vec::<Range<usize>>::new();
2436        let captures = syntax_map.captures(0..buffer.len(), buffer, |grammar| {
2437            grammar.highlights_query.as_ref()
2438        });
2439        let queries = captures
2440            .grammars()
2441            .iter()
2442            .map(|grammar| grammar.highlights_query.as_ref().unwrap())
2443            .collect::<Vec<_>>();
2444        for capture in captures {
2445            let name = &queries[capture.grammar_index].capture_names()[capture.index as usize];
2446            if highlight_query_capture_names.contains(&name.as_str()) {
2447                actual_ranges.push(capture.node.byte_range());
2448            }
2449        }
2450
2451        let (text, expected_ranges) = marked_text_ranges(&marked_string.unindent(), false);
2452        assert_eq!(text, buffer.text());
2453        assert_eq!(actual_ranges, expected_ranges);
2454    }
2455
2456    pub fn string_contains_sequence(text: &str, parts: &[&str]) -> bool {
2457        let mut last_part_end = 0;
2458        for part in parts {
2459            if let Some(start_ix) = text[last_part_end..].find(part) {
2460                last_part_end = start_ix + part.len();
2461            } else {
2462                return false;
2463            }
2464        }
2465        true
2466    }
2467}