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)

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"

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)

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

for w, x in wordlist:

# encoding: bit 7 indicates last character in word (chr(128)

# indicates the last character in an entire string)

ww = w[:-1] + chr(ord(w[-1])+128)

# reuse string tails, when possible

o = lexicon.find(ww)

if o < 0:

o = offset

lexicon = lexicon + ww

offset = offset + len(w)

words[w] = len(lexicon_offset)

lexicon_offset.append(o)

lexicon = map(ord, lexicon)

# generate phrasebook from names and lexicon

phrasebook = [0]

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

for char in unicode.chars:

name = names[char]

if name:

w = name.split()

phrasebook_offset[char] = len(phrasebook)

for w in w:

i = words[w]

if i < short:

phrasebook.append(i)

else:

# store as two bytes

phrasebook.append((i>>8) + short)

phrasebook.append(i&255)

assert getsize(phrasebook) == 1

#

# unicode name hash table

# extract names

data = []

for char in unicode.chars:

record = unicode.table[char]

if record:

name = record[1].strip()

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

data.append((name, char))

# the magic number 47 was chosen to minimize the number of

# collisions on the current data set. if you like, change it

# and see what happens...

codehash = Hash("code", data, 47)

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

fp = open(FILE, "w")

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

print >>fp

print >>fp, "#define NAME_MAXLEN", 256

print >>fp

print >>fp, "/* lexicon */"

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

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

# split decomposition index table

offset1, offset2, shift = splitbins(phrasebook_offset, trace)

print >>fp, "/* code->name phrasebook */"

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

print >>fp, "#define phrasebook_short", short

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

Array("phrasebook_offset1", offset1).dump(fp, trace)

Array("phrasebook_offset2", offset2).dump(fp, trace)

print >>fp, "/* name->code dictionary */"

codehash.dump(fp, trace)

# Changes to exclusion file not implemented yet

if old.exclusions != new.exclusions:

raise NotImplementedError, "exclusions differ"

# In these change records, 0xFF means "no change"

bidir_changes = [0xFF]*0x110000

category_changes = [0xFF]*0x110000

decimal_changes = [0xFF]*0x110000

mirrored_changes = [0xFF]*0x110000

# In numeric data, 0 means "no change",

# -1 means "did not have a numeric value

numeric_changes = [0] * 0x110000

# normalization_changes is a list of key-value pairs

normalization_changes = []

for i in range(0x110000):

if new.table[i] is None:

# Characters unassigned in the new version ought to

# be unassigned in the old one

assert old.table[i] is None

continue

# check characters unassigned in the old version

if old.table[i] is None:

# category 0 is "unassigned"

category_changes[i] = 0

continue

# check characters that differ

if old.table[i] != new.table[i]:

for k in range(len(old.table[i])):

if old.table[i][k] != new.table[i][k]:

value = old.table[i][k]

if k == 2:

#print "CATEGORY",hex(i), old.table[i][k], new.table[i][k]

category_changes[i] = CATEGORY_NAMES.index(value)

elif k == 4:

#print "BIDIR",hex(i), old.table[i][k], new.table[i][k]

bidir_changes[i] = BIDIRECTIONAL_NAMES.index(value)

elif k == 5:

#print "DECOMP",hex(i), old.table[i][k], new.table[i][k]

# We assume that all normalization changes are in 1:1 mappings

assert " " not in value

normalization_changes.append((i, value))

elif k == 6:

#print "DECIMAL",hex(i), old.table[i][k], new.table[i][k]

# we only support changes where the old value is a single digit

assert value in "0123456789"

decimal_changes[i] = int(value)

elif k == 8:

# print "NUMERIC",hex(i), `old.table[i][k]`, new.table[i][k]

# Since 0 encodes "no change", the old value is better not 0

assert value != "0" and value != "-1"

if not value:

numeric_changes[i] = -1

else:

assert re.match("^[0-9]+$", value)

numeric_changes[i] = int(value)

elif k == 9:

if value == 'Y':

mirrored_changes[i] = '1'

else:

mirrored_changes[i] = '0'

elif k == 11:

# change to ISO comment, ignore

pass

elif k == 12:

# change to simple uppercase mapping; ignore

pass

elif k == 13:

# change to simple lowercase mapping; ignore

pass

elif k == 14:

# change to simple titlecase mapping; ignore

pass

else:

class Difference(Exception):pass

raise Difference, (hex(i), k, old.table[i], new.table[i])

