interpreter

package
v0.22.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 22, 2024 License: Apache-2.0, BSD-3-Clause Imports: 15 Imported by: 49

Documentation

Overview

Package interpreter provides functions to evaluate parsed expressions with the option to augment the evaluation with inputs and functions supplied at evaluation time.

Index

Constants

This section is empty.

Variables

View Source 
var MatchesRegexOptimization = &RegexOptimization{
	Function:   "matches",
	RegexIndex: 1,
	Factory: func(call InterpretableCall, regexPattern string) (InterpretableCall, error) {
		compiledRegex, err := regexp.Compile(regexPattern)
		if err != nil {
			return nil, err
		}
		return NewCall(call.ID(), call.Function(), call.OverloadID(), call.Args(), func(values ...ref.Val) ref.Val {
			if len(values) != 2 {
				return types.NoSuchOverloadErr()
			}
			in, ok := values[0].Value().(string)
			if !ok {
				return types.NoSuchOverloadErr()
			}
			return types.Bool(compiledRegex.MatchString(in))
		}), nil
	},
}

MatchesRegexOptimization optimizes the 'matches' standard library function by compiling the regex pattern and reporting any compilation errors at program creation time, and using the compiled regex pattern for all function call invocations.

Functions

func PruneAst 

func PruneAst(expr ast.Expr, macroCalls map[int64]ast.Expr, state EvalState) *ast.AST

PruneAst prunes the given AST based on the given EvalState and generates a new AST. Given AST is copied on write and a new AST is returned. Couple of typical use cases this interface would be:

A) 1) Evaluate expr with some unknowns, 2) If result is unknown: 

a) PruneAst
b) Goto 1

Functional call results which are known would be effectively cached across iterations.

B) 1) Compile the expression (maybe via a service and maybe after checking a 

compiled expression does not exists in local cache)

2) Prepare the environment and the interpreter. Activation might be empty. 3) Eval the expression. This might return unknown or error or a concrete 

value.

4) PruneAst 4) Maybe cache the expression This is effectively constant folding the expression. How the environment is prepared in step 2 is flexible. For example, If the caller caches the compiled and constant folded expressions, but is not willing to constant fold(and thus cache results of) some external calls, then they can prepare the overloads accordingly.

Types

type Activation 

type Activation interface {
	// ResolveName returns a value from the activation by qualified name, or false if the name
	// could not be found.
	ResolveName(name string) (any, bool)

	// Parent returns the parent of the current activation, may be nil.
	// If non-nil, the parent will be searched during resolve calls.
	Parent() Activation
}

Activation used to resolve identifiers by name and references by id.

An Activation is the primary mechanism by which a caller supplies input into a CEL program.

func EmptyActivation added in v0.2.0 

func EmptyActivation() Activation

EmptyActivation returns a variable-free activation.

func NewActivation 

func NewActivation(bindings any) (Activation, error)

NewActivation returns an activation based on a map-based binding where the map keys are expected to be qualified names used with ResolveName calls.

The input `bindings` may either be of type `Activation` or `map[string]any`.

Lazy bindings may be supplied within the map-based input in either of the following forms: - func() any - func() ref.Val

The output of the lazy binding will overwrite the variable reference in the internal map.

Values which are not represented as ref.Val types on input may be adapted to a ref.Val using the types.Adapter configured in the environment.

func NewHierarchicalActivation 

func NewHierarchicalActivation(parent Activation, child Activation) Activation

NewHierarchicalActivation takes two activations and produces a new one which prioritizes resolution in the child first and parent(s) second.

type ActualCostEstimator added in v0.10.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 AttrFactoryOption added in v0.21.0 

type AttrFactoryOption func(*attrFactory) *attrFactory

AttrFactoryOption specifies a functional option for configuring an attribute factory.

func EnableErrorOnBadPresenceTest added in v0.21.0 

func EnableErrorOnBadPresenceTest(value bool) AttrFactoryOption

EnableErrorOnBadPresenceTest error generation when a presence test or optional field selection is performed on a primitive type.

type Attribute added in v0.4.0 

