#define PY_SSIZE_T_CLEAN

#include "Python.h"

#include "bytes_methods.h"

#include "unicodeobject.h"

#include "ucnhash.h"

#ifdef MS_WINDOWS

#include <windows.h>

#define PyUnicode_MAXFREELIST 1024

#define KEEPALIVE_SIZE_LIMIT 9

#ifdef WORDS_BIGENDIAN

# define BYTEORDER_IS_BIG_ENDIAN

# define BYTEORDER_IS_LITTLE_ENDIAN

#ifdef __cplusplus

extern "C" {

static PyObject *interned;

static PyUnicodeObject *free_list;

static int numfree;

static PyUnicodeObject *unicode_empty;

static PyUnicodeObject *unicode_latin1[256];

static const char unicode_default_encoding[] = "utf-8";

const unsigned char _Py_ascii_whitespace[] = {

0, 0, 0, 0, 0, 0, 0, 0,

0, 1, 1, 1, 1, 1, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 1, 1, 1, 1,

1, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0

};

static unsigned char ascii_linebreak[] = {

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 1, 0, 0, 1, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 1, 1, 1, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0

};

PyUnicode_GetMax(void)

{

#ifdef Py_UNICODE_WIDE

return 0x10FFFF;

/* This is actually an illegal character, so it should

return 0xFFFF;

}

#define BLOOM_MASK unsigned long

static BLOOM_MASK bloom_linebreak;

#define BLOOM(mask, ch) ((mask & (1 << ((ch) & 0x1F))))

#define BLOOM_LINEBREAK(ch) \

((ch) < 128U ? ascii_linebreak[(ch)] : \

(BLOOM(bloom_linebreak, (ch)) && Py_UNICODE_ISLINEBREAK(ch)))

Py_LOCAL_INLINE(BLOOM_MASK) make_bloom_mask(Py_UNICODE* ptr, Py_ssize_t len)

{

/* calculate simple bloom-style bitmask for a given unicode string */

long mask;

Py_ssize_t i;

mask = 0;

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

mask |= (1 << (ptr[i] & 0x1F));

return mask;

}

Py_LOCAL_INLINE(int) unicode_member(Py_UNICODE chr, Py_UNICODE* set, Py_ssize_t setlen)

{

Py_ssize_t i;

for (i = 0; i < setlen; i++)

if (set[i] == chr)

return 1;

return 0;

}

#define BLOOM_MEMBER(mask, chr, set, setlen) \

BLOOM(mask, chr) && unicode_member(chr, set, setlen)

int unicode_resize(register PyUnicodeObject *unicode,

Py_ssize_t length)

{

void *oldstr;

/* Shortcut if there's nothing much to do. */

if (unicode->length == length)

goto reset;

/* Resizing shared object (unicode_empty or single character

if (unicode == unicode_empty ||

(unicode->length == 1 &&

unicode->str[0] < 256U &&

unicode_latin1[unicode->str[0]] == unicode)) {

PyErr_SetString(PyExc_SystemError,

"can't resize shared str objects");

return -1;

}

/* We allocate one more byte to make sure the string is Ux0000 terminated.

oldstr = unicode->str;

unicode->str = PyObject_REALLOC(unicode->str,

sizeof(Py_UNICODE) * (length + 1));

if (!unicode->str) {

unicode->str = (Py_UNICODE *)oldstr;

PyErr_NoMemory();

return -1;

}

unicode->str[length] = 0;

unicode->length = length;

reset:

/* Reset the object caches */

if (unicode->defenc) {

Py_DECREF(unicode->defenc);

unicode->defenc = NULL;

}

unicode->hash = -1;

return 0;

}

PyUnicodeObject *_PyUnicode_New(Py_ssize_t length)

{

register PyUnicodeObject *unicode;

/* Optimization for empty strings */

if (length == 0 && unicode_empty != NULL) {

Py_INCREF(unicode_empty);

return unicode_empty;

}

/* Ensure we won't overflow the size. */

if (length > ((PY_SSIZE_T_MAX / sizeof(Py_UNICODE)) - 1)) {

return (PyUnicodeObject *)PyErr_NoMemory();

}

/* Unicode freelist & memory allocation */

if (free_list) {

unicode = free_list;

free_list = *(PyUnicodeObject **)unicode;

numfree--;

if (unicode->str) {

/* Keep-Alive optimization: we only upsize the buffer,

if ((unicode->length < length) &&

unicode_resize(unicode, length) < 0) {

PyObject_DEL(unicode->str);

unicode->str = NULL;

}

}

else {

size_t new_size = sizeof(Py_UNICODE) * ((size_t)length + 1);

unicode->str = (Py_UNICODE*) PyObject_MALLOC(new_size);

}

PyObject_INIT(unicode, &PyUnicode_Type);

}

else {

size_t new_size;

unicode = PyObject_New(PyUnicodeObject, &PyUnicode_Type);

if (unicode == NULL)

return NULL;

new_size = sizeof(Py_UNICODE) * ((size_t)length + 1);

unicode->str = (Py_UNICODE*) PyObject_MALLOC(new_size);

}

if (!unicode->str) {

PyErr_NoMemory();

goto onError;

}

/* Initialize the first element to guard against cases where

unicode->str[0] = 0;

unicode->str[length] = 0;

unicode->length = length;

unicode->hash = -1;

unicode->state = 0;

unicode->defenc = NULL;

return unicode;

onError:

/* XXX UNREF/NEWREF interface should be more symmetrical */

_Py_DEC_REFTOTAL;

_Py_ForgetReference((PyObject *)unicode);

PyObject_Del(unicode);

return NULL;

}

void unicode_dealloc(register PyUnicodeObject *unicode)

{

switch (PyUnicode_CHECK_INTERNED(unicode)) {

case SSTATE_NOT_INTERNED:

break;

case SSTATE_INTERNED_MORTAL:

/* revive dead object temporarily for DelItem */

Py_REFCNT(unicode) = 3;

if (PyDict_DelItem(interned, (PyObject *)unicode) != 0)

Py_FatalError(

"deletion of interned string failed");

break;

case SSTATE_INTERNED_IMMORTAL:

Py_FatalError("Immortal interned string died.");

default:

Py_FatalError("Inconsistent interned string state.");

}

if (PyUnicode_CheckExact(unicode) &&

numfree < PyUnicode_MAXFREELIST) {

/* Keep-Alive optimization */

if (unicode->length >= KEEPALIVE_SIZE_LIMIT) {

PyObject_DEL(unicode->str);

unicode->str = NULL;

unicode->length = 0;

}

if (unicode->defenc) {

Py_DECREF(unicode->defenc);

unicode->defenc = NULL;

}

/* Add to free list */

*(PyUnicodeObject **)unicode = free_list;

free_list = unicode;

numfree++;

}

else {

PyObject_DEL(unicode->str);

Py_XDECREF(unicode->defenc);

Py_TYPE(unicode)->tp_free((PyObject *)unicode);

}

}

int _PyUnicode_Resize(PyUnicodeObject **unicode, Py_ssize_t length)

{

register PyUnicodeObject *v;

/* Argument checks */

if (unicode == NULL) {

PyErr_BadInternalCall();

return -1;

}

v = *unicode;

if (v == NULL || !PyUnicode_Check(v) || Py_REFCNT(v) != 1 || length < 0) {

PyErr_BadInternalCall();

return -1;

}

/* Resizing unicode_empty and single character objects is not

if (v->length != length &&

(v == unicode_empty || v->length == 1)) {

PyUnicodeObject *w = _PyUnicode_New(length);

if (w == NULL)

return -1;

Py_UNICODE_COPY(w->str, v->str,

length < v->length ? length : v->length);

Py_DECREF(*unicode);

*unicode = w;

return 0;

}

/* Note that we don't have to modify *unicode for unshared Unicode

return unicode_resize(v, length);

}

int PyUnicode_Resize(PyObject **unicode, Py_ssize_t length)

{

return _PyUnicode_Resize((PyUnicodeObject **)unicode, length);

}

PyObject *PyUnicode_FromUnicode(const Py_UNICODE *u,

Py_ssize_t size)

{

PyUnicodeObject *unicode;

/* If the Unicode data is known at construction time, we can apply

if (u != NULL) {

/* Optimization for empty strings */

if (size == 0 && unicode_empty != NULL) {

Py_INCREF(unicode_empty);

return (PyObject *)unicode_empty;

}

/* Single character Unicode objects in the Latin-1 range are

if (size == 1 && *u < 256) {

unicode = unicode_latin1[*u];

if (!unicode) {

unicode = _PyUnicode_New(1);

if (!unicode)

return NULL;

unicode->str[0] = *u;

unicode_latin1[*u] = unicode;

}

Py_INCREF(unicode);

return (PyObject *)unicode;

}

}

unicode = _PyUnicode_New(size);

if (!unicode)

return NULL;

/* Copy the Unicode data into the new object */

if (u != NULL)

Py_UNICODE_COPY(unicode->str, u, size);

return (PyObject *)unicode;

}

PyObject *PyUnicode_FromStringAndSize(const char *u, Py_ssize_t size)

{

PyUnicodeObject *unicode;

if (size < 0) {

PyErr_SetString(PyExc_SystemError,

"Negative size passed to PyUnicode_FromStringAndSize");

return NULL;

}

/* If the Unicode data is known at construction time, we can apply

if (u != NULL) {

/* Optimization for empty strings */

if (size == 0 && unicode_empty != NULL) {

Py_INCREF(unicode_empty);

return (PyObject *)unicode_empty;

}

/* Single characters are shared when using this constructor.

if (size == 1 && Py_CHARMASK(*u) < 128) {

unicode = unicode_latin1[Py_CHARMASK(*u)];

if (!unicode) {

unicode = _PyUnicode_New(1);

if (!unicode)

return NULL;

unicode->str[0] = Py_CHARMASK(*u);

unicode_latin1[Py_CHARMASK(*u)] = unicode;

}

Py_INCREF(unicode);

return (PyObject *)unicode;

}

return PyUnicode_DecodeUTF8(u, size, NULL);

}

unicode = _PyUnicode_New(size);

if (!unicode)

return NULL;

return (PyObject *)unicode;

}

PyObject *PyUnicode_FromString(const char *u)

{

size_t size = strlen(u);

if (size > PY_SSIZE_T_MAX) {

PyErr_SetString(PyExc_OverflowError, "input too long");

return NULL;

}

return PyUnicode_FromStringAndSize(u, size);

}

#ifdef HAVE_WCHAR_H

PyObject *PyUnicode_FromWideChar(register const wchar_t *w,

Py_ssize_t size)

{

PyUnicodeObject *unicode;

if (w == NULL) {

if (size == 0)

return PyUnicode_FromStringAndSize(NULL, 0);

PyErr_BadInternalCall();

return NULL;

}

if (size == -1) {

size = wcslen(w);

}

unicode = _PyUnicode_New(size);

if (!unicode)

return NULL;

/* Copy the wchar_t data into the new object */

#ifdef HAVE_USABLE_WCHAR_T

memcpy(unicode->str, w, size * sizeof(wchar_t));

{

register Py_UNICODE *u;

register Py_ssize_t i;

u = PyUnicode_AS_UNICODE(unicode);

for (i = size; i > 0; i--)

*u++ = *w++;

}

return (PyObject *)unicode;

}

static void

makefmt(char *fmt, int longflag, int size_tflag, int zeropad, int width, int precision, char c)

{

*fmt++ = '%';

if (width) {

if (zeropad)

*fmt++ = '0';

fmt += sprintf(fmt, "%d", width);

}

if (precision)

fmt += sprintf(fmt, ".%d", precision);

if (longflag)

*fmt++ = 'l';

else if (size_tflag) {

char *f = PY_FORMAT_SIZE_T;

while (*f)

*fmt++ = *f++;

}

*fmt++ = c;

*fmt = '\0';

}

#define appendstring(string) {for (copy = string;*copy;) *s++ = *copy++;}

PyObject *

PyUnicode_FromFormatV(const char *format, va_list vargs)

{

va_list count;

Py_ssize_t callcount = 0;

PyObject **callresults = NULL;

PyObject **callresult = NULL;

Py_ssize_t n = 0;

int width = 0;

int precision = 0;

int zeropad;

const char* f;

Py_UNICODE *s;

PyObject *string;

/* used by sprintf */

char buffer[21];

/* use abuffer instead of buffer, if we need more space

char *abuffer = NULL;

char *realbuffer;

Py_ssize_t abuffersize = 0;

char fmt[60]; /* should be enough for %0width.precisionld */

const char *copy;

#ifdef VA_LIST_IS_ARRAY

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

#ifdef __va_copy

__va_copy(count, vargs);

count = vargs;

/* step 1: count the number of %S/%R/%A format specifications

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

if (*f == '%' && (*(f+1)=='S' || *(f+1)=='R' || *(f+1)=='A'))

++callcount;

}

/* step 2: allocate memory for the results of

if (callcount) {

callresults = PyObject_Malloc(sizeof(PyObject *)*callcount);

if (!callresults) {

PyErr_NoMemory();

return NULL;

}

callresult = callresults;

}

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

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

if (*f == '%') {

const char* p = f;

width = 0;

while (ISDIGIT((unsigned)*f))

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

while (*++f && *f != '%' && !ISALPHA((unsigned)*f))

;

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

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

if (width < 20)

width = 20;

n += width;

if (abuffersize < width)

abuffersize = width;

break;

case 's':

{

/* UTF-8 */

unsigned char*s;

s = va_arg(count, unsigned char*);

while (*s) {

if (*s < 128) {

n++; s++;

} else if (*s < 0xc0) {

/* invalid UTF-8 */

n++; s++;

} else if (*s < 0xc0) {

n++;

s++; if(!*s)break;

s++;

} else if (*s < 0xe0) {

n++;

s++; if(!*s)break;

s++; if(!*s)break;

s++;

} else {

#ifdef Py_UNICODE_WIDE

n++;

n+=2;

s++; if(!*s)break;

s++; if(!*s)break;

s++; if(!*s)break;

s++;

}

}

break;

}

case 'U':

{

PyObject *obj = va_arg(count, PyObject *);

assert(obj && PyUnicode_Check(obj));

n += PyUnicode_GET_SIZE(obj);

break;

}

case 'V':

{

PyObject *obj = va_arg(count, PyObject *);

const char *str = va_arg(count, const char *);

assert(obj || str);

assert(!obj || PyUnicode_Check(obj));

if (obj)

n += PyUnicode_GET_SIZE(obj);

else

n += strlen(str);

break;

}

case 'S':

{

PyObject *obj = va_arg(count, PyObject *);

PyObject *str;

assert(obj);

str = PyObject_Str(obj);

if (!str)

goto fail;

n += PyUnicode_GET_SIZE(str);

/* Remember the str and switch to the next slot */

*callresult++ = str;

break;

}

case 'R':

{

PyObject *obj = va_arg(count, PyObject *);

PyObject *repr;

assert(obj);

repr = PyObject_Repr(obj);

if (!repr)

goto fail;

n += PyUnicode_GET_SIZE(repr);

/* Remember the repr and switch to the next slot */

*callresult++ = repr;

break;

}

case 'A':

{

PyObject *obj = va_arg(count, PyObject *);

PyObject *ascii;

assert(obj);

ascii = PyObject_ASCII(obj);

if (!ascii)

goto fail;

n += PyUnicode_GET_SIZE(ascii);

/* Remember the repr and switch to the next slot */

*callresult++ = ascii;

break;

}

case 'p':

(void) va_arg(count, int);

/* maximum 64-bit pointer representation:

n += 19;

break;

default:

/* if we stumble upon an unknown

n += strlen(p);

goto expand;

}

} else

n++;

}

expand:

if (abuffersize > 20) {

abuffer = PyObject_Malloc(abuffersize);

if (!abuffer) {

PyErr_NoMemory();

goto fail;

}

realbuffer = abuffer;

}

else

realbuffer = buffer;

/* step 4: fill the buffer */

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

string = PyUnicode_FromUnicode(NULL, n);

if (!string)

goto fail;

s = PyUnicode_AS_UNICODE(string);

callresult = callresults;

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

if (*f == '%') {

const char* p = f++;

int longflag = 0;

int size_tflag = 0;

zeropad = (*f == '0');

/* parse the width.precision part */

width = 0;

while (ISDIGIT((unsigned)*f))

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

precision = 0;

if (*f == '.') {

f++;

while (ISDIGIT((unsigned)*f))

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

}

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

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':

makefmt(fmt, longflag, size_tflag, zeropad, width, precision, 'd');

if (longflag)

sprintf(realbuffer, fmt, va_arg(vargs, long));

else if (size_tflag)

sprintf(realbuffer, fmt, va_arg(vargs, Py_ssize_t));

else

sprintf(realbuffer, fmt, va_arg(vargs, int));

appendstring(realbuffer);

break;

case 'u':

makefmt(fmt, longflag, size_tflag, zeropad, width, precision, 'u');

if (longflag)

sprintf(realbuffer, fmt, va_arg(vargs, unsigned long));

else if (size_tflag)

sprintf(realbuffer, fmt, va_arg(vargs, size_t));

else

sprintf(realbuffer, fmt, va_arg(vargs, unsigned int));

appendstring(realbuffer);

break;

case 'i':

makefmt(fmt, 0, 0, zeropad, width, precision, 'i');

sprintf(realbuffer, fmt, va_arg(vargs, int));

appendstring(realbuffer);

break;

case 'x':

makefmt(fmt, 0, 0, zeropad, width, precision, 'x');

sprintf(realbuffer, fmt, va_arg(vargs, int));

appendstring(realbuffer);

break;

case 's':

{

/* Parameter must be UTF-8 encoded.

PyObject *u;

p = va_arg(vargs, char*);

u = PyUnicode_DecodeUTF8(p, strlen(p),

"replace");

if (!u)

goto fail;

Py_UNICODE_COPY(s, PyUnicode_AS_UNICODE(u),

PyUnicode_GET_SIZE(u));

s += PyUnicode_GET_SIZE(u);

Py_DECREF(u);

break;

}

case 'U':

{

PyObject *obj = va_arg(vargs, PyObject *);

Py_ssize_t size = PyUnicode_GET_SIZE(obj);

Py_UNICODE_COPY(s, PyUnicode_AS_UNICODE(obj), size);

s += size;

break;

}

case 'V':

{

PyObject *obj = va_arg(vargs, PyObject *);

const char *str = va_arg(vargs, const char *);

if (obj) {

Py_ssize_t size = PyUnicode_GET_SIZE(obj);

Py_UNICODE_COPY(s, PyUnicode_AS_UNICODE(obj), size);

s += size;

} else {

appendstring(str);

}

break;

}

case 'S':

case 'R':

{

Py_UNICODE *ucopy;

Py_ssize_t usize;

Py_ssize_t upos;

/* unused, since we already have the result */

(void) va_arg(vargs, PyObject *);

ucopy = PyUnicode_AS_UNICODE(*callresult);

usize = PyUnicode_GET_SIZE(*callresult);

for (upos = 0; upos<usize;)

*s++ = ucopy[upos++];

/* We're done with the unicode()/repr() => forget it */

Py_DECREF(*callresult);

/* switch to next unicode()/repr() result */

++callresult;

break;

}

case 'p':

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

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

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

buffer[1] = 'x';

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

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

buffer[0] = '0';

buffer[1] = 'x';

}

appendstring(buffer);

break;

case '%':

*s++ = '%';

break;

default:

appendstring(p);

goto end;

}

} else

*s++ = *f;

}

end:

if (callresults)

PyObject_Free(callresults);

if (abuffer)

PyObject_Free(abuffer);

PyUnicode_Resize(&string, s - PyUnicode_AS_UNICODE(string));

return string;

fail:

if (callresults) {

PyObject **callresult2 = callresults;

while (callresult2 < callresult) {

Py_DECREF(*callresult2);