Interface Traverseproc

This interface defines a CPython-equivalent traverse-mechanism allowing to detect reference cycles. While this is crucial for cyclic gc support in CPython, it only serves debugging purposes in Jython. As a side-effect it allows a more complete implementation of the gc module.

Note that implementing this interface is only OPTIONAL. Gc will work fine in Jython without it. Still we took care to have all core classes implement it and recommend third party extension providers to do so as well with custom PyObject-implementations.

Of course this interface shall only be implemented by PyObjects that potentially own direct references to other PyObjects. Note that indirect references via non-PyObjects should also be treated as "direct" (c.f. tracefunc in PyFrame). PyObjects that don't own references to other PyObjects under any condition and neither inherit such references from a superclass are strictly recommended to be annotated Untraversable.

Jython's traverse mechanism serves debugging purposes to ease finding memory leaks and compare gc behavior with CPython. While it is of course not required that gc behaviors of Jython and CPython equal, there might arise subtle bugs from these different behaviors. Jython's traverse mechanism is intended to allow finding such bugs by comparing gc behavior to CPython and isolating the Python code that is not robust enough to work invariant under different gc behaviors. See also gc for more details on this.

Further this mechanism is crucial for some aspects of gc-support of the JyNI project. JyNI does not strictly depend on it to emulate CPython's gc for extensions, but would have to perform inefficient reflection-based traversal in some edge-cases (which might also conflict with security managers).

Note that the slots-array and - if existent - the user-dict of fooDerived classes is traversed by TraverseprocDerived. The gc-module takes care of exploiting both traverse methods in its static traverse method. So for manual traversion one should always use gc.traverse(PyObject, Visitproc, Object) rather than directly calling methods in this interface.

Also note that PyObject.objtype is not subject to Traverseprocs by default. In CPython only objects with heap-types traverse their ob_type-field. In Jython, fooDerived-classes are the equivalents of heapTypes. For such classes PyObject.objtype is actually traversed (along with the user dict).

Note for implementing:
Every non-static, strong-referenced PyObject should be passed to the Visitproc. If Objects or interface-types are referenced where it is not known, whether it is a PyObject or references other PyObjects, one should check for PyObject via instanceof. If a non-PyObject implements Traverseproc, one can traverse it by delegating to its Traverseproc methods.

Warning:
If one lets non-PyObjects implement Traverseproc, extreme care must be taken, whether the traverse call shall be passed on to other non-PyObject Traverseproc-implementers, as this can cause infinite traverse cycles.
Examples for non-PyObjects that implement Traverseproc are PyException and Fetch. A safer, but potentially slower way to deal with non-PyObject-Traverseprocs or any other non-PyObject that might contain references to other PyObjects is gc.traverseByReflection(Object, Visitproc, Object). This is for instance used in PyArray.

Examples

In the following we provide some examples with code-snippets to demonstrate and streamline the writing of Traverseproc-implementations.
Since this peace of API was introduced to enhance a large existing code-base, we recommend to put the Traverseproc-implementation always to the end of a class and separate it from the original code by two blank lines and a comment "Traverseproc implementation".

Let's start with classes that don't hold references to PyObjects. If the class extends some other class that implements Traverseproc, nothing special needs to be done. For instance, we have this situation in PySet. It extends BaseSet, which in turn implements Traverseproc:

 @ExposedType(name = "set", base = PyObject.class, doc = BuiltinDocs.set_doc)
 public class PySet extends BaseSet {
   ...
 }
 

If the class neither contains PyObject-references, nor extends some Traverseproc-implementing class, it is recommended to be annotated Untraversable. PyInteger is an example for this:

 @Untraversable
 @ExposedType(name = "int", doc = BuiltinDocs.int_doc)
 public class PyInteger extends PyObject {
   ...
 }
 

If there are simply some PyObject(-subclass), non-static fields in the class, let it implement Traverseproc. Write traverse(Visitproc, Object) by just visiting the fields one by one. Check each to be non-null previously unless the field cannot be null for some good reason. If Visitproc.visit(PyObject, Object) returns non-zero, return the result immediately (i.e. abort the traverse process). The following example is taken from PyMethod:

  /* Traverseproc implementation */
  @Override
  public int traverse(Visitproc visit, Object arg) {
      int retVal;
      if (im_class != null) {
          retVal = visit.visit(im_class, arg);
          if (retVal != 0) {
              return retVal;
          }
      }
      if (__func__ != null) {
          retVal = visit.visit(__func__, arg);
          if (retVal != 0) {
              return retVal;
          }
      }
      return __self__ == null ? 0 : visit.visit(__self__, arg);
  }
 

