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

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