Imported From: https://issues.scala-lang.org/browse/SI-8252?orig=1
Reporter: @retronym
Affected Versions: 2.10.3

@retronym said (edited on Apr 9, 2014 12:46:25 PM UTC):
A branch from my investigations of this bug:

https://github.com/retronym/scala/compare/ticket/8252

It is not the correct fix, but points at the area that needs fixing.

Another example, maybe related, from @jeremyrsmith

trait Schema

class Thing[S] {
  def apply[T](col: S => T): T = ???
}


class Test {
  type :+:[H, T <: Schema] = H with T
  type End = Schema

  def test = {
    // compiles (NotImplemented at runtime)
    // new Thing[{val foo: String} :+: End].apply(_.foo)


    // compile error: cyclic aliasing or subtyping involving type :+:
    new Thing[{val foo: String} :+: {val bar: Int} :+: End].apply(x => x.foo)
  }
}

The last line trace out as:

  -> checkNonCyclic(AnyRef{val foo: String} :+: (AnyRef{val bar: Int} :+: Test.this.End), value x)
    -> checkNonCyclic(AnyRef{val foo: String} :+: (AnyRef{val bar: Int} :+: Test.this.End))
      -> checkNonCyclic(AnyRef{val foo: String} with AnyRef{val bar: Int} :+: Test.this.End, type :+:)
        -> checkNonCyclic(AnyRef{val foo: String} with AnyRef{val bar: Int} :+: Test.this.End)
          -> checkNonCyclic(AnyRef{val foo: String})
            -> checkNonCyclic(AnyRef)
              -> checkNonCyclic(Object, type AnyRef)
                -> checkNonCyclic(Object)
                <- checkNonCyclic(Object)
              <- checkNonCyclic(Object, type AnyRef)
            <- checkNonCyclic(AnyRef)
          <- checkNonCyclic(AnyRef{val foo: String})
          -> checkNonCyclic(AnyRef{val bar: Int} :+: Test.this.End)
sandbox/test.scala:19: error: cyclic aliasing or subtyping involving type :+:
    new Thing[{val foo: String} :+: {val bar: Int} :+: End].apply(x => x.foo)
                                                                  ^
          <- checkNonCyclic(AnyRef{val bar: Int} :+: Test.this.End)
        <- checkNonCyclic(AnyRef{val foo: String} with AnyRef{val bar: Int} :+: Test.this.End)
      <- checkNonCyclic(AnyRef{val foo: String} with AnyRef{val bar: Int} :+: Test.this.End, type :+:)
    <- checkNonCyclic(AnyRef{val foo: String} :+: (AnyRef{val bar: Int} :+: Test.this.End))
  <- checkNonCyclic(AnyRef{val foo: String} :+: (AnyRef{val bar: Int} :+: Test.this.End), value x)

with

diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 95c58faed2..d59bb6fb8c 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -301,7 +301,8 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
 
     /** Check that type `tp` is not a subtype of itself.
      */
-    def checkNonCyclic(pos: Position, tp: Type): Boolean = {
+    def checkNonCyclic(pos: Position, tp: Type): Boolean = try {
+      enter(s"checkNonCyclic(${tp.safeToString})")
       def checkNotLocked(sym: Symbol) = {
         sym.initialize.lockOK || { CyclicAliasingOrSubtypingError(pos, sym); false }
       }
@@ -321,12 +322,25 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
         case _ =>
           true
       }
+    } finally {
+      exit(s"checkNonCyclic(${tp.safeToString})")
     }
-
+    private var indent = 0
+    private def enter(msg: String) = {
+      indent += 1
+      log("-> " + msg)
+    }
+    private def exit(msg: String) = {
+      log("<- " + msg)
+      indent -= 1
+    }
+    private def log(msg: String) = println(("  " * indent) + msg)
     def checkNonCyclic(pos: Position, tp: Type, lockedSym: Symbol): Boolean = try {
+      enter(s"checkNonCyclic(${tp.safeToString}, $lockedSym)")
       if (!lockedSym.lock(CyclicReferenceError(pos, tp, lockedSym))) false
       else checkNonCyclic(pos, tp)
     } finally {
+      exit(s"checkNonCyclic(${tp.safeToString}, $lockedSym)")
       lockedSym.unlock()
     }

@adriaanm I sort of think that checkNonCyclic needs to consider AliasTypeSymbol-s differently. This latest example shows that in the types that it unrolls, we can hit an alias more than once without actually finding a cycle. But I don't have a clear enough mental picture of how this works...

