1 # -*- coding: utf-8 -*-
2 # Module Cyclops version 0.9.4.
3 # Released to the public domain 18-Jul-1999,
4 # by Tim Peters (tim_one@email.msn.com).
6 # Provided as-is; use at your own risk; no warranty; no promises; enjoy!
8 # Some parts of the code, and many ideas, were stolen with gratitude from:
9 # Lars Marius Garshol's Plumbo.py.
11 # Python's standard library module repr.py.
13 """Module Cyclops -- stare at cycles in Python data structures.
15 Cyclops started life as a faster implementation of Lars Marius
16 Garshol's Plumbo.py, but almost instantly diverged due to feature
19 The only object of real interest is class CycleFinder. First get an
23 z = Cyclops.CycleFinder()
25 This creates a cycle-tracker with an empty "root set". Then tell z
26 which objects you're curious about (more on that later).
28 After running your regular code, tell z to look for cycles:
30 z.find_cycles(purge_dead_roots=0)
31 Look for cycles reachable from the root set.
32 Return 1 if a cycle was found, else 0.
33 If optional arg purge_dead_roots is true, first remove objects
34 from the root set whose true refcount (exclusive of CycleFinder
35 internal references) is 0.
36 See also method install_cycle_filter.
38 Then various methods can be used to get useful reports. Which are
39 *most* useful you'll just have to play with. If you have a few small
40 cycles, show_cycles is very revealing; if you have many cycles,
41 show_sccs and show_arcs *may* cut to the heart of the problem quickly.
44 Print some stats about the last run of find_cycles: number of
45 distinct structured objects reachable from the root set, number of
46 distinct objects involved in a cycle, number of cycles found,
47 number of strongly connected components, number of objects in the
48 root set, and number of edges (graph arcs) examined.
51 Print each cycle found to stdout.
53 z.show_cycleobjs(compare=typename_address_cmp)
54 Print a listing of all objects involved in some cycle. The
55 objects are first sorted via the optional "compare" function. By
56 default, sorts first by type name and then by address (id); among
57 objects of instance type, sorts by the instances' class names;
58 among objects of class type, sorts by the classes' names.
60 x.show_sccs(compare=typename_address_cmp)
61 Print a listing of cycle objects partitioned into strongly
62 connected components (that is, the largest groupings possible such
63 that each object in an SCC is reachable from every other object in
64 that SCC). Within each SCC, objects are sorted as for
67 z.show_arcs(compare=None)
68 Print a listing of all arc types involved in some cycle. An arc
70 1) its source object type or class,
71 2) the selector (e.g. attribute) from the source, and
72 3) its destination object type or class.
73 The output is a table with four columns: count, source, selector,
74 destination. The table is sorted by default on columns 2, 3, 4
75 in that order; the first column (count) is ignored. Specify an
76 alternative compare function to change the sort; the compare
77 function sees pairs of the form
78 ((source_type, selector, destination_type), count)
79 where each element of the triple is a string and count is an int.
82 Print a 2-line description of obj, including its address, adjusted
83 refcount, type name and a short representation of its contents.
84 See the method docstring for details.
86 There are two ways to add objects to the root set:
88 z.run(func, args=(), kwargs={})
89 Run func (with optional args and keyword arguments kwargs), adding
90 every object initialized by an __init__ function to the root set.
91 This is the closest Cyclops gets to plumbo's "lazy" mode. It's
92 factored out here so it can be intermixed with the next method.
95 Add obj to the root set.
97 To see the current root set,
100 Return the root set, as a list of (rc, cyclic?, obj) tuples.
101 See method docstring for details. In short, rc is the true
102 refcount (CycleFinder internal references are subtracted out);
103 cyclic is true iff the object is in a known cycle; and obj is the
106 Finally, to empty the root set again:
109 Empty the root set, and release all other internal references to
114 + Run Cyclops.py directly to exercise its _test() function; _test()
115 sets up some common kinds of cycles, and should be easy to follow.
116 Stare at the _test() code and the output until their relationship is
119 + find_cycles is linear-time, in the number of objects reachable from
120 the root set plus the number of arcs connecting them. This makes
121 Cyclops pleasant for "real life" apps with tens of thousands of
122 reachable objects, and at least usable well beyond that.
124 + A (at least one) reference to each root-set object is maintained
125 internally, so roots cannot die before invoking .clear() (or the
126 CycleFinder is finalized). This can distort the truth of your
127 program, if a __del__ method of some root object that's not involved
128 in a cycle could have caused cycles to get broken (this is unusual,
131 If you suspect it's happening, run find_cycles again passing true
132 (optional arg purge_dead_roots): find_cycles then releases all
133 internal refs to root set objects whose true refcount is 0, thus
134 allowing their __del__ methods to get invoked. After that,
135 find_cycles chases the remaining root set objects again. You may
136 need several iterations of invoking find_cycles(1) before reaching a
139 + By default, cycles are chased through these (& only these) objects:
143 - Dicts (both keys and values).
144 - Class instances (through their attributes).
145 - Classes (through their attributes).
146 - Instance method objects (through .im_self and .im_class).
148 In particular, modules are not chased. Maybe they should be. See
149 the next section for a way to force modules to get chased.
152 CHANGING THE SET OF INTERESTING TYPES
154 Methods of a CycleFinder object can be used to alter/query its view of
155 the set of types find_cycles "chases":
157 z.chase_type(t, t_refs_func, t_tag_func)
158 Add type t to the set of interesting types.
159 t_refs_func is a function of one argument x, where type(x) is t;
160 it should return a sequence (typically a list or tuple) of all
161 objects directly reachable from x.
162 t_tag_func is a function of two arguments x and i, where type(x)
163 is t and i in range(len(t_refs_func(x))). It should return a
164 brief string describing how t_refs_func(x][i] was obtained from
166 See the _XXX_refs and _XXX_tag functions at the start of the
167 module for examples of all this.
170 Remove type t from the set of interesting types. find_cycles
171 will not attempt to chase the objects reachable from objects of
175 Return the set of interesting types, as a list.
178 CHANGING THE SET OF INTERESTING CYCLES
180 Sometimes there are "expected" cycles you would like to ignore; e.g.,
181 this can happen if you install a module-chaser, because there are
182 cycles in Python's implementation you typically don't care about (for
183 example, if your module imports sys, there's a cycle because
184 sys.modules points back to your module!).
186 z.install_cycle_filter(filter_func=None)
187 filter_func=None -> a way to ignore "expected" cycles.
189 filter_func is a function of one argument, a cycle. Each time
190 find_cycles finds a cycle, the cycle is passed to filter_func. The
191 cycle is ignored unless filter_func returns true. Passing None
192 for filter_func restores the default behavior (do not ignore any
195 A cycle is a list of (object, index) pairs, where the first object
196 in the list is the same as the last object in the list, and where
197 the object at cycle[i][0] is the cycle[i][1]'th object obtained
198 from object cycle[i-1][0]. cycle[0][1] should be ignored (it tells
199 us how we got to the first item in the cycle to begin with, but
200 that's irrelevant to the cycle).
205 Below is the driver I used to track cycles in IDLE; it's a replacement
208 At first it didn't install function or module chasers, or a cycle filter,
209 and printed everything. This turned up a bunch of easy cases, and the
210 show_sccs output was surprisingly revealing (all the cycles fell into a
211 handful of SCCs, which corresponded to distinct cycle-creating IDLE
212 subsystems). show_arcs was also very helpful in getting the big picture.
213 show_cycles output was too voluminous to be helpful.
215 After those cycles were broken, the job got harder. A module chaser was
216 added, which turned up another class of cycles, and then a function
217 chaser turned up 100s more. Most of these involved expected cycles due
218 to Python's implementation, so a cycle filter was installed to ignore
219 cycles that didn't contain at least one class instance. The remaining
220 cycles were isolated special cases, and only show_cycles output was
223 After all cycles were purged, IDLE was still leaking, so driver output was
224 added to display the root-set objects still alive at the end. This turned
225 up many cases where objects were living only because registration in the
226 root set was keeping them alive. So a loop was added to the driver that
227 repeatedly purges dead root-set objects and tries again. The __del__
228 methods of the purged roots caused other root objects to become trash,
229 and after several iterations of this the output reaches a steady state.
231 IDLE is still leaking (as of 18-Jul-1999), but ever less so, and while
232 Cyclops is no longer finding cycles, the driver's "live at the end"
233 output is still the best clue I've got for guessing what to do next.
235 Interesting: At the start of this, it turned out that almost all cycles
236 were reachable from places outside themselves. That is, they would not
237 have been considered trash even if Python used a mark-&-sweep form of
238 garbage collection. IDLE's problems, in large part inherited from Tkinter,
239 are simply that "everything points to everything else". The good news is
240 that Guido was able to clean most of this up just by adding reference-
241 purging code to widgets' explicitly-called destroy() methods.
243 #! /usr/bin/env python
249 return x.__dict__.values()
252 return "." + x.__dict__.keys()[i]
255 return x.func_globals, x.func_defaults
258 return (".func_globals", ".func_defaults")[i]
260 def instance_filter(cycle):
261 for obj, index in cycle:
262 if type(obj) is types.InstanceType:
266 # Note: PyShell binds ModifiedInterpreter.locals to __main__.__dict__,
267 # and __main__ is *us*. So if we don't keep the CycleFinder instance
268 # out of the global namespace here, z starts chewing over its own
269 # instance attributes. Nothing breaks, but the output is at best
273 z = Cyclops.CycleFinder()
274 z.chase_type(types.ModuleType, mod_refs, mod_tag)
275 z.chase_type(types.FunctionType, func_refs, func_tag)
276 z.install_cycle_filter(instance_filter)
286 print "non-cyclic root set objects:"
288 numsurvivors = numdead = 0
289 for rc, cyclic, x in z.get_rootset():
290 if not sawitalready.has_key(id(x)):
291 sawitalready[id(x)] = 1
294 numdead = numdead + 1
297 numsurvivors = numsurvivors + 1
300 print numdead, "dead;", numsurvivors, "non-cycle & alive"
303 print "releasing dead root-set objects and trying again"
311 # added purge_dead_roots arg to find_cycles
312 # rearranged module docstring; added IDLE driver sample
314 # renamed print_obj to show_obj, and advertised it
315 # redid adjusted refcount computations to account for root-set
317 # changed get_rootset to return (refcount, cyclic?, obj) triples
319 # freed __init_tracer from dependence on name "self"
320 # rearranged __find_cycles' inner loop for a nice little speed gain
321 # which was promptly way more than lost by new code to compute &
322 # display adjusted refcounts
323 # which was partly regained by rewriting all that
325 # added SCC computation/display
326 # added show_cycles; find_cycles no longer prints anything
327 # changed all showXXX names to show_XXX
328 # added install_cycle_filter
330 # first version I put under source control
332 __version__ = 0, 9, 4
334 #########################################################################
335 # Type-specific reference revealers.
337 # _T_refs(obj) should return a sequence of all objects directly
338 # reachable from obj.
340 # _T_tag(obj, i) should return a string briefly describing how
341 # _T_refs(obj][i] was obtained from obj.
343 # Why the separation? Speed and space: string tags are never
344 # computed unless a cycle is found and so something needs to be
348 return x.keys() + x.values()
352 return ".keys()[%d]" % i
354 return "[%s]" % _quickrepr(x.keys()[i-n])
361 _tuple_refs = _list_refs
362 _tuple_tag = _list_tag
364 def _instance_refs(x):
365 # the keys are strings, so not interesting to return
366 return x.__dict__.values()
367 def _instance_tag(x, i):
368 return "." + x.__dict__.keys()[i]
370 _class_refs = _instance_refs
371 _class_tag = _instance_tag
373 def _instance_method_refs(x):
374 return (x.im_self, x.im_class)
375 def _instance_method_tag(x, i):
376 return (".im_self", ".im_class")[i]
379 _default_refs_dispatcher = {
380 types.DictType: _dict_refs,
381 types.ListType: _list_refs,
382 types.TupleType: _tuple_refs,
383 types.InstanceType: _instance_refs,
384 types.ClassType: _class_refs,
385 types.MethodType: _instance_method_refs,
387 _default_tag_dispatcher = {
388 types.DictType: _dict_tag,
389 types.ListType: _list_tag,
390 types.TupleType: _tuple_tag,
391 types.InstanceType: _instance_tag,
392 types.ClassType: _class_tag,
393 types.MethodType: _instance_method_tag,
395 _InstanceType = types.InstanceType
396 _ClassType = types.ClassType
399 del _dict_refs, _list_refs, _tuple_refs, _instance_refs, \
400 _class_refs, _instance_method_refs
401 del _dict_tag, _list_tag, _tuple_tag, _instance_tag, \
402 _class_tag, _instance_method_tag
404 #########################################################################
405 # A class to make short string representations of objects, for speed
406 # and brevity. The std repr.repr sorts dicts by keys, but we refer to
407 # the keys via numeric subscript in cycle reports, so first a derived
408 # class that leaves dicts in raw order. Also, instances, instance
409 # methods and classes frequently appear in cycle reports, so avoid
410 # chopping their reprs at all. We're only trying to prevent massive
411 # expense for massive lists, tuples & dicts.
417 class _CyclopsRepr(_repr.Repr):
420 _repr.Repr.__init__(self)
421 # Boost the limit on types we don't know about; else it's too
422 # easy to get a useless repr string when adding new types via
423 # CycleFinder.chase_type.
424 # Perhaps better to expose this class too, but-- sheesh --
425 # this module is complicated enough!
426 self.maxstring = self.maxother = 40
428 # override base dictionary formatter; the code is almost the same,
429 # we just leave the dict order alone
431 def repr_dictionary(self, x, level):
438 for k, v in x.items()[:min(n, self.maxdict)]:
441 s = s + self.repr1(k, level-1)
442 s = s + ': ' + self.repr1(v, level-1)
447 # don't chop instance, class or instance method reprs
449 def repr_instance(self, x, level):
452 # Bugs in x.__repr__() can cause arbitrary
453 # exceptions -- then make up something
455 return '<' + x.__class__.__name__ + ' instance at ' + \
458 def repr_class(self, x, level):
461 repr_instance_method = repr_class
463 _quickrepr = _CyclopsRepr().repr
465 #########################################################################
466 # CycleFinder is the workhorse.
468 def typename_address_cmp(x, y):
469 if isinstance(x, _InstanceType) and isinstance(y, _InstanceType):
470 xname, yname = x.__class__.__name__, y.__class__.__name__
471 elif isinstance(x, _ClassType) and isinstance(y, _ClassType):
472 xname, yname = x.__name__, y.__name__
474 xname, yname = type(x).__name__, type(y).__name__
475 return cmp((xname, id(x)), (yname, id(y)))
478 """Class for finding cycles in Python data structures.
480 See Cyclops module docstring for details.
484 """Create a cycle finder with empty root set."""
487 self.refs_dispatcher = _default_refs_dispatcher.copy()
488 self.tag_dispatcher = _default_tag_dispatcher.copy()
489 self.cycle_filter = None
492 """Remove all internal references to external objects.
494 Empties the root set.
495 Does not change the set of types this CycleFinder chases.
496 Does not change the cycle filter in effect.
502 def register(self, obj):
503 """obj -> add object obj to the root set."""
505 self.roots.append(obj)
507 def run(self, func, args=(), kwargs={}):
508 """func, args=(), kwargs={} -> add objects to root set by magic.
510 Function func is invoked with arguments args and keyword
511 arguments kwargs. For the duration of the call, each class
512 instance initialized by an __init__ call is automatically
513 added to the root set. The result of invoking func is
516 # This clever method of trapping __init__ invocations was
517 # stolen from Lars' plumbo.py.
519 sys.setprofile(self.__init_tracer)
521 return apply(func, args, kwargs)
525 def find_cycles(self, purge_dead_roots=0):
526 """purge_dead_roots=0 -> look for cycles, return true if found.
528 Identify all cycles among objects reachable from the root set.
529 Return true iff at least one cycle is found.
531 This should be called before any of the show_XXX methods.
532 Note that it's OK to add more objects to the root set and
533 call it again, or to change the set of chased types, etc.
534 find_cycles starts over from scratch each time it's called.
536 If optional arg purge_dead_roots is true (default false),
537 before searching for cycles the root set is purged of all
538 objects that the preceding run of find_cycles determined had a
539 true refcount of 0 (that is, the root set objects that are
540 still alive only because they appear in the root set).
541 Purging these allows their finalizers to get invoked, which
542 may allow a cascade of other objects (including cycles) to go
545 See also method install_cycle_filter.
548 if purge_dead_roots and self.roots:
549 id2rc = self.id2rc.get
552 if id2rc(id(x), None) != 0:
554 self.roots = survivors
555 del x, survivors, id2rc
558 self.__find_cycles(self.roots, 0)
559 del self.seenids[id(self.roots)] # not a user-visible object
561 # Compute true refcounts for objects in cycles.
563 from sys import getrefcount
564 for x in self.cycleobjs.values():
565 # From the system refcount, subtract one for each of:
566 # being an element in the loop temp cycleobjs.values()
568 # being an argument to getrefcount
569 # being a value in the cycleobjs dict
570 # showing up exactly once somewhere in self.sccno2objs
572 id2rc[xid] = getrefcount(x) - 5
574 # Need also to subtract refs due to appearances in
575 # self.cycles. Complication: some pairs in self.cycles may
578 isknown = seenpairs.has_key
579 for cycle in self.cycles:
582 if not isknown(pairid):
583 seenpairs[pairid] = 1
585 id2rc[xid] = id2rc[xid] - 1
586 del isknown, seenpairs
588 # And need also to subtract refs for membership is self.roots.
589 # While we're at it, also compute adjusted refcounts for other
593 if id2rc.has_key(xid):
594 id2rc[xid] = id2rc[xid] - 1
596 assert not self.cycleobjs.has_key(xid)
597 # Subtract one for each of:
599 # being an argument to getrefcount
600 # being in self.roots
601 id2rc[xid] = getrefcount(x) - 3
603 return len(self.cycles) > 0
605 def install_cycle_filter(self, filter_func=None):
606 """filter_func=None -> a way to ignore "expected" cycles.
608 See module docstring for details. This is a callback function
609 invoked whenever find_cycles() finds a cycle; the cycle is
610 ignored unless the callback returns true.
613 self.cycle_filter = filter_func
615 def show_stats(self):
616 """Print statistics for the last run of find_cycles."""
618 self._print_separator()
619 print "# objects in root set:", len(self.roots)
620 print "# distinct structured objects reachable:", len(self.seenids)
621 print "# distinct structured objects in cycles:", len(self.cycleobjs)
622 print "# cycles found:", len(self.cycles)
623 print "# cycles filtered out:", self.ncyclesignored
624 print "# strongly-connected components:", len(self.sccno2objs)
625 print "# arcs examined:", self.narcs
627 def show_cycles(self):
628 """Print all cycles to stdout."""
630 self._print_separator()
631 print "# all cycles:"
634 self._print_cycle(self.cycles[i])
638 def show_cycleobjs(self, compare=typename_address_cmp):
639 """compare=typename_address_cmp -> print all objects in cycles.
641 Prints to stdout. Each distinct object find_cycles found in a
642 cycle is displayed. The set of objects found in cycles is
643 first sorted by the optional "compare" function. By default,
644 objects are sorted using their type name as the primary key
645 and their storage address (id) as the secondary key; among
646 objects of instance type, sorts by the instances' class names;
647 among objects of class type, sorts by the classes' names.
650 self._print_separator()
651 print "# objects involved in cycles:"
652 objs = self.cycleobjs.values()
657 def show_sccs(self, compare=typename_address_cmp):
658 """compare=typename_address_cmp -> print SCCs.
660 Prints to stdout. Shows the objects in cycles partitioned into
661 strongly connected components (that is, the largest groupings
662 possible such that each object in an SCC is reachable from every
663 other object in that SCC). Within each SCC, objects are sorted
664 as for show_cycleobjs.
667 self._print_separator()
668 print "# cycle objects partitioned into maximal SCCs:"
669 sccs = self.sccno2objs.values()
672 print "--- SCC", i+1, "of", n
678 def show_arcs(self, compare=None):
679 """compare=None -> print unique arc types in cycles.
681 See module docstring for details. Briefly, each arc in a
682 cycle is categorized by the type of the source node, the kind
683 of arc (how we got from the source to the destination), and
684 the type of the destination node. Each line of output
685 consists of those three pieces of info preceded by the count
686 of arcs of that kind. By default, the rows are sorted first
687 by column 2 (source node type), then by columns 3 and 4.
690 self._print_separator()
691 print "# arc types involved in cycles:"
692 items = self.arctypes.items()
697 for triple, count in items:
698 print "%6d %-20s %-20s -> %-20s" % ((count,) + triple)
700 def get_rootset(self):
701 """Return the root set, as a list of (rc, cyclic?, obj) tuples.
703 Should be called after find_cycles. For each object in the
704 root set, returns a triple consisting of
706 number of outstanding references less those due to
707 CycleFinder internals; see show_obj docstring for more
708 details; this will be None if find_cycles hasn't been
709 run, or not since the last clear()
711 true (1) iff obj is known to be in a cycle
717 getrc = self.id2rc.get
718 incycle = self.cycleobjs.has_key
721 result.append((getrc(xid, None), incycle(xid), x))
724 def chase_type(self, t, t_refs_func, t_tag_func):
725 """t, t_refs_func, t_tag_func -> chase type t.
727 See module docstring for details.
730 self.refs_dispatcher[t] = t_refs_func
731 self.tag_dispatcher[t] = t_tag_func
733 def dont_chase_type(self, t):
734 """t -> remove type t from the set of chased types.
736 See module docstring for details.
740 del self.refs_dispatcher[t], \
741 self.tag_dispatcher[t]
745 def get_chased_types(self):
746 """Return the set of chased types, as a list."""
748 return self.refs_dispatcher.keys()
750 def __init_tracer(self, frame, event, args):
751 if event == "call" and frame.f_code.co_name == "__init__":
752 # We want to capture the first argument -- this works whether
753 # or not it's named "self", and in case the function is like
754 # def __init__(*args):
755 # it's still OK: we'll pick up the name 'args', and add the
756 # tuple it's bound to to the root set; the tuple's first
757 # element is "self", so will be found by the tuple-chaser.
758 locals = frame.f_code.co_varnames
760 # first argname is first element of locals
761 self.register(frame.f_locals[locals[0]])
764 # Clear out everything except:
766 # the refs_dispatcher
770 # stack exactly mirrors __find_cycles' recursive calls; it's a
771 # list of (object, index) pairs.
774 # Map id of active object to its index in self.stack. Since
775 # it's a depth-first search, there's a cycle iff we hit an
776 # object that's already on the stack.
779 # Set of (addresses of) all interesting objects seen. Since
780 # we use a depth-first search, there's never a reason to
784 # List of all cycles found; each element is a stack slice (a
785 # list of (object, index) pairs).
788 # Set of objects found in cycles (maps id(obj) -> obj).
791 # Classifies arcs found in cycles, mapping
792 # (source_type, selector, destination_type) triples to a count
793 # of how many times that triple appears in a cycle.
796 # Support for computing strongly-connected components (SCC).
797 # We do this by merging cycles into equivalence classes.
798 # Could be done faster by e.g. Tarjan's algorithm in
799 # __find_cycles, but would rather keep that lean since cycles
800 # are expected to be unusual.
801 self.nextsccno = 1 # monotonically increasing SCC id
802 self.id2sccno = {} # map id(obj) to obj's sccno
803 self.sccno2objs = {} # map sccno back to list of objects
805 # For objects in cycles and root set, map address to true
809 # Number of arcs examined.
812 # Number of cycles ignored (filtered out).
813 self.ncyclesignored = 0
815 def __find_cycles(self, obj, i, id=id, type=type, len=len):
816 # This can be called an enormous number of times, so speed
817 # tricks are appropriate.
821 # Set of ids of objects being, or formerly, chased.
822 seenids = self.seenids
823 already_seen = seenids.has_key
825 # Maps active object id to index in stack.
826 id2stacki = self.id2stacki
827 currently_on_stack = id2stacki.has_key
829 refs_dispatcher = self.refs_dispatcher
830 is_interesting_type = refs_dispatcher.has_key
834 id2stacki[myid] = len(stack)
835 stack.append((obj, i))
836 refs = refs_dispatcher[type(obj)](obj)
837 self.narcs = self.narcs + len(refs)
838 for i in xrange(len(refs)):
840 if is_interesting_type(type(child)):
842 if not already_seen(childid):
843 self.__find_cycles(child, i)
844 elif currently_on_stack(childid):
845 cycle = stack[id2stacki[childid]:]
846 cycle.append((child, i)) # complete the cycle
847 self.__study_cycle(cycle)
849 del stack[-1], id2stacki[myid]
851 # a helper for __study_cycle
852 def __obj2arcname(self, obj):
853 if isinstance(obj, _InstanceType):
854 name = obj.__class__.__name__ + "()"
855 elif isinstance(obj, _ClassType):
858 name = type(obj).__name__
861 def __study_cycle(self, slice):
862 assert len(slice) >= 2
864 if self.cycle_filter is not None and \
865 not self.cycle_filter(slice):
866 self.ncyclesignored = self.ncyclesignored + 1
869 self.cycles.append(slice)
871 # Pick (or create) an SCC equivalence class for this cycle.
872 sccnowinner = self.id2sccno.get(id(slice[0][0]), None)
873 if sccnowinner is None:
874 sccnowinner = self.nextsccno
875 self.nextsccno = self.nextsccno + 1
876 self.sccno2objs[sccnowinner] = []
877 classwinner = self.sccno2objs[sccnowinner]
879 for i in xrange(len(slice)-1):
881 key1 = self.__obj2arcname(obj1)
883 obj2, index = slice[i+1]
884 key2 = self.tag_dispatcher[type(obj1)](obj1, index)
886 key3 = self.__obj2arcname(obj2)
888 key = (key1, key2, key3)
889 self.arctypes[key] = self.arctypes.get(key, 0) + 1
891 self.cycleobjs[id(obj1)] = obj1
893 # Merge the equivalence class for obj1 into classwinner.
894 thissccno = self.id2sccno.get(id(obj1), None)
895 if thissccno is None:
896 self.id2sccno[id(obj1)] = sccnowinner
897 classwinner.append(obj1)
898 elif thissccno != sccnowinner:
899 # merge obj1's entire equivalence class
900 tomerge = self.sccno2objs[thissccno]
902 self.id2sccno[id(obj2)] = sccnowinner
903 classwinner.extend(tomerge)
904 del self.sccno2objs[thissccno]
906 ################################################################
907 # Various output routines. If someone is motivated enough to
908 # change one of these, they're motivated enough to subclass us!
910 def show_obj(self, obj):
911 """obj -> print short description of obj to sdtout.
915 <address> rc:<refcount> <typename>
922 If find_cycles() has been run and obj is in the root set
923 or was found in a cycle, this is the number of references
924 outstanding less the number held internally by
925 CycleFinder. In most cases, this is what the true
926 refcount would be had you not used CycleFinder at all.
927 You can screw that up, e.g. by installing a cycle filter
928 that holds on to references to one or more cycle elements.
929 If find_cycles() has not been run, or has but obj wasn't
930 found in a cycle and isn't in the root set, <refcount> is
933 type(obj), as a string. If obj.__class__ exists, also
934 prints the class name.
936 repr(obj), but using a variant of the std module repr.py
937 that limits the number of characters displayed.
941 rc = self.id2rc.get(objid, "?")
942 print hex(objid), "rc:" + str(rc), type(obj).__name__,
943 if hasattr(obj, "__class__"):
946 print " repr:", _quickrepr(obj)
948 def _print_separator(self):
951 def _print_cycle(self, slice):
954 print "%d-element cycle" % (n-1)
959 index = slice[i+1][1]
961 self.tag_dispatcher[type(obj)](obj, index), \
966 def __init__(me, name):
969 return "X(" + `self.name` + ")"
971 a, b, c, d = X('a'), X('b'), X('c'), X('d')
976 d.k = {'harrumph': (1, 2, d, 3)}
980 a.__repr__ = a.__repr__
991 del a, b, c, d, e, X, Y, lonely
998 print "dead root set objects:"
999 for rc, cyclic, x in z.get_rootset():
1005 if __name__ == "__main__":