Implement refersDirectlyTo(PyObject) by checking the argument to be non-null and identity-comparing it to every field:

  @Override
  public boolean refersDirectlyTo(PyObject ob) {
      return ob != null && (ob == im_class || ob == __func__ || ob == __self__);
  }
 

If there is a Java-set or other iterable that it is not a PyObject, but contains PyObjects, visit every element. Don't forget to check for non-null if necessary and return immediately, if Visitproc.visit(PyObject, Object) returns non-zero. The following example is taken from BaseSet:

  /* Traverseproc implementation */
  @Override
  public int traverse(Visitproc visit, Object arg) {
      int retValue;
      for (PyObject ob: _set) {
          if (ob != null) {
              retValue = visit.visit(ob, arg);
              if (retValue != 0) {
                  return retValue;
              }
          }
      }
      return 0;
  }
 

In this case, refersDirectlyTo(PyObject) can be implemented (potentially) efficiently by using the backing set's contains-method:

  @Override
  public boolean refersDirectlyTo(PyObject ob) {
      return ob != null && _set.contains(ob);
  }
 

If a class extends a Traverseproc-implementing class and adds PyObject-references to it, the parent-traverse-method should be called initially via super (example is taken from PyJavaType):

  /* Traverseproc implementation */
  @Override
  public int traverse(Visitproc visit, Object arg) {
      int retVal = super.traverse(visit, arg);
      if (retVal != 0) {
          return retVal;
      }
      if (conflicted != null) {
          for (PyObject ob: conflicted) {
              if (ob != null) {
                  retVal = visit.visit(ob, arg);
                  if (retVal != 0) {
                      return retVal;
                  }
              }
          }
      }
      return 0;
  }
 

In contrast to that, refersDirectlyTo(PyObject) should call its parent-method as late as possible, because that method might throw an UnsupportedOperationException. By calling it in the end, we have the chance to fail- or succeed fast before a potential exception occurs:

  @Override
  public boolean refersDirectlyTo(PyObject ob) throws UnsupportedOperationException {
      if (ob == null) {
          return false;
      }
      if (conflicted != null) {
          for (PyObject obj: conflicted) {
              if (obj == ob) {
                  return true;
              }
          }
      }
      return super.refersDirectlyTo(ob);
  }
 

While reflection-based traversal should be avoided if possible, it can be used to traverse fields that might contain references to PyObjects, but cannot be inferred at compile-time. gc.canLinkToPyObject(Class, boolean) can help to safe some performance by failing fast if type-info already rules out the possibility of the field holding PyObject-references. This technique is for instance used to traverse the content of PyArray:

  /* Traverseproc implementation */
  @Override
  public int traverse(Visitproc visit, Object arg) {
      if (data == null || !gc.canLinkToPyObject(data.getClass(), true)) {
          return 0;
      }
      return gc.traverseByReflection(data, visit, arg);
  }
 

gc.canLinkToPyObject(Class, boolean) also offers a way to let refersDirectlyTo(PyObject) fail fast by type-information:

  @Override
  public boolean refersDirectlyTo(PyObject ob)
          throws UnsupportedOperationException {
      if (data == null || !gc.canLinkToPyObject(data.getClass(), true)) {
          return false;
      }
      throw new UnsupportedOperationException();
  }
 

List of PyObject-subclasses

We conclude with a list of PyObject subclasses in Jython, excluding derived classes.
PyObject-subclasses in Jython checked for need of Traverseproc:


