contrib/llvm/tools/lld/ELF/ScriptParser.cpp

   1 //===- ScriptParser.cpp ---------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains a recursive-descendent parser for linker scripts.
  11 // Parsed results are stored to Config and Script global objects.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "ScriptParser.h"
  16 #include "Config.h"
  17 #include "Driver.h"
  18 #include "InputSection.h"
  19 #include "LinkerScript.h"
  20 #include "OutputSections.h"
  21 #include "ScriptLexer.h"
  22 #include "Symbols.h"
  23 #include "Target.h"
  24 #include "lld/Common/Memory.h"
  25 #include "llvm/ADT/SmallString.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/ADT/StringSet.h"
  28 #include "llvm/ADT/StringSwitch.h"
  29 #include "llvm/BinaryFormat/ELF.h"
  30 #include "llvm/Support/Casting.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/FileSystem.h"
  33 #include "llvm/Support/Path.h"
  34 #include <cassert>
  35 #include <limits>
  36 #include <vector>
  37
  38 using namespace llvm;
  39 using namespace llvm::ELF;
  40 using namespace llvm::support::endian;
  41 using namespace lld;
  42 using namespace lld::elf;
  43
  44 static bool isUnderSysroot(StringRef Path);
  45
  46 namespace {
  47 class ScriptParser final : ScriptLexer {
  48 public:
  49   ScriptParser(MemoryBufferRef MB)
  50       : ScriptLexer(MB),
  51         IsUnderSysroot(isUnderSysroot(MB.getBufferIdentifier())) {}
  52
  53   void readLinkerScript();
  54   void readVersionScript();
  55   void readDynamicList();
  56   void readDefsym(StringRef Name);
  57
  58 private:
  59   void addFile(StringRef Path);
  60
  61   void readAsNeeded();
  62   void readEntry();
  63   void readExtern();
  64   void readGroup();
  65   void readInclude();
  66   void readInput();
  67   void readMemory();
  68   void readOutput();
  69   void readOutputArch();
  70   void readOutputFormat();
  71   void readPhdrs();
  72   void readRegionAlias();
  73   void readSearchDir();
  74   void readSections();
  75   void readTarget();
  76   void readVersion();
  77   void readVersionScriptCommand();
  78
  79   SymbolAssignment *readSymbolAssignment(StringRef Name);
  80   ByteCommand *readByteCommand(StringRef Tok);
  81   std::array<uint8_t, 4> readFill();
  82   std::array<uint8_t, 4> parseFill(StringRef Tok);
  83   bool readSectionDirective(OutputSection *Cmd, StringRef Tok1, StringRef Tok2);
  84   void readSectionAddressType(OutputSection *Cmd);
  85   OutputSection *readOverlaySectionDescription();
  86   OutputSection *readOutputSectionDescription(StringRef OutSec);
  87   std::vector<BaseCommand *> readOverlay();
  88   std::vector<StringRef> readOutputSectionPhdrs();
  89   InputSectionDescription *readInputSectionDescription(StringRef Tok);
  90   StringMatcher readFilePatterns();
  91   std::vector<SectionPattern> readInputSectionsList();
  92   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
  93   unsigned readPhdrType();
  94   SortSectionPolicy readSortKind();
  95   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
  96   SymbolAssignment *readAssignment(StringRef Tok);
  97   void readSort();
  98   Expr readAssert();
  99   Expr readConstant();
 100   Expr getPageSize();
 101
 102   uint64_t readMemoryAssignment(StringRef, StringRef, StringRef);
 103   std::pair<uint32_t, uint32_t> readMemoryAttributes();
 104
 105   Expr combine(StringRef Op, Expr L, Expr R);
 106   Expr readExpr();
 107   Expr readExpr1(Expr Lhs, int MinPrec);
 108   StringRef readParenLiteral();
 109   Expr readPrimary();
 110   Expr readTernary(Expr Cond);
 111   Expr readParenExpr();
 112
 113   // For parsing version script.
 114   std::vector<SymbolVersion> readVersionExtern();
 115   void readAnonymousDeclaration();
 116   void readVersionDeclaration(StringRef VerStr);
 117
 118   std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
 119   readSymbols();
 120
 121   // True if a script being read is in a subdirectory specified by -sysroot.
 122   bool IsUnderSysroot;
 123
 124   // A set to detect an INCLUDE() cycle.
 125   StringSet<> Seen;
 126 };
 127 } // namespace
 128
 129 static StringRef unquote(StringRef S) {
 130   if (S.startswith("\""))
 131     return S.substr(1, S.size() - 2);
 132   return S;
 133 }
 134
 135 static bool isUnderSysroot(StringRef Path) {
 136   if (Config->Sysroot == "")
 137     return false;
 138   for (; !Path.empty(); Path = sys::path::parent_path(Path))
 139     if (sys::fs::equivalent(Config->Sysroot, Path))
 140       return true;
 141   return false;
 142 }
 143
 144 // Some operations only support one non absolute value. Move the
 145 // absolute one to the right hand side for convenience.
 146 static void moveAbsRight(ExprValue &A, ExprValue &B) {
 147   if (A.Sec == nullptr || (A.ForceAbsolute && !B.isAbsolute()))
 148     std::swap(A, B);
 149   if (!B.isAbsolute())
 150     error(A.Loc + ": at least one side of the expression must be absolute");
 151 }
 152
 153 static ExprValue add(ExprValue A, ExprValue B) {
 154   moveAbsRight(A, B);
 155   return {A.Sec, A.ForceAbsolute, A.getSectionOffset() + B.getValue(), A.Loc};
 156 }
 157
 158 static ExprValue sub(ExprValue A, ExprValue B) {
 159   // The distance between two symbols in sections is absolute.
 160   if (!A.isAbsolute() && !B.isAbsolute())
 161     return A.getValue() - B.getValue();
 162   return {A.Sec, false, A.getSectionOffset() - B.getValue(), A.Loc};
 163 }
 164
 165 static ExprValue bitAnd(ExprValue A, ExprValue B) {
 166   moveAbsRight(A, B);
 167   return {A.Sec, A.ForceAbsolute,
 168           (A.getValue() & B.getValue()) - A.getSecAddr(), A.Loc};
 169 }
 170
 171 static ExprValue bitOr(ExprValue A, ExprValue B) {
 172   moveAbsRight(A, B);
 173   return {A.Sec, A.ForceAbsolute,
 174           (A.getValue() | B.getValue()) - A.getSecAddr(), A.Loc};
 175 }
 176
 177 void ScriptParser::readDynamicList() {
 178   Config->HasDynamicList = true;
 179   expect("{");
 180   std::vector<SymbolVersion> Locals;
 181   std::vector<SymbolVersion> Globals;
 182   std::tie(Locals, Globals) = readSymbols();
 183   expect(";");
 184
 185   if (!atEOF()) {
 186     setError("EOF expected, but got " + next());
 187     return;
 188   }
 189   if (!Locals.empty()) {
 190     setError("\"local:\" scope not supported in --dynamic-list");
 191     return;
 192   }
 193
 194   for (SymbolVersion V : Globals)
 195     Config->DynamicList.push_back(V);
 196 }
 197
 198 void ScriptParser::readVersionScript() {
 199   readVersionScriptCommand();
 200   if (!atEOF())
 201     setError("EOF expected, but got " + next());
 202 }
 203
 204 void ScriptParser::readVersionScriptCommand() {
 205   if (consume("{")) {
 206     readAnonymousDeclaration();
 207     return;
 208   }
 209
 210   while (!atEOF() && !errorCount() && peek() != "}") {
 211     StringRef VerStr = next();
 212     if (VerStr == "{") {
 213       setError("anonymous version definition is used in "
 214                "combination with other version definitions");
 215       return;
 216     }
 217     expect("{");
 218     readVersionDeclaration(VerStr);
 219   }
 220 }
 221
 222 void ScriptParser::readVersion() {
 223   expect("{");
 224   readVersionScriptCommand();
 225   expect("}");
 226 }
 227
 228 void ScriptParser::readLinkerScript() {
 229   while (!atEOF()) {
 230     StringRef Tok = next();
 231     if (Tok == ";")
 232       continue;
 233
 234     if (Tok == "ENTRY") {
 235       readEntry();
 236     } else if (Tok == "EXTERN") {
 237       readExtern();
 238     } else if (Tok == "GROUP") {
 239       readGroup();
 240     } else if (Tok == "INCLUDE") {
 241       readInclude();
 242     } else if (Tok == "INPUT") {
 243       readInput();
 244     } else if (Tok == "MEMORY") {
 245       readMemory();
 246     } else if (Tok == "OUTPUT") {
 247       readOutput();
 248     } else if (Tok == "OUTPUT_ARCH") {
 249       readOutputArch();
 250     } else if (Tok == "OUTPUT_FORMAT") {
 251       readOutputFormat();
 252     } else if (Tok == "PHDRS") {
 253       readPhdrs();
 254     } else if (Tok == "REGION_ALIAS") {
 255       readRegionAlias();
 256     } else if (Tok == "SEARCH_DIR") {
 257       readSearchDir();
 258     } else if (Tok == "SECTIONS") {
 259       readSections();
 260     } else if (Tok == "TARGET") {
 261       readTarget();
 262     } else if (Tok == "VERSION") {
 263       readVersion();
 264     } else if (SymbolAssignment *Cmd = readAssignment(Tok)) {
 265       Script->SectionCommands.push_back(Cmd);
 266     } else {
 267       setError("unknown directive: " + Tok);
 268     }
 269   }
 270 }
 271
 272 void ScriptParser::readDefsym(StringRef Name) {
 273   if (errorCount())
 274     return;
 275   Expr E = readExpr();
 276   if (!atEOF())
 277     setError("EOF expected, but got " + next());
 278   SymbolAssignment *Cmd = make<SymbolAssignment>(Name, E, getCurrentLocation());
 279   Script->SectionCommands.push_back(Cmd);
 280 }
 281
 282 void ScriptParser::addFile(StringRef S) {
 283   if (IsUnderSysroot && S.startswith("/")) {
 284     SmallString<128> PathData;
 285     StringRef Path = (Config->Sysroot + S).toStringRef(PathData);
 286     if (sys::fs::exists(Path)) {
 287       Driver->addFile(Saver.save(Path), /*WithLOption=*/false);
 288       return;
 289     }
 290   }
 291
 292   if (S.startswith("/")) {
 293     Driver->addFile(S, /*WithLOption=*/false);
 294   } else if (S.startswith("=")) {
 295     if (Config->Sysroot.empty())
 296       Driver->addFile(S.substr(1), /*WithLOption=*/false);
 297     else
 298       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)),
 299                       /*WithLOption=*/false);
 300   } else if (S.startswith("-l")) {
 301     Driver->addLibrary(S.substr(2));
 302   } else if (sys::fs::exists(S)) {
 303     Driver->addFile(S, /*WithLOption=*/false);
 304   } else {
 305     if (Optional<std::string> Path = findFromSearchPaths(S))
 306       Driver->addFile(Saver.save(*Path), /*WithLOption=*/true);
 307     else
 308       setError("unable to find " + S);
 309   }
 310 }
 311
 312 void ScriptParser::readAsNeeded() {
 313   expect("(");
 314   bool Orig = Config->AsNeeded;
 315   Config->AsNeeded = true;
 316   while (!errorCount() && !consume(")"))
 317     addFile(unquote(next()));
 318   Config->AsNeeded = Orig;
 319 }
 320
 321 void ScriptParser::readEntry() {
 322   // -e <symbol> takes predecence over ENTRY(<symbol>).
 323   expect("(");
 324   StringRef Tok = next();
 325   if (Config->Entry.empty())
 326     Config->Entry = Tok;
 327   expect(")");
 328 }
 329
 330 void ScriptParser::readExtern() {
 331   expect("(");
 332   while (!errorCount() && !consume(")"))
 333     Config->Undefined.push_back(next());
 334 }
 335
 336 void ScriptParser::readGroup() {
 337   bool Orig = InputFile::IsInGroup;
 338   InputFile::IsInGroup = true;
 339   readInput();
 340   InputFile::IsInGroup = Orig;
 341   if (!Orig)
 342     ++InputFile::NextGroupId;
 343 }
 344
 345 void ScriptParser::readInclude() {
 346   StringRef Tok = unquote(next());
 347
 348   if (!Seen.insert(Tok).second) {
 349     setError("there is a cycle in linker script INCLUDEs");
 350     return;
 351   }
 352
 353   if (Optional<std::string> Path = searchScript(Tok)) {
 354     if (Optional<MemoryBufferRef> MB = readFile(*Path))
 355       tokenize(*MB);
 356     return;
 357   }
 358   setError("cannot find linker script " + Tok);
 359 }
 360
 361 void ScriptParser::readInput() {
 362   expect("(");
 363   while (!errorCount() && !consume(")")) {
 364     if (consume("AS_NEEDED"))
 365       readAsNeeded();
 366     else
 367       addFile(unquote(next()));
 368   }
 369 }
 370
 371 void ScriptParser::readOutput() {
 372   // -o <file> takes predecence over OUTPUT(<file>).
 373   expect("(");
 374   StringRef Tok = next();
 375   if (Config->OutputFile.empty())
 376     Config->OutputFile = unquote(Tok);
 377   expect(")");
 378 }
 379
 380 void ScriptParser::readOutputArch() {
 381   // OUTPUT_ARCH is ignored for now.
 382   expect("(");
 383   while (!errorCount() && !consume(")"))
 384     skip();
 385 }
 386
 387 static std::pair<ELFKind, uint16_t> parseBfdName(StringRef S) {
 388   return StringSwitch<std::pair<ELFKind, uint16_t>>(S)
 389       .Case("elf32-i386", {ELF32LEKind, EM_386})
 390       .Case("elf32-iamcu", {ELF32LEKind, EM_IAMCU})
 391       .Case("elf32-littlearm", {ELF32LEKind, EM_ARM})
 392       .Case("elf32-x86-64", {ELF32LEKind, EM_X86_64})
 393       .Case("elf64-aarch64", {ELF64LEKind, EM_AARCH64})
 394       .Case("elf64-littleaarch64", {ELF64LEKind, EM_AARCH64})
 395       .Case("elf32-powerpc", {ELF32BEKind, EM_PPC})
 396       .Case("elf64-powerpc", {ELF64BEKind, EM_PPC64})
 397       .Case("elf64-powerpcle", {ELF64LEKind, EM_PPC64})
 398       .Case("elf64-x86-64", {ELF64LEKind, EM_X86_64})
 399       .Cases("elf32-tradbigmips", "elf32-bigmips", {ELF32BEKind, EM_MIPS})
 400       .Case("elf32-ntradbigmips", {ELF32BEKind, EM_MIPS})
 401       .Case("elf32-tradlittlemips", {ELF32LEKind, EM_MIPS})
 402       .Case("elf32-ntradlittlemips", {ELF32LEKind, EM_MIPS})
 403       .Case("elf64-tradbigmips", {ELF64BEKind, EM_MIPS})
 404       .Case("elf64-tradlittlemips", {ELF64LEKind, EM_MIPS})
 405       .Default({ELFNoneKind, EM_NONE});
 406 }
 407
 408 // Parse OUTPUT_FORMAT(bfdname) or OUTPUT_FORMAT(bfdname, big, little).
 409 // Currently we ignore big and little parameters.
 410 void ScriptParser::readOutputFormat() {
 411   expect("(");
 412
 413   StringRef Name = unquote(next());
 414   StringRef S = Name;
 415   if (S.consume_back("-freebsd"))
 416     Config->OSABI = ELFOSABI_FREEBSD;
 417
 418   std::tie(Config->EKind, Config->EMachine) = parseBfdName(S);
 419   if (Config->EMachine == EM_NONE)
 420     setError("unknown output format name: " + Name);
 421   if (S == "elf32-ntradlittlemips" || S == "elf32-ntradbigmips")
 422     Config->MipsN32Abi = true;
 423
 424   if (consume(")"))
 425     return;
 426   expect(",");
 427   skip();
 428   expect(",");
 429   skip();
 430   expect(")");
 431 }
 432
 433 void ScriptParser::readPhdrs() {
 434   expect("{");
 435
 436   while (!errorCount() && !consume("}")) {
 437     PhdrsCommand Cmd;
 438     Cmd.Name = next();
 439     Cmd.Type = readPhdrType();
 440
 441     while (!errorCount() && !consume(";")) {
 442       if (consume("FILEHDR"))
 443         Cmd.HasFilehdr = true;
 444       else if (consume("PHDRS"))
 445         Cmd.HasPhdrs = true;
 446       else if (consume("AT"))
 447         Cmd.LMAExpr = readParenExpr();
 448       else if (consume("FLAGS"))
 449         Cmd.Flags = readParenExpr()().getValue();
 450       else
 451         setError("unexpected header attribute: " + next());
 452     }
 453
 454     Script->PhdrsCommands.push_back(Cmd);
 455   }
 456 }
 457
 458 void ScriptParser::readRegionAlias() {
 459   expect("(");
 460   StringRef Alias = unquote(next());
 461   expect(",");
 462   StringRef Name = next();
 463   expect(")");
 464
 465   if (Script->MemoryRegions.count(Alias))
 466     setError("redefinition of memory region '" + Alias + "'");
 467   if (!Script->MemoryRegions.count(Name))
 468     setError("memory region '" + Name + "' is not defined");
 469   Script->MemoryRegions.insert({Alias, Script->MemoryRegions[Name]});
 470 }
 471
 472 void ScriptParser::readSearchDir() {
 473   expect("(");
 474   StringRef Tok = next();
 475   if (!Config->Nostdlib)
 476     Config->SearchPaths.push_back(unquote(Tok));
 477   expect(")");
 478 }
 479
 480 // This reads an overlay description. Overlays are used to describe output
 481 // sections that use the same virtual memory range and normally would trigger
 482 // linker's sections sanity check failures.
 483 // https://sourceware.org/binutils/docs/ld/Overlay-Description.html#Overlay-Description
 484 std::vector<BaseCommand *> ScriptParser::readOverlay() {
 485   // VA and LMA expressions are optional, though for simplicity of
 486   // implementation we assume they are not. That is what OVERLAY was designed
 487   // for first of all: to allow sections with overlapping VAs at different LMAs.
 488   Expr AddrExpr = readExpr();
 489   expect(":");
 490   expect("AT");
 491   Expr LMAExpr = readParenExpr();
 492   expect("{");
 493
 494   std::vector<BaseCommand *> V;
 495   OutputSection *Prev = nullptr;
 496   while (!errorCount() && !consume("}")) {
 497     // VA is the same for all sections. The LMAs are consecutive in memory
 498     // starting from the base load address specified.
 499     OutputSection *OS = readOverlaySectionDescription();
 500     OS->AddrExpr = AddrExpr;
 501     if (Prev)
 502       OS->LMAExpr = [=] { return Prev->getLMA() + Prev->Size; };
 503     else
 504       OS->LMAExpr = LMAExpr;
 505     V.push_back(OS);
 506     Prev = OS;
 507   }
 508
 509   // According to the specification, at the end of the overlay, the location
 510   // counter should be equal to the overlay base address plus size of the
 511   // largest section seen in the overlay.
 512   // Here we want to create the Dot assignment command to achieve that.
 513   Expr MoveDot = [=] {
 514     uint64_t Max = 0;
 515     for (BaseCommand *Cmd : V)
 516       Max = std::max(Max, cast<OutputSection>(Cmd)->Size);
 517     return AddrExpr().getValue() + Max;
 518   };
 519   V.push_back(make<SymbolAssignment>(".", MoveDot, getCurrentLocation()));
 520   return V;
 521 }
 522
 523 void ScriptParser::readSections() {
 524   Script->HasSectionsCommand = true;
 525
 526   // -no-rosegment is used to avoid placing read only non-executable sections in
 527   // their own segment. We do the same if SECTIONS command is present in linker
 528   // script. See comment for computeFlags().
 529   Config->SingleRoRx = true;
 530
 531   expect("{");
 532   std::vector<BaseCommand *> V;
 533   while (!errorCount() && !consume("}")) {
 534     StringRef Tok = next();
 535     if (Tok == "OVERLAY") {
 536       for (BaseCommand *Cmd : readOverlay())
 537         V.push_back(Cmd);
 538       continue;
 539     } else if (Tok == "INCLUDE") {
 540       readInclude();
 541       continue;
 542     }
 543
 544     if (BaseCommand *Cmd = readAssignment(Tok))
 545       V.push_back(Cmd);
 546     else
 547       V.push_back(readOutputSectionDescription(Tok));
 548   }
 549
 550   if (!atEOF() && consume("INSERT")) {
 551     std::vector<BaseCommand *> *Dest = nullptr;
 552     if (consume("AFTER"))
 553       Dest = &Script->InsertAfterCommands[next()];
 554     else if (consume("BEFORE"))
 555       Dest = &Script->InsertBeforeCommands[next()];
 556     else
 557       setError("expected AFTER/BEFORE, but got '" + next() + "'");
 558     if (Dest)
 559       Dest->insert(Dest->end(), V.begin(), V.end());
 560     return;
 561   }
 562
 563   Script->SectionCommands.insert(Script->SectionCommands.end(), V.begin(),
 564                                  V.end());
 565 }
 566
 567 void ScriptParser::readTarget() {
 568   // TARGET(foo) is an alias for "--format foo". Unlike GNU linkers,
 569   // we accept only a limited set of BFD names (i.e. "elf" or "binary")
 570   // for --format. We recognize only /^elf/ and "binary" in the linker
 571   // script as well.
 572   expect("(");
 573   StringRef Tok = next();
 574   expect(")");
 575
 576   if (Tok.startswith("elf"))
 577     Config->FormatBinary = false;
 578   else if (Tok == "binary")
 579     Config->FormatBinary = true;
 580   else
 581     setError("unknown target: " + Tok);
 582 }
 583
 584 static int precedence(StringRef Op) {
 585   return StringSwitch<int>(Op)
 586       .Cases("*", "/", "%", 8)
 587       .Cases("+", "-", 7)
 588       .Cases("<<", ">>", 6)
 589       .Cases("<", "<=", ">", ">=", "==", "!=", 5)
 590       .Case("&", 4)
 591       .Case("|", 3)
 592       .Case("&&", 2)
 593       .Case("||", 1)
 594       .Default(-1);
 595 }
 596
 597 StringMatcher ScriptParser::readFilePatterns() {
 598   std::vector<StringRef> V;
 599   while (!errorCount() && !consume(")"))
 600     V.push_back(next());
 601   return StringMatcher(V);
 602 }
 603
 604 SortSectionPolicy ScriptParser::readSortKind() {
 605   if (consume("SORT") || consume("SORT_BY_NAME"))
 606     return SortSectionPolicy::Name;
 607   if (consume("SORT_BY_ALIGNMENT"))
 608     return SortSectionPolicy::Alignment;
 609   if (consume("SORT_BY_INIT_PRIORITY"))
 610     return SortSectionPolicy::Priority;
 611   if (consume("SORT_NONE"))
 612     return SortSectionPolicy::None;
 613   return SortSectionPolicy::Default;
 614 }
 615
 616 // Reads SECTIONS command contents in the following form:
 617 //
 618 // <contents> ::= <elem>*
 619 // <elem>     ::= <exclude>? <glob-pattern>
 620 // <exclude>  ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
 621 //
 622 // For example,
 623 //
 624 // *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
 625 //
 626 // is parsed as ".foo", ".bar" with "a.o", and ".baz" with "b.o".
 627 // The semantics of that is section .foo in any file, section .bar in
 628 // any file but a.o, and section .baz in any file but b.o.
 629 std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
 630   std::vector<SectionPattern> Ret;
 631   while (!errorCount() && peek() != ")") {
 632     StringMatcher ExcludeFilePat;
 633     if (consume("EXCLUDE_FILE")) {
 634       expect("(");
 635       ExcludeFilePat = readFilePatterns();
 636     }
 637
 638     std::vector<StringRef> V;
 639     while (!errorCount() && peek() != ")" && peek() != "EXCLUDE_FILE")
 640       V.push_back(next());
 641
 642     if (!V.empty())
 643       Ret.push_back({std::move(ExcludeFilePat), StringMatcher(V)});
 644     else
 645       setError("section pattern is expected");
 646   }
 647   return Ret;
 648 }
 649
 650 // Reads contents of "SECTIONS" directive. That directive contains a
 651 // list of glob patterns for input sections. The grammar is as follows.
 652 //
 653 // <patterns> ::= <section-list>
 654 //              | <sort> "(" <section-list> ")"
 655 //              | <sort> "(" <sort> "(" <section-list> ")" ")"
 656 //
 657 // <sort>     ::= "SORT" | "SORT_BY_NAME" | "SORT_BY_ALIGNMENT"
 658 //              | "SORT_BY_INIT_PRIORITY" | "SORT_NONE"
 659 //
 660 // <section-list> is parsed by readInputSectionsList().
 661 InputSectionDescription *
 662 ScriptParser::readInputSectionRules(StringRef FilePattern) {
 663   auto *Cmd = make<InputSectionDescription>(FilePattern);
 664   expect("(");
 665
 666   while (!errorCount() && !consume(")")) {
 667     SortSectionPolicy Outer = readSortKind();
 668     SortSectionPolicy Inner = SortSectionPolicy::Default;
 669     std::vector<SectionPattern> V;
 670     if (Outer != SortSectionPolicy::Default) {
 671       expect("(");
 672       Inner = readSortKind();
 673       if (Inner != SortSectionPolicy::Default) {
 674         expect("(");
 675         V = readInputSectionsList();
 676         expect(")");
 677       } else {
 678         V = readInputSectionsList();
 679       }
 680       expect(")");
 681     } else {
 682       V = readInputSectionsList();
 683     }
 684
 685     for (SectionPattern &Pat : V) {
 686       Pat.SortInner = Inner;
 687       Pat.SortOuter = Outer;
 688     }
 689
 690     std::move(V.begin(), V.end(), std::back_inserter(Cmd->SectionPatterns));
 691   }
 692   return Cmd;
 693 }
 694
 695 InputSectionDescription *
 696 ScriptParser::readInputSectionDescription(StringRef Tok) {
 697   // Input section wildcard can be surrounded by KEEP.
 698   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
 699   if (Tok == "KEEP") {
 700     expect("(");
 701     StringRef FilePattern = next();
 702     InputSectionDescription *Cmd = readInputSectionRules(FilePattern);
 703     expect(")");
 704     Script->KeptSections.push_back(Cmd);
 705     return Cmd;
 706   }
 707   return readInputSectionRules(Tok);
 708 }
 709
 710 void ScriptParser::readSort() {
 711   expect("(");
 712   expect("CONSTRUCTORS");
 713   expect(")");
 714 }
 715
 716 Expr ScriptParser::readAssert() {
 717   expect("(");
 718   Expr E = readExpr();
 719   expect(",");
 720   StringRef Msg = unquote(next());
 721   expect(")");
 722
 723   return [=] {
 724     if (!E().getValue())
 725       error(Msg);
 726     return Script->getDot();
 727   };
 728 }
 729
 730 // Reads a FILL(expr) command. We handle the FILL command as an
 731 // alias for =fillexp section attribute, which is different from
 732 // what GNU linkers do.
 733 // https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
 734 std::array<uint8_t, 4> ScriptParser::readFill() {
 735   expect("(");
 736   std::array<uint8_t, 4> V = parseFill(next());
 737   expect(")");
 738   return V;
 739 }
 740
 741 // Tries to read the special directive for an output section definition which
 742 // can be one of following: "(NOLOAD)", "(COPY)", "(INFO)" or "(OVERLAY)".
 743 // Tok1 and Tok2 are next 2 tokens peeked. See comment for readSectionAddressType below.
 744 bool ScriptParser::readSectionDirective(OutputSection *Cmd, StringRef Tok1, StringRef Tok2) {
 745   if (Tok1 != "(")
 746     return false;
 747   if (Tok2 != "NOLOAD" && Tok2 != "COPY" && Tok2 != "INFO" && Tok2 != "OVERLAY")
 748     return false;
 749
 750   expect("(");
 751   if (consume("NOLOAD")) {
 752     Cmd->Noload = true;
 753   } else {
 754     skip(); // This is "COPY", "INFO" or "OVERLAY".
 755     Cmd->NonAlloc = true;
 756   }
 757   expect(")");
 758   return true;
 759 }
 760
 761 // Reads an expression and/or the special directive for an output
 762 // section definition. Directive is one of following: "(NOLOAD)",
 763 // "(COPY)", "(INFO)" or "(OVERLAY)".
 764 //
 765 // An output section name can be followed by an address expression
 766 // and/or directive. This grammar is not LL(1) because "(" can be
 767 // interpreted as either the beginning of some expression or beginning
 768 // of directive.
 769 //
 770 // https://sourceware.org/binutils/docs/ld/Output-Section-Address.html
 771 // https://sourceware.org/binutils/docs/ld/Output-Section-Type.html
 772 void ScriptParser::readSectionAddressType(OutputSection *Cmd) {
 773   if (readSectionDirective(Cmd, peek(), peek2()))
 774     return;
 775
 776   Cmd->AddrExpr = readExpr();
 777   if (peek() == "(" && !readSectionDirective(Cmd, "(", peek2()))
 778     setError("unknown section directive: " + peek2());
 779 }
 780
 781 static Expr checkAlignment(Expr E, std::string &Loc) {
 782   return [=] {
 783     uint64_t Alignment = std::max((uint64_t)1, E().getValue());
 784     if (!isPowerOf2_64(Alignment)) {
 785       error(Loc + ": alignment must be power of 2");
 786       return (uint64_t)1; // Return a dummy value.
 787     }
 788     return Alignment;
 789   };
 790 }
 791
 792 OutputSection *ScriptParser::readOverlaySectionDescription() {
 793   OutputSection *Cmd =
 794       Script->createOutputSection(next(), getCurrentLocation());
 795   Cmd->InOverlay = true;
 796   expect("{");
 797   while (!errorCount() && !consume("}"))
 798     Cmd->SectionCommands.push_back(readInputSectionRules(next()));
 799   Cmd->Phdrs = readOutputSectionPhdrs();
 800   return Cmd;
 801 }
 802
 803 OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec) {
 804   OutputSection *Cmd =
 805       Script->createOutputSection(OutSec, getCurrentLocation());
 806
 807   size_t SymbolsReferenced = Script->ReferencedSymbols.size();
 808
 809   if (peek() != ":")
 810     readSectionAddressType(Cmd);
 811   expect(":");
 812
 813   std::string Location = getCurrentLocation();
 814   if (consume("AT"))
 815     Cmd->LMAExpr = readParenExpr();
 816   if (consume("ALIGN"))
 817     Cmd->AlignExpr = checkAlignment(readParenExpr(), Location);
 818   if (consume("SUBALIGN"))
 819     Cmd->SubalignExpr = checkAlignment(readParenExpr(), Location);
 820
 821   // Parse constraints.
 822   if (consume("ONLY_IF_RO"))
 823     Cmd->Constraint = ConstraintKind::ReadOnly;
 824   if (consume("ONLY_IF_RW"))
 825     Cmd->Constraint = ConstraintKind::ReadWrite;
 826   expect("{");
 827
 828   while (!errorCount() && !consume("}")) {
 829     StringRef Tok = next();
 830     if (Tok == ";") {
 831       // Empty commands are allowed. Do nothing here.
 832     } else if (SymbolAssignment *Assign = readAssignment(Tok)) {
 833       Cmd->SectionCommands.push_back(Assign);
 834     } else if (ByteCommand *Data = readByteCommand(Tok)) {
 835       Cmd->SectionCommands.push_back(Data);
 836     } else if (Tok == "CONSTRUCTORS") {
 837       // CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
 838       // by name. This is for very old file formats such as ECOFF/XCOFF.
 839       // For ELF, we should ignore.
 840     } else if (Tok == "FILL") {
 841       Cmd->Filler = readFill();
 842     } else if (Tok == "SORT") {
 843       readSort();
 844     } else if (Tok == "INCLUDE") {
 845       readInclude();
 846     } else if (peek() == "(") {
 847       Cmd->SectionCommands.push_back(readInputSectionDescription(Tok));
 848     } else {
 849       // We have a file name and no input sections description. It is not a
 850       // commonly used syntax, but still acceptable. In that case, all sections
 851       // from the file will be included.
 852       auto *ISD = make<InputSectionDescription>(Tok);
 853       ISD->SectionPatterns.push_back({{}, StringMatcher({"*"})});
 854       Cmd->SectionCommands.push_back(ISD);
 855     }
 856   }
 857
 858   if (consume(">"))
 859     Cmd->MemoryRegionName = next();
 860
 861   if (consume("AT")) {
 862     expect(">");
 863     Cmd->LMARegionName = next();
 864   }
 865
 866   if (Cmd->LMAExpr && !Cmd->LMARegionName.empty())
 867     error("section can't have both LMA and a load region");
 868
 869   Cmd->Phdrs = readOutputSectionPhdrs();
 870
 871   if (consume("="))
 872     Cmd->Filler = parseFill(next());
 873   else if (peek().startswith("="))
 874     Cmd->Filler = parseFill(next().drop_front());
 875
 876   // Consume optional comma following output section command.
 877   consume(",");
 878
 879   if (Script->ReferencedSymbols.size() > SymbolsReferenced)
 880     Cmd->ExpressionsUseSymbols = true;
 881   return Cmd;
 882 }
 883
 884 // Parses a given string as a octal/decimal/hexadecimal number and
 885 // returns it as a big-endian number. Used for `=<fillexp>`.
 886 // https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
 887 //
 888 // When reading a hexstring, ld.bfd handles it as a blob of arbitrary
 889 // size, while ld.gold always handles it as a 32-bit big-endian number.
 890 // We are compatible with ld.gold because it's easier to implement.
 891 std::array<uint8_t, 4> ScriptParser::parseFill(StringRef Tok) {
 892   uint32_t V = 0;
 893   if (!to_integer(Tok, V))
 894     setError("invalid filler expression: " + Tok);
 895
 896   std::array<uint8_t, 4> Buf;
 897   write32be(Buf.data(), V);
 898   return Buf;
 899 }
 900
 901 SymbolAssignment *ScriptParser::readProvideHidden(bool Provide, bool Hidden) {
 902   expect("(");
 903   SymbolAssignment *Cmd = readSymbolAssignment(next());
 904   Cmd->Provide = Provide;
 905   Cmd->Hidden = Hidden;
 906   expect(")");
 907   return Cmd;
 908 }
 909
 910 SymbolAssignment *ScriptParser::readAssignment(StringRef Tok) {
 911   // Assert expression returns Dot, so this is equal to ".=."
 912   if (Tok == "ASSERT")
 913     return make<SymbolAssignment>(".", readAssert(), getCurrentLocation());
 914
 915   size_t OldPos = Pos;
 916   SymbolAssignment *Cmd = nullptr;
 917   if (peek() == "=" || peek() == "+=")
 918     Cmd = readSymbolAssignment(Tok);
 919   else if (Tok == "PROVIDE")
 920     Cmd = readProvideHidden(true, false);
 921   else if (Tok == "HIDDEN")
 922     Cmd = readProvideHidden(false, true);
 923   else if (Tok == "PROVIDE_HIDDEN")
 924     Cmd = readProvideHidden(true, true);
 925
 926   if (Cmd) {
 927     Cmd->CommandString =
 928         Tok.str() + " " +
 929         llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
 930     expect(";");
 931   }
 932   return Cmd;
 933 }
 934
 935 SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef Name) {
 936   StringRef Op = next();
 937   assert(Op == "=" || Op == "+=");
 938   Expr E = readExpr();
 939   if (Op == "+=") {
 940     std::string Loc = getCurrentLocation();
 941     E = [=] { return add(Script->getSymbolValue(Name, Loc), E()); };
 942   }
 943   return make<SymbolAssignment>(Name, E, getCurrentLocation());
 944 }
 945
 946 // This is an operator-precedence parser to parse a linker
 947 // script expression.
 948 Expr ScriptParser::readExpr() {
 949   // Our lexer is context-aware. Set the in-expression bit so that
 950   // they apply different tokenization rules.
 951   bool Orig = InExpr;
 952   InExpr = true;
 953   Expr E = readExpr1(readPrimary(), 0);
 954   InExpr = Orig;
 955   return E;
 956 }
 957
 958 Expr ScriptParser::combine(StringRef Op, Expr L, Expr R) {
 959   if (Op == "+")
 960     return [=] { return add(L(), R()); };
 961   if (Op == "-")
 962     return [=] { return sub(L(), R()); };
 963   if (Op == "*")
 964     return [=] { return L().getValue() * R().getValue(); };
 965   if (Op == "/") {
 966     std::string Loc = getCurrentLocation();
 967     return [=]() -> uint64_t {
 968       if (uint64_t RV = R().getValue())
 969         return L().getValue() / RV;
 970       error(Loc + ": division by zero");
 971       return 0;
 972     };
 973   }
 974   if (Op == "%") {
 975     std::string Loc = getCurrentLocation();
 976     return [=]() -> uint64_t {
 977       if (uint64_t RV = R().getValue())
 978         return L().getValue() % RV;
 979       error(Loc + ": modulo by zero");
 980       return 0;
 981     };
 982   }
 983   if (Op == "<<")
 984     return [=] { return L().getValue() << R().getValue(); };
 985   if (Op == ">>")
 986     return [=] { return L().getValue() >> R().getValue(); };
 987   if (Op == "<")
 988     return [=] { return L().getValue() < R().getValue(); };
 989   if (Op == ">")
 990     return [=] { return L().getValue() > R().getValue(); };
 991   if (Op == ">=")
 992     return [=] { return L().getValue() >= R().getValue(); };
 993   if (Op == "<=")
 994     return [=] { return L().getValue() <= R().getValue(); };
 995   if (Op == "==")
 996     return [=] { return L().getValue() == R().getValue(); };
 997   if (Op == "!=")
 998     return [=] { return L().getValue() != R().getValue(); };
 999   if (Op == "||")
1000     return [=] { return L().getValue() || R().getValue(); };
1001   if (Op == "&&")
1002     return [=] { return L().getValue() && R().getValue(); };
1003   if (Op == "&")
1004     return [=] { return bitAnd(L(), R()); };
1005   if (Op == "|")
1006     return [=] { return bitOr(L(), R()); };
1007   llvm_unreachable("invalid operator");
1008 }
1009
1010 // This is a part of the operator-precedence parser. This function
1011 // assumes that the remaining token stream starts with an operator.
1012 Expr ScriptParser::readExpr1(Expr Lhs, int MinPrec) {
1013   while (!atEOF() && !errorCount()) {
1014     // Read an operator and an expression.
1015     if (consume("?"))
1016       return readTernary(Lhs);
1017     StringRef Op1 = peek();
1018     if (precedence(Op1) < MinPrec)
1019       break;
1020     skip();
1021     Expr Rhs = readPrimary();
1022
1023     // Evaluate the remaining part of the expression first if the
1024     // next operator has greater precedence than the previous one.
1025     // For example, if we have read "+" and "3", and if the next
1026     // operator is "*", then we'll evaluate 3 * ... part first.
1027     while (!atEOF()) {
1028       StringRef Op2 = peek();
1029       if (precedence(Op2) <= precedence(Op1))
1030         break;
1031       Rhs = readExpr1(Rhs, precedence(Op2));
1032     }
1033
1034     Lhs = combine(Op1, Lhs, Rhs);
1035   }
1036   return Lhs;
1037 }
1038
1039 Expr ScriptParser::getPageSize() {
1040   std::string Location = getCurrentLocation();
1041   return [=]() -> uint64_t {
1042     if (Target)
1043       return Target->PageSize;
1044     error(Location + ": unable to calculate page size");
1045     return 4096; // Return a dummy value.
1046   };
1047 }
1048
1049 Expr ScriptParser::readConstant() {
1050   StringRef S = readParenLiteral();
1051   if (S == "COMMONPAGESIZE")
1052     return getPageSize();
1053   if (S == "MAXPAGESIZE")
1054     return [] { return Config->MaxPageSize; };
1055   setError("unknown constant: " + S);
1056   return [] { return 0; };
1057 }
1058
1059 // Parses Tok as an integer. It recognizes hexadecimal (prefixed with
1060 // "0x" or suffixed with "H") and decimal numbers. Decimal numbers may
1061 // have "K" (Ki) or "M" (Mi) suffixes.
1062 static Optional<uint64_t> parseInt(StringRef Tok) {
1063   // Hexadecimal
1064   uint64_t Val;
1065   if (Tok.startswith_lower("0x")) {
1066     if (!to_integer(Tok.substr(2), Val, 16))
1067       return None;
1068     return Val;
1069   }
1070   if (Tok.endswith_lower("H")) {
1071     if (!to_integer(Tok.drop_back(), Val, 16))
1072       return None;
1073     return Val;
1074   }
1075
1076   // Decimal
1077   if (Tok.endswith_lower("K")) {
1078     if (!to_integer(Tok.drop_back(), Val, 10))
1079       return None;
1080     return Val * 1024;
1081   }
1082   if (Tok.endswith_lower("M")) {
1083     if (!to_integer(Tok.drop_back(), Val, 10))
1084       return None;
1085     return Val * 1024 * 1024;
1086   }
1087   if (!to_integer(Tok, Val, 10))
1088     return None;
1089   return Val;
1090 }
1091
1092 ByteCommand *ScriptParser::readByteCommand(StringRef Tok) {
1093   int Size = StringSwitch<int>(Tok)
1094                  .Case("BYTE", 1)
1095                  .Case("SHORT", 2)
1096                  .Case("LONG", 4)
1097                  .Case("QUAD", 8)
1098                  .Default(-1);
1099   if (Size == -1)
1100     return nullptr;
1101
1102   size_t OldPos = Pos;
1103   Expr E = readParenExpr();
1104   std::string CommandString =
1105       Tok.str() + " " +
1106       llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
1107   return make<ByteCommand>(E, Size, CommandString);
1108 }
1109
1110 StringRef ScriptParser::readParenLiteral() {
1111   expect("(");
1112   bool Orig = InExpr;
1113   InExpr = false;
1114   StringRef Tok = next();
1115   InExpr = Orig;
1116   expect(")");
1117   return Tok;
1118 }
1119
1120 static void checkIfExists(OutputSection *Cmd, StringRef Location) {
1121   if (Cmd->Location.empty() && Script->ErrorOnMissingSection)
1122     error(Location + ": undefined section " + Cmd->Name);
1123 }
1124
1125 Expr ScriptParser::readPrimary() {
1126   if (peek() == "(")
1127     return readParenExpr();
1128
1129   if (consume("~")) {
1130     Expr E = readPrimary();
1131     return [=] { return ~E().getValue(); };
1132   }
1133   if (consume("!")) {
1134     Expr E = readPrimary();
1135     return [=] { return !E().getValue(); };
1136   }
1137   if (consume("-")) {
1138     Expr E = readPrimary();
1139     return [=] { return -E().getValue(); };
1140   }
1141
1142   StringRef Tok = next();
1143   std::string Location = getCurrentLocation();
1144
1145   // Built-in functions are parsed here.
1146   // https://sourceware.org/binutils/docs/ld/Builtin-Functions.html.
1147   if (Tok == "ABSOLUTE") {
1148     Expr Inner = readParenExpr();
1149     return [=] {
1150       ExprValue I = Inner();
1151       I.ForceAbsolute = true;
1152       return I;
1153     };
1154   }
1155   if (Tok == "ADDR") {
1156     StringRef Name = readParenLiteral();
1157     OutputSection *Sec = Script->getOrCreateOutputSection(Name);
1158     return [=]() -> ExprValue {
1159       checkIfExists(Sec, Location);
1160       return {Sec, false, 0, Location};
1161     };
1162   }
1163   if (Tok == "ALIGN") {
1164     expect("(");
1165     Expr E = readExpr();
1166     if (consume(")")) {
1167       E = checkAlignment(E, Location);
1168       return [=] { return alignTo(Script->getDot(), E().getValue()); };
1169     }
1170     expect(",");
1171     Expr E2 = checkAlignment(readExpr(), Location);
1172     expect(")");
1173     return [=] {
1174       ExprValue V = E();
1175       V.Alignment = E2().getValue();
1176       return V;
1177     };
1178   }
1179   if (Tok == "ALIGNOF") {
1180     StringRef Name = readParenLiteral();
1181     OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1182     return [=] {
1183       checkIfExists(Cmd, Location);
1184       return Cmd->Alignment;
1185     };
1186   }
1187   if (Tok == "ASSERT")
1188     return readAssert();
1189   if (Tok == "CONSTANT")
1190     return readConstant();
1191   if (Tok == "DATA_SEGMENT_ALIGN") {
1192     expect("(");
1193     Expr E = readExpr();
1194     expect(",");
1195     readExpr();
1196     expect(")");
1197     return [=] {
1198       return alignTo(Script->getDot(), std::max((uint64_t)1, E().getValue()));
1199     };
1200   }
1201   if (Tok == "DATA_SEGMENT_END") {
1202     expect("(");
1203     expect(".");
1204     expect(")");
1205     return [] { return Script->getDot(); };
1206   }
1207   if (Tok == "DATA_SEGMENT_RELRO_END") {
1208     // GNU linkers implements more complicated logic to handle
1209     // DATA_SEGMENT_RELRO_END. We instead ignore the arguments and
1210     // just align to the next page boundary for simplicity.
1211     expect("(");
1212     readExpr();
1213     expect(",");
1214     readExpr();
1215     expect(")");
1216     Expr E = getPageSize();
1217     return [=] { return alignTo(Script->getDot(), E().getValue()); };
1218   }
1219   if (Tok == "DEFINED") {
1220     StringRef Name = readParenLiteral();
1221     return [=] { return Symtab->find(Name) ? 1 : 0; };
1222   }
1223   if (Tok == "LENGTH") {
1224     StringRef Name = readParenLiteral();
1225     if (Script->MemoryRegions.count(Name) == 0) {
1226       setError("memory region not defined: " + Name);
1227       return [] { return 0; };
1228     }
1229     return [=] { return Script->MemoryRegions[Name]->Length; };
1230   }
1231   if (Tok == "LOADADDR") {
1232     StringRef Name = readParenLiteral();
1233     OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1234     return [=] {
1235       checkIfExists(Cmd, Location);
1236       return Cmd->getLMA();
1237     };
1238   }
1239   if (Tok == "MAX" || Tok == "MIN") {
1240     expect("(");
1241     Expr A = readExpr();
1242     expect(",");
1243     Expr B = readExpr();
1244     expect(")");
1245     if (Tok == "MIN")
1246       return [=] { return std::min(A().getValue(), B().getValue()); };
1247     return [=] { return std::max(A().getValue(), B().getValue()); };
1248   }
1249   if (Tok == "ORIGIN") {
1250     StringRef Name = readParenLiteral();
1251     if (Script->MemoryRegions.count(Name) == 0) {
1252       setError("memory region not defined: " + Name);
1253       return [] { return 0; };
1254     }
1255     return [=] { return Script->MemoryRegions[Name]->Origin; };
1256   }
1257   if (Tok == "SEGMENT_START") {
1258     expect("(");
1259     skip();
1260     expect(",");
1261     Expr E = readExpr();
1262     expect(")");
1263     return [=] { return E(); };
1264   }
1265   if (Tok == "SIZEOF") {
1266     StringRef Name = readParenLiteral();
1267     OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1268     // Linker script does not create an output section if its content is empty.
1269     // We want to allow SIZEOF(.foo) where .foo is a section which happened to
1270     // be empty.
1271     return [=] { return Cmd->Size; };
1272   }
1273   if (Tok == "SIZEOF_HEADERS")
1274     return [=] { return elf::getHeaderSize(); };
1275
1276   // Tok is the dot.
1277   if (Tok == ".")
1278     return [=] { return Script->getSymbolValue(Tok, Location); };
1279
1280   // Tok is a literal number.
1281   if (Optional<uint64_t> Val = parseInt(Tok))
1282     return [=] { return *Val; };
1283
1284   // Tok is a symbol name.
1285   if (!isValidCIdentifier(Tok))
1286     setError("malformed number: " + Tok);
1287   Script->ReferencedSymbols.push_back(Tok);
1288   return [=] { return Script->getSymbolValue(Tok, Location); };
1289 }
1290
1291 Expr ScriptParser::readTernary(Expr Cond) {
1292   Expr L = readExpr();
1293   expect(":");
1294   Expr R = readExpr();
1295   return [=] { return Cond().getValue() ? L() : R(); };
1296 }
1297
1298 Expr ScriptParser::readParenExpr() {
1299   expect("(");
1300   Expr E = readExpr();
1301   expect(")");
1302   return E;
1303 }
1304
1305 std::vector<StringRef> ScriptParser::readOutputSectionPhdrs() {
1306   std::vector<StringRef> Phdrs;
1307   while (!errorCount() && peek().startswith(":")) {
1308     StringRef Tok = next();
1309     Phdrs.push_back((Tok.size() == 1) ? next() : Tok.substr(1));
1310   }
1311   return Phdrs;
1312 }
1313
1314 // Read a program header type name. The next token must be a
1315 // name of a program header type or a constant (e.g. "0x3").
1316 unsigned ScriptParser::readPhdrType() {
1317   StringRef Tok = next();
1318   if (Optional<uint64_t> Val = parseInt(Tok))
1319     return *Val;
1320
1321   unsigned Ret = StringSwitch<unsigned>(Tok)
1322                      .Case("PT_NULL", PT_NULL)
1323                      .Case("PT_LOAD", PT_LOAD)
1324                      .Case("PT_DYNAMIC", PT_DYNAMIC)
1325                      .Case("PT_INTERP", PT_INTERP)
1326                      .Case("PT_NOTE", PT_NOTE)
1327                      .Case("PT_SHLIB", PT_SHLIB)
1328                      .Case("PT_PHDR", PT_PHDR)
1329                      .Case("PT_TLS", PT_TLS)
1330                      .Case("PT_GNU_EH_FRAME", PT_GNU_EH_FRAME)
1331                      .Case("PT_GNU_STACK", PT_GNU_STACK)
1332                      .Case("PT_GNU_RELRO", PT_GNU_RELRO)
1333                      .Case("PT_OPENBSD_RANDOMIZE", PT_OPENBSD_RANDOMIZE)
1334                      .Case("PT_OPENBSD_WXNEEDED", PT_OPENBSD_WXNEEDED)
1335                      .Case("PT_OPENBSD_BOOTDATA", PT_OPENBSD_BOOTDATA)
1336                      .Default(-1);
1337
1338   if (Ret == (unsigned)-1) {
1339     setError("invalid program header type: " + Tok);
1340     return PT_NULL;
1341   }
1342   return Ret;
1343 }
1344
1345 // Reads an anonymous version declaration.
1346 void ScriptParser::readAnonymousDeclaration() {
1347   std::vector<SymbolVersion> Locals;
1348   std::vector<SymbolVersion> Globals;
1349   std::tie(Locals, Globals) = readSymbols();
1350
1351   for (SymbolVersion V : Locals) {
1352     if (V.Name == "*")
1353       Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1354     else
1355       Config->VersionScriptLocals.push_back(V);
1356   }
1357
1358   for (SymbolVersion V : Globals)
1359     Config->VersionScriptGlobals.push_back(V);
1360
1361   expect(";");
1362 }
1363
1364 // Reads a non-anonymous version definition,
1365 // e.g. "VerStr { global: foo; bar; local: *; };".
1366 void ScriptParser::readVersionDeclaration(StringRef VerStr) {
1367   // Read a symbol list.
1368   std::vector<SymbolVersion> Locals;
1369   std::vector<SymbolVersion> Globals;
1370   std::tie(Locals, Globals) = readSymbols();
1371
1372   for (SymbolVersion V : Locals) {
1373     if (V.Name == "*")
1374       Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1375     else
1376       Config->VersionScriptLocals.push_back(V);
1377   }
1378
1379   // Create a new version definition and add that to the global symbols.
1380   VersionDefinition Ver;
1381   Ver.Name = VerStr;
1382   Ver.Globals = Globals;
1383
1384   // User-defined version number starts from 2 because 0 and 1 are
1385   // reserved for VER_NDX_LOCAL and VER_NDX_GLOBAL, respectively.
1386   Ver.Id = Config->VersionDefinitions.size() + 2;
1387   Config->VersionDefinitions.push_back(Ver);
1388
1389   // Each version may have a parent version. For example, "Ver2"
1390   // defined as "Ver2 { global: foo; local: *; } Ver1;" has "Ver1"
1391   // as a parent. This version hierarchy is, probably against your
1392   // instinct, purely for hint; the runtime doesn't care about it
1393   // at all. In LLD, we simply ignore it.
1394   if (peek() != ";")
1395     skip();
1396   expect(";");
1397 }
1398
1399 static bool hasWildcard(StringRef S) {
1400   return S.find_first_of("?*[") != StringRef::npos;
1401 }
1402
1403 // Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
1404 std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
1405 ScriptParser::readSymbols() {
1406   std::vector<SymbolVersion> Locals;
1407   std::vector<SymbolVersion> Globals;
1408   std::vector<SymbolVersion> *V = &Globals;
1409
1410   while (!errorCount()) {
1411     if (consume("}"))
1412       break;
1413     if (consumeLabel("local")) {
1414       V = &Locals;
1415       continue;
1416     }
1417     if (consumeLabel("global")) {
1418       V = &Globals;
1419       continue;
1420     }
1421
1422     if (consume("extern")) {
1423       std::vector<SymbolVersion> Ext = readVersionExtern();
1424       V->insert(V->end(), Ext.begin(), Ext.end());
1425     } else {
1426       StringRef Tok = next();
1427       V->push_back({unquote(Tok), false, hasWildcard(Tok)});
1428     }
1429     expect(";");
1430   }
1431   return {Locals, Globals};
1432 }
1433
1434 // Reads an "extern C++" directive, e.g.,
1435 // "extern "C++" { ns::*; "f(int, double)"; };"
1436 //
1437 // The last semicolon is optional. E.g. this is OK:
1438 // "extern "C++" { ns::*; "f(int, double)" };"
1439 std::vector<SymbolVersion> ScriptParser::readVersionExtern() {
1440   StringRef Tok = next();
1441   bool IsCXX = Tok == "\"C++\"";
1442   if (!IsCXX && Tok != "\"C\"")
1443     setError("Unknown language");
1444   expect("{");
1445
1446   std::vector<SymbolVersion> Ret;
1447   while (!errorCount() && peek() != "}") {
1448     StringRef Tok = next();
1449     bool HasWildcard = !Tok.startswith("\"") && hasWildcard(Tok);
1450     Ret.push_back({unquote(Tok), IsCXX, HasWildcard});
1451     if (consume("}"))
1452       return Ret;
1453     expect(";");
1454   }
1455
1456   expect("}");
1457   return Ret;
1458 }
1459
1460 uint64_t ScriptParser::readMemoryAssignment(StringRef S1, StringRef S2,
1461                                             StringRef S3) {
1462   if (!consume(S1) && !consume(S2) && !consume(S3)) {
1463     setError("expected one of: " + S1 + ", " + S2 + ", or " + S3);
1464     return 0;
1465   }
1466   expect("=");
1467   return readExpr()().getValue();
1468 }
1469
1470 // Parse the MEMORY command as specified in:
1471 // https://sourceware.org/binutils/docs/ld/MEMORY.html
1472 //
1473 // MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
1474 void ScriptParser::readMemory() {
1475   expect("{");
1476   while (!errorCount() && !consume("}")) {
1477     StringRef Tok = next();
1478     if (Tok == "INCLUDE") {
1479       readInclude();
1480       continue;
1481     }
1482
1483     uint32_t Flags = 0;
1484     uint32_t NegFlags = 0;
1485     if (consume("(")) {
1486       std::tie(Flags, NegFlags) = readMemoryAttributes();
1487       expect(")");
1488     }
1489     expect(":");
1490
1491     uint64_t Origin = readMemoryAssignment("ORIGIN", "org", "o");
1492     expect(",");
1493     uint64_t Length = readMemoryAssignment("LENGTH", "len", "l");
1494
1495     // Add the memory region to the region map.
1496     MemoryRegion *MR = make<MemoryRegion>(Tok, Origin, Length, Flags, NegFlags);
1497     if (!Script->MemoryRegions.insert({Tok, MR}).second)
1498       setError("region '" + Tok + "' already defined");
1499   }
1500 }
1501
1502 // This function parses the attributes used to match against section
1503 // flags when placing output sections in a memory region. These flags
1504 // are only used when an explicit memory region name is not used.
1505 std::pair<uint32_t, uint32_t> ScriptParser::readMemoryAttributes() {
1506   uint32_t Flags = 0;
1507   uint32_t NegFlags = 0;
1508   bool Invert = false;
1509
1510   for (char C : next().lower()) {
1511     uint32_t Flag = 0;
1512     if (C == '!')
1513       Invert = !Invert;
1514     else if (C == 'w')
1515       Flag = SHF_WRITE;
1516     else if (C == 'x')
1517       Flag = SHF_EXECINSTR;
1518     else if (C == 'a')
1519       Flag = SHF_ALLOC;
1520     else if (C != 'r')
1521       setError("invalid memory region attribute");
1522
1523     if (Invert)
1524       NegFlags |= Flag;
1525     else
1526       Flags |= Flag;
1527   }
1528   return {Flags, NegFlags};
1529 }
1530
1531 void elf::readLinkerScript(MemoryBufferRef MB) {
1532   ScriptParser(MB).readLinkerScript();
1533 }
1534
1535 void elf::readVersionScript(MemoryBufferRef MB) {
1536   ScriptParser(MB).readVersionScript();
1537 }
1538
1539 void elf::readDynamicList(MemoryBufferRef MB) {
1540   ScriptParser(MB).readDynamicList();
1541 }
1542
1543 void elf::readDefsym(StringRef Name, MemoryBufferRef MB) {
1544   ScriptParser(MB).readDefsym(Name);
1545 }