retex-kpath 1.3.0-alpha.2

//! A native implementation of the parts of kpathsea that TeX engines use.
//!
//! kpathsea finds files in a TeX installation from search paths defined in
//! `texmf.cnf`. It speeds lookups up with `ls-R` databases. This crate
//! reproduces its semantics so that retex finds exactly the same files as
//! `luatex`:
//!
//! * `texmf.cnf` files are found through `TEXMFCNF`. Definitions in earlier
//!   files win. `VAR.progname` takes precedence over `VAR`, and environment
//!   variables take precedence over both.
//! * Values are expanded: `$VAR`/`${VAR}`, then braces `{a,b}`, then `~`.
//! * In a path element, a leading `!!` means "look only in the `ls-R`
//!   database" and a trailing or inner `//` means "any subdirectory".
//! * A lookup of a name with no standard suffix first tries the name with each
//!   suffix of the file format, then the name as given.

#![forbid(unsafe_code)]

mod casefold;
mod cnf;
mod db;
mod expand;
mod format;
mod safe;

use std::collections::HashMap;
use std::path::{Path, PathBuf};

pub use format::FileFormat;
pub use safe::{Access, Refusal};

/// A kpathsea instance shared by several users (engine, font loader).
pub type Shared = std::rc::Rc<std::cell::RefCell<Kpathsea>>;

/// Wraps a [`Kpathsea`] for sharing.
pub fn shared(k: Kpathsea) -> Shared {
    std::rc::Rc::new(std::cell::RefCell::new(k))
}

use cnf::Cnf;
use db::{DirCache, LsR};

/// Errors raised while setting up the search machinery.
#[derive(Debug, thiserror::Error)]
pub enum Error {
    /// No `texmf.cnf` could be found.
    #[error("no texmf.cnf found (searched: {0})")]
    NoConfig(String),
    /// An I/O error while reading configuration or databases.
    #[error("reading {path}: {source}")]
    Io {
        /// The file being read.
        path: PathBuf,
        /// The underlying error.
        source: std::io::Error,
    },
}

/// The separator of path elements: `:` on Unix (where `;` is taken as
/// `:` too), `;` on Windows (where `:` follows drive letters).
pub const SEP: char = if cfg!(windows) { ';' } else { ':' };

/// The default `TEXMFCNF` search path, used when the environment does not
/// set one: the directories relative to the installed `kpsewhich` (the
/// `$SELFAUTO…` variables), when one is found, then on Unix the usual
/// locations of TeX Live and the Debian packages.
fn default_texmfcnf() -> String {
    if cfg!(windows) {
        SELFAUTO_TEXMFCNF.to_owned()
    } else {
        format!(
            "{SELFAUTO_TEXMFCNF}:/etc/texmf/web2c:/usr/local/share/texmf/web2c:\
             /usr/share/texlive/texmf-dist/web2c"
        )
    }
}

/// The part of [`default_texmfcnf`] relative to `kpsewhich`.
const SELFAUTO_TEXMFCNF: &str = "{$SELFAUTOLOC,$SELFAUTOLOC/share/texmf-local/web2c,\
$SELFAUTOLOC/share/texmf-dist/web2c,$SELFAUTOLOC/share/texmf/web2c,\
$SELFAUTOLOC/texmf-local/web2c,$SELFAUTOLOC/texmf-dist/web2c,$SELFAUTOLOC/texmf/web2c,\
$SELFAUTODIR,$SELFAUTODIR/share/texmf-local/web2c,$SELFAUTODIR/share/texmf-dist/web2c,\
$SELFAUTODIR/share/texmf/web2c,$SELFAUTODIR/texmf-local/web2c,$SELFAUTODIR/texmf-dist/web2c,\
$SELFAUTODIR/texmf/web2c,$SELFAUTOGRANDPARENT/texmf-local/web2c,$SELFAUTOPARENT,\
$SELFAUTOPARENT/share/texmf-local/web2c,$SELFAUTOPARENT/share/texmf-dist/web2c,\
$SELFAUTOPARENT/share/texmf/web2c,$SELFAUTOPARENT/texmf-local/web2c,\
$SELFAUTOPARENT/texmf-dist/web2c,$SELFAUTOPARENT/texmf/web2c}";

