1.1 --- a/common.py Mon Mar 13 14:47:44 2017 +0100
1.2 +++ b/common.py Mon Mar 13 17:09:50 2017 +0100
1.3 @@ -995,8 +995,82 @@
1.4 on.
1.5 """
1.6
1.7 - # Record the reverse dependencies, making a mapping of the form
1.8 - # "B is needed by A", "C is needed by A", and so on.
1.9 + usage = init_reverse_dependencies(all_depends)
1.10 +
1.11 + # Produce an ordering by obtaining exposed items (required by items already
1.12 + # processed) and putting them at the start of the list.
1.13 +
1.14 + ordered = []
1.15 +
1.16 + while usage:
1.17 + have_next = False
1.18 +
1.19 + for key, n in usage.items():
1.20 +
1.21 + # Add items needed by no other items to the ordering.
1.22 +
1.23 + if not n:
1.24 + remove_dependency(key, all_depends, usage, ordered)
1.25 + have_next = True
1.26 +
1.27 + if not have_next:
1.28 + raise ValueError, usage
1.29 +
1.30 + return ordered
1.31 +
1.32 +def order_dependencies_partial(all_depends):
1.33 +
1.34 + """
1.35 + Produce a dependency ordering for the 'all_depends' mapping. This mapping
1.36 + has the form "A depends on B, C...". The result will order A, B, C, and so
1.37 + on. Where cycles exist, they will be broken and a partial ordering returned.
1.38 + """
1.39 +
1.40 + usage = init_reverse_dependencies(all_depends)
1.41 +
1.42 + # Duplicate the dependencies for subsequent modification.
1.43 +
1.44 + new_depends = {}
1.45 + for key, values in all_depends.items():
1.46 + new_depends[key] = set(values)
1.47 +
1.48 + all_depends = new_depends
1.49 +
1.50 + # Produce an ordering by obtaining exposed items (required by items already
1.51 + # processed) and putting them at the start of the list.
1.52 +
1.53 + ordered = []
1.54 +
1.55 + while usage:
1.56 + least = None
1.57 + least_key = None
1.58 +
1.59 + for key, n in usage.items():
1.60 +
1.61 + # Add items needed by no other items to the ordering.
1.62 +
1.63 + if not n:
1.64 + remove_dependency(key, all_depends, usage, ordered)
1.65 + least = 0
1.66 +
1.67 + # When breaking cycles, note the least used items.
1.68 +
1.69 + elif least is None or len(n) < least:
1.70 + least_key = key
1.71 + least = len(n)
1.72 +
1.73 + if least:
1.74 + transfer_dependencies(least_key, all_depends, usage, ordered)
1.75 +
1.76 + return ordered
1.77 +
1.78 +def init_reverse_dependencies(all_depends):
1.79 +
1.80 + """
1.81 + From 'all_depends', providing a mapping of the form "A depends on B, C...",
1.82 + record the reverse dependencies, making a mapping of the form
1.83 + "B is needed by A", "C is needed by A", and so on.
1.84 + """
1.85
1.86 usage = {}
1.87
1.88 @@ -1010,32 +1084,87 @@
1.89 init_item(usage, depend, set)
1.90 usage[depend].add(key)
1.91
1.92 - # Produce an ordering by obtaining exposed items (required by items already
1.93 - # processed) and putting them at the start of the list.
1.94 + return usage
1.95 +
1.96 +def transfer_dependencies(key, all_depends, usage, ordered):
1.97 +
1.98 + """
1.99 + Transfer items needed by 'key' to those items needing 'key', found using
1.100 + 'all_depends', and updating 'usage'. Insert 'key' into the 'ordered'
1.101 + collection of dependencies.
1.102
1.103 - ordered = []
1.104 + If "A is needed by X" and "B is needed by A", then transferring items needed
1.105 + by A will cause "B is needed by X" to be recorded as a consequence.
1.106 +
1.107 + Transferring items also needs to occur in the reverse mapping, so that
1.108 + "A needs B" and "X needs A", then the consequence must be recorded as
1.109 + "X needs B".
1.110 + """
1.111 +
1.112 + ordered.insert(0, key)
1.113
1.114 - while usage:
1.115 - have_next = False
1.116 + needing = usage[key] # A is needed by X
1.117 + needed = all_depends.get(key) # A needs B
1.118 +
1.119 + if needing:
1.120 + for depend in needing:
1.121 + l = all_depends.get(depend)
1.122 + if not l:
1.123 + continue
1.124
1.125 - for path, n in usage.items():
1.126 - if not n:
1.127 - ordered.insert(0, path)
1.128 - depends = all_depends.get(path)
1.129 + l.remove(key) # X needs (A)
1.130 +
1.131 + if needed:
1.132 + l.update(needed) # X needs B...
1.133 +
1.134 + # Prevent self references.
1.135 +
1.136 + if depend in needed:
1.137 + l.remove(depend)
1.138
1.139 - # Reduce usage of the referenced items.
1.140 + if needed:
1.141 + for depend in needed:
1.142 + l = usage.get(depend)
1.143 + if not l:
1.144 + continue
1.145 +
1.146 + l.remove(key) # B is needed by (A)
1.147 + l.update(needing) # B is needed by X...
1.148
1.149 - if depends:
1.150 - for depend in depends:
1.151 - usage[depend].remove(path)
1.152 + # Prevent self references.
1.153 +
1.154 + if depend in needing:
1.155 + l.remove(depend)
1.156 +
1.157 + if needed:
1.158 + del all_depends[key]
1.159 + del usage[key]
1.160 +
1.161 +def remove_dependency(key, all_depends, usage, ordered):
1.162
1.163 - del usage[path]
1.164 - have_next = True
1.165 + """
1.166 + Remove 'key', found in 'all_depends', from 'usage', inserting it into the
1.167 + 'ordered' collection of dependencies.
1.168 +
1.169 + Given that 'usage' for a given key A would indicate that "A needs <nothing>"
1.170 + upon removing A from 'usage', the outcome is that all keys needing A will
1.171 + have A removed from their 'usage' records.
1.172 +
1.173 + So, if "B needs A", removing A will cause "B needs <nothing>" to be recorded
1.174 + as a consequence.
1.175 + """
1.176
1.177 - if not have_next:
1.178 - raise ValueError, usage
1.179 + ordered.insert(0, key)
1.180 +
1.181 + depends = all_depends.get(key)
1.182 +
1.183 + # Reduce usage of the referenced items.
1.184
1.185 - return ordered
1.186 + if depends:
1.187 + for depend in depends:
1.188 + usage[depend].remove(key)
1.189 +
1.190 + del usage[key]
1.191
1.192 # General input/output.
1.193
