@kevincox, thanks for the review of this and its predecessors. I think I've addressed all your remarks and improvement suggestions.

Instability fixed, and I took the opportunity to rebase again to leverage policy.importrust, that's been queued yesterday (rHGf7385ed775a8)

In D6429#94512, @kevincox wrote:

Wouldn't it be better to make add_missing_revisions work properly on empty inputs? It seems like it is too error prone to try and catch every caller. If possible I would like to push this check down as far as possible.
It seems easy enough to do in https://www.mercurial-scm.org/repo/hg/file/tip/rust/hg-core/src/discovery.rs#l56 by checking if common grew. This has the added benefit that attempting to re-add bases will also skill the work.

Bad phabsend usage, sorry.

Bad phabsend usage, sorry.

Bad phabsend usage, sorry.

Bad phabsend usage, sorry.

Bad phabsend usage, sorry.

Update of the whole series done but, ended up in an inconsistent state, and I have to go. Please don't act on it until I give the signal it's ready (sorry for inconvenience)

Also I'd like to mention that I have changesets that add more precise timing info, both for the Python variant (this one) and the Rust variant. These are the ones I used to put timing info in D6430 and D6428. I can share them, but I wouldn't submit them.

In D2647#93457, @martinvonz wrote:

In D2647#93456, @marmoute wrote:

We could maybe make it a function of both the number of heads and roots. That is not strictly the number of connected set, but that would provide a more conservative approach. That could over-sample for hour-glass shape, but they are probably less common.

The current way (only consider roots) should not over-sample, right? It still seems very effective in practice.

This revision is new. At the time I submitted the previous series, it was almost always the case that the advantage of the C reachableroots2() over the Rust `dagop::range() was more than compensated by sampling been done in Rust instead of Python.
I originally planned to finish that one and submit it as a follow-up optimization, but now it's necessary to prevent being slower in the fastest cases where there's no sampling.

@kevincox this used to be D6346
I had to fix conflict and adapt the test due to growing sample size having landed since then

@kevincox this used to be D6345

@kevincox this used to be D6261

@kevincox this used to be D6260 (I don't think I changed anything besides rebasing)

@kevincox this used to be D6257 (I don't think I changed anything besides rebasing)

I'm abandoning this revision because I have to resubmit the whole series after partial incorrect application last week and subsequent droping from the actual repo.

I'm abandoning this revision because I have to resubmit the whole series after partial incorrect application last week and subsequent droping from the actual repo.

I'm abandoning this revision because I have to resubmit the whole series after partial incorrect application last week and subsequent droping from the actual repo.

@kevincox I don't think the potential masking in tests due to this strategy is a big problem. That test is pretty recent, compared to setdiscovery, at least, and doesn't really test that sampling is very relevant. We could do better though by introducing several non random selecting strategies if we need it in the future, but this was good enough for me for the time being.

D6415 is also necessary to actually build with python3

@yuja yes indeed, just resubmitted with as_object(), thanks

I think it's maybe ready to land in that form. In the future, I'd like to put this ParentsIterator in a more generic place, and IMHO, it should become part of an AbstractGraph trait, that could live in a graph module.

@kevincox thanks for the initial review, I think I've implemented the corrections you suggested.