]>
Commit | Line | Data |
---|---|---|
15c0b25d AP |
1 | package cty |
2 | ||
3 | import ( | |
4 | "bytes" | |
5 | "fmt" | |
6 | "hash/crc32" | |
7 | "math/big" | |
8 | "sort" | |
107c1cdb ND |
9 | |
10 | "github.com/zclconf/go-cty/cty/set" | |
15c0b25d AP |
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 | ||
107c1cdb ND |
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 | ||
15c0b25d | 39 | func (r setRules) Hash(v interface{}) int { |
107c1cdb | 40 | return Value{ |
15c0b25d AP |
41 | ty: r.Type, |
42 | v: v, | |
107c1cdb | 43 | }.Hash() |
15c0b25d AP |
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 | ||
107c1cdb ND |
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 | ||
15c0b25d AP |
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 | } |