0001: /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
0002: *
0003: * ***** BEGIN LICENSE BLOCK *****
0004: * Version: MPL 1.1/GPL 2.0
0005: *
0006: * The contents of this file are subject to the Mozilla Public License Version
0007: * 1.1 (the "License"); you may not use this file except in compliance with
0008: * the License. You may obtain a copy of the License at
0009: * http://www.mozilla.org/MPL/
0010: *
0011: * Software distributed under the License is distributed on an "AS IS" basis,
0012: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
0013: * for the specific language governing rights and limitations under the
0014: * License.
0015: *
0016: * The Original Code is Rhino code, released
0017: * May 6, 1999.
0018: *
0019: * The Initial Developer of the Original Code is
0020: * Netscape Communications Corporation.
0021: * Portions created by the Initial Developer are Copyright (C) 1997-1999
0022: * the Initial Developer. All Rights Reserved.
0023: *
0024: * Contributor(s):
0025: * Norris Boyd
0026: * Roshan James
0027: * Roger Lawrence
0028: * Mike McCabe
0029: *
0030: * Alternatively, the contents of this file may be used under the terms of
0031: * the GNU General Public License Version 2 or later (the "GPL"), in which
0032: * case the provisions of the GPL are applicable instead of those above. If
0033: * you wish to allow use of your version of this file only under the terms of
0034: * the GPL and not to allow others to use your version of this file under the
0035: * MPL, indicate your decision by deleting the provisions above and replacing
0036: * them with the notice and other provisions required by the GPL. If you do
0037: * not delete the provisions above, a recipient may use your version of this
0038: * file under either the MPL or the GPL.
0039: *
0040: * ***** END LICENSE BLOCK ***** */
0041:
0042: package org.mozilla.javascript;
0043:
0044: /**
0045: * This class implements the root of the intermediate representation.
0046: *
0047: * @author Norris Boyd
0048: * @author Mike McCabe
0049: */
0050:
0051: public class Node {
0052: public static final int FUNCTION_PROP = 1, LOCAL_PROP = 2,
0053: LOCAL_BLOCK_PROP = 3, REGEXP_PROP = 4, CASEARRAY_PROP = 5,
0054: /*
0055: the following properties are defined and manipulated by the
0056: optimizer -
0057: TARGETBLOCK_PROP - the block referenced by a branch node
0058: VARIABLE_PROP - the variable referenced by a BIND or NAME node
0059: ISNUMBER_PROP - this node generates code on Number children and
0060: delivers a Number result (as opposed to Objects)
0061: DIRECTCALL_PROP - this call node should emit code to test the function
0062: object against the known class and call diret if it
0063: matches.
0064: */
0065:
0066: TARGETBLOCK_PROP = 6, VARIABLE_PROP = 7, ISNUMBER_PROP = 8,
0067: DIRECTCALL_PROP = 9, SPECIALCALL_PROP = 10,
0068: SKIP_INDEXES_PROP = 11, // array of skipped indexes of array literal
0069: OBJECT_IDS_PROP = 12, // array of properties for object literal
0070: INCRDECR_PROP = 13, // pre or post type of increment/decerement
0071: CATCH_SCOPE_PROP = 14, // index of catch scope block in catch
0072: LABEL_ID_PROP = 15, // label id: code generation uses it
0073: MEMBER_TYPE_PROP = 16, // type of element access operation
0074: NAME_PROP = 17, // property name
0075: CONTROL_BLOCK_PROP = 18, // flags a control block that can drop off
0076: PARENTHESIZED_PROP = 19, // expression is parenthesized
0077: LAST_PROP = 19;
0078:
0079: // values of ISNUMBER_PROP to specify
0080: // which of the children are Number types
0081: public static final int BOTH = 0, LEFT = 1, RIGHT = 2;
0082:
0083: public static final int // values for SPECIALCALL_PROP
0084: NON_SPECIALCALL = 0,
0085: SPECIALCALL_EVAL = 1, SPECIALCALL_WITH = 2;
0086:
0087: public static final int // flags for INCRDECR_PROP
0088: DECR_FLAG = 0x1,
0089: POST_FLAG = 0x2;
0090:
0091: public static final int // flags for MEMBER_TYPE_PROP
0092: PROPERTY_FLAG = 0x1, // property access: element is valid name
0093: ATTRIBUTE_FLAG = 0x2, // x.@y or x..@y
0094: DESCENDANTS_FLAG = 0x4; // x..y or x..@i
0095:
0096: // <netbeans>
0097: //private
0098: public// </netbeans>
0099: static class NumberNode extends Node {
0100: NumberNode(double number) {
0101: super (Token.NUMBER);
0102: this .number = number;
0103: }
0104:
0105: double number;
0106: }
0107:
0108: // <netbeans>
0109: //private
0110: public// </netbeans>
0111: static class StringNode extends Node {
0112: StringNode(int type, String str) {
0113: super (type);
0114: this .str = str;
0115: }
0116:
0117: String str;
0118: }
0119:
0120: // <netbeans>
0121: // Used for object literals: the labels are assigned one of these
0122: // nodes (such that names can be tracked by the IDE)
0123: public static class LabelledNode extends StringNode {
0124: LabelledNode(String name, Node labelledNode) {
0125: super (Token.OBJLITNAME, name);
0126: assert labelledNode != null;
0127: this .labelledNode = labelledNode;
0128: }
0129:
0130: public Node getLabelledNode() {
0131: return labelledNode;
0132: }
0133:
0134: private Node labelledNode;
0135: }
0136:
0137: // </netbeans>
0138:
0139: public static class Jump extends Node {
0140: public Jump(int type) {
0141: super (type);
0142: }
0143:
0144: Jump(int type, int lineno) {
0145: super (type, lineno);
0146: }
0147:
0148: Jump(int type, Node child) {
0149: super (type, child);
0150: }
0151:
0152: Jump(int type, Node child, int lineno) {
0153: super (type, child, lineno);
0154: }
0155:
0156: public final Jump getJumpStatement() {
0157: if (!(type == Token.BREAK || type == Token.CONTINUE))
0158: Kit.codeBug();
0159: return jumpNode;
0160: }
0161:
0162: public final void setJumpStatement(Jump jumpStatement) {
0163: if (!(type == Token.BREAK || type == Token.CONTINUE))
0164: Kit.codeBug();
0165: if (jumpStatement == null)
0166: Kit.codeBug();
0167: if (this .jumpNode != null)
0168: Kit.codeBug(); //only once
0169: this .jumpNode = jumpStatement;
0170: }
0171:
0172: public final Node getDefault() {
0173: if (!(type == Token.SWITCH))
0174: Kit.codeBug();
0175: return target2;
0176: }
0177:
0178: public final void setDefault(Node defaultTarget) {
0179: if (!(type == Token.SWITCH))
0180: Kit.codeBug();
0181: if (defaultTarget.type != Token.TARGET)
0182: Kit.codeBug();
0183: if (target2 != null)
0184: Kit.codeBug(); //only once
0185: target2 = defaultTarget;
0186: }
0187:
0188: public final Node getFinally() {
0189: if (!(type == Token.TRY))
0190: Kit.codeBug();
0191: return target2;
0192: }
0193:
0194: public final void setFinally(Node finallyTarget) {
0195: if (!(type == Token.TRY))
0196: Kit.codeBug();
0197: if (finallyTarget.type != Token.TARGET)
0198: Kit.codeBug();
0199: if (target2 != null)
0200: Kit.codeBug(); //only once
0201: target2 = finallyTarget;
0202: }
0203:
0204: public final Jump getLoop() {
0205: if (!(type == Token.LABEL))
0206: Kit.codeBug();
0207: return jumpNode;
0208: }
0209:
0210: public final void setLoop(Jump loop) {
0211: if (!(type == Token.LABEL))
0212: Kit.codeBug();
0213: if (loop == null)
0214: Kit.codeBug();
0215: if (jumpNode != null)
0216: Kit.codeBug(); //only once
0217: jumpNode = loop;
0218: }
0219:
0220: public final Node getContinue() {
0221: if (type != Token.LOOP)
0222: Kit.codeBug();
0223: return target2;
0224: }
0225:
0226: public final void setContinue(Node continueTarget) {
0227: if (type != Token.LOOP)
0228: Kit.codeBug();
0229: if (continueTarget.type != Token.TARGET)
0230: Kit.codeBug();
0231: if (target2 != null)
0232: Kit.codeBug(); //only once
0233: target2 = continueTarget;
0234: }
0235:
0236: public Node target;
0237: private Node target2;
0238: private Jump jumpNode;
0239: }
0240:
0241: private static class PropListItem {
0242: PropListItem next;
0243: int type;
0244: int intValue;
0245: Object objectValue;
0246: }
0247:
0248: public Node(int nodeType) {
0249: type = nodeType;
0250: }
0251:
0252: public Node(int nodeType, Node child) {
0253: type = nodeType;
0254: first = last = child;
0255: child.next = null;
0256: // <netbeans>
0257: sourceStart = child.sourceStart;
0258: sourceEnd = child.sourceEnd;
0259: // </netbeans>
0260: }
0261:
0262: public Node(int nodeType, Node left, Node right) {
0263: type = nodeType;
0264: first = left;
0265: last = right;
0266: left.next = right;
0267: right.next = null;
0268: // <netbeans>
0269: //assert left.sourceEnd <= right.sourceStart : left + "," + right;
0270: if (left.sourceEnd > 0 && right.sourceStart > 0) {
0271: sourceStart = left.sourceStart;
0272: sourceEnd = right.sourceEnd;
0273: }
0274: // </netbeans>
0275: }
0276:
0277: public Node(int nodeType, Node left, Node mid, Node right) {
0278: type = nodeType;
0279: first = left;
0280: last = right;
0281: left.next = mid;
0282: mid.next = right;
0283: right.next = null;
0284: // <netbeans>
0285: if (left.sourceEnd > 0 && right.sourceStart > 0) {
0286: sourceStart = left.sourceStart;
0287: sourceEnd = right.sourceEnd;
0288: }
0289:
0290: // assert left.sourceEnd <= right.sourceStart : left + "," + right;
0291: // assert mid.sourceStart >= left.sourceEnd : mid + "," + left;
0292: // assert mid.sourceEnd <= right.sourceStart : mid + "," + right;
0293: //sourceStart = left.sourceStart;
0294: //sourceEnd = right.sourceEnd;
0295: // </netbeans>
0296: }
0297:
0298: public Node(int nodeType, int line) {
0299: type = nodeType;
0300: lineno = line;
0301: }
0302:
0303: public Node(int nodeType, Node child, int line) {
0304: this (nodeType, child);
0305: lineno = line;
0306: }
0307:
0308: public Node(int nodeType, Node left, Node right, int line) {
0309: this (nodeType, left, right);
0310: lineno = line;
0311: }
0312:
0313: public Node(int nodeType, Node left, Node mid, Node right, int line) {
0314: this (nodeType, left, mid, right);
0315: lineno = line;
0316: }
0317:
0318: public static Node newNumber(double number) {
0319: return new NumberNode(number);
0320: }
0321:
0322: public static Node newString(String str) {
0323: return new StringNode(Token.STRING, str);
0324: }
0325:
0326: public static Node newString(int type, String str) {
0327: return new StringNode(type, str);
0328: }
0329:
0330: public int getType() {
0331: return type;
0332: }
0333:
0334: public void setType(int type) {
0335: this .type = type;
0336: }
0337:
0338: public boolean hasChildren() {
0339: return first != null;
0340: }
0341:
0342: public Node getFirstChild() {
0343: return first;
0344: }
0345:
0346: public Node getLastChild() {
0347: return last;
0348: }
0349:
0350: public Node getNext() {
0351: return next;
0352: }
0353:
0354: public Node getChildBefore(Node child) {
0355: if (child == first)
0356: return null;
0357: Node n = first;
0358: while (n.next != child) {
0359: n = n.next;
0360: if (n == null)
0361: throw new RuntimeException("node is not a child");
0362: }
0363: return n;
0364: }
0365:
0366: public Node getLastSibling() {
0367: Node n = this ;
0368: while (n.next != null) {
0369: n = n.next;
0370: }
0371: return n;
0372: }
0373:
0374: public void addChildToFront(Node child) {
0375: child.next = first;
0376: first = child;
0377: if (last == null) {
0378: last = child;
0379: }
0380:
0381: // <netbeans>
0382: if (sourceStart > child.sourceStart) {
0383: if (sourceStart == sourceEnd && sourceStart == 0) {
0384: sourceEnd = child.sourceEnd;
0385: }
0386: sourceStart = child.sourceStart;
0387: }
0388: // </netbeans>
0389: }
0390:
0391: public void addChildToBack(Node child) {
0392: child.next = null;
0393: if (last == null) {
0394: first = last = child;
0395:
0396: // <netbeans>
0397: if (sourceEnd < child.sourceEnd) {
0398: if (sourceStart == sourceEnd && sourceStart == 0) {
0399: sourceStart = child.sourceStart;
0400: }
0401: sourceEnd = child.sourceEnd;
0402: }
0403: // </netbeans>
0404: return;
0405: }
0406: last.next = child;
0407: last = child;
0408:
0409: // <netbeans>
0410: if (sourceEnd < child.sourceEnd) {
0411: if (sourceStart == sourceEnd && sourceStart == 0) {
0412: sourceStart = child.sourceStart;
0413: }
0414: sourceEnd = child.sourceEnd;
0415: }
0416: // </netbeans>
0417: }
0418:
0419: public void addChildrenToFront(Node children) {
0420: // <netbeans>
0421: if (sourceStart > children.sourceStart) {
0422: if (sourceStart == sourceEnd && sourceStart == 0) {
0423: sourceEnd = children.getLastSibling().sourceStart;
0424: }
0425: sourceStart = children.sourceStart;
0426: }
0427: // </netbeans>
0428:
0429: Node lastSib = children.getLastSibling();
0430: lastSib.next = first;
0431: first = children;
0432: if (last == null) {
0433: last = lastSib;
0434: }
0435: }
0436:
0437: public void addChildrenToBack(Node children) {
0438: if (last != null) {
0439: last.next = children;
0440: }
0441: last = children.getLastSibling();
0442: if (first == null) {
0443: first = children;
0444: }
0445: // <netbeans>
0446: if (sourceEnd < last.sourceEnd) {
0447: if (sourceStart == sourceEnd && sourceStart == 0) {
0448: sourceStart = first.sourceStart;
0449: }
0450: sourceEnd = last.sourceEnd;
0451: }
0452: // </netbeans>
0453: }
0454:
0455: /**
0456: * Add 'child' before 'node'.
0457: */
0458: public void addChildBefore(Node newChild, Node node) {
0459: if (newChild.next != null)
0460: throw new RuntimeException(
0461: "newChild had siblings in addChildBefore");
0462: if (first == node) {
0463: newChild.next = first;
0464: first = newChild;
0465: return;
0466: }
0467: Node prev = getChildBefore(node);
0468: addChildAfter(newChild, prev);
0469: // <netbeans>
0470: // This doesn't always work - in dojo.uncompressed I have some
0471: // Jump statements that aren't initialized.
0472: // Try setting the initial value of the source offsets to -1
0473: // to detect this.
0474: // if (sourceStart > newChild.sourceStart) {
0475: // sourceStart = newChild.sourceStart;
0476: // }
0477: // assert sourceEnd >= newChild.sourceEnd : newChild;
0478: // </netbeans>
0479: }
0480:
0481: /**
0482: * Add 'child' after 'node'.
0483: */
0484: public void addChildAfter(Node newChild, Node node) {
0485: if (newChild.next != null)
0486: throw new RuntimeException(
0487: "newChild had siblings in addChildAfter");
0488: newChild.next = node.next;
0489: node.next = newChild;
0490: if (last == node)
0491: last = newChild;
0492: // <netbeans>
0493: // This doesn't always work - in dojo.uncompressed I have some
0494: // Jump statements that aren't initialized.
0495: // Try setting the initial value of the source offsets to -1
0496: // to detect this.
0497: // if (sourceEnd < last.sourceEnd) {
0498: // sourceEnd = last.sourceEnd;
0499: // }
0500: // assert sourceStart <= newChild.sourceStart : newChild;
0501: // </netbeans>
0502: }
0503:
0504: public void removeChild(Node child) {
0505: Node prev = getChildBefore(child);
0506: if (prev == null)
0507: first = first.next;
0508: else
0509: prev.next = child.next;
0510: if (child == last)
0511: last = prev;
0512: child.next = null;
0513: // <netbeans>
0514: // Do I have to adjust offsets here? There shouldn't be any removeChild calls during parsing!
0515: // </netbeans>
0516: }
0517:
0518: public void replaceChild(Node child, Node newChild) {
0519: newChild.next = child.next;
0520: if (child == first) {
0521: first = newChild;
0522: } else {
0523: Node prev = getChildBefore(child);
0524: prev.next = newChild;
0525: }
0526: if (child == last)
0527: last = newChild;
0528: child.next = null;
0529: // <netbeans>
0530: // Do I have to adjust offsets here? There shouldn't be any replaceChild calls during parsing!
0531: // </netbeans>
0532: }
0533:
0534: public void replaceChildAfter(Node prevChild, Node newChild) {
0535: Node child = prevChild.next;
0536: newChild.next = child.next;
0537: prevChild.next = newChild;
0538: if (child == last)
0539: last = newChild;
0540: child.next = null;
0541: // <netbeans>
0542: // Do I have to adjust offsets here? There shouldn't be any replaceChildAfter calls during parsing!
0543: // </netbeans>
0544: }
0545:
0546: private static final String propToString(int propType) {
0547: if (Token.printTrees) {
0548: // If Context.printTrees is false, the compiler
0549: // can remove all these strings.
0550: switch (propType) {
0551: case FUNCTION_PROP:
0552: return "function";
0553: case LOCAL_PROP:
0554: return "local";
0555: case LOCAL_BLOCK_PROP:
0556: return "local_block";
0557: case REGEXP_PROP:
0558: return "regexp";
0559: case CASEARRAY_PROP:
0560: return "casearray";
0561:
0562: case TARGETBLOCK_PROP:
0563: return "targetblock";
0564: case VARIABLE_PROP:
0565: return "variable";
0566: case ISNUMBER_PROP:
0567: return "isnumber";
0568: case DIRECTCALL_PROP:
0569: return "directcall";
0570:
0571: case SPECIALCALL_PROP:
0572: return "specialcall";
0573: case SKIP_INDEXES_PROP:
0574: return "skip_indexes";
0575: case OBJECT_IDS_PROP:
0576: return "object_ids_prop";
0577: case INCRDECR_PROP:
0578: return "incrdecr_prop";
0579: case CATCH_SCOPE_PROP:
0580: return "catch_scope_prop";
0581: case LABEL_ID_PROP:
0582: return "label_id_prop";
0583: case MEMBER_TYPE_PROP:
0584: return "member_type_prop";
0585: case NAME_PROP:
0586: return "name_prop";
0587: case CONTROL_BLOCK_PROP:
0588: return "control_block_prop";
0589: case PARENTHESIZED_PROP:
0590: return "parenthesized_prop";
0591:
0592: default:
0593: Kit.codeBug();
0594: }
0595: }
0596: return null;
0597: }
0598:
0599: private PropListItem lookupProperty(int propType) {
0600: PropListItem x = propListHead;
0601: while (x != null && propType != x.type) {
0602: x = x.next;
0603: }
0604: return x;
0605: }
0606:
0607: private PropListItem ensureProperty(int propType) {
0608: PropListItem item = lookupProperty(propType);
0609: if (item == null) {
0610: item = new PropListItem();
0611: item.type = propType;
0612: item.next = propListHead;
0613: propListHead = item;
0614: }
0615: return item;
0616: }
0617:
0618: public void removeProp(int propType) {
0619: PropListItem x = propListHead;
0620: if (x != null) {
0621: PropListItem prev = null;
0622: while (x.type != propType) {
0623: prev = x;
0624: x = x.next;
0625: if (x == null) {
0626: return;
0627: }
0628: }
0629: if (prev == null) {
0630: propListHead = x.next;
0631: } else {
0632: prev.next = x.next;
0633: }
0634: }
0635: }
0636:
0637: public Object getProp(int propType) {
0638: PropListItem item = lookupProperty(propType);
0639: if (item == null) {
0640: return null;
0641: }
0642: return item.objectValue;
0643: }
0644:
0645: public int getIntProp(int propType, int defaultValue) {
0646: PropListItem item = lookupProperty(propType);
0647: if (item == null) {
0648: return defaultValue;
0649: }
0650: return item.intValue;
0651: }
0652:
0653: public int getExistingIntProp(int propType) {
0654: PropListItem item = lookupProperty(propType);
0655: if (item == null) {
0656: Kit.codeBug();
0657: }
0658: return item.intValue;
0659: }
0660:
0661: public void putProp(int propType, Object prop) {
0662: if (prop == null) {
0663: removeProp(propType);
0664: } else {
0665: PropListItem item = ensureProperty(propType);
0666: item.objectValue = prop;
0667: }
0668: }
0669:
0670: public void putIntProp(int propType, int prop) {
0671: PropListItem item = ensureProperty(propType);
0672: item.intValue = prop;
0673: }
0674:
0675: public int getLineno() {
0676: return lineno;
0677: }
0678:
0679: /** Can only be called when <tt>getType() == Token.NUMBER</tt> */
0680: public final double getDouble() {
0681: return ((NumberNode) this ).number;
0682: }
0683:
0684: public final void setDouble(double number) {
0685: ((NumberNode) this ).number = number;
0686: }
0687:
0688: /** Can only be called when node has String context. */
0689: public final String getString() {
0690: return ((StringNode) this ).str;
0691: }
0692:
0693: /** Can only be called when node has String context. */
0694: public final void setString(String s) {
0695: if (s == null)
0696: Kit.codeBug();
0697: ((StringNode) this ).str = s;
0698: }
0699:
0700: public static Node newTarget() {
0701: return new Node(Token.TARGET);
0702: }
0703:
0704: public final int labelId() {
0705: if (type != Token.TARGET)
0706: Kit.codeBug();
0707: return getIntProp(LABEL_ID_PROP, -1);
0708: }
0709:
0710: public void labelId(int labelId) {
0711: if (type != Token.TARGET)
0712: Kit.codeBug();
0713: putIntProp(LABEL_ID_PROP, labelId);
0714: }
0715:
0716: /**
0717: * Does consistent-return analysis on the function body when strict mode is
0718: * enabled.
0719: *
0720: * function (x) { return (x+1) }
0721: * is ok, but
0722: * function (x) { if (x < 0) return (x+1); }
0723: * is not becuase the function can potentially return a value when the
0724: * condition is satisfied and if not, the function does not explicitly
0725: * return value.
0726: *
0727: * This extends to checking mismatches such as "return" and "return <value>"
0728: * used in the same function. Warnings are not emitted if inconsistent
0729: * returns exist in code that can be statically shown to be unreachable.
0730: * Ex.
0731: * function (x) { while (true) { ... if (..) { return value } ... } }
0732: * emits no warning. However if the loop had a break statement, then a
0733: * warning would be emitted.
0734: *
0735: * The consistency analysis looks at control structures such as loops, ifs,
0736: * switch, try-catch-finally blocks, examines the reachable code paths and
0737: * warns the user about an inconsistent set of termination possibilities.
0738: *
0739: * Caveat: Since the parser flattens many control structures into almost
0740: * straight-line code with gotos, it makes such analysis hard. Hence this
0741: * analyser is written to taken advantage of patterns of code generated by
0742: * the parser (for loops, try blocks and such) and does not do a full
0743: * control flow analysis of the gotos and break/continue statements.
0744: * Future changes to the parser will affect this analysis.
0745: */
0746:
0747: /**
0748: * These flags enumerate the possible ways a statement/function can
0749: * terminate. These flags are used by endCheck() and by the Parser to
0750: * detect inconsistent return usage.
0751: *
0752: * END_UNREACHED is reserved for code paths that are assumed to always be
0753: * able to execute (example: throw, continue)
0754: *
0755: * END_DROPS_OFF indicates if the statement can transfer control to the
0756: * next one. Statement such as return dont. A compound statement may have
0757: * some branch that drops off control to the next statement.
0758: *
0759: * END_RETURNS indicates that the statement can return (without arguments)
0760: * END_RETURNS_VALUE indicates that the statement can return a value.
0761: *
0762: * A compound statement such as
0763: * if (condition) {
0764: * return value;
0765: * }
0766: * Will be detected as (END_DROPS_OFF | END_RETURN_VALUE) by endCheck()
0767: */
0768: static final int END_UNREACHED = 0;
0769: static final int END_DROPS_OFF = 1;
0770: static final int END_RETURNS = 2;
0771: static final int END_RETURNS_VALUE = 4;
0772:
0773: /**
0774: * Checks that every return usage in a function body is consistent with the
0775: * requirements of strict-mode.
0776: * @return true if the function satisfies strict mode requirement.
0777: */
0778: public boolean hasConsistentReturnUsage() {
0779: int n = endCheck();
0780: return (n & END_RETURNS_VALUE) == 0
0781: || (n & (END_DROPS_OFF | END_RETURNS)) == 0;
0782: }
0783:
0784: /**
0785: * Returns in the then and else blocks must be consistent with each other.
0786: * If there is no else block, then the return statement can fall through.
0787: * @return logical OR of END_* flags
0788: */
0789: private int endCheckIf() {
0790: Node th, el;
0791: int rv = END_UNREACHED;
0792:
0793: th = next;
0794: el = ((Jump) this ).target;
0795:
0796: rv = th.endCheck();
0797:
0798: if (el != null)
0799: rv |= el.endCheck();
0800: else
0801: rv |= END_DROPS_OFF;
0802:
0803: return rv;
0804: }
0805:
0806: /**
0807: * Consistency of return statements is checked between the case statements.
0808: * If there is no default, then the switch can fall through. If there is a
0809: * default,we check to see if all code paths in the default return or if
0810: * there is a code path that can fall through.
0811: * @return logical OR of END_* flags
0812: */
0813: private int endCheckSwitch() {
0814: Node n;
0815: int rv = END_UNREACHED;
0816:
0817: // examine the cases
0818: for (n = first.next; n != null; n = n.next) {
0819: if (n.type == Token.CASE) {
0820: rv |= ((Jump) n).target.endCheck();
0821: } else
0822: break;
0823: }
0824:
0825: // we don't care how the cases drop into each other
0826: rv &= ~END_DROPS_OFF;
0827:
0828: // examine the default
0829: n = ((Jump) this ).getDefault();
0830: if (n != null)
0831: rv |= n.endCheck();
0832: else
0833: rv |= END_DROPS_OFF;
0834:
0835: // remove the switch block
0836: rv |= getIntProp(CONTROL_BLOCK_PROP, END_UNREACHED);
0837:
0838: return rv;
0839: }
0840:
0841: /**
0842: * If the block has a finally, return consistency is checked in the
0843: * finally block. If all code paths in the finally returns, then the
0844: * returns in the try-catch blocks don't matter. If there is a code path
0845: * that does not return or if there is no finally block, the returns
0846: * of the try and catch blocks are checked for mismatch.
0847: * @return logical OR of END_* flags
0848: */
0849: private int endCheckTry() {
0850: Node n;
0851: int rv = END_UNREACHED;
0852:
0853: // check the finally if it exists
0854: n = ((Jump) this ).getFinally();
0855: if (n != null) {
0856: rv = n.next.first.endCheck();
0857: } else {
0858: rv = END_DROPS_OFF;
0859: }
0860:
0861: // if the finally block always returns, then none of the returns
0862: // in the try or catch blocks matter
0863: if ((rv & END_DROPS_OFF) != 0) {
0864: rv &= ~END_DROPS_OFF;
0865:
0866: // examine the try block
0867: rv |= first.endCheck();
0868:
0869: // check each catch block
0870: n = ((Jump) this ).target;
0871: if (n != null) {
0872: // point to the first catch_scope
0873: for (n = n.next.first; n != null; n = n.next.next) {
0874: // check the block of user code in the catch_scope
0875: rv |= n.next.first.next.first.endCheck();
0876: }
0877: }
0878: }
0879:
0880: return rv;
0881: }
0882:
0883: /**
0884: * Return statement in the loop body must be consistent. The default
0885: * assumption for any kind of a loop is that it will eventually terminate.
0886: * The only exception is a loop with a constant true condition. Code that
0887: * follows such a loop is examined only if one can statically determine
0888: * that there is a break out of the loop.
0889: * for(<> ; <>; <>) {}
0890: * for(<> in <> ) {}
0891: * while(<>) { }
0892: * do { } while(<>)
0893: * @return logical OR of END_* flags
0894: */
0895: private int endCheckLoop() {
0896: Node n;
0897: int rv = END_UNREACHED;
0898:
0899: // To find the loop body, we look at the second to last node of the
0900: // loop node, which should be the predicate that the loop should
0901: // satisfy.
0902: // The target of the predicate is the loop-body for all 4 kinds of
0903: // loops.
0904: for (n = first; n.next != last; n = n.next)
0905: /* skip */;
0906: if (n.type != Token.IFEQ)
0907: return END_DROPS_OFF;
0908:
0909: // The target's next is the loop body block
0910: rv = ((Jump) n).target.next.endCheck();
0911:
0912: // check to see if the loop condition is true
0913: if (n.first.type == Token.TRUE)
0914: rv &= ~END_DROPS_OFF;
0915:
0916: // look for effect of breaks
0917: rv |= getIntProp(CONTROL_BLOCK_PROP, END_UNREACHED);
0918:
0919: return rv;
0920: }
0921:
0922: /**
0923: * A general block of code is examined statement by statement. If any
0924: * statement (even compound ones) returns in all branches, then subsequent
0925: * statements are not examined.
0926: * @return logical OR of END_* flags
0927: */
0928: private int endCheckBlock() {
0929: Node n;
0930: int rv = END_DROPS_OFF;
0931:
0932: // check each statment and if the statement can continue onto the next
0933: // one, then check the next statement
0934: for (n = first; ((rv & END_DROPS_OFF) != 0) && n != null; n = n.next) {
0935: rv &= ~END_DROPS_OFF;
0936: rv |= n.endCheck();
0937: }
0938: return rv;
0939: }
0940:
0941: /**
0942: * A labelled statement implies that there maybe a break to the label. The
0943: * function processes the labelled statement and then checks the
0944: * CONTROL_BLOCK_PROP property to see if there is ever a break to the
0945: * particular label.
0946: * @return logical OR of END_* flags
0947: */
0948: private int endCheckLabel() {
0949: int rv = END_UNREACHED;
0950:
0951: rv = next.endCheck();
0952: rv |= getIntProp(CONTROL_BLOCK_PROP, END_UNREACHED);
0953:
0954: return rv;
0955: }
0956:
0957: /**
0958: * When a break is encountered annotate the statement being broken
0959: * out of by setting its CONTROL_BLOCK_PROP property.
0960: * @return logical OR of END_* flags
0961: */
0962: private int endCheckBreak() {
0963: Node n = ((Jump) this ).jumpNode;
0964: n.putIntProp(CONTROL_BLOCK_PROP, END_DROPS_OFF);
0965: return END_UNREACHED;
0966: }
0967:
0968: /**
0969: * endCheck() examines the body of a function, doing a basic reachability
0970: * analysis and returns a combination of flags END_* flags that indicate
0971: * how the function execution can terminate. These constitute only the
0972: * pessimistic set of termination conditions. It is possible that at
0973: * runtime certain code paths will never be actually taken. Hence this
0974: * analysis will flag errors in cases where there may not be errors.
0975: * @return logical OR of END_* flags
0976: */
0977: private int endCheck() {
0978: switch (type) {
0979: case Token.BREAK:
0980: return endCheckBreak();
0981:
0982: case Token.CONTINUE:
0983: case Token.THROW:
0984: return END_UNREACHED;
0985:
0986: case Token.RETURN:
0987: if (this .first != null)
0988: return END_RETURNS_VALUE;
0989: else
0990: return END_RETURNS;
0991:
0992: case Token.TARGET:
0993: if (next != null)
0994: return next.endCheck();
0995: else
0996: return END_DROPS_OFF;
0997:
0998: case Token.LOOP:
0999: return endCheckLoop();
1000:
1001: case Token.LOCAL_BLOCK:
1002: case Token.BLOCK:
1003: // there are several special kinds of blocks
1004: if (first == null)
1005: return END_DROPS_OFF;
1006:
1007: switch (first.type) {
1008: case Token.LABEL:
1009: return first.endCheckLabel();
1010:
1011: case Token.IFNE:
1012: return first.endCheckIf();
1013:
1014: case Token.SWITCH:
1015: return first.endCheckSwitch();
1016:
1017: case Token.TRY:
1018: return first.endCheckTry();
1019:
1020: default:
1021: return endCheckBlock();
1022: }
1023:
1024: default:
1025: return END_DROPS_OFF;
1026: }
1027: }
1028:
1029: public boolean hasSideEffects() {
1030: switch (type) {
1031: case Token.EXPR_VOID:
1032: case Token.COMMA:
1033: if (last != null)
1034: return last.hasSideEffects();
1035: else
1036: return true;
1037:
1038: case Token.HOOK:
1039: if (first == null || first.next == null
1040: || first.next.next == null)
1041: Kit.codeBug();
1042: return first.next.hasSideEffects()
1043: && first.next.next.hasSideEffects();
1044:
1045: case Token.ERROR: // Avoid cascaded error messages
1046: case Token.EXPR_RESULT:
1047: case Token.ASSIGN:
1048: case Token.ASSIGN_ADD:
1049: case Token.ASSIGN_SUB:
1050: case Token.ASSIGN_MUL:
1051: case Token.ASSIGN_DIV:
1052: case Token.ASSIGN_MOD:
1053: case Token.ASSIGN_BITOR:
1054: case Token.ASSIGN_BITXOR:
1055: case Token.ASSIGN_BITAND:
1056: case Token.ASSIGN_LSH:
1057: case Token.ASSIGN_RSH:
1058: case Token.ASSIGN_URSH:
1059: case Token.ENTERWITH:
1060: case Token.LEAVEWITH:
1061: case Token.RETURN:
1062: case Token.GOTO:
1063: case Token.IFEQ:
1064: case Token.IFNE:
1065: case Token.NEW:
1066: case Token.DELPROP:
1067: case Token.SETNAME:
1068: case Token.SETPROP:
1069: case Token.SETELEM:
1070: case Token.CALL:
1071: case Token.THROW:
1072: case Token.RETHROW:
1073: case Token.SETVAR:
1074: case Token.CATCH_SCOPE:
1075: case Token.RETURN_RESULT:
1076: case Token.SET_REF:
1077: case Token.DEL_REF:
1078: case Token.REF_CALL:
1079: case Token.TRY:
1080: case Token.SEMI:
1081: case Token.INC:
1082: case Token.DEC:
1083: case Token.EXPORT:
1084: case Token.IMPORT:
1085: case Token.IF:
1086: case Token.ELSE:
1087: case Token.SWITCH:
1088: case Token.WHILE:
1089: case Token.DO:
1090: case Token.FOR:
1091: case Token.BREAK:
1092: case Token.CONTINUE:
1093: case Token.VAR:
1094: case Token.CONST:
1095: case Token.WITH:
1096: case Token.CATCH:
1097: case Token.FINALLY:
1098: case Token.BLOCK:
1099: case Token.LABEL:
1100: case Token.TARGET:
1101: case Token.LOOP:
1102: case Token.JSR:
1103: case Token.SETPROP_OP:
1104: case Token.SETELEM_OP:
1105: case Token.LOCAL_BLOCK:
1106: case Token.SET_REF_OP:
1107: return true;
1108:
1109: default:
1110: return false;
1111: }
1112: }
1113:
1114: public String toString() {
1115: if (Token.printTrees) {
1116: StringBuffer sb = new StringBuffer();
1117: toString(new ObjToIntMap(), sb);
1118: return sb.toString();
1119: }
1120: // <netbeans>
1121: //return String.valueOf(type);
1122: String s = "";
1123: if (this instanceof StringNode) {
1124: s = "(\"" + getString() + "\")";
1125: }
1126: return String.valueOf(type) + ":" + Token.fullName(type) + s
1127: + "[" + sourceStart + "," + sourceEnd + "]" + "<"
1128: + Integer.toHexString(System.identityHashCode(this ))
1129: + ">";
1130: // </netbeans>
1131: }
1132:
1133: private void toString(ObjToIntMap printIds, StringBuffer sb) {
1134: if (Token.printTrees) {
1135: sb.append(Token.name(type));
1136: if (this instanceof StringNode) {
1137: sb.append(' ');
1138: sb.append(getString());
1139: } else if (this instanceof ScriptOrFnNode) {
1140: ScriptOrFnNode sof = (ScriptOrFnNode) this ;
1141: if (this instanceof FunctionNode) {
1142: FunctionNode fn = (FunctionNode) this ;
1143: sb.append(' ');
1144: sb.append(fn.getFunctionName());
1145: }
1146: sb.append(" [source name: ");
1147: sb.append(sof.getSourceName());
1148: sb.append("] [encoded source length: ");
1149: sb.append(sof.getEncodedSourceEnd()
1150: - sof.getEncodedSourceStart());
1151: sb.append("] [base line: ");
1152: sb.append(sof.getBaseLineno());
1153: sb.append("] [end line: ");
1154: sb.append(sof.getEndLineno());
1155: sb.append(']');
1156: } else if (this instanceof Jump) {
1157: Jump jump = (Jump) this ;
1158: if (type == Token.BREAK || type == Token.CONTINUE) {
1159: sb.append(" [label: ");
1160: appendPrintId(jump.getJumpStatement(), printIds, sb);
1161: sb.append(']');
1162: } else if (type == Token.TRY) {
1163: Node catchNode = jump.target;
1164: Node finallyTarget = jump.getFinally();
1165: if (catchNode != null) {
1166: sb.append(" [catch: ");
1167: appendPrintId(catchNode, printIds, sb);
1168: sb.append(']');
1169: }
1170: if (finallyTarget != null) {
1171: sb.append(" [finally: ");
1172: appendPrintId(finallyTarget, printIds, sb);
1173: sb.append(']');
1174: }
1175: } else if (type == Token.LABEL || type == Token.LOOP
1176: || type == Token.SWITCH) {
1177: sb.append(" [break: ");
1178: appendPrintId(jump.target, printIds, sb);
1179: sb.append(']');
1180: if (type == Token.LOOP) {
1181: sb.append(" [continue: ");
1182: appendPrintId(jump.getContinue(), printIds, sb);
1183: sb.append(']');
1184: }
1185: } else {
1186: sb.append(" [target: ");
1187: appendPrintId(jump.target, printIds, sb);
1188: sb.append(']');
1189: }
1190: } else if (type == Token.NUMBER) {
1191: sb.append(' ');
1192: sb.append(getDouble());
1193: } else if (type == Token.TARGET) {
1194: sb.append(' ');
1195: appendPrintId(this , printIds, sb);
1196: }
1197: if (lineno != -1) {
1198: sb.append(' ');
1199: sb.append(lineno);
1200: }
1201:
1202: for (PropListItem x = propListHead; x != null; x = x.next) {
1203: int type = x.type;
1204: sb.append(" [");
1205: sb.append(propToString(type));
1206: sb.append(": ");
1207: String value;
1208: switch (type) {
1209: case TARGETBLOCK_PROP: // can't add this as it recurses
1210: value = "target block property";
1211: break;
1212: case LOCAL_BLOCK_PROP: // can't add this as it is dull
1213: value = "last local block";
1214: break;
1215: case ISNUMBER_PROP:
1216: switch (x.intValue) {
1217: case BOTH:
1218: value = "both";
1219: break;
1220: case RIGHT:
1221: value = "right";
1222: break;
1223: case LEFT:
1224: value = "left";
1225: break;
1226: default:
1227: throw Kit.codeBug();
1228: }
1229: break;
1230: case SPECIALCALL_PROP:
1231: switch (x.intValue) {
1232: case SPECIALCALL_EVAL:
1233: value = "eval";
1234: break;
1235: case SPECIALCALL_WITH:
1236: value = "with";
1237: break;
1238: default:
1239: // NON_SPECIALCALL should not be stored
1240: throw Kit.codeBug();
1241: }
1242: break;
1243: default:
1244: Object obj = x.objectValue;
1245: if (obj != null) {
1246: value = obj.toString();
1247: } else {
1248: value = String.valueOf(x.intValue);
1249: }
1250: break;
1251: }
1252: sb.append(value);
1253: sb.append(']');
1254: }
1255: }
1256: }
1257:
1258: public String toStringTree(ScriptOrFnNode treeTop) {
1259: if (Token.printTrees) {
1260: StringBuffer sb = new StringBuffer();
1261: toStringTreeHelper(treeTop, this , null, 0, sb);
1262: return sb.toString();
1263: }
1264: return null;
1265: }
1266:
1267: private static void toStringTreeHelper(ScriptOrFnNode treeTop,
1268: Node n, ObjToIntMap printIds, int level, StringBuffer sb) {
1269: if (Token.printTrees) {
1270: if (printIds == null) {
1271: printIds = new ObjToIntMap();
1272: generatePrintIds(treeTop, printIds);
1273: }
1274: for (int i = 0; i != level; ++i) {
1275: sb.append(" ");
1276: }
1277: n.toString(printIds, sb);
1278: sb.append('\n');
1279: for (Node cursor = n.getFirstChild(); cursor != null; cursor = cursor
1280: .getNext()) {
1281: if (cursor.getType() == Token.FUNCTION) {
1282: int fnIndex = cursor
1283: .getExistingIntProp(Node.FUNCTION_PROP);
1284: FunctionNode fn = treeTop.getFunctionNode(fnIndex);
1285: toStringTreeHelper(fn, fn, null, level + 1, sb);
1286: } else {
1287: toStringTreeHelper(treeTop, cursor, printIds,
1288: level + 1, sb);
1289: }
1290: }
1291: }
1292: }
1293:
1294: private static void generatePrintIds(Node n, ObjToIntMap map) {
1295: if (Token.printTrees) {
1296: map.put(n, map.size());
1297: for (Node cursor = n.getFirstChild(); cursor != null; cursor = cursor
1298: .getNext()) {
1299: generatePrintIds(cursor, map);
1300: }
1301: }
1302: }
1303:
1304: private static void appendPrintId(Node n, ObjToIntMap printIds,
1305: StringBuffer sb) {
1306: if (Token.printTrees) {
1307: if (n != null) {
1308: int id = printIds.get(n, -1);
1309: sb.append('#');
1310: if (id != -1) {
1311: sb.append(id + 1);
1312: } else {
1313: sb.append("<not_available>");
1314: }
1315: }
1316: }
1317: }
1318:
1319: int type; // type of the node; Token.NAME for example
1320: Node next; // next sibling
1321: private Node first; // first element of a linked list of children
1322: private Node last; // last element of a linked list of children
1323: private int lineno = -1; // encapsulated int data; depends on type
1324:
1325: /**
1326: * Linked list of properties. Since vast majority of nodes would have
1327: * no more then 2 properties, linked list saves memory and provides
1328: * fast lookup. If this does not holds, propListHead can be replaced
1329: * by UintMap.
1330: */
1331: private PropListItem propListHead;
1332:
1333: // <netbeans>
1334: // The offsets returned by "getEncodedSourceStart/End are referring
1335: // to a decompiled source representation which does not match the real
1336: // source. We want the real source offsets (in the original parsed
1337: // source.)
1338: public final void setSourceBounds(int start, int end) {
1339: this .sourceStart = start;
1340: this .sourceEnd = end;
1341: }
1342:
1343: public final int getSourceStart() {
1344: return sourceStart;
1345: }
1346:
1347: public final int getSourceEnd() {
1348: return sourceEnd;
1349: }
1350:
1351: public boolean isStringNode() {
1352: return this instanceof StringNode;
1353: }
1354:
1355: public final void setParentNode(Node parent) {
1356: this .parent = parent;
1357: }
1358:
1359: public final Node getParentNode() {
1360: return parent;
1361: }
1362:
1363: private int sourceStart;
1364: private int sourceEnd;
1365: private Node parent;
1366: // </netbeans>
1367:
1368: }
|