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 */ 28 package org.antlr.tool; 29 30 import org.antlr.Tool; 31 import org.antlr.analysis.*; 32 import org.antlr.grammar.v3.ANTLRParser; 33 import org.antlr.misc.Utils; 34 import org.stringtemplate.v4.ST; 35 import org.stringtemplate.v4.STGroup; 36 import org.stringtemplate.v4.STGroupFile; 37 38 import java.util.*; 39 40 /** The DOT (part of graphviz) generation aspect. */ 41 public 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 {@code <attrname>} format */ 48 public static STGroup stlib = new STGroupFile("org/antlr/tool/templates/dot/dot.stg"); 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<Object> markedStates = null; 55 56 protected Grammar grammar; 57 58 /** This aspect is associated with a grammar */ DOTGenerator(Grammar 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 */ getDOT(State startState)67 public String getDOT(State startState) { 68 if ( startState==null ) { 69 return null; 70 } 71 // The output DOT graph for visualization 72 ST dot; 73 markedStates = new HashSet<Object>(); 74 if ( startState instanceof DFAState ) { 75 dot = stlib.getInstanceOf("dfa"); 76 dot.add("startState", 77 Utils.integer(startState.stateNumber)); 78 dot.add("useBox", 79 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.render(); 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 */ walkCreatingDFADOT(ST dot, DFAState s)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 = 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 */ walkRuleNFACreatingDOT(ST dot, State s)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; 207 for (int i = 0; i < s.getNumberOfTransitions(); i++) { 208 Transition edge = 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 */ getEdgeLabel(Transition edge)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).render() 303 +"}?"; 304 label += predsStr; 305 } 306 } 307 return label; 308 } 309 getStateLabel(State s)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 StringBuilder buf = new StringBuilder(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<Integer> alts = ((DFAState)s).getAltSet(); 327 if ( alts!=null ) { 328 buf.append("\\n"); 329 // separate alts 330 List<Integer> altList = new ArrayList<Integer>(); 331 altList.addAll(alts); 332 Collections.sort(altList); 333 Set<NFAConfiguration> configurations = ((DFAState) s).nfaConfigurations; 334 for (int altIndex = 0; altIndex < altList.size(); altIndex++) { 335 Integer altI = altList.get(altIndex); 336 int alt = altI; 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<NFAConfiguration> configsInAlt = new ArrayList<NFAConfiguration>(); 346 for (NFAConfiguration c : configurations) { 347 if ( c.alt!=alt ) continue; 348 configsInAlt.add(c); 349 } 350 int n = 0; 351 for (int cIndex = 0; cIndex < configsInAlt.size(); cIndex++) { 352 NFAConfiguration c = configsInAlt.get(cIndex); 353 n++; 354 buf.append(c.toString(false)); 355 if ( (cIndex+1)<configsInAlt.size() ) { 356 buf.append(", "); 357 } 358 if ( n%5==0 && (configsInAlt.size()-cIndex)>3 ) { 359 buf.append("\\n"); 360 } 361 } 362 } 363 } 364 } 365 stateLabel = buf.toString(); 366 } 367 if ( (s instanceof NFAState) && ((NFAState)s).isDecisionState() ) { 368 stateLabel = stateLabel+",d="+ 369 ((NFAState)s).getDecisionNumber(); 370 if ( ((NFAState)s).endOfBlockStateNumber!=State.INVALID_STATE_NUMBER ) { 371 stateLabel += ",eob="+((NFAState)s).endOfBlockStateNumber; 372 } 373 } 374 else if ( (s instanceof NFAState) && 375 ((NFAState)s).endOfBlockStateNumber!=State.INVALID_STATE_NUMBER) 376 { 377 NFAState n = ((NFAState)s); 378 stateLabel = stateLabel+",eob="+n.endOfBlockStateNumber; 379 } 380 else if ( s instanceof DFAState && ((DFAState)s).isAcceptState() ) { 381 stateLabel = stateLabel+ 382 "=>"+((DFAState)s).getUniquelyPredictedAlt(); 383 } 384 return '"'+stateLabel+'"'; 385 } 386 getArrowheadType()387 public String getArrowheadType() { 388 return arrowhead; 389 } 390 setArrowheadType(String arrowhead)391 public void setArrowheadType(String arrowhead) { 392 this.arrowhead = arrowhead; 393 } 394 getRankdir()395 public String getRankdir() { 396 return rankdir; 397 } 398 setRankdir(String rankdir)399 public void setRankdir(String rankdir) { 400 this.rankdir = rankdir; 401 } 402 } 403