Kotlin 协程 | CoroutineContext 为什么要设计成 indexed set？（一）

CoroutineContext是 Kotlin 协程中的核心概念，它是用来干嘛的？它由哪些元素组成？它为什么要这样设计？这篇试着分析源码以回答这些问题。

indexed set 既是 set 又是 map？

CoroutineContext的定义如下：

/**

 * Persistent context for the coroutine. It is an indexed set of [Element] instances.

 * An indexed set is a mix between a set and a map.

 * Every element in this set has a unique [Key].

 */

public interface CoroutineContext { ... }

暂且把CoroutineContext译成协程上下文，简称上下文。

从注解来看，上下文是一个Element的集合，这种集合被称为indexed set。它是介于 set 和 map 之间的一种结构。set 意味着其中的元素有唯一性，map 意味着每个元素都对应一个键。

public interface CoroutineContext {

    // Element 也是一个上下文

    public interface Element : CoroutineContext { ... }

}

没想到Element也是一个上下文，所以协程上下文是包含了一系列上下文的集合（自己包含自己）。暂且称在协程上下文内部的一系列上下文为子上下文。

上下文如何保证子上下文各自的唯一性？

public interface CoroutineContext {

    public interface Key<E : Element>

}

上下文为每个子上下文分配了一个Key，它是一个带有类型信息的接口。这个接口通常被实现为companion object：

// 子上下文：Job

public interface Job : CoroutineContext.Element {

    // Job 的静态 Key

    public companion object Key : CoroutineContext.Key<Job> { ... }

}


// 子上下文：拦截器

public interface ContinuationInterceptor : CoroutineContext.Element {

    // 拦截器的静态 Key

    companion object Key : CoroutineContext.Key<ContinuationInterceptor>

}


// 子上下文：协程名

public data class CoroutineName( val name: String ) : AbstractCoroutineContextElement(CoroutineName) {

    // 协程名的静态 Key

    public companion object Key : CoroutineContext.Key<CoroutineName>

}


// 子上下文：异常处理器

public interface CoroutineExceptionHandler : CoroutineContext.Element {

    // 异常处理器的静态 Key

    public companion object Key : CoroutineContext.Key<CoroutineExceptionHandler>

}

列举了若干源码中定义的子上下文，它们有一个共性，都会在内部声明一个静态的Key，类内部的静态变量意味着被所有类实例共享，即全局唯一的 Key 实例可以对应多个子上下文实例。然而在一个类似 map 的结构中，每个键必须是唯一的，因为对相同的键 put 两次值，新值会代替旧值。如此一来，键的唯一性这就保证了上下文中的所有子上下文实例都是唯一的。这就是indexed set集合的内涵。

做个阶段性总结：

1. 
   
2. 
   

   协程上下文是一个元素的集合，单个元素本身也是一个上下文，所以协程上下文的定义是递归的，自包含的（自己包含若干个自己）。

   
   
   
3. 
   

   协程上下文这个集合有点像 set 结构，因为其中的元素都是唯一的，不重复的。为了做到这一点，每一个元素都配有一个静态的键实例，构成一组键值对，这使得它又有点像 map 结构。这种介于 set 和 map 之间的结构称为indexed set

   
   
   

从 indexed set 获取元素

集合必然提供了存取其中元素的方法，CoroutineContext是Element元素的集合，取元素的方法定义如下：

public interface CoroutineContext {

    // 根据 key 在上下文中查找元素

    public operator fun <E : Element> get(key: Key<E>): E?

}

get()方法输入 Key 返回 Element。CoroutineContext 的子类Element有一个get()的实现：

public interface CoroutineContext {

    // 元素

    public interface Element : CoroutineContext {

        // 元素的键

        public val key: Key<*>

        public override operator fun <E : Element> get(key: Key<E>): E? =

            // 如果给定键和元素本身键相同，则返回当前元素，否则返回空

            if (this.key == key) this as E else null

    }

}

