| #!/usr/bin/env python |
| # Copyright 2015 The Chromium Authors. All rights reserved. |
| # Use of this source code is governed by a BSD-style license that can be |
| # found in the LICENSE file. |
| |
| """Generate a compact character composition table. |
| |
| Normal use: |
| ./generate_character_composer_data.py \ |
| --output character_composer_data.h \ |
| character_composer_sequences.txt |
| |
| Run this script with --help for a description of arguments. |
| |
| Input file format: |
| |
| Comments begin with '#' and extend to the end of the line. |
| |
| Each non-comment line is a sequence of two or more keys, separated by |
| space, the last of which is the result of composing the initial part. |
| A sequence must begin with a dead key or Compose, and the result must |
| be a character key. |
| |
| Each key can either be a character key, a dead key, or the compose key. |
| |
| A character key is written as one of the following inside matched delimiters: |
| - a single printable ASCII character; |
| - a Unicode character name; |
| - 'U+' followed by one or more hexadecimal digits. |
| Delimiter pairs are any of '' "" () <> [] or {}. |
| |
| A dead key is written as the word 'Dead' followed (immediately, without space) |
| by the combining character written in the same form as a character key. |
| |
| A compose key is written as the word 'Compose'. |
| |
| Output file format: |
| |
| The output file is a C++ header containing a small header structure |
| |ui::TreeComposeChecker::CompositionData| and a tree of composition sequences. |
| |
| For space efficiency, the tree is stored in a single array of 16-bit values, |
| which represent either characters (printable or dead-key) or subtree array |
| indices. |
| |
| Each tree level consists for four tables: two key kinds (character or dead) |
| by two node types (internal or leaf), in the order: |
| - character internal |
| - character leaf |
| - dead-key internal |
| - dead-key leaf |
| This order is used because character key entries are more common than dead-key |
| entries, and internal entries are more common than leaf entries. |
| |
| Each table consists of a word containing the number of table entries |n|, |
| followed immediately by |n| key-value pairs of words, ordered by key. |
| For internal edges, the value is the array index of the resulting subtree. |
| For leaf edges, the value is the unicode character code of the composition |
| result. |
| """ |
| |
| import argparse |
| import codecs |
| import collections |
| import sys |
| import unicodedata |
| |
| # Global error counter. |
| g_fail = 0 |
| |
| class Key(str): |
| """Represents an element of a composition sequence. |
| |
| Supports only Compose, dead keys, and BMP unicode characters. |
| Based on |str| for easy comparison and sorting. |
| The representation is 'C' (for unicode characters) or 'D' (for dead keys) |
| followed by 4 hex digits for the character value. The Compose key is |
| represented as dead key with combining character 0. |
| """ |
| _kinds = ['character', 'dead_key'] |
| |
| def __new__(cls, key, character, location=None): |
| """Construct a Key. |
| Call as: |
| - Key(None, character_code) |
| - Key('Dead', combining_character_code) |
| - Key('Compose', 0) |
| """ |
| global g_fail |
| if character > 0xFFFF: |
| print '{}: unsupported non-BMP character {}'.format(location, character) |
| g_fail += 1 |
| s = 'ERROR' |
| elif key is None: |
| s = 'C{:04X}'.format(character) |
| elif key.lower() == 'dead': |
| s = 'D{:04X}'.format(character) |
| elif key.lower() == 'compose': |
| s = 'D0000' |
| else: |
| print '{}: unexpected combination {}<{}>'.format(location, key, character) |
| g_fail += 1 |
| s = 'ERROR' |
| return str.__new__(cls, s) |
| |
| def Kind(self): |
| return {'C': 'character', 'D': 'dead_key'}[self[0]] |
| |
| def CharacterCode(self): |
| return int(self[1:], 16) |
| |
| def UnicodeName(self): |
| v = self.CharacterCode() |
| try: |
| return unicodedata.name(unichr(v)).lower() |
| except ValueError: |
| return 'U+{:04X}'.format(v) |
| |
| def ShorterUnicodeName(self): |
| s = self.UnicodeName() |
| if s.startswith('latin ') or s.startswith('greek '): |
| s = s[6:] |
| if s.startswith('small '): |
| s = s[6:] |
| return s.replace(' letter ', ' ') |
| |
| def Pretty(self): |
| if self == 'D0000': |
| return 'Compose' |
| return ('Dead' if self[0] == 'D' else '') + '<' + self.UnicodeName() + '>' |
| |
| |
| class Input: |
| """ |
| Takes a sequences of file names and presents them as a single input stream, |
| with location reporting for error messages. |
| """ |
| def __init__(self, filenames): |
| self._pending = filenames |
| self._filename = None |
| self._file = None |
| self._line = None |
| self._lineno = 0 |
| self._column = 0 |
| |
| def Where(self): |
| """Report the current input location, for error messages.""" |
| if self._file: |
| return '{}:{}:{}'.format(self._filename, self._lineno, self._column) |
| if self._pending: |
| return '<before>' |
| return '<eof>' |
| |
| def Get(self): |
| """Return the next input character, or None when inputs are exhausted.""" |
| if self._line is None: |
| if self._file is None: |
| if not self._pending: |
| return None |
| self._filename = self._pending[0] |
| self._pending = self._pending[1:] |
| self._file = codecs.open(self._filename, mode='rb', encoding='utf-8') |
| self._lineno = 0 |
| self._lineno += 1 |
| self._line = self._file.readline() |
| if not self._line: |
| self._file = None |
| self._filename = None |
| return self.Get() |
| self._column = 0 |
| if self._column >= len(self._line): |
| self._line = None |
| return self.Get() |
| c = self._line[self._column] |
| self._column += 1 |
| return c |
| |
| |
| class Lexer: |
| """ |
| Breaks the input stream into a sequence of tokens, each of which is either |
| a Key or the string 'EOL'. |
| """ |
| def __init__(self, compose_input): |
| self._input = compose_input |
| |
| _delimiters = { |
| '"': '"', |
| "'": "'", |
| '<': '>', |
| '(': ')', |
| '[': ']', |
| '{': '}', |
| } |
| |
| def GetUntilDelimiter(self, e): |
| text = '' |
| c = self._input.Get() |
| while c and c != e: |
| text += c |
| c = self._input.Get() |
| return text |
| |
| def Get(self): |
| global g_fail |
| c = ' ' |
| while c and c.isspace() and c != '\n': |
| c = self._input.Get() |
| if not c: |
| return None |
| location = self._input.Where() |
| if c == '\n': |
| return 'EOL' |
| if c == '#': |
| self.GetUntilDelimiter('\n') |
| return 'EOL' |
| if c == '\\': |
| self.GetUntilDelimiter('\n') |
| return self.Get() |
| key = None |
| character = None |
| if c.isalnum(): |
| key = '' |
| while c and c.isalnum(): |
| key += c |
| c = self._input.Get() |
| if c in Lexer._delimiters: |
| s = self.GetUntilDelimiter(Lexer._delimiters[c]) |
| if len(s) == 1: |
| character = ord(s) |
| elif s.startswith('U+'): |
| character = int(s[2:], 16) |
| else: |
| try: |
| character = ord(unicodedata.lookup(s.upper())) |
| except KeyError: |
| g_fail += 1 |
| character = None |
| print '{}: unknown character name "{}"'.format(location, |
| s.encode('utf-8')) |
| return Key(key, character, location) |
| |
| def Where(self): |
| return self._input.Where() |
| |
| |
| class Parser: |
| """ |
| Takes a sequence of tokens from a Lexer and returns a tree of |
| composition sequences, represented as nested dictionaries where each |
| composition source element key is a dictionary key, and the final |
| composition result has a dictionary key of |None|. |
| """ |
| def __init__(self, lexer): |
| self._lexer = lexer |
| self._trie = {} |
| |
| def Parse(self): |
| global g_fail |
| self._trie = {} |
| while True: |
| seq = [] |
| t = self._lexer.Get() |
| if not t: |
| break |
| if t and t != 'EOL' and t.Kind() != 'dead_key': |
| g_fail += 1 |
| print ('{}: sequence does not begin with Compose or Dead key' |
| .format(self._lexer.Where())) |
| break |
| while t and t != 'EOL': |
| seq.append(t) |
| t = self._lexer.Get() |
| if not seq: |
| continue |
| self.AddToSimpleTree(self._trie, seq) |
| return self._trie |
| |
| def AddToSimpleTree(self, tree, seq): |
| first = seq[0] |
| rest = seq[1:] |
| if first not in tree: |
| tree[first] = {} |
| if len(rest) == 1: |
| # Leaf |
| tree[first][None] = rest[0] |
| else: |
| self.AddToSimpleTree(tree[first], rest) |
| |
| |
| class GroupedTree: |
| """ |
| Represents composition sequences in a manner close to the output format. |
| |
| The core of the representation is the |_tables| dictionary, which has |
| an entry for each kind of |Key|, each of which is a dictionary with |
| two entries, 'internal' and 'leaf', for the output tables, each being |
| a dictionary indexed by a composition sequence |Key|. For 'internal' |
| tables the dictionary values are |GroupedTree|s at the next level; |
| for 'leaf' tables the dictionary values are |Key| composition results. |
| """ |
| _key_kinds = Key._kinds |
| _sub_parts = ['internal', 'leaf'] |
| |
| def __init__(self, simple_trie, path=None): |
| if path is None: |
| path = [] |
| self.path = path |
| self.depth = len(path) |
| self.height = 0 |
| self.empty = True |
| self.location = -1 |
| |
| # Initialize |_tables|. |
| self._tables = {} |
| for k in self._key_kinds: |
| self._tables[k] = {} |
| for p in self._sub_parts: |
| self._tables[k][p] = {} |
| |
| # Build the tables. |
| for key in simple_trie: |
| if key is not None: |
| # Leaf table entry. |
| if None in simple_trie[key]: |
| self.empty = False |
| self._tables[key.Kind()]['leaf'][key] = simple_trie[key][None] |
| # Internal subtree entries. |
| v = GroupedTree(simple_trie[key], path + [key]) |
| if not v.empty: |
| self.empty = False |
| self._tables[key.Kind()]['internal'][key] = v |
| if self.height < v.height: |
| self.height = v.height |
| self.height += 1 |
| |
| def SubTrees(self): |
| """Returns a list of all sub-|GroupedTree|s of the current GroupTree.""" |
| r = [] |
| for k in self._key_kinds: |
| for key in sorted(self._tables[k]['internal']): |
| r.append(self._tables[k]['internal'][key]) |
| return r |
| |
| |
| class Assembler: |
| """Convert a parse tree via a GroupedTree to a C++ header.""" |
| |
| def __init__(self, args, dtree): |
| self._name = args.data_name |
| self._type = args.type_name |
| self._gtree = GroupedTree(dtree) |
| |
| def Write(self, out): |
| # First pass: determine table sizes and locations. |
| self.Pass(None, self._gtree) |
| |
| # Second pass: write the array. |
| out.write('\nstatic const uint16_t {}Tree[] = {{\n'.format(self._name)) |
| end = self.Pass(out, self._gtree) |
| out.write('};\n\n') |
| |
| # Write the description structure. |
| out.write('static const {} {} = {{\n' |
| .format(self._type, self._name)) |
| out.write(' {}, // maximum sequence length\n'.format(self._gtree.height)) |
| out.write(' {}, // tree array entries\n'.format(end)) |
| out.write(' {}Tree\n'.format(self._name)) |
| out.write('};\n\n') |
| |
| def Pass(self, out, gtree, location=0): |
| gtree.location = location |
| |
| # Write tree header. |
| if out: |
| out.write('\n // offset 0x{:04X}:\n'.format(location)) |
| if gtree.path: |
| out.write(' // prefix:\n') |
| for key in gtree.path: |
| out.write(' // {}\n'.format(key.Pretty())) |
| |
| # Write tables. |
| for k in gtree._key_kinds: |
| for p in gtree._sub_parts: |
| # Write table size. |
| location += 1 |
| if out: |
| out.write(' // {} {} table\n'.format(p, k)) |
| out.write(' 0x{:04X}, // number of entries\n' |
| .format(len(gtree._tables[k][p]))) |
| # Write table body. |
| for key in sorted(gtree._tables[k][p]): |
| location += 2 |
| if out: |
| out.write(' 0x{:04X}, // {}\n' |
| .format(key.CharacterCode(), key.ShorterUnicodeName())) |
| result = gtree._tables[k][p][key] |
| if p == 'internal': |
| out.write(' 0x{:04X},\n'.format(result.location)) |
| else: |
| out.write(' 0x{:04X}, // -> {}\n' |
| .format(result.CharacterCode(), |
| result.ShorterUnicodeName())) |
| |
| # Assemble subtrees of the current tree. |
| for t in gtree.SubTrees(): |
| location = self.Pass(out, t, location) |
| |
| return location |
| |
| |
| def main(argv): |
| parser = argparse.ArgumentParser() |
| parser.add_argument('--type_name', |
| default='ui::TreeComposeChecker::CompositionData') |
| parser.add_argument('--data_name', default='kCompositions') |
| parser.add_argument('--output', default='character_composer_data.h') |
| parser.add_argument('--guard', default=None) |
| parser.add_argument('inputs', nargs='*') |
| args = parser.parse_args(argv[1:]) |
| |
| parse_tree = Parser(Lexer(Input(args.inputs))).Parse() |
| |
| with (sys.stdout if args.output == '-' else open(args.output, 'wb')) as out: |
| out.write('// Copyright 2015 The Chromium Authors. All rights reserved.\n') |
| out.write('// Use of this source code is governed by a BSD-style license') |
| out.write(' that can be\n// found in the LICENSE file.\n\n') |
| out.write('// DO NOT EDIT.\n') |
| out.write('// GENERATED BY {}\n'.format(sys.argv[0])) |
| out.write('// FROM {}\n\n'.format(' '.join(args.inputs))) |
| guard = args.guard if args.guard else args.output |
| guard = ''.join([c.upper() if c.isalpha() else '_' for c in guard]) |
| out.write('#ifndef {0}_\n#define {0}_\n'.format(guard)) |
| Assembler(args, parse_tree).Write(out) |
| out.write('#endif // {}_\n'.format(guard)) |
| |
| return g_fail |
| |
| if __name__ == '__main__': |
| sys.exit(main(sys.argv)) |
