# HG changeset patch # User Paul Boddie # Date 1489423999 -3600 # Node ID 8e3fdfc663c9c99c08d0d20339d33200e17907b1 # Parent 479d30d89e05361d95dbae93528adc0303960dbe# Parent 267be996f667393d4bcaa0c5b1aa65ddd04aeb74 Merged changes from the default branch. diff -r 479d30d89e05 -r 8e3fdfc663c9 common.py --- a/common.py Sat Mar 11 01:04:34 2017 +0100 +++ b/common.py Mon Mar 13 17:53:19 2017 +0100 @@ -129,7 +129,6 @@ self.astnode = None self.encoding = None - self.iterators = {} self.temp = {} self.lambdas = {} @@ -230,19 +229,6 @@ def next_literal(self): self.literals[self.get_namespace_path()] += 1 - # Temporary iterator naming. - - def get_iterator_path(self): - return self.in_function and self.get_namespace_path() or self.name - - def get_iterator_name(self): - path = self.get_iterator_path() - init_item(self.iterators, path, lambda: 0) - return "$i%d" % self.iterators[path] - - def next_iterator(self): - self.iterators[self.get_iterator_path()] += 1 - # Temporary variable naming. def get_temporary_name(self): @@ -565,17 +551,32 @@ the iterator, producing a replacement node for the original. """ + t0 = self.get_temporary_name() + self.next_temporary() + t1 = self.get_temporary_name() + self.next_temporary() + i0 = self.get_temporary_name() + self.next_temporary() + node = compiler.ast.Stmt([ - # = {n.list}.__iter__().next + # = {n.list} + # = .__iter__() + # = .next compiler.ast.Assign( - [compiler.ast.AssName(self.get_iterator_name(), "OP_ASSIGN")], - compiler.ast.Getattr( - compiler.ast.CallFunc( - compiler.ast.Getattr(n.list, "__iter__"), - [] - ), "next")), + [compiler.ast.AssName(t0, "OP_ASSIGN")], + n.list), + + compiler.ast.Assign( + [compiler.ast.AssName(t1, "OP_ASSIGN")], + compiler.ast.CallFunc( + compiler.ast.Getattr(compiler.ast.Name(t0), "__iter__"), + [])), + + compiler.ast.Assign( + [compiler.ast.AssName(i0, "OP_ASSIGN")], + compiler.ast.Getattr(compiler.ast.Name(t1), "next")), # try: # while True: @@ -591,7 +592,7 @@ compiler.ast.Assign( [n.assign], compiler.ast.CallFunc( - compiler.ast.Name(self.get_iterator_name()), + compiler.ast.Name(i0), [] )), n.body]), @@ -600,7 +601,6 @@ None) ]) - self.next_iterator() self.process_structure_node(node) def process_literal_sequence_node(self, n, name, ref, cls): @@ -987,6 +987,185 @@ def same(s1, s2): return set(s1) == set(s2) +def order_dependencies(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. + """ + + 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 = {} + + # Record path-based dependencies. + + for key in all_depends.keys(): + usage[key] = set() + + for key, depends in all_depends.items(): + for depend in depends: + init_item(usage, depend, set) + usage[depend].add(key) + + 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. + + 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) + + 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 + + l.remove(key) # X needs (A) + + if needed: + l.update(needed) # X needs B... + + # Prevent self references. + + if depend in needed: + l.remove(depend) + + 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... + + # 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): + + """ + 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. + """ + + ordered.insert(0, key) + + depends = all_depends.get(key) + + # Reduce usage of the referenced items. + + if depends: + for depend in depends: + usage[depend].remove(key) + + del usage[key] + # General input/output. def readfile(filename): diff -r 479d30d89e05 -r 8e3fdfc663c9 deducer.py --- a/deducer.py Sat Mar 11 01:04:34 2017 +0100 +++ b/deducer.py Mon Mar 13 17:53:19 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() @@ -903,9 +904,11 @@ access_location = (path, None, attrname_str, 0) # Plain name accesses do not employ attributes and are - # ignored. + # ignored. Whether they are invoked is of interest, however. if not attrname_str: + if invocation: + self.reference_invocations[access_location] = invocation continue attrnames = get_attrnames(attrname_str) @@ -1016,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): @@ -1350,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. @@ -1518,6 +1537,9 @@ if not attrname: return + invocation = access_location in self.reference_invocations + assignment = access_location in self.reference_assignments + # Collect all suggested types for the accessors. Accesses may # require accessors from of a subset of the complete set of types. @@ -1547,7 +1569,7 @@ else: self.init_definition_details(location) - self.record_types_for_usage(location, [(attrname, False, False)]) + self.record_types_for_usage(location, [(attrname, invocation, assignment)]) constrained = location in self.accessor_constrained and constrained @@ -1609,36 +1631,64 @@ have_access = self.provider_class_types.has_key(accessor_location) # With an access, attempt to narrow the existing selection of provider - # types. + # types. Invocations attempt to find return value information, with + # instance return values also yielding class providers (since attributes + # on instances could be provided by classes). if have_access: provider_class_types = self.provider_class_types[accessor_location] provider_instance_types = self.provider_instance_types[accessor_location] provider_module_types = self.provider_module_types[accessor_location] + accessor_class_types = self.accessor_class_types[accessor_location] + accessor_instance_types = self.accessor_instance_types[accessor_location] + accessor_module_types = self.accessor_module_types[accessor_location] + # Find details for any corresponding access. - all_class_types = set() - all_instance_types = set() - all_module_types = set() + new_provider_class_types = set() + new_provider_instance_types = set() + new_provider_module_types = set() + + new_accessor_class_types = set() + new_accessor_instance_types = set() + new_accessor_module_types = set() for access_location in self.alias_index[accessor_location]: location, name, attrnames, access_number = access_location + invocation = self.reference_invocations.get(access_location) + + attrnames = attrnames and attrnames.split(".") + remaining = attrnames and len(attrnames) > 1 + + # Alias has remaining attributes: reference details do not + # correspond to the accessor; the remaining attributes would + # need to be traversed first. + + if remaining: + return # Alias references an attribute access. if attrnames: - # Obtain attribute references for the access. - - attrs = [] - for _attrtype, object_type, attr in self.referenced_attrs[access_location]: - attrs.append(attr) - - # Separate the different attribute types. - - (class_types, instance_types, module_types, - function_types, var_types) = separate_types(attrs) + # Obtain references and attribute types for the access. + + attrs = self.get_references_for_access(access_location) + + # Where no specific attributes are defined, do not attempt + # to refine the alias's types. + + if not attrs: + return + + # Invocations converting class accessors to instances do not + # change the nature of class providers. + + provider_attrs = self.convert_invocation_providers(attrs, invocation) + + (class_types, instance_types, module_types, function_types, + var_types) = separate_types(provider_attrs) # Where non-accessor types are found, do not attempt to refine # the defined accessor types. @@ -1650,6 +1700,26 @@ instance_types = set(provider_instance_types).intersection(instance_types) module_types = set(provider_module_types).intersection(module_types) + new_provider_class_types.update(class_types) + new_provider_instance_types.update(instance_types) + new_provider_module_types.update(module_types) + + # Accessors are updated separately, employing invocation + # result details. + + accessor_attrs = self.convert_invocations(attrs, invocation) + + (class_types, instance_types, module_types, function_types, + var_types) = separate_types(accessor_attrs) + + class_types = set(accessor_class_types).intersection(class_types) + instance_types = set(accessor_instance_types).intersection(instance_types) + module_types = set(accessor_module_types).intersection(module_types) + + new_accessor_class_types.update(class_types) + new_accessor_instance_types.update(instance_types) + new_accessor_module_types.update(module_types) + # Alias references a name, not an access. else: @@ -1657,8 +1727,32 @@ attr = self.get_initialised_name(access_location) if attr: - (class_types, instance_types, module_types, - _function_types, _var_types) = separate_types([attr]) + attrs = [attr] + provider_attrs = self.convert_invocation_providers(attrs, invocation) + + (class_types, instance_types, module_types, function_types, + var_types) = separate_types(provider_attrs) + + class_types = set(provider_class_types).intersection(class_types) + instance_types = set(provider_instance_types).intersection(instance_types) + module_types = set(provider_module_types).intersection(module_types) + + new_provider_class_types.update(class_types) + new_provider_instance_types.update(instance_types) + new_provider_module_types.update(module_types) + + accessor_attrs = self.convert_invocations(attrs, invocation) + + (class_types, instance_types, module_types, function_types, + var_types) = separate_types(accessor_attrs) + + class_types = set(accessor_class_types).intersection(class_types) + instance_types = set(accessor_instance_types).intersection(instance_types) + module_types = set(accessor_module_types).intersection(module_types) + + new_accessor_class_types.update(class_types) + new_accessor_instance_types.update(instance_types) + new_accessor_module_types.update(module_types) # Where no further information is found, do not attempt to # refine the defined accessor types. @@ -1666,16 +1760,15 @@ else: return - all_class_types.update(class_types) - all_instance_types.update(instance_types) - all_module_types.update(module_types) - # Record refined type details for the alias as an accessor. self.init_definition_details(accessor_location) - self.record_reference_types(accessor_location, all_class_types, all_instance_types, all_module_types, False) + 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) # Without an access, attempt to identify references for the alias. + # Invocations convert classes to instances and also attempt to find + # return value information. else: refs = set() @@ -1688,6 +1781,8 @@ access_location = self.const_accesses[access_location] location, name, attrnames, access_number = access_location + invocation = self.reference_invocations.get(access_location) + attrnames = attrnames and attrnames.split(".") remaining = attrnames and len(attrnames) > 1 @@ -1700,31 +1795,94 @@ # Alias references an attribute access. - attrname = attrnames and attrnames[0] - - if attrname: - attrs = [] - for attrtype, object_type, attr in self.referenced_attrs[access_location]: - attrs.append(attr) + if attrnames: + + # Obtain references and attribute types for the access. + + attrs = self.get_references_for_access(access_location) + attrs = self.convert_invocations(attrs, invocation) refs.update(attrs) # Alias references a name, not an access. else: + + # Obtain initialiser information. + attr = self.get_initialised_name(access_location) - attrs = attr and [attr] or [] - if not attrs and self.provider_class_types.has_key(access_location): + if attr: + refs.update(self.convert_invocations([attr], invocation)) + + # Obtain provider information. + + elif self.provider_class_types.has_key(access_location): class_types = self.provider_class_types[access_location] instance_types = self.provider_instance_types[access_location] module_types = self.provider_module_types[access_location] - attrs = combine_types(class_types, instance_types, module_types) - if attrs: - refs.update(attrs) + + types = combine_types(class_types, instance_types, module_types) + refs.update(self.convert_invocation_providers(types, invocation)) # Record reference details for the alias separately from accessors. self.referenced_objects[accessor_location] = refs + def get_references_for_access(self, access_location): + + "Return the references identified for 'access_location'." + + attrs = [] + for attrtype, object_type, attr in self.referenced_attrs[access_location]: + attrs.append(attr) + return attrs + + def convert_invocation_providers(self, refs, invocation): + + """ + Convert 'refs' to providers corresponding to the results of invoking + each of the given references, if 'invocation' is set to a true value. + """ + + if not invocation: + return refs + + providers = set() + + for ref in refs: + ref = self.convert_invocation_provider(ref) + if ref.has_kind(""): + providers.add(Reference("", ref.get_origin())) + providers.add(ref) + + return providers + + def convert_invocation_provider(self, ref): + + "Convert 'ref' to a provider appropriate to its invocation result." + + if ref and ref.has_kind(""): + return ref + + return Reference("") + + def convert_invocations(self, refs, invocation): + + """ + Convert 'refs' to invocation results if 'invocation' is set to a true + value. + """ + + return invocation and map(self.convert_invocation, refs) or refs + + def convert_invocation(self, ref): + + "Convert 'ref' to its invocation result." + + if ref and ref.has_kind(""): + return ref.instance_of() + + return Reference("") + def get_initialised_name(self, access_location): """ @@ -1770,15 +1928,13 @@ # Update the type details for the location. - self.provider_class_types[location].update(class_types) - self.provider_instance_types[location].update(instance_types) - self.provider_module_types[location].update(module_types) + self.update_provider_types(location, class_types, instance_types, module_types) # Class types support classes and instances as accessors. # Instance-only and module types support only their own kinds as # accessors. - path, name, version, attrnames = location + path, name, attrnames, version = location if invocations: class_only_types = self.filter_for_invocations(class_types, invocations) @@ -1802,6 +1958,28 @@ if constrained: self.accessor_constrained.add(location) + def update_provider_types(self, location, class_types, instance_types, module_types): + + """ + Update provider types for the given 'location', adding 'class_types', + 'instance_types' and 'module_types' to those already stored. + """ + + self.provider_class_types[location].update(class_types) + self.provider_instance_types[location].update(instance_types) + self.provider_module_types[location].update(module_types) + + def update_accessor_types(self, location, class_types, instance_types, module_types): + + """ + Update accessor types for the given 'location', adding 'class_types', + 'instance_types' and 'module_types' to those already stored. + """ + + self.accessor_class_types[location].update(class_types) + self.accessor_instance_types[location].update(instance_types) + self.accessor_module_types[location].update(module_types) + def filter_for_invocations(self, class_types, attrnames): """ diff -r 479d30d89e05 -r 8e3fdfc663c9 importer.py --- a/importer.py Sat Mar 11 01:04:34 2017 +0100 +++ b/importer.py Mon Mar 13 17:53:19 2017 +0100 @@ -23,7 +23,7 @@ from errors import ProgramError from os.path import exists, extsep, getmtime, join from os import listdir, makedirs, remove -from common import init_item, readfile, writefile +from common import init_item, order_dependencies, readfile, writefile from modules import CachedModule from referencing import Reference import inspector @@ -673,44 +673,10 @@ self.condense_dependencies() - # Record the number of modules using or depending on each module. - - usage = {} - - # Record path-based dependencies. - - for path in self.depends.keys(): - usage[path] = set() - - for path, depends in self.depends.items(): - for origin in depends: - init_item(usage, origin, set) - usage[origin].add(path) - - # Produce an ordering by obtaining exposed modules (required by modules - # already processed) and putting them at the start of the list. - - ordered = [] - - while usage: - have_next = False - - for path, n in usage.items(): - if not n: - ordered.insert(0, path) - depends = self.depends.get(path) - - # Reduce usage of the referenced objects. - - if depends: - for origin in depends: - usage[origin].remove(path) - - del usage[path] - have_next = True - - if not have_next: - raise ProgramError("Modules with unresolvable dependencies exist: %s" % ", ".join(usage.keys())) + try: + ordered = order_dependencies(self.depends) + except ValueError, exc: + raise ProgramError("Modules with unresolvable dependencies exist: %s" % ", ".join(exc.args[0].keys())) if "__main__" in ordered: ordered.remove("__main__") diff -r 479d30d89e05 -r 8e3fdfc663c9 inspector.py --- a/inspector.py Sat Mar 11 01:04:34 2017 +0100 +++ b/inspector.py Mon Mar 13 17:53:19 2017 +0100 @@ -766,7 +766,7 @@ if isinstance(name_ref, ResolvedNameRef) and name_ref.has_kind(""): return InstanceRef(name_ref.reference().instance_of()) - elif isinstance(name_ref, NameRef): + elif isinstance(name_ref, (NameRef, AccessRef)): return InvocationRef(name_ref) # Provide a general reference to indicate that something is produced @@ -902,7 +902,8 @@ branches = self.trackers[-1].tracking_name(name) if branches: self.record_branches_for_access(branches, name, None) - return self.record_access_details(name, None, None, None) + return self.record_access_details(name, None, self.in_assignment, + self.in_invocation) return None def process_operator_chain(self, nodes, fn): diff -r 479d30d89e05 -r 8e3fdfc663c9 resolving.py --- a/resolving.py Sat Mar 11 01:04:34 2017 +0100 +++ b/resolving.py Mon Mar 13 17:53:19 2017 +0100 @@ -283,13 +283,12 @@ # but they may be resolvable later. if not ref: - if not invocation: - # Record the path used for tracking purposes - # alongside original name, attribute and access - # number details. + # Record the path used for tracking purposes + # alongside original name, attribute and access + # number details. - aliased_names[i] = path, name_ref.original_name, name_ref.attrnames, name_ref.number + aliased_names[i] = path, name_ref.original_name, name_ref.attrnames, name_ref.number continue @@ -297,33 +296,30 @@ elif isinstance(name_ref, LocalNameRef): key = "%s.%s" % (path, name_ref.name) - origin = self.name_references.get(key) + ref = self.name_references.get(key) # Accesses that do not refer to known static objects # cannot be resolved, but they may be resolvable later. - if not origin: - if not invocation: + if not ref: - # Record the path used for tracking purposes - # alongside original name, attribute and access - # number details. + # Record the path used for tracking purposes + # alongside original name, attribute and access + # number details. - aliased_names[i] = path, name_ref.name, None, name_ref.number + aliased_names[i] = path, name_ref.name, None, name_ref.number continue - ref = self.get_resolved_object(origin) + ref = self.get_resolved_object(ref.get_origin()) if not ref: continue elif isinstance(name_ref, NameRef): key = "%s.%s" % (path, name_ref.name) - origin = self.name_references.get(key) - if not origin: - continue + ref = self.name_references.get(key) - ref = self.get_resolved_object(origin) + ref = ref and self.get_resolved_object(ref.get_origin()) if not ref: continue @@ -338,7 +334,7 @@ # Convert class invocations to instances. - if ref and invocation: + if ref and invocation or ref.has_kind(""): ref = self.convert_invocation(ref) if ref and not ref.has_kind(""): diff -r 479d30d89e05 -r 8e3fdfc663c9 templates/ops.c --- a/templates/ops.c Sat Mar 11 01:04:34 2017 +0100 +++ b/templates/ops.c Mon Mar 13 17:53:19 2017 +0100 @@ -34,17 +34,17 @@ __attr __load_static_ignore(__ref obj) { - return (__attr) {.value=obj}; + return __ATTRVALUE(obj); } __attr __load_static_replace(__ref context, __ref obj) { - return __update_context(context, (__attr) {.value=obj}); + return __update_context(context, __ATTRVALUE(obj)); } __attr __load_static_test(__ref context, __ref obj) { - return __test_context(context, (__attr) {.value=obj}); + return __test_context(context, __ATTRVALUE(obj)); } /* Direct retrieval operations, returning and setting attributes. */ @@ -281,9 +281,9 @@ { /* Set the local context to the specified context if appropriate. */ - if (__test_context_update(context, (__attr) {.value=value})) + if (__test_context_update(context, __ATTRVALUE(value))) contexts[target] = context; - return (__attr) {.value=value}; + return __ATTRVALUE(value); } /* Context testing for invocations. */ diff -r 479d30d89e05 -r 8e3fdfc663c9 translator.py --- a/translator.py Sat Mar 11 01:04:34 2017 +0100 +++ b/translator.py Mon Mar 13 17:53:19 2017 +0100 @@ -869,7 +869,7 @@ # Produce an appropriate access to an attribute's value. - name_to_value = "%s.value" % name + name_to_value = "%s.value" % encode_path(name) # Write a test that raises a TypeError upon failure. @@ -1440,7 +1440,7 @@ # Find any invocation or alias details. name = self.get_name_for_tracking(n.name, is_global=is_global) - location = not expr and self.get_access_location(name) + location = not expr and self.get_access_location(name) or None # Mark any local assignments as volatile in exception blocks.