// the reads knot-git does with gix on disk, done here over objects pulled from
// artifacts on demand. every algorithm runs the same gix crate code knot-git
// runs (traverse, revision, diff, object parsing), so results match by
// construction rather than by reimplementation.

use std::collections::{HashMap, HashSet};
use std::ops::ControlFlow;
use std::rc::Rc;

use gix_hash::ObjectId;
use gix_object::{Kind, TreeRefIter};
use knot_gitcore::{
    BinaryBudget, BinaryDiff, BranchInfo, Commit, CommitRange, CoreError, EntryKind, FilePatch,
    LastCommit, LogLimit, LogSkip, PatchBody, PatchRange, PatchStatus, PathEntry, Side, SizedEntry,
    Submodule, TagInfo, is_hidden, is_public_ref,
};
use knot_types::{
    ChangedFiles, ChangedFilesBudget, LanguageBytes, LanguageName, ObjectFormat, Oid, RefName,
    RepoPath, TagName,
};

use crate::clock::Deadline;
use crate::error::KnotError;
use crate::odb::{ObjectSource, Objects, Odb};

const MAX_TREE_DEPTH: usize = 1024;
const MAX_TAG_DEPTH: usize = 32;

// the refs of a repo as ls-refs reported them, symrefs already resolved
#[derive(Debug, Clone, Default)]
pub struct RefSnapshot {
    pub head_symref: Option<RefName>,
    pub head_target: Option<Oid>,
    pub refs: Vec<(RefName, Oid)>,
}

impl RefSnapshot {
    pub fn find(&self, name: &str) -> Option<Oid> {
        self.refs
            .iter()
            .find(|(candidate, _)| candidate.as_str() == name)
            .map(|(_, target)| *target)
    }
}

pub struct Repo<S> {
    pub odb: Odb<S>,
    pub refs: RefSnapshot,
    pub format: ObjectFormat,
}

fn load(objects: &Objects, id: Oid) -> Result<(Kind, Rc<[u8]>), CoreError> {
    objects
        .get(&id.object_id())
        .ok_or(CoreError::ObjectNotFound(id))
}

fn backend(error: impl std::fmt::Display) -> CoreError {
    CoreError::Backend(error.to_string())
}

fn peel_tags(objects: &Objects, id: Oid) -> Result<(Oid, Kind), CoreError> {
    let mut current = id;
    for _ in 0..=MAX_TAG_DEPTH {
        let (kind, data) = load(objects, current).map_err(backend)?;
        if kind != Kind::Tag {
            return Ok((current, kind));
        }
        current = Oid::from(
            gix_object::TagRefIter::from_bytes(&data, current.object_id().kind())
                .target_id()
                .map_err(backend)?,
        );
    }
    Err(CoreError::DepthExceeded("annotated tag chain"))
}

fn peel_to_commit(objects: &Objects, id: Oid) -> Result<Oid, CoreError> {
    match peel_tags(objects, id)? {
        (commit, Kind::Commit) => Ok(commit),
        _ => Err(CoreError::ObjectType {
            oid: id,
            expected: "commit",
        }),
    }
}

fn commit_tree(objects: &Objects, commit: Oid) -> Result<Oid, CoreError> {
    let (kind, data) = load(objects, commit)?;
    if kind != Kind::Commit {
        return Err(CoreError::ObjectType {
            oid: commit,
            expected: "commit",
        });
    }
    knot_gitcore::commit_tree(commit, &data)
}

fn find_commit(objects: &Objects, oid: Oid) -> Result<Commit, CoreError> {
    let (kind, data) = load(objects, oid)?;
    if kind != Kind::Commit {
        return Err(CoreError::ObjectType {
            oid,
            expected: "commit",
        });
    }
    knot_gitcore::parse_commit(oid, &data)
}

fn tree_bytes(objects: &Objects, tree: Oid) -> Result<Rc<[u8]>, CoreError> {
    let (kind, data) = load(objects, tree).map_err(backend)?;
    match kind {
        Kind::Tree => Ok(data),
        _ => Err(backend(format!("object {tree} isn't a tree"))),
    }
}

fn empty_tree(format: ObjectFormat) -> Oid {
    Oid::from(ObjectId::empty_tree(format.kind()))
}