org.python.core:
__builtin__:
BuiltinFunctions - no refs, untraversable
ImportFunction - no refs, untraversable
SortedFunction - no refs, untraversable
AllFunction - no refs, untraversable
AnyFunction - no refs, untraversable
FormatFunction - no refs, untraversable
PrintFunction - no refs, untraversable
MaxFunction - no refs, untraversable
MinFunction - no refs, untraversable
RoundFunction - no refs, untraversable
CompileFunction - no refs, untraversable
OpenFunction - no refs, untraversable
NextFunction - no refs, untraversable
BinFunction - no refs, untraversable
AstList - Traverseproc
BaseBytes - no refs, untraversable
BaseDictionaryView - Traverseproc
BaseSet - Traverseproc
ClasspathPyImporter - no refs, untraversable
ContextGuard: - no PyObject
ContextCode - Traverseproc
GeneratorContextManager - Traverseproc
exceptions - no refs, untraversable
BoundStaticJavaMethod - no refs, untraversable
JavaImporter - no refs, untraversable
JavaProxyList:
ListMethod - no refs, untraversable (extends PyBuiltinMethodNarrow)
ListMulProxyClass - no refs, untraversable
JavaProxyMap:
MapMethod - no refs, untraversable (extends PyBuiltinMethodNarrow)
MapClassMethod - no refs, untraversable (extends PyBuiltinClassMethodNarrow)
JavaProxySet:
SetMethod - no refs, untraversable (extends PyBuiltinMethodNarrow)
SetMethodVarargs - no refs, untraversable (extends SetMethod)
CopyMethod - no refs, untraversable
IsSubsetMethod - no refs, untraversable
IsSupersetMethod - no refs, untraversable
Py:
JavaCode - Traverseproc
JavaFunc - no refs, untraversable
Py2kBuffer - no refs, untraversable
PyArray - Traverseproc, traverses via reflection
PyBaseCode - no refs, abstract class
PyBaseException - Traverseproc
PyBaseString - no refs, abstract class
PyBeanEvent - no refs, untraversable
PyBeanEventProperty - no refs, untraversable
PyBeanProperty - no refs, untraversable
PyBoolean - no refs, untraversable
PyBuffer - no PyObject
PyBuiltinCallable - no refs, untraversable
PyBuiltinClassMethodNarrow - no refs, abstract class
PyBuiltinFunction - no refs, untraversable
PyBuiltinFunctionNarrow - no refs, untraversable
PyBuiltinFunctionSet - no refs, untraversable
PyBuiltinMethod - Traverseproc
PyBuiltinMethodNarrow - no refs, abstract class
PyBuiltinMethodSet - Traverseproc
PyByteArray - no refs, untraversable
PyBytecode - Traverseproc
PyStackWhy - no refs, untraversable
PyStackException - Traverseproc
PyTryBlock - no refs, untraversable
PyCallIter - Traverseproc (with call to super)
PyCell - Traverseproc
PyClass - Traverseproc
PyClassMethod - Traverseproc
PyClassMethodDescr - no refs, untraversable
PyCode - no refs, abstract class
PyComplex - no refs, untraversable
PyCompoundCallable - Traverseproc
PyDataDescr - no refs, untraversable
PyDescriptor - Traverseproc
PyDictionary - Traverseproc
ValuesIter - no refs, extends PyIterator
ItemsIter - no refs, extends PyIterator
PyMapKeyValSet - no PyObject
PyMapEntrySet - no PyObject
PyDictProxy - Traverseproc
PyEllipsis - no refs, untraversable
PyEnumerate - Traverseproc
PyFastSequenceIter - Traverseproc
PyFile - Traverseproc
PyFileReader - no refs, untraversable
PyFileWriter - no refs, untraversable
PyFloat - no refs, untraversable
PyFrame - Traverseproc
PyFunction - Traverseproc
PyGenerator - Traverseproc (with call to super)
PyIndentationError - no PyObject
PyInstance - Traverseproc
PyInteger - no refs, untraversable
PyIterator - Traverseproc
PyJavaPackage - Traverseproc
PyJavaType - Traverseproc (with call to super)
EnumerationIter - no refs, extends PyIterator
ComparableMethod - no refs, abstract class
PyList - Traverseproc
PyLong - no refs, untraversable
PyMemoryView - Traverseproc
PyMethod - Traverseproc
PyMethodDescr - Traverseproc
PyModule - Traverseproc
PyNewWrapper - Traverseproc
PyNone - no refs, untraversable
PyNotImplemented - no refs, untraversable
PyObject - no refs (objtype is special case)
PyIdentityTuple - Traverseproc
PyOverridableNew - no refs, abstract class
PyProperty - Traverseproc
PyReflectedConstructor - no refs, untraversable
PyReflectedField - no refs, untraversable
PyReflectedFunction - Traverseproc
PyReversedIterator - Traverseproc (with call to super)
PySequence - no refs, abstract class (default Traverseproc implementation)
PySequenceIter - Traverseproc (with call to super)
PySequenceList - no refs, abstract class
PySingleton - no refs, untraversable
PySlice - Traverseproc
PySlot - no refs, untraversable
PyStaticMethod - Traverseproc
PyString - no refs, untraversable (assuming baseBuffer is not a PyObject)
PyStringMap - Traverseproc
StringMapIter - no refs, extends PyIterator, abstract class
ItemsIter - no refs, extends StringMapIter
KeysIter - no refs, extends StringMapIter
ValuesIter - no refs, extends StringMapIter
PySuper - Traverseproc
PySyntaxError - no PyObject
PySystemState - Traverseproc
PySystemStateFunctions - no refs, untraversable
PyAttributeDeleted - no refs, untraversable
FloatInfo - Traverseproc
LongInfo - Traverseproc
PyTableCode - no refs, untraversable
PyTraceback - Traverseproc
PyTuple - Traverseproc
PyType - Traverseproc
PyUnicode - no refs, untraversable
PyXRange - no refs, untraversable
PyXRangeIter - no refs, extends PyIterator
SyspathArchive - no refs, untraversable

