Auto merge of #54199 - nikomatsakis:predicate_may_hold-failure, r=eddyb

overlook overflows in rustdoc trait solving

Context:

The new rustdoc "auto trait" feature walks across impls and tries to run trait solving on them with a lot of unconstrained variables. This is prone to overflows. These overflows used to cause an ICE because of a caching bug (fixed in this PR). But even once that is fixed, it means that rustdoc causes an overflow rather than generating docs.

This PR therefore adds a new helper that propagates the overflow error out. This requires rustdoc to then decide what to do when it encounters such an overflow: technically, an overflow represents neither "yes" nor "no", but rather a failure to make a decision. I've decided to opt on the side of treating this as "yes, implemented", since rustdoc already takes an optimistic view. This may prove to include too many items, but I *suspect* not.

We could probably reduce the rate of overflows by unifying more of the parameters from the impl -- right now we only seem to consider the self type. Moreover, in the future, as we transition to Chalk, overflow errors are expected to just "go away" (in some cases, though, queries might return an ambiguous result).

Fixes #52873

cc @QuietMisdreavus -- this is the stuff we were talking about earlier
cc @GuillaumeGomez -- this supersedes #53687

5 files changed, 214 insertions, 15 deletions

diff --git a/src/librustc/traits/query/evaluate_obligation.rs b/src/librustc/traits/query/evaluate_obligation.rs
index 6bd92678362..f573b1ef45e 100644
--- a/src/librustc/traits/query/evaluate_obligation.rs
+++ b/src/librustc/traits/query/evaluate_obligation.rs
@@ -20,7 +20,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
         &self,
         obligation: &PredicateObligation<'tcx>,
     ) -> bool {
-        self.evaluate_obligation(obligation).may_apply()
+        self.evaluate_obligation_no_overflow(obligation).may_apply()
     }
 
     /// Evaluates whether the predicate can be satisfied in the given
@@ -30,28 +30,44 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
         &self,
         obligation: &PredicateObligation<'tcx>,
     ) -> bool {
-        self.evaluate_obligation(obligation) == EvaluationResult::EvaluatedToOk
+        self.evaluate_obligation_no_overflow(obligation) == EvaluationResult::EvaluatedToOk
     }
 
