rust/hg-core/src/copy_tracing.rs

use crate::utils::hg_path::HgPath;
use crate::utils::hg_path::HgPathBuf;
use crate::Revision;

use im_rc::ordmap::DiffItem;
use im_rc::ordmap::OrdMap;

use std::collections::HashMap;
use std::collections::HashSet;

pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;

#[derive(Clone, Debug, PartialEq)]
struct TimeStampedPathCopy {
    /// 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<HgPathBuf>,
}

/// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)
type TimeStampedPathCopies = OrdMap<HgPathBuf, TimeStampedPathCopy>;

/// hold parent 1, parent 2 and relevant files actions.
pub type RevInfo = (Revision, Revision, ChangedFiles);

/// represent the files affected by a changesets
///
/// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
/// all the data categories tracked by it.
pub struct ChangedFiles {
    removed: HashSet<HgPathBuf>,
    merged: HashSet<HgPathBuf>,
    salvaged: HashSet<HgPathBuf>,
    copied_from_p1: PathCopies,
    copied_from_p2: PathCopies,
}

/// 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)
    Copied(&'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,
}

impl ChangedFiles {
    pub fn new(
        removed: HashSet<HgPathBuf>,
        merged: HashSet<HgPathBuf>,
        salvaged: HashSet<HgPathBuf>,
        copied_from_p1: PathCopies,
        copied_from_p2: PathCopies,
    ) -> Self {
        ChangedFiles {
            removed,
            merged,
            salvaged,
            copied_from_p1,
            copied_from_p2,
        }
    }

    pub fn new_empty() -> Self {
        ChangedFiles {
            removed: HashSet::new(),
            merged: HashSet::new(),
            salvaged: HashSet::new(),
            copied_from_p1: PathCopies::new(),
            copied_from_p2: PathCopies::new(),
        }
    }

    /// Return an iterator over all the `Action` in this instance.
    fn iter_actions(&self, parent: usize) -> impl Iterator<Item = Action> {
        let copies_iter = match parent {
            1 => self.copied_from_p1.iter(),
            2 => self.copied_from_p2.iter(),
            _ => unreachable!(),
        };
        let remove_iter = self.removed.iter();
        let copies_iter = copies_iter.map(|(x, y)| Action::Copied(x, y));
        let remove_iter = remove_iter.map(|x| Action::Removed(x));
        copies_iter.chain(remove_iter)
    }

    /// return the MergeCase value associated with a filename
    fn get_merge_case(&self, path: &HgPath) -> MergeCase {
        if self.salvaged.contains(path) {
            return MergeCase::Salvaged;
        } else if self.merged.contains(path) {
            return MergeCase::Merged;
        } else {
            return MergeCase::Normal;
        }
    }
}

/// A struct responsible for answering "is X ancestors of Y" quickly
///
/// The structure will delegate ancestors call to a callback, and cache the
/// result.
#[derive(Debug)]
struct AncestorOracle<'a, A: Fn(Revision, Revision) -> bool> {
    inner: &'a A,
    pairs: HashMap<(Revision, Revision), bool>,
}

impl<'a, A: Fn(Revision, Revision) -> bool> AncestorOracle<'a, A> {
    fn new(func: &'a A) -> Self {
        Self {
            inner: func,
            pairs: HashMap::default(),
        }
    }

    /// returns `true` if `anc` is an ancestors of `desc`, `false` otherwise
    fn is_ancestor(&mut self, anc: Revision, desc: Revision) -> bool {
        if anc > desc {
            false
        } else if anc == desc {
            true
        } else {
            if let Some(b) = self.pairs.get(&(anc, desc)) {
                *b
            } else {
                let b = (self.inner)(anc, desc);
                self.pairs.insert((anc, desc), b);
                b
            }
        }
    }
}

