mercurial-scm/hg-stable: mercurial/ancestor.py annotate

annotate mercurial/ancestor.py @ 39490:b6db2e80a9ce

ancestors: actually iterate over ancestors in topological order (issue5979) This code previously used a dequeue logic, the first ancestors seen were the first ancestors to be emitted. In branching/merging situations, it can result in ancestors being yielded before their descendants, breaking the object contract. We got affected by this issue while working on the copy tracing code. At about the same time, Axel Hecht <axel@mozilla.com> reported the issue and provided the test case used in this changeset. Thanks Axel. Running `hg perfancestors` does not show a significant difference between the old and the new version.

author	Boris Feld <boris.feld@octobus.net>
date	Thu, 06 Sep 2018 17:00:28 -0400
parents	e7aa113b14f7
children	a60dae060bc8

rev	line source
3135 b1db258e875c Abstract ancestor algorithm into generic function Matt Mackall <mpm@selenic.com> parents: diff changeset	1 # ancestor.py - generic DAG ancestor algorithm for mercurial
b1db258e875c Abstract ancestor algorithm into generic function Matt Mackall <mpm@selenic.com> parents: diff changeset	2 #
b1db258e875c Abstract ancestor algorithm into generic function Matt Mackall <mpm@selenic.com> parents: diff changeset	3 # Copyright 2006 Matt Mackall <mpm@selenic.com>
b1db258e875c Abstract ancestor algorithm into generic function Matt Mackall <mpm@selenic.com> parents: diff changeset	4 #
8225 46293a0c7e9f updated license to be explicit about GPL version 2 Martin Geisler <mg@lazybytes.net> parents: 7882 diff changeset	5 # This software may be used and distributed according to the terms of the
10263 25e572394f5c Update license to GPLv2+ Matt Mackall <mpm@selenic.com> parents: 8465 diff changeset	6 # GNU General Public License version 2 or any later version.
3135 b1db258e875c Abstract ancestor algorithm into generic function Matt Mackall <mpm@selenic.com> parents: diff changeset	7
25915 7ef98b38163f ancestor: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25639 diff changeset	8 from __future__ import absolute_import
7ef98b38163f ancestor: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25639 diff changeset	9
20034 1e5b38a919dd cleanup: move stdlib imports to their own import statement Augie Fackler <raf@durin42.com> parents: 18987 diff changeset	10 import heapq
25915 7ef98b38163f ancestor: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25639 diff changeset	11
7ef98b38163f ancestor: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25639 diff changeset	12 from .node import nullrev
38823 e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 38596 diff changeset	13 from . import (
e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 38596 diff changeset	14 pycompat,
e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 38596 diff changeset	15 )
3135 b1db258e875c Abstract ancestor algorithm into generic function Matt Mackall <mpm@selenic.com> parents: diff changeset	16
21101 64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	17 def commonancestorsheads(pfunc, *nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	18 """Returns a set with the heads of all common ancestors of all nodes,
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	19 heads(::nodes[0] and ::nodes[1] and ...) .
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	20
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	21 pfunc must return a list of parent vertices for a given vertex.
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	22 """
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	23 if not isinstance(nodes, set):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	24 nodes = set(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	25 if nullrev in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	26 return set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	27 if len(nodes) <= 1:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	28 return nodes
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	29
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	30 allseen = (1 << len(nodes)) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	31 seen = [0] * (max(nodes) + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	32 for i, n in enumerate(nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	33 seen[n] = 1 << i
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	34 poison = 1 << (i + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	35
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	36 gca = set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	37 interesting = len(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	38 nv = len(seen) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	39 while nv >= 0 and interesting:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	40 v = nv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	41 nv -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	42 if not seen[v]:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	43 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	44 sv = seen[v]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	45 if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	46 interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	47 if sv == allseen:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	48 gca.add(v)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	49 sv \|= poison
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	50 if v in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	51 # history is linear
32331 bd872f64a8ba cleanup: use set literals Martin von Zweigbergk <martinvonz@google.com> parents: 31483 diff changeset	52 return {v}
21101 64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	53 if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	54 for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	55 sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	56 if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	57 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	58 if sp == 0:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	59 seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	60 interesting += 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	61 elif sp != sv:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	62 seen[p] \|= sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	63 else:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	64 for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	65 if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	66 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	67 sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	68 if sp and sp < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	69 interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	70 seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	71 return gca
64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	72
18986 2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	73 def ancestors(pfunc, *orignodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	74 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	75 Returns the common ancestors of a and b that are furthest from a
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	76 root (as measured by longest path).
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	77
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	78 pfunc must return a list of parent vertices for a given vertex.
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	79 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	80 def deepest(nodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	81 interesting = {}
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	82 count = max(nodes) + 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	83 depth = [0] * count
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	84 seen = [0] * count
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	85 mapping = []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	86 for (i, n) in enumerate(sorted(nodes)):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	87 depth[n] = 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	88 b = 1 << i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	89 seen[n] = b
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	90 interesting[b] = 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	91 mapping.append((b, n))
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	92 nv = count - 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	93 while nv >= 0 and len(interesting) > 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	94 v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	95 nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	96 dv = depth[v]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	97 if dv == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	98 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	99 sv = seen[v]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	100 for p in pfunc(v):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	101 if p == nullrev:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	102 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	103 dp = depth[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	104 nsp = sp = seen[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	105 if dp <= dv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	106 depth[p] = dv + 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	107 if sp != sv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	108 interesting[sv] += 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	109 nsp = seen[p] = sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	110 if sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	111 interesting[sp] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	112 if interesting[sp] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	113 del interesting[sp]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	114 elif dv == dp - 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	115 nsp = sp \| sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	116 if nsp == sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	117 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	118 seen[p] = nsp
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	119 interesting.setdefault(nsp, 0)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	120 interesting[nsp] += 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	121 interesting[sp] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	122 if interesting[sp] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	123 del interesting[sp]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	124 interesting[sv] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	125 if interesting[sv] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	126 del interesting[sv]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	127
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	128 if len(interesting) != 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	129 return []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	130
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	131 k = 0
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	132 for i in interesting:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	133 k \|= i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	134 return set(n for (i, n) in mapping if k & i)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	135
21101 64911a12dc28 ancestors: extract candidates function as commonancestorsheads Mads Kiilerich <madski@unity3d.com> parents: 20985 diff changeset	136 gca = commonancestorsheads(pfunc, *orignodes)
18986 2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	137
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	138 if len(gca) <= 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	139 return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	140 return deepest(gca)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	141
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	142 class incrementalmissingancestors(object):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	143 '''persistent state used to calculate missing ancestors incrementally
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	144
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	145 Although similar in spirit to lazyancestors below, this is a separate class
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	146 because trying to support contains and missingancestors operations with the
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	147 same internal data structures adds needless complexity.'''
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	148 def __init__(self, pfunc, bases):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	149 self.bases = set(bases)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	150 if not self.bases:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	151 self.bases.add(nullrev)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	152 self.pfunc = pfunc
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	153
23340 83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases Siddharth Agarwal <sid0@fb.com> parents: 23339 diff changeset	154 def hasbases(self):
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases Siddharth Agarwal <sid0@fb.com> parents: 23339 diff changeset	155 '''whether the common set has any non-trivial bases'''
32331 bd872f64a8ba cleanup: use set literals Martin von Zweigbergk <martinvonz@google.com> parents: 31483 diff changeset	156 return self.bases and self.bases != {nullrev}
23340 83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases Siddharth Agarwal <sid0@fb.com> parents: 23339 diff changeset	157
23341 bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object Siddharth Agarwal <sid0@fb.com> parents: 23340 diff changeset	158 def addbases(self, newbases):
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object Siddharth Agarwal <sid0@fb.com> parents: 23340 diff changeset	159 '''grow the ancestor set by adding new bases'''
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object Siddharth Agarwal <sid0@fb.com> parents: 23340 diff changeset	160 self.bases.update(newbases)
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object Siddharth Agarwal <sid0@fb.com> parents: 23340 diff changeset	161
23342 f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	162 def removeancestorsfrom(self, revs):
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	163 '''remove all ancestors of bases from the set revs (in place)'''
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	164 bases = self.bases
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	165 pfunc = self.pfunc
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	166 revs.difference_update(bases)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	167 # nullrev is always an ancestor
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	168 revs.discard(nullrev)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	169 if not revs:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	170 return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	171 # anything in revs > start is definitely not an ancestor of bases
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	172 # revs <= start needs to be investigated
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	173 start = max(bases)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	174 keepcount = sum(1 for r in revs if r > start)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	175 if len(revs) == keepcount:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	176 # no revs to consider
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	177 return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	178
38823 e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 38596 diff changeset	179 for curr in pycompat.xrange(start, min(revs) - 1, -1):
23342 f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	180 if curr not in bases:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	181 continue
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	182 revs.discard(curr)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	183 bases.update(pfunc(curr))
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	184 if len(revs) == keepcount:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	185 # no more potential revs to discard
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	186 break
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set Siddharth Agarwal <sid0@fb.com> parents: 23341 diff changeset	187
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	188 def missingancestors(self, revs):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	189 '''return all the ancestors of revs that are not ancestors of self.bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	190
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	191 This may include elements from revs.
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	192
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	193 Equivalent to the revset (::revs - ::self.bases). Revs are returned in
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	194 revision number order, which is a topological order.'''
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	195 revsvisit = set(revs)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	196 basesvisit = self.bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	197 pfunc = self.pfunc
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	198 bothvisit = revsvisit.intersection(basesvisit)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	199 revsvisit.difference_update(bothvisit)
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	200 if not revsvisit:
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	201 return []
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	202
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	203 start = max(max(revsvisit), max(basesvisit))
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	204 # At this point, we hold the invariants that:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	205 # - revsvisit is the set of nodes we know are an ancestor of at least
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	206 # one of the nodes in revs
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	207 # - basesvisit is the same for bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	208 # - bothvisit is the set of nodes we know are ancestors of at least one
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	209 # of the nodes in revs and one of the nodes in bases. bothvisit and
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	210 # revsvisit are mutually exclusive, but bothvisit is a subset of
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	211 # basesvisit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	212 # Now we walk down in reverse topo order, adding parents of nodes
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	213 # already visited to the sets while maintaining the invariants. When a
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	214 # node is found in both revsvisit and basesvisit, it is removed from
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	215 # revsvisit and added to bothvisit. When revsvisit becomes empty, there
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	216 # are no more ancestors of revs that aren't also ancestors of bases, so
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	217 # exit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	218
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	219 missing = []
38823 e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 38596 diff changeset	220 for curr in pycompat.xrange(start, nullrev, -1):
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	221 if not revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	222 break
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	223
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	224 if curr in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	225 bothvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	226 # curr's parents might have made it into revsvisit through
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	227 # another path
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	228 for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	229 revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	230 basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	231 bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	232 continue
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	233
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	234 if curr in revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	235 missing.append(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	236 revsvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	237 thisvisit = revsvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	238 othervisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	239 elif curr in basesvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	240 thisvisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	241 othervisit = revsvisit
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	242 else:
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	243 # not an ancestor of revs or bases: ignore
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	244 continue
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	245
23334 59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	246 for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	247 if p == nullrev:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	248 pass
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	249 elif p in othervisit or p in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	250 # p is implicitly in thisvisit. This means p is or should be
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	251 # in bothvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	252 revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	253 basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	254 bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	255 else:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	256 # visit later
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	257 thisvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	258
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	259 missing.reverse()
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	260 return missing
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class Siddharth Agarwal <sid0@fb.com> parents: 23333 diff changeset	261
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	262 class lazyancestors(object):
23328 3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog Siddharth Agarwal <sid0@fb.com> parents: 22225 diff changeset	263 def __init__(self, pfunc, revs, stoprev=0, inclusive=False):
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	264 """Create a new object generating ancestors for the given revs. Does
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	265 not generate revs lower than stoprev.
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	266
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	267 This is computed lazily starting from revs. The object supports
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	268 iteration and membership.
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	269
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	270 cl should be a changelog and revs should be an iterable. inclusive is
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	271 a boolean that indicates whether revs should be included. Revs lower
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	272 than stoprev will not be generated.
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	273
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	274 Result does not include the null revision."""
23328 3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog Siddharth Agarwal <sid0@fb.com> parents: 22225 diff changeset	275 self._parentrevs = pfunc
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	276 self._initrevs = revs
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	277 self._stoprev = stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	278 self._inclusive = inclusive
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	279
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	280 # Initialize data structures for __contains__.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	281 # For __contains__, we use a heap rather than a deque because
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	282 # (a) it minimizes the number of parentrevs calls made
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	283 # (b) it makes the loop termination condition obvious
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	284 # Python's heap is a min-heap. Multiply all values by -1 to convert it
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	285 # into a max-heap.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	286 self._containsvisit = [-rev for rev in revs]
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	287 heapq.heapify(self._containsvisit)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	288 if inclusive:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	289 self._containsseen = set(revs)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	290 else:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	291 self._containsseen = set()
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	292
22225 baecf4e1b7d0 ancestors: add a __nonzero__ method Pierre-Yves David <pierre-yves.david@fb.com> parents: 21101 diff changeset	293 def __nonzero__(self):
baecf4e1b7d0 ancestors: add a __nonzero__ method Pierre-Yves David <pierre-yves.david@fb.com> parents: 21101 diff changeset	294 """False if the set is empty, True otherwise."""
baecf4e1b7d0 ancestors: add a __nonzero__ method Pierre-Yves David <pierre-yves.david@fb.com> parents: 21101 diff changeset	295 try:
29216 ead25aa27a43 py3: convert to next() function timeless <timeless@mozdev.org> parents: 25915 diff changeset	296 next(iter(self))
22225 baecf4e1b7d0 ancestors: add a __nonzero__ method Pierre-Yves David <pierre-yves.david@fb.com> parents: 21101 diff changeset	297 return True
baecf4e1b7d0 ancestors: add a __nonzero__ method Pierre-Yves David <pierre-yves.david@fb.com> parents: 21101 diff changeset	298 except StopIteration:
baecf4e1b7d0 ancestors: add a __nonzero__ method Pierre-Yves David <pierre-yves.david@fb.com> parents: 21101 diff changeset	299 return False
baecf4e1b7d0 ancestors: add a __nonzero__ method Pierre-Yves David <pierre-yves.david@fb.com> parents: 21101 diff changeset	300
31483 413b44003462 py3: add __bool__ to every class defining __nonzero__ Gregory Szorc <gregory.szorc@gmail.com> parents: 29216 diff changeset	301 __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__ Gregory Szorc <gregory.szorc@gmail.com> parents: 29216 diff changeset	302
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	303 def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	304 """Generate the ancestors of _initrevs in reverse topological order.
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	305
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	306 If inclusive is False, yield a sequence of revision numbers starting
39490 b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	307 with the parents of each revision in revs, i.e., each revision is
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	308 not considered an ancestor of itself. Results are emitted in reverse
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	309 revision number order. That order is also topological: a child is
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	310 always emitted before its parent.
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	311
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	312 If inclusive is True, yield all the revs first (ignoring stoprev),
39490 b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	313 then yield all the ancestors of revs as when inclusive is False. If an
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	314 element in revs is an ancestor of a different rev it is not yielded
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	315 again."""
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	316 seen = set()
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	317 revs = self._initrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	318 if self._inclusive:
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	319 for rev in revs:
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	320 yield rev
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	321 seen.update(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	322
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	323 parentrevs = self._parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	324 stoprev = self._stoprev
39490 b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	325 visit = []
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	326 heapq.heapify(visit)
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	327 schedule = heapq.heappush
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	328 nextitem = heapq.heappop
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	329 see = seen.add
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	330 see(nullrev)
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	331
39490 b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	332 for r in revs:
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	333 for parent in parentrevs(r):
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	334 if parent not in seen:
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	335 schedule(visit, -parent)
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	336 see(parent)
25639 7125225a5287 ancestors: prefetch method outside of the loop Pierre-Yves David <pierre-yves.david@fb.com> parents: 25113 diff changeset	337
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	338 while visit:
39490 b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	339 current = -nextitem(visit)
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	340 if current >= stoprev:
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	341 yield current
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	342 for parent in parentrevs(current):
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	343 if parent not in seen:
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	344 schedule(visit, -parent)
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979) Boris Feld <boris.feld@octobus.net> parents: 38823 diff changeset	345 see(parent)
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	346
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	347 def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	348 """Test whether target is an ancestor of self._initrevs."""
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	349 # Trying to do both __iter__ and __contains__ using the same visit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	350 # heap and seen set is complex enough that it slows down both. Keep
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	351 # them separate.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	352 seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	353 if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	354 return True
38596 f8b46245b26a py3: make 'None in lazyancestors' not crash Yuya Nishihara <yuya@tcha.org> parents: 32331 diff changeset	355 # Only integer target is valid, but some callers expect 'None in self'
f8b46245b26a py3: make 'None in lazyancestors' not crash Yuya Nishihara <yuya@tcha.org> parents: 32331 diff changeset	356 # to be False. So we explicitly allow it.
f8b46245b26a py3: make 'None in lazyancestors' not crash Yuya Nishihara <yuya@tcha.org> parents: 32331 diff changeset	357 if target is None:
f8b46245b26a py3: make 'None in lazyancestors' not crash Yuya Nishihara <yuya@tcha.org> parents: 32331 diff changeset	358 return False
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	359
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	360 parentrevs = self._parentrevs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	361 visit = self._containsvisit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	362 stoprev = self._stoprev
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	363 heappop = heapq.heappop
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	364 heappush = heapq.heappush
25639 7125225a5287 ancestors: prefetch method outside of the loop Pierre-Yves David <pierre-yves.david@fb.com> parents: 25113 diff changeset	365 see = seen.add
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	366
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	367 targetseen = False
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	368
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	369 while visit and -visit[0] > target and not targetseen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	370 for parent in parentrevs(-heappop(visit)):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	371 if parent < stoprev or parent in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	372 continue
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	373 # We need to make sure we push all parents into the heap so
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	374 # that we leave it in a consistent state for future calls.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	375 heappush(visit, -parent)
25639 7125225a5287 ancestors: prefetch method outside of the loop Pierre-Yves David <pierre-yves.david@fb.com> parents: 25113 diff changeset	376 see(parent)
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	377 if parent == target:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	378 targetseen = True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	379
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	380 return targetseen

Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/ancestor.py @ 39490:b6db2e80a9ce