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

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