• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/ruby
2# encoding: utf-8
3
4=begin LICENSE
5
6[The "BSD licence"]
7Copyright (c) 2009-2010 Kyle Yetter
8All rights reserved.
9
10Redistribution and use in source and binary forms, with or without
11modification, are permitted provided that the following conditions
12are met:
13
14 1. Redistributions of source code must retain the above copyright
15    notice, this list of conditions and the following disclaimer.
16 2. Redistributions in binary form must reproduce the above copyright
17    notice, this list of conditions and the following disclaimer in the
18    documentation and/or other materials provided with the distribution.
19 3. The name of the author may not be used to endorse or promote products
20    derived from this software without specific prior written permission.
21
22THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33=end
34
35module ANTLR3
36module Profile
37=begin rdoc ANTLR3::Profile::ParserEvents
38
39ANTLR3::Profile::ParserEvents expands basic debugging events for use by
40recognition code generated by ANTLR when called with the <tt>-profile</tt>
41switch.
42
43=end
44module ParserEvents
45  include ANTLR3::Debug::ParserEvents
46
47  def self.included( klass )
48    super
49    if klass.is_a?( ::Class )
50      def klass.profile?
51        true
52      end
53    end
54  end
55
56  def initialize( stream, options = {} )
57    options[ :debug_listener ] ||= Profiler.new( self )
58    super( stream, options )
59  end
60
61  def already_parsed_rule?( rule )
62    @debug_listener.examine_rule_memoization( rule )
63    super
64  end
65
66  def profile
67    @debug_listener.profile
68  end
69
70  def memoize( rule, start_index, success )
71    @debug_listener.memoize( rule, rule_start_index, sucess )
72    super
73  end
74end
75
76class DataSet < ::Array
77  include ::Math
78  def total
79    inject( :+ )
80  end
81  def average
82    length > 0 ? ( total.to_f / length ) : 0
83  end
84  def variance
85    length.zero? and return( 0.0 )
86    mean = average
87    inject( 0.0 ) { |t, i| t + ( i - mean )**2 } / ( length - 1 )
88  end
89  def standard_deviation
90    sqrt( variance )
91  end
92end
93
94
95unless const_defined?( :Profile )
96  Profile = Struct.new(
97    :grammar_file, :parser_class, :top_rule,
98    :rule_invocations, :guessing_rule_invocations, :rule_invocation_depth,
99    :fixed_looks, :cyclic_looks, :syntactic_predicate_looks,
100    :memoization_cache_entries, :memoization_cache_hits,
101    :memoization_cache_misses, :tokens, :hidden_tokens,
102    :characters_matched, :hidden_characters_matched, :semantic_predicates,
103    :syntactic_predicates, :reported_errors
104  )
105end
106
107class Profile
108  def initialize
109    init_values = Array.new( self.class.members.length, 0 )
110    super( *init_values )
111    self.top_rule = self.parser_class = self.grammar_file = nil
112    self.fixed_looks = DataSet.new
113    self.cyclic_looks = DataSet.new
114    self.syntactic_predicate_looks = DataSet.new
115  end
116
117  def fixed_decisions
118    fixed_looks.length
119  end
120
121  def cyclic_decisions
122    cyclic_looks.length
123  end
124
125  def backtracking_decisions
126    syntactic_predicate_looks.length
127  end
128
129  def generate_report
130    report = '+' << '-' * 78 << "+\n"
131    report << '| ' << "ANTLR Rule Profile".center( 76 ) << " |\n"
132    report << '+' << '-' * 78 << "+\n"
133    report << "| Generated at #{ Time.now }".ljust( 78 ) << " |\n"
134    report << "| Profiled #{ parser_class.name }##{ top_rule }".ljust( 78 ) << " |\n"
135    report << "| Rule source generated from grammar file #{ grammar_file }".ljust( 78 ) << " |\n"
136    report << '+' << '-' * 78 << "+\n"
137
138    report << '| ' << "Rule Invocations".center( 76 ) << " |\n"
139    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
140    report << "| %-66s | %7i |\n" % [ "Total Invocations", rule_invocations ]
141    report << "| %-66s | %7i |\n" % [ "``Guessing'' Invocations", guessing_rule_invocations ]
142    report << "| %-66s | %7i |\n" % [ "Deepest Level of Invocation", rule_invocation_depth ]
143    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
144
145    report << '| ' << "Execution Events".center( 76 ) << " |\n"
146    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
147    report << "| %-66s | %7i |\n" % [ "Semantic Predicates Evaluated", semantic_predicates ]
148    report << "| %-66s | %7i |\n" % [ "Syntactic Predicates Evaluated", syntactic_predicates ]
149    report << "| %-66s | %7i |\n" % [ "Errors Reported", reported_errors ]
150    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
151
152    report << '| ' << "Token and Character Data".center( 76 ) << " |\n"
153    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
154    report << "| %-66s | %7i |\n" % [ "Tokens Consumed", tokens ]
155    report << "| %-66s | %7i |\n" % [ "Hidden Tokens Consumed", hidden_tokens ]
156    report << "| %-66s | %7i |\n" % [ "Characters Matched", characters_matched ]
157    report << "| %-66s | %7i |\n" % [ "Hidden Characters Matched", hidden_characters_matched ]
158    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
159
160    report << '| ' << "Memoization".center( 76 ) << " |\n"
161    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
162    report << "| %-66s | %7i |\n" % [ "Cache Entries", memoization_cache_entries ]
163    report << "| %-66s | %7i |\n" % [ "Cache Hits", memoization_cache_hits ]
164    report << "| %-66s | %7i |\n" % [ "Cache Misses", memoization_cache_misses ]
165    report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
166
167    [
168      [ 'Fixed Lookahead (k)', fixed_looks ],
169      [ 'Arbitrary Lookahead (k)', cyclic_looks ],
170      [ 'Backtracking (Syntactic Predicate)', syntactic_predicate_looks ]
171    ].each do |name, set|
172      mean, stdev = '%4.2f' % set.average, '%4.2f' % set.standard_deviation
173      report << '| ' << "#{ name } Decisions".center( 76 ) << " |\n"
174      report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
175      report << "| %-66s | %7i |\n" % [ "Count", set.length ]
176      report << "| %-66s | %7i |\n" % [ "Minimum k", set.min ]
177      report << "| %-66s | %7i |\n" % [ "Maximum k", set.max ]
178      report << "| %-66s | %7s |\n" % [ "Average k", mean ]
179      report << "| %-66s | %7s |\n" % [ "Standard Deviation of k", stdev ]
180      report << '+' << '-' * 68 << '+' << '-' * 9 << "+\n"
181    end
182    return( report )
183  end
184end
185
186=begin rdoc ANTLR3::Profile::Profiler
187
188When ANTLR is run with the <tt>-profile</tt> switch, it generates recognition
189code that performs accounting about the decision logic performed while parsing
190any given input. This information can be used to help refactor a slow grammar.
191Profiler is an event-listener that performs all of the profiling accounting and
192builds a simple report to present the various statistics.
193
194=end
195class Profiler
196  include Debug::EventListener
197  include Constants
198
199  PROTOCOL_VERSION = 2
200
201  attr_accessor :parser
202  attr_reader :rule_level
203  attr_reader :decision_level
204
205  # tracks the maximum look value for the current decision
206  # (maxLookaheadInCurrentDecision in java Profiler)
207  attr_reader :decision_look
208
209  # the last token consumed
210  # (lastTokenConsumed in java Profiler)
211  attr_reader :last_token
212  attr_reader :look_stack
213  attr_reader :profile
214
215  attr_accessor :output
216
217  def initialize( parser = nil, output = nil )
218    @parser = parser
219    @profile = nil
220    @rule_level = 0
221    @decision_level = 0
222    @decision_look = 0
223    @last_token = nil
224    @look_stack = []
225    @output = output
226  end
227
228  def commence
229    @profile = Profile.new
230    @rule_level = 0
231    @decision_level = 0
232    @decision_look = 0
233    @last_token = nil
234    @look_stack = []
235  end
236
237  def enter_rule( grammar_file_name, rule_name )
238    if @rule_level.zero?
239      commence
240      @profile.grammar_file = grammar_file_name
241      @profile.parser_class = @parser.class
242      @profile.top_rule = rule_name
243    end
244    @rule_level += 1
245    @profile.rule_invocations += 1
246    @profile.rule_invocation_depth < @rule_level and
247      @profile.rule_invocation_depth = @rule_level
248  end
249
250  def exit_rule( grammar_file_name, rule_name )
251    @rule_level -= 1
252  end
253
254  def examine_rule_memoization( rule )
255    stop_index = parser.rule_memoization( rule, @parser.input.index )
256    if stop_index == MEMO_RULE_UNKNOWN
257      @profile.memoization_cache_misses += 1
258      @profile.guessing_rule_invocations += 1
259    else
260      @profile.memoization_cache_hits += 1
261    end
262  end
263
264  def memoize( rule, start_index, success )
265    @profile.memoization_cache_entries += 1
266  end
267
268
269  def enter_decision( decision_number )
270    @decision_level += 1
271    starting_look_index = @parser.input.index
272    @look_stack << starting_look_index
273  end
274
275  def exit_decision( decision_number )
276    @look_stack.pop
277    @decision_level -= 1
278    if @parser.cyclic_decision? then
279      @profile.cyclic_looks << @decision_look
280    else @profile.fixed_looks << @decision_look
281    end
282
283    @parser.cyclic_decision = false
284    @decision_look = 0
285  end
286
287  def consume_token( token )
288    @last_token = token
289  end
290
291  def in_decision?
292    return( @decision_level > 0 )
293  end
294
295  def consume_hidden_token( token )
296    @last_token = token
297  end
298
299  def look( i, token )
300    in_decision? or return
301    starting_index = look_stack.last
302    input = @parser.input
303    this_ref_index = input.index
304    num_hidden = input.tokens( starting_index, this_ref_index ).count { |t| t.hidden? }
305    depth = i + this_ref_index - starting_index - num_hidden
306    if depth > @decision_look
307      @decision_look = depth
308    end
309  end
310
311  def end_backtrack( level, successful )
312    @profile.syntactic_predicate_looks << @decision_look
313  end
314
315  def recognition_exception( error )
316    @profile.reported_errors += 1
317  end
318
319  def semantic_predicate( result, predicate )
320    in_decision? and @profile.semantic_predicates += 1
321  end
322
323  def terminate
324    input = @parser.input
325    hidden_tokens = input.select { |token| token.hidden? }
326    @profile.hidden_tokens = hidden_tokens.length
327    @profile.tokens = input.tokens.length
328    @profile.hidden_characters_matched = hidden_tokens.inject( 0 ) do |count, token|
329      count + token.text.length rescue count
330    end
331    @profile.characters_matched = ( @last_token || input.tokens.last ).stop + 1 rescue 0
332    write_report
333  end
334
335
336  def write_report
337    @output << @profile.generate_report unless @output.nil?
338  rescue NoMethodError => error
339    if error.name.to_s == '<<'
340      warn( <<-END.strip! % [ __FILE__, __LINE__, @output ] )
341        [%s @ %s]: failed to write report to %p as it does not respond to :<<
342      END
343    else raise
344    end
345  rescue IOError => error
346    $stderr.puts( Util.tidy( <<-END ) % [ __FILE__, __LINE__, @output, error.class, error.message ] )
347    | [%s @ %s]: failed to write profile report to %p due to an IO Error:
348    |   %s: %s
349    END
350    $stderr.puts( error.backtrace.map { |call| "  - #{ call }" }.join( "\n" ) )
351  end
352
353  def report
354    @profile.generate_report
355  end
356
357  alias to_s report
358end
359end
360end
361