/// Same as mercurial.copies._combine_changeset_copies, but in Rust.
///
/// Arguments are:
///
/// revs: all revisions to be considered
/// children: a {parent ? [childrens]} mapping
/// target_rev: the final revision we are combining copies to
/// rev_info(rev): callback to get revision information:
///   * first parent
///   * second parent
///   * ChangedFiles
/// isancestors(low_rev, high_rev): callback to check if a revision is an
///                                 ancestor of another
pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool>(
    revs: Vec<Revision>,
    children: HashMap<Revision, Vec<Revision>>,
    target_rev: Revision,
    rev_info: &impl Fn(Revision) -> RevInfo,
    is_ancestor: &A,
) -> PathCopies {
    let mut all_copies = HashMap::new();
    let mut oracle = AncestorOracle::new(is_ancestor);

    for rev in revs {
        // Retrieve data computed in a previous iteration
        let copies = all_copies.remove(&rev);
        let copies = match copies {
            Some(c) => c,
            None => TimeStampedPathCopies::default(), // root of the walked set
        };

        let current_children = match children.get(&rev) {
            Some(c) => c,
            None => panic!("inconsistent `revs` and `children`"),
        };

        for child in current_children {
            // We will chain the copies information accumulated for `rev` with
            // the individual copies information for each of its children.
            // Creating a new PathCopies for each `rev` ? `children` vertex.
            let (p1, p2, changes) = rev_info(*child);

            let parent = if rev == p1 {
                1
            } else {
                assert_eq!(rev, p2);
                2
            };
            let mut new_copies = copies.clone();

            for action in changes.iter_actions(parent) {
                match action {
                    Action::Copied(dest, source) => {
                        let entry;
                        if let Some(v) = copies.get(source) {
                            entry = match &v.path {
                                Some(path) => Some((*(path)).to_owned()),
                                None => Some(source.to_owned()),
                            }
                        } else {
                            entry = Some(source.to_owned());
                        }
                        // Each new entry is introduced by the children, we
                        // record this information as we will need it to take
                        // the right decision when merging conflicting copy
                        // information. See merge_copies_dict for details.
                        let ttpc = TimeStampedPathCopy {
                            rev: *child,
                            path: entry,
                        };
                        new_copies.insert(dest.to_owned(), ttpc);
                    }
                    Action::Removed(f) => {
                        // We must drop copy information for removed file.
                        //
                        // We need to explicitly record them as dropped to
                        // propagate this information when merging two
                        // TimeStampedPathCopies object.
                        if new_copies.contains_key(f.as_ref()) {
                            let ttpc = TimeStampedPathCopy {
                                rev: *child,
                                path: None,
                            };
                            new_copies.insert(f.to_owned(), ttpc);
                        }
                    }
                }
            }

            // Merge has two parents needs to combines their copy information.
            //
            // If the vertex from the other parent was already processed, we
            // will have a value for the child ready to be used. We need to
            // grab it and combine it with the one we already
            // computed. If not we can simply store the newly
            // computed data. The processing happening at
            // the time of the second parent will take care of combining the
            // two TimeStampedPathCopies instance.
            match all_copies.remove(child) {
                None => {
                    all_copies.insert(child, new_copies);
                }
                Some(other_copies) => {
                    let (minor, major) = match parent {
                        1 => (other_copies, new_copies),
                        2 => (new_copies, other_copies),
                        _ => unreachable!(),
                    };
                    let merged_copies =
                        merge_copies_dict(minor, major, &changes, &mut oracle);
                    all_copies.insert(child, merged_copies);
                }
            };
        }
    }

    // Drop internal information (like the timestamp) and return the final
    // mapping.
    let tt_result = all_copies
        .remove(&target_rev)
        .expect("target revision was not processed");
    let mut result = PathCopies::default();
    for (dest, tt_source) in tt_result {
        if let Some(path) = tt_source.path {
            result.insert(dest, path);
        }
    }
    result
}

