Merge lp:~javier.collado/checkbox/bug990075 into lp:checkbox

[Javier Collado]

This change fixes the job ordering problem found bug990075 as follows:

- Removes the code in JobStore that takes of ordering and duplicate removal
The JobStore was expected to order jobs based on their dependencies when added one by one. This wasn't very efficient because the store had to perform the reordering every time a job was added and it was confusing to the programmer because it wasn't clear the algorithm being used.

- Adds topological sorting to the jobs_info.py plugin
The jobs_info.py plugin contains the whitelist ordering code, so it makes sense to take care of reordering jobs right there also to meet dependencies. Since whitelist ordering might be applied as well, the strategy used is check if the whitelist already provides a valid topological sort. If the check isn't successful, then the sorting is performed once for the whole graph using depth first search before adding any job to the JobStore.

One more thing to consider is that when test suites are added to the job store, "report-message" events are triggered with messages that contain updated information for test cases (like which one is their test suite). Before this fix, a new message was added to the list of messages and the JobStore took care of removing duplicates. Now, since the jobs are already ordered, they are updated instead to preserve their ordering in the jobs_info.py plugin prior to adding jobs to the JobStore.

[Javier Collado (javier.collado)]

One pending thing to check is what happens in the presence of circular dependencies.
Since depth-first search stops when a job has already been inspected, I don't expect
any side effect like and infinite loop.

Looking at the code, it seems that they're already handled in the suites_prompt.py plugin
using checkbox.lib.resolver.Resolver, which actually seems to address topological order,
but I didn't use it because it wasn't used either in the original code (I guess there was
a good reason for that).

Hence, what should happen is that an exception is raised in checkbox.lib.resolver.Resolver
as it would have happened in the past.

[Brendan Donegan (brendan-donegan)]

I found that running the client-cert.whitelist results in the mediacard tests (before suspend) being run after the suspend test, even though they are listed before it in the whitelist.

review: Needs Fixing

[Javier Collado (javier.collado)]

The problem is that there are some dependencies that are not explicitly set in the jobs.

For example, there are many jobs that are expected to be executed before suspend/suspend_advanced, but they haven't been added as a dependency because that will make its list of dependencies really long.

One way to workaround this issue would be to reorder the whitelist directly to make sure that the ordering is the expected one, but this will also require to be reviewed every time a job is added, so it will be easy to break the whitelist inadvertently.

Ideally, there should be some midpoint in which a whitelist that is ordered almost nicely can be reordered without breaking any of these hidden dependencies against the suspend/suspend_advanced job.

[lp:~javier.collado/checkbox/bug990075]

1377. By Javier Collado on 2012-05-07

Implemented new algorithm to order jobs

The new algorithm no longer uses a standard topological ordering algorithm
because of the lack of information available in job descriptions. For example,
most of the jobs are expected to be executed before suspend/suspend_advanced,
but they are not listed as a dependency for this job. Instead, just the jobs
that are expected to be executed after suspend depend on
suspend/suspend_advanced.

To address this problem, it's assumed that the whitelist is already almost
fine, but there are just a few test cases that are out of order (if this is not
the case, the final ordering will probably not be valid). After that, a list of
dependencies and reverse dependencies is created and an attempt to order all
the messages in the whitelist one by one is made. If the order in the whitelist
is fine, then the messsage is added to the list of sorted jobs, if that's not
the case, the message is cached and added as soon as the missing dependencies
have been added as well.

[Javier Collado (javier.collado)]

The reordering method has been changed as explained in the commite message for rev. 1377.

The following test suites have been tested: client-cert whitelist, smoke and the one attached to the bug and they look good.

review: Needs Resubmitting

[Brendan Donegan (brendan-donegan)]

This sounds more like what I assumed would happen. I'll give it a test in a little while and try to merge it today

[lp:~javier.collado/checkbox/bug990075]

1378. By Javier Collado on 2012-06-12

Added message to let the user know what's the final ordering being used

1379. By Javier Collado on 2012-06-12

Updated whitelist error message to display detailed information properly

This change needs the fix for bug1012052 to work fine.

[Marc Tardif (cr3)]

Since the time this branch was first proposed for merging, the trunk has been converted to Python 3. I've just noticed that this branch uses the cmp keyword argument to the sorted function, which is no longer supported in Python 3. And, there might be other constructs that are no longer supported. So, I'm setting this branch as "Needs Fixing" just so that it's at least tested against Python 3 before being resubmitted.

review: Needs Fixing

[lp:~javier.collado/checkbox/bug990075]

1380. By Javier Collado on 2012-06-13

Removed custom code to provide readable output and replaced with difflib

Instead of keeping track of broken dependencies, difflib is used against the
original whitelist and the new whitelist after the job reordering to provide a
diff style output that is much more readable to the user.

1381. By Javier Collado on 2012-06-13

Added text to make clear what is related to the old/new whitelist

[Javier Collado (javier.collado)]

Since the branch is now old after all the python3 changes and was also has been used to create a merge request against 0.13, I'm rejecting this merge request and creating a new one with an updated version of the changes.

review: Disapprove

Unmerged revisions

1382. By Javier Collado on 2012-06-18

