copies-rust: tokenize all paths into integer Copy information for each changesets tend to affect a small new number of path. However, each of these path might be handled a large number of time. Handling HgPathBuf (aka `Vec<u8>`) is expensive. Handling integer is cheap. With this patch we: - turn any input path into an integer "token" early, - do all the internal logic using such "token", - turn "token" back into path right before returning a result. This gives use a quite significant performance boost in our slower cases. Repo Case Source-Rev Dest-Rev # of revisions old time new time Difference Factor time per rev --------------------------------------------------------------------------------------------------------------------------------------------------------------- pypy x000_revs_x000_added_x_copies 8a3b5bfd266e 2c68e87c3efe : 6780 revs, 0.092828 s, 0.081225 s, -0.011603 s, × 0.8750, 11 µs/rev pypy x0000_revs_x_added_0_copies d1defd0dc478 c9cb1334cc78 : 43645 revs, 0.711975 s, 0.586011 s, -0.125964 s, × 0.8231, 13 µs/rev pypy x0000_revs_xx000_added_x000_copies 08ea3258278e d9fa043f30c0 : 11316 revs, 0.124505 s, 0.114173 s, -0.010332 s, × 0.9170, 10 µs/rev netbeans x000_revs_x000_added_x000_copies ff453e9fee32 411350406ec2 : 5750 revs, 0.072072 s, 0.061004 s, -0.011068 s, × 0.8464, 10 µs/rev netbeans x0000_revs_xx000_added_x000_copies 588c2d1ced70 1aad62e59ddd : 66949 revs, 0.682732 s, 0.535874 s, -0.146858 s, × 0.7849, 8 µs/rev mozilla-central x00000_revs_x0000_added_x0000_copies 6832ae71433c 4c222a1d9a00 : 153721 revs, 1.935918 s, 1.781383 s, -0.154535 s, × 0.9202, 11 µs/rev mozilla-central x00000_revs_x00000_added_x000_copies 76caed42cf7c 1daa622bbe42 : 204976 revs, 2.827320 s, 2.603867 s, -0.223453 s, × 0.9210, 12 µs/rev mozilla-try x0000_revs_xx000_added_x000_copies 89294cd501d9 7ccb2fc7ccb5 : 97052 revs, 3.243010 s, 1.529120 s, -1.713890 s, × 0.4715, 15 µs/rev mozilla-try x00000_revs_x_added_0_copies 6a320851d377 1ebb79acd503 : 363753 revs, 5.693818 s, 4.842699 s, -0.851119 s, × 0.8505, 13 µs/rev mozilla-try x00000_revs_x_added_x_copies 5173c4b6f97c 95d83ee7242d : 362229 revs, 5.677655 s, 4.761732 s, -0.915923 s, × 0.8387, 13 µs/rev mozilla-try x00000_revs_x000_added_x_copies 9126823d0e9c ca82787bb23c : 359344 revs, 5.563370 s, 4.733912 s, -0.829458 s, × 0.8509, 13 µs/rev mozilla-try x00000_revs_x0000_added_x0000_copies 8d3fafa80d4b eb884023b810 : 192665 revs, 2.864099 s, 2.593410 s, -0.270689 s, × 0.9055, 13 µs/rev mozilla-try x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs, 113.297287 s, 41.041198 s, -72.256089 s, × 0.3622, 179 µs/rev mozilla-try x00000_revs_x00000_added_x000_copies 9b2a99adc05e 8e29777b48e6 : 382065 revs, 59.498652 s, 27.915689 s, -31.582963 s, × 0.4692, 73 µs/rev Full timing comparison between this revision and the previous one: Repo Case Source-Rev Dest-Rev # of revisions old time new time Difference Factor time per rev --------------------------------------------------------------------------------------------------------------------------------------------------------------- mercurial x_revs_x_added_0_copies ad6b123de1c7 39cfcef4f463 : 1 revs, 0.000042 s, 0.000042 s, +0.000000 s, × 1.0000, 42 µs/rev mercurial x_revs_x_added_x_copies 2b1c78674230 0c1d10351869 : 6 revs, 0.000104 s, 0.000110 s, +0.000006 s, × 1.0577, 18 µs/rev mercurial x000_revs_x000_added_x_copies 81f8ff2a9bf2 dd3267698d84 : 1032 revs, 0.004913 s, 0.004918 s, +0.000005 s, × 1.0010, 4 µs/rev pypy x_revs_x_added_0_copies aed021ee8ae8 099ed31b181b : 9 revs, 0.000191 s, 0.000195 s, +0.000004 s, × 1.0209, 21 µs/rev pypy x_revs_x000_added_0_copies 4aa4e1f8e19a 359343b9ac0e : 1 revs, 0.000050 s, 0.000049 s, -0.000001 s, × 0.9800, 49 µs/rev pypy x_revs_x_added_x_copies ac52eb7bbbb0 72e022663155 : 7 revs, 0.000112 s, 0.000112 s, +0.000000 s, × 1.0000, 16 µs/rev pypy x_revs_x00_added_x_copies c3b14617fbd7 ace7255d9a26 : 1 revs, 0.000288 s, 0.000324 s, +0.000036 s, × 1.1250, 324 µs/rev pypy x_revs_x000_added_x000_copies df6f7a526b60 a83dc6a2d56f : 6 revs, 0.010411 s, 0.010611 s, +0.000200 s, × 1.0192, 1768 µs/rev pypy x000_revs_xx00_added_0_copies 89a76aede314 2f22446ff07e : 4785 revs, 0.052852 s, 0.050835 s, -0.002017 s, × 0.9618, 10 µs/rev pypy x000_revs_x000_added_x_copies 8a3b5bfd266e 2c68e87c3efe : 6780 revs, 0.092828 s, 0.081225 s, -0.011603 s, × 0.8750, 11 µs/rev pypy x000_revs_x000_added_x000_copies 89a76aede314 7b3dda341c84 : 5441 revs, 0.063269 s, 0.061291 s, -0.001978 s, × 0.9687, 11 µs/rev pypy x0000_revs_x_added_0_copies d1defd0dc478 c9cb1334cc78 : 43645 revs, 0.711975 s, 0.586011 s, -0.125964 s, × 0.8231, 13 µs/rev pypy x0000_revs_xx000_added_0_copies bf2c629d0071 4ffed77c095c : 2 revs, 0.012771 s, 0.012824 s, +0.000053 s, × 1.0042, 6412 µs/rev pypy x0000_revs_xx000_added_x000_copies 08ea3258278e d9fa043f30c0 : 11316 revs, 0.124505 s, 0.114173 s, -0.010332 s, × 0.9170, 10 µs/rev netbeans x_revs_x_added_0_copies fb0955ffcbcd a01e9239f9e7 : 2 revs, 0.000082 s, 0.000085 s, +0.000003 s, × 1.0366, 42 µs/rev netbeans x_revs_x000_added_0_copies 6f360122949f 20eb231cc7d0 : 2 revs, 0.000111 s, 0.000108 s, -0.000003 s, × 0.9730, 54 µs/rev netbeans x_revs_x_added_x_copies 1ada3faf6fb6 5a39d12eecf4 : 3 revs, 0.000171 s, 0.000175 s, +0.000004 s, × 1.0234, 58 µs/rev netbeans x_revs_x00_added_x_copies 35be93ba1e2c 9eec5e90c05f : 9 revs, 0.000708 s, 0.000719 s, +0.000011 s, × 1.0155, 79 µs/rev netbeans x000_revs_xx00_added_0_copies eac3045b4fdd 51d4ae7f1290 : 1421 revs, 0.010608 s, 0.010175 s, -0.000433 s, × 0.9592, 7 µs/rev netbeans x000_revs_x000_added_x_copies e2063d266acd 6081d72689dc : 1533 revs, 0.015635 s, 0.015569 s, -0.000066 s, × 0.9958, 10 µs/rev netbeans x000_revs_x000_added_x000_copies ff453e9fee32 411350406ec2 : 5750 revs, 0.072072 s, 0.061004 s, -0.011068 s, × 0.8464, 10 µs/rev netbeans x0000_revs_xx000_added_x000_copies 588c2d1ced70 1aad62e59ddd : 66949 revs, 0.682732 s, 0.535874 s, -0.146858 s, × 0.7849, 8 µs/rev mozilla-central x_revs_x_added_0_copies 3697f962bb7b 7015fcdd43a2 : 2 revs, 0.000090 s, 0.000090 s, +0.000000 s, × 1.0000, 45 µs/rev mozilla-central x_revs_x000_added_0_copies dd390860c6c9 40d0c5bed75d : 8 revs, 0.000210 s, 0.000281 s, +0.000071 s, × 1.3381, 35 µs/rev mozilla-central x_revs_x_added_x_copies 8d198483ae3b 14207ffc2b2f : 9 revs, 0.000182 s, 0.000187 s, +0.000005 s, × 1.0275, 20 µs/rev mozilla-central x_revs_x00_added_x_copies 98cbc58cc6bc 446a150332c3 : 7 revs, 0.000594 s, 0.000660 s, +0.000066 s, × 1.1111, 94 µs/rev mozilla-central x_revs_x000_added_x000_copies 3c684b4b8f68 0a5e72d1b479 : 3 revs, 0.003102 s, 0.003385 s, +0.000283 s, × 1.0912, 1128 µs/rev mozilla-central x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 6 revs, 0.060234 s, 0.069812 s, +0.009578 s, × 1.1590, 11635 µs/rev mozilla-central x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 1593 revs, 0.006300 s, 0.006503 s, +0.000203 s, × 1.0322, 4 µs/rev mozilla-central x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 41 revs, 0.004817 s, 0.004988 s, +0.000171 s, × 1.0355, 121 µs/rev mozilla-central x000_revs_x000_added_x000_copies 7c97034feb78 4407bd0c6330 : 7839 revs, 0.065451 s, 0.063963 s, -0.001488 s, × 0.9773, 8 µs/rev mozilla-central x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 615 revs, 0.026282 s, 0.026225 s, -0.000057 s, × 0.9978, 42 µs/rev mozilla-central x0000_revs_xx000_added_x000_copies f78c615a656c 96a38b690156 : 30263 revs, 0.206873 s, 0.201377 s, -0.005496 s, × 0.9734, 6 µs/rev mozilla-central x00000_revs_x0000_added_x0000_copies 6832ae71433c 4c222a1d9a00 : 153721 revs, 1.935918 s, 1.781383 s, -0.154535 s, × 0.9202, 11 µs/rev mozilla-central x00000_revs_x00000_added_x000_copies 76caed42cf7c 1daa622bbe42 : 204976 revs, 2.827320 s, 2.603867 s, -0.223453 s, × 0.9210, 12 µs/rev mozilla-try x_revs_x_added_0_copies aaf6dde0deb8 9790f499805a : 2 revs, 0.000842 s, 0.000845 s, +0.000003 s, × 1.0036, 422 µs/rev mozilla-try x_revs_x000_added_0_copies d8d0222927b4 5bb8ce8c7450 : 2 revs, 0.000870 s, 0.000862 s, -0.000008 s, × 0.9908, 431 µs/rev mozilla-try x_revs_x_added_x_copies 092fcca11bdb 936255a0384a : 4 revs, 0.000165 s, 0.000161 s, -0.000004 s, × 0.9758, 40 µs/rev mozilla-try x_revs_x00_added_x_copies b53d2fadbdb5 017afae788ec : 2 revs, 0.001145 s, 0.001163 s, +0.000018 s, × 1.0157, 581 µs/rev mozilla-try x_revs_x000_added_x000_copies 20408ad61ce5 6f0ee96e21ad : 1 revs, 0.026500 s, 0.032414 s, +0.005914 s, × 1.2232, 32414 µs/rev mozilla-try x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 6 revs, 0.059407 s, 0.070149 s, +0.010742 s, × 1.1808, 11691 µs/rev mozilla-try x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 1593 revs, 0.006325 s, 0.006526 s, +0.000201 s, × 1.0318, 4 µs/rev mozilla-try x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 41 revs, 0.005171 s, 0.005187 s, +0.000016 s, × 1.0031, 126 µs/rev mozilla-try x000_revs_x000_added_x000_copies 1346fd0130e4 4c65cbdabc1f : 6657 revs, 0.066837 s, 0.065047 s, -0.001790 s, × 0.9732, 9 µs/rev mozilla-try x0000_revs_x_added_0_copies 63519bfd42ee a36a2a865d92 : 40314 revs, 0.314252 s, 0.301129 s, -0.013123 s, × 0.9582, 7 µs/rev mozilla-try x0000_revs_x_added_x_copies 9fe69ff0762d bcabf2a78927 : 38690 revs, 0.304160 s, 0.280683 s, -0.023477 s, × 0.9228, 7 µs/rev mozilla-try x0000_revs_xx000_added_x_copies 156f6e2674f2 4d0f2c178e66 : 8598 revs, 0.089223 s, 0.084897 s, -0.004326 s, × 0.9515, 9 µs/rev mozilla-try x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 615 revs, 0.026711 s, 0.026620 s, -0.000091 s, × 0.9966, 43 µs/rev mozilla-try x0000_revs_xx000_added_x000_copies 89294cd501d9 7ccb2fc7ccb5 : 97052 revs, 3.243010 s, 1.529120 s, -1.713890 s, × 0.4715, 15 µs/rev mozilla-try x0000_revs_x0000_added_x0000_copies e928c65095ed e951f4ad123a : 52031 revs, 0.756500 s, 0.738709 s, -0.017791 s, × 0.9765, 14 µs/rev mozilla-try x00000_revs_x_added_0_copies 6a320851d377 1ebb79acd503 : 363753 revs, 5.693818 s, 4.842699 s, -0.851119 s, × 0.8505, 13 µs/rev mozilla-try x00000_revs_x00000_added_0_copies dc8a3ca7010e d16fde900c9c : 34414 revs, 0.590904 s, 0.596946 s, +0.006042 s, × 1.0102, 17 µs/rev mozilla-try x00000_revs_x_added_x_copies 5173c4b6f97c 95d83ee7242d : 362229 revs, 5.677655 s, 4.761732 s, -0.915923 s, × 0.8387, 13 µs/rev mozilla-try x00000_revs_x000_added_x_copies 9126823d0e9c ca82787bb23c : 359344 revs, 5.563370 s, 4.733912 s, -0.829458 s, × 0.8509, 13 µs/rev mozilla-try x00000_revs_x0000_added_x0000_copies 8d3fafa80d4b eb884023b810 : 192665 revs, 2.864099 s, 2.593410 s, -0.270689 s, × 0.9055, 13 µs/rev mozilla-try x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs, 113.297287 s, 41.041198 s, -72.256089 s, × 0.3622, 179 µs/rev mozilla-try x00000_revs_x00000_added_x000_copies 9b2a99adc05e 8e29777b48e6 : 382065 revs, 59.498652 s, 27.915689 s, -31.582963 s, × 0.4692, 73 µs/rev Full timing comparison between this revision and the filelog copy tracing. Repo Case Source-Rev Dest-Rev # of revisions filelog sidedata Difference Factor time per rev --------------------------------------------------------------------------------------------------------------------------------------------------------------- mercurial x_revs_x_added_0_copies ad6b123de1c7 39cfcef4f463 : 1 revs, 0.000903 s, 0.000042 s, -0.000861 s, × 0.0465, 41 µs/rev mercurial x_revs_x_added_x_copies 2b1c78674230 0c1d10351869 : 6 revs, 0.001861 s, 0.000110 s, -0.001751 s, × 0.0591, 18 µs/rev mercurial x000_revs_x000_added_x_copies 81f8ff2a9bf2 dd3267698d84 : 1032 revs, 0.018577 s, 0.004918 s, -0.013659 s, × 0.2647, 4 µs/rev pypy x_revs_x_added_0_copies aed021ee8ae8 099ed31b181b : 9 revs, 0.001519 s, 0.000195 s, -0.001324 s, × 0.1283, 21 µs/rev pypy x_revs_x000_added_0_copies 4aa4e1f8e19a 359343b9ac0e : 1 revs, 0.213855 s, 0.000049 s, -0.350d73 s, × 0.0002, 48 µs/rev pypy x_revs_x_added_x_copies ac52eb7bbbb0 72e022663155 : 7 revs, 0.017022 s, 0.000112 s, -0.016910 s, × 0.0065, 15 µs/rev pypy x_revs_x00_added_x_copies c3b14617fbd7 ace7255d9a26 : 1 revs, 0.019398 s, 0.000324 s, -0.019074 s, × 0.0167, 323 µs/rev pypy x_revs_x000_added_x000_copies df6f7a526b60 a83dc6a2d56f : 6 revs, 0.769467 s, 0.010611 s, -0.758856 s, × 0.0137, 1768 µs/rev pypy x000_revs_xx00_added_0_copies 89a76aede314 2f22446ff07e : 4785 revs, 1.221952 s, 0.050835 s, -1.171117 s, × 0.0416, 10 µs/rev pypy x000_revs_x000_added_x_copies 8a3b5bfd266e 2c68e87c3efe : 6780 revs, 1.304007 s, 0.081225 s, -1.222782 s, × 0.0622, 11 µs/rev pypy x000_revs_x000_added_x000_copies 89a76aede314 7b3dda341c84 : 5441 revs, 1.686610 s, 0.061291 s, -1.625319 s, × 0.0363, 11 µs/rev pypy x0000_revs_x_added_0_copies d1defd0dc478 c9cb1334cc78 : 43645 revs, 0.001107 s, 0.586011 s, +0.584904 s, × 529.36, 13 µs/rev pypy x0000_revs_xx000_added_0_copies bf2c629d0071 4ffed77c095c : 2 revs, 1.100760 s, 0.012824 s, -1.087936 s, × 0.0116, 6408 µs/rev pypy x0000_revs_xx000_added_x000_copies 08ea3258278e d9fa043f30c0 : 11316 revs, 1.350547 s, 0.114173 s, -1.236374 s, × 0.0845, 10 µs/rev netbeans x_revs_x_added_0_copies fb0955ffcbcd a01e9239f9e7 : 2 revs, 0.027864 s, 0.000085 s, -0.027779 s, × 0.0030, 42 µs/rev netbeans x_revs_x000_added_0_copies 6f360122949f 20eb231cc7d0 : 2 revs, 0.132479 s, 0.000108 s, -0.132371 s, × 0.0008, 53 µs/rev netbeans x_revs_x_added_x_copies 1ada3faf6fb6 5a39d12eecf4 : 3 revs, 0.025405 s, 0.000175 s, -0.025230 s, × 0.0068, 58 µs/rev netbeans x_revs_x00_added_x_copies 35be93ba1e2c 9eec5e90c05f : 9 revs, 0.053244 s, 0.000719 s, -0.052525 s, × 0.0135, 79 µs/rev netbeans x000_revs_xx00_added_0_copies eac3045b4fdd 51d4ae7f1290 : 1421 revs, 0.038017 s, 0.010175 s, -0.027842 s, × 0.2676, 7 µs/rev netbeans x000_revs_x000_added_x_copies e2063d266acd 6081d72689dc : 1533 revs, 0.198308 s, 0.015569 s, -0.182739 s, × 0.0785, 10 µs/rev netbeans x000_revs_x000_added_x000_copies ff453e9fee32 411350406ec2 : 5750 revs, 0.949749 s, 0.061004 s, -0.888745 s, × 0.0642, 10 µs/rev netbeans x0000_revs_xx000_added_x000_copies 588c2d1ced70 1aad62e59ddd : 66949 revs, 3.932262 s, 0.535874 s, -3.396388 s, × 0.1362, 8 µs/rev mozilla-central x_revs_x_added_0_copies 3697f962bb7b 7015fcdd43a2 : 2 revs, 0.024490 s, 0.000090 s, -0.024400 s, × 0.0036, 44 µs/rev mozilla-central x_revs_x000_added_0_copies dd390860c6c9 40d0c5bed75d : 8 revs, 0.143885 s, 0.000281 s, -0.143604 s, × 0.0019, 35 µs/rev mozilla-central x_revs_x_added_x_copies 8d198483ae3b 14207ffc2b2f : 9 revs, 0.025471 s, 0.000187 s, -0.025284 s, × 0.0073, 20 µs/rev mozilla-central x_revs_x00_added_x_copies 98cbc58cc6bc 446a150332c3 : 7 revs, 0.086013 s, 0.000660 s, -0.085353 s, × 0.0076, 94 µs/rev mozilla-central x_revs_x000_added_x000_copies 3c684b4b8f68 0a5e72d1b479 : 3 revs, 0.200726 s, 0.003385 s, -0.197341 s, × 0.0168, 1127 µs/rev mozilla-central x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 6 revs, 2.224171 s, 0.069812 s, -2.154359 s, × 0.0313, 11633 µs/rev mozilla-central x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 1593 revs, 0.090780 s, 0.006503 s, -0.084277 s, × 0.0716, 4 µs/rev mozilla-central x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 41 revs, 0.764805 s, 0.004988 s, -0.759817 s, × 0.0065, 121 µs/rev mozilla-central x000_revs_x000_added_x000_copies 7c97034feb78 4407bd0c6330 : 7839 revs, 1.161405 s, 0.063963 s, -1.097442 s, × 0.0550, 8 µs/rev mozilla-central x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 615 revs, 6.816186 s, 0.026225 s, -6.789961 s, × 0.0038, 42 µs/rev mozilla-central x0000_revs_xx000_added_x000_copies f78c615a656c 96a38b690156 : 30263 revs, 3.374819 s, 0.201377 s, -3.173442 s, × 0.0596, 6 µs/rev mozilla-central x00000_revs_x0000_added_x0000_copies 6832ae71433c 4c222a1d9a00 : 153721 revs, 16.285469 s, 1.781383 s, -14.504086 s, × 0.1093, 11 µs/rev mozilla-central x00000_revs_x00000_added_x000_copies 76caed42cf7c 1daa622bbe42 : 204976 revs, 21.207733 s, 2.603867 s, -18.603866 s, × 0.1227, 12 µs/rev mozilla-try x_revs_x_added_0_copies aaf6dde0deb8 9790f499805a : 2 revs, 0.080843 s, 0.000845 s, -0.079998 s, × 0.0104, 422 µs/rev mozilla-try x_revs_x000_added_0_copies d8d0222927b4 5bb8ce8c7450 : 2 revs, 0.511068 s, 0.000862 s, -0.510206 s, × 0.0016, 430 µs/rev mozilla-try x_revs_x_added_x_copies 092fcca11bdb 936255a0384a : 4 revs, 0.021573 s, 0.000161 s, -0.021412 s, × 0.0074, 40 µs/rev mozilla-try x_revs_x00_added_x_copies b53d2fadbdb5 017afae788ec : 2 revs, 0.227726 s, 0.001163 s, -0.226563 s, × 0.0051, 581 µs/rev mozilla-try x_revs_x000_added_x000_copies 20408ad61ce5 6f0ee96e21ad : 1 revs, 1.120448 s, 0.032414 s, -1.088034 s, × 0.0289, 32381 µs/rev mozilla-try x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 6 revs, 2.241713 s, 0.070149 s, -2.171564 s, × 0.0312, 11689 µs/rev mozilla-try x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 1593 revs, 0.090633 s, 0.006526 s, -0.084107 s, × 0.0720, 4 µs/rev mozilla-try x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 41 revs, 0.770403 s, 0.005187 s, -0.765216 s, × 0.0067, 126 µs/rev mozilla-try x000_revs_x000_added_x000_copies 1346fd0130e4 4c65cbdabc1f : 6657 revs, 1.184557 s, 0.065047 s, -1.119510 s, × 0.0549, 9 µs/rev mozilla-try x0000_revs_x_added_0_copies 63519bfd42ee a36a2a865d92 : 40314 revs, 0.085790 s, 0.301129 s, +0.215339 s, × 3.5100, 7 µs/rev mozilla-try x0000_revs_x_added_x_copies 9fe69ff0762d bcabf2a78927 : 38690 revs, 0.080616 s, 0.280683 s, +0.200067 s, × 3.4817, 7 µs/rev mozilla-try x0000_revs_xx000_added_x_copies 156f6e2674f2 4d0f2c178e66 : 8598 revs, 7.712554 s, 0.084897 s, -7.627657 s, × 0.0110, 9 µs/rev mozilla-try x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 615 revs, 6.937294 s, 0.026620 s, -6.910674 s, × 0.0038, 43 µs/rev mozilla-try x0000_revs_xx000_added_x000_copies 89294cd501d9 7ccb2fc7ccb5 : 97052 revs, 7.712313 s, 1.529120 s, -6.183193 s, × 0.1982, 15 µs/rev mozilla-try x0000_revs_x0000_added_x0000_copies e928c65095ed e951f4ad123a : 52031 revs, 9.966910 s, 0.738709 s, -9.228201 s, × 0.0741, 14 µs/rev mozilla-try x00000_revs_x_added_0_copies 6a320851d377 1ebb79acd503 : 363753 revs, 0.090397 s, 4.842699 s, +4.752302 s, × 53.571, 13 µs/rev mozilla-try x00000_revs_x00000_added_0_copies dc8a3ca7010e d16fde900c9c : 34414 revs, 27.817167 s, 0.596946 s, -27.220221 s, × 0.0214, 17 µs/rev mozilla-try x00000_revs_x_added_x_copies 5173c4b6f97c 95d83ee7242d : 362229 revs, 0.091305 s, 4.761732 s, +4.670427 s, × 52.151, 13 µs/rev mozilla-try x00000_revs_x000_added_x_copies 9126823d0e9c ca82787bb23c : 359344 revs, 0.231183 s, 4.733912 s, +4.502729 s, × 20.476, 13 µs/rev mozilla-try x00000_revs_x0000_added_x0000_copies 8d3fafa80d4b eb884023b810 : 192665 revs, 19.830617 s, 2.593410 s, -17.237207 s, × 0.1307, 13 µs/rev mozilla-try x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs, 21.743873 s, 41.041198 s, +19.297325 s, × 1.8874, 179 µs/rev mozilla-try x00000_revs_x00000_added_x000_copies 9b2a99adc05e 8e29777b48e6 : 382065 revs, 25.935037 s, 27.915689 s, +1.980652 s, × 1.0763, 73 µs/rev Differential Revision: https://phab.mercurial-scm.org/D9493

     1

