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