OSDN Git Service

76fec2b6adc86f916c543166bfd7b718fd3c4711
[stigmata/stigmata-plugins.git] / opcodes / src / main / java / jp / sourceforge / stigmata / birthmarks / ControlFlowGraph.java
1 package jp.sourceforge.stigmata.birthmarks;\r
2 \r
3 import java.util.ArrayList;\r
4 import java.util.HashSet;\r
5 import java.util.Iterator;\r
6 import java.util.List;\r
7 import java.util.Set;\r
8 \r
9 import org.objectweb.asm.Label;\r
10 import org.objectweb.asm.Opcodes;\r
11 import org.objectweb.asm.tree.AbstractInsnNode;\r
12 import org.objectweb.asm.tree.JumpInsnNode;\r
13 import org.objectweb.asm.tree.LabelNode;\r
14 import org.objectweb.asm.tree.LookupSwitchInsnNode;\r
15 import org.objectweb.asm.tree.MethodNode;\r
16 import org.objectweb.asm.tree.TableSwitchInsnNode;\r
17 import org.objectweb.asm.tree.TryCatchBlockNode;\r
18 \r
19 public class ControlFlowGraph {\r
20     private String name;\r
21     private boolean includeException;\r
22     private MethodNode method;\r
23     private BasicBlock[] blocks;\r
24 \r
25     public ControlFlowGraph(String name, MethodNode node){\r
26         this(name, node, false);\r
27     }\r
28 \r
29     public ControlFlowGraph(String name, MethodNode node, boolean includeException){\r
30         this.includeException = includeException;\r
31         this.name = name;\r
32         this.method = node;\r
33         parse(method);\r
34     }\r
35 \r
36     public int[][] getGraphMatrix(){\r
37         int[][] matrix = new int[blocks.length][blocks.length];\r
38 \r
39         for(int i = 0; i < blocks.length; i++){\r
40             for(int j = 0; j < blocks.length; j++){\r
41                 int nextValue = 0;\r
42                 for(Iterator<BasicBlock> iter = blocks[i].nextIterator(); iter.hasNext(); ){\r
43                     BasicBlock nextBlock = iter.next();\r
44                     if(nextBlock == blocks[j]){\r
45                         nextValue = 1;\r
46                         break;\r
47                     }\r
48                 }\r
49                 matrix[i][j] = nextValue;\r
50             }\r
51         }\r
52 \r
53         return matrix;\r
54     }\r
55 \r
56     public String getName(){\r
57         return name;\r
58     }\r
59 \r
60     public int getBasicBlockSize(){\r
61         return blocks.length;\r
62     }\r
63 \r
64     public boolean isIncludingExceptionFlow(){\r
65         return includeException;\r
66     }\r
67 \r
68     public void setIncludingExceptionFlow(boolean includeException){\r
69         boolean oldvalue = this.includeException;\r
70         this.includeException = includeException;\r
71         if(oldvalue != includeException){\r
72             parse(method);\r
73         }\r
74     }\r
75 \r
76     private Set<LabelNode> collectLabels(MethodNode node){\r
77         Set<LabelNode> jumpTarget = new HashSet<LabelNode>();\r
78         int size = node.instructions.size();\r
79         for(int i = 0; i < size; i++){\r
80             AbstractInsnNode inst = node.instructions.get(i);\r
81             switch(inst.getType()){\r
82             case AbstractInsnNode.JUMP_INSN:\r
83             {\r
84                 JumpInsnNode jump = (JumpInsnNode)inst;\r
85                 jumpTarget.add(jump.label);\r
86                 break;\r
87             }\r
88             case AbstractInsnNode.LOOKUPSWITCH_INSN:\r
89             {\r
90                 LookupSwitchInsnNode lookup = (LookupSwitchInsnNode)inst;\r
91                 jumpTarget.add(lookup.dflt);\r
92                 for(Object label: lookup.labels){\r
93                     jumpTarget.add((LabelNode)label);\r
94                 }\r
95                 break;\r
96             }\r
97             case AbstractInsnNode.TABLESWITCH_INSN:\r
98             {\r
99                 TableSwitchInsnNode lookup = (TableSwitchInsnNode)inst;\r
100                 jumpTarget.add(lookup.dflt);\r
101                 for(Object label: lookup.labels){\r
102                     jumpTarget.add((LabelNode)label);\r
103                 }\r
104                 break;\r
105             }\r
106             }\r
107         }\r
108         if(isIncludingExceptionFlow()){\r
109             for(Object object: node.tryCatchBlocks){\r
110                 jumpTarget.add(((TryCatchBlockNode)object).handler);\r
111             }\r
112         }\r
113         return jumpTarget;\r
114     }\r
115 \r
116     /**\r
117      * TryCatchブロックの一覧を返します.\r
118      * Try Catchブロックが含まれていない場合や,\r
119      * {@link isIncludingExceptionFlow}がfalseを返す場合は長さ0の配列を返します.\r
120      * @param node\r
121      * @return\r
122      */\r
123     private TryCatchBlockNode[] buildTryCatchBlockNode(MethodNode node){\r
124         TryCatchBlockNode[] nodes = new TryCatchBlockNode[0];\r
125         if(isIncludingExceptionFlow()){\r
126             nodes = new TryCatchBlockNode[node.tryCatchBlocks.size()];\r
127             for(int i = 0; i < nodes.length; i++){\r
128                 nodes[i] = (TryCatchBlockNode)node.tryCatchBlocks.get(i);\r
129             }\r
130         }\r
131         return nodes;\r
132     }\r
133 \r
134     private void buildExceptionFlow(AbstractInsnNode inst, Set<Label> exceptionFlows, TryCatchBlockNode[] tryCatches){\r
135         if(inst.getType() == AbstractInsnNode.LABEL){\r
136             Label label = ((LabelNode)inst).getLabel();\r
137 \r
138             for(TryCatchBlockNode node: tryCatches){\r
139                 if(node.start.getLabel() == label){\r
140                     exceptionFlows.add(node.handler.getLabel());\r
141                 }\r
142                 else if(node.end.getLabel() == label){\r
143                     exceptionFlows.remove(node.handler.getLabel());\r
144                 }\r
145             }\r
146         }\r
147     }\r
148 \r
149     private BasicBlock[] separateBasicBlock(MethodNode node, Set<LabelNode> jumpTarget){\r
150         int size = node.instructions.size();\r
151 \r
152         List<BasicBlock> blockList = new ArrayList<BasicBlock>();\r
153         Set<Label> exceptionFlows = new HashSet<Label>();\r
154         TryCatchBlockNode[] tryCatchBlocks = buildTryCatchBlockNode(node);\r
155 \r
156         BasicBlock block = new BasicBlock();\r
157         for(int i = 0; i < size; i++){\r
158             AbstractInsnNode inst = node.instructions.get(i);\r
159             block.exceptionFlows.addAll(exceptionFlows);\r
160 \r
161             if(jumpTarget.contains(inst)){\r
162                 if(!block.isEmpty()){\r
163                     blockList.add(block);\r
164                     block = new BasicBlock();\r
165                     block.exceptionFlows.addAll(exceptionFlows);\r
166                 }\r
167             }\r
168             block.addNode(inst);\r
169             buildExceptionFlow(inst, exceptionFlows, tryCatchBlocks);\r
170             if(inst.getType() == AbstractInsnNode.JUMP_INSN\r
171                     || inst.getType() == AbstractInsnNode.TABLESWITCH_INSN\r
172                     || inst.getType() == AbstractInsnNode.LOOKUPSWITCH_INSN\r
173                     || inst.getOpcode() == Opcodes.RETURN\r
174                     || inst.getOpcode() == Opcodes.ATHROW\r
175                     || inst.getOpcode() == Opcodes.RET){\r
176                 if(!block.isEmpty()){\r
177                     blockList.add(block);\r
178                     BasicBlock block2 = new BasicBlock();\r
179                     if(inst.getOpcode() != Opcodes.GOTO && inst.getOpcode() != Opcodes.JSR){\r
180                         block2.setPrev(block);\r
181                     }\r
182                     block = block2;\r
183                     block.exceptionFlows.addAll(exceptionFlows);\r
184                 }\r
185             }\r
186         }\r
187         if(!block.isEmpty()){\r
188             blockList.add(block);\r
189         }\r
190         return blockList.toArray(new BasicBlock[blockList.size()]);\r
191     }\r
192 \r
193     private BasicBlock[] joinBasicBlocks(BasicBlock[] blocks){\r
194         for(int i = 0; i < blocks.length; i++){\r
195             Label[] labels = blocks[i].getTargets();\r
196             for(int j = 0; j < labels.length; j++){\r
197                 for(int k = 0; k < blocks.length; k++){\r
198                     if(i != k && blocks[k].hasLabel(labels[j])){\r
199                         blocks[i].setNext(blocks[k]);\r
200                         break;\r
201                     }\r
202                 }\r
203             }\r
204             if((i + 1) < blocks.length && blocks[i].isFlowNext()){\r
205                 blocks[i].setNext(blocks[i + 1]);\r
206             }\r
207         }\r
208 \r
209         return blocks;\r
210     }\r
211 \r
212     private void parse(MethodNode node){\r
213         Set<LabelNode> jumpTarget = collectLabels(node);\r
214         BasicBlock[] blocks = separateBasicBlock(node, jumpTarget);\r
215         this.blocks = joinBasicBlocks(blocks);\r
216     }\r
217 }\r