/* String (str/bytes) object implementation */

#define PY_SSIZE_T_CLEAN

#include "Python.h"

#include <ctype.h>

#ifdef COUNT_ALLOCS

int null_strings, one_strings;

#endif

static PyStringObject *characters[UCHAR_MAX + 1];

static PyStringObject *nullstring;

/* This dictionary holds all interned strings.  Note that references to

   strings in this dictionary are *not* counted in the string's ob_refcnt.

   When the interned string reaches a refcnt of 0 the string deallocation

   function will delete the reference from this dictionary.

   Another way to look at this is that to say that the actual reference

   count of a string is:  s->ob_refcnt + (s->ob_sstate?2:0)

*/

static PyObject *interned;

/*

   For both PyString_FromString() and PyString_FromStringAndSize(), the

   parameter `size' denotes number of characters to allocate, not counting any

   null terminating character.

   For PyString_FromString(), the parameter `str' points to a null-terminated

   string containing exactly `size' bytes.

   For PyString_FromStringAndSize(), the parameter the parameter `str' is

   either NULL or else points to a string containing at least `size' bytes.

   For PyString_FromStringAndSize(), the string in the `str' parameter does

   not have to be null-terminated.  (Therefore it is safe to construct a

   substring by calling `PyString_FromStringAndSize(origstring, substrlen)'.)

   If `str' is NULL then PyString_FromStringAndSize() will allocate `size+1'

   bytes (setting the last byte to the null terminating character) and you can

   fill in the data yourself.  If `str' is non-NULL then the resulting

   PyString object must be treated as immutable and you must not fill in nor

   alter the data yourself, since the strings may be shared.

   The PyObject member `op->ob_size', which denotes the number of "extra

   items" in a variable-size object, will contain the number of bytes

   allocated for string data, not counting the null terminating character.  It

   is therefore equal to the equal to the `size' parameter (for

   PyString_FromStringAndSize()) or the length of the string in the `str'

   parameter (for PyString_FromString()).

*/

PyObject *

PyString_FromStringAndSize(const char *str, Py_ssize_t size)

{

	register PyStringObject *op;

	if (size < 0) {

		PyErr_SetString(PyExc_SystemError,

		    "Negative size passed to PyString_FromStringAndSize");

		return NULL;

	}

	if (size == 0 && (op = nullstring) != NULL) {

#ifdef COUNT_ALLOCS

		null_strings++;

#endif

		Py_INCREF(op);

		return (PyObject *)op;

	}

	if (size == 1 && str != NULL &&

	    (op = characters[*str & UCHAR_MAX]) != NULL)

	{

#ifdef COUNT_ALLOCS

		one_strings++;

#endif

		Py_INCREF(op);

		return (PyObject *)op;

	}

	if (size > PY_SSIZE_T_MAX - sizeof(PyStringObject)) {

		PyErr_SetString(PyExc_OverflowError, "string is too large");

		return NULL;

	}

	/* Inline PyObject_NewVar */

	op = (PyStringObject *)PyObject_MALLOC(sizeof(PyStringObject) + size);

	if (op == NULL)

		return PyErr_NoMemory();

	PyObject_INIT_VAR(op, &PyString_Type, size);

	op->ob_shash = -1;

	op->ob_sstate = SSTATE_NOT_INTERNED;

	if (str != NULL)

		Py_MEMCPY(op->ob_sval, str, size);

	op->ob_sval[size] = '\0';

	/* share short strings */

	if (size == 0) {

		PyObject *t = (PyObject *)op;

		PyString_InternInPlace(&t);

		op = (PyStringObject *)t;

		nullstring = op;

		Py_INCREF(op);

	} else if (size == 1 && str != NULL) {

		PyObject *t = (PyObject *)op;

		PyString_InternInPlace(&t);

		op = (PyStringObject *)t;

		characters[*str & UCHAR_MAX] = op;

		Py_INCREF(op);

	}

	return (PyObject *) op;

}

PyObject *

PyString_FromString(const char *str)

{

	register size_t size;

	register PyStringObject *op;

	assert(str != NULL);

	size = strlen(str);

	if (size > PY_SSIZE_T_MAX - sizeof(PyStringObject)) {

		PyErr_SetString(PyExc_OverflowError,

			"string is too long for a Python string");

		return NULL;

	}

	if (size == 0 && (op = nullstring) != NULL) {

#ifdef COUNT_ALLOCS

		null_strings++;

#endif

		Py_INCREF(op);

		return (PyObject *)op;

	}

	if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL) {

#ifdef COUNT_ALLOCS

		one_strings++;

#endif

		Py_INCREF(op);

		return (PyObject *)op;

	}

	/* Inline PyObject_NewVar */

	op = (PyStringObject *)PyObject_MALLOC(sizeof(PyStringObject) + size);

	if (op == NULL)

		return PyErr_NoMemory();

	PyObject_INIT_VAR(op, &PyString_Type, size);

	op->ob_shash = -1;

	op->ob_sstate = SSTATE_NOT_INTERNED;

	Py_MEMCPY(op->ob_sval, str, size+1);

	/* share short strings */

	if (size == 0) {

		PyObject *t = (PyObject *)op;

		PyString_InternInPlace(&t);

		op = (PyStringObject *)t;

		nullstring = op;

		Py_INCREF(op);

	} else if (size == 1) {

		PyObject *t = (PyObject *)op;

		PyString_InternInPlace(&t);

		op = (PyStringObject *)t;

		characters[*str & UCHAR_MAX] = op;

		Py_INCREF(op);

	}

	return (PyObject *) op;

}

