1 /*
2 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.nashorn.internal.ir;
27
28 import static jdk.nashorn.internal.runtime.UnwarrantedOptimismException.INVALID_PROGRAM_POINT;
29
30 import java.util.Arrays;
31 import java.util.Collections;
32 import java.util.HashSet;
33 import java.util.Set;
34 import jdk.nashorn.internal.codegen.types.Type;
35 import jdk.nashorn.internal.ir.annotations.Ignore;
36 import jdk.nashorn.internal.ir.annotations.Immutable;
37 import jdk.nashorn.internal.ir.visitor.NodeVisitor;
38 import jdk.nashorn.internal.parser.TokenType;
39
40 /**
41 * BinaryNode nodes represent two operand operations.
42 */
43 @Immutable
44 public final class BinaryNode extends Expression implements Assignment<Expression>, Optimistic {
45 private static final long serialVersionUID = 1L;
46
47 // Placeholder for "undecided optimistic ADD type". Unfortunately, we can't decide the type of ADD during optimistic
48 // type calculation as it can have local variables as its operands that will decide its ultimate type.
49 private static final Type OPTIMISTIC_UNDECIDED_TYPE = Type.typeFor(new Object(){/*empty*/}.getClass());
50
51 /** Left hand side argument. */
52 private final Expression lhs;
53
54 private final Expression rhs;
55
56 private final int programPoint;
57
58 private final Type type;
59 private transient Type cachedType;
60
61 @Ignore
62 private static final Set<TokenType> CAN_OVERFLOW =
63 Collections.unmodifiableSet(new HashSet<>(Arrays.asList(new TokenType[] {
64 TokenType.ADD,
65 TokenType.DIV,
66 TokenType.MOD,
67 TokenType.MUL,
68 TokenType.SUB,
69 TokenType.ASSIGN_ADD,
70 TokenType.ASSIGN_DIV,
71 TokenType.ASSIGN_MOD,
72 TokenType.ASSIGN_MUL,
73 TokenType.ASSIGN_SUB,
74 TokenType.SHR,
75 TokenType.ASSIGN_SHR
76 })));
77
78 /**
79 * Constructor
80 *
81 * @param token token
82 * @param lhs left hand side
83 * @param rhs right hand side
84 */
85 public BinaryNode(final long token, final Expression lhs, final Expression rhs) {
86 super(token, lhs.getStart(), rhs.getFinish());
87 assert !(isTokenType(TokenType.AND) || isTokenType(TokenType.OR)) || lhs instanceof JoinPredecessorExpression;
88 this.lhs = lhs;
89 this.rhs = rhs;
90 this.programPoint = INVALID_PROGRAM_POINT;
91 this.type = null;
92 }
93
94 private BinaryNode(final BinaryNode binaryNode, final Expression lhs, final Expression rhs, final Type type, final int programPoint) {
95 super(binaryNode);
96 this.lhs = lhs;
97 this.rhs = rhs;
98 this.programPoint = programPoint;
99 this.type = type;
100 }
101
102 /**
103 * Returns true if the node is a comparison operation (either equality, inequality, or relational).
104 * @return true if the node is a comparison operation.
105 */
106 public boolean isComparison() {
107 switch (tokenType()) {
108 case EQ:
109 case EQ_STRICT:
110 case NE:
111 case NE_STRICT:
112 case LE:
113 case LT:
114 case GE:
115 case GT:
116 return true;
117 default:
118 return false;
119 }
120 }
121
122 /**
123 * Returns true if the node is a relational operation (less than (or equals), greater than (or equals)).
124 * @return true if the node is a relational operation.
125 */
126 public boolean isRelational() {
127 switch (tokenType()) {
128 case LT:
129 case GT:
130 case LE:
131 case GE:
132 return true;
133 default:
134 return false;
135 }
136 }
137
138 /**
139 * Returns true if the node is a logical operation.
140 * @return true if the node is a logical operation.
141 */
142 public boolean isLogical() {
143 return isLogical(tokenType());
144 }
145
146 /**
147 * Returns true if the token type represents a logical operation.
148 * @param tokenType the token type
149 * @return true if the token type represents a logical operation.
150 */
151 public static boolean isLogical(final TokenType tokenType) {
152 switch (tokenType) {
153 case AND:
154 case OR:
155 return true;
156 default:
157 return false;
158 }
159 }
160
161 /**
162 * Return the widest possible operand type for this operation.
163 *
164 * @return Type
165 */
166 public Type getWidestOperandType() {
167 switch (tokenType()) {
168 case SHR:
169 case ASSIGN_SHR:
170 return Type.INT;
171 case INSTANCEOF:
172 return Type.OBJECT;
173 default:
174 if (isComparison()) {
175 return Type.OBJECT;
176 }
177 return getWidestOperationType();
178 }
179 }
180
181 @Override
182 public Type getWidestOperationType() {
183 switch (tokenType()) {
184 case ADD:
185 case ASSIGN_ADD: {
186 // Compare this logic to decideType(Type, Type); it's similar, but it handles the optimistic type
187 // calculation case while this handles the conservative case.
188 final Type lhsType = lhs.getType();
189 final Type rhsType = rhs.getType();
190 if(lhsType == Type.BOOLEAN && rhsType == Type.BOOLEAN) {
191 // Will always fit in an int, as the value range is [0, 1, 2]. If we didn't treat them specially here,
192 // they'd end up being treated as generic INT operands and their sum would be conservatively considered
193 // to be a LONG in the generic case below; we can do better here.
194 return Type.INT;
195 } else if(isString(lhsType) || isString(rhsType)) {
196 // We can statically figure out that this is a string if either operand is a string. In this case, use
197 // CHARSEQUENCE to prevent it from being proactively flattened.
198 return Type.CHARSEQUENCE;
199 }
200 final Type widestOperandType = Type.widest(undefinedToNumber(booleanToInt(lhsType)), undefinedToNumber(booleanToInt(rhsType)));
201 if (widestOperandType.isNumeric()) {
202 return Type.NUMBER;
203 }
204 // We pretty much can't know what it will be statically. Must presume OBJECT conservatively, as we can end
205 // up getting either a string or an object when adding something + object, e.g.:
206 // 1 + {} == "1[object Object]", but
207 // 1 + {valueOf: function() { return 2 }} == 3. Also:
208 // 1 + {valueOf: function() { return "2" }} == "12".
209 return Type.OBJECT;
210 }
211 case SHR:
212 case ASSIGN_SHR:
213 return Type.NUMBER;
214 case ASSIGN_SAR:
215 case ASSIGN_SHL:
216 case BIT_AND:
217 case BIT_OR:
218 case BIT_XOR:
219 case ASSIGN_BIT_AND:
220 case ASSIGN_BIT_OR:
221 case ASSIGN_BIT_XOR:
222 case SAR:
223 case SHL:
224 return Type.INT;
225 case DIV:
226 case MOD:
227 case ASSIGN_DIV:
228 case ASSIGN_MOD: {
229 // Naively, one might think MOD has the same type as the widest of its operands, this is unfortunately not
230 // true when denominator is zero, so even type(int % int) == double.
231 return Type.NUMBER;
232 }
233 case MUL:
234 case SUB:
235 case ASSIGN_MUL:
236 case ASSIGN_SUB: {
237 final Type lhsType = lhs.getType();
238 final Type rhsType = rhs.getType();
239 if(lhsType == Type.BOOLEAN && rhsType == Type.BOOLEAN) {
240 return Type.INT;
241 }
242 return Type.NUMBER;
243 }
244 case VOID: {
245 return Type.UNDEFINED;
246 }
247 case ASSIGN: {
248 return rhs.getType();
249 }
250 case INSTANCEOF: {
251 return Type.BOOLEAN;
252 }
253 case COMMALEFT: {
254 return lhs.getType();
255 }
256 case COMMARIGHT: {
257 return rhs.getType();
258 }
259 case AND:
260 case OR:{
261 return Type.widestReturnType(lhs.getType(), rhs.getType());
262 }
263 default:
264 if (isComparison()) {
265 return Type.BOOLEAN;
266 }
267 return Type.OBJECT;
268 }
269 }
270
271 private static boolean isString(final Type type) {
272 return type == Type.STRING || type == Type.CHARSEQUENCE;
273 }
274
275 private static Type booleanToInt(final Type type) {
276 return type == Type.BOOLEAN ? Type.INT : type;
277 }
278
279 private static Type undefinedToNumber(final Type type) {
280 return type == Type.UNDEFINED ? Type.NUMBER : type;
281 }
282
283 /**
284 * Check if this node is an assignment
285 *
286 * @return true if this node assigns a value
287 */
288 @Override
289 public boolean isAssignment() {
290 switch (tokenType()) {
291 case ASSIGN:
292 case ASSIGN_ADD:
293 case ASSIGN_BIT_AND:
294 case ASSIGN_BIT_OR:
295 case ASSIGN_BIT_XOR:
296 case ASSIGN_DIV:
297 case ASSIGN_MOD:
298 case ASSIGN_MUL:
299 case ASSIGN_SAR:
300 case ASSIGN_SHL:
301 case ASSIGN_SHR:
302 case ASSIGN_SUB:
303 return true;
304 default:
305 return false;
306 }
307 }
308
309 @Override
310 public boolean isSelfModifying() {
311 return isAssignment() && !isTokenType(TokenType.ASSIGN);
312 }
313
314 @Override
315 public Expression getAssignmentDest() {
316 return isAssignment() ? lhs() : null;
317 }
318
319 @Override
320 public BinaryNode setAssignmentDest(final Expression n) {
321 return setLHS(n);
322 }
323
324 @Override
325 public Expression getAssignmentSource() {
326 return rhs();
327 }
328
329 /**
330 * Assist in IR navigation.
331 * @param visitor IR navigating visitor.
332 */
333 @Override
334 public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {
335 if (visitor.enterBinaryNode(this)) {
336 return visitor.leaveBinaryNode(setLHS((Expression)lhs.accept(visitor)).setRHS((Expression)rhs.accept(visitor)));
337 }
338
339 return this;
340 }
341
342 @Override
343 public boolean isLocal() {
344 switch (tokenType()) {
345 case SAR:
346 case SHL:
347 case SHR:
348 case BIT_AND:
349 case BIT_OR:
350 case BIT_XOR:
351 case ADD:
352 case DIV:
353 case MOD:
354 case MUL:
355 case SUB:
356 return lhs.isLocal() && lhs.getType().isJSPrimitive()
357 && rhs.isLocal() && rhs.getType().isJSPrimitive();
358 case ASSIGN_ADD:
359 case ASSIGN_BIT_AND:
360 case ASSIGN_BIT_OR:
361 case ASSIGN_BIT_XOR:
362 case ASSIGN_DIV:
363 case ASSIGN_MOD:
364 case ASSIGN_MUL:
365 case ASSIGN_SAR:
366 case ASSIGN_SHL:
367 case ASSIGN_SHR:
368 case ASSIGN_SUB:
369 return lhs instanceof IdentNode && lhs.isLocal() && lhs.getType().isJSPrimitive()
370 && rhs.isLocal() && rhs.getType().isJSPrimitive();
371 case ASSIGN:
372 return lhs instanceof IdentNode && lhs.isLocal() && rhs.isLocal();
373 default:
374 return false;
375 }
376 }
377
378 @Override
379 public boolean isAlwaysFalse() {
380 switch (tokenType()) {
381 case COMMALEFT:
382 return lhs.isAlwaysFalse();
383 case COMMARIGHT:
384 return rhs.isAlwaysFalse();
385 default:
386 return false;
387 }
388 }
389
390 @Override
391 public boolean isAlwaysTrue() {
392 switch (tokenType()) {
393 case COMMALEFT:
394 return lhs.isAlwaysTrue();
395 case COMMARIGHT:
396 return rhs.isAlwaysTrue();
397 default:
398 return false;
399 }
400 }
401
402 @Override
403 public void toString(final StringBuilder sb, final boolean printType) {
404 final TokenType tokenType = tokenType();
405
406 final boolean lhsParen = tokenType.needsParens(lhs().tokenType(), true);
407 final boolean rhsParen = tokenType.needsParens(rhs().tokenType(), false);
408
409 if (lhsParen) {
410 sb.append('(');
411 }
412
413 lhs().toString(sb, printType);
414
415 if (lhsParen) {
416 sb.append(')');
417 }
418
419 sb.append(' ');
420
421 switch (tokenType) {
422 case COMMALEFT:
423 sb.append(",<");
424 break;
425 case COMMARIGHT:
426 sb.append(",>");
427 break;
428 case INCPREFIX:
429 case DECPREFIX:
430 sb.append("++");
431 break;
432 default:
433 sb.append(tokenType.getName());
434 break;
435 }
436
437 if (isOptimistic()) {
438 sb.append(Expression.OPT_IDENTIFIER);
439 }
440
441 sb.append(' ');
442
443 if (rhsParen) {
444 sb.append('(');
445 }
446 rhs().toString(sb, printType);
447 if (rhsParen) {
448 sb.append(')');
449 }
450 }
451
452 /**
453 * Get the left hand side expression for this node
454 * @return the left hand side expression
455 */
456 public Expression lhs() {
457 return lhs;
458 }
459
460 /**
461 * Get the right hand side expression for this node
462 * @return the left hand side expression
463 */
464 public Expression rhs() {
465 return rhs;
466 }
467
468 /**
469 * Set the left hand side expression for this node
470 * @param lhs new left hand side expression
471 * @return a node equivalent to this one except for the requested change.
472 */
473 public BinaryNode setLHS(final Expression lhs) {
474 if (this.lhs == lhs) {
475 return this;
476 }
477 return new BinaryNode(this, lhs, rhs, type, programPoint);
478 }
479
480 /**
481 * Set the right hand side expression for this node
482 * @param rhs new right hand side expression
483 * @return a node equivalent to this one except for the requested change.
484 */
485 public BinaryNode setRHS(final Expression rhs) {
486 if (this.rhs == rhs) {
487 return this;
488 }
489 return new BinaryNode(this, lhs, rhs, type, programPoint);
490 }
491
492 /**
493 * Set both the left and the right hand side expression for this node
494 * @param lhs new left hand side expression
495 * @param rhs new left hand side expression
496 * @return a node equivalent to this one except for the requested change.
497 */
498 public BinaryNode setOperands(final Expression lhs, final Expression rhs) {
499 if (this.lhs == lhs && this.rhs == rhs) {
500 return this;
501 }
502 return new BinaryNode(this, lhs, rhs, type, programPoint);
503 }
504
505 @Override
506 public int getProgramPoint() {
507 return programPoint;
508 }
509
510 @Override
511 public boolean canBeOptimistic() {
512 return isTokenType(TokenType.ADD) || (getMostOptimisticType() != getMostPessimisticType());
513 }
514
515 @Override
516 public BinaryNode setProgramPoint(final int programPoint) {
517 if (this.programPoint == programPoint) {
518 return this;
519 }
520 return new BinaryNode(this, lhs, rhs, type, programPoint);
521 }
522
523 @Override
524 public Type getMostOptimisticType() {
525 final TokenType tokenType = tokenType();
526 if(tokenType == TokenType.ADD || tokenType == TokenType.ASSIGN_ADD) {
527 return OPTIMISTIC_UNDECIDED_TYPE;
528 } else if (CAN_OVERFLOW.contains(tokenType)) {
529 return Type.INT;
530 }
531 return getMostPessimisticType();
532 }
533
534 @Override
535 public Type getMostPessimisticType() {
536 return getWidestOperationType();
537 }
538
539 /**
540 * Returns true if the node has the optimistic type of the node is not yet decided. Optimistic ADD nodes start out
541 * as undecided until we can figure out if they're numeric or not.
542 * @return true if the node has the optimistic type of the node is not yet decided.
543 */
544 public boolean isOptimisticUndecidedType() {
545 return type == OPTIMISTIC_UNDECIDED_TYPE;
546 }
547
548 @Override
549 public Type getType() {
550 if (cachedType == null) {
551 cachedType = getTypeUncached();
552 }
553 return cachedType;
554 }
555
556 private Type getTypeUncached() {
557 if(type == OPTIMISTIC_UNDECIDED_TYPE) {
558 return decideType(lhs.getType(), rhs.getType());
559 }
560 final Type widest = getWidestOperationType();
561 if(type == null) {
562 return widest;
563 }
564 if (tokenType() == TokenType.ASSIGN_SHR || tokenType() == TokenType.SHR) {
565 return type;
566 }
567 return Type.narrowest(widest, Type.widest(type, Type.widest(lhs.getType(), rhs.getType())));
568 }
569
570 private static Type decideType(final Type lhsType, final Type rhsType) {
571 // Compare this to getWidestOperationType() for ADD and ASSIGN_ADD cases. There's some similar logic, but these
572 // are optimistic decisions, meaning that we don't have to treat boolean addition separately (as it'll become
573 // int addition in the general case anyway), and that we also don't conservatively widen sums of ints to
574 // longs, or sums of longs to doubles.
575 if(isString(lhsType) || isString(rhsType)) {
576 return Type.CHARSEQUENCE;
577 }
578 // NOTE: We don't have optimistic object-to-(int, long) conversions. Therefore, if any operand is an Object, we
579 // bail out of optimism here and presume a conservative Object return value, as the object's ToPrimitive() can
580 // end up returning either a number or a string, and their common supertype is Object, for better or worse.
581 final Type widest = Type.widest(undefinedToNumber(booleanToInt(lhsType)), undefinedToNumber(booleanToInt(rhsType)));
582 return widest.isObject() ? Type.OBJECT : widest;
583 }
584
585 /**
586 * If the node is a node representing an add operation and has {@link #isOptimisticUndecidedType() optimistic
587 * undecided type}, decides its type. Should be invoked after its operands types have been finalized.
588 * @return returns a new node similar to this node, but with its type set to the type decided from the type of its
589 * operands.
590 */
591 public BinaryNode decideType() {
592 assert type == OPTIMISTIC_UNDECIDED_TYPE;
593 return setType(decideType(lhs.getType(), rhs.getType()));
594 }
595
596 @Override
597 public BinaryNode setType(final Type type) {
598 if (this.type == type) {
599 return this;
600 }
601 return new BinaryNode(this, lhs, rhs, type, programPoint);
602 }
603 }