fn tree_or_empty(objects: &Objects, tree: Oid, format: ObjectFormat) -> Result<Rc<[u8]>, CoreError> {
    match tree == empty_tree(format) {
        true => Ok(Rc::from(Vec::new())),
        false => tree_bytes(objects, tree),
    }
}

fn entry_at(objects: &Objects, commit: Oid, path: &RepoPath) -> Result<Option<PathEntry>, CoreError> {
    let root = commit_tree(objects, commit)?;
    let data = tree_bytes(objects, root)?;
    let mut buffer = Vec::new();
    let found = TreeRefIter::from_bytes(&data, root.object_id().kind())
        .lookup_entry_by_path(objects, &mut buffer, path.as_str())
        .map_err(backend)?;
    Ok(found.map(|entry| PathEntry {
        oid: Oid::from(entry.oid),
        kind: entry.mode.kind().into(),
    }))
}

fn dir_tree_id(objects: &Objects, commit: Oid, dir: Option<&RepoPath>) -> Result<Option<Oid>, CoreError> {
    let root = commit_tree(objects, commit)?;
    let Some(dir) = dir else {
        return Ok(Some(root));
    };
    let data = tree_bytes(objects, root)?;
    let mut buffer = Vec::new();
    match TreeRefIter::from_bytes(&data, root.object_id().kind())
        .lookup_entry_by_path(objects, &mut buffer, dir.as_str())
        .map_err(backend)?
    {
        Some(entry) if entry.mode.is_tree() => Ok(Some(Oid::from(entry.oid))),
        _ => Ok(None),
    }
}

fn entry_oids_of_tree(objects: &Objects, tree: Oid) -> Result<HashMap<String, Oid>, CoreError> {
    let data = tree_bytes(objects, tree)?;
    Ok(knot_gitcore::parse_tree(tree, &data)?
        .entries
        .into_iter()
        .map(|entry| (entry.name, entry.oid))
        .collect())
}

// gix's rev walk as knot-git configures it: newest commit time first, all parents
fn walk(objects: &Objects, start: Oid, hidden: &[Oid]) -> Result<Vec<Oid>, CoreError> {
    let hidden: Vec<Oid> = hidden
        .iter()
        .copied()
        .filter(|oid| objects.has(&oid.object_id()))
        .collect();
    let walk = gix_traverse::commit::Simple::filtered(Some(start.object_id()), objects, |_| true)
        .sorting(gix_traverse::commit::simple::Sorting::ByCommitTime(
            gix_traverse::commit::simple::CommitTimeOrder::NewestFirst,
        ))
        .map_err(|error| CoreError::RevWalk(error.to_string()))?
        .parents(gix_traverse::commit::Parents::All)
        .commit_graph(None)
        .hide(hidden.iter().map(|oid| oid.object_id()))
        .map_err(|error| CoreError::RevWalk(error.to_string()))?;
    walk.map(|info| {
        info.map(|info| Oid::from(info.id))
            .map_err(|error| CoreError::RevWalk(error.to_string()))
    })
    .collect()
}

fn merge_base(objects: &Objects, one: Oid, two: Oid) -> Result<Option<Oid>, CoreError> {
    let mut graph = gix_revwalk::Graph::new(objects, None);
    match gix_revision::merge_base(one.object_id(), &[two.object_id()], &mut graph) {
        Ok(Some(bases)) => Ok(Some(Oid::from(*bases.first()))),
        Ok(None) => Ok(None),
        Err(error) => Err(backend(error)),
    }
}

fn subject_line(message: &str) -> String {
    knot_gitcore::subject_line(message)
}

impl<S: ObjectSource> Repo<S> {
    pub fn object_format(&self) -> ObjectFormat {
        self.format
    }

    pub fn default_branch(&self) -> Option<RefName> {
        self.refs.head_symref.clone()
    }

    pub fn head(&self) -> Option<(RefName, Oid)> {
        Some((self.default_branch()?, self.refs.head_target?))
    }

    pub fn references(&self) -> &[(RefName, Oid)] {
        &self.refs.refs
    }

    pub fn find_ref(&self, name: &RefName) -> Option<Oid> {
        self.refs.find(name.as_str())
    }

    fn public_tips(&self) -> Vec<Oid> {
        self.refs
            .refs
            .iter()
            .filter(|(name, _)| is_public_ref(name))
            .map(|(_, target)| *target)
            .collect()
    }

