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

[Javier Collado]

This is a new merge request for the whitelist ordering changes. The reason a new merge request has been created is that the work started before the python3 changes and the original branch is no longer easy to merge (besides this, the old branch has been used also to create a merge request against 0.13 which is unfortunate on my side).

Hence, a new branch in which the changes from the old one have been rebased has been created so that changes now are easy to review and merge in trunk.

For a detailed explanation of the changes, please have a look at:
https://code.launchpad.net/~javier.collado/checkbox/bug990075/+merge/104369

[Marc Tardif (cr3)]

Same question as for the merge request against 0.13...

review: Needs Information

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

1446. By Javier Collado on 2012-06-18

Fixed dependency ordering check

[Javier Collado (javier.collado)]

To be honest, I don't really know what the Resolver instance does exactly. What
I can do is provide an explanation about what the algorithm used in the
jobs_info plugin and since you know the implementetation in suites_prompt,
hopefully we can reach a common understanding of both.

From an initial look at the Resolver implementation, I can tell that the
implementation is supposed to fix every dependency problem including circular
dependencies, while the jobs_info plugin just tries to reorder jobs that are
slightly out of order trying to preserve original whitelist ordering.

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.

[Marc Tardif (cr3)]

First, by asking the same applicable question and answering with the same response in both merge requests, this should make apparent the relevance of merging to one branch and then backporting to other branches. Otherwise, this is looking like two independent merges to two branches with more or less the same code resulting in effectively two reviews. For the sake of sanity, we should continue commenting on this merge request and ignore the other one for now. Even though the other branch has been merged already, we could still backport some of the changes proposed in this merge request to the other branch.

Second, it looks like part of this merge request is replacing the topological sorting done on the filesystem in the JobStore with its own method in memory. This will probably have noticeable performance improvements, so it is probably worthwhile. However, I'm not sure that the remaining code in JobStore will have much more relevance so I would just replace the class definition with:

    class JobStore(MessageStore):
        pass

Third, the topological sort method duplicates the logic already in the Resolver class. I see from the extensive commit message that we seem to need a very specific kind of topological sorting, but I would rather have it implemented in a single location rather than duplicated. However, my understanding is that topological sorting is only done as a last resort when the whitelist file is not ordered properly. So, we might not really need such a specific kind of sorting if we'll be using the whitelist most of the time.

Fourth, if we use the Resolver, we might need to repurpose the is_topological_sort method with a method that actually returns the topological sort errors. The reason is that the diff might not look as clean as with the specific kind of topological sorting method. However, the same information can still be conveyed like this:

    def get_order_errors(self, messages):
        errors = []
        names = set()
        for message in messages:
            name = message["name"]
            for dependency in message.get("depends", "").split():
                if dependency not in names:
                    errors.append("%s > %s" % (name, dependency))

            names.add(name)

        return errors

Last, I would only show the error prompt when running checkbox in debug mode. The reason is that this is not something endusers could reasonably do anything about.

For your convenience, I've created a little branch with these proposed changes:

  lp:~cr3/checkbox/bug990075-3

Note that the branch has no changelog nor merge request because it is only intended to share ideas for now. Please have a look and let me know what you think.

review: Needs Information

[Javier Collado (javier.collado)]

> For the sake of sanity, we should continue commenting on this merge request
> and ignore the other one for now.

The reason for two different branches to exist is, as you know, that the python3
upgrade hasn't finished yet in trunk, and that I'd like to have a solution
for precise as soon as possible. Certainly, it would be have been easier
if the python3 changes would have been submitted to a different branch
and merged into trunk only when finished, not on a script by script basis.

Given the current situation, of course I prefer to work on a single branch
and port the changes to the other one when I've got the solution. However,
given that the priority is to have a solution for precise, then I still
think that the review work should happen in 0.13, not in trunk.

[Marc Tardif (cr3)]

