Documentation
¶
Overview ¶
Package cost provides cost estimation, cost tracking, and saturating arithmetic.
Costs and sizes are unsigned 64-bit values where math.MaxUint64 doubles as the representation of an unbounded, or unknown, quantity. Every operation in this package saturates at math.MaxUint64 rather than wrapping so that an unbounded input remains unbounded through any sequence of operations.
Index ¶
- Constants
- Variables
- func ActualSize(value ref.Val) uint64
- func EstimateListAlloc(sz SizeEstimate, costFactor float64) (CostEstimate, *SizeEstimate)
- func EstimateStringScan(sz SizeEstimate) (CostEstimate, *SizeEstimate)
- func EstimateTraversal(nodeSize SizeEstimate, costFactor float64, allocationCost *CostEstimate) (CostEstimate, *SizeEstimate)
- func ModelVersionOf(estimator Estimator) uint32
- func NodeAsUintValue(node AstNode, defaultVal uint64) uint64
- func SafeAdd(x, y uint64, rest ...uint64) uint64
- func SafeCeil(x float64) uint64
- func SafeMultiply(x, y uint64) uint64
- func SafeMultiplyByFactor(x uint64, factor float64) uint64
- func SafeMultiplyByFactorTrunc(x uint64, factor float64) uint64
- func SafeSubtract(x, y uint64) uint64
- func SafeTrunc(x float64) uint64
- func StandardOverloadEstimators() map[string]FunctionEstimator
- func StandardOverloadEstimatorsWithOptions(opts ...ModelOption) map[string]FunctionEstimator
- func StandardOverloadTrackers() map[string]FunctionTracker
- func StandardOverloadTrackersWithOptions(opts ...ModelOption) map[string]FunctionTracker
- func UintValue(node AstNode) (uint64, bool)
- func ValidateOverloadModels(models ...OverloadModel) error
- type ActualCostEstimator
- type AstNode
- type Call
- type CallEstimate
- type ContainerSizing
- type CostEstimatedeprecated
- func (ce CostEstimate) Add(estimate CostEstimate) CostEstimate
- func (ce CostEstimate) IsUnknown() bool
- func (ce CostEstimate) Multiply(estimate CostEstimate) CostEstimate
- func (ce CostEstimate) MultiplyByCostFactor(costPerUnit float64) CostEstimate
- func (ce CostEstimate) Union(size CostEstimate) CostEstimate
- type CostOptiondeprecated
- type Estimate
- type EstimateContext
- type Estimator
- type FunctionEstimator
- type FunctionTracker
- type LimitExceededError
- type ModelOption
- type Option
- type OverloadModel
- func (m OverloadModel) FunctionEstimator() FunctionEstimator
- func (m OverloadModel) FunctionEstimatorWithOptions(opts ...ModelOption) FunctionEstimator
- func (m OverloadModel) FunctionTracker() FunctionTracker
- func (m OverloadModel) FunctionTrackerWithOptions(opts ...ModelOption) FunctionTracker
- func (m OverloadModel) Validate() error
- type OverloadModelOption
- func BeforeVersion(version uint32, opts ...OverloadModelOption) OverloadModelOption
- func EvalCost(cost QuantityExpr) OverloadModelOption
- func ManualCost(estimator FunctionEstimator, tracker FunctionTracker) OverloadModelOption
- func ManualEstimator(estimator FunctionEstimator) OverloadModelOption
- func ResultSize(size QuantityExpr) OverloadModelOption
- type QuantityExpr
- func AllocList(terms ...QuantityExpr) QuantityExpr
- func Arg(index int) QuantityExpr
- func ArgElem(index int) QuantityExpr
- func ArgKey(index int) QuantityExpr
- func AtLeastOneQuantity(expr QuantityExpr) QuantityExpr
- func AtMost(maxExpr QuantityExpr) QuantityExpr
- func Const(val uint64) QuantityExpr
- func ElemOf(expr QuantityExpr) QuantityExpr
- func ElemTotal(expr QuantityExpr) QuantityExpr
- func IntArg(index int, defaultVal uint64) QuantityExpr
- func IntTarget(defaultVal uint64) QuantityExpr
- func KeyOf(expr QuantityExpr) QuantityExpr
- func KeyTotal(expr QuantityExpr) QuantityExpr
- func Length(expr QuantityExpr) QuantityExpr
- func List(lenExpr, elemExpr QuantityExpr) QuantityExpr
- func ListAlloc(elemCount QuantityExpr, costFactor float64) QuantityExpr
- func Map(sizeExpr, keyExpr, valExpr QuantityExpr) QuantityExpr
- func Max(lhs, rhs QuantityExpr) QuantityExpr
- func Min(lhs, rhs QuantityExpr) QuantityExpr
- func Mul(terms ...QuantityExpr) QuantityExpr
- func Optional(valueExpr QuantityExpr) QuantityExpr
- func Ranged(minExpr, maxExpr QuantityExpr) QuantityExpr
- func Result() QuantityExpr
- func Scale(expr QuantityExpr, factor float64) QuantityExpr
- func Square(expr QuantityExpr) QuantityExpr
- func StringScan(expr QuantityExpr) QuantityExpr
- func Sub(lhs, rhs QuantityExpr) QuantityExpr
- func Sum(terms ...QuantityExpr) QuantityExpr
- func Target() QuantityExpr
- func TargetElem() QuantityExpr
- func TargetKey() QuantityExpr
- func Traversal(expr QuantityExpr, costFactor float64, allocCost uint64) QuantityExpr
- func Union(terms ...QuantityExpr) QuantityExpr
- type SizeEstimate
- func AtLeastOneSize(size SizeEstimate) SizeEstimate
- func EstimateSize(estimator Estimator, node AstNode) SizeEstimate
- func FixedSizeEstimate(size uint64) SizeEstimate
- func ListSizeEstimate(listSize SizeEstimate, elemSize SizeEstimate) SizeEstimate
- func MapSizeEstimate(mapSize SizeEstimate, keySize SizeEstimate, valSize SizeEstimate) SizeEstimate
- func RangedSizeEstimate(min, max uint64) SizeEstimate
- func UnknownSizeEstimate() SizeEstimate
- func (se SizeEstimate) Add(sizeEstimate SizeEstimate) SizeEstimate
- func (se SizeEstimate) AsCost() CostEstimate
- func (se SizeEstimate) IsUnknown() bool
- func (se SizeEstimate) Multiply(sizeEstimate SizeEstimate) SizeEstimate
- func (se SizeEstimate) MultiplyByCost(estimate CostEstimate) CostEstimate
- func (se SizeEstimate) MultiplyByCostFactor(costPerUnit float64) CostEstimate
- func (se SizeEstimate) Subtract(sizeEstimate SizeEstimate) SizeEstimate
- func (se SizeEstimate) Union(size SizeEstimate) SizeEstimate
- type SizingStrategy
- type TrackContext
- type Tracker
- func (c *Tracker) ActualCost() uint64
- func (c *Tracker) Clone() (*Tracker, error)
- func (c *Tracker) CostCall(call Call, args []ref.Val, result ref.Val) uint64
- func (c *Tracker) CreateList(id int64, res ref.Val)
- func (c *Tracker) CreateMap(id int64, res ref.Val)
- func (c *Tracker) CreateStruct(id int64, res ref.Val)
- func (c *Tracker) EvalAttribute(id int64, isTestOnly bool, res ref.Val)
- func (c *Tracker) EvalBinary(vars any, id int64, call Call, lhs, rhs ref.Val, result ref.Val)
- func (c *Tracker) EvalUnary(vars any, id int64, call Call, arg ref.Val, result ref.Val)
- func (c *Tracker) EvalVarArgs(vars any, id int64, call Call, args []ref.Val, result ref.Val)
- func (c *Tracker) EvalZeroArity(vars any, id int64, call Call, result ref.Val)
- func (c *Tracker) ModelVersion() uint32
- func (c *Tracker) PresenceTestHasCost() bool
- func (c *Tracker) Qualify(id int64)
- type TrackerOption
- type TypeContext
Constants ¶
const ( // SelectAndIdentCost is the cost of an operation that accesses an identifier or performs a select. SelectAndIdentCost = 1 // ConstCost is the cost of an operation that accesses a constant. ConstCost = 0 // ListCreateBaseCost is the base cost of any operation that creates a new list. ListCreateBaseCost = 10 // MapCreateBaseCost is the base cost of any operation that creates a new map. MapCreateBaseCost = 30 // StructCreateBaseCost is the base cost of any operation that creates a new struct. StructCreateBaseCost = 40 // StringTraversalCostFactor is multiplied to a length of a string when computing the cost of traversing the entire // string once. StringTraversalCostFactor = 0.1 // RegexStringLengthCostFactor is multiplied to the length of a regex string pattern when computing the cost of // applying the regex to a string of unit cost. RegexStringLengthCostFactor = 0.25 )
Variables ¶
var ( // CallCostEstimate is the base cost estimate for an O(1) function call. CallCostEstimate = FixedCostEstimate(1) // CallCost is the base cost for an O(1) function call. CallCost = uint64(1) // ListAllocCost is the base cost estimate for allocating a list. ListAllocCost = FixedCostEstimate(ListCreateBaseCost) // StringCostFactor is the cost factor for traversing a string once. StringCostFactor = StringTraversalCostFactor )
var StandardOverloadModels = []OverloadModel{ Overload(overloads.IndexList, EvalCost(Const(1)), ResultSize(ArgElem(0)), ), Overload(overloads.IndexMap, EvalCost(Const(1)), ResultSize(ArgElem(0)), ), MemberOverload(overloads.StartsWithString, EvalCost(Scale(Arg(0), StringTraversalCostFactor)), ), MemberOverload(overloads.EndsWithString, EvalCost(Scale(Arg(0), StringTraversalCostFactor)), ), Overload(overloads.StringToBytes, EvalCost(Scale(Arg(0), StringTraversalCostFactor)), ResultSize(Ranged(Arg(0), Scale(Arg(0), 4.0))), ), Overload(overloads.BytesToString, EvalCost(Scale(Arg(0), StringTraversalCostFactor)), ResultSize(Ranged(Scale(Arg(0), 0.25), Arg(0))), ), Overload(overloads.ExtQuoteString, EvalCost(Scale(Arg(0), StringTraversalCostFactor)), ResultSize(Ranged(Sum(Arg(0), Const(2)), Sum(Scale(Arg(0), 2.0), Const(2)))), ), MemberOverload(overloads.ExtFormatString, EvalCost(Scale(Target(), StringTraversalCostFactor)), ), Overload(overloads.InList, EvalCost(Arg(1))), MemberOverload(overloads.OptionalOrOptional, EvalCost(Const(0)), argumentsOnly(), ResultSize(Union(Target(), Arg(0))), BeforeVersion(1, ManualEstimator(estimateUnmodeledCall)), ), MemberOverload(overloads.OptionalOrValueValue, EvalCost(Const(0)), argumentsOnly(), ResultSize(Union(ElemOf(Target()), Arg(0))), BeforeVersion(1, ManualEstimator(estimateUnmodeledCall)), ), Overload(overloads.OptionalNone, EvalCost(Const(1)), ResultSize(Optional(Const(0))), BeforeVersion(1, ResultSize(nil)), ), Overload(overloads.OptionalOf, EvalCost(Const(1)), ResultSize(Optional(Arg(0))), BeforeVersion(1, ResultSize(nil)), ), Overload(overloads.OptionalOfNonZeroValue, EvalCost(Const(1)), ResultSize(Optional(AtMost(Arg(0)))), BeforeVersion(1, ResultSize(nil)), ), MemberOverload(overloads.OptionalValue, EvalCost(Const(1)), ResultSize(ElemOf(Target())), BeforeVersion(1, ResultSize(nil)), ), Overload(overloads.LessString, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.GreaterString, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.LessEqualsString, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.GreaterEqualsString, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.LessBytes, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.GreaterBytes, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.LessEqualsBytes, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.GreaterEqualsBytes, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.Equals, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.NotEquals, EvalCost(Scale(Min(Arg(0), Arg(1)), StringTraversalCostFactor)), BeforeVersion(1, ManualEstimator(estimateComparisonV0)), ), Overload(overloads.AddString, EvalCost(Scale(Sum(Arg(0), Arg(1)), StringTraversalCostFactor)), ResultSize(Sum(Arg(0), Arg(1))), ), Overload(overloads.AddBytes, EvalCost(Scale(Sum(Arg(0), Arg(1)), StringTraversalCostFactor)), ResultSize(Sum(Arg(0), Arg(1))), ), Overload(overloads.AddList, EvalCost(Const(1)), ResultSize(Sum(Arg(0), Arg(1))), ), Overload(overloads.Matches, EvalCost(Mul( Scale(Sum(Arg(0), Const(1)), StringTraversalCostFactor), Scale(Arg(1), RegexStringLengthCostFactor), )), BeforeVersion(1, EvalCost(Mul( roundScale(Sum(Arg(0), Const(1)), StringTraversalCostFactor), roundScale(Arg(1), RegexStringLengthCostFactor), ))), ), MemberOverload(overloads.MatchesString, EvalCost(Mul( Scale(Sum(Target(), Const(1)), StringTraversalCostFactor), Scale(Arg(0), RegexStringLengthCostFactor), )), BeforeVersion(1, EvalCost(Mul( roundScale(Sum(Target(), Const(1)), StringTraversalCostFactor), roundScale(Arg(0), RegexStringLengthCostFactor), ))), ), MemberOverload(overloads.ContainsString, EvalCost(Mul( Scale(Target(), StringTraversalCostFactor), Scale(Arg(0), StringTraversalCostFactor), )), BeforeVersion(1, EvalCost(Mul( roundScale(Target(), StringTraversalCostFactor), roundScale(Arg(0), StringTraversalCostFactor), ))), ), Overload(overloads.LogicalOr, EvalCost(Const(0)), argumentsOnly()), Overload(overloads.LogicalAnd, EvalCost(Const(0)), argumentsOnly()), Overload(overloads.Conditional, EvalCost(Const(0)), argumentsOnly(), ResultSize(Union(Arg(1), Arg(2))), ), }
StandardOverloadModels defines the cost models for standard CEL functions.
Functions ¶
func ActualSize ¶ added in v0.33.0
ActualSize returns the size of the value for all traits.Sizer values, and returns a size of 1 for all other value types.
func EstimateListAlloc ¶ added in v0.33.0
func EstimateListAlloc(sz SizeEstimate, costFactor float64) (CostEstimate, *SizeEstimate)
EstimateListAlloc estimates cost for allocating a list.
func EstimateStringScan ¶ added in v0.33.0
func EstimateStringScan(sz SizeEstimate) (CostEstimate, *SizeEstimate)
EstimateStringScan estimates cost for scanning a string.
func EstimateTraversal ¶ added in v0.33.0
func EstimateTraversal(nodeSize SizeEstimate, costFactor float64, allocationCost *CostEstimate) (CostEstimate, *SizeEstimate)
EstimateTraversal computes cost as a function of the size of the target object and whether the call allocates memory.
func ModelVersionOf ¶ added in v0.33.0
ModelVersionOf reports the cost model version the given Estimator is configured with, or math.MaxUint32 if the estimator does not carry version metadata.
func NodeAsUintValue ¶ added in v0.33.0
NodeAsUintValue returns the value of a literal int node as a uint64, or the default value if the node is not a non-negative int literal.
func SafeCeil ¶
SafeCeil returns the smallest integer value greater than or equal to the input, saturating at math.MaxUint64 and flooring at zero.
Negative and NaN inputs return zero.
func SafeMultiply ¶
SafeMultiply returns the product of the input values, saturating at math.MaxUint64.
func SafeMultiplyByFactor ¶
SafeMultiplyByFactor multiplies a value by a cost factor and returns the nearest integer value, rounded up, saturating at math.MaxUint64.
func SafeMultiplyByFactorTrunc ¶ added in v0.33.0
SafeMultiplyByFactorTrunc multiplies a value by a cost factor and returns the integer part of the result, truncated, saturating at math.MaxUint64.
This is the truncating counterpart to SafeMultiplyByFactor, which rounds up.
func SafeSubtract ¶ added in v0.33.0
SafeSubtract returns the difference of x - y, saturating at zero. If x is saturated (math.MaxUint64), it remains saturated.
func SafeTrunc ¶ added in v0.33.0
SafeTrunc returns the integer part of the input, saturating at math.MaxUint64 and flooring at zero.
Negative inputs return zero, and NaN saturates to max uint64 ¶
Cost trackers which report a truncated cost should prefer this helper over a direct conversion, as conversion of an out-of-range float64 to a uint64 is platform-defined.
func StandardOverloadEstimators ¶ added in v0.33.0
func StandardOverloadEstimators() map[string]FunctionEstimator
StandardOverloadEstimators returns the map of FunctionEstimator instances for standard overloads.
func StandardOverloadEstimatorsWithOptions ¶ added in v0.33.0
func StandardOverloadEstimatorsWithOptions(opts ...ModelOption) map[string]FunctionEstimator
StandardOverloadEstimatorsWithOptions returns the map of FunctionEstimator instances for standard overloads, configured by the supplied options.
func StandardOverloadTrackers ¶ added in v0.33.0
func StandardOverloadTrackers() map[string]FunctionTracker
StandardOverloadTrackers returns the map of FunctionTracker instances for standard overloads.
func StandardOverloadTrackersWithOptions ¶ added in v0.33.0
func StandardOverloadTrackersWithOptions(opts ...ModelOption) map[string]FunctionTracker
StandardOverloadTrackersWithOptions returns the map of FunctionTracker instances for standard overloads, configured by the supplied options.
The models are tracked under the configured revision, so that each charge is computed by the same rules as its estimate.
func UintValue ¶ added in v0.33.0
UintValue returns the value of a non-negative literal int or uint node as a uint64, or false if the node is not a non-negative integer literal.
func ValidateOverloadModels ¶ added in v0.33.0
func ValidateOverloadModels(models ...OverloadModel) error
ValidateOverloadModels reports the first model which is not well-formed.
Types ¶
type ActualCostEstimator ¶ added in v0.33.0
type ActualCostEstimator interface {
CallCost(function, overloadID string, args []ref.Val, result ref.Val) *uint64
}
ActualCostEstimator provides function call cost estimations at runtime.
CallCost returns an estimated cost for the function overload invocation with the given args, or nil if it has no estimate to provide. CEL attempts to provide reasonable estimates for its standard function library, so CallCost should typically not need to provide an estimate for CELs standard function.
type AstNode ¶ added in v0.33.0
type AstNode interface {
// Path returns a field path through the provided type declarations to the type of the AstNode, or nil if the AstNode does not
// represent type directly reachable from the provided type declarations.
// The first path element is a variable. All subsequent path elements are one of: field name, '@items', '@keys', '@values'.
Path() []string
// Type returns the deduced type of the AstNode.
Type() *types.Type
// Expr returns the expression of the AstNode.
Expr() ast.Expr
// ComputedSize returns a size estimate of the AstNode derived from information available in the CEL expression.
// For constants and inline list and map declarations, the exact size is returned. For concatenated list, strings
// and bytes, the size is derived from the size estimates of the operands. nil is returned if there is no
// computed size available.
ComputedSize() *SizeEstimate
}
AstNode represents an AST node for estimating cost.
func NewAstNode ¶ added in v0.33.0
NewAstNode returns an AstNode with the given expression, path, type, and derived size.
type Call ¶ added in v0.33.0
type Call interface {
// Function returns the name of the function being called.
Function() string
// OverloadID returns the specific overload ID being invoked.
OverloadID() string
}
Call represents an invocable function with a name and overload ID.
type CallEstimate ¶ added in v0.33.0
type CallEstimate struct {
CostEstimate
ResultSize *SizeEstimate
}
CallEstimate includes a CostEstimate for the call, and an optional estimate of the result object size. The ResultSize should only be provided if the call results in a map, list, string or bytes.
func NewCallEstimate ¶ added in v0.33.0
func NewCallEstimate(cost CostEstimate, sz *SizeEstimate) *CallEstimate
NewCallEstimate creates a new CallEstimate with the given cost and optional result size.
func NewListCallEstimate ¶ added in v0.33.0
func NewListCallEstimate(work CostEstimate, resultSize SizeEstimate) *CallEstimate
NewListCallEstimate creates a CallEstimate for a call that allocates a list, adding CallCost and ListCreateBaseCost to work and setting ResultSize to resultSize.
type ContainerSizing ¶ added in v0.33.0
type ContainerSizing int
ContainerSizing describes what the size of a container measures under a sizing strategy.
const ( // SizedByLength means a container's size is its length, as under the default sizing strategy. SizedByLength ContainerSizing = iota // SizedByContent means a container's size is 1 plus the sizes of its entries, as under the // aggregate sizing strategy. SizedByContent // SizedOpaque means the relationship between a container's size and its contents is not known, // as under a custom sizing strategy. SizedOpaque )
func ContainerSizingOf ¶ added in v0.33.0
func ContainerSizingOf(estimator Estimator) ContainerSizing
ContainerSizingOf reports what a container's size measures for the given Estimator.
A hand-written FunctionEstimator which builds a result's size from lengths, rather than from the sizes of its operands, uses it to report the size in the units of the sizing strategy. For an Estimator which carries no strategy, sizes are lengths. Prefer describing an overload by an OverloadModel, whose List and Map follow the strategy themselves.
type CostEstimate
deprecated
added in
v0.33.0
type CostEstimate = Estimate
CostEstimate is an alias for Estimate.
Deprecated: use Estimate.
func FixedCostEstimate ¶ added in v0.33.0
func FixedCostEstimate(fixedCost uint64) CostEstimate
FixedCostEstimate returns a cost with a fixed min and max range.
func RangedCostEstimate ¶ added in v0.33.0
func RangedCostEstimate(min, max uint64) CostEstimate
RangedCostEstimate returns a cost estimate bounded by min and max.
func UnknownCostEstimate ¶ added in v0.33.0
func UnknownCostEstimate() CostEstimate
UnknownCostEstimate returns a cost with an unknown impact.
func (CostEstimate) Add ¶ added in v0.33.0
func (ce CostEstimate) Add(estimate CostEstimate) CostEstimate
Add adds the costs and returns the sum. If add would result in an uint64 overflow for the min or max, the value is set to math.MaxUint64.
func (CostEstimate) IsUnknown ¶ added in v0.33.0
func (ce CostEstimate) IsUnknown() bool
IsUnknown returns true if the cost estimate represents an unknown cost (0 to math.MaxUint64).
func (CostEstimate) Multiply ¶ added in v0.33.0
func (ce CostEstimate) Multiply(estimate CostEstimate) CostEstimate
Multiply multiplies by the cost and returns the product. If multiply would result in an uint64 overflow, the result is math.MaxUint64.
func (CostEstimate) MultiplyByCostFactor ¶ added in v0.33.0
func (ce CostEstimate) MultiplyByCostFactor(costPerUnit float64) CostEstimate
MultiplyByCostFactor multiplies a CostEstimate by a cost factor and returns the CostEstimate with the nearest integer of the result, rounded up.
func (CostEstimate) Union ¶ added in v0.33.0
func (ce CostEstimate) Union(size CostEstimate) CostEstimate
Union returns a CostEstimate that encompasses both input CostEstimates.
type CostOption
deprecated
added in
v0.33.0
type Estimate ¶ added in v0.33.0
type Estimate struct {
Min, Max uint64
}
Estimate represents an estimated cost range and provides add and multiply operations that do not overflow.
type EstimateContext ¶ added in v0.33.0
type EstimateContext interface {
TypeContext
// Arg returns the size estimate for the argument at the given 0-based index.
Arg(index int) (SizeEstimate, bool)
// Target returns the size estimate for the receiver/target object, if present.
Target() (SizeEstimate, bool)
// Result returns the size estimate of the evaluated result, if known.
Result() (SizeEstimate, bool)
// Estimator returns the user-provided Estimator, if configured.
Estimator() Estimator
// Size returns the estimated size based on the SizingStrategy configured on the Estimator.
Size(node AstNode) SizeEstimate
// ArgValue returns the literal/constant uint64 value of the argument at index, or defaultVal.
ArgValue(index int, defaultVal uint64) uint64
// TargetValue returns the literal/constant uint64 value of the receiver/target, or defaultVal.
TargetValue(defaultVal uint64) uint64
}
EstimateContext provides size and argument evaluation during cost estimation.
type Estimator ¶ added in v0.33.0
type Estimator interface {
// EstimateCallCost returns the CallEstimate for a function, overload and target and arguments.
//
// If nil is returned, the cost of the function is calculated by the OverloadCostEstimate if
// provided, or standard CEL function cost estimation.
EstimateCallCost(function, overloadID string, target *AstNode, args []AstNode) *CallEstimate
// EstimateSize returns the SizeEstimate of an AstNode.
//
// If nil is returned, the size of the node is calculated by the SizingStrategy.
EstimateSize(element AstNode) *SizeEstimate
}
Estimator provides CallCost and Size estimates for cost calculation.
type FunctionEstimator ¶ added in v0.33.0
type FunctionEstimator func(estimator Estimator, target *AstNode, args []AstNode) *CallEstimate
FunctionEstimator provides a CallEstimate given the target and arguments for a specific function, overload pair.
type FunctionTracker ¶ added in v0.33.0
FunctionTracker computes the actual cost of evaluating the functions with the given arguments and result.
type LimitExceededError ¶ added in v0.33.0
type LimitExceededError struct {
Message string
}
LimitExceededError indicates that the actual cost limit was exceeded during evaluation.
func (LimitExceededError) Error ¶ added in v0.33.0
func (e LimitExceededError) Error() string
Error returns the error message for LimitExceededError.
type ModelOption ¶ added in v0.33.0
type ModelOption func(*modelOptions)
ModelOption configures how OverloadModels, cost estimators, and cost trackers are built and evaluated.
A ModelOption implements both Option (for Cost) and TrackerOption (for NewTracker), and may also be passed when compiling models directly via FunctionEstimatorWithOptions, FunctionTrackerWithOptions, StandardOverloadEstimatorsWithOptions, and StandardOverloadTrackersWithOptions.
func Model ¶ added in v0.33.0
func Model(models ...OverloadModel) ModelOption
Model registers one or more OverloadModels for both cost estimation and runtime cost tracking.
Models are validated when the option is applied to Cost or NewTracker and resolved after all options have run, so they observe the WithSizingStrategy and ModelVersion configured on the call regardless of option order.
func ModelVersion ¶ added in v0.33.0
func ModelVersion(version uint32) ModelOption
ModelVersion pins the revision of the cost model's estimation and runtime tracking rules.
If this option is not set, the latest cost model version is used. Revisions exist so that corrections to the model can land without silently moving numbers that existing deployments budget against. A caller holding estimates recorded under an earlier release can pin to the revision those estimates were produced under, review the delta at leisure, and adopt the correction deliberately.
Revisions apply to both estimation and runtime tracking, so that an estimate and the charge it predicts are always computed by the same rules. Pinning a version therefore holds both stable.
Caveat: Pinning to version 0 preserves legacy behavior from v0.32.0 and earlier, which contains known soundness gaps where static estimates can underestimate actual runtime cost (for example, when a caller's Estimator overrides computed loop variable sizes via bare "@items" paths, when selecting or indexing into computed containers, or when evaluating non-literal integer bounds). Callers are strongly encouraged to switch to ModelVersion(1) or higher (or leave the version unset to use the latest revision) for improved soundness between estimated bounds and tracked runtime cost.
Version 1:
- Min() is computed as the exact minimum of its operands' intervals, where v0.32.0 reported a lower bound of 1 for any interval whose upper bound is non-zero. The change moves only the lower bound of an estimate, never a charge, so it applies at every revision, including when pinned to version 0.
- A value inside an optional keeps its size. optional.of, optional.ofNonZeroValue and value() report the size they wrap or unwrap, the two `or` forms report the union of the receiver and the alternative, and the optional index forms record the same `@items` and `@values` field path their non-optional counterparts do.
- Optional field and index qualifiers (`m.?k`, `l[?0]`) charge 1 at runtime even when the field or index is absent, matching static estimation and non-optional qualification.
- Selecting or indexing into a computed expression (such as `[1, 2][0]` or `{"a": 1}.a`) charges the attribute traversal cost of 1 during estimation to match runtime tracking.
- Comprehension loop variables over computed (pathless) ranges retain their propagated element or key sizes rather than recording bare `@items`, `@indices`, `@keys`, or `@values` paths that a caller's Estimator could override with a smaller bound.
- The default sizing strategy skips `@items`, `@keys`, and `@values` child size hints when a container's maximum size is 0.
- Extension estimators in ext/lists (distinct, sort, sortBy, slice, range, flatten), ext/strings (join, split, substring, replace), and ext/regex (extract, extractAll, replace) align their Min/Max cost and result-size bounds with their runtime cost trackers.
- Scale applies its factor as the simplest rational with the same float64 value (0.1 is 1/10) and computes the product exactly; it keeps an unbounded quantity unbounded; and when a model is compiled, factors are moved outward so that each product is rounded once. The standard contains and matches costs become ⌈0.01·m·n⌉ and ⌈0.025·(m+1)·n⌉.
- Ranged never reports a lower bound above its upper bound.
- Combinators keep an unknown element or key size unknown, treating constants and integer values as scalars; Sub carries only its minuend's metadata.
- The result size is estimated first and is available to the cost through Result().
- A non-literal IntArg or IntTarget estimates as unbounded rather than as its default.
- List and Map report the size the sizing strategy assigns to the container they describe. Under the aggregate strategy, a comprehension iterates once per element of its range rather than once per unit of content size, and sizes its result as an aggregate container.
- Runtime tracking honors the revision, as estimation does.
- Every ext overload with a cost estimator is priced by a model, which charges by Length what its tracker charged and states result sizes in the units of the sizing strategy; flatten(depth) follows the strategy in its estimator. An Arg or Target typed as a value without elements, such as a string, carries no unknown element size.
- The value bound by cel.bind counts toward the minimum cost only when the result must read it, since the binding is lazy.
- A list or map literal's minimum size counts only its required elements or entries, and an optional element written as optional.none() or optional.of(x) contributes nothing or the size of x.
func WithSizingStrategy ¶ added in v0.33.0
func WithSizingStrategy(strategy SizingStrategy) ModelOption
WithSizingStrategy sets the SizingStrategy used to resolve sizes during both cost estimation and runtime cost tracking.
A nil strategy is ignored, leaving the default in place.
type Option ¶ added in v0.33.0
type Option interface {
// contains filtered or unexported methods
}
Option configures flags which affect cost computations.
func OverloadCostEstimate ¶ added in v0.33.0
func OverloadCostEstimate(overloadID string, functionCoster FunctionEstimator) Option
OverloadCostEstimate binds a FunctionEstimator to a specific function overload ID.
When an OverloadCostEstimate is provided, it overrides the cost calculation of the Estimator provided to the Cost() call.
func PresenceTestHasCost ¶ added in v0.33.0
PresenceTestHasCost determines whether presence testing has a cost of one or zero.
Defaults to presence test has a cost of one.
type OverloadModel ¶ added in v0.33.0
type OverloadModel struct {
ID string
Cost QuantityExpr
Size QuantityExpr
IsMember bool
// contains filtered or unexported fields
}
OverloadModel pairs an overload ID with its abstract cost and result size expressions.
An OverloadModel is a value built by Overload or MemberOverload, and is not modified afterwards: estimators and trackers are compiled from it on request. Validate reports a model which cannot be priced, and cel.CostModel and Model call it when the model is registered.
func MemberOverload ¶ added in v0.33.0
func MemberOverload(id string, opts ...OverloadModelOption) OverloadModel
MemberOverload creates a member function OverloadModel with functional options.
func Overload ¶ added in v0.33.0
func Overload(id string, opts ...OverloadModelOption) OverloadModel
Overload creates a global function OverloadModel with functional options.
func (OverloadModel) FunctionEstimator ¶ added in v0.33.0
func (m OverloadModel) FunctionEstimator() FunctionEstimator
FunctionEstimator returns a FunctionEstimator implementing the cost model.
func (OverloadModel) FunctionEstimatorWithOptions ¶ added in v0.33.0
func (m OverloadModel) FunctionEstimatorWithOptions(opts ...ModelOption) FunctionEstimator
FunctionEstimatorWithOptions returns a FunctionEstimator implementing the cost model, configured by the supplied options. Unset options take their defaults: the default SizingStrategy and the latest model revision.
func (OverloadModel) FunctionTracker ¶ added in v0.33.0
func (m OverloadModel) FunctionTracker() FunctionTracker
FunctionTracker returns a FunctionTracker implementing the cost model.
func (OverloadModel) FunctionTrackerWithOptions ¶ added in v0.33.0
func (m OverloadModel) FunctionTrackerWithOptions(opts ...ModelOption) FunctionTracker
FunctionTrackerWithOptions returns a FunctionTracker implementing the cost model, configured by the supplied options.
ModelVersion applies to tracking as it does to estimation, so that a call's estimate and its charge are computed by the same rules.
func (OverloadModel) Validate ¶ added in v0.33.0
func (m OverloadModel) Validate() error
Validate reports whether the model is well-formed.
A model is checked when it is registered, rather than when it is evaluated, because neither of the two evaluation paths can report a problem: an estimator has nowhere to return an error, and a tracker which cannot answer an expression would have to choose between charging nothing and charging the maximum, one of which lets an expression through and the other of which fails every evaluation that sets a cost limit.
The checks apply at every model version, because every model they reject is mispriced at every version. They are:
- the overload has an ID, and an evaluation cost expression;
- every Arg and IntArg index is non-negative;
- every element or key projection is applied to an expression which denotes a value;
- every ElemTotal, KeyTotal and Length is applied to Arg, Target or Result;
- a global overload does not reference the receiver;
- every Scale factor is finite and positive;
- no Ranged has constant bounds in the wrong order;
- the result size expression does not reference Result().
Projections read the value they project from, so ElemOf, KeyOf and the ArgElem, ArgKey, TargetElem and TargetKey shorthands are defined over Arg, Target, Result, and the ElemOf and KeyOf projections of those. A projection of a computed quantity, such as ElemOf(Sum(Arg(0), Arg(1))), has an estimate but no runtime counterpart, and is reported here. ElemTotal, KeyTotal and Length estimate a quantity from the size of a single value, so they are defined over Arg, Target and Result only.
type OverloadModelOption ¶ added in v0.33.0
type OverloadModelOption func(*OverloadModel)
OverloadModelOption functional options for configuring an OverloadModel.
func BeforeVersion ¶ added in v0.33.0
func BeforeVersion(version uint32, opts ...OverloadModelOption) OverloadModelOption
BeforeVersion records the options that priced the overload before the given model revision.
At revisions earlier than version, the overload is configured by opts (such as EvalCost, ResultSize, ManualCost, or ManualEstimator), inheriting the enclosing OverloadModel's ID, receiver kind, and any unset EvalCost or ResultSize.
func EvalCost ¶ added in v0.33.0
func EvalCost(cost QuantityExpr) OverloadModelOption
EvalCost sets the evaluation cost expression for the overload model.
func ManualCost ¶ added in v0.33.0
func ManualCost(estimator FunctionEstimator, tracker FunctionTracker) OverloadModelOption
ManualCost sets a custom FunctionEstimator and FunctionTracker for an overload whose cost or result size cannot be expressed declaratively with EvalCost and ResultSize.
Both functions are required; Validate reports a nil one. ManualCost cannot be combined with EvalCost, ResultSize, or ManualEstimator on the same OverloadModel or BeforeVersion entry.
func ManualEstimator ¶ added in v0.33.0
func ManualEstimator(estimator FunctionEstimator) OverloadModelOption
ManualEstimator sets a custom FunctionEstimator for an overload (or BeforeVersion entry) whose static estimate cannot be expressed declaratively with EvalCost and ResultSize, while retaining the OverloadModel's declarative EvalCost for runtime tracking.
ManualEstimator requires a non-nil FunctionEstimator and cannot be combined with ManualCost or ResultSize on the same OverloadModel or BeforeVersion entry.
func ResultSize ¶ added in v0.33.0
func ResultSize(size QuantityExpr) OverloadModelOption
ResultSize sets the result size expression for the overload model. Passing nil in a BeforeVersion entry clears any result size inherited from the enclosing OverloadModel.
type QuantityExpr ¶ added in v0.33.0
type QuantityExpr interface {
// contains filtered or unexported methods
}
QuantityExpr represents a computable size or cost equation.
func AllocList ¶ added in v0.33.0
func AllocList(terms ...QuantityExpr) QuantityExpr
AllocList creates an expression representing the cost of a call that allocates a list: CallCost + ListCreateBaseCost plus the given work terms.
func Arg ¶ added in v0.33.0
func Arg(index int) QuantityExpr
Arg creates an expression referencing the size of the argument at the given index.
func ArgElem ¶ added in v0.33.0
func ArgElem(index int) QuantityExpr
ArgElem creates an expression referencing the element size of the argument at the given index.
func ArgKey ¶ added in v0.33.0
func ArgKey(index int) QuantityExpr
ArgKey creates an expression referencing the key size of the argument at the given index.
func AtLeastOneQuantity ¶ added in v0.33.0
func AtLeastOneQuantity(expr QuantityExpr) QuantityExpr
AtLeastOneQuantity creates an expression ensuring the quantity is at least 1.
func AtMost ¶ added in v0.33.0
func AtMost(maxExpr QuantityExpr) QuantityExpr
AtMost creates an expression representing a quantity bounded between 0 and the upper bound of maxExpr.
func Const ¶ added in v0.33.0
func Const(val uint64) QuantityExpr
Const creates a constant quantity expression.
func ElemOf ¶ added in v0.33.0
func ElemOf(expr QuantityExpr) QuantityExpr
ElemOf creates an expression referencing the element size of another expression.
func ElemTotal ¶ added in v0.33.0
func ElemTotal(expr QuantityExpr) QuantityExpr
ElemTotal creates an expression referencing the combined size of every element of a list, or every value of a map, under the sizing strategy in effect: the length of a flattened list under the default strategy, or the content size of a list under the aggregate strategy. See KeyTotal for the keys of a map.
The operand must be Arg, Target or Result; see OverloadModel.Validate. The estimate is derived from the operand's size under the sizing strategy; see totalEstimate. At runtime this reports the exact total.
func IntArg ¶ added in v0.33.0
func IntArg(index int, defaultVal uint64) QuantityExpr
IntArg creates an expression referencing the integer value of the argument at the given index.
At runtime, an argument which is not an integer reads as defaultVal, and a negative integer reads as 0. When estimating, a literal argument reads as its value, and a non-literal argument is unbounded from model version 1 (or FixedSizeEstimate(defaultVal) at version 0).
func IntTarget ¶ added in v0.33.0
func IntTarget(defaultVal uint64) QuantityExpr
IntTarget creates an expression referencing the integer value of the receiver/target object, with the same runtime and estimation rules as IntArg.
func KeyOf ¶ added in v0.33.0
func KeyOf(expr QuantityExpr) QuantityExpr
KeyOf creates an expression referencing the key size of another expression.
func KeyTotal ¶ added in v0.33.0
func KeyTotal(expr QuantityExpr) QuantityExpr
KeyTotal creates an expression referencing the combined size of every key of a map. A value which is not a map has no keys.
The operand must be Arg, Target or Result; see OverloadModel.Validate. The estimate is derived from the operand's size under the sizing strategy; see totalEstimate. At runtime this reports the exact total.
func Length ¶ added in v0.33.0
func Length(expr QuantityExpr) QuantityExpr
Length creates an expression referencing the shallow top-level length of a single value (its CEL size() / ActualSize), independent of the sizing strategy: the number of code points of a string, bytes of a bytes value, top-level elements of a list or entries of a map, and 1 for any other value. Unlike Arg(i), Target(), or Result(), which report the depth-based total content size under AggregateSizingStrategy, Length always reports only the top-level container or value length.
The operand must be Arg, Target or Result; see OverloadModel.Validate. Length is a scalar and carries no element or key size.
Sizes follow the sizing strategy, so under the aggregate strategy Target() of a string is its UTF-8 byte count and Target() of a list is its depth-based aggregate content size. Length lets a model charge by top-level length under every strategy while still describing its result's size through List and Map.
func List ¶ added in v0.33.0
func List(lenExpr, elemExpr QuantityExpr) QuantityExpr
List creates an expression representing a list with the given length and element size.
The estimate is the size the sizing strategy assigns to such a list: its length under the default strategy, and 1 plus the length times the element size under the aggregate strategy. The track is the length.
func ListAlloc ¶ added in v0.33.0
func ListAlloc(elemCount QuantityExpr, costFactor float64) QuantityExpr
ListAlloc creates an expression representing list allocation cost with base cost and scaled element count.
func Map ¶ added in v0.33.0
func Map(sizeExpr, keyExpr, valExpr QuantityExpr) QuantityExpr
Map creates an expression representing a map with the given entry count, key size and value size.
The estimate is the size the sizing strategy assigns to such a map: its entry count under the default strategy, and 1 plus the entry count times the key and value sizes under the aggregate strategy. The track is the entry count.
func Max ¶ added in v0.33.0
func Max(lhs, rhs QuantityExpr) QuantityExpr
Max creates an expression representing the maximum of two quantities.
func Min ¶ added in v0.33.0
func Min(lhs, rhs QuantityExpr) QuantityExpr
Min creates an expression representing the minimum of two quantities.
func Mul ¶ added in v0.33.0
func Mul(terms ...QuantityExpr) QuantityExpr
Mul creates an expression representing the product of the given terms.
func Optional ¶ added in v0.33.0
func Optional(valueExpr QuantityExpr) QuantityExpr
Optional creates an expression representing an optional which holds a value of the given size.
From cost model version 1 an optional is 1 plus the size of the value it holds, under every sizing strategy: 1 plus the value's length under the default strategy, and 1 plus its aggregate size under the aggregate strategy. An empty optional is 1, which Optional(Const(0)) describes. The value is the optional's element, which ElemOf reads, so that value() and orValue() recover its size. Version 0 sizes every optional as 1, as cel-go v0.32.0 did.
func Ranged ¶ added in v0.33.0
func Ranged(minExpr, maxExpr QuantityExpr) QuantityExpr
Ranged creates an expression where the lower bound is taken from minExpr and the upper bound from maxExpr.
func Result ¶ added in v0.33.0
func Result() QuantityExpr
Result creates an expression referencing the size of the result.
func Scale ¶ added in v0.33.0
func Scale(expr QuantityExpr, factor float64) QuantityExpr
Scale creates an expression that scales another expression by a constant factor, rounding up.
Factors are constant so that a model's runtime charge depends only on the sizes reported by the sizing strategy. A cost which differs by argument type should be modeled with one OverloadModel per overload ID, since CEL already dispatches overloads by type. The factor must be finite and positive; Validate rejects any other.
The factor is applied as the simplest rational with the same float64 value, so that 0.1 scales by exactly 1/10, and the product is computed exactly; an unbounded quantity stays unbounded; and when a model is compiled, factors are moved outward so that each product is rounded once.
func Square ¶ added in v0.33.0
func Square(expr QuantityExpr) QuantityExpr
Square creates an expression representing the square of another expression.
func StringScan ¶ added in v0.33.0
func StringScan(expr QuantityExpr) QuantityExpr
StringScan creates an expression representing the cost of scanning a string.
func Sub ¶ added in v0.33.0
func Sub(lhs, rhs QuantityExpr) QuantityExpr
Sub creates an expression representing lhs - rhs, saturated at zero.
func Sum ¶ added in v0.33.0
func Sum(terms ...QuantityExpr) QuantityExpr
Sum creates an expression representing the sum of the given terms.
func Target ¶ added in v0.33.0
func Target() QuantityExpr
Target creates an expression referencing the size of the receiver / target object.
func TargetElem ¶ added in v0.33.0
func TargetElem() QuantityExpr
TargetElem creates an expression referencing the element size of the receiver / target object.
func TargetKey ¶ added in v0.33.0
func TargetKey() QuantityExpr
TargetKey creates an expression referencing the key size of the receiver / target object.
func Traversal ¶ added in v0.33.0
func Traversal(expr QuantityExpr, costFactor float64, allocCost uint64) QuantityExpr
Traversal creates an expression representing the traversal and optional allocation cost over an expression.
func Union ¶ added in v0.33.0
func Union(terms ...QuantityExpr) QuantityExpr
Union creates an expression representing the union interval of multiple expressions.
type SizeEstimate ¶ added in v0.33.0
type SizeEstimate struct {
// Min is the minimum estimated size (inclusive).
Min uint64
// Max is the maximum estimated size (inclusive).
Max uint64
// Key indicates the estimated size of a key, set if the size estimate is for a map.
Key *SizeEstimate
// Elem indicates the estimated size of a value, set if size estimate is for a map or list.
Elem *SizeEstimate
}
SizeEstimate represents an estimated size of a variable length string, bytes, map or list.
func AtLeastOneSize ¶ added in v0.33.0
func AtLeastOneSize(size SizeEstimate) SizeEstimate
AtLeastOneSize returns a size estimate with min and max guaranteed to be at least 1.
func EstimateSize ¶ added in v0.33.0
func EstimateSize(estimator Estimator, node AstNode) SizeEstimate
EstimateSize returns a SizeEstimate for the given node from its computed size, estimator, or unknown.
func FixedSizeEstimate ¶ added in v0.33.0
func FixedSizeEstimate(size uint64) SizeEstimate
FixedSizeEstimate returns a size estimate with a fixed min and max range.
func ListSizeEstimate ¶ added in v0.33.0
func ListSizeEstimate(listSize SizeEstimate, elemSize SizeEstimate) SizeEstimate
ListSizeEstimate returns a SizeEstimate for a list with the given list length and element size.
func MapSizeEstimate ¶ added in v0.33.0
func MapSizeEstimate(mapSize SizeEstimate, keySize SizeEstimate, valSize SizeEstimate) SizeEstimate
MapSizeEstimate returns a SizeEstimate for a map with the given map size, key size, and value size.
func RangedSizeEstimate ¶ added in v0.33.0
func RangedSizeEstimate(min, max uint64) SizeEstimate
RangedSizeEstimate returns a size estimate bounded by min and max.
func UnknownSizeEstimate ¶ added in v0.33.0
func UnknownSizeEstimate() SizeEstimate
UnknownSizeEstimate returns a size between 0 and max uint.
func (SizeEstimate) Add ¶ added in v0.33.0
func (se SizeEstimate) Add(sizeEstimate SizeEstimate) SizeEstimate
Add adds to another SizeEstimate and returns the sum. If add would result in an uint64 overflow, the result is math.MaxUint64.
func (SizeEstimate) AsCost ¶ added in v0.33.0
func (se SizeEstimate) AsCost() CostEstimate
AsCost converts a size estimate to an equivalent cost estimate.
func (SizeEstimate) IsUnknown ¶ added in v0.33.0
func (se SizeEstimate) IsUnknown() bool
IsUnknown returns true if the size estimate represents an unknown size (0 to math.MaxUint64 with no key or element sizes).
func (SizeEstimate) Multiply ¶ added in v0.33.0
func (se SizeEstimate) Multiply(sizeEstimate SizeEstimate) SizeEstimate
Multiply multiplies by another SizeEstimate and returns the product. If multiply would result in an uint64 overflow, the result is math.MaxUint64.
The product carries the union of the operands' key and element sizes, as Add, Subtract and Union do: a length scaled by a factor describes the same kind of element it started with. An estimator whose result holds something other than its operands' elements — expanded strings, for instance — must state that with List or Map rather than let the operands' sizes be inherited.
func (SizeEstimate) MultiplyByCost ¶ added in v0.33.0
func (se SizeEstimate) MultiplyByCost(estimate CostEstimate) CostEstimate
MultiplyByCost multiplies by the cost and returns the product. If multiply would result in an uint64 overflow, the result is math.MaxUint64.
func (SizeEstimate) MultiplyByCostFactor ¶ added in v0.33.0
func (se SizeEstimate) MultiplyByCostFactor(costPerUnit float64) CostEstimate
MultiplyByCostFactor multiplies a SizeEstimate by a cost factor and returns the CostEstimate with the nearest integer of the result, rounded up.
func (SizeEstimate) Subtract ¶ added in v0.33.0
func (se SizeEstimate) Subtract(sizeEstimate SizeEstimate) SizeEstimate
Subtract subtracts another SizeEstimate and returns the difference, saturating at zero.
func (SizeEstimate) Union ¶ added in v0.33.0
func (se SizeEstimate) Union(size SizeEstimate) SizeEstimate
Union returns a SizeEstimate that encompasses both input SizeEstimate values.
type SizingStrategy ¶ added in v0.33.0
type SizingStrategy interface {
// EstimateSize computes the size estimate for an AST node during cost estimation.
// For lists and maps, the returned SizeEstimate can recursively include Elem and Key sizes.
EstimateSize(ctx EstimateContext, node AstNode) (SizeEstimate, bool)
// TrackSize computes the actual runtime size of a value during cost tracking.
TrackSize(ctx TrackContext, value ref.Val) (uint64, bool)
}
SizingStrategy defines how sizes and container element sizes are estimated and tracked.
func AggregateSizingStrategy ¶ added in v0.33.0
func AggregateSizingStrategy(opts ...types.SizeCalculatorOption) SizingStrategy
AggregateSizingStrategy returns a SizingStrategy that computes recursive size estimates by following paths during cost estimation, and calculates actual runtime size using AggregateSize during cost tracking.
The strategy pins stringUnitLength to 1, overriding the types package default, so that raw character and byte lengths reach the cost model unscaled. This is deliberate: sizing strategies report raw dimensions, and cost expressions own the conversion to cost units by applying factors such as StringTraversalCostFactor.
Callers may supply additional SizeCalculatorOption values, which are applied after the pinned default.
Warning: passing types.SizeCalculatorStringUnitLength with a value other than 1 overrides the pinned default and causes string costs to be discounted twice, once by the calculator and again by the cost factor in the cost expression. A unit length of 10 combined with StringTraversalCostFactor yields an effective 100x discount rather than 10x.
func DefaultSizingStrategy ¶ added in v0.33.0
func DefaultSizingStrategy() SizingStrategy
DefaultSizingStrategy returns the default SizingStrategy implementation.
type TrackContext ¶ added in v0.33.0
type TrackContext interface {
TypeContext
// Arg returns the size of the argument at the given 0-based index.
Arg(index int) uint64
// Target returns the size of the receiver/target object, if present.
Target() uint64
// Result returns the size of the evaluated result, if present.
Result() uint64
// Estimator returns the runtime ActualCostEstimator, if configured.
Estimator() ActualCostEstimator
// Size returns the actual runtime size of a value.
Size(value ref.Val) uint64
// ArgValue returns the uint64 value of the argument at index, or defaultVal.
ArgValue(index int, defaultVal uint64) uint64
// TargetValue returns the uint64 value of the receiver/target, or defaultVal.
TargetValue(defaultVal uint64) uint64
// ArgVal returns the value of the argument at the given 0-based index, if present.
ArgVal(index int) (ref.Val, bool)
// TargetVal returns the value of the receiver/target object, if present.
TargetVal() (ref.Val, bool)
// ResultVal returns the evaluated result value, if present.
ResultVal() (ref.Val, bool)
}
TrackContext provides value size and argument evaluation during runtime cost tracking.
type Tracker ¶ added in v0.33.0
type Tracker struct {
Estimator ActualCostEstimator
Limit *uint64
// contains filtered or unexported fields
}
Tracker represents the information needed for tracking runtime cost.
func NewTracker ¶ added in v0.33.0
func NewTracker(estimator ActualCostEstimator, opts ...TrackerOption) (*Tracker, error)
NewTracker creates a new Tracker with a given estimator and a set of functional TrackerOption values.
The Tracker's configuration is fixed once it is returned; only its accumulated cost changes.
func (*Tracker) ActualCost ¶ added in v0.33.0
ActualCost returns the runtime cost.
func (*Tracker) Clone ¶ added in v0.33.0
Clone makes a shallow copy of the tracker with no accumulated cost. The different clones can be used independently from each other: they share only configuration, which is not modified after NewTracker returns.
func (*Tracker) CostCall ¶ added in v0.33.0
CostCall calculates the runtime cost for a function call.
func (*Tracker) CreateList ¶ added in v0.33.0
CreateList records list literal construction cost.
func (*Tracker) CreateStruct ¶ added in v0.33.0
CreateStruct records struct/object construction cost.
func (*Tracker) EvalAttribute ¶ added in v0.33.0
EvalAttribute records attribute resolution cost (ident / select).
func (*Tracker) EvalBinary ¶ added in v0.33.0
EvalBinary records the cost for a binary call expression.
func (*Tracker) EvalUnary ¶ added in v0.33.0
EvalUnary records the cost for a unary call expression.
func (*Tracker) EvalVarArgs ¶ added in v0.33.0
EvalVarArgs records the cost for a variadic call expression.
func (*Tracker) EvalZeroArity ¶ added in v0.33.0
EvalZeroArity records the cost for a 0-arity call expression.
func (*Tracker) ModelVersion ¶ added in v0.33.0
ModelVersion returns the cost model version configured on the tracker.
func (*Tracker) PresenceTestHasCost ¶ added in v0.33.0
PresenceTestHasCost returns whether presence testing has a cost.
type TrackerOption ¶ added in v0.33.0
type TrackerOption interface {
// contains filtered or unexported methods
}
TrackerOption configures the behavior of CostTracker objects.
func OverloadTracker ¶ added in v0.33.0
func OverloadTracker(overloadID string, fnTracker FunctionTracker) TrackerOption
OverloadTracker binds an overload ID to a runtime FunctionTracker implementation.
OverloadTracker instances augment or override ActualCostEstimator decisions, allowing for versioned and/or optional cost tracking changes.
func TrackerLimit ¶ added in v0.33.0
func TrackerLimit(limit uint64) TrackerOption
TrackerLimit sets the runtime limit on the evaluation cost during execution and will terminate the expression evaluation if the limit is exceeded.
func TrackerLimitExceededHandler ¶ added in v0.33.0
func TrackerLimitExceededHandler(handler func()) TrackerOption
TrackerLimitExceededHandler sets a custom handler invoked when the cost limit is exceeded.
func TrackerPresenceTestHasCost ¶ added in v0.33.0
func TrackerPresenceTestHasCost(hasCost bool) TrackerOption
TrackerPresenceTestHasCost determines whether presence testing has a cost of one or zero. Defaults to presence test has a cost of one.
type TypeContext ¶ added in v0.33.0
type TypeContext interface {
// TargetType returns the deduced type of the receiver/target object, if present.
TargetType() (*types.Type, bool)
// ArgType returns the deduced type of the argument at the given 0-based index.
ArgType(index int) (*types.Type, bool)
}
TypeContext provides type information for AST nodes.