1package convert 2 3import ( 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. 18func unify(types []cty.Type, unsafe bool) (cty.Type, []Conversion) { 19 if len(types) == 0 { 20 // Degenerate case 21 return cty.NilType, nil 22 } 23 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 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)) 63Preferences: 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 94 // If we fall out here, no unification is possible 95 return cty.NilType, nil 96} 97 98func 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 175func 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 209func 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 271func 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 306func 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} 315