sys/lib/python/inspect.py

   1 # -*- coding: iso-8859-1 -*-
   2 """Get useful information from live Python objects.
   3
   4 This module encapsulates the interface provided by the internal special
   5 attributes (func_*, co_*, im_*, tb_*, etc.) in a friendlier fashion.
   6 It also provides some help for examining source code and class layout.
   7
   8 Here are some of the useful functions provided by this module:
   9
  10     ismodule(), isclass(), ismethod(), isfunction(), istraceback(),
  11         isframe(), iscode(), isbuiltin(), isroutine() - check object types
  12     getmembers() - get members of an object that satisfy a given condition
  13
  14     getfile(), getsourcefile(), getsource() - find an object's source code
  15     getdoc(), getcomments() - get documentation on an object
  16     getmodule() - determine the module that an object came from
  17     getclasstree() - arrange classes so as to represent their hierarchy
  18
  19     getargspec(), getargvalues() - get info about function arguments
  20     formatargspec(), formatargvalues() - format an argument spec
  21     getouterframes(), getinnerframes() - get info about frames
  22     currentframe() - get the current stack frame
  23     stack(), trace() - get info about frames on the stack or in a traceback
  24 """
  25
  26 # This module is in the public domain.  No warranties.
  27
  28 __author__ = 'Ka-Ping Yee <ping@lfw.org>'
  29 __date__ = '1 Jan 2001'
  30
  31 import sys, os, types, string, re, dis, imp, tokenize, linecache
  32 from operator import attrgetter
  33
  34 # ----------------------------------------------------------- type-checking
  35 def ismodule(object):
  36     """Return true if the object is a module.
  37
  38     Module objects provide these attributes:
  39         __doc__         documentation string
  40         __file__        filename (missing for built-in modules)"""
  41     return isinstance(object, types.ModuleType)
  42
  43 def isclass(object):
  44     """Return true if the object is a class.
  45
  46     Class objects provide these attributes:
  47         __doc__         documentation string
  48         __module__      name of module in which this class was defined"""
  49     return isinstance(object, types.ClassType) or hasattr(object, '__bases__')
  50
  51 def ismethod(object):
  52     """Return true if the object is an instance method.
  53
  54     Instance method objects provide these attributes:
  55         __doc__         documentation string
  56         __name__        name with which this method was defined
  57         im_class        class object in which this method belongs
  58         im_func         function object containing implementation of method
  59         im_self         instance to which this method is bound, or None"""
  60     return isinstance(object, types.MethodType)
  61
  62 def ismethoddescriptor(object):
  63     """Return true if the object is a method descriptor.
  64
  65     But not if ismethod() or isclass() or isfunction() are true.
  66
  67     This is new in Python 2.2, and, for example, is true of int.__add__.
  68     An object passing this test has a __get__ attribute but not a __set__
  69     attribute, but beyond that the set of attributes varies.  __name__ is
  70     usually sensible, and __doc__ often is.
  71
  72     Methods implemented via descriptors that also pass one of the other
  73     tests return false from the ismethoddescriptor() test, simply because
  74     the other tests promise more -- you can, e.g., count on having the
  75     im_func attribute (etc) when an object passes ismethod()."""
  76     return (hasattr(object, "__get__")
  77             and not hasattr(object, "__set__") # else it's a data descriptor
  78             and not ismethod(object)           # mutual exclusion
  79             and not isfunction(object)
  80             and not isclass(object))
  81
  82 def isdatadescriptor(object):
  83     """Return true if the object is a data descriptor.
  84
  85     Data descriptors have both a __get__ and a __set__ attribute.  Examples are
  86     properties (defined in Python) and getsets and members (defined in C).
  87     Typically, data descriptors will also have __name__ and __doc__ attributes
  88     (properties, getsets, and members have both of these attributes), but this
  89     is not guaranteed."""
  90     return (hasattr(object, "__set__") and hasattr(object, "__get__"))
  91
  92 if hasattr(types, 'MemberDescriptorType'):
  93     # CPython and equivalent
  94     def ismemberdescriptor(object):
  95         """Return true if the object is a member descriptor.
  96
  97         Member descriptors are specialized descriptors defined in extension
  98         modules."""
  99         return isinstance(object, types.MemberDescriptorType)
 100 else:
 101     # Other implementations
 102     def ismemberdescriptor(object):
 103         """Return true if the object is a member descriptor.
 104
 105         Member descriptors are specialized descriptors defined in extension
 106         modules."""
 107         return False
 108
 109 if hasattr(types, 'GetSetDescriptorType'):
 110     # CPython and equivalent
 111     def isgetsetdescriptor(object):
 112         """Return true if the object is a getset descriptor.
 113
 114         getset descriptors are specialized descriptors defined in extension
 115         modules."""
 116         return isinstance(object, types.GetSetDescriptorType)
 117 else:
 118     # Other implementations
 119     def isgetsetdescriptor(object):
 120         """Return true if the object is a getset descriptor.
 121
 122         getset descriptors are specialized descriptors defined in extension
 123         modules."""
 124         return False
 125
 126 def isfunction(object):
 127     """Return true if the object is a user-defined function.
 128
 129     Function objects provide these attributes:
 130         __doc__         documentation string
 131         __name__        name with which this function was defined
 132         func_code       code object containing compiled function bytecode
 133         func_defaults   tuple of any default values for arguments
 134         func_doc        (same as __doc__)
 135         func_globals    global namespace in which this function was defined
 136         func_name       (same as __name__)"""
 137     return isinstance(object, types.FunctionType)
 138
 139 def istraceback(object):
 140     """Return true if the object is a traceback.
 141
 142     Traceback objects provide these attributes:
 143         tb_frame        frame object at this level
 144         tb_lasti        index of last attempted instruction in bytecode
 145         tb_lineno       current line number in Python source code
 146         tb_next         next inner traceback object (called by this level)"""
 147     return isinstance(object, types.TracebackType)
 148
 149 def isframe(object):
 150     """Return true if the object is a frame object.
 151
 152     Frame objects provide these attributes:
 153         f_back          next outer frame object (this frame's caller)
 154         f_builtins      built-in namespace seen by this frame
 155         f_code          code object being executed in this frame
 156         f_exc_traceback traceback if raised in this frame, or None
 157         f_exc_type      exception type if raised in this frame, or None
 158         f_exc_value     exception value if raised in this frame, or None
 159         f_globals       global namespace seen by this frame
 160         f_lasti         index of last attempted instruction in bytecode
 161         f_lineno        current line number in Python source code
 162         f_locals        local namespace seen by this frame
 163         f_restricted    0 or 1 if frame is in restricted execution mode
 164         f_trace         tracing function for this frame, or None"""
 165     return isinstance(object, types.FrameType)
 166
 167 def iscode(object):
 168     """Return true if the object is a code object.
 169
 170     Code objects provide these attributes:
 171         co_argcount     number of arguments (not including * or ** args)
 172         co_code         string of raw compiled bytecode
 173         co_consts       tuple of constants used in the bytecode
 174         co_filename     name of file in which this code object was created
 175         co_firstlineno  number of first line in Python source code
 176         co_flags        bitmap: 1=optimized | 2=newlocals | 4=*arg | 8=**arg
 177         co_lnotab       encoded mapping of line numbers to bytecode indices
 178         co_name         name with which this code object was defined
 179         co_names        tuple of names of local variables
 180         co_nlocals      number of local variables
 181         co_stacksize    virtual machine stack space required
 182         co_varnames     tuple of names of arguments and local variables"""
 183     return isinstance(object, types.CodeType)
 184
 185 def isbuiltin(object):
 186     """Return true if the object is a built-in function or method.
 187
 188     Built-in functions and methods provide these attributes:
 189         __doc__         documentation string
 190         __name__        original name of this function or method
 191         __self__        instance to which a method is bound, or None"""
 192     return isinstance(object, types.BuiltinFunctionType)
 193
 194 def isroutine(object):
 195     """Return true if the object is any kind of function or method."""
 196     return (isbuiltin(object)
 197             or isfunction(object)
 198             or ismethod(object)
 199             or ismethoddescriptor(object))
 200
 201 def getmembers(object, predicate=None):
 202     """Return all members of an object as (name, value) pairs sorted by name.
 203     Optionally, only return members that satisfy a given predicate."""
 204     results = []
 205     for key in dir(object):
 206         value = getattr(object, key)
 207         if not predicate or predicate(value):
 208             results.append((key, value))
 209     results.sort()
 210     return results
 211
 212 def classify_class_attrs(cls):
 213     """Return list of attribute-descriptor tuples.
 214
 215     For each name in dir(cls), the return list contains a 4-tuple
 216     with these elements:
 217
 218         0. The name (a string).
 219
 220         1. The kind of attribute this is, one of these strings:
 221                'class method'    created via classmethod()
 222                'static method'   created via staticmethod()
 223                'property'        created via property()
 224                'method'          any other flavor of method
 225                'data'            not a method
 226
 227         2. The class which defined this attribute (a class).
 228
 229         3. The object as obtained directly from the defining class's
 230            __dict__, not via getattr.  This is especially important for
 231            data attributes:  C.data is just a data object, but
 232            C.__dict__['data'] may be a data descriptor with additional
 233            info, like a __doc__ string.
 234     """
 235
 236     mro = getmro(cls)
 237     names = dir(cls)
 238     result = []
 239     for name in names:
 240         # Get the object associated with the name.
 241         # Getting an obj from the __dict__ sometimes reveals more than
 242         # using getattr.  Static and class methods are dramatic examples.
 243         if name in cls.__dict__:
 244             obj = cls.__dict__[name]
 245         else:
 246             obj = getattr(cls, name)
 247
 248         # Figure out where it was defined.
 249         homecls = getattr(obj, "__objclass__", None)
 250         if homecls is None:
 251             # search the dicts.
 252             for base in mro:
 253                 if name in base.__dict__:
 254                     homecls = base
 255                     break
 256
 257         # Get the object again, in order to get it from the defining
 258         # __dict__ instead of via getattr (if possible).
 259         if homecls is not None and name in homecls.__dict__:
 260             obj = homecls.__dict__[name]
 261
 262         # Also get the object via getattr.
 263         obj_via_getattr = getattr(cls, name)
 264
 265         # Classify the object.
 266         if isinstance(obj, staticmethod):
 267             kind = "static method"
 268         elif isinstance(obj, classmethod):
 269             kind = "class method"
 270         elif isinstance(obj, property):
 271             kind = "property"
 272         elif (ismethod(obj_via_getattr) or
 273               ismethoddescriptor(obj_via_getattr)):
 274             kind = "method"
 275         else:
 276             kind = "data"
 277
 278         result.append((name, kind, homecls, obj))
 279
 280     return result
 281
 282 # ----------------------------------------------------------- class helpers
 283 def _searchbases(cls, accum):
 284     # Simulate the "classic class" search order.
 285     if cls in accum:
 286         return
 287     accum.append(cls)
 288     for base in cls.__bases__:
 289         _searchbases(base, accum)
 290
 291 def getmro(cls):
 292     "Return tuple of base classes (including cls) in method resolution order."
 293     if hasattr(cls, "__mro__"):
 294         return cls.__mro__
 295     else:
 296         result = []
 297         _searchbases(cls, result)
 298         return tuple(result)
 299
 300 # -------------------------------------------------- source code extraction
 301 def indentsize(line):
 302     """Return the indent size, in spaces, at the start of a line of text."""
 303     expline = string.expandtabs(line)
 304     return len(expline) - len(string.lstrip(expline))
 305
 306 def getdoc(object):
 307     """Get the documentation string for an object.
 308
 309     All tabs are expanded to spaces.  To clean up docstrings that are
 310     indented to line up with blocks of code, any whitespace than can be
 311     uniformly removed from the second line onwards is removed."""
 312     try:
 313         doc = object.__doc__
 314     except AttributeError:
 315         return None
 316     if not isinstance(doc, types.StringTypes):
 317         return None
 318     try:
 319         lines = string.split(string.expandtabs(doc), '\n')
 320     except UnicodeError:
 321         return None
 322     else:
 323         # Find minimum indentation of any non-blank lines after first line.
 324         margin = sys.maxint
 325         for line in lines[1:]:
 326             content = len(string.lstrip(line))
 327             if content:
 328                 indent = len(line) - content
 329                 margin = min(margin, indent)
 330         # Remove indentation.
 331         if lines:
 332             lines[0] = lines[0].lstrip()
 333         if margin < sys.maxint:
 334             for i in range(1, len(lines)): lines[i] = lines[i][margin:]
 335         # Remove any trailing or leading blank lines.
 336         while lines and not lines[-1]:
 337             lines.pop()
 338         while lines and not lines[0]:
 339             lines.pop(0)
 340         return string.join(lines, '\n')
 341
 342 def getfile(object):
 343     """Work out which source or compiled file an object was defined in."""
 344     if ismodule(object):
 345         if hasattr(object, '__file__'):
 346             return object.__file__
 347         raise TypeError('arg is a built-in module')
 348     if isclass(object):
 349         object = sys.modules.get(object.__module__)
 350         if hasattr(object, '__file__'):
 351             return object.__file__
 352         raise TypeError('arg is a built-in class')
 353     if ismethod(object):
 354         object = object.im_func
 355     if isfunction(object):
 356         object = object.func_code
 357     if istraceback(object):
 358         object = object.tb_frame
 359     if isframe(object):
 360         object = object.f_code
 361     if iscode(object):
 362         return object.co_filename
 363     raise TypeError('arg is not a module, class, method, '
 364                     'function, traceback, frame, or code object')
 365
 366 def getmoduleinfo(path):
 367     """Get the module name, suffix, mode, and module type for a given file."""
 368     filename = os.path.basename(path)
 369     suffixes = map(lambda (suffix, mode, mtype):
 370                    (-len(suffix), suffix, mode, mtype), imp.get_suffixes())
 371     suffixes.sort() # try longest suffixes first, in case they overlap
 372     for neglen, suffix, mode, mtype in suffixes:
 373         if filename[neglen:] == suffix:
 374             return filename[:neglen], suffix, mode, mtype
 375
 376 def getmodulename(path):
 377     """Return the module name for a given file, or None."""
 378     info = getmoduleinfo(path)
 379     if info: return info[0]
 380
 381 def getsourcefile(object):
 382     """Return the Python source file an object was defined in, if it exists."""
 383     filename = getfile(object)
 384     if string.lower(filename[-4:]) in ('.pyc', '.pyo'):
 385         filename = filename[:-4] + '.py'
 386     for suffix, mode, kind in imp.get_suffixes():
 387         if 'b' in mode and string.lower(filename[-len(suffix):]) == suffix:
 388             # Looks like a binary file.  We want to only return a text file.
 389             return None
 390     if os.path.exists(filename):
 391         return filename
 392     # only return a non-existent filename if the module has a PEP 302 loader
 393     if hasattr(getmodule(object, filename), '__loader__'):
 394         return filename
 395
 396 def getabsfile(object, _filename=None):
 397     """Return an absolute path to the source or compiled file for an object.
 398
 399     The idea is for each object to have a unique origin, so this routine
 400     normalizes the result as much as possible."""
 401     if _filename is None:
 402         _filename = getsourcefile(object) or getfile(object)
 403     return os.path.normcase(os.path.abspath(_filename))
 404
 405 modulesbyfile = {}
 406 _filesbymodname = {}
 407
 408 def getmodule(object, _filename=None):
 409     """Return the module an object was defined in, or None if not found."""
 410     if ismodule(object):
 411         return object
 412     if hasattr(object, '__module__'):
 413         return sys.modules.get(object.__module__)
 414     # Try the filename to modulename cache
 415     if _filename is not None and _filename in modulesbyfile:
 416         return sys.modules.get(modulesbyfile[_filename])
 417     # Try the cache again with the absolute file name
 418     try:
 419         file = getabsfile(object, _filename)
 420     except TypeError:
 421         return None
 422     if file in modulesbyfile:
 423         return sys.modules.get(modulesbyfile[file])
 424     # Update the filename to module name cache and check yet again
 425     # Copy sys.modules in order to cope with changes while iterating
 426     for modname, module in sys.modules.items():
 427         if ismodule(module) and hasattr(module, '__file__'):
 428             f = module.__file__
 429             if f == _filesbymodname.get(modname, None):
 430                 # Have already mapped this module, so skip it
 431                 continue
 432             _filesbymodname[modname] = f
 433             f = getabsfile(module)
 434             # Always map to the name the module knows itself by
 435             modulesbyfile[f] = modulesbyfile[
 436                 os.path.realpath(f)] = module.__name__
 437     if file in modulesbyfile:
 438         return sys.modules.get(modulesbyfile[file])
 439     # Check the main module
 440     main = sys.modules['__main__']
 441     if not hasattr(object, '__name__'):
 442         return None
 443     if hasattr(main, object.__name__):
 444         mainobject = getattr(main, object.__name__)
 445         if mainobject is object:
 446             return main
 447     # Check builtins
 448     builtin = sys.modules['__builtin__']
 449     if hasattr(builtin, object.__name__):
 450         builtinobject = getattr(builtin, object.__name__)
 451         if builtinobject is object:
 452             return builtin
 453
 454 def findsource(object):
 455     """Return the entire source file and starting line number for an object.
 456
 457     The argument may be a module, class, method, function, traceback, frame,
 458     or code object.  The source code is returned as a list of all the lines
 459     in the file and the line number indexes a line in that list.  An IOError
 460     is raised if the source code cannot be retrieved."""
 461     file = getsourcefile(object) or getfile(object)
 462     module = getmodule(object, file)
 463     if module:
 464         lines = linecache.getlines(file, module.__dict__)
 465     else:
 466         lines = linecache.getlines(file)
 467     if not lines:
 468         raise IOError('could not get source code')
 469
 470     if ismodule(object):
 471         return lines, 0
 472
 473     if isclass(object):
 474         name = object.__name__
 475         pat = re.compile(r'^(\s*)class\s*' + name + r'\b')
 476         # make some effort to find the best matching class definition:
 477         # use the one with the least indentation, which is the one
 478         # that's most probably not inside a function definition.
 479         candidates = []
 480         for i in range(len(lines)):
 481             match = pat.match(lines[i])
 482             if match:
 483                 # if it's at toplevel, it's already the best one
 484                 if lines[i][0] == 'c':
 485                     return lines, i
 486                 # else add whitespace to candidate list
 487                 candidates.append((match.group(1), i))
 488         if candidates:
 489             # this will sort by whitespace, and by line number,
 490             # less whitespace first
 491             candidates.sort()
 492             return lines, candidates[0][1]
 493         else:
 494             raise IOError('could not find class definition')
 495
 496     if ismethod(object):
 497         object = object.im_func
 498     if isfunction(object):
 499         object = object.func_code
 500     if istraceback(object):
 501         object = object.tb_frame
 502     if isframe(object):
 503         object = object.f_code
 504     if iscode(object):
 505         if not hasattr(object, 'co_firstlineno'):
 506             raise IOError('could not find function definition')
 507         lnum = object.co_firstlineno - 1
 508         pat = re.compile(r'^(\s*def\s)|(.*(?<!\w)lambda(:|\s))|^(\s*@)')
 509         while lnum > 0:
 510             if pat.match(lines[lnum]): break
 511             lnum = lnum - 1
 512         return lines, lnum
 513     raise IOError('could not find code object')
 514
 515 def getcomments(object):
 516     """Get lines of comments immediately preceding an object's source code.
 517
 518     Returns None when source can't be found.
 519     """
 520     try:
 521         lines, lnum = findsource(object)
 522     except (IOError, TypeError):
 523         return None
 524
 525     if ismodule(object):
 526         # Look for a comment block at the top of the file.
 527         start = 0
 528         if lines and lines[0][:2] == '#!': start = 1
 529         while start < len(lines) and string.strip(lines[start]) in ('', '#'):
 530             start = start + 1
 531         if start < len(lines) and lines[start][:1] == '#':
 532             comments = []
 533             end = start
 534             while end < len(lines) and lines[end][:1] == '#':
 535                 comments.append(string.expandtabs(lines[end]))
 536                 end = end + 1
 537             return string.join(comments, '')
 538
 539     # Look for a preceding block of comments at the same indentation.
 540     elif lnum > 0:
 541         indent = indentsize(lines[lnum])
 542         end = lnum - 1
 543         if end >= 0 and string.lstrip(lines[end])[:1] == '#' and \
 544             indentsize(lines[end]) == indent:
 545             comments = [string.lstrip(string.expandtabs(lines[end]))]
 546             if end > 0:
 547                 end = end - 1
 548                 comment = string.lstrip(string.expandtabs(lines[end]))
 549                 while comment[:1] == '#' and indentsize(lines[end]) == indent:
 550                     comments[:0] = [comment]
 551                     end = end - 1
 552                     if end < 0: break
 553                     comment = string.lstrip(string.expandtabs(lines[end]))
 554             while comments and string.strip(comments[0]) == '#':
 555                 comments[:1] = []
 556             while comments and string.strip(comments[-1]) == '#':
 557                 comments[-1:] = []
 558             return string.join(comments, '')
 559
 560 class EndOfBlock(Exception): pass
 561
 562 class BlockFinder:
 563     """Provide a tokeneater() method to detect the end of a code block."""
 564     def __init__(self):
 565         self.indent = 0
 566         self.islambda = False
 567         self.started = False
 568         self.passline = False
 569         self.last = 1
 570
 571     def tokeneater(self, type, token, (srow, scol), (erow, ecol), line):
 572         if not self.started:
 573             # look for the first "def", "class" or "lambda"
 574             if token in ("def", "class", "lambda"):
 575                 if token == "lambda":
 576                     self.islambda = True
 577                 self.started = True
 578             self.passline = True    # skip to the end of the line
 579         elif type == tokenize.NEWLINE:
 580             self.passline = False   # stop skipping when a NEWLINE is seen
 581             self.last = srow
 582             if self.islambda:       # lambdas always end at the first NEWLINE
 583                 raise EndOfBlock
 584         elif self.passline:
 585             pass
 586         elif type == tokenize.INDENT:
 587             self.indent = self.indent + 1
 588             self.passline = True
 589         elif type == tokenize.DEDENT:
 590             self.indent = self.indent - 1
 591             # the end of matching indent/dedent pairs end a block
 592             # (note that this only works for "def"/"class" blocks,
 593             #  not e.g. for "if: else:" or "try: finally:" blocks)
 594             if self.indent <= 0:
 595                 raise EndOfBlock
 596         elif self.indent == 0 and type not in (tokenize.COMMENT, tokenize.NL):
 597             # any other token on the same indentation level end the previous
 598             # block as well, except the pseudo-tokens COMMENT and NL.
 599             raise EndOfBlock
 600
 601 def getblock(lines):
 602     """Extract the block of code at the top of the given list of lines."""
 603     blockfinder = BlockFinder()
 604     try:
 605         tokenize.tokenize(iter(lines).next, blockfinder.tokeneater)
 606     except (EndOfBlock, IndentationError):
 607         pass
 608     return lines[:blockfinder.last]
 609
 610 def getsourcelines(object):
 611     """Return a list of source lines and starting line number for an object.
 612
 613     The argument may be a module, class, method, function, traceback, frame,
 614     or code object.  The source code is returned as a list of the lines
 615     corresponding to the object and the line number indicates where in the
 616     original source file the first line of code was found.  An IOError is
 617     raised if the source code cannot be retrieved."""
 618     lines, lnum = findsource(object)
 619
 620     if ismodule(object): return lines, 0
 621     else: return getblock(lines[lnum:]), lnum + 1
 622
 623 def getsource(object):
 624     """Return the text of the source code for an object.
 625
 626     The argument may be a module, class, method, function, traceback, frame,
 627     or code object.  The source code is returned as a single string.  An
 628     IOError is raised if the source code cannot be retrieved."""
 629     lines, lnum = getsourcelines(object)
 630     return string.join(lines, '')
 631
 632 # --------------------------------------------------- class tree extraction
 633 def walktree(classes, children, parent):
 634     """Recursive helper function for getclasstree()."""
 635     results = []
 636     classes.sort(key=attrgetter('__module__', '__name__'))
 637     for c in classes:
 638         results.append((c, c.__bases__))
 639         if c in children:
 640             results.append(walktree(children[c], children, c))
 641     return results
 642
 643 def getclasstree(classes, unique=0):
 644     """Arrange the given list of classes into a hierarchy of nested lists.
 645
 646     Where a nested list appears, it contains classes derived from the class
 647     whose entry immediately precedes the list.  Each entry is a 2-tuple
 648     containing a class and a tuple of its base classes.  If the 'unique'
 649     argument is true, exactly one entry appears in the returned structure
 650     for each class in the given list.  Otherwise, classes using multiple
 651     inheritance and their descendants will appear multiple times."""
 652     children = {}
 653     roots = []
 654     for c in classes:
 655         if c.__bases__:
 656             for parent in c.__bases__:
 657                 if not parent in children:
 658                     children[parent] = []
 659                 children[parent].append(c)
 660                 if unique and parent in classes: break
 661         elif c not in roots:
 662             roots.append(c)
 663     for parent in children:
 664         if parent not in classes:
 665             roots.append(parent)
 666     return walktree(roots, children, None)
 667
 668 # ------------------------------------------------ argument list extraction
 669 # These constants are from Python's compile.h.
 670 CO_OPTIMIZED, CO_NEWLOCALS, CO_VARARGS, CO_VARKEYWORDS = 1, 2, 4, 8
 671
 672 def getargs(co):
 673     """Get information about the arguments accepted by a code object.
 674
 675     Three things are returned: (args, varargs, varkw), where 'args' is
 676     a list of argument names (possibly containing nested lists), and
 677     'varargs' and 'varkw' are the names of the * and ** arguments or None."""
 678
 679     if not iscode(co):
 680         raise TypeError('arg is not a code object')
 681
 682     code = co.co_code
 683     nargs = co.co_argcount
 684     names = co.co_varnames
 685     args = list(names[:nargs])
 686     step = 0
 687
 688     # The following acrobatics are for anonymous (tuple) arguments.
 689     for i in range(nargs):
 690         if args[i][:1] in ('', '.'):
 691             stack, remain, count = [], [], []
 692             while step < len(code):
 693                 op = ord(code[step])
 694                 step = step + 1
 695                 if op >= dis.HAVE_ARGUMENT:
 696                     opname = dis.opname[op]
 697                     value = ord(code[step]) + ord(code[step+1])*256
 698                     step = step + 2
 699                     if opname in ('UNPACK_TUPLE', 'UNPACK_SEQUENCE'):
 700                         remain.append(value)
 701                         count.append(value)
 702                     elif opname == 'STORE_FAST':
 703                         stack.append(names[value])
 704
 705                         # Special case for sublists of length 1: def foo((bar))
 706                         # doesn't generate the UNPACK_TUPLE bytecode, so if
 707                         # `remain` is empty here, we have such a sublist.
 708                         if not remain:
 709                             stack[0] = [stack[0]]
 710                             break
 711                         else:
 712                             remain[-1] = remain[-1] - 1
 713                             while remain[-1] == 0:
 714                                 remain.pop()
 715                                 size = count.pop()
 716                                 stack[-size:] = [stack[-size:]]
 717                                 if not remain: break
 718                                 remain[-1] = remain[-1] - 1
 719                             if not remain: break
 720             args[i] = stack[0]
 721
 722     varargs = None
 723     if co.co_flags & CO_VARARGS:
 724         varargs = co.co_varnames[nargs]
 725         nargs = nargs + 1
 726     varkw = None
 727     if co.co_flags & CO_VARKEYWORDS:
 728         varkw = co.co_varnames[nargs]
 729     return args, varargs, varkw
 730
 731 def getargspec(func):
 732     """Get the names and default values of a function's arguments.
 733
 734     A tuple of four things is returned: (args, varargs, varkw, defaults).
 735     'args' is a list of the argument names (it may contain nested lists).
 736     'varargs' and 'varkw' are the names of the * and ** arguments or None.
 737     'defaults' is an n-tuple of the default values of the last n arguments.
 738     """
 739
 740     if ismethod(func):
 741         func = func.im_func
 742     if not isfunction(func):
 743         raise TypeError('arg is not a Python function')
 744     args, varargs, varkw = getargs(func.func_code)
 745     return args, varargs, varkw, func.func_defaults
 746
 747 def getargvalues(frame):
 748     """Get information about arguments passed into a particular frame.
 749
 750     A tuple of four things is returned: (args, varargs, varkw, locals).
 751     'args' is a list of the argument names (it may contain nested lists).
 752     'varargs' and 'varkw' are the names of the * and ** arguments or None.
 753     'locals' is the locals dictionary of the given frame."""
 754     args, varargs, varkw = getargs(frame.f_code)
 755     return args, varargs, varkw, frame.f_locals
 756
 757 def joinseq(seq):
 758     if len(seq) == 1:
 759         return '(' + seq[0] + ',)'
 760     else:
 761         return '(' + string.join(seq, ', ') + ')'
 762
 763 def strseq(object, convert, join=joinseq):
 764     """Recursively walk a sequence, stringifying each element."""
 765     if type(object) in (list, tuple):
 766         return join(map(lambda o, c=convert, j=join: strseq(o, c, j), object))
 767     else:
 768         return convert(object)
 769
 770 def formatargspec(args, varargs=None, varkw=None, defaults=None,
 771                   formatarg=str,
 772                   formatvarargs=lambda name: '*' + name,
 773                   formatvarkw=lambda name: '**' + name,
 774                   formatvalue=lambda value: '=' + repr(value),
 775                   join=joinseq):
 776     """Format an argument spec from the 4 values returned by getargspec.
 777
 778     The first four arguments are (args, varargs, varkw, defaults).  The
 779     other four arguments are the corresponding optional formatting functions
 780     that are called to turn names and values into strings.  The ninth
 781     argument is an optional function to format the sequence of arguments."""
 782     specs = []
 783     if defaults:
 784         firstdefault = len(args) - len(defaults)
 785     for i in range(len(args)):
 786         spec = strseq(args[i], formatarg, join)
 787         if defaults and i >= firstdefault:
 788             spec = spec + formatvalue(defaults[i - firstdefault])
 789         specs.append(spec)
 790     if varargs is not None:
 791         specs.append(formatvarargs(varargs))
 792     if varkw is not None:
 793         specs.append(formatvarkw(varkw))
 794     return '(' + string.join(specs, ', ') + ')'
 795
 796 def formatargvalues(args, varargs, varkw, locals,
 797                     formatarg=str,
 798                     formatvarargs=lambda name: '*' + name,
 799                     formatvarkw=lambda name: '**' + name,
 800                     formatvalue=lambda value: '=' + repr(value),
 801                     join=joinseq):
 802     """Format an argument spec from the 4 values returned by getargvalues.
 803
 804     The first four arguments are (args, varargs, varkw, locals).  The
 805     next four arguments are the corresponding optional formatting functions
 806     that are called to turn names and values into strings.  The ninth
 807     argument is an optional function to format the sequence of arguments."""
 808     def convert(name, locals=locals,
 809                 formatarg=formatarg, formatvalue=formatvalue):
 810         return formatarg(name) + formatvalue(locals[name])
 811     specs = []
 812     for i in range(len(args)):
 813         specs.append(strseq(args[i], convert, join))
 814     if varargs:
 815         specs.append(formatvarargs(varargs) + formatvalue(locals[varargs]))
 816     if varkw:
 817         specs.append(formatvarkw(varkw) + formatvalue(locals[varkw]))
 818     return '(' + string.join(specs, ', ') + ')'
 819
 820 # -------------------------------------------------- stack frame extraction
 821 def getframeinfo(frame, context=1):
 822     """Get information about a frame or traceback object.
 823
 824     A tuple of five things is returned: the filename, the line number of
 825     the current line, the function name, a list of lines of context from
 826     the source code, and the index of the current line within that list.
 827     The optional second argument specifies the number of lines of context
 828     to return, which are centered around the current line."""
 829     if istraceback(frame):
 830         lineno = frame.tb_lineno
 831         frame = frame.tb_frame
 832     else:
 833         lineno = frame.f_lineno
 834     if not isframe(frame):
 835         raise TypeError('arg is not a frame or traceback object')
 836
 837     filename = getsourcefile(frame) or getfile(frame)
 838     if context > 0:
 839         start = lineno - 1 - context//2
 840         try:
 841             lines, lnum = findsource(frame)
 842         except IOError:
 843             lines = index = None
 844         else:
 845             start = max(start, 1)
 846             start = max(0, min(start, len(lines) - context))
 847             lines = lines[start:start+context]
 848             index = lineno - 1 - start
 849     else:
 850         lines = index = None
 851
 852     return (filename, lineno, frame.f_code.co_name, lines, index)
 853
 854 def getlineno(frame):
 855     """Get the line number from a frame object, allowing for optimization."""
 856     # FrameType.f_lineno is now a descriptor that grovels co_lnotab
 857     return frame.f_lineno
 858
 859 def getouterframes(frame, context=1):
 860     """Get a list of records for a frame and all higher (calling) frames.
 861
 862     Each record contains a frame object, filename, line number, function
 863     name, a list of lines of context, and index within the context."""
 864     framelist = []
 865     while frame:
 866         framelist.append((frame,) + getframeinfo(frame, context))
 867         frame = frame.f_back
 868     return framelist
 869
 870 def getinnerframes(tb, context=1):
 871     """Get a list of records for a traceback's frame and all lower frames.
 872
 873     Each record contains a frame object, filename, line number, function
 874     name, a list of lines of context, and index within the context."""
 875     framelist = []
 876     while tb:
 877         framelist.append((tb.tb_frame,) + getframeinfo(tb, context))
 878         tb = tb.tb_next
 879     return framelist
 880
 881 currentframe = sys._getframe
 882
 883 def stack(context=1):
 884     """Return a list of records for the stack above the caller's frame."""
 885     return getouterframes(sys._getframe(1), context)
 886
 887 def trace(context=1):
 888     """Return a list of records for the stack below the current exception."""
 889     return getinnerframes(sys.exc_info()[2], context)