/*

Unicode implementation based on original code by Fredrik Lundh,

modified by Marc-Andre Lemburg <mal@lemburg.com>.

Major speed upgrades to the method implementations at the Reykjavik

NeedForSpeed sprint, by Fredrik Lundh and Andrew Dalke.

Copyright (c) Corporation for National Research Initiatives.

--------------------------------------------------------------------

The original string type implementation is:

Copyright (c) 1999 by Secret Labs AB

Copyright (c) 1999 by Fredrik Lundh

By obtaining, using, and/or copying this software and/or its

associated documentation, you agree that you have read, understood,

and will comply with the following terms and conditions:

Permission to use, copy, modify, and distribute this software and its

associated documentation for any purpose and without fee is hereby

granted, provided that the above copyright notice appears in all

copies, and that both that copyright notice and this permission notice

appear in supporting documentation, and that the name of Secret Labs

AB or the author not be used in advertising or publicity pertaining to

distribution of the software without specific, written prior

permission.

SECRET LABS AB AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO

THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND

FITNESS. IN NO EVENT SHALL SECRET LABS AB OR THE AUTHOR BE LIABLE FOR

ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT

OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

--------------------------------------------------------------------

*/

#define PY_SSIZE_T_CLEAN

#include "Python.h"

#include "pycore_initconfig.h"

#include "pycore_fileutils.h"

#include "pycore_object.h"

#include "pycore_pylifecycle.h"

#include "pycore_pystate.h"

#include "ucnhash.h"

#include "bytes_methods.h"

#include "stringlib/eq.h"

#ifdef MS_WINDOWS

#include <windows.h>

#endif

/* Uncomment to display statistics on interned strings at exit when

using Valgrind or Insecure++. */

/* #define INTERNED_STATS 1 */

/*[clinic input]

class str "PyObject *" "&PyUnicode_Type"

[clinic start generated code]*/

/*[clinic end generated code: output=da39a3ee5e6b4b0d input=4884c934de622cf6]*/

/*[python input]

class Py_UCS4_converter(CConverter):

type = 'Py_UCS4'

converter = 'convert_uc'

def converter_init(self):

if self.default is not unspecified:

self.c_default = ascii(self.default)

if len(self.c_default) > 4 or self.c_default[0] != "'":

self.c_default = hex(ord(self.default))

[python start generated code]*/

/*[python end generated code: output=da39a3ee5e6b4b0d input=88f5dd06cd8e7a61]*/

/* --- Globals ------------------------------------------------------------

NOTE: In the interpreter's initialization phase, some globals are currently

initialized dynamically as needed. In the process Unicode objects may

be created before the Unicode type is ready.

*/

#ifdef __cplusplus

