[Proposal] Stable AST

[caiorcferreira]

Motivation

Implementing features such as policy mutation, JSON support, Schema support, and partial evaluation today is harder because we don't have a stable AST.

Proposal

We need to follow an incremental plan to introduce a stable AST, migrate internals, and introduce new features based on the AST. The plan is based on the approach used by Cedar Rust:

1. Cedar Rust splits the Cedar language parsing into two steps: first, it converts the raw content into a Concrete Syntax Tree (CST), and then simplifies it to an AST. I propose we follow the same approach. To build the CST, we should use a lexer/parser generator. This will reduce the burden of keeping up with the upstream changes. The generated parser will create the CST.
2. Change toEval to accept the new AST. Type implementations such as EntityUID, IPAddr, and Decimal will probably remain the same and be used inside the stable AST.
3. Implement a JSON unmarshaler and a marshaler. They will handle the translation between the AST and serializable intermediate type. Cedar Rust also uses this strategy, for example, the types EntityJson and EntityJsonParser, respectively.
4. Supporting policy mutation can produce a data race like an evaluation starts recursing the policy, and a different goroutine changes some part of it, producing an unexpected result. We should keep the evaluation in a PolicySet immutable but expose the Policies ASTs with a read-only method. Suppose the function that creates a PolicySet from a list of Policy ASTs is made public. In that case, the application can modify the ASTs that originated the evaluator and create a new PolicySet. The application is responsible for coordinating the replacement of the PolicySet with the concurrency control it seed fit.

[cdisselkoen]

Noting that the Cedar policy JSON format (documented here) is indeed stable, and is effectively a stable version of the Rust AST (which is unstable and internal). I'd recommend that the Go implementation use this same policy JSON format as its stable AST.

Similarly, Cedar schemas have two different stable formats, human-readable and JSON.

[philhassey]

@cdisselkoen I noticed this coming in: https://github.com/cedar-policy/cedar-docs/pull/109

Does that mean there is a new / somewhat better JSON format, and maybe we should just skip ahead to that?

Thanks! -Phil

[cdisselkoen]

This is the same JSON format. Previously, only JSON for a single policy was defined. https://github.com/cedar-policy/cedar-docs/pull/109 proposes JSON for a policy set, and is planned to ship in Cedar 4.0. Inside the new policy-set JSON format, each policy is still represented in the same stable policy JSON format.

[philhassey]

With v0.2.0 we have an programmatic AST.

https://github.com/cedar-policy/cedar-go/releases