--- /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;
+}