set.go

Documentation: sigs.k8s.io/structured-merge-diff/v4/fieldpath

     1  /*
     2  Copyright 2018 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 fieldpath
    18  
    19  import (
    20  	"sort"
    21  	"strings"
    22  
    23  	"sigs.k8s.io/structured-merge-diff/v4/schema"
    24  )
    25  
    26  // Set identifies a set of fields.
    27  type 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.
    39  func 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.
    49  func (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.
    66  func (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.
    76  func (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}
    92  func (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.
   108  func (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.
   119  func (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.
   140  func (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.
   147  func (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.
   155  func (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.
   174  func (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.
   179  func (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.
   190  func (s *Set) Iterate(f func(Path)) {
   191  	s.iteratePrefix(Path{}, f)
   192  }
   193  
   194  func (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.
   201  func (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.
   211  func (s *Set) Leaves() *Set {
   212  	leaves := PathElementSet{}
   213  	im := 0
   214  	ic := 0
   215  
   216  	// any members that are not also children are leaves
   217  outer:
   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.
   245  type setNode struct {
   246  	pathElement PathElement
   247  	set         *Set
   248  }
   249  
   250  // SetNodeMap is a map of PathElement to subset.
   251  type SetNodeMap struct {
   252  	members sortedSetNode
   253  }
   254  
   255  type 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.
   259  func (s sortedSetNode) Len() int           { return len(s) }
   260  func (s sortedSetNode) Less(i, j int) bool { return s[i].pathElement.Less(s[j].pathElement) }
   261  func (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.
   264  func (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.
   282  func (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.
   291  func (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.
   301  func (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).
   316  func (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.
   332  func (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.
   361  func (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.
   383  func (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.
   419  func (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.
   455  func (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.
   480  func (s *SetNodeMap) Iterate(f func(PathElement)) {
   481  	for _, n := range s.members {
   482  		f(n.pathElement)
   483  	}
   484  }
   485  
   486  func (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.
   495  func (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
View as plain text