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