//! Working-copy snapshots, commits, and the change builder (spec §12.3).

use super::*;

#[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>,
}

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 fs_entries = self.walk_working_copy()?;
        self.build_from_entries(base, base_snapshot, reuse, &fs_entries)
    }

    /// 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> {
        // 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);
        // 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();
        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)?,
            }
        }
        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;
            }
            // A directory stays while anything under it exists or is out of scope.
            let still_needed = expected.kind == NodeKind::Dir
                && (fs_entries.keys().any(|p| p.starts_with(&format!("{path}/")))
                    || base_snapshot.files.keys().any(|p| p.starts_with(&format!("{path}/")) && !self.in_scope(p)));
            if !still_needed {
                b.remove_path(path, expected);
            }
        }
        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).
    pub fn snapshot(&self, command: &str) -> Result<SnapshotResult> {
        let _lock = self.lock_snapshot()?;
        let batch = self.store.begin_batch()?;
        let result = self.snapshot_locked(command);
        batch.finish()?;
        result
    }

    fn snapshot_locked(&self, command: &str) -> Result<SnapshotResult> {
        let (op_ref, op) = self.head_op()?;
        let (old_hash, old_wc) = self.working_copy()?;
        let base = self.load_state(&old_wc.deps)?;
        let base_snapshot = 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);
        // The last manifest lets unchanged opaque files go unread.
        let manifest = self.read_manifest()?.map(|(_, _, m)| m);
        let fs_entries = self.walk_working_copy_with(manifest.as_ref())?;
        let built = self.build_from_entries(&base, &base_snapshot, reuse, &fs_entries)?;

        let mut wc = Change {
            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 new_hash = wc.hash();
        let changed = new_hash != old_hash;
        if changed {
            self.store.put_change(&wc)?;
            let mut view = op.view.clone();
            view.workspaces.insert(self.workspace, new_hash);
            self.record_op(&[op_ref], &format!("{command}{SNAPSHOT_SUFFIX}"), view)?;
        }
        // The prompt compares against this without recording anything.
        self.write_manifest_entries(base_snapshot.is_conflicted(), !wc.tree_ops.is_empty() || !wc.edits.is_empty(), &fs_entries, &built.blobs)?;
        Ok(SnapshotResult { wc_hash: new_hash, wc, base, base_snapshot, statuses, changed, resolves, contributors })
    }

    /// 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> {
        let snap = self.snapshot("oxy commit")?;
        if snap.wc.tree_ops.is_empty() && snap.wc.edits.is_empty() {
            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");
        }
        // 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> = referenced_changes(&snap.wc, &snap.base);
        // 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 {
            change_id: snap.wc.change_id,
            deps: deps.into_iter().collect(),
            author: self.author(),
            hlc: Hlc::now(),
            message: message.trim_end().to_string(),
            tree_ops: snap.wc.tree_ops.clone(),
            edits: snap.wc.edits.clone(),
            kind: if snap.resolves { ChangeKind::Resolution } else { ChangeKind::Normal },
        };
        change.normalize();
        let hash = self.store_signed(&change)?;

        // 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);
        let mut st = self.load_state(&all)?;
        st.add(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);

        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)?;
        self.rewrite_manifest_flags(snap.base_snapshot.is_conflicted() && !snap.resolves, false)?;
        self.maybe_autopack()?;
        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)
    }
}

/// Builds the tree ops and edits of a working-copy change against a base.
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>,
}

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, f) in &base_snapshot.files {
            if f.kind == NodeKind::Dir {
                dir_nodes.insert(p.clone(), f.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() }
    }

    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 {
            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: &[u8]) -> Vec<u8> {
        if self.attrs.lookup(path).eol.is_some() { crate::attributes::normalize_eol(content) } else { content.to_vec() }
    }

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

    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);
            parent = match self.dir_nodes.get(&prefix) {
                Some(n) => *n,
                None => {
                    let node = self.reused_node(&prefix, NodeKind::Dir).unwrap_or_else(NodeId::random);
                    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.reused_node(path, e.kind).unwrap_or_else(NodeId::random);
        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: split_lines(&content).iter().map(|l| l.to_vec()).collect(),
            });
        }
        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(())
    }

    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);
        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 old = self.base.live_lines(&node);
                    let edits = text_edits(node, &old, &disk_text);
                    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 {
                    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: split_lines(&e.content).iter().map(|l| l.to_vec()).collect(),
                            });
                        }
                    } 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, .. } => {
                for r in atoms {
                    if !r.change.is_zero() {
                        out.insert(r.change);
                    }
                }
            }
            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 {
                    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;

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
}