Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/graphmod.py @ 26003:62371c539c89

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
revset: remove grandparent by using reachableroots This patch is part of a series of patches to speed up the computation of revset.reachableroots by introducing a C implementation. The main motivation is to speed up smartlog on big repositories. At the end of the series, on our big repositories the computation of reachableroots is 10-50x faster and smartlog on is 2x-5x faster. Before this patch, we had a custom computation for grandparent that was very close to the idea of reacheablerooots. This patch expresses grandparent with reachableroots to reduce the amount of code.
author Laurent Charignon <lcharignon@fb.com>
date Fri, 19 Jun 2015 20:28:52 -0700
parents 69751804f2f5
children 014044dbd4e8
comparison
equal deleted inserted replaced
26002:fd92bfbbe02d 26003:62371c539c89
20 from __future__ import absolute_import 20 from __future__ import absolute_import
21 21
22 import heapq 22 import heapq
23 23
24 from .node import nullrev 24 from .node import nullrev
25 from . import util 25 from . import (
26 revset,
27 util,
28 )
26 29
27 CHANGESET = 'C' 30 CHANGESET = 'C'
28 31
29 def groupbranchiter(revs, parentsfunc, firstbranch=()): 32 def groupbranchiter(revs, parentsfunc, firstbranch=()):
30 """Yield revisions from heads to roots one (topo) branch at a time. 33 """Yield revisions from heads to roots one (topo) branch at a time.
233 returned. 236 returned.
234 """ 237 """
235 if not revs: 238 if not revs:
236 return 239 return
237 240
238 cl = repo.changelog
239 lowestrev = revs.min()
240 gpcache = {} 241 gpcache = {}
241 242
242 if repo.ui.configbool('experimental', 'graph-group-branches', False): 243 if repo.ui.configbool('experimental', 'graph-group-branches', False):
243 firstbranch = () 244 firstbranch = ()
244 firstbranchrevset = repo.ui.config( 245 firstbranchrevset = repo.ui.config(
256 p.rev() != nullrev and p.rev() not in parents] 257 p.rev() != nullrev and p.rev() not in parents]
257 258
258 for mpar in mpars: 259 for mpar in mpars:
259 gp = gpcache.get(mpar) 260 gp = gpcache.get(mpar)
260 if gp is None: 261 if gp is None:
261 gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar) 262 gp = gpcache[mpar] = revset.reachableroots(repo, revs, [mpar])
262 if not gp: 263 if not gp:
263 parents.append(mpar) 264 parents.append(mpar)
264 else: 265 else:
265 parents.extend(g for g in gp if g not in parents) 266 parents.extend(g for g in gp if g not in parents)
266 267
353 bconf.get('color', ''))) 354 bconf.get('color', '')))
354 355
355 # Yield and move on 356 # Yield and move on
356 yield (cur, type, data, (col, color), edges) 357 yield (cur, type, data, (col, color), edges)
357 seen = next 358 seen = next
358
359 def grandparent(cl, lowestrev, roots, head):
360 """Return all ancestors of head in roots which revision is
361 greater or equal to lowestrev.
362 """
363 pending = set([head])
364 seen = set()
365 kept = set()
366 llowestrev = max(nullrev, lowestrev)
367 while pending:
368 r = pending.pop()
369 if r >= llowestrev and r not in seen:
370 if r in roots:
371 kept.add(r)
372 else:
373 pending.update([p for p in cl.parentrevs(r)])
374 seen.add(r)
375 return sorted(kept)
376 359
377 def asciiedges(type, char, lines, seen, rev, parents): 360 def asciiedges(type, char, lines, seen, rev, parents):
378 """adds edge info to changelog DAG walk suitable for ascii()""" 361 """adds edge info to changelog DAG walk suitable for ascii()"""
379 if rev not in seen: 362 if rev not in seen:
380 seen.append(rev) 363 seen.append(rev)