[译] PubGrub: 下一代版本解决方案

原文

如果你在5个月前关注我的工作情况,你会发现我正在阅读关于约束解决问题的前沿学术研究.3个月前我把这些知识应用到代码里,起草并调整了一种新算法,把这项研究和现实工具结合起来.1个月前,我添加了最后几个功能并把它发布出来.

今天, PubGrub 横空出世: 一个使用听起来像单元传播,逻辑方案,冲突驱动学习等术语组成的运行更快,比其他版本解决方案错误更少的新版本解决算法.现在已经整合进pub 包管理器 和 Dart 2.0.0-dev.44.0 发布,我希望这个算法有一天能造福所有的编程语言.

首先,版本解决是什么意思

包管理器是现代编程语言的一个重要组成部分.它是一个可以获取应用程序依赖,依赖的依赖,直到所有的依赖都满足的工具.任何包管理器的核心都是它的版本解决算法,即如何确保安装每个包的版本以满足所有的依赖需求.

不幸的是,新建一个好的版本解决算法是真的难啊.对于非算法研究者来说,是否存在一个有效的算法是计算机科学界的主要未解之谜.

假设你的 app 依赖 menu 包的最新版本 1.5.0, 依赖 dropdown >= 2.0.0. 某些情况下 dropdown 的最新版本 2.3.0 是不能被选择的(假设它依赖的 icons 包 >= 2.0.0, 而你的 app 依赖 icons < 2.0.0).那么这个算法可能会尝试一下 dropdown 2.2.0 这个可能最佳的版本.同样的问题可能发生在 dropdown 2.1.0 和 2.0.0 之间.

下一步是尝试 menu 1.4.0 看它是否满足要求. solver 会再次遍历 dropdown 的所有版本看它们是否能正常运行,但答案是否定的.同样依次尝试 menu 1.3.0, 1.2.0 和 1.1.0. 最终 solver 锁定了 menu 1.1.0 和 dropdown 1.8.0 匹配.也就是这个版本组合兼容 app.回头这个过程出现了很多次遍历: menu 遍历中的一个版本 x dropdown 遍历中的一个版本.如果版本多的话,可能遍历更多

现在暂时可以说:”我们已经解决了无法使用 dropdown >= 2.0.0 的问题,所以不需要再次检查此版本了”.但问题可没这么简单.任何包的某个版本都可能会依赖于其他包,也就是说只要选择了一个包的不同版本,那么就得考虑下所有其他包的依赖问题.这就是包依赖索索时间呈指数级增长的秘诀.

那么 PubGrub 做了什么

安全带系好,接下来是硬核学习时间!我们将从几个定义开始: term 是PubGrub 工作的最基本单元,即某个包必要或禁止的版本范围.例如 menu >= 1.1.0 就是一个 term, not dropdown >= 2.0.0 也是.satisfied（符合）即选择的包版本符合 term. 如果选择了 menu 的 1.2.0 那么是符合 menu >= 1.1.0, 而选择的 dropdown 1.8.0 (或者没有选择 dropdown 的版本)也是满足 not dropdown >= 2.0.0的.

我们使用 incompatibilities 来定义一组不符合一次性要求的 term,也就是说,如果一组包一次就满足所有的 term,那么我们就知道它不是有效解决方案的一部分.我们使用 incompatibilities 来表示(尤其是)包之间的依赖关系.例如 incompatibilities 的{menu >= 1.1.0 not dropdown >= 2.2.0} 即如果选择了 menu >= 1.1.0 的某个版本就是无效的,同时 dropdown 的版本也不是 >= 2.0.0 .换言之,menu >= 1.1.0 依赖于 dropdown >= 2.0.0.