/// Source of environment variables, injectable for tests.
pub trait Env {
    /// Returns the value of the environment variable `name`, if set.
    fn var(&self, name: &str) -> Option<String>;
}

/// The process environment.
#[derive(Debug, Default, Clone, Copy)]
pub struct ProcessEnv;

impl Env for ProcessEnv {
    fn var(&self, name: &str) -> Option<String> {
        std::env::var(name).ok()
    }
}

/// Configuration for constructing a [`Kpathsea`] instance.
#[derive(Debug, Clone)]
pub struct Options {
    /// The program name (`$progname`), e.g. `lualatex`.
    pub progname: String,
    /// The engine name (`$engine`), e.g. `luahbtex`.
    pub engine: String,
    /// The directory standing in for `$SELFAUTOLOC` (the directory containing
    /// the TeX binaries). `None` locates `kpsewhich` on `PATH`.
    pub selfautoloc: Option<PathBuf>,
    /// A directory where parsed `ls-R` databases are cached between runs.
    pub cache_dir: Option<PathBuf>,
    /// Configuration lines given on the command line (`-cnf-line`); they
    /// take precedence over the `texmf.cnf` files.
    pub cnf_lines: Vec<String>,
}

impl Options {
    /// Options for the `lualatex` program run by the `luahbtex` engine.
    pub fn lualatex() -> Self {
        Options {
            progname: "lualatex".into(),
            engine: "luahbtex".into(),
            selfautoloc: None,
            cache_dir: None,
            cnf_lines: Vec::new(),
        }
    }
}

/// A configured kpathsea instance.
pub struct Kpathsea {
    cnf: Cnf,
    env: Box<dyn Env>,
    progname: String,
    engine: String,
    /// Built-in variables (`SELFAUTOLOC`, `progname`, …).
    builtins: HashMap<String, String>,
    dbs: Vec<LsR>,
    dirs: DirCache,
    /// Expanded search paths, cached per format.
    paths: HashMap<FileFormat, Vec<String>>,
    /// Where parsed databases are cached.
    cache_dir: Option<PathBuf>,
    /// `TEXMF_OUTPUT_DIRECTORY` as set by the engine, if it was.
    output_directory: Option<Option<String>>,
    /// Whether names not found are looked for in other cases
    /// (`texmf_casefold_search`).
    casefold: bool,
}

impl std::fmt::Debug for Kpathsea {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Kpathsea")
            .field("progname", &self.progname)
            .field("engine", &self.engine)
            .finish_non_exhaustive()
    }
}

impl Kpathsea {
    /// Initializes kpathsea from the process environment.
    pub fn new(options: Options) -> Result<Self, Error> {
        Self::with_env(options, Box::new(ProcessEnv))
    }

