]> git.wincent.com - walrat.git/blob - lib/walrat/parslet_sequence.rb
Initial import (extraction from Walrus repo, commit 0c9d44c)
[walrat.git] / lib / walrat / parslet_sequence.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   class ParsletSequence < ParsletCombination
27     attr_reader :hash
28
29     # first and second may not be nil.
30     def initialize first, second, *others
31       raise ArgumentError if first.nil?
32       raise ArgumentError if second.nil?
33       @components = [first, second] + others
34       update_hash
35     end
36
37     # Override so that sequences are appended to an existing sequence:
38     # Consider the following example:
39     #
40     #     A & B
41     #
42     # This constitutes a single sequence:
43     #
44     #     (A & B)
45     #
46     # If we then make this a three-element sequence:
47     #
48     #     A & B & C
49     #
50     # We are effectively creating an nested sequence containing the original
51     # sequence and an additional element:
52     #
53     #     ((A & B) & C)
54     #
55     # Although such a nested sequence is correctly parsed it produces unwanted
56     # nesting in the results because instead of returning a one-dimensional
57     # array of results:
58     #
59     #     [a, b, c]
60     #
61     # It returns a nested array:
62     #
63     #     [[a, b], c]
64     #
65     # The solution to this unwanted nesting is to allowing appending to an
66     # existing sequence by using the private "append" method.
67     #
68     # This ensures that:
69     #
70     #     A & B & C
71     #
72     # Translates to a single sequence:
73     #
74     #     (A & B & C)
75     #
76     # And a single, uni-dimensional results array:
77     #
78     #     [a, b, c]
79     def &(next_parslet)
80       append next_parslet
81     end
82
83     SKIP_FIRST  = true
84     NO_SKIP     = false
85
86     def parse string, options = {}
87       parse_common NO_SKIP, string, options
88     end
89
90     def parse_remainder string, options = {}
91       parse_common SKIP_FIRST, string, options
92     end
93
94     def parse_common skip_first, string, options = {}
95       raise ArgumentError if string.nil?
96       state           = ParserState.new(string, options)
97       last_caught     = nil   # keep track of the last kind of throw to be caught
98       left_recursion  = false # keep track of whether left recursion was detected
99
100       @components.each_with_index do |parseable, index|
101         if index == 0 # for first component only
102           if skip_first
103             next
104           end
105           begin
106             check_left_recursion(parseable, options)
107           rescue LeftRecursionException => e
108             left_recursion  = true
109             continuation    = nil
110             value           = callcc { |c| continuation = c }
111             if value == continuation        # first time that we're here
112               e.continuation = continuation # pack continuation into exception
113               raise e                       # and propagate
114             else
115               grammar   = state.options[:grammar]
116               rule_name = state.options[:rule_name]
117               state.parsed grammar.wrap(value, rule_name)
118               next
119             end
120           end
121         end
122
123         catch :ProcessNextComponent do
124           catch :NotPredicateSuccess do
125             catch :AndPredicateSuccess do
126               catch :ZeroWidthParseSuccess do
127                 begin
128                   parsed = parseable.memoizing_parse state.remainder, state.options
129                   state.parsed parsed
130                 rescue SkippedSubstringException => e
131                   state.skipped e
132                 rescue ParseError => e
133                   # failed, will try to skip; save original error in case
134                   # skipping fails
135                   if options.has_key?(:skipping_override)
136                     skipping_parslet = options[:skipping_override]
137                   elsif options.has_key?(:skipping)
138                     skipping_parslet = options[:skipping]
139                   else
140                     skipping_parslet = nil
141                   end
142                   raise e if skipping_parslet.nil?  # no skipper defined, raise original error
143                   begin
144                     # guard against self references (possible infinite recursion) here?
145                     parsed = skipping_parslet.memoizing_parse state.remainder, state.options
146                     state.skipped(parsed)
147                     redo              # skipping succeeded, try to redo
148                   rescue ParseError
149                     raise e           # skipping didn't help either, raise original error
150                   end
151                 end
152                 last_caught = nil
153
154                 # can't use "next" here because it would only break out of
155                 # innermost "do" rather than continuing the iteration
156                 throw :ProcessNextComponent
157               end
158               last_caught = :ZeroWidthParseSuccess
159               throw :ProcessNextComponent
160             end
161             last_caught = :AndPredicateSuccess
162             throw :ProcessNextComponent
163           end
164           last_caught = :NotPredicateSuccess
165         end
166       end
167
168       if left_recursion
169         results = recurse(state)
170       else
171         results = state.results
172       end
173
174       return results if skip_first
175
176       if results.respond_to? :empty? and results.empty? and last_caught
177         throw last_caught
178       else
179         results
180       end
181     end
182
183     # Left-recursion helper
184     def recurse state
185       return state.results if state.remainder == '' # further recursion is not possible
186       new_state = ParserState.new state.remainder, state.options
187       last_successful_result = nil
188       while state.remainder != ''
189         begin
190           new_results = parse_remainder new_state.remainder, new_state.options
191           new_state.parsed new_results
192           last_successful_result = ArrayResult[last_successful_result || state.results, new_results]
193         rescue ParseError
194           break
195         end
196       end
197       last_successful_result || state.results
198     end
199
200     def eql?(other)
201       return false if not other.instance_of? ParsletSequence
202       other_components = other.components
203       return false if @components.length != other_components.length
204       for i in 0..(@components.length - 1)
205         return false unless @components[i].eql? other_components[i]
206       end
207       true
208     end
209
210   protected
211
212     # For determining equality.
213     attr_reader :components
214
215   private
216
217     def hash_offset
218       40
219     end
220
221     def update_hash
222       # fixed offset to avoid unwanted collisions with similar classes
223       @hash = hash_offset
224       @components.each { |parseable| @hash += parseable.hash }
225     end
226
227     # Appends another Parslet, ParsletCombination or Predicate to the receiver
228     # and returns the receiver.
229     #
230     # Raises if next_parslet is nil.
231     # Cannot use << as a method name because Ruby cannot parse it without the
232     # self, and self is not allowed as en explicit receiver for private
233     # messages.
234     def append next_parslet
235       raise ArgumentError if next_parslet.nil?
236       @components << next_parslet.to_parseable
237       update_hash
238       self
239     end
240   end # class ParsletSequence
241 end # module Walrat