Rollup merge of #143764 - dianne:primary-binding-drop-order, r=Nadrieril,traviscross

lower pattern bindings in the order they're written and base drop order on primary bindings' order

To fix rust-lang/rust#142163, this PR does two things:
- Makes match arms base their drop order on the first sub-branch instead of the last sub-branch. Together with the second change, this makes bindings' drop order correspond to the relative order of when each binding first appears (i.e. the order of the "primary" bindings).
- Lowers pattern bindings in the order they're written (still treating the right-hand side of a ``@`` as coming before the binding on the left). In each sub-branch of a match arm, this is the order that would be obtained if the or-alternatives chosen in that sub-branch were inlined into the arm's pattern. This both affects drop order (making bindings in or-patterns not be dropped first) and fixes the issue in [this test](https://github.com/rust-lang/rust/blob/2a023bf80a6fbd6a06d5460a34eb247b986286ed/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.rs) from rust-lang/rust#121716.

My approach to the second point is admittedly a bit trickier than may be necessary. To avoid passing around a counter when building `FlatPat`s, I've instead added just enough information to recover the original structure of the pattern's bindings from a `MatchTreeSubBranch`'s path through the `Candidate` tree. Some alternatives:
- We could use a counter, then sort bindings by their ordinals when making `MatchTreeSubBranch`es.
- I'd like to experiment with always merging sub-candidates and removing `test_remaining_match_pairs_after_or`; that would require lowering bindings and guards in a different way. That makes it a bigger change too, though, so I figure it might be simplest to start here.
- For a very big change, we could track which or-alternatives succeed at runtime to base drop order on the binding order in the particular alternatives matched.

This is a breaking change. It will need a crater run, language team sign-off, and likely updates to the Reference.

This will conflict with rust-lang/rust#143376 and probably also rust-lang/rust#143028, so they shouldn't be merged at the same time.

r? `@matthewjasper` or `@Nadrieril`

7 files changed, 79 insertions, 96 deletions

diff --git a/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff b/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff
index b3eb3e1f8b9..484bc7dad12 100644
--- a/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff
+++ b/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff
@@ -85,11 +85,11 @@
           _8 = &(_2.2: std::string::String);
 -         _3 = &fake shallow (_2.0: bool);
 -         _4 = &fake shallow (_2.1: bool);
-          StorageLive(_12);
-          StorageLive(_13);
-          _13 = copy _1;
--         switchInt(move _13) -> [0: bb16, otherwise: bb15];
-+         switchInt(move _13) -> [0: bb13, otherwise: bb12];
+          StorageLive(_9);
+          StorageLive(_10);
+          _10 = copy _1;
+-         switchInt(move _10) -> [0: bb12, otherwise: bb11];
++         switchInt(move _10) -> [0: bb9, otherwise: bb8];
       }
   
 -     bb9: {
@@ -100,11 +100,11 @@
           _8 = &(_2.2: std::string::String);
 -         _3 = &fake shallow (_2.0: bool);
 -         _4 = &fake shallow (_2.1: bool);
-          StorageLive(_9);
-          StorageLive(_10);
-          _10 = copy _1;
--         switchInt(move _10) -> [0: bb12, otherwise: bb11];
-+         switchInt(move _10) -> [0: bb9, otherwise: bb8];
+          StorageLive(_12);
+          StorageLive(_13);
+          _13 = copy _1;
+-         switchInt(move _13) -> [0: bb16, otherwise: bb15];
++         switchInt(move _13) -> [0: bb13, otherwise: bb12];
       }
   
 -     bb10: {
@@ -139,7 +139,7 @@
 -         FakeRead(ForGuardBinding, _6);
 -         FakeRead(ForGuardBinding, _8);
           StorageLive(_5);
-          _5 = copy (_2.1: bool);
+          _5 = copy (_2.0: bool);
           StorageLive(_7);
           _7 = move (_2.2: std::string::String);
 -         goto -> bb10;
@@ -152,8 +152,8 @@
           StorageDead(_9);
           StorageDead(_8);
           StorageDead(_6);
--         falseEdge -> [real: bb1, imaginary: bb1];
-+         goto -> bb1;
+-         falseEdge -> [real: bb3, imaginary: bb3];
++         goto -> bb2;
       }
   
 -     bb15: {
@@ -181,7 +181,7 @@
 -         FakeRead(ForGuardBinding, _6);
 -         FakeRead(ForGuardBinding, _8);
           StorageLive(_5);
-          _5 = copy (_2.0: bool);
+          _5 = copy (_2.1: bool);
           StorageLive(_7);
           _7 = move (_2.2: std::string::String);
 -         goto -> bb10;
@@ -194,8 +194,8 @@
           StorageDead(_12);
           StorageDead(_8);
           StorageDead(_6);
--         falseEdge -> [real: bb3, imaginary: bb3];
-+         goto -> bb2;
+-         falseEdge -> [real: bb1, imaginary: bb1];
++         goto -> bb1;
       }
   
 -     bb19: {
diff --git a/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff b/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff
index b3eb3e1f8b9..484bc7dad12 100644
--- a/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff
+++ b/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff
@@ -85,11 +85,11 @@
           _8 = &(_2.2: std::string::String);
 -         _3 = &fake shallow (_2.0: bool);
 -         _4 = &fake shallow (_2.1: bool);
-          StorageLive(_12);
-          StorageLive(_13);
-          _13 = copy _1;
--         switchInt(move _13) -> [0: bb16, otherwise: bb15];
-+         switchInt(move _13) -> [0: bb13, otherwise: bb12];
+          StorageLive(_9);
+          StorageLive(_10);
+          _10 = copy _1;
+-         switchInt(move _10) -> [0: bb12, otherwise: bb11];
++         switchInt(move _10) -> [0: bb9, otherwise: bb8];
       }
   
 -     bb9: {
@@ -100,11 +100,11 @@
           _8 = &(_2.2: std::string::String);
 -         _3 = &fake shallow (_2.0: bool);
 -         _4 = &fake shallow (_2.1: bool);
-          StorageLive(_9);
-          StorageLive(_10);
-          _10 = copy _1;
--         switchInt(move _10) -> [0: bb12, otherwise: bb11];
-+         switchInt(move _10) -> [0: bb9, otherwise: bb8];
+          StorageLive(_12);
+          StorageLive(_13);
+          _13 = copy _1;
+-         switchInt(move _13) -> [0: bb16, otherwise: bb15];
++         switchInt(move _13) -> [0: bb13, otherwise: bb12];
       }
   
 -     bb10: {
@@ -139,7 +139,7 @@
 -         FakeRead(ForGuardBinding, _6);
 -         FakeRead(ForGuardBinding, _8);
           StorageLive(_5);
-          _5 = copy (_2.1: bool);
+          _5 = copy (_2.0: bool);
           StorageLive(_7);
           _7 = move (_2.2: std::string::String);
 -         goto -> bb10;
@@ -152,8 +152,8 @@
           StorageDead(_9);
           StorageDead(_8);
           StorageDead(_6);
--         falseEdge -> [real: bb1, imaginary: bb1];
-+         goto -> bb1;
+-         falseEdge -> [real: bb3, imaginary: bb3];
++         goto -> bb2;
       }
   
 -     bb15: {
@@ -181,7 +181,7 @@
 -         FakeRead(ForGuardBinding, _6);
 -         FakeRead(ForGuardBinding, _8);
           StorageLive(_5);
-          _5 = copy (_2.0: bool);
+          _5 = copy (_2.1: bool);
           StorageLive(_7);
           _7 = move (_2.2: std::string::String);
 -         goto -> bb10;
@@ -194,8 +194,8 @@
           StorageDead(_12);
           StorageDead(_8);
           StorageDead(_6);
--         falseEdge -> [real: bb3, imaginary: bb3];
-+         goto -> bb2;
+-         falseEdge -> [real: bb1, imaginary: bb1];
++         goto -> bb1;
       }
   
 -     bb19: {
diff --git a/tests/ui/drop/or-pattern-drop-order.rs b/tests/ui/drop/or-pattern-drop-order.rs
index fdc28225c35..cca81673ac3 100644
--- a/tests/ui/drop/or-pattern-drop-order.rs
+++ b/tests/ui/drop/or-pattern-drop-order.rs
@@ -1,6 +1,7 @@
 //@ run-pass
 //! Test drop order for different ways of declaring pattern bindings involving or-patterns.
-//! Currently, it's inconsistent between language constructs (#142163).
+//! In particular, are ordered based on the order in which the first occurrence of each binding
+//! appears (i.e. the "primary" bindings). Regression test for #142163.
 
 use std::cell::RefCell;
 use std::ops::Drop;
@@ -43,11 +44,10 @@ fn main() {
         y = LogDrop(o, 1);
     });
 
