lowering.rs

// Copyright 2016 The RLS Project Developers.
//
// 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.

//! For processing the raw save-analysis data from rustc into the rls
//! in-memory representation.

use analysis::{Def, Glob, PerCrateAnalysis, Ref};
use data;
use raw::{self, RelationKind, CrateId, DefKind};
use {AResult, AnalysisHost, Id, Span, NULL};
use loader::AnalysisLoader;
use util;

use span;

use std::collections::{HashSet, HashMap};
use std::collections::hash_map::Entry;
use std::iter::Extend;
use std::path::{Path, PathBuf};
use std::time::Instant;
use std::u32;

use fst;
use itertools::Itertools;

// f is a function used to record the lowered crate into analysis.
pub fn lower<F, L>(
    raw_analysis: Vec<raw::Crate>,
    base_dir: &Path,
    analysis: &AnalysisHost<L>,
    mut f: F,
) -> AResult<()>
where
    F: FnMut(&AnalysisHost<L>, PerCrateAnalysis, CrateId) -> AResult<()>,
    L: AnalysisLoader,
{
    let rss = util::get_resident().unwrap_or(0);
    let t_start = Instant::now();

    // Keep a queue of crates that we are yet to overwrite as part of the lowering
    // process (to know which already-existing defs we can overwrite and lower)
    let mut invalidated_crates: Vec<_> = raw_analysis.iter().map(|c| c.id.clone()).collect();

    for c in raw_analysis {
        let t_start = Instant::now();

        let (per_crate, id) = CrateReader::read_crate(analysis, c, base_dir, &invalidated_crates);
        invalidated_crates.retain(|elem| *elem != id);

        let time = t_start.elapsed();
        info!(
            "Lowering {} in {:.2}s",
            format!("{} ({:?})", id.name, id.disambiguator),
            time.as_secs() as f64 + time.subsec_nanos() as f64 / 1_000_000_000.0
        );
        info!("    defs:  {}", per_crate.defs.len());
        info!("    refs:  {}", per_crate.ref_spans.len());
        info!("    globs: {}", per_crate.globs.len());

        f(analysis, per_crate, id)?;
    }

    let time = t_start.elapsed();
    let rss = util::get_resident().unwrap_or(0) as isize - rss as isize;
    info!(
        "Total lowering time: {:.2}s",
        time.as_secs() as f64 + time.subsec_nanos() as f64 / 1_000_000_000.0
    );
    info!("Diff in rss: {:.2}KB", rss as f64 / 1000.0);

    Ok(())
}

fn lower_span(raw_span: &raw::SpanData, base_dir: &Path, path_rewrite: &Option<PathBuf>) -> Span {
    let file_name = &raw_span.file_name;

    // Go from relative to absolute paths.
    let file_name = if let &Some(ref prefix) = path_rewrite {
        // Invariant: !file_name.is_absolute()
        // We don't assert this because better to have an incorrect span than to
        // panic.
        let prefix = &Path::new(prefix);
        prefix.join(file_name)
    } else if file_name.is_absolute() {
        file_name.to_owned()
    } else {
        base_dir.join(file_name)
    };

    // Rustc uses 1-indexed rows and columns, the RLS uses 0-indexed.
    span::Span::new(
        raw_span.line_start.zero_indexed(),
        raw_span.line_end.zero_indexed(),
        raw_span.column_start.zero_indexed(),
        raw_span.column_end.zero_indexed(),
        file_name,
    )
}

/// Responsible for processing the raw `data::Analysis`, including translating
/// from local crate ids to global crate ids, and creating lowered
/// `PerCrateAnalysis`.
struct CrateReader<'a> {
    /// This is effectively a map from local crate id -> global crate id, where
    /// local crate id are indices 0...external_crate_count.
    crate_map: Vec<u32>,
    base_dir: PathBuf,
    crate_name: String,
    path_rewrite: Option<PathBuf>,
    crate_homonyms: Vec<CrateId>,
    /// List of crates that are invalidated (replaced) as part of the current
    /// lowering process. These will be overriden and their definitions should
    /// not be taken into account when checking if we need to ignore duplicated
    /// item.
    invalidated_crates: &'a [CrateId],
}