PyObject *

PyString_FromFormatV(const char *format, va_list vargs)

{

	va_list count;

	Py_ssize_t n = 0;

	const char* f;

	char *s;

	PyObject* string;

#ifdef VA_LIST_IS_ARRAY

	Py_MEMCPY(count, vargs, sizeof(va_list));

#else

#ifdef  __va_copy

	__va_copy(count, vargs);

#else

	count = vargs;

#endif

#endif

	/* step 1: figure out how large a buffer we need */

	for (f = format; *f; f++) {

		if (*f == '%') {

			const char* p = f;

			while (*++f && *f != '%' && !isalpha(Py_CHARMASK(*f)))

				;

			/* skip the 'l' or 'z' in {%ld, %zd, %lu, %zu} since

			 * they don't affect the amount of space we reserve.

			 */

			if ((*f == 'l' || *f == 'z') &&

					(f[1] == 'd' || f[1] == 'u'))

				++f;

			switch (*f) {

			case 'c':

				(void)va_arg(count, int);

				/* fall through... */

			case '%':

				n++;

				break;

			case 'd': case 'u': case 'i': case 'x':

				(void) va_arg(count, int);

				/* 20 bytes is enough to hold a 64-bit

				   integer.  Decimal takes the most space.

				   This isn't enough for octal. */

				n += 20;

				break;

			case 's':

				s = va_arg(count, char*);

				n += strlen(s);

				break;

			case 'p':

				(void) va_arg(count, int);

				/* maximum 64-bit pointer representation:

				 * 0xffffffffffffffff

				 * so 19 characters is enough.

				 * XXX I count 18 -- what's the extra for?

				 */

				n += 19;

				break;

			default:

				/* if we stumble upon an unknown

				   formatting code, copy the rest of

				   the format string to the output

				   string. (we cannot just skip the

				   code, since there's no way to know

				   what's in the argument list) */

				n += strlen(p);

				goto expand;

			}

		} else

			n++;

	}

 expand:

	/* step 2: fill the buffer */

	/* Since we've analyzed how much space we need for the worst case,

	   use sprintf directly instead of the slower PyOS_snprintf. */

	string = PyString_FromStringAndSize(NULL, n);

	if (!string)

		return NULL;

	s = PyString_AsString(string);

	for (f = format; *f; f++) {

		if (*f == '%') {

			const char* p = f++;

			Py_ssize_t i;

			int longflag = 0;

			int size_tflag = 0;

			/* parse the width.precision part (we're only

			   interested in the precision value, if any) */

			n = 0;

			while (isdigit(Py_CHARMASK(*f)))

				n = (n*10) + *f++ - '0';

			if (*f == '.') {

				f++;

				n = 0;

				while (isdigit(Py_CHARMASK(*f)))

					n = (n*10) + *f++ - '0';

			}

			while (*f && *f != '%' && !isalpha(Py_CHARMASK(*f)))

				f++;

			/* handle the long flag, but only for %ld and %lu.

			   others can be added when necessary. */

			if (*f == 'l' && (f[1] == 'd' || f[1] == 'u')) {

				longflag = 1;

				++f;

			}

			/* handle the size_t flag. */

			if (*f == 'z' && (f[1] == 'd' || f[1] == 'u')) {

				size_tflag = 1;

				++f;

			}

			switch (*f) {

			case 'c':

				*s++ = va_arg(vargs, int);

				break;

			case 'd':

				if (longflag)

					sprintf(s, "%ld", va_arg(vargs, long));

				else if (size_tflag)

					sprintf(s, "%" PY_FORMAT_SIZE_T "d",

					        va_arg(vargs, Py_ssize_t));

				else

					sprintf(s, "%d", va_arg(vargs, int));

				s += strlen(s);

				break;

			case 'u':

				if (longflag)

					sprintf(s, "%lu",

						va_arg(vargs, unsigned long));

				else if (size_tflag)

					sprintf(s, "%" PY_FORMAT_SIZE_T "u",

					        va_arg(vargs, size_t));

				else

					sprintf(s, "%u",

						va_arg(vargs, unsigned int));

				s += strlen(s);

				break;

			case 'i':

				sprintf(s, "%i", va_arg(vargs, int));

				s += strlen(s);

				break;

			case 'x':

				sprintf(s, "%x", va_arg(vargs, int));

				s += strlen(s);

				break;

			case 's':

				p = va_arg(vargs, char*);

				i = strlen(p);

				if (n > 0 && i > n)

					i = n;

				Py_MEMCPY(s, p, i);

				s += i;

				break;

			case 'p':

				sprintf(s, "%p", va_arg(vargs, void*));

				/* %p is ill-defined:  ensure leading 0x. */

				if (s[1] == 'X')

					s[1] = 'x';

				else if (s[1] != 'x') {

					memmove(s+2, s, strlen(s)+1);

					s[0] = '0';

					s[1] = 'x';

				}

				s += strlen(s);

				break;

			case '%':

				*s++ = '%';

				break;

			default:

				strcpy(s, p);

				s += strlen(s);

				goto end;

			}

		} else

			*s++ = *f;

	}

 end:

	_PyString_Resize(&string, s - PyString_AS_STRING(string));

	return string;

}