    /// Initializes kpathsea with a custom environment.
    pub fn with_env(options: Options, env: Box<dyn Env>) -> Result<Self, Error> {
        let cache_dir = options.cache_dir.clone();
        let selfautoloc = options
            .selfautoloc
            .clone()
            .or_else(locate_kpsewhich_dir)
            .unwrap_or_else(|| PathBuf::from("/usr/bin"));
        let mut builtins = HashMap::new();
        let loc = slashed(&selfautoloc.to_string_lossy());
        let dir = parent(&loc);
        let par = parent(&dir);
        let grand = parent(&par);
        builtins.insert("SELFAUTOLOC".to_owned(), loc);
        builtins.insert("SELFAUTODIR".to_owned(), dir);
        builtins.insert("SELFAUTOPARENT".to_owned(), par);
        builtins.insert("SELFAUTOGRANDPARENT".to_owned(), grand);
        builtins.insert("progname".to_owned(), options.progname.clone());
        builtins.insert("engine".to_owned(), options.engine.clone());

        let mut cnf = Cnf::default();
        // The first definition of a variable wins.
        for line in &options.cnf_lines {
            cnf.parse(line);
        }
        let mut kpse = Kpathsea {
            cnf,
            env,
            progname: options.progname,
            engine: options.engine,
            builtins,
            dbs: Vec::new(),
            dirs: DirCache::default(),
            paths: HashMap::new(),
            cache_dir,
            output_directory: None,
            casefold: false,
        };
        let t0 = std::time::Instant::now();
        kpse.load_cnf()?;
        kpse.casefold = casefold::enabled(kpse.var_value("texmf_casefold_search").as_deref());
        let t1 = std::time::Instant::now();
        kpse.load_dbs()?;
        if std::env::var_os("RETEX_KPSE_TIMING").is_some() {
            eprintln!("kpse: cnf {:?}, dbs {:?}", t1 - t0, t1.elapsed());
        }
        Ok(kpse)
    }

    /// The program name.
    pub fn progname(&self) -> &str {
        &self.progname
    }

    /// The engine name.
    pub fn engine(&self) -> &str {
        &self.engine
    }

    fn load_cnf(&mut self) -> Result<(), Error> {
        let raw = self
            .getenv("TEXMFCNF")
            .map(|v| expand::expand_default(&v, &default_texmfcnf()))
            .unwrap_or_else(default_texmfcnf);
        let expanded = self.expand_vars(&raw);
        let mut found_any = false;
        for dir in expand::brace_expand_path(&expanded) {
            let dir = self.expand_tilde(&dir);
            let file = Path::new(&dir).join("texmf.cnf");
            match std::fs::read_to_string(&file) {
                Ok(text) => {
                    found_any = true;
                    self.cnf.parse(&text);
                }
                Err(e) if e.kind() == std::io::ErrorKind::NotFound => {}
                Err(e) if e.kind() == std::io::ErrorKind::NotADirectory => {}
                Err(source) => return Err(Error::Io { path: file, source }),
            }
        }
        if found_any {
            Ok(())
        } else {
            Err(Error::NoConfig(expanded))
        }
    }

    fn load_dbs(&mut self) -> Result<(), Error> {
        let dbs = self.var_value("TEXMFDBS").unwrap_or_default();
        let mut seen = Vec::new();
        for elt in expand::brace_expand_path(&dbs) {
            let elt = elt.trim_start_matches("!!");
            let elt = self.expand_tilde(elt);
            let root = elt.trim_end_matches('/').to_owned();
            if root.is_empty() || seen.contains(&root) {
                continue;
            }
            seen.push(root.clone());
            for name in ["ls-R", "ls-r"] {
                let file = Path::new(&root).join(name);
                let Ok(meta) = std::fs::metadata(&file) else {
                    continue;
                };
                let mtime = meta
                    .modified()
                    .ok()
                    .and_then(|t| t.duration_since(std::time::UNIX_EPOCH).ok())
                    .map_or((0, 0), |d| (d.as_secs() as i64, d.subsec_nanos()));
                let cache_file = self
                    .cache_dir
                    .as_ref()
                    .map(|d| d.join(format!("lsr-{:016x}.idx", content_key(root.as_bytes()))));
                if let Some(cf) = &cache_file
                    && let Ok(bytes) = std::fs::read(cf)
                    && let Some(db) = LsR::from_buf(bytes, meta.len(), mtime)
                {
                    self.dbs.push(db);
                    break;
                }
                match std::fs::read(&file) {
                    Ok(bytes) => {
                        let db = LsR::parse(&root, &bytes, meta.len(), mtime);
                        if let Some(cf) = &cache_file {
                            write_atomically(cf, db.bytes());
                        }
                        self.dbs.push(db);
                        break;
                    }
                    Err(e) if e.kind() == std::io::ErrorKind::NotFound => {}
                    Err(source) => return Err(Error::Io { path: file, source }),
                }
            }
        }
        Ok(())
    }

