1package convert 2 3import ( 4 "github.com/zclconf/go-cty/cty" 5) 6 7// sortTypes produces an ordering of the given types that serves as a 8// preference order for the result of unification of the given types. 9// The return value is a slice of indices into the given slice, and will 10// thus always be the same length as the given slice. 11// 12// The goal is that the most general of the given types will appear first 13// in the ordering. If there are uncomparable pairs of types in the list 14// then they will appear in an undefined order, and the unification pass 15// will presumably then fail. 16func sortTypes(tys []cty.Type) []int { 17 l := len(tys) 18 19 // First we build a graph whose edges represent "more general than", 20 // which we will then do a topological sort of. 21 edges := make([][]int, l) 22 for i := 0; i < (l - 1); i++ { 23 for j := i + 1; j < l; j++ { 24 cmp := compareTypes(tys[i], tys[j]) 25 switch { 26 case cmp < 0: 27 edges[i] = append(edges[i], j) 28 case cmp > 0: 29 edges[j] = append(edges[j], i) 30 } 31 } 32 } 33 34 // Compute the in-degree of each node 35 inDegree := make([]int, l) 36 for _, outs := range edges { 37 for _, j := range outs { 38 inDegree[j]++ 39 } 40 } 41 42 // The array backing our result will double as our queue for visiting 43 // the nodes, with the queue slice moving along this array until it 44 // is empty and positioned at the end of the array. Thus our visiting 45 // order is also our result order. 46 result := make([]int, l) 47 queue := result[0:0] 48 49 // Initialize the queue with any item of in-degree 0, preserving 50 // their relative order. 51 for i, n := range inDegree { 52 if n == 0 { 53 queue = append(queue, i) 54 } 55 } 56 57 for len(queue) != 0 { 58 i := queue[0] 59 queue = queue[1:] 60 for _, j := range edges[i] { 61 inDegree[j]-- 62 if inDegree[j] == 0 { 63 queue = append(queue, j) 64 } 65 } 66 } 67 68 return result 69} 70