//! Finds crate binaries and loads their metadata
//!
//! Might I be the first to welcome you to a world of platform differences,
//! version requirements, dependency graphs, conflicting desires, and fun! This
//! is the major guts (along with metadata::creader) of the compiler for loading
//! crates and resolving dependencies. Let's take a tour!
//!
//! # The problem
//!
//! Each invocation of the compiler is immediately concerned with one primary
//! problem, to connect a set of crates to resolved crates on the filesystem.
//! Concretely speaking, the compiler follows roughly these steps to get here:
//!
//! 1. Discover a set of `extern crate` statements.
//! 2. Transform these directives into crate names. If the directive does not
//!    have an explicit name, then the identifier is the name.
//! 3. For each of these crate names, find a corresponding crate on the
//!    filesystem.
//!
//! Sounds easy, right? Let's walk into some of the nuances.
//!
//! ## Transitive Dependencies
//!
//! Let's say we've got three crates: A, B, and C. A depends on B, and B depends
//! on C. When we're compiling A, we primarily need to find and locate B, but we
//! also end up needing to find and locate C as well.
//!
//! The reason for this is that any of B's types could be composed of C's types,
//! any function in B could return a type from C, etc. To be able to guarantee
//! that we can always type-check/translate any function, we have to have
//! complete knowledge of the whole ecosystem, not just our immediate
//! dependencies.
//!
//! So now as part of the "find a corresponding crate on the filesystem" step
//! above, this involves also finding all crates for *all upstream
//! dependencies*. This includes all dependencies transitively.
//!
//! ## Rlibs and Dylibs
//!
//! The compiler has two forms of intermediate dependencies. These are dubbed
//! rlibs and dylibs for the static and dynamic variants, respectively. An rlib
//! is a rustc-defined file format (currently just an ar archive) while a dylib
//! is a platform-defined dynamic library. Each library has a metadata somewhere
//! inside of it.
//!
//! A third kind of dependency is an rmeta file. These are metadata files and do
//! not contain any code, etc. To a first approximation, these are treated in the
//! same way as rlibs. Where there is both an rlib and an rmeta file, the rlib
//! gets priority (even if the rmeta file is newer). An rmeta file is only
//! useful for checking a downstream crate, attempting to link one will cause an
//! error.
//!
//! When translating a crate name to a crate on the filesystem, we all of a
//! sudden need to take into account both rlibs and dylibs! Linkage later on may
//! use either one of these files, as each has their pros/cons. The job of crate
//! loading is to discover what's possible by finding all candidates.
//!
//! Most parts of this loading systems keep the dylib/rlib as just separate
//! variables.
//!
//! ## Where to look?
//!
//! We can't exactly scan your whole hard drive when looking for dependencies,
//! so we need to places to look. Currently the compiler will implicitly add the
//! target lib search path ($prefix/lib/rustlib/$target/lib) to any compilation,
//! and otherwise all -L flags are added to the search paths.
//!
//! ## What criterion to select on?
//!
//! This a pretty tricky area of loading crates. Given a file, how do we know
//! whether it's the right crate? Currently, the rules look along these lines:
//!
//! 1. Does the filename match an rlib/dylib pattern? That is to say, does the
//!    filename have the right prefix/suffix?
//! 2. Does the filename have the right prefix for the crate name being queried?
//!    This is filtering for files like `libfoo*.rlib` and such. If the crate
//!    we're looking for was originally compiled with -C extra-filename, the
//!    extra filename will be included in this prefix to reduce reading
//!    metadata from crates that would otherwise share our prefix.
//! 3. Is the file an actual rust library? This is done by loading the metadata
//!    from the library and making sure it's actually there.
//! 4. Does the name in the metadata agree with the name of the library?
//! 5. Does the target in the metadata agree with the current target?
//! 6. Does the SVH match? (more on this later)
//!
//! If the file answers `yes` to all these questions, then the file is
//! considered as being *candidate* for being accepted. It is illegal to have
//! more than two candidates as the compiler has no method by which to resolve
//! this conflict. Additionally, rlib/dylib candidates are considered
//! separately.
//!
//! After all this has happened, we have 1 or two files as candidates. These
//! represent the rlib/dylib file found for a library, and they're returned as
//! being found.
//!
//! ### What about versions?
//!
//! A lot of effort has been put forth to remove versioning from the compiler.
//! There have been forays in the past to have versioning baked in, but it was
//! largely always deemed insufficient to the point that it was recognized that
//! it's probably something the compiler shouldn't do anyway due to its
//! complicated nature and the state of the half-baked solutions.
//!
//! With a departure from versioning, the primary criterion for loading crates
//! is just the name of a crate. If we stopped here, it would imply that you
//! could never link two crates of the same name from different sources
//! together, which is clearly a bad state to be in.
//!
//! To resolve this problem, we come to the next section!
//!
//! # Expert Mode
//!
//! A number of flags have been added to the compiler to solve the "version
//! problem" in the previous section, as well as generally enabling more
//! powerful usage of the crate loading system of the compiler. The goal of
//! these flags and options are to enable third-party tools to drive the
//! compiler with prior knowledge about how the world should look.
//!
//! ## The `--extern` flag
//!
//! The compiler accepts a flag of this form a number of times:
//!
//! ```text
//! --extern crate-name=path/to/the/crate.rlib
//! ```
//!
//! This flag is basically the following letter to the compiler:
//!
//! > Dear rustc,
//! >
//! > When you are attempting to load the immediate dependency `crate-name`, I
//! > would like you to assume that the library is located at
//! > `path/to/the/crate.rlib`, and look nowhere else. Also, please do not
//! > assume that the path I specified has the name `crate-name`.
//!
//! This flag basically overrides most matching logic except for validating that
//! the file is indeed a rust library. The same `crate-name` can be specified
//! twice to specify the rlib/dylib pair.
//!
//! ## Enabling "multiple versions"
//!
//! This basically boils down to the ability to specify arbitrary packages to
//! the compiler. For example, if crate A wanted to use Bv1 and Bv2, then it
//! would look something like:
//!
//! ```compile_fail,E0463
//! extern crate b1;
//! extern crate b2;
//!
//! fn main() {}
//! ```
//!
//! and the compiler would be invoked as:
//!
//! ```text
//! rustc a.rs --extern b1=path/to/libb1.rlib --extern b2=path/to/libb2.rlib
//! ```
//!
//! In this scenario there are two crates named `b` and the compiler must be
//! manually driven to be informed where each crate is.
//!
//! ## Frobbing symbols
//!
//! One of the immediate problems with linking the same library together twice
//! in the same problem is dealing with duplicate symbols. The primary way to
//! deal with this in rustc is to add hashes to the end of each symbol.
//!
//! In order to force hashes to change between versions of a library, if
//! desired, the compiler exposes an option `-C metadata=foo`, which is used to
//! initially seed each symbol hash. The string `foo` is prepended to each
//! string-to-hash to ensure that symbols change over time.
//!
//! ## Loading transitive dependencies
//!
//! Dealing with same-named-but-distinct crates is not just a local problem, but
//! one that also needs to be dealt with for transitive dependencies. Note that
//! in the letter above `--extern` flags only apply to the *local* set of
//! dependencies, not the upstream transitive dependencies. Consider this
//! dependency graph:
//!
//! ```text
//! A.1   A.2
//! |     |
//! |     |
//! B     C
//!  \   /
//!   \ /
//!    D
//! ```
//!
//! In this scenario, when we compile `D`, we need to be able to distinctly
//! resolve `A.1` and `A.2`, but an `--extern` flag cannot apply to these
//! transitive dependencies.
//!
//! Note that the key idea here is that `B` and `C` are both *already compiled*.
//! That is, they have already resolved their dependencies. Due to unrelated
//! technical reasons, when a library is compiled, it is only compatible with
//! the *exact same* version of the upstream libraries it was compiled against.
//! We use the "Strict Version Hash" to identify the exact copy of an upstream
//! library.
//!
//! With this knowledge, we know that `B` and `C` will depend on `A` with
//! different SVH values, so we crawl the normal `-L` paths looking for
//! `liba*.rlib` and filter based on the contained SVH.
//!
//! In the end, this ends up not needing `--extern` to specify upstream
//! transitive dependencies.
//!
//! # Wrapping up
//!
//! That's the general overview of loading crates in the compiler, but it's by
//! no means all of the necessary details. Take a look at the rest of
//! metadata::locator or metadata::creader for all the juicy details!

