retex-kpath 1.3.0-alpha.2

//! `ls-R` filename databases and on-disk directory expansion.

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

/// One parsed `ls-R` database, in its serialized form.
///
/// The index is a single byte buffer (the same bytes as the on-disk cache):
/// a header, the directory names, the raw database text, and entries of
/// (name hash, name offset, name length, directory index) sorted by hash.
/// Lookups binary-search the entries in place, so loading a cached index
/// costs one file read and no per-entry work.
#[derive(Debug)]
pub struct LsR {
    buf: Vec<u8>,
    root: String,
    /// Offset (into `buf`) of each directory record.
    dir_offsets: Vec<u32>,
    data_at: usize,
    entries_at: usize,
    n_entries: usize,
}

/// Magic bytes of a serialized ls-R index.
const CACHE_MAGIC: &[u8; 8] = b"RTXLSR03";
const ENTRY: usize = 20;

/// FNV-1a over a file name.
fn name_hash(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
}

fn rd_u32(b: &[u8], at: usize) -> Option<u32> {
    Some(u32::from_le_bytes(b.get(at..at + 4)?.try_into().ok()?))
}

fn rd_u64(b: &[u8], at: usize) -> Option<u64> {
    Some(u64::from_le_bytes(b.get(at..at + 8)?.try_into().ok()?))
}

impl LsR {
    /// Parses the content of the `ls-R` file at the root of `root`. `size`
    /// and `mtime` identify the source for cache validation.
    pub fn parse(root: &str, bytes: &[u8], size: u64, mtime: (i64, u32)) -> LsR {
        let mut dirs: Vec<String> = Vec::new();
        let mut entries: Vec<(u64, u32, u32, u32)> = Vec::with_capacity(bytes.len() / 16);
        let mut current: Option<u32> = None;
        let mut pos = 0usize;
        while pos < bytes.len() {
            let end = memchr_nl(bytes, pos);
            let mut line = &bytes[pos..end];
            let start = pos;
            pos = end + 1;
            if let Some(l) = line.strip_suffix(b"\r") {
                line = l;
            }
            if line.is_empty() || line[0] == b'%' {
                continue;
            }
            if let Some(dir) = line.strip_suffix(b":") {
                let dir = String::from_utf8_lossy(dir);
                let rel = dir.strip_prefix("./").unwrap_or(&dir);
                let abs = if dir.starts_with('/') {
                    dir.trim_end_matches('/').to_owned()
                } else if rel == "." || rel.is_empty() {
                    root.to_owned()
                } else {
                    format!("{root}/{}", rel.trim_end_matches('/'))
                };
                // Hidden directories are skipped, as in kpathsea.
                let hidden = rel.split('/').any(|c| c.starts_with('.') && c != ".");
                current = if hidden {
                    None
                } else {
                    dirs.push(format!("{abs}/"));
                    Some((dirs.len() - 1) as u32)
                };
                continue;
            }
            if let Some(idx) = current {
                if line == b"." || line == b".." {
                    continue;
                }
                entries.push((name_hash(line), start as u32, line.len() as u32, idx));
            }
        }
        // ls-R lists subdirectories as entries of their parent too; they
        // are not files, so drop them (each also has its own section).
        let dir_set: std::collections::HashSet<&str> = dirs.iter().map(String::as_str).collect();
        entries.retain(|&(_, off, len, d)| {
            let name = String::from_utf8_lossy(&bytes[off as usize..(off + len) as usize]);
            !dir_set.contains(format!("{}{name}/", dirs[d as usize]).as_str())
        });
        // Stable sort keeps database order among equal hashes.
        entries.sort_by_key(|e| e.0);
        // Serialize.
        let mut out = Vec::with_capacity(bytes.len() + entries.len() * ENTRY + dirs.len() * 48);
        out.extend_from_slice(CACHE_MAGIC);
        out.extend_from_slice(&size.to_le_bytes());
        out.extend_from_slice(&(mtime.0 as u64).to_le_bytes());
        out.extend_from_slice(&mtime.1.to_le_bytes());
        out.extend_from_slice(&(root.len() as u32).to_le_bytes());
        out.extend_from_slice(root.as_bytes());
        out.extend_from_slice(&(dirs.len() as u32).to_le_bytes());
        for d in &dirs {
            out.extend_from_slice(&(d.len() as u32).to_le_bytes());
            out.extend_from_slice(d.as_bytes());
        }
        out.extend_from_slice(&(bytes.len() as u32).to_le_bytes());
        out.extend_from_slice(bytes);
        out.extend_from_slice(&(entries.len() as u32).to_le_bytes());
        for e in &entries {
            out.extend_from_slice(&e.0.to_le_bytes());
            out.extend_from_slice(&e.1.to_le_bytes());
            out.extend_from_slice(&e.2.to_le_bytes());
            out.extend_from_slice(&e.3.to_le_bytes());
        }
        LsR::from_buf(out, size, mtime).expect("freshly serialized index is valid")
    }

