Zinc doesn't support wildcard-imported 'name' and 'implicit' shadowing

[jvican]

This issue is ported from sbt/sbt https://github.com/sbt/sbt/issues/1751.

Problem

In essence, Zinc is unable to register dependencies of shadowed names coming from two wildcard imports. This means that this situation is not handled correctly:

// A.scala
import p1._
import p2._
class A {
  val b = new B()
}

// p1.scala
package p1 {
  class B
}

// p2.scala
package p2 {
  // Uncomment in next iteration -> Zinc doesn't recompile A
  // class B
} 

The problem is that p2 definitions shadow p1's and it's not possible for Zinc to know that beforehand. Zinc only know what the compiler knows, and since we don't see any reference to p2.B, the dependency on that B will never be registered.

Possible solutions

What can we do about this? I'm afraid there's nothing to do.

The name hashing algorithm buys us a very good tradeoff to detect dependencies, but the only constraint is that dependencies are explicit throughout the trees of a given compilation unit (which is the case for every used definition).

There is no way to detect this new dependency reasonably because we don't know if it will ever happen, and therefore we need to guard us against any instance that could introduce it.

To support this use case, we would need to register phantom dependencies on all used names coming from imports used in all the enclosing scopes of a given wildcard import, for every name that is not defined in the imported symbol. In our example, we would get all the members of p1 that are not defined in p2 and create a "phantom" dependency on that name as if it were defined inp2 (and bail out if it's defined).

For the sake of correctness, we should do that for every member defined in p1 and any wildcard import that is present in an enclosing scope. Then, the easy part: our algorithm would identify those "phantom" dependencies when changes in API happen. If the API introduces a member with the target name of the "phantom" dependency, the sources that introduced the dependency should be recompiled.

But hey, we're not done yet. We also need to register phantom dependencies on names coming from inherited classes and defined present in enclosing scopes (e.g. nested objects have access to all the names in enclosing classes, so if we use a wildcard import inside that object, we need to register phantom dependencies on the symbol of the Import node for every accessible name). How fun!

At this point, we realise that supporting this use case is totally unfeasible. The complexity of the algorithm and the memory required to host those phantom dependencies would be very big, especially given:

• The frequency in which wildcard imports happen in Scala code.
• The large number of definitions present in any scope.
• The complex scoping rules that Scala has.

With this, I suggest that Zinc does not handle this use case. To our defense, I will say that this is a pretty intricate bug, difficult to find in any Scala codebase, and whose fix would render Zinc highly inefficient and slow, plus add a bunch of code that anyone would ever want to touch.

To our attentive reader, if there's something you should remember, this is it: Avoid wildcard imports + name shadowing, Zinc won't do the right thing.

EDIT: This problem has been generalized a little bit since it was reported. Implicit shadowing is not supported either. This happens when a new implicit member is introduced and affects the final result of implicit resolution, but there is no way for Zinc to know that it does so.

[jvican]

I am marking this as wontfix. I'm happy to reconsider if someone finds a better solution than the one I proposed or any issues with my explanation.

[romanowski]

I run few tests and is seems that that is only the case where we are dealing with classes that comes from packages (package objects or plain objects are handled correctly).

I should soon create PR with improvements around sealed class (now adding new child recompiles every usage of sealed class but should only recompile pattern matching) and we based fix for this problem on that.

[dwijnand]

Sounds to me like what @romanowski says does contest the "wontfix". So dropping. Optimistically :)

@jvican Are you aware of the different strategies that zinc used over time? The original one, the name-hashing and the class-based name-hashing. Could you tell me if this bug is more or less fixable depending on the strategy used?

[romanowski]

I think scope of dependency (class based name hashing is all about) does not matter since it is also present if we have only one class per source file (and in that case there is no difference in both name hashing).

