typesafe contains: FLY IN OINTMENT

[Paul Phillips]

We should know better than to question Our Lord Variance.

If I can make contains final I can mostly avoid it, and I can catch ClassCastException, but the first requires "deprecated non-final" and with the second you can't help but grit your teeth.

scala> class Bippy extends Seq[Int] { override def contains(x: Int) = false ; def iterator = Nil.iterator ; def apply(idx: Int) = ??? ; def length = 0 }

defined class Bippy

scala> var x: Seq[Any] = new Bippy

x: Seq[Any] = ()

scala> x contains "blue"

java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

at scala.runtime.BoxesRunTime.unboxToInt(Unknown Source)

at Bippy.contains(<console>:7)

at .<init>(<console>:10)

[Simon Ochsenreither]

Actually, I can see nothing wrong with the current behavior.

[Josh Suereth]

That contains is overriding the "root laws of Variance" IIRC.   i.e. contains takes "Any" because A is not in a covariant location...

It appears to me your contains should be a *overload* not an override.....

I'm not quite sure what's happening there though....

- Josh

[Jan Vanek]

On 09.10.2012 19:53, Paul Phillips wrote:

We should know better than to question Our Lord Variance.

If I can make contains final I can mostly avoid it, and I can catch ClassCastException, but the first requires "deprecated non-final" and with the second you can't help but grit your teeth.

scala> class Bippy extends Seq[Int] { override def contains(x: Int) = false ; def iterator = Nil.iterator ; def apply(idx: Int) = ??? ; def length = 0 }

defined class Bippy

Looks like contract violation, the @unckeckedVariance needs to be required in the override, and probably even disallow concrete type (Int). But I'm not sure, it is very hard to think about half-solutions :-)

[Paul Phillips]

On Tue, Oct 9, 2012 at 11:08 AM, Josh Suereth <joshua....@gmail.com> wrote:

That contains is overriding the "root laws of Variance" IIRC.   i.e. contains takes "Any" because A is not in a covariant location...

Well that's the thing, it doesn't take Any after I change it not to take Any - that's the change under discussion.  The inherited implementation looks like

  def contains(x: T @uncheckedVariance): Boolean

Since in Bippy, all Ts are Ints, the override signature is correct.

The implication is that you can't place @uncheckedVariance on a parameter unless the method is final, because you have to keep the usage of that parameter under tight control.

I'm not quite sure what's happening there though....

The bridge method is casting the "Any" argument to call the right implementation.

[Josh Suereth]

My opinion on @uncheckedVariance is wholly different.  In other words:  @uncheckedVariance is to get around the situation where we return a *new instance* of something using T, which i safe, since we don't do ownership tracking.   @uncheckedVaraince on contains is exactly the sort of dangerous thing variance checking is supposed to warn you of here.

i.e:

def fakeMap(x: T => T@uncheckedVariance): Seq[T] = (this map x)(breakOut) // OK! we return a new instance.

When/why was the contains change made, or is this just a proposal?  I've been down for at least a week with travel.

- Josh

[Paul Phillips]

On Tue, Oct 9, 2012 at 11:13 AM, Jan Vanek <j3v...@gmail.com> wrote:

Looks like contract violation, the @unckeckedVariance needs to be required in the override, and probably even disallow concrete type (Int). But I'm not sure, it is very hard to think about half-solutions :-)

I'm pretty sure it's a necessary feature of annotations in general that they are not inherited.  My sense is that only finalizing contains will be sufficient.  And it would be sufficient, and I wouldn't have any objection to doing it since I want to finalize most things, but there's the usual bugbear of world-as-it-is.

Most plausible route I can think of is a newly named, final method.  I already tried to get clever with this once before, in NumericRange, with unsatisfying still-undealt-with results:

https://issues.scala-lang.org/browse/SI-4042

scala> 1L to 10L contains 3

res7: Boolean = false

scala> (1L to 10L).toList contains 3

res8: Boolean = true

Why would that be, you might ask? Here is why:

- Variance: Even though NumericRange is invariant, it inherits

contains from covariant Seq and thereby must suffer its signature.

Inability to abstract across variance strikes again.

- Since a NumericRange is implemented in terms of some unknown T, the only

ways to implement contains are to iterate over every element calling

== or to transform an "Any" into a T. Iteration will give the right answer:

scala> 1L to 10L exists (_ == 3)

res0: Boolean = true

but when one pictures doing this to see if 1L to Int.MaxValue.toLong

contains Int.MaxValue / 2, we appreciate the many orders of

magnitude speed reduction we potentially pay for correctness. Which

takes us to:

- Leaky primitive abstraction: casting a numeric primitive to another