    pub fn hidden_ref_commit_name(&self, spec: &str) -> Option<Oid> {
        let name = match spec.starts_with("refs/") {
            true => RefName::new(spec.to_string()),
            false => RefName::new(format!("refs/{spec}")),
        }
        .ok()
        .filter(is_hidden)?;
        self.find_ref(&name)
    }

    pub async fn hidden_ref_commit(&self, spec: &str) -> Option<Oid> {
        let target = self.hidden_ref_commit_name(spec)?;
        self.peel_to_commit(target).await.ok()
    }

    // what gix rev_parse_single resolves for the spec shapes knot callers send:
    // full object ids, ref names with git's dwim order, HEAD, and ~n/^n suffixes
    pub async fn resolve_revision(&self, spec: &str) -> Result<Option<Oid>, KnotError> {
        if spec.is_empty() || spec.contains('\0') {
            return Ok(None);
        }
        let (base, suffix) = split_suffix(spec);
        let Some(mut current) = self.resolve_base(base).await? else {
            return Ok(None);
        };
        for step in suffix {
            let next = self
                .odb
                .settle(|objects| -> Result<Option<Oid>, CoreError> {
                    match step {
                        Step::Ancestor(generations) => {
                            let mut at = peel_to_commit(objects, current)?;
                            for _ in 0..generations {
                                let commit = find_commit(objects, at)?;
                                match commit.parents.first() {
                                    Some(parent) => at = *parent,
                                    None => return Ok(None),
                                }
                            }
                            Ok(Some(at))
                        }
                        Step::Parent(0) => peel_to_commit(objects, current).map(Some),
                        Step::Parent(nth) => {
                            let commit = find_commit(objects, peel_to_commit(objects, current)?)?;
                            Ok(commit.parents.get(nth - 1).copied())
                        }
                        Step::PeelCommit => peel_to_commit(objects, current).map(Some),
                        Step::PeelAny => peel_tags(objects, current).map(|(oid, _)| Some(oid)),
                    }
                })
                .await?;
            match next {
                Ok(Some(oid)) => current = oid,
                _ => return Ok(None),
            }
        }
        Ok(Some(current))
    }

    async fn resolve_base(&self, base: &str) -> Result<Option<Oid>, KnotError> {
        let hex_len = self.format.null_oid().to_hex().len();
        if base.len() == hex_len
            && let Ok(oid) = Oid::from_hex(base)
            && self.odb.object(oid.object_id()).await?.is_some()
        {
            return Ok(Some(oid));
        }
        if base == "HEAD" || base == "@" {
            return Ok(self.refs.head_target);
        }
        let candidates = [
            base.to_string(),
            format!("refs/{base}"),
            format!("refs/tags/{base}"),
            format!("refs/heads/{base}"),
            format!("refs/remotes/{base}"),
            format!("refs/remotes/{base}/HEAD"),
        ];
        Ok(candidates.iter().find_map(|name| self.refs.find(name)))
    }

    pub async fn peel_to_commit(&self, oid: Oid) -> Result<Oid, KnotError> {
        Ok(self.odb.settle(|objects| peel_to_commit(objects, oid)).await??)
    }

    pub async fn peel_to_tree(&self, oid: Oid) -> Result<Oid, KnotError> {
        Ok(self
            .odb
            .settle(|objects| -> Result<Oid, CoreError> {
                let (peeled, kind) = peel_tags(objects, oid)?;
                match kind {
                    Kind::Tree => Ok(peeled),
                    Kind::Commit => commit_tree(objects, peeled),
                    _ => Err(backend(format!("object {oid} doesn't peel to a tree"))),
                }
            })
            .await??)
    }

    pub async fn find_commit(&self, oid: Oid) -> Result<Commit, KnotError> {
        Ok(self.odb.settle(|objects| find_commit(objects, oid)).await??)
    }

    pub async fn merge_base(&self, one: Oid, two: Oid) -> Result<Option<Oid>, KnotError> {
        Ok(self.odb.settle(|objects| merge_base(objects, one, two)).await??)
    }

