]>
Commit | Line | Data |
---|---|---|
15c0b25d AP |
1 | package convert |
2 | ||
3 | import ( | |
4 | "github.com/zclconf/go-cty/cty" | |
5 | ) | |
6 | ||
7 | // The current unify implementation is somewhat inefficient, but we accept this | |
8 | // under the assumption that it will generally be used with small numbers of | |
9 | // types and with types of reasonable complexity. However, it does have a | |
10 | // "happy path" where all of the given types are equal. | |
11 | // | |
12 | // This function is likely to have poor performance in cases where any given | |
13 | // types are very complex (lots of deeply-nested structures) or if the list | |
14 | // of types itself is very large. In particular, it will walk the nested type | |
15 | // structure under the given types several times, especially when given a | |
16 | // list of types for which unification is not possible, since each permutation | |
17 | // will be tried to determine that result. | |
18 | func unify(types []cty.Type, unsafe bool) (cty.Type, []Conversion) { | |
19 | if len(types) == 0 { | |
20 | // Degenerate case | |
21 | return cty.NilType, nil | |
22 | } | |
23 | ||
107c1cdb ND |
24 | // If all of the given types are of the same structural kind, we may be |
25 | // able to construct a new type that they can all be unified to, even if | |
26 | // that is not one of the given types. We must try this before the general | |
27 | // behavior below because in unsafe mode we can convert an object type to | |
28 | // a subset of that type, which would be a much less useful conversion for | |
29 | // unification purposes. | |
30 | { | |
31 | objectCt := 0 | |
32 | tupleCt := 0 | |
33 | dynamicCt := 0 | |
34 | for _, ty := range types { | |
35 | switch { | |
36 | case ty.IsObjectType(): | |
37 | objectCt++ | |
38 | case ty.IsTupleType(): | |
39 | tupleCt++ | |
40 | case ty == cty.DynamicPseudoType: | |
41 | dynamicCt++ | |
42 | default: | |
43 | break | |
44 | } | |
45 | } | |
46 | switch { | |
47 | case objectCt > 0 && (objectCt+dynamicCt) == len(types): | |
48 | return unifyObjectTypes(types, unsafe, dynamicCt > 0) | |
49 | case tupleCt > 0 && (tupleCt+dynamicCt) == len(types): | |
50 | return unifyTupleTypes(types, unsafe, dynamicCt > 0) | |
51 | case objectCt > 0 && tupleCt > 0: | |
52 | // Can never unify object and tuple types since they have incompatible kinds | |
53 | return cty.NilType, nil | |
54 | } | |
55 | } | |
56 | ||
15c0b25d AP |
57 | prefOrder := sortTypes(types) |
58 | ||
59 | // sortTypes gives us an order where earlier items are preferable as | |
60 | // our result type. We'll now walk through these and choose the first | |
61 | // one we encounter for which conversions exist for all source types. | |
62 | conversions := make([]Conversion, len(types)) | |
63 | Preferences: | |
64 | for _, wantTypeIdx := range prefOrder { | |
65 | wantType := types[wantTypeIdx] | |
66 | for i, tryType := range types { | |
67 | if i == wantTypeIdx { | |
68 | // Don't need to convert our wanted type to itself | |
69 | conversions[i] = nil | |
70 | continue | |
71 | } | |
72 | ||
73 | if tryType.Equals(wantType) { | |
74 | conversions[i] = nil | |
75 | continue | |
76 | } | |
77 | ||
78 | if unsafe { | |
79 | conversions[i] = GetConversionUnsafe(tryType, wantType) | |
80 | } else { | |
81 | conversions[i] = GetConversion(tryType, wantType) | |
82 | } | |
83 | ||
84 | if conversions[i] == nil { | |
85 | // wantType is not a suitable unification type, so we'll | |
86 | // try the next one in our preference order. | |
87 | continue Preferences | |
88 | } | |
89 | } | |
90 | ||
91 | return wantType, conversions | |
92 | } | |
93 | ||
15c0b25d AP |
94 | // If we fall out here, no unification is possible |
95 | return cty.NilType, nil | |
96 | } | |
107c1cdb ND |
97 | |
98 | func unifyObjectTypes(types []cty.Type, unsafe bool, hasDynamic bool) (cty.Type, []Conversion) { | |
99 | // If we had any dynamic types in the input here then we can't predict | |
100 | // what path we'll take through here once these become known types, so | |
101 | // we'll conservatively produce DynamicVal for these. | |
102 | if hasDynamic { | |
103 | return unifyAllAsDynamic(types) | |
104 | } | |
105 | ||
106 | // There are two different ways we can succeed here: | |
107 | // - If all of the given object types have the same set of attribute names | |
108 | // and the corresponding types are all unifyable, then we construct that | |
109 | // type. | |
110 | // - If the given object types have different attribute names or their | |
111 | // corresponding types are not unifyable, we'll instead try to unify | |
112 | // all of the attribute types together to produce a map type. | |
113 | // | |
114 | // Our unification behavior is intentionally stricter than our conversion | |
115 | // behavior for subset object types because user intent is different with | |
116 | // unification use-cases: it makes sense to allow {"foo":true} to convert | |
117 | // to emptyobjectval, but unifying an object with an attribute with the | |
118 | // empty object type should be an error because unifying to the empty | |
119 | // object type would be suprising and useless. | |
120 | ||
121 | firstAttrs := types[0].AttributeTypes() | |
122 | for _, ty := range types[1:] { | |
123 | thisAttrs := ty.AttributeTypes() | |
124 | if len(thisAttrs) != len(firstAttrs) { | |
125 | // If number of attributes is different then there can be no | |
126 | // object type in common. | |
127 | return unifyObjectTypesToMap(types, unsafe) | |
128 | } | |
129 | for name := range thisAttrs { | |
130 | if _, ok := firstAttrs[name]; !ok { | |
131 | // If attribute names don't exactly match then there can be | |
132 | // no object type in common. | |
133 | return unifyObjectTypesToMap(types, unsafe) | |
134 | } | |
135 | } | |
136 | } | |
137 | ||
138 | // If we get here then we've proven that all of the given object types | |
139 | // have exactly the same set of attribute names, though the types may | |
140 | // differ. | |
141 | retAtys := make(map[string]cty.Type) | |
142 | atysAcross := make([]cty.Type, len(types)) | |
143 | for name := range firstAttrs { | |
144 | for i, ty := range types { | |
145 | atysAcross[i] = ty.AttributeType(name) | |
146 | } | |
147 | retAtys[name], _ = unify(atysAcross, unsafe) | |
148 | if retAtys[name] == cty.NilType { | |
149 | // Cannot unify this attribute alone, which means that unification | |
150 | // of everything down to a map type can't be possible either. | |
151 | return cty.NilType, nil | |
152 | } | |
153 | } | |
154 | retTy := cty.Object(retAtys) | |
155 | ||
156 | conversions := make([]Conversion, len(types)) | |
157 | for i, ty := range types { | |
158 | if ty.Equals(retTy) { | |
159 | continue | |
160 | } | |
161 | if unsafe { | |
162 | conversions[i] = GetConversionUnsafe(ty, retTy) | |
163 | } else { | |
164 | conversions[i] = GetConversion(ty, retTy) | |
165 | } | |
166 | if conversions[i] == nil { | |
167 | // Shouldn't be reachable, since we were able to unify | |
168 | return unifyObjectTypesToMap(types, unsafe) | |
169 | } | |
170 | } | |
171 | ||
172 | return retTy, conversions | |
173 | } | |
174 | ||
175 | func unifyObjectTypesToMap(types []cty.Type, unsafe bool) (cty.Type, []Conversion) { | |
176 | // This is our fallback case for unifyObjectTypes, where we see if we can | |
177 | // construct a map type that can accept all of the attribute types. | |
178 | ||
179 | var atys []cty.Type | |
180 | for _, ty := range types { | |
181 | for _, aty := range ty.AttributeTypes() { | |
182 | atys = append(atys, aty) | |
183 | } | |
184 | } | |
185 | ||
186 | ety, _ := unify(atys, unsafe) | |
187 | if ety == cty.NilType { | |
188 | return cty.NilType, nil | |
189 | } | |
190 | ||
191 | retTy := cty.Map(ety) | |
192 | conversions := make([]Conversion, len(types)) | |
193 | for i, ty := range types { | |
194 | if ty.Equals(retTy) { | |
195 | continue | |
196 | } | |
197 | if unsafe { | |
198 | conversions[i] = GetConversionUnsafe(ty, retTy) | |
199 | } else { | |
200 | conversions[i] = GetConversion(ty, retTy) | |
201 | } | |
202 | if conversions[i] == nil { | |
203 | return cty.NilType, nil | |
204 | } | |
205 | } | |
206 | return retTy, conversions | |
207 | } | |
208 | ||
209 | func unifyTupleTypes(types []cty.Type, unsafe bool, hasDynamic bool) (cty.Type, []Conversion) { | |
210 | // If we had any dynamic types in the input here then we can't predict | |
211 | // what path we'll take through here once these become known types, so | |
212 | // we'll conservatively produce DynamicVal for these. | |
213 | if hasDynamic { | |
214 | return unifyAllAsDynamic(types) | |
215 | } | |
216 | ||
217 | // There are two different ways we can succeed here: | |
218 | // - If all of the given tuple types have the same sequence of element types | |
219 | // and the corresponding types are all unifyable, then we construct that | |
220 | // type. | |
221 | // - If the given tuple types have different element types or their | |
222 | // corresponding types are not unifyable, we'll instead try to unify | |
223 | // all of the elements types together to produce a list type. | |
224 | ||
225 | firstEtys := types[0].TupleElementTypes() | |
226 | for _, ty := range types[1:] { | |
227 | thisEtys := ty.TupleElementTypes() | |
228 | if len(thisEtys) != len(firstEtys) { | |
229 | // If number of elements is different then there can be no | |
230 | // tuple type in common. | |
231 | return unifyTupleTypesToList(types, unsafe) | |
232 | } | |
233 | } | |
234 | ||
235 | // If we get here then we've proven that all of the given tuple types | |
236 | // have the same number of elements, though the types may differ. | |
237 | retEtys := make([]cty.Type, len(firstEtys)) | |
238 | atysAcross := make([]cty.Type, len(types)) | |
239 | for idx := range firstEtys { | |
240 | for tyI, ty := range types { | |
241 | atysAcross[tyI] = ty.TupleElementTypes()[idx] | |
242 | } | |
243 | retEtys[idx], _ = unify(atysAcross, unsafe) | |
244 | if retEtys[idx] == cty.NilType { | |
245 | // Cannot unify this element alone, which means that unification | |
246 | // of everything down to a map type can't be possible either. | |
247 | return cty.NilType, nil | |
248 | } | |
249 | } | |
250 | retTy := cty.Tuple(retEtys) | |
251 | ||
252 | conversions := make([]Conversion, len(types)) | |
253 | for i, ty := range types { | |
254 | if ty.Equals(retTy) { | |
255 | continue | |
256 | } | |
257 | if unsafe { | |
258 | conversions[i] = GetConversionUnsafe(ty, retTy) | |
259 | } else { | |
260 | conversions[i] = GetConversion(ty, retTy) | |
261 | } | |
262 | if conversions[i] == nil { | |
263 | // Shouldn't be reachable, since we were able to unify | |
264 | return unifyTupleTypesToList(types, unsafe) | |
265 | } | |
266 | } | |
267 | ||
268 | return retTy, conversions | |
269 | } | |
270 | ||
271 | func unifyTupleTypesToList(types []cty.Type, unsafe bool) (cty.Type, []Conversion) { | |
272 | // This is our fallback case for unifyTupleTypes, where we see if we can | |
273 | // construct a list type that can accept all of the element types. | |
274 | ||
275 | var etys []cty.Type | |
276 | for _, ty := range types { | |
277 | for _, ety := range ty.TupleElementTypes() { | |
278 | etys = append(etys, ety) | |
279 | } | |
280 | } | |
281 | ||
282 | ety, _ := unify(etys, unsafe) | |
283 | if ety == cty.NilType { | |
284 | return cty.NilType, nil | |
285 | } | |
286 | ||
287 | retTy := cty.List(ety) | |
288 | conversions := make([]Conversion, len(types)) | |
289 | for i, ty := range types { | |
290 | if ty.Equals(retTy) { | |
291 | continue | |
292 | } | |
293 | if unsafe { | |
294 | conversions[i] = GetConversionUnsafe(ty, retTy) | |
295 | } else { | |
296 | conversions[i] = GetConversion(ty, retTy) | |
297 | } | |
298 | if conversions[i] == nil { | |
299 | // Shouldn't be reachable, since we were able to unify | |
300 | return unifyObjectTypesToMap(types, unsafe) | |
301 | } | |
302 | } | |
303 | return retTy, conversions | |
304 | } | |
305 | ||
306 | func unifyAllAsDynamic(types []cty.Type) (cty.Type, []Conversion) { | |
307 | conversions := make([]Conversion, len(types)) | |
308 | for i := range conversions { | |
309 | conversions[i] = func(cty.Value) (cty.Value, error) { | |
310 | return cty.DynamicVal, nil | |
311 | } | |
312 | } | |
313 | return cty.DynamicPseudoType, conversions | |
314 | } |