crates/oxy-core/src/repo/snapshot.rs at d0bf2da15094 · andymccall/oxygen

# d0bf2da15094 oxygen / crates / oxy-core / src / repo / snapshot.rs
113.8 KiB · Rust · last changed Edited files are diffed in parallel (refs #41) 1 month ago source blame history raw
//! Working-copy snapshots, commits, and the change builder (spec §12.3).

use super::*;
use crate::objects::AtomRef;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ChangeStatus {
    Added,
    Modified,
    Removed,
    /// Moved from another path (detected by similarity, tracked as a placement change).
    Renamed,
    ModeChanged,
    /// The file is conflicted in the base state and still contains conflict markers.
    ConflictEdited,
    /// The file was conflicted in the base state and the working copy resolves it.
    Resolved,
}

/// Lines that mark a conflict region in a materialized file (spec §9.5).
pub fn has_conflict_markers(content: &[u8]) -> bool {
    split_lines(content).iter().any(|l| {
        l.starts_with(b"<<<<<<< oxy conflict")
            || l.starts_with(b"======= oxy conflict")
            || l.starts_with(b">>>>>>> oxy conflict")
    })
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PathStatus {
    pub path: String,
    pub status: ChangeStatus,
}

/// Operations of a change built from the working directory against a base.
pub(crate) struct BuiltChange {
    pub tree_ops: Vec<TreeOp>,
    pub edits: Vec<Edit>,
    pub contributors: Vec<ChangeHash>,
    pub resolves: bool,
    pub statuses: Vec<PathStatus>,
    /// The stored blob of every opaque path, for the manifest's stat cache.
    pub blobs: HashMap<String, ObjectRef>,
}

/// Result of snapshotting the working copy.
pub struct SnapshotResult {
    pub wc_hash: ChangeHash,
    pub wc: Change,
    /// The base state (closure of the working-copy change's dependencies).
    pub base: State,
    pub base_snapshot: Snapshot,
    pub statuses: Vec<PathStatus>,
    /// Whether the snapshot rewrote the working-copy change.
    pub changed: bool,
    /// Whether the working copy resolves conflicts of its base (spec §9.6).
    pub resolves: bool,
    /// Changes that contributed to the conflicts being resolved.
    pub contributors: Vec<ChangeHash>,
    /// The `.oxyattributes` in force on disk, from the files the walk read.
    pub(crate) attributes: crate::attributes::Attributes,
    /// Folders holding a repository of their own (`.git` or `.oxy`) that
    /// are not subrepos, so nothing in them is tracked (oxygen#43).
    pub untracked_nested: Vec<String>,
    /// A commit's snapshot leaves the manifest to the commit, which writes
    /// it once with the new base's graph keys.
    pub(crate) manifest: Option<PendingManifest>,
}

/// The manifest a commit's snapshot would have written, as of the moment
/// it would have written it (that moment is the racy-window stamp).
pub(crate) struct PendingManifest {
    entries: BTreeMap<String, FsEntry>,
    blobs: HashMap<String, ObjectRef>,
    dirs: Option<super::WalkedDirs>,
    written: u128,
}

pub fn is_binary(content: &[u8]) -> bool {
    content[..content.len().min(BINARY_SNIFF)].contains(&0)
}

impl Repo {
    /// Diff the files on disk against `base` and build the operations of a
    /// change from `base` to the working directory. `reuse` maps paths to the
    /// NodeIds an earlier version of the same change assigned to new paths.
    pub(crate) fn build_against(
        &self,
        base: &State,
        base_snapshot: &Snapshot,
        reuse: HashMap<String, (NodeId, NodeKind)>,
    ) -> Result<BuiltChange> {
        let mut fs_entries =
            self.walk_working_copy_with(None, &Self::tracked_kinds(base_snapshot), None)?;
        self.platform_normalize(&mut fs_entries, base_snapshot);
        self.build_from_entries(base, base_snapshot, reuse, &fs_entries)
    }

    /// Read the working copy as the platform left it (spec §7.7): without
    /// executable bits a file keeps the bit it has in the base, and without
    /// symbolic links a plain file where the base has a symlink is that
    /// symlink, written out as its target, not a new file.
    fn platform_normalize(&self, entries: &mut BTreeMap<String, FsEntry>, base: &Snapshot) {
        let p = self.platform;
        if p.exec_bits && p.symlinks {
            return;
        }
        for (path, e) in entries.iter_mut() {
            let Some(f) = base.files.get(path) else {
                continue;
            };
            if !p.symlinks && f.kind == NodeKind::Symlink && e.kind == NodeKind::File {
                e.kind = NodeKind::Symlink;
                e.exec = false;
            }
            if !p.exec_bits && f.kind == NodeKind::File && e.kind == NodeKind::File {
                e.exec = f.mode.exec;
            }
        }
    }

    /// Like `build_against`, for files given in memory (imports).
    pub(crate) fn build_from_entries(
        &self,
        base: &State,
        base_snapshot: &Snapshot,
        reuse: HashMap<String, (NodeId, NodeKind)>,
        fs_entries: &BTreeMap<String, FsEntry>,
    ) -> Result<BuiltChange> {
        self.build_from_entries_resolving(base, base_snapshot, reuse, fs_entries, &HashSet::new())
    }

    /// Like `build_from_entries`, settling the replace conflicts of the
    /// opaque files in `resolve` to their content (spec §9.3, §9.6): a
    /// caller that knows the user chose it, such as the hub's resolver. A
    /// snapshot never settles one on its own, since a checkout writes one
    /// candidate at the path.
    pub(crate) fn build_from_entries_resolving(
        &self,
        base: &State,
        base_snapshot: &Snapshot,
        reuse: HashMap<String, (NodeId, NodeKind)>,
        fs_entries: &BTreeMap<String, FsEntry>,
        resolve: &HashSet<String>,
    ) -> Result<BuiltChange> {
        self.build_from_entries_with(
            base,
            base_snapshot,
            reuse,
            fs_entries,
            resolve,
            Scope::default(),
        )
    }

    /// `build_from_entries` whose new nodes take identifiers derived from
    /// `seed` and their paths instead of random ones, so the same input
    /// always builds the same change (a Git import, spec §23).
    ///
    /// With `dir_needed`, the snapshot and entries hold only the paths the
    /// import touches (and the directories a removal may leave empty); a
    /// directory stays while `dir_needed` says the new tree has something
    /// under it.
    pub(crate) fn build_from_entries_seeded(
        &self,
        base: &State,
        base_snapshot: &Snapshot,
        fs_entries: &BTreeMap<String, FsEntry>,
        seed: [u8; 32],
        dir_needed: Option<&dyn Fn(&str) -> bool>,
    ) -> Result<BuiltChange> {
        self.build_from_entries_with(
            base,
            base_snapshot,
            HashMap::new(),
            fs_entries,
            &HashSet::new(),
            Scope {
                seed: Some(seed),
                dir_needed,
            },
        )
    }

    /// `build_from_entries` for a snapshot most of whose files are known
    /// unchanged (oxygen#41): only the paths that may differ are built
    /// (files read rather than known unchanged, base files gone from disk,
    /// and the directories those may leave empty), against a snapshot of
    /// just those, so a large tree with a few edits costs what they touch.
    fn build_changed_only(
        &self,
        base: &State,
        base_snapshot: &Snapshot,
        reuse: HashMap<String, (NodeId, NodeKind)>,
        fs_entries: &BTreeMap<String, FsEntry>,
    ) -> Result<BuiltChange> {
        let pick = crate::timing::phase("snapshot:   of which picking the changed");
        // A file known unchanged may still have changed mode: that alters
        // neither its size nor its time.
        let changed: BTreeMap<String, FsEntry> = join(fs_entries, &base_snapshot.files)
            .filter_map(|(p, e, f)| {
                let e = e?;
                (!e.unchanged || f.is_none_or(|f| f.kind != e.kind || f.mode.exec != e.exec))
                    .then(|| (p.clone(), e.clone()))
            })
            .collect();
        let mut files: BTreeMap<String, crate::state::FileState> = BTreeMap::new();
        for p in changed.keys() {
            if let Some(f) = base_snapshot.files.get(p) {
                files.insert(p.clone(), f.clone());
            }
        }
        // Paths the base has and the disk does not.
        let gone = join(&base_snapshot.files, fs_entries)
            .filter_map(|(p, f, e)| (e.is_none()).then_some((p, f?)));
        for (p, f) in gone {
            if f.kind == NodeKind::Dir {
                continue;
            }
            files.insert(p.clone(), f.clone());
            let mut end = p.len();
            while let Some(i) = p[..end].rfind('/') {
                let dir = &p[..i];
                if files.contains_key(dir) {
                    break;
                }
                if let Some(d) = base_snapshot.files.get(dir) {
                    files.insert(dir.to_string(), d.clone());
                }
                end = i;
            }
        }
        let part = Snapshot {
            tree: base_snapshot.tree.clone(),
            files,
            unrendered: BTreeSet::new(),
        };
        drop(pick);
        let _build = crate::timing::phase("snapshot:   of which building the change");
        // Whether anything on disk is under `dir`.
        let dir_needed = |dir: &str| {
            let prefix = format!("{dir}/");
            fs_entries
                .range(prefix.clone()..)
                .next()
                .is_some_and(|(k, _)| k.starts_with(&prefix))
        };
        self.build_from_entries_with(
            base,
            &part,
            reuse,
            &changed,
            &HashSet::new(),
            Scope {
                seed: None,
                dir_needed: Some(&dir_needed),
            },
        )
    }

    fn build_from_entries_with(
        &self,
        base: &State,
        base_snapshot: &Snapshot,
        reuse: HashMap<String, (NodeId, NodeKind)>,
        fs_entries: &BTreeMap<String, FsEntry>,
        resolve: &HashSet<String>,
        scope: Scope,
    ) -> Result<BuiltChange> {
        let Scope { seed, dir_needed } = scope;
        let mut laps = crate::timing::Laps::start();
        // Attributes come from the files being committed, so a new
        // `.oxyattributes` applies to the same change that adds it.
        let attrs = crate::attributes::Attributes::from_files(
            fs_entries
                .iter()
                .filter(|(p, _)| p.as_str() == ".oxyattributes" || p.ends_with("/.oxyattributes"))
                .map(|(p, e)| (p.as_str(), e.content.as_slice())),
        );
        let mut b = ChangeBuilder::new(base, base_snapshot, reuse).with_attributes(attrs);
        b.resolve = resolve.clone();
        b.node_seed = seed;
        laps.lap("build: builder");
        // Rename detection (spec §7.1, §23): a removed file and an added file
        // of the same kind whose contents are at least half alike become one
        // move of the same node, so identity survives across the rename.
        let renames = detect_renames(base_snapshot, fs_entries, |p| self.in_scope(p));
        let renamed_from: HashMap<&str, &str> = renames
            .iter()
            .map(|(old, new)| (new.as_str(), old.as_str()))
            .collect();
        let renamed_to: HashMap<&str, &str> = renames
            .iter()
            .map(|(old, new)| (old.as_str(), new.as_str()))
            .collect();
        laps.lap("build: renames");
        b.diff_in_parallel(fs_entries);
        laps.lap("build: diffs");
        for (path, fs_entry) in fs_entries {
            match base_snapshot.files.get(path) {
                None => match renamed_from.get(path.as_str()) {
                    Some(old) => {
                        b.move_path(self, old, path, fs_entry, &base_snapshot.files[*old])?
                    }
                    None => b.add_path(self, path, fs_entry)?,
                },
                Some(expected) => b.update_path(self, path, fs_entry, expected)?,
            }
        }
        laps.lap("build: paths");
        // A directory stays while anything under it exists or is out of
        // scope: the directories above each such path, gathered once.
        let mut needed_dirs: HashSet<&str> = HashSet::new();
        fn parents_of<'a>(p: &'a str, set: &mut HashSet<&'a str>) {
            let mut end = p.len();
            while let Some(i) = p[..end].rfind('/') {
                if !set.insert(&p[..i]) {
                    break;
                }
                end = i;
            }
        }
        for p in fs_entries.keys() {
            parents_of(p, &mut needed_dirs);
        }
        for p in base_snapshot.files.keys() {
            if !self.in_scope(p) {
                parents_of(p, &mut needed_dirs);
            }
        }
        for (path, expected) in &base_snapshot.files {
            if fs_entries.contains_key(path)
                || !self.in_scope(path)
                || renamed_to.contains_key(path.as_str())
            {
                continue;
            }
            let still_needed = expected.kind == NodeKind::Dir
                && match dir_needed {
                    Some(f) => f(path),
                    None => needed_dirs.contains(path.as_str()),
                };
            if !still_needed {
                b.remove_path(path, expected);
            }
        }
        laps.lap("build: removals");
        if seed.is_some() {
            b.retire_stray_placements();
        }
        laps.lap("build: stray placements");
        let mut statuses = b.statuses;
        statuses.sort_by(|a, b| a.path.cmp(&b.path));
        Ok(BuiltChange {
            tree_ops: b.tree_ops,
            edits: b.edits,
            contributors: b.contributors.into_iter().collect(),
            resolves: b.resolves,
            statuses,
            blobs: b.blobs,
        })
    }

    /// Store a change and, when `core.sign = change` and we are its author,
    /// sign it. A rewritten change by another author is stored unsigned: only
    /// its author (or a delegate) can vouch for it.
    pub(crate) fn store_signed(&self, change: &Change) -> Result<ChangeHash> {
        let ours = change.author == self.author();
        if self.config.sign_changes && ours && self.secret_key()?.is_none() {
            return fail("core.sign is \"change\" but no secret key is available for author.key");
        }
        let hash = self.store.put_change(change)?;
        if self.config.sign_changes && ours {
            self.sign_change(&hash)?;
        }
        Ok(hash)
    }

    /// Snapshot the working copy into the working-copy change (spec §12.3).
    /// The result carries the full base state and its whole rendering.
    pub fn snapshot(&self, command: &str) -> Result<SnapshotResult> {
        self.snapshot_as(command, false, false)
    }

    /// Snapshot the working copy as [`Repo::snapshot`] does, for commands
    /// that need its statuses, conflicts and base history, and the graphs
    /// of the files it changes: status, log, show, commit, diff, hunks and
    /// discard. Text files known unchanged since the last manifest are
    /// neither read nor rendered: the result's `base` is a history-only
    /// state without their graphs, and its `base_snapshot` lists them in
    /// `unrendered` with empty bytes. They are never conflicted, and no
    /// change the working copy makes touches them.
    pub fn snapshot_status(&self, command: &str) -> Result<SnapshotResult> {
        self.snapshot_as(command, true, false)
    }

    /// `snapshot_as`; `for_commit` writes the manifest even where a status
    /// would not bother (an edited file is read next time whatever it
    /// says), since after the commit that file is unchanged, and records no
    /// operation: the commit's own, recorded straight after, replaces the
    /// working copy, so the snapshot's would cost a durable write for
    /// nothing. Should the commit fail, the files are still on disk and the
    /// next snapshot finds them.
    fn snapshot_as(
        &self,
        command: &str,
        partial: bool,
        for_commit: bool,
    ) -> Result<SnapshotResult> {
        let _lock = self.lock_snapshot()?;
        let batch = self.store.begin_batch()?;
        let result = self.snapshot_locked(command, partial, for_commit);
        batch.finish()?;
        result
    }

    fn snapshot_locked(
        &self,
        command: &str,
        partial: bool,
        for_commit: bool,
    ) -> Result<SnapshotResult> {
        let _all = crate::timing::phase("snapshot");
        let (op_ref, op) = self.head_op()?;
        let (old_hash, old_wc) = self.working_copy()?;
        // The base's history first: its graph keys say which files the
        // manifest already knows equal to it.
        let mut base = {
            let _t = crate::timing::phase("snapshot: load base history");
            self.load_state_indexed(&old_wc.deps)?
        };
        let view = {
            let _t = crate::timing::phase("snapshot: tree view");
            base.tree().view()
        };
        let manifest = {
            let _t = crate::timing::phase("snapshot: read manifest");
            self.read_manifest()?.map(|(_, _, m)| m)
        };
        let tracked: BTreeMap<String, (NodeKind, Option<ObjectRef>)> = {
            let _t = crate::timing::phase("snapshot: tracked paths");
            // In the view's path order, so the map is built without searching.
            view.entries
                .iter()
                .filter(|(_, e)| e.kind != NodeKind::Dir)
                .map(|(p, e)| {
                    let blob = if e.kind != NodeKind::File || e.mode.opaque {
                        base.live_blobs(&e.node).first().copied()
                    } else {
                        None
                    };
                    (p.clone(), (e.kind, blob))
                })
                .collect()
        };
        // A text file's graph key, worked out when the walk asks for it.
        let key_of = |p: &str| -> Option<[u8; 32]> {
            let e = view.entries.get(p)?;
            if e.kind != NodeKind::File || e.mode.opaque {
                return None;
            }
            base.graph_key(&e.node)
        };
        let mut fs_entries = {
            let _t = crate::timing::phase("snapshot: read working copy");
            self.walk_working_copy_with(manifest.as_deref(), &tracked, Some(&key_of))?
        };
        // The keys of the files read, before building graphs drops them: a
        // file found equal to its base rendering keeps its key.
        let keys: HashMap<String, [u8; 32]> = fs_entries
            .iter()
            .filter(|(_, e)| !e.unchanged && e.kind == NodeKind::File)
            .filter_map(|(p, _)| Some((p.clone(), key_of(p)?)))
            .collect();
        let base_snapshot = {
            let _t = crate::timing::phase("snapshot: load and render base");
            if partial {
                let sets = crate::timing::phase("snapshot:   of which choosing graphs");
                // Every file but those on disk known unchanged.
                let need: Vec<(&str, NodeId)> = join(&view.entries, &fs_entries)
                    .filter_map(|(p, v, f)| {
                        let v = v?;
                        (v.kind == NodeKind::File && !f.is_some_and(|f| f.unchanged))
                            .then_some((p.as_str(), v.node))
                    })
                    .collect();
                let render: std::collections::HashSet<&str> =
                    need.iter().map(|(p, _)| *p).collect();
                let need: Vec<NodeId> = need.iter().map(|(_, n)| *n).collect();
                drop(sets);
                {
                    let _t = crate::timing::phase("snapshot:   of which building graphs");
                    self.load_graphs_of(&mut base, &need)?;
                }
                let _t = crate::timing::phase("snapshot:   of which rendering");
                base.materialize_only(&render)
            } else {
                self.load_all_graphs(&mut base)?;
                base.materialize()
            }
        };

        // Reuse the NodeIds the previous working-copy version assigned to new
        // paths, so an unchanged working copy hashes identically (spec §12.3).
        let reuse = added_node_paths(&old_wc, &base_snapshot);
        self.platform_normalize(&mut fs_entries, &base_snapshot);
        let built = {
            let _t = crate::timing::phase("snapshot: diff against base");
            if partial && self.config.sparse_paths.is_empty() {
                #[cfg(test)]
                let full =
                    self.build_from_entries(&base, &base_snapshot, reuse.clone(), &fs_entries)?;
                let built = self.build_changed_only(&base, &base_snapshot, reuse, &fs_entries)?;
                #[cfg(test)]
                {
                    // New nodes take random identifiers: compare them by
                    // order of appearance.
                    let norm = |b: &BuiltChange| {
                        let text = format!("{:?} {:?} {:?}", b.tree_ops, b.edits, b.statuses);
                        let mut seen: Vec<String> = Vec::new();
                        let mut out = String::new();
                        let mut rest = text.as_str();
                        while let Some(i) = rest.find("NodeId(") {
                            out.push_str(&rest[..i]);
                            let end = i + rest[i..].find(')').unwrap() + 1;
                            let id = rest[i..end].to_string();
                            let n = seen.iter().position(|x| *x == id).unwrap_or_else(|| {
                                seen.push(id);
                                seen.len() - 1
                            });
                            out.push_str(&format!("N{n}"));
                            rest = &rest[end..];
                        }
                        out.push_str(rest);
                        out
                    };
                    assert_eq!(
                        norm(&built),
                        norm(&full),
                        "a changed-only build is the full one"
                    );
                }
                built
            } else {
                self.build_from_entries(&base, &base_snapshot, reuse, &fs_entries)?
            }
        };
        // Text files found equal to an unconflicted base rendering keep its
        // graph key, so the next snapshot need not read or render them.
        {
            let changed: HashSet<&str> = built.statuses.iter().map(|s| s.path.as_str()).collect();
            for (p, e) in fs_entries.iter_mut() {
                if e.unchanged || e.kind != NodeKind::File || changed.contains(p.as_str()) {
                    continue;
                }
                e.graph_key = match base_snapshot.files.get(p).map(|f| &f.content) {
                    Some(FileContent::Text {
                        bytes,
                        materialized,
                    }) if !materialized.is_conflicted() && *bytes == *e.content => {
                        keys.get(p).copied()
                    }
                    _ => None,
                };
            }
        }

        let mut wc = Change {
            version: crate::objects::CHANGE_VERSION,
            change_id: old_wc.change_id,
            deps: vec![],
            author: self.author(),
            hlc: old_wc.hlc,
            message: old_wc.message.clone(),
            tree_ops: built.tree_ops,
            edits: built.edits,
            kind: ChangeKind::WorkingCopy,
        };
        let base_heads = base.maximal(&old_wc.deps);
        let mut deps: BTreeSet<ChangeHash> = base_heads.into_iter().collect();
        deps.extend(referenced_changes(&wc, &base));
        deps.extend(built.contributors.iter().copied());
        wc.deps = deps.into_iter().collect();
        wc.normalize();
        let resolves = built.resolves;
        let contributors = built.contributors;
        let statuses = built.statuses;
        // Empty snapshot: hash the candidate before storing; only record an op on change.
        let record = crate::timing::phase("snapshot: hash and record");
        // Encoded once, its texts stored a batch at a time as they are
        // made (a stored blob is not stored again); the change itself only
        // when it changed.
        let encoded = wc.encode_streaming(|batch| self.store.put_texts(&batch))?;
        let new_hash = crate::hash::hash_object(crate::hash::ObjectType::Change, &encoded);
        let changed = new_hash != old_hash;
        // For a commit the change is neither stored nor recorded: the commit
        // stores its own, built from this one's operations.
        if changed && !for_commit {
            self.store.put(crate::hash::ObjectType::Change, &encoded)?;
            let mut view = op.view.clone();
            view.workspaces.insert(self.workspace, new_hash);
            self.record_op(&[op_ref], &format!("{command}{SNAPSHOT_SUFFIX}"), view)?;
        }
        drop(record);
        // The prompt compares against this without recording anything.
        let _t = crate::timing::phase("snapshot: write manifest");
        let conflicted = base_snapshot.is_conflicted();
        let uncommitted = !wc.tree_ops.is_empty() || !wc.edits.is_empty();
        // Rewriting the manifest pays only when it would teach the next
        // snapshot something: other flags, a file found equal to the base
        // (it need not be read again), a new blob, a path added or gone.
        // An edited file is read next time whatever it says.
        let worth = match self.read_manifest()? {
            _ if for_commit => true,
            None => true,
            Some((c, u, m)) => {
                c != conflicted
                    || u != uncommitted
                    || m.entries.len() != fs_entries.len()
                    || fs_entries.iter().any(|(p, e)| {
                        !e.unchanged && (e.graph_key.is_some() || !m.entries.contains_key(p))
                    })
                    || built
                        .blobs
                        .iter()
                        .any(|(p, b)| m.entries.get(p).and_then(|e| e.blob) != Some(*b))
                    // With uncommitted work, the status cache below holds
                    // only while the manifest describes the edited files as
                    // they are now.
                    || (uncommitted && statuses.iter().any(|st| {
                        let Some(e) = fs_entries.get(&st.path) else {
                            return m.entries.contains_key(&st.path);
                        };
                        let Some(me) = m.entries.get(&st.path) else {
                            return true;
                        };
                        let hash = e
                            .content_hash
                            .unwrap_or_else(|| *blake3::hash(&e.content).as_bytes());
                        let stat = e.stat.or_else(|| {
                            fs::symlink_metadata(self.root.join(&st.path))
                                .ok()
                                .map(|md| (md.len(), super::prompt::mtime_ns(&md)))
                        });
                        // The executable bit too: a mode change moves
                        // neither size nor time.
                        me.hash != hash || me.exec != e.exec || stat != Some((me.size, me.mtime_ns))
                    }))
            }
        };
        let attributes = crate::attributes::Attributes::from_files(
            fs_entries
                .iter()
                .filter(|(p, _)| is_attributes(p))
                .map(|(p, e)| (p.as_str(), e.content.as_slice())),
        );
        let mut manifest = None;
        if for_commit {
            manifest = Some(PendingManifest {
                entries: fs_entries,
                blobs: built.blobs.clone(),
                dirs: self.walked_dirs.take(),
                written: super::prompt::now_ns(),
            });
        } else {
            if worth {
                self.write_manifest_entries(conflicted, uncommitted, &fs_entries, &built.blobs)?;
            }
            self.write_status_cache((uncommitted && !conflicted).then_some(&new_hash), &statuses);
        }
        Ok(SnapshotResult {
            wc_hash: new_hash,
            wc,
            base,
            base_snapshot,
            statuses,
            changed,
            resolves,
            contributors,
            attributes,
            untracked_nested: self.untracked_nested.borrow().clone(),
            manifest,
        })
    }

    /// `oxy status --json` (spec §9.5): the changed paths and every conflict
    /// of the working copy's base with its kind, path, and contributing
    /// ChangeIds.
    pub fn status_json(&self, snap: &SnapshotResult) -> Result<String> {
        let heads = self.bookmark_heads()?;
        let base_snapshot = &snap.base_snapshot;
        let by_node = base_snapshot.tree.by_node();
        let path_of = |n: &NodeId| by_node.get(n).map(|e| e.path.clone());
        let id_of = |h: &ChangeHash| {
            snap.base
                .get(h)
                .map(|m| m.change_id.to_hex())
                .unwrap_or_else(|| h.to_hex())
        };
        let paths = json_array(snap.statuses.iter().map(|s| {
            format!(
                "{{\"path\":{},\"status\":{}}}",
                json_str(&s.path),
                json_str(&format!("{:?}", s.status))
            )
        }));
        let mut conflicts: Vec<String> = Vec::new();
        for (p, f) in &base_snapshot.files {
            if !f.is_conflicted() {
                continue;
            }
            let (kind, changes) = match &f.content {
                FileContent::Text { .. } => {
                    ("text", snap.base.conflict_regions(&f.node).contributors)
                }
                FileContent::Opaque { blobs } => {
                    ("replace", snap.base.blob_contributors(&f.node, blobs))
                }
                FileContent::Dir => continue,
            };
            let resolved = match snap
                .statuses
                .iter()
                .find(|s| s.path == *p)
                .map(|s| s.status)
            {
                Some(ChangeStatus::Resolved) => "true",
                Some(ChangeStatus::ConflictEdited) => "\"markers\"",
                _ => "false",
            };
            conflicts.push(format!(
                "{{\"kind\":{},\"path\":{},\"node\":{},\"changes\":{},\"resolved\":{resolved}}}",
                json_str(kind),
                json_str(p),
                json_str(&f.node.to_hex()),
                json_array(changes.iter().map(|h| json_str(&id_of(h))))
            ));
        }
        for c in &base_snapshot.tree.conflicts {
            let (kind, nodes): (&str, Vec<NodeId>) = match c {
                crate::tree::TreeConflict::Name { nodes, .. } => ("name", nodes.clone()),
                crate::tree::TreeConflict::MultiPlacement { node, .. } => {
                    ("multi-placement", vec![*node])
                }
                crate::tree::TreeConflict::Orphan { node, .. } => ("orphan", vec![*node]),
                crate::tree::TreeConflict::Cycle { node } => ("cycle", vec![*node]),
                crate::tree::TreeConflict::Mode { node, .. } => ("mode", vec![*node]),
            };
            let detail = match c {
                crate::tree::TreeConflict::Name { name, parent, .. } => {
                    let dir = if *parent == NodeId::ROOT {
                        String::new()
                    } else {
                        path_of(parent).unwrap_or_default()
                    };
                    format!(
                        ",\"path\":{}",
                        json_str(&if dir.is_empty() {
                            name.clone()
                        } else {
                            format!("{dir}/{name}")
                        })
                    )
                }
                _ => nodes
                    .first()
                    .and_then(path_of)
                    .map(|p| format!(",\"path\":{}", json_str(&p)))
                    .unwrap_or_default(),
            };
            conflicts.push(format!(
                "{{\"kind\":{},\"nodes\":{}{detail}}}",
                json_str(kind),
                json_array(nodes.iter().map(|n| json_str(&n.to_hex())))
            ));
        }
        Ok(format!(
            "{{\"bookmark\":{},\"working_copy\":{},\"heads\":{},\"clean\":{},\"conflicted\":{},\"paths\":{paths},\"conflicts\":{},\"untracked_nested\":{}}}",
            json_str(&self.config.bookmark),
            json_str(&snap.wc.change_id.to_hex()),
            heads.len(),
            snap.statuses.is_empty(),
            base_snapshot.is_conflicted(),
            json_array(conflicts),
            json_array(snap.untracked_nested.iter().map(|p| json_str(p)))
        ))
    }

    /// Turn the working-copy change into a normal change on the bookmark (spec §12.3).
    pub fn commit(&self, message: &str, extra_deps: &[ChangeHash]) -> Result<ChangeHash> {
        self.commit_selection(message, extra_deps, &Selection::All)
    }

    /// The hunks of the working copy, for `oxy commit --interactive`: each
    /// tree operation and each edit, in the order `select_hunks` numbers them.
    pub fn hunks(&self) -> Result<(SnapshotResult, Vec<Hunk>)> {
        let snap = self.snapshot_status("oxy commit")?;
        let hunks = render_hunks(&snap.wc, &snap.base, &snap.base_snapshot);
        Ok((snap, hunks))
    }

    /// Commit part of the working copy (spec §12.3). What is not selected
    /// stays on disk as uncommitted work: the next snapshot rebuilds it
    /// against the new base, so the working copy always describes the
    /// directory.
    /// The graph key in `st` of each text file at `paths`, the paths a
    /// commit changed: only their graphs changed, so the keys the manifest
    /// holds for the others still stand (and any that does not is simply
    /// not trusted by the next snapshot, which compares keys). Files with
    /// an `eol` attribute are left out: their bytes on disk are not the
    /// rendering.
    fn committed_graph_keys(
        &self,
        st: &State,
        paths: &[String],
        attrs: &crate::attributes::Attributes,
    ) -> HashMap<String, [u8; 32]> {
        let _t = crate::timing::phase("commit: graph keys");
        let view = st.tree().view();
        paths
            .iter()
            .filter_map(|p| {
                let e = view.entries.get(p)?;
                (e.kind == NodeKind::File && !e.mode.opaque && attrs.lookup(p).eol.is_none())
                    .then_some(())?;
                Some((p.clone(), st.graph_key(&e.node)?))
            })
            .collect()
    }

    pub fn commit_selection(
        &self,
        message: &str,
        extra_deps: &[ChangeHash],
        selection: &Selection,
    ) -> Result<ChangeHash> {
        // The commit's objects are written together, made durable at once
        // before the operation that names them (spec §13.6).
        let batch = self.store.begin_batch()?;
        let out = self.commit_selection_batched(message, extra_deps, selection);
        batch.finish()?;
        out
    }

    /// Write the manifest a commit's snapshot left to the commit, with the
    /// graph keys `keys` sets.
    fn write_pending_manifest(
        &self,
        mut m: PendingManifest,
        conflicted: bool,
        keys: HashMap<String, [u8; 32]>,
    ) -> Result<()> {
        for (path, k) in keys {
            if let Some(e) = m.entries.get_mut(&path) {
                e.graph_key = Some(k);
            }
        }
        self.write_manifest_entries_as_of(
            conflicted,
            false,
            &m.entries,
            &m.blobs,
            m.written,
            m.dirs.unwrap_or_default(),
        )
    }

    fn commit_selection_batched(
        &self,
        message: &str,
        extra_deps: &[ChangeHash],
        selection: &Selection,
    ) -> Result<ChangeHash> {
        let _wc = self.lock_working_copy()?;
        let mut snap = match self.snapshot_from_cache()? {
            Some(snap) => snap,
            None => self.snapshot_as("oxy commit", true, true)?,
        };
        let pending = snap.manifest.take();
        if snap.wc.tree_ops.is_empty() && snap.wc.edits.is_empty() {
            if let Some(m) = pending {
                let conflicted = snap.base_snapshot.is_conflicted();
                self.write_pending_manifest(m, conflicted, HashMap::new())?;
            }
            return fail("nothing to commit: the working copy matches its base");
        }
        if let Some(s) = snap
            .statuses
            .iter()
            .find(|s| s.status == ChangeStatus::ConflictEdited)
        {
            return fail(format!("{} still contains conflict markers", s.path));
        }
        if message.trim().is_empty() {
            return fail("a commit message is required");
        }
        // What the whole working copy references, before a whole commit
        // takes its operations over (they are moved, not copied: for a
        // large tree they are most of the memory).
        let wc_refs = referenced_changes(&snap.wc, &snap.base);
        let changed_paths: Vec<String> = snap.statuses.iter().map(|s| s.path.clone()).collect();
        let (tree_ops, edits, partial) = match selection {
            Selection::All => (
                std::mem::take(&mut snap.wc.tree_ops),
                std::mem::take(&mut snap.wc.edits),
                false,
            ),
            Selection::Paths(paths) => {
                let (o, e) = select_paths(&snap.wc, &snap.base_snapshot, paths);
                let partial = o.len() != snap.wc.tree_ops.len() || e.len() != snap.wc.edits.len();
                (o, e, partial)
            }
            Selection::Hunks(indices) => {
                let (o, e) = select_hunks(&snap.wc, indices);
                let partial = o.len() != snap.wc.tree_ops.len() || e.len() != snap.wc.edits.len();
                (o, e, partial)
            }
        };
        if tree_ops.is_empty() && edits.is_empty() {
            return fail("nothing selected to commit");
        }
        if partial && snap.resolves {
            return fail("a conflict resolution must be committed whole");
        }
        // pre-commit hook: may veto.
        self.run_hook(
            "pre-commit",
            &format!(
                "{{\"event\":\"pre-commit\",\"message\":{},\"paths\":{}}}",
                json_str(message),
                json_array(snap.statuses.iter().map(|s| format!(
                    "{{\"path\":{},\"status\":{}}}",
                    json_str(&s.path),
                    json_str(&format!("{:?}", s.status))
                )))
            ),
        )?;
        let (op_ref, op) = self.head_op()?;
        let mut deps: BTreeSet<ChangeHash> = wc_refs;
        // semantic-deps hook: may add explicit dependencies (spec §8.1).
        if self.config.semantic_deps {
            let touched: Vec<String> = snap.statuses.iter().map(|s| s.path.clone()).collect();
            let by_node = snap.base_snapshot.tree.by_node();
            let mut candidates: Vec<(ChangeId, ChangeHash, Vec<String>)> = Vec::new();
            let mut seen: BTreeSet<ChangeHash> = BTreeSet::new();
            for h in deps.iter().chain(snap.base.maximal(&snap.wc.deps).iter()) {
                if !seen.insert(*h) {
                    continue;
                }
                let c = self.store.get_change(h)?;
                let mut paths: BTreeSet<String> = BTreeSet::new();
                for n in c
                    .tree_ops
                    .iter()
                    .map(|o| o.node())
                    .chain(c.edits.iter().map(|e| e.node()))
                {
                    if let Some(e) = by_node.get(&n) {
                        paths.insert(e.path.clone());
                    }
                }
                candidates.push((c.change_id, *h, paths.into_iter().collect()));
            }
            for d in self.semantic_deps(&snap.wc.change_id, &touched, &candidates)? {
                if snap.base.contains(&d) {
                    deps.insert(d);
                }
            }
        }
        // A resolution depends on every change that contributed to the
        // conflict (spec §8.1). Tree and opaque conflicts are resolved through
        // ordinary operations whose references already cover the contributors.
        deps.extend(snap.contributors.iter().copied());
        for d in extra_deps {
            if !snap.base.contains(d) {
                return fail(format!(
                    "--depends-on {d}: not in the working copy's base state"
                ));
            }
            deps.insert(*d);
        }
        let mut change = Change {
            version: crate::objects::CHANGE_VERSION,
            change_id: if partial {
                ChangeId::random()
            } else {
                snap.wc.change_id
            },
            deps: vec![],
            author: self.author(),
            hlc: Hlc::now(),
            message: message.trim_end().to_string(),
            tree_ops,
            edits,
            kind: if snap.resolves {
                ChangeKind::Resolution
            } else {
                ChangeKind::Normal
            },
        };
        if partial {
            // Dependencies come from what the selected part references, not
            // from the whole working copy.
            deps = referenced_changes(&change, &snap.base);
            for d in extra_deps {
                deps.insert(*d);
            }
        }
        change.deps = deps.into_iter().collect();
        change.normalize();
        let signing = crate::timing::phase("commit: sign and store");
        let hash = self.store_signed(&change)?;
        drop(signing);
        let extending = crate::timing::phase("commit: extend the state");

        // New bookmark heads: maximal elements of old heads plus the new change.
        // The working copy continues on its own base plus the new change, which
        // is exactly what the files on disk contain; the bookmark may hold
        // other heads (and conflicts) the working copy has not checked out.
        let old_heads = self.heads_of(&op.view, &self.config.bookmark)?;
        let old_base = snap.base.maximal(&snap.wc.deps);
        let mut all: Vec<ChangeHash> = old_heads.clone();
        all.extend(old_base.iter().copied());
        all.push(hash);
        // The snapshot already loaded the working copy's base; when that also
        // holds every bookmark head, it is the state to extend.
        let mut st = if old_heads.iter().all(|h| snap.base.contains(h)) {
            snap.base
        } else {
            self.load_state(&all)?
        };
        st.add_hashed(hash, change)?;
        let mut with_new = old_heads.clone();
        with_new.push(hash);
        let new_heads = st.maximal(&with_new);
        // Automatic checkpoint once enough changes accumulated (spec §11).
        let since = self
            .latest_checkpoint(&self.config.bookmark)?
            .map(|(_, cp)| cp.count)
            .unwrap_or(0);
        if self.config.checkpoint_interval > 0
            && (st.len() as u64).saturating_sub(since) >= self.config.checkpoint_interval
        {
            let cp_state = self.load_state_full(&new_heads)?;
            self.write_checkpoint(&self.config.bookmark, &cp_state, &new_heads)?;
        }
        let mut wc_base = old_base.clone();
        wc_base.push(hash);
        let wc_base = st.maximal(&wc_base);
        drop(extending);

        // The graph keys of the files as they now are, from the state the
        // commit just extended: a file whose graph it built has none, and
        // is read by the next snapshot; a key the next base does not share
        // (the bookmark held other heads) is simply not trusted then.
        let keying = crate::timing::phase("commit: graph keys of the files");
        let committed_keys =
            (!partial).then(|| self.committed_graph_keys(&st, &changed_paths, &snap.attributes));
        drop(keying);
        let recording = crate::timing::phase("commit: record");
        let wc = self.new_working_copy(wc_base, "");
        let wc_hash = self.store.put_change(&wc)?;
        let mut view = op.view.clone();
        view.bookmarks.insert(
            self.config.bookmark.clone(),
            self.store.put_state(&StateObject::new(new_heads))?,
        );
        view.workspaces.insert(self.workspace, wc_hash);
        self.record_op(&[op_ref], &format!("oxy commit -m {message:?}"), view)?;
        drop(recording);
        let rewriting = crate::timing::phase("commit: manifest");
        if partial {
            // The rest is rebuilt from disk by the next snapshot.
            self.drop_manifest();
        } else {
            let conflicted = snap.base_snapshot.is_conflicted() && !snap.resolves;
            // The files on disk are now exactly the new base's renderings:
            // record their graph keys, so the next snapshot neither reads nor
            // renders them (oxygen#35).
            let keys = if conflicted {
                HashMap::new()
            } else {
                committed_keys.unwrap_or_default()
            };
            match pending {
                Some(m) => self.write_pending_manifest(m, conflicted, keys)?,
                None => self.rewrite_manifest(conflicted, false, &keys)?,
            }
        }
        drop(rewriting);
        let packing = crate::timing::phase("commit: autopack");
        self.maybe_autopack()?;
        drop(packing);
        let _hook = crate::timing::phase("commit: hook");
        let _ = self.run_hook(
            "post-commit",
            &format!(
                "{{\"event\":\"post-commit\",\"change_id\":{},\"hash\":{},\"message\":{}}}",
                json_str(&snap.wc.change_id.to_hex()),
                json_str(&hash.to_hex()),
                json_str(message)
            ),
        );
        Ok(hash)
    }
}

/// What part of the working copy a commit takes (spec §12.3).
#[derive(Clone, Debug)]
pub enum Selection {
    All,
    /// Every operation and edit on nodes under these paths.
    Paths(Vec<String>),
    /// Hunk indices as `Repo::hunks` numbers them; dependent hunks are added.
    Hunks(Vec<usize>),
}

/// One selectable piece of the working copy: a tree operation or an edit.
#[derive(Clone, Debug)]
pub struct Hunk {
    pub index: usize,
    pub path: String,
    /// Rendered like `oxy diff`.
    pub text: String,
}

/// The tree operations and edits on nodes under `paths`, plus the
/// additions of any new parent directories they need.
fn select_paths(
    wc: &Change,
    base_snapshot: &Snapshot,
    paths: &[String],
) -> (Vec<TreeOp>, Vec<Edit>) {
    let selected = |p: &str| {
        paths
            .iter()
            .any(|x| p == x || p.starts_with(&format!("{}/", x.trim_end_matches('/'))))
    };
    let by_node = base_snapshot.tree.by_node();
    let mut new_names: HashMap<NodeId, (NodeId, String, NodeKind)> = HashMap::new();
    for op in &wc.tree_ops {
        if let TreeOp::AddNode {
            node,
            parent,
            name,
            kind,
            ..
        } = op
        {
            new_names.insert(*node, (*parent, name.clone(), *kind));
        }
    }
    let mut nodes: BTreeSet<NodeId> = BTreeSet::new();
    for n in wc
        .tree_ops
        .iter()
        .map(|o| o.node())
        .chain(wc.edits.iter().map(|e| e.node()))
    {
        if path_of_node(&n, &by_node, &new_names).is_some_and(|p| selected(&p)) {
            nodes.insert(n);
        }
    }
    // New parents of selected new nodes come along.
    let mut changed = true;
    while changed {
        changed = false;
        for (n, (parent, _, _)) in &new_names {
            if nodes.contains(n) && new_names.contains_key(parent) && nodes.insert(*parent) {
                changed = true;
            }
        }
    }
    let ops = wc
        .tree_ops
        .iter()
        .filter(|o| nodes.contains(&o.node()))
        .cloned()
        .collect();
    let edits = wc
        .edits
        .iter()
        .filter(|e| nodes.contains(&e.node()))
        .cloned()
        .collect();
    (ops, edits)
}

/// The hunks `indices` name plus whatever they refer to within the working
/// copy (the parent directory of an added node, the insert that introduced
/// an anchor line), renumbered so the result is a well-formed change.
fn select_hunks(wc: &Change, indices: &[usize]) -> (Vec<TreeOp>, Vec<Edit>) {
    let n_ops = wc.tree_ops.len();
    let mut ops_sel = vec![false; n_ops];
    let mut edits_sel = vec![false; wc.edits.len()];
    for &i in indices {
        if i < n_ops {
            ops_sel[i] = true;
        } else if i - n_ops < wc.edits.len() {
            edits_sel[i - n_ops] = true;
        }
    }
    // Atom ranges each insert introduces, per node, in the working copy's numbering.
    let mut per_node: HashMap<NodeId, u32> = HashMap::new();
    let mut insert_ranges: Vec<Option<(NodeId, u32, u32)>> = Vec::new();
    for e in &wc.edits {
        insert_ranges.push(match e {
            Edit::Insert { node, lines, .. } => {
                let start = per_node.entry(*node).or_default();
                let r = (*node, *start, *start + lines.len() as u32);
                *start += lines.len() as u32;
                Some(r)
            }
            _ => None,
        });
    }
    let add_index: HashMap<NodeId, usize> = wc
        .tree_ops
        .iter()
        .enumerate()
        .filter_map(|(i, o)| {
            if let TreeOp::AddNode { node, .. } = o {
                Some((*node, i))
            } else {
                None
            }
        })
        .collect();
    let insert_for = |node: &NodeId, index: u32| -> Option<usize> {
        insert_ranges
            .iter()
            .position(|r| matches!(r, Some((n, a, b)) if n == node && *a <= index && index < *b))
    };
    // Closure.
    let mut changed = true;
    while changed {
        changed = false;
        for i in 0..n_ops {
            if !ops_sel[i] {
                continue;
            }
            if let TreeOp::AddNode { node, parent, .. } = &wc.tree_ops[i] {
                if let Some(&p) = add_index.get(parent) {
                    if !ops_sel[p] {
                        ops_sel[p] = true;
                        changed = true;
                    }
                }
                // A new node's content belongs with its addition: nobody
                // wants an empty file committed apart from its lines.
                for (j, e) in wc.edits.iter().enumerate() {
                    if e.node() == *node && !edits_sel[j] {
                        edits_sel[j] = true;
                        changed = true;
                    }
                }
            }
        }
        for j in 0..wc.edits.len() {
            if !edits_sel[j] {
                continue;
            }
            let e = &wc.edits[j];
            if let Some(&a) = add_index.get(&e.node()) {
                if !ops_sel[a] {
                    ops_sel[a] = true;
                    changed = true;
                }
            }
            if let Edit::Insert {
                node,
                after,
                before,
                ..
            } = e
            {
                for r in [after, before] {
                    if let AtomRef::Atom { change, index } = r {
                        if change.is_zero() {
                            if let Some(k) = insert_for(node, *index) {
                                if !edits_sel[k] {
                                    edits_sel[k] = true;
                                    changed = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    // Renumber self-references: old atom index → new index among selected inserts.
    let mut remap: HashMap<(NodeId, u32), u32> = HashMap::new();
    let mut new_counts: HashMap<NodeId, u32> = HashMap::new();
    for (j, r) in insert_ranges.iter().enumerate() {
        if let (true, Some((node, a, b))) = (edits_sel[j], r) {
            let next = new_counts.entry(*node).or_default();
            for old in *a..*b {
                remap.insert((*node, old), *next);
                *next += 1;
            }
        }
    }
    let map_ref = |r: AtomRef, node: &NodeId| -> AtomRef {
        match r {
            AtomRef::Atom { change, index } if change.is_zero() => AtomRef::Atom {
                change,
                index: remap.get(&(*node, index)).copied().unwrap_or(index),
            },
            other => other,
        }
    };
    let ops = wc
        .tree_ops
        .iter()
        .enumerate()
        .filter(|(i, _)| ops_sel[*i])
        .map(|(_, o)| o.clone())
        .collect();
    let edits = wc
        .edits
        .iter()
        .enumerate()
        .filter(|(j, _)| edits_sel[*j])
        .map(|(_, e)| match e {
            Edit::Insert {
                node,
                after,
                before,
                lines,
            } => Edit::Insert {
                node: *node,
                after: map_ref(*after, node),
                before: map_ref(*before, node),
                lines: lines.clone(),
            },
            other => other.clone(),
        })
        .collect();
    (ops, edits)
}

/// Render each tree operation and edit of `change` on its own, numbered.
pub fn render_hunks(change: &Change, base: &State, base_snapshot: &Snapshot) -> Vec<Hunk> {
    let by_node = base_snapshot.tree.by_node();
    let mut new_names: HashMap<NodeId, (NodeId, String, NodeKind)> = HashMap::new();
    for op in &change.tree_ops {
        if let TreeOp::AddNode {
            node,
            parent,
            name,
            kind,
            ..
        } = op
        {
            new_names.insert(*node, (*parent, name.clone(), *kind));
        }
    }
    let mut out = Vec::new();
    for (i, op) in change.tree_ops.iter().enumerate() {
        let one = Change {
            tree_ops: vec![op.clone()],
            edits: vec![],
            ..change.clone()
        };
        let path = path_of_node(&op.node(), &by_node, &new_names).unwrap_or_default();
        out.push(Hunk {
            index: i,
            path,
            text: render_change(&one, base, base_snapshot),
        });
    }
    for (j, e) in change.edits.iter().enumerate() {
        let one = Change {
            tree_ops: vec![],
            edits: vec![e.clone()],
            ..change.clone()
        };
        let path = path_of_node(&e.node(), &by_node, &new_names).unwrap_or_default();
        out.push(Hunk {
            index: change.tree_ops.len() + j,
            path,
            text: render_change(&one, base, base_snapshot),
        });
    }
    out
}

/// One file's part of a diff, for `oxy diff --json`.
#[derive(Clone, Debug)]
pub struct FileDiff {
    pub path: String,
    /// `added`, `removed`, `modified`, `renamed`, `mode`, `replaced`.
    pub kind: String,
    pub hunks: Vec<DiffHunk>,
    /// For renames, the previous path.
    pub from: Option<String>,
}

/// Lines inserted after `base_line` (0 = before the first line) and lines
/// removed, with their base line numbers.
#[derive(Clone, Debug, Default)]
pub struct DiffHunk {
    pub base_line: u32,
    pub added: Vec<Vec<u8>>,
    pub removed: Vec<(u32, Vec<u8>)>,
}

impl Repo {
    /// The content of `path` in a state: `heads`, or the working copy's base.
    pub fn file_at(&self, path: &str, heads: Option<&[ChangeHash]>) -> Result<Vec<u8>> {
        let snapshot = match heads {
            Some(h) => self.load_state(h)?.materialize(),
            None => {
                let (_, wc) = self.working_copy()?;
                self.load_state(&wc.deps)?.materialize()
            }
        };
        let Some(f) = snapshot.files.get(path) else {
            return fail(format!("{path} is not in that state"));
        };
        match &f.content {
            FileContent::Dir => fail(format!("{path} is a directory")),
            FileContent::Text { bytes, .. } => Ok(bytes.clone()),
            FileContent::Opaque { blobs } => match blobs.first() {
                Some(b) => self.read_blob(b),
                None => Ok(vec![]),
            },
        }
    }

    /// Restore `paths` (files or directories) to the working copy's base:
    /// edits are undone, additions removed, removals put back. Returns the
    /// number of paths touched.
    pub fn discard(&self, paths: &[String]) -> Result<usize> {
        let _wc = self.lock_working_copy()?;
        let snap = self.snapshot_status("oxy discard")?;
        let under = |p: &str| {
            paths
                .iter()
                .any(|x| p == x || p.starts_with(&format!("{}/", x.trim_end_matches('/'))))
        };
        let attrs = Repo::state_attributes(&snap.base_snapshot);
        let mut n = 0;
        for s in &snap.statuses {
            if !under(&s.path) {
                continue;
            }
            match snap.base_snapshot.files.get(&s.path) {
                None => {
                    // Added (or the new name of a rename): remove it.
                    let full = self.root.join(&s.path);
                    if full.is_dir() {
                        let _ = fs::remove_dir_all(&full);
                    } else {
                        let _ = fs::remove_file(&full);
                    }
                    n += 1;
                }
                Some(f) => {
                    match &f.content {
                        FileContent::Dir => fs::create_dir_all(self.root.join(&s.path))?,
                        FileContent::Text { bytes, .. } => {
                            let on_disk: std::borrow::Cow<[u8]> = if attrs.lookup(&s.path).eol
                                == Some(crate::attributes::Eol::Crlf)
                            {
                                crate::attributes::to_crlf(bytes).into()
                            } else {
                                bytes.as_slice().into()
                            };
                            self.write_file(&s.path, &on_disk, f.mode.exec)?;
                        }
                        FileContent::Opaque { blobs } => {
                            let bytes = match blobs.first() {
                                Some(b) => self.read_blob(b)?,
                                None => vec![],
                            };
                            if f.kind == NodeKind::Symlink {
                                self.write_symlink(&s.path, &bytes)?;
                            } else if f.kind == NodeKind::File {
                                self.write_file(&s.path, &bytes, f.mode.exec)?;
                            }
                        }
                    }
                    n += 1;
                }
            }
        }
        // A rename's old name is not in the statuses; put it back too.
        for (p, f) in &snap.base_snapshot.files {
            if under(p)
                && !self.root.join(p).exists()
                && f.kind != NodeKind::Dir
                && f.kind != NodeKind::Subrepo
                && !snap.statuses.iter().any(|s| s.path == *p)
            {
                let bytes = match &f.content {
                    FileContent::Text { bytes, .. } => bytes.clone(),
                    FileContent::Opaque { blobs } => blobs
                        .first()
                        .map(|b| self.read_blob(b))
                        .transpose()?
                        .unwrap_or_default(),
                    FileContent::Dir => continue,
                };
                if f.kind == NodeKind::Symlink {
                    self.write_symlink(p, &bytes)?
                } else {
                    self.write_file(p, &bytes, f.mode.exec)?
                }
                n += 1;
            }
        }
        self.drop_manifest();
        Ok(n)
    }

    /// Undo the working-copy hunks `indices` (as `hunks` numbers them) on
    /// disk, keeping the others: the files are rewritten from the base plus
    /// the remaining hunks.
    pub fn discard_hunks(&self, indices: &[usize]) -> Result<usize> {
        let _wc = self.lock_working_copy()?;
        let (snap, hunks) = self.hunks()?;
        let keep: Vec<usize> = hunks
            .iter()
            .map(|h| h.index)
            .filter(|i| !indices.contains(i))
            .collect();
        let (ops, edits) = select_hunks(&snap.wc, &keep);
        let dropped_nodes: BTreeSet<NodeId> = hunks
            .iter()
            .filter(|h| indices.contains(&h.index))
            .map(|h| {
                if h.index < snap.wc.tree_ops.len() {
                    snap.wc.tree_ops[h.index].node()
                } else {
                    snap.wc.edits[h.index - snap.wc.tree_ops.len()].node()
                }
            })
            .collect();
        let mut partial = snap.wc.clone();
        partial.tree_ops = ops;
        partial.edits = edits;
        partial.normalize();
        let mut st = snap.base.clone();
        st.add_unchecked(partial);
        // Every file of the target is rendered: build the graphs the
        // partial snapshot left out.
        self.load_all_graphs(&mut st)?;
        let target = st.materialize();
        let by_node_target = target.tree.by_node();
        let by_node_base = snap.base_snapshot.tree.by_node();
        let attrs = Repo::state_attributes(&target);
        let mut n = 0;
        for node in dropped_nodes {
            match by_node_target.get(&node) {
                Some(e) => {
                    let f = &target.files[&e.path];
                    match &f.content {
                        FileContent::Dir => {}
                        FileContent::Text { bytes, .. } => {
                            let on_disk: std::borrow::Cow<[u8]> = if attrs.lookup(&e.path).eol
                                == Some(crate::attributes::Eol::Crlf)
                            {
                                crate::attributes::to_crlf(bytes).into()
                            } else {
                                bytes.as_slice().into()
                            };
                            self.write_file(&e.path, &on_disk, f.mode.exec)?;
                        }
                        FileContent::Opaque { blobs } => {
                            let bytes = blobs
                                .first()
                                .map(|b| self.read_blob(b))
                                .transpose()?
                                .unwrap_or_default();
                            if f.kind == NodeKind::Symlink {
                                self.write_symlink(&e.path, &bytes)?
                            } else {
                                self.write_file(&e.path, &bytes, f.mode.exec)?
                            }
                        }
                    }
                    // A discarded rename: the new name goes.
                    if let Some(old_path) = snap
                        .statuses
                        .iter()
                        .find(|s| {
                            s.status == ChangeStatus::Renamed && !target.files.contains_key(&s.path)
                        })
                        .map(|s| s.path.clone())
                    {
                        let _ = fs::remove_file(self.root.join(old_path));
                    }
                    n += 1;
                }
                None => {
                    // The node exists in neither target nor base with a live path: an addition to remove.
                    if let Some(added) = snap.statuses.iter().find(|s| {
                        s.status == ChangeStatus::Added
                            && !target.files.contains_key(&s.path)
                            && !by_node_base.contains_key(&node)
                    }) {
                        let full = self.root.join(&added.path);
                        if full.is_dir() {
                            let _ = fs::remove_dir_all(&full);
                        } else {
                            let _ = fs::remove_file(&full);
                        }
                        n += 1;
                    }
                }
            }
        }
        self.drop_manifest();
        Ok(n)
    }

    /// The diff of the working copy (`None`) or of a change, per file with
    /// line-numbered hunks (spec: `oxy diff --json`).
    pub fn diff_files(&self, change: Option<&ChangeHash>) -> Result<Vec<FileDiff>> {
        let (c, base, base_snapshot) = match change {
            Some(h) => {
                let c = self.store.get_change(h)?;
                let (base, snapshot) = self.change_base(&c)?;
                (c, base, snapshot)
            }
            None => self.working_copy_with_base()?,
        };
        Ok(diff_files_of(&c, &base, &base_snapshot))
    }

    /// The snapshot a command would take, without taking it, when the
    /// status cache holds: every file is as the last snapshot left it, so
    /// that snapshot's working-copy change is the answer. Its base comes
    /// from the state index, the `.oxyattributes` files from disk. `None`
    /// when a snapshot must be taken, and when there is nothing to commit
    /// (the snapshot then says so). A conflicted base never gets here: the
    /// cache does not hold for one.
    pub(crate) fn snapshot_from_cache(&self) -> Result<Option<SnapshotResult>> {
        let Some(statuses) = self.status_by_manifest()? else {
            return Ok(None);
        };
        if statuses.is_empty() {
            return Ok(None);
        }
        let _t = crate::timing::phase("snapshot: from the status cache");
        let (wc_hash, wc) = self.working_copy()?;
        let base = self.load_state_indexed(&wc.deps)?;
        let (base, base_snapshot) = self.render_base_for(&wc, base)?;
        let attribute_files: Vec<(String, Vec<u8>)> = match self.read_manifest()? {
            Some((_, _, m)) => m
                .entries
                .keys()
                .filter(|p| is_attributes(p))
                .filter_map(|p| fs::read(self.root.join(p)).ok().map(|b| (p.clone(), b)))
                .collect(),
            None => Vec::new(),
        };
        let attributes = crate::attributes::Attributes::from_files(
            attribute_files
                .iter()
                .map(|(p, b)| (p.as_str(), b.as_slice())),
        );
        Ok(Some(SnapshotResult {
            wc_hash,
            wc,
            base,
            base_snapshot,
            statuses,
            changed: false,
            resolves: false,
            contributors: Vec::new(),
            attributes,
            untracked_nested: self.untracked_nested.borrow().clone(),
            manifest: None,
        }))
    }

    /// The working-copy change with its base state and the base's
    /// rendering, for showing what the working copy changes. While the
    /// status cache holds (every file as the last snapshot left it), the
    /// stored working-copy change is the answer and no snapshot is taken;
    /// otherwise a snapshot makes it.
    pub fn working_copy_with_base(&self) -> Result<(Change, State, Snapshot)> {
        if self.status_by_manifest()?.is_some() {
            let (_, wc) = self.working_copy()?;
            let base = self.load_state_indexed(&wc.deps)?;
            let (base, snapshot) = self.render_base_for(&wc, base)?;
            return Ok((wc, base, snapshot));
        }
        let snap = self.snapshot_status("oxy diff")?;
        Ok((snap.wc, snap.base, snap.base_snapshot))
    }

    /// The log restricted to changes touching `path` (its node, so renames
    /// are followed), on the current bookmark.
    pub fn log_for_path(&self, path: &str) -> Result<Vec<LogEntry>> {
        let heads = self.bookmark_heads()?;
        if self.is_bare() {
            return self.log_for_path_in(path, &heads);
        }
        let entries = self.log()?;
        let (_, wc) = self.working_copy()?;
        let base_snapshot = self.load_state(&wc.deps)?.materialize();
        let state_snapshot = self.load_state(&heads)?.materialize();
        let node = base_snapshot
            .files
            .get(path)
            .or_else(|| state_snapshot.files.get(path))
            .map(|f| f.node);
        let Some(node) = node else {
            return fail(format!("{path} is not tracked"));
        };
        Ok(self.entries_touching(entries, node))
    }

    /// The log of the state with these heads restricted to changes touching
    /// `path` (its node, so renames are followed).
    pub fn log_for_path_in(&self, path: &str, heads: &[ChangeHash]) -> Result<Vec<LogEntry>> {
        self.log_for_path_of(&self.load_state_history(heads)?, path, None)
    }

    /// The changes of a loaded state touching `path`, newest first, at most
    /// `limit` of them. The path is found in the state's tree alone, so no
    /// file is rendered, and the walk stops once `limit` are found.
    pub fn log_for_path_of(
        &self,
        state: &State,
        path: &str,
        limit: Option<usize>,
    ) -> Result<Vec<LogEntry>> {
        let Some(node) = state.tree().view().entries.get(path).map(|e| e.node) else {
            return fail(format!("{path} is not in that state"));
        };
        Ok(self.entries_touching_up_to(self.log_of(state), node, limit))
    }

    fn entries_touching(&self, entries: Vec<LogEntry>, node: NodeId) -> Vec<LogEntry> {
        self.entries_touching_up_to(entries, node, None)
    }

    fn entries_touching_up_to(
        &self,
        entries: Vec<LogEntry>,
        node: NodeId,
        limit: Option<usize>,
    ) -> Vec<LogEntry> {
        let mut out = Vec::new();
        for e in entries {
            if limit.is_some_and(|n| out.len() >= n) {
                break;
            }
            let Ok(c) = self.store.get_change(&e.hash) else {
                continue;
            };
            if c.tree_ops.iter().any(|o| o.node() == node)
                || c.edits.iter().any(|x| x.node() == node)
            {
                out.push(e);
            }
        }
        out
    }
}

/// Per-file hunks of `change` against `base`.
pub fn diff_files_of(change: &Change, base: &State, base_snapshot: &Snapshot) -> Vec<FileDiff> {
    let by_node = base_snapshot.tree.by_node();
    let mut new_names: HashMap<NodeId, (NodeId, String, NodeKind)> = HashMap::new();
    for op in &change.tree_ops {
        if let TreeOp::AddNode {
            node,
            parent,
            name,
            kind,
            ..
        } = op
        {
            new_names.insert(*node, (*parent, name.clone(), *kind));
        }
    }
    let path_of = |n: &NodeId| -> String {
        path_of_node(n, &by_node, &new_names).unwrap_or_else(|| format!("<node {}>", n.short(8)))
    };
    let mut files: BTreeMap<NodeId, FileDiff> = BTreeMap::new();
    let mut order: Vec<NodeId> = Vec::new();
    let mut entry = |files: &mut BTreeMap<NodeId, FileDiff>, n: NodeId, kind: &str| {
        if let std::collections::btree_map::Entry::Vacant(v) = files.entry(n) {
            order.push(n);
            v.insert(FileDiff {
                path: path_of(&n),
                kind: kind.to_string(),
                hunks: vec![],
                from: None,
            });
        }
    };
    for op in &change.tree_ops {
        match op {
            TreeOp::AddNode { node, kind, .. } => {
                if *kind != NodeKind::Dir {
                    entry(&mut files, *node, "added");
                }
            }
            TreeOp::RemoveNode { node, .. } => {
                entry(&mut files, *node, "removed");
                if let Some(e) = by_node.get(node) {
                    files.get_mut(node).unwrap().path = e.path.clone();
                }
            }
            TreeOp::Move {
                node, parent, name, ..
            } => {
                entry(&mut files, *node, "renamed");
                let f = files.get_mut(node).unwrap();
                f.from = by_node.get(node).map(|e| e.path.clone());
                let dir = if parent.is_root() {
                    String::new()
                } else {
                    path_of_node(parent, &by_node, &new_names).unwrap_or_default()
                };
                f.path = if dir.is_empty() {
                    name.clone()
                } else {
                    format!("{dir}/{name}")
                };
            }
            TreeOp::SetMode { node, .. } => entry(&mut files, *node, "mode"),
        }
    }
    // Base line numbers per node, 1-based.
    let mut line_of: HashMap<NodeId, HashMap<(ChangeHash, u32), u32>> = HashMap::new();
    let mut lines_for = |n: &NodeId| -> HashMap<(ChangeHash, u32), u32> {
        line_of
            .entry(*n)
            .or_insert_with(|| {
                base.live_lines(n)
                    .into_iter()
                    .enumerate()
                    .map(|(i, (k, _))| (k, i as u32 + 1))
                    .collect()
            })
            .clone()
    };
    for e in &change.edits {
        let n = e.node();
        let is_new = new_names.contains_key(&n);
        entry(&mut files, n, if is_new { "added" } else { "modified" });
        let f = files.get_mut(&n).unwrap();
        match e {
            Edit::Insert { after, lines, .. } => {
                let map = lines_for(&n);
                let base_line = match after {
                    AtomRef::Start => 0,
                    AtomRef::End => map.len() as u32,
                    AtomRef::Atom { change, index } if change.is_zero() => {
                        f.hunks.last().map(|h| h.base_line).unwrap_or(0)
                    }
                    AtomRef::Atom { change, index } => {
                        map.get(&(*change, *index)).copied().unwrap_or(0)
                    }
                };
                f.hunks.push(DiffHunk {
                    base_line,
                    added: lines.to_vec(),
                    removed: vec![],
                });
            }
            Edit::Delete { atoms, .. } => {
                let map = lines_for(&n);
                let mut removed = Vec::new();
                for r in atoms {
                    for i in r.from..r.to {
                        let line = map.get(&(r.change, i)).copied().unwrap_or(0);
                        let text = base
                            .file(&n)
                            .and_then(|g| g.content(&(r.change, i)))
                            .unwrap_or(b"")
                            .to_vec();
                        removed.push((line, text));
                    }
                }
                let base_line = removed
                    .first()
                    .map(|(l, _)| l.saturating_sub(1))
                    .unwrap_or(0);
                f.hunks.push(DiffHunk {
                    base_line,
                    added: vec![],
                    removed,
                });
            }
            Edit::Replace { .. } => {
                if !is_new {
                    f.kind = "replaced".into();
                }
            }
        }
    }
    order.into_iter().filter_map(|n| files.remove(&n)).collect()
}

/// Builds the tree ops and edits of a working-copy change against a base.
/// `BLAKE3("oxy node 1" 0 seed kind path)`, truncated: a node identifier
/// that the same seed and path always give (never the root's).
fn seeded_node(seed: &[u8; 32], path: &str, kind: NodeKind) -> NodeId {
    let mut h = blake3::Hasher::new();
    h.update(b"oxy node 1\0");
    h.update(seed);
    h.update(&[match kind {
        NodeKind::File => 1,
        NodeKind::Dir => 2,
        NodeKind::Symlink => 3,
        NodeKind::Subrepo => 4,
    }]);
    h.update(path.as_bytes());
    let mut id = [0u8; 16];
    id.copy_from_slice(&h.finalize().as_bytes()[..16]);
    if id == [0; 16] {
        id[15] = 1;
    }
    NodeId(id)
}

struct ChangeBuilder<'a> {
    base: &'a State,
    base_snapshot: &'a Snapshot,
    tree_ops: Vec<TreeOp>,
    edits: Vec<Edit>,
    statuses: Vec<PathStatus>,
    dir_nodes: HashMap<String, NodeId>,
    reuse: HashMap<String, (NodeId, NodeKind)>,
    /// Changes that contributed to conflicts this working copy resolves.
    contributors: BTreeSet<ChangeHash>,
    resolves: bool,
    attrs: crate::attributes::Attributes,
    blobs: HashMap<String, ObjectRef>,
    /// Opaque files whose replace conflict the content settles.
    resolve: HashSet<String>,
    /// When set, new nodes' identifiers derive from it and their paths.
    node_seed: Option<[u8; 32]>,
    /// For a Git import, the base's dead directories by where they were
    /// (see `ensure_dir`), worked out when first needed.
    dead_dirs: Option<HashMap<(NodeId, String), (NodeId, crate::tree::OpKey)>>,
    /// Text edits of edited files, worked out in parallel beforehand
    /// (`diff_in_parallel`); a file not here is diffed when it is updated.
    diffs: HashMap<String, Vec<Edit>>,
}

impl<'a> ChangeBuilder<'a> {
    fn new(
        base: &'a State,
        base_snapshot: &'a Snapshot,
        reuse: HashMap<String, (NodeId, NodeKind)>,
    ) -> Self {
        let mut dir_nodes: HashMap<String, NodeId> = HashMap::new();
        dir_nodes.insert(String::new(), NodeId::ROOT);
        for (p, e) in base_snapshot.tree.entries.iter() {
            if e.kind == NodeKind::Dir {
                dir_nodes.insert(p.clone(), e.node);
            }
        }
        ChangeBuilder {
            base,
            base_snapshot,
            tree_ops: vec![],
            edits: vec![],
            statuses: vec![],
            dir_nodes,
            reuse,
            contributors: BTreeSet::new(),
            resolves: false,
            attrs: crate::attributes::Attributes::default(),
            blobs: HashMap::new(),
            resolve: HashSet::new(),
            node_seed: None,
            dead_dirs: None,
            diffs: HashMap::new(),
        }
    }

    /// Diff the edited text files among `entries` against their base
    /// renderings at once, on every core, for `update_path` to take: the
    /// same diff it would make, only not one file after another.
    fn diff_in_parallel(&mut self, entries: &BTreeMap<String, FsEntry>) {
        use rayon::prelude::*;
        let files = &self.base_snapshot.files;
        let edited: Vec<(&String, &FsEntry, &crate::state::FileState)> = entries
            .iter()
            .filter_map(|(p, e)| {
                let x = files.get(p)?;
                (x.kind == e.kind && !e.unchanged && !self.opaque_for(p, e)).then_some((p, e, x))
            })
            .collect();
        // Below this, starting the threads costs more than it saves.
        if edited.len() < 16 {
            return;
        }
        let this = &*self;
        let attrs = &this.attrs;
        let diffs: Vec<(String, Vec<Edit>)> = edited
            .par_iter()
            .filter_map(|(p, e, x)| {
                let FileContent::Text {
                    bytes,
                    materialized,
                } = &x.content
                else {
                    return None;
                };
                if materialized.is_conflicted() {
                    return None;
                }
                let disk_text = if attrs.lookup(p).eol.is_some() {
                    std::sync::Arc::new(crate::attributes::normalize_eol(&e.content))
                } else {
                    e.content.clone()
                };
                if *bytes == *disk_text {
                    return None;
                }
                let keys = materialized.live_atoms();
                let lines = crate::diff::split_lines(bytes);
                (keys.len() == lines.len()).then(|| {
                    let edits = crate::diff::text_edits_of(x.node, &keys, &lines, &disk_text);
                    ((*p).clone(), edits)
                })
            })
            .collect();
        self.diffs = diffs.into_iter().collect();
    }

    fn with_attributes(mut self, attrs: crate::attributes::Attributes) -> Self {
        self.attrs = attrs;
        self
    }

    /// Whether a file is opaque: forced by `binary`, forced text by `text`
    /// only when it has no NUL bytes, else sniffed.
    /// The blob for an opaque entry: the cached one, else stored now.
    fn blob_of(
        &mut self,
        repo: &Repo,
        path: &str,
        e: &FsEntry,
        nocompress: bool,
    ) -> Result<ObjectRef> {
        let b = match e.blob {
            Some(b) => b,
            None => repo.store_blob_for(&e.content, nocompress)?,
        };
        self.blobs.insert(path.to_string(), b);
        Ok(b)
    }

    fn opaque_for(&self, path: &str, e: &FsEntry) -> bool {
        if e.blob.is_some() {
            return true;
        }
        if e.kind == NodeKind::Symlink || e.kind == NodeKind::Subrepo {
            return true;
        }
        match self.attrs.lookup(path).binary {
            Some(true) => true,
            Some(false) => is_binary(&e.content),
            None => is_binary(&e.content),
        }
    }

    /// Text content as stored: `\r\n` normalized for `eol=` files.
    fn stored_text(
        &self,
        path: &str,
        content: &std::sync::Arc<Vec<u8>>,
    ) -> std::sync::Arc<Vec<u8>> {
        if self.attrs.lookup(path).eol.is_some() {
            std::sync::Arc::new(crate::attributes::normalize_eol(content))
        } else {
            content.clone()
        }
    }

    /// The identifier of a node added at `path`: reused when asked, derived
    /// from the seed when there is one, random otherwise.
    fn new_node(&self, path: &str, kind: NodeKind) -> NodeId {
        if let Some(n) = self.reused_node(path, kind) {
            return n;
        }
        match &self.node_seed {
            Some(seed) => seeded_node(seed, path, kind),
            None => NodeId::random(),
        }
    }

    fn reused_node(&self, path: &str, kind: NodeKind) -> Option<NodeId> {
        self.reuse
            .get(path)
            .filter(|(_, k)| *k == kind)
            .map(|(n, _)| *n)
    }

    /// A dead directory last placed at (`parent`, `name`) in the base.
    fn revivable_dir(
        &mut self,
        parent: NodeId,
        name: &str,
    ) -> Option<(NodeId, crate::tree::OpKey)> {
        let base = self.base;
        self.dead_dirs
            .get_or_insert_with(|| base.tree().dead_dirs())
            .get(&(parent, name.to_string()))
            .copied()
    }

    fn ensure_dir(&mut self, path: &str) -> NodeId {
        if let Some(n) = self.dir_nodes.get(path) {
            return *n;
        }
        let mut parent = NodeId::ROOT;
        let mut prefix = String::new();
        for comp in path.split('/') {
            if !prefix.is_empty() {
                prefix.push('/');
            }
            prefix.push_str(comp);
            let known = self.dir_nodes.get(&prefix).copied();
            let revive = match known {
                Some(_) => None,
                None if self.node_seed.is_some() => self.revivable_dir(parent, comp),
                None => None,
            };
            parent = match (known, revive) {
                (Some(n), _) => n,
                (None, Some((node, old))) => {
                    // Git has no identity for a directory: one that comes
                    // back where it was is the same directory, brought back
                    // with a move, so lines of history that placed files in
                    // it before and after agree (oxygen#30).
                    self.tree_ops.push(TreeOp::Move {
                        node,
                        old: OpRef {
                            change: old.0,
                            index: old.1,
                        },
                        parent,
                        name: comp.to_string(),
                    });
                    self.dir_nodes.insert(prefix.clone(), node);
                    node
                }
                (None, None) => {
                    let node = self.new_node(&prefix, NodeKind::Dir);
                    self.tree_ops.push(TreeOp::AddNode {
                        node,
                        kind: NodeKind::Dir,
                        mode: Mode::default(),
                        parent,
                        name: comp.to_string(),
                    });
                    self.dir_nodes.insert(prefix.clone(), node);
                    node
                }
            };
        }
        parent
    }

    fn add_path(&mut self, repo: &Repo, path: &str, e: &FsEntry) -> Result<()> {
        let (dir, name) = split_path(path);
        let parent = self.ensure_dir(dir);
        let node = self.new_node(path, e.kind);
        let opaque = self.opaque_for(path, e);
        let nocompress = self.attrs.lookup(path).nocompress;
        self.tree_ops.push(TreeOp::AddNode {
            node,
            kind: e.kind,
            mode: Mode {
                exec: e.exec,
                opaque,
            },
            parent,
            name: name.to_string(),
        });
        if opaque {
            let blob = self.blob_of(repo, path, e, nocompress)?;
            self.edits.push(Edit::Replace {
                node,
                old: None,
                new: Some(blob),
            });
        } else if !e.content.is_empty() {
            let content = self.stored_text(path, &e.content);
            self.edits.push(Edit::Insert {
                node,
                after: crate::objects::AtomRef::Start,
                before: crate::objects::AtomRef::End,
                lines: crate::lines::Lines::split_shared(content),
            });
        }
        self.statuses.push(PathStatus {
            path: path.to_string(),
            status: ChangeStatus::Added,
        });
        Ok(())
    }

    /// Move the node at `old` to `new` and apply `e`'s content to it.
    fn move_path(
        &mut self,
        repo: &Repo,
        old: &str,
        new: &str,
        e: &FsEntry,
        expected: &crate::state::FileState,
    ) -> Result<()> {
        let entry = &self.base_snapshot.tree.entries[old];
        let (dir, name) = split_path(new);
        let parent = self.ensure_dir(dir);
        self.tree_ops.push(TreeOp::Move {
            node: expected.node,
            old: op_ref(entry.placement),
            parent,
            name: name.to_string(),
        });
        self.update_path(repo, old, e, expected)?;
        // update_path reports under the old path; the rename is what the user sees.
        self.statuses.retain(|s| s.path != old);
        self.statuses.push(PathStatus {
            path: new.to_string(),
            status: ChangeStatus::Renamed,
        });
        Ok(())
    }

    /// For a Git import: a node the commit keeps is in one place, the one
    /// its tree names, so any other live placement it has in the base goes;
    /// and a node the tree cannot show at all (an orphan) goes too. Such a
    /// placement is out of sight, under a directory another line of history
    /// removed, where no diff of the tree would ever reach it (oxygen#30).
    fn retire_stray_placements(&mut self) {
        let mut retired: HashSet<(ChangeHash, u32)> = HashSet::new();
        let mut placed: BTreeSet<NodeId> = BTreeSet::new();
        for op in &self.tree_ops {
            match op {
                TreeOp::Move { node, old, .. } => {
                    retired.insert((old.change, old.index));
                    placed.insert(*node);
                }
                TreeOp::RemoveNode { placement, .. } => {
                    retired.insert((placement.change, placement.index));
                }
                TreeOp::AddNode { .. } | TreeOp::SetMode { .. } => {}
            }
        }
        // Nodes kept where they were: what the base's tree view shows and
        // this change neither moves nor removes.
        let mut kept: HashMap<NodeId, (ChangeHash, u32)> = HashMap::new();
        for e in self.base_snapshot.tree.entries.values() {
            if !retired.contains(&e.placement) {
                kept.insert(e.node, e.placement);
            }
        }
        // Only a node with several live placements can have a stray one,
        // and the tree view names each as a conflict.
        let multi: BTreeSet<NodeId> = self
            .base_snapshot
            .tree
            .conflicts
            .iter()
            .filter_map(|c| match c {
                crate::tree::TreeConflict::MultiPlacement { node, .. } => Some(*node),
                _ => None,
            })
            .collect();
        let mut extra = Vec::new();
        // A node whose only placements are under a directory another line
        // removed (an orphan) is nowhere the tree can show, and Git's tree
        // has no such path: it goes.
        for c in &self.base_snapshot.tree.conflicts {
            let crate::tree::TreeConflict::Orphan { node, .. } = c else {
                continue;
            };
            if kept.contains_key(node) || placed.contains(node) {
                continue;
            }
            for (k, _) in self.base.tree().live_placements(node) {
                if retired.insert(k) {
                    extra.push(TreeOp::RemoveNode {
                        node: *node,
                        placement: op_ref(k),
                    });
                }
            }
        }
        for node in placed
            .iter()
            .chain(multi.iter().filter(|n| kept.contains_key(*n)))
        {
            for (k, _) in self.base.tree().live_placements(node) {
                if retired.contains(&k) || kept.get(node) == Some(&k) {
                    continue;
                }
                retired.insert(k);
                extra.push(TreeOp::RemoveNode {
                    node: *node,
                    placement: op_ref(k),
                });
            }
        }
        if !extra.is_empty() {
            self.resolves = true;
            self.tree_ops.extend(extra);
        }
    }

    fn remove_path(&mut self, path: &str, expected: &crate::state::FileState) {
        let entry = &self.base_snapshot.tree.entries[path];
        self.tree_ops.push(TreeOp::RemoveNode {
            node: expected.node,
            placement: op_ref(entry.placement),
        });
        if path.contains(".oxy-conflict-") || expected.is_conflicted() {
            self.resolves = true;
        }
        self.statuses.push(PathStatus {
            path: path.to_string(),
            status: ChangeStatus::Removed,
        });
    }

    fn update_path(
        &mut self,
        repo: &Repo,
        path: &str,
        e: &FsEntry,
        expected: &crate::state::FileState,
    ) -> Result<()> {
        if expected.kind != e.kind {
            self.remove_path(path, expected);
            self.statuses.pop();
            self.add_path(repo, path, e)?;
            self.statuses.pop();
            self.statuses.push(PathStatus {
                path: path.to_string(),
                status: ChangeStatus::Modified,
            });
            return Ok(());
        }
        let entry = &self.base_snapshot.tree.entries[path];
        let node = expected.node;
        let mode_atom = entry.mode_atom.map(op_ref);
        if e.unchanged {
            // Known equal to the base's unconflicted rendering (spec
            // §12.3); only the executable bit can differ.
            if e.exec != expected.mode.exec {
                if let Some(old) = mode_atom {
                    self.tree_ops.push(TreeOp::SetMode {
                        node,
                        old,
                        mode: Mode {
                            exec: e.exec,
                            opaque: false,
                        },
                    });
                    self.statuses.push(PathStatus {
                        path: path.to_string(),
                        status: ChangeStatus::ModeChanged,
                    });
                }
            }
            return Ok(());
        }
        let mut status: Option<ChangeStatus> = None;
        let wants_opaque = self.opaque_for(path, e);
        let nocompress = self.attrs.lookup(path).nocompress;
        let disk_text = self.stored_text(path, &e.content);
        match &expected.content {
            FileContent::Dir => {}
            FileContent::Text {
                bytes,
                materialized,
            } => {
                if materialized.is_conflicted() {
                    if bytes == &*disk_text {
                        return Ok(());
                    }
                    if has_conflict_markers(&e.content) {
                        self.statuses.push(PathStatus {
                            path: path.to_string(),
                            status: ChangeStatus::ConflictEdited,
                        });
                        return Ok(());
                    }
                    // Resolution (spec §9.6): diff against the unconflicted lines
                    // with each region as a gap, then retire every region atom.
                    // Whatever the author kept from a region is re-inserted as
                    // new atoms, which leaves the graph totally ordered.
                    let regions = self.base.conflict_regions(&node);
                    let mut edits = text_edits(node, &regions.plain, &disk_text);
                    if !regions.region_atoms.is_empty() {
                        edits.insert(
                            0,
                            Edit::Delete {
                                node,
                                atoms: ranges(&regions.region_atoms),
                            },
                        );
                    }
                    self.edits.extend(edits);
                    self.contributors.extend(regions.contributors);
                    self.resolves = true;
                    if e.exec != expected.mode.exec {
                        if let Some(old) = mode_atom {
                            self.tree_ops.push(TreeOp::SetMode {
                                node,
                                old,
                                mode: Mode {
                                    exec: e.exec,
                                    opaque: false,
                                },
                            });
                        }
                    }
                    self.statuses.push(PathStatus {
                        path: path.to_string(),
                        status: ChangeStatus::Resolved,
                    });
                    return Ok(());
                }
                if wants_opaque {
                    // Text → opaque (spec §7.5), by content or by attribute.
                    if let Some(old) = mode_atom {
                        self.tree_ops.push(TreeOp::SetMode {
                            node,
                            old,
                            mode: Mode {
                                exec: e.exec,
                                opaque: true,
                            },
                        });
                    }
                    let live: Vec<_> = repo_live_keys(self.base, &node);
                    if !live.is_empty() {
                        self.edits.push(Edit::Delete {
                            node,
                            atoms: ranges(&live),
                        });
                    }
                    let blob = self.blob_of(repo, path, e, nocompress)?;
                    self.edits.push(Edit::Replace {
                        node,
                        old: None,
                        new: Some(blob),
                    });
                    status = Some(ChangeStatus::Modified);
                } else if bytes != &*disk_text {
                    let mut laps = crate::timing::Laps::start();
                    // The base's rendering holds its live atoms in order,
                    // one per line (it is not conflicted here).
                    let edits = match self.diffs.remove(path) {
                        Some(edits) => edits,
                        None => {
                            let keys = materialized.live_atoms();
                            let lines = crate::diff::split_lines(bytes);
                            if keys.len() == lines.len() {
                                crate::diff::text_edits_of(node, &keys, &lines, &disk_text)
                            } else {
                                text_edits(node, &self.base.live_lines(&node), &disk_text)
                            }
                        }
                    };
                    laps.lap("build: text diff");
                    if !edits.is_empty() {
                        self.edits.extend(edits);
                        status = Some(ChangeStatus::Modified);
                    }
                }
                let switched_to_opaque = wants_opaque;
                if !switched_to_opaque && e.exec != expected.mode.exec {
                    if let Some(old) = mode_atom {
                        self.tree_ops.push(TreeOp::SetMode {
                            node,
                            old,
                            mode: Mode {
                                exec: e.exec,
                                opaque: false,
                            },
                        });
                        status.get_or_insert(ChangeStatus::ModeChanged);
                    }
                }
            }
            FileContent::Opaque { blobs } => {
                let new_ref = e.blob.unwrap_or_else(|| Repo::blob_ref(&e.content));
                if e.kind == NodeKind::File && wants_opaque {
                    // Unchanged or replaced, the file stays opaque: remember its blob.
                    self.blobs.insert(path.to_string(), new_ref);
                }
                if blobs.len() > 1 && self.resolve.contains(path) && e.kind == expected.kind {
                    // Settle the replace conflict (spec §9.3): replace every
                    // live candidate with the chosen blob, depending on each
                    // change that made one live, so all are superseded.
                    let chosen = self.blob_of(repo, path, e, nocompress)?;
                    for b in blobs {
                        self.edits.push(Edit::Replace {
                            node,
                            old: Some(*b),
                            new: Some(chosen),
                        });
                    }
                    self.contributors
                        .extend(self.base.blob_contributors(&node, blobs));
                    self.resolves = true;
                    self.statuses.push(PathStatus {
                        path: path.to_string(),
                        status: ChangeStatus::Resolved,
                    });
                    return Ok(());
                }
                if blobs.len() > 1 {
                    if !blobs.contains(&new_ref) {
                        self.statuses.push(PathStatus {
                            path: path.to_string(),
                            status: ChangeStatus::ConflictEdited,
                        });
                    }
                    return Ok(());
                }
                let current = blobs.first().copied();
                if current != Some(new_ref) {
                    if e.kind == NodeKind::File && !wants_opaque {
                        // Opaque → text (spec §7.5).
                        if let Some(old) = mode_atom {
                            self.tree_ops.push(TreeOp::SetMode {
                                node,
                                old,
                                mode: Mode {
                                    exec: e.exec,
                                    opaque: false,
                                },
                            });
                        }
                        self.edits.push(Edit::Replace {
                            node,
                            old: current,
                            new: None,
                        });
                        if !e.content.is_empty() {
                            self.edits.push(Edit::Insert {
                                node,
                                after: crate::objects::AtomRef::Start,
                                before: crate::objects::AtomRef::End,
                                lines: crate::lines::Lines::split(&e.content),
                            });
                        }
                    } else {
                        let blob = self.blob_of(repo, path, e, nocompress)?;
                        self.edits.push(Edit::Replace {
                            node,
                            old: current,
                            new: Some(blob),
                        });
                    }
                    status = Some(ChangeStatus::Modified);
                } else if e.kind == NodeKind::File && e.exec != expected.mode.exec {
                    if let Some(old) = mode_atom {
                        self.tree_ops.push(TreeOp::SetMode {
                            node,
                            old,
                            mode: Mode {
                                exec: e.exec,
                                opaque: true,
                            },
                        });
                        status = Some(ChangeStatus::ModeChanged);
                    }
                }
            }
        }
        if let Some(s) = status {
            self.statuses.push(PathStatus {
                path: path.to_string(),
                status: s,
            });
        }
        Ok(())
    }
}

fn repo_live_keys(base: &State, node: &NodeId) -> Vec<crate::graph::AtomKey> {
    base.live_lines(node).into_iter().map(|(k, _)| k).collect()
}

/// The changes a change's scope references (spec §8.1): introducers of every
/// atom, placement, and mode it touches, and of every node it operates on.
pub fn referenced_changes(change: &Change, base: &State) -> BTreeSet<ChangeHash> {
    let mut out = BTreeSet::new();
    let opref = |r: &OpRef, out: &mut BTreeSet<ChangeHash>| {
        if !r.change.is_zero() {
            out.insert(r.change);
        }
    };
    let mut nodes: Vec<NodeId> = Vec::new();
    for op in &change.tree_ops {
        match op {
            TreeOp::AddNode { parent, .. } => nodes.push(*parent),
            TreeOp::RemoveNode { node, placement } => {
                nodes.push(*node);
                opref(placement, &mut out);
            }
            TreeOp::Move {
                node, old, parent, ..
            } => {
                nodes.push(*node);
                nodes.push(*parent);
                opref(old, &mut out);
            }
            TreeOp::SetMode { node, old, .. } => {
                nodes.push(*node);
                opref(old, &mut out);
            }
        }
    }
    for e in &change.edits {
        nodes.push(e.node());
        match e {
            Edit::Insert { after, before, .. } => {
                for r in [after, before] {
                    if let crate::objects::AtomRef::Atom { change, .. } = r {
                        if !change.is_zero() {
                            out.insert(*change);
                        }
                    }
                }
            }
            Edit::Delete { atoms, .. } => {
                // Deleting an atom also depends on whoever inserted the live
                // atoms right after it: the author saw those insertions, and
                // without the dependency spec §9.1 would call the deletion
                // concurrent with them (a delete/insert conflict).
                let graph = base.file(&e.node());
                for r in atoms {
                    if !r.change.is_zero() {
                        out.insert(r.change);
                    }
                    if let Some(g) = graph {
                        for i in r.from..r.to {
                            out.extend(
                                g.live_successor_changes(&(r.change, i))
                                    .into_iter()
                                    .filter(|c| !c.is_zero()),
                            );
                        }
                    }
                }
            }
            // Replacing a blob depends on the change that made it current,
            // as deleting a line depends on the line's introducer.
            Edit::Replace {
                node,
                old: Some(old),
                ..
            } => {
                out.extend(
                    base.live_replaces(node)
                        .into_iter()
                        .filter(|(c, b)| b == old && !c.is_zero())
                        .map(|(c, _)| c),
                );
            }
            Edit::Replace { .. } => {}
        }
    }
    for n in nodes {
        if let Some(h) = base.tree().introducer(&n) {
            out.insert(h);
        }
    }
    out
}

/// Paths of the nodes a change adds on top of `base_snapshot`.
pub fn added_node_paths(
    change: &Change,
    base_snapshot: &Snapshot,
) -> HashMap<String, (NodeId, NodeKind)> {
    let by_node = base_snapshot.tree.by_node();
    let mut new_names: HashMap<NodeId, (NodeId, String, NodeKind)> = HashMap::new();
    for op in &change.tree_ops {
        if let TreeOp::AddNode {
            node,
            parent,
            name,
            kind,
            ..
        } = op
        {
            new_names.insert(*node, (*parent, name.clone(), *kind));
        }
    }
    let mut out = HashMap::new();
    for (node, (_, _, kind)) in &new_names {
        if let Some(path) = path_of_node(node, &by_node, &new_names) {
            out.insert(path, (*node, *kind));
        }
    }
    out
}

fn path_of_node(
    n: &NodeId,
    by_node: &HashMap<NodeId, &crate::tree::TreeEntry>,
    new_names: &HashMap<NodeId, (NodeId, String, NodeKind)>,
) -> Option<String> {
    if let Some(e) = by_node.get(n) {
        return Some(e.path.clone());
    }
    let mut parts = Vec::new();
    let mut cur = *n;
    loop {
        if cur.is_root() {
            break;
        }
        if let Some(e) = by_node.get(&cur) {
            if !e.path.is_empty() {
                parts.push(e.path.clone());
            }
            break;
        }
        let (parent, name, _) = new_names.get(&cur)?;
        parts.push(name.clone());
        cur = *parent;
    }
    parts.reverse();
    Some(parts.join("/"))
}

/// Render a change's operations with line content, using `base` for deleted lines.
pub fn render_change(change: &Change, base: &State, base_snapshot: &Snapshot) -> String {
    let by_node = base_snapshot.tree.by_node();
    let mut new_names: HashMap<NodeId, (NodeId, String, NodeKind)> = HashMap::new();
    for op in &change.tree_ops {
        if let TreeOp::AddNode {
            node,
            parent,
            name,
            kind,
            ..
        } = op
        {
            new_names.insert(*node, (*parent, name.clone(), *kind));
        }
    }
    let path_of = |n: &NodeId| -> String {
        path_of_node(n, &by_node, &new_names).unwrap_or_else(|| format!("<node {}>", n.short(8)))
    };

    let mut out = String::new();
    for op in &change.tree_ops {
        match op {
            TreeOp::AddNode {
                node, kind, mode, ..
            } => {
                out.push_str(&format!(
                    "A {} ({:?}{}{})\n",
                    path_of(node),
                    kind,
                    if mode.exec { ", exec" } else { "" },
                    if mode.opaque { ", opaque" } else { "" }
                ));
            }
            TreeOp::RemoveNode { node, .. } => out.push_str(&format!("D {}\n", path_of(node))),
            TreeOp::Move { node, name, .. } => {
                out.push_str(&format!("R {} -> {}\n", path_of(node), name))
            }
            TreeOp::SetMode { node, mode, .. } => {
                out.push_str(&format!(
                    "M {} mode: exec={} opaque={}\n",
                    path_of(node),
                    mode.exec,
                    mode.opaque
                ));
            }
        }
    }
    let mut last_node: Option<NodeId> = None;
    for e in &change.edits {
        let n = e.node();
        if last_node != Some(n) {
            out.push_str(&format!("--- {}\n", path_of(&n)));
            last_node = Some(n);
        }
        match e {
            Edit::Insert { lines, .. } => {
                for l in lines.iter() {
                    out.push('+');
                    out.push_str(&String::from_utf8_lossy(l));
                    if !l.ends_with(b"\n") {
                        out.push('\n');
                    }
                }
            }
            Edit::Delete { atoms, .. } => {
                for r in atoms {
                    for i in r.from..r.to {
                        let content = base
                            .file(&n)
                            .and_then(|g| g.content(&(r.change, i)))
                            .unwrap_or(b"<unknown>\n");
                        out.push('-');
                        out.push_str(&String::from_utf8_lossy(content));
                        if !content.ends_with(b"\n") {
                            out.push('\n');
                        }
                    }
                }
            }
            Edit::Replace { old, new, .. } => {
                out.push_str(&format!(
                    "  opaque content {} -> {}\n",
                    old.map(|o| o.short(12)).unwrap_or_else(|| "none".into()),
                    new.map(|o| o.short(12)).unwrap_or_else(|| "none".into())
                ));
            }
        }
    }
    out
}

/// Pair removed files with added files of the same kind whose contents are
/// at least `RENAME_THRESHOLD` percent alike, best matches first. Beyond
/// `RENAME_LIMIT` candidate pairs only identical contents are paired.
const RENAME_THRESHOLD: u32 = 50;
const RENAME_LIMIT: usize = 10_000;

/// How a change is built beyond its entries: for a Git import, the seed
/// its new nodes' identifiers derive from; and, when it is built from part
/// of the tree, whether the new tree has anything under a directory.
#[derive(Default)]
struct Scope<'a> {
    seed: Option<[u8; 32]>,
    dir_needed: Option<&'a dyn Fn(&str) -> bool>,
}

fn detect_renames(
    base_snapshot: &Snapshot,
    fs_entries: &BTreeMap<String, FsEntry>,
    in_scope: impl Fn(&str) -> bool,
) -> Vec<(String, String)> {
    let removed: Vec<(&String, &crate::state::FileState)> = base_snapshot
        .files
        .iter()
        .filter(|(p, f)| {
            f.kind != NodeKind::Dir
                && !fs_entries.contains_key(*p)
                && in_scope(p)
                && !f.is_conflicted()
        })
        .collect();
    let added: Vec<(&String, &FsEntry)> = fs_entries
        .iter()
        .filter(|(p, e)| e.kind != NodeKind::Dir && !base_snapshot.files.contains_key(*p))
        .collect();
    if removed.is_empty() || added.is_empty() {
        return vec![];
    }
    let exact_only = removed.len() * added.len() > RENAME_LIMIT;
    let old_content = |f: &crate::state::FileState| -> Option<Vec<u8>> {
        match &f.content {
            FileContent::Text { bytes, .. } => Some(bytes.clone()),
            _ => None,
        }
    };
    let mut scored: Vec<(u32, usize, usize)> = Vec::new();
    for (ri, (_, f)) in removed.iter().enumerate() {
        let old = old_content(f);
        let old_blob = match &f.content {
            FileContent::Opaque { blobs } if blobs.len() == 1 => Some(blobs[0]),
            _ => None,
        };
        for (ai, (_, e)) in added.iter().enumerate() {
            if e.kind != f.kind {
                continue;
            }
            let score = match (&old, old_blob) {
                (Some(o), _) => {
                    if exact_only {
                        if *o == *e.content {
                            100
                        } else {
                            0
                        }
                    } else {
                        similarity(o, &e.content)
                    }
                }
                (None, Some(b)) if e.blob.unwrap_or_else(|| Repo::blob_ref(&e.content)) == b => 100,
                _ => 0,
            };
            if score >= RENAME_THRESHOLD {
                scored.push((score, ri, ai));
            }
        }
    }
    scored.sort_by(|a, b| {
        b.0.cmp(&a.0)
            .then(removed[a.1].0.cmp(removed[b.1].0))
            .then(added[a.2].0.cmp(added[b.2].0))
    });
    let mut used_r = vec![false; removed.len()];
    let mut used_a = vec![false; added.len()];
    let mut out = Vec::new();
    for (_, ri, ai) in scored {
        if used_r[ri] || used_a[ai] {
            continue;
        }
        used_r[ri] = true;
        used_a[ai] = true;
        out.push((removed[ri].0.clone(), added[ai].0.clone()));
    }
    out
}

/// Percentage of the larger file's bytes found in lines the two share
/// (multiset intersection of lines), like Git's similarity index.
pub fn similarity(a: &[u8], b: &[u8]) -> u32 {
    if a == b {
        return 100;
    }
    if a.is_empty() || b.is_empty() {
        return 0;
    }
    let mut counts: HashMap<&[u8], usize> = HashMap::new();
    for l in split_lines(a) {
        *counts.entry(l).or_default() += 1;
    }
    let mut shared = 0usize;
    for l in split_lines(b) {
        if let Some(n) = counts.get_mut(l) {
            if *n > 0 {
                *n -= 1;
                shared += l.len();
            }
        }
    }
    (shared * 100 / a.len().max(b.len())) as u32
}

/// Two maps side by side in key order: each key of either, with its value
/// in each. Linear, with no lookups, for maps of a whole tree.
fn join<'a, A, B>(
    a: &'a BTreeMap<String, A>,
    b: &'a BTreeMap<String, B>,
) -> impl Iterator<Item = (&'a String, Option<&'a A>, Option<&'a B>)> {
    let (mut a, mut b) = (a.iter().peekable(), b.iter().peekable());
    std::iter::from_fn(move || match (a.peek(), b.peek()) {
        (None, None) => None,
        (Some(_), None) => a.next().map(|(k, v)| (k, Some(v), None)),
        (None, Some(_)) => b.next().map(|(k, v)| (k, None, Some(v))),
        (Some((ka, _)), Some((kb, _))) => match ka.cmp(kb) {
            std::cmp::Ordering::Less => a.next().map(|(k, v)| (k, Some(v), None)),
            std::cmp::Ordering::Greater => b.next().map(|(k, v)| (k, None, Some(v))),
            std::cmp::Ordering::Equal => {
                let (k, va) = a.next()?;
                let (_, vb) = b.next()?;
                Some((k, Some(va), Some(vb)))
            }
        },
    })
}

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

    #[test]
    fn join_pairs_every_key_in_order() {
        let a: BTreeMap<String, u8> = [("a", 1), ("b/c", 2), ("d", 3)]
            .into_iter()
            .map(|(k, v)| (k.to_string(), v))
            .collect();
        let b: BTreeMap<String, char> = [("b", 'x'), ("b/c", 'y'), ("e", 'z')]
            .into_iter()
            .map(|(k, v)| (k.to_string(), v))
            .collect();
        let got: Vec<(String, Option<u8>, Option<char>)> = join(&a, &b)
            .map(|(k, x, y)| (k.clone(), x.copied(), y.copied()))
            .collect();
        let want = vec![
            ("a".to_string(), Some(1), None),
            ("b".to_string(), None, Some('x')),
            ("b/c".to_string(), Some(2), Some('y')),
            ("d".to_string(), Some(3), None),
            ("e".to_string(), None, Some('z')),
        ];
        assert_eq!(got, want);
    }
}
`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet
Keyboard