use crate::creader::Library;
use crate::rmeta::{METADATA_HEADER, rustc_version, MetadataBlob};

use rustc_data_structures::fx::FxHashSet;
use rustc_data_structures::svh::Svh;
use rustc_data_structures::sync::MetadataRef;
use rustc::middle::cstore::{CrateSource, MetadataLoader};
use rustc::session::{config, Session, CrateDisambiguator};
use rustc::session::filesearch::{FileSearch, FileMatches, FileDoesntMatch};
use rustc::session::search_paths::PathKind;
use rustc::util::nodemap::FxHashMap;

use errors::DiagnosticBuilder;
use syntax::{span_err, span_fatal};
use syntax::symbol::{Symbol, sym};
use syntax::struct_span_err;
use syntax_pos::Span;
use rustc_target::spec::{Target, TargetTriple};

use std::cmp;
use std::fmt;
use std::fs;
use std::io::{self, Read};
use std::ops::Deref;
use std::path::{Path, PathBuf};
use std::time::Instant;

use flate2::read::DeflateDecoder;

use rustc_data_structures::owning_ref::OwningRef;

use log::{debug, info, warn};

use rustc_error_codes::*;

#[derive(Clone)]
struct CrateMismatch {
    path: PathBuf,
    got: String,
}

#[derive(Clone)]
crate struct CrateLocator<'a> {
    // Immutable per-session configuration.
    sess: &'a Session,
    metadata_loader: &'a dyn MetadataLoader,

    // Immutable per-search configuration.
    crate_name: Symbol,
    exact_paths: Vec<PathBuf>,
    pub hash: Option<Svh>,
    pub host_hash: Option<Svh>,
    extra_filename: Option<&'a str>,
    pub target: &'a Target,
    pub triple: TargetTriple,
    pub filesearch: FileSearch<'a>,
    span: Span,
    root: Option<&'a CratePaths>,
    pub is_proc_macro: Option<bool>,

    // Mutable in-progress state or output.
    rejected_via_hash: Vec<CrateMismatch>,
    rejected_via_triple: Vec<CrateMismatch>,
    rejected_via_kind: Vec<CrateMismatch>,
    rejected_via_version: Vec<CrateMismatch>,
    rejected_via_filename: Vec<CrateMismatch>,
}

