Repository: numba/numba
Pull request: Remove recursion from traverse_types

this is intended to fix #6180

Problem statement:
Type inference recursion error for self referencing types
I don't know if this should be labeled as a bug or missing feature, but is worth exposing it. Basicaly, here I am trying to self reference(forward declaration) a structref without using the undocumented DeferredType. 
<details><summary>example code</summary>

```
import numba as nb
from numba import jit, njit, types, typed, float64, int64, typeof
from numba.experimental import structref
from numba.core.extending import overload_method
from numba.experimental.structref import new, register

@structref.register
class PolygonStructType(types.StructRef):

    def preprocess_fields(self, fields):
        self.name = f"numba.PolygonStructType#{id(self)}" # temp name to allow Optional instantiation, this workaround can be replaced by extending StructRef or making StructRef to assign itself a name before preprocess_fields is called
        fields = tuple([
            ('value', types.Optional(int64)),
            ('parent', types.Optional(self)),
            ])

        return fields

polygon_struct_type = PolygonStructType(fields=(('value', types.Any), ('parent', types.Any)))

class PolygonStruct(structref.StructRefProxy):
    def __new__(cls, value, parent):
        return structref.StructRefProxy.__new__(cls, value, parent)

    @property
    def value(self):
        return PolygonStruct_get_value(self)

    @property
    def parent(self):
        return PolygonStruct_get_parent(self)

@njit
def PolygonStruct_get_value(self):
    return self.value

@njit
def PolygonStruct_get_parent(self):
    return self.parent

structref.define_proxy(PolygonStruct, PolygonStructType, ["value", "parent"])

@overload_method(PolygonStructType, "flip")
def PolygonStruct_flip(self):
    def impl(self):
        if self.value is not None:
            self.value = -self.value
    return impl

@njit
def test():
    # p = PolygonStruct(0, None)
    p = new(polygon_struct_type)
    p2 = new(polygon_struct_type)
    p2.value = 1
    p.parent = p2
    p.value = 3
    
    p.flip()
    return p.value

y = test()
print(y)
```
</details>

IMO, the usage of recursive algorithms in general is not recommended for production code.
And forward declaration for types is an essential feature in strong typed languages. There is no real workaround for it. I don't understand why numba does not have it already..

Hints from issue discussion:
Related #6077
I have a more complex example and in that one calling new(struct_type) and assigning values to parent attribute works. I have no idea why, probably because type inference kicks in at a later time and you don't end up in recursion error
When I execute this, the traceback is:

```
$ python repro.py 
Traceback (most recent call last):
  File "repro.py", line 75, in <module>
    y = test()
  File "/home/gmarkall/numbadev/numba/numba/core/dispatcher.py", line 414, in _compile_for_args
    error_rewrite(e, 'typing')
  File "/home/gmarkall/numbadev/numba/numba/core/dispatcher.py", line 357, in error_rewrite
    raise e.with_traceback(None)
numba.core.errors.TypingError: Failed in nopython mode pipeline (step: nopython frontend)
- Resolution failure for literal arguments:
No implementation of function Function(<function PolygonStruct_flip at 0x7f1d0e2c5430>) found for signature:

 >>> PolygonStruct_flip(numba.PolygonStructType(('value', OptionalType(int64)), ('parent', OptionalType(numba.PolygonStructType#139763134238832))))

There are 2 candidate implementations:
  - Of which 2 did not match due to:
  Overload in function 'PolygonStruct_flip': File: ../issues/6180/repro.py: Line 53.
    With argument(s): '(numba.PolygonStructType(('value', OptionalType(int64)), ('parent', OptionalType(numba.PolygonStructType#139763134238832))))':
   Rejected as the implementation raised a specific error:
     RecursionError: Failed in nopython mode pipeline (step: nopython mode backend)
   maximum recursion depth exceeded
  raised from /home/gmarkall/numbadev/numba/numba/core/datamodel/models.py:106

- Resolution failure for non-literal arguments:
None

During: resolving callee type: BoundFunction((<class '__main__.PolygonStructType'>, 'flip') for numba.PolygonStructType(('value', OptionalType(int64)), ('parent', OptionalType(numba.PolygonStructType#139763134238832))))
During: typing of call at repro.py (71)


File "repro.py", line 71:
def test():
    <source elided>

    p.flip()
```

My guess is that the type inference enters an infinite loop - perhaps @sklam can suggest a way forward here?

> I have a more complex example and in that one calling new(struct_type) and assigning values to parent attribute works. I have no idea why, probably because type inference kicks in at a later time and you don't end up in recursion error

Could you post the example where it does work without the recursion error please?
@gmarkall this is the code which kinda works

<details><summary>example code</summary>

