#[cfg(test)]

#[macro_use]

mod tests_support;

#[cfg(test)]

mod tests;

use crate::utils::hg_path::HgPath;

use crate::utils::hg_path::HgPathBuf;

use crate::Revision;

use crate::NULL_REVISION;

use bytes_cast::{unaligned, BytesCast};

use im_rc::ordmap::Entry;

use im_rc::ordmap::OrdMap;

use im_rc::OrdSet;

use std::cmp::Ordering;

use std::collections::HashMap;

pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;

type PathToken = usize;

#[derive(Clone, Debug)]

struct CopySource {

    /// revision at which the copy information was added

    rev: Revision,

    /// the copy source, (Set to None in case of deletion of the associated

    /// key)

    path: Option<PathToken>,

    /// a set of previous `CopySource.rev` value directly or indirectly

    /// overwritten by this one.

    overwritten: OrdSet<Revision>,

}

impl CopySource {

    /// create a new CopySource

    ///

    /// Use this when no previous copy source existed.

    fn new(rev: Revision, path: Option<PathToken>) -> Self {

        Self {

            rev,

            path,

            overwritten: OrdSet::new(),

        }

    }

    /// create a new CopySource from merging two others

    ///

    /// Use this when merging two InternalPathCopies requires active merging of

    /// some entries.

    fn new_from_merge(rev: Revision, winner: &Self, loser: &Self) -> Self {

        let mut overwritten = OrdSet::new();

        overwritten.extend(winner.overwritten.iter().copied());

        overwritten.extend(loser.overwritten.iter().copied());

        overwritten.insert(winner.rev);

        overwritten.insert(loser.rev);

        Self {

            rev,

            path: winner.path,

            overwritten: overwritten,

        }

    }

    /// Update the value of a pre-existing CopySource

    ///

    /// Use this when recording copy information from  parent → child edges

    fn overwrite(&mut self, rev: Revision, path: Option<PathToken>) {

        self.overwritten.insert(self.rev);

        self.rev = rev;

        self.path = path;

    }

    /// Mark pre-existing copy information as "dropped" by a file deletion

    ///

    /// Use this when recording copy information from  parent → child edges

    fn mark_delete(&mut self, rev: Revision) {

        self.overwritten.insert(self.rev);

        self.rev = rev;

        self.path = None;

    }

    /// Mark pre-existing copy information as "dropped" by a file deletion

    ///

    /// Use this when recording copy information from  parent → child edges

    fn mark_delete_with_pair(&mut self, rev: Revision, other: &Self) {

        self.overwritten.insert(self.rev);

        if other.rev != rev {

            self.overwritten.insert(other.rev);

        }

        self.overwritten.extend(other.overwritten.iter().copied());

        self.rev = rev;

        self.path = None;

    }

    fn is_overwritten_by(&self, other: &Self) -> bool {

        other.overwritten.contains(&self.rev)

    }

}

// For the same "dest", content generated for a given revision will always be

// the same.

impl PartialEq for CopySource {

    fn eq(&self, other: &Self) -> bool {

        #[cfg(debug_assertions)]

        {

            if self.rev == other.rev {

                debug_assert!(self.path == other.path);

                debug_assert!(self.overwritten == other.overwritten);

            }

        }

        self.rev == other.rev

    }

}

/// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)

type InternalPathCopies = OrdMap<PathToken, CopySource>;

/// Represent active changes that affect the copy tracing.

enum Action<'a> {

    /// The parent ? children edge is removing a file

    ///

    /// (actually, this could be the edge from the other parent, but it does

    /// not matters)

    Removed(&'a HgPath),

    /// The parent ? children edge introduce copy information between (dest,

    /// source)

    CopiedFromP1(&'a HgPath, &'a HgPath),

    CopiedFromP2(&'a HgPath, &'a HgPath),

}

/// This express the possible "special" case we can get in a merge

///

/// See mercurial/metadata.py for details on these values.

#[derive(PartialEq)]

enum MergeCase {

    /// Merged: file had history on both side that needed to be merged

    Merged,

    /// Salvaged: file was candidate for deletion, but survived the merge

    Salvaged,

    /// Normal: Not one of the two cases above

    Normal,

}

const COPY_MASK: u8 = 3;

const P1_COPY: u8 = 2;

const P2_COPY: u8 = 3;

const ACTION_MASK: u8 = 28;

const REMOVED: u8 = 12;

const MERGED: u8 = 8;

const SALVAGED: u8 = 16;

#[derive(BytesCast)]

#[repr(C)]

struct ChangedFilesIndexEntry {

    flags: u8,

    /// Only the end position is stored. The start is at the end of the

    /// previous entry.

    destination_path_end_position: unaligned::U32Be,

    source_index_entry_position: unaligned::U32Be,

}

fn _static_assert_size_of() {

    let _ = std::mem::transmute::<ChangedFilesIndexEntry, [u8; 9]>;

}

/// Represents the files affected by a changeset.

///

/// This holds a subset of `mercurial.metadata.ChangingFiles` as we do not need

/// all the data categories tracked by it.

pub struct ChangedFiles<'a> {

    index: &'a [ChangedFilesIndexEntry],

    paths: &'a [u8],

}

impl<'a> ChangedFiles<'a> {

