Fix MP sorting with tests.

2 files changed, 100 insertions, 31 deletions

diff --git a/bileto/worker/merge.py b/bileto/worker/merge.py
index 22179a1..f3c76e3 100644
--- a/bileto/worker/merge.py
+++ b/bileto/worker/merge.py
@@ -6,7 +6,7 @@ Everything to do with handling of launchpad MPs.
 from os import environ
 from asyncio import coroutine
 from contextlib import suppress
-from collections import defaultdict
+from collections import defaultdict, OrderedDict
 
 from lazr.restfulclient.errors import NotFound
 
@@ -48,26 +48,6 @@ def get_prop(merge, prefix):
         getattr(merge, prefix + '_git_path'))
 
 
-class SortedMPList(list):
-    """A list that sorts MPs by prerequisite branches while appending."""
-
-    def __init__(self):
-        super().__init__()
-        self.prereqs = {}
-
-    def append(self, item):
-        """Append item in the correct order."""
-        self.prereqs[get_link(item, 'prerequisite')] = item
-        if self:
-            source = get_link(item, 'source')
-            if source in self.prereqs:
-                index = self.index(self.prereqs[source])
-                self.insert(index, item)
-                log.vars(locals(), 'Inserting sortedly!')
-                return
-        super().append(item)
-
-
 @coroutine
 def get_source(result, targets, trunk, merges):
     """Arrange trunk name and merges list by source package name."""
@@ -117,6 +97,38 @@ def identify_approvers(merge):
     return ''
 
 
+def topo_sort(merges):
+    """Sort merges by their prerequisites.
+
+    A list of launchpad merges is technically a directed acyclic graph. Each
+    merge is a node in the graph and can define 0 or 1 prerequisites, which are
+    graph arcs. This algorithm sorts them according to these rules:
+
+    1. Edgeless nodes have stable ordering; merges with no prereq don't move
+    2. Arcs appear before their nodes, but not necessarily immediately before.
+    3. No nodes are duplicated.
+    """
+    objects = {}  # maps stringified merges back to merge objects
+    graph = OrderedDict()  # maps stringified merges to stringified prereqs
+    ordered = []  # holds the final ordering
+    for merge in merges:
+        node = get_link(merge, 'source')
+        arc = get_link(merge, 'prerequisite')
+        objects[node] = merge
+        graph[node] = arc
+    arcs = graph.values()
+
+    def follow_the_arcs(arc):
+        """Recurse down the tree from root to leaf nodes."""
+        obj = objects.get(arc)
+        if obj and obj not in ordered:
+            follow_the_arcs(graph.get(arc))
+            ordered.append(obj)
+
+    log.debug([follow_the_arcs(node) for node in graph if node not in arcs])
+    return ordered
+
+
 class Merge(Package):
     """Define the steps unique to packages built from merge proposals."""
     all_mps = {}
@@ -127,7 +139,7 @@ class Merge(Package):
     def prepare_all(cls, urls):
         """Process MPs for silo config."""
         log.info('Determining source package names from MPs...')
-        by_trunk = defaultdict(SortedMPList)
+        by_trunk = defaultdict(list)
         for url in urls:
             try:
                 assert url.startswith(lp.MP_ROOT)
@@ -150,6 +162,7 @@ class Merge(Package):
                     COMMASPACE.join(sorted(
                         COLON.join(trunk) if trunk[1] else trunk[0]
                         for trunk in trunks))))
+        cls.all_mps = {src: topo_sort(mps) for src, mps in cls.all_mps.items()}
         return cls.all_mps
 
     @staticmethod
diff --git a/tests/test_worker_manager.py b/tests/test_worker_manager.py
index c7a06af..662df90 100644
--- a/tests/test_worker_manager.py
+++ b/tests/test_worker_manager.py
@@ -6,7 +6,6 @@ Test the package manager class.
 from os.path import join
 from subprocess import PIPE
 from asyncio import coroutine
-from collections import defaultdict
 from unittest.mock import Mock, patch, call
 
 from lazr.restfulclient.errors import BadRequest, ClientError, Unauthorized
@@ -23,10 +22,10 @@ from bileto.worker.manager import Manager, Merge, Manual, Package, Revert
 
 DIFF_ENV = dict(INCLUDES='')
 MAKE_PPA_ENV = dict(REQUEST_URL_ROOT='https://ppa/thing')
-MERGES = fake_subproc(0, [(b'ofono', b'')] * 5)
+MERGES = fake_subproc(0, [(b'ofono', b'')] * 60)
 POST_DIFF = fake_subproc(0, [(b'swift/diff (9000 lines)', b'')])
 POST_NUKE = fake_subproc(0, [(b'', b'')])
-MOCKS = defaultdict(Mock)
+MOCKS = {}
 SLASH = '/'
 EMPTY = ''
 N = '\n'
@@ -40,6 +39,7 @@ def mp(num):
 def mp_obj(num, prereq=None, target=None):
     """Return an MP mock."""
     num = str(num)[-1]
