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