comparison mercurial/parsers.c @ 25190:22438cfd11b5

phases: add set per phase in C phase computation

To speed up the computation of draft(), secret(), divergent(), obsolete() and
unstable() we need to have a fast way of getting the list of revisions that
are in draft(), secret() or the union of both: not public().

This patch extends the work on phase computation in C and make the phase
computation code also return a list of set for each non public phase.
Using these sets we can quickly obtain all the revisions of a given phase.
We do not return a set for the public phase as we expect it to be roughly the
size of the repo. Also, it can be computed easily by substracting the entries in the
non public phases from all the revs in the repo.

25189:1c8c33eaea0a

		phases[i] = phases[parent_1];
	if (parent_2 >= 0 && phases[parent_2] > phases[i])
		phases[i] = phases[parent_2];
}

static PyObject *compute_phases(indexObject *self, PyObject *args)
{
	PyObject *roots = Py_None;
	PyObject *phaseslist = NULL;
	PyObject *phaseroots = NULL;
	PyObject *rev = NULL;
	PyObject *p1 = NULL;
	PyObject *p2 = NULL;
	Py_ssize_t addlen = self->added ? PyList_GET_SIZE(self->added) : 0;
	Py_ssize_t len = index_length(self) - 1;
	Py_ssize_t numphase = 0;
	Py_ssize_t minrevallphases = 0;
	Py_ssize_t minrevphase = 0;
	Py_ssize_t i = 0;
	int parent_1, parent_2;
	char *phases = NULL;
	const char *data;

	if (!PyArg_ParseTuple(args, "O", &roots))
		goto release_none;
	if (roots == NULL || !PyList_Check(roots))
		goto release_none;

	if (phases == NULL)
		goto release_none;
	/* Put the phase information of all the roots in phases */
	numphase = PyList_GET_SIZE(roots)+1;
	minrevallphases = len + 1;
	for (i = 0; i < numphase-1; i++) {
		phaseroots = PyList_GET_ITEM(roots, i);
		if (!PyList_Check(phaseroots))
			goto release_phases;
		minrevphase = add_roots_get_min(self, phaseroots, i+1, phases);
		if (minrevphase == -2) /* Error from add_roots_get_min */
			goto release_phases;
		minrevallphases = MIN(minrevallphases, minrevphase);
	}
	/* Propagate the phase information from the roots to the revs */
	if (minrevallphases != -1) {
		for (i = minrevallphases; i < self->raw_length; i++) {

			rev = PyList_GET_ITEM(self->added, i);
			p1 = PyTuple_GET_ITEM(rev, 5);
			p2 = PyTuple_GET_ITEM(rev, 6);
			if (!PyInt_Check(p1) || !PyInt_Check(p2)) {
				PyErr_SetString(PyExc_TypeError, "revlog parents are invalid");
				goto release_phases;
			}
			parent_1 = (int)PyInt_AS_LONG(p1);
			parent_2 = (int)PyInt_AS_LONG(p2);
			set_phase_from_parents(phases, parent_1, parent_2, i+self->raw_length);
		}
	}
	/* Transform phase list to a python list */
	phaseslist = PyList_New(len);
	if (phaseslist == NULL)
		goto release_phases;
	for (i = 0; i < len; i++)
		PyList_SET_ITEM(phaseslist, i, PyInt_FromLong(phases[i]));

release_phases:
	free(phases);
release_none:
	return phaseslist;
}

static PyObject *index_headrevs(indexObject *self, PyObject *args)
{
	Py_ssize_t i, len, addlen;

	  "return the heads of the common ancestors of the given revs"},
	{"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
	 "clear the index caches"},
	{"get", (PyCFunction)index_m_get, METH_VARARGS,
	 "get an index entry"},
	{"computephases", (PyCFunction)compute_phases, METH_VARARGS,
		"compute phases"},
	{"headrevs", (PyCFunction)index_headrevs, METH_VARARGS,
	 "get head revisions"}, /* Can do filtering since 3.2 */
	{"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS,
	 "get filtered head revisions"}, /* Can always do filtering */
	{"insert", (PyCFunction)index_insert, METH_VARARGS,

25190:22438cfd11b5

		phases[i] = phases[parent_1];
	if (parent_2 >= 0 && phases[parent_2] > phases[i])
		phases[i] = phases[parent_2];
}

