New upstream version 1.40.0+dfsg1

[rustc.git] / src / librustc_mir / borrow_check / nll / constraint_generation.rs

use crate::borrow_check::borrow_set::BorrowSet;
use crate::borrow_check::location::LocationTable;
use crate::borrow_check::nll::ToRegionVid;
use crate::borrow_check::nll::facts::AllFacts;
use crate::borrow_check::nll::region_infer::values::LivenessValues;
use crate::borrow_check::places_conflict;
use rustc::infer::InferCtxt;
use rustc::mir::visit::TyContext;
use rustc::mir::visit::Visitor;
use rustc::mir::{
    BasicBlock, BasicBlockData, Body, Local, Location, Place, PlaceBase, PlaceRef, ProjectionElem,
    Rvalue, SourceInfo, Statement, StatementKind, Terminator, TerminatorKind, UserTypeProjection,
};
use rustc::ty::fold::TypeFoldable;
use rustc::ty::{self, RegionVid, Ty};
use rustc::ty::subst::SubstsRef;

pub(super) fn generate_constraints<'cx, 'tcx>(
    infcx: &InferCtxt<'cx, 'tcx>,
    param_env: ty::ParamEnv<'tcx>,
    liveness_constraints: &mut LivenessValues<RegionVid>,
    all_facts: &mut Option<AllFacts>,
    location_table: &LocationTable,
    body: &Body<'tcx>,
    borrow_set: &BorrowSet<'tcx>,
) {
    let mut cg = ConstraintGeneration {
        borrow_set,
        infcx,
        liveness_constraints,
        location_table,
        all_facts,
        body,
        param_env,
    };

    for (bb, data) in body.basic_blocks().iter_enumerated() {
        cg.visit_basic_block_data(bb, data);
    }
}

/// 'cg = the duration of the constraint generation process itself.
struct ConstraintGeneration<'cg, 'cx, 'tcx> {
    infcx: &'cg InferCtxt<'cx, 'tcx>,
    param_env: ty::ParamEnv<'tcx>,
    all_facts: &'cg mut Option<AllFacts>,
    location_table: &'cg LocationTable,
    liveness_constraints: &'cg mut LivenessValues<RegionVid>,
    borrow_set: &'cg BorrowSet<'tcx>,
    body: &'cg Body<'tcx>,
}

impl<'cg, 'cx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'tcx> {
    fn visit_basic_block_data(&mut self, bb: BasicBlock, data: &BasicBlockData<'tcx>) {
        self.super_basic_block_data(bb, data);
    }

    /// We sometimes have `substs` within an rvalue, or within a
    /// call. Make them live at the location where they appear.
    fn visit_substs(&mut self, substs: &SubstsRef<'tcx>, location: Location) {
        self.add_regular_live_constraint(*substs, location);
        self.super_substs(substs);
    }

    /// We sometimes have `region` within an rvalue, or within a
    /// call. Make them live at the location where they appear.
    fn visit_region(&mut self, region: &ty::Region<'tcx>, location: Location) {
        self.add_regular_live_constraint(*region, location);
        self.super_region(region);
    }

    /// We sometimes have `ty` within an rvalue, or within a
    /// call. Make them live at the location where they appear.
    fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) {
        match ty_context {
            TyContext::ReturnTy(SourceInfo { span, .. })
            | TyContext::YieldTy(SourceInfo { span, .. })
            | TyContext::UserTy(span)
            | TyContext::LocalDecl { source_info: SourceInfo { span, .. }, .. } => {
                span_bug!(
                    span,
                    "should not be visiting outside of the CFG: {:?}",
                    ty_context
                );
            }
            TyContext::Location(location) => {
                self.add_regular_live_constraint(ty, location);
            }
        }

        self.super_ty(ty);
    }

    fn visit_statement(
        &mut self,
        statement: &Statement<'tcx>,
        location: Location,
    ) {
        if let Some(all_facts) = self.all_facts {
            all_facts.cfg_edge.push((
                self.location_table.start_index(location),
                self.location_table.mid_index(location),
            ));

            all_facts.cfg_edge.push((
                self.location_table.mid_index(location),
                self.location_table
                    .start_index(location.successor_within_block()),
            ));

            // If there are borrows on this now dead local, we need to record them as `killed`.
            if let StatementKind::StorageDead(ref local) = statement.kind {
                record_killed_borrows_for_local(
                    all_facts,
                    self.borrow_set,
                    self.location_table,
                    local,
                    location,
                );
            }
        }

        self.super_statement(statement, location);
    }

    fn visit_assign(
        &mut self,
        place: &Place<'tcx>,
        rvalue: &Rvalue<'tcx>,
        location: Location,
    ) {
        // When we see `X = ...`, then kill borrows of
        // `(*X).foo` and so forth.
        self.record_killed_borrows_for_place(place, location);

        self.super_assign(place, rvalue, location);
    }

    fn visit_terminator(
        &mut self,
        terminator: &Terminator<'tcx>,
        location: Location,
    ) {
        if let Some(all_facts) = self.all_facts {
            all_facts.cfg_edge.push((
                self.location_table.start_index(location),
                self.location_table.mid_index(location),
            ));

            let successor_blocks = terminator.successors();
            all_facts.cfg_edge.reserve(successor_blocks.size_hint().0);
            for successor_block in successor_blocks {
                all_facts.cfg_edge.push((
                    self.location_table.mid_index(location),
                    self.location_table
                        .start_index(successor_block.start_location()),
                ));
            }
        }

        // A `Call` terminator's return value can be a local which has borrows,
        // so we need to record those as `killed` as well.
        if let TerminatorKind::Call { ref destination, .. } = terminator.kind {
            if let Some((place, _)) = destination {
                self.record_killed_borrows_for_place(place, location);
            }
        }

        self.super_terminator(terminator, location);
    }

    fn visit_ascribe_user_ty(
        &mut self,
        _place: &Place<'tcx>,
        _variance: &ty::Variance,
        _user_ty: &UserTypeProjection,
        _location: Location,
    ) {
    }
}

