1 # Module Cyclops version 0.9.4.
2 # Released to the public domain 18-Jul-1999,
3 # by Tim Peters (tim_one@email.msn.com).
5 # Provided as-is; use at your own risk; no warranty; no promises; enjoy!
7 # Some parts of the code, and many ideas, were stolen with gratitude from:
8 # Lars Marius Garshol's Plumbo.py.
10 # Python's standard library module repr.py.
12 """Module Cyclops -- stare at cycles in Python data structures.
14 Cyclops started life as a faster implementation of Lars Marius
15 Garshol's Plumbo.py, but almost instantly diverged due to feature
18 The only object of real interest is class CycleFinder. First get an
22 z = Cyclops.CycleFinder()
24 This creates a cycle-tracker with an empty "root set". Then tell z
25 which objects you're curious about (more on that later).
27 After running your regular code, tell z to look for cycles:
29 z.find_cycles(purge_dead_roots=0)
30 Look for cycles reachable from the root set.
31 Return 1 if a cycle was found, else 0.
32 If optional arg purge_dead_roots is true, first remove objects
33 from the root set whose true refcount (exclusive of CycleFinder
34 internal references) is 0.
35 See also method install_cycle_filter.
37 Then various methods can be used to get useful reports. Which are
38 *most* useful you'll just have to play with. If you have a few small
39 cycles, show_cycles is very revealing; if you have many cycles,
40 show_sccs and show_arcs *may* cut to the heart of the problem quickly.
43 Print some stats about the last run of find_cycles: number of
44 distinct structured objects reachable from the root set, number of
45 distinct objects involved in a cycle, number of cycles found,
46 number of strongly connected components, number of objects in the
47 root set, and number of edges (graph arcs) examined.
50 Print each cycle found to stdout.
52 z.show_cycleobjs(compare=typename_address_cmp)
53 Print a listing of all objects involved in some cycle. The
54 objects are first sorted via the optional "compare" function. By
55 default, sorts first by type name and then by address (id); among
56 objects of instance type, sorts by the instances' class names;
57 among objects of class type, sorts by the classes' names.
59 x.show_sccs(compare=typename_address_cmp)
60 Print a listing of cycle objects partitioned into strongly
61 connected components (that is, the largest groupings possible such
62 that each object in an SCC is reachable from every other object in
63 that SCC). Within each SCC, objects are sorted as for
66 z.show_arcs(compare=None)
67 Print a listing of all arc types involved in some cycle. An arc
69 1) its source object type or class,
70 2) the selector (e.g. attribute) from the source, and
71 3) its destination object type or class.
72 The output is a table with four columns: count, source, selector,
73 destination. The table is sorted by default on columns 2, 3, 4
74 in that order; the first column (count) is ignored. Specify an
75 alternative compare function to change the sort; the compare
76 function sees pairs of the form
77 ((source_type, selector, destination_type), count)
78 where each element of the triple is a string and count is an int.
81 Print a 2-line description of obj, including its address, adjusted
82 refcount, type name and a short representation of its contents.
83 See the method docstring for details.
85 There are two ways to add objects to the root set:
87 z.run(func, args=(), kwargs={})
88 Run func (with optional args and keyword arguments kwargs), adding
89 every object initialized by an __init__ function to the root set.
90 This is the closest Cyclops gets to plumbo's "lazy" mode. It's
91 factored out here so it can be intermixed with the next method.
94 Add obj to the root set.
96 To see the current root set,
99 Return the root set, as a list of (rc, cyclic?, obj) tuples.
100 See method docstring for details. In short, rc is the true
101 refcount (CycleFinder internal references are subtracted out);
102 cyclic is true iff the object is in a known cycle; and obj is the
105 Finally, to empty the root set again:
108 Empty the root set, and release all other internal references to
113 + Run Cyclops.py directly to exercise its _test() function; _test()
114 sets up some common kinds of cycles, and should be easy to follow.
115 Stare at the _test() code and the output until their relationship is
118 + find_cycles is linear-time, in the number of objects reachable from
119 the root set plus the number of arcs connecting them. This makes
120 Cyclops pleasant for "real life" apps with tens of thousands of
121 reachable objects, and at least usable well beyond that.
123 + A (at least one) reference to each root-set object is maintained
124 internally, so roots cannot die before invoking .clear() (or the
125 CycleFinder is finalized). This can distort the truth of your
126 program, if a __del__ method of some root object that's not involved
127 in a cycle could have caused cycles to get broken (this is unusual,
130 If you suspect it's happening, run find_cycles again passing true
131 (optional arg purge_dead_roots): find_cycles then releases all
132 internal refs to root set objects whose true refcount is 0, thus
133 allowing their __del__ methods to get invoked. After that,
134 find_cycles chases the remaining root set objects again. You may
135 need several iterations of invoking find_cycles(1) before reaching a
138 + By default, cycles are chased through these (& only these) objects:
142 - Dicts (both keys and values).
143 - Class instances (through their attributes).
144 - Classes (through their attributes).
145 - Instance method objects (through .im_self and .im_class).
147 In particular, modules are not chased. Maybe they should be. See
148 the next section for a way to force modules to get chased.
151 CHANGING THE SET OF INTERESTING TYPES
153 Methods of a CycleFinder object can be used to alter/query its view of
154 the set of types find_cycles "chases":
156 z.chase_type(t, t_refs_func, t_tag_func)
157 Add type t to the set of interesting types.
158 t_refs_func is a function of one argument x, where type(x) is t;
159 it should return a sequence (typically a list or tuple) of all
160 objects directly reachable from x.
161 t_tag_func is a function of two arguments x and i, where type(x)
162 is t and i in range(len(t_refs_func(x))). It should return a
163 brief string describing how t_refs_func(x][i] was obtained from
165 See the _XXX_refs and _XXX_tag functions at the start of the
166 module for examples of all this.
169 Remove type t from the set of interesting types. find_cycles
170 will not attempt to chase the objects reachable from objects of
174 Return the set of interesting types, as a list.
177 CHANGING THE SET OF INTERESTING CYCLES
179 Sometimes there are "expected" cycles you would like to ignore; e.g.,
180 this can happen if you install a module-chaser, because there are
181 cycles in Python's implementation you typically don't care about (for
182 example, if your module imports sys, there's a cycle because
183 sys.modules points back to your module!).
185 z.install_cycle_filter(filter_func=None)
186 filter_func=None -> a way to ignore "expected" cycles.
188 filter_func is a function of one argument, a cycle. Each time
189 find_cycles finds a cycle, the cycle is passed to filter_func. The
190 cycle is ignored unless filter_func returns true. Passing None
191 for filter_func restores the default behavior (do not ignore any
194 A cycle is a list of (object, index) pairs, where the first object
195 in the list is the same as the last object in the list, and where
196 the object at cycle[i][0] is the cycle[i][1]'th object obtained
197 from object cycle[i-1][0]. cycle[0][1] should be ignored (it tells
198 us how we got to the first item in the cycle to begin with, but
199 that's irrelevant to the cycle).
204 Below is the driver I used to track cycles in IDLE; it's a replacement
207 At first it didn't install function or module chasers, or a cycle filter,
208 and printed everything. This turned up a bunch of easy cases, and the
209 show_sccs output was surprisingly revealing (all the cycles fell into a
210 handful of SCCs, which corresponded to distinct cycle-creating IDLE
211 subsystems). show_arcs was also very helpful in getting the big picture.
212 show_cycles output was too voluminous to be helpful.
214 After those cycles were broken, the job got harder. A module chaser was
215 added, which turned up another class of cycles, and then a function
216 chaser turned up 100s more. Most of these involved expected cycles due
217 to Python's implementation, so a cycle filter was installed to ignore
218 cycles that didn't contain at least one class instance. The remaining
219 cycles were isolated special cases, and only show_cycles output was
222 After all cycles were purged, IDLE was still leaking, so driver output was
223 added to display the root-set objects still alive at the end. This turned
224 up many cases where objects were living only because registration in the
225 root set was keeping them alive. So a loop was added to the driver that
226 repeatedly purges dead root-set objects and tries again. The __del__
227 methods of the purged roots caused other root objects to become trash,
228 and after several iterations of this the output reaches a steady state.
230 IDLE is still leaking (as of 18-Jul-1999), but ever less so, and while
231 Cyclops is no longer finding cycles, the driver's "live at the end"
232 output is still the best clue I've got for guessing what to do next.
234 Interesting: At the start of this, it turned out that almost all cycles
235 were reachable from places outside themselves. That is, they would not
236 have been considered trash even if Python used a mark-&-sweep form of
237 garbage collection. IDLE's problems, in large part inherited from Tkinter,
238 are simply that "everything points to everything else". The good news is
239 that Guido was able to clean most of this up just by adding reference-
240 purging code to widgets' explicitly-called destroy() methods.
242 #! /usr/bin/env python
248 return x.__dict__.values()
251 return "." + x.__dict__.keys()[i]
254 return x.func_globals, x.func_defaults
257 return (".func_globals", ".func_defaults")[i]
259 def instance_filter(cycle):
260 for obj, index in cycle:
261 if type(obj) is types.InstanceType:
265 # Note: PyShell binds ModifiedInterpreter.locals to __main__.__dict__,
266 # and __main__ is *us*. So if we don't keep the CycleFinder instance
267 # out of the global namespace here, z starts chewing over its own
268 # instance attributes. Nothing breaks, but the output is at best
272 z = Cyclops.CycleFinder()
273 z.chase_type(types.ModuleType, mod_refs, mod_tag)
274 z.chase_type(types.FunctionType, func_refs, func_tag)
275 z.install_cycle_filter(instance_filter)
285 print "non-cyclic root set objects:"
287 numsurvivors = numdead = 0
288 for rc, cyclic, x in z.get_rootset():
289 if not sawitalready.has_key(id(x)):
290 sawitalready[id(x)] = 1
293 numdead = numdead + 1
296 numsurvivors = numsurvivors + 1
299 print numdead, "dead;", numsurvivors, "non-cycle & alive"
302 print "releasing dead root-set objects and trying again"
310 # added purge_dead_roots arg to find_cycles
311 # rearranged module docstring; added IDLE driver sample
313 # renamed print_obj to show_obj, and advertised it
314 # redid adjusted refcount computations to account for root-set
316 # changed get_rootset to return (refcount, cyclic?, obj) triples
318 # freed __init_tracer from dependence on name "self"
319 # rearranged __find_cycles' inner loop for a nice little speed gain
320 # which was promptly way more than lost by new code to compute &
321 # display adjusted refcounts
322 # which was partly regained by rewriting all that
324 # added SCC computation/display
325 # added show_cycles; find_cycles no longer prints anything
326 # changed all showXXX names to show_XXX
327 # added install_cycle_filter
329 # first version I put under source control
331 __version__ = 0, 9, 4
333 #########################################################################
334 # Type-specific reference revealers.
336 # _T_refs(obj) should return a sequence of all objects directly
337 # reachable from obj.
339 # _T_tag(obj, i) should return a string briefly describing how
340 # _T_refs(obj][i] was obtained from obj.
342 # Why the separation? Speed and space: string tags are never
343 # computed unless a cycle is found and so something needs to be
347 return x.keys() + x.values()
351 return ".keys()[%d]" % i
353 return "[%s]" % _quickrepr(x.keys()[i-n])
360 _tuple_refs = _list_refs
361 _tuple_tag = _list_tag
363 def _instance_refs(x):
364 # the keys are strings, so not interesting to return
365 return x.__dict__.values()
366 def _instance_tag(x, i):
367 return "." + x.__dict__.keys()[i]
369 _class_refs = _instance_refs
370 _class_tag = _instance_tag
372 def _instance_method_refs(x):
373 return (x.im_self, x.im_class)
374 def _instance_method_tag(x, i):
375 return (".im_self", ".im_class")[i]
378 _default_refs_dispatcher = {
379 types.DictType: _dict_refs,
380 types.ListType: _list_refs,
381 types.TupleType: _tuple_refs,
382 types.InstanceType: _instance_refs,
383 types.ClassType: _class_refs,
384 types.MethodType: _instance_method_refs,
386 _default_tag_dispatcher = {
387 types.DictType: _dict_tag,
388 types.ListType: _list_tag,
389 types.TupleType: _tuple_tag,
390 types.InstanceType: _instance_tag,
391 types.ClassType: _class_tag,
392 types.MethodType: _instance_method_tag,
394 _InstanceType = types.InstanceType
395 _ClassType = types.ClassType
398 del _dict_refs, _list_refs, _tuple_refs, _instance_refs, \
399 _class_refs, _instance_method_refs
400 del _dict_tag, _list_tag, _tuple_tag, _instance_tag, \
401 _class_tag, _instance_method_tag
403 #########################################################################
404 # A class to make short string representations of objects, for speed
405 # and brevity. The std repr.repr sorts dicts by keys, but we refer to
406 # the keys via numeric subscript in cycle reports, so first a derived
407 # class that leaves dicts in raw order. Also, instances, instance
408 # methods and classes frequently appear in cycle reports, so avoid
409 # chopping their reprs at all. We're only trying to prevent massive
410 # expense for massive lists, tuples & dicts.
416 class _CyclopsRepr(_repr.Repr):
419 _repr.Repr.__init__(self)
420 # Boost the limit on types we don't know about; else it's too
421 # easy to get a useless repr string when adding new types via
422 # CycleFinder.chase_type.
423 # Perhaps better to expose this class too, but-- sheesh --
424 # this module is complicated enough!
425 self.maxstring = self.maxother = 40
427 # override base dictionary formatter; the code is almost the same,
428 # we just leave the dict order alone
430 def repr_dictionary(self, x, level):
437 for k, v in x.items()[:min(n, self.maxdict)]:
440 s = s + self.repr1(k, level-1)
441 s = s + ': ' + self.repr1(v, level-1)
446 # don't chop instance, class or instance method reprs
448 def repr_instance(self, x, level):
451 # Bugs in x.__repr__() can cause arbitrary
452 # exceptions -- then make up something
454 return '<' + x.__class__.__name__ + ' instance at ' + \
457 def repr_class(self, x, level):
460 repr_instance_method = repr_class
462 _quickrepr = _CyclopsRepr().repr
464 #########################################################################
465 # CycleFinder is the workhorse.
467 def typename_address_cmp(x, y):
468 if isinstance(x, _InstanceType) and isinstance(y, _InstanceType):
469 xname, yname = x.__class__.__name__, y.__class__.__name__
470 elif isinstance(x, _ClassType) and isinstance(y, _ClassType):
471 xname, yname = x.__name__, y.__name__
473 xname, yname = type(x).__name__, type(y).__name__
474 return cmp((xname, id(x)), (yname, id(y)))
477 """Class for finding cycles in Python data structures.
479 See Cyclops module docstring for details.
483 """Create a cycle finder with empty root set."""
486 self.refs_dispatcher = _default_refs_dispatcher.copy()
487 self.tag_dispatcher = _default_tag_dispatcher.copy()
488 self.cycle_filter = None
491 """Remove all internal references to external objects.
493 Empties the root set.
494 Does not change the set of types this CycleFinder chases.
495 Does not change the cycle filter in effect.
501 def register(self, obj):
502 """obj -> add object obj to the root set."""
504 self.roots.append(obj)
506 def run(self, func, args=(), kwargs={}):
507 """func, args=(), kwargs={} -> add objects to root set by magic.
509 Function func is invoked with arguments args and keyword
510 arguments kwargs. For the duration of the call, each class
511 instance initialized by an __init__ call is automatically
512 added to the root set. The result of invoking func is
515 # This clever method of trapping __init__ invocations was
516 # stolen from Lars' plumbo.py.
518 sys.setprofile(self.__init_tracer)
520 return apply(func, args, kwargs)
524 def find_cycles(self, purge_dead_roots=0):
525 """purge_dead_roots=0 -> look for cycles, return true if found.
527 Identify all cycles among objects reachable from the root set.
528 Return true iff at least one cycle is found.
530 This should be called before any of the show_XXX methods.
531 Note that it's OK to add more objects to the root set and
532 call it again, or to change the set of chased types, etc.
533 find_cycles starts over from scratch each time it's called.
535 If optional arg purge_dead_roots is true (default false),
536 before searching for cycles the root set is purged of all
537 objects that the preceding run of find_cycles determined had a
538 true refcount of 0 (that is, the root set objects that are
539 still alive only because they appear in the root set).
540 Purging these allows their finalizers to get invoked, which
541 may allow a cascade of other objects (including cycles) to go
544 See also method install_cycle_filter.
547 if purge_dead_roots and self.roots:
548 id2rc = self.id2rc.get
551 if id2rc(id(x), None) != 0:
553 self.roots = survivors
554 del x, survivors, id2rc
557 self.__find_cycles(self.roots, 0)
558 del self.seenids[id(self.roots)] # not a user-visible object
560 # Compute true refcounts for objects in cycles.
562 from sys import getrefcount
563 for x in self.cycleobjs.values():
564 # From the system refcount, subtract one for each of:
565 # being an element in the loop temp cycleobjs.values()
567 # being an argument to getrefcount
568 # being a value in the cycleobjs dict
569 # showing up exactly once somewhere in self.sccno2objs
571 id2rc[xid] = getrefcount(x) - 5
573 # Need also to subtract refs due to appearances in
574 # self.cycles. Complication: some pairs in self.cycles may
577 isknown = seenpairs.has_key
578 for cycle in self.cycles:
581 if not isknown(pairid):
582 seenpairs[pairid] = 1
584 id2rc[xid] = id2rc[xid] - 1
585 del isknown, seenpairs
587 # And need also to subtract refs for membership is self.roots.
588 # While we're at it, also compute adjusted refcounts for other
592 if id2rc.has_key(xid):
593 id2rc[xid] = id2rc[xid] - 1
595 assert not self.cycleobjs.has_key(xid)
596 # Subtract one for each of:
598 # being an argument to getrefcount
599 # being in self.roots
600 id2rc[xid] = getrefcount(x) - 3
602 return len(self.cycles) > 0
604 def install_cycle_filter(self, filter_func=None):
605 """filter_func=None -> a way to ignore "expected" cycles.
607 See module docstring for details. This is a callback function
608 invoked whenever find_cycles() finds a cycle; the cycle is
609 ignored unless the callback returns true.
612 self.cycle_filter = filter_func
614 def show_stats(self):
615 """Print statistics for the last run of find_cycles."""
617 self._print_separator()
618 print "# objects in root set:", len(self.roots)
619 print "# distinct structured objects reachable:", len(self.seenids)
620 print "# distinct structured objects in cycles:", len(self.cycleobjs)
621 print "# cycles found:", len(self.cycles)
622 print "# cycles filtered out:", self.ncyclesignored
623 print "# strongly-connected components:", len(self.sccno2objs)
624 print "# arcs examined:", self.narcs
626 def show_cycles(self):
627 """Print all cycles to stdout."""
629 self._print_separator()
630 print "# all cycles:"
633 self._print_cycle(self.cycles[i])
637 def show_cycleobjs(self, compare=typename_address_cmp):
638 """compare=typename_address_cmp -> print all objects in cycles.
640 Prints to stdout. Each distinct object find_cycles found in a
641 cycle is displayed. The set of objects found in cycles is
642 first sorted by the optional "compare" function. By default,
643 objects are sorted using their type name as the primary key
644 and their storage address (id) as the secondary key; among
645 objects of instance type, sorts by the instances' class names;
646 among objects of class type, sorts by the classes' names.
649 self._print_separator()
650 print "# objects involved in cycles:"
651 objs = self.cycleobjs.values()
656 def show_sccs(self, compare=typename_address_cmp):
657 """compare=typename_address_cmp -> print SCCs.
659 Prints to stdout. Shows the objects in cycles partitioned into
660 strongly connected components (that is, the largest groupings
661 possible such that each object in an SCC is reachable from every
662 other object in that SCC). Within each SCC, objects are sorted
663 as for show_cycleobjs.
666 self._print_separator()
667 print "# cycle objects partitioned into maximal SCCs:"
668 sccs = self.sccno2objs.values()
671 print "--- SCC", i+1, "of", n
677 def show_arcs(self, compare=None):
678 """compare=None -> print unique arc types in cycles.
680 See module docstring for details. Briefly, each arc in a
681 cycle is categorized by the type of the source node, the kind
682 of arc (how we got from the source to the destination), and
683 the type of the destination node. Each line of output
684 consists of those three pieces of info preceded by the count
685 of arcs of that kind. By default, the rows are sorted first
686 by column 2 (source node type), then by columns 3 and 4.
689 self._print_separator()
690 print "# arc types involved in cycles:"
691 items = self.arctypes.items()
696 for triple, count in items:
697 print "%6d %-20s %-20s -> %-20s" % ((count,) + triple)
699 def get_rootset(self):
700 """Return the root set, as a list of (rc, cyclic?, obj) tuples.
702 Should be called after find_cycles. For each object in the
703 root set, returns a triple consisting of
705 number of outstanding references less those due to
706 CycleFinder internals; see show_obj docstring for more
707 details; this will be None if find_cycles hasn't been
708 run, or not since the last clear()
710 true (1) iff obj is known to be in a cycle
716 getrc = self.id2rc.get
717 incycle = self.cycleobjs.has_key
720 result.append((getrc(xid, None), incycle(xid), x))
723 def chase_type(self, t, t_refs_func, t_tag_func):
724 """t, t_refs_func, t_tag_func -> chase type t.
726 See module docstring for details.
729 self.refs_dispatcher[t] = t_refs_func
730 self.tag_dispatcher[t] = t_tag_func
732 def dont_chase_type(self, t):
733 """t -> remove type t from the set of chased types.
735 See module docstring for details.
739 del self.refs_dispatcher[t], \
740 self.tag_dispatcher[t]
744 def get_chased_types(self):
745 """Return the set of chased types, as a list."""
747 return self.refs_dispatcher.keys()
749 def __init_tracer(self, frame, event, args):
750 if event == "call" and frame.f_code.co_name == "__init__":
751 # We want to capture the first argument -- this works whether
752 # or not it's named "self", and in case the function is like
753 # def __init__(*args):
754 # it's still OK: we'll pick up the name 'args', and add the
755 # tuple it's bound to to the root set; the tuple's first
756 # element is "self", so will be found by the tuple-chaser.
757 locals = frame.f_code.co_varnames
759 # first argname is first element of locals
760 self.register(frame.f_locals[locals[0]])
763 # Clear out everything except:
765 # the refs_dispatcher
769 # stack exactly mirrors __find_cycles' recursive calls; it's a
770 # list of (object, index) pairs.
773 # Map id of active object to its index in self.stack. Since
774 # it's a depth-first search, there's a cycle iff we hit an
775 # object that's already on the stack.
778 # Set of (addresses of) all interesting objects seen. Since
779 # we use a depth-first search, there's never a reason to
783 # List of all cycles found; each element is a stack slice (a
784 # list of (object, index) pairs).
787 # Set of objects found in cycles (maps id(obj) -> obj).
790 # Classifies arcs found in cycles, mapping
791 # (source_type, selector, destination_type) triples to a count
792 # of how many times that triple appears in a cycle.
795 # Support for computing strongly-connected components (SCC).
796 # We do this by merging cycles into equivalence classes.
797 # Could be done faster by e.g. Tarjan's algorithm in
798 # __find_cycles, but would rather keep that lean since cycles
799 # are expected to be unusual.
800 self.nextsccno = 1 # monotonically increasing SCC id
801 self.id2sccno = {} # map id(obj) to obj's sccno
802 self.sccno2objs = {} # map sccno back to list of objects
804 # For objects in cycles and root set, map address to true
808 # Number of arcs examined.
811 # Number of cycles ignored (filtered out).
812 self.ncyclesignored = 0
814 def __find_cycles(self, obj, i, id=id, type=type, len=len):
815 # This can be called an enormous number of times, so speed
816 # tricks are appropriate.
820 # Set of ids of objects being, or formerly, chased.
821 seenids = self.seenids
822 already_seen = seenids.has_key
824 # Maps active object id to index in stack.
825 id2stacki = self.id2stacki
826 currently_on_stack = id2stacki.has_key
828 refs_dispatcher = self.refs_dispatcher
829 is_interesting_type = refs_dispatcher.has_key
833 id2stacki[myid] = len(stack)
834 stack.append((obj, i))
835 refs = refs_dispatcher[type(obj)](obj)
836 self.narcs = self.narcs + len(refs)
837 for i in xrange(len(refs)):
839 if is_interesting_type(type(child)):
841 if not already_seen(childid):
842 self.__find_cycles(child, i)
843 elif currently_on_stack(childid):
844 cycle = stack[id2stacki[childid]:]
845 cycle.append((child, i)) # complete the cycle
846 self.__study_cycle(cycle)
848 del stack[-1], id2stacki[myid]
850 # a helper for __study_cycle
851 def __obj2arcname(self, obj):
852 if isinstance(obj, _InstanceType):
853 name = obj.__class__.__name__ + "()"
854 elif isinstance(obj, _ClassType):
857 name = type(obj).__name__
860 def __study_cycle(self, slice):
861 assert len(slice) >= 2
863 if self.cycle_filter is not None and \
864 not self.cycle_filter(slice):
865 self.ncyclesignored = self.ncyclesignored + 1
868 self.cycles.append(slice)
870 # Pick (or create) an SCC equivalence class for this cycle.
871 sccnowinner = self.id2sccno.get(id(slice[0][0]), None)
872 if sccnowinner is None:
873 sccnowinner = self.nextsccno
874 self.nextsccno = self.nextsccno + 1
875 self.sccno2objs[sccnowinner] = []
876 classwinner = self.sccno2objs[sccnowinner]
878 for i in xrange(len(slice)-1):
880 key1 = self.__obj2arcname(obj1)
882 obj2, index = slice[i+1]
883 key2 = self.tag_dispatcher[type(obj1)](obj1, index)
885 key3 = self.__obj2arcname(obj2)
887 key = (key1, key2, key3)
888 self.arctypes[key] = self.arctypes.get(key, 0) + 1
890 self.cycleobjs[id(obj1)] = obj1
892 # Merge the equivalence class for obj1 into classwinner.
893 thissccno = self.id2sccno.get(id(obj1), None)
894 if thissccno is None:
895 self.id2sccno[id(obj1)] = sccnowinner
896 classwinner.append(obj1)
897 elif thissccno != sccnowinner:
898 # merge obj1's entire equivalence class
899 tomerge = self.sccno2objs[thissccno]
901 self.id2sccno[id(obj2)] = sccnowinner
902 classwinner.extend(tomerge)
903 del self.sccno2objs[thissccno]
905 ################################################################
906 # Various output routines. If someone is motivated enough to
907 # change one of these, they're motivated enough to subclass us!
909 def show_obj(self, obj):
910 """obj -> print short description of obj to sdtout.
914 <address> rc:<refcount> <typename>
921 If find_cycles() has been run and obj is in the root set
922 or was found in a cycle, this is the number of references
923 outstanding less the number held internally by
924 CycleFinder. In most cases, this is what the true
925 refcount would be had you not used CycleFinder at all.
926 You can screw that up, e.g. by installing a cycle filter
927 that holds on to references to one or more cycle elements.
928 If find_cycles() has not been run, or has but obj wasn't
929 found in a cycle and isn't in the root set, <refcount> is
932 type(obj), as a string. If obj.__class__ exists, also
933 prints the class name.
935 repr(obj), but using a variant of the std module repr.py
936 that limits the number of characters displayed.
940 rc = self.id2rc.get(objid, "?")
941 print hex(objid), "rc:" + str(rc), type(obj).__name__,
942 if hasattr(obj, "__class__"):
945 print " repr:", _quickrepr(obj)
947 def _print_separator(self):
950 def _print_cycle(self, slice):
953 print "%d-element cycle" % (n-1)
958 index = slice[i+1][1]
960 self.tag_dispatcher[type(obj)](obj, index), \
965 def __init__(me, name):
968 return "X(" + `self.name` + ")"
970 a, b, c, d = X('a'), X('b'), X('c'), X('d')
975 d.k = {'harrumph': (1, 2, d, 3)}
979 a.__repr__ = a.__repr__
990 del a, b, c, d, e, X, Y, lonely
997 print "dead root set objects:"
998 for rc, cyclic, x in z.get_rootset():
1004 if __name__ == "__main__":