Heredoc termination erroneously detected when not at start of line

[unphased]

I was editing this bash code today and realized that the heredoc was being terminated early and incorrectly by treesitter.

: <<'END_COMMENT'
This section is a heredoc (<<) redirected to a NOP command (:).
The single quotes around END_COMMENT are important,
because it disables variable resolving and command resolving
within these lines.  Without the single-quotes around END_COMMENT,
any $() `` would get executed as commands. 

END_COMMENT

Here the END_COMMENT was treated by treesitter as the end when the heredoc only terminates upon seeing END_COMMENT at the start of a line.

I'm still a noob so still learning how to set up a treesitter development environment to try to poke around and come up with the fix myself. So if someone wants to show me how i can get past getting stuck here, then that would also be appreciated.

I got tree-sitter cli installed and cloned tree-sitter-bash. Then I ran npm i in there and tree-sitter generate and tree-sitter test. Then I made the following change:

diff --git i/corpus/commands.txt w/corpus/commands.txt
index bca86b4..9c44a49 100644
--- i/corpus/commands.txt
+++ w/corpus/commands.txt
@@ -217,6 +217,18 @@ EOF

 (program (redirected_statement (command (command_name (word))) (heredoc_redirect (heredoc_start))) (heredoc_body))

+======================================
+Heredocs with closure not at BOL
+======================================
+: <<EOF
+even if EOF shows up in the middle of a line
+it should not terminate the heredoc
+EOF
+
+---
+
+(program (redirected_statement (command (command_name (word))) (heredoc_redirect (heredoc_start))) (heredoc_body))
+
 ======================================
 Quoted Heredocs
 ======================================

But no amount of subsequent tree-sitter test calls allows the new test I added to be picked up. Here I am stuck.

[unphased]

I've also tried this, I put the above example into a test.sh, and then

❯ tree-sitter parse test.sh
(program [0, 0] - [4, 0]
  (redirected_statement [0, 0] - [0, 7]
    body: (command [0, 0] - [0, 1]
      name: (command_name [0, 0] - [0, 1]
        (word [0, 0] - [0, 1])))
    redirect: (heredoc_redirect [0, 2] - [0, 7]
      (heredoc_start [0, 4] - [0, 7])))
  (heredoc_body [1, 0] - [1, 11])
  (command [1, 12] - [1, 44]
    name: (command_name [1, 12] - [1, 17]
      (word [1, 12] - [1, 17]))
    argument: (word [1, 18] - [1, 20])
    argument: (word [1, 21] - [1, 23])
    argument: (word [1, 24] - [1, 27])
    argument: (word [1, 28] - [1, 34])
    argument: (word [1, 35] - [1, 37])
    argument: (word [1, 38] - [1, 39])
    argument: (word [1, 40] - [1, 44]))
  (command [2, 0] - [2, 35]
    name: (command_name [2, 0] - [2, 2]
      (word [2, 0] - [2, 2]))
    argument: (word [2, 3] - [2, 9])
    argument: (word [2, 10] - [2, 13])
    argument: (word [2, 14] - [2, 23])
    argument: (word [2, 24] - [2, 27])
    argument: (word [2, 28] - [2, 35]))
  (command [3, 0] - [3, 3]
    name: (command_name [3, 0] - [3, 3]
      (word [3, 0] - [3, 3]))))
test.sh 0 ms    (MISSING "\n" [1, 11] - [1, 11])

I don't know for sure how to interpret the output, but it does make a good bit of sense. Maybe I can start to try to poke at the grammar changes until this changes to look more sensible.

[unphased]

I can note that this was (and still is) confusing:

❯ tree-sitter parse <(echo "abc def")                                           
Warning: You have not configured any parser directories!
Please run `tree-sitter init-config` and edit the resulting
configuration file to indicate where we should look for
language grammars.

(program [0, 0] - [1, 0]
  (command [0, 0] - [0, 7]
    name: (command_name [0, 0] - [0, 3]
      (word [0, 0] - [0, 3]))
    argument: (word [0, 4] - [0, 7])))