org.python.core.stringlib:
FieldNameIterator - no refs, traverses via reflection
MarkupIterator - no refs, untraversable

org.python.core.util:
importer - no refs, abstract class

org.python.jsr223:
PyScriptEngineScope - no refs, untraversable
ScopeIterator - Traverseproc

org.python.modules:
_codecs:
EncodingMap - no refs, untraversable
_hashlib:
Hash - no refs, untraversable
_marshal:
Marshaller - Traverseproc
Unmarshaller - Traverseproc
cStringIO:
StringIO - no refs, extends PyIterator
operator:
OperatorFunctions - no refs, untraversable
operator - no refs, untraversable
PyAttrGetter - Traverseproc
PyItemGetter - Traverseproc
PyMethodCaller - Traverseproc
PyStruct - no refs, untraversable
synchronize:
SynchronizedCallable - Traverseproc

org.python.modules._collections:
PyDefaultDict - Traverseproc (with call to super)
PyDeque - Traverseproc (assuming, Nodes can't build cycles)
PyDequeIter - Traverseproc (with call to super)

org.python.modules._csv:
PyDialect - no refs, untraversable
PyReader - Traverseproc (with call to super)
PyWriter - Traverseproc

org.python.modules._functools:
PyPartial - Traverseproc

org.python.modules._io:
PyFileIO - no refs, untraversable (there is a final PyString "mode" that is guaranteed to be a PyString and no subclass; as such it needs not be traversed since it cannot have refs itself)
PyIOBase - Traverseproc
PyRawIOBase - no refs, extends PyIOBase

org.python.modules._json:
Encoder - Traverseproc
Scanner - Traverseproc
_json: ScanstringFunction - no refs, untraversable
EncodeBasestringAsciiFunction - no refs, untraversable

org.python.modules._jythonlib:
dict_builder - Traverseproc

org.python.modules._threading:
Condition - Traverseproc
Lock - no refs, untraversable

org.python.modules._weakref:
AbstractReference - Traverseproc
ReferenceType - no refs, extends AbstractReference
ProxyType - no refs, extends AbstractReference
CallableProxyType - no refs, extends ProxyType

org.python.modules.bz2:
PyBZ2Compressor - no refs, untraversable
PyBZ2Decompressor - Traverseproc
PyBZ2File - no refs, untraversable
BZ2FileIterator - no refs, extends PyIterator

org.python.modules.itertools:
chain - Traverseproc (with call to super)
combinations - Traverseproc (with call to super)
combinationsWithReplacement - Traverseproc (with call to super)
compress - Traverseproc (with call to super)
count - Traverseproc (with call to super)
cycle - Traverseproc (with call to super)
dropwhile - Traverseproc (with call to super)
groupby - Traverseproc (with call to super)
ifilter - Traverseproc (with call to super)
ifiIterfalse - Traverseproc (with call to super)
imap - Traverseproc (with call to super)
islice - Traverseproc (with call to super)
itertools:
ItertoolsIterator - no refs, extends PyIterator, abstract class
FilterIterator - Traverseproc, extends ItertoolsIterator
WhileIterator - Traverseproc, extends ItertoolsIterator izip - Traverseproc (with call to super)
izipLongest - Traverseproc (with call to super)
permutations - Traverseproc (with call to super)
product - Traverseproc (with call to super)
PyTeeIterator - Traverseproc (with call to super)
repeat - Traverseproc (with call to super)
starmap - Traverseproc (with call to super)
takewhile - Traverseproc (with call to super)

org.python.modules.jffi:
ArrayCData - Traverseproc (with call to super; maybe check referenceMemory field whether it extends PyObject)
ArrayIter - no refs, extends PyIterator
BasePointer - no refs, abstract class
ByReference - no refs, untraversable (maybe check memory field whether it extends PyObject)
CData - Traverseproc (maybe check referenceMemory field whether it extends PyObject)
CType - no refs, abstract class
Builtin - no refs, untraversable
DynamicLibrary - no refs, untraversable
StructLayout:
Field - Traverseproc

org.python.modules.posix:
PosixModule:
FstatFunction - no refs, untraversable
LstatFunction - no refs, untraversable
StatFunction - no refs, untraversable
WindowsStatFunction - no refs, untraversable
PyStatResult - Traverseproc (with call to super)

org.python.modules.random:
PyRandom - no refs, untraversable

org.python.modules.sre:
MatchObject - Traverseproc
PatternObject - Traverseproc
ScannerObject - Traverseproc

org.python.modules.thread:
PyLocal - Traverseproc
PyLock - no refs, untraversable

org.python.modules.time:
PyTimeTuple - Traverseproc (with call to super)
Time:
TimeFunctions - no refs, untraversable

org.python.modules.zipimport:
zipimporter - Traverseproc

org.python.util:
InteractiveInterpreter - no PyObject

com.ziclix.python.sql:
DBApiType - no refs, untraversable
PyConnection - Traverseproc
ConnectionFunc - no refs, extends PyBuiltinMethodSet
PyCursor - Traverseproc
CursorFunc - no refs, extends PyBuiltinMethodSet
PyExtendedCursor - no refs, extends PyCursor
ExtendedCursorFunc - no refs, extends PyBuiltinMethodSet
PyStatement - Traverseproc (because Object sql could be a PyObject or Traverseproc)
zxJDBC - no refs, untraversable
zxJDBCFunc - no refs, untraversable

com.ziclix.python.sql.connect:
Connect - no refs, untraversable
Connectx - no refs, untraversable
Lookup - no refs, untraversable

com.ziclix.python.sql.util:
BCP - Traverseproc
BCPFunc - no refs, extends PyBuiltinMethodSet

org.python.antlr:
AnalyzingParser:
AnalyzerTreeAdaptor - no PyObject
AST - no refs, untraversable
PythonErrorNode - no refs, extends PythonTree
PythonTree - Traverseproc

org.python.antlr.ast:
alias - no refs, extends PythonTree
arguments - Traverseproc (with call to super)
comprehension - Traverseproc (with call to super)
keyword - Traverseproc (with call to super)

org.python.antlr.base:
boolop - no refs, extends PythonTree
cmpop - no refs, extends PythonTree
excepthandler - no refs, extends PythonTree
expr_context - no refs, extends PythonTree
expr - no refs, extends PythonTree
mod - no refs, extends PythonTree
operator - no refs, extends PythonTree
slice - no refs, extends PythonTree
stmt - no refs, extends PythonTree
unaryop - no refs, extends PythonTree

org.python.antlr.op:
Add - no refs, extends PythonTree
And - no refs, extends PythonTree
AugLoad - no refs, extends PythonTree
AugStore - no refs, extends PythonTree
BitAnd - no refs, extends PythonTree
BitOr - no refs, extends PythonTree
BitXor - no refs, extends PythonTree
Del - no refs, extends PythonTree
Div - no refs, extends PythonTree
Eq - no refs, extends PythonTree
FloorDiv - no refs, extends PythonTree
Gt - no refs, extends PythonTree
GtE - no refs, extends PythonTree
In - no refs, extends PythonTree
Invert - no refs, extends PythonTree
Is - no refs, extends PythonTree
IsNot - no refs, extends PythonTree
Load - no refs, extends PythonTree
LShift - no refs, extends PythonTree
Lt - no refs, extends PythonTree
LtE - no refs, extends PythonTree
Mod - no refs, extends PythonTree
Mult - no refs, extends PythonTree
Not - no refs, extends PythonTree
NotEq - no refs, extends PythonTree
NotIn - no refs, extends PythonTree
Or - no refs, extends PythonTree
Param - no refs, extends PythonTree
Pow - no refs, extends PythonTree
RShift - no refs, extends PythonTree
Store - no refs, extends PythonTree
Sub - no refs, extends PythonTree
UAdd - no refs, extends PythonTree
USub - no refs, extends PythonTree