From c62c41bc8aba632439dc19848d395180c4ad8e19 Mon Sep 17 00:00:00 2001
From: "Luke T. Shumaker" <lukeshu@lukeshu.com>
Date: Mon, 14 Apr 2025 08:28:19 -0600
Subject: lib9p_core: Redefine topo_sort() to be stable and prettier

---
 lib9p/core_gen/idlutil.py | 40 +++++++++++++++++++++++++++++-----------
 1 file changed, 29 insertions(+), 11 deletions(-)

(limited to 'lib9p/core_gen/idlutil.py')

diff --git a/lib9p/core_gen/idlutil.py b/lib9p/core_gen/idlutil.py
index 9843675..e92839a 100644
--- a/lib9p/core_gen/idlutil.py
+++ b/lib9p/core_gen/idlutil.py
@@ -4,7 +4,6 @@
 # SPDX-License-Identifier: AGPL-3.0-or-later
 
 import enum
-import graphlib
 import typing
 
 import idl
@@ -22,21 +21,40 @@ __all__ = [
 
 
 def topo_sorted(typs: list[idl.UserType]) -> typing.Iterable[idl.UserType]:
-    ts: graphlib.TopologicalSorter[idl.UserType] = graphlib.TopologicalSorter()
+    ret: list[idl.UserType] = []
+    struct_ord: dict[str, int] = {}
+
+    def get_struct_ord(typ: idl.Struct) -> int:
+        nonlocal struct_ord
+        if typ.typname not in struct_ord:
+            deps = [
+                get_struct_ord(member.typ)
+                for member in typ.members
+                if isinstance(member.typ, idl.Struct)
+            ]
+            if len(deps) == 0:
+                struct_ord[typ.typname] = 0
+            else:
+                struct_ord[typ.typname] = 1 + max(deps)
+        return struct_ord[typ.typname]
+
     for typ in typs:
         match typ:
             case idl.Number():
-                ts.add(typ)
+                ret.append(typ)
             case idl.Bitfield():
-                ts.add(typ)
+                ret.append(typ)
             case idl.Struct():  # and idl.Message():
-                deps = [
-                    member.typ
-                    for member in typ.members
-                    if not isinstance(member.typ, idl.Primitive)
-                ]
-                ts.add(typ, *deps)
-    return ts.static_order()
+                _ = get_struct_ord(typ)
+    for _ord in sorted(set(struct_ord.values())):
+        for typ in typs:
+            if not isinstance(typ, idl.Struct):
+                continue
+            if struct_ord[typ.typname] != _ord:
+                continue
+            ret.append(typ)
+    assert len(ret) == len(typs)
+    return ret
 
 
 # walk() #######################################################################
-- 
cgit v1.2.3-2-g168b