diff options
Diffstat (limited to 'compiler/rustc_index')
| -rw-r--r-- | compiler/rustc_index/Cargo.toml | 2 | ||||
| -rw-r--r-- | compiler/rustc_index/src/bit_set.rs | 253 | ||||
| -rw-r--r-- | compiler/rustc_index/src/bit_set/tests.rs | 56 | ||||
| -rw-r--r-- | compiler/rustc_index/src/idx.rs | 15 | ||||
| -rw-r--r-- | compiler/rustc_index/src/interval.rs | 54 |
5 files changed, 235 insertions, 145 deletions
diff --git a/compiler/rustc_index/Cargo.toml b/compiler/rustc_index/Cargo.toml index 3d83a3c98da..e46a1a7f760 100644 --- a/compiler/rustc_index/Cargo.toml +++ b/compiler/rustc_index/Cargo.toml @@ -15,8 +15,8 @@ smallvec = "1.8.1" # tidy-alphabetical-start default = ["nightly"] nightly = [ - "dep:rustc_serialize", "dep:rustc_macros", + "dep:rustc_serialize", "rustc_index_macros/nightly", ] rustc_randomized_layouts = [] diff --git a/compiler/rustc_index/src/bit_set.rs b/compiler/rustc_index/src/bit_set.rs index 0b3bc8963a3..f7649c5f5c5 100644 --- a/compiler/rustc_index/src/bit_set.rs +++ b/compiler/rustc_index/src/bit_set.rs @@ -491,19 +491,15 @@ pub struct ChunkedBitSet<T> { marker: PhantomData<T>, } -// Note: the chunk domain size is duplicated in each variant. This is a bit -// inconvenient, but it allows the type size to be smaller than if we had an -// outer struct containing a chunk domain size plus the `Chunk`, because the -// compiler can place the chunk domain size after the tag. +// NOTE: The chunk size is computed on-the-fly on each manipulation of a chunk. +// This avoids storing it, as it's almost always CHUNK_BITS except for the last one. #[derive(Clone, Debug, PartialEq, Eq)] enum Chunk { /// A chunk that is all zeros; we don't represent the zeros explicitly. - /// The `ChunkSize` is always non-zero. - Zeros(ChunkSize), + Zeros, /// A chunk that is all ones; we don't represent the ones explicitly. - /// `ChunkSize` is always non-zero. - Ones(ChunkSize), + Ones, /// A chunk that has a mix of zeros and ones, which are represented /// explicitly and densely. It never has all zeros or all ones. @@ -514,16 +510,14 @@ enum Chunk { /// to store the length, which would make this type larger. These excess /// words are always zero, as are any excess bits in the final in-use word. /// - /// The first `ChunkSize` field is always non-zero. - /// - /// The second `ChunkSize` field is the count of 1s set in the chunk, and + /// The `ChunkSize` field is the count of 1s set in the chunk, and /// must satisfy `0 < count < chunk_domain_size`. /// /// The words are within an `Rc` because it's surprisingly common to /// duplicate an entire chunk, e.g. in `ChunkedBitSet::clone_from()`, or /// when a `Mixed` chunk is union'd into a `Zeros` chunk. When we do need /// to modify a chunk we use `Rc::make_mut`. - Mixed(ChunkSize, ChunkSize, Rc<[Word; CHUNK_WORDS]>), + Mixed(ChunkSize, Rc<[Word; CHUNK_WORDS]>), } // This type is used a lot. Make sure it doesn't unintentionally get bigger. @@ -535,6 +529,22 @@ impl<T> ChunkedBitSet<T> { self.domain_size } + #[inline] + fn last_chunk_size(&self) -> ChunkSize { + let n = self.domain_size % CHUNK_BITS; + if n == 0 { CHUNK_BITS as ChunkSize } else { n as ChunkSize } + } + + /// All the chunks have a chunk_domain_size of `CHUNK_BITS` except the final one. + #[inline] + fn chunk_domain_size(&self, chunk: usize) -> ChunkSize { + if chunk == self.chunks.len() - 1 { + self.last_chunk_size() + } else { + CHUNK_BITS as ChunkSize + } + } + #[cfg(test)] fn assert_valid(&self) { if self.domain_size == 0 { @@ -544,8 +554,9 @@ impl<T> ChunkedBitSet<T> { assert!((self.chunks.len() - 1) * CHUNK_BITS <= self.domain_size); assert!(self.chunks.len() * CHUNK_BITS >= self.domain_size); - for chunk in self.chunks.iter() { - chunk.assert_valid(); + for (chunk_index, chunk) in self.chunks.iter().enumerate() { + let chunk_domain_size = self.chunk_domain_size(chunk_index); + chunk.assert_valid(chunk_domain_size); } } } @@ -556,16 +567,7 @@ impl<T: Idx> ChunkedBitSet<T> { let chunks = if domain_size == 0 { Box::new([]) } else { - // All the chunks have a chunk_domain_size of `CHUNK_BITS` except - // the final one. - let final_chunk_domain_size = { - let n = domain_size % CHUNK_BITS; - if n == 0 { CHUNK_BITS } else { n } - }; - let mut chunks = - vec![Chunk::new(CHUNK_BITS, is_empty); num_chunks(domain_size)].into_boxed_slice(); - *chunks.last_mut().unwrap() = Chunk::new(final_chunk_domain_size, is_empty); - chunks + vec![if is_empty { Zeros } else { Ones }; num_chunks(domain_size)].into_boxed_slice() }; ChunkedBitSet { domain_size, chunks, marker: PhantomData } } @@ -594,11 +596,15 @@ impl<T: Idx> ChunkedBitSet<T> { /// Count the number of bits in the set. pub fn count(&self) -> usize { - self.chunks.iter().map(|chunk| chunk.count()).sum() + self.chunks + .iter() + .enumerate() + .map(|(index, chunk)| chunk.count(self.chunk_domain_size(index))) + .sum() } pub fn is_empty(&self) -> bool { - self.chunks.iter().all(|chunk| matches!(chunk, Zeros(..))) + self.chunks.iter().all(|chunk| matches!(chunk, Zeros)) } /// Returns `true` if `self` contains `elem`. @@ -607,9 +613,9 @@ impl<T: Idx> ChunkedBitSet<T> { assert!(elem.index() < self.domain_size); let chunk = &self.chunks[chunk_index(elem)]; match &chunk { - Zeros(_) => false, - Ones(_) => true, - Mixed(_, _, words) => { + Zeros => false, + Ones => true, + Mixed(_, words) => { let (word_index, mask) = chunk_word_index_and_mask(elem); (words[word_index] & mask) != 0 } @@ -625,9 +631,10 @@ impl<T: Idx> ChunkedBitSet<T> { pub fn insert(&mut self, elem: T) -> bool { assert!(elem.index() < self.domain_size); let chunk_index = chunk_index(elem); + let chunk_domain_size = self.chunk_domain_size(chunk_index); let chunk = &mut self.chunks[chunk_index]; match *chunk { - Zeros(chunk_domain_size) => { + Zeros => { if chunk_domain_size > 1 { #[cfg(feature = "nightly")] let mut words = { @@ -649,14 +656,14 @@ impl<T: Idx> ChunkedBitSet<T> { let (word_index, mask) = chunk_word_index_and_mask(elem); words_ref[word_index] |= mask; - *chunk = Mixed(chunk_domain_size, 1, words); + *chunk = Mixed(1, words); } else { - *chunk = Ones(chunk_domain_size); + *chunk = Ones; } true } - Ones(_) => false, - Mixed(chunk_domain_size, ref mut count, ref mut words) => { + Ones => false, + Mixed(ref mut count, ref mut words) => { // We skip all the work if the bit is already set. let (word_index, mask) = chunk_word_index_and_mask(elem); if (words[word_index] & mask) == 0 { @@ -665,7 +672,7 @@ impl<T: Idx> ChunkedBitSet<T> { let words = Rc::make_mut(words); words[word_index] |= mask; } else { - *chunk = Ones(chunk_domain_size); + *chunk = Ones; } true } else { @@ -678,11 +685,7 @@ impl<T: Idx> ChunkedBitSet<T> { /// Sets all bits to true. pub fn insert_all(&mut self) { for chunk in self.chunks.iter_mut() { - *chunk = match *chunk { - Zeros(chunk_domain_size) - | Ones(chunk_domain_size) - | Mixed(chunk_domain_size, ..) => Ones(chunk_domain_size), - } + *chunk = Ones; } } @@ -690,10 +693,11 @@ impl<T: Idx> ChunkedBitSet<T> { pub fn remove(&mut self, elem: T) -> bool { assert!(elem.index() < self.domain_size); let chunk_index = chunk_index(elem); + let chunk_domain_size = self.chunk_domain_size(chunk_index); let chunk = &mut self.chunks[chunk_index]; match *chunk { - Zeros(_) => false, - Ones(chunk_domain_size) => { + Zeros => false, + Ones => { if chunk_domain_size > 1 { #[cfg(feature = "nightly")] let mut words = { @@ -722,13 +726,13 @@ impl<T: Idx> ChunkedBitSet<T> { ); let (word_index, mask) = chunk_word_index_and_mask(elem); words_ref[word_index] &= !mask; - *chunk = Mixed(chunk_domain_size, chunk_domain_size - 1, words); + *chunk = Mixed(chunk_domain_size - 1, words); } else { - *chunk = Zeros(chunk_domain_size); + *chunk = Zeros; } true } - Mixed(chunk_domain_size, ref mut count, ref mut words) => { + Mixed(ref mut count, ref mut words) => { // We skip all the work if the bit is already clear. let (word_index, mask) = chunk_word_index_and_mask(elem); if (words[word_index] & mask) != 0 { @@ -737,7 +741,7 @@ impl<T: Idx> ChunkedBitSet<T> { let words = Rc::make_mut(words); words[word_index] &= !mask; } else { - *chunk = Zeros(chunk_domain_size); + *chunk = Zeros } true } else { @@ -748,11 +752,12 @@ impl<T: Idx> ChunkedBitSet<T> { } fn chunk_iter(&self, chunk_index: usize) -> ChunkIter<'_> { + let chunk_domain_size = self.chunk_domain_size(chunk_index); match self.chunks.get(chunk_index) { - Some(Zeros(_chunk_domain_size)) => ChunkIter::Zeros, - Some(Ones(chunk_domain_size)) => ChunkIter::Ones(0..*chunk_domain_size as usize), - Some(Mixed(chunk_domain_size, _, words)) => { - let num_words = num_words(*chunk_domain_size as usize); + Some(Zeros) => ChunkIter::Zeros, + Some(Ones) => ChunkIter::Ones(0..chunk_domain_size as usize), + Some(Mixed(_, words)) => { + let num_words = num_words(chunk_domain_size as usize); ChunkIter::Mixed(BitIter::new(&words[0..num_words])) } None => ChunkIter::Finished, @@ -765,23 +770,33 @@ impl<T: Idx> ChunkedBitSet<T> { impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { fn union(&mut self, other: &ChunkedBitSet<T>) -> bool { assert_eq!(self.domain_size, other.domain_size); - debug_assert_eq!(self.chunks.len(), other.chunks.len()); + + let num_chunks = self.chunks.len(); + debug_assert_eq!(num_chunks, other.chunks.len()); + + let last_chunk_size = self.last_chunk_size(); + debug_assert_eq!(last_chunk_size, other.last_chunk_size()); let mut changed = false; - for (mut self_chunk, other_chunk) in self.chunks.iter_mut().zip(other.chunks.iter()) { + for (chunk_index, (mut self_chunk, other_chunk)) in + self.chunks.iter_mut().zip(other.chunks.iter()).enumerate() + { + let chunk_domain_size = if chunk_index + 1 == num_chunks { + last_chunk_size + } else { + CHUNK_BITS as ChunkSize + }; + match (&mut self_chunk, &other_chunk) { - (_, Zeros(_)) | (Ones(_), _) => {} - (Zeros(self_chunk_domain_size), Ones(other_chunk_domain_size)) - | (Mixed(self_chunk_domain_size, ..), Ones(other_chunk_domain_size)) - | (Zeros(self_chunk_domain_size), Mixed(other_chunk_domain_size, ..)) => { + (_, Zeros) | (Ones, _) => {} + (Zeros, Ones) | (Mixed(..), Ones) | (Zeros, Mixed(..)) => { // `other_chunk` fully overwrites `self_chunk` - debug_assert_eq!(self_chunk_domain_size, other_chunk_domain_size); *self_chunk = other_chunk.clone(); changed = true; } ( - Mixed(self_chunk_domain_size, self_chunk_count, self_chunk_words), - Mixed(_other_chunk_domain_size, _other_chunk_count, other_chunk_words), + Mixed(self_chunk_count, self_chunk_words), + Mixed(_other_chunk_count, other_chunk_words), ) => { // First check if the operation would change // `self_chunk.words`. If not, we can avoid allocating some @@ -789,7 +804,7 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { // performance win. Also, we only need to operate on the // in-use words, hence the slicing. let op = |a, b| a | b; - let num_words = num_words(*self_chunk_domain_size as usize); + let num_words = num_words(chunk_domain_size as usize); if bitwise_changes( &self_chunk_words[0..num_words], &other_chunk_words[0..num_words], @@ -806,8 +821,8 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { .iter() .map(|w| w.count_ones() as ChunkSize) .sum(); - if *self_chunk_count == *self_chunk_domain_size { - *self_chunk = Ones(*self_chunk_domain_size); + if *self_chunk_count == chunk_domain_size { + *self_chunk = Ones; } changed = true; } @@ -819,36 +834,41 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { fn subtract(&mut self, other: &ChunkedBitSet<T>) -> bool { assert_eq!(self.domain_size, other.domain_size); - debug_assert_eq!(self.chunks.len(), other.chunks.len()); + + let num_chunks = self.chunks.len(); + debug_assert_eq!(num_chunks, other.chunks.len()); + + let last_chunk_size = self.last_chunk_size(); + debug_assert_eq!(last_chunk_size, other.last_chunk_size()); let mut changed = false; - for (mut self_chunk, other_chunk) in self.chunks.iter_mut().zip(other.chunks.iter()) { + for (chunk_index, (mut self_chunk, other_chunk)) in + self.chunks.iter_mut().zip(other.chunks.iter()).enumerate() + { + let chunk_domain_size = if chunk_index + 1 == num_chunks { + last_chunk_size + } else { + CHUNK_BITS as ChunkSize + }; + match (&mut self_chunk, &other_chunk) { - (Zeros(..), _) | (_, Zeros(..)) => {} - ( - Ones(self_chunk_domain_size) | Mixed(self_chunk_domain_size, _, _), - Ones(other_chunk_domain_size), - ) => { - debug_assert_eq!(self_chunk_domain_size, other_chunk_domain_size); + (Zeros, _) | (_, Zeros) => {} + (Ones | Mixed(_, _), Ones) => { changed = true; - *self_chunk = Zeros(*self_chunk_domain_size); + *self_chunk = Zeros; } - ( - Ones(self_chunk_domain_size), - Mixed(other_chunk_domain_size, other_chunk_count, other_chunk_words), - ) => { - debug_assert_eq!(self_chunk_domain_size, other_chunk_domain_size); + (Ones, Mixed(other_chunk_count, other_chunk_words)) => { changed = true; - let num_words = num_words(*self_chunk_domain_size as usize); + let num_words = num_words(chunk_domain_size as usize); debug_assert!(num_words > 0 && num_words <= CHUNK_WORDS); let mut tail_mask = - 1 << (*other_chunk_domain_size - ((num_words - 1) * WORD_BITS) as u16) - 1; + 1 << (chunk_domain_size - ((num_words - 1) * WORD_BITS) as u16) - 1; let mut self_chunk_words = **other_chunk_words; for word in self_chunk_words[0..num_words].iter_mut().rev() { *word = !*word & tail_mask; tail_mask = u64::MAX; } - let self_chunk_count = *self_chunk_domain_size - *other_chunk_count; + let self_chunk_count = chunk_domain_size - *other_chunk_count; debug_assert_eq!( self_chunk_count, self_chunk_words[0..num_words] @@ -856,16 +876,15 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { .map(|w| w.count_ones() as ChunkSize) .sum() ); - *self_chunk = - Mixed(*self_chunk_domain_size, self_chunk_count, Rc::new(self_chunk_words)); + *self_chunk = Mixed(self_chunk_count, Rc::new(self_chunk_words)); } ( - Mixed(self_chunk_domain_size, self_chunk_count, self_chunk_words), - Mixed(_other_chunk_domain_size, _other_chunk_count, other_chunk_words), + Mixed(self_chunk_count, self_chunk_words), + Mixed(_other_chunk_count, other_chunk_words), ) => { // See [`<Self as BitRelations<ChunkedBitSet<T>>>::union`] for the explanation let op = |a: u64, b: u64| a & !b; - let num_words = num_words(*self_chunk_domain_size as usize); + let num_words = num_words(chunk_domain_size as usize); if bitwise_changes( &self_chunk_words[0..num_words], &other_chunk_words[0..num_words], @@ -883,7 +902,7 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { .map(|w| w.count_ones() as ChunkSize) .sum(); if *self_chunk_count == 0 { - *self_chunk = Zeros(*self_chunk_domain_size); + *self_chunk = Zeros; } changed = true; } @@ -895,28 +914,36 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { fn intersect(&mut self, other: &ChunkedBitSet<T>) -> bool { assert_eq!(self.domain_size, other.domain_size); - debug_assert_eq!(self.chunks.len(), other.chunks.len()); + + let num_chunks = self.chunks.len(); + debug_assert_eq!(num_chunks, other.chunks.len()); + + let last_chunk_size = self.last_chunk_size(); + debug_assert_eq!(last_chunk_size, other.last_chunk_size()); let mut changed = false; - for (mut self_chunk, other_chunk) in self.chunks.iter_mut().zip(other.chunks.iter()) { + for (chunk_index, (mut self_chunk, other_chunk)) in + self.chunks.iter_mut().zip(other.chunks.iter()).enumerate() + { + let chunk_domain_size = if chunk_index + 1 == num_chunks { + last_chunk_size + } else { + CHUNK_BITS as ChunkSize + }; + match (&mut self_chunk, &other_chunk) { - (Zeros(..), _) | (_, Ones(..)) => {} - ( - Ones(self_chunk_domain_size), - Zeros(other_chunk_domain_size) | Mixed(other_chunk_domain_size, ..), - ) - | (Mixed(self_chunk_domain_size, ..), Zeros(other_chunk_domain_size)) => { - debug_assert_eq!(self_chunk_domain_size, other_chunk_domain_size); + (Zeros, _) | (_, Ones) => {} + (Ones, Zeros | Mixed(..)) | (Mixed(..), Zeros) => { changed = true; *self_chunk = other_chunk.clone(); } ( - Mixed(self_chunk_domain_size, self_chunk_count, self_chunk_words), - Mixed(_other_chunk_domain_size, _other_chunk_count, other_chunk_words), + Mixed(self_chunk_count, self_chunk_words), + Mixed(_other_chunk_count, other_chunk_words), ) => { // See [`<Self as BitRelations<ChunkedBitSet<T>>>::union`] for the explanation let op = |a, b| a & b; - let num_words = num_words(*self_chunk_domain_size as usize); + let num_words = num_words(chunk_domain_size as usize); if bitwise_changes( &self_chunk_words[0..num_words], &other_chunk_words[0..num_words], @@ -934,7 +961,7 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { .map(|w| w.count_ones() as ChunkSize) .sum(); if *self_chunk_count == 0 { - *self_chunk = Zeros(*self_chunk_domain_size); + *self_chunk = Zeros; } changed = true; } @@ -964,7 +991,7 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for DenseBitSet<T> { words = &mut words[..CHUNK_WORDS]; } match chunk { - Zeros(..) => { + Zeros => { for word in words { if *word != 0 { changed = true; @@ -972,8 +999,8 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for DenseBitSet<T> { } } } - Ones(..) => (), - Mixed(_, _, data) => { + Ones => (), + Mixed(_, data) => { for (i, word) in words.iter_mut().enumerate() { let new_val = *word & data[i]; if new_val != *word { @@ -1053,13 +1080,11 @@ impl<'a, T: Idx> Iterator for ChunkedBitIter<'a, T> { impl Chunk { #[cfg(test)] - fn assert_valid(&self) { + fn assert_valid(&self, chunk_domain_size: ChunkSize) { + assert!(chunk_domain_size as usize <= CHUNK_BITS); match *self { - Zeros(chunk_domain_size) | Ones(chunk_domain_size) => { - assert!(chunk_domain_size as usize <= CHUNK_BITS); - } - Mixed(chunk_domain_size, count, ref words) => { - assert!(chunk_domain_size as usize <= CHUNK_BITS); + Zeros | Ones => {} + Mixed(count, ref words) => { assert!(0 < count && count < chunk_domain_size); // Check the number of set bits matches `count`. @@ -1083,18 +1108,12 @@ impl Chunk { } } - fn new(chunk_domain_size: usize, is_empty: bool) -> Self { - debug_assert!(0 < chunk_domain_size && chunk_domain_size <= CHUNK_BITS); - let chunk_domain_size = chunk_domain_size as ChunkSize; - if is_empty { Zeros(chunk_domain_size) } else { Ones(chunk_domain_size) } - } - /// Count the number of 1s in the chunk. - fn count(&self) -> usize { + fn count(&self, chunk_domain_size: ChunkSize) -> usize { match *self { - Zeros(_) => 0, - Ones(chunk_domain_size) => chunk_domain_size as usize, - Mixed(_, count, _) => count as usize, + Zeros => 0, + Ones => chunk_domain_size as usize, + Mixed(count, _) => count as usize, } } } diff --git a/compiler/rustc_index/src/bit_set/tests.rs b/compiler/rustc_index/src/bit_set/tests.rs index 9ce4cf4293f..deddc872614 100644 --- a/compiler/rustc_index/src/bit_set/tests.rs +++ b/compiler/rustc_index/src/bit_set/tests.rs @@ -120,8 +120,9 @@ fn chunked_bitset() { let mut b1 = ChunkedBitSet::<usize>::new_empty(1); assert_eq!( b1, - ChunkedBitSet { domain_size: 1, chunks: Box::new([Zeros(1)]), marker: PhantomData } + ChunkedBitSet { domain_size: 1, chunks: Box::new([Zeros]), marker: PhantomData } ); + assert_eq!(b1.chunk_domain_size(0), 1); b1.assert_valid(); assert!(!b1.contains(0)); @@ -129,12 +130,12 @@ fn chunked_bitset() { assert!(b1.insert(0)); assert!(b1.contains(0)); assert_eq!(b1.count(), 1); - assert_eq!(b1.chunks(), [Ones(1)]); + assert_eq!(b1.chunks(), [Ones]); assert!(!b1.insert(0)); assert!(b1.remove(0)); assert!(!b1.contains(0)); assert_eq!(b1.count(), 0); - assert_eq!(b1.chunks(), [Zeros(1)]); + assert_eq!(b1.chunks(), [Zeros]); b1.assert_valid(); //----------------------------------------------------------------------- @@ -142,8 +143,9 @@ fn chunked_bitset() { let mut b100 = ChunkedBitSet::<usize>::new_filled(100); assert_eq!( b100, - ChunkedBitSet { domain_size: 100, chunks: Box::new([Ones(100)]), marker: PhantomData } + ChunkedBitSet { domain_size: 100, chunks: Box::new([Ones]), marker: PhantomData } ); + assert_eq!(b100.chunk_domain_size(0), 100); b100.assert_valid(); for i in 0..100 { @@ -152,7 +154,7 @@ fn chunked_bitset() { assert_eq!(b100.count(), 100); assert!(b100.remove(3)); assert!(b100.insert(3)); - assert_eq!(b100.chunks(), vec![Ones(100)]); + assert_eq!(b100.chunks(), vec![Ones]); assert!( b100.remove(20) && b100.remove(30) && b100.remove(40) && b100.remove(99) && b100.insert(30) ); @@ -161,7 +163,6 @@ fn chunked_bitset() { assert_eq!( b100.chunks(), vec![Mixed( - 100, 97, #[rustfmt::skip] Rc::new([ @@ -180,7 +181,7 @@ fn chunked_bitset() { } } assert_eq!(num_removed, 97); - assert_eq!(b100.chunks(), vec![Zeros(100)]); + assert_eq!(b100.chunks(), vec![Zeros]); b100.assert_valid(); //----------------------------------------------------------------------- @@ -188,23 +189,21 @@ fn chunked_bitset() { let mut b2548 = ChunkedBitSet::<usize>::new_empty(2548); assert_eq!( b2548, - ChunkedBitSet { - domain_size: 2548, - chunks: Box::new([Zeros(2048), Zeros(500)]), - marker: PhantomData, - } + ChunkedBitSet { domain_size: 2548, chunks: Box::new([Zeros, Zeros]), marker: PhantomData } ); + assert_eq!(b2548.chunk_domain_size(0), 2048); + assert_eq!(b2548.chunk_domain_size(1), 500); b2548.assert_valid(); b2548.insert(14); b2548.remove(14); - assert_eq!(b2548.chunks(), vec![Zeros(2048), Zeros(500)]); + assert_eq!(b2548.chunks(), vec![Zeros, Zeros]); b2548.insert_all(); for i in 0..2548 { assert!(b2548.contains(i)); } assert_eq!(b2548.count(), 2548); - assert_eq!(b2548.chunks(), vec![Ones(2048), Ones(500)]); + assert_eq!(b2548.chunks(), vec![Ones, Ones]); b2548.assert_valid(); //----------------------------------------------------------------------- @@ -212,12 +211,10 @@ fn chunked_bitset() { let mut b4096 = ChunkedBitSet::<usize>::new_empty(4096); assert_eq!( b4096, - ChunkedBitSet { - domain_size: 4096, - chunks: Box::new([Zeros(2048), Zeros(2048)]), - marker: PhantomData, - } + ChunkedBitSet { domain_size: 4096, chunks: Box::new([Zeros, Zeros]), marker: PhantomData } ); + assert_eq!(b4096.chunk_domain_size(0), 2048); + assert_eq!(b4096.chunk_domain_size(1), 2048); b4096.assert_valid(); for i in 0..4096 { @@ -231,11 +228,11 @@ fn chunked_bitset() { b4096.chunks(), #[rustfmt::skip] vec![ - Mixed(2048, 1, Rc::new([ + Mixed(1, Rc::new([ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ])), - Mixed(2048, 1, Rc::new([ + Mixed(1, Rc::new([ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x8000_0000_0000_0000 ])), @@ -251,10 +248,15 @@ fn chunked_bitset() { b10000, ChunkedBitSet { domain_size: 10000, - chunks: Box::new([Zeros(2048), Zeros(2048), Zeros(2048), Zeros(2048), Zeros(1808),]), + chunks: Box::new([Zeros, Zeros, Zeros, Zeros, Zeros,]), marker: PhantomData, } ); + assert_eq!(b10000.chunk_domain_size(0), 2048); + assert_eq!(b10000.chunk_domain_size(1), 2048); + assert_eq!(b10000.chunk_domain_size(2), 2048); + assert_eq!(b10000.chunk_domain_size(3), 2048); + assert_eq!(b10000.chunk_domain_size(4), 1808); b10000.assert_valid(); assert!(b10000.insert(3000) && b10000.insert(5000)); @@ -262,17 +264,17 @@ fn chunked_bitset() { b10000.chunks(), #[rustfmt::skip] vec![ - Zeros(2048), - Mixed(2048, 1, Rc::new([ + Zeros, + Mixed(1, Rc::new([ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100_0000_0000_0000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ])), - Mixed(2048, 1, Rc::new([ + Mixed(1, Rc::new([ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ])), - Zeros(2048), - Zeros(1808), + Zeros, + Zeros, ], ); let mut b10000b = ChunkedBitSet::<usize>::new_empty(10000); diff --git a/compiler/rustc_index/src/idx.rs b/compiler/rustc_index/src/idx.rs index 33f406e2113..9cd7134659c 100644 --- a/compiler/rustc_index/src/idx.rs +++ b/compiler/rustc_index/src/idx.rs @@ -130,7 +130,22 @@ impl<I: Idx, T> IntoSliceIdx<I, [T]> for core::range::RangeFrom<I> { impl<I: Idx, T> IntoSliceIdx<I, [T]> for core::range::RangeInclusive<I> { type Output = core::range::RangeInclusive<usize>; #[inline] + #[cfg(bootstrap)] fn into_slice_idx(self) -> Self::Output { core::range::RangeInclusive { start: self.start.index(), end: self.end.index() } } + #[inline] + #[cfg(not(bootstrap))] + fn into_slice_idx(self) -> Self::Output { + core::range::RangeInclusive { start: self.start.index(), last: self.last.index() } + } +} + +#[cfg(all(feature = "nightly", not(bootstrap)))] +impl<I: Idx, T> IntoSliceIdx<I, [T]> for core::range::RangeToInclusive<I> { + type Output = core::range::RangeToInclusive<usize>; + #[inline] + fn into_slice_idx(self) -> Self::Output { + core::range::RangeToInclusive { last: self.last.index() } + } } diff --git a/compiler/rustc_index/src/interval.rs b/compiler/rustc_index/src/interval.rs index 0225c5c4f32..dda5253e7c5 100644 --- a/compiler/rustc_index/src/interval.rs +++ b/compiler/rustc_index/src/interval.rs @@ -140,6 +140,30 @@ impl<I: Idx> IntervalSet<I> { result } + /// Specialized version of `insert` when we know that the inserted point is *after* any + /// contained. + pub fn append(&mut self, point: I) { + let point = point.index() as u32; + + if let Some((_, last_end)) = self.map.last_mut() { + assert!(*last_end <= point); + if point == *last_end { + // The point is already in the set. + } else if point == *last_end + 1 { + *last_end = point; + } else { + self.map.push((point, point)); + } + } else { + self.map.push((point, point)); + } + + debug_assert!( + self.check_invariants(), + "wrong intervals after append {point:?} to {self:?}" + ); + } + pub fn contains(&self, needle: I) -> bool { let needle = needle.index() as u32; let Some(last) = self.map.partition_point(|r| r.0 <= needle).checked_sub(1) else { @@ -176,6 +200,32 @@ impl<I: Idx> IntervalSet<I> { }) } + pub fn disjoint(&self, other: &IntervalSet<I>) -> bool + where + I: Step, + { + let helper = move || { + let mut self_iter = self.iter_intervals(); + let mut other_iter = other.iter_intervals(); + + let mut self_current = self_iter.next()?; + let mut other_current = other_iter.next()?; + + loop { + if self_current.end <= other_current.start { + self_current = self_iter.next()?; + continue; + } + if other_current.end <= self_current.start { + other_current = other_iter.next()?; + continue; + } + return Some(false); + } + }; + helper().unwrap_or(true) + } + pub fn is_empty(&self) -> bool { self.map.is_empty() } @@ -325,6 +375,10 @@ impl<R: Idx, C: Step + Idx> SparseIntervalMatrix<R, C> { self.ensure_row(row).insert(point) } + pub fn append(&mut self, row: R, point: C) { + self.ensure_row(row).append(point) + } + pub fn contains(&self, row: R, point: C) -> bool { self.row(row).is_some_and(|r| r.contains(point)) } |