## 2.1.3 Supporting cyclic garbage collection

Python has a cyclic-garbage collector that can identify unneeded objects even when their reference counts are not zero. This can happen when objects are involved in cycles. For example, consider:

    >>> l = []
    >>> l.append(l)
    >>> del l

In this example, we create a list that contains itself. When we delete it, it still has a reference from itself. Its reference count doesn't drop to zero. Fortunately, Python's cyclic-garbage collector will eventually figure out that the list is garbage and free it.

In the second version of the `Noddy` example, we allowed any kind of object to be stored in the `first` or `last` attributes.2.4 This means that `Noddy` objects can participate in cycles:

    >>> import noddy2
    >>> n = noddy2.Noddy()
    >>> l = [n]
    >>> n.first = l

This is pretty silly, but it gives us an excuse to add support for the cyclic-garbage collector to the `Noddy` example. To support cyclic garbage collection, types need to fill two slots and set a class flag that enables these slots:

    #include <Python.h>
    #include "structmember.h"

    typedef struct {
        PyObject_HEAD
        PyObject *first;
        PyObject *last;
        int number;
    } Noddy;

    static int
    Noddy_traverse(Noddy *self, visitproc visit, void *arg)
    {
        int vret;

        if (self->first) {
            vret = visit(self->first, arg);
            if (vret != 0)
                return vret;
        }
        if (self->last) {
            vret = visit(self->last, arg);
            if (vret != 0)
                return vret;
        }

        return 0;
    }

    static int
    Noddy_clear(Noddy *self)
    {
        PyObject *tmp;

        tmp = self->first;
        self->first = NULL;
        Py_XDECREF(tmp);

        tmp = self->last;
        self->last = NULL;
        Py_XDECREF(tmp);

        return 0;
    }

    static void
    Noddy_dealloc(Noddy* self)
    {
        Noddy_clear(self);
        self->ob_type->tp_free((PyObject*)self);
    }

    static PyObject *
    Noddy_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    {
        Noddy *self;

        self = (Noddy *)type->tp_alloc(type, 0);
        if (self != NULL) {
            self->first = PyString_FromString("");
            if (self->first == NULL)
              {
                Py_DECREF(self);
                return NULL;
              }

            self->last = PyString_FromString("");
            if (self->last == NULL)
              {
                Py_DECREF(self);
                return NULL;
              }

            self->number = 0;
        }

        return (PyObject *)self;
    }

    static int
    Noddy_init(Noddy *self, PyObject *args, PyObject *kwds)
    {
        PyObject *first=NULL, *last=NULL, *tmp;

        static char *kwlist[] = {"first", "last", "number", NULL};

        if (! PyArg_ParseTupleAndKeywords(args, kwds, "|OOi", kwlist,
                                          &first, &last,
                                          &self->number))
            return -1;

        if (first) {
            tmp = self->first;
            Py_INCREF(first);
            self->first = first;
            Py_XDECREF(tmp);
        }

        if (last) {
            tmp = self->last;
            Py_INCREF(last);
            self->last = last;
            Py_XDECREF(tmp);
        }

        return 0;
    }

    static PyMemberDef Noddy_members[] = {
        {"first", T_OBJECT_EX, offsetof(Noddy, first), 0,
         "first name"},
        {"last", T_OBJECT_EX, offsetof(Noddy, last), 0,
         "last name"},
        {"number", T_INT, offsetof(Noddy, number), 0,
         "noddy number"},
        {NULL}  /* Sentinel */
    };

    static PyObject *
    Noddy_name(Noddy* self)
    {
        static PyObject *format = NULL;
        PyObject *args, *result;

        if (format == NULL) {
            format = PyString_FromString("%s %s");
            if (format == NULL)
                return NULL;
        }

        if (self->first == NULL) {
            PyErr_SetString(PyExc_AttributeError, "first");
            return NULL;
        }

        if (self->last == NULL) {
            PyErr_SetString(PyExc_AttributeError, "last");
            return NULL;
        }

        args = Py_BuildValue("OO", self->first, self->last);
        if (args == NULL)
            return NULL;

        result = PyString_Format(format, args);
        Py_DECREF(args);

        return result;
    }

    static PyMethodDef Noddy_methods[] = {
        {"name", (PyCFunction)Noddy_name, METH_NOARGS,
         "Return the name, combining the first and last name"
        },
        {NULL}  /* Sentinel */
    };

    static PyTypeObject NoddyType = {
        PyObject_HEAD_INIT(NULL)
        0,                         /*ob_size*/
        "noddy.Noddy",             /*tp_name*/
        sizeof(Noddy),             /*tp_basicsize*/
        0,                         /*tp_itemsize*/
        (destructor)Noddy_dealloc, /*tp_dealloc*/
        0,                         /*tp_print*/
        0,                         /*tp_getattr*/
        0,                         /*tp_setattr*/
        0,                         /*tp_compare*/
        0,                         /*tp_repr*/
        0,                         /*tp_as_number*/
        0,                         /*tp_as_sequence*/
        0,                         /*tp_as_mapping*/
        0,                         /*tp_hash */
        0,                         /*tp_call*/
        0,                         /*tp_str*/
        0,                         /*tp_getattro*/
        0,                         /*tp_setattro*/
        0,                         /*tp_as_buffer*/
        Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC, /*tp_flags*/
        "Noddy objects",           /* tp_doc */
        (traverseproc)Noddy_traverse,   /* tp_traverse */
        (inquiry)Noddy_clear,           /* tp_clear */
        0,		               /* tp_richcompare */
        0,		               /* tp_weaklistoffset */
        0,		               /* tp_iter */
        0,		               /* tp_iternext */
        Noddy_methods,             /* tp_methods */
        Noddy_members,             /* tp_members */
        0,                         /* tp_getset */
        0,                         /* tp_base */
        0,                         /* tp_dict */
        0,                         /* tp_descr_get */
        0,                         /* tp_descr_set */
        0,                         /* tp_dictoffset */
        (initproc)Noddy_init,      /* tp_init */
        0,                         /* tp_alloc */
        Noddy_new,                 /* tp_new */
    };

    static PyMethodDef module_methods[] = {
        {NULL}  /* Sentinel */
    };

    #ifndef PyMODINIT_FUNC	/* declarations for DLL import/export */
    #define PyMODINIT_FUNC void
    #endif
    PyMODINIT_FUNC
    initnoddy4(void)
    {
        PyObject* m;

        if (PyType_Ready(&NoddyType) < 0)
            return;

        m = Py_InitModule3("noddy4", module_methods,
                           "Example module that creates an extension type.");

        if (m == NULL)
          return;

        Py_INCREF(&NoddyType);
        PyModule_AddObject(m, "Noddy", (PyObject *)&NoddyType);
    }