    pub async fn reachable_from_public(&self, target: Oid) -> Result<bool, KnotError> {
        let tips = self.public_tips();
        let peeled = self
            .odb
            .settle(|objects| {
                tips.iter()
                    .filter_map(|tip| peel_to_commit(objects, *tip).ok())
                    .collect::<Vec<_>>()
            })
            .await?;
        if peeled.contains(&target) {
            return Ok(true);
        }
        for tip in peeled {
            if self.merge_base(target, tip).await? == Some(target) {
                return Ok(true);
            }
        }
        Ok(false)
    }

    pub async fn commits_between(&self, range: CommitRange, limit: LogLimit) -> Result<Vec<Oid>, KnotError> {
        let walked = self
            .odb
            .settle(|objects| walk(objects, range.head, &[range.base]))
            .await??;
        Ok(walked.into_iter().take(limit.get()).collect())
    }

    pub async fn log_window(
        &self,
        start: Oid,
        skip: LogSkip,
        limit: LogLimit,
    ) -> Result<(Vec<Commit>, usize), KnotError> {
        let walked = self.odb.settle(|objects| walk(objects, start, &[])).await??;
        let total = walked.len();
        let window: Vec<Oid> = walked.into_iter().skip(skip.get()).take(limit.get()).collect();
        let commits = self
            .odb
            .settle(|objects| {
                window
                    .iter()
                    .map(|oid| find_commit(objects, *oid))
                    .collect::<Result<Vec<_>, _>>()
            })
            .await??;
        Ok((commits, total))
    }

    // commits reachable from `start` and from none of `hidden`, as knot-git's rev_walk
    pub async fn walk_hiding(&self, start: Oid, hidden: &[Oid]) -> Result<Vec<Oid>, KnotError> {
        Ok(self.odb.settle(|objects| walk(objects, start, hidden)).await??)
    }

    // the file paths a range touches, as knot-git's changed_paths lists them
    pub async fn changed_paths(&self, range: PatchRange) -> Result<ChangedFiles, KnotError> {
        let sides = self.changed_sides(range).await?;
        let mut budget = ChangedFilesBudget::new();
        for (_, path, old, new) in sides {
            let is_tree = |side: &Side| {
                matches!(
                    side,
                    Side::Present {
                        kind: EntryKind::Tree,
                        ..
                    }
                )
            };
            if is_tree(&old) || is_tree(&new) {
                continue;
            }
            let flow = match RepoPath::new(path) {
                Ok(path) => budget.admit(path),
                Err(_) => budget.truncate(),
            };
            if flow.is_break() {
                break;
            }
        }
        Ok(budget.finish())
    }

    pub async fn entry_at(&self, commit: Oid, path: &RepoPath) -> Result<Option<PathEntry>, KnotError> {
        Ok(self.odb.settle(|objects| entry_at(objects, commit, path)).await??)
    }

    pub async fn read_blob(&self, oid: Oid) -> Result<Vec<u8>, KnotError> {
        match self.odb.object(oid.object_id()).await? {
            Some((Kind::Blob, data)) => Ok(data.to_vec()),
            Some(_) => Err(CoreError::ObjectType {
                oid,
                expected: "blob",
            }
            .into()),
            None => Err(CoreError::ObjectNotFound(oid).into()),
        }
    }

    pub async fn blob_size(&self, oid: Oid) -> Result<u64, KnotError> {
        self.odb
            .blob_size(oid.object_id())
            .await?
            .ok_or_else(|| CoreError::ObjectNotFound(oid).into())
    }

    async fn sized(&self, tree: Oid) -> Result<Vec<SizedEntry>, KnotError> {
        let entries = self
            .odb
            .settle(|objects| -> Result<_, CoreError> {
                let data = tree_bytes(objects, tree)?;
                knot_gitcore::parse_tree(tree, &data)
            })
            .await??
            .entries;
        let blobs: Vec<ObjectId> = entries
            .iter()
            .filter(|entry| {
                matches!(
                    entry.kind,
                    EntryKind::Blob | EntryKind::BlobExecutable | EntryKind::Link
                )
            })
            .map(|entry| entry.oid.object_id())
            .collect();
        let sizes = self.odb.blob_sizes(blobs).await?;
        Ok(entries
            .into_iter()
            .map(|entry| {
                let size = match entry.kind {
                    EntryKind::Blob | EntryKind::BlobExecutable | EntryKind::Link => sizes
                        .get(&entry.oid.object_id())
                        .copied()
                        .flatten()
                        .unwrap_or(0),
                    EntryKind::Tree | EntryKind::Commit => 0,
                };
                SizedEntry {
                    name: entry.name,
                    oid: entry.oid,
                    kind: entry.kind,
                    size,
                }
            })
            .collect())
    }