-    // When bindings are declared with `let pat = expr;`, bindings within or-patterns are seen last,
-    // thus they're dropped first.
+    // `let pat = expr;` should have the same drop order.
     assert_drop_order(1..=3, |o| {
-        // Drops are right-to-left, treating `y` as rightmost: `y`, `z`, `x`.
-        let (x, Ok(y) | Err(y), z) = (LogDrop(o, 3), Ok(LogDrop(o, 1)), LogDrop(o, 2));
+        // Drops are right-to-left: `z`, `y`, `x`.
+        let (x, Ok(y) | Err(y), z) = (LogDrop(o, 3), Ok(LogDrop(o, 2)), LogDrop(o, 1));
     });
     assert_drop_order(1..=2, |o| {
         // The first or-pattern alternative determines the bindings' drop order: `y`, `x`.
@@ -58,30 +58,29 @@ fn main() {
         let ((true, x, y) | (false, y, x)) = (false, LogDrop(o, 1), LogDrop(o, 2));
     });
 
-    // `match` treats or-patterns as last like `let pat = expr;`, but also determines drop order
-    // using the order of the bindings in the *last* or-pattern alternative.
+    // `match` should have the same drop order.
     assert_drop_order(1..=3, |o| {
-        // Drops are right-to-left, treating `y` as rightmost: `y`, `z`, `x`.
-        match (LogDrop(o, 3), Ok(LogDrop(o, 1)), LogDrop(o, 2)) { (x, Ok(y) | Err(y), z) => {} }
+        // Drops are right-to-left: `z`, `y` `x`.
+        match (LogDrop(o, 3), Ok(LogDrop(o, 2)), LogDrop(o, 1)) { (x, Ok(y) | Err(y), z) => {} }
     });
     assert_drop_order(1..=2, |o| {
-        // The last or-pattern alternative determines the bindings' drop order: `x`, `y`.
-        match (true, LogDrop(o, 1), LogDrop(o, 2)) { (true, x, y) | (false, y, x) => {} }
+        // The first or-pattern alternative determines the bindings' drop order: `y`, `x`.
+        match (true, LogDrop(o, 2), LogDrop(o, 1)) { (true, x, y) | (false, y, x) => {} }
     });
     assert_drop_order(1..=2, |o| {
-        // That drop order is used regardless of which or-pattern alternative matches: `x`, `y`.
-        match (false, LogDrop(o, 2), LogDrop(o, 1)) { (true, x, y) | (false, y, x) => {} }
+        // That drop order is used regardless of which or-pattern alternative matches: `y`, `x`.
+        match (false, LogDrop(o, 1), LogDrop(o, 2)) { (true, x, y) | (false, y, x) => {} }
     });
 
     // Function params are visited one-by-one, and the order of bindings within a param's pattern is
-    // the same as `let pat = expr`;
+    // the same as `let pat = expr;`
     assert_drop_order(1..=3, |o| {
         // Among separate params, the drop order is right-to-left: `z`, `y`, `x`.
         (|x, (Ok(y) | Err(y)), z| {})(LogDrop(o, 3), Ok(LogDrop(o, 2)), LogDrop(o, 1));
     });
     assert_drop_order(1..=3, |o| {
-        // Within a param's pattern, or-patterns are treated as rightmost: `y`, `z`, `x`.
-        (|(x, Ok(y) | Err(y), z)| {})((LogDrop(o, 3), Ok(LogDrop(o, 1)), LogDrop(o, 2)));
+        // Within a param's pattern, likewise: `z`, `y`, `x`.
+        (|(x, Ok(y) | Err(y), z)| {})((LogDrop(o, 3), Ok(LogDrop(o, 2)), LogDrop(o, 1)));
     });
     assert_drop_order(1..=2, |o| {
         // The first or-pattern alternative determines the bindings' drop order: `y`, `x`.
@@ -89,12 +88,11 @@ fn main() {
     });
 
     // `if let` and `let`-`else` see bindings in the same order as `let pat = expr;`.
-    // Vars in or-patterns are seen last (dropped first), and the first alternative's order is used.
     assert_drop_order(1..=3, |o| {
-        if let (x, Ok(y) | Err(y), z) = (LogDrop(o, 3), Ok(LogDrop(o, 1)), LogDrop(o, 2)) {}
+        if let (x, Ok(y) | Err(y), z) = (LogDrop(o, 3), Ok(LogDrop(o, 2)), LogDrop(o, 1)) {}
     });
     assert_drop_order(1..=3, |o| {
-        let (x, Ok(y) | Err(y), z) = (LogDrop(o, 3), Ok(LogDrop(o, 1)), LogDrop(o, 2)) else {
+        let (x, Ok(y) | Err(y), z) = (LogDrop(o, 3), Ok(LogDrop(o, 2)), LogDrop(o, 1)) else {
             unreachable!();
         };
     });
@@ -106,4 +104,21 @@ fn main() {
             unreachable!();
         };
     });
+
+    // Test nested and adjacent or-patterns, including or-patterns without bindings under a guard.
+    assert_drop_order(1..=6, |o| {
+        // The `LogDrop`s that aren't moved into bindings are dropped last.
+        match [
+            [LogDrop(o, 6), LogDrop(o, 4)],
+            [LogDrop(o, 3), LogDrop(o, 2)],
+            [LogDrop(o, 1), LogDrop(o, 5)],
+        ] {
+            [
+                [_ | _, w | w] | [w | w, _ | _],
+                [x | x, y | y] | [y | y, x | x],
+                [z | z, _ | _] | [_ | _, z | z],
+            ] if true => {}
+            _ => unreachable!(),
+        }
+    });
 }
