indexical/bitset/
rustc.rs

1//! The Rust compiler's [`BitSet`](https://doc.rust-lang.org/beta/nightly-rustc/rustc_index/bit_set/struct.BitSet.html).
2
3extern crate rustc_driver;
4pub extern crate rustc_index;
5extern crate rustc_mir_dataflow;
6
7use crate::{
8    IndexedValue,
9    bitset::BitSet,
10    pointer::{ArcFamily, PointerFamily, RcFamily, RefFamily},
11};
12use rustc_mir_dataflow::JoinSemiLattice;
13use std::hash::Hash;
14
15pub use rustc_index::bit_set::{ChunkedBitSet, DenseBitSet, MixedBitIter, MixedBitSet};
16
17/// A bitset specialized to `usize` indices.
18pub type RustcBitSet = MixedBitSet<usize>;
19
20impl BitSet for RustcBitSet {
21    fn empty(size: usize) -> Self {
22        RustcBitSet::new_empty(size)
23    }
24
25    fn contains(&self, index: usize) -> bool {
26        self.contains(index)
27    }
28
29    fn insert(&mut self, index: usize) -> bool {
30        self.insert(index)
31    }
32
33    fn remove(&mut self, index: usize) -> bool {
34        self.remove(index)
35    }
36
37    fn iter(&self) -> impl Iterator<Item = usize> {
38        self.iter()
39    }
40
41    fn intersect(&mut self, other: &Self) {
42        self.intersect_changed(other);
43    }
44
45    fn intersect_changed(&mut self, other: &Self) -> bool {
46        // TODO: this code should be removed once the corresponding implementation
47        // has been added to rustc
48        match (self, other) {
49            (MixedBitSet::Large(self_large), MixedBitSet::Large(other_large)) => {
50                ChunkedBitSet::intersect(self_large, other_large)
51            }
52            (MixedBitSet::Small(self_small), MixedBitSet::Small(other_small)) => {
53                DenseBitSet::intersect(self_small, other_small)
54            }
55            _ => panic!("Mismatched domains"),
56        }
57    }
58
59    fn len(&self) -> usize {
60        self.iter().count()
61    }
62
63    fn union(&mut self, other: &Self) {
64        self.union_changed(other);
65    }
66
67    fn union_changed(&mut self, other: &Self) -> bool {
68        self.union(other)
69    }
70
71    fn subtract(&mut self, other: &Self) {
72        self.subtract_changed(other);
73    }
74
75    fn subtract_changed(&mut self, other: &Self) -> bool {
76        self.subtract(other)
77    }
78
79    fn clear(&mut self) {
80        self.clear();
81    }
82
83    fn invert(&mut self) {
84        let mut inverted = RustcBitSet::new_empty(self.domain_size());
85        inverted.insert_all();
86        inverted.subtract(self);
87        *self = inverted;
88    }
89
90    fn insert_all(&mut self) {
91        self.insert_all();
92    }
93
94    fn copy_from(&mut self, other: &Self) {
95        self.clone_from(other);
96    }
97}
98
99/// [`IndexSet`](crate::IndexSet) specialized to the `bit_set::BitSet` implementation.
100pub type IndexSet<T> = crate::IndexSet<'static, T, RustcBitSet, RcFamily>;
101
102/// [`IndexSet`](crate::IndexSet) specialized to the `bit_set::BitSet` implementation with the [`ArcFamily`].
103pub type ArcIndexSet<T> = crate::IndexSet<'static, T, RustcBitSet, ArcFamily>;
104
105/// [`IndexSet`](crate::IndexSet) specialized to the `bit_set::BitSet` implementation with the [`RefFamily`].
106pub type RefIndexSet<'a, T> = crate::IndexSet<'a, T, RustcBitSet, RefFamily<'a>>;
107
108/// [`IndexMatrix`](crate::IndexMatrix) specialized to the `bit_set::BitSet` implementation.
109pub type IndexMatrix<R, C> = crate::IndexMatrix<'static, R, C, RustcBitSet, RcFamily>;
110
111/// [`IndexMatrix`](crate::IndexMatrix) specialized to the `bit_set::BitSet` implementation with the [`ArcFamily`].
112pub type ArcIndexMatrix<R, C> = crate::IndexMatrix<'static, R, C, RustcBitSet, ArcFamily>;
113
114/// [`IndexMatrix`](crate::IndexMatrix) specialized to the `bit_set::BitSet` implementation with the [`RefFamily`].
115pub type RefIndexMatrix<'a, R, C> = crate::IndexMatrix<'a, R, C, RustcBitSet, RefFamily<'a>>;
116
117impl<'a, T, S, P> JoinSemiLattice for crate::IndexSet<'a, T, S, P>
118where
119    T: IndexedValue + 'a,
120    S: BitSet,
121    P: PointerFamily<'a>,
122{
123    fn join(&mut self, other: &Self) -> bool {
124        self.union_changed(other)
125    }
126}
127
128impl<'a, R, C, S, P> JoinSemiLattice for crate::IndexMatrix<'a, R, C, S, P>
129where
130    R: PartialEq + Eq + Hash + Clone,
131    C: IndexedValue + 'a,
132    S: BitSet,
133    P: PointerFamily<'a>,
134{
135    fn join(&mut self, other: &Self) -> bool {
136        let mut changed = false;
137        for (row, col) in other.matrix.iter() {
138            changed |= self.ensure_row(row.clone()).union_changed(col);
139        }
140        changed
141    }
142}
143
144#[test]
145fn test_rustc_bitset() {
146    crate::test_utils::impl_test::<RustcBitSet>();
147}
indexical/bitset/rustc.rs

indexical/bitset/
rustc.rs
