michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include <assert.h>
michael@0: #include <ctype.h>
michael@0: #include <stdarg.h>
michael@0: #include <stdio.h>
michael@0: #include <stdlib.h>
michael@0: #include <string.h>
michael@0: 
michael@0: #include "vm/Keywords.h"
michael@0: 
michael@0: static const char * const keyword_list[] = {
michael@0: #define KEYWORD_STRING(keyword, name, type, version) #keyword,
michael@0:     FOR_EACH_JAVASCRIPT_KEYWORD(KEYWORD_STRING)
michael@0: #undef KEYWORD_STRING
michael@0: };
michael@0: 
michael@0: struct gen_opt {
michael@0:     FILE *output;                       /* output file for generated source */
michael@0:     unsigned use_if_threshold;          /* max number of choices to generate
michael@0:                                            "if" selector instead of "switch" */
michael@0:     unsigned char_tail_test_threshold;  /* max number of unprocessed columns
michael@0:                                            to use inlined char compare
michael@0:                                            for remaining chars and not generic
michael@0:                                            string compare code */
michael@0:     unsigned indent_level;              /* current source identation level */
michael@0: };
michael@0: 
michael@0: static unsigned column_to_compare;
michael@0: 
michael@0: static int
michael@0: length_comparator(const void *a, const void *b)
michael@0: {
michael@0:     const char *str1 = keyword_list[*(unsigned *)a];
michael@0:     const char *str2 = keyword_list[*(unsigned *)b];
michael@0:     return (int)strlen(str1) - (int)strlen(str2);
michael@0: }
michael@0: 
michael@0: static int
michael@0: column_comparator(const void *a, const void *b)
michael@0: {
michael@0:     const char *str1 = keyword_list[*(unsigned *)a];
michael@0:     const char *str2 = keyword_list[*(unsigned *)b];
michael@0:     return (int)str1[column_to_compare] - (int)str2[column_to_compare];
michael@0: }
michael@0: 
michael@0: static unsigned
michael@0: count_different_lengths(unsigned indexes[], unsigned nelem)
michael@0: {
michael@0:     unsigned nlength, current_length, i, l;
michael@0: 
michael@0:     current_length = 0;
michael@0:     nlength = 0;
michael@0:     for (i = 0; i != nelem; ++i) {
michael@0:         l = (unsigned)strlen(keyword_list[indexes[i]]);
michael@0:         assert(l != 0);
michael@0:         if (current_length != l) {
michael@0:             ++nlength;
michael@0:             current_length = l;
michael@0:         }
michael@0:     }
michael@0:     return nlength;
michael@0: }
michael@0: 
michael@0: static void
michael@0: find_char_span_and_count(unsigned indexes[], unsigned nelem, unsigned column,
michael@0:                          unsigned *span_result, unsigned *count_result)
michael@0: {
michael@0:     unsigned i, count;
michael@0:     unsigned char c, prev, minc, maxc;
michael@0: 
michael@0:     assert(nelem != 0);
michael@0:     minc = maxc = prev = (unsigned char)keyword_list[indexes[0]][column];
michael@0:     count = 1;
michael@0:     for (i = 1; i != nelem; ++i) {
michael@0:         c = (unsigned char)keyword_list[indexes[i]][column];
michael@0:         if (prev != c) {
michael@0:             prev = c;
michael@0:             ++count;
michael@0:             if (minc > c) {
michael@0:                 minc = c;
michael@0:             } else if (maxc < c) {
michael@0:                 maxc = c;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     *span_result = maxc - minc + 1;
michael@0:     *count_result = count;
michael@0: }
michael@0: 
michael@0: static unsigned
michael@0: find_optimal_switch_column(struct gen_opt *opt,
michael@0:                            unsigned indexes[], unsigned nelem,
michael@0:                            unsigned columns[], unsigned unprocessed_columns,
michael@0:                            int *use_if_result)
michael@0: {
michael@0:     unsigned i;
michael@0:     unsigned span, min_span, min_span_index;
michael@0:     unsigned nchar, min_nchar, min_nchar_index;
michael@0: 
michael@0:     assert(unprocessed_columns != 0);
michael@0:     i = 0;
michael@0:     min_nchar = min_span = (unsigned)-1;
michael@0:     min_nchar_index = min_span_index = 0;
michael@0:     do {
michael@0:         column_to_compare = columns[i];
michael@0:         qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
michael@0:         find_char_span_and_count(indexes, nelem, column_to_compare,
michael@0:                                  &span, &nchar);
michael@0:         assert(span != 0);
michael@0:         if (span == 1) {
michael@0:             assert(nchar == 1);
michael@0:             *use_if_result = 1;
michael@0:             return 1;
michael@0:         }
michael@0:         assert(nchar != 1);
michael@0:         if (min_span > span) {
michael@0:             min_span = span;
michael@0:             min_span_index = i;
michael@0:         }
michael@0:         if (min_nchar > nchar) {
michael@0:             min_nchar = nchar;
michael@0:             min_nchar_index = i;
michael@0:         }
michael@0:     } while (++i != unprocessed_columns);
michael@0: 
michael@0:     if (min_nchar <= opt->use_if_threshold) {
michael@0:         *use_if_result = 1;
michael@0:         i = min_nchar_index;
michael@0:     } else {
michael@0:         *use_if_result = 0;
michael@0:         i = min_span_index;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Restore order corresponding to i if it was destroyed by
michael@0:      * subsequent sort.
michael@0:      */
michael@0:     if (i != unprocessed_columns - 1) {
michael@0:         column_to_compare = columns[i];
michael@0:         qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
michael@0:     }
michael@0: 
michael@0:     return i;
michael@0: }
michael@0: 
michael@0: 
michael@0: static void
michael@0: p(struct gen_opt *opt, const char *format, ...)
michael@0: {
michael@0:     va_list ap;
michael@0: 
michael@0:     va_start(ap, format);
michael@0:     vfprintf(opt->output, format, ap);
michael@0:     va_end(ap);
michael@0: }
michael@0: 
michael@0: /* Size for '\xxx' where xxx is octal escape */
michael@0: #define MIN_QUOTED_CHAR_BUFFER 7
michael@0: 
michael@0: static char *
michael@0: qchar(char c, char *quoted_buffer)
michael@0: {
michael@0:     char *s;
michael@0: 
michael@0:     s = quoted_buffer;
michael@0:     *s++ = '\'';
michael@0:     switch (c) {
michael@0:       case '\n': c = 'n'; goto one_char_escape;
michael@0:       case '\r': c = 'r'; goto one_char_escape;
michael@0:       case '\t': c = 't'; goto one_char_escape;
michael@0:       case '\f': c = 't'; goto one_char_escape;
michael@0:       case '\0': c = '0'; goto one_char_escape;
michael@0:       case '\'': goto one_char_escape;
michael@0:       one_char_escape:
michael@0:         *s++ = '\\';
michael@0:         break;
michael@0:       default:
michael@0:         if (!isprint(c)) {
michael@0:             *s++ = '\\';
michael@0:             *s++ = (char)('0' + (0x3 & (((unsigned char)c) >> 6)));
michael@0:             *s++ = (char)('0' + (0x7 & (((unsigned char)c) >> 3)));
michael@0:             c = (char)('0' + (0x7 & ((unsigned char)c)));
michael@0:         }
michael@0:     }
michael@0:     *s++ = c;
michael@0:     *s++ = '\'';
michael@0:     *s = '\0';
michael@0:     assert(s + 1 <= quoted_buffer + MIN_QUOTED_CHAR_BUFFER);
michael@0:     return quoted_buffer;
michael@0: }
michael@0: 
michael@0: static void
michael@0: nl(struct gen_opt *opt)
michael@0: {
michael@0:     putc('\n', opt->output);
michael@0: }
michael@0: 
michael@0: static void
michael@0: indent(struct gen_opt *opt)
michael@0: {
michael@0:     unsigned n = opt->indent_level;
michael@0:     while (n != 0) {
michael@0:         --n;
michael@0:         fputs("    ", opt->output);
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void
michael@0: line(struct gen_opt *opt, const char *format, ...)
michael@0: {
michael@0:     va_list ap;
michael@0: 
michael@0:     indent(opt);
michael@0:     va_start(ap, format);
michael@0:     vfprintf(opt->output, format, ap);
michael@0:     va_end(ap);
michael@0:     nl(opt);
michael@0: }
michael@0: 
michael@0: static void
michael@0: generate_letter_switch_r(struct gen_opt *opt,
michael@0:                          unsigned indexes[], unsigned nelem,
michael@0:                          unsigned columns[], unsigned unprocessed_columns)
michael@0: {
michael@0:     char qbuf[MIN_QUOTED_CHAR_BUFFER];
michael@0: 
michael@0:     assert(nelem != 0);
michael@0:     if (nelem == 1) {
michael@0:         unsigned kw_index = indexes[0];
michael@0:         const char *keyword = keyword_list[kw_index];
michael@0: 
michael@0:         if (unprocessed_columns == 0) {
michael@0:             line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
michael@0:         } else if (unprocessed_columns > opt->char_tail_test_threshold) {
michael@0:             line(opt, "JSKW_TEST_GUESS(%u) /* %s */", kw_index, keyword);
michael@0:         } else {
michael@0:             unsigned i, column;
michael@0: 
michael@0:             indent(opt); p(opt, "if (");
michael@0:             for (i = 0; i != unprocessed_columns; ++i) {
michael@0:                 column = columns[i];
michael@0:                 qchar(keyword[column], qbuf);
michael@0:                 p(opt, "%sJSKW_AT(%u)==%s", (i == 0) ? "" : " && ",
michael@0:                   column, qbuf);
michael@0:             }
michael@0:             p(opt, ") {"); nl(opt);
michael@0:             ++opt->indent_level;
michael@0:             line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
michael@0:             --opt->indent_level;
michael@0:             line(opt, "}");
michael@0:             line(opt, "JSKW_NO_MATCH()");
michael@0:         }
michael@0:     } else {
michael@0:         unsigned optimal_column_index, optimal_column;
michael@0:         unsigned i;
michael@0:         int use_if;
michael@0:         char current;
michael@0: 
michael@0:         assert(unprocessed_columns != 0);
michael@0:         optimal_column_index = find_optimal_switch_column(opt, indexes, nelem,
michael@0:                                                           columns,
michael@0:                                                           unprocessed_columns,
michael@0:                                                           &use_if);
michael@0:         optimal_column = columns[optimal_column_index];
michael@0:         columns[optimal_column_index] = columns[unprocessed_columns - 1];
michael@0: 
michael@0:         if (!use_if)
michael@0:             line(opt, "switch (JSKW_AT(%u)) {", optimal_column);
michael@0: 
michael@0:         current = keyword_list[indexes[0]][optimal_column];
michael@0:         for (i = 0; i != nelem;) {
michael@0:             unsigned same_char_begin = i;
michael@0:             char next = current;
michael@0: 
michael@0:             for (++i; i != nelem; ++i) {
michael@0:                 next = keyword_list[indexes[i]][optimal_column];
michael@0:                 if (next != current)
michael@0:                     break;
michael@0:             }
michael@0:             qchar(current, qbuf);
michael@0:             if (use_if) {
michael@0:                 line(opt, "if (JSKW_AT(%u) == %s) {", optimal_column, qbuf);
michael@0:             } else {
michael@0:                 line(opt, "  case %s:", qbuf);
michael@0:             }
michael@0:             ++opt->indent_level;
michael@0:             generate_letter_switch_r(opt, indexes + same_char_begin,
michael@0:                                      i - same_char_begin,
michael@0:                                      columns, unprocessed_columns - 1);
michael@0:             --opt->indent_level;
michael@0:             if (use_if) {
michael@0:                 line(opt, "}");
michael@0:             }
michael@0:             current = next;
michael@0:         }
michael@0: 
michael@0:         if (!use_if) {
michael@0:             line(opt, "}");
michael@0:         }
michael@0: 
michael@0:         columns[optimal_column_index] = optimal_column;
michael@0: 
michael@0:         line(opt, "JSKW_NO_MATCH()");
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void
michael@0: generate_letter_switch(struct gen_opt *opt,
michael@0:                        unsigned indexes[], unsigned nelem,
michael@0:                        unsigned current_length)
michael@0: {
michael@0:     unsigned *columns;
michael@0:     unsigned i;
michael@0: 
michael@0:     columns = (unsigned *) malloc(sizeof(columns[0]) * current_length);
michael@0:     if (!columns) {
michael@0:         perror("malloc");
michael@0:         exit(EXIT_FAILURE);
michael@0:     }
michael@0:     for (i = 0; i != current_length; ++i) {
michael@0:         columns[i] = i;
michael@0:     }
michael@0:     generate_letter_switch_r(opt, indexes, nelem, columns, current_length);
michael@0:     free(columns);
michael@0: }
michael@0: 
michael@0: 
michael@0: static void
michael@0: generate_switch(struct gen_opt *opt)
michael@0: {
michael@0:     unsigned *indexes;
michael@0:     unsigned nlength;
michael@0:     unsigned i, current;
michael@0:     int use_if;
michael@0:     unsigned nelem;
michael@0: 
michael@0:     nelem = sizeof(keyword_list)/sizeof(keyword_list[0]);
michael@0: 
michael@0:     line(opt, "/*");
michael@0:     line(opt, " * Generating switch for the list of %u entries:", nelem);
michael@0:     for (i = 0; i != nelem; ++i) {
michael@0:         line(opt, " * %s", keyword_list[i]);
michael@0:     }
michael@0:     line(opt, " */");
michael@0: 
michael@0:     indexes = (unsigned *) malloc(sizeof(indexes[0]) * nelem);
michael@0:     if (!indexes) {
michael@0:         perror("malloc");
michael@0:         exit(EXIT_FAILURE);
michael@0:     }
michael@0:     for (i = 0; i != nelem; ++i)
michael@0:         indexes[i] = i;
michael@0:     qsort(indexes, nelem, sizeof(indexes[i]), length_comparator);
michael@0:     nlength = count_different_lengths(indexes, nelem);
michael@0: 
michael@0:     use_if = (nlength <= opt->use_if_threshold);
michael@0: 
michael@0:     if (!use_if)
michael@0:         line(opt, "switch (JSKW_LENGTH()) {");
michael@0: 
michael@0:     current = (unsigned)strlen(keyword_list[indexes[0]]);
michael@0:     for (i = 0; i != nelem;) {
michael@0:         unsigned same_length_begin = i;
michael@0:         unsigned next = current;
michael@0: 
michael@0:         for (++i; i != nelem; ++i) {
michael@0:             next = (unsigned)strlen(keyword_list[indexes[i]]);
michael@0:             if (next != current)
michael@0:                 break;
michael@0:         }
michael@0:         if (use_if) {
michael@0:             line(opt, "if (JSKW_LENGTH() == %u) {", current);
michael@0:         } else {
michael@0:             line(opt, "  case %u:", current);
michael@0:         }
michael@0:         ++opt->indent_level;
michael@0:         generate_letter_switch(opt, indexes + same_length_begin,
michael@0:                                i - same_length_begin,
michael@0:                                current);
michael@0:         --opt->indent_level;
michael@0:         if (use_if) {
michael@0:             line(opt, "}");
michael@0:         }
michael@0:         current = next;
michael@0:     }
michael@0:     if (!use_if)
michael@0:         line(opt, "}");
michael@0:     line(opt, "JSKW_NO_MATCH()");
michael@0:     free(indexes);
michael@0: }
michael@0: 
michael@0: int main(int argc, char **argv)
michael@0: {
michael@0:     struct gen_opt opt;
michael@0: 
michael@0:     if (argc < 2) {
michael@0:         opt.output = stdout;
michael@0:     } else {
michael@0:         opt.output = fopen(argv[1], "w");
michael@0:         if (!opt.output) {
michael@0:             perror("fopen");
michael@0:             exit(EXIT_FAILURE);
michael@0:         }
michael@0:     }
michael@0:     opt.indent_level = 1;
michael@0:     opt.use_if_threshold = 3;
michael@0:     opt.char_tail_test_threshold = 4;
michael@0: 
michael@0:     generate_switch(&opt);
michael@0: 
michael@0:     if (opt.output != stdout) {
michael@0:         if (fclose(opt.output)) {
michael@0:             perror("fclose");
michael@0:             exit(EXIT_FAILURE);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return EXIT_SUCCESS;
michael@0: }