Mercurial > public > mercurial-scm > hg
comparison mercurial/manifest.py @ 24404:96cccf1e3257
treemanifest: make diff() faster
Containment checking is slower in treemanifest than it is in
manifestdict, making the current diff algorithm O(n log n). By
traversing both treemanifests in parallel, we can make it O(n). More
importantly, once we start lazily loading submanifests, we will be
able to easily skip entire submanifest if they have the same nodeid.
| author | Martin von Zweigbergk <martinvonz@google.com> |
|---|---|
| date | Thu, 19 Feb 2015 17:13:35 -0800 |
| parents | 0e23faa1511c |
| children | cbe9d50d9e65 |
comparison
equal
deleted
inserted
replaced
| 24403:0e23faa1511c | 24404:96cccf1e3257 |
|---|---|
| 525 nodeid in the current/other manifest and fl1/fl2 is the flag | 525 nodeid in the current/other manifest and fl1/fl2 is the flag |
| 526 in the current/other manifest. Where the file does not exist, | 526 in the current/other manifest. Where the file does not exist, |
| 527 the nodeid will be None and the flags will be the empty | 527 the nodeid will be None and the flags will be the empty |
| 528 string. | 528 string. |
| 529 ''' | 529 ''' |
| 530 diff = {} | 530 result = {} |
| 531 | 531 emptytree = treemanifest() |
| 532 for fn, n1 in self.iteritems(): | 532 def _diff(t1, t2): |
| 533 fl1 = self.flags(fn) | 533 for d, m1 in t1._dirs.iteritems(): |
| 534 n2 = m2.get(fn, None) | 534 m2 = t2._dirs.get(d, emptytree) |
| 535 fl2 = m2.flags(fn) | 535 _diff(m1, m2) |
| 536 if n2 is None: | 536 |
| 537 fl2 = '' | 537 for d, m2 in t2._dirs.iteritems(): |
| 538 if n1 != n2 or fl1 != fl2: | 538 if d not in t1._dirs: |
| 539 diff[fn] = ((n1, fl1), (n2, fl2)) | 539 _diff(emptytree, m2) |
| 540 elif clean: | 540 |
| 541 diff[fn] = None | 541 for fn, n1 in t1._files.iteritems(): |
| 542 | 542 fl1 = t1._flags.get(fn, '') |
| 543 for fn, n2 in m2.iteritems(): | 543 n2 = t2._files.get(fn, None) |
| 544 if fn not in self: | 544 fl2 = t2._flags.get(fn, '') |
| 545 fl2 = m2.flags(fn) | 545 if n1 != n2 or fl1 != fl2: |
| 546 diff[fn] = ((None, ''), (n2, fl2)) | 546 result[t1._subpath(fn)] = ((n1, fl1), (n2, fl2)) |
| 547 | 547 elif clean: |
| 548 return diff | 548 result[t1._subpath(fn)] = None |
| 549 | |
| 550 for fn, n2 in t2._files.iteritems(): | |
| 551 if fn not in t1._files: | |
| 552 fl2 = t2._flags.get(fn, '') | |
| 553 result[t2._subpath(fn)] = ((None, ''), (n2, fl2)) | |
| 554 | |
| 555 _diff(self, m2) | |
| 556 return result | |
| 549 | 557 |
| 550 def text(self): | 558 def text(self): |
| 551 """Get the full data of this manifest as a bytestring.""" | 559 """Get the full data of this manifest as a bytestring.""" |
| 552 fl = self.keys() | 560 fl = self.keys() |
| 553 _checkforbidden(fl) | 561 _checkforbidden(fl) |