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