utils/unicode-case-fold.py

   1 #!/usr/bin/env python
   2 """
   3 Unicode case folding database conversion utility
   4
   5 Parses the database and generates a C++ function which implements the case
   6 folding algorithm. The database entries are of the form:
   7
   8   <code>; <status>; <mapping>; # <name>
   9
  10 <status> can be one of four characters:
  11   C - Common mappings
  12   S - mappings for Simple case folding
  13   F - mappings for Full case folding
  14   T - special case for Turkish I characters
  15
  16 Right now this generates a function which implements simple case folding (C+S
  17 entries).
  18 """
  19
  20 from __future__ import print_function
  21
  22 import sys
  23 import re
  24 try:
  25     from urllib.request import urlopen
  26 except ImportError:
  27     from urllib2 import urlopen
  28
  29
  30 # This variable will body of the mappings function
  31 body = ""
  32
  33 # Reads file line-by-line, extracts Common and Simple case fold mappings and
  34 # returns a (from_char, to_char, from_name) tuple.
  35 def mappings(f):
  36     previous_from = -1
  37     expr = re.compile(r'^(.*); [CS]; (.*); # (.*)')
  38     for line in f:
  39         m = expr.match(line)
  40         if not m: continue
  41         from_char = int(m.group(1), 16)
  42         to_char = int(m.group(2), 16)
  43         from_name = m.group(3)
  44
  45         if from_char <= previous_from:
  46             raise Exception("Duplicate or unsorted characters in input")
  47         yield from_char, to_char, from_name
  48         previous_from = from_char
  49
  50 # Computes the shift (to_char - from_char) in a mapping.
  51 def shift(mapping):
  52     return mapping[1] - mapping[0]
  53
  54 # Computes the stride (from_char2 - from_char1) of two mappings.
  55 def stride2(mapping1, mapping2):
  56     return mapping2[0] - mapping1[0]
  57
  58 # Computes the stride of a list of mappings. The list should have at least two
  59 # mappings. All mappings in the list are assumed to have the same stride.
  60 def stride(block):
  61     return stride2(block[0], block[1])
  62
  63
  64 # b is a list of mappings. All the mappings are assumed to have the same
  65 # shift and the stride between adjecant mappings (if any) is constant.
  66 def dump_block(b):
  67     global body
  68
  69     if len(b) == 1:
  70         # Special case for handling blocks of length 1. We don't even need to
  71         # emit the "if (C < X) return C" check below as all characters in this
  72         # range will be caught by the "C < X" check emitted by the first
  73         # non-trivial block.
  74         body  += "  // {2}\n  if (C == {0:#06x})\n    return {1:#06x};\n".format(*b[0])
  75         return
  76
  77     first = b[0][0]
  78     last = first + stride(b) * (len(b)-1)
  79     modulo = first % stride(b)
  80
  81     # All characters before this block map to themselves.
  82     body += "  if (C < {0:#06x})\n    return C;\n".format(first)
  83     body += "  // {0} characters\n".format(len(b))
  84
  85     # Generic pattern: check upper bound (lower bound is checked by the "if"
  86     # above) and modulo of C, return C+shift.
  87     pattern = "  if (C <= {0:#06x} && C % {1} == {2})\n    return C + {3};\n"
  88
  89     if stride(b) == 2 and shift(b[0]) == 1 and modulo == 0:
  90         # Special case:
  91         # We can elide the modulo-check because the expression "C|1" will map
  92         # the intervening characters to themselves.
  93         pattern = "  if (C <= {0:#06x})\n    return C | 1;\n"
  94     elif stride(b) == 1:
  95         # Another special case: X % 1 is always zero, so don't emit the
  96         # modulo-check.
  97         pattern = "  if (C <= {0:#06x})\n    return C + {3};\n"
  98
  99     body += pattern.format(last, stride(b), modulo, shift(b[0]))
 100
 101 current_block = []
 102 f = urlopen(sys.argv[1])
 103 for m in mappings(f):
 104     if len(current_block) == 0:
 105         current_block.append(m)
 106         continue
 107
 108     if shift(current_block[0]) != shift(m):
 109         # Incompatible shift, start a new block.
 110         dump_block(current_block)
 111         current_block = [m]
 112         continue
 113
 114     if len(current_block) == 1 or stride(current_block) == stride2(current_block[-1], m):
 115         current_block.append(m)
 116         continue
 117
 118     # Incompatible stride, start a new block.
 119     dump_block(current_block)
 120     current_block = [m]
 121 f.close()
 122
 123 dump_block(current_block)
 124
 125 print('//===---------- Support/UnicodeCaseFold.cpp -------------------------------===//')
 126 print('//')
 127 print('// This file was generated by utils/unicode-case-fold.py from the Unicode')
 128 print('// case folding database at')
 129 print('//   ', sys.argv[1])
 130 print('//')
 131 print('// To regenerate this file, run:')
 132 print('//   utils/unicode-case-fold.py \\')
 133 print('//     "{}" \\'.format(sys.argv[1]))
 134 print('//     > lib/Support/UnicodeCaseFold.cpp')
 135 print('//')
 136 print('//===----------------------------------------------------------------------===//')
 137 print('')
 138 print('#include "llvm/Support/Unicode.h"')
 139 print('')
 140 print("int llvm::sys::unicode::foldCharSimple(int C) {")
 141 print(body)
 142 print("  return C;")
 143 print("}")