//! Liveness analysis which computes liveness of MIR local variables at the boundary of basic
//! blocks.
//!
//! This analysis considers references as being used only at the point of the
//! borrow. This means that this does not track uses because of references that
//! already exist:
//!
//! ```rust
//! fn foo() {
//!     x = 0;
//!     // `x` is live here ...
//!     GLOBAL = &x: *const u32;
//!     // ... but not here, even while it can be accessed through `GLOBAL`.
//!     foo();
//!     x = 1;
//!     // `x` is live again here, because it is assigned to `OTHER_GLOBAL`.
//!     OTHER_GLOBAL = &x: *const u32;
//!     // ...
//! }
//! ```
//!
//! This means that users of this analysis still have to check whether
//! pre-existing references can be used to access the value (e.g., at movable
//! generator yield points, all pre-existing references are invalidated, so this
//! doesn't matter).

use rustc::mir::visit::{
    PlaceContext, Visitor, MutatingUseContext, NonMutatingUseContext, NonUseContext,
};
use rustc::mir::Local;
use rustc::mir::*;
use rustc::ty::{self, TyCtxt};
use rustc_data_structures::bit_set::BitSet;
use rustc_data_structures::indexed_vec::{Idx, IndexVec};
use rustc_data_structures::work_queue::WorkQueue;
use std::fs;
use std::io::{self, Write};
use std::path::{Path, PathBuf};
use crate::transform::MirSource;
use crate::util::pretty::{dump_enabled, write_basic_block, write_mir_intro};

pub type LiveVarSet = BitSet<Local>;

/// This gives the result of the liveness analysis at the boundary of
/// basic blocks.
///
/// The `V` type defines the set of variables that we computed
/// liveness for. This is often `Local`, in which case we computed
/// liveness for all variables -- but it can also be some other type,
/// which indicates a subset of the variables within the graph.
pub struct LivenessResult {
    /// Live variables on exit to each basic block. This is equal to
    /// the union of the `ins` for each successor.
    pub outs: IndexVec<BasicBlock, LiveVarSet>,
}

/// Computes which local variables are live within the given function
/// `mir`, including drops.
pub fn liveness_of_locals(
    body: &Body<'_>,
) -> LivenessResult {
    let num_live_vars = body.local_decls.len();

    let def_use: IndexVec<_, DefsUses> = body
        .basic_blocks()
        .iter()
        .map(|b| block(b, num_live_vars))
        .collect();

    let mut outs: IndexVec<_, LiveVarSet> = body
        .basic_blocks()
        .indices()
        .map(|_| LiveVarSet::new_empty(num_live_vars))
        .collect();

    let mut bits = LiveVarSet::new_empty(num_live_vars);

    // The dirty queue contains the set of basic blocks whose entry sets have changed since they
    // were last processed. At the start of the analysis, we initialize the queue in post-order to
    // make it more likely that the entry set for a given basic block will have the effects of all
    // its successors in the CFG applied before it is processed.
    //
    // FIXME(ecstaticmorse): Reverse post-order on the reverse CFG may generate a better iteration
    // order when cycles are present, but the overhead of computing the reverse CFG may outweigh
    // any benefits. Benchmark this and find out.
    let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks().len());
    for (bb, _) in traversal::postorder(body) {
        dirty_queue.insert(bb);
    }

    // Add blocks which are not reachable from START_BLOCK to the work queue. These blocks will
    // be processed after the ones added above.
    for bb in body.basic_blocks().indices() {
        dirty_queue.insert(bb);
    }

    let predecessors = body.predecessors();

    while let Some(bb) = dirty_queue.pop() {
        // bits = use ∪ (bits - def)
        bits.overwrite(&outs[bb]);
        def_use[bb].apply(&mut bits);

        // `bits` now contains the live variables on entry. Therefore,
        // add `bits` to the `out` set for each predecessor; if those
        // bits were not already present, then enqueue the predecessor
        // as dirty.
        //
        // (note that `union` returns true if the `self` set changed)
        for &pred_bb in &predecessors[bb] {
            if outs[pred_bb].union(&bits) {
                dirty_queue.insert(pred_bb);
            }
        }
    }

    LivenessResult { outs }
}

#[derive(Eq, PartialEq, Clone)]
pub enum DefUse {
    Def,
    Use,
    Drop,
}

pub fn categorize(context: PlaceContext) -> Option<DefUse> {
    match context {
        ///////////////////////////////////////////////////////////////////////////
        // DEFS

        PlaceContext::MutatingUse(MutatingUseContext::Store) |

        // This is potentially both a def and a use...
        PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |

        // We let Call define the result in both the success and
        // unwind cases. This is not really correct, however it
        // does not seem to be observable due to the way that we
        // generate MIR. To do things properly, we would apply
        // the def in call only to the input from the success
        // path and not the unwind path. -nmatsakis
        PlaceContext::MutatingUse(MutatingUseContext::Call) |

        // Storage live and storage dead aren't proper defines, but we can ignore
        // values that come before them.
        PlaceContext::NonUse(NonUseContext::StorageLive) |
        PlaceContext::NonUse(NonUseContext::StorageDead) => Some(DefUse::Def),

        ///////////////////////////////////////////////////////////////////////////
        // REGULAR USES
        //
        // These are uses that occur *outside* of a drop. For the
        // purposes of NLL, these are special in that **all** the
        // lifetimes appearing in the variable must be live for each regular use.

        PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) |
        PlaceContext::MutatingUse(MutatingUseContext::Projection) |

        // Borrows only consider their local used at the point of the borrow.
        // This won't affect the results since we use this analysis for generators
        // and we only care about the result at suspension points. Borrows cannot
        // cross suspension points so this behavior is unproblematic.
        PlaceContext::MutatingUse(MutatingUseContext::Borrow) |
        PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow) |
        PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow) |
        PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow) |

        PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
        PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
        PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) |
        PlaceContext::NonUse(NonUseContext::AscribeUserTy) |
        PlaceContext::MutatingUse(MutatingUseContext::Retag) =>
            Some(DefUse::Use),

        ///////////////////////////////////////////////////////////////////////////
        // DROP USES
        //
        // These are uses that occur in a DROP (a MIR drop, not a
        // call to `std::mem::drop()`). For the purposes of NLL,
        // uses in drop are special because `#[may_dangle]`
        // attributes can affect whether lifetimes must be live.

        PlaceContext::MutatingUse(MutatingUseContext::Drop) =>
            Some(DefUse::Drop),
    }
}

