1 //! A test for the logic that updates the state in a `ResultsCursor` during seek.
3 use std
::marker
::PhantomData
;
5 use rustc_index
::bit_set
::BitSet
;
6 use rustc_index
::vec
::IndexVec
;
7 use rustc_middle
::mir
::{self, BasicBlock, Location}
;
9 use rustc_span
::DUMMY_SP
;
13 /// Creates a `mir::Body` with a few disconnected basic blocks.
15 /// This is the `Body` that will be used by the `MockAnalysis` below. The shape of its CFG is not
17 fn mock_body
<'tcx
>() -> mir
::Body
<'tcx
> {
18 let source_info
= mir
::SourceInfo
::outermost(DUMMY_SP
);
20 let mut blocks
= IndexVec
::new();
21 let mut block
= |n
, kind
| {
22 let nop
= mir
::Statement { source_info, kind: mir::StatementKind::Nop }
;
24 blocks
.push(mir
::BasicBlockData
{
25 statements
: std
::iter
::repeat(&nop
).cloned().take(n
).collect(),
26 terminator
: Some(mir
::Terminator { source_info, kind }
),
31 let dummy_place
= mir
::Place { local: mir::RETURN_PLACE, projection: ty::List::empty() }
;
33 block(4, mir
::TerminatorKind
::Return
);
34 block(1, mir
::TerminatorKind
::Return
);
37 mir
::TerminatorKind
::Call
{
38 func
: mir
::Operand
::Copy(dummy_place
.clone()),
40 destination
: dummy_place
.clone(),
41 target
: Some(mir
::START_BLOCK
),
47 block(3, mir
::TerminatorKind
::Return
);
48 block(0, mir
::TerminatorKind
::Return
);
51 mir
::TerminatorKind
::Call
{
52 func
: mir
::Operand
::Copy(dummy_place
.clone()),
54 destination
: dummy_place
.clone(),
55 target
: Some(mir
::START_BLOCK
),
62 mir
::Body
::new_cfg_only(blocks
)
65 /// A dataflow analysis whose state is unique at every possible `SeekTarget`.
67 /// Uniqueness is achieved by having a *locally* unique effect before and after each statement and
68 /// terminator (see `effect_at_target`) while ensuring that the entry set for each block is
69 /// *globally* unique (see `mock_entry_set`).
71 /// For example, a `BasicBlock` with ID `2` and a `Call` terminator has the following state at each
72 /// location ("+x" indicates that "x" is added to the state).
74 /// | Location | Before | After |
75 /// |------------------------|-------------------|--------|
76 /// | (on_entry) | {102} ||
77 /// | statement 0 | +0 | +1 |
78 /// | statement 1 | +2 | +3 |
79 /// | `Call` terminator | +4 | +5 |
80 /// | (on unwind) | {102,0,1,2,3,4,5} ||
82 /// The `102` in the block's entry set is derived from the basic block index and ensures that the
83 /// expected state is unique across all basic blocks. Remember, it is generated by
84 /// `mock_entry_sets`, not from actually running `MockAnalysis` to fixpoint.
85 struct MockAnalysis
<'tcx
, D
> {
86 body
: &'tcx mir
::Body
<'tcx
>,
90 impl<D
: Direction
> MockAnalysis
<'_
, D
> {
91 const BASIC_BLOCK_OFFSET
: usize = 100;
93 /// The entry set for each `BasicBlock` is the ID of that block offset by a fixed amount to
94 /// avoid colliding with the statement/terminator effects.
95 fn mock_entry_set(&self, bb
: BasicBlock
) -> BitSet
<usize> {
96 let mut ret
= self.bottom_value(self.body
);
97 ret
.insert(Self::BASIC_BLOCK_OFFSET
+ bb
.index());
101 fn mock_entry_sets(&self) -> IndexVec
<BasicBlock
, BitSet
<usize>> {
102 let empty
= self.bottom_value(self.body
);
103 let mut ret
= IndexVec
::from_elem(empty
, &self.body
.basic_blocks
);
105 for (bb
, _
) in self.body
.basic_blocks
.iter_enumerated() {
106 ret
[bb
] = self.mock_entry_set(bb
);
112 /// Returns the index that should be added to the dataflow state at the given target.
113 fn effect(&self, loc
: EffectIndex
) -> usize {
114 let idx
= match loc
.effect
{
115 Effect
::Before
=> loc
.statement_index
* 2,
116 Effect
::Primary
=> loc
.statement_index
* 2 + 1,
119 assert
!(idx
< Self::BASIC_BLOCK_OFFSET
, "Too many statements in basic block");
123 /// Returns the expected state at the given `SeekTarget`.
125 /// This is the union of index of the target basic block, the index assigned to the
126 /// target statement or terminator, and the indices of all preceding statements in the target
129 /// For example, the expected state when calling
130 /// `seek_before_primary_effect(Location { block: 2, statement_index: 2 })`
131 /// would be `[102, 0, 1, 2, 3, 4]`.
132 fn expected_state_at_target(&self, target
: SeekTarget
) -> BitSet
<usize> {
133 let block
= target
.block();
134 let mut ret
= self.bottom_value(self.body
);
135 ret
.insert(Self::BASIC_BLOCK_OFFSET
+ block
.index());
137 let target
= match target
{
138 SeekTarget
::BlockEntry { .. }
=> return ret
,
139 SeekTarget
::Before(loc
) => Effect
::Before
.at_index(loc
.statement_index
),
140 SeekTarget
::After(loc
) => Effect
::Primary
.at_index(loc
.statement_index
),
143 let mut pos
= if D
::IS_FORWARD
{
144 Effect
::Before
.at_index(0)
146 Effect
::Before
.at_index(self.body
[block
].statements
.len())
150 ret
.insert(self.effect(pos
));
157 pos
= pos
.next_in_forward_order();
159 pos
= pos
.next_in_backward_order();
165 impl<'tcx
, D
: Direction
> AnalysisDomain
<'tcx
> for MockAnalysis
<'tcx
, D
> {
166 type Domain
= BitSet
<usize>;
169 const NAME
: &'
static str = "mock";
171 fn bottom_value(&self, body
: &mir
::Body
<'tcx
>) -> Self::Domain
{
172 BitSet
::new_empty(Self::BASIC_BLOCK_OFFSET
+ body
.basic_blocks
.len())
175 fn initialize_start_block(&self, _
: &mir
::Body
<'tcx
>, _
: &mut Self::Domain
) {
176 unimplemented
!("This is never called since `MockAnalysis` is never iterated to fixpoint");
180 impl<'tcx
, D
: Direction
> Analysis
<'tcx
> for MockAnalysis
<'tcx
, D
> {
181 fn apply_statement_effect(
183 state
: &mut Self::Domain
,
184 _statement
: &mir
::Statement
<'tcx
>,
187 let idx
= self.effect(Effect
::Primary
.at_index(location
.statement_index
));
188 assert
!(state
.insert(idx
));
191 fn apply_before_statement_effect(
193 state
: &mut Self::Domain
,
194 _statement
: &mir
::Statement
<'tcx
>,
197 let idx
= self.effect(Effect
::Before
.at_index(location
.statement_index
));
198 assert
!(state
.insert(idx
));
201 fn apply_terminator_effect(
203 state
: &mut Self::Domain
,
204 _terminator
: &mir
::Terminator
<'tcx
>,
207 let idx
= self.effect(Effect
::Primary
.at_index(location
.statement_index
));
208 assert
!(state
.insert(idx
));
211 fn apply_before_terminator_effect(
213 state
: &mut Self::Domain
,
214 _terminator
: &mir
::Terminator
<'tcx
>,
217 let idx
= self.effect(Effect
::Before
.at_index(location
.statement_index
));
218 assert
!(state
.insert(idx
));
221 fn apply_call_return_effect(
223 _state
: &mut Self::Domain
,
225 _return_places
: CallReturnPlaces
<'_
, 'tcx
>,
230 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
232 BlockEntry(BasicBlock
),
238 fn block(&self) -> BasicBlock
{
242 BlockEntry(block
) => block
,
243 Before(loc
) | After(loc
) => loc
.block
,
247 /// An iterator over all possible `SeekTarget`s in a given block in order, starting with
249 fn iter_in_block(body
: &mir
::Body
<'_
>, block
: BasicBlock
) -> impl Iterator
<Item
= Self> {
250 let statements_and_terminator
= (0..=body
[block
].statements
.len())
251 .flat_map(|i
| (0..2).map(move |j
| (i
, j
)))
252 .map(move |(i
, kind
)| {
253 let loc
= Location { block, statement_index: i }
;
255 0 => SeekTarget
::Before(loc
),
256 1 => SeekTarget
::After(loc
),
261 std
::iter
::once(SeekTarget
::BlockEntry(block
)).chain(statements_and_terminator
)
265 fn test_cursor
<D
: Direction
>(analysis
: MockAnalysis
<'_
, D
>) {
266 let body
= analysis
.body
;
269 Results { entry_sets: analysis.mock_entry_sets(), analysis }
.into_results_cursor(body
);
271 cursor
.allow_unreachable();
273 let every_target
= || {
274 body
.basic_blocks
.iter_enumerated().flat_map(|(bb
, _
)| SeekTarget
::iter_in_block(body
, bb
))
277 let mut seek_to_target
= |targ
| {
281 BlockEntry(block
) => cursor
.seek_to_block_entry(block
),
282 Before(loc
) => cursor
.seek_before_primary_effect(loc
),
283 After(loc
) => cursor
.seek_after_primary_effect(loc
),
286 assert_eq
!(cursor
.get(), &cursor
.analysis().expected_state_at_target(targ
));
289 // Seek *to* every possible `SeekTarget` *from* every possible `SeekTarget`.
291 // By resetting the cursor to `from` each time it changes, we end up checking some edges twice.
292 // What we really want is an Eulerian cycle for the complete digraph over all possible
293 // `SeekTarget`s, but it's not worth spending the time to compute it.
294 for from
in every_target() {
295 seek_to_target(from
);
297 for to
in every_target() {
301 seek_to_target(from
);
307 fn backward_cursor() {
308 let body
= mock_body();
310 let analysis
= MockAnalysis { body, dir: PhantomData::<Backward> }
;
311 test_cursor(analysis
)
315 fn forward_cursor() {
316 let body
= mock_body();
318 let analysis
= MockAnalysis { body, dir: PhantomData::<Forward> }
;
319 test_cursor(analysis
)