I am volunteering to backport the changes in trunk to 0.13 and submit a merge request. So, we can concentrate on this branch and postpone 0.13 until we agree on this branch. What do you think of my branch?

[Marc Tardif (cr3)]

I replaced the branch mentionned earlier with this one:

  https://code.launchpad.net/~cr3/checkbox/bug990075-3_trunk

and created another one for 0.13:

  https://code.launchpad.net/~cr3/checkbox/bug990075-3_0.13

After we agree on some of these changes, the next steps will be:

1. Agree on the error format;
2. Run checkbox-oem in debug mode.

[Javier Collado (javier.collado)]

After running a simple test case, I saw duplicated jobs in the test results:

Name Result Comment
graphics/xorg-version PASSED 1.11.3
graphics/resolution-change uninitiated
graphics/xorg-version PASSED 1.11.3
graphics/resolution-change PASSED Manually marked as passed

Note that there are two graphics/resolution-change jobs with different result.

[Javier Collado (javier.collado)]

When testing the python3 branch, I also got a an exception:

2012-06-19 17:35:50,631 ERROR Error running event handler <string> JobsInfo.gather() for event type 'gather'
Traceback (most recent call last):
  File "/usr/lib/python3/dist-packages/checkbox/reactor.py", line 74, in fire
    results.append(handler(*args, **kwargs))
  File "<string>", line 174, in gather
  File "/usr/lib/python3/dist-packages/checkbox/lib/resolver.py", line 111, in get_dependents
    dependents = sorted(dependents)
TypeError: unorderable types: dict() < dict()

[Javier Collado (javier.collado)]

Looking the checkbox/lib/resolve.py it seems that jobs are reordered based on the number of dependencies they have. Is that correct? If that's the case, this might break whitelist ordering and cause some other trouble with jobs that have implicit dependencies (suspend/advanced).

[Marc Tardif (cr3)]

So, you had a few comments that I will try to address individually in this comment:

1. About the duplicate tests, I was able to reproduce the problem. I reintroduced some of the code in the JobStore class in revno 1447 and I was then unable to reproduce the problem. Fixed!

2. About sorting dicts, I was also able to reproduce the problem. I specified the key parameter to the sorted() function in revno 1445 and that exception no longer appeared in the log. As for the mysterious revno 1446, that fixed another unrelated exception that no longer appears in the log either. Double fixed!

3. About the reordering, it seems that the motivation for the error message when the whitelist does not honour dependencies is to encourage developers to use the whitelist as the authority. In other words, the most common use case will be to use the ordering specified in the whitelist. So, we could potentially improve the ordering in the Resolver class but I don't think it's really worthwhile. What do you think?

All the changes have been ported from the bug990075-3_trunk to the bug990075-3_0.13 branch. So, you should be able to test once again.

[Javier Collado (javier.collado)]

The problems have been fixed indeed, thanks.

I've tested the changes directly using the trunk version, because Sylvain already submitted a checkbox-oem branch with all plugins disabled that works in python3.

Unfortunately, I still see that for checkbox-oem there's a problem which is that when the messages are checked for topological order, they haven't been expanded yet, that is, the messages don't contain all the jobs that are in the whitelist.

For example, for two equivalent whitelist for checkbox and checkbox-oem (only different by a few resource jobs and the certification tests being included as a test suite), the messages that get_order_error receives in plain checkbox are:
cpuinfo
cdimage
dpkg
gconf
lsb
meminfo
module
package
device
dmi
uname
sleep
optical_drive
block_device
display
__graphics__
graphics/resolution-change
graphics/xorg-version

However, the messages in checkbox-oem are:
build
accessibility
resource
hardware
hardware/certification

As explained above, the hardware/certification job is a local job that has to be expanded to get all the jobs contained in the test suite. However, they are not there yet when the ordering is checked.

[Javier Collado (javier.collado)]

To fix the problem, I tried to move the check after these lines:

          for message in messages:
              self._manager.reactor.fire("report-job", message)

