log and the state index without needless copies 79b5a90ffd43

- **A quicker log and diff on long histories (#94, first part).** `oxy log` no longer reads the working copy's metadata through the store's cache, walks the history with a fast hash and without copying each change's metadata, and works out the shortest unique id prefixes for the changes it shows rather than for every change. The state index is read without copying the file histories in it, and its change list is checked on every core. On VS Code at 20 000 commits, `log -n 20` went from 74 ms to 40 ms and loading the state index from 43 ms to 28 ms, with the same output.

        let at = 4 + 32 * heads.len() + 64;

        let body = bytes.get(at..)?;

        let sum = |b: &[u8]| *blake3::Hasher::new().update_rayon(b).finalize().as_bytes();

        if sum(changes) != changes_sum.0 || sum(rest) != rest_sum.0 {

        // The histories point into this buffer rather than copying it.

        Some((

            State::read_index_in(&std::sync::Arc::new(bytes), at).ok()?,

            heads,

        ))

        let checking = crate::timing::phase("load:   of which checking");

        let mut h = blake3::Hasher::new();

        h.update_rayon(&changes);

        if h.finalize().as_bytes() != sum {

        drop(checking);

        let _decoding = crate::timing::phase("load:   of which decoding");

        w.fixed(

            blake3::Hasher::new()

                .update_rayon(&body[..split])

                .finalize()

                .as_bytes(),

        );

        let (wc_hash, wc) = self.working_copy()?;

            // The working copy's change is in hand, and is never in the

            // state index: its metadata is not looked up again.

            let mut below: Vec<ChangeHash> = head_set.iter().copied().collect();

            below.extend(wc.deps.iter().copied());

            let _t = crate::timing::phase("log: metadata");

            let mut metas = self.metas_of(&below)?;

            if !metas.iter().any(|(h, _)| *h == wc_hash) {

                metas.push((wc_hash, crate::state::ChangeMeta::of(&wc)));

            }

            metas

        let _sorting = crate::timing::phase("log: sort");

        // The hash makes the order total, so an unstable sort gives the same.

        entries.sort_unstable_by(|a, b| {

        entries.sort_unstable_by(|a, b| b.change.hlc.cmp(&a.change.hlc).then(b.hash.cmp(&a.hash)));

        let mut indexed = self.read_state_index_changes();

        let _walk = crate::timing::phase("metadata: walk");

        let mut seen: crate::fasthash::FastSet<ChangeHash> = Default::default();

        let mut out = Vec::with_capacity(indexed.as_ref().map_or(0, |m| m.len()));

            // Taken out of the index's map, each once: not copied.

            if let Some(meta) = indexed.as_mut().and_then(|m| m.remove(&h)) {

                    *meta,

                let meta = std::sync::Arc::unwrap_or_clone(meta);

                out.push((h, meta));

        entries.sort_unstable_by(|a, b| b.change.hlc.cmp(&a.change.hlc).then(b.hash.cmp(&a.hash)));

    raw: Option<(Arc<Vec<u8>>, std::ops::Range<usize>)>,

        Self::read_index_in(&Arc::new(bytes.to_vec()), 0)

    }

    /// As [`State::read_index`], for an index at `at` in `file`, which the

    /// files' histories keep pointing into rather than copying: most of an

    /// index is histories a command never decodes.

    pub fn read_index_in(file: &Arc<Vec<u8>>, at: usize) -> Result<State, ObjectError> {

        let bytes = file.get(at..).ok_or_else(|| bad("truncated"))?;

        let start = deferred_bytes.as_ptr() as usize - file.as_ptr() as usize;

            || Self::read_deferred(file, start..start + deferred_bytes.len()),

        file: &Arc<Vec<u8>>,

        within: std::ops::Range<usize>,

        let mut r = Reader::new(&file[within]);

            let start = body.as_ptr() as usize - file.as_ptr() as usize;

                raw: Some((file.clone(), start..start + body.len())),

    let prefixes = oxy_core::timing::phase("log: id prefixes");

    let id_prefix = id_prefixes(

        all.iter().map(|e| e.change.change_id.0).collect(),

        entries.iter().take(shown).map(|e| e.change.change_id.0),

    );

    drop(prefixes);

        let n = id_prefix.get(&c.change_id.0).copied().unwrap_or(8).min(8);

/// The shortest prefix, in hex digits, that names each of `wanted` among

/// `all`: worked out for the few shown rather than for the whole history.

fn id_prefixes(

    mut all: Vec<[u8; 16]>,

    wanted: impl Iterator<Item = [u8; 16]>,

) -> std::collections::HashMap<[u8; 16], usize> {

    all.sort_unstable();

    all.dedup();

    // Hex digits two ids share at the start.

    let common = |a: &[u8; 16], b: &[u8; 16]| {

        let bytes = a.iter().zip(b).take_while(|(x, y)| x == y).count();

        match (a.get(bytes), b.get(bytes)) {

            (Some(x), Some(y)) if x >> 4 == y >> 4 => 2 * bytes + 1,

            _ => 2 * bytes,

        }

    };

    let mut out = std::collections::HashMap::new();

    for id in wanted {

        let Ok(i) = all.binary_search(&id) else {

            continue;

        };

        let before = i.checked_sub(1).map_or(0, |j| common(&all[j], &id));

        let after = all.get(i + 1).map_or(0, |n| common(&id, n));

        out.insert(id, before.max(after) + 1);

    }

    out

}

}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn id_prefixes_agree_with_the_whole_list() {

        // Ids that share long prefixes, and some that differ only in a

        // half byte, from a fixed sequence.

        let mut x: u64 = 0x9e37_79b9_7f4a_7c15;

        let mut next = || {

            x ^= x << 13;

            x ^= x >> 7;

            x ^= x << 17;

            x

        };

        let mut ids: Vec<[u8; 16]> = Vec::new();

        for _ in 0..2000 {

            let mut id = [0u8; 16];

            id[..8].copy_from_slice(&next().to_le_bytes());

            id[8..].copy_from_slice(&next().to_le_bytes());

            let share = (next() % 4) as usize;

            if let Some(prev) = ids.last() {

                id[..share].copy_from_slice(&prev[..share]);

                if next() % 2 == 0 {

                    id[share] = (prev[share] & 0xf0) | (id[share] & 0x0f);

                }

            }

            ids.push(id);

        }

        let hex = |id: &[u8; 16]| oxy_core::ids::ChangeId(*id).to_hex();

        let whole = unique_prefixes(ids.iter().map(hex));

        let some = id_prefixes(ids.clone(), ids.iter().copied());

        for id in &ids {

            assert_eq!(some[id], whole[&hex(id)], "{}", hex(id));

        }

    }