charon_lib/ast/bodies/structured.rs
1//! Bodies with structured control-flow (`if ... then ... else ...`,
2//! `loop { ... }`, etc).
3//!
4//! We reconstruct this structure from the unstructured ast in an optional translation pass.
5use derive_generic_visitor::*;
6use enum_as_inner::EnumAsInner;
7use serde_state::{DeserializeState, SerializeState};
8use std::mem;
9use std::sync::atomic::{AtomicUsize, Ordering};
10
11use crate::ast::*;
12
13// Globally-unique identifier for each statement.
14generate_index_type!(StatementId);
15// Globally-unique identifier for each block.
16generate_index_type!(BlockId);
17
18pub type ExprBody = GExprBody<Block>;
19
20/// A sequence of statements.
21#[derive(Debug, Clone, Eq)]
22#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
23#[serde_state(state_implements = DedupSerializerState)] // Avoid corecursive impls due to perfect derive
24pub struct Block {
25 pub span: Span,
26 /// An integer uniquely identifying this block.
27 #[cfg_attr(feature = "charon_on_charon", charon::rename("block_id"))]
28 pub id: BlockId,
29 pub statements: Vec<Statement>,
30}
31
32/// A statement, which can contain nested statements inside loops or switchers.
33#[derive(Debug, Clone, Eq)]
34#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
35pub struct Statement {
36 pub span: Span,
37 /// An integer uniquely identifying this statement.
38 #[cfg_attr(feature = "charon_on_charon", charon::rename("statement_id"))]
39 pub id: StatementId,
40 pub kind: StatementKind,
41 /// Comments that precede this statement.
42 // This is filled in a late pass after all the control-flow manipulation.
43 pub comments_before: Vec<String>,
44}
45
46#[derive(Debug, Clone, PartialEq, Eq)]
47#[derive(EnumAsInner)]
48#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
49pub enum StatementKind {
50 /// Assigns an `Rvalue` to a `Place`. e.g. `let y = x;` could become
51 /// `y := move x` which is represented as `Assign(y, Rvalue::Use(Operand::Move(x)))`.
52 Assign(Place, Rvalue),
53 /// Not used today because we take MIR built.
54 SetDiscriminant(Place, VariantId),
55 /// Indicates that this local should be allocated; if it is already allocated, this frees
56 /// the local and re-allocates it. The arguments do not receive a `StorageLive`. We ensure in
57 /// the micro-pass `insert_storage_statements` that all other locals have a `StorageLive`
58 /// associated with them.
59 StorageLive(LocalId),
60 /// Deallocates the given local; if it is already deallocated, this is
61 /// a no-op. Not all local deallocations are explicit: if a non-return local is still live at
62 /// function end (return or unwind), it is implicitly deallocated.
63 /// If `--deallocate-all-locals` is set, all local deallocations are made explicit.
64 StorageDead(LocalId),
65 /// A place is mentioned, but not accessed. The place itself must still be valid though, so
66 /// this statement is not a no-op: it can trigger UB if the place's projections are not valid
67 /// (e.g. because they go out of bounds).
68 PlaceMention(Place),
69 /// Statements that only affect borrow-checking.
70 Borrowck(BorrowckStatement),
71 /// Drop the value at the given place.
72 ///
73 /// Depending on `DropKind`, this may be a real call to `drop_glue`, or a conditional call
74 /// that should only happen if the place has not been moved out of. See the docs of `DropKind`
75 /// for more details; to get precise drops use `--precise-drops`.
76 Drop {
77 place: Place,
78 /// Reference to the `drop_glue` code to call on drop.
79 fn_ptr: FnPtr,
80 kind: DropKind,
81 on_unwind: Block,
82 },
83 /// Deallocate a `Box` whose pointee has already been moved out/dropped.
84 ///
85 /// Resugared when it appears in elaborated/optimized MIR, if `--treat-box-as-builtin` is set
86 /// and `--desugar-drops` isn't.
87 DropEmptyBox {
88 place: Place,
89 on_unwind: Block,
90 },
91 Assert {
92 assert: Assert,
93 on_failure: AbortKind,
94 on_unwind: Block,
95 },
96 /// An inline assembly block.
97 InlineAsm {
98 asm: InlineAsm,
99 /// Next block if the control-flow continues without jumping. Absent for `naked_asm!` and `noreturn`.
100 fallthrough: Option<Block>,
101 /// Targets of [`AsmOperand::Label`] operands.
102 labels: IndexVec<BranchId, Block>,
103 /// Action to be taken if the inline assembly unwinds.
104 on_unwind: Block,
105 },
106 Call {
107 call: Call,
108 dest: Place,
109 on_unwind: Block,
110 },
111 Switch {
112 data: SwitchData,
113 branches: IndexVec<BranchId, Block>,
114 },
115
116 Loop(Block),
117 /// Break out of one or more loops.
118 /// The `usize` gives the index of the loop to break from, counting inside-out:
119 /// * 0: break from the innermost loop (the current loop)
120 /// * 1: break from the second innermost loop
121 /// * ...
122 Break(usize),
123 /// Continue to the start of a loop.
124 /// The `usize` gives the index of the loop to continue to, counting inside-out:
125 /// * 0: continue to the start of the innermost loop (the current loop)
126 /// * 1: continue to the start of the second innermost loop
127 /// * ...
128 Continue(usize),
129
130 /// Call to a built-in panicking function. Only if `--reconstruct-panic-calls` is passed.
131 Panic {
132 call: Call,
133 on_unwind: Block,
134 },
135 /// Unwinding must stop for ABI reasons or because cleanup code panicked again. The function is
136 /// the lang item that rustc calls in that case.
137 UnwindTerminate(UnwindTerminateReason, FunDeclRef),
138 /// Unwind out of the current function into its caller.
139 UnwindResume,
140
141 Return,
142 /// Reaching this point is undefined behavior in the Rust abstract machine.
143 UndefinedBehavior,
144 /// No-op.
145 Nop,
146}
147
148/// Ignores statement ids.
149impl PartialEq for Statement {
150 fn eq(&self, other: &Self) -> bool {
151 self.span == other.span
152 && self.kind == other.kind
153 && self.comments_before == other.comments_before
154 }
155}
156
157/// Ignores block ids.
158impl PartialEq for Block {
159 fn eq(&self, other: &Self) -> bool {
160 self.span == other.span && self.statements == other.statements
161 }
162}
163
164impl Block {
165 pub fn new(span: Span, statements: Vec<Statement>) -> Self {
166 Block {
167 span,
168 id: BlockId::fresh(),
169 statements,
170 }
171 }
172
173 pub fn new_unreachable(span: Span) -> Self {
174 Statement::new(span, StatementKind::UndefinedBehavior).into_block()
175 }
176
177 pub fn from_seq(seq: Vec<Statement>) -> Option<Self> {
178 if seq.is_empty() {
179 None
180 } else {
181 let span = seq
182 .iter()
183 .map(|st| st.span)
184 .reduce(|a, b| meta::combine_span(&a, &b))
185 .unwrap();
186 Some(Block::new(span, seq))
187 }
188 }
189
190 pub fn merge(mut self, mut other: Self) -> Self {
191 self.span = meta::combine_span(&self.span, &other.span);
192 self.statements.append(&mut other.statements);
193 self
194 }
195
196 pub fn then(mut self, r: Statement) -> Self {
197 self.span = meta::combine_span(&self.span, &r.span);
198 self.statements.push(r);
199 self
200 }
201
202 pub fn then_opt(self, other: Option<Statement>) -> Self {
203 if let Some(other) = other {
204 self.then(other)
205 } else {
206 self
207 }
208 }
209
210 /// Apply a function to all the statements, in a top-down manner.
211 pub fn visit_statements<F: FnMut(&mut Statement)>(&mut self, f: F) {
212 self.visit_helper(|_| {}, f);
213 }
214
215 /// Apply a transformer to all the statements, in a bottom-up manner. Compared to `transform`,
216 /// this also gives access to the following statements if any. Statements that are not part of
217 /// a sequence will be traversed as `[st]`. Statements that are will be traversed twice: once
218 /// as `[st]`, and then as `[st, ..]` with the following statements if any.
219 ///
220 /// The transformer should:
221 /// - mutate the current statements in place
222 /// - return the sequence of statements to introduce before the current statements
223 pub fn transform_sequences<F: FnMut(&mut [Statement]) -> Vec<Statement>>(&mut self, mut f: F) {
224 self.visit_blocks_bwd(|blk: &mut Block| {
225 let mut final_len = blk.statements.len();
226 let mut to_insert = vec![];
227 for i in (0..blk.statements.len()).rev() {
228 let new_to_insert = f(&mut blk.statements[i..]);
229 final_len += new_to_insert.len();
230 to_insert.push((i, new_to_insert));
231 }
232 if !to_insert.is_empty() {
233 to_insert.sort_by_key(|(i, _)| *i);
234 // Make it so the first element is always at the end so we can pop it.
235 to_insert.reverse();
236 // Construct the merged list of statements.
237 let old_statements =
238 mem::replace(&mut blk.statements, Vec::with_capacity(final_len));
239 for (i, stmt) in old_statements.into_iter().enumerate() {
240 while let Some((j, _)) = to_insert.last()
241 && *j == i
242 {
243 let (_, mut stmts) = to_insert.pop().unwrap();
244 blk.statements.append(&mut stmts);
245 }
246 blk.statements.push(stmt);
247 }
248 }
249 })
250 }
251
252 /// Visit `self` and its sub-blocks in a bottom-up (post-order) traversal.
253 pub fn visit_blocks_bwd<F: FnMut(&mut Block)>(&mut self, f: F) {
254 self.visit_helper(f, |_| {});
255 }
256
257 /// Small visitor helper to visit statements and blocks.
258 fn visit_helper<F: FnMut(&mut Block), G: FnMut(&mut Statement)>(
259 &mut self,
260 exit_blk: F,
261 enter_stmt: G,
262 ) {
263 #[derive(Visitor)]
264 pub struct BlockVisitor<F: FnMut(&mut Block), G: FnMut(&mut Statement)> {
265 exit_blk: F,
266 enter_stmt: G,
267 }
268
269 impl<F: FnMut(&mut Block), G: FnMut(&mut Statement)> VisitBodyMut for BlockVisitor<F, G> {
270 fn exit_llbc_block(&mut self, x: &mut Block) {
271 (self.exit_blk)(x)
272 }
273 fn enter_llbc_statement(&mut self, x: &mut Statement) {
274 (self.enter_stmt)(x)
275 }
276 }
277 BlockVisitor {
278 exit_blk,
279 enter_stmt,
280 }
281 .visit_by_val_infallible(self);
282 }
283}
284
285impl BlockId {
286 pub fn fresh() -> BlockId {
287 static COUNTER: AtomicUsize = AtomicUsize::new(0);
288 let id = COUNTER.fetch_add(1, Ordering::Relaxed);
289 BlockId::new(id)
290 }
291}
292
293impl Statement {
294 pub fn new(span: Span, kind: StatementKind) -> Self {
295 Statement {
296 span,
297 id: StatementId::fresh(),
298 kind,
299 comments_before: vec![],
300 }
301 }
302
303 pub fn into_box(self) -> Box<Self> {
304 Box::new(self)
305 }
306
307 pub fn into_block(self) -> Block {
308 Block::new(self.span, vec![self])
309 }
310}
311
312impl StatementId {
313 pub fn fresh() -> StatementId {
314 static COUNTER: AtomicUsize = AtomicUsize::new(0);
315 let id = COUNTER.fetch_add(1, Ordering::Relaxed);
316 StatementId::new(id)
317 }
318}