1/* 2Copyright 2018 The Kubernetes Authors. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15*/ 16 17package fieldpath 18 19import ( 20 "sort" 21 "strings" 22) 23 24// Set identifies a set of fields. 25type Set struct { 26 // Members lists fields that are part of the set. 27 // TODO: will be serialized as a list of path elements. 28 Members PathElementSet 29 30 // Children lists child fields which themselves have children that are 31 // members of the set. Appearance in this list does not imply membership. 32 // Note: this is a tree, not an arbitrary graph. 33 Children SetNodeMap 34} 35 36// NewSet makes a set from a list of paths. 37func NewSet(paths ...Path) *Set { 38 s := &Set{} 39 for _, p := range paths { 40 s.Insert(p) 41 } 42 return s 43} 44 45// Insert adds the field identified by `p` to the set. Important: parent fields 46// are NOT added to the set; if that is desired, they must be added separately. 47func (s *Set) Insert(p Path) { 48 if len(p) == 0 { 49 // Zero-length path identifies the entire object; we don't 50 // track top-level ownership. 51 return 52 } 53 for { 54 if len(p) == 1 { 55 s.Members.Insert(p[0]) 56 return 57 } 58 s = s.Children.Descend(p[0]) 59 p = p[1:] 60 } 61} 62 63// Union returns a Set containing elements which appear in either s or s2. 64func (s *Set) Union(s2 *Set) *Set { 65 return &Set{ 66 Members: *s.Members.Union(&s2.Members), 67 Children: *s.Children.Union(&s2.Children), 68 } 69} 70 71// Intersection returns a Set containing leaf elements which appear in both s 72// and s2. Intersection can be constructed from Union and Difference operations 73// (example in the tests) but it's much faster to do it in one pass. 74func (s *Set) Intersection(s2 *Set) *Set { 75 return &Set{ 76 Members: *s.Members.Intersection(&s2.Members), 77 Children: *s.Children.Intersection(&s2.Children), 78 } 79} 80 81// Difference returns a Set containing elements which: 82// * appear in s 83// * do not appear in s2 84// 85// In other words, for leaf fields, this acts like a regular set difference 86// operation. When non leaf fields are compared with leaf fields ("parents" 87// which contain "children"), the effect is: 88// * parent - child = parent 89// * child - parent = {empty set} 90func (s *Set) Difference(s2 *Set) *Set { 91 return &Set{ 92 Members: *s.Members.Difference(&s2.Members), 93 Children: *s.Children.Difference(s2), 94 } 95} 96 97// Size returns the number of members of the set. 98func (s *Set) Size() int { 99 return s.Members.Size() + s.Children.Size() 100} 101 102// Empty returns true if there are no members of the set. It is a separate 103// function from Size since it's common to check whether size > 0, and 104// potentially much faster to return as soon as a single element is found. 105func (s *Set) Empty() bool { 106 if s.Members.Size() > 0 { 107 return false 108 } 109 return s.Children.Empty() 110} 111 112// Has returns true if the field referenced by `p` is a member of the set. 113func (s *Set) Has(p Path) bool { 114 if len(p) == 0 { 115 // No one owns "the entire object" 116 return false 117 } 118 for { 119 if len(p) == 1 { 120 return s.Members.Has(p[0]) 121 } 122 var ok bool 123 s, ok = s.Children.Get(p[0]) 124 if !ok { 125 return false 126 } 127 p = p[1:] 128 } 129} 130 131// Equals returns true if s and s2 have exactly the same members. 132func (s *Set) Equals(s2 *Set) bool { 133 return s.Members.Equals(&s2.Members) && s.Children.Equals(&s2.Children) 134} 135 136// String returns the set one element per line. 137func (s *Set) String() string { 138 elements := []string{} 139 s.Iterate(func(p Path) { 140 elements = append(elements, p.String()) 141 }) 142 return strings.Join(elements, "\n") 143} 144 145// Iterate calls f once for each field that is a member of the set (preorder 146// DFS). The path passed to f will be reused so make a copy if you wish to keep 147// it. 148func (s *Set) Iterate(f func(Path)) { 149 s.iteratePrefix(Path{}, f) 150} 151 152func (s *Set) iteratePrefix(prefix Path, f func(Path)) { 153 s.Members.Iterate(func(pe PathElement) { f(append(prefix, pe)) }) 154 s.Children.iteratePrefix(prefix, f) 155} 156 157// WithPrefix returns the subset of paths which begin with the given prefix, 158// with the prefix not included. 159func (s *Set) WithPrefix(pe PathElement) *Set { 160 subset, ok := s.Children.Get(pe) 161 if !ok { 162 return NewSet() 163 } 164 return subset 165} 166 167// setNode is a pair of PathElement / Set, for the purpose of expressing 168// nested set membership. 169type setNode struct { 170 pathElement PathElement 171 set *Set 172} 173 174// SetNodeMap is a map of PathElement to subset. 175type SetNodeMap struct { 176 members sortedSetNode 177} 178 179type sortedSetNode []setNode 180 181// Implement the sort interface; this would permit bulk creation, which would 182// be faster than doing it one at a time via Insert. 183func (s sortedSetNode) Len() int { return len(s) } 184func (s sortedSetNode) Less(i, j int) bool { return s[i].pathElement.Less(s[j].pathElement) } 185func (s sortedSetNode) Swap(i, j int) { s[i], s[j] = s[j], s[i] } 186 187// Descend adds pe to the set if necessary, returning the associated subset. 188func (s *SetNodeMap) Descend(pe PathElement) *Set { 189 loc := sort.Search(len(s.members), func(i int) bool { 190 return !s.members[i].pathElement.Less(pe) 191 }) 192 if loc == len(s.members) { 193 s.members = append(s.members, setNode{pathElement: pe, set: &Set{}}) 194 return s.members[loc].set 195 } 196 if s.members[loc].pathElement.Equals(pe) { 197 return s.members[loc].set 198 } 199 s.members = append(s.members, setNode{}) 200 copy(s.members[loc+1:], s.members[loc:]) 201 s.members[loc] = setNode{pathElement: pe, set: &Set{}} 202 return s.members[loc].set 203} 204 205// Size returns the sum of the number of members of all subsets. 206func (s *SetNodeMap) Size() int { 207 count := 0 208 for _, v := range s.members { 209 count += v.set.Size() 210 } 211 return count 212} 213 214// Empty returns false if there's at least one member in some child set. 215func (s *SetNodeMap) Empty() bool { 216 for _, n := range s.members { 217 if !n.set.Empty() { 218 return false 219 } 220 } 221 return true 222} 223 224// Get returns (the associated set, true) or (nil, false) if there is none. 225func (s *SetNodeMap) Get(pe PathElement) (*Set, bool) { 226 loc := sort.Search(len(s.members), func(i int) bool { 227 return !s.members[i].pathElement.Less(pe) 228 }) 229 if loc == len(s.members) { 230 return nil, false 231 } 232 if s.members[loc].pathElement.Equals(pe) { 233 return s.members[loc].set, true 234 } 235 return nil, false 236} 237 238// Equals returns true if s and s2 have the same structure (same nested 239// child sets). 240func (s *SetNodeMap) Equals(s2 *SetNodeMap) bool { 241 if len(s.members) != len(s2.members) { 242 return false 243 } 244 for i := range s.members { 245 if !s.members[i].pathElement.Equals(s2.members[i].pathElement) { 246 return false 247 } 248 if !s.members[i].set.Equals(s2.members[i].set) { 249 return false 250 } 251 } 252 return true 253} 254 255// Union returns a SetNodeMap with members that appear in either s or s2. 256func (s *SetNodeMap) Union(s2 *SetNodeMap) *SetNodeMap { 257 out := &SetNodeMap{} 258 259 i, j := 0, 0 260 for i < len(s.members) && j < len(s2.members) { 261 if s.members[i].pathElement.Less(s2.members[j].pathElement) { 262 out.members = append(out.members, s.members[i]) 263 i++ 264 } else { 265 if !s2.members[j].pathElement.Less(s.members[i].pathElement) { 266 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set.Union(s2.members[j].set)}) 267 i++ 268 } else { 269 out.members = append(out.members, s2.members[j]) 270 } 271 j++ 272 } 273 } 274 275 if i < len(s.members) { 276 out.members = append(out.members, s.members[i:]...) 277 } 278 if j < len(s2.members) { 279 out.members = append(out.members, s2.members[j:]...) 280 } 281 return out 282} 283 284// Intersection returns a SetNodeMap with members that appear in both s and s2. 285func (s *SetNodeMap) Intersection(s2 *SetNodeMap) *SetNodeMap { 286 out := &SetNodeMap{} 287 288 i, j := 0, 0 289 for i < len(s.members) && j < len(s2.members) { 290 if s.members[i].pathElement.Less(s2.members[j].pathElement) { 291 i++ 292 } else { 293 if !s2.members[j].pathElement.Less(s.members[i].pathElement) { 294 res := s.members[i].set.Intersection(s2.members[j].set) 295 if !res.Empty() { 296 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: res}) 297 } 298 i++ 299 } 300 j++ 301 } 302 } 303 return out 304} 305 306// Difference returns a SetNodeMap with members that appear in s but not in s2. 307func (s *SetNodeMap) Difference(s2 *Set) *SetNodeMap { 308 out := &SetNodeMap{} 309 310 i, j := 0, 0 311 for i < len(s.members) && j < len(s2.Children.members) { 312 if s.members[i].pathElement.Less(s2.Children.members[j].pathElement) { 313 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set}) 314 i++ 315 } else { 316 if !s2.Children.members[j].pathElement.Less(s.members[i].pathElement) { 317 318 diff := s.members[i].set.Difference(s2.Children.members[j].set) 319 // We aren't permitted to add nodes with no elements. 320 if !diff.Empty() { 321 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: diff}) 322 } 323 324 i++ 325 } 326 j++ 327 } 328 } 329 330 if i < len(s.members) { 331 out.members = append(out.members, s.members[i:]...) 332 } 333 return out 334} 335 336// Iterate calls f for each PathElement in the set. 337func (s *SetNodeMap) Iterate(f func(PathElement)) { 338 for _, n := range s.members { 339 f(n.pathElement) 340 } 341} 342 343func (s *SetNodeMap) iteratePrefix(prefix Path, f func(Path)) { 344 for _, n := range s.members { 345 pe := n.pathElement 346 n.set.iteratePrefix(append(prefix, pe), f) 347 } 348} 349