type Attribute interface {
	Qualifier

	// AddQualifier adds a qualifier on the Attribute or error if the qualification is not a valid qualifier type.
	AddQualifier(Qualifier) (Attribute, error)

	// Resolve returns the value of the Attribute and whether it was present given an Activation.
	// For objects which support safe traversal, the value may be non-nil and the presence flag be false.
	//
	// If an error is encountered during attribute resolution, it will be returned immediately.
	// If the attribute cannot be resolved within the Activation, the result must be: `nil`, `error`
	// with the error indicating which variable was missing.
	Resolve(Activation) (any, error)
}

Attribute values are a variable or value with an optional set of qualifiers, such as field, key, or index accesses.

type AttributeFactory added in v0.4.0 

type AttributeFactory interface {
	// AbsoluteAttribute creates an attribute that refers to a top-level variable name.
	//
	// Checked expressions generate absolute attribute with a single name.
	// Parse-only expressions may have more than one possible absolute identifier when the
	// expression is created within a container, e.g. package or namespace.
	//
	// When there is more than one name supplied to the AbsoluteAttribute call, the names
	// must be in CEL's namespace resolution order. The name arguments provided here are
	// returned in the same order as they were provided by the NamespacedAttribute
	// CandidateVariableNames method.
	AbsoluteAttribute(id int64, names ...string) NamespacedAttribute

	// ConditionalAttribute creates an attribute with two Attribute branches, where the Attribute
	// that is resolved depends on the boolean evaluation of the input 'expr'.
	ConditionalAttribute(id int64, expr Interpretable, t, f Attribute) Attribute

	// MaybeAttribute creates an attribute that refers to either a field selection or a namespaced
	// variable name.
	//
	// Only expressions which have not been type-checked may generate oneof attributes.
	MaybeAttribute(id int64, name string) Attribute

	// RelativeAttribute creates an attribute whose value is a qualification of a dynamic
	// computation rather than a static variable reference.
	RelativeAttribute(id int64, operand Interpretable) Attribute

	// NewQualifier creates a qualifier on the target object with a given value.
	//
	// The 'val' may be an Attribute or any proto-supported map key type: bool, int, string, uint.
	//
	// The qualifier may consider the object type being qualified, if present. If absent, the
	// qualification should be considered dynamic and the qualification should still work, though
	// it may be sub-optimal.
	NewQualifier(objType *types.Type, qualID int64, val any, opt bool) (Qualifier, error)
}

AttributeFactory provides methods creating Attribute and Qualifier values.

func NewAttributeFactory added in v0.4.0 

func NewAttributeFactory(cont *containers.Container, a types.Adapter, p types.Provider, opts ...AttrFactoryOption) AttributeFactory

NewAttributeFactory returns a default AttributeFactory which is produces Attribute values capable of resolving types by simple names and qualify the values using the supported qualifier types: bool, int, string, and uint.

func NewPartialAttributeFactory added in v0.4.0 

func NewPartialAttributeFactory(container *containers.Container, adapter types.Adapter, provider types.Provider, opts ...AttrFactoryOption) AttributeFactory

NewPartialAttributeFactory returns an AttributeFactory implementation capable of performing AttributePattern matches with PartialActivation inputs.

type AttributePattern added in v0.4.0 

type AttributePattern struct {
	// contains filtered or unexported fields
}

AttributePattern represents a top-level variable with an optional set of qualifier patterns.

When using a CEL expression within a container, e.g. a package or namespace, the variable name in the pattern must match the qualified name produced during the variable namespace resolution. For example, if variable `c` appears in an expression whose container is `a.b`, the variable name supplied to the pattern must be `a.b.c`

The qualifier patterns for attribute matching must be one of the following:

  • valid map key type: string, int, uint, bool
  • wildcard (*)

Examples:

  1. ns.myvar["complex-value"]
  2. ns.myvar["complex-value"][0]
  3. ns.myvar["complex-value"].*.name

The first example is simple: match an attribute where the variable is 'ns.myvar' with a field access on 'complex-value'. The second example expands the match to indicate that only a specific index `0` should match. And lastly, the third example matches any indexed access that later selects the 'name' field.

func NewAttributePattern added in v0.4.0 

func NewAttributePattern(variable string) *AttributePattern

