Read a state index's file histories only when used 5552e69c7325

- **A state index read only as far as it is used (#94).** Each file's history in the workspace's state index is stored after the rest with a hash of its own, and is read and checked only when a command builds that file, so a diff or a one-file cat no longer reads and hashes the histories of every file (67 MB of an 84 MB index on VS Code at 20 000 commits). Changes added on top of an index no longer decode the histories they touch. A history found damaged is an error that says so, and the index is removed and rebuilt by the next command. Under load on that repository, `diff` went from 85 ms to 63 ms and `cat`/`blame` from 102 ms to 80 ms.

    /// A cache this repository derived and can derive again (a state

    /// index) does not match the hash it was written with.

    #[error("damaged index: {0}")]

    DamagedIndex(String),

        state

            .load_graphs(

                nodes,

                |refs| {

                    self.read_blobs(refs).map_err(|e| {

                        crate::objects::ObjectError::Schema(format!("graph and text blobs: {e}"))

                    })

                },

                |h| self.change_bytes(h),

            )

            .map_err(|e| self.index_damage(e))

    /// An error building graphs, and when it is a state index found

    /// damaged (a file's history that does not match its hash), the

    /// workspace's state indexes removed: they are rebuilt from history by

    /// the next command.

    fn index_damage(&self, e: crate::objects::ObjectError) -> RepoError {

        let crate::objects::ObjectError::DamagedIndex(why) = &e else {

            return e.into();

        };

        for path in self.state_indexes() {

            let _ = fs::remove_file(path);

        }

        RepoError::Msg(format!(

            "this workspace's state index was damaged ({why}) and has been removed; run the command again to rebuild it"

        ))

    }

            )

            .map_err(|e| self.index_damage(e))?

        state

            .load_all_graphs(

                |refs| {

                    self.read_blobs(refs).map_err(|e| {

                        crate::objects::ObjectError::Schema(format!("graph and text blobs: {e}"))

                    })

                },

                |h| self.change_bytes(h),

            )

            .map_err(|e| self.index_damage(e))

                // Re-encoding reads every history: one found damaged is

                // left to the build that reads it, which reports it.

                if let Some(mine) = st.write_index() {

                    assert_eq!(

                        Some(mine),

                        self.load_state_history(deps)?.write_index(),

                        "a state index holds the state history gives"

                    );

                }

        use std::io::Read;

        let reading = crate::timing::phase("load:   of which reading the file");

        let mut f = match fs::File::open(&exact) {

            Ok(f) => {

                f

            Err(_) => fs::File::open(self.state_indexes().first()?).ok()?,

        let total = f.metadata().ok()?.len();

        let mut word = [0u8; 4];

        f.read_exact(&mut word).ok()?;

        let n = u32::from_le_bytes(word) as usize;

        let mut head = vec![0u8; 32 * n + 64 + 8];

        f.read_exact(&mut head).ok()?;

        let heads: Vec<ChangeHash> = head[..32 * n]

            .chunks_exact(32)

            .map(|c| ObjectRef(c.try_into().unwrap()))

            .collect();

        let (changes_sum, rest_sum) = (&head[32 * n..32 * n + 32], &head[32 * n + 32..32 * n + 64]);

        let front_len = u64::from_le_bytes(head[32 * n + 64..].try_into().unwrap());

        let at = (4 + head.len()) as u64;

        if at.checked_add(front_len).is_none_or(|end| end > total) {

            return None;

        // The front only: the files' histories after it are read, each

        // checked by its own hash, when a command builds that file.

        let mut front = vec![0u8; front_len as usize];

        f.read_exact(&mut front).ok()?;

        drop(reading);

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

        let split = 4 + u32::from_le_bytes(front.get(..4)?.try_into().unwrap()) as usize;

        let (changes, rest) = (front.get(..split)?, front.get(split..)?);

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

        drop(checking);

        let histories = crate::state::Histories::File(

            std::sync::Arc::new(f),

            at + front_len,

            total - at - front_len,

        );

        Some((State::read_index_front(&front, histories).ok()?, heads))

        // Heads, the two sums, the front's length, then the changes block.

        let mut head = vec![0u8; 32 * n + 64 + 8 + 4];

        let len = u32::from_le_bytes(head[32 * n + 72..].try_into().unwrap()) as usize;

        changes[..4].copy_from_slice(&head[32 * n + 72..]);

        // The body is the front's length, the front, then the files'

        // histories, which carry their own hashes: the sums cover the

        // front's changes block and the rest of the front.

        let front_len = u64::from_le_bytes(body[..8].try_into().unwrap()) as usize;

        let front = &body[8..8 + front_len];

        let split = 4 + u32::from_le_bytes(front[..4].try_into().unwrap()) as usize;

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

        w.fixed(&sum(&front[..split]));

        w.fixed(&sum(&front[split..]));

/// oxygen#94: a state index's file histories are read, and checked by

/// their own hashes, only when a file is built. One found damaged is an

/// error that says so, the index is removed, and the next read rebuilds it.

#[test]

fn a_damaged_file_history_in_the_state_index_is_rebuilt() {

    hermetic();

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

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

    for i in 0..6 {

        write(

            dir.path(),

            &format!("f{i}.txt"),

            format!("one {i}\n").as_bytes(),

        );

    }

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

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

    for i in 0..6 {

        write(

            dir.path(),

            &format!("f{i}.txt"),

            format!("one {i}\ntwo\n").as_bytes(),

        );

    }

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

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

    let want: Vec<Vec<u8>> = (0..6)

        .map(|i| format!("one {i}\ntwo\n").into_bytes())

        .collect();

    // The index of the working copy's base, holding every file's history

    // (a few changes behind, an index is replayed onto, not rewritten).

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

    let base = repo.load_state_history(&wc.deps).unwrap();

    repo.write_state_index(&wc.deps, &base);

    for (i, w) in want.iter().enumerate() {

        assert_eq!(&repo.file_at(&format!("f{i}.txt"), None).unwrap(), w);

    }

    let index = repo.state_indexes();

    assert!(!index.is_empty(), "a state index was written");

    // The histories are last in the file: damage the last of them.

    let mut bytes = fs::read(&index[0]).unwrap();

    let last = bytes.len() - 1;

    bytes[last] ^= 0x40;

    fs::write(&index[0], &bytes).unwrap();

    let reads: Vec<_> = (0..6)

        .map(|i| repo.file_at(&format!("f{i}.txt"), None))

        .collect();

    let damaged: Vec<String> = reads

        .iter()

        .filter_map(|r| r.as_ref().err().map(|e| e.to_string()))

        .collect();

    assert_eq!(damaged.len(), 1, "{damaged:?}");

    assert!(

        damaged[0].contains("state index was damaged")

            && damaged[0].contains("run the command again"),

        "{}",

        damaged[0]

    );

    // Every file reads right again, from an index rebuilt from history.

    for (i, w) in want.iter().enumerate() {

        assert_eq!(&repo.file_at(&format!("f{i}.txt"), None).unwrap(), w);

    }

}

/// Read from a state index, it stays in the index, unread, until first

/// used: a command that builds a few files reads and checks only their

/// histories (oxygen#94).

    /// The history: `raw` read and decoded, with `more` after it. An

    /// error when `raw` does not match its hash.

    body: std::sync::OnceLock<Result<DeferredBody, String>>,

    /// The history as an index holds it, not read yet.

    raw: Option<RawHistory>,

    /// Changes added since the index was read, kept beside `raw`, so that

    /// adding one neither reads nor decodes the history.

    more: Vec<(ChangeHash, Vec<Edit>)>,

    more_texts: Vec<TextRef>,

/// Where a state index's file histories are: the index file itself, read

/// on first use, or bytes in memory.

#[derive(Clone)]

pub enum Histories {

    Bytes(Arc<Vec<u8>>),

    /// The file, where its histories start, and how many bytes they take.

    File(Arc<std::fs::File>, u64, u64),

}

impl Histories {

    fn len(&self) -> u64 {

        match self {

            Histories::Bytes(b) => b.len() as u64,

            Histories::File(_, _, len) => *len,

        }

    }

    fn read(&self, at: u64, len: usize) -> std::io::Result<Vec<u8>> {

        match self {

            Histories::Bytes(b) => Ok(b[at as usize..at as usize + len].to_vec()),

            Histories::File(f, start, _) => {

                let mut buf = vec![0u8; len];

                read_exact_at(f, &mut buf, start + at)?;

                Ok(buf)

            }

        }

    }

}

#[cfg(unix)]

fn read_exact_at(f: &std::fs::File, buf: &mut [u8], at: u64) -> std::io::Result<()> {

    std::os::unix::fs::FileExt::read_exact_at(f, buf, at)

}

#[cfg(windows)]

fn read_exact_at(f: &std::fs::File, mut buf: &mut [u8], mut at: u64) -> std::io::Result<()> {

    while !buf.is_empty() {

        match std::os::windows::fs::FileExt::seek_read(f, buf, at)? {

            0 => return Err(std::io::ErrorKind::UnexpectedEof.into()),

            n => {

                buf = &mut buf[n..];

                at += n as u64;

            }

        }

    }

    Ok(())

}

/// One file's history in a state index: where it is and its hash.

#[derive(Clone)]

struct RawHistory {

    from: Histories,

    at: u64,

    len: usize,

    sum: [u8; 32],

}

impl RawHistory {

    /// The history's bytes, checked against the hash the index holds.

    fn bytes(&self) -> Result<Vec<u8>, ObjectError> {

        let damaged = |why: String| ObjectError::DamagedIndex(why);

        let b = self

            .from

            .read(self.at, self.len)

            .map_err(|e| damaged(format!("a file's history cannot be read: {e}")))?;

        if *blake3::hash(&b).as_bytes() != self.sum {

            return Err(damaged("a file's history does not match its hash".into()));

        }

        Ok(b)

    }

}

            body: std::sync::OnceLock::from(Ok(body)),

    }

    /// The history, read and checked on first use.

    fn body(&self) -> Result<&DeferredBody, ObjectError> {

        self.body

            .get_or_init(|| {

                let mut b = match &self.raw {

                    // Matching its hash, it is what `write_index` wrote: it

                    // decodes.

                    Some(raw) => raw

                        .bytes()

                        .and_then(|b| State::read_deferred_body(&b))

                        .map_err(|e| e.to_string())?,

                    None => DeferredBody::default(),

                };

                b.edits.extend(self.more.iter().cloned());

                b.texts.extend(self.more_texts.iter().cloned());

                Ok(b)

            })

            .as_ref()

            .map_err(|e| ObjectError::DamagedIndex(e.clone()))

    /// Add a change's edits to the history: beside the index's encoding

    /// while it is unread, so that nothing is read or decoded to add them.

    fn add(&mut self, h: ChangeHash, edits: Vec<Edit>, texts: Vec<TextRef>) {

        if self.raw.is_some() && !matches!(self.body.get(), Some(Ok(_))) {

            self.more.push((h, edits));

            self.more_texts.extend(texts);

            // A body found damaged stays so: what was added cannot mend it.

            return;

        }

        // No encoding to read, or decoded already: this cannot fail.

        let b = self.body_mut().expect("a history in memory");

        b.edits.push((h, edits));

        b.texts.extend(texts);

    fn body_mut(&mut self) -> Result<&mut DeferredBody, ObjectError> {

        self.body()?;

        self.more.clear();

        self.more_texts.clear();

        Ok(self

            .body

            .get_mut()

            .and_then(|b| b.as_mut().ok())

            .expect("decoded above"))

    fn into_body(mut self) -> Result<DeferredBody, ObjectError> {

        self.body()?;

        Ok(self

            .body

            .take()

            .and_then(|b| b.ok())

            .expect("decoded above"))

    const INDEX_MAGIC: &'static [u8] = b"oxy state index 4\n";

        let mut front = w;

        // The table: per file its key and where its history is, with the

        // history's hash, which is checked when it is read (oxygen#94).

        let mut table = Writer::default();

        let mut histories: Vec<u8> = Vec::new();

        table.count(nodes.len());

            let key = match d.key.get() {

                Some(k) => *k,

                None => {

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

                    h.update(b"oxy graph key 1\0");

                    h.update(&n.0);

                    let k = d.graph_key(h).ok()?;

                    let _ = d.key.set(k);

                    k

            };

            // Unchanged since read: its bytes as they are, checked.

            let bytes = match &d.raw {

                Some(raw) if d.more.is_empty() => raw.bytes().ok()?,

                _ => Self::write_deferred_body(d.body().ok()?)?,

            };

            table.fixed(&n.0);

            table.fixed(&key);

            table.u64(histories.len() as u64);

            table.u32(u32::try_from(bytes.len()).ok()?);

            table.fixed(blake3::hash(&bytes).as_bytes());

            histories.extend_from_slice(&bytes);

        }

        front.bytes(&table.0);

        let mut out = Writer::default();

        out.u64(front.0.len() as u64);

        out.fixed(&front.0);

        out.fixed(&histories);

        Some(out.0)

    }

    /// One file's history as an index encodes it; `None` when it holds

    /// text in memory, which an index does not.

    fn write_deferred_body(d: &DeferredBody) -> Option<Vec<u8>> {

        use crate::flat::Writer;

        let atom = |w: &mut Writer, a: &AtomRef| match a {

            AtomRef::Start => w.u8(0),

            AtomRef::End => w.u8(1),

            AtomRef::Atom { change, index } => {

                w.u8(2);

                w.object(change);

                w.u32(*index);

        };

        let mut w = Writer::default();

        match &d.base {

            None => w.u8(0),

            Some(DeferredBase::Blob(r)) => {

                w.u8(1);

                w.object(r);

            Some(DeferredBase::Inline(v)) => {

                w.u8(2);

                w.bytes(&cbor::encode(v));

        }

        // Each change's edits with the texts of its inserts, sorted by

        // change: a graph does not depend on the order changes applied

        // in, and the index is then the same however history was read.

        let mut texts = d.texts.iter();

        let mut per_change: Vec<(&ChangeHash, &Vec<Edit>, Vec<&TextRef>)> = Vec::new();

        for (c, edits) in &d.edits {

            let n = edits

                .filter(|e| matches!(e, Edit::Insert { lines, .. } if lines.is_empty()))

                .count();

            per_change.push((c, edits, texts.by_ref().take(n).collect()));

        }

        per_change.sort_by_key(|(c, _, _)| **c);

        w.count(per_change.len());

        for (c, edits, _) in &per_change {

            w.object(c);

            w.count(edits.len());

            for e in edits.iter() {

                match e {

                    Edit::Insert {

                        node,

                        after,

                        before,

                        lines,

                    } => {

                        if !lines.is_empty() {

                            return None;

                        }

                        w.fixed(&node.0);

                        atom(&mut w, after);

                        atom(&mut w, before);

                    Edit::Delete { node, atoms } => {

                        w.fixed(&node.0);

                        w.count(atoms.len());

                        for r in atoms {

                            w.object(&r.change);

                            w.u32(r.from);

                            w.u32(r.to);

                        }

                    Edit::Replace { .. } => return None,

        let texts: Vec<&TextRef> = per_change

            .iter()

            .flat_map(|(_, _, t)| t.iter().copied())

            .collect();

        w.count(texts.len());

        for t in texts {

            match t {

                TextRef::Blob(r, count, form) => {

                    w.u8(0);

                    w.object(r);

                    w.u32(*count);

                    w.u8(match form {

                        crate::objects::TextForm::Cbor => 0,

                        crate::objects::TextForm::Raw => 1,

                        crate::objects::TextForm::CborFallback => 2,

                    });

                }

                TextRef::Inline { change, start, end } => {

                    w.u8(1);

                    w.object(change);

                    w.u32(*start);

                    w.u32(*end);

                }

            }

        }

        Some(w.0)

        let bad = || ObjectError::Schema("state index: truncated".into());

        let front_len =

            usize::try_from(crate::flat::Reader::new(bytes).u64()?).map_err(|_| bad())?;

        let front = bytes.get(8..8 + front_len).ok_or_else(bad)?;

        let histories = Histories::Bytes(Arc::new(bytes[8 + front_len..].to_vec()));

        Self::read_index_front(front, histories)

    /// An index's front, everything but the files' histories, with where

    /// those are: each is read, and checked against the hash the front

    /// holds, only when its graph is built (oxygen#94).

    pub fn read_index_front(bytes: &[u8], histories: Histories) -> Result<State, ObjectError> {

            || Self::read_deferred(deferred_bytes, &histories),

        table: &[u8],

        histories: &Histories,

        let mut r = Reader::new(table);

            // The length is of bytes in the histories, not in this table:

            // checked against the histories' size below.

            let (at, len, sum) = (r.u64()?, r.u32()? as usize, r.fixed::<32>()?);

            if at

                .checked_add(len as u64)

                .is_none_or(|end| end > histories.len())

            {

                return Err(ObjectError::Schema(

                    "state index: a file's history lies outside it".into(),

                ));

            }

                raw: Some(RawHistory {

                    from: histories.clone(),

                    at,

                    len,

                    sum,

                }),

    let mut taken: Vec<(NodeId, DeferredBody)> = taken

        .into_iter()

        .map(|(n, d)| Ok((n, d.into_body()?)))

        .collect::<Result<_, ObjectError>>()?;

        // A history that cannot be read is no single text: building its

        // graph reports why.

        let d = self.deferred.as_ref()?.get(node)?.body().ok()?;

        // A history that cannot be read has no key: the file is read.

        if let Some(k) = d.key.get() {

            return Some(*k);

        }

        let k = d.graph_key(h).ok()?;

        Some(*d.key.get_or_init(|| k))

            let n: usize = v

                .body()

                .map_or(0, |b| b.edits.iter().map(|(_, e)| e.len()).sum());

    fn graph_key(&self, mut h: blake3::Hasher) -> Result<[u8; 32], ObjectError> {

        let d = self.body()?;

        Ok(*h.finalize().as_bytes())

                        d.add(h, edits, node_texts);