TRA

TRA-3

Tip: 在 Swift 中实现 protected 对应的功能

无论是 ObjC 还是 Swift, 都没有提供原生的 protected 概念.

在 ObjC 中, 经常把那些对应 protected 的方法定义在一个特殊的 .h 文件中, 要求子类的实现者在需要调用这些方法时, 引用这个头文件. 这当然只是一个 trick, 因为事实上没有办法避免非子类实现者也引用这个头文件, 再加上 ObjC 的 runtime 的存在, 本质上并没有办法阻止这些方法暴露出去. 而在 Swift 中, 由于一些设计方面的理由, protected 被认为是不必要的. 而因为 Swift 没有头文件的概念, 之前 ObjC 中的 trick 根本无法实施, 从而只能靠 comment 或者 documentation 约定来指明哪些方法应被视作 protected.

跳出原有的思维, 来看一看 protected 能完成的任务, 通常我们需要做到这样的效果.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
open class Base {
  final public func routine() {
    var value = step1()
    value = step2(value)
    step3(value)
  }

  private func step1() -> Int {
    100
  }
  open func step2(_ input: Int) -> Int {
    input
  }
  private func step3(_ value: Int) {
    print(value)
  }

  // MARK: protected methods
  final func util1() -> Int {
    Int(Date.timeIntervalSinceReferenceDate)
  }

  final func util2(_ value: Int) -> Int {
    (value * 3 + 50) / 2
  }
}

class Derived: Base {
  override func step2(_ input: Int) -> Int {
    util1() + util2(input)
  }
}

let object: Base = Derived()
object.routine()

// 无法阻止
object.util1()

这个 Base 类提供了一个 routine 方法作为其 API, 其内部实现把步骤分为 3 步, 其中开始和结束步骤是固定的, 允许子类通过重写第二个步骤来扩展基类的功能. 同时基类提供了一系列 protected 方法, 供子类在扩展过程中调用. 在上面的实现中, 我们通过 comment, 将基类中的一些方法标注为 protected, 但这样显然无法阻止它们被基类实现者以外的 code 访问.

为了解决这个问题, 我们可以把那些只允许子类调用的 protected 方法标记成 private, 同时改写允许子类扩展功能的那部分方法的接口, 把 protected 方法作为 closure 参数注入到这个待扩展的方法中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
open class Base {
  final public func routine() { 
    var value = step1()
    // note: 这里用到了 partial application 语法. 当然也可以构造一个临时的 closure, 包一层调用.
    value = step2(value, self.util1, self.util2)
    step3(value)
  }

  private func step1() -> Int { /* same as before */ }
  private func step3(_ value: Int) { /* same as before */ }

  open func step2(_ input: Int, 
    _ util1: () -> Int, 
    _ util2: (Int) -> Int
  ) -> Int {
    input
  }

  private func util1() -> Int { /* same as before */ }
  private func util2(_ value: Int) -> Int { /* same as before */ }
}

class Derived: Base {
  override func step2(_ input: Int, 
    _ util1: () -> Int,
    _ util2: (Int) -> Int
  ) -> Int {
    util1() + util2(input)
  }
}

let object: Base = Derived()
object.routine()

// compiler error
object.util1()

当 protected 方法比较多时, 上面的方式可能造成允许子类扩展功能的那些方法拥有太长的签名, 此时可以通过进一步把 protected 方法用 struct 或 protocol 包装一下, 作为 1 个参数传递给子类. 只要注意把封装了 protected 方法的类型定义为 private, 就可以保证这些方法不可能在允许子类扩展的那个方法以外的地方被调用.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
protocol ProtectedMethods {
  func util1()  -> Int
  func util2(_ value: Int) -> Int
}

open class Base {
  private class Protected: ProtectedMethods {
    private unowned let base: Base

    init(_ base: Base) {
      self.base = base
    }

    func util1()  -> Int {
      base.util1()
    }
    func util2(_ value: Int) -> Int {
      base.util2(value)
    }
  }