crate struct CratePaths {
    name: Symbol,
    source: CrateSource,
}

impl CratePaths {
    crate fn new(name: Symbol, source: CrateSource) -> CratePaths {
        CratePaths { name, source }
    }
}

#[derive(Copy, Clone, PartialEq)]
enum CrateFlavor {
    Rlib,
    Rmeta,
    Dylib,
}

impl fmt::Display for CrateFlavor {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(match *self {
            CrateFlavor::Rlib => "rlib",
            CrateFlavor::Rmeta => "rmeta",
            CrateFlavor::Dylib => "dylib",
        })
    }
}

impl<'a> CrateLocator<'a> {
    crate fn new(
        sess: &'a Session,
        metadata_loader: &'a dyn MetadataLoader,
        crate_name: Symbol,
        hash: Option<Svh>,
        host_hash: Option<Svh>,
        extra_filename: Option<&'a str>,
        is_host: bool,
        path_kind: PathKind,
        span: Span,
        root: Option<&'a CratePaths>,
        is_proc_macro: Option<bool>,
    ) -> CrateLocator<'a> {
        CrateLocator {
            sess,
            metadata_loader,
            crate_name,
            exact_paths: if hash.is_none() {
                sess.opts.externs.get(&crate_name.as_str()).into_iter()
                    .flat_map(|entry| entry.locations.iter())
                    .filter_map(|location| location.clone().map(PathBuf::from)).collect()
            } else {
                // SVH being specified means this is a transitive dependency,
                // so `--extern` options do not apply.
                Vec::new()
            },
            hash,
            host_hash,
            extra_filename,
            target: if is_host { &sess.host } else { &sess.target.target },
            triple: if is_host {
                TargetTriple::from_triple(config::host_triple())
            } else {
                sess.opts.target_triple.clone()
            },
            filesearch: if is_host {
                sess.host_filesearch(path_kind)
            } else {
                sess.target_filesearch(path_kind)
            },
            span,
            root,
            is_proc_macro,
            rejected_via_hash: Vec::new(),
            rejected_via_triple: Vec::new(),
            rejected_via_kind: Vec::new(),
            rejected_via_version: Vec::new(),
            rejected_via_filename: Vec::new(),
        }
    }

    crate fn reset(&mut self) {
        self.rejected_via_hash.clear();
        self.rejected_via_triple.clear();
        self.rejected_via_kind.clear();
        self.rejected_via_version.clear();
        self.rejected_via_filename.clear();
    }

    crate fn maybe_load_library_crate(&mut self) -> Option<Library> {
        if !self.exact_paths.is_empty() {
            return self.find_commandline_library();
        }
        let mut seen_paths = FxHashSet::default();
        match self.extra_filename {
            Some(s) => self.find_library_crate(s, &mut seen_paths)
                .or_else(|| self.find_library_crate("", &mut seen_paths)),
            None => self.find_library_crate("", &mut seen_paths)
        }
    }

    crate fn report_errs(self) -> ! {
        let add = match self.root {
            None => String::new(),
            Some(r) => format!(" which `{}` depends on", r.name),
        };
        let mut msg = "the following crate versions were found:".to_string();
        let mut err = if !self.rejected_via_hash.is_empty() {
            let mut err = struct_span_err!(self.sess,
                                           self.span,
                                           E0460,
                                           "found possibly newer version of crate `{}`{}",
                                           self.crate_name,
                                           add);
            err.note("perhaps that crate needs to be recompiled?");
            let mismatches = self.rejected_via_hash.iter();
            for &CrateMismatch { ref path, .. } in mismatches {
                msg.push_str(&format!("\ncrate `{}`: {}", self.crate_name, path.display()));
            }
            match self.root {
                None => {}
                Some(r) => {
                    for path in r.source.paths() {
                        msg.push_str(&format!("\ncrate `{}`: {}", r.name, path.display()));
                    }
                }
            }
            err.note(&msg);
            err
        } else if !self.rejected_via_triple.is_empty() {
            let mut err = struct_span_err!(self.sess,
                                           self.span,
                                           E0461,
                                           "couldn't find crate `{}` \
                                            with expected target triple {}{}",
                                           self.crate_name,
                                           self.triple,
                                           add);
            let mismatches = self.rejected_via_triple.iter();
            for &CrateMismatch { ref path, ref got } in mismatches {
                msg.push_str(&format!("\ncrate `{}`, target triple {}: {}",
                                      self.crate_name,
                                      got,
                                      path.display()));
            }
            err.note(&msg);
            err
        } else if !self.rejected_via_kind.is_empty() {
            let mut err = struct_span_err!(self.sess,
                                           self.span,
                                           E0462,
                                           "found staticlib `{}` instead of rlib or dylib{}",
                                           self.crate_name,
                                           add);
            err.help("please recompile that crate using --crate-type lib");
            let mismatches = self.rejected_via_kind.iter();
            for &CrateMismatch { ref path, .. } in mismatches {
                msg.push_str(&format!("\ncrate `{}`: {}", self.crate_name, path.display()));
            }
            err.note(&msg);
            err
        } else if !self.rejected_via_version.is_empty() {
            let mut err = struct_span_err!(self.sess,
                                           self.span,
                                           E0514,
                                           "found crate `{}` compiled by an incompatible version \
                                            of rustc{}",
                                           self.crate_name,
                                           add);
            err.help(&format!("please recompile that crate using this compiler ({})",
                              rustc_version()));
            let mismatches = self.rejected_via_version.iter();
            for &CrateMismatch { ref path, ref got } in mismatches {
                msg.push_str(&format!("\ncrate `{}` compiled by {}: {}",
                                      self.crate_name,
                                      got,
                                      path.display()));
            }
            err.note(&msg);
            err
        } else {
            let mut err = struct_span_err!(self.sess,
                                           self.span,
                                           E0463,
                                           "can't find crate for `{}`{}",
                                           self.crate_name,
                                           add);

            if (self.crate_name == sym::std || self.crate_name == sym::core)
                && self.triple != TargetTriple::from_triple(config::host_triple()) {
                err.note(&format!("the `{}` target may not be installed", self.triple));
            }
            err.span_label(self.span, "can't find crate");
            err
        };

        if !self.rejected_via_filename.is_empty() {
            let dylibname = self.dylibname();
            let mismatches = self.rejected_via_filename.iter();
            for &CrateMismatch { ref path, .. } in mismatches {
                err.note(&format!("extern location for {} is of an unknown type: {}",
                                  self.crate_name,
                                  path.display()))
                   .help(&format!("file name should be lib*.rlib or {}*.{}",
                                  dylibname.0,
                                  dylibname.1));
            }
        }

        err.emit();
        self.sess.abort_if_errors();
        unreachable!();
    }

    fn find_library_crate(&mut self,
                          extra_prefix: &str,
                          seen_paths: &mut FxHashSet<PathBuf>)
                          -> Option<Library> {
        let dypair = self.dylibname();
        let staticpair = self.staticlibname();

        // want: crate_name.dir_part() + prefix + crate_name.file_part + "-"
        let dylib_prefix = format!("{}{}{}", dypair.0, self.crate_name, extra_prefix);
        let rlib_prefix = format!("lib{}{}", self.crate_name, extra_prefix);
        let staticlib_prefix = format!("{}{}{}", staticpair.0, self.crate_name, extra_prefix);

        let mut candidates: FxHashMap<
            _,
            (FxHashMap<_, _>, FxHashMap<_, _>, FxHashMap<_, _>),
        > = Default::default();
        let mut staticlibs = vec![];

        // First, find all possible candidate rlibs and dylibs purely based on
        // the name of the files themselves. We're trying to match against an
        // exact crate name and a possibly an exact hash.
        //
        // During this step, we can filter all found libraries based on the
        // name and id found in the crate id (we ignore the path portion for
        // filename matching), as well as the exact hash (if specified). If we
        // end up having many candidates, we must look at the metadata to
        // perform exact matches against hashes/crate ids. Note that opening up
        // the metadata is where we do an exact match against the full contents
        // of the crate id (path/name/id).
        //
        // The goal of this step is to look at as little metadata as possible.
        self.filesearch.search(|path, kind| {
            let file = match path.file_name().and_then(|s| s.to_str()) {
                None => return FileDoesntMatch,
                Some(file) => file,
            };
            let (hash, found_kind) =
                if file.starts_with(&rlib_prefix) && file.ends_with(".rlib") {
                    (&file[(rlib_prefix.len())..(file.len() - ".rlib".len())], CrateFlavor::Rlib)
                } else if file.starts_with(&rlib_prefix) && file.ends_with(".rmeta") {
                    (&file[(rlib_prefix.len())..(file.len() - ".rmeta".len())], CrateFlavor::Rmeta)
                } else if file.starts_with(&dylib_prefix) &&
                                             file.ends_with(&dypair.1) {
                    (&file[(dylib_prefix.len())..(file.len() - dypair.1.len())], CrateFlavor::Dylib)
                } else {
                    if file.starts_with(&staticlib_prefix) && file.ends_with(&staticpair.1) {
                        staticlibs.push(CrateMismatch {
                            path: path.to_path_buf(),
                            got: "static".to_string(),
                        });
                    }
                    return FileDoesntMatch;
                };

            info!("lib candidate: {}", path.display());

            let hash_str = hash.to_string();
            let slot = candidates.entry(hash_str).or_default();
            let (ref mut rlibs, ref mut rmetas, ref mut dylibs) = *slot;
            fs::canonicalize(path)
                .map(|p| {
                    if seen_paths.contains(&p) {
                        return FileDoesntMatch
                    };
                    seen_paths.insert(p.clone());
                    match found_kind {
                        CrateFlavor::Rlib => { rlibs.insert(p, kind); }
                        CrateFlavor::Rmeta => { rmetas.insert(p, kind); }
                        CrateFlavor::Dylib => { dylibs.insert(p, kind); }
                    }
                    FileMatches
                })
                .unwrap_or(FileDoesntMatch)
        });
        self.rejected_via_kind.extend(staticlibs);

        // We have now collected all known libraries into a set of candidates
        // keyed of the filename hash listed. For each filename, we also have a
        // list of rlibs/dylibs that apply. Here, we map each of these lists
        // (per hash), to a Library candidate for returning.
        //
        // A Library candidate is created if the metadata for the set of
        // libraries corresponds to the crate id and hash criteria that this
        // search is being performed for.
        let mut libraries = FxHashMap::default();
        for (_hash, (rlibs, rmetas, dylibs)) in candidates {
            if let Some((svh, lib)) = self.extract_lib(rlibs, rmetas, dylibs) {
                libraries.insert(svh, lib);
            }
        }

        // Having now translated all relevant found hashes into libraries, see
        // what we've got and figure out if we found multiple candidates for
        // libraries or not.
        match libraries.len() {
            0 => None,
            1 => Some(libraries.into_iter().next().unwrap().1),
            _ => {
                let mut err = struct_span_err!(self.sess,
                                               self.span,
                                               E0464,
                                               "multiple matching crates for `{}`",
                                               self.crate_name);
                let candidates = libraries.iter().filter_map(|(_, lib)| {
                    let crate_name = &lib.metadata.get_root().name().as_str();
                    match &(&lib.source.dylib, &lib.source.rlib) {
                        &(&Some((ref pd, _)), &Some((ref pr, _))) => {
                            Some(format!("\ncrate `{}`: {}\n{:>padding$}",
                                         crate_name,
                                         pd.display(),
                                         pr.display(),
                                         padding=8 + crate_name.len()))
                        }
                        &(&Some((ref p, _)), &None) | &(&None, &Some((ref p, _))) => {
                            Some(format!("\ncrate `{}`: {}", crate_name, p.display()))
                        }
                        &(&None, &None) => None,
                    }
                }).collect::<String>();
                err.note(&format!("candidates:{}", candidates));
                err.emit();
                None
            }
        }
    }

    fn extract_lib(
        &mut self,
        rlibs: FxHashMap<PathBuf, PathKind>,
        rmetas: FxHashMap<PathBuf, PathKind>,
        dylibs: FxHashMap<PathBuf, PathKind>,
    ) -> Option<(Svh, Library)> {
        let mut slot = None;
        let source = CrateSource {
            rlib: self.extract_one(rlibs, CrateFlavor::Rlib, &mut slot),
            rmeta: self.extract_one(rmetas, CrateFlavor::Rmeta, &mut slot),
            dylib: self.extract_one(dylibs, CrateFlavor::Dylib, &mut slot),
        };
        slot.map(|(svh, metadata)| (svh, Library { source, metadata }))
    }

    // Attempts to extract *one* library from the set `m`. If the set has no
    // elements, `None` is returned. If the set has more than one element, then
    // the errors and notes are emitted about the set of libraries.
    //
    // With only one library in the set, this function will extract it, and then
    // read the metadata from it if `*slot` is `None`. If the metadata couldn't
    // be read, it is assumed that the file isn't a valid rust library (no
    // errors are emitted).
    fn extract_one(&mut self,
                   m: FxHashMap<PathBuf, PathKind>,
                   flavor: CrateFlavor,
                   slot: &mut Option<(Svh, MetadataBlob)>)
                   -> Option<(PathBuf, PathKind)> {
        let mut ret: Option<(PathBuf, PathKind)> = None;
        let mut error = 0;

        if slot.is_some() {
            // FIXME(#10786): for an optimization, we only read one of the
            //                libraries' metadata sections. In theory we should
            //                read both, but reading dylib metadata is quite
            //                slow.
            if m.is_empty() {
                return None;
            } else if m.len() == 1 {
                return Some(m.into_iter().next().unwrap());
            }
        }

        let mut err: Option<DiagnosticBuilder<'_>> = None;
        for (lib, kind) in m {
            info!("{} reading metadata from: {}", flavor, lib.display());
            let (hash, metadata) =
                match get_metadata_section(self.target, flavor, &lib, self.metadata_loader) {
                    Ok(blob) => {
                        if let Some(h) = self.crate_matches(&blob, &lib) {
                            (h, blob)
                        } else {
                            info!("metadata mismatch");
                            continue;
                        }
                    }
                    Err(err) => {
                        warn!("no metadata found: {}", err);
                        continue;
                    }
                };
            // If we see multiple hashes, emit an error about duplicate candidates.
            if slot.as_ref().map_or(false, |s| s.0 != hash) {
                let mut e = struct_span_err!(self.sess,
                                             self.span,
                                             E0465,
                                             "multiple {} candidates for `{}` found",
                                             flavor,
                                             self.crate_name);
                e.span_note(self.span,
                            &format!(r"candidate #1: {}",
                                     ret.as_ref()
                                         .unwrap()
                                         .0
                                         .display()));
                if let Some(ref mut e) = err {
                    e.emit();
                }
                err = Some(e);
                error = 1;
                *slot = None;
            }
            if error > 0 {
                error += 1;
                err.as_mut().unwrap().span_note(self.span,
                                                &format!(r"candidate #{}: {}",
                                                         error,
                                                         lib.display()));
                continue;
            }

            // Ok so at this point we've determined that `(lib, kind)` above is
            // a candidate crate to load, and that `slot` is either none (this
            // is the first crate of its kind) or if some the previous path has
            // the exact same hash (e.g., it's the exact same crate).
            //
            // In principle these two candidate crates are exactly the same so
            // we can choose either of them to link. As a stupidly gross hack,
            // however, we favor crate in the sysroot.
            //
            // You can find more info in rust-lang/rust#39518 and various linked
            // issues, but the general gist is that during testing libstd the
            // compilers has two candidates to choose from: one in the sysroot
            // and one in the deps folder. These two crates are the exact same
            // crate but if the compiler chooses the one in the deps folder
            // it'll cause spurious errors on Windows.
            //
            // As a result, we favor the sysroot crate here. Note that the
            // candidates are all canonicalized, so we canonicalize the sysroot
            // as well.
            if let Some((ref prev, _)) = ret {
                let sysroot = &self.sess.sysroot;
                let sysroot = sysroot.canonicalize()
                                     .unwrap_or_else(|_| sysroot.to_path_buf());
                if prev.starts_with(&sysroot) {
                    continue
                }
            }
            *slot = Some((hash, metadata));
            ret = Some((lib, kind));
        }

        if error > 0 {
            err.unwrap().emit();
            None
        } else {
            ret
        }
    }

    fn crate_matches(&mut self, metadata: &MetadataBlob, libpath: &Path) -> Option<Svh> {
        let rustc_version = rustc_version();
        let found_version = metadata.get_rustc_version();
        if found_version != rustc_version {
            info!("Rejecting via version: expected {} got {}",
                  rustc_version,
                  found_version);
            self.rejected_via_version.push(CrateMismatch {
                path: libpath.to_path_buf(),
                got: found_version,
            });
            return None;
        }

        let root = metadata.get_root();
        if let Some(expected_is_proc_macro) = self.is_proc_macro {
            let is_proc_macro = root.is_proc_macro_crate();
            if is_proc_macro != expected_is_proc_macro {
                info!("Rejecting via proc macro: expected {} got {}",
                      expected_is_proc_macro, is_proc_macro);
                return None;
            }
        }

        if self.exact_paths.is_empty() {
            if self.crate_name != root.name() {
                info!("Rejecting via crate name");
                return None;
            }
        }

        if root.triple() != &self.triple {
            info!("Rejecting via crate triple: expected {} got {}",
                  self.triple,
                  root.triple());
            self.rejected_via_triple.push(CrateMismatch {
                path: libpath.to_path_buf(),
                got: root.triple().to_string(),
            });
            return None;
        }

        let hash = root.hash();
        if let Some(expected_hash) = self.hash {
            if hash != expected_hash {
                info!("Rejecting via hash: expected {} got {}", expected_hash, hash);
                self.rejected_via_hash.push(CrateMismatch {
                    path: libpath.to_path_buf(),
                    got: hash.to_string(),
                });
                return None;
            }
        }

        Some(hash)
    }


    // Returns the corresponding (prefix, suffix) that files need to have for
    // dynamic libraries
    fn dylibname(&self) -> (String, String) {
        let t = &self.target;
        (t.options.dll_prefix.clone(), t.options.dll_suffix.clone())
    }

    // Returns the corresponding (prefix, suffix) that files need to have for
    // static libraries
    fn staticlibname(&self) -> (String, String) {
        let t = &self.target;
        (t.options.staticlib_prefix.clone(), t.options.staticlib_suffix.clone())
    }

    fn find_commandline_library(&mut self) -> Option<Library> {
        // First, filter out all libraries that look suspicious. We only accept
        // files which actually exist that have the correct naming scheme for
        // rlibs/dylibs.
        let sess = self.sess;
        let dylibname = self.dylibname();
        let mut rlibs = FxHashMap::default();
        let mut rmetas = FxHashMap::default();
        let mut dylibs = FxHashMap::default();
        {
                let crate_name = self.crate_name;
                let rejected_via_filename = &mut self.rejected_via_filename;
                let locs = self.exact_paths.iter().filter(|loc| {
                if !loc.exists() {
                    sess.err(&format!("extern location for {} does not exist: {}",
                                      crate_name,
                                      loc.display()));
                    return false;
                }
                let file = match loc.file_name().and_then(|s| s.to_str()) {
                    Some(file) => file,
                    None => {
                        sess.err(&format!("extern location for {} is not a file: {}",
                                          crate_name,
                                          loc.display()));
                        return false;
                    }
                };
                if file.starts_with("lib") &&
                   (file.ends_with(".rlib") || file.ends_with(".rmeta")) {
                    return true;
                } else {
                    let (ref prefix, ref suffix) = dylibname;
                    if file.starts_with(&prefix[..]) && file.ends_with(&suffix[..]) {
                        return true;
                    }
                }

                rejected_via_filename.push(CrateMismatch {
                    path: (*loc).clone(),
                    got: String::new(),
                });

                false
            });

            // Now that we have an iterator of good candidates, make sure
            // there's at most one rlib and at most one dylib.
            for loc in locs {
                if loc.file_name().unwrap().to_str().unwrap().ends_with(".rlib") {
                    rlibs.insert(fs::canonicalize(&loc).unwrap(), PathKind::ExternFlag);
                } else if loc.file_name().unwrap().to_str().unwrap().ends_with(".rmeta") {
                    rmetas.insert(fs::canonicalize(&loc).unwrap(), PathKind::ExternFlag);
                } else {
                    dylibs.insert(fs::canonicalize(&loc).unwrap(), PathKind::ExternFlag);
                }
            }
        };

        // Extract the dylib/rlib/rmeta triple.
        self.extract_lib(rlibs, rmetas, dylibs).map(|(_, lib)| lib)
    }
}

