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