[SI-13] Types$$TypeRef Types$$SubType stack overflow Created: 28/Aug/07  Updated: 12/Mar/13  Resolved: 28/Jan/13

Status: CLOSED
Project: Scala Programming Language
Component/s: Type Checker
Affects Version/s: None
Fix Version/s: Scala 2.10.1

Type: Bug Priority: Minor
Reporter: Stephane Micheloud Assignee: Adriaan Moors
Resolution: Fixed Votes: 0
Labels: None

stack overflow type parameter inference

Paul Phillips, Simon Ochsenreither


== Code ==

// providing the type parameter in the recursive call to all4Impl
// avoids the problem
// covariant linked list
abstract class M { 
  self =>
    type T
    final type selfType = M {type T <: self.T}
    type actualSelfType >: self.type <: selfType
    def next: selfType
    // I don't understand why this doesn't compile, but that's a separate matter
    // error: method all2 cannot be accessed in M.this.selfType
    // because its instance type => Stream[M{type T <: M.this.selfType#T}]
    // contains a malformed type: M.this.selfType#T
    // def all2: Stream[M {type T <: self.T}] = Stream.cons(self: actualSelfType, next.all2)
    // compiles successfully
    // def all3: Stream[M {type T <: self.T}] = all3Impl(self: actualSelfType)
    // private def all3Impl(first: M {type T <: self.T}): Stream[M {type T <: self.T}] = Stream.cons(first, all3Impl(first.next))
    def all4: Stream[M {type T <: self.T}] = Unrelated.all4Impl[T](self: actualSelfType)
object Unrelated {
    def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl(first.next))
    // compiles successfully
    // def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl[U](first.next))

== What happened ==

Exception in thread "main" java.lang.StackOverflowError
	at scala.tools.nsc.symtab.Symbols$$ClassSymbol.name(Symbols.scala:1335)
	at scala.tools.nsc.symtab.Symbols$$Symbol.rawInfo(Symbols.scala:502)
	at scala.tools.nsc.symtab.Symbols$$Symbol.info(Symbols.scala:473)
	at scala.tools.nsc.symtab.Symbols$$Symbol.closureLength$$0(Symbols.scala:624)
	at scala.tools.nsc.symtab.Symbols$$Symbol.isLess(Symbols.scala:627)
	at scala.tools.nsc.symtab.Types$$Type.closurePos(Types.scala:528)
	at scala.tools.nsc.symtab.Symbols$$Symbol.isNonBottomSubClass(Symbols.scala:643)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.toPrefix$$0(Types.scala:2229)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.apply(Types.scala:2236)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.apply(Types.scala:2210)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:2087)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.apply(Types.scala:2281)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.apply(Types.scala:2210)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:2100)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.apply(Types.scala:2281)
	at scala.tools.nsc.symtab.Types$$Type.asSeenFrom(Types.scala:367)
	at scala.tools.nsc.symtab.Types$$Type.memberInfo(Types.scala:374)
	at scala.tools.nsc.symtab.Types$$TypeRef.relativeInfo(Types.scala:1283)
	at scala.tools.nsc.symtab.Types$$TypeRef.baseType(Types.scala:1396)
	at scala.tools.nsc.symtab.Types$$SubType.baseType(Types.scala:710)

== What expected ==

successful compilation

Comment by Gilles Dubochet [ 29/Aug/07 ]

Shorter example: abstract class M { type T def all4Impl[U](first: M

{type T <: U}

): Stream[M

{type T <: U}

] = Stream.cons(first, all4Impl(Stream.empty)) } [st�phane]

Comment by Gilles Dubochet [ 29/Aug/07 ]

The example now causes a type error:

bug1279a.scala:34: error: no type parameters for method all4ImplSI-4259: (MSI-3759{type TSI-4288 <: USI-4285})StreamSI-437[MSI-3759{type TSI-4291 <: USI-4285}] exist so that it can be applied to arguments (firstSI-4262.selfTypeSI-3770)
 --- because ---
result type StreamSI-437[MSI-3759{type TSI-4291 <: USI-4285}] is incompatible with expected type StreamSI-437[MSI-3759{type TSI-4264 <: USI-4261}]
    def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl(first.next))

Not ideal, but workable. I lowered priority but leave it open.


Comment by Martin Odersky [ 14/Jan/09 ]

Milestone postponed deleted

Comment by Paul Phillips [ 13/Aug/09 ]

The example given in the ticket compiles with trunk. The shorter example doesn't, but I think the reason is unrelated.

abstract class M { 
  type T 
  def all4Impl[U](first: M { type T <: U }): Stream[M { type T <: U }] =
    Stream.cons(first, all4Impl(Stream.empty))

Comment by Paul Phillips [ 02/Jul/10 ]

(In r22467) Test cases close SI-13, SI-95. No review.

(That's right, multiple two digit tickets.)

Comment by Adriaan Moors [ 16/Sep/10 ]

see test/files/pos/bug1279a.scala (and r23011)

Comment by Simon Ochsenreither [ 26/Apr/11 ]

With Scala version 2.10.0-20120430-094203-cfd037271e (OpenJDK 64-Bit Server VM, Java 1.6.0_24) in file test/files/pos/bug1279a.scala:

// TODO!!! fix this bug for real, it compiles successfully, but weird types are inferred
    def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl(first.next))

results in

<console>:34: error: type mismatch;
 found   : first.selfType
    (which expands to)  M{type T <: first.T}
 required: M{type T <: Nothing}
           def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl(first.next))

Does this change the status of the bug?

Comment by Paul Phillips [ 04/May/12 ]

Nope. I updated the test to make clearer what should happen. bbdd570ccc

Generated at Wed Dec 12 22:53:30 CET 2018 using JIRA 7.9.1#79001-sha1:60970b42586a2ec2760ed6cfe825b26961e62b9e.