Source file src/k8s.io/apiextensions-apiserver/pkg/apiserver/schema/cel/compilation_test.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  	"math"
    22  	"strings"
    23  	"testing"
    24  
    25  	celgo "github.com/google/cel-go/cel"
    26  	"github.com/google/cel-go/common/types"
    27  	"github.com/google/cel-go/common/types/ref"
    28  
    29  	apiextensions "k8s.io/apiextensions-apiserver/pkg/apis/apiextensions/v1"
    30  	"k8s.io/apiextensions-apiserver/pkg/apiserver/schema"
    31  	"k8s.io/apiextensions-apiserver/pkg/apiserver/schema/cel/model"
    32  	apiextensionsfeatures "k8s.io/apiextensions-apiserver/pkg/features"
    33  	"k8s.io/apimachinery/pkg/util/version"
    34  	celconfig "k8s.io/apiserver/pkg/apis/cel"
    35  	"k8s.io/apiserver/pkg/cel"
    36  	"k8s.io/apiserver/pkg/cel/environment"
    37  	utilfeature "k8s.io/apiserver/pkg/util/feature"
    38  	featuregatetesting "k8s.io/component-base/featuregate/testing"
    39  	"k8s.io/utils/ptr"
    40  )
    41  
    42  const (
    43  	costLimit = 100000000
    44  )
    45  
    46  type validationMatcher interface {
    47  	matches(cr CompilationResult) bool
    48  	String() string
    49  }
    50  
    51  type allMatcher []validationMatcher
    52  
    53  func matchesAll(matchers ...validationMatcher) validationMatcher {
    54  	return allMatcher(matchers)
    55  }
    56  
    57  func (m allMatcher) matches(cr CompilationResult) bool {
    58  	for _, each := range m {
    59  		if !each.matches(cr) {
    60  			return false
    61  		}
    62  	}
    63  	return true
    64  }
    65  
    66  func (m allMatcher) String() string {
    67  	if len(m) == 0 {
    68  		return "any result"
    69  	}
    70  	var b strings.Builder
    71  	for i, each := range m {
    72  		b.WriteString(each.String())
    73  		if i < len(m)-1 {
    74  			b.WriteString(" and ")
    75  		}
    76  	}
    77  	return b.String()
    78  }
    79  
    80  type fnMatcher struct {
    81  	fn  func(CompilationResult) bool
    82  	msg string
    83  }
    84  
    85  func (m fnMatcher) matches(cr CompilationResult) bool {
    86  	return m.fn(cr)
    87  }
    88  
    89  func (m fnMatcher) String() string {
    90  	return m.msg
    91  }
    92  
    93  type errorMatcher struct {
    94  	errorType cel.ErrorType
    95  	contains  string
    96  }
    97  
    98  func invalidError(contains string) validationMatcher {
    99  	return errorMatcher{errorType: cel.ErrorTypeInvalid, contains: contains}
   100  }
   101  
   102  func (v errorMatcher) matches(cr CompilationResult) bool {
   103  	return cr.Error != nil && cr.Error.Type == v.errorType && strings.Contains(cr.Error.Error(), v.contains)
   104  }
   105  
   106  func (v errorMatcher) String() string {
   107  	return fmt.Sprintf("has error of type %q containing string %q", v.errorType, v.contains)
   108  }
   109  
   110  type messageExpressionErrorMatcher struct {
   111  	contains string
   112  }
   113  
   114  func messageExpressionError(contains string) validationMatcher {
   115  	return messageExpressionErrorMatcher{contains: contains}
   116  }
   117  
   118  func (m messageExpressionErrorMatcher) matches(cr CompilationResult) bool {
   119  	return cr.MessageExpressionError != nil && cr.MessageExpressionError.Type == cel.ErrorTypeInvalid && strings.Contains(cr.MessageExpressionError.Error(), m.contains)
   120  }
   121  
   122  func (m messageExpressionErrorMatcher) String() string {
   123  	return fmt.Sprintf("has messageExpression error containing string %q", m.contains)
   124  }
   125  
   126  type noErrorMatcher struct{}
   127  
   128  func noError() validationMatcher {
   129  	return noErrorMatcher{}
   130  }
   131  
   132  func (noErrorMatcher) matches(cr CompilationResult) bool {
   133  	return cr.Error == nil
   134  }
   135  
   136  func (noErrorMatcher) String() string {
   137  	return "no error"
   138  }
   139  
   140  type transitionRuleMatcher bool
   141  
   142  func transitionRule(t bool) validationMatcher {
   143  	return transitionRuleMatcher(t)
   144  }
   145  
   146  func (v transitionRuleMatcher) matches(cr CompilationResult) bool {
   147  	return cr.UsesOldSelf == bool(v)
   148  }
   149  
   150  func (v transitionRuleMatcher) String() string {
   151  	if v {
   152  		return "is a transition rule"
   153  	}
   154  	return "is not a transition rule"
   155  }
   156  
   157  func TestCelCompilation(t *testing.T) {
   158  	defer featuregatetesting.SetFeatureGateDuringTest(t, utilfeature.DefaultFeatureGate, apiextensionsfeatures.CRDValidationRatcheting, true)()
   159  	cases := []struct {
   160  		name            string
   161  		input           schema.Structural
   162  		expectedResults []validationMatcher
   163  		unmodified      bool
   164  	}{
   165  		{
   166  			name: "optional primitive transition rule type checking",
   167  			input: schema.Structural{
   168  				Generic: schema.Generic{
   169  					Type: "integer",
   170  				},
   171  				Extensions: schema.Extensions{
   172  					XValidations: apiextensions.ValidationRules{
   173  						{Rule: "self >= oldSelf.value()", OptionalOldSelf: ptr.To(true)},
   174  						{Rule: "self >= oldSelf.orValue(1)", OptionalOldSelf: ptr.To(true)},
   175  						{Rule: "oldSelf.hasValue() ? self >= oldSelf.value() : true", OptionalOldSelf: ptr.To(true)},
   176  						{Rule: "self >= oldSelf", OptionalOldSelf: ptr.To(true)},
   177  						{Rule: "self >= oldSelf.orValue('')", OptionalOldSelf: ptr.To(true)},
   178  					},
   179  				},
   180  			},
   181  			expectedResults: []validationMatcher{
   182  				matchesAll(noError(), transitionRule(true)),
   183  				matchesAll(noError(), transitionRule(true)),
   184  				matchesAll(noError(), transitionRule(true)),
   185  				matchesAll(invalidError("optional")),
   186  				matchesAll(invalidError("orValue")),
   187  			},
   188  		},
   189  		{
   190  			name: "optional complex transition rule type checking",
   191  			input: schema.Structural{
   192  				Generic: schema.Generic{
   193  					Type: "object",
   194  				},
   195  				Properties: map[string]schema.Structural{
   196  					"i": {Generic: schema.Generic{Type: "integer"}},
   197  					"b": {Generic: schema.Generic{Type: "boolean"}},
   198  					"s": {Generic: schema.Generic{Type: "string"}},
   199  					"a": {
   200  						Generic: schema.Generic{Type: "array"},
   201  						Items:   &schema.Structural{Generic: schema.Generic{Type: "integer"}},
   202  					},
   203  					"o": {
   204  						Generic: schema.Generic{Type: "object"},
   205  						Properties: map[string]schema.Structural{
   206  							"i": {Generic: schema.Generic{Type: "integer"}},
   207  							"b": {Generic: schema.Generic{Type: "boolean"}},
   208  							"s": {Generic: schema.Generic{Type: "string"}},
   209  							"a": {
   210  								Generic: schema.Generic{Type: "array"},
   211  								Items:   &schema.Structural{Generic: schema.Generic{Type: "integer"}},
   212  							},
   213  							"o": {
   214  								Generic: schema.Generic{Type: "object"},
   215  							},
   216  						},
   217  					},
   218  				},
   219  				Extensions: schema.Extensions{
   220  					XValidations: apiextensions.ValidationRules{
   221  						{Rule: "self.i >= oldSelf.i.value()", OptionalOldSelf: ptr.To(true)},
   222  						{Rule: "self.s == oldSelf.s.value()", OptionalOldSelf: ptr.To(true)},
   223  						{Rule: "self.b == oldSelf.b.value()", OptionalOldSelf: ptr.To(true)},
   224  						{Rule: "self.o == oldSelf.o.value()", OptionalOldSelf: ptr.To(true)},
   225  						{Rule: "self.o.i >= oldSelf.o.i.value()", OptionalOldSelf: ptr.To(true)},
   226  						{Rule: "self.o.s == oldSelf.o.s.value()", OptionalOldSelf: ptr.To(true)},
   227  						{Rule: "self.o.b == oldSelf.o.b.value()", OptionalOldSelf: ptr.To(true)},
   228  						{Rule: "self.o.o == oldSelf.o.o.value()", OptionalOldSelf: ptr.To(true)},
   229  						{Rule: "self.o.i >= oldSelf.o.i.orValue(1)", OptionalOldSelf: ptr.To(true)},
   230  						{Rule: "oldSelf.hasValue() ? self.o.i >= oldSelf.o.i.value() : true", OptionalOldSelf: ptr.To(true)},
   231  						{Rule: "self.o.i >= oldSelf.o.i", OptionalOldSelf: ptr.To(true)},
   232  						{Rule: "self.o.i >= oldSelf.o.s.orValue(0)", OptionalOldSelf: ptr.To(true)},
   233  					},
   234  				},
   235  			},
   236  			expectedResults: []validationMatcher{
   237  				matchesAll(noError(), transitionRule(true)),
   238  				matchesAll(noError(), transitionRule(true)),
   239  				matchesAll(noError(), transitionRule(true)),
   240  				matchesAll(noError(), transitionRule(true)),
   241  				matchesAll(noError(), transitionRule(true)),
   242  				matchesAll(noError(), transitionRule(true)),
   243  				matchesAll(noError(), transitionRule(true)),
   244  				matchesAll(noError(), transitionRule(true)),
   245  				matchesAll(noError(), transitionRule(true)),
   246  				matchesAll(noError(), transitionRule(true)),
   247  				matchesAll(invalidError("optional")),
   248  				matchesAll(invalidError("orValue")),
   249  			},
   250  		},
   251  		{
   252  			name: "valid object",
   253  			input: schema.Structural{
   254  				Generic: schema.Generic{
   255  					Type: "object",
   256  				},
   257  				Properties: map[string]schema.Structural{
   258  					"minReplicas": {
   259  						Generic: schema.Generic{
   260  							Type: "integer",
   261  						},
   262  					},
   263  					"maxReplicas": {
   264  						Generic: schema.Generic{
   265  							Type: "integer",
   266  						},
   267  					},
   268  				},
   269  				Extensions: schema.Extensions{
   270  					XValidations: apiextensions.ValidationRules{
   271  						{
   272  							Rule:    "self.minReplicas < self.maxReplicas",
   273  							Message: "minReplicas should be smaller than maxReplicas",
   274  						},
   275  					},
   276  				},
   277  			},
   278  			expectedResults: []validationMatcher{
   279  				noError(),
   280  			},
   281  		},
   282  		{
   283  			name: "valid for string",
   284  			input: schema.Structural{
   285  				Generic: schema.Generic{
   286  					Type: "string",
   287  				},
   288  				Extensions: schema.Extensions{
   289  					XValidations: apiextensions.ValidationRules{
   290  						{
   291  							Rule:    "self.startsWith('s')",
   292  							Message: "scoped field should start with 's'",
   293  						},
   294  					},
   295  				},
   296  			},
   297  			expectedResults: []validationMatcher{
   298  				noError(),
   299  			},
   300  		},
   301  		{
   302  			name: "valid for byte",
   303  			input: schema.Structural{
   304  				Generic: schema.Generic{
   305  					Type: "string",
   306  				},
   307  				ValueValidation: &schema.ValueValidation{
   308  					Format: "byte",
   309  				},
   310  				Extensions: schema.Extensions{
   311  					XValidations: apiextensions.ValidationRules{
   312  						{
   313  							Rule:    "string(self).endsWith('s')",
   314  							Message: "scoped field should end with 's'",
   315  						},
   316  					},
   317  				},
   318  			},
   319  			expectedResults: []validationMatcher{
   320  				noError(),
   321  			},
   322  		},
   323  		{
   324  			name: "valid for boolean",
   325  			input: schema.Structural{
   326  				Generic: schema.Generic{
   327  					Type: "boolean",
   328  				},
   329  				Extensions: schema.Extensions{
   330  					XValidations: apiextensions.ValidationRules{
   331  						{
   332  							Rule:    "self == true",
   333  							Message: "scoped field should be true",
   334  						},
   335  					},
   336  				},
   337  			},
   338  			expectedResults: []validationMatcher{
   339  				noError(),
   340  			},
   341  		},
   342  		{
   343  			name: "valid for integer",
   344  			input: schema.Structural{
   345  				Generic: schema.Generic{
   346  					Type: "integer",
   347  				},
   348  				Extensions: schema.Extensions{
   349  					XValidations: apiextensions.ValidationRules{
   350  						{
   351  							Rule:    "self > 0",
   352  							Message: "scoped field should be greater than 0",
   353  						},
   354  					},
   355  				},
   356  			},
   357  			expectedResults: []validationMatcher{
   358  				noError(),
   359  			},
   360  		},
   361  		{
   362  			name: "valid for number",
   363  			input: schema.Structural{
   364  				Generic: schema.Generic{
   365  					Type: "number",
   366  				},
   367  				Extensions: schema.Extensions{
   368  					XValidations: apiextensions.ValidationRules{
   369  						{
   370  							Rule:    "self > 1.0",
   371  							Message: "scoped field should be greater than 1.0",
   372  						},
   373  					},
   374  				},
   375  			},
   376  			expectedResults: []validationMatcher{
   377  				noError(),
   378  			},
   379  		},
   380  		{
   381  			name: "valid nested object of object",
   382  			input: schema.Structural{
   383  				Generic: schema.Generic{
   384  					Type: "object",
   385  				},
   386  				Properties: map[string]schema.Structural{
   387  					"nestedObj": {
   388  						Generic: schema.Generic{
   389  							Type: "object",
   390  						},
   391  						Properties: map[string]schema.Structural{
   392  							"val": {
   393  								Generic: schema.Generic{
   394  									Type: "integer",
   395  								},
   396  								ValueValidation: &schema.ValueValidation{
   397  									Format: "int64",
   398  								},
   399  							},
   400  						},
   401  					},
   402  				},
   403  				Extensions: schema.Extensions{
   404  					XValidations: apiextensions.ValidationRules{
   405  						{
   406  							Rule:    "self.nestedObj.val == 10",
   407  							Message: "val should be equal to 10",
   408  						},
   409  					},
   410  				},
   411  			},
   412  			expectedResults: []validationMatcher{
   413  				noError(),
   414  			},
   415  		},
   416  		{
   417  			name: "valid nested object of array",
   418  			input: schema.Structural{
   419  				Generic: schema.Generic{
   420  					Type: "object",
   421  				},
   422  				Properties: map[string]schema.Structural{
   423  					"nestedObj": {
   424  						Generic: schema.Generic{
   425  							Type: "array",
   426  						},
   427  						Items: &schema.Structural{
   428  							Generic: schema.Generic{
   429  								Type: "array",
   430  							},
   431  							Items: &schema.Structural{
   432  								Generic: schema.Generic{
   433  									Type: "string",
   434  								},
   435  							},
   436  						},
   437  					},
   438  				},
   439  				Extensions: schema.Extensions{
   440  					XValidations: apiextensions.ValidationRules{
   441  						{
   442  							Rule:    "size(self.nestedObj[0]) == 10",
   443  							Message: "size of first element in nestedObj should be equal to 10",
   444  						},
   445  					},
   446  				},
   447  			},
   448  			expectedResults: []validationMatcher{
   449  				noError(),
   450  			},
   451  		},
   452  		{
   453  			name: "valid nested array of array",
   454  			input: schema.Structural{
   455  				Generic: schema.Generic{
   456  					Type: "array",
   457  				},
   458  				Items: &schema.Structural{
   459  					Generic: schema.Generic{
   460  						Type: "array",
   461  					},
   462  					Items: &schema.Structural{
   463  						Generic: schema.Generic{
   464  							Type: "array",
   465  						},
   466  						Items: &schema.Structural{
   467  							Generic: schema.Generic{
   468  								Type: "string",
   469  							},
   470  						},
   471  					},
   472  				},
   473  				Extensions: schema.Extensions{
   474  					XValidations: apiextensions.ValidationRules{
   475  						{
   476  							Rule:    "size(self[0][0]) == 10",
   477  							Message: "size of items under items of scoped field should be equal to 10",
   478  						},
   479  					},
   480  				},
   481  			},
   482  			expectedResults: []validationMatcher{
   483  				noError(),
   484  			},
   485  		},
   486  		{
   487  			name: "valid nested array of object",
   488  			input: schema.Structural{
   489  				Generic: schema.Generic{
   490  					Type: "array",
   491  				},
   492  				Items: &schema.Structural{
   493  					Generic: schema.Generic{
   494  						Type: "object",
   495  					},
   496  					Properties: map[string]schema.Structural{
   497  						"nestedObj": {
   498  							Generic: schema.Generic{
   499  								Type: "object",
   500  							},
   501  							Properties: map[string]schema.Structural{
   502  								"val": {
   503  									Generic: schema.Generic{
   504  										Type: "integer",
   505  									},
   506  									ValueValidation: &schema.ValueValidation{
   507  										Format: "int64",
   508  									},
   509  								},
   510  							},
   511  						},
   512  					},
   513  				},
   514  				Extensions: schema.Extensions{
   515  					XValidations: apiextensions.ValidationRules{
   516  						{
   517  							Rule:    "self[0].nestedObj.val == 10",
   518  							Message: "val under nestedObj under properties under items should be equal to 10",
   519  						},
   520  					},
   521  				},
   522  			},
   523  			expectedResults: []validationMatcher{
   524  				noError(),
   525  			},
   526  		},
   527  		{
   528  			name: "valid map",
   529  			input: schema.Structural{
   530  				Generic: schema.Generic{
   531  					Type: "object",
   532  					AdditionalProperties: &schema.StructuralOrBool{
   533  						Bool: true,
   534  						Structural: &schema.Structural{
   535  							Generic: schema.Generic{
   536  								Type:     "boolean",
   537  								Nullable: false,
   538  							},
   539  						},
   540  					},
   541  				},
   542  				Extensions: schema.Extensions{
   543  					XValidations: apiextensions.ValidationRules{
   544  						{
   545  							Rule:    "size(self) > 0",
   546  							Message: "size of scoped field should be greater than 0",
   547  						},
   548  					},
   549  				},
   550  			},
   551  			expectedResults: []validationMatcher{
   552  				noError(),
   553  			},
   554  		},
   555  		{
   556  			name: "invalid checking for number",
   557  			input: schema.Structural{
   558  				Generic: schema.Generic{
   559  					Type: "number",
   560  				},
   561  				Extensions: schema.Extensions{
   562  					XValidations: apiextensions.ValidationRules{
   563  						{
   564  							Rule:    "size(self) == 10",
   565  							Message: "size of scoped field should be equal to 10",
   566  						},
   567  					},
   568  				},
   569  			},
   570  			expectedResults: []validationMatcher{
   571  				invalidError("compilation failed"),
   572  			},
   573  		},
   574  		{
   575  			name: "compilation failure",
   576  			input: schema.Structural{
   577  				Generic: schema.Generic{
   578  					Type: "integer",
   579  				},
   580  				Extensions: schema.Extensions{
   581  					XValidations: apiextensions.ValidationRules{
   582  						{
   583  							Rule:    "size(self) == 10",
   584  							Message: "size of scoped field should be equal to 10",
   585  						},
   586  					},
   587  				},
   588  			},
   589  			expectedResults: []validationMatcher{
   590  				invalidError("compilation failed"),
   591  			},
   592  		},
   593  		{
   594  			name: "valid for escaping",
   595  			input: schema.Structural{
   596  				Generic: schema.Generic{
   597  					Type: "object",
   598  				},
   599  				Properties: map[string]schema.Structural{
   600  					"namespace": {
   601  						Generic: schema.Generic{
   602  							Type: "array",
   603  						},
   604  						Items: &schema.Structural{
   605  							Generic: schema.Generic{
   606  								Type: "array",
   607  							},
   608  							Items: &schema.Structural{
   609  								Generic: schema.Generic{
   610  									Type: "string",
   611  								},
   612  							},
   613  						},
   614  					},
   615  					"if": {
   616  						Generic: schema.Generic{
   617  							Type: "integer",
   618  						},
   619  					},
   620  					"self": {
   621  						Generic: schema.Generic{
   622  							Type: "integer",
   623  						},
   624  					},
   625  				},
   626  				Extensions: schema.Extensions{
   627  					XValidations: apiextensions.ValidationRules{
   628  						{
   629  							Rule:    "size(self.__namespace__[0]) == 10",
   630  							Message: "size of first element in nestedObj should be equal to 10",
   631  						},
   632  						{
   633  							Rule: "self.__if__ == 10",
   634  						},
   635  						{
   636  							Rule: "self.self == 10",
   637  						},
   638  					},
   639  				},
   640  			},
   641  			expectedResults: []validationMatcher{
   642  				noError(),
   643  				noError(),
   644  				noError(),
   645  			},
   646  		},
   647  		{
   648  			name: "invalid for escaping",
   649  			input: schema.Structural{
   650  				Generic: schema.Generic{
   651  					Type: "object",
   652  				},
   653  				Properties: map[string]schema.Structural{
   654  					"namespace": {
   655  						Generic: schema.Generic{
   656  							Type: "array",
   657  						},
   658  						Items: &schema.Structural{
   659  							Generic: schema.Generic{
   660  								Type: "array",
   661  							},
   662  							Items: &schema.Structural{
   663  								Generic: schema.Generic{
   664  									Type: "string",
   665  								},
   666  							},
   667  						},
   668  					},
   669  					"if": {
   670  						Generic: schema.Generic{
   671  							Type: "integer",
   672  						},
   673  					},
   674  					"self": {
   675  						Generic: schema.Generic{
   676  							Type: "integer",
   677  						},
   678  					},
   679  				},
   680  				Extensions: schema.Extensions{
   681  					XValidations: apiextensions.ValidationRules{
   682  						{
   683  							Rule:    "size(self.namespace[0]) == 10",
   684  							Message: "size of first element in nestedObj should be equal to 10",
   685  						},
   686  						{
   687  							Rule: "self.if == 10",
   688  						},
   689  						{
   690  							Rule: "self == 10",
   691  						},
   692  					},
   693  				},
   694  			},
   695  			expectedResults: []validationMatcher{
   696  				invalidError("undefined field 'namespace'"),
   697  				invalidError("undefined field 'if'"),
   698  				invalidError("found no matching overload"),
   699  			},
   700  		},
   701  		{
   702  			name: "transition rule identified",
   703  			input: schema.Structural{
   704  				Generic: schema.Generic{
   705  					Type: "integer",
   706  				},
   707  				Extensions: schema.Extensions{
   708  					XValidations: apiextensions.ValidationRules{
   709  						{Rule: "self > 0"},
   710  						{Rule: "self >= oldSelf"},
   711  					},
   712  				},
   713  			},
   714  			expectedResults: []validationMatcher{
   715  				matchesAll(noError(), transitionRule(false)),
   716  				matchesAll(noError(), transitionRule(true)),
   717  			},
   718  		},
   719  		{
   720  			name: "whitespace-only rule",
   721  			input: schema.Structural{
   722  				Generic: schema.Generic{
   723  					Type: "object",
   724  				},
   725  				Extensions: schema.Extensions{
   726  					XValidations: apiextensions.ValidationRules{
   727  						{Rule: " \t"},
   728  					},
   729  				},
   730  			},
   731  			expectedResults: []validationMatcher{
   732  				matchesAll(
   733  					noError(),
   734  					fnMatcher{
   735  						msg: "program is nil",
   736  						fn: func(cr CompilationResult) bool {
   737  							return cr.Program == nil
   738  						},
   739  					}),
   740  			},
   741  		},
   742  		{
   743  			name: "expression must evaluate to bool",
   744  			input: schema.Structural{
   745  				Generic: schema.Generic{
   746  					Type: "object",
   747  				},
   748  				Extensions: schema.Extensions{
   749  					XValidations: apiextensions.ValidationRules{
   750  						{Rule: "42"},
   751  					},
   752  				},
   753  			},
   754  			expectedResults: []validationMatcher{
   755  				invalidError("must evaluate to a bool"),
   756  			},
   757  		},
   758  		{
   759  			name: "messageExpression inclusion",
   760  			input: schema.Structural{
   761  				Generic: schema.Generic{
   762  					Type: "string",
   763  				},
   764  				Extensions: schema.Extensions{
   765  					XValidations: apiextensions.ValidationRules{
   766  						{
   767  							Rule:              "self.startsWith('s')",
   768  							MessageExpression: `"scoped field should start with 's'"`,
   769  						},
   770  					},
   771  				},
   772  			},
   773  			expectedResults: []validationMatcher{
   774  				noError(),
   775  			},
   776  		},
   777  		{
   778  			name: "messageExpression must evaluate to a string",
   779  			input: schema.Structural{
   780  				Generic: schema.Generic{
   781  					Type: "integer",
   782  				},
   783  				Extensions: schema.Extensions{
   784  					XValidations: apiextensions.ValidationRules{
   785  						{
   786  							Rule:              "self == 5",
   787  							MessageExpression: `42`,
   788  						},
   789  					},
   790  				},
   791  			},
   792  			expectedResults: []validationMatcher{
   793  				messageExpressionError("must evaluate to a string"),
   794  			},
   795  		},
   796  		{
   797  			name: "messageExpression syntax error",
   798  			input: schema.Structural{
   799  				Generic: schema.Generic{
   800  					Type: "number",
   801  				},
   802  				Extensions: schema.Extensions{
   803  					XValidations: apiextensions.ValidationRules{
   804  						{
   805  							Rule:              "self < 32.0",
   806  							MessageExpression: `"abc`,
   807  						},
   808  					},
   809  				},
   810  			},
   811  			expectedResults: []validationMatcher{
   812  				messageExpressionError("messageExpression compilation failed"),
   813  			},
   814  		},
   815  		{
   816  			name: "unmodified expression may use CEL environment features planned to be added in future releases",
   817  			input: schema.Structural{
   818  				Generic: schema.Generic{
   819  					Type: "object",
   820  				},
   821  				Extensions: schema.Extensions{
   822  					XValidations: apiextensions.ValidationRules{
   823  						{Rule: "fakeFunction('abc') == 'ABC'"},
   824  					},
   825  				},
   826  			},
   827  			unmodified: true,
   828  			expectedResults: []validationMatcher{
   829  				noError(),
   830  			},
   831  		},
   832  		{
   833  			name: "modified expressions may not use CEL environment features planned to be added in future releases",
   834  			input: schema.Structural{
   835  				Generic: schema.Generic{
   836  					Type: "object",
   837  				},
   838  				Extensions: schema.Extensions{
   839  					XValidations: apiextensions.ValidationRules{
   840  						{Rule: "fakeFunction('abc') == 'ABC'"},
   841  					},
   842  				},
   843  			},
   844  			unmodified: false,
   845  			expectedResults: []validationMatcher{
   846  				invalidError("undeclared reference to 'fakeFunction'"),
   847  			},
   848  		},
   849  	}
   850  
   851  	for _, tt := range cases {
   852  		t.Run(tt.name, func(t *testing.T) {
   853  			env, err := environment.MustBaseEnvSet(environment.DefaultCompatibilityVersion()).Extend(
   854  				environment.VersionedOptions{
   855  					IntroducedVersion: version.MajorMinor(1, 999),
   856  					EnvOptions:        []celgo.EnvOption{celgo.Lib(&fakeLib{})},
   857  				})
   858  			if err != nil {
   859  				t.Fatal(err)
   860  			}
   861  			loader := NewExpressionsEnvLoader()
   862  			if tt.unmodified {
   863  				loader = StoredExpressionsEnvLoader()
   864  			}
   865  			compilationResults, err := Compile(&tt.input, model.SchemaDeclType(&tt.input, false), celconfig.PerCallLimit, env, loader)
   866  			if err != nil {
   867  				t.Fatalf("Expected no error, but got: %v", err)
   868  			}
   869  
   870  			if len(compilationResults) != len(tt.input.XValidations) {
   871  				t.Fatalf("compilation did not produce one result per rule")
   872  			}
   873  
   874  			if len(compilationResults) != len(tt.expectedResults) {
   875  				t.Fatalf("one test expectation per rule is required")
   876  			}
   877  
   878  			for i, expectedResult := range tt.expectedResults {
   879  				if !expectedResult.matches(compilationResults[i]) {
   880  					t.Errorf("result %d does not match expectation: %v", i+1, expectedResult)
   881  				}
   882  			}
   883  		})
   884  	}
   885  }
   886  
   887  // take a single rule type in (string/number/map/etc.) and return appropriate values for
   888  // Type, Format, and XIntOrString
   889  func parseRuleType(ruleType string) (string, string, bool) {
   890  	if ruleType == "duration" || ruleType == "date" || ruleType == "date-time" {
   891  		return "string", ruleType, false
   892  	}
   893  	if ruleType == "int-or-string" {
   894  		return "", "", true
   895  	}
   896  	return ruleType, "", false
   897  }
   898  
   899  func genArrayWithRule(arrayType, rule string) func(maxItems *int64) *schema.Structural {
   900  	passedType, passedFormat, xIntString := parseRuleType(arrayType)
   901  	return func(maxItems *int64) *schema.Structural {
   902  		return &schema.Structural{
   903  			Generic: schema.Generic{
   904  				Type: "array",
   905  			},
   906  			Items: &schema.Structural{
   907  				Generic: schema.Generic{
   908  					Type: passedType,
   909  				},
   910  				ValueValidation: &schema.ValueValidation{
   911  					Format: passedFormat,
   912  				},
   913  				Extensions: schema.Extensions{
   914  					XIntOrString: xIntString,
   915  				},
   916  			},
   917  			ValueValidation: &schema.ValueValidation{
   918  				MaxItems: maxItems,
   919  			},
   920  			Extensions: schema.Extensions{
   921  				XValidations: apiextensions.ValidationRules{
   922  					{
   923  						Rule: rule,
   924  					},
   925  				},
   926  			},
   927  		}
   928  	}
   929  }
   930  
   931  func genArrayOfArraysWithRule(arrayType, rule string) func(maxItems *int64) *schema.Structural {
   932  	return func(maxItems *int64) *schema.Structural {
   933  		return &schema.Structural{
   934  			Generic: schema.Generic{
   935  				Type: "array",
   936  			},
   937  			Items: &schema.Structural{
   938  				Generic: schema.Generic{
   939  					Type: "array",
   940  				},
   941  				Items: &schema.Structural{
   942  					Generic: schema.Generic{
   943  						Type: arrayType,
   944  					},
   945  				},
   946  			},
   947  			ValueValidation: &schema.ValueValidation{
   948  				MaxItems: maxItems,
   949  			},
   950  			Extensions: schema.Extensions{
   951  				XValidations: apiextensions.ValidationRules{
   952  					{
   953  						Rule: rule,
   954  					},
   955  				},
   956  			},
   957  		}
   958  	}
   959  }
   960  
   961  func genObjectArrayWithRule(rule string) func(maxItems *int64) *schema.Structural {
   962  	return func(maxItems *int64) *schema.Structural {
   963  		return &schema.Structural{
   964  			Generic: schema.Generic{
   965  				Type: "array",
   966  			},
   967  			Items: &schema.Structural{
   968  				Generic: schema.Generic{
   969  					Type: "object",
   970  				},
   971  				Properties: map[string]schema.Structural{
   972  					"required": {
   973  						Generic: schema.Generic{
   974  							Type: "string",
   975  						},
   976  					},
   977  					"optional": {
   978  						Generic: schema.Generic{
   979  							Type: "string",
   980  						},
   981  					},
   982  				},
   983  				ValueValidation: &schema.ValueValidation{
   984  					Required: []string{"required"},
   985  				},
   986  			},
   987  			ValueValidation: &schema.ValueValidation{
   988  				MaxItems: maxItems,
   989  			},
   990  			Extensions: schema.Extensions{
   991  				XValidations: apiextensions.ValidationRules{
   992  					{
   993  						Rule: rule,
   994  					},
   995  				},
   996  			},
   997  		}
   998  	}
   999  }
  1000  
  1001  func getMapArrayWithRule(mapType, rule string) func(maxItems *int64) *schema.Structural {
  1002  	return func(maxItems *int64) *schema.Structural {
  1003  		return &schema.Structural{
  1004  			Generic: schema.Generic{
  1005  				Type: "array",
  1006  			},
  1007  			Items: &schema.Structural{
  1008  				Generic: schema.Generic{
  1009  					Type: "object",
  1010  					AdditionalProperties: &schema.StructuralOrBool{Structural: &schema.Structural{
  1011  						Generic: schema.Generic{
  1012  							Type: mapType,
  1013  						},
  1014  					}},
  1015  				},
  1016  			},
  1017  			ValueValidation: &schema.ValueValidation{
  1018  				MaxItems: maxItems,
  1019  			},
  1020  			Extensions: schema.Extensions{
  1021  				XValidations: apiextensions.ValidationRules{
  1022  					{
  1023  						Rule: rule,
  1024  					},
  1025  				},
  1026  			},
  1027  		}
  1028  	}
  1029  }
  1030  
  1031  func genMapWithRule(mapType, rule string) func(maxProperties *int64) *schema.Structural {
  1032  	passedType, passedFormat, xIntString := parseRuleType(mapType)
  1033  	return func(maxProperties *int64) *schema.Structural {
  1034  		return &schema.Structural{
  1035  			Generic: schema.Generic{
  1036  				Type: "object",
  1037  				AdditionalProperties: &schema.StructuralOrBool{Structural: &schema.Structural{
  1038  					Generic: schema.Generic{
  1039  						Type: passedType,
  1040  					},
  1041  					ValueValidation: &schema.ValueValidation{
  1042  						Format: passedFormat,
  1043  					},
  1044  					Extensions: schema.Extensions{
  1045  						XIntOrString: xIntString,
  1046  					},
  1047  				}},
  1048  			},
  1049  			ValueValidation: &schema.ValueValidation{
  1050  				MaxProperties: maxProperties,
  1051  			},
  1052  			Extensions: schema.Extensions{
  1053  				XValidations: apiextensions.ValidationRules{
  1054  					{
  1055  						Rule: rule,
  1056  					},
  1057  				},
  1058  			},
  1059  		}
  1060  	}
  1061  }
  1062  
  1063  func genStringWithRule(rule string) func(maxLength *int64) *schema.Structural {
  1064  	return func(maxLength *int64) *schema.Structural {
  1065  		return &schema.Structural{
  1066  			Generic: schema.Generic{
  1067  				Type: "string",
  1068  			},
  1069  			ValueValidation: &schema.ValueValidation{
  1070  				MaxLength: maxLength,
  1071  			},
  1072  			Extensions: schema.Extensions{
  1073  				XValidations: apiextensions.ValidationRules{
  1074  					{
  1075  						Rule: rule,
  1076  					},
  1077  				},
  1078  			},
  1079  		}
  1080  	}
  1081  }
  1082  
  1083  // genEnumWithRuleAndValues creates a function that accepts an optional maxLength
  1084  // with given validation rule and a set of enum values, following the convention of existing tests.
  1085  // The test has two checks, first with maxLength unset to check if maxLength can be concluded from enums,
  1086  // second with maxLength set to ensure it takes precedence.
  1087  func genEnumWithRuleAndValues(rule string, values ...string) func(maxLength *int64) *schema.Structural {
  1088  	enums := make([]schema.JSON, 0, len(values))
  1089  	for _, v := range values {
  1090  		enums = append(enums, schema.JSON{Object: v})
  1091  	}
  1092  	return func(maxLength *int64) *schema.Structural {
  1093  		return &schema.Structural{
  1094  			Generic: schema.Generic{
  1095  				Type: "string",
  1096  			},
  1097  			ValueValidation: &schema.ValueValidation{
  1098  				MaxLength: maxLength,
  1099  				Enum:      enums,
  1100  			},
  1101  			Extensions: schema.Extensions{
  1102  				XValidations: apiextensions.ValidationRules{
  1103  					{
  1104  						Rule: rule,
  1105  					},
  1106  				},
  1107  			},
  1108  		}
  1109  	}
  1110  }
  1111  
  1112  func genBytesWithRule(rule string) func(maxLength *int64) *schema.Structural {
  1113  	return func(maxLength *int64) *schema.Structural {
  1114  		return &schema.Structural{
  1115  			Generic: schema.Generic{
  1116  				Type: "string",
  1117  			},
  1118  			ValueValidation: &schema.ValueValidation{
  1119  				MaxLength: maxLength,
  1120  				Format:    "byte",
  1121  			},
  1122  			Extensions: schema.Extensions{
  1123  				XValidations: apiextensions.ValidationRules{
  1124  					{
  1125  						Rule: rule,
  1126  					},
  1127  				},
  1128  			},
  1129  		}
  1130  	}
  1131  }
  1132  
  1133  func genNestedSpecWithRule(rule string) func(maxLength *int64) *schema.Structural {
  1134  	return func(maxLength *int64) *schema.Structural {
  1135  		return &schema.Structural{
  1136  			Generic: schema.Generic{
  1137  				Type: "object",
  1138  				AdditionalProperties: &schema.StructuralOrBool{Structural: &schema.Structural{
  1139  					Generic: schema.Generic{
  1140  						Type: "string",
  1141  					},
  1142  					ValueValidation: &schema.ValueValidation{
  1143  						MaxLength: maxLength,
  1144  					},
  1145  				}},
  1146  			},
  1147  			ValueValidation: &schema.ValueValidation{
  1148  				MaxProperties: maxLength,
  1149  			},
  1150  			Extensions: schema.Extensions{
  1151  				XValidations: apiextensions.ValidationRules{
  1152  					{
  1153  						Rule: rule,
  1154  					},
  1155  				},
  1156  			},
  1157  		}
  1158  	}
  1159  }
  1160  
  1161  func genAllMaxNestedSpecWithRootRule(rule string) func(maxLength *int64) *schema.Structural {
  1162  	return func(maxLength *int64) *schema.Structural {
  1163  		return &schema.Structural{
  1164  			Generic: schema.Generic{
  1165  				Type: "array",
  1166  			},
  1167  			Items: &schema.Structural{
  1168  				Generic: schema.Generic{
  1169  					Type: "object",
  1170  					AdditionalProperties: &schema.StructuralOrBool{Structural: &schema.Structural{
  1171  						Generic: schema.Generic{
  1172  							Type: "object",
  1173  						},
  1174  						ValueValidation: &schema.ValueValidation{
  1175  							Required:      []string{"required"},
  1176  							MaxProperties: maxLength,
  1177  						},
  1178  						Properties: map[string]schema.Structural{
  1179  							"required": {
  1180  								Generic: schema.Generic{
  1181  									Type: "string",
  1182  								},
  1183  							},
  1184  							"optional": {
  1185  								Generic: schema.Generic{
  1186  									Type: "string",
  1187  								},
  1188  							},
  1189  						},
  1190  					}},
  1191  				},
  1192  				ValueValidation: &schema.ValueValidation{
  1193  					MaxProperties: maxLength,
  1194  				},
  1195  			},
  1196  			ValueValidation: &schema.ValueValidation{
  1197  				MaxItems: maxLength,
  1198  			},
  1199  			Extensions: schema.Extensions{
  1200  				XValidations: apiextensions.ValidationRules{
  1201  					{
  1202  						Rule: rule,
  1203  					},
  1204  				},
  1205  			},
  1206  		}
  1207  	}
  1208  }
  1209  
  1210  func genOneMaxNestedSpecWithRootRule(rule string) func(maxLength *int64) *schema.Structural {
  1211  	return func(maxLength *int64) *schema.Structural {
  1212  		return &schema.Structural{
  1213  			Generic: schema.Generic{
  1214  				Type: "array",
  1215  			},
  1216  			Items: &schema.Structural{
  1217  				Generic: schema.Generic{
  1218  					Type: "object",
  1219  					AdditionalProperties: &schema.StructuralOrBool{Structural: &schema.Structural{
  1220  						Generic: schema.Generic{
  1221  							Type: "object",
  1222  						},
  1223  						ValueValidation: &schema.ValueValidation{
  1224  							Required: []string{"required"},
  1225  						},
  1226  						Properties: map[string]schema.Structural{
  1227  							"required": {
  1228  								Generic: schema.Generic{
  1229  									Type: "string",
  1230  								},
  1231  							},
  1232  							"optional": {
  1233  								Generic: schema.Generic{
  1234  									Type: "string",
  1235  								},
  1236  							},
  1237  						},
  1238  					}},
  1239  				},
  1240  				ValueValidation: &schema.ValueValidation{
  1241  					MaxProperties: maxLength,
  1242  				},
  1243  			},
  1244  			Extensions: schema.Extensions{
  1245  				XValidations: apiextensions.ValidationRules{
  1246  					{
  1247  						Rule: rule,
  1248  					},
  1249  				},
  1250  			},
  1251  		}
  1252  	}
  1253  }
  1254  
  1255  func genObjectForMap() *schema.Structural {
  1256  	return &schema.Structural{
  1257  		Generic: schema.Generic{
  1258  			Type: "object",
  1259  		},
  1260  		Properties: map[string]schema.Structural{
  1261  			"required": {
  1262  				Generic: schema.Generic{
  1263  					Type: "string",
  1264  				},
  1265  			},
  1266  			"optional": {
  1267  				Generic: schema.Generic{
  1268  					Type: "string",
  1269  				},
  1270  			},
  1271  		},
  1272  		ValueValidation: &schema.ValueValidation{
  1273  			Required: []string{"required"},
  1274  		},
  1275  	}
  1276  }
  1277  
  1278  func genArrayForMap() *schema.Structural {
  1279  	return &schema.Structural{
  1280  		Generic: schema.Generic{
  1281  			Type: "array",
  1282  		},
  1283  		Items: &schema.Structural{
  1284  			Generic: schema.Generic{
  1285  				Type: "number",
  1286  			},
  1287  		},
  1288  	}
  1289  }
  1290  
  1291  func genMapForMap() *schema.Structural {
  1292  	return &schema.Structural{
  1293  		Generic: schema.Generic{
  1294  			Type: "object",
  1295  			AdditionalProperties: &schema.StructuralOrBool{Structural: &schema.Structural{
  1296  				Generic: schema.Generic{
  1297  					Type: "number",
  1298  				},
  1299  			}},
  1300  		},
  1301  	}
  1302  }
  1303  
  1304  func genMapWithCustomItemRule(item *schema.Structural, rule string) func(maxProperties *int64) *schema.Structural {
  1305  	return func(maxProperties *int64) *schema.Structural {
  1306  		return &schema.Structural{
  1307  			Generic: schema.Generic{
  1308  				Type:                 "object",
  1309  				AdditionalProperties: &schema.StructuralOrBool{Structural: item},
  1310  			},
  1311  			ValueValidation: &schema.ValueValidation{
  1312  				MaxProperties: maxProperties,
  1313  			},
  1314  			Extensions: schema.Extensions{
  1315  				XValidations: apiextensions.ValidationRules{
  1316  					{
  1317  						Rule: rule,
  1318  					},
  1319  				},
  1320  			},
  1321  		}
  1322  	}
  1323  }
  1324  
  1325  // schemaChecker checks the cost of the validation rule declared in the provided schema (it requires there be exactly one rule)
  1326  // and checks that the resulting equals the expectedCost if expectedCost is non-zero, and that the resulting cost is >= expectedCostExceedsLimit
  1327  // if expectedCostExceedsLimit is non-zero. Typically, only expectedCost or expectedCostExceedsLimit is non-zero, not both.
  1328  func schemaChecker(schema *schema.Structural, expectedCost uint64, expectedCostExceedsLimit uint64, t *testing.T) func(t *testing.T) {
  1329  	return func(t *testing.T) {
  1330  		compilationResults, err := Compile(schema, model.SchemaDeclType(schema, false), celconfig.PerCallLimit, environment.MustBaseEnvSet(environment.DefaultCompatibilityVersion()), NewExpressionsEnvLoader())
  1331  		if err != nil {
  1332  			t.Fatalf("Expected no error, got: %v", err)
  1333  		}
  1334  		if len(compilationResults) != 1 {
  1335  			t.Fatalf("Expected one rule, got: %d", len(compilationResults))
  1336  		}
  1337  		result := compilationResults[0]
  1338  		if result.Error != nil {
  1339  			t.Errorf("Expected no compile-time error, got: %v", result.Error)
  1340  		}
  1341  		if expectedCost > 0 {
  1342  			if result.MaxCost != expectedCost {
  1343  				t.Errorf("Wrong cost (expected %d, got %d)", expectedCost, result.MaxCost)
  1344  			}
  1345  		}
  1346  		if expectedCostExceedsLimit > 0 {
  1347  			if result.MaxCost < expectedCostExceedsLimit {
  1348  				t.Errorf("Cost did not exceed limit as expected (expected more than %d, got %d)", expectedCostExceedsLimit, result.MaxCost)
  1349  			}
  1350  		}
  1351  	}
  1352  }
  1353  
  1354  func TestCostEstimation(t *testing.T) {
  1355  	cases := []struct {
  1356  		name            string
  1357  		schemaGenerator func(maxLength *int64) *schema.Structural
  1358  		setMaxElements  int64
  1359  
  1360  		// calc costs expectations are checked against the generated schema without any max element limits set
  1361  		expectedCalcCost           uint64
  1362  		expectCalcCostExceedsLimit uint64
  1363  
  1364  		// calc costs expectations are checked against the generated schema with max element limits set
  1365  		expectedSetCost             uint64
  1366  		expectedSetCostExceedsLimit uint64
  1367  	}{
  1368  		{
  1369  			name:             "number array with all",
  1370  			schemaGenerator:  genArrayWithRule("number", "self.all(x, true)"),
  1371  			expectedCalcCost: 4718591,
  1372  			setMaxElements:   10,
  1373  			expectedSetCost:  32,
  1374  		},
  1375  		{
  1376  			name:             "string array with all",
  1377  			schemaGenerator:  genArrayWithRule("string", "self.all(x, true)"),
  1378  			expectedCalcCost: 3145727,
  1379  			setMaxElements:   20,
  1380  			expectedSetCost:  62,
  1381  		},
  1382  		{
  1383  			name:             "boolean array with all",
  1384  			schemaGenerator:  genArrayWithRule("boolean", "self.all(x, true)"),
  1385  			expectedCalcCost: 1887437,
  1386  			setMaxElements:   5,
  1387  			expectedSetCost:  17,
  1388  		},
  1389  		// all array-of-array tests should have the same expected cost along the same expression,
  1390  		// since arrays-of-arrays are serialized the same in minimized form regardless of item type
  1391  		// of the subarray ([[], [], ...])
  1392  		{
  1393  			name:             "array of number arrays with all",
  1394  			schemaGenerator:  genArrayOfArraysWithRule("number", "self.all(x, true)"),
  1395  			expectedCalcCost: 3145727,
  1396  			setMaxElements:   100,
  1397  			expectedSetCost:  302,
  1398  		},
  1399  		{
  1400  			name:             "array of objects with all",
  1401  			schemaGenerator:  genObjectArrayWithRule("self.all(x, true)"),
  1402  			expectedCalcCost: 555128,
  1403  			setMaxElements:   50,
  1404  			expectedSetCost:  152,
  1405  		},
  1406  		{
  1407  			name:             "map of numbers with all",
  1408  			schemaGenerator:  genMapWithRule("number", "self.all(x, true)"),
  1409  			expectedCalcCost: 1348169,
  1410  			setMaxElements:   10,
  1411  			expectedSetCost:  32,
  1412  		},
  1413  		{
  1414  			name:             "map of numbers with has",
  1415  			schemaGenerator:  genMapWithRule("number", "has(self.x)"),
  1416  			expectedCalcCost: 0,
  1417  			setMaxElements:   100,
  1418  			expectedSetCost:  0,
  1419  		},
  1420  		{
  1421  			name:             "map of strings with all",
  1422  			schemaGenerator:  genMapWithRule("string", "self.all(x, true)"),
  1423  			expectedCalcCost: 1179647,
  1424  			setMaxElements:   3,
  1425  			expectedSetCost:  11,
  1426  		},
  1427  		{
  1428  			name:             "map of strings with has",
  1429  			schemaGenerator:  genMapWithRule("string", "has(self.x)"),
  1430  			expectedCalcCost: 0,
  1431  			setMaxElements:   550,
  1432  			expectedSetCost:  0,
  1433  		},
  1434  		{
  1435  			name:             "map of booleans with all",
  1436  			schemaGenerator:  genMapWithRule("boolean", "self.all(x, true)"),
  1437  			expectedCalcCost: 943718,
  1438  			setMaxElements:   100,
  1439  			expectedSetCost:  302,
  1440  		},
  1441  		{
  1442  			name:             "map of booleans with has",
  1443  			schemaGenerator:  genMapWithRule("boolean", "has(self.x)"),
  1444  			expectedCalcCost: 0,
  1445  			setMaxElements:   1024,
  1446  			expectedSetCost:  0,
  1447  		},
  1448  		{
  1449  			name:             "string with contains",
  1450  			schemaGenerator:  genStringWithRule("self.contains('test')"),
  1451  			expectedCalcCost: 314574,
  1452  			setMaxElements:   10,
  1453  			expectedSetCost:  5,
  1454  		},
  1455  		{
  1456  			name:             "string with startsWith",
  1457  			schemaGenerator:  genStringWithRule("self.startsWith('test')"),
  1458  			expectedCalcCost: 2,
  1459  			setMaxElements:   15,
  1460  			expectedSetCost:  2,
  1461  		},
  1462  		{
  1463  			name:             "string with endsWith",
  1464  			schemaGenerator:  genStringWithRule("self.endsWith('test')"),
  1465  			expectedCalcCost: 2,
  1466  			setMaxElements:   30,
  1467  			expectedSetCost:  2,
  1468  		},
  1469  		{
  1470  			name:             "concat string",
  1471  			schemaGenerator:  genStringWithRule(`size(self + "hello") > size("hello")`),
  1472  			expectedCalcCost: 314578,
  1473  			setMaxElements:   4,
  1474  			expectedSetCost:  7,
  1475  		},
  1476  		{
  1477  			name:             "index of array with numbers",
  1478  			schemaGenerator:  genArrayWithRule("number", "self[1] == 0.0"),
  1479  			expectedCalcCost: 2,
  1480  			setMaxElements:   5000,
  1481  			expectedSetCost:  2,
  1482  		},
  1483  		{
  1484  			name:             "index of array with strings",
  1485  			schemaGenerator:  genArrayWithRule("string", "self[1] == self[1]"),
  1486  			expectedCalcCost: 314577,
  1487  			setMaxElements:   8,
  1488  			expectedSetCost:  314577,
  1489  		},
  1490  		{
  1491  			name:                       "O(n^2) loop with numbers",
  1492  			schemaGenerator:            genArrayWithRule("number", "self.all(x, self.all(y, true))"),
  1493  			expectCalcCostExceedsLimit: costLimit,
  1494  			setMaxElements:             10,
  1495  			expectedSetCost:            352,
  1496  		},
  1497  		{
  1498  			name:                       "O(n^3) loop with numbers",
  1499  			schemaGenerator:            genArrayWithRule("number", "self.all(x, self.all(y, self.all(z, true)))"),
  1500  			expectCalcCostExceedsLimit: costLimit,
  1501  			setMaxElements:             10,
  1502  			expectedSetCost:            3552,
  1503  		},
  1504  		{
  1505  			name:             "regex matches simple",
  1506  			schemaGenerator:  genStringWithRule(`self.matches("x")`),
  1507  			expectedCalcCost: 314574,
  1508  			setMaxElements:   50,
  1509  			expectedSetCost:  22,
  1510  		},
  1511  		{
  1512  			name:             "regex matches empty string",
  1513  			schemaGenerator:  genStringWithRule(`"".matches("(((((((((())))))))))[0-9]")`),
  1514  			expectedCalcCost: 7,
  1515  			setMaxElements:   10,
  1516  			expectedSetCost:  7,
  1517  		},
  1518  		{
  1519  			name:             "regex matches empty regex",
  1520  			schemaGenerator:  genStringWithRule(`self.matches("")`),
  1521  			expectedCalcCost: 1,
  1522  			setMaxElements:   100,
  1523  			expectedSetCost:  1,
  1524  		},
  1525  		{
  1526  			name:             "map of strings with value length",
  1527  			schemaGenerator:  genNestedSpecWithRule("self.all(x, x.contains(self[x]))"),
  1528  			expectedCalcCost: 2752507,
  1529  			setMaxElements:   10,
  1530  			expectedSetCost:  72,
  1531  		},
  1532  		{
  1533  			name:             "set array maxLength to zero",
  1534  			schemaGenerator:  genArrayWithRule("number", "self[3] == 0.0"),
  1535  			expectedCalcCost: 2,
  1536  			setMaxElements:   0,
  1537  			expectedSetCost:  2,
  1538  		},
  1539  		{
  1540  			name:             "set map maxLength to zero",
  1541  			schemaGenerator:  genMapWithRule("number", `self["x"] == 0.0`),
  1542  			expectedCalcCost: 2,
  1543  			setMaxElements:   0,
  1544  			expectedSetCost:  2,
  1545  		},
  1546  		{
  1547  			name:             "set string maxLength to zero",
  1548  			schemaGenerator:  genStringWithRule(`self == "x"`),
  1549  			expectedCalcCost: 2,
  1550  			setMaxElements:   0,
  1551  			expectedSetCost:  1,
  1552  		},
  1553  		{
  1554  			name:             "set bytes maxLength to zero",
  1555  			schemaGenerator:  genBytesWithRule(`self == b"x"`),
  1556  			expectedCalcCost: 2,
  1557  			setMaxElements:   0,
  1558  			expectedSetCost:  1,
  1559  		},
  1560  		{
  1561  			name:             "set maxLength greater than estimated maxLength",
  1562  			schemaGenerator:  genArrayWithRule("number", "self.all(x, x == 0.0)"),
  1563  			expectedCalcCost: 6291454,
  1564  			setMaxElements:   3 * 1024 * 2048,
  1565  			expectedSetCost:  25165826,
  1566  		},
  1567  		{
  1568  			name:             "nested types with root rule with all supporting maxLength",
  1569  			schemaGenerator:  genAllMaxNestedSpecWithRootRule(`self.all(x, x["y"].required == "z")`),
  1570  			expectedCalcCost: 7340027,
  1571  			setMaxElements:   10,
  1572  			expectedSetCost:  72,
  1573  		},
  1574  		{
  1575  			name:             "nested types with root rule with one supporting maxLength",
  1576  			schemaGenerator:  genOneMaxNestedSpecWithRootRule(`self.all(x, x["y"].required == "z")`),
  1577  			expectedCalcCost: 7340027,
  1578  			setMaxElements:   10,
  1579  			expectedSetCost:  7340027,
  1580  		},
  1581  		{
  1582  			name:             "int-or-string array with all",
  1583  			schemaGenerator:  genArrayWithRule("int-or-string", "self.all(x, true)"),
  1584  			expectedCalcCost: 4718591,
  1585  			setMaxElements:   10,
  1586  			expectedSetCost:  32,
  1587  		},
  1588  		{
  1589  			name:             "index of array with int-or-strings",
  1590  			schemaGenerator:  genArrayWithRule("int-or-string", "self[0] == 5"),
  1591  			expectedCalcCost: 3,
  1592  			setMaxElements:   10,
  1593  			expectedSetCost:  3,
  1594  		},
  1595  		{
  1596  			name:             "index of array with booleans",
  1597  			schemaGenerator:  genArrayWithRule("boolean", "self[0] == false"),
  1598  			expectedCalcCost: 2,
  1599  			setMaxElements:   25,
  1600  			expectedSetCost:  2,
  1601  		},
  1602  		{
  1603  			name:             "index of array of objects",
  1604  			schemaGenerator:  genObjectArrayWithRule("self[0] == null"),
  1605  			expectedCalcCost: 2,
  1606  			setMaxElements:   422,
  1607  			expectedSetCost:  2,
  1608  		},
  1609  		{
  1610  			name:             "index of array of array of numnbers",
  1611  			schemaGenerator:  genArrayOfArraysWithRule("number", "self[0][0] == -1.0"),
  1612  			expectedCalcCost: 3,
  1613  			setMaxElements:   51,
  1614  			expectedSetCost:  3,
  1615  		},
  1616  		{
  1617  			name:             "array of number maps with all",
  1618  			schemaGenerator:  getMapArrayWithRule("number", `self.all(x, x.y == 25.2)`),
  1619  			expectedCalcCost: 6291452,
  1620  			setMaxElements:   12,
  1621  			expectedSetCost:  74,
  1622  		},
  1623  		{
  1624  			name:             "index of array of number maps",
  1625  			schemaGenerator:  getMapArrayWithRule("number", `self[0].x > 2.0`),
  1626  			expectedCalcCost: 4,
  1627  			setMaxElements:   3000,
  1628  			expectedSetCost:  4,
  1629  		},
  1630  		{
  1631  			name:             "duration array with all",
  1632  			schemaGenerator:  genArrayWithRule("duration", "self.all(x, true)"),
  1633  			expectedCalcCost: 2359295,
  1634  			setMaxElements:   5,
  1635  			expectedSetCost:  17,
  1636  		},
  1637  		{
  1638  			name:             "index of duration array",
  1639  			schemaGenerator:  genArrayWithRule("duration", "self[0].getHours() == 2"),
  1640  			expectedCalcCost: 4,
  1641  			setMaxElements:   525,
  1642  			expectedSetCost:  4,
  1643  		},
  1644  		{
  1645  			name:             "date array with all",
  1646  			schemaGenerator:  genArrayWithRule("date", "self.all(x, true)"),
  1647  			expectedCalcCost: 725936,
  1648  			setMaxElements:   15,
  1649  			expectedSetCost:  47,
  1650  		},
  1651  		{
  1652  			name:             "index of date array",
  1653  			schemaGenerator:  genArrayWithRule("date", "self[2].getDayOfMonth() == 13"),
  1654  			expectedCalcCost: 4,
  1655  			setMaxElements:   42,
  1656  			expectedSetCost:  4,
  1657  		},
  1658  		{
  1659  			name:             "date-time array with all",
  1660  			schemaGenerator:  genArrayWithRule("date-time", "self.all(x, true)"),
  1661  			expectedCalcCost: 428963,
  1662  			setMaxElements:   25,
  1663  			expectedSetCost:  77,
  1664  		},
  1665  		{
  1666  			name:             "index of date-time array",
  1667  			schemaGenerator:  genArrayWithRule("date-time", "self[2].getMinutes() == 45"),
  1668  			expectedCalcCost: 4,
  1669  			setMaxElements:   99,
  1670  			expectedSetCost:  4,
  1671  		},
  1672  		{
  1673  			name:             "map of int-or-strings with all",
  1674  			schemaGenerator:  genMapWithRule("int-or-string", "self.all(x, true)"),
  1675  			expectedCalcCost: 1348169,
  1676  			setMaxElements:   15,
  1677  			expectedSetCost:  47,
  1678  		},
  1679  		{
  1680  			name:             "map of int-or-strings with has",
  1681  			schemaGenerator:  genMapWithRule("int-or-string", "has(self.x)"),
  1682  			expectedCalcCost: 0,
  1683  			setMaxElements:   5000,
  1684  			expectedSetCost:  0,
  1685  		},
  1686  		{
  1687  			name:             "map of objects with all",
  1688  			schemaGenerator:  genMapWithCustomItemRule(genObjectForMap(), "self.all(x, true)"),
  1689  			expectedCalcCost: 428963,
  1690  			setMaxElements:   20,
  1691  			expectedSetCost:  62,
  1692  		},
  1693  		{
  1694  			name:             "map of objects with has",
  1695  			schemaGenerator:  genMapWithCustomItemRule(genObjectForMap(), "has(self.x)"),
  1696  			expectedCalcCost: 0,
  1697  			setMaxElements:   9001,
  1698  			expectedSetCost:  0,
  1699  		},
  1700  		{
  1701  			name:             "map of number maps with all",
  1702  			schemaGenerator:  genMapWithCustomItemRule(genMapForMap(), "self.all(x, true)"),
  1703  			expectedCalcCost: 1179647,
  1704  			setMaxElements:   10,
  1705  			expectedSetCost:  32,
  1706  		},
  1707  		{
  1708  			name:             "map of number maps with has",
  1709  			schemaGenerator:  genMapWithCustomItemRule(genMapForMap(), "has(self.x)"),
  1710  			expectedCalcCost: 0,
  1711  			setMaxElements:   101,
  1712  			expectedSetCost:  0,
  1713  		},
  1714  		{
  1715  			name:             "map of number arrays with all",
  1716  			schemaGenerator:  genMapWithCustomItemRule(genArrayForMap(), "self.all(x, true)"),
  1717  			expectedCalcCost: 1179647,
  1718  			setMaxElements:   25,
  1719  			expectedSetCost:  77,
  1720  		},
  1721  		{
  1722  			name:             "map of number arrays with has",
  1723  			schemaGenerator:  genMapWithCustomItemRule(genArrayForMap(), "has(self.x)"),
  1724  			expectedCalcCost: 0,
  1725  			setMaxElements:   40000,
  1726  			expectedSetCost:  0,
  1727  		},
  1728  		{
  1729  			name:             "map of durations with all",
  1730  			schemaGenerator:  genMapWithRule("duration", "self.all(x, true)"),
  1731  			expectedCalcCost: 1048577,
  1732  			setMaxElements:   5,
  1733  			expectedSetCost:  17,
  1734  		},
  1735  		{
  1736  			name:             "map of durations with has",
  1737  			schemaGenerator:  genMapWithRule("duration", "has(self.x)"),
  1738  			expectedCalcCost: 0,
  1739  			setMaxElements:   256,
  1740  			expectedSetCost:  0,
  1741  		},
  1742  		{
  1743  			name:             "map of dates with all",
  1744  			schemaGenerator:  genMapWithRule("date", "self.all(x, true)"),
  1745  			expectedCalcCost: 524288,
  1746  			setMaxElements:   10,
  1747  			expectedSetCost:  32,
  1748  		},
  1749  		{
  1750  			name:             "map of dates with has",
  1751  			schemaGenerator:  genMapWithRule("date", "has(self.x)"),
  1752  			expectedCalcCost: 0,
  1753  			setMaxElements:   65536,
  1754  			expectedSetCost:  0,
  1755  		},
  1756  		{
  1757  			name:             "map of date-times with all",
  1758  			schemaGenerator:  genMapWithRule("date-time", "self.all(x, true)"),
  1759  			expectedCalcCost: 349526,
  1760  			setMaxElements:   25,
  1761  			expectedSetCost:  77,
  1762  		},
  1763  		{
  1764  			name:             "map of date-times with has",
  1765  			schemaGenerator:  genMapWithRule("date-time", "has(self.x)"),
  1766  			expectedCalcCost: 0,
  1767  			setMaxElements:   490,
  1768  			expectedSetCost:  0,
  1769  		},
  1770  		// Ensure library functions are integrated with size estimates by testing the interesting cases.
  1771  		{
  1772  			name:             "extended library regex find",
  1773  			schemaGenerator:  genStringWithRule("self.find('[0-9]+') == ''"),
  1774  			expectedCalcCost: 629147,
  1775  			setMaxElements:   10,
  1776  			expectedSetCost:  11,
  1777  		},
  1778  		{
  1779  			name: "extended library join",
  1780  			schemaGenerator: func(max *int64) *schema.Structural {
  1781  				strType := withMaxLength(primitiveType("string", ""), max)
  1782  				array := withMaxItems(arrayType("atomic", nil, &strType), max)
  1783  				array = withRule(array, "self.join(' ') == 'aa bb'")
  1784  				return &array
  1785  			},
  1786  			expectedCalcCost: 329853068905,
  1787  			setMaxElements:   10,
  1788  			expectedSetCost:  43,
  1789  		},
  1790  		{
  1791  			name: "extended library isSorted",
  1792  			schemaGenerator: func(max *int64) *schema.Structural {
  1793  				strType := withMaxLength(primitiveType("string", ""), max)
  1794  				array := withMaxItems(arrayType("atomic", nil, &strType), max)
  1795  				array = withRule(array, "self.isSorted() == true")
  1796  				return &array
  1797  			},
  1798  			expectedCalcCost: 329854432052,
  1799  			setMaxElements:   10,
  1800  			expectedSetCost:  52,
  1801  		},
  1802  		{
  1803  			name: "extended library replace",
  1804  			schemaGenerator: func(max *int64) *schema.Structural {
  1805  				strType := withMaxLength(primitiveType("string", ""), max)
  1806  				beforeLen := int64(2)
  1807  				afterLen := int64(4)
  1808  				objType := objectType(map[string]schema.Structural{
  1809  					"str":    strType,
  1810  					"before": withMaxLength(primitiveType("string", ""), &beforeLen),
  1811  					"after":  withMaxLength(primitiveType("string", ""), &afterLen),
  1812  				})
  1813  				objType = withRule(objType, "self.str.replace(self.before, self.after) == 'does not matter'")
  1814  				return &objType
  1815  			},
  1816  			expectedCalcCost: 629154, // cost is based on the result size of the replace() call
  1817  			setMaxElements:   4,
  1818  			expectedSetCost:  12,
  1819  		},
  1820  		{
  1821  			name: "extended library split",
  1822  			schemaGenerator: func(max *int64) *schema.Structural {
  1823  				strType := withMaxLength(primitiveType("string", ""), max)
  1824  				objType := objectType(map[string]schema.Structural{
  1825  					"str":       strType,
  1826  					"separator": strType,
  1827  				})
  1828  				objType = withRule(objType, "self.str.split(self.separator) == []")
  1829  				return &objType
  1830  			},
  1831  			expectedCalcCost: 629160,
  1832  			setMaxElements:   10,
  1833  			expectedSetCost:  22,
  1834  		},
  1835  		{
  1836  			name: "extended library lowerAscii",
  1837  			schemaGenerator: func(max *int64) *schema.Structural {
  1838  				strType := withMaxLength(primitiveType("string", ""), max)
  1839  				strType = withRule(strType, "self.lowerAscii() == 'lower!'")
  1840  				return &strType
  1841  			},
  1842  			expectedCalcCost: 314575,
  1843  			setMaxElements:   10,
  1844  			expectedSetCost:  6,
  1845  		},
  1846  		{
  1847  			name:             "check cost of size call",
  1848  			schemaGenerator:  genMapWithRule("integer", "oldSelf.size() == self.size()"),
  1849  			expectedCalcCost: 5,
  1850  			setMaxElements:   10,
  1851  			expectedSetCost:  5,
  1852  		},
  1853  		{
  1854  			name:             "check cost of timestamp comparison",
  1855  			schemaGenerator:  genMapWithRule("date-time", `self["a"] == self["b"]`),
  1856  			expectedCalcCost: 8,
  1857  			setMaxElements:   7,
  1858  			expectedSetCost:  8,
  1859  		},
  1860  		{
  1861  			name:             "check cost of duration comparison",
  1862  			schemaGenerator:  genMapWithRule("duration", `self["c"] == self["d"]`),
  1863  			expectedCalcCost: 8,
  1864  			setMaxElements:   42,
  1865  			expectedSetCost:  8,
  1866  		},
  1867  		{
  1868  			name:             "enums with maxLength equals to the longest possible value",
  1869  			schemaGenerator:  genEnumWithRuleAndValues("self.contains('A')", "A", "B", "C", "LongValue"),
  1870  			expectedCalcCost: 2,
  1871  			setMaxElements:   1000,
  1872  			expectedSetCost:  401,
  1873  		},
  1874  	}
  1875  	for _, testCase := range cases {
  1876  		t.Run(testCase.name, func(t *testing.T) {
  1877  			// dynamic maxLength case
  1878  			schema := testCase.schemaGenerator(nil)
  1879  			t.Run("calc maxLength", schemaChecker(schema, testCase.expectedCalcCost, testCase.expectCalcCostExceedsLimit, t))
  1880  			// static maxLength case
  1881  			setSchema := testCase.schemaGenerator(&testCase.setMaxElements)
  1882  			t.Run("set maxLength", schemaChecker(setSchema, testCase.expectedSetCost, testCase.expectedSetCostExceedsLimit, t))
  1883  		})
  1884  	}
  1885  }
  1886  
  1887  func BenchmarkCompile(b *testing.B) {
  1888  	env := environment.MustBaseEnvSet(environment.DefaultCompatibilityVersion()) // prepare the environment
  1889  	s := genArrayWithRule("number", "true")(nil)
  1890  	b.ReportAllocs()
  1891  	b.ResetTimer()
  1892  	for i := 0; i < b.N; i++ {
  1893  		_, err := Compile(s, model.SchemaDeclType(s, false), math.MaxInt64, env, NewExpressionsEnvLoader())
  1894  		if err != nil {
  1895  			b.Fatal(err)
  1896  		}
  1897  	}
  1898  }
  1899  
  1900  type fakeLib struct{}
  1901  
  1902  var testLibraryDecls = map[string][]celgo.FunctionOpt{
  1903  	"fakeFunction": {
  1904  		celgo.Overload("fakeFunction", []*celgo.Type{celgo.StringType}, celgo.StringType,
  1905  			celgo.UnaryBinding(fakeFunction))},
  1906  }
  1907  
  1908  func (*fakeLib) CompileOptions() []celgo.EnvOption {
  1909  	options := make([]celgo.EnvOption, 0, len(testLibraryDecls))
  1910  	for name, overloads := range testLibraryDecls {
  1911  		options = append(options, celgo.Function(name, overloads...))
  1912  	}
  1913  	return options
  1914  }
  1915  
  1916  func (*fakeLib) ProgramOptions() []celgo.ProgramOption {
  1917  	return []celgo.ProgramOption{}
  1918  }
  1919  
  1920  func fakeFunction(arg1 ref.Val) ref.Val {
  1921  	arg, ok := arg1.Value().(string)
  1922  	if !ok {
  1923  		return types.MaybeNoSuchOverloadErr(arg1)
  1924  	}
  1925  
  1926  	return types.String(strings.ToUpper(arg))
  1927  }
  1928  

View as plain text