--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/cext/pathencode.c	Sat Aug 13 12:23:56 2016 +0900
@@ -0,0 +1,765 @@
+/*
+ pathencode.c - efficient path name encoding
+
+ Copyright 2012 Facebook
+
+ This software may be used and distributed according to the terms of
+ the GNU General Public License, incorporated herein by reference.
+*/
+
+/*
+ * An implementation of the name encoding scheme used by the fncache
+ * store.  The common case is of a path < 120 bytes long, which is
+ * handled either in a single pass with no allocations or two passes
+ * with a single allocation.  For longer paths, multiple passes are
+ * required.
+ */
+
+#define PY_SSIZE_T_CLEAN
+#include <Python.h>
+#include <assert.h>
+#include <ctype.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "util.h"
+
+/* state machine for the fast path */
+enum path_state {
+	START,   /* first byte of a path component */
+	A,       /* "AUX" */
+	AU,
+	THIRD,   /* third of a 3-byte sequence, e.g. "AUX", "NUL" */
+	C,       /* "CON" or "COMn" */
+	CO,
+	COMLPT,  /* "COM" or "LPT" */
+	COMLPTn,
+	L,
+	LP,
+	N,
+	NU,
+	P,       /* "PRN" */
+	PR,
+	LDOT,    /* leading '.' */
+	DOT,     /* '.' in a non-leading position */
+	H,       /* ".h" */
+	HGDI,    /* ".hg", ".d", or ".i" */
+	SPACE,
+	DEFAULT  /* byte of a path component after the first */
+};
+
+/* state machine for dir-encoding */
+enum dir_state {
+	DDOT,
+	DH,
+	DHGDI,
+	DDEFAULT
+};
+
+static inline int inset(const uint32_t bitset[], char c)
+{
+	return bitset[((uint8_t)c) >> 5] & (1 << (((uint8_t)c) & 31));
+}
+
+static inline void charcopy(char *dest, Py_ssize_t *destlen, size_t destsize,
+                            char c)
+{
+	if (dest) {
+		assert(*destlen < destsize);
+		dest[*destlen] = c;
+	}
+	(*destlen)++;
+}
+
+static inline void memcopy(char *dest, Py_ssize_t *destlen, size_t destsize,
+                           const void *src, Py_ssize_t len)
+{
+	if (dest) {
+		assert(*destlen + len < destsize);
+		memcpy((void *)&dest[*destlen], src, len);
+	}
+	*destlen += len;
+}
+
+static inline void hexencode(char *dest, Py_ssize_t *destlen, size_t destsize,
+			     uint8_t c)
+{
+	static const char hexdigit[] = "0123456789abcdef";
+
+	charcopy(dest, destlen, destsize, hexdigit[c >> 4]);
+	charcopy(dest, destlen, destsize, hexdigit[c & 15]);
+}
+
+/* 3-byte escape: tilde followed by two hex digits */
+static inline void escape3(char *dest, Py_ssize_t *destlen, size_t destsize,
+			   char c)
+{
+	charcopy(dest, destlen, destsize, '~');
+	hexencode(dest, destlen, destsize, c);
+}
+
+static Py_ssize_t _encodedir(char *dest, size_t destsize,
+                             const char *src, Py_ssize_t len)
+{
+	enum dir_state state = DDEFAULT;
+	Py_ssize_t i = 0, destlen = 0;
+
+	while (i < len) {
+		switch (state) {
+		case DDOT:
+			switch (src[i]) {
+			case 'd':
+			case 'i':
+				state = DHGDI;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'h':
+				state = DH;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			default:
+				state = DDEFAULT;
+				break;
+			}
+			break;
+		case DH:
+			if (src[i] == 'g') {
+				state = DHGDI;
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DDEFAULT;
+			break;
+		case DHGDI:
+			if (src[i] == '/') {
+				memcopy(dest, &destlen, destsize, ".hg", 3);
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			state = DDEFAULT;
+			break;
+		case DDEFAULT:
+			if (src[i] == '.')
+				state = DDOT;
+			charcopy(dest, &destlen, destsize, src[i++]);
+			break;
+		}
+	}
+
+	return destlen;
+}
+
+PyObject *encodedir(PyObject *self, PyObject *args)
+{
+	Py_ssize_t len, newlen;
+	PyObject *pathobj, *newobj;
+	char *path;
+
+	if (!PyArg_ParseTuple(args, "O:encodedir", &pathobj))
+		return NULL;
+
+	if (PyBytes_AsStringAndSize(pathobj, &path, &len) == -1) {
+		PyErr_SetString(PyExc_TypeError, "expected a string");
+		return NULL;
+	}
+
+	newlen = len ? _encodedir(NULL, 0, path, len + 1) : 1;
+
+	if (newlen == len + 1) {
+		Py_INCREF(pathobj);
+		return pathobj;
+	}
+
+	newobj = PyBytes_FromStringAndSize(NULL, newlen);
+
+	if (newobj) {
+		assert(PyBytes_Check(newobj));
+		Py_SIZE(newobj)--;
+		_encodedir(PyBytes_AS_STRING(newobj), newlen, path,
+			   len + 1);
+	}
+
+	return newobj;
+}
+
+static Py_ssize_t _encode(const uint32_t twobytes[8], const uint32_t onebyte[8],
+			  char *dest, Py_ssize_t destlen, size_t destsize,
+			  const char *src, Py_ssize_t len,
+			  int encodedir)
+{
+	enum path_state state = START;
+	Py_ssize_t i = 0;
+
+	/*
+	 * Python strings end with a zero byte, which we use as a
+	 * terminal token as they are not valid inside path names.
+	 */
+
+	while (i < len) {
+		switch (state) {
+		case START:
+			switch (src[i]) {
+			case '/':
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case '.':
+				state = LDOT;
+				escape3(dest, &destlen, destsize, src[i++]);
+				break;
+			case ' ':
+				state = DEFAULT;
+				escape3(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'a':
+				state = A;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'c':
+				state = C;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'l':
+				state = L;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'n':
+				state = N;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'p':
+				state = P;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			default:
+				state = DEFAULT;
+				break;
+			}
+			break;
+		case A:
+			if (src[i] == 'u') {
+				state = AU;
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DEFAULT;
+			break;
+		case AU:
+			if (src[i] == 'x') {
+				state = THIRD;
+				i++;
+			}
+			else state = DEFAULT;
+			break;
+		case THIRD:
+			state = DEFAULT;
+			switch (src[i]) {
+			case '.':
+			case '/':
+			case '\0':
+				escape3(dest, &destlen, destsize, src[i - 1]);
+				break;
+			default:
+				i--;
+				break;
+			}
+			break;
+		case C:
+			if (src[i] == 'o') {
+				state = CO;
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DEFAULT;
+			break;
+		case CO:
+			if (src[i] == 'm') {
+				state = COMLPT;
+				i++;
+			}
+			else if (src[i] == 'n') {
+				state = THIRD;
+				i++;
+			}
+			else state = DEFAULT;
+			break;
+		case COMLPT:
+			switch (src[i]) {
+			case '1': case '2': case '3': case '4': case '5':
+			case '6': case '7': case '8': case '9':
+				state = COMLPTn;
+				i++;
+				break;
+			default:
+				state = DEFAULT;
+				charcopy(dest, &destlen, destsize, src[i - 1]);
+				break;
+			}
+			break;
+		case COMLPTn:
+			state = DEFAULT;
+			switch (src[i]) {
+			case '.':
+			case '/':
+			case '\0':
+				escape3(dest, &destlen, destsize, src[i - 2]);
+				charcopy(dest, &destlen, destsize, src[i - 1]);
+				break;
+			default:
+				memcopy(dest, &destlen, destsize,
+					&src[i - 2], 2);
+				break;
+			}
+			break;
+		case L:
+			if (src[i] == 'p') {
+				state = LP;
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DEFAULT;
+			break;
+		case LP:
+			if (src[i] == 't') {
+				state = COMLPT;
+				i++;
+			}
+			else state = DEFAULT;
+			break;
+		case N:
+			if (src[i] == 'u') {
+				state = NU;
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DEFAULT;
+			break;
+		case NU:
+			if (src[i] == 'l') {
+				state = THIRD;
+				i++;
+			}
+			else state = DEFAULT;
+			break;
+		case P:
+			if (src[i] == 'r') {
+				state = PR;
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DEFAULT;
+			break;
+		case PR:
+			if (src[i] == 'n') {
+				state = THIRD;
+				i++;
+			}
+			else state = DEFAULT;
+			break;
+		case LDOT:
+			switch (src[i]) {
+			case 'd':
+			case 'i':
+				state = HGDI;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'h':
+				state = H;
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			default:
+				state = DEFAULT;
+				break;
+			}
+			break;
+		case DOT:
+			switch (src[i]) {
+			case '/':
+			case '\0':
+				state = START;
+				memcopy(dest, &destlen, destsize, "~2e", 3);
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'd':
+			case 'i':
+				state = HGDI;
+				charcopy(dest, &destlen, destsize, '.');
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			case 'h':
+				state = H;
+				memcopy(dest, &destlen, destsize, ".h", 2);
+				i++;
+				break;
+			default:
+				state = DEFAULT;
+				charcopy(dest, &destlen, destsize, '.');
+				break;
+			}
+			break;
+		case H:
+			if (src[i] == 'g') {
+				state = HGDI;
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DEFAULT;
+			break;
+		case HGDI:
+			if (src[i] == '/') {
+				state = START;
+				if (encodedir)
+					memcopy(dest, &destlen, destsize, ".hg",
+						3);
+				charcopy(dest, &destlen, destsize, src[i++]);
+			}
+			else state = DEFAULT;
+			break;
+		case SPACE:
+			switch (src[i]) {
+			case '/':
+			case '\0':
+				state = START;
+				memcopy(dest, &destlen, destsize, "~20", 3);
+				charcopy(dest, &destlen, destsize, src[i++]);
+				break;
+			default:
+				state = DEFAULT;
+				charcopy(dest, &destlen, destsize, ' ');
+				break;
+			}
+			break;
+		case DEFAULT:
+			while (inset(onebyte, src[i])) {
+				charcopy(dest, &destlen, destsize, src[i++]);
+				if (i == len)
+					goto done;
+			}
+			switch (src[i]) {
+			case '.':
+				state = DOT;
+				i++;
+				break;
+			case ' ':
+				state = SPACE;
+				i++;
+				break;
+			case '/':
+				state = START;
+				charcopy(dest, &destlen, destsize, '/');
+				i++;
+				break;
+			default:
+				if (inset(onebyte, src[i])) {
+					do {
+						charcopy(dest, &destlen,
+							 destsize, src[i++]);
+					} while (i < len &&
+						 inset(onebyte, src[i]));
+				}
+				else if (inset(twobytes, src[i])) {
+					char c = src[i++];
+					charcopy(dest, &destlen, destsize, '_');
+					charcopy(dest, &destlen, destsize,
+						 c == '_' ? '_' : c + 32);
+				}
+				else
+					escape3(dest, &destlen, destsize,
+						src[i++]);
+				break;
+			}
+			break;
+		}
+	}
+done:
+	return destlen;
+}
+
+static Py_ssize_t basicencode(char *dest, size_t destsize,
+			      const char *src, Py_ssize_t len)
+{
+	static const uint32_t twobytes[8] = { 0, 0, 0x87fffffe };
+
+	static const uint32_t onebyte[8] = {
+		1, 0x2bff3bfa, 0x68000001, 0x2fffffff,
+	};
+
+	Py_ssize_t destlen = 0;
+
+	return _encode(twobytes, onebyte, dest, destlen, destsize,
+		       src, len, 1);
+}
+
+static const Py_ssize_t maxstorepathlen = 120;
+
+static Py_ssize_t _lowerencode(char *dest, size_t destsize,
+			       const char *src, Py_ssize_t len)
+{
+	static const uint32_t onebyte[8] = {
+		1, 0x2bfffbfb, 0xe8000001, 0x2fffffff
+	};
+
+	static const uint32_t lower[8] = { 0, 0, 0x7fffffe };
+
+	Py_ssize_t i, destlen = 0;
+
+	for (i = 0; i < len; i++) {
+		if (inset(onebyte, src[i]))
+			charcopy(dest, &destlen, destsize, src[i]);
+		else if (inset(lower, src[i]))
+			charcopy(dest, &destlen, destsize, src[i] + 32);
+		else
+			escape3(dest, &destlen, destsize, src[i]);
+	}
+
+	return destlen;
+}
+
+PyObject *lowerencode(PyObject *self, PyObject *args)
+{
+	char *path;
+	Py_ssize_t len, newlen;
+	PyObject *ret;
+
+	if (!PyArg_ParseTuple(args, "s#:lowerencode", &path, &len))
+		return NULL;
+
+	newlen = _lowerencode(NULL, 0, path, len);
+	ret = PyBytes_FromStringAndSize(NULL, newlen);
+	if (ret)
+		_lowerencode(PyBytes_AS_STRING(ret), newlen, path, len);
+
+	return ret;
+}
+
+/* See store.py:_auxencode for a description. */
+static Py_ssize_t auxencode(char *dest, size_t destsize,
+			    const char *src, Py_ssize_t len)
+{
+	static const uint32_t twobytes[8];
+
+	static const uint32_t onebyte[8] = {
+		~0U, 0xffff3ffe, ~0U, ~0U, ~0U, ~0U, ~0U, ~0U,
+	};
+
+	return _encode(twobytes, onebyte, dest, 0, destsize, src, len, 0);
+}
+
+static PyObject *hashmangle(const char *src, Py_ssize_t len, const char sha[20])
+{
+	static const Py_ssize_t dirprefixlen = 8;
+	static const Py_ssize_t maxshortdirslen = 68;
+	char *dest;
+	PyObject *ret;
+
+	Py_ssize_t i, d, p, lastslash = len - 1, lastdot = -1;
+	Py_ssize_t destsize, destlen = 0, slop, used;
+
+	while (lastslash >= 0 && src[lastslash] != '/') {
+		if (src[lastslash] == '.' && lastdot == -1)
+			lastdot = lastslash;
+		lastslash--;
+	}
+
+#if 0
+	/* All paths should end in a suffix of ".i" or ".d".
+           Unfortunately, the file names in test-hybridencode.py
+           violate this rule.  */
+	if (lastdot != len - 3) {
+		PyErr_SetString(PyExc_ValueError,
+				"suffix missing or wrong length");
+		return NULL;
+	}
+#endif
+
+	/* If src contains a suffix, we will append it to the end of
+	   the new string, so make room. */
+	destsize = 120;
+	if (lastdot >= 0)
+		destsize += len - lastdot - 1;
+
+	ret = PyBytes_FromStringAndSize(NULL, destsize);
+	if (ret == NULL)
+		return NULL;
+
+	dest = PyBytes_AS_STRING(ret);
+	memcopy(dest, &destlen, destsize, "dh/", 3);
+
+	/* Copy up to dirprefixlen bytes of each path component, up to
+	   a limit of maxshortdirslen bytes. */
+	for (i = d = p = 0; i < lastslash; i++, p++) {
+		if (src[i] == '/') {
+			char d = dest[destlen - 1];
+			/* After truncation, a directory name may end
+			   in a space or dot, which are unportable. */
+			if (d == '.' || d == ' ')
+				dest[destlen - 1] = '_';
+			/* The + 3 is to account for "dh/" in the beginning */
+			if (destlen > maxshortdirslen + 3)
+				break;
+			charcopy(dest, &destlen, destsize, src[i]);
+			p = -1;
+		}
+		else if (p < dirprefixlen)
+			charcopy(dest, &destlen, destsize, src[i]);
+	}
+
+	/* Rewind to just before the last slash copied. */
+	if (destlen > maxshortdirslen + 3)
+		do {
+			destlen--;
+		} while (destlen > 0 && dest[destlen] != '/');
+
+	if (destlen > 3) {
+		if (lastslash > 0) {
+			char d = dest[destlen - 1];
+			/* The last directory component may be
+			   truncated, so make it safe. */
+			if (d == '.' || d == ' ')
+				dest[destlen - 1] = '_';
+		}
+
+		charcopy(dest, &destlen, destsize, '/');
+	}
+
+	/* Add a prefix of the original file's name. Its length
+	   depends on the number of bytes left after accounting for
+	   hash and suffix. */
+	used = destlen + 40;
+	if (lastdot >= 0)
+		used += len - lastdot - 1;
+	slop = maxstorepathlen - used;
+	if (slop > 0) {
+		Py_ssize_t basenamelen =
+			lastslash >= 0 ? len - lastslash - 2 : len - 1;
+
+		if (basenamelen > slop)
+			basenamelen = slop;
+		if (basenamelen > 0)
+			memcopy(dest, &destlen, destsize, &src[lastslash + 1],
+				basenamelen);
+	}
+
+	/* Add hash and suffix. */
+	for (i = 0; i < 20; i++)
+		hexencode(dest, &destlen, destsize, sha[i]);
+
+	if (lastdot >= 0)
+		memcopy(dest, &destlen, destsize, &src[lastdot],
+			len - lastdot - 1);
+
+	assert(PyBytes_Check(ret));
+	Py_SIZE(ret) = destlen;
+
+	return ret;
+}
+
+/*
+ * Avoiding a trip through Python would improve performance by 50%,
+ * but we don't encounter enough long names to be worth the code.
+ */
+static int sha1hash(char hash[20], const char *str, Py_ssize_t len)
+{
+	static PyObject *shafunc;
+	PyObject *shaobj, *hashobj;
+
+	if (shafunc == NULL) {
+		PyObject *hashlib, *name = PyBytes_FromString("hashlib");
+
+		if (name == NULL)
+			return -1;
+
+		hashlib = PyImport_Import(name);
+		Py_DECREF(name);
+
+		if (hashlib == NULL) {
+			PyErr_SetString(PyExc_ImportError, "hashlib");
+			return -1;
+		}
+		shafunc = PyObject_GetAttrString(hashlib, "sha1");
+		Py_DECREF(hashlib);
+
+		if (shafunc == NULL) {
+			PyErr_SetString(PyExc_AttributeError,
+					"module 'hashlib' has no "
+					"attribute 'sha1'");
+			return -1;
+		}
+	}
+
+	shaobj = PyObject_CallFunction(shafunc, "s#", str, len);
+
+	if (shaobj == NULL)
+		return -1;
+
+	hashobj = PyObject_CallMethod(shaobj, "digest", "");
+	Py_DECREF(shaobj);
+	if (hashobj == NULL)
+		return -1;
+
+	if (!PyBytes_Check(hashobj) || PyBytes_GET_SIZE(hashobj) != 20) {
+		PyErr_SetString(PyExc_TypeError,
+				"result of digest is not a 20-byte hash");
+		Py_DECREF(hashobj);
+		return -1;
+	}
+
+	memcpy(hash, PyBytes_AS_STRING(hashobj), 20);
+	Py_DECREF(hashobj);
+	return 0;
+}
+
+#define MAXENCODE 4096 * 4
+
+static PyObject *hashencode(const char *src, Py_ssize_t len)
+{
+	char dired[MAXENCODE];
+	char lowered[MAXENCODE];
+	char auxed[MAXENCODE];
+	Py_ssize_t dirlen, lowerlen, auxlen, baselen;
+	char sha[20];
+
+	baselen = (len - 5) * 3;
+	if (baselen >= MAXENCODE) {
+		PyErr_SetString(PyExc_ValueError, "string too long");
+		return NULL;
+	}
+
+	dirlen = _encodedir(dired, baselen, src, len);
+	if (sha1hash(sha, dired, dirlen - 1) == -1)
+		return NULL;
+	lowerlen = _lowerencode(lowered, baselen, dired + 5, dirlen - 5);
+	auxlen = auxencode(auxed, baselen, lowered, lowerlen);
+	return hashmangle(auxed, auxlen, sha);
+}
+
+PyObject *pathencode(PyObject *self, PyObject *args)
+{
+	Py_ssize_t len, newlen;
+	PyObject *pathobj, *newobj;
+	char *path;
+
+	if (!PyArg_ParseTuple(args, "O:pathencode", &pathobj))
+		return NULL;
+
+	if (PyBytes_AsStringAndSize(pathobj, &path, &len) == -1) {
+		PyErr_SetString(PyExc_TypeError, "expected a string");
+		return NULL;
+	}
+
+	if (len > maxstorepathlen)
+		newlen = maxstorepathlen + 2;
+	else
+		newlen = len ? basicencode(NULL, 0, path, len + 1) : 1;
+
+	if (newlen <= maxstorepathlen + 1) {
+		if (newlen == len + 1) {
+			Py_INCREF(pathobj);
+			return pathobj;
+		}
+
+		newobj = PyBytes_FromStringAndSize(NULL, newlen);
+
+		if (newobj) {
+			assert(PyBytes_Check(newobj));
+			Py_SIZE(newobj)--;
+			basicencode(PyBytes_AS_STRING(newobj), newlen, path,
+				    len + 1);
+		}
+	}
+	else
+		newobj = hashencode(path, len + 1);
+
+	return newobj;
+}