#ifndef Py_BUILD_CORE_BUILTIN

# define Py_BUILD_CORE_MODULE 1

#include "Python.h"

#include "pycore_object.h" // _PyObject_VisitType()

#include "pycore_ucnhash.h" // _PyUnicode_Name_CAPI

#include "pycore_unicodectype.h" // _PyUnicode_IsXidStart()

#include <stdbool.h>

#include <stddef.h> // offsetof()

#define ADJUST_INDICES(start, end, len) \

do { \

if (end > len) { \

end = len; \

} \

else if (end < 0) { \

end += len; \

if (end < 0) { \

end = 0; \

} \

} \

if (start < 0) { \

start += len; \

if (start < 0) { \

start = 0; \

} \

} \

} while (0)

typedef struct {

const unsigned char category; /* index into

const unsigned char combining; /* combining class value 0 - 255 */

const unsigned char bidirectional; /* index into

const unsigned char mirrored; /* true if mirrored in bidir mode */

const unsigned char east_asian_width; /* index into

const unsigned char normalization_quick_check; /* see is_normalized() */

const unsigned char grapheme_cluster_break; /* index into

const unsigned char incb; /* index into

const unsigned char ext_pict; /* true if Extended_Pictographic */

} _PyUnicode_DatabaseRecord;

typedef struct change_record {

} change_record;

#include "unicodedata_db.h"

static const _PyUnicode_DatabaseRecord*

_getrecord_ex(Py_UCS4 code)

{

int index;

if (code >= 0x110000)

index = 0;

else {

index = index1[(code>>SHIFT)];

index = index2[(index<<SHIFT)+(code&((1<<SHIFT)-1))];

}

return &_PyUnicode_Database_Records[index];

}

typedef struct {

PyObject *SegmentType;

PyObject *GraphemeBreakIteratorType;

} unicodedatastate;

static inline unicodedatastate *

get_unicodedata_state(PyObject *module)

{

void *state = _PyModule_GetState(module);

assert(state != NULL);

return (unicodedatastate *)state;

}

typedef struct previous_version {

} PreviousDBVersion;

#define PreviousDBVersion_CAST(op) ((PreviousDBVersion *)(op))

#include "clinic/unicodedata.c.h"

#define get_old_record(self, v) (PreviousDBVersion_CAST(self)->getrecord(v))

static PyMemberDef DB_members[] = {

{"unidata_version", Py_T_STRING, offsetof(PreviousDBVersion, name), Py_READONLY},

{NULL}

};

#define UCD_Check(self) (self != NULL && !PyModule_Check(self))

static PyObject*

new_previous_version(PyTypeObject *ucd_type,

const char*name, const change_record* (*getrecord)(Py_UCS4),

Py_UCS4 (*normalization)(Py_UCS4))

{

PreviousDBVersion *self;

self = PyObject_GC_New(PreviousDBVersion, ucd_type);

if (self == NULL)

return NULL;

self->name = name;

self->getrecord = getrecord;

self->normalization = normalization;

PyObject_GC_Track(self);

return (PyObject*)self;

}

static PyObject *

unicodedata_UCD_decimal_impl(PyObject *self, int chr,

PyObject *default_value)

{

int have_old = 0;

long rc;

Py_UCS4 c = (Py_UCS4)chr;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed == 0) {

/* unassigned */

have_old = 1;

rc = -1;

}

else if (old->decimal_changed != 0xFF) {

have_old = 1;

rc = old->decimal_changed;

}

}

if (!have_old)

rc = Py_UNICODE_TODECIMAL(c);

if (rc < 0) {

if (default_value == NULL) {

PyErr_SetString(PyExc_ValueError,

"not a decimal");

return NULL;

}

else {

return Py_NewRef(default_value);

}

}

return PyLong_FromLong(rc);

}

static PyObject *

unicodedata_UCD_digit_impl(PyObject *self, int chr, PyObject *default_value)

{

long rc;

Py_UCS4 c = (Py_UCS4)chr;

rc = Py_UNICODE_TODIGIT(c);

if (rc < 0) {

if (default_value == NULL) {

PyErr_SetString(PyExc_ValueError, "not a digit");

return NULL;

}

else {

return Py_NewRef(default_value);

}

}

return PyLong_FromLong(rc);

}

static PyObject *

