annotate rust/hg-core/src/copy_tracing.rs @ 45987:8b99c473aae2

copies-rust: move is_ancestor caching within the rust code

Now that the OrdMap merging is fast, smaller things start to matters.

We move the caching of `is_ancestor` call within the Rust code. This avoid
round-trip to Python and help us to shave more time on our slower case:

Repo            Cases                                 Source-Rev   Dest-Rev         Old-Time      New-Time     Difference   Factor
------------------------------------------------------------------------------------------------------------------------------------
pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :   2.780174 s,   2.137894 s,  -0.642280 s, × 0.7690
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :   9.843481 s,   8.100385 s,  -1.743096 s, × 0.8229


Note: I would happily have used native code for ancestors computation, however
I failed (did not tried hard) to created a rust version that goes as fast as
the current C version.

Below are full tables for:
- this change compared to the previous change
- this change compared to filelog performance

Repo            Cases                                 Source-Rev   Dest-Rev         Old-Time      New-Time     Difference   Factor
------------------------------------------------------------------------------------------------------------------------------------
mercurial       x_revs_x_added_0_copies               ad6b123de1c7 39cfcef4f463 :   0.000049 s,   0.000047 s,  -0.000002 s, × 0.9592
mercurial       x_revs_x_added_x_copies               2b1c78674230 0c1d10351869 :   0.000182 s,   0.000181 s,  -0.000001 s, × 0.9945
mercurial       x000_revs_x000_added_x_copies         81f8ff2a9bf2 dd3267698d84 :   0.005872 s,   0.005852 s,  -0.000020 s, × 0.9966
pypy            x_revs_x_added_0_copies               aed021ee8ae8 099ed31b181b :   0.000229 s,   0.000229 s,  +0.000000 s, × 1.0000
pypy            x_revs_x000_added_0_copies            4aa4e1f8e19a 359343b9ac0e :   0.000058 s,   0.000058 s,  +0.000000 s, × 1.0000
pypy            x_revs_x_added_x_copies               ac52eb7bbbb0 72e022663155 :   0.000148 s,   0.000146 s,  -0.000002 s, × 0.9865
pypy            x_revs_x00_added_x_copies             c3b14617fbd7 ace7255d9a26 :   0.001205 s,   0.001206 s,  +0.000001 s, × 1.0008
pypy            x_revs_x000_added_x000_copies         df6f7a526b60 a83dc6a2d56f :   0.025662 s,   0.025275 s,  -0.000387 s, × 0.9849
pypy            x000_revs_xx00_added_0_copies         89a76aede314 2f22446ff07e :   0.080113 s,   0.080303 s,  +0.000190 s, × 1.0024
pypy            x000_revs_x000_added_x_copies         8a3b5bfd266e 2c68e87c3efe :   0.153030 s,   0.152641 s,  -0.000389 s, × 0.9975
pypy            x000_revs_x000_added_x000_copies      89a76aede314 7b3dda341c84 :   0.098774 s,   0.099107 s,  +0.000333 s, × 1.0034
pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :   2.780174 s,   2.137894 s,  -0.642280 s, × 0.7690
pypy            x0000_revs_xx000_added_0_copies       bf2c629d0071 4ffed77c095c :   0.022218 s,   0.022202 s,  -0.000016 s, × 0.9993
pypy            x0000_revs_xx000_added_x000_copies    08ea3258278e d9fa043f30c0 :   0.252125 s,   0.228946 s,  -0.023179 s, × 0.9081
netbeans        x_revs_x_added_0_copies               fb0955ffcbcd a01e9239f9e7 :   0.000186 s,   0.000186 s,  +0.000000 s, × 1.0000
netbeans        x_revs_x000_added_0_copies            6f360122949f 20eb231cc7d0 :   0.000133 s,   0.000133 s,  +0.000000 s, × 1.0000
netbeans        x_revs_x_added_x_copies               1ada3faf6fb6 5a39d12eecf4 :   0.000320 s,   0.000320 s,  +0.000000 s, × 1.0000
netbeans        x_revs_x00_added_x_copies             35be93ba1e2c 9eec5e90c05f :   0.001336 s,   0.001339 s,  +0.000003 s, × 1.0022
netbeans        x000_revs_xx00_added_0_copies         eac3045b4fdd 51d4ae7f1290 :   0.015573 s,   0.015694 s,  +0.000121 s, × 1.0078
netbeans        x000_revs_x000_added_x_copies         e2063d266acd 6081d72689dc :   0.018667 s,   0.018457 s,  -0.000210 s, × 0.9888
netbeans        x000_revs_x000_added_x000_copies      ff453e9fee32 411350406ec2 :   0.112534 s,   0.111691 s,  -0.000843 s, × 0.9925
netbeans        x0000_revs_xx000_added_x000_copies    588c2d1ced70 1aad62e59ddd :   1.231869 s,   1.166017 s,  -0.065852 s, × 0.9465
mozilla-central x_revs_x_added_0_copies               3697f962bb7b 7015fcdd43a2 :   0.000197 s,   0.000197 s,  +0.000000 s, × 1.0000
mozilla-central x_revs_x000_added_0_copies            dd390860c6c9 40d0c5bed75d :   0.000637 s,   0.000626 s,  -0.000011 s, × 0.9827
mozilla-central x_revs_x_added_x_copies               8d198483ae3b 14207ffc2b2f :   0.000303 s,   0.000303 s,  +0.000000 s, × 1.0000
mozilla-central x_revs_x00_added_x_copies             98cbc58cc6bc 446a150332c3 :   0.001663 s,   0.001679 s,  +0.000016 s, × 1.0096
mozilla-central x_revs_x000_added_x000_copies         3c684b4b8f68 0a5e72d1b479 :   0.007008 s,   0.006947 s,  -0.000061 s, × 0.9913
mozilla-central x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :   0.127385 s,   0.133070 s,  +0.005685 s, × 1.0446
mozilla-central x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   0.008740 s,   0.008705 s,  -0.000035 s, × 0.9960
mozilla-central x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :   0.005783 s,   0.005913 s,  +0.000130 s, × 1.0225
mozilla-central x000_revs_x000_added_x000_copies      7c97034feb78 4407bd0c6330 :   0.102184 s,   0.101373 s,  -0.000811 s, × 0.9921
mozilla-central x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :   0.046220 s,   0.046526 s,  +0.000306 s, × 1.0066
mozilla-central x0000_revs_xx000_added_x000_copies    f78c615a656c 96a38b690156 :   0.315271 s,   0.313954 s,  -0.001317 s, × 0.9958
mozilla-central x00000_revs_x0000_added_x0000_copies  6832ae71433c 4c222a1d9a00 :   3.478747 s,   3.367395 s,  -0.111352 s, × 0.9680
mozilla-central x00000_revs_x00000_added_x000_copies  76caed42cf7c 1daa622bbe42 :   4.766435 s,   4.691820 s,  -0.074615 s, × 0.9843
mozilla-try     x_revs_x_added_0_copies               aaf6dde0deb8 9790f499805a :   0.001214 s,   0.001199 s,  -0.000015 s, × 0.9876
mozilla-try     x_revs_x000_added_0_copies            d8d0222927b4 5bb8ce8c7450 :   0.001221 s,   0.001216 s,  -0.000005 s, × 0.9959
mozilla-try     x_revs_x_added_x_copies               092fcca11bdb 936255a0384a :   0.000613 s,   0.000613 s,  +0.000000 s, × 1.0000
mozilla-try     x_revs_x00_added_x_copies             b53d2fadbdb5 017afae788ec :   0.001904 s,   0.001906 s,  +0.000002 s, × 1.0011
mozilla-try     x_revs_x000_added_x000_copies         20408ad61ce5 6f0ee96e21ad :   0.093000 s,   0.092766 s,  -0.000234 s, × 0.9975
mozilla-try     x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :   0.132194 s,   0.136074 s,  +0.003880 s, × 1.0294
mozilla-try     x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   0.009069 s,   0.009067 s,  -0.000002 s, × 0.9998
mozilla-try     x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :   0.006169 s,   0.006243 s,  +0.000074 s, × 1.0120
mozilla-try     x000_revs_x000_added_x000_copies      1346fd0130e4 4c65cbdabc1f :   0.115540 s,   0.114463 s,  -0.001077 s, × 0.9907
mozilla-try     x0000_revs_x_added_0_copies           63519bfd42ee a36a2a865d92 :   0.435381 s,   0.433683 s,  -0.001698 s, × 0.9961
mozilla-try     x0000_revs_x_added_x_copies           9fe69ff0762d bcabf2a78927 :   0.415461 s,   0.411278 s,  -0.004183 s, × 0.9899
mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :   0.155946 s,   0.155133 s,  -0.000813 s, × 0.9948
mozilla-try     x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :   0.048521 s,   0.048933 s,  +0.000412 s, × 1.0085
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :   9.843481 s,   8.100385 s,  -1.743096 s, × 0.8229
mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :   1.465128 s,   1.446720 s,  -0.018408 s, × 0.9874
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :   1.374283 s,   1.369537 s,  -0.004746 s, × 0.9965
mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 :   5.255158 s,   5.186079 s,  -0.069079 s, × 0.9869

