Merge lp:~cr3/checkbox/0.13_resolver into lp:checkbox/0.13

[Marc Tardif]

[Javier Collado (javier.collado)]

Changes still past unit tests and work correctly with the same whitelists that were used to verify them in trunk. Besides this, no error or traceback is printed to the log file on a regular execution.

review: Approve

=== modified file 'checkbox/job.py'
--- checkbox/job.py	2012-06-20 20:34:40 +0000
+++ checkbox/job.py	2012-06-28 16:54:19 +0000
@@ -104,4 +104,18 @@
 class JobStore(MessageStore):
     """A job store which stores its jobs in a file system hierarchy."""
 
-    pass
+    def add(self, job):
+        # Return if the same job is already in the store
+        if list(self._find_matching_messages(name=job["name"])):
+            return
+
+        return super(JobStore, self).add(job)
+
+    def _find_matching_messages(self, **kwargs):
+        for filename in self._walk_messages():
+            message = self._read_message(filename,cache=True)
+            for key, value in kwargs.items():
+                if message.get(key) != value:
+                    break
+            else:
+                yield filename

=== modified file 'checkbox/lib/resolver.py'
--- checkbox/lib/resolver.py	2012-06-19 20:45:11 +0000
+++ checkbox/lib/resolver.py	2012-06-28 16:54:19 +0000
@@ -16,111 +16,130 @@
 # You should have received a copy of the GNU General Public License
 # along with Checkbox.  If not, see <http://www.gnu.org/licenses/>.
 #
+from collections import defaultdict, OrderedDict
+
+
 class Resolver:
     """
     Main class. Instantiate with the root directory of your items.
     """
 
-    def __init__(self, compare=None, key=None):
-        if compare is None:
-            compare = lambda a, b: cmp(a, b)
-        if key is None:
-            key = lambda k: k
-
-        self.compare = compare
-        self.key = key
-
-        # detect repeated resolution attempts - these indicate some circular dependency
-        self.reentrant_resolution = set()
-
-        # collect all items
-        self.items = {}
-
-        # for each item, keep a set of dependents and dependencies
-        self.dependents = {}
-        self.dependencies = {}
+    def __init__(self, key_func=None):
+        if key_func is None:
+            key_func = lambda k: k
+        self.key_func = key_func
+
+        self.items_added = OrderedDict()
+        self.depends = {}  # Dependencies
+        self.rdepends = defaultdict(list)  # Reverse dependencies
+
+        # Data used in _resolve method
+        self.items = None
+        self.items_blocked = None
+        self.resolved = False
 
     def add(self, item, *dependencies):
-        key = self.key(item)
-        if key in self.items:
-            raise Exception, "%s: key already exists" % key
-        self.items[key] = item
-
-        self.dependencies[key] = set(dependencies)
-
-    def remove(self, item):
-        key = self.key(item)
-        del self.items[key]
-        del self.dependencies[key]
-
-    def resolve(self, item, found=None):
-        """
-        the center piece.
-        recursively resolve dependencies of scripts
-        return them as a flat list, sorted according to ancestral relationships
-        """
-        key = self.key(item)
-        resolved = self.dependents.get(key, None)
-        if resolved is not None:
-            return resolved
-
-        if key not in self.items:
-            msg = "no dependencies found for %s" % key
-            if found:
-                msg += " while resolving %s" % found
-            raise Exception, msg
-
-        dependencies = self.dependencies.get(key, set())
-        resolved = set()
-
+        """
+        Add item as pending
+        """
+        key = self.key_func(item)
+        if key in self.items_added:
+            raise Exception("%s: key already exists" % key)
+
+        # Dependencies bookkeeping
+        self.items_added[key] = item
+        self.depends[key] = list(dependencies)
         for dependency in dependencies:
