1/* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2014 Eric Lafortune (eric@graphics.cornell.edu) 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU General Public License as published by the Free 9 * Software Foundation; either version 2 of the License, or (at your option) 10 * any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 15 * more details. 16 * 17 * You should have received a copy of the GNU General Public License along 18 * with this program; if not, write to the Free Software Foundation, Inc., 19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21package proguard.evaluation; 22 23import proguard.evaluation.value.*; 24 25import java.util.Arrays; 26 27/** 28 * This class represents an operand stack that contains <code>Value</code> 29 * objects. 30 * 31 * @author Eric Lafortune 32 */ 33public class Stack 34{ 35 private static final TopValue TOP_VALUE = new TopValue(); 36 37 38 protected Value[] values; 39 protected int currentSize; 40 protected int actualMaxSize; 41 42 43 /** 44 * Creates a new Stack with a given maximum size, accounting for the double 45 * space required by Category 2 values. 46 */ 47 public Stack(int maxSize) 48 { 49 values = new Value[maxSize]; 50 } 51 52 53 /** 54 * Creates a Stack that is a copy of the given Stack. 55 */ 56 public Stack(Stack stack) 57 { 58 // Create the values array. 59 this(stack.values.length); 60 61 // Copy the stack contents. 62 copy(stack); 63 } 64 65 66 /** 67 * Returns the actual maximum stack size that was required for all stack 68 * operations, accounting for the double space required by Category 2 values. 69 */ 70 public int getActualMaxSize() 71 { 72 return actualMaxSize; 73 } 74 75 76 /** 77 * Resets this Stack, so that it can be reused. 78 */ 79 public void reset(int maxSize) 80 { 81 // Is the values array large enough? 82 if (maxSize > values.length) 83 { 84 // Create a new one. 85 values = new Value[maxSize]; 86 } 87 88 // Clear the sizes. 89 clear(); 90 91 actualMaxSize = 0; 92 } 93 94 95 /** 96 * Copies the values of the given Stack into this Stack. 97 */ 98 public void copy(Stack other) 99 { 100 // Is the values array large enough? 101 if (other.values.length > values.length) 102 { 103 // Create a new one. 104 values = new Value[other.values.length]; 105 } 106 107 // Copy the stack contents. 108 System.arraycopy(other.values, 0, this.values, 0, other.currentSize); 109 110 // Copy the sizes. 111 currentSize = other.currentSize; 112 actualMaxSize = other.actualMaxSize; 113 } 114 115 116 /** 117 * Generalizes the values of this Stack with the values of the given Stack. 118 * The stacks must have the same current sizes. 119 * @return whether the generalization has made any difference. 120 */ 121 public boolean generalize(Stack other) 122 { 123 if (this.currentSize != other.currentSize) 124 { 125 throw new IllegalArgumentException("Stacks have different current sizes ["+this.currentSize+"] and ["+other.currentSize+"]"); 126 } 127 128 boolean changed = false; 129 130 // Generalize the stack values. 131 for (int index = 0; index < currentSize; index++) 132 { 133 Value thisValue = this.values[index]; 134 135 if (thisValue != null) 136 { 137 Value newValue = null; 138 139 Value otherValue = other.values[index]; 140 141 if (otherValue != null) 142 { 143 newValue = thisValue.generalize(otherValue); 144 } 145 146 changed = changed || !thisValue.equals(newValue); 147 148 values[index] = newValue; 149 } 150 } 151 152 // Check if the other stack extends beyond this one. 153 if (this.actualMaxSize < other.actualMaxSize) 154 { 155 this.actualMaxSize = other.actualMaxSize; 156 } 157 158 return changed; 159 } 160 161 162 /** 163 * Clears the stack. 164 */ 165 public void clear() 166 { 167 // Clear the stack contents. 168 Arrays.fill(values, 0, currentSize, null); 169 170 currentSize = 0; 171 } 172 173 174 /** 175 * Returns the number of elements currently on the stack, accounting for the 176 * double space required by Category 2 values. 177 */ 178 public int size() 179 { 180 return currentSize; 181 } 182 183 184 /** 185 * Gets the specified Value from the stack, without disturbing it. 186 * @param index the index of the stack element, counting from the bottom 187 * of the stack. 188 * @return the value at the specified position. 189 */ 190 public Value getBottom(int index) 191 { 192 return values[index]; 193 } 194 195 196 /** 197 * Sets the specified Value on the stack, without disturbing it. 198 * @param index the index of the stack element, counting from the bottom 199 * of the stack. 200 * @param value the value to set. 201 */ 202 public void setBottom(int index, Value value) 203 { 204 values[index] = value; 205 } 206 207 208 /** 209 * Gets the specified Value from the stack, without disturbing it. 210 * @param index the index of the stack element, counting from the top 211 * of the stack. 212 * @return the value at the specified position. 213 */ 214 public Value getTop(int index) 215 { 216 return values[currentSize - index - 1]; 217 } 218 219 220 /** 221 * Sets the specified Value on the stack, without disturbing it. 222 * @param index the index of the stack element, counting from the top 223 * of the stack. 224 * @param value the value to set. 225 */ 226 public void setTop(int index, Value value) 227 { 228 values[currentSize - index - 1] = value; 229 } 230 231 232 /** 233 * Removes the specified Value from the stack. 234 * @param index the index of the stack element, counting from the top 235 * of the stack. 236 */ 237 public void removeTop(int index) 238 { 239 System.arraycopy(values, currentSize - index, 240 values, currentSize - index - 1, 241 index); 242 currentSize--; 243 } 244 245 246 /** 247 * Pushes the given Value onto the stack. 248 */ 249 public void push(Value value) 250 { 251 // Account for the extra space required by Category 2 values. 252 if (value.isCategory2()) 253 { 254 values[currentSize++] = TOP_VALUE; 255 } 256 257 // Push the value. 258 values[currentSize++] = value; 259 260 // Update the maximum actual size; 261 if (actualMaxSize < currentSize) 262 { 263 actualMaxSize = currentSize; 264 } 265 } 266 267 268 /** 269 * Pops the top Value from the stack. 270 */ 271 public Value pop() 272 { 273 Value value = values[--currentSize]; 274 275 values[currentSize] = null; 276 277 // Account for the extra space required by Category 2 values. 278 if (value.isCategory2()) 279 { 280 values[--currentSize] = null; 281 } 282 283 return value; 284 } 285 286 287 // Pop methods that provide convenient casts to the expected value types. 288 289 /** 290 * Pops the top IntegerValue from the stack. 291 */ 292 public IntegerValue ipop() 293 { 294 return pop().integerValue(); 295 } 296 297 298 /** 299 * Pops the top LongValue from the stack. 300 */ 301 public LongValue lpop() 302 { 303 return pop().longValue(); 304 } 305 306 307 /** 308 * Pops the top FloatValue from the stack. 309 */ 310 public FloatValue fpop() 311 { 312 return pop().floatValue(); 313 } 314 315 316 /** 317 * Pops the top DoubleValue from the stack. 318 */ 319 public DoubleValue dpop() 320 { 321 return pop().doubleValue(); 322 } 323 324 325 /** 326 * Pops the top ReferenceValue from the stack. 327 */ 328 public ReferenceValue apop() 329 { 330 return pop().referenceValue(); 331 } 332 333 334 /** 335 * Pops the top InstructionOffsetValue from the stack. 336 */ 337 public InstructionOffsetValue opop() 338 { 339 return pop().instructionOffsetValue(); 340 } 341 342 343 /** 344 * Pops the top category 1 value from the stack. 345 */ 346 public void pop1() 347 { 348 values[--currentSize] = null; 349 } 350 351 352 /** 353 * Pops the top category 2 value from the stack (or alternatively, two 354 * Category 1 stack elements). 355 */ 356 public void pop2() 357 { 358 values[--currentSize] = null; 359 values[--currentSize] = null; 360 } 361 362 363 /** 364 * Duplicates the top Category 1 value. 365 */ 366 public void dup() 367 { 368 values[currentSize] = values[currentSize - 1].category1Value(); 369 370 currentSize++; 371 372 // Update the maximum actual size; 373 if (actualMaxSize < currentSize) 374 { 375 actualMaxSize = currentSize; 376 } 377 } 378 379 380 /** 381 * Duplicates the top Category 1 value, one Category 1 element down the 382 * stack. 383 */ 384 public void dup_x1() 385 { 386 values[currentSize] = values[currentSize - 1].category1Value(); 387 values[currentSize - 1] = values[currentSize - 2].category1Value(); 388 values[currentSize - 2] = values[currentSize ]; 389 390 currentSize++; 391 392 // Update the maximum actual size; 393 if (actualMaxSize < currentSize) 394 { 395 actualMaxSize = currentSize; 396 } 397 } 398 399 400 /** 401 * Duplicates the top Category 1 value, two Category 1 elements (or one 402 * Category 2 element) down the stack. 403 */ 404 public void dup_x2() 405 { 406 values[currentSize] = values[currentSize - 1].category1Value(); 407 values[currentSize - 1] = values[currentSize - 2]; 408 values[currentSize - 2] = values[currentSize - 3]; 409 values[currentSize - 3] = values[currentSize ]; 410 411 currentSize++; 412 413 // Update the maximum actual size; 414 if (actualMaxSize < currentSize) 415 { 416 actualMaxSize = currentSize; 417 } 418 } 419 420 /** 421 * Duplicates the top Category 2 value (or alternatively, the equivalent 422 * Category 1 stack elements). 423 */ 424 public void dup2() 425 { 426 values[currentSize ] = values[currentSize - 2]; 427 values[currentSize + 1] = values[currentSize - 1]; 428 429 currentSize += 2; 430 431 // Update the maximum actual size; 432 if (actualMaxSize < currentSize) 433 { 434 actualMaxSize = currentSize; 435 } 436 } 437 438 439 /** 440 * Duplicates the top Category 2 value, one Category 1 element down the 441 * stack (or alternatively, the equivalent Category 1 stack values). 442 */ 443 public void dup2_x1() 444 { 445 values[currentSize + 1] = values[currentSize - 1]; 446 values[currentSize ] = values[currentSize - 2]; 447 values[currentSize - 1] = values[currentSize - 3]; 448 values[currentSize - 2] = values[currentSize + 1]; 449 values[currentSize - 3] = values[currentSize ]; 450 451 currentSize += 2; 452 453 // Update the maximum actual size; 454 if (actualMaxSize < currentSize) 455 { 456 actualMaxSize = currentSize; 457 } 458 } 459 460 461 /** 462 * Duplicates the top Category 2 value, one Category 2 stack element down 463 * the stack (or alternatively, the equivalent Category 1 stack values). 464 */ 465 public void dup2_x2() 466 { 467 values[currentSize + 1] = values[currentSize - 1]; 468 values[currentSize ] = values[currentSize - 2]; 469 values[currentSize - 1] = values[currentSize - 3]; 470 values[currentSize - 2] = values[currentSize - 4]; 471 values[currentSize - 3] = values[currentSize + 1]; 472 values[currentSize - 4] = values[currentSize ]; 473 474 currentSize += 2; 475 476 // Update the maximum actual size; 477 if (actualMaxSize < currentSize) 478 { 479 actualMaxSize = currentSize; 480 } 481 } 482 483 484 /** 485 * Swaps the top two Category 1 values. 486 */ 487 public void swap() 488 { 489 Value value1 = values[currentSize - 1].category1Value(); 490 Value value2 = values[currentSize - 2].category1Value(); 491 492 values[currentSize - 1] = value2; 493 values[currentSize - 2] = value1; 494 } 495 496 497 // Implementations for Object. 498 499 public boolean equals(Object object) 500 { 501 if (object == null || 502 this.getClass() != object.getClass()) 503 { 504 return false; 505 } 506 507 Stack other = (Stack)object; 508 509 if (this.currentSize != other.currentSize) 510 { 511 return false; 512 } 513 514 for (int index = 0; index < currentSize; index++) 515 { 516 Value thisValue = this.values[index]; 517 Value otherValue = other.values[index]; 518 if (thisValue == null ? otherValue != null : 519 !thisValue.equals(otherValue)) 520 { 521 return false; 522 } 523 } 524 525 return true; 526 } 527 528 529 public int hashCode() 530 { 531 int hashCode = currentSize; 532 533 for (int index = 0; index < currentSize; index++) 534 { 535 Value value = values[index]; 536 if (value != null) 537 { 538 hashCode ^= value.hashCode(); 539 } 540 } 541 542 return hashCode; 543 } 544 545 546 public String toString() 547 { 548 StringBuffer buffer = new StringBuffer(); 549 550 for (int index = 0; index < currentSize; index++) 551 { 552 Value value = values[index]; 553 buffer = buffer.append('[') 554 .append(value == null ? "empty" : value.toString()) 555 .append(']'); 556 } 557 558 return buffer.toString(); 559 } 560} 561