DefinitionFreePath


1   /*
2    * Created on 18.11.2004
3    * 
4    * written by Matthias Kempka
5    */
6   package de.uka.ipd.coverage.natures.all_uses;
7   
8   import java.util.ArrayList  ;
9   import java.util.Iterator  ;
10  import java.util.List  ;
11  
12  import org.apache.bcel.classfile.LocalVariable;
13  import org.apache.bcel.classfile.Method;
14  import org.apache.bcel.generic.InstructionHandle;
15  import org.apache.bcel.generic.LoadInstruction;
16  import org.apache.bcel.generic.StoreInstruction;
17  
18  import de.uka.ipd.coverage.recording.*;
19  
20  /**
21   * Created on 18.11.2004
22   * @author Matthias Kempka
23   */
24  public class DefinitionFreePath extends Path {
25  
26      private int index;
27      private boolean finished = false;
28      /**
29       * @param index the index this definitionfree path records.
30       */
31      public DefinitionFreePath(Integer   index) {
32          this.index = index.intValue();
33      }
34  
35      /**
36       * removes blocks at the end of the path where the given index
37       * is not read.
38       * @param index
39       */
40      public void removeUnnecessaryBlocks(Integer   index) {
41          while(enteredBlocks.size() > 1 &&
42                  !(containsLoad(getLastSSABasicBlockWrapper(),
43                      index,
44                      enteredBlocks.size() == 1))) {
45              enteredBlocks.removeLast();
46          }
47      }
48      
49      private SsaBasicBlockWrapper getLastSSABasicBlockWrapper() {
50          return (SsaBasicBlockWrapper)
51                  ((RuntimeBasicBlockWrapper) enteredBlocks.getLast()).getWrappedBasicBlock();
52      }
53  
54      public void addBlock(SsaBasicBlockWrapper block) {
55          if (finished) throw new AssertionError  ("Entry in finished DefinitionFreePath"); //$NON-NLS-1$
56          addEnteredBlock(block);
57          addExitedBlock(block);
58      }
59      
60      private boolean containsLoad(SsaBasicBlockWrapper wrapper, Integer   originalIndex,
61              boolean isFirstBlock) {
62          assert wrapper != null :"wrapper must not be null"; //$NON-NLS-1$
63          assert originalIndex != null : "index must not be null"; //$NON-NLS-1$
64          
65          int index = wrapper.getSSAIndex(originalIndex.intValue());
66          InstructionHandle[] ih = wrapper.getInstructionHandles();
67          for (int i = 0; i < ih.length; i++) {
68              if (ih[i].getInstruction() instanceof LoadInstruction) {
69                  LoadInstruction load = (LoadInstruction) ih[i].getInstruction();
70                  if (index == load.getIndex()) {
71                      return true;
72                  }
73                  // SSA index may be overwritten by a store later in the block,
74                  // thus compare also with the index history.
75                  if (isInIndexHistory(wrapper, originalIndex, load.getIndex())) {
76                      return true;
77                  }
78              } else if (ih[i].getInstruction() instanceof StoreInstruction) {
79                  // load instructions after a store for the given index
80                  // are not of interest for this definition free path
81                  // unless this is the first block (the one, where the index
82                  // is defined).
83                  StoreInstruction store = (StoreInstruction) ih[i].getInstruction();
84                  if (!isFirstBlock && index == store.getIndex()) {
85                      return false;
86                  }
87                  // SSA index may be overwritten by a store later in the block,
88                  // thus compare also with the index history.
89                  if (isInIndexHistory(wrapper, originalIndex, store.getIndex())) {
90                      return false;
91                  }
92              }
93          }
94          return false;
95      }
96      
97      /**
98       * checks whether the <code>indexInQuestion</code> is in the
99       * <code>indexHistory</code> for the <code>originalIndex</code> in the 
100      * given <code>wrapper</code> 
101      */
102     private boolean isInIndexHistory(SsaBasicBlockWrapper wrapper, 
103             Integer   originalIndex, int indexInQuestion) {
104         Integer  [] historyIndices = wrapper.getIndexHistory(originalIndex);
105         for (int j = 0; j < historyIndices.length; j++) {
106             if (historyIndices[j].intValue() == indexInQuestion) {
107                 return true;
108             }
109         }
110         return false;
111     }
112     
113     public Definition getDefinition() {
114         InstructionHandle definitiningInstruction = getDefinitiningInstruction();
115         int sourceLine = getSafeSourcePosition(definitiningInstruction);
116         int bytecodePos = definitiningInstruction.getPosition();
117         Definition result = new Definition( 
118             sourceLine, 
119             bytecodePos, 
120             getDefinitionVariableName(), 
121             getRegisteredMethod());
122         return result;
123     }
124     
125     /**
126      * @throws AssertionError
127      */
128     private InstructionHandle getDefinitiningInstruction() {
129         SsaBasicBlockWrapper block = (SsaBasicBlockWrapper) 
130                 ((RuntimeBasicBlockWrapper) enteredBlocks.getFirst()).
131                         getWrappedBasicBlock();
132         int sSAIndex = block.getSSAIndex(index);
133         InstructionHandle[] handles = block.getInstructionHandles();
134         for (int i = 0; i < handles.length; i++) {
135             if (handles[i].getInstruction() instanceof StoreInstruction) {
136                 StoreInstruction si = (StoreInstruction) handles[i].getInstruction();
137                 if (si.getIndex() == sSAIndex) {
138                     return handles[i];
139                 }
140             }
141         }
142         throw new AssertionError  ("DefinitionFreePath without definition!"); //$NON-NLS-1$
143     }
144 
145     private String   getDefinitionVariableName() {
146         LocalVariable var = getRegisteredMethod().getMethod().getLocalVariableTable().getLocalVariable(index);
147         if (var == null) {
148             return Messages.getString("DefinitionFreePath.4"); //$NON-NLS-1$
149         }
150         return var.getName();
151     }
152     
153     /*
154      * This method is a somewhat weird construction that was necessary
155      * due to the impossibility in BCEL to set the source line number on
156      * handmade instruction handles. So, if we come across an instruction 
157      * of type PseudoStore (woven in by SSABasicBlockWrapper) 
158      * we take the line number it carries.
159      */
160     private int getSafeSourcePosition(InstructionHandle handle) {
161         Method method = getRegisteredMethod().getMethod();
162         if (handle.getInstruction() instanceof PseudoStore) {
163             return ((PseudoStore) handle.getInstruction()).getSourceLine();
164         }
165         int sourceLine = method.getLineNumberTable().getSourceLine(handle.getPosition());
166         return sourceLine;
167     }
168 
169     public UsesCoverage getCoveredUsesSourcePositions() {
170         Path path = findBestMatchingPath();
171         UsesCoverage result = new UsesCoverage(this);
172         IBasicBlock[] testedBlocks = path.getEnteredBlocksWithoutReiteratedLoops();
173         int[] firstIndices = findFirstBlock(testedBlocks); // beginning must be 
174                                     // non-negative because path has at 
175                                     // least one element.
176         
177         // first, add the uses of blocks that can be compared 
178         Iterator   iter = enteredBlocks.iterator();
179         for (int i = 0; i < firstIndices.length; i++) {
180             int lastIndex = findLastBlockOfCommonSubpath(testedBlocks, firstIndices[i]);
181             boolean state_covered = true;
182             for (int j = firstIndices[i]; (j < lastIndex) && iter.hasNext(); j++) {
183                 RuntimeBasicBlockWrapper wrapper = (RuntimeBasicBlockWrapper) iter.next();
184                 SsaBasicBlockWrapper dfpBlock = (SsaBasicBlockWrapper) wrapper.getWrappedBasicBlock();
185                 if (CoverageState.FULL_COVERAGE == testedBlocks[j].covers(dfpBlock)) {
186                     assert state_covered : "full coverage in state NOT COVERED"; //$NON-NLS-1$
187                     result.addCoveredUsesByteCodePositions(
188                         findUses(dfpBlock));
189                 } else {
190                     break;  // the rest of the dfp does not need to be compared,
191                             // it is uncovered here.
192                 }
193             }
194         }
195         
196         // second, add uses of blocks that are left in the definitionfree path
197         // but weren't covered.
198         while (iter.hasNext()) {
199             RuntimeBasicBlockWrapper wrapper = (RuntimeBasicBlockWrapper) iter.next();
200             SsaBasicBlockWrapper dfpBlock = (SsaBasicBlockWrapper) wrapper.getWrappedBasicBlock();
201             result.addUncoveredUsesByteCodePositions(findUses(dfpBlock));
202         }
203         return result;
204     }
205     
206     /**
207      * @param start the beginning of the definition free path in testedBlocks.
208      * it can be found via findFirstBlock(IBasicBlock[]).
209      * @return returns an index for <code>testedBlocks</code>. This index 
210      * indicates the last block (including) where this definition free path 
211      * has a common subpath with testedBlocks. 
212      */
213     private int findLastBlockOfCommonSubpath(IBasicBlock[] testedBlocks, int start) {
214         assert start < testedBlocks.length;
215         Iterator   iter = enteredBlocks.iterator();
216         for (int i = start; (i < testedBlocks.length) 
217                 && iter.hasNext(); i++) {
218             RuntimeBasicBlockWrapper wrapper = (RuntimeBasicBlockWrapper) iter.next();
219             SsaBasicBlockWrapper dfpBlock = (SsaBasicBlockWrapper) wrapper.getWrappedBasicBlock();
220             if (CoverageState.FULL_COVERAGE != testedBlocks[i].covers(dfpBlock)) {
221                 return i;
222             } else {
223                 assert i > start : "the given startblock is does not cover the first block of the definitionfree path."; //$NON-NLS-1$
224             }
225         }
226         return testedBlocks.length;
227     }
228 
229     /**
230      * @param dfpBlock
231      * @return returns a List of uses in the given Block.
232      */
233     private Integer  [] findUses(SsaBasicBlockWrapper dfpBlock) {
234         List   result = new ArrayList  ();
235         int ssaIndex = dfpBlock.getSSAIndex(index);
236         InstructionHandle ihs[] = dfpBlock.getInstructionHandles();
237         for (int i = 0; i < ihs.length; i++) {
238             if (ihs[i].getInstruction() instanceof LoadInstruction) {
239                 LoadInstruction load = (LoadInstruction) ihs[i].getInstruction();
240                 if (load.getIndex() == ssaIndex) {
241                     result.add(new Integer  (ihs[i].getPosition()));
242                 } else {
243                     Integer  [] history = dfpBlock.getIndexHistory(new Integer  (index));
244                     for (int j = 0; j < history.length; j++) {
245                         if (load.getIndex() == history[j].intValue()) {
246                             result.add(new Integer  (ihs[i].getPosition()));
247                         }
248                     }
249                 }
250             }
251         }
252         return (Integer  []) result.toArray(new Integer  [result.size()]);
253     }
254 
255     /**
256      * @return returns the indices of the block which are equal to the first
257      * block of the definition free path.
258      */
259     private int[] findFirstBlock(IBasicBlock[] blocks) {
260         List   beginnings = new ArrayList  ();
261         RuntimeBasicBlockWrapper dfpFirstElement = 
262             (RuntimeBasicBlockWrapper) enteredBlocks.getFirst();
263         for (int j = 0; j < blocks.length; j++) {
264             RuntimeBasicBlockWrapper element = (RuntimeBasicBlockWrapper) blocks[j];
265             CoverageState firstPathElementCoverage 
266                     = element.covers(dfpFirstElement);
267             if (CoverageState.FULL_COVERAGE == firstPathElementCoverage) {
268                 beginnings.add(new Integer  (j));
269             }
270         }
271         int[] result = new int[beginnings.size()];
272         Integer  [] b = (Integer  []) beginnings.toArray(new Integer  [beginnings.size()]);
273         for (int i = 0; i < b.length; i++) {
274             result[i] = b[i].intValue();
275         }
276         return result;
277    }
278 
279     private Path findBestMatchingPath() {
280         assert enteredBlocks.size() > 0 : "DefinitionfreePath must not be empty."; //$NON-NLS-1$
281         Path[] paths = getRegisteredMethod().getPaths();
282         Path candidate = new Path();
283         for (int i = 0; i < paths.length; i++) {
284             // if there is a full covered match we don't need to search.
285             if (paths[i].includes(this) == CoverageState.FULL_COVERAGE) {
286                 return paths[i];
287             }
288             
289             IBasicBlock[] testedBlocks = paths[i].getEnteredBlocks();
290             assert testedBlocks.length > 0 : "After a test run, paths can not be empty!"; //$NON-NLS-1$
291             /*
292              *  find the beginnings of the definition free path in the testedBlock[] 
293              *          if one is found, compare the next elements if 
294              *          the dfp is found to have more common elements. 
295              *          record how many then, and possibly 
296              *          remember it as return candidate.
297              */
298             int[] beginning = findFirstBlock(testedBlocks);
299             for (int j = 0; j < beginning.length; j++) {
300                 if (beginning[j] >= 0) {
301                     // first matching element found, check the next elements.
302                     int k = beginning[j];
303                     int matchingBlockCount = 0;
304                     if (candidate.length() == 0) {
305                         candidate = paths[i];
306                     }
307                     Iterator   iter = enteredBlocks.iterator();
308                     for (k = beginning[j]; (k < testedBlocks.length) &&
309                             iter.hasNext(); k++) {
310                         RuntimeBasicBlockWrapper wrapper = (RuntimeBasicBlockWrapper) iter.next();
311                         SsaBasicBlockWrapper dfpBlock = (SsaBasicBlockWrapper) wrapper.getWrappedBasicBlock();
312                         if (CoverageState.FULL_COVERAGE == dfpBlock.covers(testedBlocks[k])) {
313                             matchingBlockCount++;
314                         } else {
315                             if (matchingBlockCount > candidate.length()) {
316                                 candidate = paths[i];
317                             }
318                             break;
319                         }
320                     }
321                     assert matchingBlockCount > 0 : "first element found by findFirstBlock() did not match the first element in enteredBlocks!"; //$NON-NLS-1$
322                 }
323             }
324         }
325         return candidate;
326     }
327 
328     /**
329      * @return returns the same object the method clone() returns, but without
330      * the need to cast.
331      */
332     public Object   clone() {
333         DefinitionFreePath result = new DefinitionFreePath(new Integer  (index));
334         cloneFields(result);
335         result.finished = finished;
336         assert this.equals(result) : "Cloned objects are not really cloned"; //$NON-NLS-1$
337         return result;
338     }
339     
340     
341     
342     public boolean equals(Object   obj) {
343         if (obj instanceof DefinitionFreePath) {
344             DefinitionFreePath dfp = (DefinitionFreePath) obj;
345             return super.equals(obj) && index == dfp.index;
346         }
347         return super.equals(obj);
348     }
349     
350     public boolean describesSamePath(Path path) {
351         return super.equals(path);
352     }
353     
354     
355     public void addEnteredBlock(IBasicBlock block) {
356         if (finished) throw new AssertionError  ("Entry in finished DefinitionFreePath"); //$NON-NLS-1$
357         assert block instanceof SsaBasicBlockWrapper : "DefinitionFreePath only accepts SsaBasicBlockWrapper!"; //$NON-NLS-1$
358         super.addEnteredBlock(block);
359     }
360     public void addExitedBlock(IBasicBlock block) {
361         if (finished) throw new AssertionError  ("Entry in finished DefinitionFreePath"); //$NON-NLS-1$
362         assert block instanceof SsaBasicBlockWrapper : "DefinitionFreePath only accepts SsaBasicBlockWrapper!"; //$NON-NLS-1$
363         super.addExitedBlock(block);
364     }
365     public int getIndex() {
366         return index;
367     }
368 
369     /**
370      * checks whether the given DefinitionFeePath descents from the same 
371      * definition. This is true if the index and the first block are the same.
372      */
373     public boolean hasSameDefinitionAs(DefinitionFreePath dfp) {
374         return getDefinition().equals(dfp.getDefinition());
375     }
376     
377 
378     public String   toString() {
379         return "{DFP: " + getRegisteredMethod().getMethod().getName() + ":" + getDefinitionVariableName() + "}"  //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
380                 +  super.toString();
381     }
382     
383     
384     public RegisteredMethod getRegisteredMethod() {
385         return super.getRegisteredMethod();
386     }
387 
388     /**
389      * after triggerFinished is called, the path will accept no further entries.
390      */
391     public void triggerFinished() {
392         this.finished = true;
393     }
394 }
395
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags