##// END OF EJS Templates
convert: split toposort() into subfunctions for readability
Patrick Mezard -
r8688:31e613a8 default
parent child Browse files
Show More
@@ -117,31 +117,60 b' class converter(object):'
117 117 def toposort(self, parents):
118 118 '''Return an ordering such that every uncommitted changeset is
119 119 preceeded by all its uncommitted ancestors.'''
120 visit = parents.keys()
121 seen = set()
122 children = {}
123 actives = []
120
121 def mapchildren(parents):
122 """Return a (children, roots) tuple where 'children' maps parent
123 revision identifiers to children ones, and 'roots' is the list of
124 revisions without parents. 'parents' must be a mapping of revision
125 identifier to its parents ones.
126 """
127 visit = parents.keys()
128 seen = set()
129 children = {}
130 roots = []
124 131
125 while visit:
126 n = visit.pop(0)
127 if n in seen: continue
128 seen.add(n)
129 # Ensure that nodes without parents are present in the 'children'
130 # mapping.
131 children.setdefault(n, [])
132 hasparent = False
133 for p in parents[n]:
134 if not p in self.map:
135 visit.append(p)
136 hasparent = True
137 children.setdefault(p, []).append(n)
138 if not hasparent:
139 actives.append(n)
132 while visit:
133 n = visit.pop(0)
134 if n in seen:
135 continue
136 seen.add(n)
137 # Ensure that nodes without parents are present in the
138 # 'children' mapping.
139 children.setdefault(n, [])
140 hasparent = False
141 for p in parents[n]:
142 if not p in self.map:
143 visit.append(p)
144 hasparent = True
145 children.setdefault(p, []).append(n)
146 if not hasparent:
147 roots.append(n)
148
149 return children, roots
140 150
141 del seen
142 del visit
151 # Sort functions are supposed to take a list of revisions which
152 # can be converted immediately and pick one
143 153
144 if self.opts.get('datesort'):
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 """
161 prev = [None]
162 def picknext(nodes):
163 next = nodes[0]
164 for n in nodes:
165 if prev[0] in parents[n]:
166 next = n
167 break
168 prev[0] = next
169 return next
170 return picknext
171
172 def makedatesorter():
173 """Sort revisions by date."""
145 174 dates = {}
146 175 def getdate(n):
147 176 if n not in dates:
@@ -150,18 +179,15 b' class converter(object):'
150 179
151 180 def picknext(nodes):
152 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()
153 187 else:
154 prev = [None]
155 def picknext(nodes):
156 # Return the first eligible child of the previously converted
157 # revision, or any of them.
158 next = nodes[0]
159 for n in nodes:
160 if prev[0] in parents[n]:
161 next = n
162 break
163 prev[0] = next
164 return next
188 picknext = makebranchsorter()
189
190 children, actives = mapchildren(parents)
165 191
166 192 s = []
167 193 pendings = {}
General Comments 0
You need to be logged in to leave comments. Login now