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): |