❯ tree-sitter init-config                         
Saved initial configuration to /Users/slu/Library/Application Support/tree-sitter/config.json

no idea what I'm supposed to place into /Users/slu/Library/Application Support/tree-sitter/config.json, but its contents are surely incorrect right now:

{
  "parser-directories": [
    "/Users/slu/github",
    "/Users/slu/src",
    "/Users/slu/source"
  ],
  "theme": {
    "function.builtin": {
      "bold": true,
      "color": 26
    },
    "keyword": 56,
    "type": 23,
    "comment": {
      "color": 245,
      "italic": true
    },
    "embedded": null,
    "constant.builtin": {
      "color": 94,
      "bold": true
    },
    "function": 26,
    "constructor": 136,
    "punctuation.bracket": 239,
    "module": 136,
    "tag": 18,
    "property": 124,
    "variable.builtin": {
      "bold": true
    },
    "constant": 94,
    "operator": {
      "color": 239,
      "bold": true
    },
    "string": 28,
    "type.builtin": {
      "bold": true,
      "color": 23
    },
    "punctuation.delimiter": 239,
    "attribute": {
      "italic": true,
      "color": 124
    },
    "variable.parameter": {
      "underline": true
    },
    "number": {
      "color": 94,
      "bold": true
    },
    "string.special": 30
  }
}

What are these integers? ansi 256 color codes?

[unphased]

Alright well I think the fix is gonna need to go somewhere inside src/scanner.cc and i need a lot more lexer/parser background before I could confidently say anything more.

[verhovsky]

The issue is the underscore in END_COMMENT is treated as the end of the delimiter. You can see this if you try this example

: <<EOF_FOO
sometext
EOF_FOO

vs

: <<EOF
sometext
EOF

on https://tree-sitter.github.io/tree-sitter/playground

Your test parses correctly, at least on the latest master of tree-sitter-bash, because it doesn't have the underscore.

You're right to notice that heredoc parsing in tree-sitter-bash is implemented in scanner.cc. tree-sitter-bash's heredoc implementation is pretty simplistic, looks like it only checks if the delimiter starts with a quote, quotes anywhere else aren't detected. For this issue I think you just have to change the logic here

tree-sitter-bash/src/scanner.cc

Lines 373 to 382 in b338fa9

	while (lexer->lookahead && ! (quote ? lexer->lookahead == quote :
	iswspace(lexer->lookahead))) {
	if (lexer->lookahead == '\\') {
	advance(lexer);
	if (! lexer->lookahead) return false;
	}
	empty = false;
	unquoted_word += lexer->lookahead;
	advance(lexer);
	}

but it seems like it might be more complicated than that.

i need a lot more lexer/parser background

I can recommend https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools . Stanford's compilers class recommends it too and also recommends Modern Compiler Implementation in Java (Second Edition) - Andrew Appel and Jens Palsberg (there's also an ML version) and Engineering a Compiler - Keith Cooper and Linda Torczon.

If you want to understand the real Bash parser, it's implemented with C and Bison:

https://www.gnu.org/software/bison/manual/bison.html#Concepts

for example Here Docs are implemented here:

https://github.com/bminor/bash/blob/ec8113b9861375e4e17b3307372569d429dec814/parse.y#L575-L581

and more interesting stuff happens here

https://github.com/bminor/bash/blob/ec8113b9861375e4e17b3307372569d429dec814/make_cmd.c#L558

[unphased]

@verhovsky could you help me understand what piece i'm missing when I added the new test in the corpus/commands.txt and the test run doesn't pick it up?

[verhovsky]

Try running tests with npm test instead? When I try tree-sitter test directly I get a dynamic library error on macOS but with npm test it works.

And sorry, I assumed it was being picked up and you just didn’t notice that it passes, but I was wrong. I just tried adding and running it and you’re right this is a bug.

[unphased]

I got

