#

# (re)generate unicode property and type databases

#

# this script converts a unicode 3.2 database file to

# Modules/unicodedata_db.h, Modules/unicodename_db.h,

# and Objects/unicodetype_db.h

#

# history:

# 2000-09-24 fl   created (based on bits and pieces from unidb)

# 2000-09-25 fl   merged tim's splitbin fixes, separate decomposition table

# 2000-09-25 fl   added character type table

# 2000-09-26 fl   added LINEBREAK, DECIMAL, and DIGIT flags/fields (2.0)

# 2000-11-03 fl   expand first/last ranges

# 2001-01-19 fl   added character name tables (2.1)

# 2001-01-21 fl   added decomp compression; dynamic phrasebook threshold

# 2002-09-11 wd   use string methods

# 2002-10-18 mvl  update to Unicode 3.2

# 2002-10-22 mvl  generate NFC tables

# 2002-11-24 mvl  expand all ranges, sort names version-independently

# 2002-11-25 mvl  add UNIDATA_VERSION

# 2004-05-29 perky add east asian width information

# 2006-03-10 mvl  update to Unicode 4.1; add UCD 3.2 delta

#

# written by Fredrik Lundh (fredrik@pythonware.com)

#

import sys

SCRIPT = sys.argv[0]

VERSION = "2.6"

# The Unicode Database

UNIDATA_VERSION = "5.1.0"

UNICODE_DATA = "UnicodeData%s.txt"

COMPOSITION_EXCLUSIONS = "CompositionExclusions%s.txt"

EASTASIAN_WIDTH = "EastAsianWidth%s.txt"

old_versions = ["3.2.0"]

CATEGORY_NAMES = [ "Cn", "Lu", "Ll", "Lt", "Mn", "Mc", "Me", "Nd",

    "Nl", "No", "Zs", "Zl", "Zp", "Cc", "Cf", "Cs", "Co", "Cn", "Lm",

    "Lo", "Pc", "Pd", "Ps", "Pe", "Pi", "Pf", "Po", "Sm", "Sc", "Sk",

    "So" ]

BIDIRECTIONAL_NAMES = [ "", "L", "LRE", "LRO", "R", "AL", "RLE", "RLO",

    "PDF", "EN", "ES", "ET", "AN", "CS", "NSM", "BN", "B", "S", "WS",

    "ON" ]

EASTASIANWIDTH_NAMES = [ "F", "H", "W", "Na", "A", "N" ]

# note: should match definitions in Objects/unicodectype.c

ALPHA_MASK = 0x01

DECIMAL_MASK = 0x02

DIGIT_MASK = 0x04

LOWER_MASK = 0x08

LINEBREAK_MASK = 0x10

SPACE_MASK = 0x20

TITLE_MASK = 0x40

UPPER_MASK = 0x80

NODELTA_MASK = 0x100

def maketables(trace=0):

    print "--- Reading", UNICODE_DATA % "", "..."

    version = ""

    unicode = UnicodeData(UNICODE_DATA % version,

                          COMPOSITION_EXCLUSIONS % version,

                          EASTASIAN_WIDTH % version)

    print len(filter(None, unicode.table)), "characters"

    for version in old_versions:

        print "--- Reading", UNICODE_DATA % ("-"+version), "..."

        old_unicode = UnicodeData(UNICODE_DATA % ("-"+version),

                                  COMPOSITION_EXCLUSIONS % ("-"+version),

                                  EASTASIAN_WIDTH % ("-"+version))

        print len(filter(None, old_unicode.table)), "characters"

        merge_old_version(version, unicode, old_unicode)

    makeunicodename(unicode, trace)

    makeunicodedata(unicode, trace)

    makeunicodetype(unicode, trace)

# --------------------------------------------------------------------

# unicode character properties

