Repository: neovim
Issue: tree-sitter injected language ranges sometimes cross over the capture boundaries when `@combined`
Labels: bug,treesitter

<details> <summary>Using latest master</summary>

### Neovim version (nvim -v)

v0.9.0-dev-448+g707df8805-dirty

### Vim (not Nvim) behaves the same?

N/A

### Operating system/version

macOS 12

### Terminal name/version

alacritty

### $TERM environment variable

alacritty

### Installation

built from source today
</details>

### How to reproduce the issue

The following Rust code presents issues when injecting `@markdown @combined` into the doc comments.

```rust
/// # Doc comment
///
/// ```rust
/// let x = 5;
/// let y = 10; // does not highlight properly.
/// ```
```

Note that the rust TS grammar does not yet allow querying doc comments. I'm using a fork based on https://github.com/tree-sitter/tree-sitter-rust/pull/168. Basically it parses these as `(line_doc_comment (doc_content))` and then we inject using `(doc_content) @markdown @combine`.

If you don't want to repro by working on the rust grammar, here are three grammars that exhibit the issue when you nest them, because they roughly approximate the interference that goes on with `rust > markdown > rust`.

<details>
<summary>Detailed repro</summary>

```javascript
// a simple language made of leading ))))))) with the rest of the line captured as (host)
// designed to mess up parenlang below
module.exports = grammar({
    name: 'bubble',
    extras: _ => [],
    rules: {
        source_file: $ => repeat(choice($.line, '\n')),
        host: _ => token(/[^\)][^\n]*/),
        line: $ => seq($.bubbles, $.host),
        bubbles: $ => repeat1(')'),
    }
})
```

```scheme
; bubble/highlights.scm
(line (bubbles) @comment)
; bubble/injections.scm
(host) @bracketlang @combined
```

```javascript
// arbitrary content inside of square brackets, captured as (brackets_inner)
module.exports = grammar({
    name: "bracketlang",
    rules: {
        source_file: $ => repeat(seq('[', $.brackets_inner, ']')),
        brackets_inner: $ => /[^\]]*/,
    }
})
```

```scheme
; bracketlang/highlights.scm
("[" @operator)
("]" @operator)
; bracketlang/injections.scm
(brackets_inner) @parenlang @combined
```

```javascript
// s-expressions basically. designed to mess up when it sees a ))))) from bubble.
module.exports = grammar({
    name: "parenlang",
    inline: $ => [$._expr],
    supertypes: $ => [$._expr],
    word: $ => $.atom,
    rules: {
        source_file: $ => repeat($._expr),
        _expr: $ => choice(
            $.parens,
            $.atom,
        ),
        parens: $ => seq('(', repeat($._expr), ')'),
        atom: _ => /[^\s\(\)]+/,
    }
})
```

```scheme
; parenlang/highlights.scm
(parens "(" @delimiter)
(parens ")" @delimiter)
(atom) @keyword
```

```lua
local parser_config = require "nvim-treesitter.parsers".get_parser_configs()
parser_config.bubble = {
  install_info = {
    url = "~/src/tree-sitter-bubble",
    files = {"src/parser.c"},
  },
}
parser_config.bracketlang = {
  install_info = {
    url = "~/src/tree-sitter-bracketlang",
    files = {"src/parser.c"},
  },
}
parser_config.parenlang = {
  install_info = {
    url = "~/src/tree-sitter-parenlang",
    files = {"src/parser.c"},
  },
}
```
</details>

### Expected behavior

In simple terms, the second line of the fenced code block should highlight in the language specified. It's not happening.

For the bubble lang example, this is how it should parse (yes I have a potential solution)

<img width="606" alt="Screen Shot 2022-12-06 at 9 37 26 pm" src="https://user-images.githubusercontent.com/378760/205910955-230df958-0d5d-41ed-bfe6-cdf03faabbe3.png">


### Actual behavior

The complication happens at the second level of nesting injections.

1. The top-level `rust` injections give you a list of `@markdown` ones, each with the content that follows the initial `/// `. I.e. `# Doc comment\n`, `\n`, `\`\`\`rust\n`, etc.
2. The queries for the markdown parser produces a bunch of `@markdown_inline` (we can ignore these ones) and also one `@rust` injection.
3. The rust injection capture looks like this:

       let x = 5;
       /// let y = 10; // does not highlight properly

This is where it goes wrong. The range in question is `{ 3, 4, 5, 0 }` (aka line 3 col 4 .. line 5 col 0). This includes parts of the buffer that were not given to the markdown parser in the first place, specifically the `/// ` on the second and any subsequent lines. (As it goes down the rabbit-hole of the erroneous parse, it interprets the second line as a Rust doc comment, and hence the `let y...` is treated as a markdown inline.)

For the toy languages:

<img width="606" alt="error" src="https://user-images.githubusercontent.com/378760/205911097-675c02a4-273a-4033-b52b-b56edce14ece.png">

It's pretty much the same as above with the Rust doc comment:
- The second line's `)))))` is not included in the injection for bracketlang (OUTSIDE the square braces),
- but once bracketlang's injections are queried, you get a range spanning INSIDE the square braces, that starts on the first line and ends on the second, which includes the `)))))`.
- Then the parenlang parses that range, which means it has five extra brackets, and the latter four will be unbalanced and mess up the parse.

I'm guessing it happens this way because the tree-sitter query code isn't smart enough, and just constructs a node range by getting the relevant node and taking its start point and end point in the original buffer.

### Good news!

I have actually already devised a solution. The idea is to take an injected range like `{ 3, 4, 5, 0 }` and 'clip' or 'hole punch' the bit that isn't allowed, which splits it into two ranges `{3, 4, 4, 0}`, `{4, 4, 5, 0}`. You can do this by constructing an interval tree of all the parent LanguageTree's ranges, and then intersecting any overlapping ranges using some stock-standard `if start_child < start_parent`-style code.