False edges in `match` MIR lowering

I'm trying to understand them.

Code and docs

False edges

We don't want to have the exact structure of the decision tree be
visible through borrow checking. False edges ensure that the CFG as
seen by borrow checking doesn't encode this. False edges are added:

From each pre-binding block to the next pre-binding block.

From each otherwise block to the next pre-binding block.

The first case is set up here, the second here.

I couldn't find more explanation than that so I tried commenting out and looking at tests.

Tests

From looking at the tests, the overall idea is to make borrowck think that we're trying each arm in order despite the fact that we're often more clever than that. Also that any guard may of may not be run.

In each case, the error mentioned disappears when I disable false edges.

The pre-binding-to-pre-binding false edges

Originally added in https://github.com/rust-lang/rust/pull/45200 as "always true guards", now they do more than that.

From tests/ui/borrowck/or-patterns.rs

  fn or_pattern_moves_all(x: (String, String)) {
      match x {
          (y, _) | (_, y) => (),
      }
      &x.1;
      //~^ ERROR borrow of moved value
  }

From tests/ui/borrowck/borrowck-match-already-borrowed.rs

fn main() {
    let mut x = 1;
    let r = &mut x;
    let _ = match x {
        _ => 0,
        y => y + 2, //~ ERROR cannot use `x` because it was mutably borrowed
    };
    drop(r);
}

From tests/ui/nll/match-cfg-fake-edges.rs

let x;
// Even though x *is* always initialized, we don't want to have borrowck
// results be based on whether patterns are exhaustive.
match y {
    _ if { x = 2; true } => 1,
    _ if {
        x; //~ ERROR used binding `x` isn't initialized
        false
    } => 2,
    _ => 3,
};

From tests/ui/nll/match-cfg-fake-edges2.rs

fn all_previous_tests_may_be_done(y: &mut (bool, bool)) {
    let r = &mut y.1;
    // We don't actually test y.1 to select the second arm, but we don't want
    // borrowck results to be based on the order we match patterns.
    match y { //~ ERROR cannot use `y.1` because it was mutably borrowed
        (false, true) => {},
        (true, _) => drop(r),
        (false, _) => {},
    };
}

From tests/ui/nll/match-guards-partially-borrow.rs

fn bad_indirect_mutation_in_if_guard4(mut b: &bool) {
    match b {
        &_ => (),
        &_ if {
            b = &true; //~ ERROR cannot assign `b` in match guard
            false
        } => (),
    }
}

The otherwise-to-pre-binding false edges

From tests/ui/nll/match-cfg-fake-edges.rs

let x = String::new();
// Even though x *is* never moved before the use, we don't want to have
// borrowck results be based on whether patterns are disjoint.
match y {
    false if { drop(x); true } => {},
    true => drop(x), //~ ERROR use of moved value: `x`
    false => {},
};

fn do_guards_in_order() {
    // Like the previous case, making really sure we respect the order.
    let [a, b, c, d]: [String; 4] = Default::default();
    match true {
        false if { drop(a); true } => {},
        true  if { drop(b); true } => drop(a),
        //~^ ERROR use of moved value: `a`
        false if { drop(c); true } => drop(b),
        //~^ ERROR use of moved value: `b`
        true => drop(c),
        //~^ ERROR use of moved value: `c`
        _ => {},
    };
    let [a, b, c, d]: [String; 4] = Default::default();
    match true {
        true => drop(c),
        false if { drop(c); true } => drop(b),
        true  if { drop(b); true } => drop(a),
        false if { drop(a); true } => {},
        _ => {},
    };
}

False edges in match MIR lowering

Code and docs

False edges

Tests

The pre-binding-to-pre-binding false edges

The otherwise-to-pre-binding false edges

Read more

Validity invariants and representations

Effect as bounds on behavior

Design Meeting: Match Ergonomics 5

Match ergonomics design axioms and typing rules

False edges in `match` MIR lowering