001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1997-2000 Etienne Gagnon. All rights reserved.
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot.jimple.toolkits.typing.integer;
027:
028: import soot.*;
029: import java.util.*;
030:
031: class StronglyConnectedComponents {
032: List<TypeVariable> variables;
033: Set<TypeVariable> black;
034: LinkedList<TypeVariable> finished;
035:
036: LinkedList<LinkedList<TypeVariable>> forest = new LinkedList<LinkedList<TypeVariable>>();
037: LinkedList<TypeVariable> current_tree;
038:
039: private static final boolean DEBUG = false;
040:
041: public static void merge(List<TypeVariable> typeVariableList)
042: throws TypeException {
043: new StronglyConnectedComponents(typeVariableList);
044: }
045:
046: private StronglyConnectedComponents(
047: List<TypeVariable> typeVariableList) throws TypeException {
048: variables = typeVariableList;
049:
050: black = new TreeSet<TypeVariable>();
051: finished = new LinkedList<TypeVariable>();
052:
053: for (TypeVariable var : variables) {
054: if (!black.contains(var)) {
055: black.add(var);
056: dfsg_visit(var);
057: }
058: }
059:
060: black = new TreeSet<TypeVariable>();
061:
062: for (TypeVariable var : finished) {
063: if (!black.contains(var)) {
064: current_tree = new LinkedList<TypeVariable>();
065: forest.add(current_tree);
066: black.add(var);
067: dfsgt_visit(var);
068: }
069: }
070:
071: for (Iterator<LinkedList<TypeVariable>> i = forest.iterator(); i
072: .hasNext();) {
073: LinkedList list = i.next();
074: TypeVariable previous = null;
075: StringBuffer s = null;
076: if (DEBUG) {
077: s = new StringBuffer("scc:\n");
078: }
079:
080: for (Iterator j = list.iterator(); j.hasNext();) {
081: TypeVariable current = (TypeVariable) j.next();
082:
083: if (DEBUG) {
084: s.append(" " + current + "\n");
085: }
086:
087: if (previous == null) {
088: previous = current;
089: } else {
090: try {
091: previous = previous.union(current);
092: } catch (TypeException e) {
093: if (DEBUG) {
094: G.v().out.println(s);
095: }
096: throw e;
097: }
098: }
099: }
100: }
101: }
102:
103: private void dfsg_visit(TypeVariable var) {
104: List<TypeVariable> parents = var.parents();
105:
106: for (TypeVariable parent : parents) {
107: if (!black.contains(parent)) {
108: black.add(parent);
109: dfsg_visit(parent);
110: }
111: }
112:
113: finished.add(0, var);
114: }
115:
116: private void dfsgt_visit(TypeVariable var) {
117: current_tree.add(var);
118:
119: List<TypeVariable> children = var.children();
120:
121: for (TypeVariable child : children) {
122: if (!black.contains(child)) {
123: black.add(child);
124: dfsgt_visit(child);
125: }
126: }
127: }
128: }
|