rucc_driver/

link.rs

//! Finding a linker and telling it what to link.
//!
//! Design: `spec/04-driver-and-cli.md` section 4.9. There is no linker of our own before 1.0, so
//! this finds one on the machine and builds the command line it wants.
//!
//! The linker is invoked directly rather than through the system compiler driver. Going through
//! `cc` would be shorter to write and would borrow that compiler's idea of where everything is,
//! and it would also mean this compiler cannot link on a machine that has no other compiler on
//! it, which is most of the machines a compiler ends up on. It would also make `-###` output a
//! line that does not say what happens, since the interesting half would be inside the program
//! being spawned.
//!
//! # What is not decided here
//!
//! The startup files and the library directories are looked for rather than configured, for the
//! same reason `library` looks for the headers: gcc settles this when it is built because a gcc
//! is built for the machine it will run on, and this is one binary that runs wherever it is
//! copied. So the shape of the answer is a list of candidates per platform of which the ones
//! that exist are taken, and a cross build says where the rest is with `--sysroot`.
//!
//! # What is not here yet
//!
//! `crtbegin` and `crtend`, and `-lgcc`. Those are a compiler's own runtime rather than the
//! library's, and this compiler's is `rucc-builtins`, which is not written. A program that needs
//! neither links and runs without them, which is every program that does not divide a 128-bit
//! integer or unwind through a frame, and a program that needs one gets an undefined symbol from
//! the linker naming exactly what is missing rather than a wrong answer at run time.
//!
//! Darwin and Windows. `ld64` wants a different line, a platform version load command and a
//! different set of default libraries, and `link.exe` wants another one again. Each arrives with
//! the target that needs it.

use std::ffi::OsString;
use std::path::{Path, PathBuf};
use std::process::Command;

use rucc_target::{Arch, Env, Os, Triple};

/// What the command line said about linking.
///
/// Kept apart from `Options` because none of it reaches the compilation. A flag here changes what
/// the linker is told and changes nothing about the object files handed to it, which is why `-lm`
/// on a `-c` line is a note rather than an error.
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub struct LinkOptions {
    /// `-fuse-ld=<name>`, which names a linker rather than a path to one.
    pub use_ld: Option<String>,
    /// `-L<dir>`, in order, because the linker takes the first library it finds.
    pub search: Vec<PathBuf>,
    /// `-Wl,<arg>` and `-Xlinker <arg>`, in order, passed through untouched.
    pub passthrough: Vec<String>,
    /// `-B<prefix>`, which is where to look for the linker before looking on the path.
    pub prefixes: Vec<PathBuf>,
    /// `--sysroot=<dir>`, which prefixes the directories this looks in.
    pub sysroot: Option<PathBuf>,
    /// `-static`.
    pub is_static: bool,
    /// `-shared`.
    pub shared: bool,
    /// `-pie` or `-no-pie`, and the platform's default when neither was written.
    pub pie: Option<bool>,
    /// `-nostdlib`, which is `-nostartfiles` and `-nodefaultlibs` together.
    pub no_stdlib: bool,
    /// `-nostartfiles`.
    pub no_startfiles: bool,
    /// `-nodefaultlibs`.
    pub no_defaultlibs: bool,
    /// `-rdynamic`, which puts every symbol in the dynamic table so a program can look itself up.
    pub export_dynamic: bool,
    /// `-s`, which drops the symbol table.
    pub strip: bool,
}

impl LinkOptions {
    /// Whether the startup files go on the line.
    fn wants_startfiles(&self) -> bool {
        !self.no_stdlib && !self.no_startfiles
    }

    /// Whether the library the program was written against goes on the line.
    fn wants_defaultlibs(&self) -> bool {
        !self.no_stdlib && !self.no_defaultlibs
    }
}

/// One item on the link line, in the order it was written, because link order is semantic.
///
/// A library named before the object that needs it is not found on a static link, which is the
/// oldest surprise in the toolchain and the reason this is one ordered list rather than a list of
/// files and a list of libraries.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Item {
    /// A file: an object this compilation produced, or one named on the command line.
    File(String),
    /// `-l<name>`, which the linker resolves against its search path.
    Library(String),
}

