001: /* -*- Mode: java; tab-width: 4; indent-tabs-mode: 1; c-basic-offset: 4 -*-
002: *
003: * ***** BEGIN LICENSE BLOCK *****
004: * Version: MPL 1.1/GPL 2.0
005: *
006: * The contents of this file are subject to the Mozilla Public License Version
007: * 1.1 (the "License"); you may not use this file except in compliance with
008: * the License. You may obtain a copy of the License at
009: * http://www.mozilla.org/MPL/
010: *
011: * Software distributed under the License is distributed on an "AS IS" basis,
012: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
013: * for the specific language governing rights and limitations under the
014: * License.
015: *
016: * The Original Code is Rhino code, released
017: * May 6, 1999.
018: *
019: * The Initial Developer of the Original Code is
020: * Netscape Communications Corporation.
021: * Portions created by the Initial Developer are Copyright (C) 1997-1999
022: * the Initial Developer. All Rights Reserved.
023: *
024: * Contributor(s):
025: * Igor Bukanov
026: *
027: * Alternatively, the contents of this file may be used under the terms of
028: * the GNU General Public License Version 2 or later (the "GPL"), in which
029: * case the provisions of the GPL are applicable instead of those above. If
030: * you wish to allow use of your version of this file only under the terms of
031: * the GPL and not to allow others to use your version of this file under the
032: * MPL, indicate your decision by deleting the provisions above and replacing
033: * them with the notice and other provisions required by the GPL. If you do
034: * not delete the provisions above, a recipient may use your version of this
035: * file under either the MPL or the GPL.
036: *
037: * ***** END LICENSE BLOCK ***** */
038: package org.mozilla.javascript.tools.idswitch;
039:
040: import org.mozilla.javascript.EvaluatorException;
041: import org.mozilla.javascript.tools.ToolErrorReporter;
042:
043: public class SwitchGenerator {
044:
045: String v_switch_label = "L0";
046: String v_label = "L";
047: String v_s = "s";
048: String v_c = "c";
049: String v_guess = "X";
050: String v_id = "id";
051: String v_length_suffix = "_length";
052:
053: int use_if_threshold = 3;
054: int char_tail_test_threshold = 2;
055:
056: private IdValuePair[] pairs;
057: private String default_value;
058: private int[] columns;
059: private boolean c_was_defined;
060:
061: private CodePrinter P;
062: private ToolErrorReporter R;
063: private String source_file;
064:
065: public CodePrinter getCodePrinter() {
066: return P;
067: }
068:
069: public void setCodePrinter(CodePrinter value) {
070: P = value;
071: }
072:
073: public ToolErrorReporter getReporter() {
074: return R;
075: }
076:
077: public void setReporter(ToolErrorReporter value) {
078: R = value;
079: }
080:
081: public String getSourceFileName() {
082: return source_file;
083: }
084:
085: public void setSourceFileName(String value) {
086: source_file = value;
087: }
088:
089: public void generateSwitch(String[] pairs, String default_value) {
090: int N = pairs.length / 2;
091: IdValuePair[] id_pairs = new IdValuePair[N];
092: for (int i = 0; i != N; ++i) {
093: id_pairs[i] = new IdValuePair(pairs[2 * i],
094: pairs[2 * i + 1]);
095: }
096: generateSwitch(id_pairs, default_value);
097:
098: }
099:
100: public void generateSwitch(IdValuePair[] pairs, String default_value) {
101: int begin = 0;
102: int end = pairs.length;
103: if (begin == end) {
104: return;
105: }
106: this .pairs = pairs;
107: this .default_value = default_value;
108:
109: generate_body(begin, end, 2);
110: }
111:
112: private void generate_body(int begin, int end, int indent_level) {
113: P.indent(indent_level);
114: P.p(v_switch_label);
115: P.p(": { ");
116: P.p(v_id);
117: P.p(" = ");
118: P.p(default_value);
119: P.p("; String ");
120: P.p(v_guess);
121: P.p(" = null;");
122:
123: c_was_defined = false;
124: int c_def_begin = P.getOffset();
125: P.p(" int ");
126: P.p(v_c);
127: P.p(';');
128: int c_def_end = P.getOffset();
129: P.nl();
130:
131: generate_length_switch(begin, end, indent_level + 1);
132:
133: if (!c_was_defined) {
134: P.erase(c_def_begin, c_def_end);
135: }
136:
137: P.indent(indent_level + 1);
138: P.p("if (");
139: P.p(v_guess);
140: P.p("!=null && ");
141: P.p(v_guess);
142: P.p("!=");
143: P.p(v_s);
144: P.p(" && !");
145: P.p(v_guess);
146: P.p(".equals(");
147: P.p(v_s);
148: P.p(")) ");
149: P.p(v_id);
150: P.p(" = ");
151: P.p(default_value);
152: P.p(";");
153: P.nl();
154:
155: // Add break at end of block to suppress warning for unused label
156: P.indent(indent_level + 1);
157: P.p("break ");
158: P.p(v_switch_label);
159: P.p(";");
160: P.nl();
161:
162: P.line(indent_level, "}");
163: }
164:
165: private void generate_length_switch(int begin, int end,
166: int indent_level) {
167:
168: sort_pairs(begin, end, -1);
169:
170: check_all_is_different(begin, end);
171:
172: int lengths_count = count_different_lengths(begin, end);
173:
174: columns = new int[pairs[end - 1].idLength];
175:
176: boolean use_if;
177: if (lengths_count <= use_if_threshold) {
178: use_if = true;
179: if (lengths_count != 1) {
180: P.indent(indent_level);
181: P.p("int ");
182: P.p(v_s);
183: P.p(v_length_suffix);
184: P.p(" = ");
185: P.p(v_s);
186: P.p(".length();");
187: P.nl();
188: }
189: } else {
190: use_if = false;
191: P.indent(indent_level);
192: P.p(v_label);
193: P.p(": switch (");
194: P.p(v_s);
195: P.p(".length()) {");
196: P.nl();
197: }
198:
199: int same_length_begin = begin;
200: int cur_l = pairs[begin].idLength, l = 0;
201: for (int i = begin;;) {
202: ++i;
203: if (i == end || (l = pairs[i].idLength) != cur_l) {
204: int next_indent;
205: if (use_if) {
206: P.indent(indent_level);
207: if (same_length_begin != begin) {
208: P.p("else ");
209: }
210: P.p("if (");
211: if (lengths_count == 1) {
212: P.p(v_s);
213: P.p(".length()==");
214: } else {
215: P.p(v_s);
216: P.p(v_length_suffix);
217: P.p("==");
218: }
219: P.p(cur_l);
220: P.p(") {");
221: next_indent = indent_level + 1;
222: } else {
223: P.indent(indent_level);
224: P.p("case ");
225: P.p(cur_l);
226: P.p(":");
227: next_indent = indent_level + 1;
228: }
229: generate_letter_switch(same_length_begin, i,
230: next_indent, !use_if, use_if);
231: if (use_if) {
232: P.p("}");
233: P.nl();
234: } else {
235: P.p("break ");
236: P.p(v_label);
237: P.p(";");
238: P.nl();
239: }
240:
241: if (i == end) {
242: break;
243: }
244: same_length_begin = i;
245: cur_l = l;
246: }
247: }
248:
249: if (!use_if) {
250: P.indent(indent_level);
251: P.p("}");
252: P.nl();
253: }
254:
255: }
256:
257: private void generate_letter_switch(int begin, int end,
258: int indent_level, boolean label_was_defined,
259: boolean inside_if) {
260: int L = pairs[begin].idLength;
261:
262: for (int i = 0; i != L; ++i) {
263: columns[i] = i;
264: }
265:
266: generate_letter_switch_r(begin, end, L, indent_level,
267: label_was_defined, inside_if);
268: }
269:
270: private boolean generate_letter_switch_r(int begin, int end, int L,
271: int indent_level, boolean label_was_defined,
272: boolean inside_if) {
273: boolean next_is_unreachable = false;
274: if (begin + 1 == end) {
275: P.p(' ');
276: IdValuePair pair = pairs[begin];
277: if (L > char_tail_test_threshold) {
278: P.p(v_guess);
279: P.p("=");
280: P.qstring(pair.id);
281: P.p(";");
282: P.p(v_id);
283: P.p("=");
284: P.p(pair.value);
285: P.p(";");
286: } else {
287: if (L == 0) {
288: next_is_unreachable = true;
289: P.p(v_id);
290: P.p("=");
291: P.p(pair.value);
292: P.p("; break ");
293: P.p(v_switch_label);
294: P.p(";");
295: } else {
296: P.p("if (");
297: int column = columns[0];
298: P.p(v_s);
299: P.p(".charAt(");
300: P.p(column);
301: P.p(")==");
302: P.qchar(pair.id.charAt(column));
303: for (int i = 1; i != L; ++i) {
304: P.p(" && ");
305: column = columns[i];
306: P.p(v_s);
307: P.p(".charAt(");
308: P.p(column);
309: P.p(")==");
310: P.qchar(pair.id.charAt(column));
311: }
312: P.p(") {");
313: P.p(v_id);
314: P.p("=");
315: P.p(pair.value);
316: P.p("; break ");
317: P.p(v_switch_label);
318: P.p(";}");
319: }
320: }
321: P.p(' ');
322: return next_is_unreachable;
323: }
324:
325: int max_column_index = find_max_different_column(begin, end, L);
326: int max_column = columns[max_column_index];
327: int count = count_different_chars(begin, end, max_column);
328:
329: columns[max_column_index] = columns[L - 1];
330:
331: if (inside_if) {
332: P.nl();
333: P.indent(indent_level);
334: } else {
335: P.p(' ');
336: }
337:
338: boolean use_if;
339: if (count <= use_if_threshold) {
340: use_if = true;
341: c_was_defined = true;
342: P.p(v_c);
343: P.p("=");
344: P.p(v_s);
345: P.p(".charAt(");
346: P.p(max_column);
347: P.p(");");
348: } else {
349: use_if = false;
350: if (!label_was_defined) {
351: label_was_defined = true;
352: P.p(v_label);
353: P.p(": ");
354: }
355: P.p("switch (");
356: P.p(v_s);
357: P.p(".charAt(");
358: P.p(max_column);
359: P.p(")) {");
360: }
361:
362: int same_char_begin = begin;
363: int cur_ch = pairs[begin].id.charAt(max_column), ch = 0;
364: for (int i = begin;;) {
365: ++i;
366: if (i == end
367: || (ch = pairs[i].id.charAt(max_column)) != cur_ch) {
368: int next_indent;
369: if (use_if) {
370: P.nl();
371: P.indent(indent_level);
372: if (same_char_begin != begin) {
373: P.p("else ");
374: }
375: P.p("if (");
376: P.p(v_c);
377: P.p("==");
378: P.qchar(cur_ch);
379: P.p(") {");
380: next_indent = indent_level + 1;
381: } else {
382: P.nl();
383: P.indent(indent_level);
384: P.p("case ");
385: P.qchar(cur_ch);
386: P.p(":");
387: next_indent = indent_level + 1;
388: }
389: boolean after_unreachable = generate_letter_switch_r(
390: same_char_begin, i, L - 1, next_indent,
391: label_was_defined, use_if);
392: if (use_if) {
393: P.p("}");
394: } else {
395: if (!after_unreachable) {
396: P.p("break ");
397: P.p(v_label);
398: P.p(";");
399: }
400: }
401: if (i == end) {
402: break;
403: }
404: same_char_begin = i;
405: cur_ch = ch;
406: }
407: }
408:
409: if (use_if) {
410: P.nl();
411: if (inside_if) {
412: P.indent(indent_level - 1);
413: } else {
414: P.indent(indent_level);
415: }
416: } else {
417: P.nl();
418: P.indent(indent_level);
419: P.p("}");
420: if (inside_if) {
421: P.nl();
422: P.indent(indent_level - 1);
423: } else {
424: P.p(' ');
425: }
426: }
427:
428: columns[max_column_index] = max_column;
429:
430: return next_is_unreachable;
431: }
432:
433: private int count_different_lengths(int begin, int end) {
434: int lengths_count = 0;
435: int cur_l = -1;
436: for (; begin != end; ++begin) {
437: int l = pairs[begin].idLength;
438: if (cur_l != l) {
439: ++lengths_count;
440: cur_l = l;
441: }
442: }
443: return lengths_count;
444: }
445:
446: private int find_max_different_column(int begin, int end, int L) {
447: int max_count = 0;
448: int max_index = 0;
449:
450: for (int i = 0; i != L; ++i) {
451: int column = columns[i];
452: sort_pairs(begin, end, column);
453: int count = count_different_chars(begin, end, column);
454: if (count == end - begin) {
455: return i;
456: }
457: if (max_count < count) {
458: max_count = count;
459: max_index = i;
460: }
461: }
462:
463: if (max_index != L - 1) {
464: sort_pairs(begin, end, columns[max_index]);
465: }
466:
467: return max_index;
468: }
469:
470: private int count_different_chars(int begin, int end, int column) {
471: int chars_count = 0;
472: int cur_ch = -1;
473: for (; begin != end; ++begin) {
474: int ch = pairs[begin].id.charAt(column);
475: if (ch != cur_ch) {
476: ++chars_count;
477: cur_ch = ch;
478: }
479: }
480: return chars_count;
481: }
482:
483: private void check_all_is_different(int begin, int end) {
484: if (begin != end) {
485: IdValuePair prev = pairs[begin];
486: while (++begin != end) {
487: IdValuePair current = pairs[begin];
488: if (prev.id.equals(current.id)) {
489: throw on_same_pair_fail(prev, current);
490: }
491: prev = current;
492: }
493: }
494: }
495:
496: private EvaluatorException on_same_pair_fail(IdValuePair a,
497: IdValuePair b) {
498: int line1 = a.getLineNumber(), line2 = b.getLineNumber();
499: if (line2 > line1) {
500: int tmp = line1;
501: line1 = line2;
502: line2 = tmp;
503: }
504: String error_text = ToolErrorReporter.getMessage(
505: "msg.idswitch.same_string", a.id, new Integer(line2));
506: return R.runtimeError(error_text, source_file, line1, null, 0);
507: }
508:
509: private void sort_pairs(int begin, int end, int comparator) {
510: heap4Sort(pairs, begin, end - begin, comparator);
511: }
512:
513: private static boolean bigger(IdValuePair a, IdValuePair b,
514: int comparator) {
515: if (comparator < 0) {
516: // For length selection switch it is enough to compare just length,
517: // but to detect same strings full comparison is essential
518: //return a.idLength > b.idLength;
519: int diff = a.idLength - b.idLength;
520: if (diff != 0) {
521: return diff > 0;
522: }
523: return a.id.compareTo(b.id) > 0;
524: } else {
525: return a.id.charAt(comparator) > b.id.charAt(comparator);
526: }
527: }
528:
529: private static void heap4Sort(IdValuePair[] array, int offset,
530: int size, int comparator) {
531: if (size <= 1) {
532: return;
533: }
534: makeHeap4(array, offset, size, comparator);
535: while (size > 1) {
536: --size;
537: IdValuePair v1 = array[offset + size];
538: IdValuePair v2 = array[offset + 0];
539: array[offset + size] = v2;
540: array[offset + 0] = v1;
541: heapify4(array, offset, size, 0, comparator);
542: }
543: }
544:
545: private static void makeHeap4(IdValuePair[] array, int offset,
546: int size, int comparator) {
547: for (int i = ((size + 2) >> 2); i != 0;) {
548: --i;
549: heapify4(array, offset, size, i, comparator);
550: }
551: }
552:
553: private static void heapify4(IdValuePair[] array, int offset,
554: int size, int i, int comparator) {
555: int new_i1, new_i2, new_i3;
556: IdValuePair i_val = array[offset + i];
557: for (;;) {
558: int base = (i << 2);
559: new_i1 = base | 1;
560: new_i2 = base | 2;
561: new_i3 = base | 3;
562: int new_i4 = base + 4;
563: if (new_i4 >= size) {
564: break;
565: }
566: IdValuePair val1 = array[offset + new_i1];
567: IdValuePair val2 = array[offset + new_i2];
568: IdValuePair val3 = array[offset + new_i3];
569: IdValuePair val4 = array[offset + new_i4];
570: if (bigger(val2, val1, comparator)) {
571: val1 = val2;
572: new_i1 = new_i2;
573: }
574: if (bigger(val4, val3, comparator)) {
575: val3 = val4;
576: new_i3 = new_i4;
577: }
578: if (bigger(val3, val1, comparator)) {
579: val1 = val3;
580: new_i1 = new_i3;
581: }
582: if (bigger(i_val, val1, comparator)) {
583: return;
584: }
585: array[offset + i] = val1;
586: array[offset + new_i1] = i_val;
587: i = new_i1;
588: }
589: if (new_i1 < size) {
590: IdValuePair val1 = array[offset + new_i1];
591: if (new_i2 != size) {
592: IdValuePair val2 = array[offset + new_i2];
593: if (bigger(val2, val1, comparator)) {
594: val1 = val2;
595: new_i1 = new_i2;
596: }
597: if (new_i3 != size) {
598: IdValuePair val3 = array[offset + new_i3];
599: if (bigger(val3, val1, comparator)) {
600: val1 = val3;
601: new_i1 = new_i3;
602: }
603: }
604: }
605: if (bigger(val1, i_val, comparator)) {
606: array[offset + i] = val1;
607: array[offset + new_i1] = i_val;
608: }
609: }
610: }
611: }
|