# HG changeset patch # User Paul Boddie # Date 1489528443 -3600 # Node ID 812f634ba99efd1574b1f56b3c10774bc51f696b # Parent 8ee69504cbf313fe774750c4c5f9d8f5be3867ae Replaced the single-pass traversal of partially-ordered alias dependencies with repetitive traversal, iteratively propagating information between aliases and accesses. diff -r 8ee69504cbf3 -r 812f634ba99e deducer.py --- a/deducer.py Tue Mar 14 22:52:13 2017 +0100 +++ b/deducer.py Tue Mar 14 22:54:03 2017 +0100 @@ -146,7 +146,6 @@ self.init_accessors() self.init_accesses() self.init_aliases() - self.init_alias_network() self.modify_mutated_attributes() self.identify_references() self.classify_accessors() @@ -969,6 +968,15 @@ for accessor_location, access_locations in self.alias_index.items(): self.update_aliases(accessor_location, access_locations) + # Get accesses affected by aliases. + + self.alias_index_rev = {} + + for accessor_location, access_locations in self.alias_index.items(): + for access_location in access_locations: + init_item(self.alias_index_rev, access_location, set) + self.alias_index_rev[access_location].add(accessor_location) + def update_aliases(self, accessor_location, access_locations, visited=None): """ @@ -1019,21 +1027,6 @@ 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): @@ -1365,17 +1358,39 @@ self.const_accesses[original_location] = access_location self.const_accesses_rev[access_location] = original_location - # Aliased name definitions. All aliases with usage will have been - # defined, but they may be refined according to referenced accesses. - - 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. - - for access_location in alias_accesses: - self.record_types_for_access(access_location, self.access_index[access_location]) + # Propagate alias-related information. + + affected_aliases = set(self.alias_index.keys()) + + while True: + + # Aliased name definitions. All aliases with usage will have been + # defined, but they may be refined according to referenced accesses. + + updated_aliases = set() + + for location in affected_aliases: + if self.record_types_for_alias(location): + updated_aliases.add(location) + + # Update accesses employing aliases. + + updated_accesses = set() + + for access_location in alias_accesses: + if self.record_types_for_access(access_location, self.access_index[access_location]): + updated_accesses.add(access_location) + + # Update aliases for updated accesses. + + affected_aliases = set() + + for access_location in updated_accesses: + if self.alias_index_rev.has_key(access_location): + affected_aliases.update(self.alias_index_rev[access_location]) + + if not affected_aliases: + break def constrain_types(self, path, class_types, instance_types, module_types): @@ -1530,12 +1545,12 @@ """ Define types for the 'access_location' associated with the given - 'accessor_locations'. + 'accessor_locations'. Return whether referenced attributes were updated. """ attrname = get_attrname_from_location(access_location) if not attrname: - return + return False invocation = access_location in self.reference_invocations assignment = access_location in self.reference_assignments @@ -1549,6 +1564,8 @@ constrained = True + old_referenced_attrs = self.referenced_attrs.get(access_location) + for location in accessor_locations: # Remember accesses employing aliases. @@ -1576,6 +1593,10 @@ self.init_access_details(access_location) self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, constrained) + # Return whether the referenced attributes have changed. + + return old_referenced_attrs != self.referenced_attrs.get(access_location) + def record_types_for_usage(self, accessor_location, usage): """ @@ -1626,6 +1647,7 @@ """ Define types for the 'accessor_location' not having associated usage. + Return whether the types were updated. """ have_access = self.provider_class_types.has_key(accessor_location) @@ -1666,7 +1688,7 @@ # need to be traversed first. if remaining: - return + return False # Alias references an attribute access. @@ -1680,7 +1702,7 @@ # to refine the alias's types. if not attrs: - return + return False # Invocations converting class accessors to instances do not # change the nature of class providers. @@ -1694,7 +1716,7 @@ # the defined accessor types. if function_types or var_types: - return + return False class_types = set(provider_class_types).intersection(class_types) instance_types = set(provider_instance_types).intersection(instance_types) @@ -1758,7 +1780,7 @@ # refine the defined accessor types. else: - return + return False # Record refined type details for the alias as an accessor. @@ -1766,11 +1788,16 @@ self.update_provider_types(accessor_location, new_provider_class_types, new_provider_instance_types, new_provider_module_types) self.update_accessor_types(accessor_location, new_accessor_class_types, new_accessor_instance_types, new_accessor_module_types) + return new_accessor_class_types != accessor_class_types or \ + new_accessor_instance_types != accessor_instance_types or \ + new_accessor_module_types != accessor_module_types + # Without an access, attempt to identify references for the alias. # Invocations convert classes to instances and also attempt to find # return value information. else: + old_refs = self.referenced_objects.get(accessor_location) refs = set() for access_location in self.alias_index[accessor_location]: @@ -1791,7 +1818,7 @@ # need to be traversed first. if remaining: - return + return False # Alias references an attribute access. @@ -1827,6 +1854,8 @@ self.referenced_objects[accessor_location] = refs + return old_refs != refs + def get_references_for_access(self, access_location): "Return the references identified for 'access_location'."