Molinillo 依赖校验

引子

通过「前文」对 CocaPods-Core 的分析，我们大体了解了 Pod 是如何被解析、查询与管理的。有了这些整体概念之后，我们就可以逐步深入 pod install 的各个细节。今天我们就来聊聊 Pod 的依赖校验工具 — Molinillo。开始前，需要聊聊依赖校验的背景。

依赖管理的挑战

同大多数包管理工具一样 Pod 会将传递依赖的包用扁平化的形式，安装至 workspace 目录 (即：Pods/)。

依赖传递：pod A 依赖于 pod B，而 pod B 依赖 Alamofire。

01-dependency-flat

可以看到，经依赖解析原有的依赖树被拍平了，安装在同层目录中。

然而在大型项目中，遇到的更多情况可能像下面这样：

02-dependency-conflict

**依赖冲突：即 pod A 和 pod B 分别依赖不同版本的 Alamofire。这就是依赖地狱**的开始。

依赖地狱：指在操作系统中由于软件之间的依赖性不能被满足而引发的问题。

随着项目的迭代，我们不断引入依赖并最终形成错综复杂的网络。这使得项目的依赖性解析变得异常困难，甚至出现致命错误。

那么，产生的问题有哪些类型 ？

问题类型

依赖过多/多重依赖

即项目存在大量依赖关系，或者依赖本身有其自身依赖（依赖传递），导致依赖层级过深。像微信或淘宝这样的超级应用，其中的单一业务模块都可能存在这些问题，这将使得依赖解析过于复杂，且容易产生依赖冲突和依赖循环。

依赖冲突

即项目中的两个依赖包无法共存的情况。可能两个依赖库内部的代码冲突，也可能其底层依赖互相冲突。上面例子中因 Alamofire 版本不同产生的问题就是依赖冲突。

依赖循环

即依赖性关系形成一个闭合环路。如下图三个 pod 库之间互相依赖产生循环：

03-dependency-conflict

要判断依赖关系中是否存在依赖环，则需要通依赖仲裁算法来解决。

依赖关系的解决

对于依赖过多或者多重依赖问题，我们可通过合理的架构和设计模式来解决。而依赖校验主要解决的问题为：

  1. 检查依赖图是否存在版本冲突；
  2. 判断依赖图是否存在循环依赖；

0x01 版本冲突的解决方案

对于版本冲突可通过修改指定版本为带兼容性的版本范围问题来避免。如上面的问题有两个解决方案：

  • 通过修改两个 pod 的 Alamofire 版本约束为 ~> 4.0 来解决。
  • 去除两个 pod 的版本约束，交由项目中的 Podfile 来指定。

不过这样会有一个隐患，由于两个 Pod 使用的主版本不同，可能带来 API 不兼容，导致 pod install 即使成功了，最终也无法编译或运行时报错。

还有一种解决方案，是基于语言特性来进行依赖性隔离。如 npm 的每个传递依赖包如果冲突都可以有自己的 node_modules 依赖目录，即一个依赖库可以存在多个不同版本。

04-dependency-conflict

0x02 循环依赖的解决方案

循环依赖则需要需要进行数学建模生成 DAG 图，利用拓扑排序的拆点进行处理。通过确定依赖图是否为 DAG 图，来验证依赖关系的合理性。

一个 DAG 图的示例：

04-DAG

DAG 是图论中常见的一种描述问题的结构，全称**有向无环图 (Directed Acyclic Graph) **。想了解更多，可查看瓜瓜的文章 —「从拓扑排序到 Carthage 依赖校验算法」。

另外，各种包管理工具的依赖校验算法也各不相同，有如 Dart 和 SwiftPM 所使用的 PubGrub，作者号称其为下一代依赖校验算法，Yarn 的 Selective dependency resolutions，还有我们今天聊到的 Molinillo。

Molinillo

Molinillo 作为通用的依赖解析工具，它不仅应用在 CocoaPods 中，在 Bundler 1.9 版本也采用 Molinillo。另外，值得注意的是 Bundler 在 Ruby 2.6 中被作为了默认的 gem 工具内嵌。可以说 Ruby 相关的依赖工具都通过 Molinillo 完成依赖解析。

