|
1
30
31 package oracle.toplink.libraries.asm.tree.analysis;
32
33 import java.util.ArrayList  ;
34 import java.util.List ;
35
36 import oracle.toplink.libraries.asm.Constants;
37 import oracle.toplink.libraries.asm.Label;
38 import oracle.toplink.libraries.asm.Type;
39 import oracle.toplink.libraries.asm.tree.AbstractInsnNode;
40 import oracle.toplink.libraries.asm.tree.ClassNode;
41 import oracle.toplink.libraries.asm.tree.IincInsnNode;
42 import oracle.toplink.libraries.asm.tree.JumpInsnNode;
43 import oracle.toplink.libraries.asm.tree.LookupSwitchInsnNode;
44 import oracle.toplink.libraries.asm.tree.MethodNode;
45 import oracle.toplink.libraries.asm.tree.TableSwitchInsnNode;
46 import oracle.toplink.libraries.asm.tree.TryCatchBlockNode;
47 import oracle.toplink.libraries.asm.tree.VarInsnNode;
48
49
54
55 public class Analyzer implements Constants {
56
57 private Interpreter interpreter;
58
59 private int n;
60
61 private IntMap indexes;
62
63 private List [] handlers;
64
65 private Frame[] frames;
66
67 private Subroutine[] subroutines;
68
69 private boolean[] queued;
70
71 private int[] queue;
72
73 private int top;
74
75 private boolean jsr;
76
77
83
84 public Analyzer (final Interpreter interpreter) {
85 this.interpreter = interpreter;
86 }
87
88
100
101 public Frame[] analyze (final ClassNode c, final MethodNode m)
102 throws AnalyzerException
103 {
104 n = m.instructions.size();
105 indexes = new IntMap(2*n);
106 handlers = new List [n];
107 frames = new Frame[n];
108 subroutines = new Subroutine[n];
109 queued = new boolean[n];
110 queue = new int[n];
111 top = 0;
112
113 for (int i = 0; i < n; ++i) {
115 indexes.put(m.instructions.get(i), i);
116 }
117
118 for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
120 TryCatchBlockNode tcb = (TryCatchBlockNode)m.tryCatchBlocks.get(i);
121 int begin = indexes.get(tcb.start);
122 int end = indexes.get(tcb.end);
123 for (int j = begin; j < end; ++j) {
124 List insnHandlers = handlers[j];
125 if (insnHandlers == null) {
126 insnHandlers = new ArrayList ();
127 handlers[j] = insnHandlers;
128 }
129 insnHandlers.add(tcb);
130 }
131 }
132
133 Frame current = newFrame(m.maxLocals, m.maxStack);
135 Frame handler = newFrame(m.maxLocals, m.maxStack);
136 Type[] args = Type.getArgumentTypes(m.desc);
137 int local = 0;
138 if ((m.access & ACC_STATIC) == 0) {
139 Type ctype = Type.getType("L" + c.name + ";");
140 current.setLocal(local++, interpreter.newValue(ctype));
141 }
142 for (int i = 0; i < args.length; ++i) {
143 current.setLocal(local++, interpreter.newValue(args[i]));
144 if (args[i].getSize() == 2) {
145 current.setLocal(local++, interpreter.newValue(null));
146 }
147 }
148 while (local < m.maxLocals) {
149 current.setLocal(local++, interpreter.newValue(null));
150 }
151 merge(0, current, null);
152
153 while (top > 0) {
155 int insn = queue[--top];
156 Frame f = frames[insn];
157 Subroutine subroutine = subroutines[insn];
158 queued[insn] = false;
159
160 try {
161 Object o = m.instructions.get(insn);
162 jsr = false;
163
164 if (o instanceof Label) {
165 merge(insn + 1, f, subroutine);
166 } else {
167 AbstractInsnNode insnNode = (AbstractInsnNode)o;
168 int insnOpcode = insnNode.getOpcode();
169
170 current.init(f).execute(insnNode, interpreter);
171 subroutine = subroutine == null ? null : subroutine.copy();
172
173 if (insnNode instanceof JumpInsnNode) {
174 JumpInsnNode j = (JumpInsnNode)insnNode;
175 if (insnOpcode != GOTO && insnOpcode != JSR) {
176 merge(insn + 1, current, subroutine);
177 }
178 if (insnOpcode == JSR) {
179 jsr = true;
180 merge(indexes.get(j.label), current, new Subroutine(j.label, m.maxLocals, j));
181 } else {
182 merge(indexes.get(j.label), current, subroutine);
183 }
184 } else if (insnNode instanceof LookupSwitchInsnNode) {
185 LookupSwitchInsnNode lsi = (LookupSwitchInsnNode)insnNode;
186 merge(indexes.get(lsi.dflt), current, subroutine);
187 for (int j = 0; j < lsi.labels.size(); ++j) {
188 Label label = (Label)lsi.labels.get(j);
189 merge(indexes.get(label), current, subroutine);
190 }
191 } else if (insnNode instanceof TableSwitchInsnNode) {
192 TableSwitchInsnNode tsi = (TableSwitchInsnNode)insnNode;
193 merge(indexes.get(tsi.dflt), current, subroutine);
194 for (int j = 0; j < tsi.labels.size(); ++j) {
195 Label label = (Label)tsi.labels.get(j);
196 merge(indexes.get(label), current, subroutine);
197 }
198 } else if (insnOpcode == RET) {
199 if (subroutine == null) {
200 throw new AnalyzerException(
201 "RET instruction outside of a sub routine");
202 } else {
203 for (int i = 0; i < subroutine.callers.size(); ++i) {
204 int caller = indexes.get(subroutine.callers.get(i));
205 merge(caller + 1, frames[caller], current, subroutines[caller], subroutine.access);
206 }
207 }
208 } else if (insnOpcode != ATHROW && (insnOpcode < IRETURN || insnOpcode > RETURN)) {
209 if (subroutine != null) {
210 if (insnNode instanceof VarInsnNode) {
211 int var = ((VarInsnNode)insnNode).var;
212 subroutine.access[var] = true;
213 if (insnOpcode == LLOAD ||
214 insnOpcode == DLOAD ||
215 insnOpcode == LSTORE ||
216 insnOpcode == DSTORE)
217 {
218 subroutine.access[var + 1] = true;
219 }
220 } else if (insnNode instanceof IincInsnNode) {
221 int var = ((IincInsnNode)insnNode).var;
222 subroutine.access[var] = true;
223 }
224 }
225 merge(insn + 1, current, subroutine);
226 }
227 }
228
229 List insnHandlers = handlers[insn];
230 if (insnHandlers != null) {
231 for (int i = 0; i < insnHandlers.size(); ++i) {
232 TryCatchBlockNode tcb = (TryCatchBlockNode)insnHandlers.get(i);
233 Type type;
234 if (tcb.type == null) {
235 type = Type.getType("Ljava/lang/Throwable;");
236 } else {
237 type = Type.getType("L" + tcb.type + ";");
238 }
239 handler.init(f);
240 handler.clearStack();
241 handler.push(interpreter.newValue(type));
242 merge(indexes.get(tcb.handler), handler, subroutine);
243 }
244 }
245 } catch (Exception e) {
246 throw new AnalyzerException(
247 "Error at instruction " + insn + ": " + e.getMessage());
248 }
249 }
250
251 return frames;
252 }
253
254
264
265 public Frame[] getFrames () {
266 return frames;
267 }
268
269
277
278 public int getIndex (final Object insn) {
279 return indexes.get(insn);
280 }
281
282
289
290 public List getHandlers (final int insn) {
291 return handlers[insn];
292 }
293
294
301
302 protected Frame newFrame (final int nLocals, final int nStack) {
303 return new Frame(nLocals, nStack);
304 }
305
306
312
313 protected Frame newFrame (final Frame src) {
314 return new Frame(src);
315 }
316
317
326
327 protected void newControlFlowEdge (final Frame frame, final Frame successor) {
328 }
329
330
332 private void merge (
333 final int insn,
334 final Frame frame,
335 final Subroutine subroutine) throws AnalyzerException
336 {
337 if (insn > n - 1) {
338 throw new AnalyzerException("Execution can fall off end of the code");
339 } else {
340 Frame oldFrame = frames[insn];
341 Subroutine oldSubroutine = subroutines[insn];
342 boolean changes = false;
343
344 if (oldFrame == null) {
345 frames[insn] = newFrame(frame);
346 changes = true;
347 } else {
348 changes |= oldFrame.merge(frame, interpreter);
349 }
350
351 newControlFlowEdge(frame, oldFrame);
352
353 if (oldSubroutine == null) {
354 if (subroutine != null) {
355 subroutines[insn] = subroutine.copy();
356 changes = true;
357 }
358 } else {
359 if (subroutine != null) {
360 changes |= oldSubroutine.merge(subroutine, !jsr);
361 }
362 }
363 if (changes && !queued[insn]) {
364 queued[insn] = true;
365 queue[top++] = insn;
366 }
367 }
368 }
369
370 private void merge (
371 final int insn,
372 final Frame beforeJSR,
373 final Frame afterRET,
374 final Subroutine subroutineBeforeJSR,
375 final boolean[] access) throws AnalyzerException
376 {
377 if (insn > n - 1) {
378 throw new AnalyzerException("Execution can fall off end of the code");
379 } else {
380 Frame oldFrame = frames[insn];
381 Subroutine oldSubroutine = subroutines[insn];
382 boolean changes = false;
383
384 afterRET.merge(beforeJSR, access);
385
386 if (oldFrame == null) {
387 frames[insn] = newFrame(afterRET);
388 changes = true;
389 } else {
390 changes |= oldFrame.merge(afterRET, access);
391 }
392
393 newControlFlowEdge(afterRET, oldFrame);
394
395 if (oldSubroutine == null) {
396 if (subroutineBeforeJSR != null) {
397 subroutines[insn] = subroutineBeforeJSR.copy();
398 changes = true;
399 }
400 } else {
401 if (subroutineBeforeJSR != null) {
402 changes |= oldSubroutine.merge(subroutineBeforeJSR, !jsr);
403 }
404 }
405 if (changes && !queued[insn]) {
406 queued[insn] = true;
407 queue[top++] = insn;
408 }
409 }
410 }
411
412 private static class IntMap {
413
414 private int size;
415
416 private Object [] keys;
417
418 private int[] values;
419
420 private IntMap (final int size) {
421 this.size = size;
422 this.keys = new Object [size];
423 this.values = new int[size];
424 }
425
426 public int get (final Object key) {
427 int n = size;
428 int i = (key.hashCode() & 0x7FFFFFFF)%n;
429 while (keys[i] != key) {
430 i = (i+1)%n;
431 }
432 return values[i];
433 }
434
435 public void put (final Object key, final int value) {
436 int n = size;
437 int i = (key.hashCode() & 0x7FFFFFFF)%n;
438 while (keys[i] != null) {
439 i = (i+1)%n;
440 }
441 keys[i] = key;
442 values[i] = value;
443 }
444 }
445
446 private static class Subroutine {
447
448 Label start;
449
450 boolean[] access;
451
452 List callers;
453
454 private Subroutine () {
455 }
456
457 public Subroutine (final Label start, final int maxLocals, final JumpInsnNode caller) {
458 this.start = start;
459 this.access = new boolean[maxLocals];
460 this.callers = new ArrayList ();
461 callers.add(caller);
462 }
463
464 public Subroutine copy () {
465 Subroutine result = new Subroutine();
466 result.start = start;
467 result.access = new boolean[access.length];
468 System.arraycopy(access, 0, result.access, 0, access.length);
469 result.callers = new ArrayList (callers);
470 return result;
471 }
472
473 public boolean merge (final Subroutine subroutine, boolean checkOverlap) throws AnalyzerException {
474 if (checkOverlap && subroutine.start != start) {
475 throw new AnalyzerException("Overlapping sub routines");
476 }
477 boolean changes = false;
478 for (int i = 0; i < access.length; ++i) {
479 if (subroutine.access[i] && !access[i]) {
480 access[i] = true;
481 changes = true;
482 }
483 }
484 for (int i = 0; i < subroutine.callers.size(); ++i) {
485 Object caller = subroutine.callers.get(i);
486 if (!callers.contains(caller)) {
487 callers.add(caller);
488 changes = true;
489 }
490 }
491 return changes;
492 }
493 }
494 }
495 |
Popular Tags |
Java API By Example, From Geeks To Geeks.