values.rs

// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use rustc::mir::{BasicBlock, Location, Mir};
use rustc::ty::{self, RegionVid};
use rustc_data_structures::bit_set::{HybridBitSet, SparseBitMatrix};
use rustc_data_structures::fx::FxHashMap;
use rustc_data_structures::indexed_vec::Idx;
use rustc_data_structures::indexed_vec::IndexVec;
use std::fmt::Debug;
use std::rc::Rc;

/// Maps between a `Location` and a `PointIndex` (and vice versa).
crate struct RegionValueElements {
    /// For each basic block, how many points are contained within?
    statements_before_block: IndexVec<BasicBlock, usize>,

    /// Map backward from each point to the basic block that it
    /// belongs to.
    basic_blocks: IndexVec<PointIndex, BasicBlock>,

    num_points: usize,
}

impl RegionValueElements {
    crate fn new(mir: &Mir<'_>) -> Self {
        let mut num_points = 0;
        let statements_before_block: IndexVec<BasicBlock, usize> = mir.basic_blocks()
            .iter()
            .map(|block_data| {
                let v = num_points;
                num_points += block_data.statements.len() + 1;
                v
            })
            .collect();
        debug!(
            "RegionValueElements: statements_before_block={:#?}",
            statements_before_block
        );
        debug!("RegionValueElements: num_points={:#?}", num_points);

        let mut basic_blocks = IndexVec::with_capacity(num_points);
        for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
            basic_blocks.extend((0..bb_data.statements.len() + 1).map(|_| bb));
        }

        Self {
            statements_before_block,
            basic_blocks,
            num_points,
        }
    }

    /// Total number of point indices
    crate fn num_points(&self) -> usize {
        self.num_points
    }

    /// Converts a `Location` into a `PointIndex`. O(1).
    crate fn point_from_location(&self, location: Location) -> PointIndex {
        let Location {
            block,
            statement_index,
        } = location;
        let start_index = self.statements_before_block[block];
        PointIndex::new(start_index + statement_index)
    }

    /// Converts a `Location` into a `PointIndex`. O(1).
    crate fn entry_point(&self, block: BasicBlock) -> PointIndex {
        let start_index = self.statements_before_block[block];
        PointIndex::new(start_index)
    }

    /// Converts a `PointIndex` back to a location. O(1).
    crate fn to_location(&self, index: PointIndex) -> Location {
        assert!(index.index() < self.num_points);
        let block = self.basic_blocks[index];
        let start_index = self.statements_before_block[block];
        let statement_index = index.index() - start_index;
        Location {
            block,
            statement_index,
        }
    }

    /// Sometimes we get point-indices back from bitsets that may be
    /// out of range (because they round up to the nearest 2^N number
    /// of bits). Use this function to filter such points out if you
    /// like.
    crate fn point_in_range(&self, index: PointIndex) -> bool {
        index.index() < self.num_points
    }

    /// Pushes all predecessors of `index` onto `stack`.
    crate fn push_predecessors(
        &self,
        mir: &Mir<'_>,
        index: PointIndex,
        stack: &mut Vec<PointIndex>,
    ) {
        let Location {
            block,
            statement_index,
        } = self.to_location(index);
        if statement_index == 0 {
            // If this is a basic block head, then the predecessors are
            // the terminators of other basic blocks
            stack.extend(
                mir.predecessors_for(block)
                    .iter()
                    .map(|&pred_bb| mir.terminator_loc(pred_bb))
                    .map(|pred_loc| self.point_from_location(pred_loc)),
            );
        } else {
            // Otherwise, the pred is just the previous statement
            stack.push(PointIndex::new(index.index() - 1));
        }
    }
}

/// A single integer representing a `Location` in the MIR control-flow
/// graph. Constructed efficiently from `RegionValueElements`.
newtype_index! {
    pub struct PointIndex { DEBUG_FORMAT = "PointIndex({})" }
}

/// A single integer representing a `ty::Placeholder`.
newtype_index! {
    pub struct PlaceholderIndex { DEBUG_FORMAT = "PlaceholderIndex({})" }
}

