vendor/github.com/zclconf/go-cty/cty/convert/unify.go

   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
  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))
  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
  94         // If we fall out here, no unification is possible
  95         return cty.NilType, nil
  96 }
  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 }