( )⚙ D8679 manifest: tigher manifest parsing and flag use

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D8679

manifest: tigher manifest parsing and flag use
ClosedPublic

Authored by joerg.sonnenberger on Jul 5 2020, 9:45 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGd0ef8c1dddd4: manifest: tigher manifest parsing and flag use
Summary

In the manifest line, flags are put directly after the hash, so the
parser has been guessing the presence of flags based on the length of
the hash. Replace this assumption by an enumeration of the valid flags
and removing them from the hash first as they are distinct input values.

Consistently handle the expected 256bit length of the SHA1-replacement
in the pure Python parser. Check that setting flags will use one of the
blessed values.

Extend write logic in the C version to handle 256bit hashes as well.

Verify that hashes always have exactly the expected length. Since
1070df141718 we should no longer depend on the old extra-byte hack.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

joerg.sonnenberger added a comment.Jul 5 2020, 10:05 PM

I'm still working on this changeset to assert the "extra bytes in node" nonsense documented in some places, if someone has a case to actually trigger that it would be very helpful.

joerg.sonnenberger edited the summary of this revision. (Show Details)Jul 6 2020, 7:38 AM
joerg.sonnenberger updated this revision to Diff 21769.
joerg.sonnenberger added a commit: rHGd0ef8c1dddd4: manifest: tigher manifest parsing and flag use.Jul 15 2020, 12:14 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGd0ef8c1dddd4: manifest: tigher manifest parsing and flag use (authored by joerg.sonnenberger). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/manifest.c (74 lines)
Mmercurial/manifest.py (57 lines)
Mmercurial/merge.py (3 lines)
Mtests/test-manifest.py (33 lines)

Diff 21919

mercurial/cext/manifest.c

