StackOverflow in typer

[sir-wabbit]

trait X {
  type A = B
  type B
}
trait Y {
  type A
  type B = A
}
trait Z extends X with Y

Exception in thread "main" java.lang.StackOverflowError
	at java.lang.invoke.MemberName.getInvocationType(MemberName.java:164)
	at java.lang.invoke.DirectMethodHandle.preparedLambdaForm(DirectMethodHandle.java:167)
	at java.lang.invoke.DirectMethodHandle.make(DirectMethodHandle.java:89)
	at java.lang.invoke.MethodHandles$Lookup.getDirectMethodCommon(MethodHandles.java:1660)
	at java.lang.invoke.MethodHandles$Lookup.getDirectMethodNoSecurityManager(MethodHandles.java:1617)
	at java.lang.invoke.MethodHandles$Lookup.getDirectMethodForConstant(MethodHandles.java:1802)
	at java.lang.invoke.MethodHandles$Lookup.linkMethodHandleConstant(MethodHandles.java:1751)
	at java.lang.invoke.MethodHandleNatives.linkMethodHandleConstant(MethodHandleNatives.java:477)
	at dotty.tools.dotc.core.Types$Type.findMember(Types.scala:661)
	at dotty.tools.dotc.core.Types$Type.memberExcluding(Types.scala:491)
	at dotty.tools.dotc.core.Types$Type.$anonfun$nonPrivateMember$1(Types.scala:482)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.core.Types$Type.nonPrivateMember(Types.scala:482)
	at dotty.tools.dotc.core.Types$NamedType.memberDenot(Types.scala:1777)
	at dotty.tools.dotc.core.Types$NamedType.reload$1(Types.scala:2025)
	at dotty.tools.dotc.core.Types$NamedType.withPrefix(Types.scala:2037)
	at dotty.tools.dotc.core.Types$NamedType.derivedSelect(Types.scala:1997)
	at dotty.tools.dotc.core.Types$TypeMap.derivedSelect(Types.scala:3902)
	at dotty.tools.dotc.core.Types$ApproximatingTypeMap.derivedSelect(Types.scala:4174)
	at dotty.tools.dotc.core.TypeOps$AsSeenFromMap.$anonfun$apply$4(TypeOps.scala:61)
	at dotty.tools.dotc.reporting.trace$.op1$1(trace.scala:18)
	at dotty.tools.dotc.reporting.trace$.conditionally(trace.scala:20)
	at dotty.tools.dotc.core.TypeOps$AsSeenFromMap.apply(TypeOps.scala:54)
	at dotty.tools.dotc.core.Types$TypeMap.$anonfun$mapOver$7(Types.scala:3974)
	at dotty.tools.dotc.core.Types$VariantTraversal.atVariance(Types.scala:3888)
	at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:3974)
	at dotty.tools.dotc.core.TypeOps$AsSeenFromMap.$anonfun$apply$4(TypeOps.scala:67)
	at dotty.tools.dotc.reporting.trace$.op1$1(trace.scala:18)
	at dotty.tools.dotc.reporting.trace$.conditionally(trace.scala:20)
	at dotty.tools.dotc.core.TypeOps$AsSeenFromMap.apply(TypeOps.scala:54)
	at dotty.tools.dotc.core.TypeOps.asSeenFrom(TypeOps.scala:28)
	at dotty.tools.dotc.core.TypeOps.asSeenFrom$(TypeOps.scala:27)
	at dotty.tools.dotc.core.Contexts$Context.asSeenFrom(Contexts.scala:71)
	at dotty.tools.dotc.core.Types$Type.$anonfun$asSeenFrom$1(Types.scala:767)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.core.Types$Type.asSeenFrom(Types.scala:766)
	at dotty.tools.dotc.core.Denotations$SingleDenotation.computeAsSeenFrom(Denotations.scala:1075)
	at dotty.tools.dotc.core.Denotations$SingleDenotation.computeAsSeenFrom(Denotations.scala:660)
	at dotty.tools.dotc.core.Denotations$PreDenotation.asSeenFrom(Denotations.scala:131)
	at dotty.tools.dotc.core.Denotations$SingleDenotation.mapInherited(Denotations.scala:1062)
	at dotty.tools.dotc.core.Denotations$SingleDenotation.mapInherited(Denotations.scala:660)
	at dotty.tools.dotc.core.SymDenotations$ClassDenotation.collect$1(SymDenotations.scala:1605)
	at dotty.tools.dotc.core.SymDenotations$ClassDenotation.collect$1(SymDenotations.scala:1600)
	at dotty.tools.dotc.core.SymDenotations$ClassDenotation.collect$1(SymDenotations.scala:1600)
	at dotty.tools.dotc.core.SymDenotations$ClassDenotation.$anonfun$computeNPMembersNamed$1(SymDenotations.scala:1613)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.core.SymDenotations$ClassDenotation.computeNPMembersNamed(SymDenotations.scala:1592)
	at dotty.tools.dotc.core.SymDenotations$ClassDenotation.nonPrivateMembersNamed(SymDenotations.scala:1582)
	at dotty.tools.dotc.core.SymDenotations$ClassDenotation.findMember(SymDenotations.scala:1617)
	at dotty.tools.dotc.core.Types$Type.go$1(Types.scala:509)
	at dotty.tools.dotc.core.Types$Type.goThis$1(Types.scala:613)
	at dotty.tools.dotc.core.Types$Type.go$1(Types.scala:522)
	at dotty.tools.dotc.core.Types$Type.findMember(Types.scala:658)
	at dotty.tools.dotc.core.Types$Type.memberExcluding(Types.scala:491)
	at dotty.tools.dotc.core.Types$Type.$anonfun$nonPrivateMember$1(Types.scala:482)
	at dotty.tools.dotc.util.Stats$.track(Stats.scala:35)
	at dotty.tools.dotc.core.Types$Type.nonPrivateMember(Types.scala:482)
	at dotty.tools.dotc.core.Types$NamedType.memberDenot(Types.scala:1777)
	at dotty.tools.dotc.core.Types$NamedType.reload$1(Types.scala:2025)
	at dotty.tools.dotc.core.Types$NamedType.withPrefix(Types.scala:2037)
	at dotty.tools.dotc.core.Types$NamedType.derivedSelect(Types.scala:1997)
	at dotty.tools.dotc.core.Types$TypeMap.derivedSelect(Types.scala:3902)
	at dotty.tools.dotc.core.Types$ApproximatingTypeMap.derivedSelect(Types.scala:4174)
	at dotty.tools.dotc.core.TypeOps$AsSeenFromMap.$anonfun$apply$4(TypeOps.scala:61)
	at dotty.tools.dotc.reporting.trace$.op1$1(trace.scala:18)
	at dotty.tools.dotc.reporting.trace$.conditionally(trace.scala:20)
	at dotty.tools.dotc.core.TypeOps$AsSeenFromMap.apply(TypeOps.scala:54)
	at dotty.tools.dotc.core.Types$TypeMap.$anonfun$mapOver$7(Types.scala:3974)
	at dotty.tools.dotc.core.Types$VariantTraversal.atVariance(Types.scala:3888)
	at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:3974)
	at dotty.tools.dotc.core.TypeOps$AsSeenFromMap.$anonfun$apply$4(TypeOps.scala:67)
	at dotty.tools.dotc.reporting.trace$.op1$1(trace.scala:18)
	at dotty.tools.dotc.reporting.trace$.conditionally(trace.scala:20)
