--- a/mercurial/context.py Tue Sep 13 13:49:42 2016 -0700
+++ b/mercurial/context.py Wed Sep 14 17:12:39 2016 +0200
@@ -990,15 +990,29 @@
# bit recursion-hostile. Instead we do an iterative
# depth-first search.
+ # 1st DFS pre-calculates pcache and needed
visit = [base]
- hist = {}
pcache = {}
needed = {base: 1}
while visit:
+ f = visit.pop()
+ if f in pcache:
+ continue
+ pl = parents(f)
+ pcache[f] = pl
+ for p in pl:
+ needed[p] = needed.get(p, 0) + 1
+ if p not in pcache:
+ visit.append(p)
+
+ # 2nd DFS does the actual annotate
+ visit[:] = [base]
+ hist = {}
+ while visit:
f = visit[-1]
- pcached = f in pcache
- if not pcached:
- pcache[f] = parents(f)
+ if f in hist:
+ visit.pop()
+ continue
ready = True
pl = pcache[f]
@@ -1006,18 +1020,11 @@
if p not in hist:
ready = False
visit.append(p)
- if not pcached:
- needed[p] = needed.get(p, 0) + 1
if ready:
visit.pop()
- reusable = f in hist
- if reusable:
- curr = hist[f]
- else:
- curr = decorate(f.data(), f)
+ curr = decorate(f.data(), f)
for p in pl:
- if not reusable:
- curr = pair(hist[p], curr)
+ curr = pair(hist[p], curr)
if needed[p] == 1:
del hist[p]
del needed[p]
@@ -1025,7 +1032,7 @@
needed[p] -= 1
hist[f] = curr
- pcache[f] = []
+ del pcache[f]
return zip(hist[base][0], hist[base][1].splitlines(True))