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
Closed

futile implicit search fails to terminate #5318

scabug opened this issue Dec 16, 2011 · 6 comments
Assignees
Milestone

Comments

@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
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
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
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
Copy link
Author

scabug commented Jan 9, 2012

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

@scabug
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
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 as completed 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
Projects
None yet
Development

No branches or pull requests

2 participants