branchcache: add a "pure topological head" fast path

In a narrow but actually quick common case, all topological heads are all on
the same branch and all open. In this case, computing the branch map is very
simple. We can quickly detect situation where this situation will not change.

So we update the V3 format to be able to express this situation and upgrade the
update code to detect we remains in that mode.

The branch cache is populated with the actual value when the branch map is
accessed, but the update_disk method can do the update without needing to
populate it.

mercurial/branchmap.py

@@ -62,6 +62,7 b' class BranchMapCache:'
     def __getitem__(self, repo):
         self.updatecache(repo)
         bcache = self._per_filter[repo.filtername]
+        bcache._ensure_populated(repo)
         assert bcache._filtername == repo.filtername, (
             bcache._filtername,
             repo.filtername,
@@ -484,6 +485,9 b' class _LocalBranchCache(_BaseBranchCache'
     def _compute_key_hashes(self, repo) -> Tuple[bytes]:
         raise NotImplementedError
 
+    def _ensure_populated(self, repo):
+        """make sure any lazily loaded values are fully populated"""
+
     def validfor(self, repo):
         """check that cache contents are valid for (a subset of) this repo
 
@@ -861,7 +865,18 b' class BranchCacheV3(_LocalBranchCache):'
     _base_filename = b"branch3"
     _default_key_hashes = (None, None)
 
-    def _get_topo_heads(self, repo) -> List[int]:
+    def __init__(self, *args, pure_topo_branch=None, **kwargs):
+        super().__init__(*args, **kwargs)
+        self._pure_topo_branch = pure_topo_branch
+        self._needs_populate = self._pure_topo_branch is not None
+
+    def inherit_for(self, repo):
+        new = super().inherit_for(repo)
+        new._pure_topo_branch = self._pure_topo_branch
+        new._needs_populate = self._needs_populate
+        return new
+
+    def _get_topo_heads(self, repo):
         """returns the topological head of a repoview content up to self.tiprev"""
         cl = repo.changelog
         if self.tiprev == nullrev:
@@ -883,22 +898,33 b' class BranchCacheV3(_LocalBranchCache):'
                 cache_keys[b"filtered-hash"] = hex(self.key_hashes[0])
             if self.key_hashes[1] is not None:
                 cache_keys[b"obsolete-hash"] = hex(self.key_hashes[1])
+        if self._pure_topo_branch is not None:
+            cache_keys[b"topo-mode"] = b"pure"
         pieces = (b"%s=%s" % i for i in sorted(cache_keys.items()))
         fp.write(b" ".join(pieces) + b'\n')
+        if self._pure_topo_branch is not None:
+            label = encoding.fromlocal(self._pure_topo_branch)
+            fp.write(label + b'\n')
 
     def _write_heads(self, repo, fp) -> int:
         """write list of heads to a file
 
         Return the number of heads written."""
         nodecount = 0
-        topo_heads = set(self._get_topo_heads(repo))
+        topo_heads = None
+        if self._pure_topo_branch is None:
+            topo_heads = set(self._get_topo_heads(repo))
         to_rev = repo.changelog.index.rev
         for label, nodes in sorted(self._entries.items()):
+            if label == self._pure_topo_branch:
+                # not need to write anything the header took care of that
+                continue
             label = encoding.fromlocal(label)
             for node in nodes:
-                rev = to_rev(node)
-                if rev in topo_heads:
-                    continue
+                if topo_heads is not None:
+                    rev = to_rev(node)
+                    if rev in topo_heads:
+                        continue
                 if node in self._closednodes:
                     state = b'c'
                 else:
@@ -916,6 +942,7 b' class BranchCacheV3(_LocalBranchCache):'
         args = {}
         filtered_hash = None
         obsolete_hash = None
+        has_pure_topo_heads = False
         for k, v in cache_keys.items():
             if k == b"tip-rev":
                 args["tiprev"] = int(v)
@@ -925,16 +952,28 b' class BranchCacheV3(_LocalBranchCache):'
                 filtered_hash = bin(v)
             elif k == b"obsolete-hash":
                 obsolete_hash = bin(v)
+            elif k == b"topo-mode":
+                if v == b"pure":
+                    has_pure_topo_heads = True
+                else:
+                    msg = b"unknown topo-mode: %r" % v
+                    raise ValueError(msg)
             else:
                 msg = b"unknown cache key: %r" % k
                 raise ValueError(msg)
         args["key_hashes"] = (filtered_hash, obsolete_hash)
+        if has_pure_topo_heads:
+            pure_line = next(lineiter).rstrip(b'\n')
+            args["pure_topo_branch"] = encoding.tolocal(pure_line)
         return args
 
     def _load_heads(self, repo, lineiter):
         """fully loads the branchcache by reading from the file using the line
         iterator passed"""
         super()._load_heads(repo, lineiter)
+        if self._pure_topo_branch is not None:
+            # no need to read the repository heads, we know their value already.
+            return
         cl = repo.changelog
         getbranchinfo = repo.revbranchcache().branchinfo
         obsrevs = obsolete.getrevs(repo, b'obsolete')
@@ -960,6 +999,62 b' class BranchCacheV3(_LocalBranchCache):'
             self.tiprev,
         )
 
+    def _process_new(
+        self,
+        repo,
+        newbranches,
+        new_closed,
+        obs_ignored,
+        max_rev,
+    ) -> None:
+        if (
+            # note: the check about `obs_ignored` is too strict as the
+            # obsolete revision could be non-topological, but lets keep
+            # things simple for now
+            #
+            # The same apply to `new_closed` if the closed changeset are
+            # not a head, we don't care that it is closed, but lets keep
+            # things simple here too.
+            not (obs_ignored or new_closed)
+            and (
+                not newbranches
+                or (
+                    len(newbranches) == 1
+                    and (
+                        self.tiprev == nullrev
+                        or self._pure_topo_branch in newbranches
+                    )
+                )
+            )
+        ):
+            if newbranches:
+                assert len(newbranches) == 1
+                self._pure_topo_branch = list(newbranches.keys())[0]
+                self._needs_populate = True
+                self._entries.pop(self._pure_topo_branch, None)
+            return
+
+        self._ensure_populated(repo)
+        self._pure_topo_branch = None
+        super()._process_new(
+            repo,
+            newbranches,
+            new_closed,
+            obs_ignored,
+            max_rev,
+        )
+
+    def _ensure_populated(self, repo):
+        """make sure any lazily loaded values are fully populated"""
+        if self._needs_populate:
+            assert self._pure_topo_branch is not None
+            cl = repo.changelog
+            to_node = cl.node
+            topo_heads = self._get_topo_heads(repo)
+            heads = [to_node(r) for r in topo_heads]
+            self._entries[self._pure_topo_branch] = heads
+            self._needs_populate = False
+
 
 class remotebranchcache(_BaseBranchCache):
     """Branchmap info for a remote connection, should not write locally"""

tests/test-branches-obsolete.t

@@ -113,6 +113,19 b' We want some branching and some obsolesc'
   |
   o  root
   
+
+#if v2
+  $ show_cache
+  ##### .hg/cache/branch2-served
+  3d808bbc94408ea19da905596d4079357a1f28be 8
+  63ba7cd843d1e95aac1a24435befeb1909c53619 o default
+  3d808bbc94408ea19da905596d4079357a1f28be o default
+#else
+  $ show_cache
+  ##### .hg/cache/branch3-served
+  tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8 topo-mode=pure
+  default
+#endif
   $ hg log -T '{desc}\n' --rev 'head()'
   B_4
   A_4
@@ -157,7 +170,8 b' Absolete a couple of changes'
 #else
   $ show_cache
   ##### .hg/cache/branch3-served
-  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7
+  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7 topo-mode=pure
+  default
 #endif
   $ cd ..
 
@@ -209,7 +223,6 b' Revealing tipmost changeset'
   $ show_cache
   ##### .hg/cache/branch3
   obsolete-hash=b6d2b1f5b70f09c25c835edcae69be35f681605c tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8
-  550bb31f072912453ccbb503de1d554616911e88 o default
   7c29ff2453bf38c75ee8982935739103c38a9284 o default
   ##### .hg/cache/branch3-served
   filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 obsolete-hash=ac5282439f301518f362f37547fcd52bcc670373 tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8
@@ -251,7 +264,8 b' And we can get back to normal'
 #else
   $ show_cache
   ##### .hg/cache/branch3-served
-  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7
+  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7 topo-mode=pure
+  default
 #endif
 
   $ cd ..
@@ -299,7 +313,6 b' Check that revealing an obsolete changes'
   $ show_cache
   ##### .hg/cache/branch3
   obsolete-hash=b6d2b1f5b70f09c25c835edcae69be35f681605c tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8
-  550bb31f072912453ccbb503de1d554616911e88 o default
   7c29ff2453bf38c75ee8982935739103c38a9284 o default
   ##### .hg/cache/branch3-served
   filtered-hash=f1456c0d675980582dda9b8edc7f13f503ce544f obsolete-hash=3e74f5349008671629e39d13d7e00d9ba94c74f7 tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7
@@ -341,7 +354,8 b' And we can get back to normal'
 #else
   $ show_cache
   ##### .hg/cache/branch3-served
-  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7
+  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7 topo-mode=pure
+  default
 #endif
 
   $ cd ..
@@ -434,7 +448,8 b' And we can get back to normal'
 #else
   $ show_cache
   ##### .hg/cache/branch3-served
-  tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7
+  tip-node=7c29ff2453bf38c75ee8982935739103c38a9284 tip-rev=7 topo-mode=pure
+  default
 #endif
 
   $ cd ..
@@ -477,7 +492,8 b' Getting the obsolescence marker after th'
 #else
   $ show_cache
   ##### .hg/cache/branch3-served
-  tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8
+  tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8 topo-mode=pure
+  default
 #endif
 
   $ hg pull --rev `cat ../main-single-branch-node_B4` --remote-hidden
@@ -539,7 +555,8 b' And we can get back to normal'
 #else
   $ show_cache
   ##### .hg/cache/branch3-served
-  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8
+  filtered-hash=f8006d64a10d35c011a5c5fa88be1e25c5929514 tip-node=3d808bbc94408ea19da905596d4079357a1f28be tip-rev=8 topo-mode=pure
+  default
 #endif
 
   $ cd ..

tests/test-branches.t

@@ -1312,7 +1312,8 b' Unbundling revision should warm the serv'
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
 #if v3
   $ cat branchmap-update-01/.hg/cache/branch3-base
-  tip-node=99ba08759bc7f6fdbe5304e83d0387f35c082479 tip-rev=1
+  tip-node=99ba08759bc7f6fdbe5304e83d0387f35c082479 tip-rev=1 topo-mode=pure
+  A
 #else
   $ cat branchmap-update-01/.hg/cache/branch2-base
   99ba08759bc7f6fdbe5304e83d0387f35c082479 1
@@ -1327,7 +1328,8 b' Unbundling revision should warm the serv'
   (run 'hg update' to get a working copy)
 #if v3
   $ cat branchmap-update-01/.hg/cache/branch3-served
-  tip-node=71ca9a6d524ed3c2a215119b2086ac3b8c4c8286 tip-rev=3
+  tip-node=71ca9a6d524ed3c2a215119b2086ac3b8c4c8286 tip-rev=3 topo-mode=pure
+  A
 #else
   $ cat branchmap-update-01/.hg/cache/branch2-served
   71ca9a6d524ed3c2a215119b2086ac3b8c4c8286 3
@@ -1356,7 +1358,8 b' aborted Unbundle should not update the o'
 
 #if v3
   $ cat branchmap-update-02/.hg/cache/branch3-base
-  tip-node=99ba08759bc7f6fdbe5304e83d0387f35c082479 tip-rev=1
+  tip-node=99ba08759bc7f6fdbe5304e83d0387f35c082479 tip-rev=1 topo-mode=pure
+  A
 #else
   $ cat branchmap-update-02/.hg/cache/branch2-base
   99ba08759bc7f6fdbe5304e83d0387f35c082479 1
@@ -1372,7 +1375,8 b' aborted Unbundle should not update the o'
   [40]
 #if v3
   $ cat branchmap-update-02/.hg/cache/branch3-base
-  tip-node=99ba08759bc7f6fdbe5304e83d0387f35c082479 tip-rev=1
+  tip-node=99ba08759bc7f6fdbe5304e83d0387f35c082479 tip-rev=1 topo-mode=pure
+  A
 #else
   $ cat branchmap-update-02/.hg/cache/branch2-base
   99ba08759bc7f6fdbe5304e83d0387f35c082479 1