Mercurial > hg
changeset 45:f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
| author | mpm@selenic.com |
|---|---|
| date | Tue, 10 May 2005 00:34:57 -0800 |
| parents | e825a68d7227 |
| children | 93e868fa0db8 |
| files | mercurial/revlog.py |
| diffstat | 1 files changed, 32 insertions(+), 14 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/revlog.py Tue May 10 00:33:48 2005 -0800 +++ b/mercurial/revlog.py Tue May 10 00:34:57 2005 -0800 @@ -170,20 +170,38 @@ return node def ancestor(self, a, b): - def expand(e1, e2, a1, a2): - ne = [] - for n in e1: - (p1, p2) = self.parents(n) - if p1 in a2: return p1 - if p2 in a2: return p2 - if p1 != nullid and p1 not in a1: - a1[p1] = 1 - ne.append(p1) - if p2 != nullid and p2 not in a1: - a1[p2] = 1 - ne.append(p2) - return expand(e2, ne, a2, a1) - return expand([a], [b], {a:1}, {b:1}) + def expand(list, map): + a = [] + while list: + n = list.pop(0) + map[n] = 1 + yield n + for p in self.parents(n): + if p != nullid and p not in map: + list.append(p) + yield nullid + + amap = {} + bmap = {} + ag = expand([a], amap) + bg = expand([b], bmap) + adone = bdone = 0 + + while not adone or not bdone: + if not adone: + an = ag.next() + if an == nullid: + adone = 1 + elif an in bmap: + return an + if not bdone: + bn = bg.next() + if bn == nullid: + bdone = 1 + elif bn in amap: + return bn + + return nullid def mergedag(self, other, transaction, linkseq, accumulate = None): """combine the nodes from other's DAG into ours"""