1 19 20 25 26 27 package soot.jimple.toolkits.typing; 28 29 import soot.*; 30 import soot.jimple.*; 31 import soot.util.*; 32 import java.util.*; 33 34 class StronglyConnectedComponentsBV 35 { 36 BitVector variables; 37 Set black; 38 LinkedList finished; 39 40 TypeResolverBV resolver; 41 42 LinkedList forest = new LinkedList(); 43 LinkedList current_tree; 44 45 private static final boolean DEBUG = false; 46 47 public StronglyConnectedComponentsBV(BitVector typeVariableList, TypeResolverBV resolver) throws TypeException 48 { 49 this.resolver = resolver; 50 variables = typeVariableList; 51 52 black = new TreeSet(); 53 finished = new LinkedList(); 54 55 for(BitSetIterator i = variables.iterator(); i.hasNext(); ) 56 { 57 TypeVariableBV var = resolver.typeVariableForId(i.next()); 58 59 if(!black.contains(var)) 60 { 61 black.add(var); 62 dfsg_visit(var); 63 } 64 } 65 66 black = new TreeSet(); 67 68 for(Iterator i = finished.iterator(); i.hasNext(); ) 69 { 70 TypeVariableBV var = (TypeVariableBV) i.next(); 71 72 if(!black.contains(var)) 73 { 74 current_tree = new LinkedList(); 75 forest.add(current_tree); 76 black.add(var); 77 dfsgt_visit(var); 78 } 79 } 80 81 for(Iterator i = forest.iterator(); i.hasNext();) 82 { 83 LinkedList list = (LinkedList) i.next(); 84 TypeVariableBV previous = null; 85 StringBuffer s = null; 86 if(DEBUG) 87 { 88 s = new StringBuffer ("scc:\n"); 89 } 90 91 for(Iterator j = list.iterator(); j.hasNext();) 92 { 93 TypeVariableBV current = (TypeVariableBV) j.next(); 94 95 if(DEBUG) 96 { 97 s.append(" " + current + "\n"); 98 } 99 100 if(previous == null) 101 { 102 previous = current; 103 } 104 else 105 { 106 try 107 { 108 previous = previous.union(current); 109 } 110 catch(TypeException e) 111 { 112 if(DEBUG) 113 { 114 G.v().out.println(s); 115 } 116 throw e; 117 } 118 } 119 } 120 } 121 } 122 123 private void dfsg_visit(TypeVariableBV var) 124 { 125 BitVector parents = var.parents(); 126 127 for(BitSetIterator i = parents.iterator(); i.hasNext(); ) 128 { 129 TypeVariableBV parent = resolver.typeVariableForId(i.next()); 130 131 if(!black.contains(parent)) 132 { 133 black.add(parent); 134 dfsg_visit(parent); 135 } 136 } 137 138 finished.add(0, var); 139 } 140 141 private void dfsgt_visit(TypeVariableBV var) 142 { 143 current_tree.add(var); 144 145 BitVector children = var.children(); 146 147 for(BitSetIterator i = children.iterator(); i.hasNext(); ) 148 { 149 TypeVariableBV child = resolver.typeVariableForId(i.next()); 150 151 if(!black.contains(child)) 152 { 153 black.add(child); 154 dfsgt_visit(child); 155 } 156 } 157 } 158 } 159 | Popular Tags |