协程上下文是元素的集合，而元素也是一个上下文，所以元素也是一个元素的集合（解释递归的定义有点像绕口令）。只不过这个元素集合有一点特别，它只包含一个元素，即它本身。这从Element.get()方法的实现中也可以看出：当从 Element 的元素集合中获取元素时，要么返回自身，要么返回空。

协程上下文还有一个实现类叫CombinedContext混合上下文，它的get()实现如下：

// 混合上下文(大蒜)

internal class CombinedContext(

    // 左上下文

    private val left: CoroutineContext,

    // 右元素

    private val element: Element

) : CoroutineContext, Serializable {

    // 根据 key 在上下文中查找元素

    override fun <E : Element> get(key: Key<E>): E? {

        var cur = this

        while (true) {

            // 如果输入 key 和右元素的 key 相同，则返回右元素（剥去大蒜的一片）

            cur.element[key]?.let { return it }

            // 若右元素不匹配，则向左继续查找

            val next = cur.left

            // 如果左上下文是混合上下文，则开始向左递归（剥去一片后还是一个大蒜，继续剥）

            if (next is CombinedContext) {

                cur = next

            } 

            // 若左上下文不是混合上下文，则结束递归

            else {

                return next[key]

            }

        }

    }

}

CombinedContext.get() 用 while 循环实现了类似递归的效果。CombinedContext的定义本身就是递归的，它包含两个成员：left和element，其中left是一个协程上下文，若left实例是另一个CombinedContext，就发生了自己包含自己的递归情况，这结构非常像大蒜：left是“蒜体”，element是“蒜皮”。当剥开一片蒜皮后，发现还是一颗大蒜，只是变小了而已。

CombinedContext.get() 这个算法就好比是“找到一棵大蒜中指定的一片蒜皮”，每剥去一片，都检查一下是不是想要的那一片，若不是就继续剥下一片，就这样递归地进行下去，直到命中了指定片或大蒜被剥空了。

CombinedContext这颗大蒜还是偏心的，即它的最后一片不在正中心，而是在最左边（当left的类型不再是CombinedContext时），但遍历这颗大蒜是从最右边开始向左进行的，这使得每一片蒜皮拥有不同的优先级，越早被遍历到，优先级越高。

做一个阶段性总结：

CombinedContext是协程上下文的一个具体实现，就像协程上下文一样，它也包含了一组元素，这组元素被组织成 “偏心大蒜” 这种自包含的结构。偏心大蒜也是 indexed set 的一种具体实现，即它用唯一键对应唯一值的方式保证了集合中元素的唯一性。但和 set 和 map 这种“平”的结构不同的是，偏心大蒜内元素天然是有层级的，遍历大蒜结构是从外层向内（从右到左）进行的，越先被遍历到的元素自然具有较高的优先级。

向 indexed set 追加元素

说完取元素操作，接着说存元素：

public interface CoroutineContext {

    // 重载操作符

    public operator fun plus(context: CoroutineContext): CoroutineContext =

    // 若追加上下文是空的（等于啥也没追加），则直接返回当前山下文（高性能返回）

    if (context === EmptyCoroutineContext) this else 

        // 以当前上下文为初始值进行累加

        context.fold(this) { acc, element -> // 累加算法 }

}

CoroutineContext 使用operator保留词重载了plus操作符，即重新定义运算符的语义。Kotlin 中预定义了一些函数名和运算符的对应关系，称为约定。当前这个就是plus()和+的约定。当两个 CoroutineContext 实例通过+相连时，就等价于调用了plus()方法，这样做的目的是增加代码可读性。

plus() 的返回值是CoroutineContext，这使得c1 + c2 + c3这样的链式调用变得方便。

EmptyCoroutineContext是一个特殊的上下文，它不包含任何元素，这从它的get()方法的实现中可见一斑：

// 空协程上下文

public object EmptyCoroutineContext : CoroutineContext, Serializable {

    // 返回空元素

    public override fun <E : Element> get(key: Key<E>): E? = null

    ...

}

plus() 中调用的CoroutineContext.fold()是将协程上下文中元素进行累加的接口：

public interface CoroutineContext {

