Provide formatting-insensitive structural equality for parsed CEL expressions

[zacharyblasczyk]

Feature request checklist

• There are no issues that match the desired change
• The change is large enough it can't be addressed with a simple Pull Request
• If this is a bug, please file a Bug Report.

Change

Provide, or document an existing supported mechanism for, comparing two
parsed CEL expressions by structure while ignoring source formatting and
parse metadata.

The intended comparison would:

• ignore whitespace, redundant parentheses, source positions, and expression
  node IDs;
• treat equivalent literal spellings as equal when they parse to the same
  literal value;
• work for macro-backed expressions such as exists, all, and map;
• compare expression structure rather than rendered text; and
• avoid logical or algebraic equivalence. For example, a && b and b && a
  would remain different.

A concrete downstream use case is configuration reconciliation. A Terraform
provider may receive a CEL expression from configuration, while the backing
API returns the same expression with different whitespace or fully
parenthesized formatting. Treating those values as different produces a
perpetual plan diff even though the parsed expression has not changed.

One example of this use case and its current workaround is:

wandb/terraform-provider-orca#32

The current cel-go APIs provide the underlying pieces, but not an explicit
equality contract:

• cel.AstToString produces stable, semantically equivalent text when it can
  unparse the expression.
• cel.EnableMacroCallTracking allows macro calls to be reconstructed during
  unparsing.
• Comparing the expression protobufs with proto.Equal works for the cases
  tested, but it is unclear whether equality across independently parsed ASTs,
  including the treatment of expression IDs, is a supported guarantee.
• (*cel.Ast).Expr() is deprecated in favor of cel.AstToParsedExpr, but
  neither API documents structural comparison as a supported use case.

An explicit helper would let embedders use this behavior without depending on
unparser behavior or undocumented protobuf details.

Example

A possible API might look like this; the exact name and package are open for
discussion:

env, _ := cel.NewEnv()

left, _ := env.Parse(`
    resource.kind == "service"
      && resource.name == "api"
`)
right, _ := env.Parse(`
    (resource.kind == "service") &&
    (resource.name == "api")
`)

same := cel.AstStructurallyEqual(left, right)
// same == true

macroLeft, _ := env.Parse(`[1,2].exists(x,x>1)`)
macroRight, _ := env.Parse(`([1, 2].exists(x, x > 1))`)

sameMacro := cel.AstStructurallyEqual(macroLeft, macroRight)
// sameMacro == true

different, _ := env.Parse(`resource.name == "worker"`)

sameExpression := cel.AstStructurallyEqual(left, different)
// sameExpression == false

The implementation could instead live in common/ast, for example:

func ExprEqual(left, right ast.Expr) bool

The important part is a documented contract that ignores IDs and source
metadata while comparing the parsed expression structure.

Alternatives considered

1. Compare cel.AstToString output

   This works for many expressions when macro-call tracking is enabled, but
   equality becomes dependent on an unparser that can return errors. Unparser
   behavior also evolves independently; for example, parser/unparser: AstToString produces unparseable output for doubles in scientific notation #1325 required parser/unparser: emit valid CEL for doubles in scientific notation #1326 to
   fix invalid output for doubles in scientific notation.

2. Compare expression protobufs with proto.Equal

   Comparing only the Expr fields from cel.AstToParsedExpr works for the
   formatting, parenthesization, and macro cases tested. However, it is not
   documented whether expression IDs are guaranteed to be stable across
   independent parses or whether this is a supported equality mechanism.

   If this is already the recommended approach, documenting that guarantee
   would satisfy this request without adding another API.

3. Implement an application-specific recursive AST visitor

   This avoids unparsing but duplicates cel-go's handling of expression kinds,
   literals, comprehensions, optional syntax, and future AST additions in each
   embedding application.

4. Continue comparing raw source strings

   This cannot distinguish formatting-only changes from actual expression
   changes and causes persistent configuration diffs.

[zacharyblasczyk]

@TristonianJones It looks like you are the primary maintainer so let me know if there is an alternative I didn't consider or if you like the proposal, a draft implementation I can contribute with.

[TristonianJones]

The AstToParsedExpr or AstToCheckedExpr should provide a normalized proto that's useful for equivalence checking. When testing the expression for equivalence, only use the Expr message and ignore the id field as the ids are not guaranteed to be stable between compilations. We can formalize the comparison via a small helper library under tools.