impl std::fmt::Display for Item {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Item::File(path) => f.write_str(path),
            Item::Library(name) => write!(f, "-l{name}"),
        }
    }
}

/// Why a link could not be run.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Error {
    /// No linker was found, after looking everywhere there was to look.
    NoLinker {
        /// The names that were tried, in the order they were tried.
        tried: Vec<String>,
    },
    /// `-fuse-ld=` named one that is not on this machine.
    Named {
        /// What it named.
        name: String,
    },
    /// A target this does not know how to build a link line for.
    Target {
        /// The triple that was asked for.
        triple: String,
    },
    /// The linker was found and could not be started.
    Spawn {
        /// Where it was.
        path: String,
        /// What the operating system said.
        why: String,
    },
    /// The linker ran and said no.
    Refused {
        /// What it exited with, or a description when it was killed instead.
        status: String,
    },
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Error::NoLinker { tried } => {
                write!(f, "no linker was found; tried {}", tried.join(", "))
            }
            Error::Named { name } => {
                write!(f, "-fuse-ld={name} asks for a linker that is not on this machine")
            }
            Error::Target { triple } => {
                write!(f, "there is no link line for {triple} in this compiler yet")
            }
            Error::Spawn { path, why } => write!(f, "could not run the linker at {path}: {why}"),
            Error::Refused { status } => write!(f, "the linker {status}"),
        }
    }
}

impl std::error::Error for Error {}

/// A linker, found.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Linker {
    /// The name it is known by, which is what `--print-config` reports.
    pub name: String,
    /// Where it is, which is what gets spawned.
    pub path: PathBuf,
}

/// The names to look for, in the order section 4.9 gives.
///
/// `mold` first because it is dramatically faster, and a compiler that is twice the speed of
/// another one while the link takes twelve seconds has not helped anybody. Then `lld`, then the
/// platform's own. Each is looked for under both the bare name and the `ld.` prefix, because a
/// distribution installs `mold` under its own name and `ld.mold` for exactly this lookup.
#[must_use]
pub fn order(target: Triple, opts: &LinkOptions) -> Vec<String> {
    if let Some(named) = &opts.use_ld {
        // A name rather than a path, so `-fuse-ld=mold` finds a `mold` that is not `ld.mold`.
        return vec![format!("ld.{named}"), named.clone()];
    }
    match target.os {
        Os::Windows => vec!["lld-link".to_owned(), "link.exe".to_owned()],
        _ => vec![
            "ld.mold".to_owned(),
            "mold".to_owned(),
            "ld.lld".to_owned(),
            "lld".to_owned(),
            "ld".to_owned(),
        ],
    }
}

/// The linker to use, looked for where a linker is.
///
/// `-B` prefixes first, since the point of one is to put a toolchain in front of the machine's,
/// then the path. A name that contains a separator is a path and is taken as one, which is what
/// gcc does with `-fuse-ld=/usr/bin/ld.gold` and what a build system relying on that expects.
///
/// # Errors
///
/// [`Error::Named`] when `-fuse-ld=` asked for one that is not here, and [`Error::NoLinker`] when
/// nothing was, which name the candidates so that the message says what was looked for.
pub fn find(target: Triple, opts: &LinkOptions) -> Result<Linker, Error> {
    let tried = order(target, opts);
    for name in &tried {
        if name.contains(std::path::MAIN_SEPARATOR) || name.contains('/') {
            let path = PathBuf::from(name);
            if path.is_file() {
                return Ok(Linker { name: name.clone(), path });
            }
            continue;
        }
        for dir in &opts.prefixes {
            let path = dir.join(name);
            if path.is_file() {
                return Ok(Linker { name: name.clone(), path });
            }
        }
        if let Some(path) = on_path(name) {
            return Ok(Linker { name: name.clone(), path });
        }
    }
    match &opts.use_ld {
        Some(name) => Err(Error::Named { name: name.clone() }),
        None => Err(Error::NoLinker { tried }),
    }
}

