+def toposort2(data):
+ '''Topological sort.
+ From http://code.activestate.com/recipes/577413-topological-sort/
+ This function is under the MIT license.
+ '''
+ for k, v in data.items():
+ v.discard(k) # Ignore self dependencies
+ extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
+ data.update(dict([(item, set()) for item in extra_items_in_deps]))
+ while True:
+ ordered = set(item for item,dep in data.items() if not dep)
+ if not ordered:
+ break
+ for item in sorted(ordered):
+ yield item
+ data = dict([(item, (dep - ordered)) for item,dep in data.items()
+ if item not in ordered])
+ assert not data, "A cyclic dependency exists amongst %r" % data
+
+def sort_dependencies(messages):
+ '''Sort a list of Messages based on dependencies.'''
+ dependencies = {}
+ message_by_name = {}
+ for message in messages:
+ dependencies[str(message.name)] = set(message.get_dependencies())
+ message_by_name[str(message.name)] = message
+
+ for msgname in toposort2(dependencies):
+ if msgname in message_by_name:
+ yield message_by_name[msgname]
+