    pub async fn tree_entries_at(
        &self,
        commit: Oid,
        path: Option<&RepoPath>,
    ) -> Result<Option<Vec<SizedEntry>>, KnotError> {
        let Some(path) = path else {
            let root = self.odb.settle(|objects| commit_tree(objects, commit)).await??;
            return self.sized(root).await.map(Some);
        };
        match self.entry_at(commit, path).await? {
            None => Ok(None),
            Some(entry) if entry.kind == EntryKind::Tree => self.sized(entry.oid).await.map(Some),
            Some(entry) if entry.kind == EntryKind::Commit => Ok(None),
            Some(_) => Ok(Some(Vec::new())),
        }
    }

    // knot-git's last-commit attribution, step for step
    pub async fn last_commits(
        &self,
        start: Oid,
        dir: Option<&RepoPath>,
        names: &[String],
        deadline: Deadline,
    ) -> Result<HashMap<String, LastCommit>, KnotError> {
        let walked = self.odb.settle(|objects| walk(objects, start, &[])).await??;
        let mut pending: HashSet<&str> = names.iter().map(String::as_str).collect();
        let mut attributed = HashMap::new();
        let mut dir_trees: HashMap<Oid, Option<Oid>> = HashMap::new();
        for oid in walked {
            if pending.is_empty() || deadline.passed() {
                break;
            }
            let commit = self.find_commit(oid).await?;
            if commit.parents.len() > 1 {
                continue;
            }
            let mut dir_tree_of = async |commit: Oid| -> Result<Option<Oid>, KnotError> {
                if let Some(known) = dir_trees.get(&commit) {
                    return Ok(*known);
                }
                let id = self
                    .odb
                    .settle(|objects| dir_tree_id(objects, commit, dir))
                    .await??;
                dir_trees.insert(commit, id);
                Ok(id)
            };
            let here_tree = dir_tree_of(oid).await?;
            let parent_tree = match commit.parents.first().copied() {
                Some(parent) => dir_tree_of(parent).await?,
                None => None,
            };
            if here_tree == parent_tree || here_tree.is_none() {
                continue;
            }
            let here_id = here_tree.expect("checked above");
            let (here, parent) = self
                .odb
                .settle(|objects| -> Result<_, CoreError> {
                    let here = entry_oids_of_tree(objects, here_id)?;
                    let parent = parent_tree
                        .map(|tree| entry_oids_of_tree(objects, tree))
                        .transpose()?
                        .unwrap_or_default();
                    Ok((here, parent))
                })
                .await??;
            let changed: Vec<String> = pending
                .iter()
                .filter(|name| here.contains_key(**name) && here.get(**name) != parent.get(**name))
                .map(|name| name.to_string())
                .collect();
            changed.iter().for_each(|name| {
                pending.remove(name.as_str());
            });
            changed.into_iter().for_each(|name| {
                attributed.insert(
                    name,
                    LastCommit {
                        id: oid,
                        subject: subject_line(&commit.message),
                        time: commit.author.time,
                    },
                );
            });
        }
        Ok(attributed)
    }

    pub async fn submodules(&self, commit: Oid) -> Result<Vec<Submodule>, KnotError> {
        let gitmodules = RepoPath::new(".gitmodules").expect("literal path is well-formed");
        let Some(entry) = self.entry_at(commit, &gitmodules).await? else {
            return Ok(Vec::new());
        };
        if !entry.kind.is_file() {
            return Ok(Vec::new());
        }
        let raw = self.read_blob(entry.oid).await?;
        Ok(knot_gitcore::gitmodules(&raw))
    }

    pub async fn branch_list(&self) -> Result<Vec<BranchInfo>, KnotError> {
        let branches: Vec<_> = self
            .refs
            .refs
            .iter()
            .filter_map(|(name, target)| name.branch_name().map(|branch| (branch, *target)))
            .collect();
        let mut out = Vec::with_capacity(branches.len());
        for (name, target) in branches {
            let (kind, data) = self
                .odb
                .object(target.object_id())
                .await?
                .ok_or_else(|| backend(format!("object {target} not found")))?;
            out.push(BranchInfo {
                name,
                tip: knot_gitcore::branch_tip(target, kind.into(), &data)?,
            });
        }
        Ok(out)
    }

