OSDN Git Service

コントロールフローを抽出可能にした.
[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.tree.AbstractInsnNode;\r
11 import org.objectweb.asm.tree.JumpInsnNode;\r
12 import org.objectweb.asm.tree.LabelNode;\r
13 import org.objectweb.asm.tree.LookupSwitchInsnNode;\r
14 import org.objectweb.asm.tree.MethodNode;\r
15 import org.objectweb.asm.tree.TableSwitchInsnNode;\r
16 import org.objectweb.asm.tree.TryCatchBlockNode;\r
17 \r
18 import com.sun.xml.internal.ws.org.objectweb.asm.Opcodes;\r
19 \r
20 public class ControlFlowGraph {\r
21     private String name;\r
22     private boolean includeException;\r
23     private MethodNode method;\r
24     private BasicBlock[] blocks;\r
25 \r
26     public ControlFlowGraph(String name, MethodNode node){\r
27         this(name, node, false);\r
28     }\r
29 \r
30     public ControlFlowGraph(String name, MethodNode node, boolean includeException){\r
31         this.includeException = includeException;\r
32         this.name = name;\r
33         this.method = node;\r
34         parse(method);\r
35     }\r
36 \r
37     public int[][] getGraphMatrix(){\r
38         int[][] matrix = new int[blocks.length][blocks.length];\r
39 \r
40         for(int i = 0; i < blocks.length; i++){\r
41             for(int j = 0; j < blocks.length; j++){\r
42                 int nextValue = 0;\r
43                 for(Iterator<BasicBlock> iter = blocks[i].nextIterator(); iter.hasNext(); ){\r
44                     BasicBlock nextBlock = iter.next();\r
45                     if(nextBlock == blocks[j]){\r
46                         nextValue = 1;\r
47                         break;\r
48                     }\r
49                 }\r
50                 matrix[i][j] = nextValue;\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> jumpedTarget = 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                 jumpedTarget.add(jump.label);\r
86                 break;\r
87             }\r
88             case AbstractInsnNode.LOOKUPSWITCH_INSN:\r
89             {\r
90                 LookupSwitchInsnNode lookup = (LookupSwitchInsnNode)inst;\r
91                 jumpedTarget.add(lookup.dflt);\r
92                 for(Object label: lookup.labels){\r
93                     jumpedTarget.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                 jumpedTarget.add(lookup.dflt);\r
101                 for(Object label: lookup.labels){\r
102                     jumpedTarget.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                 jumpedTarget.add(((TryCatchBlockNode)object).handler);\r
111             }\r
112         }\r
113         return jumpedTarget;\r
114     }\r
115 \r
116     private BasicBlock[] separateBasicBlock(MethodNode node, Set<LabelNode> jumpedTarget){\r
117         int size = node.instructions.size();\r
118 \r
119         List<BasicBlock> blockList = new ArrayList<BasicBlock>();\r
120         BasicBlock block = new BasicBlock();\r
121         for(int i = 0; i < size; i++){\r
122             AbstractInsnNode inst = node.instructions.get(i);\r
123 \r
124             if(jumpedTarget.contains(inst)){\r
125                 if(!block.isEmpty()){\r
126                     blockList.add(block);\r
127                     block = new BasicBlock();\r
128                 }\r
129             }\r
130             block.addNode(inst);\r
131             if(inst.getType() == AbstractInsnNode.JUMP_INSN\r
132                     || inst.getType() == AbstractInsnNode.TABLESWITCH_INSN\r
133                     || inst.getType() == AbstractInsnNode.LOOKUPSWITCH_INSN){\r
134                 if(!block.isEmpty()){\r
135                     blockList.add(block);\r
136                     BasicBlock block2 = new BasicBlock();\r
137                     if(inst.getOpcode() != Opcodes.GOTO && inst.getOpcode() != Opcodes.JSR){\r
138                         block2.setPrev(block);\r
139                     }\r
140                     block = block2;\r
141                 }\r
142             }\r
143         }\r
144         blockList.add(block);\r
145         return blockList.toArray(new BasicBlock[blockList.size()]);\r
146     }\r
147 \r
148     private BasicBlock[] joinBasicBlocks(BasicBlock[] blocks){\r
149         for(int i = 0; i < blocks.length; i++){\r
150             Label[] labels = blocks[i].getTargets();\r
151             for(int j = 0; j < labels.length; j++){\r
152                 for(int k = 0; k < blocks.length; k++){\r
153                     if(i != k && blocks[k].hasLabel(labels[j])){\r
154                         blocks[i].setNext(blocks[k]);\r
155                         break;\r
156                     }\r
157                 }\r
158             }\r
159             if(labels.length == 0 && (i + 1) < blocks.length){\r
160                 blocks[i].setNext(blocks[i + 1]);\r
161             }\r
162         }\r
163 \r
164         return blocks;\r
165     }\r
166 \r
167     private void parse(MethodNode node){\r
168         Set<LabelNode> jumpedTarget = collectLabels(node);\r
169         BasicBlock[] blocks = separateBasicBlock(node, jumpedTarget);\r
170         this.blocks = joinBasicBlocks(blocks);\r
171     }\r
172 }\r