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

   1 package cty
   2
   3 import (
   4         "bytes"
   5         "fmt"
   6         "hash/crc32"
   7         "math/big"
   8         "sort"
   9
  10         "github.com/zclconf/go-cty/cty/set"
  11 )
  12
  13 // setRules provides a Rules implementation for the ./set package that
  14 // respects the equality rules for cty values of the given type.
  15 //
  16 // This implementation expects that values added to the set will be
  17 // valid internal values for the given Type, which is to say that wrapping
  18 // the given value in a Value struct along with the ruleset's type should
  19 // produce a valid, working Value.
  20 type setRules struct {
  21         Type Type
  22 }
  23
  24 var _ set.OrderedRules = setRules{}
  25
  26 // Hash returns a hash value for the receiver that can be used for equality
  27 // checks where some inaccuracy is tolerable.
  28 //
  29 // The hash function is value-type-specific, so it is not meaningful to compare
  30 // hash results for values of different types.
  31 //
  32 // This function is not safe to use for security-related applications, since
  33 // the hash used is not strong enough.
  34 func (val Value) Hash() int {
  35         hashBytes := makeSetHashBytes(val)
  36         return int(crc32.ChecksumIEEE(hashBytes))
  37 }
  38
  39 func (r setRules) Hash(v interface{}) int {
  40         return Value{
  41                 ty: r.Type,
  42                 v:  v,
  43         }.Hash()
  44 }
  45
  46 func (r setRules) Equivalent(v1 interface{}, v2 interface{}) bool {
  47         v1v := Value{
  48                 ty: r.Type,
  49                 v:  v1,
  50         }
  51         v2v := Value{
  52                 ty: r.Type,
  53                 v:  v2,
  54         }
  55
  56         eqv := v1v.Equals(v2v)
  57
  58         // By comparing the result to true we ensure that an Unknown result,
  59         // which will result if either value is unknown, will be considered
  60         // as non-equivalent. Two unknown values are not equivalent for the
  61         // sake of set membership.
  62         return eqv.v == true
  63 }
  64
  65 // Less is an implementation of set.OrderedRules so that we can iterate over
  66 // set elements in a consistent order, where such an order is possible.
  67 func (r setRules) Less(v1, v2 interface{}) bool {
  68         v1v := Value{
  69                 ty: r.Type,
  70                 v:  v1,
  71         }
  72         v2v := Value{
  73                 ty: r.Type,
  74                 v:  v2,
  75         }
  76
  77         if v1v.RawEquals(v2v) { // Easy case: if they are equal then v1 can't be less
  78                 return false
  79         }
  80
  81         // Null values always sort after non-null values
  82         if v2v.IsNull() && !v1v.IsNull() {
  83                 return true
  84         } else if v1v.IsNull() {
  85                 return false
  86         }
  87         // Unknown values always sort after known values
  88         if v1v.IsKnown() && !v2v.IsKnown() {
  89                 return true
  90         } else if !v1v.IsKnown() {
  91                 return false
  92         }
  93
  94         switch r.Type {
  95         case String:
  96                 // String values sort lexicographically
  97                 return v1v.AsString() < v2v.AsString()
  98         case Bool:
  99                 // Weird to have a set of bools, but if we do then false sorts before true.
 100                 if v2v.True() || !v1v.True() {
 101                         return true
 102                 }
 103                 return false
 104         case Number:
 105                 v1f := v1v.AsBigFloat()
 106                 v2f := v2v.AsBigFloat()
 107                 return v1f.Cmp(v2f) < 0
 108         default:
 109                 // No other types have a well-defined ordering, so we just produce a
 110                 // default consistent-but-undefined ordering then. This situation is
 111                 // not considered a compatibility constraint; callers should rely only
 112                 // on the ordering rules for primitive values.
 113                 v1h := makeSetHashBytes(v1v)
 114                 v2h := makeSetHashBytes(v2v)
 115                 return bytes.Compare(v1h, v2h) < 0
 116         }
 117 }
 118
 119 func makeSetHashBytes(val Value) []byte {
 120         var buf bytes.Buffer
 121         appendSetHashBytes(val, &buf)
 122         return buf.Bytes()
 123 }
 124
 125 func appendSetHashBytes(val Value, buf *bytes.Buffer) {
 126         // Exactly what bytes we generate here don't matter as long as the following
 127         // constraints hold:
 128         // - Unknown and null values all generate distinct strings from
 129         //   each other and from any normal value of the given type.
 130         // - The delimiter used to separate items in a compound structure can
 131         //   never appear literally in any of its elements.
 132         // Since we don't support hetrogenous lists we don't need to worry about
 133         // collisions between values of different types, apart from
 134         // PseudoTypeDynamic.
 135         // If in practice we *do* get a collision then it's not a big deal because
 136         // the Equivalent function will still distinguish values, but set
 137         // performance will be best if we are able to produce a distinct string
 138         // for each distinct value, unknown values notwithstanding.
 139         if !val.IsKnown() {
 140                 buf.WriteRune('?')
 141                 return
 142         }
 143         if val.IsNull() {
 144                 buf.WriteRune('~')
 145                 return
 146         }
 147
 148         switch val.ty {
 149         case Number:
 150                 buf.WriteString(val.v.(*big.Float).String())
 151                 return
 152         case Bool:
 153                 if val.v.(bool) {
 154                         buf.WriteRune('T')
 155                 } else {
 156                         buf.WriteRune('F')
 157                 }
 158                 return
 159         case String:
 160                 buf.WriteString(fmt.Sprintf("%q", val.v.(string)))
 161                 return
 162         }
 163
 164         if val.ty.IsMapType() {
 165                 buf.WriteRune('{')
 166                 val.ForEachElement(func(keyVal, elementVal Value) bool {
 167                         appendSetHashBytes(keyVal, buf)
 168                         buf.WriteRune(':')
 169                         appendSetHashBytes(elementVal, buf)
 170                         buf.WriteRune(';')
 171                         return false
 172                 })
 173                 buf.WriteRune('}')
 174                 return
 175         }
 176
 177         if val.ty.IsListType() || val.ty.IsSetType() {
 178                 buf.WriteRune('[')
 179                 val.ForEachElement(func(keyVal, elementVal Value) bool {
 180                         appendSetHashBytes(elementVal, buf)
 181                         buf.WriteRune(';')
 182                         return false
 183                 })
 184                 buf.WriteRune(']')
 185                 return
 186         }
 187
 188         if val.ty.IsObjectType() {
 189                 buf.WriteRune('<')
 190                 attrNames := make([]string, 0, len(val.ty.AttributeTypes()))
 191                 for attrName := range val.ty.AttributeTypes() {
 192                         attrNames = append(attrNames, attrName)
 193                 }
 194                 sort.Strings(attrNames)
 195                 for _, attrName := range attrNames {
 196                         appendSetHashBytes(val.GetAttr(attrName), buf)
 197                         buf.WriteRune(';')
 198                 }
 199                 buf.WriteRune('>')
 200                 return
 201         }
 202
 203         if val.ty.IsTupleType() {
 204                 buf.WriteRune('<')
 205                 val.ForEachElement(func(keyVal, elementVal Value) bool {
 206                         appendSetHashBytes(elementVal, buf)
 207                         buf.WriteRune(';')
 208                         return false
 209                 })
 210                 buf.WriteRune('>')
 211                 return
 212         }
 213
 214         // should never get down here
 215         panic("unsupported type in set hash")
 216 }