Re: Tree-sitter integration on feature/tree-sitter

[Yoav Marco <yoavm448@gmail.com>]

Looking at the code, isn't the while loop in treesit-query-capture
O(n²)? It essentially amounts to

  result = nil
  while (next capture group is avaliable) {
        captures = nil
        for (capture in capture group) {
          captures = cons(capture, captures)
        }
        captures = nreverse(captures)
        if (captures pass all predicates in their query)
           result = nconc(result, captures) // <----- THE OFFENDER
  }

A better way to do this would be to call nconc(captures, result) and
nreverse it all at the end instead of at the end of the for loop.

An even faster way would be to add unconditionally to result and roll it
back in case predicates fail. This doesn't use nconc at all:

  result = nil
  while (next capture group is avaliable) {
        prev_result = result;
        for (capture in capture group) {
          result = cons(capture, result)
        }
        if (captures *fail* at a predicate)
           result = prev_result
  }
  result = nreverse(result)


Context: I'm still working on profiling query compilation, and from what
I understand of gprof's output (not much) nconc indeed is very slow
here. Seeing nconc in the report is what made me look for nconc usage in
treesit-query-capture.

index % time    self  children    called     name
[1]     98.4    1.76    0.13     169+9031282 <cycle 1 as a whole> [1]
                1.59    0.00   41385             Fnconc <cycle 1> [2]
                0.06    0.05 2432616+3714        process_mark_stack <cycle 1> [24]
                0.08    0.00  147643             re_match_2_internal <cycle 1> [25]
                0.02    0.00    1707+56214       mark_char_table <cycle 1> [32]
                0.00    0.02      18             garbage_collect <cycle 1> [33]
                ...

The thing profiled is calling treesit-font-lock-fontify-region with c
queries accidentally on a go file with 8k lines. Still shouldn't take
the 2.2 seconds that it did, though.


> BTW, I would appreciate for someone to look at the manual and maybe
> touch up a bit, as I’m not a native speaker and might write something
> not very idiomatic/fluent.

One thing I've noticed - the manual node starts by introducing
treesit-available-p, a function that doesn't seem to exist anymore?