Auto merge of #43108 - pnkfelix:mir-borrowck3c, r=arielb1

MIR borrow check (under debug flag)

Here is the current state of MIR borrow check.

It consists of (1.) some refactoring, (2.) a dataflow analysis to identify the borrows themselves, and (3.) a mir "transform" that does the borrow check itself based on the aforementioned dataflow results.

(There's also a drive-by fix to dataflow that I can factor into a separate PR if necessary. Interestingly I could not find a way to observe the bug outside of MIR borrowck.)

To be clear, this branch is not ready to be used as the default borrow check. Thus the code is guarded: To get mir-borrowck to run, you need to either supply an attribute `#[rustc_mir_borrowck]` or a debug flag `-Z borrowck-mir`.

Here are the main issues with the current MIR borrowck as it stands in this PR:

 * No Notes emitted yet, just errors. (So the feedback is definitely inferior compared to AST borrowck today)
 * Lvalue rendering differs between Ast and Mir. (Mostly minor, but replacement of field names with indices is very bad; big priority for me to fix ASAP.)
 * Lots of ICEs (presumably because some MIR operations used here have well-formedness assumptions that are violated in borrowck-broken code)
 * Conflates lots of cases that are distinguished by AST-borrowck
 * Conflates "uninitialized" with "moved" (special case of previous bullet, one that I think should be fixed ASAP)

 (I am hoping to fix as many of the above issues as I can in the near term, but I also would like to land this even if they are *not* all fixed, because the rebasing effort is getting to be a real drag.)

1 files changed, 64 insertions, 0 deletions

diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index 572ce98d3ae..9cb6806e9ad 100644
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -153,4 +153,68 @@ impl<T: Idx> IdxSet<T> {
     pub fn subtract(&mut self, other: &IdxSet<T>) -> bool {
         bitwise(self.words_mut(), other.words(), &Subtract)
     }
+
+    /// Calls `f` on each index value held in this set, up to the
+    /// bound `max_bits` on the size of universe of indexes.
+    pub fn each_bit<F>(&self, max_bits: usize, f: F) where F: FnMut(T) {
+        each_bit(self, max_bits, f)
+    }
+
+    /// Removes all elements from this set.
+    pub fn reset_to_empty(&mut self) {
+        for word in self.words_mut() { *word = 0; }
+    }
+
+    pub fn elems(&self, universe_size: usize) -> Elems<T> {
+        Elems { i: 0, set: self, universe_size: universe_size }
+    }
+}
+
+pub struct Elems<'a, T: Idx> { i: usize, set: &'a IdxSet<T>, universe_size: usize }
+
+impl<'a, T: Idx> Iterator for Elems<'a, T> {
+    type Item = T;
+    fn next(&mut self) -> Option<T> {
+        if self.i >= self.universe_size { return None; }
+        let mut i = self.i;
+        loop {
+            if i >= self.universe_size {
+                self.i = i; // (mark iteration as complete.)
+                return None;
+            }
+            if self.set.contains(&T::new(i)) {
+                self.i = i + 1; // (next element to start at.)
+                return Some(T::new(i));
+            }
+            i = i + 1;
+        }
+    }
+}
+
+fn each_bit<T: Idx, F>(words: &IdxSet<T>, max_bits: usize, mut f: F) where F: FnMut(T) {
+    let usize_bits: usize = mem::size_of::<usize>() * 8;
+
+    for (word_index, &word) in words.words().iter().enumerate() {
+        if word != 0 {
+            let base_index = word_index * usize_bits;
+            for offset in 0..usize_bits {
+                let bit = 1 << offset;
+                if (word & bit) != 0 {
+                    // NB: we round up the total number of bits
+                    // that we store in any given bit set so that
+                    // it is an even multiple of usize::BITS. This
+                    // means that there may be some stray bits at
+                    // the end that do not correspond to any
+                    // actual value; that's why we first check
+                    // that we are in range of bits_per_block.
+                    let bit_index = base_index + offset as usize;
+                    if bit_index >= max_bits {
+                        return;
+                    } else {
+                        f(Idx::new(bit_index));
+                    }
+                }
+            }
+        }
+    }
 }