[Qt]REGRESSION(r92254): It made 2 tests timeout
[WebKit-https.git] / Source / JavaScriptCore / offlineasm / parser.rb
1 # Copyright (C) 2011 Apple Inc. All rights reserved.
2 #
3 # Redistribution and use in source and binary forms, with or without
4 # modification, are permitted provided that the following conditions
5 # are met:
6 # 1. Redistributions of source code must retain the above copyright
7 #    notice, this list of conditions and the following disclaimer.
8 # 2. Redistributions in binary form must reproduce the above copyright
9 #    notice, this list of conditions and the following disclaimer in the
10 #    documentation and/or other materials provided with the distribution.
11 #
12 # THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
13 # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
14 # THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
15 # PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
16 # BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
17 # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
18 # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
19 # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
20 # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
21 # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
22 # THE POSSIBILITY OF SUCH DAMAGE.
23
24 require "ast"
25 require "instructions"
26 require "registers"
27
28 class Token
29     attr_reader :codeOrigin, :string
30     
31     def initialize(codeOrigin, string)
32         @codeOrigin = codeOrigin
33         @string = string
34     end
35     
36     def ==(other)
37         if other.is_a? Token
38             @string == other.string
39         else
40             @string == other
41         end
42     end
43     
44     def =~(other)
45         @string =~ other
46     end
47     
48     def to_s
49         "#{@string.inspect} at line #{codeOrigin}"
50     end
51     
52     def parseError(*comment)
53         if comment.empty?
54             raise "Parse error: #{to_s}"
55         else
56             raise "Parse error: #{to_s}: #{comment[0]}"
57         end
58     end
59 end
60
61 #
62 # The lexer. Takes a string and returns an array of tokens.
63 #
64
65 def lex(str)
66     result = []
67     lineNumber = 1
68     while not str.empty?
69         case str
70         when /\A\#([^\n]*)/
71             # comment, ignore
72         when /\A\n/
73             result << Token.new(lineNumber, $&)
74             lineNumber += 1
75         when /\A[a-zA-Z]([a-zA-Z0-9_]*)/
76             result << Token.new(lineNumber, $&)
77         when /\A\.([a-zA-Z0-9_]*)/
78             result << Token.new(lineNumber, $&)
79         when /\A_([a-zA-Z0-9_]*)/
80             result << Token.new(lineNumber, $&)
81         when /\A([ \t]+)/
82             # whitespace, ignore
83         when /\A0x([0-9a-fA-F]+)/
84             result << Token.new(lineNumber, $&.hex.to_s)
85         when /\A0([0-7]+)/
86             result << Token.new(lineNumber, $&.oct.to_s)
87         when /\A([0-9]+)/
88             result << Token.new(lineNumber, $&)
89         when /\A::/
90             result << Token.new(lineNumber, $&)
91         when /\A[:,\(\)\[\]=\+\-*]/
92             result << Token.new(lineNumber, $&)
93         else
94             raise "Lexer error at line number #{lineNumber}, unexpected sequence #{str[0..20].inspect}"
95         end
96         str = $~.post_match
97     end
98     result
99 end
100
101 #
102 # Token identification.
103 #
104
105 def isRegister(token)
106     token =~ REGISTER_PATTERN
107 end
108
109 def isInstruction(token)
110     token =~ INSTRUCTION_PATTERN
111 end
112
113 def isKeyword(token)
114     token =~ /\A((true)|(false)|(if)|(then)|(else)|(elsif)|(end)|(and)|(or)|(not)|(macro)|(const)|(sizeof)|(error))\Z/ or
115         token =~ REGISTER_PATTERN or
116         token =~ INSTRUCTION_PATTERN
117 end
118
119 def isIdentifier(token)
120     token =~ /\A[a-zA-Z]([a-zA-Z0-9_]*)\Z/ and not isKeyword(token)
121 end
122
123 def isLabel(token)
124     token =~ /\A_([a-zA-Z0-9_]*)\Z/
125 end
126
127 def isLocalLabel(token)
128     token =~ /\A\.([a-zA-Z0-9_]*)\Z/
129 end
130
131 def isVariable(token)
132     isIdentifier(token) or isRegister(token)
133 end
134
135 def isInteger(token)
136     token =~ /\A[0-9]/
137 end
138
139 #
140 # The parser. Takes an array of tokens and returns an AST. Methods
141 # other than parse(tokens) are not for public consumption.
142 #
143
144 class Parser
145     def initialize(tokens)
146         @tokens = tokens
147         @idx = 0
148     end
149     
150     def parseError(*comment)
151         if @tokens[@idx]
152             @tokens[@idx].parseError(*comment)
153         else
154             if comment.empty?
155                 raise "Parse error at end of file"
156             else
157                 raise "Parse error at end of file: #{comment[0]}"
158             end
159         end
160     end
161     
162     def consume(regexp)
163         if regexp
164             parseError unless @tokens[@idx] =~ regexp
165         else
166             parseError unless @idx == @tokens.length
167         end
168         @idx += 1
169     end
170     
171     def skipNewLine
172         while @tokens[@idx] == "\n"
173             @idx += 1
174         end
175     end
176     
177     def parsePredicateAtom
178         if @tokens[@idx] == "not"
179             @idx += 1
180             parsePredicateAtom
181         elsif @tokens[@idx] == "("
182             @idx += 1
183             skipNewLine
184             result = parsePredicate
185             parseError unless @tokens[@idx] == ")"
186             @idx += 1
187             result
188         elsif @tokens[@idx] == "true"
189             result = True.instance
190             @idx += 1
191             result
192         elsif @tokens[@idx] == "false"
193             result = False.instance
194             @idx += 1
195             result
196         elsif isIdentifier @tokens[@idx]
197             result = Setting.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string)
198             @idx += 1
199             result
200         else
201             parseError
202         end
203     end
204     
205     def parsePredicateAnd
206         result = parsePredicateAtom
207         while @tokens[@idx] == "and"
208             codeOrigin = @tokens[@idx].codeOrigin
209             @idx += 1
210             skipNewLine
211             right = parsePredicateAtom
212             result = And.new(codeOrigin, result, right)
213         end
214         result
215     end
216     
217     def parsePredicate
218         # some examples of precedence:
219         # not a and b -> (not a) and b
220         # a and b or c -> (a and b) or c
221         # a or b and c -> a or (b and c)
222         
223         result = parsePredicateAnd
224         while @tokens[@idx] == "or"
225             codeOrigin = @tokens[@idx].codeOrigin
226             @idx += 1
227             skipNewLine
228             right = parsePredicateAnd
229             result = Or.new(codeOrigin, result, right)
230         end
231         result
232     end
233     
234     def parseVariable
235         if isRegister(@tokens[@idx])
236             if @tokens[@idx] =~ FPR_PATTERN
237                 result = FPRegisterID.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string)
238             else
239                 result = RegisterID.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string)
240             end
241         elsif isIdentifier(@tokens[@idx])
242             result = Variable.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string)
243         else
244             parseError
245         end
246         @idx += 1
247         result
248     end
249     
250     def parseAddress(offset)
251         parseError unless @tokens[@idx] == "["
252         codeOrigin = @tokens[@idx].codeOrigin
253         
254         # Three possibilities:
255         # []       -> AbsoluteAddress
256         # [a]      -> Address
257         # [a,b]    -> BaseIndex with scale = 1
258         # [a,b,c]  -> BaseIndex
259         
260         @idx += 1
261         if @tokens[@idx] == "]"
262             @idx += 1
263             return AbsoluteAddress.new(codeOrigin, offset)
264         end
265         a = parseVariable
266         if @tokens[@idx] == "]"
267             result = Address.new(codeOrigin, a, offset)
268         else
269             parseError unless @tokens[@idx] == ","
270             @idx += 1
271             b = parseVariable
272             if @tokens[@idx] == "]"
273                 result = BaseIndex.new(codeOrigin, a, b, 1, offset)
274             else
275                 parseError unless @tokens[@idx] == ","
276                 @idx += 1
277                 parseError unless ["1", "2", "4", "8"].member? @tokens[@idx].string
278                 c = @tokens[@idx].string.to_i
279                 @idx += 1
280                 parseError unless @tokens[@idx] == "]"
281                 result = BaseIndex.new(codeOrigin, a, b, c, offset)
282             end
283         end
284         @idx += 1
285         result
286     end
287     
288     def parseColonColon
289         skipNewLine
290         codeOrigin = @tokens[@idx].codeOrigin
291         parseError unless isIdentifier @tokens[@idx]
292         names = [@tokens[@idx].string]
293         @idx += 1
294         while @tokens[@idx] == "::"
295             @idx += 1
296             parseError unless isIdentifier @tokens[@idx]
297             names << @tokens[@idx].string
298             @idx += 1
299         end
300         raise if names.empty?
301         [codeOrigin, names]
302     end
303     
304     def parseExpressionAtom
305         skipNewLine
306         if @tokens[@idx] == "-"
307             @idx += 1
308             NegImmediate.new(@tokens[@idx - 1].codeOrigin, parseExpressionAtom)
309         elsif @tokens[@idx] == "("
310             @idx += 1
311             result = parseExpression
312             parseError unless @tokens[@idx] == ")"
313             @idx += 1
314             result
315         elsif isInteger @tokens[@idx]
316             result = Immediate.new(@tokens[@idx].codeOrigin, @tokens[@idx].string.to_i)
317             @idx += 1
318             result
319         elsif isIdentifier @tokens[@idx]
320             codeOrigin, names = parseColonColon
321             if names.size > 1
322                 StructOffset.forField(codeOrigin, names[0..-2].join('::'), names[-1])
323             else
324                 Variable.forName(codeOrigin, names[0])
325             end
326         elsif isRegister @tokens[@idx]
327             parseVariable
328         elsif @tokens[@idx] == "sizeof"
329             @idx += 1
330             codeOrigin, names = parseColonColon
331             Sizeof.forName(codeOrigin, names.join('::'))
332         else
333             parseError
334         end
335     end
336     
337     def parseExpressionMul
338         skipNewLine
339         result = parseExpressionAtom
340         while @tokens[@idx] == "*"
341             if @tokens[@idx] == "*"
342                 @idx += 1
343                 result = MulImmediates.new(@tokens[@idx - 1].codeOrigin, result, parseExpressionAtom)
344             else
345                 raise
346             end
347         end
348         result
349     end
350     
351     def couldBeExpression
352         @tokens[@idx] == "-" or @tokens[@idx] == "sizeof" or isInteger(@tokens[@idx]) or isVariable(@tokens[@idx]) or @tokens[@idx] == "("
353     end
354     
355     def parseExpression
356         skipNewLine
357         result = parseExpressionMul
358         while @tokens[@idx] == "+" or @tokens[@idx] == "-"
359             if @tokens[@idx] == "+"
360                 @idx += 1
361                 result = AddImmediates.new(@tokens[@idx - 1].codeOrigin, result, parseExpressionMul)
362             elsif @tokens[@idx] == "-"
363                 @idx += 1
364                 result = SubImmediates.new(@tokens[@idx - 1].codeOrigin, result, parseExpressionMul)
365             else
366                 raise
367             end
368         end
369         result
370     end
371     
372     def parseOperand(comment)
373         skipNewLine
374         if couldBeExpression
375             expr = parseExpression
376             if @tokens[@idx] == "["
377                 parseAddress(expr)
378             else
379                 expr
380             end
381         elsif @tokens[@idx] == "["
382             parseAddress(Immediate.new(@tokens[@idx].codeOrigin, 0))
383         elsif isLabel @tokens[@idx]
384             result = LabelReference.new(@tokens[@idx].codeOrigin, Label.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string))
385             @idx += 1
386             result
387         elsif isLocalLabel @tokens[@idx]
388             result = LocalLabelReference.new(@tokens[@idx].codeOrigin, LocalLabel.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string))
389             @idx += 1
390             result
391         else
392             parseError(comment)
393         end
394     end
395     
396     def parseMacroVariables
397         skipNewLine
398         consume(/\A\(\Z/)
399         variables = []
400         loop {
401             skipNewLine
402             if @tokens[@idx] == ")"
403                 @idx += 1
404                 break
405             elsif isIdentifier(@tokens[@idx])
406                 variables << Variable.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string)
407                 @idx += 1
408                 skipNewLine
409                 if @tokens[@idx] == ")"
410                     @idx += 1
411                     break
412                 elsif @tokens[@idx] == ","
413                     @idx += 1
414                 else
415                     parseError
416                 end
417             else
418                 parseError
419             end
420         }
421         variables
422     end
423     
424     def parseSequence(final, comment)
425         firstCodeOrigin = @tokens[@idx].codeOrigin
426         list = []
427         loop {
428             if (@idx == @tokens.length and not final) or (final and @tokens[@idx] =~ final)
429                 break
430             elsif @tokens[@idx] == "\n"
431                 # ignore
432                 @idx += 1
433             elsif @tokens[@idx] == "const"
434                 @idx += 1
435                 parseError unless isVariable @tokens[@idx]
436                 variable = Variable.forName(@tokens[@idx].codeOrigin, @tokens[@idx].string)
437                 @idx += 1
438                 parseError unless @tokens[@idx] == "="
439                 @idx += 1
440                 value = parseOperand("while inside of const #{variable.name}")
441                 list << ConstDecl.new(@tokens[@idx].codeOrigin, variable, value)
442             elsif @tokens[@idx] == "error"
443                 list << Error.new(@tokens[@idx].codeOrigin)
444                 @idx += 1
445             elsif @tokens[@idx] == "if"
446                 codeOrigin = @tokens[@idx].codeOrigin
447                 @idx += 1
448                 skipNewLine
449                 predicate = parsePredicate
450                 consume(/\A((then)|(\n))\Z/)
451                 skipNewLine
452                 ifThenElse = IfThenElse.new(codeOrigin, predicate, parseSequence(/\A((else)|(end)|(elsif))\Z/, "while inside of \"if #{predicate.dump}\""))
453                 list << ifThenElse
454                 while @tokens[@idx] == "elsif"
455                     codeOrigin = @tokens[@idx].codeOrigin
456                     @idx += 1
457                     skipNewLine
458                     predicate = parsePredicate
459                     consume(/\A((then)|(\n))\Z/)
460                     skipNewLine
461                     elseCase = IfThenElse.new(codeOrigin, predicate, parseSequence(/\A((else)|(end)|(elsif))\Z/, "while inside of \"if #{predicate.dump}\""))
462                     ifThenElse.elseCase = elseCase
463                     ifThenElse = elseCase
464                 end
465                 if @tokens[@idx] == "else"
466                     @idx += 1
467                     ifThenElse.elseCase = parseSequence(/\Aend\Z/, "while inside of else case for \"if #{predicate.dump}\"")
468                     @idx += 1
469                 else
470                     parseError unless @tokens[@idx] == "end"
471                     @idx += 1
472                 end
473             elsif @tokens[@idx] == "macro"
474                 codeOrigin = @tokens[@idx].codeOrigin
475                 @idx += 1
476                 skipNewLine
477                 parseError unless isIdentifier(@tokens[@idx])
478                 name = @tokens[@idx].string
479                 @idx += 1
480                 variables = parseMacroVariables
481                 body = parseSequence(/\Aend\Z/, "while inside of macro #{name}")
482                 @idx += 1
483                 list << Macro.new(codeOrigin, name, variables, body)
484             elsif isInstruction @tokens[@idx]
485                 codeOrigin = @tokens[@idx].codeOrigin
486                 name = @tokens[@idx].string
487                 @idx += 1
488                 if (not final and @idx == @tokens.size) or (final and @tokens[@idx] =~ final)
489                     # Zero operand instruction, and it's the last one.
490                     list << Instruction.new(codeOrigin, name, [])
491                     break
492                 elsif @tokens[@idx] == "\n"
493                     # Zero operand instruction.
494                     list << Instruction.new(codeOrigin, name, [])
495                     @idx += 1
496                 else
497                     # It's definitely an instruction, and it has at least one operand.
498                     operands = []
499                     endOfSequence = false
500                     loop {
501                         operands << parseOperand("while inside of instruction #{name}")
502                         if (not final and @idx == @tokens.size) or (final and @tokens[@idx] =~ final)
503                             # The end of the instruction and of the sequence.
504                             endOfSequence = true
505                             break
506                         elsif @tokens[@idx] == ","
507                             # Has another operand.
508                             @idx += 1
509                         elsif @tokens[@idx] == "\n"
510                             # The end of the instruction.
511                             @idx += 1
512                             break
513                         else
514                             parseError("Expected a comma, newline, or #{final} after #{operands.last.dump}")
515                         end
516                     }
517                     list << Instruction.new(codeOrigin, name, operands)
518                     if endOfSequence
519                         break
520                     end
521                 end
522             elsif isIdentifier @tokens[@idx]
523                 codeOrigin = @tokens[@idx].codeOrigin
524                 name = @tokens[@idx].string
525                 @idx += 1
526                 if @tokens[@idx] == "("
527                     # Macro invocation.
528                     @idx += 1
529                     operands = []
530                     skipNewLine
531                     if @tokens[@idx] == ")"
532                         @idx += 1
533                     else
534                         loop {
535                             skipNewLine
536                             if @tokens[@idx] == "macro"
537                                 # It's a macro lambda!
538                                 codeOriginInner = @tokens[@idx].codeOrigin
539                                 @idx += 1
540                                 variables = parseMacroVariables
541                                 body = parseSequence(/\Aend\Z/, "while inside of anonymous macro passed as argument to #{name}")
542                                 @idx += 1
543                                 operands << Macro.new(codeOriginInner, nil, variables, body)
544                             else
545                                 operands << parseOperand("while inside of macro call to #{name}")
546                             end
547                             skipNewLine
548                             if @tokens[@idx] == ")"
549                                 @idx += 1
550                                 break
551                             elsif @tokens[@idx] == ","
552                                 @idx += 1
553                             else
554                                 parseError "Unexpected #{@tokens[@idx].string.inspect} while parsing invocation of macro #{name}"
555                             end
556                         }
557                     end
558                     list << MacroCall.new(codeOrigin, name, operands)
559                 else
560                     parseError "Expected \"(\" after #{name}"
561                 end
562             elsif isLabel @tokens[@idx] or isLocalLabel @tokens[@idx]
563                 codeOrigin = @tokens[@idx].codeOrigin
564                 name = @tokens[@idx].string
565                 @idx += 1
566                 parseError unless @tokens[@idx] == ":"
567                 # It's a label.
568                 if isLabel name
569                     list << Label.forName(codeOrigin, name)
570                 else
571                     list << LocalLabel.forName(codeOrigin, name)
572                 end
573                 @idx += 1
574             else
575                 parseError "Expecting terminal #{final} #{comment}"
576             end
577         }
578         Sequence.new(firstCodeOrigin, list)
579     end
580 end
581
582 def parse(tokens)
583     parser = Parser.new(tokens)
584     parser.parseSequence(nil, "")
585 end
586