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// RecursiveDifference returns a Set containing elements which: 98// * appear in s 99// * do not appear in s2 100// 101// Compared to a regular difference, 102// this removes every field **and its children** from s that is contained in s2. 103// 104// For example, with s containing `a.b.c` and s2 containing `a.b`, 105// a RecursiveDifference will result in `a`, as the entire node `a.b` gets removed. 106func (s *Set) RecursiveDifference(s2 *Set) *Set { 107 return &Set{ 108 Members: *s.Members.Difference(&s2.Members), 109 Children: *s.Children.RecursiveDifference(s2), 110 } 111} 112 113// Size returns the number of members of the set. 114func (s *Set) Size() int { 115 return s.Members.Size() + s.Children.Size() 116} 117 118// Empty returns true if there are no members of the set. It is a separate 119// function from Size since it's common to check whether size > 0, and 120// potentially much faster to return as soon as a single element is found. 121func (s *Set) Empty() bool { 122 if s.Members.Size() > 0 { 123 return false 124 } 125 return s.Children.Empty() 126} 127 128// Has returns true if the field referenced by `p` is a member of the set. 129func (s *Set) Has(p Path) bool { 130 if len(p) == 0 { 131 // No one owns "the entire object" 132 return false 133 } 134 for { 135 if len(p) == 1 { 136 return s.Members.Has(p[0]) 137 } 138 var ok bool 139 s, ok = s.Children.Get(p[0]) 140 if !ok { 141 return false 142 } 143 p = p[1:] 144 } 145} 146 147// Equals returns true if s and s2 have exactly the same members. 148func (s *Set) Equals(s2 *Set) bool { 149 return s.Members.Equals(&s2.Members) && s.Children.Equals(&s2.Children) 150} 151 152// String returns the set one element per line. 153func (s *Set) String() string { 154 elements := []string{} 155 s.Iterate(func(p Path) { 156 elements = append(elements, p.String()) 157 }) 158 return strings.Join(elements, "\n") 159} 160 161// Iterate calls f once for each field that is a member of the set (preorder 162// DFS). The path passed to f will be reused so make a copy if you wish to keep 163// it. 164func (s *Set) Iterate(f func(Path)) { 165 s.iteratePrefix(Path{}, f) 166} 167 168func (s *Set) iteratePrefix(prefix Path, f func(Path)) { 169 s.Members.Iterate(func(pe PathElement) { f(append(prefix, pe)) }) 170 s.Children.iteratePrefix(prefix, f) 171} 172 173// WithPrefix returns the subset of paths which begin with the given prefix, 174// with the prefix not included. 175func (s *Set) WithPrefix(pe PathElement) *Set { 176 subset, ok := s.Children.Get(pe) 177 if !ok { 178 return NewSet() 179 } 180 return subset 181} 182 183// setNode is a pair of PathElement / Set, for the purpose of expressing 184// nested set membership. 185type setNode struct { 186 pathElement PathElement 187 set *Set 188} 189 190// SetNodeMap is a map of PathElement to subset. 191type SetNodeMap struct { 192 members sortedSetNode 193} 194 195type sortedSetNode []setNode 196 197// Implement the sort interface; this would permit bulk creation, which would 198// be faster than doing it one at a time via Insert. 199func (s sortedSetNode) Len() int { return len(s) } 200func (s sortedSetNode) Less(i, j int) bool { return s[i].pathElement.Less(s[j].pathElement) } 201func (s sortedSetNode) Swap(i, j int) { s[i], s[j] = s[j], s[i] } 202 203// Descend adds pe to the set if necessary, returning the associated subset. 204func (s *SetNodeMap) Descend(pe PathElement) *Set { 205 loc := sort.Search(len(s.members), func(i int) bool { 206 return !s.members[i].pathElement.Less(pe) 207 }) 208 if loc == len(s.members) { 209 s.members = append(s.members, setNode{pathElement: pe, set: &Set{}}) 210 return s.members[loc].set 211 } 212 if s.members[loc].pathElement.Equals(pe) { 213 return s.members[loc].set 214 } 215 s.members = append(s.members, setNode{}) 216 copy(s.members[loc+1:], s.members[loc:]) 217 s.members[loc] = setNode{pathElement: pe, set: &Set{}} 218 return s.members[loc].set 219} 220 221// Size returns the sum of the number of members of all subsets. 222func (s *SetNodeMap) Size() int { 223 count := 0 224 for _, v := range s.members { 225 count += v.set.Size() 226 } 227 return count 228} 229 230// Empty returns false if there's at least one member in some child set. 231func (s *SetNodeMap) Empty() bool { 232 for _, n := range s.members { 233 if !n.set.Empty() { 234 return false 235 } 236 } 237 return true 238} 239 240// Get returns (the associated set, true) or (nil, false) if there is none. 241func (s *SetNodeMap) Get(pe PathElement) (*Set, bool) { 242 loc := sort.Search(len(s.members), func(i int) bool { 243 return !s.members[i].pathElement.Less(pe) 244 }) 245 if loc == len(s.members) { 246 return nil, false 247 } 248 if s.members[loc].pathElement.Equals(pe) { 249 return s.members[loc].set, true 250 } 251 return nil, false 252} 253 254// Equals returns true if s and s2 have the same structure (same nested 255// child sets). 256func (s *SetNodeMap) Equals(s2 *SetNodeMap) bool { 257 if len(s.members) != len(s2.members) { 258 return false 259 } 260 for i := range s.members { 261 if !s.members[i].pathElement.Equals(s2.members[i].pathElement) { 262 return false 263 } 264 if !s.members[i].set.Equals(s2.members[i].set) { 265 return false 266 } 267 } 268 return true 269} 270 271// Union returns a SetNodeMap with members that appear in either s or s2. 272func (s *SetNodeMap) Union(s2 *SetNodeMap) *SetNodeMap { 273 out := &SetNodeMap{} 274 275 i, j := 0, 0 276 for i < len(s.members) && j < len(s2.members) { 277 if s.members[i].pathElement.Less(s2.members[j].pathElement) { 278 out.members = append(out.members, s.members[i]) 279 i++ 280 } else { 281 if !s2.members[j].pathElement.Less(s.members[i].pathElement) { 282 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set.Union(s2.members[j].set)}) 283 i++ 284 } else { 285 out.members = append(out.members, s2.members[j]) 286 } 287 j++ 288 } 289 } 290 291 if i < len(s.members) { 292 out.members = append(out.members, s.members[i:]...) 293 } 294 if j < len(s2.members) { 295 out.members = append(out.members, s2.members[j:]...) 296 } 297 return out 298} 299 300// Intersection returns a SetNodeMap with members that appear in both s and s2. 301func (s *SetNodeMap) Intersection(s2 *SetNodeMap) *SetNodeMap { 302 out := &SetNodeMap{} 303 304 i, j := 0, 0 305 for i < len(s.members) && j < len(s2.members) { 306 if s.members[i].pathElement.Less(s2.members[j].pathElement) { 307 i++ 308 } else { 309 if !s2.members[j].pathElement.Less(s.members[i].pathElement) { 310 res := s.members[i].set.Intersection(s2.members[j].set) 311 if !res.Empty() { 312 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: res}) 313 } 314 i++ 315 } 316 j++ 317 } 318 } 319 return out 320} 321 322// Difference returns a SetNodeMap with members that appear in s but not in s2. 323func (s *SetNodeMap) Difference(s2 *Set) *SetNodeMap { 324 out := &SetNodeMap{} 325 326 i, j := 0, 0 327 for i < len(s.members) && j < len(s2.Children.members) { 328 if s.members[i].pathElement.Less(s2.Children.members[j].pathElement) { 329 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set}) 330 i++ 331 } else { 332 if !s2.Children.members[j].pathElement.Less(s.members[i].pathElement) { 333 334 diff := s.members[i].set.Difference(s2.Children.members[j].set) 335 // We aren't permitted to add nodes with no elements. 336 if !diff.Empty() { 337 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: diff}) 338 } 339 340 i++ 341 } 342 j++ 343 } 344 } 345 346 if i < len(s.members) { 347 out.members = append(out.members, s.members[i:]...) 348 } 349 return out 350} 351 352// RecursiveDifference returns a SetNodeMap with members that appear in s but not in s2. 353// 354// Compared to a regular difference, 355// this removes every field **and its children** from s that is contained in s2. 356// 357// For example, with s containing `a.b.c` and s2 containing `a.b`, 358// a RecursiveDifference will result in `a`, as the entire node `a.b` gets removed. 359func (s *SetNodeMap) RecursiveDifference(s2 *Set) *SetNodeMap { 360 out := &SetNodeMap{} 361 362 i, j := 0, 0 363 for i < len(s.members) && j < len(s2.Children.members) { 364 if s.members[i].pathElement.Less(s2.Children.members[j].pathElement) { 365 if !s2.Members.Has(s.members[i].pathElement) { 366 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set}) 367 } 368 i++ 369 } else { 370 if !s2.Children.members[j].pathElement.Less(s.members[i].pathElement) { 371 if !s2.Members.Has(s.members[i].pathElement) { 372 diff := s.members[i].set.RecursiveDifference(s2.Children.members[j].set) 373 if !diff.Empty() { 374 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: diff}) 375 } 376 } 377 i++ 378 } 379 j++ 380 } 381 } 382 383 if i < len(s.members) { 384 for _, c := range s.members[i:] { 385 if !s2.Members.Has(c.pathElement) { 386 out.members = append(out.members, c) 387 } 388 } 389 } 390 391 return out 392} 393 394// Iterate calls f for each PathElement in the set. 395func (s *SetNodeMap) Iterate(f func(PathElement)) { 396 for _, n := range s.members { 397 f(n.pathElement) 398 } 399} 400 401func (s *SetNodeMap) iteratePrefix(prefix Path, f func(Path)) { 402 for _, n := range s.members { 403 pe := n.pathElement 404 n.set.iteratePrefix(append(prefix, pe), f) 405 } 406} 407