<commit_before># Language Definition

This page constitutes the reference for CEL. For a gentle introduction, see
[Intro](intro.md).

## Overview

In the taxonomy of programming languages, CEL is:

*   **memory-safe:** programs cannot express access to unrelated memory, such as
    out-of-bounds array indexes or use-after-free pointer dereferences;
*   **side-effect-free:** a CEL program only computes an output from its inputs;
*   **terminating:** CEL programs cannot loop forever;
*   **strongly-typed:** values have a well-defined type, and operators and
    functions check that their arguments have the expected types;
*   **dynamically-typed:** types are associated with values, not with variables
    or expressions, and type safety is enforced at runtime;
*   **gradually-typed:** an optional type-checking phase before runtime can
    detect and reject some programs which would violate type constraints.

## Syntax

The grammar of CEL is defined below, using `|` for alternatives, `[]` for
optional, `{}` for repeated, and `()` for grouping.

```grammar
Expr           = ConditionalOr ["?" ConditionalOr ":" Expr] ;
ConditionalOr  = [ConditionalOr "||"] ConditionalAnd ;
ConditionalAnd = [ConditionalAnd "&&"] Relation ;
Relation       = [Relation Relop] Addition ;
Relop          = "<" | "<=" | ">=" | ">" | "==" | "!=" | "in" ;
Addition       = [Addition ("+" | "-")] Multiplication ;
Multiplication = [Multiplication ("*" | "/" | "%")] Unary ;
Unary          = Member
               | "!" {"!"} Member
               | "-" {"-"} Member
               ;
Member         = Primary
               | Member "." IDENT ["(" [ExprList] ")"]
               | Member "[" Expr "]"
               | Member "{" [FieldInits] "}"
               ;
Primary        = ["."] IDENT ["(" [ExprList] ")"]
               | "(" Expr ")"
               | "[" [ExprList] "]"
               | "{" [MapInits] "}"
               | LITERAL
               ;
ExprList       = Expr {"," Expr} ;
FieldInits     = IDENT ":" Expr {"," IDENT ":" Expr} ;
MapInits       = Expr ":" Expr {"," Expr ":" Expr} ;
```

This grammar corresponds to the following operator precedence and associativity:

Precedence | Operator        | Description                    | Associativity
---------- | --------------- | ------------------------------ | -------------
1          | ()              | Function call                  | Left-to-right
&nbsp;     | .               | Qualified name or field access |
&nbsp;     | []              | Indexing                       |
&nbsp;     | {}              | Field initialization           |
2          | - (unary)       | Negation                       | Right-to-left
&nbsp;     | !               | Logical NOT                    |
3          | *               | Multiplication                 | Left-to-right
&nbsp;     | /               | Division                       |
&nbsp;     | %               | Remainder                      |
4          | +               | Addition                       |
&nbsp;     | - (binary)      | Subtraction                    |
5          | == != < > <= >= | Relations                      |
&nbsp;     | in              | Inclusion test                 |
6          | &&              | Logical AND                    |
7          | \|\|            | Logical OR                     |
8          | ?:              | Conditional                    | Right-to-left

The lexis is defined below. As is typical, the `WHITESPACE` and `COMMENT`
productions are only used to recognize separate lexical elements and are ignored
by the grammar.

```
IDENT          ::= [_a-zA-Z][_a-zA-Z0-9]* - RESERVED
LITERAL        ::= INT_LIT | UINT_LIT | FLOAT_LIT | STRING_LIT | BYTES_LIT
                 | BOOL_LIT | NULL_LIT
INT_LIT        ::= DIGIT+ | 0x HEXDIGIT+
UINT_LIT       ::= INT_LIT [uU]
FLOAT_LIT      ::= DIGIT* . DIGIT+ EXPONENT? | DIGIT+ EXPONENT
DIGIT          ::= [0-9]
HEXDIGIT       ::= [0-9abcdefABCDEF]
EXPONENT       ::= [eE] [+-]? DIGIT+
STRING_LIT     ::= [rR]? ( "    ~( " | NEWLINE )*  "
                         | '    ~( ' | NEWLINE )*  '
                         | """  ~"""*              """
                         | '''  ~'''*              '''
                         )
BYTES_LIT      ::= [bB] STRING_LIT
ESCAPE         ::= \ [bfnrt"'\]
                 | \ x HEXDIGIT HEXDIGIT
                 | \ u HEXDIGIT HEXDIGIT HEXDIGIT HEXDIGIT
                 | \ [0-3] [0-7] [0-7]
NEWLINE        ::= \r\n | \r | \n
BOOL_LIT       ::= "true" | "false"
NULL_LIT       ::= "null"
RESERVED       ::= BOOL_LIT | NULL_LIT | "in"
                 | "for" | "if" | "function" | "return" | "void"
                 | "import" | "package" | "as" | "let" | "const"
WHITESPACE     ::= [\t\n\f\r ]+
COMMENT        ::= '//' ~NEWLINE* NEWLINE
```