However, that doesn't solve the problem. Despite the ordering seems to be fixed, I don't get the dialog that explains that the whitelist has been reordered using debug log level and in the list of messages passed to get_order_error I see duplicated jobs like this:
...
__graphics__
graphics/resolution-change
graphics/resolution-change
graphics/xorg-version
graphics/xorg-version

One alternative way I tried in the past to fix the problem was trying to decouple the job-report event from the storage in the JobStore object. However, that didn't work fine either for unknown reasons.

[Marc Tardif (cr3)]

Before, sorting was done incrementally in the JobStore class. Now, it must be done on a complete list of messages in the jobs_info plugin.

As you probably noticed, the messages array doesn't contain the complete list before reaching the for loop you quoted in your previous message:

          for message in messages:
              self._manager.reactor.fire("report-job", message)

Rather, the messages array is appended with more messages as the "report-job" event is fired. Admittedly, this is very difficult to manage so I made a couple changes to simplify the code. First, I split the "report-job" handler in the job_prompt plugin and created the "report-jobs" (plural) handler for adding to the store:

    def report_job(self, job):
        # Update job
        job.setdefault("status", UNINITIATED)
        self._manager.reactor.fire("report-%s" % job["plugin"], job)

    def report_jobs(self, jobs):
        for job in jobs:
            self.store.add(job)

Second, I move the for loop for gathering messages earlier in the gather handler of the jobs_info prompt. As a result of these changes, the messages array is now complete when you reach the middle of the handler. So, I added this call to get a list of unique messages:

        # Get unique messages from the now complete list
        messages = self.get_unique_messages(messages)

Then, all the subsequent code should work nicely since it is operating on the complete list of messages. I haven't been able to test these changes against the oem-qa-checkbox branch but I have ported to 0.13 just in case it might be useful.

Please let me know if we're getting closer :)

[Javier Collado (javier.collado)]

We're definitely closer. I've tested trunk changes and I was able to see the whitelist ordering error message in both checkbox and checkbox-oem branches.

Things that are remaining:
- Agree on the error format
I still find that the diff output suggested by Brendan looked nice, because you're able to check which jobs have been moved in a compact way, not the ones that were causing problems. Note that they are not exactly the same ones.

For example, if we have a whitelist like this:
mediacard/mmc-insert-after-suspend
mediacard/mmc-storage-after-suspend
suspend/suspend_advanced

The error message that the user currently gets would be:
mediacard/mmc-insert-after-suspend > suspend/suspend_advanced

However, when displaying a diff, the output would be:
--- old_whitelist
+++ new_whitelist
@@ -1,3 +1,3 @@
+suspend/suspend_advanced
 mediacard/mmc-insert-after-suspend
 mediacard/mmc-storage-after-suspend
-suspend/suspend_advanced

I find the second one clearer and more informative. In fact, it lets me check that mediacard/mmc-storage-after-suspend has been moved after suspend/suspend_advanced as well (not only mediacard/mmc-insert-after-suspend); while, with the previous output, I haven't been able to test that.

- Run checkbox-oem in debug mode
Looks like this is already in place. I see in all binaries in the checkbox-oem branch the following line:
export CHECKBOX_OPTIONS=${CHECKBOX_OPTIONS:---log-level=debug --log=$CHECKBOX_DATA/checkbox-oem.log}

and indeed I don't need to specify any command line option to get the whitelist ordering error message, so unless this isn't the proper way to enable debug mode, I think we're done on this one.

[Marc Tardif (cr3)]

1. About the error format, since the error is now only shown in debug mode, I'm much more comfortable using the unified diff format because it is mostly targetted towards developers. So, I reintroduced your code using difflib into both branches that I reiterate here for your convenience:

  https://code.launchpad.net/~cr3/checkbox/bug990075-3_trunk
  https://code.launchpad.net/~cr3/checkbox/bug990075-3_0.13