use crate::utils::hg_path::HgPath;

     2

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

     3

use crate::Revision;

     4

use crate::NULL_REVISION;

     5

     6

use im_rc::ordmap::DiffItem;

     7

use im_rc::ordmap::OrdMap;

     8

     9

use std::cmp::Ordering;

    10

use std::collections::HashMap;

    11

use std::convert::TryInto;

    12

    13

pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;

    14

    15

type PathToken = usize;

    16

    17

#[derive(Clone, Debug, PartialEq, Copy)]

    18

struct TimeStampedPathCopy {

    19

    /// revision at which the copy information was added

    20

    rev: Revision,

    21

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

    22

    /// key)

    23

    path: Option<PathToken>,

    24

}

    25

    26

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

    27

type TimeStampedPathCopies = OrdMap<PathToken, TimeStampedPathCopy>;

    28

    29

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

    30

pub type RevInfo<'a> = (Revision, Revision, ChangedFiles<'a>);

    31

    32

/// represent the files affected by a changesets

    33

///

    34

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

    35

/// all the data categories tracked by it.

    36

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

    37

/// all the data categories tracked by it.

    38

pub struct ChangedFiles<'a> {

    39

    nb_items: u32,

    40

    index: &'a [u8],

    41

    data: &'a [u8],

    42

}

    43

    44

