bring #21802 back; fixes #21753 [backport] (#21815)

* bring #21802 back; fixes #21753 [backport]

* adds tests and multiple fixes

* add test cases

* refactor and remove startId

* fixes custom hooks and adds tests

* handle tyUncheckedArray better

7 files changed, 174 insertions, 26 deletions

diff --git a/compiler/ccgexprs.nim b/compiler/ccgexprs.nim
index 66f92f12e..38ecb11aa 100644
--- a/compiler/ccgexprs.nim
+++ b/compiler/ccgexprs.nim
@@ -1414,7 +1414,7 @@ proc rawGenNew(p: BProc, a: var TLoc, sizeExpr: Rope; needsInit: bool) =
       p.module.s[cfsTypeInit3].addf("$1->finalizer = (void*)$2;$n", [ti, rdLoc(f)])
 
     if a.storage == OnHeap and usesWriteBarrier(p.config):
-      if canFormAcycle(a.t):
+      if canFormAcycle(p.module.g.graph, a.t):
         linefmt(p, cpsStmts, "if ($1) { #nimGCunrefRC1($1); $1 = NIM_NIL; }$n", [a.rdLoc])
       else:
         linefmt(p, cpsStmts, "if ($1) { #nimGCunrefNoCycle($1); $1 = NIM_NIL; }$n", [a.rdLoc])
@@ -1451,7 +1451,7 @@ proc genNewSeqAux(p: BProc, dest: TLoc, length: Rope; lenIsZero: bool) =
   var call: TLoc
   initLoc(call, locExpr, dest.lode, OnHeap)
   if dest.storage == OnHeap and usesWriteBarrier(p.config):
-    if canFormAcycle(dest.t):
+    if canFormAcycle(p.module.g.graph, dest.t):
       linefmt(p, cpsStmts, "if ($1) { #nimGCunrefRC1($1); $1 = NIM_NIL; }$n", [dest.rdLoc])
     else:
       linefmt(p, cpsStmts, "if ($1) { #nimGCunrefNoCycle($1); $1 = NIM_NIL; }$n", [dest.rdLoc])
