element.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  	"fmt"
    21  	"sort"
    22  	"strings"
    23  
    24  	"sigs.k8s.io/structured-merge-diff/v4/value"
    25  )
    26  
    27  // PathElement describes how to select a child field given a containing object.
    28  type PathElement struct {
    29  	// Exactly one of the following fields should be non-nil.
    30  
    31  	// FieldName selects a single field from a map (reminder: this is also
    32  	// how structs are represented). The containing object must be a map.
    33  	FieldName *string
    34  
    35  	// Key selects the list element which has fields matching those given.
    36  	// The containing object must be an associative list with map typed
    37  	// elements. They are sorted alphabetically.
    38  	Key *value.FieldList
    39  
    40  	// Value selects the list element with the given value. The containing
    41  	// object must be an associative list with a primitive typed element
    42  	// (i.e., a set).
    43  	Value *value.Value
    44  
    45  	// Index selects a list element by its index number. The containing
    46  	// object must be an atomic list.
    47  	Index *int
    48  }
    49  
    50  // Less provides an order for path elements.
    51  func (e PathElement) Less(rhs PathElement) bool {
    52  	return e.Compare(rhs) < 0
    53  }
    54  
    55  // Compare provides an order for path elements.
    56  func (e PathElement) Compare(rhs PathElement) int {
    57  	if e.FieldName != nil {
    58  		if rhs.FieldName == nil {
    59  			return -1
    60  		}
    61  		return strings.Compare(*e.FieldName, *rhs.FieldName)
    62  	} else if rhs.FieldName != nil {
    63  		return 1
    64  	}
    65  
    66  	if e.Key != nil {
    67  		if rhs.Key == nil {
    68  			return -1
    69  		}
    70  		return e.Key.Compare(*rhs.Key)
    71  	} else if rhs.Key != nil {
    72  		return 1
    73  	}
    74  
    75  	if e.Value != nil {
    76  		if rhs.Value == nil {
    77  			return -1
    78  		}
    79  		return value.Compare(*e.Value, *rhs.Value)
    80  	} else if rhs.Value != nil {
    81  		return 1
    82  	}
    83  
    84  	if e.Index != nil {
    85  		if rhs.Index == nil {
    86  			return -1
    87  		}
    88  		if *e.Index < *rhs.Index {
    89  			return -1
    90  		} else if *e.Index == *rhs.Index {
    91  			return 0
    92  		}
    93  		return 1
    94  	} else if rhs.Index != nil {
    95  		return 1
    96  	}
    97  
    98  	return 0
    99  }
   100  
   101  // Equals returns true if both path elements are equal.
   102  func (e PathElement) Equals(rhs PathElement) bool {
   103  	if e.FieldName != nil {
   104  		if rhs.FieldName == nil {
   105  			return false
   106  		}
   107  		return *e.FieldName == *rhs.FieldName
   108  	} else if rhs.FieldName != nil {
   109  		return false
   110  	}
   111  	if e.Key != nil {
   112  		if rhs.Key == nil {
   113  			return false
   114  		}
   115  		return e.Key.Equals(*rhs.Key)
   116  	} else if rhs.Key != nil {
   117  		return false
   118  	}
   119  	if e.Value != nil {
   120  		if rhs.Value == nil {
   121  			return false
   122  		}
   123  		return value.Equals(*e.Value, *rhs.Value)
   124  	} else if rhs.Value != nil {
   125  		return false
   126  	}
   127  	if e.Index != nil {
   128  		if rhs.Index == nil {
   129  			return false
   130  		}
   131  		return *e.Index == *rhs.Index
   132  	} else if rhs.Index != nil {
   133  		return false
   134  	}
   135  	return true
   136  }
   137  
   138  // String presents the path element as a human-readable string.
   139  func (e PathElement) String() string {
   140  	switch {
   141  	case e.FieldName != nil:
   142  		return "." + *e.FieldName
   143  	case e.Key != nil:
   144  		strs := make([]string, len(*e.Key))
   145  		for i, k := range *e.Key {
   146  			strs[i] = fmt.Sprintf("%v=%v", k.Name, value.ToString(k.Value))
   147  		}
   148  		// Keys are supposed to be sorted.
   149  		return "[" + strings.Join(strs, ",") + "]"
   150  	case e.Value != nil:
   151  		return fmt.Sprintf("[=%v]", value.ToString(*e.Value))
   152  	case e.Index != nil:
   153  		return fmt.Sprintf("[%v]", *e.Index)
   154  	default:
   155  		return "{{invalid path element}}"
   156  	}
   157  }
   158  
   159  // KeyByFields is a helper function which constructs a key for an associative
   160  // list type. `nameValues` must have an even number of entries, alternating
   161  // names (type must be string) with values (type must be value.Value). If these
   162  // conditions are not met, KeyByFields will panic--it's intended for static
   163  // construction and shouldn't have user-produced values passed to it.
   164  func KeyByFields(nameValues ...interface{}) *value.FieldList {
   165  	if len(nameValues)%2 != 0 {
   166  		panic("must have a value for every name")
   167  	}
   168  	out := value.FieldList{}
   169  	for i := 0; i < len(nameValues)-1; i += 2 {
   170  		out = append(out, value.Field{Name: nameValues[i].(string), Value: value.NewValueInterface(nameValues[i+1])})
   171  	}
   172  	out.Sort()
   173  	return &out
   174  }
   175  
   176  // PathElementSet is a set of path elements.
   177  // TODO: serialize as a list.
   178  type PathElementSet struct {
   179  	members sortedPathElements
   180  }
   181  
   182  func MakePathElementSet(size int) PathElementSet {
   183  	return PathElementSet{
   184  		members: make(sortedPathElements, 0, size),
   185  	}
   186  }
   187  
   188  type sortedPathElements []PathElement
   189  
   190  // Implement the sort interface; this would permit bulk creation, which would
   191  // be faster than doing it one at a time via Insert.
   192  func (spe sortedPathElements) Len() int           { return len(spe) }
   193  func (spe sortedPathElements) Less(i, j int) bool { return spe[i].Less(spe[j]) }
   194  func (spe sortedPathElements) Swap(i, j int)      { spe[i], spe[j] = spe[j], spe[i] }
   195  
   196  // Insert adds pe to the set.
   197  func (s *PathElementSet) Insert(pe PathElement) {
   198  	loc := sort.Search(len(s.members), func(i int) bool {
   199  		return !s.members[i].Less(pe)
   200  	})
   201  	if loc == len(s.members) {
   202  		s.members = append(s.members, pe)
   203  		return
   204  	}
   205  	if s.members[loc].Equals(pe) {
   206  		return
   207  	}
   208  	s.members = append(s.members, PathElement{})
   209  	copy(s.members[loc+1:], s.members[loc:])
   210  	s.members[loc] = pe
   211  }
   212  
   213  // Union returns a set containing elements that appear in either s or s2.
   214  func (s *PathElementSet) Union(s2 *PathElementSet) *PathElementSet {
   215  	out := &PathElementSet{}
   216  
   217  	i, j := 0, 0
   218  	for i < len(s.members) && j < len(s2.members) {
   219  		if s.members[i].Less(s2.members[j]) {
   220  			out.members = append(out.members, s.members[i])
   221  			i++
   222  		} else {
   223  			out.members = append(out.members, s2.members[j])
   224  			if !s2.members[j].Less(s.members[i]) {
   225  				i++
   226  			}
   227  			j++
   228  		}
   229  	}
   230  
   231  	if i < len(s.members) {
   232  		out.members = append(out.members, s.members[i:]...)
   233  	}
   234  	if j < len(s2.members) {
   235  		out.members = append(out.members, s2.members[j:]...)
   236  	}
   237  	return out
   238  }
   239  
   240  // Intersection returns a set containing elements which appear in both s and s2.
   241  func (s *PathElementSet) Intersection(s2 *PathElementSet) *PathElementSet {
   242  	out := &PathElementSet{}
   243  
   244  	i, j := 0, 0
   245  	for i < len(s.members) && j < len(s2.members) {
   246  		if s.members[i].Less(s2.members[j]) {
   247  			i++
   248  		} else {
   249  			if !s2.members[j].Less(s.members[i]) {
   250  				out.members = append(out.members, s.members[i])
   251  				i++
   252  			}
   253  			j++
   254  		}
   255  	}
   256  
   257  	return out
   258  }
   259  
   260  // Difference returns a set containing elements which appear in s but not in s2.
   261  func (s *PathElementSet) Difference(s2 *PathElementSet) *PathElementSet {
   262  	out := &PathElementSet{}
   263  
   264  	i, j := 0, 0
   265  	for i < len(s.members) && j < len(s2.members) {
   266  		if s.members[i].Less(s2.members[j]) {
   267  			out.members = append(out.members, s.members[i])
   268  			i++
   269  		} else {
   270  			if !s2.members[j].Less(s.members[i]) {
   271  				i++
   272  			}
   273  			j++
   274  		}
   275  	}
   276  	if i < len(s.members) {
   277  		out.members = append(out.members, s.members[i:]...)
   278  	}
   279  	return out
   280  }
   281  
   282  // Size retuns the number of elements in the set.
   283  func (s *PathElementSet) Size() int { return len(s.members) }
   284  
   285  // Has returns true if pe is a member of the set.
   286  func (s *PathElementSet) Has(pe PathElement) bool {
   287  	loc := sort.Search(len(s.members), func(i int) bool {
   288  		return !s.members[i].Less(pe)
   289  	})
   290  	if loc == len(s.members) {
   291  		return false
   292  	}
   293  	if s.members[loc].Equals(pe) {
   294  		return true
   295  	}
   296  	return false
   297  }
   298  
   299  // Equals returns true if s and s2 have exactly the same members.
   300  func (s *PathElementSet) Equals(s2 *PathElementSet) bool {
   301  	if len(s.members) != len(s2.members) {
   302  		return false
   303  	}
   304  	for k := range s.members {
   305  		if !s.members[k].Equals(s2.members[k]) {
   306  			return false
   307  		}
   308  	}
   309  	return true
   310  }
   311  
   312  // Iterate calls f for each PathElement in the set. The order is deterministic.
   313  func (s *PathElementSet) Iterate(f func(PathElement)) {
   314  	for _, pe := range s.members {
   315  		f(pe)
   316  	}
   317  }
   318
View as plain text