contrib/llvm-project/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
  41 namespace lld {
  42 namespace elf {
  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       errorOrWarn(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     cmd->type = SHT_NOBITS;
 741   } else {
 742     skip(); // This is "COPY", "INFO" or "OVERLAY".
 743     cmd->nonAlloc = true;
 744   }
 745   expect(")");
 746   return true;
 747 }
 748
 749 // Reads an expression and/or the special directive for an output
 750 // section definition. Directive is one of following: "(NOLOAD)",
 751 // "(COPY)", "(INFO)" or "(OVERLAY)".
 752 //
 753 // An output section name can be followed by an address expression
 754 // and/or directive. This grammar is not LL(1) because "(" can be
 755 // interpreted as either the beginning of some expression or beginning
 756 // of directive.
 757 //
 758 // https://sourceware.org/binutils/docs/ld/Output-Section-Address.html
 759 // https://sourceware.org/binutils/docs/ld/Output-Section-Type.html
 760 void ScriptParser::readSectionAddressType(OutputSection *cmd) {
 761   if (readSectionDirective(cmd, peek(), peek2()))
 762     return;
 763
 764   cmd->addrExpr = readExpr();
 765   if (peek() == "(" && !readSectionDirective(cmd, "(", peek2()))
 766     setError("unknown section directive: " + peek2());
 767 }
 768
 769 static Expr checkAlignment(Expr e, std::string &loc) {
 770   return [=] {
 771     uint64_t alignment = std::max((uint64_t)1, e().getValue());
 772     if (!isPowerOf2_64(alignment)) {
 773       error(loc + ": alignment must be power of 2");
 774       return (uint64_t)1; // Return a dummy value.
 775     }
 776     return alignment;
 777   };
 778 }
 779
 780 OutputSection *ScriptParser::readOverlaySectionDescription() {
 781   OutputSection *cmd =
 782       script->createOutputSection(next(), getCurrentLocation());
 783   cmd->inOverlay = true;
 784   expect("{");
 785   while (!errorCount() && !consume("}"))
 786     cmd->sectionCommands.push_back(readInputSectionRules(next()));
 787   cmd->phdrs = readOutputSectionPhdrs();
 788   return cmd;
 789 }
 790
 791 OutputSection *ScriptParser::readOutputSectionDescription(StringRef outSec) {
 792   OutputSection *cmd =
 793       script->createOutputSection(outSec, getCurrentLocation());
 794
 795   size_t symbolsReferenced = script->referencedSymbols.size();
 796
 797   if (peek() != ":")
 798     readSectionAddressType(cmd);
 799   expect(":");
 800
 801   std::string location = getCurrentLocation();
 802   if (consume("AT"))
 803     cmd->lmaExpr = readParenExpr();
 804   if (consume("ALIGN"))
 805     cmd->alignExpr = checkAlignment(readParenExpr(), location);
 806   if (consume("SUBALIGN"))
 807     cmd->subalignExpr = checkAlignment(readParenExpr(), location);
 808
 809   // Parse constraints.
 810   if (consume("ONLY_IF_RO"))
 811     cmd->constraint = ConstraintKind::ReadOnly;
 812   if (consume("ONLY_IF_RW"))
 813     cmd->constraint = ConstraintKind::ReadWrite;
 814   expect("{");
 815
 816   while (!errorCount() && !consume("}")) {
 817     StringRef tok = next();
 818     if (tok == ";") {
 819       // Empty commands are allowed. Do nothing here.
 820     } else if (SymbolAssignment *assign = readAssignment(tok)) {
 821       cmd->sectionCommands.push_back(assign);
 822     } else if (ByteCommand *data = readByteCommand(tok)) {
 823       cmd->sectionCommands.push_back(data);
 824     } else if (tok == "CONSTRUCTORS") {
 825       // CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
 826       // by name. This is for very old file formats such as ECOFF/XCOFF.
 827       // For ELF, we should ignore.
 828     } else if (tok == "FILL") {
 829       // We handle the FILL command as an alias for =fillexp section attribute,
 830       // which is different from what GNU linkers do.
 831       // https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
 832       expect("(");
 833       cmd->filler = readFill();
 834       expect(")");
 835     } else if (tok == "SORT") {
 836       readSort();
 837     } else if (tok == "INCLUDE") {
 838       readInclude();
 839     } else if (peek() == "(") {
 840       cmd->sectionCommands.push_back(readInputSectionDescription(tok));
 841     } else {
 842       // We have a file name and no input sections description. It is not a
 843       // commonly used syntax, but still acceptable. In that case, all sections
 844       // from the file will be included.
 845       auto *isd = make<InputSectionDescription>(tok);
 846       isd->sectionPatterns.push_back({{}, StringMatcher({"*"})});
 847       cmd->sectionCommands.push_back(isd);
 848     }
 849   }
 850
 851   if (consume(">"))
 852     cmd->memoryRegionName = next();
 853
 854   if (consume("AT")) {
 855     expect(">");
 856     cmd->lmaRegionName = next();
 857   }
 858
 859   if (cmd->lmaExpr && !cmd->lmaRegionName.empty())
 860     error("section can't have both LMA and a load region");
 861
 862   cmd->phdrs = readOutputSectionPhdrs();
 863
 864   if (peek() == "=" || peek().startswith("=")) {
 865     inExpr = true;
 866     consume("=");
 867     cmd->filler = readFill();
 868     inExpr = false;
 869   }
 870
 871   // Consume optional comma following output section command.
 872   consume(",");
 873
 874   if (script->referencedSymbols.size() > symbolsReferenced)
 875     cmd->expressionsUseSymbols = true;
 876   return cmd;
 877 }
 878
 879 // Reads a `=<fillexp>` expression and returns its value as a big-endian number.
 880 // https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
 881 // We do not support using symbols in such expressions.
 882 //
 883 // When reading a hexstring, ld.bfd handles it as a blob of arbitrary
 884 // size, while ld.gold always handles it as a 32-bit big-endian number.
 885 // We are compatible with ld.gold because it's easier to implement.
 886 std::array<uint8_t, 4> ScriptParser::readFill() {
 887   uint64_t value = readExpr()().val;
 888   if (value > UINT32_MAX)
 889     setError("filler expression result does not fit 32-bit: 0x" +
 890              Twine::utohexstr(value));
 891
 892   std::array<uint8_t, 4> buf;
 893   write32be(buf.data(), (uint32_t)value);
 894   return buf;
 895 }
 896
 897 SymbolAssignment *ScriptParser::readProvideHidden(bool provide, bool hidden) {
 898   expect("(");
 899   SymbolAssignment *cmd = readSymbolAssignment(next());
 900   cmd->provide = provide;
 901   cmd->hidden = hidden;
 902   expect(")");
 903   return cmd;
 904 }
 905
 906 SymbolAssignment *ScriptParser::readAssignment(StringRef tok) {
 907   // Assert expression returns Dot, so this is equal to ".=."
 908   if (tok == "ASSERT")
 909     return make<SymbolAssignment>(".", readAssert(), getCurrentLocation());
 910
 911   size_t oldPos = pos;
 912   SymbolAssignment *cmd = nullptr;
 913   if (peek() == "=" || peek() == "+=")
 914     cmd = readSymbolAssignment(tok);
 915   else if (tok == "PROVIDE")
 916     cmd = readProvideHidden(true, false);
 917   else if (tok == "HIDDEN")
 918     cmd = readProvideHidden(false, true);
 919   else if (tok == "PROVIDE_HIDDEN")
 920     cmd = readProvideHidden(true, true);
 921
 922   if (cmd) {
 923     cmd->commandString =
 924         tok.str() + " " +
 925         llvm::join(tokens.begin() + oldPos, tokens.begin() + pos, " ");
 926     expect(";");
 927   }
 928   return cmd;
 929 }
 930
 931 SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef name) {
 932   StringRef op = next();
 933   assert(op == "=" || op == "+=");
 934   Expr e = readExpr();
 935   if (op == "+=") {
 936     std::string loc = getCurrentLocation();
 937     e = [=] { return add(script->getSymbolValue(name, loc), e()); };
 938   }
 939   return make<SymbolAssignment>(name, e, getCurrentLocation());
 940 }
 941
 942 // This is an operator-precedence parser to parse a linker
 943 // script expression.
 944 Expr ScriptParser::readExpr() {
 945   // Our lexer is context-aware. Set the in-expression bit so that
 946   // they apply different tokenization rules.
 947   bool orig = inExpr;
 948   inExpr = true;
 949   Expr e = readExpr1(readPrimary(), 0);
 950   inExpr = orig;
 951   return e;
 952 }
 953
 954 Expr ScriptParser::combine(StringRef op, Expr l, Expr r) {
 955   if (op == "+")
 956     return [=] { return add(l(), r()); };
 957   if (op == "-")
 958     return [=] { return sub(l(), r()); };
 959   if (op == "*")
 960     return [=] { return l().getValue() * r().getValue(); };
 961   if (op == "/") {
 962     std::string loc = getCurrentLocation();
 963     return [=]() -> uint64_t {
 964       if (uint64_t rv = r().getValue())
 965         return l().getValue() / rv;
 966       error(loc + ": division by zero");
 967       return 0;
 968     };
 969   }
 970   if (op == "%") {
 971     std::string loc = getCurrentLocation();
 972     return [=]() -> uint64_t {
 973       if (uint64_t rv = r().getValue())
 974         return l().getValue() % rv;
 975       error(loc + ": modulo by zero");
 976       return 0;
 977     };
 978   }
 979   if (op == "<<")
 980     return [=] { return l().getValue() << r().getValue(); };
 981   if (op == ">>")
 982     return [=] { return l().getValue() >> r().getValue(); };
 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 bitAnd(l(), r()); };
