Repository: kubernetes
Issue: CEL feedback: expressions within arrays are too costly
Labels: kind/support,sig/api-machinery,kind/feature,triage/accepted

tl;dr: CEL cost is extremely restrictive, in particular with arrays, despite not being logically more expensive than native OpenAPI expressions

### What happened?

1. I migrated a very complex, N^2, native OpenAPI validation to a trivial O(1) CEL expression
2. CRD is now rejected with max cost exceeded



### What did you expect to happen?

I can migrate from a complex expression to a simple CEL expression

### How can we reproduce it (as minimally and precisely as possible)?

What I am trying to do is represent protobuf in CRDs. In particular, the `oneOf` aspect of protobuf. Note that "oneOf" in proto is not the same as OpenAPI: it allows none set, as well.

This is tricky to represent in OpenAPI, especially if you have multiple `oneOf` for a single message or in nested messages. In this case, the best implementation I had found ends up being N^2:

<details>

```yaml
oneOf:
- not:
    anyOf:
    - required:
      - simple
    - properties:
        consistentHash:
          allOf:
          - oneOf:
            - not:
                anyOf:
                - required:
                  - httpHeaderName
                - required:
                  - httpCookie
                - required:
                  - useSourceIp
                - required:
                  - httpQueryParameterName
            - required:
              - httpHeaderName
            - required:
              - httpCookie
            - required:
              - useSourceIp
            - required:
              - httpQueryParameterName
          - oneOf:
            - not:
                anyOf:
                - required:
                  - ringHash
                - required:
                  - maglev
            - required:
              - ringHash
            - required:
              - maglev
          properties:
            minimumRingSize: {}
      required:
      - consistentHash
- required:
  - simple
- properties:
    consistentHash:
      allOf:
      - oneOf:
        - not:
            anyOf:
            - required:
              - httpHeaderName
            - required:
              - httpCookie
            - required:
              - useSourceIp
            - required:
              - httpQueryParameterName
        - required:
          - httpHeaderName
        - required:
          - httpCookie
        - required:
          - useSourceIp
        - required:
          - httpQueryParameterName
      - oneOf:
        - not:
            anyOf:
            - required:
              - ringHash
            - required:
              - maglev
        - required:
          - ringHash
        - required:
          - maglev
      properties:
        minimumRingSize: {}
  required:
  - consistentHash
properties:
  consistentHash:
    properties:
      httpCookie:
        description: Hash based on HTTP cookie.
        properties:
          name:
            description: Name of the cookie.
            type: string
          path:
            description: Path to set for the cookie.
            type: string
          ttl:
            description: Lifetime of the cookie.
            type: string
        type: object
      httpHeaderName:
        description: Hash based on a specific HTTP header.
        type: string
      httpQueryParameterName:
        description: Hash based on a specific HTTP query
          parameter.
        type: string
      maglev:
        description: The Maglev load balancer implements
          consistent hashing to backend hosts.
        properties:
          tableSize:
            description: The table size for Maglev hashing.
            type: integer
        type: object
      minimumRingSize:
        description: Deprecated.
        type: integer
      ringHash:
        description: The ring/modulo hash load balancer
          implements consistent hashing to backend hosts.
        properties:
          minimumRingSize:
            description: The minimum number of virtual nodes
              to use for the hash ring.
            type: integer
        type: object
      useSourceIp:
        description: Hash based on the source IP address.
        type: boolean
    type: object
```

</details>

Due to the cognitive complexity and cost (its huge -- some small changes to our API can easily bloat this further as well), I wanted to replace this with CEL. This can be done with a trivial O(1) CEL expression. (switching to another simpler message, so its not huge):

```yaml
allowOrigins:
  description: String patterns that match allowed origins.
  items:
    properties:
      exact:
        type: string
      prefix:
        type: string
      regex:
        description: RE2 style regex-based match (https://github.com/google/re2/wiki/Syntax).
        type: string
    type: object
    x-kubernetes-validations:
    - message: At most one of [exact prefix regex] should
        be set
      reason: FieldValueDuplicate
      rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
  type: array
```

The problem here is the `array`. Maybe we should have had a `maxItems`, but we don't, and doing so is a backwards incompatible breaking change for our users.

I understand the cost is theoretically `unbounded list size * really small number` (I think "really small number" is `6`, if I did the cost calculation correctly). But the same applies to native OpenAPI! If I understand right, this limitation essentially means in any `array` APIs we cannot use CEL and are forced to stick with native OpenAPI validation. It works in simple cases, but we don't have simple cases. This will effectively block us from adopting any CEL beyond some trivial use cases; a LARGE portion of our APIs are complex objects nested under unbounded `arrays`. Note even the maxItems bound needs to be pretty extreme for our usages; I got errors until I dropped it under 100 for some of our cases.

Below shows a minimal reproducer. In the real world, obviously the same rule will not be repeated -- this is just a trivial example.

```yaml
# Generated with `kubectl kustomize "https://github.com/kubernetes-sigs/gateway-api/config/crd/experimental?ref=v0.8.0"`
apiVersion: apiextensions.k8s.io/v1
kind: CustomResourceDefinition
metadata:
  name: gatewayclasses.example.io
spec:
  group: example.io
  names:
    categories:
    - gateway-api
    kind: GatewayClass
    listKind: GatewayClassList
    plural: gatewayclasses
    singular: gatewayclass
  scope: Cluster
  versions:
  - name: v1alpha2
    schema:
      openAPIV3Schema:
        properties:
          allowOrigins:
            items:
              properties:
                exact:
                  type: string
                prefix:
                  type: string
                regex:
                  type: string
              type: object
              x-kubernetes-validations:
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
                - rule: (has(self.exact)?1:0)+(has(self.prefix)?1:0)+(has(self.regex)?1:0)<=1
            type: array
        type: object
    served: true
    storage: true
```

### Anything else we need to know?

I was told to file bugs like this and tag @TristonianJones @cici37  and @zielenski on CEL usability issues, so I am doing so

### Kubernetes version

<details>

```console
$ kubectl version
v1.28.0
```

</details>


### Cloud provider

<details>
kind
</details>


### OS version

<details>

```console
# On Linux:
$ cat /etc/os-release
# paste output here
$ uname -a
# paste output here

# On Windows:
C:\> wmic os get Caption, Version, BuildNumber, OSArchitecture
# paste output here
```

</details>


### Install tools

<details>

</details>


### Container runtime (CRI) and version (if applicable)

<details>

</details>


### Related plugins (CNI, CSI, ...) and versions (if applicable)

<details>

</details>