Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Fix nested CallExpr cost estimation #571

Merged
merged 10 commits into from Aug 17, 2022
Merged

Fix nested CallExpr cost estimation #571

merged 10 commits into from Aug 17, 2022

Conversation

DangerOnTheRanger
Copy link
Contributor

@DangerOnTheRanger DangerOnTheRanger commented Aug 10, 2022 •
edited

This PR fixes instances where cost estimation is used on expressions where a CallExpr is nested inside of another CallExpr and math.MaxUint64 is incorrectly returned. The test case included with this PR shows an example of where this can happen; == is treated as a function call/CallExpr, and will call sizeEstimate on its left and right-hand expressions. sizeEstimate will then try to call AstNode.ComputedSize before trying EstimateSize and finally returning math.MaxUint64 for an upper limit.

That constant will get returned for operator-based CallExprs inside CallExprs whenever the inner one lacks an EstimateSize, such as with list.size(). Instead, this PR checks for CallExpr inside SizeEstimate and returns a min/max cost of 1.

The original issue was first reported in kubernetes/kubernetes#111769.

@DangerOnTheRanger DangerOnTheRanger mentioned this pull request Aug 10, 2022
Closed
jpbetz
jpbetz requested changes Aug 10, 2022
View reviewed changes
checker/cost.go Outdated Show resolved Hide resolved
checker/cost_test.go Show resolved Hide resolved
@jpbetz
Copy link
Collaborator

jpbetz commented Aug 10, 2022

Please add a link in the description to k8s issue where this was discovered.

@jpbetz
Copy link
Collaborator

jpbetz commented Aug 10, 2022

/gcbrun

@jpbetz
Copy link
Collaborator

jpbetz commented Aug 10, 2022

@TristonianJones I'd like to backport the fix to Kubernetes 1.24 and 1.23 if possible.

Once this is ready, would it be possible to backport to cel-go v0.10 and v0.9? These are the CEL versions those Kubernetes releases depend on (https://github.com/kubernetes/kubernetes/blob/release-1.24/go.mod#L267, https://github.com/kubernetes/kubernetes/blob/release-1.23/go.mod#L272)

alexzielenski
alexzielenski reviewed Aug 10, 2022
View reviewed changes
checker/cost.go Outdated Show resolved Hide resolved
@TristonianJones
Copy link
Collaborator

/gcbrun

@TristonianJones
Copy link
Collaborator

@jpbetz I'll cherry pick the squashed commit back into the previous releases with minor version bumps, e.g. v0.11.5, v0.10.2, v0.9.1. Sound good?

@jpbetz
Copy link
Collaborator

jpbetz commented Aug 11, 2022

Joe Betz I'll cherry pick the squashed commit back into the previous releases with minor version bumps, e.g. v0.11.5, v0.10.2, v0.9.1. Sound good?

Thank you so much. I realize this is tedious.

@DangerOnTheRanger DangerOnTheRanger mentioned this pull request Aug 11, 2022
Closed
3 tasks
jpbetz
jpbetz reviewed Aug 11, 2022
View reviewed changes
checker/cost_test.go Outdated Show resolved Hide resolved
@TristonianJones
Copy link
Collaborator

/gcbrun

jpbetz
jpbetz reviewed Aug 11, 2022
View reviewed changes
checker/cost.go Outdated Show resolved Hide resolved
@jpbetz
Copy link
Collaborator

jpbetz commented Aug 11, 2022

/gcbrun

@TristonianJones
Copy link
Collaborator

/gcbrun

jpbetz
jpbetz reviewed Aug 15, 2022
View reviewed changes
checker/cost.go Outdated Show resolved Hide resolved
jpbetz
jpbetz reviewed Aug 15, 2022
View reviewed changes
checker/cost.go Outdated Show resolved Hide resolved
@TristonianJones
Copy link
Collaborator

/gcbrun

@jpbetz
Copy link
Collaborator

jpbetz commented Aug 15, 2022

LGTM

@TristonianJones
Copy link
Collaborator

/gcbrun

@TristonianJones TristonianJones merged commit 1aae83a into google:master Aug 17, 2022
TristonianJones pushed a commit to TristonianJones/cel-go that referenced this pull request Aug 18, 2022
@DangerOnTheRanger @TristonianJones
Fix nested CallExpr cost estimation (google#571)
299d4fe 
* Fix nested CallExpr cost estimation.
* Add TODO about merging isScalar/ComputedSize.

(cherry picked from commit 1aae83a)
liggitt pushed a commit to liggitt/cel-go that referenced this pull request Jan 3, 2023
@DangerOnTheRanger @TristonianJones
Fix nested CallExpr cost estimation (google#571)
e731d43 
* Fix nested CallExpr cost estimation.
* Add TODO about merging isScalar/ComputedSize.

(cherry picked from commit 1aae83a)
liggitt pushed a commit to liggitt/cel-go that referenced this pull request Jan 3, 2023
@DangerOnTheRanger @TristonianJones
Fix nested CallExpr cost estimation (google#571)
8de19f3 
* Fix nested CallExpr cost estimation.
* Add TODO about merging isScalar/ComputedSize.

(cherry picked from commit 1aae83a)
TristonianJones pushed a commit to TristonianJones/cel-go that referenced this pull request Jan 5, 2023
@DangerOnTheRanger @TristonianJones
Fix nested CallExpr cost estimation (google#571)
631934d 
* Fix nested CallExpr cost estimation.
* Add TODO about merging isScalar/ComputedSize.
TristonianJones added a commit that referenced this pull request Jan 5, 2023
@TristonianJones @DangerOnTheRanger
Fix nested CallExpr cost estimation (#571) (#624)
f663409 
* Fix nested CallExpr cost estimation.
* Add TODO about merging isScalar/ComputedSize.

Co-authored-by: Kermit Alexander II <kotuxguy@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@alexzielenski alexzielenski alexzielenski left review comments

@TristonianJones TristonianJones TristonianJones approved these changes

@jpbetz jpbetz jpbetz approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
4 participants
@DangerOnTheRanger @jpbetz @TristonianJones @alexzielenski