    public fun <R> fold(initial: R, operation: (R, Element) -> R): R

}

fold() 需要输入一个累加初始值initial和累加算法operation。先来看看 plus() 方法中定义的累加算法：

public interface CoroutineContext {

    public operator fun plus(context: CoroutineContext): CoroutineContext =

    if (context === EmptyCoroutineContext) this else 

        // 以当前上下文为初始值进行累加

        context.fold(this) { acc, element ->

            // 将追加的元素抽出以便将其重定位

            val removed = acc.minusKey(element.key)

            // 若集合中只包含追加元素，则不需要重定位，直接返回

            if (removed === EmptyCoroutineContext) element else {

                // 获取元素集合中的 Interceptor

                val interceptor = removed[ContinuationInterceptor]

                // 如果元素集合中不包含 Interceptor 则将追加元素作为最外层蒜皮

                if (interceptor == null) CombinedContext(removed, element) else {

                    // 如果元素集合中包含 Interceptor 则将其抽出以便将其重定位

                    val left = removed.minusKey(ContinuationInterceptor)

                    // 元素集合中只包含 Interceptor 和追加元素

                    if (left === EmptyCoroutineContext) CombinedContext(element, interceptor) else

                        // 将 Interceptor 作为最外层蒜皮，追加元素作为次外层蒜皮

                        CombinedContext(CombinedContext(left, element), interceptor)

                }

            }

        }

}

累加算法有两个输入参数，一个代表当前累加值acc，另一个代表新追加的元素element。上述算法可以概括为：“当向协程上下文中追加元素时，总是会将所有元素重定位。定位原则如下：将 Interceptor 和新追加的元素依次放在偏心大蒜的最外层和次外层。”

minusKey()

其中minusKey()也是协程上下文的一个接口：

public interface CoroutineContext {

    public fun minusKey(key: Key<*>): CoroutineContext

}

minusKey()返回一个协程上下文，该上下文的元素集合中去掉了 key 对应的元素。Element 对该接口的实现如下：

public interface Element : CoroutineContext {

    public override fun minusKey(key: Key<*>): CoroutineContext =

