Svelte/src/edu/berkeley/cs/bodik/svelte/plugin/bfsliceview/BFSliceInput.java

   1 /*******************************************************************************
   2  * This program and the accompanying materials
   3  * are made available under the terms of the Eclipse Public License v1.0
   4  * which accompanies this distribution, and is available at
   5  * http://www.eclipse.org/legal/epl-v10.html.
   6  *
   7  * This file is a derivative of code released by the University of
   8  * California under the terms listed below.
   9  *
  10  * Refinement Analysis Tools is Copyright ©2007 The Regents of the
  11  * University of California (Regents). Provided that this notice and
  12  * the following two paragraphs are included in any distribution of
  13  * Refinement Analysis Tools or its derivative work, Regents agrees
  14  * not to assert any of Regents' copyright rights in Refinement
  15  * Analysis Tools against recipient for recipients reproduction,
  16  * preparation of derivative works, public display, public
  17  * performance, distribution or sublicensing of Refinement Analysis
  18  * Tools and derivative works, in source code and object code form.
  19  * This agreement not to assert does not confer, by implication,
  20  * estoppel, or otherwise any license or rights in any intellectual
  21  * property of Regents, including, but not limited to, any patents
  22  * of Regents or Regents employees.
  23  *
  24  * IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT,
  25  * INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
  26  * INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE
  27  * AND ITS DOCUMENTATION, EVEN IF REGENTS HAS BEEN ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
  31  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  32  * FOR A PARTICULAR PURPOSE AND FURTHER DISCLAIMS ANY STATUTORY
  33  * WARRANTY OF NON-INFRINGEMENT. THE SOFTWARE AND ACCOMPANYING
  34  * DOCUMENTATION, IF ANY, PROVIDED HEREUNDER IS PROVIDED "AS
  35  * IS". REGENTS HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
  36  * UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  37  */
  38 package edu.berkeley.cs.bodik.svelte.plugin.bfsliceview;
  39
  40 import java.util.ArrayList;
  41 import java.util.Hashtable;
  42 import java.util.Iterator;
  43
  44 import com.ibm.wala.ipa.slicer.Statement;
  45 import com.ibm.wala.util.graph.Graph;
  46
  47 import edu.berkeley.cs.bodik.svelte.Slice;
  48
  49 interface BFSliceStatement {
  50         Statement getStatement();
  51
  52         public ArrayList<BFSliceStatement> getChildren();
  53         public boolean hasChildren();
  54
  55         /**
  56          * A BFSliceStatement normally keeps a cache of its children. When the children are no longer needed
  57          * (i.e. when we go up a level) they can forgotten about so the GC can free the memory. This is necessary
  58          * because the <code>BFSliceInput.getChildren()</code> function must generate its children for each parent so we can
  59          * have different BFSliceStatements referring to the same Statement.
  60          */
  61         void freeChildren();
  62
  63         /**
  64          * Markings. Along with freeChildren, these don't really make sense for the RootStatement.
  65          */
  66         public void markCheck();
  67         public void unmarkCheck();
  68         public boolean isMarkedChecked();
  69
  70         public BFSliceStatement getParent();
  71
  72
  73 }
  74
  75 public class BFSliceInput {
  76         private Graph<Statement> graph;
  77         private Slice seed;
  78         private RootStatement root;
  79
  80         private Hashtable<Statement,Boolean> markings = new Hashtable<Statement,Boolean>();
  81
  82         /**
  83          * Wrapper around a real statement.
  84          * This allows one Statement in the slice to have more than one incarnation in the viewer, since
  85          * they are only equal if they are the same object.
  86          * @author evan
  87          *
  88          */
  89         private class RealStatement implements BFSliceStatement {
  90                 Statement s;
  91                 ArrayList<BFSliceStatement> children;
  92                 private BFSliceStatement parent;
  93
  94
  95                 public RealStatement(Statement s, BFSliceStatement parent) {
  96                         this.s = s;
  97                         children = null;
  98                         this.parent = parent;
  99                 }
 100
 101                 public String toString() {
 102                         return s.toString();
 103                 }
 104
 105                 public boolean equals(Object x) {
 106                         return x == this;
 107                 }
 108
 109                 public Statement getStatement() {
 110                         return s;
 111                 }
 112
 113                 public ArrayList<BFSliceStatement> getChildren() {
 114                         if ( children == null ) {
 115                                 children = new ArrayList<BFSliceStatement>();
 116                                 Iterator<? extends Statement> iter = graph.getSuccNodes(s);
 117                                 while ( iter.hasNext() ) {
 118                                         children.add(new RealStatement(iter.next(), this));
 119                                 }
 120                         }
 121                         return children;
 122                 }
 123
 124                 public void freeChildren() {
 125                         if ( children != null ) {
 126                                 children.clear();
 127                                 children = null;
 128                         }
 129                 }
 130
 131                 public void markCheck() {
 132                         markings.put(s, new Boolean(true));
 133                 }
 134
 135                 public void unmarkCheck() {
 136                         if ( markings.containsKey(s) )
 137                                 markings.remove(s);
 138                 }
 139
 140                 public boolean isMarkedChecked() {
 141                         return markings.containsKey(s) && markings.get(s).booleanValue();
 142                 }
 143
 144                 public BFSliceStatement getParent() {
 145                         return parent;
 146                 }
 147
 148                 public boolean hasChildren() {
 149                         return graph.getSuccNodes(s).hasNext();
 150                 }
 151         }
 152
 153         /**
 154          * Fake statement representing parent of all seeds in a slice.
 155          * @author evan
 156          */
 157         private class RootStatement implements BFSliceStatement {
 158                 ArrayList<BFSliceStatement> children;
 159
 160                 @Override
 161                 public boolean equals(Object obj) {
 162                     return obj == root;
 163                 }
 164
 165                 @Override
 166                 public int hashCode() {
 167                         return graph.hashCode() + seed.hashCode();
 168                 }
 169
 170                 @Override
 171                 public String toString() {
 172                         return "All Seed Statements";
 173                 }
 174
 175                 public Statement getStatement() {
 176                         return null;
 177                 }
 178
 179                 public void freeChildren() {
 180                         // you cannot back up beyond the root node
 181                 }
 182
 183                 public ArrayList<BFSliceStatement> getChildren() {
 184                         if ( children == null ) {
 185                                 children = new ArrayList<BFSliceStatement>();
 186                                 Iterator<? extends Statement> iter = seed.iterator();
 187                                 while ( iter.hasNext() ) {
 188                                         children.add(new RealStatement(iter.next(), root));
 189                                 }
 190                         }
 191                         return children;
 192                 }
 193
 194                 public boolean isMarkedChecked() {
 195                         return false;
 196                 }
 197
 198                 public void markCheck() {
 199                 }
 200
 201                 public void unmarkCheck() {
 202                 }
 203
 204                 public BFSliceStatement getParent() {
 205                         // TODO Auto-generated method stub
 206                         return null;
 207                 }
 208
 209                 public boolean hasChildren() {
 210                         return true;
 211                 }
 212
 213         }
 214
 215         public BFSliceInput(Graph<Statement> graph, Slice seed) {
 216                 this.graph = graph;
 217                 this.seed = seed;
 218                 this.root = new RootStatement();
 219         }
 220
 221         // in the future we might wasn't abstractions to different kinds of slices (CI thin, CS thin, CS thick) in here.
 222         public BFSliceStatement getRoot() {
 223                 return root;
 224         }
 225
 226 //      public void add(Word word) {
 227 //      list.add(word);
 228 //      writeFile();
 229 //      if (listener != null)
 230 //      listener.added(word);
 231 //      }
 232
 233 //      public void remove(Word word) {
 234 //      list.remove(word);
 235 //      writeFile();
 236 //      if (listener != null)
 237 //      listener.removed(word);
 238 //      }
 239
 240 //      public Word find(String str) {
 241 //      Iterator iter = list.iterator();
 242 //      while (iter.hasNext()) {
 243 //      Word word = (Word)iter.next();
 244 //      if (str.equals(word.toString()))
 245 //      return word;
 246 //      }
 247 //      return null;
 248 //      }
 249 }
 250
 251