Size ptr tuple (#10846)

* fixes #10117
* Add support for recursive tuples
* detect in generics

8 files changed, 153 insertions, 10 deletions

diff --git a/compiler/semtypes.nim b/compiler/semtypes.nim
index 52b236883..6996082c3 100644
--- a/compiler/semtypes.nim
+++ b/compiler/semtypes.nim
@@ -448,6 +448,10 @@ proc semTuple(c: PContext, n: PNode, prev: PType): PType =
       styleCheckDef(c.config, a.sons[j].info, field)
       onDef(field.info, field)
   if result.n.len == 0: result.n = nil
+  if isTupleRecursive(result):
+    localError(c.config, n.info, errIllegalRecursionInTypeX % typeToString(result))
+
+
 
 proc semIdentVis(c: PContext, kind: TSymKind, n: PNode,
                  allowed: TSymFlags): PSym =
diff --git a/compiler/semtypinst.nim b/compiler/semtypinst.nim
index 152a75ee3..9203f6437 100644
--- a/compiler/semtypinst.nim
+++ b/compiler/semtypinst.nim
@@ -24,7 +24,7 @@ proc checkConstructedType*(conf: ConfigRef; info: TLineInfo, typ: PType) =
   if t.kind in tyTypeClasses: discard
   elif t.kind in {tyVar, tyLent} and t.sons[0].kind in {tyVar, tyLent}:
     localError(conf, info, "type 'var var' is not allowed")
-  elif computeSize(conf, t) == szIllegalRecursion:
+  elif computeSize(conf, t) == szIllegalRecursion or isTupleRecursive(t):
     localError(conf, info,  "illegal recursion in type '" & typeToString(t) & "'")
   when false:
     if t.kind == tyObject and t.sons[0] != nil:
@@ -682,4 +682,3 @@ proc prepareMetatypeForSigmatch*(p: PContext, pt: TIdTable, info: TLineInfo,
 template generateTypeInstance*(p: PContext, pt: TIdTable, arg: PNode,
                                t: PType): untyped =
   generateTypeInstance(p, pt, arg.info, t)
-
diff --git a/compiler/sizealignoffsetimpl.nim b/compiler/sizealignoffsetimpl.nim
index af2f0ad40..665f4b1ab 100644
--- a/compiler/sizealignoffsetimpl.nim
+++ b/compiler/sizealignoffsetimpl.nim
@@ -272,14 +272,6 @@ proc computeSizeAlign(conf: ConfigRef; typ: PType) =
       typ.align = szIllegalRecursion
       return
 
-    # recursive tuplers are not allowed and should be detected in the frontend
-    if base.kind == tyTuple:
-      computeSizeAlign(conf, base)
-      if base.size < 0:
-        typ.size = base.size
-        typ.align = base.align
-        return
-
     typ.align = int16(conf.target.ptrSize)
     if typ.kind == tySequence and conf.selectedGC == gcDestructors:
       typ.size = conf.target.ptrSize * 2
diff --git a/compiler/types.nim b/compiler/types.nim
index ddd299a86..069d663ac 100644
--- a/compiler/types.nim
+++ b/compiler/types.nim
@@ -1514,3 +1514,23 @@ proc typeMismatch*(conf: ConfigRef; info: TLineInfo, formal, actual: PType) =
       of efLockLevelsDiffer:
         msg.add "\nlock levels differ"
     localError(conf, info, msg)
+
+proc isTupleRecursive(t: PType, cycleDetector: var IntSet): bool =
+  if t == nil: return
+  case t.kind:
+    of tyTuple:
+      if cycleDetector.containsOrIncl(t.id):
+        return true
+      var cycleDetectorCopy: IntSet
+      for i in  0..<t.len:
+        assign(cycleDetectorCopy, cycleDetector)
+        if isTupleRecursive(t[i], cycleDetectorCopy):
+          return true
+    of tyAlias, tyRef, tyPtr, tyGenericInst, tyVar, tyLent, tySink, tyArray, tyUncheckedArray, tySequence:
+      return isTupleRecursive(t.lastSon, cycleDetector)
+    else:
+      discard
+
+proc isTupleRecursive*(t: PType): bool =
+  var cycleDetector = initIntSet()
+  isTupleRecursive(t, cycleDetector)
diff --git a/tests/destructor/smart_ptr.nim b/tests/destructor/smart_ptr.nim
new file mode 100644
index 000000000..7c3141d22
--- /dev/null
+++ b/tests/destructor/smart_ptr.nim
@@ -0,0 +1,49 @@
+
+type
+  SharedPtr*[T] = object
+    val: ptr tuple[atomicCounter: int, value: T]
+
+proc `=destroy`*[T](p: var SharedPtr[T]) =
+  mixin `=destroy`
+  if p.val != nil:
+    let c = atomicDec(p.val[].atomicCounter)
+    if c == 0:
+      `=destroy`(p.val.value)
+      freeShared(p.val)
+    p.val = nil
+
+proc `=`*[T](dest: var SharedPtr[T], src: SharedPtr[T]) {.inline.} =
+  if dest.val != src.val:
+    if dest.val != nil:
+      `=destroy`(dest)
+    if src.val != nil:
+      discard atomicInc(src.val[].atomicCounter)
+    dest.val = src.val
+
+proc `=sink`*[T](dest: var SharedPtr[T], src: SharedPtr[T]) {.inline.} =
+  if dest.val != src.val:
+    if dest.val != nil:
+      `=destroy`(dest)
+    dest.val = src.val
+
+proc newSharedPtr*[T](val: sink T): SharedPtr[T] =
+  result.val = cast[type(result.val)](allocShared0(sizeof(result.val[])))
+  result.val.atomicCounter = 1
+  result.val.value = val
+
+func get*[T](p: SharedPtr[T]): var T {.inline.} =
+  p.val.value
+
+func isNil*[T](p: SharedPtr[T]): bool {.inline.} =
+  p.val == nil
+
+proc cas*[T](p, old_val: var SharedPtr[T], new_val: SharedPtr[T]): bool {.inline.} =
+  if old_val.val == new_val.val:
+    result = true
+  else:
+    result = cas(p.val.addr, old_val.val, new_val.val)
+    if result:
+      `=destroy`(old_val)
+      if new_val.val != nil:
+        discard atomicInc(new_val.val[].atomicCounter)
+
diff --git a/tests/destructor/trecursive.nim b/tests/destructor/trecursive.nim
new file mode 100644
index 000000000..55e67f52a
--- /dev/null
+++ b/tests/destructor/trecursive.nim
@@ -0,0 +1,34 @@
+
+discard """
+   output: '''
+test1 OK
+'''
+"""
+
+import smart_ptr
+
+type
+  Node[T] = object
+    value: T
+    next: SharedPtr[Node[T]]
+
+  ForwardList[T] = object
+    first: SharedPtr[Node[T]]
+    len: Natural
+
+proc pushFront*[T] (list: var ForwardList[T], val: sink T) =
+  var newNode = newSharedPtr(Node[T](value: val))
+  var result = false
+  while not result:
+    var head = list.first
+    newNode.get.next = head
+    result = list.first.cas(head, newNode)
+  list.len.atomicInc()
+
+proc test1() =
+  var list: ForwardList[int]
+  list.pushFront(1)
+  doAssert list.len == 1
+  echo "test1 OK"
+
+test1()
diff --git a/tests/types/tillegaltuplerecursion.nim b/tests/types/tillegaltuplerecursion.nim
new file mode 100644
index 000000000..c822e8880
--- /dev/null
+++ b/tests/types/tillegaltuplerecursion.nim
@@ -0,0 +1,38 @@
+discard """
+  errormsg: "illegal recursion in type"
+"""
+
+# This is one big illegal type cycle. It doesn't really matter at
+# what line the error is reported, nor what name is picked to point
+# out the illegal recursion.
+
+type
+  MyType0 = ref tuple
+    children: MyType1
+
+  MyType1 = ref tuple
+    children: array[10, MyType2]
+
+  MyType2 = ref tuple
+    children: seq[MyType3]
+
+  MyType3 = ref tuple
+    children: UncheckedArray[MyType4]
+
+  MyType4 = ref tuple
+    children: MyType5
+
+  MyType5 = tuple
+    children: array[10, MyType6]
+
+  MyType6 = tuple
+    children: seq[MyType7]
+
+  MyType7 = tuple
+    children: UncheckedArray[MyType8]
+
+  MyType8 = tuple
+    children: ptr MyType9
+
+  MyType9 = tuple
+    children: MyType0
diff --git a/tests/types/tillegaltuplerecursiongeneric.nim b/tests/types/tillegaltuplerecursiongeneric.nim
new file mode 100644
index 000000000..e5191e4d7
--- /dev/null
+++ b/tests/types/tillegaltuplerecursiongeneric.nim
@@ -0,0 +1,7 @@
+discard """
+  errormsg: "illegal recursion in type 'RefTreeInt'"
+"""
+
+type
+  RefTree[T] = ref tuple[le, ri: RefTree[T]; data: T]
+  RefTreeInt = RefTree[int]