unicodedata_UCD_numeric_impl(PyObject *self, int chr,

PyObject *default_value)

{

int have_old = 0;

double rc;

Py_UCS4 c = (Py_UCS4)chr;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed == 0) {

/* unassigned */

have_old = 1;

rc = -1.0;

}

else if (old->numeric_changed != 0.0) {

have_old = 1;

rc = old->numeric_changed;

}

}

if (!have_old)

rc = Py_UNICODE_TONUMERIC(c);

if (rc == -1.0) {

if (default_value == NULL) {

PyErr_SetString(PyExc_ValueError, "not a numeric character");

return NULL;

}

else {

return Py_NewRef(default_value);

}

}

return PyFloat_FromDouble(rc);

}

static PyObject *

unicodedata_UCD_category_impl(PyObject *self, int chr)

{

int index;

Py_UCS4 c = (Py_UCS4)chr;

index = (int) _getrecord_ex(c)->category;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed != 0xFF)

index = old->category_changed;

}

return PyUnicode_FromString(_PyUnicode_CategoryNames[index]);

}

static PyObject *

unicodedata_UCD_bidirectional_impl(PyObject *self, int chr)

{

int index;

Py_UCS4 c = (Py_UCS4)chr;

index = (int) _getrecord_ex(c)->bidirectional;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed == 0)

index = 0; /* unassigned */

else if (old->bidir_changed != 0xFF)

index = old->bidir_changed;

}

return PyUnicode_FromString(_PyUnicode_BidirectionalNames[index]);

}

static int

unicodedata_UCD_combining_impl(PyObject *self, int chr)

{

int index;

Py_UCS4 c = (Py_UCS4)chr;

index = (int) _getrecord_ex(c)->combining;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed == 0)

index = 0; /* unassigned */

}

return index;

}

static int

unicodedata_UCD_mirrored_impl(PyObject *self, int chr)

{

int index;

Py_UCS4 c = (Py_UCS4)chr;

index = (int) _getrecord_ex(c)->mirrored;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed == 0)

index = 0; /* unassigned */

else if (old->mirrored_changed != 0xFF)

index = old->mirrored_changed;

}

return index;

}

static PyObject *

unicodedata_UCD_east_asian_width_impl(PyObject *self, int chr)

{

int index;

Py_UCS4 c = (Py_UCS4)chr;

index = (int) _getrecord_ex(c)->east_asian_width;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed == 0)

index = 0; /* unassigned */

else if (old->east_asian_width_changed != 0xFF)

index = old->east_asian_width_changed;

}

return PyUnicode_FromString(_PyUnicode_EastAsianWidthNames[index]);

}

#define SBase 0xAC00

#define LBase 0x1100

#define VBase 0x1161

#define TBase 0x11A7

#define LCount 19

#define VCount 21

#define TCount 28

#define NCount (VCount*TCount)

#define SCount (LCount*NCount)

static PyObject *

unicodedata_UCD_decomposition_impl(PyObject *self, int chr)

{

char decomp[256];

int code, index, count;

size_t i;

unsigned int prefix_index;

Py_UCS4 c = (Py_UCS4)chr;

code = (int)c;

if (UCD_Check(self)) {

const change_record *old = get_old_record(self, c);

if (old->category_changed == 0)

return Py_GetConstant(Py_CONSTANT_EMPTY_STR); /* unassigned */

}

// Hangul Decomposition.

// See section 3.12.2, "Hangul Syllable Decomposition"

// https://www.unicode.org/versions/latest/core-spec/chapter-3/#G56669

if (SBase <= code && code < (SBase + SCount)) {

int SIndex = code - SBase;

int L = LBase + SIndex / NCount;

int V = VBase + (SIndex % NCount) / TCount;

int T = TBase + SIndex % TCount;

if (T != TBase) {

PyOS_snprintf(decomp, sizeof(decomp),

"%04X %04X %04X", L, V, T);

}

else {

PyOS_snprintf(decomp, sizeof(decomp),

"%04X %04X", L, V);

}

return PyUnicode_FromString(decomp);

}

if (code < 0 || code >= 0x110000)

index = 0;

else {

index = decomp_index1[(code>>DECOMP_SHIFT)];

index = decomp_index2[(index<<DECOMP_SHIFT)+

(code&((1<<DECOMP_SHIFT)-1))];

}

/* high byte is number of hex bytes (usually one or two), low byte

count = decomp_data[index] >> 8;

/* XXX: could allocate the PyString up front instead

/* Based on how index is calculated above and decomp_data is generated

prefix_index = decomp_data[index] & 255;

assert(prefix_index < Py_ARRAY_LENGTH(decomp_prefix));

/* copy prefix */

i = strlen(decomp_prefix[prefix_index]);

memcpy(decomp, decomp_prefix[prefix_index], i);

while (count-- > 0) {

if (i)

decomp[i++] = ' ';

assert(i < sizeof(decomp));

PyOS_snprintf(decomp + i, sizeof(decomp) - i, "%04X",

decomp_data[++index]);

i += strlen(decomp + i);

}

return PyUnicode_FromStringAndSize(decomp, i);

}