-    // Helper function that canonicalizes and runs the query, as well as handles
-    // overflow.
-    fn evaluate_obligation(
+    /// Evaluate a given predicate, capturing overflow and propagating it back.
+    pub fn evaluate_obligation(
         &self,
         obligation: &PredicateObligation<'tcx>,
-    ) -> EvaluationResult {
+    ) -> Result<EvaluationResult, OverflowError> {
         let mut _orig_values = SmallVec::new();
         let c_pred = self.canonicalize_query(&obligation.param_env.and(obligation.predicate),
                                              &mut _orig_values);
         // Run canonical query. If overflow occurs, rerun from scratch but this time
         // in standard trait query mode so that overflow is handled appropriately
         // within `SelectionContext`.
-        match self.tcx.global_tcx().evaluate_obligation(c_pred) {
+        self.tcx.global_tcx().evaluate_obligation(c_pred)
+    }
+
+    // Helper function that canonicalizes and runs the query. If an
+    // overflow results, we re-run it in the local context so we can
+    // report a nice error.
+    fn evaluate_obligation_no_overflow(
+        &self,
+        obligation: &PredicateObligation<'tcx>,
+    ) -> EvaluationResult {
+        match self.evaluate_obligation(obligation) {
             Ok(result) => result,
             Err(OverflowError) => {
                 let mut selcx =
                     SelectionContext::with_query_mode(&self, TraitQueryMode::Standard);
                 selcx.evaluate_obligation_recursively(obligation)
-                     .expect("Overflow should be caught earlier in standard query mode")
+                    .unwrap_or_else(|r| {
+                        span_bug!(
+                            obligation.cause.span,
+                            "Overflow should be caught earlier in standard query mode: {:?}, {:?}",
+                            obligation,
+                            r,
+                        )
+                    })
             }
         }
     }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 232ef108537..706d038812e 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -1376,7 +1376,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         let tcx = self.tcx();
         let trait_ref = cache_fresh_trait_pred.skip_binder().trait_ref;
         if self.can_use_global_caches(param_env) {
-            if let Some(trait_ref) = tcx.lift_to_global(&trait_ref) {
+            if let Err(Overflow) = candidate {
+                // Don't cache overflow globally; we only produce this
+                // in certain modes.
+            } else if let Some(trait_ref) = tcx.lift_to_global(&trait_ref) {
                 if let Some(candidate) = tcx.lift_to_global(&candidate) {
                     debug!(
                         "insert_candidate_cache(trait_ref={:?}, candidate={:?}) global",
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index 10e930d1c92..6b0b1c35a7e 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -175,7 +175,7 @@ impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
             super::ConstEvalFailure(ref err) => tcx.lift(&**err).map(|err| super::ConstEvalFailure(
                 err.into(),
             )),
-            super::Overflow => bug!(), // FIXME: ape ConstEvalFailure?
+            super::Overflow => Some(super::Overflow),
         }
     }
 }
diff --git a/src/librustdoc/clean/blanket_impl.rs b/src/librustdoc/clean/blanket_impl.rs
index e7e371cd567..3d591a702aa 100644
--- a/src/librustdoc/clean/blanket_impl.rs
+++ b/src/librustdoc/clean/blanket_impl.rs
@@ -103,11 +103,20 @@ impl<'a, 'tcx, 'rcx, 'cstore> BlanketImplFinder <'a, 'tcx, 'rcx, 'cstore> {
                         // FIXME(eddyb) ignoring `obligations` might cause false positives.
                         drop(obligations);
 
-                        let may_apply = infcx.predicate_may_hold(&traits::Obligation::new(
-                            cause.clone(),
-                            param_env,
-                            trait_ref.to_predicate(),
-                        ));
+                        debug!(
+                            "invoking predicate_may_hold: {:?}",
+                            trait_ref,
+                        );
+                        let may_apply = match infcx.evaluate_obligation(
+                            &traits::Obligation::new(
+                                cause.clone(),
+                                param_env,
+                                trait_ref.to_predicate(),
+                            ),
+                        ) {
+                            Ok(eval_result) => eval_result.may_apply(),
+                            Err(traits::OverflowError) => true, // overflow doesn't mean yes *or* no
+                        };
                         if !may_apply {
                             return
                         }
diff --git a/src/test/rustdoc/issue-52873.rs b/src/test/rustdoc/issue-52873.rs
new file mode 100644
index 00000000000..9138dd50def
--- /dev/null
+++ b/src/test/rustdoc/issue-52873.rs
@@ -0,0 +1,171 @@
+// Regression test for #52873. We used to ICE due to unexpected
+// overflows when checking for "blanket impl inclusion".
+
+use std::marker::PhantomData;
+use std::cmp::Ordering;
+use std::ops::{Add, Mul};
+
+pub type True = B1;
+pub type False = B0;
+pub type U0 = UTerm;
+pub type U1 = UInt<UTerm, B1>;
+
+pub trait NonZero {}
+
+pub trait Bit {
+}
+
+pub trait Unsigned {
+}
+
+#[derive(Eq, PartialEq, Ord, PartialOrd, Clone, Copy, Hash, Debug, Default)]
+pub struct B0;
+
+impl B0 {
+    #[inline]
+    pub fn new() -> B0 {
+        B0
+    }
+}
+
+#[derive(Eq, PartialEq, Ord, PartialOrd, Clone, Copy, Hash, Debug, Default)]
+pub struct B1;
+
+impl B1 {
+    #[inline]
+    pub fn new() -> B1 {
+        B1
+    }
+}
+
+impl Bit for B0 {
+}
+
+impl Bit for B1 {
+}
+
+impl NonZero for B1 {}
+
+pub trait PrivatePow<Y, N> {
+    type Output;
+}
+pub type PrivatePowOut<A, Y, N> = <A as PrivatePow<Y, N>>::Output;
+
+pub type Add1<A> = <A as Add<::B1>>::Output;
+pub type Prod<A, B> = <A as Mul<B>>::Output;
+pub type Square<A> = <A as Mul>::Output;
+pub type Sum<A, B> = <A as Add<B>>::Output;
+
+#[derive(Eq, PartialEq, Ord, PartialOrd, Clone, Copy, Hash, Debug, Default)]
+pub struct UTerm;
+
+impl UTerm {
+    #[inline]
+    pub fn new() -> UTerm {
+        UTerm
+    }
+}
+
+impl Unsigned for UTerm {
+}
+
+#[derive(Eq, PartialEq, Ord, PartialOrd, Clone, Copy, Hash, Debug, Default)]
+pub struct UInt<U, B> {
+    _marker: PhantomData<(U, B)>,
+}
+
+impl<U: Unsigned, B: Bit> UInt<U, B> {
+    #[inline]
+    pub fn new() -> UInt<U, B> {
+        UInt {
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<U: Unsigned, B: Bit> Unsigned for UInt<U, B> {
+}
+
+impl<U: Unsigned, B: Bit> NonZero for UInt<U, B> {}
+
+impl Add<B0> for UTerm {
+    type Output = UTerm;
+    fn add(self, _: B0) -> Self::Output {
+        UTerm
+    }
+}
+
+impl<U: Unsigned, B: Bit> Add<B0> for UInt<U, B> {
+    type Output = UInt<U, B>;
+    fn add(self, _: B0) -> Self::Output {
+        UInt::new()
+    }
+}
+
+impl<U: Unsigned> Add<U> for UTerm {
+    type Output = U;
+    fn add(self, _: U) -> Self::Output {
+        unsafe { ::std::mem::uninitialized() }
+    }
+}
+
+impl<U: Unsigned, B: Bit> Mul<B0> for UInt<U, B> {
+    type Output = UTerm;
+    fn mul(self, _: B0) -> Self::Output {
+        UTerm
+    }
+}
+
+impl<U: Unsigned, B: Bit> Mul<B1> for UInt<U, B> {
+    type Output = UInt<U, B>;
+    fn mul(self, _: B1) -> Self::Output {
+        UInt::new()
+    }
+}
+
+impl<U: Unsigned> Mul<U> for UTerm {
+    type Output = UTerm;
+    fn mul(self, _: U) -> Self::Output {
+        UTerm
+    }
+}
+
+impl<Ul: Unsigned, B: Bit, Ur: Unsigned> Mul<UInt<Ur, B>> for UInt<Ul, B0>
+where
+    Ul: Mul<UInt<Ur, B>>,
+{
+    type Output = UInt<Prod<Ul, UInt<Ur, B>>, B0>;
+    fn mul(self, _: UInt<Ur, B>) -> Self::Output {
+        unsafe { ::std::mem::uninitialized() }
+    }
+}
+
+pub trait Pow<Exp> {
+    type Output;
+}
+
+impl<X: Unsigned, N: Unsigned> Pow<N> for X
+where
+    X: PrivatePow<U1, N>,
+{
+    type Output = PrivatePowOut<X, U1, N>;
+}
+
+impl<Y: Unsigned, X: Unsigned> PrivatePow<Y, U0> for X {
+    type Output = Y;
+}
+
+impl<Y: Unsigned, X: Unsigned> PrivatePow<Y, U1> for X
+where
+    X: Mul<Y>,
+{
+    type Output = Prod<X, Y>;
+}
+
+impl<Y: Unsigned, U: Unsigned, B: Bit, X: Unsigned> PrivatePow<Y, UInt<UInt<U, B>, B0>> for X
+where
+    X: Mul,
+    Square<X>: PrivatePow<Y, UInt<U, B>>,
+{
+    type Output = PrivatePowOut<Square<X>, Y, UInt<U, B>>;
+}