Auto merge of #30533 - nikomatsakis:fulfillment-tree, r=aturon

This PR introduces an `ObligationForest` data structure that the fulfillment context can use to track what's going on, instead of the current flat vector. This enables a number of improvements:

1. transactional support, at least for pushing new obligations
2. remove the "errors will be reported" hack -- instead, we only add types to the global cache once their entire subtree has been proven safe. Before, we never knew when this point was reached because we didn't track the subtree.
   - this in turn allows us to limit coinductive reasoning to structural traits, which sidesteps #29859
3. keeping the backtrace should allow for an improved error message, where we give the user full context
    - we can also remove chained obligation causes

This PR is not 100% complete. In particular:

- [x] Currently, types that embed themselves like `struct Foo { f: Foo }` give an overflow when evaluating whether `Foo: Sized`. This is not a very user-friendly error message, and this is a common beginner error. I plan to special-case this scenario, I think.
- [x] I should do some perf. measurements. (Update: 2% regression.)
- [x] More tests targeting #29859
- [ ] The transactional support is not fully integrated, though that should be easy enough.
- [ ] The error messages are not taking advantage of the backtrace.

I'd certainly like to do 1 through 3 before landing, but 4 and 5 could come as separate PRs.

r? @aturon // good way to learn more about this part of the trait system
f? @arielb1 // already knows this part of the trait system :)

1 files changed, 31 insertions, 0 deletions

diff --git a/src/test/compile-fail/traits-inductive-overflow-two-traits.rs b/src/test/compile-fail/traits-inductive-overflow-two-traits.rs
new file mode 100644
index 00000000000..c622dca2b4d
--- /dev/null
+++ b/src/test/compile-fail/traits-inductive-overflow-two-traits.rs
@@ -0,0 +1,31 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for #29859, initial version. This example allowed
+// arbitrary trait bounds to be synthesized.
+
+// Trait that you want all types to implement.
+use std::marker::{Sync as Trait};
+
+pub trait Magic {
+    type X: Trait;
+}
+impl<T: Magic> Magic for T {
+    type X = Self;
+}
+
+fn check<T: Trait>() {}
+
+fn wizard<T: Magic>() { check::<<T as Magic>::X>(); }
+
+fn main() {
+    wizard::<*mut ()>(); //~ ERROR E0275
+    // check::<*mut ()>();
+}