无论外部上下文如何,incompatibilities 的 term 都是不兼容的,即 PubGrub 可以利用此来避免一遍又一遍的重复工作.诀窍是弄清楚如何生成全部正确且可能有用的 incompatibilities.像上面的例子中很容易生成代表包依赖的 incompatibilities,但是同时我们也希望能从已存在的 term 中生成新的 incompatibilities.如果我们第一次遇到 dropdown 时能从 {dropdown >= 2.0.0}（即不应选择 dropdown >= 2.0.0 的版本） incompatibilities 中生成 incompatibilities,那么就可以跳过许多冗余的工作.

这就是”冲突驱动的从句学习”中的从句学习.在我们开始之前,先来看下”冲突”的部分,它来自运行中的 PubGrub 的核心循环.

核心循环

大多数情况下, PubGrub 会在两个阶段交替执行,同时生成在包版本集中使用的包版本暂定集.

第一个阶段是”单元传递”,由一组选定的包版本和一组 incompatibilities 组合,从我们选定的包版本中找到 terms 为 true 的集合.例如,如果已经选择了 menu 1.4.0,可以根据{menu >= 1.1.0, not dropdown >= 2.0.0}看 dropdown 是不是 >=2.0.0.（如果不是的话那么所有的 terms 就满足了,这就冲突了）

生成的 terms 同样也会反馈到单元传递阶段.一旦我们我们生成 dropdown >= 2.0.0,那么就可根据 incompatibility {dropdown >= 2.0.0, not icons >= 2.0.0} 推断出 icons >= 2.0.0.此推断会继续直到没有新的生成.这时 PubGrub 就进入了第二阶段.

第二阶段是决策生成,发生在不再有单元传递,但是依赖问题还未解决.此时选择某些包的某些版本添加到包版本列表里.只要满足了上面推断出的所有 terms 的版本就是可以正常运行的版本,但通常情况下,包管理器希望选择某些包的最近最新版本(启发式选择,pub 优先考虑总版本最小的包)

这里也是 PubGrub 添加 incompatibilities 来表示新包的依赖的地方.当解析到包时才惰性加载而不是在开始的时候对所有包的所有依赖统一添加是很重要的,因为我们不能提前知道哪些包最终会被使用到,哪些版本会是相关的.

如果一切顺利,核心循环就会找到满足所有包依赖的包版本集,那么用户就可以开始运行自己的代码了.但是我们并不总是生活在一个一切都顺利的世界,这也是为什么会有冲突解决部分的原因.

冲突解决

有时在单元传递阶段,PubGrub 会根据某个 incompatibilities 生成一个满足所有 terms 的 term.例如,当要根据 icon >= 2.0.0 和根目录包自己的版本匹配的 {root any, not icons < 2.0.0}(根包依赖于 icons) 生成新 term 时.这就产生了冲突,那么就会触发第三个阶段去解决.

在当代版本解决方案中,冲突的解决方案也就是跳回到可能导致冲突的版本之前选择不同的版本来尝试.PubGrub 也是这样做的,但是它会找到冲突的根源,然后将其标记为不兼容.这个不兼容将会在单元传递阶段中帮助避免不断的遇到相同的冲突.

通过不断的组合生成的已知逻辑规则和 incompatibilities 来生成冲突的根源.这个规则是如果 “P or Q” 和 “R or not Q” 都为 true,那么 “P or R” 也为 true.对于 incompatibilities 来说, 根据已知的 {S,T} 和 {U, not T} 可以推导出 {U, S}.

我们先把触发冲突的 {root any, not icons < 2.0.0} incompatibility 和已经推导出的 term (icons >= 2.0.0, 由 {dropdown >= 2.0.0, not icons >= 2.0.0}推导出.)组合在一起.推导出 {root any, dropdown >= 2.0.0}, 即 root 包和任何 dropdown >= 2.0.0 都是不兼容的.

然后继续把它和最近推导出的符合的 term (即 dropdown >= 2.0.0 是由 {menu >= 1.0.0, not dropdown >= 2.0.0} 推导出.)组合.这个组合推导出 {root any, menu >= 1.1.0}.因为这个符合的 term 是在决策生成阶段产生的而不是推导阶段,那么我们可以认为这就是根源,跳回到我们选择 menu 1.4.0 生成这个决策之前,然后回到单元传递阶段.

