/*

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.

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

*/

#include "Python.h"

#include "pycore_abstract.h" // _PyIndex_Check()

#include "pycore_bytes_methods.h" // _Py_bytes_lower()

#include "pycore_bytesobject.h" // _PyBytes_Repeat()

#include "pycore_ceval.h" // _PyEval_GetBuiltin()

#include "pycore_codecs.h" // _PyCodec_Lookup()

#include "pycore_critical_section.h" // Py_*_CRITICAL_SECTION_SEQUENCE_FAST

#include "pycore_format.h" // F_LJUST

#include "pycore_freelist.h" // _Py_FREELIST_FREE(), _Py_FREELIST_POP()

#include "pycore_initconfig.h" // _PyStatus_OK()

#include "pycore_interp.h" // PyInterpreterState.fs_codec

#include "pycore_long.h" // _PyLong_FormatWriter()

#include "pycore_object.h" // _PyObject_GC_TRACK(), _Py_FatalRefcountError()

#include "pycore_pathconfig.h" // _Py_DumpPathConfig()

#include "pycore_pyerrors.h" // _PyUnicodeTranslateError_Create()

#include "pycore_pyhash.h" // _Py_HashSecret_t

#include "pycore_pylifecycle.h" // _Py_SetFileSystemEncoding()

#include "pycore_pystate.h" // _PyInterpreterState_GET()

#include "pycore_ucnhash.h" // _PyUnicode_Name_CAPI

#include "pycore_unicodeobject.h" // struct _Py_unicode_state

#include "pycore_unicodeobject_generated.h" // _PyUnicode_InitStaticStrings()

#include "stringlib/eq.h" // unicode_eq()

#include <stddef.h> // ptrdiff_t

#ifdef MS_WINDOWS

#include <windows.h>

#endif

#ifdef HAVE_NON_UNICODE_WCHAR_T_REPRESENTATION

# include "pycore_fileutils.h" // _Py_LocaleUsesNonUnicodeWchar()

#endif

/* Uncomment to display statistics on interned strings at exit

in _PyUnicode_ClearInterned(). */

/* #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.

*/

#define MAX_UNICODE _Py_MAX_UNICODE

#define ensure_unicode _PyUnicode_EnsureUnicode

#ifdef Py_DEBUG

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

#else

# define _PyUnicode_CHECK(op) PyUnicode_Check(op)

#endif

static inline char* _PyUnicode_UTF8(PyObject *op)

{

return FT_ATOMIC_LOAD_PTR_ACQUIRE(_PyCompactUnicodeObject_CAST(op)->utf8);

}

static inline char* PyUnicode_UTF8(PyObject *op)

{

assert(_PyUnicode_CHECK(op));

if (PyUnicode_IS_COMPACT_ASCII(op)) {

return ((char*)(_PyASCIIObject_CAST(op) + 1));

}

else {

return _PyUnicode_UTF8(op);

}

}

static inline void PyUnicode_SET_UTF8(PyObject *op, char *utf8)

{

FT_ATOMIC_STORE_PTR_RELEASE(_PyCompactUnicodeObject_CAST(op)->utf8, utf8);

}

static inline Py_ssize_t PyUnicode_UTF8_LENGTH(PyObject *op)

{

assert(_PyUnicode_CHECK(op));

if (PyUnicode_IS_COMPACT_ASCII(op)) {

return _PyASCIIObject_CAST(op)->length;

}

else {

return _PyCompactUnicodeObject_CAST(op)->utf8_length;

}

}

static inline void PyUnicode_SET_UTF8_LENGTH(PyObject *op, Py_ssize_t length)

{

_PyCompactUnicodeObject_CAST(op)->utf8_length = length;

}

#define _PyUnicode_LENGTH(op) \

(_PyASCIIObject_CAST(op)->length)

#define _PyUnicode_STATE(op) \

(_PyASCIIObject_CAST(op)->state)

#define _PyUnicode_HASH(op) \

(_PyASCIIObject_CAST(op)->hash)

#define PyUnicode_HASH PyUnstable_Unicode_GET_CACHED_HASH

static inline void PyUnicode_SET_HASH(PyObject *op, Py_hash_t hash)

{

FT_ATOMIC_STORE_SSIZE_RELAXED(_PyASCIIObject_CAST(op)->hash, hash);

}

#define _PyUnicode_DATA_ANY(op) \

