copies: introduce a basic Rust function for `combine_changeset_copies`

This new function mirror the python code.  This first implementation does a lot
of data copies and is therefore quite slow. However my goal here is to create a
simple "frame" from where to start adding optimization.

This patch focus on the `hg-core` part of this work. Coming patches will do the
necessary `hg-cpython` work  to be able to use this from Python.

Differential Revision: https://phab.mercurial-scm.org/D9297

rust/hg-core/src/copy_tracing.rs

@@ -0,0 +1,262
+use crate::utils::hg_path::HgPathBuf;
+use crate::Revision;
+
+use std::collections::HashMap;
+use std::collections::HashSet;
+
+pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
+
+#[derive(Clone, Debug)]
+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 = HashMap<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,
+}
+
+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(),
+        }
+    }
+}
+
+/// 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(
+    revs: Vec<Revision>,
+    children: HashMap<Revision, Vec<Revision>>,
+    target_rev: Revision,
+    rev_info: &impl Fn(Revision) -> RevInfo,
+    is_ancestor: &impl Fn(Revision, Revision) -> bool,
+) -> PathCopies {
+    let mut all_copies = HashMap::new();
+
+    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, child_copies) = if rev == p1 {
+                (1, &changes.copied_from_p1)
+            } else {
+                assert_eq!(rev, p2);
+                (2, &changes.copied_from_p2)
+            };
+            let mut new_copies = copies.clone();
+
+            for (dest, source) in child_copies {
+                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);
+            }
+
+            // 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.
+            for f in changes.removed.iter() {
+                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, is_ancestor);
+                    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(
+    minor: TimeStampedPathCopies,
+    major: TimeStampedPathCopies,
+    changes: &ChangedFiles,
+    is_ancestor: &impl Fn(Revision, Revision) -> bool,
+) -> TimeStampedPathCopies {
+    let mut result = minor.clone();
+    for (dest, src_major) in major {
+        let overwrite;
+        if let Some(src_minor) = minor.get(&dest) {
+            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
+                    overwrite = false;
+                } else if is_ancestor(src_major.rev, src_minor.rev) {
+                    overwrite = false;
+                } else {
+                    overwrite = true;
+                }
+            } 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.
+                overwrite = false;
+            } else if src_major.path.is_none()
+                && changes.salvaged.contains(&dest)
+            {
+                // If the file is "deleted" in the major side but was salvaged
+                // by the merge, we keep the minor side alive
+                overwrite = false;
+            } else if src_minor.path.is_none()
+                && changes.salvaged.contains(&dest)
+            {
+                // If the file is "deleted" in the minor side but was salvaged
+                // by the merge, unconditionnaly preserve the major side.
+                overwrite = true;
+            } else if changes.merged.contains(&dest) {
+                // If the file was actively merged, copy information from each
+                // side might conflict. The major side will win such conflict.
+                overwrite = true;
+            } else if is_ancestor(src_major.rev, src_minor.rev) {
+                // If the minor side is strictly newer than the major side, it
+                // should be kept.
+                overwrite = false;
+            } else if src_major.path.is_some() {
+                // without any special case, the "major" value win other the
+                // "minor" one.
+                overwrite = true;
+            } else if is_ancestor(src_minor.rev, src_major.rev) {
+                // the "major" rev is a direct ancestors of "minor", any
+                // different value should overwrite
+                overwrite = true;
+            } else {
+                // major version is None (so the file was deleted on that
+                // branch) annd that branch is independant (neither minor nor
+                // major is an ancestors of the other one.) We preserve the new
+                // information about the new file.
+                overwrite = false;
+            }
+        } else {
+            // minor had no value
+            overwrite = true;
+        }
+        if overwrite {
+            result.insert(dest, src_major);
+        }
+    }
+    result
+}

rust/hg-core/src/lib.rs

@@ -1,193 +1,194
 // Copyright 2018-2020 Georges Racinet <[e-mail]>
 //           and Mercurial contributors
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 mod ancestors;
 pub mod dagops;
 pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
 mod dirstate;
 pub mod discovery;
 pub mod requirements;
 pub mod testing; // unconditionally built, for use from integration tests
 pub use dirstate::{
     dirs_multiset::{DirsMultiset, DirsMultisetIter},
     dirstate_map::DirstateMap,
     parsers::{pack_dirstate, parse_dirstate, PARENT_SIZE},
     status::{
         status, BadMatch, BadType, DirstateStatus, StatusError, StatusOptions,
     },
     CopyMap, CopyMapIter, DirstateEntry, DirstateParents, EntryState,
     StateMap, StateMapIter,
 };
