(caught cyclic reference) error on type definitions that works on Scala 2

[tribbloid]

Compiler version

3.6.2

Minimized code

The following code defined some common graph axioms:

object Scaffold {

  trait Arrow
  object Arrow {
    trait Outbound extends Arrow
  }

  trait NodeKOrGraphK {}

  trait NodeK extends NodeKOrGraphK {

    type FBound <: Induction

    protected def getInduction: Seq[FBound]
  }

  trait Induction {
    def arrow: Arrow
    def node: NodeK
  }

  object Induction {

    trait FP[+N <: NodeK] extends Induction { // short for "fixed point"
      def node: N
    }
  }

  trait GraphK extends NodeKOrGraphK {

    type Batch[+T] <: Iterable[T]

    type _Node <: NodeK

    def entries: Batch[_Node]
  }

  trait Topology {

    type FP = Induction.FP[Node]
    type FBound <: FP

    type Node = NodeK { type FBound <: Topology.this.FBound }
    trait Node_ extends NodeK {
      type FBound = Topology.this.FBound
    }

    type Graph = GraphK { type _Node <: Node }
  }

}

Output

49:10: illegal cyclic type reference: alias ai.acyclic.six.graph.Scaffold.Induction.FP[Topology.this.Node] of ... (caught cyclic reference) ... refers back to the type itself

The error occurred while trying to compute the signature of type FP
  which required to explore type Node for cyclic references
  which required to explore type FBound for cyclic references
  which required to explore type FP for cyclic references

 Run with both -explain-cyclic and -Ydebug-cyclic to see full stack trace.
one error found

FAILURE: Build failed with an exception.

Expectation

cyclic reference in sound type definition are common, but some of them are not compilable.

what makes this case interesting is that Scala 2.13 compiler has no problem compiling it.

is it an edge case of which old type exploration algorithm works better?

[Gedochao]

cc @SethTisue @dwijnand

[dwijnand]

You can make the code compile if you defined the refined type first:

--- i22257.orig.scala	2025-01-04 14:48:36
+++ i22257.fixed.scala	2025-01-04 14:50:47
@@ -38,14 +38,14 @@

   trait Topology {

+    type Node = NodeK { type FBound <: Topology.this.FBound }
+    trait Node_ extends NodeK {
+      type FBound = Topology.this.FBound
+    }
+
     type FP = Induction.FP[Node]
     type FBound <: FP
 
-    type Node = NodeK { type FBound <: Topology.this.FBound }
-    trait Node_ extends NodeK {
-      type FBound = Topology.this.FBound
-    }
-
     type Graph = GraphK { type _Node <: Node }
   }

But that's because it will start completing the symbols for the chain of type references while the Node type's info is set to the empty TypeBounds (Nothing..Any), which is documented to be there for f-bound purposes, which this isn't... So it's not a true fix.

scala3/compiler/src/dotty/tools/dotc/typer/Namer.scala

Lines 1050 to 1054 in 1448123

	val dummyInfo1 = abstracted(TypeBounds.empty)
	sym.info = dummyInfo1
	sym.setFlag(Provisional)
	// Temporarily set info of defined type T to ` >: Nothing <: Any.
	// This is done to avoid cyclic reference errors for F-bounds.

[tribbloid]

so there is a "chain of type references", not a "DAG of bound references"

sounds like a sub-problem of #22163