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

Pattern match typing fail in for comprehension #7222

Open
scabug opened this issue Mar 6, 2013 · 10 comments
Open

Pattern match typing fail in for comprehension #7222

scabug opened this issue Mar 6, 2013 · 10 comments
Labels
Milestone

Comments

@scabug
Copy link

scabug commented Mar 6, 2013

This is a regression from 2.10.0

 $ ~/Downloads/scala-2.10.1-RC2/bin/scalac -d /tmp fred.scala 
fred.scala:4: error: constructor cannot be instantiated to expected type;
 found   : (T1, T2)
 required: scala.util.Either[Nothing,(String, String)]
      (a, b) <- foo.right
      ^
fred.scala:6: error: not found: value a
      a + b
      ^
two errors found


On Tue, Mar 5, 2013 at 6:20 PM, Fredrik Ekholdt wrote:
Hey guys!

This fails in 2.10.1-20130225-100 (3.0-RC1) but not when compiling in sbt with 2.10.0 - is that expected?

object Foo {
    val foo: Either[String, (String, String)] = Left("")
    for {
      (a, b) <- foo.right
    } yield {
      a + b
    }
}
@scabug
Copy link
Author

scabug commented Mar 6, 2013

Imported From: https://issues.scala-lang.org/browse/SI-7222?orig=1
Reporter: @JamesIry
Affected Versions: 2.10.1-RC3, 2.10.1
See #5589, #6968

@scabug
Copy link
Author

scabug commented Mar 6, 2013

@JamesIry said (edited on Mar 6, 2013 2:36:40 PM UTC):
The regression existed in 2.10.1-RC1

@scabug
Copy link
Author

scabug commented Mar 6, 2013

@JamesIry said:
Adriaan is looking at some strange types in the desugaring.

@scabug
Copy link
Author

scabug commented Mar 6, 2013

@JamesIry said:
Part of the problem is that Either.RightProjection.filter has the wrong signature

def filter[X](p: (B) ⇒ Boolean): Option[Either[X, B]]

That X is unneeded and causes the Nothing

@scabug
Copy link
Author

scabug commented Mar 6, 2013

@JamesIry said:
Okay, looking through all the Either code, and actually giving it some thought.

map and flatMap on projections should return the same projection type. That's because we expect map/flatMap to be chain-able. And, you know, Functor, Monad, that stuff.

filter on Either has entirely the wrong signature and basically could only ever work accidentally. Because it returns an option, future map/flatMap stuff in the chain is on the option and that's just wrong. Filter, like map and flatMap, shouldn't change the type.

A filter with the right signature (one that returns a projection) doesn't make sense as-is because there's no zero for an Either or its projections, i.e. no equivalent of an empty List, or a None.

We can always hack in a filter that throws an exception on mismatch, but that's ugly. Or we could add a zero to Either so that Either[String, String] is Right | Left | F-You, but that's outside the normal contract of Either and frankly is better done as Option[Either[A, B]] instead.

@scabug
Copy link
Author

scabug commented Mar 6, 2013

@JamesIry said:
To close the loop, the issue is that both the spec and the 2.10.1 compiler say that the original pattern isn't "irrefutable" so the compiler emits a filter call which leads to the crap show in the previous comment which just happens to sorta work in this simple case.

In 2.10.0 refutability checking was broken and would let too much stuff in without emitting the filter. That would lead to runtime failures. So we don't want to revert that fix.

In 2.11 we can change the Either API to be sane but unless we define an insane filter method (that throws an exception or produces a dummy "empty" Either on mismatch) then the resulting Either still won't be usable in refutable for comprehensions.

It would be nice if the refutability checker could be speced so that patterns like the above are irrefutable so that no filter was necessary.

@scabug
Copy link
Author

scabug commented Mar 6, 2013

@retronym said:
Dup of #5589, no?

@scabug
Copy link
Author

scabug commented Mar 6, 2013

