1use 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 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
41fn 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 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 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 assert!(src_kind == tgt_kind);
100 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 StatementKind::Assign(
132 place,
133 Rvalue::Repeat {
134 operand,
135 count,
136 elem_is_sized,
137 elem_is_copy,
138 },
139 ) => {
140 let Some(&fun_id) = std_items.item_map.get(&StdItem::ArrayRepeat) else {
143 return;
144 };
145 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#[derive(Visitor)]
185struct IndexVisitor<'a, 'b> {
186 ctx: &'b mut LlbcStatementTransformCtx<'a>,
187 std_items: &'b Transform,
188 place_mutability_stack: Vec<bool>,
193}
194
195impl<'a, 'b> IndexVisitor<'a, 'b> {
196 fn transform_place(&mut self, mut_access: bool, place: &mut Place) {
198 use ProjectionElem::*;
199 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 let input_var =
260 self.ctx
261 .borrow_to_new_var(subplace.clone(), BorrowKind::mutable(mut_access), None);
262
263 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 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 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 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
455impl VisitBodyMut for IndexVisitor<'_, '_> {
457 fn exit_place(&mut self, place: &mut Place) {
459 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 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#[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 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}