eficas 2.0.3-1-1 / usr / share / pyshared / Misc / Cyclops.py

# -*- coding: utf-8 -*-
# Module Cyclops version 0.9.4.
# Released to the public domain 18-Jul-1999,
# by Tim Peters (tim_one@email.msn.com).

# Provided as-is; use at your own risk; no warranty; no promises; enjoy!

# Some parts of the code, and many ideas, were stolen with gratitude from:
#     Lars Marius Garshol's Plumbo.py.
#     Guido van Rossum.
#     Python's standard library module repr.py.

"""Module Cyclops -- stare at cycles in Python data structures.

Cyclops started life as a faster implementation of Lars Marius
Garshol's Plumbo.py, but almost instantly diverged due to feature
bloat.

The only object of real interest is class CycleFinder.  First get an
instance of that:

import Cyclops
z = Cyclops.CycleFinder()

This creates a cycle-tracker with an empty "root set".  Then tell z
which objects you're curious about (more on that later).

After running your regular code, tell z to look for cycles:

z.find_cycles(purge_dead_roots=0)
    Look for cycles reachable from the root set.
    Return 1 if a cycle was found, else 0.
    If optional arg purge_dead_roots is true, first remove objects
    from the root set whose true refcount (exclusive of CycleFinder
    internal references) is 0.
    See also method install_cycle_filter.

Then various methods can be used to get useful reports.  Which are
*most* useful you'll just have to play with.  If you have a few small
cycles, show_cycles is very revealing; if you have many cycles,
show_sccs and show_arcs *may* cut to the heart of the problem quickly.

z.show_stats()
    Print some stats about the last run of find_cycles:  number of
    distinct structured objects reachable from the root set, number of
    distinct objects involved in a cycle, number of cycles found,
    number of strongly connected components, number of objects in the
    root set, and number of edges (graph arcs) examined.

z.show_cycles()
    Print each cycle found to stdout.

z.show_cycleobjs(compare=typename_address_cmp)
    Print a listing of all objects involved in some cycle.  The
    objects are first sorted via the optional "compare" function.  By
    default, sorts first by type name and then by address (id); among
    objects of instance type, sorts by the instances' class names;
    among objects of class type, sorts by the classes' names.

x.show_sccs(compare=typename_address_cmp)
    Print a listing of cycle objects partitioned into strongly
    connected components (that is, the largest groupings possible such
    that each object in an SCC is reachable from every other object in
    that SCC).  Within each SCC, objects are sorted as for
    show_cycleobjs.

z.show_arcs(compare=None)
    Print a listing of all arc types involved in some cycle.  An arc
    is characterized by:
    1) its source object type or class,
    2) the selector (e.g. attribute) from the source, and
    3) its destination object type or class.
    The output is a table with four columns:  count, source, selector,
    destination.  The table is sorted by default on columns 2, 3, 4
    in that order; the first column (count) is ignored.  Specify an
    alternative compare function to change the sort; the compare
    function sees pairs of the form
        ((source_type, selector, destination_type), count)
    where each element of the triple is a string and count is an int.

z.show_obj(obj)
    Print a 2-line description of obj, including its address, adjusted
    refcount, type name and a short representation of its contents.
    See the method docstring for details.

There are two ways to add objects to the root set:

z.run(func, args=(), kwargs={})
    Run func (with optional args and keyword arguments kwargs), adding
    every object initialized by an __init__ function to the root set.
    This is the closest Cyclops gets to plumbo's "lazy" mode.  It's
    factored out here so it can be intermixed with the next method.

z.register(obj)
    Add obj to the root set.

To see the current root set,

z.get_rootset()
    Return the root set, as a list of (rc, cyclic?, obj) tuples.
    See method docstring for details.  In short, rc is the true
    refcount (CycleFinder internal references are subtracted out);
    cyclic is true iff the object is in a known cycle; and obj is the
    object.

Finally, to empty the root set again:

z.clear()
    Empty the root set, and release all other internal references to
    register'ed objects.

Notes:

+ Run Cyclops.py directly to exercise its _test() function; _test()
  sets up some common kinds of cycles, and should be easy to follow.
  Stare at the _test() code and the output until their relationship is
  clear.

+ find_cycles is linear-time, in the number of objects reachable from
  the root set plus the number of arcs connecting them.  This makes
  Cyclops pleasant for "real life" apps with tens of thousands of
  reachable objects, and at least usable well beyond that.

+ A (at least one) reference to each root-set object is maintained
  internally, so roots cannot die before invoking .clear() (or the
  CycleFinder is finalized).  This can distort the truth of your
  program, if a __del__ method of some root object that's not involved
  in a cycle could have caused cycles to get broken (this is unusual,
  but possible!).

  If you suspect it's happening, run find_cycles again passing true
  (optional arg purge_dead_roots):  find_cycles then releases all
  internal refs to root set objects whose true refcount is 0, thus
  allowing their __del__ methods to get invoked.  After that,
  find_cycles chases the remaining root set objects again.  You may
  need several iterations of invoking find_cycles(1) before reaching a
  steady state!

+ By default, cycles are chased through these (& only these) objects:

  - Lists.
  - Tuples.
  - Dicts (both keys and values).
  - Class instances (through their attributes).
  - Classes (through their attributes).
  - Instance method objects (through .im_self and .im_class).

  In particular, modules are not chased.  Maybe they should be.  See
  the next section for a way to force modules to get chased.


CHANGING THE SET OF INTERESTING TYPES

Methods of a CycleFinder object can be used to alter/query its view of
the set of types find_cycles "chases":

z.chase_type(t, t_refs_func, t_tag_func)
    Add type t to the set of interesting types.
    t_refs_func is a function of one argument x, where type(x) is t;
    it should return a sequence (typically a list or tuple) of all
    objects directly reachable from x.
    t_tag_func is a function of two arguments x and i, where type(x)
    is t and i in range(len(t_refs_func(x))).  It should return a
    brief string describing how t_refs_func(x][i] was obtained from
    x.
    See the _XXX_refs and _XXX_tag functions at the start of the
    module for examples of all this.

z.dont_chase_type(t)
    Remove type t from the set of interesting types.  find_cycles
    will not attempt to chase the objects reachable from objects of
    type t.

z.get_chased_types()
    Return the set of interesting types, as a list.


CHANGING THE SET OF INTERESTING CYCLES

Sometimes there are "expected" cycles you would like to ignore; e.g.,
this can happen if you install a module-chaser, because there are
cycles in Python's implementation you typically don't care about (for
example, if your module imports sys, there's a cycle because
sys.modules points back to your module!).

z.install_cycle_filter(filter_func=None)
    filter_func=None -> a way to ignore "expected" cycles.

    filter_func is a function of one argument, a cycle.  Each time
    find_cycles finds a cycle, the cycle is passed to filter_func.  The
    cycle is ignored unless filter_func returns true.  Passing None
    for filter_func restores the default behavior (do not ignore any
    cycle).

    A cycle is a list of (object, index) pairs, where the first object
    in the list is the same as the last object in the list, and where
    the object at cycle[i][0] is the cycle[i][1]'th object obtained
    from object cycle[i-1][0]. cycle[0][1] should be ignored (it tells
    us how we got to the first item in the cycle to begin with, but
    that's irrelevant to the cycle).


CASE STUDY

Below is the driver I used to track cycles in IDLE; it's a replacement
for IDLE's idle.py.

At first it didn't install function or module chasers, or a cycle filter,
and printed everything.  This turned up a bunch of easy cases, and the
show_sccs output was surprisingly revealing (all the cycles fell into a
handful of SCCs, which corresponded to distinct cycle-creating IDLE
subsystems).  show_arcs was also very helpful in getting the big picture.
show_cycles output was too voluminous to be helpful.

After those cycles were broken, the job got harder.  A module chaser was
added, which turned up another class of cycles, and then a function
chaser turned up 100s more.  Most of these involved expected cycles due
to Python's implementation, so a cycle filter was installed to ignore
cycles that didn't contain at least one class instance.  The remaining
cycles were isolated special cases, and only show_cycles output was
of real use.

After all cycles were purged, IDLE was still leaking, so driver output was
added to display the root-set objects still alive at the end.  This turned
up many cases where objects were living only because registration in the
root set was keeping them alive.  So a loop was added to the driver that
repeatedly purges dead root-set objects and tries again.  The __del__
methods of the purged roots caused other root objects to become trash,
and after several iterations of this the output reaches a steady state.

IDLE is still leaking (as of 18-Jul-1999), but ever less so, and while
Cyclops is no longer finding cycles, the driver's "live at the end"
output is still the best clue I've got for guessing what to do next.

Interesting:  At the start of this, it turned out that almost all cycles
were reachable from places outside themselves.  That is, they would not
have been considered trash even if Python used a mark-&-sweep form of
garbage collection.  IDLE's problems, in large part inherited from Tkinter,
are simply that "everything points to everything else".  The good news is
that Guido was able to clean most of this up just by adding reference-
purging code to widgets' explicitly-called destroy() methods.

#! /usr/bin/env python
import PyShell
import Cyclops
import types

def mod_refs(x):
    return x.__dict__.values()

def mod_tag(x, i):
    return "." + x.__dict__.keys()[i]

def func_refs(x):
    return x.func_globals, x.func_defaults

def func_tag(x, i):
    return (".func_globals", ".func_defaults")[i]

def instance_filter(cycle):
    for obj, index in cycle:
        if type(obj) is types.InstanceType:
            return 1
    return 0

# Note: PyShell binds ModifiedInterpreter.locals  to __main__.__dict__,
# and __main__ is *us*.  So if we don't keep the CycleFinder instance
# out of the global namespace here, z starts chewing over its own
# instance attributes.  Nothing breaks, but the output is at best
# surprising.

def hidez():
    z = Cyclops.CycleFinder()
    z.chase_type(types.ModuleType, mod_refs, mod_tag)
    z.chase_type(types.FunctionType, func_refs, func_tag)
    z.install_cycle_filter(instance_filter)
    z.run(PyShell.main)
    z.find_cycles()
    z.show_stats()
    z.show_cycles()
    # z.show_cycleobjs()
    # z.show_sccs()
    z.show_arcs()
    while 1:
        print "*" * 70
        print "non-cyclic root set objects:"
        sawitalready = {}
        numsurvivors = numdead = 0
        for rc, cyclic, x in z.get_rootset():
            if not sawitalready.has_key(id(x)):
                sawitalready[id(x)] = 1
                if rc == 0:
                    print "DEAD",
                    numdead = numdead + 1
                    z.show_obj(x)
                elif not cyclic:
                    numsurvivors = numsurvivors + 1
                    z.show_obj(x)
        x = None
        print numdead, "dead;", numsurvivors, "non-cycle & alive"
        if numdead == 0:
            break
        print "releasing dead root-set objects and trying again"
        z.find_cycles(1)
        z.show_stats()

hidez()
"""

