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    /// Transform a body.
25    fn transform_body(&self, _ctx: &mut TransformCtx, _body: &mut ullbc_ast::ExprBody) {}
26
27    /// Transform a function declaration. This forwards to `transform_body` by default.
28    fn transform_function(&self, ctx: &mut TransformCtx, decl: &mut FunDecl) {
29        if let Some(body) = decl.body.as_unstructured_mut() {
30            self.transform_body(ctx, body)
31        }
32    }
33
34    /// Transform the given context. This forwards to the other methods by default.
35    fn transform_ctx(&self, ctx: &mut TransformCtx) {
36        ctx.for_each_fun_decl(|ctx, decl| {
37            self.log_before_body(ctx, &decl.item_meta.name, &decl.body);
38            self.transform_function(ctx, decl);
39        });
40    }
41
42    /// The name of the pass, used for debug logging. The default implementation uses the type
43    /// name.
44    fn name(&self) -> &str {
45        std::any::type_name::<Self>()
46    }
47
48    /// Log that the pass is about to be run on this body.
49    fn log_before_body(&self, ctx: &TransformCtx, name: &Name, body: &Body) {
50        let fmt_ctx = &ctx.into_fmt();
51        let body_str = body.to_string_with_ctx(fmt_ctx);
52        trace!(
53            "# About to run pass [{}] on `{}`:\n{}",
54            self.name(),
55            name.with_ctx(fmt_ctx),
56            body_str,
57        );
58    }
59}
60
61/// A pass that modifies llbc bodies.
62pub trait LlbcPass: Sync {
63    /// Transform a body.
64    fn transform_body(&self, _ctx: &mut TransformCtx, _body: &mut llbc_ast::ExprBody) {}
65
66    /// Transform a function declaration. This forwards to `transform_body` by default.
67    fn transform_function(&self, ctx: &mut TransformCtx, decl: &mut FunDecl) {
68        if let Some(body) = decl.body.as_structured_mut() {
69            self.transform_body(ctx, body)
70        }
71    }
72
73    /// Transform the given context. This forwards to the other methods by default.
74    fn transform_ctx(&self, ctx: &mut TransformCtx) {
75        ctx.for_each_fun_decl(|ctx, decl| {
76            self.log_before_body(ctx, &decl.item_meta.name, &decl.body);
77            self.transform_function(ctx, decl);
78        });
79    }
80
81    /// The name of the pass, used for debug logging. The default implementation uses the type
82    /// name.
83    fn name(&self) -> &str {
84        std::any::type_name::<Self>()
85    }
86
87    /// Log that the pass is about to be run on this body.
88    fn log_before_body(&self, ctx: &TransformCtx, name: &Name, body: &Body) {
89        let fmt_ctx = &ctx.into_fmt();
90        let body_str = body.to_string_with_ctx(fmt_ctx);
91        trace!(
92            "# About to run pass [{}] on `{}`:\n{}",
93            self.name(),
94            name.with_ctx(fmt_ctx),
95            body_str,
96        );
97    }
98}
99
100/// A pass that transforms the crate data.
101pub trait TransformPass: Sync {
102    fn transform_ctx(&self, ctx: &mut TransformCtx);
103
104    /// The name of the pass, used for debug logging. The default implementation uses the type
105    /// name.
106    fn name(&self) -> &str {
107        std::any::type_name::<Self>()
108    }
109}
110
111impl<'ctx> TransformCtx {
112    pub(crate) fn has_errors(&self) -> bool {
113        self.errors.borrow().has_errors()
114    }
115
116    /// Span an error and register the error.
117    pub(crate) fn span_err(&self, span: Span, msg: &str, level: Level) -> Error {
118        self.errors
119            .borrow_mut()
120            .span_err(&self.translated, span, msg, level)
121    }
122
123    pub(crate) fn opacity_for_name(&self, name: &Name) -> ItemOpacity {
124        self.options.opacity_for_name(&self.translated, name)
125    }
126
127    pub(crate) fn with_def_id<F, T>(
128        &mut self,
129        def_id: impl Into<ItemId>,
130        def_id_is_local: bool,
131        f: F,
132    ) -> T
133    where
134        F: FnOnce(&mut Self) -> T,
135    {
136        let mut errors = self.errors.borrow_mut();
137        let current_def_id = mem::replace(&mut errors.def_id, Some(def_id.into()));
138        let current_def_id_is_local = mem::replace(&mut errors.def_id_is_local, def_id_is_local);
139        drop(errors); // important: release the refcell "lock"
140        let ret = f(self);
141        let mut errors = self.errors.borrow_mut();
142        errors.def_id = current_def_id;
143        errors.def_id_is_local = current_def_id_is_local;
144        ret
145    }
146
147    /// Mutably iterate over the bodies.
148    /// Warning: we replace each body with `Err(Opaque)` while inspecting it so we can keep access
149    /// to the rest of the crate.
150    pub(crate) fn for_each_body(&mut self, mut f: impl FnMut(&mut Self, &mut Body)) {
151        let fn_ids = self.translated.fun_decls.all_indices();
152        for id in fn_ids {
153            if let Some(decl) = self.translated.fun_decls.get_mut(id) {
154                if decl.body.has_contents() {
155                    let mut body = mem::replace(&mut decl.body, Body::Opaque);
156                    let fun_decl_id = decl.def_id;
157                    let is_local = decl.item_meta.is_local;
158                    self.with_def_id(fun_decl_id, is_local, |ctx| f(ctx, &mut body));
159                    self.translated.fun_decls[id].body = body;
160                }
161            }
162        }
163    }
164
165    /// Mutably iterate over the function declarations.
166    /// Warning: each inspected fundecl becomes inaccessible from `ctx` during the course of this function.
167    pub(crate) fn for_each_fun_decl(&mut self, mut f: impl FnMut(&mut Self, &mut FunDecl)) {
168        let fn_ids = self.translated.fun_decls.all_indices();
169        for id in fn_ids {
170            if let Some(mut decl) = self.translated.fun_decls.remove(id) {
171                let fun_decl_id = decl.def_id;
172                let is_local = decl.item_meta.is_local;
173                self.with_def_id(fun_decl_id, is_local, |ctx| f(ctx, &mut decl));
174                self.translated.fun_decls.set_slot(id, decl);
175            }
176        }
177    }
178
179    /// Iterate mutably over all items, keeping access to `self`. To make this work, we move out
180    /// each item before iterating over it. Items added during traversal will not be iterated over.
181    pub fn for_each_item_mut(&mut self, mut f: impl for<'a> FnMut(&'a mut Self, ItemRefMut<'a>)) {
182        for id in self.translated.all_ids() {
183            if let Some(mut decl) = self.translated.remove_item(id) {
184                f(self, decl.as_mut());
185                self.translated.set_item_slot(id, decl);
186            }
187        }
188    }
189}
190
191impl<'a> IntoFormatter for &'a TransformCtx {
192    type C = FmtCtx<'a>;
193
194    fn into_fmt(self) -> Self::C {
195        self.translated.into_fmt()
196    }
197}
198
199impl fmt::Display for TransformCtx {
200    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
201        self.translated.fmt(f)
202    }
203}
204
205/// A helper trait that captures the usual operation in body transformation.
206pub trait BodyTransformCtx: Sized {
207    fn get_ctx(&self) -> &TransformCtx;
208    fn get_params(&self) -> &GenericParams;
209    fn get_locals_mut(&mut self) -> &mut Locals;
210
211    fn insert_storage_live_stmt(&mut self, local: LocalId);
212    fn insert_storage_dead_stmt(&mut self, local: LocalId);
213    fn insert_assn_stmt(&mut self, place: Place, rvalue: Rvalue);
214
215    /// Create a local & return the place pointing to it
216    fn fresh_var(&mut self, name: Option<String>, ty: Ty) -> Place {
217        let var = self.get_locals_mut().new_var(name, ty);
218        self.insert_storage_live_stmt(var.local_id().unwrap());
219        var
220    }
221
222    /// When `from_end` is true, we need to compute `len(p) - last_arg` instead of just using `last_arg`.
223    /// Otherwise, we simply return `last_arg`.
224    /// New local variables are created as needed.
225    ///
226    /// The `last_arg` is either the `offset` for `Index` or the `to` for `Subslice` for the projections.
227    fn compute_subslice_end_idx(
228        &mut self,
229        len_place: &Place,
230        last_arg: Operand,
231        from_end: bool,
232    ) -> Operand {
233        if from_end {
234            // `storage_live(len_var)`
235            // `len_var = len(p)`
236            let len_var = self.fresh_var(None, Ty::mk_usize());
237            self.insert_assn_stmt(
238                len_var.clone(),
239                Rvalue::Len(
240                    len_place.clone(),
241                    len_place.ty().clone(),
242                    len_place
243                        .ty()
244                        .as_adt()
245                        .unwrap()
246                        .generics
247                        .const_generics
248                        .get(0.into())
249                        .cloned(),
250                ),
251            );
252
253            // `storage_live(index_var)`
254            // `index_var = len_var - last_arg`
255            // `storage_dead(len_var)`
256            let index_var = self.fresh_var(None, Ty::mk_usize());
257            self.insert_assn_stmt(
258                index_var.clone(),
259                Rvalue::BinaryOp(
260                    BinOp::Sub(OverflowMode::UB),
261                    Operand::Copy(len_var.clone()),
262                    last_arg,
263                ),
264            );
265            self.insert_storage_dead_stmt(len_var.local_id().unwrap());
266            Operand::Copy(index_var)
267        } else {
268            last_arg
269        }
270    }
271
272    fn is_sized_type_var(&mut self, ty: &Ty) -> bool {
273        match ty.kind() {
274            TyKind::TypeVar(..) => {
275                if self.get_ctx().options.hide_marker_traits {
276                    // If we're hiding `Sized`, let's consider everything to be sized.
277                    return true;
278                }
279                let params = self.get_params();
280                for clause in &params.trait_clauses {
281                    let tref = clause.trait_.clone().erase();
282                    // Check if it is `Sized<T>`
283                    if tref.generics.types[0] == *ty
284                        && self
285                            .get_ctx()
286                            .translated
287                            .trait_decls
288                            .get(tref.id)
289                            .and_then(|decl| decl.item_meta.lang_item.clone())
290                            == Some("sized".into())
291                    {
292                        return true;
293                    }
294                }
295                false
296            }
297            _ => false,
298        }
299    }
300
301    /// Emit statements that compute the metadata of the given place. Returns an operand containing the
302    /// metadata value.
303    fn compute_place_metadata(&mut self, place: &Place) -> Operand {
304        /// No metadata. We use the `unit_metadata` global to avoid having to define unit locals
305        /// everywhere.
306        fn no_metadata<T: BodyTransformCtx>(ctx: &T) -> Operand {
307            let unit_meta = ctx.get_ctx().translated.unit_metadata.clone().unwrap();
308            Operand::Copy(Place::new_global(unit_meta, Ty::mk_unit()))
309        }
310
311        /// Compute the metadata for a place. Return `None` if the place has no metadata.
312        fn compute_place_metadata_inner<T: BodyTransformCtx>(
313            ctx: &mut T,
314            place: &Place,
315            metadata_ty: &Ty,
316        ) -> Option<Operand> {
317            let (subplace, proj) = place.as_projection()?;
318            match proj {
319                // The outermost deref we encountered gives us the metadata of the place.
320                ProjectionElem::Deref => {
321                    let metadata_place = subplace
322                        .clone()
323                        .project(ProjectionElem::PtrMetadata, metadata_ty.clone());
324                    Some(Operand::Copy(metadata_place))
325                }
326                ProjectionElem::Field { .. } => {
327                    compute_place_metadata_inner(ctx, subplace, metadata_ty)
328                }
329                // Indexing for array & slice will only result in sized types, hence no metadata
330                ProjectionElem::Index { .. } => None,
331                // Ptr metadata is always sized.
332                ProjectionElem::PtrMetadata { .. } => None,
333                // Subslice must have metadata length, compute the metadata here as `to` - `from`
334                ProjectionElem::Subslice { from, to, from_end } => {
335                    let to_idx = ctx.compute_subslice_end_idx(subplace, *to.clone(), *from_end);
336                    let diff_place = ctx.fresh_var(None, Ty::mk_usize());
337                    ctx.insert_assn_stmt(
338                        diff_place.clone(),
339                        // Overflow is UB and should have been prevented by a bound check beforehand.
340                        Rvalue::BinaryOp(BinOp::Sub(OverflowMode::UB), to_idx, *from.clone()),
341                    );
342                    Some(Operand::Copy(diff_place))
343                }
344            }
345        }
346        trace!(
347            "getting ptr metadata for place: {}",
348            place.with_ctx(&self.get_ctx().into_fmt())
349        );
350        let metadata_ty = place
351            .ty()
352            .get_ptr_metadata(&self.get_ctx().translated)
353            .into_type();
354        if metadata_ty.is_unit()
355            || matches!(metadata_ty.kind(), TyKind::PtrMetadata(ty) if self.is_sized_type_var(ty))
356        {
357            // If the type var is known to be `Sized`, then no metadata is needed
358            return no_metadata(self);
359        }
360        trace!(
361            "computed metadata type: {}",
362            metadata_ty.with_ctx(&self.get_ctx().into_fmt())
363        );
364        compute_place_metadata_inner(self, place, &metadata_ty).unwrap_or_else(|| no_metadata(self))
365    }
366}
367
368pub struct UllbcStatementTransformCtx<'a> {
369    pub ctx: &'a mut TransformCtx,
370    pub params: &'a GenericParams,
371    pub locals: &'a mut Locals,
372    /// Span of the statement being explored
373    pub span: Span,
374    /// Statements to prepend to the statement currently being explored.
375    pub statements: Vec<ullbc_ast::Statement>,
376}
377
378impl BodyTransformCtx for UllbcStatementTransformCtx<'_> {
379    fn get_ctx(&self) -> &TransformCtx {
380        self.ctx
381    }
382    fn get_params(&self) -> &GenericParams {
383        self.params
384    }
385    fn get_locals_mut(&mut self) -> &mut Locals {
386        self.locals
387    }
388
389    fn insert_storage_live_stmt(&mut self, local: LocalId) {
390        self.statements.push(ullbc_ast::Statement::new(
391            self.span,
392            ullbc_ast::StatementKind::StorageLive(local),
393        ));
394    }
395
396    fn insert_assn_stmt(&mut self, place: Place, rvalue: Rvalue) {
397        self.statements.push(ullbc_ast::Statement::new(
398            self.span,
399            ullbc_ast::StatementKind::Assign(place, rvalue),
400        ));
401    }
402
403    fn insert_storage_dead_stmt(&mut self, local: LocalId) {
404        self.statements.push(ullbc_ast::Statement::new(
405            self.span,
406            ullbc_ast::StatementKind::StorageDead(local),
407        ));
408    }
409}
410
411impl FunDecl {
412    pub fn transform_ullbc_terminators(
413        &mut self,
414        ctx: &mut TransformCtx,
415        mut f: impl FnMut(&mut UllbcStatementTransformCtx, &mut ullbc_ast::Terminator),
416    ) {
417        if let Some(body) = self.body.as_unstructured_mut() {
418            let params = &self.signature.generics;
419            body.body.iter_mut().for_each(|block| {
420                let span = block.terminator.span;
421                let mut ctx = UllbcStatementTransformCtx {
422                    ctx,
423                    params,
424                    locals: &mut body.locals,
425                    span,
426                    statements: std::mem::take(&mut block.statements),
427                };
428                f(&mut ctx, &mut block.terminator);
429                block.statements = ctx.statements;
430            });
431        }
432    }
433
434    pub fn transform_ullbc_statements(
435        &mut self,
436        ctx: &mut TransformCtx,
437        mut f: impl FnMut(&mut UllbcStatementTransformCtx, &mut ullbc_ast::Statement),
438    ) {
439        if let Some(body) = self.body.as_unstructured_mut() {
440            let params = &self.signature.generics;
441            body.body.iter_mut().for_each(|block| {
442                block.transform(|st: &mut ullbc_ast::Statement| {
443                    let mut ctx = UllbcStatementTransformCtx {
444                        ctx,
445                        params,
446                        locals: &mut body.locals,
447                        span: st.span,
448                        statements: Vec::new(),
449                    };
450                    f(&mut ctx, st);
451                    ctx.statements
452                });
453            });
454        }
455    }
456}
charon_lib/transform/ctx.rs

charon_lib/transform/
ctx.rs
