branchcache: write branchmap in subset inheritance order

This way, we can guarantee a valid subset has been written before touching the
branchmap of another filter.

This is especially useful as we are bout to start deleting outdated branchmap
file.

mercurial/branchmap.py

@@ -166,7 +166,10 b' class BranchMapCache:'
 
     def write_delayed(self, repo):
         unfi = repo.unfiltered()
-        for filtername, cache in self._per_filter.items():
+        for filtername in repoviewutil.get_ordered_subset():
+            cache = self._per_filter.get(filtername)
+            if cache is None:
+                continue
             if cache._delayed:
                 if filtername is None:
                     repo = unfi

mercurial/utils/repoviewutil.py

@@ -6,6 +6,7 b''
 # 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' subsettable = {'
     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