NullPointerException on polymorphic and dependent function applied to itself

[panacekcz]

Code:

object O{
  val v = [T] => (y:T) => (x:y.type) => 3
  def m = v(v)
}

Output:

java.lang.NullPointerException while compiling ../../files/pdf.scala
Exception in thread "main" java.lang.NullPointerException
        at dotty.tools.dotc.core.Types$typeListDeco$.equalElements$extension(Types.scala:5190)
        at dotty.tools.dotc.core.Types$MethodOrPoly.iso(Types.scala:3043)
        at dotty.tools.dotc.core.Types$Type.equals(Types.scala:1572)
        at dotty.tools.dotc.core.Types$MethodOrPoly.equals(Types.scala:3034)
        at dotty.tools.dotc.core.Types$$anon$5.apply(Types.scala:3089)
        at dotty.tools.dotc.core.Types$$anon$5.apply(Types.scala:3085)
        at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$1(Types.scala:4903)
        at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:4907)
        at dotty.tools.dotc.core.Types$$anon$5.apply(Types.scala:3099)
        at dotty.tools.dotc.core.Types$$anon$5.apply(Types.scala:3085)
        at dotty.tools.dotc.core.Types$TermLambda.dotty$tools$dotc$core$Types$TermLambda$$depStatus(Types.scala:3102)
        at dotty.tools.dotc.core.Types$TermLambda.dependencyStatus(Types.scala:3116)
        at dotty.tools.dotc.core.Types$TermLambda.resultType(Types.scala:3059)
        at dotty.tools.dotc.core.Types$MethodType.resultType(Types.scala:3163)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4523)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4530)
        at dotty.tools.dotc.core.Substituters.subst(Substituters.scala:21)
        at dotty.tools.dotc.core.Contexts$Context.subst(Contexts.scala:71)
        at dotty.tools.dotc.core.Types$Type.subst(Types.scala:1452)
        at dotty.tools.dotc.core.Types$LambdaType.newLikeThis$$anonfun$2(Types.scala:3000)
        at dotty.tools.dotc.core.Types$PolyType.<init>(Types.scala:3373)
        at dotty.tools.dotc.core.Types$PolyType$.apply(Types.scala:3445)
        at dotty.tools.dotc.core.Types$PolyType$.apply(Types.scala:3442)
        at dotty.tools.dotc.core.Types$LambdaType.newLikeThis(Types.scala:3000)
        at dotty.tools.dotc.core.Types$MethodOrPoly.newLikeThis(Types.scala:3031)
        at dotty.tools.dotc.core.Types$LambdaType.derivedLambdaType(Types.scala:2995)
        at dotty.tools.dotc.core.Types$MethodOrPoly.derivedLambdaType(Types.scala:3031)
        at dotty.tools.dotc.core.Types$TypeMap.derivedLambdaType(Types.scala:4460)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4528)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4530)
        at dotty.tools.dotc.core.Substituters.subst(Substituters.scala:21)
        at dotty.tools.dotc.core.Contexts$Context.subst(Contexts.scala:71)
        at dotty.tools.dotc.core.Substituters$SubstBindingMap.apply(Substituters.scala:164)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4500)
        at dotty.tools.dotc.core.Substituters.subst(Substituters.scala:21)
        at dotty.tools.dotc.core.Contexts$Context.subst(Contexts.scala:71)
        at dotty.tools.dotc.core.Types$Type.subst(Types.scala:1452)
        at dotty.tools.dotc.core.Types$LambdaType.newLikeThis$$anonfun$3$$anonfun$1(Types.scala:2999)
        at scala.collection.immutable.List.mapConserve(List.scala:179)
        at dotty.tools.dotc.core.Types$LambdaType.newLikeThis$$anonfun$1(Types.scala:2999)
        at dotty.tools.dotc.core.Types$MethodType.<init>(Types.scala:3170)
        at dotty.tools.dotc.core.Types$CachedMethodType.<init>(Types.scala:3199)
        at dotty.tools.dotc.core.Types$MethodTypeCompanion.apply(Types.scala:3267)
        at dotty.tools.dotc.core.Types$MethodTypeCompanion.apply(Types.scala:3266)
        at dotty.tools.dotc.core.Types$LambdaType.newLikeThis(Types.scala:3000)
        at dotty.tools.dotc.core.Types$MethodOrPoly.newLikeThis(Types.scala:3031)
        at dotty.tools.dotc.core.Types$LambdaType.derivedLambdaType(Types.scala:2995)
        at dotty.tools.dotc.core.Types$MethodOrPoly.derivedLambdaType(Types.scala:3031)
        at dotty.tools.dotc.core.Types$TypeMap.derivedLambdaType(Types.scala:4460)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4528)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4530)
        at dotty.tools.dotc.core.Substituters.substParam(Substituters.scala:146)
        at dotty.tools.dotc.core.Contexts$Context.substParam(Contexts.scala:71)
        at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:192)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4528)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4530)
        at dotty.tools.dotc.core.Substituters.substParam(Substituters.scala:146)
        at dotty.tools.dotc.core.Contexts$Context.substParam(Contexts.scala:71)
        at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:192)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4500)
        at dotty.tools.dotc.core.Substituters.substParam(Substituters.scala:146)
        at dotty.tools.dotc.core.Contexts$Context.substParam(Contexts.scala:71)
        at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:192)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4516)
        at dotty.tools.dotc.core.Substituters.substParam(Substituters.scala:146)
        at dotty.tools.dotc.core.Contexts$Context.substParam(Contexts.scala:71)
        at dotty.tools.dotc.core.Types$Type.substParam(Types.scala:1468)
        at dotty.tools.dotc.core.OrderingConstraint.replaceIn$2(OrderingConstraint.scala:422)
        at dotty.tools.dotc.core.OrderingConstraint.replaceIn$1$$anonfun$1(OrderingConstraint.scala:420)
        at dotty.tools.dotc.core.OrderingConstraint.replaceIn$3$$anonfun$adapted$1(OrderingConstraint.scala:420)
        at dotty.tools.dotc.core.OrderingConstraint.recombineAnd$1(OrderingConstraint.scala:397)
        at dotty.tools.dotc.core.OrderingConstraint.replaceIn$2(OrderingConstraint.scala:420)
        at dotty.tools.dotc.core.OrderingConstraint.replaceParam$1(OrderingConstraint.scala:425)
        at dotty.tools.dotc.core.OrderingConstraint.replace$$anonfun$1$$anonfun$1(OrderingConstraint.scala:433)
        at dotty.tools.dotc.core.OrderingConstraint$ConstraintLens.map(OrderingConstraint.scala:77)
        at dotty.tools.dotc.core.OrderingConstraint.replace$$anonfun$4(OrderingConstraint.scala:433)
        at dotty.tools.dotc.core.OrderingConstraint.replace$$anonfun$adapted$1(OrderingConstraint.scala:435)
        at dotty.runtime.function.JProcedure2.apply(JProcedure2.java:15)
        at dotty.runtime.function.JProcedure2.apply(JProcedure2.java:10)
        at dotty.tools.dotc.core.OrderingConstraint.foreachParam$$anonfun$2$$anonfun$1(OrderingConstraint.scala:481)
        at dotty.runtime.function.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.java:12)
        at scala.collection.immutable.Range.foreach(Range.scala:158)
        at dotty.tools.dotc.core.OrderingConstraint.foreachParam$$anonfun$1(OrderingConstraint.scala:481)
        at dotty.runtime.function.JProcedure2.apply(JProcedure2.java:15)
        at dotty.runtime.function.JProcedure2.apply(JProcedure2.java:10)
        at dotty.tools.dotc.util.SimpleIdentityMap$Map1.foreachBinding(SimpleIdentityMap.scala:61)
        at dotty.tools.dotc.core.OrderingConstraint.foreachParam(OrderingConstraint.scala:481)
        at dotty.tools.dotc.core.OrderingConstraint.replace(OrderingConstraint.scala:435)
        at dotty.tools.dotc.core.OrderingConstraint.replace(OrderingConstraint.scala:382)
        at dotty.tools.dotc.core.Types$TypeVar.instantiateWith(Types.scala:3802)
        at dotty.tools.dotc.core.Types$TypeVar.instantiate(Types.scala:3814)
        at dotty.tools.dotc.typer.Inferencing.interpolateTypeVars$$anonfun$2(Inferencing.scala:429)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at dotty.tools.dotc.util.SimpleIdentitySet$Set2.foreach(SimpleIdentitySet.scala:69)
        at dotty.tools.dotc.typer.Inferencing.interpolateTypeVars(Inferencing.scala:437)
        at dotty.tools.dotc.typer.Typer.interpolateTypeVars(Typer.scala:87)
        at dotty.tools.dotc.typer.Typer.simplify(Typer.scala:2217)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2207)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2239)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2251)
        at dotty.tools.dotc.typer.Namer.typedAheadExpr$$anonfun$1(Namer.scala:1173)
        at dotty.tools.dotc.typer.Namer.typedAhead(Namer.scala:1163)
        at dotty.tools.dotc.typer.Namer.typedAheadExpr(Namer.scala:1173)
        at dotty.tools.dotc.typer.Namer.rhsType$2(Namer.scala:1308)
        at dotty.tools.dotc.typer.Namer.cookedRhsType$1(Namer.scala:1320)
        at dotty.tools.dotc.typer.Namer.lhsType$1(Namer.scala:1321)
        at dotty.tools.dotc.typer.Namer.inferredType$1(Namer.scala:1339)
        at dotty.tools.dotc.typer.Namer.valOrDefDefSig(Namer.scala:1347)
        at dotty.tools.dotc.typer.Namer.defDefSig(Namer.scala:1416)
        at dotty.tools.dotc.typer.Namer$Completer.typeSig(Namer.scala:760)
        at dotty.tools.dotc.typer.Namer$Completer.completeInCreationContext(Namer.scala:873)
        at dotty.tools.dotc.typer.Namer$Completer.complete(Namer.scala:786)
        at dotty.tools.dotc.core.SymDenotations$SymDenotation.completeFrom(SymDenotations.scala:239)
        at dotty.tools.dotc.core.Denotations$Denotation.completeInfo$1(Denotations.scala:180)
        at dotty.tools.dotc.core.Denotations$Denotation.info(Denotations.scala:182)
        at dotty.tools.dotc.core.SymDenotations$SymDenotation.ensureCompleted(SymDenotations.scala:345)
        at dotty.tools.dotc.typer.Typer.retrieveSym(Typer.scala:2103)
        at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2128)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2204)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2239)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2251)
        at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2270)
        at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2316)
        at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:1678)
        at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2141)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2204)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2239)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2251)
        at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2270)
        at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2316)
        at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:1802)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2181)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2205)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2239)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2251)
        at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2329)
        at dotty.tools.dotc.typer.FrontEnd.typeCheck$$anonfun$1(FrontEnd.scala:75)
        at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
        at dotty.tools.dotc.typer.FrontEnd.monitor(FrontEnd.scala:41)
        at dotty.tools.dotc.typer.FrontEnd.typeCheck(FrontEnd.scala:79)
        at dotty.tools.dotc.typer.FrontEnd.runOn$$anonfun$3(FrontEnd.scala:109)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at scala.collection.immutable.List.foreach(List.scala:392)
        at dotty.tools.dotc.typer.FrontEnd.runOn(FrontEnd.scala:109)
        at dotty.tools.dotc.Run.runPhases$4$$anonfun$4(Run.scala:158)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at scala.collection.IndexedSeqOptimized.foreach(IndexedSeqOptimized.scala:36)
        at scala.collection.IndexedSeqOptimized.foreach$(IndexedSeqOptimized.scala:33)
        at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:198)
        at dotty.tools.dotc.Run.runPhases$5(Run.scala:170)
        at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:178)
        at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
        at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:102)
        at dotty.tools.dotc.Run.compileUnits(Run.scala:185)
        at dotty.tools.dotc.Run.compileSources(Run.scala:120)
        at dotty.tools.dotc.Run.compile(Run.scala:104)
        at dotty.tools.dotc.Driver.doCompile(Driver.scala:34)
        at dotty.tools.dotc.Driver.process(Driver.scala:172)
        at dotty.tools.dotc.Driver.process(Driver.scala:141)
        at dotty.tools.dotc.Driver.process(Driver.scala:153)
        at dotty.tools.dotc.Driver.main(Driver.scala:180)
        at dotty.tools.dotc.Main.main(Main.scala)

