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