1 package org.kit.furia.fragment.soot;
2
3 import java.util.List;
4 import org.apache.log4j.Logger;
5 import org.kit.furia.exceptions.IRException;
6 import org.kit.furia.fragment.MTDFragmentAST;
7 import org.kit.furia.fragment.OBFragment;
8 import org.kit.furia.fragment.soot.representation.Frimp;
9 import org.kit.furia.fragment.soot.representation.internal.FExprBox;
10 import org.kit.furia.fragment.soot.representation.internal.FPhiExpr;
11 import org.kit.furia.fragment.soot.representation.internal.FSelfReference;
12 import org.kit.furia.misc.IntegerHolder;
13
14 import soot.Body;
15 import soot.Unit;
16 import soot.Value;
17 import soot.shimple.PhiExpr;
18 import soot.toolkits.graph.Block;
19 import soot.toolkits.graph.BlockGraph;
20 import soot.toolkits.graph.DirectedGraph;
21 import soot.toolkits.graph.ExceptionalBlockGraph;
22
23 import soot.ValueBox;
24
25 import java.util.Map;
26 import java.util.HashMap;
27
28 import soot.grimp.Grimp;
29 import soot.grimp.internal.ExprBox;
30 import soot.jimple.ArrayRef;
31 import soot.jimple.InstanceFieldRef;
32 import soot.jimple.StaticFieldRef;
33 import soot.jimple.internal.AbstractDefinitionStmt;
34 import soot.jimple.internal.JimpleLocal;
35
36 import java.util.LinkedList;
37 import java.util.Stack;
38 import java.util.Iterator;
39
40 /*
41 Furia-chan: An Open Source software license violation detector.
42 Copyright (C) 2008 Kyushu Institute of Technology
43
44 This program is free software: you can redistribute it and/or modify
45 it under the terms of the GNU General Public License as published by
46 the Free Software Foundation, either version 3 of the License, or
47 (at your option) any later version.
48
49 This program is distributed in the hope that it will be useful,
50 but WITHOUT ANY WARRANTY; without even the implied warranty of
51 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
52 GNU General Public License for more details.
53
54 You should have received a copy of the GNU General Public License
55 along with this program. If not, see <http://www.gnu.org/licenses/>.
56 */
57
58 /**
59 * FragmentBuilder builds new fragments out of a soot method. At first, it
60 * creates a graph representation of the method, and from there the
61 * fragmentation can be executed
62 * @author Arnoldo Jose Muller Molina
63 */
64 public class FragmentBuilder {
65
66 private static final Logger logger = Logger
67 .getLogger(FragmentBuilder.class);
68
69 private int hugeSlices;
70
71 private int smallSlices;
72
73 private final Map < Value, ValueBox > slices;
74
75 // private final Map < Value, Integer > sliceSizes;
76
77 private final String methodName;
78
79 private int minAllowedSize;
80
81 private int maxAllowedSize;
82
83 public FragmentBuilder(final Body body, final BlockGraph graph,
84 int maxAllowedSize, int minAllowedSize) {
85 hugeSlices = 0;
86 smallSlices = 0;
87 this.minAllowedSize = minAllowedSize;
88 this.maxAllowedSize = maxAllowedSize;
89 // sliceSizes = new HashMap < Value, Integer >();
90 methodName = body.getMethod().getSignature();
91 Map < Value, ValueBox > unexpandedSlices = extractUnexpandedSlices(graph);
92 slices = expandSlices(unexpandedSlices);
93
94 }
95
96 public Map < Value, ValueBox > getSlices() {
97 return slices;
98 }
99
100 /*
101 * public int getSliceSize(Value x) { return sliceSizes.get(x); }
102 */
103
104 /*
105 * Extracts all the slices from all the blocks of the method
106 */
107 private Map < Value, ValueBox > extractUnexpandedSlices(
108 final BlockGraph graph) {
109
110 final Map < Value, ValueBox > res = new HashMap();
111 final Iterator it = graph.getBlocks().iterator();
112 while (it.hasNext()) {
113 final Block block = (Block) it.next();
114 final Iterator blockIt = block.iterator();
115 while (blockIt.hasNext()) {
116 final Unit ins = (Unit) blockIt.next();
117
118 if (ins instanceof AbstractDefinitionStmt) {
119 final AbstractDefinitionStmt a = (AbstractDefinitionStmt) ins;
120 final ValueBox rightvb = new FExprBox(a.getRightOp());
121 Value left = a.getLeftOp();
122
123 // if this assert rings, you have to update expandSliceAux
124 // here: if(j.contains(v) || ! (v instanceof JimpleLocal))
125 assert left instanceof ArrayRef
126 || left instanceof JimpleLocal
127 || left instanceof InstanceFieldRef
128 || left instanceof StaticFieldRef : " left var instance of:"
129 + left.getClass().getName();
130
131 if (res.containsKey(left)) { // if we already have the
132 // variable, create a phi
133 // construct.
134 final ValueBox vb = res.get(left);
135 final Value v = vb.getValue();
136 if (v instanceof FPhiExpr) {
137 ((FPhiExpr) v).add(rightvb);
138 } else {
139 // if there is no phi expression we create one
140 final List < Value > x = new LinkedList < Value >();
141 x.add(v);
142 x.add(rightvb.getValue());
143 FPhiExpr n = new FPhiExpr(x);
144 res.put(left, new FExprBox(n));
145 }
146 } else {
147 res.put(left, rightvb);
148 }
149 }
150 }
151 }
152 return res;
153 }
154
155 public int getTotalSlices() {
156 return this.slices.size();
157 }
158
159 /**
160 * Expands all the fragments in a method.
161 */
162 private Map < Value, ValueBox > expandSlices(
163 final Map < Value, ValueBox > ue) {
164 this.hugeSlices = 0;
165 this.smallSlices = 0;
166 Map < Value, ValueBox > res = new HashMap < Value, ValueBox >();
167 Iterator < Value > it = ue.keySet().iterator();
168 while (it.hasNext()) {
169 Value k = it.next();
170 Stack < Value > j = new Stack < Value >();
171 j.push(k); // put our slice at the top of the stack
172 IntegerHolder i = new IntegerHolder(1);
173 try {
174 // expand one slice
175 Value expanded = expandSliceAux(j, ue, k, i, maxAllowedSize);
176
177 int size = i.getValue();
178 if (size > maxAllowedSize) {
179 throw new HugeFragmentException();
180 } else if (size >= minAllowedSize) {
181 res.put(k, new FExprBox(expanded));
182 // sliceSizes.put(k, Integer.valueOf(size));
183 } else {
184 this.smallSlices++;
185 }
186 } catch (HugeFragmentException e) {
187 if (logger.isDebugEnabled()) {
188 logger.debug("Huge slice of size: " + i.getValue()
189 + " in: " + k + " " + this.methodName);
190 }
191 hugeSlices++;
192 }
193
194 }
195 return res;
196 }
197
198 private Value expandSliceAux(final Stack < Value > j,
199 final Map < Value, ValueBox > ue, final Value originalValue,
200 IntegerHolder i, int max_allowed_size) // NOPMD by amuller on
201 // 11/16/06 4:07 PM
202 throws HugeFragmentException {
203 if (i.getValue() > max_allowed_size) { // if the size is getting tooooo
204 // big
205 throw new HugeFragmentException();
206 }
207 // right hand side is backed up.
208 Value rightToProcess;
209 // no references in list of pairs key => value
210 if (null == ue.get(j.peek())) {
211 rightToProcess = Grimp.cloneIfNecessary(j.peek());
212 } else {
213 // we get the right hand side from our list of pairs key => value
214 rightToProcess = Grimp.cloneIfNecessary(((ValueBox) ue
215 .get(j.peek())).getValue());
216 }
217 // we process what we have at the top of the stack.
218 Iterator it = rightToProcess.getUseBoxes().iterator();
219 while (it.hasNext()) {
220 ValueBox vb = (ValueBox) it.next();
221 Value v = vb.getValue();
222 // if the value that we are evaluating is the "original value", we
223 // replace it
224 if (v.equals(originalValue)) {
225 vb.setValue(new FSelfReference());
226 continue;
227 }
228 // if the value has been expanded, we continue to the next value
229 if (j.contains(v)) {
230 continue;
231 }
232 // or if the value is not a reference we continue to the next value
233 if (!(v instanceof JimpleLocal || v instanceof InstanceFieldRef || v instanceof StaticFieldRef)) {
234 continue;
235 }
236 i.inc();
237 j.push(v);
238
239 vb.setValue(expandSliceAux(j, ue, originalValue, i,
240 max_allowed_size));
241
242 }
243 j.pop();
244 return rightToProcess;
245 }
246
247 public int getHugeSlices() {
248 return hugeSlices;
249 }
250
251 public String getMethodName() {
252 return methodName;
253 }
254
255 /**
256 * Fills a hash map that contains the fragment and number of occurrences.
257 * @param result
258 * @throws Exception
259 */
260 public void fillRepetitionCounts(
261 HashMap < String, IntegerHolder > repetitionCounts)
262 throws IRException {
263 try{
264 // result.append("// Method: " + getMethodName() + "\n");
265 Iterator < Value > keys = slices.keySet().iterator();
266 while (keys.hasNext()) {
267 Value keyValue = keys.next();
268 Value value = slices.get(keyValue).getValue();
269 String fragment = Frimp.toQ(value);
270
271 IntegerHolder counter = repetitionCounts.get(fragment);
272 if (counter == null) {
273 counter = new IntegerHolder(0);
274 repetitionCounts.put(fragment, counter);
275 }
276 counter.inc();
277
278 }
279 }catch(Exception e){
280 throw new IRException(e);
281 }
282 }
283
284 /**
285 * public String generateStringSpecial(boolean debugSlices) throws Exception {
286 * StringBuilder result = new StringBuilder(); // if(debugSlices){
287 * result.append("// Method: " + getMethodName() + "\n"); // } Iterator <
288 * Value > keys = slices.keySet().iterator(); Stack < SliceAST > stack = new
289 * Stack < SliceAST >(); while (keys.hasNext()) { Value keyValue =
290 * keys.next(); Value value = slices.get(keyValue).getValue(); String slice =
291 * Frimp.toQ(value); SliceAST s = SliceFactory.createSliceASTLean(slice);
292 * s.getSize(); result.append(microSliceString(s)); } return
293 * result.toString(); } public static void doMicroSlice(SliceAST s,
294 * LinkedList < SliceAST > result) { if (!isPhi(s)) { result.add(s);
295 * microSliceAux(s, result); } else { splitPhi(s, result); } } protected
296 * static void microSliceAux(SliceAST s, LinkedList < SliceAST > res) {
297 * SliceAST down = (SliceAST) s.getFirstChild(); boolean hadPhi = false; if
298 * (down != null) { if (isPhi(down)) { // 1) remove it
299 * s.setFirstChild(down.getNextSibling()); // 2) create new slices out of
300 * down splitPhi(down, res); hadPhi = true; } else { microSliceAux(down,
301 * res); } } SliceAST right = (SliceAST) s.getNextSibling(); if (right !=
302 * null) { if (isPhi(right)) { // 1) remove it
303 * s.setNextSibling(right.getNextSibling()); // 2) create new slices out of
304 * right splitPhi(right, res); hadPhi = true; } else { microSliceAux(right,
305 * res); } } if (hadPhi) { microSliceAux(s, res); // need to execute again } }
306 * protected static void splitPhi(SliceAST s, LinkedList < SliceAST > res) {
307 * SliceAST t = s.getLeftmostChild(); assert isPhi(s); while (t != null) {
308 * SliceAST a = t; t = (SliceAST) t.getNextSibling();
309 * a.setNextSibling(null); // we have to create a new slice doMicroSlice(a,
310 * res); // creates new slices } } protected static boolean isPhi(SliceAST
311 * s) { return s.getText().equals(FuriaConstructDefinitions.FURIA_fphi); }
312 * public static String microSliceString(SliceAST s) { LinkedList < SliceAST >
313 * result = new LinkedList < SliceAST >(); doMicroSlice(s, result); Iterator <
314 * SliceAST > it = result.iterator(); StringBuilder res = new
315 * StringBuilder(); while (it.hasNext()) { SliceAST t = it.next();
316 * res.append(t.toQ()); res.append("\n"); } String r = res.toString();
317 * assert !r.contains("p"); return r; }
318 */
319
320 public int getSmallSlices() {
321 return smallSlices;
322 }
323
324 }