@retronym said:
Refutability doesn't make sense without types, you can't type without a filter call, ergo, you can't use refutability in this case.

I've spent a bit of time talking to Martin about this when I was investigating #6968. It's a can of worms. null brings additional wrinkles.

A few new ideas: Either#RightProjection could define a dummy filter method that was somehow annotated to blowup if it still existed in the tree post-refchecks (when proper irrefutability analysis is possible.)

Oh yeah, the idea of eliding the filter call in refchecks after determining irrefutability is was effectively neutered when withFilter was introduced, as qual.withFilter(...) and qual have different types, so any subsequent calls are invalid if you blindly remove withFilter. We only seemed not to notice that problem because the irrefutability check was busted. It was even more busted in 2.11 because it assumed that pattern matching translation hadn't happened yet.

Did I mention canned worms? It all comes down to blindly making decisions about the for rewriting without types.

Oh well, at least the Haskell guys have a similar problem :)

http://thread.gmane.org/gmane.comp.lang.haskell.cafe/15656/focus=15666

@scabug
Copy link
Author

scabug commented Mar 7, 2013

@adriaanm said:
To explain more precisely, in the 2.10.0 window, a for-comprehension with a tuple-pattern binding that consists strictly of variables (or wildcards) erroneously did not result in a call to withFilter (or, in casu, filter). The translation was performed on a purely syntactic basis, but would lead to unexpected MatchErrors as illustrated by Jason:

// 2.9.2, 2.10.1
scala> for ((a, b) <- List[Any](0)) yield a
res0: List[Any] = List()

// 2.10.0
scala> for ((a, b) <- List[Any](0)) yield a
scala.MatchError: 0 (of class java.lang.Integer)

If we leave the 2.10.0 bug in place, we let buggy code that could only have been written in the couple of months that 2.10.0 is out, fester until we fix it in 2.11.

As always, we're talking trade-offs here. I did not intend "drop-in replacement" as a legal term. I should have qualified it with "modulo bad bugs that are expected to cause more pain than sticking to our doctrine".

So, to get back to your example, as soon as the pattern becomes non-trivial, 2.10.0's behavior matches that of 2.9/2.10.1:

scala> object Foo {
     |     val foo: Either[String, (String, String)] = Right(("a", "b"))
     |     def res = for {
     |       ("a", b) <- foo.right
     |     } yield {
     |       b
     |     }
     | }
<console>:10: error: constructor cannot be instantiated to expected type;
 found   : (T1, T2)
 required: scala.util.Either[Nothing,(String, String)]
             ("a", b) <- foo.right
             ^

This is because the signature of RightProjection's filter is not what you might expect: it returns an Option[Either[A, B]], so the subsequent map must deal with a full Either, not just the element on the right. I had to desugar the for comprehension to make it work because this kind of definition of filter just doesn't work with for comprehensions (it can't change the "type in the monad". There, I said "monad".).

scala>   foo.right filter {
     |     case ("a", b) => true
     |     case _ => false
     |   } map {
     |     case Right((a, b)) => a + b
     |   }
<console>:12: warning: match may not be exhaustive.
It would fail on the following input: Left(_)
                } map {
                      ^
res1: Option[String] = Some(ab)

@scabug scabug added the patmat label Apr 7, 2017
@scabug scabug added this to the Backlog milestone Apr 7, 2017
@scala scala deleted a comment from scabug Mar 2, 2018
@SethTisue
Copy link
Member

SethTisue commented Apr 5, 2023

The problem remains in 2.13 (and 3), even if you drop the .right now that Either is right-biased. I don't know if anyone has explored the consequences of adding .filter (and .withFilter) to Either — does the right-biasing make it feasible...?

In any case, the error is now sensible, so perhaps this isn't even really the same issue anymore.

(I've looked this over cursorily — consider it an invitation to anyone interested to think about it harder and decide if there are currently two issues here, or one, or zero.)

@SethTisue SethTisue added library and removed patmat labels Apr 5, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants