4

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()?).

  • What is the reason for this runtime exception; is it expected (mis-use of conformance to Stridable)?

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:

  • Is this a bug in the next() method of StrideToGenerator, or just an error that pops up due to a mis-use of String.CharacterView.Index conformance to Stridable?

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:

  • conforms to Comparable (and in so, Equatable),
  • contains implementations for advancedBy(_:) and distanceTo(_:).

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?

Improve this question
1

3 Answers 3

Reset to default
4

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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.

Improve this answer

6 Comments

@VatsalManot: I am not sure if I understand what you mean. You can define a extension String.CharacterView.Index : Strideable with a strideTo method. Perhaps I am overlooking something?
@MartinR: Yes, I believe you are. The runtime error cannot be avoided. stride(to:by:) is implemented in an extension, not declared in the protocol. So if working with a generic Strideable, the compiler will always choose the default implementation over the custom one.
@MartinR: The problem lies not in the strideTo function, but in stride(to:by), where next() called on an index with value endIndex - 1 triggers a runtime error. An unavoidable error, by design.
@MartinR: extension String.CharacterView.Index: Strideable {} with a custom stride(to:by:) implementation is not a correct solution, for the reasons I just pointed out. However, the stride(to:by:) on it's own will not cause any issues.
@VatsalManot: "... the compiler will always choose the default implementation over the custom one." – That is not correct. See "Providing Default Implementations" in the Swift book: "If a conforming type provides its own implementation of a required method or property, that implementation will be used instead of the one provided by the extension." – My example is not perfect, but it shows that it can be done.
|
0

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.

Improve this answer

1 Comment

Thanks! I realized the same upon reading my own question: the default implementation of the stride functions make use (via Stridable types += operator) of the non-bounds-checking advancedBy(_:), which in combination with the non-thorough bounds testing in StrideToIterator .next() will fail the crucial test you've performed above.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.