Wasm should support call_indirect
[WebKit-https.git] / Source / JavaScriptCore / wasm / WasmValidate.cpp
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 #include "config.h"
27 #include "WasmValidate.h"
28
29 #if ENABLE(WEBASSEMBLY)
30
31 #include "WasmFunctionParser.h"
32 #include <wtf/CommaPrinter.h>
33 #include <wtf/text/StringBuilder.h>
34
35 namespace JSC { namespace Wasm {
36
37 class Validate {
38 public:
39     class ControlData {
40     public:
41         ControlData(BlockType type, Type signature)
42             : m_blockType(type)
43             , m_signature(signature)
44         {
45         }
46
47         ControlData()
48         {
49         }
50
51         void dump(PrintStream& out) const
52         {
53             switch (type()) {
54             case BlockType::If:
55                 out.print("If:    ");
56                 break;
57             case BlockType::Block:
58                 out.print("Block: ");
59                 break;
60             case BlockType::Loop:
61                 out.print("Loop:  ");
62                 break;
63             }
64         }
65
66         bool hasNonVoidSignature() const { return m_signature != Void; }
67
68         BlockType type() const { return m_blockType; }
69         Type signature() const { return m_signature; }
70     private:
71         BlockType m_blockType;
72         Type m_signature;
73     };
74     typedef Type ExpressionType;
75     typedef ControlData ControlType;
76     typedef Vector<ExpressionType, 1> ExpressionList;
77     typedef FunctionParser<Validate>::ControlEntry ControlEntry;
78
79     static const ExpressionType emptyExpression = Void;
80
81     bool WARN_UNUSED_RETURN addArguments(const Vector<Type>&);
82     bool WARN_UNUSED_RETURN addLocal(Type, uint32_t);
83     ExpressionType addConstant(Type type, uint64_t) { return type; }
84
85     // Locals
86     bool WARN_UNUSED_RETURN getLocal(uint32_t index, ExpressionType& result);
87     bool WARN_UNUSED_RETURN setLocal(uint32_t index, ExpressionType value);
88
89     // Memory
90     bool WARN_UNUSED_RETURN load(LoadOpType, ExpressionType pointer, ExpressionType& result, uint32_t offset);
91     bool WARN_UNUSED_RETURN store(StoreOpType, ExpressionType pointer, ExpressionType value, uint32_t offset);
92
93     // Basic operators
94     template<OpType>
95     bool WARN_UNUSED_RETURN addOp(ExpressionType arg, ExpressionType& result);
96     template<OpType>
97     bool WARN_UNUSED_RETURN addOp(ExpressionType left, ExpressionType right, ExpressionType& result);
98     bool WARN_UNUSED_RETURN addSelect(ExpressionType condition, ExpressionType nonZero, ExpressionType zero, ExpressionType& result);
99
100     // Control flow
101     ControlData WARN_UNUSED_RETURN addBlock(Type signature);
102     ControlData WARN_UNUSED_RETURN addLoop(Type signature);
103     bool WARN_UNUSED_RETURN addIf(ExpressionType condition, Type signature, ControlData& result);
104     bool WARN_UNUSED_RETURN addElse(ControlData&, const ExpressionList&);
105     bool WARN_UNUSED_RETURN addElseToUnreachable(ControlData&);
106
107     bool WARN_UNUSED_RETURN addReturn(const ExpressionList& returnValues);
108     bool WARN_UNUSED_RETURN addBranch(ControlData&, ExpressionType condition, const ExpressionList& expressionStack);
109     bool WARN_UNUSED_RETURN addSwitch(ExpressionType condition, const Vector<ControlData*>& targets, ControlData& defaultTarget, const ExpressionList& expressionStack);
110     bool WARN_UNUSED_RETURN endBlock(ControlEntry&, ExpressionList& expressionStack);
111     bool WARN_UNUSED_RETURN addEndToUnreachable(ControlEntry&);
112
113     // Calls
114     bool WARN_UNUSED_RETURN addCall(unsigned calleeIndex, const Signature*, const Vector<ExpressionType>& args, ExpressionType& result);
115     bool WARN_UNUSED_RETURN addCallIndirect(const Signature*, const Vector<ExpressionType>& args, ExpressionType& result);
116
117     void dump(const Vector<ControlEntry>& controlStack, const ExpressionList& expressionStack);
118
119     bool hasMemory() const { return !!m_memory; }
120
121     void setErrorMessage(String&& message) { ASSERT(m_errorMessage.isNull()); m_errorMessage = WTFMove(message); }
122     String errorMessage() const { return m_errorMessage; }
123     Validate(ExpressionType returnType, const MemoryInformation& memory)
124         : m_returnType(returnType)
125         , m_memory(memory)
126     {
127     }
128
129 private:
130     bool unify(Type, Type);
131     bool unify(const ExpressionList&, const ControlData&);
132
133     bool checkBranchTarget(ControlData& target, const ExpressionList& expressionStack);
134
135     ExpressionType m_returnType;
136     Vector<Type> m_locals;
137     String m_errorMessage;
138     const MemoryInformation& m_memory;
139 };
140
141 bool Validate::addArguments(const Vector<Type>& args)
142 {
143     for (Type arg : args) {
144         if (!addLocal(arg, 1))
145             return false;
146     }
147     return true;
148 }
149
150 bool Validate::addLocal(Type type, uint32_t count)
151 {
152     if (!m_locals.tryReserveCapacity(m_locals.size() + count))
153         return false;
154
155     for (uint32_t i = 0; i < count; ++i)
156         m_locals.uncheckedAppend(type);
157     return true;
158 }
159
160 bool Validate::getLocal(uint32_t index, ExpressionType& result)
161 {
162     if (index < m_locals.size()) {
163         result = m_locals[index];
164         return true;
165     }
166     m_errorMessage = ASCIILiteral("Attempt to use unknown local.");
167     return false;
168 }
169
170 bool Validate::setLocal(uint32_t index, ExpressionType value)
171 {
172     ExpressionType localType;
173     if (!getLocal(index, localType))
174         return false;
175
176     if (localType == value)
177         return true;
178
179     m_errorMessage = makeString("Attempt to set local with type: ", toString(localType), " with a variable of type: ", toString(value));
180     return false;
181 }
182
183 Validate::ControlType Validate::addBlock(Type signature)
184 {
185     return ControlData(BlockType::Block, signature);
186 }
187
188 Validate::ControlType Validate::addLoop(Type signature)
189 {
190     return ControlData(BlockType::Loop, signature);
191 }
192
193 bool Validate::addSelect(ExpressionType condition, ExpressionType nonZero, ExpressionType zero, ExpressionType& result)
194 {
195     if (condition != I32) {
196         m_errorMessage = makeString("Attempting to use ", toString(condition), " as the condition for select");
197         return false;
198     }
199
200     if (nonZero != zero) {
201         m_errorMessage = makeString("Result types of select don't match. Got: ", toString(nonZero), " and ", toString(zero));
202         return false;
203     }
204
205     result = zero;
206     return true;
207 }
208
209 bool Validate::addIf(ExpressionType condition, Type signature, ControlType& result)
210 {
211     if (condition != I32) {
212         m_errorMessage = makeString("Attempting to use ", toString(condition), " as the condition for an if block");
213         return false;
214     }
215     result = ControlData(BlockType::If, signature);
216     return true;
217 }
218
219 bool Validate::addElse(ControlType& current, const ExpressionList& values)
220 {
221     if (!unify(values, current)) {
222         ASSERT(errorMessage());
223         return false;
224     }
225
226     return addElseToUnreachable(current);
227 }
228
229 bool Validate::addElseToUnreachable(ControlType& current)
230 {
231     if (current.type() != BlockType::If) {
232         m_errorMessage = makeString("Attempting to add else block to something other than an if");
233         return false;
234     }
235
236     current = ControlData(BlockType::Block, current.signature());
237     return true;
238 }
239
240 bool Validate::addReturn(const ExpressionList& returnValues)
241 {
242     if (m_returnType == Void)
243         return true;
244     ASSERT(returnValues.size() == 1);
245
246     if (m_returnType == returnValues[0])
247         return true;
248
249     m_errorMessage = makeString("Attempting to add return with type: ", toString(returnValues[0]), " but function expects return with type: ", toString(m_returnType));
250     return false;
251 }
252
253 bool Validate::checkBranchTarget(ControlType& target, const ExpressionList& expressionStack)
254     {
255         if (target.type() == BlockType::Loop)
256             return true;
257
258         if (target.signature() == Void)
259             return true;
260
261         if (!expressionStack.size()) {
262             m_errorMessage = makeString("Attempting to branch to block with expected type: ", toString(target.signature()), " but the stack was empty");
263             return false;
264         }
265
266         if (target.signature() == expressionStack.last())
267             return true;
268
269         m_errorMessage = makeString("Attempting to branch to block with expected type: ", toString(target.signature()), " but stack has type: ", toString(target.signature()));
270         return false;
271     }
272
273 bool Validate::addBranch(ControlType& target, ExpressionType condition, const ExpressionList& stack)
274 {
275     // Void means this is an unconditional branch.
276     if (condition != Void && condition != I32) {
277         m_errorMessage = makeString("Attempting to add a conditional branch with condition type: ", toString(condition), " but expected i32.");
278         return false;
279     }
280
281     return checkBranchTarget(target, stack);
282 }
283
284 bool Validate::addSwitch(ExpressionType condition, const Vector<ControlData*>& targets, ControlData& defaultTarget, const ExpressionList& expressionStack)
285 {
286     if (condition != I32) {
287         m_errorMessage = makeString("Attempting to add a br_table with condition type: ", toString(condition), " but expected i32.");
288         return false;
289     }
290
291     for (auto target : targets) {
292         if (defaultTarget.signature() != target->signature()) {
293             m_errorMessage = makeString("Attempting to add a br_table with different expected types. Default target has type: ", toString(defaultTarget.signature()), " but case has type: ", toString(target->signature()));
294             return false;
295         }
296     }
297
298     return checkBranchTarget(defaultTarget, expressionStack);
299 }
300
301 bool Validate::endBlock(ControlEntry& entry, ExpressionList& stack)
302 {
303     ControlData& block = entry.controlData;
304     if (block.signature() == Void)
305         return true;
306
307     if (!stack.size()) {
308         m_errorMessage = makeString("Block fallthough expected type: ", toString(block.signature()), " but the stack was empty");
309         return false;
310     }
311
312     if (block.signature() == stack.last()) {
313         entry.enclosedExpressionStack.append(block.signature());
314         return true;
315     }
316
317     m_errorMessage = makeString("Block fallthrough has expected type: ", toString(block.signature()), " but produced type: ", toString(block.signature()));
318     return false;
319 }
320
321 bool Validate::addEndToUnreachable(ControlEntry& entry)
322 {
323     if (entry.controlData.signature() != Void)
324         entry.enclosedExpressionStack.append(entry.controlData.signature());
325     return true;
326 }
327
328 bool Validate::addCall(unsigned, const Signature* signature, const Vector<ExpressionType>& args, ExpressionType& result)
329 {
330     if (signature->arguments.size() != args.size()) {
331         StringBuilder builder;
332         builder.append("Arity mismatch in call, expected: ");
333         builder.appendNumber(signature->arguments.size());
334         builder.append(" but got: ");
335         builder.appendNumber(args.size());
336         m_errorMessage = builder.toString();
337         return false;
338     }
339
340     for (unsigned i = 0; i < args.size(); ++i) {
341         if (args[i] != signature->arguments[i]) {
342             m_errorMessage = makeString("Expected argument type: ", toString(signature->arguments[i]), " does not match passed argument type: ", toString(args[i]));
343             return false;
344         }
345     }
346
347     result = signature->returnType;
348     return true;
349 }
350
351 bool Validate::addCallIndirect(const Signature* signature, const Vector<ExpressionType>& args, ExpressionType& result)
352 {
353     const auto argumentCount = signature->arguments.size();
354     if (argumentCount != args.size() - 1) {
355         StringBuilder builder;
356         builder.append("Arity mismatch in call_indirect, expected: ");
357         builder.appendNumber(signature->arguments.size());
358         builder.append(" but got: ");
359         builder.appendNumber(args.size());
360         m_errorMessage = builder.toString();
361         return false;
362     }
363
364     for (unsigned i = 0; i < argumentCount; ++i) {
365         if (args[i] != signature->arguments[i]) {
366             m_errorMessage = makeString("Expected argument type: ", toString(signature->arguments[i]), " does not match passed argument type: ", toString(args[i]));
367             return false;
368         }
369     }
370
371     if (args.last() != I32) {
372         m_errorMessage = makeString("Expected call_indirect target index to have type: i32 but got type: ", toString(args.last()));
373         return false;
374     }
375     
376     result = signature->returnType;
377     return true;
378 }
379
380 bool Validate::unify(const ExpressionList& values, const ControlType& block)
381 {
382     ASSERT(values.size() <= 1);
383     if (block.signature() == Void)
384         return true;
385
386     if (!values.size()) {
387         m_errorMessage = makeString("Block has non-void signature but has no stack entries on exit");
388         return false;
389     }
390
391     if (values[0] == block.signature())
392         return true;
393
394     m_errorMessage = makeString("Expected control flow to return value with type: ", toString(block.signature()), " but got value with type: ", toString(values[0]));
395     return false;
396 }
397
398 void Validate::dump(const Vector<ControlEntry>&, const ExpressionList&)
399 {
400     // If you need this then you should fix the validator's error messages instead...
401     // Think of this as penance for the sin of bad error messages.
402 }
403
404 String validateFunction(const uint8_t* source, size_t length, const Signature* signature, const ImmutableFunctionIndexSpace& functionIndexSpace, const ModuleInformation& info)
405 {
406     Validate context(signature->returnType, info.memory);
407     FunctionParser<Validate> validator(context, source, length, signature, functionIndexSpace, info);
408
409     if (!validator.parse()) {
410         // FIXME: add better location information here. see: https://bugs.webkit.org/show_bug.cgi?id=164288
411         // FIXME: We should never not have an error message if we return false.
412         // see: https://bugs.webkit.org/show_bug.cgi?id=164354
413         if (context.errorMessage().isNull())
414             return "Unknown error";
415         return context.errorMessage();
416     }
417
418     return String();
419 }
420
421 } } // namespace JSC::Wasm
422
423 #include "WasmValidateInlines.h"
424
425 #endif // ENABLE(WEBASSEMBLY)