1 /*
2  * Copyright 2015 WebAssembly Community Group participants
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 //
18 // Parses WebAssembly code in S-Expression format, as in .wast files
19 // such as are in the spec test suite.
20 //
21 
22 #ifndef wasm_wasm_s_parser_h
23 #define wasm_wasm_s_parser_h
24 
25 #include "mixed_arena.h"
26 #include "parsing.h" // for UniqueNameMapper. TODO: move dependency to cpp file?
27 #include "wasm-builder.h"
28 #include "wasm.h"
29 
30 namespace wasm {
31 
32 class SourceLocation {
33 public:
34   cashew::IString filename;
35   uint32_t line;
36   uint32_t column;
37   SourceLocation(cashew::IString filename_,
38                  uint32_t line_,
39                  uint32_t column_ = 0)
filename(filename_)40     : filename(filename_), line(line_), column(column_) {}
41 };
42 
43 //
44 // An element in an S-Expression: a list or a string
45 //
46 class Element {
47   typedef ArenaVector<Element*> List;
48 
49   bool isList_ = true;
50   List list_;
51   cashew::IString str_;
52   bool dollared_;
53   bool quoted_;
54 
55 public:
Element(MixedArena & allocator)56   Element(MixedArena& allocator) : list_(allocator) {}
57 
isList()58   bool isList() const { return isList_; }
isStr()59   bool isStr() const { return !isList_; }
dollared()60   bool dollared() const { return isStr() && dollared_; }
quoted()61   bool quoted() const { return isStr() && quoted_; }
62 
63   size_t line = -1;
64   size_t col = -1;
65   // original locations at the start/end of the S-Expression list
66   SourceLocation* startLoc = nullptr;
67   SourceLocation* endLoc = nullptr;
68 
69   // list methods
70   List& list();
71   Element* operator[](unsigned i);
size()72   size_t size() { return list().size(); }
73 
74   // string methods
75   cashew::IString str() const;
76   const char* c_str() const;
77   Element* setString(cashew::IString str__, bool dollared__, bool quoted__);
78   Element* setMetadata(size_t line_, size_t col_, SourceLocation* startLoc_);
79 
80   // printing
81   friend std::ostream& operator<<(std::ostream& o, Element& e);
82   void dump();
83 };
84 
85 //
86 // Generic S-Expression parsing into lists
87 //
88 class SExpressionParser {
89   char* input;
90   size_t line;
91   char* lineStart;
92   SourceLocation* loc = nullptr;
93 
94   MixedArena allocator;
95 
96 public:
97   // Assumes control of and modifies the input.
98   SExpressionParser(char* input);
99   Element* root;
100 
101 private:
102   Element* parse();
103   void skipWhitespace();
104   void parseDebugLocation();
105   Element* parseString();
106 };
107 
108 //
109 // SExpressions => WebAssembly module
110 //
111 class SExpressionWasmBuilder {
112   Module& wasm;
113   MixedArena& allocator;
114   IRProfile profile;
115   std::vector<Signature> signatures;
116   std::unordered_map<std::string, size_t> signatureIndices;
117   std::vector<Name> functionNames;
118   std::vector<Name> globalNames;
119   std::vector<Name> eventNames;
120   int functionCounter = 0;
121   int globalCounter = 0;
122   int eventCounter = 0;
123   // we need to know function return types before we parse their contents
124   std::map<Name, Type> functionTypes;
125   std::unordered_map<cashew::IString, Index> debugInfoFileIndices;
126 
127 public:
128   // Assumes control of and modifies the input.
129   SExpressionWasmBuilder(Module& wasm, Element& module, IRProfile profile);
130 
131 private:
132   // pre-parse types and function definitions, so we know function return types
133   // before parsing their contents
134   void preParseFunctionType(Element& s);
135   bool isImport(Element& curr);
136   void preParseImports(Element& curr);
137   void parseModuleElement(Element& curr);
138 
139   // function parsing state
140   std::unique_ptr<Function> currFunction;
141   bool brokeToAutoBlock;
142 
143   UniqueNameMapper nameMapper;
144 
145   Signature getFunctionSignature(Element& s);
146   Name getFunctionName(Element& s);
147   Name getGlobalName(Element& s);
148   Name getEventName(Element& s);
parseStart(Element & s)149   void parseStart(Element& s) { wasm.addStart(getFunctionName(*s[1])); }
150 
151   // returns the next index in s
152   size_t parseFunctionNames(Element& s, Name& name, Name& exportName);
153   void parseFunction(Element& s, bool preParseImport = false);
154 
155   Type stringToType(cashew::IString str,
156                     bool allowError = false,
157                     bool prefix = false) {
158     return stringToType(str.str, allowError, prefix);
159   }
160   Type
161   stringToType(const char* str, bool allowError = false, bool prefix = false);
162   HeapType stringToHeapType(cashew::IString str, bool prefix = false) {
163     return stringToHeapType(str.str, prefix);
164   }
165   HeapType stringToHeapType(const char* str, bool prefix = false);
166   Type elementToType(Element& s);
167   Type stringToLaneType(const char* str);
isType(cashew::IString str)168   bool isType(cashew::IString str) {
169     return stringToType(str, true) != Type::none;
170   }
171 
172 public:
parseExpression(Element * s)173   Expression* parseExpression(Element* s) { return parseExpression(*s); }
174   Expression* parseExpression(Element& s);
175 
getModule()176   Module& getModule() { return wasm; }
177 
178 private:
179   Expression* makeExpression(Element& s);
180   Expression* makeUnreachable();
181   Expression* makeNop();
182   Expression* makeBinary(Element& s, BinaryOp op);
183   Expression* makeUnary(Element& s, UnaryOp op);
184   Expression* makeSelect(Element& s);
185   Expression* makeDrop(Element& s);
186   Expression* makeMemorySize(Element& s);
187   Expression* makeMemoryGrow(Element& s);
188   Index getLocalIndex(Element& s);
189   Expression* makeLocalGet(Element& s);
190   Expression* makeLocalTee(Element& s);
191   Expression* makeLocalSet(Element& s);
192   Expression* makeGlobalGet(Element& s);
193   Expression* makeGlobalSet(Element& s);
194   Expression* makeBlock(Element& s);
195   Expression* makeThenOrElse(Element& s);
196   Expression* makeConst(Element& s, Type type);
197   Expression* makeLoad(Element& s, Type type, bool isAtomic);
198   Expression* makeStore(Element& s, Type type, bool isAtomic);
199   Expression* makeAtomicRMWOrCmpxchg(Element& s, Type type);
200   Expression*
201   makeAtomicRMW(Element& s, Type type, uint8_t bytes, const char* extra);
202   Expression*
203   makeAtomicCmpxchg(Element& s, Type type, uint8_t bytes, const char* extra);
204   Expression* makeAtomicWait(Element& s, Type type);
205   Expression* makeAtomicNotify(Element& s);
206   Expression* makeAtomicFence(Element& s);
207   Expression* makeSIMDExtract(Element& s, SIMDExtractOp op, size_t lanes);
208   Expression* makeSIMDReplace(Element& s, SIMDReplaceOp op, size_t lanes);
209   Expression* makeSIMDShuffle(Element& s);
210   Expression* makeSIMDTernary(Element& s, SIMDTernaryOp op);
211   Expression* makeSIMDShift(Element& s, SIMDShiftOp op);
212   Expression* makeSIMDLoad(Element& s, SIMDLoadOp op);
213   Expression* makeMemoryInit(Element& s);
214   Expression* makeDataDrop(Element& s);
215   Expression* makeMemoryCopy(Element& s);
216   Expression* makeMemoryFill(Element& s);
217   Expression* makePush(Element& s);
218   Expression* makePop(Element& s);
219   Expression* makeIf(Element& s);
220   Expression* makeMaybeBlock(Element& s, size_t i, Type type);
221   Expression* makeLoop(Element& s);
222   Expression* makeCall(Element& s, bool isReturn);
223   Expression* makeCallIndirect(Element& s, bool isReturn);
224   template<class T>
parseCallOperands(Element & s,Index i,Index j,T * call)225   void parseCallOperands(Element& s, Index i, Index j, T* call) {
226     while (i < j) {
227       call->operands.push_back(parseExpression(s[i]));
228       i++;
229     }
230   }
231   Name getLabel(Element& s);
232   Expression* makeBreak(Element& s);
233   Expression* makeBreakTable(Element& s);
234   Expression* makeReturn(Element& s);
235   Expression* makeRefNull(Element& s);
236   Expression* makeRefIsNull(Element& s);
237   Expression* makeRefFunc(Element& s);
238   Expression* makeRefEq(Element& s);
239   Expression* makeTry(Element& s);
240   Expression* makeTryOrCatchBody(Element& s, Type type, bool isTry);
241   Expression* makeThrow(Element& s);
242   Expression* makeRethrow(Element& s);
243   Expression* makeBrOnExn(Element& s);
244   Expression* makeTupleMake(Element& s);
245   Expression* makeTupleExtract(Element& s);
246   Expression* makeI31New(Element& s);
247   Expression* makeI31Get(Element& s, bool signed_);
248   Expression* makeRefTest(Element& s);
249   Expression* makeRefCast(Element& s);
250   Expression* makeBrOnCast(Element& s);
251   Expression* makeRttCanon(Element& s);
252   Expression* makeRttSub(Element& s);
253   Expression* makeStructNew(Element& s, bool default_);
254   Expression* makeStructGet(Element& s);
255   Expression* makeStructGet(Element& s, bool signed_);
256   Expression* makeStructSet(Element& s);
257   Expression* makeArrayNew(Element& s, bool default_);
258   Expression* makeArrayGet(Element& s);
259   Expression* makeArrayGet(Element& s, bool signed_);
260   Expression* makeArraySet(Element& s);
261   Expression* makeArrayLen(Element& s);
262 
263   // Helper functions
264   Type parseOptionalResultType(Element& s, Index& i);
265   Index parseMemoryLimits(Element& s, Index i);
266   Index parseMemoryIndex(Element& s, Index i);
267   std::vector<Type> parseParamOrLocal(Element& s);
268   std::vector<NameType> parseParamOrLocal(Element& s, size_t& localIndex);
269   std::vector<Type> parseResults(Element& s);
270   Signature parseTypeRef(Element& s);
271   size_t parseTypeUse(Element& s,
272                       size_t startPos,
273                       Signature& functionSignature,
274                       std::vector<NameType>& namedParams);
275   size_t
276   parseTypeUse(Element& s, size_t startPos, Signature& functionSignature);
277 
278   void stringToBinary(const char* input, size_t size, std::vector<char>& data);
279   void parseMemory(Element& s, bool preParseImport = false);
280   void parseData(Element& s);
281   void parseInnerData(Element& s, Index i, Expression* offset, bool isPassive);
282   void parseExport(Element& s);
283   void parseImport(Element& s);
284   void parseGlobal(Element& s, bool preParseImport = false);
285   void parseTable(Element& s, bool preParseImport = false);
286   void parseElem(Element& s);
287   void parseInnerElem(Element& s, Index i = 1, Expression* offset = nullptr);
288   void parseType(Element& s);
289   void parseEvent(Element& s, bool preParseImport = false);
290 
291   Function::DebugLocation getDebugLocation(const SourceLocation& loc);
292 };
293 
294 } // namespace wasm
295 
296 #endif // wasm_wasm_s_parser_h
297