# HG changeset patch # User Paul Boddie # Date 1472935424 -7200 # Node ID f836023496a3249ffe77d635eee7121105af48b7 # Parent ad44d74420568b05115ee31db151e17bac56bfdf Inspect modules one at a time with imports queued and inter-module dependencies deferred until all modules have been imported. Changed imports to only import specific modules, not the ancestors of modules in a descent to the indicated module. Reorganised the class hierarchy, introducing a separate name resolution mix-in. Removed import-related module attributes since the importer now tracks module relationships. diff -r ad44d7442056 -r f836023496a3 importer.py --- a/importer.py Sat Sep 03 22:38:21 2016 +0200 +++ b/importer.py Sat Sep 03 22:43:44 2016 +0200 @@ -49,11 +49,10 @@ self.cache = cache self.verbose = verbose + self.to_import = set() + self.modules = {} - self.modules_ordered = [] - self.loading = set() - self.hidden = {} - self.revealing = {} + self.accessing_modules = {} self.invalidated = set() self.objects = {} @@ -230,45 +229,33 @@ # Module management. + def queue_module(self, name, module): + + """ + Queue the module with the given 'name' for import from the given + 'module'. + """ + + if not self.modules.has_key(name): + self.to_import.add(name) + + init_item(self.accessing_modules, name, set) + self.accessing_modules[name].add(module.name) + def get_modules(self): "Return all modules known to the importer." return self.modules.values() - def get_module(self, name, hidden=False): + def get_module(self, name): "Return the module with the given 'name'." if not self.modules.has_key(name): return None - # Obtain the module and attempt to reveal it. - - module = self.modules[name] - if not hidden: - self.reveal_module(module) - return module - - def reveal_module(self, module): - - "Check if 'module' is hidden and reveal it." - - if module.name in self.hidden: - del self.hidden[module.name] - - # Reveal referenced modules. - - module.reveal_referenced() - - def set_revealing(self, module, name, instigator): - - """ - Make the revealing of 'module' conditional on 'name' for the given - 'instigator' of the reveal operation. - """ - - self.revealing[module.name].add((name, instigator)) + return self.modules[name] # Program operations. @@ -287,10 +274,20 @@ m = self.load_from_file(filename) + # Load any queued modules. + + while self.to_import: + for name in list(self.to_import): # avoid mutation issue + self.load(name) + + # Resolve dependencies between modules. + + self.resolve() + # Resolve dependencies within the program. - for module in self.modules_ordered: - module.resolve() + for module in self.modules.values(): + module.complete() return m @@ -299,12 +296,38 @@ "Finalise the inspected program." self.finalise_classes() - self.remove_hidden() self.to_cache() self.set_class_types() self.define_instantiators() self.collect_constants() + # Supporting operations. + + def resolve(self): + + "Resolve dependencies between modules." + + resolved = {} + + for name, ref in self.objects.items(): + if ref.has_kind(""): + ref = self.find_dependency(ref) + if ref: + resolved[name] = ref + + for name, ref in resolved.items(): + self.objects[name] = ref + + def find_dependency(self, ref): + + "Find the ultimate dependency for 'ref'." + + found = set() + while ref and ref.has_kind("") and not ref in found: + found.add(ref) + ref = self.objects.get(ref.get_origin()) + return ref + def finalise_classes(self): "Finalise the class relationships and attributes." @@ -395,41 +418,6 @@ if attrs: self.all_shadowed_attrs[name] = attrs - def remove_hidden(self): - - "Remove all hidden modules." - - # First reveal any modules exposing names. - - for modname, names in self.revealing.items(): - module = self.modules[modname] - - # Obtain the imported names and determine whether they should cause - # the module to be revealed. - - for (name, instigator) in names: - if module is not instigator: - - # Only if an object is provided by the module should the - # module be revealed. References to objects in other modules - # should not in themselves expose the module in which those - # references occur. - - ref = module.get_global(name) - if ref and ref.provided_by_module(module.name): - self.reveal_module(module) - instigator.revealed.add(module) - - # Then remove all modules that are still hidden. - - for modname in self.hidden: - module = self.modules[modname] - module.unpropagate() - del self.modules[modname] - ref = self.objects.get(modname) - if ref and ref.get_kind() == "": - del self.objects[modname] - def set_class_types(self): "Set the type of each class." @@ -533,30 +521,22 @@ else: return None - def load(self, name, return_leaf=False, hidden=False): + def load(self, name): """ Load the module or package with the given 'name'. Return an object referencing the loaded module or package, or None if no such module or package exists. - - Where 'return_leaf' is specified, the final module in the chain is - returned. Where 'hidden' is specified, the module is marked as hidden. """ - if return_leaf: - name_for_return = name - else: - name_for_return = name.split(".")[0] - # Loaded modules are returned immediately. # Modules may be known but not yet loading (having been registered as # submodules), loading, loaded, or completely unknown. - module = self.get_module(name, hidden) + module = self.get_module(name) if module: - return self.modules[name_for_return] + return self.modules[name] # Otherwise, modules are loaded. @@ -568,7 +548,7 @@ path = name.split(".") path_so_far = [] - top = module = None + module = None for p in path: @@ -593,18 +573,11 @@ # Get the module itself. d, filename = m - submodule = self.load_from_file(filename, module_name, hidden) - - if module is None: - top = submodule + module = self.load_from_file(filename, module_name) - module = submodule - - # Return either the deepest or the uppermost module. + return module - return return_leaf and module or top - - def load_from_file(self, filename, module_name=None, hidden=False): + def load_from_file(self, filename, module_name=None): "Load the module from the given 'filename'." @@ -617,7 +590,7 @@ # Try to load from cache. - module = self.load_from_cache(filename, module_name, hidden) + module = self.load_from_cache(filename, module_name) if module: return module @@ -627,10 +600,7 @@ self.add_module(module_name, module) self.update_cache_validity(module) - # Initiate loading if not already in progress. - - if not module.loaded and module not in self.loading: - self._load(module, module_name, hidden, lambda m: m.parse, filename) + self._load(module, module_name, lambda m: m.parse, filename) return module @@ -638,7 +608,9 @@ "Make 'module' valid in the cache, but invalidate accessing modules." - self.invalidated.update(module.accessing_modules) + accessing = self.accessing_modules.get(module.name) + if accessing: + self.invalidated.update(accessing) if module.name in self.invalidated: self.invalidated.remove(module.name) @@ -654,48 +626,35 @@ else: return True - def load_from_cache(self, filename, module_name, hidden=False): + def load_from_cache(self, filename, module_name): "Return a module residing in the cache." module = self.modules.get(module_name) - if not self.source_is_new(filename, module_name): + if not module and not self.source_is_new(filename, module_name): + module = inspector.CachedModule(module_name, self) + self.add_module(module_name, module) - if not module: - module = inspector.CachedModule(module_name, self) - self.add_module(module_name, module) - - if not module.loaded and module not in self.loading: - filename = join(self.cache, module_name) - self._load(module, module_name, hidden, lambda m: m.from_cache, filename) + filename = join(self.cache, module_name) + self._load(module, module_name, lambda m: m.from_cache, filename) return module - def _load(self, module, module_name, hidden, fn, filename): + def _load(self, module, module_name, fn, filename): """ - Load 'module' for the given 'module_name', with the module being hidden - if 'hidden' is a true value, and with 'fn' performing an invocation on - the module with the given 'filename'. + Load 'module' for the given 'module_name', and with 'fn' performing an + invocation on the module with the given 'filename'. """ - # Indicate that the module is hidden if requested. + # Load the module. - if hidden: - self.hidden[module_name] = module - - # Indicate that loading is in progress and load the module. - - self.loading.add(module) if self.verbose: print >>sys.stderr, "Loading", filename fn(module)(filename) if self.verbose: print >>sys.stderr, "Loaded", filename - self.loading.remove(module) - - self.modules_ordered.append(module) def add_module(self, module_name, module): @@ -706,5 +665,7 @@ self.modules[module_name] = module self.objects[module_name] = Reference("", module_name) + if module_name in self.to_import: + self.to_import.remove(module_name) # vim: tabstop=4 expandtab shiftwidth=4 diff -r ad44d7442056 -r f836023496a3 inspector.py --- a/inspector.py Sat Sep 03 22:38:21 2016 +0200 +++ b/inspector.py Sat Sep 03 22:43:44 2016 +0200 @@ -21,48 +21,23 @@ """ from branching import BranchTracker -from common import * -from modules import * -from os import listdir -from os.path import extsep, split, splitext +from common import get_argnames, init_item, predefined_constants +from modules import BasicModule, CacheWritingModule from referencing import Reference +from resolving import NameResolving +from results import AccessRef, InstanceRef, InvocationRef, LiteralSequenceRef, \ + LocalNameRef, NameRef, ResolvedNameRef import compiler import sys -class AccessRef(Result): - - """ - A reference to an attribute access that is generally only returned from a - processed access for possible initialiser resolution for assignments. - """ - - def __init__(self, original_name, attrnames, number): - self.original_name = original_name - self.attrnames = attrnames - self.number = number - - def reference(self): - return None - - def __repr__(self): - return "AccessRef(%r, %r, %r)" % (self.original_name, self.attrnames, self.number) - -class InvocationRef(Result): - - "An invocation of a name reference." - - def __init__(self, name_ref): - self.name_ref = name_ref - - def __repr__(self): - return "InvocationRef(%r)" % self.name_ref - -class InspectedModule(BasicModule, CacheWritingModule): +class InspectedModule(BasicModule, CacheWritingModule, NameResolving): "A module inspector." def __init__(self, name, importer): BasicModule.__init__(self, name, importer) + NameResolving.__init__(self) + self.in_class = False self.in_conditional = False self.global_attr_accesses = {} @@ -105,340 +80,21 @@ self.stop_tracking_in_module() - # Check names used and resolve them. - - self.register_submodules() - self.loaded = True - - def register_submodules(self): - - "For package modules add submodule details." - - if splitext(split(self.filename)[1])[0] == "__init__": - for subname in listdir(split(self.filename)[0]): - name, ext = splitext(subname) - - # Add modules whose names are not already defined as globals. - - if ext == ("%spy" % extsep) and name != "__init__" and not self.get_global(name): - module_name = self.get_global_path(name) - top, submodule = self.get_module(module_name, True) - self.set_module(name, submodule, hidden=True) - - def check_special(self): - - "Check special names." - - for name, value in self.special.items(): - if value.has_kind(""): - self.find_imported_name(name, self.name) - self.special[name] = self.get_object(value.get_origin()) - - def check_names_used(self): - - "Check the names used by each function." - - for path in self.names_used.keys(): - self.check_names_used_for_path(path) - - def check_names_used_for_path(self, path): - - "Check the names used by the given 'path'." + def complete(self): - names = self.names_used.get(path) - if not names: - return - - in_function = self.function_locals.has_key(path) - - for name in names: - if name in predefined_constants or in_function and name in self.function_locals[path]: - continue - - # Resolve names that have been imported locally. - - self.find_imported_name(name, path) - - # Find local definitions. - - key = "%s.%s" % (path, name) - ref = self.get_object(key) - if ref: - self.name_references[key] = ref.final() or key - self.resolve_accesses(path, name, ref) - continue - - # Resolve names that have been imported globally. - - self.find_imported_name(name, self.name) - - # Find global or built-in definitions. - - ref = self.get_global_or_builtin(name) - objpath = ref and (ref.final() or ref.get_name()) - if objpath: - self.name_references[key] = objpath - self.resolve_accesses(path, name, ref) - continue - - print >>sys.stderr, "Name not recognised: %s in %s" % (name, path) - init_item(self.names_missing, path, set) - self.names_missing[path].add(name) - - def resolve_members(self): + "Complete the module inspection." - "Resolve any members referring to deferred references." - - for name, ref in self.objects.items(): - if ref.has_kind(""): - ref = self.get_object(ref.get_origin()) - ref = ref.alias(name) - self.importer.objects[name] = self.objects[name] = ref - - def resolve_accesses(self, path, name, ref): - - """ - Resolve any unresolved accesses in the function at the given 'path' - for the given 'name' corresponding to the indicated 'ref'. Note that - this mechanism cannot resolve things like inherited methods because - they are not recorded as program objects in their inherited locations. - """ - - attr_accesses = self.global_attr_accesses.get(path) - all_attrnames = attr_accesses and attr_accesses.get(name) - - if not all_attrnames: - return - - # Insist on constant accessors. - - if not ref.has_kind(["", ""]): - return - - found_attrnames = set() - - for attrnames in all_attrnames: - - # Start with the resolved name, adding attributes. - - attrs = ref.get_path() - remaining = attrnames.split(".") - last_ref = ref - - # Add each component, testing for a constant object. + # Resolve names not definitively mapped to objects. - while remaining: - attrname = remaining[0] - attrs.append(attrname) - del remaining[0] - - # Find any constant object reference. - - attr_ref = self.get_object(".".join(attrs)) - - # Non-constant accessors terminate the traversal. - - if not attr_ref.has_kind(["", "", ""]): - - # Provide the furthest constant accessor unless the final - # access can be resolved. - - if remaining: - remaining.insert(0, attrs.pop()) - else: - last_ref = attr_ref - break - - # A module may expose an attribute imported from a hidden - # module. - - elif last_ref.has_kind(""): - module, leaf_module = self.get_module(last_ref.get_origin()) - self.find_imported_name(attrname, module.name, module) - - # Follow any reference to a constant object. - # Where the given name refers to an object in another location, - # switch to the other location in order to be able to test its - # attributes. - - last_ref = attr_ref - attrs = attr_ref.get_path() - - # Record a constant accessor only if an object was found - # that is different from the namespace involved. - - if last_ref: - objpath = ".".join(attrs) - if objpath != path: + self.resolve() - # Establish a constant access. - - init_item(self.const_accesses, path, dict) - self.const_accesses[path][(name, attrnames)] = (objpath, last_ref, ".".join(remaining)) - - if len(attrs) > 1: - found_attrnames.add(attrs[1]) - - # Remove any usage records for the name. - - if found_attrnames: - - # NOTE: Should be only one name version. - - versions = [] - for version in self.attr_usage[path][name]: - new_usage = set() - for usage in version: - if found_attrnames.intersection(usage): - new_usage.add(tuple(set(usage).difference(found_attrnames))) - else: - new_usage.add(usage) - versions.append(new_usage) - - self.attr_usage[path][name] = versions - - def resolve_initialisers(self): - - "Resolve initialiser values for names." - - # Get the initialisers in each namespace. - - for path, name_initialisers in self.name_initialisers.items(): - const_accesses = self.const_accesses.get(path) - - # Resolve values for each name in a scope. + # Define the invocation requirements in each namespace. - for name, values in name_initialisers.items(): - if path == self.name: - assigned_path = name - else: - assigned_path = "%s.%s" % (path, name) - - initialised_names = {} - aliased_names = {} - - for i, name_ref in enumerate(values): - - # Unwrap invocations. - - if isinstance(name_ref, InvocationRef): - invocation = True - name_ref = name_ref.name_ref - else: - invocation = False - - # Obtain a usable reference from names or constants. - - if isinstance(name_ref, ResolvedNameRef): - if not name_ref.reference(): - continue - ref = name_ref.reference() - - # Obtain a reference from instances. - - elif isinstance(name_ref, InstanceRef): - if not name_ref.reference(): - continue - ref = name_ref.reference() - - # Resolve accesses that employ constants. - - elif isinstance(name_ref, AccessRef): - ref = None - - if const_accesses: - resolved_access = const_accesses.get((name_ref.original_name, name_ref.attrnames)) - if resolved_access: - objpath, ref, remaining_attrnames = resolved_access - if remaining_attrnames: - ref = None + self.set_invocation_usage() - # Accesses that do not employ constants cannot be resolved, - # but they may be resolvable later. - - if not ref: - if not invocation: - aliased_names[i] = name_ref.original_name, name_ref.attrnames, name_ref.number - continue - - # Attempt to resolve a plain name reference. - - elif isinstance(name_ref, LocalNameRef): - key = "%s.%s" % (path, name_ref.name) - origin = 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: - aliased_names[i] = name_ref.name, None, name_ref.number - continue - - ref = self.get_object(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.get_object(origin) - if not ref: - continue - - else: - continue - - # Convert class invocations to instances. + # Propagate to the importer information needed in subsequent activities. - if invocation: - ref = ref.has_kind("") and ref.instance_of() or None - - if ref: - initialised_names[i] = ref - - if initialised_names: - self.initialised_names[assigned_path] = initialised_names - if aliased_names: - self.aliased_names[assigned_path] = aliased_names - - def resolve_literals(self): - - "Resolve constant value types." - - # Get the constants defined in each namespace. - - for path, constants in self.constants.items(): - for constant, n in constants.items(): - objpath = "%s.$c%d" % (path, n) - _constant, value_type = self.constant_values[objpath] - self.initialised_names[objpath] = {0 : Reference("", value_type)} - - # Get the literals defined in each namespace. - - for path, literals in self.literals.items(): - for n in range(0, literals): - objpath = "%s.$C%d" % (path, n) - value_type = self.literal_types[objpath] - self.initialised_names[objpath] = {0 : Reference("", value_type)} - - def remove_redundant_accessors(self): - - "Remove now-redundant modifier and accessor information." - - for path, const_accesses in self.const_accesses.items(): - accesses = self.attr_accessors.get(path) - modifiers = self.attr_access_modifiers.get(path) - if not accesses: - continue - for access in const_accesses.keys(): - if accesses.has_key(access): - del accesses[access] - if modifiers and modifiers.has_key(access): - del modifiers[access] + self.propagate() def set_invocation_usage(self): @@ -761,8 +417,8 @@ base_class = self.get_class(base) if not base_class: - print >>sys.stderr, "In %s, class %s has unidentifiable base classes." % ( - path, n.name) + print >>sys.stderr, "In %s, class %s has unidentifiable base class: %s" % ( + path, n.name, base) return else: bases.append(base_class) @@ -804,73 +460,23 @@ path = self.get_namespace_path() - modname, names = self.get_module_name(n) - - # Load the mentioned module. + module_name, names = self.get_module_name(n) + if module_name == self.name: + raise InspectError("Cannot import from the current module.", path, n) - top, module = self.get_module(modname, True) - self.set_module(None, module, hidden=True) - - if not module: - print >>sys.stderr, "In %s, from statement importing from %s failed." % ( - path, modname) + self.importer.queue_module(module_name, self) # Attempt to obtain the referenced objects. for name, alias in n.names: - - # NOTE: Package submodules are not implicitly imported. - if name == "*": - if module: - - # Warn about a circular import that probably doesn't find - # the names. - - if not module.loaded: - print >>sys.stderr, "In %s, from statement performs circular import %s of %s." % ( - path, modname) - - for name, value in module.get_globals().items(): - if name != "__name__": - value = ResolvedNameRef(name, value) - self.set_general_local(name, value) - self.set_imported_name(name, modname) - break + raise InspectError("Only explicitly specified names can be imported from modules.", path, n) # Explicit names. - ref = self.import_name_from_module(name, modname, module, alias) + ref = self.import_name_from_module(name, module_name) value = ResolvedNameRef(alias or name, ref) self.set_general_local(alias or name, value) - self.set_imported_name(name, modname, alias) - - def import_name_from_module(self, name, modname, module, alias=None): - - """ - Import 'name' from the module having the given 'modname', with 'module' - having been obtained for the module name, using 'alias' for the imported - name in the current namespace. - """ - - path = self.get_namespace_path() - - if module and module.get_global(name): - value = module.get_global(name) - - # Warn about an import that fails to provide a name, perhaps due - # to a circular import. - - if not value: - print >>sys.stderr, "In %s, from statement cannot import %s from %s%s." % ( - path, name, modname, not module.loaded and "(circular import)") - - return value - - # Record the name as a dependency. - - else: - return Reference("", "%s.%s" % (modname, name)) def process_function_node(self, n, name): @@ -1031,16 +637,13 @@ # Load the mentioned module. for name, alias in n.names: - module, leaf_module = self.get_module(name, alias) + if name == self.name: + raise InspectError("Cannot import the current module.", path, n) + if not alias and len(n.names) > 1: + raise InspectError("Imported modules must be aliased unless a simple module is imported.", path, n) - if not module: - print >>sys.stderr, "In %s, import statement importing from %s failed." % ( - path, name) - if module and not module.loaded: - print >>sys.stderr, "In %s, import statement performs circular import of %s." % ( - path, name) - - self.set_module(alias or name.split(".")[0], module, leaf_module) + self.set_module(alias or name.split(".")[0], name) + self.importer.queue_module(name, self) def process_invocation_node(self, n): @@ -1124,22 +727,12 @@ op = n.name[len("$op"):] - # Access the operator module. - - top, module = self.get_module("operator", True) - self.set_module(None, module, hidden=True) - - # Link the operation to the operator module definition in this - # module. - - self.set_imported_name(op, "operator", n.name, self.name) - # Attempt to get a reference. - ref = self.import_name_from_module(op, "operator", module) - ref = self.get_object("operator.%s" % op) or ref + ref = self.import_name_from_module(op, "operator") # Record the imported name and provide the resolved name reference. + # NOTE: Maybe use a different class. value = ResolvedNameRef(n.name, ref) self.set_special(n.name, value) @@ -1491,29 +1084,15 @@ init_item(self.names_used, path, set) self.names_used[path].add(name) - def set_module(self, name, module, leaf_module=None, hidden=False): + def set_module(self, name, module_name): """ - Set a module in the current namespace using the given 'name' and - corresponding 'module' object, with the 'leaf_module' being recorded - if different. If 'hidden' is a true value, the modules are recorded as - not necessarily being exposed by this module. This module is, however, - recorded as accessing the given modules and is thus dependent on them. + Set a module in the current namespace using the given 'name' associated + with the corresponding 'module_name'. """ if name: - self.set_general_local(name, module and Reference("", module.name) or None) - if module: - if hidden: - self.imported_hidden.add(module) - if leaf_module and leaf_module is not module: - self.imported_hidden.add(leaf_module) - else: - self.imported.add(module) - module.accessing_modules.add(self.name) - if leaf_module and leaf_module is not module: - self.imported.add(leaf_module) - leaf_module.accessing_modules.add(self.name) + self.set_general_local(name, Reference("", module_name)) def set_definition(self, name, kind): @@ -1688,16 +1267,16 @@ "Return a constant reference for the given type 'name' and 'value'." - ref = self.get_literal_builtin(name) + ref = self.get_builtin_class(name) return self.get_constant_reference(ref, value) def get_literal_instance(self, n, name): "For node 'n', return a reference to an instance of 'name'." - # Get a class reference. + # Get a reference to the built-in class. - ref = self.get_literal_builtin(name) + ref = self.get_builtin_class(name) # Obtain the details of the literal itself. # An alias to the type is generated for sequences. @@ -1711,31 +1290,6 @@ else: return self.get_constant_reference(ref, n.value) - def get_literal_builtin(self, name): - - "Return a reference for a built-in literal type of the given 'name'." - - ref = self.get_builtin(name) - true_origin = "__builtins__.%s.%s" % (name, name) - exposed_origin = "__builtins__.%s" % name - - # Obtain fully-imported built-in class references. - - if ref and ref.has_kind(""): - pass - - # Early-stage references need explicit references. - - elif ref: - ref = Reference("", true_origin) - - # Otherwise, the normal locations can be used. - - else: - ref = Reference("", true_origin, exposed_origin) - - return ref - # Functions and invocations. def allocate_arguments(self, path, args): diff -r ad44d7442056 -r f836023496a3 modules.py --- a/modules.py Sat Sep 03 22:38:21 2016 +0200 +++ b/modules.py Sat Sep 03 22:43:44 2016 +0200 @@ -20,9 +20,10 @@ this program. If not, see . """ -from common import * +from common import CommonModule from encoders import decode_modifier_term, encode_modifiers, encode_usage from referencing import decode_reference, Reference +from results import ResolvedNameRef import sys class BasicModule(CommonModule): @@ -32,18 +33,6 @@ def __init__(self, name, importer): CommonModule.__init__(self, name, importer) - # Import machinery links. - - self.loaded = False - - # Module dependencies. - - self.imported = set() - self.imported_hidden = set() - self.imported_names = {} - self.revealed = set() - self.accessing_modules = set() - # Global name information. self.objects = {} @@ -64,7 +53,6 @@ self.names_used = {} self.names_missing = {} - self.name_references = {} # references to globals # Function details. @@ -96,31 +84,9 @@ self.attr_access_modifiers = {} - # Initialisation-related details. - - self.initialised_names = {} - self.aliased_names = {} - def __repr__(self): return "BasicModule(%r, %r)" % (self.name, self.importer) - def resolve(self): - - "Resolve dependencies and complete definitions." - - self.resolve_class_bases() - self.check_special() - self.check_names_used() - self.resolve_members() - self.resolve_initialisers() - self.resolve_literals() - self.remove_redundant_accessors() - self.set_invocation_usage() - - # Propagate to the importer information needed in subsequent activities. - - self.propagate() - # Derived information methods. def propagate(self): @@ -176,36 +142,6 @@ if ref.get_kind() != "": del self.importer.objects[name] - def resolve_class_bases(self): - - "Resolve all class bases since some of them may have been deferred." - - for name, bases in self.classes.items(): - resolved = [] - bad = [] - - for base in bases: - - # Resolve dependencies. - - if base.has_kind(""): - ref = self.importer.get_object(base.get_origin()) - else: - ref = base - - # Obtain the origin of the base class reference. - - if not ref or not ref.has_kind(""): - bad.append(base) - break - - resolved.append(ref) - - if bad: - print >>sys.stderr, "Bases of class %s were not classes." % (name, ", ".join(map(str, bad))) - else: - self.importer.classes[name] = self.classes[name] = resolved - def propagate_attrs(self): "Derive attributes from the class and module member details." @@ -268,20 +204,6 @@ path = self.get_namespace_path() return name in self.scope_globals.get(path, []) - def get_globals(self): - - """ - Get the globals from this module, returning a dictionary mapping names - to references incorporating original definition details. - """ - - l = [] - for name, value in self.objects.items(): - parent, attrname = name.rsplit(".", 1) - if parent == self.name: - l.append((attrname, value)) - return dict(l) - def get_global(self, name): """ @@ -297,57 +219,38 @@ def get_global_or_builtin(self, name): """ - Return the object recorded the given 'name' from this module or from the - __builtins__ module. If no object has yet been defined, perhaps due to - circular module references, None is returned. + Return a reference for the given 'name' found in this module or in the + __builtins__. """ return self.get_global(name) or self.get_builtin(name) def get_builtin(self, name): - "Return the object providing the given built-in 'name'." - - path = "__builtins__.%s" % name - - # Obtain __builtins__. + "Return a reference to the built-in with the given 'name'." - module = self.ensure_builtins(path) - - # Attempt to find the named object within __builtins__. - - if module: - self.find_imported_name(name, module.name, module) + self.importer.queue_module("__builtins__", self) + return Reference("", "__builtins__.%s" % name) - # Return the path and any reference for the named object. + def get_builtin_class(self, name): - return self.importer.get_object(path) - - def ensure_builtins(self, path): + "Return a reference to the actual object providing 'name'." - """ - If 'path' is a reference to an object within __builtins__, return the - __builtins__ module. - """ + # NOTE: This makes assumptions about the __builtins__ structure. - if path.split(".", 1)[0] == "__builtins__": - return self.importer.load("__builtins__", True, True) - else: - return None + return Reference("", "__builtins__.%s.%s" % (name, name)) def get_object(self, path): """ - Get the details of an object with the given 'path', either from this - module or from the whole program. Return a tuple containing the path and - any object found. + Get the details of an object with the given 'path'. Where the object + cannot be resolved, an unresolved reference is returned. """ if self.objects.has_key(path): return self.objects[path] else: - self.ensure_builtins(path) - return self.importer.get_object(path) + return Reference("", path) def set_object(self, name, value=None): @@ -357,6 +260,14 @@ multiple = self.objects.has_key(name) and self.objects[name].get_kind() != ref.get_kind() self.importer.objects[name] = self.objects[name] = multiple and ref.as_var() or ref + def import_name_from_module(self, name, module_name): + + "Import 'name' from the module having the given 'module_name'." + + if module_name != self.name: + self.importer.queue_module(module_name, self) + return Reference("", "%s.%s" % (module_name, name)) + # Special names. def get_special(self, name): @@ -385,160 +296,6 @@ value = ResolvedNameRef(literal_name, ref) self.set_special(literal_name, value) - # Revealing modules by tracking name imports across modules. - - def set_imported_name(self, name, module_name, alias=None, path=None): - - """ - Record 'name' as being imported from the given 'module_name', employing - the given 'alias' in the local namespace if specified. - """ - - path = path or self.get_namespace_path() - init_item(self.imported_names, path, dict) - self.imported_names[path][alias or name] = (name, module_name) - - def get_imported_name(self, name, path): - - "Get details of any imported 'name' within the namespace at 'path'." - - if self.imported_names.has_key(path): - return self.imported_names[path].get(name) - else: - return None - - def find_imported_name(self, name, path, module=None): - - """ - Find details of the imported 'name' within the namespace at 'path', - starting within the given 'module' if indicated, or within this module - otherwise. - """ - - module = module or self - - # Obtain any module required by the name. - - name_modname = module.get_imported_name(name, path) - - if name_modname: - name, modname = name_modname - module = self._find_imported_name(name, modname, module) - - # Obtain the name from the final module, revealing it if appropriate. - - if module: - init_item(self.importer.revealing, module.name, set) - self.importer.set_revealing(module, name, self) - - def _find_imported_name(self, name, modname, module): - - """ - Traverse details for 'name' via 'modname' to the module providing the - name, tentatively revealing the module even if the module is not yet - loaded and cannot provide the details of the object recorded for the - name. - """ - - _name = name - - # Obtain any modules referenced by each required module. - - while True: - - # Get the module directly or traverse possibly-aliased names. - - module = self.get_module_direct(modname, True) - if not module: - top, module = self.get_module(modname, True) - name_modname = module.get_imported_name(_name, module.name) - if not name_modname: - break - else: - _name, modname = name_modname - - return module - - def reveal_referenced(self): - - """ - Reveal modules referenced by this module. - """ - - for path, names in self.imported_names.items(): - for alias, (name, modname) in names.items(): - module = self._find_imported_name(name, modname, self) - self.reveal_module(module) - - def reveal_module(self, module): - - """ - Reveal the given 'module', recording the revealed modules on this - module. - """ - - if module is not self: - self.importer.reveal_module(module) - self.revealed.add(module) - module.accessing_modules.add(self.name) - - # Module loading. - - def get_module_direct(self, modname, hidden=False): - - """ - Return 'modname' without traversing parent modules, keeping the module - 'hidden' if set to a true value, loading the module if not already - loaded. - """ - - return self.importer.get_module(modname, True) or self.importer.load(modname, hidden=hidden) - - def get_module(self, name, hidden=False): - - """ - Use the given 'name' to obtain the identity of a module. Return module - objects or None if the module cannot be found. This method is required - when aliases are used to refer to modules and where a module "path" does - not correspond to the actual module path. - - A tuple is returned containing the top or base module and the deepest or - leaf module involved. - """ - - path_so_far = [] - top = module = None - parts = name.split(".") - - for i, part in enumerate(parts): - path_so_far.append(part) - module_name = ".".join(path_so_far) - ref = self.get_object(module_name) - - # If no known object exists, attempt to load it. - - if not ref: - module = self.importer.load(module_name, True, hidden) - if not module: - return None - - # Rewrite the path to use the actual module details. - - path_so_far = module.name.split(".") - - # If the object exists and is not a module, stop. - - elif ref.has_kind(["", "", ""]): - return None - - else: - module = self.importer.get_module(ref.get_origin(), hidden) - - if not top: - top = module - - return top, module - class CachedModule(BasicModule): "A cached module." @@ -546,9 +303,6 @@ def __repr__(self): return "CachedModule(%r, %r)" % (self.name, self.importer) - def resolve(self): - pass - def to_cache(self, filename): "Not actually writing the module back to 'filename'." @@ -566,27 +320,8 @@ try: self.filename = f.readline().rstrip() - accessing_modules = f.readline().split(": ", 1)[-1].rstrip() - - module_names = f.readline().split(": ", 1)[-1].rstrip() - if module_names: - for module_name in module_names.split(", "): - self.imported.add(self.importer.load(module_name)) - - module_names = f.readline().split(": ", 1)[-1].rstrip() - if module_names: - for module_name in module_names.split(", "): - self.imported_hidden.add(self.importer.load(module_name, hidden=True)) - - module_names = f.readline().split(": ", 1)[-1].rstrip() - if module_names: - for module_name in module_names.split(", "): - module = self.importer.load(module_name, True, True) - self.reveal_module(module) - f.readline() # (empty line) - self._get_imported_names(f) self._get_members(f) self._get_class_relationships(f) self._get_instance_attrs(f) @@ -613,20 +348,9 @@ finally: f.close() - self.loaded = True - - def resolve(self): + def complete(self): self.propagate() - def _get_imported_names(self, f): - f.readline() # "imported names:" - line = f.readline().rstrip() - while line: - path, alias_or_name, name, module_name = self._get_fields(line, 4) - init_item(self.imported_names, path, dict) - self.imported_names[path][alias_or_name] = (name, module_name) - line = f.readline().rstrip() - def _get_members(self, f): f.readline() # "members:" line = f.readline().rstrip() @@ -885,13 +609,6 @@ format to the file having the given 'filename': filename - "accessed by:" accessing module names during this module's import - "imports:" imported module names - "hidden imports:" imported module names - "reveals:" revealed module names - (empty line) - "imported names:" - zero or more: qualified name " " name " " module name (empty line) "members:" zero or more: qualified name " " reference @@ -988,33 +705,6 @@ try: print >>f, self.filename - accessing_modules = list(self.accessing_modules) - accessing_modules.sort() - print >>f, "accessed by:", ", ".join(accessing_modules) - - module_names = [m.name for m in self.imported] - module_names.sort() - print >>f, "imports:", ", ".join(module_names) - - module_names = [m.name for m in self.imported_hidden] - module_names.sort() - print >>f, "hidden imports:", ", ".join(module_names) - - module_names = [m.name for m in self.revealed] - module_names.sort() - print >>f, "reveals:", ", ".join(module_names) - - print >>f - print >>f, "imported names:" - paths = self.imported_names.keys() - paths.sort() - for path in paths: - names = self.imported_names[path].keys() - names.sort() - for alias_or_name in names: - name, modname = self.imported_names[path][alias_or_name] - print >>f, path, alias_or_name, name, modname - print >>f print >>f, "members:" objects = self.objects.keys() diff -r ad44d7442056 -r f836023496a3 resolving.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/resolving.py Sat Sep 03 22:43:44 2016 +0200 @@ -0,0 +1,409 @@ +#!/usr/bin/env python + +""" +Name resolution. + +Copyright (C) 2016 Paul Boddie + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; either version 3 of the License, or (at your option) any later +version. + +This program is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +details. + +You should have received a copy of the GNU General Public License along with +this program. If not, see . +""" + +from common import init_item, predefined_constants +from results import AccessRef, InstanceRef, InvocationRef, LocalNameRef, \ + NameRef, ResolvedNameRef +from referencing import Reference +import sys + +class NameResolving: + + "Resolving names mix-in for inspected modules." + + def __init__(self): + self.name_references = {} # references to globals + + # Initialisation-related details. + + self.initialised_names = {} + self.aliased_names = {} + + # Object resolution. + + def resolve_object(self, ref): + + """ + Return the given 'ref' in resolved form, given knowledge of the entire + program. + """ + + if ref.has_kind(""): + return self.importer.get_object(ref.get_origin()) + else: + return ref + + def get_resolved_object(self, path): + + """ + Get the details of an object with the given 'path'. Where the object + has not been resolved, None is returned. This differs from the + get_object method used elsewhere in that it does not return an + unresolved object reference. + """ + + if self.objects.has_key(path): + ref = self.objects[path] + if ref.has_kind(""): + return None + else: + return ref + else: + return None + + # Post-inspection resolution activities. + + def resolve(self): + + "Resolve dependencies and complete definitions." + + self.resolve_members() + self.resolve_class_bases() + #self.check_special() + self.check_names_used() + self.resolve_initialisers() + self.resolve_literals() + self.remove_redundant_accessors() + + def resolve_members(self): + + "Resolve any members referring to deferred references." + + for name, ref in self.objects.items(): + if ref.has_kind(""): + ref = self.importer.get_object(name) + ref = ref.alias(name) + self.importer.objects[name] = self.objects[name] = ref + + def resolve_class_bases(self): + + "Resolve all class bases since some of them may have been deferred." + + for name, bases in self.classes.items(): + resolved = [] + bad = [] + + for base in bases: + ref = self.resolve_object(base) + + # Obtain the origin of the base class reference. + + if not ref or not ref.has_kind(""): + bad.append(base) + break + + resolved.append(ref) + + if bad: + print >>sys.stderr, "Bases of class %s were not classes." % (name, ", ".join(map(str, bad))) + else: + self.importer.classes[name] = self.classes[name] = resolved + + def check_special(self): + + "Check special names." + + for name, value in self.special.items(): + # NOTE: Needs to handle Ref classes. + self.special[name] = self.get_resolved_object(value.get_origin()) + + def check_names_used(self): + + "Check the names used by each function." + + for path in self.names_used.keys(): + self.check_names_used_for_path(path) + + def check_names_used_for_path(self, path): + + "Check the names used by the given 'path'." + + names = self.names_used.get(path) + if not names: + return + + in_function = self.function_locals.has_key(path) + + for name in names: + if name in predefined_constants or in_function and name in self.function_locals[path]: + continue + + # Find local definitions (within static namespaces). + + key = "%s.%s" % (path, name) + ref = self.get_resolved_object(key) + if ref: + self.name_references[key] = ref.final() or key + self.resolve_accesses(path, name, ref) + continue + + # Find global or built-in definitions. + + ref = self.get_global_or_builtin(name) + objpath = ref and (ref.final() or ref.get_name()) + if objpath: + self.name_references[key] = objpath + self.resolve_accesses(path, name, ref) + continue + + print >>sys.stderr, "Name not recognised: %s in %s" % (name, path) + init_item(self.names_missing, path, set) + self.names_missing[path].add(name) + + def resolve_accesses(self, path, name, ref): + + """ + Resolve any unresolved accesses in the function at the given 'path' + for the given 'name' corresponding to the indicated 'ref'. Note that + this mechanism cannot resolve things like inherited methods because + they are not recorded as program objects in their inherited locations. + """ + + attr_accesses = self.global_attr_accesses.get(path) + all_attrnames = attr_accesses and attr_accesses.get(name) + + if not all_attrnames: + return + + # Insist on constant accessors. + + if not ref.has_kind(["", ""]): + return + + found_attrnames = set() + + for attrnames in all_attrnames: + + # Start with the resolved name, adding attributes. + + attrs = ref.get_path() + remaining = attrnames.split(".") + last_ref = ref + + # Add each component, testing for a constant object. + + while remaining: + attrname = remaining[0] + attrs.append(attrname) + del remaining[0] + + # Find any constant object reference. + + attr_ref = self.get_resolved_object(".".join(attrs)) + + # Non-constant accessors terminate the traversal. + + if not attr_ref or not attr_ref.has_kind(["", "", ""]): + + # Provide the furthest constant accessor unless the final + # access can be resolved. + + if remaining: + remaining.insert(0, attrs.pop()) + else: + last_ref = attr_ref + break + + # Follow any reference to a constant object. + # Where the given name refers to an object in another location, + # switch to the other location in order to be able to test its + # attributes. + + last_ref = attr_ref + attrs = attr_ref.get_path() + + # Record a constant accessor only if an object was found + # that is different from the namespace involved. + + if last_ref: + objpath = ".".join(attrs) + if objpath != path: + + # Establish a constant access. + + init_item(self.const_accesses, path, dict) + self.const_accesses[path][(name, attrnames)] = (objpath, last_ref, ".".join(remaining)) + + if len(attrs) > 1: + found_attrnames.add(attrs[1]) + + # Remove any usage records for the name. + + if found_attrnames: + + # NOTE: Should be only one name version. + + versions = [] + for version in self.attr_usage[path][name]: + new_usage = set() + for usage in version: + if found_attrnames.intersection(usage): + new_usage.add(tuple(set(usage).difference(found_attrnames))) + else: + new_usage.add(usage) + versions.append(new_usage) + + self.attr_usage[path][name] = versions + + def resolve_initialisers(self): + + "Resolve initialiser values for names." + + # Get the initialisers in each namespace. + + for path, name_initialisers in self.name_initialisers.items(): + const_accesses = self.const_accesses.get(path) + + # Resolve values for each name in a scope. + + for name, values in name_initialisers.items(): + if path == self.name: + assigned_path = name + else: + assigned_path = "%s.%s" % (path, name) + + initialised_names = {} + aliased_names = {} + + for i, name_ref in enumerate(values): + + # Unwrap invocations. + + if isinstance(name_ref, InvocationRef): + invocation = True + name_ref = name_ref.name_ref + else: + invocation = False + + # Obtain a usable reference from names or constants. + + if isinstance(name_ref, ResolvedNameRef): + if not name_ref.reference(): + continue + ref = name_ref.reference() + + # Obtain a reference from instances. + + elif isinstance(name_ref, InstanceRef): + if not name_ref.reference(): + continue + ref = name_ref.reference() + + # Resolve accesses that employ constants. + + elif isinstance(name_ref, AccessRef): + ref = None + + if const_accesses: + resolved_access = const_accesses.get((name_ref.original_name, name_ref.attrnames)) + if resolved_access: + objpath, ref, remaining_attrnames = resolved_access + if remaining_attrnames: + ref = None + + # Accesses that do not employ constants cannot be resolved, + # but they may be resolvable later. + + if not ref: + if not invocation: + aliased_names[i] = name_ref.original_name, name_ref.attrnames, name_ref.number + continue + + # Attempt to resolve a plain name reference. + + elif isinstance(name_ref, LocalNameRef): + key = "%s.%s" % (path, name_ref.name) + origin = 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: + aliased_names[i] = name_ref.name, None, name_ref.number + continue + + ref = self.get_resolved_object(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.get_resolved_object(origin) + if not ref: + continue + + else: + continue + + # Convert class invocations to instances. + + if invocation: + ref = ref.has_kind("") and ref.instance_of() or None + + if ref: + initialised_names[i] = ref + + if initialised_names: + self.initialised_names[assigned_path] = initialised_names + if aliased_names: + self.aliased_names[assigned_path] = aliased_names + + def resolve_literals(self): + + "Resolve constant value types." + + # Get the constants defined in each namespace. + + for path, constants in self.constants.items(): + for constant, n in constants.items(): + objpath = "%s.$c%d" % (path, n) + _constant, value_type = self.constant_values[objpath] + self.initialised_names[objpath] = {0 : Reference("", value_type)} + + # Get the literals defined in each namespace. + + for path, literals in self.literals.items(): + for n in range(0, literals): + objpath = "%s.$C%d" % (path, n) + value_type = self.literal_types[objpath] + self.initialised_names[objpath] = {0 : Reference("", value_type)} + + def remove_redundant_accessors(self): + + "Remove now-redundant modifier and accessor information." + + for path, const_accesses in self.const_accesses.items(): + accesses = self.attr_accessors.get(path) + modifiers = self.attr_access_modifiers.get(path) + if not accesses: + continue + for access in const_accesses.keys(): + if accesses.has_key(access): + del accesses[access] + if modifiers and modifiers.has_key(access): + del modifiers[access] + +# vim: tabstop=4 expandtab shiftwidth=4