KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > antlr > works > visualization > graphics > graph > GGraphGroup


1 /*
2
3 [The "BSD licence"]
4 Copyright (c) 2005 Jean Bovet
5 All rights reserved.
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions
9 are met:
10
11 1. Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 2. Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
16 3. The name of the author may not be used to endorse or promote products
17 derived from this software without specific prior written permission.
18
19 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 */

31
32 package org.antlr.works.visualization.graphics.graph;
33
34 import org.antlr.analysis.NFAState;
35 import org.antlr.works.visualization.fa.FAState;
36 import org.antlr.works.visualization.fa.FATransition;
37 import org.antlr.works.visualization.graphics.GContext;
38 import org.antlr.works.visualization.graphics.path.GPath;
39 import org.antlr.works.visualization.graphics.path.GPathElement;
40 import org.antlr.works.visualization.graphics.path.GPathGroup;
41 import org.antlr.works.visualization.graphics.primitive.GDimension;
42 import org.antlr.works.visualization.graphics.shape.GNode;
43 import org.antlr.works.visualization.skin.syntaxdiagram.SDSkin;
44
45 import java.awt.*;
46 import java.util.ArrayList JavaDoc;
47 import java.util.List JavaDoc;
48 import java.util.Map JavaDoc;
49
50 public class GGraphGroup extends GGraphAbstract {
51
52     public static final int TITLE_OFFSET = 100;
53
54     public GDimension dimension = new GDimension();
55     public List JavaDoc<GGraph> graphs = new ArrayList JavaDoc<GGraph>();
56     public GPathGroup pathGroup = new GPathGroup();
57
58     protected GContext defaultContext;
59
60     public GGraphGroup() {
61         // The default context is used to evaluate the position of certain objects in addPath()
62
// because position requires a context to be evaluated ;-)
63
defaultContext = new GContext();
64         defaultContext.setSkin(new SDSkin());
65     }
66
67     public void setEnable(boolean flag) {
68         pathGroup.setEnable(flag);
69     }
70
71     public void setContext(GContext context) {
72         super.setContext(context);
73         for (GGraph graph : graphs) {
74             graph.setContext(context);
75         }
76         pathGroup.setContext(context);
77     }
78
79     public void add(GGraph graph) {
80         dimension.maxWidth(graph.dimension.width);
81         dimension.addUp(graph.dimension.up);
82         dimension.addDown(graph.dimension.down);
83         if(graphs.size()>0)
84             dimension.addDown(GContext.LINE_SPACE);
85         graphs.add(graph);
86     }
87
88     public float getHeight() {
89         return getDimension().getPixelHeight(context);
90     }
91
92     public float getWidth() {
93         return getDimension().getPixelWidth(context)+TITLE_OFFSET;
94     }
95
96     protected int pathIndex;
97
98     public List JavaDoc<FATransition> getTransitionsMatchingSkippedStates(List JavaDoc<FATransition> candidates, List JavaDoc states) {
99         /** First convert the list of NFAStates to a list of Integer containing
100          * the state number
101          */

102         List JavaDoc statesNumbers = new ArrayList JavaDoc();
103         for(int i=0; i<states.size(); i++) {
104             statesNumbers.add((((NFAState) states.get(i)).stateNumber));
105         }
106
107         /** Select only the transitions that containing all the state numbers */
108         List JavaDoc<FATransition> newCandidates = new ArrayList JavaDoc<FATransition>();
109         for(int c=0; c<candidates.size(); c++) {
110             FATransition t = candidates.get(c);
111             if(t.skippedStates != null && t.skippedStates.containsAll(statesNumbers)) {
112                 newCandidates.add(t);
113             }
114         }
115
116         return newCandidates;
117     }
118
119     public FATransition getNodeTransitionToNextNonSkippedState(GNode node, List JavaDoc path) {
120         if(node == null)
121             return null;
122
123         List JavaDoc<FATransition> candidateTransitions = new ArrayList JavaDoc<FATransition>(node.state.transitions);
124         FATransition candidate = null;
125         int start = pathIndex;
126
127         loop:
128         for(; pathIndex < path.size(); pathIndex++) {
129             candidateTransitions = getTransitionsMatchingSkippedStates(candidateTransitions, path.subList(start, pathIndex+1));
130             switch(candidateTransitions.size()) {
131                 case 0: // No more transitions. Exit and use the candidate transition.
132
break loop;
133
134                 case 1:
135                     // The uniquely identified transition has been found.
136
// Continue to loop until all skipped states have been found.
137
candidate = candidateTransitions.get(0);
138                     break;
139
140                 default:
141                     // More than one transition candidates found. Look if any of these
142
// transitions's target state correspond to the next path state to avoid
143
// missing a transition: this can happen if a transition is a subset of
144
// the others (the next state of the path can return no transition at all)
145
if(pathIndex+1 < path.size()) {
146                         NFAState nextPathState = (NFAState) path.get(pathIndex+1);
147                         for(int i=0; i<candidateTransitions.size(); i++) {
148                             FATransition t = candidateTransitions.get(i);
149                             if(t.target.stateNumber == nextPathState.stateNumber) {
150                                 pathIndex++; // always points to the next element after the transition
151
return t;
152                             }
153                         }
154                     }
155                     break;
156             }
157         }
158
159         return candidate;
160     }
161
162     public void addNextElementInSameRule(List JavaDoc<GPathElement> elements, GNode node, GNode nextNode) {
163         elements.add(GPathElement.createElement(node));
164
165         // Use nextNode instead of nextState (previously in parameter) because nextState
166
// could be null if it was skipped during optimization. nextNode cannot be null.
167
FATransition t = node.state.getTransitionToStateNumber(nextNode.state.stateNumber);
168         if(t == null) {
169             // Probably a loop. In this case, the transition is located in the target state.
170
t = nextNode.state.getTransitionToStateNumber(node.state.stateNumber);
171             if(t == null) {
172                 // Still no transition found. This is a reference to the same rule (recursive)
173
elements.add(GPathElement.createLink(node, nextNode));
174             } else {
175                 // Add the loop transition to the path
176
elements.add(GPathElement.createElement(nextNode.getLink(t)));
177             }
178         } else {
179             // Add the transition to the path
180
elements.add(GPathElement.createElement(node.getLink(t)));
181         }
182     }
183
184     public void addNextElementInOtherRule(List JavaDoc<GPathElement> elements, GNode node, GNode externalNode, GNode nextNode, NFAState nextState) {
185         if(externalNode == null) {
186             // The external node is not specified. Try to find it.
187
if(node.state.getFirstTransition() == null) {
188                 // If the node contains no transition (probably if it is at the end of a rule), then
189
// ignore externalNode. We will draw only a link from node to nextNode.
190
} else {
191                 // Find the transition that points to the external rule ref
192
FATransition t = node.state.getTransitionToExternalStateRule(nextState.getEnclosingRule());
193                 if(t == null) {
194                     System.err.println("[GGraphGroup] No transition to external state "+nextState.stateNumber+"["+nextState.getEnclosingRule()+"] - using first transition by default");
195                     t = node.state.getFirstTransition();
196                 }
197                 externalNode = findNodeForStateNumber(t.target.stateNumber);
198             }
199         }
200
201         if(externalNode == null) {
202             // Add the link between node and nextNode, ignore externalNode because it doesn't exist
203
elements.add(GPathElement.createElement(node));
204             elements.add(GPathElement.createLink(node, nextNode));
205         } else {
206             elements.add(GPathElement.createElement(node));
207
208             // Add the link between node and externalNode.
209
FATransition t = node.state.getTransitionToStateNumber(externalNode.state.stateNumber);
210             elements.add(GPathElement.createElement(node.getLink(t)));
211             elements.add(GPathElement.createElement(externalNode));
212
213             // Add the link between externalNode and nextNode
214
elements.add(GPathElement.createLink(externalNode, nextNode));
215         }
216     }
217
218     public void addPath(List JavaDoc path, boolean disabled, Map JavaDoc<Integer JavaDoc,FAState> skippedStates) {
219         List JavaDoc<GPathElement> elements = new ArrayList JavaDoc<GPathElement>();
220
221         /** path contains a list of NFAState states (from ANTLR): they represent
222          * all the states along the path. The graphical representation of the NFA/SD
223          * does not necessarily contains all the states of the path because the representation
224          * can be simplified to remove all unecessary states.
225          * The problem here is to use the information stored in the transition of the
226          * graphical representation to figure out exactly which graphical node corresponds
227          * to the path.
228          */

229
230         /*System.out.println("***");
231         for (Iterator iterator = path.iterator(); iterator.hasNext();) {
232             NFAState state = (NFAState)iterator.next();
233             System.out.println(state+" - "+state.getEnclosingRule());
234         } */

235
236         NFAState state;
237         GNode node;
238         NFAState nextState = null;
239         GNode nextNode = null;
240         for(pathIndex = 0; pathIndex < path.size(); pathIndex++) {
241             if(pathIndex == 0) {
242                 nextState = (NFAState)path.get(pathIndex);
243                 nextNode = findNodeForStateNumber(nextState.stateNumber);
244                 if(nextNode == null) {
245                     // A path can start from anywhere in the graph. It might happen
246
// that the starting state of the path has been skipped by
247
// the optimization in FAFactory. We use the skippedStates mapping
248
// to find out what is the parent state of the skipped state.
249
FAState parentState = skippedStates.get(nextState.stateNumber);
250                     if(parentState == null) {
251                         System.err.println("[GGraphGroup] Starting path state "+nextState.stateNumber+"["+nextState.getEnclosingRule()+"] cannot be found in the graph");
252                         return;
253                     } else {
254                         nextNode = findNodeForStateNumber(parentState.stateNumber);
255                     }
256                 }
257                 continue;
258             } else {
259                 state = nextState;
260                 node = nextNode;
261             }
262
263             nextState = (NFAState)path.get(pathIndex);
264             nextNode = findNodeForStateNumber(nextState.stateNumber);
265
266             GNode externalNode = null;
267
268             if(nextNode == null) {
269                 // The state has probably been skipped during the graphical rendering.
270
// Find the next non-skipped state.
271
FATransition t = getNodeTransitionToNextNonSkippedState(node, path);
272                 if(t == null) {
273                     // No transition found. Look in the skipped states mapping because
274
// it might be possible that the next state is in another rule but
275
// cannot be found because it has been skipped.
276

277                     FAState parentState = skippedStates.get(nextState.stateNumber);
278                     if(parentState == null) {
279                         // OK. The node really does not exist. Continue by skipping it.
280
nextNode = node;
281                         continue;
282                     } else {
283                         nextNode = findNodeForStateNumber(parentState.stateNumber);
284                     }
285                 } else {
286                     // pathIndex can be out of range because getNodeTransitionToNextNonSkippedState()
287
// is incrementing it
288
if(pathIndex >= path.size()) {
289                         nextNode = findNodeForStateNumber(t.target.stateNumber);
290                     } else {
291                         nextState = (NFAState)path.get(pathIndex);
292
293                         if(t.target.stateNumber == nextState.stateNumber) {
294                             nextNode = findNodeForStateNumber(t.target.stateNumber);
295                         } else {
296                             // The only case that the target state of the transition if not
297
// the next state of the path is when the next state of the path
298
// is in another rule. In this case, the target state of the transition
299
// will contain a negative state number indicating an external rule reference:
300
// this external rule reference is added by AW during rendering and is not
301
// part of any ANTLR NFA.
302

303                             // This node is the node representing the external rule reference
304
// before jumping outside of the rule
305
externalNode = findNodeForStateNumber(t.target.stateNumber);
306
307                             // This node is the first node in the other rule
308
nextNode = findNodeForStateNumber(nextState.stateNumber);
309                         }
310                     }
311                 }
312             }
313
314             if(state == null || node == null || nextNode == null)
315                 continue;
316
317             if(state.getEnclosingRule().equals(nextState.getEnclosingRule()))
318                 addNextElementInSameRule(elements, node, nextNode);
319             else
320                 addNextElementInOtherRule(elements, node, externalNode, nextNode, nextState);
321         }
322
323         if(nextNode != null)
324             elements.add(GPathElement.createElement(nextNode));
325
326         pathGroup.addPath(new GPath(elements, disabled));
327     }
328
329     public void addUnreachableAlt(NFAState state, Integer JavaDoc alt) {
330         List JavaDoc<GPathElement> elements = new ArrayList JavaDoc<GPathElement>();
331
332         GNode node = findNodeForStateNumber(state.stateNumber);
333         if(node == null) {
334             System.err.println("[GGraphGroup] Decision state "+state.stateNumber+"["+state.getEnclosingRule()+"] cannot be found in the graph");
335             return;
336         }
337         List JavaDoc<FATransition> transitions = node.state.transitions;
338         int altNum = alt -1;
339
340         if(altNum >= transitions.size()) {
341             System.err.println("[GGraphGroup] Unreachable alt "+altNum+"["+state.getEnclosingRule()+"] is out of bounds: "+transitions.size());
342             return;
343         }
344
345         FATransition t = transitions.get(altNum);
346
347         elements.add(GPathElement.createElement(node));
348         elements.add(GPathElement.createElement(node.getLink(t)));
349
350         /** This path has to be visible but not selectable */
351         GPath path = new GPath(elements, true);
352         path.setVisible(true);
353         path.setSelectable(false);
354         pathGroup.addPath(path);
355     }
356
357     public GNode findNodeForStateNumber(int stateNumber) {
358         for (GGraph graph : graphs) {
359             GNode node = graph.findNodeForStateNumber(stateNumber);
360             if (node != null) {
361                 return node;
362             }
363         }
364         return null;
365     }
366
367     public GDimension getDimension() {
368         return dimension;
369     }
370
371     public void render(float ox, float oy) {
372         ox += TITLE_OFFSET;
373         for (int i = 0; i<graphs.size(); i++) {
374             GGraph graph = graphs.get(i);
375             graph.render(ox, oy);
376             if(i<graphs.size()-1)
377                 oy += graph.getHeight()+context.getPixelLineSpace();
378         }
379
380         setRendered(true);
381     }
382
383     public void draw() {
384         context.nodeColor = Color.black;
385         context.linkColor = Color.black;
386         context.setLineWidth(1);
387
388         for (int i = 0; i<graphs.size(); i++) {
389             GGraph graph = graphs.get(i);
390             graph.draw();
391             context.setColor(Color.black);
392             context.drawString(context.getRuleFont(), graph.name, TITLE_OFFSET-5, graph.offsetY, GContext.ALIGN_RIGHT);
393         }
394
395         pathGroup.draw();
396
397         if(context.drawdimension) {
398             context.setLineWidth(1);
399             context.setColor(Color.lightGray);
400             float width = getDimension().getPixelWidth(context);
401             float up = getDimension().getPixelUp(context);
402             float down = getDimension().getPixelDown(context);
403             if(up+down>0)
404                 context.drawRect(0, 0, width, up+down, false);
405         }
406     }
407
408 }
409
Popular Tags