// 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  Pacien TRAN-GIRARD <pacien.trangirard@pacien.net>

use crate::graph::{
    Graph, GraphReadError, Leap, LeapType, Parents, Rank, RankedGraph,
    Revision, StableOrderGraph, NULL_REVISION,
};
use crate::lazy_ancestors::LazyAncestors;
use std::collections::HashSet;
use std::option::Option::Some;
use std::result::Result;
use std::result::Result::Ok;
use std::vec::Vec;

/// Computes the rank, i.e. the number of ancestors, of a node,
/// including itself.
pub fn rank(
    graph: &impl Graph,
    rev: Revision,
) -> Result<Rank, GraphReadError> {
    Ok(ancestor_set(graph, &[rev])?.len())
}

/// Computes the merge rank, i.e. the number of ancestors which are merge
/// nodes, of a node, including itself.
pub fn merge_rank(
    graph: &impl Graph,
    rev: Revision,
) -> Result<Rank, GraphReadError> {
    let mut merge_rank = 0;

    for ancestor in ancestor_set(graph, &[rev])? {
        if graph.is_merge(ancestor)? {
            merge_rank += 1;
        }
    }

    Ok(merge_rank)
}

/// Computes the rank, i.e. the number of ancestors including itself,
/// of a node represented by its parents.
/// This is an useful alternative to `rank` when the graph isn't yet built up
/// to this node.
pub fn node_rank(
    graph: &(impl Graph + RankedGraph),
    parents: &Parents,
) -> Result<Rank, GraphReadError> {
    let parent_rank = match parents {
        Parents([NULL_REVISION, NULL_REVISION]) => 0,
        Parents([p, NULL_REVISION]) | Parents([NULL_REVISION, p]) => {
            graph.rank(*p)?
        }
        Parents([p1, p2]) => ancestor_set(graph, &[*p1, *p2])?.len(),
    };

    Ok(1 + parent_rank)
}

/// Computes the set of ancestors of some nodes, which includes themselves.
pub fn ancestor_set(
    graph: &impl Graph,
    revs: &[Revision],
) -> Result<HashSet<Revision>, GraphReadError> {
    let mut ancestors: HashSet<Revision> = HashSet::new();
    let mut pending: Vec<Revision> = Vec::new();
    pending.extend_from_slice(revs);

    while let Some(cursor) = pending.pop() {
        if !ancestors.insert(cursor) {
            continue;
        }
        pending.extend(graph.parents(cursor)?);
    }

    Ok(ancestors)
}

/// Tells whether a revision is an ancestor of a head, including itself.
pub fn is_ancestor(
    graph: &impl Graph,
    head: Revision,
    rev: Revision,
) -> Result<bool, GraphReadError> {
    let mut ancestors: HashSet<Revision> = HashSet::new();
    let mut pending: Vec<Revision> = Vec::new();
    pending.push(head);

    while let Some(cursor) = pending.pop() {
        if cursor == rev {
            return Ok(true);
        }
        if !ancestors.insert(cursor) {
            continue;
        }
        pending.extend(graph.parents(cursor)?);
    }

    Ok(false)
}

#[derive(Clone, Debug)]
pub struct LeapInfo {
    pub exclusive_part_size: usize,
    pub exclusive_merge_count: usize,
    pub leaps: Vec<Leap>,
}