Fixed dependency ordering check

1381. By Javier Collado on 2012-06-13

Added text to make clear what is related to the old/new whitelist

1380. By Javier Collado on 2012-06-13

Removed custom code to provide readable output and replaced with difflib

Instead of keeping track of broken dependencies, difflib is used against the
original whitelist and the new whitelist after the job reordering to provide a
diff style output that is much more readable to the user.

1379. By Javier Collado on 2012-06-12

Updated whitelist error message to display detailed information properly

This change needs the fix for bug1012052 to work fine.

1378. By Javier Collado on 2012-06-12

Added message to let the user know what's the final ordering being used

1377. By Javier Collado on 2012-05-07

Implemented new algorithm to order jobs

The new algorithm no longer uses a standard topological ordering algorithm
because of the lack of information available in job descriptions. For example,
most of the jobs are expected to be executed before suspend/suspend_advanced,
but they are not listed as a dependency for this job. Instead, just the jobs
that are expected to be executed after suspend depend on
suspend/suspend_advanced.

To address this problem, it's assumed that the whitelist is already almost
fine, but there are just a few test cases that are out of order (if this is not
the case, the final ordering will probably not be valid). After that, a list of
dependencies and reverse dependencies is created and an attempt to order all
the messages in the whitelist one by one is made. If the order in the whitelist
is fine, then the messsage is added to the list of sorted jobs, if that's not
the case, the message is cached and added as soon as the missing dependencies
have been added as well.

1376. By Javier Collado on 2012-05-02

