`_ => _` 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.