/// Represent active changes that affect the copy tracing.

    45

enum Action<'a> {

    46

    /// The parent ? children edge is removing a file

    47

    ///

    48

    /// (actually, this could be the edge from the other parent, but it does

    49

    /// not matters)

    50

    Removed(&'a HgPath),

    51

    /// The parent ? children edge introduce copy information between (dest,

    52

    /// source)

    53

    Copied(&'a HgPath, &'a HgPath),

    54

}

    55

    56

/// This express the possible "special" case we can get in a merge

    57

///

    58

/// See mercurial/metadata.py for details on these values.

    59

#[derive(PartialEq)]

    60

enum MergeCase {

    61

    /// Merged: file had history on both side that needed to be merged

    62

    Merged,

    63

    /// Salvaged: file was candidate for deletion, but survived the merge

    64

    Salvaged,

    65

    /// Normal: Not one of the two cases above

    66

    Normal,

    67

}

    68

    69

type FileChange<'a> = (u8, &'a HgPath, &'a HgPath);

    70

    71

const EMPTY: &[u8] = b"";

    72

const COPY_MASK: u8 = 3;

    73

const P1_COPY: u8 = 2;

    74

const P2_COPY: u8 = 3;

    75

const ACTION_MASK: u8 = 28;

    76

const REMOVED: u8 = 12;

    77