# 0,9,4    18-Jul-1999
#    added purge_dead_roots arg to find_cycles
#    rearranged module docstring; added IDLE driver sample
# 0,9,3    29-Jun-1999
#    renamed print_obj to show_obj, and advertised it
#    redid adjusted refcount computations to account for root-set
#        objects too
#    changed get_rootset to return (refcount, cyclic?, obj) triples
# 0,9,2    27-Jun-1999
#    freed __init_tracer from dependence on name "self"
#    rearranged __find_cycles' inner loop for a nice little speed gain
#    which was promptly way more than lost by new code to compute &
#        display adjusted refcounts
#    which was partly regained by rewriting all that
# 0,9,1    26-Jun-1999
#    added SCC computation/display
#    added show_cycles; find_cycles no longer prints anything
#    changed all showXXX names to show_XXX
#    added install_cycle_filter
# 0,9,0    24-Jun-1999
#    first version I put under source control

__version__ = 0, 9, 4

#########################################################################
# Type-specific reference revealers.
#
# _T_refs(obj) should return a sequence of all objects directly
# reachable from obj.
#
# _T_tag(obj, i) should return a string briefly describing how
# _T_refs(obj][i] was obtained from obj.
#
# Why the separation?  Speed and space:  string tags are never
# computed unless a cycle is found and so something needs to be
# printed.

