Pitch: Offsetting Indices and Relative Ranges
Hello everyone, I’m back with yet another attempt at deriving indices, ranges, and slices through offsets.
This pitch introduces the type RelativeRange
, which is capable of representing a range whose bounds are relative to a normal range’s bounds by applying an offset. Applying offsets to indices and using relative ranges brings ease of use improvements to all Collections and is a convenient tools for reducing bugs in Int
-indexed Collections. It also makes types like String more approachable in casual contexts, such as for programming puzzles and learning.
Changes in revision 2: Collapses all the relative range types into RelativeRange
, internalizes the backing enum of RelativeBound
, and minor clarifications.
Approach
Bounds, (e.g. indices) can have offsets applied to them, creating RelativeBound
s which can be used for range formation and slicing. We introduce infix ++
and --
to create these, and either side may be omitted to imply startIndex
and endIndex
, just like the existing range operators.
RelativeRange
and corresponding partial variants are introduced, all of which conform to RangeExpression
so they can be used in all the normal places, such as slicing and replaceSubrange
.
let str = "abcdefghijklmnopqrstuvwxyz"
let idx = str.firstIndex { $0 == "n" }!
print(str[--4]) // w
print(str[idx++1]) // o
print(str[idx--2...idx++3]) // lmnopq
Other suggestions for operators are certainly welcome. I accepted ++
and --
after seeing @dabrahams mentioning them here. At first glance, they seemed a little odd (old C++ baggage), but I quickly adjusted and grew to like them. The pair of operators imply advancing forwards and backwards by the value on the right-hand-side.
Example Uses
Reduce Bugs for Int Indices
When a RandomAccessCollection
’s index type happens to be Int
, it’s a common mistake to assume that such indices start from zero.
For an example from this forum post, the fact that an Int
range’s indices are the very Int
s themselves means they don’t start at zero. Using relative offsets addresses this:
let r = 3..<10
print((absolute: r[5...], relative: r[++5...]))
// (absolute: Range(5..<10), relative: Range(8..<10))
This can be tricky in generic code. Tests written with e.g. Array
will pass, until some future caller supplies a slice type. Most slices share indices with the outer collection and thus do not start at 0. This illustrates the difference:
func getFifth<C: RandomAccessCollection>(
_ c: C
) -> (absolute: C.Element, relative: C.Element) where C.Index == Int {
return (c[5], c[++5])
}
let array = [0, 1,2,3,4,5,6,7,8,9]
print(getFifth(array)) // (absolute: 5, relative: 5)
print(getFifth(array[2...])) // (absolute: 5, relative: 7)
During code review, the generic signature and constraint on C.Index
might trigger more careful inspection that might catch the bug. But, this is a big foot-gun for Collections that are their own slice type, such as Data
. For Data
, there’s nothing in the type system that hints it might not start at zero. A library may just happen to work for multiple releases until one day a client passes in a Data
that happened to be sliced. This illustrates the difference:
func getFifth(_ data: Data) -> (absolute: UInt8, relative: UInt8) {
return (data[5], data[++5])
}
var data = Data([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
print(getFifth(data)) // (absolute: 5, relative: 5)
data = data.dropFirst()
print(getFifth(data)) // (absolute: 5, relative: 6)
Expressive Relative Indexing
For an example from a simplification of this forum post, we can conveniently apply a relative offset to an index we derived from another API:
func splitAndTruncate<T: BinaryFloatingPoint>(
_ value: T, precision: Int = 3
) -> (whole: Substring, fraction: Substring) {
let str = String(describing: value)
guard let dotIdx = str.firstIndex(of: ".") else { return (str[...], "") }
let fracIdx = dotIdx++1
return (str[..<dotIdx], str[fracIdx..<fracIdx++precision])
}
print(splitAndTruncate(1.0)) // (whole: "1", fraction: "0")
print(splitAndTruncate(1.25)) // (whole: "1", fraction: "25")
print(splitAndTruncate(1.1000000000000001)) // (whole: "1", fraction: "1")
print(splitAndTruncate(1.3333333)) // (whole: "1", fraction: "333")
print(splitAndTruncate(200)) // (whole: "200", fraction: "0")
An operation such as fracIdx++precision
has runtime complexity of O(precision)
.
Relative indexing is also useful for fixed-width textual formats. A very simple example from Advent of Code 2018 Day 7:
func parseRequirement(
_ str: Substring
) -> (predecessor: Unicode.Scalar, successor: Unicode.Scalar) {
return (str.unicodeScalars[++5], str.unicodeScalars[++36])
}
"""
Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.
""".split(separator: "\n").forEach { print(parseRequirement($0)) }
// (predecessor: "C", successor: "A")
// (predecessor: "C", successor: "F")
// (predecessor: "A", successor: "B")
// (predecessor: "A", successor: "D")
// (predecessor: "B", successor: "E")
// (predecessor: "D", successor: "E")
// (predecessor: "F", successor: "E")
These being available on all Collections means that all of String’s views, such as the UnicodeScalarView
and UTF8View
, benefit as well. These views give more technical precision, which is useful for processing textual formats that are not defined over grapheme clusters.
The below is a visual demonstration of all the nifty new additions:
let str = "abcdefghijklmnopqrstuvwxyz"
let idx = str.firstIndex { $0 == "n" }!
// -- single element subscript --
print(str[--14]) // m
print(str[idx--100]) // a
print(str[idx++1]) // o
print(str[(idx++1)--10]) // e
// -- relative range --
print(str[++1 ..< --2]) // bcdefghijklmnopqrstuvwx
print(str[idx--2 ..< --2]) // lmnopqrstuvwx
print(str[idx ..< --2]) // nopqrstuvwx
print(str[idx--2..<idx]) // lm
print(str[idx--2..<idx++3]) // lmnop
print(str[--4 ..< --2]) // wx
// -- relative range through --
print(str[idx--2 ... --2]) // lmnopqrstuvwxy
print(str[idx ... --2]) // nopqrstuvwxy
print(str[idx--2...idx]) // lmn
print(str[idx--2...idx++3]) // lmnopq
print(str[--4 ... --2]) // wxy
// -- partial relative range up to --
print(str[..<idx++2]) // abcdefghijklmno
print(str[..<idx--2]) // abcdefghijk
print(str[..<(++20)]) // abcdefghijklmnopqrst
print(str[..<(--20)]) // abcdef
// -- partial relative range through --
print(str[...idx++2]) // abcdefghijklmnop
print(str[...idx--2]) // abcdefghijkl
print(str[...(++20)]) // abcdefghijklmnopqrstu
print(str[...(--20)]) // abcdefg
// -- partial relative range from --
print(str[idx++2...]) // pqrstuvwxyz
print(str[idx--2...]) // lmnopqrstuvwxyz
print(str[++20...]) // uvwxyz
print(str[--20...]) // ghijklmnopqrstuvwxyz
Detailed Design
This introduces RelativeBound
, which is capable of representing a bound (e.g. index) with some offset applied to it. The bound itself may be omitted, in which case it is a pure offset from either the start of end.
public struct RelativeBound<Bound: Comparable> {
// implementation is internal enum of the form:
// case from(Bound, offset: Int)
// case fromStart(offset: Int)
// case fromEnd(offset: Int)
}
Negative offsets, or positive fromEnd
offsets, are only valid on BidirectionalCollection, following the same rules as index(_:offsetBy:)
.
This also adds relative (partial) range structs corresponding to existing (partial) ranges. They conform to RangeExpression
so they can be used in slicing, replaceSubrange
, removeSubrange
, etc. Conforming to RangeExpression means that they supply a partial-order (for containment) and can produce a Range<Index>
when given a Collection
. These new structs are necessary due to ABI-stability, since we cannot change the existing ranges nor RangeExpression
.
public struct RelativeRange<Bound: Comparable>: RangeExpression {
public func relative<C: Collection>(
to col: C
) -> Range<Bound> where C.Index == Bound
public func contains(_ element: Bound) -> Bool
}
public struct RelativeClosedRange<Bound: Comparable>: RangeExpression {
public func relative<C: Collection>(
to col: C
) -> Range<Bound> where C.Index == Bound
public func contains(_ element: Bound) -> Bool
}
public struct RelativePartialRangeUpTo<Bound: Comparable>: RangeExpression {
public func relative<C: Collection>(
to col: C
) -> Range<Bound> where C.Index == Bound
public func contains(_ element: Bound) -> Bool
}
public struct RelativePartialRangeThrough<Bound: Comparable>: RangeExpression {
public func relative<C: Collection>(
to col: C
) -> Range<Bound> where C.Index == Bound
public func contains(_ element: Bound) -> Bool
}
public struct RelativePartialRangeFrom<Bound: Comparable>: RangeExpression {
public func relative<C: Collection>(
to col: C
) -> Range<Bound> where C.Index == Bound
public func contains(_ element: Bound) -> Bool
}
The partial order is derived by considering the relative ranges as having a “hole” in the middle, similarly to how partial ranges have holes at the beginning or end. Order is derived by first comparing the bounds, followed by offsets, accounting for the implicit start and end bound:
internal static func < (lhs: RelativeBound, rhs: RelativeBound) -> Bool {
switch (lhs, rhs) {
case (.from(let lhsBound, let lhsOffset),
.from(let rhsBound, let rhsOffset)):
if lhsBound == rhsBound { return lhsOffset < rhsOffset }
return lhsBound < rhsBound
case (.from(_, _), .fromStart(_)): return false
case (.from(_, _), .fromEnd(_)): return true
case (.fromStart(_), .from(_, _)): return true
case (.fromStart(let lhs), .fromStart(let rhs)): return lhs < rhs
case (.fromStart(_), .fromEnd(_)): return true
case (.fromEnd(_), .from(_, _)): return false
case (.fromEnd(_), .fromStart(_)): return true
case (.fromEnd(let lhs), .fromEnd(let rhs)): return lhs > rhs
}
}
RelativeBound
does not conform to Comparable
, which would make them candidates for the type checker to consider as bounds for the existing range structs. Such range structs would be rejected anyways when used due to the same-type constraint between Bound
and Index
.
What a relative range really represents is determined when applied to a collection. These ranges don’t supply additional conditional conformances, such as Range
’s random access conformance if Bound
is Strideable
, as these are ephemeral structures meant to soon be applied, producing a regular Range
. Unlike Range
, these are not likely to be heavily used as currency types.
We provide infix ++
and --
, which may have the left hand side side omitted to imply an implicit start/end index. We do this through more overloads of prefix and postfix ++
, --
, and disambiguating overloads over PartialRangeFrom
:
precedencegroup RelativeOffsetPrecedence {
higherThan: RangeFormationPrecedence
}
infix operator ++ : RelativeOffsetPrecedence
infix operator -- : RelativeOffsetPrecedence
extension Int {
public static prefix func ++<Bound: Comparable>(
rhs: Int
) -> RelativeBound<Bound>
public static prefix func --<Bound: Comparable>(
rhs: Int
) -> RelativeBound<Bound>
}
extension Comparable {
public static func ++(
lhs: Self, rhs: Int
) -> RelativeBound<Self>
public static func --(
lhs: Self, rhs: Int
) -> RelativeBound<Self>
}
extension RelativeBound {
public static func ++(
lhs: RelativeBound, rhs: Int
) -> RelativeBound {
return lhs.addingOffset(rhs)
}
public static func --(
lhs: RelativeBound, rhs: Int
) -> RelativeBound {
return lhs.addingOffset(-rhs)
}
}
// ... and some more convenience overloads
We provide overloads for the range operators:
extension RelativeBound {
public static func ..< (
lhs: RelativeBound<Bound>, rhs: RelativeBound<Bound>
) -> RelativeRange<Bound>
public static func ..< (
lhs: Bound, rhs: RelativeBound<Bound>
) -> RelativeRange<Bound>
public static func ..< (
lhs: RelativeBound<Bound>, rhs: Bound
) -> RelativeRange<Bound>
public static func ... (
lhs: RelativeBound<Bound>, rhs: RelativeBound<Bound>
) -> RelativeClosedRange<Bound>
public static func ... (
lhs: Bound, rhs: RelativeBound<Bound>
) -> RelativeClosedRange<Bound>
public static func ... (
lhs: RelativeBound<Bound>, rhs: Bound
) -> RelativeClosedRange<Bound>
public static prefix func ..< (
maximum: RelativeBound<Bound>
) -> PartialRelativeRangeUpTo<Bound>
public static prefix func ... (
maximum: RelativeBound<Bound>
) -> PartialRelativeRangeThrough<Bound>
public static postfix func ... (
maximum: RelativeBound<Bound>
) -> PartialRelativeRangeFrom<Bound>
}
Try it Out
Copy-paste this gist into your code, and you can try it today! It has examples at the bottom. No need to download/install toolchains.
The implementation is here.
Acknowledgements
Many people have contributed to this design space in the prior threads. Huge thanks to @Letan’s original thread and proposals which spawned a ton of great feedback and explored so much of the design space. My earlier thread acknowledges the insights of @Letan, @dabrahams, @QuinceyMorris, @xwu, @Karl, @nnnnnnnn, @SDGGiesbrecht, and @itaiferber. It was meant to be a smaller less controversial short-term approach, but this way provides much more functionality and obviates some of the design details such as the optional-ness in APIs.
This approach is a combination of @xwu’s ordering semantics with @beccadax’s RelativeBound
and @dabrahams ’s syntax.
If any of you want to be a co-author or acknowledged in the formal proposal, please let me know.