Repository: tree-sitter/tree-sitter-haskell (language: python)

Issue:
Faster Scanner (part 2)
See [part 1](https://github.com/tree-sitter/tree-sitter-haskell/pull/52) for more info.

---

| | old | new | speedup |
|---|---|---|---|
| effects | 1.07s | 0.034s | 31.5x |
| postgrest | stackoverflow | 0.083s | ∞x |
| ivory | 10.16s | 0.225s | 45.16x |
| polysemy |  3.71s  | 0.089s | 41.7x |
| semantic |  50.62s | 1.089s | 46.5x |
| haskell-language-server | 24.28s | 0.504s | 48.2x |



**Overall speedup**: around 45x.


WASM build fails with error
Using the wasm generated with `npx tree-sitter build-wasm` fails with the following error:
```
Aborted(Assertion failed: undefined symbol `_ZNSt3__24cerrE`. 
    perhaps a side module was not linked in? 
    if this global was expected to arrive from a system library, 
    try to build the MAIN_MODULE with EMCC_FORCE_STDLIBS=1 in the environment)
```


Discussion / hints:
```
$ ./script/parse-example effects |& head -n 100
Successfully parsed 100.00% of 'effects' in 0.09s (38 of 38 files)
```

Original time: 1.09s

```
1.09 / 0.09 = 12.11
```
Nice work on this.

Having removed the use of closures, would it be straightforward to get this compiling without C++14 features? That would make this parser a bit easier to consume in downstream applications, and develop on a Mac.
awesome!!

> Having removed the use of closures, would it be straightforward to get this compiling without C++14 features? 

Yes I plan to remove the need for c++14, and maybe even convert the scanner to pure C :)
Oh, that’s interesting. I’d think that C++ would be useful just for std::vector. are you thinking that a dynamically sized array isn’t needed in the scanner?
> are you thinking that a dynamically sized array isn’t needed in the scanner?

I think we will need one, but I'm happy to implement my own if it means we can compile this as C.

While we have you here, would we be able to get your opinion on https://github.com/tree-sitter/tree-sitter-haskell/issues/41#issuecomment-1003353274? We think the scanner's probably running over the whole file (or a lot of it) every edit, but we're not sure if it should.
@414owen Amazing work! How far are you from hitting C++03? Once you do, I can check if the wasm can build successfully via the standard pathways now, and perhaps contribute some tests for that from #55.
> @414owen Amazing work! How far are you from hitting C++03?

Thanks :smile: . I'm actually pretty close to removing the last closure. I've removed the `Parser` type completely, now I just have to give the same treatment to `Condition`s and `Peek`s, which are way easier.

 I'd say I'll be done later today.
@wenkokke I've removed all the closures. It now compiles with `-std=c++11` but not `-std=c++03`.

I'll see what I can do.
```
$ ./script/parse-example effects |& head -n 100
Successfully parsed 100.00% of 'effects' in 0.0297s (38 of 38 files)
```

Original time: 1.09s

```
1.09 / 0.0297 = 36.7
```