(_PyUnicodeObject_CAST(op)->data.any)

static inline int _PyUnicode_SHARE_UTF8(PyObject *op)

{

assert(_PyUnicode_CHECK(op));

assert(!PyUnicode_IS_COMPACT_ASCII(op));

return (_PyUnicode_UTF8(op) == PyUnicode_DATA(op));

}

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

(not shared with other data) */

static inline int _PyUnicode_HAS_UTF8_MEMORY(PyObject *op)

{

return (!PyUnicode_IS_COMPACT_ASCII(op)

&& _PyUnicode_UTF8(op) != NULL

&& _PyUnicode_UTF8(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)

#define LATIN1 _Py_LATIN1_CHR

#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

/* Forward declaration */

static inline int

_PyUnicodeWriter_WriteCharInline(_PyUnicodeWriter *writer, Py_UCS4 ch);

static inline void

_PyUnicodeWriter_InitWithBuffer(_PyUnicodeWriter *writer, PyObject *buffer);

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);

static int

unicode_decode_utf8_writer(_PyUnicodeWriter *writer,

const char *s, Py_ssize_t size,

_Py_error_handler error_handler, const char *errors,

Py_ssize_t *consumed);

#ifdef Py_DEBUG

static inline int unicode_is_finalizing(void);

static int unicode_is_singleton(PyObject *unicode);

#endif

// Return a reference to the immortal empty string singleton.

static inline PyObject* unicode_get_empty(void)

{

_Py_DECLARE_STR(empty, "");

return &_Py_STR(empty);

}

/* This dictionary holds per-interpreter interned strings.

* See InternalDocs/string_interning.md for details.

*/

static inline PyObject *get_interned_dict(PyInterpreterState *interp)

{

return _Py_INTERP_CACHED_OBJECT(interp, interned_strings);

}

/* This hashtable holds statically allocated interned strings.

* See InternalDocs/string_interning.md for details.

*/

#define INTERNED_STRINGS _PyRuntime.cached_objects.interned_strings

/* Get number of all interned strings for the current interpreter. */

Py_ssize_t

_PyUnicode_InternedSize(void)

{

PyObject *dict = get_interned_dict(_PyInterpreterState_GET());

return _Py_hashtable_len(INTERNED_STRINGS) + PyDict_GET_SIZE(dict);

}

/* Get number of immortal interned strings for the current interpreter. */

Py_ssize_t

_PyUnicode_InternedSize_Immortal(void)

{

PyObject *dict = get_interned_dict(_PyInterpreterState_GET());

PyObject *key, *value;

Py_ssize_t pos = 0;

Py_ssize_t count = 0;

// It's tempting to keep a count and avoid a loop here. But, this function

// is intended for refleak tests. It spends extra work to report the true

// value, to help detect bugs in optimizations.

while (PyDict_Next(dict, &pos, &key, &value)) {

assert(PyUnicode_CHECK_INTERNED(key) != SSTATE_INTERNED_IMMORTAL_STATIC);

if (PyUnicode_CHECK_INTERNED(key) == SSTATE_INTERNED_IMMORTAL) {

count++;

}

}

return _Py_hashtable_len(INTERNED_STRINGS) + count;

}

static Py_hash_t unicode_hash(PyObject *);

static Py_uhash_t

hashtable_unicode_hash(const void *key)

{

return unicode_hash((PyObject *)key);

}

static int

hashtable_unicode_compare(const void *key1, const void *key2)

{

PyObject *obj1 = (PyObject *)key1;

PyObject *obj2 = (PyObject *)key2;

if (obj1 != NULL && obj2 != NULL) {

return unicode_eq(obj1, obj2);

}

else {

return obj1 == obj2;

}

}

/* Return true if this interpreter should share the main interpreter's

intern_dict. That's important for interpreters which load basic

single-phase init extension modules (m_size == -1). There could be interned

immortal strings that are shared between interpreters, due to the

PyDict_Update(mdict, m_copy) call in import_find_extension().

It's not safe to deallocate those strings until all interpreters that

potentially use them are freed. By storing them in the main interpreter, we

ensure they get freed after all other interpreters are freed.

*/

static bool

has_shared_intern_dict(PyInterpreterState *interp)

{

PyInterpreterState *main_interp = _PyInterpreterState_Main();

return interp != main_interp && interp->feature_flags & Py_RTFLAGS_USE_MAIN_OBMALLOC;

}

static int

init_interned_dict(PyInterpreterState *interp)

{

assert(get_interned_dict(interp) == NULL);

PyObject *interned;

if (has_shared_intern_dict(interp)) {

interned = get_interned_dict(_PyInterpreterState_Main());

Py_INCREF(interned);

}

else {

interned = PyDict_New();

if (interned == NULL) {

return -1;

}

}

_Py_INTERP_CACHED_OBJECT(interp, interned_strings) = interned;

return 0;

}

static void

clear_interned_dict(PyInterpreterState *interp)

{

PyObject *interned = get_interned_dict(interp);

if (interned != NULL) {

if (!has_shared_intern_dict(interp)) {

// only clear if the dict belongs to this interpreter

PyDict_Clear(interned);

}

Py_DECREF(interned);

_Py_INTERP_CACHED_OBJECT(interp, interned_strings) = NULL;

}

}

static PyStatus

init_global_interned_strings(PyInterpreterState *interp)

{

assert(INTERNED_STRINGS == NULL);

_Py_hashtable_allocator_t hashtable_alloc = {PyMem_RawMalloc, PyMem_RawFree};

INTERNED_STRINGS = _Py_hashtable_new_full(

hashtable_unicode_hash,

hashtable_unicode_compare,

// Objects stored here are immortal and statically allocated,

// so we don't need key_destroy_func & value_destroy_func:

NULL,

NULL,

&hashtable_alloc

);

if (INTERNED_STRINGS == NULL) {

PyErr_Clear();

return _PyStatus_ERR("failed to create global interned dict");

}

/* Intern statically allocated string identifiers, deepfreeze strings,

* and one-byte latin-1 strings.

* This must be done before any module initialization so that statically

* allocated string identifiers are used instead of heap allocated strings.

* Deepfreeze uses the interned identifiers if present to save space

* else generates them and they are interned to speed up dict lookups.

*/

_PyUnicode_InitStaticStrings(interp);

for (int i = 0; i < 256; i++) {

PyObject *s = LATIN1(i);

_PyUnicode_InternStatic(interp, &s);

assert(s == LATIN1(i));

}

#ifdef Py_DEBUG

assert(_PyUnicode_CheckConsistency(&_Py_STR(empty), 1));

for (int i = 0; i < 256; i++) {

assert(_PyUnicode_CheckConsistency(LATIN1(i), 1));

}

#endif

return _PyStatus_OK();

}

static void clear_global_interned_strings(void)

{

if (INTERNED_STRINGS != NULL) {

_Py_hashtable_destroy(INTERNED_STRINGS);

INTERNED_STRINGS = NULL;

}

}

#define _Py_RETURN_UNICODE_EMPTY() \

do { \

return unicode_get_empty(); \

} while (0)

/* 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 PyObject* get_latin1_char(unsigned char ch);

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);

struct encoding_map;

#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;

}

static inline int

unicode_check_encoding_errors(const char *encoding, const char *errors)

{

if (encoding == NULL && errors == NULL) {

return 0;

}

PyInterpreterState *interp = _PyInterpreterState_GET();

#ifndef Py_DEBUG

/* In release mode, only check in development mode (-X dev) */

if (!_PyInterpreterState_GetConfig(interp)->dev_mode) {

return 0;

}

#else

/* Always check in debug mode */

#endif

/* Avoid calling _PyCodec_Lookup() and PyCodec_LookupError() before the

codec registry is ready: before_PyUnicode_InitEncodings() is called. */

if (!interp->unicode.fs_codec.encoding) {

return 0;

}

/* Disable checks during Python finalization. For example, it allows to

call _PyObject_Dump() during finalization for debugging purpose. */

if (_PyInterpreterState_GetFinalizing(interp) != NULL) {

return 0;

}

if (encoding != NULL

// Fast path for the most common built-in encodings. Even if the codec

// is cached, _PyCodec_Lookup() decodes the bytes string from UTF-8 to

// create a temporary Unicode string (the key in the cache).

&& strcmp(encoding, "utf-8") != 0

&& strcmp(encoding, "utf8") != 0

&& strcmp(encoding, "ascii") != 0)

{

PyObject *handler = _PyCodec_Lookup(encoding);

if (handler == NULL) {

return -1;

}

Py_DECREF(handler);

}

if (errors != NULL

// Fast path for the most common built-in error handlers.

&& strcmp(errors, "strict") != 0

&& strcmp(errors, "ignore") != 0

&& strcmp(errors, "replace") != 0

&& strcmp(errors, "surrogateescape") != 0

&& strcmp(errors, "surrogatepass") != 0)

{

PyObject *handler = PyCodec_LookupError(errors);

if (handler == NULL) {

return -1;

}

Py_DECREF(handler);

}

return 0;

}

