weavatrix-git 0.2.0

use std::{
    cmp::Ordering,
    collections::{BinaryHeap, HashSet},
};

use crate::{Commit, GitError, ObjectId, Repository, Result};

#[derive(Clone, Copy, Debug)]
pub struct HistoryOptions {
    pub max_commits: usize,
    pub first_parent: bool,
    pub since: Option<i64>,
    pub until: Option<i64>,
}

impl Default for HistoryOptions {
    fn default() -> Self {
        Self {
            max_commits: 10_000,
            first_parent: false,
            since: None,
            until: None,
        }
    }
}

#[derive(Clone, Debug)]
pub struct HistoryRecord {
    pub id: ObjectId,
    pub commit: Commit,
}

#[derive(Clone, Debug, Eq, PartialEq)]
struct Pending {
    time: i64,
    sequence: u64,
    commit: Commit,
}

#[derive(Clone, Debug, Eq, PartialEq)]
struct PendingId {
    time: i64,
    sequence: u64,
    id: ObjectId,
    parents: Vec<ObjectId>,
}

impl Ord for Pending {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.time, self.sequence).cmp(&(other.time, other.sequence))
    }
}

impl PartialOrd for Pending {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for PendingId {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.time, self.sequence).cmp(&(other.time, other.sequence))
    }
}

impl PartialOrd for PendingId {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

pub(crate) fn walk(
    repository: &Repository,
    start: ObjectId,
    options: HistoryOptions,
) -> Result<Vec<HistoryRecord>> {
    let cap = options
        .max_commits
        .min(repository.limits().max_history_commits);
    if options.max_commits > repository.limits().max_history_commits {
        return Err(GitError::LimitExceeded {
            resource: "history commits",
            limit: repository.limits().max_history_commits,
        });
    }
    let first = repository.commit(start)?;
    let mut pending = BinaryHeap::from([Pending {
        time: commit_time(&first),
        sequence: 0,
        commit: first,
    }]);
    let mut scheduled = HashSet::from([start]);
    let mut result = Vec::with_capacity(cap.min(1024));
    let mut sequence = 1;
    while let Some(item) = pending.pop() {
        if result.len() == cap {
            break;
        }
        let commit = item.commit;
        let parents = if options.first_parent {
            commit.parents.get(..1).unwrap_or(&[])
        } else {
            &commit.parents
        };
        for parent in parents {
            if scheduled.insert(*parent) {
                let parent_commit = repository.commit(*parent)?;
                pending.push(Pending {
                    time: commit_time(&parent_commit),
                    sequence,
                    commit: parent_commit,
                });
                sequence += 1;
            }
        }
        let in_range = options.since.is_none_or(|time| item.time >= time)
            && options.until.is_none_or(|time| item.time <= time);
        if in_range {
            result.push(HistoryRecord {
                id: commit.id,
                commit,
            });
        }
    }
    Ok(result)
}

pub(crate) fn walk_ids(
    repository: &Repository,
    start: ObjectId,
    options: HistoryOptions,
) -> Result<Vec<ObjectId>> {
    validate_limit(repository, options)?;
    if options.first_parent {
        return walk_first_parent_ids(repository, start, options);
    }
    let first = load_id(repository, start, 0)?;
    let mut pending = BinaryHeap::from([first]);
    let mut scheduled = HashSet::from([start]);
    let mut result = Vec::with_capacity(options.max_commits.min(1024));
    let mut sequence = 1;
    while let Some(item) = pending.pop() {
        if result.len() == options.max_commits {
            break;
        }
        let parents = if options.first_parent {
            item.parents.get(..1).unwrap_or(&[])
        } else {
            &item.parents
        };
        for parent in parents {
            if scheduled.insert(*parent) {
                pending.push(load_id(repository, *parent, sequence)?);
                sequence += 1;
            }
        }
        if options.since.is_none_or(|time| item.time >= time)
            && options.until.is_none_or(|time| item.time <= time)
        {
            result.push(item.id);
        }
    }
    Ok(result)
}

fn walk_first_parent_ids(
    repository: &Repository,
    start: ObjectId,
    options: HistoryOptions,
) -> Result<Vec<ObjectId>> {
    if let Some(ids) = repository.graph_first_parent_ids(start, options)? {
        return Ok(ids);
    }
    let mut current = Some(start);
    let mut result = Vec::with_capacity(options.max_commits.min(1024));
    let mut traversed = 0;
    while let Some(id) = current {
        if result.len() == options.max_commits {
            break;
        }
        if traversed == repository.limits().max_history_commits {
            return Err(GitError::LimitExceeded {
                resource: "history traversal",
                limit: repository.limits().max_history_commits,
            });
        }
        traversed += 1;
        let commit = repository.commit_metadata(id)?;
        current = commit.parents.first().copied();
        if options
            .since
            .is_none_or(|time| commit.committer_time >= time)
            && options
                .until
                .is_none_or(|time| commit.committer_time <= time)
        {
            result.push(commit.id);
        }
    }
    Ok(result)
}

fn load_id(repository: &Repository, id: ObjectId, sequence: u64) -> Result<PendingId> {
    let commit = repository.commit_metadata(id)?;
    Ok(PendingId {
        time: commit.committer_time,
        sequence,
        id: commit.id,
        parents: commit.parents,
    })
}

fn validate_limit(repository: &Repository, options: HistoryOptions) -> Result<()> {
    if options.max_commits > repository.limits().max_history_commits {
        return Err(GitError::LimitExceeded {
            resource: "history commits",
            limit: repository.limits().max_history_commits,
        });
    }
    Ok(())
}

fn commit_time(commit: &Commit) -> i64 {
    commit
        .committer
        .as_ref()
        .or(commit.author.as_ref())
        .map_or(0, |signature| signature.timestamp)
}