/[jscoverage]/trunk/js/jskwgen.cpp
ViewVC logotype

Contents of /trunk/js/jskwgen.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 507 - (show annotations)
Sun Jan 10 07:23:34 2010 UTC (9 years, 5 months ago) by siliconforks
File size: 13443 byte(s)
Update SpiderMonkey from Firefox 3.6rc1.

1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set sw=4 ts=8 et tw=80:
3 *
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6 *
7 * The contents of this file are subject to the Mozilla Public License Version
8 * 1.1 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
11 *
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14 * for the specific language governing rights and limitations under the
15 * License.
16 *
17 * The Original Code is String Switch Generator for JavaScript Keywords,
18 * released 2005-12-09.
19 *
20 * The Initial Developer of the Original Code is
21 * Igor Bukanov.
22 * Portions created by the Initial Developer are Copyright (C) 2005-2006
23 * the Initial Developer. All Rights Reserved.
24 *
25 * Contributor(s):
26 *
27 * Alternatively, the contents of this file may be used under the terms of
28 * either of the GNU General Public License Version 2 or later (the "GPL"),
29 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30 * in which case the provisions of the GPL or the LGPL are applicable instead
31 * of those above. If you wish to allow use of your version of this file only
32 * under the terms of either the GPL or the LGPL, and not to allow others to
33 * use your version of this file under the terms of the MPL, indicate your
34 * decision by deleting the provisions above and replace them with the notice
35 * and other provisions required by the GPL or the LGPL. If you do not delete
36 * the provisions above, a recipient may use your version of this file under
37 * the terms of any one of the MPL, the GPL or the LGPL.
38 *
39 * ***** END LICENSE BLOCK ***** */
40
41 #include <stddef.h>
42 #include <assert.h>
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46 #include <stdarg.h>
47 #include <ctype.h>
48
49 #include "jsversion.h"
50
51 const char * const keyword_list[] = {
52 #define JS_KEYWORD(keyword, type, op, version) #keyword,
53 #include "jskeyword.tbl"
54 #undef JS_KEYWORD
55 };
56
57 struct gen_opt {
58 FILE *output; /* output file for generated source */
59 unsigned use_if_threshold; /* max number of choices to generate
60 "if" selector instead of "switch" */
61 unsigned char_tail_test_threshold; /* max number of unprocessed columns
62 to use inlined char compare
63 for remaining chars and not generic
64 string compare code */
65 unsigned indent_level; /* current source identation level */
66 };
67
68 static unsigned column_to_compare;
69
70 static int
71 length_comparator(const void *a, const void *b)
72 {
73 const char *str1 = keyword_list[*(unsigned *)a];
74 const char *str2 = keyword_list[*(unsigned *)b];
75 return (int)strlen(str1) - (int)strlen(str2);
76 }
77
78 static int
79 column_comparator(const void *a, const void *b)
80 {
81 const char *str1 = keyword_list[*(unsigned *)a];
82 const char *str2 = keyword_list[*(unsigned *)b];
83 return (int)str1[column_to_compare] - (int)str2[column_to_compare];
84 }
85
86 static unsigned
87 count_different_lengths(unsigned indexes[], unsigned nelem)
88 {
89 unsigned nlength, current_length, i, l;
90
91 current_length = 0;
92 nlength = 0;
93 for (i = 0; i != nelem; ++i) {
94 l = (unsigned)strlen(keyword_list[indexes[i]]);
95 assert(l != 0);
96 if (current_length != l) {
97 ++nlength;
98 current_length = l;
99 }
100 }
101 return nlength;
102 }
103
104 static void
105 find_char_span_and_count(unsigned indexes[], unsigned nelem, unsigned column,
106 unsigned *span_result, unsigned *count_result)
107 {
108 unsigned i, count;
109 unsigned char c, prev, minc, maxc;
110
111 assert(nelem != 0);
112 minc = maxc = prev = (unsigned char)keyword_list[indexes[0]][column];
113 count = 1;
114 for (i = 1; i != nelem; ++i) {
115 c = (unsigned char)keyword_list[indexes[i]][column];
116 if (prev != c) {
117 prev = c;
118 ++count;
119 if (minc > c) {
120 minc = c;
121 } else if (maxc < c) {
122 maxc = c;
123 }
124 }
125 }
126
127 *span_result = maxc - minc + 1;
128 *count_result = count;
129 }
130
131 static unsigned
132 find_optimal_switch_column(struct gen_opt *opt,
133 unsigned indexes[], unsigned nelem,
134 unsigned columns[], unsigned unprocessed_columns,
135 int *use_if_result)
136 {
137 unsigned i;
138 unsigned span, min_span, min_span_index;
139 unsigned nchar, min_nchar, min_nchar_index;
140
141 assert(unprocessed_columns != 0);
142 i = 0;
143 min_nchar = min_span = (unsigned)-1;
144 min_nchar_index = min_span_index = 0;
145 do {
146 column_to_compare = columns[i];
147 qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
148 find_char_span_and_count(indexes, nelem, column_to_compare,
149 &span, &nchar);
150 assert(span != 0);
151 if (span == 1) {
152 assert(nchar == 1);
153 *use_if_result = 1;
154 return 1;
155 }
156 assert(nchar != 1);
157 if (min_span > span) {
158 min_span = span;
159 min_span_index = i;
160 }
161 if (min_nchar > nchar) {
162 min_nchar = nchar;
163 min_nchar_index = i;
164 }
165 } while (++i != unprocessed_columns);
166
167 if (min_nchar <= opt->use_if_threshold) {
168 *use_if_result = 1;
169 i = min_nchar_index;
170 } else {
171 *use_if_result = 0;
172 i = min_span_index;
173 }
174
175 /*
176 * Restore order corresponding to i if it was destroyed by
177 * subsequent sort.
178 */
179 if (i != unprocessed_columns - 1) {
180 column_to_compare = columns[i];
181 qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
182 }
183
184 return i;
185 }
186
187
188 static void
189 p(struct gen_opt *opt, const char *format, ...)
190 {
191 va_list ap;
192
193 va_start(ap, format);
194 vfprintf(opt->output, format, ap);
195 va_end(ap);
196 }
197
198 /* Size for '\xxx' where xxx is octal escape */
199 #define MIN_QUOTED_CHAR_BUFFER 7
200
201 static char *
202 qchar(char c, char *quoted_buffer)
203 {
204 char *s;
205
206 s = quoted_buffer;
207 *s++ = '\'';
208 switch (c) {
209 case '\n': c = 'n'; goto one_char_escape;
210 case '\r': c = 'r'; goto one_char_escape;
211 case '\t': c = 't'; goto one_char_escape;
212 case '\f': c = 't'; goto one_char_escape;
213 case '\0': c = '0'; goto one_char_escape;
214 case '\'': goto one_char_escape;
215 one_char_escape:
216 *s++ = '\\';
217 break;
218 default:
219 if (!isprint(c)) {
220 *s++ = '\\';
221 *s++ = (char)('0' + (0x3 & (((unsigned char)c) >> 6)));
222 *s++ = (char)('0' + (0x7 & (((unsigned char)c) >> 3)));
223 c = (char)('0' + (0x7 & ((unsigned char)c)));
224 }
225 }
226 *s++ = c;
227 *s++ = '\'';
228 *s = '\0';
229 assert(s + 1 <= quoted_buffer + MIN_QUOTED_CHAR_BUFFER);
230 return quoted_buffer;
231 }
232
233 static void
234 nl(struct gen_opt *opt)
235 {
236 putc('\n', opt->output);
237 }
238
239 static void
240 indent(struct gen_opt *opt)
241 {
242 unsigned n = opt->indent_level;
243 while (n != 0) {
244 --n;
245 fputs(" ", opt->output);
246 }
247 }
248
249 static void
250 line(struct gen_opt *opt, const char *format, ...)
251 {
252 va_list ap;
253
254 indent(opt);
255 va_start(ap, format);
256 vfprintf(opt->output, format, ap);
257 va_end(ap);
258 nl(opt);
259 }
260
261 static void
262 generate_letter_switch_r(struct gen_opt *opt,
263 unsigned indexes[], unsigned nelem,
264 unsigned columns[], unsigned unprocessed_columns)
265 {
266 char qbuf[MIN_QUOTED_CHAR_BUFFER];
267
268 assert(nelem != 0);
269 if (nelem == 1) {
270 unsigned kw_index = indexes[0];
271 const char *keyword = keyword_list[kw_index];
272
273 if (unprocessed_columns == 0) {
274 line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
275 } else if (unprocessed_columns > opt->char_tail_test_threshold) {
276 line(opt, "JSKW_TEST_GUESS(%u) /* %s */", kw_index, keyword);
277 } else {
278 unsigned i, column;
279
280 indent(opt); p(opt, "if (");
281 for (i = 0; i != unprocessed_columns; ++i) {
282 column = columns[i];
283 qchar(keyword[column], qbuf);
284 p(opt, "%sJSKW_AT(%u)==%s", (i == 0) ? "" : " && ",
285 column, qbuf);
286 }
287 p(opt, ") {"); nl(opt);
288 ++opt->indent_level;
289 line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
290 --opt->indent_level;
291 line(opt, "}");
292 line(opt, "JSKW_NO_MATCH()");
293 }
294 } else {
295 unsigned optimal_column_index, optimal_column;
296 unsigned i;
297 int use_if;
298 char current;
299
300 assert(unprocessed_columns != 0);
301 optimal_column_index = find_optimal_switch_column(opt, indexes, nelem,
302 columns,
303 unprocessed_columns,
304 &use_if);
305 optimal_column = columns[optimal_column_index];
306 columns[optimal_column_index] = columns[unprocessed_columns - 1];
307
308 if (!use_if)
309 line(opt, "switch (JSKW_AT(%u)) {", optimal_column);
310
311 current = keyword_list[indexes[0]][optimal_column];
312 for (i = 0; i != nelem;) {
313 unsigned same_char_begin = i;
314 char next = current;
315
316 for (++i; i != nelem; ++i) {
317 next = keyword_list[indexes[i]][optimal_column];
318 if (next != current)
319 break;
320 }
321 qchar(current, qbuf);
322 if (use_if) {
323 line(opt, "if (JSKW_AT(%u) == %s) {", optimal_column, qbuf);
324 } else {
325 line(opt, " case %s:", qbuf);
326 }
327 ++opt->indent_level;
328 generate_letter_switch_r(opt, indexes + same_char_begin,
329 i - same_char_begin,
330 columns, unprocessed_columns - 1);
331 --opt->indent_level;
332 if (use_if) {
333 line(opt, "}");
334 }
335 current = next;
336 }
337
338 if (!use_if) {
339 line(opt, "}");
340 }
341
342 columns[optimal_column_index] = optimal_column;
343
344 line(opt, "JSKW_NO_MATCH()");
345 }
346 }
347
348 static void
349 generate_letter_switch(struct gen_opt *opt,
350 unsigned indexes[], unsigned nelem,
351 unsigned current_length)
352 {
353 unsigned *columns;
354 unsigned i;
355
356 columns = (unsigned *) malloc(sizeof(columns[0]) * current_length);
357 if (!columns) {
358 perror("malloc");
359 exit(EXIT_FAILURE);
360 }
361 for (i = 0; i != current_length; ++i) {
362 columns[i] = i;
363 }
364 generate_letter_switch_r(opt, indexes, nelem, columns, current_length);
365 free(columns);
366 }
367
368
369 static void
370 generate_switch(struct gen_opt *opt)
371 {
372 unsigned *indexes;
373 unsigned nlength;
374 unsigned i, current;
375 int use_if;
376 unsigned nelem;
377
378 nelem = sizeof(keyword_list)/sizeof(keyword_list[0]);
379
380 line(opt, "/*");
381 line(opt, " * Generating switch for the list of %u entries:", nelem);
382 for (i = 0; i != nelem; ++i) {
383 line(opt, " * %s", keyword_list[i]);
384 }
385 line(opt, " */");
386
387 indexes = (unsigned *) malloc(sizeof(indexes[0]) * nelem);
388 if (!indexes) {
389 perror("malloc");
390 exit(EXIT_FAILURE);
391 }
392 for (i = 0; i != nelem; ++i)
393 indexes[i] = i;
394 qsort(indexes, nelem, sizeof(indexes[i]), length_comparator);
395 nlength = count_different_lengths(indexes, nelem);
396
397 use_if = (nlength <= opt->use_if_threshold);
398
399 if (!use_if)
400 line(opt, "switch (JSKW_LENGTH()) {");
401
402 current = (unsigned)strlen(keyword_list[indexes[0]]);
403 for (i = 0; i != nelem;) {
404 unsigned same_length_begin = i;
405 unsigned next = current;
406
407 for (++i; i != nelem; ++i) {
408 next = (unsigned)strlen(keyword_list[indexes[i]]);
409 if (next != current)
410 break;
411 }
412 if (use_if) {
413 line(opt, "if (JSKW_LENGTH() == %u) {", current);
414 } else {
415 line(opt, " case %u:", current);
416 }
417 ++opt->indent_level;
418 generate_letter_switch(opt, indexes + same_length_begin,
419 i - same_length_begin,
420 current);
421 --opt->indent_level;
422 if (use_if) {
423 line(opt, "}");
424 }
425 current = next;
426 }
427 if (!use_if)
428 line(opt, "}");
429 line(opt, "JSKW_NO_MATCH()");
430 free(indexes);
431 }
432
433 int main(int argc, char **argv)
434 {
435 struct gen_opt opt;
436
437 if (argc < 2) {
438 opt.output = stdout;
439 } else {
440 opt.output = fopen(argv[1], "w");
441 if (!opt.output) {
442 perror("fopen");
443 exit(EXIT_FAILURE);
444 }
445 }
446 opt.indent_level = 1;
447 opt.use_if_threshold = 3;
448 opt.char_tail_test_threshold = 4;
449
450 generate_switch(&opt);
451
452 if (opt.output != stdout) {
453 if (fclose(opt.output)) {
454 perror("fclose");
455 exit(EXIT_FAILURE);
456 }
457 }
458
459 return EXIT_SUCCESS;
460 }

  ViewVC Help
Powered by ViewVC 1.1.24