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