Repo            Case                                  Source-Rev   Dest-Rev        filelog     sidedata     Difference    Factor
--------------------------------------------------------------------------------------------------------------------------------------
mercurial       x_revs_x_added_0_copies               ad6b123de1c7 39cfcef4f463 :  0.000892 s, 0.000047 s,  -0.000845 s,    × 0.052691
mercurial       x_revs_x_added_x_copies               2b1c78674230 0c1d10351869 :  0.001823 s, 0.000181 s,  -0.001642 s,    × 0.099287
mercurial       x000_revs_x000_added_x_copies         81f8ff2a9bf2 dd3267698d84 :  0.018063 s, 0.005852 s,  -0.012211 s,    × 0.323977
pypy            x_revs_x_added_0_copies               aed021ee8ae8 099ed31b181b :  0.001505 s, 0.000229 s,  -0.001276 s,    × 0.152159
pypy            x_revs_x000_added_0_copies            4aa4e1f8e19a 359343b9ac0e :  0.205895 s, 0.000058 s,  -0.205837 s,    × 0.000282
pypy            x_revs_x_added_x_copies               ac52eb7bbbb0 72e022663155 :  0.017021 s, 0.000146 s,  -0.016875 s,    × 0.008578
pypy            x_revs_x00_added_x_copies             c3b14617fbd7 ace7255d9a26 :  0.019422 s, 0.001206 s,  -0.018216 s,    × 0.062095
pypy            x_revs_x000_added_x000_copies         df6f7a526b60 a83dc6a2d56f :  0.767740 s, 0.025275 s,  -0.742465 s,    × 0.032921
pypy            x000_revs_xx00_added_0_copies         89a76aede314 2f22446ff07e :  1.188515 s, 0.080303 s,  -1.108212 s,    × 0.067566
pypy            x000_revs_x000_added_x_copies         8a3b5bfd266e 2c68e87c3efe :  1.251968 s, 0.152641 s,  -1.099327 s,    × 0.121921
pypy            x000_revs_x000_added_x000_copies      89a76aede314 7b3dda341c84 :  1.616799 s, 0.099107 s,  -1.517692 s,    × 0.061298
pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :  0.001057 s, 2.137894 s,  +2.136837 s, × 2022.605487
pypy            x0000_revs_xx000_added_0_copies       bf2c629d0071 4ffed77c095c :  1.069485 s, 0.022202 s,  -1.047283 s,    × 0.020760
pypy            x0000_revs_xx000_added_x000_copies    08ea3258278e d9fa043f30c0 :  1.350162 s, 0.228946 s,  -1.121216 s,    × 0.169569
netbeans        x_revs_x_added_0_copies               fb0955ffcbcd a01e9239f9e7 :  0.028008 s, 0.000186 s,  -0.027822 s,    × 0.006641
netbeans        x_revs_x000_added_0_copies            6f360122949f 20eb231cc7d0 :  0.132281 s, 0.000133 s,  -0.132148 s,    × 0.001005
netbeans        x_revs_x_added_x_copies               1ada3faf6fb6 5a39d12eecf4 :  0.025311 s, 0.000320 s,  -0.024991 s,    × 0.012643
netbeans        x_revs_x00_added_x_copies             35be93ba1e2c 9eec5e90c05f :  0.052957 s, 0.001339 s,  -0.051618 s,    × 0.025285
netbeans        x000_revs_xx00_added_0_copies         eac3045b4fdd 51d4ae7f1290 :  0.038011 s, 0.015694 s,  -0.022317 s,    × 0.412880
netbeans        x000_revs_x000_added_x_copies         e2063d266acd 6081d72689dc :  0.198639 s, 0.018457 s,  -0.180182 s,    × 0.092917
netbeans        x000_revs_x000_added_x000_copies      ff453e9fee32 411350406ec2 :  0.955713 s, 0.111691 s,  -0.844022 s,    × 0.116867
netbeans        x0000_revs_xx000_added_x000_copies    588c2d1ced70 1aad62e59ddd :  3.838886 s, 1.166017 s,  -2.672869 s,    × 0.303738
mozilla-central x_revs_x_added_0_copies               3697f962bb7b 7015fcdd43a2 :  0.024548 s, 0.000197 s,  -0.024351 s,    × 0.008025
mozilla-central x_revs_x000_added_0_copies            dd390860c6c9 40d0c5bed75d :  0.143394 s, 0.000626 s,  -0.142768 s,    × 0.004366
mozilla-central x_revs_x_added_x_copies               8d198483ae3b 14207ffc2b2f :  0.026046 s, 0.000303 s,  -0.025743 s,    × 0.011633
mozilla-central x_revs_x00_added_x_copies             98cbc58cc6bc 446a150332c3 :  0.085440 s, 0.001679 s,  -0.083761 s,    × 0.019651
mozilla-central x_revs_x000_added_x000_copies         3c684b4b8f68 0a5e72d1b479 :  0.195656 s, 0.006947 s,  -0.188709 s,    × 0.035506
mozilla-central x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :  2.190874 s, 0.133070 s,  -2.057804 s,    × 0.060738
mozilla-central x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :  0.090208 s, 0.008705 s,  -0.081503 s,    × 0.096499
mozilla-central x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :  0.747367 s, 0.005913 s,  -0.741454 s,    × 0.007912
mozilla-central x000_revs_x000_added_x000_copies      7c97034feb78 4407bd0c6330 :  1.152863 s, 0.101373 s,  -1.051490 s,    × 0.087932
mozilla-central x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :  6.598336 s, 0.046526 s,  -6.551810 s,    × 0.007051
mozilla-central x0000_revs_xx000_added_x000_copies    f78c615a656c 96a38b690156 :  3.255015 s, 0.313954 s,  -2.941061 s,    × 0.096452
mozilla-central x00000_revs_x0000_added_x0000_copies  6832ae71433c 4c222a1d9a00 : 15.668041 s, 3.367395 s, -12.300646 s,    × 0.214921
mozilla-central x00000_revs_x00000_added_x000_copies  76caed42cf7c 1daa622bbe42 : 20.439638 s, 4.691820 s, -15.747818 s,    × 0.229545
mozilla-try     x_revs_x_added_0_copies               aaf6dde0deb8 9790f499805a :  0.080923 s, 0.001199 s,  -0.079724 s,    × 0.014817
mozilla-try     x_revs_x000_added_0_copies            d8d0222927b4 5bb8ce8c7450 :  0.498456 s, 0.001216 s,  -0.497240 s,    × 0.002440
mozilla-try     x_revs_x_added_x_copies               092fcca11bdb 936255a0384a :  0.020798 s, 0.000613 s,  -0.020185 s,    × 0.029474
mozilla-try     x_revs_x00_added_x_copies             b53d2fadbdb5 017afae788ec :  0.226930 s, 0.001906 s,  -0.225024 s,    × 0.008399
mozilla-try     x_revs_x000_added_x000_copies         20408ad61ce5 6f0ee96e21ad :  1.113005 s, 0.092766 s,  -1.020239 s,    × 0.083347
mozilla-try     x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :  2.230671 s, 0.136074 s,  -2.094597 s,    × 0.061001
mozilla-try     x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :  0.089672 s, 0.009067 s,  -0.080605 s,    × 0.101113
mozilla-try     x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :  0.740221 s, 0.006243 s,  -0.733978 s,    × 0.008434
mozilla-try     x000_revs_x000_added_x000_copies      1346fd0130e4 4c65cbdabc1f :  1.185881 s, 0.114463 s,  -1.071418 s,    × 0.096521
mozilla-try     x0000_revs_x_added_0_copies           63519bfd42ee a36a2a865d92 :  0.086072 s, 0.433683 s,  +0.347611 s,    × 5.038607
mozilla-try     x0000_revs_x_added_x_copies           9fe69ff0762d bcabf2a78927 :  0.081321 s, 0.411278 s,  +0.329957 s,    × 5.057464
mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :  7.528370 s, 0.155133 s,  -7.373237 s,    × 0.020606
mozilla-try     x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :  6.757368 s, 0.048933 s,  -6.708435 s,    × 0.007241
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :  7.643752 s, 8.100385 s,  +0.456633 s,    × 1.059739
mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :  9.704242 s, 1.446720 s,  -8.257522 s,    × 0.149081
mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 :  0.092845 s, killed
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c : 26.626870 s, 1.369537 s, -25.257333 s,    × 0.051434
mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d :  0.092953 s, killed
mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c :  0.227131 s, killed
mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 18.884666 s, 5.186079 s, -13.698587 s,    × 0.274619
mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 21.451622 s, killed
mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 25.152558 s, killed

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

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,
}

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(),
        }
    }
}

/// 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, 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, &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 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
                    pick_minor();
                } 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.
                    pick_major();
                } 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.
                    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
}