NewAttributePattern produces a new mutable AttributePattern based on a variable name.

func (*AttributePattern) QualBool added in v0.4.0 

func (apat *AttributePattern) QualBool(pattern bool) *AttributePattern

QualBool adds a bool qualifier pattern for a map index operation to the AttributePattern.

func (*AttributePattern) QualInt added in v0.4.0 

func (apat *AttributePattern) QualInt(pattern int64) *AttributePattern

QualInt adds an int qualifier pattern to the AttributePattern. The index may be either a map or list index.

func (*AttributePattern) QualString added in v0.4.0 

func (apat *AttributePattern) QualString(pattern string) *AttributePattern

QualString adds a string qualifier pattern to the AttributePattern. The string may be a valid identifier, or string map key including empty string.

func (*AttributePattern) QualUint added in v0.4.0 

func (apat *AttributePattern) QualUint(pattern uint64) *AttributePattern

QualUint adds an uint qualifier pattern for a map index operation to the AttributePattern.

func (*AttributePattern) QualifierPatterns added in v0.4.0 

func (apat *AttributePattern) QualifierPatterns() []*AttributeQualifierPattern

QualifierPatterns returns the set of AttributeQualifierPattern values on the AttributePattern.

func (*AttributePattern) VariableMatches added in v0.4.0 

func (apat *AttributePattern) VariableMatches(variable string) bool

VariableMatches returns true if the fully qualified variable matches the AttributePattern fully qualified variable name.

func (*AttributePattern) Wildcard added in v0.4.0 

func (apat *AttributePattern) Wildcard() *AttributePattern

Wildcard adds a special sentinel qualifier pattern that will match any single qualifier.

type AttributeQualifierPattern added in v0.4.0 

type AttributeQualifierPattern struct {
	// contains filtered or unexported fields
}

AttributeQualifierPattern holds a wildcard or valued qualifier pattern.

func (*AttributeQualifierPattern) Matches added in v0.4.0 

func (qpat *AttributeQualifierPattern) Matches(q Qualifier) bool

Matches returns true if the qualifier pattern is a wildcard, or the Qualifier implements the qualifierValueEquator interface and its IsValueEqualTo returns true for the qualifier pattern.

type CancellationCause added in v0.10.0 

type CancellationCause int

CancellationCause enumerates the ways a program evaluation operation can be cancelled. 

const (
	// ContextCancelled indicates that the operation was cancelled in response to a Golang context cancellation.
	ContextCancelled CancellationCause = iota

	// CostLimitExceeded indicates that the operation was cancelled in response to the actual cost limit being
	// exceeded.
	CostLimitExceeded
)

type ConstantQualifier added in v0.6.0 

type ConstantQualifier interface {
	Qualifier

	// Value returns the constant value associated with the qualifier.
	Value() ref.Val
}

ConstantQualifier interface embeds the Qualifier interface and provides an option to inspect the qualifier's constant value.

Non-constant qualifiers are of Attribute type.

type CostTracker added in v0.10.0 

type CostTracker struct {
	Estimator ActualCostEstimator

	Limit *uint64
	// contains filtered or unexported fields
}

CostTracker represents the information needed for tracking runtime cost.

func NewCostTracker added in v0.16.0 

func NewCostTracker(estimator ActualCostEstimator, opts ...CostTrackerOption) (*CostTracker, error)

NewCostTracker creates a new CostTracker with a given estimator and a set of functional CostTrackerOption values.

func (*CostTracker) ActualCost added in v0.10.0 

func (c *CostTracker) ActualCost() uint64

ActualCost returns the runtime cost

type CostTrackerOption added in v0.16.0 

type CostTrackerOption func(*CostTracker) error

CostTrackerOption configures the behavior of CostTracker objects.

func CostTrackerLimit added in v0.16.0 

func CostTrackerLimit(limit uint64) CostTrackerOption

CostTrackerLimit sets the runtime limit on the evaluation cost during execution and will terminate the expression evaluation if the limit is exceeded.

func OverloadCostTracker added in v0.17.7 

func OverloadCostTracker(overloadID string, fnTracker FunctionTracker) CostTrackerOption

OverloadCostTracker binds an overload ID to a runtime FunctionTracker implementation.

