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

     1

use crate::utils::hg_path::HgPathBuf;

     2

use crate::Revision;

     3

     4

use im_rc::ordmap::DiffItem;

     5

use im_rc::ordmap::OrdMap;

     6

     7

use std::collections::HashMap;

     8

use std::collections::HashSet;

     9

    10

pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;

    11

    12

#[derive(Clone, Debug, PartialEq)]

    13

struct TimeStampedPathCopy {

    14

    /// revision at which the copy information was added

    15

    rev: Revision,

    16

    /// the copy source, (Set to None in case of deletion of the associated

    17

    /// key)

    18

    path: Option<HgPathBuf>,

    19

}

    20

    21

/// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)

    22

type TimeStampedPathCopies = OrdMap<HgPathBuf, TimeStampedPathCopy>;

    23

    24

/// hold parent 1, parent 2 and relevant files actions.

    25

pub type RevInfo = (Revision, Revision, ChangedFiles);

    26

    27

/// represent the files affected by a changesets

    28

///

    29

/// This hold a subset of mercurial.metadata.ChangingFiles as we do not need

    30

/// all the data categories tracked by it.

    31

pub struct ChangedFiles {

    32

    removed: HashSet<HgPathBuf>,

    33

    merged: HashSet<HgPathBuf>,

    34

    salvaged: HashSet<HgPathBuf>,

    35

    copied_from_p1: PathCopies,

    36

    copied_from_p2: PathCopies,

    37

}

    38

    39

impl ChangedFiles {

    40

    pub fn new(

    41

        removed: HashSet<HgPathBuf>,

    42

        merged: HashSet<HgPathBuf>,

    43

        salvaged: HashSet<HgPathBuf>,

    44

        copied_from_p1: PathCopies,

    45

        copied_from_p2: PathCopies,

    46

    ) -> Self {

    47

        ChangedFiles {

    48

            removed,

    49

            merged,

    50

            salvaged,

    51

            copied_from_p1,

    52

            copied_from_p2,

    53

        }

    54

    }

    55

    56

    pub fn new_empty() -> Self {

    57

        ChangedFiles {

    58

            removed: HashSet::new(),

    59

            merged: HashSet::new(),

    60

            salvaged: HashSet::new(),

    61

            copied_from_p1: PathCopies::new(),

    62

            copied_from_p2: PathCopies::new(),

    63

        }

    64

    }

    65

}

    66

    67

/// A struct responsible for answering "is X ancestors of Y" quickly

    68

///

    69

/// The structure will delegate ancestors call to a callback, and cache the

    70

/// result.

    71

#[derive(Debug)]

    72

struct AncestorOracle<'a, A: Fn(Revision, Revision) -> bool> {

    73

    inner: &'a A,

    74

    pairs: HashMap<(Revision, Revision), bool>,

    75

}

    76

    77

impl<'a, A: Fn(Revision, Revision) -> bool> AncestorOracle<'a, A> {

    78

    fn new(func: &'a A) -> Self {

    79

        Self {

    80

            inner: func,

    81

            pairs: HashMap::default(),

    82

        }

    83

    }

    84

    85

    /// returns `true` if `anc` is an ancestors of `desc`, `false` otherwise

    86

    fn is_ancestor(&mut self, anc: Revision, desc: Revision) -> bool {

    87

        if anc > desc {

    88

            false

    89

        } else if anc == desc {

    90

            true

    91

        } else {

    92

            if let Some(b) = self.pairs.get(&(anc, desc)) {

    93

                *b

    94

            } else {

    95

                let b = (self.inner)(anc, desc);

    96

                self.pairs.insert((anc, desc), b);

    97

                b

    98

            }

    99

        }

   100

    }

   101

}

   102

   103

/// Same as mercurial.copies._combine_changeset_copies, but in Rust.

   104

///

   105

/// Arguments are:

   106

///

   107

/// revs: all revisions to be considered

   108

/// children: a {parent ? [childrens]} mapping

   109

/// target_rev: the final revision we are combining copies to

   110

/// rev_info(rev): callback to get revision information:

   111

///   * first parent

   112

///   * second parent

   113

///   * ChangedFiles

   114

/// isancestors(low_rev, high_rev): callback to check if a revision is an

   115

///                                 ancestor of another

   116

pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool>(

   117

    revs: Vec<Revision>,

   118

    children: HashMap<Revision, Vec<Revision>>,

   119

    target_rev: Revision,

   120

    rev_info: &impl Fn(Revision) -> RevInfo,

   121

    is_ancestor: &A,

   122

) -> PathCopies {

   123

    let mut all_copies = HashMap::new();

   124

    let mut oracle = AncestorOracle::new(is_ancestor);

   125

   126

    for rev in revs {

   127

        // Retrieve data computed in a previous iteration

   128

        let copies = all_copies.remove(&rev);

   129

        let copies = match copies {

   130

            Some(c) => c,

   131

            None => TimeStampedPathCopies::default(), // root of the walked set

   132

        };

   133

   134

        let current_children = match children.get(&rev) {

   135

            Some(c) => c,

   136

            None => panic!("inconsistent `revs` and `children`"),

   137

        };

   138

   139

        for child in current_children {

   140

            // We will chain the copies information accumulated for `rev` with

   141

            // the individual copies information for each of its children.

   142

            // Creating a new PathCopies for each `rev` ? `children` vertex.

   143

            let (p1, p2, changes) = rev_info(*child);

   144

   145

            let (parent, child_copies) = if rev == p1 {

   146

                (1, &changes.copied_from_p1)

   147

            } else {

   148

                assert_eq!(rev, p2);

   149

                (2, &changes.copied_from_p2)

   150

            };

   151

            let mut new_copies = copies.clone();

   152

   153

            for (dest, source) in child_copies {

   154

                let entry;

   155

                if let Some(v) = copies.get(source) {

   156

                    entry = match &v.path {

   157

                        Some(path) => Some((*(path)).to_owned()),

   158

                        None => Some(source.to_owned()),

   159

                    }

   160

                } else {

   161

                    entry = Some(source.to_owned());

   162

                }

   163

                // Each new entry is introduced by the children, we record this

   164

                // information as we will need it to take the right decision

   165

                // when merging conflicting copy information. See

   166

                // merge_copies_dict for details.

   167

                let ttpc = TimeStampedPathCopy {

   168

                    rev: *child,

   169

                    path: entry,

   170

                };

   171

                new_copies.insert(dest.to_owned(), ttpc);

   172

            }

   173

   174

            // We must drop copy information for removed file.

   175

            //

   176

            // We need to explicitly record them as dropped to propagate this

   177

            // information when merging two TimeStampedPathCopies object.

   178

            for f in changes.removed.iter() {

   179

                if new_copies.contains_key(f.as_ref()) {

   180

                    let ttpc = TimeStampedPathCopy {

   181

                        rev: *child,

   182

                        path: None,

   183

                    };

   184

                    new_copies.insert(f.to_owned(), ttpc);

   185

                }

   186

            }

   187

   188

            // Merge has two parents needs to combines their copy information.

   189

            //

   190

            // If the vertex from the other parent was already processed, we

   191

            // will have a value for the child ready to be used. We need to

   192

            // grab it and combine it with the one we already

   193

            // computed. If not we can simply store the newly

   194

            // computed data. The processing happening at

   195

            // the time of the second parent will take care of combining the

   196

            // two TimeStampedPathCopies instance.

   197

            match all_copies.remove(child) {

   198

                None => {

   199

                    all_copies.insert(child, new_copies);

   200

                }

   201

                Some(other_copies) => {

   202

                    let (minor, major) = match parent {

   203

                        1 => (other_copies, new_copies),

   204

                        2 => (new_copies, other_copies),

   205

                        _ => unreachable!(),

   206

                    };

   207

                    let merged_copies =

   208

                        merge_copies_dict(minor, major, &changes, &mut oracle);

   209

                    all_copies.insert(child, merged_copies);

   210

                }

   211

            };

   212

        }

   213

    }

   214

   215

    // Drop internal information (like the timestamp) and return the final

   216

    // mapping.

   217

    let tt_result = all_copies

   218

        .remove(&target_rev)

   219

        .expect("target revision was not processed");

   220

    let mut result = PathCopies::default();

   221

    for (dest, tt_source) in tt_result {

   222

        if let Some(path) = tt_source.path {

   223

            result.insert(dest, path);

   224

        }

   225

    }

   226

    result

   227

}

   228

   229

/// merge two copies-mapping together, minor and major

   230

///

   231

/// In case of conflict, value from "major" will be picked, unless in some

   232

/// cases. See inline documentation for details.

   233

#[allow(clippy::if_same_then_else)]

   234

