transactions: convert changes['phases'] to list of ranges

Consecutive revisions are often in the same phase, especially public
revisions. This means that a dictionary keyed by the revision for the
phase transitions is highly redundant. Build a list of (range, (old,
new)) entries instead and aggressively merge ranges with the same
transition. For the test case in issue5691, this reduces memory use by
~20MB.

Differential Revision: https://phab.mercurial-scm.org/D8125

mercurial/localrepo.py

@@ -2178,15 +2178,16 b' class localrepository(object):'
                     )
             if hook.hashook(repo.ui, b'pretxnclose-phase'):
                 cl = repo.unfiltered().changelog
-                for rev, (old, new) in tr.changes[b'phases'].items():
-                    args = tr.hookargs.copy()
-                    node = hex(cl.node(rev))
-                    args.update(phases.preparehookargs(node, old, new))
-                    repo.hook(
-                        b'pretxnclose-phase',
-                        throw=True,
-                        **pycompat.strkwargs(args)
-                    )
+                for revs, (old, new) in tr.changes[b'phases']:
+                    for rev in revs:
+                        args = tr.hookargs.copy()
+                        node = hex(cl.node(rev))
+                        args.update(phases.preparehookargs(node, old, new))
+                        repo.hook(
+                            b'pretxnclose-phase',
+                            throw=True,
+                            **pycompat.strkwargs(args)
+                        )
 
             repo.hook(
                 b'pretxnclose', throw=True, **pycompat.strkwargs(tr.hookargs)
@@ -2231,7 +2232,7 b' class localrepository(object):'
         )
         tr.changes[b'origrepolen'] = len(self)
         tr.changes[b'obsmarkers'] = set()
-        tr.changes[b'phases'] = {}
+        tr.changes[b'phases'] = []
         tr.changes[b'bookmarks'] = {}
 
         tr.hookargs[b'txnid'] = txnid
@@ -2265,16 +2266,19 b' class localrepository(object):'
 
                 if hook.hashook(repo.ui, b'txnclose-phase'):
                     cl = repo.unfiltered().changelog