int

_PyUnicode_CheckConsistency(PyObject *op, int check_content)

{

#define CHECK(expr) \

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

assert(op != NULL);

CHECK(PyUnicode_Check(op));

PyASCIIObject *ascii = _PyASCIIObject_CAST(op);

int kind = ascii->state.kind;

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

CHECK(kind == PyUnicode_1BYTE_KIND);

}

else {

PyCompactUnicodeObject *compact = _PyCompactUnicodeObject_CAST(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(_PyUnicode_UTF8(op) != data);

}

else {

PyUnicodeObject *unicode = _PyUnicodeObject_CAST(op);

data = unicode->data.any;

CHECK(kind == PyUnicode_1BYTE_KIND

|| kind == PyUnicode_2BYTE_KIND

|| kind == PyUnicode_4BYTE_KIND);

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

CHECK(data != NULL);

if (ascii->state.ascii) {

CHECK(_PyUnicode_UTF8(op) == data);

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

}

else {

CHECK(_PyUnicode_UTF8(op) != data);

}

}

#ifndef Py_GIL_DISABLED

if (_PyUnicode_UTF8(op) == NULL)

CHECK(compact->utf8_length == 0);

#endif

}

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

if (check_content) {

Py_ssize_t i;

Py_UCS4 maxchar = 0;

const 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);

}

