annotate mercurial/utils/repoviewutil.py @ 51528:f85f23f1479b

branchcache: skip entries that are topological heads in the on disk file In the majority of cases, topological heads are also branch heads. We have efficient way to get the topological heads and efficient way to retrieve their branch information. So there is little value in putting them in the branch cache file explicitly. On the contrary, writing them explicitly tend to create very large cache file that are inefficient to read and update. So the branch cache v3 format is no longer including them. This changeset focus on the format aspect and have no focus on the performance aspect. We will cover that later.
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Thu, 07 Mar 2024 10:55:22 +0100
parents 1a9bdd0e1c44
children f4733654f144
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
42138
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
1 # repoviewutil.py - constaints data relevant to repoview.py and other module
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
2 #
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
3 # Copyright 2012 Pierre-Yves David <pierre-yves.david@ens-lyon.org>
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
4 # Logilab SA <contact@logilab.fr>
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
5 #
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
6 # This software may be used and distributed according to the terms of the
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
7 # GNU General Public License version 2 or any later version.
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
8
51484
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
9 from .. import error
42138
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
10
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
11 ### Nearest subset relation
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
12 # Nearest subset of filter X is a filter Y so that:
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
13 # * Y is included in X,
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
14 # * X - Y is as small as possible.
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
15 # This create and ordering used for branchmap purpose.
caebe5e7f4bd repoview: move subsettable in a dedicated module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
16 # the ordering may be partial
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42138
diff changeset
17 subsettable = {
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
18 None: b'visible',
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
19 b'visible-hidden': b'visible',
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
20 b'visible': b'served',
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
21 b'served.hidden': b'served',
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
22 b'served': b'immutable',
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
23 b'immutable': b'base',
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42138
diff changeset
24 }
51484
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
25
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
26
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
27 def get_ordered_subset():
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
28 """return a list of subset name from dependencies to dependents"""
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
29 _unfinalized = set(subsettable.values())
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
30 ordered = []
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
31
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
32 # the subset table is expected to be small so we do the stupid N² version
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
33 # of the algorithm
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
34 while _unfinalized:
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
35 this_level = []
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
36 for candidate in _unfinalized:
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
37 dependency = subsettable.get(candidate)
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
38 if dependency not in _unfinalized:
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
39 this_level.append(candidate)
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
40
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
41 if not this_level:
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
42 msg = "cyclic dependencies in repoview subset %r"
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
43 msg %= subsettable
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
44 raise error.ProgrammingError(msg)
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
45
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
46 this_level.sort(key=lambda x: x if x is not None else '')
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
47
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
48 ordered.extend(this_level)
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
49 _unfinalized.difference_update(this_level)
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
50
1a9bdd0e1c44 branchcache: write branchmap in subset inheritance order
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 48875
diff changeset
51 return ordered