1 /*

     2  parsers.c - efficient content parsing

     3 

     4  Copyright 2008 Matt Mackall <mpm@selenic.com> and others

     5 

     6  This software may be used and distributed according to the terms of

     7  the GNU General Public License, incorporated herein by reference.

     8 */

     9 

    10 #include <Python.h>

    11 #include <ctype.h>

    12 #include <stddef.h>

    13 #include <string.h>

    14 

    15 #include "util.h"

    16 #include "bitmanipulation.h"

    17 

    18 #ifdef IS_PY3K

    19 /* The mapping of Python types is meant to be temporary to get Python

    20  * 3 to compile. We should remove this once Python 3 support is fully

    21  * supported and proper types are used in the extensions themselves. */

    22 #define PyInt_Type PyLong_Type

    23 #define PyInt_Check PyLong_Check

    24 #define PyInt_FromLong PyLong_FromLong

    25 #define PyInt_FromSsize_t PyLong_FromSsize_t

    26 #define PyInt_AS_LONG PyLong_AS_LONG

    27 #define PyInt_AsLong PyLong_AsLong

    28 #endif

    29 

    30 static char *versionerrortext = "Python minor version mismatch";

    31 

    32 static int8_t hextable[256] = {

    33 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    34 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    35 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    36 	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /* 0-9 */

    37 	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* A-F */

    38 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    39 	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a-f */

    40 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    41 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    42 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    43 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    44 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    45 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    46 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    47 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    48 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1

    49 };

    50 

    51 static char lowertable[128] = {

    52 	'\x00', '\x01', '\x02', '\x03', '\x04', '\x05', '\x06', '\x07',

    53 	'\x08', '\x09', '\x0a', '\x0b', '\x0c', '\x0d', '\x0e', '\x0f',

    54 	'\x10', '\x11', '\x12', '\x13', '\x14', '\x15', '\x16', '\x17',

    55 	'\x18', '\x19', '\x1a', '\x1b', '\x1c', '\x1d', '\x1e', '\x1f',

    56 	'\x20', '\x21', '\x22', '\x23', '\x24', '\x25', '\x26', '\x27',

    57 	'\x28', '\x29', '\x2a', '\x2b', '\x2c', '\x2d', '\x2e', '\x2f',

    58 	'\x30', '\x31', '\x32', '\x33', '\x34', '\x35', '\x36', '\x37',

    59 	'\x38', '\x39', '\x3a', '\x3b', '\x3c', '\x3d', '\x3e', '\x3f',

    60 	'\x40',

    61 	        '\x61', '\x62', '\x63', '\x64', '\x65', '\x66', '\x67', /* A-G */

    62 	'\x68', '\x69', '\x6a', '\x6b', '\x6c', '\x6d', '\x6e', '\x6f', /* H-O */

    63 	'\x70', '\x71', '\x72', '\x73', '\x74', '\x75', '\x76', '\x77', /* P-W */

    64 	'\x78', '\x79', '\x7a',                                         /* X-Z */

    65 	                        '\x5b', '\x5c', '\x5d', '\x5e', '\x5f',

    66 	'\x60', '\x61', '\x62', '\x63', '\x64', '\x65', '\x66', '\x67',

    67 	'\x68', '\x69', '\x6a', '\x6b', '\x6c', '\x6d', '\x6e', '\x6f',

    68 	'\x70', '\x71', '\x72', '\x73', '\x74', '\x75', '\x76', '\x77',

    69 	'\x78', '\x79', '\x7a', '\x7b', '\x7c', '\x7d', '\x7e', '\x7f'

    70 };

    71 

    72 static char uppertable[128] = {

    73 	'\x00', '\x01', '\x02', '\x03', '\x04', '\x05', '\x06', '\x07',

    74 	'\x08', '\x09', '\x0a', '\x0b', '\x0c', '\x0d', '\x0e', '\x0f',

    75 	'\x10', '\x11', '\x12', '\x13', '\x14', '\x15', '\x16', '\x17',

    76 	'\x18', '\x19', '\x1a', '\x1b', '\x1c', '\x1d', '\x1e', '\x1f',

    77 	'\x20', '\x21', '\x22', '\x23', '\x24', '\x25', '\x26', '\x27',

    78 	'\x28', '\x29', '\x2a', '\x2b', '\x2c', '\x2d', '\x2e', '\x2f',

    79 	'\x30', '\x31', '\x32', '\x33', '\x34', '\x35', '\x36', '\x37',

    80 	'\x38', '\x39', '\x3a', '\x3b', '\x3c', '\x3d', '\x3e', '\x3f',

    81 	'\x40', '\x41', '\x42', '\x43', '\x44', '\x45', '\x46', '\x47',

    82 	'\x48', '\x49', '\x4a', '\x4b', '\x4c', '\x4d', '\x4e', '\x4f',

    83 	'\x50', '\x51', '\x52', '\x53', '\x54', '\x55', '\x56', '\x57',

    84 	'\x58', '\x59', '\x5a', '\x5b', '\x5c', '\x5d', '\x5e', '\x5f',

    85 	'\x60',

    86 		'\x41', '\x42', '\x43', '\x44', '\x45', '\x46', '\x47', /* a-g */

    87 	'\x48', '\x49', '\x4a', '\x4b', '\x4c', '\x4d', '\x4e', '\x4f', /* h-o */

    88 	'\x50', '\x51', '\x52', '\x53', '\x54', '\x55', '\x56', '\x57', /* p-w */

    89 	'\x58', '\x59', '\x5a', 					/* x-z */

    90 				'\x7b', '\x7c', '\x7d', '\x7e', '\x7f'

    91 };

    92 

    93 static inline int hexdigit(const char *p, Py_ssize_t off)

    94 {

    95 	int8_t val = hextable[(unsigned char)p[off]];

    96 

    97 	if (val >= 0) {

    98 		return val;

    99 	}

   100 

   101 	PyErr_SetString(PyExc_ValueError, "input contains non-hex character");

   102 	return 0;

   103 }

   104 

   105 /*

   106  * Turn a hex-encoded string into binary.

   107  */

   108 PyObject *unhexlify(const char *str, int len)

   109 {

   110 	PyObject *ret;

   111 	char *d;

   112 	int i;

   113 

   114 	ret = PyBytes_FromStringAndSize(NULL, len / 2);

   115 

   116 	if (!ret)

   117 		return NULL;

   118 

   119 	d = PyBytes_AsString(ret);

   120 

   121 	for (i = 0; i < len;) {

   122 		int hi = hexdigit(str, i++);

   123 		int lo = hexdigit(str, i++);

   124 		*d++ = (hi << 4) | lo;

   125 	}

   126 

   127 	return ret;

   128 }

   129 

   130 static inline PyObject *_asciitransform(PyObject *str_obj,

   131 					const char table[128],

   132 					PyObject *fallback_fn)

   133 {

   134 	char *str, *newstr;

   135 	Py_ssize_t i, len;

   136 	PyObject *newobj = NULL;

   137 	PyObject *ret = NULL;

   138 

   139 	str = PyBytes_AS_STRING(str_obj);

   140 	len = PyBytes_GET_SIZE(str_obj);

   141 

   142 	newobj = PyBytes_FromStringAndSize(NULL, len);

   143 	if (!newobj)

   144 		goto quit;

   145 

   146 	newstr = PyBytes_AS_STRING(newobj);

   147 

   148 	for (i = 0; i < len; i++) {

   149 		char c = str[i];

   150 		if (c & 0x80) {

   151 			if (fallback_fn != NULL) {

   152 				ret = PyObject_CallFunctionObjArgs(fallback_fn,

   153 					str_obj, NULL);

   154 			} else {

   155 				PyObject *err = PyUnicodeDecodeError_Create(

   156 					"ascii", str, len, i, (i + 1),

   157 					"unexpected code byte");

   158 				PyErr_SetObject(PyExc_UnicodeDecodeError, err);

   159 				Py_XDECREF(err);

   160 			}

   161 			goto quit;

   162 		}

   163 		newstr[i] = table[(unsigned char)c];

   164 	}

   165 

   166 	ret = newobj;

   167 	Py_INCREF(ret);

   168 quit:

   169 	Py_XDECREF(newobj);

   170 	return ret;

   171 }

   172 

   173 static PyObject *asciilower(PyObject *self, PyObject *args)

   174 {

   175 	PyObject *str_obj;

   176 	if (!PyArg_ParseTuple(args, "O!:asciilower", &PyBytes_Type, &str_obj))

   177 		return NULL;

   178 	return _asciitransform(str_obj, lowertable, NULL);

   179 }

   180 

   181 static PyObject *asciiupper(PyObject *self, PyObject *args)

   182 {

   183 	PyObject *str_obj;

   184 	if (!PyArg_ParseTuple(args, "O!:asciiupper", &PyBytes_Type, &str_obj))

   185 		return NULL;

   186 	return _asciitransform(str_obj, uppertable, NULL);

   187 }

   188 

   189 static inline PyObject *_dict_new_presized(Py_ssize_t expected_size)

   190 {

   191 	/* _PyDict_NewPresized expects a minused parameter, but it actually

   192 	   creates a dictionary that's the nearest power of two bigger than the

   193 	   parameter. For example, with the initial minused = 1000, the

   194 	   dictionary created has size 1024. Of course in a lot of cases that

   195 	   can be greater than the maximum load factor Python's dict object

   196 	   expects (= 2/3), so as soon as we cross the threshold we'll resize

   197 	   anyway. So create a dictionary that's at least 3/2 the size. */

   198 	return _PyDict_NewPresized(((1 + expected_size) / 2) * 3);

   199 }

   200 

   201 static PyObject *dict_new_presized(PyObject *self, PyObject *args)

   202 {

   203 	Py_ssize_t expected_size;

   204 

   205 	if (!PyArg_ParseTuple(args, "n:make_presized_dict", &expected_size))

   206 		return NULL;

   207 

   208 	return _dict_new_presized(expected_size);

   209 }

   210 

   211 static PyObject *make_file_foldmap(PyObject *self, PyObject *args)

   212 {

   213 	PyObject *dmap, *spec_obj, *normcase_fallback;

   214 	PyObject *file_foldmap = NULL;

   215 	enum normcase_spec spec;

   216 	PyObject *k, *v;

   217 	dirstateTupleObject *tuple;

   218 	Py_ssize_t pos = 0;

   219 	const char *table;

   220 

   221 	if (!PyArg_ParseTuple(args, "O!O!O!:make_file_foldmap",

   222 			      &PyDict_Type, &dmap,

   223 			      &PyInt_Type, &spec_obj,

   224 			      &PyFunction_Type, &normcase_fallback))

   225 		goto quit;

   226 

   227 	spec = (int)PyInt_AS_LONG(spec_obj);

   228 	switch (spec) {

   229 	case NORMCASE_LOWER:

   230 		table = lowertable;

   231 		break;

   232 	case NORMCASE_UPPER:

   233 		table = uppertable;

   234 		break;

   235 	case NORMCASE_OTHER:

   236 		table = NULL;

   237 		break;

   238 	default:

   239 		PyErr_SetString(PyExc_TypeError, "invalid normcasespec");

   240 		goto quit;

   241 	}

   242 

   243 	/* Add some more entries to deal with additions outside this

   244 	   function. */

   245 	file_foldmap = _dict_new_presized((PyDict_Size(dmap) / 10) * 11);

   246 	if (file_foldmap == NULL)

   247 		goto quit;

   248 

   249 	while (PyDict_Next(dmap, &pos, &k, &v)) {

   250 		if (!dirstate_tuple_check(v)) {

   251 			PyErr_SetString(PyExc_TypeError,

   252 					"expected a dirstate tuple");

   253 			goto quit;

   254 		}

   255 

   256 		tuple = (dirstateTupleObject *)v;

   257 		if (tuple->state != 'r') {

   258 			PyObject *normed;

   259 			if (table != NULL) {

   260 				normed = _asciitransform(k, table,

   261 					normcase_fallback);

   262 			} else {

   263 				normed = PyObject_CallFunctionObjArgs(

   264 					normcase_fallback, k, NULL);

   265 			}

   266 

   267 			if (normed == NULL)

   268 				goto quit;

   269 			if (PyDict_SetItem(file_foldmap, normed, k) == -1) {

   270 				Py_DECREF(normed);

   271 				goto quit;

   272 			}

   273 			Py_DECREF(normed);

   274 		}

   275 	}

   276 	return file_foldmap;

   277 quit:

   278 	Py_XDECREF(file_foldmap);

   279 	return NULL;

   280 }

   281 

   282 /*

   283  * This code assumes that a manifest is stitched together with newline

   284  * ('\n') characters.

   285  */

   286 static PyObject *parse_manifest(PyObject *self, PyObject *args)

   287 {

   288 	PyObject *mfdict, *fdict;

   289 	char *str, *start, *end;

   290 	int len;

   291 

   292 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",

   293 			      &PyDict_Type, &mfdict,

   294 			      &PyDict_Type, &fdict,

   295 			      &str, &len))

   296 		goto quit;

   297 

   298 	start = str;

   299 	end = str + len;

   300 	while (start < end) {

   301 		PyObject *file = NULL, *node = NULL;

   302 		PyObject *flags = NULL;

   303 		char *zero = NULL, *newline = NULL;

   304 		ptrdiff_t nlen;

   305 

   306 		zero = memchr(start, '\0', end - start);

   307 		if (!zero) {

   308 			PyErr_SetString(PyExc_ValueError,

   309 					"manifest entry has no separator");

   310 			goto quit;

   311 		}

   312 

   313 		newline = memchr(zero + 1, '\n', end - (zero + 1));

   314 		if (!newline) {

   315 			PyErr_SetString(PyExc_ValueError,

   316 					"manifest contains trailing garbage");

   317 			goto quit;

   318 		}

   319 

   320 		file = PyBytes_FromStringAndSize(start, zero - start);

   321 

   322 		if (!file)

   323 			goto bail;

   324 

   325 		nlen = newline - zero - 1;

   326 

   327 		node = unhexlify(zero + 1, nlen > 40 ? 40 : (int)nlen);

   328 		if (!node)

   329 			goto bail;

   330 

   331 		if (nlen > 40) {

   332 			flags = PyBytes_FromStringAndSize(zero + 41,

   333 							   nlen - 40);

   334 			if (!flags)

   335 				goto bail;

   336 

   337 			if (PyDict_SetItem(fdict, file, flags) == -1)

   338 				goto bail;

   339 		}

   340 

   341 		if (PyDict_SetItem(mfdict, file, node) == -1)

   342 			goto bail;

   343 

   344 		start = newline + 1;

   345 

   346 		Py_XDECREF(flags);

   347 		Py_XDECREF(node);

   348 		Py_XDECREF(file);

   349 		continue;

   350 	bail:

   351 		Py_XDECREF(flags);

   352 		Py_XDECREF(node);

   353 		Py_XDECREF(file);

   354 		goto quit;

   355 	}

   356 

   357 	Py_INCREF(Py_None);

   358 	return Py_None;

   359 quit:

   360 	return NULL;

   361 }

   362 

   363 static inline dirstateTupleObject *make_dirstate_tuple(char state, int mode,

   364 						       int size, int mtime)

   365 {

   366 	dirstateTupleObject *t = PyObject_New(dirstateTupleObject,

   367 					      &dirstateTupleType);

   368 	if (!t)

   369 		return NULL;

   370 	t->state = state;

   371 	t->mode = mode;

   372 	t->size = size;

   373 	t->mtime = mtime;

   374 	return t;

   375 }

   376 

   377 static PyObject *dirstate_tuple_new(PyTypeObject *subtype, PyObject *args,

   378 				    PyObject *kwds)

   379 {

   380 	/* We do all the initialization here and not a tp_init function because

   381 	 * dirstate_tuple is immutable. */

   382 	dirstateTupleObject *t;

   383 	char state;

   384 	int size, mode, mtime;

   385 	if (!PyArg_ParseTuple(args, "ciii", &state, &mode, &size, &mtime))

   386 		return NULL;

   387 

   388 	t = (dirstateTupleObject *)subtype->tp_alloc(subtype, 1);

   389 	if (!t)

   390 		return NULL;

   391 	t->state = state;

   392 	t->mode = mode;

   393 	t->size = size;

   394 	t->mtime = mtime;

   395 

   396 	return (PyObject *)t;

   397 }

   398 

   399 static void dirstate_tuple_dealloc(PyObject *o)

   400 {

   401 	PyObject_Del(o);

   402 }

   403 

   404 static Py_ssize_t dirstate_tuple_length(PyObject *o)

   405 {

   406 	return 4;

   407 }

   408 

   409 static PyObject *dirstate_tuple_item(PyObject *o, Py_ssize_t i)

   410 {

   411 	dirstateTupleObject *t = (dirstateTupleObject *)o;

   412 	switch (i) {

   413 	case 0:

   414 		return PyBytes_FromStringAndSize(&t->state, 1);

   415 	case 1:

   416 		return PyInt_FromLong(t->mode);

   417 	case 2:

   418 		return PyInt_FromLong(t->size);

   419 	case 3:

   420 		return PyInt_FromLong(t->mtime);

   421 	default:

   422 		PyErr_SetString(PyExc_IndexError, "index out of range");

   423 		return NULL;

   424 	}

   425 }

   426 

   427 static PySequenceMethods dirstate_tuple_sq = {

   428 	dirstate_tuple_length,     /* sq_length */

   429 	0,                         /* sq_concat */

   430 	0,                         /* sq_repeat */

   431 	dirstate_tuple_item,       /* sq_item */

   432 	0,                         /* sq_ass_item */

   433 	0,                         /* sq_contains */

   434 	0,                         /* sq_inplace_concat */

   435 	0                          /* sq_inplace_repeat */

   436 };

   437 

   438 PyTypeObject dirstateTupleType = {

   439 	PyVarObject_HEAD_INIT(NULL, 0)

   440 	"dirstate_tuple",          /* tp_name */

   441 	sizeof(dirstateTupleObject),/* tp_basicsize */

   442 	0,                         /* tp_itemsize */

   443 	(destructor)dirstate_tuple_dealloc, /* tp_dealloc */

   444 	0,                         /* tp_print */

   445 	0,                         /* tp_getattr */

   446 	0,                         /* tp_setattr */

   447 	0,                         /* tp_compare */

   448 	0,                         /* tp_repr */

   449 	0,                         /* tp_as_number */

   450 	&dirstate_tuple_sq,        /* tp_as_sequence */

   451 	0,                         /* tp_as_mapping */

   452 	0,                         /* tp_hash  */

   453 	0,                         /* tp_call */

   454 	0,                         /* tp_str */

   455 	0,                         /* tp_getattro */

   456 	0,                         /* tp_setattro */

   457 	0,                         /* tp_as_buffer */

   458 	Py_TPFLAGS_DEFAULT,        /* tp_flags */

   459 	"dirstate tuple",          /* tp_doc */

   460 	0,                         /* tp_traverse */

   461 	0,                         /* tp_clear */

   462 	0,                         /* tp_richcompare */

   463 	0,                         /* tp_weaklistoffset */

   464 	0,                         /* tp_iter */

   465 	0,                         /* tp_iternext */

   466 	0,                         /* tp_methods */

   467 	0,                         /* tp_members */

   468 	0,                         /* tp_getset */

   469 	0,                         /* tp_base */

   470 	0,                         /* tp_dict */

   471 	0,                         /* tp_descr_get */

   472 	0,                         /* tp_descr_set */

   473 	0,                         /* tp_dictoffset */

   474 	0,                         /* tp_init */

   475 	0,                         /* tp_alloc */

   476 	dirstate_tuple_new,        /* tp_new */

   477 };

   478 

   479 static PyObject *parse_dirstate(PyObject *self, PyObject *args)

   480 {

   481 	PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;

   482 	PyObject *fname = NULL, *cname = NULL, *entry = NULL;

   483 	char state, *cur, *str, *cpos;

   484 	int mode, size, mtime;

   485 	unsigned int flen, len, pos = 40;

   486 	int readlen;

   487 

   488 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",

   489 			      &PyDict_Type, &dmap,

   490 			      &PyDict_Type, &cmap,

   491 			      &str, &readlen))

   492 		goto quit;

   493 

   494 	len = readlen;

   495 

   496 	/* read parents */

   497 	if (len < 40) {

   498 		PyErr_SetString(

   499 			PyExc_ValueError, "too little data for parents");

   500 		goto quit;

   501 	}

   502 

   503 	parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);

   504 	if (!parents)

   505 		goto quit;

   506 

   507 	/* read filenames */

   508 	while (pos >= 40 && pos < len) {

   509 		if (pos + 17 > len) {

   510 			PyErr_SetString(PyExc_ValueError,

   511 					"overflow in dirstate");

   512 			goto quit;

   513 		}

   514 		cur = str + pos;

   515 		/* unpack header */

   516 		state = *cur;

   517 		mode = getbe32(cur + 1);

   518 		size = getbe32(cur + 5);

   519 		mtime = getbe32(cur + 9);

   520 		flen = getbe32(cur + 13);

   521 		pos += 17;

   522 		cur += 17;

   523 		if (flen > len - pos) {

   524 			PyErr_SetString(PyExc_ValueError, "overflow in dirstate");

   525 			goto quit;

   526 		}

   527 

   528 		entry = (PyObject *)make_dirstate_tuple(state, mode, size,

   529 							mtime);

   530 		cpos = memchr(cur, 0, flen);

   531 		if (cpos) {

   532 			fname = PyBytes_FromStringAndSize(cur, cpos - cur);

   533 			cname = PyBytes_FromStringAndSize(cpos + 1,

   534 							   flen - (cpos - cur) - 1);

   535 			if (!fname || !cname ||

   536 			    PyDict_SetItem(cmap, fname, cname) == -1 ||

   537 			    PyDict_SetItem(dmap, fname, entry) == -1)

   538 				goto quit;

   539 			Py_DECREF(cname);

   540 		} else {

   541 			fname = PyBytes_FromStringAndSize(cur, flen);

   542 			if (!fname ||

   543 			    PyDict_SetItem(dmap, fname, entry) == -1)

   544 				goto quit;

   545 		}

   546 		Py_DECREF(fname);

   547 		Py_DECREF(entry);

   548 		fname = cname = entry = NULL;

   549 		pos += flen;

   550 	}

   551 

   552 	ret = parents;

   553 	Py_INCREF(ret);

   554 quit:

   555 	Py_XDECREF(fname);

   556 	Py_XDECREF(cname);

   557 	Py_XDECREF(entry);

   558 	Py_XDECREF(parents);

   559 	return ret;

   560 }

   561 

   562 /*

   563  * Build a set of non-normal and other parent entries from the dirstate dmap

   564 */

   565 static PyObject *nonnormalotherparententries(PyObject *self, PyObject *args) {

   566 	PyObject *dmap, *fname, *v;

   567 	PyObject *nonnset = NULL, *otherpset = NULL, *result = NULL;

   568 	Py_ssize_t pos;

   569 

   570 	if (!PyArg_ParseTuple(args, "O!:nonnormalentries",

   571 			      &PyDict_Type, &dmap))

   572 		goto bail;

   573 

   574 	nonnset = PySet_New(NULL);

   575 	if (nonnset == NULL)

   576 		goto bail;

   577 

   578 	otherpset = PySet_New(NULL);

   579 	if (otherpset == NULL)

   580 		goto bail;

   581 

   582 	pos = 0;

   583 	while (PyDict_Next(dmap, &pos, &fname, &v)) {

   584 		dirstateTupleObject *t;

   585 		if (!dirstate_tuple_check(v)) {

   586 			PyErr_SetString(PyExc_TypeError,

   587 					"expected a dirstate tuple");

   588 			goto bail;

   589 		}

   590 		t = (dirstateTupleObject *)v;

   591 

   592 		if (t->state == 'n' && t->size == -2) {

   593 			if (PySet_Add(otherpset, fname) == -1) {

   594 				goto bail;

   595 			}

   596 		}

   597 

   598 		if (t->state == 'n' && t->mtime != -1)

   599 			continue;

   600 		if (PySet_Add(nonnset, fname) == -1)

   601 			goto bail;

   602 	}

   603 

   604 	result = Py_BuildValue("(OO)", nonnset, otherpset);

   605 	if (result == NULL)

   606 		goto bail;

   607 	Py_DECREF(nonnset);

   608 	Py_DECREF(otherpset);

   609 	return result;

   610 bail:

   611 	Py_XDECREF(nonnset);

   612 	Py_XDECREF(otherpset);

   613 	Py_XDECREF(result);

   614 	return NULL;

   615 }

   616 

   617 /*

   618  * Efficiently pack a dirstate object into its on-disk format.

   619  */

   620 static PyObject *pack_dirstate(PyObject *self, PyObject *args)

   621 {

   622 	PyObject *packobj = NULL;

   623 	PyObject *map, *copymap, *pl, *mtime_unset = NULL;

   624 	Py_ssize_t nbytes, pos, l;

   625 	PyObject *k, *v = NULL, *pn;

   626 	char *p, *s;

   627 	int now;

   628 

   629 	if (!PyArg_ParseTuple(args, "O!O!Oi:pack_dirstate",

   630 			      &PyDict_Type, &map, &PyDict_Type, &copymap,

   631 			      &pl, &now))

   632 		return NULL;

   633 

   634 	if (!PySequence_Check(pl) || PySequence_Size(pl) != 2) {

   635 		PyErr_SetString(PyExc_TypeError, "expected 2-element sequence");

   636 		return NULL;

   637 	}

   638 

   639 	/* Figure out how much we need to allocate. */

   640 	for (nbytes = 40, pos = 0; PyDict_Next(map, &pos, &k, &v);) {

   641 		PyObject *c;

   642 		if (!PyBytes_Check(k)) {

   643 			PyErr_SetString(PyExc_TypeError, "expected string key");

   644 			goto bail;

   645 		}

   646 		nbytes += PyBytes_GET_SIZE(k) + 17;

   647 		c = PyDict_GetItem(copymap, k);

   648 		if (c) {

   649 			if (!PyBytes_Check(c)) {

   650 				PyErr_SetString(PyExc_TypeError,

   651 						"expected string key");

   652 				goto bail;

   653 			}

   654 			nbytes += PyBytes_GET_SIZE(c) + 1;

   655 		}

   656 	}

   657 

   658 	packobj = PyBytes_FromStringAndSize(NULL, nbytes);

   659 	if (packobj == NULL)

   660 		goto bail;

   661 

   662 	p = PyBytes_AS_STRING(packobj);

   663 

   664 	pn = PySequence_ITEM(pl, 0);

   665 	if (PyBytes_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {

   666 		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");

   667 		goto bail;

   668 	}

   669 	memcpy(p, s, l);

   670 	p += 20;

   671 	pn = PySequence_ITEM(pl, 1);

   672 	if (PyBytes_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {

   673 		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");

   674 		goto bail;

   675 	}

   676 	memcpy(p, s, l);

   677 	p += 20;

   678 

   679 	for (pos = 0; PyDict_Next(map, &pos, &k, &v); ) {

   680 		dirstateTupleObject *tuple;

   681 		char state;

   682 		int mode, size, mtime;

   683 		Py_ssize_t len, l;

   684 		PyObject *o;

   685 		char *t;

   686 

   687 		if (!dirstate_tuple_check(v)) {

   688 			PyErr_SetString(PyExc_TypeError,

   689 					"expected a dirstate tuple");

   690 			goto bail;

   691 		}

   692 		tuple = (dirstateTupleObject *)v;

   693 

   694 		state = tuple->state;

   695 		mode = tuple->mode;

   696 		size = tuple->size;

   697 		mtime = tuple->mtime;

   698 		if (state == 'n' && mtime == now) {

   699 			/* See pure/parsers.py:pack_dirstate for why we do

   700 			 * this. */

   701 			mtime = -1;

   702 			mtime_unset = (PyObject *)make_dirstate_tuple(

   703 				state, mode, size, mtime);

   704 			if (!mtime_unset)

   705 				goto bail;

   706 			if (PyDict_SetItem(map, k, mtime_unset) == -1)

   707 				goto bail;

   708 			Py_DECREF(mtime_unset);

   709 			mtime_unset = NULL;

   710 		}

   711 		*p++ = state;

   712 		putbe32((uint32_t)mode, p);

   713 		putbe32((uint32_t)size, p + 4);

   714 		putbe32((uint32_t)mtime, p + 8);

   715 		t = p + 12;

   716 		p += 16;

   717 		len = PyBytes_GET_SIZE(k);

   718 		memcpy(p, PyBytes_AS_STRING(k), len);

   719 		p += len;

   720 		o = PyDict_GetItem(copymap, k);

   721 		if (o) {

   722 			*p++ = '\0';

   723 			l = PyBytes_GET_SIZE(o);

   724 			memcpy(p, PyBytes_AS_STRING(o), l);

   725 			p += l;

   726 			len += l + 1;

   727 		}

   728 		putbe32((uint32_t)len, t);

   729 	}

   730 

   731 	pos = p - PyBytes_AS_STRING(packobj);

   732 	if (pos != nbytes) {

   733 		PyErr_Format(PyExc_SystemError, "bad dirstate size: %ld != %ld",

   734                              (long)pos, (long)nbytes);

   735 		goto bail;

   736 	}

   737 

   738 	return packobj;

   739 bail:

   740 	Py_XDECREF(mtime_unset);

   741 	Py_XDECREF(packobj);

   742 	Py_XDECREF(v);

   743 	return NULL;

   744 }

   745 

   746 /*

   747  * A base-16 trie for fast node->rev mapping.

   748  *

   749  * Positive value is index of the next node in the trie

   750  * Negative value is a leaf: -(rev + 1)

   751  * Zero is empty

   752  */

   753 typedef struct {

   754 	int children[16];

   755 } nodetree;

   756 

   757 /*

   758  * This class has two behaviors.

   759  *

   760  * When used in a list-like way (with integer keys), we decode an

   761  * entry in a RevlogNG index file on demand. Our last entry is a

   762  * sentinel, always a nullid.  We have limited support for

   763  * integer-keyed insert and delete, only at elements right before the

   764  * sentinel.

   765  *

   766  * With string keys, we lazily perform a reverse mapping from node to

   767  * rev, using a base-16 trie.

   768  */

   769 typedef struct {

   770 	PyObject_HEAD

   771 	/* Type-specific fields go here. */

   772 	PyObject *data;        /* raw bytes of index */

   773 	Py_buffer buf;         /* buffer of data */

   774 	PyObject **cache;      /* cached tuples */

   775 	const char **offsets;  /* populated on demand */

   776 	Py_ssize_t raw_length; /* original number of elements */

   777 	Py_ssize_t length;     /* current number of elements */

   778 	PyObject *added;       /* populated on demand */

   779 	PyObject *headrevs;    /* cache, invalidated on changes */

   780 	PyObject *filteredrevs;/* filtered revs set */

   781 	nodetree *nt;          /* base-16 trie */

   782 	unsigned ntlength;          /* # nodes in use */

   783 	unsigned ntcapacity;        /* # nodes allocated */

   784 	int ntdepth;           /* maximum depth of tree */

   785 	int ntsplits;          /* # splits performed */

   786 	int ntrev;             /* last rev scanned */

   787 	int ntlookups;         /* # lookups */

   788 	int ntmisses;          /* # lookups that miss the cache */

   789 	int inlined;

   790 } indexObject;

   791 

   792 static Py_ssize_t index_length(const indexObject *self)

   793 {

   794 	if (self->added == NULL)

   795 		return self->length;

   796 	return self->length + PyList_GET_SIZE(self->added);

   797 }

   798 

   799 static PyObject *nullentry;

   800 static const char nullid[20];

   801 

   802 static Py_ssize_t inline_scan(indexObject *self, const char **offsets);

   803 

   804 #if LONG_MAX == 0x7fffffffL

   805 static char *tuple_format = "Kiiiiiis#";

   806 #else

   807 static char *tuple_format = "kiiiiiis#";

   808 #endif

   809 

   810 /* A RevlogNG v1 index entry is 64 bytes long. */

   811 static const long v1_hdrsize = 64;

   812 

   813 /*

   814  * Return a pointer to the beginning of a RevlogNG record.

   815  */

   816 static const char *index_deref(indexObject *self, Py_ssize_t pos)

   817 {

   818 	if (self->inlined && pos > 0) {

   819 		if (self->offsets == NULL) {

   820 			self->offsets = PyMem_Malloc(self->raw_length *

   821 					             sizeof(*self->offsets));

   822 			if (self->offsets == NULL)

   823 				return (const char *)PyErr_NoMemory();

   824 			inline_scan(self, self->offsets);

   825 		}

   826 		return self->offsets[pos];

   827 	}

   828 

   829 	return (const char *)(self->buf.buf) + pos * v1_hdrsize;

   830 }

   831 

   832 static inline int index_get_parents(indexObject *self, Py_ssize_t rev,

   833 				    int *ps, int maxrev)

   834 {

   835 	if (rev >= self->length - 1) {

   836 		PyObject *tuple = PyList_GET_ITEM(self->added,

   837 						  rev - self->length + 1);

   838 		ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5));

   839 		ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6));

   840 	} else {

   841 		const char *data = index_deref(self, rev);

   842 		ps[0] = getbe32(data + 24);

   843 		ps[1] = getbe32(data + 28);

   844 	}

   845 	/* If index file is corrupted, ps[] may point to invalid revisions. So

   846 	 * there is a risk of buffer overflow to trust them unconditionally. */

   847 	if (ps[0] > maxrev || ps[1] > maxrev) {

   848 		PyErr_SetString(PyExc_ValueError, "parent out of range");

   849 		return -1;

   850 	}

   851 	return 0;

   852 }

   853 

   854 

   855 /*

   856  * RevlogNG format (all in big endian, data may be inlined):

   857  *    6 bytes: offset

   858  *    2 bytes: flags

   859  *    4 bytes: compressed length

   860  *    4 bytes: uncompressed length

   861  *    4 bytes: base revision

   862  *    4 bytes: link revision

   863  *    4 bytes: parent 1 revision

   864  *    4 bytes: parent 2 revision

   865  *   32 bytes: nodeid (only 20 bytes used)

   866  */

   867 static PyObject *index_get(indexObject *self, Py_ssize_t pos)

   868 {

   869 	uint64_t offset_flags;

   870 	int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;

   871 	const char *c_node_id;

   872 	const char *data;

   873 	Py_ssize_t length = index_length(self);

   874 	PyObject *entry;

   875 

   876 	if (pos < 0)

   877 		pos += length;

   878 

   879 	if (pos < 0 || pos >= length) {

   880 		PyErr_SetString(PyExc_IndexError, "revlog index out of range");

   881 		return NULL;

   882 	}

   883 

   884 	if (pos == length - 1) {

   885 		Py_INCREF(nullentry);

   886 		return nullentry;

   887 	}

   888 

   889 	if (pos >= self->length - 1) {

   890 		PyObject *obj;

   891 		obj = PyList_GET_ITEM(self->added, pos - self->length + 1);

   892 		Py_INCREF(obj);

   893 		return obj;

   894 	}

   895 

   896 	if (self->cache) {

   897 		if (self->cache[pos]) {

   898 			Py_INCREF(self->cache[pos]);

   899 			return self->cache[pos];

   900 		}

   901 	} else {

   902 		self->cache = calloc(self->raw_length, sizeof(PyObject *));

   903 		if (self->cache == NULL)

   904 			return PyErr_NoMemory();

   905 	}

   906 

   907 	data = index_deref(self, pos);

   908 	if (data == NULL)

   909 		return NULL;

   910 

   911 	offset_flags = getbe32(data + 4);

   912 	if (pos == 0) /* mask out version number for the first entry */

   913 		offset_flags &= 0xFFFF;

   914 	else {

   915 		uint32_t offset_high = getbe32(data);

   916 		offset_flags |= ((uint64_t)offset_high) << 32;

   917 	}

   918 

   919 	comp_len = getbe32(data + 8);

   920 	uncomp_len = getbe32(data + 12);

   921 	base_rev = getbe32(data + 16);

   922 	link_rev = getbe32(data + 20);

   923 	parent_1 = getbe32(data + 24);

   924 	parent_2 = getbe32(data + 28);

   925 	c_node_id = data + 32;

   926 

   927 	entry = Py_BuildValue(tuple_format, offset_flags, comp_len,

   928 			      uncomp_len, base_rev, link_rev,

   929 			      parent_1, parent_2, c_node_id, 20);

   930 

   931 	if (entry) {

   932 		PyObject_GC_UnTrack(entry);

   933 		Py_INCREF(entry);

   934 	}

   935 

   936 	self->cache[pos] = entry;

   937 

   938 	return entry;

   939 }

   940 

   941 /*

   942  * Return the 20-byte SHA of the node corresponding to the given rev.

   943  */

   944 static const char *index_node(indexObject *self, Py_ssize_t pos)

   945 {

   946 	Py_ssize_t length = index_length(self);

   947 	const char *data;

   948 

   949 	if (pos == length - 1 || pos == INT_MAX)

   950 		return nullid;

   951 

   952 	if (pos >= length)

   953 		return NULL;

   954 

   955 	if (pos >= self->length - 1) {

   956 		PyObject *tuple, *str;

   957 		tuple = PyList_GET_ITEM(self->added, pos - self->length + 1);

   958 		str = PyTuple_GetItem(tuple, 7);

   959 		return str ? PyBytes_AS_STRING(str) : NULL;

   960 	}

   961 

   962 	data = index_deref(self, pos);

   963 	return data ? data + 32 : NULL;

   964 }

   965 

   966 static int nt_insert(indexObject *self, const char *node, int rev);

   967 

   968 static int node_check(PyObject *obj, char **node, Py_ssize_t *nodelen)

   969 {

   970 	if (PyBytes_AsStringAndSize(obj, node, nodelen) == -1)

   971 		return -1;

   972 	if (*nodelen == 20)

   973 		return 0;

   974 	PyErr_SetString(PyExc_ValueError, "20-byte hash required");

   975 	return -1;

   976 }

   977 

   978 static PyObject *index_insert(indexObject *self, PyObject *args)

   979 {

   980 	PyObject *obj;

   981 	char *node;

   982 	int index;

   983 	Py_ssize_t len, nodelen;

   984 

   985 	if (!PyArg_ParseTuple(args, "iO", &index, &obj))

   986 		return NULL;

   987 

   988 	if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {

   989 		PyErr_SetString(PyExc_TypeError, "8-tuple required");

   990 		return NULL;

   991 	}

   992 

   993 	if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)

   994 		return NULL;

   995 

   996 	len = index_length(self);

   997 

   998 	if (index < 0)

   999 		index += len;

  1000 

  1001 	if (index != len - 1) {

  1002 		PyErr_SetString(PyExc_IndexError,

  1003 				"insert only supported at index -1");

  1004 		return NULL;

  1005 	}

  1006 

  1007 	if (self->added == NULL) {

  1008 		self->added = PyList_New(0);

  1009 		if (self->added == NULL)

  1010 			return NULL;

  1011 	}

  1012 

  1013 	if (PyList_Append(self->added, obj) == -1)

  1014 		return NULL;

  1015 

  1016 	if (self->nt)

  1017 		nt_insert(self, node, index);

  1018 

  1019 	Py_CLEAR(self->headrevs);

  1020 	Py_RETURN_NONE;

  1021 }

  1022 

  1023 static void _index_clearcaches(indexObject *self)

  1024 {

  1025 	if (self->cache) {

  1026 		Py_ssize_t i;

  1027 

  1028 		for (i = 0; i < self->raw_length; i++)

  1029 			Py_CLEAR(self->cache[i]);

  1030 		free(self->cache);

  1031 		self->cache = NULL;

  1032 	}

  1033 	if (self->offsets) {

  1034 		PyMem_Free(self->offsets);

  1035 		self->offsets = NULL;

  1036 	}

  1037 	if (self->nt) {

  1038 		free(self->nt);

  1039 		self->nt = NULL;

  1040 	}

  1041 	Py_CLEAR(self->headrevs);

  1042 }

  1043 

  1044 static PyObject *index_clearcaches(indexObject *self)

  1045 {

  1046 	_index_clearcaches(self);

  1047 	self->ntlength = self->ntcapacity = 0;

  1048 	self->ntdepth = self->ntsplits = 0;

  1049 	self->ntrev = -1;

  1050 	self->ntlookups = self->ntmisses = 0;

  1051 	Py_RETURN_NONE;

  1052 }

  1053 

  1054 static PyObject *index_stats(indexObject *self)

  1055 {

  1056 	PyObject *obj = PyDict_New();

  1057 	PyObject *t = NULL;

  1058 

  1059 	if (obj == NULL)

  1060 		return NULL;

  1061 

  1062 #define istat(__n, __d) \

  1063 	do { \

  1064 		t = PyInt_FromSsize_t(self->__n); \

  1065 		if (!t) \

  1066 			goto bail; \

  1067 		if (PyDict_SetItemString(obj, __d, t) == -1) \

  1068 			goto bail; \

  1069 		Py_DECREF(t); \

  1070 	} while (0)

  1071 

  1072 	if (self->added) {

  1073 		Py_ssize_t len = PyList_GET_SIZE(self->added);

  1074 		t = PyInt_FromSsize_t(len);

  1075 		if (!t)

  1076 			goto bail;

  1077 		if (PyDict_SetItemString(obj, "index entries added", t) == -1)

  1078 			goto bail;

  1079 		Py_DECREF(t);

  1080 	}

  1081 

  1082 	if (self->raw_length != self->length - 1)

  1083 		istat(raw_length, "revs on disk");

  1084 	istat(length, "revs in memory");

  1085 	istat(ntcapacity, "node trie capacity");

  1086 	istat(ntdepth, "node trie depth");

  1087 	istat(ntlength, "node trie count");

  1088 	istat(ntlookups, "node trie lookups");

  1089 	istat(ntmisses, "node trie misses");

  1090 	istat(ntrev, "node trie last rev scanned");

  1091 	istat(ntsplits, "node trie splits");

  1092 

  1093 #undef istat

  1094 

  1095 	return obj;

  1096 

  1097 bail:

  1098 	Py_XDECREF(obj);

  1099 	Py_XDECREF(t);

  1100 	return NULL;

  1101 }

  1102 

  1103 /*

  1104  * When we cache a list, we want to be sure the caller can't mutate

  1105  * the cached copy.

  1106  */

  1107 static PyObject *list_copy(PyObject *list)

  1108 {

  1109 	Py_ssize_t len = PyList_GET_SIZE(list);

  1110 	PyObject *newlist = PyList_New(len);

  1111 	Py_ssize_t i;

  1112 

  1113 	if (newlist == NULL)

  1114 		return NULL;

  1115 

  1116 	for (i = 0; i < len; i++) {

  1117 		PyObject *obj = PyList_GET_ITEM(list, i);

  1118 		Py_INCREF(obj);

  1119 		PyList_SET_ITEM(newlist, i, obj);

  1120 	}

  1121 

  1122 	return newlist;

  1123 }

  1124 

  1125 static int check_filter(PyObject *filter, Py_ssize_t arg) {

  1126 	if (filter) {

  1127 		PyObject *arglist, *result;

  1128 		int isfiltered;

  1129 

  1130 		arglist = Py_BuildValue("(n)", arg);

  1131 		if (!arglist) {

  1132 			return -1;

  1133 		}

  1134