static void

get_decomp_record(PyObject *self, Py_UCS4 code,

int *index, int *prefix, int *count)

{

if (code >= 0x110000) {

*index = 0;

}

else if (UCD_Check(self)

&& get_old_record(self, code)->category_changed==0) {

/* unassigned in old version */

*index = 0;

}

else {

*index = decomp_index1[(code>>DECOMP_SHIFT)];

*index = decomp_index2[(*index<<DECOMP_SHIFT)+

(code&((1<<DECOMP_SHIFT)-1))];

}

/* high byte is number of hex bytes (usually one or two), low byte

*count = decomp_data[*index] >> 8;

*prefix = decomp_data[*index] & 255;

(*index)++;

}

#define CANONICAL_ORDERING_COUNTING_SORT_THRESHOLD 20

static void

canonical_ordering_sort_insertion(Py_UCS4 *data, Py_ssize_t length)

{

for (Py_ssize_t i = 1; i < length; i++) {

Py_UCS4 code = data[i];

unsigned char combining = _getrecord_ex(code)->combining;

Py_ssize_t j = i;

while (j > 0) {

Py_UCS4 previous = data[j - 1];

if (_getrecord_ex(previous)->combining <= combining) {

break;

}

data[j] = previous;

j--;

}

if (j != i) {

data[j] = code;

}

}

}

static void

canonical_ordering_sort_counting(Py_UCS4 *data, Py_ssize_t length,

Py_UCS4 *sortbuf)

{

Py_ssize_t counts[256] = {0};

Py_ssize_t total = 0;

for (Py_ssize_t i = 0; i < length; i++) {

Py_UCS4 code = data[i];

unsigned char combining = _getrecord_ex(code)->combining;

counts[combining]++;

}

for (size_t i = 0; i < Py_ARRAY_LENGTH(counts); i++) {

Py_ssize_t count = counts[i];

counts[i] = total;

total += count;

}

/* Reuse counts[] as the next output slot for each CCC. */

for (Py_ssize_t i = 0; i < length; i++) {

Py_UCS4 code = data[i];

unsigned char combining = _getrecord_ex(code)->combining;

sortbuf[counts[combining]++] = code;

}

memcpy(data, sortbuf, length * sizeof(Py_UCS4));

}

static PyObject*

nfd_nfkd(PyObject *self, PyObject *input, int k)