def makeunicodedata(unicode, trace):

    dummy = (0, 0, 0, 0, 0)

    table = [dummy]

    cache = {0: dummy}

    index = [0] * len(unicode.chars)

    FILE = "Modules/unicodedata_db.h"

    print "--- Preparing", FILE, "..."

    # 1) database properties

    for char in unicode.chars:

        record = unicode.table[char]

        if record:

            # extract database properties

            category = CATEGORY_NAMES.index(record[2])

            combining = int(record[3])

            bidirectional = BIDIRECTIONAL_NAMES.index(record[4])

            mirrored = record[9] == "Y"

            eastasianwidth = EASTASIANWIDTH_NAMES.index(record[15])

            item = (

                category, combining, bidirectional, mirrored, eastasianwidth

                )

            # add entry to index and item tables

            i = cache.get(item)

            if i is None:

                cache[item] = i = len(table)

                table.append(item)

            index[char] = i

    # 2) decomposition data

    decomp_data = [0]

    decomp_prefix = [""]

    decomp_index = [0] * len(unicode.chars)

    decomp_size = 0

    comp_pairs = []

    comp_first = [None] * len(unicode.chars)

    comp_last = [None] * len(unicode.chars)

    for char in unicode.chars:

        record = unicode.table[char]

        if record:

            if record[5]:

                decomp = record[5].split()

                if len(decomp) > 19:

                    raise Exception, "character %x has a decomposition too large for nfd_nfkd" % char

                # prefix

                if decomp[0][0] == "<":

                    prefix = decomp.pop(0)

                else:

                    prefix = ""

                try:

                    i = decomp_prefix.index(prefix)

                except ValueError:

                    i = len(decomp_prefix)

                    decomp_prefix.append(prefix)

                prefix = i

                assert prefix < 256

                # content

                decomp = [prefix + (len(decomp)<<8)] +\

                         map(lambda s: int(s, 16), decomp)

                # Collect NFC pairs

                if not prefix and len(decomp) == 3 and \

                   char not in unicode.exclusions and \

                   unicode.table[decomp[1]][3] == "0":

                    p, l, r = decomp

                    comp_first[l] = 1

                    comp_last[r] = 1

                    comp_pairs.append((l,r,char))

                try:

                    i = decomp_data.index(decomp)

                except ValueError:

                    i = len(decomp_data)

                    decomp_data.extend(decomp)

                    decomp_size = decomp_size + len(decomp) * 2

            else:

                i = 0

            decomp_index[char] = i

    f = l = 0

    comp_first_ranges = []

    comp_last_ranges = []

    prev_f = prev_l = None

    for i in unicode.chars:

        if comp_first[i] is not None:

            comp_first[i] = f

            f += 1

            if prev_f is None:

                prev_f = (i,i)

            elif prev_f[1]+1 == i:

                prev_f = prev_f[0],i

            else:

                comp_first_ranges.append(prev_f)

                prev_f = (i,i)

        if comp_last[i] is not None:

            comp_last[i] = l

            l += 1

            if prev_l is None:

                prev_l = (i,i)

            elif prev_l[1]+1 == i:

                prev_l = prev_l[0],i

            else:

                comp_last_ranges.append(prev_l)

                prev_l = (i,i)

    comp_first_ranges.append(prev_f)

    comp_last_ranges.append(prev_l)

    total_first = f

    total_last = l

    comp_data = [0]*(total_first*total_last)

    for f,l,char in comp_pairs:

        f = comp_first[f]

        l = comp_last[l]

        comp_data[f*total_last+l] = char

    print len(table), "unique properties"

    print len(decomp_prefix), "unique decomposition prefixes"

    print len(decomp_data), "unique decomposition entries:",

    print decomp_size, "bytes"

    print total_first, "first characters in NFC"

    print total_last, "last characters in NFC"

    print len(comp_pairs), "NFC pairs"

    print "--- Writing", FILE, "..."

    fp = open(FILE, "w")

    print >>fp, "/* this file was generated by %s %s */" % (SCRIPT, VERSION)

    print >>fp

    print >>fp, '#define UNIDATA_VERSION "%s"' % UNIDATA_VERSION

    print >>fp, "/* a list of unique database records */"

    print >>fp, \

          "const _PyUnicode_DatabaseRecord _PyUnicode_Database_Records[] = {"

    for item in table:

        print >>fp, "    {%d, %d, %d, %d, %d}," % item

    print >>fp, "};"

    print >>fp

    print >>fp, "/* Reindexing of NFC first characters. */"

    print >>fp, "#define TOTAL_FIRST",total_first

    print >>fp, "#define TOTAL_LAST",total_last

    print >>fp, "struct reindex{int start;short count,index;};"

    print >>fp, "static struct reindex nfc_first[] = {"

    for start,end in comp_first_ranges:

        print >>fp,"  { %d, %d, %d}," % (start,end-start,comp_first[start])

    print >>fp,"  {0,0,0}"

    print >>fp,"};\n"

    print >>fp, "static struct reindex nfc_last[] = {"

    for start,end in comp_last_ranges:

        print >>fp,"  { %d, %d, %d}," % (start,end-start,comp_last[start])

    print >>fp,"  {0,0,0}"

    print >>fp,"};\n"

    # FIXME: <fl> the following tables could be made static, and

    # the support code moved into unicodedatabase.c

    print >>fp, "/* string literals */"

    print >>fp, "const char *_PyUnicode_CategoryNames[] = {"

    for name in CATEGORY_NAMES:

        print >>fp, "    \"%s\"," % name

    print >>fp, "    NULL"

    print >>fp, "};"

    print >>fp, "const char *_PyUnicode_BidirectionalNames[] = {"

    for name in BIDIRECTIONAL_NAMES:

        print >>fp, "    \"%s\"," % name

    print >>fp, "    NULL"

    print >>fp, "};"

    print >>fp, "const char *_PyUnicode_EastAsianWidthNames[] = {"

    for name in EASTASIANWIDTH_NAMES:

        print >>fp, "    \"%s\"," % name

    print >>fp, "    NULL"

    print >>fp, "};"

    print >>fp, "static const char *decomp_prefix[] = {"

    for name in decomp_prefix:

        print >>fp, "    \"%s\"," % name

    print >>fp, "    NULL"

    print >>fp, "};"

    # split record index table

    index1, index2, shift = splitbins(index, trace)

    print >>fp, "/* index tables for the database records */"

    print >>fp, "#define SHIFT", shift

    Array("index1", index1).dump(fp, trace)

    Array("index2", index2).dump(fp, trace)

    # split decomposition index table

    index1, index2, shift = splitbins(decomp_index, trace)

    print >>fp, "/* decomposition data */"

    Array("decomp_data", decomp_data).dump(fp, trace)

    print >>fp, "/* index tables for the decomposition data */"

    print >>fp, "#define DECOMP_SHIFT", shift

    Array("decomp_index1", index1).dump(fp, trace)

    Array("decomp_index2", index2).dump(fp, trace)

    index, index2, shift = splitbins(comp_data, trace)

    print >>fp, "/* NFC pairs */"

    print >>fp, "#define COMP_SHIFT", shift

    Array("comp_index", index).dump(fp, trace)

    Array("comp_data", index2).dump(fp, trace)

    # Generate delta tables for old versions

    for version, table, normalization in unicode.changed:

        cversion = version.replace(".","_")

        records = [table[0]]

        cache = {table[0]:0}

        index = [0] * len(table)

        for i, record in enumerate(table):

            try:

                index[i] = cache[record]

            except KeyError:

                index[i] = cache[record] = len(records)

                records.append(record)

        index1, index2, shift = splitbins(index, trace)

        print >>fp, "static const change_record change_records_%s[] = {" % cversion

        for record in records:

            print >>fp, "\t{ %s }," % ", ".join(map(str,record))

        print >>fp, "};"

        Array("changes_%s_index" % cversion, index1).dump(fp, trace)

        Array("changes_%s_data" % cversion, index2).dump(fp, trace)

        print >>fp, "static const change_record* get_change_%s(Py_UCS4 n)" % cversion

        print >>fp, "{"

        print >>fp, "\tint index;"

        print >>fp, "\tif (n >= 0x110000) index = 0;"

        print >>fp, "\telse {"

        print >>fp, "\t\tindex = changes_%s_index[n>>%d];" % (cversion, shift)

        print >>fp, "\t\tindex = changes_%s_data[(index<<%d)+(n & %d)];" % \

              (cversion, shift, ((1<<shift)-1))

        print >>fp, "\t}"

        print >>fp, "\treturn change_records_%s+index;" % cversion

        print >>fp, "}\n"

        print >>fp, "static Py_UCS4 normalization_%s(Py_UCS4 n)" % cversion

        print >>fp, "{"

        print >>fp, "\tswitch(n) {"

        for k, v in normalization:

            print >>fp, "\tcase %s: return 0x%s;" % (hex(k), v)

        print >>fp, "\tdefault: return 0;"

        print >>fp, "\t}\n}\n"

    fp.close()