  final public func routine() { 
    var value = step1()
    value = step2(value, Protected(self))
    step3(value)
  }

  private func step1() -> Int { /* same as before */}
  private func step3(_ value: Int) { /* same as before */ }

  open func step2(_ input: Int, _ protected: ProtectedMethods) -> Int {
    input
  }

  private func util1() -> Int { /* same as before */ }
  private func util2(_ value: Int) -> Int { /* same as before */ }
}

class Derived: Base {
  override func step2(_ input: Int, _ protected: ProtectedMethods) {
    protected.util1() + protected.util2(input)
  }
}

可以看到, 只要跳出其他语言中 protected 使用姿势的思维限制, 通过调整 API 的设计, 我们也能在 Swift 中达到类似的效果.

Receive: 了解 Swift Runtime 实现

最近我在阅读一位前 Apple 雇员, 前 Swift Core Team 成员 Jordan Rose 今年在其 blog 上写的 Swift 系列文章. 业界系统性介绍 Swift 编译器的文章少之又少, 而有的一些, 从时间上说也不能代表 “state of the art” 的 Swift 实现. 因此他的这一系列文章必定让 Swift 爱好者受益匪浅.

Jordan 最初是想在一台老式的运行 Mac OS 9 系统的电脑上运行 Swift, 为了达到这个纯粹是技术性追求的目的, 他需要对 Swift 编译器做一些调整, 使之能把输入的 Swift 源文件转换成能在 Mac OS 9 上运行的二进制文件. 作者说, 这个过程对他而言也是一个不断学习的过程, 加深了他对 Swift runtime 和编译器各个部分的理解, 于是决定把这部分分享给 Swift 社区.

截止到目前一共有 7 篇介绍 Swift 原理的 blog:

由于一些时间原因, 这一些列暂时是停更的状态, 但大佬说之后会继续.

Algorithm: Longest Valid Parentheses

题目

来自 LeetCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

  Input: s = "(()"
  Output: 2
  Explanation: The longest valid parentheses substring is "()".

Example 2:

  Input: s = ")()())"
  Output: 4
  Explanation: The longest valid parentheses substring is "()()".

实现

使用动态规划思想, 在遍历每个字符的过程中, 记录以当前字符为结束字符的最大匹配的括号长度. 这样下一个字符是否产生匹配, 以及匹配的长度可以完全由当前字符决定.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func longestValidParentheses(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  
  let c1 = Character("(").asciiValue!

  // 保存最大的长度
  var runningLength = 0
  let length = s.utf8.count
  return s.withCString { pointer in
    // 保存各个字符对应的最大长度
    var bookkeeping = [0]
  
    for i in 1..<length {
      let current = pointer[i]
      if current == c1 {
        // 当前字符为 "(", 不可能匹配
        bookkeeping.append(0)
      } else {
        // 当前字符为 ")"
        // 找到之前位置 (i - 1) 的字符对应匹配的开始的前一个字符
        let evenSide = i - 1 - bookkeeping[i - 1]
        guard evenSide >= 0 && pointer[evenSide] == c1 else {
          // 若该字符是 ")", 说明不可能匹配
          bookkeeping.append(0)
          continue
        }
        // 该字符是 "(", 说明可以匹配. 匹配的长度是: 在前一个字符的匹配长度基础上, 增加前一个字符匹配开始处再前一个字符对应的匹配长度
        let maxLength = i - evenSide + 1 +
          (evenSide > 0 ? bookkeeping[evenSide - 1] : 0)
        bookkeeping.append(maxLength)
        
        // 更新全局 max
        if maxLength > runningLength {
          runningLength = maxLength
        }
      }
    }
    return runningLength
  }
}

实现中使用了withCString, 在不产生 copy 的情况下允许了 random access 的 indexing 操作, 增强了性能.

性能分析

由于使用动态规划思想, 上面的实现只使用一次遍历, 时间复杂度仅为 O(n)O(n). 事实上在 leetcode 上的运行结果也是 “super fast” 的😁.