const MERGED: u8 = 8;

    78

const SALVAGED: u8 = 16;

    79

    80

impl<'a> ChangedFiles<'a> {

    81

    const INDEX_START: usize = 4;

    82

    const ENTRY_SIZE: u32 = 9;

    83

    const FILENAME_START: u32 = 1;

    84

    const COPY_SOURCE_START: u32 = 5;

    85

    86

    pub fn new(data: &'a [u8]) -> Self {

    87

        assert!(

    88

            data.len() >= 4,

    89

            "data size ({}) is too small to contain the header (4)",

    90

            data.len()

    91

        );

    92

        let nb_items_raw: [u8; 4] = (&data[0..=3])

    93

            .try_into()

    94

            .expect("failed to turn 4 bytes into 4 bytes");

    95

        let nb_items = u32::from_be_bytes(nb_items_raw);

    96

    97

        let index_size = (nb_items * Self::ENTRY_SIZE) as usize;

    98

        let index_end = Self::INDEX_START + index_size;

    99

   100

        assert!(

   101

            data.len() >= index_end,

   102

            "data size ({}) is too small to fit the index_data ({})",

   103

            data.len(),

   104

            index_end

   105

        );

   106

   107

        let ret = ChangedFiles {

   108

            nb_items,

   109

            index: &data[Self::INDEX_START..index_end],

   110

            data: &data[index_end..],

   111

        };

   112

        let max_data = ret.filename_end(nb_items - 1) as usize;

   113

        assert!(

   114

            ret.data.len() >= max_data,

   115

            "data size ({}) is too small to fit all data ({})",

   116

            data.len(),

   117

            index_end + max_data

   118

        );

   119

        ret

   120

    }

