CODEWITHSUNDEEP
swift
dfrib
dfrib

Reputation: 73196

Conforming String.CharacterView.Index to Strideable: fatal error when using stride(to:by:): "cannot increment endIndex "

Question:

When attempting to stride over String.CharacterView.Index indices by e.g. a stride of 2 

extension String.CharacterView.Index : Strideable { }

let str = "01234"
for _ in str.startIndex.stride(to: str.endIndex, by: 2) { } // fatal error

I get the following runtime exception

fatal error: cannot increment endIndex

Just creating the StrideTo<String.CharacterView.Index> above, however, (let foo = str.startIndex.stride(to: str.endIndex, by: 2)) does not yield an error, only when attempting to stride/iterate over or operate on it (.next()?).

I'm using Swift 2.2 and Xcode 7.3. Details follow below.

Edit addition: error source located

Upon reading my question carefully, it would seem as if the error really does occur in the next() method of StrideToGenerator (see bottom of this post), specifically at the following marked line

let ret = current
current += stride  // <-- here
return ret

Even if the last update of current will never be returned (in next call to next()), the final advance of current index to a value larger or equal to that of _end yields the specific runtime error above (for Index type String.CharacterView.Index).

(0..<4).startIndex.advancedBy(4) // OK, -> 4
"foo".startIndex.advancedBy(4)   // fatal error: cannot increment endIndex

However, one question still remains:

Related

The following Q&A is related to the subject of a iterating over characters in steps other than +1, and worth including in this question even if the two questions differ.

Especially note @Sulthan:s neat solution in the thread above.

Details

(Apologies for hefty details/investigations of my own, just skip these sections if you can answer my question without the details herein)

The String.CharacterView.Index type describes a character position, and:

Hence, it can directly be made to conform to the protocol Strideable, making use of Stridable:s default implementations of methods stride(through:by:) and stride(to:by:). The examples below will focus on the latter (analogous problems with the former):

...

func stride(to end: Self, by stride: Self.Stride) -> StrideTo<Self>

Returns the sequence of values (self, self + stride, self + stride + stride, ... last) where last is the last value in the progression that is less than end.

Conforming to Stridable and striding by 1: all good

Extending String.CharacterView.Index to Stridable and striding by 1 works fine:

extension String.CharacterView.Index : Strideable { }

var str = "0123"

// stride by 1: all good
str.startIndex.stride(to: str.endIndex, by: 1).forEach {
    print($0,str.characters[$0])
} /* 0 0 
     1 1 
     2 2
     3 3 */

For an even number of indices in str above (indices 0..<4), this also works for a stride of 2:

// stride by 2: OK for even number of characters in str.
str.startIndex.stride(to: str.endIndex, by: 2).forEach {
    print($0,str.characters[$0])
} /* 0 0
     2 2 */

However, for some cases of striding by >1: runtime exception

For an odd number of indices and a stride of 2, however, the stride over the character views indices yield a runtime error

// stride by 2: fatal error for odd number of characters in str.
str = "01234"
str.startIndex.stride(to: str.endIndex, by: 2).forEach {
    print($0,str.characters[$0])
} /* 0 0
     2 2
     fatal error: cannot increment endIndex */

Investigations of my own

My own investigations into this made me suspect the error comes from the next() method of the StrideToGenerator structure, possibly when this method calls += on the stridable element

public func += <T : Strideable>(inout lhs: T, rhs: T.Stride) {
  lhs = lhs.advancedBy(rhs)
}

(from a version of the Swift source for swift/stdlib/public/core/Stride.swift that somewhat corresponds to Swift 2.2). Given the following Q&A:s

we could suspect that we would possibly need to use String.CharacterView.Index.advancedBy(_:limit:) rather than ...advancedBy(_:) above. However from what I can see, the next() method in StrideToGenerator guards against advancing the index past the limit.

Edit addition: the source of the error seems to indeed be located in the next() method in StrideToGenerator:

// ... in StrideToGenerator
public mutating func next() -> Element? {
    if stride > 0 ? current >= end : current <= end {
        return nil
    }
    let ret = current
    current += stride /* <-- will increase current to larger or equal to end 
                               if stride is large enough (even if this last current
                               will never be returned in next call to next()) */
    return ret
}

Even if the last update of current will never be returned (in next call to next()), the final advance of current index to a value larger or equal to that of end yields the specific runtime error above, for Index type String.CharacterView.Index. 

(0..<4).startIndex.advancedBy(4) // OK, -> 4
"foo".startIndex.advancedBy(4)   // fatal error: cannot increment endIndex

Is this to be considered a bug, or is String.CharacterView.Index simply not intended to be (directly) conformed to Stridable?

Upvotes: 4

Views: 3489

Answers (3)

Vatsal
Vatsal

Reputation: 18181

To simply answer your ending question: this is not a bug. This is normal behavior.

String.CharacterView.Index can never exceed the endIndex of the parent construct (i.e. the character view), and thus triggers a runtime error when forced to (as correctly noted in the latter part of your answer). This is by design.

The only solution is to write your own alternative to the stride(to:by:), one that avoids equalling or exceeding the endIndex in any way.

As you know already, you can technically implement Strideable, but you cannot prevent that error. And since stride(to:by:) is not blueprinted within the protocol itself but introduced in an extension, there is no way you can use a "custom" stride(to:by:) in a generic scope (i.e. <T: Strideable> etc.). Which means you should probably not try and implement it unless you are absolutely sure that there is no way that error can occur; something which seems impossible.

Solution: There isn't one, currently. However, if you feel that this is an issue, I encourage you to start a thread in the swift-evolution mailing list, where this topic would be best received.

Upvotes: 2

Martin R
Martin R

Reputation: 539965

Simply declaring the protocol conformance 

extension String.CharacterView.Index : Strideable { }

compiles because String.CharacterView.Index conforms to BidirectionalIndexType , and ForwardIndexType/BidirectionalIndexType have default method implementations for advancedBy() and distanceTo() as required by Strideable.

Strideable has the default protocol method implementation for stride():

extension Strideable {
    // ...
    public func stride(to end: Self, by stride: Self.Stride) -> StrideTo<Self>
}

So the only methods which are "directly" implemented for String.CharacterView.Index are – as far as I can see - the successor() and predecessor() methods from BidirectionalIndexType.

As you already figured out, the default method implementation of stride() does not work well with String.CharacterView.Index.

But is is always possible to define dedicated methods for a concrete type. For the problems of making String.CharacterView.Index conform to Strideable see Vatsal Manot's answer below and the discussion in the comments – it took me a while to get what he meant :)

Here is a possible implementation of a stride(to:by:) method for String.CharacterView.Index:

extension String.CharacterView.Index {
    typealias Index = String.CharacterView.Index

    func stride(to end: Index, by stride: Int) -> AnySequence<Index> {

        precondition(stride != 0, "stride size must not be zero")

        return AnySequence { () -> AnyGenerator<Index> in
            var current = self
            return AnyGenerator {
                if stride > 0 ? current >= end : current <= end {
                    return nil
                }
                defer {
                    current = current.advancedBy(stride, limit: end)
                }
                return current
            }
        }
    }
}

This seems to work as expected:

let str = "01234"
str.startIndex.stride(to: str.endIndex, by: 2).forEach {
    print($0,str.characters[$0])
}

Output

0 0
2 2
4 4

Upvotes: 4

matt
matt

Reputation: 535606

This isn't really an answer; it's just that your question got me playing around. Let's ignore Stridable and just try striding through a character view:

    let str = "01234"
    var i = str.startIndex
    // i = i.advancedBy(1)
    let inc = 2
    while true {
        print(str.characters[i])
        if i.distanceTo(str.endIndex) > inc {
            i = i.advancedBy(inc)
        } else {
            break
        }
    }

As you can see, it is crucial to test with distanceTo before we call advancedBy. Otherwise, we risk attempting to advance right through the end index and we'll get the "fatal error: can not increment endIndex" bomb.

So my thought is that something like this must be necessary in order to make the indices of a character view stridable.

Upvotes: 0

Related Questions