text: """
  Find modules used by a script, using bytecode analysis.
  
  Based on the stdlib modulefinder by Thomas Heller and Just van Rossum,
  but uses a graph data structure and 2.3 features
  
  XXX: Verify all calls to _import_hook (and variants) to ensure that
  imports are done in the right way.
  """
  from __future__ import absolute_import, print_function
  
  #FIXME: To decrease the likelihood of ModuleGraph exceeding the recursion limit
  #and hence unpredictably raising fatal exceptions, increase the recursion
  #limit at PyInstaller startup (i.e., in the
  #PyInstaller.building.build_main.build() function). For details, see:
  #    https://github.com/pyinstaller/pyinstaller/issues/1919#issuecomment-216016176
  
  import pkg_resources
  
  import ast
  import dis
  import imp
  import marshal
  import os
  import pkgutil
  import sys
  import re
  from collections import deque, namedtuple
  from struct import unpack
  
  from ..altgraph.ObjectGraph import ObjectGraph
  from ..altgraph import GraphError
  
  from . import util
  from . import zipio
  from ._compat import get_instructions, BytesIO, StringIO, \
       pathname2url, _cOrd, _READ_MODE
  
  
  import codecs
  BOM = codecs.BOM_UTF8.decode('utf-8')
  
  
  #FIXME: Leverage this rather than magic numbers below.
  ABSOLUTE_OR_RELATIVE_IMPORT_LEVEL = -1
  """
  Constant instructing the builtin `__import__()` function to attempt both
  absolute and relative imports.
  """
  
  
  #FIXME: Leverage this rather than magic numbers below.
  ABSOLUTE_IMPORT_LEVEL = 0
  """
  Constant instructing the builtin `__import__()` function to attempt only
  absolute imports.
  """
  
  
  #FIXME: Leverage this rather than magic numbers below.
  DEFAULT_IMPORT_LEVEL = (
      ABSOLUTE_OR_RELATIVE_IMPORT_LEVEL if sys.version_info[0] == 2 else
      ABSOLUTE_IMPORT_LEVEL)
  """
  Constant instructing the builtin `__import__()` function to attempt the default
  import style specific to the active Python interpreter.
  
  Specifically, under:
  
  * Python 2, this defaults to attempting both absolute and relative imports.
  * Python 3, this defaults to attempting only absolute imports.
  """
  
  # TODO: Refactor all uses of explicit filetypes in this module *AND* of the
  # imp.get_suffixes() function to use this dictionary instead. Unfortunately,
  # tests for explicit filetypes (e.g., ".py") are non-portable. Under Windows,
  # for example, both the ".py" *AND* ".pyw" filetypes signify valid uncompiled
  # Python modules.
  # TODO: The imp.get_suffixes() function (in fact, the entire "imp" package) has
  # been deprecated as of Python 3.3 by the importlib.machinery.all_suffixes()
  # function, which largely performs the same role. Unfortunately, the latter
  # function was only introduced with Python 3.3. Since PyInstaller requires
  # Python >= 3.3 when running under Python 3, refactor this as follows:
  #
  # * Under Python 2, continue calling imp.get_suffixes().
  # * Under Python 3, call importlib.machinery.all_suffixes() instead.
  _IMPORTABLE_FILETYPE_TO_METADATA = {
      filetype: (filetype, open_mode, imp_type)
      for filetype, open_mode, imp_type in imp.get_suffixes()
  }
  """
  Dictionary mapping the filetypes of importable files to the 3-tuple of metadata
  describing such files returned by the `imp.get_suffixes()` function whose first
  element is that filetype.
  
  This dictionary simplifies platform-portable importation of importable files,
  including:
  
  * Uncompiled modules suffixed by `.py` (as well as `.pyw` under Windows).
  * Compiled modules suffixed by either `.pyc` or `.pyo`.
  * C extensions suffixed by the platform-specific shared library filetype (e.g.,
    `.so` under Linux, `.dll` under Windows).
  
  The keys of this dictionary are `.`-prefixed filetypes (e.g., `.py`, `.so');
  the values of this dictionary are 3-tuples whose:
  
  1. First element is the same `.`-prefixed filetype.
  1. Second element is the mode to be passed to the `open()` built-in to open
     files of that filetype under the current platform and Python interpreter
     (e.g., `rU` for the `.py` filetype under Python 2, `r` for the same
     filetype under Python 3).
  1. Third element is a magic number specific to the `imp` module (e.g.,
     `imp.C_EXTENSION` for filetypes corresponding to C extensions).
  """
  
  
  
  # Modulegraph does a good job at simulating Python's, but it can not
  # handle packagepath modifications packages make at runtime.  Therefore there
  # is a mechanism whereby you can register extra paths in this map for a
  # package, and it will be honored.
  #
  # Note this is a mapping is lists of paths.
  _packagePathMap = {}
  
  # Prefix used in magic .pth files used by setuptools to create namespace
  # packages without an __init__.py file.
  #
  # The value is a list of such prefixes as the prefix varies with versions of
  # setuptools.
  _SETUPTOOLS_NAMESPACEPKG_PTHs=(
      "import sys, types, os;has_mfs = sys.version_info > (3, 5);p = os.path.join(sys._getframe(1).f_locals['sitedir'], *('",
      "import sys,types,os; p = os.path.join(sys._getframe(1).f_locals['sitedir'], *('",
      "import sys,new,os; p = os.path.join(sys._getframe(1).f_locals['sitedir'], *('",
      "import sys, types, os;p = os.path.join(sys._getframe(1).f_locals['sitedir'], *('",
      "import sys, types, os;pep420 = sys.version_info > (3, 3);p = os.path.join(sys._getframe(1).f_locals['sitedir'], *('",
  )
  
  
  def _namespace_package_path(fqname, pathnames, path=None):
      """
      Return the __path__ for the python package in *fqname*.
  
      This function uses setuptools metadata to extract information
      about namespace packages from installed eggs.
      """
      working_set = pkg_resources.WorkingSet(path)
  
      path = list(pathnames)
  
      for dist in working_set:
          if dist.has_metadata('namespace_packages.txt'):
              namespaces = dist.get_metadata(
                      'namespace_packages.txt').splitlines()
              if fqname in namespaces:
                  nspath = os.path.join(dist.location, *fqname.split('.'))
                  if nspath not in path:
                      path.append(nspath)
  
      return path
  
  _strs = re.compile(r'''^\s*["']([A-Za-z0-9_]+)["'],?\s*''') # "<- emacs happy
  
  def _eval_str_tuple(value):
      """
      Input is the repr of a tuple of strings, output
      is that tuple.
  
      This only works with a tuple where the members are
      python identifiers.
      """
      if not (value.startswith('(') and value.endswith(')')):
          raise ValueError(value)
  
      orig_value = value
      value = value[1:-1]
  
      result = []
      while value:
          m = _strs.match(value)
          if m is None:
              raise ValueError(orig_value)
  
          result.append(m.group(1))
          value = value[len(m.group(0)):]
  
      return tuple(result)
  
  def _path_from_importerror(exc, default):
      # This is a hack, but sadly enough the necessary information
      # isn't available otherwise.
      m = re.match('^No module named (\S+)$', str(exc))
      if m is not None:
          return m.group(1)
  
      return default
  
  def os_listdir(path):
      """
      Deprecated name
      """
      warnings.warn("Use zipio.listdir instead of os_listdir",
              DeprecationWarning)
      return zipio.listdir(path)
  
  
  def _code_to_file(co):
      """ Convert code object to a .pyc pseudo-file """
      return BytesIO(
              imp.get_magic() + b'\0\0\0\0' + marshal.dumps(co))
  
  def moduleInfoForPath(path):
      for (ext, readmode, typ) in imp.get_suffixes():
          if path.endswith(ext):
              return os.path.basename(path)[:-len(ext)], readmode, typ
      return None
  
  # A Public interface
  import warnings
  def AddPackagePath(packagename, path):
      warnings.warn("Use addPackagePath instead of AddPackagePath",
              DeprecationWarning)
  
      addPackagePath(packagename, path)
  
  def addPackagePath(packagename, path):
      paths = _packagePathMap.get(packagename, [])
      paths.append(path)
      _packagePathMap[packagename] = paths
  
  _replacePackageMap = {}
  
  # This ReplacePackage mechanism allows modulefinder to work around the
  # way the _xmlplus package injects itself under the name "xml" into
  # sys.modules at runtime by calling ReplacePackage("_xmlplus", "xml")
  # before running ModuleGraph.
  def ReplacePackage(oldname, newname):
      warnings.warn("use replacePackage instead of ReplacePackage",
              DeprecationWarning)
      replacePackage(oldname, newname)
  
  def replacePackage(oldname, newname):
      _replacePackageMap[oldname] = newname
  
  
  #FIXME: What is this? Do we actually need this? This appears to provide
  #significantly more fine-grained metadata than PyInstaller will ever require.
  #It consumes a great deal of space (slots or no slots), since we store an
  #instance of this class for each edge of the graph.
  class DependencyInfo (namedtuple("DependencyInfo", ["conditional", "function", "tryexcept", "fromlist"])):
      __slots__ = ()
  
      def _merged(self, other):
          if (not self.conditional and not self.function and not self.tryexcept) \
                  or (not other.conditional and not other.function and not other.tryexcept):
              return DependencyInfo(conditional=False, function=False, tryexcept=False, fromlist=self.fromlist and other.fromlist)
  
          else:
              return DependencyInfo(
                      conditional=self.conditional or other.conditional,
                      function=self.function or other.function,
                      tryexcept=self.tryexcept or other.tryexcept,
                      fromlist=self.fromlist and other.fromlist)
  
  
  #FIXME: Shift the following Node class hierarchy into a new
  #"PyInstaller.lib.modulegraph.node" module. This module is much too long.
  #FIXME: Refactor "_deferred_imports" from a tuple into a proper lightweight
  #class leveraging "__slots__". If not for backward compatibility, we'd just
  #leverage a named tuple -- but this should do just as well.
  #FIXME: Move the "packagepath" attribute into the "Package" class. Only
  #packages define the "__path__" special attribute. The codebase currently
  #erroneously tests whether "module.packagepath is not None" to determine
  #whether a node is a package or not. However, "isinstance(module, Package)" is
  #a significantly more reliable test. Refactor the former into the latter.
  class Node(object):
      """
      Abstract base class (ABC) of all objects added to a `ModuleGraph`.
  
      Attributes
      ----------
      code : codeobject
          Code object of the pure-Python module corresponding to this graph node
          if any _or_ `None` otherwise.
      graphident : str
          Synonym of `identifier` required by the `ObjectGraph` superclass of the
          `ModuleGraph` class. For readability, the `identifier` attribute should
          typically be used instead.
      filename : str
          Absolute path of this graph node's corresponding module, package, or C
          extension if any _or_ `None` otherwise.
      identifier : str
          Fully-qualified name of this graph node's corresponding module,
          package, or C extension.
      packagepath : str
          List of the absolute paths of all directories comprising this graph
          node's corresponding package. If this is a:
          * Non-namespace package, this list contains exactly one path.
          * Namespace package, this list contains one or more paths.
      _deferred_imports : list
          List of all target modules imported by the source module corresponding
          to this graph node whole importations have been deferred for subsequent
          processing in between calls to the `_ModuleGraph._scan_code()` and
          `_ModuleGraph._process_imports()` methods for this source module _or_
          `None` otherwise. Each element of this list is a 3-tuple
          `(have_star, _safe_import_hook_args, _safe_import_hook_kwargs)`
          collecting the importation of a target module from this source module
          for subsequent processing, where:
          * `have_star` is a boolean `True` only if this is a `from`-style star
            import (e.g., resembling `from {target_module_name} import *`).
          * `_safe_import_hook_args` is a (typically non-empty) sequence of all
            positional arguments to be passed to the `_safe_import_hook()` method
            to add this importation to the graph.
          * `_safe_import_hook_kwargs` is a (typically empty) dictionary of all
            keyword arguments to be passed to the `_safe_import_hook()` method
            to add this importation to the graph.
          Unlike functional languages, Python imposes a maximum depth on the
          interpreter stack (and hence recursion). On breaching this depth,
          Python raises a fatal `RuntimeError` exception. Since `ModuleGraph`
          parses imports recursively rather than iteratively, this depth _was_
          commonly breached before the introduction of this list. Python
          environments installing a large number of modules (e.g., Anaconda) were
          particularly susceptible. Why? Because `ModuleGraph` concurrently
          descended through both the abstract syntax trees (ASTs) of all source
          modules being parsed _and_ the graph of all target modules imported by
          these source modules being built. The stack thus consisted of
          alternating layers of AST and graph traversal. To unwind such
          alternation and effectively halve the stack depth, `ModuleGraph` now
          descends through the abstract syntax tree (AST) of each source module
          being parsed and adds all importations originating within this module
          to this list _before_ descending into the graph of these importations.
          See pyinstaller/pyinstaller/#1289 for further details.
      _global_attr_names : set
          Set of the unqualified names of all global attributes (e.g., classes,
          variables) defined in the pure-Python module corresponding to this
          graph node if any _or_ the empty set otherwise. This includes the names
          of all attributes imported via `from`-style star imports from other
          existing modules (e.g., `from {target_module_name} import *`). This
          set is principally used to differentiate the non-ignorable importation
          of non-existent submodules in a package from the ignorable importation
          of existing global attributes defined in that package's pure-Python
          `__init__` submodule in `from`-style imports (e.g., `bar` in
          `from foo import bar`, which may be either a submodule or attribute of
          `foo`), as such imports ambiguously allow both. This set is _not_ used
          to differentiate submodules from attributes in `import`-style imports
          (e.g., `bar` in `import foo.bar`, which _must_ be a submodule of
          `foo`), as such imports unambiguously allow only submodules.
      _starimported_ignored_module_names : set
          Set of the fully-qualified names of all existing unparsable modules
          that the existing parsable module corresponding to this graph node
          attempted to perform one or more "star imports" from. If this module
          either does _not_ exist or does but is unparsable, this is the empty
          set. Equivalently, this set contains each fully-qualified name
          `{trg_module_name}` for which:
          * This module contains an import statement of the form
            `from {trg_module_name} import *`.
          * The module whose name is `{trg_module_name}` exists but is _not_
            parsable by `ModuleGraph` (e.g., due to _not_ being pure-Python).
          **This set is currently defined but otherwise ignored.**
      _submodule_basename_to_node : dict
          Dictionary mapping from the unqualified name of each submodule
          contained by the parent module corresponding to this graph node to that
          submodule's graph node. If this dictionary is non-empty, this parent
          module is typically but _not_ always a package (e.g., the non-package
          `os` module containing the `os.path` submodule).
      """
  
      __slots__ = [
          'code',
          'filename',
          'graphident',
          'identifier',
          'packagepath',
          '_deferred_imports',
          '_global_attr_names',
          '_starimported_ignored_module_names',
          '_submodule_basename_to_node',
      ]
  
      def __init__(self, identifier):
          """
          Initialize this graph node.
  
          Parameters
          ----------
          identifier : str
              Fully-qualified name of this graph node's corresponding module,
              package, or C extension.
          """
  
          self.code = None
          self.filename = None
          self.graphident = identifier
          self.identifier = identifier
          self.packagepath = None
          self._deferred_imports = None
          self._global_attr_names = set()
          self._starimported_ignored_module_names = set()
          self._submodule_basename_to_node = dict()
  
  
      def is_global_attr(self, attr_name):
          """
          `True` only if the pure-Python module corresponding to this graph node
          defines a global attribute (e.g., class, variable) with the passed
          name.
  
          If this module is actually a package, this method instead returns
          `True` only if this package's pure-Python `__init__` submodule defines
          such a global attribute. In this case, note that this package may still
          contain an importable submodule of the same name. Callers should
          attempt to import this attribute as a submodule of this package
          _before_ assuming this attribute to be an ignorable global. See
          "Examples" below for further details.
  
          Parameters
          ----------
          attr_name : str
              Unqualified name of the attribute to be tested.
  
          Returns
          ----------
          bool
              `True` only if this module defines this global attribute.
  
          Examples
          ----------
          Consider a hypothetical module `foo` containing submodules `bar` and
          `__init__` where the latter assigns `bar` to be a global variable
          (possibly star-exported via the special `__all__` global variable):
  
          >>> # In "foo.__init__":
          >>> bar = 3.1415
  
          Python 2 and 3 both permissively permit this. This method returns
          `True` in this case (i.e., when called on the `foo` package's graph
          node, passed the attribute name `bar`) despite the importability of the
          `foo.bar` submodule.
          """
  
          return attr_name in self._global_attr_names
  
  
      def is_submodule(self, submodule_basename):
          """
          `True` only if the parent module corresponding to this graph node
          contains the submodule with the passed name.
  
          If `True`, this parent module is typically but _not_ always a package
          (e.g., the non-package `os` module containing the `os.path` submodule).
  
          Parameters
          ----------
          submodule_basename : str
              Unqualified name of the submodule to be tested.
  
          Returns
          ----------
          bool
              `True` only if this parent module contains this submodule.
          """
  
          return submodule_basename in self._submodule_basename_to_node
  
  
      def add_global_attr(self, attr_name):
          """
          Record the global attribute (e.g., class, variable) with the passed
          name to be defined by the pure-Python module corresponding to this
          graph node.
  
          If this module is actually a package, this method instead records this
          attribute to be defined by this package's pure-Python `__init__`
          submodule.
  
          Parameters
          ----------
          attr_name : str
              Unqualified name of the attribute to be added.
          """
  
          self._global_attr_names.add(attr_name)
  
  
      def add_global_attrs_from_module(self, target_module):
          """
          Record all global attributes (e.g., classes, variables) defined by the
          target module corresponding to the passed graph node to also be defined
          by the source module corresponding to this graph node.
  
          If the source module is actually a package, this method instead records
          these attributes to be defined by this package's pure-Python `__init__`
          submodule.
  
          Parameters
          ----------
          target_module : Node
              Graph node of the target module to import attributes from.
          """
  
          self._global_attr_names.update(target_module._global_attr_names)
  
  
      def add_submodule(self, submodule_basename, submodule_node):
          """
          Add the submodule with the passed name and previously imported graph
          node to the parent module corresponding to this graph node.
  
          This parent module is typically but _not_ always a package (e.g., the
          non-package `os` module containing the `os.path` submodule).
  
          Parameters
          ----------
          submodule_basename : str
              Unqualified name of the submodule to add to this parent module.
          submodule_node : Node
              Graph node of this submodule.
          """
  
          self._submodule_basename_to_node[submodule_basename] = submodule_node
  
  
      def get_submodule(self, submodule_basename):
          """
          Graph node of the submodule with the passed name in the parent module
          corresponding to this graph node.
  
          If this parent module does _not_ contain this submodule, an exception
          is raised. Else, this parent module is typically but _not_ always a
          package (e.g., the non-package `os` module containing the `os.path`
          submodule).
  
          Parameters
          ----------
          module_basename : str
              Unqualified name of the submodule to retrieve.
  
          Returns
          ----------
          Node
              Graph node of this submodule.
          """
  
          return self._submodule_basename_to_node[submodule_basename]
  
  
      def get_submodule_or_none(self, submodule_basename):
          """
          Graph node of the submodule with the passed unqualified name in the
          parent module corresponding to this graph node if this module contains
          this submodule _or_ `None`.
  
          This parent module is typically but _not_ always a package (e.g., the
          non-package `os` module containing the `os.path` submodule).
  
          Parameters
          ----------
          submodule_basename : str
              Unqualified name of the submodule to retrieve.
  
          Returns
          ----------
          Node
              Graph node of this submodule if this parent module contains this
              submodule _or_ `None`.
          """
  
          return self._submodule_basename_to_node.get(submodule_basename)
  
  
      def remove_global_attr_if_found(self, attr_name):
          """
          Record the global attribute (e.g., class, variable) with the passed
          name if previously recorded as defined by the pure-Python module
          corresponding to this graph node to be subsequently undefined by the
          same module.
  
          If this module is actually a package, this method instead records this
          attribute to be undefined by this package's pure-Python `__init__`
          submodule.
  
          This method is intended to be called on globals previously defined by
          this module that are subsequently undefined via the `del` built-in by
          this module, thus "forgetting" or "undoing" these globals.
  
          For safety, there exists no corresponding `remove_global_attr()`
          method. While defining this method is trivial, doing so would invite
          `KeyError` exceptions on scanning valid Python that lexically deletes a
          global in a scope under this module's top level (e.g., in a function)
          _before_ defining this global at this top level. Since `ModuleGraph`
          cannot and should not (re)implement a full-blown Python interpreter,
          ignoring out-of-order deletions is the only sane policy.
  
          Parameters
          ----------
          attr_name : str
              Unqualified name of the attribute to be removed.
          """
  
          if self.is_global_attr(attr_name):
              self._global_attr_names.remove(attr_name)
  
  
      def __cmp__(self, other):
          try:
              otherIdent = getattr(other, 'graphident')
          except AttributeError:
              return NotImplemented
  
          return cmp(self.graphident, otherIdent)
  
      def __eq__(self, other):
          try:
              otherIdent = getattr(other, 'graphident')
          except AttributeError:
              return False
  
          return self.graphident == otherIdent
  
      def __ne__(self, other):
          try:
              otherIdent = getattr(other, 'graphident')
          except AttributeError:
              return True
  
          return self.graphident != otherIdent
  
      def __lt__(self, other):
          try:
              otherIdent = getattr(other, 'graphident')
          except AttributeError:
              return NotImplemented
  
          return self.graphident < otherIdent
  
      def __le__(self, other):
          try:
              otherIdent = getattr(other, 'graphident')
          except AttributeError:
              return NotImplemented
  
          return self.graphident <= otherIdent
  
      def __gt__(self, other):
          try:
              otherIdent = getattr(other, 'graphident')
          except AttributeError:
              return NotImplemented
  
          return self.graphident > otherIdent
  
      def __ge__(self, other):
          try:
              otherIdent = getattr(other, 'graphident')
          except AttributeError:
              return NotImplemented
  
          return self.graphident >= otherIdent
  
  
      def __hash__(self):
          return hash(self.graphident)
  
      def infoTuple(self):
          return (self.identifier,)
  
      def __repr__(self):
          return '%s%r' % (type(self).__name__, self.infoTuple())
  
  
  # TODO: This indirection is, frankly, unnecessary. The
  # ModuleGraph.alias_module() should directly add the desired AliasNode instance
  # to the graph rather than indirectly adding an Alias instance to the
  # "lazynodes" dictionary.
  class Alias(str):
      """
      Placeholder aliasing an existing source module to a non-existent target
      module (i.e., the desired alias).
  
      For obscure reasons, this class subclasses `str`. Each instance of this
      class is the fully-qualified name of the existing source module being
      aliased. Unlike the related `AliasNode` class, instances of this class are
      _not_ actual nodes and hence _not_ added to the graph; they only facilitate
      communication between the `ModuleGraph.alias_module()` and
      `ModuleGraph.findNode()` methods.
      """
  
  
  class AliasNode(Node):
      """
      Graph node representing the aliasing of an existing source module under a
      non-existent target module name (i.e., the desired alias).
      """
  
      def __init__(self, name, node):
          """
          Initialize this alias.
  
          Parameters
          ----------
          name : str
              Fully-qualified name of the non-existent target module to be
              created (as an alias of the existing source module).
          node : Node
              Graph node of the existing source module being aliased.
          """
          super(AliasNode, self).__init__(name)
  
          #FIXME: Why only some? Why not *EVERYTHING* except "graphident", which
          #must remain equal to "name" for lookup purposes? This is, after all,
          #an alias. The idea is for the two nodes to effectively be the same.
  
          # Copy some attributes from this source module into this target alias.
          for attr_name in (
              'identifier', 'packagepath',
              '_global_attr_names', '_starimported_ignored_module_names',
              '_submodule_basename_to_node'):
              if hasattr(node, attr_name):
                  setattr(self, attr_name, getattr(node, attr_name))
  
  
      def infoTuple(self):
          return (self.graphident, self.identifier)
  
  
  class BadModule(Node):
      pass
  
  class ExcludedModule(BadModule):
      pass
  
  class MissingModule(BadModule):
      pass
  
  class Script(Node):
      def __init__(self, filename):
          super(Script, self).__init__(filename)
          self.filename = filename
  
      def infoTuple(self):
          return (self.filename,)
  
  class BaseModule(Node):
      def __init__(self, name, filename=None, path=None):
          super(BaseModule, self).__init__(name)
          self.filename = filename
          self.packagepath = path
  
      def infoTuple(self):
          return tuple(filter(None, (self.identifier, self.filename, self.packagepath)))
  
  class BuiltinModule(BaseModule):
      pass
  
  class SourceModule(BaseModule):
      pass
  
  class InvalidSourceModule(SourceModule):
      pass
  
  class CompiledModule(BaseModule):
      pass
  
  class InvalidCompiledModule(BaseModule):
      pass
  
  class Extension(BaseModule):
      pass
  
  
  class Package(BaseModule):
      """
      Graph node representing a non-namespace package.
      """
      pass
  
  
  class NamespacePackage(Package):
      """
      Graph node representing a namespace package.
      """
      pass
  
  
  class RuntimeModule(BaseModule):
      """
      Graph node representing a non-package Python module dynamically defined at
      runtime.
  
      Most modules are statically defined on-disk as standard Python files.
      Some modules, however, are dynamically defined in-memory at runtime
      (e.g., `gi.repository.Gst`, dynamically defined by the statically
      defined `gi.repository.__init__` module).
  
      This node represents such a runtime module. Since this is _not_ a package,
      all attempts to import submodules from this module in `from`-style import
      statements (e.g., the `queue` submodule in `from six.moves import queue`)
      will be silently ignored.
  
      To ensure that the parent package of this module if any is also imported
      and added to the graph, this node is typically added to the graph by
      calling the `ModuleGraph.add_module()` method.
      """
      pass
  
  
  class RuntimePackage(Package):
      """
      Graph node representing a non-namespace Python package dynamically defined
      at runtime.
  
      Most packages are statically defined on-disk as standard subdirectories
      containing `__init__.py` files. Some packages, however, are dynamically
      defined in-memory at runtime (e.g., `six.moves`, dynamically defined by
      the statically defined `six` module).
  
      This node represents such a runtime package. All attributes imported from
      this package in `from`-style import statements that are submodules of this
      package (e.g., the `queue` submodule in `from six.moves import queue`) will
      be imported rather than ignored.
  
      To ensure that the parent package of this package if any is also imported
      and added to the graph, this node is typically added to the graph by
      calling the `ModuleGraph.add_module()` method.
      """
      pass
  
  
  #FIXME: Safely removable. We don't actually use this anywhere. After removing
  #this class, remove the corresponding entry from "compat".
  class FlatPackage(BaseModule): # nocoverage
      def __init__(self, *args, **kwds):
          warnings.warn("This class will be removed in a future version of modulegraph",
              DeprecationWarning)
          super(FlatPackage, *args, **kwds)
  
  #FIXME: Safely removable. We don't actually use this anywhere. After removing
  #this class, remove the corresponding entry from "compat".
  class ArchiveModule(BaseModule): # nocoverage
      def __init__(self, *args, **kwds):
          warnings.warn("This class will be removed in a future version of modulegraph",
              DeprecationWarning)
          super(FlatPackage, *args, **kwds)
  
  
  # HTML templates for ModuleGraph generator
  header = """\
  <html>
    <head>
      <title>%(TITLE)s</title>
      <style>
        .node { padding: 0.5em 0 0.5em; border-top: thin grey dotted; }
        .moduletype { font: smaller italic }
        .node a { text-decoration: none; color: #006699; }
        .node a:visited { text-decoration: none; color: #2f0099; }
      </style>
    </head>
    <body>
      <h1>%(TITLE)s</h1>"""
  entry = """
  <div class="node">
    <a name="%(NAME)s"></a>
    %(CONTENT)s
  </div>"""
  contpl = """<tt>%(NAME)s</tt> <span class="moduletype">%(TYPE)s</span>"""
  contpl_linked = """\
  <a target="code" href="%(URL)s" type="text/plain"><tt>%(NAME)s</tt></a>
  <span class="moduletype">%(TYPE)s</span>"""
  imports = """\
    <div class="import">
  %(HEAD)s:
    %(LINKS)s
    </div>
  """
  footer = """
    </body>
  </html>"""
  
  def _ast_names(names):
      result = []
      for nm in names:
          if isinstance(nm, ast.alias):
              result.append(nm.name)
          else:
              result.append(nm)
  
      result = [r for r in result if r != '__main__']
      return result
  
  
  def uniq(seq):
      """Remove duplicates from a list, preserving order"""
      # Taken from https://stackoverflow.com/questions/480214
      seen = set()
      seen_add = seen.add
      return [x for x in seq if not (x in seen or seen_add(x))]
  
  
  if sys.version_info[0] == 2:
      DEFAULT_IMPORT_LEVEL= -1
  else:
      DEFAULT_IMPORT_LEVEL= 0
  
  class _Visitor(ast.NodeVisitor):
      def __init__(self, graph, module):
          self._graph = graph
          self._module = module
          self._level = DEFAULT_IMPORT_LEVEL
          self._in_if = [False]
          self._in_def = [False]
          self._in_tryexcept = [False]
  
      @property
      def in_if(self):
          return self._in_if[-1]
  
      @property
      def in_def(self):
          return self._in_def[-1]
  
      @property
      def in_tryexcept(self):
          return self._in_tryexcept[-1]
  
  
      def _collect_import(self, name, fromlist, level):
          if sys.version_info[0] == 2:
              if name == '__future__' and 'absolute_import' in (fromlist or ()):
                  self._level = 0
  
          have_star = False
          if fromlist is not None:
              fromlist = uniq(fromlist)
              if '*' in fromlist:
                  fromlist.remove('*')
                  have_star = True
  
          # Record this import as originating from this module for subsequent
          # handling by the _process_imports() method.
          self._module._deferred_imports.append(
              (have_star,
               (name, self._module, fromlist, level),
               {'edge_attr': DependencyInfo(
                   conditional=self.in_if,
                   tryexcept=self.in_tryexcept,
                   function=self.in_def,
                   fromlist=False)}))
  
  
      def visit_Import(self, node):
          for nm in _ast_names(node.names):
              self._collect_import(nm, None, self._level)
  
      def visit_ImportFrom(self, node):
          level = node.level if node.level != 0 else self._level
          self._collect_import(node.module or '', _ast_names(node.names), level)
  
      def visit_If(self, node):
          self._in_if.append(True)
          self.generic_visit(node)
          self._in_if.pop()
  
      def visit_FunctionDef(self, node):
          self._in_def.append(True)
          self.generic_visit(node)
          self._in_def.pop()
  
      def visit_Try(self, node):
          self._in_tryexcept.append(True)
          self.generic_visit(node)
          self._in_tryexcept.pop()
  
      def visit_ExceptHandler(self, node):
          self._in_tryexcept.append(True)
          self.generic_visit(node)
          self._in_tryexcept.pop()
  
      def visit_TryExcept(self, node):
          self._in_tryexcept.append(True)
          self.generic_visit(node)
          self._in_tryexcept.pop()
  
      def visit_Expression(self, node):
          # Expression node's cannot contain import statements or
          # other nodes that are relevant for us.
          pass
  
      # Expression isn't actually used as such in AST trees,
      # therefore define visitors for all kinds of expression nodes.
      visit_BoolOp = visit_Expression
      visit_BinOp = visit_Expression
      visit_UnaryOp = visit_Expression
      visit_Lambda = visit_Expression
      visit_IfExp = visit_Expression
      visit_Dict = visit_Expression
      visit_Set = visit_Expression
      visit_ListComp = visit_Expression
      visit_SetComp = visit_Expression
      visit_ListComp = visit_Expression
      visit_GeneratorExp = visit_Expression
      visit_Compare = visit_Expression
      visit_Yield = visit_Expression
      visit_YieldFrom = visit_Expression
      visit_Await = visit_Expression
      visit_Call = visit_Expression
  
  
  
  class ModuleGraph(ObjectGraph):
      """
      Directed graph whose nodes represent modules and edges represent
      dependencies between these modules.
      """
  
  
      def createNode(self, cls, name, *args, **kw):
          m = self.findNode(name)
  
          if m is None:
              #assert m is None, m
              m = super(ModuleGraph, self).createNode(cls, name, *args, **kw)
  
          return m
  
  
      def __init__(self, path=None, excludes=(), replace_paths=(), implies=(), graph=None, debug=0):
          super(ModuleGraph, self).__init__(graph=graph, debug=debug)
          if path is None:
              path = sys.path
          self.path = path
          self.lazynodes = {}
          # excludes is stronger than implies
          self.lazynodes.update(dict(implies))
          for m in excludes:
              self.lazynodes[m] = None
          self.replace_paths = replace_paths
  
          self.set_setuptools_nspackages()
          # Maintain own list of package path mappings in the scope of Modulegraph
          # object.
          self._package_path_map = _packagePathMap
  
      def set_setuptools_nspackages(self):
          # This is used when running in the test-suite
          self.nspackages = self._calc_setuptools_nspackages()
  
      def _calc_setuptools_nspackages(self):
          # Setuptools has some magic handling for namespace
          # packages when using 'install --single-version-externally-managed'
          # (used by system packagers and also by pip)
          #
          # When this option is used namespace packages are writting to
          # disk *without* an __init__.py file, which means the regular
          # import machinery will not find them.
          #
          # We therefore explicitly look for the hack used by
          # setuptools to get this kind of namespace packages to work.
  
          pkgmap = {}
  
          try:
              from pkgutil import ImpImporter
          except ImportError:
              try:
                  from _pkgutil import ImpImporter
              except ImportError:
                  ImpImporter = pkg_resources.ImpWrapper
  
          if sys.version_info[:2] >= (3,3):
              import importlib.machinery
              ImpImporter = importlib.machinery.FileFinder
  
          for entry in self.path:
              importer = pkg_resources.get_importer(entry)
  
              if isinstance(importer, ImpImporter):
                  try:
                      ldir = os.listdir(entry)
                  except os.error:
                      continue
  
                  for fn in ldir:
                      if fn.endswith('-nspkg.pth'):
                          fp = open(os.path.join(entry, fn), 'rU')
                          try:
                              for ln in fp:
                                  for pfx in _SETUPTOOLS_NAMESPACEPKG_PTHs:
                                      if ln.startswith(pfx):
                                          try:
                                              start = len(pfx)-2
                                              stop = ln.index(')', start)+1
                                          except ValueError:
                                              continue
  
                                          pkg = _eval_str_tuple(ln[start:stop])
                                          identifier = ".".join(pkg)
                                          subdir = os.path.join(entry, *pkg)
                                          if os.path.exists(os.path.join(subdir, '__init__.py')):
                                              # There is a real __init__.py, ignore the setuptools hack
                                              continue
  
                                          if identifier in pkgmap:
                                              pkgmap[identifier].append(subdir)
                                          else:
                                              pkgmap[identifier] = [subdir]
                                          break
                          finally:
                              fp.close()
  
          return pkgmap
  
  
      def implyNodeReference(self, node, other, edge_data=None):
          """
          Create a reference from the passed source node to the passed other node,
          implying the former to depend upon the latter.
  
          While the source node _must_ be an existing graph node, the target node
          may be either an existing graph node _or_ a fully-qualified module name.
          In the latter case, the module with that name and all parent packages of
          that module will be imported _without_ raising exceptions and for each
          newly imported module or package:
  
          * A new graph node will be created for that module or package.
          * A reference from the passed source node to that module or package will
            be created.
  
          This method allows dependencies between Python objects _not_ importable
          with standard techniques (e.g., module aliases, C extensions).
  
          Parameters
          ----------
          node : str
              Graph node for this reference's source module or package.
          other : {Node, str}
              Either a graph node _or_ fully-qualified name for this reference's
              target module or package.
          """
  
          if isinstance(other, Node):
              self._updateReference(node, other, edge_data)
          else:
              if isinstance(other, tuple):
                  raise ValueError(other)
  
              others = self._safe_import_hook(other, node, None)
              for other in others:
                  self._updateReference(node, other, edge_data)
  
  
      def getReferences(self, fromnode):
          """
          Yield all nodes that `fromnode` dependes on (that is,
          all modules that `fromnode` imports.
          """
  
          node = self.findNode(fromnode)
          out_edges, _ = self.get_edges(node)
          return out_edges
  
  
      def getReferers(self, tonode, collapse_missing_modules=True):
          node = self.findNode(tonode)
          _, in_edges = self.get_edges(node)
  
          if collapse_missing_modules:
              for n in in_edges:
                  if isinstance(n, MissingModule):
                      for n in self.getReferers(n, False):
                          yield n
  
                  else:
                      yield n
  
          else:
              for n in in_edges:
                  yield n
  
  
      def hasEdge(self, fromnode, tonode):
          """ Return True iff there is an edge from 'fromnode' to 'tonode' """
          fromnode = self.findNode(fromnode)
          tonode = self.findNode(tonode)
  
          return self.graph.edge_by_node(fromnode, tonode) is not None
  
  
      def foldReferences(self, packagenode):
          """
          Create edges to/from `packagenode` based on the edges to/from all
          submodules of that package _and_ then hide the graph nodes
          corresponding to those submodules.
          """
  
          pkg = self.findNode(packagenode)
  
          for n in self.nodes():
              if not n.identifier.startswith(pkg.identifier + '.'):
                  continue
  
              iter_out, iter_inc = n.get_edges()
              for other in iter_out:
                  if other.identifier.startswith(pkg.identifier + '.'):
                      continue
  
                  if not self.hasEdge(pkg, other):
                      # Ignore circular dependencies
                      self._updateReference(pkg, other, 'pkg-internal-import')
  
              for other in iter_in:
                  if other.identifier.startswith(pkg.identifier + '.'):
                      # Ignore circular dependencies
                      continue
  
                  if not self.hasEdge(other, pkg):
                      self._updateReference(other, pkg, 'pkg-import')
  
              self.graph.hide_node(n)
  
      # TODO: unfoldReferences(pkg) that restore the submodule nodes and
      #       removes 'pkg-import' and 'pkg-internal-import' edges. Care should
      #       be taken to ensure that references are correct if multiple packages
      #       are folded and then one of them in unfolded
  
  
      def _updateReference(self, fromnode, tonode, edge_data):
          try:
              ed = self.edgeData(fromnode, tonode)
          except (KeyError, GraphError): # XXX: Why 'GraphError'
              return self.createReference(fromnode, tonode, edge_data)
  
          if not (isinstance(ed, DependencyInfo) and isinstance(edge_data, DependencyInfo)):
              self.updateEdgeData(fromnode, tonode, edge_data)
          else:
              self.updateEdgeData(fromnode, tonode, ed._merged(edge_data))
  
  
      def createReference(self, fromnode, tonode, edge_data='direct'):
          """
          Create a reference from fromnode to tonode
          """
          return super(ModuleGraph, self).createReference(fromnode, tonode, edge_data=edge_data)
  
  
      def findNode(self, name, create_nspkg=True):
          """
          Graph node uniquely identified by the passed fully-qualified module
          name if this module has been added to the graph _or_ `None` otherwise.
  
          If (in order):
  
          . A namespace package with this identifier exists _and_ the passed
            `create_nspkg` parameter is `True`, this package will be
            instantiated and returned.
          . A lazy node with this identifier and:
            * No dependencies exists, this node will be instantiated and
              returned.
            * Dependencies exists, this node and all transitive dependencies of
              this node be instantiated and this node returned.
          . A non-lazy node with this identifier exists, this node will be
            returned as is.
  
          Parameters
          ----------
          name : str
              Fully-qualified name of the module whose graph node is to be found.
          create_nspkg : bool
              Whether or not to implicitly instantiate namespace packages. If
              `True` _and_ this name is that of a previously registered namespace
              package (i.e., in `self.nspackages`) not already added to the
              graph, this package will be added to the graph. Defaults to `True`.
  
          Returns
          ----------
          Node
              Graph node of this module if added to the graph _or_ `None`
              otherwise.
          """
  
          data = super(ModuleGraph, self).findNode(name)
  
          if data is not None:
              return data
  
          if name in self.lazynodes:
              deps = self.lazynodes.pop(name)
  
              if deps is None:
                  # excluded module
                  m = self.createNode(ExcludedModule, name)
              elif isinstance(deps, Alias):
                  other = self._safe_import_hook(deps, None, None).pop()
                  m = self.createNode(AliasNode, name, other)
                  self.implyNodeReference(m, other)
              else:
                  m = self._safe_import_hook(name, None, None).pop()
                  for dep in deps:
                      self.implyNodeReference(m, dep)
  
              return m
  
          if name in self.nspackages and create_nspkg:
              # name is a --single-version-externally-managed
              # namespace package (setuptools/distribute)
              pathnames = self.nspackages.pop(name)
              m = self.createNode(NamespacePackage, name)
  
              # FIXME: The filename must be set to a string to ensure that py2app
              # works, it is not clear yet why that is. Setting to None would be
              # cleaner.
              m.filename = '-'
              m.packagepath = _namespace_package_path(name, pathnames, self.path)
  
              # As per comment at top of file, simulate runtime packagepath additions.
              m.packagepath = m.packagepath + self._package_path_map.get(name, [])
              return m
  
          return None
  
  
      def run_script(self, pathname, caller=None):
          """
          Create a node by path (not module name).  It is expected to be a Python
          source file, and will be scanned for dependencies.
          """
          self.msg(2, "run_script", pathname)
  
          pathname = os.path.realpath(pathname)
          m = self.findNode(pathname)
          if m is not None:
              return m
  
          if sys.version_info[0] != 2:
              with open(pathname, 'rb') as fp:
                  encoding = util.guess_encoding(fp)
  
              with open(pathname, _READ_MODE, encoding=encoding) as fp:
                  contents = fp.read() + '\n'
              if contents.startswith(BOM):
                  # Ignore BOM at start of input
                  contents = contents[1:]
  
          else:
              with open(pathname, _READ_MODE) as fp:
                  contents = fp.read() + '\n'
  
          co_ast = compile(contents, pathname, 'exec', ast.PyCF_ONLY_AST, True)
          co = compile(co_ast, pathname, 'exec', 0, True)
          m = self.createNode(Script, pathname)
          self._updateReference(caller, m, None)
          self._scan_code(m, co, co_ast)
          m.code = co
          if self.replace_paths:
              m.code = self._replace_paths_in_code(m.code)
          return m
  
  
      #FIXME: For safety, the "source_module" parameter should default to the
      #root node of the current graph if unpassed. This parameter currently
      #defaults to None, thus disconnected modules imported in this manner (e.g.,
      #hidden imports imported by depend.analysis.initialize_modgraph()).
      def import_hook(
          self,
          target_module_partname,
          source_module=None,
          target_attr_names=None,
          level=DEFAULT_IMPORT_LEVEL,
          edge_attr=None,
      ):
          """
          Import the module with the passed name, all parent packages of this
          module, _and_ all submodules and attributes in this module with the
          passed names from the previously imported caller module signified by
          the passed graph node.
  
          Unlike most import methods (e.g., `_safe_import_hook()`), this method
          is designed to be publicly called by both external and internal
          callers and hence is public.
  
          Parameters
          ----------
          target_module_partname : str
              Partially-qualified name of the target module to be imported. See
              `_safe_import_hook()` for further details.
          source_module : Node
              Graph node for the previously imported **source module** (i.e.,
              module containing the `import` statement triggering the call to
              this method) _or_ `None` if this module is to be imported in a
              "disconnected" manner. **Passing `None` is _not_ recommended.**
              Doing so produces a disconnected graph in which the graph node
              created for the module to be imported will be disconnected and
              hence unreachable from all other nodes -- which frequently causes
              subtle issues in external callers (namely PyInstaller, which
              silently ignores unreachable nodes).
          target_attr_names : list
              List of the unqualified names of all submodules and attributes to
              be imported from the module to be imported if this is a "from"-
              style import (e.g., `[encode_base64, encode_noop]` for the import
              `from email.encoders import encode_base64, encode_noop`) _or_
              `None` otherwise.
          level : int
              Whether to perform an absolute or relative import. See
              `_safe_import_hook()` for further details.
  
          Returns
          ----------
          list
              List of the graph nodes created for all modules explicitly imported
              by this call, including the passed module and all submodules listed
              in `target_attr_names` _but_ excluding all parent packages
              implicitly imported by this call. If `target_attr_names` is `None`
              or the empty list, this is guaranteed to be a list of one element:
              the graph node created for the passed module.
  
          Raises
          ----------
          ImportError
              If the target module to be imported is unimportable.
          """
          self.msg(3, "_import_hook", target_module_partname, source_module, source_module, level)
  
          source_package = self._determine_parent(source_module)
          target_package, target_module_partname = self._find_head_package(
              source_package, target_module_partname, level)
          target_module = self._load_tail(target_package, target_module_partname)
          target_modules = [target_module]
  
          # If this is a "from"-style import *AND* this target module is
          # actually a package, import all submodules of this package specified
          # by the "import" half of this import (e.g., the submodules "bar" and
          # "car" of the target package "foo" in "from foo import bar, car").
          #
          # If this target module is a non-package, it could still contain
          # importable submodules (e.g., the non-package `os` module containing
          # the `os.path` submodule). In this case, these submodules are already
          # imported by this target module's pure-Python code. Since our import
          # scanner already detects such imports, these submodules need *NOT* be
          # reimported here.
          if target_attr_names and isinstance(target_module, Package):
              for target_submodule in self._import_importable_package_submodules(
                  target_module, target_attr_names):
                  if target_submodule not in target_modules:
                      target_modules.append(target_submodule)
  
          # Add an edge from this source module to each target module.
          for target_module in target_modules:
              self._updateReference(
                  source_module, target_module, edge_data=edge_attr)
  
          return target_modules
  
  
      def _determine_parent(self, caller):
          """
          Determine the package containing a node.
          """
          self.msgin(4, "determine_parent", caller)
  
          parent = None
          if caller:
              pname = caller.identifier
  
              if isinstance(caller, Package):
                  parent = caller
  
              elif '.' in pname:
                  pname = pname[:pname.rfind('.')]
                  parent = self.findNode(pname)
  
              elif caller.packagepath:
                  # XXX: I have no idea why this line
                  # is necessary.
                  parent = self.findNode(pname)
  
  
          self.msgout(4, "determine_parent ->", parent)
          return parent
  
  
      def _find_head_package(
          self,
          source_package,
          target_module_partname,
          level=DEFAULT_IMPORT_LEVEL):
          """
          Import the target package providing the target module with the passed
          name to be subsequently imported from the previously imported source
          package corresponding to the passed graph node.
  
          Parameters
          ----------
          source_package : Package
              Graph node for the previously imported **source package** (i.e.,
              package containing the module containing the `import` statement
              triggering the call to this method) _or_ `None` if this module is
              to be imported in a "disconnected" manner. **Passing `None` is
              _not_ recommended.** See the `_import_hook()` method for further
              details.
          target_module_partname : str
              Partially-qualified name of the target module to be imported. See
              `_safe_import_hook()` for further details.
          level : int
              Whether to perform absolute or relative imports. See the
              `_safe_import_hook()` method for further details.
  
          Returns
          ----------
          (target_package, target_module_tailname)
              2-tuple describing the imported target package, where:
              * `target_package` is the graph node created for this package.
              * `target_module_tailname` is the unqualified name of the target
                module to be subsequently imported (e.g., `text` when passed a
                `target_module_partname` of `email.mime.text`).
  
          Raises
          ----------
          ImportError
              If the package to be imported is unimportable.
          """
          self.msgin(4, "find_head_package", source_package, target_module_partname, level)
  
          #FIXME: Rename all local variable names to something sensible. No,
          #"p_fqdn" is not a sensible name.
  
          # If this target module is a submodule...
          if '.' in target_module_partname:
              target_module_headname, target_module_tailname = (
                  target_module_partname.split('.', 1))
          # Else, this target module is a top-level module.
          else:
              target_module_headname = target_module_partname
              target_module_tailname = ''
  
          # If attempting both absolute and relative imports...
          if level == ABSOLUTE_OR_RELATIVE_IMPORT_LEVEL:
              if source_package:
                  target_package_name = source_package.identifier + '.' + target_module_headname
              else:
                  target_package_name = target_module_headname
          # Else if attempting only absolute imports...
          elif level == ABSOLUTE_IMPORT_LEVEL:
              target_package_name = target_module_headname
  
              # Absolute import, ignore the parent
              source_package = None
          # Else if attempting only relative imports...
          else:
              if source_package is None:
                  self.msg(2, "Relative import outside of package")
                  raise ImportError("Relative import outside of package (name=%r, parent=%r, level=%r)"%(target_module_partname, source_package, level))
  
              for i in range(level - 1):
                  if '.' not in source_package.identifier:
                      self.msg(2, "Relative import outside of package")
                      raise ImportError("Relative import outside of package (name=%r, parent=%r, level=%r)"%(target_module_partname, source_package, level))
  
                  p_fqdn = source_package.identifier.rsplit('.', 1)[0]
                  new_parent = self.findNode(p_fqdn)
                  if new_parent is None:
                      #FIXME: Repetition detected. Exterminate. Exterminate.
                      self.msg(2, "Relative import outside of package")
                      raise ImportError("Relative import outside of package (name=%r, parent=%r, level=%r)"%(target_module_partname, source_package, level))
  
                  assert new_parent is not source_package, (
                      new_parent, source_package)
                  source_package = new_parent
  
              if target_module_headname:
                  target_package_name = (
                      source_package.identifier + '.' + target_module_headname)
              else:
                  target_package_name = source_package.identifier
  
          # Graph node of this target package.
          target_package = self._safe_import_module(
              target_module_headname, target_package_name, source_package)
  
          #FIXME: Why exactly is this necessary again? This doesn't quite seem
          #right but maybe it is. Shouldn't absolute imports only be performed if
          #the passed "level" is either "ABSOLUTE_IMPORT_LEVEL" or
          #"ABSOLUTE_OR_RELATIVE_IMPORT_LEVEL" -- or, more succinctly:
          #
          #    if level < 1:
  
          # If this target package is *NOT* importable and a source package was
          # passed, attempt to import this target package as an absolute import.
          if target_package is None and source_package is not None:
              target_package_name = target_module_headname
              source_package = None
  
              # Graph node for the target package, again.
              target_package = self._safe_import_module(
                  target_module_headname, target_package_name, source_package)
  
          # If this target package is importable, return this package.
          if target_package is not None:
              self.msgout(4, "find_head_package ->", (target_package, target_module_tailname))
              return target_package, target_module_tailname
  
          # Else, raise an exception.
          self.msgout(4, "raise ImportError: No module named", target_package_name)
          raise ImportError("No module named " + target_package_name)
  
  
      def _load_tail(self, package, submodule_name):
          """
          Import the submodule with the passed name and all parent packages of
          this module from the previously imported parent package corresponding
          to the passed graph node.
  
          Parameters
          ----------
          package : Package
              Graph node of the previously imported package containing this
              submodule.
          submodule_name : str
              Name of the submodule to be imported in either qualified (e.g.,
              `email.mime.base`) or unqualified (e.g., `base`) form.
  
          Returns
          ----------
          Node
              Graph node created for this submodule.
  
          Raises
          ----------
          ImportError
              If this submodule is unimportable.
          """
          self.msgin(4, "load_tail", package, submodule_name)
  
          submodule = package
          while submodule_name:
              i = submodule_name.find('.')
              if i < 0: i = len(submodule_name)
              head, submodule_name = submodule_name[:i], submodule_name[i+1:]
              mname = "%s.%s" % (submodule.identifier, head)
              submodule = self._safe_import_module(head, mname, submodule)
  
              if submodule is None:
                  # FIXME: Why do we no longer return a MissingModule instance?
                  # result = self.createNode(MissingModule, mname)
                  self.msgout(4, "raise ImportError: No module named", mname)
                  raise ImportError("No module named " + repr(mname))
  
          self.msgout(4, "load_tail ->", submodule)
          return submodule
  
  
      #FIXME: Refactor from a generator yielding graph nodes into a non-generator
      #returning a list or tuple of all yielded graph nodes. This method is only
      #called once above and the return value of that call is only iterated over
      #as a list or tuple. There's no demonstrable reason for this to be a
      #generator. Generators are great for their intended purposes (e.g., as
      #continuations). This isn't one of those purposes.
      def _import_importable_package_submodules(self, package, attr_names):
          """
          Generator importing and yielding each importable submodule (of the
          previously imported package corresponding to the passed graph node)
          whose unqualified name is in the passed list.
  
          Elements of this list that are _not_ importable submodules of this
          package are either:
  
          * Ignorable attributes (e.g., classes, globals) defined at the top
            level of this package's `__init__` submodule, which will be ignored.
          * Else, unignorable unimportable submodules, in which case an
            exception is raised.
  
          Parameters
          ----------
          package : Package
              Graph node of the previously imported package containing the
              modules to be imported and yielded.
  
          attr_names : list
              List of the unqualified names of all attributes of this package to
              attempt to import as submodules. This list will be internally
              converted into a set, safely ignoring any duplicates in this list
              (e.g., reducing the "from"-style import
              `from foo import bar, car, far, bar, car, far` to merely
              `from foo import bar, car, far`).
  
          Yields
          ----------
          Node
              Graph node created for the currently imported submodule.
  
          Raises
          ----------
          ImportError
              If any attribute whose name is in `attr_names` is neither:
              * An importable submodule of this package.
              * An ignorable global attribute (e.g., class, variable) defined at
                the top level of this package's `__init__` submodule.
              In this case, this attribute _must_ be an unimportable submodule of
              this package.
          """
  
          # Ignore duplicate submodule names in the passed list.
          attr_names = set(attr_names)
          self.msgin(4, "_import_importable_package_submodules", package, attr_names)
  
          #FIXME: This test *SHOULD* be superfluous and hence safely removable.
          #The higher-level _scan_bytecode() and _collect_import() methods
          #already guarantee "*" characters to be removed from fromlists.
          if '*' in attr_names:
              attr_names.update(self._find_all_submodules(package))
              attr_names.remove('*')
  
          # self.msg(4, '_import_importable_package_submodules (global attrs)', package.identifier, package._global_attr_names)
  
          # For the name of each attribute to be imported from this package...
          for attr_name in attr_names:
              # self.msg(4, '_import_importable_package_submodules (fromlist attr)', package.identifier, attr_name)
  
              # Graph node of this attribute if this attribute is a previously
              # imported module or None otherwise.
              submodule = package.get_submodule_or_none(attr_name)
  
              # If this attribute is *NOT* a previously imported module, attempt
              # to import this attribute as a submodule of this package.
              if submodule is None:
                  # Fully-qualified name of this submodule.
                  submodule_name = package.identifier + '.' + attr_name
  
                  # Graph node of this submodule if importable or None otherwise.
                  submodule = self._safe_import_module(
                      attr_name, submodule_name, package)
  
                  # If this submodule is unimportable...
                  if submodule is None:
                      # If this attribute is a global (e.g., class, variable)
                      # defined at the top level of this package's "__init__"
                      # submodule, this importation is safely ignorable. Do so
                      # and skip to the next attribute.
                      #
                      # This behaviour is non-conformant with Python behaviour,
                      # which is bad, but is required to sanely handle all
                      # possible edge cases, which is good. In Python, a global
                      # attribute defined at the top level of a package's
                      # "__init__" submodule shadows a submodule of the same name
                      # in that package. Attempting to import that submodule
                      # instead imports that attribute; thus, that submodule is
                      # effectively unimportable. In this method and elsewhere,
                      # that submodule is tested for first and hence shadows that
                      # attribute -- the opposite logic. Attempts to import that
                      # attribute are mistakenly seen as attempts to import that
                      # submodule! Why?
                      #
                      # Edge cases. PyInstaller (and by extension ModuleGraph)
                      # only cares about module imports. Global attribute imports
                      # are parsed only as the means to this ends and are
                      # otherwise ignorable. The cost of erroneously shadowing:
                      #
                      # * Submodules by attributes is significant. Doing so
                      #   prevents such submodules from being frozen and hence
                      #   imported at application runtime.
                      # * Attributes by submodules is insignificant. Doing so
                      #   could erroneously freeze such submodules despite their
                      #   never being imported at application runtime. However,
                      #   ModuleGraph is incapable of determining with certainty
                      #   that Python logic in another module other than the
                      #   "__init__" submodule containing these attributes does
                      #   *NOT* delete these attributes and hence unshadow these
                      #   submodules, which would then become importable at
                      #   runtime and require freezing. Hence, ModuleGraph *MUST*
                      #   permissively assume submodules of the same name as
                      #   attributes to be unshadowed elsewhere and require
                      #   freezing -- even if they do not.
                      #
                      # It is practically difficult (albeit technically feasible)
                      # for ModuleGraph to determine whether or not the target
                      # attribute names of "from"-style import statements (e.g.,
                      # "bar" and "car" in "from foo import bar, car") refer to
                      # non-ignorable submodules or ignorable non-module globals
                      # during opcode scanning. Distinguishing these two cases
                      # during opcode scanning would require a costly call to the
                      # _find_module() method, which would subsequently be
                      # repeated during import-graph construction. This could be
                      # ameliorated with caching, which itself would require
                      # costly space consumption and developer time.
                      #
                      # Since opcode scanning fails to distinguish these two
                      # cases, this and other methods subsequently called at
                      # import-graph construction time (e.g.,
                      # _safe_import_hook()) must do so. Since submodules of the
                      # same name as attributes must assume to be unshadowed
                      # elsewhere and require freezing, the only solution is to
                      # attempt to import an attribute as a non-ignorable module
                      # *BEFORE* assuming an attribute to be an ignorable
                      # non-module. Which is what this and other methods do.
                      #
                      # See Package.is_global_attr() for similar discussion.
                      if package.is_global_attr(attr_name):
                          self.msg(4, '_import_importable_package_submodules: ignoring from-imported global', package.identifier, attr_name)
                          continue
                      # Else, this attribute is an unimportable submodule. Since
                      # this is *NOT* safely ignorable, raise an exception.
                      else:
                          raise ImportError("No module named " + submodule_name)
  
              # Yield this submodule's graph node to the caller.
              yield submodule
  
          self.msgin(4, "_import_importable_package_submodules ->")
  
  
      def _find_all_submodules(self, m):
          if not m.packagepath:
              return
  
          # TODO: Unused and hence safely removable.
          # 'suffixes' used to be a list hardcoded to [".py", ".pyc", ".pyo"].
          # But we must also collect Python extension modules - although
          # we cannot separate normal dlls from Python extensions.
          # suffixes = [triple[0] for triple in imp.get_suffixes()]
  
          for path in m.packagepath:
              try:
                  names = zipio.listdir(path)
              except (os.error, IOError):
                  self.msg(2, "can't list directory", path)
                  continue
              for info in (moduleInfoForPath(p) for p in names):
                  if info is None: continue
                  if info[0] != '__init__':
                      yield info[0]
  
  
      def alias_module(self, src_module_name, trg_module_name):
          """
          Alias the source module to the target module with the passed names.
  
          This method ensures that the next call to findNode() given the target
          module name will resolve this alias. This includes importing and adding
          a graph node for the source module if needed as well as adding a
          reference from the target to source module.
  
          Parameters
          ----------
          src_module_name : str
              Fully-qualified name of the existing **source module** (i.e., the
              module being aliased).
          trg_module_name : str
              Fully-qualified name of the non-existent **target module** (i.e.,
              the alias to be created).
          """
          self.msg(3, 'alias_module "%s" -> "%s"' % (src_module_name, trg_module_name))
          # print('alias_module "%s" -> "%s"' % (src_module_name, trg_module_name))
          assert isinstance(src_module_name, str), '"%s" not a module name.' % str(src_module_name)
          assert isinstance(trg_module_name, str), '"%s" not a module name.' % str(trg_module_name)
  
          # If the target module has already been added to the graph as either a
          # non-alias or as a different alias, raise an exception.
          trg_module = self.findNode(trg_module_name)
          if trg_module is not None and not (
             isinstance(trg_module, AliasNode) and
             trg_module.identifier == src_module_name):
              raise ValueError('Target module "%s" already imported as "%s".' % (trg_module_name, trg_module))
  
          # See findNode() for details.
          self.lazynodes[trg_module_name] = Alias(src_module_name)
  
  
      def add_module(self, module):
          """
          Add the passed module node to the graph if not already added.
  
          If that module has a parent module or package with a previously added
          node, this method also adds a reference from this module node to its
          parent node and adds this module node to its parent node's namespace.
  
          This high-level method wraps the low-level `addNode()` method, but is
          typically _only_ called by graph hooks adding runtime module nodes. For
          all other node types, the `import_module()` method should be called.
  
          Parameters
          ----------
          module : BaseModule
              Graph node of the module to be added.
          """
          self.msg(3, 'add_module', module)
  
          # If no node exists for this module, add such a node.
          module_added = self.findNode(module.identifier)
          if module_added is None:
              self.addNode(module)
          else:
              assert module == module_added, 'Newly added module "%s" != previously added module "%s".' % (str(module), str(module_added))
  
          # If this module has a previously added parent, reference this module to
          # its parent and add this module to its parent's namespace.
          parent_name, _, module_basename = module.identifier.rpartition('.')
          if parent_name:
              parent = self.findNode(parent_name)
              if parent is None:
                  self.msg(4, 'add_module parent not found:', parent_name)
              else:
                  self.createReference(module, parent)
                  parent.add_submodule(module_basename, module)
  
  
      def append_package_path(self, package_name, directory):
          """
          Modulegraph does a good job at simulating Python's, but it can not
          handle packagepath '__path__' modifications packages make at runtime.
  
          Therefore there is a mechanism whereby you can register extra paths
          in this map for a package, and it will be honored.
  
          NOTE: This method has to be called before a package is resolved by
                modulegraph.
  
          Parameters
          ----------
          module : str
              Fully-qualified module name.
          directory : str
              Absolute or relative path of the directory to append to the
              '__path__' attribute.
          """
  
          paths = self._package_path_map.setdefault(package_name, [])
          paths.append(directory)
  
  
      def _safe_import_module(
          self, module_partname, module_name, parent_module):
          """
          Create a new graph node for the module with the passed name under the
          parent package signified by the passed graph node _without_ raising
          `ImportError` exceptions.
  
          If this module has already been imported, this module's existing graph
          node will be returned; else if this module is importable, a new graph
          node will be added for this module and returned; else this module is
          unimportable, in which case `None` will be returned. Like the
          `_safe_import_hook()` method, this method does _not_ raise
          `ImportError` exceptions when this module is unimportable.
  
          Parameters
          ----------
          module_partname : str
              Unqualified name of the module to be imported (e.g., `text`).
          module_name : str
              Fully-qualified name of this module (e.g., `email.mime.text`).
          parent_module : Package
              Graph node of the previously imported parent module containing this
              submodule _or_ `None` if this is a top-level module (i.e.,
              `module_name` contains no `.` delimiters). This parent module is
              typically but _not_ always a package (e.g., the `os.path` submodule
              contained by the `os` module).
  
          Returns
          ----------
          Node
              Graph node created for this module _or_ `None` if this module is
              unimportable.
          """
          self.msgin(3, "safe_import_module", module_partname, module_name, parent_module)
  
          # If this module has *NOT* already been imported, do so.
          module = self.findNode(module_name)
          if module is None:
              # List of the absolute paths of all directories to be searched for
              # this module. This effectively defaults to "sys.path".
              search_dirs = None
  
              # Open file handle providing the physical contents of this module.
              file_handle = None
  
              # If this module has a parent package...
              if parent_module is not None:
                  # ...with a list of the absolute paths of all directories
                  # comprising this package, prefer that to "sys.path".
                  if parent_module.packagepath is not None:
                      search_dirs = parent_module.packagepath
                  # Else, something is horribly wrong. Return emptiness.
                  else:
                      self.msgout(3, "safe_import_module -> None (parent_parent.packagepath is None)")
                      return None
  
              try:
                  try:
                      file_handle, pathname, metadata = self._find_module(
                          module_partname, search_dirs, parent_module)
                  except ImportError as exc:
                      self.msgout(3, "safe_import_module -> None (%r)" % exc)
                      return None
  
                  module = self._load_module(
                      module_name, file_handle, pathname, metadata)
              finally:
                  if file_handle is not None:
                      file_handle.close()
  
          # If this is a submodule rather than top-level module...
          if parent_module is not None:
              self.msg(4, "safe_import_module create reference", module, "->", parent_module)
  
              # Add an edge from this submodule to its parent module.
              self._updateReference(
                  module, parent_module, edge_data=DependencyInfo(
                      conditional=False,
                      fromlist=False,
                      function=False,
                      tryexcept=False,
              ))
  
              # Add this submodule to its parent module.
              parent_module.add_submodule(module_partname, module)
  
          # Return this module.
          self.msgout(3, "safe_import_module ->", module)
          return module
  
  
      #FIXME: For clarity, rename method parameters to:
      #    def _load_module(self, module_name, file_handle, pathname, imp_info):
      def _load_module(self, fqname, fp, pathname, info):
          suffix, mode, typ = info
          self.msgin(2, "load_module", fqname, fp and "fp", pathname)
  
          if typ == imp.PKG_DIRECTORY:
              if isinstance(mode, (list, tuple)):
                  packagepath = mode
              else:
                  packagepath = []
  
              m = self._load_package(fqname, pathname, packagepath)
              self.msgout(2, "load_module ->", m)
              return m
  
          if typ == imp.PY_SOURCE:
              contents = fp.read()
              if isinstance(contents, bytes):
                  contents += b'\n'
              else:
                  contents += '\n'
  
              try:
                  co = compile(contents, pathname, 'exec', ast.PyCF_ONLY_AST, True)
                  #co = compile(contents, pathname, 'exec', 0, True)
              except SyntaxError:
                  co = None
                  cls = InvalidSourceModule
                  self.msg(2, "load_module: InvalidSourceModule", pathname)
  
              else:
                  cls = SourceModule
  
          elif typ == imp.PY_COMPILED:
              if fp.read(4) != imp.get_magic():
                  self.msg(2, "load_module: InvalidCompiledModule", pathname)
                  co = None
                  cls = InvalidCompiledModule
  
              else:
                  fp.read(4)
                  try:
                      co = marshal.loads(fp.read())
                      cls = CompiledModule
                  except Exception:
                      co = None
                      cls = InvalidCompiledModule
  
          elif typ == imp.C_BUILTIN:
              cls = BuiltinModule
              co = None
  
          else:
              cls = Extension
              co = None
  
          m = self.createNode(cls, fqname)
          m.filename = pathname
          if co is not None:
              try:
                  if isinstance(co, ast.AST):
                      co_ast = co
                      co = compile(co_ast, pathname, 'exec', 0, True)
                  else:
                      co_ast = None
                  self._scan_code(m, co, co_ast)
  
                  if self.replace_paths:
                      co = self._replace_paths_in_code(co)
                  m.code = co
              except SyntaxError:
                  self.msg(1, "load_module: SyntaxError in ", pathname)
                  cls = InvalidSourceModule
                  m = self.createNode(cls, fqname)
  
          self.msgout(2, "load_module ->", m)
          return m
  
  
      def _safe_import_hook(
          self, target_module_partname, source_module, target_attr_names,
          level=DEFAULT_IMPORT_LEVEL, edge_attr=None):
          """
          Import the module with the passed name and all parent packages of this
          module from the previously imported caller module signified by the
          passed graph node _without_ raising `ImportError` exceptions.
  
          This method wraps the lowel-level `_import_hook()` method. On catching
          an `ImportError` exception raised by that method, this method creates
          and adds a `MissingNode` instance describing the unimportable module to
          the graph instead.
  
          Parameters
          ----------
          target_module_partname : str
              Partially-qualified name of the module to be imported. If `level`
              is:
              * `ABSOLUTE_OR_RELATIVE_IMPORT_LEVEL` (e.g., the Python 2 default)
                or a positive integer (e.g., an explicit relative import), the
                fully-qualified name of this module is the concatenation of the
                fully-qualified name of the caller module's package and this
                parameter.
              * `ABSOLUTE_IMPORT_LEVEL` (e.g., the Python 3 default), this name
                is already fully-qualified.
              * A non-negative integer (e.g., `1`), this name is typically the
                empty string. In this case, this is a "from"-style relative
                import (e.g., "from . import bar") and the fully-qualified name
                of this module is dynamically resolved by import machinery.
          source_module : Node
              Graph node for the previously imported **caller module** (i.e.,
              module containing the `import` statement triggering the call to
              this method) _or_ `None` if this module is to be imported in a
              "disconnected" manner. **Passing `None` is _not_ recommended.**
              Doing so produces a disconnected graph in which the graph node
              created for the module to be imported will be disconnected and
              hence unreachable from all other nodes -- which frequently causes
              subtle issues in external callers (e.g., PyInstaller, which
              silently ignores unreachable nodes).
          target_attr_names : list
              List of the unqualified names of all submodules and attributes to
              be imported via a `from`-style import statement from this target
              module if any (e.g., the list `[encode_base64, encode_noop]` for
              the import `from email.encoders import encode_base64, encode_noop`)
              _or_ `None` otherwise. Ignored unless `source_module` is the graph
              node of a package (i.e., is an instance of the `Package` class).
              Why? Because:
              * Consistency. The `_import_importable_package_submodules()`
                method accepts a similar list applicable only to packages.
              * Efficiency. Unlike packages, modules cannot physically contain
                submodules. Hence, any target module imported via a `from`-style
                import statement as an attribute from another target parent
                module must itself have been imported in that target parent
                module. The import statement responsible for that import must
                already have been previously parsed by `ModuleGraph`, in which
                case that target module will already be frozen by PyInstaller.
                These imports are safely ignorable here.
          level : int
              Whether to perform an absolute or relative import. This parameter
              corresponds exactly to the parameter of the same name accepted by
              the `__import__()` built-in: "The default is -1 which indicates
              both absolute and relative imports will be attempted. 0 means only
              perform absolute imports. Positive values for level indicate the
              number of parent directories to search relative to the directory of
              the module calling `__import__()`." Defaults to -1 under Python 2
              and 0 under Python 3. Since this default depends on the major
              version of the current Python interpreter, depending on this
              default can result in unpredictable and non-portable behaviour.
              Callers are strongly recommended to explicitly pass this parameter
              rather than implicitly accept this default.
  
          Returns
          ----------
          list
              List of the graph nodes created for all modules explicitly imported
              by this call, including the passed module and all submodules listed
              in `target_attr_names` _but_ excluding all parent packages
              implicitly imported by this call. If `target_attr_names` is either
              `None` or the empty list, this is guaranteed to be a list of one
              element: the graph node created for the passed module. As above,
              `MissingNode` instances are created for all unimportable modules.
          """
          self.msg(3, "_safe_import_hook", target_module_partname, source_module, target_attr_names, level)
  
          def is_swig_candidate():
              return (source_module is not None and
                      target_attr_names is None and
                      level == ABSOLUTE_IMPORT_LEVEL and
                      type(source_module) is SourceModule and
                      target_module_partname ==
                        '_' + source_module.identifier.rpartition('.')[2] and
                      sys.version_info[0] == 3)
  
          def is_swig_wrapper(source_module):
              # TODO Define a new function util.open_text_file() performing
              # this logic, which is repeated numerous times in this module.
              # FIXME: Actually, can't we just use the new compat.open()
              # function to reliably open text files in a portable manner?
              with open(source_module.filename, 'rb') as source_module_file:
                  encoding = util.guess_encoding(source_module_file)
              with open(source_module.filename, _READ_MODE, encoding=encoding) \
                      as source_module_file:
                  first_line = source_module_file.readline()
              self.msg(5, 'SWIG wrapper candidate first line: %r' % (first_line))
              return "automatically generated by SWIG" in first_line
  
  
          # List of the graph nodes created for all target modules both
          # imported by and returned from this call, whose:
          #
          # * First element is the graph node for the core target module
          #   specified by the "target_module_partname" parameter.
          # * Remaining elements are the graph nodes for all target submodules
          #   specified by the "target_attr_names" parameter.
          target_modules = None
  
          # True if this is a Python 2-style implicit relative import of a
          # SWIG-generated C extension. False if we checked and it is not SWIG.
          # None if we haven't checked yet.
          is_swig_import = None
  
          # Attempt to import this target module in the customary way.
          try:
              target_modules = self.import_hook(
                  target_module_partname, source_module,
                  target_attr_names=None, level=level, edge_attr=edge_attr)
          # Failing that, defer to custom module importers handling non-standard
          # import schemes (namely, SWIG).
          except ImportError as msg:
              # If this is an absolute top-level import under Python 3 and if the
              # name to be imported is the caller's name prefixed by "_", this
              # could be a SWIG-generated Python 2-style implicit relative import.
              # SWIG-generated files contain functions named swig_import_helper()
              # importing dynamic libraries residing in the same directory. For
              # example, a SWIG-generated caller module "csr.py" might resemble:
              #
              #     # This file was automatically generated by SWIG (http://www.swig.org).
              #     ...
              #     def swig_import_helper():
              #         ...
              #         try:
              #             fp, pathname, description = imp.find_module('_csr', [dirname(__file__)])
              #         except ImportError:
              #             import _csr
              #             return _csr
              #
              # While there exists no reasonable means for modulegraph to parse
              # the call to imp.find_module(), the subsequent implicit relative
              # import is trivially parsable. This import is prohibited under
              # Python 3, however, and thus parsed only if the caller's file is
              # parsable plaintext (as indicated by a filetype of ".py") and the
              # first line of this file is the above SWIG header comment.
              #
              # The constraint that this library's name be the caller's name
              # prefixed by '_' is explicitly mandated by SWIG and thus a
              # reliable indicator of "SWIG-ness". The SWIG documentation states:
              # "When linking the module, the name of the output file has to match
              #  the name of the module prefixed by an underscore."
              #
              # Only source modules (e.g., ".py"-suffixed files) are SWIG import
              # candidates. All other node types are safely ignorable.
              if is_swig_candidate():
                  self.msg(4, 'SWIG import candidate (name=%r, caller=%r, level=%r)' % (target_module_partname, source_module, level))
                  is_swig_import = is_swig_wrapper(source_module)
                  if is_swig_import:
                      # Convert this Python 2-compliant implicit relative
                      # import prohibited by Python 3 into a Python
                      # 3-compliant explicit relative "from"-style import for
                      # the duration of this function call by overwriting the
                      # original parameters passed to this call.
                      target_attr_names = [target_module_partname]
                      target_module_partname = ''
                      level = 1
                      self.msg(2,
                               'SWIG import (caller=%r, fromlist=%r, level=%r)'
                               % (source_module, target_attr_names, level))
                      # Import this target SWIG C extension's package.
                      try:
                          target_modules = self.import_hook(
                              target_module_partname, source_module,
                              target_attr_names=None,
                              level=level,
                              edge_attr=edge_attr)
                      except ImportError as msg:
                          self.msg(2, "SWIG ImportError:", str(msg))
  
              # If this module remains unimportable...
              if target_modules is None:
                  self.msg(2, "ImportError:", str(msg))
  
                  # Add this module as a MissingModule node.
                  target_module = self.createNode(
                      MissingModule,
                      _path_from_importerror(msg, target_module_partname))
                  self._updateReference(
                      source_module, target_module, edge_data=edge_attr)
  
                  # Initialize this list to this node.
                  target_modules = [target_module]
  
          # Ensure that the above logic imported exactly one target module.
          assert len(target_modules) == 1, (
              'Expected import_hook() to'
              'return only one module but received: {}'.format(target_modules))
  
          # Target module imported above.
          target_module = target_modules[0]
  
          if isinstance(target_module, MissingModule) \
             and is_swig_import is None and is_swig_candidate() \
             and is_swig_wrapper(source_module):
              # if this possible swig C module was previously imported from
              # a python module other than its corresponding swig python
              # module, then it may have been considered a MissingModule.
              # Try to reimport it now. For details see pull-request #2578
              # and issue #1522.
              #
              # If this module was takes as a SWIG candidate above, but failed
              # to import, this would be a MissingModule, too. Thus check if
              # this was the case (is_swig_import would be not None) to avoid
              # recursion error. If `is_swig_import` is None and we are still a
              # swig candidate then that means we haven't properly imported this
              # swig module yet so do that below.
              #
              # Remove the MissingModule node from the graph so that we can
              # attempt a reimport and avoid collisions. This node should be
              # fine to remove because the proper module will be imported and
              # added to the graph in the next line (call to _safe_import_hook).
              self.removeNode(target_module)
              # Reimport the SWIG C module relative to the wrapper
              target_modules = self._safe_import_hook(
                  target_module_partname, source_module,
                  target_attr_names=None, level=1, edge_attr=edge_attr)
              # return the output regardless because it would just be
              # duplicating the processing below
              return target_modules
  
          if isinstance(edge_attr, DependencyInfo):
              edge_attr = edge_attr._replace(fromlist=True)
  
          # If this is a "from"-style import *AND* this target module is a
          # package, import all attributes listed by the "import" clause of this
          # import that are submodules of this package. If this target module is
          # *NOT* a package, these attributes are always ignorable globals (e.g.,
          # classes, variables) defined at the top level of this module.
          #
          # If this target module is a non-package, it could still contain
          # importable submodules (e.g., the non-package `os` module containing
          # the `os.path` submodule). In this case, these submodules are already
          # imported by this target module's pure-Python code. Since our import
          # scanner already detects these imports, these submodules need *NOT* be
          # reimported here. (Doing so would be harmless but inefficient.)
          if target_attr_names and isinstance(target_module, Package):
              # For the name of each attribute imported from this target package
              # into this source module...
              for target_submodule_partname in target_attr_names:
                  #FIXME: Is this optimization *REALLY* an optimization or at all
                  #necessary? The findNode() method called below should already
                  #be heavily optimized, in which case this optimization here is
                  #premature, senseless, and should be eliminated.
  
                  # If this attribute is a previously imported submodule of this
                  # target module, optimize this edge case.
                  if target_module.is_submodule(target_submodule_partname):
                      # Graph node for this submodule.
                      target_submodule = target_module.get_submodule(
                          target_submodule_partname)
  
                      #FIXME: What? Shouldn't "target_submodule" *ALWAYS* be
                      #non-None here? Assert this to be non-None instead.
                      if target_submodule is not None:
                          #FIXME: Why does duplication matter? List searches are
                          #mildly expensive.
  
                          # If this submodule has not already been added to the
                          # list of submodules to be returned, do so.
                          if target_submodule not in target_modules:
                              self._updateReference(
                                  source_module,
                                  target_submodule,
                                  edge_data=edge_attr)
                              target_modules.append(target_submodule)
                          continue
  
                  # Fully-qualified name of this submodule.
                  target_submodule_name = (
                      target_module.identifier + '.' + target_submodule_partname)
  
                  # Graph node of this submodule if previously imported or None.
                  target_submodule = self.findNode(target_submodule_name)
  
                  # If this submodule has not been imported, do so as if this
                  # submodule were the only attribute listed by the "import"
                  # clause of this import (e.g., as "from foo import bar" rather
                  # than "from foo import car, far, bar").
                  if target_submodule is None:
                      # Attempt to import this submodule.
                      try:
                          # Ignore the list of graph nodes returned by this
                          # method. If both this submodule's package and this
                          # submodule are importable, this method returns a
                          # 2-element list whose second element is this
                          # submodule's graph node. However, if this submodule's
                          # package is importable but this submodule is not,
                          # this submodule is either:
                          #
                          # * An ignorable global attribute defined at the top
                          #   level of this package's "__init__" submodule. In
                          #   this case, this method returns a 1-element list
                          #   without raising an exception.
                          # * A non-ignorable unimportable submodule. In this
                          #   case, this method raises an "ImportError".
                          #
                          # While the first two cases are disambiguatable by the
                          # length of this list, doing so would render this code
                          # dependent on import_hook() details subject to change.
                          # Instead, call findNode() to decide the truthiness.
                          self.import_hook(
                              target_module_partname, source_module,
                              target_attr_names=[target_submodule_partname],
                              level=level,
                              edge_attr=edge_attr)
  
                          # Graph node of this submodule imported by the prior
                          # call if importable or None otherwise.
                          target_submodule = self.findNode(target_submodule_name)
  
                          # If this submodule does not exist, this *MUST* be an
                          # ignorable global attribute defined at the top level
                          # of this package's "__init__" submodule.
                          if target_submodule is None:
                              # Assert this to actually be the case.
                              assert target_module.is_global_attr(
                                  target_submodule_partname), (
                                  'No global named {} in {}.__init__'.format(
                                      target_submodule_partname,
                                      target_module.identifier))
  
                              # Skip this safely ignorable importation to the
                              # next attribute. See similar logic in the body of
                              # _import_importable_package_submodules().
                              self.msg(4, '_safe_import_hook', 'ignoring imported non-module global', target_module.identifier, target_submodule_partname)
                              continue
  
                          # If this is a SWIG C extension, instruct PyInstaller
                          # to freeze this extension under its unqualified rather
                          # than qualified name (e.g., as "_csr" rather than
                          # "scipy.sparse.sparsetools._csr"), permitting the
                          # implicit relative import in its parent SWIG module to
                          # successfully find this extension.
                          if is_swig_import:
                              # If a graph node with this name already exists,
                              # avoid collisions by emitting an error instead.
                              if self.findNode(target_submodule_partname):
                                  self.msg(2, 'SWIG import error: %r basename %r already exists' % (target_submodule_name, target_submodule_partname))
                              else:
                                  self.msg(4, 'SWIG import renamed from %r to %r' % (target_submodule_name, target_submodule_partname))
                                  target_submodule.identifier = (
                                      target_submodule_partname)
                      # If this submodule is unimportable, add a MissingModule.
                      except ImportError as msg:
                          self.msg(2, "ImportError:", str(msg))
                          #sm = self.createNode(MissingModule, _path_from_importerror(msg, fullname))
                          target_submodule = self.createNode(
                              MissingModule, target_submodule_name)
  
                  # Add this submodule to its package.
                  target_module.add_submodule(
                      target_submodule_partname, target_submodule)
                  if target_submodule is not None:
                      self._updateReference(
                          target_module, target_submodule, edge_data=edge_attr)
                      self._updateReference(
                          source_module, target_submodule, edge_data=edge_attr)
  
                      if target_submodule not in target_modules:
                          target_modules.append(target_submodule)
  
          # Return the list of all target modules imported by this call.
          return target_modules
  
  
      def _scan_code(
          self,
          module,
          module_code_object,
          module_code_object_ast=None):
          """
          Parse and add all import statements from the passed code object of the
          passed source module to this graph, recursively.
  
          **This method is at the root of all `ModuleGraph` recursion.**
          Recursion begins here and ends when all import statements in all code
          objects of all modules transitively imported by the source module
          passed to the first call to this method have been added to the graph.
          Specifically, this method:
  
          1. If the passed `module_code_object_ast` parameter is non-`None`,
             parses all import statements from this object.
          2. Else, parses all import statements from the passed
             `module_code_object` parameter.
          1. For each such import statement:
             1. Adds to this `ModuleGraph` instance:
                1. Nodes for all target modules of these imports.
                1. Directed edges from this source module to these target
                   modules.
             2. Recursively calls this method with these target modules.
  
          Parameters
          ----------
          module : Node
              Graph node of the module to be parsed.
          module_code_object : PyCodeObject
              Code object providing this module's disassembled Python bytecode.
              Ignored unless `module_code_object_ast` is `None`.
          module_code_object_ast : optional[ast.AST]
              Optional abstract syntax tree (AST) of this module if any or `None`
              otherwise. Defaults to `None`, in which case the passed
              `module_code_object` is parsed instead.
          """
  
          # For safety, guard against multiple scans of the same module by
          # resetting this module's list of deferred target imports. While
          # uncommon, this edge case can occur due to:
          #
          # * Dynamic package replacement via the replacePackage() function. For
          #   example, the real "_xmlplus" package dynamically replaces itself
          #   with the fake "xml" package into the "sys.modules" cache of all
          #   currently loaded modules at runtime.
          module._deferred_imports = []
  
          # Parse all imports from this module *BEFORE* adding these imports to
          # the graph. If an AST is provided, parse that rather than this
          # module's code object.
          if module_code_object_ast is not None:
              # Parse this module's AST for imports.
              self._scan_ast(module, module_code_object_ast)
  
              # Parse this module's code object for all relevant non-imports
              # (e.g., global variable declarations and undeclarations).
              self._scan_bytecode(
                  module, module_code_object, is_scanning_imports=False)
          # Else, parse this module's code object for imports.
          else:
              self._scan_bytecode(
                  module, module_code_object, is_scanning_imports=True)
  
          # Add all imports parsed above to this graph.
          self._process_imports(module)
  
  
      def _scan_ast(self, module, module_code_object_ast):
          """
          Parse and add all import statements from the passed abstract syntax
          tree (AST) of the passed source module to this graph, non-recursively.
  
          Parameters
          ----------
          module : Node
              Graph node of the module to be parsed.
          module_code_object_ast : ast.AST
              Abstract syntax tree (AST) of this module to be parsed.
          """
  
          visitor = _Visitor(self, module)
          visitor.visit(module_code_object_ast)
  
      #FIXME: Optimize. Global attributes added by this method are tested by
      #other methods *ONLY* for packages, implying this method should scan and
      #handle opcodes pertaining to global attributes (e.g.,
      #"STORE_NAME", "DELETE_GLOBAL") only if the passed "module"
      #object is an instance of the "Package" class. For all other module types,
      #these opcodes should simply be ignored.
      #
      #After doing so, the "Node._global_attr_names" attribute and all methods
      #using this attribute (e.g., Node.is_global()) should be moved from the
      #"Node" superclass to the "Package" subclass.
      def _scan_bytecode(
          self, module, module_code_object, is_scanning_imports):
          """
          Parse and add all import statements from the passed code object of the
          passed source module to this graph, non-recursively.
  
          This method parses all reasonably parsable operations (i.e., operations
          that are both syntactically and semantically parsable _without_
          requiring Turing-complete interpretation) directly or indirectly
          involving module importation from this code object. This includes:
  
          * `IMPORT_NAME`, denoting an import statement. Ignored unless
            the passed `is_scanning_imports` parameter is `True`.
          * `STORE_NAME` and `STORE_GLOBAL`, denoting the
            declaration of a global attribute (e.g., class, variable) in this
            module. This method stores each such declaration for subsequent
            lookup. While global attributes are usually irrelevant to import
            parsing, they remain the only means of distinguishing erroneous
            non-ignorable attempts to import non-existent submodules of a package
            from successful ignorable attempts to import existing global
            attributes of a package's `__init__` submodule (e.g., the `bar` in
            `from foo import bar`, which is either a non-ignorable submodule of
            `foo` or an ignorable global attribute of `foo.__init__`).
          * `DELETE_NAME` and `DELETE_GLOBAL`, denoting the
            undeclaration of a previously declared global attribute in this
            module.
  
          Since `ModuleGraph` is _not_ intended to replicate the behaviour of a
          full-featured Turing-complete Python interpreter, this method ignores
          operations that are _not_ reasonably parsable from this code object --
          even those directly or indirectly involving module importation. This
          includes:
  
          * `STORE_ATTR(namei)`, implementing `TOS.name = TOS1`. If `TOS` is the
            name of a target module currently imported into the namespace of the
            passed source module, this opcode would ideally be parsed to add that
            global attribute to that target module. Since this addition only
            conditionally occurs on the importation of this source module and
            execution of the code branch in this module performing this addition,
            however, that global _cannot_ be unconditionally added to that target
            module. In short, only Turing-complete behaviour suffices.
          * `DELETE_ATTR(namei)`, implementing `del TOS.name`. If `TOS` is the
            name of a target module currently imported into the namespace of the
            passed source module, this opcode would ideally be parsed to remove
            that global attribute from that target module. Again, however, only
            Turing-complete behaviour suffices.
  
          Parameters
          ----------
          module : Node
              Graph node of the module to be parsed.
          module_code_object : PyCodeObject
              Code object of the module to be parsed.
          is_scanning_imports : bool
              `True` only if this method is parsing import statements from
              `IMPORT_NAME` opcodes. If `False`, no import statements will be
              parsed. This parameter is typically:
              * `True` when parsing this module's code object for such imports.
              * `False` when parsing this module's abstract syntax tree (AST)
                (rather than code object) for such imports. In this case, that
                parsing will have already parsed import statements, which this
                parsing must avoid repeating.
          """
          level = None
          fromlist = None
  
          # 'deque' is a list-like container with fast appends, pops on
          # either end, and automatically discarding elements too much.
          prev_insts = deque(maxlen=2)
          for inst in util.iterate_instructions(module_code_object):
              if not inst:
                  continue
              # If this is an import statement originating from this module,
              # parse this import.
              #
              # Note that the related "IMPORT_FROM" opcode need *NOT* be parsed.
              # "IMPORT_NAME" suffices. For further details, see
              #     http://probablyprogramming.com/2008/04/14/python-import_name
              if inst.opname == 'IMPORT_NAME':
                  # If this method is ignoring import statements, skip to the
                  # next opcode.
                  if not is_scanning_imports:
                      continue
  
                  assert prev_insts[-2].opname == 'LOAD_CONST'
                  assert prev_insts[-1].opname == 'LOAD_CONST'
  
                  # Python >=2.5: LOAD_CONST flags, LOAD_CONST names, IMPORT_NAME name
                  level = prev_insts[-2].argval
                  fromlist = prev_insts[-1].argval
  
                  assert fromlist is None or type(fromlist) is tuple
                  target_module_partname = inst.argval
  
                  #FIXME: The exact same logic appears in _collect_import(),
                  #which isn't particularly helpful. Instead, defer this logic
                  #until later by:
                  #
                  #* Refactor the "_deferred_imports" list to contain 2-tuples
                  #  "(_safe_import_hook_args, _safe_import_hook_kwargs)" rather
                  #  than 3-tuples "(have_star, _safe_import_hook_args,
                  #  _safe_import_hook_kwargs)".
                  #* Stop prepending these tuples by a "have_star" boolean both
                  #  here, in _collect_import(), and in _process_imports().
                  #* Shift the logic below to _process_imports().
                  #* Remove the same logic from _collect_import().
                  have_star = False
                  if fromlist is not None:
                      fromlist = uniq(fromlist)
                      if '*' in fromlist:
                          fromlist.remove('*')
                          have_star = True
  
                  # Record this import as originating from this module for
                  # subsequent handling by the _process_imports() method.
                  module._deferred_imports.append((
                      have_star,
                      (target_module_partname, module, fromlist, level),
                      {}
                  ))
  
              elif inst.opname in ('STORE_NAME', 'STORE_GLOBAL'):
                  # If this is the declaration of a global attribute (e.g.,
                  # class, variable) in this module, store this declaration for
                  # subsequent lookup. See method docstring for further details.
                  #
                  # Global attributes are usually irrelevant to import parsing, but
                  # remain the only means of distinguishing erroneous non-ignorable
                  # attempts to import non-existent submodules of a package from
                  # successful ignorable attempts to import existing global
                  # attributes of a package's "__init__" submodule (e.g., the "bar"
                  # in "from foo import bar", which is either a non-ignorable
                  # submodule of "foo" or an ignorable global attribute of
                  # "foo.__init__").
                  name = inst.argval
                  module.add_global_attr(name)
  
              elif inst.opname in ('DELETE_NAME', 'DELETE_GLOBAL'):
                  # If this is the undeclaration of a previously declared global
                  # attribute (e.g., class, variable) in this module, remove that
                  # declaration to prevent subsequent lookup. See method docstring
                  # for further details.
                  name = inst.argval
                  module.remove_global_attr_if_found(name)
  
              prev_insts.append(inst)
  
  
      def _process_imports(self, source_module):
          """
          Graph all target modules whose importations were previously parsed from
          the passed source module by a prior call to the `_scan_code()` method
          and methods call by that method (e.g., `_scan_ast()`,
          `_scan_bytecode()`, `_scan_bytecode_stores()`).
  
          Parameters
          ----------
          source_module : Node
              Graph node of the source module to graph target imports for.
          """
  
          # If this source module imported no target modules, noop.
          if not source_module._deferred_imports:
              return
  
          # For each target module imported by this source module...
          for have_star, import_info, kwargs in source_module._deferred_imports:
              # Graph node of the target module specified by the "from" portion
              # of this "from"-style star import (e.g., an import resembling
              # "from {target_module_name} import *") or ignored otherwise.
              target_module = self._safe_import_hook(*import_info, **kwargs)[0]
  
              # If this is a "from"-style star import, process this import.
              if have_star:
                  #FIXME: Sadly, the current approach to importing attributes
                  #from "from"-style star imports is... simplistic. This should
                  #be revised as follows. If this target module is:
                  #
                  #* A package:
                  #  * Whose "__init__" submodule defines the "__all__" global
                  #    attribute, only attributes listed by this attribute should
                  #    be imported.
                  #  * Else, *NO* attributes should be imported.
                  #* A non-package:
                  #  * Defining the "__all__" global attribute, only attributes
                  #    listed by this attribute should be imported.
                  #  * Else, only public attributes whose names are *NOT*
                  #    prefixed by "_" should be imported.
                  source_module.add_global_attrs_from_module(target_module)
  
                  source_module._starimported_ignored_module_names.update(
                      target_module._starimported_ignored_module_names)
  
                  # If this target module has no code object and hence is
                  # unparsable, record its name for posterity.
                  if target_module.code is None:
                      target_module_name = import_info[0]
                      source_module._starimported_ignored_module_names.add(
                          target_module_name)
  
          # For safety, prevent these imports from being reprocessed.
          source_module._deferred_imports = None
  
  
      def _load_package(self, fqname, pathname, pkgpath):
          """
          Called only when an imp.PKG_DIRECTORY is found
          """
          self.msgin(2, "load_package", fqname, pathname, pkgpath)
          newname = _replacePackageMap.get(fqname)
          if newname:
              fqname = newname
  
          ns_pkgpath = _namespace_package_path(fqname, pkgpath or [], self.path)
          if ns_pkgpath or pkgpath:
              # this is a namespace package
              m = self.createNode(NamespacePackage, fqname)
              m.filename = '-'
              m.packagepath = ns_pkgpath
          else:
              m = self.createNode(Package, fqname)
              m.filename = pathname
              # PEP-302-compliant loaders return the pathname of the
              # `__init__`-file, not the packge directory.
              if os.path.basename(pathname).startswith('__init__.'):
                  pathname = os.path.dirname(pathname)
              m.packagepath = [pathname] + ns_pkgpath
  
          # As per comment at top of file, simulate runtime packagepath additions.
          m.packagepath = m.packagepath + self._package_path_map.get(fqname, [])
  
          try:
              self.msg(2, "find __init__ for %s"%(m.packagepath,))
              fp, buf, stuff = self._find_module("__init__", m.packagepath, parent=m)
          except ImportError:
              pass
  
          else:
              try:
                  self.msg(2, "load __init__ for %s"%(m.packagepath,))
                  self._load_module(fqname, fp, buf, stuff)
              finally:
                  if fp is not None:
                      fp.close()
          self.msgout(2, "load_package ->", m)
          return m
  
  
      def _find_module(self, name, path, parent=None):
          """
          3-tuple describing the physical location of the module with the passed
          name if this module is physically findable _or_ raise `ImportError`.
  
          This high-level method wraps the low-level `modulegraph.find_module()`
          function with additional support for graph-based module caching.
  
          Parameters
          ----------
          name : str
              Fully-qualified name of the Python module to be found.
          path : list
              List of the absolute paths of all directories to search for this
              module _or_ `None` if the default path list `self.path` is to be
              searched.
          parent : Node
              Package containing this module if this module is a submodule of a
              package _or_ `None` if this is a top-level module.
  
          Returns
          ----------
          (file_handle, filename, metadata)
              See `modulegraph._find_module()` for details.
  
          Raises
          ----------
          ImportError
              If this module is _not_ found.
          """
  
          if parent is not None:
              # assert path is not None
              fullname = parent.identifier + '.' + name
          else:
              fullname = name
  
          node = self.findNode(fullname)
          if node is not None:
              self.msg(3, "find_module: already included?", node)
              raise ImportError(name)
  
          if path is None:
              if name in sys.builtin_module_names:
                  return (None, None, ("", "", imp.C_BUILTIN))
  
              path = self.path
  
          return self._find_module_path(fullname, name, path)
  
  
      def _find_module_path(self, fullname, module_name, search_dirs):
          """
          3-tuple describing the physical location of the module with the passed
          name if this module is physically findable _or_ raise `ImportError`.
  
          This low-level function is a variant on the standard `imp.find_module()`
          function with additional support for:
  
          * Multiple search paths. The passed list of absolute paths will be
            iteratively searched for the first directory containing a file
            corresponding to this module.
          * Compressed (e.g., zipped) packages.
  
          For efficiency, the higher level `ModuleGraph._find_module()` method
          wraps this function with support for module caching.
  
          Parameters
          ----------
          module_name : str
              Fully-qualified name of the module to be found.
          search_dirs : list
              List of the absolute paths of all directories to search for this
              module (in order). Searching will halt at the first directory
              containing this module.
  
          Returns
          ----------
          (file_handle, filename, metadata)
              3-tuple describing the physical location of this module, where:
              * `file_handle` is an open read-only file handle from which the
                on-disk contents of this module may be read if this is a
                pure-Python module or `None` otherwise (e.g., if this is a
                package or C extension).
              * `filename` is the absolute path of this file.
              * `metadata` is itself a 3-tuple `(filetype, open_mode, imp_type)`.
                See the `_IMPORTABLE_FILETYPE_TO_METADATA` dictionary for
                details.
  
          Raises
          ----------
          ImportError
              If this module is _not_ found.
          """
          self.msgin(4, "_find_module_path <-", fullname, search_dirs)
  
          # TODO: Under:
          #
          # * Python 3.3, the following logic should be replaced by logic
          #   leveraging only the "importlib" module.
          # * Python 3.4, the following logic should be replaced by a call to
          #   importlib.util.find_spec().
  
          # Top-level 3-tuple to be returned.
          path_data = None
  
          # File handle to be returned.
          file_handle = None
  
          # List of the absolute paths of all directories comprising the
          # namespace package to which this module belongs if any.
          namespace_dirs = []
  
          try:
              for search_dir in search_dirs:
                  # PEP 302-compliant importer making loaders for this directory.
                  importer = pkgutil.get_importer(search_dir)
  
                  # If this directory is not importable, continue.
                  if importer is None:
                      # self.msg(4, "_find_module_path importer not found", search_dir)
                      continue
  
                  # Get the PEP 302-compliant loader object loading this module.
                  #
                  # If this importer defines the PEP 302-compliant find_loader()
                  # method, prefer that.
                  if hasattr(importer, 'find_loader'):
                      loader, loader_namespace_dirs = importer.find_loader(
                          module_name)
                      namespace_dirs.extend(loader_namespace_dirs)
                  # Else if this importer defines the Python 2-specific
                  # find_module() method, fall back to that. Despite the method
                  # name, this method returns a loader rather than a module.
                  elif hasattr(importer, 'find_module'):
                      loader = importer.find_module(module_name)
                  # Else, raise an exception.
                  else:
                      raise ImportError(
                          "Module %r importer %r loader unobtainable" % (module_name, importer))
  
                  # If this module is not loadable from this directory, continue.
                  if loader is None:
                      # self.msg(4, "_find_module_path loader not found", search_dir)
                      continue
  
                  # 3-tuple of metadata to be returned.
                  metadata = None
  
                  # Absolute path of this module. If this module resides in a
                  # compressed archive, this is the absolute path of this module
                  # after extracting this module from that archive and hence
                  # should not exist; else, this path should typically exist.
                  pathname = None
  
                  # If this loader defines the PEP 302-compliant get_filename()
                  # method, preferably call that method first. Most if not all
                  # loaders (including zipimporter objects) define this method.
                  if hasattr(loader, 'get_filename'):
                      pathname = loader.get_filename(module_name)
                  # Else if this loader provides a "path" attribute, defer to that.
                  elif hasattr(loader, 'path'):
                      pathname = loader.path
                  # Else, raise an exception.
                  else:
                      raise ImportError(
                          "Module %r loader %r path unobtainable" % (module_name, loader))
  
                  # If no path was found, this is probably a namespace package. In
                  # such case, continue collecting namespace directories.
                  if pathname is None:
                      self.msg(4, "_find_module_path path not found", pathname)
                      continue
  
                  # If this loader defines the PEP 302-compliant is_package()
                  # method returning True, this is a non-namespace package.
                  if hasattr(loader, 'is_package') and loader.is_package(module_name):
                      metadata = ('', '', imp.PKG_DIRECTORY)
                  # Else, this is either a module or C extension.
                  else:
                      # In either case, this path must have a filetype.
                      filetype = os.path.splitext(pathname)[1]
                      if not filetype:
                          raise ImportError(
                              'Non-package module %r path %r has no filetype' % (module_name, pathname))
  
                      # 3-tuple of metadata specific to this filetype.
                      metadata = _IMPORTABLE_FILETYPE_TO_METADATA.get(
                          filetype, None)
                      if metadata is None:
                          raise ImportError(
                              'Non-package module %r filetype %r unrecognized' % (pathname, filetype))
  
                      # See "_IMPORTABLE_FILETYPE_TO_METADATA" for details.
                      open_mode = metadata[1]
                      imp_type = metadata[2]
  
                      # If this is a C extension, leave this path unopened.
                      if imp_type == imp.C_EXTENSION:
                          pass
                      # Else, this is a module.
                      #
                      # If this loader defines the PEP 302-compliant get_source()
                      # method, open the returned string as a file-like buffer.
                      elif imp_type == imp.PY_SOURCE and hasattr(loader, 'get_source'):
                          file_handle = StringIO(loader.get_source(module_name))
                      # If this loader defines the PEP 302-compliant get_code()
                      # method, open the returned object as a file-like buffer.
                      elif imp_type == imp.PY_COMPILED and hasattr(loader, 'get_code'):
                          try:
                              code_object = loader.get_code(module_name)
                              if code_object is None:
                                  file_handle = BytesIO(b'\0\0\0\0\0\0\0\0')
                              else:
                                  file_handle = _code_to_file(code_object)
                          except ImportError:
                              # post-bone the ImportError until load_module
                              file_handle = BytesIO(b'\0\0\0\0\0\0\0\0')
                      # If this is an uncompiled file under Python 3, open this
                      # file for encoding-aware text reading.
                      elif imp_type == imp.PY_SOURCE and sys.version_info[0] == 3:
                          with open(pathname, 'rb') as file_handle:
                              encoding = util.guess_encoding(file_handle)
                          file_handle = open(
                              pathname, open_mode, encoding=encoding)
                      # Else, this is either a compiled file or an uncompiled
                      # file under Python 2. In either case, open this file.
                      else:
                          file_handle = open(pathname, open_mode)
  
                  # Return such metadata.
                  path_data = (file_handle, pathname, metadata)
                  break
              # Else if this is a namespace package, return such metadata.
              else:
                  if namespace_dirs:
                      path_data = (None, namespace_dirs[0], (
                          '', namespace_dirs, imp.PKG_DIRECTORY))
          except UnicodeDecodeError as exc:
              self.msgout(1, "_find_module_path -> unicode error", exc)
          # Ensure that exceptions are logged, as this function is typically
          # called by the import_module() method which squelches ImportErrors.
          except Exception as exc:
              self.msgout(4, "_find_module_path -> exception", exc)
              raise
  
          # If this module was not found, raise an exception.
          self.msgout(4, "_find_module_path ->", path_data)
          if path_data is None:
              raise ImportError("No module named " + repr(module_name))
  
          return path_data
  
  
      def create_xref(self, out=None):
          global header, footer, entry, contpl, contpl_linked, imports
          if out is None:
              out = sys.stdout
          scripts = []
          mods = []
          for mod in self.flatten():
              name = os.path.basename(mod.identifier)
              if isinstance(mod, Script):
                  scripts.append((name, mod))
              else:
                  mods.append((name, mod))
          scripts.sort()
          mods.sort()
          scriptnames = [name for name, m in scripts]
          scripts.extend(mods)
          mods = scripts
  
          title = "modulegraph cross reference for "  + ', '.join(scriptnames)
          print(header % {"TITLE": title}, file=out)
  
          def sorted_namelist(mods):
              lst = [os.path.basename(mod.identifier) for mod in mods if mod]
              lst.sort()
              return lst
          for name, m in mods:
              content = ""
              if isinstance(m, BuiltinModule):
                  content = contpl % {"NAME": name,
                                      "TYPE": "<i>(builtin module)</i>"}
              elif isinstance(m, Extension):
                  content = contpl % {"NAME": name,\
                                      "TYPE": "<tt>%s</tt>" % m.filename}
              else:
                  url = pathname2url(m.filename or "")
                  content = contpl_linked % {"NAME": name, "URL": url,
                                             'TYPE': m.__class__.__name__}
              oute, ince = map(sorted_namelist, self.get_edges(m))
              if oute:
                  links = []
                  for n in oute:
                      links.append("""  <a href="#%s">%s</a>\n""" % (n, n))
                  # #8226 = bullet-point; can't use html-entities since the
                  # test-suite uses xml.etree.ElementTree.XMLParser, which
                  # does't supprot them.
                  links = " &#8226; ".join(links)
                  content += imports % {"HEAD": "imports", "LINKS": links}
              if ince:
                  links = []
                  for n in ince:
                      links.append("""  <a href="#%s">%s</a>\n""" % (n, n))
                  # #8226 = bullet-point; can't use html-entities since the
                  # test-suite uses xml.etree.ElementTree.XMLParser, which
                  # does't supprot them.
                  links = " &#8226; ".join(links)
                  content += imports % {"HEAD": "imported by", "LINKS": links}
              print(entry % {"NAME": name,"CONTENT": content}, file=out)
          print(footer, file=out)
  
  
      def itergraphreport(self, name='G', flatpackages=()):
          # XXX: Can this be implemented using Dot()?
          nodes = list(map(self.graph.describe_node, self.graph.iterdfs(self)))
          describe_edge = self.graph.describe_edge
          edges = deque()
          packagenodes = set()
          packageidents = {}
          nodetoident = {}
          inpackages = {}
          mainedges = set()
  
          # XXX - implement
          flatpackages = dict(flatpackages)
  
          def nodevisitor(node, data, outgoing, incoming):
              if not isinstance(data, Node):
                  return {'label': str(node)}
              #if isinstance(d, (ExcludedModule, MissingModule, BadModule)):
              #    return None
              s = '<f0> ' + type(data).__name__
              for i,v in enumerate(data.infoTuple()[:1], 1):
                  s += '| <f%d> %s' % (i,v)
              return {'label':s, 'shape':'record'}
  
  
          def edgevisitor(edge, data, head, tail):
              # XXX: This method nonsense, the edge
              # data is never initialized.
              if data == 'orphan':
                  return {'style':'dashed'}
              elif data == 'pkgref':
                  return {'style':'dotted'}
              return {}
  
          yield 'digraph %s {\n' % (name,)
          attr = dict(rankdir='LR', concentrate='true')
          cpatt  = '%s="%s"'
          for item in attr.items():
              yield '\t%s;\n' % (cpatt % item,)
  
          # find all packages (subgraphs)
          for (node, data, outgoing, incoming) in nodes:
              nodetoident[node] = getattr(data, 'identifier', None)
              if isinstance(data, Package):
                  packageidents[data.identifier] = node
                  inpackages[node] = set([node])
                  packagenodes.add(node)
  
  
          # create sets for subgraph, write out descriptions
          for (node, data, outgoing, incoming) in nodes:
              # update edges
              for edge in (describe_edge(e) for e in outgoing):
                  edges.append(edge)
  
              # describe node
              yield '\t"%s" [%s];\n' % (
                  node,
                  ','.join([
                      (cpatt % item) for item in
                      nodevisitor(node, data, outgoing, incoming).items()
                  ]),
              )
  
              inside = inpackages.get(node)
              if inside is None:
                  inside = inpackages[node] = set()
              ident = nodetoident[node]
              if ident is None:
                  continue
              pkgnode = packageidents.get(ident[:ident.rfind('.')])
              if pkgnode is not None:
                  inside.add(pkgnode)
  
  
          graph = []
          subgraphs = {}
          for key in packagenodes:
              subgraphs[key] = []
  
          while edges:
              edge, data, head, tail = edges.popleft()
              if ((head, tail)) in mainedges:
                  continue
              mainedges.add((head, tail))
              tailpkgs = inpackages[tail]
              common = inpackages[head] & tailpkgs
              if not common and tailpkgs:
                  usepkgs = sorted(tailpkgs)
                  if len(usepkgs) != 1 or usepkgs[0] != tail:
                      edges.append((edge, data, head, usepkgs[0]))
                      edges.append((edge, 'pkgref', usepkgs[-1], tail))
                      continue
              if common:
                  common = common.pop()
                  if tail == common:
                      edges.append((edge, data, tail, head))
                  elif head == common:
                      subgraphs[common].append((edge, 'pkgref', head, tail))
                  else:
                      edges.append((edge, data, common, head))
                      edges.append((edge, data, common, tail))
  
              else:
                  graph.append((edge, data, head, tail))
  
          def do_graph(edges, tabs):
              edgestr = tabs + '"%s" -> "%s" [%s];\n'
              # describe edge
              for (edge, data, head, tail) in edges:
                  attribs = edgevisitor(edge, data, head, tail)
                  yield edgestr % (
                      head,
                      tail,
                      ','.join([(cpatt % item) for item in attribs.items()]),
                  )
  
          for g, edges in subgraphs.items():
              yield '\tsubgraph "cluster_%s" {\n' % (g,)
              yield '\t\tlabel="%s";\n' % (nodetoident[g],)
              for s in do_graph(edges, '\t\t'):
                  yield s
              yield '\t}\n'
  
          for s in do_graph(graph, '\t'):
              yield s
  
          yield '}\n'
  
  
      def graphreport(self, fileobj=None, flatpackages=()):
          if fileobj is None:
              fileobj = sys.stdout
          fileobj.writelines(self.itergraphreport(flatpackages=flatpackages))
  
      def report(self):
          """Print a report to stdout, listing the found modules with their
          paths, as well as modules that are missing, or seem to be missing.
          """
          print()
          print("%-15s %-25s %s" % ("Class", "Name", "File"))
          print("%-15s %-25s %s" % ("-----", "----", "----"))
          # Print modules found
          sorted = [(os.path.basename(mod.identifier), mod) for mod in self.flatten()]
          sorted.sort()
          for (name, m) in sorted:
              print("%-15s %-25s %s" % (type(m).__name__, name, m.filename or ""))
  
      def _replace_paths_in_code(self, co):
          new_filename = original_filename = os.path.normpath(co.co_filename)
          for f, r in self.replace_paths:
              f = os.path.join(f, '')
              r = os.path.join(r, '')
              if original_filename.startswith(f):
                  new_filename = r + original_filename[len(f):]
                  break
  
          else:
              return co
  
          consts = list(co.co_consts)
          for i in range(len(consts)):
              if isinstance(consts[i], type(co)):
                  consts[i] = self._replace_paths_in_code(consts[i])
  
          code_func = type(co)
  
          if hasattr(co, 'co_kwonlyargcount'):
              return code_func(co.co_argcount, co.co_kwonlyargcount, co.co_nlocals, co.co_stacksize,
                           co.co_flags, co.co_code, tuple(consts), co.co_names,
                           co.co_varnames, new_filename, co.co_name,
                           co.co_firstlineno, co.co_lnotab,
                           co.co_freevars, co.co_cellvars)
          else:
              return code_func(co.co_argcount, co.co_nlocals, co.co_stacksize,
                           co.co_flags, co.co_code, tuple(consts), co.co_names,
                           co.co_varnames, new_filename, co.co_name,
                           co.co_firstlineno, co.co_lnotab,
                           co.co_freevars, co.co_cellvars)
  