Generate region values directly to reduce memory usage.

Also modify `SparseBitMatrix` so that it does not require knowing the
dimensions in advance, but instead grows on demand.

3 files changed, 66 insertions, 9 deletions

diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
index a22dd1fecec..617153d5765 100644
--- a/src/librustc_data_structures/bitvec.rs
+++ b/src/librustc_data_structures/bitvec.rs
@@ -281,10 +281,10 @@ where
 }
 
 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
-    /// Create a new `rows x columns` matrix, initially empty.
-    pub fn new(rows: R, _columns: C) -> SparseBitMatrix<R, C> {
-        SparseBitMatrix {
-            vector: IndexVec::from_elem_n(SparseBitSet::new(), rows.index()),
+    /// Create a new empty sparse bit matrix with no rows or columns.
+    pub fn new() -> Self {
+        Self {
+            vector: IndexVec::new(),
         }
     }
 
@@ -293,6 +293,14 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
     ///
     /// Returns true if this changed the matrix, and false otherwise.
     pub fn add(&mut self, row: R, column: C) -> bool {
+        debug!(
+            "add(row={:?}, column={:?}, current_len={})",
+            row,
+            column,
+            self.vector.len()
+        );
+        self.vector
+            .ensure_contains_elem(row, || SparseBitSet::new());
         self.vector[row].insert(column)
     }
 
@@ -301,7 +309,7 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
     /// if the matrix represents (transitive) reachability, can
     /// `row` reach `column`?
     pub fn contains(&self, row: R, column: C) -> bool {
-        self.vector[row].contains(column)
+        self.vector.get(row).map_or(false, |r| r.contains(column))
     }
 
     /// Add the bits from row `read` to the bits from row `write`,
@@ -315,16 +323,27 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         let mut changed = false;
 
         if read != write {
-            let (bit_set_read, bit_set_write) = self.vector.pick2_mut(read, write);
+            if self.vector.get(read).is_some() {
+                self.vector
+                    .ensure_contains_elem(write, || SparseBitSet::new());
+                let (bit_set_read, bit_set_write) = self.vector.pick2_mut(read, write);
 
-            for read_chunk in bit_set_read.chunks() {
-                changed = changed | bit_set_write.insert_chunk(read_chunk).any();
+                for read_chunk in bit_set_read.chunks() {
+                    changed = changed | bit_set_write.insert_chunk(read_chunk).any();
+                }
             }
         }
 
         changed
     }
 
+    /// Merge a row, `from`, into the `into` row.
+    pub fn merge_into(&mut self, into: R, from: &SparseBitSet<C>) -> bool {
+        self.vector
+            .ensure_contains_elem(into, || SparseBitSet::new());
+        self.vector[into].insert_from(from)
+    }
+
     /// True if `sub` is a subset of `sup`
     pub fn is_subset(&self, sub: R, sup: R) -> bool {
         sub == sup || {
@@ -336,10 +355,20 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         }
     }
 
+    /// Number of elements in the matrix.
+    pub fn len(&self) -> usize {
+        self.vector.len()
+    }
+
     /// Iterates through all the columns set to true in a given row of
     /// the matrix.
     pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
-        self.vector[row].iter()
+        self.vector.get(row).into_iter().flat_map(|r| r.iter())
+    }
+
+    /// Iterates through each row and the accompanying bit set.
+    pub fn iter_enumerated<'a>(&'a self) -> impl Iterator<Item = (R, &'a SparseBitSet<C>)> + 'a {
+        self.vector.iter_enumerated()
     }
 }
 
@@ -445,6 +474,15 @@ impl<I: Idx> SparseBitSet<I> {
         }
     }
 
+    /// Insert into bit set from another bit set.
+    pub fn insert_from(&mut self, from: &SparseBitSet<I>) -> bool {
+        let mut changed = false;
+        for read_chunk in from.chunks() {
+            changed = changed | self.insert_chunk(read_chunk).any();
+        }
+        changed
+    }
+
     pub fn remove_chunk(&mut self, chunk: SparseChunk<I>) -> SparseChunk<I> {
         if chunk.bits == 0 {
             return chunk;
diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index 26de2191090..e7a75c149cc 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -518,10 +518,28 @@ impl<I: Idx, T> IndexVec<I, T> {
 }
 
 impl<I: Idx, T: Clone> IndexVec<I, T> {
+    /// Grows the index vector so that it contains an entry for
+    /// `elem`; if that is already true, then has no
+    /// effect. Otherwise, inserts new values as needed by invoking
+    /// `fill_value`.
+    #[inline]
+    pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
+        let min_new_len = elem.index() + 1;
+        if self.len() < min_new_len {
+            self.raw.resize_with(min_new_len, fill_value);
+        }
+    }
+
     #[inline]
     pub fn resize(&mut self, new_len: usize, value: T) {
         self.raw.resize(new_len, value)
     }
+
+    #[inline]
+    pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
+        let min_new_len = elem.index() + 1;
+        self.raw.resize_with(min_new_len, fill_value);
+    }
 }
 
 impl<I: Idx, T: Ord> IndexVec<I, T> {
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 508dc567fa0..b386f887d77 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -30,6 +30,7 @@
 #![feature(optin_builtin_traits)]
 #![feature(macro_vis_matcher)]
 #![feature(allow_internal_unstable)]
+#![feature(vec_resize_with)]
 
 #![cfg_attr(unix, feature(libc))]
 #![cfg_attr(test, feature(test))]