001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common Development
008: * and Distribution License("CDDL") (collectively, the "License"). You
009: * may not use this file except in compliance with the License. You can obtain
010: * a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
011: * or glassfish/bootstrap/legal/LICENSE.txt. See the License for the specific
012: * language governing permissions and limitations under the License.
013: *
014: * When distributing the software, include this License Header Notice in each
015: * file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
016: * Sun designates this particular file as subject to the "Classpath" exception
017: * as provided by Sun in the GPL Version 2 section of the License file that
018: * accompanied this code. If applicable, add the following below the License
019: * Header, with the fields enclosed by brackets [] replaced by your own
020: * identifying information: "Portions Copyrighted [year]
021: * [name of copyright owner]"
022: *
023: * Contributor(s):
024: *
025: * If you wish your version of this file to be governed by only the CDDL or
026: * only the GPL Version 2, indicate your decision by adding "[Contributor]
027: * elects to include this software in this distribution under the [CDDL or GPL
028: * Version 2] license." If you don't indicate a single choice of license, a
029: * recipient has the option to distribute your version of this file under
030: * either the CDDL, the GPL Version 2 or to extend the choice of license to
031: * its licensees as provided above. However, if you add GPL Version 2 code
032: * and therefore, elected the GPL Version 2 license, then the option applies
033: * only if the new code is made subject to such option by the copyright
034: * holder.
035: */
036:
037: package com.sun.tools.xjc.reader.gbind;
038:
039: import java.util.Collections;
040: import java.util.Iterator;
041: import java.util.LinkedHashSet;
042: import java.util.List;
043: import java.util.Set;
044:
045: /**
046: * {@link Expression} that represents an alphabet of a regular language.
047: *
048: * <p>
049: * Since this package is about a regular expression over element declarations,
050: * this represents an XML element declaration (hence the name.)
051: *
052: * Element needs to be interned, meaning one {@link Element} per one tag name.
053: *
054: * <p>
055: * Implements {@link ElementSet} to represent a self.
056: *
057: * @author Kohsuke Kawaguchi
058: */
059: public abstract class Element extends Expression implements ElementSet {
060: /**
061: * Once we build a graph from {@link Expression},
062: * we represent an edge e1 -> e2 by {@code e1.foreEdges.contains(e2)}
063: * and {@code e2.backEdges.contains(e1)}.
064: */
065: final Set<Element> foreEdges = new LinkedHashSet<Element>();
066: final Set<Element> backEdges = new LinkedHashSet<Element>();
067:
068: /**
069: * Previous element in the DFS post-order traveral
070: * of the element graph.
071: *
072: * <p>
073: * We use {@code prevPostOrder==null} as a check if the element is visted in DFS,
074: * so this chain terminates by a self-reference, not by having null.
075: *
076: * Set in {@link #assignDfsPostOrder(Element)}
077: */
078: /*package*/Element prevPostOrder;
079:
080: /**
081: * {@link ConnectedComponent} to which this element belongs.
082: *
083: * Set in {@link #buildStronglyConnectedComponents(List<ConnectedComponent>)}
084: */
085: private ConnectedComponent cc;
086:
087: protected Element() {
088: }
089:
090: ElementSet lastSet() {
091: return this ;
092: }
093:
094: boolean isNullable() {
095: return false;
096: }
097:
098: /**
099: * True if this {@link Element} is {@link SourceNode}.
100: */
101: boolean isSource() {
102: return false;
103: }
104:
105: /**
106: * True if this {@link Element} is {@link SinkNode}.
107: */
108: boolean isSink() {
109: return false;
110: }
111:
112: void buildDAG(ElementSet incoming) {
113: incoming.addNext(this );
114: }
115:
116: public void addNext(Element element) {
117: foreEdges.add(element);
118: element.backEdges.add(this );
119: }
120:
121: public boolean contains(ElementSet rhs) {
122: return this == rhs || rhs == ElementSet.EMPTY_SET;
123: }
124:
125: /**
126: * Just to satisfy the {@link ElementSet} contract.
127: *
128: * @deprecated
129: * if you statically call this method, there's something wrong.
130: */
131: public Iterator<Element> iterator() {
132: return Collections.singleton(this ).iterator();
133: }
134:
135: /**
136: * Traverses the {@link Element} graph with DFS
137: * and set {@link #prevPostOrder}.
138: *
139: * Should be first invoked on the source node of the graph.
140: */
141: /*package*/Element assignDfsPostOrder(Element prev) {
142: if (prevPostOrder != null)
143: return prev; // already visited
144:
145: prevPostOrder = this ; // set a dummy value to prepare for cycles
146:
147: for (Element next : foreEdges) {
148: prev = next.assignDfsPostOrder(prev);
149: }
150: this .prevPostOrder = prev; // set to the real value
151: return this ;
152: }
153:
154: /**
155: * Builds a set of strongly connected components and puts them
156: * all into the given set.
157: */
158: public void buildStronglyConnectedComponents(
159: List<ConnectedComponent> ccs) {
160: for (Element cur = this ; cur != cur.prevPostOrder; cur = cur.prevPostOrder) {
161: if (cur.belongsToSCC())
162: continue;
163:
164: // start a new component
165: ConnectedComponent cc = new ConnectedComponent();
166: ccs.add(cc);
167:
168: cur.formConnectedComponent(cc);
169: }
170: }
171:
172: private boolean belongsToSCC() {
173: return cc != null || isSource() || isSink();
174: }
175:
176: /**
177: * Forms a strongly connected component by doing a reverse DFS.
178: */
179: private void formConnectedComponent(ConnectedComponent group) {
180: if (belongsToSCC())
181: return;
182:
183: this .cc = group;
184: group.add(this );
185: for (Element prev : backEdges)
186: prev.formConnectedComponent(group);
187: }
188:
189: public boolean hasSelfLoop() {
190: // if foreEdges have a loop, backEdges must have one. Or vice versa
191: assert foreEdges.contains(this ) == backEdges.contains(this );
192:
193: return foreEdges.contains(this );
194: }
195:
196: /**
197: * Checks if the given {@link ConnectedComponent} forms a cut-set
198: * of a graph.
199: *
200: * @param visited
201: * Used to keep track of visited nodes.
202: * @return
203: * true if it is indeed a cut-set. false if not.
204: */
205: /*package*/final boolean checkCutSet(ConnectedComponent cc,
206: Set<Element> visited) {
207: assert belongsToSCC(); // SCC discomposition must be done first
208:
209: if (isSink())
210: // the definition of the cut set is that without those nodes
211: // you can't reach from soruce to sink
212: return false;
213:
214: if (!visited.add(this ))
215: return true;
216:
217: if (this .cc == cc)
218: return true;
219:
220: for (Element next : foreEdges) {
221: if (!next.checkCutSet(cc, visited))
222: // we've found a path to the sink
223: return false;
224: }
225:
226: return true;
227: }
228: }
|