ec193254a668342fd6044a5d2d2a22177d6ab55f
[WebKit-https.git] / Source / JavaScriptCore / wasm / WasmFunctionParser.h
1 /*
2  * Copyright (C) 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #pragma once
27
28 #if ENABLE(WEBASSEMBLY)
29
30 #include "WasmParser.h"
31 #include <wtf/DataLog.h>
32
33 namespace JSC { namespace Wasm {
34
35 enum class BlockType {
36     If,
37     Block,
38     Loop
39 };
40
41 template<typename Context>
42 class FunctionParser : public Parser {
43 public:
44     typedef typename Context::ExpressionType ExpressionType;
45     typedef typename Context::ControlType ControlType;
46     typedef typename Context::ExpressionList ExpressionList;
47
48     FunctionParser(Context&, const uint8_t* functionStart, size_t functionLength, const Signature*, const FunctionIndexSpace&);
49
50     bool WARN_UNUSED_RETURN parse();
51
52     struct ControlEntry {
53         ExpressionList enclosedExpressionStack;
54         ControlType controlData;
55     };
56
57 private:
58     static const bool verbose = false;
59
60     bool WARN_UNUSED_RETURN parseBody();
61     bool WARN_UNUSED_RETURN parseExpression(OpType);
62     bool WARN_UNUSED_RETURN parseUnreachableExpression(OpType);
63     bool WARN_UNUSED_RETURN addReturn();
64     bool WARN_UNUSED_RETURN unifyControl(Vector<ExpressionType>&, unsigned level);
65
66     bool WARN_UNUSED_RETURN popExpressionStack(ExpressionType& result);
67
68     template<OpType>
69     bool WARN_UNUSED_RETURN unaryCase();
70
71     template<OpType>
72     bool WARN_UNUSED_RETURN binaryCase();
73
74     void setErrorMessage(String&& message) { m_context.setErrorMessage(WTFMove(message)); }
75
76     Context& m_context;
77     ExpressionList m_expressionStack;
78     Vector<ControlEntry> m_controlStack;
79     const Signature* m_signature;
80     const FunctionIndexSpace& m_functionIndexSpace;
81     unsigned m_unreachableBlocks { 0 };
82 };
83
84 template<typename Context>
85 FunctionParser<Context>::FunctionParser(Context& context, const uint8_t* functionStart, size_t functionLength, const Signature* signature, const FunctionIndexSpace& functionIndexSpace)
86     : Parser(functionStart, functionLength)
87     , m_context(context)
88     , m_signature(signature)
89     , m_functionIndexSpace(functionIndexSpace)
90 {
91     if (verbose)
92         dataLogLn("Parsing function starting at: ", (uintptr_t)functionStart, " of length: ", functionLength);
93 }
94
95 template<typename Context>
96 bool FunctionParser<Context>::parse()
97 {
98     if (!m_context.addArguments(m_signature->arguments))
99         return false;
100
101     uint32_t localCount;
102     if (!parseVarUInt32(localCount))
103         return false;
104
105     for (uint32_t i = 0; i < localCount; ++i) {
106         uint32_t numberOfLocals;
107         if (!parseVarUInt32(numberOfLocals))
108             return false;
109
110         Type typeOfLocal;
111         if (!parseValueType(typeOfLocal))
112             return false;
113
114         if (!m_context.addLocal(typeOfLocal, numberOfLocals))
115             return false;
116     }
117
118     return parseBody();
119 }
120
121 template<typename Context>
122 bool FunctionParser<Context>::parseBody()
123 {
124     while (true) {
125         uint8_t op;
126         if (!parseUInt8(op) || !isValidOpType(op)) {
127             if (verbose)
128                 WTF::dataLogLn("attempted to decode invalid op: ", RawPointer(reinterpret_cast<void*>(op)), " at offset: ", RawPointer(reinterpret_cast<void*>(m_offset)));
129             return false;
130         }
131
132         if (verbose) {
133             dataLogLn("processing op (", m_unreachableBlocks, "): ",  RawPointer(reinterpret_cast<void*>(op)), " at offset: ", RawPointer(reinterpret_cast<void*>(m_offset)));
134             m_context.dump(m_controlStack, m_expressionStack);
135         }
136
137         if (op == OpType::End && !m_controlStack.size())
138             return m_unreachableBlocks ? true : addReturn();
139
140         if (m_unreachableBlocks) {
141             if (!parseUnreachableExpression(static_cast<OpType>(op))) {
142                 if (verbose)
143                     dataLogLn("failed to process unreachable op:", op);
144                 return false;
145             }
146         } else if (!parseExpression(static_cast<OpType>(op))) {
147             if (verbose)
148                 dataLogLn("failed to process op:", op);
149             return false;
150         }
151
152     }
153
154     RELEASE_ASSERT_NOT_REACHED();
155 }
156
157 template<typename Context>
158 bool FunctionParser<Context>::addReturn()
159 {
160     ExpressionList returnValues;
161     if (m_signature->returnType != Void) {
162         ExpressionType returnValue;
163         if (!popExpressionStack(returnValue))
164             return false;
165         returnValues.append(returnValue);
166     }
167
168     m_unreachableBlocks = 1;
169     return m_context.addReturn(returnValues);
170 }
171
172 template<typename Context>
173 template<OpType op>
174 bool FunctionParser<Context>::binaryCase()
175 {
176     ExpressionType right;
177     if (!popExpressionStack(right))
178         return false;
179
180     ExpressionType left;
181     if (!popExpressionStack(left))
182         return false;
183
184     ExpressionType result;
185     if (!m_context.template addOp<op>(left, right, result))
186         return false;
187     m_expressionStack.append(result);
188     return true;
189 }
190
191 template<typename Context>
192 template<OpType op>
193 bool FunctionParser<Context>::unaryCase()
194 {
195     ExpressionType value;
196     if (!popExpressionStack(value))
197         return false;
198
199     ExpressionType result;
200     if (!m_context.template addOp<op>(value, result))
201         return false;
202     m_expressionStack.append(result);
203     return true;
204 }
205
206 template<typename Context>
207 bool FunctionParser<Context>::parseExpression(OpType op)
208 {
209     switch (op) {
210 #define CREATE_CASE(name, id, b3op, inc) case OpType::name: return binaryCase<OpType::name>();
211     FOR_EACH_WASM_SIMPLE_BINARY_OP(CREATE_CASE)
212 #undef CREATE_CASE
213
214     case OpType::F32ConvertUI64: return unaryCase<OpType::F32ConvertUI64>();
215     case OpType::F64ConvertUI64: return unaryCase<OpType::F64ConvertUI64>();
216     case OpType::F32Nearest: return unaryCase<OpType::F32Nearest>();
217     case OpType::F64Nearest: return unaryCase<OpType::F64Nearest>();
218     case OpType::F32Trunc: return unaryCase<OpType::F32Trunc>();
219     case OpType::F64Trunc: return unaryCase<OpType::F64Trunc>();
220     case OpType::I32Ctz: return unaryCase<OpType::I32Ctz>();
221     case OpType::I64Ctz: return unaryCase<OpType::I64Ctz>();
222     case OpType::I32Popcnt: return unaryCase<OpType::I32Popcnt>();
223     case OpType::I64Popcnt: return unaryCase<OpType::I64Popcnt>();
224     case OpType::I32TruncSF32: return unaryCase<OpType::I32TruncSF32>();
225     case OpType::I32TruncUF32: return unaryCase<OpType::I32TruncUF32>();
226     case OpType::I32TruncSF64: return unaryCase<OpType::I32TruncSF64>();
227     case OpType::I32TruncUF64: return unaryCase<OpType::I32TruncUF64>();
228     case OpType::I64TruncSF32: return unaryCase<OpType::I64TruncSF32>();
229     case OpType::I64TruncUF32: return unaryCase<OpType::I64TruncUF32>();
230     case OpType::I64TruncSF64: return unaryCase<OpType::I64TruncSF64>();
231     case OpType::I64TruncUF64: return unaryCase<OpType::I64TruncUF64>();
232 #define CREATE_CASE(name, id, b3op, inc) case OpType::name: return unaryCase<OpType::name>();
233     FOR_EACH_WASM_SIMPLE_UNARY_OP(CREATE_CASE)
234 #undef CREATE_CASE
235
236     case OpType::Select: {
237         ExpressionType condition;
238         if (!popExpressionStack(condition))
239             return false;
240
241         ExpressionType zero;
242         if (!popExpressionStack(zero))
243             return false;
244
245         ExpressionType nonZero;
246         if (!popExpressionStack(nonZero))
247             return false;
248
249         ExpressionType result;
250         if (!m_context.addSelect(condition, nonZero, zero, result))
251             return false;
252
253         m_expressionStack.append(result);
254         return true;
255     }
256
257 #define CREATE_CASE(name, id, b3op, inc) case OpType::name:
258     FOR_EACH_WASM_MEMORY_LOAD_OP(CREATE_CASE) {
259         uint32_t alignment;
260         if (!parseVarUInt32(alignment))
261             return false;
262
263         uint32_t offset;
264         if (!parseVarUInt32(offset))
265             return false;
266
267         ExpressionType pointer;
268         if (!popExpressionStack(pointer))
269             return false;
270
271         ExpressionType result;
272         if (!m_context.load(static_cast<LoadOpType>(op), pointer, result, offset))
273             return false;
274         m_expressionStack.append(result);
275         return true;
276     }
277
278     FOR_EACH_WASM_MEMORY_STORE_OP(CREATE_CASE) {
279         uint32_t alignment;
280         if (!parseVarUInt32(alignment))
281             return false;
282
283         uint32_t offset;
284         if (!parseVarUInt32(offset))
285             return false;
286
287         ExpressionType value;
288         if (!popExpressionStack(value))
289             return false;
290
291         ExpressionType pointer;
292         if (!popExpressionStack(pointer))
293             return false;
294
295         return m_context.store(static_cast<StoreOpType>(op), pointer, value, offset);
296     }
297 #undef CREATE_CASE
298
299     case OpType::F32Const:
300     case OpType::I32Const: {
301         uint32_t constant;
302         if (!parseVarUInt32(constant))
303             return false;
304         m_expressionStack.append(m_context.addConstant(I32, constant));
305         return true;
306     }
307
308     case OpType::F64Const:
309     case OpType::I64Const: {
310         uint64_t constant;
311         if (!parseVarUInt64(constant))
312             return false;
313         m_expressionStack.append(m_context.addConstant(I64, constant));
314         return true;
315     }
316
317     case OpType::GetLocal: {
318         uint32_t index;
319         if (!parseVarUInt32(index))
320             return false;
321         ExpressionType result;
322         if (!m_context.getLocal(index, result))
323             return false;
324
325         m_expressionStack.append(result);
326         return true;
327     }
328
329     case OpType::SetLocal: {
330         uint32_t index;
331         if (!parseVarUInt32(index))
332             return false;
333         ExpressionType value;
334         if (!popExpressionStack(value))
335             return false;
336         return m_context.setLocal(index, value);
337     }
338
339     case OpType::TeeLocal: {
340         uint32_t index;
341         if (!parseVarUInt32(index))
342             return false;
343         if (!m_expressionStack.size())
344             return false;
345         return m_context.setLocal(index, m_expressionStack.last());
346     }
347
348     case OpType::Call: {
349         uint32_t functionIndex;
350         if (!parseVarUInt32(functionIndex))
351             return false;
352
353         if (functionIndex >= m_functionIndexSpace.size())
354             return false;
355
356         const Signature* calleeSignature = m_functionIndexSpace[functionIndex].signature;
357
358         if (calleeSignature->arguments.size() > m_expressionStack.size())
359             return false;
360
361         size_t firstArgumentIndex = m_expressionStack.size() - calleeSignature->arguments.size();
362         Vector<ExpressionType> args;
363         args.reserveInitialCapacity(calleeSignature->arguments.size());
364         for (unsigned i = firstArgumentIndex; i < m_expressionStack.size(); ++i)
365             args.append(m_expressionStack[i]);
366         m_expressionStack.shrink(firstArgumentIndex);
367
368         ExpressionType result = Context::emptyExpression;
369         if (!m_context.addCall(functionIndex, calleeSignature, args, result))
370             return false;
371
372         if (result != Context::emptyExpression)
373             m_expressionStack.append(result);
374
375         return true;
376     }
377
378     case OpType::Block: {
379         Type inlineSignature;
380         if (!parseResultType(inlineSignature))
381             return false;
382
383         m_controlStack.append({ WTFMove(m_expressionStack), m_context.addBlock(inlineSignature) });
384         m_expressionStack = ExpressionList();
385         return true;
386     }
387
388     case OpType::Loop: {
389         Type inlineSignature;
390         if (!parseResultType(inlineSignature))
391             return false;
392
393         m_controlStack.append({ WTFMove(m_expressionStack), m_context.addLoop(inlineSignature) });
394         m_expressionStack = ExpressionList();
395         return true;
396     }
397
398     case OpType::If: {
399         Type inlineSignature;
400         if (!parseResultType(inlineSignature))
401             return false;
402
403         ExpressionType condition;
404         if (!popExpressionStack(condition))
405             return false;
406
407         ControlType control;
408         if (!m_context.addIf(condition, inlineSignature, control))
409             return false;
410
411         m_controlStack.append({ WTFMove(m_expressionStack), control });
412         m_expressionStack = ExpressionList();
413         return true;
414     }
415
416     case OpType::Else: {
417         if (!m_controlStack.size()) {
418             setErrorMessage("Attempted to use else block at the top-level of a function");
419             return false;
420         }
421
422         if (!m_context.addElse(m_controlStack.last().controlData, m_expressionStack))
423             return false;
424         m_expressionStack.shrink(0);
425         return true;
426     }
427
428     case OpType::Br:
429     case OpType::BrIf: {
430         uint32_t target;
431         if (!parseVarUInt32(target) || target >= m_controlStack.size())
432             return false;
433
434         ExpressionType condition = Context::emptyExpression;
435         if (op == OpType::BrIf) {
436             if (!popExpressionStack(condition))
437                 return false;
438         } else
439             m_unreachableBlocks = 1;
440
441         ControlType& data = m_controlStack[m_controlStack.size() - 1 - target].controlData;
442
443         return m_context.addBranch(data, condition, m_expressionStack);
444     }
445
446     case OpType::BrTable: {
447         uint32_t numberOfTargets;
448         if (!parseVarUInt32(numberOfTargets))
449             return false;
450
451         Vector<ControlType*> targets;
452         if (!targets.tryReserveCapacity(numberOfTargets))
453             return false;
454
455         for (uint32_t i = 0; i < numberOfTargets; ++i) {
456             uint32_t target;
457             if (!parseVarUInt32(target))
458                 return false;
459
460             if (target >= m_controlStack.size())
461                 return false;
462
463             targets.uncheckedAppend(&m_controlStack[m_controlStack.size() - 1 - target].controlData);
464         }
465
466         uint32_t defaultTarget;
467         if (!parseVarUInt32(defaultTarget))
468             return false;
469
470         if (defaultTarget >= m_controlStack.size())
471             return false;
472
473         ExpressionType condition;
474         if (!popExpressionStack(condition))
475             return false;
476         
477         if (!m_context.addSwitch(condition, targets, m_controlStack[m_controlStack.size() - 1 - defaultTarget].controlData, m_expressionStack))
478             return false;
479
480         m_unreachableBlocks = 1;
481         return true;
482     }
483
484     case OpType::Return: {
485         return addReturn();
486     }
487
488     case OpType::End: {
489         ControlEntry data = m_controlStack.takeLast();
490         // FIXME: This is a little weird in that it will modify the expressionStack for the result of the block.
491         // That's a little too effectful for me but I don't have a better API right now.
492         // see: https://bugs.webkit.org/show_bug.cgi?id=164353
493         if (!m_context.endBlock(data, m_expressionStack))
494             return false;
495         m_expressionStack.swap(data.enclosedExpressionStack);
496         return true;
497     }
498
499     case OpType::Unreachable: {
500         m_unreachableBlocks = 1;
501         return true;
502     }
503
504     case OpType::Drop: {
505         if (!m_expressionStack.size()) {
506             setErrorMessage("Attempted to drop an expression from an empty stack.");
507             return false;
508         }
509         m_expressionStack.takeLast();
510         return true;
511     }
512
513     case OpType::Nop: {
514         return true;
515     }
516
517     case OpType::GrowMemory:
518     case OpType::CurrentMemory:
519     case OpType::GetGlobal:
520     case OpType::SetGlobal:
521     case OpType::CallIndirect: {
522         // FIXME: Not yet implemented.
523         return false;
524     }
525     }
526
527     ASSERT_NOT_REACHED();
528 }
529
530 template<typename Context>
531 bool FunctionParser<Context>::parseUnreachableExpression(OpType op)
532 {
533     ASSERT(m_unreachableBlocks);
534     switch (op) {
535     case OpType::Else: {
536         if (m_unreachableBlocks > 1)
537             return true;
538
539         ControlEntry& data = m_controlStack.last();
540         m_unreachableBlocks = 0;
541         if (!m_context.addElseToUnreachable(data.controlData))
542             return false;
543         m_expressionStack.shrink(0);
544         return true;
545     }
546
547     case OpType::End: {
548         if (m_unreachableBlocks == 1) {
549             ControlEntry data = m_controlStack.takeLast();
550             if (!m_context.addEndToUnreachable(data))
551                 return false;
552             m_expressionStack.swap(data.enclosedExpressionStack);
553         }
554         m_unreachableBlocks--;
555         return true;
556     }
557
558     case OpType::Loop:
559     case OpType::If:
560     case OpType::Block: {
561         m_unreachableBlocks++;
562         return true;
563     }
564
565     // two immediate cases
566     case OpType::Br:
567     case OpType::BrIf: {
568         uint32_t unused;
569         if (!parseVarUInt32(unused))
570             return false;
571         return parseVarUInt32(unused);
572     }
573
574     // one immediate cases
575     case OpType::F32Const:
576     case OpType::I32Const:
577     case OpType::F64Const:
578     case OpType::I64Const:
579     case OpType::SetLocal:
580     case OpType::GetLocal: {
581         uint32_t unused;
582         return parseVarUInt32(unused);
583     }
584
585     default:
586         break;
587     }
588     return true;
589 }
590
591 template<typename Context>
592 bool FunctionParser<Context>::popExpressionStack(ExpressionType& result)
593 {
594     if (m_expressionStack.size()) {
595         result = m_expressionStack.takeLast();
596         return true;
597     }
598
599     setErrorMessage("Attempted to use a stack value when none existed");
600     return false;
601 }
602
603 } } // namespace JSC::Wasm
604
605 #endif // ENABLE(WEBASSEMBLY)