Lib/modulefinder.py

   1 """Find modules used by a script, using introspection."""
   2
   3 # This module should be kept compatible with Python 1.5.2, see PEP 291.
   4
   5 import dis
   6 import imp
   7 import marshal
   8 import os
   9 import sys
  10 import new
  11
  12 if hasattr(sys.__stdout__, "newlines"):
  13     READ_MODE = "U"  # universal line endings
  14 else:
  15     # remain compatible with Python  < 2.3
  16     READ_MODE = "r"
  17
  18 LOAD_CONST = dis.opname.index('LOAD_CONST')
  19 IMPORT_NAME = dis.opname.index('IMPORT_NAME')
  20 STORE_NAME = dis.opname.index('STORE_NAME')
  21 STORE_GLOBAL = dis.opname.index('STORE_GLOBAL')
  22 STORE_OPS = [STORE_NAME, STORE_GLOBAL]
  23
  24 # Modulefinder does a good job at simulating Python's, but it can not
  25 # handle __path__ modifications packages make at runtime.  Therefore there
  26 # is a mechanism whereby you can register extra paths in this map for a
  27 # package, and it will be honored.
  28
  29 # Note this is a mapping is lists of paths.
  30 packagePathMap = {}
  31
  32 # A Public interface
  33 def AddPackagePath(packagename, path):
  34     paths = packagePathMap.get(packagename, [])
  35     paths.append(path)
  36     packagePathMap[packagename] = paths
  37
  38 replacePackageMap = {}
  39
  40 # This ReplacePackage mechanism allows modulefinder to work around the
  41 # way the _xmlplus package injects itself under the name "xml" into
  42 # sys.modules at runtime by calling ReplacePackage("_xmlplus", "xml")
  43 # before running ModuleFinder.
  44
  45 def ReplacePackage(oldname, newname):
  46     replacePackageMap[oldname] = newname
  47
  48
  49 class Module:
  50
  51     def __init__(self, name, file=None, path=None):
  52         self.__name__ = name
  53         self.__file__ = file
  54         self.__path__ = path
  55         self.__code__ = None
  56         # The set of global names that are assigned to in the module.
  57         # This includes those names imported through starimports of
  58         # Python modules.
  59         self.globalnames = {}
  60         # The set of starimports this module did that could not be
  61         # resolved, ie. a starimport from a non-Python module.
  62         self.starimports = {}
  63
  64     def __repr__(self):
  65         s = "Module(%s" % `self.__name__`
  66         if self.__file__ is not None:
  67             s = s + ", %s" % `self.__file__`
  68         if self.__path__ is not None:
  69             s = s + ", %s" % `self.__path__`
  70         s = s + ")"
  71         return s
  72
  73 class ModuleFinder:
  74
  75     def __init__(self, path=None, debug=0, excludes=[], replace_paths=[]):
  76         if path is None:
  77             path = sys.path
  78         self.path = path
  79         self.modules = {}
  80         self.badmodules = {}
  81         self.debug = debug
  82         self.indent = 0
  83         self.excludes = excludes
  84         self.replace_paths = replace_paths
  85         self.processed_paths = []   # Used in debugging only
  86
  87     def msg(self, level, str, *args):
  88         if level <= self.debug:
  89             for i in range(self.indent):
  90                 print "   ",
  91             print str,
  92             for arg in args:
  93                 print repr(arg),
  94             print
  95
  96     def msgin(self, *args):
  97         level = args[0]
  98         if level <= self.debug:
  99             self.indent = self.indent + 1
 100             self.msg(*args)
 101
 102     def msgout(self, *args):
 103         level = args[0]
 104         if level <= self.debug:
 105             self.indent = self.indent - 1
 106             self.msg(*args)
 107
 108     def run_script(self, pathname):
 109         self.msg(2, "run_script", pathname)
 110         fp = open(pathname, READ_MODE)
 111         stuff = ("", "r", imp.PY_SOURCE)
 112         self.load_module('__main__', fp, pathname, stuff)
 113
 114     def load_file(self, pathname):
 115         dir, name = os.path.split(pathname)
 116         name, ext = os.path.splitext(name)
 117         fp = open(pathname, READ_MODE)
 118         stuff = (ext, "r", imp.PY_SOURCE)
 119         self.load_module(name, fp, pathname, stuff)
 120
 121     def import_hook(self, name, caller=None, fromlist=None):
 122         self.msg(3, "import_hook", name, caller, fromlist)
 123         parent = self.determine_parent(caller)
 124         q, tail = self.find_head_package(parent, name)
 125         m = self.load_tail(q, tail)
 126         if not fromlist:
 127             return q
 128         if m.__path__:
 129             self.ensure_fromlist(m, fromlist)
 130         return None
 131
 132     def determine_parent(self, caller):
 133         self.msgin(4, "determine_parent", caller)
 134         if not caller:
 135             self.msgout(4, "determine_parent -> None")
 136             return None
 137         pname = caller.__name__
 138         if caller.__path__:
 139             parent = self.modules[pname]
 140             assert caller is parent
 141             self.msgout(4, "determine_parent ->", parent)
 142             return parent
 143         if '.' in pname:
 144             i = pname.rfind('.')
 145             pname = pname[:i]
 146             parent = self.modules[pname]
 147             assert parent.__name__ == pname
 148             self.msgout(4, "determine_parent ->", parent)
 149             return parent
 150         self.msgout(4, "determine_parent -> None")
 151         return None
 152
 153     def find_head_package(self, parent, name):
 154         self.msgin(4, "find_head_package", parent, name)
 155         if '.' in name:
 156             i = name.find('.')
 157             head = name[:i]
 158             tail = name[i+1:]
 159         else:
 160             head = name
 161             tail = ""
 162         if parent:
 163             qname = "%s.%s" % (parent.__name__, head)
 164         else:
 165             qname = head
 166         q = self.import_module(head, qname, parent)
 167         if q:
 168             self.msgout(4, "find_head_package ->", (q, tail))
 169             return q, tail
 170         if parent:
 171             qname = head
 172             parent = None
 173             q = self.import_module(head, qname, parent)
 174             if q:
 175                 self.msgout(4, "find_head_package ->", (q, tail))
 176                 return q, tail
 177         self.msgout(4, "raise ImportError: No module named", qname)
 178         raise ImportError, "No module named " + qname
 179
 180     def load_tail(self, q, tail):
 181         self.msgin(4, "load_tail", q, tail)
 182         m = q
 183         while tail:
 184             i = tail.find('.')
 185             if i < 0: i = len(tail)
 186             head, tail = tail[:i], tail[i+1:]
 187             mname = "%s.%s" % (m.__name__, head)
 188             m = self.import_module(head, mname, m)
 189             if not m:
 190                 self.msgout(4, "raise ImportError: No module named", mname)
 191                 raise ImportError, "No module named " + mname
 192         self.msgout(4, "load_tail ->", m)
 193         return m
 194
 195     def ensure_fromlist(self, m, fromlist, recursive=0):
 196         self.msg(4, "ensure_fromlist", m, fromlist, recursive)
 197         for sub in fromlist:
 198             if sub == "*":
 199                 if not recursive:
 200                     all = self.find_all_submodules(m)
 201                     if all:
 202                         self.ensure_fromlist(m, all, 1)
 203             elif not hasattr(m, sub):
 204                 subname = "%s.%s" % (m.__name__, sub)
 205                 submod = self.import_module(sub, subname, m)
 206                 if not submod:
 207                     raise ImportError, "No module named " + subname
 208
 209     def find_all_submodules(self, m):
 210         if not m.__path__:
 211             return
 212         modules = {}
 213         suffixes = [".py", ".pyc", ".pyo"]
 214         for dir in m.__path__:
 215             try:
 216                 names = os.listdir(dir)
 217             except os.error:
 218                 self.msg(2, "can't list directory", dir)
 219                 continue
 220             for name in names:
 221                 mod = None
 222                 for suff in suffixes:
 223                     n = len(suff)
 224                     if name[-n:] == suff:
 225                         mod = name[:-n]
 226                         break
 227                 if mod and mod != "__init__":
 228                     modules[mod] = mod
 229         return modules.keys()
 230
 231     def import_module(self, partname, fqname, parent):
 232         self.msgin(3, "import_module", partname, fqname, parent)
 233         try:
 234             m = self.modules[fqname]
 235         except KeyError:
 236             pass
 237         else:
 238             self.msgout(3, "import_module ->", m)
 239             return m
 240         if self.badmodules.has_key(fqname):
 241             self.msgout(3, "import_module -> None")
 242             return None
 243         try:
 244             fp, pathname, stuff = self.find_module(partname,
 245                                                    parent and parent.__path__, parent)
 246         except ImportError:
 247             self.msgout(3, "import_module ->", None)
 248             return None
 249         try:
 250             m = self.load_module(fqname, fp, pathname, stuff)
 251         finally:
 252             if fp: fp.close()
 253         if parent:
 254             setattr(parent, partname, m)
 255         self.msgout(3, "import_module ->", m)
 256         return m
 257
 258     def load_module(self, fqname, fp, pathname, (suffix, mode, type)):
 259         self.msgin(2, "load_module", fqname, fp and "fp", pathname)
 260         if type == imp.PKG_DIRECTORY:
 261             m = self.load_package(fqname, pathname)
 262             self.msgout(2, "load_module ->", m)
 263             return m
 264         if type == imp.PY_SOURCE:
 265             co = compile(fp.read()+'\n', pathname, 'exec')
 266         elif type == imp.PY_COMPILED:
 267             if fp.read(4) != imp.get_magic():
 268                 self.msgout(2, "raise ImportError: Bad magic number", pathname)
 269                 raise ImportError, "Bad magic number in %s" % pathname
 270             fp.read(4)
 271             co = marshal.load(fp)
 272         else:
 273             co = None
 274         m = self.add_module(fqname)
 275         m.__file__ = pathname
 276         if co:
 277             if self.replace_paths:
 278                 co = self.replace_paths_in_code(co)
 279             m.__code__ = co
 280             self.scan_code(co, m)
 281         self.msgout(2, "load_module ->", m)
 282         return m
 283
 284     def _add_badmodule(self, name, caller):
 285         if name not in self.badmodules:
 286             self.badmodules[name] = {}
 287         self.badmodules[name][caller.__name__] = 1
 288
 289     def _safe_import_hook(self, name, caller, fromlist):
 290         # wrapper for self.import_hook() that won't raise ImportError
 291         if name in self.badmodules:
 292             self._add_badmodule(name, caller)
 293             return
 294         try:
 295             self.import_hook(name, caller)
 296         except ImportError, msg:
 297             self.msg(2, "ImportError:", str(msg))
 298             self._add_badmodule(name, caller)
 299         else:
 300             if fromlist:
 301                 for sub in fromlist:
 302                     if sub in self.badmodules:
 303                         self._add_badmodule(sub, caller)
 304                         continue
 305                     try:
 306                         self.import_hook(name, caller, [sub])
 307                     except ImportError, msg:
 308                         self.msg(2, "ImportError:", str(msg))
 309                         fullname = name + "." + sub
 310                         self._add_badmodule(fullname, caller)
 311
 312     def scan_code(self, co, m):
 313         code = co.co_code
 314         n = len(code)
 315         i = 0
 316         fromlist = None
 317         while i < n:
 318             c = code[i]
 319             i = i+1
 320             op = ord(c)
 321             if op >= dis.HAVE_ARGUMENT:
 322                 oparg = ord(code[i]) + ord(code[i+1])*256
 323                 i = i+2
 324             if op == LOAD_CONST:
 325                 # An IMPORT_NAME is always preceded by a LOAD_CONST, it's
 326                 # a tuple of "from" names, or None for a regular import.
 327                 # The tuple may contain "*" for "from <mod> import *"
 328                 fromlist = co.co_consts[oparg]
 329             elif op == IMPORT_NAME:
 330                 assert fromlist is None or type(fromlist) is tuple
 331                 name = co.co_names[oparg]
 332                 have_star = 0
 333                 if fromlist is not None:
 334                     if "*" in fromlist:
 335                         have_star = 1
 336                     fromlist = [f for f in fromlist if f != "*"]
 337                 self._safe_import_hook(name, m, fromlist)
 338                 if have_star:
 339                     # We've encountered an "import *". If it is a Python module,
 340                     # the code has already been parsed and we can suck out the
 341                     # global names.
 342                     mm = None
 343                     if m.__path__:
 344                         # At this point we don't know whether 'name' is a
 345                         # submodule of 'm' or a global module. Let's just try
 346                         # the full name first.
 347                         mm = self.modules.get(m.__name__ + "." + name)
 348                     if mm is None:
 349                         mm = self.modules.get(name)
 350                     if mm is not None:
 351                         m.globalnames.update(mm.globalnames)
 352                         m.starimports.update(mm.starimports)
 353                         if mm.__code__ is None:
 354                             m.starimports[name] = 1
 355                     else:
 356                         m.starimports[name] = 1
 357             elif op in STORE_OPS:
 358                 # keep track of all global names that are assigned to
 359                 name = co.co_names[oparg]
 360                 m.globalnames[name] = 1
 361         for c in co.co_consts:
 362             if isinstance(c, type(co)):
 363                 self.scan_code(c, m)
 364
 365     def load_package(self, fqname, pathname):
 366         self.msgin(2, "load_package", fqname, pathname)
 367         newname = replacePackageMap.get(fqname)
 368         if newname:
 369             fqname = newname
 370         m = self.add_module(fqname)
 371         m.__file__ = pathname
 372         m.__path__ = [pathname]
 373
 374         # As per comment at top of file, simulate runtime __path__ additions.
 375         m.__path__ = m.__path__ + packagePathMap.get(fqname, [])
 376
 377         fp, buf, stuff = self.find_module("__init__", m.__path__)
 378         self.load_module(fqname, fp, buf, stuff)
 379         self.msgout(2, "load_package ->", m)
 380         return m
 381
 382     def add_module(self, fqname):
 383         if self.modules.has_key(fqname):
 384             return self.modules[fqname]
 385         self.modules[fqname] = m = Module(fqname)
 386         return m
 387
 388     def find_module(self, name, path, parent=None):
 389         if parent is not None:
 390             fullname = parent.__name__+'.'+name
 391         else:
 392             fullname = name
 393         if fullname in self.excludes:
 394             self.msgout(3, "find_module -> Excluded", fullname)
 395             raise ImportError, name
 396
 397         if path is None:
 398             if name in sys.builtin_module_names:
 399                 return (None, None, ("", "", imp.C_BUILTIN))
 400
 401             path = self.path
 402         return imp.find_module(name, path)
 403
 404     def report(self):
 405         """Print a report to stdout, listing the found modules with their
 406         paths, as well as modules that are missing, or seem to be missing.
 407         """
 408         print
 409         print "  %-25s %s" % ("Name", "File")
 410         print "  %-25s %s" % ("----", "----")
 411         # Print modules found
 412         keys = self.modules.keys()
 413         keys.sort()
 414         for key in keys:
 415             m = self.modules[key]
 416             if m.__path__:
 417                 print "P",
 418             else:
 419                 print "m",
 420             print "%-25s" % key, m.__file__ or ""
 421
 422         # Print missing modules
 423         missing, maybe = self.any_missing_maybe()
 424         if missing:
 425             print
 426             print "Missing modules:"
 427             for name in missing:
 428                 mods = self.badmodules[name].keys()
 429                 mods.sort()
 430                 print "?", name, "imported from", ', '.join(mods)
 431         # Print modules that may be missing, but then again, maybe not...
 432         if maybe:
 433             print
 434             print "Submodules thay appear to be missing, but could also be",
 435             print "global names in the parent package:"
 436             for name in maybe:
 437                 mods = self.badmodules[name].keys()
 438                 mods.sort()
 439                 print "?", name, "imported from", ', '.join(mods)
 440
 441     def any_missing(self):
 442         """Return a list of modules that appear to be missing. Use
 443         any_missing_maybe() if you want to know which modules are
 444         certain to be missing, and which *may* be missing.
 445         """
 446         missing, maybe = self.any_missing_maybe()
 447         return missing + maybe
 448
 449     def any_missing_maybe(self):
 450         """Return two lists, one with modules that are certainly missing
 451         and one with modules that *may* be missing. The latter names could
 452         either be submodules *or* just global names in the package.
 453
 454         The reason it can't always be determined is that it's impossible to
 455         tell which names are imported when "from module import *" is done
 456         with an extension module, short of actually importing it.
 457         """
 458         missing = []
 459         maybe = []
 460         for name in self.badmodules:
 461             if name in self.excludes:
 462                 continue
 463             i = name.rfind(".")
 464             if i < 0:
 465                 missing.append(name)
 466                 continue
 467             subname = name[i+1:]
 468             pkgname = name[:i]
 469             pkg = self.modules.get(pkgname)
 470             if pkg is not None:
 471                 if pkgname in self.badmodules[name]:
 472                     # The package tried to import this module itself and
 473                     # failed. It's definitely missing.
 474                     missing.append(name)
 475                 elif subname in pkg.globalnames:
 476                     # It's a global in the package: definitely not missing.
 477                     pass
 478                 elif pkg.starimports:
 479                     # It could be missing, but the package did an "import *"
 480                     # from a non-Python module, so we simply can't be sure.
 481                     maybe.append(name)
 482                 else:
 483                     # It's not a global in the package, the package didn't
 484                     # do funny star imports, it's very likely to be missing.
 485                     # The symbol could be inserted into the package from the
 486                     # outside, but since that's not good style we simply list
 487                     # it missing.
 488                     missing.append(name)
 489             else:
 490                 missing.append(name)
 491         missing.sort()
 492         maybe.sort()
 493         return missing, maybe
 494
 495     def replace_paths_in_code(self, co):
 496         new_filename = original_filename = os.path.normpath(co.co_filename)
 497         for f, r in self.replace_paths:
 498             if original_filename.startswith(f):
 499                 new_filename = r + original_filename[len(f):]
 500                 break
 501
 502         if self.debug and original_filename not in self.processed_paths:
 503             if new_filename != original_filename:
 504                 self.msgout(2, "co_filename %r changed to %r" \
 505                                     % (original_filename,new_filename,))
 506             else:
 507                 self.msgout(2, "co_filename %r remains unchanged" \
 508                                     % (original_filename,))
 509             self.processed_paths.append(original_filename)
 510
 511         consts = list(co.co_consts)
 512         for i in range(len(consts)):
 513             if isinstance(consts[i], type(co)):
 514                 consts[i] = self.replace_paths_in_code(consts[i])
 515
 516         return new.code(co.co_argcount, co.co_nlocals, co.co_stacksize,
 517                          co.co_flags, co.co_code, tuple(consts), co.co_names,
 518                          co.co_varnames, new_filename, co.co_name,
 519                          co.co_firstlineno, co.co_lnotab,
 520                          co.co_freevars, co.co_cellvars)
 521
 522
 523 def test():
 524     # Parse command line
 525     import getopt
 526     try:
 527         opts, args = getopt.getopt(sys.argv[1:], "dmp:qx:")
 528     except getopt.error, msg:
 529         print msg
 530         return
 531
 532     # Process options
 533     debug = 1
 534     domods = 0
 535     addpath = []
 536     exclude = []
 537     for o, a in opts:
 538         if o == '-d':
 539             debug = debug + 1
 540         if o == '-m':
 541             domods = 1
 542         if o == '-p':
 543             addpath = addpath + a.split(os.pathsep)
 544         if o == '-q':
 545             debug = 0
 546         if o == '-x':
 547             exclude.append(a)
 548
 549     # Provide default arguments
 550     if not args:
 551         script = "hello.py"
 552     else:
 553         script = args[0]
 554
 555     # Set the path based on sys.path and the script directory
 556     path = sys.path[:]
 557     path[0] = os.path.dirname(script)
 558     path = addpath + path
 559     if debug > 1:
 560         print "path:"
 561         for item in path:
 562             print "   ", `item`
 563
 564     # Create the module finder and turn its crank
 565     mf = ModuleFinder(path, debug, exclude)
 566     for arg in args[1:]:
 567         if arg == '-m':
 568             domods = 1
 569             continue
 570         if domods:
 571             if arg[-2:] == '.*':
 572                 mf.import_hook(arg[:-2], None, ["*"])
 573             else:
 574                 mf.import_hook(arg)
 575         else:
 576             mf.load_file(arg)
 577     mf.run_script(script)
 578     mf.report()
 579     return mf  # for -i debugging
 580
 581
 582 if __name__ == '__main__':
 583     try:
 584         mf = test()
 585     except KeyboardInterrupt:
 586         print "\n[interrupt]"