Repository: Microsoft/thrifty (kotlin)

Issue:
Schema should sort constants in dependency order
"Dependency order" meaning a sort of reverse topological sort - for any constant C in a schema's `constants` list, all constants referenced by C are guaranteed to precede it in the list.  This removes the need for codegen to figure out what order to emit things in.

Pull request:
Fixes #500

Patch:
diff --git a/thrifty-schema/src/main/kotlin/com/microsoft/thrifty/schema/Schema.kt b/thrifty-schema/src/main/kotlin/com/microsoft/thrifty/schema/Schema.kt
index 3db67a808..40f3abe7b 100644
--- a/thrifty-schema/src/main/kotlin/com/microsoft/thrifty/schema/Schema.kt
+++ b/thrifty-schema/src/main/kotlin/com/microsoft/thrifty/schema/Schema.kt
@@ -96,7 +96,7 @@ class Schema {
         this.unions = unions
         this.exceptions = exceptions
         this.enums = enums
-        this.constants = constants
+        this.constants = sortConstantsInDependencyOrder(constants)
         this.typedefs = typedefs
         this.services = services
     }
@@ -106,7 +106,7 @@ class Schema {
         this.unions = builder.unions
         this.exceptions = builder.exceptions
         this.enums = builder.enums
-        this.constants = builder.constants
+        this.constants = sortConstantsInDependencyOrder(builder.constants)
         this.typedefs = builder.typedefs
         this.services = builder.services
     }
@@ -214,4 +214,32 @@ class Schema {
         result = 31 * result + services.hashCode()
         return result
     }
+
+    /**
+     * Returns a copy of the collection of [Constants][Constant] sorted in dependency
+     * order, suitable for generating code in the order presented.
+     *
+     * Dependency-order is a reverse topological sort, and  here means that for any
+     * given constant in the list, all constants on which it depends (i.e. that it
+     * references) come before it in order.  For example:
+     *
+     * ```
+     * // given this thrift
+     * const list<string> STRS = [A, B];
+     * const string A = "a";
+     * const string B = "b";
+     *
+     * // A reverse-topological-sort of these constants would be:
+     * [A, B, STRS]
+     *
+     * // A naive code-generation strategy of emitting constants in the order
+     * // in which they appear will work as expected:
+     * val A: String = "a"
+     * val B: String = "b"
+     * val STRS: List<String> = listOf(A, B)
+     * ```
+     */
+    private fun sortConstantsInDependencyOrder(constants: List<Constant>): List<Constant> {
+        return SortUtil.inDependencyOrder(constants) { it.referencedConstants }
+    }
 }
diff --git a/thrifty-schema/src/main/kotlin/com/microsoft/thrifty/schema/SortUtil.kt b/thrifty-schema/src/main/kotlin/com/microsoft/thrifty/schema/SortUtil.kt
new file mode 100644
index 000000000..a02214387
--- /dev/null
+++ b/thrifty-schema/src/main/kotlin/com/microsoft/thrifty/schema/SortUtil.kt
@@ -0,0 +1,66 @@
+/*
+ * Thrifty
+ *
+ * Copyright (c) Microsoft Corporation
+ *
+ * All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the License);
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * THIS CODE IS PROVIDED ON AN  *AS IS* BASIS, WITHOUT WARRANTIES OR
+ * CONDITIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING
+ * WITHOUT LIMITATION ANY IMPLIED WARRANTIES OR CONDITIONS OF TITLE,
+ * FITNESS FOR A PARTICULAR PURPOSE, MERCHANTABLITY OR NON-INFRINGEMENT.
+ *
+ * See the Apache Version 2.0 License for specific language governing permissions and limitations under the License.
+ */
+package com.microsoft.thrifty.schema
+
+internal object SortUtil {
+    fun <T> inDependencyOrder(nodes: List<T>, getRefs: (T) -> List<T>): List<T> {
+        // KAAAAAAAAAAAAAAHHHHHHNNNNNNNNNNNN!!!!!!!!! ('s algorithm)
+
+        // A mapping of nodes to the number of other nodes referencing them
+        val references = LinkedHashMap<T, Int>()
+        val roots = ArrayDeque<T>()
+
+        // ArrayDeque implements List and allows efficient insertion at the head,
+        // allowing us to avoid a '.reversed()' call.
+        val result = ArrayDeque<T>()
+
+        for (n in nodes) {
+            // We need to ensure that every node has a refcount
+            references.computeIfAbsent(n) { 0 }
+
+            for (r in getRefs(n)) {
+                // Every node r is referenced by the current node n, so
+                // we can increment its refcount
+                references.compute(r) { _, maybeCount -> (maybeCount ?: 0) + 1 }
+            }
+        }
+
+        for ((n, numRefs) in references) {
+            if (numRefs == 0) {
+                roots.add(n)
+            }
+        }
+
+        while (roots.isNotEmpty()) {
+            val n = roots.removeFirst()
+            result.addFirst(n)
+
+            for (r in getRefs(n)) {
+                val numRefs = references.compute(r) { _, numRefs -> numRefs!! - 1 }
+                if (numRefs == 0) {
+                    roots.add(r)
+                }
+            }
+        }
+
+        return result
+    }
+}
\ No newline at end of file


