001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.runtime.debug;
029:
030: import org.antlr.runtime.*;
031: import org.antlr.runtime.misc.Stats;
032:
033: import java.util.*;
034: import java.io.IOException;
035:
036: /** Using the debug event interface, track what is happening in the parser
037: * and record statistics about the runtime.
038: */
039: public class Profiler extends BlankDebugEventListener {
040: /** Because I may change the stats, I need to track that for later
041: * computations to be consistent.
042: */
043: public static final String Version = "2";
044: public static final String RUNTIME_STATS_FILENAME = "runtime.stats";
045: public static final int NUM_RUNTIME_STATS = 29;
046:
047: public DebugParser parser = null;
048:
049: // working variables
050:
051: protected int ruleLevel = 0;
052: protected int decisionLevel = 0;
053: protected int maxLookaheadInCurrentDecision = 0;
054: protected CommonToken lastTokenConsumed = null;
055:
056: protected List lookaheadStack = new ArrayList();
057:
058: // stats variables
059:
060: public int numRuleInvocations = 0;
061: public int numGuessingRuleInvocations = 0;
062: public int maxRuleInvocationDepth = 0;
063: public int numFixedDecisions = 0;
064: public int numCyclicDecisions = 0;
065: public int numBacktrackDecisions = 0;
066: public int[] decisionMaxFixedLookaheads = new int[200]; // TODO: make List
067: public int[] decisionMaxCyclicLookaheads = new int[200];
068: public List decisionMaxSynPredLookaheads = new ArrayList();
069: public int numHiddenTokens = 0;
070: public int numCharsMatched = 0;
071: public int numHiddenCharsMatched = 0;
072: public int numSemanticPredicates = 0;
073: public int numSyntacticPredicates = 0;
074: protected int numberReportedErrors = 0;
075: public int numMemoizationCacheMisses = 0;
076: public int numMemoizationCacheHits = 0;
077: public int numMemoizationCacheEntries = 0;
078:
079: public Profiler() {
080: }
081:
082: public Profiler(DebugParser parser) {
083: this .parser = parser;
084: }
085:
086: public void enterRule(String ruleName) {
087: //System.out.println("enterRule "+ruleName);
088: ruleLevel++;
089: numRuleInvocations++;
090: if (ruleLevel > maxRuleInvocationDepth) {
091: maxRuleInvocationDepth = ruleLevel;
092: }
093:
094: }
095:
096: /** Track memoization; this is not part of standard debug interface
097: * but is triggered by profiling. Code gen inserts an override
098: * for this method in the recognizer, which triggers this method.
099: */
100: public void examineRuleMemoization(IntStream input, int ruleIndex,
101: String ruleName) {
102: //System.out.println("examine memo "+ruleName);
103: int stopIndex = parser.getRuleMemoization(ruleIndex, input
104: .index());
105: if (stopIndex == BaseRecognizer.MEMO_RULE_UNKNOWN) {
106: //System.out.println("rule "+ruleIndex+" missed @ "+input.index());
107: numMemoizationCacheMisses++;
108: numGuessingRuleInvocations++; // we'll have to enter
109: } else {
110: // regardless of rule success/failure, if in cache, we have a cache hit
111: //System.out.println("rule "+ruleIndex+" hit @ "+input.index());
112: numMemoizationCacheHits++;
113: }
114: }
115:
116: public void memoize(IntStream input, int ruleIndex,
117: int ruleStartIndex, String ruleName) {
118: // count how many entries go into table
119: //System.out.println("memoize "+ruleName);
120: numMemoizationCacheEntries++;
121: }
122:
123: public void exitRule(String ruleName) {
124: ruleLevel--;
125: }
126:
127: public void enterDecision(int decisionNumber) {
128: decisionLevel++;
129: int startingLookaheadIndex = parser.getTokenStream().index();
130: //System.out.println("enterDecision "+decisionNumber+" @ index "+startingLookaheadIndex);
131: lookaheadStack.add(new Integer(startingLookaheadIndex));
132: }
133:
134: public void exitDecision(int decisionNumber) {
135: //System.out.println("exitDecision "+decisionNumber);
136: // track how many of acyclic, cyclic here as we don't know what kind
137: // yet in enterDecision event.
138: if (parser.isCyclicDecision) {
139: numCyclicDecisions++;
140: } else {
141: numFixedDecisions++;
142: }
143: lookaheadStack.remove(lookaheadStack.size() - 1); // pop lookahead depth counter
144: decisionLevel--;
145: if (parser.isCyclicDecision) {
146: if (numCyclicDecisions >= decisionMaxCyclicLookaheads.length) {
147: int[] bigger = new int[decisionMaxCyclicLookaheads.length * 2];
148: System.arraycopy(decisionMaxCyclicLookaheads, 0,
149: bigger, 0, decisionMaxCyclicLookaheads.length);
150: decisionMaxCyclicLookaheads = bigger;
151: }
152: decisionMaxCyclicLookaheads[numCyclicDecisions - 1] = maxLookaheadInCurrentDecision;
153: } else {
154: if (numFixedDecisions >= decisionMaxFixedLookaheads.length) {
155: int[] bigger = new int[decisionMaxFixedLookaheads.length * 2];
156: System.arraycopy(decisionMaxFixedLookaheads, 0, bigger,
157: 0, decisionMaxFixedLookaheads.length);
158: decisionMaxFixedLookaheads = bigger;
159: }
160: decisionMaxFixedLookaheads[numFixedDecisions - 1] = maxLookaheadInCurrentDecision;
161: }
162: parser.isCyclicDecision = false; // can't nest so just reset to false
163: maxLookaheadInCurrentDecision = 0;
164: }
165:
166: public void consumeToken(Token token) {
167: //System.out.println("consume token "+token);
168: lastTokenConsumed = (CommonToken) token;
169: }
170:
171: /** The parser is in a decision if the decision depth > 0. This
172: * works for backtracking also, which can have nested decisions.
173: */
174: public boolean inDecision() {
175: return decisionLevel > 0;
176: }
177:
178: public void consumeHiddenToken(Token token) {
179: //System.out.println("consume hidden token "+token);
180: lastTokenConsumed = (CommonToken) token;
181: }
182:
183: /** Track refs to lookahead if in a fixed/nonfixed decision.
184: */
185: public void LT(int i, Token t) {
186: if (inDecision()) {
187: // get starting index off stack
188: int stackTop = lookaheadStack.size() - 1;
189: Integer startingIndex = (Integer) lookaheadStack
190: .get(stackTop);
191: // compute lookahead depth
192: int this RefIndex = parser.getTokenStream().index();
193: int numHidden = getNumberOfHiddenTokens(startingIndex
194: .intValue(), this RefIndex);
195: int depth = i + this RefIndex - startingIndex.intValue()
196: - numHidden;
197: /*
198: System.out.println("LT("+i+") @ index "+thisRefIndex+" is depth "+depth+
199: " max is "+maxLookaheadInCurrentDecision);
200: */
201: if (depth > maxLookaheadInCurrentDecision) {
202: maxLookaheadInCurrentDecision = depth;
203: }
204: }
205: }
206:
207: /** Track backtracking decisions. You'll see a fixed or cyclic decision
208: * and then a backtrack.
209: *
210: * enter rule
211: * ...
212: * enter decision
213: * LA and possibly consumes (for cyclic DFAs)
214: * begin backtrack level
215: * mark m
216: * rewind m
217: * end backtrack level, success
218: * exit decision
219: * ...
220: * exit rule
221: */
222: public void beginBacktrack(int level) {
223: //System.out.println("enter backtrack "+level);
224: numBacktrackDecisions++;
225: }
226:
227: /** Successful or not, track how much lookahead synpreds use */
228: public void endBacktrack(int level, boolean successful) {
229: //System.out.println("exit backtrack "+level+": "+successful);
230: decisionMaxSynPredLookaheads.add(new Integer(
231: maxLookaheadInCurrentDecision));
232: }
233:
234: /*
235: public void mark(int marker) {
236: int i = parser.getTokenStream().index();
237: System.out.println("mark @ index "+i);
238: synPredLookaheadStack.add(new Integer(i));
239: }
240:
241: public void rewind(int marker) {
242: // pop starting index off stack
243: int stackTop = synPredLookaheadStack.size()-1;
244: Integer startingIndex = (Integer)synPredLookaheadStack.get(stackTop);
245: synPredLookaheadStack.remove(synPredLookaheadStack.size()-1);
246: // compute lookahead depth
247: int stopIndex = parser.getTokenStream().index();
248: System.out.println("rewind @ index "+stopIndex);
249: int depth = stopIndex - startingIndex.intValue();
250: System.out.println("depth of lookahead for synpred: "+depth);
251: decisionMaxSynPredLookaheads.add(
252: new Integer(depth)
253: );
254: }
255: */
256:
257: public void recognitionException(RecognitionException e) {
258: numberReportedErrors++;
259: }
260:
261: public void semanticPredicate(boolean result, String predicate) {
262: if (inDecision()) {
263: numSemanticPredicates++;
264: }
265: }
266:
267: public void terminate() {
268: String stats = toNotifyString();
269: try {
270: Stats.writeReport(RUNTIME_STATS_FILENAME, stats);
271: } catch (IOException ioe) {
272: System.err.println(ioe);
273: ioe.printStackTrace(System.err);
274: }
275: System.out.println(toString(stats));
276: }
277:
278: public void setParser(DebugParser parser) {
279: this .parser = parser;
280: }
281:
282: // R E P O R T I N G
283:
284: public String toNotifyString() {
285: TokenStream input = parser.getTokenStream();
286: for (int i = 0; i < input.size() && lastTokenConsumed != null
287: && i <= lastTokenConsumed.getTokenIndex(); i++) {
288: Token t = input.get(i);
289: if (t.getChannel() != Token.DEFAULT_CHANNEL) {
290: numHiddenTokens++;
291: numHiddenCharsMatched += t.getText().length();
292: }
293: }
294: numCharsMatched = lastTokenConsumed.getStopIndex() + 1;
295: decisionMaxFixedLookaheads = trim(decisionMaxFixedLookaheads,
296: numFixedDecisions);
297: decisionMaxCyclicLookaheads = trim(decisionMaxCyclicLookaheads,
298: numCyclicDecisions);
299: StringBuffer buf = new StringBuffer();
300: buf.append(Version);
301: buf.append('\t');
302: buf.append(parser.getClass().getName());
303: buf.append('\t');
304: buf.append(numRuleInvocations);
305: buf.append('\t');
306: buf.append(maxRuleInvocationDepth);
307: buf.append('\t');
308: buf.append(numFixedDecisions);
309: buf.append('\t');
310: buf.append(Stats.min(decisionMaxFixedLookaheads));
311: buf.append('\t');
312: buf.append(Stats.max(decisionMaxFixedLookaheads));
313: buf.append('\t');
314: buf.append(Stats.avg(decisionMaxFixedLookaheads));
315: buf.append('\t');
316: buf.append(Stats.stddev(decisionMaxFixedLookaheads));
317: buf.append('\t');
318: buf.append(numCyclicDecisions);
319: buf.append('\t');
320: buf.append(Stats.min(decisionMaxCyclicLookaheads));
321: buf.append('\t');
322: buf.append(Stats.max(decisionMaxCyclicLookaheads));
323: buf.append('\t');
324: buf.append(Stats.avg(decisionMaxCyclicLookaheads));
325: buf.append('\t');
326: buf.append(Stats.stddev(decisionMaxCyclicLookaheads));
327: buf.append('\t');
328: buf.append(numBacktrackDecisions);
329: buf.append('\t');
330: buf.append(Stats.min(toArray(decisionMaxSynPredLookaheads)));
331: buf.append('\t');
332: buf.append(Stats.max(toArray(decisionMaxSynPredLookaheads)));
333: buf.append('\t');
334: buf.append(Stats.avg(toArray(decisionMaxSynPredLookaheads)));
335: buf.append('\t');
336: buf.append(Stats.stddev(toArray(decisionMaxSynPredLookaheads)));
337: buf.append('\t');
338: buf.append(numSemanticPredicates);
339: buf.append('\t');
340: buf.append(parser.getTokenStream().size());
341: buf.append('\t');
342: buf.append(numHiddenTokens);
343: buf.append('\t');
344: buf.append(numCharsMatched);
345: buf.append('\t');
346: buf.append(numHiddenCharsMatched);
347: buf.append('\t');
348: buf.append(numberReportedErrors);
349: buf.append('\t');
350: buf.append(numMemoizationCacheHits);
351: buf.append('\t');
352: buf.append(numMemoizationCacheMisses);
353: buf.append('\t');
354: buf.append(numGuessingRuleInvocations);
355: buf.append('\t');
356: buf.append(numMemoizationCacheEntries);
357: return buf.toString();
358: }
359:
360: public String toString() {
361: return toString(toNotifyString());
362: }
363:
364: protected static String[] decodeReportData(String data) {
365: String[] fields = new String[NUM_RUNTIME_STATS];
366: StringTokenizer st = new StringTokenizer(data, "\t");
367: int i = 0;
368: while (st.hasMoreTokens()) {
369: fields[i] = st.nextToken();
370: i++;
371: }
372: if (i != NUM_RUNTIME_STATS) {
373: return null;
374: }
375: return fields;
376: }
377:
378: public static String toString(String notifyDataLine) {
379: String[] fields = decodeReportData(notifyDataLine);
380: if (fields == null) {
381: return null;
382: }
383: StringBuffer buf = new StringBuffer();
384: buf.append("ANTLR Runtime Report; Profile Version ");
385: buf.append(fields[0]);
386: buf.append('\n');
387: buf.append("parser name ");
388: buf.append(fields[1]);
389: buf.append('\n');
390: buf.append("Number of rule invocations ");
391: buf.append(fields[2]);
392: buf.append('\n');
393: buf.append("Number of rule invocations in \"guessing\" mode ");
394: buf.append(fields[27]);
395: buf.append('\n');
396: buf.append("max rule invocation nesting depth ");
397: buf.append(fields[3]);
398: buf.append('\n');
399: buf.append("number of fixed lookahead decisions ");
400: buf.append(fields[4]);
401: buf.append('\n');
402: buf.append("min lookahead used in a fixed lookahead decision ");
403: buf.append(fields[5]);
404: buf.append('\n');
405: buf.append("max lookahead used in a fixed lookahead decision ");
406: buf.append(fields[6]);
407: buf.append('\n');
408: buf
409: .append("average lookahead depth used in fixed lookahead decisions ");
410: buf.append(fields[7]);
411: buf.append('\n');
412: buf
413: .append("standard deviation of depth used in fixed lookahead decisions ");
414: buf.append(fields[8]);
415: buf.append('\n');
416: buf.append("number of arbitrary lookahead decisions ");
417: buf.append(fields[9]);
418: buf.append('\n');
419: buf
420: .append("min lookahead used in an arbitrary lookahead decision ");
421: buf.append(fields[10]);
422: buf.append('\n');
423: buf
424: .append("max lookahead used in an arbitrary lookahead decision ");
425: buf.append(fields[11]);
426: buf.append('\n');
427: buf
428: .append("average lookahead depth used in arbitrary lookahead decisions ");
429: buf.append(fields[12]);
430: buf.append('\n');
431: buf
432: .append("standard deviation of depth used in arbitrary lookahead decisions ");
433: buf.append(fields[13]);
434: buf.append('\n');
435: buf.append("number of evaluated syntactic predicates ");
436: buf.append(fields[14]);
437: buf.append('\n');
438: buf.append("min lookahead used in a syntactic predicate ");
439: buf.append(fields[15]);
440: buf.append('\n');
441: buf.append("max lookahead used in a syntactic predicate ");
442: buf.append(fields[16]);
443: buf.append('\n');
444: buf
445: .append("average lookahead depth used in syntactic predicates ");
446: buf.append(fields[17]);
447: buf.append('\n');
448: buf
449: .append("standard deviation of depth used in syntactic predicates ");
450: buf.append(fields[18]);
451: buf.append('\n');
452: buf.append("rule memoization cache size ");
453: buf.append(fields[28]);
454: buf.append('\n');
455: buf.append("number of rule memoization cache hits ");
456: buf.append(fields[25]);
457: buf.append('\n');
458: buf.append("number of rule memoization cache misses ");
459: buf.append(fields[26]);
460: buf.append('\n');
461: buf.append("number of evaluated semantic predicates ");
462: buf.append(fields[19]);
463: buf.append('\n');
464: buf.append("number of tokens ");
465: buf.append(fields[20]);
466: buf.append('\n');
467: buf.append("number of hidden tokens ");
468: buf.append(fields[21]);
469: buf.append('\n');
470: buf.append("number of char ");
471: buf.append(fields[22]);
472: buf.append('\n');
473: buf.append("number of hidden char ");
474: buf.append(fields[23]);
475: buf.append('\n');
476: buf.append("number of syntax errors ");
477: buf.append(fields[24]);
478: buf.append('\n');
479: return buf.toString();
480: }
481:
482: protected int[] trim(int[] X, int n) {
483: if (n < X.length) {
484: int[] trimmed = new int[n];
485: System.arraycopy(X, 0, trimmed, 0, n);
486: X = trimmed;
487: }
488: return X;
489: }
490:
491: protected int[] toArray(List a) {
492: int[] x = new int[a.size()];
493: for (int i = 0; i < a.size(); i++) {
494: Integer I = (Integer) a.get(i);
495: x[i] = I.intValue();
496: }
497: return x;
498: }
499:
500: /** Get num hidden tokens between i..j inclusive */
501: public int getNumberOfHiddenTokens(int i, int j) {
502: int n = 0;
503: TokenStream input = parser.getTokenStream();
504: for (int ti = i; ti < input.size() && ti <= j; ti++) {
505: Token t = input.get(ti);
506: if (t.getChannel() != Token.DEFAULT_CHANNEL) {
507: n++;
508: }
509: }
510: return n;
511: }
512: }
|