copy_tracing.rs
415 lines
| 15.2 KiB
| application/rls-services+xml
|
RustLexer
r46587 | use crate::utils::hg_path::HgPath; | |||
r46556 | use crate::utils::hg_path::HgPathBuf; | |||
use crate::Revision; | ||||
r46585 | use im_rc::ordmap::DiffItem; | |||
r46577 | use im_rc::ordmap::OrdMap; | |||
r46556 | use std::collections::HashMap; | |||
use std::collections::HashSet; | ||||
pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>; | ||||
r46585 | #[derive(Clone, Debug, PartialEq)] | |||
r46556 | 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) | ||||
r46577 | type TimeStampedPathCopies = OrdMap<HgPathBuf, TimeStampedPathCopy>; | |||
r46556 | ||||
/// 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, | ||||
} | ||||
r46587 | /// 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), | ||||
} | ||||
r46589 | /// 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, | ||||
} | ||||
r46556 | 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(), | ||||
} | ||||
} | ||||
r46587 | ||||
/// 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) | ||||
} | ||||
r46589 | ||||
/// 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; | ||||
} | ||||
} | ||||
r46556 | } | |||
r46586 | /// 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 | ||||
} | ||||
} | ||||
} | ||||
} | ||||
r46556 | /// 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 | ||||
r46586 | pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool>( | |||
r46556 | revs: Vec<Revision>, | |||
children: HashMap<Revision, Vec<Revision>>, | ||||
target_rev: Revision, | ||||
rev_info: &impl Fn(Revision) -> RevInfo, | ||||
r46586 | is_ancestor: &A, | |||
r46556 | ) -> PathCopies { | |||
let mut all_copies = HashMap::new(); | ||||
r46586 | let mut oracle = AncestorOracle::new(is_ancestor); | |||
r46556 | ||||
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); | ||||
r46587 | let parent = if rev == p1 { | |||
1 | ||||
r46556 | } else { | |||
assert_eq!(rev, p2); | ||||
r46587 | 2 | |||
r46556 | }; | |||
let mut new_copies = copies.clone(); | ||||
r46587 | 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); | ||||
r46556 | } | |||
r46587 | 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); | ||||
} | ||||
} | ||||
r46556 | } | |||
} | ||||
// 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 = | ||||
r46586 | merge_copies_dict(minor, major, &changes, &mut oracle); | |||
r46556 | 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)] | ||||
r46586 | fn merge_copies_dict<A: Fn(Revision, Revision) -> bool>( | |||
r46556 | minor: TimeStampedPathCopies, | |||
major: TimeStampedPathCopies, | ||||
changes: &ChangedFiles, | ||||
r46586 | oracle: &mut AncestorOracle<A>, | |||
r46556 | ) -> TimeStampedPathCopies { | |||
r46585 | 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)); | ||||
r46578 | if src_major.path == src_minor.path { | |||
r46585 | // we have the same value, but from other source; | |||
r46578 | if src_major.rev == src_minor.rev { | |||
// If the two entry are identical, no need to do | ||||
r46585 | // anything (but diff should not have yield them) | |||
unreachable!(); | ||||
r46586 | } else if oracle.is_ancestor(src_major.rev, src_minor.rev) | |||
{ | ||||
r46585 | pick_minor(); | |||
r46578 | } else { | |||
r46585 | pick_major(); | |||
r46578 | } | |||
} 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. | ||||
r46585 | unreachable!(); | |||
r46556 | } else { | |||
r46589 | let action = changes.get_merge_case(&dest); | |||
r46588 | if src_major.path.is_none() | |||
r46589 | && action == MergeCase::Salvaged | |||
r46588 | { | |||
// 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() | ||||
r46589 | && action == MergeCase::Salvaged | |||
r46588 | { | |||
// If the file is "deleted" in the minor side but was | ||||
// salvaged by the merge, unconditionnaly preserve the | ||||
// major side. | ||||
pick_major(); | ||||
r46589 | } else if action == MergeCase::Merged { | |||
r46588 | // 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(); | ||||
} | ||||
r46556 | } | |||
} | ||||
r46585 | }; | |||
} | ||||
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; | ||||
r46556 | } else { | |||
r46585 | updates = override_major; | |||
result = major; | ||||
r46556 | } | |||
r46585 | for (k, v) in updates { | |||
result.insert(k, v); | ||||
r46556 | } | |||
} | ||||
result | ||||
} | ||||