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, 25 insertions, 0 deletions

diff --git a/src/test/compile-fail/traits-inductive-overflow-supertrait.rs b/src/test/compile-fail/traits-inductive-overflow-supertrait.rs
new file mode 100644
index 00000000000..c717ae9639f
--- /dev/null
+++ b/src/test/compile-fail/traits-inductive-overflow-supertrait.rs
@@ -0,0 +1,25 @@
+// 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, supertrait version. This example
+// allowed arbitrary trait bounds to be synthesized.
+
+trait Magic: Copy {}
+impl<T: Magic> Magic for T {}
+
+fn copy<T: Magic>(x: T) -> (T, T) { (x, x) }
+
+#[derive(Debug)]
+struct NoClone;
+
+fn main() {
+    let (a, b) = copy(NoClone); //~ ERROR E0275
+    println!("{:?} {:?}", a, b);
+}