diff --git a/tests/ui/dropck/eager-by-ref-binding-for-guards.rs b/tests/ui/dropck/eager-by-ref-binding-for-guards.rs
index 3f475839171..90ff9a747ae 100644
--- a/tests/ui/dropck/eager-by-ref-binding-for-guards.rs
+++ b/tests/ui/dropck/eager-by-ref-binding-for-guards.rs
@@ -17,15 +17,15 @@ fn main() {
         (mut long2, ref short2) if true => long2.0 = &short2,
         _ => unreachable!(),
     }
-    // This depends on the binding modes of the final or-pattern alternatives (see #142163):
+    // This depends on the binding modes of the first or-pattern alternatives:
     let res: &Result<u8, &u8> = &Ok(1);
     match (Struct(&&0), res) {
         (mut long3, Ok(short3) | &Err(short3)) if true => long3.0 = &short3,
-        //~^ ERROR `short3` does not live long enough
         _ => unreachable!(),
     }
     match (Struct(&&0), res) {
         (mut long4, &Err(short4) | Ok(short4)) if true => long4.0 = &short4,
+        //~^ ERROR `short4` does not live long enough
         _ => unreachable!(),
     }
 }
diff --git a/tests/ui/dropck/eager-by-ref-binding-for-guards.stderr b/tests/ui/dropck/eager-by-ref-binding-for-guards.stderr
index cb1a04cd444..2648ce6f99c 100644
--- a/tests/ui/dropck/eager-by-ref-binding-for-guards.stderr
+++ b/tests/ui/dropck/eager-by-ref-binding-for-guards.stderr
@@ -11,15 +11,15 @@ LL |         (mut long1, ref short1) => long1.0 = &short1,
    |
    = note: values in a scope are dropped in the opposite order they are defined
 
