mercurial/utils/repoviewutil.py
changeset 51487 1a9bdd0e1c44
parent 48875 6000f5b25c9b
--- a/mercurial/utils/repoviewutil.py	Fri Mar 08 15:06:54 2024 +0100
+++ b/mercurial/utils/repoviewutil.py	Fri Mar 08 15:50:15 2024 +0100
@@ -6,6 +6,7 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
+from .. import error
 
 ### Nearest subset relation
 # Nearest subset of filter X is a filter Y so that:
@@ -21,3 +22,30 @@
     b'served': b'immutable',
     b'immutable': b'base',
 }
+
+
+def get_ordered_subset():
+    """return a list of subset name from dependencies to dependents"""
+    _unfinalized = set(subsettable.values())
+    ordered = []
+
+    # the subset table is expected to be small so we do the stupid N² version
+    # of the algorithm
+    while _unfinalized:
+        this_level = []
+        for candidate in _unfinalized:
+            dependency = subsettable.get(candidate)
+            if dependency not in _unfinalized:
+                this_level.append(candidate)
+
+        if not this_level:
+            msg = "cyclic dependencies in repoview subset %r"
+            msg %= subsettable
+            raise error.ProgrammingError(msg)
+
+        this_level.sort(key=lambda x: x if x is not None else '')
+
+        ordered.extend(this_level)
+        _unfinalized.difference_update(this_level)
+
+    return ordered