| 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 |
} |