/// The first executable of that name on `PATH`.
///
/// Executability is checked rather than assumed, because a directory of that name on `PATH` is
/// not a thing to try to run and neither is a file nobody may execute.
fn on_path(name: &str) -> Option<PathBuf> {
    let path = std::env::var_os("PATH")?;
    std::env::split_paths(&path).map(|dir| dir.join(name)).find(|p| executable(p))
}

/// Whether a path is a file this process could run.
#[cfg(unix)]
fn executable(path: &Path) -> bool {
    use std::os::unix::fs::PermissionsExt as _;
    path.metadata().is_ok_and(|m| m.is_file() && m.permissions().mode() & 0o111 != 0)
}

/// Whether a path is a file this process could run.
///
/// Windows has no executable bit and decides by extension, and the names looked for above carry
/// theirs, so being a file is the whole of the question here.
#[cfg(not(unix))]
fn executable(path: &Path) -> bool {
    path.is_file()
}

/// What the linker is told, in order, not counting the linker itself.
///
/// # Errors
///
/// [`Error::Target`] for a platform there is no line for yet, which is every one but Linux.
pub fn line(
    target: Triple,
    opts: &LinkOptions,
    items: &[Item],
    output: &str,
) -> Result<Vec<String>, Error> {
    if target.os != Os::Linux {
        return Err(Error::Target { triple: target.to_string() });
    }
    let machine = emulation(target);
    let root = opts.sysroot.as_deref();
    let dirs = library_dirs(target, root);
    let mut args = vec![
        "-o".to_owned(),
        output.to_owned(),
        // Which of the several formats one `ld` can write is meant. A linker built for more than
        // one machine guesses from its first input otherwise, and a link of no objects at all has
        // nothing to guess from.
        "-m".to_owned(),
        machine.to_owned(),
        // The table a program unwinds through, which a C program with no exceptions in it still
        // needs because `backtrace` and every crash handler read it.
        "--eh-frame-hdr".to_owned(),
        // The symbol hash a dynamic loader from this century reads. The old one is still written
        // alongside by default on some distributions, and asking for this one is what stops a link
        // from carrying a table nothing has needed since 2006.
        "--hash-style=gnu".to_owned(),
    ];

    let pie = opts.pie.unwrap_or(!opts.is_static && !opts.shared);
    if opts.shared {
        args.push("-shared".to_owned());
    } else if opts.is_static {
        args.push("-static".to_owned());
    } else if pie {
        args.push("-pie".to_owned());
    } else {
        args.push("-no-pie".to_owned());
    }
    if !opts.is_static && !opts.shared {
        args.push("-dynamic-linker".to_owned());
        args.push(target_path(root, loader(target)));
    }
    if opts.export_dynamic {
        args.push("--export-dynamic".to_owned());
    }
    if opts.strip {
        args.push("-s".to_owned());
    }

    // The startup file the C library brings, which is what calls `main` and what passes it the
    // arguments. `Scrt1.o` rather than `crt1.o` when the result moves, because the two differ in
    // whether the reference to `main` in them is one a loader may relocate.
    if opts.wants_startfiles() {
        let first = if opts.shared {
            None
        } else if pie {
            Some("Scrt1.o")
        } else {
            Some("crt1.o")
        };
        for name in first.into_iter().chain(["crti.o"]) {
            if let Some(path) = find_file(&dirs, name) {
                args.push(path.display().to_string());
            }
        }
    }

    for dir in &opts.search {
        args.push(format!("-L{}", dir.display()));
    }
    for dir in &dirs {
        args.push(format!("-L{}", dir.display()));
    }

    for item in items {
        match item {
            Item::File(path) => args.push(path.clone()),
            Item::Library(name) => args.push(format!("-l{name}")),
        }
    }
    // After the objects, because a static archive is searched for what is undefined at the point
    // it is reached and a library named before the object that needs it contributes nothing.
    if opts.wants_defaultlibs() {
        args.push("-lc".to_owned());
    }
    if opts.wants_startfiles() {
        if let Some(path) = find_file(&dirs, "crtn.o") {
            args.push(path.display().to_string());
        }
    }

    // Last, so that anything the user said wins over anything decided above, which is what
    // `-Wl,` is for.
    args.extend(opts.passthrough.iter().cloned());
    Ok(args)
}

