This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4022

index: don't include nullid in len()
ClosedPublic

Authored by martinvonz on Aug 1 2018, 2:47 PM.

Details

Reviewers
indygreg
Group Reviewers
hg-reviewers
Commits
rHG781b2720d2ac: index: don't include nullid in len()
Summary

I suspect the reason the nullid is in the index in the last position
is that it lets index[i] for regular revision number, even when index
was just a regular Python list. An alternative solution would have
been to reserve revision number 0 for the null revision. I don't know
why that wasn't done. Now that we have classes backing the index, we
can easily make index[-1] get the nullid without having to put it last
in the list and including it in the len().

This patch just hides the nullid -- it will still be accessible at
index[len(index)].

I realize that this will be annoying when checking out across this
commit for debugging (including bisection).

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

martinvonz created this revision.Aug 1 2018, 2:47 PM
martinvonz updated this revision to Diff 9781.Aug 2 2018, 12:40 AM
martinvonz updated this revision to Diff 9885.Aug 4 2018, 12:20 AM
yuja added a subscriber: yuja.Aug 4 2018, 2:42 AM
	if (PyInt_Check(value)) {
		long rev = PyInt_AS_LONG(value);
  • return rev >= -1 && rev < index_length(self);

+ return rev >= -1 && rev < index_length(self) - 1;

Fixed this to index_length(self) + 1. Maybe you'll want to drop + 1 by
a later patch, but excluding the tip rev is clearly wrong.

Closed by commit rHG781b2720d2ac: index: don't include nullid in len() (authored by martinvonz). · Explain WhyAug 4 2018, 2:43 AM
This revision was automatically updated to reflect the committed changes.
martinvonz added a comment.Aug 4 2018, 2:46 AM
In D4022#63500, @yuja wrote:
	if (PyInt_Check(value)) {
		long rev = PyInt_AS_LONG(value);
  • return rev >= -1 && rev < index_length(self);

+ return rev >= -1 && rev < index_length(self) - 1;

Fixed this to index_length(self) + 1. Maybe you'll want to drop + 1 by
a later patch, but excluding the tip rev is clearly wrong.

Thanks for careful review (as always). Yes, I had meant to clean up the "+1" and "-1" this patch sprinkled across the code, but thanks for the reminder because I had forgotten about that.

Revision Contents
Changeset List

Diff 9722

mercurial/cext/revlog.c

int ntlookups; /* # lookups */ int ntlookups; /* # lookups */
int ntmisses; /* # lookups that miss the cache */ int ntmisses; /* # lookups that miss the cache */
int inlined; int inlined;
} indexObject; } indexObject;
static Py_ssize_t index_length(const indexObject *self) static Py_ssize_t index_length(const indexObject *self)
{ {
if (self->added == NULL) if (self->added == NULL)
return self->length; return self->length - 1;
return self->length + PyList_GET_SIZE(self->added); return self->length + PyList_GET_SIZE(self->added) - 1;
} }
static PyObject *nullentry; static PyObject *nullentry;
static const char nullid[20]; static const char nullid[20];
static Py_ssize_t inline_scan(indexObject *self, const char **offsets); static Py_ssize_t inline_scan(indexObject *self, const char **offsets);
#if LONG_MAX == 0x7fffffffL #if LONG_MAX == 0x7fffffffL
* 32 bytes: nodeid (only 20 bytes used) * 32 bytes: nodeid (only 20 bytes used)
*/ */
static PyObject *index_get(indexObject *self, Py_ssize_t pos) static PyObject *index_get(indexObject *self, Py_ssize_t pos)
{ {
uint64_t offset_flags; uint64_t offset_flags;
int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2; int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
const char *c_node_id; const char *c_node_id;
const char *data; const char *data;
Py_ssize_t length = index_length(self); Py_ssize_t length = index_length(self) + 1;
PyObject *entry; PyObject *entry;
if (pos == -1 || pos == length - 1) { if (pos == -1 || pos == length - 1) {
Py_INCREF(nullentry); Py_INCREF(nullentry);
return nullentry; return nullentry;
} }
if (pos < 0 || pos >= length) { if (pos < 0 || pos >= length) {
return entry; return entry;
} }
/* /*
* Return the 20-byte SHA of the node corresponding to the given rev. * Return the 20-byte SHA of the node corresponding to the given rev.
*/ */
static const char *index_node(indexObject *self, Py_ssize_t pos) static const char *index_node(indexObject *self, Py_ssize_t pos)
{ {
Py_ssize_t length = index_length(self); Py_ssize_t length = index_length(self) + 1;
const char *data; const char *data;
if (pos == length - 1 || pos == INT_MAX) if (pos == length - 1 || pos == INT_MAX)
return nullid; return nullid;
if (pos >= length) if (pos >= length)
return NULL; return NULL;
if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) { if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {
PyErr_SetString(PyExc_TypeError, "8-tuple required"); PyErr_SetString(PyExc_TypeError, "8-tuple required");
return NULL; return NULL;
} }
if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1) if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)
return NULL; return NULL;
len = index_length(self); len = index_length(self) + 1;
if (self->added == NULL) { if (self->added == NULL) {
self->added = PyList_New(0); self->added = PyList_New(0);
if (self->added == NULL) if (self->added == NULL)
return NULL; return NULL;
} }
if (PyList_Append(self->added, obj) == -1) if (PyList_Append(self->added, obj) == -1)
} }
} }
static Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list, static Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list,
Py_ssize_t marker, char *phases) Py_ssize_t marker, char *phases)
{ {
PyObject *iter = NULL; PyObject *iter = NULL;
PyObject *iter_item = NULL; PyObject *iter_item = NULL;
Py_ssize_t min_idx = index_length(self) + 1; Py_ssize_t min_idx = index_length(self) + 2;
long iter_item_long; long iter_item_long;
if (PyList_GET_SIZE(list) != 0) { if (PyList_GET_SIZE(list) != 0) {
iter = PyObject_GetIter(list); iter = PyObject_GetIter(list);
if (iter == NULL) if (iter == NULL)
return -2; return -2;
while ((iter_item = PyIter_Next(iter))) { while ((iter_item = PyIter_Next(iter))) {
iter_item_long = PyInt_AS_LONG(iter_item); iter_item_long = PyInt_AS_LONG(iter_item);
PyObject *includepatharg = NULL; PyObject *includepatharg = NULL;
int includepath = 0; int includepath = 0;
/* heads and roots are lists */ /* heads and roots are lists */
PyObject *heads = NULL; PyObject *heads = NULL;
PyObject *roots = NULL; PyObject *roots = NULL;
PyObject *reachable = NULL; PyObject *reachable = NULL;
PyObject *val; PyObject *val;
Py_ssize_t len = index_length(self) - 1; Py_ssize_t len = index_length(self);
long revnum; long revnum;
Py_ssize_t k; Py_ssize_t k;
Py_ssize_t i; Py_ssize_t i;
Py_ssize_t l; Py_ssize_t l;
int r; int r;
int parents[2]; int parents[2];
/* Internal data structure: /* Internal data structure:
{ {
PyObject *roots = Py_None; PyObject *roots = Py_None;
PyObject *ret = NULL; PyObject *ret = NULL;
PyObject *phasessize = NULL; PyObject *phasessize = NULL;
PyObject *phaseroots = NULL; PyObject *phaseroots = NULL;
PyObject *phaseset = NULL; PyObject *phaseset = NULL;
PyObject *phasessetlist = NULL; PyObject *phasessetlist = NULL;
PyObject *rev = NULL; PyObject *rev = NULL;
Py_ssize_t len = index_length(self) - 1; Py_ssize_t len = index_length(self);
Py_ssize_t numphase = 0; Py_ssize_t numphase = 0;
Py_ssize_t minrevallphases = 0; Py_ssize_t minrevallphases = 0;
Py_ssize_t minrevphase = 0; Py_ssize_t minrevphase = 0;
Py_ssize_t i = 0; Py_ssize_t i = 0;
char *phases = NULL; char *phases = NULL;
long phase; long phase;
if (!PyArg_ParseTuple(args, "O", &roots)) if (!PyArg_ParseTuple(args, "O", &roots))
filter = PyObject_GetAttrString(filteredrevs, "__contains__"); filter = PyObject_GetAttrString(filteredrevs, "__contains__");
if (!filter) { if (!filter) {
PyErr_SetString(PyExc_TypeError, PyErr_SetString(PyExc_TypeError,
"filteredrevs has no attribute __contains__"); "filteredrevs has no attribute __contains__");
goto bail; goto bail;
} }
} }
len = index_length(self) - 1; len = index_length(self);
heads = PyList_New(0); heads = PyList_New(0);
if (heads == NULL) if (heads == NULL)
goto bail; goto bail;
if (len == 0) { if (len == 0) {
PyObject *nullid = PyInt_FromLong(-1); PyObject *nullid = PyInt_FromLong(-1);
if (nullid == NULL || PyList_Append(heads, nullid) == -1) { if (nullid == NULL || PyList_Append(heads, nullid) == -1) {
Py_XDECREF(nullid); Py_XDECREF(nullid);
goto bail; goto bail;
static PyObject *index_deltachain(indexObject *self, PyObject *args) static PyObject *index_deltachain(indexObject *self, PyObject *args)
{ {
int rev, generaldelta; int rev, generaldelta;
PyObject *stoparg; PyObject *stoparg;
int stoprev, iterrev, baserev = -1; int stoprev, iterrev, baserev = -1;
int stopped; int stopped;
PyObject *chain = NULL, *result = NULL; PyObject *chain = NULL, *result = NULL;
const Py_ssize_t length = index_length(self); const Py_ssize_t length = index_length(self) + 1;
if (!PyArg_ParseTuple(args, "iOi", &rev, &stoparg, &generaldelta)) { if (!PyArg_ParseTuple(args, "iOi", &rev, &stoparg, &generaldelta)) {
return NULL; return NULL;
} }
if (PyInt_Check(stoparg)) { if (PyInt_Check(stoparg)) {
stoprev = (int)PyInt_AsLong(stoparg); stoprev = (int)PyInt_AsLong(stoparg);
if (stoprev == -1 && PyErr_Occurred()) { if (stoprev == -1 && PyErr_Occurred()) {
? 4 : (int)self->raw_length / 2; ? 4 : (int)self->raw_length / 2;
self->nt = calloc(self->ntcapacity, sizeof(nodetree)); self->nt = calloc(self->ntcapacity, sizeof(nodetree));
if (self->nt == NULL) { if (self->nt == NULL) {
PyErr_NoMemory(); PyErr_NoMemory();
return -1; return -1;
} }
self->ntlength = 1; self->ntlength = 1;
self->ntrev = (int)index_length(self) - 1; self->ntrev = (int)index_length(self);
self->ntlookups = 1; self->ntlookups = 1;
self->ntmisses = 0; self->ntmisses = 0;
if (nt_insert(self, nullid, INT_MAX) == -1) if (nt_insert(self, nullid, INT_MAX) == -1)
return -1; return -1;
} }
return 0; return 0;
} }
static int index_contains(indexObject *self, PyObject *value) static int index_contains(indexObject *self, PyObject *value)
{ {
char *node; char *node;
Py_ssize_t nodelen; Py_ssize_t nodelen;
if (PyInt_Check(value)) { if (PyInt_Check(value)) {
long rev = PyInt_AS_LONG(value); long rev = PyInt_AS_LONG(value);
return rev >= -1 && rev < index_length(self); return rev >= -1 && rev < index_length(self) - 1;
} }
if (node_check(value, &node, &nodelen) == -1) if (node_check(value, &node, &nodelen) == -1)
return -1; return -1;
switch (index_find_node(self, node, nodelen)) { switch (index_find_node(self, node, nodelen)) {
case -3: case -3:
return -1; return -1;
bitmask repeat = 0; bitmask repeat = 0;
int revcount = 0; int revcount = 0;
int *revs; int *revs;
argcount = PySequence_Length(args); argcount = PySequence_Length(args);
revs = PyMem_Malloc(argcount * sizeof(*revs)); revs = PyMem_Malloc(argcount * sizeof(*revs));
if (argcount > 0 && revs == NULL) if (argcount > 0 && revs == NULL)
return PyErr_NoMemory(); return PyErr_NoMemory();
len = index_length(self) - 1; len = index_length(self);
for (i = 0; i < argcount; i++) { for (i = 0; i < argcount; i++) {
static const int capacity = 24; static const int capacity = 24;
PyObject *obj = PySequence_GetItem(args, i); PyObject *obj = PySequence_GetItem(args, i);
bitmask x; bitmask x;
long val; long val;
if (!PyInt_Check(obj)) { if (!PyInt_Check(obj)) {
/* /*
* Delete a numeric range of revs, which must be at the end of the * Delete a numeric range of revs, which must be at the end of the
* range, but exclude the sentinel nullid entry. * range, but exclude the sentinel nullid entry.
*/ */
static int index_slice_del(indexObject *self, PyObject *item) static int index_slice_del(indexObject *self, PyObject *item)
{ {
Py_ssize_t start, stop, step, slicelength; Py_ssize_t start, stop, step, slicelength;
Py_ssize_t length = index_length(self); Py_ssize_t length = index_length(self) + 1;
int ret = 0; int ret = 0;
/* Argument changed from PySliceObject* to PyObject* in Python 3. */ /* Argument changed from PySliceObject* to PyObject* in Python 3. */
#ifdef IS_PY3K #ifdef IS_PY3K
if (PySlice_GetIndicesEx(item, length, if (PySlice_GetIndicesEx(item, length,
#else #else
if (PySlice_GetIndicesEx((PySliceObject*)item, length, if (PySlice_GetIndicesEx((PySliceObject*)item, length,
#endif #endif

mercurial/pure/parsers.py

def gettype(q): def gettype(q):
return int(q & 0xFFFF) return int(q & 0xFFFF)
def offset_type(offset, type): def offset_type(offset, type):
return int(int(offset) << 16 | type) return int(int(offset) << 16 | type)
class BaseIndexObject(object): class BaseIndexObject(object):
def __len__(self): def __len__(self):
return self._lgt + len(self._extra) + 1 return self._lgt + len(self._extra)
def append(self, tup): def append(self, tup):
self._extra.append(tup) self._extra.append(tup)
def _fix_index(self, i): def _fix_index(self, i):
if not isinstance(i, int): if not isinstance(i, int):
raise TypeError("expecting int indexes") raise TypeError("expecting int indexes")
if i < 0 or i >= len(self): if i < 0 or i >= len(self) + 1:
raise IndexError raise IndexError
return i return i
def __getitem__(self, i): def __getitem__(self, i):
if i == -1 or i == len(self) - 1: if i == -1 or i == len(self):
return (0, 0, 0, -1, -1, -1, -1, nullid) return (0, 0, 0, -1, -1, -1, -1, nullid)
i = self._fix_index(i) i = self._fix_index(i)
if i >= self._lgt: if i >= self._lgt:
return self._extra[i - self._lgt] return self._extra[i - self._lgt]
index = self._calculate_index(i) index = self._calculate_index(i)
r = struct.unpack(indexformatng, self._data[index:index + indexsize]) r = struct.unpack(indexformatng, self._data[index:index + indexsize])
if i == 0: if i == 0:
e = list(r) e = list(r)

mercurial/repoview.py

"""return a filtered version of the changeset """return a filtered version of the changeset
this changelog must not be used for writing""" this changelog must not be used for writing"""
# some cache may be implemented later # some cache may be implemented later
unfi = self._unfilteredrepo unfi = self._unfilteredrepo
unfichangelog = unfi.changelog unfichangelog = unfi.changelog
# bypass call to changelog.method # bypass call to changelog.method
unfiindex = unfichangelog.index unfiindex = unfichangelog.index
unfilen = len(unfiindex) - 1 unfilen = len(unfiindex)
unfinode = unfiindex[unfilen - 1][7] unfinode = unfiindex[unfilen - 1][7]
revs = filterrevs(unfi, self.filtername, self._visibilityexceptions) revs = filterrevs(unfi, self.filtername, self._visibilityexceptions)
cl = self._clcache cl = self._clcache
newkey = (unfilen, unfinode, hash(revs), unfichangelog._delayed) newkey = (unfilen, unfinode, hash(revs), unfichangelog._delayed)
# if cl.index is not unfiindex, unfi.changelog would be # if cl.index is not unfiindex, unfi.changelog would be
# recreated, and our clcache refers to garbage object # recreated, and our clcache refers to garbage object
if (cl is not None and if (cl is not None and

mercurial/revlog.py

# 20 bytes: parent 1 nodeid # 20 bytes: parent 1 nodeid
# 20 bytes: parent 2 nodeid # 20 bytes: parent 2 nodeid
# 20 bytes: nodeid # 20 bytes: nodeid
indexformatv0 = struct.Struct(">4l20s20s20s") indexformatv0 = struct.Struct(">4l20s20s20s")
indexformatv0_pack = indexformatv0.pack indexformatv0_pack = indexformatv0.pack
indexformatv0_unpack = indexformatv0.unpack indexformatv0_unpack = indexformatv0.unpack
class revlogoldindex(list): class revlogoldindex(list):
def __len__(self):
return list.__len__(self) + 1
def __getitem__(self, i): def __getitem__(self, i):
if i == -1 or i == len(self) - 1: if i == -1 or i == len(self):
return (0, 0, 0, -1, -1, -1, -1, nullid) return (0, 0, 0, -1, -1, -1, -1, nullid)
return list.__getitem__(self, i) return list.__getitem__(self, i)
class revlogoldio(object): class revlogoldio(object):
def __init__(self): def __init__(self):
self.size = indexformatv0.size self.size = indexformatv0.size
def parseindex(self, data, inline): def parseindex(self, data, inline):
if self._inline: if self._inline:
func = self._indexfp func = self._indexfp
else: else:
func = self._datafp func = self._datafp
with func() as fp: with func() as fp:
yield fp yield fp
def tip(self): def tip(self):
return self.node(len(self.index) - 2) return self.node(len(self.index) - 1)
def __contains__(self, rev): def __contains__(self, rev):
return 0 <= rev < len(self) return 0 <= rev < len(self)
def __len__(self): def __len__(self):
return len(self.index) - 1 return len(self.index)
def __iter__(self): def __iter__(self):
return iter(xrange(len(self))) return iter(xrange(len(self)))
def revs(self, start=0, stop=None): def revs(self, start=0, stop=None):
"""iterate over all rev in this revlog (from start to stop)""" """iterate over all rev in this revlog (from start to stop)"""
step = 1 step = 1
length = len(self) length = len(self)
if stop is not None: if stop is not None:
if start > stop: if start > stop:
raise error.WdirUnsupported raise error.WdirUnsupported
raise LookupError(node, self.indexfile, _('no node')) raise LookupError(node, self.indexfile, _('no node'))
except KeyError: except KeyError:
# pure python cache lookup failed # pure python cache lookup failed
n = self._nodecache n = self._nodecache
i = self.index i = self.index
p = self._nodepos p = self._nodepos
if p is None: if p is None:
p = len(i) - 2 p = len(i) - 1
else: else:
assert p < len(i) assert p < len(i)
for r in xrange(p, -1, -1): for r in xrange(p, -1, -1):
v = i[r][7] v = i[r][7]
n[v] = r n[v] = r
if v == node: if v == node:
self._nodepos = r - 1 self._nodepos = r - 1
return r return r