2. About running checkbox-oem in debug mode, your current approach is the proper way to enable debug mode.

If you agree with both branches, I could try to submit merge requests for each of them that should hopefully apply cleanly. What do you think, shall we try?

[Javier Collado (javier.collado)]

There's a small problem related to the diff output, difflib expects every element in the lists of strings to have a newline character output.

To fix that, these lines:
old_message_names = [message["name"] for message in messages]
...
new_message_names = [message["name"] for message in messages]

should be replaced with something like:
old_message_names = ['{0}\n'.format(message['name']) for message in messages]
...
new_message_names = ['{0}\n'.format(message['name']) for message in messages]

[Javier Collado (javier.collado)]

> If you agree with both branches, I could try to submit merge requests for each
> of them that should hopefully apply cleanly. What do you think, shall we try?

Once the problem in the diff output is fixed, I'll run a few tests to make sure the reordering works as we expect.

[Marc Tardif (cr3)]

Done, you can safely run your tests now.

[Marc Tardif (cr3)]

I also took the opportunity of only reporting problems with patterns in debug in the post_gather method of the jobs_info plugin. This should not affect checkbox-oem as it is always running in debug mode.

[Javier Collado (javier.collado)]

I'm not completely happy with the changes because, according the results, they don't seem to stick to the original idea of reordering jobs only when dependencies where not correctly met, that is, to preserve whitelist ordering as much as possible.

For example, using a very easy whitelist with a few resource jobs and a couple of test cases in which one dependency is out of order, what I get with the initial changes I proposed to merge:

--- old whitelist
+++ new whitelist
@@ -14,5 +14,5 @@
 block_device
 display
 __graphics__
+graphics/xorg-version
 graphics/resolution-change
-graphics/xorg-version

However, what I get with the last changes you submitted is:

--- old whitelist
+++ new whitelist
@@ -1,18 +1,18 @@
+__graphics__
+block_device
+cdimage
 cpuinfo
-cdimage
+device
+display
+dmi
 dpkg
 gconf
+graphics/xorg-version
+graphics/resolution-change
 lsb
 meminfo
 module
+optical_drive
 package
-device
-dmi
+sleep
 uname
-sleep
-optical_drive
-block_device
-display
-__graphics__
-graphics/resolution-change
-graphics/xorg-version

In my opinion it would be much better if the output looked as the first one, since that would provide a nice feedback to the tester with a malformed whitelist.

[Marc Tardif (cr3)]

Sure, if this is critical to have the branch merged, please feel free to modify the Resolver class accordingly. Now that topological sorting is done in a single location rather than by introducing duplicate logic, I'm much more comfortable with improving that logic. If you're able to complete this today, I might even be able to push your improvements in Ubuntu over the weekend!

[Brendan Donegan (brendan-donegan)]

I think I should let my feelings known about this functionality. As I've said before, I think the whitelist should be authoritative. The jobs should run in strict whitelist order and if any cannot be run due to failing dependencies than this should be reflected in the test report. For example, you could have job output like:

suspend/wireless_after_suspend Unitiated Did not run because suspend/suspend_advanced_auto failed

network/ping Unitiated Did not run because network/detect has not been run yet

I appreciate that people may be frustrated if they run tests and they see these messages if they have not been given a chance to rectify them. But two things to consider. One is that giving feedback *in Checkbox* does not help in the case of fully automated runs (as we do for server testing and SRU), the same result will occur. The other is that we could create a simple tool which validates a whitelist and points out any issues without having to run Checkbox itself. Take the precedent of a compiler or interpreter - it does not try to fix your program for you on the fly! The whitelists should be the same - if it's not right then A:) your results aren't right B:) you know why

I can't envision how we will have people coming to us saying they don't understand why their tests weren't run properly if we follow a simple scheme such as this.

Please, let me know what you think.

review: Needs Information

[Javier Collado (javier.collado)]

@Brendan

