Creando tuplas autorreferenciadas

Question

Después de ver una conversación en un foro de hace muchos años que nunca se resolvió, me hizo preguntarme cómo se crearía correctamente una tupla que se refiriera a sí misma. Técnicamente, esta es una muy mala idea ya que se supone que las tuplas son inmutables. ¿Cómo podría contenerse un objeto inmutable? Sin embargo, esta pregunta no se trata de las mejores prácticas, sino que es una consulta sobre lo que es posible en 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') 

La función anterior se diseñó para acceder a la API C de Python, manteniendo las estructuras internas y tipos de datos en mente. Sin embargo, el siguiente error generalmente se genera cuando se ejecuta la función. A través de procesos desconocidos, ha sido posible crear una tupla autorreferencial mediante técnicas similares anteriormente.

Pregunta: ¿Cómo se debe modificar la función self_reference para que funcione constantemente todo el tiempo?

>>> 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 
>>> 

Editar: Éstos son dos conversaciones diferentes con el intérprete que son un tanto confuso. El código anterior parece ser correcto si entiendo la documentación correctamente. Sin embargo, las conversaciones de abajo parecen estar en conflicto entre sí y la función self_reference arriba.

Conversación 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) 
>>> 

Conversación 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 
>>> 

Answer 1

Gracias a la ayuda de nneonneo, me decidí por la siguiente implementación del método 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() 

Para utilizar el método, siga el ejemplo que se muestra abajo para crear sus propias tuplas de autorreferencia.

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

Answer 2

AFAICT, la razón por la que está viendo se debe a problemas PyTuple_SetItem falla si el refcount de la tupla no es exactamente uno. Esto es para evitar que se use la función si la tupla ya se ha utilizado en otro lugar. No estoy seguro de por qué se produce una infracción de acceso a eso, pero puede deberse a que la excepción emitida por PyTuple_SetItem no se trata adecuadamente. Además, la razón por la cual la matriz parece mutar a algún otro objeto es porque PyTuple_SetItem DECREF es la tupla en cada falla; después de dos fallas, el refcount es cero por lo que el objeto se libera (y algún otro objeto aparentemente termina en la misma ubicación de memoria).

El uso del objeto pythonapi en ctypes es la forma preferida de obtener acceso a la DLL de Python, ya que maneja las excepciones de Python correctamente y se garantiza que utiliza la convención de llamada correcta.

no tengo una máquina Windows a mano para probar esto, pero el siguiente trabaja muy bien en Mac OS X (tanto Python 2.7.3 y 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) 

Resultado:

>>> 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) 

Answer 3

Técnicamente, podría envolver la referencia a la tupla dentro de un objeto mutable.

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

Answer 4

La inmutabilidad no debe evitar que un objeto se refiera a sí mismo. Esto es fácil de hacer en Haskell porque tiene una evaluación perezosa.Aquí es una imitación que hace que usando un golpe seco:

>>> 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 

Ésta no es una respuesta completa, simplemente preliminar. Estoy trabajando para ver si hay otra manera de hacer esto posible.