{

PyObject *result;

Py_UCS4 *output;

Py_ssize_t i, o, osize;

int input_kind;

const void *input_data;

/* Longest decomposition in Unicode 3.2: U+FDFA */

Py_UCS4 stack[20];

Py_ssize_t space, isize;

int index, prefix, count, stackptr;

unsigned char prev, cur;

Py_UCS4 *sortbuf = NULL;

Py_ssize_t sortbuflen = 0;

stackptr = 0;

isize = PyUnicode_GET_LENGTH(input);

space = isize;

/* Overallocate at most 10 characters. */

if (space > 10) {

if (space <= PY_SSIZE_T_MAX - 10)

space += 10;

}

else {

space *= 2;

}

osize = space;

output = PyMem_NEW(Py_UCS4, space);

if (!output) {

PyErr_NoMemory();

return NULL;

}

i = o = 0;

input_kind = PyUnicode_KIND(input);

input_data = PyUnicode_DATA(input);

while (i < isize) {

stack[stackptr++] = PyUnicode_READ(input_kind, input_data, i++);

while(stackptr) {

Py_UCS4 code = stack[--stackptr];

/* Hangul Decomposition adds three characters in

if (space < 3) {

Py_UCS4 *new_output;

osize += 10;

space += 10;

new_output = PyMem_Realloc(output, osize*sizeof(Py_UCS4));

if (new_output == NULL) {

PyMem_Free(output);

PyErr_NoMemory();

return NULL;

}

output = new_output;

}

// Hangul Decomposition.

// See section 3.12.2, "Hangul Syllable Decomposition"

// https://www.unicode.org/versions/latest/core-spec/chapter-3/#G56669

if (SBase <= code && code < (SBase+SCount)) {

int SIndex = code - SBase;

int L = LBase + SIndex / NCount;

int V = VBase + (SIndex % NCount) / TCount;

int T = TBase + SIndex % TCount;

output[o++] = L;

output[o++] = V;

space -= 2;

if (T != TBase) {

output[o++] = T;

space --;

}

continue;

}

/* normalization changes */

if (UCD_Check(self)) {

Py_UCS4 value = ((PreviousDBVersion*)self)->normalization(code);

if (value != 0) {

stack[stackptr++] = value;

continue;

}

}

/* Other decompositions. */

get_decomp_record(self, code, &index, &prefix, &count);

/* Copy character if it is not decomposable, or has a

if (!count || (prefix && !k)) {

output[o++] = code;

space--;

continue;

}

/* Copy decomposition onto the stack, in reverse

while(count) {

code = decomp_data[index + (--count)];

stack[stackptr++] = code;

}

}

}

/* Sort each consecutive combining-character run canonically. */

i = 0;

while (i < o) {

Py_ssize_t run_length, run_start;

int needs_sort = 0;

Py_UCS4 ch = output[i];

prev = _getrecord_ex(ch)->combining;

if (prev == 0) {

i++;

continue;

}

run_start = i++;

while (i < o) {

Py_UCS4 ch = output[i];

cur = _getrecord_ex(ch)->combining;

if (cur == 0) {

break;

}

if (prev > cur) {

needs_sort = 1;

}

prev = cur;

i++;

}

if (!needs_sort) {

continue;

}

run_length = i - run_start;

if (run_length < CANONICAL_ORDERING_COUNTING_SORT_THRESHOLD) {

canonical_ordering_sort_insertion(output + run_start, run_length);

continue;

}

if (run_length > sortbuflen) {

Py_UCS4 *new_sortbuf = PyMem_Resize(sortbuf, Py_UCS4, run_length);

if (new_sortbuf == NULL) {

PyErr_NoMemory();

PyMem_Free(sortbuf);

PyMem_Free(output);

return NULL;

}

sortbuf = new_sortbuf;

sortbuflen = run_length;

}

canonical_ordering_sort_counting(output + run_start, run_length,

sortbuf);

}

PyMem_Free(sortbuf);

result = PyUnicode_FromKindAndData(PyUnicode_4BYTE_KIND, output, o);

PyMem_Free(output);

return result;

}

static int

find_nfc_index(const struct reindex* nfc, Py_UCS4 code)

{

/* The table is sorted by .start ascending with disjoint [start, start+count]

unsigned int i;

for (i = 0; (Py_UCS4)nfc[i].start <= code; i++) {

}

if (i == 0) {

return -1;

}

unsigned int start = nfc[i - 1].start;

if (code <= start + nfc[i - 1].count) {

return nfc[i - 1].index + (code - start);

}

return -1;

}

static PyObject*

nfc_nfkc(PyObject *self, PyObject *input, int k)

{

PyObject *result;

int kind;

const void *data;

Py_UCS4 *output;

Py_ssize_t i, i1, o, len;

int f,l,index,index1,comb;

Py_UCS4 code;

Py_ssize_t skipped[20];

int cskipped = 0;

result = nfd_nfkd(self, input, k);

if (!result)

return NULL;

kind = PyUnicode_KIND(result);

data = PyUnicode_DATA(result);

len = PyUnicode_GET_LENGTH(result);

/* We allocate a buffer for the output.

output = PyMem_NEW(Py_UCS4, len);

if (!output) {

PyErr_NoMemory();

Py_DECREF(result);

return 0;

}

i = o = 0;

again:

while (i < len) {

for (index = 0; index < cskipped; index++) {

if (skipped[index] == i) {

/* *i character is skipped.

skipped[index] = skipped[cskipped-1];

cskipped--;

i++;

goto again; /* continue while */

}

}

/* Hangul Composition. We don't need to check for <LV,T>

code = PyUnicode_READ(kind, data, i);

if (LBase <= code && code < (LBase+LCount) &&

i + 1 < len &&

VBase <= PyUnicode_READ(kind, data, i+1) &&

PyUnicode_READ(kind, data, i+1) < (VBase+VCount)) {

/* check L character is a modern leading consonant (0x1100 ~ 0x1112)

int LIndex, VIndex;

LIndex = code - LBase;

VIndex = PyUnicode_READ(kind, data, i+1) - VBase;

code = SBase + (LIndex*VCount+VIndex)*TCount;

i+=2;

if (i < len &&

TBase < PyUnicode_READ(kind, data, i) &&

PyUnicode_READ(kind, data, i) < (TBase+TCount)) {

/* check T character is a modern trailing consonant

code += PyUnicode_READ(kind, data, i)-TBase;

i++;

}

output[o++] = code;

continue;

}

/* code is still input[i] here */

f = find_nfc_index(nfc_first, code);

if (f == -1) {

output[o++] = code;

i++;

continue;

}

/* Find next unblocked character. */

i1 = i+1;

comb = 0;

/* output base character for now; might be updated later. */

output[o] = PyUnicode_READ(kind, data, i);

while (i1 < len) {

Py_UCS4 code1 = PyUnicode_READ(kind, data, i1);

int comb1 = _getrecord_ex(code1)->combining;

if (comb) {

if (comb1 == 0)

break;

if (comb >= comb1) {

/* Character is blocked. */

i1++;

continue;

}

}

l = find_nfc_index(nfc_last, code1);

/* i1 cannot be combined with i. If i1

if (l == -1) {

not_combinable:

if (comb1 == 0)

break;

comb = comb1;

i1++;

continue;

}

index = f*TOTAL_LAST + l;

index1 = comp_index[index >> COMP_SHIFT];

code = comp_data[(index1<<COMP_SHIFT)+

(index&((1<<COMP_SHIFT)-1))];

if (code == 0)

goto not_combinable;

/* Replace the original character. */

output[o] = code;

/* Mark the second character unused. */

assert(cskipped < 20);

skipped[cskipped++] = i1;

i1++;

f = find_nfc_index(nfc_first, output[o]);

if (f == -1)

break;

}

/* Output character was already written.

o++; i++;

}

if (o == len) {

/* No changes. Return original string. */

PyMem_Free(output);

return result;

}

