This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9297

copies: introduce a basic Rust function for `combine_changeset_copies`
ClosedPublic

Authored by marmoute on Nov 12 2020, 10:16 AM.

Details

Reviewers
Alphare
pulkit
Group Reviewers
hg-reviewers
Commits
rHG595979dc924e: copies: introduce a basic Rust function for `combine_changeset_copies`
Summary

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.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

marmoute created this revision.Nov 12 2020, 10:16 AM
Alphare accepted this revision.Nov 13 2020, 6:03 AM
Alphare added a subscriber: Alphare.

Mostly nits, but I'd like not to break clippy when we can help it.

The logic seems sound, which is not surprising since this is a re-write of Python.

rust/hg-core/src/copy_tracing.rs
98

Nit: for loops already desugar to calling into_iter(). This applies to multiple other places in the file

106

Simply use let (parent, child_copies) = if ...

167

let (minor, major) = if ...

198

You should add #[allow(clippy::if_same_then_else)] to this function because clippy is not happy with your explicit identical if/else cases. https://rust-lang.github.io/rust-clippy/master/index.html#if_same_then_else

207

let overwrite = if

marmoute added a comment.Nov 13 2020, 5:32 PM

The rest of the feedback have been applied. update to the diff to come.

rust/hg-core/src/copy_tracing.rs
207

The logic here is enough of a headache, that I really prefer to be explicit here, with each close to be fairly easy to understand on its own.

marmoute updated this revision to Diff 23492.Nov 13 2020, 7:05 PM
Alphare accepted this revision.Nov 16 2020, 6:10 AM
Alphare added inline comments.
rust/hg-core/src/copy_tracing.rs
207

Sure, sounds good.

SimonSapin added a subscriber: SimonSapin.Nov 25 2020, 8:55 AM
SimonSapin added inline comments.
rust/hg-core/src/copy_tracing.rs
8

Could be worth documenting which of the key or value are source v.s. destination. At first I assumed the opposite of what the code seems to be doing.

Speaking of, can multiple keys have the same value? If so, what does that represent?

15

What does None represent here?

161–165

unreachable! can be avoided by using a custom enum (which can be defined inline in the function) instead of plain integers, or using a bool and renaming parent to something like is_parent_1

176

to_owned here copies a TimeStampedPathCopies value, but the original is not needed anymore so remove could be used instead of get.

marmoute added inline comments.Nov 25 2020, 9:06 AM
rust/hg-core/src/copy_tracing.rs
8

This use the same direction than the expect return (and the python implementation). But you are right, this could use a comment.

Multiple key can have a same value. It means that the file have been copied to multiple other file at the same time. The common use case for that is when a file is split in multiple others.

15

A file deletion. (I assume this is a hint that a comment could help).

161–165

I agrre with you so much that I am introducing an enum doing this further down the road :-)

176

Good point.

marmoute updated this revision to Diff 23714.Nov 27 2020, 7:30 AM
pulkit accepted this revision.Nov 28 2020, 4:39 AM
This revision is now accepted and ready to land.Nov 28 2020, 4:39 AM
marmoute updated this revision to Diff 23762.Nov 28 2020, 5:26 AM

Revision Contents
Changeset List

Diff 23766

rust/hg-core/src/copy_tracing.rs

  • This file was added.
use crate::utils::hg_path::HgPathBuf;
use crate::Revision;
use std::collections::HashMap;
use std::collections::HashSet;
pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
SimonSapinUnsubmitted
Not Done

Could be worth documenting which of the key or value are source v.s. destination. At first I assumed the opposite of what the code seems to be doing.

Speaking of, can multiple keys have the same value? If so, what does that represent?

SimonSapin: Could be worth documenting which of the key or value are source v.s. destination. At first I…
marmouteAuthorUnsubmitted
Done

This use the same direction than the expect return (and the python implementation). But you are right, this could use a comment.

Multiple key can have a same value. It means that the file have been copied to multiple other file at the same time. The common use case for that is when a file is split in multiple others.

marmoute: This use the same direction than the expect return (and the python implementation). But you are…
#[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>,
SimonSapinUnsubmitted
Not Done

What does None represent here?

SimonSapin: What does `None` represent here?
marmouteAuthorUnsubmitted
Done

A file deletion. (I assume this is a hint that a comment could help).

marmoute: A file deletion. (I assume this is a hint that a comment could help).
}
/// 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`"),
};
AlphareUnsubmitted
Not Done

Nit: for loops already desugar to calling into_iter(). This applies to multiple other places in the file

Alphare: Nit: `for` loops already desugar to calling `into_iter()`. This applies to multiple other…
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)
AlphareUnsubmitted
Not Done

Simply use let (parent, child_copies) = if ...

Alphare: Simply use `let (parent, child_copies) = if ...`
} 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!(),
SimonSapinUnsubmitted
Not Done

unreachable! can be avoided by using a custom enum (which can be defined inline in the function) instead of plain integers, or using a bool and renaming parent to something like is_parent_1

SimonSapin: `unreachable!` can be avoided by using a custom enum (which can be defined inline in the…
marmouteAuthorUnsubmitted
Done

I agrre with you so much that I am introducing an enum doing this further down the road :-)

marmoute: I agrre with you so much that I am introducing an enum doing this further down the road :-)
};
let merged_copies =
AlphareUnsubmitted
Not Done

let (minor, major) = if ...

Alphare: `let (minor, major) = if ...`
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.
SimonSapinUnsubmitted
Not Done

to_owned here copies a TimeStampedPathCopies value, but the original is not needed anymore so remove could be used instead of get.

SimonSapin: `to_owned` here copies a `TimeStampedPathCopies` value, but the original is not needed anymore…
marmouteAuthorUnsubmitted
Done

Good point.

marmoute: Good point.
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,
AlphareUnsubmitted
Not Done

You should add #[allow(clippy::if_same_then_else)] to this function because clippy is not happy with your explicit identical if/else cases. https://rust-lang.github.io/rust-clippy/master/index.html#if_same_then_else

Alphare: You should add `#[allow(clippy::if_same_then_else)]` to this function because `clippy` is not…
) -> 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
AlphareUnsubmitted
Not Done

let overwrite = if

Alphare: `let overwrite = if`
marmouteAuthorUnsubmitted
Done

The logic here is enough of a headache, that I really prefer to be explicit here, with each close to be fairly easy to understand on its own.

marmoute: The logic here is enough of a headache, that I really prefer to be explicit here, with each…
AlphareUnsubmitted
Done

Sure, sounds good.

Alphare: Sure, sounds good.
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

dirstate_map::DirstateMap, dirstate_map::DirstateMap,
parsers::{pack_dirstate, parse_dirstate, PARENT_SIZE}, parsers::{pack_dirstate, parse_dirstate, PARENT_SIZE},
status::{ status::{
status, BadMatch, BadType, DirstateStatus, StatusError, StatusOptions, status, BadMatch, BadType, DirstateStatus, StatusError, StatusOptions,
}, },
CopyMap, CopyMapIter, DirstateEntry, DirstateParents, EntryState, CopyMap, CopyMapIter, DirstateEntry, DirstateParents, EntryState,
StateMap, StateMapIter, StateMap, StateMapIter,
}; };
pub mod copy_tracing;
mod filepatterns; mod filepatterns;
pub mod matchers; pub mod matchers;
pub mod revlog; pub mod revlog;
pub use revlog::*; pub use revlog::*;
pub mod operations; pub mod operations;
pub mod utils; pub mod utils;
// Remove this to see (potential) non-artificial compile failures. MacOS // Remove this to see (potential) non-artificial compile failures. MacOS