Skip to main content

charon_lib/transform/simplify_output/
builtins_to_function_calls.rs

1//! Desugar built-in operations and array/slice indexing to standard library function calls.
2
3use std::collections::{HashMap, HashSet};
4
5use crate::llbc_ast::*;
6use crate::name_matcher::NamePattern;
7use crate::transform::ctx::{BodyTransformCtx, LlbcStatementTransformCtx};
8use crate::transform::{CowBox, TransformCtx};
9use derive_generic_visitor::*;
10use itertools::Itertools;
11
12use crate::transform::ctx::LlbcPass;
13
14fn mk_fn_ptr(ctx: &TransformCtx, id: ItemId, mut generics: GenericArgs) -> FnPtr {
15    if ctx.options.add_destruct_bounds
16        && let Some(item) = ctx.translated.get_item(id)
17    {
18        // Charon adds `Destruct` as the last trait clause of every generic item.
19        let trait_decl_ref = item
20            .generic_params()
21            .trait_clauses
22            .last()
23            .unwrap()
24            .trait_
25            .clone()
26            .substitute(&generics);
27        let kind = TraitRefKind::BuiltinOrAuto {
28            builtin_data: BuiltinImplData::UntrackedDestruct,
29            parent_trait_refs: Default::default(),
30            types: Default::default(),
31            vtable: None,
32        };
33        generics
34            .trait_refs
35            .push(PolyTraitRef::new(kind, trait_decl_ref));
36    }
37    let fun_id = *id.as_fun().unwrap();
38    FnPtr::new(FnPtrKind::Fun(fun_id), generics)
39}
40
41/// Instantiate the trait impl that provides the given method.
42fn method_impl_trait_ref(
43    ctx: &TransformCtx,
44    id: ItemId,
45    fun_generics: &GenericArgs,
46) -> Option<TraitRef> {
47    let fun_id = *id.as_fun()?;
48    let fun = ctx.translated.fun_decls.get(fun_id)?;
49    let FunSource::TraitImpl { impl_ref, .. } = &fun.src else {
50        return None;
51    };
52    let impl_ref = impl_ref.clone().substitute(fun_generics);
53    let trait_impl = ctx.translated.trait_impls.get(impl_ref.id)?;
54    let trait_decl_ref = trait_impl.impl_trait.clone().substitute(&impl_ref.generics);
55    Some(TraitRef::new(
56        TraitRefKind::TraitImpl(impl_ref),
57        trait_decl_ref,
58    ))
59}
60
61fn index_method_types(
62    params: &GenericParams,
63    elem_ty: &Ty,
64    index_ty: &Ty,
65    output_ty: &Ty,
66) -> Option<IndexVec<TypeVarId, Ty>> {
67    let mut types: IndexVec<TypeVarId, Ty> =
68        [elem_ty.clone(), index_ty.clone()].into_iter().collect();
69    match params.types.len() {
70        // With `--lift-associated-types`, `Index::Output` is an explicit type parameter.
71        3 => {
72            types.push(output_ty.clone());
73        }
74        2 => {}
75        _ => return None,
76    }
77    Some(types)
78}
79
80fn transform_operation(std_items: &Transform, ctx: &TransformCtx, statement: &mut Statement) {
81    match &statement.kind {
82        // Transform the ArrayToSlice unop.
83        StatementKind::Assign(
84            place,
85            Rvalue::UnaryOp(
86                UnOp::Cast(CastKind::Unsize(tgt_ty, UnsizingMetadata::Length(_), _)),
87                operand,
88            ),
89        ) => {
90            if let (TyKind::Ref(_, src_ty, src_kind), TyKind::Ref(_, tgt_ty, tgt_kind)) =
91                (operand.ty().kind(), tgt_ty.kind())
92                && let TyKind::Array(elem_ty, len, elem_ty_is_sized) = src_ty.kind()
93                && let TyKind::Slice(..) = tgt_ty.kind()
94            {
95                // In MIR terminology, we go from &[T; l] to &[T] which means we
96                // effectively "unsize" the type, as `l` no longer appears in the
97                // destination type. At runtime, the converse happens: the length
98                // materializes into the fat pointer.
99                assert!(src_kind == tgt_kind);
100                // We could avoid the clone operations below if we take the content of
101                // the statement. In practice, this shouldn't have much impact.
102                let item = match src_kind {
103                    RefKind::Shared => StdItem::ArrayAsSlice,
104                    RefKind::Mut => StdItem::ArrayAsMutSlice,
105                };
106                let Some(&fun_id) = std_items.item_map.get(&item) else {
107                    return;
108                };
109                let generics = GenericArgs::new(
110                    [Region::Erased].into(),
111                    [elem_ty.clone()].into(),
112                    [len.clone()].into(),
113                    elem_ty_is_sized
114                        .iter()
115                        .cloned()
116                        .map(PolyTraitRef::empty)
117                        .collect(),
118                );
119                statement.kind = StatementKind::Call {
120                    call: Call {
121                        func: FnOperand::Regular(mk_fn_ptr(ctx, fun_id, generics)),
122                        args: vec![operand.clone()],
123                        safety: CallSafety::Inherit,
124                    },
125                    dest: place.clone(),
126                    on_unwind: Block::new_unreachable(statement.span),
127                };
128            }
129        }
130        // Transform the array aggregates to function calls.
131        StatementKind::Assign(
132            place,
133            Rvalue::Repeat {
134                operand,
135                count,
136                elem_is_sized,
137                elem_is_copy,
138            },
139        ) => {
140            // We could avoid the clone operations below if we take the content of
141            // the statement. In practice, this shouldn't have much impact.
142            let Some(&fun_id) = std_items.item_map.get(&StdItem::ArrayRepeat) else {
143                return;
144            };
145            // `Copy`'s explicit `Clone` supertrait follows its optional implicit marker clause.
146            // `array::repeat` has the corresponding `Clone` bound at the same position.
147            let clone_clause_id = TraitClauseId::new(usize::from(elem_is_sized.is_some()));
148            let Some(ty_is_clone) = elem_is_copy
149                .clone()
150                .project_parent_clause(&ctx.translated, clone_clause_id)
151            else {
152                return;
153            };
154            let generics = GenericArgs::new(
155                [].into(),
156                [operand.ty().clone()].into(),
157                [count.clone()].into(),
158                elem_is_sized
159                    .iter()
160                    .cloned()
161                    .map(PolyTraitRef::empty)
162                    .chain([ty_is_clone])
163                    .collect(),
164            );
165            statement.kind = StatementKind::Call {
166                call: Call {
167                    func: FnOperand::Regular(mk_fn_ptr(ctx, fun_id, generics)),
168                    args: vec![operand.clone()],
169                    safety: CallSafety::Inherit,
170                },
171                dest: place.clone(),
172                on_unwind: Block::new_unreachable(statement.span),
173            };
174        }
175        _ => {}
176    }
177}
178
179/// We replace some place constructors with function calls. To do that, we explore all the places
180/// in a body and deconstruct a given place access into intermediate assignments.
181///
182/// We accumulate the new assignments as statements in the visitor, and at the end we insert these
183/// statements before the one that was just explored.
184#[derive(Visitor)]
185struct IndexVisitor<'a, 'b> {
186    ctx: &'b mut LlbcStatementTransformCtx<'a>,
187    std_items: &'b Transform,
188    // When we visit a place, we need to know if it is being accessed mutably or not. Whenever we
189    // visit something that contains a place we push the relevant mutability on this stack.
190    // Unfortunately this requires us to be very careful to catch all the cases where we see
191    // places.
192    place_mutability_stack: Vec<bool>,
193}
194
195impl<'a, 'b> IndexVisitor<'a, 'b> {
196    /// transform `place: subplace[i]` into indexing function calls for `subplace` and `i`
197    fn transform_place(&mut self, mut_access: bool, place: &mut Place) {
198        use ProjectionElem::*;
199        // This function is naturally called recusively, so `subplace` cannot be another `Index` or `Subslice`.
200        // Hence, `subplace`, if still projecting, must be either a `Deref` or a `Field`.
201        let Some((subplace, pe @ (Index { .. } | Subslice { .. }))) = place.as_projection() else {
202            return;
203        };
204
205        let (ty, len, ty_is_sized) = match subplace.ty.kind() {
206            TyKind::Array(ty, len, ty_is_sized) => (ty.clone(), Some(len.clone()), ty_is_sized),
207            TyKind::Slice(ty, ty_is_sized) => (ty.clone(), None, ty_is_sized),
208            _ => unreachable!("Indexing can only be done on arrays or slices"),
209        };
210
211        let mutability = RefKind::mutable(mut_access);
212        let item = match (pe.is_subslice(), mutability) {
213            (false, RefKind::Shared) => StdItem::SliceIndex,
214            (false, RefKind::Mut) => StdItem::SliceIndexMut,
215            (true, RefKind::Shared) => StdItem::RangeIndex,
216            (true, RefKind::Mut) => StdItem::RangeIndexMut,
217        };
218        let Some(&index_fun_id) = self.std_items.item_map.get(&item) else {
219            return;
220        };
221        let Some(index_fun) = index_fun_id
222            .as_fun()
223            .and_then(|id| self.ctx.ctx.translated.fun_decls.get(*id))
224        else {
225            return;
226        };
227        let index_generics = GenericArgs::new(
228            [Region::Erased].into(),
229            [ty.clone()].into(),
230            [].into(),
231            ty_is_sized
232                .iter()
233                .cloned()
234                .map(PolyTraitRef::empty)
235                .collect(),
236        );
237        let index_fn_ptr = mk_fn_ptr(self.ctx.ctx, index_fun_id, index_generics);
238        let index_ty = index_fun.signature.inputs[0]
239            .clone()
240            .substitute(&index_fn_ptr.generics);
241
242        let output_inner_ty = if matches!(pe, Index { .. }) {
243            ty.clone()
244        } else {
245            TyKind::Slice(ty.clone(), ty_is_sized.clone()).into_ty()
246        };
247        let output_ty = {
248            TyKind::Ref(
249                Region::Erased,
250                output_inner_ty.clone(),
251                RefKind::mutable(mut_access),
252            )
253            .into_ty()
254        };
255
256        // Push the statements:
257        // `storage_live(tmp0)`
258        // `tmp0 = &{mut}p`
259        let input_var =
260            self.ctx
261                .borrow_to_new_var(subplace.clone(), BorrowKind::mutable(mut_access), None);
262
263        // Construct the arguments to pass to the indexing function.
264        let (last_arg, from_end) = match &pe {
265            Index {
266                offset: x,
267                from_end,
268                ..
269            }
270            | Subslice {
271                to: x, from_end, ..
272            } => (x.as_ref().clone(), *from_end),
273            _ => unreachable!(),
274        };
275        let to_idx = self
276            .ctx
277            .compute_subslice_end_idx(subplace, last_arg, from_end);
278        let index = match &pe {
279            Index { .. } => to_idx,
280            Subslice { from, .. } => {
281                let Some(range_ref) = index_ty.as_adt().cloned() else {
282                    return;
283                };
284                let range_ty = TyKind::Adt(range_ref.clone()).into_ty();
285                let range_var = self.ctx.fresh_var(None, range_ty);
286                self.ctx.insert_assn_stmt(
287                    range_var.clone(),
288                    Rvalue::Aggregate(
289                        AggregateKind::Adt(range_ref, None, None),
290                        vec![from.as_ref().clone(), to_idx],
291                    ),
292                );
293                Operand::Move(range_var)
294            }
295            _ => unreachable!(),
296        };
297
298        let (index_fn_ptr, args) = if let Some(len) = len {
299            let (array_item, slice_item) = match mutability {
300                RefKind::Shared => (StdItem::ArrayIndex, StdItem::SliceIndexImpl),
301                RefKind::Mut => (StdItem::ArrayIndexMut, StdItem::SliceIndexMutImpl),
302            };
303            let Some(&array_fun_id) = self.std_items.item_map.get(&array_item) else {
304                return;
305            };
306            let Some(array_fun) = array_fun_id
307                .as_fun()
308                .and_then(|id| self.ctx.ctx.translated.fun_decls.get(*id))
309            else {
310                return;
311            };
312            let Some(&slice_fun_id) = self.std_items.item_map.get(&slice_item) else {
313                return;
314            };
315            let Some(slice_fun) = slice_fun_id
316                .as_fun()
317                .and_then(|id| self.ctx.ctx.translated.fun_decls.get(*id))
318            else {
319                return;
320            };
321
322            let Some(slice_types) =
323                index_method_types(&slice_fun.generics, &ty, &index_ty, &output_inner_ty)
324            else {
325                return;
326            };
327            let mut slice_generics =
328                GenericArgs::new([Region::Erased].into(), slice_types, [].into(), [].into());
329            let Some(slice_index_trait_ref) =
330                method_impl_trait_ref(self.ctx.ctx, index_fun_id, &index_fn_ptr.generics)
331            else {
332                return;
333            };
334            let index_ty_is_sized = if ty_is_sized.is_some() {
335                let Some(clause) = slice_fun.generics.trait_clauses.get(TraitClauseId::new(1))
336                else {
337                    return;
338                };
339                let trait_decl_ref = clause.trait_.clone().substitute_explicits(&slice_generics);
340                let Some(meta_sized) = slice_index_trait_ref
341                    .clone()
342                    .project_parent_clause(&self.ctx.ctx.translated, TraitClauseId::ZERO)
343                else {
344                    return;
345                };
346                Some(TraitRef::new(
347                    TraitRefKind::BuiltinOrAuto {
348                        builtin_data: BuiltinImplData::Sized,
349                        parent_trait_refs: [meta_sized].into_iter().collect(),
350                        types: Default::default(),
351                        vtable: None,
352                    },
353                    trait_decl_ref.no_bound_vars(),
354                ))
355            } else {
356                None
357            };
358            slice_generics.trait_refs = ty_is_sized
359                .iter()
360                .cloned()
361                .chain(index_ty_is_sized.iter().cloned())
362                .chain([slice_index_trait_ref])
363                .map(PolyTraitRef::empty)
364                .collect();
365            let slice_fn_ptr = mk_fn_ptr(self.ctx.ctx, slice_fun_id, slice_generics);
366            let Some(slice_trait_ref) =
367                method_impl_trait_ref(self.ctx.ctx, slice_fun_id, &slice_fn_ptr.generics)
368            else {
369                return;
370            };
371
372            let Some(array_types) =
373                index_method_types(&array_fun.generics, &ty, &index_ty, &output_inner_ty)
374            else {
375                return;
376            };
377            let array_generics = GenericArgs::new(
378                [Region::Erased].into(),
379                array_types,
380                [len].into(),
381                ty_is_sized
382                    .iter()
383                    .cloned()
384                    .chain(index_ty_is_sized)
385                    .chain([slice_trait_ref])
386                    .map(PolyTraitRef::empty)
387                    .collect(),
388            );
389            (
390                mk_fn_ptr(self.ctx.ctx, array_fun_id, array_generics),
391                vec![Operand::Move(input_var), index],
392            )
393        } else {
394            (index_fn_ptr, vec![index, Operand::Move(input_var)])
395        };
396
397        // Call the indexing function:
398        // `storage_live(tmp1)`
399        // `tmp1 = {Array,Slice}{Mut,Shared}{Index,SubSlice}(move tmp0, <other args>)`
400        let output_var = {
401            let output_var = self.ctx.fresh_var(None, output_ty);
402            let index_call = Call {
403                func: FnOperand::Regular(index_fn_ptr),
404                args,
405                safety: CallSafety::Inherit,
406            };
407            let kind = StatementKind::Call {
408                call: index_call,
409                dest: output_var.clone(),
410                on_unwind: Block::new_unreachable(self.ctx.span),
411            };
412            self.ctx
413                .statements
414                .push(Statement::new(self.ctx.span, kind));
415            output_var
416        };
417
418        // Slice patterns make array subslices that are themselves arrays. We cast the slice
419        // returned by indexing into that array.
420        let output_var =
421            if matches!(pe, Subslice { .. }) && matches!(place.ty().kind(), TyKind::Array(..)) {
422                let array_ref_ty =
423                    TyKind::Ref(Region::Erased, place.ty().clone(), mutability).into_ty();
424                let array_ref_var = self.ctx.fresh_var(None, array_ref_ty.clone());
425                self.ctx.insert_assn_stmt(
426                    array_ref_var.clone(),
427                    Rvalue::UnaryOp(
428                        UnOp::Cast(CastKind::Concretize(array_ref_ty, vec![])),
429                        Operand::Move(output_var),
430                    ),
431                );
432                array_ref_var
433            } else {
434                output_var
435            };
436        *place = output_var.project(ProjectionElem::Deref, place.ty().clone());
437    }
438
439    /// Calls `self.visit_inner()` with `mutability` pushed on the stack.
440    fn visit_inner_with_mutability<T>(
441        &mut self,
442        x: &mut T,
443        mutability: bool,
444    ) -> ControlFlow<Infallible>
445    where
446        T: for<'s> DriveMut<'s, BodyVisitableWrapper<Self>> + BodyVisitable,
447    {
448        self.place_mutability_stack.push(mutability);
449        self.visit_inner(x)?;
450        self.place_mutability_stack.pop();
451        Continue(())
452    }
453}
454
455/// The visitor methods.
456impl VisitBodyMut for IndexVisitor<'_, '_> {
457    /// We explore places from the inside-out --- recursion naturally happens here.
458    fn exit_place(&mut self, place: &mut Place) {
459        // We have intercepted every traversal that would reach a place and pushed the correct
460        // mutability on the stack.
461        let mut_access = *self.place_mutability_stack.last().unwrap();
462        self.transform_place(mut_access, place);
463    }
464
465    fn visit_operand(&mut self, x: &mut Operand) -> ControlFlow<Infallible> {
466        match x {
467            Operand::Move(_) => self.visit_inner_with_mutability(x, true),
468            Operand::Copy(..) | Operand::Read(_) => self.visit_inner_with_mutability(x, false),
469            Operand::Const(..) => self.visit_inner(x),
470        }
471    }
472
473    fn visit_asm_operand(&mut self, x: &mut AsmOperand) -> ControlFlow<Infallible> {
474        match x {
475            AsmOperand::Out { .. } | AsmOperand::InOut { .. } => {
476                self.visit_inner_with_mutability(x, true)
477            }
478            _ => self.visit_inner(x),
479        }
480    }
481
482    fn visit_fn_operand(&mut self, x: &mut FnOperand) -> ControlFlow<Infallible> {
483        match x {
484            FnOperand::Regular(_) => self.visit_inner(x),
485            FnOperand::Dynamic(..) => self.visit_inner_with_mutability(x, true),
486        }
487    }
488
489    fn visit_rvalue(&mut self, x: &mut Rvalue) -> ControlFlow<Infallible> {
490        use Rvalue::*;
491        match x {
492            // `UniqueImmutable` de facto gives mutable access and only shows up if there is nested
493            // mutable access.
494            RawPtr {
495                kind: RefKind::Mut, ..
496            }
497            | Ref {
498                kind: BorrowKind::Mut | BorrowKind::TwoPhaseMut | BorrowKind::UniqueImmutable,
499                ..
500            } => self.visit_inner_with_mutability(x, true),
501            RawPtr {
502                kind: RefKind::Shared,
503                ..
504            }
505            | Ref {
506                kind: BorrowKind::Shared | BorrowKind::Shallow,
507                ..
508            }
509            | Discriminant(..) => self.visit_inner_with_mutability(x, false),
510
511            Use(..)
512            | NullaryOp(..)
513            | UnaryOp(..)
514            | BinaryOp(..)
515            | Aggregate(..)
516            | Repeat { .. } => self.visit_inner(x),
517        }
518    }
519
520    fn visit_llbc_block(&mut self, _: &mut llbc_ast::Block) -> ControlFlow<Infallible> {
521        ControlFlow::Continue(())
522    }
523}
524
525/// We do the following.
526///
527/// If `p` is a projection (for instance: `var`, `*var`, `var.f`, etc.), we
528/// detect:
529/// - whether it operates on a slice or an array (we keep track of the types)
530/// - whether the access might mutate the value or not (it is
531///   the case if it is in a `move`, `&mut` or at the lhs of an assignment),
532///   and do the following transformations
533///
534/// ```text
535///   // If array and mutable access:
536///   ... p[i] ...
537///      ~~>
538///   tmp0 = &mut p
539///   tmp1 = <[_; _] as IndexMut<_>>::index_mut(move tmp0, i)
540///   ... *tmp1 ...
541///
542///   // If array and non-mutable access:
543///   ... p[i] ...
544///      ~~>
545///   tmp0 := & p
546///   tmp1 := <[_; _] as Index<_>>::index(move tmp0, i)
547///   ... *tmp1 ...
548///
549///   // Omitting the slice cases, which are similar
550/// ```
551///
552/// For instance, it leads to the following transformations:
553/// ```text
554///   // x : [u32; N]
555///   y : u32 = copy x[i]
556///      ~~>
557///   tmp0 : & [u32; N] := &x
558///   tmp1 : &u32 = <[_; _] as Index<_>>::index(move tmp0, i)
559///   y : u32 = copy (*tmp1)
560///
561///   // x : &[T; N]
562///   y : &T = & (*x)[i]
563///      ~~>
564///   tmp0 : & [T; N] := & (*x)
565///   tmp1 : &T = <[_; _] as Index<_>>::index(move tmp0, i)
566///   y : &T = & (*tmp1)
567///
568///   // x : [u32; N]
569///   y = &mut x[i]
570///      ~~>
571///   tmp0 : &mut [u32; N] := &mut x
572///   tmp1 : &mut u32 := <[_; _] as IndexMut<_>>::index_mut(move tmp0, i)
573///   y = &mut (*tmp)
574///
575///   // When using an index on the lhs:
576///   // y : [T; N]
577///   y[i] = x
578///      ~~>
579///   tmp0 : &mut [T; N] := &mut y;
580///   tmp1 : &mut T = <[_; _] as IndexMut<_>>::index_mut(move tmp0, i)
581///   *tmp1 = x
582/// ```
583#[derive(Copy, Clone, PartialEq, Eq, Hash)]
584enum StdItem {
585    ArrayAsSlice,
586    ArrayAsMutSlice,
587    ArrayRepeat,
588    ArrayIndex,
589    ArrayIndexMut,
590    SliceIndexImpl,
591    SliceIndexMutImpl,
592    SliceIndex,
593    SliceIndexMut,
594    RangeIndex,
595    RangeIndexMut,
596}
597
598pub struct Transform {
599    item_map: HashMap<StdItem, ItemId>,
600    item_set: HashSet<ItemId>,
601}
602
603impl Transform {
604    pub fn new(ctx: &TransformCtx) -> CowBox<dyn LlbcPass> {
605        use StdItem::*;
606
607        let mut matches: [(StdItem, NamePattern, Vec<ItemId>); _] = [
608            (ArrayAsSlice, "core::array::_::as_slice"),
609            (ArrayAsMutSlice, "core::array::_::as_mut_slice"),
610            (ArrayRepeat, "core::array::repeat"),
611            (
612                SliceIndex,
613                "core::slice::index::{impl core::slice::index::SliceIndex<_> for usize}::index",
614            ),
615            (
616                SliceIndexMut,
617                "core::slice::index::{impl core::slice::index::SliceIndex<_> for usize}::index_mut",
618            ),
619            (
620                RangeIndex,
621                "core::slice::index::{impl core::slice::index::SliceIndex<_> for core::ops::range::Range<usize>}::index",
622            ),
623            (
624                RangeIndexMut,
625                "core::slice::index::{impl core::slice::index::SliceIndex<_> for core::ops::range::Range<usize>}::index_mut",
626            ),
627        ]
628        .map(|(item, path)| (item, NamePattern::parse(path).unwrap(), Vec::new()));
629
630        // Resolve the items
631        for (id, name) in &ctx.translated.item_names {
632            for (_, pattern, found) in &mut matches {
633                if pattern.matches(&ctx.translated, name) {
634                    found.push(*id);
635                }
636            }
637        }
638
639        let mut index_impl_methods: HashMap<StdItem, Vec<ItemId>> = HashMap::new();
640        for fun in &ctx.translated.fun_decls {
641            let FunSource::TraitImpl { trait_ref, .. } = &fun.src else {
642                continue;
643            };
644            let Some(trait_decl) = ctx.translated.trait_decls.get(trait_ref.id) else {
645                continue;
646            };
647            let Some(self_ty) = trait_ref.self_ty(&ctx.translated) else {
648                continue;
649            };
650            let item = match (&trait_decl.item_meta.lang_item, self_ty.kind()) {
651                (Some(crate::ast::from_rustc::LangItem::Index), TyKind::Array(..)) => ArrayIndex,
652                (Some(crate::ast::from_rustc::LangItem::IndexMut), TyKind::Array(..)) => {
653                    ArrayIndexMut
654                }
655                (Some(crate::ast::from_rustc::LangItem::Index), TyKind::Slice(..)) => {
656                    SliceIndexImpl
657                }
658                (Some(crate::ast::from_rustc::LangItem::IndexMut), TyKind::Slice(..)) => {
659                    SliceIndexMutImpl
660                }
661                _ => continue,
662            };
663            index_impl_methods
664                .entry(item)
665                .or_default()
666                .push(ItemId::Fun(fun.def_id));
667        }
668        let item_map = matches
669            .into_iter()
670            .map(|(item, _, found)| (item, found))
671            .chain(index_impl_methods)
672            .filter_map(|(item, found)| found.into_iter().exactly_one().ok().map(|id| (item, id)))
673            .collect::<HashMap<_, _>>();
674        let item_set = item_map.values().copied().collect();
675        CowBox::Owned(Box::new(Self { item_map, item_set }))
676    }
677}
678
679impl LlbcPass for Transform {
680    fn should_run(&self, options: &crate::options::TranslateOptions) -> bool {
681        options.ops_to_function_calls || options.index_to_function_calls
682    }
683
684    fn transform_function(&self, ctx: &mut TransformCtx, decl: &mut FunDecl) {
685        if self.item_set.contains(&ItemId::Fun(decl.def_id)) {
686            return;
687        }
688        let Some(body) = decl.body.as_structured_mut() else {
689            return;
690        };
691        if ctx.options.ops_to_function_calls {
692            body.body
693                .visit_statements(&mut |statement: &mut Statement| {
694                    transform_operation(self, ctx, statement)
695                });
696        }
697        if ctx.options.index_to_function_calls {
698            decl.transform_llbc_statements(ctx, |ctx, st: &mut Statement| {
699                let mut visitor = IndexVisitor {
700                    ctx,
701                    std_items: self,
702                    place_mutability_stack: Vec::new(),
703                };
704                use StatementKind::*;
705                match &mut st.kind {
706                    Assign(..)
707                    | SetDiscriminant(..)
708                    | Drop { .. }
709                    | DropEmptyBox { .. }
710                    | Call { .. } => {
711                        let _ = visitor.visit_inner_with_mutability(st, true);
712                    }
713                    Switch { .. } | PlaceMention(..) | Borrowck(..) => {
714                        let _ = visitor.visit_inner_with_mutability(st, false);
715                    }
716                    Nop
717                    | UnwindResume
718                    | InlineAsm { .. }
719                    | Assert { .. }
720                    | Panic { .. }
721                    | UndefinedBehavior
722                    | UnwindTerminate(..)
723                    | StorageDead(..)
724                    | StorageLive(..)
725                    | Return
726                    | Break(..)
727                    | Continue(..)
728                    | Loop(..) => {
729                        let _ = st.drive_body_mut(&mut visitor);
730                    }
731                }
732            })
733        }
734    }
735}