[Tim]
How do we know which other objects they refer to?
[Neil Schemenauer]
We call tp_traverse on them.
We just went thru this for tuples, right? PyTuple_New returns a tracked tuple T all of whose data slots are NULL. If tupletraverse(T, visit, arg) is called when T is in this state, tupletraverse will never call visit. And, AFAICT, whether or not the visit() function is called is the only information you can get out of calling tp_traverse. In which case, calling tp_traverse will tell you if a tuple *does* point to a gcable object, but tells you nothing about the tuple if visit doesn't get called, only that the tuple doesn't currently happen to point to anything interesting (but well may if you try again later). IOW, "immutable" isn't a truthful description of tuples at this level; tuples are all but guaranteed to mutate after they become tracked, and knowing when a tuple has undergone its final under-the-covers mutation requires exact knowledge of how tuples are layed out and used. s/tuple/xyzobject/g.
How do we know that the set of objects they refer to will never change?
The assumption is that if the object doesn't have tp_clear then it's immutable. That's a little risky I guess.
Seems likely, yes.