DOCSEARCHbyAlgolia
Submit Docs

Common Expression Language (CEL) Specification

repository·master·Indexed 26 days ago

https://github.com/cel-expr/cel-spec

Documentation for the Common Expression Language (CEL), a fast, safe, and extensible expression language designed for security policies and protocols. It covers language characteristics, operator precedence, name resolution, and supported value types. The spec details required components for implementation—including the AST, compiler, and evaluator—and provides guidance on serializing expressions using canonical protocol buffers.

Tokens
10.6K
Snippets
18
Records
72
Agent score
86%

What's inside cel-spec

  1. Overview of Common Expression Language (CEL)

    master

    Common Expression Language (CEL) is a language designed for expression evaluation with common semantics to enable interoperability across different applications. It is optimized for security policies and protocols where expressions need to be portable across programming languages and platforms.

    Key Characteristics:

    • Small & Fast: Evaluates in linear time, is mutation-free, and is not Turing-complete to ensure high performance and safety.
    • Extensible: Designed to be embedded in applications, allowing developers to provide custom functions and data via a context.
    • Developer-friendly: Uses a syntax similar to C, C++, Java, and JavaScript.

  2. Understand CEL evaluation semantics

    master

    CEL expressions evaluate deterministically to either a value or an error based on the evaluation environment.

    Key evaluation rules:

    • Literals: Evaluate to their represented values (numbers, booleans, strings, bytes, null).
    • Variables: Looked up in the binding environment; unbound variables cause an error.
    • Aggregates (List, Map, Message): Sub-expressions are evaluated. If any sub-expression errors, the whole expression errors. If types are incorrect, it errors.
    • Operators: Translated into functions (e.g., e1 + e2 becomes _+_(e1, e2)).
    • Functions: Arguments are evaluated; if any error, the function errors. Otherwise, it is dispatched based on argument types.

    Note on Side Effects: CEL is free of side effects, so the order of evaluation among sub-expressions is not guaranteed. If multiple sub-expressions error, the specific error propagated is not specified.

  3. Understand CEL performance and complexity

    master

    CEL specifies the time and space computational complexity of language constructs to ensure reliable containment when executing untrusted expressions.

    Abstract Size Measurements

    Complexity is measured using abstract sizes of values:

    • string: length (number of code points) + constant.
    • bytes: length (number of bytes) + constant.
    • list: sum of sizes of entries + constant.
    • map: sum of (key size + value size) for all entries + constant.
    • message: sum of the size of all fields + constant.
    • Other values: constant size.

    Time Complexity Patterns

    • Constant time: Simple expressions (e.g., x), list index operators, and message select operators.
    • Linear time: size() on lists/maps (proportional to length, not total size).
    • Product time (O(N*M)): Map index/select operators, the in operator, and string functions like contains, startsWith, endsWith, and matches.

  4. Understand Common Expression Language (CEL) basics

    master
    Common Expression Language (CEL) is a simple expression language built on top of protocol buffer types. It is designed to allow simple computations on structured data, supporting boolean operators, relations, arithmetic, string/byte operations, and operations for lists and maps. CEL can be used with both static and dynamic typing (gradual typing).

  5. Understand CEL language characteristics

    master

    Common Expression Language (CEL) is designed with the following properties:

    • Memory-safe: Prevents out-of-bounds array indexes and use-after-free pointer dereferences.
    • Side-effect-free: Programs only compute an output from inputs without modifying external state.
    • Terminating: Programs are guaranteed not to loop forever.
    • Strongly-typed: Values have well-defined types, and operators/functions enforce type constraints.
    • Dynamically-typed: Types are associated with values at runtime rather than variables.
    • Gradually-typed: Supports an optional type-checking phase before runtime to catch type violations.

  6. Serialize CEL Expressions for Persistence or Communication

    master

    When you need to persist expressions or communicate them across processes, it is highly recommended to serialize the type-checked expression as a protocol buffer. The CEL team maintains canonical, wire-compatible protocol buffers for ASTs:

    • CEL canonical: Located in proto/cel/expr within the repository.
    • CEL v1alpha1: Located in google/api/expr/v1alpha1 within the googleapis repository.

  7. Avoid exponential complexity in CEL macros

    master

    Macros can lead to exponential time and space complexity if nested or chained.

    Macro Complexity Rules

    • has(e.f): Space is constant. Time is linear for maps, constant for messages.
    • e.all(x, p), e.exists(x, p), e.exists_one(x, p): Time is the sum of time of p for each element of e. Space is constant.
    • e.map(x, t): Time is the sum of time of t for each element of e. Space is the sum of space of t for each element of e + constant.
    • e.filter(x, t): Time is the sum of time of t for each element of e. Space is the space of e.

    Dangerous Patterns

    Avoid deeply nested macros like:

    [0,1].all(x, [0,1].all(x, ... [0,1].all(x, 1/0)...))

    Or chained maps like:

    ["foo","bar"].map(x, [x+x,x+x]).map(x, [x+x,x+x])...
    [0,1].all(x,
  [0,1].all(x,
    ...
      [0,1].all(x, 1/0)...))

  8. Use logical operators and short-circuiting

    master

    CEL uses specific semantics for logical operators:

    • Conditional Operator (e ? e1 : e2): Evaluates to e1 if e is true, otherwise e2.
    • Boolean Operators (&& and ||): These are commutative and do not guarantee traditional left-to-right short-circuiting. If an operand uniquely determines the result (e.g., false for &&), the other operand might still be evaluated. If that evaluation errors, the error may be ignored.

    To achieve traditional McCarthy (left-to-right) short-circuiting:

    • Rewrite e1 && e2 as e1 ? e2 : false.
    • Rewrite e1 || e2 as e1 ? true : e2.

  9. Use Gradual Type Checking in CEL

    master

    CEL is dynamically-typed, but supports an optional static type-checking phase. This phase attempts to deduce types for expressions and sub-expressions to identify potential runtime errors like no_matching_overload and no_such_field before execution.

    Key Concepts

    • Static vs. Dynamic: Expressions that avoid dynamic features (like Struct, Value, or Any) can be fully statically type-checked. Expressions using these features will have undecidable type decisions delegated to runtime.
    • The dyn Type: The dyn type is the union of all other types. You can use the dyn function to signal to the type checker that an argument should be treated as dyn, list(dyn), or a dyn-valued map. This is useful for heterogeneous collections, e.g., list(dyn) for [1, 3.14, "foo"].
    • Richer Type System: The type checker uses more granular types than runtime values (e.g., list(type) and map(key_type, value_type)).
    • Optimization: Type checking helps optimize execution speed by narrowing down function overloads and allowing for efficient unboxed runtime representations.

    Note: Type checking is an optional phase and does not change the result of the evaluation; it only rejects ill-typed expressions.

  10. Use String and Bytes Literals

    master

    Strings

    • Single/Double Quotes: Delimited by ' or ". The closing delimiter must match the opening one. Newlines are not allowed in these literals.
    • Triple Quotes: Delimited by ''' or """. These may contain newlines.
    • Raw Strings: Precede the delimiter with r or R (e.g., r"\"") to prevent the interpretation of escape sequences. Useful for regular expressions.

    Bytes

    • Byte Literals: Precede the string delimiter with b or B (e.g., b"abc"). The literal represents the UTF-8 representation of the string.

    Escape Sequences

    Use a backslash (\) followed by:

    • Punctuation: \, \?, \", \', \
    • Whitespace: \a (bell), \b (backspace), \f (form feed), \n (line feed), \r (carriage return), \t (tab), \v (vertical tab).
    • Unicode: \u followed by 4 hex digits (BMP) or \U followed by 8 hex digits (full plane).
    • Hex/Octal: \x or \X for hex, or three octal digits (000-377).
    // Examples of literal types
""
'""'
'''x''x'''
"\""
"\\"
r"\\"
b"abc"
b"\303\277"

  11. Configure the CEL evaluation environment

    master

    A CEL expression is evaluated within a scope defined by:

    1. Protocol Buffer Package: Controls name resolution.
    2. Binding Context: Binds identifiers to values, errors, and functions.

    Implementations can use a context proto (a single protocol buffer message) where each field represents a binding. The environment can also specify an expected type for the result; if the result is a protocol buffer wrapper message, CEL will attempt to convert the result to that type or raise an error.

  12. Handle Numeric Values and Mixed-Type Arithmetic

    master

    CEL supports 64-bit integers and 64-bit IEEE double-precision floating-point numbers.

    Literals

    • Integers: Only positive, decimal integer literals are supported. Use the unary negation operator for negative integers.
    • Unsigned Integers: Append u to a literal (e.g., 7u).
    • Doubles: Use a decimal point or exponent (e.g., 7.0, 7e0, .700e1).

    Mixed-Type Arithmetic

    There are no automatic arithmetic conversions between int, uint, and double. Arithmetic operators do not support mixed-type arguments (e.g., 1 + 1u will fail). You must use explicit conversion functions to perform mixed-type arithmetic.

    Example: To add an integer to an unsigned integer, convert the integer first:

    uint(1) + 1u