Note that negative numbers are recognized as positives with the unary `-`
operator from the grammar. For the sake of a readable representation, the escape
sequences (`ESCAPE`) are kept implicit in string tokens. The meaning is that in
strings without the `r` or `R` (raw) prefix, `ESCAPE` is processed, whereas in
strings with they stay uninterpreted. See documentation of string literals
below.

The following identifiers are reserved due to their use as literal values or in
the syntax:

    false in null true

The following identifiers are reserved to allow easier embedding of CEL into a
host language.

    as break const continue else for function if import let loop package
    namespace return var void while

In general it is a bad idea for those defining contexts or extensions to use
identifiers that are reserved words in programming languages which might embed
CEL.

### Name Resolution

A CEL expression is parsed in the scope of a specific protocol buffer package
or message, which controls the interpretation of names. The scope is set by
the application context of an expression. A CEL expression can contain simple
names as in `a` or qualified names as in `a.b`. The meaning of such expressions
is a combination of one or more of:

*   Variables and Functions: some simple names refer to variables in the
    execution context, standard functions, or other name bindings provided by
    the CEL application.
*   Field selection: appending a period and identifier to an expression could
    indicate that we're accessing a field within a protocol buffer or map.
*   Protocol buffer package names: a simple or qualified name could represent an
    absolute or relative name in the protocol buffer package namespace. Package
    names must be followed by a message type or enum constant.
*   Protocol buffer message types and enum constants: following an optional
    protocol buffer package name, a simple or qualified name could refer to a
    message type or enum constant in the package's namespace.

Resolution works as follows. If `a.b` is a name to be resolved in the context of
a protobuf declaration with scope `A.B`, then resolution is attempted, in order,
as `A.B.a.b`, `A.a.b`, and finally `a.b`. To override this behavior, one can use
`.a.b`; this name will only be attempted to be resolved in the root scope, i.e.
as `a.b`.

If name qualification is mixed with field selection, the longest prefix of the
name which resolves in the current lexical scope is used. For example, if
`a.b.c` resolves to a message declaration, and `a.b` does so as well with `c` a
possible field selection, then `a.b.c` takes priority over the interpretation
`(a.b).c`. Explicit parentheses can be used to choose the field selection
interpretation.

## Values

Values in CEL represent any of the following:

Type          | Description
------------- | ---------------------------------------------------------------
`int`         | 64-bit signed integers
`uint`        | 64-bit unsigned integers
`double`      | 64-bit IEEE floating-point numbers
`bool`        | Booleans (`true` or `false`)
`string`      | Strings of Unicode code points
`bytes`       | Byte sequences
`list`        | Lists of values
`map`         | Associative arrays with `int`, `uint`, `bool`, or `string` keys
`null_type`   | The value `null`
message names | Protocol buffer messages
`type`        | Values representing the types in the first column

### Numeric Values

CEL supports only 64-bit integers and 64-bit IEEE double-precision
floating-point. We only support positive, decimal integer literals; negative
integers are produced by the unary negation operator. Note that the integer 7 as
an `int` is a different value than 7 as a `uint`, which would be written `7u`.
Double-precision floating-point is also supported, and the integer 7 would be
written `7.`, `7.0`, `7e0`, or any equivalent representation using a decimal
point or exponent.