# --------------------------------------------------------------------

# unicode character type tables

def makeunicodetype(unicode, trace):

    FILE = "Objects/unicodetype_db.h"

    print "--- Preparing", FILE, "..."

    # extract unicode types

    dummy = (0, 0, 0, 0, 0, 0)

    table = [dummy]

    cache = {0: dummy}

    index = [0] * len(unicode.chars)

    for char in unicode.chars:

        record = unicode.table[char]

        if record:

            # extract database properties

            category = record[2]

            bidirectional = record[4]

            flags = 0

            delta = True

            if category in ["Lm", "Lt", "Lu", "Ll", "Lo"]:

                flags |= ALPHA_MASK

            if category == "Ll":

                flags |= LOWER_MASK

            if category == "Zl" or bidirectional == "B":

                flags |= LINEBREAK_MASK

            if category == "Zs" or bidirectional in ("WS", "B", "S"):

                flags |= SPACE_MASK

            if category == "Lt":

                flags |= TITLE_MASK

            if category == "Lu":

                flags |= UPPER_MASK

            # use delta predictor for upper/lower/title if it fits

            if record[12]:

                upper = int(record[12], 16) - char

                if  -32768 <= upper <= 32767 and delta:

                    upper = upper & 0xffff

                else:

                    upper += char

                    delta = False

            else:

                upper = 0

            if record[13]:

                lower = int(record[13], 16) - char

                if -32768 <= lower <= 32767 and delta:

                    lower = lower & 0xffff

                else:

                    lower += char

                    delta = False

            else:

                lower = 0

            if record[14]:

                title = int(record[14], 16) - char

                if -32768 <= lower <= 32767 and delta:

                    title = title & 0xffff

                else:

                    title += char

                    delta = False

            else:

                title = 0

            if not delta:

                flags |= NODELTA_MASK

            # decimal digit, integer digit

            decimal = 0

            if record[6]:

                flags |= DECIMAL_MASK

                decimal = int(record[6])

            digit = 0

            if record[7]:

                flags |= DIGIT_MASK

                digit = int(record[7])

            item = (

                upper, lower, title, decimal, digit, flags

                )

            # add entry to index and item tables

            i = cache.get(item)

            if i is None:

                cache[item] = i = len(table)

                table.append(item)

            index[char] = i

    print len(table), "unique character type entries"

    print "--- Writing", FILE, "..."

    fp = open(FILE, "w")

    print >>fp, "/* this file was generated by %s %s */" % (SCRIPT, VERSION)

    print >>fp

    print >>fp, "/* a list of unique character type descriptors */"

    print >>fp, "const _PyUnicode_TypeRecord _PyUnicode_TypeRecords[] = {"

    for item in table:

        print >>fp, "    {%d, %d, %d, %d, %d, %d}," % item

    print >>fp, "};"

    print >>fp

    # split decomposition index table

    index1, index2, shift = splitbins(index, trace)

    print >>fp, "/* type indexes */"

    print >>fp, "#define SHIFT", shift

    Array("index1", index1).dump(fp, trace)

    Array("index2", index2).dump(fp, trace)

    fp.close()