+pub mod copy_tracing;
 mod filepatterns;
 pub mod matchers;
 pub mod revlog;
 pub use revlog::*;
 pub mod operations;
 pub mod utils;
 
 // Remove this to see (potential) non-artificial compile failures. MacOS
 // *should* compile, but fail to compile tests for example as of 2020-03-06
 #[cfg(not(target_os = "linux"))]
 compile_error!(
     "`hg-core` has only been tested on Linux and will most \
      likely not behave correctly on other platforms."
 );
 
 use crate::utils::hg_path::{HgPathBuf, HgPathError};
 pub use filepatterns::{
     parse_pattern_syntax, read_pattern_file, IgnorePattern,
     PatternFileWarning, PatternSyntax,
 };
 use std::collections::HashMap;
 use twox_hash::RandomXxHashBuilder64;
 
 /// This is a contract between the `micro-timer` crate and us, to expose
 /// the `log` crate as `crate::log`.
 use log;
 
 pub type LineNumber = usize;
 
 /// Rust's default hasher is too slow because it tries to prevent collision
 /// attacks. We are not concerned about those: if an ill-minded person has
 /// write access to your repository, you have other issues.
 pub type FastHashMap<K, V> = HashMap<K, V, RandomXxHashBuilder64>;
 
 #[derive(Clone, Debug, PartialEq)]
 pub enum DirstateParseError {
     TooLittleData,
     Overflow,
     // TODO refactor to use bytes instead of String
     CorruptedEntry(String),
     Damaged,
 }
 
 impl From<std::io::Error> for DirstateParseError {
     fn from(e: std::io::Error) -> Self {
         DirstateParseError::CorruptedEntry(e.to_string())
     }
 }
 
 impl ToString for DirstateParseError {
     fn to_string(&self) -> String {
         use crate::DirstateParseError::*;
         match self {
             TooLittleData => "Too little data for dirstate.".to_string(),
             Overflow => "Overflow in dirstate.".to_string(),
             CorruptedEntry(e) => format!("Corrupted entry: {:?}.", e),
             Damaged => "Dirstate appears to be damaged.".to_string(),
         }
     }
 }
 
 #[derive(Debug, PartialEq)]
 pub enum DirstatePackError {
     CorruptedEntry(String),
     CorruptedParent,
     BadSize(usize, usize),
 }
 
 impl From<std::io::Error> for DirstatePackError {
     fn from(e: std::io::Error) -> Self {
         DirstatePackError::CorruptedEntry(e.to_string())
     }
 }
 #[derive(Debug, PartialEq)]
 pub enum DirstateMapError {
     PathNotFound(HgPathBuf),
     EmptyPath,
     InvalidPath(HgPathError),
 }
 
 impl ToString for DirstateMapError {
     fn to_string(&self) -> String {
         match self {
             DirstateMapError::PathNotFound(_) => {
                 "expected a value, found none".to_string()
             }
             DirstateMapError::EmptyPath => "Overflow in dirstate.".to_string(),
             DirstateMapError::InvalidPath(e) => e.to_string(),
         }
     }
 }
 
 #[derive(Debug)]
 pub enum DirstateError {
     Parse(DirstateParseError),
     Pack(DirstatePackError),
     Map(DirstateMapError),
     IO(std::io::Error),
 }
 
 impl From<DirstateParseError> for DirstateError {
     fn from(e: DirstateParseError) -> Self {
         DirstateError::Parse(e)
     }
 }
 
 impl From<DirstatePackError> for DirstateError {
     fn from(e: DirstatePackError) -> Self {
         DirstateError::Pack(e)
     }
 }
 
 #[derive(Debug)]
 pub enum PatternError {
     Path(HgPathError),
     UnsupportedSyntax(String),
     UnsupportedSyntaxInFile(String, String, usize),
     TooLong(usize),
     IO(std::io::Error),
     /// Needed a pattern that can be turned into a regex but got one that
     /// can't. This should only happen through programmer error.
     NonRegexPattern(IgnorePattern),
 }
 
 impl ToString for PatternError {
     fn to_string(&self) -> String {
         match self {
             PatternError::UnsupportedSyntax(syntax) => {
                 format!("Unsupported syntax {}", syntax)
             }
             PatternError::UnsupportedSyntaxInFile(syntax, file_path, line) => {
                 format!(
                     "{}:{}: unsupported syntax {}",
                     file_path, line, syntax
                 )
             }
             PatternError::TooLong(size) => {
                 format!("matcher pattern is too long ({} bytes)", size)
             }
             PatternError::IO(e) => e.to_string(),
             PatternError::Path(e) => e.to_string(),
             PatternError::NonRegexPattern(pattern) => {
                 format!("'{:?}' cannot be turned into a regex", pattern)
             }
         }
     }
 }
 
 impl From<DirstateMapError> for DirstateError {
     fn from(e: DirstateMapError) -> Self {
         DirstateError::Map(e)
     }
 }
 
 impl From<std::io::Error> for DirstateError {
     fn from(e: std::io::Error) -> Self {
         DirstateError::IO(e)
     }
 }
 
 impl From<std::io::Error> for PatternError {
     fn from(e: std::io::Error) -> Self {
         PatternError::IO(e)
     }
 }
 
 impl From<HgPathError> for PatternError {
     fn from(e: HgPathError) -> Self {
         PatternError::Path(e)
     }
 }