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

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