1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
|
# Copyright 2016-present Facebook. All Rights Reserved.
#
# revmap: trivial hg hash - linelog rev bidirectional map
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
import bisect
import io
import os
import struct
from mercurial.node import hex
from mercurial.pycompat import open
from mercurial import (
error as hgerror,
)
from . import error
# the revmap file format is straightforward:
#
# 8 bytes: header
# 1 byte : flag for linelog revision 1
# ? bytes: (optional) '\0'-terminated path string
# only exists if (flag & renameflag) != 0
# 20 bytes: hg hash for linelog revision 1
# 1 byte : flag for linelog revision 2
# ? bytes: (optional) '\0'-terminated path string
# 20 bytes: hg hash for linelog revision 2
# ....
#
# the implementation is kinda stupid: __init__ loads the whole revmap.
# no laziness. benchmark shows loading 10000 revisions is about 0.015
# seconds, which looks enough for our use-case. if this implementation
# becomes a bottleneck, we can change it to lazily read the file
# from the end.
# whether the changeset is in the side branch. i.e. not in the linear main
# branch but only got referenced by lines in merge changesets.
sidebranchflag = 1
# whether the changeset changes the file path (ie. is a rename)
renameflag = 2
# len(mercurial.node.nullid)
_hshlen = 20
class revmap:
"""trivial hg bin hash - linelog rev bidirectional map
also stores a flag (uint8) for each revision, and track renames.
"""
HEADER = b'REVMAP1\0'
def __init__(self, path=None):
"""create or load the revmap, optionally associate to a file
if path is None, the revmap is entirely in-memory. the caller is
responsible for locking. concurrent writes to a same file is unsafe.
the caller needs to make sure one file is associated to at most one
revmap object at a time."""
self.path = path
self._rev2hsh = [None]
self._rev2flag = [None]
self._hsh2rev = {}
# since rename does not happen frequently, do not store path for every
# revision. self._renamerevs can be used for bisecting.
self._renamerevs = [0]
self._renamepaths = [b'']
self._lastmaxrev = -1
if path:
if os.path.exists(path):
self._load()
else:
# write the header so "append" can do incremental updates
self.flush()
def copyfrom(self, rhs):
"""copy the map data from another revmap. do not affect self.path"""
self._rev2hsh = rhs._rev2hsh[:]
self._rev2flag = rhs._rev2flag[:]
self._hsh2rev = rhs._hsh2rev.copy()
self._renamerevs = rhs._renamerevs[:]
self._renamepaths = rhs._renamepaths[:]
self._lastmaxrev = -1
@property
def maxrev(self):
"""return max linelog revision number"""
return len(self._rev2hsh) - 1
def append(self, hsh, sidebranch=False, path=None, flush=False):
"""add a binary hg hash and return the mapped linelog revision.
if flush is True, incrementally update the file.
"""
if hsh in self._hsh2rev:
raise error.CorruptedFileError(
b'%r is in revmap already' % hex(hsh)
)
if len(hsh) != _hshlen:
raise hgerror.ProgrammingError(
b'hsh must be %d-char long' % _hshlen
)
idx = len(self._rev2hsh)
flag = 0
if sidebranch:
flag |= sidebranchflag
if path is not None and path != self._renamepaths[-1]:
flag |= renameflag
self._renamerevs.append(idx)
self._renamepaths.append(path)
self._rev2hsh.append(hsh)
self._rev2flag.append(flag)
self._hsh2rev[hsh] = idx
if flush:
self.flush()
return idx
def rev2hsh(self, rev):
"""convert linelog revision to hg hash. return None if not found."""
if rev > self.maxrev or rev < 0:
return None
return self._rev2hsh[rev]
def rev2flag(self, rev):
"""get the flag (uint8) for a given linelog revision.
return None if revision does not exist.
"""
if rev > self.maxrev or rev < 0:
return None
return self._rev2flag[rev]
def rev2path(self, rev):
"""get the path for a given linelog revision.
return None if revision does not exist.
"""
if rev > self.maxrev or rev < 0:
return None
idx = bisect.bisect_right(self._renamerevs, rev) - 1
return self._renamepaths[idx]
def hsh2rev(self, hsh):
"""convert hg hash to linelog revision. return None if not found."""
return self._hsh2rev.get(hsh)
def clear(self, flush=False):
"""make the map empty. if flush is True, write to disk"""
# rev 0 is reserved, real rev starts from 1
self._rev2hsh = [None]
self._rev2flag = [None]
self._hsh2rev = {}
self._rev2path = [b'']
self._lastmaxrev = -1
if flush:
self.flush()
def flush(self):
"""write the state down to the file"""
if not self.path:
return
if self._lastmaxrev == -1: # write the entire file
with open(self.path, b'wb') as f:
f.write(self.HEADER)
for i in range(1, len(self._rev2hsh)):
self._writerev(i, f)
else: # append incrementally
with open(self.path, b'ab') as f:
for i in range(self._lastmaxrev + 1, len(self._rev2hsh)):
self._writerev(i, f)
self._lastmaxrev = self.maxrev
def _load(self):
"""load state from file"""
if not self.path:
return
# use local variables in a loop. CPython uses LOAD_FAST for them,
# which is faster than both LOAD_CONST and LOAD_GLOBAL.
flaglen = 1
hshlen = _hshlen
with open(self.path, b'rb') as f:
if f.read(len(self.HEADER)) != self.HEADER:
raise error.CorruptedFileError()
self.clear(flush=False)
while True:
buf = f.read(flaglen)
if not buf:
break
flag = ord(buf)
rev = len(self._rev2hsh)
if flag & renameflag:
path = self._readcstr(f)
self._renamerevs.append(rev)
self._renamepaths.append(path)
hsh = f.read(hshlen)
if len(hsh) != hshlen:
raise error.CorruptedFileError()
self._hsh2rev[hsh] = rev
self._rev2flag.append(flag)
self._rev2hsh.append(hsh)
self._lastmaxrev = self.maxrev
def _writerev(self, rev, f):
"""append a revision data to file"""
flag = self._rev2flag[rev]
hsh = self._rev2hsh[rev]
f.write(struct.pack(b'B', flag))
if flag & renameflag:
path = self.rev2path(rev)
if path is None:
raise error.CorruptedFileError(b'cannot find path for %s' % rev)
f.write(path + b'\0')
f.write(hsh)
@staticmethod
def _readcstr(f):
"""read a C-language-like '\0'-terminated string"""
buf = b''
while True:
ch = f.read(1)
if not ch: # unexpected eof
raise error.CorruptedFileError()
if ch == b'\0':
break
buf += ch
return buf
def __contains__(self, f):
"""(fctx or (node, path)) -> bool.
test if (node, path) is in the map, and is not in a side branch.
f can be either a tuple of (node, path), or a fctx.
"""
if isinstance(f, tuple): # f: (node, path)
hsh, path = f
else: # f: fctx
hsh, path = f.node(), f.path()
rev = self.hsh2rev(hsh)
if rev is None:
return False
if path is not None and path != self.rev2path(rev):
return False
return (self.rev2flag(rev) & sidebranchflag) == 0
def getlastnode(path):
"""return the last hash in a revmap, without loading its full content.
this is equivalent to `m = revmap(path); m.rev2hsh(m.maxrev)`, but faster.
"""
hsh = None
try:
with open(path, b'rb') as f:
f.seek(-_hshlen, io.SEEK_END)
if f.tell() > len(revmap.HEADER):
hsh = f.read(_hshlen)
except IOError:
pass
return hsh
|