001: /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
002: *
003: * The contents of this file are subject to the Netscape Public
004: * License Version 1.1 (the "License"); you may not use this file
005: * except in compliance with the License. You may obtain a copy of
006: * the License at http://www.mozilla.org/NPL/
007: *
008: * Software distributed under the License is distributed on an "AS
009: * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
010: * implied. See the License for the specific language governing
011: * rights and limitations under the License.
012: *
013: * The Original Code is Rhino code, released
014: * May 6, 1999.
015: *
016: * The Initial Developer of the Original Code is Netscape
017: * Communications Corporation. Portions created by Netscape are
018: * Copyright (C) 1997-1999 Netscape Communications Corporation. All
019: * Rights Reserved.
020: *
021: * Contributor(s):
022: * Norris Boyd
023: * Roger Lawrence
024: * Mike McCabe
025: *
026: * Alternatively, the contents of this file may be used under the
027: * terms of the GNU Public License (the "GPL"), in which case the
028: * provisions of the GPL are applicable instead of those above.
029: * If you wish to allow use of your version of this file only
030: * under the terms of the GPL and not to allow others to use your
031: * version of this file under the NPL, indicate your decision by
032: * deleting the provisions above and replace them with the notice
033: * and other provisions required by the GPL. If you do not delete
034: * the provisions above, a recipient may use your version of this
035: * file under either the NPL or the GPL.
036: */
037: // Modified by Google
038: package com.google.gwt.dev.js.rhino;
039:
040: /**
041: * This class implements the root of the intermediate representation.
042: *
043: * @author Norris Boyd
044: * @author Mike McCabe
045: */
046:
047: public class Node implements Cloneable {
048:
049: private static class NumberNode extends Node {
050:
051: NumberNode(double number) {
052: super (TokenStream.NUMBER);
053: this .number = number;
054: }
055:
056: public double getDouble() {
057: return this .number;
058: }
059:
060: public boolean equals(Object o) {
061: return o instanceof NumberNode
062: && getDouble() == ((NumberNode) o).getDouble();
063: }
064:
065: private double number;
066: }
067:
068: private static class StringNode extends Node {
069:
070: StringNode(int type, String str) {
071: super (type);
072: if (null == str) {
073: throw new IllegalArgumentException(
074: "StringNode: str is null");
075: }
076: this .str = str;
077: }
078:
079: /** returns the string content.
080: * @return non null.
081: */
082: public String getString() {
083: return this .str;
084: }
085:
086: /** sets the string content.
087: * @param str the new value. Non null.
088: */
089: public void setString(String str) {
090: if (null == str) {
091: throw new IllegalArgumentException(
092: "StringNode: str is null");
093: }
094: this .str = str;
095: }
096:
097: public boolean equals(Object o) {
098: if (!(o instanceof StringNode)) {
099: return false;
100: }
101: return o instanceof StringNode
102: && this .str.equals(((StringNode) o).str);
103: }
104:
105: private String str;
106: }
107:
108: public Node(int nodeType) {
109: type = nodeType;
110: }
111:
112: public Node(int nodeType, Node child) {
113: type = nodeType;
114: first = last = child;
115: child.next = null;
116: }
117:
118: public Node(int nodeType, Node left, Node right) {
119: type = nodeType;
120: first = left;
121: last = right;
122: left.next = right;
123: right.next = null;
124: }
125:
126: public Node(int nodeType, Node left, Node mid, Node right) {
127: type = nodeType;
128: first = left;
129: last = right;
130: left.next = mid;
131: mid.next = right;
132: right.next = null;
133: }
134:
135: public Node(int nodeType, Node left, Node mid, Node mid2, Node right) {
136: type = nodeType;
137: first = left;
138: last = right;
139: left.next = mid;
140: mid.next = mid2;
141: mid2.next = right;
142: right.next = null;
143: }
144:
145: public Node(int nodeType, Node[] children) {
146: this .type = nodeType;
147: if (children.length != 0) {
148: this .first = children[0];
149: this .last = children[children.length - 1];
150:
151: for (int i = 1; i < children.length; i++) {
152: if (null != children[i - 1].next) {
153: // fail early on loops. implies same node in array twice
154: throw new IllegalArgumentException(
155: "duplicate child");
156: }
157: children[i - 1].next = children[i];
158: }
159: if (null != this .last.next) {
160: // fail early on loops. implies same node in array twice
161: throw new IllegalArgumentException("duplicate child");
162: }
163: }
164: }
165:
166: public Node(int nodeType, int value) {
167: type = nodeType;
168: intDatum = value;
169: }
170:
171: public Node(int nodeType, Node child, int value) {
172: this (nodeType, child);
173: intDatum = value;
174: }
175:
176: public Node(int nodeType, Node left, Node right, int value) {
177: this (nodeType, left, right);
178: intDatum = value;
179: }
180:
181: public Node(int nodeType, Node left, Node mid, Node right, int value) {
182: this (nodeType, left, mid, right);
183: intDatum = value;
184: }
185:
186: public static Node newNumber(double number) {
187: return new NumberNode(number);
188: }
189:
190: public static Node newString(String str) {
191: return new StringNode(TokenStream.STRING, str);
192: }
193:
194: public static Node newString(int type, String str) {
195: return new StringNode(type, str);
196: }
197:
198: public int getType() {
199: return type;
200: }
201:
202: public void setType(int type) {
203: this .type = type;
204: }
205:
206: public int getIntDatum() {
207: return this .intDatum;
208: }
209:
210: public boolean hasChildren() {
211: return first != null;
212: }
213:
214: public Node getFirstChild() {
215: return first;
216: }
217:
218: public Node getLastChild() {
219: return last;
220: }
221:
222: public Node getNext() {
223: return next;
224: }
225:
226: public int getChildCount() {
227: int c = 0;
228: for (Node n = first; n != null; n = n.next)
229: c++;
230:
231: return c;
232: }
233:
234: public Node getChildBefore(Node child) {
235: if (child == first)
236: return null;
237: Node n = first;
238: while (n.next != child) {
239: n = n.next;
240: if (n == null)
241: throw new RuntimeException("node is not a child");
242: }
243: return n;
244: }
245:
246: public Node getLastSibling() {
247: Node n = this ;
248: while (n.next != null) {
249: n = n.next;
250: }
251: return n;
252: }
253:
254: public void addChildToFront(Node child) {
255: child.next = first;
256: first = child;
257: if (last == null) {
258: last = child;
259: }
260: }
261:
262: public void addChildToBack(Node child) {
263: child.next = null;
264: if (last == null) {
265: first = last = child;
266: return;
267: }
268: last.next = child;
269: last = child;
270: }
271:
272: public void addChildrenToFront(Node children) {
273: Node lastSib = children.getLastSibling();
274: lastSib.next = first;
275: first = children;
276: if (last == null) {
277: last = lastSib;
278: }
279: }
280:
281: public void addChildrenToBack(Node children) {
282: if (last != null) {
283: last.next = children;
284: }
285: last = children.getLastSibling();
286: if (first == null) {
287: first = children;
288: }
289: }
290:
291: /**
292: * Add 'child' before 'node'.
293: */
294: public void addChildBefore(Node newChild, Node node) {
295: if (newChild.next != null)
296: throw new RuntimeException(
297: "newChild had siblings in addChildBefore");
298: if (first == node) {
299: newChild.next = first;
300: first = newChild;
301: return;
302: }
303: Node prev = getChildBefore(node);
304: addChildAfter(newChild, prev);
305: }
306:
307: /**
308: * Add 'child' after 'node'.
309: */
310: public void addChildAfter(Node newChild, Node node) {
311: if (newChild.next != null)
312: throw new RuntimeException(
313: "newChild had siblings in addChildAfter");
314: newChild.next = node.next;
315: node.next = newChild;
316: if (last == node)
317: last = newChild;
318: }
319:
320: public void removeChild(Node child) {
321: Node prev = getChildBefore(child);
322: if (prev == null)
323: first = first.next;
324: else
325: prev.next = child.next;
326: if (child == last)
327: last = prev;
328: child.next = null;
329: }
330:
331: public void replaceChild(Node child, Node newChild) {
332: newChild.next = child.next;
333: if (child == first) {
334: first = newChild;
335: } else {
336: Node prev = getChildBefore(child);
337: prev.next = newChild;
338: }
339: if (child == last)
340: last = newChild;
341: child.next = null;
342: }
343:
344: public void replaceChildAfter(Node prevChild, Node newChild) {
345: Node child = prevChild.next;
346: newChild.next = child.next;
347: prevChild.next = newChild;
348: if (child == last)
349: last = newChild;
350: child.next = null;
351: }
352:
353: public static final int TARGET_PROP = 1, BREAK_PROP = 2,
354: CONTINUE_PROP = 3, ENUM_PROP = 4, FUNCTION_PROP = 5,
355: TEMP_PROP = 6, LOCAL_PROP = 7, CODEOFFSET_PROP = 8,
356: FIXUPS_PROP = 9, VARS_PROP = 10, USES_PROP = 11,
357: REGEXP_PROP = 12, CASES_PROP = 13, DEFAULT_PROP = 14,
358: CASEARRAY_PROP = 15, SOURCENAME_PROP = 16,
359: SOURCE_PROP = 17, TYPE_PROP = 18, SPECIAL_PROP_PROP = 19,
360: LABEL_PROP = 20, FINALLY_PROP = 21, LOCALCOUNT_PROP = 22,
361: /*
362: the following properties are defined and manipulated by the
363: optimizer -
364: TARGETBLOCK_PROP - the block referenced by a branch node
365: VARIABLE_PROP - the variable referenced by a BIND or NAME node
366: LASTUSE_PROP - that variable node is the last reference before
367: a new def or the end of the block
368: ISNUMBER_PROP - this node generates code on Number children and
369: delivers a Number result (as opposed to Objects)
370: DIRECTCALL_PROP - this call node should emit code to test the function
371: object against the known class and call diret if it
372: matches.
373: */
374:
375: TARGETBLOCK_PROP = 23, VARIABLE_PROP = 24,
376: LASTUSE_PROP = 25, ISNUMBER_PROP = 26,
377: DIRECTCALL_PROP = 27,
378:
379: BASE_LINENO_PROP = 28, END_LINENO_PROP = 29,
380: SPECIALCALL_PROP = 30, DEBUGSOURCE_PROP = 31;
381:
382: public static final int // this value of the ISNUMBER_PROP specifies
383: BOTH = 0, // which of the children are Number types
384: LEFT = 1, RIGHT = 2;
385:
386: private static final String propToString(int propType) {
387: switch (propType) {
388: case TARGET_PROP:
389: return "target";
390: case BREAK_PROP:
391: return "break";
392: case CONTINUE_PROP:
393: return "continue";
394: case ENUM_PROP:
395: return "enum";
396: case FUNCTION_PROP:
397: return "function";
398: case TEMP_PROP:
399: return "temp";
400: case LOCAL_PROP:
401: return "local";
402: case CODEOFFSET_PROP:
403: return "codeoffset";
404: case FIXUPS_PROP:
405: return "fixups";
406: case VARS_PROP:
407: return "vars";
408: case USES_PROP:
409: return "uses";
410: case REGEXP_PROP:
411: return "regexp";
412: case CASES_PROP:
413: return "cases";
414: case DEFAULT_PROP:
415: return "default";
416: case CASEARRAY_PROP:
417: return "casearray";
418: case SOURCENAME_PROP:
419: return "sourcename";
420: case SOURCE_PROP:
421: return "source";
422: case TYPE_PROP:
423: return "type";
424: case SPECIAL_PROP_PROP:
425: return "special_prop";
426: case LABEL_PROP:
427: return "label";
428: case FINALLY_PROP:
429: return "finally";
430: case LOCALCOUNT_PROP:
431: return "localcount";
432:
433: case TARGETBLOCK_PROP:
434: return "targetblock";
435: case VARIABLE_PROP:
436: return "variable";
437: case LASTUSE_PROP:
438: return "lastuse";
439: case ISNUMBER_PROP:
440: return "isnumber";
441: case DIRECTCALL_PROP:
442: return "directcall";
443:
444: case BASE_LINENO_PROP:
445: return "base_lineno";
446: case END_LINENO_PROP:
447: return "end_lineno";
448: case SPECIALCALL_PROP:
449: return "specialcall";
450: case DEBUGSOURCE_PROP:
451: return "debugsource";
452:
453: default:
454: Context.codeBug();
455:
456: }
457: return null;
458: }
459:
460: public Object getProp(int propType) {
461: if (props == null)
462: return null;
463: return props.getObject(propType);
464: }
465:
466: public int getIntProp(int propType, int defaultValue) {
467: if (props == null)
468: return defaultValue;
469: return props.getInt(propType, defaultValue);
470: }
471:
472: public int getExistingIntProp(int propType) {
473: return props.getExistingInt(propType);
474: }
475:
476: public void putProp(int propType, Object prop) {
477: if (prop == null) {
478: removeProp(propType);
479: } else {
480: if (props == null) {
481: props = new UintMap(2);
482: }
483: props.put(propType, prop);
484: }
485: }
486:
487: public void putIntProp(int propType, int prop) {
488: if (props == null)
489: props = new UintMap(2);
490: props.put(propType, prop);
491: }
492:
493: public void removeProp(int propType) {
494: if (props != null) {
495: props.remove(propType);
496: }
497: }
498:
499: public int getOperation() {
500: switch (type) {
501: case TokenStream.EQOP:
502: case TokenStream.RELOP:
503: case TokenStream.UNARYOP:
504: case TokenStream.PRIMARY:
505: return intDatum;
506: }
507: Context.codeBug();
508: return 0;
509: }
510:
511: public int getLineno() {
512: if (hasLineno()) {
513: return intDatum;
514: }
515: return -1;
516: }
517:
518: private boolean hasLineno() {
519: switch (type) {
520: case TokenStream.EXPRSTMT:
521: case TokenStream.BLOCK:
522: case TokenStream.VAR:
523: case TokenStream.WHILE:
524: case TokenStream.DO:
525: case TokenStream.SWITCH:
526: case TokenStream.CATCH:
527: case TokenStream.THROW:
528: case TokenStream.RETURN:
529: case TokenStream.BREAK:
530: case TokenStream.CONTINUE:
531: case TokenStream.WITH:
532: return true;
533: }
534: return false;
535: }
536:
537: /** Can only be called when <tt>getType() == TokenStream.NUMBER</tt> */
538: public double getDouble() throws UnsupportedOperationException {
539: throw new UnsupportedOperationException(this
540: + " is not a number node");
541: }
542:
543: /** Can only be called when node has String context. */
544: public String getString() throws UnsupportedOperationException {
545: throw new UnsupportedOperationException(this
546: + " is not a string node");
547: }
548:
549: /** Can only be called when node has String context. */
550: public void setString(String s)
551: throws UnsupportedOperationException {
552: throw new UnsupportedOperationException(this
553: + " is not a string node");
554: }
555:
556: /**
557: * Not usefully implemented.
558: */
559: public final int hashCode() {
560: assert false : "hashCode not designed";
561: return 42; // any arbitrary constant will do
562: }
563:
564: public boolean equals(Object o) {
565: if (!(o instanceof Node)) {
566: return false;
567: }
568: return hasLineno()
569: || this .getIntDatum() == ((Node) o).getIntDatum();
570: }
571:
572: public Node cloneNode() {
573: Node result;
574: try {
575: result = (Node) super .clone();
576: result.next = null;
577: result.first = null;
578: result.last = null;
579: } catch (CloneNotSupportedException e) {
580: throw new RuntimeException(e.getMessage());
581: }
582: return result;
583: }
584:
585: public Node cloneTree() {
586: Node result = cloneNode();
587: for (Node n2 = getFirstChild(); n2 != null; n2 = n2.getNext()) {
588: Node n2clone = n2.cloneTree();
589: if (result.last != null) {
590: result.last.next = n2clone;
591: }
592: if (result.first == null) {
593: result.first = n2clone;
594: }
595: result.last = n2clone;
596: }
597: return result;
598: }
599:
600: public String toString() {
601: if (Context.printTrees) {
602: StringBuffer sb = new StringBuffer(TokenStream
603: .tokenToName(type));
604: if (this instanceof StringNode) {
605: sb.append(' ');
606: sb.append(getString());
607: } else {
608: switch (type) {
609: case TokenStream.TARGET:
610: sb.append(' ');
611: sb.append(hashCode());
612: break;
613: case TokenStream.NUMBER:
614: sb.append(' ');
615: sb.append(getDouble());
616: break;
617: case TokenStream.FUNCTION:
618: sb.append(' ');
619: sb.append(first.getString());
620: break;
621: }
622: }
623: if (intDatum != -1) {
624: sb.append(' ');
625: sb.append(intDatum);
626: }
627: if (props == null)
628: return sb.toString();
629:
630: int[] keys = props.getKeys();
631: for (int i = 0; i != keys.length; ++i) {
632: int key = keys[i];
633: sb.append(" [");
634: sb.append(propToString(key));
635: sb.append(": ");
636: switch (key) {
637: case FIXUPS_PROP: // can't add this as it recurses
638: sb.append("fixups property");
639: break;
640: case SOURCE_PROP: // can't add this as it has unprintables
641: sb.append("source property");
642: break;
643: case TARGETBLOCK_PROP: // can't add this as it recurses
644: sb.append("target block property");
645: break;
646: case LASTUSE_PROP: // can't add this as it is dull
647: sb.append("last use property");
648: break;
649: default:
650: Object obj = props.getObject(key);
651: if (obj != null) {
652: sb.append(obj.toString());
653: } else {
654: sb.append(props.getExistingInt(key));
655: }
656: break;
657: }
658: sb.append(']');
659: }
660: return sb.toString();
661: }
662: return null;
663: }
664:
665: public String toStringTree() {
666: return toStringTreeHelper(0);
667: }
668:
669: private String toStringTreeHelper(int level) {
670: if (Context.printTrees) {
671: StringBuffer s = new StringBuffer();
672: for (int i = 0; i < level; i++) {
673: s.append(" ");
674: }
675: s.append(toString());
676: s.append('\n');
677: for (Node cursor = getFirstChild(); cursor != null; cursor = cursor
678: .getNext()) {
679: Node n = cursor;
680: s.append(n.toStringTreeHelper(level + 1));
681: }
682: return s.toString();
683: }
684: return "";
685: }
686:
687: /**
688: * Checks if the subtree under this node is the same as another subtree.
689: * Returns null if it's equal, or a message describing the differences.
690: */
691: public String checkTreeEquals(Node node2) {
692: boolean eq = false;
693:
694: if (type == node2.getType()
695: && getChildCount() == node2.getChildCount()
696: && getClass() == node2.getClass()) {
697:
698: eq = this .equals(node2);
699: }
700:
701: if (!eq) {
702: return "Node tree inequality:\nTree1:\n"
703: + toStringTreeHelper(1) + "\n\nTree2:\n"
704: + node2.toStringTreeHelper(1);
705: }
706:
707: String res = null;
708: Node n, n2;
709: for (n = first, n2 = node2.first; res == null && n != null; n = n.next, n2 = n2.next) {
710: res = n.checkTreeEquals(n2);
711: if (res != null) {
712: return res;
713: }
714: }
715: return res;
716: }
717:
718: public void setIsSyntheticBlock(boolean val) {
719: isSyntheticBlock = val;
720: }
721:
722: public boolean isSyntheticBlock() {
723: return isSyntheticBlock;
724: }
725:
726: int type; // type of the node; TokenStream.NAME for example
727: Node next; // next sibling
728: private Node first; // first element of a linked list of children
729: private Node last; // last element of a linked list of children
730: private int intDatum = -1; // encapsulated int data; depends on type
731: private UintMap props;
732: private boolean isSyntheticBlock = false;
733: }
|