handle operator associavity

[oppiliappan]

Port of @oberblastmeister's changes from #35, should hopefully fix #74. I haven't fully wrapped my head around the parser code, but I think the changes I have ported are correct as far as I have tested.

Summary & Motivation

An attempt to split changes from that #35 into more reviewable chunks.

Backwards-incompatible changes

Changes syntax trees generated for binary expressions using right-associative operators.

Further context

Previously, all operators were parsed as left associative, certain operators such as concat (++), merge (//), and implication (->) are now parsed as right associative:

echo "false -> true -> false" | cargo run --quiet --example from-stdin
# parsed as `false -> (true -> false)`
# instead of `(false -> true) -> false`
NODE_ROOT 0..23 {
  NODE_BIN_OP 0..22 {
    NODE_IDENT 0..5 {
      TOKEN_IDENT("false") 0..5
    }
    TOKEN_WHITESPACE(" ") 5..6
    TOKEN_IMPLICATION("->") 6..8
    TOKEN_WHITESPACE(" ") 8..9
    NODE_BIN_OP 9..22 {
      NODE_IDENT 9..13 {
        TOKEN_IDENT("true") 9..13
      }
      TOKEN_WHITESPACE(" ") 13..14
      TOKEN_IMPLICATION("->") 14..16
      TOKEN_WHITESPACE(" ") 16..17
      NODE_IDENT 17..22 {
        TOKEN_IDENT("false") 17..22
      }
    }
  }
  TOKEN_WHITESPACE("\n") 22..23
}

[oppiliappan]

~Tests fail at the moment because expect.sh was not run after #67 (I think?), I'll open a separate PR for that.~ Oops, I should be using UPDATE_TESTS=1 for this.

[Ma27]

@nerdypepper SGTM, thanks :+1: . Just got a single question, after that it should be good to go :)

[oppiliappan]

Thanks for the review, this should be fixed now, do let me know if I should squash these or if they will will be squashed directly during merge.

[oberblastmeister]

once should not be removed. It is used to handle non-associative operators I think

[oberblastmeister]

It should be used to parse operators such as ==, >=, etc. which are not parsed correctly currently

[Ma27]

@oberblastmeister according to https://nixos.org/manual/nix/stable/expressions/language-operators.html ==/>= are neither left nor right-associative. The proper solution would be to create for e.g. a == b == c a node with a/b/c being children of it, but I think that this is good-enough for now. Or am I missing something? :)

[oberblastmeister]

Yes, they are non-associative. The proper solution is to just not parse them, and have a parse error.

[Ma27]

OK, I should've checked more closely how what Nix actually expects. First of all, this doesn't affect that PR IMHO, so we can merge this.

In fact, cargo run --example from-stdin <<< "a == b == c" already gives a parse error as expected, namely error: unexpected token at 7..11.

[oberblastmeister]

Yeah my bad, currently it parses it correctly. Also adding once for left and right would be redundant, so removing it makes sense.