on Tue Apr 12 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:
> Yes, I totally agree that `Collection.subscript(_: Index)` should not > be Optional. > > But I think that index-manipulation methods like `successor(of:)` are > a different story. It is normal and expected that, when you alter an > index, you will occasionally hit the boundaries of the > collection. There certainly are cases where you know a particular > index manipulation is safe, but most index manipulations need to be > guarded by something like: > > while index < collection.endIndex { > let nextIndex = collection.successor(of: index) > … > index = nextIndex > } I disagree that this should be considered a “guard.” You are testing against another index—a basic feature of what makes something an index. It's probably a bit more likely that this other index is at the end of the collection, but it might not be. For example, look at the algorithm for reversing a collection in place: extension BidirectionalCollection where Self : MutableCollection { mutating func reverse() { if isEmpty { return } // early exit eliminates a branch in the loop var i = startIndex var j = predecessor(of: endIndex) while i < j { swap(&self[i], &self[j]) formSuccessor(&i) formPredecessor(&j) } } } [Why isn't this in the stdlib?! Someone file a bug and write a proposal, quick!] > In these cases, it would be better if the `successor(of:)` method was > designed in a way that acknowledged and encapsulated the bounds check > that is usually required when it is used: > > while let nextIndex = collection.successor(of: index) { > … > index = nextIndex > } I disagree; it doesn't make sense that I should have to check for nil when I'm not really interested in the end of the collection as in my example above. Many other nontrivial algorithms will have the same characteristic. If all you need is to loop through indices to the end, there are lots of ways to do it. Looking closer, what you've got here is actually a *highly* unusual case, where you want a pair of indices that you want to always point to successive elements. I do not know of any algorithm that would use this except maybe bubblesort, and frankly I cannot see any reason to change the standard library to support it. Am I missing something? > Given the difficulties of statically detecting index invalidation, I > totally agree that (as you discussed in a section I've snipped) we > can't statically prove indexes are safe. But we can, at the point > where we generate an index, easily check if that index is *currently* > valid. And it's something that most callers will have to do anyway if > we don't do it ourselves. I really disagree with the assertion that most callers will need to do this. It certainly isn't a normal thing to do in any algorithm I know of. If you think I'm wrong (not unheard of!), I suggest you code up the method you've requested and try to apply it in actual code that manipulates indices, and show us how it improved the code. >> We will change the index(_:stepsFrom:limitedBy:) overload to return >> an optional, and we will see what other implications it has, and how >> it fits into the rest of the system. > > I'm glad to hear you'll evaluate this option, and I think it can give > us both what we want from this API. > > I think having the most high-level operations incorporate bounds > checks, while the lower-level ones don't, is a good compromise. That may be the pattern you discern in Swift's bounds checks, but I just want to be very clear that it's not a criterion we use to make the determination. I would love it if we had a more systematic way to make the choice to insert bounds checks or not, but for now it remains something of an art, trying to balance usability and performance concerns. > If we encourage people to use `index(_:stepsFrom:limitedBy:)` unless > they know what they're doing, naïve clients will get an implicit > bounds check, while sophisticated, speed-sensitive clients can use > methods like `successor(of:)` which require them to check bounds > manually. It's not a bounds check. There are lots of ways to pass a limit that's outside the bounds of the collection, and you can pass a limit that's in the opposite direction from the offset. If they happen to pass the collection's endIndex and a positive offset, it degenerates to a bounds check, but that's not what this method is for. I will encourage people to use high-level algorithms where possible, so they're not doing index manipulations directly. Anyone doing low-level index manipulations is probably implementing an algorithm, and I'll encourage them to do whatever will be most efficient, and then test the algorithm on some very strict models of Collection, that check everything. You can find some of these in the StdlibUnittest library in the swift source tree. > (There might even be a case for offering bounds-checked > `successor(of:limitedBy:)` and `predecessor(of:limitedBy:)` methods to > give people bounds-checked alternatives to all three.) > >> Thanks again, Brent. > > Thank you! -- Dave _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution