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

annotate mercurial/ancestor.py @ 20985:231ccc08670c

ancestor: remove unused genericancestor

author	Mads Kiilerich <madski@unity3d.com>
date	Thu, 20 Mar 2014 01:35:07 +0100
parents	4add43865a9b
children	64911a12dc28

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
20034 1e5b38a919dd cleanup: move stdlib imports to their own import statement Augie Fackler <raf@durin42.com> parents: 18987 diff changeset	8 import heapq
1e5b38a919dd cleanup: move stdlib imports to their own import statement Augie Fackler <raf@durin42.com> parents: 18987 diff changeset	9 import util
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	10 from node import nullrev
3135 b1db258e875c Abstract ancestor algorithm into generic function Matt Mackall <mpm@selenic.com> parents: diff changeset	11
18986 2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	12 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	13 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	14 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	15 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	16
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	17 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	18 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	19 if not isinstance(orignodes, set):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	20 orignodes = set(orignodes)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	21 if nullrev in orignodes:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	22 return set()
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	23 if len(orignodes) <= 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	24 return orignodes
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	25
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	26 def candidates(nodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	27 allseen = (1 << len(nodes)) - 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	28 seen = [0] * (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	29 for i, n in enumerate(nodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	30 seen[n] = 1 << i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	31 poison = 1 << (i + 1)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	32
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	33 gca = set()
20555 4add43865a9b ancestors: remove unnecessary handling of 'left' Mads Kiilerich <madski@unity3d.com> parents: 20034 diff changeset	34 interesting = len(nodes)
18986 2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	35 nv = len(seen) - 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	36 while nv >= 0 and interesting:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	37 v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	38 nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	39 if not seen[v]:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	40 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	41 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	42 if sv < poison:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	43 interesting -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	44 if sv == allseen:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	45 gca.add(v)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	46 sv \|= poison
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	47 if v in nodes:
20555 4add43865a9b ancestors: remove unnecessary handling of 'left' Mads Kiilerich <madski@unity3d.com> parents: 20034 diff changeset	48 # history is linear
4add43865a9b ancestors: remove unnecessary handling of 'left' Mads Kiilerich <madski@unity3d.com> parents: 20034 diff changeset	49 return set([v])
18986 2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	50 if sv < poison:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	51 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	52 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	53 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	54 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	55 if sp == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	56 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	57 interesting += 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	58 elif sp != sv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	59 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	60 else:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	61 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	62 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	63 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	64 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	65 if sp and sp < poison:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	66 interesting -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	67 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	68 return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	69
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	70 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	71 interesting = {}
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	72 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	73 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	74 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	75 mapping = []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	76 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	77 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	78 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	79 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	80 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	81 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	82 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	83 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	84 v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	85 nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	86 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	87 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	88 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	89 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	90 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	91 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	92 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	93 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	94 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	95 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	96 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	97 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	98 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	99 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	100 if sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	101 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	102 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	103 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	104 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	105 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	106 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	107 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	108 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	109 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	110 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	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 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	115 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	116 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	117
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	118 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	119 return []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	120
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	121 k = 0
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	122 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	123 k \|= i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	124 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	125
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	126 gca = candidates(orignodes)
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(gca) <= 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 gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip Bryan O'Sullivan <bryano@fb.com> parents: 18091 diff changeset	130 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	131
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	132 def missingancestors(revs, bases, pfunc):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	133 """Return all the ancestors of revs that are not ancestors of bases.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	134
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	135 This may include elements from revs.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	136
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	137 Equivalent to the revset (::revs - ::bases). Revs are returned in
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	138 revision number order, which is a topological order.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	139
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	140 revs and bases should both be iterables. pfunc must return a list of
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	141 parent revs for a given revs.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	142 """
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	143
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	144 revsvisit = set(revs)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	145 basesvisit = set(bases)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	146 if not revsvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	147 return []
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	148 if not basesvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	149 basesvisit.add(nullrev)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	150 start = max(max(revsvisit), max(basesvisit))
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	151 bothvisit = revsvisit.intersection(basesvisit)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	152 revsvisit.difference_update(bothvisit)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	153 basesvisit.difference_update(bothvisit)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	154 # At this point, we hold the invariants that:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	155 # - revsvisit is the set of nodes we know are an ancestor of at least one
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	156 # of the nodes in revs
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	157 # - basesvisit is the same for bases
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	158 # - bothvisit is the set of nodes we know are ancestors of at least one of
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	159 # the nodes in revs and one of the nodes in bases
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	160 # - a node may be in none or one, but not more, of revsvisit, basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	161 # and bothvisit at any given time
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	162 # Now we walk down in reverse topo order, adding parents of nodes already
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	163 # visited to the sets while maintaining the invariants. When a node is
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	164 # found in both revsvisit and basesvisit, it is removed from them and
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	165 # added to bothvisit instead. When revsvisit becomes empty, there are no
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	166 # more ancestors of revs that aren't also ancestors of bases, so exit.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	167
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	168 missing = []
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	169 for curr in xrange(start, nullrev, -1):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	170 if not revsvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	171 break
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	172
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	173 if curr in bothvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	174 bothvisit.remove(curr)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	175 # curr's parents might have made it into revsvisit or basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	176 # through another path
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	177 for p in pfunc(curr):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	178 revsvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	179 basesvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	180 bothvisit.add(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	181 continue
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	182
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	183 # curr will never be in both revsvisit and basesvisit, since if it
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	184 # were it'd have been pushed to bothvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	185 if curr in revsvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	186 missing.append(curr)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	187 thisvisit = revsvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	188 othervisit = basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	189 elif curr in basesvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	190 thisvisit = basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	191 othervisit = revsvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	192 else:
17976 09d5681d5b72 ancestor: fix a comment (followup to 0b03454abae7) Siddharth Agarwal <sid0@fb.com> parents: 17970 diff changeset	193 # not an ancestor of revs or bases: ignore
17970 0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	194 continue
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	195
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	196 thisvisit.remove(curr)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	197 for p in pfunc(curr):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	198 if p == nullrev:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	199 pass
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	200 elif p in othervisit or p in bothvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	201 # p is implicitly in thisvisit. This means p is or should be
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	202 # in bothvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	203 revsvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	204 basesvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	205 bothvisit.add(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	206 else:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	207 # visit later
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	208 thisvisit.add(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	209
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	210 missing.reverse()
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets Siddharth Agarwal <sid0@fb.com> parents: 14494 diff changeset	211 return missing
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	212
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	213 class lazyancestors(object):
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	214 def __init__(self, cl, revs, stoprev=0, inclusive=False):
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	215 """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	216 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	217
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	218 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	219 iteration and membership.
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	220
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	221 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	222 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	223 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	224
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	225 Result does not include the null revision."""
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	226 self._parentrevs = cl.parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	227 self._initrevs = revs
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	228 self._stoprev = stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	229 self._inclusive = inclusive
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	230
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	231 # Initialize data structures for __contains__.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	232 # 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	233 # (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	234 # (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	235 # 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	236 # into a max-heap.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	237 self._containsvisit = [-rev for rev in revs]
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	238 heapq.heapify(self._containsvisit)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	239 if inclusive:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	240 self._containsseen = set(revs)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	241 else:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	242 self._containsseen = set()
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	243
18090 9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	244 def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	245 """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	246
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	247 If inclusive is False, yield a sequence of revision numbers starting
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	248 with the parents of each revision in revs, i.e., each revision is not
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	249 considered an ancestor of itself. Results are in breadth-first order:
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	250 parents of each rev in revs, then parents of those, etc.
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	251
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	252 If inclusive is True, yield all the revs first (ignoring stoprev),
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	253 then yield all the ancestors of revs as when inclusive is False.
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	254 If an element in revs is an ancestor of a different rev it is not
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	255 yielded again."""
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	256 seen = set()
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	257 revs = self._initrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	258 if self._inclusive:
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	259 for rev in revs:
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	260 yield rev
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	261 seen.update(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	262
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	263 parentrevs = self._parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	264 stoprev = self._stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	265 visit = util.deque(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	266
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	267 while visit:
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	268 for parent in parentrevs(visit.popleft()):
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	269 if parent >= stoprev and parent not in seen:
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	270 visit.append(parent)
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	271 seen.add(parent)
9abc55ef85b5 revlog: move ancestor generation out to a new class Siddharth Agarwal <sid0@fb.com> parents: 18079 diff changeset	272 yield parent
18091 f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	273
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	274 def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	275 """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	276 # 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	277 # 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	278 # them separate.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	279 seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	280 if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	281 return True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	282
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	283 parentrevs = self._parentrevs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	284 visit = self._containsvisit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	285 stoprev = self._stoprev
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	286 heappop = heapq.heappop
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	287 heappush = heapq.heappush
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	288
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	289 targetseen = False
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	290
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	291 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	292 for parent in parentrevs(-heappop(visit)):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	293 if parent < stoprev or parent in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	294 continue
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	295 # 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	296 # 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	297 heappush(visit, -parent)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	298 seen.add(parent)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	299 if parent == target:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	300 targetseen = True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	301
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors Siddharth Agarwal <sid0@fb.com> parents: 18090 diff changeset	302 return targetseen

Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/ancestor.py @ 20985:231ccc08670c