    /// The directory of retex's cache files, if any.
    pub fn cache_dir(&self) -> Option<&Path> {
        self.cache_dir.as_deref()
    }

    /// The names of the files ending with `suffix` in the `ls-R`
    /// databases (each once, sorted): what is installed, for suggestions.
    pub fn installed_names(&self, suffix: &str) -> Vec<String> {
        let mut out: std::collections::BTreeSet<&str> = std::collections::BTreeSet::new();
        for db in &self.dbs {
            out.extend(db.names().filter(|n| n.ends_with(suffix)));
        }
        out.into_iter().map(str::to_owned).collect()
    }

    /// Returns the expanded value of variable `name`, like
    /// `kpsewhich -var-value`. Braces are not expanded.
    pub fn var_value(&self, name: &str) -> Option<String> {
        let raw = self.raw_var(name)?;
        Some(self.expand_vars(&raw))
    }

    /// The environment's value of `name`. As with kpathsea, an empty value
    /// counts as unset (`TEXMFHOME= kpsewhich -var-value=TEXMFHOME` prints
    /// the value from texmf.cnf).
    fn getenv(&self, name: &str) -> Option<String> {
        self.env.var(name).filter(|v| !v.is_empty())
    }

    /// The environment's value of `name` (`name.progname`, `name_progname`
    /// or `name`).
    fn env_var(&self, name: &str) -> Option<String> {
        let dotted = format!("{name}.{}", self.progname);
        let underscored = format!("{name}_{}", self.progname);
        self.getenv(&dotted)
            .or_else(|| self.getenv(&underscored))
            .or_else(|| self.getenv(name))
    }

    /// The value of `name` from texmf.cnf or the built-in values.
    fn cnf_var(&self, name: &str) -> Option<String> {
        let value = self
            .cnf
            .get(name, &self.progname)
            .map(str::to_owned)
            .or_else(|| self.builtins.get(name).cloned())?;
        Some(self.expand_tilde(&value))
    }

    /// Looks a variable up without expansion: environment first
    /// (`NAME.progname`, `NAME_progname`, `NAME`), then the configuration
    /// files (`NAME.progname`, `NAME`), then built-in variables.
    fn raw_var(&self, name: &str) -> Option<String> {
        // kpathsea sets these itself, so they beat the environment and
        // texmf.cnf (observed: `SELFAUTOLOC=/x kpsewhich
        // -var-value=SELFAUTOLOC` prints kpsewhich's own directory).
        if matches!(
            name,
            "progname"
                | "engine"
                | "SELFAUTOLOC"
                | "SELFAUTODIR"
                | "SELFAUTOPARENT"
                | "SELFAUTOGRANDPARENT"
        ) {
            return self.builtins.get(name).cloned();
        }
        let dotted = format!("{name}.{}", self.progname);
        let underscored = format!("{name}_{}", self.progname);
        let value = self
            .getenv(&dotted)
            .or_else(|| self.getenv(&underscored))
            .or_else(|| self.getenv(name))
            .or_else(|| self.cnf.get(name, &self.progname).map(str::to_owned))
            .or_else(|| self.builtins.get(name).cloned())?;
        // A value starting with `~` refers to the home directory.
        Some(self.expand_tilde(&value))
    }

    /// Expands `$VAR` and `${VAR}` references recursively.
    fn expand_vars(&self, s: &str) -> String {
        expand::expand_vars(s, &|name| self.raw_var(name), 0)
    }

