Range and Protocol-Oriented Programming
Range
This article explains some implementation details of the Range family and some concrete examples of protocol-oriented programming in Swift. For convenience, both class and struct will be referred to as “types.”
Introduction
Before Swift 4.0, the Range family had four types:
1
2
3
4
let rang: Range = 0.0..<1.0 // half-open range
let closedRange: ClosedRange = 0.0...1.0 // closed range
let countableRange: CountableRange = 0..<1 // countable half-open range
let countableClosedRange: CountableClosedRange = 0...1 // countable closed range
Swift 4.0 then introduced four more types:
1
2
3
4
let partialRangeThrough: PartialRangeThrough = ...1.0 // one-sided range
let partialRangeFrom: PartialRangeFrom = 0.0... // one-sided range
let partialRangeUpTo: PartialRangeUpTo = ..<1.0 // one-sided range
let countablePartialRangeFrom: CountablePartialRangeFrom = 1... // countable one-sided range
By Swift 4.2, only five types remained: Range, ClosedRange, PartialRangeThrough, PartialRangeFrom, and PartialRangeUpTo. All Countable types became corresponding typealiases.
1
2
3
public typealias CountableRange<Bound> = Range<Bound>
public typealias CountableClosedRange<Bound> = ClosedRange<Bound>
public typealias CountablePartialRangeFrom<Bound> = PartialRangeFrom<Bound>
Basic Structure
All Range types are structs with a generic Bound, and that Bound must conform to Comparable.
1
2
3
4
5
public struct Range<Bound> where Bound : Comparable
public struct ClosedRange<Bound> where Bound : Comparable
public struct PartialRangeThrough<Bound> where Bound : Comparable
public struct PartialRangeFrom<Bound> where Bound : Comparable
public struct PartialRangeUpTo<Bound> where Bound : Comparable
In the Swift standard library, most basic types conform to this protocol, including String, Date, and IndexPath.
1
2
3
let stringRange = "a"..<"z"
let dateRange = Date()...Date()
let indexRange = IndexPath(item: 0, section: 0)...IndexPath(row: 1, section: 0)
When you need to create a Range from a custom type, all you need is for it to conform to Comparable and implement the relevant methods, for example:
1
2
3
4
5
6
7
8
9
10
11
12
13
struct Foo: Comparable {
var value: Int
static func < (lhs: Foo, rhs: Foo) -> Bool {
return lhs.value < rhs.value
}
init(_ v: Int) {
value = v
}
}
let range = Foo(1)...Foo(20)
foo.contains(Foo(2)) // true
contains(_:) is also implemented automatically, which is actually thanks to the RangeExpression protocol:
1
public func contains(_ element: Self.Bound) -> Bool
The reason is that each Range type has an extension: when the generic Bound conforms to Comparable, the corresponding type is extended to conform to RangeExpression.
1
extension Range : RangeExpression where Bound : Comparable
1
extension ClosedRange : RangeExpression where Bound : Comparable
1
extension PartialRangeThrough : RangeExpression where Bound : Comparable
1
extension PartialRangeFrom : RangeExpression where Bound : Comparable
1
extension PartialRangeUpTo : RangeExpression where Bound : Comparable
Try to imagine how you would normally implement contains(_:) in an object-oriented language.
Countable Implementation Details
As mentioned earlier, in Swift 4.2 all Countable types are typealiases. Whether a type is countable is abstracted onto the generic Bound. Using ClosedRange as an example:
1
2
3
4
5
6
7
8
9
extension ClosedRange : Sequence where Bound : Strideable, Bound.Stride : SignedInteger {
/// A type representing the sequence's elements.
public typealias Element = Bound
/// A type that provides the sequence's iteration interface and
/// encapsulates its iteration state.
public typealias Iterator = IndexingIterator<ClosedRange<Bound>>
}
You can see that in order to conform to Sequence, the generic Bound must first conform to Strideable. The Strideable protocol is defined as follows:
1
2
3
4
5
6
7
8
public protocol Strideable : Comparable {
/// A type that represents the distance between two values.
associatedtype Stride : Comparable, SignedNumeric
public func distance(to other: Self) -> Self.Stride
public func advanced(by n: Self.Stride) -> Self
}
It has a bound type Stride and two methods that must be implemented. So Bound.Stride : SignedInteger means that the bound type Stride of Strideable must conform to SignedInteger.
To summarize, Swift uses generic constraints, associated type constraints in protocols, and extensions to abstract Countable behavior onto the generic Bound. In the end, the generic Bound determines whether a Range has Sequence capability.
Why Int Can Create a Countable Range
You may know that a Range created from Int is a CountableRange, but why is that? First, Int conforms to FixedWidthInteger and SignedInteger.
1
public struct Int : FixedWidthInteger, SignedInteger
SignedInteger in turn conforms to BinaryInteger and SignedNumeric.
1
2
public protocol SignedInteger : BinaryInteger, SignedNumeric {
}
Under certain conditions, BinaryInteger also conforms to Strideable.
1
public protocol BinaryInteger : CustomStringConvertible, Hashable, Numeric, Strideable where Self.Magnitude : BinaryInteger, Self.Magnitude == Self.Magnitude.Magnitude
Looking at the Strideable implementation for BinaryInteger:
1
2
3
4
extension BinaryInteger {
public func distance(to other: Self) -> Int
public func advanced(by n: Int) -> Self
}
you will find that the Stride type is Int, and Int itself conforms to SignedInteger, which satisfies the earlier Bound.Stride : SignedInteger requirement. Finally, do not forget the other constraint:
1
where Self.Magnitude : BinaryInteger, Self.Magnitude == Self.Magnitude.Magnitude
Magnitude is the associated type of the Numeric protocol, which is defined as follows:
1
2
3
4
public protocol Numeric : Equatable, ExpressibleByIntegerLiteral {
associatedtype Magnitude : Comparable, Numeric
public var magnitude: Self.Magnitude { get }
}
But there is no extension on BinaryInteger that defines a Magnitude type. That can only mean Magnitude is specified on concrete types. Looking at Int, we find Magnitude immediately:
1
2
3
public struct Int : FixedWidthInteger, SignedInteger {
public typealias Magnitude = UInt
}
Now look at UInt:
1
2
3
public struct UInt : FixedWidthInteger, UnsignedInteger {
public typealias Magnitude = UInt
}
UnsignedInteger also conforms to BinaryInteger.
1
2
public protocol UnsignedInteger : BinaryInteger {
}
So Self.Magnitude : BinaryInteger, Self.Magnitude == Self.Magnitude.Magnitude is equivalent to Int.UInt : BinaryInteger, Int.UInt == Int.UInt.UInt. At this point, Int satisfies all requirements. In fact, not only Int, but the entire Int family and UInt family satisfy these conditions. Below is a rough protocol inheritance relationship for Int and UInt.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
+---------------+
| Comparable |
+-------+-------+
^
|
+-------------+ +-----+-------+
+------>+ Numeric | | Strideable |
| +------------++ +-----+-------+
| ^ ^
| | |
+-------+-------+ +---+----------+----+
| SignedNumeric | | BinaryInteger |
+------+--------+ +---+-----+-----+---+
^ +-----------^ ^ ^----------+
| | | |
+------+---------++ +-----------+--------+ +----+-------------+
| SignedInteger | | FixedWidthInteger | | UnsignedInteger |
+---------------+-+ +-+----------------+-+ +--+---------------+
^ ^ ^ ^
| | | |
| | | |
++--------+-+ ++-------+--+
|Int family | |UInt family|
+-----------+ +-----------+
Manually Implementing Strideable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Foo {
var value: Int
init(_ v: Int) {
value = v
}
}
extension Foo: Strideable {
func distance(to other: Foo) -> Int {
return other.value - self.value
}
func advanced(by n: Int) -> Foo {
var result = self
result.value += n
return result
}
}
While Foo conforms to Strideable, its bound is also specified as Int. This makes it possible to create a custom Range type, and it also conforms to Sequence.
1
2
3
4
5
6
let fooRange = Foo(1)...Foo(20)
fooRange.contains(Foo(2))
Array((Foo(1)..<Foo(20)))
for item in fooRange {
print(item)
}
Summary
Swift is a protocol-oriented language, and the implementation of Range reflects that clearly. With the addition of SE-0142 and SE-0143 in Swift 4.0 and Swift 4.2 respectively, this capability became even stronger.