@dwijnand Fix for this will probably require some serious changes in hash computation (since we need to aggregate hash for package across all dependencies no just for single source (either single jar or outer project).

[jvican]

I didn't say that scoping from nested classes is not supported, it is supported indeed. At the moment you modify one source file, the whole source file will be recompiled again, so if you define values in outer scopes that are used in inner scopes, you'll always get the right dependency.

The problem with scoping comes when you have open-ended features like wildcard imports. Because these imports could shadow any name in the scope, Zinc is not capable of recognising them.

@dwijnand Yes, I'm aware of the different strategies. In my view, the previous and overly pessimistic strategy worked because Zinc was overcompiling. But in this case, we have a more fine-grained algorithm that avoids overcompiling at any cost and aims at a higher precision.

I was thinking how this could be solved with more complex and better techniques, like the call-graph, and my conclusion is that this is not possible. So, in conclusion, my ticket only refers to wildcard imports + scoping together, not separately.

[dwijnand]

Yes, I'm aware of the different strategies.

I should have clarified: I'm a noob; I was asking because I'm not aware of the exact differences between them.

In my view, the previous and overly pessimistic strategy worked because Zinc was overcompiling. But in this case, we have a more fine-grained algorithm that avoids overcompiling at any cost and aims at a higher precision.

At the cost of this bug. Hopefully Krzysztof is able to fix this, because I don't consider wildcard imports "evil" and don't want to give them up because of zinc.

[jvican]

@dwijnand No, there's no issue using wildcard imports in cases where name shadowing doesn't exist, that's why the title of this issue says "wildcard imports + name shadowing".

If you use wildcard imports effectively, you will always register its dependencies with Zinc. Why? Because of two things:

• The Scala compiler will expand some paths and use Selects chains.
• The Scala compiler will fill in the trees with symbol information that will allow you to know that a certain name comes from a concrete path.

So, using wildcard imports is totally okay. What it's not okay is that you introduce a new name on a wildcard import that shadows an existing name at the use-site. In that case, Zinc cannot register the dependency for the reasons explained above.

I'm not a fan of wildcard imports because of these hard-to-spot subtleties. I was trying to fix this issue, but I found out it's not possible.

@dwijnand Regarding the previous strategy, AFAIK, any reference to a previous class meant that the source file defining it had to be recompiled. There was no fine-grained control over what kind of dependency we were handling.

I'd like to retract what I said before about the previous Zinc algorithm. After giving it some more thought, I think that not even the previous algorithm was handling this case.

[dwijnand]

I'd like to retract what I said before about the previous Zinc algorithm. After giving it some more thought, I think that not even the previous algorithm was handling this case.

Ok. Thanks. It's not a regression in behaviour then.

What it's not okay is that you introduce a new name on a wildcard import that shadows an existing name at the use-site. In that case, Zinc cannot register the dependency for the reasons explained above.

That's clearer. Thanks. I wouldn't be surprised if that still happens a bunch in some codebases. But it's definitely a lot less than I thought.

[jvican]

But it's definitely a lot less than I thought.

Yeah, exactly, that's why I said that it's a intricate behaviour that would rarely happen. IIRC, some small corners in ScalaJS rely on this, but they are so small that should not suppose any issue. The reason for ScalaJS to use this feature interaction is, I think, for patching stuff and making it compatible with any Scalac version (Scalajs hasn't broken compatibility since first release).

[dwijnand]

#267 "Implement used scopes for used names and implement PatMat scope" (now merged!) states

In future this mechanism can be used in #227 #226

So I guess this is no longer "wontfix"?

[jvican]

I already explain in #267 that those have nothing to do with this. This won't be ever fixed.

[jvican]

No, didn't explain it in the ticket but the Gitter channel. I'll post link later for future reference.

[dwijnand]

I'll post link later for future reference.

Excellent. Thank you.

[xuwei-k]

Is this same issue?

https://github.com/xuwei-k/sbt-incremental-compiler-bug/commit/6976731454879eb117bcd809839858bdb4aed355

[jvican]

At first glance, no, I don't think so. Is this happening with Zinc 1.0?

If so, can you open a new issue in this repo? Otherwise, can you do it in the sbt repo? If it's a Zinc 1.0 error, I'll look into it and do a deeper diagnosis of this error.

[romanowski]

I fear root of problem may be the same since every class has a 'wildcard import' from its package(s) (but I need to confirm that).

[jvican]

I fear root of problem may be the same since every class has a 'wildcard import' from its package(s) (but I need to confirm that).

@romanowski Yes, typer definitely puts into scope all the names that are known to be defined under a package foo. If you're curious about that, have a look at Contexts.scala: https://github.com/scala/scala/blob/2.12.x/src/compiler/scala/tools/nsc/typechecker/Contexts.scala.

@xuwei-k Actually, yes, your issue is basically reproducing the situation that I describe in the description. I missed the package y in the createFoo task.

[romanowski]

Problem manifested in another form (please correct me if I am not right): https://github.com/romanowski/zinc/commit/82d660cf2f245da400ab68a145b1f3ed21f83046

No wildcard used here :)

Do want me to PR this test?

[jvican]

Hey @romanowski, excellent! You found another instance of the same problem. Let's try to generalize the title of this ticket. I would name the new instance "implicit shadowing". Let me know if you agree with it.

Regarding the PR, feel free to, but I wouldn't see it as necessary since there is no way we can fix this in the current name-hashing algorithm without making Zinc substantially slower :smile:. Test cases are great when we can fix them!

[jvican]

Note that the issue with implicit resolution only happens because we're declaring an implicit in a package object, which following the SLS (Scala Language Specification) is always auto-imported in sources defined in the same package name. Any change that requires a source change in the file that triggered implicit resolution would be perfectly handled.

Note also that if you import an implicit name and then you declare an implicit with higher priority in a wilcard imported scope, Zinc will not recompile that source file triggering implicit resolution. This is just a subset of the problem described in the description of the ticket, but it's worth a redundant explanation.

[romanowski]

always auto-imported in sources defined in the same package name

Not in this case. The problem here is that we've got unused import on type foo,Foo and later on I am creating implicit val Foo in package `foo.

Anyway, should I do a PR? :)

