1/* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2009 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.preverify; 22 23import proguard.classfile.*; 24import proguard.classfile.attribute.*; 25import proguard.classfile.attribute.preverification.*; 26import proguard.classfile.attribute.visitor.AttributeVisitor; 27import proguard.classfile.editor.*; 28import proguard.classfile.instruction.*; 29import proguard.classfile.util.SimplifiedVisitor; 30import proguard.classfile.visitor.*; 31import proguard.evaluation.*; 32import proguard.evaluation.value.*; 33import proguard.optimize.evaluation.*; 34 35import java.util.*; 36 37/** 38 * This class can preverify methods in program class pools, according to a given 39 * specification. 40 * 41 * @author Eric Lafortune 42 */ 43public class CodePreverifier 44extends SimplifiedVisitor 45implements MemberVisitor, 46 AttributeVisitor 47{ 48 //* 49 private static final boolean DEBUG = false; 50 /*/ 51 private static boolean DEBUG = true; 52 //*/ 53 54 55 private final boolean microEdition; 56 57 private final PartialEvaluator partialEvaluator = new PartialEvaluator(); 58 private final LivenessAnalyzer livenessAnalyzer = new LivenessAnalyzer(partialEvaluator); 59 60 61 /** 62 * Creates a new CodePreverifier. 63 */ 64 public CodePreverifier(boolean microEdition) 65 { 66 this.microEdition = microEdition; 67 } 68 69 70 // Implementations for AttributeVisitor. 71 72 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 73 74 75 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 76 { 77 // TODO: Remove this when the preverifier has stabilized. 78 // Catch any unexpected exceptions from the actual visiting method. 79 try 80 { 81 // Process the code. 82 visitCodeAttribute0(clazz, method, codeAttribute); 83 } 84 catch (RuntimeException ex) 85 { 86 System.err.println("Unexpected error while preverifying:"); 87 System.err.println(" Class = ["+clazz.getName()+"]"); 88 System.err.println(" Method = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]"); 89 System.err.println(" Exception = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")"); 90 91 throw ex; 92 } 93 } 94 95 96 public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute) 97 { 98// DEBUG = 99// clazz.getName().equals("abc/Def") && 100// method.getName(clazz).equals("abc"); 101 102 ProgramClass programClass = (ProgramClass)clazz; 103 ProgramMethod programMethod = (ProgramMethod)method; 104 105 // Evaluate the method. 106 //partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute); 107 livenessAnalyzer.visitCodeAttribute(clazz, method, codeAttribute); 108 109 // Collect the stack map frames. 110 List stackMapFrameList = new ArrayList(); 111 112 for (int offset = 0; offset < codeAttribute.u4codeLength; offset++) 113 { 114 // Only store frames at the beginning of code blocks. 115 if (partialEvaluator.isTraced(offset) && 116 partialEvaluator.isBranchOrExceptionTarget(offset)) 117 { 118 // Convert the variable values to types. 119 VerificationType[] variableTypes = 120 correspondingVerificationTypes(programClass, 121 programMethod, 122 codeAttribute, 123 offset, 124 partialEvaluator.getVariablesBefore(offset)); 125 126 // Convert the stack values to types. 127 VerificationType[] stackTypes = 128 correspondingVerificationTypes(programClass, 129 programMethod, 130 codeAttribute, 131 offset, 132 partialEvaluator.getStackBefore(offset)); 133 // Create and store a new frame. 134 stackMapFrameList.add(new FullFrame(offset, 135 variableTypes, 136 stackTypes)); 137 } 138 } 139 140 // Compress the stack map frames if the target is not Java Micro Edition. 141 if (!microEdition && !stackMapFrameList.isEmpty()) 142 { 143 // Convert the initial variable values to types. 144 VerificationType[] initialVariables = 145 correspondingVerificationTypes(programClass, 146 programMethod, 147 codeAttribute, 148 PartialEvaluator.AT_METHOD_ENTRY, 149 partialEvaluator.getVariablesBefore(0)); 150 151 // Special case: the <init> method. 152 if (method.getName(programClass).equals(ClassConstants.INTERNAL_METHOD_NAME_INIT)) 153 { 154 initialVariables[0] = VerificationTypeFactory.createUninitializedThisType(); 155 } 156 157 compressStackMapFrames(initialVariables, 158 stackMapFrameList); 159 } 160 161 // Get the proper name for the attribute to be added/replaced/deleted. 162 String stackMapAttributeName = microEdition ? 163 ClassConstants.ATTR_StackMap : 164 ClassConstants.ATTR_StackMapTable; 165 166 int frameCount = stackMapFrameList.size(); 167 168 if (DEBUG) 169 { 170 Attribute originalStackMapAttribute = codeAttribute.getAttribute(clazz, 171 stackMapAttributeName); 172 173 if (originalStackMapAttribute != null) 174 { 175 int originalFrameCount = microEdition ? 176 ((StackMapAttribute)originalStackMapAttribute).u2stackMapFramesCount : 177 ((StackMapTableAttribute)originalStackMapAttribute).u2stackMapFramesCount; 178 179 StackMapFrame[] originalFrames = microEdition ? 180 ((StackMapAttribute)originalStackMapAttribute).stackMapFrames : 181 ((StackMapTableAttribute)originalStackMapAttribute).stackMapFrames; 182 183 if (frameCount != originalFrameCount || 184 !Arrays.equals(stackMapFrameList.toArray(), originalFrames)) 185 { 186 System.out.println("Original preverification ["+clazz.getName()+"]:"); 187 new ClassPrinter().visitProgramMethod(programClass, programMethod); 188 } 189 } 190 else if (frameCount != 0) 191 { 192 System.out.println("Original preverification empty ["+clazz.getName()+"."+method.getName(clazz)+"]"); 193 } 194 } 195 196 if (frameCount == 0) 197 { 198 // Remove any stack map (table) attribute from the code attribute. 199 new AttributesEditor(programClass, programMethod, codeAttribute, true).deleteAttribute(stackMapAttributeName); 200 } 201 else 202 { 203 Attribute stackMapAttribute; 204 205 // Create the appropriate attribute. 206 if (microEdition) 207 { 208 // Copy the frames into an array. 209 FullFrame[] stackMapFrames = new FullFrame[frameCount]; 210 stackMapFrameList.toArray(stackMapFrames); 211 212 // Put the frames into a stack map attribute. 213 stackMapAttribute = new StackMapAttribute(stackMapFrames); 214 } 215 else 216 { 217 // Copy the frames into an array. 218 StackMapFrame[] stackMapFrames = new StackMapFrame[frameCount]; 219 stackMapFrameList.toArray(stackMapFrames); 220 221 // Put the frames into a stack map table attribute. 222 stackMapAttribute = new StackMapTableAttribute(stackMapFrames); 223 } 224 225 // Fill out the name of the stack map attribute. 226 stackMapAttribute.u2attributeNameIndex = 227 new ConstantPoolEditor(programClass).addUtf8Constant(stackMapAttributeName); 228 229 // Add the new stack map (table) attribute to the code attribute. 230 new AttributesEditor(programClass, programMethod, codeAttribute, true).addAttribute(stackMapAttribute); 231 232 if (DEBUG) 233 { 234 System.out.println("Preverifier ["+programClass.getName()+"."+programMethod.getName(programClass)+"]:"); 235 stackMapAttribute.accept(programClass, programMethod, codeAttribute, new ClassPrinter()); 236 } 237 } 238 } 239 240 241 // Small utility methods. 242 243 /** 244 * Creates and returns the verification types corresponding to the given 245 * variables. If necessary, class constants are added to the constant pool 246 * of the given class. 247 */ 248 private VerificationType[] correspondingVerificationTypes(ProgramClass programClass, 249 ProgramMethod programMethod, 250 CodeAttribute codeAttribute, 251 int offset, 252 TracedVariables variables) 253 { 254 int maximumVariablesSize = variables.size(); 255 int typeCount = 0; 256 int typeIndex = 0; 257 258 // Count the the number of verification types, ignoring any nulls at 259 // the end. 260 for (int index = 0; index < maximumVariablesSize; index++) 261 { 262 Value value = variables.getValue(index); 263 264 typeIndex++; 265 266 // Remember the maximum live type index. 267 if (value != null && 268 (offset == PartialEvaluator.AT_METHOD_ENTRY || 269 livenessAnalyzer.isAliveBefore(offset, index))) 270 { 271 typeCount = typeIndex; 272 273 // Category 2 types that are alive are stored as single entries. 274 if (value.isCategory2()) 275 { 276 index++; 277 } 278 } 279 } 280 281 // Create and fill out the verification types. 282 VerificationType[] types = new VerificationType[typeCount]; 283 284 typeIndex = 0; 285 286 // Note the slightly different terminating condition, because the 287 // types may have been truncated. 288 for (int index = 0; typeIndex < typeCount; index++) 289 { 290 Value value = variables.getValue(index); 291 Value producerValue = variables.getProducerValue(index); 292 293 // Fill out the type. 294 VerificationType type; 295 296 if (value != null && 297 (offset == PartialEvaluator.AT_METHOD_ENTRY || 298 livenessAnalyzer.isAliveBefore(offset, index))) 299 { 300 type = correspondingVerificationType(programClass, 301 programMethod, 302 codeAttribute, 303 offset, 304 index == 0, 305 value, 306 producerValue); 307 308 // Category 2 types that are alive are stored as single entries. 309 if (value.isCategory2()) 310 { 311 index++; 312 } 313 } 314 else 315 { 316 type = VerificationTypeFactory.createTopType(); 317 } 318 319 types[typeIndex++] = type; 320 } 321 322 return types; 323 } 324 325 326 /** 327 * Creates and returns the verification types corresponding to the given 328 * stack. If necessary, class constants are added to the constant pool 329 * of the given class. 330 */ 331 private VerificationType[] correspondingVerificationTypes(ProgramClass programClass, 332 ProgramMethod programMethod, 333 CodeAttribute codeAttribute, 334 int offset, 335 TracedStack stack) 336 { 337 int maximumStackSize = stack.size(); 338 int typeCount = 0; 339 340 // Count the the number of verification types. 341 for (int index = 0; index < maximumStackSize; index++) 342 { 343 // We have to work down from the top of the stack. 344 Value value = stack.getTop(index); 345 346 typeCount++; 347 348 // Category 2 types are stored as single entries. 349 if (value.isCategory2()) 350 { 351 index++; 352 } 353 } 354 355 // Create and fill out the verification types. 356 VerificationType[] types = new VerificationType[typeCount]; 357 358 int typeIndex = typeCount; 359 360 for (int index = 0; index < maximumStackSize; index++) 361 { 362 // We have to work down from the top of the stack. 363 Value value = stack.getTop(index); 364 Value producerValue = stack.getTopProducerValue(index); 365 366 // Fill out the type. 367 types[--typeIndex] = 368 correspondingVerificationType(programClass, 369 programMethod, 370 codeAttribute, 371 offset, 372 false, 373 value, 374 producerValue); 375 376 // Category 2 types are stored as single entries. 377 if (value.isCategory2()) 378 { 379 index++; 380 } 381 } 382 383 return types; 384 } 385 386 387 /** 388 * Creates and returns the verification type corresponding to the given 389 * value. If necessary, a class constant is added to the constant pool of 390 * the given class. 391 */ 392 private VerificationType correspondingVerificationType(ProgramClass programClass, 393 ProgramMethod programMethod, 394 CodeAttribute codeAttribute, 395 int offset, 396 boolean isVariable0, 397 Value value, 398 Value producerValue) 399 { 400 if (value == null) 401 { 402 return VerificationTypeFactory.createTopType(); 403 } 404 405 int type = value.computationalType(); 406 407 switch (type) 408 { 409 case Value.TYPE_INSTRUCTION_OFFSET: 410 case Value.TYPE_INTEGER: return VerificationTypeFactory.createIntegerType(); 411 case Value.TYPE_LONG: return VerificationTypeFactory.createLongType(); 412 case Value.TYPE_FLOAT: return VerificationTypeFactory.createFloatType(); 413 case Value.TYPE_DOUBLE: return VerificationTypeFactory.createDoubleType(); 414 case Value.TYPE_TOP: return VerificationTypeFactory.createTopType(); 415 case Value.TYPE_REFERENCE: 416 // Is it a Null type? 417 ReferenceValue referenceValue = value.referenceValue(); 418 if (referenceValue.isNull() == Value.ALWAYS) 419 { 420 return VerificationTypeFactory.createNullType(); 421 } 422 423 // Does the reference type have a single producer? 424 if (offset != PartialEvaluator.AT_METHOD_ENTRY) 425 { 426 InstructionOffsetValue producers = producerValue.instructionOffsetValue(); 427 if (producers.instructionOffsetCount() == 1) 428 { 429 int producerOffset = producers.instructionOffset(0); 430 431 // Follow any dup or swap instructions. 432 while (producerOffset != PartialEvaluator.AT_METHOD_ENTRY && 433 isDupOrSwap(codeAttribute.code[producerOffset])) 434 { 435 producers = partialEvaluator.getStackBefore(producerOffset).getTopProducerValue(0).instructionOffsetValue(); 436 producerOffset = producers.instructionOffset(0); 437 } 438 439 // Are we in an instance initialization method, 440 // before the super initialization, loading "this"? 441 if (partialEvaluator.isInitializer() && 442 offset <= partialEvaluator.superInitializationOffset() && 443 (isVariable0 || 444 producerOffset > PartialEvaluator.AT_METHOD_ENTRY && 445 codeAttribute.code[producerOffset] == InstructionConstants.OP_ALOAD_0)) 446 { 447 // It's an UninitializedThis type. 448 return VerificationTypeFactory.createUninitializedThisType(); 449 } 450 451 // Is the reference type newly created and still 452 // uninitialized? 453 if (producerOffset > PartialEvaluator.AT_METHOD_ENTRY && 454 offset <= partialEvaluator.initializationOffset(producerOffset)) 455 { 456 // It's an Uninitialized type. 457 return VerificationTypeFactory.createUninitializedType(producerOffset); 458 } 459 } 460 } 461 462 // It's an ordinary Object type. 463 return VerificationTypeFactory.createObjectType(createClassConstant(programClass, referenceValue)); 464 } 465 466 throw new IllegalArgumentException("Unknown computational type ["+type+"]"); 467 } 468 469 470 /** 471 * Finds or creates a class constant for the given reference value, and 472 * returns its index in the constant pool. 473 */ 474 private int createClassConstant(ProgramClass programClass, 475 ReferenceValue referenceValue) 476 { 477 return new ConstantPoolEditor(programClass).addClassConstant(referenceValue.getType(), 478 referenceValue.getReferencedClass()); 479 } 480 481 482 /** 483 * Compresses the given list of full frames, for use in a stack map table. 484 */ 485 private void compressStackMapFrames(VerificationType[] initialVariableTypes, 486 List stackMapFrameList) 487 { 488 int previousVariablesCount = initialVariableTypes.length; 489 VerificationType[] previousVariableTypes = initialVariableTypes; 490 491 int previousOffset = -1; 492 493 for (int index = 0; index < stackMapFrameList.size(); index++) 494 { 495 FullFrame fullFrame = (FullFrame)stackMapFrameList.get(index); 496 497 int variablesCount = fullFrame.variablesCount; 498 VerificationType[] variables = fullFrame.variables; 499 int stackCount = fullFrame.stackCount; 500 VerificationType[] stack = fullFrame.stack; 501 502 // Start computing the compressed frame. 503 // The default is the full frame. 504 StackMapFrame compressedFrame = fullFrame; 505 506 // Are all variables equal? 507 if (variablesCount == previousVariablesCount && 508 equalVerificationTypes(variables, previousVariableTypes, variablesCount)) 509 { 510 // Are the stacks equal? 511 //if (stackCount == previousStackCount && 512 // equalVerificationTypes(stack, previousStack, stackCount)) 513 //{ 514 // // Remove the identical frame. 515 // stackMapFrameList.remove(index--); 516 // 517 // // Move on to the next frame (at the same index). 518 // continue; 519 //} 520 // Is the new stack empty? 521 //else 522 if (stackCount == 0) 523 { 524 compressedFrame = new SameZeroFrame(); 525 } 526 // Does the new stack contain a single element? 527 else if (stackCount == 1) 528 { 529 compressedFrame = new SameOneFrame(stack[0]); 530 } 531 } 532 // Is the stack empty? 533 else if (stackCount == 0) 534 { 535 int additionalVariablesCount = variablesCount - previousVariablesCount; 536 537 // Are the variables chopped? 538 if (additionalVariablesCount < 0 && 539 additionalVariablesCount > -4 && 540 equalVerificationTypes(variables, previousVariableTypes, variablesCount)) 541 { 542 compressedFrame = new LessZeroFrame((byte)-additionalVariablesCount); 543 } 544 // Are the variables extended? 545 else if (//previousVariablesCount > 0 && 546 additionalVariablesCount > 0 && 547 additionalVariablesCount < 4 && 548 equalVerificationTypes(variables, previousVariableTypes, previousVariablesCount)) 549 { 550 // Copy the additional variables into an array. 551 VerificationType[] additionalVariables = new VerificationType[additionalVariablesCount]; 552 System.arraycopy(variables, variablesCount - additionalVariablesCount, 553 additionalVariables, 0, 554 additionalVariablesCount); 555 556 compressedFrame = new MoreZeroFrame(additionalVariables); 557 } 558 } 559 560 // Compress the instruction offset. 561 int offset = fullFrame.u2offsetDelta; 562 compressedFrame.u2offsetDelta = offset - previousOffset - 1; 563 previousOffset = offset; 564 565 // Remember this frame. 566 previousVariablesCount = fullFrame.variablesCount; 567 previousVariableTypes = fullFrame.variables; 568 569 // Replace the full frame. 570 stackMapFrameList.set(index, compressedFrame); 571 } 572 } 573 574 575 /** 576 * Returns whether the given arrays of verification types are equal, up to 577 * the given length. 578 */ 579 private boolean equalVerificationTypes(VerificationType[] types1, 580 VerificationType[] types2, 581 int length) 582 { 583 if (length > 0 && 584 (types1.length < length || 585 types2.length < length)) 586 { 587 return false; 588 } 589 590 for (int index = 0; index < length; index++) 591 { 592 if (!types1[index].equals(types2[index])) 593 { 594 return false; 595 } 596 } 597 598 return true; 599 } 600 601 602 /** 603 * Returns whether the given instruction opcode represents a dup or swap 604 * instruction (dup, dup_x1, dup_x2, dup2, dup2_x1, dup2_x2, swap). 605 */ 606 private boolean isDupOrSwap(int opcode) 607 { 608 return opcode >= InstructionConstants.OP_DUP && 609 opcode <= InstructionConstants.OP_SWAP; 610 } 611} 612