/// An individual element in a region value -- the value of a
/// particular region variable consists of a set of these elements.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
crate enum RegionElement {
    /// A point in the control-flow graph.
    Location(Location),

    /// A universally quantified region from the root universe (e.g.,
    /// a lifetime parameter).
    RootUniversalRegion(RegionVid),

    /// A placeholder (e.g., instantiated from a `for<'a> fn(&'a u32)`
    /// type).
    PlaceholderRegion(ty::Placeholder),
}

/// When we initially compute liveness, we use a bit matrix storing
/// points for each region-vid.
crate struct LivenessValues<N: Idx> {
    elements: Rc<RegionValueElements>,
    points: SparseBitMatrix<N, PointIndex>,
}

impl<N: Idx> LivenessValues<N> {
    /// Creates a new set of "region values" that tracks causal information.
    /// Each of the regions in num_region_variables will be initialized with an
    /// empty set of points and no causal information.
    crate fn new(elements: &Rc<RegionValueElements>) -> Self {
        Self {
            elements: elements.clone(),
            points: SparseBitMatrix::new(elements.num_points),
        }
    }

    /// Iterate through each region that has a value in this set.
    crate fn rows<'a>(&'a self) -> impl Iterator<Item = N> {
        self.points.rows()
    }

    /// Adds the given element to the value for the given region. Returns true if
    /// the element is newly added (i.e., was not already present).
    crate fn add_element(&mut self, row: N, location: Location) -> bool {
        debug!("LivenessValues::add(r={:?}, location={:?})", row, location);
        let index = self.elements.point_from_location(location);
        self.points.insert(row, index)
    }

    /// Adds all the elements in the given bit array into the given
    /// region. Returns true if any of them are newly added.
    crate fn add_elements(&mut self, row: N, locations: &HybridBitSet<PointIndex>) -> bool {
        debug!(
            "LivenessValues::add_elements(row={:?}, locations={:?})",
            row, locations
        );
        self.points.union_into_row(row, locations)
    }

    /// Adds all the control-flow points to the values for `r`.
    crate fn add_all_points(&mut self, row: N) {
        self.points.insert_all_into_row(row);
    }

    /// True if the region `r` contains the given element.
    crate fn contains(&self, row: N, location: Location) -> bool {
        let index = self.elements.point_from_location(location);
        self.points.contains(row, index)
    }

    /// Returns a "pretty" string value of the region. Meant for debugging.
    crate fn region_value_str(&self, r: N) -> String {
        region_value_str(
            self.points
                .row(r)
                .into_iter()
                .flat_map(|set| set.iter())
                .take_while(|&p| self.elements.point_in_range(p))
                .map(|p| self.elements.to_location(p))
                .map(RegionElement::Location),
        )
    }
}

/// Maps from `ty::Placeholder` values that are used in the rest of
/// rustc to the internal `PlaceholderIndex` values that are used in
/// NLL.
#[derive(Default)]
crate struct PlaceholderIndices {
    to_index: FxHashMap<ty::Placeholder, PlaceholderIndex>,
    from_index: IndexVec<PlaceholderIndex, ty::Placeholder>,
}

impl PlaceholderIndices {
    crate fn insert(&mut self, placeholder: ty::Placeholder) -> PlaceholderIndex {
        let PlaceholderIndices {
            to_index,
            from_index,
        } = self;
        *to_index
            .entry(placeholder)
            .or_insert_with(|| from_index.push(placeholder))
    }

    crate fn lookup_index(&self, placeholder: ty::Placeholder) -> PlaceholderIndex {
        self.to_index[&placeholder]
    }

    crate fn lookup_placeholder(&self, placeholder: PlaceholderIndex) -> ty::Placeholder {
        self.from_index[placeholder]
    }

    crate fn len(&self) -> usize {
        self.from_index.len()
    }
}

