Mercurial > hg
comparison mercurial/copies.py @ 6430:a6a66e812c34
copies: teach symmetric difference about working revisions
- use changelog.count() as a pseudo revision number
- abort early in copies if revs are the same
- eliminate working dir hacks in copies
- yield results as they're found
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Sat, 29 Mar 2008 12:39:47 -0500 |
parents | 532ca442b903 |
children | a42d8d3e6ea9 |
comparison
equal
deleted
inserted
replaced
6429:532ca442b903 | 6430:a6a66e812c34 |
---|---|
51 # return old names sorted by depth | 51 # return old names sorted by depth |
52 old = old.values() | 52 old = old.values() |
53 old.sort() | 53 old.sort() |
54 return [o[1] for o in old] | 54 return [o[1] for o in old] |
55 | 55 |
56 def _symmetricdifference(a, b, pfunc): | 56 def _symmetricdifference(repo, a, b): |
57 """find revisions that are ancestors of a or b, but not both""" | 57 """find revisions that are ancestors of a or b, but not both""" |
58 # basic idea: | 58 # basic idea: |
59 # - mark a and b with different sides | 59 # - mark a and b with different sides |
60 # - if a parent's children are all on the same side, the parent is | 60 # - if a parent's children are all on the same side, the parent is |
61 # on that side, otherwise it is on no side | 61 # on that side, otherwise it is on no side |
62 # - walk the graph in topological order with the help of a heap; | 62 # - walk the graph in topological order with the help of a heap; |
63 # - add unseen parents to side map | 63 # - add unseen parents to side map |
64 # - clear side of any parent that has children on different sides | 64 # - clear side of any parent that has children on different sides |
65 # - track number of unvisited nodes that might still be on a side | 65 # - track number of unvisited nodes that might still be on a side |
66 # - quit when interesting nodes is zero | 66 # - quit when interesting nodes is zero |
67 if a == b: | 67 |
68 return [a] | 68 cl = repo.changelog |
69 working = cl.count() | |
70 if a is None: | |
71 a = working | |
72 if b is None: | |
73 b = working | |
69 | 74 |
70 side = {a: -1, b: 1} | 75 side = {a: -1, b: 1} |
71 visit = [-a, -b] | 76 visit = [-a, -b] |
72 heapq.heapify(visit) | 77 heapq.heapify(visit) |
73 interesting = len(visit) | 78 interesting = len(visit) |
74 | 79 |
75 while interesting: | 80 while interesting: |
76 r = -heapq.heappop(visit) | 81 r = -heapq.heappop(visit) |
77 if side[r]: | 82 if r == working: |
78 interesting -= 1 | 83 parents = [cl.rev(p) for p in repo.dirstate.parents()] |
79 for p in pfunc(r): | 84 else: |
85 parents = cl.parentrevs(r) | |
86 for p in parents: | |
80 if p not in side: | 87 if p not in side: |
81 # first time we see p; add it to visit | 88 # first time we see p; add it to visit |
82 side[p] = side[r] | 89 side[p] = side[r] |
83 if side[p]: | 90 if side[p]: |
84 interesting += 1 | 91 interesting += 1 |
85 heapq.heappush(visit, -p) | 92 heapq.heappush(visit, -p) |
86 elif side[p] and side[p] != side[r]: | 93 elif side[p] and side[p] != side[r]: |
87 # p was interesting but now we know better | 94 # p was interesting but now we know better |
88 side[p] = 0 | 95 side[p] = 0 |
89 interesting -= 1 | 96 interesting -= 1 |
90 | 97 if side[r]: |
91 return [r for r in side if side[r]] | 98 interesting -= 1 |
99 yield r | |
92 | 100 |
93 def copies(repo, c1, c2, ca, checkdirs=False): | 101 def copies(repo, c1, c2, ca, checkdirs=False): |
94 """ | 102 """ |
95 Find moves and copies between context c1 and c2 | 103 Find moves and copies between context c1 and c2 |
96 """ | 104 """ |
97 # avoid silly behavior for update from empty dir | 105 # avoid silly behavior for update from empty dir |
98 if not c1 or not c2: | 106 if not c1 or not c2 or c1 == c2: |
99 return {}, {} | 107 return {}, {} |
100 | 108 |
101 rev1, rev2 = c1.rev(), c2.rev() | 109 limit = min(_symmetricdifference(repo, c1.rev(), c2.rev())) |
102 if rev1 is None: # c1 is a workingctx | |
103 rev1 = c1.parents()[0].rev() | |
104 if rev2 is None: # c2 is a workingctx | |
105 rev2 = c2.parents()[0].rev() | |
106 pr = repo.changelog.parentrevs | |
107 def parents(rev): | |
108 return [p for p in pr(rev) if p != nullrev] | |
109 limit = min(_symmetricdifference(rev1, rev2, parents)) | |
110 m1 = c1.manifest() | 110 m1 = c1.manifest() |
111 m2 = c2.manifest() | 111 m2 = c2.manifest() |
112 ma = ca.manifest() | 112 ma = ca.manifest() |
113 | 113 |
114 def makectx(f, n): | 114 def makectx(f, n): |