Make sure that jobs are topologically ordered (LP: #990075)

1375. By Javier Collado on 2012-05-02

Removed unused code to delete duplicates from job store

jobs_info.py plugin now takes care of the duplicates by updating the message
list before any message is added to the store. Hence, the code to remove files
from store for duplicated message is no longer needed.

1374. By Javier Collado on 2012-05-02

Fixed report-message callback to update existing messages

In the past messages for the same job were added multiple times and it looks
like the store took care of removing duplicates. Now, given that jobs are
already ordered, they can be updated in place before adding them to the store.

1373. By Javier Collado on 2012-05-01

Added topological sort implementation

Unfortunately, this breaks the selection dialog and the test cases
are no long displayed under their test suites.

=== modified file 'checkbox/job.py'
--- checkbox/job.py	2012-05-31 20:21:08 +0000
+++ checkbox/job.py	2012-06-13 16:02:19 +0000
@@ -107,26 +107,11 @@
     def add(self, job):
         # TODO: Order alphabetically within suite or non-suite
 
-        # Remove the same job if it already exists without a suite
-        if "suite" in job:
-            for filename in self._find_matching_messages(name=job["name"], suite=None):
-                os.unlink(filename)
-
         # Return if the same job is already in the store
         if list(self._find_matching_messages(name=job["name"])):
             return
 
         message_id = super(JobStore, self).add(job)
-
-        # TODO: Apply dependencies
-        if "depends" in job:
-            for depends in job["depends"]:
-                for filename in self._find_matching_messages():
-                    message = self._read_message(filename, cache=True)
-                    if job["name"] in message.get("depends", []):
-                        new_filename = self._get_next_message_filename()
-                        os.rename(filename, new_filename)
-
         return message_id
 
     # TODO: Optimize by only searching backwards until a given condition
 
=== modified file 'debian/changelog'
--- debian/changelog	2012-06-13 15:25:12 +0000
+++ debian/changelog	2012-06-13 16:02:19 +0000
@@ -115,6 +115,7 @@
 
 checkbox (0.13.8) precise; urgency=low
 
+  [ Daniel Manrique ]
   [Brendan Donegan]
   * Run fwts_test as root so that the log can be written to on servers and
     also because it's supposed to be run as root (LP: #989701)
@@ -159,11 +160,18 @@
   * [FEATURE] jobs/info.txt.in: added new attachments, lspci -vvnnQ and
     lsusb -vv and ensure outputs of lscpi, lsusb and dmidecode return UTF8.
 
+<<<<<<< TREE
   [Tim Chen]
   * Use nmcli con delete instead of deleting the connection file, also avoid
     bringing eth0 down when running the wireless_monitoring tests.
 
  -- Jeff Lane <[e-mail]>  Mon, 14 May 2012 10:20:59 -0400
+=======
+  [ Javier Collado ]
+  * Make sure that jobs are topologically ordered (LP: #990075)
+
+ -- Javier Collado <[e-mail]>  Wed, 02 May 2012 12:40:29 +0200
+>>>>>>> MERGE-SOURCE
 
 checkbox (0.13.7) precise; urgency=low
 
 
=== modified file 'plugins/jobs_info.py'
--- plugins/jobs_info.py	2012-06-12 15:03:42 +0000
+++ plugins/jobs_info.py	2012-06-13 16:02:19 +0000
@@ -16,9 +16,12 @@
 # You should have received a copy of the GNU General Public License
 # along with Checkbox.  If not, see <http://www.gnu.org/licenses/>.
 #
-import os, sys, re
+import os
+import sys
+import re
 import gettext
 import logging
+import difflib
 
 from collections import defaultdict
 
@@ -108,18 +111,23 @@
         return [re.compile(r"^%s$" % s) for s in strings
             if s and not s.startswith("#")]
 
-
     def gather(self):
         # Register temporary handler for report-message events
         messages = []
 
-        def report_message(message):
+        def report_message(new_message):
+            name = new_message["name"]
             if self.whitelist_patterns:
-                name = message["name"]
                 if not [name for p in self.whitelist_patterns if p.match(name)]:
                     return
 
-            messages.append(message)
+            for message in messages:
+                if message['name'] == name:
+                    # Update message to be added to the store
+                    message.update(new_message)
+            else:
+                # Add message if it wasn't previously added
+                messages.append(new_message)
 
         # Set domain and message event handler
         old_domain = gettext.textdomain()
@@ -130,6 +138,7 @@
             self._manager.reactor.fire("message-directory", directory)
 
         # Apply whitelist ordering
+<<<<<<< TREE
         def key_function(obj):
             name = obj["name"]
             for pattern in self.whitelist_patterns:
@@ -139,8 +148,52 @@
 
             return index
 
+=======
+>>>>>>> MERGE-SOURCE
         if self.whitelist_patterns:
+<<<<<<< TREE
             messages = sorted(messages, key=key_function)
+=======
+            def cmp_function(a, b):
+                a_name = a["name"]
+                b_name = b["name"]
+                for pattern in self.whitelist_patterns:
+                    if pattern.match(a_name):
+                        a_index = self.whitelist_patterns.index(pattern)
+                    elif pattern.match(b_name):
+                        b_index = self.whitelist_patterns.index(pattern)
+
+                return cmp(a_index, b_index)
+
+            messages = sorted(messages, cmp=cmp_function)
+
+        # Check if messages are already topologically ordered
+        is_topological_sort = self.is_topological_sort(messages)
+
+        if not is_topological_sort:
+            # Apply topological sorting
+            old_message_names = ['{0}\n'.format(message['name'])
+                                 for message in messages]
+            messages = self.topological_sort(messages)
+            new_message_names = ['{0}\n'.format(message['name'])
+                                 for message in messages]
+
+            if self.whitelist_patterns:
+                diff = ''.join(difflib
+                               .unified_diff(old_message_names,
+                                             new_message_names,
+                                             'old whitelist',
+                                             'new whitelist'))
+                detailed_text = 'Whitelist diff output:\n{0}'.format(diff)
+                self._manager.reactor.fire(
+                        'prompt-error',
+                        self.interface,
+                        'Whitelist not topologically ordered',
+                        'Jobs have been reordered to fix broken dependencies',
+                        detailed_text)
+
+        # Add jobs to the store
+>>>>>>> MERGE-SOURCE
         for message in messages:
             self._manager.reactor.fire("report-job", message)
 
@@ -148,6 +201,80 @@
         self._manager.reactor.cancel_call(event_id)
         gettext.textdomain(old_domain)
 
+<<<<<<< TREE
+=======
+    def is_topological_sort(self, messages):
+        """
+        Return True if messages are topologically ordered
+        """
+        message_ordering = {message['name']: index
+                            for index, message in enumerate(messages)}
+
+        def check_dependencies_order(message):
+            dependencies = message.get('depends', '').split()
+            message_order = message_ordering[message['name']]
+            return all(message_ordering[dependency] > message_order
+                       for dependency in dependencies)
+
+        return all(check_dependencies_order(message)
+                   for message in messages)
+
+    def topological_sort(self, messages):
+        """
+        Sort messages topologically
+        """
+        whitelist = {message['name']: message
+                     for message in messages}
+
+        # Map messages to their dependencies
+        depends = defaultdict(list)
+        for message in messages:
+            m_name = message['name']
+            m_depends = message.get('depends', '').split()
+            for dependency in m_depends:
+                # Ignore dependencies against
+                # messages that haven't been whitelisted
+                if dependency in whitelist:
+                    depends[m_name].append(dependency)
+
+        # Map messages to their reverse dependencies
+        rdepends = defaultdict(list)
+        for m_name, m_depends in depends.items():
+            for dependency in m_depends:
+                rdepends[dependency].append(m_name)
+
+        sorted_messages = []
+        skipped_messages = set()
+
+        def message_append(m_name):
+            """
+            Append messages without breaking dependencies
+            trying to follow whitelist order closely
+            """
+            # Skip message if depends on other messages
+            if len(depends[m_name]) > 0:
+                skipped_messages.add(m_name)
+                return
+
+            message = whitelist[m_name]
+            sorted_messages.append(message)
+
+            for r_name in rdepends[m_name]:
+                depends[r_name].remove(m_name)
+
+                if r_name in skipped_messages:
+                    skipped_messages.remove(r_name)
+                    message_append(r_name)
+
+        # Traverse messages and add them to sorted_messages
+        # in the correct order that doesn't break any dependency
+        for message in messages:
+            message_append(message['name'])
+
+        assert len(messages) == len(sorted_messages)
+        return sorted_messages
+
+>>>>>>> MERGE-SOURCE
     def post_gather(self, interface):
         """
         Verify that all patterns were used