Test patch:
diff --git a/thrifty-schema/src/test/kotlin/com/microsoft/thrifty/schema/LoaderTest.kt b/thrifty-schema/src/test/kotlin/com/microsoft/thrifty/schema/LoaderTest.kt
index 676798fe7..4cfa8d532 100644
--- a/thrifty-schema/src/test/kotlin/com/microsoft/thrifty/schema/LoaderTest.kt
+++ b/thrifty-schema/src/test/kotlin/com/microsoft/thrifty/schema/LoaderTest.kt
@@ -1022,6 +1022,26 @@ class LoaderTest {
         strs.referencedConstants.map { it.name} shouldBe listOf("A", "B")
     }
 
+    @Test
+    fun topologicallySortsConstants() {
+        val thrift = """
+            struct Node {
+              1: required list<Node> n;
+            }
+            
+            const Node A = { "n": [F] }
+            const Node B = { "n": [A] }
+            const Node C = { "n": [ ] }
+            const Node D = { "n": [B, C] }
+            const Node E = { "n": [C, F] }
+            const Node F = { "n": [ ] }
+        """.trimIndent()
+
+        val schema = load(thrift)
+        val order = schema.constants.map { it.name }
+        order shouldBe listOf("F", "A", "C", "B", "E", "D")
+    }
+
     @Test
     fun unionWithOneDefaultValue() {
         val thrift = """
diff --git a/thrifty-schema/src/test/kotlin/com/microsoft/thrifty/schema/SortUtilTest.kt b/thrifty-schema/src/test/kotlin/com/microsoft/thrifty/schema/SortUtilTest.kt
new file mode 100644
index 000000000..12825dc50
--- /dev/null
+++ b/thrifty-schema/src/test/kotlin/com/microsoft/thrifty/schema/SortUtilTest.kt
@@ -0,0 +1,120 @@
+/*
+ * Thrifty
+ *
+ * Copyright (c) Microsoft Corporation
+ *
+ * All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the License);
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * THIS CODE IS PROVIDED ON AN  *AS IS* BASIS, WITHOUT WARRANTIES OR
+ * CONDITIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING
+ * WITHOUT LIMITATION ANY IMPLIED WARRANTIES OR CONDITIONS OF TITLE,
+ * FITNESS FOR A PARTICULAR PURPOSE, MERCHANTABLITY OR NON-INFRINGEMENT.
+ *
+ * See the Apache Version 2.0 License for specific language governing permissions and limitations under the License.
+ */
+package com.microsoft.thrifty.schema
+
+import io.kotest.matchers.Matcher
+import io.kotest.matchers.MatcherResult
+import io.kotest.matchers.should
+import io.kotest.matchers.shouldBe
+import io.kotest.matchers.shouldNot
+import org.junit.jupiter.api.Test
+
+class SortUtilTest {
+    class Node(
+        val label: String
+    ) {
+        var refs: MutableList<Node> = mutableListOf()
+
+        override fun equals(other: Any?): Boolean {
+            return other !== null && other is Node && label == other.label
+        }
+
+        override fun hashCode(): Int {
+            return label.hashCode()
+        }
+
+        override fun toString(): String {
+            return label
+        }
+    }
+
+    @Test
+    fun sortsInDependencyOrder() {
+        val nodes = sort("""
+            A -> F
+            B -> A
+            C
+            D -> B, C
+            E -> C, F
+            F
+        """.trimIndent())
+
+        nodes should beDependencySorted()
+    }
+
+    private fun beDependencySorted(): DependencyOrderMatcher {
+        return DependencyOrderMatcher()
+    }
+
+    private class DependencyOrderMatcher : Matcher<Collection<Node>> {
+        override fun test(value: Collection<Node>): MatcherResult {
+            val seen = mutableSetOf<Node>()
+            var isSorted = true
+
+            outer@for (node in value) {
+                for (ref in node.refs) {
+                    if (ref !in seen) {
+                        isSorted = false
+                        break@outer
+                    }
+                }
+
+                seen.add(node)
+            }
+
+            return MatcherResult(
+                passed = isSorted,
+                failureMessageFn = { "$value should have been topologically sorted" },
+                negatedFailureMessageFn = { "$value should not have been topologically sorted" })
+        }
+    }
+
+    private fun sort(graph: String): List<Node> {
+        val nodes = parseNodes(graph)
+        return SortUtil.inDependencyOrder(nodes) { it.refs }
+    }
+
+    private fun parseNodes(graph: String): List<Node> {
+        val nodes = LinkedHashMap<String, Node>()
+        for (line in graph.lineSequence()) {
+            if (line.isEmpty()) {
+                continue
+            }
+            val arrowIndex = line.indexOf("->")
+            if (arrowIndex == -1) {
+                // Line is a node with no edges
+                val label = line.trim()
+                nodes.computeIfAbsent(label) { Node(label) }
+                continue
+            }
+
+            val label = line.substring(0, arrowIndex).trim()
+            val edgesText = line.substring(arrowIndex + "->".length).trim()
+            val edgeLabels = edgesText.split(",").map(String::trim)
+            val node = nodes.computeIfAbsent(label) { Node(label) }
+            for (refLabel in edgeLabels) {
+                val ref = nodes.computeIfAbsent(refLabel) { Node(refLabel) }
+                node.refs.add(ref)
+            }
+        }
+        return nodes.toList().map { it.second }
+    }
+}
\ No newline at end of file