Iterating a range of integers

Evolution Discussion
1

Range conforms to Sequence under the condition Bound: Strideable, Bound.Stride: SignedInteger.

However, BinaryInteger does not currently provide SignedInteger conformance for its Stride.

This causes problems in generic code. Specifically, when looping over a generic integer type, we cannot use a for loop:

func foo<T: BinaryInteger>(_ a: T, _ b: T) {
  for i in a ..< b {    // error: Operator function '..<' requires that 'T.Stride' conform to 'SignedInteger'
    print(i)
  }
}

Note that we can form the range itself: let range = a ..< b. We just can’t iterate over it or perform other sequence / collection operations like shuffled(), first(where:), and randomElement().

Furthermore, even changing the generic constraint from T: BinaryInteger to T: SignedInteger does not fix the problem. It is still the same error for signed integers.

Of course a while loop works fine even with BinaryInteger, which highlights that logically there is no reason to prohibit iteration here:

func foo<T: BinaryInteger>(_ a: T, _ b: T) {
  precondition(a <= b)
  var i = a
  while i < b {
    print(i)
    i += 1
  }
}

• • •

Personally, I just encountered this issue while writing some generic floating-point code where I needed to iterate through a range of exponents.

Having to write a while loop rather than a for loop is not a major showstopper, just a minor annoyance. But it is still an annoyance, and in a language like Swift that takes pride in its clarity, a for loop over a range is much more clear to readers than a while loop with manual increments.

In another situation, instead of a simple loop, one might want to call a generic algorithm on the range such as sorted(by:). And that being disallowed is a much larger annoyance.

• • •

I know this has been mentioned on the forums before, such as in the thread, Why does a for loop range need a signed integer?, but I don’t recall any discussion about actually rectifying the situation.

Currently:

• BinaryInteger is declared as being Strideable.

• Strideable.Stride is declared as being SignedNumeric.

So it follows that BinaryInteger.Stride is always SignedNumeric.

But today there is no constraint that BinaryInteger.Stride must be an integer.

• • •

I think it is completely reasonable to require that the stride of an integer should itself be an integer. And, since strides are always signed, it follows that the stride of an integer should really be a signed integer.

Thus, the missing piece is that BinaryInteger.Stride needs to conform to SignedInteger.

Specifically, the BinaryInteger protocol should be declared with a constraint where Stride: SignedInteger.

Note that FixedWidthInteger already has that constraint. Adding it to BinaryInteger would allow ranges of any generic integer type to be used as collections, including for loops and calling generic algorithms.

• • •

Conceptually for users this change is trivial: every integer type should already have integer strides, and strides are always signed.

What would an integer type with non-integer strides even mean? It doesn’t make sense as a concept.

The only place this would break source-compatibility is on the declaration of an integer type with non-integer strides, which should not exist in the first place.

• • •

However, I suspect there might be binary compatibility concerns with adding a constraint to a standard-library protocol. I don’t know enough about the ABI to say for sure, but it seems like the sort of thing that might cause issues.

So I wanted to gauge whether this (adding where Stride: SignedInteger to the declaration of BinaryInteger) is something that could be done in a normal release, almost like a bug-fix, or if it would need to wait for a full version change like Swift 6.

8 Likes
2

@Slava_Pestov can confirm, but yeah, I don't think that there's any way to make this change in the language at present without breaking ABI.

Note that this isn't a one-off; there's a whole bunch of "small" missing conformances like this scattered throughout the stdlib. We'll need to figure out something to do about them eventually, but it hasn't become a major problem yet.

8 Likes
3

@scanon, do you know if there are any plans/process to make an ABI-breaking release once there is critical mass of things that need to be fixed?

1 Like
4

I don't speak for the core team, but I don't think we'd break ABI to fix this sort of issue. I think it's more likely that we would make language changes that allowed us to resolve them without breaking ABI, whether that's new forms of availability checking or versioning the stdlib or something else.

2 Likes
5

And it’s not the API break that’s most critical here; it’s the ABI. Every function defined as Number: BinaryInteger where Number.Stride: SignedInteger will now have a different calling convention, because that second constraint is redundant. That’s the sort of thing we have to worry about here; we can bludgeon -swift-version into whatever rules we want with enough code and special cases, but we can’t change old versions of the stdlib that are already in macOS and iOS—or worse yet, other libraries in the OSs that merely use the stdlib protocol.

3 Likes
6

How about get around this shortcoming by defining ForEach and Range.forEach over BinaryInteger?

func ForEach<T: BinaryInteger>(_ range: Range<T>, _ body: (T) -> ()) {
    var i = range.lowerBound
    while i < range.upperBound {
        body(i)
        i += 1
    }
}

extension Range where Bound: BinaryInteger {
    func forEach(_ body: (Bound) -> ()) {
        var i = lowerBound
        while i < upperBound {
            body(i)
            i += 1
        }
    }
}

func foo<T: BinaryInteger>(_ a: T, _ b: T) {
    precondition(a <= b, "Precondition a <= b fail, a = \(a), b = \(b)")
    ForEach(a..<b) { i in
        print(i)
    }
}

func foofoo<T: BinaryInteger>(_ a: T, _ b: T) {
    precondition(a <= b, "Precondition a <= b fail, a = \(a), b = \(b)")
    (a..<b).forEach { i in
        print(i)
    }
}

foo(0, 10)
foofoo(0, 10)

// ok, simply use `stride()` okay, too
func foofoofoo<T: BinaryInteger>(_ a: T, _ b: T) {
    precondition(a <= b, "Precondition a <= b fail, a = \(a), b = \(b)")
    for i in stride(from: a, to: b, by: 1) {
        print(i)
    }
}