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 "sigs.k8s.io/structured-merge-diff/v4/schema" 24) 25 26// Set identifies a set of fields. 27type Set struct { 28 // Members lists fields that are part of the set. 29 // TODO: will be serialized as a list of path elements. 30 Members PathElementSet 31 32 // Children lists child fields which themselves have children that are 33 // members of the set. Appearance in this list does not imply membership. 34 // Note: this is a tree, not an arbitrary graph. 35 Children SetNodeMap 36} 37 38// NewSet makes a set from a list of paths. 39func NewSet(paths ...Path) *Set { 40 s := &Set{} 41 for _, p := range paths { 42 s.Insert(p) 43 } 44 return s 45} 46 47// Insert adds the field identified by `p` to the set. Important: parent fields 48// are NOT added to the set; if that is desired, they must be added separately. 49func (s *Set) Insert(p Path) { 50 if len(p) == 0 { 51 // Zero-length path identifies the entire object; we don't 52 // track top-level ownership. 53 return 54 } 55 for { 56 if len(p) == 1 { 57 s.Members.Insert(p[0]) 58 return 59 } 60 s = s.Children.Descend(p[0]) 61 p = p[1:] 62 } 63} 64 65// Union returns a Set containing elements which appear in either s or s2. 66func (s *Set) Union(s2 *Set) *Set { 67 return &Set{ 68 Members: *s.Members.Union(&s2.Members), 69 Children: *s.Children.Union(&s2.Children), 70 } 71} 72 73// Intersection returns a Set containing leaf elements which appear in both s 74// and s2. Intersection can be constructed from Union and Difference operations 75// (example in the tests) but it's much faster to do it in one pass. 76func (s *Set) Intersection(s2 *Set) *Set { 77 return &Set{ 78 Members: *s.Members.Intersection(&s2.Members), 79 Children: *s.Children.Intersection(&s2.Children), 80 } 81} 82 83// Difference returns a Set containing elements which: 84// * appear in s 85// * do not appear in s2 86// 87// In other words, for leaf fields, this acts like a regular set difference 88// operation. When non leaf fields are compared with leaf fields ("parents" 89// which contain "children"), the effect is: 90// * parent - child = parent 91// * child - parent = {empty set} 92func (s *Set) Difference(s2 *Set) *Set { 93 return &Set{ 94 Members: *s.Members.Difference(&s2.Members), 95 Children: *s.Children.Difference(s2), 96 } 97} 98 99// RecursiveDifference returns a Set containing elements which: 100// * appear in s 101// * do not appear in s2 102// 103// Compared to a regular difference, 104// this removes every field **and its children** from s that is contained in s2. 105// 106// For example, with s containing `a.b.c` and s2 containing `a.b`, 107// a RecursiveDifference will result in `a`, as the entire node `a.b` gets removed. 108func (s *Set) RecursiveDifference(s2 *Set) *Set { 109 return &Set{ 110 Members: *s.Members.Difference(&s2.Members), 111 Children: *s.Children.RecursiveDifference(s2), 112 } 113} 114 115// EnsureNamedFieldsAreMembers returns a Set that contains all the 116// fields in s, as well as all the named fields that are typically not 117// included. For example, a set made of "a.b.c" will end-up also owning 118// "a" if it's a named fields but not "a.b" if it's a map. 119func (s *Set) EnsureNamedFieldsAreMembers(sc *schema.Schema, tr schema.TypeRef) *Set { 120 members := PathElementSet{ 121 members: make(sortedPathElements, 0, s.Members.Size()+len(s.Children.members)), 122 } 123 atom, _ := sc.Resolve(tr) 124 members.members = append(members.members, s.Members.members...) 125 for _, node := range s.Children.members { 126 // Only insert named fields. 127 if node.pathElement.FieldName != nil && atom.Map != nil { 128 if _, has := atom.Map.FindField(*node.pathElement.FieldName); has { 129 members.Insert(node.pathElement) 130 } 131 } 132 } 133 return &Set{ 134 Members: members, 135 Children: *s.Children.EnsureNamedFieldsAreMembers(sc, tr), 136 } 137} 138 139// Size returns the number of members of the set. 140func (s *Set) Size() int { 141 return s.Members.Size() + s.Children.Size() 142} 143 144// Empty returns true if there are no members of the set. It is a separate 145// function from Size since it's common to check whether size > 0, and 146// potentially much faster to return as soon as a single element is found. 147func (s *Set) Empty() bool { 148 if s.Members.Size() > 0 { 149 return false 150 } 151 return s.Children.Empty() 152} 153 154// Has returns true if the field referenced by `p` is a member of the set. 155func (s *Set) Has(p Path) bool { 156 if len(p) == 0 { 157 // No one owns "the entire object" 158 return false 159 } 160 for { 161 if len(p) == 1 { 162 return s.Members.Has(p[0]) 163 } 164 var ok bool 165 s, ok = s.Children.Get(p[0]) 166 if !ok { 167 return false 168 } 169 p = p[1:] 170 } 171} 172 173// Equals returns true if s and s2 have exactly the same members. 174func (s *Set) Equals(s2 *Set) bool { 175 return s.Members.Equals(&s2.Members) && s.Children.Equals(&s2.Children) 176} 177 178// String returns the set one element per line. 179func (s *Set) String() string { 180 elements := []string{} 181 s.Iterate(func(p Path) { 182 elements = append(elements, p.String()) 183 }) 184 return strings.Join(elements, "\n") 185} 186 187// Iterate calls f once for each field that is a member of the set (preorder 188// DFS). The path passed to f will be reused so make a copy if you wish to keep 189// it. 190func (s *Set) Iterate(f func(Path)) { 191 s.iteratePrefix(Path{}, f) 192} 193 194func (s *Set) iteratePrefix(prefix Path, f func(Path)) { 195 s.Members.Iterate(func(pe PathElement) { f(append(prefix, pe)) }) 196 s.Children.iteratePrefix(prefix, f) 197} 198 199// WithPrefix returns the subset of paths which begin with the given prefix, 200// with the prefix not included. 201func (s *Set) WithPrefix(pe PathElement) *Set { 202 subset, ok := s.Children.Get(pe) 203 if !ok { 204 return NewSet() 205 } 206 return subset 207} 208 209// Leaves returns a set containing only the leaf paths 210// of a set. 211func (s *Set) Leaves() *Set { 212 leaves := PathElementSet{} 213 im := 0 214 ic := 0 215 216 // any members that are not also children are leaves 217outer: 218 for im < len(s.Members.members) { 219 member := s.Members.members[im] 220 221 for ic < len(s.Children.members) { 222 d := member.Compare(s.Children.members[ic].pathElement) 223 if d == 0 { 224 ic++ 225 im++ 226 continue outer 227 } else if d < 0 { 228 break 229 } else /* if d > 0 */ { 230 ic++ 231 } 232 } 233 leaves.members = append(leaves.members, member) 234 im++ 235 } 236 237 return &Set{ 238 Members: leaves, 239 Children: *s.Children.Leaves(), 240 } 241} 242 243// setNode is a pair of PathElement / Set, for the purpose of expressing 244// nested set membership. 245type setNode struct { 246 pathElement PathElement 247 set *Set 248} 249 250// SetNodeMap is a map of PathElement to subset. 251type SetNodeMap struct { 252 members sortedSetNode 253} 254 255type sortedSetNode []setNode 256 257// Implement the sort interface; this would permit bulk creation, which would 258// be faster than doing it one at a time via Insert. 259func (s sortedSetNode) Len() int { return len(s) } 260func (s sortedSetNode) Less(i, j int) bool { return s[i].pathElement.Less(s[j].pathElement) } 261func (s sortedSetNode) Swap(i, j int) { s[i], s[j] = s[j], s[i] } 262 263// Descend adds pe to the set if necessary, returning the associated subset. 264func (s *SetNodeMap) Descend(pe PathElement) *Set { 265 loc := sort.Search(len(s.members), func(i int) bool { 266 return !s.members[i].pathElement.Less(pe) 267 }) 268 if loc == len(s.members) { 269 s.members = append(s.members, setNode{pathElement: pe, set: &Set{}}) 270 return s.members[loc].set 271 } 272 if s.members[loc].pathElement.Equals(pe) { 273 return s.members[loc].set 274 } 275 s.members = append(s.members, setNode{}) 276 copy(s.members[loc+1:], s.members[loc:]) 277 s.members[loc] = setNode{pathElement: pe, set: &Set{}} 278 return s.members[loc].set 279} 280 281// Size returns the sum of the number of members of all subsets. 282func (s *SetNodeMap) Size() int { 283 count := 0 284 for _, v := range s.members { 285 count += v.set.Size() 286 } 287 return count 288} 289 290// Empty returns false if there's at least one member in some child set. 291func (s *SetNodeMap) Empty() bool { 292 for _, n := range s.members { 293 if !n.set.Empty() { 294 return false 295 } 296 } 297 return true 298} 299 300// Get returns (the associated set, true) or (nil, false) if there is none. 301func (s *SetNodeMap) Get(pe PathElement) (*Set, bool) { 302 loc := sort.Search(len(s.members), func(i int) bool { 303 return !s.members[i].pathElement.Less(pe) 304 }) 305 if loc == len(s.members) { 306 return nil, false 307 } 308 if s.members[loc].pathElement.Equals(pe) { 309 return s.members[loc].set, true 310 } 311 return nil, false 312} 313 314// Equals returns true if s and s2 have the same structure (same nested 315// child sets). 316func (s *SetNodeMap) Equals(s2 *SetNodeMap) bool { 317 if len(s.members) != len(s2.members) { 318 return false 319 } 320 for i := range s.members { 321 if !s.members[i].pathElement.Equals(s2.members[i].pathElement) { 322 return false 323 } 324 if !s.members[i].set.Equals(s2.members[i].set) { 325 return false 326 } 327 } 328 return true 329} 330 331// Union returns a SetNodeMap with members that appear in either s or s2. 332func (s *SetNodeMap) Union(s2 *SetNodeMap) *SetNodeMap { 333 out := &SetNodeMap{} 334 335 i, j := 0, 0 336 for i < len(s.members) && j < len(s2.members) { 337 if s.members[i].pathElement.Less(s2.members[j].pathElement) { 338 out.members = append(out.members, s.members[i]) 339 i++ 340 } else { 341 if !s2.members[j].pathElement.Less(s.members[i].pathElement) { 342 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set.Union(s2.members[j].set)}) 343 i++ 344 } else { 345 out.members = append(out.members, s2.members[j]) 346 } 347 j++ 348 } 349 } 350 351 if i < len(s.members) { 352 out.members = append(out.members, s.members[i:]...) 353 } 354 if j < len(s2.members) { 355 out.members = append(out.members, s2.members[j:]...) 356 } 357 return out 358} 359 360// Intersection returns a SetNodeMap with members that appear in both s and s2. 361func (s *SetNodeMap) Intersection(s2 *SetNodeMap) *SetNodeMap { 362 out := &SetNodeMap{} 363 364 i, j := 0, 0 365 for i < len(s.members) && j < len(s2.members) { 366 if s.members[i].pathElement.Less(s2.members[j].pathElement) { 367 i++ 368 } else { 369 if !s2.members[j].pathElement.Less(s.members[i].pathElement) { 370 res := s.members[i].set.Intersection(s2.members[j].set) 371 if !res.Empty() { 372 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: res}) 373 } 374 i++ 375 } 376 j++ 377 } 378 } 379 return out 380} 381 382// Difference returns a SetNodeMap with members that appear in s but not in s2. 383func (s *SetNodeMap) Difference(s2 *Set) *SetNodeMap { 384 out := &SetNodeMap{} 385 386 i, j := 0, 0 387 for i < len(s.members) && j < len(s2.Children.members) { 388 if s.members[i].pathElement.Less(s2.Children.members[j].pathElement) { 389 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set}) 390 i++ 391 } else { 392 if !s2.Children.members[j].pathElement.Less(s.members[i].pathElement) { 393 394 diff := s.members[i].set.Difference(s2.Children.members[j].set) 395 // We aren't permitted to add nodes with no elements. 396 if !diff.Empty() { 397 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: diff}) 398 } 399 400 i++ 401 } 402 j++ 403 } 404 } 405 406 if i < len(s.members) { 407 out.members = append(out.members, s.members[i:]...) 408 } 409 return out 410} 411 412// RecursiveDifference returns a SetNodeMap with members that appear in s but not in s2. 413// 414// Compared to a regular difference, 415// this removes every field **and its children** from s that is contained in s2. 416// 417// For example, with s containing `a.b.c` and s2 containing `a.b`, 418// a RecursiveDifference will result in `a`, as the entire node `a.b` gets removed. 419func (s *SetNodeMap) RecursiveDifference(s2 *Set) *SetNodeMap { 420 out := &SetNodeMap{} 421 422 i, j := 0, 0 423 for i < len(s.members) && j < len(s2.Children.members) { 424 if s.members[i].pathElement.Less(s2.Children.members[j].pathElement) { 425 if !s2.Members.Has(s.members[i].pathElement) { 426 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: s.members[i].set}) 427 } 428 i++ 429 } else { 430 if !s2.Children.members[j].pathElement.Less(s.members[i].pathElement) { 431 if !s2.Members.Has(s.members[i].pathElement) { 432 diff := s.members[i].set.RecursiveDifference(s2.Children.members[j].set) 433 if !diff.Empty() { 434 out.members = append(out.members, setNode{pathElement: s.members[i].pathElement, set: diff}) 435 } 436 } 437 i++ 438 } 439 j++ 440 } 441 } 442 443 if i < len(s.members) { 444 for _, c := range s.members[i:] { 445 if !s2.Members.Has(c.pathElement) { 446 out.members = append(out.members, c) 447 } 448 } 449 } 450 451 return out 452} 453 454// EnsureNamedFieldsAreMembers returns a set that contains all the named fields along with the leaves. 455func (s *SetNodeMap) EnsureNamedFieldsAreMembers(sc *schema.Schema, tr schema.TypeRef) *SetNodeMap { 456 out := make(sortedSetNode, 0, s.Size()) 457 atom, _ := sc.Resolve(tr) 458 for _, member := range s.members { 459 tr := schema.TypeRef{} 460 if member.pathElement.FieldName != nil && atom.Map != nil { 461 tr = atom.Map.ElementType 462 if sf, ok := atom.Map.FindField(*member.pathElement.FieldName); ok { 463 tr = sf.Type 464 } 465 } else if member.pathElement.Key != nil && atom.List != nil { 466 tr = atom.List.ElementType 467 } 468 out = append(out, setNode{ 469 pathElement: member.pathElement, 470 set: member.set.EnsureNamedFieldsAreMembers(sc, tr), 471 }) 472 } 473 474 return &SetNodeMap{ 475 members: out, 476 } 477} 478 479// Iterate calls f for each PathElement in the set. 480func (s *SetNodeMap) Iterate(f func(PathElement)) { 481 for _, n := range s.members { 482 f(n.pathElement) 483 } 484} 485 486func (s *SetNodeMap) iteratePrefix(prefix Path, f func(Path)) { 487 for _, n := range s.members { 488 pe := n.pathElement 489 n.set.iteratePrefix(append(prefix, pe), f) 490 } 491} 492 493// Leaves returns a SetNodeMap containing 494// only setNodes with leaf PathElements. 495func (s *SetNodeMap) Leaves() *SetNodeMap { 496 out := &SetNodeMap{} 497 out.members = make(sortedSetNode, len(s.members)) 498 for i, n := range s.members { 499 out.members[i] = setNode{ 500 pathElement: n.pathElement, 501 set: n.set.Leaves(), 502 } 503 } 504 return out 505} 506