PatchingChain


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 1997-1999 Raja Vallee-Rai
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the
16   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17   * Boston, MA 02111-1307, USA.
18   */
19  
20  /*
21   * Modified by the Sable Research Group and others 1997-1999.  
22   * See the 'credits' file distributed with Soot for the complete list of
23   * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
24   */
25  
26  package soot;
27  
28  import java.util.*;
29  import soot.util.*;
30  
31  /** An implementation of a Chain which can contain only Units,
32   * and handles patching to deal with element insertions and removals.
33   * This is done by calling Unit.redirectJumpsToThisTo at strategic
34   * times. */
35  public class PatchingChain extends AbstractCollection implements Chain 
36  {
37      protected Chain innerChain;
38  
39      /** Constructs a PatchingChain from the given Chain. */
40      public PatchingChain(Chain aChain)
41      {
42          innerChain = aChain;
43      }
44  
45      /**
46       * Returns the inner chain used by the PatchingChain.  In general,
47       * this should not be used.  However, direct access to the inner
48       * chain may be necessary if you wish to perform certain
49       * operations (such as control-flow manipulations) without
50       * interference from the patching algorithms.
51       **/
52      public Chain getNonPatchingChain()
53      {
54          return innerChain;
55      }
56      
57      /** Adds the given object to this Chain. */
58      public boolean add(Object   o)
59      {
60          return innerChain.add(o);
61      }
62  
63      /** Replaces <code>out</code> in the Chain by <code>in</code>. */
64      public void swapWith(Object   out, Object   in)
65      {
66          insertBefore(in, out);
67          remove(out);
68      }
69  
70      /** Inserts <code>toInsert</code> in the Chain after <code>point</code>. */
71      public void insertAfter(Object   toInsert, Object   point)
72      {
73          innerChain.insertAfter(toInsert, point);
74      }
75  
76      /** Inserts <code>toInsert</code> in the Chain after <code>point</code>. */
77      public void insertAfter(List toInsert, Object   point)
78      {
79          innerChain.insertAfter(toInsert, point);
80      }
81      
82      public void insertAfter(Chain toInsert, Object   point)
83      {
84          innerChain.insertAfter(toInsert, point);
85      }
86  
87      /** Inserts <code>toInsert</code> in the Chain before <code>point</code>. */
88      public void insertBefore(List toInsert, Object   point)
89      {
90          LinkedList backwardList = new LinkedList();
91          // Insert toInsert backwards into the list
92          {
93              Iterator it = toInsert.iterator();
94              
95              while(it.hasNext())
96                  backwardList.addFirst(it.next());
97          }
98                  
99          Object   previousPoint = point;
100         Iterator it = backwardList.iterator();
101         while (it.hasNext())
102         {
103             Object   o = it.next();
104             insertBefore(o, previousPoint);
105             previousPoint = o;
106         }
107     }
108     
109     /** Inserts <code>toInsert</code> in the Chain before <code>point</code>. */
110     public void insertBefore(Chain toInsert, Object   point)
111     {
112         LinkedList backwardList = new LinkedList();
113         // Insert toInsert backwards into the list
114         {
115             Iterator it = toInsert.iterator();
116             
117             while(it.hasNext())
118                 backwardList.addFirst(it.next());
119         }
120                 
121         Object   previousPoint = point;
122         Iterator it = backwardList.iterator();
123         while (it.hasNext())
124         {
125             Object   o = it.next();
126             insertBefore(o, previousPoint);
127             previousPoint = o;
128         }
129     }
130 
131     /** Inserts <code>toInsert</code> in the Chain before <code>point</code>. */
132     public void insertBefore(Object   toInsert, Object   point)
133     {
134         ((Unit) point).redirectJumpsToThisTo((Unit) toInsert);
135         innerChain.insertBefore(toInsert, point);
136     }
137 
138     /** Returns true if object <code>a</code> follows object <code>b</code> in the Chain. */
139     public boolean follows(Object   a, Object   b)
140     {
141         return innerChain.follows(a,b);
142     }
143 
144     /** Removes the given object from this Chain. */
145     public boolean remove(Object   obj)
146     {
147         boolean res = false;
148 
149         if(contains(obj))
150         {
151             Unit successor;
152             
153             if((successor = (Unit)getSuccOf(obj)) == null)
154                 successor = (Unit)getPredOf(obj); 
155         // Note that redirecting to the last unit in the method 
156         // like this is probably incorrect when dealing with a Trap.
157             // I.e., let's say that the final unit in the method used to
158             // be U10, preceded by U9, and that there was a Trap which
159             // returned U10 as getEndUnit(). I.e., before the trap covered U9.
160             // When we redirect the Trap's end unit to U9, the trap will no
161             // longer cover U9. I know this is incorrect, but I'm not sure how
162             // to fix it, so I'm leaving this comment in the hopes that some
163             // future maintainer will see the right course to take.
164             
165             res = innerChain.remove(obj);
166 
167             ((Unit)obj).redirectJumpsToThisTo(successor);
168         }
169 
170         return res;        
171     }
172 
173     /** Returns true if this patching chain contains the specified element. */
174     public boolean contains(Object   u)
175     {
176         return innerChain.contains(u);
177     }
178 
179     /** Adds the given object at the beginning of the Chain. */
180     public void addFirst(Object   u)
181     {
182         innerChain.addFirst(u);
183     }
184     
185     /** Adds the given object at the end of the Chain. */
186     public void addLast(Object   u)
187     {
188         innerChain.addLast(u);
189     }
190     
191     /** Removes the first object from this Chain. */
192     public void removeFirst() 
193     {
194         remove(innerChain.getFirst());
195     }
196     
197     /** Removes the last object from this Chain. */
198     public void removeLast()
199     {
200         remove(innerChain.getLast());
201     }
202     
203     /** Returns the first object in this Chain. */
204     public Object   getFirst() { return innerChain.getFirst(); }
205 
206     /** Returns the last object in this Chain. */
207     public Object   getLast() { return innerChain.getLast(); }
208     
209     /** Returns the object immediately following <code>point</code>. */
210     public Object   getSuccOf(Object   point){return innerChain.getSuccOf(point);}
211 
212     /** Returns the object immediately preceding <code>point</code>. */
213     public Object   getPredOf(Object   point){return innerChain.getPredOf(point);}
214 
215     protected class PatchingIterator implements Iterator
216     {
217         protected Iterator innerIterator = null;
218         protected Object   lastObject;
219         protected boolean state = false;
220 
221         protected PatchingIterator (Chain innerChain) { innerIterator = innerChain.iterator(); }
222         protected PatchingIterator (Chain innerChain, Object   u) { innerIterator = innerChain.iterator(u); }
223         protected PatchingIterator (Chain innerChain, Object   head, Object   tail) { innerIterator = innerChain.iterator(head, tail); }
224 
225         public boolean hasNext() { return innerIterator.hasNext(); }
226         public Object   next() { lastObject = innerIterator.next(); state = true; return lastObject; }
227         public void remove() 
228         { 
229             if (!state)
230                 throw new IllegalStateException  ("remove called before first next() call");
231 
232             Unit successor;
233             
234               if((successor = (Unit)getSuccOf(lastObject)) == null)
235           successor = (Unit)getPredOf(lastObject);
236           // Note that redirecting to the last unit in the method 
237           // like this is probably incorrect when dealing with a Trap.
238           // I.e., let's say that the final unit in the method used to
239           // be U10, preceded by U9, and that there was a Trap which
240           // returned U10 as getEndUnit(). I.e., before the trap covered U9.
241           // When we redirect the Trap's end unit to U9, the trap will no
242           // longer cover U9. I know this is incorrect, but I'm not sure how
243           // to fix it, so I'm leaving this comment in the hopes that some
244           // future maintainer will see the right course to take.
245             
246             innerIterator.remove();
247 
248             ((Unit)lastObject).redirectJumpsToThisTo(successor);
249         }
250     }
251 
252     /** Returns an iterator over a copy of this chain. 
253      * This avoids ConcurrentModificationExceptions from being thrown
254      * if the underlying Chain is modified during iteration.
255      * Do not use this to remove elements which have not yet been
256      * iterated over! */
257     public Iterator snapshotIterator() 
258     {
259         List l = new ArrayList(); l.addAll(this);
260         return l.iterator();
261     }
262    
263     /** Returns an iterator over this Chain. */
264     public Iterator iterator() { return new PatchingIterator(innerChain); }
265 
266     /** Returns an iterator over this Chain, starting at the given object. */
267     public Iterator iterator(Object   u) { return new PatchingIterator(innerChain, u); }
268 
269     /** Returns an iterator over this Chain, starting at head and reaching tail (inclusive). */
270     public Iterator iterator(Object   head, Object   tail) { return new PatchingIterator(innerChain, head, tail); }
271 
272     /** Returns the size of this Chain. */
273     public int size(){return innerChain.size(); }
274 }
275
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags