Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/ancestors.rs @ 45892:06b64fabf91c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
copies: cache the ancestor checking call when tracing copy A good share of the time spent in this function is spent doing ancestors checking. To avoid spending time in duplicated call, we cache the result of calls. In the slower case, this provide a quite significant performance boost. Below are the result for a set of selected pairs (many of them pathological): (And further down is another table that summarize the current state of filelog based vs changeset base copy tracing) The benchmark have been configured to be killed after 6 minutes of runtime, which mean that any detect slower than 2 minutes will be marked as "killed". This drop some useful information about how much slower these case are? but also prevent 99% of the benchmark time to be spent on case that can be labelled "very slow" anyway. Repo Case Source-Rev Dest-Rev Old-Time New-Time Difference Factor ------------------------------------------------------------------------------------------------------------------------------------ mercurial x_revs_x_added_0_copies ad6b123de1c7 39cfcef4f463 : 0.000044 s, 0.000044 s, +0.000000 s, ? 1.0000 mercurial x_revs_x_added_x_copies 2b1c78674230 0c1d10351869 : 0.000138 s, 0.000138 s, +0.000000 s, ? 1.0000 mercurial x000_revs_x000_added_x_copies 81f8ff2a9bf2 dd3267698d84 : 0.005067 s, 0.005052 s, -0.000015 s, ? 0.9970 pypy x_revs_x_added_0_copies aed021ee8ae8 099ed31b181b : 0.000218 s, 0.000219 s, +0.000001 s, ? 1.0046 pypy x_revs_x000_added_0_copies 4aa4e1f8e19a 359343b9ac0e : 0.000053 s, 0.000055 s, +0.000002 s, ? 1.0377 pypy x_revs_x_added_x_copies ac52eb7bbbb0 72e022663155 : 0.000125 s, 0.000128 s, +0.000003 s, ? 1.0240 pypy x_revs_x00_added_x_copies c3b14617fbd7 ace7255d9a26 : 0.001098 s, 0.001089 s, -0.000009 s, ? 0.9918 pypy x_revs_x000_added_x000_copies df6f7a526b60 a83dc6a2d56f : 0.017546 s, 0.017407 s, -0.000139 s, ? 0.9921 pypy x000_revs_xx00_added_0_copies 89a76aede314 2f22446ff07e : 0.096723 s, 0.094175 s, -0.002548 s, ? 0.9737 pypy x000_revs_x000_added_x_copies 8a3b5bfd266e 2c68e87c3efe : 0.271796 s, 0.238009 s, -0.033787 s, ? 0.8757 pypy x000_revs_x000_added_x000_copies 89a76aede314 7b3dda341c84 : 0.128602 s, 0.125876 s, -0.002726 s, ? 0.9788 pypy x0000_revs_x_added_0_copies d1defd0dc478 c9cb1334cc78 : 7.086742 s, 3.581556 s, -3.505186 s, ? 0.5054 pypy x0000_revs_xx000_added_0_copies bf2c629d0071 4ffed77c095c : 0.016634 s, 0.016721 s, +0.000087 s, ? 1.0052 pypy x0000_revs_xx000_added_x000_copies 08ea3258278e d9fa043f30c0 : 0.254225 s, 0.242367 s, -0.011858 s, ? 0.9534 netbeans x_revs_x_added_0_copies fb0955ffcbcd a01e9239f9e7 : 0.000166 s, 0.000165 s, -0.000001 s, ? 0.9940 netbeans x_revs_x000_added_0_copies 6f360122949f 20eb231cc7d0 : 0.000118 s, 0.000114 s, -0.000004 s, ? 0.9661 netbeans x_revs_x_added_x_copies 1ada3faf6fb6 5a39d12eecf4 : 0.000296 s, 0.000296 s, +0.000000 s, ? 1.0000 netbeans x_revs_x00_added_x_copies 35be93ba1e2c 9eec5e90c05f : 0.001137 s, 0.001124 s, -0.000013 s, ? 0.9886 netbeans x000_revs_xx00_added_0_copies eac3045b4fdd 51d4ae7f1290 : 0.014133 s, 0.013060 s, -0.001073 s, ? 0.9241 netbeans x000_revs_x000_added_x_copies e2063d266acd 6081d72689dc : 0.016988 s, 0.017112 s, +0.000124 s, ? 1.0073 netbeans x000_revs_x000_added_x000_copies ff453e9fee32 411350406ec2 : 0.676361 s, 0.660350 s, -0.016011 s, ? 0.9763 netbeans x0000_revs_xx000_added_x000_copies 588c2d1ced70 1aad62e59ddd : 12.515149 s, 10.032499 s, -2.482650 s, ? 0.8016 mozilla-central x_revs_x_added_0_copies 3697f962bb7b 7015fcdd43a2 : 0.000186 s, 0.000189 s, +0.000003 s, ? 1.0161 mozilla-central x_revs_x000_added_0_copies dd390860c6c9 40d0c5bed75d : 0.000459 s, 0.000462 s, +0.000003 s, ? 1.0065 mozilla-central x_revs_x_added_x_copies 8d198483ae3b 14207ffc2b2f : 0.000273 s, 0.000270 s, -0.000003 s, ? 0.9890 mozilla-central x_revs_x00_added_x_copies 98cbc58cc6bc 446a150332c3 : 0.001503 s, 0.001474 s, -0.000029 s, ? 0.9807 mozilla-central x_revs_x000_added_x000_copies 3c684b4b8f68 0a5e72d1b479 : 0.004862 s, 0.004806 s, -0.000056 s, ? 0.9885 mozilla-central x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 0.088291 s, 0.085150 s, -0.003141 s, ? 0.9644 mozilla-central x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 0.007113 s, 0.007064 s, -0.000049 s, ? 0.9931 mozilla-central x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 0.004687 s, 0.004741 s, +0.000054 s, ? 1.0115 mozilla-central x000_revs_x000_added_x000_copies 7c97034feb78 4407bd0c6330 : 0.198710 s, 0.190133 s, -0.008577 s, ? 0.9568 mozilla-central x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 0.036068 s, 0.035651 s, -0.000417 s, ? 0.9884 mozilla-central x0000_revs_xx000_added_x000_copies f78c615a656c 96a38b690156 : 0.465362 s, 0.440694 s, -0.024668 s, ? 0.9470 mozilla-central x00000_revs_x0000_added_x0000_copies 6832ae71433c 4c222a1d9a00 : 24.519684 s, 18.454163 s, -6.065521 s, ? 0.7526 mozilla-central x00000_revs_x00000_added_x000_copies 76caed42cf7c 1daa622bbe42 : 42.711897 s, 31.562719 s, -11.149178 s, ? 0.7390 mozilla-try x_revs_x_added_0_copies aaf6dde0deb8 9790f499805a : 0.001201 s, 0.001189 s, -0.000012 s, ? 0.9900 mozilla-try x_revs_x000_added_0_copies d8d0222927b4 5bb8ce8c7450 : 0.001216 s, 0.001204 s, -0.000012 s, ? 0.9901 mozilla-try x_revs_x_added_x_copies 092fcca11bdb 936255a0384a : 0.000595 s, 0.000586 s, -0.000009 s, ? 0.9849 mozilla-try x_revs_x00_added_x_copies b53d2fadbdb5 017afae788ec : 0.001856 s, 0.001845 s, -0.000011 s, ? 0.9941 mozilla-try x_revs_x000_added_x000_copies 20408ad61ce5 6f0ee96e21ad : 0.064936 s, 0.063822 s, -0.001114 s, ? 0.9828 mozilla-try x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 0.090601 s, 0.088038 s, -0.002563 s, ? 0.9717 mozilla-try x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 0.007510 s, 0.007389 s, -0.000121 s, ? 0.9839 mozilla-try x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 0.004911 s, 0.004868 s, -0.000043 s, ? 0.9912 mozilla-try x000_revs_x000_added_x000_copies 1346fd0130e4 4c65cbdabc1f : 0.233231 s, 0.222450 s, -0.010781 s, ? 0.9538 mozilla-try x0000_revs_x_added_0_copies 63519bfd42ee a36a2a865d92 : 0.419989 s, 0.370675 s, -0.049314 s, ? 0.8826 mozilla-try x0000_revs_x_added_x_copies 9fe69ff0762d bcabf2a78927 : 0.401521 s, 0.358020 s, -0.043501 s, ? 0.8917 mozilla-try x0000_revs_xx000_added_x_copies 156f6e2674f2 4d0f2c178e66 : 0.179555 s, 0.145235 s, -0.034320 s, ? 0.8089 mozilla-try x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 0.038004 s, 0.037606 s, -0.000398 s, ? 0.9895 mozilla-try x0000_revs_xx000_added_x000_copies 89294cd501d9 7ccb2fc7ccb5 : 52.838482 s, 7.382439 s, -45.456043 s, ? 0.1397 mozilla-try x0000_revs_x0000_added_x0000_copies e928c65095ed e951f4ad123a : 8.705874 s, 7.273506 s, -1.432368 s, ? 0.8355 mozilla-try x00000_revs_x00000_added_0_copies dc8a3ca7010e d16fde900c9c : 1.126708 s, 1.074593 s, -0.052115 s, ? 0.9537 mozilla-try x00000_revs_x0000_added_x0000_copies 8d3fafa80d4b eb884023b810 : 83.854020 s, 27.746195 s, -56.107825 s, ? 0.3309 Below is a table comparing the runtime of the current "filelog centric" algorithm, with the "changeset centric" one, we just modified. The changeset centric algorithm is a significant win in many scenario, but they are still various cases where it is quite slower. When many revision has to be considered the cost of retrieving the copy information, creating new dictionaries, merging dictionaries and checking if revision are ancestors of each other can slow things down. The rest of this series, will introduce a rust version of the copy tracing code to deal with most of theses issues. Repo Case Source-Rev Dest-Rev filelog sidedata Difference Factor --------------------------------------------------------------------------------------------------------------------------------------- mercurial x_revs_x_added_0_copies ad6b123de1c7 39cfcef4f463 : 0.000914 s, 0.000044 s, - 0.000870 s, ? 0.048140 mercurial x_revs_x_added_x_copies 2b1c78674230 0c1d10351869 : 0.001812 s, 0.000138 s, - 0.001674 s, ? 0.076159 mercurial x000_revs_x000_added_x_copies 81f8ff2a9bf2 dd3267698d84 : 0.017954 s, 0.005052 s, - 0.012902 s, ? 0.281386 pypy x_revs_x_added_0_copies aed021ee8ae8 099ed31b181b : 0.001509 s, 0.000219 s, - 0.001290 s, ? 0.145129 pypy x_revs_x000_added_0_copies 4aa4e1f8e19a 359343b9ac0e : 0.206881 s, 0.000055 s, - 0.206826 s, ? 0.000266 pypy x_revs_x_added_x_copies ac52eb7bbbb0 72e022663155 : 0.016951 s, 0.000128 s, - 0.016823 s, ? 0.007551 pypy x_revs_x00_added_x_copies c3b14617fbd7 ace7255d9a26 : 0.019096 s, 0.001089 s, - 0.018007 s, ? 0.057028 pypy x_revs_x000_added_x000_copies df6f7a526b60 a83dc6a2d56f : 0.762506 s, 0.017407 s, - 0.745099 s, ? 0.022829 pypy x000_revs_xx00_added_0_copies 89a76aede314 2f22446ff07e : 1.179211 s, 0.094175 s, - 1.085036 s, ? 0.079863 pypy x000_revs_x000_added_x_copies 8a3b5bfd266e 2c68e87c3efe : 1.249058 s, 0.238009 s, - 1.011049 s, ? 0.190551 pypy x000_revs_x000_added_x000_copies 89a76aede314 7b3dda341c84 : 1.614107 s, 0.125876 s, - 1.488231 s, ? 0.077985 pypy x0000_revs_x_added_0_copies d1defd0dc478 c9cb1334cc78 : 0.001064 s, 3.581556 s, + 3.580492 s, ? 3366.124060 pypy x0000_revs_xx000_added_0_copies bf2c629d0071 4ffed77c095c : 1.061275 s, 0.016721 s, - 1.044554 s, ? 0.015756 pypy x0000_revs_xx000_added_x000_copies 08ea3258278e d9fa043f30c0 : 1.341119 s, 0.242367 s, - 1.098752 s, ? 0.180720 netbeans x_revs_x_added_0_copies fb0955ffcbcd a01e9239f9e7 : 0.027803 s, 0.000165 s, - 0.027638 s, ? 0.005935 netbeans x_revs_x000_added_0_copies 6f360122949f 20eb231cc7d0 : 0.130014 s, 0.000114 s, - 0.129900 s, ? 0.000877 netbeans x_revs_x_added_x_copies 1ada3faf6fb6 5a39d12eecf4 : 0.024990 s, 0.000296 s, - 0.024694 s, ? 0.011845 netbeans x_revs_x00_added_x_copies 35be93ba1e2c 9eec5e90c05f : 0.052201 s, 0.001124 s, - 0.051077 s, ? 0.021532 netbeans x000_revs_xx00_added_0_copies eac3045b4fdd 51d4ae7f1290 : 0.037642 s, 0.013060 s, - 0.024582 s, ? 0.346953 netbeans x000_revs_x000_added_x_copies e2063d266acd 6081d72689dc : 0.197086 s, 0.017112 s, - 0.179974 s, ? 0.086825 netbeans x000_revs_x000_added_x000_copies ff453e9fee32 411350406ec2 : 0.935148 s, 0.660350 s, - 0.274798 s, ? 0.706145 netbeans x0000_revs_xx000_added_x000_copies 588c2d1ced70 1aad62e59ddd : 3.920674 s, 10.032499 s, + 6.111825 s, ? 2.558871 mozilla-central x_revs_x_added_0_copies 3697f962bb7b 7015fcdd43a2 : 0.024232 s, 0.000189 s, - 0.024043 s, ? 0.007800 mozilla-central x_revs_x000_added_0_copies dd390860c6c9 40d0c5bed75d : 0.141483 s, 0.000462 s, - 0.141021 s, ? 0.003265 mozilla-central x_revs_x_added_x_copies 8d198483ae3b 14207ffc2b2f : 0.025775 s, 0.000270 s, - 0.025505 s, ? 0.010475 mozilla-central x_revs_x00_added_x_copies 98cbc58cc6bc 446a150332c3 : 0.084922 s, 0.001474 s, - 0.083448 s, ? 0.017357 mozilla-central x_revs_x000_added_x000_copies 3c684b4b8f68 0a5e72d1b479 : 0.194784 s, 0.004806 s, - 0.189978 s, ? 0.024673 mozilla-central x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 2.161103 s, 0.085150 s, - 2.075953 s, ? 0.039401 mozilla-central x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 0.089347 s, 0.007064 s, - 0.082283 s, ? 0.079063 mozilla-central x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 0.732171 s, 0.004741 s, - 0.727430 s, ? 0.006475 mozilla-central x000_revs_x000_added_x000_copies 7c97034feb78 4407bd0c6330 : 1.157287 s, 0.190133 s, - 0.967154 s, ? 0.164292 mozilla-central x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 6.726568 s, 0.035651 s, - 6.690917 s, ? 0.005300 mozilla-central x0000_revs_xx000_added_x000_copies f78c615a656c 96a38b690156 : 3.266229 s, 0.440694 s, - 2.825535 s, ? 0.134924 mozilla-central x00000_revs_x0000_added_x0000_copies 6832ae71433c 4c222a1d9a00 : 15.860534 s, 18.454163 s, + 2.593629 s, ? 1.163527 mozilla-central x00000_revs_x00000_added_x000_copies 76caed42cf7c 1daa622bbe42 : 20.450475 s, 31.562719 s, +11.112244 s, ? 1.543373 mozilla-try x_revs_x_added_0_copies aaf6dde0deb8 9790f499805a : 0.080442 s, 0.001189 s, - 0.079253 s, ? 0.014781 mozilla-try x_revs_x000_added_0_copies d8d0222927b4 5bb8ce8c7450 : 0.497672 s, 0.001204 s, - 0.496468 s, ? 0.002419 mozilla-try x_revs_x_added_x_copies 092fcca11bdb 936255a0384a : 0.021183 s, 0.000586 s, - 0.020597 s, ? 0.027664 mozilla-try x_revs_x00_added_x_copies b53d2fadbdb5 017afae788ec : 0.230991 s, 0.001845 s, - 0.229146 s, ? 0.007987 mozilla-try x_revs_x000_added_x000_copies 20408ad61ce5 6f0ee96e21ad : 1.118461 s, 0.063822 s, - 1.054639 s, ? 0.057062 mozilla-try x_revs_x0000_added_x0000_copies effb563bb7e5 c07a39dc4e80 : 2.206083 s, 0.088038 s, - 2.118045 s, ? 0.039907 mozilla-try x000_revs_xx00_added_0_copies 6100d773079a 04a55431795e : 0.089404 s, 0.007389 s, - 0.082015 s, ? 0.082647 mozilla-try x000_revs_x000_added_x_copies 9f17a6fc04f9 2d37b966abed : 0.733043 s, 0.004868 s, - 0.728175 s, ? 0.006641 mozilla-try x000_revs_x000_added_x000_copies 1346fd0130e4 4c65cbdabc1f : 1.163367 s, 0.222450 s, - 0.940917 s, ? 0.191212 mozilla-try x0000_revs_x_added_0_copies 63519bfd42ee a36a2a865d92 : 0.085456 s, 0.370675 s, + 0.285219 s, ? 4.337612 mozilla-try x0000_revs_x_added_x_copies 9fe69ff0762d bcabf2a78927 : 0.083601 s, 0.358020 s, + 0.274419 s, ? 4.282485 mozilla-try x0000_revs_xx000_added_x_copies 156f6e2674f2 4d0f2c178e66 : 7.366614 s, 0.145235 s, - 7.221379 s, ? 0.019715 mozilla-try x0000_revs_xx000_added_0_copies 9eec5917337d 67118cc6dcad : 6.664464 s, 0.037606 s, - 6.626858 s, ? 0.005643 mozilla-try x0000_revs_xx000_added_x000_copies 89294cd501d9 7ccb2fc7ccb5 : 7.467836 s, 7.382439 s, - 0.085397 s, ? 0.988565 mozilla-try x0000_revs_x0000_added_x0000_copies e928c65095ed e951f4ad123a : 9.801294 s, 7.273506 s, - 2.527788 s, ? 0.742097 mozilla-try x00000_revs_x_added_0_copies 6a320851d377 1ebb79acd503 : 0.091886 s, killed mozilla-try x00000_revs_x00000_added_0_copies dc8a3ca7010e d16fde900c9c : 26.491140 s, 1.074593 s, -25.416547 s, ? 0.040564 mozilla-try x00000_revs_x_added_x_copies 5173c4b6f97c 95d83ee7242d : 0.092863 s, killed mozilla-try x00000_revs_x000_added_x_copies 9126823d0e9c ca82787bb23c : 0.226823 s, killed mozilla-try x00000_revs_x0000_added_x0000_copies 8d3fafa80d4b eb884023b810 : 18.914630 s, 27.746195 s, + 8.831565 s, ? 1.466917 mozilla-try x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 21.198903 s, killed mozilla-try x00000_revs_x00000_added_x000_copies 9b2a99adc05e 8e29777b48e6 : 24.952268 s, killed Differential Revision: https://phab.mercurial-scm.org/D9296
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Mon, 02 Nov 2020 11:03:56 +0100
parents 26114bd6ec60
children 791f5d5f7a96
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
1 // ancestors.rs
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
2 //
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
3 // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
4 //
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
5 // This software may be used and distributed according to the terms of the
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
6 // GNU General Public License version 2 or any later version.
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
7
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
8 //! Rust versions of generic DAG ancestors algorithms for Mercurial
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
9
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
10 use super::{Graph, GraphError, Revision, NULL_REVISION};
42327
e8f3740cc067 rust-filepatterns: add a Rust implementation of pattern-related utils
Rapha?l Gom?s <rgomes@octobus.net>
parents: 41717
diff changeset
11 use crate::dagops;
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
12 use std::cmp::max;
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
13 use std::collections::{BinaryHeap, HashSet};
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
14
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
15 /// Iterator over the ancestors of a given list of revisions
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
16 /// This is a generic type, defined and implemented for any Graph, so that
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
17 /// it's easy to
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
18 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
19 /// - unit test in pure Rust
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
20 /// - bind to main Mercurial code, potentially in several ways and have these
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
21 /// bindings evolve over time
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
22 pub struct AncestorsIterator<G: Graph> {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
23 graph: G,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
24 visit: BinaryHeap<Revision>,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
25 seen: HashSet<Revision>,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
26 stoprev: Revision,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
27 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
28
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
29 /// Lazy ancestors set, backed by AncestorsIterator
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
30 pub struct LazyAncestors<G: Graph + Clone> {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
31 graph: G,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
32 containsiter: AncestorsIterator<G>,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
33 initrevs: Vec<Revision>,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
34 stoprev: Revision,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
35 inclusive: bool,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
36 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
37
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
38 pub struct MissingAncestors<G: Graph> {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
39 graph: G,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
40 bases: HashSet<Revision>,
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
41 max_base: Revision,
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
42 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
43
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
44 impl<G: Graph> AncestorsIterator<G> {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
45 /// Constructor.
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
46 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
47 /// if `inclusive` is true, then the init revisions are emitted in
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
48 /// particular, otherwise iteration starts from their parents.
41105
35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator
Yuya Nishihara <yuya@tcha.org>
parents: 41104
diff changeset
49 pub fn new(
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
50 graph: G,
41105
35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator
Yuya Nishihara <yuya@tcha.org>
parents: 41104
diff changeset
51 initrevs: impl IntoIterator<Item = Revision>,
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
52 stoprev: Revision,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
53 inclusive: bool,
41105
35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator
Yuya Nishihara <yuya@tcha.org>
parents: 41104
diff changeset
54 ) -> Result<Self, GraphError> {
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
55 let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev);
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
56 if inclusive {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
57 let visit: BinaryHeap<Revision> = filtered_initrevs.collect();
44973
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
58 let seen = visit.iter().cloned().collect();
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
59 return Ok(AncestorsIterator {
44973
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
60 visit,
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
61 seen,
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
62 stoprev,
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
63 graph,
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
64 });
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
65 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
66 let mut this = AncestorsIterator {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
67 visit: BinaryHeap::new(),
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
68 seen: HashSet::new(),
44973
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
69 stoprev,
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
70 graph,
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
71 };
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
72 this.seen.insert(NULL_REVISION);
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
73 for rev in filtered_initrevs {
40933
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents: 40932
diff changeset
74 for parent in this.graph.parents(rev)?.iter().cloned() {
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents: 40932
diff changeset
75 this.conditionally_push_rev(parent);
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents: 40932
diff changeset
76 }
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
77 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
78 Ok(this)
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
79 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
80
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
81 #[inline]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
82 fn conditionally_push_rev(&mut self, rev: Revision) {
41714
70827ebba453 rust: less set lookups in AncestorsIterator
Georges Racinet <georges.racinet@octobus.net>
parents: 41246
diff changeset
83 if self.stoprev <= rev && self.seen.insert(rev) {
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
84 self.visit.push(rev);
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
85 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
86 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
87
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
88 /// Consumes partially the iterator to tell if the given target
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
89 /// revision
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
90 /// is in the ancestors it emits.
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
91 /// This is meant for iterators actually dedicated to that kind of
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
92 /// purpose
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
93 pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> {
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
94 if self.seen.contains(&target) && target != NULL_REVISION {
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
95 return Ok(true);
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
96 }
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
97 for item in self {
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
98 let rev = item?;
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
99 if rev == target {
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
100 return Ok(true);
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
101 }
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
102 if rev < target {
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
103 return Ok(false);
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
104 }
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
105 }
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
106 Ok(false)
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
107 }
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
108
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
109 pub fn peek(&self) -> Option<Revision> {
44973
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
110 self.visit.peek().cloned()
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
111 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
112
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
113 /// Tell if the iterator is about an empty set
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
114 ///
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
115 /// The result does not depend whether the iterator has been consumed
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
116 /// or not.
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
117 /// This is mostly meant for iterators backing a lazy ancestors set
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
118 pub fn is_empty(&self) -> bool {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
119 if self.visit.len() > 0 {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
120 return false;
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
121 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
122 if self.seen.len() > 1 {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
123 return false;
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
124 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
125 // at this point, the seen set is at most a singleton.
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
126 // If not `self.inclusive`, it's still possible that it has only
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
127 // the null revision
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
128 self.seen.is_empty() || self.seen.contains(&NULL_REVISION)
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
129 }
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
130 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
131
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
132 /// Main implementation for the iterator
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
133 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
134 /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
135 /// with a few non crucial differences:
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
136 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
137 /// - there's no filtering of invalid parent revisions. Actually, it should be
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
138 /// consistent and more efficient to filter them from the end caller.
40932
dc38d976ff4d rust: improved docstring
Georges Racinet <gracinet@anybox.fr>
parents: 40929
diff changeset
139 /// - we don't have the optimization for adjacent revisions (i.e., the case
dc38d976ff4d rust: improved docstring
Georges Racinet <gracinet@anybox.fr>
parents: 40929
diff changeset
140 /// where `p1 == rev - 1`), because it amounts to update the first element of
dc38d976ff4d rust: improved docstring
Georges Racinet <gracinet@anybox.fr>
parents: 40929
diff changeset
141 /// the heap without sifting, which Rust's BinaryHeap doesn't let us do.
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
142 /// - we save a few pushes by comparing with `stoprev` before pushing
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
143 impl<G: Graph> Iterator for AncestorsIterator<G> {
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
144 type Item = Result<Revision, GraphError>;
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
145
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
146 fn next(&mut self) -> Option<Self::Item> {
40811
e13ab4acf555 rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40300
diff changeset
147 let current = match self.visit.peek() {
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
148 None => {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
149 return None;
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
150 }
40811
e13ab4acf555 rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40300
diff changeset
151 Some(c) => *c,
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
152 };
40933
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents: 40932
diff changeset
153 let [p1, p2] = match self.graph.parents(current) {
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
154 Ok(ps) => ps,
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
155 Err(e) => return Some(Err(e)),
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
156 };
41714
70827ebba453 rust: less set lookups in AncestorsIterator
Georges Racinet <georges.racinet@octobus.net>
parents: 41246
diff changeset
157 if p1 < self.stoprev || !self.seen.insert(p1) {
40811
e13ab4acf555 rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40300
diff changeset
158 self.visit.pop();
e13ab4acf555 rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40300
diff changeset
159 } else {
e13ab4acf555 rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40300
diff changeset
160 *(self.visit.peek_mut().unwrap()) = p1;
e13ab4acf555 rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40300
diff changeset
161 };
e13ab4acf555 rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40300
diff changeset
162
40832
70976974c14a rust: rename local variables in AncestorsIterator::next
Georges Racinet <georges@racinet.fr>
parents: 40811
diff changeset
163 self.conditionally_push_rev(p2);
40863
443eb4bc41af rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents: 40832
diff changeset
164 Some(Ok(current))
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
165 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
166 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
167
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
168 impl<G: Graph + Clone> LazyAncestors<G> {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
169 pub fn new(
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
170 graph: G,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
171 initrevs: impl IntoIterator<Item = Revision>,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
172 stoprev: Revision,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
173 inclusive: bool,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
174 ) -> Result<Self, GraphError> {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
175 let v: Vec<Revision> = initrevs.into_iter().collect();
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
176 Ok(LazyAncestors {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
177 graph: graph.clone(),
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
178 containsiter: AncestorsIterator::new(
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
179 graph,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
180 v.iter().cloned(),
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
181 stoprev,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
182 inclusive,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
183 )?,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
184 initrevs: v,
44973
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
185 stoprev,
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
186 inclusive,
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
187 })
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
188 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
189
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
190 pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
191 self.containsiter.contains(rev)
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
192 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
193
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
194 pub fn is_empty(&self) -> bool {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
195 self.containsiter.is_empty()
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
196 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
197
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
198 pub fn iter(&self) -> AncestorsIterator<G> {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
199 // the arguments being the same as for self.containsiter, we know
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
200 // for sure that AncestorsIterator constructor can't fail
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
201 AncestorsIterator::new(
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
202 self.graph.clone(),
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
203 self.initrevs.iter().cloned(),
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
204 self.stoprev,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
205 self.inclusive,
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
206 )
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
207 .unwrap()
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
208 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
209 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
210
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
211 impl<G: Graph> MissingAncestors<G> {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
212 pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
213 let mut created = MissingAncestors {
44973
26114bd6ec60 rust: do a clippy pass
Rapha?l Gom?s <rgomes@octobus.net>
parents: 42841
diff changeset
214 graph,
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
215 bases: HashSet::new(),
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
216 max_base: NULL_REVISION,
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
217 };
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
218 created.add_bases(bases);
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
219 created
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
220 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
221
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
222 pub fn has_bases(&self) -> bool {
41716
977432970080 rust: stop putting NULL_REVISION in MissingAncestors.bases
Georges Racinet <georges.racinet@octobus.net>
parents: 41715
diff changeset
223 !self.bases.is_empty()
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
224 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
225
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
226 /// Return a reference to current bases.
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
227 ///
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
228 /// This is useful in unit tests, but also setdiscovery.py does
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
229 /// read the bases attribute of a ancestor.missingancestors instance.
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
230 pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
231 &self.bases
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
232 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
233
41246
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
234 /// Computes the relative heads of current bases.
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
235 ///
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
236 /// The object is still usable after this.
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
237 pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> {
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
238 dagops::heads(&self.graph, self.bases.iter())
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
239 }
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
240
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
241 /// Consumes the object and returns the relative heads of its bases.
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
242 pub fn into_bases_heads(
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
243 mut self,
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
244 ) -> Result<HashSet<Revision>, GraphError> {
41246
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
245 dagops::retain_heads(&self.graph, &mut self.bases)?;
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
246 Ok(self.bases)
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
247 }
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
248
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
249 /// Add some revisions to `self.bases`
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
250 ///
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
251 /// Takes care of keeping `self.max_base` up to date.
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
252 pub fn add_bases(
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
253 &mut self,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
254 new_bases: impl IntoIterator<Item = Revision>,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
255 ) {
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
256 let mut max_base = self.max_base;
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
257 self.bases.extend(
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
258 new_bases
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
259 .into_iter()
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
260 .filter(|&rev| rev != NULL_REVISION)
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
261 .map(|r| {
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
262 if r > max_base {
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
263 max_base = r;
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
264 }
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
265 r
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
266 }),
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
267 );
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
268 self.max_base = max_base;
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
269 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
270
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
271 /// Remove all ancestors of self.bases from the revs set (in place)
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
272 pub fn remove_ancestors_from(
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
273 &mut self,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
274 revs: &mut HashSet<Revision>,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
275 ) -> Result<(), GraphError> {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
276 revs.retain(|r| !self.bases.contains(r));
41716
977432970080 rust: stop putting NULL_REVISION in MissingAncestors.bases
Georges Racinet <georges.racinet@octobus.net>
parents: 41715
diff changeset
277 // the null revision is always an ancestor. Logically speaking
977432970080 rust: stop putting NULL_REVISION in MissingAncestors.bases
Georges Racinet <georges.racinet@octobus.net>
parents: 41715
diff changeset
278 // it's debatable in case bases is empty, but the Python
977432970080 rust: stop putting NULL_REVISION in MissingAncestors.bases
Georges Racinet <georges.racinet@octobus.net>
parents: 41715
diff changeset
279 // implementation always adds NULL_REVISION to bases, making it
977432970080 rust: stop putting NULL_REVISION in MissingAncestors.bases
Georges Racinet <georges.racinet@octobus.net>
parents: 41715
diff changeset
280 // unconditionnally true.
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
281 revs.remove(&NULL_REVISION);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
282 if revs.is_empty() {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
283 return Ok(());
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
284 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
285 // anything in revs > start is definitely not an ancestor of bases
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
286 // revs <= start need to be investigated
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
287 if self.max_base == NULL_REVISION {
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
288 return Ok(());
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
289 }
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
290
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
291 // whatever happens, we'll keep at least keepcount of them
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
292 // knowing this gives us a earlier stop condition than
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
293 // going all the way to the root
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
294 let keepcount = revs.iter().filter(|r| **r > self.max_base).count();
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
295
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
296 let mut curr = self.max_base;
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
297 while curr != NULL_REVISION && revs.len() > keepcount {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
298 if self.bases.contains(&curr) {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
299 revs.remove(&curr);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
300 self.add_parents(curr)?;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
301 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
302 curr -= 1;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
303 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
304 Ok(())
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
305 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
306
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
307 /// Add the parents of `rev` to `self.bases`
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
308 ///
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
309 /// This has no effect on `self.max_base`
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
310 #[inline]
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
311 fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> {
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
312 if rev == NULL_REVISION {
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
313 return Ok(());
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
314 }
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
315 for p in self.graph.parents(rev)?.iter().cloned() {
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
316 // No need to bother the set with inserting NULL_REVISION over and
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
317 // over
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
318 if p != NULL_REVISION {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
319 self.bases.insert(p);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
320 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
321 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
322 Ok(())
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
323 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
324
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
325 /// Return all the ancestors of revs that are not ancestors of self.bases
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
326 ///
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
327 /// This may include elements from revs.
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
328 ///
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
329 /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
330 /// revision number order, which is a topological order.
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
331 pub fn missing_ancestors(
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
332 &mut self,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
333 revs: impl IntoIterator<Item = Revision>,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
334 ) -> Result<Vec<Revision>, GraphError> {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
335 // just for convenience and comparison with Python version
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
336 let bases_visit = &mut self.bases;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
337 let mut revs: HashSet<Revision> = revs
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
338 .into_iter()
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
339 .filter(|r| !bases_visit.contains(r))
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
340 .collect();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
341 let revs_visit = &mut revs;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
342 let mut both_visit: HashSet<Revision> =
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
343 revs_visit.intersection(&bases_visit).cloned().collect();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
344 if revs_visit.is_empty() {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
345 return Ok(Vec::new());
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
346 }
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
347 let max_revs = revs_visit.iter().cloned().max().unwrap();
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
348 let start = max(self.max_base, max_revs);
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
349
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
350 // TODO heuristics for with_capacity()?
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
351 let mut missing: Vec<Revision> = Vec::new();
41104
247f51cfc668 rust: use .rev() for reverse range
Yuya Nishihara <yuya@tcha.org>
parents: 41054
diff changeset
352 for curr in (0..=start).rev() {
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
353 if revs_visit.is_empty() {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
354 break;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
355 }
41715
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
356 if both_visit.remove(&curr) {
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
357 // curr's parents might have made it into revs_visit through
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
358 // another path
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
359 for p in self.graph.parents(curr)?.iter().cloned() {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
360 if p == NULL_REVISION {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
361 continue;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
362 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
363 revs_visit.remove(&p);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
364 bases_visit.insert(p);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
365 both_visit.insert(p);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
366 }
41134
17a195676472 rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents: 41133
diff changeset
367 } else if revs_visit.remove(&curr) {
41131
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
368 missing.push(curr);
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
369 for p in self.graph.parents(curr)?.iter().cloned() {
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
370 if p == NULL_REVISION {
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
371 continue;
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
372 }
41715
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
373 if bases_visit.contains(&p) {
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
374 // p is already known to be an ancestor of revs_visit
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
375 revs_visit.remove(&p);
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
376 both_visit.insert(p);
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
377 } else if both_visit.contains(&p) {
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
378 // p should have been in bases_visit
41131
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
379 revs_visit.remove(&p);
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
380 bases_visit.insert(p);
41131
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
381 } else {
486908e691be rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents: 41105
diff changeset
382 // visit later
41133
a1b3800c8a19 rust-ancestors: remove unreachable conditions from missing_ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 41132
diff changeset
383 revs_visit.insert(p);
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
384 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
385 }
41132
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
386 } else if bases_visit.contains(&curr) {
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
387 for p in self.graph.parents(curr)?.iter().cloned() {
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
388 if p == NULL_REVISION {
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
389 continue;
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
390 }
41715
fccb61a1777b rust: less set lookups in MissingAncestors
Georges Racinet <georges.racinet@octobus.net>
parents: 41714
diff changeset
391 if revs_visit.remove(&p) || both_visit.contains(&p) {
41134
17a195676472 rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents: 41133
diff changeset
392 // p is an ancestor of bases_visit, and is implicitly
17a195676472 rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents: 41133
diff changeset
393 // in revs_visit, which means p is ::revs & ::bases.
41132
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
394 bases_visit.insert(p);
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
395 both_visit.insert(p);
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
396 } else {
41133
a1b3800c8a19 rust-ancestors: remove unreachable conditions from missing_ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 41132
diff changeset
397 bases_visit.insert(p);
41132
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
398 }
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents: 41131
diff changeset
399 }
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
400 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
401 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
402 missing.reverse();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
403 Ok(missing)
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
404 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
405 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
406
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
407 #[cfg(test)]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
408 mod tests {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
409
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
410 use super::*;
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
411 use crate::testing::{SampleGraph, VecGraph};
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
412 use std::iter::FromIterator;
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
413
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
414 fn list_ancestors<G: Graph>(
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
415 graph: G,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
416 initrevs: Vec<Revision>,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
417 stoprev: Revision,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
418 inclusive: bool,
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
419 ) -> Vec<Revision> {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
420 AncestorsIterator::new(graph, initrevs, stoprev, inclusive)
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
421 .unwrap()
40929
43ca24b772d6 rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents: 40927
diff changeset
422 .map(|res| res.unwrap())
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
423 .collect()
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
424 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
425
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
426 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
427 /// Same tests as test-ancestor.py, without membership
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
428 /// (see also test-ancestor.py.out)
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
429 fn test_list_ancestor() {
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
430 assert_eq!(list_ancestors(SampleGraph, vec![], 0, false), vec![]);
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
431 assert_eq!(
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
432 list_ancestors(SampleGraph, vec![11, 13], 0, false),
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
433 vec![8, 7, 4, 3, 2, 1, 0]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
434 );
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
435 assert_eq!(
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
436 list_ancestors(SampleGraph, vec![1, 3], 0, false),
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
437 vec![1, 0]
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
438 );
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
439 assert_eq!(
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
440 list_ancestors(SampleGraph, vec![11, 13], 0, true),
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
441 vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
442 );
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
443 assert_eq!(
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
444 list_ancestors(SampleGraph, vec![11, 13], 6, false),
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
445 vec![8, 7]
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
446 );
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
447 assert_eq!(
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
448 list_ancestors(SampleGraph, vec![11, 13], 6, true),
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
449 vec![13, 11, 8, 7]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
450 );
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
451 assert_eq!(
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
452 list_ancestors(SampleGraph, vec![11, 13], 11, true),
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
453 vec![13, 11]
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
454 );
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
455 assert_eq!(
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
456 list_ancestors(SampleGraph, vec![11, 13], 12, true),
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
457 vec![13]
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
458 );
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
459 assert_eq!(
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
460 list_ancestors(SampleGraph, vec![10, 1], 0, true),
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
461 vec![10, 5, 4, 2, 1, 0]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
462 );
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
463 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
464
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
465 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
466 /// Corner case that's not directly in test-ancestors.py, but
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
467 /// that happens quite often, as demonstrated by running the whole
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
468 /// suite.
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
469 /// For instance, run tests/test-obsolete-checkheads.t
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
470 fn test_nullrev_input() {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
471 let mut iter =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
472 AncestorsIterator::new(SampleGraph, vec![-1], 0, false).unwrap();
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
473 assert_eq!(iter.next(), None)
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
474 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
475
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
476 #[test]
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
477 fn test_contains() {
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
478 let mut lazy =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
479 AncestorsIterator::new(SampleGraph, vec![10, 1], 0, true).unwrap();
40929
43ca24b772d6 rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents: 40927
diff changeset
480 assert!(lazy.contains(1).unwrap());
43ca24b772d6 rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents: 40927
diff changeset
481 assert!(!lazy.contains(3).unwrap());
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
482
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
483 let mut lazy =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
484 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
40929
43ca24b772d6 rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents: 40927
diff changeset
485 assert!(!lazy.contains(NULL_REVISION).unwrap());
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
486 }
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40271
diff changeset
487
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
488 #[test]
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
489 fn test_peek() {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
490 let mut iter =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
491 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
492 // peek() gives us the next value
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
493 assert_eq!(iter.peek(), Some(10));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
494 // but it's not been consumed
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
495 assert_eq!(iter.next(), Some(Ok(10)));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
496 // and iteration resumes normally
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
497 assert_eq!(iter.next(), Some(Ok(5)));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
498
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
499 // let's drain the iterator to test peek() at the end
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
500 while iter.next().is_some() {}
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
501 assert_eq!(iter.peek(), None);
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
502 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
503
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
504 #[test]
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
505 fn test_empty() {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
506 let mut iter =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
507 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
508 assert!(!iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
509 while iter.next().is_some() {}
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
510 assert!(!iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
511
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
512 let iter =
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
513 AncestorsIterator::new(SampleGraph, vec![], 0, true).unwrap();
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
514 assert!(iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
515
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
516 // case where iter.seen == {NULL_REVISION}
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
517 let iter =
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
518 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
519 assert!(iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
520 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
521
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
522 /// A corrupted Graph, supporting error handling tests
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
523 #[derive(Clone, Debug)]
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
524 struct Corrupted;
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
525
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
526 impl Graph for Corrupted {
40933
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents: 40932
diff changeset
527 fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
528 match rev {
40933
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents: 40932
diff changeset
529 1 => Ok([0, -1]),
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
530 r => Err(GraphError::ParentOutOfRange(r)),
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
531 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
532 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
533 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
534
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
535 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
536 fn test_initrev_out_of_range() {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
537 // inclusive=false looks up initrev's parents right away
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
538 match AncestorsIterator::new(SampleGraph, vec![25], 0, false) {
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
539 Ok(_) => panic!("Should have been ParentOutOfRange"),
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
540 Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)),
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
541 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
542 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
543
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
544 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
545 fn test_next_out_of_range() {
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
546 // inclusive=false looks up initrev's parents right away
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
547 let mut iter =
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
548 AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap();
40929
43ca24b772d6 rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents: 40927
diff changeset
549 assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0))));
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
550 }
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
551
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
552 #[test]
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
553 fn test_lazy_iter_contains() {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
554 let mut lazy =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
555 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap();
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
556
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
557 let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
558 // compare with iterator tests on the same initial revisions
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
559 assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
560
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
561 // contains() results are correct, unaffected by the fact that
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
562 // we consumed entirely an iterator out of lazy
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
563 assert_eq!(lazy.contains(2), Ok(true));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
564 assert_eq!(lazy.contains(9), Ok(false));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
565 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
566
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
567 #[test]
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
568 fn test_lazy_contains_iter() {
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
569 let mut lazy =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
570 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0]
41054
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
571
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
572 assert_eq!(lazy.contains(2), Ok(true));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
573 assert_eq!(lazy.contains(6), Ok(false));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
574
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
575 // after consumption of 2 by the inner iterator, results stay
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
576 // consistent
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
577 assert_eq!(lazy.contains(2), Ok(true));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
578 assert_eq!(lazy.contains(5), Ok(false));
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
579
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
580 // iter() still gives us a fresh iterator
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
581 let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
582 assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
583 }
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
584
ef54bd33b476 rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40959
diff changeset
585 #[test]
41246
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
586 /// Test constructor, add/get bases and heads
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
587 fn test_missing_bases() -> Result<(), GraphError> {
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
588 let mut missing_ancestors =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
589 MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
590 let mut as_vec: Vec<Revision> =
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
591 missing_ancestors.get_bases().iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
592 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
593 assert_eq!(as_vec, [1, 3, 5]);
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
594 assert_eq!(missing_ancestors.max_base, 5);
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
595
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
596 missing_ancestors.add_bases([3, 7, 8].iter().cloned());
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
597 as_vec = missing_ancestors.get_bases().iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
598 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
599 assert_eq!(as_vec, [1, 3, 5, 7, 8]);
41717
9060af281be7 rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents: 41716
diff changeset
600 assert_eq!(missing_ancestors.max_base, 8);
41246
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
601
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
602 as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect();
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
603 as_vec.sort();
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
604 assert_eq!(as_vec, [3, 5, 7, 8]);
619ee4039bd4 rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41241
diff changeset
605 Ok(())
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
606 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
607
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
608 fn assert_missing_remove(
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
609 bases: &[Revision],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
610 revs: &[Revision],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
611 expected: &[Revision],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
612 ) {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
613 let mut missing_ancestors =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
614 MissingAncestors::new(SampleGraph, bases.iter().cloned());
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
615 let mut revset: HashSet<Revision> = revs.iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
616 missing_ancestors
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
617 .remove_ancestors_from(&mut revset)
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
618 .unwrap();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
619 let mut as_vec: Vec<Revision> = revset.into_iter().collect();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
620 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
621 assert_eq!(as_vec.as_slice(), expected);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
622 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
623
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
624 #[test]
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
625 fn test_missing_remove() {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
626 assert_missing_remove(
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
627 &[1, 2, 3, 4, 7],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
628 Vec::from_iter(1..10).as_slice(),
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
629 &[5, 6, 8, 9],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
630 );
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
631 assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
632 assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
633 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
634
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
635 fn assert_missing_ancestors(
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
636 bases: &[Revision],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
637 revs: &[Revision],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
638 expected: &[Revision],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
639 ) {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
640 let mut missing_ancestors =
41241
168041fa6d5f rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents: 41134
diff changeset
641 MissingAncestors::new(SampleGraph, bases.iter().cloned());
40959
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
642 let missing = missing_ancestors
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
643 .missing_ancestors(revs.iter().cloned())
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
644 .unwrap();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
645 assert_eq!(missing.as_slice(), expected);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
646 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
647
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
648 #[test]
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
649 fn test_missing_ancestors() {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
650 // examples taken from test-ancestors.py by having it run
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
651 // on the same graph (both naive and fast Python algs)
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
652 assert_missing_ancestors(&[10], &[11], &[3, 7, 11]);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
653 assert_missing_ancestors(&[11], &[10], &[5, 10]);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
654 assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
655 }
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
656
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
657 /// An interesting case found by a random generator similar to
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
658 /// the one in test-ancestor.py. An early version of Rust MissingAncestors
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
659 /// failed this, yet none of the integration tests of the whole suite
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
660 /// catched it.
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
661 #[test]
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
662 fn test_remove_ancestors_from_case1() {
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
663 let graph: VecGraph = vec![
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
664 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
665 [0, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
666 [1, 0],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
667 [2, 1],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
668 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
669 [4, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
670 [5, 1],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
671 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
672 [7, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
673 [8, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
674 [9, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
675 [10, 1],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
676 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
677 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
678 [13, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
679 [14, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
680 [4, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
681 [16, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
682 [17, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
683 [18, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
684 [19, 11],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
685 [20, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
686 [21, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
687 [22, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
688 [23, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
689 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
690 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
691 [26, 24],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
692 [27, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
693 [28, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
694 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
695 [1, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
696 [1, 9],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
697 [32, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
698 [33, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
699 [34, 31],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
700 [35, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
701 [36, 26],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
702 [37, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
703 [38, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
704 [39, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
705 [40, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
706 [41, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
707 [42, 26],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
708 [0, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
709 [44, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
710 [45, 4],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
711 [40, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
712 [47, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
713 [36, 0],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
714 [49, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
715 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
716 [51, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
717 [52, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
718 [53, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
719 [14, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
720 [55, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
721 [15, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
722 [23, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
723 [58, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
724 [59, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
725 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
726 [61, 59],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
727 [62, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
728 [63, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
729 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
730 [65, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
731 [66, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
732 [67, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
733 [68, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
734 [37, 28],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
735 [69, 25],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
736 [71, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
737 [72, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
738 [50, 2],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
739 [74, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
740 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
741 [18, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
742 [77, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
743 [78, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
744 [79, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
745 [43, 33],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
746 [81, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
747 [82, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
748 [83, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
749 [84, 45],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
750 [85, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
751 [86, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
752 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
753 [88, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
754 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
755 [76, 83],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
756 [44, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
757 [92, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
758 [93, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
759 [9, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
760 [95, 67],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
761 [96, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
762 [97, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
763 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
764 ];
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
765 let problem_rev = 28 as Revision;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
766 let problem_base = 70 as Revision;
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
767 // making the problem obvious: problem_rev is a parent of problem_base
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
768 assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
769
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
770 let mut missing_ancestors: MissingAncestors<VecGraph> =
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
771 MissingAncestors::new(
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
772 graph,
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
773 [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6]
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
774 .iter()
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
775 .cloned(),
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
776 );
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
777 assert!(missing_ancestors.bases.contains(&problem_base));
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
778
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
779 let mut revs: HashSet<Revision> =
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
780 [4, 12, 41, 28, 68, 38, 1, 30, 56, 44]
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
781 .iter()
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
782 .cloned()
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
783 .collect();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
784 missing_ancestors.remove_ancestors_from(&mut revs).unwrap();
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
785 assert!(!revs.contains(&problem_rev));
d097dd0afc19 rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents: 40933
diff changeset
786 }
40271
dbc28c91f7ff rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff changeset
787 }