impl<'cx, 'cg, 'tcx> ConstraintGeneration<'cx, 'cg, 'tcx> {
    /// Some variable with type `live_ty` is "regular live" at
    /// `location` -- i.e., it may be used later. This means that all
    /// regions appearing in the type `live_ty` must be live at
    /// `location`.
    fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location)
    where
        T: TypeFoldable<'tcx>,
    {
        debug!(
            "add_regular_live_constraint(live_ty={:?}, location={:?})",
            live_ty, location
        );

        self.infcx
            .tcx
            .for_each_free_region(&live_ty, |live_region| {
                let vid = live_region.to_region_vid();
                self.liveness_constraints.add_element(vid, location);
            });
    }

    /// When recording facts for Polonius, records the borrows on the specified place
    /// as `killed`. For example, when assigning to a local, or on a call's return destination.
    fn record_killed_borrows_for_place(&mut self, place: &Place<'tcx>, location: Location) {
        if let Some(all_facts) = self.all_facts {
            // Depending on the `Place` we're killing:
            // - if it's a local, or a single deref of a local,
            //   we kill all the borrows on the local.
            // - if it's a deeper projection, we have to filter which
            //   of the borrows are killed: the ones whose `borrowed_place`
            //   conflicts with the `place`.
            match place.as_ref() {
                PlaceRef {
                    base: &PlaceBase::Local(local),
                    projection: &[],
                } |
                PlaceRef {
                    base: &PlaceBase::Local(local),
                    projection: &[ProjectionElem::Deref],
                } => {
                    debug!(
                        "Recording `killed` facts for borrows of local={:?} at location={:?}",
                        local, location
                    );

                    record_killed_borrows_for_local(
                        all_facts,
                        self.borrow_set,
                        self.location_table,
                        &local,
                        location,
                    );
                }

                PlaceRef {
                    base: &PlaceBase::Static(_),
                    ..
                } => {
                    // Ignore kills of static or static mut variables.
                }

                PlaceRef {
                    base: &PlaceBase::Local(local),
                    projection: &[.., _],
                } => {
                    // Kill conflicting borrows of the innermost local.
                    debug!(
                        "Recording `killed` facts for borrows of \
                            innermost projected local={:?} at location={:?}",
                        local, location
                    );

                    if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) {
                        for &borrow_index in borrow_indices {
                            let places_conflict = places_conflict::places_conflict(
                                self.infcx.tcx,
                                self.param_env,
                                self.body,
                                &self.borrow_set.borrows[borrow_index].borrowed_place,
                                place,
                                places_conflict::PlaceConflictBias::NoOverlap,
                            );

                            if places_conflict {
                                let location_index = self.location_table.mid_index(location);
                                all_facts.killed.push((borrow_index, location_index));
                            }
                        }
                    }
                }
            }
        }
    }
}

/// When recording facts for Polonius, records the borrows on the specified local as `killed`.
fn record_killed_borrows_for_local(
    all_facts: &mut AllFacts,
    borrow_set: &BorrowSet<'_>,
    location_table: &LocationTable,
    local: &Local,
    location: Location,
) {
    if let Some(borrow_indices) = borrow_set.local_map.get(local) {
        all_facts.killed.reserve(borrow_indices.len());
        for &borrow_index in borrow_indices {
            let location_index = location_table.mid_index(location);
            all_facts.killed.push((borrow_index, location_index));
        }
    }
}