1use derive_generic_visitor::{Drive, DriveMut, DriveTwo};
5use enum_as_inner::EnumAsInner;
6use rustc_hash::FxHashMap as HashMap;
7use serde_state::{DeserializeState, SerializeState};
8use smallvec::{SmallVec, smallvec};
9use std::mem;
10use std::ops::{Index, IndexMut};
11
12use crate::ast::*;
13
14generate_index_type!(BlockId, "Block");
16
17pub static START_BLOCK_ID: BlockId = BlockId::ZERO;
19
20#[cfg_attr(feature = "charon_on_charon", charon::rename("Blocks"))]
21pub type BodyContents = IndexVec<BlockId, BlockData>;
22pub type ExprBody = GExprBody<BodyContents>;
23
24#[derive(Debug, Clone, PartialEq, Eq)]
27#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
28#[cfg_attr(feature = "charon_on_charon", charon::rename("Block"))]
29pub struct BlockData {
30 pub statements: Vec<Statement>,
31 pub terminator: Terminator,
32 pub kind: UnwindKind,
33}
34
35#[derive(Debug, Copy, Clone, PartialEq, Eq)]
37#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
38pub enum UnwindKind {
39 Regular,
41 Cleanup,
43 Terminate,
46}
47
48#[derive(Debug, Clone, PartialEq, Eq)]
50#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
51pub struct Statement {
52 pub span: Span,
53 pub kind: StatementKind,
54 pub comments_before: Vec<String>,
57}
58
59#[derive(Debug, Clone, PartialEq, Eq)]
60#[derive(EnumAsInner)]
61#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
62pub enum StatementKind {
63 Assign(Place, Rvalue),
64 SetDiscriminant(Place, VariantId),
66 StorageLive(LocalId),
71 StorageDead(LocalId),
76 PlaceMention(Place),
80 Borrowck(BorrowckStatement),
82 Assert {
89 assert: Assert,
90 on_failure: AbortKind,
91 },
92 Nop,
94}
95
96#[derive(Debug, Clone, PartialEq, Eq)]
97#[derive(EnumAsInner)]
98#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
99pub enum TerminatorKind {
100 Goto {
101 target: BlockId,
102 },
103 Switch {
104 data: SwitchData,
105 branches: IndexVec<BranchId, BlockId>,
106 },
107 Call {
108 call: Call,
109 dest: Place,
110 target: BlockId,
111 on_unwind: BlockId,
112 },
113 Drop {
119 kind: DropKind,
120 place: Place,
121 fn_ptr: FnPtr,
123 target: BlockId,
124 on_unwind: BlockId,
125 },
126 DropEmptyBox {
131 place: Place,
132 target: BlockId,
133 on_unwind: BlockId,
134 },
135 InlineAsm {
137 asm: InlineAsm,
138 fallthrough: Option<BlockId>,
140 labels: IndexVec<BranchId, BlockId>,
142 on_unwind: BlockId,
144 },
145
146 #[cfg_attr(feature = "charon_on_charon", charon::rename("TAssert"))]
149 Assert {
150 assert: Assert,
151 target: BlockId,
152 on_unwind: BlockId,
153 },
154 Panic {
156 call: Call,
157 on_unwind: BlockId,
158 },
159 UnwindTerminate(UnwindTerminateReason, FunDeclRef),
162 UnwindResume,
164
165 Return,
166 UndefinedBehavior,
168}
169
170#[derive(Debug, Clone, PartialEq, Eq)]
172#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
173pub struct Terminator {
174 pub span: Span,
175 pub kind: TerminatorKind,
176 pub comments_before: Vec<String>,
179}
180
181impl ExprBody {
182 pub fn as_abort_map(&self) -> HashMap<BlockId, (AbortKind, Option<Call>)> {
186 self.body
187 .iter_enumerated()
188 .filter_map(|(bid, block)| block.as_abort().map(|abort| (bid, abort)))
189 .collect()
190 }
191
192 pub fn transform_sequences_fwd<F>(&mut self, mut f: F)
193 where
194 F: FnMut(BlockId, &mut Locals, &mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
195 {
196 for (id, block) in &mut self.body.iter_mut_enumerated() {
197 block.transform_sequences_fwd(|seq| f(id, &mut self.locals, seq));
198 }
199 }
200
201 pub fn transform_sequences_bwd<F>(&mut self, mut f: F)
202 where
203 F: FnMut(&mut Locals, &mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
204 {
205 for block in &mut self.body {
206 block.transform_sequences_bwd(|seq| f(&mut self.locals, seq));
207 }
208 }
209
210 pub fn visit_block_ids_mut<F: FnMut(&mut BlockId)>(&mut self, mut f: F) {
212 for block in &mut self.body {
213 block.terminator.targets_mut().into_iter().for_each(&mut f);
214 }
215 }
216
217 pub fn visit_statements<F: FnMut(&mut Statement)>(&mut self, mut f: F) {
219 for block in self.body.iter_mut().rev() {
220 for st in block.statements.iter_mut().rev() {
221 f(st);
222 }
223 }
224 }
225}
226
227impl BlockData {
228 pub fn new_goto(span: Span, target: BlockId, kind: UnwindKind) -> Self {
230 BlockData {
231 statements: vec![],
232 terminator: Terminator::goto(span, target),
233 kind,
234 }
235 }
236 pub fn as_goto(&self) -> Option<BlockId> {
237 self.terminator.kind.as_goto().copied()
238 }
239
240 pub fn as_trivial_goto(&self) -> Option<BlockId> {
242 self.as_goto().filter(|_| {
243 self.statements
244 .iter()
245 .all(|st| matches!(st.kind, StatementKind::Nop))
246 })
247 }
248
249 pub fn is_trivial_return(&self) -> bool {
251 self.terminator.kind.is_return()
252 && self
253 .statements
254 .iter()
255 .all(|st| st.kind.is_storage_dead() || st.kind.is_nop())
256 }
257
258 pub fn as_abort(&self) -> Option<(AbortKind, Option<Call>)> {
259 if self.statements.iter().all(|st| {
260 matches!(
261 st.kind,
262 StatementKind::Nop | StatementKind::StorageLive(_) | StatementKind::StorageDead(_)
263 )
264 }) {
265 match &self.terminator.kind {
266 TerminatorKind::Panic { call, .. } => Some((AbortKind::Panic, Some(call.clone()))),
267 TerminatorKind::UndefinedBehavior => Some((AbortKind::UndefinedBehavior, None)),
268 TerminatorKind::UnwindTerminate(reason, fun_ref) => {
269 let call = Call {
270 func: FnOperand::Regular(fun_ref.clone().into()),
271 args: vec![],
272 safety: CallSafety::Inherit,
273 };
274 Some((AbortKind::UnwindTerminate(*reason), Some(call)))
275 }
276 _ => None,
277 }
278 } else {
279 None
280 }
281 }
282
283 pub fn new_unreachable(kind: UnwindKind) -> Self {
285 Terminator::new(Span::dummy(), TerminatorKind::UndefinedBehavior).into_block(kind)
286 }
287 pub fn take(&mut self) -> Self {
289 mem::replace(self, BlockData::new_unreachable(self.kind))
290 }
291
292 pub fn targets(&self) -> SmallVec<[BlockId; 2]> {
293 self.terminator.targets()
294 }
295 pub fn targets_ignoring_unwind(&self) -> SmallVec<[BlockId; 2]> {
296 self.terminator.targets_ignoring_unwind()
297 }
298
299 pub fn transform<F: FnMut(&mut Statement) -> Vec<Statement>>(&mut self, mut f: F) {
305 self.transform_sequences_fwd(|slice| {
306 let new_statements = f(&mut slice[0]);
307 if new_statements.is_empty() {
308 vec![]
309 } else {
310 vec![(0, new_statements)]
311 }
312 });
313 }
314
315 fn transform_sequences<F>(&mut self, mut f: F, forward: bool)
317 where
318 F: FnMut(&mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
319 {
320 let mut to_insert = vec![];
321 let mut final_len = self.statements.len();
322 if forward {
323 for i in 0..self.statements.len() {
324 let new_to_insert = f(&mut self.statements[i..]);
325 to_insert.extend(new_to_insert.into_iter().map(|(j, stmts)| {
326 final_len += stmts.len();
327 (i + j, stmts)
328 }));
329 }
330 } else {
331 for i in (0..self.statements.len()).rev() {
332 let new_to_insert = f(&mut self.statements[i..]);
333 to_insert.extend(new_to_insert.into_iter().map(|(j, stmts)| {
334 final_len += stmts.len();
335 (i + j, stmts)
336 }));
337 }
338 }
339 if !to_insert.is_empty() {
340 to_insert.sort_by_key(|(i, _)| *i);
341 to_insert.reverse();
343 let old_statements = mem::replace(&mut self.statements, Vec::with_capacity(final_len));
345 for (i, stmt) in old_statements.into_iter().enumerate() {
346 while let Some((j, _)) = to_insert.last()
347 && *j == i
348 {
349 let (_, mut stmts) = to_insert.pop().unwrap();
350 self.statements.append(&mut stmts);
351 }
352 self.statements.push(stmt);
353 }
354 }
355 }
356
357 pub fn transform_sequences_fwd<F>(&mut self, f: F)
363 where
364 F: FnMut(&mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
365 {
366 self.transform_sequences(f, true);
367 }
368
369 pub fn transform_sequences_bwd<F>(&mut self, f: F)
375 where
376 F: FnMut(&mut [Statement]) -> Vec<(usize, Vec<Statement>)>,
377 {
378 self.transform_sequences(f, false);
379 }
380}
381
382impl UnwindKind {
383 pub fn further_unwind_kind(self) -> Self {
385 match self {
386 Self::Regular => Self::Cleanup,
387 Self::Cleanup | Self::Terminate => Self::Terminate,
389 }
390 }
391}
392
393impl Statement {
394 pub fn new(span: Span, kind: StatementKind) -> Self {
395 Statement {
396 span,
397 kind,
398 comments_before: vec![],
399 }
400 }
401}
402
403impl Terminator {
404 pub fn new(span: Span, kind: TerminatorKind) -> Self {
405 Terminator {
406 span,
407 kind,
408 comments_before: vec![],
409 }
410 }
411 pub fn goto(span: Span, target: BlockId) -> Self {
412 Self::new(span, TerminatorKind::Goto { target })
413 }
414 pub fn is_error(&self) -> bool {
416 use TerminatorKind::*;
417 match &self.kind {
418 Panic { .. } | UndefinedBehavior | UnwindTerminate(..) => true,
419 Goto { .. }
420 | Switch { .. }
421 | InlineAsm { .. }
422 | Return
423 | Call { .. }
424 | Drop { .. }
425 | DropEmptyBox { .. }
426 | UnwindResume
427 | Assert { .. } => false,
428 }
429 }
430
431 pub fn into_block(self, kind: UnwindKind) -> BlockData {
432 BlockData {
433 statements: vec![],
434 terminator: self,
435 kind,
436 }
437 }
438
439 pub fn targets(&self) -> SmallVec<[BlockId; 2]> {
440 match &self.kind {
441 TerminatorKind::Goto { target } => {
442 smallvec![*target]
443 }
444 TerminatorKind::Switch { branches, .. } => branches.iter().copied().collect(),
445 TerminatorKind::InlineAsm {
446 fallthrough,
447 labels,
448 on_unwind,
449 ..
450 } => fallthrough
451 .iter()
452 .copied()
453 .chain(labels.iter().copied())
454 .chain([*on_unwind])
455 .collect(),
456 TerminatorKind::Call {
457 target, on_unwind, ..
458 }
459 | TerminatorKind::Drop {
460 target, on_unwind, ..
461 }
462 | TerminatorKind::DropEmptyBox {
463 target, on_unwind, ..
464 }
465 | TerminatorKind::Assert {
466 target, on_unwind, ..
467 } => smallvec![*target, *on_unwind],
468 TerminatorKind::Panic { on_unwind, .. } => smallvec![*on_unwind],
469 TerminatorKind::UndefinedBehavior
470 | TerminatorKind::UnwindTerminate(..)
471 | TerminatorKind::Return
472 | TerminatorKind::UnwindResume => {
473 smallvec![]
474 }
475 }
476 }
477 pub fn targets_mut(&mut self) -> SmallVec<[&mut BlockId; 2]> {
478 match &mut self.kind {
479 TerminatorKind::Goto { target } => {
480 smallvec![target]
481 }
482 TerminatorKind::Switch { branches, .. } => branches.iter_mut().collect(),
483 TerminatorKind::InlineAsm {
484 fallthrough,
485 labels,
486 on_unwind,
487 ..
488 } => fallthrough
489 .iter_mut()
490 .chain(labels.iter_mut())
491 .chain([on_unwind])
492 .collect(),
493 TerminatorKind::Call {
494 target, on_unwind, ..
495 }
496 | TerminatorKind::Drop {
497 target, on_unwind, ..
498 }
499 | TerminatorKind::DropEmptyBox {
500 target, on_unwind, ..
501 }
502 | TerminatorKind::Assert {
503 target, on_unwind, ..
504 } => smallvec![target, on_unwind],
505 TerminatorKind::Panic { on_unwind, .. } => smallvec![on_unwind],
506 TerminatorKind::UndefinedBehavior
507 | TerminatorKind::UnwindTerminate(..)
508 | TerminatorKind::Return
509 | TerminatorKind::UnwindResume => {
510 smallvec![]
511 }
512 }
513 }
514
515 pub fn targets_ignoring_unwind(&self) -> SmallVec<[BlockId; 2]> {
516 match &self.kind {
517 TerminatorKind::Goto { target } => {
518 smallvec![*target]
519 }
520 TerminatorKind::Switch { branches, .. } => branches.iter().copied().collect(),
521 TerminatorKind::InlineAsm {
522 fallthrough,
523 labels,
524 ..
525 } => fallthrough
526 .iter()
527 .copied()
528 .chain(labels.iter().copied())
529 .collect(),
530 TerminatorKind::Call { target, .. }
531 | TerminatorKind::Drop { target, .. }
532 | TerminatorKind::DropEmptyBox { target, .. }
533 | TerminatorKind::Assert { target, .. } => {
534 smallvec![*target]
535 }
536 TerminatorKind::Panic { .. }
537 | TerminatorKind::UndefinedBehavior
538 | TerminatorKind::UnwindTerminate(..)
539 | TerminatorKind::Return
540 | TerminatorKind::UnwindResume => {
541 smallvec![]
542 }
543 }
544 }
545}
546
547impl TerminatorKind {
548 pub fn take(&mut self) -> Self {
550 std::mem::replace(self, TerminatorKind::UndefinedBehavior)
551 }
552}
553
554#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
556pub struct StmtLoc {
557 pub block: BlockId,
558 pub statement: usize,
559}
560
561impl StmtLoc {
562 pub fn new(block: BlockId, statement: usize) -> Self {
563 StmtLoc { block, statement }
564 }
565
566 pub fn block_start(block: BlockId) -> Self {
567 StmtLoc {
568 block,
569 statement: 0,
570 }
571 }
572
573 pub fn after(self) -> Self {
574 StmtLoc {
575 block: self.block,
576 statement: self.statement + 1,
577 }
578 }
579}
580
581impl Index<StmtLoc> for ExprBody {
582 type Output = Statement;
583 fn index(&self, loc: StmtLoc) -> &Self::Output {
584 &self.body[loc.block].statements[loc.statement]
585 }
586}
587
588impl IndexMut<StmtLoc> for ExprBody {
589 fn index_mut(&mut self, loc: StmtLoc) -> &mut Self::Output {
590 &mut self.body[loc.block].statements[loc.statement]
591 }
592}
593
594pub struct BodyBuilder {
596 pub span: Span,
598 pub body: ExprBody,
600 pub current_block: BlockId,
602 pub unwind_block: Option<BlockId>,
604}
605
606fn mk_block(span: Span, term: TerminatorKind, kind: UnwindKind) -> BlockData {
607 BlockData {
608 statements: vec![],
609 terminator: Terminator::new(span, term),
610 kind,
611 }
612}
613
614impl BodyBuilder {
615 pub fn new(span: Span, arg_count: usize) -> Self {
616 let mut body: ExprBody = GExprBody {
617 span,
618 locals: Locals::new(arg_count),
619 bound_body_regions: 0,
620 body: IndexVec::new(),
621 comments: vec![],
622 };
623 let current_block = body.body.push(BlockData {
624 statements: Default::default(),
625 terminator: Terminator::new(span, TerminatorKind::Return),
626 kind: UnwindKind::Regular,
627 });
628 Self {
629 span,
630 body,
631 current_block,
632 unwind_block: None,
633 }
634 }
635
636 pub fn build(mut self) -> ExprBody {
638 let mut freshener: IndexMap<RegionId, ()> = IndexMap::new();
640 self.body.dyn_visit_mut(|r: &mut Region| {
641 if r.is_erased() || r.is_body() {
642 *r = Region::Body(freshener.push(()));
643 }
644 });
645 self.body.bound_body_regions = freshener.slot_count();
646 self.body
648 }
649
650 pub fn new_var(&mut self, name: Option<String>, ty: Ty) -> Place {
653 let place = self.body.locals.new_var(name, ty);
654 let local_id = place.as_local().unwrap();
655 if !self.body.locals.is_return_or_arg(local_id) {
656 self.push_statement(StatementKind::StorageLive(local_id));
657 }
658 place
659 }
660
661 fn current_block(&mut self) -> &mut BlockData {
663 &mut self.body.body[self.current_block]
664 }
665
666 pub fn push_statement(&mut self, kind: StatementKind) {
667 let st = Statement::new(self.span, kind);
668 self.current_block().statements.push(st);
669 }
670
671 fn unwind_block(&mut self) -> BlockId {
672 *self.unwind_block.get_or_insert_with(|| {
673 self.body.body.push(mk_block(
674 self.span,
675 TerminatorKind::UnwindResume,
676 UnwindKind::Cleanup,
677 ))
678 })
679 }
680
681 pub fn call(&mut self, dest: Place, call: Call) {
682 let next_block = self.body.body.push(mk_block(
683 self.span,
684 TerminatorKind::Return,
685 UnwindKind::Regular,
686 ));
687 let term = TerminatorKind::Call {
688 target: next_block,
689 call,
690 dest,
691 on_unwind: self.unwind_block(),
692 };
693 self.current_block().terminator.kind = term;
694 self.current_block = next_block;
695 }
696
697 pub fn insert_drop(&mut self, place: Place, fn_ptr: FnPtr) {
698 let next_block = self.body.body.push(mk_block(
699 self.span,
700 TerminatorKind::Return,
701 UnwindKind::Regular,
702 ));
703 let term = TerminatorKind::Drop {
704 kind: DropKind::Precise,
705 place,
706 fn_ptr,
707 target: next_block,
708 on_unwind: self.unwind_block(),
709 };
710 self.current_block().terminator.kind = term;
711 self.current_block = next_block;
712 }
713}