    fn expand_tilde(&self, s: &str) -> String {
        if let Some(rest) = s.strip_prefix('~')
            && (rest.is_empty() || rest.starts_with('/'))
        {
            let home = self.getenv("HOME").unwrap_or_default();
            return format!("{home}{rest}");
        }
        s.to_owned()
    }

    /// The fully expanded search path for `format`, one element per entry.
    /// Elements may start with `!!` and contain `//`.
    pub fn search_path(&mut self, format: FileFormat) -> &[String] {
        if !self.paths.contains_key(&format) {
            let info = format.info();
            // An environment value's extra colon (leading, trailing or
            // doubled) stands for the value from texmf.cnf (kpathsea
            // manual, "Default expansion").
            // The environment comes first, for all the format's variables
            // (`TEXFONTS` for any font format), then texmf.cnf.
            let mut raw = None;
            let vars = format.variables(&self.progname);
            if let Some(env) = vars.iter().find_map(|v| self.env_var(v)) {
                let below = vars
                    .iter()
                    .find_map(|v| self.cnf_var(v))
                    .unwrap_or_else(|| info.default_path.to_owned());
                raw = Some(expand::expand_default(&self.expand_tilde(&env), &below));
            }
            if raw.is_none() {
                raw = vars.iter().find_map(|v| self.raw_var(v));
            }
            let raw = raw.unwrap_or_else(|| info.default_path.to_owned());
            let expanded = self.expand_vars(&raw);
            let elts: Vec<String> = expand::brace_expand_path(&expanded)
                .into_iter()
                .map(|e| match e.strip_prefix("!!") {
                    Some(rest) => format!("!!{}", self.expand_tilde(rest)),
                    None => self.expand_tilde(&e),
                })
                .filter(|e| !e.is_empty())
                .collect();
            self.paths.insert(format, elts);
        }
        &self.paths[&format]
    }

    /// Finds the first file matching `name` in the search path of `format`,
    /// like `kpsewhich -format=… name`.
    pub fn find_file(&mut self, name: &str, format: FileFormat) -> Option<PathBuf> {
        let candidates = candidate_names(name, format);
        // Absolute and explicitly relative names bypass the search path.
        if is_absolute_or_explicit_relative(name) {
            let exact = candidates.iter().map(PathBuf::from).find(|p| p.is_file());
            if exact.is_some() || !self.casefold {
                return exact;
            }
            return candidates.iter().find_map(|c| {
                let p = Path::new(c);
                let dir = p.parent().filter(|d| !d.as_os_str().is_empty())?;
                casefold::find(dir, p.file_name()?.to_str()?)
            });
        }
        let path = self.search_path(format).to_vec();
        for elt in &path {
            if let Some(found) = self.search_element(elt, &candidates) {
                return Some(found);
            }
        }
        None
    }

    /// Searches one path element for any of `names`, returning the first
    /// match.
    fn search_element(&mut self, elt: &str, names: &[String]) -> Option<PathBuf> {
        let (db_only, elt) = match elt.strip_prefix("!!") {
            Some(rest) => (true, rest),
            None => (false, elt),
        };
        // Database lookup when a database covers this element.
        if let Some(db) = self.dbs.iter().find(|db| db.covers(elt)) {
            for name in names {
                if let Some(found) = db.lookup(name, elt) {
                    return Some(found);
                }
            }
            if db_only {
                return None;
            }
        } else if db_only {
            return None;
        }
        let dirs = self.dirs.expand(elt);
        for dir in &dirs {
            for name in names {
                let candidate = PathBuf::from(join(dir, name));
                if candidate.is_file() {
                    return Some(candidate);
                }
            }
        }
        if self.casefold {
            for dir in &dirs {
                for name in names {
                    if let Some(found) = casefold::find(Path::new(dir), name) {
                        return Some(found);
                    }
                }
            }
        }
        None
    }
}

/// A stable key for cache file names (FNV-1a).
fn content_key(b: &[u8]) -> u64 {
    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
    for &x in b {
        h ^= u64::from(x);
        h = h.wrapping_mul(0x0100_0000_01b3);
    }
    h
}

