vendor/github.com/zclconf/go-cty/cty/path_set.go

   1 package cty
   2
   3 import (
   4         "fmt"
   5         "hash/crc64"
   6
   7         "github.com/zclconf/go-cty/cty/set"
   8 )
   9
  10 // PathSet represents a set of Path objects. This can be used, for example,
  11 // to talk about a subset of paths within a value that meet some criteria,
  12 // without directly modifying the values at those paths.
  13 type PathSet struct {
  14         set set.Set
  15 }
  16
  17 // NewPathSet creates and returns a PathSet, with initial contents optionally
  18 // set by the given arguments.
  19 func NewPathSet(paths ...Path) PathSet {
  20         ret := PathSet{
  21                 set: set.NewSet(pathSetRules{}),
  22         }
  23
  24         for _, path := range paths {
  25                 ret.Add(path)
  26         }
  27
  28         return ret
  29 }
  30
  31 // Add inserts a single given path into the set.
  32 //
  33 // Paths are immutable after construction by convention. It is particularly
  34 // important not to mutate a path after it has been placed into a PathSet.
  35 // If a Path is mutated while in a set, behavior is undefined.
  36 func (s PathSet) Add(path Path) {
  37         s.set.Add(path)
  38 }
  39
  40 // AddAllSteps is like Add but it also adds all of the steps leading to
  41 // the given path.
  42 //
  43 // For example, if given a path representing "foo.bar", it will add both
  44 // "foo" and "bar".
  45 func (s PathSet) AddAllSteps(path Path) {
  46         for i := 1; i <= len(path); i++ {
  47                 s.Add(path[:i])
  48         }
  49 }
  50
  51 // Has returns true if the given path is in the receiving set.
  52 func (s PathSet) Has(path Path) bool {
  53         return s.set.Has(path)
  54 }
  55
  56 // List makes and returns a slice of all of the paths in the receiving set,
  57 // in an undefined but consistent order.
  58 func (s PathSet) List() []Path {
  59         if s.Empty() {
  60                 return nil
  61         }
  62         ret := make([]Path, 0, s.set.Length())
  63         for it := s.set.Iterator(); it.Next(); {
  64                 ret = append(ret, it.Value().(Path))
  65         }
  66         return ret
  67 }
  68
  69 // Remove modifies the receving set to no longer include the given path.
  70 // If the given path was already absent, this is a no-op.
  71 func (s PathSet) Remove(path Path) {
  72         s.set.Remove(path)
  73 }
  74
  75 // Empty returns true if the length of the receiving set is zero.
  76 func (s PathSet) Empty() bool {
  77         return s.set.Length() == 0
  78 }
  79
  80 // Union returns a new set whose contents are the union of the receiver and
  81 // the given other set.
  82 func (s PathSet) Union(other PathSet) PathSet {
  83         return PathSet{
  84                 set: s.set.Union(other.set),
  85         }
  86 }
  87
  88 // Intersection returns a new set whose contents are the intersection of the
  89 // receiver and the given other set.
  90 func (s PathSet) Intersection(other PathSet) PathSet {
  91         return PathSet{
  92                 set: s.set.Intersection(other.set),
  93         }
  94 }
  95
  96 // Subtract returns a new set whose contents are those from the receiver with
  97 // any elements of the other given set subtracted.
  98 func (s PathSet) Subtract(other PathSet) PathSet {
  99         return PathSet{
 100                 set: s.set.Subtract(other.set),
 101         }
 102 }
 103
 104 // SymmetricDifference returns a new set whose contents are the symmetric
 105 // difference of the receiver and the given other set.
 106 func (s PathSet) SymmetricDifference(other PathSet) PathSet {
 107         return PathSet{
 108                 set: s.set.SymmetricDifference(other.set),
 109         }
 110 }
 111
 112 // Equal returns true if and only if both the receiver and the given other
 113 // set contain exactly the same paths.
 114 func (s PathSet) Equal(other PathSet) bool {
 115         if s.set.Length() != other.set.Length() {
 116                 return false
 117         }
 118         // Now we know the lengths are the same we only need to test in one
 119         // direction whether everything in one is in the other.
 120         for it := s.set.Iterator(); it.Next(); {
 121                 if !other.set.Has(it.Value()) {
 122                         return false
 123                 }
 124         }
 125         return true
 126 }
 127
 128 var crc64Table = crc64.MakeTable(crc64.ISO)
 129
 130 var indexStepPlaceholder = []byte("#")
 131
 132 // pathSetRules is an implementation of set.Rules from the set package,
 133 // used internally within PathSet.
 134 type pathSetRules struct {
 135 }
 136
 137 func (r pathSetRules) Hash(v interface{}) int {
 138         path := v.(Path)
 139         hash := crc64.New(crc64Table)
 140
 141         for _, rawStep := range path {
 142                 switch step := rawStep.(type) {
 143                 case GetAttrStep:
 144                         // (this creates some garbage converting the string name to a
 145                         // []byte, but that's okay since cty is not designed to be
 146                         // used in tight loops under memory pressure.)
 147                         hash.Write([]byte(step.Name))
 148                 default:
 149                         // For any other step type we just append a predefined value,
 150                         // which means that e.g. all indexes into a given collection will
 151                         // hash to the same value but we assume that collections are
 152                         // small and thus this won't hurt too much.
 153                         hash.Write(indexStepPlaceholder)
 154                 }
 155         }
 156
 157         // We discard half of the hash on 32-bit platforms; collisions just make
 158         // our lookups take marginally longer, so not a big deal.
 159         return int(hash.Sum64())
 160 }
 161
 162 func (r pathSetRules) Equivalent(a, b interface{}) bool {
 163         aPath := a.(Path)
 164         bPath := b.(Path)
 165
 166         if len(aPath) != len(bPath) {
 167                 return false
 168         }
 169
 170         for i := range aPath {
 171                 switch aStep := aPath[i].(type) {
 172                 case GetAttrStep:
 173                         bStep, ok := bPath[i].(GetAttrStep)
 174                         if !ok {
 175                                 return false
 176                         }
 177
 178                         if aStep.Name != bStep.Name {
 179                                 return false
 180                         }
 181                 case IndexStep:
 182                         bStep, ok := bPath[i].(IndexStep)
 183                         if !ok {
 184                                 return false
 185                         }
 186
 187                         eq := aStep.Key.Equals(bStep.Key)
 188                         if !eq.IsKnown() || eq.False() {
 189                                 return false
 190                         }
 191                 default:
 192                         // Should never happen, since we document PathStep as a closed type.
 193                         panic(fmt.Errorf("unsupported step type %T", aStep))
 194                 }
 195         }
 196
 197         return true
 198 }