```
import numba as nb
from numba import jit, njit, types, typed, float64, int64, typeof, gdb, gdb_init, gdb_breakpoint
from numba.core import types
from numba.experimental import structref
from numba.core.extending import overload_method
from numba.experimental.structref import new, register

@structref.register
class VectorStructType(types.StructRef):
    def preprocess_fields(self, fields):
        return tuple((name, types.unliteral(typ)) for name, typ in fields)

class VectorStruct(structref.StructRefProxy):
    def __new__(cls, x, y, z):
        return structref.StructRefProxy.__new__(cls, x, y, z)

    @property
    def x(self):
        return VectorStruct_get_x(self)

    @property
    def y(self):
        return VectorStruct_get_y(self)

    @property
    def z(self):
        return VectorStruct_get_z(self)

@njit
def VectorStruct_get_x(self):
    return self.x

@njit
def VectorStruct_get_y(self):
    return self.y

@njit
def VectorStruct_get_z(self):
    return self.z

structref.define_proxy(VectorStruct, VectorStructType, ["x", "y", "z"])

vector_struct_type = VectorStructType(fields=(('x', float64), ('y', float64),
                                              ('z', float64)))


@structref.register
class PolygonStructType(types.StructRef):
    def preprocess_fields(self, fields):
        self.name = f"numba.PolygonStructType#{id(self)}" # temp name to allow Optional instantiation   
        fields = tuple([
            ('vertices', types.Optional(types.ListType(vector_struct_type))),
            ('parent', types.Optional(self)),
            ])

        return fields

PolygonType_inst = PolygonStructType(fields=(('vertices', types.Any), ('parent', types.Any)))

class PolygonStruct(structref.StructRefProxy):
    def __new__(cls, vertices, parent):
        return structref.StructRefProxy.__new__(cls, vertices, parent)

    @property
    def vertices(self):
        return PolygonStruct_get_vertices(self)

    @property
    def parent(self):
        return PolygonStruct_get_parent(self)

@njit
def PolygonStruct_get_vertices(self):
    return self.vertices

@njit
def PolygonStruct_get_parent(self):
    return self.parent

structref.define_proxy(PolygonStruct, PolygonStructType, ["vertices", "parent"])

@overload_method(PolygonStructType, "flip")
def PolygonStruct_flip(self):
    # if self is PolygonType_inst:
    def impl(self):
        if self.vertices is not None:
            ref = self.vertices[0]
            ref.x = -ref.x
            ref.y = -ref.y
    return impl

@njit
def test():
    lst = typed.List.empty_list(vector_struct_type)
    lst.append(VectorStruct(1.0, 2.0, 3.0))

    print('before')
    
    p = new(PolygonType_inst)
    p2 = new(PolygonType_inst)
    print('after construct')
    p2.vertices = lst
    p.parent = p2
    p.vertices = lst
    
    # p.flip() doesn't work
    print('after')
    print(p.parent.vertices[0].y)
    return p.vertices[0].x

print('start')

y = test()

print(y)
print('end')
```
</details>

As I have said in my first post, proxy constructor and overload method does not work because type inference kicks in
the error you are seing comes from traverse_types() in models.py. that's where the inf recursion takes place

Commit message: remove recursion from traverse_types

Patch to review:
diff --git a/numba/core/datamodel/models.py b/numba/core/datamodel/models.py
index 77b2fc90a21..452e18ad0d3 100644
--- a/numba/core/datamodel/models.py
+++ b/numba/core/datamodel/models.py
@@ -103,11 +103,23 @@ def traverse_types(self):
         """
         Recursively list all frontend types involved in this model.
         """
-        return [self._fe_type] + self.inner_types()
+        types = [self._fe_type]
+        queue = [self]
+        while len(queue) > 0:
+            dm = queue[0]
+            queue.pop(0)
+            
+            for i_dm in dm.inner_models():
+                if i_dm._fe_type not in types:
+                    queue.append(i_dm)                    
+                    types.append(i_dm._fe_type)
 
-    def inner_types(self):
+        return types
+
+
+    def inner_models(self):
         """
-        List all *inner* frontend types.
+        List all *inner* models.
         """
         return []
 
@@ -326,8 +338,8 @@ def __init__(self, dmm, fe_type):
 @register_default(types.MemInfoPointer)
 class MemInfoModel(OpaqueModel):
 
-    def inner_types(self):
-        return self._dmm.lookup(self._fe_type.dtype).traverse_types()
+    def inner_models(self):
+        return [self._dmm.lookup(self._fe_type.dtype)]
 
     def has_nrt_meminfo(self):
         return True
@@ -485,8 +497,8 @@ def getter(i, value):
         return [(self._fe_type.dtype, partial(getter, i))
                 for i in range(self._count)]
 
-    def inner_types(self):
-        return self._elem_model.traverse_types()
+    def inner_models(self):
+        return [self._elem_model]
 
 
 class CompositeModel(DataModel):
@@ -700,11 +712,8 @@ def getter(k, value):
 
         return [(self.get_type(k), partial(getter, k)) for k in self._fields]
 
-    def inner_types(self):
-        types = []
-        for dm in self._models:
-            types += dm.traverse_types()
-        return types
+    def inner_models(self):
+        return self._models
 
 
 @register_default(types.Complex)


Code review comments:
diff_hunk: @@ -103,11 +103,23 @@ def traverse_types(self):
         """
         Recursively list all frontend types involved in this model.
         """
-        return [self._fe_type] + self.inner_types()
+        types = [self._fe_type]
+        queue = [self]
+        while len(queue) > 0:
+            dm = queue[0]
+            queue.pop(0)
path: numba/core/datamodel/models.py
text: @user1:
`list.pop(0)` is O(n). Use `collections.deque` instead of `list` for `queue` to be more efficient.