def _dict_refs(x):
    return x.keys() + x.values()
def _dict_tag(x, i):
    n = len(x)
    if i < n:
        return ".keys()[%d]" % i
    else:
        return "[%s]" % _quickrepr(x.keys()[i-n])

def _list_refs(x):
    return x
def _list_tag(x, i):
    return "[%d]" % i

_tuple_refs = _list_refs
_tuple_tag = _list_tag

def _instance_refs(x):
    # the keys are strings, so not interesting to return
    return x.__dict__.values()
def _instance_tag(x, i):
    return "." + x.__dict__.keys()[i]

_class_refs = _instance_refs
_class_tag = _instance_tag

def _instance_method_refs(x):
    return (x.im_self, x.im_class)
def _instance_method_tag(x, i):
    return (".im_self", ".im_class")[i]

import types
_default_refs_dispatcher = {
    types.DictType: _dict_refs,
    types.ListType: _list_refs,
    types.TupleType: _tuple_refs,
    types.InstanceType: _instance_refs,
    types.ClassType: _class_refs,
    types.MethodType: _instance_method_refs,
}
_default_tag_dispatcher = {
    types.DictType: _dict_tag,
    types.ListType: _list_tag,
    types.TupleType: _tuple_tag,
    types.InstanceType: _instance_tag,
    types.ClassType: _class_tag,
    types.MethodType: _instance_method_tag,
}
_InstanceType = types.InstanceType
_ClassType = types.ClassType
del types