OverloadCostTracker instances augment or override ActualCostEstimator decisions, allowing for versioned and/or optional cost tracking changes.

func PresenceTestHasCost added in v0.16.0 

func PresenceTestHasCost(hasCost bool) CostTrackerOption

PresenceTestHasCost determines whether presence testing has a cost of one or zero. Defaults to presence test has a cost of one.

type Dispatcher 

type Dispatcher interface {
	// Add one or more overloads, returning an error if any Overload has the same Overload#Name.
	Add(overloads ...*functions.Overload) error

	// FindOverload returns an Overload definition matching the provided name.
	FindOverload(overload string) (*functions.Overload, bool)

	// OverloadIds returns the set of all overload identifiers configured for dispatch.
	OverloadIds() []string
}

Dispatcher resolves function calls to their appropriate overload.

func ExtendDispatcher 

func ExtendDispatcher(parent Dispatcher) Dispatcher

ExtendDispatcher returns a Dispatcher which inherits the overloads of its parent, and provides an isolation layer between built-ins and extension functions which is useful for forward compatibility.

func NewDispatcher 

func NewDispatcher() Dispatcher

NewDispatcher returns an empty Dispatcher instance.

type EvalCancelledError added in v0.10.0 

type EvalCancelledError struct {
	Message string
	// Type identifies the cause of the cancellation.
	Cause CancellationCause
}

EvalCancelledError represents a cancelled program evaluation operation.

func (EvalCancelledError) Error added in v0.10.0 

func (e EvalCancelledError) Error() string

type EvalObserver added in v0.10.0 

type EvalObserver func(id int64, programStep any, value ref.Val)

EvalObserver is a functional interface that accepts an expression id and an observed value. The id identifies the expression that was evaluated, the programStep is the Interpretable or Qualifier that was evaluated and value is the result of the evaluation.

func CostObserver added in v0.10.0 

func CostObserver(tracker *CostTracker) EvalObserver

CostObserver provides an observer that tracks runtime cost.

func EvalStateObserver added in v0.10.0 

func EvalStateObserver(state EvalState) EvalObserver

EvalStateObserver provides an observer which records the value associated with the given expression id. EvalState must be provided to the observer. This decorator is not thread-safe, and the EvalState must be reset between Eval() calls.

type EvalState 

type EvalState interface {
	// IDs returns the list of ids with recorded values.
	IDs() []int64

	// Value returns the observed value of the given expression id if found, and a nil false
	// result if not.
	Value(int64) (ref.Val, bool)

	// SetValue sets the observed value of the expression id.
	SetValue(int64, ref.Val)

	// Reset clears the previously recorded expression values.
	Reset()
}

EvalState tracks the values associated with expression ids during execution.

func NewEvalState 

func NewEvalState() EvalState

NewEvalState returns an EvalState instanced used to observe the intermediate evaluations of an expression.

type FunctionTracker added in v0.17.7 

type FunctionTracker func(args []ref.Val, result ref.Val) *uint64

FunctionTracker computes the actual cost of evaluating the functions with the given arguments and result.

type Interpretable 

type Interpretable interface {
	// ID value corresponding to the expression node.
	ID() int64

	// Eval an Activation to produce an output.
	Eval(activation Activation) ref.Val
}

Interpretable can accept a given Activation and produce a value along with an accompanying EvalState which can be used to inspect whether additional data might be necessary to complete the evaluation.

type InterpretableAttribute added in v0.6.0 

type InterpretableAttribute interface {
	Interpretable

	// Attr returns the Attribute value.
	Attr() Attribute

	// Adapter returns the type adapter to be used for adapting resolved Attribute values.
	Adapter() types.Adapter

	// AddQualifier proxies the Attribute.AddQualifier method.
	//
	// Note, this method may mutate the current attribute state. If the desire is to clone the
	// Attribute, the Attribute should first be copied before adding the qualifier. Attributes
	// are not copyable by default, so this is a capable that would need to be added to the
	// AttributeFactory or specifically to the underlying Attribute implementation.
	AddQualifier(Qualifier) (Attribute, error)

	// Qualify replicates the Attribute.Qualify method to permit extension and interception
	// of object qualification.
	Qualify(vars Activation, obj any) (any, error)

	// QualifyIfPresent qualifies the object if the qualifier is declared or defined on the object.
	// The 'presenceOnly' flag indicates that the value is not necessary, just a boolean status as
	// to whether the qualifier is present.
	QualifyIfPresent(vars Activation, obj any, presenceOnly bool) (any, bool, error)

	// IsOptional indicates whether the resulting value is an optional type.
	IsOptional() bool

	// Resolve returns the value of the Attribute given the current Activation.
	Resolve(Activation) (any, error)
}