   121

   122

    pub fn new_empty() -> Self {

   123

        ChangedFiles {

   124

            nb_items: 0,

   125

            index: EMPTY,

   126

            data: EMPTY,

   127

        }

   128

    }

   129

   130

    /// internal function to return an individual entry at a given index

   131

    fn entry(&'a self, idx: u32) -> FileChange<'a> {

   132

        if idx >= self.nb_items {

   133

            panic!(

   134

                "index for entry is higher that the number of file {} >= {}",

   135

                idx, self.nb_items

   136

            )

   137

        }

   138

        let flags = self.flags(idx);

   139

        let filename = self.filename(idx);

   140

        let copy_idx = self.copy_idx(idx);

   141

        let copy_source = self.filename(copy_idx);

   142

        (flags, filename, copy_source)

   143

    }

   144

   145

    /// internal function to return the filename of the entry at a given index

   146

    fn filename(&self, idx: u32) -> &HgPath {

   147

        let filename_start;

   148

        if idx == 0 {

   149

            filename_start = 0;

   150

        } else {

   151

            filename_start = self.filename_end(idx - 1)

   152

        }

   153

        let filename_end = self.filename_end(idx);

   154

        let filename_start = filename_start as usize;

   155

        let filename_end = filename_end as usize;

   156

        HgPath::new(&self.data[filename_start..filename_end])

   157

    }

   158

   159

    /// internal function to return the flag field of the entry at a given

   160

    /// index

   161

    fn flags(&self, idx: u32) -> u8 {

   162

        let idx = idx as usize;

   163

        self.index[idx * (Self::ENTRY_SIZE as usize)]

   164

    }

   165

   166

    /// internal function to return the end of a filename part at a given index

   167

    fn filename_end(&self, idx: u32) -> u32 {

   168

        let start = (idx * Self::ENTRY_SIZE) + Self::FILENAME_START;

   169

        let end = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;

   170

        let start = start as usize;

   171

        let end = end as usize;

   172

        let raw = (&self.index[start..end])

   173

            .try_into()

   174

            .expect("failed to turn 4 bytes into 4 bytes");

   175

        u32::from_be_bytes(raw)

   176

    }

   177

   178

    /// internal function to return index of the copy source of the entry at a

   179

    /// given index

   180

    fn copy_idx(&self, idx: u32) -> u32 {

   181

        let start = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;

   182

        let end = (idx + 1) * Self::ENTRY_SIZE;

   183

        let start = start as usize;

   184

        let end = end as usize;

   185

        let raw = (&self.index[start..end])

   186

            .try_into()

   187

            .expect("failed to turn 4 bytes into 4 bytes");

   188

        u32::from_be_bytes(raw)

   189

    }

   190

   191

    /// Return an iterator over all the `Action` in this instance.

   192

    fn iter_actions(&self, parent: Parent) -> ActionsIterator {

   193

        ActionsIterator {

   194

            changes: &self,

   195

            parent: parent,

   196

            current: 0,

   197

        }

   198

    }

   199

   200

    /// return the MergeCase value associated with a filename

   201

    fn get_merge_case(&self, path: &HgPath) -> MergeCase {

   202

        if self.nb_items == 0 {

   203

            return MergeCase::Normal;

   204

        }

   205

        let mut low_part = 0;

   206

        let mut high_part = self.nb_items;

   207

   208

        while low_part < high_part {

   209

            let cursor = (low_part + high_part - 1) / 2;

   210

            let (flags, filename, _source) = self.entry(cursor);

   211

            match path.cmp(filename) {

   212

                Ordering::Less => low_part = cursor + 1,

   213

                Ordering::Greater => high_part = cursor,

   214

                Ordering::Equal => {

   215

                    return match flags & ACTION_MASK {

   216

                        MERGED => MergeCase::Merged,

   217

                        SALVAGED => MergeCase::Salvaged,

   218

                        _ => MergeCase::Normal,

   219

                    };

   220

                }

   221

            }

   222

        }

   223

        MergeCase::Normal

   224

    }

   225

}