del _dict_refs, _list_refs, _tuple_refs, _instance_refs, \
    _class_refs, _instance_method_refs
del _dict_tag, _list_tag, _tuple_tag, _instance_tag, \
    _class_tag, _instance_method_tag

#########################################################################
# A class to make short string representations of objects, for speed
# and brevity.  The std repr.repr sorts dicts by keys, but we refer to
# the keys via numeric subscript in cycle reports, so first a derived
# class that leaves dicts in raw order.  Also, instances, instance
# methods and classes frequently appear in cycle reports, so avoid
# chopping their reprs at all.  We're only trying to prevent massive
# expense for massive lists, tuples & dicts.

import repr
_repr = repr
del repr

class _CyclopsRepr(_repr.Repr):

    def __init__(self):
        _repr.Repr.__init__(self)
        # Boost the limit on types we don't know about; else it's too
        # easy to get a useless repr string when adding new types via
        # CycleFinder.chase_type.
        # Perhaps better to expose this class too, but-- sheesh --
        # this module is complicated enough!
        self.maxstring = self.maxother = 40

    # override base dictionary formatter; the code is almost the same,
    # we just leave the dict order alone

    def repr_dictionary(self, x, level):
        n = len(x)
        if n == 0:
            return '{}'
        if level <= 0:
            return '{...}'
        s = ''
        for k, v in x.items()[:min(n, self.maxdict)]:
            if s:
                s = s + ', '
            s = s + self.repr1(k, level-1)
            s = s + ': ' + self.repr1(v, level-1)
        if n > self.maxdict:
            s = s + ', ...'
        return '{' + s + '}'

    # don't chop instance, class or instance method reprs

    def repr_instance(self, x, level):
        try:
            return `x`
            # Bugs in x.__repr__() can cause arbitrary
            # exceptions -- then make up something
        except:
            return '<' + x.__class__.__name__ + ' instance at ' + \
                   hex(id(x))[2:] + '>'

    def repr_class(self, x, level):
        return `x`

    repr_instance_method = repr_class

_quickrepr = _CyclopsRepr().repr

#########################################################################
# CycleFinder is the workhorse.

def typename_address_cmp(x, y):
    if isinstance(x, _InstanceType) and isinstance(y, _InstanceType):
        xname, yname = x.__class__.__name__, y.__class__.__name__
    elif isinstance(x, _ClassType) and isinstance(y, _ClassType):
        xname, yname = x.__name__, y.__name__
    else:
        xname, yname = type(x).__name__, type(y).__name__
    return cmp((xname, id(x)), (yname, id(y)))

