构建自引用元组

Question

在看到几年前从未解决的论坛对话后，我想知道如何正确创建引用自身的元组。从技术上讲，这是一个非常糟糕的想法，因为元组应该是不可变的。一个不可变的对象怎么可能包含它自己呢？然而，这个问题不是关于最佳实践，而是关于 Python 中可能性的查询。

import ctypes

def self_reference(array, index):
    if not isinstance(array, tuple):
        raise TypeError('array must be a tuple')
    if not isinstance(index, int):
        raise TypeError('index must be an int')
    if not 0 <= index < len(array):
        raise ValueError('index is out of range')
    address = id(array)
    obj_refcnt = ctypes.cast(address, ctypes.POINTER(ctypes.c_ssize_t))
    obj_refcnt.contents.value += 1
    if ctypes.cdll.python32.PyTuple_SetItem(ctypes.py_object(array),
                                            ctypes.c_ssize_t(index),
                                            ctypes.py_object(array)):
        raise RuntimeError('PyTuple_SetItem signaled an error')

前面的函数是为了访问Python的C API，同时考虑到内部结构和数据类型而设计的。然而，当运行该函数时，通常会生成以下错误。通过未知的过程，之前已经可以使用类似的技术创建一个自引用元组。

问题：应如何修改self_reference函数以始终正常工作？

>>> import string
>>> a = tuple(string.ascii_lowercase)
>>> self_reference(a, 2)
Traceback (most recent call last):
  File "<pyshell#56>", line 1, in <module>
    self_reference(a, 2)
  File "C:/Users/schappell/Downloads/srt.py", line 15, in self_reference
    ctypes.py_object(array)):
WindowsError: exception: access violation reading 0x0000003C
>>> 

编辑：这里有两个跟解释器有关的对话，有些令人困惑。如果我正确理解了文档，上面的代码似乎是正确的。然而，在下面的对话中，似乎彼此之间以及上面的self_reference函数都存在冲突。

对话1：

Python 3.2.3 (default, Apr 11 2012, 07:15:24) [MSC v.1500 32 bit (Intel)]
on win32
Type "copyright", "credits" or "license()" for more information.
>>> from ctypes import *
>>> array = tuple(range(10))
>>> cast(id(array), POINTER(c_ssize_t)).contents.value
1
>>> cast(id(array), POINTER(c_ssize_t)).contents.value += 1
>>> cast(id(array), POINTER(c_ssize_t)).contents.value
2
>>> array
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> cdll.python32.PyTuple_SetItem(c_void_p(id(array)), 0,
                                  c_void_p(id(array)))
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    cdll.python32.PyTuple_SetItem(c_void_p(id(array)), 0,
                                  c_void_p(id(array)))
WindowsError: exception: access violation reading 0x0000003C
>>> cdll.python32.PyTuple_SetItem(c_void_p(id(array)), 0,
                                  c_void_p(id(array)))
Traceback (most recent call last):
  File "<pyshell#7>", line 1, in <module>
    cdll.python32.PyTuple_SetItem(c_void_p(id(array)), 0,
                                  c_void_p(id(array)))
WindowsError: exception: access violation reading 0x0000003C
>>> array
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> cdll.python32.PyTuple_SetItem(c_void_p(id(array)), 0,
                                  c_void_p(id(array)))
0
>>> array
((<NULL>, <code object __init__ at 0x02E68C50, file "C:\Python32\lib
kinter\simpledialog.py", line 121>, <code object destroy at 0x02E68CF0,
file "C:\Python32\lib   kinter\simpledialog.py", line 171>, <code object
body at 0x02E68D90, file "C:\Python32\lib      kinter\simpledialog.py",
line 179>, <code object buttonbox at 0x02E68E30, file "C:\Python32\lib
kinter\simpledialog.py", line 188>, <code object ok at 0x02E68ED0, file
"C:\Python32\lib        kinter\simpledialog.py", line 209>, <code object
cancel at 0x02E68F70, file "C:\Python32\lib    kinter\simpledialog.py",
line 223>, <code object validate at 0x02E6F070, file "C:\Python32\lib
kinter\simpledialog.py", line 233>, <code object apply at 0x02E6F110, file
"C:\Python32\lib     kinter\simpledialog.py", line 242>, None), 1, 2, 3, 4,
5, 6, 7, 8, 9)
>>>

对话2：

Python 3.2.3 (default, Apr 11 2012, 07:15:24) [MSC v.1500 32 bit (Intel)]
on win32
Type "copyright", "credits" or "license()" for more information.
>>> from ctypes import *
>>> array = tuple(range(10))
>>> cdll.python32.PyTuple_SetItem(c_void_p(id(array)), c_ssize_t(1),
                                  c_void_p(id(array)))
0
>>> array
(0, (...), 2, 3, 4, 5, 6, 7, 8, 9)
>>> array[1] is array
True
>>>

- Noctis Skytower

---

它至少在哪个Python版本中运行过一次？ - jsbueno

编辑显示Python在IDLE中的版本。另外，这是否意味着它实际上是一台64位计算机？ - Noctis Skytower

我猜在C语言层面上，元组并不是不可变的。 - Claudiu

从技术上讲，在C级别上没有什么是不可变的（除了只读内存区域......）。例如，将Python字符串（Python中的不可变构造）传递给修改其输入的C函数将修改该字符串。虽然这通常是个坏主意，因为它可能会导致一个interned字符串改变值，但仍然是可能的。 - nneonneo

有趣的是，文档明确声明这是不可能的: "可以证明没有引用循环可以完全由元组组成。" - Hood

Answer 1

由于nneonneo的帮助，我最终采用了以下实现方式来完成self_reference方法。

import ctypes

