1 /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- 2 * 3 * This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 package org.mozilla.javascript; 8 9 import org.mozilla.javascript.ast.Comment; 10 import org.mozilla.javascript.ast.FunctionNode; 11 import org.mozilla.javascript.ast.Jump; 12 import org.mozilla.javascript.ast.Name; 13 import org.mozilla.javascript.ast.NumberLiteral; 14 import org.mozilla.javascript.ast.Scope; 15 import org.mozilla.javascript.ast.ScriptNode; 16 17 import java.util.Iterator; 18 import java.util.NoSuchElementException; 19 20 /** 21 * This class implements the root of the intermediate representation. 22 * 23 * @author Norris Boyd 24 * @author Mike McCabe 25 */ 26 public class Node implements Iterable<Node> 27 { 28 public static final int 29 FUNCTION_PROP = 1, 30 LOCAL_PROP = 2, 31 LOCAL_BLOCK_PROP = 3, 32 REGEXP_PROP = 4, 33 CASEARRAY_PROP = 5, 34 35 // the following properties are defined and manipulated by the 36 // optimizer - 37 // TARGETBLOCK_PROP - the block referenced by a branch node 38 // VARIABLE_PROP - the variable referenced by a BIND or NAME node 39 // ISNUMBER_PROP - this node generates code on Number children and 40 // delivers a Number result (as opposed to Objects) 41 // DIRECTCALL_PROP - this call node should emit code to test the function 42 // object against the known class and call direct if it 43 // matches. 44 45 TARGETBLOCK_PROP = 6, 46 VARIABLE_PROP = 7, 47 ISNUMBER_PROP = 8, 48 DIRECTCALL_PROP = 9, 49 SPECIALCALL_PROP = 10, 50 SKIP_INDEXES_PROP = 11, // array of skipped indexes of array literal 51 OBJECT_IDS_PROP = 12, // array of properties for object literal 52 INCRDECR_PROP = 13, // pre or post type of increment/decrement 53 CATCH_SCOPE_PROP = 14, // index of catch scope block in catch 54 LABEL_ID_PROP = 15, // label id: code generation uses it 55 MEMBER_TYPE_PROP = 16, // type of element access operation 56 NAME_PROP = 17, // property name 57 CONTROL_BLOCK_PROP = 18, // flags a control block that can drop off 58 PARENTHESIZED_PROP = 19, // expression is parenthesized 59 GENERATOR_END_PROP = 20, 60 DESTRUCTURING_ARRAY_LENGTH = 21, 61 DESTRUCTURING_NAMES = 22, 62 DESTRUCTURING_PARAMS = 23, 63 JSDOC_PROP = 24, 64 EXPRESSION_CLOSURE_PROP = 25, // JS 1.8 expression closure pseudo-return 65 DESTRUCTURING_SHORTHAND = 26, // JS 1.8 destructuring shorthand 66 LAST_PROP = 26; 67 68 // values of ISNUMBER_PROP to specify 69 // which of the children are Number types 70 public static final int 71 BOTH = 0, 72 LEFT = 1, 73 RIGHT = 2; 74 75 public static final int // values for SPECIALCALL_PROP 76 NON_SPECIALCALL = 0, 77 SPECIALCALL_EVAL = 1, 78 SPECIALCALL_WITH = 2; 79 80 public static final int // flags for INCRDECR_PROP 81 DECR_FLAG = 0x1, 82 POST_FLAG = 0x2; 83 84 public static final int // flags for MEMBER_TYPE_PROP 85 PROPERTY_FLAG = 0x1, // property access: element is valid name 86 ATTRIBUTE_FLAG = 0x2, // x.@y or x..@y 87 DESCENDANTS_FLAG = 0x4; // x..y or x..@i 88 89 private static class PropListItem 90 { 91 PropListItem next; 92 int type; 93 int intValue; 94 Object objectValue; 95 } 96 Node(int nodeType)97 public Node(int nodeType) { 98 type = nodeType; 99 } 100 Node(int nodeType, Node child)101 public Node(int nodeType, Node child) { 102 type = nodeType; 103 first = last = child; 104 child.next = null; 105 } 106 Node(int nodeType, Node left, Node right)107 public Node(int nodeType, Node left, Node right) { 108 type = nodeType; 109 first = left; 110 last = right; 111 left.next = right; 112 right.next = null; 113 } 114 Node(int nodeType, Node left, Node mid, Node right)115 public Node(int nodeType, Node left, Node mid, Node right) { 116 type = nodeType; 117 first = left; 118 last = right; 119 left.next = mid; 120 mid.next = right; 121 right.next = null; 122 } 123 Node(int nodeType, int line)124 public Node(int nodeType, int line) { 125 type = nodeType; 126 lineno = line; 127 } 128 Node(int nodeType, Node child, int line)129 public Node(int nodeType, Node child, int line) { 130 this(nodeType, child); 131 lineno = line; 132 } 133 Node(int nodeType, Node left, Node right, int line)134 public Node(int nodeType, Node left, Node right, int line) { 135 this(nodeType, left, right); 136 lineno = line; 137 } 138 Node(int nodeType, Node left, Node mid, Node right, int line)139 public Node(int nodeType, Node left, Node mid, Node right, int line) { 140 this(nodeType, left, mid, right); 141 lineno = line; 142 } 143 newNumber(double number)144 public static Node newNumber(double number) { 145 NumberLiteral n = new NumberLiteral(); 146 n.setNumber(number); 147 return n; 148 } 149 newString(String str)150 public static Node newString(String str) { 151 return newString(Token.STRING, str); 152 } 153 newString(int type, String str)154 public static Node newString(int type, String str) { 155 Name name = new Name(); 156 name.setIdentifier(str); 157 name.setType(type); 158 return name; 159 } 160 getType()161 public int getType() { 162 return type; 163 } 164 165 /** 166 * Sets the node type and returns this node. 167 */ setType(int type)168 public Node setType(int type) { 169 this.type = type; 170 return this; 171 } 172 173 /** 174 * Gets the JsDoc comment string attached to this node. 175 * @return the comment string or {@code null} if no JsDoc is attached to 176 * this node 177 */ getJsDoc()178 public String getJsDoc() { 179 Comment comment = getJsDocNode(); 180 if (comment != null) { 181 return comment.getValue(); 182 } 183 return null; 184 } 185 186 /** 187 * Gets the JsDoc Comment object attached to this node. 188 * @return the Comment or {@code null} if no JsDoc is attached to 189 * this node 190 */ getJsDocNode()191 public Comment getJsDocNode() { 192 return (Comment) getProp(JSDOC_PROP); 193 } 194 195 /** 196 * Sets the JsDoc comment string attached to this node. 197 */ setJsDocNode(Comment jsdocNode)198 public void setJsDocNode(Comment jsdocNode) { 199 putProp(JSDOC_PROP, jsdocNode); 200 } 201 hasChildren()202 public boolean hasChildren() { 203 return first != null; 204 } 205 getFirstChild()206 public Node getFirstChild() { 207 return first; 208 } 209 getLastChild()210 public Node getLastChild() { 211 return last; 212 } 213 getNext()214 public Node getNext() { 215 return next; 216 } 217 getChildBefore(Node child)218 public Node getChildBefore(Node child) { 219 if (child == first) 220 return null; 221 Node n = first; 222 while (n.next != child) { 223 n = n.next; 224 if (n == null) 225 throw new RuntimeException("node is not a child"); 226 } 227 return n; 228 } 229 getLastSibling()230 public Node getLastSibling() { 231 Node n = this; 232 while (n.next != null) { 233 n = n.next; 234 } 235 return n; 236 } 237 addChildToFront(Node child)238 public void addChildToFront(Node child) { 239 child.next = first; 240 first = child; 241 if (last == null) { 242 last = child; 243 } 244 } 245 addChildToBack(Node child)246 public void addChildToBack(Node child) { 247 child.next = null; 248 if (last == null) { 249 first = last = child; 250 return; 251 } 252 last.next = child; 253 last = child; 254 } 255 addChildrenToFront(Node children)256 public void addChildrenToFront(Node children) { 257 Node lastSib = children.getLastSibling(); 258 lastSib.next = first; 259 first = children; 260 if (last == null) { 261 last = lastSib; 262 } 263 } 264 addChildrenToBack(Node children)265 public void addChildrenToBack(Node children) { 266 if (last != null) { 267 last.next = children; 268 } 269 last = children.getLastSibling(); 270 if (first == null) { 271 first = children; 272 } 273 } 274 275 /** 276 * Add 'child' before 'node'. 277 */ addChildBefore(Node newChild, Node node)278 public void addChildBefore(Node newChild, Node node) { 279 if (newChild.next != null) 280 throw new RuntimeException( 281 "newChild had siblings in addChildBefore"); 282 if (first == node) { 283 newChild.next = first; 284 first = newChild; 285 return; 286 } 287 Node prev = getChildBefore(node); 288 addChildAfter(newChild, prev); 289 } 290 291 /** 292 * Add 'child' after 'node'. 293 */ addChildAfter(Node newChild, Node node)294 public void addChildAfter(Node newChild, Node node) { 295 if (newChild.next != null) 296 throw new RuntimeException( 297 "newChild had siblings in addChildAfter"); 298 newChild.next = node.next; 299 node.next = newChild; 300 if (last == node) 301 last = newChild; 302 } 303 removeChild(Node child)304 public void removeChild(Node child) { 305 Node prev = getChildBefore(child); 306 if (prev == null) 307 first = first.next; 308 else 309 prev.next = child.next; 310 if (child == last) last = prev; 311 child.next = null; 312 } 313 replaceChild(Node child, Node newChild)314 public void replaceChild(Node child, Node newChild) { 315 newChild.next = child.next; 316 if (child == first) { 317 first = newChild; 318 } else { 319 Node prev = getChildBefore(child); 320 prev.next = newChild; 321 } 322 if (child == last) 323 last = newChild; 324 child.next = null; 325 } 326 replaceChildAfter(Node prevChild, Node newChild)327 public void replaceChildAfter(Node prevChild, Node newChild) { 328 Node child = prevChild.next; 329 newChild.next = child.next; 330 prevChild.next = newChild; 331 if (child == last) 332 last = newChild; 333 child.next = null; 334 } 335 removeChildren()336 public void removeChildren() { 337 first = last = null; 338 } 339 340 private static final Node NOT_SET = new Node(Token.ERROR); 341 342 /** 343 * Iterates over the children of this Node. Supports child removal. Not 344 * thread-safe. If anyone changes the child list before the iterator 345 * finishes, the results are undefined and probably bad. 346 */ 347 public class NodeIterator implements Iterator<Node> { 348 private Node cursor; // points to node to be returned next 349 private Node prev = NOT_SET; 350 private Node prev2; 351 private boolean removed = false; 352 NodeIterator()353 public NodeIterator() { 354 cursor = Node.this.first; 355 } 356 hasNext()357 public boolean hasNext() { 358 return cursor != null; 359 } 360 next()361 public Node next() { 362 if (cursor == null) { 363 throw new NoSuchElementException(); 364 } 365 removed = false; 366 prev2 = prev; 367 prev = cursor; 368 cursor = cursor.next; 369 return prev; 370 } 371 remove()372 public void remove() { 373 if (prev == NOT_SET) { 374 throw new IllegalStateException("next() has not been called"); 375 } 376 if (removed) { 377 throw new IllegalStateException( 378 "remove() already called for current element"); 379 } 380 if (prev == first) { 381 first = prev.next; 382 } else if (prev == last) { 383 prev2.next = null; 384 last = prev2; 385 } else { 386 prev2.next = cursor; 387 } 388 } 389 } 390 391 /** 392 * Returns an {@link java.util.Iterator} over the node's children. 393 */ iterator()394 public Iterator<Node> iterator() { 395 return new NodeIterator(); 396 } 397 propToString(int propType)398 private static final String propToString(int propType) 399 { 400 if (Token.printTrees) { 401 // If Context.printTrees is false, the compiler 402 // can remove all these strings. 403 switch (propType) { 404 case FUNCTION_PROP: return "function"; 405 case LOCAL_PROP: return "local"; 406 case LOCAL_BLOCK_PROP: return "local_block"; 407 case REGEXP_PROP: return "regexp"; 408 case CASEARRAY_PROP: return "casearray"; 409 410 case TARGETBLOCK_PROP: return "targetblock"; 411 case VARIABLE_PROP: return "variable"; 412 case ISNUMBER_PROP: return "isnumber"; 413 case DIRECTCALL_PROP: return "directcall"; 414 415 case SPECIALCALL_PROP: return "specialcall"; 416 case SKIP_INDEXES_PROP: return "skip_indexes"; 417 case OBJECT_IDS_PROP: return "object_ids_prop"; 418 case INCRDECR_PROP: return "incrdecr_prop"; 419 case CATCH_SCOPE_PROP: return "catch_scope_prop"; 420 case LABEL_ID_PROP: return "label_id_prop"; 421 case MEMBER_TYPE_PROP: return "member_type_prop"; 422 case NAME_PROP: return "name_prop"; 423 case CONTROL_BLOCK_PROP: return "control_block_prop"; 424 case PARENTHESIZED_PROP: return "parenthesized_prop"; 425 case GENERATOR_END_PROP: return "generator_end"; 426 case DESTRUCTURING_ARRAY_LENGTH: 427 return "destructuring_array_length"; 428 case DESTRUCTURING_NAMES: return "destructuring_names"; 429 case DESTRUCTURING_PARAMS: return "destructuring_params"; 430 431 default: Kit.codeBug(); 432 } 433 } 434 return null; 435 } 436 lookupProperty(int propType)437 private PropListItem lookupProperty(int propType) 438 { 439 PropListItem x = propListHead; 440 while (x != null && propType != x.type) { 441 x = x.next; 442 } 443 return x; 444 } 445 ensureProperty(int propType)446 private PropListItem ensureProperty(int propType) 447 { 448 PropListItem item = lookupProperty(propType); 449 if (item == null) { 450 item = new PropListItem(); 451 item.type = propType; 452 item.next = propListHead; 453 propListHead = item; 454 } 455 return item; 456 } 457 removeProp(int propType)458 public void removeProp(int propType) 459 { 460 PropListItem x = propListHead; 461 if (x != null) { 462 PropListItem prev = null; 463 while (x.type != propType) { 464 prev = x; 465 x = x.next; 466 if (x == null) { return; } 467 } 468 if (prev == null) { 469 propListHead = x.next; 470 } else { 471 prev.next = x.next; 472 } 473 } 474 } 475 getProp(int propType)476 public Object getProp(int propType) 477 { 478 PropListItem item = lookupProperty(propType); 479 if (item == null) { return null; } 480 return item.objectValue; 481 } 482 getIntProp(int propType, int defaultValue)483 public int getIntProp(int propType, int defaultValue) 484 { 485 PropListItem item = lookupProperty(propType); 486 if (item == null) { return defaultValue; } 487 return item.intValue; 488 } 489 getExistingIntProp(int propType)490 public int getExistingIntProp(int propType) 491 { 492 PropListItem item = lookupProperty(propType); 493 if (item == null) { Kit.codeBug(); } 494 return item.intValue; 495 } 496 putProp(int propType, Object prop)497 public void putProp(int propType, Object prop) 498 { 499 if (prop == null) { 500 removeProp(propType); 501 } else { 502 PropListItem item = ensureProperty(propType); 503 item.objectValue = prop; 504 } 505 } 506 putIntProp(int propType, int prop)507 public void putIntProp(int propType, int prop) 508 { 509 PropListItem item = ensureProperty(propType); 510 item.intValue = prop; 511 } 512 513 /** 514 * Return the line number recorded for this node. 515 * @return the line number 516 */ getLineno()517 public int getLineno() { 518 return lineno; 519 } 520 setLineno(int lineno)521 public void setLineno(int lineno) { 522 this.lineno = lineno; 523 } 524 525 /** Can only be called when <tt>getType() == Token.NUMBER</tt> */ getDouble()526 public final double getDouble() { 527 return ((NumberLiteral)this).getNumber(); 528 } 529 setDouble(double number)530 public final void setDouble(double number) { 531 ((NumberLiteral)this).setNumber(number); 532 } 533 534 /** Can only be called when node has String context. */ getString()535 public final String getString() { 536 return ((Name)this).getIdentifier(); 537 } 538 539 /** Can only be called when node has String context. */ setString(String s)540 public final void setString(String s) { 541 if (s == null) Kit.codeBug(); 542 ((Name)this).setIdentifier(s); 543 } 544 545 /** Can only be called when node has String context. */ getScope()546 public Scope getScope() { 547 return ((Name)this).getScope(); 548 } 549 550 /** Can only be called when node has String context. */ setScope(Scope s)551 public void setScope(Scope s) { 552 if (s == null) Kit.codeBug(); 553 if (!(this instanceof Name)) { 554 throw Kit.codeBug(); 555 } 556 ((Name)this).setScope(s); 557 } 558 newTarget()559 public static Node newTarget() 560 { 561 return new Node(Token.TARGET); 562 } 563 labelId()564 public final int labelId() 565 { 566 if (type != Token.TARGET && type != Token.YIELD) Kit.codeBug(); 567 return getIntProp(LABEL_ID_PROP, -1); 568 } 569 labelId(int labelId)570 public void labelId(int labelId) 571 { 572 if (type != Token.TARGET && type != Token.YIELD) Kit.codeBug(); 573 putIntProp(LABEL_ID_PROP, labelId); 574 } 575 576 577 /** 578 * Does consistent-return analysis on the function body when strict mode is 579 * enabled. 580 * 581 * function (x) { return (x+1) } 582 * is ok, but 583 * function (x) { if (x < 0) return (x+1); } 584 * is not becuase the function can potentially return a value when the 585 * condition is satisfied and if not, the function does not explicitly 586 * return value. 587 * 588 * This extends to checking mismatches such as "return" and "return <value>" 589 * used in the same function. Warnings are not emitted if inconsistent 590 * returns exist in code that can be statically shown to be unreachable. 591 * Ex. 592 * <pre>function (x) { while (true) { ... if (..) { return value } ... } } 593 * </pre> 594 * emits no warning. However if the loop had a break statement, then a 595 * warning would be emitted. 596 * 597 * The consistency analysis looks at control structures such as loops, ifs, 598 * switch, try-catch-finally blocks, examines the reachable code paths and 599 * warns the user about an inconsistent set of termination possibilities. 600 * 601 * Caveat: Since the parser flattens many control structures into almost 602 * straight-line code with gotos, it makes such analysis hard. Hence this 603 * analyser is written to taken advantage of patterns of code generated by 604 * the parser (for loops, try blocks and such) and does not do a full 605 * control flow analysis of the gotos and break/continue statements. 606 * Future changes to the parser will affect this analysis. 607 */ 608 609 /** 610 * These flags enumerate the possible ways a statement/function can 611 * terminate. These flags are used by endCheck() and by the Parser to 612 * detect inconsistent return usage. 613 * 614 * END_UNREACHED is reserved for code paths that are assumed to always be 615 * able to execute (example: throw, continue) 616 * 617 * END_DROPS_OFF indicates if the statement can transfer control to the 618 * next one. Statement such as return dont. A compound statement may have 619 * some branch that drops off control to the next statement. 620 * 621 * END_RETURNS indicates that the statement can return (without arguments) 622 * END_RETURNS_VALUE indicates that the statement can return a value. 623 * 624 * A compound statement such as 625 * if (condition) { 626 * return value; 627 * } 628 * Will be detected as (END_DROPS_OFF | END_RETURN_VALUE) by endCheck() 629 */ 630 public static final int END_UNREACHED = 0; 631 public static final int END_DROPS_OFF = 1; 632 public static final int END_RETURNS = 2; 633 public static final int END_RETURNS_VALUE = 4; 634 public static final int END_YIELDS = 8; 635 636 /** 637 * Checks that every return usage in a function body is consistent with the 638 * requirements of strict-mode. 639 * @return true if the function satisfies strict mode requirement. 640 */ hasConsistentReturnUsage()641 public boolean hasConsistentReturnUsage() 642 { 643 int n = endCheck(); 644 return (n & END_RETURNS_VALUE) == 0 || 645 (n & (END_DROPS_OFF|END_RETURNS|END_YIELDS)) == 0; 646 } 647 648 /** 649 * Returns in the then and else blocks must be consistent with each other. 650 * If there is no else block, then the return statement can fall through. 651 * @return logical OR of END_* flags 652 */ endCheckIf()653 private int endCheckIf() 654 { 655 Node th, el; 656 int rv = END_UNREACHED; 657 658 th = next; 659 el = ((Jump)this).target; 660 661 rv = th.endCheck(); 662 663 if (el != null) 664 rv |= el.endCheck(); 665 else 666 rv |= END_DROPS_OFF; 667 668 return rv; 669 } 670 671 /** 672 * Consistency of return statements is checked between the case statements. 673 * If there is no default, then the switch can fall through. If there is a 674 * default,we check to see if all code paths in the default return or if 675 * there is a code path that can fall through. 676 * @return logical OR of END_* flags 677 */ endCheckSwitch()678 private int endCheckSwitch() 679 { 680 int rv = END_UNREACHED; 681 682 // examine the cases 683 // for (n = first.next; n != null; n = n.next) 684 // { 685 // if (n.type == Token.CASE) { 686 // rv |= ((Jump)n).target.endCheck(); 687 // } else 688 // break; 689 // } 690 691 // // we don't care how the cases drop into each other 692 // rv &= ~END_DROPS_OFF; 693 694 // // examine the default 695 // n = ((Jump)this).getDefault(); 696 // if (n != null) 697 // rv |= n.endCheck(); 698 // else 699 // rv |= END_DROPS_OFF; 700 701 // // remove the switch block 702 // rv |= getIntProp(CONTROL_BLOCK_PROP, END_UNREACHED); 703 704 return rv; 705 } 706 707 /** 708 * If the block has a finally, return consistency is checked in the 709 * finally block. If all code paths in the finally returns, then the 710 * returns in the try-catch blocks don't matter. If there is a code path 711 * that does not return or if there is no finally block, the returns 712 * of the try and catch blocks are checked for mismatch. 713 * @return logical OR of END_* flags 714 */ endCheckTry()715 private int endCheckTry() 716 { 717 int rv = END_UNREACHED; 718 719 // a TryStatement isn't a jump - needs rewriting 720 721 // check the finally if it exists 722 // n = ((Jump)this).getFinally(); 723 // if(n != null) { 724 // rv = n.next.first.endCheck(); 725 // } else { 726 // rv = END_DROPS_OFF; 727 // } 728 729 // // if the finally block always returns, then none of the returns 730 // // in the try or catch blocks matter 731 // if ((rv & END_DROPS_OFF) != 0) { 732 // rv &= ~END_DROPS_OFF; 733 734 // // examine the try block 735 // rv |= first.endCheck(); 736 737 // // check each catch block 738 // n = ((Jump)this).target; 739 // if (n != null) 740 // { 741 // // point to the first catch_scope 742 // for (n = n.next.first; n != null; n = n.next.next) 743 // { 744 // // check the block of user code in the catch_scope 745 // rv |= n.next.first.next.first.endCheck(); 746 // } 747 // } 748 // } 749 750 return rv; 751 } 752 753 /** 754 * Return statement in the loop body must be consistent. The default 755 * assumption for any kind of a loop is that it will eventually terminate. 756 * The only exception is a loop with a constant true condition. Code that 757 * follows such a loop is examined only if one can statically determine 758 * that there is a break out of the loop. 759 * <pre> 760 * for(<> ; <>; <>) {} 761 * for(<> in <> ) {} 762 * while(<>) { } 763 * do { } while(<>) 764 * </pre> 765 * @return logical OR of END_* flags 766 */ endCheckLoop()767 private int endCheckLoop() 768 { 769 Node n; 770 int rv = END_UNREACHED; 771 772 // To find the loop body, we look at the second to last node of the 773 // loop node, which should be the predicate that the loop should 774 // satisfy. 775 // The target of the predicate is the loop-body for all 4 kinds of 776 // loops. 777 for (n = first; n.next != last; n = n.next) { 778 /* skip */ 779 } 780 if (n.type != Token.IFEQ) 781 return END_DROPS_OFF; 782 783 // The target's next is the loop body block 784 rv = ((Jump)n).target.next.endCheck(); 785 786 // check to see if the loop condition is true 787 if (n.first.type == Token.TRUE) 788 rv &= ~END_DROPS_OFF; 789 790 // look for effect of breaks 791 rv |= getIntProp(CONTROL_BLOCK_PROP, END_UNREACHED); 792 793 return rv; 794 } 795 796 /** 797 * A general block of code is examined statement by statement. If any 798 * statement (even compound ones) returns in all branches, then subsequent 799 * statements are not examined. 800 * @return logical OR of END_* flags 801 */ endCheckBlock()802 private int endCheckBlock() 803 { 804 Node n; 805 int rv = END_DROPS_OFF; 806 807 // check each statment and if the statement can continue onto the next 808 // one, then check the next statement 809 for (n=first; ((rv & END_DROPS_OFF) != 0) && n != null; n = n.next) 810 { 811 rv &= ~END_DROPS_OFF; 812 rv |= n.endCheck(); 813 } 814 return rv; 815 } 816 817 /** 818 * A labelled statement implies that there maybe a break to the label. The 819 * function processes the labelled statement and then checks the 820 * CONTROL_BLOCK_PROP property to see if there is ever a break to the 821 * particular label. 822 * @return logical OR of END_* flags 823 */ endCheckLabel()824 private int endCheckLabel() 825 { 826 int rv = END_UNREACHED; 827 828 rv = next.endCheck(); 829 rv |= getIntProp(CONTROL_BLOCK_PROP, END_UNREACHED); 830 831 return rv; 832 } 833 834 /** 835 * When a break is encountered annotate the statement being broken 836 * out of by setting its CONTROL_BLOCK_PROP property. 837 * @return logical OR of END_* flags 838 */ endCheckBreak()839 private int endCheckBreak() 840 { 841 Node n = ((Jump) this).getJumpStatement(); 842 n.putIntProp(CONTROL_BLOCK_PROP, END_DROPS_OFF); 843 return END_UNREACHED; 844 } 845 846 /** 847 * endCheck() examines the body of a function, doing a basic reachability 848 * analysis and returns a combination of flags END_* flags that indicate 849 * how the function execution can terminate. These constitute only the 850 * pessimistic set of termination conditions. It is possible that at 851 * runtime certain code paths will never be actually taken. Hence this 852 * analysis will flag errors in cases where there may not be errors. 853 * @return logical OR of END_* flags 854 */ endCheck()855 private int endCheck() 856 { 857 switch(type) 858 { 859 case Token.BREAK: 860 return endCheckBreak(); 861 862 case Token.EXPR_VOID: 863 if (this.first != null) 864 return first.endCheck(); 865 return END_DROPS_OFF; 866 867 case Token.YIELD: 868 return END_YIELDS; 869 870 case Token.CONTINUE: 871 case Token.THROW: 872 return END_UNREACHED; 873 874 case Token.RETURN: 875 if (this.first != null) 876 return END_RETURNS_VALUE; 877 else 878 return END_RETURNS; 879 880 case Token.TARGET: 881 if (next != null) 882 return next.endCheck(); 883 else 884 return END_DROPS_OFF; 885 886 case Token.LOOP: 887 return endCheckLoop(); 888 889 case Token.LOCAL_BLOCK: 890 case Token.BLOCK: 891 // there are several special kinds of blocks 892 if (first == null) 893 return END_DROPS_OFF; 894 895 switch(first.type) { 896 case Token.LABEL: 897 return first.endCheckLabel(); 898 899 case Token.IFNE: 900 return first.endCheckIf(); 901 902 case Token.SWITCH: 903 return first.endCheckSwitch(); 904 905 case Token.TRY: 906 return first.endCheckTry(); 907 908 default: 909 return endCheckBlock(); 910 } 911 912 default: 913 return END_DROPS_OFF; 914 } 915 } 916 hasSideEffects()917 public boolean hasSideEffects() 918 { 919 switch (type) { 920 case Token.EXPR_VOID: 921 case Token.COMMA: 922 if (last != null) 923 return last.hasSideEffects(); 924 else 925 return true; 926 927 case Token.HOOK: 928 if (first == null || 929 first.next == null || 930 first.next.next == null) 931 Kit.codeBug(); 932 return first.next.hasSideEffects() && 933 first.next.next.hasSideEffects(); 934 935 case Token.AND: 936 case Token.OR: 937 if (first == null || last == null) 938 Kit.codeBug(); 939 return first.hasSideEffects() || last.hasSideEffects(); 940 941 case Token.ERROR: // Avoid cascaded error messages 942 case Token.EXPR_RESULT: 943 case Token.ASSIGN: 944 case Token.ASSIGN_ADD: 945 case Token.ASSIGN_SUB: 946 case Token.ASSIGN_MUL: 947 case Token.ASSIGN_DIV: 948 case Token.ASSIGN_MOD: 949 case Token.ASSIGN_BITOR: 950 case Token.ASSIGN_BITXOR: 951 case Token.ASSIGN_BITAND: 952 case Token.ASSIGN_LSH: 953 case Token.ASSIGN_RSH: 954 case Token.ASSIGN_URSH: 955 case Token.ENTERWITH: 956 case Token.LEAVEWITH: 957 case Token.RETURN: 958 case Token.GOTO: 959 case Token.IFEQ: 960 case Token.IFNE: 961 case Token.NEW: 962 case Token.DELPROP: 963 case Token.SETNAME: 964 case Token.SETPROP: 965 case Token.SETELEM: 966 case Token.CALL: 967 case Token.THROW: 968 case Token.RETHROW: 969 case Token.SETVAR: 970 case Token.CATCH_SCOPE: 971 case Token.RETURN_RESULT: 972 case Token.SET_REF: 973 case Token.DEL_REF: 974 case Token.REF_CALL: 975 case Token.TRY: 976 case Token.SEMI: 977 case Token.INC: 978 case Token.DEC: 979 case Token.IF: 980 case Token.ELSE: 981 case Token.SWITCH: 982 case Token.WHILE: 983 case Token.DO: 984 case Token.FOR: 985 case Token.BREAK: 986 case Token.CONTINUE: 987 case Token.VAR: 988 case Token.CONST: 989 case Token.LET: 990 case Token.LETEXPR: 991 case Token.WITH: 992 case Token.WITHEXPR: 993 case Token.CATCH: 994 case Token.FINALLY: 995 case Token.BLOCK: 996 case Token.LABEL: 997 case Token.TARGET: 998 case Token.LOOP: 999 case Token.JSR: 1000 case Token.SETPROP_OP: 1001 case Token.SETELEM_OP: 1002 case Token.LOCAL_BLOCK: 1003 case Token.SET_REF_OP: 1004 case Token.YIELD: 1005 return true; 1006 1007 default: 1008 return false; 1009 } 1010 } 1011 1012 /** 1013 * Recursively unlabel every TARGET or YIELD node in the tree. 1014 * 1015 * This is used and should only be used for inlining finally blocks where 1016 * jsr instructions used to be. It is somewhat hackish, but implementing 1017 * a clone() operation would take much, much more effort. 1018 * 1019 * This solution works for inlining finally blocks because you should never 1020 * be writing any given block to the class file simultaneously. Therefore, 1021 * an unlabeling will never occur in the middle of a block. 1022 */ resetTargets()1023 public void resetTargets() 1024 { 1025 if (type == Token.FINALLY) { 1026 resetTargets_r(); 1027 } else { 1028 Kit.codeBug(); 1029 } 1030 } 1031 resetTargets_r()1032 private void resetTargets_r() 1033 { 1034 if (type == Token.TARGET || type == Token.YIELD) { 1035 labelId(-1); 1036 } 1037 Node child = first; 1038 while (child != null) { 1039 child.resetTargets_r(); 1040 child = child.next; 1041 } 1042 } 1043 1044 @Override toString()1045 public String toString() 1046 { 1047 if (Token.printTrees) { 1048 StringBuffer sb = new StringBuffer(); 1049 toString(new ObjToIntMap(), sb); 1050 return sb.toString(); 1051 } 1052 return String.valueOf(type); 1053 } 1054 toString(ObjToIntMap printIds, StringBuffer sb)1055 private void toString(ObjToIntMap printIds, StringBuffer sb) 1056 { 1057 if (Token.printTrees) { 1058 sb.append(Token.name(type)); 1059 if (this instanceof Name) { 1060 sb.append(' '); 1061 sb.append(getString()); 1062 Scope scope = getScope(); 1063 if (scope != null) { 1064 sb.append("[scope: "); 1065 appendPrintId(scope, printIds, sb); 1066 sb.append("]"); 1067 } 1068 } else if (this instanceof Scope) { 1069 if (this instanceof ScriptNode) { 1070 ScriptNode sof = (ScriptNode)this; 1071 if (this instanceof FunctionNode) { 1072 FunctionNode fn = (FunctionNode)this; 1073 sb.append(' '); 1074 sb.append(fn.getName()); 1075 } 1076 sb.append(" [source name: "); 1077 sb.append(sof.getSourceName()); 1078 sb.append("] [encoded source length: "); 1079 sb.append(sof.getEncodedSourceEnd() 1080 - sof.getEncodedSourceStart()); 1081 sb.append("] [base line: "); 1082 sb.append(sof.getBaseLineno()); 1083 sb.append("] [end line: "); 1084 sb.append(sof.getEndLineno()); 1085 sb.append(']'); 1086 } 1087 if (((Scope)this).getSymbolTable() != null) { 1088 sb.append(" [scope "); 1089 appendPrintId(this, printIds, sb); 1090 sb.append(": "); 1091 Iterator<String> iter = 1092 ((Scope) this).getSymbolTable().keySet().iterator(); 1093 while (iter.hasNext()) { 1094 sb.append(iter.next()); 1095 sb.append(" "); 1096 } 1097 sb.append("]"); 1098 } 1099 } else if (this instanceof Jump) { 1100 Jump jump = (Jump)this; 1101 if (type == Token.BREAK || type == Token.CONTINUE) { 1102 sb.append(" [label: "); 1103 appendPrintId(jump.getJumpStatement(), printIds, sb); 1104 sb.append(']'); 1105 } else if (type == Token.TRY) { 1106 Node catchNode = jump.target; 1107 Node finallyTarget = jump.getFinally(); 1108 if (catchNode != null) { 1109 sb.append(" [catch: "); 1110 appendPrintId(catchNode, printIds, sb); 1111 sb.append(']'); 1112 } 1113 if (finallyTarget != null) { 1114 sb.append(" [finally: "); 1115 appendPrintId(finallyTarget, printIds, sb); 1116 sb.append(']'); 1117 } 1118 } else if (type == Token.LABEL || type == Token.LOOP 1119 || type == Token.SWITCH) 1120 { 1121 sb.append(" [break: "); 1122 appendPrintId(jump.target, printIds, sb); 1123 sb.append(']'); 1124 if (type == Token.LOOP) { 1125 sb.append(" [continue: "); 1126 appendPrintId(jump.getContinue(), printIds, sb); 1127 sb.append(']'); 1128 } 1129 } else { 1130 sb.append(" [target: "); 1131 appendPrintId(jump.target, printIds, sb); 1132 sb.append(']'); 1133 } 1134 } else if (type == Token.NUMBER) { 1135 sb.append(' '); 1136 sb.append(getDouble()); 1137 } else if (type == Token.TARGET) { 1138 sb.append(' '); 1139 appendPrintId(this, printIds, sb); 1140 } 1141 if (lineno != -1) { 1142 sb.append(' '); 1143 sb.append(lineno); 1144 } 1145 1146 for (PropListItem x = propListHead; x != null; x = x.next) { 1147 int type = x.type; 1148 sb.append(" ["); 1149 sb.append(propToString(type)); 1150 sb.append(": "); 1151 String value; 1152 switch (type) { 1153 case TARGETBLOCK_PROP : // can't add this as it recurses 1154 value = "target block property"; 1155 break; 1156 case LOCAL_BLOCK_PROP : // can't add this as it is dull 1157 value = "last local block"; 1158 break; 1159 case ISNUMBER_PROP: 1160 switch (x.intValue) { 1161 case BOTH: 1162 value = "both"; 1163 break; 1164 case RIGHT: 1165 value = "right"; 1166 break; 1167 case LEFT: 1168 value = "left"; 1169 break; 1170 default: 1171 throw Kit.codeBug(); 1172 } 1173 break; 1174 case SPECIALCALL_PROP: 1175 switch (x.intValue) { 1176 case SPECIALCALL_EVAL: 1177 value = "eval"; 1178 break; 1179 case SPECIALCALL_WITH: 1180 value = "with"; 1181 break; 1182 default: 1183 // NON_SPECIALCALL should not be stored 1184 throw Kit.codeBug(); 1185 } 1186 break; 1187 case OBJECT_IDS_PROP: { 1188 Object[] a = (Object[]) x.objectValue; 1189 value = "["; 1190 for (int i=0; i < a.length; i++) { 1191 value += a[i].toString(); 1192 if (i+1 < a.length) 1193 value += ", "; 1194 } 1195 value += "]"; 1196 break; 1197 } 1198 default : 1199 Object obj = x.objectValue; 1200 if (obj != null) { 1201 value = obj.toString(); 1202 } else { 1203 value = String.valueOf(x.intValue); 1204 } 1205 break; 1206 } 1207 sb.append(value); 1208 sb.append(']'); 1209 } 1210 } 1211 } 1212 toStringTree(ScriptNode treeTop)1213 public String toStringTree(ScriptNode treeTop) { 1214 if (Token.printTrees) { 1215 StringBuffer sb = new StringBuffer(); 1216 toStringTreeHelper(treeTop, this, null, 0, sb); 1217 return sb.toString(); 1218 } 1219 return null; 1220 } 1221 toStringTreeHelper(ScriptNode treeTop, Node n, ObjToIntMap printIds, int level, StringBuffer sb)1222 private static void toStringTreeHelper(ScriptNode treeTop, Node n, 1223 ObjToIntMap printIds, 1224 int level, StringBuffer sb) 1225 { 1226 if (Token.printTrees) { 1227 if (printIds == null) { 1228 printIds = new ObjToIntMap(); 1229 generatePrintIds(treeTop, printIds); 1230 } 1231 for (int i = 0; i != level; ++i) { 1232 sb.append(" "); 1233 } 1234 n.toString(printIds, sb); 1235 sb.append('\n'); 1236 for (Node cursor = n.getFirstChild(); cursor != null; 1237 cursor = cursor.getNext()) 1238 { 1239 if (cursor.getType() == Token.FUNCTION) { 1240 int fnIndex = cursor.getExistingIntProp(Node.FUNCTION_PROP); 1241 FunctionNode fn = treeTop.getFunctionNode(fnIndex); 1242 toStringTreeHelper(fn, fn, null, level + 1, sb); 1243 } else { 1244 toStringTreeHelper(treeTop, cursor, printIds, level+1, sb); 1245 } 1246 } 1247 } 1248 } 1249 generatePrintIds(Node n, ObjToIntMap map)1250 private static void generatePrintIds(Node n, ObjToIntMap map) 1251 { 1252 if (Token.printTrees) { 1253 map.put(n, map.size()); 1254 for (Node cursor = n.getFirstChild(); cursor != null; 1255 cursor = cursor.getNext()) 1256 { 1257 generatePrintIds(cursor, map); 1258 } 1259 } 1260 } 1261 appendPrintId(Node n, ObjToIntMap printIds, StringBuffer sb)1262 private static void appendPrintId(Node n, ObjToIntMap printIds, 1263 StringBuffer sb) 1264 { 1265 if (Token.printTrees) { 1266 if (n != null) { 1267 int id = printIds.get(n, -1); 1268 sb.append('#'); 1269 if (id != -1) { 1270 sb.append(id + 1); 1271 } else { 1272 sb.append("<not_available>"); 1273 } 1274 } 1275 } 1276 } 1277 1278 protected int type = Token.ERROR; // type of the node, e.g. Token.NAME 1279 protected Node next; // next sibling 1280 protected Node first; // first element of a linked list of children 1281 protected Node last; // last element of a linked list of children 1282 protected int lineno = -1; 1283 1284 /** 1285 * Linked list of properties. Since vast majority of nodes would have 1286 * no more then 2 properties, linked list saves memory and provides 1287 * fast lookup. If this does not holds, propListHead can be replaced 1288 * by UintMap. 1289 */ 1290 protected PropListItem propListHead; 1291 } 1292