   226

   227

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

   228

///

   229

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

   230

/// result.

   231

#[derive(Debug)]

   232

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

   233

    inner: &'a A,

   234

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

   235

}

   236

   237

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

   238

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

   239

        Self {

   240

            inner: func,

   241

            pairs: HashMap::default(),

   242

        }

   243

    }

   244

   245

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

   246

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

   247

        if anc > desc {

   248

            false

   249

        } else if anc == desc {

   250

            true

   251

        } else {

   252

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

   253

                *b

   254

            } else {

   255

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

   256

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

   257

                b

   258

            }

   259

        }

   260

    }

   261

}

   262

   263

struct ActionsIterator<'a> {

   264

    changes: &'a ChangedFiles<'a>,

   265

    parent: Parent,

   266

    current: u32,

   267

}

   268

   269

impl<'a> Iterator for ActionsIterator<'a> {

   270

    type Item = Action<'a>;

   271

   272

    fn next(&mut self) -> Option<Action<'a>> {

   273

        let copy_flag = match self.parent {

   274

            Parent::FirstParent => P1_COPY,

   275

            Parent::SecondParent => P2_COPY,

   276

        };

   277

        while self.current < self.changes.nb_items {

   278

            let (flags, file, source) = self.changes.entry(self.current);

   279

            self.current += 1;

   280

            if (flags & ACTION_MASK) == REMOVED {

   281

                return Some(Action::Removed(file));

   282

            }

   283

            let copy = flags & COPY_MASK;

   284

            if copy == copy_flag {

   285

                return Some(Action::Copied(file, source));

   286

            }

   287

        }