/* get the length of the path for a line */ /* get the length of the path for a line */
static Py_ssize_t pathlen(line *l) static Py_ssize_t pathlen(line *l)
{ {
const char *end = memchr(l->start, '\0', l->len); const char *end = memchr(l->start, '\0', l->len);
return (end) ? (Py_ssize_t)(end - l->start) : l->len; return (end) ? (Py_ssize_t)(end - l->start) : l->len;
} }
/* get the node value of a single line */ /* get the node value of a single line */
static PyObject *nodeof(line *l) static PyObject *nodeof(line *l, char *flag)
{ {
char *s = l->start; char *s = l->start;
Py_ssize_t llen = pathlen(l); Py_ssize_t llen = pathlen(l);
Py_ssize_t hlen = l->len - llen - 2; Py_ssize_t hlen = l->len - llen - 2;
Py_ssize_t hlen_raw = 20; Py_ssize_t hlen_raw;
PyObject *hash; PyObject *hash;
if (llen + 1 + 40 + 1 > l->len) { /* path '\0' hash '\n' */ if (llen + 1 + 40 + 1 > l->len) { /* path '\0' hash '\n' */
PyErr_SetString(PyExc_ValueError, "manifest line too short"); PyErr_SetString(PyExc_ValueError, "manifest line too short");
return NULL; return NULL;
} }
/* Detect flags after the hash first. */
switch (s[llen + hlen]) {
case 'l':
case 't':
case 'x':
*flag = s[llen + hlen];
--hlen;
break;
default:
*flag = '\0';
break;
}
switch (hlen) { switch (hlen) {
case 40: /* sha1 */ case 40: /* sha1 */
case 41: /* sha1 with cruft for a merge */ hlen_raw = 20;
break; break;
case 64: /* new hash */ case 64: /* new hash */
case 65: /* new hash with cruft for a merge */
hlen_raw = 32; hlen_raw = 32;
break; break;
default: default:
PyErr_SetString(PyExc_ValueError, "invalid node length in manifest"); PyErr_SetString(PyExc_ValueError, "invalid node length in manifest");
return NULL; return NULL;
} }
hash = unhexlify(s + llen + 1, hlen_raw * 2); hash = unhexlify(s + llen + 1, hlen_raw * 2);
if (!hash) { if (!hash) {
return NULL; return NULL;
} }
if (l->hash_suffix != '\0') { if (l->hash_suffix != '\0') {
char newhash[33]; char newhash[33];
memcpy(newhash, PyBytes_AsString(hash), hlen_raw); memcpy(newhash, PyBytes_AsString(hash), hlen_raw);
Py_DECREF(hash); Py_DECREF(hash);
newhash[hlen_raw] = l->hash_suffix; newhash[hlen_raw] = l->hash_suffix;
hash = PyBytes_FromStringAndSize(newhash, hlen_raw+1); hash = PyBytes_FromStringAndSize(newhash, hlen_raw+1);
} }
return hash; return hash;
} }
/* get the node hash and flags of a line as a tuple */ /* get the node hash and flags of a line as a tuple */
static PyObject *hashflags(line *l) static PyObject *hashflags(line *l)
{ {
char *s = l->start; char flag;
Py_ssize_t plen = pathlen(l); PyObject *hash = nodeof(l, &flag);
PyObject *hash = nodeof(l);
ssize_t hlen; ssize_t hlen;
Py_ssize_t hplen, flen; Py_ssize_t hplen, flen;
PyObject *flags; PyObject *flags;
PyObject *tup; PyObject *tup;
if (!hash) if (!hash)
return NULL; return NULL;
/* hash is either 20 or 21 bytes for an old hash, so we use a flags = PyBytes_FromStringAndSize(&flag, flag ? 1 : 0);
ternary here to get the "real" hexlified sha length. */
hlen = PyBytes_GET_SIZE(hash) < 22 ? 40 : 64;
/* 1 for null byte, 1 for newline */
hplen = plen + hlen + 2;
flen = l->len - hplen;
flags = PyBytes_FromStringAndSize(s + hplen - 1, flen);
if (!flags) { if (!flags) {
Py_DECREF(hash); Py_DECREF(hash);
return NULL; return NULL;
} }
tup = PyTuple_Pack(2, hash, flags); tup = PyTuple_Pack(2, hash, flags);
Py_DECREF(flags); Py_DECREF(flags);
Py_DECREF(hash); Py_DECREF(hash);
return tup; return tup;
} while (self->m->lines[self->pos].deleted); } while (self->m->lines[self->pos].deleted);
return self->m->lines + self->pos; return self->m->lines + self->pos;
} }
static PyObject *lmiter_iterentriesnext(PyObject *o) static PyObject *lmiter_iterentriesnext(PyObject *o)
{ {
Py_ssize_t pl; Py_ssize_t pl;
line *l; line *l;
char flag;
Py_ssize_t consumed; Py_ssize_t consumed;
PyObject *ret = NULL, *path = NULL, *hash = NULL, *flags = NULL; PyObject *ret = NULL, *path = NULL, *hash = NULL, *flags = NULL;
l = lmiter_nextline((lmIter *)o); l = lmiter_nextline((lmIter *)o);
if (!l) { if (!l) {
goto done; goto done;
} }
pl = pathlen(l); pl = pathlen(l);
path = PyBytes_FromStringAndSize(l->start, pl); path = PyBytes_FromStringAndSize(l->start, pl);
hash = nodeof(l); hash = nodeof(l, &flag);
if (!path || !hash) { if (!path || !hash) {
goto done; goto done;
} }
consumed = pl + 41; flags = PyBytes_FromStringAndSize(&flag, flag ? 1 : 0);
flags = PyBytes_FromStringAndSize(l->start + consumed,
l->len - consumed - 1);
if (!flags) { if (!flags) {
goto done; goto done;
} }
ret = PyTuple_Pack(3, path, hash, flags); ret = PyTuple_Pack(3, path, hash, flags);
done: done:
Py_XDECREF(path); Py_XDECREF(path);
Py_XDECREF(hash); Py_XDECREF(hash);
Py_XDECREF(flags); Py_XDECREF(flags);
} }
if (PyBytes_AsStringAndSize(key, &path, &plen) == -1) { if (PyBytes_AsStringAndSize(key, &path, &plen) == -1) {
return -1; return -1;
} }
pyhash = PyTuple_GetItem(value, 0); pyhash = PyTuple_GetItem(value, 0);
if (!PyBytes_Check(pyhash)) { if (!PyBytes_Check(pyhash)) {
PyErr_Format(PyExc_TypeError, PyErr_Format(PyExc_TypeError,
"node must be a 20-byte string"); "node must be a 20 or 32 bytes string");
return -1; return -1;
} }
hlen = PyBytes_Size(pyhash); hlen = PyBytes_Size(pyhash);
/* Some parts of the codebase try and set 21 or 22 if (hlen != 20 && hlen != 32) {
* byte "hash" values in order to perturb things for
* status. We have to preserve at least the 21st
* byte. Sigh. If there's a 22nd byte, we drop it on
* the floor, which works fine.
*/
if (hlen != 20 && hlen != 21 && hlen != 22) {
PyErr_Format(PyExc_TypeError, PyErr_Format(PyExc_TypeError,
"node must be a 20-byte string"); "node must be a 20 or 32 bytes string");
return -1; return -1;
} }
hash = PyBytes_AsString(pyhash); hash = PyBytes_AsString(pyhash);
pyflags = PyTuple_GetItem(value, 1); pyflags = PyTuple_GetItem(value, 1);
if (!PyBytes_Check(pyflags) || PyBytes_Size(pyflags) > 1) { if (!PyBytes_Check(pyflags) || PyBytes_Size(pyflags) > 1) {
PyErr_Format(PyExc_TypeError, PyErr_Format(PyExc_TypeError,
"flags must a 0 or 1 byte string"); "flags must a 0 or 1 bytes string");
return -1; return -1;
} }
if (PyBytes_AsStringAndSize(pyflags, &flags, &flen) == -1) { if (PyBytes_AsStringAndSize(pyflags, &flags, &flen) == -1) {
return -1; return -1;
} }
if (flen == 1) {
switch (*flags) {
case 'l':
case 't':
case 'x':
break;
default:
PyErr_Format(PyExc_TypeError, "invalid manifest flag");
return -1;
}
}
/* one null byte and one newline */ /* one null byte and one newline */
dlen = plen + 41 + flen + 1; dlen = plen + hlen * 2 + 1 + flen + 1;
dest = malloc(dlen); dest = malloc(dlen);
if (!dest) { if (!dest) {
PyErr_NoMemory(); PyErr_NoMemory();
return -1; return -1;
} }
memcpy(dest, path, plen + 1); memcpy(dest, path, plen + 1);
for (i = 0; i < 20; i++) { for (i = 0; i < hlen; i++) {
/* Cast to unsigned, so it will not get sign-extended when promoted /* Cast to unsigned, so it will not get sign-extended when promoted
* to int (as is done when passing to a variadic function) * to int (as is done when passing to a variadic function)
*/ */
sprintf(dest + plen + 1 + (i * 2), "%02x", (unsigned char)hash[i]); sprintf(dest + plen + 1 + (i * 2), "%02x", (unsigned char)hash[i]);
} }
memcpy(dest + plen + 41, flags, flen); memcpy(dest + plen + 2 * hlen + 1, flags, flen);
dest[plen + 41 + flen] = '\n'; dest[plen + 2 * hlen + 1 + flen] = '\n';
new.start = dest; new.start = dest;
new.len = dlen; new.len = dlen;
new.hash_suffix = '\0'; new.hash_suffix = '\0';
if (hlen > 20) { if (hlen > 20) {
new.hash_suffix = hash[20]; new.hash_suffix = hash[20];
} }
new.from_malloc = true; /* is `start` a pointer we allocated? */ new.from_malloc = true; /* is `start` a pointer we allocated? */
new.deleted = false; /* is this entry deleted? */ new.deleted = false; /* is this entry deleted? */

