Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

futile implicit search fails to terminate #5318

Closed
scabug opened this Issue Dec 16, 2011 · 6 comments

Comments

Projects
None yet
2 participants
@scabug
Copy link

scabug commented Dec 16, 2011

class CompilerHang {
  trait TC[M[_]]
  trait S[A]

  implicit def tc[M[_]](implicit M0: TC[M]): TC[S] = null
  def breakage[F[_] : TC] = 0
  breakage  // type checker doesn't terminate, should report inference failure
}

This gives SOE with the repeated section:

	at scala.tools.nsc.Global$$anon$1.inferImplicit(Global.scala:401)
	at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:120)
	at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:115)
	at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:59)
	at scala.collection.immutable.List.foreach(List.scala:77)
	at scala.tools.nsc.typechecker.Typers$Typer.applyImplicitArgs(Typers.scala:115)
	at scala.tools.nsc.typechecker.Typers$Typer.adaptToImplicitMethod$1(Typers.scala:747)
	at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:895)
	at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:893)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.typedImplicit1(Implicits.scala:524)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.typedImplicit0(Implicits.scala:486)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.scala$tools$nsc$typechecker$Implicits$ImplicitSearch$$typedImplicit(Implicits.scala:398)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.tryImplicitInfo$1(Implicits.scala:740)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.rankImplicits(Implicits.scala:743)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.findBest(Implicits.scala:767)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.searchImplicit(Implicits.scala:825)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.bestImplicit(Implicits.scala:1157)
	at scala.tools.nsc.typechecker.Implicits$class.inferImplicit(Implicits.scala:67)
	at scala.tools.nsc.Global$$anon$1.inferImplicit(Global.scala:401)

Similar code without a type constructor as a type parmaeter reports the divergent implicit failure correctly:

class DivergingImplicitReported {
  trait TC[M]
  trait S

  implicit def tc[M](implicit M0: TC[M]): TC[S] = null
  def breakage[F: TC] = 0
  breakage // correct: diverging implicit expansion
}

It looks like a pathological case, but it's based on some real life implicits from Scalaz. Possibly the underlying problem of: https://scala-ide-portfolio.assembla.com/spaces/scala-ide/tickets/1000674

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Dec 16, 2011

Imported From: https://issues.scala-lang.org/browse/SI-5318?orig=1
Reporter: @retronym
Affected Versions: 2.9.1, 2.10.0
Other Milestones: 2.10.0

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jan 9, 2012

Kris Nuttycombe (nuttycom) said:
This bug is causing ReportGrid major hassles - in one piece of our current development work, we seem to hang the compiler on this bug in probably 25% of our build attempts. We're able to work around it by explicitly annotating every type, but this can be pretty challenging with the complexity of some of our types - in numerous places, the volume of type annotations is several times as large as the code being annotated.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jan 9, 2012

@djspiewak said:
I can reproduce this bug on the current HEAD (2.10.0.rdev-4148-2012-01-09-g820491e) simply by dropping the snippet into the repl in :paste mode. Interesting sidebar: it no longer hangs in head, but stack overflows.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jan 9, 2012

@paulp said:
I fixed it, will check in shortly.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jan 10, 2012

@paulp said:
More slippery than I thought. For now I only note what is happening: when searching for the implicit parameter M0, the method tc is seen as eligible, and it recursively keeps trying to satisfy it with itself. The symbols are cloned each time in adapt and so new ones keep showing up. The mechanism which normally prevents this fails to do so when type constructors are used this way.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 13, 2012

@retronym said:
Here's a two line patch to fix this. I haven't run the full test suite yet, and I'm not totally happy with those two lines, but it at least pinpoints the problem.

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

@scabug scabug closed this May 26, 2012

@scabug scabug added this to the 2.10.0-M3 milestone Apr 7, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.