numeric primitive always succeeds. Casting between boxed types will

always fail. Calling a method taking Any boxes the parameter. And

this is why we can't find 3 in a range containing 3L: the cast from

java.lang.Integer to java.lang.Long fails.

There are a number of possible ways out, none very appealing. My

plan right now is to type match the contains argument and widen to

Long or Double if it's a primitive, then call the (not yet existing)

fromLong or fromDouble method on Numeric which (will) have the

each-Numeric-specific knowledge of how to create a T.

One might be tempted to simply overload contains in NumericRange

with the primitives, which is easy and will mostly work – and then

still fail if the static type of the argument is Any. No point in

being sort of right. We have to deal with the Any argument so we

may as well go straight there.

[Paul Phillips]

On Tue, Oct 9, 2012 at 11:20 AM, Josh Suereth <joshua....@gmail.com> wrote:
>
> When/why was the contains change made, or is this just a proposal?

Nothing has been done, but it was probably pretty close given that
martin expressed agreement about the angle. Read the thread with
subject "decl/def-site variance".

[martin odersky]

On Tue, Oct 9, 2012 at 7:53 PM, Paul Phillips <pa...@improving.org> wrote:

We should know better than to question Our Lord Variance.

If I can make contains final I can mostly avoid it, and I can catch ClassCastException, but the first requires "deprecated non-final" and with the second you can't help but grit your teeth.

scala> class Bippy extends Seq[Int] { override def contains(x: Int) = false ; def iterator = Nil.iterator ; def apply(idx: Int) = ??? ; def length = 0 }

defined class Bippy

Ouch. Yes, that throws a spammer in the works. 

 - Martin

 

scala> var x: Seq[Any] = new Bippy

x: Seq[Any] = ()

scala> x contains "blue"

java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

at scala.runtime.BoxesRunTime.unboxToInt(Unknown Source)

at Bippy.contains(<console>:7)

at .<init>(<console>:10)

--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[Josh Suereth]

On Tue, Oct 9, 2012 at 2:22 PM, Paul Phillips <pa...@improving.org> wrote:

On Tue, Oct 9, 2012 at 11:13 AM, Jan Vanek <j3v...@gmail.com> wrote:

Looks like contract violation, the @unckeckedVariance needs to be required in the override, and probably even disallow concrete type (Int). But I'm not sure, it is very hard to think about half-solutions :-)

I'm pretty sure it's a necessary feature of annotations in general that they are not inherited.  My sense is that only finalizing contains will be sufficient.  And it would be sufficient, and I wouldn't have any objection to doing it since I want to finalize most things, but there's the usual bugbear of world-as-it-is.

Most plausible route I can think of is a newly named, final method.  I already tried to get clever with this once before, in NumericRange, with unsatisfying still-undealt-with results:

https://issues.scala-lang.org/browse/SI-4042

scala> 1L to 10L contains 3

res7: Boolean = false

scala> (1L to 10L).toList contains 3

res8: Boolean = true

Why would that be, you might ask? Here is why:

- Variance: Even though NumericRange is invariant, it inherits

contains from covariant Seq and thereby must suffer its signature.

Inability to abstract across variance strikes again.

I'd more place the blame on 3L == 3 as true.  I'm not sure I understand why 1L to 10L contains 3 = false, based on equality, 

it seems that the situation you describe above *is a bug*.  I.e. read the wording of contains, which is overloaded contains in Range:

true if this range has an element that is is equal (wrt ==) to elem, false otherwise.

While I agree that avoiding boxing is ideal, I don't think we should hold that example as an issue where variance is broken.   That's the standard hijinx that runtime class casting causes.

 

- Since a NumericRange is implemented in terms of some unknown T, the only

ways to implement contains are to iterate over every element calling

== or to transform an "Any" into a T. Iteration will give the right answer:

scala> 1L to 10L exists (_ == 3)

res0: Boolean = true

but when one pictures doing this to see if 1L to Int.MaxValue.toLong

contains Int.MaxValue / 2, we appreciate the many orders of

magnitude speed reduction we potentially pay for correctness. Which

takes us to:

Yeah, a less than ideal situation.

 

- Leaky primitive abstraction: casting a numeric primitive to another

numeric primitive always succeeds. Casting between boxed types will

always fail. Calling a method taking Any boxes the parameter. And

this is why we can't find 3 in a range containing 3L: the cast from

java.lang.Integer to java.lang.Long fails.

True, but look at the code:

  override def contains(x: Any): Boolean =

    try containsTyped(x.asInstanceOf[T])    // <--- right here, asking for fun.

    catch { case _: ClassCastException => false }

