|
|
|
|
|
|
by codebje
2022 days ago
|
|
|
The only place I can find that makes the 3-SAT claim is this comment thread. Nevertheless, there's two answers I can think of here. The first is simple (but IMO probably not right): 3-SAT is (probably) exponential, but the language definition document qualifies the linear claim by saying that macro expansion can also be exponential. The second is probably more accurate, though. General 3-SAT is (probably) exponential, but we're dealing with 3-SAT for a constant number of variables. You can solve 3-SAT by producing all combinations of values for the variables and testing the expression for each one, but while testing an expression should be linear there's an exponential number of combinations. If your combination count is constant, though, the whole complexity becomes linear ... with a shockingly bad constant factor. |
|
|
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.