    pub async fn tag_list(&self) -> Result<Vec<TagInfo>, KnotError> {
        let tags: Vec<(TagName, Oid)> = self
            .refs
            .refs
            .iter()
            .filter_map(|(name, target)| name.tag_name().map(|tag| (tag, *target)))
            .collect();
        let mut out = Vec::with_capacity(tags.len());
        for (name, target) in tags {
            let (kind, data) = self
                .odb
                .object(target.object_id())
                .await?
                .ok_or_else(|| backend(format!("object {target} not found")))?;
            out.push(knot_gitcore::tag_info(name, target, kind.into(), &data)?);
        }
        Ok(out)
    }

    async fn side_size(&self, side: &Side) -> Result<Option<u64>, KnotError> {
        let blob = match knot_gitcore::needs_blob(side) {
            Some(oid) => Some(self.blob_size(oid).await?),
            None => None,
        };
        Ok(knot_gitcore::side_size(side, blob))
    }

    async fn side_content(&self, side: &Side) -> Result<Vec<u8>, KnotError> {
        match knot_gitcore::needs_blob(side) {
            Some(oid) => self.read_blob(oid).await,
            None => Ok(knot_gitcore::synthesized_content(side)),
        }
    }

    // gix's tree diff with rename tracking off, as knot-git runs it
    async fn changed_sides(&self, range: PatchRange) -> Result<Vec<(PatchStatus, String, Side, Side)>, KnotError> {
        let format = self.format;
        let records = self
            .odb
            .settle(|objects| -> Result<_, CoreError> {
                let new_tree = commit_tree(objects, peel_to_commit(objects, range.head)?)?;
                let old_tree = match range.base {
                    Some(base) => commit_tree(objects, peel_to_commit(objects, base)?)?,
                    None => empty_tree(format),
                };
                let old = tree_or_empty(objects, old_tree, format)?;
                let new = tree_or_empty(objects, new_tree, format)?;
                let kind = format.kind();
                let mut recorder = gix_diff::tree::Recorder::default()
                    .track_location(Some(gix_diff::tree::recorder::Location::Path));
                gix_diff::tree(
                    TreeRefIter::from_bytes(&old, kind),
                    TreeRefIter::from_bytes(&new, kind),
                    &mut gix_diff::tree::State::default(),
                    objects,
                    &mut recorder,
                )
                .map_err(backend)?;
                Ok(recorder.records)
            })
            .await??;
        use gix_diff::tree::recorder::Change;
        Ok(records
            .into_iter()
            .map(|change| match change {
                Change::Addition {
                    entry_mode,
                    oid,
                    path,
                    ..
                } => (
                    PatchStatus::Added,
                    path.to_string(),
                    Side::Absent,
                    Side::Present {
                        oid: Oid::from(oid),
                        kind: entry_mode.kind().into(),
                    },
                ),
                Change::Deletion {
                    entry_mode,
                    oid,
                    path,
                    ..
                } => (
                    PatchStatus::Deleted,
                    path.to_string(),
                    Side::Present {
                        oid: Oid::from(oid),
                        kind: entry_mode.kind().into(),
                    },
                    Side::Absent,
                ),
                Change::Modification {
                    previous_entry_mode,
                    previous_oid,
                    entry_mode,
                    oid,
                    path,
                } => (
                    PatchStatus::Modified,
                    path.to_string(),
                    Side::Present {
                        oid: Oid::from(previous_oid),
                        kind: previous_entry_mode.kind().into(),
                    },
                    Side::Present {
                        oid: Oid::from(oid),
                        kind: entry_mode.kind().into(),
                    },
                ),
            })
            .collect())
    }

