[Swift] Rangeの種類が足りない！② 〜初めてのtype erasure〜

> 註: [Ver. 3.0.0](https://github.com/YOCKOW/SwiftRanges/commit/5e29414298c22c9ab3baa648bf68d1bc855f0ca5)から[仕様変更](https://github.com/YOCKOW/SwiftRanges/commit/5e29414298c22c9ab3baa648bf68d1bc855f0ca5#diff-22721018930b6264c7fced4150f4fe88)があって、この記事の内容は古くなっています。ただ、簡単なtype erasureの実装について参考になる(なればいいなー)と思いますので、記事はこのまま残しておきます。

# 概要

[前回](https://qiita.com/YOCKOW/items/0cf8ababc9b81b730fc3)、Swiftに足りないRangeを[実装](https://github.com/YOCKOW/SwiftRanges)したよ。
そこで、いろんなRangeを一貫性を持って扱えるように`AnyRange`というtype erasureを実装したよ！
初めてtype erasureを実装して勉強になったよ！

# なぜ`AnyRange`が必要？

次のような「断続的な範囲」を表す構造体が欲しくて。そのためには`AnyRange`みたいなtype erasureがあると便利かなって…。

```swift:MultipleRanges.swift
public struct MultipleRanges<Bound> where Bound:Comparable {
  private var _ranges: [AnyRange<Bound>] = []
  // RangeExpressionはassociatedtypeを持っているため
  // var _ranges:[RangeExpression] とはできない
}
```

# 却下案

```swift
public enum AnyRange<Bound> where Bound: Comparable {
  case empty
  case unbounded
  case closedRange(ClosedRange<Bound>)
  case leftOpenRange(LeftOpenRange<Bound>)
  case openRange(OpenRange<Bound>)
  case range(Range<Bound>)
  case partialRangeFrom(PartialRangeFrom<Bound>)
  case partialRangeGreaterThan(PartialRangeGreaterThan<Bound>)
  case partialRangeThrough(PartialRangeThrough<Bound>)
  case partialRangeUpTo(PartialRangeUpTo<Bound>)
}
```

所詮は範囲を表す構造体の種類なんて有限個だから、ということで力技で実装する案。
別にこれはこれでよかったのですが、次の2つの理由から却下となりました：

* Swiftのバグ([SR-8192](https://bugs.swift.org/browse/SR-8192))があった(ただし、Swift 4.2では解決済み)。
* `overlaps(_:)`などを実装しようとするときに煩雑になった。


# 採用案 〜自前のプロトコルを用意する〜

## 既存のプロトコルを知る

Swiftには[`RangeExpression`](https://developer.apple.com/documentation/swift/rangeexpression)というプロトコルがあります。しかし、このプロトコルは

```swift
func contains(_ element: Self.Bound) -> Bool
func relative<C>(to collection: C) -> Range<Self.Bound> where C : Collection, Self.Bound == C.Index
```

という2つのインスタンスメソッドぐらいしか定義されておらず、“これでtypeをeraseしちゃったら何も残らないじゃん”というわけで、このプロトコロルを元にtype erasureを作るわけにはいかないと結論づけました。

## 新たなプロトコルを作る

### 「範囲」とは

新たなプロトコルを作るにあたって、まず「範囲」とは何かを考えることにしました。
まず、範囲とは「“ここからここまで”というもの」だと思ったので、“ここから”と“ここまで”、即ち範囲の境界というものを表す物を作ることにしました。

### 範囲の境界を表す構造体

```swift:Boundary.swift
public struct Boundary<Bound> where Bound: Comparable {
  public let bound: Bound
  public let isIncluded: Bool
}
```

ということで、範囲の両端(のどちらか)を表す構造体を定義してみました。名前は`Bound`でもよかったのですが、`RangeExpression`の`associatedtype`である`Bound`と被ってしまってややこしくなりそうだったので`Boundary`にしました。
範囲では、その境界自体を含むかどうかというのもあるので、`let isIncluded: Bool`というプロパティを用意しました。

### 「両端」を表すためには

```swift:GeneralizedRange.swift
public typealias Bounds<Bound> =
  (lower:Boundary<Bound>?, upper:Boundary<Bound>?) where Bound:Comparable
```

構造体でも良かったのかもしれませんが、メソッドを持たせる予定もなかったのでtupleで済ませました。なお、Partial Rangeは「端っこがない」ということで`nil`で表します。たとえば、`PartialRangeFrom`では`(lower:Boundary<Bound>(bound:self.lowerBound, isIncluded:true), upper:nil)`というような感じです。`lower`も`upper`も`nil`ならunboundedと考えます。
このように、`Bounds<Bound>`を使えば任意の範囲を表すことができるはずです。

### プロトコロルを定義する

これで下準備も整ったので、`GeneralizedRange`というプロトコルを定義しました：

```Swift:GeneralizedRange.swift
public protocol GeneralizedRange: RangeExpression {
  var bounds: Bounds<Bound>? { get }
}
```

すごく単純で、前述のように`Bounds<Bound>`を使えば任意の範囲を表すことができるはずなので、プロパティとして`var bounds: Bounds<Bound>? { get }`さえ持っていればいいことにしました。なおOptionalになっているのは、空の範囲を表す場合は`var bounds`の値として`nil`を返すようにしたかったからです[^empty-open-range]。


## `GeneralizedRange`を用いてtype erasureの実装

### `GeneralizedRange`に準拠させる

というわけで、いろんな範囲を表す構造体を`GeneralizedRange`に準拠させてみましょう：

```swift
extension ClosedRange: GeneralizedRange {
  public var bounds: Bounds<Bound>? {
    if self.isEmpty { return nil }
    return (lower:Boundary<Bound>(bound:self.lowerBound, isIncluded:true),
            upper:Boundary<Bound>(bound:self.upperBound, isIncluded:true))
  }
}

extension LeftOpenRange: GeneralizedRange {
  public var bounds:Bounds<Bound>? {
    if self.isEmpty { return nil }
    return (lower:Boundary<Bound>(bound:self.lowerBound, isIncluded:false),
            upper:Boundary<Bound>(bound:self.upperBound, isIncluded:true))
  }
}

extension OpenRange: GeneralizedRange {
  public var bounds:Bounds<Bound>? {
    if self.isEmpty { return nil }
    return (lower:Boundary<Bound>(bound:self.lowerBound, isIncluded:false),
            upper:Boundary<Bound>(bound:self.upperBound, isIncluded:false))
  }
}

extension Range: GeneralizedRange {
  public var bounds: Bounds<Bound>? {
    if self.isEmpty { return nil }
    return (lower:Boundary<Bound>(bound:self.lowerBound, isIncluded:true),
            upper:Boundary<Bound>(bound:self.upperBound, isIncluded:false))
  }
}

extension PartialRangeFrom: GeneralizedRange {
  public var bounds: Bounds<Bound>? {
    return (lower:Boundary<Bound>(bound:self.lowerBound, isIncluded:true),
            upper:nil)
  }
}

extension PartialRangeGreaterThan: GeneralizedRange {
  public var bounds: Bounds<Bound>? {
    return (lower:Boundary<Bound>(bound:self.lowerBound, isIncluded:false),
            upper:nil)
  }
}

extension PartialRangeThrough: GeneralizedRange {
  public var bounds: Bounds<Bound>? {
    return (lower:nil,
            upper:Boundary<Bound>(bound:self.upperBound, isIncluded:true))
  }
}

extension PartialRangeUpTo: GeneralizedRange {
  public var bounds: Bounds<Bound>? {
    return (lower:nil,
            upper:Boundary<Bound>(bound:self.upperBound, isIncluded:false))
  }
}
```

## `AnyRange<Bound>`を実装

繰り返しになりますが、`Bounds<Bound>?`さえあれば任意の範囲を表すことができるので、`AnyRange<Bound>`はプロパティとして`Bounds<Bound>?`のみを保持することにします：

```swift:AnyRange.swift
public struct AnyRange<Bound> where Bound:Comparable {
  private let _bounds: Bounds<Bound>?
}
```

あとは、引数に`GeneralizedRange`に準拠するインスタンスを受け取るイニシャライザを実装すれば、type erasureの完成です！

```swift:AnyRange.swift
extension AnyRange {
  public init<T>(_ range:T) where T:GeneralizedRange, T.Bound == Bound {
    self._bounds = range.bounds
    // 実際の実装では`bounds`の有効性チェックなどが入るので、
    // もう少し複雑になっています。
  }
}
```

### おまけ: `AnyRange`も`GeneralizedRange`に準拠させる

当然ながら、`AnyRange`も`GeneralizedRange`に準拠させることは簡単です：

```swift:AnyRange.swift
extension AnyRange: GeneralizedRange {
  public var bounds: Bounds<Bound>? {
    return self._bounds
  }
}
```

# おわりに

Qiitaに「[Swift の Type Erasure の実装パターンの紹介](https://qiita.com/omochimetaru/items/5d26b95eb21e022106f0)」という記事があったので、`AnyRange`はどのパターンかなと探したのですが、どれでもありませんでした。もちろん、ここに載っていないぐらい複雑ということではなく、*“ここに載っていないぐらい単純”*ということです。
`GeneralizedRange`にはメソッドがなくプロパティのみなので(というよりは`AnyRange`で必要なのがプロパティのみなので)、クロージャもBoxも必要ないからです。
初めてのtype erasureの実装が`AnyRange`で良かったです。Boxパターンが必要なものだったら挫折していたと思います。

-----

[^empty-open-range]: `OpenRange<Bound>`は`Bound`がcountableかどうかで、空かどうかの判定が変わってくることもあって、それをプロトコル側で実装したくなかったので…。