001: /*
002: * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package com.sun.tools.internal.xjc.reader.gbind;
027:
028: import java.util.Collections;
029: import java.util.HashSet;
030: import java.util.Iterator;
031: import java.util.List;
032: import java.util.Set;
033:
034: /**
035: * {@link Expression} that represents an alphabet of a regular language.
036: *
037: * <p>
038: * Since this package is about a regular expression over element declarations,
039: * this represents an XML element declaration (hence the name.)
040: *
041: * Element needs to be interned, meaning one {@link Element} per one tag name.
042: *
043: * <p>
044: * Implements {@link ElementSet} to represent a self.
045: *
046: * @author Kohsuke Kawaguchi
047: */
048: public abstract class Element extends Expression implements ElementSet {
049: /**
050: * Once we build a graph from {@link Expression},
051: * we represent an edge e1 -> e2 by {@code e1.foreEdges.contains(e2)}
052: * and {@code e2.backEdges.contains(e1)}.
053: */
054: final Set<Element> foreEdges = new HashSet<Element>();
055: final Set<Element> backEdges = new HashSet<Element>();
056:
057: /**
058: * Previous element in the DFS post-order traveral
059: * of the element graph.
060: *
061: * <p>
062: * We use {@code prevPostOrder==null} as a check if the element is visted in DFS,
063: * so this chain terminates by a self-reference, not by having null.
064: *
065: * Set in {@link #assignDfsPostOrder(Element)}
066: */
067: /*package*/Element prevPostOrder;
068:
069: /**
070: * {@link ConnectedComponent} to which this element belongs.
071: *
072: * Set in {@link #buildStronglyConnectedComponents(List<ConnectedComponent>)}
073: */
074: private ConnectedComponent cc;
075:
076: protected Element() {
077: }
078:
079: ElementSet lastSet() {
080: return this ;
081: }
082:
083: boolean isNullable() {
084: return false;
085: }
086:
087: /**
088: * True if this {@link Element} is {@link SourceNode}.
089: */
090: boolean isSource() {
091: return false;
092: }
093:
094: /**
095: * True if this {@link Element} is {@link SinkNode}.
096: */
097: boolean isSink() {
098: return false;
099: }
100:
101: void buildDAG(ElementSet incoming) {
102: incoming.addNext(this );
103: }
104:
105: public void addNext(Element element) {
106: foreEdges.add(element);
107: element.backEdges.add(this );
108: }
109:
110: public boolean contains(ElementSet rhs) {
111: return this == rhs || rhs == ElementSet.EMPTY_SET;
112: }
113:
114: /**
115: * Just to satisfy the {@link ElementSet} contract.
116: *
117: * @deprecated
118: * if you statically call this method, there's something wrong.
119: */
120: public Iterator<Element> iterator() {
121: return Collections.singleton(this ).iterator();
122: }
123:
124: /**
125: * Traverses the {@link Element} graph with DFS
126: * and set {@link #prevPostOrder}.
127: *
128: * Should be first invoked on the source node of the graph.
129: */
130: /*package*/Element assignDfsPostOrder(Element prev) {
131: if (prevPostOrder != null)
132: return prev; // already visited
133:
134: prevPostOrder = this ; // set a dummy value to prepare for cycles
135:
136: for (Element next : foreEdges) {
137: prev = next.assignDfsPostOrder(prev);
138: }
139: this .prevPostOrder = prev; // set to the real value
140: return this ;
141: }
142:
143: /**
144: * Builds a set of strongly connected components and puts them
145: * all into the given set.
146: */
147: public void buildStronglyConnectedComponents(
148: List<ConnectedComponent> ccs) {
149: for (Element cur = this ; cur != cur.prevPostOrder; cur = cur.prevPostOrder) {
150: if (cur.belongsToSCC())
151: continue;
152:
153: // start a new component
154: ConnectedComponent cc = new ConnectedComponent();
155: ccs.add(cc);
156:
157: cur.formConnectedComponent(cc);
158: }
159: }
160:
161: private boolean belongsToSCC() {
162: return cc != null || isSource() || isSink();
163: }
164:
165: /**
166: * Forms a strongly connected component by doing a reverse DFS.
167: */
168: private void formConnectedComponent(ConnectedComponent group) {
169: if (belongsToSCC())
170: return;
171:
172: this .cc = group;
173: group.add(this );
174: for (Element prev : backEdges)
175: prev.formConnectedComponent(group);
176: }
177:
178: public boolean hasSelfLoop() {
179: // if foreEdges have a loop, backEdges must have one. Or vice versa
180: assert foreEdges.contains(this ) == backEdges.contains(this );
181:
182: return foreEdges.contains(this );
183: }
184:
185: /**
186: * Checks if the given {@link ConnectedComponent} forms a cut-set
187: * of a graph.
188: *
189: * @param visited
190: * Used to keep track of visited nodes.
191: * @return
192: * true if it is indeed a cut-set. false if not.
193: */
194: /*package*/final boolean checkCutSet(ConnectedComponent cc,
195: Set<Element> visited) {
196: assert belongsToSCC(); // SCC discomposition must be done first
197:
198: if (isSink())
199: // the definition of the cut set is that without those nodes
200: // you can't reach from soruce to sink
201: return false;
202:
203: if (!visited.add(this ))
204: return true;
205:
206: if (this .cc == cc)
207: return true;
208:
209: for (Element next : foreEdges) {
210: if (!next.checkCutSet(cc, visited))
211: // we've found a path to the sink
212: return false;
213: }
214:
215: return true;
216: }
217: }
|