@retronym @adriaanm here's the reason it's so odd; this example (building on the previous type aliases) compiles just fine, when there's a typeclass involved

  trait Example[T] {
    type Out
    def apply[A](fn: Out => A): A = ???
  }

  object Example {
    def apply[A](implicit inst: Example[A]): Aux[A, inst.Out] = inst
    type Aux[T, Out0] = Example[T] { type Out = Out0 }
    implicit def forall[T]: Aux[T, T] = new Example[T] { type Out = T }
  }

  // this compiles. We can safely say that the nth structural mixin doesn't break it. 
  // apply is the same signature as when it breaks, the only difference being that it's a type member of an implicit?
  Example[{val foo: Int} :+: {val bar: String} :+: {val baz: Boolean} :+: {val buzz: Double} :+: {val booze: Float} :+: End].apply(_.foo)

Interesting as well. Using the same trait Example that works above (when summoned implicitly) fails when constructed explicitly:

new Example[Unit] {
    type Out = {val foo: Int} :+: {val bar: String} :+: {val baz: Boolean} :+: {val buzz: Double} :+: {val booze: Float} :+: End
  }.apply(_.foo)

Here, you get cyclic aliasing or subtyping involving type :+: at the type Out = ... part. So it fails even without the apply(_.foo) at the end.

And again, if the nesting is shallower, it does compile:

// compiles
new Example[Unit] {
    type Out = {val foo: Int} :+: End
}.apply(_.foo)

It seems to be the type member that makes it work in the typeclass case above - or where the type member is constructed - rather than the fact that it's implicitly summoned. Adding a type member is enough to make the original example work, without any typeclasses involved:

object Example {

  trait Schema
  type :+:[H, T <: Schema] = H with T
  type End = Schema

  class Thing[S] {
    type Out = S
    
    // added a type member that references the type arg,
    // and use that for the type signature here
    def apply[T](fn: Out => T): T = ???
  }

  // this compiles now
  new Thing[
    {val foo: String} :+: {val bar: Int} :+: {val baz: Boolean} :+: {val booze: Double} :+: End
  ].apply(x => x.foo)

}

Edit: but this fails!

val foo = new Thing[
  {val foo: String} :+: {val bar: Int} :+: {val baz: Boolean} :+: {val booze: Double} :+: End
]

// compile error; cyclic aliasing or subtyping involving type :+:
foo.apply(x => x.foo)

The only difference being assigning the Thing to a value and then calling apply.

However, if you move the type member, and apply, to an implicit class, then it works even with value assignment (this works iff the implicit class has a type member and that's referenced instead of the type argument in the type signature of apply):

object Example {

  trait Schema
  type :+:[H, T <: Schema] = H with T
  type End = Schema

  class Thing[S]

  implicit class ThingOps[S](self: Thing[S]) {
    type Out = S
    def apply[T](fn: Out => T): T = ???
  }

  val foo = new Thing[
    {val foo: String} :+: {val bar: Int} :+: {val baz: Boolean} :+: {val booze: Double} :+: End
  ]

  // compiles
  foo.apply(x => x.foo)

}

Apologies for spamming this issue; if this is too much noise, let me know and I'll quit it. Just figured the more info the better.

Here's another example that fails in the same way:

trait Foo { type X }
trait HL extends Foo { override type X }
trait HC[H <: Foo, T <: HL] extends HL { override type X = H#X with T#X }
trait HN extends HL { override type X = Any }
class A extends Foo { trait X } ; class B extends Foo { trait X }
class Test {
    def test: Unit = {
        val bad = new HC[A, HC[B, HN]] {}
        val xx: bad.X = ???
    }
}

In this case, at least, I think the problem is that our approach of using the LOCKED flag on type symbols as we unroll the type is overly restrictive for type members. Perhaps for these we should be using a stack of encountered prefixes instead? We need to be careful about allowing infinite expansions where the the prefix somehow varies at each step without ever reducing.

One workaround, at least for the most recent example I posted, is to use the experimental option -Yrecursion N which defers errors based on symbol locking until the symbol has appeared N times in recursion. See scala/scala@fa8d0d8

Here's a sketch of using a dedicated, on-by-default recursion table for type aliases. It doesn't fix the first example in this ticket as the in that one the alias Id is encountered on the same prefix but with different type args, so my approach of allowing differing prefixes isn't enoough.