_ => _ should be a valid way to write Function1[_, _]

[smarter]

This works in scalac but not in dotty:

val x: _ => _ = (x: Int) => 1
val y: (_ <: Int) => _ = (x: Int) => 1

Real-world usage: https://github.com/functional-streams-for-scala/fs2/blob/series/0.9/core/src/main/scala/fs2/Chunk.scala#L321

[smarter]

Note: I'm thinking that we could leave this one open for a bit and others like it for new contributors in the spirit of https://starters.servo.org/

[cswinter]

It looks like you cannot have existentials within infix types. E.g. this won't work either:

val x: Int Either _ = Left(10)

[cswinter]

I suppose this is caused by an unrelated issue, but when I run the initial example using Function1[_, _] instead of _ => _ with dotr (or dotc), the console will freeze for tens of seconds with CPU at 100% and then report this error (sometimes it OOMs instead):

scala> val x: Function1[_, _] = (s: String) => 1 
                                        ^
val x: Function1[_, _] = (s: String) => 1
<console>:4: error: type mismatch:
 found   : Int(1)
 required: 

[odersky]

@cswinter Thanks for exploring this. The unrelated issue is fixed in #1402.

[cswinter]

I've investigated some more, and I believe that at the core of this problem (and also of #1403) is an incomplete attempt of rejecting unbound wildcard types at the grammar level.
Basically, wildcards are only allowed in the ArgType production which is used instead of Type inside tuple types and type parameter lists, but which is not available to other types (including infix types). We can easily fix #1396 by e.g. widening the grammar through merging the ArgType and SimpleType productions. Of course then we also allow things like val a: _ = ??? (this is currently rejected as unbound wildcard by scalac, and causes dotty to hang and eventually oom). Note that it is already possible to define constructs like this in dotty by working around the grammar restriction using singleton tuples (this is essentially what #1403 does). E.g. all of these are currently accepted by the parser:

val f: (_) => (_)          // compiles
val a: (_) = 1             // #1403. compiler hangs, then cryptic error message/oom
def wut(x: (_)): Int = 1   // compiles
wut(???)                   // compiler hangs, then oom

I haven't yet tried to figure out whether there is a good way to fix the grammar to prevent this. It does seem like it may require some amount of contextual knowledge, so it might be more appropriate to do this in a mini phase. Would be interesting to find out how scalac solves this.

