// SPDX-License-Identifier: GPL-2.0-or-later
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
//
// Copyright 2020  Laurent Bulteau <laurent.bulteau@u-pem.fr>
//                 Pierre-Yves David <pierre-yves.david@octobus.net>
//                 Georges Racinet <georges.racinet@octobus.net>
//                 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net>

use hex::{FromHex, FromHexError, ToHex};
use std::convert::{AsRef, From};
use std::fmt::{Debug, Display, Formatter};
use std::iter::{FromIterator, IntoIterator};
use std::ops::Add;
use std::result::Result;
use std::result::Result::Ok;
use std::str::FromStr;
use std::string::String;

/// Mercurial revision numbers
///
/// As noted in mercurial's revlog.c, revision numbers are actually encoded in
/// 4 bytes, and are liberally converted to ints, whence the i32
pub type Revision = i32;

/// Mercurial Node ID length
///
/// Note that the 20 bytes length is too strict as we will need 32 size for
/// sha2 (or other newer hash).
pub const NODE_ID_LEN: usize = 20;

/// Mercurial Node ID
#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct NodeID(pub [u8; NODE_ID_LEN]);

impl FromHex for NodeID {
    type Error = FromHexError;

    fn from_hex<T: AsRef<[u8]>>(hex: T) -> Result<Self, Self::Error> {
        Ok(NodeID(<[u8; NODE_ID_LEN]>::from_hex(hex)?))
    }
}

impl FromStr for NodeID {
    type Err = FromHexError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        FromHex::from_hex(s)
    }
}

impl ToHex for NodeID {
    fn encode_hex<T: FromIterator<char>>(&self) -> T {
        self.0.encode_hex()
    }

    fn encode_hex_upper<T: FromIterator<char>>(&self) -> T {
        self.0.encode_hex_upper()
    }
}

impl Display for NodeID {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0.encode_hex::<String>())
    }
}

impl Debug for NodeID {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        Display::fmt(self, f)
    }
}

/// Marker expressing the absence of a parent
///
/// Independently of the actual representation, `NULL_REVISION` is guaranteed
/// to be smaller than all existing revisions.
pub const NULL_REVISION: Revision = -1;
pub const NULL_ID: NodeID = NodeID([0; NODE_ID_LEN]);

/// Rank of a node, i.e. its number of ancestors including itself.
pub type Rank = usize;

/// Parents revisions of a Node
///
/// In Mercurial, a node may have at most two parents.
///
/// This may later be replaced to support an arbitrary number of parents.
#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash, Debug)]
pub struct Parents(pub [Revision; 2]);

impl Parents {
    pub fn contains(&self, rev: Revision) -> bool {
        self.0[0] == rev || self.0[1] == rev
    }
}

impl From<Parents> for [Revision; 2] {
    fn from(parents: Parents) -> Self {
        parents.0
    }
}

impl IntoIterator for Parents {
    type Item = Revision;
    type IntoIter = std::vec::IntoIter<Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        match self.0 {
            [NULL_REVISION, NULL_REVISION] => vec![],
            [p1, NULL_REVISION] | [NULL_REVISION, p1] => vec![p1],
            [p1, p2] => vec![p1, p2],
        }
        .into_iter()
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum GraphReadError {
    InvalidKey,
    KeyedInvalidKey(Revision), // TODO: split errors
    InconsistentGraphData,
    WorkingDirectoryUnsupported, // TODO: split errors
}

/// Graph that can be queried
pub trait Graph {
    fn parents(&self, rev: Revision) -> Result<Parents, GraphReadError>;

