Compiler type-checking failure with empty list variables

[seirl]

Description

We have encountered a subtle and relatively specific type-unification bug in the CEL compiler (specifically when compiling CEL policies).

When a list of strings is unwrapped from a list of optional strings (list(optional(string))) using standard comprehensions (filter/map), and then concatenated with an untyped empty list [] defined as a variable, the CEL type checker incorrectly propagates the list(optional(string)) constraint down the addition chain.

This causes the compiler to incorrectly infer the empty list variable as list(optional(string)) instead of list(string), resulting in a compilation failure:

found no matching overload for '_+_' applied to '(list(string), list(optional_type(string)))'

This bug is highly sensitive to variable boundaries and ONLY triggers when all steps are declared as separate variables in the policy. Inlining any of these steps acts as a workaround and allows the compiler to succeed.

To Reproduce
Check which components this affects:

• parser
• checker
• interpreter

---

Minimal Reproducible Example (MRE)

name: "mre"
rule:
  variables:
    # type: list(dyn) - Initially untyped empty list
    - name: "empty_list"
      expression: |
        []

    # type: list(optional(string)) - Source list of optional strings
    - name: "list_optional_string"
      expression: |
        [optional.of("foo")]

    # type: list(string) - Unwrapped string list using standard comprehensions
    - name: "string_list"
      expression: |
        variables.list_optional_string.filter(u, u.hasValue()).map(u, u.value())

    # Expected type: list(string)
    # ERROR TRIGGERS HERE:
    # "found no matching overload for '_+_' applied to '(list(string), list(optional_type(string)))'"
    - name: "concatenated_list"
      expression: |
        variables.string_list +
        variables.empty_list
  match:
    - output: |
        variables.concatenated_list

When compiling the above MRE, we get the following error message:

Compile(mre_policy.celpolicy) failed: 
ERROR: mre_policy.celpolicy:24:31: found no matching overload for '_+_' applied to (list(string), list(optional_type(string)))
 |         variables.string_list +
 | ..............................^

---

This bug seems strictly tied to how the compiler manages type constraints across variable boundaries. It only triggers when the compilation steps are split across separate variables:

1. Empty list must be a variable:
   The empty list [] must be defined as a variable (empty_list = []).
   • Inlining it directly into the addition chain (e.g., variables.string_list + []) compiles successfully.
2. Source optional list must be a variable:
   The source optional list list_optional_string must be defined as a variable.
   • Inlining it directly into the comprehension expression (e.g., [optional.of("foo")].filter(...)) compiles successfully.
3. Unwrapped list must be a variable:
   The mapped string list string_list must be defined as a variable.
   • Inlining it directly into the final addition (e.g., variables.list_optional_string.filter(...).map(...) + variables.empty_list) compiles successfully.

If you inline any of these three variables, the type checker correctly unifies the types. Only when they are declared as separate variables does the compiler incorrectly "leak" the type of the original optional list (list_optional_string) to the empty list variable in the addition step, thinking we are trying to add list(string) and list(optional(string)).

[seirl]

Here's an even simpler MRE:

name: "mre"
rule:
  variables:
    - name: "empty_list"
      expression: "[]"
    - name: "string_list"
      expression: "['foo']"
  match:
    - output: "variables.empty_list + [1]"

Compiling this gives:

found no matching overload for '_+_' applied to '(list(string), list(int))'

So it looks like whenever an untyped empty list [] is defined as a variable in the variables block, the CEL type checker incorrectly unifies its type with any other list type declared in the same variables block, even if they are completely unrelated and the other variable is completely unused.