1 /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
\r
3 * The contents of this file are subject to the Netscape Public
\r
4 * License Version 1.1 (the "License"); you may not use this file
\r
5 * except in compliance with the License. You may obtain a copy of
\r
6 * the License at http://www.mozilla.org/NPL/
\r
8 * Software distributed under the License is distributed on an "AS
\r
9 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express oqr
\r
10 * implied. See the License for the specific language governing
\r
11 * rights and limitations under the License.
\r
13 * The Original Code is Rhino code, released
\r
16 * The Initial Developer of the Original Code is Netscape
\r
17 * Communications Corporation. Portions created by Netscape are
\r
18 * Copyright (C) 1997-1999 Netscape Communications Corporation. All
\r
26 * Alternatively, the contents of this file may be used under the
\r
27 * terms of the GNU Public License (the "GPL"), in which case the
\r
28 * provisions of the GPL are applicable instead of those above.
\r
29 * If you wish to allow use of your version of this file only
\r
30 * under the terms of the GPL and not to allow others to use your
\r
31 * version of this file under the NPL, indicate your decision by
\r
32 * deleting the provisions above and replace them with the notice
\r
33 * and other provisions required by the GPL. If you do not delete
\r
34 * the provisions above, a recipient may use your version of this
\r
35 * file under either the NPL or the GPL.
\r
38 package org.mozilla.javascript;
\r
40 import java.util.Hashtable;
\r
41 import java.util.Stack;
\r
42 import java.util.Vector;
\r
45 * This class transforms a tree to a lower-level representation for codegen.
\r
48 * @author Norris Boyd
\r
51 public class NodeTransformer {
\r
54 * Return new instance of this class. So that derived classes
\r
55 * can override methods of the transformer.
\r
57 public NodeTransformer newInstance() {
\r
58 return new NodeTransformer();
\r
61 public IRFactory createIRFactory(TokenStream ts, Scriptable scope) {
\r
62 return new IRFactory(ts, scope);
\r
65 public Node transform(Node tree, Node enclosing, TokenStream ts,
\r
68 loops = new Stack();
\r
69 loopEnds = new Stack();
\r
70 inFunction = tree.getType() == TokenStream.FUNCTION;
\r
72 addVariables(tree, getVariableTable(tree));
\r
74 irFactory = createIRFactory(ts, scope);
\r
76 // to save against upchecks if no finally blocks are used.
\r
77 boolean hasFinally = false;
\r
79 PreorderNodeIterator iterator = tree.getPreorderIterator();
\r
81 while ((node = iterator.nextNode()) != null) {
\r
82 int type = node.getType();
\r
87 case TokenStream.FUNCTION:
\r
89 // Add the variables to variable table, the
\r
90 // parameters were added earlier.
\r
91 VariableTable vars = getVariableTable(tree);
\r
92 addVariables(tree, vars);
\r
94 // Add return to end if needed.
\r
95 Node stmts = node.getLastChild();
\r
96 Node lastStmt = stmts.getLastChild();
\r
97 if (lastStmt == null ||
\r
98 lastStmt.getType() != TokenStream.RETURN)
\r
100 stmts.addChildToBack(new Node(TokenStream.RETURN));
\r
104 FunctionNode fnNode = (FunctionNode)
\r
105 node.getProp(Node.FUNCTION_PROP);
\r
107 // Functions containing other functions require
\r
108 // activation objects
\r
109 ((FunctionNode) tree).setRequiresActivation(true);
\r
111 // Nested functions must check their 'this' value to
\r
112 // insure it is not an activation object:
\r
113 // see 10.1.6 Activation Object
\r
114 fnNode.setCheckThis(true);
\r
116 addParameters(fnNode);
\r
117 NodeTransformer inner = newInstance();
\r
118 fnNode = (FunctionNode)
\r
119 inner.transform(fnNode, tree, ts, scope);
\r
120 node.putProp(Node.FUNCTION_PROP, fnNode);
\r
121 Vector fns = (Vector) tree.getProp(Node.FUNCTION_PROP);
\r
123 fns = new Vector(7);
\r
124 tree.putProp(Node.FUNCTION_PROP, fns);
\r
126 fns.addElement(fnNode);
\r
130 case TokenStream.LABEL:
\r
132 Node child = node.getFirstChild();
\r
133 node.removeChild(child);
\r
134 String id = child.getString();
\r
136 // check against duplicate labels...
\r
137 for (int i=loops.size()-1; i >= 0; i--) {
\r
138 Node n = (Node) loops.elementAt(i);
\r
139 if (n.getType() == TokenStream.LABEL) {
\r
140 String otherId = (String)n.getProp(Node.LABEL_PROP);
\r
141 if (id.equals(otherId)) {
\r
142 String message = Context.getMessage1(
\r
143 "msg.dup.label", id);
\r
144 reportMessage(Context.getContext(), message, node,
\r
145 tree, true, scope);
\r
151 node.putProp(Node.LABEL_PROP, id);
\r
153 /* Make a target and put it _after_ the following
\r
154 * node. And in the LABEL node, so breaks get the
\r
157 Node breakTarget = new Node(TokenStream.TARGET);
\r
158 Node parent = iterator.getCurrentParent();
\r
159 Node next = node.getNextSibling();
\r
160 while (next != null &&
\r
161 (next.getType() == TokenStream.LABEL ||
\r
162 next.getType() == TokenStream.TARGET))
\r
163 next = next.getNextSibling();
\r
166 parent.addChildAfter(breakTarget, next);
\r
167 node.putProp(Node.BREAK_PROP, breakTarget);
\r
169 if (next.getType() == TokenStream.LOOP) {
\r
170 node.putProp(Node.CONTINUE_PROP,
\r
171 next.getProp(Node.CONTINUE_PROP));
\r
175 loopEnds.push(breakTarget);
\r
180 case TokenStream.SWITCH:
\r
182 Node breakTarget = new Node(TokenStream.TARGET);
\r
183 Node parent = iterator.getCurrentParent();
\r
184 parent.addChildAfter(breakTarget, node);
\r
186 // make all children siblings except for selector
\r
188 Node child = node.getFirstChild().next;
\r
189 while (child != null) {
\r
190 Node next = child.next;
\r
191 node.removeChild(child);
\r
192 parent.addChildAfter(child, sib);
\r
197 node.putProp(Node.BREAK_PROP, breakTarget);
\r
199 loopEnds.push(breakTarget);
\r
200 node.putProp(Node.CASES_PROP, new Vector(13));
\r
204 case TokenStream.DEFAULT:
\r
205 case TokenStream.CASE:
\r
207 Node sw = (Node) loops.peek();
\r
208 if (type == TokenStream.CASE) {
\r
209 Vector cases = (Vector) sw.getProp(Node.CASES_PROP);
\r
210 cases.addElement(node);
\r
212 sw.putProp(Node.DEFAULT_PROP, node);
\r
217 case TokenStream.NEWLOCAL : {
\r
219 = (Integer)(tree.getProp(Node.LOCALCOUNT_PROP));
\r
220 if (localCount == null) {
\r
221 tree.putProp(Node.LOCALCOUNT_PROP, new Integer(1));
\r
224 tree.putProp(Node.LOCALCOUNT_PROP,
\r
225 new Integer(localCount.intValue() + 1));
\r
230 case TokenStream.LOOP:
\r
232 loopEnds.push(node.getProp(Node.BREAK_PROP));
\r
235 case TokenStream.WITH:
\r
238 // With statements require an activation object.
\r
239 ((FunctionNode) tree).setRequiresActivation(true);
\r
242 Node leave = node.getNextSibling();
\r
243 if (leave.getType() != TokenStream.LEAVEWITH) {
\r
244 throw new RuntimeException("Unexpected tree");
\r
246 loopEnds.push(leave);
\r
250 case TokenStream.TRY:
\r
252 Node finallytarget = (Node)node.getProp(Node.FINALLY_PROP);
\r
253 if (finallytarget != null) {
\r
256 loopEnds.push(finallytarget);
\r
259 = (Integer)(tree.getProp(Node.LOCALCOUNT_PROP));
\r
260 if (localCount == null) {
\r
261 tree.putProp(Node.LOCALCOUNT_PROP, new Integer(1));
\r
264 tree.putProp(Node.LOCALCOUNT_PROP,
\r
265 new Integer(localCount.intValue() + 1));
\r
270 case TokenStream.TARGET:
\r
271 case TokenStream.LEAVEWITH:
\r
272 if (!loopEnds.empty() && loopEnds.peek() == node) {
\r
278 case TokenStream.RETURN:
\r
280 /* If we didn't support try/finally, it wouldn't be
\r
281 * necessary to put LEAVEWITH nodes here... but as
\r
282 * we do need a series of JSR FINALLY nodes before
\r
283 * each RETURN, we need to ensure that each finally
\r
284 * block gets the correct scope... which could mean
\r
285 * that some LEAVEWITH nodes are necessary.
\r
288 break; // skip the whole mess.
\r
290 Node parent = iterator.getCurrentParent();
\r
291 for (int i=loops.size()-1; i >= 0; i--) {
\r
292 Node n = (Node) loops.elementAt(i);
\r
293 int elemtype = n.getType();
\r
294 if (elemtype == TokenStream.TRY) {
\r
295 Node jsrnode = new Node(TokenStream.JSR);
\r
296 Object jsrtarget = n.getProp(Node.FINALLY_PROP);
\r
297 jsrnode.putProp(Node.TARGET_PROP, jsrtarget);
\r
298 parent.addChildBefore(jsrnode, node);
\r
299 } else if (elemtype == TokenStream.WITH) {
\r
300 parent.addChildBefore(new Node(TokenStream.LEAVEWITH),
\r
307 case TokenStream.BREAK:
\r
308 case TokenStream.CONTINUE:
\r
311 boolean labelled = node.hasChildren();
\r
314 /* get the label */
\r
315 Node child = node.getFirstChild();
\r
316 id = child.getString();
\r
317 node.removeChild(child);
\r
321 Node parent = iterator.getCurrentParent();
\r
322 for (i=loops.size()-1; i >= 0; i--) {
\r
323 Node n = (Node) loops.elementAt(i);
\r
324 int elemtype = n.getType();
\r
325 if (elemtype == TokenStream.WITH) {
\r
326 parent.addChildBefore(new Node(TokenStream.LEAVEWITH),
\r
328 } else if (elemtype == TokenStream.TRY) {
\r
329 Node jsrFinally = new Node(TokenStream.JSR);
\r
330 Object jsrTarget = n.getProp(Node.FINALLY_PROP);
\r
331 jsrFinally.putProp(Node.TARGET_PROP, jsrTarget);
\r
332 parent.addChildBefore(jsrFinally, node);
\r
333 } else if (!labelled &&
\r
334 (elemtype == TokenStream.LOOP ||
\r
335 (elemtype == TokenStream.SWITCH &&
\r
336 type == TokenStream.BREAK)))
\r
338 /* if it's a simple break/continue, break from the
\r
339 * nearest enclosing loop or switch
\r
343 } else if (labelled &&
\r
344 elemtype == TokenStream.LABEL &&
\r
345 id.equals((String)n.getProp(Node.LABEL_PROP)))
\r
351 int propType = type == TokenStream.BREAK
\r
353 : Node.CONTINUE_PROP;
\r
354 Node target = loop == null
\r
356 : (Node) loop.getProp(propType);
\r
357 if (loop == null || target == null) {
\r
360 // didn't find an appropriate target
\r
361 if (type == TokenStream.CONTINUE) {
\r
362 message = Context.getMessage
\r
363 ("msg.continue.outside", null);
\r
365 message = Context.getMessage
\r
366 ("msg.bad.break", null);
\r
368 } else if (loop != null) {
\r
369 message = Context.getMessage0("msg.continue.nonloop");
\r
371 Object[] errArgs = { id };
\r
372 message = Context.getMessage
\r
373 ("msg.undef.label", errArgs);
\r
375 reportMessage(Context.getContext(), message, node,
\r
376 tree, true, scope);
\r
377 node.setType(TokenStream.NOP);
\r
380 node.setType(TokenStream.GOTO);
\r
381 node.putProp(Node.TARGET_PROP, target);
\r
385 case TokenStream.CALL:
\r
386 if (isSpecialCallName(tree, node))
\r
387 node.putProp(Node.SPECIALCALL_PROP, Boolean.TRUE);
\r
388 visitCall(node, tree);
\r
391 case TokenStream.NEW:
\r
392 if (isSpecialCallName(tree, node))
\r
393 node.putProp(Node.SPECIALCALL_PROP, Boolean.TRUE);
\r
394 visitNew(node, tree);
\r
397 case TokenStream.DOT:
\r
399 Node right = node.getLastChild();
\r
400 right.setType(TokenStream.STRING);
\r
404 case TokenStream.EXPRSTMT:
\r
405 node.setType(inFunction ? TokenStream.POP : TokenStream.POPV);
\r
408 case TokenStream.OBJECT:
\r
410 Vector regexps = (Vector) tree.getProp(Node.REGEXP_PROP);
\r
411 if (regexps == null) {
\r
412 regexps = new Vector(3);
\r
413 tree.putProp(Node.REGEXP_PROP, regexps);
\r
415 regexps.addElement(node);
\r
416 Node n = new Node(TokenStream.OBJECT);
\r
417 iterator.replaceCurrent(n);
\r
418 n.putProp(Node.REGEXP_PROP, node);
\r
422 case TokenStream.VAR:
\r
424 ShallowNodeIterator i = node.getChildIterator();
\r
425 Node result = new Node(TokenStream.BLOCK);
\r
426 while (i.hasMoreElements()) {
\r
427 Node n = i.nextNode();
\r
428 if (!n.hasChildren())
\r
430 Node init = n.getFirstChild();
\r
431 n.removeChild(init);
\r
432 Node asn = (Node) irFactory.createAssignment(
\r
433 TokenStream.NOP, n, init, null,
\r
435 Node pop = new Node(TokenStream.POP, asn, node.getDatum());
\r
436 result.addChildToBack(pop);
\r
438 iterator.replaceCurrent(result);
\r
442 case TokenStream.DELPROP:
\r
443 case TokenStream.SETNAME:
\r
445 if (!inFunction || inWithStatement())
\r
447 Node bind = node.getFirstChild();
\r
448 if (bind == null || bind.getType() != TokenStream.BINDNAME)
\r
450 String name = bind.getString();
\r
451 Context cx = Context.getCurrentContext();
\r
452 if (cx != null && cx.isActivationNeeded(name)) {
\r
453 // use of "arguments" requires an activation object.
\r
454 ((FunctionNode) tree).setRequiresActivation(true);
\r
456 VariableTable vars = getVariableTable(tree);
\r
457 if (vars.getVariable(name) != null) {
\r
458 if (type == TokenStream.SETNAME) {
\r
459 node.setType(TokenStream.SETVAR);
\r
460 bind.setType(TokenStream.STRING);
\r
462 // Local variables are by definition permanent
\r
463 Node n = new Node(TokenStream.PRIMARY,
\r
464 new Integer(TokenStream.FALSE));
\r
465 iterator.replaceCurrent(n);
\r
471 case TokenStream.GETPROP:
\r
473 Node n = node.getFirstChild().getNextSibling();
\r
474 String name = n == null ? "" : n.getString();
\r
475 Context cx = Context.getCurrentContext();
\r
476 if ((cx != null && cx.isActivationNeeded(name)) ||
\r
477 (name.equals("length") &&
\r
478 Context.getContext().getLanguageVersion() ==
\r
479 Context.VERSION_1_2))
\r
481 // Use of "arguments" or "length" in 1.2 requires
\r
482 // an activation object.
\r
483 ((FunctionNode) tree).setRequiresActivation(true);
\r
488 case TokenStream.NAME:
\r
490 if (!inFunction || inWithStatement())
\r
492 String name = node.getString();
\r
493 Context cx = Context.getCurrentContext();
\r
494 if (cx != null && cx.isActivationNeeded(name)) {
\r
495 // Use of "arguments" requires an activation object.
\r
496 ((FunctionNode) tree).setRequiresActivation(true);
\r
498 VariableTable vars = getVariableTable(tree);
\r
499 if (vars.getVariable(name) != null) {
\r
500 node.setType(TokenStream.GETVAR);
\r
510 protected void addVariables(Node tree, VariableTable vars) {
\r
511 // OPT: a whole pass to collect variables seems expensive.
\r
512 // Could special case to go into statements only.
\r
513 boolean inFunction = tree.getType() == TokenStream.FUNCTION;
\r
514 PreorderNodeIterator iterator = tree.getPreorderIterator();
\r
515 Hashtable ht = null;
\r
517 while ((node = iterator.nextNode()) != null) {
\r
518 int nodeType = node.getType();
\r
519 if (inFunction && nodeType == TokenStream.FUNCTION &&
\r
521 ((FunctionNode) node.getProp(Node.FUNCTION_PROP)).getFunctionType() ==
\r
522 FunctionNode.FUNCTION_EXPRESSION_STATEMENT)
\r
524 // In a function with both "var x" and "function x",
\r
525 // disregard the var statement, independent of order.
\r
526 String name = node.getString();
\r
529 vars.removeLocal(name);
\r
531 ht = new Hashtable();
\r
532 ht.put(name, Boolean.TRUE);
\r
534 if (nodeType != TokenStream.VAR)
\r
536 ShallowNodeIterator i = node.getChildIterator();
\r
537 while (i.hasMoreElements()) {
\r
538 Node n = i.nextNode();
\r
539 if (ht == null || ht.get(n.getString()) == null)
\r
540 vars.addLocal(n.getString());
\r
543 String name = (String) tree.getDatum();
\r
544 if (inFunction && ((FunctionNode) tree).getFunctionType() ==
\r
545 FunctionNode.FUNCTION_EXPRESSION &&
\r
546 name != null && name.length() > 0 &&
\r
547 vars.getVariable(name) == null)
\r
549 // A function expression needs to have its name as a variable
\r
550 // (if it isn't already allocated as a variable). See
\r
551 // ECMA Ch. 13. We add code to the beginning of the function
\r
552 // to initialize a local variable of the function's name
\r
553 // to the function value.
\r
554 vars.addLocal(name);
\r
555 Node block = tree.getLastChild();
\r
556 Node setFn = new Node(TokenStream.POP,
\r
557 new Node(TokenStream.SETVAR,
\r
558 new Node(TokenStream.STRING, name),
\r
559 new Node(TokenStream.PRIMARY,
\r
560 new Integer(TokenStream.THISFN))));
\r
561 block.addChildrenToFront(setFn);
\r
565 protected void addParameters(FunctionNode fnNode) {
\r
566 VariableTable vars = fnNode.getVariableTable();
\r
567 Node args = fnNode.getFirstChild();
\r
568 if (args.getType() == TokenStream.LP && vars.getParameterCount() == 0)
\r
571 ShallowNodeIterator i = args.getChildIterator();
\r
572 while (i.hasMoreElements()) {
\r
573 Node n = i.nextNode();
\r
574 String arg = n.getString();
\r
575 vars.addParameter(arg);
\r
580 protected void visitNew(Node node, Node tree) {
\r
583 protected void visitCall(Node node, Node tree) {
\r
586 * Call(GetProp(a, b), c, d) // or GetElem...
\r
587 * we wish to evaluate as
\r
588 * Call(GetProp(tmp=a, b), tmp, c, d)
\r
591 * Call(Name("a"), b, c)
\r
592 * we wish to evaluate as
\r
593 * Call(GetProp(tmp=GetBase("a"), "a"), tmp, b, c)
\r
597 * we wish to evaluate as
\r
598 * Call(tmp=a, Parent(tmp), c, d)
\r
600 Node left = node.getFirstChild();
\r
601 // count the arguments
\r
603 Node arg = left.getNextSibling();
\r
604 while (arg != null) {
\r
605 arg = arg.getNextSibling();
\r
608 boolean addGetThis = false;
\r
609 if (left.getType() == TokenStream.NAME) {
\r
610 VariableTable vars = getVariableTable(tree);
\r
611 String name = left.getString();
\r
612 if (inFunction && vars.getVariable(name) != null &&
\r
613 !inWithStatement())
\r
615 // call to a var. Transform to Call(GetVar("a"), b, c)
\r
616 left.setType(TokenStream.GETVAR);
\r
617 // fall through to code to add GetParent
\r
619 // transform to Call(GetProp(GetBase("a"), "a"), b, c)
\r
621 node.removeChild(left);
\r
622 left.setType(TokenStream.GETBASE);
\r
623 Node str = left.cloneNode();
\r
624 str.setType(TokenStream.STRING);
\r
625 Node getProp = new Node(TokenStream.GETPROP, left, str);
\r
626 node.addChildToFront(getProp);
\r
629 // Conditionally set a flag to add a GETTHIS node.
\r
630 // The getThis entry in the runtime will take a
\r
631 // Scriptable object intended to be used as a 'this'
\r
632 // and make sure that it is neither a With object or
\r
633 // an activation object.
\r
634 // Executing getThis requires at least two instanceof
\r
635 // tests, so we only include it if we are currently
\r
636 // inside a 'with' statement, or if we are executing
\r
637 // a script (to protect against an eval inside a with).
\r
638 addGetThis = inWithStatement() || !inFunction;
\r
639 // fall through to GETPROP code
\r
642 if (left.getType() != TokenStream.GETPROP &&
\r
643 left.getType() != TokenStream.GETELEM)
\r
645 node.removeChild(left);
\r
646 Node tmp = irFactory.createNewTemp(left);
\r
647 Node use = irFactory.createUseTemp(tmp);
\r
648 use.putProp(Node.TEMP_PROP, tmp);
\r
649 Node parent = new Node(TokenStream.PARENT, use);
\r
650 node.addChildToFront(parent);
\r
651 node.addChildToFront(tmp);
\r
654 Node leftLeft = left.getFirstChild();
\r
655 left.removeChild(leftLeft);
\r
656 Node tmp = irFactory.createNewTemp(leftLeft);
\r
657 left.addChildToFront(tmp);
\r
658 Node use = irFactory.createUseTemp(tmp);
\r
659 use.putProp(Node.TEMP_PROP, tmp);
\r
661 use = new Node(TokenStream.GETTHIS, use);
\r
662 node.addChildAfter(use, left);
\r
665 protected boolean inWithStatement() {
\r
666 for (int i=loops.size()-1; i >= 0; i--) {
\r
667 Node n = (Node) loops.elementAt(i);
\r
668 if (n.getType() == TokenStream.WITH)
\r
675 * Return true if the node is a call to a function that requires
\r
676 * access to the enclosing activation object.
\r
678 private boolean isSpecialCallName(Node tree, Node node) {
\r
679 Node left = node.getFirstChild();
\r
680 boolean isSpecial = false;
\r
681 if (left.getType() == TokenStream.NAME) {
\r
682 String name = left.getString();
\r
683 isSpecial = name.equals("eval") || name.equals("With");
\r
685 if (left.getType() == TokenStream.GETPROP) {
\r
686 String name = left.getLastChild().getString();
\r
687 isSpecial = name.equals("exec");
\r
691 // Calls to these functions require activation objects.
\r
693 ((FunctionNode) tree).setRequiresActivation(true);
\r
699 protected VariableTable createVariableTable() {
\r
700 return new VariableTable();
\r
703 protected VariableTable getVariableTable(Node tree) {
\r
705 return ((FunctionNode)tree).getVariableTable();
\r
707 VariableTable result = (VariableTable)(tree.getProp(Node.VARS_PROP));
\r
708 if (result == null) {
\r
709 result = createVariableTable();
\r
710 tree.putProp(Node.VARS_PROP, result);
\r
715 protected void reportMessage(Context cx, String msg, Node stmt,
\r
716 Node tree, boolean isError,
\r
719 Object obj = stmt.getDatum();
\r
721 if (obj != null && obj instanceof Integer)
\r
722 lineno = ((Integer) obj).intValue();
\r
723 Object prop = tree == null
\r
725 : tree.getProp(Node.SOURCENAME_PROP);
\r
728 throw NativeGlobal.constructError(
\r
729 cx, "SyntaxError", msg, scope,
\r
730 (String) prop, lineno, 0, null);
\r
732 cx.reportError(msg, (String) prop, lineno, null, 0);
\r
735 cx.reportWarning(msg, (String) prop, lineno, null, 0);
\r
738 protected Stack loops;
\r
739 protected Stack loopEnds;
\r
740 protected boolean inFunction;
\r
741 protected IRFactory irFactory;
\r