The traversal method provides access to subobjects that could participate in cycles:

    static int
    Noddy_traverse(Noddy *self, visitproc visit, void *arg)
    {
        int vret;

        if (self->first) {
            vret = visit(self->first, arg);
            if (vret != 0)
                return vret;
        }
        if (self->last) {
            vret = visit(self->last, arg);
            if (vret != 0)
                return vret;
        }

        return 0;
    }

For each subobject that can participate in cycles, we need to call the `visit()` function, which is passed to the traversal method. The `visit()` function takes as arguments the subobject and the extra argument arg passed to the traversal method. It returns an integer value that must be returned if it is non-zero.

Python 2.4 and higher provide a `Py_VISIT()` macro that automates calling visit functions. With `Py_VISIT()`, `Noddy_traverse()` can be simplified:

    static int
    Noddy_traverse(Noddy *self, visitproc visit, void *arg)
    {
        Py_VISIT(self->first);
        Py_VISIT(self->last);
        return 0;
    }

Note: Note that the `tp_traverse` implementation must name its arguments exactly visit and arg in order to use `Py_VISIT()`. This is to encourage uniformity across these boring implementations.

We also need to provide a method for clearing any subobjects that can participate in cycles. We implement the method and reimplement the deallocator to use it:

    static int
    Noddy_clear(Noddy *self)
    {
        PyObject *tmp;

        tmp = self->first;
        self->first = NULL;
        Py_XDECREF(tmp);

        tmp = self->last;
        self->last = NULL;
        Py_XDECREF(tmp);

        return 0;
    }

    static void
    Noddy_dealloc(Noddy* self)
    {
        Noddy_clear(self);
        self->ob_type->tp_free((PyObject*)self);
    }

Notice the use of a temporary variable in `Noddy_clear()`. We use the temporary variable so that we can set each member to `NULL` before decrementing its reference count. We do this because, as was discussed earlier, if the reference count drops to zero, we might cause code to run that calls back into the object. In addition, because we now support garbage collection, we also have to worry about code being run that triggers garbage collection. If garbage collection is run, our `tp_traverse` handler could get called. We can't take a chance of having `Noddy_traverse()` called when a member's reference count has dropped to zero and its value hasn't been set to `NULL`.

Python 2.4 and higher provide a `Py_CLEAR()` that automates the careful decrementing of reference counts. With `Py_CLEAR()`, the `Noddy_clear()` function can be simplified:

    static int
    Noddy_clear(Noddy *self)
    {
        Py_CLEAR(self->first);
        Py_CLEAR(self->last);
        return 0;
    }

Finally, we add the `Py_TPFLAGS_HAVE_GC` flag to the class flags:

        Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC, /*tp_flags*/

That's pretty much it. If we had written custom `tp_alloc` or `tp_free` slots, we'd need to modify them for cyclic-garbage collection. Most extensions will use the versions automatically provided.

#### Footnotes

... attributes.2.4
  Even in the third version, we aren't guaranteed to avoid cycles. Instances of string subclasses are allowed and string subclasses could allow cycles even if normal strings don't.