Recursive tuples: what do they break?

Python Help
1

A list can easily contain itself.

lst = []
lst.append(lst)

A tuple cannot… normally.

import ctypes
tup = (None,)
ctypes.cast(id(tup), ctypes.POINTER(ctypes.c_long))[3] = id(tup)

Since you can’t generally have a tuple contain itself, some things assume that this can’t happen. So, what breaks? Actually, not all that much. Most things either don’t recurse, or guard properly against infinite recursion (usually because they handle lists and tuples the same way - eg json.dumps() and repr()). I’ve found two things that break, plus one that only breaks in Python 2.7 (IMO that doesn’t really count):

>>> isinstance("spam", tup)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded in __instancecheck__
>>> pickle.dumps(tup)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded while pickling an object
>>> print(tup)
((...),)

In Python 2, that last one printed out a huge number of open parentheses and then segfaulted. In every Py3 version that I have here (back as far as 3.3), this correctly reports the recursion.

So! What do you know of that special-cases tuples, and can it be busted with this? One point if it raises an unexpected exception, two points if it gets stuck or segfaults.

2

Well, if I have two of them, comparison recurse:

>>> tup2 = (None,)
>>> ctypes.cast(id(tup2), ctypes.POINTER(ctypes.c_long))[3] = id(tup2)
>>> tup == tup2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded in comparison

(but that also happens with lists, so I don’t know if it counts):

>>> lst2 = []
>>> lst2.append(lst)
>>> lst == lst2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded in comparison

However here’s a crash:

>>> hash(tup)
zsh: segmentation fault  python

(and thus it crash also when putting tup into a set or dict!)

3

I got curious and tried with collections.namedtuple and the that’s even worse:

import collections, ctypes
NT = colletions.namedtuple("NT", "x")
tup = NT(None)
ctypes.cast(id(tup), ctypes.POINTER(ctypes.c_long))[3] = id(tup)

>>> repr(tup)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File ".../lib/python3.11/collections/__init__.py", line 461, in __repr__
    return self.__class__.__name__ + repr_fmt % self
                                     ~~~~~~~~~^~~~~~
  File ".../lib/python3.11/collections/__init__.py", line 461, in __repr__
    return self.__class__.__name__ + repr_fmt % self
                                     ~~~~~~~~~^~~~~~
  File ".../lib/python3.11/collections/__init__.py", line 461, in __repr__
    return self.__class__.__name__ + repr_fmt % self
                                     ~~~~~~~~~^~~~~~
  [Previous line repeated 496 more times]
RecursionError: maximum recursion depth exceeded while getting the repr of an object
4

Yeah, a lot of things are like that - they error out on ANY recursive structure, so it’s nothing special about recursive tuples.

Oooh, that’s a good one! Can confirm, hashing a recursive tuple segfaults.

5

Is this just for fun, or are you considering developing an issue?

6

If I get enough tuits, I’ll look into fixing the hash issue, since that one might be worth the effort. The others aren’t.

The main reason for asking was that, over on python-list (it’s not dead yet folks, come back Thursday), we were having a discussion about why tuples and not arbitrary iterables were accepted in various places. I put the explanation that they can’t be self-referential, so recursive descent of tuples can safely be assumed to terminate, and then sought examples where this was the case. Which I guess means that the details are really just for fun.

(Sadly, this Discourse doesn’t have a section for fun, and Python Help is the best we have. Which makes some threads seem a little out of place.)

7

You wanted help to have some fun, and possibly do an issue. Sounds good to me ;-).

2 Likes
8

This implies that given a little ctypes shenanigans, even tuples aren’t really constant, right ? Wouldn’t that break some expectations even aside from recursivity ?

For example some system could expect ints, strings and tuples to be constant and share them between threads or processes without checking anything, and that apparently would be an incorrect assumption.
It’s often said that no container, even frozen dataclasses, is truly constant except tuples, hence most uses of namedtuple, but if even they aren’t… :frowning:

9

Well, yes, but unless you have some sort of memory protection, nothing is constant. With ctypes, you can change the value of 17 to be 19. So I’m sure you could do other things like breaking hashes; that’s not really surprising.

However, that aside, it’s still possible to make a recursive tuple using the C API, without violating the normal rules of constancy. That’s because tuples are created with just a length, and then you populate the elements; nothing’s stopping you from using the newly-created tuple as part of itself.