    pub async fn commit_patches(
        &self,
        range: PatchRange,
        budget: &mut BinaryBudget,
    ) -> Result<Vec<FilePatch>, KnotError> {
        let sides = self.changed_sides(range).await?;
        let absent = self.format.null_oid();
        let mut patches = Vec::new();
        for (status, path, old, new) in sides {
            let is_tree = |side: &Side| {
                matches!(
                    side,
                    Side::Present {
                        kind: EntryKind::Tree,
                        ..
                    }
                )
            };
            if is_tree(&old) || is_tree(&new) {
                continue;
            }
            let path = RepoPath::new(path).map_err(|error| CoreError::Decode(error.to_string()))?;
            let past = knot_gitcore::past_diff_budget(
                self.side_size(&old).await?,
                self.side_size(&new).await?,
            );
            let body = match past {
                Some(sizes) => PatchBody::Binary(BinaryDiff::Omitted(sizes)),
                None => {
                    let old_content = self.side_content(&old).await?;
                    let new_content = self.side_content(&new).await?;
                    knot_gitcore::patch_body(&old, &new, &old_content, &new_content, budget)?
                }
            };
            patches.push(knot_gitcore::file_patch(status, path, &old, &new, absent, body));
        }
        Ok(patches)
    }

    // knot-langs' walk, with its classification
    pub async fn languages(
        &self,
        commit: Oid,
        deadline: Deadline,
    ) -> Result<HashMap<LanguageName, LanguageBytes>, KnotError> {
        let mut sizes = HashMap::new();
        let root = self.peel_to_tree(commit).await?;
        let _walked = self
            .walk_languages(root, String::new(), 0, deadline, &mut sizes)
            .await?;
        Ok(sizes)
    }

    fn walk_languages<'a>(
        &'a self,
        tree: Oid,
        dir: String,
        depth: usize,
        deadline: Deadline,
        sizes: &'a mut HashMap<LanguageName, LanguageBytes>,
    ) -> futures::future::LocalBoxFuture<'a, Result<ControlFlow<()>, KnotError>> {
        Box::pin(async move {
            if depth > MAX_TREE_DEPTH || deadline.passed() {
                return Ok(ControlFlow::Break(()));
            }
            let entries = self.sized(tree).await?;
            for entry in entries {
                if deadline.passed() {
                    return Ok(ControlFlow::Break(()));
                }
                let path = match dir.is_empty() {
                    true => entry.name.clone(),
                    false => format!("{dir}/{}", entry.name),
                };
                match entry.kind {
                    EntryKind::Tree => {
                        if knot_langs::classify::descends(&path)
                            && self
                                .walk_languages(entry.oid, path, depth + 1, deadline, sizes)
                                .await?
                                .is_break()
                        {
                            return Ok(ControlFlow::Break(()));
                        }
                    }
                    EntryKind::Blob | EntryKind::BlobExecutable => {
                        if knot_langs::classify::counts(&path) {
                            let content = match knot_langs::classify::reads_content(entry.size) {
                                true => {
                                    let blob = self.read_blob(entry.oid).await?;
                                    blob[..blob.len().min(knot_langs::classify::READ_LIMIT)].to_vec()
                                }
                                false => Vec::new(),
                            };
                            knot_langs::classify::tally(&path, entry.size, &content, sizes);
                        }
                    }
                    EntryKind::Link | EntryKind::Commit => {}
                }
            }
            Ok(ControlFlow::Continue(()))
        })
    }
}

enum Step {
    Ancestor(usize),
    Parent(usize),
    PeelCommit,
    PeelAny,
}

// "main~2^2" -> ("main", [~2, ^2])
fn split_suffix(spec: &str) -> (&str, Vec<Step>) {
    let cut = spec.find(['~', '^']).unwrap_or(spec.len());
    let (base, mut rest) = spec.split_at(cut);
    let mut steps = Vec::new();
    while let Some(op) = rest.chars().next() {
        rest = &rest[1..];
        if op == '^' && rest.starts_with('{') {
            let end = rest.find('}').unwrap_or(rest.len());
            steps.push(match &rest[1..end] {
                "commit" => Step::PeelCommit,
                _ => Step::PeelAny,
            });
            rest = rest.get(end + 1..).unwrap_or("");
            continue;
        }
        let digits = rest.chars().take_while(char::is_ascii_digit).count();
        let count = rest[..digits].parse::<usize>().ok();
        rest = &rest[digits..];
        steps.push(match op {
            '~' => Step::Ancestor(count.unwrap_or(1)),
            _ => Step::Parent(count.unwrap_or(1)),
        });
    }
    (base, steps)
}