Self-referencing lists

Question

Say you do the following:

a = [1]
a[0] = a

You end up with a as equal to [[...]]. What's going on here? How does this implicitly defined infinite chain of a's referring to a's end up as [[...]]?

Answer 1

You ain't seen nothing:

>>> a = []
>>> a[:] = [a] * 4
>>> a
[[...], [...], [...], [...]]

If you're interested in how this works in CPython, see list_repr in listobject.c and similar functions. Basically, any function that potentially prints a self-referential object calls Py_ReprEnter on the object before printing it and Py_ReprLeave when it is done. (See object.c for the definitions of these functions.) The former checks to see if the object is found in a thread-local stack of objects that are currently being printed (and if not, pushes it); the latter pops the object from the stack. So if Python is printing a list and discovers that the list is on the stack, that must mean that this is a self-referential list, and the list should be abbreviated, to avoid an infinite loop:

 i = Py_ReprEnter((PyObject*)v);
 if (i != 0) {
     return i > 0 ? PyString_FromString("[...]") : NULL;
 }

 // ...

 Py_ReprLeave((PyObject *)v);
 return result;

Answer 2

The list contains a reference to itself. The [[...]] is how this is rendered when you print the list.

The implementation goes out of its way to ensure it doesn't end up in an infinite recursion. It does this by rendering references to objects that are already being printed as [...].

This makes it work with indirect self-references too:

>>> a = []
>>> b = [a]
>>> a.append(b)
>>> a
[[[...]]]
>>> b
[[[...]]]

If you are really curious, you could study CPython's source code. In Python 2.7.3, the relevant code is located in Objects/listobject.c.