KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > typing > StronglyConnectedComponentsBV


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-2000 Etienne Gagnon. All rights reserved.
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
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 JavaDoc s = null;
86     if(DEBUG)
87       {
88         s = new StringBuffer JavaDoc("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