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