If we're really going to allow 1 == 1L, then here we'd have to use that Numeric[T] to adapt from our arbitrary Any into T, rather than casting.    Is this what you meant by "going directly after Any"?  Because, to implement the method correctly (according to the documentation), it seems that's what we have to do here.  I'd call the current behavior a bug.

 

There are a number of possible ways out, none very appealing. My

plan right now is to type match the contains argument and widen to

Long or Double if it's a primitive, then call the (not yet existing)

fromLong or fromDouble method on Numeric which (will) have the

each-Numeric-specific knowledge of how to create a T.

I think this is the right way to go for now, given the definition of the contains method.   If we limited it such that Seq[T] contains (y: U) is true iff typeOf[T] == typeOf[U], then that's a different story.

[Nils Kilden-Pedersen]

On Tue, Oct 9, 2012 at 1:14 PM, Paul Phillips <pa...@improving.org> wrote:

Well that's the thing, it doesn't take Any after I change it not to take Any

I don't see how you can both override and change a signature. It's gotta be either an override, which must match the signature being overridden, or an overload, which is what this looks like.

Is specialization at play here?

[Paul Phillips]

On Tue, Oct 9, 2012 at 12:37 PM, Josh Suereth <joshua....@gmail.com> wrote:
> I'd more place the blame on 3L == 3 as true. I'm not sure I understand why
> 1L to 10L contains 3 = false, based on equality,

Because it doesn't call == on individual elements, since it would mean
"1L to Long.MaxValue contains Long.MaxValue - 1" would take about the
lifetime of the universe. Given a range and an argument, whether the
argument is one of the elements of the range is a tiny calculation
comparing step/start/end to the value.

But if you don't know if the value is of the same type, then first you
have to figure out how to compare the value to start/end/step. And it
is an Any. You can try to cast it - and it will work if it is exactly
the same type - and it will fail in "1L to 10L contains 3", because
you cannot cast an Integer to a Long.

[Paul Phillips]

On Tue, Oct 9, 2012 at 12:37 PM, Josh Suereth <joshua....@gmail.com> wrote:

> then here we'd have to use that Numeric[T] to adapt from our arbitrary Any
> into T,

Yes, an Any => Option[T] method on Numeric would be a huge problem
solver, and is something I've implemented a couple times before I
threw up my hands because Numeric is really a mess.

[Josh Suereth]

Yeah, we're in agreement here.  However, this is "contains" not implementing what it says it implements, which is a bug.   I agree that implementing what it *wants* seems to be crazy, but the point is that I don't think variance is getting in our way.   It's the definition of "contains" as taking Any and using ==.   So, without special Numeric/Integral support, we're kinda hosed here.   It's not the variance, but the runtime difference between Class + Equality, and the fact that a little "asInstnaceOf" is destroying that.

You're taking an Any => Boolean and using a cast to make it fit into A => Boolean.   My argument is that a simple cast is the issue, not the variance.  The variance forced you to use the cast, informing you that it's a dangerous thing to do.   I'd be against @uncheckedVariance on contains for this very reason.   It's *not* safe to allow covariance with contains.   I don't see how the compiler can make it so.

In any case, I think we actually agree on solutions but disagree on first causes :)

[Paul Phillips]

On Tue, Oct 9, 2012 at 1:16 PM, Josh Suereth <joshua....@gmail.com> wrote:
> It's the definition of "contains" as taking Any and using ==

Would you write "contains" to take Any if you didn't have to due to
variance? I thought it was a foregone conclusion that people wouldn't,
but perhaps I misjudged.

[Josh Suereth]

The == is the one that bugs me.   But sure, contains would take A instead.   Maybe the mutable collections being invariant have something to tell Mr. Immutable Seq.

[Jan Vanek]

Hi Paul,

thanks for pointing the NumericRange, it is *really* interesting. I'll think about it, but well, unfortunately I'll have to go back to my work.

Marginally related:

    class X
    class CA[+T]
    class CB[T <: X] extends CA[T]
    val cb = new CB[X]
    val ca1: CA[X] = cb
    val ca2: CA[Any] = ca1 // can we make this fail, please

I don't want to convert to use-site variance camp.

Regards,
Jan

[Paul Phillips]

Looking at NumericRange with fresh eyes (remember this was years ago)
made me see what I can do there to get what I want, no casting, no
non-local changes. You can't overload with 'def contains(x: T)'
because it erases the same as contains(Any). But you can do this,
which I will pull-request shortly.

def contains(x: T)(implicit dummy: DummyImplicit): Boolean =
isWithinBoundaries(x) && (((x - start) % step) == zero)