/// Stores the full values for a set of regions (in contrast to
/// `LivenessValues`, which only stores those points in the where a
/// region is live). The full value for a region may contain points in
/// the CFG, but also free regions as well as bound universe
/// placeholders.
///
/// Example:
///
/// ```text
/// fn foo(x: &'a u32) -> &'a u32 {
///    let y: &'0 u32 = x; // let's call this `'0`
///    y
/// }
/// ```
///
/// Here, the variable `'0` would contain the free region `'a`,
/// because (since it is returned) it must live for at least `'a`. But
/// it would also contain various points from within the function.
#[derive(Clone)]
crate struct RegionValues<N: Idx> {
    elements: Rc<RegionValueElements>,
    placeholder_indices: Rc<PlaceholderIndices>,
    points: SparseBitMatrix<N, PointIndex>,
    free_regions: SparseBitMatrix<N, RegionVid>,

    /// Placeholders represent bound regions -- so something like `'a`
    /// in for<'a> fn(&'a u32)`.
    placeholders: SparseBitMatrix<N, PlaceholderIndex>,
}

impl<N: Idx> RegionValues<N> {
    /// Creates a new set of "region values" that tracks causal information.
    /// Each of the regions in num_region_variables will be initialized with an
    /// empty set of points and no causal information.
    crate fn new(
        elements: &Rc<RegionValueElements>,
        num_universal_regions: usize,
        placeholder_indices: &Rc<PlaceholderIndices>,
    ) -> Self {
        let num_placeholders = placeholder_indices.len();
        Self {
            elements: elements.clone(),
            points: SparseBitMatrix::new(elements.num_points),
            placeholder_indices: placeholder_indices.clone(),
            free_regions: SparseBitMatrix::new(num_universal_regions),
            placeholders: SparseBitMatrix::new(num_placeholders),
        }
    }

    /// Adds the given element to the value for the given region. Returns true if
    /// the element is newly added (i.e., was not already present).
    crate fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool {
        debug!("add(r={:?}, elem={:?})", r, elem);
        elem.add_to_row(self, r)
    }

    /// Adds all the control-flow points to the values for `r`.
    crate fn add_all_points(&mut self, r: N) {
        self.points.insert_all_into_row(r);
    }

    /// Add all elements in `r_from` to `r_to` (because e.g. `r_to:
    /// r_from`).
    crate fn add_region(&mut self, r_to: N, r_from: N) -> bool {
        self.points.union_rows(r_from, r_to)
            | self.free_regions.union_rows(r_from, r_to)
            | self.placeholders.union_rows(r_from, r_to)
    }

    /// True if the region `r` contains the given element.
    crate fn contains(&self, r: N, elem: impl ToElementIndex) -> bool {
        elem.contained_in_row(self, r)
    }

    /// `self[to] |= values[from]`, essentially: that is, take all the
    /// elements for the region `from` from `values` and add them to
    /// the region `to` in `self`.
    crate fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) {
        if let Some(set) = values.points.row(from) {
            self.points.union_into_row(to, set);
        }
    }

    /// True if `sup_region` contains all the CFG points that
    /// `sub_region` contains. Ignores universal regions.
    crate fn contains_points(&self, sup_region: N, sub_region: N) -> bool {
        if let Some(sub_row) = self.points.row(sub_region) {
            if let Some(sup_row) = self.points.row(sup_region) {
                sup_row.superset(sub_row)
            } else {
                // sup row is empty, so sub row must be empty
                sub_row.is_empty()
            }
        } else {
            // sub row is empty, always true
            true
        }
    }

    /// Returns the locations contained within a given region `r`.
    crate fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a {
        self.points.row(r).into_iter().flat_map(move |set| {
            set.iter()
                .take_while(move |&p| self.elements.point_in_range(p))
                .map(move |p| self.elements.to_location(p))
        })
    }

    /// Returns just the universal regions that are contained in a given region's value.
    crate fn universal_regions_outlived_by<'a>(
        &'a self,
        r: N,
    ) -> impl Iterator<Item = RegionVid> + 'a {
        self.free_regions
            .row(r)
            .into_iter()
            .flat_map(|set| set.iter())
    }

    /// Returns all the elements contained in a given region's value.
    crate fn placeholders_contained_in<'a>(
        &'a self,
        r: N,
    ) -> impl Iterator<Item = ty::Placeholder> + 'a {
        self.placeholders
            .row(r)
            .into_iter()
            .flat_map(|set| set.iter())
            .map(move |p| self.placeholder_indices.lookup_placeholder(p))
    }

    /// Returns all the elements contained in a given region's value.
    crate fn elements_contained_in<'a>(&'a self, r: N) -> impl Iterator<Item = RegionElement> + 'a {
        let points_iter = self.locations_outlived_by(r).map(RegionElement::Location);

        let free_regions_iter = self.universal_regions_outlived_by(r)
            .map(RegionElement::RootUniversalRegion);

        let placeholder_universes_iter = self.placeholders_contained_in(r)
            .map(RegionElement::PlaceholderRegion);

        points_iter
            .chain(free_regions_iter)
            .chain(placeholder_universes_iter)
    }

    /// Returns a "pretty" string value of the region. Meant for debugging.
    crate fn region_value_str(&self, r: N) -> String {
        region_value_str(self.elements_contained_in(r))
    }
}

