1/* 2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package com.sun.tools.internal.xjc.reader.gbind; 27 28import java.util.ArrayList; 29import java.util.Collections; 30import java.util.Iterator; 31import java.util.LinkedHashSet; 32import java.util.List; 33import java.util.Set; 34 35/** 36 * {@link Expression} that represents an alphabet of a regular language. 37 * 38 * <p> 39 * Since this package is about a regular expression over element declarations, 40 * this represents an XML element declaration (hence the name.) 41 * 42 * Element needs to be interned, meaning one {@link Element} per one tag name. 43 * 44 * <p> 45 * Implements {@link ElementSet} to represent a self. 46 * 47 * @author Kohsuke Kawaguchi 48 */ 49public abstract class Element extends Expression implements ElementSet { 50 /** 51 * Once we build a graph from {@link Expression}, 52 * we represent an edge e1 -> e2 by {@code e1.foreEdges.contains(e2)} 53 * and {@code e2.backEdges.contains(e1)}. 54 */ 55 final Set<Element> foreEdges = new LinkedHashSet<Element>(); 56 final Set<Element> backEdges = new LinkedHashSet<Element>(); 57 58 /** 59 * Previous element in the DFS post-order traveral 60 * of the element graph. 61 * 62 * <p> 63 * We use {@code prevPostOrder==null} as a check if the element is visted in DFS, 64 * so this chain terminates by a self-reference, not by having null. 65 * 66 * Set in {@link #assignDfsPostOrder(Element)} 67 */ 68 /*package*/ Element prevPostOrder; 69 70 /** 71 * {@link ConnectedComponent} to which this element belongs. 72 * 73 * Set in {@link #buildStronglyConnectedComponents(List<ConnectedComponent>)} 74 */ 75 private ConnectedComponent cc; 76 77 protected Element() { 78 } 79 80 ElementSet lastSet() { 81 return this; 82 } 83 84 boolean isNullable() { 85 return false; 86 } 87 88 /** 89 * True if this {@link Element} is {@link SourceNode}. 90 */ 91 boolean isSource() { 92 return false; 93 } 94 95 /** 96 * True if this {@link Element} is {@link SinkNode}. 97 */ 98 boolean isSink() { 99 return false; 100 } 101 102 void buildDAG(ElementSet incoming) { 103 incoming.addNext(this); 104 } 105 106 public void addNext(Element element) { 107 foreEdges.add(element); 108 element.backEdges.add(this); 109 } 110 111 public boolean contains(ElementSet rhs) { 112 return this==rhs || rhs==ElementSet.EMPTY_SET; 113 } 114 115 /** 116 * Just to satisfy the {@link ElementSet} contract. 117 * 118 * @deprecated 119 * if you statically call this method, there's something wrong. 120 */ 121 public Iterator<Element> iterator() { 122 return Collections.singleton(this).iterator(); 123 } 124 125 /** 126 * Traverses the {@link Element} graph with DFS 127 * and set {@link #prevPostOrder}. 128 * 129 * Should be first invoked on the source node of the graph. 130 */ 131 /*package*/ Element assignDfsPostOrder(Element prev) { 132 if(prevPostOrder!=null) 133 return prev; // already visited 134 135 prevPostOrder = this; // set a dummy value to prepare for cycles 136 137 for (Element next : foreEdges) { 138 prev = next.assignDfsPostOrder(prev); 139 } 140 this.prevPostOrder = prev; // set to the real value 141 return this; 142 } 143 144 /** 145 * Builds a set of strongly connected components and puts them 146 * all into the given set. 147 */ 148 public void buildStronglyConnectedComponents(List<ConnectedComponent> ccs) { 149 150 // store visited elements - loop detection 151 List<Element> visitedElements = new ArrayList<Element>(); 152 153 for(Element cur=this; cur!=cur.prevPostOrder; cur=cur.prevPostOrder) { 154 155 if(visitedElements.contains(cur)) { 156 // if I've already processed cur element, I'm in a loop 157 break; 158 } else { 159 visitedElements.add(cur); 160 } 161 162 if(cur.belongsToSCC()) 163 continue; 164 165 // start a new component 166 ConnectedComponent cc = new ConnectedComponent(); 167 ccs.add(cc); 168 169 cur.formConnectedComponent(cc); 170 } 171 } 172 173 private boolean belongsToSCC() { 174 return cc!=null || isSource() || isSink(); 175 } 176 177 /** 178 * Forms a strongly connected component by doing a reverse DFS. 179 */ 180 private void formConnectedComponent(ConnectedComponent group) { 181 if(belongsToSCC()) 182 return; 183 184 this.cc=group; 185 group.add(this); 186 for (Element prev : backEdges) 187 prev.formConnectedComponent(group); 188 } 189 190 public boolean hasSelfLoop() { 191 // if foreEdges have a loop, backEdges must have one. Or vice versa 192 assert foreEdges.contains(this)==backEdges.contains(this); 193 194 return foreEdges.contains(this); 195 } 196 197 /** 198 * Checks if the given {@link ConnectedComponent} forms a cut-set 199 * of a graph. 200 * 201 * @param visited 202 * Used to keep track of visited nodes. 203 * @return 204 * true if it is indeed a cut-set. false if not. 205 */ 206 /*package*/ final boolean checkCutSet(ConnectedComponent cc, 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} 229