Show More
@@ -0,0 +1,83 b'' | |||||
|
1 | # ancestor.py - generic DAG ancestor algorithm for mercurial | |||
|
2 | # | |||
|
3 | # Copyright 2006 Matt Mackall <mpm@selenic.com> | |||
|
4 | # | |||
|
5 | # This software may be used and distributed according to the terms | |||
|
6 | # of the GNU General Public License, incorporated herein by reference. | |||
|
7 | ||||
|
8 | import heapq | |||
|
9 | ||||
|
10 | def ancestor(a, b, pfunc): | |||
|
11 | """ | |||
|
12 | return the least common ancestor of nodes a and b or None if there | |||
|
13 | is no such ancestor. | |||
|
14 | ||||
|
15 | pfunc must return a list of parent vertices | |||
|
16 | """ | |||
|
17 | ||||
|
18 | if a == b: | |||
|
19 | return a | |||
|
20 | ||||
|
21 | # find depth from root of all ancestors | |||
|
22 | visit = [a, b] | |||
|
23 | depth = {} | |||
|
24 | while visit: | |||
|
25 | vertex = visit[-1] | |||
|
26 | pl = pfunc(vertex) | |||
|
27 | if not pl: | |||
|
28 | depth[vertex] = 0 | |||
|
29 | visit.pop() | |||
|
30 | else: | |||
|
31 | for p in pl: | |||
|
32 | if p == a or p == b: # did we find a or b as a parent? | |||
|
33 | return p # we're done | |||
|
34 | if p not in depth: | |||
|
35 | visit.append(p) | |||
|
36 | if visit[-1] == vertex: | |||
|
37 | depth[vertex] = min([depth[p] for p in pl]) - 1 | |||
|
38 | visit.pop() | |||
|
39 | ||||
|
40 | # traverse ancestors in order of decreasing distance from root | |||
|
41 | def ancestors(vertex): | |||
|
42 | h = [(depth[vertex], vertex)] | |||
|
43 | seen = {} | |||
|
44 | while h: | |||
|
45 | d, n = heapq.heappop(h) | |||
|
46 | if n not in seen: | |||
|
47 | seen[n] = 1 | |||
|
48 | yield (d, n) | |||
|
49 | for p in pfunc(n): | |||
|
50 | heapq.heappush(h, (depth[p], p)) | |||
|
51 | ||||
|
52 | def generations(vertex): | |||
|
53 | sg, s = None, {} | |||
|
54 | for g,v in ancestors(vertex): | |||
|
55 | if g != sg: | |||
|
56 | if sg: | |||
|
57 | yield sg, s | |||
|
58 | sg, s = g, {v:1} | |||
|
59 | else: | |||
|
60 | s[v] = 1 | |||
|
61 | yield sg, s | |||
|
62 | ||||
|
63 | x = generations(a) | |||
|
64 | y = generations(b) | |||
|
65 | gx = x.next() | |||
|
66 | gy = y.next() | |||
|
67 | ||||
|
68 | # increment each ancestor list until it is closer to root than | |||
|
69 | # the other, or they match | |||
|
70 | try: | |||
|
71 | while 1: | |||
|
72 | if gx[0] == gy[0]: | |||
|
73 | for v in gx[1]: | |||
|
74 | if v in gy[1]: | |||
|
75 | return v | |||
|
76 | gy = y.next() | |||
|
77 | gx = x.next() | |||
|
78 | elif gx[0] > gy[0]: | |||
|
79 | gy = y.next() | |||
|
80 | else: | |||
|
81 | gx = x.next() | |||
|
82 | except StopIteration: | |||
|
83 | return None |
@@ -5,6 +5,10 b'' | |||||
5 | # This software may be used and distributed according to the terms |
|
5 | # This software may be used and distributed according to the terms | |
6 | # of the GNU General Public License, incorporated herein by reference. |
|
6 | # of the GNU General Public License, incorporated herein by reference. | |
7 |
|
7 | |||
|
8 | from node import * | |||
|
9 | from demandload import demandload | |||
|
10 | demandload(globals(), "ancestor") | |||
|
11 | ||||
8 | class changectx(object): |
|
12 | class changectx(object): | |
9 | """A changecontext object makes access to data related to a particular |
|
13 | """A changecontext object makes access to data related to a particular | |
10 | changeset convenient.""" |
|
14 | changeset convenient.""" | |
@@ -42,7 +46,7 b' class changectx(object):' | |||||
42 | def node(self): return self._node |
|
46 | def node(self): return self._node | |
43 | def user(self): return self.changeset()[1] |
|
47 | def user(self): return self.changeset()[1] | |
44 | def date(self): return self.changeset()[2] |
|
48 | def date(self): return self.changeset()[2] | |
45 |
def |
|
49 | def files(self): return self.changeset()[3] | |
46 | def description(self): return self.changeset()[4] |
|
50 | def description(self): return self.changeset()[4] | |
47 |
|
51 | |||
48 | def parents(self): |
|
52 | def parents(self): | |
@@ -74,10 +78,17 b' class changectx(object):' | |||||
74 | for f in m: |
|
78 | for f in m: | |
75 | yield self.filectx(f, fileid=mf[f]) |
|
79 | yield self.filectx(f, fileid=mf[f]) | |
76 |
|
80 | |||
|
81 | def ancestor(self, c2): | |||
|
82 | """ | |||
|
83 | return the ancestor context of self and c2 | |||
|
84 | """ | |||
|
85 | n = self._repo.changelog.ancestor(self._node, c2._node) | |||
|
86 | return changectx(self._repo, n) | |||
|
87 | ||||
77 | class filectx(object): |
|
88 | class filectx(object): | |
78 | """A filecontext object makes access to data related to a particular |
|
89 | """A filecontext object makes access to data related to a particular | |
79 | filerevision convenient.""" |
|
90 | filerevision convenient.""" | |
80 | def __init__(self, repo, path, changeid=None, fileid=None): |
|
91 | def __init__(self, repo, path, changeid=None, fileid=None, filelog=None): | |
81 | """changeid can be a changeset revision, node, or tag. |
|
92 | """changeid can be a changeset revision, node, or tag. | |
82 | fileid can be a file revision or node.""" |
|
93 | fileid can be a file revision or node.""" | |
83 | self._repo = repo |
|
94 | self._repo = repo | |
@@ -85,15 +96,18 b' class filectx(object):' | |||||
85 |
|
96 | |||
86 | assert changeid or fileid |
|
97 | assert changeid or fileid | |
87 |
|
98 | |||
|
99 | if filelog: | |||
|
100 | self._filelog = filelog | |||
|
101 | else: | |||
|
102 | self._filelog = self._repo.file(self._path) | |||
|
103 | ||||
88 | if not fileid: |
|
104 | if not fileid: | |
89 | # if given a changeset id, go ahead and look up the file |
|
105 | # if given a changeset id, go ahead and look up the file | |
90 | self._changeid = changeid |
|
106 | self._changeid = changeid | |
91 | self._changectx = self.changectx() |
|
107 | self._changectx = self.changectx() | |
92 | self._filelog = self._repo.file(self._path) |
|
|||
93 | self._filenode = self._changectx.filenode(self._path) |
|
108 | self._filenode = self._changectx.filenode(self._path) | |
94 | else: |
|
109 | else: | |
95 |
# else |
|
110 | # else delay changectx creation | |
96 | self._filelog = self._repo.file(self._path) |
|
|||
97 | self._filenode = self._filelog.lookup(fileid) |
|
111 | self._filenode = self._filelog.lookup(fileid) | |
98 | self._changeid = self._filelog.linkrev(self._filenode) |
|
112 | self._changeid = self._filelog.linkrev(self._filenode) | |
99 | self._filerev = self._filelog.rev(self._filenode) |
|
113 | self._filerev = self._filelog.rev(self._filenode) | |
@@ -118,18 +132,55 b' class filectx(object):' | |||||
118 | def manifest(self): return self.changectx().manifest() |
|
132 | def manifest(self): return self.changectx().manifest() | |
119 |
|
133 | |||
120 | def data(self): return self._filelog.read(self._filenode) |
|
134 | def data(self): return self._filelog.read(self._filenode) | |
121 | def metadata(self): return self._filelog.readmeta(self._filenode) |
|
|||
122 | def renamed(self): return self._filelog.renamed(self._filenode) |
|
135 | def renamed(self): return self._filelog.renamed(self._filenode) | |
|
136 | def path(self): return self._path | |||
123 |
|
137 | |||
124 | def parents(self): |
|
138 | def parents(self): | |
125 | # need to fix for renames |
|
139 | p = self._path | |
126 |
|
|
140 | fl = self._filelog | |
127 | return [ filectx(self._repo, self._path, fileid=x) for x in p ] |
|
141 | pl = [ (p, n, fl) for n in self._filelog.parents(self._filenode) ] | |
|
142 | ||||
|
143 | r = self.renamed() | |||
|
144 | if r: | |||
|
145 | pl[0] = (r[0], r[1], None) | |||
|
146 | ||||
|
147 | return [ filectx(self._repo, p, fileid=n, filelog=l) | |||
|
148 | for p,n,l in pl if n != nullid ] | |||
128 |
|
149 | |||
129 | def children(self): |
|
150 | def children(self): | |
130 | # hard for renames |
|
151 | # hard for renames | |
131 | c = self._filelog.children(self._filenode) |
|
152 | c = self._filelog.children(self._filenode) | |
132 |
return [ filectx(self._repo, self._path, fileid=x |
|
153 | return [ filectx(self._repo, self._path, fileid=x, | |
|
154 | filelog=self._filelog) for x in c ] | |||
133 |
|
155 | |||
134 | def annotate(self): |
|
156 | def annotate(self): | |
135 | return self._filelog.annotate(self._filenode) |
|
157 | return self._filelog.annotate(self._filenode) | |
|
158 | ||||
|
159 | def ancestor(self, fc2): | |||
|
160 | """ | |||
|
161 | find the common ancestor file context, if any, of self, and fc2 | |||
|
162 | """ | |||
|
163 | ||||
|
164 | acache = {} | |||
|
165 | flcache = {self._path:self._filelog, fc2._path:fc2._filelog} | |||
|
166 | def parents(vertex): | |||
|
167 | if vertex in acache: | |||
|
168 | return acache[vertex] | |||
|
169 | f, n = vertex | |||
|
170 | if f not in flcache: | |||
|
171 | flcache[f] = self._repo.file(f) | |||
|
172 | fl = flcache[f] | |||
|
173 | pl = [ (f,p) for p in fl.parents(n) if p != nullid ] | |||
|
174 | re = fl.renamed(n) | |||
|
175 | if re: | |||
|
176 | pl.append(re) | |||
|
177 | acache[vertex]=pl | |||
|
178 | return pl | |||
|
179 | ||||
|
180 | a, b = (self._path, self._filenode), (fc2._path, fc2._filenode) | |||
|
181 | v = ancestor.ancestor(a, b, parents) | |||
|
182 | if v: | |||
|
183 | f,n = v | |||
|
184 | return filectx(self._repo, f, fileid=n, filelog=flcache[f]) | |||
|
185 | ||||
|
186 | return None |
@@ -37,7 +37,7 b' class filelog(revlog):' | |||||
37 | s = t.index('\1\n', 2) |
|
37 | s = t.index('\1\n', 2) | |
38 | return t[s+2:] |
|
38 | return t[s+2:] | |
39 |
|
39 | |||
40 | def readmeta(self, node): |
|
40 | def _readmeta(self, node): | |
41 | t = self.revision(node) |
|
41 | t = self.revision(node) | |
42 | if not t.startswith('\1\n'): |
|
42 | if not t.startswith('\1\n'): | |
43 | return {} |
|
43 | return {} | |
@@ -60,7 +60,7 b' class filelog(revlog):' | |||||
60 | def renamed(self, node): |
|
60 | def renamed(self, node): | |
61 | if self.parents(node)[0] != nullid: |
|
61 | if self.parents(node)[0] != nullid: | |
62 | return False |
|
62 | return False | |
63 | m = self.readmeta(node) |
|
63 | m = self._readmeta(node) | |
64 | if m and m.has_key("copy"): |
|
64 | if m and m.has_key("copy"): | |
65 | return (m["copy"], bin(m["copyrev"])) |
|
65 | return (m["copy"], bin(m["copyrev"])) | |
66 | return False |
|
66 | return False |
@@ -62,6 +62,9 b' static struct flist *lalloc(int size)' | |||||
62 | { |
|
62 | { | |
63 | struct flist *a = NULL; |
|
63 | struct flist *a = NULL; | |
64 |
|
64 | |||
|
65 | if (size < 1) | |||
|
66 | size = 1; | |||
|
67 | ||||
65 | a = (struct flist *)malloc(sizeof(struct flist)); |
|
68 | a = (struct flist *)malloc(sizeof(struct flist)); | |
66 | if (a) { |
|
69 | if (a) { | |
67 | a->base = (struct frag *)malloc(sizeof(struct frag) * size); |
|
70 | a->base = (struct frag *)malloc(sizeof(struct frag) * size); |
@@ -13,7 +13,7 b' of the GNU General Public License, incor' | |||||
13 | from node import * |
|
13 | from node import * | |
14 | from i18n import gettext as _ |
|
14 | from i18n import gettext as _ | |
15 | from demandload import demandload |
|
15 | from demandload import demandload | |
16 |
demandload(globals(), "binascii changegroup errno |
|
16 | demandload(globals(), "binascii changegroup errno ancestor mdiff os") | |
17 | demandload(globals(), "sha struct util zlib") |
|
17 | demandload(globals(), "sha struct util zlib") | |
18 |
|
18 | |||
19 | # revlog version strings |
|
19 | # revlog version strings | |
@@ -1016,78 +1016,14 b' class revlog(object):' | |||||
1016 | def ancestor(self, a, b): |
|
1016 | def ancestor(self, a, b): | |
1017 | """calculate the least common ancestor of nodes a and b""" |
|
1017 | """calculate the least common ancestor of nodes a and b""" | |
1018 |
|
1018 | |||
1019 | # start with some short cuts for the linear cases |
|
1019 | def parents(rev): | |
1020 | if a == b: |
|
1020 | return [p for p in self.parentrevs(rev) if p != -1] | |
1021 | return a |
|
|||
1022 | ra = self.rev(a) |
|
|||
1023 | rb = self.rev(b) |
|
|||
1024 | if ra < rb: |
|
|||
1025 | last = b |
|
|||
1026 | first = a |
|
|||
1027 | else: |
|
|||
1028 | last = a |
|
|||
1029 | first = b |
|
|||
1030 |
|
||||
1031 | # reachable won't include stop in the list, so we have to use a parent |
|
|||
1032 | reachable = self.reachable(last, stop=self.parents(first)[0]) |
|
|||
1033 | if first in reachable: |
|
|||
1034 | return first |
|
|||
1035 |
|
||||
1036 | # calculate the distance of every node from root |
|
|||
1037 | dist = {nullid: 0} |
|
|||
1038 | for i in xrange(self.count()): |
|
|||
1039 | n = self.node(i) |
|
|||
1040 | p1, p2 = self.parents(n) |
|
|||
1041 | dist[n] = max(dist[p1], dist[p2]) + 1 |
|
|||
1042 |
|
1021 | |||
1043 | # traverse ancestors in order of decreasing distance from root |
|
1022 | c = ancestor.ancestor(self.rev(a), self.rev(b), parents) | |
1044 | def ancestors(node): |
|
1023 | if c is None: | |
1045 | # we store negative distances because heap returns smallest member |
|
1024 | return nullid | |
1046 | h = [(-dist[node], node)] |
|
|||
1047 | seen = {} |
|
|||
1048 | while h: |
|
|||
1049 | d, n = heapq.heappop(h) |
|
|||
1050 | if n not in seen: |
|
|||
1051 | seen[n] = 1 |
|
|||
1052 | yield (-d, n) |
|
|||
1053 | for p in self.parents(n): |
|
|||
1054 | heapq.heappush(h, (-dist[p], p)) |
|
|||
1055 |
|
||||
1056 | def generations(node): |
|
|||
1057 | sg, s = None, {} |
|
|||
1058 | for g,n in ancestors(node): |
|
|||
1059 | if g != sg: |
|
|||
1060 | if sg: |
|
|||
1061 | yield sg, s |
|
|||
1062 | sg, s = g, {n:1} |
|
|||
1063 | else: |
|
|||
1064 | s[n] = 1 |
|
|||
1065 | yield sg, s |
|
|||
1066 |
|
1025 | |||
1067 | x = generations(a) |
|
1026 | return self.node(c) | |
1068 | y = generations(b) |
|
|||
1069 | gx = x.next() |
|
|||
1070 | gy = y.next() |
|
|||
1071 |
|
||||
1072 | # increment each ancestor list until it is closer to root than |
|
|||
1073 | # the other, or they match |
|
|||
1074 | while 1: |
|
|||
1075 | #print "ancestor gen %s %s" % (gx[0], gy[0]) |
|
|||
1076 | if gx[0] == gy[0]: |
|
|||
1077 | # find the intersection |
|
|||
1078 | i = [ n for n in gx[1] if n in gy[1] ] |
|
|||
1079 | if i: |
|
|||
1080 | return i[0] |
|
|||
1081 | else: |
|
|||
1082 | #print "next" |
|
|||
1083 | gy = y.next() |
|
|||
1084 | gx = x.next() |
|
|||
1085 | elif gx[0] < gy[0]: |
|
|||
1086 | #print "next y" |
|
|||
1087 | gy = y.next() |
|
|||
1088 | else: |
|
|||
1089 | #print "next x" |
|
|||
1090 | gx = x.next() |
|
|||
1091 |
|
1027 | |||
1092 | def group(self, nodelist, lookup, infocollect=None): |
|
1028 | def group(self, nodelist, lookup, infocollect=None): | |
1093 | """calculate a delta group |
|
1029 | """calculate a delta group |
General Comments 0
You need to be logged in to leave comments.
Login now