# --------------------------------------------------------------------

# unicode name database

def makeunicodename(unicode, trace):

    FILE = "Modules/unicodename_db.h"

    print "--- Preparing", FILE, "..."

    # collect names

    names = [None] * len(unicode.chars)

    for char in unicode.chars:

        record = unicode.table[char]

        if record:

            name = record[1].strip()

            if name and name[0] != "<":

                names[char] = name + chr(0)

    print len(filter(lambda n: n is not None, names)), "distinct names"

    # collect unique words from names (note that we differ between

    # words inside a sentence, and words ending a sentence.  the

    # latter includes the trailing null byte.

    words = {}

    n = b = 0

    for char in unicode.chars:

        name = names[char]

        if name:

            w = name.split()

            b = b + len(name)

            n = n + len(w)

            for w in w:

                l = words.get(w)

                if l:

                    l.append(None)

                else:

                    words[w] = [len(words)]

    print n, "words in text;", b, "bytes"

    wordlist = words.items()

    # sort on falling frequency, then by name

    def cmpwords((aword, alist),(bword, blist)):

        r = -cmp(len(alist),len(blist))

        if r:

            return r

        return cmp(aword, bword)

    wordlist.sort(cmpwords)

    # figure out how many phrasebook escapes we need

    escapes = 0

    while escapes * 256 < len(wordlist):

        escapes = escapes + 1

    print escapes, "escapes"

    short = 256 - escapes

    assert short > 0

    print short, "short indexes in lexicon"

    # statistics

    n = 0

    for i in range(short):

        n = n + len(wordlist[i][1])

    print n, "short indexes in phrasebook"

    # pick the most commonly used words, and sort the rest on falling

    # length (to maximize overlap)

    wordlist, wordtail = wordlist[:short], wordlist[short:]

    wordtail.sort(lambda a, b: len(b[0])-len(a[0]))

    wordlist.extend(wordtail)

    # generate lexicon from words

    lexicon_offset = [0]

    lexicon = ""

    words = {}

    # build a lexicon string

    offset = 0