/* Check interning state */

#ifdef Py_DEBUG

// Note that we do not check `_Py_IsImmortal(op)`, since stable ABI

// extensions can make immortal strings mortal (but with a high enough

// refcount).

// The other way is extremely unlikely (worth a potential failed assertion

// in a debug build), so we do check `!_Py_IsImmortal(op)`.

switch (PyUnicode_CHECK_INTERNED(op)) {

case SSTATE_NOT_INTERNED:

if (ascii->state.statically_allocated) {

// This state is for two exceptions:

// - strings are currently checked before they're interned

// - the 256 one-latin1-character strings

// are static but use SSTATE_NOT_INTERNED

}

else {

CHECK(!_Py_IsImmortal(op));

}

break;

case SSTATE_INTERNED_MORTAL:

CHECK(!ascii->state.statically_allocated);

CHECK(!_Py_IsImmortal(op));

break;

case SSTATE_INTERNED_IMMORTAL:

CHECK(!ascii->state.statically_allocated);

break;

case SSTATE_INTERNED_IMMORTAL_STATIC:

CHECK(ascii->state.statically_allocated);

break;

default:

Py_UNREACHABLE();

}

#endif

return 1;

#undef CHECK

}

static PyObject*

unicode_result(PyObject *unicode)

{

assert(_PyUnicode_CHECK(unicode));

Py_ssize_t length = PyUnicode_GET_LENGTH(unicode);

if (length == 0) {

PyObject *empty = unicode_get_empty();

if (unicode != empty) {

Py_DECREF(unicode);

}

return empty;

}

if (length == 1) {

int kind = PyUnicode_KIND(unicode);

if (kind == PyUnicode_1BYTE_KIND) {

const Py_UCS1 *data = PyUnicode_1BYTE_DATA(unicode);

Py_UCS1 ch = data[0];

PyObject *latin1_char = LATIN1(ch);

if (unicode != latin1_char) {

Py_DECREF(unicode);

}

return latin1_char;

}

}

assert(_PyUnicode_CheckConsistency(unicode, 1));

return unicode;

}

static PyObject*

unicode_result_unchanged(PyObject *unicode)

{

if (PyUnicode_CheckExact(unicode)) {

return Py_NewRef(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;

int kind;

const void *data;

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_GrowAndUpdatePointer(writer, size, str);

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;

int kind;

const void *data;

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_GrowAndUpdatePointer(writer, size, str);

if (str == NULL) {

return NULL;

}

/* generate replacement */

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

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

if (size < 0) {

return NULL;

}

str += size;

}

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 _PyUnicode_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, const 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

}

/* Compilation of templated routines */

#define STRINGLIB_GET_EMPTY() unicode_get_empty()

#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"