1// Copyright 2018 Google LLC 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package types 16 17import ( 18 "fmt" 19 "reflect" 20 21 "github.com/golang/protobuf/proto" 22 "github.com/golang/protobuf/ptypes" 23 24 "github.com/google/cel-go/common/types/ref" 25 "github.com/google/cel-go/common/types/traits" 26 27 structpb "github.com/golang/protobuf/ptypes/struct" 28) 29 30var ( 31 // ListType singleton. 32 ListType = NewTypeValue("list", 33 traits.AdderType, 34 traits.ContainerType, 35 traits.IndexerType, 36 traits.IterableType, 37 traits.SizerType) 38) 39 40// NewDynamicList returns a traits.Lister with heterogenous elements. 41// value should be an array of "native" types, i.e. any type that 42// NativeToValue() can convert to a ref.Val. 43func NewDynamicList(adapter ref.TypeAdapter, value interface{}) traits.Lister { 44 return &baseList{ 45 TypeAdapter: adapter, 46 value: value, 47 refValue: reflect.ValueOf(value)} 48} 49 50// NewStringList returns a traits.Lister containing only strings. 51func NewStringList(adapter ref.TypeAdapter, elems []string) traits.Lister { 52 return &stringList{ 53 baseList: NewDynamicList(adapter, elems).(*baseList), 54 elems: elems} 55} 56 57// NewValueList returns a traits.Lister with ref.Val elements. 58func NewValueList(adapter ref.TypeAdapter, elems []ref.Val) traits.Lister { 59 return &valueList{ 60 baseList: NewDynamicList(adapter, elems).(*baseList), 61 elems: elems} 62} 63 64// baseList points to a list containing elements of any type. 65// The `value` is an array of native values, and refValue is its reflection object. 66// The `ref.TypeAdapter` enables native type to CEL type conversions. 67type baseList struct { 68 ref.TypeAdapter 69 value interface{} 70 refValue reflect.Value 71} 72 73// Add implements the traits.Adder interface method. 74func (l *baseList) Add(other ref.Val) ref.Val { 75 otherList, ok := other.(traits.Lister) 76 if !ok { 77 return ValOrErr(other, "no such overload") 78 } 79 if l.Size() == IntZero { 80 return other 81 } 82 if otherList.Size() == IntZero { 83 return l 84 } 85 return &concatList{ 86 TypeAdapter: l.TypeAdapter, 87 prevList: l, 88 nextList: otherList} 89} 90 91// Contains implements the traits.Container interface method. 92func (l *baseList) Contains(elem ref.Val) ref.Val { 93 if IsUnknownOrError(elem) { 94 return elem 95 } 96 var err ref.Val 97 sz := l.Size().(Int) 98 for i := Int(0); i < sz; i++ { 99 val := l.Get(i) 100 cmp := elem.Equal(val) 101 b, ok := cmp.(Bool) 102 // When there is an error on the contain check, this is not necessarily terminal. 103 // The contains call could find the element and return True, just as though the user 104 // had written a per-element comparison in an exists() macro or logical ||, e.g. 105 // list.exists(e, e == elem) 106 if !ok && err == nil { 107 err = ValOrErr(cmp, "no such overload") 108 } 109 if b == True { 110 return True 111 } 112 } 113 if err != nil { 114 return err 115 } 116 return False 117} 118 119// ConvertToNative implements the ref.Val interface method. 120func (l *baseList) ConvertToNative(typeDesc reflect.Type) (interface{}, error) { 121 // TODO: Add support for conversion to Any 122 // JSON conversions are a special case since the 'native' type is a proto message. 123 switch typeDesc { 124 case anyValueType: 125 json, err := l.ConvertToNative(jsonListValueType) 126 if err != nil { 127 return nil, err 128 } 129 return ptypes.MarshalAny(json.(proto.Message)) 130 case jsonValueType, jsonListValueType: 131 jsonValues, err := 132 l.ConvertToNative(reflect.TypeOf([]*structpb.Value{})) 133 if err != nil { 134 return nil, err 135 } 136 jsonList := &structpb.ListValue{Values: jsonValues.([]*structpb.Value)} 137 if typeDesc == jsonListValueType { 138 return jsonList, nil 139 } 140 return &structpb.Value{Kind: &structpb.Value_ListValue{ListValue: jsonList}}, nil 141 } 142 143 // Non-list conversion. 144 if typeDesc.Kind() != reflect.Slice && typeDesc.Kind() != reflect.Array { 145 return nil, fmt.Errorf("type conversion error from list to '%v'", typeDesc) 146 } 147 148 // If the list is already assignable to the desired type return it. 149 if reflect.TypeOf(l).AssignableTo(typeDesc) { 150 return l, nil 151 } 152 153 // List conversion. 154 thisType := l.refValue.Type() 155 thisElem := thisType.Elem() 156 thisElemKind := thisElem.Kind() 157 158 otherElem := typeDesc.Elem() 159 otherElemKind := otherElem.Kind() 160 if otherElemKind == thisElemKind { 161 return l.value, nil 162 } 163 // Allow the element ConvertToNative() function to determine whether conversion is possible. 164 elemCount := int(l.Size().(Int)) 165 nativeList := reflect.MakeSlice(typeDesc, elemCount, elemCount) 166 for i := 0; i < elemCount; i++ { 167 elem := l.Get(Int(i)) 168 nativeElemVal, err := elem.ConvertToNative(otherElem) 169 if err != nil { 170 return nil, err 171 } 172 nativeList.Index(i).Set(reflect.ValueOf(nativeElemVal)) 173 } 174 return nativeList.Interface(), nil 175} 176 177// ConvertToType implements the ref.Val interface method. 178func (l *baseList) ConvertToType(typeVal ref.Type) ref.Val { 179 switch typeVal { 180 case ListType: 181 return l 182 case TypeType: 183 return ListType 184 } 185 return NewErr("type conversion error from '%s' to '%s'", ListType, typeVal) 186} 187 188// Equal implements the ref.Val interface method. 189func (l *baseList) Equal(other ref.Val) ref.Val { 190 otherList, ok := other.(traits.Lister) 191 if !ok { 192 return ValOrErr(other, "no such overload") 193 } 194 if l.Size() != otherList.Size() { 195 return False 196 } 197 for i := IntZero; i < l.Size().(Int); i++ { 198 thisElem := l.Get(i) 199 otherElem := otherList.Get(i) 200 elemEq := thisElem.Equal(otherElem) 201 if elemEq != True { 202 return elemEq 203 } 204 } 205 return True 206} 207 208// Get implements the traits.Indexer interface method. 209func (l *baseList) Get(index ref.Val) ref.Val { 210 i, ok := index.(Int) 211 if !ok { 212 return ValOrErr(index, "unsupported index type '%s' in list", index.Type()) 213 } 214 if i < 0 || i >= l.Size().(Int) { 215 return NewErr("index '%d' out of range in list size '%d'", i, l.Size()) 216 } 217 elem := l.refValue.Index(int(i)).Interface() 218 return l.NativeToValue(elem) 219} 220 221// Iterator implements the traits.Iterable interface method. 222func (l *baseList) Iterator() traits.Iterator { 223 return &listIterator{ 224 baseIterator: &baseIterator{}, 225 listValue: l, 226 cursor: 0, 227 len: l.Size().(Int)} 228} 229 230// Size implements the traits.Sizer interface method. 231func (l *baseList) Size() ref.Val { 232 return Int(l.refValue.Len()) 233} 234 235// Type implements the ref.Val interface method. 236func (l *baseList) Type() ref.Type { 237 return ListType 238} 239 240// Value implements the ref.Val interface method. 241func (l *baseList) Value() interface{} { 242 return l.value 243} 244 245// concatList combines two list implementations together into a view. 246// The `ref.TypeAdapter` enables native type to CEL type conversions. 247type concatList struct { 248 ref.TypeAdapter 249 value interface{} 250 prevList traits.Lister 251 nextList traits.Lister 252} 253 254// Add implements the traits.Adder interface method. 255func (l *concatList) Add(other ref.Val) ref.Val { 256 otherList, ok := other.(traits.Lister) 257 if !ok { 258 return ValOrErr(other, "no such overload") 259 } 260 if l.Size() == IntZero { 261 return other 262 } 263 if otherList.Size() == IntZero { 264 return l 265 } 266 return &concatList{ 267 TypeAdapter: l.TypeAdapter, 268 prevList: l, 269 nextList: otherList} 270} 271 272// Contains implments the traits.Container interface method. 273func (l *concatList) Contains(elem ref.Val) ref.Val { 274 // The concat list relies on the IsErrorOrUnknown checks against the input element to be 275 // performed by the `prevList` and/or `nextList`. 276 prev := l.prevList.Contains(elem) 277 // Short-circuit the return if the elem was found in the prev list. 278 if prev == True { 279 return prev 280 } 281 // Return if the elem was found in the next list. 282 next := l.nextList.Contains(elem) 283 if next == True { 284 return next 285 } 286 // Handle the case where an error or unknown was encountered before checking next. 287 if IsUnknownOrError(prev) { 288 return prev 289 } 290 // Otherwise, rely on the next value as the representative result. 291 return next 292} 293 294// ConvertToNative implements the ref.Val interface method. 295func (l *concatList) ConvertToNative(typeDesc reflect.Type) (interface{}, error) { 296 combined := &baseList{ 297 TypeAdapter: l.TypeAdapter, 298 value: l.Value(), 299 refValue: reflect.ValueOf(l.Value())} 300 return combined.ConvertToNative(typeDesc) 301} 302 303// ConvertToType implements the ref.Val interface method. 304func (l *concatList) ConvertToType(typeVal ref.Type) ref.Val { 305 switch typeVal { 306 case ListType: 307 return l 308 case TypeType: 309 return ListType 310 } 311 return NewErr("type conversion error from '%s' to '%s'", ListType, typeVal) 312} 313 314// Equal implements the ref.Val interface method. 315func (l *concatList) Equal(other ref.Val) ref.Val { 316 otherList, ok := other.(traits.Lister) 317 if !ok { 318 return ValOrErr(other, "no such overload") 319 } 320 if l.Size() != otherList.Size() { 321 return False 322 } 323 for i := IntZero; i < l.Size().(Int); i++ { 324 thisElem := l.Get(i) 325 otherElem := otherList.Get(i) 326 elemEq := thisElem.Equal(otherElem) 327 if elemEq != True { 328 return elemEq 329 } 330 } 331 return True 332} 333 334// Get implements the traits.Indexer interface method. 335func (l *concatList) Get(index ref.Val) ref.Val { 336 i, ok := index.(Int) 337 if !ok { 338 return ValOrErr(index, "no such overload") 339 } 340 if i < l.prevList.Size().(Int) { 341 return l.prevList.Get(i) 342 } 343 offset := i - l.prevList.Size().(Int) 344 return l.nextList.Get(offset) 345} 346 347// Iterator implements the traits.Iterable interface method. 348func (l *concatList) Iterator() traits.Iterator { 349 return &listIterator{ 350 baseIterator: &baseIterator{}, 351 listValue: l, 352 cursor: 0, 353 len: l.Size().(Int)} 354} 355 356// Size implements the traits.Sizer interface method. 357func (l *concatList) Size() ref.Val { 358 return l.prevList.Size().(Int).Add(l.nextList.Size()) 359} 360 361// Type implements the ref.Val interface method. 362func (l *concatList) Type() ref.Type { 363 return ListType 364} 365 366// Value implements the ref.Val interface method. 367func (l *concatList) Value() interface{} { 368 if l.value == nil { 369 merged := make([]interface{}, l.Size().(Int), l.Size().(Int)) 370 prevLen := l.prevList.Size().(Int) 371 for i := Int(0); i < prevLen; i++ { 372 merged[i] = l.prevList.Get(i).Value() 373 } 374 nextLen := l.nextList.Size().(Int) 375 for j := Int(0); j < nextLen; j++ { 376 merged[prevLen+j] = l.nextList.Get(j).Value() 377 } 378 l.value = merged 379 } 380 return l.value 381} 382 383// stringList is a specialization of the traits.Lister interface which is 384// present to demonstrate the ability to specialize Lister implementations. 385type stringList struct { 386 *baseList 387 elems []string 388} 389 390// Add implments the traits.Adder interface method. 391func (l *stringList) Add(other ref.Val) ref.Val { 392 if other.Type() != ListType { 393 return ValOrErr(other, "no such overload") 394 } 395 if l.Size() == IntZero { 396 return other 397 } 398 if other.(traits.Sizer).Size() == IntZero { 399 return l 400 } 401 switch other.(type) { 402 case *stringList: 403 concatElems := append(l.elems, other.(*stringList).elems...) 404 return NewStringList(l.TypeAdapter, concatElems) 405 } 406 return &concatList{ 407 TypeAdapter: l.TypeAdapter, 408 prevList: l.baseList, 409 nextList: other.(traits.Lister)} 410} 411 412// ConvertToNative implements the ref.Val interface method. 413func (l *stringList) ConvertToNative(typeDesc reflect.Type) (interface{}, error) { 414 switch typeDesc.Kind() { 415 case reflect.Array, reflect.Slice: 416 if typeDesc.Elem().Kind() == reflect.String { 417 return l.elems, nil 418 } 419 if typeDesc.Elem().Kind() == reflect.Interface { 420 iface := make([]interface{}, len(l.elems), len(l.elems)) 421 for i, str := range l.elems { 422 iface[i] = str 423 } 424 return iface, nil 425 } 426 case reflect.Ptr: 427 switch typeDesc { 428 case anyValueType: 429 json, err := l.ConvertToNative(jsonListValueType) 430 if err != nil { 431 return nil, err 432 } 433 return ptypes.MarshalAny(json.(proto.Message)) 434 case jsonValueType, jsonListValueType: 435 elemCount := len(l.elems) 436 listVals := make([]*structpb.Value, elemCount, elemCount) 437 for i := 0; i < elemCount; i++ { 438 listVals[i] = &structpb.Value{ 439 Kind: &structpb.Value_StringValue{StringValue: l.elems[i]}} 440 } 441 jsonList := &structpb.ListValue{Values: listVals} 442 if typeDesc == jsonListValueType { 443 return jsonList, nil 444 } 445 return &structpb.Value{ 446 Kind: &structpb.Value_ListValue{ 447 ListValue: jsonList}}, nil 448 } 449 } 450 // If the list is already assignable to the desired type return it. 451 if reflect.TypeOf(l).AssignableTo(typeDesc) { 452 return l, nil 453 } 454 return nil, fmt.Errorf("no conversion found from list type to native type."+ 455 " list elem: string, native type: %v", typeDesc) 456} 457 458// Get implements the traits.Indexer interface method. 459func (l *stringList) Get(index ref.Val) ref.Val { 460 i, ok := index.(Int) 461 if !ok { 462 return ValOrErr(index, "no such overload") 463 } 464 if i < 0 || i >= l.Size().(Int) { 465 return NewErr("index '%d' out of range in list size '%d'", i, l.Size()) 466 } 467 return String(l.elems[i]) 468} 469 470// Size implements the traits.Sizer interface method. 471func (l *stringList) Size() ref.Val { 472 return Int(len(l.elems)) 473} 474 475// valueList is a specialization of traits.Lister for ref.Val. 476type valueList struct { 477 *baseList 478 elems []ref.Val 479} 480 481// Add implements the traits.Adder interface method. 482func (l *valueList) Add(other ref.Val) ref.Val { 483 otherList, ok := other.(traits.Lister) 484 if !ok { 485 return ValOrErr(other, "no such overload") 486 } 487 return &concatList{ 488 TypeAdapter: l.TypeAdapter, 489 prevList: l, 490 nextList: otherList} 491} 492 493// Get implements the traits.Indexer interface method. 494func (l *valueList) Get(index ref.Val) ref.Val { 495 i, ok := index.(Int) 496 if !ok { 497 return ValOrErr(index, "no such overload") 498 } 499 if i < 0 || i >= l.Size().(Int) { 500 return NewErr("index '%d' out of range in list size '%d'", i, l.Size()) 501 } 502 return l.elems[i] 503} 504 505// Size implements the traits.Sizer interface method. 506func (l *valueList) Size() ref.Val { 507 return Int(len(l.elems)) 508} 509 510type listIterator struct { 511 *baseIterator 512 listValue traits.Lister 513 cursor Int 514 len Int 515} 516 517// HasNext implements the traits.Iterator interface method. 518func (it *listIterator) HasNext() ref.Val { 519 return Bool(it.cursor < it.len) 520} 521 522// Next implements the traits.Iterator interface method. 523func (it *listIterator) Next() ref.Val { 524 if it.HasNext() == True { 525 index := it.cursor 526 it.cursor++ 527 return it.listValue.Get(index) 528 } 529 return nil 530} 531