ResolutionState

Molinillo 算法的核心是基于回溯 (Backtracking) 和 向前检查 (forward checking)，整个过程会追踪栈中的两个状态 DependencyState 和 PossibilityState。

 1module Molinillo
 2  # 解析状态
 3  ResolutionState = Struct.new(
 4    # [String] 当前需求名称
 5    :name,
 6    # [Array<Object>] 未处理的需求
 7    :requirements,
 8    # [DependencyGraph] 依赖关系图
 9    :activated,
10    # [Object] 当前需求
11    :requirement,
12    # [Object] 满足当前需求的可能性
13    :possibilities,
14    # [Integer] 解析深度
15    :depth,
16    # [Hash] 未解决的冲突，以需求名为 key
17    :conflicts,
18    # [Array<UnwindDetails>] 记录着未处理过的需要用于回溯的信息
19    :unused_unwind_options
20  )
21
22  class ResolutionState
23    def self.empty
24      new(nil, [], DependencyGraph.new, nil, nil, 0, {}, [])
25    end
26  end
27
28  # 记录一组需求和满足当前需求的可能性
29  class DependencyState < ResolutionState
30	 # 通过不断 pop 过滤包含的可能性，找出最符合需求的解
31    def pop_possibility_state
32      PossibilityState.new(
33        name,
34        requirements.dup,
35        activated,
36        requirement,
37        [possibilities.pop],
38        depth + 1,
39        conflicts.dup,
40        unused_unwind_options.dup
41      ).tap do |state|
42        state.activated.tag(state)
43      end
44    end
45  end
46
47  # 仅包含一个满足需求的可能性
48  class PossibilityState < ResolutionState
49  end
50end

光看 state 定义大家可能觉得云里雾里。这里很有必要解释一下：

我们说的需求 (requirement) 到底是指什么呢？大家可以理解为在 Podfile 中声明的 pod。**之所以称为需求，是由于无法判断定义的 dependency 是否合法。**假设它合法，又是否存在符合需求限制版本的解呢 ？即是否存在对应的 PodSpec 我们不而知。因此，这些未知状态称为统一被可能性 possibility。

Tips: 了解这个概念非常重要，这也是笔者在几乎写完本文的情况下，才想明白这些变量名的意义。💔

Resolution Loop

