hir_ty/mir/
borrowck.rs

1//! MIR borrow checker, which is used in diagnostics like `unused_mut`
2
3// Currently it is an ad-hoc implementation, only useful for mutability analysis. Feel free to remove all of these
4// if needed for implementing a proper borrow checker.
5
6use std::iter;
7
8use hir_def::{DefWithBodyId, HasModule};
9use la_arena::ArenaMap;
10use rustc_hash::FxHashMap;
11use stdx::never;
12use triomphe::Arc;
13
14use crate::{
15    ClosureId, Interner, Substitution, Ty, TyExt, TypeFlags,
16    db::{HirDatabase, InternedClosure},
17    display::DisplayTarget,
18    mir::OperandKind,
19    utils::ClosureSubst,
20};
21
22use super::{
23    BasicBlockId, BorrowKind, LocalId, MirBody, MirLowerError, MirSpan, MutBorrowKind, Operand,
24    Place, ProjectionElem, Rvalue, StatementKind, TerminatorKind,
25};
26
27#[derive(Debug, Clone, PartialEq, Eq)]
28/// Stores spans which implies that the local should be mutable.
29pub enum MutabilityReason {
30    Mut { spans: Vec<MirSpan> },
31    Not,
32    Unused,
33}
34
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub struct MovedOutOfRef {
37    pub ty: Ty,
38    pub span: MirSpan,
39}
40
41#[derive(Debug, Clone, PartialEq, Eq)]
42pub struct PartiallyMoved {
43    pub ty: Ty,
44    pub span: MirSpan,
45    pub local: LocalId,
46}
47
48#[derive(Debug, Clone, PartialEq, Eq)]
49pub struct BorrowRegion {
50    pub local: LocalId,
51    pub kind: BorrowKind,
52    pub places: Vec<MirSpan>,
53}
54
55#[derive(Debug, Clone, PartialEq, Eq)]
56pub struct BorrowckResult {
57    pub mir_body: Arc<MirBody>,
58    pub mutability_of_locals: ArenaMap<LocalId, MutabilityReason>,
59    pub moved_out_of_ref: Vec<MovedOutOfRef>,
60    pub partially_moved: Vec<PartiallyMoved>,
61    pub borrow_regions: Vec<BorrowRegion>,
62}
63
64fn all_mir_bodies(
65    db: &dyn HirDatabase,
66    def: DefWithBodyId,
67    mut cb: impl FnMut(Arc<MirBody>),
68) -> Result<(), MirLowerError> {
69    fn for_closure(
70        db: &dyn HirDatabase,
71        c: ClosureId,
72        cb: &mut impl FnMut(Arc<MirBody>),
73    ) -> Result<(), MirLowerError> {
74        match db.mir_body_for_closure(c.into()) {
75            Ok(body) => {
76                cb(body.clone());
77                body.closures.iter().try_for_each(|&it| for_closure(db, it, cb))
78            }
79            Err(e) => Err(e),
80        }
81    }
82    match db.mir_body(def) {
83        Ok(body) => {
84            cb(body.clone());
85            body.closures.iter().try_for_each(|&it| for_closure(db, it, &mut cb))
86        }
87        Err(e) => Err(e),
88    }
89}
90
91pub fn borrowck_query(
92    db: &dyn HirDatabase,
93    def: DefWithBodyId,
94) -> Result<Arc<[BorrowckResult]>, MirLowerError> {
95    let _p = tracing::info_span!("borrowck_query").entered();
96    let mut res = vec![];
97    all_mir_bodies(db, def, |body| {
98        res.push(BorrowckResult {
99            mutability_of_locals: mutability_of_locals(db, &body),
100            moved_out_of_ref: moved_out_of_ref(db, &body),
101            partially_moved: partially_moved(db, &body),
102            borrow_regions: borrow_regions(db, &body),
103            mir_body: body,
104        });
105    })?;
106    Ok(res.into())
107}
108
109fn make_fetch_closure_field(
110    db: &dyn HirDatabase,
111) -> impl FnOnce(ClosureId, &Substitution, usize) -> Ty + '_ {
112    |c: ClosureId, subst: &Substitution, f: usize| {
113        let InternedClosure(def, _) = db.lookup_intern_closure(c.into());
114        let infer = db.infer(def);
115        let (captures, _) = infer.closure_info(&c);
116        let parent_subst = ClosureSubst(subst).parent_subst();
117        captures.get(f).expect("broken closure field").ty.clone().substitute(Interner, parent_subst)
118    }
119}
120
121fn moved_out_of_ref(db: &dyn HirDatabase, body: &MirBody) -> Vec<MovedOutOfRef> {
122    let mut result = vec![];
123    let mut for_operand = |op: &Operand, span: MirSpan| match op.kind {
124        OperandKind::Copy(p) | OperandKind::Move(p) => {
125            let mut ty: Ty = body.locals[p.local].ty.clone();
126            let mut is_dereference_of_ref = false;
127            for proj in p.projection.lookup(&body.projection_store) {
128                if *proj == ProjectionElem::Deref && ty.as_reference().is_some() {
129                    is_dereference_of_ref = true;
130                }
131                ty = proj.projected_ty(
132                    ty,
133                    db,
134                    make_fetch_closure_field(db),
135                    body.owner.module(db).krate(),
136                );
137            }
138            if is_dereference_of_ref
139                && !ty.clone().is_copy(db, body.owner)
140                && !ty.data(Interner).flags.intersects(TypeFlags::HAS_ERROR)
141            {
142                result.push(MovedOutOfRef { span: op.span.unwrap_or(span), ty });
143            }
144        }
145        OperandKind::Constant(_) | OperandKind::Static(_) => (),
146    };
147    for (_, block) in body.basic_blocks.iter() {
148        db.unwind_if_revision_cancelled();
149        for statement in &block.statements {
150            match &statement.kind {
151                StatementKind::Assign(_, r) => match r {
152                    Rvalue::ShallowInitBoxWithAlloc(_) => (),
153                    Rvalue::ShallowInitBox(o, _)
154                    | Rvalue::UnaryOp(_, o)
155                    | Rvalue::Cast(_, o, _)
156                    | Rvalue::Repeat(o, _)
157                    | Rvalue::Use(o) => for_operand(o, statement.span),
158                    Rvalue::CopyForDeref(_)
159                    | Rvalue::Discriminant(_)
160                    | Rvalue::Len(_)
161                    | Rvalue::Ref(_, _) => (),
162                    Rvalue::CheckedBinaryOp(_, o1, o2) => {
163                        for_operand(o1, statement.span);
164                        for_operand(o2, statement.span);
165                    }
166                    Rvalue::Aggregate(_, ops) => {
167                        for op in ops.iter() {
168                            for_operand(op, statement.span);
169                        }
170                    }
171                    Rvalue::ThreadLocalRef(n)
172                    | Rvalue::AddressOf(n)
173                    | Rvalue::BinaryOp(n)
174                    | Rvalue::NullaryOp(n) => match *n {},
175                },
176                StatementKind::FakeRead(_)
177                | StatementKind::Deinit(_)
178                | StatementKind::StorageLive(_)
179                | StatementKind::StorageDead(_)
180                | StatementKind::Nop => (),
181            }
182        }
183        match &block.terminator {
184            Some(terminator) => match &terminator.kind {
185                TerminatorKind::SwitchInt { discr, .. } => for_operand(discr, terminator.span),
186                TerminatorKind::FalseEdge { .. }
187                | TerminatorKind::FalseUnwind { .. }
188                | TerminatorKind::Goto { .. }
189                | TerminatorKind::UnwindResume
190                | TerminatorKind::CoroutineDrop
191                | TerminatorKind::Abort
192                | TerminatorKind::Return
193                | TerminatorKind::Unreachable
194                | TerminatorKind::Drop { .. } => (),
195                TerminatorKind::DropAndReplace { value, .. } => {
196                    for_operand(value, terminator.span);
197                }
198                TerminatorKind::Call { func, args, .. } => {
199                    for_operand(func, terminator.span);
200                    args.iter().for_each(|it| for_operand(it, terminator.span));
201                }
202                TerminatorKind::Assert { cond, .. } => {
203                    for_operand(cond, terminator.span);
204                }
205                TerminatorKind::Yield { value, .. } => {
206                    for_operand(value, terminator.span);
207                }
208            },
209            None => (),
210        }
211    }
212    result.shrink_to_fit();
213    result
214}
215
216fn partially_moved(db: &dyn HirDatabase, body: &MirBody) -> Vec<PartiallyMoved> {
217    let mut result = vec![];
218    let mut for_operand = |op: &Operand, span: MirSpan| match op.kind {
219        OperandKind::Copy(p) | OperandKind::Move(p) => {
220            let mut ty: Ty = body.locals[p.local].ty.clone();
221            for proj in p.projection.lookup(&body.projection_store) {
222                ty = proj.projected_ty(
223                    ty,
224                    db,
225                    make_fetch_closure_field(db),
226                    body.owner.module(db).krate(),
227                );
228            }
229            if !ty.clone().is_copy(db, body.owner)
230                && !ty.data(Interner).flags.intersects(TypeFlags::HAS_ERROR)
231            {
232                result.push(PartiallyMoved { span, ty, local: p.local });
233            }
234        }
235        OperandKind::Constant(_) | OperandKind::Static(_) => (),
236    };
237    for (_, block) in body.basic_blocks.iter() {
238        db.unwind_if_revision_cancelled();
239        for statement in &block.statements {
240            match &statement.kind {
241                StatementKind::Assign(_, r) => match r {
242                    Rvalue::ShallowInitBoxWithAlloc(_) => (),
243                    Rvalue::ShallowInitBox(o, _)
244                    | Rvalue::UnaryOp(_, o)
245                    | Rvalue::Cast(_, o, _)
246                    | Rvalue::Repeat(o, _)
247                    | Rvalue::Use(o) => for_operand(o, statement.span),
248                    Rvalue::CopyForDeref(_)
249                    | Rvalue::Discriminant(_)
250                    | Rvalue::Len(_)
251                    | Rvalue::Ref(_, _) => (),
252                    Rvalue::CheckedBinaryOp(_, o1, o2) => {
253                        for_operand(o1, statement.span);
254                        for_operand(o2, statement.span);
255                    }
256                    Rvalue::Aggregate(_, ops) => {
257                        for op in ops.iter() {
258                            for_operand(op, statement.span);
259                        }
260                    }
261                    Rvalue::ThreadLocalRef(n)
262                    | Rvalue::AddressOf(n)
263                    | Rvalue::BinaryOp(n)
264                    | Rvalue::NullaryOp(n) => match *n {},
265                },
266                StatementKind::FakeRead(_)
267                | StatementKind::Deinit(_)
268                | StatementKind::StorageLive(_)
269                | StatementKind::StorageDead(_)
270                | StatementKind::Nop => (),
271            }
272        }
273        match &block.terminator {
274            Some(terminator) => match &terminator.kind {
275                TerminatorKind::SwitchInt { discr, .. } => for_operand(discr, terminator.span),
276                TerminatorKind::FalseEdge { .. }
277                | TerminatorKind::FalseUnwind { .. }
278                | TerminatorKind::Goto { .. }
279                | TerminatorKind::UnwindResume
280                | TerminatorKind::CoroutineDrop
281                | TerminatorKind::Abort
282                | TerminatorKind::Return
283                | TerminatorKind::Unreachable
284                | TerminatorKind::Drop { .. } => (),
285                TerminatorKind::DropAndReplace { value, .. } => {
286                    for_operand(value, terminator.span);
287                }
288                TerminatorKind::Call { func, args, .. } => {
289                    for_operand(func, terminator.span);
290                    args.iter().for_each(|it| for_operand(it, terminator.span));
291                }
292                TerminatorKind::Assert { cond, .. } => {
293                    for_operand(cond, terminator.span);
294                }
295                TerminatorKind::Yield { value, .. } => {
296                    for_operand(value, terminator.span);
297                }
298            },
299            None => (),
300        }
301    }
302    result.shrink_to_fit();
303    result
304}
305
306fn borrow_regions(db: &dyn HirDatabase, body: &MirBody) -> Vec<BorrowRegion> {
307    let mut borrows = FxHashMap::default();
308    for (_, block) in body.basic_blocks.iter() {
309        db.unwind_if_revision_cancelled();
310        for statement in &block.statements {
311            if let StatementKind::Assign(_, Rvalue::Ref(kind, p)) = &statement.kind {
312                borrows
313                    .entry(p.local)
314                    .and_modify(|it: &mut BorrowRegion| {
315                        it.places.push(statement.span);
316                    })
317                    .or_insert_with(|| BorrowRegion {
318                        local: p.local,
319                        kind: *kind,
320                        places: vec![statement.span],
321                    });
322            }
323        }
324        match &block.terminator {
325            Some(terminator) => match &terminator.kind {
326                TerminatorKind::FalseEdge { .. }
327                | TerminatorKind::FalseUnwind { .. }
328                | TerminatorKind::Goto { .. }
329                | TerminatorKind::UnwindResume
330                | TerminatorKind::CoroutineDrop
331                | TerminatorKind::Abort
332                | TerminatorKind::Return
333                | TerminatorKind::Unreachable
334                | TerminatorKind::Drop { .. } => (),
335                TerminatorKind::DropAndReplace { .. } => {}
336                TerminatorKind::Call { .. } => {}
337                _ => (),
338            },
339            None => (),
340        }
341    }
342
343    borrows.into_values().collect()
344}
345
346#[derive(Debug, Clone, Copy, PartialEq, Eq)]
347enum ProjectionCase {
348    /// Projection is a local
349    Direct,
350    /// Projection is some field or slice of a local
351    DirectPart,
352    /// Projection is deref of something
353    Indirect,
354}
355
356fn place_case(db: &dyn HirDatabase, body: &MirBody, lvalue: &Place) -> ProjectionCase {
357    let mut is_part_of = false;
358    let mut ty = body.locals[lvalue.local].ty.clone();
359    for proj in lvalue.projection.lookup(&body.projection_store).iter() {
360        match proj {
361            ProjectionElem::Deref if ty.as_adt().is_none() => return ProjectionCase::Indirect, // It's indirect in case of reference and raw
362            ProjectionElem::Deref // It's direct in case of `Box<T>`
363            | ProjectionElem::ConstantIndex { .. }
364            | ProjectionElem::Subslice { .. }
365            | ProjectionElem::Field(_)
366            | ProjectionElem::ClosureField(_)
367            | ProjectionElem::Index(_) => {
368                is_part_of = true;
369            }
370            ProjectionElem::OpaqueCast(_) => (),
371        }
372        ty = proj.projected_ty(ty, db, make_fetch_closure_field(db), body.owner.module(db).krate());
373    }
374    if is_part_of { ProjectionCase::DirectPart } else { ProjectionCase::Direct }
375}
376
377/// Returns a map from basic blocks to the set of locals that might be ever initialized before
378/// the start of the block. Only `StorageDead` can remove something from this map, and we ignore
379/// `Uninit` and `drop` and similar after initialization.
380fn ever_initialized_map(
381    db: &dyn HirDatabase,
382    body: &MirBody,
383) -> ArenaMap<BasicBlockId, ArenaMap<LocalId, bool>> {
384    let mut result: ArenaMap<BasicBlockId, ArenaMap<LocalId, bool>> =
385        body.basic_blocks.iter().map(|it| (it.0, ArenaMap::default())).collect();
386    fn dfs(
387        db: &dyn HirDatabase,
388        body: &MirBody,
389        l: LocalId,
390        stack: &mut Vec<BasicBlockId>,
391        result: &mut ArenaMap<BasicBlockId, ArenaMap<LocalId, bool>>,
392    ) {
393        while let Some(b) = stack.pop() {
394            let mut is_ever_initialized = result[b][l]; // It must be filled, as we use it as mark for dfs
395            let block = &body.basic_blocks[b];
396            for statement in &block.statements {
397                match &statement.kind {
398                    StatementKind::Assign(p, _) => {
399                        if p.projection.lookup(&body.projection_store).is_empty() && p.local == l {
400                            is_ever_initialized = true;
401                        }
402                    }
403                    StatementKind::StorageDead(p) => {
404                        if *p == l {
405                            is_ever_initialized = false;
406                        }
407                    }
408                    StatementKind::Deinit(_)
409                    | StatementKind::FakeRead(_)
410                    | StatementKind::Nop
411                    | StatementKind::StorageLive(_) => (),
412                }
413            }
414            let Some(terminator) = &block.terminator else {
415                never!(
416                    "Terminator should be none only in construction.\nThe body:\n{}",
417                    body.pretty_print(db, DisplayTarget::from_crate(db, body.owner.krate(db)))
418                );
419                return;
420            };
421            let mut process = |target, is_ever_initialized| {
422                if !result[target].contains_idx(l) || !result[target][l] && is_ever_initialized {
423                    result[target].insert(l, is_ever_initialized);
424                    stack.push(target);
425                }
426            };
427            match &terminator.kind {
428                TerminatorKind::Goto { target } => process(*target, is_ever_initialized),
429                TerminatorKind::SwitchInt { targets, .. } => {
430                    targets.all_targets().iter().for_each(|&it| process(it, is_ever_initialized));
431                }
432                TerminatorKind::UnwindResume
433                | TerminatorKind::Abort
434                | TerminatorKind::Return
435                | TerminatorKind::Unreachable => (),
436                TerminatorKind::Call { target, cleanup, destination, .. } => {
437                    if destination.projection.lookup(&body.projection_store).is_empty()
438                        && destination.local == l
439                    {
440                        is_ever_initialized = true;
441                    }
442                    target.iter().chain(cleanup).for_each(|&it| process(it, is_ever_initialized));
443                }
444                TerminatorKind::Drop { target, unwind, place: _ } => {
445                    iter::once(target)
446                        .chain(unwind)
447                        .for_each(|&it| process(it, is_ever_initialized));
448                }
449                TerminatorKind::DropAndReplace { .. }
450                | TerminatorKind::Assert { .. }
451                | TerminatorKind::Yield { .. }
452                | TerminatorKind::CoroutineDrop
453                | TerminatorKind::FalseEdge { .. }
454                | TerminatorKind::FalseUnwind { .. } => {
455                    never!("We don't emit these MIR terminators yet");
456                }
457            }
458        }
459    }
460    let mut stack = Vec::new();
461    for &l in &body.param_locals {
462        result[body.start_block].insert(l, true);
463        stack.clear();
464        stack.push(body.start_block);
465        dfs(db, body, l, &mut stack, &mut result);
466    }
467    for l in body.locals.iter().map(|it| it.0) {
468        db.unwind_if_revision_cancelled();
469        if !result[body.start_block].contains_idx(l) {
470            result[body.start_block].insert(l, false);
471            stack.clear();
472            stack.push(body.start_block);
473            dfs(db, body, l, &mut stack, &mut result);
474        }
475    }
476    result
477}
478
479fn push_mut_span(local: LocalId, span: MirSpan, result: &mut ArenaMap<LocalId, MutabilityReason>) {
480    match &mut result[local] {
481        MutabilityReason::Mut { spans } => spans.push(span),
482        it @ (MutabilityReason::Not | MutabilityReason::Unused) => {
483            *it = MutabilityReason::Mut { spans: vec![span] }
484        }
485    };
486}
487
488fn record_usage(local: LocalId, result: &mut ArenaMap<LocalId, MutabilityReason>) {
489    if let it @ MutabilityReason::Unused = &mut result[local] {
490        *it = MutabilityReason::Not;
491    };
492}
493
494fn record_usage_for_operand(arg: &Operand, result: &mut ArenaMap<LocalId, MutabilityReason>) {
495    if let OperandKind::Copy(p) | OperandKind::Move(p) = arg.kind {
496        record_usage(p.local, result);
497    }
498}
499
500fn mutability_of_locals(
501    db: &dyn HirDatabase,
502    body: &MirBody,
503) -> ArenaMap<LocalId, MutabilityReason> {
504    let mut result: ArenaMap<LocalId, MutabilityReason> =
505        body.locals.iter().map(|it| (it.0, MutabilityReason::Unused)).collect();
506
507    let ever_init_maps = ever_initialized_map(db, body);
508    for (block_id, mut ever_init_map) in ever_init_maps.into_iter() {
509        let block = &body.basic_blocks[block_id];
510        for statement in &block.statements {
511            match &statement.kind {
512                StatementKind::Assign(place, value) => {
513                    match place_case(db, body, place) {
514                        ProjectionCase::Direct => {
515                            if ever_init_map.get(place.local).copied().unwrap_or_default() {
516                                push_mut_span(place.local, statement.span, &mut result);
517                            } else {
518                                ever_init_map.insert(place.local, true);
519                            }
520                        }
521                        ProjectionCase::DirectPart => {
522                            // Partial initialization is not supported, so it is definitely `mut`
523                            push_mut_span(place.local, statement.span, &mut result);
524                        }
525                        ProjectionCase::Indirect => {
526                            record_usage(place.local, &mut result);
527                        }
528                    }
529                    match value {
530                        Rvalue::CopyForDeref(p)
531                        | Rvalue::Discriminant(p)
532                        | Rvalue::Len(p)
533                        | Rvalue::Ref(_, p) => {
534                            record_usage(p.local, &mut result);
535                        }
536                        Rvalue::Use(o)
537                        | Rvalue::Repeat(o, _)
538                        | Rvalue::Cast(_, o, _)
539                        | Rvalue::UnaryOp(_, o) => record_usage_for_operand(o, &mut result),
540                        Rvalue::CheckedBinaryOp(_, o1, o2) => {
541                            for o in [o1, o2] {
542                                record_usage_for_operand(o, &mut result);
543                            }
544                        }
545                        Rvalue::Aggregate(_, args) => {
546                            for arg in args.iter() {
547                                record_usage_for_operand(arg, &mut result);
548                            }
549                        }
550                        Rvalue::ShallowInitBox(_, _) | Rvalue::ShallowInitBoxWithAlloc(_) => (),
551                        Rvalue::ThreadLocalRef(n)
552                        | Rvalue::AddressOf(n)
553                        | Rvalue::BinaryOp(n)
554                        | Rvalue::NullaryOp(n) => match *n {},
555                    }
556                    if let Rvalue::Ref(
557                        BorrowKind::Mut {
558                            kind: MutBorrowKind::Default | MutBorrowKind::TwoPhasedBorrow,
559                        },
560                        p,
561                    ) = value
562                        && place_case(db, body, p) != ProjectionCase::Indirect
563                    {
564                        push_mut_span(p.local, statement.span, &mut result);
565                    }
566                }
567                StatementKind::FakeRead(p) => {
568                    record_usage(p.local, &mut result);
569                }
570                StatementKind::StorageDead(p) => {
571                    ever_init_map.insert(*p, false);
572                }
573                StatementKind::Deinit(_) | StatementKind::StorageLive(_) | StatementKind::Nop => (),
574            }
575        }
576        let Some(terminator) = &block.terminator else {
577            never!("Terminator should be none only in construction");
578            continue;
579        };
580        match &terminator.kind {
581            TerminatorKind::Goto { .. }
582            | TerminatorKind::UnwindResume
583            | TerminatorKind::Abort
584            | TerminatorKind::Return
585            | TerminatorKind::Unreachable
586            | TerminatorKind::FalseEdge { .. }
587            | TerminatorKind::FalseUnwind { .. }
588            | TerminatorKind::CoroutineDrop
589            | TerminatorKind::Drop { .. }
590            | TerminatorKind::DropAndReplace { .. }
591            | TerminatorKind::Assert { .. }
592            | TerminatorKind::Yield { .. } => (),
593            TerminatorKind::SwitchInt { discr, targets: _ } => {
594                record_usage_for_operand(discr, &mut result);
595            }
596            TerminatorKind::Call { destination, args, func, .. } => {
597                record_usage_for_operand(func, &mut result);
598                for arg in args.iter() {
599                    record_usage_for_operand(arg, &mut result);
600                }
601                if destination.projection.lookup(&body.projection_store).is_empty() {
602                    if ever_init_map.get(destination.local).copied().unwrap_or_default() {
603                        push_mut_span(destination.local, terminator.span, &mut result);
604                    } else {
605                        ever_init_map.insert(destination.local, true);
606                    }
607                }
608            }
609        }
610    }
611    result
612}
hir_ty/mir/borrowck.rs

hir_ty/mir/
borrowck.rs
