a024885820dd3735ec355e850b3f41a9df48c8b6
[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
114     bool WARN_UNUSED_RETURN addCall(unsigned calleeIndex, const Signature*, const Vector<ExpressionType>& args, ExpressionType& result);
115
116     void dump(const Vector<ControlEntry>& controlStack, const ExpressionList& expressionStack);
117
118     bool hasMemory() const { return !!m_memory; }
119
120     void setErrorMessage(String&& message) { ASSERT(m_errorMessage.isNull()); m_errorMessage = WTFMove(message); }
121     String errorMessage() const { return m_errorMessage; }
122     Validate(ExpressionType returnType, const MemoryInformation& memory)
123         : m_returnType(returnType)
124         , m_memory(memory)
125     {
126     }
127
128 private:
129     bool unify(Type, Type);
130     bool unify(const ExpressionList&, const ControlData&);
131
132     bool checkBranchTarget(ControlData& target, const ExpressionList& expressionStack);
133
134     ExpressionType m_returnType;
135     Vector<Type> m_locals;
136     String m_errorMessage;
137     const MemoryInformation& m_memory;
138 };
139
140 bool Validate::addArguments(const Vector<Type>& args)
141 {
142     for (Type arg : args) {
143         if (!addLocal(arg, 1))
144             return false;
145     }
146     return true;
147 }
148
149 bool Validate::addLocal(Type type, uint32_t count)
150 {
151     if (!m_locals.tryReserveCapacity(m_locals.size() + count))
152         return false;
153
154     for (uint32_t i = 0; i < count; ++i)
155         m_locals.uncheckedAppend(type);
156     return true;
157 }
158
159 bool Validate::getLocal(uint32_t index, ExpressionType& result)
160 {
161     if (index < m_locals.size()) {
162         result = m_locals[index];
163         return true;
164     }
165     m_errorMessage = ASCIILiteral("Attempt to use unknown local.");
166     return false;
167 }
168
169 bool Validate::setLocal(uint32_t index, ExpressionType value)
170 {
171     ExpressionType localType;
172     if (!getLocal(index, localType))
173         return false;
174
175     if (localType == value)
176         return true;
177
178     m_errorMessage = makeString("Attempt to set local with type: ", toString(localType), " with a variable of type: ", toString(value));
179     return false;
180 }
181
182 Validate::ControlType Validate::addBlock(Type signature)
183 {
184     return ControlData(BlockType::Block, signature);
185 }
186
187 Validate::ControlType Validate::addLoop(Type signature)
188 {
189     return ControlData(BlockType::Loop, signature);
190 }
191
192 bool Validate::addSelect(ExpressionType condition, ExpressionType nonZero, ExpressionType zero, ExpressionType& result)
193 {
194     if (condition != I32) {
195         m_errorMessage = makeString("Attempting to use ", toString(condition), " as the condition for select");
196         return false;
197     }
198
199     if (nonZero != zero) {
200         m_errorMessage = makeString("Result types of select don't match. Got: ", toString(nonZero), " and ", toString(zero));
201         return false;
202     }
203
204     result = zero;
205     return true;
206 }
207
208 bool Validate::addIf(ExpressionType condition, Type signature, ControlType& result)
209 {
210     if (condition != I32) {
211         m_errorMessage = makeString("Attempting to use ", toString(condition), " as the condition for an if block");
212         return false;
213     }
214     result = ControlData(BlockType::If, signature);
215     return true;
216 }
217
218 bool Validate::addElse(ControlType& current, const ExpressionList& values)
219 {
220     if (!unify(values, current)) {
221         ASSERT(errorMessage());
222         return false;
223     }
224
225     return addElseToUnreachable(current);
226 }
227
228 bool Validate::addElseToUnreachable(ControlType& current)
229 {
230     if (current.type() != BlockType::If) {
231         m_errorMessage = makeString("Attempting to add else block to something other than an if");
232         return false;
233     }
234
235     current = ControlData(BlockType::Block, current.signature());
236     return true;
237 }
238
239 bool Validate::addReturn(const ExpressionList& returnValues)
240 {
241     if (m_returnType == Void)
242         return true;
243     ASSERT(returnValues.size() == 1);
244
245     if (m_returnType == returnValues[0])
246         return true;
247
248     m_errorMessage = makeString("Attempting to add return with type: ", toString(returnValues[0]), " but function expects return with type: ", toString(m_returnType));
249     return false;
250 }
251
252 bool Validate::checkBranchTarget(ControlType& target, const ExpressionList& expressionStack)
253     {
254         if (target.type() == BlockType::Loop)
255             return true;
256
257         if (target.signature() == Void)
258             return true;
259
260         if (!expressionStack.size()) {
261             m_errorMessage = makeString("Attempting to branch to block with expected type: ", toString(target.signature()), " but the stack was empty");
262             return false;
263         }
264
265         if (target.signature() == expressionStack.last())
266             return true;
267
268         m_errorMessage = makeString("Attempting to branch to block with expected type: ", toString(target.signature()), " but stack has type: ", toString(target.signature()));
269         return false;
270     }
271
272 bool Validate::addBranch(ControlType& target, ExpressionType condition, const ExpressionList& stack)
273 {
274     // Void means this is an unconditional branch.
275     if (condition != Void && condition != I32) {
276         m_errorMessage = makeString("Attempting to add a conditional branch with condition type: ", toString(condition), " but expected i32.");
277         return false;
278     }
279
280     return checkBranchTarget(target, stack);
281 }
282
283 bool Validate::addSwitch(ExpressionType condition, const Vector<ControlData*>& targets, ControlData& defaultTarget, const ExpressionList& expressionStack)
284 {
285     if (condition != I32) {
286         m_errorMessage = makeString("Attempting to add a br_table with condition type: ", toString(condition), " but expected i32.");
287         return false;
288     }
289
290     for (auto target : targets) {
291         if (defaultTarget.signature() != target->signature()) {
292             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()));
293             return false;
294         }
295     }
296
297     return checkBranchTarget(defaultTarget, expressionStack);
298 }
299
300 bool Validate::endBlock(ControlEntry& entry, ExpressionList& stack)
301 {
302     ControlData& block = entry.controlData;
303     if (block.signature() == Void)
304         return true;
305
306     if (!stack.size()) {
307         m_errorMessage = makeString("Block fallthough expected type: ", toString(block.signature()), " but the stack was empty");
308         return false;
309     }
310
311     if (block.signature() == stack.last()) {
312         entry.enclosedExpressionStack.append(block.signature());
313         return true;
314     }
315
316     m_errorMessage = makeString("Block fallthrough has expected type: ", toString(block.signature()), " but produced type: ", toString(block.signature()));
317     return false;
318 }
319
320 bool Validate::addEndToUnreachable(ControlEntry& entry)
321 {
322     if (entry.controlData.signature() != Void)
323         entry.enclosedExpressionStack.append(entry.controlData.signature());
324     return true;
325 }
326
327 bool Validate::addCall(unsigned, const Signature* signature, const Vector<ExpressionType>& args, ExpressionType& result)
328 {
329     if (signature->arguments.size() != args.size()) {
330         StringBuilder builder;
331         builder.append("Arity mismatch in call, expected: ");
332         builder.appendNumber(signature->arguments.size());
333         builder.append(" but got: ");
334         builder.appendNumber(args.size());
335         m_errorMessage = builder.toString();
336         return false;
337     }
338
339     for (unsigned i = 0; i < args.size(); ++i) {
340         if (args[i] != signature->arguments[i]) {
341             m_errorMessage = makeString("Expected argument type: ", toString(signature->arguments[i]), " does not match passed argument type: ", toString(args[i]));
342             return false;
343         }
344     }
345
346     result = signature->returnType;
347     return true;
348 }
349
350 bool Validate::unify(const ExpressionList& values, const ControlType& block)
351 {
352     ASSERT(values.size() <= 1);
353     if (block.signature() == Void)
354         return true;
355
356     if (!values.size()) {
357         m_errorMessage = makeString("Block has non-void signature but has no stack entries on exit");
358         return false;
359     }
360
361     if (values[0] == block.signature())
362         return true;
363
364     m_errorMessage = makeString("Expected control flow to return value with type: ", toString(block.signature()), " but got value with type: ", toString(values[0]));
365     return false;
366 }
367
368 void Validate::dump(const Vector<ControlEntry>&, const ExpressionList&)
369 {
370     // If you need this then you should fix the validator's error messages instead...
371     // Think of this as penance for the sin of bad error messages.
372 }
373
374 String validateFunction(const uint8_t* source, size_t length, const Signature* signature, const FunctionIndexSpace& functionIndexSpace, const MemoryInformation& memory)
375 {
376     Validate context(signature->returnType, memory);
377     FunctionParser<Validate> validator(context, source, length, signature, functionIndexSpace);
378     if (!validator.parse()) {
379         // FIXME: add better location information here. see: https://bugs.webkit.org/show_bug.cgi?id=164288
380         // FIXME: We should never not have an error message if we return false.
381         // see: https://bugs.webkit.org/show_bug.cgi?id=164354
382         if (context.errorMessage().isNull())
383             return "Unknown error";
384         return context.errorMessage();
385     }
386
387     return String();
388 }
389
390 } } // namespace JSC::Wasm
391
392 #include "WasmValidateInlines.h"
393
394 #endif // ENABLE(WEBASSEMBLY)