+    MOCKS.setdefault(num, Mock(name=num))
     mock = MOCKS[num]
     mock.source_branch_link = mock.web_link = mp(num)
     mock.target_branch.display_name = target or 'lp:ofono'
@@ -47,8 +47,13 @@ def mp_obj(num, prereq=None, target=None):
     mock.source_git_path = None
     mock.target_git_repository = None
     mock.target_git_path = None
-    if prereq:
+    mock.prerequisite_branch_link = None
+    mock.prerequisite_git_repository_link = None
+    mock.prerequisite_git_path = None
+    if prereq is True:
         mock.prerequisite_branch_link = mp(int(num) + 1)
+    else:
+        mock.prerequisite_branch_link = mp(prereq)
     return mock
 
 
@@ -60,21 +65,72 @@ class ManagerTestCase(WorkerTestCase):
     def test_manager_merges(self, load):
         """Ensure manager can instantiate merges."""
         load.side_effect = mp_obj
-        ticket = Mock(merge_proposals_list=[mp(1), mp(2), mp(3)])
+        ticket = Mock(merge_proposals_list=[mp(1), mp(2), mp(3), mp(4), mp(5)])
         manager = Manager(ticket)
         self.assertEqual(manager.merges(), dict(ofono=[
-            mp_obj(1), mp_obj(2), mp_obj(3),
+            mp_obj(1), mp_obj(2), mp_obj(3), mp_obj(4), mp_obj(5),
         ]))
 
     @patch('bileto.worker.merge.lp.load')
     @patch('bileto.worker.vcs.create_subprocess_exec', MERGES)
     def test_manager_merges_sorted(self, load):
-        """Ensure manager can sort merges."""
+        """Ensure manager can sort merges totally backwards."""
         load.side_effect = lambda x: mp_obj(x, prereq=True)
-        ticket = Mock(merge_proposals_list=[mp(1), mp(2), mp(3)])
+        ticket = Mock(merge_proposals_list=[mp(1), mp(2), mp(3), mp(4)])
+        manager = Manager(ticket)
+        self.assertEqual(manager.merges(), dict(ofono=[
+            mp_obj(4), mp_obj(3), mp_obj(2), mp_obj(1),
+        ]))
+
+    @patch('bileto.worker.merge.lp.load')
+    @patch('bileto.worker.vcs.create_subprocess_exec', MERGES)
+    def test_manager_merges_sorted_2(self, load):
+        """Ensure manager can sort merges with first and last transposed."""
+        load.side_effect = lambda x: mp_obj(x, prereq=True)
+        ticket = Mock(merge_proposals_list=[mp(1), mp(3), mp(2), mp(4)])
+        manager = Manager(ticket)
+        self.assertEqual(manager.merges(), dict(ofono=[
+            mp_obj(4), mp_obj(3), mp_obj(2), mp_obj(1),
+        ]))
+
+    @patch('bileto.worker.merge.lp.load')
+    @patch('bileto.worker.vcs.create_subprocess_exec', MERGES)
+    def test_manager_merges_sorted_3(self, load):
+        """Ensure manager can sort merges from a jumble."""
+        load.side_effect = lambda x: mp_obj(x, prereq=True)
+        ticket = Mock(merge_proposals_list=[mp(1), mp(2), mp(4), mp(3)])
+        manager = Manager(ticket)
+        self.assertEqual(manager.merges(), dict(ofono=[
+            mp_obj(4), mp_obj(3), mp_obj(2), mp_obj(1),
+        ]))
+
+    @patch('bileto.worker.merge.lp.load')
+    @patch('bileto.worker.vcs.create_subprocess_exec', MERGES)
+    def test_manager_merges_sorted_4(self, load):
+        """Ensure manager respects pre-sorted merges."""
+        load.side_effect = lambda x: mp_obj(x, prereq=True)
+        ticket = Mock(merge_proposals_list=[mp(4), mp(3), mp(2), mp(1)])
+        manager = Manager(ticket)
+        self.assertEqual(manager.merges(), dict(ofono=[
+            mp_obj(4), mp_obj(3), mp_obj(2), mp_obj(1),
+        ]))
+
+    @patch('bileto.worker.merge.lp.load')
+    @patch('bileto.worker.vcs.create_subprocess_exec', MERGES)
+    def test_manager_merges_sorted_5(self, load):
+        """Ensure manager doesn't duplicate MPs."""
+        objects = [
+            mp_obj(5),
+            mp_obj(4, prereq=5),
+            mp_obj(3, prereq=4),
+            mp_obj(1, prereq=4),
+            mp_obj(2, prereq=4),
+        ]
+        load.side_effect = lambda _: objects.pop()
+        ticket = Mock(merge_proposals_list=[mp(2), mp(1), mp(5), mp(3), mp(4)])
         manager = Manager(ticket)
         self.assertEqual(manager.merges(), dict(ofono=[
-            mp_obj(3), mp_obj(2), mp_obj(1),
+            mp_obj(5), mp_obj(4), mp_obj(2), mp_obj(1), mp_obj(3),
         ]))
 
     @patch('bileto.worker.merge.lp.load')