Repository: numba/numba

Issue:
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..
 

Discussion:

Patch:
diff --git a/numba/core/datamodel/models.py b/numba/core/datamodel/models.py
index 77b2fc90a..0d06c560d 100644
--- a/numba/core/datamodel/models.py
+++ b/numba/core/datamodel/models.py
@@ -1,4 +1,5 @@
 from functools import partial
+from collections import deque
 
 from llvmlite import ir
 
@@ -103,11 +104,21 @@ class DataModel(object):
         """
         Recursively list all frontend types involved in this model.
         """
-        return [self._fe_type] + self.inner_types()
+        types = [self._fe_type]
+        queue = deque([self])
+        while len(queue) > 0:
+            dm = queue.popleft()
 
-    def inner_types(self):
+            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)
+
+        return types
+
+    def inner_models(self):
         """
-        List all *inner* frontend types.
+        List all *inner* models.
         """
         return []
 
@@ -326,8 +337,8 @@ class OpaqueModel(PrimitiveModel):
 @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 +496,8 @@ class UniTupleModel(DataModel):
         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 +711,8 @@ class StructModel(CompositeModel):
 
         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)


Test patch:
diff --git a/numba/tests/test_struct_ref.py b/numba/tests/test_struct_ref.py
index 8bcc3219a..b358ff29d 100644
--- a/numba/tests/test_struct_ref.py
+++ b/numba/tests/test_struct_ref.py
@@ -317,3 +317,112 @@ class TestStructRefCaching(MemoryLeakMixin, TestCase):
 
         check(cached=False)
         check(cached=True)
+
+
+@structref.register
+class PolygonStructType(types.StructRef):
+
+    def preprocess_fields(self, fields):
+        # temp name to allow Optional instantiation
+        self.name = f"numba.PolygonStructType#{id(self)}"
+        fields = tuple([
+            ('value', types.Optional(types.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 _ol_polygon_struct_flip(self):
+    def impl(self):
+        if self.value is not None:
+            self.value = -self.value
+    return impl
+
+
+@overload_attribute(PolygonStructType, "prop")
+def _ol_polygon_struct_prop(self):
+    def get(self):
+        return self.value, self.parent
+    return get
+
+
+class TestStructRefForwardTyping(MemoryLeakMixin, TestCase):
+    def test_same_type_assignment(self):
+        @njit
+        def check(x):
+            poly = PolygonStruct(None, None)
+            p_poly = PolygonStruct(None, None)
+            poly.value = x
+            poly.parent = p_poly
+            p_poly.value = x
+            return poly.parent.value
+
+        x = 11
+        got = check(x)
+        expect = x
+        self.assertPreciseEqual(got, expect)
+
+    def test_overload_method(self):
+        @njit
+        def check(x):
+            poly = PolygonStruct(None, None)
+            p_poly = PolygonStruct(None, None)
+            poly.value = x
+            poly.parent = p_poly
+            p_poly.value = x
+            poly.flip()
+            poly.parent.flip()
+            return poly.parent.value
+
+        x = 3
+        got = check(x)
+        expect = -x
+        self.assertPreciseEqual(got, expect)
+
+    def test_overload_attribute(self):
+        @njit
+        def check():
+            obj = PolygonStruct(5, None)
+            return obj.prop[0]
+
+        got = check()
+        expect = 5
+        self.assertPreciseEqual(got, expect)