    /// The serialized index (written to the cache).
    pub fn bytes(&self) -> &[u8] {
        &self.buf
    }

    /// Uses a serialized index if it is valid and matches the source's size
    /// and modification time.
    pub fn from_buf(buf: Vec<u8>, size: u64, mtime: (i64, u32)) -> Option<LsR> {
        if buf.get(..8)? != CACHE_MAGIC {
            return None;
        }
        if rd_u64(&buf, 8)? != size
            || rd_u64(&buf, 16)? as i64 != mtime.0
            || rd_u32(&buf, 24)? != mtime.1
        {
            return None;
        }
        let mut at = 28;
        let rl = rd_u32(&buf, at)? as usize;
        let root = std::str::from_utf8(buf.get(at + 4..at + 4 + rl)?)
            .ok()?
            .to_owned();
        at += 4 + rl;
        let n_dirs = rd_u32(&buf, at)? as usize;
        at += 4;
        let mut dir_offsets = Vec::with_capacity(n_dirs);
        for _ in 0..n_dirs {
            dir_offsets.push(at as u32);
            let l = rd_u32(&buf, at)? as usize;
            at += 4 + l;
        }
        let dl = rd_u32(&buf, at)? as usize;
        let data_at = at + 4;
        at = data_at + dl;
        let n_entries = rd_u32(&buf, at)? as usize;
        let entries_at = at + 4;
        if buf.len() < entries_at + n_entries.checked_mul(ENTRY)? {
            return None;
        }
        let db = LsR {
            buf,
            root,
            dir_offsets,
            data_at,
            entries_at,
            n_entries,
        };
        Some(db)
    }

    /// Whether this database is responsible for path element `elt`.
    pub fn covers(&self, elt: &str) -> bool {
        elt.starts_with(&self.root)
            && matches!(elt.as_bytes().get(self.root.len()), None | Some(b'/'))
    }

    fn entry(&self, i: usize) -> (u64, usize, usize, usize) {
        let at = self.entries_at + i * ENTRY;
        let b = &self.buf;
        (
            rd_u64(b, at).unwrap_or(0),
            rd_u32(b, at + 8).unwrap_or(0) as usize,
            rd_u32(b, at + 12).unwrap_or(0) as usize,
            rd_u32(b, at + 16).unwrap_or(0) as usize,
        )
    }

    /// The name of directory `i` (absolute, with trailing slash).
    fn dir(&self, i: usize) -> &str {
        let Some(&at) = self.dir_offsets.get(i) else {
            return "";
        };
        let at = at as usize;
        let l = rd_u32(&self.buf, at).unwrap_or(0) as usize;
        std::str::from_utf8(self.buf.get(at + 4..at + 4 + l).unwrap_or(&[])).unwrap_or("")
    }

    /// The file names in the database.
    pub fn names(&self) -> impl Iterator<Item = &str> {
        (0..self.n_entries).filter_map(|i| {
            let (_, off, len, _) = self.entry(i);
            let start = self.data_at + off;
            std::str::from_utf8(self.buf.get(start..start + len)?).ok()
        })
    }