/// Which output format this `ld` should write, in the name `ld` knows it by.
fn emulation(target: Triple) -> &'static str {
    match target.arch {
        Arch::X86_64 => "elf_x86_64",
        Arch::Aarch64 => "aarch64linux",
        Arch::Riscv64 => "elf64lriscv",
    }
}

/// The program that starts a dynamically linked program, whose path is part of the file.
///
/// It is a per-target constant rather than something to look for, because the name is fixed by
/// the platform's ABI and a program naming a different one does not start.
fn loader(target: Triple) -> &'static str {
    match (target.arch, target.env) {
        (Arch::X86_64, Env::Musl) => "/lib/ld-musl-x86_64.so.1",
        (Arch::X86_64, _) => "/lib64/ld-linux-x86-64.so.2",
        (Arch::Aarch64, Env::Musl) => "/lib/ld-musl-aarch64.so.1",
        (Arch::Aarch64, _) => "/lib/ld-linux-aarch64.so.1",
        (Arch::Riscv64, Env::Musl) => "/lib/ld-musl-riscv64.so.1",
        (Arch::Riscv64, _) => "/lib/ld-linux-riscv64-lp64d.so.1",
    }
}

/// Where the library's own files might be, in search order.
///
/// The multiarch directory first for the reason it comes first in the header search: it is where
/// a distribution that can hold two architectures at once puts the one being asked for, and a
/// distribution that cannot simply does not have it. `lib64` after it, which is what the
/// distributions that split by word size use instead, and `lib` last, which is every other one.
#[must_use]
pub fn candidates(target: Triple, sysroot: Option<&Path>) -> Vec<PathBuf> {
    let libc = match target.env {
        Env::Musl => "musl",
        Env::None | Env::Gnu | Env::Msvc => "gnu",
    };
    let multiarch = format!("{}-linux-{libc}", target.arch.as_str());
    [
        format!("/usr/lib/{multiarch}"),
        format!("/lib/{multiarch}"),
        "/usr/lib64".to_owned(),
        "/lib64".to_owned(),
        "/usr/lib".to_owned(),
        "/lib".to_owned(),
    ]
    .into_iter()
    .map(|dir| under(sysroot, &dir))
    .collect()
}

/// The candidates that are there.
fn library_dirs(target: Triple, sysroot: Option<&Path>) -> Vec<PathBuf> {
    candidates(target, sysroot).into_iter().filter(|dir| dir.is_dir()).collect()
}

/// The first of those directories holding a file of that name.
fn find_file(dirs: &[PathBuf], name: &str) -> Option<PathBuf> {
    dirs.iter().map(|dir| dir.join(name)).find(|path| path.is_file())
}

/// A path under the sysroot, when there is one.
fn under(sysroot: Option<&Path>, path: &str) -> PathBuf {
    match sysroot {
        // `strip_prefix` because joining an absolute path replaces the root rather than extending
        // it, which would make every entry the unprefixed one.
        Some(root) => root.join(path.strip_prefix('/').unwrap_or(path)),
        None => PathBuf::from(path),
    }
}

/// A path on the machine that will run the program, rather than on the one compiling it.
///
/// Written with the separator of the target and not of the host, which matters for the one path
/// that is not looked at here but stored in the file and read by something else later: the loader
/// a dynamic program names. A Windows host joining it would put a backslash in the middle of a
/// name that a Linux loader has to find, and the program would not start.
fn target_path(sysroot: Option<&Path>, path: &str) -> String {
    match sysroot {
        Some(root) => {
            let root = root.display().to_string();
            format!("{}/{}", root.trim_end_matches(['/', '\\']), path.trim_start_matches('/'))
        }
        None => path.to_owned(),
    }
}

