# HG changeset patch # User Paul Boddie # Date 1489421390 -3600 # Node ID 267be996f667393d4bcaa0c5b1aa65ddd04aeb74 # Parent 3d89317842b9cd3da265603d4facb160a50e577f Introduced partial alias ordering for the refinement of alias types. diff -r 3d89317842b9 -r 267be996f667 common.py --- a/common.py Mon Mar 13 14:47:44 2017 +0100 +++ b/common.py Mon Mar 13 17:09:50 2017 +0100 @@ -995,8 +995,82 @@ on. """ - # Record the reverse dependencies, making a mapping of the form - # "B is needed by A", "C is needed by A", and so on. + usage = init_reverse_dependencies(all_depends) + + # Produce an ordering by obtaining exposed items (required by items already + # processed) and putting them at the start of the list. + + ordered = [] + + while usage: + have_next = False + + for key, n in usage.items(): + + # Add items needed by no other items to the ordering. + + if not n: + remove_dependency(key, all_depends, usage, ordered) + have_next = True + + if not have_next: + raise ValueError, usage + + return ordered + +def order_dependencies_partial(all_depends): + + """ + Produce a dependency ordering for the 'all_depends' mapping. This mapping + has the form "A depends on B, C...". The result will order A, B, C, and so + on. Where cycles exist, they will be broken and a partial ordering returned. + """ + + usage = init_reverse_dependencies(all_depends) + + # Duplicate the dependencies for subsequent modification. + + new_depends = {} + for key, values in all_depends.items(): + new_depends[key] = set(values) + + all_depends = new_depends + + # Produce an ordering by obtaining exposed items (required by items already + # processed) and putting them at the start of the list. + + ordered = [] + + while usage: + least = None + least_key = None + + for key, n in usage.items(): + + # Add items needed by no other items to the ordering. + + if not n: + remove_dependency(key, all_depends, usage, ordered) + least = 0 + + # When breaking cycles, note the least used items. + + elif least is None or len(n) < least: + least_key = key + least = len(n) + + if least: + transfer_dependencies(least_key, all_depends, usage, ordered) + + return ordered + +def init_reverse_dependencies(all_depends): + + """ + From 'all_depends', providing a mapping of the form "A depends on B, C...", + record the reverse dependencies, making a mapping of the form + "B is needed by A", "C is needed by A", and so on. + """ usage = {} @@ -1010,32 +1084,87 @@ init_item(usage, depend, set) usage[depend].add(key) - # Produce an ordering by obtaining exposed items (required by items already - # processed) and putting them at the start of the list. + return usage + +def transfer_dependencies(key, all_depends, usage, ordered): + + """ + Transfer items needed by 'key' to those items needing 'key', found using + 'all_depends', and updating 'usage'. Insert 'key' into the 'ordered' + collection of dependencies. - ordered = [] + If "A is needed by X" and "B is needed by A", then transferring items needed + by A will cause "B is needed by X" to be recorded as a consequence. + + Transferring items also needs to occur in the reverse mapping, so that + "A needs B" and "X needs A", then the consequence must be recorded as + "X needs B". + """ + + ordered.insert(0, key) - while usage: - have_next = False + needing = usage[key] # A is needed by X + needed = all_depends.get(key) # A needs B + + if needing: + for depend in needing: + l = all_depends.get(depend) + if not l: + continue - for path, n in usage.items(): - if not n: - ordered.insert(0, path) - depends = all_depends.get(path) + l.remove(key) # X needs (A) + + if needed: + l.update(needed) # X needs B... + + # Prevent self references. + + if depend in needed: + l.remove(depend) - # Reduce usage of the referenced items. + if needed: + for depend in needed: + l = usage.get(depend) + if not l: + continue + + l.remove(key) # B is needed by (A) + l.update(needing) # B is needed by X... - if depends: - for depend in depends: - usage[depend].remove(path) + # Prevent self references. + + if depend in needing: + l.remove(depend) + + if needed: + del all_depends[key] + del usage[key] + +def remove_dependency(key, all_depends, usage, ordered): - del usage[path] - have_next = True + """ + Remove 'key', found in 'all_depends', from 'usage', inserting it into the + 'ordered' collection of dependencies. + + Given that 'usage' for a given key A would indicate that "A needs " + upon removing A from 'usage', the outcome is that all keys needing A will + have A removed from their 'usage' records. + + So, if "B needs A", removing A will cause "B needs " to be recorded + as a consequence. + """ - if not have_next: - raise ValueError, usage + ordered.insert(0, key) + + depends = all_depends.get(key) + + # Reduce usage of the referenced items. - return ordered + if depends: + for depend in depends: + usage[depend].remove(key) + + del usage[key] # General input/output. diff -r 3d89317842b9 -r 267be996f667 deducer.py --- a/deducer.py Mon Mar 13 14:47:44 2017 +0100 +++ b/deducer.py Mon Mar 13 17:09:50 2017 +0100 @@ -22,7 +22,7 @@ from common import first, get_assigned_attributes, \ get_attrname_from_location, get_attrnames, \ get_invoked_attributes, get_name_path, init_item, \ - sorted_output, CommonOutput + order_dependencies_partial, sorted_output, CommonOutput from encoders import encode_access_location, encode_constrained, \ encode_instruction, encode_location, encode_usage, \ get_kinds, test_label_for_kind, test_label_for_type @@ -146,6 +146,7 @@ self.init_accessors() self.init_accesses() self.init_aliases() + self.init_alias_network() self.modify_mutated_attributes() self.identify_references() self.classify_accessors() @@ -1018,6 +1019,21 @@ self.alias_index[accessor_location] = updated_locations return updated_locations + def init_alias_network(self): + + """ + Initialise a network of aliases, their initialising accesses, and the + accessors supporting those accesses. + """ + + self.alias_network = {} + self.alias_network.update(self.alias_index) + + for accessor_location, access_locations in self.alias_index.items(): + for access_location in access_locations: + if not self.alias_network.has_key(access_location): + self.alias_network[access_location] = self.get_accessors_for_access(access_location) + # Attribute mutation for types. def modify_mutated_attributes(self): @@ -1352,8 +1368,9 @@ # Aliased name definitions. All aliases with usage will have been # defined, but they may be refined according to referenced accesses. - for accessor_location in self.alias_index.keys(): - self.record_types_for_alias(accessor_location) + for location in order_dependencies_partial(self.alias_network): + if self.alias_index.has_key(location): + self.record_types_for_alias(location) # Update accesses employing aliases.