mercurial/manifest.py

try: try:
data, pos = self.lm._get(self.pos) data, pos = self.lm._get(self.pos)
except IndexError: except IndexError:
raise StopIteration raise StopIteration
if pos == -1: if pos == -1:
self.pos += 1 self.pos += 1
return data return data
zeropos = data.find(b'\x00', pos) zeropos = data.find(b'\x00', pos)
hashval = unhexlify(data, self.lm.extrainfo[self.pos], zeropos + 1, 40) nlpos = data.find(b'\n', pos)
flags = self.lm._getflags(data, self.pos, zeropos) if zeropos == -1 or nlpos == -1 or nlpos < zeropos:
raise error.StorageError(b'Invalid manifest line')
flags = data[nlpos - 1 : nlpos]
if flags in _manifestflags:
hlen = nlpos - zeropos - 2
else:
hlen = nlpos - zeropos - 1
flags = b''
if hlen not in (40, 64):
raise error.StorageError(b'Invalid manifest line')
hashval = unhexlify(
data, self.lm.extrainfo[self.pos], zeropos + 1, hlen
)
self.pos += 1 self.pos += 1
return (data[pos:zeropos], hashval, flags) return (data[pos:zeropos], hashval, flags)
__next__ = next __next__ = next
def unhexlify(data, extra, pos, length): def unhexlify(data, extra, pos, length):
s = bin(data[pos : pos + length]) s = bin(data[pos : pos + length])
if extra: if extra:
s += chr(extra & 0xFF) s += chr(extra & 0xFF)
return s return s
def _cmp(a, b): def _cmp(a, b):
return (a > b) - (a < b) return (a > b) - (a < b)
_manifestflags = {b'', b'l', b't', b'x'}
class _lazymanifest(object): class _lazymanifest(object):
"""A pure python manifest backed by a byte string. It is supplimented with """A pure python manifest backed by a byte string. It is supplimented with
internal lists as it is modified, until it is compacted back to a pure byte internal lists as it is modified, until it is compacted back to a pure byte
string. string.
``data`` is the initial manifest data. ``data`` is the initial manifest data.
``positions`` is a list of offsets, one per manifest entry. Positive ``positions`` is a list of offsets, one per manifest entry. Positive
last = midpoint - 1 last = midpoint - 1
else: else:
first = midpoint + 1 first = midpoint + 1
return (first, False) return (first, False)
def __contains__(self, key): def __contains__(self, key):
return self.bsearch(key) != -1 return self.bsearch(key) != -1
def _getflags(self, data, needle, pos):
start = pos + 41
end = data.find(b"\n", start)
if end == -1:
end = len(data) - 1
if start == end:
return b''
return self.data[start:end]
def __getitem__(self, key): def __getitem__(self, key):
if not isinstance(key, bytes): if not isinstance(key, bytes):
raise TypeError(b"getitem: manifest keys must be a bytes.") raise TypeError(b"getitem: manifest keys must be a bytes.")
needle = self.bsearch(key) needle = self.bsearch(key)
if needle == -1: if needle == -1:
raise KeyError raise KeyError
data, pos = self._get(needle) data, pos = self._get(needle)
if pos == -1: if pos == -1:
return (data[1], data[2]) return (data[1], data[2])
zeropos = data.find(b'\x00', pos) zeropos = data.find(b'\x00', pos)
nlpos = data.find(b'\n', zeropos) nlpos = data.find(b'\n', zeropos)
assert 0 <= needle <= len(self.positions) assert 0 <= needle <= len(self.positions)
assert len(self.extrainfo) == len(self.positions) assert len(self.extrainfo) == len(self.positions)
if zeropos == -1 or nlpos == -1 or nlpos < zeropos:
raise error.StorageError(b'Invalid manifest line')
hlen = nlpos - zeropos - 1 hlen = nlpos - zeropos - 1
# Hashes sometimes have an extra byte tucked on the end, so flags = data[nlpos - 1 : nlpos]
# detect that. if flags in _manifestflags:
if hlen % 2:
hlen -= 1 hlen -= 1
else:
flags = b''
if hlen not in (40, 64):
raise error.StorageError(b'Invalid manifest line')
hashval = unhexlify(data, self.extrainfo[needle], zeropos + 1, hlen) hashval = unhexlify(data, self.extrainfo[needle], zeropos + 1, hlen)
flags = self._getflags(data, needle, zeropos)
return (hashval, flags) return (hashval, flags)
def __delitem__(self, key): def __delitem__(self, key):
needle, found = self.bsearch2(key) needle, found = self.bsearch2(key)
if not found: if not found:
raise KeyError raise KeyError
cur = self.positions[needle] cur = self.positions[needle]
self.positions = self.positions[:needle] + self.positions[needle + 1 :] self.positions = self.positions[:needle] + self.positions[needle + 1 :]
offset += len(l[-1]) offset += len(l[-1])
i += 1 i += 1
self.data = b''.join(l) self.data = b''.join(l)
self.hasremovals = False self.hasremovals = False
self.extradata = [] self.extradata = []
def _pack(self, d): def _pack(self, d):
n = d[1] n = d[1]
if len(n) == 21 or len(n) == 33: assert len(n) in (20, 32)
n = n[:-1]
assert len(n) == 20 or len(n) == 32
return d[0] + b'\x00' + hex(n) + d[2] + b'\n' return d[0] + b'\x00' + hex(n) + d[2] + b'\n'
def text(self): def text(self):
self._compact() self._compact()
return self.data return self.data
def diff(self, m2, clean=False): def diff(self, m2, clean=False):
'''Finds changes between the current manifest and m2.''' '''Finds changes between the current manifest and m2.'''
''' '''
if match: if match:
m1 = self._matches(match) m1 = self._matches(match)
m2 = m2._matches(match) m2 = m2._matches(match)
return m1.diff(m2, clean=clean) return m1.diff(m2, clean=clean)
return self._lm.diff(m2._lm, clean) return self._lm.diff(m2._lm, clean)
def setflag(self, key, flag): def setflag(self, key, flag):
if flag not in _manifestflags:
raise TypeError(b"Invalid manifest flag set.")
self._lm[key] = self[key], flag self._lm[key] = self[key], flag
def get(self, key, default=None): def get(self, key, default=None):
try: try:
return self._lm[key][0] return self._lm[key][0]
except KeyError: except KeyError:
return default return default
dir, subpath = _splittopdir(f) dir, subpath = _splittopdir(f)
if dir: if dir:
self._loadlazy(dir) self._loadlazy(dir)
if dir not in self._dirs: if dir not in self._dirs:
self._dirs[dir] = treemanifest(self._subpath(dir)) self._dirs[dir] = treemanifest(self._subpath(dir))
self._dirs[dir].__setitem__(subpath, n) self._dirs[dir].__setitem__(subpath, n)
else: else:
# manifest nodes are either 20 bytes or 32 bytes, # manifest nodes are either 20 bytes or 32 bytes,
# depending on the hash in use. An extra byte is # depending on the hash in use. Assert this as historically
# occasionally used by hg, but won't ever be # sometimes extra bytes were added.
# persisted. Trim to 21 or 33 bytes as appropriate. assert len(n) in (20, 32)
trim = 21 if len(n) < 25 else 33 self._files[f] = n
self._files[f] = n[:trim] # to match manifestdict's behavior
self._dirty = True self._dirty = True
def _load(self): def _load(self):
if self._loadfunc is not _noop: if self._loadfunc is not _noop:
lf, self._loadfunc = self._loadfunc, _noop lf, self._loadfunc = self._loadfunc, _noop
lf(self) lf(self)
elif self._copyfunc is not _noop: elif self._copyfunc is not _noop:
cf, self._copyfunc = self._copyfunc, _noop cf, self._copyfunc = self._copyfunc, _noop
cf(self) cf(self)
def setflag(self, f, flags): def setflag(self, f, flags):
"""Set the flags (symlink, executable) for path f.""" """Set the flags (symlink, executable) for path f."""
if flags not in _manifestflags:
raise TypeError(b"Invalid manifest flag set.")
self._load() self._load()
dir, subpath = _splittopdir(f) dir, subpath = _splittopdir(f)
if dir: if dir:
self._loadlazy(dir) self._loadlazy(dir)
if dir not in self._dirs: if dir not in self._dirs:
self._dirs[dir] = treemanifest(self._subpath(dir)) self._dirs[dir] = treemanifest(self._subpath(dir))
self._dirs[dir].setflag(subpath, flags) self._dirs[dir].setflag(subpath, flags)
else: else:

mercurial/merge.py

) )
else: else:
actions[f] = ( actions[f] = (
mergestatemod.ACTION_CHANGED_DELETED, mergestatemod.ACTION_CHANGED_DELETED,
(f, None, f, False, pa.node()), (f, None, f, False, pa.node()),
b'prompt changed/deleted', b'prompt changed/deleted',
) )
elif n1 == addednodeid: elif n1 == addednodeid:
# This extra 'a' is added by working copy manifest to mark # This file was locally added. We should forget it instead of
# the file as locally added. We should forget it instead of
# deleting it. # deleting it.
actions[f] = ( actions[f] = (
mergestatemod.ACTION_FORGET, mergestatemod.ACTION_FORGET,
None, None,
b'remote deleted', b'remote deleted',
) )
else: else:
actions[f] = ( actions[f] = (

tests/test-manifest.py

self.assertEqual(h2, m[b'bar/baz/qux.py']) self.assertEqual(h2, m[b'bar/baz/qux.py'])
self.assertEqual(h2, m[b'beta']) self.assertEqual(h2, m[b'beta'])
self.assertEqual(b'', m.flags(b'alpha')) self.assertEqual(b'', m.flags(b'alpha'))
self.assertEqual(b'l', m.flags(b'bar/baz/qux.py')) self.assertEqual(b'l', m.flags(b'bar/baz/qux.py'))
self.assertEqual(b'', m.flags(b'beta')) self.assertEqual(b'', m.flags(b'beta'))
with self.assertRaises(KeyError): with self.assertRaises(KeyError):
m[b'foo'] m[b'foo']
def testSetGetNodeSuffix(self):
clean = self.parsemanifest(A_SHORT_MANIFEST)
m = self.parsemanifest(A_SHORT_MANIFEST)
h = m[b'foo']
f = m.flags(b'foo')
want = h + b'a'
# Merge code wants to set 21-byte fake hashes at times
m[b'foo'] = want
self.assertEqual(want, m[b'foo'])
self.assertEqual(
[(b'bar/baz/qux.py', BIN_HASH_2), (b'foo', BIN_HASH_1 + b'a')],
list(m.items()),
)
# Sometimes it even tries a 22-byte fake hash, but we can
# return 21 and it'll work out
m[b'foo'] = want + b'+'
self.assertEqual(want, m[b'foo'])
# make sure the suffix survives a copy
match = matchmod.match(util.localpath(b'/repo'), b'', [b're:foo'])
m2 = m._matches(match)
self.assertEqual(want, m2[b'foo'])
self.assertEqual(1, len(m2))
m2 = m.copy()
self.assertEqual(want, m2[b'foo'])
# suffix with iteration
self.assertEqual(
[(b'bar/baz/qux.py', BIN_HASH_2), (b'foo', want)], list(m.items())
)
# shows up in diff
self.assertEqual({b'foo': ((want, f), (h, b''))}, m.diff(clean))
self.assertEqual({b'foo': ((h, b''), (want, f))}, clean.diff(m))
def testMatchException(self): def testMatchException(self):
m = self.parsemanifest(A_SHORT_MANIFEST) m = self.parsemanifest(A_SHORT_MANIFEST)
match = matchmod.match(util.localpath(b'/repo'), b'', [b're:.*']) match = matchmod.match(util.localpath(b'/repo'), b'', [b're:.*'])
def filt(path): def filt(path):
if path == b'foo': if path == b'foo':
assert False assert False
return True return True