    /// Finds `name` (which may contain directory components) in a directory
    /// matching the path element `elt`.
    pub fn lookup(&self, name: &str, elt: &str) -> Option<PathBuf> {
        let (subdir, base) = match name.rfind('/') {
            Some(i) => (&name[..=i], &name[i + 1..]),
            None => ("", name),
        };
        let h = name_hash(base.as_bytes());
        // Binary search for the first entry with this hash.
        let (mut lo, mut hi) = (0usize, self.n_entries);
        while lo < hi {
            let mid = (lo + hi) / 2;
            if self.entry(mid).0 < h {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        let mut i = lo;
        while i < self.n_entries {
            let (eh, off, len, d) = self.entry(i);
            if eh != h {
                break;
            }
            let start = self.data_at + off;
            if self.buf.get(start..start + len) == Some(base.as_bytes()) {
                let dir = self.dir(d);
                if dir
                    .strip_suffix(subdir)
                    .is_some_and(|parent| elt_matches(elt, parent))
                {
                    return Some(PathBuf::from(format!("{dir}{base}")));
                }
            }
            i += 1;
        }
        None
    }
}

/// Position of the next newline at or after `pos` (or the end).
fn memchr_nl(data: &[u8], pos: usize) -> usize {
    data[pos..]
        .iter()
        .position(|&b| b == b'\n')
        .map_or(data.len(), |i| pos + i)
}

/// Whether directory `dir` (absolute, with trailing slash) matches the
/// path element `elt`, where `//` stands for any sequence of directories.
pub fn elt_matches(elt: &str, dir: &str) -> bool {
    let elt = if elt.ends_with('/') {
        elt.to_owned()
    } else {
        format!("{elt}/")
    };
    match_parts(&elt, dir)
}

fn match_parts(pattern: &str, dir: &str) -> bool {
    match pattern.find("//") {
        None => pattern == dir,
        Some(i) => {
            // Literal prefix up to and including the first slash of `//`.
            let prefix = &pattern[..=i];
            let rest = &pattern[i + 2..];
            let Some(tail) = dir.strip_prefix(prefix) else {
                return false;
            };
            if rest.is_empty() {
                return true;
            }
            // Try every directory boundary in `tail` as the start of `rest`.
            let mut start = 0;
            loop {
                if match_parts(&format!("/{rest}"), &format!("/{}", &tail[start..])) {
                    return true;
                }
                match tail[start..].find('/') {
                    Some(j) => start += j + 1,
                    None => return false,
                }
            }
        }
    }
}

/// Cache of on-disk directory expansions for path elements not covered by a
/// database.
#[derive(Debug, Default)]
pub struct DirCache {
    expanded: HashMap<String, Vec<String>>,
}

impl DirCache {
    /// The directories that path element `elt` stands for, in search order.
    pub fn expand(&mut self, elt: &str) -> Vec<String> {
        if let Some(v) = self.expanded.get(elt) {
            return v.clone();
        }
        let mut out = Vec::new();
        expand_elt(elt, &mut out);
        self.expanded.insert(elt.to_owned(), out.clone());
        out
    }
}

fn expand_elt(elt: &str, out: &mut Vec<String>) {
    match elt.find("//") {
        None => {
            if Path::new(elt).is_dir() {
                out.push(elt.to_owned());
            }
        }
        Some(i) => {
            let base = &elt[..i];
            let base = if base.is_empty() { "/" } else { base };
            let rest = &elt[i + 2..];
            let mut subdirs = Vec::new();
            collect_subdirs(Path::new(base), &mut subdirs);
            for dir in subdirs {
                if rest.is_empty() {
                    out.push(dir);
                } else {
                    expand_elt(&format!("{dir}/{rest}"), out);
                }
            }
        }
    }
}

/// Collects `dir` and all its subdirectories, depth first, in name order.
fn collect_subdirs(dir: &Path, out: &mut Vec<String>) {
    if !dir.is_dir() {
        return;
    }
    out.push(dir.to_string_lossy().into_owned());
    let Ok(entries) = std::fs::read_dir(dir) else {
        return;
    };
    let mut children: Vec<PathBuf> = entries
        .filter_map(Result::ok)
        .filter(|e| e.file_type().map(|t| t.is_dir()).unwrap_or(false))
        .filter(|e| !e.file_name().to_string_lossy().starts_with('.'))
        .map(|e| e.path())
        .collect();
    children.sort();
    for child in children {
        collect_subdirs(&child, out);
    }
}

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

    #[test]
    fn element_matching() {
        assert!(elt_matches("/t/tex//", "/t/tex/latex/base/"));
        assert!(elt_matches("/t/tex//", "/t/tex/"));
        assert!(!elt_matches("/t/tex/", "/t/tex/latex/"));
        assert!(elt_matches("/t/tex/", "/t/tex/"));
        assert!(elt_matches("/t//base/", "/t/a/b/base/"));
        assert!(!elt_matches("/t//base/", "/t/a/b/based/"));
        assert!(!elt_matches("/t/tex//", "/t/texmf/"));
    }

    #[test]
    fn lsr_lookup() {
        let db = LsR::parse(
            "/r",
            b"% ls-R\n./:\ntex\n\n./tex/latex/base:\narticle.cls\n\n./tex/.git:\narticle.cls\n",
            0,
            (0, 0),
        );
        assert!(db.covers("/r/tex//"));
        assert!(!db.covers("/rx/tex//"));
        assert_eq!(
            db.lookup("article.cls", "/r/tex//"),
            Some(PathBuf::from("/r/tex/latex/base/article.cls"))
        );
        assert_eq!(
            db.lookup("base/article.cls", "/r/tex//"),
            Some(PathBuf::from("/r/tex/latex/base/article.cls"))
        );
        assert_eq!(db.lookup("article.cls", "/r/fonts//"), None);
    }

    #[test]
    fn directories_are_not_files() {
        // tex/latex/xkeyval is a directory listed in tex/latex; looking up
        // "xkeyval" must not find it (kpsewhich finds xkeyval.tex instead).
        let db = LsR::parse(
            "/r",
            b"./tex/latex:\nxkeyval\n\n./tex/latex/xkeyval:\nxkeyval.sty\n\n\
              ./tex/generic/xkeyval:\nxkeyval.tex\n",
            0,
            (0, 0),
        );
        assert_eq!(db.lookup("xkeyval", "/r/tex//"), None);
        assert_eq!(
            db.lookup("xkeyval.tex", "/r/tex//"),
            Some(PathBuf::from("/r/tex/generic/xkeyval/xkeyval.tex"))
        );
    }
}