(Out of curiosity, is there a reason that makes unbound wildcard types inherently unsound, or do we just prevent them because they are pointless/annoying? While they are largely useless and currently break dotty in various ways, it does seem like they could have meaningful semantics. There also exists (somewhat) legitimate Scala code that will give you values that are essentially wildcard typed, e.g. Map[Int, Int => _](0 -> ((x: Int) => "string")(0)(0) is valid Scala code which has type Any in scalac, and type (Int => _)#R in dotty.)

[smarter]

Nice analysis!

val a: (_) = 1 // #1403. compiler hangs, then cryptic error message/oom

The expression val a: (_) = 1 cannot typecheck because the type of _ is represented internally as an instance of TypeBounds which is used to represent bounds but is not a valid type for a value (it can only be part of another type like Foo[_]) so it can never be a supertype of the type of 1.
As a side note, the compiler hangs because it's spending a huge amount of time looking for an implicit conversion that would make the expression typechecks, I've seen this behavior in other situations and believe there's a bug here, we shouldn't spend that much time looking for implicits. A workaround is to hide the implicits that are imported by default by putting import Predef.{assert => _} on top of the file (-Yno-predef should work too but results in a crash, another bug!).

Out of curiosity, is there a reason that makes unbound wildcard types inherently unsound, or do we just prevent them because they are pointless/annoying?

I don't think there's anything unsound about unbound wildcards, in Scala 2 you can write val x: T forSome { type T } = 1 and it will compile, T forSome { type T >: L <: H } is equivalent to _ >: L <: H (in dotty we don't accept the forSome syntax which allows more general existentials).
I can't think of any case where having unbound wildcards would make your code better or clearer in any way, on the other hand misusing them is easy, so I'm not in favor of supporting them.

Would be interesting to find out how scalac solves this

As far as I can tell this is all done in the parser: https://github.com/scala/scala/blob/20dd825ec6b5d4015ce36cf4373ba1c1d917da94/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala#L463-L521

[cswinter]

Something like this might actually fix the grammar, but it makes InfixType left-recursive and I think associativity becomes ambiguous.

InfixType  ::= ArgType id [nl] ArgType
             | RefinedType
SimpleType ::= ...
             | `(' ArgType `,' ArgTypes `)'
             | `(' SimpleType `)'

For the tuple case in SimpleType, we could also just check that ArgTypes is not a single wildcard type, and similarly use the following grammar with an additional check that we don't get a wildcard type for InfixType. This actually seems like it could be a good solution.

InfixType    ::= WildcardType {id [nl] WildcardType}
WildcardType ::= RefinedType
               | `_' TypeBounds

Edit: Hmm, things like List[(_)] wouldn't work anymore though. Will have to give this some more thought.

[odersky]

I think what scalac does, and what we could try ourselves as well, as treat wildcards in types analogous to wildcards in expressions. I.e. the grammer allows them everywhere. But then there is a check at top-level types that they are not a TypeBoundsTree.

[cswinter]

Yes, that sounds much cleaner. I'll start working on a patch.

[cswinter]

I have a basic prototype now. Is there any documentation for the tests? Specifically, I would like to know where should I put my test files, and how to check that some code will result in a specific compile error.

I also found another amusing edge case. The following compiles in scalac (with type List[_]) and causes an assertion error in dotty:

val lolwut: List[_ <: _ <: _] = List(10)

Do we want to mimic this behavior (i.e. allow wildcards in type bounds), or should we just reject this from now on? (scalac does already reject constructs like def id[T <: _](x: Int): Int = x.)

[odersky]

@cswinter There are three main test directories: pos, neg and run.

pos tests only need to compile.

neg tests need to produce errors on the lines marked with // error. Multiple expected errors on one line need multiple // error markers on the right.

run tests need to compile and run. If there is output it needs to match the one in the .check file.

Hope this helps.

By the way, the curried lambda problem you noted on gitter should be fixed in #1409.

[odersky]

@cswinter

Do we want to mimic this behavior (i.e. allow wildcards in type bounds), or should we just reject this from now on? (scalac does already reject constructs like def id[T <: _](x: Int): Int = x.)

I lean towards reject. In:

val lolwut: List[_ <: _ <: _] = List(10)

I would classify bound types as top-level types, which cannot be wildcards.

[cswinter]

My code is essentially ready for review now, there is just one remaining issue. When you compile a program that contains unbound wildcard types (e.g. my tests), the parser emits the expected syntax errors (using Parser.syntaxError(String, Position)). And then the compiler goes ahead and continues with compilation which causes it to die a slow and horrible death to the various issues caused by unexpected TypeBounds.

I'm not quite sure about the desired behaviour here. Do we want to modify later compiler stages to cope with unbound wildcard types? Or is there a way to issue a "hard" syntax error and just abort? One hack that I've tried and which seems to work pretty well is returning Ident(names.typeName("Any")) instead of unbound wildcards.

[smarter]

@cswinter: I suggest you first make a PR with just your fix and a neg test that demonstrates that the code does not compile, if the compiler just takes more time to finish that test than expected, that's OK, we already have a few tests like this, and we need a general solution to that problem (the long time spent in implicit search that I mentioned above)

[smarter]

Also you might have seen this already but I just realized that our parser has a checkNoEscapingPlaceholders function like the scalac one, except we only track wildcards in terms and not types in ours, so we can just extend that to also track types.

[cswinter]

So the problem is that the tests don't even pass because the compiler crashes with an assertion error. What I can do is comment out the tests and create a new issue to track that problem separately, but it might make more sense to wait for a fix/include it with this changeset.

I don't think we should try to reuse checkNoEscapingPlaceholders; semantically and syntactically placeholders are quite orthogonal to wildcard types and require different processing (like tracking the index). But have a look at the pull request and let me know what you think.