InterpretableAttribute interface for tracking whether the Interpretable is an attribute.

type InterpretableCall added in v0.6.0 

type InterpretableCall interface {
	Interpretable

	// Function returns the function name as it appears in text or mangled operator name as it
	// appears in the operators.go file.
	Function() string

	// OverloadID returns the overload id associated with the function specialization.
	// Overload ids are stable across language boundaries and can be treated as synonymous with a
	// unique function signature.
	OverloadID() string

	// Args returns the normalized arguments to the function overload.
	// For receiver-style functions, the receiver target is arg 0.
	Args() []Interpretable
}

InterpretableCall interface for inspecting Interpretable instructions related to function calls.

func NewCall added in v0.10.0 

func NewCall(id int64, function, overload string, args []Interpretable, impl functions.FunctionOp) InterpretableCall

NewCall creates a new call Interpretable.

type InterpretableConst added in v0.6.0 

type InterpretableConst interface {
	Interpretable

	// Value returns the constant value of the instruction.
	Value() ref.Val
}

InterpretableConst interface for tracking whether the Interpretable is a constant value.

func NewConstValue added in v0.6.0 

func NewConstValue(id int64, val ref.Val) InterpretableConst

NewConstValue creates a new constant valued Interpretable.

type InterpretableConstructor added in v0.10.0 

type InterpretableConstructor interface {
	Interpretable

	// InitVals returns all the list elements, map key and values or struct field values.
	InitVals() []Interpretable

	// Type returns the type constructed.
	Type() ref.Type
}

InterpretableConstructor interface for inspecting Interpretable instructions that initialize a list, map or struct.

type InterpretableDecorator 

type InterpretableDecorator func(Interpretable) (Interpretable, error)

InterpretableDecorator is a functional interface for decorating or replacing Interpretable expression nodes at construction time.

func CompileRegexConstants added in v0.10.0 

func CompileRegexConstants(regexOptimizations ...*RegexOptimization) InterpretableDecorator

CompileRegexConstants compiles regex pattern string constants at program creation time and reports any regex pattern compile errors.

func ExhaustiveEval 

func ExhaustiveEval() InterpretableDecorator

ExhaustiveEval replaces operations that short-circuit with versions that evaluate expressions and couples this behavior with the TrackState() decorator to provide insight into the evaluation state of the entire expression. EvalState must be provided to the decorator. This decorator is not thread-safe, and the EvalState must be reset between Eval() calls.

func InterruptableEval added in v0.10.0 

func InterruptableEval() InterpretableDecorator

InterruptableEval annotates comprehension loops with information that indicates they should check the `#interrupted` state within a custom Activation.

The custom activation is currently managed higher up in the stack within the 'cel' package and should not require any custom support on behalf of callers.

func Observe added in v0.10.0 

func Observe(observers ...EvalObserver) InterpretableDecorator

Observe constructs a decorator that calls all the provided observers in order after evaluating each Interpretable or Qualifier during program evaluation.

func Optimize added in v0.3.0 

func Optimize() InterpretableDecorator

Optimize will pre-compute operations such as list and map construction and optimize call arguments to set membership tests. The set of optimizations will increase over time.

func TrackState 

func TrackState(state EvalState) InterpretableDecorator

TrackState decorates each expression node with an observer which records the value associated with the given expression id. EvalState must be provided to the decorator. This decorator is not thread-safe, and the EvalState must be reset between Eval() calls. DEPRECATED: Please use EvalStateObserver instead. It composes gracefully with additional observers.

type Interpreter 