    pub fn new(data: &'a [u8]) -> Self {

        let (header, rest) = unaligned::U32Be::from_bytes(data).unwrap();

        let nb_index_entries = header.get() as usize;

        let (index, paths) =

            ChangedFilesIndexEntry::slice_from_bytes(rest, nb_index_entries)

                .unwrap();

        Self { index, paths }

    }

    pub fn new_empty() -> Self {

        ChangedFiles {

            index: &[],

            paths: &[],

        }

    }

    /// Internal function to return the filename of the entry at a given index

    fn path(&self, idx: usize) -> &HgPath {

        let start = if idx == 0 {

            0

        } else {

            self.index[idx - 1].destination_path_end_position.get() as usize

        };

        let end = self.index[idx].destination_path_end_position.get() as usize;

        HgPath::new(&self.paths[start..end])

    }

    /// Return an iterator over all the `Action` in this instance.

    fn iter_actions(&self) -> impl Iterator<Item = Action> {

        self.index.iter().enumerate().flat_map(move |(idx, entry)| {

            let path = self.path(idx);

            if (entry.flags & ACTION_MASK) == REMOVED {

                Some(Action::Removed(path))

            } else if (entry.flags & COPY_MASK) == P1_COPY {

                let source_idx =

                    entry.source_index_entry_position.get() as usize;

                Some(Action::CopiedFromP1(path, self.path(source_idx)))

            } else if (entry.flags & COPY_MASK) == P2_COPY {

                let source_idx =

                    entry.source_index_entry_position.get() as usize;

                Some(Action::CopiedFromP2(path, self.path(source_idx)))

            } else {

                None

            }

        })

    }

    /// return the MergeCase value associated with a filename

    fn get_merge_case(&self, path: &HgPath) -> MergeCase {

        if self.index.is_empty() {

            return MergeCase::Normal;

        }

        let mut low_part = 0;

        let mut high_part = self.index.len();

        while low_part < high_part {

            let cursor = (low_part + high_part - 1) / 2;

            match path.cmp(self.path(cursor)) {

                Ordering::Less => low_part = cursor + 1,

                Ordering::Greater => high_part = cursor,

                Ordering::Equal => {

                    return match self.index[cursor].flags & ACTION_MASK {

                        MERGED => MergeCase::Merged,

                        SALVAGED => MergeCase::Salvaged,

                        _ => MergeCase::Normal,

                    };

                }

            }

        }

        MergeCase::Normal

    }

}

/// A small "tokenizer" responsible of turning full HgPath into lighter

/// PathToken

///

/// Dealing with small object, like integer is much faster, so HgPath input are

/// turned into integer "PathToken" and converted back in the end.

#[derive(Clone, Debug, Default)]

struct TwoWayPathMap {

    token: HashMap<HgPathBuf, PathToken>,

    path: Vec<HgPathBuf>,

}

impl TwoWayPathMap {

    fn tokenize(&mut self, path: &HgPath) -> PathToken {

        match self.token.get(path) {

            Some(a) => *a,

            None => {

                let a = self.token.len();

                let buf = path.to_owned();

                self.path.push(buf.clone());

                self.token.insert(buf, a);

                a

            }

        }

    }

    fn untokenize(&self, token: PathToken) -> &HgPathBuf {

        assert!(token < self.path.len(), "Unknown token: {}", token);

        &self.path[token]

    }

}

/// Same as mercurial.copies._combine_changeset_copies, but in Rust.

pub struct CombineChangesetCopies {

    all_copies: HashMap<Revision, InternalPathCopies>,

    path_map: TwoWayPathMap,

    children_count: HashMap<Revision, usize>,

}

impl CombineChangesetCopies {

    pub fn new(children_count: HashMap<Revision, usize>) -> Self {

        Self {

            all_copies: HashMap::new(),

            path_map: TwoWayPathMap::default(),

            children_count,

        }

    }

    /// Combined the given `changes` data specific to `rev` with the data

    /// previously given for its parents (and transitively, its ancestors).

    pub fn add_revision(

        &mut self,

        rev: Revision,

        p1: Revision,

        p2: Revision,

        changes: ChangedFiles<'_>,

    ) {

        self.add_revision_inner(rev, p1, p2, changes.iter_actions(), |path| {

            changes.get_merge_case(path)

        })

    }

    /// Separated out from `add_revsion` so that unit tests can call this

    /// without synthetizing a `ChangedFiles` in binary format.

    fn add_revision_inner<'a>(

        &mut self,

        rev: Revision,

        p1: Revision,

        p2: Revision,

        copy_actions: impl Iterator<Item = Action<'a>>,

        get_merge_case: impl Fn(&HgPath) -> MergeCase + Copy,

    ) {

        // Retrieve data computed in a previous iteration

        let p1_copies = match p1 {

            NULL_REVISION => None,

            _ => get_and_clean_parent_copies(

                &mut self.all_copies,

                &mut self.children_count,

                p1,

            ), // will be None if the vertex is not to be traversed

        };

        let p2_copies = match p2 {

            NULL_REVISION => None,

            _ => get_and_clean_parent_copies(

                &mut self.all_copies,

                &mut self.children_count,

                p2,

            ), // will be None if the vertex is not to be traversed

        };

        // combine it with data for that revision

        let (p1_copies, p2_copies) = chain_changes(

            &mut self.path_map,

            p1_copies,

            p2_copies,

            copy_actions,

            rev,

        );

        let copies = match (p1_copies, p2_copies) {