PyObject *

PyString_FromFormat(const char *format, ...)

{

	PyObject* ret;

	va_list vargs;

#ifdef HAVE_STDARG_PROTOTYPES

	va_start(vargs, format);

#else

	va_start(vargs);

#endif

	ret = PyString_FromFormatV(format, vargs);

	va_end(vargs);

	return ret;

}

PyObject *PyString_Decode(const char *s,

			  Py_ssize_t size,

			  const char *encoding,

			  const char *errors)

{

    PyObject *v, *str;

    str = PyString_FromStringAndSize(s, size);

    if (str == NULL)

	return NULL;

    v = PyString_AsDecodedString(str, encoding, errors);

    Py_DECREF(str);

    return v;

}

PyObject *PyString_AsDecodedObject(PyObject *str,

				   const char *encoding,

				   const char *errors)

{

    PyObject *v;

    if (!PyString_Check(str)) {

        PyErr_BadArgument();

        goto onError;

    }

    if (encoding == NULL) {

#ifdef Py_USING_UNICODE

	encoding = PyUnicode_GetDefaultEncoding();

#else

	PyErr_SetString(PyExc_ValueError, "no encoding specified");

	goto onError;

#endif

    }

    /* Decode via the codec registry */

    v = PyCodec_Decode(str, encoding, errors);

    if (v == NULL)

        goto onError;

    return v;

 onError:

    return NULL;

}

PyObject *PyString_AsDecodedString(PyObject *str,

				   const char *encoding,

				   const char *errors)

{

    PyObject *v;

    v = PyString_AsDecodedObject(str, encoding, errors);

    if (v == NULL)

        goto onError;

#ifdef Py_USING_UNICODE

    /* Convert Unicode to a string using the default encoding */

    if (PyUnicode_Check(v)) {

	PyObject *temp = v;

	v = PyUnicode_AsEncodedString(v, NULL, NULL);

	Py_DECREF(temp);

	if (v == NULL)

	    goto onError;

    }

#endif

    if (!PyString_Check(v)) {

        PyErr_Format(PyExc_TypeError,

                     "decoder did not return a string object (type=%.400s)",

                     Py_TYPE(v)->tp_name);

        Py_DECREF(v);

        goto onError;

    }

    return v;

 onError:

    return NULL;

}

PyObject *PyString_Encode(const char *s,

			  Py_ssize_t size,

			  const char *encoding,

			  const char *errors)

{

    PyObject *v, *str;

    str = PyString_FromStringAndSize(s, size);

    if (str == NULL)

	return NULL;

    v = PyString_AsEncodedString(str, encoding, errors);

    Py_DECREF(str);

    return v;

}

PyObject *PyString_AsEncodedObject(PyObject *str,

				   const char *encoding,

				   const char *errors)

{

    PyObject *v;

    if (!PyString_Check(str)) {

        PyErr_BadArgument();

        goto onError;

    }

    if (encoding == NULL) {

#ifdef Py_USING_UNICODE

	encoding = PyUnicode_GetDefaultEncoding();

#else

	PyErr_SetString(PyExc_ValueError, "no encoding specified");

	goto onError;

#endif

    }

    /* Encode via the codec registry */

    v = PyCodec_Encode(str, encoding, errors);

    if (v == NULL)

        goto onError;

    return v;

 onError:

    return NULL;

}

PyObject *PyString_AsEncodedString(PyObject *str,

				   const char *encoding,

				   const char *errors)

{

    PyObject *v;

    v = PyString_AsEncodedObject(str, encoding, errors);

    if (v == NULL)

        goto onError;

#ifdef Py_USING_UNICODE

    /* Convert Unicode to a string using the default encoding */

    if (PyUnicode_Check(v)) {

	PyObject *temp = v;

	v = PyUnicode_AsEncodedString(v, NULL, NULL);

	Py_DECREF(temp);

	if (v == NULL)

	    goto onError;

    }

#endif

    if (!PyString_Check(v)) {

        PyErr_Format(PyExc_TypeError,

                     "encoder did not return a string object (type=%.400s)",

                     Py_TYPE(v)->tp_name);

        Py_DECREF(v);

        goto onError;

    }

    return v;

 onError:

    return NULL;

}

static void

string_dealloc(PyObject *op)

{

	switch (PyString_CHECK_INTERNED(op)) {

		case SSTATE_NOT_INTERNED:

			break;