fn merge_copies_dict<A: Fn(Revision, Revision) -> bool>(

   235

    minor: TimeStampedPathCopies,

   236

    major: TimeStampedPathCopies,

   237

    changes: &ChangedFiles,

   238

    oracle: &mut AncestorOracle<A>,

   239

) -> TimeStampedPathCopies {

   240

    if minor.is_empty() {

   241

        return major;

   242

    } else if major.is_empty() {

   243

        return minor;

   244

    }

   245

    let mut override_minor = Vec::new();

   246

    let mut override_major = Vec::new();

   247

   248

    let mut to_major = |k: &HgPathBuf, v: &TimeStampedPathCopy| {

   249

        override_major.push((k.clone(), v.clone()))

   250

    };

   251

    let mut to_minor = |k: &HgPathBuf, v: &TimeStampedPathCopy| {

   252

        override_minor.push((k.clone(), v.clone()))

   253

    };

   254

   255

    // The diff function leverage detection of the identical subpart if minor

   256

    // and major has some common ancestors. This make it very fast is most

   257

    // case.

   258

    //

   259

    // In case where the two map are vastly different in size, the current

   260

    // approach is still slowish because the iteration will iterate over

   261

    // all the "exclusive" content of the larger on. This situation can be

   262

    // frequent when the subgraph of revision we are processing has a lot

   263

    // of roots. Each roots adding they own fully new map to the mix (and

   264

    // likely a small map, if the path from the root to the "main path" is

   265

    // small.

   266

    //

   267

    // We could do better by detecting such situation and processing them

   268

    // differently.

   269

    for d in minor.diff(&major) {

   270

        match d {

   271

            DiffItem::Add(k, v) => to_minor(k, v),

   272

            DiffItem::Remove(k, v) => to_major(k, v),

   273

            DiffItem::Update { old, new } => {

   274

                let (dest, src_major) = new;

   275

                let (_, src_minor) = old;

   276

                let mut pick_minor = || (to_major(dest, src_minor));

   277

                let mut pick_major = || (to_minor(dest, src_major));

   278

                if src_major.path == src_minor.path {

   279

                    // we have the same value, but from other source;

   280

                    if src_major.rev == src_minor.rev {

   281

                        // If the two entry are identical, no need to do

   282

                        // anything (but diff should not have yield them)

   283

                        unreachable!();

   284

                    } else if oracle.is_ancestor(src_major.rev, src_minor.rev)

   285

                    {

   286

                        pick_minor();

   287

                    } else {

   288

                        pick_major();

   289

                    }

   290

                } else if src_major.rev == src_minor.rev {

   291

                    // We cannot get copy information for both p1 and p2 in the

   292

                    // same rev. So this is the same value.

   293

                    unreachable!();

   294

                } else if src_major.path.is_none()

   295

                    && changes.salvaged.contains(dest)

   296

                {

   297

                    // If the file is "deleted" in the major side but was

   298

                    // salvaged by the merge, we keep the minor side alive

   299

                    pick_minor();

   300

                } else if src_minor.path.is_none()

   301

                    && changes.salvaged.contains(dest)

   302

                {

   303

                    // If the file is "deleted" in the minor side but was

   304

                    // salvaged by the merge, unconditionnaly preserve the

   305

                    // major side.

   306

                    pick_major();

   307

                } else if changes.merged.contains(dest) {

   308

                    // If the file was actively merged, copy information from

   309

                    // each side might conflict.  The major side will win such

   310

                    // conflict.

   311

                    pick_major();

   312

                } else if oracle.is_ancestor(src_major.rev, src_minor.rev) {

   313

                    // If the minor side is strictly newer than the major side,

   314

                    // it should be kept.

   315

                    pick_minor();

   316

                } else if src_major.path.is_some() {

   317

                    // without any special case, the "major" value win other

   318

                    // the "minor" one.

   319

                    pick_major();

   320

                } else if oracle.is_ancestor(src_minor.rev, src_major.rev) {

   321

                    // the "major" rev is a direct ancestors of "minor", any

   322

                    // different value should overwrite

   323

                    pick_major();

   324

                } else {

   325

                    // major version is None (so the file was deleted on that

   326

                    // branch) and that branch is independant (neither minor

   327

                    // nor major is an ancestors of the other one.) We preserve

   328

                    // the new information about the new file.

   329

                    pick_minor();

   330

                }

   331

            }

   332

        };

   333

    }

   334

   335

    let updates;

   336

    let mut result;

   337

    if override_major.is_empty() {

   338

        result = major

   339

    } else if override_minor.is_empty() {

   340

        result = minor

   341

    } else {

   342

        if override_minor.len() < override_major.len() {

   343

            updates = override_minor;

   344

            result = minor;

   345

        } else {

   346

            updates = override_major;

   347

            result = major;

   348

        }

   349

        for (k, v) in updates {

   350

            result.insert(k, v);

   351

        }

   352

    }

   353

    result

   354

}