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