[jvican]

Not in this case. The problem here is that we've got unused import on type foo,Foo and later on I am creating implicit val Foo in package `foo.

Yes in this case :smile:. You're adding that implicit to a package object that requires no import in the original file to be in scope. Package objects are always auto-imported in packages with the same namespace. I say that it's auto-imported or wildcard-imported because defining members in package object has the same effect, even if they don't use _ at the use site.

That will also happen if you do the following:

package foo
package bar.baz

class Baz

Separate package definitions (in different lines) auto-import members in the use site. For instance, Baz will have access to all member ofsfoo, even if there's no wildcard import.

Anyway, should I do a PR? :)

PR it :wink:, but I don't know an efficient solution to this problem.

[romanowski]

I think we are will be forced to hash packages entries. I think we can do it without much overhead (for sure there will be some).

Anyway we need to at least try to solve this.

[romanowski]

PR created: https://github.com/sbt/zinc/pull/289

[pauldraper]

Example:

mkdir project
echo sbt.version=1.2.3 > project/build.properties
echo import example._ > A.scala
echo 'class A {}' >> A.scala
echo 'class B {}' > B.scala
sbt compile # fail

echo package example > Example.scala
echo 'class Example' >> Example.scala
sbt compile # succeed

rm Example.scala
sbt compile # succeed

[liufengyun]

It seems macros and shadowing are two dark areas of incremental compilation. I think wontfix is an acceptable solution, as (1) the problem is not frequent; (2) programmers may always do a clean compile to remove all problems.

It would be nice that

• when programmers publish artifacts, SBT always forces a clean build.
• In the SBT build documentation, make programmers aware of the case of dirty cache, and instruct them how to deal with that.