CodePreverifier


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