16$: Fix precedence bugs

[strager]

I added a test for precedence, test_parse_expression.precedence. There are some known bugs, and the test is incomplete (so there might be more bugs). Let's fix everything once and for all, at least for normal expressions.

• [ ] #1143

[strager]

Idea for binary precedence:

As I've found binary precedence bugs, I've been adding new AST nodes. One idea is to keep the AST flat, as originally planned, but when we do need precedence, we re-parse using an efficient algorithm.

For example:

selection === "agree" || "strongly agree" === selection
//        ^^^         ^^                  ^^^

Let's say we want to check for E0190: missing comparison; '===' does not extend to the right side of '||'. A binary AST node has a list of operators: ===, ||, and ===.

We ask the algorithm to tell us about || operators. It scans the list of operators for a ||. When it finds the ||, the algorithm scans left of the || until it finds something with an equal or lower precedence level. Then it scans right of the || until it finds something with an equal or lower precedence level. The result of the algorithm is the stuff to the left (selection === "agree") and the stuff to the right ("strongly agree" === selection). The algorithm actually would output a list of such things. I'm thinking of an interface like this:

// maybe also iterate_binary_deep
template <class OperatorPredicate>
void iterate_binary(
  expression::binary* ast,
  OperatorPredicate is_interesting_operator,
  function_ref<void(expression::binary_slice lhs, token_type op, expression::binary_slice rhs)>);

// Example call:
iterate_binary(ast, [](token_type t) { return t == token_type::pipe_pipe; },
  [&](expression::binary_slice lhs, token_type, expression::binary_slice rhs) {
    /* if lhs is an === but rhs is a literal, report diagnostic */
  });

It might also be useful to have a helper function to query the highest precedence of a binary AST node or slice. This would make it easier for E0190's check to look see whether the lhs of || is a == or something uninteresting (e.g. +):

class expression::binary {
  ...
  // Returns an index into operators_.
  int highest_precedence() const;
  // A slice would return std::optional<int>, because a slice might be have no operators.
};

To make the left+right searching algorithm efficient, we could encode precedence levels inside token_type. For example:

enum class token_type {
  ...

  // lower precedence level
  equal_equal = 0x10,  // ==
  bang_equal = 0x11, // !=

  plus = 0x20,  // +
  minus = 0x21,  // -

  // higher precedence level
  star = 0x30, // *
  slash = 0x31, // /

  ...
};

int compare_precedence(token_type a, token_type b) {
  int a_level = (a & 0xf0);
  int b_level = (b & 0xf0);
  if (a_level < b_level) return -1;
  if (a_level > b_level) return +1;
  return 0;
}