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.analysis.DFA;
31import org.antlr.grammar.v3.ANTLRParser;
32import org.antlr.misc.Utils;
33import org.antlr.runtime.misc.Stats;
34
35import java.lang.reflect.Field;
36import java.util.*;
37
38public class GrammarReport {
39	/** Because I may change the stats, I need to track version for later
40	 *  computations to be consistent.
41	 */
42	public static final String Version = "5";
43	public static final String GRAMMAR_STATS_FILENAME = "grammar.stats";
44
45	public static class ReportData {
46		String version;
47		String gname;
48		String gtype;
49		String language;
50		int numRules;
51		int numOuterProductions;
52		int numberOfDecisionsInRealRules;
53		int numberOfDecisions;
54		int numberOfCyclicDecisions;
55		int numberOfFixedKDecisions;
56		int numLL1;
57		int mink;
58		int maxk;
59		double avgk;
60		int numTokens;
61		long DFACreationWallClockTimeInMS;
62		int numberOfSemanticPredicates;
63		int numberOfManualLookaheadOptions; // TODO: verify
64		int numNonLLStarDecisions;
65		int numNondeterministicDecisions;
66		int numNondeterministicDecisionNumbersResolvedWithPredicates;
67		int errors;
68		int warnings;
69		int infos;
70		//int num_synpreds;
71		int blocksWithSynPreds;
72		int decisionsWhoseDFAsUsesSynPreds;
73		int blocksWithSemPreds;
74		int decisionsWhoseDFAsUsesSemPreds;
75		String output;
76		String grammarLevelk;
77		String grammarLevelBacktrack;
78	}
79
80	public static final String newline = System.getProperty("line.separator");
81
82	public Grammar grammar;
83
84	public GrammarReport(Grammar grammar) {
85		this.grammar = grammar;
86	}
87
88	public static ReportData getReportData(Grammar g) {
89		ReportData data = new ReportData();
90		data.version = Version;
91		data.gname = g.name;
92
93		data.gtype = g.getGrammarTypeString();
94
95		data.language = (String) g.getOption("language");
96		data.output = (String) g.getOption("output");
97		if ( data.output==null ) {
98			data.output = "none";
99		}
100
101		String k = (String) g.getOption("k");
102		if ( k==null ) {
103			k = "none";
104		}
105		data.grammarLevelk = k;
106
107		String backtrack = (String) g.getOption("backtrack");
108		if ( backtrack==null ) {
109			backtrack = "false";
110		}
111		data.grammarLevelBacktrack = backtrack;
112
113		int totalNonSynPredProductions = 0;
114		int totalNonSynPredRules = 0;
115		Collection rules = g.getRules();
116		for (Iterator it = rules.iterator(); it.hasNext();) {
117			Rule r = (Rule) it.next();
118			if ( !r.name.toUpperCase()
119				.startsWith(Grammar.SYNPRED_RULE_PREFIX.toUpperCase()) )
120			{
121				totalNonSynPredProductions += r.numberOfAlts;
122				totalNonSynPredRules++;
123			}
124		}
125
126		data.numRules = totalNonSynPredRules;
127		data.numOuterProductions = totalNonSynPredProductions;
128
129		int numACyclicDecisions =
130			g.getNumberOfDecisions()- g.getNumberOfCyclicDecisions();
131		List<Integer> depths = new ArrayList<Integer>();
132		int[] acyclicDFAStates = new int[numACyclicDecisions];
133		int[] cyclicDFAStates = new int[g.getNumberOfCyclicDecisions()];
134		int acyclicIndex = 0;
135		int cyclicIndex = 0;
136		int numLL1 = 0;
137		int blocksWithSynPreds = 0;
138		int dfaWithSynPred = 0;
139		int numDecisions = 0;
140		int numCyclicDecisions = 0;
141		for (int i=1; i<= g.getNumberOfDecisions(); i++) {
142			Grammar.Decision d = g.getDecision(i);
143			if( d.dfa==null ) {
144				//System.out.println("dec "+d.decision+" has no AST");
145				continue;
146			}
147			Rule r = d.dfa.decisionNFAStartState.enclosingRule;
148			if ( r.name.toUpperCase()
149				.startsWith(Grammar.SYNPRED_RULE_PREFIX.toUpperCase()) )
150			{
151				//System.out.println("dec "+d.decision+" is a synpred");
152				continue;
153			}
154
155			numDecisions++;
156			if ( blockHasSynPred(d.blockAST) ) blocksWithSynPreds++;
157			//if ( g.decisionsWhoseDFAsUsesSynPreds.contains(d.dfa) ) dfaWithSynPred++;
158			if ( d.dfa.hasSynPred() ) dfaWithSynPred++;
159
160//			NFAState decisionStartState = grammar.getDecisionNFAStartState(d.decision);
161//			int nalts = grammar.getNumberOfAltsForDecisionNFA(decisionStartState);
162//			for (int alt = 1; alt <= nalts; alt++) {
163//				int walkAlt =
164//					decisionStartState.translateDisplayAltToWalkAlt(alt);
165//				NFAState altLeftEdge = grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt);
166//			}
167//			int nalts = grammar.getNumberOfAltsForDecisionNFA(d.dfa.decisionNFAStartState);
168//			for (int a=1; a<nalts; a++) {
169//				NFAState altStart =
170//					grammar.getNFAStateForAltOfDecision(d.dfa.decisionNFAStartState, a);
171//			}
172			if ( !d.dfa.isCyclic() ) {
173				if ( d.dfa.isClassicDFA() ) {
174					int maxk = d.dfa.getMaxLookaheadDepth();
175					//System.out.println("decision "+d.dfa.decisionNumber+" k="+maxk);
176					if ( maxk==1 ) numLL1++;
177					depths.add( maxk );
178				}
179				else {
180					acyclicDFAStates[acyclicIndex] = d.dfa.getNumberOfStates();
181					acyclicIndex++;
182				}
183			}
184			else {
185				//System.out.println("CYCLIC decision "+d.dfa.decisionNumber);
186				numCyclicDecisions++;
187				cyclicDFAStates[cyclicIndex] = d.dfa.getNumberOfStates();
188				cyclicIndex++;
189			}
190		}
191
192		data.numLL1 = numLL1;
193		data.numberOfFixedKDecisions = depths.size();
194		data.mink = Stats.min(depths);
195		data.maxk = Stats.max(depths);
196		data.avgk = Stats.avg(depths);
197
198		data.numberOfDecisionsInRealRules = numDecisions;
199		data.numberOfDecisions = g.getNumberOfDecisions();
200		data.numberOfCyclicDecisions = numCyclicDecisions;
201
202//		Map synpreds = grammar.getSyntacticPredicates();
203//		int num_synpreds = synpreds!=null ? synpreds.size() : 0;
204//		data.num_synpreds = num_synpreds;
205		data.blocksWithSynPreds = blocksWithSynPreds;
206		data.decisionsWhoseDFAsUsesSynPreds = dfaWithSynPred;
207
208//
209//		data. = Stats.stddev(depths);
210//
211//		data. = Stats.min(acyclicDFAStates);
212//
213//		data. = Stats.max(acyclicDFAStates);
214//
215//		data. = Stats.avg(acyclicDFAStates);
216//
217//		data. = Stats.stddev(acyclicDFAStates);
218//
219//		data. = Stats.sum(acyclicDFAStates);
220//
221//		data. = Stats.min(cyclicDFAStates);
222//
223//		data. = Stats.max(cyclicDFAStates);
224//
225//		data. = Stats.avg(cyclicDFAStates);
226//
227//		data. = Stats.stddev(cyclicDFAStates);
228//
229//		data. = Stats.sum(cyclicDFAStates);
230
231		data.numTokens = g.getTokenTypes().size();
232
233		data.DFACreationWallClockTimeInMS = g.DFACreationWallClockTimeInMS;
234
235		// includes true ones and preds in synpreds I think; strip out.
236		data.numberOfSemanticPredicates = g.numberOfSemanticPredicates;
237
238		data.numberOfManualLookaheadOptions = g.numberOfManualLookaheadOptions;
239
240		data.numNonLLStarDecisions = g.numNonLLStar;
241		data.numNondeterministicDecisions = g.setOfNondeterministicDecisionNumbers.size();
242		data.numNondeterministicDecisionNumbersResolvedWithPredicates =
243			g.setOfNondeterministicDecisionNumbersResolvedWithPredicates.size();
244
245		data.errors = ErrorManager.getErrorState().errors;
246		data.warnings = ErrorManager.getErrorState().warnings;
247		data.infos = ErrorManager.getErrorState().infos;
248
249		data.blocksWithSemPreds = g.blocksWithSemPreds.size();
250
251		data.decisionsWhoseDFAsUsesSemPreds = g.decisionsWhoseDFAsUsesSemPreds.size();
252
253		return data;
254	}
255
256	/** Create a single-line stats report about this grammar suitable to
257	 *  send to the notify page at antlr.org
258	 */
259	public String toNotifyString() {
260		StringBuffer buf = new StringBuffer();
261		ReportData data = getReportData(grammar);
262		Field[] fields = ReportData.class.getDeclaredFields();
263		int i = 0;
264		for (Field f : fields) {
265			try {
266				Object v = f.get(data);
267				String s = v!=null ? v.toString() : "null";
268				if (i>0) buf.append('\t');
269				buf.append(s);
270			}
271			catch (Exception e) {
272				ErrorManager.internalError("Can't get data", e);
273			}
274			i++;
275		}
276		return buf.toString();
277	}
278
279	public String getBacktrackingReport() {
280		StringBuffer buf = new StringBuffer();
281		buf.append("Backtracking report:");
282		buf.append(newline);
283		buf.append("Number of decisions that backtrack: ");
284		buf.append(grammar.decisionsWhoseDFAsUsesSynPreds.size());
285		buf.append(newline);
286		buf.append(getDFALocations(grammar.decisionsWhoseDFAsUsesSynPreds));
287		return buf.toString();
288	}
289
290	protected String getDFALocations(Set dfas) {
291		Set decisions = new HashSet();
292		StringBuffer buf = new StringBuffer();
293		Iterator it = dfas.iterator();
294		while ( it.hasNext() ) {
295			DFA dfa = (DFA) it.next();
296			// if we aborted a DFA and redid with k=1, the backtrackin
297			if ( decisions.contains(Utils.integer(dfa.decisionNumber)) ) {
298				continue;
299			}
300			decisions.add(Utils.integer(dfa.decisionNumber));
301			buf.append("Rule ");
302			buf.append(dfa.decisionNFAStartState.enclosingRule.name);
303			buf.append(" decision ");
304			buf.append(dfa.decisionNumber);
305			buf.append(" location ");
306			GrammarAST decisionAST =
307				dfa.decisionNFAStartState.associatedASTNode;
308			buf.append(decisionAST.getLine());
309			buf.append(":");
310			buf.append(decisionAST.getCharPositionInLine());
311			buf.append(newline);
312		}
313		return buf.toString();
314	}
315
316	/** Given a stats line suitable for sending to the antlr.org site,
317	 *  return a human-readable version.  Return null if there is a
318	 *  problem with the data.
319	 */
320	public String toString() {
321		return toString(toNotifyString());
322	}
323
324	protected static ReportData decodeReportData(String dataS) {
325		ReportData data = new ReportData();
326		StringTokenizer st = new StringTokenizer(dataS, "\t");
327		Field[] fields = ReportData.class.getDeclaredFields();
328		for (Field f : fields) {
329			String v = st.nextToken();
330			try {
331				if ( f.getType() == String.class ) {
332					f.set(data, v);
333				}
334				else if ( f.getType() == double.class ) {
335					f.set(data, Double.valueOf(v));
336				}
337				else {
338					f.set(data, Integer.valueOf(v));
339				}
340			}
341			catch (Exception e) {
342				ErrorManager.internalError("Can't get data", e);
343			}
344		}
345		return data;
346	}
347
348	public static String toString(String notifyDataLine) {
349		ReportData data = decodeReportData(notifyDataLine);
350		if ( data ==null ) {
351			return null;
352		}
353		StringBuffer buf = new StringBuffer();
354		buf.append("ANTLR Grammar Report; Stats Version ");
355		buf.append(data.version);
356		buf.append('\n');
357		buf.append("Grammar: ");
358		buf.append(data.gname);
359		buf.append('\n');
360		buf.append("Type: ");
361		buf.append(data.gtype);
362		buf.append('\n');
363		buf.append("Target language: ");
364		buf.append(data.language);
365		buf.append('\n');
366		buf.append("Output: ");
367		buf.append(data.output);
368		buf.append('\n');
369		buf.append("Grammar option k: ");
370		buf.append(data.grammarLevelk);
371		buf.append('\n');
372		buf.append("Grammar option backtrack: ");
373		buf.append(data.grammarLevelBacktrack);
374		buf.append('\n');
375		buf.append("Rules: ");
376		buf.append(data.numRules);
377		buf.append('\n');
378		buf.append("Outer productions: ");
379		buf.append(data.numOuterProductions);
380		buf.append('\n');
381		buf.append("Decisions: ");
382		buf.append(data.numberOfDecisions);
383		buf.append('\n');
384		buf.append("Decisions (ignoring decisions in synpreds): ");
385		buf.append(data.numberOfDecisionsInRealRules);
386		buf.append('\n');
387		buf.append("Fixed k DFA decisions: ");
388		buf.append(data.numberOfFixedKDecisions);
389		buf.append('\n');
390		buf.append("Cyclic DFA decisions: ");
391		buf.append(data.numberOfCyclicDecisions);
392		buf.append('\n');
393		buf.append("LL(1) decisions: "); buf.append(data.numLL1);
394		buf.append('\n');
395		buf.append("Min fixed k: "); buf.append(data.mink);
396		buf.append('\n');
397		buf.append("Max fixed k: "); buf.append(data.maxk);
398		buf.append('\n');
399		buf.append("Average fixed k: "); buf.append(data.avgk);
400		buf.append('\n');
401//		buf.append("Standard deviation of fixed k: "); buf.append(fields[12]);
402//		buf.append('\n');
403//		buf.append("Min acyclic DFA states: "); buf.append(fields[13]);
404//		buf.append('\n');
405//		buf.append("Max acyclic DFA states: "); buf.append(fields[14]);
406//		buf.append('\n');
407//		buf.append("Average acyclic DFA states: "); buf.append(fields[15]);
408//		buf.append('\n');
409//		buf.append("Standard deviation of acyclic DFA states: "); buf.append(fields[16]);
410//		buf.append('\n');
411//		buf.append("Total acyclic DFA states: "); buf.append(fields[17]);
412//		buf.append('\n');
413//		buf.append("Min cyclic DFA states: "); buf.append(fields[18]);
414//		buf.append('\n');
415//		buf.append("Max cyclic DFA states: "); buf.append(fields[19]);
416//		buf.append('\n');
417//		buf.append("Average cyclic DFA states: "); buf.append(fields[20]);
418//		buf.append('\n');
419//		buf.append("Standard deviation of cyclic DFA states: "); buf.append(fields[21]);
420//		buf.append('\n');
421//		buf.append("Total cyclic DFA states: "); buf.append(fields[22]);
422//		buf.append('\n');
423		buf.append("DFA creation time in ms: ");
424		buf.append(data.DFACreationWallClockTimeInMS);
425		buf.append('\n');
426
427//		buf.append("Number of syntactic predicates available (including synpred rules): ");
428//		buf.append(data.num_synpreds);
429//		buf.append('\n');
430		buf.append("Decisions with available syntactic predicates (ignoring synpred rules): ");
431		buf.append(data.blocksWithSynPreds);
432		buf.append('\n');
433		buf.append("Decision DFAs using syntactic predicates (ignoring synpred rules): ");
434		buf.append(data.decisionsWhoseDFAsUsesSynPreds);
435		buf.append('\n');
436
437		buf.append("Number of semantic predicates found: ");
438		buf.append(data.numberOfSemanticPredicates);
439		buf.append('\n');
440		buf.append("Decisions with semantic predicates: ");
441		buf.append(data.blocksWithSemPreds);
442		buf.append('\n');
443		buf.append("Decision DFAs using semantic predicates: ");
444		buf.append(data.decisionsWhoseDFAsUsesSemPreds);
445		buf.append('\n');
446
447		buf.append("Number of (likely) non-LL(*) decisions: ");
448		buf.append(data.numNonLLStarDecisions);
449		buf.append('\n');
450		buf.append("Number of nondeterministic decisions: ");
451		buf.append(data.numNondeterministicDecisions);
452		buf.append('\n');
453		buf.append("Number of nondeterministic decisions resolved with predicates: ");
454		buf.append(data.numNondeterministicDecisionNumbersResolvedWithPredicates);
455		buf.append('\n');
456
457		buf.append("Number of manual or forced fixed lookahead k=value options: ");
458		buf.append(data.numberOfManualLookaheadOptions);
459		buf.append('\n');
460
461		buf.append("Vocabulary size: ");
462		buf.append(data.numTokens);
463		buf.append('\n');
464		buf.append("Number of errors: ");
465		buf.append(data.errors);
466		buf.append('\n');
467		buf.append("Number of warnings: ");
468		buf.append(data.warnings);
469		buf.append('\n');
470		buf.append("Number of infos: ");
471		buf.append(data.infos);
472		buf.append('\n');
473		return buf.toString();
474	}
475
476	public static boolean blockHasSynPred(GrammarAST blockAST) {
477		GrammarAST c1 = blockAST.findFirstType(ANTLRParser.SYN_SEMPRED);
478		GrammarAST c2 = blockAST.findFirstType(ANTLRParser.BACKTRACK_SEMPRED);
479		if ( c1!=null || c2!=null ) return true;
480//		System.out.println(blockAST.enclosingRuleName+
481//						   " "+blockAST.getLine()+":"+blockAST.getColumn()+" no preds AST="+blockAST.toStringTree());
482		return false;
483	}
484
485}
486