use sparse bitsets instead of dense ones for NLL results

[nikomatsakis]

As part of #47879, it seems clear that using dense bitsets is going to be a problem for NLL sooner or later. We should move to a sparse set. I think that the BTreeMap idea sketched in #47575 may be a good choice.

The NLL region representation is defined here:

rust/src/librustc_mir/borrow_check/nll/region_infer/values.rs

Lines 186 to 200 in 16362c7

	/// Stores the values for a set of regions. These are stored in a
	/// compact `BitMatrix` representation, with one row per region
	/// variable. The columns consist of either universal regions or
	/// points in the CFG.
	#[derive(Clone)]
	pub(super) struct RegionValues {
	elements: Rc<RegionValueElements>,
	matrix: BitMatrix,
	/// If cause tracking is enabled, maps from a pair (r, e)
	/// consisting of a region `r` that contains some element `e` to
	/// the reason that the element is contained. There should be an
	/// entry for every bit set to 1 in `BitMatrix`.
	causes: Option<CauseMap>,
	}

In particular, the field matrix uses aBitMatrix. The "rows" in the matrix are inference variables, and the columns are the indices defined here (either cfg points or universal regions).

I think we should add a new type SparseBitMatrix that offers the same API as BitMatrix. It might be represented with a Vec<SparseSet>, per #47575, where SparseSet is a bit set represented as sketched in this comment. Or it might even just use a single SparseSet internally, where each bit is indexed by an index I = (row * num_columns) + column.

[nikomatsakis]

@spastorino indicated that they wanted to give this a try. @eddyb -- is your sparsebitmatrix stuff working out? Is current version on a branch somewhere?

[eddyb]

@nikomatsakis I've been using the SparseBitSet from #47575 (comment), w/o a matrix on top of it.