❯ npm run test               

> tree-sitter-bash@0.19.0 test
> tree-sitter test && script/parse-examples

Error opening dynamic library "/Users/slu/Library/Caches/tree-sitter/lib/bash.so"

Caused by:
    dlopen(/Users/slu/Library/Caches/tree-sitter/lib/bash.so, 0x0005): tried: '/Users/slu/Library/Caches/tree-sitter/lib/bash.so' (mach-o file, but is an incompatible architecture (have (arm64), need (x86_64)))

[verhovsky]

If you run

npm run build
npm test

do you still get the same error?

[unphased]

I got past the error by re-npm i and npm run build could then pass.

    ✓ Variable declaration: readonly
    ✓ Variable declaration: local
    ✓ Variable declaration: export
    ✓ Variable declaration: command substitution with semi-colon
    ✓ Expressions passed to declaration commands
    ✓ Unset commands
    ✓ Compound statements
  commands:
    ✓ Commands
    ✓ Commands with arguments
    ✓ Quoted command names
    ✓ Commands with numeric arguments
    ✓ Commands with environment variables
    ✓ Empty environment variables
    ✓ File redirects
    ✓ File redirects (noclobber override)
    ✓ Heredoc redirects
    ✓ Heredocs with variables
    ✓ Heredocs with file redirects
    ✓ Heredocs with pipes
    ✓ Heredocs with escaped expansions
    ✓ Quoted Heredocs
    ✓ Heredocs with indented closing delimiters
    ✓ Heredocs with empty bodies
    ✓ Heredocs with weird characters
    ✓ Herestrings
  crlf:
    ✓ Variables with CRLF line endings
examples/atom.sh                1 ms
examples/clean-old.sh           0 ms
examples/doc-build.sh           0 ms
examples/install.sh             0 ms
examples/release.sh             0 ms
examples/relocate.sh            0 ms
examples/test.sh                0 ms
examples/update-authors.sh      0 ms
slu@Stevens-MacBook-Pro:~/tree-sitter-bash MBP M1 Max[tmux] 03/27/23 15:43:52 11716
❯ d                                                                                                                                                                                                                                 master[✦]b338fa9[✎]11d21h42m
slu@Stevens-MacBook-Pro:~/tree-sitter-bash MBP M1 Max[tmux] 03/27/23 15:44:06 11717
❯ git --no-pager diff                                                                                                                                                                                                               master[✦]b338fa9[✎]11d21h42m
diff --git i/corpus/commands.txt w/corpus/commands.txt
index bca86b4..9c44a49 100644
--- i/corpus/commands.txt
+++ w/corpus/commands.txt
@@ -217,6 +217,18 @@ EOF

 (program (redirected_statement (command (command_name (word))) (heredoc_redirect (heredoc_start))) (heredoc_body))

+======================================
+Heredocs with closure not at BOL
+======================================
+: <<EOF
+even if EOF shows up in the middle of a line
+it should not terminate the heredoc
+EOF
+
+---
+
+(program (redirected_statement (command (command_name (word))) (heredoc_redirect (heredoc_start))) (heredoc_body))
+
 ======================================
 Quoted Heredocs
 ======================================

Still not picking up the test i added.

[verhovsky]

No idea. Try adding a syntax error to the s-expression (remove some of the )). Try deleting all the tests. Try compiling/installing the tree-sitter CLI locally, if that doesn't help then you could start adding debug print statements and re-compiling. First add a print to check it's reading the test file you edited, like the same actual path, then if its reading the updated contents and finally why its not parsing the test you added.

https://github.com/tree-sitter/tree-sitter/blob/1b1c3974f789a9bfaa31f493e6eaa212f13bdfb9/cli/src/test.rs#L344

[verhovsky]

This doesn't help you, but today I had the same issue because I didn't have a --- after the test input. So I had like

===========================================
My test
===========================================

echo foo

(a mistake)

instead of

===========================================
My test
===========================================

echo foo

---

(a mistake)