More useful (or less confusing) parse errors on unexpected token

[john-h-kastner-aws]

Category

Other

Describe the feature you'd like to request

An unexpected token causes the parser to emit an error message listing every token in would have accepted in that position.

E.g., on permit(principal, action, resource; (missing the closing paren) the error text is

Error: cedar_policy_core::parser::to_cst_error

  × unexpected token `;`
   ╭─[a.cedar:1:1]
 1 │ permit(principal, action resource;
   ·                                  ┬
   ·                                  ╰── expected `!=`, `%`, `&&`, `(`, `)`, `*`, `+`, `,`, `-`, `.`, `/`, `:`, `::`, `<`, `<=`, `==`, `>`, `>=`, `[`, `]`, `{`, `||`, `}`, `else`, `has`, `in`, `like`, or `then`
   ╰────

The list of expected tokens isn't helpful, and potentially makes the error more confusing that it would be otherwise.

This was brought up recently due to a schema parsing error in #149 where this sort of overly verbose error was caused by an empty string used for an entity type name.

Some solutions that come to mind:

• Expand what tokens the parer expects so that more error reporting can be handled in CST -> AST conversion where we have full control over error messages and can inspect the surrounding CST to generate better errors.
• Restrict what tokens the parser expects so that there will be fewer tokens in the expected tokens list.
• Hide the long token lists. Maybe they're confusing enough that it makes sense to hide it altogether.

[john-h-kastner-aws]

#218 pulls in a lalrpop update that improves these errors somewhat

The example in the issue will have the smaller token list

`!=`, `)`, `,`, `:`, `<`, `<=`, `==`, `>`, `>=`, or `in`

Notably, the token list does not include tokens like ||, [, or like. These tokens could never parse in a policy in that position, so including them in the expected tokens list was incorrect of lalrpop. All of the tokens still being suggested can parse in a policy in that position.

Not all of the tokens can appear there in a valid policy, so there is room for improvement. Other parse errors still have much longer expected tokens lists. For example:

$ cargo run check-parse <<<'permit(principal, action, resource) when {'
    Finished dev [unoptimized + debuginfo] target(s) in 0.10s
     Running `target/debug/cedar check-parse`
Error: cedar_policy_core::parser::to_cst_error

  × failed to parse policy set
  ╰─▶ unexpected end of input
   ╭─[<stdin>:1:1]
 1 │ permit(principal, action, resource) when {
   ·                                           ▲
   ·                                           ╰── expected `!`, `(`, `-`, `[`, `{`, `}`, `action`, `context`, `else`, `false`, `forbid`, `has`, identifier, `if`, `in`, `like`, number, `permit`, `principal`, `?principal`, `resource`, `?resource`, string literal, `then`, `true`, `unless`, or `when`
   ╰────

All of the tokens can parse into a CST at that location, but some like has will never work given our CST to AST conversion rules.

[john-h-kastner-aws]

Further improved on in #668. With that PR permit(principal, action, resource) when { gives a much nicer list of tokens: expected `!`, `(`, `-`, `[`, `{`, `}`, `false`, identifier, `if`, number, `?principal`, `?resource`, string literal, or `true`.

Some cases where the unexpected token errors can still be improved are noted in the comments on tests cases added with that PR.

A particular case that stand out is permit(principal, action, resource) when { principal is. We claim to expect expected `!`, `(`, `-`, `[`, `{`, `false`, identifier, `if`, number, `?principal`, `?resource`, string literal, or `true`, but only an identifier is actually valid. This is a side effect of #491 where we changed the CST grammar to parse the right operand of is as an Add rather than a Name. A similar issue applies like where the right operand must be a pattern literal, and record literals where attribute names must be literal names.

[hakanson]

Some additional parse errors.

This one tries to parse permit (principal, action, resource,); which I think should error on the , and not the )

$ cedar check-parse -p badcomma.cedar 
  × failed to parse policy set
  ╰─▶ unexpected token `)`
   ╭─[badcomma.cedar:1:37]
 1 │ permit (principal, action, resource,);
   ·                                     ┬
   ·                                     ╰── expected `action`, `context`, `else`, `false`, `forbid`, `has`, identifier, `if`, `in`, `is`, `like`, `permit`, `principal`, `resource`, `then`, `true`, `unless`, or `when`
   ╰────

Counter to this one tries to parse permit (principal, action, resource.); which is on the right character, but gives me invalid expectations (e.g if I try and use >= I get "not a valid policy scope constraint: >=").

$ cedar check-parse -p badperiod.cedar 
  × failed to parse policy set
  ╰─▶ unexpected token `.`
   ╭─[badperiod.cedar:1:36]
 1 │ permit (principal, action, resource.);
   ·                                    ┬
   ·                                    ╰── expected `!=`, `)`, `,`, `:`, `<`, `<=`, `=`, `==`, `>`, `>=`, `in`, or `is`
   ╰────

[john-h-kastner-aws]

Dropping this link here: https://lalrpop.github.io/lalrpop/tutorial/008_error_recovery.html

I think we should be able to use lalrpops error recovery mechanism to improve these errors substantially.