1//===- WasmObjectFile.cpp - Wasm object file implementation ---------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/ADT/ArrayRef.h"
10#include "llvm/ADT/DenseSet.h"
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/ADT/SmallSet.h"
13#include "llvm/ADT/StringRef.h"
14#include "llvm/ADT/StringSet.h"
15#include "llvm/ADT/Triple.h"
16#include "llvm/BinaryFormat/Wasm.h"
17#include "llvm/MC/SubtargetFeature.h"
18#include "llvm/Object/Binary.h"
19#include "llvm/Object/Error.h"
20#include "llvm/Object/ObjectFile.h"
21#include "llvm/Object/SymbolicFile.h"
22#include "llvm/Object/Wasm.h"
23#include "llvm/Support/Endian.h"
24#include "llvm/Support/Error.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/LEB128.h"
27#include "llvm/Support/ScopedPrinter.h"
28#include <algorithm>
29#include <cassert>
30#include <cstdint>
31#include <cstring>
32#include <system_error>
33
34#define DEBUG_TYPE "wasm-object"
35
36using namespace llvm;
37using namespace object;
38
39void WasmSymbol::print(raw_ostream &Out) const {
40  Out << "Name=" << Info.Name
41      << ", Kind=" << toString(wasm::WasmSymbolType(Info.Kind))
42      << ", Flags=" << Info.Flags;
43  if (!isTypeData()) {
44    Out << ", ElemIndex=" << Info.ElementIndex;
45  } else if (isDefined()) {
46    Out << ", Segment=" << Info.DataRef.Segment;
47    Out << ", Offset=" << Info.DataRef.Offset;
48    Out << ", Size=" << Info.DataRef.Size;
49  }
50}
51
52#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
53LLVM_DUMP_METHOD void WasmSymbol::dump() const { print(dbgs()); }
54#endif
55
56Expected<std::unique_ptr<WasmObjectFile>>
57ObjectFile::createWasmObjectFile(MemoryBufferRef Buffer) {
58  Error Err = Error::success();
59  auto ObjectFile = std::make_unique<WasmObjectFile>(Buffer, Err);
60  if (Err)
61    return std::move(Err);
62
63  return std::move(ObjectFile);
64}
65
66#define VARINT7_MAX ((1 << 7) - 1)
67#define VARINT7_MIN (-(1 << 7))
68#define VARUINT7_MAX (1 << 7)
69#define VARUINT1_MAX (1)
70
71static uint8_t readUint8(WasmObjectFile::ReadContext &Ctx) {
72  if (Ctx.Ptr == Ctx.End)
73    report_fatal_error("EOF while reading uint8");
74  return *Ctx.Ptr++;
75}
76
77static uint32_t readUint32(WasmObjectFile::ReadContext &Ctx) {
78  if (Ctx.Ptr + 4 > Ctx.End)
79    report_fatal_error("EOF while reading uint32");
80  uint32_t Result = support::endian::read32le(Ctx.Ptr);
81  Ctx.Ptr += 4;
82  return Result;
83}
84
85static int32_t readFloat32(WasmObjectFile::ReadContext &Ctx) {
86  if (Ctx.Ptr + 4 > Ctx.End)
87    report_fatal_error("EOF while reading float64");
88  int32_t Result = 0;
89  memcpy(&Result, Ctx.Ptr, sizeof(Result));
90  Ctx.Ptr += sizeof(Result);
91  return Result;
92}
93
94static int64_t readFloat64(WasmObjectFile::ReadContext &Ctx) {
95  if (Ctx.Ptr + 8 > Ctx.End)
96    report_fatal_error("EOF while reading float64");
97  int64_t Result = 0;
98  memcpy(&Result, Ctx.Ptr, sizeof(Result));
99  Ctx.Ptr += sizeof(Result);
100  return Result;
101}
102
103static uint64_t readULEB128(WasmObjectFile::ReadContext &Ctx) {
104  unsigned Count;
105  const char *Error = nullptr;
106  uint64_t Result = decodeULEB128(Ctx.Ptr, &Count, Ctx.End, &Error);
107  if (Error)
108    report_fatal_error(Error);
109  Ctx.Ptr += Count;
110  return Result;
111}
112
113static StringRef readString(WasmObjectFile::ReadContext &Ctx) {
114  uint32_t StringLen = readULEB128(Ctx);
115  if (Ctx.Ptr + StringLen > Ctx.End)
116    report_fatal_error("EOF while reading string");
117  StringRef Return =
118      StringRef(reinterpret_cast<const char *>(Ctx.Ptr), StringLen);
119  Ctx.Ptr += StringLen;
120  return Return;
121}
122
123static int64_t readLEB128(WasmObjectFile::ReadContext &Ctx) {
124  unsigned Count;
125  const char *Error = nullptr;
126  uint64_t Result = decodeSLEB128(Ctx.Ptr, &Count, Ctx.End, &Error);
127  if (Error)
128    report_fatal_error(Error);
129  Ctx.Ptr += Count;
130  return Result;
131}
132
133static uint8_t readVaruint1(WasmObjectFile::ReadContext &Ctx) {
134  int64_t Result = readLEB128(Ctx);
135  if (Result > VARUINT1_MAX || Result < 0)
136    report_fatal_error("LEB is outside Varuint1 range");
137  return Result;
138}
139
140static int32_t readVarint32(WasmObjectFile::ReadContext &Ctx) {
141  int64_t Result = readLEB128(Ctx);
142  if (Result > INT32_MAX || Result < INT32_MIN)
143    report_fatal_error("LEB is outside Varint32 range");
144  return Result;
145}
146
147static uint32_t readVaruint32(WasmObjectFile::ReadContext &Ctx) {
148  uint64_t Result = readULEB128(Ctx);
149  if (Result > UINT32_MAX)
150    report_fatal_error("LEB is outside Varuint32 range");
151  return Result;
152}
153
154static int64_t readVarint64(WasmObjectFile::ReadContext &Ctx) {
155  return readLEB128(Ctx);
156}
157
158static uint8_t readOpcode(WasmObjectFile::ReadContext &Ctx) {
159  return readUint8(Ctx);
160}
161
162static Error readInitExpr(wasm::WasmInitExpr &Expr,
163                          WasmObjectFile::ReadContext &Ctx) {
164  Expr.Opcode = readOpcode(Ctx);
165
166  switch (Expr.Opcode) {
167  case wasm::WASM_OPCODE_I32_CONST:
168    Expr.Value.Int32 = readVarint32(Ctx);
169    break;
170  case wasm::WASM_OPCODE_I64_CONST:
171    Expr.Value.Int64 = readVarint64(Ctx);
172    break;
173  case wasm::WASM_OPCODE_F32_CONST:
174    Expr.Value.Float32 = readFloat32(Ctx);
175    break;
176  case wasm::WASM_OPCODE_F64_CONST:
177    Expr.Value.Float64 = readFloat64(Ctx);
178    break;
179  case wasm::WASM_OPCODE_GLOBAL_GET:
180    Expr.Value.Global = readULEB128(Ctx);
181    break;
182  default:
183    return make_error<GenericBinaryError>("Invalid opcode in init_expr",
184                                          object_error::parse_failed);
185  }
186
187  uint8_t EndOpcode = readOpcode(Ctx);
188  if (EndOpcode != wasm::WASM_OPCODE_END) {
189    return make_error<GenericBinaryError>("Invalid init_expr",
190                                          object_error::parse_failed);
191  }
192  return Error::success();
193}
194
195static wasm::WasmLimits readLimits(WasmObjectFile::ReadContext &Ctx) {
196  wasm::WasmLimits Result;
197  Result.Flags = readVaruint32(Ctx);
198  Result.Initial = readVaruint32(Ctx);
199  if (Result.Flags & wasm::WASM_LIMITS_FLAG_HAS_MAX)
200    Result.Maximum = readVaruint32(Ctx);
201  return Result;
202}
203
204static wasm::WasmTable readTable(WasmObjectFile::ReadContext &Ctx) {
205  wasm::WasmTable Table;
206  Table.ElemType = readUint8(Ctx);
207  Table.Limits = readLimits(Ctx);
208  return Table;
209}
210
211static Error readSection(WasmSection &Section, WasmObjectFile::ReadContext &Ctx,
212                         WasmSectionOrderChecker &Checker) {
213  Section.Offset = Ctx.Ptr - Ctx.Start;
214  Section.Type = readUint8(Ctx);
215  LLVM_DEBUG(dbgs() << "readSection type=" << Section.Type << "\n");
216  uint32_t Size = readVaruint32(Ctx);
217  if (Size == 0)
218    return make_error<StringError>("Zero length section",
219                                   object_error::parse_failed);
220  if (Ctx.Ptr + Size > Ctx.End)
221    return make_error<StringError>("Section too large",
222                                   object_error::parse_failed);
223  if (Section.Type == wasm::WASM_SEC_CUSTOM) {
224    WasmObjectFile::ReadContext SectionCtx;
225    SectionCtx.Start = Ctx.Ptr;
226    SectionCtx.Ptr = Ctx.Ptr;
227    SectionCtx.End = Ctx.Ptr + Size;
228
229    Section.Name = readString(SectionCtx);
230
231    uint32_t SectionNameSize = SectionCtx.Ptr - SectionCtx.Start;
232    Ctx.Ptr += SectionNameSize;
233    Size -= SectionNameSize;
234  }
235
236  if (!Checker.isValidSectionOrder(Section.Type, Section.Name)) {
237    return make_error<StringError>("Out of order section type: " +
238                                       llvm::to_string(Section.Type),
239                                   object_error::parse_failed);
240  }
241
242  Section.Content = ArrayRef<uint8_t>(Ctx.Ptr, Size);
243  Ctx.Ptr += Size;
244  return Error::success();
245}
246
247WasmObjectFile::WasmObjectFile(MemoryBufferRef Buffer, Error &Err)
248    : ObjectFile(Binary::ID_Wasm, Buffer) {
249  ErrorAsOutParameter ErrAsOutParam(&Err);
250  Header.Magic = getData().substr(0, 4);
251  if (Header.Magic != StringRef("\0asm", 4)) {
252    Err =
253        make_error<StringError>("Bad magic number", object_error::parse_failed);
254    return;
255  }
256
257  ReadContext Ctx;
258  Ctx.Start = getData().bytes_begin();
259  Ctx.Ptr = Ctx.Start + 4;
260  Ctx.End = Ctx.Start + getData().size();
261
262  if (Ctx.Ptr + 4 > Ctx.End) {
263    Err = make_error<StringError>("Missing version number",
264                                  object_error::parse_failed);
265    return;
266  }
267
268  Header.Version = readUint32(Ctx);
269  if (Header.Version != wasm::WasmVersion) {
270    Err = make_error<StringError>("Bad version number",
271                                  object_error::parse_failed);
272    return;
273  }
274
275  WasmSection Sec;
276  WasmSectionOrderChecker Checker;
277  while (Ctx.Ptr < Ctx.End) {
278    if ((Err = readSection(Sec, Ctx, Checker)))
279      return;
280    if ((Err = parseSection(Sec)))
281      return;
282
283    Sections.push_back(Sec);
284  }
285}
286
287Error WasmObjectFile::parseSection(WasmSection &Sec) {
288  ReadContext Ctx;
289  Ctx.Start = Sec.Content.data();
290  Ctx.End = Ctx.Start + Sec.Content.size();
291  Ctx.Ptr = Ctx.Start;
292  switch (Sec.Type) {
293  case wasm::WASM_SEC_CUSTOM:
294    return parseCustomSection(Sec, Ctx);
295  case wasm::WASM_SEC_TYPE:
296    return parseTypeSection(Ctx);
297  case wasm::WASM_SEC_IMPORT:
298    return parseImportSection(Ctx);
299  case wasm::WASM_SEC_FUNCTION:
300    return parseFunctionSection(Ctx);
301  case wasm::WASM_SEC_TABLE:
302    return parseTableSection(Ctx);
303  case wasm::WASM_SEC_MEMORY:
304    return parseMemorySection(Ctx);
305  case wasm::WASM_SEC_GLOBAL:
306    return parseGlobalSection(Ctx);
307  case wasm::WASM_SEC_EVENT:
308    return parseEventSection(Ctx);
309  case wasm::WASM_SEC_EXPORT:
310    return parseExportSection(Ctx);
311  case wasm::WASM_SEC_START:
312    return parseStartSection(Ctx);
313  case wasm::WASM_SEC_ELEM:
314    return parseElemSection(Ctx);
315  case wasm::WASM_SEC_CODE:
316    return parseCodeSection(Ctx);
317  case wasm::WASM_SEC_DATA:
318    return parseDataSection(Ctx);
319  case wasm::WASM_SEC_DATACOUNT:
320    return parseDataCountSection(Ctx);
321  default:
322    return make_error<GenericBinaryError>(
323        "Invalid section type: " + Twine(Sec.Type), object_error::parse_failed);
324  }
325}
326
327Error WasmObjectFile::parseDylinkSection(ReadContext &Ctx) {
328  // See https://github.com/WebAssembly/tool-conventions/blob/master/DynamicLinking.md
329  HasDylinkSection = true;
330  DylinkInfo.MemorySize = readVaruint32(Ctx);
331  DylinkInfo.MemoryAlignment = readVaruint32(Ctx);
332  DylinkInfo.TableSize = readVaruint32(Ctx);
333  DylinkInfo.TableAlignment = readVaruint32(Ctx);
334  uint32_t Count = readVaruint32(Ctx);
335  while (Count--) {
336    DylinkInfo.Needed.push_back(readString(Ctx));
337  }
338  if (Ctx.Ptr != Ctx.End)
339    return make_error<GenericBinaryError>("dylink section ended prematurely",
340                                          object_error::parse_failed);
341  return Error::success();
342}
343
344Error WasmObjectFile::parseNameSection(ReadContext &Ctx) {
345  llvm::DenseSet<uint64_t> Seen;
346  if (FunctionTypes.size() && !SeenCodeSection) {
347    return make_error<GenericBinaryError>("Names must come after code section",
348                                          object_error::parse_failed);
349  }
350
351  while (Ctx.Ptr < Ctx.End) {
352    uint8_t Type = readUint8(Ctx);
353    uint32_t Size = readVaruint32(Ctx);
354    const uint8_t *SubSectionEnd = Ctx.Ptr + Size;
355    switch (Type) {
356    case wasm::WASM_NAMES_FUNCTION: {
357      uint32_t Count = readVaruint32(Ctx);
358      while (Count--) {
359        uint32_t Index = readVaruint32(Ctx);
360        if (!Seen.insert(Index).second)
361          return make_error<GenericBinaryError>("Function named more than once",
362                                                object_error::parse_failed);
363        StringRef Name = readString(Ctx);
364        if (!isValidFunctionIndex(Index) || Name.empty())
365          return make_error<GenericBinaryError>("Invalid name entry",
366                                                object_error::parse_failed);
367        DebugNames.push_back(wasm::WasmFunctionName{Index, Name});
368        if (isDefinedFunctionIndex(Index))
369          getDefinedFunction(Index).DebugName = Name;
370      }
371      break;
372    }
373    // Ignore local names for now
374    case wasm::WASM_NAMES_LOCAL:
375    default:
376      Ctx.Ptr += Size;
377      break;
378    }
379    if (Ctx.Ptr != SubSectionEnd)
380      return make_error<GenericBinaryError>(
381          "Name sub-section ended prematurely", object_error::parse_failed);
382  }
383
384  if (Ctx.Ptr != Ctx.End)
385    return make_error<GenericBinaryError>("Name section ended prematurely",
386                                          object_error::parse_failed);
387  return Error::success();
388}
389
390Error WasmObjectFile::parseLinkingSection(ReadContext &Ctx) {
391  HasLinkingSection = true;
392  if (FunctionTypes.size() && !SeenCodeSection) {
393    return make_error<GenericBinaryError>(
394        "Linking data must come after code section",
395        object_error::parse_failed);
396  }
397
398  LinkingData.Version = readVaruint32(Ctx);
399  if (LinkingData.Version != wasm::WasmMetadataVersion) {
400    return make_error<GenericBinaryError>(
401        "Unexpected metadata version: " + Twine(LinkingData.Version) +
402            " (Expected: " + Twine(wasm::WasmMetadataVersion) + ")",
403        object_error::parse_failed);
404  }
405
406  const uint8_t *OrigEnd = Ctx.End;
407  while (Ctx.Ptr < OrigEnd) {
408    Ctx.End = OrigEnd;
409    uint8_t Type = readUint8(Ctx);
410    uint32_t Size = readVaruint32(Ctx);
411    LLVM_DEBUG(dbgs() << "readSubsection type=" << int(Type) << " size=" << Size
412                      << "\n");
413    Ctx.End = Ctx.Ptr + Size;
414    switch (Type) {
415    case wasm::WASM_SYMBOL_TABLE:
416      if (Error Err = parseLinkingSectionSymtab(Ctx))
417        return Err;
418      break;
419    case wasm::WASM_SEGMENT_INFO: {
420      uint32_t Count = readVaruint32(Ctx);
421      if (Count > DataSegments.size())
422        return make_error<GenericBinaryError>("Too many segment names",
423                                              object_error::parse_failed);
424      for (uint32_t I = 0; I < Count; I++) {
425        DataSegments[I].Data.Name = readString(Ctx);
426        DataSegments[I].Data.Alignment = readVaruint32(Ctx);
427        DataSegments[I].Data.LinkerFlags = readVaruint32(Ctx);
428      }
429      break;
430    }
431    case wasm::WASM_INIT_FUNCS: {
432      uint32_t Count = readVaruint32(Ctx);
433      LinkingData.InitFunctions.reserve(Count);
434      for (uint32_t I = 0; I < Count; I++) {
435        wasm::WasmInitFunc Init;
436        Init.Priority = readVaruint32(Ctx);
437        Init.Symbol = readVaruint32(Ctx);
438        if (!isValidFunctionSymbol(Init.Symbol))
439          return make_error<GenericBinaryError>("Invalid function symbol: " +
440                                                    Twine(Init.Symbol),
441                                                object_error::parse_failed);
442        LinkingData.InitFunctions.emplace_back(Init);
443      }
444      break;
445    }
446    case wasm::WASM_COMDAT_INFO:
447      if (Error Err = parseLinkingSectionComdat(Ctx))
448        return Err;
449      break;
450    default:
451      Ctx.Ptr += Size;
452      break;
453    }
454    if (Ctx.Ptr != Ctx.End)
455      return make_error<GenericBinaryError>(
456          "Linking sub-section ended prematurely", object_error::parse_failed);
457  }
458  if (Ctx.Ptr != OrigEnd)
459    return make_error<GenericBinaryError>("Linking section ended prematurely",
460                                          object_error::parse_failed);
461  return Error::success();
462}
463
464Error WasmObjectFile::parseLinkingSectionSymtab(ReadContext &Ctx) {
465  uint32_t Count = readVaruint32(Ctx);
466  LinkingData.SymbolTable.reserve(Count);
467  Symbols.reserve(Count);
468  StringSet<> SymbolNames;
469
470  std::vector<wasm::WasmImport *> ImportedGlobals;
471  std::vector<wasm::WasmImport *> ImportedFunctions;
472  std::vector<wasm::WasmImport *> ImportedEvents;
473  ImportedGlobals.reserve(Imports.size());
474  ImportedFunctions.reserve(Imports.size());
475  ImportedEvents.reserve(Imports.size());
476  for (auto &I : Imports) {
477    if (I.Kind == wasm::WASM_EXTERNAL_FUNCTION)
478      ImportedFunctions.emplace_back(&I);
479    else if (I.Kind == wasm::WASM_EXTERNAL_GLOBAL)
480      ImportedGlobals.emplace_back(&I);
481    else if (I.Kind == wasm::WASM_EXTERNAL_EVENT)
482      ImportedEvents.emplace_back(&I);
483  }
484
485  while (Count--) {
486    wasm::WasmSymbolInfo Info;
487    const wasm::WasmSignature *Signature = nullptr;
488    const wasm::WasmGlobalType *GlobalType = nullptr;
489    const wasm::WasmEventType *EventType = nullptr;
490
491    Info.Kind = readUint8(Ctx);
492    Info.Flags = readVaruint32(Ctx);
493    bool IsDefined = (Info.Flags & wasm::WASM_SYMBOL_UNDEFINED) == 0;
494
495    switch (Info.Kind) {
496    case wasm::WASM_SYMBOL_TYPE_FUNCTION:
497      Info.ElementIndex = readVaruint32(Ctx);
498      if (!isValidFunctionIndex(Info.ElementIndex) ||
499          IsDefined != isDefinedFunctionIndex(Info.ElementIndex))
500        return make_error<GenericBinaryError>("invalid function symbol index",
501                                              object_error::parse_failed);
502      if (IsDefined) {
503        Info.Name = readString(Ctx);
504        unsigned FuncIndex = Info.ElementIndex - NumImportedFunctions;
505        Signature = &Signatures[FunctionTypes[FuncIndex]];
506        wasm::WasmFunction &Function = Functions[FuncIndex];
507        if (Function.SymbolName.empty())
508          Function.SymbolName = Info.Name;
509      } else {
510        wasm::WasmImport &Import = *ImportedFunctions[Info.ElementIndex];
511        if ((Info.Flags & wasm::WASM_SYMBOL_EXPLICIT_NAME) != 0)
512          Info.Name = readString(Ctx);
513        else
514          Info.Name = Import.Field;
515        Signature = &Signatures[Import.SigIndex];
516        Info.ImportName = Import.Field;
517        Info.ImportModule = Import.Module;
518      }
519      break;
520
521    case wasm::WASM_SYMBOL_TYPE_GLOBAL:
522      Info.ElementIndex = readVaruint32(Ctx);
523      if (!isValidGlobalIndex(Info.ElementIndex) ||
524          IsDefined != isDefinedGlobalIndex(Info.ElementIndex))
525        return make_error<GenericBinaryError>("invalid global symbol index",
526                                              object_error::parse_failed);
527      if (!IsDefined && (Info.Flags & wasm::WASM_SYMBOL_BINDING_MASK) ==
528                            wasm::WASM_SYMBOL_BINDING_WEAK)
529        return make_error<GenericBinaryError>("undefined weak global symbol",
530                                              object_error::parse_failed);
531      if (IsDefined) {
532        Info.Name = readString(Ctx);
533        unsigned GlobalIndex = Info.ElementIndex - NumImportedGlobals;
534        wasm::WasmGlobal &Global = Globals[GlobalIndex];
535        GlobalType = &Global.Type;
536        if (Global.SymbolName.empty())
537          Global.SymbolName = Info.Name;
538      } else {
539        wasm::WasmImport &Import = *ImportedGlobals[Info.ElementIndex];
540        if ((Info.Flags & wasm::WASM_SYMBOL_EXPLICIT_NAME) != 0)
541          Info.Name = readString(Ctx);
542        else
543          Info.Name = Import.Field;
544        GlobalType = &Import.Global;
545        Info.ImportName = Import.Field;
546        Info.ImportModule = Import.Module;
547      }
548      break;
549
550    case wasm::WASM_SYMBOL_TYPE_DATA:
551      Info.Name = readString(Ctx);
552      if (IsDefined) {
553        uint32_t Index = readVaruint32(Ctx);
554        if (Index >= DataSegments.size())
555          return make_error<GenericBinaryError>("invalid data symbol index",
556                                                object_error::parse_failed);
557        uint32_t Offset = readVaruint32(Ctx);
558        uint32_t Size = readVaruint32(Ctx);
559        if (Offset + Size > DataSegments[Index].Data.Content.size())
560          return make_error<GenericBinaryError>("invalid data symbol offset",
561                                                object_error::parse_failed);
562        Info.DataRef = wasm::WasmDataReference{Index, Offset, Size};
563      }
564      break;
565
566    case wasm::WASM_SYMBOL_TYPE_SECTION: {
567      if ((Info.Flags & wasm::WASM_SYMBOL_BINDING_MASK) !=
568          wasm::WASM_SYMBOL_BINDING_LOCAL)
569        return make_error<GenericBinaryError>(
570            "Section symbols must have local binding",
571            object_error::parse_failed);
572      Info.ElementIndex = readVaruint32(Ctx);
573      // Use somewhat unique section name as symbol name.
574      StringRef SectionName = Sections[Info.ElementIndex].Name;
575      Info.Name = SectionName;
576      break;
577    }
578
579    case wasm::WASM_SYMBOL_TYPE_EVENT: {
580      Info.ElementIndex = readVaruint32(Ctx);
581      if (!isValidEventIndex(Info.ElementIndex) ||
582          IsDefined != isDefinedEventIndex(Info.ElementIndex))
583        return make_error<GenericBinaryError>("invalid event symbol index",
584                                              object_error::parse_failed);
585      if (!IsDefined && (Info.Flags & wasm::WASM_SYMBOL_BINDING_MASK) ==
586                            wasm::WASM_SYMBOL_BINDING_WEAK)
587        return make_error<GenericBinaryError>("undefined weak global symbol",
588                                              object_error::parse_failed);
589      if (IsDefined) {
590        Info.Name = readString(Ctx);
591        unsigned EventIndex = Info.ElementIndex - NumImportedEvents;
592        wasm::WasmEvent &Event = Events[EventIndex];
593        Signature = &Signatures[Event.Type.SigIndex];
594        EventType = &Event.Type;
595        if (Event.SymbolName.empty())
596          Event.SymbolName = Info.Name;
597
598      } else {
599        wasm::WasmImport &Import = *ImportedEvents[Info.ElementIndex];
600        if ((Info.Flags & wasm::WASM_SYMBOL_EXPLICIT_NAME) != 0)
601          Info.Name = readString(Ctx);
602        else
603          Info.Name = Import.Field;
604        EventType = &Import.Event;
605        Signature = &Signatures[EventType->SigIndex];
606        Info.ImportName = Import.Field;
607        Info.ImportModule = Import.Module;
608      }
609      break;
610    }
611
612    default:
613      return make_error<GenericBinaryError>("Invalid symbol type",
614                                            object_error::parse_failed);
615    }
616
617    if ((Info.Flags & wasm::WASM_SYMBOL_BINDING_MASK) !=
618            wasm::WASM_SYMBOL_BINDING_LOCAL &&
619        !SymbolNames.insert(Info.Name).second)
620      return make_error<GenericBinaryError>("Duplicate symbol name " +
621                                                Twine(Info.Name),
622                                            object_error::parse_failed);
623    LinkingData.SymbolTable.emplace_back(Info);
624    Symbols.emplace_back(LinkingData.SymbolTable.back(), GlobalType, EventType,
625                         Signature);
626    LLVM_DEBUG(dbgs() << "Adding symbol: " << Symbols.back() << "\n");
627  }
628
629  return Error::success();
630}
631
632Error WasmObjectFile::parseLinkingSectionComdat(ReadContext &Ctx) {
633  uint32_t ComdatCount = readVaruint32(Ctx);
634  StringSet<> ComdatSet;
635  for (unsigned ComdatIndex = 0; ComdatIndex < ComdatCount; ++ComdatIndex) {
636    StringRef Name = readString(Ctx);
637    if (Name.empty() || !ComdatSet.insert(Name).second)
638      return make_error<GenericBinaryError>("Bad/duplicate COMDAT name " +
639                                                Twine(Name),
640                                            object_error::parse_failed);
641    LinkingData.Comdats.emplace_back(Name);
642    uint32_t Flags = readVaruint32(Ctx);
643    if (Flags != 0)
644      return make_error<GenericBinaryError>("Unsupported COMDAT flags",
645                                            object_error::parse_failed);
646
647    uint32_t EntryCount = readVaruint32(Ctx);
648    while (EntryCount--) {
649      unsigned Kind = readVaruint32(Ctx);
650      unsigned Index = readVaruint32(Ctx);
651      switch (Kind) {
652      default:
653        return make_error<GenericBinaryError>("Invalid COMDAT entry type",
654                                              object_error::parse_failed);
655      case wasm::WASM_COMDAT_DATA:
656        if (Index >= DataSegments.size())
657          return make_error<GenericBinaryError>(
658              "COMDAT data index out of range", object_error::parse_failed);
659        if (DataSegments[Index].Data.Comdat != UINT32_MAX)
660          return make_error<GenericBinaryError>("Data segment in two COMDATs",
661                                                object_error::parse_failed);
662        DataSegments[Index].Data.Comdat = ComdatIndex;
663        break;
664      case wasm::WASM_COMDAT_FUNCTION:
665        if (!isDefinedFunctionIndex(Index))
666          return make_error<GenericBinaryError>(
667              "COMDAT function index out of range", object_error::parse_failed);
668        if (getDefinedFunction(Index).Comdat != UINT32_MAX)
669          return make_error<GenericBinaryError>("Function in two COMDATs",
670                                                object_error::parse_failed);
671        getDefinedFunction(Index).Comdat = ComdatIndex;
672        break;
673      }
674    }
675  }
676  return Error::success();
677}
678
679Error WasmObjectFile::parseProducersSection(ReadContext &Ctx) {
680  llvm::SmallSet<StringRef, 3> FieldsSeen;
681  uint32_t Fields = readVaruint32(Ctx);
682  for (size_t I = 0; I < Fields; ++I) {
683    StringRef FieldName = readString(Ctx);
684    if (!FieldsSeen.insert(FieldName).second)
685      return make_error<GenericBinaryError>(
686          "Producers section does not have unique fields",
687          object_error::parse_failed);
688    std::vector<std::pair<std::string, std::string>> *ProducerVec = nullptr;
689    if (FieldName == "language") {
690      ProducerVec = &ProducerInfo.Languages;
691    } else if (FieldName == "processed-by") {
692      ProducerVec = &ProducerInfo.Tools;
693    } else if (FieldName == "sdk") {
694      ProducerVec = &ProducerInfo.SDKs;
695    } else {
696      return make_error<GenericBinaryError>(
697          "Producers section field is not named one of language, processed-by, "
698          "or sdk",
699          object_error::parse_failed);
700    }
701    uint32_t ValueCount = readVaruint32(Ctx);
702    llvm::SmallSet<StringRef, 8> ProducersSeen;
703    for (size_t J = 0; J < ValueCount; ++J) {
704      StringRef Name = readString(Ctx);
705      StringRef Version = readString(Ctx);
706      if (!ProducersSeen.insert(Name).second) {
707        return make_error<GenericBinaryError>(
708            "Producers section contains repeated producer",
709            object_error::parse_failed);
710      }
711      ProducerVec->emplace_back(Name, Version);
712    }
713  }
714  if (Ctx.Ptr != Ctx.End)
715    return make_error<GenericBinaryError>("Producers section ended prematurely",
716                                          object_error::parse_failed);
717  return Error::success();
718}
719
720Error WasmObjectFile::parseTargetFeaturesSection(ReadContext &Ctx) {
721  llvm::SmallSet<std::string, 8> FeaturesSeen;
722  uint32_t FeatureCount = readVaruint32(Ctx);
723  for (size_t I = 0; I < FeatureCount; ++I) {
724    wasm::WasmFeatureEntry Feature;
725    Feature.Prefix = readUint8(Ctx);
726    switch (Feature.Prefix) {
727    case wasm::WASM_FEATURE_PREFIX_USED:
728    case wasm::WASM_FEATURE_PREFIX_REQUIRED:
729    case wasm::WASM_FEATURE_PREFIX_DISALLOWED:
730      break;
731    default:
732      return make_error<GenericBinaryError>("Unknown feature policy prefix",
733                                            object_error::parse_failed);
734    }
735    Feature.Name = readString(Ctx);
736    if (!FeaturesSeen.insert(Feature.Name).second)
737      return make_error<GenericBinaryError>(
738          "Target features section contains repeated feature \"" +
739              Feature.Name + "\"",
740          object_error::parse_failed);
741    TargetFeatures.push_back(Feature);
742  }
743  if (Ctx.Ptr != Ctx.End)
744    return make_error<GenericBinaryError>(
745        "Target features section ended prematurely",
746        object_error::parse_failed);
747  return Error::success();
748}
749
750Error WasmObjectFile::parseRelocSection(StringRef Name, ReadContext &Ctx) {
751  uint32_t SectionIndex = readVaruint32(Ctx);
752  if (SectionIndex >= Sections.size())
753    return make_error<GenericBinaryError>("Invalid section index",
754                                          object_error::parse_failed);
755  WasmSection &Section = Sections[SectionIndex];
756  uint32_t RelocCount = readVaruint32(Ctx);
757  uint32_t EndOffset = Section.Content.size();
758  uint32_t PreviousOffset = 0;
759  while (RelocCount--) {
760    wasm::WasmRelocation Reloc = {};
761    Reloc.Type = readVaruint32(Ctx);
762    Reloc.Offset = readVaruint32(Ctx);
763    if (Reloc.Offset < PreviousOffset)
764      return make_error<GenericBinaryError>("Relocations not in offset order",
765                                            object_error::parse_failed);
766    PreviousOffset = Reloc.Offset;
767    Reloc.Index = readVaruint32(Ctx);
768    switch (Reloc.Type) {
769    case wasm::R_WASM_FUNCTION_INDEX_LEB:
770    case wasm::R_WASM_TABLE_INDEX_SLEB:
771    case wasm::R_WASM_TABLE_INDEX_I32:
772    case wasm::R_WASM_TABLE_INDEX_REL_SLEB:
773      if (!isValidFunctionSymbol(Reloc.Index))
774        return make_error<GenericBinaryError>("Bad relocation function index",
775                                              object_error::parse_failed);
776      break;
777    case wasm::R_WASM_TYPE_INDEX_LEB:
778      if (Reloc.Index >= Signatures.size())
779        return make_error<GenericBinaryError>("Bad relocation type index",
780                                              object_error::parse_failed);
781      break;
782    case wasm::R_WASM_GLOBAL_INDEX_LEB:
783      // R_WASM_GLOBAL_INDEX_LEB are can be used against function and data
784      // symbols to refer to their GOT entries.
785      if (!isValidGlobalSymbol(Reloc.Index) &&
786          !isValidDataSymbol(Reloc.Index) &&
787          !isValidFunctionSymbol(Reloc.Index))
788        return make_error<GenericBinaryError>("Bad relocation global index",
789                                              object_error::parse_failed);
790      break;
791    case wasm::R_WASM_EVENT_INDEX_LEB:
792      if (!isValidEventSymbol(Reloc.Index))
793        return make_error<GenericBinaryError>("Bad relocation event index",
794                                              object_error::parse_failed);
795      break;
796    case wasm::R_WASM_MEMORY_ADDR_LEB:
797    case wasm::R_WASM_MEMORY_ADDR_SLEB:
798    case wasm::R_WASM_MEMORY_ADDR_I32:
799    case wasm::R_WASM_MEMORY_ADDR_REL_SLEB:
800      if (!isValidDataSymbol(Reloc.Index))
801        return make_error<GenericBinaryError>("Bad relocation data index",
802                                              object_error::parse_failed);
803      Reloc.Addend = readVarint32(Ctx);
804      break;
805    case wasm::R_WASM_FUNCTION_OFFSET_I32:
806      if (!isValidFunctionSymbol(Reloc.Index))
807        return make_error<GenericBinaryError>("Bad relocation function index",
808                                              object_error::parse_failed);
809      Reloc.Addend = readVarint32(Ctx);
810      break;
811    case wasm::R_WASM_SECTION_OFFSET_I32:
812      if (!isValidSectionSymbol(Reloc.Index))
813        return make_error<GenericBinaryError>("Bad relocation section index",
814                                              object_error::parse_failed);
815      Reloc.Addend = readVarint32(Ctx);
816      break;
817    default:
818      return make_error<GenericBinaryError>("Bad relocation type: " +
819                                                Twine(Reloc.Type),
820                                            object_error::parse_failed);
821    }
822
823    // Relocations must fit inside the section, and must appear in order.  They
824    // also shouldn't overlap a function/element boundary, but we don't bother
825    // to check that.
826    uint64_t Size = 5;
827    if (Reloc.Type == wasm::R_WASM_TABLE_INDEX_I32 ||
828        Reloc.Type == wasm::R_WASM_MEMORY_ADDR_I32 ||
829        Reloc.Type == wasm::R_WASM_SECTION_OFFSET_I32 ||
830        Reloc.Type == wasm::R_WASM_FUNCTION_OFFSET_I32)
831      Size = 4;
832    if (Reloc.Offset + Size > EndOffset)
833      return make_error<GenericBinaryError>("Bad relocation offset",
834                                            object_error::parse_failed);
835
836    Section.Relocations.push_back(Reloc);
837  }
838  if (Ctx.Ptr != Ctx.End)
839    return make_error<GenericBinaryError>("Reloc section ended prematurely",
840                                          object_error::parse_failed);
841  return Error::success();
842}
843
844Error WasmObjectFile::parseCustomSection(WasmSection &Sec, ReadContext &Ctx) {
845  if (Sec.Name == "dylink") {
846    if (Error Err = parseDylinkSection(Ctx))
847      return Err;
848  } else if (Sec.Name == "name") {
849    if (Error Err = parseNameSection(Ctx))
850      return Err;
851  } else if (Sec.Name == "linking") {
852    if (Error Err = parseLinkingSection(Ctx))
853      return Err;
854  } else if (Sec.Name == "producers") {
855    if (Error Err = parseProducersSection(Ctx))
856      return Err;
857  } else if (Sec.Name == "target_features") {
858    if (Error Err = parseTargetFeaturesSection(Ctx))
859      return Err;
860  } else if (Sec.Name.startswith("reloc.")) {
861    if (Error Err = parseRelocSection(Sec.Name, Ctx))
862      return Err;
863  }
864  return Error::success();
865}
866
867Error WasmObjectFile::parseTypeSection(ReadContext &Ctx) {
868  uint32_t Count = readVaruint32(Ctx);
869  Signatures.reserve(Count);
870  while (Count--) {
871    wasm::WasmSignature Sig;
872    uint8_t Form = readUint8(Ctx);
873    if (Form != wasm::WASM_TYPE_FUNC) {
874      return make_error<GenericBinaryError>("Invalid signature type",
875                                            object_error::parse_failed);
876    }
877    uint32_t ParamCount = readVaruint32(Ctx);
878    Sig.Params.reserve(ParamCount);
879    while (ParamCount--) {
880      uint32_t ParamType = readUint8(Ctx);
881      Sig.Params.push_back(wasm::ValType(ParamType));
882    }
883    uint32_t ReturnCount = readVaruint32(Ctx);
884    while (ReturnCount--) {
885      uint32_t ReturnType = readUint8(Ctx);
886      Sig.Returns.push_back(wasm::ValType(ReturnType));
887    }
888    Signatures.push_back(std::move(Sig));
889  }
890  if (Ctx.Ptr != Ctx.End)
891    return make_error<GenericBinaryError>("Type section ended prematurely",
892                                          object_error::parse_failed);
893  return Error::success();
894}
895
896Error WasmObjectFile::parseImportSection(ReadContext &Ctx) {
897  uint32_t Count = readVaruint32(Ctx);
898  Imports.reserve(Count);
899  for (uint32_t I = 0; I < Count; I++) {
900    wasm::WasmImport Im;
901    Im.Module = readString(Ctx);
902    Im.Field = readString(Ctx);
903    Im.Kind = readUint8(Ctx);
904    switch (Im.Kind) {
905    case wasm::WASM_EXTERNAL_FUNCTION:
906      NumImportedFunctions++;
907      Im.SigIndex = readVaruint32(Ctx);
908      break;
909    case wasm::WASM_EXTERNAL_GLOBAL:
910      NumImportedGlobals++;
911      Im.Global.Type = readUint8(Ctx);
912      Im.Global.Mutable = readVaruint1(Ctx);
913      break;
914    case wasm::WASM_EXTERNAL_MEMORY:
915      Im.Memory = readLimits(Ctx);
916      break;
917    case wasm::WASM_EXTERNAL_TABLE:
918      Im.Table = readTable(Ctx);
919      if (Im.Table.ElemType != wasm::WASM_TYPE_FUNCREF)
920        return make_error<GenericBinaryError>("Invalid table element type",
921                                              object_error::parse_failed);
922      break;
923    case wasm::WASM_EXTERNAL_EVENT:
924      NumImportedEvents++;
925      Im.Event.Attribute = readVarint32(Ctx);
926      Im.Event.SigIndex = readVarint32(Ctx);
927      break;
928    default:
929      return make_error<GenericBinaryError>("Unexpected import kind",
930                                            object_error::parse_failed);
931    }
932    Imports.push_back(Im);
933  }
934  if (Ctx.Ptr != Ctx.End)
935    return make_error<GenericBinaryError>("Import section ended prematurely",
936                                          object_error::parse_failed);
937  return Error::success();
938}
939
940Error WasmObjectFile::parseFunctionSection(ReadContext &Ctx) {
941  uint32_t Count = readVaruint32(Ctx);
942  FunctionTypes.reserve(Count);
943  Functions.resize(Count);
944  uint32_t NumTypes = Signatures.size();
945  while (Count--) {
946    uint32_t Type = readVaruint32(Ctx);
947    if (Type >= NumTypes)
948      return make_error<GenericBinaryError>("Invalid function type",
949                                            object_error::parse_failed);
950    FunctionTypes.push_back(Type);
951  }
952  if (Ctx.Ptr != Ctx.End)
953    return make_error<GenericBinaryError>("Function section ended prematurely",
954                                          object_error::parse_failed);
955  return Error::success();
956}
957
958Error WasmObjectFile::parseTableSection(ReadContext &Ctx) {
959  uint32_t Count = readVaruint32(Ctx);
960  Tables.reserve(Count);
961  while (Count--) {
962    Tables.push_back(readTable(Ctx));
963    if (Tables.back().ElemType != wasm::WASM_TYPE_FUNCREF) {
964      return make_error<GenericBinaryError>("Invalid table element type",
965                                            object_error::parse_failed);
966    }
967  }
968  if (Ctx.Ptr != Ctx.End)
969    return make_error<GenericBinaryError>("Table section ended prematurely",
970                                          object_error::parse_failed);
971  return Error::success();
972}
973
974Error WasmObjectFile::parseMemorySection(ReadContext &Ctx) {
975  uint32_t Count = readVaruint32(Ctx);
976  Memories.reserve(Count);
977  while (Count--) {
978    Memories.push_back(readLimits(Ctx));
979  }
980  if (Ctx.Ptr != Ctx.End)
981    return make_error<GenericBinaryError>("Memory section ended prematurely",
982                                          object_error::parse_failed);
983  return Error::success();
984}
985
986Error WasmObjectFile::parseGlobalSection(ReadContext &Ctx) {
987  GlobalSection = Sections.size();
988  uint32_t Count = readVaruint32(Ctx);
989  Globals.reserve(Count);
990  while (Count--) {
991    wasm::WasmGlobal Global;
992    Global.Index = NumImportedGlobals + Globals.size();
993    Global.Type.Type = readUint8(Ctx);
994    Global.Type.Mutable = readVaruint1(Ctx);
995    if (Error Err = readInitExpr(Global.InitExpr, Ctx))
996      return Err;
997    Globals.push_back(Global);
998  }
999  if (Ctx.Ptr != Ctx.End)
1000    return make_error<GenericBinaryError>("Global section ended prematurely",
1001                                          object_error::parse_failed);
1002  return Error::success();
1003}
1004
1005Error WasmObjectFile::parseEventSection(ReadContext &Ctx) {
1006  EventSection = Sections.size();
1007  uint32_t Count = readVarint32(Ctx);
1008  Events.reserve(Count);
1009  while (Count--) {
1010    wasm::WasmEvent Event;
1011    Event.Index = NumImportedEvents + Events.size();
1012    Event.Type.Attribute = readVaruint32(Ctx);
1013    Event.Type.SigIndex = readVarint32(Ctx);
1014    Events.push_back(Event);
1015  }
1016
1017  if (Ctx.Ptr != Ctx.End)
1018    return make_error<GenericBinaryError>("Event section ended prematurely",
1019                                          object_error::parse_failed);
1020  return Error::success();
1021}
1022
1023Error WasmObjectFile::parseExportSection(ReadContext &Ctx) {
1024  uint32_t Count = readVaruint32(Ctx);
1025  Exports.reserve(Count);
1026  for (uint32_t I = 0; I < Count; I++) {
1027    wasm::WasmExport Ex;
1028    Ex.Name = readString(Ctx);
1029    Ex.Kind = readUint8(Ctx);
1030    Ex.Index = readVaruint32(Ctx);
1031    switch (Ex.Kind) {
1032    case wasm::WASM_EXTERNAL_FUNCTION:
1033
1034      if (!isDefinedFunctionIndex(Ex.Index))
1035        return make_error<GenericBinaryError>("Invalid function export",
1036                                              object_error::parse_failed);
1037      getDefinedFunction(Ex.Index).ExportName = Ex.Name;
1038      break;
1039    case wasm::WASM_EXTERNAL_GLOBAL:
1040      if (!isValidGlobalIndex(Ex.Index))
1041        return make_error<GenericBinaryError>("Invalid global export",
1042                                              object_error::parse_failed);
1043      break;
1044    case wasm::WASM_EXTERNAL_EVENT:
1045      if (!isValidEventIndex(Ex.Index))
1046        return make_error<GenericBinaryError>("Invalid event export",
1047                                              object_error::parse_failed);
1048      break;
1049    case wasm::WASM_EXTERNAL_MEMORY:
1050    case wasm::WASM_EXTERNAL_TABLE:
1051      break;
1052    default:
1053      return make_error<GenericBinaryError>("Unexpected export kind",
1054                                            object_error::parse_failed);
1055    }
1056    Exports.push_back(Ex);
1057  }
1058  if (Ctx.Ptr != Ctx.End)
1059    return make_error<GenericBinaryError>("Export section ended prematurely",
1060                                          object_error::parse_failed);
1061  return Error::success();
1062}
1063
1064bool WasmObjectFile::isValidFunctionIndex(uint32_t Index) const {
1065  return Index < NumImportedFunctions + FunctionTypes.size();
1066}
1067
1068bool WasmObjectFile::isDefinedFunctionIndex(uint32_t Index) const {
1069  return Index >= NumImportedFunctions && isValidFunctionIndex(Index);
1070}
1071
1072bool WasmObjectFile::isValidGlobalIndex(uint32_t Index) const {
1073  return Index < NumImportedGlobals + Globals.size();
1074}
1075
1076bool WasmObjectFile::isDefinedGlobalIndex(uint32_t Index) const {
1077  return Index >= NumImportedGlobals && isValidGlobalIndex(Index);
1078}
1079
1080bool WasmObjectFile::isValidEventIndex(uint32_t Index) const {
1081  return Index < NumImportedEvents + Events.size();
1082}
1083
1084bool WasmObjectFile::isDefinedEventIndex(uint32_t Index) const {
1085  return Index >= NumImportedEvents && isValidEventIndex(Index);
1086}
1087
1088bool WasmObjectFile::isValidFunctionSymbol(uint32_t Index) const {
1089  return Index < Symbols.size() && Symbols[Index].isTypeFunction();
1090}
1091
1092bool WasmObjectFile::isValidGlobalSymbol(uint32_t Index) const {
1093  return Index < Symbols.size() && Symbols[Index].isTypeGlobal();
1094}
1095
1096bool WasmObjectFile::isValidEventSymbol(uint32_t Index) const {
1097  return Index < Symbols.size() && Symbols[Index].isTypeEvent();
1098}
1099
1100bool WasmObjectFile::isValidDataSymbol(uint32_t Index) const {
1101  return Index < Symbols.size() && Symbols[Index].isTypeData();
1102}
1103
1104bool WasmObjectFile::isValidSectionSymbol(uint32_t Index) const {
1105  return Index < Symbols.size() && Symbols[Index].isTypeSection();
1106}
1107
1108wasm::WasmFunction &WasmObjectFile::getDefinedFunction(uint32_t Index) {
1109  assert(isDefinedFunctionIndex(Index));
1110  return Functions[Index - NumImportedFunctions];
1111}
1112
1113const wasm::WasmFunction &
1114WasmObjectFile::getDefinedFunction(uint32_t Index) const {
1115  assert(isDefinedFunctionIndex(Index));
1116  return Functions[Index - NumImportedFunctions];
1117}
1118
1119wasm::WasmGlobal &WasmObjectFile::getDefinedGlobal(uint32_t Index) {
1120  assert(isDefinedGlobalIndex(Index));
1121  return Globals[Index - NumImportedGlobals];
1122}
1123
1124wasm::WasmEvent &WasmObjectFile::getDefinedEvent(uint32_t Index) {
1125  assert(isDefinedEventIndex(Index));
1126  return Events[Index - NumImportedEvents];
1127}
1128
1129Error WasmObjectFile::parseStartSection(ReadContext &Ctx) {
1130  StartFunction = readVaruint32(Ctx);
1131  if (!isValidFunctionIndex(StartFunction))
1132    return make_error<GenericBinaryError>("Invalid start function",
1133                                          object_error::parse_failed);
1134  return Error::success();
1135}
1136
1137Error WasmObjectFile::parseCodeSection(ReadContext &Ctx) {
1138  SeenCodeSection = true;
1139  CodeSection = Sections.size();
1140  uint32_t FunctionCount = readVaruint32(Ctx);
1141  if (FunctionCount != FunctionTypes.size()) {
1142    return make_error<GenericBinaryError>("Invalid function count",
1143                                          object_error::parse_failed);
1144  }
1145
1146  for (uint32_t i = 0; i < FunctionCount; i++) {
1147    wasm::WasmFunction& Function = Functions[i];
1148    const uint8_t *FunctionStart = Ctx.Ptr;
1149    uint32_t Size = readVaruint32(Ctx);
1150    const uint8_t *FunctionEnd = Ctx.Ptr + Size;
1151
1152    Function.CodeOffset = Ctx.Ptr - FunctionStart;
1153    Function.Index = NumImportedFunctions + i;
1154    Function.CodeSectionOffset = FunctionStart - Ctx.Start;
1155    Function.Size = FunctionEnd - FunctionStart;
1156
1157    uint32_t NumLocalDecls = readVaruint32(Ctx);
1158    Function.Locals.reserve(NumLocalDecls);
1159    while (NumLocalDecls--) {
1160      wasm::WasmLocalDecl Decl;
1161      Decl.Count = readVaruint32(Ctx);
1162      Decl.Type = readUint8(Ctx);
1163      Function.Locals.push_back(Decl);
1164    }
1165
1166    uint32_t BodySize = FunctionEnd - Ctx.Ptr;
1167    Function.Body = ArrayRef<uint8_t>(Ctx.Ptr, BodySize);
1168    // This will be set later when reading in the linking metadata section.
1169    Function.Comdat = UINT32_MAX;
1170    Ctx.Ptr += BodySize;
1171    assert(Ctx.Ptr == FunctionEnd);
1172  }
1173  if (Ctx.Ptr != Ctx.End)
1174    return make_error<GenericBinaryError>("Code section ended prematurely",
1175                                          object_error::parse_failed);
1176  return Error::success();
1177}
1178
1179Error WasmObjectFile::parseElemSection(ReadContext &Ctx) {
1180  uint32_t Count = readVaruint32(Ctx);
1181  ElemSegments.reserve(Count);
1182  while (Count--) {
1183    wasm::WasmElemSegment Segment;
1184    Segment.TableIndex = readVaruint32(Ctx);
1185    if (Segment.TableIndex != 0) {
1186      return make_error<GenericBinaryError>("Invalid TableIndex",
1187                                            object_error::parse_failed);
1188    }
1189    if (Error Err = readInitExpr(Segment.Offset, Ctx))
1190      return Err;
1191    uint32_t NumElems = readVaruint32(Ctx);
1192    while (NumElems--) {
1193      Segment.Functions.push_back(readVaruint32(Ctx));
1194    }
1195    ElemSegments.push_back(Segment);
1196  }
1197  if (Ctx.Ptr != Ctx.End)
1198    return make_error<GenericBinaryError>("Elem section ended prematurely",
1199                                          object_error::parse_failed);
1200  return Error::success();
1201}
1202
1203Error WasmObjectFile::parseDataSection(ReadContext &Ctx) {
1204  DataSection = Sections.size();
1205  uint32_t Count = readVaruint32(Ctx);
1206  if (DataCount && Count != DataCount.getValue())
1207    return make_error<GenericBinaryError>(
1208        "Number of data segments does not match DataCount section");
1209  DataSegments.reserve(Count);
1210  while (Count--) {
1211    WasmSegment Segment;
1212    Segment.Data.InitFlags = readVaruint32(Ctx);
1213    Segment.Data.MemoryIndex = (Segment.Data.InitFlags & wasm::WASM_SEGMENT_HAS_MEMINDEX)
1214                               ? readVaruint32(Ctx) : 0;
1215    if ((Segment.Data.InitFlags & wasm::WASM_SEGMENT_IS_PASSIVE) == 0) {
1216      if (Error Err = readInitExpr(Segment.Data.Offset, Ctx))
1217        return Err;
1218    } else {
1219      Segment.Data.Offset.Opcode = wasm::WASM_OPCODE_I32_CONST;
1220      Segment.Data.Offset.Value.Int32 = 0;
1221    }
1222    uint32_t Size = readVaruint32(Ctx);
1223    if (Size > (size_t)(Ctx.End - Ctx.Ptr))
1224      return make_error<GenericBinaryError>("Invalid segment size",
1225                                            object_error::parse_failed);
1226    Segment.Data.Content = ArrayRef<uint8_t>(Ctx.Ptr, Size);
1227    // The rest of these Data fields are set later, when reading in the linking
1228    // metadata section.
1229    Segment.Data.Alignment = 0;
1230    Segment.Data.LinkerFlags = 0;
1231    Segment.Data.Comdat = UINT32_MAX;
1232    Segment.SectionOffset = Ctx.Ptr - Ctx.Start;
1233    Ctx.Ptr += Size;
1234    DataSegments.push_back(Segment);
1235  }
1236  if (Ctx.Ptr != Ctx.End)
1237    return make_error<GenericBinaryError>("Data section ended prematurely",
1238                                          object_error::parse_failed);
1239  return Error::success();
1240}
1241
1242Error WasmObjectFile::parseDataCountSection(ReadContext &Ctx) {
1243  DataCount = readVaruint32(Ctx);
1244  return Error::success();
1245}
1246
1247const wasm::WasmObjectHeader &WasmObjectFile::getHeader() const {
1248  return Header;
1249}
1250
1251void WasmObjectFile::moveSymbolNext(DataRefImpl &Symb) const { Symb.d.b++; }
1252
1253uint32_t WasmObjectFile::getSymbolFlags(DataRefImpl Symb) const {
1254  uint32_t Result = SymbolRef::SF_None;
1255  const WasmSymbol &Sym = getWasmSymbol(Symb);
1256
1257  LLVM_DEBUG(dbgs() << "getSymbolFlags: ptr=" << &Sym << " " << Sym << "\n");
1258  if (Sym.isBindingWeak())
1259    Result |= SymbolRef::SF_Weak;
1260  if (!Sym.isBindingLocal())
1261    Result |= SymbolRef::SF_Global;
1262  if (Sym.isHidden())
1263    Result |= SymbolRef::SF_Hidden;
1264  if (!Sym.isDefined())
1265    Result |= SymbolRef::SF_Undefined;
1266  if (Sym.isTypeFunction())
1267    Result |= SymbolRef::SF_Executable;
1268  return Result;
1269}
1270
1271basic_symbol_iterator WasmObjectFile::symbol_begin() const {
1272  DataRefImpl Ref;
1273  Ref.d.a = 1; // Arbitrary non-zero value so that Ref.p is non-null
1274  Ref.d.b = 0; // Symbol index
1275  return BasicSymbolRef(Ref, this);
1276}
1277
1278basic_symbol_iterator WasmObjectFile::symbol_end() const {
1279  DataRefImpl Ref;
1280  Ref.d.a = 1; // Arbitrary non-zero value so that Ref.p is non-null
1281  Ref.d.b = Symbols.size(); // Symbol index
1282  return BasicSymbolRef(Ref, this);
1283}
1284
1285const WasmSymbol &WasmObjectFile::getWasmSymbol(const DataRefImpl &Symb) const {
1286  return Symbols[Symb.d.b];
1287}
1288
1289const WasmSymbol &WasmObjectFile::getWasmSymbol(const SymbolRef &Symb) const {
1290  return getWasmSymbol(Symb.getRawDataRefImpl());
1291}
1292
1293Expected<StringRef> WasmObjectFile::getSymbolName(DataRefImpl Symb) const {
1294  return getWasmSymbol(Symb).Info.Name;
1295}
1296
1297Expected<uint64_t> WasmObjectFile::getSymbolAddress(DataRefImpl Symb) const {
1298  auto &Sym = getWasmSymbol(Symb);
1299  if (Sym.Info.Kind == wasm::WASM_SYMBOL_TYPE_FUNCTION &&
1300      isDefinedFunctionIndex(Sym.Info.ElementIndex))
1301    return getDefinedFunction(Sym.Info.ElementIndex).CodeSectionOffset;
1302  else
1303    return getSymbolValue(Symb);
1304}
1305
1306uint64_t WasmObjectFile::getWasmSymbolValue(const WasmSymbol &Sym) const {
1307  switch (Sym.Info.Kind) {
1308  case wasm::WASM_SYMBOL_TYPE_FUNCTION:
1309  case wasm::WASM_SYMBOL_TYPE_GLOBAL:
1310  case wasm::WASM_SYMBOL_TYPE_EVENT:
1311    return Sym.Info.ElementIndex;
1312  case wasm::WASM_SYMBOL_TYPE_DATA: {
1313    // The value of a data symbol is the segment offset, plus the symbol
1314    // offset within the segment.
1315    uint32_t SegmentIndex = Sym.Info.DataRef.Segment;
1316    const wasm::WasmDataSegment &Segment = DataSegments[SegmentIndex].Data;
1317    assert(Segment.Offset.Opcode == wasm::WASM_OPCODE_I32_CONST);
1318    return Segment.Offset.Value.Int32 + Sym.Info.DataRef.Offset;
1319  }
1320  case wasm::WASM_SYMBOL_TYPE_SECTION:
1321    return 0;
1322  }
1323  llvm_unreachable("invalid symbol type");
1324}
1325
1326uint64_t WasmObjectFile::getSymbolValueImpl(DataRefImpl Symb) const {
1327  return getWasmSymbolValue(getWasmSymbol(Symb));
1328}
1329
1330uint32_t WasmObjectFile::getSymbolAlignment(DataRefImpl Symb) const {
1331  llvm_unreachable("not yet implemented");
1332  return 0;
1333}
1334
1335uint64_t WasmObjectFile::getCommonSymbolSizeImpl(DataRefImpl Symb) const {
1336  llvm_unreachable("not yet implemented");
1337  return 0;
1338}
1339
1340Expected<SymbolRef::Type>
1341WasmObjectFile::getSymbolType(DataRefImpl Symb) const {
1342  const WasmSymbol &Sym = getWasmSymbol(Symb);
1343
1344  switch (Sym.Info.Kind) {
1345  case wasm::WASM_SYMBOL_TYPE_FUNCTION:
1346    return SymbolRef::ST_Function;
1347  case wasm::WASM_SYMBOL_TYPE_GLOBAL:
1348    return SymbolRef::ST_Other;
1349  case wasm::WASM_SYMBOL_TYPE_DATA:
1350    return SymbolRef::ST_Data;
1351  case wasm::WASM_SYMBOL_TYPE_SECTION:
1352    return SymbolRef::ST_Debug;
1353  case wasm::WASM_SYMBOL_TYPE_EVENT:
1354    return SymbolRef::ST_Other;
1355  }
1356
1357  llvm_unreachable("Unknown WasmSymbol::SymbolType");
1358  return SymbolRef::ST_Other;
1359}
1360
1361Expected<section_iterator>
1362WasmObjectFile::getSymbolSection(DataRefImpl Symb) const {
1363  const WasmSymbol &Sym = getWasmSymbol(Symb);
1364  if (Sym.isUndefined())
1365    return section_end();
1366
1367  DataRefImpl Ref;
1368  switch (Sym.Info.Kind) {
1369  case wasm::WASM_SYMBOL_TYPE_FUNCTION:
1370    Ref.d.a = CodeSection;
1371    break;
1372  case wasm::WASM_SYMBOL_TYPE_GLOBAL:
1373    Ref.d.a = GlobalSection;
1374    break;
1375  case wasm::WASM_SYMBOL_TYPE_DATA:
1376    Ref.d.a = DataSection;
1377    break;
1378  case wasm::WASM_SYMBOL_TYPE_SECTION:
1379    Ref.d.a = Sym.Info.ElementIndex;
1380    break;
1381  case wasm::WASM_SYMBOL_TYPE_EVENT:
1382    Ref.d.a = EventSection;
1383    break;
1384  default:
1385    llvm_unreachable("Unknown WasmSymbol::SymbolType");
1386  }
1387  return section_iterator(SectionRef(Ref, this));
1388}
1389
1390void WasmObjectFile::moveSectionNext(DataRefImpl &Sec) const { Sec.d.a++; }
1391
1392Expected<StringRef> WasmObjectFile::getSectionName(DataRefImpl Sec) const {
1393  const WasmSection &S = Sections[Sec.d.a];
1394#define ECase(X)                                                               \
1395  case wasm::WASM_SEC_##X:                                                     \
1396    return #X;
1397  switch (S.Type) {
1398    ECase(TYPE);
1399    ECase(IMPORT);
1400    ECase(FUNCTION);
1401    ECase(TABLE);
1402    ECase(MEMORY);
1403    ECase(GLOBAL);
1404    ECase(EVENT);
1405    ECase(EXPORT);
1406    ECase(START);
1407    ECase(ELEM);
1408    ECase(CODE);
1409    ECase(DATA);
1410    ECase(DATACOUNT);
1411  case wasm::WASM_SEC_CUSTOM:
1412    return S.Name;
1413  default:
1414    return createStringError(object_error::invalid_section_index, "");
1415  }
1416#undef ECase
1417}
1418
1419uint64_t WasmObjectFile::getSectionAddress(DataRefImpl Sec) const { return 0; }
1420
1421uint64_t WasmObjectFile::getSectionIndex(DataRefImpl Sec) const {
1422  return Sec.d.a;
1423}
1424
1425uint64_t WasmObjectFile::getSectionSize(DataRefImpl Sec) const {
1426  const WasmSection &S = Sections[Sec.d.a];
1427  return S.Content.size();
1428}
1429
1430Expected<ArrayRef<uint8_t>>
1431WasmObjectFile::getSectionContents(DataRefImpl Sec) const {
1432  const WasmSection &S = Sections[Sec.d.a];
1433  // This will never fail since wasm sections can never be empty (user-sections
1434  // must have a name and non-user sections each have a defined structure).
1435  return S.Content;
1436}
1437
1438uint64_t WasmObjectFile::getSectionAlignment(DataRefImpl Sec) const {
1439  return 1;
1440}
1441
1442bool WasmObjectFile::isSectionCompressed(DataRefImpl Sec) const {
1443  return false;
1444}
1445
1446bool WasmObjectFile::isSectionText(DataRefImpl Sec) const {
1447  return getWasmSection(Sec).Type == wasm::WASM_SEC_CODE;
1448}
1449
1450bool WasmObjectFile::isSectionData(DataRefImpl Sec) const {
1451  return getWasmSection(Sec).Type == wasm::WASM_SEC_DATA;
1452}
1453
1454bool WasmObjectFile::isSectionBSS(DataRefImpl Sec) const { return false; }
1455
1456bool WasmObjectFile::isSectionVirtual(DataRefImpl Sec) const { return false; }
1457
1458bool WasmObjectFile::isSectionBitcode(DataRefImpl Sec) const { return false; }
1459
1460relocation_iterator WasmObjectFile::section_rel_begin(DataRefImpl Ref) const {
1461  DataRefImpl RelocRef;
1462  RelocRef.d.a = Ref.d.a;
1463  RelocRef.d.b = 0;
1464  return relocation_iterator(RelocationRef(RelocRef, this));
1465}
1466
1467relocation_iterator WasmObjectFile::section_rel_end(DataRefImpl Ref) const {
1468  const WasmSection &Sec = getWasmSection(Ref);
1469  DataRefImpl RelocRef;
1470  RelocRef.d.a = Ref.d.a;
1471  RelocRef.d.b = Sec.Relocations.size();
1472  return relocation_iterator(RelocationRef(RelocRef, this));
1473}
1474
1475void WasmObjectFile::moveRelocationNext(DataRefImpl &Rel) const { Rel.d.b++; }
1476
1477uint64_t WasmObjectFile::getRelocationOffset(DataRefImpl Ref) const {
1478  const wasm::WasmRelocation &Rel = getWasmRelocation(Ref);
1479  return Rel.Offset;
1480}
1481
1482symbol_iterator WasmObjectFile::getRelocationSymbol(DataRefImpl Ref) const {
1483  const wasm::WasmRelocation &Rel = getWasmRelocation(Ref);
1484  if (Rel.Type == wasm::R_WASM_TYPE_INDEX_LEB)
1485    return symbol_end();
1486  DataRefImpl Sym;
1487  Sym.d.a = 1;
1488  Sym.d.b = Rel.Index;
1489  return symbol_iterator(SymbolRef(Sym, this));
1490}
1491
1492uint64_t WasmObjectFile::getRelocationType(DataRefImpl Ref) const {
1493  const wasm::WasmRelocation &Rel = getWasmRelocation(Ref);
1494  return Rel.Type;
1495}
1496
1497void WasmObjectFile::getRelocationTypeName(
1498    DataRefImpl Ref, SmallVectorImpl<char> &Result) const {
1499  const wasm::WasmRelocation &Rel = getWasmRelocation(Ref);
1500  StringRef Res = "Unknown";
1501
1502#define WASM_RELOC(name, value)                                                \
1503  case wasm::name:                                                             \
1504    Res = #name;                                                               \
1505    break;
1506
1507  switch (Rel.Type) {
1508#include "llvm/BinaryFormat/WasmRelocs.def"
1509  }
1510
1511#undef WASM_RELOC
1512
1513  Result.append(Res.begin(), Res.end());
1514}
1515
1516section_iterator WasmObjectFile::section_begin() const {
1517  DataRefImpl Ref;
1518  Ref.d.a = 0;
1519  return section_iterator(SectionRef(Ref, this));
1520}
1521
1522section_iterator WasmObjectFile::section_end() const {
1523  DataRefImpl Ref;
1524  Ref.d.a = Sections.size();
1525  return section_iterator(SectionRef(Ref, this));
1526}
1527
1528uint8_t WasmObjectFile::getBytesInAddress() const { return 4; }
1529
1530StringRef WasmObjectFile::getFileFormatName() const { return "WASM"; }
1531
1532Triple::ArchType WasmObjectFile::getArch() const { return Triple::wasm32; }
1533
1534SubtargetFeatures WasmObjectFile::getFeatures() const {
1535  return SubtargetFeatures();
1536}
1537
1538bool WasmObjectFile::isRelocatableObject() const { return HasLinkingSection; }
1539
1540bool WasmObjectFile::isSharedObject() const { return HasDylinkSection; }
1541
1542const WasmSection &WasmObjectFile::getWasmSection(DataRefImpl Ref) const {
1543  assert(Ref.d.a < Sections.size());
1544  return Sections[Ref.d.a];
1545}
1546
1547const WasmSection &
1548WasmObjectFile::getWasmSection(const SectionRef &Section) const {
1549  return getWasmSection(Section.getRawDataRefImpl());
1550}
1551
1552const wasm::WasmRelocation &
1553WasmObjectFile::getWasmRelocation(const RelocationRef &Ref) const {
1554  return getWasmRelocation(Ref.getRawDataRefImpl());
1555}
1556
1557const wasm::WasmRelocation &
1558WasmObjectFile::getWasmRelocation(DataRefImpl Ref) const {
1559  assert(Ref.d.a < Sections.size());
1560  const WasmSection &Sec = Sections[Ref.d.a];
1561  assert(Ref.d.b < Sec.Relocations.size());
1562  return Sec.Relocations[Ref.d.b];
1563}
1564
1565int WasmSectionOrderChecker::getSectionOrder(unsigned ID,
1566                                             StringRef CustomSectionName) {
1567  switch (ID) {
1568  case wasm::WASM_SEC_CUSTOM:
1569    return StringSwitch<unsigned>(CustomSectionName)
1570        .Case("dylink", WASM_SEC_ORDER_DYLINK)
1571        .Case("linking", WASM_SEC_ORDER_LINKING)
1572        .StartsWith("reloc.", WASM_SEC_ORDER_RELOC)
1573        .Case("name", WASM_SEC_ORDER_NAME)
1574        .Case("producers", WASM_SEC_ORDER_PRODUCERS)
1575        .Case("target_features", WASM_SEC_ORDER_TARGET_FEATURES)
1576        .Default(WASM_SEC_ORDER_NONE);
1577  case wasm::WASM_SEC_TYPE:
1578    return WASM_SEC_ORDER_TYPE;
1579  case wasm::WASM_SEC_IMPORT:
1580    return WASM_SEC_ORDER_IMPORT;
1581  case wasm::WASM_SEC_FUNCTION:
1582    return WASM_SEC_ORDER_FUNCTION;
1583  case wasm::WASM_SEC_TABLE:
1584    return WASM_SEC_ORDER_TABLE;
1585  case wasm::WASM_SEC_MEMORY:
1586    return WASM_SEC_ORDER_MEMORY;
1587  case wasm::WASM_SEC_GLOBAL:
1588    return WASM_SEC_ORDER_GLOBAL;
1589  case wasm::WASM_SEC_EXPORT:
1590    return WASM_SEC_ORDER_EXPORT;
1591  case wasm::WASM_SEC_START:
1592    return WASM_SEC_ORDER_START;
1593  case wasm::WASM_SEC_ELEM:
1594    return WASM_SEC_ORDER_ELEM;
1595  case wasm::WASM_SEC_CODE:
1596    return WASM_SEC_ORDER_CODE;
1597  case wasm::WASM_SEC_DATA:
1598    return WASM_SEC_ORDER_DATA;
1599  case wasm::WASM_SEC_DATACOUNT:
1600    return WASM_SEC_ORDER_DATACOUNT;
1601  case wasm::WASM_SEC_EVENT:
1602    return WASM_SEC_ORDER_EVENT;
1603  default:
1604    return WASM_SEC_ORDER_NONE;
1605  }
1606}
1607
1608// Represents the edges in a directed graph where any node B reachable from node
1609// A is not allowed to appear before A in the section ordering, but may appear
1610// afterward.
1611int WasmSectionOrderChecker::DisallowedPredecessors[WASM_NUM_SEC_ORDERS][WASM_NUM_SEC_ORDERS] = {
1612  {}, // WASM_SEC_ORDER_NONE
1613  {WASM_SEC_ORDER_TYPE, WASM_SEC_ORDER_IMPORT}, // WASM_SEC_ORDER_TYPE,
1614  {WASM_SEC_ORDER_IMPORT, WASM_SEC_ORDER_FUNCTION}, // WASM_SEC_ORDER_IMPORT,
1615  {WASM_SEC_ORDER_FUNCTION, WASM_SEC_ORDER_TABLE}, // WASM_SEC_ORDER_FUNCTION,
1616  {WASM_SEC_ORDER_TABLE, WASM_SEC_ORDER_MEMORY}, // WASM_SEC_ORDER_TABLE,
1617  {WASM_SEC_ORDER_MEMORY, WASM_SEC_ORDER_GLOBAL}, // WASM_SEC_ORDER_MEMORY,
1618  {WASM_SEC_ORDER_GLOBAL, WASM_SEC_ORDER_EVENT}, // WASM_SEC_ORDER_GLOBAL,
1619  {WASM_SEC_ORDER_EVENT, WASM_SEC_ORDER_EXPORT}, // WASM_SEC_ORDER_EVENT,
1620  {WASM_SEC_ORDER_EXPORT, WASM_SEC_ORDER_START}, // WASM_SEC_ORDER_EXPORT,
1621  {WASM_SEC_ORDER_START, WASM_SEC_ORDER_ELEM}, // WASM_SEC_ORDER_START,
1622  {WASM_SEC_ORDER_ELEM, WASM_SEC_ORDER_DATACOUNT}, // WASM_SEC_ORDER_ELEM,
1623  {WASM_SEC_ORDER_DATACOUNT, WASM_SEC_ORDER_CODE}, // WASM_SEC_ORDER_DATACOUNT,
1624  {WASM_SEC_ORDER_CODE, WASM_SEC_ORDER_DATA}, // WASM_SEC_ORDER_CODE,
1625  {WASM_SEC_ORDER_DATA, WASM_SEC_ORDER_LINKING}, // WASM_SEC_ORDER_DATA,
1626
1627  // Custom Sections
1628  {WASM_SEC_ORDER_DYLINK, WASM_SEC_ORDER_TYPE}, // WASM_SEC_ORDER_DYLINK,
1629  {WASM_SEC_ORDER_LINKING, WASM_SEC_ORDER_RELOC, WASM_SEC_ORDER_NAME}, // WASM_SEC_ORDER_LINKING,
1630  {}, // WASM_SEC_ORDER_RELOC (can be repeated),
1631  {WASM_SEC_ORDER_NAME, WASM_SEC_ORDER_PRODUCERS}, // WASM_SEC_ORDER_NAME,
1632  {WASM_SEC_ORDER_PRODUCERS, WASM_SEC_ORDER_TARGET_FEATURES}, // WASM_SEC_ORDER_PRODUCERS,
1633  {WASM_SEC_ORDER_TARGET_FEATURES}  // WASM_SEC_ORDER_TARGET_FEATURES
1634};
1635
1636bool WasmSectionOrderChecker::isValidSectionOrder(unsigned ID,
1637                                                  StringRef CustomSectionName) {
1638  int Order = getSectionOrder(ID, CustomSectionName);
1639  if (Order == WASM_SEC_ORDER_NONE)
1640    return true;
1641
1642  // Disallowed predecessors we need to check for
1643  SmallVector<int, WASM_NUM_SEC_ORDERS> WorkList;
1644
1645  // Keep track of completed checks to avoid repeating work
1646  bool Checked[WASM_NUM_SEC_ORDERS] = {};
1647
1648  int Curr = Order;
1649  while (true) {
1650    // Add new disallowed predecessors to work list
1651    for (size_t I = 0;; ++I) {
1652      int Next = DisallowedPredecessors[Curr][I];
1653      if (Next == WASM_SEC_ORDER_NONE)
1654        break;
1655      if (Checked[Next])
1656        continue;
1657      WorkList.push_back(Next);
1658      Checked[Next] = true;
1659    }
1660
1661    if (WorkList.empty())
1662      break;
1663
1664    // Consider next disallowed predecessor
1665    Curr = WorkList.pop_back_val();
1666    if (Seen[Curr])
1667      return false;
1668  }
1669
1670  // Have not seen any disallowed predecessors
1671  Seen[Order] = true;
1672  return true;
1673}
1674