Hi, I'm Tristan (@TristonianJones), the lead of the CEL project here at Google which has a few core maintainers as well as a number of regular contributors: https://github.com/google/cel-spec/blob/master/MAINTAINERS.m...

Macros are considered an optional feature of the language because they can: a) easily be disabled, b) have no dedicated syntax beyond that defined for core CEL.

CEL supports subsetting and extension which means you can actually turn off built-in features in order to guarantee a sort of maximal compute / memory impact that an expression might have while still augmenting the core feature set in order to tailor it to your use case.

Bounded iteration is possible via macros, and such iterations can be nested; thus, you can have high polynomial time expressions, but only if you choose to permit them and many use cases (like IAM Conditions) don't. This is different from OPA Rego or HashiCorp Sentinel in that these features are baked into the syntax and impossible to turn off with 100% certainty.

Since you can't declare functions or variables within CEL, the environment of an expression (the variables and functions it can use) is completely controlled by the host process. The environment acts like a sandbox of sorts, but one specifically chosen by the application and not a general purpose mechanism like a hypervisor or sandbox like WebAssembly.

Hi, I'm Jim (@JimLarson), another CEL maintainer. Yes, the full language spec is more clear about the performance limits, and macros can easily result in exponential time or space complexity. The original claim could be for either the macro version or the equivalent expanded version, e.g. "[true, false].exists(v1, [true, false].exists(v2, ... [true, false].exists(vN, (v1 || !v2 || v3) && (v2 || v3 || !v4) && ...)...))", etc. But it doesn't require much power in the language to express this kind of "solver" - there's still no general recursion.