lib/walrat/memoizing_cache.rb

   1 # Copyright 2007-2010 Wincent Colaiuta. All rights reserved.
   2 # Redistribution and use in source and binary forms, with or without
   3 # modification, are permitted provided that the following conditions are met:
   4 #
   5 # 1. Redistributions of source code must retain the above copyright notice,
   6 #    this list of conditions and the following disclaimer.
   7 # 2. Redistributions in binary form must reproduce the above copyright notice,
   8 #    this list of conditions and the following disclaimer in the documentation
   9 #    and/or other materials provided with the distribution.
  10 #
  11 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  12 # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  13 # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  14 # ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE
  15 # LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  16 # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  17 # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  18 # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  19 # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  20 # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  21 # POSSIBILITY OF SUCH DAMAGE.
  22
  23 require 'walrat'
  24
  25 module Walrat
  26   # The MemoizingCache class memoizes the outcomes of parse operations. The
  27   # functionality is implemented as a separate class so as to minimize the
  28   # amount of "contamination" of other classes by memoizing code, and to allow
  29   # memoizing to be cleanly turned on or off at will. If a MemoizingCache is
  30   # passed to a Parslet, ParsletCombination or Predicate as a value for the
  31   # :memoizer key in the options hash passed to a parse method, the class
  32   # implementing that method will call the parse method on the cache rather
  33   # than proceeding normally. The cache will either propagate the previously
  34   # memoized result, or will defer back to the original class to obtain the
  35   # result. A circular dependency is avoided by setting the :skip_memoizer flag
  36   # in the options dictionary. If no MemoizingCache is passed then normal
  37   # program flow takes place.
  38   class MemoizingCache
  39     # Singleton class that serves as a default value for unset keys in a Hash.
  40     class NoValueForKey
  41       require 'singleton'
  42       include Singleton
  43     end
  44
  45     def initialize
  46       # The results of parse operations are stored (memoized) in a cache, keyed
  47       # on a unique identifier comprising the Parslet, ParsletCombination or
  48       # Predicate used in the parse operation, the location of the operation
  49       # (the line_start and column_start), and the skipping override (if any).
  50       # The values may be:
  51       #
  52       #   - ParseErrors raised during parsing
  53       #   - SkippedSubstringExceptions raised during parsing
  54       #   - :ZeroWidthParseSuccess symbols thrown during parsing
  55       #   - :AndPredicateSuccess symbols thrown during parsing
  56       #   - :NotPredicateSuccess symbols thrown during parsing
  57       #   - String instances returned as parse results
  58       #   - MatchDataWrapper instance returned as parse results
  59       #   - Array instances containing ordered collections of parse results
  60       #   - Node subclass instances containing AST productions
  61       @cache = Hash.new NoValueForKey.instance
  62     end
  63
  64     # The receiver checks whether there is already a stored result
  65     # corresponding to that a unique identifier that specifies the
  66     # "coordinates" of a parsing operation (location, parseable, skipping
  67     # override). If found propogates the result directly to the caller rather
  68     # than performing the parse method all over again. Here "propagation" means
  69     # re-raising parse errors, re-throwing symbols, and returning object
  70     # references. If not found, performs the parsing operation and stores the
  71     # result in the cache before propagating it.
  72     def parse string, options = {}
  73       raise ArgumentError if string.nil?
  74
  75       # construct a unique identifier
  76       identifier = [options[:parseable], options[:line_start], options[:column_start]]
  77       identifier << options[:origin] if options.has_key? :origin
  78       identifier << options[:skipping_override] if options.has_key? :skipping_override
  79
  80       if (result = @cache[identifier]) != NoValueForKey.instance
  81         if result.kind_of? Symbol
  82           throw result
  83         elsif result.kind_of? Exception
  84           raise result
  85         else
  86           return result
  87         end
  88       else
  89         # first time for this parseable/location/skipping_override (etc)
  90         # combination; capture result and propagate
  91         catch :NotPredicateSuccess do
  92           catch :AndPredicateSuccess do
  93             catch :ZeroWidthParseSuccess do
  94               begin
  95                 options[:ignore_memoizer] = true
  96
  97                 # short-circuit left recursion here rather than infinite
  98                 # looping
  99                 if options[:parseable].kind_of? SymbolParslet
 100                   check_left_recursion(options[:parseable], options)
 101                   @last_seen_symbol_parslet             = options[:parseable]
 102                   @last_seen_symbol_parslet_location    = [options[:line_start], options[:column_start]]
 103                 end
 104
 105                 return @cache[identifier] = options[:parseable].memoizing_parse(string, options)  # store and return
 106               rescue Exception => e
 107                 raise @cache[identifier] = e                  # store and re-raise
 108               end
 109             end
 110             throw @cache[identifier] = :ZeroWidthParseSuccess # store and re-throw
 111           end
 112           throw @cache[identifier] = :AndPredicateSuccess     # store and re-throw
 113         end
 114         throw @cache[identifier] = :NotPredicateSuccess       # store and re-throw
 115       end
 116     end
 117
 118     def check_left_recursion parseable, options = {}
 119       if parseable.kind_of? SymbolParslet and
 120          @last_seen_symbol_parslet == parseable and
 121          @last_seen_symbol_parslet_location == [options[:line_start], options[:column_start]]
 122         raise LeftRecursionException
 123       end
 124     end
 125   end # class MemoizingCache
 126 end # module Walrat