]> git.wincent.com - walrat.git/blob - lib/walrat/parslet_choice.rb
Initial import (extraction from Walrus repo, commit 0c9d44c)
[walrat.git] / lib / walrat / parslet_choice.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 ParsletChoice < ParsletCombination
27     attr_reader :hash
28
29     # Either parameter may be a Parslet or a ParsletCombination.
30     # Neither parmeter may be nil.
31     def initialize left, right, *others
32       raise ArgumentError if left.nil?
33       raise ArgumentError if right.nil?
34       @alternatives = [left, right] + others
35       update_hash
36     end
37
38     # Override so that alternatives are appended to an existing sequence:
39     # Consider the following example:
40     #
41     #     A | B
42     #
43     # This constitutes a single choice:
44     #
45     #     (A | B)
46     #
47     # If we then make this a three-element sequence:
48     #
49     #     A | B | C
50     #
51     # We are effectively creating an nested sequence containing the original
52     # sequence and an additional element:
53     #
54     #     ((A | B) | C)
55     #
56     # Although such a nested sequence is correctly parsed it is not as
57     # architecturally clean as a single sequence without nesting:
58     #
59     #     (A | B | C)
60     #
61     # This method allows us to use the architecturally cleaner format.
62     def |(next_parslet)
63       append next_parslet
64     end
65
66     # First tries to parse the left option, falling back and trying the right
67     # option and then the any subsequent options in the others instance
68     # variable on failure. If no options successfully complete parsing then an
69     # ParseError is raised. Any zero-width parse successes thrown by
70     # alternative parsers will flow on to a higher level.
71     def parse string, options = {}
72       raise ArgumentError if string.nil?
73       error           = nil # for error reporting purposes will track which parseable gets farthest to the right before failing
74       left_recursion  = nil # will also track any left recursion that we detect
75       @alternatives.each do |parseable|
76         begin
77           result = parseable.memoizing_parse(string, options) # successful parse
78           if left_recursion and left_recursion.continuation   # and we have a continuation
79             continuation = left_recursion.continuation        # continuations are once-only, one-way tickets
80             left_recursion = nil                              # set this to nil so as not to call it again without meaning to
81             continuation.call(result)                         # so jump back to where we were before
82           end
83           return result
84         rescue LeftRecursionException => e
85           left_recursion = e
86
87           # TODO:
88           # it's not enough to just catch this kind of exception and remember
89           # the last one
90           # may need to accumulate these in an array
91           # consider the example rule:
92           #   :a, :a & :b | :a & :c | :a & :d | :b
93           # the first option will raise a LeftRecursionException
94           # the next option will raise for the same reason
95           # the third likewise
96           # finally we get to the fourth option, the first which might succeed
97           # at that point we should have three continuations
98           # we should try the first, falling back to the second and third if
99           # necessary
100           # on successfully retrying, need to start all over again and try all
101           # the options again, just in case further recursion is possible
102           # so it is quite complicated
103           # the question is, is it more complicated than the other ways of
104           # getting right-associativity into Walrat-generated parsers?
105         rescue ParseError => e
106           if error.nil?
107             error = e
108           else
109             error = e unless error.rightmost?(e)
110           end
111         end
112       end
113
114       # should generally report the rightmost error
115       raise ParseError.new('no valid alternatives while parsing "%s" (%s)' % [string, error.to_s],
116                            :line_end => error.line_end,
117                            :column_end => error.column_end)
118     end
119
120     def eql? other
121       return false if not other.instance_of? ParsletChoice
122       other_alternatives = other.alternatives
123       return false if @alternatives.length != other_alternatives.length
124       for i in 0..(@alternatives.length - 1)
125         return false unless @alternatives[i].eql? other_alternatives[i]
126       end
127       true
128     end
129
130   protected
131
132     # For determining equality.
133     attr_reader :alternatives
134
135   private
136
137     def update_hash
138       # fixed offset to avoid unwanted collisions with similar classes
139       @hash = 30
140       @alternatives.each { |parseable| @hash += parseable.hash }
141     end
142
143     # Appends another Parslet (or ParsletCombination) to the receiver and
144     # returns the receiver.
145     # Raises if parslet is nil.
146     # Cannot use << as a method name because Ruby cannot parse it without
147     # the self, and self is not allowed as en explicit receiver for private messages.
148     def append next_parslet
149       raise ArgumentError if next_parslet.nil?
150       @alternatives << next_parslet.to_parseable
151       update_hash
152       self
153     end
154   end # class ParsletChoice
155 end # module Walrat