type Interpreter interface {
	// NewInterpretable creates an Interpretable from a checked expression and an
	// optional list of InterpretableDecorator values.
	NewInterpretable(exprAST *ast.AST, decorators ...InterpretableDecorator) (Interpretable, error)
}

Interpreter generates a new Interpretable from a checked or unchecked expression.

func NewInterpreter 

func NewInterpreter(dispatcher Dispatcher,
	container *containers.Container,
	provider types.Provider,
	adapter types.Adapter,
	attrFactory AttributeFactory) Interpreter

NewInterpreter builds an Interpreter from a Dispatcher and TypeProvider which will be used throughout the Eval of all Interpretable instances generated from it.

type NamespacedAttribute added in v0.4.0 

type NamespacedAttribute interface {
	Attribute

	// CandidateVariableNames returns the possible namespaced variable names for this Attribute in
	// the CEL namespace resolution order.
	CandidateVariableNames() []string

	// Qualifiers returns the list of qualifiers associated with the Attribute.
	Qualifiers() []Qualifier
}

NamespacedAttribute values are a variable within a namespace, and an optional set of qualifiers such as field, key, or index accesses.

type PartialActivation added in v0.4.0 

type PartialActivation interface {
	Activation

	// UnknownAttributePaths returns a set of AttributePattern values which match Attribute
	// expressions for data accesses whose values are not yet known.
	UnknownAttributePatterns() []*AttributePattern
}

PartialActivation extends the Activation interface with a set of UnknownAttributePatterns.

func NewPartialActivation added in v0.4.0 

func NewPartialActivation(bindings any,
	unknowns ...*AttributePattern) (PartialActivation, error)

NewPartialActivation returns an Activation which contains a list of AttributePattern values representing field and index operations that should result in a 'types.Unknown' result.

The `bindings` value may be any value type supported by the interpreter.NewActivation call, but is typically either an existing Activation or map[string]any.

type Qualifier added in v0.4.0 

type Qualifier interface {
	// ID where the qualifier appears within an expression.
	ID() int64

	// IsOptional specifies whether the qualifier is optional.
	// Instead of a direct qualification, an optional qualifier will be resolved via QualifyIfPresent
	// rather than Qualify. A non-optional qualifier may also be resolved through QualifyIfPresent if
	// the object to qualify is itself optional.
	IsOptional() bool

	// Qualify performs a qualification, e.g. field selection, on the input object and returns
	// the value of the access and whether the value was set. A non-nil value with a false presence
	// test result indicates that the value being returned is the default value.
	Qualify(vars Activation, obj any) (any, error)

	// QualifyIfPresent qualifies the object if the qualifier is declared or defined on the object.
	// The 'presenceOnly' flag indicates that the value is not necessary, just a boolean status as
	// to whether the qualifier is present.
	QualifyIfPresent(vars Activation, obj any, presenceOnly bool) (any, bool, error)
}

Qualifier marker interface for designating different qualifier values and where they appear within field selections and index call expressions (`_[_]`).

type RegexOptimization added in v0.10.0 

type RegexOptimization struct {
	// Function is the name of the function to optimize.
	Function string
	// OverloadID is the ID of the overload to optimize.
	OverloadID string
	// RegexIndex is the index position of the regex pattern argument. Only calls to the function where this argument is
	// a string constant will be delegated to this optimizer.
	RegexIndex int
	// Factory constructs a replacement InterpretableCall node that optimizes the regex function call. Factory is
	// provided with the unoptimized regex call and the string constant at the RegexIndex argument.
	// The Factory may compile the regex for use across all invocations of the call, return any errors and
	// return an interpreter.NewCall with the desired regex optimized function impl.
	Factory func(call InterpretableCall, regexPattern string) (InterpretableCall, error)
}

RegexOptimization provides a way to replace an InterpretableCall for a regex function when the RegexIndex argument is a string constant. Typically, the Factory would compile the regex pattern at RegexIndex and report any errors (at program creation time) and then use the compiled regex for all regex function invocations.

Source Files

View all Source files

Directories

Path Synopsis
Package functions defines the standard builtin functions supported by the interpreter and as declared within the checker#StandardDeclarations.
 Package functions defines the standard builtin functions supported by the interpreter and as declared within the checker#StandardDeclarations.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.