charon_lib/transform/
ctx.rs

1use crate::ast::*;
2use crate::errors::{ErrorCtx, Level};
3use crate::formatter::{FmtCtx, IntoFormatter};
4use crate::llbc_ast;
5use crate::options::TranslateOptions;
6use crate::pretty::FmtWithCtx;
7use crate::ullbc_ast;
8use std::cell::RefCell;
9use std::{fmt, mem};
10
11/// Simpler context used for rustc-independent code transformation. This only depends on rustc for
12/// its error reporting machinery.
13pub struct TransformCtx {
14    /// The options that control transformation.
15    pub options: TranslateOptions,
16    /// The translated data.
17    pub translated: TranslatedCrate,
18    /// Context for tracking and reporting errors.
19    pub errors: RefCell<ErrorCtx>,
20}
21
22/// A pass that modifies ullbc bodies.
23pub trait UllbcPass: Sync {
24    /// Whether the pass should run.
25    fn should_run(&self, _options: &TranslateOptions) -> bool {
26        true
27    }
28
29    /// Transform a body.
30    fn transform_body(&self, _ctx: &mut TransformCtx, _body: &mut ullbc_ast::ExprBody) {}
31
32    /// Transform a function declaration. This forwards to `transform_body` by default.
33    fn transform_function(&self, ctx: &mut TransformCtx, decl: &mut FunDecl) {
34        if let Some(body) = decl.body.as_unstructured_mut() {
35            self.transform_body(ctx, body)
36        }
37    }
38
39    /// Transform the given context. This forwards to the other methods by default.
40    fn transform_ctx(&self, ctx: &mut TransformCtx) {
41        ctx.for_each_fun_decl(|ctx, decl| {
42            self.log_before_body(ctx, &decl.item_meta.name, &decl.body);
43            self.transform_function(ctx, decl);
44        });
45    }
46
47    /// The name of the pass, used for debug logging. The default implementation uses the type
48    /// name.
49    fn name(&self) -> &str {
50        std::any::type_name::<Self>()
51    }
52
53    /// Log that the pass is about to be run on this body.
54    fn log_before_body(&self, ctx: &TransformCtx, name: &Name, body: &Body) {
55        let fmt_ctx = &ctx.into_fmt();
56        trace!(
57            "# About to run pass [{}] on `{}`:\n{}",
58            self.name(),
59            name.with_ctx(fmt_ctx),
60            body.with_ctx(fmt_ctx),
61        );
62    }
63}
64
65/// A pass that modifies ullbc bodies and can be fused with previous passes so that we run all of
66/// them on a given body.
67pub trait FusedUllbcPass: Sync {
68    /// Whether the pass should run.
69    fn should_run(&self, _options: &TranslateOptions) -> bool {
70        true
71    }
72
73    /// Transform a body.
74    fn transform_body(&self, _ctx: &mut TransformCtx, _body: &mut ullbc_ast::ExprBody) {}
75
76    /// Transform a function declaration. This forwards to `transform_body` by default.
77    fn transform_function(&self, ctx: &mut TransformCtx, decl: &mut FunDecl) {
78        if let Some(body) = decl.body.as_unstructured_mut() {
79            self.transform_body(ctx, body)
80        }
81    }
82
83    /// The name of the pass, used for debug logging. The default implementation uses the type
84    /// name.
85    fn name(&self) -> &str {
86        std::any::type_name::<Self>()
87    }
88}
89
90/// A pass that modifies llbc bodies.
91pub trait LlbcPass: Sync {
92    /// Whether the pass should run.
93    fn should_run(&self, _options: &TranslateOptions) -> bool {
94        true
95    }
96
97    /// Transform a body.
98    fn transform_body(&self, _ctx: &mut TransformCtx, _body: &mut llbc_ast::ExprBody) {}
99
100    /// Transform a function declaration. This forwards to `transform_body` by default.
101    fn transform_function(&self, ctx: &mut TransformCtx, decl: &mut FunDecl) {
102        if let Some(body) = decl.body.as_structured_mut() {
103            self.transform_body(ctx, body)
104        }
105    }
106
107    /// Transform the given context. This forwards to the other methods by default.
108    fn transform_ctx(&self, ctx: &mut TransformCtx) {
109        ctx.for_each_fun_decl(|ctx, decl| {
110            self.log_before_body(ctx, &decl.item_meta.name, &decl.body);
111            self.transform_function(ctx, decl);
112        });
113    }
114
115    /// The name of the pass, used for debug logging. The default implementation uses the type
116    /// name.
117    fn name(&self) -> &str {
118        std::any::type_name::<Self>()
119    }
120
121    /// Log that the pass is about to be run on this body.
122    fn log_before_body(&self, ctx: &TransformCtx, name: &Name, body: &Body) {
123        let fmt_ctx = &ctx.into_fmt();
124        let body_str = body.to_string_with_ctx(fmt_ctx);
125        trace!(
126            "# About to run pass [{}] on `{}`:\n{}",
127            self.name(),
128            name.with_ctx(fmt_ctx),
129            body_str,
130        );
131    }
132}
133
134/// A pass that transforms the crate data.
135pub trait TransformPass: Sync {
136    /// Whether the pass should run.
137    fn should_run(&self, _options: &TranslateOptions) -> bool {
138        true
139    }
140
141    fn transform_ctx(&self, ctx: &mut TransformCtx);
142
143    /// The name of the pass, used for debug logging. The default implementation uses the type
144    /// name.
145    fn name(&self) -> &str {
146        std::any::type_name::<Self>()
147    }
148}
149
150impl TransformCtx {
151    pub(crate) fn has_errors(&self) -> bool {
152        self.errors.borrow().has_errors()
153    }
154
155    /// Span an error and register the error.
156    pub(crate) fn span_err(&self, span: Span, msg: &str, level: Level) -> Error {
157        self.errors
158            .borrow_mut()
159            .span_err(&self.translated, span, msg, level)
160    }
161
162    pub(crate) fn opacity_for_name(&self, name: &Name) -> ItemOpacity {
163        self.options.opacity_for_name(&self.translated, name)
164    }
165
166    pub(crate) fn with_def_id<F, T>(
167        &mut self,
168        def_id: impl Into<ItemId>,
169        def_id_is_local: bool,
170        f: F,
171    ) -> T
172    where
173        F: FnOnce(&mut Self) -> T,
174    {
175        let mut errors = self.errors.borrow_mut();
176        let current_def_id = errors.def_id.replace(def_id.into());
177        let current_def_id_is_local = mem::replace(&mut errors.def_id_is_local, def_id_is_local);
178        drop(errors); // important: release the refcell "lock"
179        let ret = f(self);
180        let mut errors = self.errors.borrow_mut();
181        errors.def_id = current_def_id;
182        errors.def_id_is_local = current_def_id_is_local;
183        ret
184    }
185
186    /// Mutably iterate over the bodies.
187    /// Warning: we replace each body with `Err(Opaque)` while inspecting it so we can keep access
188    /// to the rest of the crate.
189    pub(crate) fn for_each_body(&mut self, mut f: impl FnMut(&mut Self, &mut Body)) {
190        let fn_ids = self.translated.fun_decls.all_indices();
191        for id in fn_ids {
192            if let Some(decl) = self.translated.fun_decls.get_mut(id)
193                && decl.body.has_contents()
194            {
195                let mut body = mem::replace(&mut decl.body, Body::Opaque);
196                let fun_decl_id = decl.def_id;
197                let is_local = decl.item_meta.is_local;
198                self.with_def_id(fun_decl_id, is_local, |ctx| f(ctx, &mut body));
199                self.translated.fun_decls[id].body = body;
200            }
201        }
202    }
203
204    /// Mutably iterate over the function declarations.
205    /// Warning: each inspected fundecl becomes inaccessible from `ctx` during the course of this function.
206    pub(crate) fn for_each_fun_decl(&mut self, mut f: impl FnMut(&mut Self, &mut FunDecl)) {
207        let fn_ids = self.translated.fun_decls.all_indices();
208        for id in fn_ids {
209            if let Some(mut decl) = self.translated.fun_decls.remove(id) {
210                let fun_decl_id = decl.def_id;
211                let is_local = decl.item_meta.is_local;
212                self.with_def_id(fun_decl_id, is_local, |ctx| f(ctx, &mut decl));
213                self.translated.fun_decls.set_slot(id, decl);
214            }
215        }
216    }
217
218    /// Iterate mutably over all items, keeping access to `self`. To make this work, we move out
219    /// each item before iterating over it. Items added during traversal will not be iterated over.
220    pub fn for_each_item_mut(&mut self, mut f: impl for<'a> FnMut(&'a mut Self, ItemRefMut<'a>)) {
221        for id in self.translated.all_ids() {
222            if let Some(mut decl) = self.translated.remove_item_temporarily(id) {
223                f(self, decl.as_mut());
224                self.translated.set_item_slot(id, decl);
225            }
226        }
227    }
228}
229
230impl<'a> IntoFormatter for &'a TransformCtx {
231    type C = FmtCtx<'a>;
232
233    fn into_fmt(self) -> Self::C {
234        self.translated.into_fmt()
235    }
236}
237
238impl fmt::Display for TransformCtx {
239    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
240        self.translated.fmt(f)
241    }
242}
243
244/// A helper trait that captures common operations in body transformation.
245pub trait BodyTransformCtx: Sized {
246    fn get_crate(&self) -> &TranslatedCrate;
247    fn get_options(&self) -> &TranslateOptions;
248    fn get_params(&self) -> &GenericParams;
249    fn get_locals_mut(&mut self) -> &mut Locals;
250
251    fn insert_storage_live_stmt(&mut self, local: LocalId);
252    fn insert_storage_dead_stmt(&mut self, local: LocalId);
253    fn insert_assn_stmt(&mut self, place: Place, rvalue: Rvalue);
254
255    fn to_fmt(&self) -> FmtCtx<'_> {
256        self.get_crate().into_fmt()
257    }
258
259    /// Create a local & return the place pointing to it
260    fn fresh_var(&mut self, name: Option<String>, ty: Ty) -> Place {
261        let var = self.get_locals_mut().new_var(name, ty);
262        self.insert_storage_live_stmt(var.local_id().unwrap());
263        var
264    }
265
266    /// Assign an rvalue to a place, unless the rvalue is a move in which case we just use the
267    /// moved place.
268    fn rval_to_place(&mut self, rvalue: Rvalue, ty: Ty) -> Place {
269        if let Rvalue::Use(Operand::Move(place)) = rvalue {
270            place
271        } else {
272            let var = self.fresh_var(None, ty);
273            self.insert_assn_stmt(var.clone(), rvalue);
274            var
275        }
276    }
277
278    /// When `from_end` is true, we need to compute `len(p) - last_arg` instead of just using `last_arg`.
279    /// Otherwise, we simply return `last_arg`.
280    /// New local variables are created as needed.
281    ///
282    /// The `last_arg` is either the `offset` for `Index` or the `to` for `Subslice` for the projections.
283    fn compute_subslice_end_idx(
284        &mut self,
285        len_place: &Place,
286        last_arg: Operand,
287        from_end: bool,
288    ) -> Operand {
289        if from_end {
290            // `storage_live(len_var)`
291            // `len_var = len(p)`
292            let len_var = self.fresh_var(None, Ty::mk_usize());
293            let len = match len_place.ty().kind() {
294                TyKind::Array(_, len) => Some(len.clone()),
295                TyKind::Slice(_) => None,
296                _ => panic!(
297                    "called `compute_subslice_end_idx` on something that isn't an array or slice: {:?}",
298                    len_place.ty()
299                ),
300            };
301            self.insert_assn_stmt(
302                len_var.clone(),
303                Rvalue::Len(len_place.clone(), len_place.ty().clone(), len),
304            );
305
306            // `storage_live(index_var)`
307            // `index_var = len_var - last_arg`
308            // `storage_dead(len_var)`
309            let index_var = self.fresh_var(None, Ty::mk_usize());
310            self.insert_assn_stmt(
311                index_var.clone(),
312                Rvalue::BinaryOp(
313                    BinOp::Sub(OverflowMode::UB),
314                    Operand::Copy(len_var.clone()),
315                    last_arg,
316                ),
317            );
318            self.insert_storage_dead_stmt(len_var.local_id().unwrap());
319            Operand::Copy(index_var)
320        } else {
321            last_arg
322        }
323    }
324
325    fn is_sized_type_var(&mut self, ty: &Ty) -> bool {
326        match ty.kind() {
327            TyKind::TypeVar(..) => {
328                if self.get_options().hide_marker_traits {
329                    // If we're hiding `Sized`, let's consider everything to be sized.
330                    return true;
331                }
332                let params = self.get_params();
333                for clause in &params.trait_clauses {
334                    let tref = clause.trait_.clone().erase();
335                    // Check if it is `Sized<T>`
336                    if tref.generics.types[0] == *ty
337                        && self
338                            .get_crate()
339                            .trait_decls
340                            .get(tref.id)
341                            .and_then(|decl| decl.item_meta.lang_item.clone())
342                            == Some("sized".into())
343                    {
344                        return true;
345                    }
346                }
347                false
348            }
349            _ => false,
350        }
351    }
352
353    /// Emit statements that compute the metadata of the given place. Returns an operand containing the
354    /// metadata value.
355    ///
356    /// E.g., for:
357    /// ```ignore
358    /// let x = &(*ptr).field;
359    /// ```
360    /// if `(*ptr).field` is a DST like `[i32]`, this will get the metadata from the appropriate
361    /// pointer:
362    /// ```ignore
363    /// let len = ptr.metadata;
364    /// ```
365    /// and return `Operand::Move(len)`.
366    ///
367    fn compute_place_metadata(&mut self, place: &Place) -> Operand {
368        /// No metadata. We use the `unit_metadata` global to avoid having to define unit locals
369        /// everywhere.
370        fn no_metadata<T: BodyTransformCtx>(ctx: &T) -> Operand {
371            let unit_meta = ctx.get_crate().unit_metadata.clone().unwrap();
372            Operand::Copy(Place::new_global(unit_meta, Ty::mk_unit()))
373        }
374
375        /// Compute the metadata for a place. Return `None` if the place has no metadata.
376        fn compute_place_metadata_inner<T: BodyTransformCtx>(
377            ctx: &mut T,
378            place: &Place,
379            metadata_ty: &Ty,
380        ) -> Option<Operand> {
381            let (subplace, proj) = place.as_projection()?;
382            match proj {
383                // The outermost deref we encountered gives us the metadata of the place.
384                ProjectionElem::Deref => {
385                    let metadata_place = subplace
386                        .clone()
387                        .project(ProjectionElem::PtrMetadata, metadata_ty.clone());
388                    Some(Operand::Copy(metadata_place))
389                }
390                ProjectionElem::Field { .. } => {
391                    compute_place_metadata_inner(ctx, subplace, metadata_ty)
392                }
393                // Indexing for array & slice will only result in sized types, hence no metadata
394                ProjectionElem::Index { .. } => None,
395                // Ptr metadata is always sized.
396                ProjectionElem::PtrMetadata => None,
397                // Subslice must have metadata length, compute the metadata here as `to` - `from`
398                ProjectionElem::Subslice { from, to, from_end } => {
399                    let to_idx = ctx.compute_subslice_end_idx(subplace, *to.clone(), *from_end);
400                    let diff_place = ctx.fresh_var(None, Ty::mk_usize());
401                    ctx.insert_assn_stmt(
402                        diff_place.clone(),
403                        // Overflow is UB and should have been prevented by a bound check beforehand.
404                        Rvalue::BinaryOp(BinOp::Sub(OverflowMode::UB), to_idx, *from.clone()),
405                    );
406                    Some(Operand::Copy(diff_place))
407                }
408            }
409        }
410        trace!(
411            "getting ptr metadata for place: {}",
412            place.with_ctx(&self.to_fmt())
413        );
414        let metadata_ty = place.ty().get_ptr_metadata(self.get_crate()).into_type();
415        if metadata_ty.is_unit()
416            || matches!(metadata_ty.kind(), TyKind::PtrMetadata(ty) if self.is_sized_type_var(ty))
417        {
418            // If the type var is known to be `Sized`, then no metadata is needed
419            return no_metadata(self);
420        }
421        trace!(
422            "computed metadata type: {}",
423            metadata_ty.with_ctx(&self.to_fmt())
424        );
425        compute_place_metadata_inner(self, place, &metadata_ty).unwrap_or_else(|| no_metadata(self))
426    }
427
428    /// Create a `&` borrow of the place.
429    fn borrow(&mut self, place: Place, kind: BorrowKind) -> Rvalue {
430        let ptr_metadata = self.compute_place_metadata(&place);
431        Rvalue::Ref {
432            place,
433            kind,
434            ptr_metadata,
435        }
436    }
437    /// Create a `&raw` borrow of the place.
438    fn raw_borrow(&mut self, place: Place, kind: RefKind) -> Rvalue {
439        let ptr_metadata = self.compute_place_metadata(&place);
440        Rvalue::RawPtr {
441            place,
442            kind,
443            ptr_metadata,
444        }
445    }
446
447    /// Store a `&` borrow of the place into a new place.
448    fn borrow_to_new_var(&mut self, place: Place, kind: BorrowKind, name: Option<String>) -> Place {
449        let ref_ty = TyKind::Ref(Region::Erased, place.ty().clone(), kind.into()).into_ty();
450        let target_place = self.fresh_var(name, ref_ty);
451        let rvalue = self.borrow(place, kind);
452        self.insert_assn_stmt(target_place.clone(), rvalue);
453        target_place
454    }
455    /// Store a `&raw` borrow of the place into a new place.
456    fn raw_borrow_to_new_var(
457        &mut self,
458        place: Place,
459        kind: RefKind,
460        name: Option<String>,
461    ) -> Place {
462        let ref_ty = TyKind::RawPtr(place.ty().clone(), kind).into_ty();
463        let target_place = self.fresh_var(name, ref_ty);
464        let rvalue = self.raw_borrow(place, kind);
465        self.insert_assn_stmt(target_place.clone(), rvalue);
466        target_place
467    }
468}
469
470pub struct UllbcStatementTransformCtx<'a> {
471    pub ctx: &'a mut TransformCtx,
472    pub params: &'a GenericParams,
473    pub locals: &'a mut Locals,
474    /// Span of the statement being explored
475    pub span: Span,
476    /// Statements to prepend to the statement currently being explored.
477    pub statements: Vec<ullbc_ast::Statement>,
478}
479
480impl BodyTransformCtx for UllbcStatementTransformCtx<'_> {
481    fn get_crate(&self) -> &TranslatedCrate {
482        &self.ctx.translated
483    }
484    fn get_options(&self) -> &TranslateOptions {
485        &self.ctx.options
486    }
487    fn get_params(&self) -> &GenericParams {
488        self.params
489    }
490    fn get_locals_mut(&mut self) -> &mut Locals {
491        self.locals
492    }
493
494    fn insert_storage_live_stmt(&mut self, local: LocalId) {
495        self.statements.push(ullbc_ast::Statement::new(
496            self.span,
497            ullbc_ast::StatementKind::StorageLive(local),
498        ));
499    }
500
501    fn insert_assn_stmt(&mut self, place: Place, rvalue: Rvalue) {
502        self.statements.push(ullbc_ast::Statement::new(
503            self.span,
504            ullbc_ast::StatementKind::Assign(place, rvalue),
505        ));
506    }
507
508    fn insert_storage_dead_stmt(&mut self, local: LocalId) {
509        self.statements.push(ullbc_ast::Statement::new(
510            self.span,
511            ullbc_ast::StatementKind::StorageDead(local),
512        ));
513    }
514}
515
516pub struct LlbcStatementTransformCtx<'a> {
517    pub ctx: &'a mut TransformCtx,
518    pub params: &'a GenericParams,
519    pub locals: &'a mut Locals,
520    /// Span of the statement being explored
521    pub span: Span,
522    /// Statements to prepend to the statement currently being explored.
523    pub statements: Vec<llbc_ast::Statement>,
524}
525
526impl BodyTransformCtx for LlbcStatementTransformCtx<'_> {
527    fn get_crate(&self) -> &TranslatedCrate {
528        &self.ctx.translated
529    }
530    fn get_options(&self) -> &TranslateOptions {
531        &self.ctx.options
532    }
533    fn get_params(&self) -> &GenericParams {
534        self.params
535    }
536    fn get_locals_mut(&mut self) -> &mut Locals {
537        self.locals
538    }
539
540    fn insert_storage_live_stmt(&mut self, local: LocalId) {
541        self.statements.push(llbc_ast::Statement::new(
542            self.span,
543            llbc_ast::StatementKind::StorageLive(local),
544        ));
545    }
546
547    fn insert_assn_stmt(&mut self, place: Place, rvalue: Rvalue) {
548        self.statements.push(llbc_ast::Statement::new(
549            self.span,
550            llbc_ast::StatementKind::Assign(place, rvalue),
551        ));
552    }
553
554    fn insert_storage_dead_stmt(&mut self, local: LocalId) {
555        self.statements.push(llbc_ast::Statement::new(
556            self.span,
557            llbc_ast::StatementKind::StorageDead(local),
558        ));
559    }
560}
561
562impl FunDecl {
563    pub fn transform_ullbc_statements(
564        &mut self,
565        ctx: &mut TransformCtx,
566        mut f: impl FnMut(&mut UllbcStatementTransformCtx, &mut ullbc_ast::Statement),
567    ) {
568        if let Some(body) = self.body.as_unstructured_mut() {
569            let mut ctx = UllbcStatementTransformCtx {
570                ctx,
571                params: &self.generics,
572                locals: &mut body.locals,
573                span: self.item_meta.span,
574                statements: Vec::new(),
575            };
576            body.body.iter_mut().for_each(|block| {
577                ctx.statements = Vec::with_capacity(block.statements.len());
578                for mut st in mem::take(&mut block.statements) {
579                    ctx.span = st.span;
580                    f(&mut ctx, &mut st);
581                    ctx.statements.push(st);
582                }
583                block.statements = mem::take(&mut ctx.statements);
584            });
585        }
586    }
587
588    pub fn transform_ullbc_terminators(
589        &mut self,
590        ctx: &mut TransformCtx,
591        mut f: impl FnMut(&mut UllbcStatementTransformCtx, &mut ullbc_ast::Terminator),
592    ) {
593        if let Some(body) = self.body.as_unstructured_mut() {
594            let mut ctx = UllbcStatementTransformCtx {
595                ctx,
596                params: &self.generics,
597                locals: &mut body.locals,
598                span: self.item_meta.span,
599                statements: Vec::new(),
600            };
601            body.body.iter_mut().for_each(|block| {
602                ctx.span = block.terminator.span;
603                ctx.statements = mem::take(&mut block.statements);
604                f(&mut ctx, &mut block.terminator);
605                block.statements = mem::take(&mut ctx.statements);
606            });
607        }
608    }
609
610    pub fn transform_ullbc_operands(
611        &mut self,
612        ctx: &mut TransformCtx,
613        mut f: impl FnMut(&mut UllbcStatementTransformCtx, &mut Operand),
614    ) {
615        self.transform_ullbc_statements(ctx, |ctx, st| {
616            st.kind.dyn_visit_in_body_mut(|op: &mut Operand| f(ctx, op));
617        });
618        self.transform_ullbc_terminators(ctx, |ctx, st| {
619            st.kind.dyn_visit_in_body_mut(|op: &mut Operand| f(ctx, op));
620        });
621    }
622
623    pub fn transform_llbc_statements(
624        &mut self,
625        ctx: &mut TransformCtx,
626        mut f: impl FnMut(&mut LlbcStatementTransformCtx, &mut llbc_ast::Statement),
627    ) {
628        if let Some(body) = self.body.as_structured_mut() {
629            let mut ctx = LlbcStatementTransformCtx {
630                ctx,
631                locals: &mut body.locals,
632                statements: Vec::new(),
633                span: self.item_meta.span,
634                params: &self.generics,
635            };
636            body.body.visit_blocks_bwd(|block: &mut llbc_ast::Block| {
637                ctx.statements = Vec::with_capacity(block.statements.len());
638                for mut st in mem::take(&mut block.statements) {
639                    ctx.span = st.span;
640                    f(&mut ctx, &mut st);
641                    ctx.statements.push(st);
642                }
643                block.statements = mem::take(&mut ctx.statements)
644            })
645        }
646    }
647}
charon_lib/transform/ctx.rs

charon_lib/transform/
ctx.rs
