compilation.go

Documentation: k8s.io/apiextensions-apiserver/pkg/apiserver/schema/cel

     1  /*
     2  Copyright 2021 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package cel
    18  
    19  import (
    20  	"fmt"
    21  	"strings"
    22  	"time"
    23  
    24  	"github.com/google/cel-go/cel"
    25  	"github.com/google/cel-go/checker"
    26  	"github.com/google/cel-go/common/types"
    27  
    28  	apiextensions "k8s.io/apiextensions-apiserver/pkg/apis/apiextensions/v1"
    29  	"k8s.io/apiextensions-apiserver/pkg/apiserver/schema"
    30  	"k8s.io/apimachinery/pkg/util/version"
    31  	celconfig "k8s.io/apiserver/pkg/apis/cel"
    32  	apiservercel "k8s.io/apiserver/pkg/cel"
    33  	"k8s.io/apiserver/pkg/cel/environment"
    34  	"k8s.io/apiserver/pkg/cel/library"
    35  	"k8s.io/apiserver/pkg/cel/metrics"
    36  )
    37  
    38  const (
    39  	// ScopedVarName is the variable name assigned to the locally scoped data element of a CEL validation
    40  	// expression.
    41  	ScopedVarName = "self"
    42  
    43  	// OldScopedVarName is the variable name assigned to the existing value of the locally scoped data element of a
    44  	// CEL validation expression.
    45  	OldScopedVarName = "oldSelf"
    46  )
    47  
    48  // CompilationResult represents the cel compilation result for one rule
    49  type CompilationResult struct {
    50  	Program cel.Program
    51  	Error   *apiservercel.Error
    52  	// If true, the compiled expression contains a reference to the identifier "oldSelf".
    53  	UsesOldSelf bool
    54  	// Represents the worst-case cost of the compiled expression in terms of CEL's cost units, as used by cel.EstimateCost.
    55  	MaxCost uint64
    56  	// MaxCardinality represents the worse case number of times this validation rule could be invoked if contained under an
    57  	// unbounded map or list in an OpenAPIv3 schema.
    58  	MaxCardinality uint64
    59  	// MessageExpression represents the cel Program that should be evaluated to generate an error message if the rule
    60  	// fails to validate. If no MessageExpression was given, or if this expression failed to compile, this will be nil.
    61  	MessageExpression cel.Program
    62  	// MessageExpressionError represents an error encountered during compilation of MessageExpression. If no error was
    63  	// encountered, this will be nil.
    64  	MessageExpressionError *apiservercel.Error
    65  	// MessageExpressionMaxCost represents the worst-case cost of the compiled MessageExpression in terms of CEL's cost units,
    66  	// as used by cel.EstimateCost.
    67  	MessageExpressionMaxCost uint64
    68  	// NormalizedRuleFieldPath represents the relative fieldPath specified by user after normalization.
    69  	NormalizedRuleFieldPath string
    70  }
    71  
    72  // EnvLoader delegates the decision of which CEL environment to use for each expression.
    73  // Callers should return the appropriate CEL environment based on the guidelines from
    74  // environment.NewExpressions and environment.StoredExpressions.
    75  type EnvLoader interface {
    76  	// RuleEnv returns the appropriate environment from the EnvSet for the given CEL rule.
    77  	RuleEnv(envSet *environment.EnvSet, expression string) *cel.Env
    78  	// MessageExpressionEnv returns the appropriate environment from the EnvSet for the given
    79  	// CEL messageExpressions.
    80  	MessageExpressionEnv(envSet *environment.EnvSet, expression string) *cel.Env
    81  }
    82  
    83  // NewExpressionsEnvLoader creates an EnvLoader that always uses the NewExpressions environment type.
    84  func NewExpressionsEnvLoader() EnvLoader {
    85  	return alwaysNewEnvLoader{loadFn: func(envSet *environment.EnvSet) *cel.Env {
    86  		return envSet.NewExpressionsEnv()
    87  	}}
    88  }
    89  
    90  // StoredExpressionsEnvLoader creates an EnvLoader that always uses the StoredExpressions environment type.
    91  func StoredExpressionsEnvLoader() EnvLoader {
    92  	return alwaysNewEnvLoader{loadFn: func(envSet *environment.EnvSet) *cel.Env {
    93  		return envSet.StoredExpressionsEnv()
    94  	}}
    95  }
    96  
    97  type alwaysNewEnvLoader struct {
    98  	loadFn func(envSet *environment.EnvSet) *cel.Env
    99  }
   100  
   101  func (pe alwaysNewEnvLoader) RuleEnv(envSet *environment.EnvSet, _ string) *cel.Env {
   102  	return pe.loadFn(envSet)
   103  }
   104  
   105  func (pe alwaysNewEnvLoader) MessageExpressionEnv(envSet *environment.EnvSet, _ string) *cel.Env {
   106  	return pe.loadFn(envSet)
   107  }
   108  
   109  // Compile compiles all the XValidations rules (without recursing into the schema) and returns a slice containing a
   110  // CompilationResult for each ValidationRule, or an error. declType is expected to be a CEL DeclType corresponding
   111  // to the structural schema.
   112  // Each CompilationResult may contain:
   113  //   - non-nil Program, nil Error: The program was compiled successfully
   114  //   - nil Program, non-nil Error: Compilation resulted in an error
   115  //   - nil Program, nil Error: The provided rule was empty so compilation was not attempted
   116  //
   117  // perCallLimit was added for testing purpose only. Callers should always use const PerCallLimit from k8s.io/apiserver/pkg/apis/cel/config.go as input.
   118  // baseEnv is used as the base CEL environment, see common.BaseEnvironment.
   119  func Compile(s *schema.Structural, declType *apiservercel.DeclType, perCallLimit uint64, baseEnvSet *environment.EnvSet, envLoader EnvLoader) ([]CompilationResult, error) {
   120  	t := time.Now()
   121  	defer func() {
   122  		metrics.Metrics.ObserveCompilation(time.Since(t))
   123  	}()
   124  
   125  	if len(s.Extensions.XValidations) == 0 {
   126  		return nil, nil
   127  	}
   128  	celRules := s.Extensions.XValidations
   129  
   130  	oldSelfEnvSet, optionalOldSelfEnvSet, err := prepareEnvSet(baseEnvSet, declType)
   131  	if err != nil {
   132  		return nil, err
   133  	}
   134  	estimator := newCostEstimator(declType)
   135  	// compResults is the return value which saves a list of compilation results in the same order as x-kubernetes-validations rules.
   136  	compResults := make([]CompilationResult, len(celRules))
   137  	maxCardinality := maxCardinality(declType.MinSerializedSize)
   138  	for i, rule := range celRules {
   139  		ruleEnvSet := oldSelfEnvSet
   140  		if rule.OptionalOldSelf != nil && *rule.OptionalOldSelf {
   141  			ruleEnvSet = optionalOldSelfEnvSet
   142  		}
   143  		compResults[i] = compileRule(s, rule, ruleEnvSet, envLoader, estimator, maxCardinality, perCallLimit)
   144  	}
   145  
   146  	return compResults, nil
   147  }
   148  
   149  func prepareEnvSet(baseEnvSet *environment.EnvSet, declType *apiservercel.DeclType) (oldSelfEnvSet *environment.EnvSet, optionalOldSelfEnvSet *environment.EnvSet, err error) {
   150  	scopedType := declType.MaybeAssignTypeName(generateUniqueSelfTypeName())
   151  
   152  	oldSelfEnvSet, err = baseEnvSet.Extend(
   153  		environment.VersionedOptions{
   154  			// Feature epoch was actually 1.23, but we artificially set it to 1.0 because these
   155  			// options should always be present.
   156  			IntroducedVersion: version.MajorMinor(1, 0),
   157  			EnvOptions: []cel.EnvOption{
   158  				cel.Variable(ScopedVarName, scopedType.CelType()),
   159  			},
   160  			DeclTypes: []*apiservercel.DeclType{
   161  				scopedType,
   162  			},
   163  		},
   164  		environment.VersionedOptions{
   165  			IntroducedVersion: version.MajorMinor(1, 24),
   166  			EnvOptions: []cel.EnvOption{
   167  				cel.Variable(OldScopedVarName, scopedType.CelType()),
   168  			},
   169  		},
   170  	)
   171  	if err != nil {
   172  		return nil, nil, err
   173  	}
   174  
   175  	optionalOldSelfEnvSet, err = baseEnvSet.Extend(
   176  		environment.VersionedOptions{
   177  			// Feature epoch was actually 1.23, but we artificially set it to 1.0 because these
   178  			// options should always be present.
   179  			IntroducedVersion: version.MajorMinor(1, 0),
   180  			EnvOptions: []cel.EnvOption{
   181  				cel.Variable(ScopedVarName, scopedType.CelType()),
   182  			},
   183  			DeclTypes: []*apiservercel.DeclType{
   184  				scopedType,
   185  			},
   186  		},
   187  		environment.VersionedOptions{
   188  			IntroducedVersion: version.MajorMinor(1, 24),
   189  			EnvOptions: []cel.EnvOption{
   190  				cel.Variable(OldScopedVarName, types.NewOptionalType(scopedType.CelType())),
   191  			},
   192  		},
   193  	)
   194  	if err != nil {
   195  		return nil, nil, err
   196  	}
   197  
   198  	return oldSelfEnvSet, optionalOldSelfEnvSet, nil
   199  }
   200  
   201  func compileRule(s *schema.Structural, rule apiextensions.ValidationRule, envSet *environment.EnvSet, envLoader EnvLoader, estimator *library.CostEstimator, maxCardinality uint64, perCallLimit uint64) (compilationResult CompilationResult) {
   202  	if len(strings.TrimSpace(rule.Rule)) == 0 {
   203  		// include a compilation result, but leave both program and error nil per documented return semantics of this
   204  		// function
   205  		return
   206  	}
   207  	ruleEnv := envLoader.RuleEnv(envSet, rule.Rule)
   208  	ast, issues := ruleEnv.Compile(rule.Rule)
   209  	if issues != nil {
   210  		compilationResult.Error = &apiservercel.Error{Type: apiservercel.ErrorTypeInvalid, Detail: "compilation failed: " + issues.String()}
   211  		return
   212  	}
   213  	if ast.OutputType() != cel.BoolType {
   214  		compilationResult.Error = &apiservercel.Error{Type: apiservercel.ErrorTypeInvalid, Detail: "cel expression must evaluate to a bool"}
   215  		return
   216  	}
   217  
   218  	checkedExpr, err := cel.AstToCheckedExpr(ast)
   219  	if err != nil {
   220  		// should be impossible since env.Compile returned no issues
   221  		compilationResult.Error = &apiservercel.Error{Type: apiservercel.ErrorTypeInternal, Detail: "unexpected compilation error: " + err.Error()}
   222  		return
   223  	}
   224  	for _, ref := range checkedExpr.ReferenceMap {
   225  		if ref.Name == OldScopedVarName {
   226  			compilationResult.UsesOldSelf = true
   227  			break
   228  		}
   229  	}
   230  
   231  	// TODO: Ideally we could configure the per expression limit at validation time and set it to the remaining overall budget, but we would either need a way to pass in a limit at evaluation time or move program creation to validation time
   232  	prog, err := ruleEnv.Program(ast,
   233  		cel.CostLimit(perCallLimit),
   234  		cel.CostTracking(estimator),
   235  		cel.InterruptCheckFrequency(celconfig.CheckFrequency),
   236  	)
   237  	if err != nil {
   238  		compilationResult.Error = &apiservercel.Error{Type: apiservercel.ErrorTypeInvalid, Detail: "program instantiation failed: " + err.Error()}
   239  		return
   240  	}
   241  	costEst, err := ruleEnv.EstimateCost(ast, estimator)
   242  	if err != nil {
   243  		compilationResult.Error = &apiservercel.Error{Type: apiservercel.ErrorTypeInternal, Detail: "cost estimation failed: " + err.Error()}
   244  		return
   245  	}
   246  	compilationResult.MaxCost = costEst.Max
   247  	compilationResult.MaxCardinality = maxCardinality
   248  	compilationResult.Program = prog
   249  	if rule.MessageExpression != "" {
   250  		messageEnv := envLoader.MessageExpressionEnv(envSet, rule.MessageExpression)
   251  		ast, issues := messageEnv.Compile(rule.MessageExpression)
   252  		if issues != nil {
   253  			compilationResult.MessageExpressionError = &apiservercel.Error{Type: apiservercel.ErrorTypeInvalid, Detail: "messageExpression compilation failed: " + issues.String()}
   254  			return
   255  		}
   256  		if ast.OutputType() != cel.StringType {
   257  			compilationResult.MessageExpressionError = &apiservercel.Error{Type: apiservercel.ErrorTypeInvalid, Detail: "messageExpression must evaluate to a string"}
   258  			return
   259  		}
   260  
   261  		_, err := cel.AstToCheckedExpr(ast)
   262  		if err != nil {
   263  			compilationResult.MessageExpressionError = &apiservercel.Error{Type: apiservercel.ErrorTypeInternal, Detail: "unexpected messageExpression compilation error: " + err.Error()}
   264  			return
   265  		}
   266  
   267  		msgProg, err := messageEnv.Program(ast,
   268  			cel.CostLimit(perCallLimit),
   269  			cel.CostTracking(estimator),
   270  			cel.InterruptCheckFrequency(celconfig.CheckFrequency),
   271  		)
   272  		if err != nil {
   273  			compilationResult.MessageExpressionError = &apiservercel.Error{Type: apiservercel.ErrorTypeInvalid, Detail: "messageExpression instantiation failed: " + err.Error()}
   274  			return
   275  		}
   276  		costEst, err := messageEnv.EstimateCost(ast, estimator)
   277  		if err != nil {
   278  			compilationResult.MessageExpressionError = &apiservercel.Error{Type: apiservercel.ErrorTypeInternal, Detail: "cost estimation failed for messageExpression: " + err.Error()}
   279  			return
   280  		}
   281  		compilationResult.MessageExpression = msgProg
   282  		compilationResult.MessageExpressionMaxCost = costEst.Max
   283  	}
   284  	if rule.FieldPath != "" {
   285  		validFieldPath, _, err := ValidFieldPath(rule.FieldPath, s)
   286  		if err == nil {
   287  			compilationResult.NormalizedRuleFieldPath = validFieldPath.String()
   288  		}
   289  	}
   290  	return
   291  }
   292  
   293  // generateUniqueSelfTypeName creates a placeholder type name to use in a CEL programs for cases
   294  // where we do not wish to expose a stable type name to CEL validator rule authors. For this to effectively prevent
   295  // developers from depending on the generated name (i.e. using it in CEL programs), it must be changed each time a
   296  // CRD is created or updated.
   297  func generateUniqueSelfTypeName() string {
   298  	return fmt.Sprintf("selfType%d", time.Now().Nanosecond())
   299  }
   300  
   301  func newCostEstimator(root *apiservercel.DeclType) *library.CostEstimator {
   302  	return &library.CostEstimator{SizeEstimator: &sizeEstimator{root: root}}
   303  }
   304  
   305  type sizeEstimator struct {
   306  	root *apiservercel.DeclType
   307  }
   308  
   309  func (c *sizeEstimator) EstimateSize(element checker.AstNode) *checker.SizeEstimate {
   310  	if len(element.Path()) == 0 {
   311  		// Path() can return an empty list, early exit if it does since we can't
   312  		// provide size estimates when that happens
   313  		return nil
   314  	}
   315  	currentNode := c.root
   316  	// cut off "self" from path, since we always start there
   317  	for _, name := range element.Path()[1:] {
   318  		switch name {
   319  		case "@items", "@values":
   320  			if currentNode.ElemType == nil {
   321  				return nil
   322  			}
   323  			currentNode = currentNode.ElemType
   324  		case "@keys":
   325  			if currentNode.KeyType == nil {
   326  				return nil
   327  			}
   328  			currentNode = currentNode.KeyType
   329  		default:
   330  			field, ok := currentNode.Fields[name]
   331  			if !ok {
   332  				return nil
   333  			}
   334  			if field.Type == nil {
   335  				return nil
   336  			}
   337  			currentNode = field.Type
   338  		}
   339  	}
   340  	return &checker.SizeEstimate{Min: 0, Max: uint64(currentNode.MaxElements)}
   341  }
   342  
   343  func (c *sizeEstimator) EstimateCallCost(function, overloadID string, target *checker.AstNode, args []checker.AstNode) *checker.CallEstimate {
   344  	return nil
   345  }
   346  
   347  // maxCardinality returns the maximum number of times data conforming to the minimum size given could possibly exist in
   348  // an object serialized to JSON. For cases where a schema is contained under map or array schemas of unbounded
   349  // size, this can be used as an estimate as the worst case number of times data matching the schema could be repeated.
   350  // Note that this only assumes a single comma between data elements, so if the schema is contained under only maps,
   351  // this estimates a higher cardinality that would be possible. DeclType.MinSerializedSize is meant to be passed to
   352  // this function.
   353  func maxCardinality(minSize int64) uint64 {
   354  	sz := minSize + 1 // assume at least one comma between elements
   355  	return uint64(celconfig.MaxRequestSizeBytes / sz)
   356  }
   357
View as plain text