// Just a small wrapper to time how long reading metadata takes.
fn get_metadata_section(target: &Target,
                        flavor: CrateFlavor,
                        filename: &Path,
                        loader: &dyn MetadataLoader)
                        -> Result<MetadataBlob, String> {
    let start = Instant::now();
    let ret = get_metadata_section_imp(target, flavor, filename, loader);
    info!("reading {:?} => {:?}",
          filename.file_name().unwrap(),
          start.elapsed());
    return ret;
}

/// A trivial wrapper for `Mmap` that implements `StableDeref`.
struct StableDerefMmap(memmap::Mmap);

impl Deref for StableDerefMmap {
    type Target = [u8];

    fn deref(&self) -> &[u8] {
        self.0.deref()
    }
}

unsafe impl stable_deref_trait::StableDeref for StableDerefMmap {}

fn get_metadata_section_imp(target: &Target,
                            flavor: CrateFlavor,
                            filename: &Path,
                            loader: &dyn MetadataLoader)
                            -> Result<MetadataBlob, String> {
    if !filename.exists() {
        return Err(format!("no such file: '{}'", filename.display()));
    }
    let raw_bytes: MetadataRef = match flavor {
        CrateFlavor::Rlib => loader.get_rlib_metadata(target, filename)?,
        CrateFlavor::Dylib => {
            let buf = loader.get_dylib_metadata(target, filename)?;
            // The header is uncompressed
            let header_len = METADATA_HEADER.len();
            debug!("checking {} bytes of metadata-version stamp", header_len);
            let header = &buf[..cmp::min(header_len, buf.len())];
            if header != METADATA_HEADER {
                return Err(format!("incompatible metadata version found: '{}'",
                                   filename.display()));
            }

            // Header is okay -> inflate the actual metadata
            let compressed_bytes = &buf[header_len..];
            debug!("inflating {} bytes of compressed metadata", compressed_bytes.len());
            let mut inflated = Vec::new();
            match DeflateDecoder::new(compressed_bytes).read_to_end(&mut inflated) {
                Ok(_) => {
                    rustc_erase_owner!(OwningRef::new(inflated).map_owner_box())
                }
                Err(_) => {
                    return Err(format!("failed to decompress metadata: {}", filename.display()));
                }
            }
        }
        CrateFlavor::Rmeta => {
            // mmap the file, because only a small fraction of it is read.
            let file = std::fs::File::open(filename).map_err(|_|
                format!("failed to open rmeta metadata: '{}'", filename.display()))?;
            let mmap = unsafe { memmap::Mmap::map(&file) };
            let mmap = mmap.map_err(|_|
                format!("failed to mmap rmeta metadata: '{}'", filename.display()))?;

            rustc_erase_owner!(OwningRef::new(StableDerefMmap(mmap)).map_owner_box())
        }
    };
    let blob = MetadataBlob::new(raw_bytes);
    if blob.is_compatible() {
        Ok(blob)
    } else {
        Err(format!("incompatible metadata version found: '{}'", filename.display()))
    }
}