impl<'a> CrateReader<'a> {
    fn from_prelude(
        mut prelude: raw::CratePreludeData,
        master_crate_map: &mut HashMap<CrateId, u32>,
        base_dir: &Path,
        path_rewrite: Option<PathBuf>,
        invalidated_crates: &'a [CrateId],
    ) -> CrateReader<'a> {
        fn fetch_crate_index(map: &mut HashMap<CrateId, u32>,
                             id: CrateId) -> u32 {
            let next = map.len() as u32;
            *map.entry(id).or_insert(next)
        }
        // When reading a local crate and its external crates, we need to:
        // 1. Update a global crate id map if we encounter any new crate
        // 2. Prepare a local crate id -> global crate id map, so we can easily
        // map those when lowering symbols with local crate ids into global registry
        // It's worth noting, that we assume that local crate id is 0, whereas
        // the external crates will have num in 1..count contiguous range.
        let crate_id = prelude.crate_id;
        trace!("building crate map for {:?}", crate_id);
        let index = fetch_crate_index(master_crate_map, crate_id.clone());
        let mut crate_map = vec![index];
        trace!("  {} -> {}", crate_id.name, master_crate_map[&crate_id]);

        prelude.external_crates.sort_by(|a, b| a.num.cmp(&b.num));
        for c in prelude.external_crates {
            assert!(c.num == crate_map.len() as u32);
            let index = fetch_crate_index(master_crate_map, c.id.clone());
            crate_map.push(index);
            trace!("  {} -> {}", c.id.name, master_crate_map[&c.id]);
        }