/// The whole invocation as one line, quoted the way `-###` prints it.
#[must_use]
pub fn render(linker: &Linker, args: &[String]) -> String {
    let mut out = linker.path.display().to_string();
    for arg in args {
        out.push(' ');
        if arg.is_empty() || arg.contains(char::is_whitespace) {
            out.push('"');
            out.push_str(arg);
            out.push('"');
        } else {
            out.push_str(arg);
        }
    }
    out
}

/// Runs the linker and waits for it.
///
/// # Errors
///
/// [`Error::Spawn`] when it could not be started, which is a machine problem, and
/// [`Error::Refused`] when it ran and said no, which is a program problem and one the linker has
/// already explained on its own error output.
pub fn run(linker: &Linker, args: &[String]) -> Result<(), Error> {
    let args: Vec<OsString> = args.iter().map(OsString::from).collect();
    let status = Command::new(&linker.path).args(&args).status().map_err(|why| Error::Spawn {
        path: linker.path.display().to_string(),
        why: why.to_string(),
    })?;
    if status.success() {
        return Ok(());
    }
    // Nothing is added to what the linker printed. It has already named the symbol or the file,
    // and a second message from here saying that linking failed would only push the first one
    // further up the screen.
    Err(Error::Refused {
        status: match status.code() {
            Some(code) => format!("exited with status {code}"),
            None => "was killed before it finished".to_owned(),
        },
    })
}

#[cfg(test)]
mod tests {
    use super::*;

    fn linux() -> Triple {
        Triple::new(Arch::X86_64, Os::Linux, Env::Gnu)
    }

    fn one(name: &str) -> Vec<Item> {
        vec![Item::File(name.to_owned())]
    }

    #[test]
    fn the_fast_one_is_looked_for_first_and_the_platforms_own_last() {
        let names = order(linux(), &LinkOptions::default());
        assert_eq!(names.first().map(String::as_str), Some("ld.mold"));
        assert_eq!(names.last().map(String::as_str), Some("ld"));
    }

    #[test]
    fn naming_one_is_the_whole_of_the_order() {
        let opts = LinkOptions { use_ld: Some("gold".to_owned()), ..LinkOptions::default() };
        assert_eq!(order(linux(), &opts), ["ld.gold", "gold"]);
    }

    #[test]
    fn a_dynamic_program_names_the_loader_that_will_start_it() {
        let args = line(linux(), &LinkOptions::default(), &one("a.o"), "a.out").expect("a line");
        let at = args.iter().position(|a| a == "-dynamic-linker").expect("the flag");
        assert!(args[at + 1].ends_with("/lib64/ld-linux-x86-64.so.2"), "{args:?}");
    }

    #[test]
    fn a_static_program_names_no_loader_because_nothing_will_start_it() {
        let opts = LinkOptions { is_static: true, ..LinkOptions::default() };
        let args = line(linux(), &opts, &one("a.o"), "a.out").expect("a line");
        assert!(args.contains(&"-static".to_owned()), "{args:?}");
        assert!(!args.contains(&"-dynamic-linker".to_owned()), "{args:?}");
    }

    #[test]
    fn the_startup_file_of_a_program_that_moves_is_not_the_one_of_a_program_that_does_not() {
        let moving = LinkOptions { pie: Some(true), ..LinkOptions::default() };
        let fixed = LinkOptions { pie: Some(false), ..LinkOptions::default() };
        let named = |opts: &LinkOptions| {
            line(linux(), opts, &one("a.o"), "a.out")
                .expect("a line")
                .iter()
                .filter_map(|a| Path::new(a).file_name().map(|n| n.to_string_lossy().into_owned()))
                .find(|n| n.ends_with("crt1.o"))
        };
        // Only when the machine running this has them, which is what makes this two assertions
        // rather than one: a machine with no glibc development files has neither to find.
        if let Some(name) = named(&moving) {
            assert_eq!(name, "Scrt1.o");
            assert_eq!(named(&fixed).as_deref(), Some("crt1.o"));
        }
    }

