]> git.wincent.com - walrat.git/blob - lib/walrat/memoizing_cache.rb
Initial import (extraction from Walrus repo, commit 0c9d44c)
[walrat.git] / 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