1/* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28package org.antlr.tool; 29 30import org.antlr.Tool; 31import org.antlr.analysis.*; 32import org.antlr.grammar.v3.ANTLRParser; 33import org.antlr.misc.Utils; 34import org.stringtemplate.v4.ST; 35import org.stringtemplate.v4.STGroup; 36import org.stringtemplate.v4.STGroupDir; 37 38import java.util.*; 39 40/** The DOT (part of graphviz) generation aspect. */ 41public class DOTGenerator { 42 public static final boolean STRIP_NONREDUCED_STATES = false; 43 44 protected String arrowhead="normal"; 45 protected String rankdir="LR"; 46 47 /** Library of output templates; use <attrname> format */ 48 public static STGroup stlib = new STGroupDir("org/antlr/tool/templates/dot/dfa"); 49 50 /** To prevent infinite recursion when walking state machines, record 51 * which states we've visited. Make a new set every time you start 52 * walking in case you reuse this object. 53 */ 54 protected Set markedStates = null; 55 56 protected Grammar grammar; 57 58 /** This aspect is associated with a grammar */ 59 public DOTGenerator(Grammar grammar) { 60 this.grammar = grammar; 61 } 62 63 /** Return a String containing a DOT description that, when displayed, 64 * will show the incoming state machine visually. All nodes reachable 65 * from startState will be included. 66 */ 67 public String getDOT(State startState) { 68 if ( startState==null ) { 69 return null; 70 } 71 // The output DOT graph for visualization 72 ST dot = null; 73 markedStates = new HashSet(); 74 if ( startState instanceof DFAState ) { 75 dot = stlib.getInstanceOf("dfa"); 76 dot.add("startState", 77 Utils.integer(startState.stateNumber)); 78 dot.add("useBox", 79 Boolean.valueOf(Tool.internalOption_ShowNFAConfigsInDFA)); 80 walkCreatingDFADOT(dot, (DFAState)startState); 81 } 82 else { 83 dot = stlib.getInstanceOf("nfa"); 84 dot.add("startState", 85 Utils.integer(startState.stateNumber)); 86 walkRuleNFACreatingDOT(dot, startState); 87 } 88 dot.add("rankdir", rankdir); 89 return dot.toString(); 90 } 91 92 /** Return a String containing a DOT description that, when displayed, 93 * will show the incoming state machine visually. All nodes reachable 94 * from startState will be included. 95 public String getRuleNFADOT(State startState) { 96 // The output DOT graph for visualization 97 ST dot = stlib.getInstanceOf("nfa"); 98 99 markedStates = new HashSet(); 100 dot.add("startState", 101 Utils.integer(startState.stateNumber)); 102 walkRuleNFACreatingDOT(dot, startState); 103 return dot.toString(); 104 } 105 */ 106 107 /** Do a depth-first walk of the state machine graph and 108 * fill a DOT description template. Keep filling the 109 * states and edges attributes. 110 */ 111 protected void walkCreatingDFADOT(ST dot, 112 DFAState s) 113 { 114 if ( markedStates.contains(Utils.integer(s.stateNumber)) ) { 115 return; // already visited this node 116 } 117 118 markedStates.add(Utils.integer(s.stateNumber)); // mark this node as completed. 119 120 // first add this node 121 ST st; 122 if ( s.isAcceptState() ) { 123 st = stlib.getInstanceOf("stopstate"); 124 } 125 else { 126 st = stlib.getInstanceOf("state"); 127 } 128 st.add("name", getStateLabel(s)); 129 dot.add("states", st); 130 131 // make a DOT edge for each transition 132 for (int i = 0; i < s.getNumberOfTransitions(); i++) { 133 Transition edge = (Transition) s.transition(i); 134 /* 135 System.out.println("dfa "+s.dfa.decisionNumber+ 136 " edge from s"+s.stateNumber+" ["+i+"] of "+s.getNumberOfTransitions()); 137 */ 138 if ( STRIP_NONREDUCED_STATES ) { 139 if ( edge.target instanceof DFAState && 140 ((DFAState)edge.target).getAcceptStateReachable()!=DFA.REACHABLE_YES ) 141 { 142 continue; // don't generate nodes for terminal states 143 } 144 } 145 st = stlib.getInstanceOf("edge"); 146 st.add("label", getEdgeLabel(edge)); 147 st.add("src", getStateLabel(s)); 148 st.add("target", getStateLabel(edge.target)); 149 st.add("arrowhead", arrowhead); 150 dot.add("edges", st); 151 walkCreatingDFADOT(dot, (DFAState)edge.target); // keep walkin' 152 } 153 } 154 155 /** Do a depth-first walk of the state machine graph and 156 * fill a DOT description template. Keep filling the 157 * states and edges attributes. We know this is an NFA 158 * for a rule so don't traverse edges to other rules and 159 * don't go past rule end state. 160 */ 161 protected void walkRuleNFACreatingDOT(ST dot, 162 State s) 163 { 164 if ( markedStates.contains(s) ) { 165 return; // already visited this node 166 } 167 168 markedStates.add(s); // mark this node as completed. 169 170 // first add this node 171 ST stateST; 172 if ( s.isAcceptState() ) { 173 stateST = stlib.getInstanceOf("stopstate"); 174 } 175 else { 176 stateST = stlib.getInstanceOf("state"); 177 } 178 stateST.add("name", getStateLabel(s)); 179 dot.add("states", stateST); 180 181 if ( s.isAcceptState() ) { 182 return; // don't go past end of rule node to the follow states 183 } 184 185 // special case: if decision point, then line up the alt start states 186 // unless it's an end of block 187 if ( ((NFAState)s).isDecisionState() ) { 188 GrammarAST n = ((NFAState)s).associatedASTNode; 189 if ( n!=null && n.getType()!=ANTLRParser.EOB ) { 190 ST rankST = stlib.getInstanceOf("decision-rank"); 191 NFAState alt = (NFAState)s; 192 while ( alt!=null ) { 193 rankST.add("states", getStateLabel(alt)); 194 if ( alt.transition[1] !=null ) { 195 alt = (NFAState)alt.transition[1].target; 196 } 197 else { 198 alt=null; 199 } 200 } 201 dot.add("decisionRanks", rankST); 202 } 203 } 204 205 // make a DOT edge for each transition 206 ST edgeST = null; 207 for (int i = 0; i < s.getNumberOfTransitions(); i++) { 208 Transition edge = (Transition) s.transition(i); 209 if ( edge instanceof RuleClosureTransition ) { 210 RuleClosureTransition rr = ((RuleClosureTransition)edge); 211 // don't jump to other rules, but display edge to follow node 212 edgeST = stlib.getInstanceOf("edge"); 213 if ( rr.rule.grammar != grammar ) { 214 edgeST.add("label", "<" + rr.rule.grammar.name + "." + rr.rule.name + ">"); 215 } 216 else { 217 edgeST.add("label", "<" + rr.rule.name + ">"); 218 } 219 edgeST.add("src", getStateLabel(s)); 220 edgeST.add("target", getStateLabel(rr.followState)); 221 edgeST.add("arrowhead", arrowhead); 222 dot.add("edges", edgeST); 223 walkRuleNFACreatingDOT(dot, rr.followState); 224 continue; 225 } 226 if ( edge.isAction() ) { 227 edgeST = stlib.getInstanceOf("action-edge"); 228 } 229 else if ( edge.isEpsilon() ) { 230 edgeST = stlib.getInstanceOf("epsilon-edge"); 231 } 232 else { 233 edgeST = stlib.getInstanceOf("edge"); 234 } 235 edgeST.add("label", getEdgeLabel(edge)); 236 edgeST.add("src", getStateLabel(s)); 237 edgeST.add("target", getStateLabel(edge.target)); 238 edgeST.add("arrowhead", arrowhead); 239 dot.add("edges", edgeST); 240 walkRuleNFACreatingDOT(dot, edge.target); // keep walkin' 241 } 242 } 243 244 /* 245 public void writeDOTFilesForAllRuleNFAs() throws IOException { 246 Collection rules = grammar.getRules(); 247 for (Iterator itr = rules.iterator(); itr.hasNext();) { 248 Grammar.Rule r = (Grammar.Rule) itr.next(); 249 String ruleName = r.name; 250 writeDOTFile( 251 ruleName, 252 getRuleNFADOT(grammar.getRuleStartState(ruleName))); 253 } 254 } 255 */ 256 257 /* 258 public void writeDOTFilesForAllDecisionDFAs() throws IOException { 259 // for debugging, create a DOT file for each decision in 260 // a directory named for the grammar. 261 File grammarDir = new File(grammar.name+"_DFAs"); 262 grammarDir.mkdirs(); 263 List decisionList = grammar.getDecisionNFAStartStateList(); 264 if ( decisionList==null ) { 265 return; 266 } 267 int i = 1; 268 Iterator iter = decisionList.iterator(); 269 while (iter.hasNext()) { 270 NFAState decisionState = (NFAState)iter.next(); 271 DFA dfa = decisionState.getDecisionASTNode().getLookaheadDFA(); 272 if ( dfa!=null ) { 273 String dot = getDOT( dfa.startState ); 274 writeDOTFile(grammarDir+"/dec-"+i, dot); 275 } 276 i++; 277 } 278 } 279 */ 280 281 /** Fix edge strings so they print out in DOT properly; 282 * generate any gated predicates on edge too. 283 */ 284 protected String getEdgeLabel(Transition edge) { 285 String label = edge.label.toString(grammar); 286 label = Utils.replace(label,"\\", "\\\\"); 287 label = Utils.replace(label,"\"", "\\\""); 288 label = Utils.replace(label,"\n", "\\\\n"); 289 label = Utils.replace(label,"\r", ""); 290 if ( label.equals(Label.EPSILON_STR) ) { 291 label = "e"; 292 } 293 State target = edge.target; 294 if ( !edge.isSemanticPredicate() && target instanceof DFAState ) { 295 // look for gated predicates; don't add gated to simple sempred edges 296 SemanticContext preds = 297 ((DFAState)target).getGatedPredicatesInNFAConfigurations(); 298 if ( preds!=null ) { 299 String predsStr = ""; 300 predsStr = "&&{"+ 301 preds.genExpr(grammar.generator, 302 grammar.generator.getTemplates(), null).toString() 303 +"}?"; 304 label += predsStr; 305 } 306 } 307 return label; 308 } 309 310 protected String getStateLabel(State s) { 311 if ( s==null ) { 312 return "null"; 313 } 314 String stateLabel = String.valueOf(s.stateNumber); 315 if ( s instanceof DFAState ) { 316 StringBuffer buf = new StringBuffer(250); 317 buf.append('s'); 318 buf.append(s.stateNumber); 319 if ( Tool.internalOption_ShowNFAConfigsInDFA ) { 320 if ( s instanceof DFAState ) { 321 if ( ((DFAState)s).abortedDueToRecursionOverflow ) { 322 buf.append("\\n"); 323 buf.append("abortedDueToRecursionOverflow"); 324 } 325 } 326 Set alts = ((DFAState)s).getAltSet(); 327 if ( alts!=null ) { 328 buf.append("\\n"); 329 // separate alts 330 List altList = new ArrayList(); 331 altList.addAll(alts); 332 Collections.sort(altList); 333 Set configurations = ((DFAState) s).nfaConfigurations; 334 for (int altIndex = 0; altIndex < altList.size(); altIndex++) { 335 Integer altI = (Integer) altList.get(altIndex); 336 int alt = altI.intValue(); 337 if ( altIndex>0 ) { 338 buf.append("\\n"); 339 } 340 buf.append("alt"); 341 buf.append(alt); 342 buf.append(':'); 343 // get a list of configs for just this alt 344 // it will help us print better later 345 List configsInAlt = new ArrayList(); 346 for (Iterator it = configurations.iterator(); it.hasNext();) { 347 NFAConfiguration c = (NFAConfiguration) it.next(); 348 if ( c.alt!=alt ) continue; 349 configsInAlt.add(c); 350 } 351 int n = 0; 352 for (int cIndex = 0; cIndex < configsInAlt.size(); cIndex++) { 353 NFAConfiguration c = 354 (NFAConfiguration)configsInAlt.get(cIndex); 355 n++; 356 buf.append(c.toString(false)); 357 if ( (cIndex+1)<configsInAlt.size() ) { 358 buf.append(", "); 359 } 360 if ( n%5==0 && (configsInAlt.size()-cIndex)>3 ) { 361 buf.append("\\n"); 362 } 363 } 364 } 365 } 366 } 367 stateLabel = buf.toString(); 368 } 369 if ( (s instanceof NFAState) && ((NFAState)s).isDecisionState() ) { 370 stateLabel = stateLabel+",d="+ 371 ((NFAState)s).getDecisionNumber(); 372 if ( ((NFAState)s).endOfBlockStateNumber!=State.INVALID_STATE_NUMBER ) { 373 stateLabel += ",eob="+((NFAState)s).endOfBlockStateNumber; 374 } 375 } 376 else if ( (s instanceof NFAState) && 377 ((NFAState)s).endOfBlockStateNumber!=State.INVALID_STATE_NUMBER) 378 { 379 NFAState n = ((NFAState)s); 380 stateLabel = stateLabel+",eob="+n.endOfBlockStateNumber; 381 } 382 else if ( s instanceof DFAState && ((DFAState)s).isAcceptState() ) { 383 stateLabel = stateLabel+ 384 "=>"+((DFAState)s).getUniquelyPredictedAlt(); 385 } 386 return '"'+stateLabel+'"'; 387 } 388 389 public String getArrowheadType() { 390 return arrowhead; 391 } 392 393 public void setArrowheadType(String arrowhead) { 394 this.arrowhead = arrowhead; 395 } 396 397 public String getRankdir() { 398 return rankdir; 399 } 400 401 public void setRankdir(String rankdir) { 402 this.rankdir = rankdir; 403 } 404} 405