[Zodb-checkins] CVS: Packages/StorageGC - CyclicGC.py:1.2

[tim@digicool.com]

Update of /cvs-repository/Packages/StorageGC
In directory korak:/tmp/cvs-serv23673/StorageGC

Modified Files:
	CyclicGC.py 
Log Message:
Added user-level comment-docs for the GCable and CycleGC interfaces.  Barry,
Jim, does the writeup jibe with your understandings of our design mtg?



--- Updated File CyclicGC.py in package Packages/StorageGC --
--- CyclicGC.py	2001/04/19 17:37:12	1.1
+++ CyclicGC.py	2001/04/19 19:05:28	1.2
@@ -3,6 +3,80 @@
 # named "storage" to reflect its expected use.  storage must implement
 # the GCable interface, and objects must be hashable.
 
+###########################################################################
+# The GCable interface.
+# A storage implementing GCable implements the following methods.  "oid"
+# is short for object ID, and oids must be hashable (usable as Python dict
+# keys); no other assumption about oids is made by CycleGC.
+#
+# GCable.gcRefcount(oid) -> int
+#     Return reference count of oid.
+#
+# GCable.gcReferences(oid) -> oids (a list of oid)
+#     Return list of oid's immediate successors.
+#     y is in gcReferences(x) if and only if x accounts for at least one
+#     of y's refcounts; if x accounts for N of y's refcounts, then y must
+#     appear exactly N times in gcReferences(x).
+#
+# GCable.trash(oids) -> None
+#     This is a callback, invoked when CycleGC has discovered cyclic
+#     garbage.  oids is a list of objects in garbage cycles, and of objects
+#     reachable only from garbage cycles.
+#     trash() must be robust in the face of an oid that no longer exists,
+#     since CycleGC can run incrementally, and oids it was originally told
+#     about may no longer exist by the time it discovers they were trash.
+
+###########################################################################
+# The CycleGC interface.
+# The CycleGC class here supplies the following methods for use by
+# refcounted storages desiring detecting of unreachabe cycles.
+#
+# Typical use:
+#
+#     collector = CycleGC(self)
+#     collector.start(list_of_suspect_objects)
+#     while not collector.done():
+#         collector.resume()
+#
+# CycleGC.__init__(storage)
+#     The constructor takes a storage argument.  The storage must implement
+#     GCable (see above).
+#
+# CycleGC.start(oids) -> None
+#     The list of oids is taken as a root set.  All objects reachable from
+#     the root set (the "transitive closure", or TC) are examined, and
+#     all objects in the TC *not* reachable-- whether directly or
+#     indirectly --from *outside* the TC are (eventually) passed to
+#     storage's gcTrash() callback.  The intent is that the storage take
+#     its best guess at which objects *may* be in garbage cycles, and
+#     pass them to .start().
+#     .start() only begins the job.  .resume() continues it.  In effect,
+#     this is a by-hand coroutine approach.
+#     It's OK to call .start() again before CycleGC has completed analyzing
+#     the TC of the objects passed to preceding .start() calls.  In that
+#     case, the subsequent OIDs are queued internally for later processing.
+#     In particular, the gcTrash() callback may want to call .start() if
+#     seeing a list of actual trash helps it guess which other objects may
+#     be in garbage cycles.
+#
+# CycleGC.resume(effort=-1) -> None
+#     .resume() continues analyzing the TC.  Optional integer argument
+#     "effort" is a measure of how much work the caller wants .resume()
+#     to do before returning.  A value <= 0 means .resume() should not
+#     return until analysis is complete (i.e., until .done() returns true).
+#     It's OK to call .resume() when .done() returns true, although there's
+#     no point to doing so.
+#     XXX TODO All effort values are treated as -1 right now.
+#     XXX TODO Define what effort *means*; e.g., perhaps an approximation
+#     XXX      to the maximum number of .gcReferences() calls the storage
+#     XXX      wants to endure before regaining control?  milliseconds
+#     XXX      elapsed?  Not yet clear what would be most useful.
+#
+# CycleGC.done() -> bool
+#     Return true when analysis is complete, false if .resume() has more
+#     work to do.
+
+###########################################################################
 # The approach takes a bit from many techniques in the literature, but is
 # closest to:
 #
@@ -18,6 +92,7 @@
 # XXX recursion, and will make the algorithm 10x more brittle.  Need a great
 # XXX test suite first.
 
+###########################################################################
 # Indices into object descriptors.
 # An object descriptor is a 4-list of the form [OBJ, RC, ADJRC, ISFREE].
 # A list is used instead of an object to slash the space overhead; a tuple