115 return parents |
115 return parents |
116 |
116 |
117 def toposort(self, parents): |
117 def toposort(self, parents): |
118 '''Return an ordering such that every uncommitted changeset is |
118 '''Return an ordering such that every uncommitted changeset is |
119 preceeded by all its uncommitted ancestors.''' |
119 preceeded by all its uncommitted ancestors.''' |
120 visit = parents.keys() |
120 |
121 seen = set() |
121 def mapchildren(parents): |
122 children = {} |
122 """Return a (children, roots) tuple where 'children' maps parent |
123 actives = [] |
123 revision identifiers to children ones, and 'roots' is the list of |
124 |
124 revisions without parents. 'parents' must be a mapping of revision |
125 while visit: |
125 identifier to its parents ones. |
126 n = visit.pop(0) |
126 """ |
127 if n in seen: continue |
127 visit = parents.keys() |
128 seen.add(n) |
128 seen = set() |
129 # Ensure that nodes without parents are present in the 'children' |
129 children = {} |
130 # mapping. |
130 roots = [] |
131 children.setdefault(n, []) |
131 |
132 hasparent = False |
132 while visit: |
133 for p in parents[n]: |
133 n = visit.pop(0) |
134 if not p in self.map: |
134 if n in seen: |
135 visit.append(p) |
135 continue |
136 hasparent = True |
136 seen.add(n) |
137 children.setdefault(p, []).append(n) |
137 # Ensure that nodes without parents are present in the |
138 if not hasparent: |
138 # 'children' mapping. |
139 actives.append(n) |
139 children.setdefault(n, []) |
140 |
140 hasparent = False |
141 del seen |
141 for p in parents[n]: |
142 del visit |
142 if not p in self.map: |
143 |
143 visit.append(p) |
144 if self.opts.get('datesort'): |
144 hasparent = True |
145 dates = {} |
145 children.setdefault(p, []).append(n) |
146 def getdate(n): |
146 if not hasparent: |
147 if n not in dates: |
147 roots.append(n) |
148 dates[n] = util.parsedate(self.commitcache[n].date) |
148 |
149 return dates[n] |
149 return children, roots |
150 |
150 |
151 def picknext(nodes): |
151 # Sort functions are supposed to take a list of revisions which |
152 return min([(getdate(n), n) for n in nodes])[1] |
152 # can be converted immediately and pick one |
153 else: |
153 |
|
154 def makebranchsorter(): |
|
155 """If the previously converted revision has a child in the |
|
156 eligible revisions list, pick it. Return the list head |
|
157 otherwise. Branch sort attempts to minimize branch |
|
158 switching, which is harmful for Mercurial backend |
|
159 compression. |
|
160 """ |
154 prev = [None] |
161 prev = [None] |
155 def picknext(nodes): |
162 def picknext(nodes): |
156 # Return the first eligible child of the previously converted |
|
157 # revision, or any of them. |
|
158 next = nodes[0] |
163 next = nodes[0] |
159 for n in nodes: |
164 for n in nodes: |
160 if prev[0] in parents[n]: |
165 if prev[0] in parents[n]: |
161 next = n |
166 next = n |
162 break |
167 break |
163 prev[0] = next |
168 prev[0] = next |
164 return next |
169 return next |
|
170 return picknext |
|
171 |
|
172 def makedatesorter(): |
|
173 """Sort revisions by date.""" |
|
174 dates = {} |
|
175 def getdate(n): |
|
176 if n not in dates: |
|
177 dates[n] = util.parsedate(self.commitcache[n].date) |
|
178 return dates[n] |
|
179 |
|
180 def picknext(nodes): |
|
181 return min([(getdate(n), n) for n in nodes])[1] |
|
182 |
|
183 return picknext |
|
184 |
|
185 if self.opts.get('datesort'): |
|
186 picknext = makedatesorter() |
|
187 else: |
|
188 picknext = makebranchsorter() |
|
189 |
|
190 children, actives = mapchildren(parents) |
165 |
191 |
166 s = [] |
192 s = [] |
167 pendings = {} |
193 pendings = {} |
168 while actives: |
194 while actives: |
169 n = picknext(actives) |
195 n = picknext(actives) |