-            resolution_step = (key, dependency)
-            if resolution_step in self.reentrant_resolution:
-                if found:
-                    scapegoat = found
-                else:
-                    scapegoat = dependency
-                raise Exception, "circular dependency involving %s and %s" % (key, scapegoat)
-            # add resolution
-            self.reentrant_resolution.add(resolution_step)
-            # and its dependencies, if any
-            if dependency in self.items:
-                resolved.update(self.resolve(self.items[dependency], found=key))
-
-        # now it's time for sorting hierarchically... Since circular dependencies are excluded,
-        # ancestors will always have fewer dependencies than descendants, so sorting by the
-        # number of dependencies will give the desired order.
-        resolved = sorted(resolved, key=lambda x: len(self.dependents[x]))
-        resolved.append(key)
-        self.dependents[key] = resolved
-
-        return resolved
+            self.rdepends[dependency].append(key)
+
+        # Circular dependencies check
+        def circular_dependencies(node):
+            seen = circular_dependencies.seen
+            for dependency in self.depends.get(node, []):
+                if key == dependency:
+                    raise Exception("circular dependency involving "
+                                    "%s and %s" % (key, node))
+                if dependency in seen:
+                    continue
+                seen.add(dependency)
+                circular_dependencies(dependency)
+        circular_dependencies.seen = set((key,))
+        circular_dependencies(key)
+
+        # Resolve on next call to get_dependencies/get_dependents
+        self.resolved = False
+
+    def _resolve(self):
+        """
+        Work through the pending items and reorder them properly
+        """
+        if self.resolved:
+            return
+
+        # Initialize internal ordering data
+        self.items = OrderedDict()
+        self.items_blocked = {}
+
+        def add_unblocked(key):
+            """Add items that have been unblocked"""
+            for dependent in self.rdepends[key]:
+                if not dependent in self.items_blocked:
+                    continue
+
+                unblocked = all(dependency in self.items
+                                for dependency in self.depends[dependent]
+                                if dependency in self.items_added)
+                if unblocked:
+                    item = self.items_blocked[dependent]
+                    self.items[dependent] = item
+                    del self.items_blocked[dependent]
+
+                    add_unblocked(dependent)
+
+        for key, item in self.items_added.items():
+            # Avoid adding an item until all dependencies have been met
+            blocked = any(dependency not in self.items
+                          for dependency in self.depends[key]
+                          if dependency in self.items_added)
+
+            if blocked:
+                self.items_blocked[key] = item
+            else:
+                self.items[key] = item
+                add_unblocked(key)
+
+        if self.items_blocked:
+            raise Exception('There are {} items blocked: {}'
+                            .format(len(self.items_blocked),
+                                    ', '.join(self.items_blocked.keys())))
+
+        # Don't resolve again on next call to get_dependencies/get_dependents
+        # unless a new item is added
+        self.resolved = True
 
     def get_dependencies(self, item):
-        return [self.items[r] for r in self.resolve(item)]
+        """
+        Return a list of the dependencies for a given item
+        """
+        self._resolve()
+        key = self.key_func(item)
+        if key not in self.depends:
+            msg = "no dependencies found for %s" % key
+            raise Exception(msg)
+
+        dependencies = self.depends[key] + [key]
+
+        return dependencies
 
     def get_dependents(self, item=None):
-        dependents = []
-        if item:
-            # Immediate dependents
-            key = self.key(item)
-            all_dependents = filter(
-                lambda x: key in self.resolve(x)[:-1],
-                self.items.itervalues())
-            dependents = filter(
-                lambda x: self.key(self.get_dependencies(x)[-2]) == key,
-                all_dependents)
-        else:
-            # First level of dependents
-            dependents = filter(lambda x: len(self.resolve(x)) == 1, self.items.itervalues())
-
-        index = 0
-        dependents = sorted(dependents, key=self.key)
-        while index < len(dependents):
-            sub_dependents = self.get_dependents(dependents[index])
-            if sub_dependents:
-                dependents[index+1:index+1] = sub_dependents
-                index += len(sub_dependents)
-            index += 1
-
-        return dependents
+        """
+        Return a list of the items that depend on the given one
+        or the whole list of items topologically ordered
+        """
+        self._resolve()
+        items = list(self.items.values())
+        if item is not None:
+            index = items.index(item)
+            items = items[index + 1:]
+
+        return items

=== modified file 'checkbox/lib/tests/resolver.py'
--- checkbox/lib/tests/resolver.py	2009-07-22 03:48:49 +0000
+++ checkbox/lib/tests/resolver.py	2012-06-28 16:54:19 +0000
@@ -22,71 +22,62 @@
 
 
 class ResolverTest(unittest.TestCase):
+    def setUp(self):
+        self.resolver = Resolver()
+
     def test_dependencies_none(self):
-        resolver = Resolver()
         try:
-            resolver.get_dependencies('a')
-        except Exception, error:
+            self.resolver.get_dependencies('a')
+        except Exception as error:
             self.assertTrue(error.args[0].startswith('no dependencies'))
         else:
             self.fail('non existing element accepted by resolver')
 
     def test_dependencies_one_level(self):
-        resolver = Resolver()
-        resolver.add('a')
+        self.resolver.add('a')
 
-        results = resolver.get_dependencies('a')
-        self.assertTrue(len(results) == 1)
-        self.assertTrue(results[0] == 'a')
+        results = self.resolver.get_dependencies('a')
+        self.assertListEqual(results, ['a'])
 
     def test_dependencies_two_level(self):
-        resolver = Resolver()
-        resolver.add('a')
-        resolver.add('b', 'a')
+        self.resolver.add('a')
+        self.resolver.add('b', 'a')
 
