1/*
2 * Javassist, a Java-bytecode translator toolkit.
3 * Copyright (C) 1999-2007 Shigeru Chiba. All Rights Reserved.
4 *
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License.  Alternatively, the contents of this file may be used under
8 * the terms of the GNU Lesser General Public License Version 2.1 or later.
9 *
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
13 * License.
14 */
15
16package javassist.bytecode.stackmap;
17
18import javassist.ClassPool;
19import javassist.bytecode.*;
20
21/**
22 * Stack map maker.
23 */
24public class MapMaker extends Tracer {
25    /*
26    public static void main(String[] args) throws Exception {
27        boolean useMain2 = args[0].equals("0");
28        if (useMain2 && args.length > 1) {
29            main2(args);
30            return;
31        }
32
33        for (int i = 0; i < args.length; i++)
34            main1(args[i]);
35    }
36
37    public static void main1(String className) throws Exception {
38        ClassPool cp = ClassPool.getDefault();
39        //javassist.CtClass cc = cp.get(className);
40        javassist.CtClass cc = cp.makeClass(new java.io.FileInputStream(className));
41        System.out.println(className);
42        ClassFile cf = cc.getClassFile();
43        java.util.List minfos = cf.getMethods();
44        for (int i = 0; i < minfos.size(); i++) {
45            MethodInfo minfo = (MethodInfo)minfos.get(i);
46            CodeAttribute ca = minfo.getCodeAttribute();
47            if (ca != null)
48                ca.setAttribute(make(cp, minfo));
49        }
50
51        cc.writeFile("tmp");
52    }
53
54    public static void main2(String[] args) throws Exception {
55        ClassPool cp = ClassPool.getDefault();
56        //javassist.CtClass cc = cp.get(args[1]);
57        javassist.CtClass cc = cp.makeClass(new java.io.FileInputStream(args[1]));
58        MethodInfo minfo;
59        if (args[2].equals("_init_"))
60            minfo = cc.getDeclaredConstructors()[0].getMethodInfo();
61            // minfo = cc.getClassInitializer().getMethodInfo();
62        else
63            minfo = cc.getDeclaredMethod(args[2]).getMethodInfo();
64
65        CodeAttribute ca = minfo.getCodeAttribute();
66        if (ca == null) {
67            System.out.println("abstarct method");
68            return;
69        }
70
71        TypedBlock[] blocks = TypedBlock.makeBlocks(minfo, ca, false);
72        MapMaker mm = new MapMaker(cp, minfo, ca);
73        mm.make(blocks, ca.getCode());
74        for (int i = 0; i < blocks.length; i++)
75            System.out.println(blocks[i]);
76    }
77    */
78
79    /**
80     * Computes the stack map table of the given method and returns it.
81     * It returns null if the given method does not have to have a
82     * stack map table.
83     */
84    public static StackMapTable make(ClassPool classes, MethodInfo minfo)
85        throws BadBytecode
86    {
87        CodeAttribute ca = minfo.getCodeAttribute();
88        if (ca == null)
89            return null;
90
91        TypedBlock[] blocks = TypedBlock.makeBlocks(minfo, ca, true);
92        if (blocks == null)
93            return null;
94
95        MapMaker mm = new MapMaker(classes, minfo, ca);
96        mm.make(blocks, ca.getCode());
97        return mm.toStackMap(blocks);
98    }
99
100    /**
101     * Computes the stack map table for J2ME.
102     * It returns null if the given method does not have to have a
103     * stack map table.
104     */
105    public static StackMap make2(ClassPool classes, MethodInfo minfo)
106        throws BadBytecode
107    {
108        CodeAttribute ca = minfo.getCodeAttribute();
109        if (ca == null)
110            return null;
111
112        TypedBlock[] blocks = TypedBlock.makeBlocks(minfo, ca, true);
113        if (blocks == null)
114            return null;
115
116        MapMaker mm = new MapMaker(classes, minfo, ca);
117        mm.make(blocks, ca.getCode());
118        return mm.toStackMap2(minfo.getConstPool(), blocks);
119    }
120
121    public MapMaker(ClassPool classes, MethodInfo minfo, CodeAttribute ca) {
122        super(classes, minfo.getConstPool(),
123              ca.getMaxStack(), ca.getMaxLocals(),
124              TypedBlock.getRetType(minfo.getDescriptor()));
125    }
126
127    protected MapMaker(MapMaker old, boolean copyStack) {
128        super(old, copyStack);
129    }
130
131    /**
132     * Runs an analyzer (Phase 1 and 2).
133     */
134    void make(TypedBlock[] blocks, byte[] code)
135        throws BadBytecode
136    {
137        TypedBlock first = blocks[0];
138        fixParamTypes(first);
139        TypeData[] srcTypes = first.localsTypes;
140        copyFrom(srcTypes.length, srcTypes, this.localsTypes);
141        make(code, first);
142
143        int n = blocks.length;
144        for (int i = 0; i < n; i++)
145            evalExpected(blocks[i]);
146    }
147
148    /*
149     * If a parameter type is String but it is used only as Object
150     * within the method body, this MapMaker class will report its type
151     * is Object.  To avoid this, fixParamTypes calls TypeData.setType()
152     * on each parameter type.
153     */
154    private void fixParamTypes(TypedBlock first) throws BadBytecode {
155        TypeData[] types = first.localsTypes;
156        int n = types.length;
157        for (int i = 0; i < n; i++) {
158            TypeData t = types[i];
159            if (t instanceof TypeData.ClassName) {
160                /* Skip the following statement if t.isNullType() is true
161                 * although a parameter type is never null type.
162                 */
163                TypeData.setType(t, t.getName(), classPool);
164            }
165        }
166    }
167
168    // Phase 1
169
170    private void make(byte[] code, TypedBlock tb)
171        throws BadBytecode
172    {
173        BasicBlock.Catch handlers = tb.toCatch;
174        while (handlers != null) {
175            traceException(code, handlers);
176            handlers = handlers.next;
177        }
178
179        int pos = tb.position;
180        int end = pos + tb.length;
181        while (pos < end)
182            pos += doOpcode(pos, code);
183
184        if (tb.exit != null) {
185            for (int i = 0; i < tb.exit.length; i++) {
186                TypedBlock e = (TypedBlock)tb.exit[i];
187                if (e.alreadySet())
188                    mergeMap(e, true);
189                else {
190                    recordStackMap(e);
191                    MapMaker maker = new MapMaker(this, true);
192                    maker.make(code, e);
193                }
194            }
195        }
196    }
197
198    private void traceException(byte[] code, TypedBlock.Catch handler)
199        throws BadBytecode
200    {
201        TypedBlock tb = (TypedBlock)handler.body;
202        if (tb.alreadySet())
203            mergeMap(tb, false);
204        else {
205            recordStackMap(tb, handler.typeIndex);
206            MapMaker maker = new MapMaker(this, false);
207
208            /* the following code is equivalent to maker.copyFrom(this)
209             * except stackTypes are not copied.
210             */
211            maker.stackTypes[0] = tb.stackTypes[0].getSelf();
212            maker.stackTop = 1;
213            maker.make(code, tb);
214        }
215    }
216
217    private void mergeMap(TypedBlock dest, boolean mergeStack) {
218        boolean[] inputs = dest.inputs;
219        int n = inputs.length;
220        for (int i = 0; i < n; i++)
221            if (inputs[i])
222                merge(localsTypes[i], dest.localsTypes[i]);
223
224        if (mergeStack) {
225            n = stackTop;
226            for (int i = 0; i < n; i++)
227                merge(stackTypes[i], dest.stackTypes[i]);
228        }
229    }
230
231    private void merge(TypeData td, TypeData target) {
232        boolean tdIsObj = false;
233        boolean targetIsObj = false;
234        // td or target is null if it is TOP.
235        if (td != TOP && td.isObjectType())
236            tdIsObj = true;
237
238        if (target != TOP && target.isObjectType())
239            targetIsObj = true;
240
241        if (tdIsObj && targetIsObj)
242            target.merge(td);
243    }
244
245    private void recordStackMap(TypedBlock target)
246        throws BadBytecode
247    {
248        TypeData[] tStackTypes = new TypeData[stackTypes.length];
249        int st = stackTop;
250        copyFrom(st, stackTypes, tStackTypes);
251        recordStackMap0(target, st, tStackTypes);
252    }
253
254    private void recordStackMap(TypedBlock target, int exceptionType)
255        throws BadBytecode
256    {
257        String type;
258        if (exceptionType == 0)
259            type = "java.lang.Throwable";
260        else
261            type = cpool.getClassInfo(exceptionType);
262
263        TypeData[] tStackTypes = new TypeData[stackTypes.length];
264        tStackTypes[0] = new TypeData.ClassName(type);
265
266        recordStackMap0(target, 1, tStackTypes);
267    }
268
269    private void recordStackMap0(TypedBlock target, int st, TypeData[] tStackTypes)
270        throws BadBytecode
271    {
272        int n = localsTypes.length;
273        TypeData[] tLocalsTypes = new TypeData[n];
274        int k = copyFrom(n, localsTypes, tLocalsTypes);
275
276        boolean[] inputs = target.inputs;
277        for (int i = 0; i < n; i++)
278            if (!inputs[i])
279                tLocalsTypes[i] = TOP;
280
281        target.setStackMap(st, tStackTypes, k, tLocalsTypes);
282    }
283
284    // Phase 2
285
286    void evalExpected(TypedBlock target) throws BadBytecode {
287        ClassPool cp = classPool;
288        evalExpected(cp, target.stackTop, target.stackTypes);
289        TypeData[] types = target.localsTypes;
290        if (types != null)  // unless this block is dead code
291            evalExpected(cp, types.length, types);
292    }
293
294    private static void evalExpected(ClassPool cp, int n, TypeData[] types)
295        throws BadBytecode
296    {
297        for (int i = 0; i < n; i++) {
298            TypeData td = types[i];
299            if (td != null)
300                td.evalExpectedType(cp);
301        }
302    }
303
304    // Phase 3
305
306    public StackMapTable toStackMap(TypedBlock[] blocks) {
307        StackMapTable.Writer writer = new StackMapTable.Writer(32);
308        int n = blocks.length;
309        TypedBlock prev = blocks[0];
310        int offsetDelta = prev.length;
311        if (prev.incoming > 0) {     // the first instruction is a branch target.
312            writer.sameFrame(0);
313            offsetDelta--;
314        }
315
316        for (int i = 1; i < n; i++) {
317            TypedBlock bb = blocks[i];
318            if (isTarget(bb, blocks[i - 1])) {
319                bb.resetNumLocals();
320                int diffL = stackMapDiff(prev.numLocals, prev.localsTypes,
321                                         bb.numLocals, bb.localsTypes);
322                toStackMapBody(writer, bb, diffL, offsetDelta, prev);
323                offsetDelta = bb.length - 1;
324                prev = bb;
325            }
326            else
327                offsetDelta += bb.length;
328        }
329
330        return writer.toStackMapTable(cpool);
331    }
332
333    /**
334     * Returns true if cur is a branch target.
335     */
336    private boolean isTarget(TypedBlock cur, TypedBlock prev) {
337        int in = cur.incoming;
338        if (in > 1)
339            return true;
340        else if (in < 1)
341            return false;
342
343        return prev.stop;
344    }
345
346    private void toStackMapBody(StackMapTable.Writer writer, TypedBlock bb,
347                                int diffL, int offsetDelta, TypedBlock prev) {
348        // if diffL is -100, two TypeData arrays do not share
349        // any elements.
350
351        int stackTop = bb.stackTop;
352        if (stackTop == 0) {
353            if (diffL == 0) {
354                writer.sameFrame(offsetDelta);
355                return;
356            }
357            else if (0 > diffL && diffL >= -3) {
358                writer.chopFrame(offsetDelta, -diffL);
359                return;
360            }
361            else if (0 < diffL && diffL <= 3) {
362                int[] data = new int[diffL];
363                int[] tags = fillStackMap(bb.numLocals - prev.numLocals,
364                                          prev.numLocals, data,
365                                          bb.localsTypes);
366                writer.appendFrame(offsetDelta, tags, data);
367                return;
368            }
369        }
370        else if (stackTop == 1 && diffL == 0) {
371            TypeData td = bb.stackTypes[0];
372            if (td == TOP)
373                writer.sameLocals(offsetDelta, StackMapTable.TOP, 0);
374            else
375                writer.sameLocals(offsetDelta, td.getTypeTag(),
376                                  td.getTypeData(cpool));
377            return;
378        }
379        else if (stackTop == 2 && diffL == 0) {
380            TypeData td = bb.stackTypes[0];
381            if (td != TOP && td.is2WordType()) {
382                // bb.stackTypes[1] must be TOP.
383                writer.sameLocals(offsetDelta, td.getTypeTag(),
384                                  td.getTypeData(cpool));
385                return;
386            }
387        }
388
389        int[] sdata = new int[stackTop];
390        int[] stags = fillStackMap(stackTop, 0, sdata, bb.stackTypes);
391        int[] ldata = new int[bb.numLocals];
392        int[] ltags = fillStackMap(bb.numLocals, 0, ldata, bb.localsTypes);
393        writer.fullFrame(offsetDelta, ltags, ldata, stags, sdata);
394    }
395
396    private int[] fillStackMap(int num, int offset, int[] data, TypeData[] types) {
397        int realNum = diffSize(types, offset, offset + num);
398        ConstPool cp = cpool;
399        int[] tags = new int[realNum];
400        int j = 0;
401        for (int i = 0; i < num; i++) {
402            TypeData td = types[offset + i];
403            if (td == TOP) {
404                tags[j] = StackMapTable.TOP;
405                data[j] = 0;
406            }
407            else {
408                tags[j] = td.getTypeTag();
409                data[j] = td.getTypeData(cp);
410                if (td.is2WordType())
411                    i++;
412            }
413
414            j++;
415        }
416
417        return tags;
418    }
419
420    private static int stackMapDiff(int oldTdLen, TypeData[] oldTd,
421                                    int newTdLen, TypeData[] newTd)
422    {
423        int diff = newTdLen - oldTdLen;
424        int len;
425        if (diff > 0)
426            len = oldTdLen;
427        else
428            len = newTdLen;
429
430        if (stackMapEq(oldTd, newTd, len))
431            if (diff > 0)
432                return diffSize(newTd, len, newTdLen);
433            else
434                return -diffSize(oldTd, len, oldTdLen);
435        else
436            return -100;
437    }
438
439    private static boolean stackMapEq(TypeData[] oldTd, TypeData[] newTd, int len) {
440        for (int i = 0; i < len; i++) {
441            TypeData td = oldTd[i];
442            if (td == TOP) {        // the next element to LONG/DOUBLE is TOP.
443                if (newTd[i] != TOP)
444                    return false;
445            }
446            else
447                if (!oldTd[i].equals(newTd[i]))
448                    return false;
449        }
450
451        return true;
452    }
453
454    private static int diffSize(TypeData[] types, int offset, int len) {
455        int num = 0;
456        while (offset < len) {
457            TypeData td = types[offset++];
458            num++;
459            if (td != TOP && td.is2WordType())
460                offset++;
461        }
462
463        return num;
464    }
465
466    // Phase 3 for J2ME
467
468    public StackMap toStackMap2(ConstPool cp, TypedBlock[] blocks) {
469        StackMap.Writer writer = new StackMap.Writer();
470        int n = blocks.length;      // should be > 0
471        boolean[] effective = new boolean[n];
472        TypedBlock prev = blocks[0];
473
474        // Is the first instruction a branch target?
475        effective[0] = prev.incoming > 0;
476
477        int num = effective[0] ? 1 : 0;
478        for (int i = 1; i < n; i++) {
479            TypedBlock bb = blocks[i];
480            if (effective[i] = isTarget(bb, blocks[i - 1])) {
481                bb.resetNumLocals();
482                prev = bb;
483                num++;
484            }
485        }
486
487        if (num == 0)
488            return null;
489
490        writer.write16bit(num);
491        for (int i = 0; i < n; i++)
492            if (effective[i])
493                writeStackFrame(writer, cp, blocks[i].position, blocks[i]);
494
495        return writer.toStackMap(cp);
496    }
497
498    private void writeStackFrame(StackMap.Writer writer, ConstPool cp, int offset, TypedBlock tb) {
499        writer.write16bit(offset);
500        writeVerifyTypeInfo(writer, cp, tb.localsTypes, tb.numLocals);
501        writeVerifyTypeInfo(writer, cp, tb.stackTypes, tb.stackTop);
502    }
503
504    private void writeVerifyTypeInfo(StackMap.Writer writer, ConstPool cp, TypeData[] types, int num) {
505        int numDWord = 0;
506        for (int i = 0; i < num; i++) {
507            TypeData td = types[i];
508            if (td != null && td.is2WordType()) {
509                numDWord++;
510                i++;
511            }
512        }
513
514        writer.write16bit(num - numDWord);
515        for (int i = 0; i < num; i++) {
516            TypeData td = types[i];
517            if (td == TOP)
518                writer.writeVerifyTypeInfo(StackMap.TOP, 0);
519            else {
520                writer.writeVerifyTypeInfo(td.getTypeTag(), td.getTypeData(cp));
521                if (td.is2WordType())
522                    i++;
523            }
524        }
525    }
526}
527