/// Look for a plugin registrar. Returns its library path and crate disambiguator.
pub fn find_plugin_registrar(
    sess: &Session,
    metadata_loader: &dyn MetadataLoader,
    span: Span,
    name: Symbol,
) -> Option<(PathBuf, CrateDisambiguator)> {
    info!("find plugin registrar `{}`", name);
    let target_triple = sess.opts.target_triple.clone();
    let host_triple = TargetTriple::from_triple(config::host_triple());
    let is_cross = target_triple != host_triple;
    let mut target_only = false;
    let mut locator = CrateLocator::new(
        sess,
        metadata_loader,
        name,
        None, // hash
        None, // host_hash
        None, // extra_filename
        true, // is_host
        PathKind::Crate,
        span,
        None, // root
        None, // is_proc_macro
    );

    let library = locator.maybe_load_library_crate().or_else(|| {
        if !is_cross {
            return None
        }
        // Try loading from target crates. This will abort later if we
        // try to load a plugin registrar function,
        target_only = true;

        locator.target = &sess.target.target;
        locator.triple = target_triple;
        locator.filesearch = sess.target_filesearch(PathKind::Crate);

        locator.maybe_load_library_crate()
    });
    let library = match library {
        Some(l) => l,
        None => locator.report_errs(),
    };

    if target_only {
        // Need to abort before syntax expansion.
        let message = format!("plugin `{}` is not available for triple `{}` \
                                (only found {})",
                                name,
                                config::host_triple(),
                                sess.opts.target_triple);
        span_fatal!(sess, span, E0456, "{}", &message);
    }

    match library.source.dylib {
        Some(dylib) => {
            Some((dylib.0, library.metadata.get_root().disambiguator()))
        }
        None => {
            span_err!(sess, span, E0457,
                        "plugin `{}` only found in rlib format, but must be available \
                        in dylib format",
                        name);
            // No need to abort because the loading code will just ignore this
            // empty dylib.
            None
        }
    }
}

/// A diagnostic function for dumping crate metadata to an output stream.
pub fn list_file_metadata(target: &Target,
                          path: &Path,
                          metadata_loader: &dyn MetadataLoader,
                          out: &mut dyn io::Write)
                          -> io::Result<()> {
    let filename = path.file_name().unwrap().to_str().unwrap();
    let flavor = if filename.ends_with(".rlib") {
        CrateFlavor::Rlib
    } else if filename.ends_with(".rmeta") {
        CrateFlavor::Rmeta
    } else {
        CrateFlavor::Dylib
    };
    match get_metadata_section(target, flavor, path, metadata_loader) {
        Ok(metadata) => metadata.list_crate_metadata(out),
        Err(msg) => write!(out, "{}\n", msg),
    }
}