ob_refcnt_p = ctypes.POINTER(ctypes.c_ssize_t)

class GIL:
    acquire = staticmethod(ctypes.pythonapi.PyGILState_Ensure)
    release = staticmethod(ctypes.pythonapi.PyGILState_Release)

class Ref:
    dec = staticmethod(ctypes.pythonapi.Py_DecRef)
    inc = staticmethod(ctypes.pythonapi.Py_IncRef)

class Tuple:
    setitem = staticmethod(ctypes.pythonapi.PyTuple_SetItem)
    @classmethod
    def self_reference(cls, array, index):
        if not isinstance(array, tuple):
            raise TypeError('array must be a tuple')
        if not isinstance(index, int):
            raise TypeError('index must be an int')
        if not 0 <= index < len(array):
            raise ValueError('index is out of range')
        GIL.acquire()
        try:
            obj = ctypes.py_object(array)
            ob_refcnt = ctypes.cast(id(array), ob_refcnt_p).contents.value
            for _ in range(ob_refcnt - 1):
                Ref.dec(obj)
            if cls.setitem(obj, ctypes.c_ssize_t(index), obj):
                raise SystemError('PyTuple_SetItem was not successful')
            for _ in range(ob_refcnt):
                Ref.inc(obj)
        finally:
            GIL.release()

要使用这个方法，请按照下面的示例创建自己的自引用元组。

>>> array = tuple(range(5))
>>> Tuple.self_reference(array, 1)
>>> array
(0, (...), 2, 3, 4)
>>> Tuple.self_reference(array, 3)
>>> array
(0, (...), 2, (...), 4)
>>> 

- Noctis Skytower

Answer 2

据我所知，您看到问题的原因是因为如果元组的引用计数不恰好为一，则PyTuple_SetItem失败。这是为了防止在元组已经在其他地方使用时使用该函数。我不确定您为什么会从中得到访问冲突，但可能是因为PyTuple_SetItem抛出的异常没有得到正确处理。此外，数组似乎变异为某些其他对象的原因是因为PyTuple_SetItem在每次失败时都会对元组进行DECREF；经过两次失败后，引用计数为零，因此对象被释放（并且某些其他对象显然出现在相同的内存位置）。

在ctypes中使用pythonapi对象是获取Python DLL访问权限的首选方式，因为它可以正确处理Python异常，并保证使用正确的调用约定。

我手头没有Windows机器来测试这个问题，但在Mac OS X上（Python 2.7.3和3.2.2），以下内容运行良好：

import ctypes

def self_reference(array, index):
    # Sanity check. We can't let PyTuple_SetItem fail, or it will Py_DECREF
    # the object and destroy it.
    if not isinstance(array, tuple):
        raise TypeError("array must be a tuple")

    if not 0 <= index < len(array):
        raise IndexError("tuple assignment index out of range")

    arrayobj = ctypes.py_object(array)

    # Need to drop the refcount to 1 in order to use PyTuple_SetItem.
    # Needless to say, this is incredibly dangerous.
    refcnt = ctypes.pythonapi.Py_DecRef(arrayobj)
    for i in range(refcnt-1):
        ctypes.pythonapi.Py_DecRef(arrayobj)

    try:
        ret = ctypes.pythonapi.PyTuple_SetItem(arrayobj, ctypes.c_ssize_t(index), arrayobj)
        if ret != 0:
            raise RuntimeError("PyTuple_SetItem failed")
    except:
        raise SystemError("FATAL: PyTuple_SetItem failed: tuple probably unusable")

    # Restore refcount and add one more for the new self-reference
    for i in range(refcnt+1):
        ctypes.pythonapi.Py_IncRef(arrayobj)

结果：

>>> x = (1,2,3,4,5)
>>> self_reference(x, 1)
>>> import pprint
>>> pprint.pprint(x)
(1, <Recursion on tuple with id=4299516720>, 3, 4, 5)

- nneonneo

---

非常感谢您的帮助！我将我们的工作合并为一个答案。ctypes.pythonapi.Py_DecRef(arrayobj)返回的是对象的地址而不是引用计数，所以我修改了代码手动获取数字。您的见解确实有助于得到问题的答案。 - Noctis Skytower

是的，我的错。Py_DecRef和Py_IncRef返回void，所以您必须从对象结构中提取refcount。 - nneonneo

我提供的答案在你的平台上可行吗？我只在Windows上测试过。 - Noctis Skytower

Answer 3

更简单的解决方案：

import ctypes
tup = (0,)
ctypes.c_longlong.from_address(id(tup)+24).value = id(tup)

结果：

>>> tup
((...),)
>>> type(tup)
tuple
>>> tup[0] is tup
True

- wim

Answer 4

不可变性不应该防止对象引用自身。在Haskell中很容易做到这一点，因为它具有惰性求值。以下是使用thunk实现此操作的模拟：

>>> def self_ref_tuple():
    a = (1, 2, lambda: a)
    return a

>>> ft = self_ref_tuple()
>>> ft
(1, 2, <function <lambda> at 0x02A7C330>)
>>> ft[2]()
(1, 2, <function <lambda> at 0x02A7C330>)
>>> ft[2]() is ft
True

这不是一个完整的答案，只是初步的想法。我正在努力寻找是否有其他方法使此成为可能。

- Claudiu

---

目标是要直接引用，而不是使用一个惰性计算函数。 - Noctis Skytower

Answer 5

从技术上讲，您可以将对元组的引用包装在可变对象中。

>>> c = ([],)
>>> c[0].append(c)
>>> c
([(...)],)
>>> c[0]
[([...],)]
>>> 

- Nick ODell

---

目标是要有一个直接的引用，而不使用另一个容器。 - Noctis Skytower