/// Computes and returns the list of leaps encountered when visiting the
/// ancestors of a node, as well as some information related to the excusive
/// part.
///
/// The returned leap vector can then be used to quickly and efficiently
/// iterate over the ancestor set of the node in an ordered manner.
///
/// The node is specified by its Revision number, which can be foreign to the
/// graph, and its Parents, which need to be present in the graph. This allows
/// the computation of the leaps for a node which is not yet inserted in the
/// graph.
pub fn node_leaps(
    graph: &impl StableOrderGraph,
    rev: Revision,
    parents: &Parents,
) -> Result<LeapInfo, GraphReadError> {
    match graph.sorted_parents(*parents)? {
        Parents([_, NULL_REVISION]) => Ok(LeapInfo {
            exclusive_part_size: 0,
            exclusive_merge_count: 0,
            leaps: vec![],
        }),
        Parents([p_min, p_max]) => {
            // TODO:
            //   Make this a dynamic ancestor set extending only when the rank
            //   of our cursor becomes lower than the minimum rank in this set?
            //   This would require an rank-ordered version of the lazy iter
            let mut lower_nodes =
                LazyAncestors::new(graph, vec![p_min], NULL_REVISION, true)?;

            // vector to accumulate all leap we saw (eventually returned)
            let mut leaps = Vec::new();
            // The last revision from pmax ordered ancestors that we saw and
            // was "valid" (ie: not par of pmin ancestors. In case
            // of leap, this will be the leap source.
            let mut previous_rev = rev;
            // The "natural" next revision after the current iteration (its
            // pmax)
            let mut expected_successor = p_max;
            // The number of revision we saw since the last leap. Used to keep
            // track of the size of section between leaps.
            let mut since_last_leap_count = 0;
            let mut merges_since_last_leap_count = 0;
            let mut next_leap_type = LeapType::Soft;
            // Total size of the exclusive part,
            // excluding the starting merge node
            let mut exclusive_part_size = 0;
            // Total number of merge nodes in the exclusive part,
            // excluding the starting merge node.
            let mut exclusive_merge_count = 0;

            // Stack of commits signalling the end of opened branchpoints.
            // Used to know when we are back on the main part and should not
            // expect any new leap.
            let mut unexplored_parents = Vec::new();

            for res_ancestor in OrderedAncestorIterator::new(graph, p_max)? {
                let ancestor = res_ancestor?;

                if lower_nodes.contains(ancestor)? {
                    if unexplored_parents.is_empty() {
                        break;
                    } else {
                        next_leap_type = LeapType::Hard;
                        continue;
                    }
                }

                if graph.is_merge(ancestor)? {
                    let ancestor_p_min = graph.lower_parent(ancestor)?;
                    if !lower_nodes.contains(ancestor_p_min)? {
                        unexplored_parents.push(ancestor_p_min);
                    }

                    merges_since_last_leap_count += 1;
                    exclusive_merge_count += 1;
                }

                since_last_leap_count += 1;
                exclusive_part_size += 1;

                if let Some(end_p_min) = unexplored_parents.last() {
                    if &ancestor == end_p_min {
                        unexplored_parents.pop();
                    }
                }

                if ancestor != expected_successor {
                    leaps.push(Leap {
                        source: previous_rev,
                        target: ancestor,
                        leap_type: next_leap_type,
                        since_previous: since_last_leap_count,
                        merges_since_previous: merges_since_last_leap_count,
                    });

                    since_last_leap_count = 0;
                    merges_since_last_leap_count = 0;
                }

                previous_rev = ancestor;
                expected_successor = graph.higher_parent(ancestor)?;
                next_leap_type = LeapType::Soft;
            }

            leaps.push(Leap {
                source: previous_rev,
                target: p_min,
                leap_type: LeapType::Last,
                since_previous: since_last_leap_count,
                merges_since_previous: merges_since_last_leap_count,
            });

            Ok(LeapInfo {
                exclusive_part_size,
                exclusive_merge_count,
                leaps,
            })
        }
    }
}

/// An iterator using the leaps in a `StableGraph` to iterate over ancestors
/// in the same order as `ordered_ancestors`.
pub struct OrderedAncestorIterator<'a, G: StableOrderGraph> {
    graph: &'a G,
    cursor: Revision,

    /// Leaps to follow when walking the current exclusive part.
    leaps: &'a Vec<Leap>,
    leap_cursor: usize,
}

impl<'a, G: StableOrderGraph> OrderedAncestorIterator<'a, G> {
    pub fn new(graph: &'a G, rev: Revision) -> Result<Self, GraphReadError> {
        Ok(OrderedAncestorIterator {
            graph,
            cursor: rev,
            leaps: graph.leaps(rev)?,
            leap_cursor: 0,
        })
    }

    fn get_next(&mut self) -> Result<Revision, GraphReadError> {
        let current = self.cursor;

        // initial linear leap-free part
        if self.leaps.is_empty() {
            self.cursor = self.graph.higher_parent(current)?;
            self.leaps = self.graph.leaps(self.cursor)?;
            self.leap_cursor = 0;
            return Ok(current);
        }

        match self.leaps.get(self.leap_cursor) {
            // end of current exclusive part => switch to sortFrom(p_min)
            Some(Leap {
                leap_type: LeapType::Last,
                source,
                target,
                ..
            }) if *source == current => {
                self.cursor = *target;
                self.leaps = self.graph.leaps(*target)?;
                self.leap_cursor = 0;
                Ok(current)
            }

            // other leap => follow leap
            Some(Leap { source, target, .. }) if *source == current => {
                self.cursor = *target;
                self.leap_cursor += 1;
                Ok(current)
            }

            // linear part => follow next
            Some(Leap { .. }) => {
                self.cursor = self.graph.higher_parent(current)?;
                Ok(current)
            }

            // leap list is malformed
            None => Err(GraphReadError::InconsistentGraphData),
        }
    }
}

impl<'a, G: StableOrderGraph> Iterator for OrderedAncestorIterator<'a, G> {
    type Item = Result<Revision, GraphReadError>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cursor == NULL_REVISION {
            None // end of iteration
        } else {
            Some(self.get_next())
        }
    }
}

