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