Py_DECREF(result);

result = PyUnicode_FromKindAndData(PyUnicode_4BYTE_KIND,

output, o);

PyMem_Free(output);

return result;

}

typedef enum {YES = 0, MAYBE = 1, NO = 2} QuickcheckResult;

static QuickcheckResult

is_normalized_quickcheck(PyObject *self, PyObject *input, bool nfc, bool k,

bool yes_only)

{

/* UCD 3.2.0 is requested, quickchecks must be disabled. */

if (UCD_Check(self)) {

return MAYBE;

}

if (PyUnicode_IS_ASCII(input)) {

return YES;

}

Py_ssize_t i, len;

int kind;

const void *data;

unsigned char prev_combining = 0;

/* The two quickcheck bits at this shift have type QuickcheckResult. */

int quickcheck_shift = (nfc ? 4 : 0) + (k ? 2 : 0);

QuickcheckResult result = YES; /* certainly normalized, unless we find something */

i = 0;

kind = PyUnicode_KIND(input);

data = PyUnicode_DATA(input);

len = PyUnicode_GET_LENGTH(input);

while (i < len) {

Py_UCS4 ch = PyUnicode_READ(kind, data, i++);

const _PyUnicode_DatabaseRecord *record = _getrecord_ex(ch);

unsigned char combining = record->combining;

if (combining && prev_combining > combining)

return NO; /* non-canonical sort order, not normalized */

prev_combining = combining;

unsigned char quickcheck_whole = record->normalization_quick_check;

if (yes_only) {

if (quickcheck_whole & (3 << quickcheck_shift))

return MAYBE;

} else {

switch ((quickcheck_whole >> quickcheck_shift) & 3) {

case NO:

return NO;

case MAYBE:

result = MAYBE; /* this string might need normalization */

}

}

}

return result;

}