log --path and touches() without decoding all of history 170bb436e1d5

//! The nodes each change touches, kept beside the store (oxygen#91).

//!

//! Finding the changes that touched a file (`oxy log --path`, the

//! `touches()` revset) otherwise reads and decodes every change of the

//! history, its lines included. A change is immutable, so its entry never

//! goes stale: one missing is read from the store once and added. Like

//! Git's changed-path filters it is derived data, and deleting

//! `.oxy/index/touched` loses nothing but time.

use super::*;

use crate::fasthash::FastMap;

use crate::ids::NodeId;

/// The cache, loaded; [`Touched::save`] writes it back when it grew.

pub(crate) struct Touched {

    nodes: FastMap<ChangeHash, Box<[NodeId]>>,

    /// Working-copy changes, which a snapshot replaces: kept for this

    /// command only, so the cache does not fill with dead entries.

    transient: FastMap<ChangeHash, Box<[NodeId]>>,

    added: usize,

    path: PathBuf,

}

impl Touched {

    /// The nodes `h` touches, from the cache or else from the store; `None`

    /// when the change is not stored (beyond a shallow boundary).

    pub(crate) fn of(&mut self, repo: &Repo, h: &ChangeHash) -> Option<&[NodeId]> {

        if !self.nodes.contains_key(h) && !self.transient.contains_key(h) {

            // The skeleton names every node; no text is read.

            let (c, _) = repo.store.get_change_lazy(h).ok()?;

            self.keep(*h, &c);

        }

        self.nodes

            .get(h)

            .or_else(|| self.transient.get(h))

            .map(|n| &n[..])

    }

    fn keep(&mut self, h: ChangeHash, c: &Change) {

        if c.kind == ChangeKind::WorkingCopy {

            self.transient.insert(h, nodes_of(c));

        } else {

            self.nodes.insert(h, nodes_of(c));

            self.added += 1;

        }

    }

    /// Read every one of `hashes` the cache lacks.

    pub(crate) fn fill(&mut self, repo: &Repo, hashes: &[ChangeHash]) {

        use rayon::prelude::*;

        let missing: Vec<ChangeHash> = hashes

            .iter()

            .filter(|h| !self.nodes.contains_key(*h) && !self.transient.contains_key(*h))

            .copied()

            .collect();

        // Read a batch at a time, then decode skeletons (no text) on every

        // core. A change the store lacks is left out, as `of` leaves it.

        for batch in missing.chunks(8192) {

            let read: Vec<(ChangeHash, Change)> = repo

                .store

                .get_many(batch)

                .into_par_iter()

                .zip(batch.par_iter())

                .filter_map(|(got, h)| match got {

                    Ok((ObjectType::Change, bytes)) => {

                        Some((*h, Change::decode_skeleton(&bytes, *h).ok()?.0))

                    }

                    _ => None,

                })

                .collect();

            for (h, c) in &read {

                self.keep(*h, c);

            }

        }

    }

    /// Whether `h` touches any of `nodes` (false when it is not stored).

    pub(crate) fn touches(&mut self, repo: &Repo, h: &ChangeHash, nodes: &HashSet<NodeId>) -> bool {

        self.of(repo, h)

            .is_some_and(|n| n.iter().any(|n| nodes.contains(n)))

    }

    /// Write the cache back if it grew; quietly nothing when it cannot be.

    pub(crate) fn save(self) {

        if self.added == 0 {

            return;

        }

        let _t = crate::timing::phase("write: touched nodes");

        let mut w = crate::flat::Writer::default();

        w.count(self.nodes.len());

        for (h, nodes) in &self.nodes {

            w.object(h);

            w.count(nodes.len());

            for n in nodes.iter() {

                w.fixed(&n.0);

            }

        }

        // Checked whole on reading: a damaged entry would hide a change.

        let sum = *blake3::hash(&w.0).as_bytes();

        w.fixed(&sum);

        let _ = fs::create_dir_all(self.path.parent().unwrap_or(&self.path));

        let _ = write_cache(&self.path, &w.0);

    }

}

/// The nodes a change's tree operations and edits name, each once.

fn nodes_of(c: &Change) -> Box<[NodeId]> {

    let mut nodes: Vec<NodeId> = c

        .tree_ops

        .iter()

        .map(|o| o.node())

        .chain(c.edits.iter().map(|e| e.node()))

        .collect();

    nodes.sort();

    nodes.dedup();

    nodes.into_boxed_slice()

}

impl Repo {

    /// The touched-nodes cache: empty when there is none yet or it does

    /// not read back whole.

    pub(crate) fn touched(&self) -> Touched {

        let _t = crate::timing::phase("load: touched nodes");

        let path = self.oxy.join("index").join("touched");

        let nodes = fs::read(&path)

            .ok()

            .and_then(|b| read_touched(&b))

            .unwrap_or_default();

        Touched {

            nodes,

            transient: FastMap::default(),

            added: 0,

            path,

        }

    }

}