我们先通过图来了解一下 Molinillo 的核心流程 (先忽略异常流）：

07-backtrack-state

可以看到整个流程就是不断的将 requirement 的 possibility 过滤和处理，一层层剥离转换为 DependencyState，如此循环往复。

Molinillo 的入口为 Resolution::resolve 方法，也是上图对应的实现，逻辑如下：

 1# lib/molinillo/resolution.rb
 2
 3def resolve
 4  # 1. 初始化 timer 统计耗时初始位置打点
 5  # 2. 内部会调用 push_initial_state 初始化 DependencyState 压栈
 6  # 3. 初始化 DependencyGraph 实例
 7  start_resolution
 8
 9  while state
10    break if !state.requirement && state.requirements.empty?
11    # 输出一个进度占位
12    indicate_progress
13    if state.respond_to?(:pop_possibility_state) # DependencyState
14      # 调试日志入口
15      # 如果环境变量 MOLINILLO_DEBUG 是非 nil 就输出 log
16      # 这里的调试日志有助于排查 Pod 组件的依赖问题
17      debug(depth) { "Creating possibility state for #{requirement} (#{possibilities.count} remaining)" }
18      state.pop_possibility_state.tap do |s|
19        if s
20          states.push(s)
21          activated.tag(s)
22        end
23      end
24    end
25    # 处理栈顶 Possibility State
26    process_topmost_state
27  end
28  # 遍历 Dependency Graph 
29  resolve_activated_specs
30ensure
31  end_resolution
32end
  1. 首先 #start_resolution 会初始化 timer 用于统计解析耗时，并调用 #push_initial_state 初始化 DependencyState 入栈，以及 DependencyGraph 初始化。
  2. 获取栈顶 state 检查是否存在待解析需求，接着调用 #pop_possibility_state 进行 state 转换并入栈。
  3. 调用 #process_topmost_state 处理栈顶的 possiblity state，如果当前 state 可被激活，则将该 possiblity 存入 DependencyGraph 对应顶点的 payload 中。否则判定为冲突，需要进行状态回滚。
  4. 循环直到 state 的可能性全部处理结束。
  5. 调用 #resolve_activated_specs ，遍历 DependencyGraph 以存储更新需求的可能性，解析结束。

当然，依赖处理并非这么简单，复杂的过滤和回溯逻辑都隐藏在 #process_topmost_state 中。

ResolutionState 的变化

其实从 ResolutionState 的定义能够看出，为了方便回溯和数据还原，state 是以 Struct 结构定义的。同时在每次 #pop_possibility_state 中，通过 #dup 对 diff 数据进行了复制。

这里用依赖传递的例子来展示解析后状态栈的变化。假设我们在 Podfile 中声明了 A，B，C 三个依赖，他们的关系为：A -> B -> C。

1target 'Example' do
2  pod 'C', :path => '../'
3  pod 'B', :path => '../'  
4  pod 'A', :path => '../’
5end

在 #resolve_activated_specs 方法设置断点，在解析结束时打印状态栈 @states（简化处理后）如下：

 1 [
 2   #<struct Molinillo::DependencyState name="C", requirements=[B, A], ...>, 
 3   #<struct Molinillo::PossibilityState name="C", requirements=[B, A], ...>
 4   #<struct Molinillo::DependencyState name="B", requirements=[A], ...>
 5   #<struct Molinillo::PossibilityState name="B", requirements=[A], ...>
 6   # 省略了 C、C、A、A...
 7   #<struct Molinillo::DependencyState name="B", requirements=[], ..., 
 8   #<struct Molinillo::PossibilityState name="B", requirements=[], ..., 
 9   #<struct Molinillo::DependencyState name="", requirements=[], ..., 
10]

可以看到栈内保存的 states 中 DependencyState 与 PossibilityState 是成对出现的。不过最后入栈的 DependencyState 是一个空状态，requirements 也为空，此时无法再 pop state 循环结束。

DependencyGraph

其实包括 Molinillo 在内的依赖解析工具都会在运行期间对依赖关系进行建模来构建依赖图，毕竟这是我们表达依赖关系的方式。那么 DependencyGraph (以下简称 dg ) 是如何定义：

 1module Molinillo
 2
 3  class DependencyGraph
 4    # 有向边
 5    Edge = Struct.new(:origin, :destination, :requirement)
 6    # @return [{String => Vertex}] 用字典保存顶点, key 为顶点名称(即 requirement.name)
 7    attr_reader :vertices
 8    # @return [Log] 操作日志
 9    attr_reader :log
10	 ...
11end

另外 Vertex 定义如下：

 1module Molinillo
 2  class DependencyGraph
 3    class Vertex
 4      attr_accessor :name
 5      # @return [Object] 顶点的元数据，reqiuremnt 对应的 possiblity
 6      attr_accessor :payload
 7      # @return [Array<Object>] 需要依赖该顶点可能性能的需求
 8      attr_reader :explicit_requirements
 9      # @return [Boolean] 是否为根结点
10      attr_accessor :root
11      # @return [Array<Edge>] 出度 {Edge#origin}
12      attr_accessor :outgoing_edges
13      # @return [Array<Edge>] 入度 {Edge#destination}
14      attr_accessor :incoming_edges
15      # @return [Array<Vertex>] 入度的起点
16      def predecessors
17        incoming_edges.map(&:origin)
18      end
19      # @return [Array<Vertex>] 出度的终点
20      def successors
21        outgoing_edges.map(&:destination)
22      end
23      ...
24    end
25  end
26end

熟悉图论的同学都了解，图的保存常用的方式是邻接表和邻接矩阵。Molinillo 则通过 map + list，vertext 字典与边集数组来保存。如果仅用边集数组来查询顶点本身效率并不高，好在顶点直接用了字典保存了。Molinillo 通过栈来维护解析状态，不断将解析结果 possibility 存入 dg 的 payload 中，同时记录了各个顶点的依赖关系，即 dg 的出度和入度。

06-Vertex

  • 在有向图中对于一个顶点来说，如果一条边的终点是这个顶点，这条边就是这个顶点的入度；
  • 在有向图中对于一个顶点来说，如果一条边的起点是这个顶点，这条边就是这个顶点的出度。

当成功解析的一刻，dg 图也构建完毕。

Operation Log

当解析过程出现冲突时，状态栈要回溯直接 pop 一下就完事了，而 dg 咋办 ? 它可没法 pop。

好在 Molinillo 设计了 Operation Log 机制，通过 Log 记录 dg 执行过的操作。这些操作类型包括：AddEdgeNoCircular、AddVertex、DeleteEdge、DetachVertexNamed、SetPayload、Tag。

Log 结构如下：

 1# frozen_string_literal: true
 2
 3module Molinillo
 4  class DependencyGraph
 5    class Log
 6      def initialize
 7        @current_action = @first_action = nil
 8      end
 9
10      def pop!(graph)
11        return unless action = @current_action
12        unless @current_action = action.previous
13          @first_action = nil
14        end
15        action.down(graph)
16        action
17      end
18
19      # 回撤到指定的操作节点
20      def rewind_to(graph, tag)
21        loop do
22          action = pop!(graph)
23          raise "No tag #{tag.inspect} found" unless action
24          break if action.class.action_name == :tag && action.tag == tag
25        end
26      end
27
28      private
29
30      # 插入操作节点
31      def push_action(graph, action)
32
33        action.previous = @current_action
34        @current_action.next = action if @current_action
35        @current_action = action
36        @first_action ||= action
37        action.up(graph)
38      end
39      ...
40    end
41  end
42end

标准的链表结构，Log 提供了当前指针 @current_action 和表头指针 @first_action 便于链表的遍历。接着看看 Action：

 1# frozen_string_literal: true
 2
 3module Molinillo
 4  class DependencyGraph
 5
 6    class Action
 7      # @return [Symbol] action 名称
 8      def self.action_name
 9        raise 'Abstract'
10      end
11
12      # 对图执行正向操作
13      def up(graph)
14        raise 'Abstract'
15      end
16
17      # 撤销对图的操作
18      def down(graph)
19        raise 'Abstract'
20      end
21       
22      # @return [Action,Nil] 前序节点
23      attr_accessor :previous
24      # @return [Action,Nil] 后序节点
25      attr_accessor :next
26    end
27  end
28end

Action 本身是个抽象类，Log 通过 Action 子类的 #up、#down 来完成对 dg 的操作和撤销。所提供的 Action 中除了 Tag 特殊一点，其余均是对 dg 的顶点和边的 CURD 操作。这里以 AddVertex 为例：

 1# frozen_string_literal: true
 2
 3require_relative 'action'
 4module Molinillo
 5  class DependencyGraph
 6	 # @!visibility private
 7    class AddVertex < Action # :nodoc:
 8      def self.action_name
 9        :add_vertex
10      end
11      
12      # 操作添加顶点
13      def up(graph)
14        if existing = graph.vertices[name]
15          @existing_payload = existing.payload
16          @existing_root = existing.root
17        end
18        vertex = existing || Vertex.new(name, payload)
19        graph.vertices[vertex.name] = vertex
20        vertex.payload ||= payload
21        vertex.root ||= root
22        vertex
23      end
24
25      # 删除顶点
26      def down(graph)
27        if defined?(@existing_payload)
28          vertex = graph.vertices[name]
29          vertex.payload = @existing_payload
30          vertex.root = @existing_root
31        else
32          graph.vertices.delete(name)
33        end
34      end
35
36      # @return [String] 顶点名称 (或者说依赖名称)
37      attr_reader :name
38      # @return [Object] 顶点元数据
39      attr_reader :payload
40      # @return [Boolean] 是否为根
41      attr_reader :root
42		...
43    end
44  end
45end

Action 子类均声明为 private 的，通过 Log 提供的对应方法来执行。

 1def tag(graph, tag)
 2  push_action(graph, Tag.new(tag))
 3end
 4
 5def add_vertex(graph, name, payload, root)
 6  push_action(graph, AddVertex.new(name, payload, root))
 7end
 8
 9def detach_vertex_named(graph, name)
10  push_action(graph, DetachVertexNamed.new(name))
11end
12
13def add_edge_no_circular(graph, origin, destination, requirement)
14  push_action(graph, AddEdgeNoCircular.new(origin, destination, requirement))
15end
16
17def delete_edge(graph, origin_name, destination_name, requirement)
18  push_action(graph, DeleteEdge.new(origin_name, destination_name, requirement))
19end
20
21def set_payload(graph, name, payload)
22  push_action(graph, SetPayload.new(name, payload))
23end

最后 log 声明的这些方法会由 dg 直接调用，如 #addVertext:

1module Molinillo
2  class DependencyGraph
3    def add_vertex(name, payload, root = false)
4      log.add_vertex(self, name, payload, root)
5    end
6    ...
7  end
8end

Unwind For Conflict

有了 op log 之后我们还需要一样重要的东西：哨兵节点。由 Tag 类来承载：

 1# frozen_string_literal: true
 2module Molinillo
 3  class DependencyGraph
 4    # @!visibility private     
 5    class Tag < Action
 6
 7      def up(graph)
 8      end
 9       
10      def down(graph)
11      end
12
13      attr_reader :tag
14
15      def initialize(tag)
16        @tag = tag
17      end
18    end
19  end
20end

作为哨兵节点 Tag 的 #up 与 #down 操作总是成对出现的。在 Molinillo 中有两处需要进行状态回溯，分别为可能性校验和冲突状态回撤。

0x1 可能性校验

#possibility_satisfies_requirements? 方法用于冲突产生的前后，用于判断该可能性能否同时满足多个需求：

 1def possibility_satisfies_requirements?(possibility, requirements)
 2  name = name_for(possibility)
 3
 4  activated.tag(:swap)
 5  activated.set_payload(name, possibility) if activated.vertex_named(name)
 6  satisfied = requirements.all? { |r| requirement_satisfied_by?(r, activated, possibility) }
 7  activated.rewind_to(:swap)
 8
 9  satisfied
10end

为了直观的说明参数，我们举个例子。Case 1假设 Podfile 中存在 pod A 和 B，且 A、B 分别依赖了 Alamofire 3.0 和 4.0，那么对应的参数为：

1possibility: #<Pod::Specification name="Alamofire" version="4.0.0">
2requirements: [
3	<Pod::Dependency name=Alamofire requirements=~> 3.0 source=nil external_source=nil>, 		<Pod::Dependency name=Alamofire requirements=~> 4.0 source=nil external_source=nil>
4]

现在来看方法实现：

  1. 首先 activated 就是 Podfile 解析生成的 dg 对象，这里将 symbol :swap 作为标识用于稍后的回撤；
  2. 调用 #set_payload 将顶点 Alamofire 的 payload 修改为 possibility 版本；
  3. 遍历 requirements 并调用代理的 #requirement_satisfied_by 以校验 possiblity 在 dg 中存在的可能性；
  4. 调用 #rewind_to 将顶点的修改回撤至 :swap 前的状态，最后返回检验结果。

Tips: 此处的代理是指 CocoaPods，它做为 Molinillo 的 client 实现了很多代理方法，后续会聊到。

作为候选项 possibility 当然不止一个，代理提供的查询方法 #search_for(dependency) 会返回所有符合 requiremnt 名称的依赖。在 CocoaPods 中，就是通过 Pod::Source 查询获得所有版本的 Pod::Specification，具体可以看上一篇文章：PodSpec 管理策略。

0x2 冲突状态回撤

依赖解析过程出现冲突属于正常情况，此时通过回撤也许可以避免部分冲突，找出其它可行解。Molinillo 通过定义 Conflict 来记录当前的冲突的必要信息：

 1Conflict = Struct.new(
 2  :requirement,
 3  :requirements,
 4  :existing,
 5  :possibility_set,
 6  :locked_requirement,
 7  :requirement_trees,
 8  :activated_by_name,
 9  :underlying_error
10)

重点关注 underlying_error，它记录了所拦截的指定类型错误，并用于状态回撤时的一些判断依据 (后面会解释)。这里我们先看一下定义的错误类型：

 1# frozen_string_literal: true
 2
 3module Molinillo
 4
 5  class ResolverError < StandardError; end
 6   
 7  # 错误信息："Unable to find a specification for `#{dependency}`"
 8  class NoSuchDependencyError < ResolverError ... end
 9        
10  # 错误信息："There is a circular dependency between ..."
11  class CircularDependencyError < ResolverError ... end
12        
13  # 当出现版本冲突时抛出
14  # 错误信息："Unable to satisfy the following requirements:\n\n ..."
15  class VersionConflict < ResolverError ... end
16end

除了主动拦截错误之外，possiblity 不存在时也会主动生成冲突，同时进入状态回撤处理。发生冲突后调用 #create_conflict 和 #unwind_for_conflict 两个方法分别用于生成 Conflict 对象和状态回撤。

 1def process_topmost_state
 2  if possibility
 3    attempt_to_activate
 4  else
 5    create_conflict
 6    unwind_for_conflict
 7  end
 8rescue CircularDependencyError => underlying_error
 9  create_conflict(underlying_error)
10  unwind_for_conflict
11end
12
13def attempt_to_activate
14  debug(depth) { 'Attempting to activate ' + possibility.to_s }
15  existing_vertex = activated.vertex_named(name)
16  if existing_vertex.payload
17    debug(depth) { "Found existing spec (#{existing_vertex.payload})" }
18    attempt_to_filter_existing_spec(existing_vertex)
19  else
20    latest = possibility.latest_version
21    possibility.possibilities.select! do |possibility|
22      requirement_satisfied_by?(requirement, activated, possibility)
23    end
24    if possibility.latest_version.nil?
25      # ensure there's a possibility for better error messages
26      possibility.possibilities << latest if latest
27      create_conflict
28      unwind_for_conflict
29    else
30      activate_new_spec
31    end
32  end
33end
34
35def attempt_to_filter_existing_spec(vertex)
36  filtered_set = filtered_possibility_set(vertex)
37  if !filtered_set.possibilities.empty?
38    activated.set_payload(name, filtered_set)
39    new_requirements = requirements.dup
40    push_state_for_requirements(new_requirements, false)
41  else
42    create_conflict
43    debug(depth) { "Unsatisfied by existing spec (#{vertex.payload})" }
44    unwind_for_conflict
45  end
46end

可以看到这 3 个方法中处理了 4 处冲突的情况。其中 #process_topmost_state 方法拦截了 CircularDependencyError 并将其记录在 Conflict 的 underlying_error 中，其余的都是因为 possibility 可行解不存在而主动抛出冲突。

我们简化成下面的状态图：

08-process-topmost-state

可以理解 possiblity 状态机，通过不断检查可能性，一旦出错主动生成异常。为什么要这么做 ？ 因为状态回溯的成本是很高的，一旦发生意味着我们之前检查工作可能就白费了。这也是 Molinillo 前向查询的充电，通过提早暴露问题，提前回溯。

unwind_for_conflict

了解了冲突时如何产生之后，接下来该 #unwind_for_conflict 登场了：

 1def unwind_for_conflict
 2  details_for_unwind = build_details_for_unwind
 3  unwind_options = unused_unwind_options
 4  debug(depth) { "Unwinding for conflict: #{requirement} to #{details_for_unwind.state_index / 2}" }
 5  conflicts.tap do |c|
 6    sliced_states = states.slice!((details_for_unwind.state_index + 1)..-1)
 7    raise_error_unless_state(c)
 8    activated.rewind_to(sliced_states.first || :initial_state) if sliced_states
 9    state.conflicts = c
10    state.unused_unwind_options = unwind_options
11    filter_possibilities_after_unwind(details_for_unwind)
12    index = states.size - 1
13    @parents_of.each { |_, a| a.reject! { |i| i >= index } }
14    state.unused_unwind_options.reject! { |uw| uw.state_index >= index }
15  end
16end

冲突回溯就涉及到前面说过的两个状态需要处理，分别是状态栈 @states 和 dg 内容的回溯。 @state 本身是数组实现的，其元素是各个状态的 state, 要回溯到指定的 state 则要利用 state_index，它保存在 UnwindDetails 中：

 1UnwindDetails = Struct.new(
 2  :state_index,
 3  :state_requirement,
 4  :requirement_tree,
 5  :conflicting_requirements,
 6  :requirement_trees,
 7  :requirements_unwound_to_instead
 8)
 9
10class UnwindDetails
11  include Comparable
12  ...
13end

这里解释一下 requirement_trees，这里是指以当前需求作为依赖的需求。以上面的 Case 1 为例，当前冲突的 requirement 就是 Alamofire，对应 requirement_trees 就是依赖了 Alamofire 的 Pod A 和 B：

1[
2  [
3    <Pod::Dependency name=A requirements=nil source=nil external_source=nil>,
4    <Pod::Dependency name=Alamofire requirements=~> 3.0 ...>
5  ],[
6    <Pod::Dependency name=B ...>,
7    <Pod::Dependency name=Alamofire requirements=~> 4.0 ...>
8  ]
9]

#build_details_for_unwind 主要用于生成 UnwindDetails，大致流程如下：

 1def build_details_for_unwind
 2  current_conflict = conflicts[name]
 3  binding_requirements = binding_requirements_for_conflict(current_conflict)
 4  unwind_details = unwind_options_for_requirements(binding_requirements)
 5
 6  last_detail_for_current_unwind = unwind_details.sort.last
 7  current_detail = last_detail_for_current_unwind
 8
 9  # filter & update details options
10  ...
11  current_detail
12end
  1. 以 conflict.requirement 为参数，执行 #binding_requirements_for_conflict 以查找出存在冲突的需求 binding_requirements。查询是通过代理的 #search_for(dependency) 方法；
  2. 通过 #unwind_options_for_requirements 遍历查询到的 binding_requirements 获取 requirement 对应的 state 以及该 state 在栈中的 index，用于生成 unwind_details；
  3. 对 unwind_details 排序，取 last 作为 current_detail 并进行其他相关的修改。

关于如何获取 state_index 和 unwind_details:

 1def unwind_options_for_requirements(binding_requirements)
 2  unwind_details = []
 3
 4  trees = []
 5  binding_requirements.reverse_each do |r|
 6    partial_tree = [r]
 7    trees << partial_tree
 8    unwind_details << UnwindDetails.new(-1, nil, partial_tree, binding_requirements, trees, [])
 9    # 1.1 获取 requirement 对应的 state
10    requirement_state = find_state_for(r)
11    # 1.2 确认 possibility 存在
12    if conflict_fixing_possibilities?(requirement_state, binding_requirements)
13      # 1.3 生成 detail 存入 unwind_details
14      unwind_details << UnwindDetails.new(
15        states.index(requirement_state),
16        r,
17        partial_tree,
18        binding_requirements,
19        trees,
20        []
21      )
22    end
23    
24    # 2. 沿着 requirement 依赖树的父节点获取其 state
25    parent_r = parent_of(r)
26    next if parent_r.nil?
27    partial_tree.unshift(parent_r)
28    requirement_state = find_state_for(parent_r)
29    # 重复 1.2， 1.3 步骤 ...
30 	
31    # 6. 沿着依赖树，重复上述操作
32    grandparent_r = parent_of(parent_r)
33    until grandparent_r.nil?
34      partial_tree.unshift(grandparent_r)
35      requirement_state = find_state_for(grandparent_r)
36      # 重复 1.2、1.3 步骤 ...
37      parent_r = grandparent_r
38      grandparent_r = parent_of(parent_r)
39    end
40  end
41
42  unwind_details
43end

确认 state_index 后，栈回溯反而比较简单了，直接 #slice! 即可：

1sliced_states = states.slice!((details_for_unwind.state_index + 1)..-1)

dg 回撤还是 activated.rewind_to(sliced_states.first || :initial_state) if sliced_states。回撤结束后，流程重新回到 Resolution Loop。

SpecificationProvider

最后一节简单聊聊 SpecificationProvider。为了更好的接入不同平台，同时保证 Molinillo 的通用性和灵活性，作者将依赖描述文件查询等逻辑抽象成了代理。

SpecificationProvider 作为单独的 Module 声明了接入端必须实现的 API：

 1module Molinillo
 2   module SpecificationProvider
 3
 4    def search_for(dependency)
 5      []
 6    end
 7
 8    def dependencies_for(specification)
 9      []
10    end
11    ...
12  end
13end

而 Provider 就是在 Molinillo 初始化的时候注入的：

 1require_relative 'dependency_graph'
 2
 3module Molinillo
 4
 5  class Resolver
 6    require_relative 'resolution'
 7
 8    attr_reader :specification_provider
 9    attr_reader :resolver_ui
10
11    def initialize(specification_provider, resolver_ui)
12      @specification_provider = specification_provider
13      @resolver_ui = resolver_ui
14    end
15
16    def resolve(requested, base = DependencyGraph.new)
17      Resolution.new(specification_provider,
18                     resolver_ui,
19                     requested,
20                     base).
21        resolve
22    end
23  end
24end

而在 CocoaPods 中的初始化方法则是：

 1# /lib/CocoaPods/resolver.rb
 2def resolve
 3  dependencies = @podfile_dependency_cache.target_definition_list.flat_map do |target|
 4    @podfile_dependency_cache.target_definition_dependencies(target).each do |dep|
 5      next unless target.platform
 6      @platforms_by_dependency[dep].push(target.platform)
 7    end
 8  end.uniq
 9  @platforms_by_dependency.each_value(&:uniq!)
10  @activated = Molinillo::Resolver.new(self, self).resolve(dependencies, locked_dependencies)
11  resolver_specs_by_target
12rescue Molinillo::ResolverError => e
13  handle_resolver_error(e)
14end

该方法则处于 pod install 中的 resolve dependencies 阶段：

01-pod-install

NoSuchDependencyError

另外，为了更好的处理产生的异常，同时保证核心逻辑对 provider 的无感知，Molinillo 将代理方法做了一层隔离，并且对异常做了统一拦截：

 1module Molinillo
 2  module Delegates
 3
 4    module SpecificationProvider
 5
 6      def search_for(dependency)
 7        with_no_such_dependency_error_handling do
 8          specification_provider.search_for(dependency)
 9        end
10      end
11
12      def dependencies_for(specification)
13        with_no_such_dependency_error_handling do
14          specification_provider.dependencies_for(specification)
15        end
16      end
17
18      ...
19
20      private
21
22      def with_no_such_dependency_error_handling
23        yield
24      rescue NoSuchDependencyError => error
25        if state
26          ...
27        end
28        raise
29      end
30    end
31  end
32end

总结

本篇文章从依赖解析的状态维护、状态存储、状态回溯三个维度来解构 Molinillo 的核心逻辑，它们分别对应了 ResolutionState、DependencyGraph、UnwindDetail 这三种数据结构。一开始写这篇内容时，头脑中对于这些概念是未知的，因为一开始就直接看了作者对 Molinillo 的架构阐述更是完全找不到思绪，好在我有 VSCode ！！！最终依据不同 Case 下的数据呈现，一点点的进行源码调试，大致摸清的 Molinillo 的状态是如何变化转移的。最后一点，英文和数据结构还是很重要的，possiblity 你理解了吗 ？

知识点问题梳理

这里罗列了五个问题用来考察你是否已经掌握了这篇文章，如果没有建议你加入收藏再次阅读：

  1. 说说 Resolution 栈中的 state 是如何转移的 ？
  2. DependencyGraph 的数据通过什么方式进行回撤的 ？
  3. #process_topmost_state 处理了几种 conflict 情况 ？
  4. UnwindDetail 的 state_index 是如何获取的 ？
  5. 作者如何利用 SpecificationProvider 来解偶的 ？