mercurial-scm/hg-stable: mercurial/revlogutils/nodemap.py annotate

annotate mercurial/revlogutils/nodemap.py @ 44367:50ad851efd9b

nodemap: introduce append-only incremental update of the persistent data Rewriting the full nodemap for each transaction has a cost we would like to avoid. We introduce a new way to write persistent nodemap data by adding new information at the end for file. Any new and updated block as added at the end of the file. The last block is the new root node. With this method, some of the block already on disk get "dereferenced" and become dead data. In later changesets, We'll start tracking the amount of dead data to eventually re-generate a full nodemap. Differential Revision: https://phab.mercurial-scm.org/D7886

author	Pierre-Yves David <pierre-yves.david@octobus.net>
date	Wed, 15 Jan 2020 15:49:54 +0100
parents	76a96e3a2bbb
children	e41a164db7a9

rev	line source
44035 ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	1 # nodemap.py - nodemap related code and utilities
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	2 #
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	3 # Copyright 2019 Pierre-Yves David <pierre-yves.david@octobus.net>
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	4 # Copyright 2019 George Racinet <georges.racinet@octobus.net>
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	5 #
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap 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
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	7 # GNU General Public License version 2 or any later version.
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	8
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	9 from __future__ import absolute_import
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	10
44354 2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	11 import os
44355 563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	12 import re
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	13 import struct
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	14
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	15 from .. import (
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	16 error,
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	17 node as nodemod,
44357 7f4f7ef3133e nodemap: add a optional `nodemap_add_full` method on indexes Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44355 diff changeset	18 util,
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	19 )
44035 ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	20
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	21
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	22 class NodeMap(dict):
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	23 def __missing__(self, x):
ab595920de0e revlogutils: move the NodeMap class in a dedicated nodemap module Pierre-Yves David <pierre-yves.david@octobus.net> parents: diff changeset	24 raise error.RevlogError(b'unknown node: %s' % x)
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	25
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	26
44352 6c07480d6659 nodemap: add a function to read the data from disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44351 diff changeset	27 def persisted_data(revlog):
6c07480d6659 nodemap: add a function to read the data from disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44351 diff changeset	28 """read the nodemap for a revlog from disk"""
6c07480d6659 nodemap: add a function to read the data from disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44351 diff changeset	29 if revlog.nodemap_file is None:
6c07480d6659 nodemap: add a function to read the data from disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44351 diff changeset	30 return None
44354 2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	31 pdata = revlog.opener.tryread(revlog.nodemap_file)
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	32 if not pdata:
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	33 return None
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	34 offset = 0
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	35 (version,) = S_VERSION.unpack(pdata[offset : offset + S_VERSION.size])
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	36 if version != ONDISK_VERSION:
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	37 return None
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	38 offset += S_VERSION.size
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	39 (uid_size,) = S_HEADER.unpack(pdata[offset : offset + S_HEADER.size])
44354 2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	40 offset += S_HEADER.size
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	41 docket = NodeMapDocket(pdata[offset : offset + uid_size])
44354 2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	42
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	43 filename = _rawdata_filepath(revlog, docket)
44366 76a96e3a2bbb nodemap: keep track of the docket for loaded data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44365 diff changeset	44 return docket, revlog.opener.tryread(filename)
44352 6c07480d6659 nodemap: add a function to read the data from disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44351 diff changeset	45
6c07480d6659 nodemap: add a function to read the data from disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44351 diff changeset	46
44351 5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	47 def setup_persistent_nodemap(tr, revlog):
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	48 """Install whatever is needed transaction side to persist a nodemap on disk
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	49
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	50 (only actually persist the nodemap if this is relevant for this revlog)
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	51 """
44353 daad3aace942 nodemap: only use persistent nodemap for non-inlined revlog Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44352 diff changeset	52 if revlog._inline:
daad3aace942 nodemap: only use persistent nodemap for non-inlined revlog Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44352 diff changeset	53 return # inlined revlog are too small for this to be relevant
44351 5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	54 if revlog.nodemap_file is None:
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	55 return # we do not use persistent_nodemap on this revlog
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	56 callback_id = b"revlog-persistent-nodemap-%s" % revlog.nodemap_file
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	57 if tr.hasfinalize(callback_id):
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	58 return # no need to register again
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	59 tr.addfinalize(callback_id, lambda tr: _persist_nodemap(tr, revlog))
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	60
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	61
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	62 def _persist_nodemap(tr, revlog):
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	63 """Write nodemap data on disk for a given revlog
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	64 """
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	65 if getattr(revlog, 'filteredrevs', ()):
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	66 raise error.ProgrammingError(
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	67 "cannot persist nodemap of a filtered changelog"
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	68 )
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	69 if revlog.nodemap_file is None:
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	70 msg = "calling persist nodemap on a revlog without the feature enableb"
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	71 raise error.ProgrammingError(msg)
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	72
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	73 can_incremental = util.safehasattr(revlog.index, "nodemap_data_incremental")
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	74 ondisk_docket = revlog._nodemap_docket
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	75
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	76 # first attemp an incremental update of the data
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	77 if can_incremental and ondisk_docket is not None:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	78 target_docket = revlog._nodemap_docket.copy()
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	79 data = revlog.index.nodemap_data_incremental()
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	80 datafile = _rawdata_filepath(revlog, target_docket)
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	81 # EXP-TODO: if this is a cache, this should use a cache vfs, not a
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	82 # store vfs
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	83 with revlog.opener(datafile, b'a') as fd:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	84 fd.write(data)
44357 7f4f7ef3133e nodemap: add a optional `nodemap_add_full` method on indexes Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44355 diff changeset	85 else:
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	86 # otherwise fallback to a full new export
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	87 target_docket = NodeMapDocket()
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	88 datafile = _rawdata_filepath(revlog, target_docket)
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	89 if util.safehasattr(revlog.index, "nodemap_data_all"):
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	90 data = revlog.index.nodemap_data_all()
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	91 else:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	92 data = persistent_data(revlog.index)
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	93 # EXP-TODO: if this is a cache, this should use a cache vfs, not a
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	94 # store vfs
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	95 with revlog.opener(datafile, b'w') as fd:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	96 fd.write(data)
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	97 # EXP-TODO: if this is a cache, this should use a cache vfs, not a
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	98 # store vfs
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	99 with revlog.opener(revlog.nodemap_file, b'w', atomictemp=True) as fp:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	100 fp.write(target_docket.serialize())
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	101 revlog._nodemap_docket = target_docket
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	102 # EXP-TODO: if the transaction abort, we should remove the new data and
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	103 # reinstall the old one.
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	104
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	105 # search for old index file in all cases, some older process might have
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	106 # left one behind.
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	107 olds = _other_rawdata_filepath(revlog, target_docket)
44355 563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	108 if olds:
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	109 realvfs = getattr(revlog, '_realopener', revlog.opener)
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	110
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	111 def cleanup(tr):
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	112 for oldfile in olds:
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	113 realvfs.tryunlink(oldfile)
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	114
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	115 callback_id = b"revlog-cleanup-nodemap-%s" % revlog.nodemap_file
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	116 tr.addpostclose(callback_id, cleanup)
44354 2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	117
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	118
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	119 ### Nodemap docket file
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	120 #
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	121 # The nodemap data are stored on disk using 2 files:
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	122 #
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	123 # * a raw data files containing a persistent nodemap
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	124 # (see `Nodemap Trie` section)
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	125 #
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	126 # * a small "docket" file containing medatadata
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	127 #
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	128 # While the nodemap data can be multiple tens of megabytes, the "docket" is
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	129 # small, it is easy to update it automatically or to duplicated its content
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	130 # during a transaction.
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	131 #
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	132 # Multiple raw data can exist at the same time (The currently valid one and a
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	133 # new one beind used by an in progress transaction). To accomodate this, the
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	134 # filename hosting the raw data has a variable parts. The exact filename is
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	135 # specified inside the "docket" file.
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	136 #
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	137 # The docket file contains information to find, qualify and validate the raw
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	138 # data. Its content is currently very light, but it will expand as the on disk
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	139 # nodemap gains the necessary features to be used in production.
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	140
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	141 # version 0 is experimental, no BC garantee, do no use outside of tests.
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	142 ONDISK_VERSION = 0
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	143
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	144 S_VERSION = struct.Struct(">B")
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	145 S_HEADER = struct.Struct(">B")
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	146
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	147 ID_SIZE = 8
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	148
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	149
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	150 def _make_uid():
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	151 """return a new unique identifier.
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	152
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	153 The identifier is random and composed of ascii characters."""
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	154 return nodemod.hex(os.urandom(ID_SIZE))
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	155
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	156
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	157 class NodeMapDocket(object):
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	158 """metadata associated with persistent nodemap data
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	159
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	160 The persistent data may come from disk or be on their way to disk.
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	161 """
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	162
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	163 def __init__(self, uid=None):
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	164 if uid is None:
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	165 uid = _make_uid()
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	166 self.uid = uid
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	167
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	168 def copy(self):
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	169 return NodeMapDocket(uid=self.uid)
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	170
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	171 def serialize(self):
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	172 """return serialized bytes for a docket using the passed uid"""
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	173 data = []
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	174 data.append(S_VERSION.pack(ONDISK_VERSION))
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	175 data.append(S_HEADER.pack(len(self.uid)))
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	176 data.append(self.uid)
72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	177 return b''.join(data)
44354 2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	178
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	179
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	180 def _rawdata_filepath(revlog, docket):
44354 2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	181 """The (vfs relative) nodemap's rawdata file for a given uid"""
2b72c4ff8ed1 nodemap: use an intermediate "docket" file to carry small metadata Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44353 diff changeset	182 prefix = revlog.nodemap_file[:-2]
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	183 return b"%s-%s.nd" % (prefix, docket.uid)
44351 5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	184
5962fd0d1045 nodemap: write nodemap data on disk Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44350 diff changeset	185
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	186 def _other_rawdata_filepath(revlog, docket):
44355 563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	187 prefix = revlog.nodemap_file[:-2]
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	188 pattern = re.compile(b"(^\|/)%s-[0-9a-f]+\.nd$" % prefix)
44365 72c15641c8b4 nodemap: introduce an explicit class/object for the docket Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44364 diff changeset	189 new_file_path = _rawdata_filepath(revlog, docket)
44355 563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	190 new_file_name = revlog.opener.basename(new_file_path)
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	191 dirpath = revlog.opener.dirname(new_file_path)
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	192 others = []
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	193 for f in revlog.opener.listdir(dirpath):
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	194 if pattern.match(f) and f != new_file_name:
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	195 others.append(f)
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	196 return others
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	197
563dfdfd01a4 nodemap: delete older raw data file when creating a new ones Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44354 diff changeset	198
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	199 ### Nodemap Trie
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	200 #
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	201 # This is a simple reference implementation to compute and persist a nodemap
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	202 # trie. This reference implementation is write only. The python version of this
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	203 # is not expected to be actually used, since it wont provide performance
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	204 # improvement over existing non-persistent C implementation.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	205 #
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	206 # The nodemap is persisted as Trie using 4bits-address/16-entries block. each
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	207 # revision can be adressed using its node shortest prefix.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	208 #
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	209 # The trie is stored as a sequence of block. Each block contains 16 entries
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	210 # (signed 64bit integer, big endian). Each entry can be one of the following:
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	211 #
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	212 # * value >= 0 -> index of sub-block
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	213 # * value == -1 -> no value
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	214 # * value < -1 -> a revision value: rev = -(value+10)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	215 #
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	216 # The implementation focus on simplicity, not on performance. A Rust
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	217 # implementation should provide a efficient version of the same binary
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	218 # persistence. This reference python implementation is never meant to be
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	219 # extensively use in production.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	220
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	221
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	222 def persistent_data(index):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	223 """return the persistent binary form for a nodemap for a given index
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	224 """
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	225 trie = _build_trie(index)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	226 return _persist_trie(trie)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	227
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	228
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	229 def update_persistent_data(index, root, max_idx, last_rev):
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	230 """return the incremental update for persistent nodemap from a given index
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	231 """
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	232 trie = _update_trie(index, root, last_rev)
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	233 return _persist_trie(trie, existing_idx=max_idx)
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	234
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	235
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	236 S_BLOCK = struct.Struct(">" + ("l" * 16))
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	237
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	238 NO_ENTRY = -1
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	239 # rev 0 need to be -2 because 0 is used by block, -1 is a special value.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	240 REV_OFFSET = 2
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	241
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	242
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	243 def _transform_rev(rev):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	244 """Return the number used to represent the rev in the tree.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	245
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	246 (or retrieve a rev number from such representation)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	247
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	248 Note that this is an involution, a function equal to its inverse (i.e.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	249 which gives the identity when applied to itself).
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	250 """
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	251 return -(rev + REV_OFFSET)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	252
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	253
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	254 def _to_int(hex_digit):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	255 """turn an hexadecimal digit into a proper integer"""
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	256 return int(hex_digit, 16)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	257
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	258
44358 7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	259 class Block(dict):
7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	260 """represent a block of the Trie
7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	261
7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	262 contains up to 16 entry indexed from 0 to 15"""
7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	263
44364 f0862ee1a31e nodemap: keep track of the ondisk id of nodemap blocks Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44362 diff changeset	264 def __init__(self):
f0862ee1a31e nodemap: keep track of the ondisk id of nodemap blocks Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44362 diff changeset	265 super(Block, self).__init__()
f0862ee1a31e nodemap: keep track of the ondisk id of nodemap blocks Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44362 diff changeset	266 # If this block exist on disk, here is its ID
f0862ee1a31e nodemap: keep track of the ondisk id of nodemap blocks Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44362 diff changeset	267 self.ondisk_id = None
f0862ee1a31e nodemap: keep track of the ondisk id of nodemap blocks Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44362 diff changeset	268
44359 55b12f2593c1 nodemap: move the iteratio inside the Block object Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44358 diff changeset	269 def __iter__(self):
55b12f2593c1 nodemap: move the iteratio inside the Block object Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44358 diff changeset	270 return iter(self.get(i) for i in range(16))
55b12f2593c1 nodemap: move the iteratio inside the Block object Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44358 diff changeset	271
44358 7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	272
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	273 def _build_trie(index):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	274 """build a nodemap trie
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	275
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	276 The nodemap stores revision number for each unique prefix.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	277
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	278 Each block is a dictionary with keys in `[0, 15]`. Values are either
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	279 another block or a revision number.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	280 """
44358 7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	281 root = Block()
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	282 for rev in range(len(index)):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	283 hex = nodemod.hex(index[rev][7])
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	284 _insert_into_block(index, 0, root, rev, hex)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	285 return root
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	286
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	287
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	288 def _update_trie(index, root, last_rev):
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	289 """consume"""
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	290 for rev in range(last_rev + 1, len(index)):
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	291 hex = nodemod.hex(index[rev][7])
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	292 _insert_into_block(index, 0, root, rev, hex)
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	293 return root
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	294
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	295
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	296 def _insert_into_block(index, level, block, current_rev, current_hex):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	297 """insert a new revision in a block
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	298
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	299 index: the index we are adding revision for
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	300 level: the depth of the current block in the trie
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	301 block: the block currently being considered
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	302 current_rev: the revision number we are adding
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	303 current_hex: the hexadecimal representation of the of that revision
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	304 """
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	305 if block.ondisk_id is not None:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	306 block.ondisk_id = None
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	307 hex_digit = _to_int(current_hex[level : level + 1])
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	308 entry = block.get(hex_digit)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	309 if entry is None:
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	310 # no entry, simply store the revision number
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	311 block[hex_digit] = current_rev
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	312 elif isinstance(entry, dict):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	313 # need to recurse to an underlying block
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	314 _insert_into_block(index, level + 1, entry, current_rev, current_hex)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	315 else:
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	316 # collision with a previously unique prefix, inserting new
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	317 # vertices to fit both entry.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	318 other_hex = nodemod.hex(index[entry][7])
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	319 other_rev = entry
44358 7762a295fd4d nodemap: use an explicit "Block" object in the reference implementation Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44357 diff changeset	320 new = Block()
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	321 block[hex_digit] = new
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	322 _insert_into_block(index, level + 1, new, other_rev, other_hex)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	323 _insert_into_block(index, level + 1, new, current_rev, current_hex)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	324
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	325
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	326 def _persist_trie(root, existing_idx=None):
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	327 """turn a nodemap trie into persistent binary data
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	328
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	329 See `_build_trie` for nodemap trie structure"""
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	330 block_map = {}
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	331 if existing_idx is not None:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	332 base_idx = existing_idx + 1
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	333 else:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	334 base_idx = 0
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	335 chunks = []
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	336 for tn in _walk_trie(root):
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	337 if tn.ondisk_id is not None:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	338 block_map[id(tn)] = tn.ondisk_id
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	339 else:
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	340 block_map[id(tn)] = len(chunks) + base_idx
50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	341 chunks.append(_persist_block(tn, block_map))
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	342 return b''.join(chunks)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	343
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	344
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	345 def _walk_trie(block):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	346 """yield all the block in a trie
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	347
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	348 Children blocks are always yield before their parent block.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	349 """
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	350 for (_, item) in sorted(block.items()):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	351 if isinstance(item, dict):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	352 for sub_block in _walk_trie(item):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	353 yield sub_block
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	354 yield block
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	355
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	356
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	357 def _persist_block(block_node, block_map):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	358 """produce persistent binary data for a single block
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	359
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	360 Children block are assumed to be already persisted and present in
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	361 block_map.
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	362 """
44359 55b12f2593c1 nodemap: move the iteratio inside the Block object Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44358 diff changeset	363 data = tuple(_to_value(v, block_map) for v in block_node)
44350 c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	364 return S_BLOCK.pack(*data)
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	365
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	366
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	367 def _to_value(item, block_map):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	368 """persist any value as an integer"""
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	369 if item is None:
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	370 return NO_ENTRY
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	371 elif isinstance(item, dict):
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	372 return block_map[id(item)]
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	373 else:
c577bb4a04d4 nodemap: have some python code writing a nodemap in persistent binary form Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44035 diff changeset	374 return _transform_rev(item)
44360 78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	375
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	376
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	377 def parse_data(data):
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	378 """parse parse nodemap data into a nodemap Trie"""
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	379 if (len(data) % S_BLOCK.size) != 0:
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	380 msg = "nodemap data size is not a multiple of block size (%d): %d"
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	381 raise error.Abort(msg % (S_BLOCK.size, len(data)))
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	382 if not data:
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	383 return Block(), None
44360 78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	384 block_map = {}
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	385 new_blocks = []
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	386 for i in range(0, len(data), S_BLOCK.size):
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	387 block = Block()
44364 f0862ee1a31e nodemap: keep track of the ondisk id of nodemap blocks Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44362 diff changeset	388 block.ondisk_id = len(block_map)
f0862ee1a31e nodemap: keep track of the ondisk id of nodemap blocks Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44362 diff changeset	389 block_map[block.ondisk_id] = block
44360 78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	390 block_data = data[i : i + S_BLOCK.size]
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	391 values = S_BLOCK.unpack(block_data)
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	392 new_blocks.append((block, values))
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	393 for b, values in new_blocks:
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	394 for idx, v in enumerate(values):
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	395 if v == NO_ENTRY:
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	396 continue
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	397 elif v >= 0:
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	398 b[idx] = block_map[v]
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	399 else:
78721bbdb2ab nodemap: code to parse the persistent binary nodemap data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44359 diff changeset	400 b[idx] = _transform_rev(v)
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	401 return block, i // S_BLOCK.size
44361 20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	402
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	403
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	404 # debug utility
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	405
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	406
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	407 def check_data(ui, index, data):
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	408 """verify that the provided nodemap data are valid for the given idex"""
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	409 ret = 0
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	410 ui.status((b"revision in index: %d\n") % len(index))
44367 50ad851efd9b nodemap: introduce append-only incremental update of the persistent data Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44366 diff changeset	411 root, __ = parse_data(data)
44361 20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	412 all_revs = set(_all_revisions(root))
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	413 ui.status((b"revision in nodemap: %d\n") % len(all_revs))
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	414 for r in range(len(index)):
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	415 if r not in all_revs:
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	416 msg = b" revision missing from nodemap: %d\n" % r
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	417 ui.write_err(msg)
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	418 ret = 1
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	419 else:
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	420 all_revs.remove(r)
44362 d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	421 nm_rev = _find_node(root, nodemod.hex(index[r][7]))
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	422 if nm_rev is None:
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	423 msg = b" revision node does not match any entries: %d\n" % r
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	424 ui.write_err(msg)
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	425 ret = 1
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	426 elif nm_rev != r:
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	427 msg = (
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	428 b" revision node does not match the expected revision: "
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	429 b"%d != %d\n" % (r, nm_rev)
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	430 )
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	431 ui.write_err(msg)
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	432 ret = 1
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	433
44361 20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	434 if all_revs:
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	435 for r in sorted(all_revs):
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	436 msg = b" extra revision in nodemap: %d\n" % r
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	437 ui.write_err(msg)
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	438 ret = 1
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	439 return ret
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	440
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	441
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	442 def _all_revisions(root):
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	443 """return all revisions stored in a Trie"""
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	444 for block in _walk_trie(root):
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	445 for v in block:
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	446 if v is None or isinstance(v, Block):
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	447 continue
20e125cdd719 nodemap: add basic checking of the on disk nodemap content Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44360 diff changeset	448 yield v
44362 d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	449
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	450
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	451 def _find_node(block, node):
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	452 """find the revision associated with a given node"""
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	453 entry = block.get(_to_int(node[0:1]))
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	454 if isinstance(entry, dict):
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	455 return _find_node(entry, node[1:])
d58206b70199 nodemap: all check that revision and nodes match in the nodemap Pierre-Yves David <pierre-yves.david@octobus.net> parents: 44361 diff changeset	456 return entry

Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/revlogutils/nodemap.py @ 44367:50ad851efd9b