KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > jode > jvm > CodeVerifier


1 /* CodeVerifier Copyright (C) 1999-2002 Jochen Hoenicke.
2  *
3  * This program is free software; you can redistribute it and/or modify
4  * it under the terms of the GNU Lesser General Public License as published by
5  * the Free Software Foundation; either version 2, or (at your option)
6  * any later version.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  * GNU General Public License for more details.
12  *
13  * You should have received a copy of the GNU Lesser General Public License
14  * along with this program; see the file COPYING.LESSER. If not, write to
15  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
16  *
17  * $Id: CodeVerifier.java.in,v 1.4.2.4 2002/05/28 17:34:12 hoenicke Exp $
18  */

19
20 package jode.jvm;
21 import jode.AssertError;
22 import jode.GlobalOptions;
23 import jode.bytecode.BytecodeInfo;
24 import jode.bytecode.ClassInfo;
25 import jode.bytecode.Handler;
26 import jode.bytecode.Instruction;
27 import jode.bytecode.MethodInfo;
28 import jode.bytecode.Opcodes;
29 import jode.bytecode.Reference;
30 import jode.bytecode.TypeSignature;
31
32 import java.util.BitSet JavaDoc;
33 import java.util.Iterator JavaDoc;
34 import java.util.HashSet JavaDoc;
35 import java.util.List JavaDoc;
36 import java.util.ArrayList JavaDoc;
37
38 public class CodeVerifier implements Opcodes {
39     ClassInfo ci;
40     MethodInfo mi;
41     BytecodeInfo bi;
42
43     String JavaDoc methodType;
44     String JavaDoc returnType;
45
46     static Type tNull = Type.tType("0");
47     static Type tInt = Type.tType("I");
48     static Type tLong = Type.tType("J");
49     static Type tFloat = Type.tType("F");
50     static Type tDouble = Type.tType("D");
51     static Type tString = Type.tType("Ljava/lang/String;");
52     static Type tNone = Type.tType("?");
53     static Type tSecondPart = new Type("2");
54     static Type tObject = new Type("Ljava/lang/Object;");
55
56
57     /**
58      * We need some more types, than mentioned in jvm.
59      */

60     private static class Type {
61     /* "ZBCSIFJD" are the normal primitive types.
62      * "L...;" is normal class type.
63      * "[..." is normal array type
64      * "?" stands for type error
65      * "N...;" stands for new uninitialized type.
66      * "0" stands for null type.
67      * "R" stands for return address type.
68      * "2" stands for second half of a two word type.
69      */

70     private String JavaDoc typeSig;
71
72     /**
73      * The dependant instruction. This has two usages:
74      * <dl> <dt>"N...;"</dt>
75      * <dd> The new instruction, or null if this is the this param
76      * of &lt;init&gt;.</dd>
77      * <dt>"R"</dt> <dd>The <i>target</i> of the jsr.
78      */

79     private Instruction instr;
80
81     public Type(String JavaDoc typeSig) {
82         this.typeSig = typeSig;
83     }
84
85     public Type(String JavaDoc typeSig, Instruction instr) {
86         this.typeSig = typeSig;
87         this.instr = instr;
88     }
89
90     public static Type tType(String JavaDoc typeSig) {
91         // unify them?
92
return new Type(typeSig);
93     }
94
95     public static Type tType(String JavaDoc typeSig, Instruction instr) {
96         // unify them?
97
return new Type(typeSig, instr);
98     }
99
100     public String JavaDoc getTypeSig() {
101         return typeSig;
102     }
103     
104     public Instruction getInstruction() {
105         return instr;
106     }
107
108     /**
109      * @param t2 the type signature of the type to check for.
110      * This may be one of the special signatures:
111      * <dl><dt>"[*"<dt><dd>array of something</dd>
112      * <dt>"+"</dt><dd>(uninitialized) object/returnvalue type</dd>
113      * <dt>"2", "R"</dt> <dd>as the typeSig parameter </dd>
114      * </dl>
115      * @return true, iff this is castable to t2 by a
116      * widening cast. */

117     public boolean isOfType(String JavaDoc destSig) {
118         String JavaDoc thisSig = typeSig;
119         if ((GlobalOptions.debuggingFlags
120          & GlobalOptions.DEBUG_VERIFIER) != 0)
121         GlobalOptions.err.println("isOfType("+thisSig+","+destSig+")");
122         if (thisSig.equals(destSig))
123         return true;
124         
125         char c1 = thisSig.charAt(0);
126         char c2 = destSig.charAt(0);
127         switch (c2) {
128         case 'Z': case 'B': case 'C': case 'S': case 'I':
129         /* integer type */
130         return ("ZBCSI".indexOf(c1) >= 0);
131         case '+':
132         return ("L[nNR0".indexOf(c1) >= 0);
133
134         case '[':
135         if (c1 == '0')
136             return true;
137         while (c1 == '[' && c2 == '[') {
138             thisSig = thisSig.substring(1);
139             destSig = destSig.substring(1);
140             c1 = thisSig.charAt(0);
141             c2 = destSig.charAt(0);
142         }
143
144         if (c2 == '*')
145             /* destType is array of unknowns */
146             return true;
147         /* Note that short[] is only compatible to short[],
148          * therefore we only need to handle Object types specially.
149          */

150
151         if (c2 != 'L')
152             return false;
153         /* fall through*/
154         case 'L':
155         if (c1 == '0')
156             return true;
157         if ("L[".indexOf(c1) < 0)
158             return false;
159
160         ClassInfo wantedType = TypeSignature.getClassInfo(destSig);
161         if (wantedType.isInterface()
162             || wantedType == ClassInfo.javaLangObject)
163             return true;
164         if (c1 == 'L')
165             return wantedType.superClassOf(TypeSignature
166                            .getClassInfo(thisSig));
167         }
168         return false;
169     }
170
171     /**
172      * @return The common super type of this and type2.
173      */

174     public Type mergeType(Type type2) {
175         String JavaDoc sig1 = typeSig;
176         String JavaDoc sig2 = type2.typeSig;
177         
178         if (this.equals(type2))
179         return this;
180         
181         char c1 = sig1.charAt(0);
182         char c2 = sig2.charAt(0);
183         if (c1 == '*')
184         return type2;
185         if (c2 == '*')
186         return this;
187         if ("ZBCSI".indexOf(c1) >= 0 && "ZBCSI".indexOf(c2) >= 0)
188         return this;
189         
190         if (c1 == '0')
191         return ("L[0".indexOf(c2) >= 0) ? type2 : tNone;
192         if (c2 == '0')
193         return ("L[".indexOf(c1) >= 0) ? this : tNone;
194
195
196         int dimensions = 0;
197         /* Note that short[] is only compatible to short[],
198          * therefore we make the array handling after the primitive
199          * type handling. Also note that we don't allow arrays of
200          * special types.
201          */

202         while (c1 == '[' && c2 == '[') {
203         sig1 = sig1.substring(1);
204         sig2 = sig2.substring(1);
205         c1 = sig1.charAt(0);
206         c2 = sig2.charAt(0);
207         dimensions++;
208         }
209
210         // One of them is array now, the other is an object,
211
// the common super is tObject
212
if ((c1 == '[' && c2 == 'L')
213         || (c1 == 'L' && c2 == '[')) {
214         if (dimensions == 0)
215             return tObject;
216         StringBuffer JavaDoc result = new StringBuffer JavaDoc(dimensions + 18);
217         for (int i=0; i< dimensions; i++)
218             result.append("[");
219         result.append("Ljava/lang/Object;");
220         return tType(result.toString());
221         }
222
223         if (c1 == 'L' && c2 == 'L') {
224         ClassInfo clazz1 = TypeSignature.getClassInfo(sig1);
225         ClassInfo clazz2 = TypeSignature.getClassInfo(sig2);
226         if (clazz1.superClassOf(clazz2))
227             return this;
228         if (clazz2.superClassOf(clazz1))
229             return type2;
230         do {
231             clazz1 = clazz1.getSuperclass();
232         } while (!clazz1.superClassOf(clazz2));
233         StringBuffer JavaDoc result = new StringBuffer JavaDoc
234             (dimensions + clazz1.getName().length() + 2);
235         for (int i=0; i< dimensions; i++)
236             result.append("[");
237         result.append("L")
238             .append(clazz1.getName().replace('.', '/')).append(";");
239         return tType(result.toString());
240         }
241
242         // Both were arrays, but of different primitive types. The
243
// common super is tObject with one dimension less.
244
if (dimensions > 0) {
245         if (dimensions == 1)
246             return tObject;
247         StringBuffer JavaDoc result = new StringBuffer JavaDoc(dimensions + 17);
248         for (int i=0; i < dimensions - 1; i++)
249             result.append("[");
250         result.append("Ljava/lang/Object;");
251         return tType(result.toString());
252         }
253         return tNone;
254     }
255
256     public boolean equals(Object JavaDoc other) {
257         if (other instanceof Type) {
258         Type type2 = (Type) other;
259         return typeSig.equals(type2.typeSig)
260             && instr == type2.instr;
261         }
262         return false;
263     }
264
265     public String JavaDoc toString() {
266         if (instr != null)
267         return typeSig+"@"+instr.getAddr();
268         return typeSig;
269     }
270     }
271
272     /**
273      * JLS 4.9.6: Verifying code that contains a finally clause:
274      * - Each instruction keeps track of the list of jsr targets.
275      * - For each instruction and each jsr needed to reach that instruction
276      * a bit vector is maintained of all local vars accessed or modified.
277      */

278
279     class VerifyInfo implements Cloneable JavaDoc {
280     Type[] stack = new Type[bi.getMaxStack()];
281     Type[] locals = new Type[bi.getMaxLocals()];
282     Instruction[] jsrTargets = null;
283     BitSet JavaDoc[] jsrLocals = null;
284     int stackHeight = 0;
285     int maxHeight = 0;
286     /* If this is a jsr target, this field contains the single
287      * allowed ret instruction.
288      */

289     Instruction retInstr = null;
290
291     public Object JavaDoc clone() {
292         try {
293         VerifyInfo result = (VerifyInfo) super.clone();
294         result.stack = (Type[]) stack.clone();
295         result.locals = (Type[]) locals.clone();
296         return result;
297         } catch(CloneNotSupportedException JavaDoc ex) {
298         throw new AssertError("Clone not supported?");
299         }
300     }
301
302     public final void reserve(int count) throws VerifyException {
303         if (stackHeight + count > maxHeight) {
304         maxHeight = stackHeight + count;
305         if (maxHeight > stack.length)
306             throw new VerifyException("stack overflow");
307         }
308     }
309     
310     public final void need(int count) throws VerifyException {
311         if (stackHeight < count)
312         throw new VerifyException("stack underflow");
313     }
314     
315     public final void push(Type type) throws VerifyException {
316         reserve(1);
317         stack[stackHeight++] = type;
318     }
319     
320     public final Type pop() throws VerifyException {
321         need(1);
322         return stack[--stackHeight];
323     }
324     
325     public String JavaDoc toString() {
326         StringBuffer JavaDoc result = new StringBuffer JavaDoc("locals:[");
327         String JavaDoc comma = "";
328         for (int i=0; i<locals.length; i++) {
329         result.append(comma).append(i).append(':');
330         result.append(locals[i]);
331         comma = ",";
332         }
333         result.append("], stack:[");
334         comma = "";
335         for (int i=0; i<stackHeight; i++) {
336         result.append(comma).append(stack[i]);
337         comma = ",";
338         }
339         if (jsrTargets != null) {
340         result.append("], jsrs:[");
341         comma = "";
342         for (int i=0; i<jsrTargets.length; i++) {
343             result.append(comma).append(jsrTargets[i])
344             .append(jsrLocals[i]);
345             comma = ",";
346         }
347         }
348         return result.append("]").toString();
349     }
350     }
351
352
353     public CodeVerifier(ClassInfo ci, MethodInfo mi, BytecodeInfo bi) {
354     this.ci = ci;
355     this.mi = mi;
356     this.bi = bi;
357     this.methodType = mi.getType();
358     this.returnType = TypeSignature.getReturnType(methodType);
359     }
360
361     public VerifyInfo initInfo() {
362     VerifyInfo info = new VerifyInfo();
363     int pos = 1;
364     int slot = 0;
365     if (!mi.isStatic()) {
366         String JavaDoc clazzName = ci.getName().replace('.','/');
367         if (mi.getName().equals("<init>"))
368         info.locals[slot++] = Type.tType("N"+ clazzName+";", null);
369         else
370         info.locals[slot++] = Type.tType("L"+ clazzName+";");
371     }
372     while (methodType.charAt(pos) != ')') {
373         int start = pos;
374         pos = TypeSignature.skipType(methodType, pos);
375         String JavaDoc paramType = methodType.substring(start, pos);
376         info.locals[slot++] = Type.tType(paramType);
377         if (TypeSignature.getTypeSize(paramType) == 2)
378         info.locals[slot++] = tSecondPart;
379     }
380     while (slot < bi.getMaxLocals())
381         info.locals[slot++] = tNone;
382     return info;
383     }
384
385     public boolean mergeInfo(Instruction instr, VerifyInfo info)
386     throws VerifyException {
387     if (instr.getTmpInfo() == null) {
388         instr.setTmpInfo(info);
389         return true;
390     }
391     boolean changed = false;
392     VerifyInfo oldInfo = (VerifyInfo) instr.getTmpInfo();
393     if (oldInfo.stackHeight != info.stackHeight)
394         throw new VerifyException("Stack height differ at: "
395                       + instr.getDescription());
396     for (int i=0; i < oldInfo.stackHeight; i++) {
397         Type newType = oldInfo.stack[i].mergeType(info.stack[i]);
398         if (!newType.equals(oldInfo.stack[i])) {
399         if (newType == tNone)
400             throw new VerifyException("Type error while merging: "
401                           + oldInfo.stack[i]
402                           + " and " + info.stack[i]);
403         changed = true;
404         oldInfo.stack[i] = newType;
405         }
406     }
407     for (int i=0; i < bi.getMaxLocals(); i++) {
408         Type newType = oldInfo.locals[i].mergeType(info.locals[i]);
409         if (!newType.equals(oldInfo.locals[i])) {
410         changed = true;
411         oldInfo.locals[i] = newType;
412         }
413     }
414     if (oldInfo.jsrTargets != null) {
415         int jsrDepth;
416         if (info.jsrTargets == null)
417         jsrDepth = 0;
418         else {
419         jsrDepth = info.jsrTargets.length;
420         int infoPtr = 0;
421         oldInfo_loop:
422         for (int oldInfoPtr=0;
423              oldInfoPtr < oldInfo.jsrTargets.length; oldInfoPtr++) {
424             for (int i=infoPtr; i< jsrDepth; i++) {
425             if (oldInfo.jsrTargets[oldInfoPtr]
426                 == info.jsrTargets[i]) {
427                 System.arraycopy(info.jsrTargets, i,
428                          info.jsrTargets, infoPtr,
429                          jsrDepth - i);
430                 jsrDepth -= (i - infoPtr);
431                 infoPtr++;
432                 continue oldInfo_loop;
433             }
434             }
435         }
436         jsrDepth = infoPtr;
437         }
438         if (jsrDepth != oldInfo.jsrTargets.length) {
439         if (jsrDepth == 0)
440             oldInfo.jsrTargets = null;
441         else {
442             oldInfo.jsrTargets = new Instruction[jsrDepth];
443             System.arraycopy(info.jsrTargets, 0,
444                      oldInfo.jsrTargets, 0, jsrDepth);
445         }
446         changed = true;
447         }
448     }
449     return changed;
450     }
451
452
453     String JavaDoc[] types = {
454     "I", "J", "F", "D", "+", "B", "C", "S"
455     };
456     String JavaDoc[] arrayTypes = {
457     "[I", "[J", "[F", "[D", "[Ljava/lang/Object;", "[B", "[C", "[S"
458     };
459
460     public VerifyInfo modelEffect(Instruction instr, VerifyInfo prevInfo)
461     throws VerifyException {
462     int jsrLength =
463         prevInfo.jsrTargets != null ? prevInfo.jsrTargets.length : 0;
464     VerifyInfo result = (VerifyInfo) prevInfo.clone();
465     int opcode = instr.getOpcode();
466     switch (opcode) {
467     case opc_nop:
468     case opc_goto:
469         break;
470     case opc_ldc: {
471         Type type;
472         Object JavaDoc constant = instr.getConstant();
473         if (constant == null)
474         type = tNull;
475         else if (constant instanceof Integer JavaDoc)
476         type = tInt;
477         else if (constant instanceof Float JavaDoc)
478         type = tFloat;
479         else
480         type = tString;
481         result.push(type);
482         break;
483     }
484     case opc_ldc2_w: {
485         Type type;
486         Object JavaDoc constant = instr.getConstant();
487         if (constant instanceof Long JavaDoc)
488         type = tLong;
489         else
490         type = tDouble;
491         result.push(type);
492         result.push(tSecondPart);
493         break;
494     }
495     case opc_iload:
496     case opc_lload:
497     case opc_fload:
498     case opc_dload:
499     case opc_aload: {
500         if (jsrLength > 0
501         && (!result.jsrLocals[jsrLength-1].get(instr.getLocalSlot())
502             || ((opcode & 0x1) == 0
503             && !result.jsrLocals[jsrLength-1]
504             .get(instr.getLocalSlot()+1)))) {
505         result.jsrLocals = (BitSet JavaDoc[]) result.jsrLocals.clone();
506         result.jsrLocals[jsrLength-1]
507             = (BitSet JavaDoc) result.jsrLocals[jsrLength-1].clone();
508         result.jsrLocals[jsrLength-1].set(instr.getLocalSlot());
509         if ((opcode & 0x1) == 0)
510             result.jsrLocals[jsrLength-1].set(instr.getLocalSlot() + 1);
511         }
512         if ((opcode & 0x1) == 0
513         && result.locals[instr.getLocalSlot()+1] != tSecondPart)
514         throw new VerifyException(instr.getDescription());
515         Type type = result.locals[instr.getLocalSlot()];
516         if (!type.isOfType(types[opcode - opc_iload]))
517         throw new VerifyException(instr.getDescription());
518         result.push(type);
519         if ((opcode & 0x1) == 0)
520         result.push(tSecondPart);
521         break;
522     }
523     case opc_iaload: case opc_laload:
524     case opc_faload: case opc_daload: case opc_aaload:
525     case opc_baload: case opc_caload: case opc_saload: {
526         if (!result.pop().isOfType("I"))
527         throw new VerifyException(instr.getDescription());
528         Type arrType = result.pop();
529         if (!arrType.isOfType(arrayTypes[opcode - opc_iaload])
530         && (opcode != opc_baload
531             || !arrType.isOfType("[Z")))
532         throw new VerifyException(instr.getDescription());
533         
534         String JavaDoc typeSig = arrType.getTypeSig();
535         Type elemType = (typeSig.charAt(0) == '['
536                  ? Type.tType(typeSig.substring(1))
537                  : (opcode == opc_aaload ? tNull
538                 : Type.tType(types[opcode - opc_iaload])));
539         result.push(elemType);
540         if (((1 << opcode - opc_iaload) & 0xa) != 0)
541         result.push(tSecondPart);
542         break;
543     }
544     case opc_istore: case opc_lstore:
545     case opc_fstore: case opc_dstore: case opc_astore: {
546         if (jsrLength > 0
547         && (!result.jsrLocals[jsrLength-1].get(instr.getLocalSlot())
548             || ((opcode & 0x1) != 0
549             && !result.jsrLocals[jsrLength-1]
550             .get(instr.getLocalSlot()+1)))) {
551         result.jsrLocals = (BitSet JavaDoc[]) result.jsrLocals.clone();
552         result.jsrLocals[jsrLength-1]
553             = (BitSet JavaDoc) result.jsrLocals[jsrLength-1].clone();
554         result.jsrLocals[jsrLength-1].set(instr.getLocalSlot());
555         if ((opcode & 0x1) != 0)
556             result.jsrLocals[jsrLength-1].set(instr.getLocalSlot() + 1);
557         }
558         if ((opcode & 0x1) != 0
559         && result.pop() != tSecondPart)
560         throw new VerifyException(instr.getDescription());
561         Type type = result.pop();
562         if (!type.isOfType(types[opcode - opc_istore]))
563         if (opcode != opc_astore || !type.isOfType("R"))
564             throw new VerifyException(instr.getDescription());
565         result.locals[instr.getLocalSlot()] = type;
566         if ((opcode & 0x1) != 0)
567         result.locals[instr.getLocalSlot()+1] = tSecondPart;
568         break;
569     }
570     case opc_iastore: case opc_lastore:
571     case opc_fastore: case opc_dastore: case opc_aastore:
572     case opc_bastore: case opc_castore: case opc_sastore: {
573         if (((1 << opcode - opc_iastore) & 0xa) != 0
574         && result.pop() != tSecondPart)
575         throw new VerifyException(instr.getDescription());
576         Type type = result.pop();
577         if (!result.pop().isOfType("I"))
578         throw new VerifyException(instr.getDescription());
579         Type arrType = result.pop();
580         if (!arrType.isOfType(arrayTypes[opcode - opc_iastore])
581         && (opcode != opc_bastore || !arrType.isOfType("[Z")))
582         throw new VerifyException(instr.getDescription());
583         String JavaDoc elemType = opcode >= opc_bastore ? "I"
584         : types[opcode - opc_iastore];
585         if (!type.isOfType(elemType))
586         throw new VerifyException(instr.getDescription());
587         break;
588     }
589     case opc_pop: case opc_pop2: {
590         int count = opcode - (opc_pop-1);
591         result.need(count);
592         result.stackHeight -= count;
593         break;
594     }
595     case opc_dup: case opc_dup_x1: case opc_dup_x2: {
596         int depth = opcode - opc_dup;
597         result.reserve(1);
598         result.need(depth+1);
599         if (result.stack[result.stackHeight-1] == tSecondPart)
600         throw new VerifyException(instr.getDescription());
601         
602         int stackdepth = result.stackHeight - (depth + 1);
603         if (result.stack[stackdepth] == tSecondPart)
604         throw new VerifyException(instr.getDescription()
605                       + " on long or double");
606         for (int i=result.stackHeight; i > stackdepth; i--)
607         result.stack[i] = result.stack[i-1];
608         result.stack[stackdepth] = result.stack[result.stackHeight++];
609         break;
610     }
611     case opc_dup2: case opc_dup2_x1: case opc_dup2_x2: {
612         int depth = opcode - opc_dup2;
613         result.reserve(2);
614         result.need(depth+2);
615         if (result.stack[result.stackHeight-2] == tSecondPart)
616         throw new VerifyException(instr.getDescription()
617                       + " on misaligned long or double");
618         int stacktop = result.stackHeight;
619         int stackdepth = stacktop - (depth + 2);
620         if (result.stack[stackdepth] == tSecondPart)
621         throw new VerifyException(instr.getDescription()
622                       + " on long or double");
623         for (int i=stacktop; i > stackdepth; i--)
624         result.stack[i+1] = result.stack[i-1];
625         result.stack[stackdepth+1] = result.stack[stacktop+1];
626         result.stack[stackdepth] = result.stack[stacktop];
627         result.stackHeight+=2;
628         break;
629     }
630     case opc_swap: {
631         result.need(2);
632         if (result.stack[result.stackHeight-2] == tSecondPart
633         || result.stack[result.stackHeight-1] == tSecondPart)
634         throw new VerifyException(instr.getDescription()
635                       + " on misaligned long or double");
636         Type tmp = result.stack[result.stackHeight-1];
637         result.stack[result.stackHeight-1] =
638         result.stack[result.stackHeight-2];
639         result.stack[result.stackHeight-2] = tmp;
640         break;
641     }
642         case opc_iadd: case opc_ladd: case opc_fadd: case opc_dadd:
643         case opc_isub: case opc_lsub: case opc_fsub: case opc_dsub:
644         case opc_imul: case opc_lmul: case opc_fmul: case opc_dmul:
645         case opc_idiv: case opc_ldiv: case opc_fdiv: case opc_ddiv:
646         case opc_irem: case opc_lrem: case opc_frem: case opc_drem: {
647         String JavaDoc type = types[(opcode - opc_iadd) & 3];
648         if ((opcode & 1) != 0
649         && result.pop() != tSecondPart)
650         throw new VerifyException(instr.getDescription());
651         if (!result.pop().isOfType(type))
652         throw new VerifyException(instr.getDescription());
653         if ((opcode & 1) != 0) {
654         result.need(2);
655         if (result.stack[result.stackHeight-1] != tSecondPart
656             || !result.stack[result.stackHeight-2].isOfType(type))
657             throw new VerifyException(instr.getDescription());
658         } else {
659         result.need(1);
660         if (!result.stack[result.stackHeight-1].isOfType(type))
661             throw new VerifyException(instr.getDescription());
662         }
663         break;
664     }
665         case opc_ineg: case opc_lneg: case opc_fneg: case opc_dneg: {
666         String JavaDoc type = types[(opcode - opc_ineg) & 3];
667         if ((opcode & 1) != 0) {
668         result.need(2);
669         if (result.stack[result.stackHeight-1] != tSecondPart
670             || !result.stack[result.stackHeight-2].isOfType(type))
671             throw new VerifyException(instr.getDescription());
672         } else {
673         result.need(1);
674         if (!result.stack[result.stackHeight-1].isOfType(type))
675             throw new VerifyException(instr.getDescription());
676         }
677         break;
678     }
679         case opc_ishl: case opc_lshl:
680         case opc_ishr: case opc_lshr:
681         case opc_iushr: case opc_lushr:
682         if (!result.pop().isOfType("I"))
683         throw new VerifyException(instr.getDescription());
684         
685         if ((opcode & 1) != 0) {
686         result.need(2);
687         if (result.stack[result.stackHeight-1] != tSecondPart ||
688             !result.stack[result.stackHeight-2].isOfType("J"))
689             throw new VerifyException(instr.getDescription());
690         } else {
691         result.need(1);
692         if (!result.stack[result.stackHeight-1].isOfType("I"))
693             throw new VerifyException(instr.getDescription());
694         }
695         break;
696
697         case opc_iand: case opc_land:
698         case opc_ior : case opc_lor :
699         case opc_ixor: case opc_lxor:
700         if ((opcode & 1) != 0
701         && result.pop() != tSecondPart)
702         throw new VerifyException(instr.getDescription());
703         if (!result.pop().isOfType(types[opcode & 1]))
704         throw new VerifyException(instr.getDescription());
705         if ((opcode & 1) != 0) {
706         result.need(2);
707         if (result.stack[result.stackHeight-1] != tSecondPart
708             || !result.stack[result.stackHeight-2].isOfType("J"))
709             throw new VerifyException(instr.getDescription());
710         } else {
711         result.need(1);
712         if (!result.stack[result.stackHeight-1].isOfType("I"))
713             throw new VerifyException(instr.getDescription());
714         }
715         break;
716
717     case opc_iinc:
718         if (!result.locals[instr.getLocalSlot()].isOfType("I"))
719         throw new VerifyException(instr.getDescription());
720         break;
721         case opc_i2l: case opc_i2f: case opc_i2d:
722         case opc_l2i: case opc_l2f: case opc_l2d:
723         case opc_f2i: case opc_f2l: case opc_f2d:
724         case opc_d2i: case opc_d2l: case opc_d2f: {
725             int from = (opcode-opc_i2l)/3;
726             int to = (opcode-opc_i2l)%3;
727             if (to >= from)
728                 to++;
729         if ((from & 1) != 0
730         && result.pop() != tSecondPart)
731         throw new VerifyException(instr.getDescription());
732         if (!result.pop().isOfType(types[from]))
733         throw new VerifyException(instr.getDescription());
734         
735         result.push(Type.tType(types[to]));
736         if ((to & 1) != 0)
737         result.push(tSecondPart);
738         break;
739     }
740         case opc_i2b: case opc_i2c: case opc_i2s:
741         result.need(1);
742         if (!result.stack[result.stackHeight-1].isOfType("I"))
743         throw new VerifyException(instr.getDescription());
744         break;
745
746     case opc_lcmp:
747         if (result.pop() != tSecondPart)
748         throw new VerifyException(instr.getDescription());
749         if (!result.pop().isOfType("J"))
750         throw new VerifyException(instr.getDescription());
751         if (result.pop() != tSecondPart)
752         throw new VerifyException(instr.getDescription());
753         if (!result.pop().isOfType("J"))
754         throw new VerifyException(instr.getDescription());
755         result.push(tInt);
756         break;
757     case opc_dcmpl: case opc_dcmpg:
758         if (result.pop() != tSecondPart)
759         throw new VerifyException(instr.getDescription());
760         if (!result.pop().isOfType("D"))
761         throw new VerifyException(instr.getDescription());
762         if (result.pop() != tSecondPart)
763         throw new VerifyException(instr.getDescription());
764         if (!result.pop().isOfType("D"))
765         throw new VerifyException(instr.getDescription());
766         result.push(tInt);
767         break;
768     case opc_fcmpl: case opc_fcmpg:
769         if (!result.pop().isOfType("F"))
770         throw new VerifyException(instr.getDescription());
771         if (!result.pop().isOfType("F"))
772         throw new VerifyException(instr.getDescription());
773         result.push(tInt);
774         break;
775
776     case opc_ifeq: case opc_ifne:
777     case opc_iflt: case opc_ifge:
778     case opc_ifgt: case opc_ifle:
779     case opc_tableswitch:
780     case opc_lookupswitch:
781         if (!result.pop().isOfType("I"))
782         throw new VerifyException(instr.getDescription());
783         break;
784
785     case opc_if_icmpeq: case opc_if_icmpne:
786     case opc_if_icmplt: case opc_if_icmpge:
787     case opc_if_icmpgt: case opc_if_icmple:
788         if (!result.pop().isOfType("I"))
789         throw new VerifyException(instr.getDescription());
790         if (!result.pop().isOfType("I"))
791         throw new VerifyException(instr.getDescription());
792         break;
793     case opc_if_acmpeq: case opc_if_acmpne:
794         if (!result.pop().isOfType("+"))
795         throw new VerifyException(instr.getDescription());
796         if (!result.pop().isOfType("+"))
797         throw new VerifyException(instr.getDescription());
798         break;
799     case opc_ifnull: case opc_ifnonnull:
800         if (!result.pop().isOfType("+"))
801         throw new VerifyException(instr.getDescription());
802         break;
803
804     case opc_ireturn: case opc_lreturn:
805     case opc_freturn: case opc_dreturn: case opc_areturn: {
806         if (((1 << opcode - opc_ireturn) & 0xa) != 0
807         && result.pop() != tSecondPart)
808         throw new VerifyException(instr.getDescription());
809         Type type = result.pop();
810         if (!type.isOfType(types[opcode - opc_ireturn])
811         || !type.isOfType(TypeSignature.getReturnType(methodType)))
812         throw new VerifyException(instr.getDescription());
813         break;
814     }
815     case opc_jsr: {
816         Instruction jsrTarget = instr.getSingleSucc();
817         result.stack[result.stackHeight++] = Type.tType("R", jsrTarget);
818         result.jsrTargets = new Instruction[jsrLength+1];
819         result.jsrLocals = new BitSet JavaDoc[jsrLength+1];
820         if (jsrLength > 0) {
821         for (int i=0; i< prevInfo.jsrTargets.length; i++)
822             if (prevInfo.jsrTargets[i] == instr.getSingleSucc())
823             throw new VerifyException(instr.getDescription()+
824                           " is recursive");
825         System.arraycopy(prevInfo.jsrTargets, 0,
826                  result.jsrTargets, 0, jsrLength);
827         System.arraycopy(prevInfo.jsrLocals, 0,
828                  result.jsrLocals, 0, jsrLength);
829         }
830         result.jsrTargets[jsrLength] = instr.getSingleSucc();
831         result.jsrLocals[jsrLength] = new BitSet JavaDoc();
832         break;
833     }
834     case opc_return:
835         if (!returnType.equals("V"))
836         throw new VerifyException(instr.getDescription());
837         break;
838     case opc_getstatic: {
839         Reference ref = instr.getReference();
840         String JavaDoc type = ref.getType();
841         result.push(Type.tType(type));
842         if (TypeSignature.getTypeSize(type) == 2)
843         result.push(tSecondPart);
844         break;
845     }
846     case opc_getfield: {
847         Reference ref = instr.getReference();
848         String JavaDoc classType = ref.getClazz();
849         if (!result.pop().isOfType(classType))
850         throw new VerifyException(instr.getDescription());
851         String JavaDoc type = ref.getType();
852         result.push(Type.tType(type));
853         if (TypeSignature.getTypeSize(type) == 2)
854         result.push(tSecondPart);
855         break;
856     }
857     case opc_putstatic: {
858         Reference ref = instr.getReference();
859         String JavaDoc type = ref.getType();
860         if (TypeSignature.getTypeSize(type) == 2
861         && result.pop() != tSecondPart)
862         throw new VerifyException(instr.getDescription());
863         if (!result.pop().isOfType(type))
864         throw new VerifyException(instr.getDescription());
865         break;
866     }
867     case opc_putfield: {
868         Reference ref = instr.getReference();
869         String JavaDoc type = ref.getType();
870         if (TypeSignature.getTypeSize(type) == 2
871         && result.pop() != tSecondPart)
872         throw new VerifyException(instr.getDescription());
873         if (!result.pop().isOfType(type))
874         throw new VerifyException(instr.getDescription());
875         String JavaDoc classType = ref.getClazz();
876         if (!result.pop().isOfType(classType))
877         throw new VerifyException(instr.getDescription());
878         break;
879     }
880     case opc_invokevirtual:
881     case opc_invokespecial:
882     case opc_invokestatic :
883     case opc_invokeinterface: {
884         Reference ref = instr.getReference();
885         String JavaDoc refmt = ref.getType();
886         String JavaDoc[] paramTypes = TypeSignature.getParameterTypes(refmt);
887         for (int i=paramTypes.length - 1; i >= 0; i--) {
888         if (TypeSignature.getTypeSize(paramTypes[i]) == 2
889             && result.pop() != tSecondPart)
890             throw new VerifyException(instr.getDescription());
891         if (!result.pop().isOfType(paramTypes[i]))
892             throw new VerifyException(instr.getDescription());
893         }
894         if (ref.getName().equals("<init>")) {
895             Type clazz = result.pop();
896         String JavaDoc typeSig = clazz.getTypeSig();
897         String JavaDoc refClazz = ref.getClazz();
898         if (opcode != opc_invokespecial
899             || typeSig.charAt(0) != 'N'
900             || refClazz.charAt(0) != 'L')
901             throw new VerifyException(instr.getDescription());
902         if (!typeSig.substring(1).equals(refClazz.substring(1))) {
903             ClassInfo uci = ClassInfo.forName
904             (typeSig.substring(1, typeSig.length()-1)
905              .replace('/', '.'));
906             if (uci.getSuperclass()
907             != TypeSignature.getClassInfo(refClazz)
908             || clazz.getInstruction() != null)
909             throw new VerifyException(instr.getDescription());
910         }
911         Type newType = Type.tType("L" + typeSig.substring(1));
912         for (int i=0; i< result.stackHeight; i++)
913             if (result.stack[i] == clazz)
914             result.stack[i] = newType;
915         for (int i=0; i< result.locals.length; i++)
916             if (result.locals[i] == clazz)
917             result.locals[i] = newType;
918         } else if (opcode != opc_invokestatic) {
919         String JavaDoc classType = ref.getClazz();
920         if (!result.pop().isOfType(classType))
921             throw new VerifyException(instr.getDescription());
922         }
923         String JavaDoc type = TypeSignature.getReturnType(refmt);
924         if (!type.equals("V")) {
925         result.push(Type.tType(type));
926         if (TypeSignature.getTypeSize(type) == 2)
927             result.push(tSecondPart);
928         }
929         break;
930     }
931     case opc_new: {
932         String JavaDoc clName = instr.getClazzType();
933         result.stack[result.stackHeight++] =
934         Type.tType("N" + clName.substring(1), instr);
935         break;
936     }
937     case opc_arraylength: {
938         if (!result.pop().isOfType("[*"))
939         throw new VerifyException(instr.getDescription());
940         result.push(tInt);
941         break;
942     }
943     case opc_athrow: {
944         if (!result.pop().isOfType("Ljava/lang/Throwable;"))
945         throw new VerifyException(instr.getDescription());
946         break;
947     }
948     case opc_checkcast: {
949         String JavaDoc classType = instr.getClazzType();
950         if (!result.pop().isOfType("+"))
951         throw new VerifyException(instr.getDescription());
952         result.push(Type.tType(classType));
953         break;
954     }
955     case opc_instanceof: {
956         if (!result.pop().isOfType("Ljava/lang/Object;"))
957         throw new VerifyException(instr.getDescription());
958         result.push(tInt);
959         break;
960     }
961     case opc_monitorenter:
962     case opc_monitorexit:
963         if (!result.pop().isOfType("Ljava/lang/Object;"))
964         throw new VerifyException(instr.getDescription());
965         break;
966     case opc_multianewarray: {
967         int dimension = instr.getDimensions();
968         for (int i=dimension - 1; i >= 0; i--)
969         if (!result.pop().isOfType("I"))
970             throw new VerifyException(instr.getDescription());
971         String JavaDoc classType = instr.getClazzType();
972         result.push(Type.tType(classType));
973         break;
974     }
975     default:
976         throw new AssertError("Invalid opcode "+opcode);
977     }
978     return result;
979     }
980     
981     public void doVerify() throws VerifyException {
982     HashSet JavaDoc todoSet = new HashSet JavaDoc();
983
984     Instruction firstInstr = (Instruction) bi.getInstructions().get(0);
985     firstInstr.setTmpInfo(initInfo());
986     todoSet.add(firstInstr);
987     Handler[] handlers = bi.getExceptionHandlers();
988     while (!todoSet.isEmpty()) {
989         Iterator JavaDoc iter = todoSet.iterator();
990         Instruction instr = (Instruction) iter.next();
991         iter.remove();
992         if (!instr.doesAlwaysJump() && instr.getNextByAddr() == null)
993         throw new VerifyException("Flow can fall off end of method");
994
995         VerifyInfo prevInfo = (VerifyInfo) instr.getTmpInfo();
996         int opcode = instr.getOpcode();
997         if (opcode == opc_ret) {
998         Type retVarType = prevInfo.locals[instr.getLocalSlot()];
999         if (prevInfo.jsrTargets == null
1000            || !retVarType.isOfType("R"))
1001            throw new VerifyException(instr.getDescription());
1002        int jsrLength = prevInfo.jsrTargets.length - 1;
1003        Instruction jsrTarget = retVarType.getInstruction();
1004        while (jsrTarget != prevInfo.jsrTargets[jsrLength])
1005            if (--jsrLength < 0)
1006            throw new VerifyException(instr.getDescription());
1007        VerifyInfo jsrTargetInfo = (VerifyInfo) jsrTarget.getTmpInfo();
1008        if (jsrTargetInfo.retInstr == null)
1009            jsrTargetInfo.retInstr = instr;
1010        else if (jsrTargetInfo.retInstr != instr)
1011            throw new VerifyException
1012            ("JsrTarget has more than one ret: "
1013             + jsrTarget.getDescription());
1014        Instruction[] nextTargets;
1015        BitSet JavaDoc[] nextLocals;
1016        if (jsrLength > 0) {
1017            nextTargets = new Instruction[jsrLength];
1018            nextLocals = new BitSet JavaDoc[jsrLength];
1019            System.arraycopy(prevInfo.jsrTargets, 0,
1020                     nextTargets, 0, jsrLength);
1021            System.arraycopy(prevInfo.jsrLocals, 0,
1022                     nextLocals, 0, jsrLength);
1023        } else {
1024            nextTargets = null;
1025            nextLocals = null;
1026        }
1027        for (int i=0; i < jsrTarget.getPreds().length; i++) {
1028            Instruction jsrInstr = jsrTarget.getPreds()[i];
1029            if (jsrInstr.getTmpInfo() != null)
1030            todoSet.add(jsrInstr);
1031        }
1032        } else {
1033        VerifyInfo info = modelEffect(instr, prevInfo);
1034        if (!instr.doesAlwaysJump())
1035            if (mergeInfo(instr.getNextByAddr(), info))
1036            todoSet.add(instr.getNextByAddr());
1037        if (opcode == opc_jsr) {
1038            VerifyInfo targetInfo =
1039            (VerifyInfo) instr.getSingleSucc().getTmpInfo();
1040            if (targetInfo != null && targetInfo.retInstr != null) {
1041            VerifyInfo afterJsrInfo
1042                = (VerifyInfo) prevInfo.clone();
1043            VerifyInfo retInfo
1044                = (VerifyInfo) targetInfo.retInstr.getTmpInfo();
1045            BitSet JavaDoc usedLocals
1046                = retInfo.jsrLocals[retInfo.jsrLocals.length-1];
1047            for (int j = 0; j < bi.getMaxLocals(); j++) {
1048                if (usedLocals.get(j))
1049                afterJsrInfo.locals[j] = retInfo.locals[j];
1050            }
1051            if (mergeInfo(instr.getNextByAddr(), afterJsrInfo))
1052                todoSet.add(instr.getNextByAddr());
1053            }
1054        }
1055        if (instr.getSuccs() != null) {
1056            for (int i=0; i< instr.getSuccs().length; i++) {
1057            if (mergeInfo(instr.getSuccs()[i],
1058                      (VerifyInfo) info.clone()))
1059                todoSet.add(instr.getSuccs()[i]);
1060            }
1061        }
1062        for (int i=0; i<handlers.length; i++) {
1063            if (handlers[i].start.compareTo(instr) <= 0
1064            && handlers[i].end.compareTo(instr) >= 0) {
1065            VerifyInfo excInfo = (VerifyInfo) prevInfo.clone();
1066            excInfo.stackHeight = 1;
1067            if (handlers[i].type != null)
1068                excInfo.stack[0] =
1069                Type.tType("L" + handlers[i].type
1070                       .replace('.', '/') + ";");
1071            else
1072                excInfo.stack[0]
1073                = Type.tType("Ljava/lang/Throwable;");
1074            if (mergeInfo(handlers[i].catcher, excInfo))
1075                todoSet.add(handlers[i].catcher);
1076            }
1077        }
1078        }
1079    }
1080
1081    if ((GlobalOptions.debuggingFlags
1082         & GlobalOptions.DEBUG_VERIFIER) != 0) {
1083        for (Iterator JavaDoc i = bi.getInstructions().iterator(); i.hasNext(); ) {
1084        Instruction instr = (Instruction) i.next();
1085
1086        VerifyInfo info = (VerifyInfo) instr.getTmpInfo();
1087        if (info != null)
1088            GlobalOptions.err.println(info.toString());
1089        GlobalOptions.err.println(instr.getDescription());
1090
1091        }
1092    }
1093    for (Iterator JavaDoc i = bi.getInstructions().iterator(); i.hasNext(); ) {
1094        Instruction instr = (Instruction) i.next();
1095        instr.setTmpInfo(null);
1096    }
1097    }
1098
1099
1100    public void verify() throws VerifyException {
1101    try {
1102        doVerify();
1103    } catch (VerifyException ex) {
1104        for (Iterator JavaDoc i = bi.getInstructions().iterator(); i.hasNext(); ) {
1105        Instruction instr = (Instruction) i.next();
1106        VerifyInfo info = (VerifyInfo) instr.getTmpInfo();
1107        if (info != null)
1108            GlobalOptions.err.println(info.toString());
1109        GlobalOptions.err.println(instr.getDescription());
1110
1111        instr.setTmpInfo(null);
1112        }
1113        throw ex;
1114    }
1115    }
1116}
1117
Popular Tags