        CrateReader {
            crate_map,
            base_dir: base_dir.to_owned(),
            crate_homonyms: master_crate_map.keys().filter(|cid| cid.name == crate_id.name).cloned().collect(),
            crate_name: crate_id.name,
            path_rewrite,
            invalidated_crates,
        }
    }

    /// Lowers a given `raw::Crate` into `AnalysisHost`.
    fn read_crate<L: AnalysisLoader>(
        project_analysis: &AnalysisHost<L>,
        krate: raw::Crate,
        base_dir: &Path,
        invalidated_crates: &[CrateId],
    ) -> (PerCrateAnalysis, CrateId) {
        let reader = CrateReader::from_prelude(
            krate.analysis.prelude.unwrap(),
            &mut project_analysis.master_crate_map.lock().unwrap(),
            base_dir,
            krate.path_rewrite,
            invalidated_crates,
        );

        let mut per_crate = PerCrateAnalysis::new(krate.timestamp, krate.path);

        let is_distro_crate = krate.analysis.config.distro_crate;
        reader.read_defs(krate.analysis.defs, &mut per_crate, is_distro_crate, project_analysis);
        reader.read_imports(krate.analysis.imports, &mut per_crate, project_analysis);
        reader.read_refs(krate.analysis.refs, &mut per_crate, project_analysis);
        reader.read_impls(krate.analysis.relations, &mut per_crate, project_analysis);
        per_crate.global_crate_num = reader.crate_map[0];

        {
            let analysis = &mut project_analysis.analysis.lock().unwrap();
            analysis.as_mut()
                .unwrap()
                .crate_names
                .entry(krate.id.name.clone())
                .or_insert_with(|| vec![])
                .push(krate.id.clone());
        }

        (per_crate, krate.id)
    }

    fn read_imports<L: AnalysisLoader>(
        &self,
        imports: Vec<raw::Import>,
        analysis: &mut PerCrateAnalysis,
        project_analysis: &AnalysisHost<L>,
    ) {
        for i in imports {
            let span = lower_span(&i.span, &self.base_dir, &self.path_rewrite);
            if !i.value.is_empty() {
                // A glob import.
                if !self.has_congruent_glob(&span, project_analysis) {
                    let glob = Glob { value: i.value };
                    trace!("record glob {:?} {:?}", span, glob);
                    analysis.globs.insert(span, glob);
                }
            } else if let Some(ref ref_id) = i.ref_id {
                // Import where we know the referred def.
                let def_id = self.id_from_compiler_id(ref_id);
                self.record_ref(def_id, span, analysis, project_analysis);
                if let Some(alias_span) = i.alias_span {
                    let alias_span = lower_span(&alias_span, &self.base_dir, &self.path_rewrite);
                    self.record_ref(def_id, alias_span, analysis, project_analysis);
                    let mut analysis = project_analysis.analysis.lock().unwrap();
                    analysis.as_mut().unwrap().aliased_imports.insert(def_id);
                }
            }
        }
    }

    fn record_ref<L: AnalysisLoader>(
        &self,
        def_id: Id,
        span: Span,
        analysis: &mut PerCrateAnalysis,
        project_analysis: &AnalysisHost<L>,
    ) {
        if def_id != NULL && (project_analysis.has_def(def_id) || analysis.defs.contains_key(&def_id)) {
            trace!("record_ref {:?} {}", span, def_id);
            match analysis.def_id_for_span.entry(span.clone()) {
                Entry::Occupied(mut oe) => {
                    let new = oe.get().add_id(def_id);
                    oe.insert(new);
                }
                Entry::Vacant(ve) => {
                    ve.insert(Ref::Id(def_id));
                }
            }
            analysis
                .ref_spans
                .entry(def_id)
                .or_insert_with(|| vec![])
                .push(span);
        }
    }

    // We are sometimes asked to analyze the same crate twice. This can happen due to duplicate data,
    // but more frequently is due to compiling it twice with different Cargo targets (e.g., bin and test).
    // In that case there will be two crates with the same names, but different disambiguators. We
    // want to ensure that we only record defs once, even if the defintion is in multiple crates.
    // So we compare the crate-local id and span and skip any subsequent defs which match already
    // present defs.
    fn has_congruent_def<L: AnalysisLoader>(&self, local_id: u32, span: &Span, project_analysis: &AnalysisHost<L>) -> bool {
        self.has_congruent_item(project_analysis, |per_crate| per_crate.has_congruent_def(local_id, span))
    }

    fn has_congruent_glob<L: AnalysisLoader>(&self, span: &Span, project_analysis: &AnalysisHost<L>) -> bool {
        self.has_congruent_item(project_analysis, |per_crate| per_crate.globs.contains_key(span))
    }

    fn has_congruent_item<L, P>(&self, project_analysis: &AnalysisHost<L>, pred: P) -> bool
        where
            L: AnalysisLoader,
            P: Fn(&PerCrateAnalysis) -> bool,
    {
        if self.crate_homonyms.is_empty() {
            return false;
        }

        let project_analysis = project_analysis.analysis.lock().unwrap();
        let project_analysis = project_analysis.as_ref().unwrap();

        // Don't take into account crates that we are about to replace as part
        // of the lowering. This often happens when we reload definitions for
        // the same crate. Naturally most of the definitions will stay the same
        // for incremental changes but will be overwritten - don't ignore them!
        let homonyms_to_consider = self
            .crate_homonyms
            .iter()
            .filter(|c| !self.invalidated_crates.contains(c));

        homonyms_to_consider
            .filter_map(|ch| project_analysis.per_crate.get(ch))
            .any(pred)
    }

    fn read_defs<L: AnalysisLoader>(
        &self,
        defs: Vec<raw::Def>,
        analysis: &mut PerCrateAnalysis,
        distro_crate: bool,
        project_analysis: &AnalysisHost<L>,
    ) {
        let mut defs_to_index = Vec::new();
        for d in defs {
            if bad_span(&d.span, d.kind == DefKind::Mod) {
                continue;
            }
            let span = lower_span(&d.span, &self.base_dir, &self.path_rewrite);
            if self.has_congruent_def(d.id.index, &span, project_analysis) {
                trace!("read_defs: has_congruent_def({}, {:?}), skipping", d.id.index, span);
                continue;
            }

            let id = self.id_from_compiler_id(&d.id);
            if id != NULL && !analysis.defs.contains_key(&id) {
                let file_name = span.file.clone();
                analysis
                    .defs_per_file
                    .entry(file_name)
                    .or_insert_with(|| vec![])
                    .push(id);
                let decl_id = match d.decl_id {
                    Some(ref decl_id) => {
                        let def_id = self.id_from_compiler_id(decl_id);
                        analysis
                            .ref_spans
                            .entry(def_id)
                            .or_insert_with(|| vec![])
                            .push(span.clone());
                        Ref::Id(def_id)
                    }
                    None => Ref::Id(id),
                };
                match analysis.def_id_for_span.entry(span.clone()) {
                    Entry::Occupied(_) => {
                        debug!("def already exists at span: {:?} {:?}", span, d);
                    }
                    Entry::Vacant(ve) => {
                        ve.insert(decl_id);
                    }
                }

                analysis
                    .def_names
                    .entry(d.name.clone())
                    .or_insert_with(|| vec![])
                    .push(id);

                // NOTE not every Def will have a name, e.g. test_data/hello/src/main is analyzed with an implicit module
                // that's fine, but no need to index in def_trie
                if d.name != "" {
                    defs_to_index.push((d.name.to_lowercase(), id));
                }

                let parent = d.parent.map(|id| self.id_from_compiler_id(&id));
                if let Some(parent) = parent {
                    let children = analysis
                        .children
                        .entry(parent)
                        .or_insert_with(HashSet::new);
                    children.insert(id);
                }
                if !d.children.is_empty() {
                    let children_for_id = analysis.children.entry(id).or_insert_with(HashSet::new);
                    children_for_id
                        .extend(d.children.iter().map(|id| self.id_from_compiler_id(id)));
                }

                let def = Def {
                    kind: d.kind,
                    span: span,
                    name: d.name,
                    value: d.value,
                    qualname: format!("{}{}", self.crate_name, d.qualname),
                    distro_crate,
                    parent: parent,
                    docs: d.docs,
                    // sig: d.sig.map(|ref s| self.lower_sig(s, &self.base_dir)),
                };
                trace!(
                    "record def: {:?}/{:?} ({}): {:?}",
                    id,
                    d.id,
                    self.crate_map[d.id.krate as usize],
                    def
                );

                if d.kind == super::raw::DefKind::Mod && def.name == "" {
                    assert!(analysis.root_id.is_none());
                    analysis.root_id = Some(id);
                }

                analysis.defs.insert(id, def);
            }
        }

        let (def_fst, def_fst_values) = build_index(defs_to_index);
        analysis.def_fst = def_fst;
        analysis.def_fst_values = def_fst_values;

        // We must now run a pass over the defs setting parents, because
        // save-analysis often omits parent info.
        for (parent, children) in &analysis.children {
            for c in children {
                analysis
                    .defs
                    .get_mut(c)
                    .map(|def| def.parent = Some(*parent));
            }
        }
    }

    fn read_refs<L: AnalysisLoader>(
        &self,
        refs: Vec<raw::Ref>,
        analysis: &mut PerCrateAnalysis,
        project_analysis: &AnalysisHost<L>,
    ) {
        for r in refs {
            if r.span.file_name.to_str().map(|s| s.ends_with('>')).unwrap_or(true) {
                continue;
            }
            let def_id = self.id_from_compiler_id(&r.ref_id);
            let span = lower_span(&r.span, &self.base_dir, &self.path_rewrite);
            self.record_ref(def_id, span, analysis, project_analysis);
        }
    }

    fn read_impls<L: AnalysisLoader>(
        &self,
        relations: Vec<raw::Relation>,
        analysis: &mut PerCrateAnalysis,
        project_analysis: &AnalysisHost<L>,
    ) {
        for r in relations {
            match r.kind {
                RelationKind::Impl { .. } => {}
                _ => continue,
            }
            let self_id = self.id_from_compiler_id(&r.from);
            let trait_id = self.id_from_compiler_id(&r.to);
            let span = lower_span(&r.span, &self.base_dir, &self.path_rewrite);
            if self_id != NULL {
                if let Some(self_id) = abs_ref_id(self_id, analysis, project_analysis) {
                    trace!("record impl for self type {:?} {}", span, self_id);
                    analysis
                        .impls
                        .entry(self_id)
                        .or_insert_with(|| vec![])
                        .push(span.clone());
                }
            }
            if trait_id != NULL {
                if let Some(trait_id) = abs_ref_id(trait_id, analysis, project_analysis) {
                    trace!("record impl for trait {:?} {}", span, trait_id);
                    analysis
                        .impls
                        .entry(trait_id)
                        .or_insert_with(|| vec![])
                        .push(span);
                }
            }
        }
    }

    // fn lower_sig(&self, raw_sig: &raw::Signature, base_dir: &Path) -> Signature {
    //     Signature {
    //         span: lower_span(&raw_sig.span, base_dir, &self.path_rewrite),
    //         text: raw_sig.text.clone(),
    //         ident_start: raw_sig.ident_start as u32,
    //         ident_end: raw_sig.ident_end as u32,
    //         defs: raw_sig.defs.iter().map(|se| self.lower_sig_element(se)).collect(),
    //         refs: raw_sig.refs.iter().map(|se| self.lower_sig_element(se)).collect(),
    //     }
    // }

    // fn lower_sig_element(&self, raw_se: &raw::SigElement) -> SigElement {
    //     SigElement {
    //         id: self.id_from_compiler_id(&raw_se.id),
    //         start: raw_se.start,
    //         end: raw_se.end,
    //     }
    // }

    /// Recreates resulting crate-local (`u32`, `u32`) id from compiler
    /// to a global `u64` `Id`, mapping from a local to global crate id.
    fn id_from_compiler_id(&self, id: &data::Id) -> Id {
        if id.krate == u32::MAX || id.index == u32::MAX {
            return NULL;
        }

        let krate = self.crate_map[id.krate as usize];
        Id::from_crate_and_local(krate, id.index)
    }
}

fn abs_ref_id<L: AnalysisLoader>(
    id: Id,
    analysis: &PerCrateAnalysis,
    project_analysis: &AnalysisHost<L>,
) -> Option<Id> {
    if project_analysis.has_def(id) || analysis.defs.contains_key(&id) {
        return Some(id);
    }

    // TODO
    None
}

fn build_index(mut defs: Vec<(String, Id)>) -> (fst::Map, Vec<Vec<Id>>) {
    defs.sort_by(|(n1, _), (n2, _)| n1.cmp(n2));
    let by_name = defs.into_iter().group_by(|(n, _)| n.clone());

    let mut values: Vec<Vec<Id>> = Vec::new();
    let fst = {
        let defs = by_name.into_iter().enumerate().map(|(i, (name, defs))| {
            values.push(defs.map(|(_, id)| id).collect());
            (name, i as u64)
        });
        fst::Map::from_iter(defs).expect("defs are sorted by lowercase name")
    };
    (fst, values)
}

fn bad_span(span: &raw::SpanData, is_mod: bool) -> bool {
    span.file_name.to_str().map(|s| s.ends_with('>')).unwrap_or(true) ||
        (!is_mod &&
         span.byte_start == 0 &&
         span.byte_end == 0)
}