/// Computes the ordered list of ancestors of a node, including itself.
/// using a given `NodeComparator` to order the parents of merge commits.
pub fn ordered_ancestors<G: StableOrderGraph>(
    graph: &G,
    rev: Revision,
) -> Result<Vec<Revision>, GraphReadError> {
    /// Naive recursive implementation of `sort_from`.
    ///
    /// The `visited` set corresponds to the set of `ancestors(p_min)` to
    /// exclude.
    ///
    /// The newly visited nodes and the ordered ancestors are placed in
    /// the `visited` and `ancestors` accumulators respectively.
    ///
    /// This implementation is tail-recursive in the orphan and linear node
    /// cases, but generates stack frames for each encountered merge nodes.
    ///
    /// TODO: rewrite as an iterative version for that last case,
    ///       which will probably easier after having leaps.
    fn sort_from<G: StableOrderGraph>(
        graph: &G,
        rev: Revision,
        visited: &mut HashSet<Revision>,
        ancestors: &mut Vec<Revision>,
    ) -> Result<(), GraphReadError> {
        if visited.contains(&rev) {
            return Ok(());
        }

        visited.insert(rev);
        ancestors.push(rev);

        match graph.ordered_parents(rev)? {
            Parents([NULL_REVISION, NULL_REVISION]) => Ok(()),
            Parents([p, NULL_REVISION]) => {
                sort_from(graph, p, visited, ancestors)
            }
            Parents([p_min, p_max]) => {
                let mut p_min_ancestors: Vec<Revision> = Vec::new();
                sort_from(graph, p_min, visited, &mut p_min_ancestors)?;
                sort_from(graph, p_max, visited, ancestors)?;
                ancestors.extend(p_min_ancestors);
                Ok(())
            }
        }
    }

    let mut visited: HashSet<Revision> = HashSet::new();
    let mut ancestors: Vec<Revision> = Vec::new();
    sort_from(graph, rev, &mut visited, &mut ancestors)?;
    Ok(ancestors)
}

#[cfg(test)]
mod tests {
    use crate::ancestors::{
        ancestor_set, is_ancestor, merge_rank, ordered_ancestors, rank,
        OrderedAncestorIterator,
    };
    use crate::graph::{
        Graph, GraphReadError, LabelledGraph, MutableGraph, NodeID,
        RankedGraph, Revision, StableOrderGraph, NODE_ID_LEN, NULL_ID,
    };
    use crate::testing::graph_in_mem::InMemoryGraph;
    use crate::testing::ordering::{
        NodeIDComparator, NodeIDComparatorReverse,
    };
    use std::collections::HashSet;
    use std::iter::Iterator;
    use std::vec::Vec;

    //noinspection DuplicatedCode
    fn make_dummy_graph() -> impl Graph + LabelledGraph + StableOrderGraph {
        let node: Vec<NodeID> =
            (0..=6).map(|i| NodeID([i + 1; NODE_ID_LEN])).collect();

        let mut graph = InMemoryGraph::<NodeIDComparator>::new();
        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
        graph.push(node[1], node[0], NULL_ID).unwrap();
        graph.push(node[2], node[0], NULL_ID).unwrap();
        graph.push(node[3], node[1], NULL_ID).unwrap();
        graph.push(node[4], node[3], node[2]).unwrap();
        graph.push(node[5], node[4], NULL_ID).unwrap();
        graph.push(node[6], node[3], NULL_ID).unwrap();

        graph
    }

    #[test]
    fn test_rank() {
        let graph = make_dummy_graph();
        assert_eq!(rank(&graph, 0).unwrap(), 1);
        assert_eq!(rank(&graph, 3).unwrap(), 3);
        assert_eq!(rank(&graph, 5).unwrap(), 6);
    }

    #[test]
    fn test_merge_rank() {
        let graph = make_dummy_graph();
        assert_eq!(merge_rank(&graph, 0).unwrap(), 0);
        assert_eq!(merge_rank(&graph, 3).unwrap(), 0);
        assert_eq!(merge_rank(&graph, 4).unwrap(), 1);
        assert_eq!(merge_rank(&graph, 5).unwrap(), 1);
    }

    #[test]
    fn test_ancestor_set() {
        let graph = make_dummy_graph();
        let res = ancestor_set(&graph, &[3]).unwrap();
        let expected: HashSet<Revision> = [3, 1, 0].iter().cloned().collect();
        assert_eq!(res, expected);
    }

    #[test]
    fn test_is_ancestor() {
        let graph = make_dummy_graph();
        assert!(is_ancestor(&graph, 3, 1).unwrap());
        assert!(!is_ancestor(&graph, 1, 3).unwrap());
    }