class CycleFinder:
    """Class for finding cycles in Python data structures.

    See Cyclops module docstring for details.
    """

    def __init__(self):
        """Create a cycle finder with empty root set."""

        self.clear()
        self.refs_dispatcher = _default_refs_dispatcher.copy()
        self.tag_dispatcher = _default_tag_dispatcher.copy()
        self.cycle_filter = None

    def clear(self):
        """Remove all internal references to external objects.

        Empties the root set.
        Does not change the set of types this CycleFinder chases.
        Does not change the cycle filter in effect.
        """

        self.roots = []
        self.__reset()

    def register(self, obj):
        """obj -> add object obj to the root set."""

        self.roots.append(obj)

    def run(self, func, args=(), kwargs={}):
        """func, args=(), kwargs={} -> add objects to root set by magic.

        Function func is invoked with arguments args and keyword
        arguments kwargs.  For the duration of the call, each class
        instance initialized by an __init__ call is automatically
        added to the root set.  The result of invoking func is
        returned. """

        # This clever method of trapping __init__ invocations was
        # stolen from Lars' plumbo.py.
        import sys
        sys.setprofile(self.__init_tracer)
        try:
            return apply(func, args, kwargs)
        finally:
            sys.setprofile(None)

    def find_cycles(self, purge_dead_roots=0):
        """purge_dead_roots=0 -> look for cycles, return true if found.

        Identify all cycles among objects reachable from the root set.
        Return true iff at least one cycle is found.

        This should be called before any of the show_XXX methods.
        Note that it's OK to add more objects to the root set and
        call it again, or to change the set of chased types, etc.
        find_cycles starts over from scratch each time it's called.

        If optional arg purge_dead_roots is true (default false),
        before searching for cycles the root set is purged of all
        objects that the preceding run of find_cycles determined had a
        true refcount of 0 (that is, the root set objects that are
        still alive only because they appear in the root set).
        Purging these allows their finalizers to get invoked, which
        may allow a cascade of other objects (including cycles) to go
        away too.

        See also method install_cycle_filter.
        """

        if purge_dead_roots and self.roots:
            id2rc = self.id2rc.get
            survivors = []
            for x in self.roots:
                if id2rc(id(x), None) != 0:
                    survivors.append(x)
            self.roots = survivors
            del x, survivors, id2rc

        self.__reset()
        self.__find_cycles(self.roots, 0)
        del self.seenids[id(self.roots)]    # not a user-visible object

        # Compute true refcounts for objects in cycles.
        id2rc = self.id2rc
        from sys import getrefcount
        for x in self.cycleobjs.values():
            # From the system refcount, subtract one for each of:
            #    being an element in the loop temp cycleobjs.values()
            #    being bound to "x"
            #    being an argument to getrefcount
            #    being a value in the cycleobjs dict
            #    showing up exactly once somewhere in self.sccno2objs
            xid = id(x)
            id2rc[xid] = getrefcount(x) - 5

        # Need also to subtract refs due to appearances in
        # self.cycles.  Complication:  some pairs in self.cycles may
        # be shared.
        seenpairs = {}
        isknown = seenpairs.has_key
        for cycle in self.cycles:
            for pair in cycle:
                pairid = id(pair)
                if not isknown(pairid):
                    seenpairs[pairid] = 1
                    xid = id(pair[0])
                    id2rc[xid] = id2rc[xid] - 1
        del isknown, seenpairs

        # And need also to subtract refs for membership is self.roots.
        # While we're at it, also compute adjusted refcounts for other
        # root set objects.
        for x in self.roots:
            xid = id(x)
            if id2rc.has_key(xid):
                id2rc[xid] = id2rc[xid] - 1
            else:
                assert not self.cycleobjs.has_key(xid)
                # Subtract one for each of:
                #     being bound to "x"
                #     being an argument to getrefcount
                #     being in self.roots
                id2rc[xid] = getrefcount(x) - 3

        return len(self.cycles) > 0

    def install_cycle_filter(self, filter_func=None):
        """filter_func=None -> a way to ignore "expected" cycles.

        See module docstring for details.  This is a callback function
        invoked whenever find_cycles() finds a cycle; the cycle is
        ignored unless the callback returns true.
        """

        self.cycle_filter = filter_func

    def show_stats(self):
        """Print statistics for the last run of find_cycles."""

        self._print_separator()
        print "# objects in root set:", len(self.roots)
        print "# distinct structured objects reachable:", len(self.seenids)
        print "# distinct structured objects in cycles:", len(self.cycleobjs)
        print "# cycles found:", len(self.cycles)
        print "# cycles filtered out:", self.ncyclesignored
        print "# strongly-connected components:", len(self.sccno2objs)
        print "# arcs examined:", self.narcs

    def show_cycles(self):
        """Print all cycles to stdout."""

        self._print_separator()
        print "# all cycles:"
        n = len(self.cycles)
        for i in xrange(n):
            self._print_cycle(self.cycles[i])
            if i < n-1:
                print "-" * 20

    def show_cycleobjs(self, compare=typename_address_cmp):
        """compare=typename_address_cmp -> print all objects in cycles.

        Prints to stdout.  Each distinct object find_cycles found in a
        cycle is displayed.  The set of objects found in cycles is
        first sorted by the optional "compare" function.  By default,
        objects are sorted using their type name as the primary key
        and their storage address (id) as the secondary key; among
        objects of instance type, sorts by the instances' class names;
        among objects of class type, sorts by the classes' names.
        """

        self._print_separator()
        print "# objects involved in cycles:"
        objs = self.cycleobjs.values()
        objs.sort(compare)
        for obj in objs:
            self.show_obj(obj)

    def show_sccs(self, compare=typename_address_cmp):
        """compare=typename_address_cmp -> print SCCs.

        Prints to stdout.  Shows the objects in cycles partitioned into
        strongly connected components (that is, the largest groupings
        possible such that each object in an SCC is reachable from every
        other object in that SCC).  Within each SCC, objects are sorted
        as for show_cycleobjs.
        """

        self._print_separator()
        print "# cycle objects partitioned into maximal SCCs:"
        sccs = self.sccno2objs.values()
        n = len(sccs)
        for i in xrange(n):
            print "--- SCC", i+1, "of", n
            objs = sccs[i]
            objs.sort(compare)
            for obj in objs:
                self.show_obj(obj)

    def show_arcs(self, compare=None):
        """compare=None -> print unique arc types in cycles.

        See module docstring for details.  Briefly, each arc in a
        cycle is categorized by the type of the source node, the kind
        of arc (how we got from the source to the destination), and
        the type of the destination node.  Each line of output
        consists of those three pieces of info preceded by the count
        of arcs of that kind.  By default, the rows are sorted first
        by column 2 (source node type), then by columns 3 and 4.
        """

        self._print_separator()
        print "# arc types involved in cycles:"
        items = self.arctypes.items()
        if compare:
            items.sort(compare)
        else:
            items.sort()
        for triple, count in items:
            print "%6d %-20s %-20s -> %-20s" % ((count,) + triple)

    def get_rootset(self):
        """Return the root set, as a list of (rc, cyclic?, obj) tuples.

        Should be called after find_cycles.  For each object in the
        root set, returns a triple consisting of
        refcount
            number of outstanding references less those due to
            CycleFinder internals; see show_obj docstring for more
            details; this will be None if find_cycles hasn't been
            run, or not since the last clear()
        cyclic?
            true (1) iff obj is known to be in a cycle
        obj
            the object
        """

        result = []
        getrc = self.id2rc.get
        incycle = self.cycleobjs.has_key
        for x in self.roots:
            xid = id(x)
            result.append((getrc(xid, None), incycle(xid), x))
        return result

    def chase_type(self, t, t_refs_func, t_tag_func):
        """t, t_refs_func, t_tag_func -> chase type t.

        See module docstring for details.
        """

        self.refs_dispatcher[t] = t_refs_func
        self.tag_dispatcher[t] = t_tag_func

    def dont_chase_type(self, t):
        """t -> remove type t from the set of chased types.

        See module docstring for details.
        """

        try:
            del self.refs_dispatcher[t], \
                self.tag_dispatcher[t]
        except KeyError:
            pass

    def get_chased_types(self):
        """Return the set of chased types, as a list."""

        return self.refs_dispatcher.keys()

    def __init_tracer(self, frame, event, args):
        if event == "call" and frame.f_code.co_name == "__init__":
            # We want to capture the first argument -- this works whether
            # or not it's named "self", and in case the function is like
            #     def __init__(*args):
            # it's still OK:  we'll pick up the name 'args', and add the
            # tuple it's bound to to the root set; the tuple's first
            # element is "self", so will be found by the tuple-chaser.
            locals = frame.f_code.co_varnames
            if locals:
                # first argname is first element of locals
                self.register(frame.f_locals[locals[0]])

    def __reset(self):
        # Clear out everything except:
        #       the root set
        #       the refs_dispatcher
        #       the tag_dispatcher
        #       the cycle filter

        # stack exactly mirrors __find_cycles' recursive calls; it's a
        # list of (object, index) pairs.
        self.stack = []

        # Map id of active object to its index in self.stack.  Since
        # it's a depth-first search, there's a cycle iff we hit an
        # object that's already on the stack.
        self.id2stacki = {}

        # Set of (addresses of) all interesting objects seen.  Since
        # we use a depth-first search, there's never a reason to
        # revisit a node.
        self.seenids = {}

        # List of all cycles found; each element is a stack slice (a
        # list of (object, index) pairs).
        self.cycles = []

        # Set of objects found in cycles (maps id(obj) -> obj).
        self.cycleobjs = {}

        # Classifies arcs found in cycles, mapping
        # (source_type, selector, destination_type) triples to a count
        # of how many times that triple appears in a cycle.
        self.arctypes = {}

        # Support for computing strongly-connected components (SCC).
        # We do this by merging cycles into equivalence classes.
        # Could be done faster by e.g. Tarjan's algorithm in
        # __find_cycles, but would rather keep that lean since cycles
        # are expected to be unusual.
        self.nextsccno = 1      # monotonically increasing SCC id
        self.id2sccno = {}      # map id(obj) to obj's sccno
        self.sccno2objs = {}    # map sccno back to list of objects

        # For objects in cycles and root set, map address to true
        # reference count.
        self.id2rc = {}

        # Number of arcs examined.
        self.narcs = 0

        # Number of cycles ignored (filtered out).
        self.ncyclesignored = 0

    def __find_cycles(self, obj, i, id=id, type=type, len=len):
        # This can be called an enormous number of times, so speed
        # tricks are appropriate.

        stack = self.stack

        # Set of ids of objects being, or formerly, chased.
        seenids = self.seenids
        already_seen = seenids.has_key

        # Maps active object id to index in stack.
        id2stacki = self.id2stacki
        currently_on_stack = id2stacki.has_key

        refs_dispatcher = self.refs_dispatcher
        is_interesting_type = refs_dispatcher.has_key

        myid = id(obj)
        seenids[myid] = 1
        id2stacki[myid] = len(stack)
        stack.append((obj, i))
        refs = refs_dispatcher[type(obj)](obj)
        self.narcs = self.narcs + len(refs)
        for i in xrange(len(refs)):
            child = refs[i]
            if is_interesting_type(type(child)):
                childid = id(child)
                if not already_seen(childid):
                    self.__find_cycles(child, i)
                elif currently_on_stack(childid):
                    cycle = stack[id2stacki[childid]:]
                    cycle.append((child, i)) # complete the cycle
                    self.__study_cycle(cycle)

        del stack[-1], id2stacki[myid]

    # a helper for __study_cycle
    def __obj2arcname(self, obj):
        if isinstance(obj, _InstanceType):
            name = obj.__class__.__name__ + "()"
        elif isinstance(obj, _ClassType):
            name = obj.__name__
        else:
            name = type(obj).__name__
        return name

    def __study_cycle(self, slice):
        assert len(slice) >= 2

        if self.cycle_filter is not None and \
           not self.cycle_filter(slice):
            self.ncyclesignored = self.ncyclesignored + 1
            return

        self.cycles.append(slice)

        # Pick (or create) an SCC equivalence class for this cycle.
        sccnowinner = self.id2sccno.get(id(slice[0][0]), None)
        if sccnowinner is None:
            sccnowinner = self.nextsccno
            self.nextsccno = self.nextsccno + 1
            self.sccno2objs[sccnowinner] = []
        classwinner = self.sccno2objs[sccnowinner]

        for i in xrange(len(slice)-1):
            obj1 = slice[i][0]
            key1 = self.__obj2arcname(obj1)

            obj2, index = slice[i+1]
            key2 = self.tag_dispatcher[type(obj1)](obj1, index)

            key3 = self.__obj2arcname(obj2)

            key = (key1, key2, key3)
            self.arctypes[key] = self.arctypes.get(key, 0) + 1

            self.cycleobjs[id(obj1)] = obj1

            # Merge the equivalence class for obj1 into classwinner.
            thissccno = self.id2sccno.get(id(obj1), None)
            if thissccno is None:
                self.id2sccno[id(obj1)] = sccnowinner
                classwinner.append(obj1)
            elif thissccno != sccnowinner:
                # merge obj1's entire equivalence class
                tomerge = self.sccno2objs[thissccno]
                for obj2 in tomerge:
                    self.id2sccno[id(obj2)] = sccnowinner
                classwinner.extend(tomerge)
                del self.sccno2objs[thissccno]

    ################################################################
    # Various output routines.  If someone is motivated enough to
    # change one of these, they're motivated enough to subclass us!

    def show_obj(self, obj):
        """obj -> print short description of obj to sdtout.

        This is of the form

        <address> rc:<refcount> <typename>
            repr: <shortrepr>

        where
        <address>
            hex address of obj
        <refcount>
            If find_cycles() has been run and obj is in the root set
            or was found in a cycle, this is the number of references
            outstanding less the number held internally by
            CycleFinder.  In most cases, this is what the true
            refcount would be had you not used CycleFinder at all.
            You can screw that up, e.g. by installing a cycle filter
            that holds on to references to one or more cycle elements.
            If find_cycles() has not been run, or has but obj wasn't
            found in a cycle and isn't in the root set, <refcount> is
            "?".
        <typename>
            type(obj), as a string.  If obj.__class__ exists, also
            prints the class name.
        <shortrepr>
            repr(obj), but using a variant of the std module repr.py
            that limits the number of characters displayed.
        """

        objid = id(obj)
        rc = self.id2rc.get(objid, "?")
        print hex(objid), "rc:" + str(rc), type(obj).__name__,
        if hasattr(obj, "__class__"):
            print obj.__class__,
        print
        print "    repr:", _quickrepr(obj)

    def _print_separator(self):
        print "*" * 70

    def _print_cycle(self, slice):
        n = len(slice)
        assert n >= 2
        print "%d-element cycle" % (n-1)
        for i in xrange(n):
            obj = slice[i][0]
            self.show_obj(obj)
            if i < n-1:
                index = slice[i+1][1]
                print "    this" + \
                      self.tag_dispatcher[type(obj)](obj, index), \
                      "->"

def _test():
    class X:
        def __init__(me, name):
            me.name = name
        def __repr__(self):
            return "X(" + `self.name` + ")"

    a, b, c, d = X('a'), X('b'), X('c'), X('d')
    a.k = b
    b.k = c
    c.k = a
    a.y = b.y = c.y = d
    d.k = {'harrumph': (1, 2, d, 3)}
    e = X('e')
    e.selfref = e
    a.gotoe = e
    a.__repr__ = a.__repr__

    class Y: pass
    X.gotoy = Y
    Y.gotox = X

    lonely = X('lonely')

    z = CycleFinder()
    z.register(a)
    z.register(lonely)
    del a, b, c, d, e, X, Y, lonely
    z.find_cycles()
    z.show_stats()
    z.show_cycles()
    z.show_cycleobjs()
    z.show_sccs()
    z.show_arcs()
    print "dead root set objects:"
    for rc, cyclic, x in z.get_rootset():
        if rc == 0:
            z.show_obj(x)
    z.find_cycles(1)
    z.show_stats()

if __name__ == "__main__":
    _test()