libpijul 0.12.0

use super::{Graph, VertexId};
use backend::*;
use std::collections::HashSet;

pub(in graph) struct DFS {
    pub visits: Vec<Visits>,
    pub counter: usize,
    pub has_conflicts: bool,
}

#[derive(Clone, Debug)]
pub(in graph) struct Visits {
    pub first: usize,
    pub last: usize,
    /// Does this vertex have incomparable children?
    pub begins_conflict: Option<usize>,
    /// Does this vertex have incoming cross-edges?
    pub ends_conflict: bool,
    /// Has the line been output? (for the second DFS, in
    /// conflict_tree)
    pub output: bool,
}

impl Default for Visits {
    fn default() -> Self {
        Visits {
            first: 0,
            last: 0,
            begins_conflict: None,
            ends_conflict: false,
            output: false,
        }
    }
}

impl DFS {
    pub fn new(n: usize) -> Self {
        DFS {
            visits: vec![Visits::default(); n],
            counter: 1,
            has_conflicts: false,
        }
    }
}

impl DFS {
    fn mark_discovered(&mut self, scc: usize) {
        if self.visits[scc].first == 0 {
            self.visits[scc].first = self.counter;
            self.counter += 1;
        }
    }

    fn mark_last_visit(&mut self, scc: usize) {
        self.mark_discovered(scc);
        self.visits[scc].last = self.counter;
        self.counter += 1;
    }

    pub fn first_visit(&self, scc: usize) -> usize {
        self.visits[scc].first
    }

    pub fn last_visit(&self, scc: usize) -> usize {
        self.visits[scc].last
    }
}

struct State {
    n_scc: usize,
    forward_scc: HashSet<usize>,
    descendants: Option<Vec<usize>>,
    current_path: Path,
    // Length of the current path just when we first visited `n_scc`
    // (including n_scc).
    current_path_len: usize,
    return_values: Vec<Path>,
}

#[derive(Debug)]
pub(in graph) struct Path {
    pub path: Vec<PathElement>,
    pub sccs: HashSet<usize>,
    pub end: usize,
}

#[derive(Debug)]
pub(in graph) enum PathElement {
    Scc { scc: usize },
    Conflict { sides: Vec<Path> },
}