    #[test]
    fn asking_for_no_startup_files_leaves_out_both_ends_of_them() {
        let opts = LinkOptions { no_startfiles: true, ..LinkOptions::default() };
        let args = line(linux(), &opts, &one("a.o"), "a.out").expect("a line");
        assert!(!args.iter().any(|a| a.ends_with("crt1.o")), "{args:?}");
        assert!(!args.iter().any(|a| a.ends_with("crtn.o")), "{args:?}");
        // And still links against the library, because that is the other flag.
        assert!(args.contains(&"-lc".to_owned()), "{args:?}");
    }

    #[test]
    fn asking_for_no_library_at_all_leaves_out_the_startup_files_too() {
        let opts = LinkOptions { no_stdlib: true, ..LinkOptions::default() };
        let args = line(linux(), &opts, &one("a.o"), "a.out").expect("a line");
        assert!(!args.contains(&"-lc".to_owned()), "{args:?}");
        assert!(!args.iter().any(|a| a.ends_with("crt1.o")), "{args:?}");
    }

    #[test]
    fn the_library_comes_after_the_objects_that_need_it() {
        let items = vec![Item::File("a.o".to_owned()), Item::Library("m".to_owned())];
        let args = line(linux(), &LinkOptions::default(), &items, "a.out").expect("a line");
        let obj = args.iter().position(|a| a == "a.o").expect("the object");
        let m = args.iter().position(|a| a == "-lm").expect("the library");
        let c = args.iter().position(|a| a == "-lc").expect("the library");
        assert!(obj < m && m < c, "{args:?}");
    }

    #[test]
    fn what_the_user_told_the_linker_comes_after_what_this_told_it() {
        let opts = LinkOptions {
            passthrough: vec!["--no-eh-frame-hdr".to_owned()],
            ..LinkOptions::default()
        };
        let args = line(linux(), &opts, &one("a.o"), "a.out").expect("a line");
        assert_eq!(args.last().map(String::as_str), Some("--no-eh-frame-hdr"));
    }

    #[test]
    fn a_sysroot_moves_every_path_this_decided_and_none_the_user_wrote() {
        let opts = LinkOptions {
            sysroot: Some(PathBuf::from("/nowhere-at-all")),
            search: vec![PathBuf::from("/opt/mine")],
            ..LinkOptions::default()
        };
        let args = line(linux(), &opts, &one("a.o"), "a.out").expect("a line");
        let at = args.iter().position(|a| a == "-dynamic-linker").expect("the flag");
        assert_eq!(args[at + 1], "/nowhere-at-all/lib64/ld-linux-x86-64.so.2");
        assert!(args.contains(&"-L/opt/mine".to_owned()), "{args:?}");
    }

    #[test]
    fn a_platform_with_no_link_line_is_said_so_rather_than_linked_wrongly() {
        for triple in [
            Triple::new(Arch::X86_64, Os::Darwin, Env::Gnu),
            Triple::new(Arch::X86_64, Os::Windows, Env::Msvc),
        ] {
            let error = line(triple, &LinkOptions::default(), &one("a.o"), "a.out")
                .expect_err("no line for it");
            assert!(matches!(error, Error::Target { .. }), "{error:?}");
        }
    }

    #[test]
    fn the_line_is_printed_the_way_it_would_be_typed() {
        let linker = Linker { name: "ld".to_owned(), path: PathBuf::from("/usr/bin/ld") };
        let args = ["-o".to_owned(), "a b".to_owned()];
        assert_eq!(render(&linker, &args), "/usr/bin/ld -o \"a b\"");
    }

    #[test]
    fn a_linker_that_is_not_there_is_said_by_name() {
        let opts = LinkOptions {
            use_ld: Some("a-linker-nobody-has".to_owned()),
            ..LinkOptions::default()
        };
        let error = find(linux(), &opts).expect_err("not on this machine");
        assert_eq!(error, Error::Named { name: "a-linker-nobody-has".to_owned() });
    }
}