-                    phasemv = sorted(tr.changes[b'phases'].items())
-                    for rev, (old, new) in phasemv:
-                        args = tr.hookargs.copy()
-                        node = hex(cl.node(rev))
-                        args.update(phases.preparehookargs(node, old, new))
-                        repo.hook(
-                            b'txnclose-phase',
-                            throw=False,
-                            **pycompat.strkwargs(args)
-                        )
+                    phasemv = sorted(
+                        tr.changes[b'phases'], key=lambda r: r[0][0]
+                    )
+                    for revs, (old, new) in phasemv:
+                        for rev in revs:
+                            args = tr.hookargs.copy()
+                            node = hex(cl.node(rev))
+                            args.update(phases.preparehookargs(node, old, new))
+                            repo.hook(
+                                b'txnclose-phase',
+                                throw=False,
+                                **pycompat.strkwargs(args)
+                            )
 
                 repo.hook(
                     b'txnclose', throw=False, **pycompat.strkwargs(hookargs)

mercurial/phases.py

@@ -216,17 +216,101 b' def binarydecode(stream):'
     return headsbyphase
 
 
+def _sortedrange_insert(data, idx, rev, t):
+    merge_before = False
+    if idx:
+        r1, t1 = data[idx - 1]
+        merge_before = r1[-1] + 1 == rev and t1 == t
+    merge_after = False
+    if idx < len(data):
+        r2, t2 = data[idx]
+        merge_after = r2[0] == rev + 1 and t2 == t
+
+    if merge_before and merge_after:
+        data[idx - 1] = (pycompat.xrange(r1[0], r2[-1] + 1), t)
+        data.pop(idx)
+    elif merge_before:
+        data[idx - 1] = (pycompat.xrange(r1[0], rev + 1), t)
+    elif merge_after:
+        data[idx] = (pycompat.xrange(rev, r2[-1] + 1), t)
+    else:
+        data.insert(idx, (pycompat.xrange(rev, rev + 1), t))
+
+
+def _sortedrange_split(data, idx, rev, t):
+    r1, t1 = data[idx]
+    if t == t1:
+        return
+    t = (t1[0], t[1])
+    if len(r1) == 1:
+        data.pop(idx)
+        _sortedrange_insert(data, idx, rev, t)
+    elif r1[0] == rev:
+        data[idx] = (pycompat.xrange(rev + 1, r1[-1] + 1), t1)
+        _sortedrange_insert(data, idx, rev, t)
+    elif r1[-1] == rev:
+        data[idx] = (pycompat.xrange(r1[0], rev), t1)
+        _sortedrange_insert(data, idx + 1, rev, t)
+    else:
+        data[idx : idx + 1] = [
+            (pycompat.xrange(r1[0], rev), t1),
+            (pycompat.xrange(rev, rev + 1), t),
+            (pycompat.xrange(rev + 1, r1[-1] + 1), t1),
+        ]
+
+
 def _trackphasechange(data, rev, old, new):
-    """add a phase move the <data> dictionnary
+    """add a phase move to the <data> list of ranges
 
     If data is None, nothing happens.
     """
     if data is None:
         return
-    existing = data.get(rev)
-    if existing is not None:
-        old = existing[0]
-    data[rev] = (old, new)
+
+    # If data is empty, create a one-revision range and done
+    if not data:
+        data.insert(0, (pycompat.xrange(rev, rev + 1), (old, new)))
+        return
+
+    low = 0
+    high = len(data)
+    t = (old, new)
+    while low < high:
+        mid = (low + high) // 2
+        revs = data[mid][0]
+
+        if rev in revs:
+            _sortedrange_split(data, mid, rev, t)
+            return
+
+        if revs[0] == rev + 1:
+            if mid and data[mid - 1][0][-1] == rev:
+                _sortedrange_split(data, mid - 1, rev, t)
+            else:
+                _sortedrange_insert(data, mid, rev, t)
+            return
+
+        if revs[-1] == rev - 1:
+            if mid + 1 < len(data) and data[mid + 1][0][0] == rev:
+                _sortedrange_split(data, mid + 1, rev, t)
+            else:
+                _sortedrange_insert(data, mid + 1, rev, t)
+            return
+
+        if revs[0] > rev:
+            high = mid
+        else:
+            low = mid + 1
+
+    if low == len(data):
+        data.append((pycompat.xrange(rev, rev + 1), t))
+        return
+
+    r1, t1 = data[low]
+    if r1[0] > rev:
+        data.insert(low, (pycompat.xrange(rev, rev + 1), t))
+    else:
+        data.insert(low + 1, (pycompat.xrange(rev, rev + 1), t))
 
 
 class phasecache(object):
@@ -400,8 +484,9 b' class phasecache(object):'
             phasetracking = tr.changes[b'phases']
             torev = repo.changelog.rev
             phase = self.phase
-            for n in nodes:
-                rev = torev(n)
+            revs = [torev(node) for node in nodes]
+            revs.sort()
+            for rev in revs:
                 revphase = phase(repo, rev)
                 _trackphasechange(phasetracking, rev, None, revphase)
         repo.invalidatevolatilesets()
@@ -485,7 +570,7 b' class phasecache(object):'
                     affected -= revs
                 else:  # public phase
                     revs = affected
-                for r in revs:
+                for r in sorted(revs):
                     _trackphasechange(phasetracking, r, phase, targetphase)
         repo.invalidatevolatilesets()
 

mercurial/scmutil.py

@@ -2058,14 +2058,11 b' def registersummarycallback(repo, otr, t'
             pull/unbundle.
             """
             origrepolen = tr.changes.get(b'origrepolen', len(repo))
-            phasetracking = tr.changes.get(b'phases', {})
-            if not phasetracking:
-                return
-            published = [
-                rev
-                for rev, (old, new) in pycompat.iteritems(phasetracking)
-                if new == phases.public and rev < origrepolen
-            ]
+            published = []
+            for revs, (old, new) in tr.changes.get(b'phases', []):
+                if new != phases.public:
+                    continue
+                published.extend(rev for rev in revs if rev < origrepolen)
             if not published:
                 return
             msg = _(b'%d local changesets published\n')

tests/testlib/ext-phase-report.py

@@ -5,21 +5,22 b' from __future__ import absolute_import'
 
 def reposetup(ui, repo):
     def reportphasemove(tr):
-        for rev, move in sorted(tr.changes[b'phases'].items()):
-            if move[0] is None:
-                ui.write(
-                    (
-                        b'test-debug-phase: new rev %d:  x -> %d\n'
-                        % (rev, move[1])
+        for revs, move in sorted(tr.changes[b"phases"], key=lambda r: r[0][0]):
+            for rev in revs:
+                if move[0] is None:
+                    ui.write(
+                        (
+                            b'test-debug-phase: new rev %d:  x -> %d\n'
+                            % (rev, move[1])
+                        )
                     )
-                )
-            else:
-                ui.write(
-                    (
-                        b'test-debug-phase: move rev %d: %d -> %d\n'
-                        % (rev, move[0], move[1])
+                else:
+                    ui.write(
+                        (
+                            b'test-debug-phase: move rev %d: %d -> %d\n'
+                            % (rev, move[0], move[1])
+                        )
                     )
-                )
 
     class reportphaserepo(repo.__class__):
         def transaction(self, *args, **kwargs):