Fix order of normalization and recursion in const folding.

Fixes #126831.

Without this patch, type normalization is not always idempotent, which
leads to all sorts of bugs in places that assume that normalizing a
normalized type does nothing.

2 files changed, 29 insertions, 4 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
index 247b6e4823c..cb96db5f7a2 100644
--- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
@@ -333,14 +333,14 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx>
             return Ok(constant);
         }
 
-        let constant = constant.try_super_fold_with(self)?;
-        debug!(?constant, ?self.param_env);
-        Ok(crate::traits::with_replaced_escaping_bound_vars(
+        let constant = crate::traits::with_replaced_escaping_bound_vars(
             self.infcx,
             &mut self.universes,
             constant,
             |constant| constant.normalize(self.infcx.tcx, self.param_env),
-        ))
+        );
+        debug!(?constant, ?self.param_env);
+        constant.try_super_fold_with(self)
     }
 
     #[inline]
diff --git a/tests/ui/const-generics/const-ty-is-normalized.rs b/tests/ui/const-generics/const-ty-is-normalized.rs
new file mode 100644
index 00000000000..784145f735e
--- /dev/null
+++ b/tests/ui/const-generics/const-ty-is-normalized.rs
@@ -0,0 +1,25 @@
+//@ compile-flags: -Cdebuginfo=2 --crate-type=lib
+//@ build-pass
+#![feature(adt_const_params)]
+
+const N_ISLANDS: usize = 4;
+
+pub type Matrix = [[usize; N_ISLANDS]; N_ISLANDS];
+
+const EMPTY_MATRIX: Matrix = [[0; N_ISLANDS]; N_ISLANDS];
+
+const fn to_matrix() -> Matrix {
+    EMPTY_MATRIX
+}
+
+const BRIDGE_MATRIX: [[usize; N_ISLANDS]; N_ISLANDS] = to_matrix();
+
+pub struct Walk<const CURRENT: usize, const REMAINING: Matrix> {
+    _p: (),
+}
+
+impl Walk<0, BRIDGE_MATRIX> {
+    pub const fn new() -> Self {
+        Self { _p: () }
+    }
+}