merge with stable

doc/hgrc.5.txt

@@ -1,41 +1,41
 ======
  hgrc
 ======
 
 ---------------------------------
 configuration files for Mercurial
 ---------------------------------
 
 :Author:         Bryan O'Sullivan <[e-mail]>
 :Organization:   Mercurial
 :Manual section: 5
 :Manual group:   Mercurial Manual
 
 .. contents::
    :backlinks: top
    :class: htmlonly
 
 
-Synopsis
-========
+Description
+===========
 
 .. include:: ../mercurial/help/config.txt
 
 Author
 ======
 Bryan O'Sullivan <[e-mail]>.
 
 Mercurial was written by Matt Mackall <[e-mail]>.
 
 See Also
 ========
 |hg(1)|_, |hgignore(5)|_
 
 Copying
 =======
 This manual page is copyright 2005 Bryan O'Sullivan.
 Mercurial is copyright 2005-2012 Matt Mackall.
 Free use of this software is granted under the terms of the GNU General
 Public License version 2 or any later version.
 
 .. include:: common.txt

mercurial/pathencode.c

@@ -1,760 +1,761
 /*
  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 (PyString_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 = PyString_FromStringAndSize(NULL, newlen);
 
 	if (newobj) {
 		PyString_GET_SIZE(newobj)--;
 		_encodedir(PyString_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 = PyString_FromStringAndSize(NULL, newlen);
 	if (ret)
 		newlen = _lowerencode(PyString_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] = {
 		~0, 0xffff3ffe, ~0, ~0, ~0, ~0, ~0, ~0,
 	};
 
 	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 = PyString_FromStringAndSize(NULL, destsize);
 	if (ret == NULL)
 		return NULL;
 
 	dest = PyString_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] = '_';
-			if (destlen > maxshortdirslen)
+			/* 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);
 
 	PyString_GET_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 *util, *name = PyString_FromString("mercurial.util");
 
 		if (name == NULL)
 			return -1;
 
 		util = PyImport_Import(name);
 		Py_DECREF(name);
 
 		if (util == NULL) {
 			PyErr_SetString(PyExc_ImportError, "mercurial.util");
 			return -1;
 		}
 		shafunc = PyObject_GetAttrString(util, "sha1");
 		Py_DECREF(util);
 
 		if (shafunc == NULL) {
 			PyErr_SetString(PyExc_AttributeError,
 					"module 'mercurial.util' 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 (!PyString_Check(hashobj) || PyString_GET_SIZE(hashobj) != 20) {
 		PyErr_SetString(PyExc_TypeError,
 				"result of digest is not a 20-byte hash");
 		Py_DECREF(hashobj);
 		return -1;
 	}
 
 	memcpy(hash, PyString_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 (PyString_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 = PyString_FromStringAndSize(NULL, newlen);
 
 		if (newobj) {
 			PyString_GET_SIZE(newobj)--;
 			basicencode(PyString_AS_STRING(newobj), newlen, path,
 				    len + 1);
 		}
 	}
 	else
 		newobj = hashencode(path, len + 1);
 
 	return newobj;
 }

tests/test-pathencode.py

@@ -1,197 +1,198
 # This is a randomized test that generates different pathnames every
 # time it is invoked, and tests the encoding of those pathnames.
 #
 # It uses a simple probabilistic model to generate valid pathnames
 # that have proven likely to expose bugs and divergent behaviour in
 # different encoding implementations.
 
 from mercurial import store
 import binascii, itertools, math, os, random, sys, time
 import collections
 
 if sys.version_info[:2] < (2, 6):
     sys.exit(0)
 
 validchars = set(map(chr, range(0, 256)))
 alphanum = range(ord('A'), ord('Z'))
 
 for c in '\0/':
     validchars.remove(c)
 
 winreserved = ('aux con prn nul'.split() +
                ['com%d' % i for i in xrange(1, 10)] +
                ['lpt%d' % i for i in xrange(1, 10)])
 
 def casecombinations(names):
     '''Build all case-diddled combinations of names.'''
 
     combos = set()
 
     for r in names:
         for i in xrange(len(r) + 1):
             for c in itertools.combinations(xrange(len(r)), i):
                 d = r
                 for j in c:
                     d = ''.join((d[:j], d[j].upper(), d[j + 1:]))
                 combos.add(d)
     return sorted(combos)
 
 def buildprobtable(fp, cmd='hg manifest tip'):
     '''Construct and print a table of probabilities for path name
     components.  The numbers are percentages.'''
 
     counts = collections.defaultdict(lambda: 0)
     for line in os.popen(cmd).read().splitlines():
         if line[-2:] in ('.i', '.d'):
             line = line[:-2]
         if line.startswith('data/'):
             line = line[5:]
         for c in line:
             counts[c] += 1
     for c in '\r/\n':
         counts.pop(c, None)
     t = sum(counts.itervalues()) / 100.0
     fp.write('probtable = (')
     for i, (k, v) in enumerate(sorted(counts.iteritems(), key=lambda x: x[1],
                                       reverse=True)):
         if (i % 5) == 0:
             fp.write('\n    ')
         vt = v / t
         if vt < 0.0005:
             break
         fp.write('(%r, %.03f), ' % (k, vt))
     fp.write('\n    )\n')
 
 # A table of character frequencies (as percentages), gleaned by
 # looking at filelog names from a real-world, very large repo.
 
 probtable = (
     ('t', 9.828), ('e', 9.042), ('s', 8.011), ('a', 6.801), ('i', 6.618),
     ('g', 5.053), ('r', 5.030), ('o', 4.887), ('p', 4.363), ('n', 4.258),
     ('l', 3.830), ('h', 3.693), ('_', 3.659), ('.', 3.377), ('m', 3.194),
     ('u', 2.364), ('d', 2.296), ('c', 2.163), ('b', 1.739), ('f', 1.625),
     ('6', 0.666), ('j', 0.610), ('y', 0.554), ('x', 0.487), ('w', 0.477),
     ('k', 0.476), ('v', 0.473), ('3', 0.336), ('1', 0.335), ('2', 0.326),
     ('4', 0.310), ('5', 0.305), ('9', 0.302), ('8', 0.300), ('7', 0.299),
     ('q', 0.298), ('0', 0.250), ('z', 0.223), ('-', 0.118), ('C', 0.095),
     ('T', 0.087), ('F', 0.085), ('B', 0.077), ('S', 0.076), ('P', 0.076),
     ('L', 0.059), ('A', 0.058), ('N', 0.051), ('D', 0.049), ('M', 0.046),
     ('E', 0.039), ('I', 0.035), ('R', 0.035), ('G', 0.028), ('U', 0.026),
     ('W', 0.025), ('O', 0.017), ('V', 0.015), ('H', 0.013), ('Q', 0.011),
     ('J', 0.007), ('K', 0.005), ('+', 0.004), ('X', 0.003), ('Y', 0.001),
     )
 
 for c, _ in probtable:
     validchars.remove(c)
 validchars = list(validchars)
 
 def pickfrom(rng, table):
     c = 0
     r = rng.random() * sum(i[1] for i in table)
     for i, p in table:
         c += p
         if c >= r:
             return i
 
 reservedcombos = casecombinations(winreserved)
 
 # The first component of a name following a slash.
 
 firsttable = (
     (lambda rng: pickfrom(rng, probtable), 90),
     (lambda rng: rng.choice(validchars), 5),
     (lambda rng: rng.choice(reservedcombos), 5),
     )
 
 # Components of a name following the first.
 
 resttable = firsttable[:-1]
 
 # Special suffixes.
 
 internalsuffixcombos = casecombinations('.hg .i .d'.split())
 
 # The last component of a path, before a slash or at the end of a name.
 
 lasttable = resttable + (
     (lambda rng: '', 95),
     (lambda rng: rng.choice(internalsuffixcombos), 5),
     )
 
 def makepart(rng, k):
     '''Construct a part of a pathname, without slashes.'''
 
     p = pickfrom(rng, firsttable)(rng)
     l = len(p)
     ps = [p]
-    while l <= k:
+    maxl = rng.randint(1, k)
+    while l < maxl:
         p = pickfrom(rng, resttable)(rng)
         l += len(p)
         ps.append(p)
     ps.append(pickfrom(rng, lasttable)(rng))
     return ''.join(ps)
 
 def makepath(rng, j, k):
     '''Construct a complete pathname.'''
 
     return ('data/' + '/'.join(makepart(rng, k) for _ in xrange(j)) +
             rng.choice(['.d', '.i']))
 
 def genpath(rng, count):
     '''Generate random pathnames with gradually increasing lengths.'''
 
     mink, maxk = 1, 4096
     def steps():
         x, k = 0, mink
         for i in xrange(count):
             yield mink + int(round(math.sqrt((maxk - mink) * float(i) / count)))
     for k in steps():
         x = rng.randint(1, k)
         y = rng.randint(1, k)
         yield makepath(rng, x, y)
 
 def runtests(rng, seed, count):
     nerrs = 0
     for p in genpath(rng, count):
         h = store._pathencode(p)    # uses C implementation, if available
         r = store._hybridencode(p, True) # reference implementation in Python
         if h != r:
             if nerrs == 0:
                 print >> sys.stderr, 'seed:', hex(seed)[:-1]
             print >> sys.stderr, "\np: '%s'" % p.encode("string_escape")
             print >> sys.stderr, "h: '%s'" % h.encode("string_escape")
             print >> sys.stderr, "r: '%s'" % r.encode("string_escape")
             nerrs += 1
     return nerrs
 
 def main():
     import getopt
 
     # Empirically observed to take about a second to run
     count = 100
     seed = None
     opts, args = getopt.getopt(sys.argv[1:], 'c:s:',
                                ['build', 'count=', 'seed='])
     for o, a in opts:
         if o in ('-c', '--count'):
             count = int(a)
         elif o in ('-s', '--seed'):
             seed = long(a, base=0) # accepts base 10 or 16 strings
         elif o == '--build':
             buildprobtable(sys.stdout,
                            'find .hg/store/data -type f && '
                            'cat .hg/store/fncache 2>/dev/null')
             sys.exit(0)
 
     if seed is None:
         try:
             seed = long(binascii.hexlify(os.urandom(16)), 16)
         except AttributeError:
             seed = long(time.time() * 1000)
 
     rng = random.Random(seed)
     if runtests(rng, seed, count):
         sys.exit(1)
 
 if __name__ == '__main__':
     main()