diff --git a/compiler/ccgtypes.nim b/compiler/ccgtypes.nim
index 2d1f632a2..2669dec24 100644
--- a/compiler/ccgtypes.nim
+++ b/compiler/ccgtypes.nim
@@ -1036,7 +1036,7 @@ proc genTypeInfoAuxBase(m: BModule; typ, origType: PType;
   # compute type flags for GC optimization
   var flags = 0
   if not containsGarbageCollectedRef(typ): flags = flags or 1
-  if not canFormAcycle(typ): flags = flags or 2
+  if not canFormAcycle(m.g.graph, typ): flags = flags or 2
   #else echo("can contain a cycle: " & typeToString(typ))
   if flags != 0:
     m.s[cfsTypeInit3].addf("$1.flags = $2;$n", [nameHcr, rope(flags)])
@@ -1318,7 +1318,7 @@ proc genHook(m: BModule; t: PType; info: TLineInfo; op: TTypeAttachedOp; result:
     result.add theProc.loc.r
 
     when false:
-      if not canFormAcycle(t) and op == attachedTrace:
+      if not canFormAcycle(m.g.graph, t) and op == attachedTrace:
         echo "ayclic but has this =trace ", t, " ", theProc.ast
   else:
     when false:
@@ -1364,7 +1364,7 @@ proc genTypeInfoV2OldImpl(m: BModule; t, origType: PType, name: Rope; info: TLin
   m.s[cfsStrData].addf("N_LIB_PRIVATE TNimTypeV2 $1;$n", [name])
 
   var flags = 0
-  if not canFormAcycle(t): flags = flags or 1
+  if not canFormAcycle(m.g.graph, t): flags = flags or 1
 
   var typeEntry = newRopeAppender()
   addf(typeEntry, "$1.destructor = (void*)", [name])
@@ -1405,7 +1405,7 @@ proc genTypeInfoV2Impl(m: BModule; t, origType: PType, name: Rope; info: TLineIn
   m.s[cfsStrData].addf("N_LIB_PRIVATE TNimTypeV2 $1;$n", [name])
 
   var flags = 0
-  if not canFormAcycle(t): flags = flags or 1
+  if not canFormAcycle(m.g.graph, t): flags = flags or 1
 
   var typeEntry = newRopeAppender()
   addf(typeEntry, "N_LIB_PRIVATE TNimTypeV2 $1 = {", [name])
diff --git a/compiler/injectdestructors.nim b/compiler/injectdestructors.nim
index ab0fa02d9..9745fee81 100644
--- a/compiler/injectdestructors.nim
+++ b/compiler/injectdestructors.nim
@@ -305,13 +305,13 @@ proc isCriticalLink(dest: PNode): bool {.inline.} =
 proc finishCopy(c: var Con; result, dest: PNode; isFromSink: bool) =
   if c.graph.config.selectedGC == gcOrc:
     let t = dest.typ.skipTypes({tyGenericInst, tyAlias, tySink, tyDistinct})
-    if cyclicType(t):
+    if cyclicType(c.graph, t):
       result.add boolLit(c.graph, result.info, isFromSink or isCriticalLink(dest))
 
 proc genMarkCyclic(c: var Con; result, dest: PNode) =
   if c.graph.config.selectedGC == gcOrc:
     let t = dest.typ.skipTypes({tyGenericInst, tyAlias, tySink, tyDistinct})
-    if cyclicType(t):
+    if cyclicType(c.graph, t):
       if t.kind == tyRef:
         result.add callCodegenProc(c.graph, "nimMarkCyclic", dest.info, dest)
       else:
diff --git a/compiler/liftdestructors.nim b/compiler/liftdestructors.nim
index 34ab3cc8e..85403586f 100644
--- a/compiler/liftdestructors.nim
+++ b/compiler/liftdestructors.nim
@@ -545,7 +545,7 @@ proc fillSeqOp(c: var TLiftCtx; t: PType; body, x, y: PNode) =
     forallElements(c, t, body, x, y)
     body.add genBuiltin(c, mDestroy, "destroy", x)
   of attachedTrace:
-    if canFormAcycle(t.elemType):
+    if canFormAcycle(c.g, t.elemType):
       # follow all elements:
       forallElements(c, t, body, x, y)
   of attachedWasMoved: body.add genBuiltin(c, mWasMoved, "wasMoved", x)
@@ -583,7 +583,7 @@ proc useSeqOrStrOp(c: var TLiftCtx; t: PType; body, x, y: PNode) =
     doAssert t.destructor != nil
     body.add destructorCall(c, t.destructor, x)
   of attachedTrace:
-    if t.kind != tyString and canFormAcycle(t.elemType):
+    if t.kind != tyString and canFormAcycle(c.g, t.elemType):
       let op = getAttachedOp(c.g, t, c.kind)
       if op == nil:
         return # protect from recursion
@@ -610,9 +610,9 @@ proc fillStrOp(c: var TLiftCtx; t: PType; body, x, y: PNode) =
   of attachedDup:
     assert false, "cannot happen"
 
-proc cyclicType*(t: PType): bool =
+proc cyclicType*(g: ModuleGraph, t: PType): bool =
   case t.kind
-  of tyRef: result = types.canFormAcycle(t.lastSon)
+  of tyRef: result = types.canFormAcycle(g, t.lastSon)
   of tyProc: result = t.callConv == ccClosure
   else: result = false
 
@@ -640,7 +640,7 @@ proc atomicRefOp(c: var TLiftCtx; t: PType; body, x, y: PNode) =
   let elemType = t.lastSon
 
   createTypeBoundOps(c.g, c.c, elemType, c.info, c.idgen)
-  let isCyclic = c.g.config.selectedGC == gcOrc and types.canFormAcycle(elemType)
+  let isCyclic = c.g.config.selectedGC == gcOrc and types.canFormAcycle(c.g, elemType)
 
   let isInheritableAcyclicRef = c.g.config.selectedGC == gcOrc and
                       (not isPureObject(elemType)) and
@@ -990,7 +990,7 @@ proc symPrototype(g: ModuleGraph; typ: PType; owner: PSym; kind: TTypeAttachedOp
     result.typ.addParam src
 
   if kind == attachedAsgn and g.config.selectedGC == gcOrc and
-      cyclicType(typ.skipTypes(abstractInst)):
+      cyclicType(g, typ.skipTypes(abstractInst)):
     let cycleParam = newSym(skParam, getIdent(g.cache, "cyclic"),
                             idgen, result, info)
     cycleParam.typ = getSysType(g, info, tyBool)
diff --git a/compiler/semmagic.nim b/compiler/semmagic.nim
index 6af752770..71efcadb1 100644
--- a/compiler/semmagic.nim
+++ b/compiler/semmagic.nim
@@ -215,6 +215,10 @@ proc evalTypeTrait(c: PContext; traitCall: PNode, operand: PType, context: PSym)
     var arg = operand.skipTypes({tyGenericInst})
     assert arg.kind == tyRange
     result = getTypeDescNode(c, arg.base, operand.owner, traitCall.info)
+  of "isCyclic":
+    var operand = operand.skipTypes({tyGenericInst})
+    let isCyclic = canFormAcycle(c.graph, operand)
+    result = newIntNodeT(toInt128(ord(isCyclic)), traitCall, c.idgen, c.graph)
   else:
     localError(c.config, traitCall.info, "unknown trait: " & s)
     result = newNodeI(nkEmpty, traitCall.info)
diff --git a/compiler/types.nim b/compiler/types.nim
index d2517127a..97cc439c0 100644
--- a/compiler/types.nim
+++ b/compiler/types.nim
@@ -370,41 +370,62 @@ proc containsHiddenPointer*(typ: PType): bool =
   # that need to be copied deeply)
   result = searchTypeFor(typ, isHiddenPointer)
 
-proc canFormAcycleAux(marker: var IntSet, typ: PType, startId: int): bool
-proc canFormAcycleNode(marker: var IntSet, n: PNode, startId: int): bool =
+proc canFormAcycleAux(g: ModuleGraph; marker: var IntSet, typ: PType, orig: PType, withRef: bool, hasTrace: bool): bool
+proc canFormAcycleNode(g: ModuleGraph; marker: var IntSet, n: PNode, orig: PType, withRef: bool, hasTrace: bool): bool =
   result = false
   if n != nil:
-    result = canFormAcycleAux(marker, n.typ, startId)
+    result = canFormAcycleAux(g, marker, n.typ, orig, withRef, hasTrace)
     if not result:
       case n.kind
       of nkNone..nkNilLit:
         discard
       else:
         for i in 0..<n.len:
-          result = canFormAcycleNode(marker, n[i], startId)
+          result = canFormAcycleNode(g, marker, n[i], orig, withRef, hasTrace)
           if result: return
 
-proc canFormAcycleAux(marker: var IntSet, typ: PType, startId: int): bool =
+
+proc sameBackendType*(x, y: PType): bool
+proc canFormAcycleAux(g: ModuleGraph, marker: var IntSet, typ: PType, orig: PType, withRef: bool, hasTrace: bool): bool =
   result = false
   if typ == nil: return
   if tfAcyclic in typ.flags: return
   var t = skipTypes(typ, abstractInst+{tyOwned}-{tyTypeDesc})
   if tfAcyclic in t.flags: return
   case t.kind
-  of tyTuple, tyObject, tyRef, tySequence, tyArray, tyOpenArray, tyVarargs:
-    if t.id == startId:
+  of tyRef, tyPtr, tyUncheckedArray:
+    if t.kind == tyRef or hasTrace:
+      if withRef and sameBackendType(t, orig):
+        result = true
+      elif not containsOrIncl(marker, t.id):
+        for i in 0..<t.len:
+          result = canFormAcycleAux(g, marker, t[i], orig, withRef or t.kind != tyUncheckedArray, hasTrace)
+          if result: return
+  of tyObject:
+    if withRef and sameBackendType(t, orig):
       result = true
     elif not containsOrIncl(marker, t.id):
+      var hasTrace = hasTrace
+      let op = getAttachedOp(g, t.skipTypes({tyRef}), attachedTrace)
+      if op != nil and sfOverriden in op.flags:
+        hasTrace = true
       for i in 0..<t.len:
-        result = canFormAcycleAux(marker, t[i], startId)
+        result = canFormAcycleAux(g, marker, t[i], orig, withRef, hasTrace)
         if result: return
-      if t.n != nil: result = canFormAcycleNode(marker, t.n, startId)
+      if t.n != nil: result = canFormAcycleNode(g, marker, t.n, orig, withRef, hasTrace)
     # Inheritance can introduce cyclic types, however this is not relevant
     # as the type that is passed to 'new' is statically known!
     # er but we use it also for the write barrier ...
-    if t.kind == tyObject and tfFinal notin t.flags:
+    if tfFinal notin t.flags:
       # damn inheritance may introduce cycles:
       result = true
+  of tyTuple, tySequence, tyArray, tyOpenArray, tyVarargs:
+    if withRef and sameBackendType(t, orig):
+      result = true
+    elif not containsOrIncl(marker, t.id):
+      for i in 0..<t.len:
+        result = canFormAcycleAux(g, marker, t[i], orig, withRef, hasTrace)
+        if result: return
   of tyProc: result = typ.callConv == ccClosure
   else: discard
 
@@ -412,10 +433,10 @@ proc isFinal*(t: PType): bool =
   let t = t.skipTypes(abstractInst)
   result = t.kind != tyObject or tfFinal in t.flags or isPureObject(t)
 
-proc canFormAcycle*(typ: PType): bool =
+proc canFormAcycle*(g: ModuleGraph, typ: PType): bool =
   var marker = initIntSet()
   let t = skipTypes(typ, abstractInst+{tyOwned}-{tyTypeDesc})
-  result = canFormAcycleAux(marker, t, t.id)
+  result = canFormAcycleAux(g, marker, t, t, false, false)
 
 proc mutateTypeAux(marker: var IntSet, t: PType, iter: TTypeMutator,
                    closure: RootRef): PType
diff --git a/tests/types/tcyclic.nim b/tests/types/tcyclic.nim
new file mode 100644
index 000000000..fc2852c49
--- /dev/null
+++ b/tests/types/tcyclic.nim
@@ -0,0 +1,123 @@
+## todo publish the `isCyclic` when it's mature.
+proc isCyclic(t: typedesc): bool {.magic: "TypeTrait".} =
+  ## Returns true if the type can potentially form a cyclic type
+
+template cyclicYes(x: typed) =
+  doAssert isCyclic(x)
+
+template cyclicNo(x: typed) =
+  doAssert not isCyclic(x)
+
+# atomic types are not cyclic
+cyclicNo(int)
+cyclicNo(float)
+cyclicNo(string)
+cyclicNo(char)
+cyclicNo(void)
+
+type
+  Object = object
+  Ref = ref object
+
+cyclicNo(Object)
+cyclicNo(Ref)
+
+type
+  Data1 = ref object
+  Data2 = ref object
+    id: Data1
+
+cyclicNo(Data2)
+
+type
+  Cyclone = ref object
+    data: Cyclone
+
+  Alias = Cyclone
+
+  Acyclic {.acyclic.} = ref object
+    data: Acyclic
+
+  LinkedNode = object
+    next: ref LinkedNode
+
+  LinkedNodeWithCursor = object
+    next {.cursor.} : ref LinkedNodeWithCursor
+
+cyclicYes(Cyclone)
+cyclicYes(Alias)
+cyclicNo(seq[Cyclone])
+cyclicNo((Cyclone, ))
+cyclicNo(Acyclic)
+
+cyclicYes(LinkedNode)
+
+when false:
+  # todo fix me
+  cyclicNo(LinkedNodeWithCursor)
+
+type
+  ObjectWithoutCycles = object
+    data: seq[ObjectWithoutCycles]
+
+cyclicNo(ObjectWithoutCycles)
+
+
+block:
+  type
+    Try = object
+      id: Best
+    Best = object
+      name: ref Try
+    Best2 = ref Best
+
+  cyclicYes(Best)
+  cyclicYes(Try)
+  cyclicNo(Best2)
+
+  type
+    Base = object
+      data: ref seq[Base]
+    Base2 = ref Base
+
+  cyclicYes(Base)
+  cyclicNo(Base2)
+
+
+  type
+    Base3 = ref object
+      id: Base3
+
+    Base4 = object
+      id: ref Base4
+
+  cyclicYes(Base3)
+  cyclicYes(Base4)
+  cyclicYes(ref Base4)
+
+block:
+  type Cyclic2 = object
+    x: ref (Cyclic2, int)
+
+  cyclicYes (Cyclic2, int)
+  cyclicYes (ref (Cyclic2, int))
+
+block:
+  type
+    myseq[T] = object
+      data: ptr UncheckedArray[T]
+    Node = ref object
+      kids: myseq[Node]
+
+  cyclicNo(Node)
+
+block:
+  type
+    myseq[T] = object
+      data: ptr UncheckedArray[T]
+    Node = ref object
+      kids: myseq[Node]
+
+  proc `=trace`(x: var myseq[Node]; env: pointer) = discard
+
+  cyclicYes(Node)