        if (this.key == key) EmptyCoroutineContext else this

}

因为 Element 只包含一个元素，如果要去掉的元素就是它自己，则返回一个空上下文，否则返回自己。

CombineContext 对 minusKey() 的实现如下：

internal class CombinedContext(

    private val left: CoroutineContext,

    private val element: Element

) : CoroutineContext, Serializable {

    public override fun minusKey(key: Key<*>): CoroutineContext {

    // 1. 如果最外层就是要去掉的元素，则直接返回左上下文

    element[key]?.let { return left }

    // 2. 在左上下文中去掉对应元素

    val newLeft = left.minusKey(key)

    return when {

        // 2.1 左上下文中也不包含对应元素

        newLeft === left -> this

        // 2.2 左上下文中除了对应元素外不包含任何元素，返回右元素

        newLeft === EmptyCoroutineContext -> element

        // 2.3 将移除了对应元素的左上下文和右元素组合成新得混合上下文

        else -> CombinedContext(newLeft, element)

    }

}

可以总结为：在偏心大蒜结构中找到对应的蒜皮，并把它剔除，然后将剩下的所有蒜皮按原来的顺序重新组合成偏心大蒜结构。

Element.fold()

分析完累加算法之后，看看Element对fold()的实现：

public interface CoroutineContext {

    public interface Element : CoroutineContext {

        public override fun <R> fold(initial: R, operation: (R, Element) -> R): R =

            operation(initial, this)

}

Element 在这个方法中将自己作为追加值。结合上面的累加算法，可以这样理解 Element 累加：“Element 总是将自己作为被追加的元素，即 Element 总是会出现在偏心大蒜的最外层。”

举个例子：

val e1 = Element()

val e2 = Element()

val context = e1 + e2

上述代码中的 context 是一个什么结构？推理如下：

• 
  
• e1 + e2 等价于e2.fold(e1)
  
• 因为 e2 是 Element 类型，所以调用 Element.fold()，等价于operation(e1, e2)
  
• operation 就是上述累加算法，结合累加算法，最终得出 context = CombinedContext(e1, e2)
  

再举一个更复杂的例子：

val e1 = Element()

val e2 = Element()

val e3 = Element()

val c = CombinedContext(e1, e2)

val context = c + e3

上述代码中的 context 是一个什么结构？推理如下：

• 
  
• c + e3 等价于e3.fold(c)
  
• 因为 e3 是 Element 类型，所以调用 Element.fold()，等价于operation(c, e3)
  
• operation 就是上述累加算法，结合累加算法，最终得出 context = CombinedContext(c, e2)
  
• 将 context 完全展开如下：CombinedContext(CombinedContext(e1, e2), e3)
  

做一个阶段性总结：

两个协程上下文做加法运算意味着将它们的元素合并形成一个新的更大的偏心大蒜。若被加数是 Element 类型的，即被加数中只包含一个元素，则该元素总是被追加到偏心的大蒜的最外层。

CombinedContext.fold()

再来看看CombinedContext对fold()的实现：

internal class CombinedContext(

    private val left: CoroutineContext,

    private val element: Element

) : CoroutineContext, Serializable {

    public override fun <R> fold(initial: R, operation: (R, Element) -> R): R =

        operation(left.fold(initial, operation), element)

}

这就比 Element 的复杂多了，因为有递归。

还是举一个例子：

val e1 = Element()

val e2 = Element()

val e3 = Element()

val c = CombinedContext(e1, e2)

val context = e3 + c // 和上一个例子几乎是一样的，只是换了下加数与被加数的位置

上述代码中的 context 是一个什么结构？推理如下：

• 
  
• e3 + c 等价于c.fold(e3)
  
• 因为 c 是 CombinedContext 类型，所以调用 CombinedContext.fold()，等价于operation(e1.fold(e3), e2)
  
• 其中e1.fold(e3)等价于operation(e3, e1)，它的值为 CombinedContext(e3, e1)
  
• 将第三步结果代入第二步，最终得出 context = CombinedContext(CombinedContext(e3, e1), e2)
  

再做一个阶段性总结：

两个协程上下文做加法运算意味着将它们的元素合并形成一个新的更大的偏心大蒜。若被加数是 CombinedContext 类型的，即被加数包含一个左侧的蒜体和一个右侧的蒜皮，则蒜皮还是在原来的位置待着，蒜体会和加数融合成新的偏心大蒜结构。

总结

这一篇介绍了 CoroutineContext 的数据结构，它包含如下特征：

1. 
   
2. 协程上下文是一个元素的集合，单个元素本身也是一个上下文，所以协程上下文的定义是递归的，自包含的（自己包含若干个自己）。
   
3. 协程上下文这个集合有点像 set 结构，因为其中的元素都是唯一的，不重复的。为了做到这一点，每一个元素都配有一个静态的键实例，构成一组键值对，这使得它又有点像 map 结构。这种介于 set 和 map 之间的结构称为indexed set
   
4. CombinedContext是协程上下文的一个具体实现，就像协程上下文一样，它也包含了一组元素，这组元素被组织成 “偏心大蒜” 这种自包含的结构。偏心大蒜也是 indexed set 的一种具体实现，即它用唯一键对应唯一值的方式保证了集合中元素的唯一性。但和 set 和 map 这种“平”的结构不同的是，偏心大蒜内元素天然是有层级的，遍历大蒜结构是从外层向内（从右到左）进行的，越先被遍历到的元素自然具有较高的优先级。
   
5. 两个协程上下文做加法运算意味着将它们的元素合并形成一个新的更大的偏心大蒜。若被加数是 Element 类型的，即被加数中只包含一个元素，则该元素总是被追加到偏心的大蒜的最外层。若被加数是 CombinedContext 类型的，即被加数包含一个左侧的蒜体和一个右侧的蒜皮，则蒜皮还是在原来的位置待着，蒜体会和加数融合成新的偏心大蒜结构。