crate trait ToElementIndex: Debug + Copy {
    fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool;

    fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool;
}

impl ToElementIndex for Location {
    fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
        let index = values.elements.point_from_location(self);
        values.points.insert(row, index)
    }

    fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
        let index = values.elements.point_from_location(self);
        values.points.contains(row, index)
    }
}

impl ToElementIndex for RegionVid {
    fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
        values.free_regions.insert(row, self)
    }

    fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
        values.free_regions.contains(row, self)
    }
}

impl ToElementIndex for ty::Placeholder {
    fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
        let index = values.placeholder_indices.lookup_index(self);
        values.placeholders.insert(row, index)
    }

    fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
        let index = values.placeholder_indices.lookup_index(self);
        values.placeholders.contains(row, index)
    }
}

crate fn location_set_str(
    elements: &RegionValueElements,
    points: impl IntoIterator<Item = PointIndex>,
) -> String {
    region_value_str(
        points
            .into_iter()
            .take_while(|&p| elements.point_in_range(p))
            .map(|p| elements.to_location(p))
            .map(RegionElement::Location),
    )
}

fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String {
    let mut result = String::new();
    result.push_str("{");

    // Set to Some(l1, l2) when we have observed all the locations
    // from l1..=l2 (inclusive) but not yet printed them. This
    // gets extended if we then see l3 where l3 is the successor
    // to l2.
    let mut open_location: Option<(Location, Location)> = None;

    let mut sep = "";
    let mut push_sep = |s: &mut String| {
        s.push_str(sep);
        sep = ", ";
    };

    for element in elements {
        match element {
            RegionElement::Location(l) => {
                if let Some((location1, location2)) = open_location {
                    if location2.block == l.block
                        && location2.statement_index == l.statement_index - 1
                    {
                        open_location = Some((location1, l));
                        continue;
                    }

                    push_sep(&mut result);
                    push_location_range(&mut result, location1, location2);
                }

                open_location = Some((l, l));
            }

            RegionElement::RootUniversalRegion(fr) => {
                if let Some((location1, location2)) = open_location {
                    push_sep(&mut result);
                    push_location_range(&mut result, location1, location2);
                    open_location = None;
                }

                push_sep(&mut result);
                result.push_str(&format!("{:?}", fr));
            }

            RegionElement::PlaceholderRegion(placeholder) => {
                if let Some((location1, location2)) = open_location {
                    push_sep(&mut result);
                    push_location_range(&mut result, location1, location2);
                    open_location = None;
                }

                push_sep(&mut result);
                result.push_str(&format!("{:?}", placeholder));
            }
        }
    }

    if let Some((location1, location2)) = open_location {
        push_sep(&mut result);
        push_location_range(&mut result, location1, location2);
    }

    result.push_str("}");

    return result;

    fn push_location_range(str: &mut String, location1: Location, location2: Location) {
        if location1 == location2 {
            str.push_str(&format!("{:?}", location1));
        } else {
            assert_eq!(location1.block, location2.block);
            str.push_str(&format!(
                "{:?}[{}..={}]",
                location1.block, location1.statement_index, location2.statement_index
            ));
        }
    }
}