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.Label;
32import org.antlr.analysis.NFAState;
33import org.antlr.analysis.RuleClosureTransition;
34import org.antlr.analysis.Transition;
35import org.antlr.misc.IntervalSet;
36import org.antlr.misc.Utils;
37
38import java.io.BufferedReader;
39import java.io.FileReader;
40import java.util.ArrayList;
41import java.util.List;
42import java.util.Random;
43import java.util.Stack;
44
45/** Generate a random phrase given a grammar.
46 *  Usage:
47 *     java org.antlr.tool.RandomPhrase grammarFile.g startRule [seed]
48 *
49 *  For example:
50 *     java org.antlr.tool.RandomPhrase simple.g program 342
51 *
52 *  The seed acts like a unique identifier so you can get the same random
53 *  phrase back during unit testing, for example.
54 *
55 *  If you do not specify a seed then the current time in milliseconds is used
56 *  guaranteeing that you'll never see that seed again.
57 *
58 *  NOTE: this does not work well for large grammars...it tends to recurse
59 *  too much and build really long strings.  I need throttle control; later.
60 */
61public class RandomPhrase {
62	public static final boolean debug = false;
63
64	protected static Random random;
65
66	/** an experimental method to generate random phrases for a given
67	 *  grammar given a start rule.  Return a list of token types.
68	 */
69	protected static void randomPhrase(Grammar g, List<Integer> tokenTypes, String startRule) {
70		NFAState state = g.getRuleStartState(startRule);
71		NFAState stopState = g.getRuleStopState(startRule);
72
73		Stack ruleInvocationStack = new Stack();
74		while ( true ) {
75			if ( state==stopState && ruleInvocationStack.size()==0 ) {
76				break;
77			}
78			if ( debug ) System.out.println("state "+state);
79			if ( state.getNumberOfTransitions()==0 ) {
80				if ( debug ) System.out.println("dangling state: "+state);
81				return;
82			}
83			// end of rule node
84			if ( state.isAcceptState() ) {
85				NFAState invokingState = (NFAState)ruleInvocationStack.pop();
86				if ( debug ) System.out.println("pop invoking state "+invokingState);
87				//System.out.println("leave "+state.enclosingRule.name);
88				RuleClosureTransition invokingTransition =
89					(RuleClosureTransition)invokingState.transition[0];
90				// move to node after state that invoked this rule
91				state = invokingTransition.followState;
92				continue;
93			}
94			if ( state.getNumberOfTransitions()==1 ) {
95				// no branching, just take this path
96				Transition t0 = state.transition[0];
97				if ( t0 instanceof RuleClosureTransition ) {
98					ruleInvocationStack.push(state);
99					if ( debug ) System.out.println("push state "+state);
100					//System.out.println("call "+((RuleClosureTransition)t0).rule.name);
101					//System.out.println("stack depth="+ruleInvocationStack.size());
102				}
103				else if ( t0.label.isSet() || t0.label.isAtom() ) {
104					tokenTypes.add( getTokenType(t0.label) );
105				}
106				state = (NFAState)t0.target;
107				continue;
108			}
109
110			int decisionNumber = state.getDecisionNumber();
111			if ( decisionNumber==0 ) {
112				System.out.println("weird: no decision number but a choice node");
113				continue;
114			}
115			// decision point, pick ith alternative randomly
116			int n = g.getNumberOfAltsForDecisionNFA(state);
117			int randomAlt = random.nextInt(n) + 1;
118			if ( debug ) System.out.println("randomAlt="+randomAlt);
119			NFAState altStartState =
120				g.getNFAStateForAltOfDecision(state, randomAlt);
121			Transition t = altStartState.transition[0];
122			state = (NFAState)t.target;
123		}
124	}
125
126	protected static Integer getTokenType(Label label) {
127		if ( label.isSet() ) {
128			// pick random element of set
129			IntervalSet typeSet = (IntervalSet)label.getSet();
130			int randomIndex = random.nextInt(typeSet.size());
131			return typeSet.get(randomIndex);
132		}
133		else {
134			return Utils.integer(label.getAtom());
135		}
136		//System.out.println(t0.label.toString(g));
137	}
138
139	/** Used to generate random strings */
140	public static void main(String[] args) {
141		if ( args.length < 2 ) {
142			System.err.println("usage: java org.antlr.tool.RandomPhrase grammarfile startrule");
143			return;
144		}
145		String grammarFileName = args[0];
146		String startRule = args[1];
147		long seed = System.currentTimeMillis(); // use random seed unless spec.
148		if ( args.length==3 ) {
149			String seedStr = args[2];
150			seed = Long.parseLong(seedStr);
151		}
152		try {
153			random = new Random(seed);
154
155			CompositeGrammar composite = new CompositeGrammar();
156			Tool tool = new Tool();
157			Grammar parser = new Grammar(tool, grammarFileName, composite);
158			composite.setDelegationRoot(parser);
159
160			FileReader fr = new FileReader(grammarFileName);
161			BufferedReader br = new BufferedReader(fr);
162			parser.parseAndBuildAST(br);
163			br.close();
164
165			parser.composite.assignTokenTypes();
166			parser.composite.defineGrammarSymbols();
167			parser.composite.createNFAs();
168
169			List leftRecursiveRules = parser.checkAllRulesForLeftRecursion();
170			if ( leftRecursiveRules.size()>0 ) {
171				return;
172			}
173
174			if ( parser.getRule(startRule)==null ) {
175				System.out.println("undefined start rule "+startRule);
176				return;
177			}
178
179			String lexerGrammarText = parser.getLexerGrammar();
180			Grammar lexer = new Grammar(tool);
181			lexer.importTokenVocabulary(parser);
182			lexer.fileName = grammarFileName;
183			if ( lexerGrammarText!=null ) {
184				lexer.setGrammarContent(lexerGrammarText);
185			}
186			else {
187				System.err.println("no lexer grammar found in "+grammarFileName);
188			}
189			lexer.buildNFA();
190			leftRecursiveRules = lexer.checkAllRulesForLeftRecursion();
191			if ( leftRecursiveRules.size()>0 ) {
192				return;
193			}
194			//System.out.println("lexer:\n"+lexer);
195
196			List<Integer> tokenTypes = new ArrayList<Integer>(100);
197			randomPhrase(parser, tokenTypes, startRule);
198			System.out.println("token types="+tokenTypes);
199			for (int i = 0; i < tokenTypes.size(); i++) {
200				Integer ttypeI = (Integer) tokenTypes.get(i);
201				int ttype = ttypeI.intValue();
202				String ttypeDisplayName = parser.getTokenDisplayName(ttype);
203				if ( Character.isUpperCase(ttypeDisplayName.charAt(0)) ) {
204					List<Integer> charsInToken = new ArrayList<Integer>(10);
205					randomPhrase(lexer, charsInToken, ttypeDisplayName);
206					System.out.print(" ");
207					for (int j = 0; j < charsInToken.size(); j++) {
208						java.lang.Integer cI = (java.lang.Integer) charsInToken.get(j);
209						System.out.print((char)cI.intValue());
210					}
211				}
212				else { // it's a literal
213					String literal =
214						ttypeDisplayName.substring(1,ttypeDisplayName.length()-1);
215					System.out.print(" "+literal);
216				}
217			}
218			System.out.println();
219		}
220		catch (Error er) {
221			System.err.println("Error walking "+grammarFileName+" rule "+startRule+" seed "+seed);
222			er.printStackTrace(System.err);
223		}
224		catch (Exception e) {
225			System.err.println("Exception walking "+grammarFileName+" rule "+startRule+" seed "+seed);
226			e.printStackTrace(System.err);
227		}
228	}
229}
230