revset: add depth limit to descendants() (issue5374) This is naive implementation using two-pass scanning. Tracking descendants isn't an easy problem if both start and stop depths are specified. It's impractical to remember all possible depths of each node while scanning from roots to descendants because the number of depths explodes. Instead, we could cache (min, max) depths as a good approximation and track ancestors back when needed, but that's likely to have off-by-one bug. Since this implementation appears not significantly slower, and is quite straightforward, I think it's good enough for practical use cases. The time and space complexity is O(n) ish. revisions: 0) 1-pass scanning with (min, max)-depth cache (worst-case quadratic) 1) 2-pass scanning (this version) repository: mozilla-central # descendants(0) (for reference) *) 0.430353 # descendants(0, depth=1000) 0) 0.264889 1) 0.398289 # descendants(limit(tip:0, 1, offset=10000), depth=1000) 0) 0.025478 1) 0.029099 # descendants(0, depth=2000, startdepth=1000) 0) painfully slow (due to quadratic backtracking of ancestors) 1) 1.531138

dagop: make walk direction switchable so it can track descendants # ancestors(tip) using hg repo 2) 0.068527 3) 0.069097

dagop: factor out generator of ancestor nodes # ancestors(tip) using hg repo 1) 0.068976 2) 0.068527

dagop: factor out pfunc from revancestors() generator This generator will be reused for tracking descendants with depth limit. # ancestors(tip) using hg repo 0) 0.065868 1) 0.068976

dagop: use smartset.min() in revdescendants() generator All callers pass the result of revset.getset(), which should be a smartset.

dagop: change revdescendants() to include all root revisions Prepares for adding depth support. I want to process depth=0 in revdescendants() to make things simpler. only() also calls dagop.revdescendants(), but it filters out root revisions explicitly. So this should cause no problem. # descendants(0) using hg repo 0) 0.052380 1) 0.051226 # only(tip) using hg repo 0) 0.001433 1) 0.001425

test-revset: add a few more tests of descendants() I'll add depth support to descendants().