-        results = resolver.get_dependencies('b')
-        self.assertTrue(len(results) == 2)
-        self.assertTrue(results[0] == 'a')
-        self.assertTrue(results[1] == 'b')
+        results = self.resolver.get_dependencies('b')
+        self.assertListEqual(results, ['a', 'b'])
 
     def test_dependencies_multiple(self):
-        resolver = Resolver()
-        resolver.add('a')
-        resolver.add('b')
-        resolver.add('c', 'a', 'b')
+        self.resolver.add('a')
+        # A appears as a dependency multiple times
+        # in b and c, but isn't a circular dependency
+        self.resolver.add('b', 'a')
+        self.resolver.add('c', 'a', 'b')
 
-        results = resolver.get_dependencies('c')
-        self.assertTrue(len(results) == 3)
-        self.assertTrue(results[0] == 'a')
-        self.assertTrue(results[1] == 'b')
-        self.assertTrue(results[2] == 'c')
+        results = self.resolver.get_dependencies('c')
+        self.assertListEqual(results, ['a', 'b', 'c'])
 
     def test_dependencies_circular(self):
-        resolver = Resolver()
-        resolver.add('a', 'b')
-        resolver.add('b', 'a')
         try:
-            resolver.get_dependencies('a')
-        except Exception, error:
+            self.resolver.add('a', 'b')
+            self.resolver.add('b', 'a')
+            self.resolver.get_dependencies('a')
+        except Exception as error:
             self.assertTrue(error.args[0].startswith('circular dependency'))
         else:
             self.fail('circular dependency not detected')
 
     def test_dependents_none(self):
-        resolver = Resolver()
-        resolver.add('a')
+        self.resolver.add('a')
 
-        results = resolver.get_dependents('a')
+        results = self.resolver.get_dependents('a')
         self.assertTrue(len(results) == 0)
 
     def test_dependents_one(self):
-        resolver = Resolver()
-        resolver.add('a')
-        resolver.add('b', 'a')
+        self.resolver.add('a')
+        self.resolver.add('b', 'a')
 
-        results = resolver.get_dependents('a')
-        self.assertTrue(len(results) == 1)
-        self.assertTrue(results[0] == 'b')
+        results = self.resolver.get_dependents('a')
+        self.assertListEqual(results, ['b'])
 
     def test_dependents_two(self):
         resolver = Resolver()
@@ -95,6 +86,13 @@
         resolver.add('c', 'b')
 
         results = resolver.get_dependents('a')
-        self.assertTrue(len(results) == 2)
-        self.assertTrue(results[0] == 'b')
-        self.assertTrue(results[1] == 'c')
+        self.assertListEqual(results, ['b', 'c'])
+
+    def test_multiple_resolve_steps(self):
+        self.resolver.add('a', 'b')
+        results = self.resolver.get_dependents()
+        self.assertListEqual(results, ['a'])
+
+        self.resolver.add('b')
+        results = self.resolver.get_dependents()
+        self.assertListEqual(results, ['b', 'a'])

=== modified file 'debian/changelog'
--- debian/changelog	2012-06-25 19:26:57 +0000
+++ debian/changelog	2012-06-28 16:54:19 +0000
@@ -15,6 +15,8 @@
 
   [Javier Collado]
   * Make sure that jobs are topologically ordered (LP: #990075)
+  * Keep job ordering as close to whitelist as possible (LP: #1017951)
+  * Fixed detection of circular references in resolver.
 
   [Jeff Lane]
   * Bumped revision to 0.13.8
@@ -47,6 +49,9 @@
   * [FEATURE] checkbox_gtk/gtk_interface.py: Capture ESC keypresses so that
     Checkbox doesn't close/die when user presses ESC.
 
+  [Marc Tardif]
+  * Fixed duplicate jobs appearing in the store when rerunning jobs.
+
   [Sylvain Pineau]
   * [FEATURE] jobs/info.txt.in: added new attachments, lspci -vvnnQ and
     lsusb -vv and ensure outputs of lscpi, lsusb and dmidecode return UTF8.

=== modified file 'plugins/jobs_info.py'
--- plugins/jobs_info.py	2012-06-21 17:08:04 +0000
+++ plugins/jobs_info.py	2012-06-28 16:54:19 +0000
@@ -183,7 +183,7 @@
 
         if not self.check_ordered_messages(messages):
             old_message_names = [message["name"] + "\n" for message in messages]
-            resolver = Resolver(key=lambda m: m["name"])
+            resolver = Resolver(key_func=lambda m: m["name"])
             for message in messages:
                 resolver.add(
                     message, *message.get("depends", []))