    /// Tells whether the given Revision is a merge node,
    /// i.e. it has two parents that are not NULL_REVISION.
    fn is_merge(&self, rev: Revision) -> Result<bool, GraphReadError> {
        Ok(match self.parents(rev)? {
            Parents([_, NULL_REVISION]) | Parents([NULL_REVISION, _]) => false,
            _ => true,
        })
    }
}

/// Graph with efficient revision rank retrieval
pub trait RankedGraph {
    fn rank(&self, rev: Revision) -> Result<Rank, GraphReadError>;
}

/// Graph with efficient revision merge-rank retrieval
pub trait MergeRankedGraph {
    /// Returns the number of merge nodes in the ancestors of the given
    /// Revision, which includes itself.
    fn merge_rank(&self, rev: Revision) -> Result<Rank, GraphReadError>;
}

impl<G: Graph> Graph for &G {
    fn parents(&self, rev: Revision) -> Result<Parents, GraphReadError> {
        (**self).parents(rev)
    }
}

impl<G: RankedGraph> RankedGraph for &G {
    fn rank(&self, rev: Revision) -> Result<Rank, GraphReadError> {
        (**self).rank(rev)
    }
}

impl<G: MergeRankedGraph> MergeRankedGraph for &G {
    fn merge_rank(&self, rev: Revision) -> Result<Rank, GraphReadError> {
        (**self).merge_rank(rev)
    }
}

/// Graph with labelled nodes
pub trait LabelledGraph {
    fn rev_of_node_id(
        &self,
        node_id: NodeID,
    ) -> Result<Revision, GraphReadError>;
    fn node_id(&self, rev: Revision) -> Result<NodeID, GraphReadError>;
}

/// Graph with a known order (number of nodes).
pub trait SizedGraph {
    fn nb_nodes(&self) -> usize;
}

/// Graph with a stable node order.
pub trait StableOrderGraph: Graph {
    /// Sorts the given parents according to the intrinsic node order of the
    /// graph.
    ///
    /// This can be used to order the parents of a node not yet present in
    /// the graph. Non-existing parents must however be part of the graph.
    fn sorted_parents(
        &self,
        parents: Parents,
    ) -> Result<Parents, GraphReadError>;

    /// Returns the Parents of a given Revision sorted by the intrinsic order
    /// of the stable graph. Single-parents are always on the left.
    fn ordered_parents(
        &self,
        rev: Revision,
    ) -> Result<Parents, GraphReadError>;

    /// Returns the ordered list of leaps to follow when walking over the
    /// exclusive part. The list is empty for linear commits.
    fn leaps(&self, rev: Revision) -> Result<&Vec<Leap>, GraphReadError>;

    /// Returns Leap count tuple, i.e. the number of Leap-s to follow when
    /// iterating over the ancestor set of a given Revision in an ordered way.
    fn leap_counts(&self, rev: Revision)
        -> Result<LeapCounts, GraphReadError>;

    /// Returns p_min, the lower parent of a Revision with respect to the
    /// intrinsic node order of the graph.
    fn lower_parent(&self, rev: Revision) -> Result<Revision, GraphReadError> {
        Ok(match self.ordered_parents(rev)? {
            Parents([p, NULL_REVISION]) | Parents([NULL_REVISION, p]) => p,
            Parents([p_min, _]) => p_min,
        })
    }

    /// Returns p_max, the higher parent of a Revision with respect to the
    /// intrinsic node order of the graph.
    fn higher_parent(
        &self,
        rev: Revision,
    ) -> Result<Revision, GraphReadError> {
        Ok(match self.ordered_parents(rev)? {
            Parents([p, NULL_REVISION]) | Parents([NULL_REVISION, p]) => p,
            Parents([_, p_max]) => p_max,
        })
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum LeapType {
    /// Leap that preserves the ordered walk within the exclusive part.
    Soft,

    /// Leap that breaks the ordered walk within the exclusive part.
    Hard,

    /// Last leap ending the exclusive part.
    Last,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Leap {
    pub source: Revision,
    pub target: Revision,
    pub leap_type: LeapType,
    pub since_previous: usize,
    pub merges_since_previous: usize,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct LeapCounts {
    pub soft_leaps: usize,

    /// Includes Hard and Last Leap types.
    pub hard_leaps: usize,
}

impl Add for LeapCounts {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        LeapCounts {
            soft_leaps: self.soft_leaps + other.soft_leaps,
            hard_leaps: self.hard_leaps + other.hard_leaps,
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum GraphWriteError {
    InvalidNodeID(NodeID),
    UnknownParent(NodeID),
    InvalidParents(NodeID),
}

/// Mutable graph in which nodes can be added
pub trait MutableGraph {
    /// Add a revision to the graph
    ///
    /// Absent parents are represented by `NULL_REVISION`.
    fn push(
        &mut self,
        node_id: NodeID,
        p1: NodeID,
        p2: NodeID,
    ) -> Result<Revision, GraphWriteError>;
}