.......

[sir-wabbit]

Other ways to do the same thing

trait W {
  type A
  type B
}
trait X { z: W =>
  type A = z.B
  type B
}
trait Y { z: W =>
  type A
  type B = z.A
}
trait Z extends X with Y

trait W {
  type A
  type B
}
trait X { z: W =>
  type A = z.B
  type B
}
trait Y { z: W =>
  type A
  type B = z.A
}

object App {
  type Z = X with Y
  val z: Z = z
  val a: z.A = a
}

trait X[F[_]] {
  protected type A = F[B]
  protected type B
}
trait Y[F[_]] {
  protected type A
  protected type B = F[A]
}

trait Fix[F[_]] extends X[F] with Y[F] {
  type Result = A
}

trait X {
  type A = B
  type B
}
trait Y {
  type A
  type B = A
}

object App {
  type Z = X & Y
  val z: Z = z
  val a: z.A = a
}

trait W { type T <: W; val t: T }
trait X {
  type A = b.T
  val a : A = b.t
  type B <: W
  val b : B
}
trait Y {
  type A <: W
  val a : A
  type B = a.T
  val b = a.t
}
trait Z extends X with Y

class Fix[F[_]] {
  class Foo { type R >: F[T] <: F[T] }
  type T = F[Foo#R]
}

object App {
  type Nat = Fix[Option]#T
}

[sir-wabbit]

trait W {
  type A
}
trait X extends W {
  type A = B
  type B
}
trait Y extends W {
  type A
  type B = A
}

trait Foo[X <: W, Y <: W] {
  type Z = X & Y
  val z: Z
  val a: z.A
}

trait Boo {
  val f: Foo[X, Y]
}

trait Baz extends Boo {
  val a = f.a // only this line triggers StackOverflow
  // remove it and it compiles fine
}

[odersky]

Would be good to know what scalac does in this case.

[Blaisorblade]

For the first example, StackOverflow in normalize.

scala> trait Z extends X with Y
java.lang.StackOverflowError
	at scala.reflect.internal.Symbols$Symbol.rawInfo(Symbols.scala:1605)
	at scala.reflect.internal.Symbols$Symbol.info(Symbols.scala:1542)
	at scala.reflect.internal.Types$TypeRef.baseClasses(Types.scala:2304)
	at scala.reflect.internal.Types$SimpleTypeProxy.baseClasses(Types.scala:163)
	at scala.reflect.internal.Types$SimpleTypeProxy.baseClasses$(Types.scala:163)
	at scala.reflect.internal.Types$SingletonType.baseClasses(Types.scala:1095)
	at scala.reflect.internal.tpe.FindMembers$FindMemberBase.<init>(FindMembers.scala:17)
	at scala.reflect.internal.tpe.FindMembers$FindMember.<init>(FindMembers.scala:219)
	at scala.reflect.internal.Types$Type.findMemberInternal$1(Types.scala:1033)
	at scala.reflect.internal.Types$Type.findMember(Types.scala:1035)
	at scala.reflect.internal.Types$Type.memberBasedOnName(Types.scala:661)
	at scala.reflect.internal.Types$Type.nonPrivateMember(Types.scala:632)
	at scala.reflect.internal.Types.rebind(Types.scala:3525)
	at scala.reflect.internal.Types.typeRef(Types.scala:3602)
	at scala.reflect.internal.Types.typeRef$(Types.scala:3596)
	at scala.reflect.internal.SymbolTable.typeRef(SymbolTable.scala:18)
	at scala.reflect.internal.Types.copyTypeRef(Types.scala:3629)
	at scala.reflect.internal.Types.copyTypeRef$(Types.scala:3619)
	at scala.reflect.internal.SymbolTable.copyTypeRef(SymbolTable.scala:18)
	at scala.reflect.internal.tpe.TypeMaps$TypeMap.mapOver(TypeMaps.scala:115)
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.apply(TypeMaps.scala:484)
	at scala.reflect.internal.Types$Type.asSeenFrom(Types.scala:693)
	at scala.reflect.internal.Types$TypeRef.relativize(Types.scala:2177)
	at scala.reflect.internal.Types$AliasTypeRef.betaReduce(Types.scala:2037)
	at scala.reflect.internal.Types$AliasTypeRef.betaReduce$(Types.scala:2037)
	at scala.reflect.internal.Types$AliasNoArgsTypeRef.betaReduce(Types.scala:2433)
[followed by iterations of]
	at scala.reflect.internal.Types$AliasTypeRef.normalizeImpl(Types.scala:2017)
	at scala.reflect.internal.Types$AliasTypeRef.normalizeImpl$(Types.scala:2016)
	at scala.reflect.internal.Types$AliasNoArgsTypeRef.normalizeImpl(Types.scala:2433)
	at scala.reflect.internal.Types$TypeRef.normalize(Types.scala:2254)

[Blaisorblade]

scala/bug#10846 reports quite a few examples also stack overflow there. The last one fails due to volatility checks:

trait W {
  type A
}
trait X extends W {
  type A = B
  type B
}
trait Y extends W {
  type A
  type B = A
}

trait Foo[X <: W, Y <: W] {
  type Z = X with Y
  val z: Z
  val a: z.A
}

[smarter]

Looks like a duplicate of one of the oldest issue still open: #318