Note that currently there are no automatic arithmetic conversions for the
numeric types (`int`, `uint`, and `double`). The arithmetic operators typically
contain overloads for arguments of the same numeric type, but not for mixed-type
arguments. Therefore an expression like `1 + 1u` is going to fail to dispatch.
To perform mixed-type arithmetic, use explicit conversion functions such as
`uint(1) + 1u`. Such explicit conversions will maintain their meaning even if
arithmetic conversions are added in the future.

CEL provides no way to control the finer points of floating-point arithmetic,
such as expression evaluation, rounding mode, or exception handling. However,
any two not-a-number values will compare unequal even if their underlying
properties are different.

### String and Bytes Values

Strings are sequences of Unicode code points. Bytes are sequences of octets
(eight-bit data).

Quoted string literals are delimited by either single- or double-quote
characters, where the closing delimiter must match the opening one, and can
contain any unescaped character except the delimiter or newlines (either CR or
LF).

Triple-quoted string literals are delimited by three single-quotes or three
double-quotes, and may contain any unescaped characters except for the delimiter
sequence.  Again, the closing delimiter must match the opening one. Triple-quoted
strings may contain newlines.

Both sorts of strings can include escape sequences, described below.

If preceded by an `r` or `R` character, the string is a _raw_ string and does
not interpret escape sequences. Raw strings are useful for expressing strings
which themselves must use escape sequences, such as regular expressions or
program text.

Bytes literals are represented by string literals preceded by a `b` or `B`
character. The bytes literal is the sequence of bytes given by the UTF-8
representation of the string literal. In addition, the octal escape sequence are
interpreted as octet values rather than as Unicode code points. Both raw and
multiline string literals can be used for byte literals.

