Path


1   /*
2    * Created on Aug 13, 2004
3    */
4   package de.uka.ipd.coverage.recording;
5   
6   import java.io.Serializable  ;
7   import java.util.*;
8   
9   /**
10   * This is a class representing a path that is taken in a test run.
11   * A <code>Path</code> object records the way through basic blocks
12   * in a method. A <code>Path</code> object is responsible for one method only,
13   * necessary records in a method B that was called within a basic block
14   * of method A do not touch the <code>Path</code> object of method A.<br>
15   * Note, that although a <code>Path</code> object is responsible for exactly
16   * one method, there can be several <code>Path</code> objects at the same time
17   * for one method. 
18   * 
19   * @author Matthias Kempka
20   */
21  
22  public class Path implements Cloneable  , Serializable  , Comparable   {
23      
24      // contains RuntimeBasicBlockWrapper elements;
25      protected LinkedList enteredBlocks = new LinkedList();
26      private RuntimeBasicBlockWrapper currentBlock = null;  
27      
28      public Path() {}
29      
30      /**
31       * this method decides whether the given path includes the comparing path.
32       * this means, the comparing path object has to represent a sub-path of of
33       * the parameter path to achieve full coverage.<br>
34       * partial coverage is achieved if both paths contain a common sub-path.<br>
35       * A path is a sub-path if a sequence of its BasicBlock objects is covered.
36       * The blocks of the 
37       * parameter are not checked for entering or exiting.
38       * 
39       * @param path
40       */
41      public CoverageState includes(Path path) {
42          if (path == null) {
43              throw new IllegalArgumentException  ("Path must be non-null for " + //$NON-NLS-1$
44                      "a coverage decision"); //$NON-NLS-1$
45          }
46          if (path.enteredBlocks.isEmpty()) {
47              // empty path is always covered
48              return CoverageState.FULL_COVERAGE;
49          } else if (this.enteredBlocks.isEmpty()) {
50              return CoverageState.NO_COVERAGE;
51          }
52          RuntimeBasicBlockWrapper pathFirstElement = 
53              (RuntimeBasicBlockWrapper) path.enteredBlocks.get(0);
54          
55          /* iterate over the elements in this.blockList:
56           *      compare each one with the first of the supposed subpath.
57           *          if one is found, compare the next elements until path
58           *          is proven to be a sub-path or to be none.
59           *          if somewhere after the first element there is a mismatch, 
60           *          the path is a partial sub-path in any case. 
61           */
62          for (ListIterator iter = (ListIterator)enteredBlocks.iterator(); iter.hasNext();) {
63              RuntimeBasicBlockWrapper element = (RuntimeBasicBlockWrapper) iter.next();
64              CoverageState firstPathElementCoverage 
65                      = element.covers(pathFirstElement);
66              
67              if (CoverageState.FULL_COVERAGE == firstPathElementCoverage) {
68                  // first matching element found, check the next elements.
69                  int elementIndex = iter.nextIndex() - 1;
70                  List sublist = enteredBlocks.subList(elementIndex, enteredBlocks.size());
71                  return getCoverage(sublist, path.enteredBlocks);
72              } else if (CoverageState.PARTIAL_COVERAGE == firstPathElementCoverage) {
73                  // first matching element found, but only with partial coverage
74                  return CoverageState.PARTIAL_COVERAGE;
75              } 
76          }
77          return CoverageState.NO_COVERAGE;
78      }
79      
80      /**
81       * this method is used by includes.
82       * precondition: the first BasicBlock A of path must have full coverage
83       * by the first BasicBlock B of sublist, checked via B.covers(A).<br>
84       * returns whether the retaining BasicBlocks in path are also covered by
85       * the next BasicBlocks of sublist. If so, the return value is full coverage,
86       * otherwise it is partial coverage.
87       * @param sublist
88       * @param path
89       */
90      private CoverageState getCoverage(List sublist, List path) {
91          Iterator compIter = sublist.iterator();
92          Iterator pathIter = path.iterator();
93          RuntimeBasicBlockWrapper compElement = (RuntimeBasicBlockWrapper) compIter.next();
94          RuntimeBasicBlockWrapper pathElement = (RuntimeBasicBlockWrapper) pathIter.next();
95          while(CoverageState.FULL_COVERAGE == compElement.covers(pathElement)) { 
96              if (!pathIter.hasNext()) { 
97                  // a coverage has been found
98                  return CoverageState.FULL_COVERAGE;
99              } else if (!compIter.hasNext()) { // only of interest 
100                                             // if first condition
101                                             // didn't match
102                 // end of the comparing path, partial coverage
103                 return CoverageState.PARTIAL_COVERAGE;
104             }
105             compElement = (RuntimeBasicBlockWrapper) compIter.next();
106             pathElement = (RuntimeBasicBlockWrapper) pathIter.next();
107         }
108         // a part of path was found and is now ended with a
109         // not or partial covered block. Result is partial coverage
110         return CoverageState.PARTIAL_COVERAGE;
111     }
112 
113     public void addEnteredBlock(IBasicBlock block) {
114         currentBlock = new RuntimeBasicBlockWrapper(block);
115         currentBlock.triggerEntered();
116         this.enteredBlocks.add(currentBlock);
117     }
118     
119     public void addExitedBlock(IBasicBlock block) {
120         assert currentBlock != null 
121                 && currentBlock.isEntered()
122                 && !currentBlock.isExited() :
123                     "currentBlock not entered but exited!"; //$NON-NLS-1$
124         currentBlock.triggerExited();
125         currentBlock = null;
126     }
127     
128     /**
129      * toString method for a path. Blocks are in parenthesises, first the
130      * start, then the end line. Exclamationmarks are set in front of the 
131      * line numbers to denote whether a line mark was not executed.
132      */
133     public String   toString() {
134         String   result = "[ "; //$NON-NLS-1$
135         boolean afterfirstIteration = false;
136         for (Iterator iter = enteredBlocks.iterator(); iter.hasNext();) {
137             if (afterfirstIteration) {
138                 result += ", "; //$NON-NLS-1$
139             }
140             RuntimeBasicBlockWrapper element = (RuntimeBasicBlockWrapper) iter.next();
141             result += "("; //$NON-NLS-1$
142             if (!element.isEntered()) {
143                 result += "!"; //$NON-NLS-1$
144             }
145             result += element.getStartLine() + ","; //$NON-NLS-1$
146             if (!element.isExited()) {
147                 result += "!";  //$NON-NLS-1$
148             }
149             result += element.getEndLine() + ")"  ; //$NON-NLS-1$
150             afterfirstIteration = true;
151         }
152         result += " ]"; //$NON-NLS-1$
153         return result;
154     }
155     
156     public boolean equals(Object   obj) {
157         if (obj instanceof Path) {
158             Path comPath = (Path) obj;
159             if (!this.getRegisteredMethod().equals(comPath.getRegisteredMethod())) {
160                 return false;
161             }
162             Iterator compIter = comPath.enteredBlocks.iterator();
163             Iterator iter = enteredBlocks.iterator();
164             while (compIter.hasNext() & iter.hasNext()) {
165                 if (!iter.next().equals(compIter.next())) {
166                     return false;
167                 }
168             }
169             if (compIter.hasNext() != iter.hasNext()) {
170                 return false;
171             }
172             return true;
173         }
174         return false;
175     }
176 
177     public int hashCode() {
178         int pow = (int) Math.pow(enteredBlocks.size(), 4);
179         //TODO: use larger prime number.
180         return pow % 151;
181     }
182 
183     public Object   clone() {
184         Path result = new Path();
185         cloneFields(result);
186         assert this.equals(result) : "Cloned objects are not really cloned"; //$NON-NLS-1$
187         return result;
188     }
189     
190     protected void cloneFields(Path target) {
191         if (currentBlock != null) {
192             target.currentBlock = (RuntimeBasicBlockWrapper) this.currentBlock.clone();
193         }
194         target.enteredBlocks = (LinkedList) this.enteredBlocks.clone();
195     }
196     
197     /**
198      * @return returns the Method for this path or <code>null</code> if there is
199      * none (meaning the path is empty). 
200      */
201     public RegisteredMethod getRegisteredMethod() {
202         if (enteredBlocks.isEmpty()) {
203             return null;
204         }
205         return ((IBasicBlock) enteredBlocks.getFirst()).getRegisteredMethod();
206     }
207     
208     public IBasicBlock[] getEnteredBlocks() {
209         return (IBasicBlock[]) enteredBlocks.toArray(new IBasicBlock[enteredBlocks.size()]);
210     }
211     
212     public IBasicBlock[] getEnteredBlocksWithoutReiteratedLoops() {
213         List result = new ArrayList(enteredBlocks);
214         snipReiteratedLoops(result);
215         return (IBasicBlock[]) result.toArray(new IBasicBlock[result.size()]);
216     }
217     
218     public int length() {
219         return enteredBlocks.size();
220     }
221 
222     public int compareTo(Object   o) {
223         if (o instanceof Path) {
224             Path cPath = (Path) o;
225             return this.compareTo(cPath, 0);
226         }
227         throw new AssertionError  ("compared object not of class Path!"); //$NON-NLS-1$
228     }
229     
230     private int compareTo(Path path, int recursion) {
231         if (recursion == enteredBlocks.size()) {
232             return 0;
233         } else if (recursion == path.enteredBlocks.size()) {
234             return -1;
235         }
236         
237         IBasicBlock cBlock = (IBasicBlock) path.enteredBlocks.get(recursion);
238         IBasicBlock block = (IBasicBlock) enteredBlocks.get(recursion);
239         if (block.getStartLine() > cBlock.getStartLine()) {
240             return 1;
241         } else if (block.getStartLine() < cBlock.getStartLine()) {
242             return 0;
243         } else {
244             return compareTo(path, recursion + 1);
245         }
246     }
247 
248     /**
249      * checks if dfp is a subPath of this path assuming this path has not 
250      * traversed loop(s) a second time.
251      * @return returns only full coverage or no coverage. partial coverage is not
252      * checked.
253      */
254     public CoverageState loopIncludes(Path subPathWithoutLoops) {
255         if (subPathWithoutLoops == null) {
256             throw new IllegalArgumentException  ("Path must be non-null for " + //$NON-NLS-1$
257                     "a coverage decision"); //$NON-NLS-1$
258         }
259         if (subPathWithoutLoops.enteredBlocks.isEmpty()) {
260             // empty path is always covered
261             return CoverageState.FULL_COVERAGE;
262         } else if (this.enteredBlocks.isEmpty()) {
263             return CoverageState.NO_COVERAGE;
264         }
265         RuntimeBasicBlockWrapper pathFirstElement = 
266             (RuntimeBasicBlockWrapper) subPathWithoutLoops.enteredBlocks.get(0);
267         
268         /* iterate over the elements in this.blockList:
269          *      compare each one with the first of the supposed subpath.
270          *          if one is found, compare the next elements until path
271          *          is proven to be a sub-path or to be none.
272          *          if somewhere after the first element there is a mismatch, 
273          *          the path is a partial sub-path in any case. 
274          */
275         for (ListIterator iter = (ListIterator)enteredBlocks.iterator(); iter.hasNext();) {
276             RuntimeBasicBlockWrapper element = (RuntimeBasicBlockWrapper) iter.next();
277             CoverageState firstPathElementCoverage 
278                     = element.covers(pathFirstElement);
279             
280             if (CoverageState.FULL_COVERAGE == firstPathElementCoverage) {
281                 // first matching element found, check the next elements.
282                 int elementIndex = iter.nextIndex() - 1;
283                 List sublist = enteredBlocks.subList(elementIndex, enteredBlocks.size());
284                 List clonedSublist = new ArrayList(sublist);
285                 snipReiteratedLoops(clonedSublist);
286                 return getCoverage(clonedSublist, subPathWithoutLoops.enteredBlocks);
287             } else if (CoverageState.PARTIAL_COVERAGE == firstPathElementCoverage) {
288                 // first matching element found, but only with partial coverage
289                 return CoverageState.PARTIAL_COVERAGE;
290             } 
291         }
292         return CoverageState.NO_COVERAGE;
293     }
294 
295     private void snipReiteratedLoops(List sublist) {
296         int loopStart = getStartLoopPosition(sublist);
297         int loopStop = Integer.MAX_VALUE;
298         while (loopStart >= 0 && loopStop >= loopStart) {
299             loopStop = getStopLoopPosition(sublist, loopStart);
300             sublist.subList(loopStart, loopStop + 1).clear();
301             loopStart = getStartLoopPosition(sublist);
302         }
303     }
304     
305     private int getStopLoopPosition(List list, int loopstart) {
306         List sublist = list.subList(loopstart, list.size());
307         Object   searchObject = list.get(loopstart - 1);
308         int stopPos = sublist.indexOf(searchObject);
309         return stopPos + loopstart;
310     }
311 
312     /**
313      * @param sublist
314      * @return returns the index of the first element in sublist that occurs
315      * twice thus indicating a loop.
316      */
317     private int getStartLoopPosition(List sublist) {
318         List history = new ArrayList();
319         int result = 0;
320         for (Iterator iter = sublist.iterator(); iter.hasNext();) {
321             IBasicBlock current = (IBasicBlock) iter.next();
322             if (containsBlock(history, current)) {
323                 return result;
324             }
325             history.add(current);
326             result++;
327         }
328         return Integer.MIN_VALUE;
329     }
330 
331     private boolean containsBlock(List history, IBasicBlock current) {
332         for (Iterator iter = history.iterator(); iter.hasNext();) {
333             IBasicBlock element = (IBasicBlock) iter.next();
334             if (CoverageState.FULL_COVERAGE == element.covers(current)) {
335                 return true;
336             }
337         }
338         return false;
339     }
340 }
341
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags