cargo gets stuck compiling nlist crate

[souragc]

cargo fails to compile the latest version of nlist. This happens because rustc gets stuck in rustc_trait_selection::traits::project::normalize_projection_term.

This only happens at opt-level 2 and only when inline-mir is enabled. It successfully compiles with the following command:

cargo +nightly rustc --release -- -Z inline-mir=no

I used perf to see where the compiler is getting stuck. The following is the relevant part of the perf report:

Samples: 120K of event 'cycles', Event count (approx.): 111444101575
  Children      Self  Command  Shared Object                        Symbol
+   79.78%    79.71%  rustc    librustc_driver-24ace9b62cb3ceb9.so  [.] rustc_trait_selection::traits::project::normalize_projection_term
+   42.68%     0.00%  rustc    [unknown]                            [.] 0000000000000000
+   20.22%    20.20%  rustc    librustc_driver-24ace9b62cb3ceb9.so  [.] <rustc_trait_selection::traits::normalize::AssocTypeNormalizer as rustc_type_ir::fold::TypeFolder<rustc_middle::ty::context::TyCtxt>>::fold_ty
+    5.93%     0.00%  rustc    [unknown]                            [.] 0x0000000e00000000
+    5.59%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef69da0
+    5.49%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef72010
+    5.37%     0.00%  rustc    [unknown]                            [k] 0x0000001f00000021
+    2.87%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef71fd0
+    2.77%     0.00%  rustc    [unknown]                            [.] 0x0000001c00000000
+    2.67%     0.00%  rustc    [unknown]                            [.] 0x0000000000000001
+    1.45%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef6bc20
+    1.40%     0.00%  rustc    [unknown]                            [.] 0x00007f4990d71158
+    1.37%     0.00%  rustc    [unknown]                            [.] 0x00007f4990658190
+    1.28%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef62600
+    0.75%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef6a830
+    0.70%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef61210
+    0.67%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef6d050
+    0.66%     0.00%  rustc    [unknown]                            [.] 0x0000000100000003
     0.39%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef73ca0
     0.33%     0.00%  rustc    [unknown]                            [.] 0x000d2829ffffff01
     0.32%     0.00%  rustc    [unknown]                            [.] 0x00007f498ef69440

[bjorn3]

Is this a regression from stable to nightly? Can you bisect this using cargo-bisect-rustc?

[souragc]

I was unable to find the exact version where this started happening. cargo-bisect went quite far back and then started failing due to Rust version issues. I tested this on the stable release, and the hang exists on stable as well.

From that crate, the file that causes the issue is flatten.
I tried making a minimal file but was only able to get it to the following, which still depends on other files:

use super::{NList, NList2D};
use crate::peano::{self, PeanoInt, Zero};
impl<T, L: PeanoInt, L2: PeanoInt> NList<NList<T, L2>, L> {
    pub fn flatten(self) -> NList<T, peano::Mul<L, L2>> {
        enum FlattenState {
            Iterating,
        }
        impl FlattenState {
            const NEW: Self = FlattenState::Iterating;
        }
        fn inner<T, LSub, LOuter, LInner, LRet>(
            _sub: NList<T, LSub>,
            outer: NList2D<T, LOuter, LInner>,
        ) -> NList<T, LRet>
        where
            LSub: PeanoInt,
            LOuter: PeanoInt,
            LInner: PeanoInt,
            LRet: PeanoInt,
        {
            match FlattenState::NEW {
                FlattenState::Iterating {} => {
                    let next_sub: Option<
                        NList<
                            T,
                            <LSub as PeanoInt>::IfZeroPI<
                                <LOuter as PeanoInt>::IfZeroPI<Zero, LInner>,
                                <LSub as PeanoInt>::SubOneSat,
                            >,
                        >,
                    > = None;
                    inner(
                        next_sub.unwrap(),
                        NList::<NList<T, LInner>, peano::Zero>::nil(),
                    )
                }
            }
        }
        inner(NList::nil(), self)
    }
}

From what I can tell, if the variable next_sub's type is changed to something simpler. It resolves the hang.