/// merge two copies-mapping together, minor and major
///
/// In case of conflict, value from "major" will be picked, unless in some
/// cases. See inline documentation for details.
#[allow(clippy::if_same_then_else)]
fn merge_copies_dict<A: Fn(Revision, Revision) -> bool>(
    minor: TimeStampedPathCopies,
    major: TimeStampedPathCopies,
    changes: &ChangedFiles,
    oracle: &mut AncestorOracle<A>,
) -> TimeStampedPathCopies {
    if minor.is_empty() {
        return major;
    } else if major.is_empty() {
        return minor;
    }
    let mut override_minor = Vec::new();
    let mut override_major = Vec::new();

    let mut to_major = |k: &HgPathBuf, v: &TimeStampedPathCopy| {
        override_major.push((k.clone(), v.clone()))
    };
    let mut to_minor = |k: &HgPathBuf, v: &TimeStampedPathCopy| {
        override_minor.push((k.clone(), v.clone()))
    };

    // The diff function leverage detection of the identical subpart if minor
    // and major has some common ancestors. This make it very fast is most
    // case.
    //
    // In case where the two map are vastly different in size, the current
    // approach is still slowish because the iteration will iterate over
    // all the "exclusive" content of the larger on. This situation can be
    // frequent when the subgraph of revision we are processing has a lot
    // of roots. Each roots adding they own fully new map to the mix (and
    // likely a small map, if the path from the root to the "main path" is
    // small.
    //
    // We could do better by detecting such situation and processing them
    // differently.
    for d in minor.diff(&major) {
        match d {
            DiffItem::Add(k, v) => to_minor(k, v),
            DiffItem::Remove(k, v) => to_major(k, v),
            DiffItem::Update { old, new } => {
                let (dest, src_major) = new;
                let (_, src_minor) = old;
                let mut pick_minor = || (to_major(dest, src_minor));
                let mut pick_major = || (to_minor(dest, src_major));
                if src_major.path == src_minor.path {
                    // we have the same value, but from other source;
                    if src_major.rev == src_minor.rev {
                        // If the two entry are identical, no need to do
                        // anything (but diff should not have yield them)
                        unreachable!();
                    } else if oracle.is_ancestor(src_major.rev, src_minor.rev)
                    {
                        pick_minor();
                    } else {
                        pick_major();
                    }
                } else if src_major.rev == src_minor.rev {
                    // We cannot get copy information for both p1 and p2 in the
                    // same rev. So this is the same value.
                    unreachable!();
                } else {
                    let action = changes.get_merge_case(&dest);
                    if src_major.path.is_none()
                        && action == MergeCase::Salvaged
                    {
                        // If the file is "deleted" in the major side but was
                        // salvaged by the merge, we keep the minor side alive
                        pick_minor();
                    } else if src_minor.path.is_none()
                        && action == MergeCase::Salvaged
                    {
                        // If the file is "deleted" in the minor side but was
                        // salvaged by the merge, unconditionnaly preserve the
                        // major side.
                        pick_major();
                    } else if action == MergeCase::Merged {
                        // If the file was actively merged, copy information
                        // from each side might conflict.  The major side will
                        // win such conflict.
                        pick_major();
                    } else if oracle.is_ancestor(src_major.rev, src_minor.rev)
                    {
                        // If the minor side is strictly newer than the major
                        // side, it should be kept.
                        pick_minor();
                    } else if src_major.path.is_some() {
                        // without any special case, the "major" value win
                        // other the "minor" one.
                        pick_major();
                    } else if oracle.is_ancestor(src_minor.rev, src_major.rev)
                    {
                        // the "major" rev is a direct ancestors of "minor",
                        // any different value should
                        // overwrite
                        pick_major();
                    } else {
                        // major version is None (so the file was deleted on
                        // that branch) and that branch is independant (neither
                        // minor nor major is an ancestors of the other one.)
                        // We preserve the new
                        // information about the new file.
                        pick_minor();
                    }
                }
            }
        };
    }

    let updates;
    let mut result;
    if override_major.is_empty() {
        result = major
    } else if override_minor.is_empty() {
        result = minor
    } else {
        if override_minor.len() < override_major.len() {
            updates = override_minor;
            result = minor;
        } else {
            updates = override_major;
            result = major;
        }
        for (k, v) in updates {
            result.insert(k, v);
        }
    }
    result
}