考虑到这个不兼容,单元传递可以不需要再查看 dropdown 的不兼容版本,而推导出 not menu >= 1.1.0, 然后决策生成选择 menu 1.0.0. 这就是 PubGrub 的核心.

如果失败了怎么办?

有效的找到正确的解决方案固然好,但是强大如 PubGrub 也也需要且能够向用户解释为什么无法找到符合另一个依赖的包版本集.版本解决失败的原因可能会很复杂,但是无论多么混乱, PubGrub 都能生成一个清晰的解释标明哪块出错了.

回到我们的例子: 你试着添加 intl >= 5.0.0 到 app 中,但是 dropdown < 2.0.0 依赖的确是 intl < 4.0.0.呃,这意味即使回退到 dropdown 1.8.0 也无法正常运行.

现代版本解决方案只会报告这是一个 intl 引起的错误,而你的 app 需要解决的真正问题是升级它的依赖 icons.下面是 PubGrub 的提示:

Because dropdown >=2.0.0 depends on icons >=2.0.0 and root depends
  on icons <2.0.0, dropdown >=2.0.0 is forbidden.
And because menu >=1.1.0 depends on dropdown >=2.0.0, menu >=1.1.0
  is forbidden.
And because menu <1.1.0 depends on dropdown >=1.0.0 <2.0.0 which
  depends on intl <4.0.0, every version of menu requires intl
  <4.0.0.
So, because root depends on both menu >=1.0.0 and intl >=5.0.0,
  version solving failed.

这就很清楚的指出为什么不能选择 dropdown 的最近版本,同样的选择更古老的版本也无法解决问题的原因.根据这个输出,用户可以找到要么支持最新的 icons 版本或更古老的 intl 版本才能解决这个问题.

这个详尽的错误输出是因为 PubGrub 的冲突解决能力才支持的.每次使用冲突解决去组合两个 incompatibilities,都会向新 incompatibilities 添加指向其上一级的指针.如果已经到了无法再继续向上溯源的 incompatibility (如 {root any}) 时,那么就可以使用这些父指针来组成一个 incompatibilities 有向无环图,代表 root 包的依赖是无法满足的.

对于这个例子所示的上图仅仅是一条直线.越复杂的错误会生成更复杂的图.而且可能会有分支,有时甚至多个分支是由同一个 incompatibilities 推导出的.

为了更友好的输出,PubGrub 使用深度优先遍历这个图,然后把它转为白话.因为这个转换是为了使所有的内容都可被人读懂,它涉及到了很多模糊的启发方式,例如巧妙的组合不兼容的描述,将看起来不太明显的步骤折叠在一起,以及在纯行无法写下时添加行号.

我要使用 PubGrub！

到目前为止,PubGrub 仅作为 Dart 的包管理器实现.但它是作为一个通用的纯算法设计的,可以用在其他地方去解决相同的问题.所以,在你最喜欢的包管理器的 Github 仓库提个 issue,(非常有礼貌的)请求支持 PubGrub 吧.

这个算法一个好处就是灵活.到这里我已经写了很多关于版本解决的基础知识,而 PubGrub 是可以处理包之间的任何关系(这些关系可以表述为包范围之间的逻辑关系).Pub 支持如锁定版本,强制升级，SDK 版本限制,和依赖覆盖等特性.通过微调每个包的 incompatibilities 很容易自定义特殊需求.

如果你正在为包管理器方案提供智力支持,而且对 PubGrub 有点兴趣,那么我推荐你阅读完整文档.那里深入介绍了本篇未涉及到的算法详情.如果有任何问题,都可以提 issue,我会及时更新这篇文档.当然也可以通过 Twitter 和 email 联系我.

鸣谢

欢迎查看原文,开源万岁.