Mercurial > public > mercurial-scm > hg-stable
comparison mercurial/context.py @ 13552:7ab85fec60c3 stable
ancestor: rewrite to deal with crossed linkrevs (issue2682)
This version is about 10% slower, possibly because it visits some
revisions in a different topological order than what's in the revlog.
| author | Matt Mackall <mpm@selenic.com> |
|---|---|
| date | Mon, 07 Mar 2011 15:44:43 -0600 |
| parents | 4eb1e9d6a7c9 |
| children | 653121e6941f |
comparison
equal
deleted
inserted
replaced
| 13551:bbfae32f178e | 13552:7ab85fec60c3 |
|---|---|
| 464 if self.rev() != self.linkrev(): | 464 if self.rev() != self.linkrev(): |
| 465 base = self.filectx(self.filerev()) | 465 base = self.filectx(self.filerev()) |
| 466 else: | 466 else: |
| 467 base = self | 467 base = self |
| 468 | 468 |
| 469 # find all ancestors | 469 # This algorithm would prefer to be recursive, but Python is a |
| 470 # bit recursion-hostile. Instead we do an iterative | |
| 471 # depth-first search. | |
| 472 | |
| 473 visit = [base] | |
| 474 hist = {} | |
| 475 pcache = {} | |
| 470 needed = {base: 1} | 476 needed = {base: 1} |
| 471 visit = [base] | |
| 472 files = [base._path] | |
| 473 while visit: | 477 while visit: |
| 474 f = visit.pop(0) | 478 f = visit[-1] |
| 475 for p in parents(f): | 479 if f not in pcache: |
| 476 if p not in needed: | 480 pcache[f] = parents(f) |
| 477 needed[p] = 1 | 481 |
| 482 ready = True | |
| 483 pl = pcache[f] | |
| 484 for p in pl: | |
| 485 if p not in hist: | |
| 486 ready = False | |
| 478 visit.append(p) | 487 visit.append(p) |
| 479 if p._path not in files: | 488 needed[p] = needed.get(p, 0) + 1 |
| 480 files.append(p._path) | 489 if ready: |
| 481 else: | 490 visit.pop() |
| 482 # count how many times we'll use this | 491 curr = decorate(f.data(), f) |
| 483 needed[p] += 1 | 492 for p in pl: |
| 484 | 493 curr = pair(hist[p], curr) |
| 485 # sort by revision (per file) which is a topological order | 494 if needed[p] == 1: |
| 486 visit = [] | 495 del hist[p] |
| 487 for f in files: | 496 else: |
| 488 visit.extend(n for n in needed if n._path == f) | 497 needed[p] -= 1 |
| 489 | 498 |
| 490 hist = {} | 499 hist[f] = curr |
| 491 for f in sorted(visit, key=lambda x: x.rev()): | 500 pcache[f] = [] |
| 492 curr = decorate(f.data(), f) | 501 |
| 493 for p in parents(f): | 502 return zip(hist[base][0], hist[base][1].splitlines(True)) |
| 494 curr = pair(hist[p], curr) | |
| 495 # trim the history of unneeded revs | |
| 496 needed[p] -= 1 | |
| 497 if not needed[p]: | |
| 498 del hist[p] | |
| 499 hist[f] = curr | |
| 500 | |
| 501 return zip(hist[f][0], hist[f][1].splitlines(True)) | |
| 502 | 503 |
| 503 def ancestor(self, fc2, actx=None): | 504 def ancestor(self, fc2, actx=None): |
| 504 """ | 505 """ |
| 505 find the common ancestor file context, if any, of self, and fc2 | 506 find the common ancestor file context, if any, of self, and fc2 |
| 506 | 507 |