struct DefsUsesVisitor
{
    defs_uses: DefsUses,
}

#[derive(Eq, PartialEq, Clone)]
struct DefsUses {
    defs: LiveVarSet,
    uses: LiveVarSet,
}

impl DefsUses {
    fn apply(&self, bits: &mut LiveVarSet) -> bool {
        bits.subtract(&self.defs) | bits.union(&self.uses)
    }

    fn add_def(&mut self, index: Local) {
        // If it was used already in the block, remove that use
        // now that we found a definition.
        //
        // Example:
        //
        //     // Defs = {X}, Uses = {}
        //     X = 5
        //     // Defs = {}, Uses = {X}
        //     use(X)
        self.uses.remove(index);
        self.defs.insert(index);
    }

    fn add_use(&mut self, index: Local) {
        // Inverse of above.
        //
        // Example:
        //
        //     // Defs = {}, Uses = {X}
        //     use(X)
        //     // Defs = {X}, Uses = {}
        //     X = 5
        //     // Defs = {}, Uses = {X}
        //     use(X)
        self.defs.remove(index);
        self.uses.insert(index);
    }
}

impl<'tcx> Visitor<'tcx> for DefsUsesVisitor
{
    fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
        match categorize(context) {
            Some(DefUse::Def) => self.defs_uses.add_def(local),
            Some(DefUse::Use) | Some(DefUse::Drop) => self.defs_uses.add_use(local),
            _ => (),
        }
    }
}

fn block(
    b: &BasicBlockData<'_>,
    locals: usize,
) -> DefsUses {
    let mut visitor = DefsUsesVisitor {
        defs_uses: DefsUses {
            defs: LiveVarSet::new_empty(locals),
            uses: LiveVarSet::new_empty(locals),
        },
    };

    let dummy_location = Location {
        block: BasicBlock::new(0),
        statement_index: 0,
    };

    // Visit the various parts of the basic block in reverse. If we go
    // forward, the logic in `add_def` and `add_use` would be wrong.
    visitor.visit_terminator(b.terminator(), dummy_location);
    for statement in b.statements.iter().rev() {
        visitor.visit_statement(statement, dummy_location);
    }

    visitor.defs_uses
}

pub fn dump_mir<'tcx>(
    tcx: TyCtxt<'tcx>,
    pass_name: &str,
    source: MirSource<'tcx>,
    body: &Body<'tcx>,
    result: &LivenessResult,
) {
    if !dump_enabled(tcx, pass_name, source) {
        return;
    }
    let node_path = ty::print::with_forced_impl_filename_line(|| {
        // see notes on #41697 below
        tcx.def_path_str(source.def_id())
    });
    dump_matched_mir_node(tcx, pass_name, &node_path, source, body, result);
}

fn dump_matched_mir_node<'tcx>(
    tcx: TyCtxt<'tcx>,
    pass_name: &str,
    node_path: &str,
    source: MirSource<'tcx>,
    body: &Body<'tcx>,
    result: &LivenessResult,
) {
    let mut file_path = PathBuf::new();
    file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir));
    let item_id = tcx.hir().as_local_hir_id(source.def_id()).unwrap();
    let file_name = format!("rustc.node{}{}-liveness.mir", item_id, pass_name);
    file_path.push(&file_name);
    let _ = fs::File::create(&file_path).and_then(|mut file| {
        writeln!(file, "// MIR local liveness analysis for `{}`", node_path)?;
        writeln!(file, "// source = {:?}", source)?;
        writeln!(file, "// pass_name = {}", pass_name)?;
        writeln!(file, "")?;
        write_mir_fn(tcx, source, body, &mut file, result)?;
        Ok(())
    });
}

pub fn write_mir_fn<'tcx>(
    tcx: TyCtxt<'tcx>,
    src: MirSource<'tcx>,
    body: &Body<'tcx>,
    w: &mut dyn Write,
    result: &LivenessResult,
) -> io::Result<()> {
    write_mir_intro(tcx, src, body, w)?;
    for block in body.basic_blocks().indices() {
        let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet>| {
            let live: Vec<String> = result[block]
                .iter()
                .map(|local| format!("{:?}", local))
                .collect();
            writeln!(w, "{} {{{}}}", prefix, live.join(", "))
        };
        write_basic_block(tcx, block, body, &mut |_, _| Ok(()), w)?;
        print(w, "   ", &result.outs)?;
        if block.index() + 1 != body.basic_blocks().len() {
            writeln!(w, "")?;
        }
    }

    writeln!(w, "}}")?;
    Ok(())
}