NumericRange is the poster child for feature intersection troubles

[scabug]

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.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4042?orig=1
Reporter: @paulp

[scabug]

@odersky said:
I think NumericRange is essentially an over-abstraction, not worth the troubles it causes. We should make sure things work for int and long ranges, by systematically overriding methods like contains, if necessary. If the rest can't be made to work it should be deprecated.

Note that for numeric primitive ranges the right test goes something like this (say for Long):

  def contains(elem: Any) = elem match {
    case n: Number => ... stuff with n.longValue ...
    case _ => false
  }

[scabug]

@paulp said:
Replying to [comment:2 odersky]:

I think NumericRange is essentially an over-abstraction, not worth the troubles it causes.

I see it differently, in two ways. First, that BigInt and BigDecimal/Double ranges are quite useful, and second that I view the trouble it has caused is providing a very useful early warning system regarding surprising/unfortunate feature interactions. There is no question we haven't yet found all the interesting consequences of recent changes like weak conformance, and NumericRange helps us find them faster.

I can (and want to) make the rest work. (I didn't open the ticket looking for anyone else to do it, but to document the issue and give people a chance to chime in.) In some sense the harder it is to make work the more worthwhile it is. It's not like this is a crazily esoteric abstraction, it's a successor function: given the existence of Numeric if we can't make it work there's something wrong. In fact the whole class is purely optimization, because

Iterate.iterate(start)(_ `plus` step) takeWhile (_ lt/gt/le/ge end)

is all you need, until you want to contains to finish in your lifetime.

Note that for numeric primitive ranges the right test goes something like this (say for Long):
{code}
def contains(elem: Any) = elem match {
case n: Number => ... stuff with n.longValue ...
case _ => false
}
}}

Actually in the course of addressing this and other bugs I noticed that this is insufficient, and here is one reason why:

scala> (Long.MinValue to Long.MinValue + 1)        
res5: scala.collection.immutable.NumericRange.Inclusive[Long] = NumericRange(-9223372036854775808, -9223372036854775807)

scala> BigInt(Long.MaxValue) + 1
res6: scala.math.BigInt = 9223372036854775808

scala> res5 contains res6
res7: Boolean = false

scala> res5 contains res6.longValue
res8: Boolean = true

I have found more long-standing Range bugs too. These classes are surprisingly subtle.

[scabug]

@paulp said (edited on Sep 10, 2013 11:27:30 PM UTC):
Since I see Rex that you assigned this to yourself, let me note for the record that the real bug has nothing to do with this class. In paulp-collections, NumericRange doesn't inherit contains, it defines it - and you can't call contains with anything but a "T". All the problems mentioned here go away.

Defining contains on a common covariant superclass to be inherited as Any => Boolean in all the invariant leaf classes was a huge mistake.

[scabug]

@Ichoran said:
I've assigned it to myself because I'm handling performance improvements to Range and possibly NumericRange and also possibly deprecating things for 2.11 that we don't want in 2.12, so it seems plausible that I'll tackle this issue. If I don't manage to, I'll just let it go back to Unassigned again. No promises!

This sort of thing is a difficult issue in general; extensibility of numbers is hard because numbers should be numbers, but they can be extended in different ways. In the absence of something that sensibly covers all the Reals (all uncountably many of them), it's pretty hard to provide full extensibility. (You can't even in principle compute most of the Reals, so it's really quite hopeless--what if I want to pick out some set of uncomputable Reals and then start asking about ranges between them?)

[scabug]

@paulp said:
I'm not sure I see how this class relates to the extensibility of numbers. I think the uses to which a class like this might be put are pretty apparent and don't involve picking sets of uncomputable reals.

That said, if I were to do it again I would most likely just wrap an integer basis, so that there is always an underlying range with well defined endpoints and integer step, e.g. 0.0 to 1.0 by 0.01 is represented by MappedRange(0 to 100 by 1, multiplier = 0.01) or whatever.

[scabug]

@Ichoran said:
There's another way out of this mess, which is not great for performance and is messy, but recovers most generality except for pairs of ill-behaved Integrals and/or those that cannot be embedded into any of the existing Integral types.

If you have a new method on Numeric:

  def comparator[U <: Numeric[U]](u: U): Option[(T, U) => Int]

and you have a new trait that is something like:

  trait EmbeddableNumber {
    def embed: Either[ Either[Long, Double], Either[BigInt, BigDecimal] ]
  }

from which any new numeric types should inherit, then if you define a comparator on all four types into which you might embed, you can do a binary search for contains on any numeric type that defines EmbeddableNumber. This gives non-ideal performance, of course, but it's O(log N) instead of O(N), and it works extremely generally.

(The key feature of embedding is that for your type T, T embeds into type U iff for all numeric types V, T==V iff U==V.)