[nicolasstucki]

It looks like we are trying to read an uninitialiezed field MethodType.paramInfos. If we make that field a lazy val there is a dead/live lock.

[liufengyun]

After some diagnosis, it seems to me this is a problem with the caching of TypeParamRef.

The following equivalent program compiles fine without any problem.

object O{
  val v = [T] => (y:T) => (x:y.type) => 3
  val u = [T] => (y:T) => (x:y.type) => 3
  def m = v(u)
}

More concretely, we are calling tp.substParam(param, replacement) with

tp = TypeVar(TypeParamRef(T)#3218 -> RefinedType(TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),trait PolyFunction),apply,PolyType#3217(List(T), List(TypeBounds(TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Nothing),TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Any))), MethodType#3219(List(y), List(TypeParamRef(T)#3218), AppliedType(TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),trait Function1),List(TermParamRef(y)#3220, TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Int)))))))
param = TypeParamRef(T)#3218
replacement = RefinedType(TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),trait PolyFunction),apply,PolyType#3217(List(T), List(TypeBounds(TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Nothing),TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Any))), MethodType#3219(List(y), List(TypeParamRef(T)#3218), AppliedType(TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),trait Function1),List(TermParamRef(y)#3220, TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Int))))))

Notice that TypeParamRef(T)#3218 appears in replacement, which is problematic.

Ping @smarter @odersky