   288

        return None;

   289

    }

   290

}

   291

   292

/// A small struct whose purpose is to ensure lifetime of bytes referenced in

   293

/// ChangedFiles

   294

///

   295

/// It is passed to the RevInfoMaker callback who can assign any necessary

   296

/// content to the `data` attribute. The copy tracing code is responsible for

   297

/// keeping the DataHolder alive at least as long as the ChangedFiles object.

   298

pub struct DataHolder<D> {

   299

    /// RevInfoMaker callback should assign data referenced by the

   300

    /// ChangedFiles struct it return to this attribute. The DataHolder

   301

    /// lifetime will be at least as long as the ChangedFiles one.

   302

    pub data: Option<D>,

   303

}

   304

   305

pub type RevInfoMaker<'a, D> =

   306

    Box<dyn for<'r> Fn(Revision, &'r mut DataHolder<D>) -> RevInfo<'r> + 'a>;

   307

   308

/// enum used to carry information about the parent → child currently processed

   309

#[derive(Copy, Clone, Debug)]

   310

enum Parent {

   311

    /// The `p1(x) → x` edge

   312

    FirstParent,

   313

    /// The `p2(x) → x` edge

   314

    SecondParent,

   315

}

   316

   317

/// A small "tokenizer" responsible of turning full HgPath into lighter

   318

/// PathToken

   319

///

   320

/// Dealing with small object, like integer is much faster, so HgPath input are

   321

/// turned into integer "PathToken" and converted back in the end.

   322

#[derive(Clone, Debug, Default)]

   323

struct TwoWayPathMap {

   324

    token: HashMap<HgPathBuf, PathToken>,

   325

    path: Vec<HgPathBuf>,

   326

}

   327

   328

impl TwoWayPathMap {

   329

    fn tokenize(&mut self, path: &HgPath) -> PathToken {

   330

        match self.token.get(path) {

   331

            Some(a) => *a,

   332

            None => {

   333

                let a = self.token.len();

   334

                let buf = path.to_owned();

   335

                self.path.push(buf.clone());

   336

                self.token.insert(buf, a);

   337

                a

   338

            }

   339

        }

   340

    }

   341

   342

    fn untokenize(&self, token: PathToken) -> &HgPathBuf {

   343

        assert!(token < self.path.len(), format!("Unknown token: {}", token));

   344

        &self.path[token]