use std::{
    borrow::Cow,
    fmt::{Display, Formatter},
};

use git_object::bstr::BStr;

#[derive(PartialEq, Eq, Debug, Hash, Ord, PartialOrd, Clone)]
pub struct Outcome<'a> {
    pub name: Cow<'a, BStr>,
    pub id: git_hash::ObjectId,
    pub depth: u32,
}

impl<'a> Outcome<'a> {
    pub fn into_format(self, hex_len: usize) -> Format<'a> {
        Format {
            name: self.name,
            id: self.id,
            hex_len,
            depth: self.depth,
            long: false,
            dirty_suffix: None,
        }
    }
}

#[derive(PartialEq, Eq, Debug, Hash, Ord, PartialOrd, Clone)]
pub struct Format<'a> {
    pub name: Cow<'a, BStr>,
    pub id: git_hash::ObjectId,
    pub hex_len: usize,
    pub depth: u32,
    pub long: bool,
    pub dirty_suffix: Option<String>,
}

impl<'a> Format<'a> {
    pub fn is_exact_match(&self) -> bool {
        self.depth == 0
    }
    pub fn long(&mut self) -> &mut Self {
        self.long = true;
        self
    }
    pub fn short(&mut self) -> &mut Self {
        self.long = false;
        self
    }
}

impl<'a> Display for Format<'a> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        if !self.long && self.is_exact_match() {
            self.name.fmt(f)?;
        } else {
            write!(
                f,
                "{}-{}-g{}",
                self.name,
                self.depth,
                self.id.to_hex_with_len(self.hex_len)
            )?;
        }
        if let Some(suffix) = &self.dirty_suffix {
            write!(f, "-{}", suffix)?;
        }
        Ok(())
    }
}

pub(crate) mod function {
    use std::{
        borrow::Cow,
        collections::{hash_map, HashMap, VecDeque},
        iter::FromIterator,
    };

    use git_hash::{oid, ObjectId};
    use git_object::{bstr::BStr, CommitRefIter};

    use super::Outcome;

    #[allow(clippy::result_unit_err)]
    pub fn describe<'a, Find, E>(
        commit: &oid,
        mut find: Find,
        name_set: &HashMap<ObjectId, Cow<'a, BStr>>,
    ) -> Result<Option<Outcome<'a>>, E>
    where
        Find: for<'b> FnMut(&oid, &'b mut Vec<u8>) -> Result<CommitRefIter<'b>, E>,
        E: std::error::Error + Send + Sync + 'static,
    {
        if let Some(name) = name_set.get(commit) {
            return Ok(Some(Outcome {
                name: name.clone(),
                id: commit.to_owned(),
                depth: 0,
            }));
        }

        let mut buf = Vec::new();
        let mut parent_buf = Vec::new();
        let mut parents = Vec::new();

        let mut queue = VecDeque::from_iter(Some(commit.to_owned()));
        let mut candidates = Vec::new();
        let mut seen_commits = 0;
        let mut _gave_up_on_commit = None;
        let mut seen = hash_hasher::HashedMap::default();
        seen.insert(commit.to_owned(), 0u32);

        const MAX_CANDIDATES: usize = std::mem::size_of::<Flags>() * 8;
        while let Some(commit) = queue.pop_front() {
            seen_commits += 1;
            if let Some(name) = name_set.get(&commit) {
                if candidates.len() < MAX_CANDIDATES {
                    let identity_bit = 1 << candidates.len();
                    candidates.push(Candidate {
                        name: name.clone(),
                        commits_in_its_future: seen_commits - 1,
                        identity_bit,
                        order: candidates.len(),
                    });
                    *seen.get_mut(&commit).expect("inserted") |= identity_bit;
                } else {
                    _gave_up_on_commit = Some(commit);
                    break;
                }
            }

            let flags = seen[&commit];
            for candidate in candidates
                .iter_mut()
                .filter(|c| (flags & c.identity_bit) != c.identity_bit)
            {
                candidate.commits_in_its_future += 1;
            }

            let commit_iter = find(&commit, &mut buf)?;
            parents.clear();
            for token in commit_iter {
                match token {
                    Ok(git_object::commit::ref_iter::Token::Tree { .. }) => continue,
                    Ok(git_object::commit::ref_iter::Token::Parent { id: parent_id }) => {
                        match seen.entry(parent_id) {
                            hash_map::Entry::Vacant(entry) => {
                                let parent = find(&parent_id, &mut parent_buf)?;
                                // TODO: figure out if not having a date is a hard error.
                                let parent_commit_date = parent
                                    .committer()
                                    .map(|committer| committer.time.seconds_since_unix_epoch)
                                    .unwrap_or_default();

                                entry.insert(flags);
                                parents.push((parent_id, parent_commit_date));
                            }
                            hash_map::Entry::Occupied(mut entry) => {
                                *entry.get_mut() |= flags;
                            }
                        }
                    }
                    Ok(_unused_token) => break,
                    Err(_err) => todo!("return a decode error"),
                }
            }

            if !parents.is_empty() {
                parents.sort_by(|a, b| a.1.cmp(&b.1).reverse());
                seen.extend(parents.iter().map(|e| (e.0, flags)));
                queue.extend(parents.iter().map(|e| e.0));
            }
        }

        if candidates.is_empty() {
            return Ok(None);
        }

        candidates.sort_by(|a, b| {
            a.commits_in_its_future
                .cmp(&b.commits_in_its_future)
                .then_with(|| a.order.cmp(&b.order))
        });
        Ok(candidates.into_iter().next().map(|c| Outcome {
            name: c.name,
            id: commit.to_owned(),
            depth: c.commits_in_its_future,
        }))
    }

    type Flags = u32;

    #[derive(Debug)]
    struct Candidate<'a> {
        name: Cow<'a, BStr>,
        commits_in_its_future: Flags,
        /// A single bit identifying this candidate uniquely in a bitset
        identity_bit: Flags,
        /// The order at which we found the candidate, first one has order = 0
        order: usize,
    }
}