Debian Codegraph @

pkg/cel/common/maplist.go

raw
1 /*
2 Copyright 2022 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 common
18
19 import (
20 "fmt"
21 "strings"
22 )
23
24 // MapList provides a "lookup by key" operation for lists (arrays) with x-kubernetes-list-type=map.
25 type MapList interface {
26 // Get returns the first element having given key, for all
27 // x-kubernetes-list-map-keys, to the provided object. If the provided object isn't itself a valid MapList element,
28 // get returns nil.
29 Get(interface{}) interface{}
30 }
31
32 type keyStrategy interface {
33 // CompositeKeyFor returns a composite key for the provided object, if possible, and a
34 // boolean that indicates whether or not a key could be generated for the provided object.
35 CompositeKeyFor(map[string]interface{}) (interface{}, bool)
36 }
37
38 // singleKeyStrategy is a cheaper strategy for associative lists that have exactly one key.
39 type singleKeyStrategy struct {
40 key string
41 }
42
43 // CompositeKeyFor directly returns the value of the single key to
44 // use as a composite key.
45 func (ks *singleKeyStrategy) CompositeKeyFor(obj map[string]interface{}) (interface{}, bool) {
46 v, ok := obj[ks.key]
47 if !ok {
48 return nil, false
49 }
50
51 switch v.(type) {
52 case bool, float64, int64, string:
53 return v, true
54 default:
55 return nil, false // non-scalar
56 }
57 }
58
59 // multiKeyStrategy computes a composite key of all key values.
60 type multiKeyStrategy struct {
61 sts Schema
62 }
63
64 // CompositeKeyFor returns a composite key computed from the values of all
65 // keys.
66 func (ks *multiKeyStrategy) CompositeKeyFor(obj map[string]interface{}) (interface{}, bool) {
67 const keyDelimiter = "\x00" // 0 byte should never appear in the composite key except as delimiter
68
69 var delimited strings.Builder
70 for _, key := range ks.sts.XListMapKeys() {
71 v, ok := obj[key]
72 if !ok {
73 return nil, false
74 }
75
76 switch v.(type) {
77 case bool:
78 fmt.Fprintf(&delimited, keyDelimiter+"%t", v)
79 case float64:
80 fmt.Fprintf(&delimited, keyDelimiter+"%f", v)
81 case int64:
82 fmt.Fprintf(&delimited, keyDelimiter+"%d", v)
83 case string:
84 fmt.Fprintf(&delimited, keyDelimiter+"%q", v)
85 default:
86 return nil, false // values must be scalars
87 }
88 }
89 return delimited.String(), true
90 }
91
92 // emptyMapList is a MapList containing no elements.
93 type emptyMapList struct{}
94
95 func (emptyMapList) Get(interface{}) interface{} {
96 return nil
97 }
98
99 type mapListImpl struct {
100 sts Schema
101 ks keyStrategy
102 // keyedItems contains all lazily keyed map items
103 keyedItems map[interface{}]interface{}
104 // unkeyedItems contains all map items that have not yet been keyed
105 unkeyedItems []interface{}
106 }
107
108 func (a *mapListImpl) Get(obj interface{}) interface{} {
109 mobj, ok := obj.(map[string]interface{})
110 if !ok {
111 return nil
112 }
113
114 key, ok := a.ks.CompositeKeyFor(mobj)
115 if !ok {
116 return nil
117 }
118 if match, ok := a.keyedItems[key]; ok {
119 return match
120 }
121 // keep keying items until we either find a match or run out of unkeyed items
122 for len(a.unkeyedItems) > 0 {
123 // dequeue an unkeyed item
124 item := a.unkeyedItems[0]
125 a.unkeyedItems = a.unkeyedItems[1:]
126
127 // key the item
128 mitem, ok := item.(map[string]interface{})
129 if !ok {
130 continue
131 }
132 itemKey, ok := a.ks.CompositeKeyFor(mitem)
133 if !ok {
134 continue
135 }
136 if _, exists := a.keyedItems[itemKey]; !exists {
137 a.keyedItems[itemKey] = mitem
138 }
139
140 // if it matches, short-circuit
141 if itemKey == key {
142 return mitem
143 }
144 }
145
146 return nil
147 }
148
149 func makeKeyStrategy(sts Schema) keyStrategy {
150 listMapKeys := sts.XListMapKeys()
151 if len(listMapKeys) == 1 {
152 key := listMapKeys[0]
153 return &singleKeyStrategy{
154 key: key,
155 }
156 }
157
158 return &multiKeyStrategy{
159 sts: sts,
160 }
161 }
162
163 // MakeMapList returns a queryable interface over the provided x-kubernetes-list-type=map
164 // keyedItems. If the provided schema is _not_ an array with x-kubernetes-list-type=map, returns an
165 // empty mapList.
166 func MakeMapList(sts Schema, items []interface{}) (rv MapList) {
167 if sts.Type() != "array" || sts.XListType() != "map" || len(sts.XListMapKeys()) == 0 || len(items) == 0 {
168 return emptyMapList{}
169 }
170 ks := makeKeyStrategy(sts)
171 return &mapListImpl{
172 sts: sts,
173 ks: ks,
174 keyedItems: map[interface{}]interface{}{},
175 unkeyedItems: items,
176 }
177 }