OSDN Git Service

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