js/src/frontend/GenerateReservedWords.py

   1 # This Source Code Form is subject to the terms of the Mozilla Public
   2 # License, v. 2.0. If a copy of the MPL was not distributed with this
   3 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
   4
   5 import re
   6 import sys
   7
   8
   9 def read_reserved_word_list(filename, enable_decorators):
  10     macro_pat = re.compile(r"MACRO\(([^,]+), *[^,]+, *[^\)]+\)\s*\\?")
  11
  12     reserved_word_list = []
  13     index = 0
  14     with open(filename, "r") as f:
  15         for line in f:
  16             m = macro_pat.search(line)
  17             if m:
  18                 reserved_word = m.group(1)
  19                 if reserved_word == "accessor" and not enable_decorators:
  20                     continue
  21                 reserved_word_list.append((index, reserved_word))
  22                 index += 1
  23
  24     assert len(reserved_word_list) != 0
  25
  26     return reserved_word_list
  27
  28
  29 def line(opt, s):
  30     opt["output"].write("{}{}\n".format("    " * opt["indent_level"], s))
  31
  32
  33 def indent(opt):
  34     opt["indent_level"] += 1
  35
  36
  37 def dedent(opt):
  38     opt["indent_level"] -= 1
  39
  40
  41 def span_and_count_at(reserved_word_list, column):
  42     assert len(reserved_word_list) != 0
  43
  44     chars_dict = {}
  45     for index, word in reserved_word_list:
  46         chars_dict[ord(word[column])] = True
  47
  48     chars = sorted(chars_dict.keys())
  49     return chars[-1] - chars[0] + 1, len(chars)
  50
  51
  52 def optimal_switch_column(opt, reserved_word_list, columns, unprocessed_columns):
  53     assert len(reserved_word_list) != 0
  54     assert unprocessed_columns != 0
  55
  56     min_count = 0
  57     min_span = 0
  58     min_count_index = 0
  59     min_span_index = 0
  60
  61     for index in range(0, unprocessed_columns):
  62         span, count = span_and_count_at(reserved_word_list, columns[index])
  63         assert span != 0
  64
  65         if span == 1:
  66             assert count == 1
  67             return 1, True
  68
  69         assert count != 1
  70         if index == 0 or min_span > span:
  71             min_span = span
  72             min_span_index = index
  73
  74         if index == 0 or min_count > count:
  75             min_count = count
  76             min_count_index = index
  77
  78     if min_count <= opt["use_if_threshold"]:
  79         return min_count_index, True
  80
  81     return min_span_index, False
  82
  83
  84 def split_list_per_column(reserved_word_list, column):
  85     assert len(reserved_word_list) != 0
  86
  87     column_dict = {}
  88     for item in reserved_word_list:
  89         index, word = item
  90         per_column = column_dict.setdefault(word[column], [])
  91         per_column.append(item)
  92
  93     return sorted(column_dict.items())
  94
  95
  96 def generate_letter_switch(opt, unprocessed_columns, reserved_word_list, columns=None):
  97     assert len(reserved_word_list) != 0
  98
  99     if not columns:
 100         columns = range(0, unprocessed_columns)
 101
 102     if len(reserved_word_list) == 1:
 103         index, word = reserved_word_list[0]
 104
 105         if unprocessed_columns == 0:
 106             line(opt, "JSRW_GOT_MATCH({}) /* {} */".format(index, word))
 107             return
 108
 109         if unprocessed_columns > opt["char_tail_test_threshold"]:
 110             line(opt, "JSRW_TEST_GUESS({}) /* {} */".format(index, word))
 111             return
 112
 113         conds = []
 114         for column in columns[0:unprocessed_columns]:
 115             quoted = repr(word[column])
 116             conds.append("JSRW_AT({})=={}".format(column, quoted))
 117
 118         line(opt, "if ({}) {{".format(" && ".join(conds)))
 119
 120         indent(opt)
 121         line(opt, "JSRW_GOT_MATCH({}) /* {} */".format(index, word))
 122         dedent(opt)
 123
 124         line(opt, "}")
 125         line(opt, "JSRW_NO_MATCH()")
 126         return
 127
 128     assert unprocessed_columns != 0
 129
 130     optimal_column_index, use_if = optimal_switch_column(
 131         opt, reserved_word_list, columns, unprocessed_columns
 132     )
 133     optimal_column = columns[optimal_column_index]
 134
 135     # Make a copy to avoid breaking passed list.
 136     columns = list(columns)
 137     columns[optimal_column_index] = columns[unprocessed_columns - 1]
 138
 139     list_per_column = split_list_per_column(reserved_word_list, optimal_column)
 140
 141     if not use_if:
 142         line(opt, "switch (JSRW_AT({})) {{".format(optimal_column))
 143
 144     for char, reserved_word_list_per_column in list_per_column:
 145         quoted = repr(char)
 146         if use_if:
 147             line(opt, "if (JSRW_AT({}) == {}) {{".format(optimal_column, quoted))
 148         else:
 149             line(opt, "  case {}:".format(quoted))
 150
 151         indent(opt)
 152         generate_letter_switch(
 153             opt, unprocessed_columns - 1, reserved_word_list_per_column, columns
 154         )
 155         dedent(opt)
 156
 157         if use_if:
 158             line(opt, "}")
 159
 160     if not use_if:
 161         line(opt, "}")
 162
 163     line(opt, "JSRW_NO_MATCH()")
 164
 165
 166 def split_list_per_length(reserved_word_list):
 167     assert len(reserved_word_list) != 0
 168
 169     length_dict = {}
 170     for item in reserved_word_list:
 171         index, word = item
 172         per_length = length_dict.setdefault(len(word), [])
 173         per_length.append(item)
 174
 175     return sorted(length_dict.items())
 176
 177
 178 def generate_switch(opt, reserved_word_list):
 179     assert len(reserved_word_list) != 0
 180
 181     line(opt, "/*")
 182     line(
 183         opt,
 184         " * Generating switch for the list of {} entries:".format(
 185             len(reserved_word_list)
 186         ),
 187     )
 188     for index, word in reserved_word_list:
 189         line(opt, " * {}".format(word))
 190     line(opt, " */")
 191
 192     list_per_length = split_list_per_length(reserved_word_list)
 193
 194     use_if = False
 195     if len(list_per_length) < opt["use_if_threshold"]:
 196         use_if = True
 197
 198     if not use_if:
 199         line(opt, "switch (JSRW_LENGTH()) {")
 200
 201     for length, reserved_word_list_per_length in list_per_length:
 202         if use_if:
 203             line(opt, "if (JSRW_LENGTH() == {}) {{".format(length))
 204         else:
 205             line(opt, "  case {}:".format(length))
 206
 207         indent(opt)
 208         generate_letter_switch(opt, length, reserved_word_list_per_length)
 209         dedent(opt)
 210
 211         if use_if:
 212             line(opt, "}")
 213
 214     if not use_if:
 215         line(opt, "}")
 216     line(opt, "JSRW_NO_MATCH()")
 217
 218
 219 def main(output, reserved_words_h, enable_decorators=False):
 220     reserved_word_list = read_reserved_word_list(reserved_words_h, enable_decorators)
 221
 222     opt = {
 223         "indent_level": 1,
 224         "use_if_threshold": 3,
 225         "char_tail_test_threshold": 4,
 226         "output": output,
 227     }
 228     generate_switch(opt, reserved_word_list)
 229
 230
 231 if __name__ == "__main__":
 232     main(sys.stdout, *sys.argv[1:])