new.changed.append((version, zip(bidir_changes, category_changes,

decimal_changes, mirrored_changes,

numeric_changes),

def __init__(self, filename, exclusions, eastasianwidth, expand=1):

self.changed = []

file = open(filename)

table = [None] * 0x110000

while 1:

s = file.readline()

if not s:

break

s = s.strip().split(";")

char = int(s[0], 16)

table[char] = s

# expand first-last ranges

if expand:

field = None

for i in range(0, 0x110000):

s = table[i]

if s:

if s[1][-6:] == "First>":

s[1] = ""

field = s

elif s[1][-5:] == "Last>":

s[1] = ""

field = None

elif field:

f2 = field[:]

f2[0] = "%X" % i

table[i] = f2

# public attributes

self.filename = filename

self.table = table

self.chars = range(0x110000) # unicode 3.2

file = open(exclusions)

self.exclusions = {}

for s in file:

s = s.strip()

if not s:

continue

if s[0] == '#':

continue

char = int(s.split()[0],16)

self.exclusions[char] = 1

widths = [None] * 0x110000

for s in open(eastasianwidth):

s = s.strip()

if not s:

continue

if s[0] == '#':

continue

s = s.split()[0].split(';')

if '..' in s[0]:

first, last = [int(c, 16) for c in s[0].split('..')]

chars = range(first, last+1)

else:

chars = [int(s[0], 16)]

for char in chars:

widths[char] = s[1]

for i in range(0, 0x110000):

if table[i] is not None:

table[i].append(widths[i])

def uselatin1(self):

# restrict character range to ISO Latin 1

h = 0

for c in map(ord, s.upper()):

h = (h * magic) + c

ix = h & 0xff000000L

if ix:

h = (h ^ ((ix>>24) & 0xff)) & 0x00ffffff

(4,3), (8,3), (16,3), (32,5), (64,3), (128,3), (256,29), (512,17),

(1024,9), (2048,5), (4096,83), (8192,27), (16384,43), (32768,3),

(65536,45), (131072,9), (262144,39), (524288,39), (1048576,9),

(2097152,5), (4194304,3), (8388608,33), (16777216,27)

def __init__(self, name, data, magic):

# turn a (key, value) list into a static hash table structure

# determine table size

for size, poly in SIZES:

if size > len(data):

poly = size + poly

break

else:

raise AssertionError, "ran out of polynominals"

print size, "slots in hash table"

table = [None] * size

mask = size-1

n = 0

hash = myhash

# initialize hash table

for key, value in data:

h = hash(key, magic)

i = (~h) & mask

v = table[i]

if v is None:

table[i] = value

continue

incr = (h ^ (h >> 3)) & mask;

if not incr:

incr = mask

while 1:

n = n + 1

i = (i + incr) & mask

v = table[i]

if v is None:

table[i] = value

break

incr = incr << 1

if incr > mask:

incr = incr ^ poly

print n, "collisions"

self.collisions = n

for i in range(len(table)):

if table[i] is None:

table[i] = 0

self.data = Array(name + "_hash", table)

self.magic = magic

self.name = name

self.size = size

self.poly = poly

def dump(self, file, trace):

# write data to file, as a C array

self.data.dump(file, trace)

file.write("#define %s_magic %d\n" % (self.name, self.magic))

file.write("#define %s_size %d\n" % (self.name, self.size))

def __init__(self, name, data):

self.name = name

self.data = data

def dump(self, file, trace=0):

# write data to file, as a C array

size = getsize(self.data)

if trace:

print >>sys.stderr, self.name+":", size*len(self.data), "bytes"

file.write("static ")

if size == 1:

file.write("unsigned char")

elif size == 2:

file.write("unsigned short")

else:

file.write("unsigned int")

file.write(" " + self.name + "[] = {\n")

if self.data:

s = " "

for item in self.data:

i = str(item) + ", "

if len(s) + len(i) > 78:

file.write(s + "\n")

s = " " + i

else:

s = s + i

if s.strip():

file.write(s + "\n")

# return smallest possible integer size for the given array

maxdata = max(data)

if maxdata < 256:

return 1

elif maxdata < 65536:

return 2

else:

"""t, trace=0 -> (t1, t2, shift). Split a table to save space.

import sys

if trace:

def dump(t1, t2, shift, bytes):

print >>sys.stderr, "%d+%d bins at shift %d; %d bytes" % (

len(t1), len(t2), shift, bytes)

print >>sys.stderr, "Size of original table:", len(t)*getsize(t), \

"bytes"

n = len(t)-1 # last valid index

maxshift = 0 # the most we can shift n and still have something left

if n > 0:

while n >> 1:

n >>= 1

maxshift += 1

del n

bytes = sys.maxint # smallest total size so far

t = tuple(t) # so slices can be dict keys

for shift in range(maxshift + 1):

t1 = []

t2 = []

size = 2**shift

bincache = {}

for i in range(0, len(t), size):

bin = t[i:i+size]

index = bincache.get(bin)

if index is None:

index = len(t2)

bincache[bin] = index

t2.extend(bin)

t1.append(index >> shift)

# determine memory size

b = len(t1)*getsize(t1) + len(t2)*getsize(t2)

if trace > 1:

dump(t1, t2, shift, b)

if b < bytes:

best = t1, t2, shift

bytes = b

t1, t2, shift = best

if trace:

print >>sys.stderr, "Best:",

dump(t1, t2, shift, bytes)

if __debug__:

# exhaustively verify that the decomposition is correct

mask = ~((~0) << shift) # i.e., low-bit mask of shift bits

for i in xrange(len(t)):

assert t[i] == t2[(t1[i >> shift] << shift) + (i & mask)]