    #[test]
    fn test_ordered_ancestors() {
        let graph = make_dummy_graph();
        let res = ordered_ancestors(&graph, 5).unwrap();
        assert_eq!(res, vec![5, 4, 3, 1, 2, 0]);
    }

    #[test]
    fn test_ordered_ancestors_iterator() {
        let graph = make_dummy_graph();
        for rev in 0..=6 {
            assert_eq!(
                run_ordered_ancestors_iter(&graph, rev).unwrap(),
                ordered_ancestors(&graph, rev).unwrap()
            );
        }
    }

    fn make_node_id_vec(len: u8) -> Vec<NodeID> {
        (0..len).map(|i| NodeID([i + 1; NODE_ID_LEN])).collect()
    }

    fn run_ordered_ancestors_iter(
        graph: &impl StableOrderGraph,
        rev: Revision,
    ) -> Result<Vec<Revision>, GraphReadError> {
        OrderedAncestorIterator::new(graph, rev)?.collect()
    }

    #[test]
    fn test_ordered_ancestors_iterator_multiple_roots() {
        let node = make_node_id_vec(3);
        let mut graph = InMemoryGraph::<NodeIDComparator>::new();
        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
        graph.push(node[1], NULL_ID, NULL_ID).unwrap();
        graph.push(node[2], node[0], node[1]).unwrap();
        assert_eq!(run_ordered_ancestors_iter(&graph, 2).unwrap(), [2, 1, 0]);
    }

    #[test]
    fn test_ordered_ancestors_iterator_oedipe() {
        let node = make_node_id_vec(3);
        let mut graph = InMemoryGraph::<NodeIDComparator>::new();
        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
        graph.push(node[1], node[0], NULL_ID).unwrap();
        graph.push(node[2], node[0], node[1]).unwrap();
        assert_eq!(run_ordered_ancestors_iter(&graph, 2).unwrap(), [2, 1, 0]);
    }

    #[test]
    fn test_ordered_ancestors_iterator_simple_merge_right() {
        let node = make_node_id_vec(5);
        let mut graph = InMemoryGraph::<NodeIDComparator>::new();
        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
        graph.push(node[1], node[0], NULL_ID).unwrap();
        graph.push(node[2], node[1], NULL_ID).unwrap();
        graph.push(node[3], node[0], NULL_ID).unwrap();
        graph.push(node[4], node[2], node[3]).unwrap();
        assert_eq!(
            run_ordered_ancestors_iter(&graph, 4).unwrap(),
            [4, 3, 2, 1, 0]
        );
    }

    #[test]
    fn test_ordered_ancestors_iterator_simple_merge_left() {
        let node = make_node_id_vec(5);
        let mut graph = InMemoryGraph::<NodeIDComparator>::new();
        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
        graph.push(node[1], node[0], NULL_ID).unwrap();
        graph.push(node[2], node[0], NULL_ID).unwrap();
        graph.push(node[3], node[2], NULL_ID).unwrap();
        graph.push(node[4], node[3], node[1]).unwrap();
        assert_eq!(
            run_ordered_ancestors_iter(&graph, 4).unwrap(),
            [4, 3, 2, 1, 0]
        );
    }

    #[test]
    fn test_ordered_ancestors_iterator_shared_root() {
        let node = make_node_id_vec(6);
        let mut graph = InMemoryGraph::<NodeIDComparator>::new();
        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
        graph.push(node[1], node[0], NULL_ID).unwrap();
        graph.push(node[2], node[0], NULL_ID).unwrap();
        graph.push(node[3], NULL_ID, NULL_ID).unwrap();
        graph.push(node[4], node[3], node[2]).unwrap();
        graph.push(node[5], node[1], node[4]).unwrap();

        for rev in 0..6 {
            assert_eq!(graph.rank(rev), rank(&graph, rev));
        }

        assert_eq!(
            run_ordered_ancestors_iter(&graph, 5).unwrap(),
            [5, 4, 3, 2, 1, 0]
        );
    }

    #[test]
    fn test_ordered_ancestors_iterator_shared_root_rev() {
        let node = make_node_id_vec(6);
        let mut graph = InMemoryGraph::<NodeIDComparatorReverse>::new();
        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
        graph.push(node[1], node[0], NULL_ID).unwrap();
        graph.push(node[2], node[0], NULL_ID).unwrap();
        graph.push(node[3], NULL_ID, NULL_ID).unwrap();
        graph.push(node[4], node[3], node[2]).unwrap();
        graph.push(node[5], node[1], node[4]).unwrap();

        for rev in 0..6 {
            assert_eq!(graph.rank(rev), rank(&graph, rev));
        }

        assert_eq!(
            run_ordered_ancestors_iter(&graph, 5).unwrap(),
            [5, 1, 4, 2, 0, 3]
        );
    }
}