Doing it this way, both "1L to 10L contains 3L" and even more nicely
"1L to 10L contains 3" are routed to the fast method. If the overload
logic decided this method is inapplicable, then it will call the
regular contains - which will still give the right answer, albeit
slowly.

This does not make contains say true for "1L to 10L contains
BigInt(1)". I don't think anything can do that short of always
iterating, and I'd far rather just delete it than do that. Why would
anyone want a "Range" class which has a membership test which is up to
6 orders of magnitude slower than necessary.

[Paul Phillips]

On Tue, Oct 9, 2012 at 1:44 PM, Paul Phillips <pa...@improving.org> wrote:
> This does not make contains say true for "1L to 10L contains
> BigInt(1)".

Wait, what am I saying, of course it does. The fast method is only
called with Ts. So it's always right, it's just slow if you mix
types.

[Rex Kerr]

On Tue, Oct 9, 2012 at 4:32 PM, Jan Vanek <j3v...@gmail.com> wrote:

Marginally related:

    class X
    class CA[+T]
    class CB[T <: X] extends CA[T]
    val cb = new CB[X]
    val ca1: CA[X] = cb
    val ca2: CA[Any] = ca1 // can we make this fail, please

I don't want to convert to use-site variance camp.

Why do you want that to fail?  It meets all the requirements.  If an instance of CB cannot handle its type parameter being widened beyond X when it is viewed as a CA, then it violates the Liskov Substitution Principle.  So allowing it looks perfectly okay to me.  (ca1 is the dangerous step anyway.)

  --Rex

[Jan Vanek]

On 09.10.2012 22:48, Rex Kerr wrote:

On Tue, Oct 9, 2012 at 4:32 PM, Jan Vanek <j3v...@gmail.com> wrote:

Marginally related:

    class X
    class CA[+T]
    class CB[T <: X] extends CA[T]
    val cb = new CB[X]
    val ca1: CA[X] = cb
    val ca2: CA[Any] = ca1 // can we make this fail, please

I don't want to convert to use-site variance camp.

Why do you want that to fail?  It meets all the requirements.  If an instance of CB cannot handle its type parameter being widened beyond X when it is viewed as a CA,

I know it does. I'd prefer if the CB could be viewed as CA only "within its bounds". The why? question is complicated. If we have Seq[+T], and List[+T] extends Seq[T], then I have no problem viewing List[Ford] as Seq[Car] (assuming Ford <: Car), because it is possible that List[Car] also can exist. But if we have List[T <: EuropaCar] extends Seq[T] then I don't like to see List[Skoda] as Seq[Car] because List[Car] cannot exist (the type itself doesn't exist, we can't even say it is not inhabited). Which means I can't ever see List[Skoda] as List[Car], why would I want to see it as Seq[Car]? ((Apart from that it makes couple of things in my variance-quest easier :- ))

then it violates the Liskov Substitution Principle.  So allowing it looks perfectly okay to me.  (ca1 is the dangerous step anyway.)

Absolutely. It seems it would have to be:
val ca1: (CA with T<:X)[X] = cb

  --Rex

I can't say I'm clear on this though.

Regards,
Jan

[Rex Kerr]

That doesn't help because CA with whatever is a subtype of CA.  Breaking LSP just leads to headaches.  If your relationships are not well-modeled with inheritance, don't use inheritance to implement them.  Use composition or context bounds or something.

  --Rex

[Jan Vanek]

Right, I take it back. Luckily, as Paul pointed, the (knowledge of) bounds can be recovered with genuineImplicit. Declaration-site variance rules.

 

  --Rex

Regards,

Jan

[Alec Zorab]

What am I missing? Surely if EuropaCar <: Car then List[T <: EuropaCar] can be viewed as a List[Car] and therefore as Seq[Car].

  trait Car

  trait EuropaCar extends Car

  trait Skoda extends EuropaCar

  val SList = List.empty[Skoda]

  val EList: List[EuropaCar] = SList

  val CList : List[Car] = EList //You're saying this doesn't exist?/Shouldn't work?

  

  val SSeq : Seq[Skoda] = SList

  val ESeq : Seq[EuropaCar] = SList

  val CSeq : Seq[Car] = SList

[Jan Vanek]

Hi Alec,

I wrote: "But if we have List[T <: EuropaCar] extends Seq[T] then".

  trait Seq[+T]

  trait List[+T <: EuropaCar] extends Seq[T]

  val EList: List[EuropaCar] = null

  val CList : List[Car] = EList // yes, it doesn't

I shouldn't have used List name, I should have used say ECList as name.

You can see it as diamond:

               Seq[Car]

            /                   \

Seq[Skoda]              ECList[Car] // this path is impossible

        \                         /

            ECList[Skoda]

Regards,

Jan