Mercurial > hg
comparison hgext/hbisect.py @ 5773:2f6105ab4c54
bisect: merge ancestor lists when pushing to children
- eliminate some redundant tests and assignments
- move ancestor list merging to child update
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Mon, 31 Dec 2007 18:20:34 -0600 |
parents | 4c46636eafe5 |
children | c850a8640981 |
comparison
equal
deleted
inserted
replaced
5772:4c46636eafe5 | 5773:2f6105ab4c54 |
---|---|
62 for rev in candidates: | 62 for rev in candidates: |
63 if rev in poison: | 63 if rev in poison: |
64 for c in children.get(rev, []): | 64 for c in children.get(rev, []): |
65 poison[c] = True # poison children | 65 poison[c] = True # poison children |
66 continue | 66 continue |
67 l = ancestors[rev] | 67 |
68 a = ancestors[rev] or [rev] | |
68 ancestors[rev] = None | 69 ancestors[rev] = None |
69 if l != None: | 70 |
70 if not l: | 71 x = len(a) # number of ancestors |
71 a = [rev] | 72 y = tot - x # number of non-ancestors |
72 elif len(l) == 1: | 73 value = min(x, y) # how good is this test? |
73 a = l[0] + [rev] | 74 if value > best_len and rev not in skip: |
75 best_len = value | |
76 best_rev = rev | |
77 if value == perfect: # found a perfect candidate? quit early | |
78 break | |
79 | |
80 if y < perfect: # all downhill from here? | |
81 for c in children.get(rev, []): | |
82 poison[c] = True # poison children | |
83 continue | |
84 | |
85 for c in children.get(rev, []): | |
86 if ancestors[c]: | |
87 s = dict.fromkeys(ancestors[c]) | |
88 s.update(dict.fromkeys(a)) | |
89 ancestors[c] = s.keys() | |
74 else: | 90 else: |
75 a = {} | 91 ancestors[c] = a + [c] |
76 for s in l: | |
77 a.update(dict.fromkeys(s)) | |
78 a[rev] = None | |
79 a = a.keys() | |
80 | |
81 x = len(a) # number of ancestors | |
82 y = tot - x # number of non-ancestors | |
83 value = min(x, y) # how good is this test? | |
84 if value > best_len and rev not in skip: | |
85 best_len = value | |
86 best_rev = rev | |
87 if value == perfect: # found a perfect candidate? quit early | |
88 break | |
89 | |
90 if y < perfect: # all downhill from here? | |
91 for c in children.get(rev, []): | |
92 poison[c] = True # poison children | |
93 continue | |
94 | |
95 for c in children.get(rev, []): | |
96 if ancestors[c]: | |
97 ancestors[c].append(a) | |
98 else: | |
99 ancestors[c] = [a] | |
100 | 92 |
101 assert best_rev is not None | 93 assert best_rev is not None |
102 best_node = changelog.node(best_rev) | 94 best_node = changelog.node(best_rev) |
103 | 95 |
104 return (best_node, tot) | 96 return (best_node, tot) |