1 files changed, 69 insertions, 0 deletions

diff --git a/vendor/github.com/zclconf/go-cty/cty/convert/sort_types.go b/vendor/github.com/zclconf/go-cty/cty/convert/sort_types.go
new file mode 100644
index 0000000..b776910
--- /dev/null
+++ b/vendor/github.com/zclconf/go-cty/cty/convert/sort_types.go
@@ -0,0 +1,69 @@
+package convert
+
+import (
+        "github.com/zclconf/go-cty/cty"
+)
+
+// sortTypes produces an ordering of the given types that serves as a
+// preference order for the result of unification of the given types.
+// The return value is a slice of indices into the given slice, and will
+// thus always be the same length as the given slice.
+//
+// The goal is that the most general of the given types will appear first
+// in the ordering. If there are uncomparable pairs of types in the list
+// then they will appear in an undefined order, and the unification pass
+// will presumably then fail.
+func sortTypes(tys []cty.Type) []int {
+        l := len(tys)
+
+        // First we build a graph whose edges represent "more general than",
+        // which we will then do a topological sort of.
+        edges := make([][]int, l)
+        for i := 0; i < (l - 1); i++ {
+                for j := i + 1; j < l; j++ {
+                        cmp := compareTypes(tys[i], tys[j])
+                        switch {
+                        case cmp < 0:
+                                edges[i] = append(edges[i], j)
+                        case cmp > 0:
+                                edges[j] = append(edges[j], i)
+                        }
+                }
+        }
+
+        // Compute the in-degree of each node
+        inDegree := make([]int, l)
+        for _, outs := range edges {
+                for _, j := range outs {
+                        inDegree[j]++
+                }
+        }
+
+        // The array backing our result will double as our queue for visiting
+        // the nodes, with the queue slice moving along this array until it
+        // is empty and positioned at the end of the array. Thus our visiting
+        // order is also our result order.
+        result := make([]int, l)
+        queue := result[0:0]
+
+        // Initialize the queue with any item of in-degree 0, preserving
+        // their relative order.
+        for i, n := range inDegree {
+                if n == 0 {
+                        queue = append(queue, i)
+                }
+        }
+
+        for len(queue) != 0 {
+                i := queue[0]
+                queue = queue[1:]
+                for _, j := range edges[i] {
+                        inDegree[j]--
+                        if inDegree[j] == 0 {
+                                queue = append(queue, j)
+                        }
+                }
+        }
+
+        return result
+}