core/deptools.py

   1 #! /usr/bin/env python
   2 from collections import deque,defaultdict
   3 from itertools import ifilter
   4 import digraphtools
   5
   6 from core.bits import Item,Group
   7
   8 def unbound(func):
   9         '''always return the underlying function from a bound method'''
  10         return getattr(func, 'im_func', func)
  11
  12 class BaseDependencyStrategy:
  13         '''Base class for strategies for dependency resolution'''
  14         @classmethod
  15         def iterate_pruned_item_dependencies(cls, requirements, item):
  16                 '''return an ordered list of dependencies for an item such that an items dependencies are before it in the list
  17                 prunted based on predicate
  18                 Not used, but left here because at some point it might be needed to do
  19                 this in a way that does not alter the items at all (as per the below filter)'''
  20                 raise NotImplementedError
  21
  22         @classmethod
  23         def iterate_item_dependencies(cls, item):
  24                 '''return an ordered list of dependencies for an item such that an items dependencies are before it in the list'''
  25                 raise NotImplementedError
  26
  27         @classmethod
  28         def make_group_dependencies_explicit(cls, item):
  29                 '''applying dependencies of groups to those it contains'''
  30                 raise NotImplementedError
  31
  32         @classmethod
  33         def filter_dependency_graph(cls, requirements, item):
  34                 '''filter items in the dependency graph INPLACE based on the supplied requirements
  35                 It's highly recommended you only do this on item instances and not classes as
  36                 it alters or the depends attribute on all items in the supplied DAG '''
  37                 raise NotImplementedError
  38
  39         @classmethod
  40         def item_factory(cls, goal_item):
  41                 '''instantiate all items in a dependency tree from an end-goal item
  42
  43                 for every instance in the dependency tree, the depends attribute on the instance overriding the class
  44                 returns an instance of the end-goal where all recursively all dependencies are item instances
  45                 '''
  46                 raise NotImplementedError
  47
  48         @classmethod
  49         def early_iter_all_items(cls, item):
  50                 '''get a list of all times, including all groups, contents and dependencies of same
  51                 before groups are unrolled into something that can be represented by a digraph we
  52                 need a way of getting all items, including traversing group contents
  53                 '''
  54                 raise NotImplementedError
  55
  56
  57 class SimpleDependencyStrategy(BaseDependencyStrategy):
  58         '''Reasonably generic strategy for working with dependencies
  59         Requires implementation of some things by other strategies
  60         '''
  61
  62         @classmethod
  63         def iterate_pruned_item_dependencies(cls, requirements, item, seen=None):
  64                 '''return an ordered list of dependencies for an item such that an items dependencies are before it in the list
  65                 This is equivalent to treating the dependencies as a DAG and traversing while:
  66                         - reducing it to a tree by ignoring any nodes seen in the traversal
  67                         - pruning branches where the requirements do not meet an item's predicate
  68                         - doing a post-order traversal to maintain the invaraint that a node's
  69                           dependencies preceed it in the traversal.
  70                 '''
  71                 if seen is None: seen = set()
  72                 if item in seen: raise StopIteration
  73                 seen.add(item)
  74                 filtereddeps = ifilter(lambda i: unbound(i.predicate)(requirements), item.depends)
  75                 for dep in filtereddeps:
  76                         for cdep in cls.iterate_pruned_item_dependencies(requirements,dep,seen):
  77                                 yield cdep
  78                 yield item
  79
  80         @classmethod
  81         def iterate_item_dependencies(cls, item, seen=None):
  82                 if seen is None: seen = set()
  83                 if item in seen: raise StopIteration
  84                 seen.add(item)
  85                 for dep in item.depends:
  86                         for cdep in cls.iterate_item_dependencies(dep,seen):
  87                                 yield cdep
  88                 yield item
  89
  90         @classmethod
  91         def early_iter_all_items(cls, item, seen=None):
  92                 '''get a list of all times, including all groups, contents and dependencies of same
  93                 before groups are unrolled into soemthing that can be represented by a digraph we
  94                 need a way of getting all items, including traversing group contents
  95                 '''
  96                 if seen is None: seen = set()
  97                 if item in seen: raise StopIteration
  98                 seen.add(item)
  99                 for dep in item.depends:
 100                         for cdep in cls.early_iter_all_items(dep,seen):
 101                                 yield cdep
 102                 if isinstance(item,Group) or type(item) == type and issubclass(item,Group):
 103                         for member in item.contains:
 104                                 for cdep in cls.early_iter_all_items(member,seen):
 105                                         yield cdep
 106                 yield item
 107
 108         @classmethod
 109         def filter_dependency_graph(cls, requirements, item):
 110                 '''filter items in the dependency graph INPLACE based on the supplied requirements
 111                 It's highly recommended you only do this on item instances and not classes as
 112                 it alters or the depends attribute on all items in the supplied DAG '''
 113                 items = cls.iterate_item_dependencies(item)
 114                 keptitems = set(filter(lambda i: unbound(i.predicate)(requirements), items))
 115                 droppeditems = set(items).difference(keptitems)
 116
 117                 for dropped in droppeditems: del(dropped.depends) # Drop possible circular refs to filtered instances
 118                 for survivor in keptitems:
 119                         # Drop references to filtered instances
 120                         survivor.depends = tuple(dep for dep in survivor.depends if dep in keptitems)
 121                 if item not in keptitems:
 122                         return None
 123                 return item
 124
 125         @classmethod
 126         def instantiate_items(cls, items):
 127                 '''returns a map from classes to instances'''
 128                 # Pre: All items, including all deps, are in 'items'
 129                 instancemap = dict((item, item()) for item in items) # Only ever instantiate each item once
 130                 iteminstances = map(instancemap.get, items)
 131                 for inst in iteminstances:
 132                         inst.depends = tuple(map(instancemap.get, inst.depends))
 133                         if isinstance(inst,Group):
 134                                 inst.contains = tuple(map(instancemap.get, inst.contains))
 135                 return instancemap
 136
 137         @classmethod
 138         def item_factory(cls, goal_item):
 139                 '''instantiate all items in a dependency tree from an end-goal item
 140
 141                 for every instance in the dependency tree, the depends attribute on the instance overriding the class
 142                 returns an instance of the end-goal where all recursively all dependencies are item instances
 143                 '''
 144                 # Flatten the dep graph to a topsort, instantiate all items, then override depends attributes
 145                 items = set(cls.early_iter_all_items(goal_item))
 146                 instancemap = cls.instantiate_items(items)
 147                 return instancemap[goal_item]
 148
 149         @classmethod
 150         def make_group_dependencies_explicit(cls, item):
 151                 items = set(cls.early_iter_all_items(item))     # Gotta catch them all
 152                 items = cls.make_group_dependencies_explicit_for_items(items)
 153                 assert item in items
 154                 return item
 155
 156         @classmethod
 157         def make_group_dependencies_explicit_for_items(cls, items):
 158                 allitems = items
 159                 items = set(k for k in allitems if isinstance(k,Item) or type(k) == type and issubclass(k,Item))
 160                 groups = set(k for k in allitems if isinstance(k,Group) or type(k) == type and issubclass(k,Group))
 161                 origitems,origgroups = set(items),set(groups)   # For later testing
 162                 assert allitems == items.union(groups)
 163                 assert items.isdisjoint(groups)
 164
 165                 contained_by = defaultdict(set)
 166
 167                 # First find out what groups an item is contained by
 168                 def iter_group_contents(group):
 169                         for k in group.contains:
 170                                 if k in groups:
 171                                         for kk in iter_group_contents(k): yield kk
 172                                 else: yield k
 173                 for group in groups:
 174                         for k in iter_group_contents(group):
 175                                 contained_by[k].add(group)
 176
 177                 # Item dependencies are the explicit dependencies of the items themselves
 178                 # plus the dependencies of the groups they are contained by
 179                 for item,ingroups in contained_by.items():
 180                         assert ingroups.issubset(groups)
 181                         new_deps = set(item.depends)
 182                         for g in ingroups:
 183                                 new_deps.update(g.depends)
 184                         item.depends = tuple(new_deps)
 185
 186                 # Now the dependencies of the items inside groups are unrolled, reduce any
 187                 # references of groups to the contents of the groups
 188
 189                 # First do the group contents themselves recursively, and store as sets
 190                 for group in groups:
 191                         group.contains = set(group.contains)
 192                         while not group.contains.isdisjoint(groups):
 193                                 for containedgroup in group.contains.intersection(groups):
 194                                         assert containedgroup != group
 195                                         group.contains.update(containedgroup.contains)
 196                                         group.contains.remove(containedgroup)
 197
 198                 # Now that for group.contains has been reduced to non-group items,
 199                 # replace any reference to groups in the dependencies of any item with
 200                 # the contents of that group
 201                 for item in items.difference(groups):
 202                         assert item not in groups
 203                         if not groups.isdisjoint(item.depends):
 204                                 item.depends = set(item.depends)
 205                                 for groupdep in item.depends.intersection(groups):
 206                                         item.depends.update(groupdep.contains)
 207                                         item.depends.remove(groupdep)
 208                                 item.depends = tuple(item.depends)
 209                         assert groups.isdisjoint(item.depends)
 210
 211                 assert items == origitems
 212                 assert groups == origgroups
 213                 assert allitems == items.union(groups)
 214                 assert items.isdisjoint(groups)
 215                 assert items == allitems.difference(groups)
 216
 217                 return items
 218
 219
 220 not_none = lambda n: n is not None
 221
 222 class GraphDependencyStrategy(SimpleDependencyStrategy):
 223         '''deal with item dependencies by treating them as a directed acyclic graph
 224         a graph is represented as a 2tuple of a node, and a list of nodes connected to it's outgoing edges
 225
 226         graphs calls are generally passed by goal node, with dependencies on the goal being
 227         it's outgoing edges'''
 228
 229         @classmethod
 230         def get_graph(cls, item, seen=None):
 231                 '''return a DAG from a base item and a set of requirements
 232                 items are pruned from the graph if their predicates are false for the requirements
 233                 '''
 234                 if seen is None: seen = dict()
 235                 if item in seen: return seen[item]
 236                 branches = []
 237                 seen[item] = [item, branches]
 238                 for dep in item.depends:
 239                         branch = cls.get_graph(dep, seen)
 240                         if branch:
 241                                 branches.append(branch)
 242                 return seen[item]
 243
 244         @classmethod
 245         def get_pruned_graph(cls, requirements, item, seen=None):
 246                 '''return a DAG from a base item and a set of requirements
 247                 items are pruned from the graph if their predicates are false for the requirements
 248                 '''
 249                 if seen is None: seen = dict()
 250                 if item in seen: return seen[item]
 251                 branches = []
 252                 seen[item] = [item, branches]
 253                 for dep in filter(lambda i: unbound(i.predicate)(requirements), item.depends):
 254                         branch = cls.get_pruned_graph(requirements, dep, seen)
 255                         if branch:
 256                                 branches.append(branch)
 257                 return seen[item]
 258
 259         @classmethod
 260         def tree_from_graph(cls, graph, seen=None):
 261                 '''convert a DAG into a arborescence by removing edges to seen nodes'''
 262                 node,connected = graph
 263                 if seen is None: seen=set()
 264                 if node in seen: return None
 265                 seen.add(node)
 266                 connected = [cls.tree_from_graph(sub,seen) for sub in connected]
 267                 return [ node,filter(not_none,connected) ]
 268
 269
 270         @classmethod
 271         def postorder_traversal(cls, tree):
 272                 '''traverse tree post-order and return a list of nodes'''
 273                 root,branches = tree
 274                 ret = map(cls.postorder_traversal,branches)
 275                 return sum(ret,[]) + [root]
 276
 277         @classmethod
 278         def iterate_pruned_item_dependencies(cls, requirements, item):
 279                 tree = cls.tree_from_graph( cls.get_pruned_graph(requirements,item) )
 280                 return cls.postorder_traversal(tree)
 281
 282         @classmethod
 283         def iterate_item_dependencies(cls, item):
 284                 tree = cls.tree_from_graph( cls.get_graph(item) )
 285                 return cls.postorder_traversal(tree)
 286
 287
 288 class DigraphDependencyStrategy(SimpleDependencyStrategy):
 289         @classmethod
 290         def edges_from_item_deps(cls, item):
 291                 '''iterates over dependency edges with transiability from item'''
 292                 tovisit = deque([item])
 293                 while len(tovisit):
 294                         item = tovisit.pop()
 295                         for dep in item.depends:
 296                                 yield (item,dep)
 297                         tovisit.extendleft(item.depends)
 298
 299         @classmethod
 300         def graph_from_item_deps(cls, item):
 301                 return digraphtools.graph_from_edges( cls.edges_from_item_deps(item) )
 302
 303         @classmethod
 304         def iterate_item_dependencies(cls, item):
 305                 g = cls.graph_from_item_deps(item)
 306                 return digraphtools.dfs_topsort_traversal(g, item)
 307
 308         @classmethod
 309         def graph_from_items(cls, items):
 310                 # pre: all items in graph are passed
 311                 def edges_from_items(items):
 312                         for i in items:
 313                                 for d in i.depends: yield (i,d)
 314                 return digraphtools.graph_from_edges( edges_from_items(items) )
 315
 316         @classmethod
 317         def find_goal_nodes(cls, items):
 318                 '''return the set of all nodes that aren't depended on'''
 319                 graph = cls.graph_from_items(items)
 320                 start_nodes,dependencies = zip(*list(digraphtools.iter_edges(graph)))
 321                 return set(start_nodes).difference(dependencies)
 322
 323         @classmethod
 324         def needed_dependencies(cls, graph, item):
 325                 '''return which of an item's dependencies are incomplete'''
 326                 return [dep for dep in graph[item] if dep.data['state'] != dep.COMPLETE]
 327
 328         @classmethod
 329         def ready_to_run(cls, items):
 330                 '''return items that are incomplete who have no uncompleted dependencies'''
 331                 graph = cls.graph_from_items(items)
 332                 incomplete =  [item for item in items if item.data['state'] == item.INCOMPLETE]
 333                 return [item for item in incomplete if len(cls.needed_dependencies(graph,item)) == 0]
 334
 335 class DeprecatedDependencyMagic(object):
 336         #TODO: Figure out the object structure for *Magic. Likely it shouldn't even be in this module
 337         def __init__(self, strategy=DigraphDependencyStrategy):
 338                 self.strategy = strategy
 339         def make_new_dep_graph(self, goal_node):
 340                 goal_node = self.strategy.item_factory(goal_node)
 341                 self.strategy.make_group_dependencies_explicit(goal_node)
 342                 return goal_node
 343         def item_list_for_task(self, task):
 344                 # FIXME: Doesn't look at all goal nodes. If we want only 1 goal node we should enforce it
 345                 goal = self.make_new_dep_graph(task.will[0])
 346                 goal = self.strategy.filter_dependency_graph(task.wants, goal)
 347                 return self.strategy.iterate_item_dependencies(goal)