/// Writes a cache file via a temporary file and a rename; failures are
/// ignored (the cache is an optimization).
fn write_atomically(path: &Path, data: &[u8]) {
    if let Some(dir) = path.parent() {
        let _ = std::fs::create_dir_all(dir);
    }
    let tmp = path.with_extension(format!("tmp{}", std::process::id()));
    if std::fs::write(&tmp, data).is_ok() && std::fs::rename(&tmp, path).is_err() {
        let _ = std::fs::remove_file(&tmp);
    }
}

/// The names to try for `name`: with each standard suffix first (unless it
/// already has one), then the name itself.
fn candidate_names(name: &str, format: FileFormat) -> Vec<String> {
    let info = format.info();
    let has_suffix = info
        .suffixes
        .iter()
        .chain(info.alt_suffixes)
        .any(|s| name.ends_with(s));
    let mut out = Vec::new();
    if !has_suffix {
        for s in info.suffixes {
            out.push(format!("{name}{s}"));
        }
    }
    if has_suffix || info.bare {
        out.push(name.to_owned());
    }
    out
}

fn is_absolute_or_explicit_relative(name: &str) -> bool {
    name.starts_with('/')
        || name.starts_with("./")
        || name.starts_with("../")
        || (cfg!(windows)
            && (Path::new(name).is_absolute()
                || name.starts_with('\\')
                || name.starts_with(".\\")
                || name.starts_with("..\\")))
}

fn parent(p: &str) -> String {
    let trimmed = p.trim_end_matches('/');
    if trimmed.is_empty() && p.starts_with('/') {
        return "/".to_owned();
    }
    match trimmed.rfind('/') {
        Some(0) => "/".to_owned(),
        Some(i) => trimmed[..i].to_owned(),
        None => ".".to_owned(),
    }
}

/// `dir/name`, with `/` as kpathsea joins names, also on Windows (where
/// `Path::join` would put `\\`): `./paper.tex` appears in logs as such.
pub(crate) fn join(dir: &str, name: &str) -> String {
    if dir.ends_with('/') || (cfg!(windows) && dir.ends_with('\\')) {
        format!("{dir}{name}")
    } else {
        format!("{dir}/{name}")
    }
}

/// A directory name as kpathsea writes it: with `/` (also on Windows,
/// where `\\?\\` before a canonical name is dropped).
fn slashed(p: &str) -> String {
    if cfg!(windows) {
        p.strip_prefix(r"\\?\").unwrap_or(p).replace('\\', "/")
    } else {
        p.to_owned()
    }
}

/// Locates the directory of `kpsewhich` on `PATH`, resolving symlinks.
fn locate_kpsewhich_dir() -> Option<PathBuf> {
    let path = std::env::var_os("PATH")?;
    for dir in std::env::split_paths(&path) {
        let candidate = dir.join(format!("kpsewhich{}", std::env::consts::EXE_SUFFIX));
        if candidate.is_file() {
            let real = std::fs::canonicalize(&candidate).unwrap_or(candidate);
            return real.parent().map(Path::to_path_buf);
        }
    }
    None
}

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

    #[test]
    fn candidates_add_suffix_first() {
        // `.cls` is an alternate suffix of the tex format.
        assert_eq!(
            candidate_names("article.cls", FileFormat::Tex),
            vec!["article.cls"]
        );
        assert_eq!(
            candidate_names("a.foo", FileFormat::Tex),
            vec!["a.foo.tex", "a.foo"]
        );
        assert_eq!(candidate_names("foo.tex", FileFormat::Tex), vec!["foo.tex"]);
    }

    #[test]
    fn parent_dirs() {
        assert_eq!(parent("/usr/bin"), "/usr");
        assert_eq!(parent("/usr"), "/");
        assert_eq!(parent("/"), "/");
    }
}