impl Graph {
    /// Run a depth-first search on this graph, assigning the
    /// `first_visit` and `last_visit` numbers to each node.
    pub(in graph) fn dfs<A: Transaction, R>(
        &mut self,
        txn: &GenericTxn<A, R>,
        branch: &Branch,
        scc: &[Vec<VertexId>],
        dfs: &mut DFS,
        forward: &mut Vec<(Key<PatchId>, Edge)>,
    ) -> Path {
        let mut call_stack: Vec<State> = Vec::with_capacity(scc.len());
        call_stack.push(State {
            n_scc: scc.len() - 1,
            forward_scc: HashSet::new(),
            descendants: None,
            current_path: Path {
                path: Vec::new(),
                sccs: HashSet::new(),
                end: 0,
            },
            current_path_len: 0,
            return_values: Vec::new(),
        });
        let mut return_value = None;

        while let Some(mut state) = call_stack.pop() {
            debug!("dfs, n_scc = {:?}", state.n_scc);
            for &VertexId(id) in scc[state.n_scc].iter() {
                debug!("dfs, n_scc: {:?}", self.lines[id].key);
            }
            dfs.mark_discovered(state.n_scc);
            debug!(
                "scc: {:?}, first {} last {}",
                state.n_scc,
                dfs.first_visit(state.n_scc),
                dfs.last_visit(state.n_scc)
            );
            debug!("descendants = {:?}", state.descendants);
            let mut descendants = if let Some(descendants) = state.descendants {
                descendants
            } else {
                // First visit / discovery of SCC n_scc.
                state
                    .current_path
                    .path
                    .push(PathElement::Scc { scc: state.n_scc });
                state.current_path.sccs.insert(state.n_scc);
                state.current_path.end = std::cmp::min(state.current_path.end, state.n_scc);
                // Collect all descendants of this SCC, in order of increasing
                // SCC.
                let mut descendants = Vec::new();
                for cousin in scc[state.n_scc].iter() {
                    for &(e, n_child) in self.children(*cousin) {
                        let is_ok = match e {
                            Some(e) if e.flag.contains(EdgeFlags::FOLDER_EDGE) => false,
                            _ => true,
                        };
                        if is_ok {
                            let child_component = self[n_child].scc;
                            debug!("child_component {:?}", child_component);
                            if child_component < state.n_scc
                                && dfs.first_visit(child_component) == 0
                            {
                                // If this is a child, and we haven't visited it yet.
                                debug!("not yet visited");
                                descendants.push(child_component)
                            } else {
                                // Set the end to the highest descendant.
                                state.current_path.end =
                                    std::cmp::max(state.current_path.end, child_component);
                            }
                        }
                    }
                }
                // After Tarjan's algorithm, the SCC numbers are in
                // reverse topological order. Here, we want to visit
                // the first child in topological order, hence the one
                // with the largest SCC number first.
                descendants.sort();
                descendants
            };

            // Pop descendants until we find one into which we can
            // recurse.
            let mut recursive_call = None;
            while let Some(child) = descendants.pop() {
                debug!(
                    "child {:?}, first {} last {}",
                    child,
                    dfs.first_visit(child),
                    dfs.last_visit(child)
                );
                if dfs.first_visit(state.n_scc) < dfs.first_visit(child) {
                    // This is a forward edge.
                    debug!("last_visit to {:?}: {:?}", child, dfs.last_visit(child));
                    state.forward_scc.insert(child);
                } else if dfs.first_visit(child) == 0 {
                    // SCC `child` has not yet been visited, visit it.
                    recursive_call = Some(child);
                    break;
                } else {
                    // cross edge
                }
            }
            if let Some(child) = recursive_call {
                if let Some(return_value) = return_value.take() {
                    state.return_values.push(return_value)
                }
                // The current path is passed on to the first
                // child. Subsequent children will start with an empty
                // Vec as their current path.
                let current_path = std::mem::replace(
                    &mut state.current_path,
                    Path {
                        path: Vec::new(),
                        sccs: HashSet::new(),
                        end: 0,
                    },
                );
                call_stack.push(State {
                    descendants: Some(descendants),
                    ..state
                });
                call_stack.push(State {
                    n_scc: child,
                    forward_scc: HashSet::new(),
                    descendants: None,
                    current_path_len: current_path.path.len(),
                    current_path,
                    return_values: Vec::new(),
                });
            } else {
                dfs.mark_last_visit(state.n_scc);
                debug!("return value: {:?}", return_value);
                if let Some(return_value_) = return_value.take() {
                    if state.return_values.is_empty() {
                        debug!("passing the return value on");
                        return_value = Some(return_value_)
                    } else {
                        // Conflict, build the conflict
                        debug!(
                            "reducing conflict, current_path_len = {:?}",
                            state.current_path_len
                        );
                        state.return_values.push(return_value_);
                        let mut main_path = state.return_values[0]
                            .path
                            .split_off(state.current_path_len + 1);
                        std::mem::swap(&mut state.return_values[0].path, &mut main_path);

                        // We sort the sides, putting the `end` vertex
                        // that is highest in the graph last.
                        state.return_values.sort_by(|a, b| a.end.cmp(&b.end));
                        debug!("return_values = {:?}", state.return_values);
                        let sccs = state
                            .return_values
                            .iter()
                            .flat_map(|side| side.sccs.iter())
                            .map(|&x| x)
                            .collect();
                        let mut sides = Vec::new();
                        while let Some(side) = state.return_values.pop() {
                            debug!("handling conflict side {:?}", side);
                            // In which of the other sides does this side end?
                            let main_side = if let Some(n) = state
                                .return_values
                                .iter()
                                .position(|side_| {
                                    side_.sccs.contains(&side.end)
                                })
                            {
                                n
                            } else {
                                debug!("no main side found");
                                sides.push(side);
                                continue;
                            };
                            debug!("main_side = {:?}", main_side);

                            // If there is already a conflict started,
                            // just add a side, and continue.
                            if let PathElement::Conflict { ref mut sides, .. } =
                                state.return_values[main_side].path[0]
                            {
                                debug!("there is already a conflict, sides = {:?}", sides);
                                // This conflict already existed.
                                if sides[0].end == side.end {
                                    sides.push(side);
                                    continue;
                                }
                            }

                            // Else, find the last vertex of the conflict.
                            let end = state.return_values[main_side]
                                .path
                                .iter()
                                .position(|v| match v {
                                    PathElement::Scc { scc } => *scc == side.end,
                                    PathElement::Conflict { ref sides } => {
                                        sides.iter().any(|side_| side_.sccs.contains(&side.end))
                                    }
                                })
                                .unwrap();
                            debug!("end = {:?} {:?}", end, state.return_values[main_side].path);
                            let mut v = Vec::new();
                            // Insert empty conflict at the beginning,
                            // we will populate it just after a little
                            // memory trick.
                            v.push(PathElement::Conflict { sides: Vec::new() });
                            v.extend(state.return_values[main_side].path.drain(end..));
                            let side0 =
                                std::mem::replace(&mut state.return_values[main_side].path, v);
                            // Here, side0 contains just a conflicting
                            // side, and
                            // `state.return_values[main_side]` starts
                            // with a PathElement::Conflict, and ends
                            // with the end of the main path.

                            // Clean the SCCS in the return values, populate the SCCS of side0.
                            let mut sccs0 = HashSet::new();
                            for elt in side0.iter() {
                                match *elt {
                                    PathElement::Scc { scc } => {
                                        sccs0.insert(scc);
                                    }
                                    PathElement::Conflict { ref sides } => {
                                        for side in sides {
                                            for &scc in side.sccs.iter() {
                                                sccs0.insert(scc);
                                            }
                                        }
                                    }
                                }
                            }
                            state.return_values[main_side].sccs.extend(
                                side.sccs.iter().map(|&x| x)
                            );
                            state.return_values[main_side].path[0] = PathElement::Conflict {
                                sides: vec![
                                    Path {
                                        path: side0,
                                        sccs: sccs0,
                                        end: side.end,
                                    },
                                    side,
                                ],
                            };
                        }
                        if sides.len() > 1 {
                            main_path.push(PathElement::Conflict { sides })
                        } else {
                            main_path.extend(sides.pop().unwrap().path.into_iter())
                        }
                        return_value = Some(Path {
                            path: main_path,
                            sccs,
                            end: 0,
                        })
                    }
                } else {
                    debug!(
                        "no previous return value, returning current path {:?}",
                        state.current_path
                    );
                    return_value = Some(state.current_path)
                }

                // After this, collect forward edges. Look at all
                // children of this SCC.
                for cousin in scc[state.n_scc].iter() {
                    for &(edge, n_child) in self.children(*cousin) {
                        if let Some(mut edge) = edge {
                            // Is this edge a forward edge of the DAG?
                            if state.forward_scc.contains(&self[n_child].scc)
                                && edge.flag.contains(EdgeFlags::PSEUDO_EDGE)
                                && !txn.test_edge(
                                    branch,
                                    self[*cousin].key,
                                    edge.dest,
                                    EdgeFlags::DELETED_EDGE,
                                    EdgeFlags::DELETED_EDGE,
                                )
                            {
                                debug!("forward: {:?} {:?}", self[*cousin].key, edge);
                                forward.push((self[*cousin].key, edge))
                            } else {
                                // Does this edge have parallel PSEUDO edges? If so, they may not be "forward", but they are redundant.
                                edge.flag = EdgeFlags::PSEUDO_EDGE;
                                edge.introduced_by = ROOT_PATCH_ID;
                                let mut edges = txn
                                    .iter_nodes(branch, Some((self[*cousin].key, Some(edge))))
                                    .take_while(|&(k, v)| {
                                        k == self[*cousin].key
                                            && v.dest == edge.dest
                                            && v.flag
                                                <= EdgeFlags::FOLDER_EDGE | EdgeFlags::PSEUDO_EDGE
                                    });
                                edges.next(); // ignore the first pseudo-edge.
                                forward.extend(edges.map(|(k, v)| (k, v))); // add all parallel edges.
                            }
                        }
                    }
                }
            }
        }
        debug!("DFS done, returning");
        return_value.unwrap_or(Path {
            path: Vec::new(),
            sccs: HashSet::new(),
            end: 0,
        })
    }
}