Mercurial > public > mercurial-scm > hg

comparison mercurial/copies.py @ 6431:a42d8d3e6ea9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
copies: refactor symmetricdifference as _findlimit We only need to track the lowest revision seen, which makes things simpler.
author Matt Mackall <mpm@selenic.com>
date Sat, 29 Mar 2008 12:39:47 -0500
parents a6a66e812c34
children 9eb274d773d9
comparison
equal deleted inserted replaced
6430:a6a66e812c34 6431:a42d8d3e6ea9
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(repo, a, b): 56 def _findlimit(repo, a, b):
57 """find revisions that are ancestors of a or b, but not both""" 57 "find the earliest revision that's an ancestor 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 interesting revs that might still be on a side
66 # - quit when interesting nodes is zero 66 # - track the lowest interesting rev seen
67 # - quit when interesting revs is zero
67 68
68 cl = repo.changelog 69 cl = repo.changelog
69 working = cl.count() 70 working = cl.count() # pseudo rev for the working directory
70 if a is None: 71 if a is None:
71 a = working 72 a = working
72 if b is None: 73 if b is None:
73 b = working 74 b = working
74 75
75 side = {a: -1, b: 1} 76 side = {a: -1, b: 1}
76 visit = [-a, -b] 77 visit = [-a, -b]
77 heapq.heapify(visit) 78 heapq.heapify(visit)
78 interesting = len(visit) 79 interesting = len(visit)
80 limit = working
79 81
80 while interesting: 82 while interesting:
81 r = -heapq.heappop(visit) 83 r = -heapq.heappop(visit)
82 if r == working: 84 if r == working:
83 parents = [cl.rev(p) for p in repo.dirstate.parents()] 85 parents = [cl.rev(p) for p in repo.dirstate.parents()]
93 elif side[p] and side[p] != side[r]: 95 elif side[p] and side[p] != side[r]:
94 # p was interesting but now we know better 96 # p was interesting but now we know better
95 side[p] = 0 97 side[p] = 0
96 interesting -= 1 98 interesting -= 1
97 if side[r]: 99 if side[r]:
100 limit = r # lowest rev visited
98 interesting -= 1 101 interesting -= 1
99 yield r 102 return limit
100 103
101 def copies(repo, c1, c2, ca, checkdirs=False): 104 def copies(repo, c1, c2, ca, checkdirs=False):
102 """ 105 """
103 Find moves and copies between context c1 and c2 106 Find moves and copies between context c1 and c2
104 """ 107 """
105 # avoid silly behavior for update from empty dir 108 # avoid silly behavior for update from empty dir
106 if not c1 or not c2 or c1 == c2: 109 if not c1 or not c2 or c1 == c2:
107 return {}, {} 110 return {}, {}
108 111
109 limit = min(_symmetricdifference(repo, c1.rev(), c2.rev())) 112 limit = _findlimit(repo, c1.rev(), c2.rev())
110 m1 = c1.manifest() 113 m1 = c1.manifest()
111 m2 = c2.manifest() 114 m2 = c2.manifest()
112 ma = ca.manifest() 115 ma = ca.manifest()
113 116
114 def makectx(f, n): 117 def makectx(f, n):