Thanks for your feedback. I agree on that it's safer to force the user to fix the whitelist before using checkbox, but I also think that it's difficult to make things work that way now that checkbox has been reordering jobs for quite a long time. What I mean is that users are already used to let checkbox fix things without worrying too much and things get a little bit more complex, then the feedback probably isn't going to be positive.

For now, what I believe is the right choice is to implement this feature which just provides some warning message to users, so that they decide if they want to fix their whitelist or let checkbox do it. Depending on the feedback received, the feature can be turned into something stricter or not, but let the users decide (we might be wrong in our judgment).

Anyway, it's true that a tool can be created to provide real help on the whitelist creation. Given that checkbox-editor already does that, after this fix is submitted, I'll work on improving the whitelist creation feature in checkbox-editor to avoid some of the issues found in the whitelists that have been created with it.

[Brendan Donegan (brendan-donegan)]

@Javier,

Personally I don't think anyone will miss Checkbox reordering jobs, as long as there is clear feedback - but certainly this isn't a decision you or I can make exclusively. We should talk about this at the next Checkbox stakeholders meeting. As for the tool to help whitelist ordering, I feel this needs to be a core part of Checkbox, not a seperate tool that needs to be installed and so on. A simple script should do the trick.

[Marc Tardif (cr3)]

I'm afraid we're spending a significant amount of resources on this branch. Please let me know how my branch does not fix the problem described in bug #990075. If my branch does fix the problem, let's merge it and report a separate bug to improve ordering and move on.

review: Needs Information

[Marc Tardif (cr3)]

This merge request has been superseded by this one:

https://code.launchpad.net/~cr3/checkbox/bug990075-3_trunk/+merge/111861

and the corresponding merge request for 0.13:

https://code.launchpad.net/~cr3/checkbox/bug990075-3_0.13/+merge/111862

There is still a pending improvement to make the topological ordering match the whitelist file more closely, but Javier will be creating a bug to track this separately. So, I'm disapproving this merge request and setting the status to rejected.

review: Disapprove

Unmerged revisions

1446. By Javier Collado on 2012-06-18

Fixed dependency ordering check

1445. By Javier Collado on 2012-06-13

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

1444. 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.

1443. 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.

1442. By Javier Collado on 2012-06-12

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

1441. 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.

1440. By Javier Collado on 2012-05-02

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

1439. 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.

1438. 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.

1437. 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-18 09:21:39 +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-15 08:10:37 +0000
+++ debian/changelog	2012-06-18 09:21:39 +0000
@@ -117,6 +117,9 @@
   * jobs/stress.txt.in: add OEM team's stress tests (including reboot and poweroff)
     and log analysis jobs      
 
+  [ Javier Collado ]
+  * Make sure that jobs are topologically ordered (LP: #990075)
+
  -- Jeff Lane <[e-mail]>  Wed, 06 Jun 2012 15:12:25 -0400
 
 checkbox (0.13.8) 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-18 09:21:39 +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,17 +138,44 @@
             self._manager.reactor.fire("message-directory", directory)
 
         # Apply whitelist ordering
-        def key_function(obj):
-            name = obj["name"]
-            for pattern in self.whitelist_patterns:
-                if pattern.match(name):
-                    index = self.whitelist_patterns.index(pattern)
-                    break
-
-            return index
-
         if self.whitelist_patterns:
+            def key_function(obj):
+                name = obj["name"]
+                for pattern in self.whitelist_patterns:
+                    if pattern.match(name):
+                        index = self.whitelist_patterns.index(pattern)
+                        break
+
+                return index
+
             messages = sorted(messages, key=key_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
         for message in messages:
             self._manager.reactor.fire("report-job", message)
 
@@ -148,6 +183,77 @@
         self._manager.reactor.cancel_call(event_id)
         gettext.textdomain(old_domain)
 
+    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
+
     def post_gather(self, interface):
         """
         Verify that all patterns were used