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

[Jackguo123]

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.

[bjorn3]

Location sensitivity has been deferred to Polonius, which is currently being worked on. Unconditionally implementing location sensitivity was found to be way too slow.

[Jackguo123]

Location sensitivity has been deferred to Polonius, which is currently being worked on. Unconditionally implementing location sensitivity was found to be way too slow.

Thanks for your reply! Now I understand that location sensitivity has been deferred to Polonius, and that unconditionally implementing location sensitivity was found to be too slow.

However, I still want to confirm whether "unconditionally implementing location sensitivity" refers to the depth-first search (DFS) starting from P, as shown in nll/src/infer.rs#L71-L113? I know that Polonius (Datalog) has performance issues, and I'm expecting that the current polonius-next implementation has both location sensitivity and much better performance. Thanks again!