##// 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 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 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:
132 while visit:
126 n = visit.pop(0)
133 n = visit.pop(0)
127 if n in seen: continue
134 if n in seen:
128 seen.add(n)
135 continue
129 # Ensure that nodes without parents are present in the 'children'
136 seen.add(n)
130 # mapping.
137 # Ensure that nodes without parents are present in the
131 children.setdefault(n, [])
138 # 'children' mapping.
132 hasparent = False
139 children.setdefault(n, [])
133 for p in parents[n]:
140 hasparent = False
134 if not p in self.map:
141 for p in parents[n]:
135 visit.append(p)
142 if not p in self.map:
136 hasparent = True
143 visit.append(p)
137 children.setdefault(p, []).append(n)
144 hasparent = True
138 if not hasparent:
145 children.setdefault(p, []).append(n)
139 actives.append(n)
146 if not hasparent:
147 roots.append(n)
148
149 return children, roots
140
150
141 del seen
151 # Sort functions are supposed to take a list of revisions which
142 del visit
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 dates = {}
174 dates = {}
146 def getdate(n):
175 def getdate(n):
147 if n not in dates:
176 if n not in dates:
@@ -150,18 +179,15 b' class converter(object):'
150
179
151 def picknext(nodes):
180 def picknext(nodes):
152 return min([(getdate(n), n) for n in nodes])[1]
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 else:
187 else:
154 prev = [None]
188 picknext = makebranchsorter()
155 def picknext(nodes):
189
156 # Return the first eligible child of the previously converted
190 children, actives = mapchildren(parents)
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
165
191
166 s = []
192 s = []
167 pendings = {}
193 pendings = {}
General Comments 0
You need to be logged in to leave comments. Login now