static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args)
{
	PyObject *roots = Py_None;
	PyObject *ret = NULL;
	PyObject *phaseslist = NULL;
	PyObject *phaseroots = NULL;
	PyObject *rev = NULL;
	PyObject *p1 = NULL;
	PyObject *p2 = NULL;
	PyObject *phaseset = NULL;
	PyObject *phasessetlist = NULL;
	Py_ssize_t addlen = self->added ? PyList_GET_SIZE(self->added) : 0;
	Py_ssize_t len = index_length(self) - 1;
	Py_ssize_t numphase = 0;
	Py_ssize_t minrevallphases = 0;
	Py_ssize_t minrevphase = 0;
	Py_ssize_t i = 0;
	int parent_1, parent_2;
	char *phases = NULL;
	const char *data;
	long phase;

	if (!PyArg_ParseTuple(args, "O", &roots))
		goto release_none;
	if (roots == NULL || !PyList_Check(roots))
		goto release_none;

	if (phases == NULL)
		goto release_none;
	/* Put the phase information of all the roots in phases */
	numphase = PyList_GET_SIZE(roots)+1;
	minrevallphases = len + 1;
	phasessetlist = PyList_New(numphase);
	if (phasessetlist == NULL)
		goto release_none;

	PyList_SET_ITEM(phasessetlist, 0, Py_None);
	Py_INCREF(Py_None);

	for (i = 0; i < numphase-1; i++) {
		phaseroots = PyList_GET_ITEM(roots, i);
		phaseset = PySet_New(NULL);
		if (phaseset == NULL)
			goto release_phasesetlist;
		PyList_SET_ITEM(phasessetlist, i+1, phaseset);
		if (!PyList_Check(phaseroots))
			goto release_phasesetlist;
		minrevphase = add_roots_get_min(self, phaseroots, i+1, phases);
		if (minrevphase == -2) /* Error from add_roots_get_min */
			goto release_phasesetlist;
		minrevallphases = MIN(minrevallphases, minrevphase);
	}
	/* Propagate the phase information from the roots to the revs */
	if (minrevallphases != -1) {
		for (i = minrevallphases; i < self->raw_length; i++) {

			rev = PyList_GET_ITEM(self->added, i);
			p1 = PyTuple_GET_ITEM(rev, 5);
			p2 = PyTuple_GET_ITEM(rev, 6);
			if (!PyInt_Check(p1) || !PyInt_Check(p2)) {
				PyErr_SetString(PyExc_TypeError, "revlog parents are invalid");
				goto release_phasesetlist;
			}
			parent_1 = (int)PyInt_AS_LONG(p1);
			parent_2 = (int)PyInt_AS_LONG(p2);
			set_phase_from_parents(phases, parent_1, parent_2, i+self->raw_length);
		}
	}
	/* Transform phase list to a python list */
	phaseslist = PyList_New(len);
	if (phaseslist == NULL)
		goto release_phasesetlist;
	for (i = 0; i < len; i++) {
		phase = phases[i];
		/* We only store the sets of phase for non public phase, the public phase
		 * is computed as a difference */
		if (phase != 0) {
			phaseset = PyList_GET_ITEM(phasessetlist, phase);
			PySet_Add(phaseset, PyInt_FromLong(i));
		}
		PyList_SET_ITEM(phaseslist, i, PyInt_FromLong(phase));
	}
	ret = PyList_New(2);
	if (ret == NULL)
		goto release_phaseslist;

	PyList_SET_ITEM(ret, 0, phaseslist);
	PyList_SET_ITEM(ret, 1, phasessetlist);
	/* We don't release phaseslist and phasessetlist as we return them to
	 * python */
	goto release_phases;

release_phaseslist:
	Py_XDECREF(phaseslist);
release_phasesetlist:
	Py_XDECREF(phasessetlist);
release_phases:
	free(phases);
release_none:
	return ret;
}

static PyObject *index_headrevs(indexObject *self, PyObject *args)
{
	Py_ssize_t i, len, addlen;

	  "return the heads of the common ancestors of the given revs"},
	{"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
	 "clear the index caches"},
	{"get", (PyCFunction)index_m_get, METH_VARARGS,
	 "get an index entry"},
	{"computephasesmapsets", (PyCFunction)compute_phases_map_sets,
			METH_VARARGS, "compute phases"},
	{"headrevs", (PyCFunction)index_headrevs, METH_VARARGS,
	 "get head revisions"}, /* Can do filtering since 3.2 */
	{"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS,
	 "get filtered head revisions"}, /* Can always do filtering */
	{"insert", (PyCFunction)index_insert, METH_VARARGS,