调研RFC 2094中DFS传播算法在rustc中的实现历史

[Jackguo123]

调研目标

需要调研RFC 2094中描述的DFS传播算法是否在rustc的历史版本中有过真正的实现，而不仅仅是原型或设计阶段。

具体问题

1. RFC 2094的DFS算法：RFC中描述了使用深度优先搜索来传播outlives关系，保持位置敏感性
2. 当前实现：目前rustc中使用的是基于SCC的连通图算法，位置信息在传播阶段基本被忽略
3. 历史实现：是否存在过真正实现RFC 2094精神的版本？

需要查找的信息

代码历史

• 查找rustc历史commit中是否有DFS传播的实现
• 确认NLL最初实现时使用的算法
• 查看从DFS到SCC算法的演进过程（如果存在）

关键文件历史

重点关注以下文件的历史版本：

• compiler/rustc_borrowck/src/region_infer/mod.rs
• compiler/rustc_borrowck/src/constraints/
• NLL相关的早期实现文件

Git历史搜索关键词

• "DFS propagation"
• "depth-first"
• "RFC 2094"
• "region propagation"
• "outlives constraint propagation"

时间范围

重点关注：

• 2017-2018年：RFC 2094提出和初始实现期间
• 2018-2019年：NLL稳定化期间
• 可能存在的性能优化时期

预期发现

可能的结果：

1. 从未真正实现：直接从设计跳到了SCC优化版本
2. 早期实现后被替换：初期实现了DFS，后来为了性能改为SCC
3. 部分实现：某些组件使用了DFS思想，但整体架构不同

研究价值

这个调研有助于理解：

• rustc开发中算法选择的权衡考虑
• 为什么需要Polonius这样的重新设计
• 技术债务和性能优化的历史选择