From d7c5ad7d6263fd1baf9bfdbaa4c50b70ef2fbdb2 Mon Sep 17 00:00:00 2001 From: Alexander Sulfrian Date: Tue, 8 Jun 2010 08:22:05 +0200 Subject: reverted folder structure change for better mergeing with upstream --- .../javascript/tools/idswitch/SwitchGenerator.java | 491 +++++++++++++++++++++ 1 file changed, 491 insertions(+) create mode 100644 trunk/infrastructure/rhino1_7R1/toolsrc/org/mozilla/javascript/tools/idswitch/SwitchGenerator.java (limited to 'trunk/infrastructure/rhino1_7R1/toolsrc/org/mozilla/javascript/tools/idswitch/SwitchGenerator.java') diff --git a/trunk/infrastructure/rhino1_7R1/toolsrc/org/mozilla/javascript/tools/idswitch/SwitchGenerator.java b/trunk/infrastructure/rhino1_7R1/toolsrc/org/mozilla/javascript/tools/idswitch/SwitchGenerator.java new file mode 100644 index 0000000..3db99d6 --- /dev/null +++ b/trunk/infrastructure/rhino1_7R1/toolsrc/org/mozilla/javascript/tools/idswitch/SwitchGenerator.java @@ -0,0 +1,491 @@ +/* -*- Mode: java; tab-width: 4; indent-tabs-mode: 1; c-basic-offset: 4 -*- + * + * ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is Rhino code, released + * May 6, 1999. + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1997-1999 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * Igor Bukanov + * + * Alternatively, the contents of this file may be used under the terms of + * the GNU General Public License Version 2 or later (the "GPL"), in which + * case the provisions of the GPL are applicable instead of those above. If + * you wish to allow use of your version of this file only under the terms of + * the GPL and not to allow others to use your version of this file under the + * MPL, indicate your decision by deleting the provisions above and replacing + * them with the notice and other provisions required by the GPL. If you do + * not delete the provisions above, a recipient may use your version of this + * file under either the MPL or the GPL. + * + * ***** END LICENSE BLOCK ***** */ +package org.mozilla.javascript.tools.idswitch; + +import org.mozilla.javascript.EvaluatorException; +import org.mozilla.javascript.tools.ToolErrorReporter; + +public class SwitchGenerator { + + String v_switch_label = "L0"; + String v_label = "L"; + String v_s = "s"; + String v_c = "c"; + String v_guess = "X"; + String v_id = "id"; + String v_length_suffix = "_length"; + + int use_if_threshold = 3; + int char_tail_test_threshold = 2; + + private IdValuePair[] pairs; + private String default_value; + private int[] columns; + private boolean c_was_defined; + + private CodePrinter P; + private ToolErrorReporter R; + private String source_file; + + public CodePrinter getCodePrinter() { return P; } + public void setCodePrinter(CodePrinter value) { P = value; } + + public ToolErrorReporter getReporter() { return R; } + public void setReporter(ToolErrorReporter value) { R = value; } + + public String getSourceFileName() { return source_file; } + public void setSourceFileName(String value) { source_file = value; } + + public void generateSwitch(String[] pairs, String default_value) { + int N = pairs.length / 2; + IdValuePair[] id_pairs = new IdValuePair[N]; + for (int i = 0; i != N; ++i) { + id_pairs[i] = new IdValuePair(pairs[2 * i], pairs[2 * i + 1]); + } + generateSwitch(id_pairs, default_value); + + } + + public void generateSwitch(IdValuePair[] pairs, String default_value) { + int begin = 0; + int end = pairs.length; + if (begin == end) { return; } + this.pairs = pairs; + this.default_value = default_value; + + generate_body(begin, end, 2); + } + + private void generate_body(int begin, int end, int indent_level) { + P.indent(indent_level); + P.p(v_switch_label); P.p(": { "); + P.p(v_id); P.p(" = "); P.p(default_value); + P.p("; String "); P.p(v_guess); P.p(" = null;"); + + c_was_defined = false; + int c_def_begin = P.getOffset(); + P.p(" int "); P.p(v_c); P.p(';'); + int c_def_end = P.getOffset(); + P.nl(); + + generate_length_switch(begin, end, indent_level + 1); + + if (!c_was_defined) { + P.erase(c_def_begin, c_def_end); + } + + P.indent(indent_level + 1); + P.p("if ("); P.p(v_guess); P.p("!=null && "); + P.p(v_guess); P.p("!="); P.p(v_s); + P.p(" && !"); P.p(v_guess); P.p(".equals("); P.p(v_s); P.p(")) "); + P.p(v_id); P.p(" = "); P.p(default_value); P.p(";"); P.nl(); + + // Add break at end of block to suppress warning for unused label + P.indent(indent_level + 1); + P.p("break "); P.p(v_switch_label); P.p(";"); P.nl(); + + P.line(indent_level, "}"); + } + + private void generate_length_switch(int begin, int end, int indent_level) { + + sort_pairs(begin, end, -1); + + check_all_is_different(begin, end); + + int lengths_count = count_different_lengths(begin, end); + + columns = new int[pairs[end - 1].idLength]; + + boolean use_if; + if (lengths_count <= use_if_threshold) { + use_if = true; + if (lengths_count != 1) { + P.indent(indent_level); + P.p("int "); P.p(v_s); P.p(v_length_suffix); + P.p(" = "); P.p(v_s); P.p(".length();"); + P.nl(); + } + } + else { + use_if = false; + P.indent(indent_level); + P.p(v_label); P.p(": switch ("); + P.p(v_s); P.p(".length()) {"); + P.nl(); + } + + int same_length_begin = begin; + int cur_l = pairs[begin].idLength, l = 0; + for (int i = begin;;) { + ++i; + if (i == end || (l = pairs[i].idLength) != cur_l) { + int next_indent; + if (use_if) { + P.indent(indent_level); + if (same_length_begin != begin) { P.p("else "); } + P.p("if ("); + if (lengths_count == 1) { + P.p(v_s); P.p(".length()=="); + } + else { + P.p(v_s); P.p(v_length_suffix); P.p("=="); + } + P.p(cur_l); + P.p(") {"); + next_indent = indent_level + 1; + } + else { + P.indent(indent_level); + P.p("case "); P.p(cur_l); P.p(":"); + next_indent = indent_level + 1; + } + generate_letter_switch + (same_length_begin, i, next_indent, !use_if, use_if); + if (use_if) { + P.p("}"); P.nl(); + } + else { + P.p("break "); P.p(v_label); P.p(";"); P.nl(); + } + + if (i == end) { break; } + same_length_begin = i; + cur_l = l; + } + } + + if (!use_if) { + P.indent(indent_level); P.p("}"); P.nl(); + } + + } + + private void generate_letter_switch + (int begin, int end, + int indent_level, boolean label_was_defined, boolean inside_if) + { + int L = pairs[begin].idLength; + + for (int i = 0; i != L; ++i) { + columns[i] = i; + } + + generate_letter_switch_r + (begin, end, L, indent_level, label_was_defined, inside_if); + } + + + private boolean generate_letter_switch_r + (int begin, int end, int L, + int indent_level, boolean label_was_defined, boolean inside_if) + { + boolean next_is_unreachable = false; + if (begin + 1 == end) { + P.p(' '); + IdValuePair pair = pairs[begin]; + if (L > char_tail_test_threshold) { + P.p(v_guess); P.p("="); P.qstring(pair.id); P.p(";"); + P.p(v_id); P.p("="); P.p(pair.value); P.p(";"); + } + else { + if (L == 0) { + next_is_unreachable = true; + P.p(v_id); P.p("="); P.p(pair.value); + P.p("; break "); P.p(v_switch_label); P.p(";"); + } + else { + P.p("if ("); + int column = columns[0]; + P.p(v_s); P.p(".charAt("); P.p(column); P.p(")=="); + P.qchar(pair.id.charAt(column)); + for (int i = 1; i != L; ++i) { + P.p(" && "); + column = columns[i]; + P.p(v_s); P.p(".charAt("); P.p(column); P.p(")=="); + P.qchar(pair.id.charAt(column)); + } + P.p(") {"); + P.p(v_id); P.p("="); P.p(pair.value); + P.p("; break "); P.p(v_switch_label); P.p(";}"); + } + } + P.p(' '); + return next_is_unreachable; + } + + int max_column_index = find_max_different_column(begin, end, L); + int max_column = columns[max_column_index]; + int count = count_different_chars(begin, end, max_column); + + columns[max_column_index] = columns[L - 1]; + + if (inside_if) { P.nl(); P.indent(indent_level); } + else { P.p(' '); } + + boolean use_if; + if (count <= use_if_threshold) { + use_if = true; + c_was_defined = true; + P.p(v_c); P.p("="); P.p(v_s); + P.p(".charAt("); P.p(max_column); P.p(");"); + } + else { + use_if = false; + if (!label_was_defined) { + label_was_defined = true; + P.p(v_label); P.p(": "); + } + P.p("switch ("); P.p(v_s); + P.p(".charAt("); P.p(max_column); P.p(")) {"); + } + + int same_char_begin = begin; + int cur_ch = pairs[begin].id.charAt(max_column), ch = 0; + for (int i = begin;;) { + ++i; + if (i == end || (ch = pairs[i].id.charAt(max_column)) != cur_ch) { + int next_indent; + if (use_if) { + P.nl(); P.indent(indent_level); + if (same_char_begin != begin) { P.p("else "); } + P.p("if ("); P.p(v_c); P.p("=="); + P.qchar(cur_ch); P.p(") {"); + next_indent = indent_level + 1; + } + else { + P.nl(); P.indent(indent_level); + P.p("case "); P.qchar(cur_ch); P.p(":"); + next_indent = indent_level + 1; + } + boolean after_unreachable = generate_letter_switch_r + (same_char_begin, i, L - 1, + next_indent, label_was_defined, use_if); + if (use_if) { + P.p("}"); + } + else { + if (!after_unreachable) { + P.p("break "); P.p(v_label); P.p(";"); + } + } + if (i == end) { break; } + same_char_begin = i; + cur_ch = ch; + } + } + + if (use_if) { + P.nl(); + if (inside_if) { P.indent(indent_level - 1); } + else { P.indent(indent_level); } + } + else { + P.nl(); P.indent(indent_level); P.p("}"); + if (inside_if) { P.nl(); P.indent(indent_level - 1);} + else { P.p(' '); } + } + + columns[max_column_index] = max_column; + + return next_is_unreachable; + } + + + private int count_different_lengths(int begin, int end) { + int lengths_count = 0; + int cur_l = -1; + for (; begin != end; ++begin) { + int l = pairs[begin].idLength; + if (cur_l != l) { + ++lengths_count; cur_l = l; + } + } + return lengths_count; + } + + private int find_max_different_column(int begin, int end, int L) { + int max_count = 0; + int max_index = 0; + + for (int i = 0; i != L; ++i) { + int column = columns[i]; + sort_pairs(begin, end, column); + int count = count_different_chars(begin, end, column); + if (count == end - begin) { return i; } + if (max_count < count) { + max_count = count; + max_index = i; + } + } + + if (max_index != L - 1) { + sort_pairs(begin, end, columns[max_index]); + } + + return max_index; + } + + private int count_different_chars(int begin, int end, int column) { + int chars_count = 0; + int cur_ch = -1; + for (; begin != end; ++begin) { + int ch = pairs[begin].id.charAt(column); + if (ch != cur_ch) { + ++chars_count; cur_ch = ch; + } + } + return chars_count; + } + + private void check_all_is_different(int begin, int end) { + if (begin != end) { + IdValuePair prev = pairs[begin]; + while (++begin != end) { + IdValuePair current = pairs[begin]; + if (prev.id.equals(current.id)) { + throw on_same_pair_fail(prev, current); + } + prev = current; + } + } + } + + private EvaluatorException on_same_pair_fail(IdValuePair a, IdValuePair b) { + int line1 = a.getLineNumber(), line2 = b.getLineNumber(); + if (line2 > line1) { int tmp = line1; line1 = line2; line2 = tmp; } + String error_text = ToolErrorReporter.getMessage( + "msg.idswitch.same_string", a.id, new Integer(line2)); + return R.runtimeError(error_text, source_file, line1, null, 0); + } + + private void sort_pairs(int begin, int end, int comparator) { + heap4Sort(pairs, begin, end - begin, comparator); + } + + private static boolean bigger + (IdValuePair a, IdValuePair b, int comparator) + { + if (comparator < 0) { + // For length selection switch it is enough to compare just length, + // but to detect same strings full comparison is essential + //return a.idLength > b.idLength; + int diff = a.idLength - b.idLength; + if (diff != 0) { return diff > 0; } + return a.id.compareTo(b.id) > 0; + } + else { + return a.id.charAt(comparator) > b.id.charAt(comparator); + } + } + + private static void heap4Sort + (IdValuePair[] array, int offset, int size, int comparator) + { + if (size <= 1) { return; } + makeHeap4(array, offset, size, comparator); + while (size > 1) { + --size; + IdValuePair v1 = array[offset + size]; + IdValuePair v2 = array[offset + 0]; + array[offset + size] = v2; + array[offset + 0] = v1; + heapify4(array, offset, size, 0, comparator); + } + } + + private static void makeHeap4 + (IdValuePair[] array, int offset, int size, int comparator) + { + for (int i = ((size + 2) >> 2); i != 0;) { + --i; + heapify4(array, offset, size, i, comparator); + } + } + + private static void heapify4 + (IdValuePair[] array, int offset, int size, int i, int comparator) + { + int new_i1, new_i2, new_i3; + IdValuePair i_val = array[offset + i]; + for (;;) { + int base = (i << 2); + new_i1 = base | 1; + new_i2 = base | 2; + new_i3 = base | 3; + int new_i4 = base + 4; + if (new_i4 >= size) { break; } + IdValuePair val1 = array[offset + new_i1]; + IdValuePair val2 = array[offset + new_i2]; + IdValuePair val3 = array[offset + new_i3]; + IdValuePair val4 = array[offset + new_i4]; + if (bigger(val2, val1, comparator)) { + val1 = val2; new_i1 = new_i2; + } + if (bigger(val4, val3, comparator)) { + val3 = val4; new_i3 = new_i4; + } + if (bigger(val3, val1, comparator)) { + val1 = val3; new_i1 = new_i3; + } + if (bigger(i_val, val1, comparator)) { return; } + array[offset + i] = val1; + array[offset + new_i1] = i_val; + i = new_i1; + } + if (new_i1 < size) { + IdValuePair val1 = array[offset + new_i1]; + if (new_i2 != size) { + IdValuePair val2 = array[offset + new_i2]; + if (bigger(val2, val1, comparator)) { + val1 = val2; new_i1 = new_i2; + } + if (new_i3 != size) { + IdValuePair val3 = array[offset + new_i3]; + if (bigger(val3, val1, comparator)) { + val1 = val3; new_i1 = new_i3; + } + } + } + if (bigger(val1, i_val, comparator)) { + array[offset + i] = val1; + array[offset + new_i1] = i_val; + } + } + } +} -- cgit v1.2.3