Escape sequences are a backslash (`\`) followed by one of the following:

*   A single-quote(`'`), double-quote(`"`), or backslash(`\`), representing
    itself.
*   A code for whitespace:
    *   `b`: backspace
    *   `f`: form feed
    *   `n`: line feed
    *   `r`: carriage return
    *   `t`: horizontal tab
*   A `u` followed by four hexadecimal characters, encoding a Unicode code point
    in the BMP. Characters in other Unicode planes can be represented with
    surrogate pairs.
*   A `x` followed by two hexadecimal characters. For strings, it denotes the
    unicode code point. For bytes, it represents an octet value.
*   Three octal digits, in the range `000` to `377`. For strings, it denotes the
    unicode code point. For bytes, it represents an octet value.

Examples:

CEL Literal  | Meaning
------------ | --------------------------------------------------------------
`""`         | Empty string
`'""'`       | String of two double-quote characters
`'''x''x'''` | String of four characters "x''x"
`"\""`       | String of one double-quote character
`"\\"`       | String of one backslash character
`r"\\"`      | String of two backslash characters
`b"abc"`     | Byte sequence of 61, 62, 63
`b"&yuml;"`  | Sequence of bytes 195 and 191 (UTF-8 of &yuml;)
`b"\303\277"`| Also sequence of bytes 195 and 191
`"\303\277"` | String of "&Atilde;&iquest;" (code points 195, 191)
`"\377"`     | String of "&yuml;" (code point 255)
`b"\377"`    | Sequence of byte 255 (_not_ UTF-8 of &yuml;)
`"\xFF"`     | String of "&yuml;" (code point 255)
`b"\xFF"`    | Sequence of byte 255 (_not_ UTF-8 of &yuml;)

### Aggregate Values

Lists are ordered sequences of values.

Maps are a set of key values, and a mapping from these keys to arbitrary values.
Key values must be an allowed key type: `int`, `uint`, `bool`, or `string`.
Thus maps are the union of what's allowed in protocol buffer maps and JSON
objects.

Note that the type checker uses a finer-grained notion of list and map types.
Lists are `list(A)` for the homogenous type `A` of list elements. Maps are
`map(K, V)` for maps with keys of type `K` and values of type `V`.  The type
`dyn` is used for heterogeneous values  See<commit_msg>Fix formatting glitch in byte literal example.<commit_after># Language Definition

This page constitutes the reference for CEL. For a gentle introduction, see
[Intro](intro.md).

## Overview

In the taxonomy of programming languages, CEL is:

*   **memory-safe:** programs cannot express access to unrelated memory, such as
    out-of-bounds array indexes or use-after-free pointer dereferences;
*   **side-effect-free:** a CEL program only computes an output from its inputs;
*   **terminating:** CEL programs cannot loop forever;
*   **strongly-typed:** values have a well-defined type, and operators and
    functions check that their arguments have the expected types;
*   **dynamically-typed:** types are associated with values, not with variables
    or expressions, and type safety is enforced at runtime;
*   **gradually-typed:** an optional type-checking phase before runtime can
    detect and reject some programs which would violate type constraints.

## Syntax

The grammar of CEL is defined below, using `|` for alternatives, `[]` for
optional, `{}` for repeated, and `()` for grouping.

```grammar
Expr           = ConditionalOr ["?" ConditionalOr ":" Expr] ;
ConditionalOr  = [ConditionalOr "||"] ConditionalAnd ;
ConditionalAnd = [ConditionalAnd "&&"] Relation ;
Relation       = [Relation Relop] Addition ;
Relop          = "<" | "<=" | ">=" | ">" | "==" | "!=" | "in" ;
Addition       = [Addition ("+" | "-")] Multiplication ;
Multiplication = [Multiplication ("*" | "/" | "%")] Unary ;
Unary          = Member
               | "!" {"!"} Member
               | "-" {"-"} Member
               ;
Member         = Primary
               | Member "." IDENT ["(" [ExprList] ")"]
               | Member "[" Expr "]"
               | Member "{" [FieldInits] "}"
               ;
Primary        = ["."] IDENT ["(" [ExprList] ")"]
               | "(" Expr ")"
               | "[" [ExprList] "]"
               | "{" [MapInits] "}"
               | LITERAL
               ;
ExprList       = Expr {"," Expr} ;
FieldInits     = IDENT ":" Expr {"," IDENT ":" Expr} ;
MapInits       = Expr ":" Expr {"," Expr ":" Expr} ;
```

This grammar corresponds to the following operator precedence and associativity:

Precedence | Operator        | Description                    | Associativity
---------- | --------------- | ------------------------------ | -------------
1          | ()              | Function call                  | Left-to-right
&nbsp;     | .               | Qualified name or field access |
&nbsp;     | []              | Indexing                       |
&nbsp;     | {}              | Field initialization           |
2          | - (unary)       | Negation                       | Right-to-left
&nbsp;     | !               | Logical NOT                    |
3          | *               | Multiplication                 | Left-to-right
&nbsp;     | /               | Division                       |
&nbsp;     | %               | Remainder                      |
4          | +               | Addition                       |
&nbsp;     | - (binary)      | Subtraction                    |
5          | == != < > <= >= | Relations                      |
&nbsp;     | in              | Inclusion test                 |
6          | &&              | Logical AND                    |
7          | \|\|            | Logical OR                     |
8          | ?:              | Conditional                    | Right-to-left

The lexis is defined below. As is typical, the `WHITESPACE` and `COMMENT`
productions are only used to recognize separate lexical elements and are ignored
by the grammar.

```
IDENT          ::= [_a-zA-Z][_a-zA-Z0-9]* - RESERVED
LITERAL        ::= INT_LIT | UINT_LIT | FLOAT_LIT | STRING_LIT | BYTES_LIT
                 | BOOL_LIT | NULL_LIT
INT_LIT        ::= DIGIT+ | 0x HEXDIGIT+
UINT_LIT       ::= INT_LIT [uU]
FLOAT_LIT      ::= DIGIT* . DIGIT+ EXPONENT? | DIGIT+ EXPONENT
DIGIT          ::= [0-9]
HEXDIGIT       ::= [0-9abcdefABCDEF]
EXPONENT       ::= [eE] [+-]? DIGIT+
STRING_LIT     ::= [rR]? ( "    ~( " | NEWLINE )*  "
                         | '    ~( ' | NEWLINE )*  '
                         | """  ~"""*              """
                         | '''  ~'''*              '''
                         )
BYTES_LIT      ::= [bB] STRING_LIT
ESCAPE         ::= \ [bfnrt"'\]
                 | \ x HEXDIGIT HEXDIGIT
                 | \ u HEXDIGIT HEXDIGIT HEXDIGIT HEXDIGIT
                 | \ [0-3] [0-7] [0-7]
NEWLINE        ::= \r\n | \r | \n
BOOL_LIT       ::= "true" | "false"
NULL_LIT       ::= "null"
RESERVED       ::= BOOL_LIT | NULL_LIT | "in"
                 | "for" | "if" | "function" | "return" | "void"
                 | "import" | "package" | "as" | "let" | "const"
WHITESPACE     ::= [\t\n\f\r ]+
COMMENT        ::= '//' ~NEWLINE* NEWLINE
```

Note that negative numbers are recognized as positives with the unary `-`
operator from the grammar. For the sake of a readable representation, the escape
sequences (`ESCAPE`) are kept implicit in string tokens. The meaning is that in
strings without the `r` or `R` (raw) prefix, `ESCAPE` is processed, whereas in
strings with they stay uninterpreted. See documentation of string literals
below.

The following identifiers are reserved due to their use as literal values or in
the syntax:

    false in null true

The following identifiers are reserved to allow easier embedding of CEL into a
host language.

    as break const continue else for function if import let loop package
    namespace return var void while

In general it is a bad idea for those defining contexts or extensions to use
identifiers that are reserved words in programming languages which might embed
CEL.

### Name Resolution

A CEL expression is parsed in the scope of a specific protocol buffer package
or message, which controls the interpretation of names. The scope is set by
the application context of an expression. A CEL expression can contain simple
names as in `a` or qualified names as in `a.b`. The meaning of such expressions
is a combination of one or more of:

*   Variables and Functions: some simple names refer to variables in the
    execution context, standard functions, or other name bindings provided by
    the CEL application.
*   Field selection: appending a period and identifier to an expression could
    indicate that we're accessing a field within a protocol buffer or map.
*   Protocol buffer package names: a simple or qualified name could represent an
    absolute or relative name in the protocol buffer package namespace. Package
    names must be followed by a message type or enum constant.
*   Protocol buffer message types and enum constants: following an optional
    protocol buffer package name, a simple or qualified name could refer to a
    message type or enum constant in the package's namespace.

Resolution works as follows. If `a.b` is a name to be resolved in the context of
a protobuf declaration with scope `A.B`, then resolution is attempted, in order,
as `A.B.a.b`, `A.a.b`, and finally `a.b`. To override this behavior, one can use
`.a.b`; this name will only be attempted to be resolved in the root scope, i.e.
as `a.b`.

If name qualification is mixed with field selection, the longest prefix of the
name which resolves in the current lexical scope is used. For example, if
`a.b.c` resolves to a message declaration, and `a.b` does so as well with `c` a
possible field selection, then `a.b.c` takes priority over the interpretation
`(a.b).c`. Explicit parentheses can be used to choose the field selection
interpretation.

## Values

Values in CEL represent any of the following:

Type          | Description
------------- | ---------------------------------------------------------------
`int`         | 64-bit signed integers
`uint`        | 64-bit unsigned integers
`double`      | 64-bit IEEE floating-point numbers
`bool`        | Booleans (`true` or `false`)
`string`      | Strings of Unicode code points
`bytes`       | Byte sequences
`list`        | Lists of values
`map`         | Associative arrays with `int`, `uint`, `bool`, or `string` keys
`null_type`   | The value `null`
message names | Protocol buffer messages
`type`        | Values representing the types in the first column

### Numeric Values

CEL supports only 64-bit integers and 64-bit IEEE double-precision
floating-point. We only support positive, decimal integer literals; negative
integers are produced by the unary negation operator. Note that the integer 7 as
an `int` is a different value than 7 as a `uint`, which would be written `7u`.
Double-precision floating-point is also supported, and the integer 7 would be
written `7.`, `7.0`, `7e0`, or any equivalent representation using a decimal
point or exponent.

Note that currently there are no automatic arithmetic conversions for the
numeric types (`int`, `uint`, and `double`). The arithmetic operators typically
contain overloads for arguments of the same numeric type, but not for mixed-type
arguments. Therefore an expression like `1 + 1u` is going to fail to dispatch.
To perform mixed-type arithmetic, use explicit conversion functions such as
`uint(1) + 1u`. Such explicit conversions will maintain their meaning even if
arithmetic conversions are added in the future.

CEL provides no way to control the finer points of floating-point arithmetic,
such as expression evaluation, rounding mode, or exception handling. However,
any two not-a-number values will compare unequal even if their underlying
properties are different.

### String and Bytes Values

Strings are sequences of Unicode code points. Bytes are sequences of octets
(eight-bit data).

Quoted string literals are delimited by either single- or double-quote
characters, where the closing delimiter must match the opening one, and can
contain any unescaped character except the delimiter or newlines (either CR or
LF).

Triple-quoted string literals are delimited by three single-quotes or three
double-quotes, and may contain any unescaped characters except for the delimiter
sequence.  Again, the closing delimiter must match the opening one. Triple-quoted
strings may contain newlines.

Both sorts of strings can include escape sequences, described below.

If preceded by an `r` or `R` character, the string is a _raw_ string and does
not interpret escape sequences. Raw strings are useful for expressing strings
which themselves must use escape sequences, such as regular expressions or
program text.

Bytes literals are represented by string literals preceded by a `b` or `B`
character. The bytes literal is the sequence of bytes given by the UTF-8
representation of the string literal. In addition, the octal escape sequence are
interpreted as octet values rather than as Unicode code points. Both raw and
multiline string literals can be used for byte literals.

Escape sequences are a backslash (`\`) followed by one of the following:

*   A single-quote(`'`), double-quote(`"`), or backslash(`\`), representing
    itself.
*   A code for whitespace:
    *   `b`: backspace
    *   `f`: form feed
    *   `n`: line feed
    *   `r`: carriage return
    *   `t`: horizontal tab
*   A `u` followed by four hexadecimal characters, encoding a Unicode code point
    in the BMP. Characters in other Unicode planes can be represented with
    surrogate pairs.
*   A `x` followed by two hexadecimal characters. For strings, it denotes the
    unicode code point. For bytes, it represents an octet value.
*   Three octal digits, in the range `000` to `377`. For strings, it denotes the
    unicode code point. For bytes, it represents an octet value.

Examples:

CEL Literal  | Meaning
------------ | --------------------------------------------------------------
`""`         | Empty string
`'""'`       | String of two double-quote characters
`'''x''x'''` | String of four characters "x''x"
`"\""`       | String of one double-quote character
`"\\"`       | String of one backslash character
`r"\\"`      | String of two backslash characters
`b"abc"`     | Byte sequence of 61, 62, 63
`b"ÿ"`       | Sequence of bytes 195 and 191 (UTF-8 of &yuml;)
`b"\303\277"`| Also sequence of bytes 195 and 191
`"\303\277"` | String of "&Atilde;&iquest;" (code points 195, 191)
`"\377"`     | String of "&yuml;" (code point 255)
`b"\377"`    | Sequence of byte 255 (_not_ UTF-8 of &yuml;)
`"\xFF"`     | String of "&yuml;" (code point 255)
`b"\xFF"`    | Sequence of byte 255 (_not_ UTF-8 of &yuml;)

### Aggregate Values

Lists are ordered sequences of values.

Maps are a set of key values, and a mapping from these keys to arbitrary values.
Key values must be an allowed key type: `int`, `uint`, `bool`, or `string`.
Thus maps are the union of what's allowed in protocol buffer maps and JSON
objects.

Note that the type checker uses a finer-grained notion of list and map types.
Lists are `list(A)` for the homogenous type `A` of list elements. Maps are
`map(K, V)` for maps with keys of type `K` and values of type `V`.  The type
`dyn` is used for heterogeneous values  See
{'fraction_non_alphanumeric': 0.1106162411211365, 'fraction_numerical': 0.008293338452678057, 'mean_word_length': 2.433882663150956, 'pattern_counts': {'":': 10, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '566817', 'n_tokens_mistral': 7399, 'n_tokens_neox': 6938, 'n_words': 3123}