1001   if (op == "|")
1002     return [=] { return bitOr(l(), r()); };
1003   llvm_unreachable("invalid operator");
1004 }
1005
1006 // This is a part of the operator-precedence parser. This function
1007 // assumes that the remaining token stream starts with an operator.
1008 Expr ScriptParser::readExpr1(Expr lhs, int minPrec) {
1009   while (!atEOF() && !errorCount()) {
1010     // Read an operator and an expression.
1011     if (consume("?"))
1012       return readTernary(lhs);
1013     StringRef op1 = peek();
1014     if (precedence(op1) < minPrec)
1015       break;
1016     skip();
1017     Expr rhs = readPrimary();
1018
1019     // Evaluate the remaining part of the expression first if the
1020     // next operator has greater precedence than the previous one.
1021     // For example, if we have read "+" and "3", and if the next
1022     // operator is "*", then we'll evaluate 3 * ... part first.
1023     while (!atEOF()) {
1024       StringRef op2 = peek();
1025       if (precedence(op2) <= precedence(op1))
1026         break;
1027       rhs = readExpr1(rhs, precedence(op2));
1028     }
1029
1030     lhs = combine(op1, lhs, rhs);
1031   }
1032   return lhs;
1033 }
1034
1035 Expr ScriptParser::getPageSize() {
1036   std::string location = getCurrentLocation();
1037   return [=]() -> uint64_t {
1038     if (target)
1039       return config->commonPageSize;
1040     error(location + ": unable to calculate page size");
1041     return 4096; // Return a dummy value.
1042   };
1043 }
1044
1045 Expr ScriptParser::readConstant() {
1046   StringRef s = readParenLiteral();
1047   if (s == "COMMONPAGESIZE")
1048     return getPageSize();
1049   if (s == "MAXPAGESIZE")
1050     return [] { return config->maxPageSize; };
1051   setError("unknown constant: " + s);
1052   return [] { return 0; };
1053 }
1054
1055 // Parses Tok as an integer. It recognizes hexadecimal (prefixed with
1056 // "0x" or suffixed with "H") and decimal numbers. Decimal numbers may
1057 // have "K" (Ki) or "M" (Mi) suffixes.
1058 static Optional<uint64_t> parseInt(StringRef tok) {
1059   // Hexadecimal
1060   uint64_t val;
1061   if (tok.startswith_lower("0x")) {
1062     if (!to_integer(tok.substr(2), val, 16))
1063       return None;
1064     return val;
1065   }
1066   if (tok.endswith_lower("H")) {
1067     if (!to_integer(tok.drop_back(), val, 16))
1068       return None;
1069     return val;
1070   }
1071
1072   // Decimal
1073   if (tok.endswith_lower("K")) {
1074     if (!to_integer(tok.drop_back(), val, 10))
1075       return None;
1076     return val * 1024;
1077   }
1078   if (tok.endswith_lower("M")) {
1079     if (!to_integer(tok.drop_back(), val, 10))
1080       return None;
1081     return val * 1024 * 1024;
1082   }
1083   if (!to_integer(tok, val, 10))
1084     return None;
1085   return val;
1086 }
1087
1088 ByteCommand *ScriptParser::readByteCommand(StringRef tok) {
1089   int size = StringSwitch<int>(tok)
1090                  .Case("BYTE", 1)
1091                  .Case("SHORT", 2)
1092                  .Case("LONG", 4)
1093                  .Case("QUAD", 8)
1094                  .Default(-1);
1095   if (size == -1)
1096     return nullptr;
1097
1098   size_t oldPos = pos;
1099   Expr e = readParenExpr();
1100   std::string commandString =
1101       tok.str() + " " +
1102       llvm::join(tokens.begin() + oldPos, tokens.begin() + pos, " ");
1103   return make<ByteCommand>(e, size, commandString);
1104 }
1105
1106 StringRef ScriptParser::readParenLiteral() {
1107   expect("(");
1108   bool orig = inExpr;
1109   inExpr = false;
1110   StringRef tok = next();
1111   inExpr = orig;
1112   expect(")");
1113   return tok;
1114 }
1115
1116 static void checkIfExists(OutputSection *cmd, StringRef location) {
1117   if (cmd->location.empty() && script->errorOnMissingSection)
1118     error(location + ": undefined section " + cmd->name);
1119 }
1120
1121 Expr ScriptParser::readPrimary() {
1122   if (peek() == "(")
1123     return readParenExpr();
1124
1125   if (consume("~")) {
1126     Expr e = readPrimary();
1127     return [=] { return ~e().getValue(); };
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
1138   StringRef tok = next();
1139   std::string location = getCurrentLocation();
1140
1141   // Built-in functions are parsed here.
1142   // https://sourceware.org/binutils/docs/ld/Builtin-Functions.html.
1143   if (tok == "ABSOLUTE") {
1144     Expr inner = readParenExpr();
1145     return [=] {
1146       ExprValue i = inner();
1147       i.forceAbsolute = true;
1148       return i;
1149     };
1150   }
1151   if (tok == "ADDR") {
1152     StringRef name = readParenLiteral();
1153     OutputSection *sec = script->getOrCreateOutputSection(name);
1154     sec->usedInExpression = true;
1155     return [=]() -> ExprValue {
1156       checkIfExists(sec, location);
1157       return {sec, false, 0, location};
1158     };
1159   }
1160   if (tok == "ALIGN") {
1161     expect("(");
1162     Expr e = readExpr();
1163     if (consume(")")) {
1164       e = checkAlignment(e, location);
1165       return [=] { return alignTo(script->getDot(), e().getValue()); };
1166     }
1167     expect(",");
1168     Expr e2 = checkAlignment(readExpr(), location);
1169     expect(")");
1170     return [=] {
1171       ExprValue v = e();
1172       v.alignment = e2().getValue();
1173       return v;
1174     };
1175   }
1176   if (tok == "ALIGNOF") {
1177     StringRef name = readParenLiteral();
1178     OutputSection *cmd = script->getOrCreateOutputSection(name);
1179     return [=] {
1180       checkIfExists(cmd, location);
1181       return cmd->alignment;
1182     };
1183   }
1184   if (tok == "ASSERT")
1185     return readAssert();
1186   if (tok == "CONSTANT")
1187     return readConstant();
1188   if (tok == "DATA_SEGMENT_ALIGN") {
1189     expect("(");
1190     Expr e = readExpr();
1191     expect(",");
1192     readExpr();
1193     expect(")");
1194     return [=] {
1195       return alignTo(script->getDot(), std::max((uint64_t)1, e().getValue()));
1196     };
1197   }
1198   if (tok == "DATA_SEGMENT_END") {
1199     expect("(");
1200     expect(".");
1201     expect(")");
1202     return [] { return script->getDot(); };
1203   }
1204   if (tok == "DATA_SEGMENT_RELRO_END") {
1205     // GNU linkers implements more complicated logic to handle
1206     // DATA_SEGMENT_RELRO_END. We instead ignore the arguments and
1207     // just align to the next page boundary for simplicity.
1208     expect("(");
1209     readExpr();
1210     expect(",");
1211     readExpr();
1212     expect(")");
1213     Expr e = getPageSize();
1214     return [=] { return alignTo(script->getDot(), e().getValue()); };
1215   }
1216   if (tok == "DEFINED") {
1217     StringRef name = readParenLiteral();
1218     return [=] { return symtab->find(name) ? 1 : 0; };
1219   }
1220   if (tok == "LENGTH") {
1221     StringRef name = readParenLiteral();
1222     if (script->memoryRegions.count(name) == 0) {
1223       setError("memory region not defined: " + name);
1224       return [] { return 0; };
1225     }
1226     return [=] { return script->memoryRegions[name]->length; };
1227   }
1228   if (tok == "LOADADDR") {
1229     StringRef name = readParenLiteral();
1230     OutputSection *cmd = script->getOrCreateOutputSection(name);
1231     cmd->usedInExpression = true;
1232     return [=] {
1233       checkIfExists(cmd, location);
1234       return cmd->getLMA();
1235     };
1236   }
1237   if (tok == "MAX" || tok == "MIN") {
1238     expect("(");
1239     Expr a = readExpr();
1240     expect(",");
1241     Expr b = readExpr();
1242     expect(")");
1243     if (tok == "MIN")
1244       return [=] { return std::min(a().getValue(), b().getValue()); };
1245     return [=] { return std::max(a().getValue(), b().getValue()); };
1246   }
1247   if (tok == "ORIGIN") {
1248     StringRef name = readParenLiteral();
1249     if (script->memoryRegions.count(name) == 0) {
1250       setError("memory region not defined: " + name);
1251       return [] { return 0; };
1252     }
1253     return [=] { return script->memoryRegions[name]->origin; };
1254   }
1255   if (tok == "SEGMENT_START") {
1256     expect("(");
1257     skip();
1258     expect(",");
1259     Expr e = readExpr();
1260     expect(")");
1261     return [=] { return e(); };
1262   }
1263   if (tok == "SIZEOF") {
1264     StringRef name = readParenLiteral();
1265     OutputSection *cmd = script->getOrCreateOutputSection(name);
1266     // Linker script does not create an output section if its content is empty.
1267     // We want to allow SIZEOF(.foo) where .foo is a section which happened to
1268     // be empty.
1269     return [=] { return cmd->size; };
1270   }
1271   if (tok == "SIZEOF_HEADERS")
1272     return [=] { return getHeaderSize(); };
1273
1274   // Tok is the dot.
1275   if (tok == ".")
1276     return [=] { return script->getSymbolValue(tok, location); };
1277
1278   // Tok is a literal number.
1279   if (Optional<uint64_t> val = parseInt(tok))
1280     return [=] { return *val; };
1281
1282   // Tok is a symbol name.
1283   if (!isValidCIdentifier(tok))
1284     setError("malformed number: " + tok);
1285   script->referencedSymbols.push_back(tok);
1286   return [=] { return script->getSymbolValue(tok, location); };
1287 }
1288
1289 Expr ScriptParser::readTernary(Expr cond) {
1290   Expr l = readExpr();
1291   expect(":");
1292   Expr r = readExpr();
1293   return [=] { return cond().getValue() ? l() : r(); };
1294 }
1295
1296 Expr ScriptParser::readParenExpr() {
1297   expect("(");
1298   Expr e = readExpr();
1299   expect(")");
1300   return e;
1301 }
1302
1303 std::vector<StringRef> ScriptParser::readOutputSectionPhdrs() {
1304   std::vector<StringRef> phdrs;
1305   while (!errorCount() && peek().startswith(":")) {
1306     StringRef tok = next();
1307     phdrs.push_back((tok.size() == 1) ? next() : tok.substr(1));
1308   }
1309   return phdrs;
1310 }
1311
1312 // Read a program header type name. The next token must be a
1313 // name of a program header type or a constant (e.g. "0x3").
1314 unsigned ScriptParser::readPhdrType() {
1315   StringRef tok = next();
1316   if (Optional<uint64_t> val = parseInt(tok))
1317     return *val;
1318
1319   unsigned ret = StringSwitch<unsigned>(tok)
1320                      .Case("PT_NULL", PT_NULL)
1321                      .Case("PT_LOAD", PT_LOAD)
1322                      .Case("PT_DYNAMIC", PT_DYNAMIC)
1323                      .Case("PT_INTERP", PT_INTERP)
1324                      .Case("PT_NOTE", PT_NOTE)
1325                      .Case("PT_SHLIB", PT_SHLIB)
1326                      .Case("PT_PHDR", PT_PHDR)
1327                      .Case("PT_TLS", PT_TLS)
1328                      .Case("PT_GNU_EH_FRAME", PT_GNU_EH_FRAME)
1329                      .Case("PT_GNU_STACK", PT_GNU_STACK)
1330                      .Case("PT_GNU_RELRO", PT_GNU_RELRO)
1331                      .Case("PT_OPENBSD_RANDOMIZE", PT_OPENBSD_RANDOMIZE)
1332                      .Case("PT_OPENBSD_WXNEEDED", PT_OPENBSD_WXNEEDED)
1333                      .Case("PT_OPENBSD_BOOTDATA", PT_OPENBSD_BOOTDATA)
1334                      .Default(-1);
1335
1336   if (ret == (unsigned)-1) {
1337     setError("invalid program header type: " + tok);
1338     return PT_NULL;
1339   }
1340   return ret;
1341 }
1342
1343 // Reads an anonymous version declaration.
1344 void ScriptParser::readAnonymousDeclaration() {
1345   std::vector<SymbolVersion> locals;
1346   std::vector<SymbolVersion> globals;
1347   std::tie(locals, globals) = readSymbols();
1348   for (const SymbolVersion &pat : locals)
1349     config->versionDefinitions[VER_NDX_LOCAL].patterns.push_back(pat);
1350   for (const SymbolVersion &pat : globals)
1351     config->versionDefinitions[VER_NDX_GLOBAL].patterns.push_back(pat);
1352
1353   expect(";");
1354 }
1355
1356 // Reads a non-anonymous version definition,
1357 // e.g. "VerStr { global: foo; bar; local: *; };".
1358 void ScriptParser::readVersionDeclaration(StringRef verStr) {
1359   // Read a symbol list.
1360   std::vector<SymbolVersion> locals;
1361   std::vector<SymbolVersion> globals;
1362   std::tie(locals, globals) = readSymbols();
1363   for (const SymbolVersion &pat : locals)
1364     config->versionDefinitions[VER_NDX_LOCAL].patterns.push_back(pat);
1365
1366   // Create a new version definition and add that to the global symbols.
1367   VersionDefinition ver;
1368   ver.name = verStr;
1369   ver.patterns = globals;
1370   ver.id = config->versionDefinitions.size();
1371   config->versionDefinitions.push_back(ver);
1372
1373   // Each version may have a parent version. For example, "Ver2"
1374   // defined as "Ver2 { global: foo; local: *; } Ver1;" has "Ver1"
1375   // as a parent. This version hierarchy is, probably against your
1376   // instinct, purely for hint; the runtime doesn't care about it
1377   // at all. In LLD, we simply ignore it.
1378   if (peek() != ";")
1379     skip();
1380   expect(";");
1381 }
1382
1383 static bool hasWildcard(StringRef s) {
1384   return s.find_first_of("?*[") != StringRef::npos;
1385 }
1386
1387 // Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
1388 std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
1389 ScriptParser::readSymbols() {
1390   std::vector<SymbolVersion> locals;
1391   std::vector<SymbolVersion> globals;
1392   std::vector<SymbolVersion> *v = &globals;
1393
1394   while (!errorCount()) {
1395     if (consume("}"))
1396       break;
1397     if (consumeLabel("local")) {
1398       v = &locals;
1399       continue;
1400     }
1401     if (consumeLabel("global")) {
1402       v = &globals;
1403       continue;
1404     }
1405
1406     if (consume("extern")) {
1407       std::vector<SymbolVersion> ext = readVersionExtern();
1408       v->insert(v->end(), ext.begin(), ext.end());
1409     } else {
1410       StringRef tok = next();
1411       v->push_back({unquote(tok), false, hasWildcard(tok)});
1412     }
1413     expect(";");
1414   }
1415   return {locals, globals};
1416 }
1417
1418 // Reads an "extern C++" directive, e.g.,
1419 // "extern "C++" { ns::*; "f(int, double)"; };"
1420 //
1421 // The last semicolon is optional. E.g. this is OK:
1422 // "extern "C++" { ns::*; "f(int, double)" };"
1423 std::vector<SymbolVersion> ScriptParser::readVersionExtern() {
1424   StringRef tok = next();
1425   bool isCXX = tok == "\"C++\"";
1426   if (!isCXX && tok != "\"C\"")
1427     setError("Unknown language");
1428   expect("{");
1429
1430   std::vector<SymbolVersion> ret;
1431   while (!errorCount() && peek() != "}") {
1432     StringRef tok = next();
1433     ret.push_back(
1434         {unquote(tok), isCXX, !tok.startswith("\"") && hasWildcard(tok)});
1435     if (consume("}"))
1436       return ret;
1437     expect(";");
1438   }
1439
1440   expect("}");
1441   return ret;
1442 }
1443
1444 uint64_t ScriptParser::readMemoryAssignment(StringRef s1, StringRef s2,
1445                                             StringRef s3) {
1446   if (!consume(s1) && !consume(s2) && !consume(s3)) {
1447     setError("expected one of: " + s1 + ", " + s2 + ", or " + s3);
1448     return 0;
1449   }
1450   expect("=");
1451   return readExpr()().getValue();
1452 }
1453
1454 // Parse the MEMORY command as specified in:
1455 // https://sourceware.org/binutils/docs/ld/MEMORY.html
1456 //
1457 // MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
1458 void ScriptParser::readMemory() {
1459   expect("{");
1460   while (!errorCount() && !consume("}")) {
1461     StringRef tok = next();
1462     if (tok == "INCLUDE") {
1463       readInclude();
1464       continue;
1465     }
1466
1467     uint32_t flags = 0;
1468     uint32_t negFlags = 0;
1469     if (consume("(")) {
1470       std::tie(flags, negFlags) = readMemoryAttributes();
1471       expect(")");
1472     }
1473     expect(":");
1474
1475     uint64_t origin = readMemoryAssignment("ORIGIN", "org", "o");
1476     expect(",");
1477     uint64_t length = readMemoryAssignment("LENGTH", "len", "l");
1478
1479     // Add the memory region to the region map.
1480     MemoryRegion *mr = make<MemoryRegion>(tok, origin, length, flags, negFlags);
1481     if (!script->memoryRegions.insert({tok, mr}).second)
1482       setError("region '" + tok + "' already defined");
1483   }
1484 }
1485
1486 // This function parses the attributes used to match against section
1487 // flags when placing output sections in a memory region. These flags
1488 // are only used when an explicit memory region name is not used.
1489 std::pair<uint32_t, uint32_t> ScriptParser::readMemoryAttributes() {
1490   uint32_t flags = 0;
1491   uint32_t negFlags = 0;
1492   bool invert = false;
1493
1494   for (char c : next().lower()) {
1495     uint32_t flag = 0;
1496     if (c == '!')
1497       invert = !invert;
1498     else if (c == 'w')
1499       flag = SHF_WRITE;
1500     else if (c == 'x')
1501       flag = SHF_EXECINSTR;
1502     else if (c == 'a')
1503       flag = SHF_ALLOC;
1504     else if (c != 'r')
1505       setError("invalid memory region attribute");
1506
1507     if (invert)
1508       negFlags |= flag;
1509     else
1510       flags |= flag;
1511   }
1512   return {flags, negFlags};
1513 }
1514
1515 void readLinkerScript(MemoryBufferRef mb) {
1516   ScriptParser(mb).readLinkerScript();
1517 }
1518
1519 void readVersionScript(MemoryBufferRef mb) {
1520   ScriptParser(mb).readVersionScript();
1521 }
1522
1523 void readDynamicList(MemoryBufferRef mb) { ScriptParser(mb).readDynamicList(); }
1524
1525 void readDefsym(StringRef name, MemoryBufferRef mb) {
1526   ScriptParser(mb).readDefsym(name);
1527 }
1528
1529 } // namespace elf
1530 } // namespace lld