Fixes CEL estimated cost to propagate result sizes correctly

[jpbetz]

/kind bug

What this PR does / why we need it:

Fixes CEL estimated cost to propagate the result size of functions that returns strings/bytes/lists/maps. Without this fix, the estimated size is assumed to be max integer and the estimated cost limit is exceeded, preventing some valid CEL expressions from being used in CRDs for validation.

Which issue(s) this PR fixes:

Fixes #119749

Special notes for your reviewer:

See google/cel-go#787 for the fix to cel-go picked up by this PR. The rest of this PR is tests to ensure the fix applies as expected.

Does this PR introduce a user-facing change?

Fixed a bug where CEL expressions in CRD validation rules would incorrectly compute a high estimated cost for functions that return strings, lists or maps.
The incorrect cost was evident when the result of a function was used in subsequent operations.

[k8s-ci-robot]

Please note that we're already in Test Freeze for the release-1.28 branch. This means every merged PR will be automatically fast-forwarded via the periodic ci-fast-forward job to the release branch of the upcoming v1.28.0 release.

Fast forwards are scheduled to happen every 6 hours, whereas the most recent run was: Mon Aug 7 16:31:33 UTC 2023.

[jpbetz]

/priority important-soon

[liggitt]

any explanation for why this test changed or why the new value is better / more correct?

asked another way, if we'd kept the value 'does not matter', would the expectedCalcCost / expectedSetCost have changed?

[jpbetz]

Good question. This is the only test that exercised the behavior being fixed. But it failed to catch it.

The estimator calculates the cost of the equals check based on the min(length(LHS), length(RHS)) of the equal operation.

Before fixing the bug it was doing min(length(MAX_INT), length("does not matter")) and so the expected cost values were based on the length of "does not matter". When I fixed the bug it changed the expected values because length(<expected replace result size>) became less than "does not matter". This is what the test should have expected all along.

I actually don't need to keep this string change, I modified it when testing my assumptions locally, I'll revert it. The expected values will still change.

[jpbetz]

/hold
For until code thaw per slack discussion with @dims

EDIT: We'll backport to 1.28.1 via #119807

[jpbetz]

/retest

[alexzielenski]

/triage accepted

[sftim]

Changelog suggestion

Fixed a bug where CEL expressions in CRD validation rules would incorrectly compute a high estimated cost for functions that return strings, lists or maps.
The incorrect cost was evident when the result of a function was used in subsequent operations.

Does this definitely only apply to CRD validation and not elsewhere?

[jpbetz]

Changelog suggestion

Fixed a bug where CEL expressions in CRD validation rules would incorrectly compute a high estimated cost for functions that return strings, lists or maps.
The incorrect cost was evident when the result of a function was used in subsequent operations.

Does this definitely only apply to CRD validation and not elsewhere?

Yes, this applies only to CRD validation. It is the only feature that uses estimated cost.

[jpbetz]

/hold cancel
This is ready to merge.

[liggitt]

/lgtm
/approve

[k8s-ci-robot]

LGTM label has been added.

Git tree hash: 31c38f82edcf00bb81d314b41b7c74439caacc5d

[k8s-ci-robot]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: jpbetz, liggitt

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Needs approval from an approver in each of these files:

• OWNERS [liggitt]
• staging/src/k8s.io/apiextensions-apiserver/OWNERS [jpbetz,liggitt]
• staging/src/k8s.io/apiextensions-apiserver/pkg/apis/OWNERS [liggitt]
• staging/src/k8s.io/apiserver/OWNERS [jpbetz,liggitt]
• staging/src/k8s.io/cloud-provider/OWNERS [liggitt]
• staging/src/k8s.io/controller-manager/OWNERS [jpbetz,liggitt]
• staging/src/k8s.io/kube-aggregator/OWNERS [jpbetz,liggitt]
• staging/src/k8s.io/kube-controller-manager/OWNERS [liggitt]
• staging/src/k8s.io/kubelet/OWNERS [liggitt]
• staging/src/k8s.io/legacy-cloud-providers/OWNERS [liggitt]
• staging/src/k8s.io/pod-security-admission/OWNERS [liggitt]
• staging/src/k8s.io/sample-apiserver/OWNERS [jpbetz,liggitt]
• vendor/OWNERS [liggitt]

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

[jpbetz]

/retest

[Rajalakshmi-Girish]

Merge of this is giving below error in ppc architecture:

--- FAIL: TestCostEstimation (1.90s)
    --- FAIL: TestCostEstimation/extended_library_replace (0.03s)
        --- FAIL: TestCostEstimation/extended_library_replace/calc_maxLength (0.02s)
            compilation_test.go:1223: Wrong cost (expected 629152, got 629154)
        --- FAIL: TestCostEstimation/extended_library_replace/set_maxLength (0.01s)
            compilation_test.go:1223: Wrong cost (expected 14, got 16)

@jpbetz Please let us know if anything has to be changed specific to architecture.

[jpbetz]

Joe Betz Please let us know if anything has to be changed specific to architecture.

There is not. The cost of this expression changed from 16 to 14 in cel-go 1.16.1 (https://github.com/google/cel-go/commits/v0.16.1) by this exact amount. Can you point me to the test run, I'd like to validate that the dependency update was applied.

[Rajalakshmi-Girish]

Joe Betz Please let us know if anything has to be changed specific to architecture.

There is not. The cost of this expression changed from 16 to 14 in cel-go 1.16.1 (https://github.com/google/cel-go/commits/v0.16.1) by this exact amount. Can you point me to the test run, I'd like to validate that the dependency update was applied.

https://prow.ppc64le-cloud.cis.ibm.net/view/gs/ppc64le-kubernetes/logs/periodic-kubernetes-unit-test-ppc64le/1692340684859641856 is the link to CI job that has been failing with above test.

[jpbetz]

https://prow.ppc64le-cloud.cis.ibm.net/view/gs/ppc64le-kubernetes/logs/periodic-kubernetes-unit-test-ppc64le/1692340684859641856 is the link to CI job that has been failing with above test.

Yes, the test failures exactly matche what would happen if somehow the cel-go bump from 1.16.0 to 1.16.1 was somehow not applied.

I checked the cel-go code for anything architecture specific and found nothing. I think our best lead at the moment is that the failure exactly matches what should happen if the dependency bump is not picked up. I've opened a slack thread: https://kubernetes.slack.com/archives/C09QZ4DQB/p1692373534287669

[jpbetz]

#120097 fixes the ppc64le issue.