Cyclic errors when using exports

doofin commented 1 year ago

This is a very strange problem that only shows occasionally, I have no idea how to reliably reproduce it. updates: reproduced in https://github.com/lampepfl/dotty/issues/17076#issuecomment-1473922793 and https://github.com/lampepfl/dotty/issues/17076#issuecomment-1472721415

Compiler version

3.2.2

Minimized code

it can't be reproduced,that's why it's so strange. I copied this snippet to another project without giving any errors.

  sealed trait Expr[w <: Int]
  case class BinOp[w <: Int](a: Expr[w], b: Expr[w], nm: String) extends Expr[w]

Output

metals ide gives error below,and sbt also gives same error message:

the error message is

Overloaded or recursive constructor BinOp needs return type
Something's wrong: missing original symbol for type tree

Sometimes, it will give errors like "Cyclic reference involving val ..."

Expectation

code should compile

nicolasstucki commented 1 year ago

Could this be related to the incremental compilation?

nicolasstucki commented 1 year ago

@doofin when you get the error, have you tried to compile it manually from the terminal? Just to see if the error happens in general or within the current state of bloop.

doofin commented 1 year ago

@doofin when you get the error, have you tried to compile it manually from the terminal? Just to see if the error happens in general or within the current state of bloop.

I tried to compile with sbt manually (I have also clean/cleanFiles before compile) , and it's the same error

I feel it might be related to incremental compilation, but this scenario seems to suggest it's more than that

trying to search for "Overloaded or recursive constructor"(does that imply type constructors needs kind annotation?) gives no result in dotty codebase,there's only "Overloaded or recursive methods".

prolativ commented 1 year ago

@doofin would it be possible for you to provide the entire codebase of the project (assuming it's not confidential)? If not then maybe you could try creating a copy of the project and gradually removing portions of code until the problem stops occurring?

doofin commented 1 year ago

thanks @smarter to help me pinpoint the problem, it happens when some methods are not explicitly given type annotations like below:

extension [w <: Int](x: Expr[w]) {
  def +(oth: Expr[w]) = BinOp(x, oth, "+")
  def *(oth: Expr[w]) = BinOp(x, oth, "*")
  def -(oth: Expr[w]) = BinOp(x, oth, "-")
  def |(oth: Expr[w]) = BinOp(x, oth, "|")
  def &(oth: Expr[w]) = BinOp(x, oth, "&")
}

However, I copied this snippet to another project but still can't reproduce it. Will meet with @smarter for possible better error message when this happens.

doofin commented 1 year ago

Hi @prolativ I tried but it might be a bit hard to reduce it to minimul. The project might be open sourced in the future but is currently private. I have invited you to the project and feel free to take a look at https://github.com/doofin/dependentChisel/commit/101cf6d535f85f6634dd8adcbe86d191a55dbd29

smarter commented 1 year ago

I can reproduce the errors with:

object A {
  import B.*
  def foo(foo: Foo[Int]) = foo
}

object B {
  import C.*
  trait Expr[T <: Int]
  case class Foo[T <: Int](x: Any) extends Expr[T]
  def foo = Foo(0)
}

object C extends D.Foo[Int](0)

object D {
  export B.*
}

-- Error: try/i17076/A.scala:9:30 ----------------------------------------------
9 |  case class Foo[T <: Int](x: Any) extends Expr[T]
  |                              ^^^
  |                  Something's wrong: missing original symbol for type tree
-- [E044] Cyclic Error: try/i17076/A.scala:9:2 ---------------------------------
9 |  case class Foo[T <: Int](x: Any) extends Expr[T]
  |  ^
  |  Overloaded or recursive constructor Foo needs return type

The use of object C extends D.Foo[Int](0) is arguably problematic since we import C.* in the scope where we define Foo itself, but there isn't anything equivalent in the original codebase, so there's probably still something missing to trigger the problem in the same way it's triggered in the original codebase.

prolativ commented 1 year ago

@smarter I spent a few hours yesterday minimizing that and I almost got to this point but you turned out to be faster 😆

prolativ commented 1 year ago

Minimized slightly further:

got rid of trait Expr
got rid of wildcard exports
got rid of import B.*

object A {
  def bar(x: B.Foo[Int]) = x
}

object B {
  import C.*
  case class Foo[T <: Int](x: Any)
  def foo = Foo(0)
}

object C extends D.Foo[Int](0)

object D {
  export B.foo
  type Foo[T <: Int] = B.Foo[T]
}

odersky commented 1 year ago

We clearly should not complain about a missing return type in a constructor. We should fall back to the generic "cyclic reference involving...." error message instead.

That said, this looks like a legit cyclic reference error, no?

To process the export, you need to know the type of B.foo.
To know the type you need to process the RHS of B.foo.
To process the RHS you need to typecheck class B.Foo
To typecheck class B.Foo you need to analyze the import import C.* (for instance, it might define a type Int, which would take precedence over scala.Int.
To analyze the import, you need to find the members of C.
To find the members of C you need to analyze its parent, D.Foo
To analyze that parent you need to find the members of D.
To find the members of D you need to analyze the export.

There's your cycle.

robmwalsh commented 1 year ago

We clearly should not complain about a missing return type in a constructor. We should fall back to the generic "cyclic reference involving...." error message instead.

That said, this looks like a legit cyclic reference error, no?

To process the export, you need to know the type of B.foo.

To know the type you need to process the RHS of B.foo.

To process the RHS you need to typecheck class B.Foo

To typecheck class B.Foo you need to analyze the import import C.* (for instance, it might define a type Int, which would take precedence over scala.Int.

To analyze the import, you need to find the members of C.

To find the members of C you need to analyze its parent, D.Foo

To analyze that parent you need to find the members of D.

To find the members of D you need to analyze the export.

There's your cycle.

FWIW I think cyclic errors should be displayed like your comment (including "There's your cycle" ;) )

odersky commented 1 year ago

FWIW I think cyclic errors should be displayed like your comment (including "There's your cycle" ;) )

Yes, this would be great! I don't yet see an easy way to do it, though. Essentially, the compiler would have to keep a log of everything it does which would have to be inspected in case of a Cyclic Reference. That looks expensive, in both time and code complexity...

robmwalsh commented 1 year ago

FWIW I think cyclic errors should be displayed like your comment (including "There's your cycle" ;) )

Yes, this would be great! I don't yet see an easy way to do it, though. Essentially, the compiler would have to keep a log of everything it does which would have to be inspected in case of a Cyclic Reference. That looks expensive, in both time and code complexity...

I don't think recording all steps the compiler takes would be necessary, wouldn't we just need the steps that the cyclic reference check does? Couldn't this be done in a similar way to zio 2.x's stack reification? If you're unfamiliar with it, basically it tries to make progress recursively in a try catch block (it looks like the implementation for checking cyclic references is already doing this) and if it needs to yield, it throws a ReifyStack exception which contains a ChunkBuilder. This is caught at every level of recursion, adding the effect to the ChunkBuilder and rethrowing the ReifyStack exception. When it gets to the first try/catch, the exception contains the whole stack which is turned into a chunk and sent back to the scheduler. I think a similar approach may be used here which means basically no overhead unless there's a cyclic error. Do you think this approach may be feasible or am I missing something here?

odersky commented 1 year ago

We do similar stack reification when we emit "a recurring operation is" diagnostics. But we can't directly use it for cyclic references (at least not as a default) since we are not allowed to unwind the stack to the root of the problem. Instead, we continue reporting close to where the cyclic reference was detected.

scala / scala3