Investigation: Did RFC 2094-NLL's DFS propagation for outlives in region infer algorithm ever get implemented in rustc?

Investigation Goal

We need to investigate whether the DFS propagation algorithm described in RFC 2094 was ever truly implemented in rustc's historical versions, rather than just being a prototype or design-stage concept.

Background

RFC 2094 introduced Non-Lexical Lifetimes (NLL) and described using depth-first search to propagate outlives relationships while maintaining location sensitivity. However, the current rustc implementation uses an SCC-based connected graph algorithm where location information is largely ignored during the propagation phase.

Specific Questions

1. RFC 2094 DFS Algorithm: The RFC described using depth-first search to propagate outlives relationships with location sensitivity
2. Current Implementation: rustc currently uses SCC-based connected graph algorithm, with location information mostly ignored during propagation
3. Historical Implementation: Was there ever a version that truly implemented the RFC 2094 approach?

Investigation Areas

Code History

• Search rustc git history for DFS propagation implementations
• Identify the algorithm used in NLL's initial implementation
• Track the evolution from DFS to SCC algorithm (if it exists)

Key Files to Examine

Focus on historical versions of:

• compiler/rustc_borrowck/src/region_infer/mod.rs
• compiler/rustc_borrowck/src/constraints/
• Early NLL implementation files

Git History Search Keywords

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

Timeline Focus

Key periods to examine:

• 2017-2018: RFC 2094 proposal and initial implementation period
• 2018-2019: NLL stabilization period
• Performance optimization phases

Expected Findings

Possible outcomes:

1. Never Fully Implemented: Direct jump from design to SCC-optimized version
2. Early Implementation Replaced: Initial DFS implementation later replaced with SCC for performance
3. Partial Implementation: Some components used DFS ideas but overall architecture differed

Technical Context

Current evidence suggests that the constraint propagation ignores location information:

fn compute_value_for_scc(&mut self, scc_a: ConstraintSccIndex) {
    // Only uses sup -> sub relationships, locations seem ignored
    for &scc_b in self.constraint_sccs.successors(scc_a) {
        self.scc_values.add_region(scc_a, scc_b);  // Merges all values
    }
}

While RFC 2094 described more location-sensitive propagation that would preserve constraint locations during the propagation process.

Research Value

This investigation will help us understand:

• Algorithm choice trade-offs in rustc development
• Why Polonius redesign became necessary
• Historical technical debt and performance optimization decisions
• The relationship between theoretical design (RFC) and practical implementation

Related Work

This investigation relates to current Polonius development, which reintroduces location sensitivity through localized constraints, potentially addressing limitations introduced by the SCC-based approach.

Start with git history for compiler/rustc_borrowck/src/region_infer/mod.rs, compiler/rustc_borrowck/src/constraints/, and early NLL files. Search for the listed DFS, RFC 2094, region propagation, and location-sensitive propagation terms across the 2017–2019 history. Done means documenting whether rustc used the RFC's DFS algorithm, replaced it with SCC propagation, or only implemented parts of it.