-error[E0597]: `short3` does not live long enough
-  --> $DIR/eager-by-ref-binding-for-guards.rs:23:69
+error[E0597]: `short4` does not live long enough
+  --> $DIR/eager-by-ref-binding-for-guards.rs:27:69
    |
-LL |         (mut long3, Ok(short3) | &Err(short3)) if true => long3.0 = &short3,
-   |                        ------                                       ^^^^^^-
-   |                        |                                            |     |
-   |                        |                                            |     `short3` dropped here while still borrowed
-   |                        |                                            |     borrow might be used here, when `long3` is dropped and runs the `Drop` code for type `Struct`
-   |                        binding `short3` declared here               borrowed value does not live long enough
+LL |         (mut long4, &Err(short4) | Ok(short4)) if true => long4.0 = &short4,
+   |                          ------                                     ^^^^^^-
+   |                          |                                          |     |
+   |                          |                                          |     `short4` dropped here while still borrowed
+   |                          |                                          |     borrow might be used here, when `long4` is dropped and runs the `Drop` code for type `Struct`
+   |                          binding `short4` declared here             borrowed value does not live long enough
    |
    = note: values in a scope are dropped in the opposite order they are defined
 
diff --git a/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.rs b/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.rs
index 1555da2fd1f..dd23acfa235 100644
--- a/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.rs
+++ b/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.rs
@@ -1,16 +1,15 @@
-//@ known-bug: unknown
+//@ run-pass
 #![allow(unused)]
 
 struct A(u32);
 
 pub fn main() {
-    // The or-pattern bindings are lowered after `x`, which triggers the error.
+    // Bindings are lowered in the order they appear syntactically, so this works.
     let x @ (A(a) | A(a)) = A(10);
-    // ERROR: use of moved value
     assert!(x.0 == 10);
     assert!(a == 10);
 
-    // This works.
+    // This also works.
     let (x @ A(a) | x @ A(a)) = A(10);
     assert!(x.0 == 10);
     assert!(a == 10);
diff --git a/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.stderr b/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.stderr
deleted file mode 100644
index 79808186358..00000000000
--- a/tests/ui/pattern/bindings-after-at/bind-by-copy-or-pat.stderr
+++ /dev/null
@@ -1,31 +0,0 @@
-error[E0382]: use of moved value
-  --> $DIR/bind-by-copy-or-pat.rs:8:16
-   |
-LL |     let x @ (A(a) | A(a)) = A(10);
-   |         -      ^            ----- move occurs because value has type `A`, which does not implement the `Copy` trait
-   |         |      |
-   |         |      value used here after move
-   |         value moved here
-   |
-help: borrow this binding in the pattern to avoid moving the value
-   |
-LL |     let ref x @ (A(a) | A(a)) = A(10);
-   |         +++
-
-error[E0382]: use of moved value
-  --> $DIR/bind-by-copy-or-pat.rs:8:23
-   |
-LL |     let x @ (A(a) | A(a)) = A(10);
-   |         -             ^     ----- move occurs because value has type `A`, which does not implement the `Copy` trait
-   |         |             |
-   |         |             value used here after move
-   |         value moved here
-   |
-help: borrow this binding in the pattern to avoid moving the value
-   |
-LL |     let ref x @ (A(a) | A(a)) = A(10);
-   |         +++
-
-error: aborting due to 2 previous errors
-
-For more information about this error, try `rustc --explain E0382`.