fn read_touched(bytes: &[u8]) -> Option<FastMap<ChangeHash, Box<[NodeId]>>> {

    let (body, sum) = bytes.split_at_checked(bytes.len().checked_sub(32)?)?;

    if blake3::hash(body).as_bytes() != sum {

        return None;

    }

    let mut r = crate::flat::Reader::new(body);

    let n = r.count().ok()?;

    let mut out = FastMap::default();

    out.reserve(n);

    for _ in 0..n {

        let h = r.object().ok()?;

        let k = r.count().ok()?;

        let mut nodes = Vec::with_capacity(k);

        for _ in 0..k {

            nodes.push(NodeId(r.fixed::<16>().ok()?));

        }

        out.insert(h, nodes.into_boxed_slice());

    }

    r.at_end().then_some(out)

}

/// The changes a cache file holds, for tests.

#[cfg(test)]

pub(crate) fn read_touched_for_test(bytes: &[u8]) -> Option<HashSet<ChangeHash>> {

    read_touched(bytes).map(|m| m.into_keys().collect())

}

## Unreleased

- **A file's history in a fraction of a second (#91).** `oxy log --path` rendered every file of the tree twice just to find the path, and both it and the `touches()` revset decoded every change of the history, its text included, to see what each one touched. They now read the path from the tree alone and keep the nodes each change touches in a cache beside the store (`.oxy/index/touched`, rebuilt if missing). On VS Code at 20 000 commits, `log --path package.json` went from 53.6 s to 0.16 s (Git: 0.15 s) and `touches("package.json")` from 3.4 s to 0.16 s, with the same output.

mod touched;

        // The tree alone names the nodes: no file graph is built. The

        // working copy's base comes from the workspace's state index.

        let state = match self.working_copy() {

            Some(wc) => {

                let deps = self

                    .graph

                    .get(&wc)

                    .map(|m| m.deps.clone())

                    .or_else(|| self.repo.working_copy().ok().map(|(_, c)| c.deps))

                    .unwrap_or_default();

                self.repo.load_state_indexed(&deps)?

            }

            None => self.repo.load_state_history(&self.repo.bookmark_heads()?)?,

        let mut touched = self.repo.touched();

        touched.fill(self.repo, &candidates.iter().copied().collect::<Vec<_>>());

            if touched.touches(self.repo, h, &nodes) {

        touched.save();

        // The path's node from the trees alone: the base's (from the

        // workspace's state index), else the bookmark's. Nothing is

        // rendered.

        let node_in = |state: State| state.tree().view().entries.get(path).map(|e| e.node);

        let node = match node_in(self.load_state_indexed(&wc.deps)?) {

            Some(n) => Some(n),

            None => node_in(self.load_state_history(&heads)?),

        };

        let mut touched = self.touched();

        if limit.is_none() {

            let hashes: Vec<ChangeHash> = entries.iter().map(|e| e.hash).collect();

            touched.fill(self, &hashes);

        }

        let wanted = HashSet::from([node]);

            if touched.touches(self, &e.hash, &wanted) {

        touched.save();

#[test]

fn touched_nodes_cache_answers_as_the_changes_do() {

    hermetic();

    let dir = tempfile::tempdir().unwrap();

    let repo = Repo::init(dir.path()).unwrap();

    write(dir.path(), "a.txt", b"one\n");

    write(dir.path(), "b.txt", b"x\n");

    repo.snapshot("t").unwrap();

    let c1 = repo.commit("first", &[]).unwrap();

    write(dir.path(), "b.txt", b"y\n");

    repo.snapshot("t").unwrap();

    repo.commit("b only", &[]).unwrap();

    fs::rename(dir.path().join("a.txt"), dir.path().join("c.txt")).unwrap();

    write(dir.path(), "c.txt", b"one\ntwo\n");

    repo.snapshot("t").unwrap();

    let c3 = repo.commit("rename and edit", &[]).unwrap();

    // Uncommitted work, so the working copy touches a file too.

    write(dir.path(), "c.txt", b"one\ntwo\nthree\n");

    repo.snapshot("t").unwrap();

    let path = dir.path().join(".oxy/index/touched");

    let hashes = |es: Vec<LogEntry>| es.iter().map(|e| e.hash).collect::<Vec<_>>();

    let cold = hashes(repo.log_for_path("c.txt").unwrap());

    assert!(path.exists(), "the first query writes the cache");

    let warm = hashes(repo.log_for_path("c.txt").unwrap());

    assert_eq!(cold, warm, "the cache answers as the changes do");

    let (wc, _) = repo.working_copy().unwrap();

    assert_eq!(

        cold,

        vec![wc, c3, c1],

        "renames followed, the working copy included"

    );

    // Working-copy changes are not kept: they are replaced by every snapshot.

    let cached = super::touched::read_touched_for_test(&fs::read(&path).unwrap()).unwrap();

    assert!(!cached.contains(&wc), "a working-copy change is not cached");

    assert!(cached.contains(&c1) && cached.contains(&c3));

    // A damaged cache is ignored, not trusted.

    let mut bytes = fs::read(&path).unwrap();

    let last = bytes.len() - 40;

    bytes[last] ^= 1;

    fs::write(&path, &bytes).unwrap();

    assert_eq!(hashes(repo.log_for_path("c.txt").unwrap()), cold);

    let touches = repo.log_revset("touches(\"c.txt\") ~ @").unwrap();

    assert_eq!(hashes(touches), vec![c3, c1]);

}

  index/              derived caches, rebuilt when missing or damaged: each

                      workspace's state indexes, and the nodes each change touches