There might be one or two micro-optimizations left (PEEKing before taking some code paths?)
As well as maybe decreasing the necessary re-computations (see https://github.com/tree-sitter/tree-sitter-haskell/issues/41#issuecomment-950424044)

But this will in any case let us edit 36x larger files than before :tada:  
@wenkokke I've added c++03 support  here: https://github.com/414owen/tree-sitter-haskell/pull/1
With your current faster-scanner branch, you've got the patch to tree-sitter down to:
```diff
--- a/lib/binding_web/exports.json
+++ b/lib/binding_web/exports.json
@@ -3,6 +3,9 @@
   "_free",
   "_malloc",

+  "__ZNSt3__25ctypeIcE2idE",
+  "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE25__init_copy_ctor_externalEPKcm",
+
   "__ZNKSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE4copyEPcmm",
   "__ZNKSt3__220__vector_base_commonILb1EE20__throw_length_errorEv",
   "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE6__initEPKcm",
```

See https://github.com/wenkokke/tree-sitter-haskell/tree/tree-sitter-haskell-wasm-faster-scanner.
@tek This is ready for review, when you have a chance.

All tests pass. Any further changes will probably be cosmetic (moving things around, rather than changing what they do).
@tek I have an updated version of #55 for when this pull request is merged
awesome!
Compiling `web-tree-sitter` using `ASSERTIONS=1`, via `script/build-wasm --debug`, refines the error message to:
```
Aborted(Assertion failed: undefined symbol `_ZTVN10__cxxabiv117__class_type_infoE`. 
    perhaps a side module was not linked in?
    if this global was expected to arrive from a system library, 
    try to build the MAIN_MODULE with EMCC_FORCE_STDLIBS=1 in the environment)
```
Compiling with `EMCC_FORCE_STDLIBS=1` does not make a difference.
The issue is that `web-tree-sitter` performs dead code elimination, and eliminates all but a select few functions listed in [exports.json](https://github.com/tree-sitter/tree-sitter/blob/master/lib/binding_web/exports.json). The following patch to `tree-sitter` ensures that the functions used by `tree-sitter-haskell` are kept:
```diff
diff --git a/lib/binding_web/exports.json b/lib/binding_web/exports.json
index e0b3f718..36342e52 100644
--- a/lib/binding_web/exports.json
+++ b/lib/binding_web/exports.json
@@ -3,6 +3,15 @@
   "_free",
   "_malloc",
 
+  "__ZNSt3__24cerrE",
+  "__ZNSt3__25ctypeIcE2idE",
+  "__ZTVN10__cxxabiv117__class_type_infoE",
+  "__ZTVN10__cxxabiv120__si_class_type_infoE",
+  "__ZTVN10__cxxabiv120__function_type_infoE",
+  "__ZTVN10__cxxabiv119__pointer_type_infoE",
+  "__ZTVN10__cxxabiv121__vmi_class_type_infoE",
+  "___cxa_pure_virtual",
+
   "__ZNKSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE4copyEPcmm",
   "__ZNKSt3__220__vector_base_commonILb1EE20__throw_length_errorEv",
   "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE6__initEPKcm",
```
However, I suppose such a patch is unlikely to be accepted. Is the use of these functions really worth the hassle?
With the above patch applied to `tree-sitter` running a simple parser test results in the following error:
```
TypeError: Cannot read properties of undefined (reading 'apply')
    at e.<computed> (tree-sitter-haskell/node_modules/web-tree-sitter/tree-sitter.js:1:10543)
    at wasm://wasm/00ea81ae:wasm-function[2590]:0xc09ac
    at e.<computed> (tree-sitter-haskell/node_modules/web-tree-sitter/tree-sitter.js:1:10543)
    at wasm://wasm/00ea81ae:wasm-function[2962]:0xc55b5
    at e.<computed> (tree-sitter-haskell/node_modules/web-tree-sitter/tree-sitter.js:1:10543)
    at wasm://wasm/00ea81ae:wasm-function[2961]:0xc55a8
    at e.<computed> (tree-sitter-haskell/node_modules/web-tree-sitter/tree-sitter.js:1:10543)
    at wasm://wasm/00ea81ae:wasm-function[2939]:0xc5468
    at e.<computed> (tree-sitter-haskell/node_modules/web-tree-sitter/tree-sitter.js:1:10543)
    at wasm://wasm/00ea81ae:wasm-function[2583]:0xc089a
```
To help reproducing these errors, here is a simple script which uses the generated wasm, to be called as `script/parse-example.js`:
```javascript
#!/usr/bin/env node

const fs = require('fs')
const Parser = require('web-tree-sitter');

if (process.argv.length < 3) {
  console.log('Usage: script/parse-example.js <haskell-file>')
  process.exit(1)
}

const fileName = process.argv[2]
const sourceCode = fs.readFileSync(fileName, 'utf8')

Parser.init().then(() => {
  Parser.Language.load('tree-sitter-haskell.wasm').then((Haskell) => {
    const parser = new Parser;
    parser.setLanguage(Haskell);
    const tree = parser.parse(sourceCode);
    console.log(tree.rootNode.toString());
  });
});
```
The following patch to `web-tree-sitter` makes `tree-sitter-haskell` work:
```diff
diff --git a/lib/binding_web/exports.json b/lib/binding_web/exports.json
index e0b3f718..3a43ae33 100644
--- a/lib/binding_web/exports.json
+++ b/lib/binding_web/exports.json
@@ -3,6 +3,17 @@
   "_free",
   "_malloc",
 
+  "__ZNSt3__24cerrE",
+  "__ZNSt3__25ctypeIcE2idE",
+  "__ZTVN10__cxxabiv117__class_type_infoE",
+  "__ZTVN10__cxxabiv120__si_class_type_infoE",
+  "__ZTVN10__cxxabiv120__function_type_infoE",
+  "__ZTVN10__cxxabiv119__pointer_type_infoE",
+  "__ZTVN10__cxxabiv121__vmi_class_type_infoE",
+  "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE25__init_copy_ctor_externalEPKcm",
+  "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE25__init_copy_ctor_externalEPKcm",
+  "___cxa_pure_virtual",
+
   "__ZNKSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE4copyEPcmm",
   "__ZNKSt3__220__vector_base_commonILb1EE20__throw_length_errorEv",
   "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE6__initEPKcm",
```
Created two issues which may help debug such problems in the future (https://github.com/tree-sitter/tree-sitter/issues/1565 and https://github.com/tree-sitter/tree-sitter/issues/1566).

Fix patch:
diff --git a/Makefile b/Makefile
new file mode 100644
index 00000000..0d3fe27d
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,42 @@
+WEB_TREE_SITTER=README.md package.json tree-sitter-web.d.ts tree-sitter.js tree-sitter.wasm
+TREE_SITTER_VERSION=v0.20.1
+
+all: node_modules/web-tree-sitter tree-sitter-haskell.wasm
+
+# build parser.c
+src/parser.c: grammar.js
+	npx tree-sitter generate
+
+# build patched version of web-tree-sitter
+node_modules/web-tree-sitter:
+	if [ ! -d "tmp/tree-sitter" ]; then git clone https://github.com/tree-sitter/tree-sitter.git tmp/tree-sitter; fi
+	cd tmp/tree-sitter && git checkout $(TREE_SITTER_VERSION)
+	cp tree-sitter.patch tmp/tree-sitter/
+	cd tmp/tree-sitter\
+		&& git apply tree-sitter.patch\
+		&& ./script/build-wasm
+	mkdir -p node_modules/web-tree-sitter
+	cp tmp/tree-sitter/LICENSE node_modules/web-tree-sitter
+	cp $(addprefix tmp/tree-sitter/lib/binding_web/,$(WEB_TREE_SITTER)) node_modules/web-tree-sitter
+	rm -rf tmp/tree-sitter
+
+# build web version of tree-sitter-haskell
+# NOTE: requires patched version of web-tree-sitter
+tree-sitter-haskell.wasm: src/parser.c src/scanner.cc
+	emcc                                             \
+		-o tree-sitter-haskell.wasm                    \
+		-Os                                            \
+		-std=c++11                                     \
+		-s WASM=1                                      \
+		-s SIDE_MODULE=1                               \
+		-s TOTAL_MEMORY=33554432                       \
+		-s NODEJS_CATCH_EXIT=0                         \
+		-s EXPORTED_FUNCTIONS=["_tree_sitter_haskell"] \
+		-fno-exceptions                                \
+		-Wno-reorder-init-list                         \
+		-Wno-c99-designator                            \
+		-I src                                         \
+		-xc++                                          \
+		src/scanner.cc                                 \
+		src/parser.c
+
diff --git a/package.json b/package.json
index 1b84df49..ce5b47b2 100644
--- a/package.json
+++ b/package.json
@@ -19,7 +19,8 @@
   },
   "scripts": {
     "test": "tree-sitter test",
-    "examples": "script/parse-examples"
+    "examples": "script/parse-examples",
+    "examples-wasm": "script/parse-examples wasm"
   },
   "tree-sitter": [
     {
diff --git a/script/parse-example b/script/parse-example
index f5a68b65..1277dfdd 100755
--- a/script/parse-example
+++ b/script/parse-example
@@ -1,13 +1,20 @@
 #!/usr/bin/env bash
 
+# Usage: script/parse-examples [repo_name] [native|wasm]
+
+# Exit immediately if a command exits with a non-zero status.
 set -e
 
-name=$1
-root=$(dirname $(dirname $(realpath "$0")))
-cd $root
+# Change directory to project root.
+cd "$(dirname "$0")/.."
 
+# Get the repository name
+name=$1
 repo=examples/$name
 
+# Parse examples in 'native' or 'wasm' mode.
+mode=${2:-native}
+
 known_failures=$(cat "script/known-failures-$name.txt")
 examples_to_parse=$(
   for example in $(find "$repo" -name '*.hs'); do
@@ -17,11 +24,21 @@ examples_to_parse=$(
   done
 )
 
-# ensure the scanner was recompiled
-tree-sitter test -f 'just compile it' >/dev/null
+if [ "$mode" == "native" ]; then
+  # Ensure the scanner was recompiled
+  tree-sitter test -f 'just compile it' >/dev/null
+elif [ "$mode" == "wasm" ]; then
+  # Ensure tree-sitter-haskell.wasm was compiled
+  make node_modules/web-tree-sitter
+  make tree-sitter-haskell.wasm
+fi
 
 start=$(date '+%s.%N')
-echo $examples_to_parse | xargs -n 2000 tree-sitter parse -q
+if [ "$mode" == "native" ]; then
+  echo $examples_to_parse | xargs -n 2000 tree-sitter parse -q
+elif [ "$mode" == "wasm" ]; then
+  echo $examples_to_parse | xargs -n 2000 ./script/tree-sitter-parse.js
+fi
 end=$(date '+%s.%N')
 
 skipped=$( echo $known_failures | wc -w )
diff --git a/script/parse-examples b/script/parse-examples
index 72cc4f3b..8184fe5e 100755
--- a/script/parse-examples
+++ b/script/parse-examples
@@ -1,9 +1,17 @@
 #!/usr/bin/env bash
 
+# Usage: script/parse-examples [native|wasm]
+
+# Exit immediately if a command exits with a non-zero status.
 set -e
 
+# Parse examples in 'native' or 'wasm' mode.
+mode=${1:-native}
+
+# Change directory to project root.
 cd "$(dirname "$0")/.."
 
+# Clone a GitHub repository to the examples directory
 # clone_repo OWNER NAME SHA
 function clone_repo {
   owner=$1
@@ -28,5 +36,5 @@ clone_repo github semantic b162132339622fe1e80e243f630fe092d5c0cbe1
 clone_repo haskell haskell-language-server d397ef491ef1689d43028f4d3d01a42118292235
 
 for name in effects postgrest ivory polysemy semantic haskell-language-server; do
-  script/parse-example $name
+  script/parse-example $name $mode
 done
diff --git a/script/tree-sitter-parse.js b/script/tree-sitter-parse.js
new file mode 100755
index 00000000..d206d177
--- /dev/null
+++ b/script/tree-sitter-parse.js
@@ -0,0 +1,21 @@
+#!/usr/bin/env node
+
+const fs = require('fs');
+const Parser = require('web-tree-sitter');
+
+if (process.argv.length < 3) {
+  console.log('Usage: script/tree-sitter-parse.js <haskell-file..>')
+  process.exit(1)
+}
+
+Parser.init().then(() => {
+  Parser.Language.load('tree-sitter-haskell.wasm').then((Haskell) => {
+    const parser = new Parser;
+    parser.setLanguage(Haskell);
+    for (let i = 2; i < process.argv.length - 1; i++) {
+      const fileName = process.argv[2]
+      const sourceCode = fs.readFileSync(fileName, 'utf8')
+      const tree = parser.parse(sourceCode);
+    }
+  });
+});
diff --git a/tree-sitter-haskell.wasm b/tree-sitter-haskell.wasm
new file mode 100755
index 00000000..500b794f
Binary files /dev/null and b/tree-sitter-haskell.wasm differ
diff --git a/tree-sitter.patch b/tree-sitter.patch
new file mode 100644
index 00000000..d33dfad0
--- /dev/null
+++ b/tree-sitter.patch
@@ -0,0 +1,12 @@
+--- a/lib/binding_web/exports.json
++++ b/lib/binding_web/exports.json
+@@ -3,6 +3,9 @@
+   "_free",
+   "_malloc",
+
++  "__ZNSt3__25ctypeIcE2idE",
++  "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE25__init_copy_ctor_externalEPKcm",
++
+   "__ZNKSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE4copyEPcmm",
+   "__ZNKSt3__220__vector_base_commonILb1EE20__throw_length_errorEv",
+   "__ZNSt3__212basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE6__initEPKcm",


Test patch:
diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml
index e2abbab6..3dcace81 100644
--- a/.github/workflows/test.yml
+++ b/.github/workflows/test.yml
@@ -22,6 +22,7 @@ jobs:
       - run: npm run examples
         env:
           CXX: g++-9
+      - run: npm run examples-wasm
   # build-mac:
   #   runs-on: macos-latest
   #   steps: