Range<UInt64>.count can abort


(Jens Alfke) #1

I’m writing some code that deals with ranges of “sequence numbers”, which are consecutively-assigned positive 64-bit integers, thus Range<UInt64> in Swift. I’m having trouble handling half-open ranges with no maximum, which are very commonly used for representing all items created since a certain time.

The trouble is, if I represent these with Ranges whose endIndex is UInt64.max, those ranges tend to bomb:

let r: Range<UInt64> = 5..<UInt64.max
r.count // FATAL ERROR

The problem is that Range.count’s type is Element.Distance, and UInt64.Distance is a typealias of … Int. Huh? It’s pretty clear that the distance between two UInt64s can’t be represented by a signed Int64. Why isn’t Distance UInt64?

(I’m guessing it’s because Distance needs to be signed, to represent backwards distances? But that’s not needed for Ranges, of course.)

It’s sort of worrisome that Swift will let me create a valid Range value that nonetheless bombs when accessed!

—Jens


(Dmitri Gribenko) #2

Hi Jens,

The distance is signed so that we can represent negative distances.
r.distance(from:to:) should be able to measure distances backwards.

We are aware of this issue, but we don't know of a good solution.
We'd appreciate your suggestions.

Dmitri

···

On Fri, Apr 15, 2016 at 4:23 PM, Jens Alfke via swift-users <swift-users@swift.org> wrote:

I’m writing some code that deals with ranges of “sequence numbers”, which
are consecutively-assigned positive 64-bit integers, thus Range<UInt64> in
Swift. I’m having trouble handling half-open ranges with no maximum, which
are very commonly used for representing all items created since a certain
time.

The trouble is, if I represent these with Ranges whose endIndex is
UInt64.max, those ranges tend to bomb:

let r: Range<UInt64> = 5..<UInt64.max
r.count // FATAL ERROR

The problem is that Range.count’s type is Element.Distance, and
UInt64.Distance is a typealias of … Int. Huh? It’s pretty clear that the
distance between two UInt64s can’t be represented by a signed Int64. Why
isn’t Distance UInt64?

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Jens Alfke) #3

--Jens [via iPhone]

The distance is signed so that we can represent negative distances.
r.distance(from:to:) should be able to measure distances backwards.

Yeah, makes sense in general, just not for this particular case...

We are aware of this issue, but we don't know of a good solution.
We'd appreciate your suggestions.

Add Int128! :wink:

Ok, maybe that just pushes the problem further down the road. How about making Distance be Double? :wink:

--Jens

···

On Apr 15, 2016, at 4:26 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:


(David Sweeris) #4

Is there any reason that Distance has to be a simple Int? Since it’s defined per-type, UInt64 could use a custom struct without impacting the performance of other types:
struct UInt64Distance : Comparable { //I'm not sure what else it needs to conform to
    var distance: UInt64
    var isPositive: Bool
}
func == (lhs: UInt64Distance, rhs: UInt64Distance) -> Bool {
    return lhs.distance == rhs.distance && lhs.isPositive == rhs.isPositive
}
func < (lhs: UInt64Distance, rhs: UInt64Distance) -> Bool {
    switch (lhs.isPositive, rhs.isPositive) {
    case (false, false): return lhs.distance > rhs.distance
    case (false, true ): return true
    case (true, false): return false
    case (true, true ): return lhs.distance < rhs.distance
    }
}
... //The rest of `Comparable`

(I’m assuming it’d need `Comparable`, but a quick glance around with cmd-click in Xcode didn’t tell me what, if any, protocols `Distance` needs to conform to.)

- Dave Sweeris

···

On Apr 15, 2016, at 6:26 PM, Dmitri Gribenko via swift-users <swift-users@swift.org> wrote:

On Fri, Apr 15, 2016 at 4:23 PM, Jens Alfke via swift-users > <swift-users@swift.org> wrote:

I’m writing some code that deals with ranges of “sequence numbers”, which
are consecutively-assigned positive 64-bit integers, thus Range<UInt64> in
Swift. I’m having trouble handling half-open ranges with no maximum, which
are very commonly used for representing all items created since a certain
time.

The trouble is, if I represent these with Ranges whose endIndex is
UInt64.max, those ranges tend to bomb:

let r: Range<UInt64> = 5..<UInt64.max
r.count // FATAL ERROR

The problem is that Range.count’s type is Element.Distance, and
UInt64.Distance is a typealias of … Int. Huh? It’s pretty clear that the
distance between two UInt64s can’t be represented by a signed Int64. Why
isn’t Distance UInt64?

Hi Jens,

The distance is signed so that we can represent negative distances.
r.distance(from:to:) should be able to measure distances backwards.

We are aware of this issue, but we don't know of a good solution.
We'd appreciate your suggestions.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Dmitri Gribenko) #5

--Jens [via iPhone]

The distance is signed so that we can represent negative distances.
r.distance(from:to:) should be able to measure distances backwards.

Yeah, makes sense in general, just not for this particular case...

We are aware of this issue, but we don't know of a good solution.
We'd appreciate your suggestions.

Add Int128! :wink:

Ok, maybe that just pushes the problem further down the road.

Indeed.

How about making Distance be Double? :wink:

Double only has 53 bits of precision.

Dmitri

···

On Fri, Apr 15, 2016 at 4:41 PM, Jens Alfke <jens@mooseyard.com> wrote:

On Apr 15, 2016, at 4:26 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Dmitri Gribenko) #6

It needs to be a signed integer. And a signed integer needs a
distance type itself.

Dmitri

···

On Sat, Apr 16, 2016 at 8:29 AM, <davesweeris@mac.com> wrote:

Is there any reason that Distance has to be a simple Int? Since it’s defined
per-type, UInt64 could use a custom struct without impacting the performance
of other types:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Jens Alfke) #7

Yeah, there’s an infinite regress implied there, since a distance type has to be one bit larger than its source type.

The only plausible solution is bignums. Any talk of adding those to Swift?

—Jens

···

On Apr 16, 2016, at 12:53 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

It needs to be a signed integer. And a signed integer needs a distance type itself.