OSDN Git Service

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