extern "C" {

#endif

// Maximum code point of Unicode 6.0: 0x10ffff (1,114,111).

// The value must be the same in fileutils.c.

#define MAX_UNICODE 0x10ffff

#ifdef Py_DEBUG

# define _PyUnicode_CHECK(op) _PyUnicode_CheckConsistency(op, 0)

#else

# define _PyUnicode_CHECK(op) PyUnicode_Check(op)

#endif

#define _PyUnicode_UTF8(op) \

(((PyCompactUnicodeObject*)(op))->utf8)

#define PyUnicode_UTF8(op) \

(assert(_PyUnicode_CHECK(op)), \

assert(PyUnicode_IS_READY(op)), \

PyUnicode_IS_COMPACT_ASCII(op) ? \

((char*)((PyASCIIObject*)(op) + 1)) : \

_PyUnicode_UTF8(op))

#define _PyUnicode_UTF8_LENGTH(op) \

(((PyCompactUnicodeObject*)(op))->utf8_length)

#define PyUnicode_UTF8_LENGTH(op) \

(assert(_PyUnicode_CHECK(op)), \

assert(PyUnicode_IS_READY(op)), \

PyUnicode_IS_COMPACT_ASCII(op) ? \

((PyASCIIObject*)(op))->length : \

_PyUnicode_UTF8_LENGTH(op))

#define _PyUnicode_WSTR(op) \

(((PyASCIIObject*)(op))->wstr)

#define _PyUnicode_WSTR_LENGTH(op) \

(((PyCompactUnicodeObject*)(op))->wstr_length)

#define _PyUnicode_LENGTH(op) \

(((PyASCIIObject *)(op))->length)

#define _PyUnicode_STATE(op) \

(((PyASCIIObject *)(op))->state)

#define _PyUnicode_HASH(op) \

(((PyASCIIObject *)(op))->hash)

#define _PyUnicode_KIND(op) \

(assert(_PyUnicode_CHECK(op)), \

((PyASCIIObject *)(op))->state.kind)

#define _PyUnicode_GET_LENGTH(op) \

(assert(_PyUnicode_CHECK(op)), \

((PyASCIIObject *)(op))->length)

#define _PyUnicode_DATA_ANY(op) \

(((PyUnicodeObject*)(op))->data.any)

#undef PyUnicode_READY

#define PyUnicode_READY(op) \

(assert(_PyUnicode_CHECK(op)), \

(PyUnicode_IS_READY(op) ? \

0 : \

_PyUnicode_Ready(op)))

#define _PyUnicode_SHARE_UTF8(op) \

(assert(_PyUnicode_CHECK(op)), \

assert(!PyUnicode_IS_COMPACT_ASCII(op)), \

(_PyUnicode_UTF8(op) == PyUnicode_DATA(op)))

#define _PyUnicode_SHARE_WSTR(op) \

(assert(_PyUnicode_CHECK(op)), \

(_PyUnicode_WSTR(unicode) == PyUnicode_DATA(op)))

/* true if the Unicode object has an allocated UTF-8 memory block

(not shared with other data) */

#define _PyUnicode_HAS_UTF8_MEMORY(op) \

((!PyUnicode_IS_COMPACT_ASCII(op) \

&& _PyUnicode_UTF8(op) \

&& _PyUnicode_UTF8(op) != PyUnicode_DATA(op)))

/* true if the Unicode object has an allocated wstr memory block

(not shared with other data) */

#define _PyUnicode_HAS_WSTR_MEMORY(op) \

((_PyUnicode_WSTR(op) && \

(!PyUnicode_IS_READY(op) || \

_PyUnicode_WSTR(op) != PyUnicode_DATA(op))))

/* Generic helper macro to convert characters of different types.

from_type and to_type have to be valid type names, begin and end

are pointers to the source characters which should be of type

"from_type *". to is a pointer of type "to_type *" and points to the

buffer where the result characters are written to. */

#define _PyUnicode_CONVERT_BYTES(from_type, to_type, begin, end, to) \

do { \

to_type *_to = (to_type *)(to); \

const from_type *_iter = (const from_type *)(begin);\

const from_type *_end = (const from_type *)(end);\

Py_ssize_t n = (_end) - (_iter); \

const from_type *_unrolled_end = \

_iter + _Py_SIZE_ROUND_DOWN(n, 4); \

while (_iter < (_unrolled_end)) { \

_to[0] = (to_type) _iter[0]; \

_to[1] = (to_type) _iter[1]; \

_to[2] = (to_type) _iter[2]; \

_to[3] = (to_type) _iter[3]; \

_iter += 4; _to += 4; \

} \

while (_iter < (_end)) \

*_to++ = (to_type) *_iter++; \

} while (0)

#ifdef MS_WINDOWS

/* On Windows, overallocate by 50% is the best factor */

# define OVERALLOCATE_FACTOR 2

#else

/* On Linux, overallocate by 25% is the best factor */

# define OVERALLOCATE_FACTOR 4

#endif

/* This dictionary holds all interned unicode 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->state ? 2 : 0)

*/

static PyObject *interned = NULL;

/* The empty Unicode object is shared to improve performance. */

static PyObject *unicode_empty = NULL;

#define _Py_INCREF_UNICODE_EMPTY() \

do { \

if (unicode_empty != NULL) \

Py_INCREF(unicode_empty); \

else { \

unicode_empty = PyUnicode_New(0, 0); \

if (unicode_empty != NULL) { \

Py_INCREF(unicode_empty); \

assert(_PyUnicode_CheckConsistency(unicode_empty, 1)); \

} \

} \

} while (0)

#define _Py_RETURN_UNICODE_EMPTY() \

do { \

_Py_INCREF_UNICODE_EMPTY(); \

return unicode_empty; \

} while (0)

static inline void

unicode_fill(enum PyUnicode_Kind kind, void *data, Py_UCS4 value,

Py_ssize_t start, Py_ssize_t length)

{

assert(0 <= start);

assert(kind != PyUnicode_WCHAR_KIND);

switch (kind) {

case PyUnicode_1BYTE_KIND: {

assert(value <= 0xff);

Py_UCS1 ch = (unsigned char)value;

Py_UCS1 *to = (Py_UCS1 *)data + start;

memset(to, ch, length);

break;

}

case PyUnicode_2BYTE_KIND: {

assert(value <= 0xffff);

Py_UCS2 ch = (Py_UCS2)value;

Py_UCS2 *to = (Py_UCS2 *)data + start;

const Py_UCS2 *end = to + length;

for (; to < end; ++to) *to = ch;

break;

}

case PyUnicode_4BYTE_KIND: {

assert(value <= MAX_UNICODE);

Py_UCS4 ch = value;

Py_UCS4 * to = (Py_UCS4 *)data + start;

const Py_UCS4 *end = to + length;

for (; to < end; ++to) *to = ch;

break;

}

default: Py_UNREACHABLE();

}

}

/* Forward declaration */

static inline int

_PyUnicodeWriter_WriteCharInline(_PyUnicodeWriter *writer, Py_UCS4 ch);

static PyObject *

unicode_encode_utf8(PyObject *unicode, _Py_error_handler error_handler,

const char *errors);

static PyObject *

unicode_decode_utf8(const char *s, Py_ssize_t size,

_Py_error_handler error_handler, const char *errors,

Py_ssize_t *consumed);

/* List of static strings. */

static _Py_Identifier *static_strings = NULL;

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

shared as well. */

static PyObject *unicode_latin1[256] = {NULL};

/* Fast detection of the most frequent whitespace characters */

const unsigned char _Py_ascii_whitespace[] = {

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

/* case 0x0009: * CHARACTER TABULATION */

/* case 0x000A: * LINE FEED */

/* case 0x000B: * LINE TABULATION */

/* case 0x000C: * FORM FEED */

/* case 0x000D: * CARRIAGE RETURN */

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

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

/* case 0x001C: * FILE SEPARATOR */

/* case 0x001D: * GROUP SEPARATOR */

/* case 0x001E: * RECORD SEPARATOR */

/* case 0x001F: * UNIT SEPARATOR */

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

/* case 0x0020: * SPACE */

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

};

/* forward */

static PyUnicodeObject *_PyUnicode_New(Py_ssize_t length);

static PyObject* get_latin1_char(unsigned char ch);

static int unicode_modifiable(PyObject *unicode);

static PyObject *

_PyUnicode_FromUCS1(const Py_UCS1 *s, Py_ssize_t size);

static PyObject *

_PyUnicode_FromUCS2(const Py_UCS2 *s, Py_ssize_t size);

static PyObject *

_PyUnicode_FromUCS4(const Py_UCS4 *s, Py_ssize_t size);

static PyObject *

unicode_encode_call_errorhandler(const char *errors,

PyObject **errorHandler,const char *encoding, const char *reason,

PyObject *unicode, PyObject **exceptionObject,

Py_ssize_t startpos, Py_ssize_t endpos, Py_ssize_t *newpos);

static void

raise_encode_exception(PyObject **exceptionObject,

const char *encoding,

PyObject *unicode,

Py_ssize_t startpos, Py_ssize_t endpos,

const char *reason);

/* Same for linebreaks */

static const unsigned char ascii_linebreak[] = {

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

/* 0x000A, * LINE FEED */

/* 0x000B, * LINE TABULATION */

/* 0x000C, * FORM FEED */

/* 0x000D, * CARRIAGE RETURN */

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

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

/* 0x001C, * FILE SEPARATOR */

/* 0x001D, * GROUP SEPARATOR */

/* 0x001E, * RECORD SEPARATOR */

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

};

static int convert_uc(PyObject *obj, void *addr);

#include "clinic/unicodeobject.c.h"

_Py_error_handler

_Py_GetErrorHandler(const char *errors)

{

if (errors == NULL || strcmp(errors, "strict") == 0) {

return _Py_ERROR_STRICT;

}

if (strcmp(errors, "surrogateescape") == 0) {

return _Py_ERROR_SURROGATEESCAPE;

}

if (strcmp(errors, "replace") == 0) {

return _Py_ERROR_REPLACE;

}

if (strcmp(errors, "ignore") == 0) {

return _Py_ERROR_IGNORE;

}

if (strcmp(errors, "backslashreplace") == 0) {

return _Py_ERROR_BACKSLASHREPLACE;

}

if (strcmp(errors, "surrogatepass") == 0) {

return _Py_ERROR_SURROGATEPASS;

}

if (strcmp(errors, "xmlcharrefreplace") == 0) {

return _Py_ERROR_XMLCHARREFREPLACE;

}

return _Py_ERROR_OTHER;

}

static _Py_error_handler

get_error_handler_wide(const wchar_t *errors)

{

if (errors == NULL || wcscmp(errors, L"strict") == 0) {

return _Py_ERROR_STRICT;

}

if (wcscmp(errors, L"surrogateescape") == 0) {

return _Py_ERROR_SURROGATEESCAPE;

}

if (wcscmp(errors, L"replace") == 0) {

return _Py_ERROR_REPLACE;

}

if (wcscmp(errors, L"ignore") == 0) {

return _Py_ERROR_IGNORE;

}

if (wcscmp(errors, L"backslashreplace") == 0) {

return _Py_ERROR_BACKSLASHREPLACE;

}

if (wcscmp(errors, L"surrogatepass") == 0) {

return _Py_ERROR_SURROGATEPASS;

}

if (wcscmp(errors, L"xmlcharrefreplace") == 0) {

return _Py_ERROR_XMLCHARREFREPLACE;

}

return _Py_ERROR_OTHER;

}

/* The max unicode value is always 0x10FFFF while using the PEP-393 API.

This function is kept for backward compatibility with the old API. */

Py_UNICODE

PyUnicode_GetMax(void)

{

#ifdef Py_UNICODE_WIDE

return 0x10FFFF;

#else

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

not be passed to unichr. */

return 0xFFFF;

#endif

}

int

_PyUnicode_CheckConsistency(PyObject *op, int check_content)

{

#define CHECK(expr) \

do { if (!(expr)) { _PyObject_ASSERT_FAILED_MSG(op, Py_STRINGIFY(expr)); } } while (0)

PyASCIIObject *ascii;

unsigned int kind;

assert(op != NULL);

CHECK(PyUnicode_Check(op));

ascii = (PyASCIIObject *)op;

kind = ascii->state.kind;

if (ascii->state.ascii == 1 && ascii->state.compact == 1) {

CHECK(kind == PyUnicode_1BYTE_KIND);

CHECK(ascii->state.ready == 1);

}

else {

PyCompactUnicodeObject *compact = (PyCompactUnicodeObject *)op;

void *data;

if (ascii->state.compact == 1) {

data = compact + 1;

CHECK(kind == PyUnicode_1BYTE_KIND

|| kind == PyUnicode_2BYTE_KIND

|| kind == PyUnicode_4BYTE_KIND);

CHECK(ascii->state.ascii == 0);

CHECK(ascii->state.ready == 1);

CHECK(compact->utf8 != data);

}

else {

PyUnicodeObject *unicode = (PyUnicodeObject *)op;

data = unicode->data.any;

if (kind == PyUnicode_WCHAR_KIND) {

CHECK(ascii->length == 0);

CHECK(ascii->hash == -1);

CHECK(ascii->state.compact == 0);

CHECK(ascii->state.ascii == 0);

CHECK(ascii->state.ready == 0);

CHECK(ascii->state.interned == SSTATE_NOT_INTERNED);

CHECK(ascii->wstr != NULL);

CHECK(data == NULL);

CHECK(compact->utf8 == NULL);

}

else {

CHECK(kind == PyUnicode_1BYTE_KIND

|| kind == PyUnicode_2BYTE_KIND

|| kind == PyUnicode_4BYTE_KIND);

CHECK(ascii->state.compact == 0);

CHECK(ascii->state.ready == 1);

CHECK(data != NULL);

if (ascii->state.ascii) {

CHECK(compact->utf8 == data);

CHECK(compact->utf8_length == ascii->length);

}

else

CHECK(compact->utf8 != data);

}

}

if (kind != PyUnicode_WCHAR_KIND) {

if (

#if SIZEOF_WCHAR_T == 2

kind == PyUnicode_2BYTE_KIND

#else

kind == PyUnicode_4BYTE_KIND

#endif

)

{

CHECK(ascii->wstr == data);

CHECK(compact->wstr_length == ascii->length);

} else

CHECK(ascii->wstr != data);

}

if (compact->utf8 == NULL)

CHECK(compact->utf8_length == 0);

if (ascii->wstr == NULL)

CHECK(compact->wstr_length == 0);

}

/* check that the best kind is used: O(n) operation */

if (check_content && kind != PyUnicode_WCHAR_KIND) {

Py_ssize_t i;

Py_UCS4 maxchar = 0;

void *data;

Py_UCS4 ch;

data = PyUnicode_DATA(ascii);

for (i=0; i < ascii->length; i++)

{

ch = PyUnicode_READ(kind, data, i);

if (ch > maxchar)

maxchar = ch;

}

if (kind == PyUnicode_1BYTE_KIND) {

if (ascii->state.ascii == 0) {

CHECK(maxchar >= 128);

CHECK(maxchar <= 255);

}

else

CHECK(maxchar < 128);

}

else if (kind == PyUnicode_2BYTE_KIND) {

CHECK(maxchar >= 0x100);

CHECK(maxchar <= 0xFFFF);

}

else {

CHECK(maxchar >= 0x10000);

CHECK(maxchar <= MAX_UNICODE);

}

CHECK(PyUnicode_READ(kind, data, ascii->length) == 0);

}

return 1;

#undef CHECK

}

static PyObject*

unicode_result_wchar(PyObject *unicode)

{

#ifndef Py_DEBUG

Py_ssize_t len;

len = _PyUnicode_WSTR_LENGTH(unicode);

if (len == 0) {

Py_DECREF(unicode);

_Py_RETURN_UNICODE_EMPTY();

}

if (len == 1) {

wchar_t ch = _PyUnicode_WSTR(unicode)[0];

if ((Py_UCS4)ch < 256) {

PyObject *latin1_char = get_latin1_char((unsigned char)ch);

Py_DECREF(unicode);

return latin1_char;

}

}

if (_PyUnicode_Ready(unicode) < 0) {

Py_DECREF(unicode);

return NULL;

}

#else

assert(Py_REFCNT(unicode) == 1);

/* don't make the result ready in debug mode to ensure that the caller

makes the string ready before using it */

assert(_PyUnicode_CheckConsistency(unicode, 1));

#endif

return unicode;

}

static PyObject*

unicode_result_ready(PyObject *unicode)

{

Py_ssize_t length;

length = PyUnicode_GET_LENGTH(unicode);

if (length == 0) {

if (unicode != unicode_empty) {

Py_DECREF(unicode);

_Py_RETURN_UNICODE_EMPTY();

}

return unicode_empty;

}

if (length == 1) {

void *data = PyUnicode_DATA(unicode);

int kind = PyUnicode_KIND(unicode);

Py_UCS4 ch = PyUnicode_READ(kind, data, 0);

if (ch < 256) {

PyObject *latin1_char = unicode_latin1[ch];

if (latin1_char != NULL) {

if (unicode != latin1_char) {

Py_INCREF(latin1_char);

Py_DECREF(unicode);

}

return latin1_char;

}

else {

assert(_PyUnicode_CheckConsistency(unicode, 1));

Py_INCREF(unicode);

unicode_latin1[ch] = unicode;

return unicode;

}

}

}

assert(_PyUnicode_CheckConsistency(unicode, 1));

return unicode;

}

static PyObject*

unicode_result(PyObject *unicode)

{

assert(_PyUnicode_CHECK(unicode));

if (PyUnicode_IS_READY(unicode))

return unicode_result_ready(unicode);

else

return unicode_result_wchar(unicode);

}

static PyObject*

unicode_result_unchanged(PyObject *unicode)

{

if (PyUnicode_CheckExact(unicode)) {

if (PyUnicode_READY(unicode) == -1)

return NULL;

Py_INCREF(unicode);

return unicode;

}

else

/* Subtype -- return genuine unicode string with the same value. */

return _PyUnicode_Copy(unicode);

}

/* Implementation of the "backslashreplace" error handler for 8-bit encodings:

ASCII, Latin1, UTF-8, etc. */

static char*

backslashreplace(_PyBytesWriter *writer, char *str,

PyObject *unicode, Py_ssize_t collstart, Py_ssize_t collend)

{

Py_ssize_t size, i;

Py_UCS4 ch;

enum PyUnicode_Kind kind;

void *data;

assert(PyUnicode_IS_READY(unicode));

kind = PyUnicode_KIND(unicode);

data = PyUnicode_DATA(unicode);

size = 0;

/* determine replacement size */

for (i = collstart; i < collend; ++i) {

Py_ssize_t incr;

ch = PyUnicode_READ(kind, data, i);

if (ch < 0x100)

incr = 2+2;

else if (ch < 0x10000)

incr = 2+4;

else {

assert(ch <= MAX_UNICODE);

incr = 2+8;

}

if (size > PY_SSIZE_T_MAX - incr) {

PyErr_SetString(PyExc_OverflowError,

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

return NULL;

}

size += incr;

}

str = _PyBytesWriter_Prepare(writer, str, size);

if (str == NULL)

return NULL;

/* generate replacement */

for (i = collstart; i < collend; ++i) {

ch = PyUnicode_READ(kind, data, i);

*str++ = '\\';

if (ch >= 0x00010000) {

*str++ = 'U';

*str++ = Py_hexdigits[(ch>>28)&0xf];

*str++ = Py_hexdigits[(ch>>24)&0xf];

*str++ = Py_hexdigits[(ch>>20)&0xf];

*str++ = Py_hexdigits[(ch>>16)&0xf];

*str++ = Py_hexdigits[(ch>>12)&0xf];

*str++ = Py_hexdigits[(ch>>8)&0xf];

}

else if (ch >= 0x100) {

*str++ = 'u';

*str++ = Py_hexdigits[(ch>>12)&0xf];

*str++ = Py_hexdigits[(ch>>8)&0xf];

}

else

*str++ = 'x';

*str++ = Py_hexdigits[(ch>>4)&0xf];

*str++ = Py_hexdigits[ch&0xf];

}

return str;

}

/* Implementation of the "xmlcharrefreplace" error handler for 8-bit encodings:

ASCII, Latin1, UTF-8, etc. */

static char*

xmlcharrefreplace(_PyBytesWriter *writer, char *str,

PyObject *unicode, Py_ssize_t collstart, Py_ssize_t collend)

{

Py_ssize_t size, i;

Py_UCS4 ch;

enum PyUnicode_Kind kind;

void *data;

assert(PyUnicode_IS_READY(unicode));

kind = PyUnicode_KIND(unicode);

data = PyUnicode_DATA(unicode);

size = 0;

/* determine replacement size */

for (i = collstart; i < collend; ++i) {

Py_ssize_t incr;

ch = PyUnicode_READ(kind, data, i);

if (ch < 10)

incr = 2+1+1;

else if (ch < 100)

incr = 2+2+1;

else if (ch < 1000)

incr = 2+3+1;

else if (ch < 10000)

incr = 2+4+1;

else if (ch < 100000)

incr = 2+5+1;

else if (ch < 1000000)

incr = 2+6+1;

else {

assert(ch <= MAX_UNICODE);

incr = 2+7+1;

}

if (size > PY_SSIZE_T_MAX - incr) {

PyErr_SetString(PyExc_OverflowError,

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

return NULL;

}

size += incr;

}

str = _PyBytesWriter_Prepare(writer, str, size);

if (str == NULL)

return NULL;

/* generate replacement */

for (i = collstart; i < collend; ++i) {

str += sprintf(str, "&#%d;", PyUnicode_READ(kind, data, i));

}

return str;

}

/* --- Bloom Filters ----------------------------------------------------- */

/* stuff to implement simple "bloom filters" for Unicode characters.

to keep things simple, we use a single bitmask, using the least 5

bits from each unicode characters as the bit index. */

/* the linebreak mask is set up by Unicode_Init below */

#if LONG_BIT >= 128

#define BLOOM_WIDTH 128

#elif LONG_BIT >= 64

#define BLOOM_WIDTH 64

#elif LONG_BIT >= 32

#define BLOOM_WIDTH 32

#else

#error "LONG_BIT is smaller than 32"

#endif

#define BLOOM_MASK unsigned long

static BLOOM_MASK bloom_linebreak = ~(BLOOM_MASK)0;

#define BLOOM(mask, ch) ((mask & (1UL << ((ch) & (BLOOM_WIDTH - 1)))))

#define BLOOM_LINEBREAK(ch) \

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

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

static inline BLOOM_MASK

make_bloom_mask(int kind, void* ptr, Py_ssize_t len)

{

#define BLOOM_UPDATE(TYPE, MASK, PTR, LEN) \

do { \

TYPE *data = (TYPE *)PTR; \

TYPE *end = data + LEN; \

Py_UCS4 ch; \

for (; data != end; data++) { \

ch = *data; \

MASK |= (1UL << (ch & (BLOOM_WIDTH - 1))); \

} \

break; \

} while (0)

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

BLOOM_MASK mask;

mask = 0;

switch (kind) {

case PyUnicode_1BYTE_KIND:

BLOOM_UPDATE(Py_UCS1, mask, ptr, len);

break;

case PyUnicode_2BYTE_KIND:

BLOOM_UPDATE(Py_UCS2, mask, ptr, len);

break;

case PyUnicode_4BYTE_KIND:

BLOOM_UPDATE(Py_UCS4, mask, ptr, len);

break;

default:

Py_UNREACHABLE();

}

return mask;

#undef BLOOM_UPDATE

}

static int

ensure_unicode(PyObject *obj)

{

if (!PyUnicode_Check(obj)) {

PyErr_Format(PyExc_TypeError,

"must be str, not %.100s",

Py_TYPE(obj)->tp_name);

return -1;

}

return PyUnicode_READY(obj);

}

/* Compilation of templated routines */

#include "stringlib/asciilib.h"

#include "stringlib/fastsearch.h"

#include "stringlib/partition.h"

#include "stringlib/split.h"

#include "stringlib/count.h"

#include "stringlib/find.h"

#include "stringlib/find_max_char.h"

#include "stringlib/undef.h"

#include "stringlib/ucs1lib.h"

#include "stringlib/fastsearch.h"

#include "stringlib/partition.h"

#include "stringlib/split.h"

#include "stringlib/count.h"

#include "stringlib/find.h"

#include "stringlib/replace.h"

#include "stringlib/find_max_char.h"

#include "stringlib/undef.h"

#include "stringlib/ucs2lib.h"

#include "stringlib/fastsearch.h"

#include "stringlib/partition.h"

#include "stringlib/split.h"

#include "stringlib/count.h"

#include "stringlib/find.h"

#include "stringlib/replace.h"

#include "stringlib/find_max_char.h"

#include "stringlib/undef.h"

#include "stringlib/ucs4lib.h"

#include "stringlib/fastsearch.h"

#include "stringlib/partition.h"

#include "stringlib/split.h"

#include "stringlib/count.h"

#include "stringlib/find.h"

#include "stringlib/replace.h"

#include "stringlib/find_max_char.h"

#include "stringlib/undef.h"

#include "stringlib/unicodedefs.h"

#include "stringlib/fastsearch.h"

#include "stringlib/count.h"

#include "stringlib/find.h"

#include "stringlib/undef.h"

/* --- Unicode Object ----------------------------------------------------- */

static inline Py_ssize_t

findchar(const void *s, int kind,

Py_ssize_t size, Py_UCS4 ch,

int direction)

{

switch (kind) {

case PyUnicode_1BYTE_KIND:

if ((Py_UCS1) ch != ch)

return -1;

if (direction > 0)

return ucs1lib_find_char((const Py_UCS1 *) s, size, (Py_UCS1) ch);

else

return ucs1lib_rfind_char((const Py_UCS1 *) s, size, (Py_UCS1) ch);

case PyUnicode_2BYTE_KIND:

if ((Py_UCS2) ch != ch)

return -1;

if (direction > 0)

return ucs2lib_find_char((const Py_UCS2 *) s, size, (Py_UCS2) ch);

else

return ucs2lib_rfind_char((const Py_UCS2 *) s, size, (Py_UCS2) ch);

case PyUnicode_4BYTE_KIND:

if (direction > 0)

return ucs4lib_find_char((const Py_UCS4 *) s, size, ch);

else

return ucs4lib_rfind_char((const Py_UCS4 *) s, size, ch);

default:

Py_UNREACHABLE();

}

}

#ifdef Py_DEBUG

/* Fill the data of a Unicode string with invalid characters to detect bugs

earlier.

_PyUnicode_CheckConsistency(str, 1) detects invalid characters, at least for

ASCII and UCS-4 strings. U+00FF is invalid in ASCII and U+FFFFFFFF is an

invalid character in Unicode 6.0. */

static void

unicode_fill_invalid(PyObject *unicode, Py_ssize_t old_length)

{

int kind = PyUnicode_KIND(unicode);

Py_UCS1 *data = PyUnicode_1BYTE_DATA(unicode);

Py_ssize_t length = _PyUnicode_LENGTH(unicode);

if (length <= old_length)

return;

memset(data + old_length * kind, 0xff, (length - old_length) * kind);

}

#endif

static PyObject*

resize_compact(PyObject *unicode, Py_ssize_t length)

{

Py_ssize_t char_size;

Py_ssize_t struct_size;

Py_ssize_t new_size;

int share_wstr;

PyObject *new_unicode;

#ifdef Py_DEBUG

Py_ssize_t old_length = _PyUnicode_LENGTH(unicode);

#endif

assert(unicode_modifiable(unicode));

assert(PyUnicode_IS_READY(unicode));

assert(PyUnicode_IS_COMPACT(unicode));

char_size = PyUnicode_KIND(unicode);

if (PyUnicode_IS_ASCII(unicode))

struct_size = sizeof(PyASCIIObject);

else

struct_size = sizeof(PyCompactUnicodeObject);

share_wstr = _PyUnicode_SHARE_WSTR(unicode);

if (length > ((PY_SSIZE_T_MAX - struct_size) / char_size - 1)) {

PyErr_NoMemory();

return NULL;

}

new_size = (struct_size + (length + 1) * char_size);

if (_PyUnicode_HAS_UTF8_MEMORY(unicode)) {

PyObject_DEL(_PyUnicode_UTF8(unicode));

_PyUnicode_UTF8(unicode) = NULL;

_PyUnicode_UTF8_LENGTH(unicode) = 0;

}

_Py_DEC_REFTOTAL;

_Py_ForgetReference(unicode);

new_unicode = (PyObject *)PyObject_REALLOC(unicode, new_size);

if (new_unicode == NULL) {