ScriptParser.cpp

//===- ScriptParser.cpp ---------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains a recursive-descendent parser for linker scripts.
// Parsed results are stored to Config and Script global objects.
//
//===----------------------------------------------------------------------===//

#include"ScriptParser.h"
#include"Config.h"
#include"Driver.h"
#include"InputSection.h"
#include"LinkerScript.h"
#include"OutputSections.h"
#include"ScriptLexer.h"
#include"Symbols.h"
#include"Target.h"
#include"lld/Common/Memory.h"
#include"llvm/ADT/SmallString.h"
#include"llvm/ADT/StringRef.h"
#include"llvm/ADT/StringSet.h"
#include"llvm/ADT/StringSwitch.h"
#include"llvm/BinaryFormat/ELF.h"
#include"llvm/Support/Casting.h"
#include"llvm/Support/ErrorHandling.h"
#include"llvm/Support/FileSystem.h"
#include"llvm/Support/Path.h"
#include<cassert>
#include<limits>
#include<vector>

usingnamespacellvm;
usingnamespacellvm::ELF;
usingnamespacellvm::support::endian;
usingnamespacelld;
usingnamespacelld::elf;

staticboolisUnderSysroot(StringRef Path);

namespace {
classScriptParserfinal : ScriptLexer {
public:
ScriptParser(MemoryBufferRef MB)
 : ScriptLexer(MB),
IsUnderSysroot(isUnderSysroot(MB.getBufferIdentifier())) {}

voidreadLinkerScript();
voidreadVersionScript();
voidreadDynamicList();
voidreadDefsym(StringRef Name);

private:
voidaddFile(StringRef Path);

voidreadAsNeeded();
voidreadEntry();
voidreadExtern();
voidreadGroup();
voidreadInclude();
voidreadInput();
voidreadMemory();
voidreadOutput();
voidreadOutputArch();
voidreadOutputFormat();
voidreadPhdrs();
voidreadRegionAlias();
voidreadSearchDir();
voidreadSections();
voidreadTarget();
voidreadVersion();
voidreadVersionScriptCommand();

 SymbolAssignment *readSymbolAssignment(StringRef Name);
 ByteCommand *readByteCommand(StringRef Tok);
 std::array<uint8_t, 4> readFill();
 std::array<uint8_t, 4> parseFill(StringRef Tok);
boolreadSectionDirective(OutputSection *Cmd, StringRef Tok1, StringRef Tok2);
voidreadSectionAddressType(OutputSection *Cmd);
 OutputSection *readOverlaySectionDescription();
 OutputSection *readOutputSectionDescription(StringRef OutSec);
 std::vector<BaseCommand *> readOverlay();
 std::vector<StringRef> readOutputSectionPhdrs();
 InputSectionDescription *readInputSectionDescription(StringRef Tok);
 StringMatcher readFilePatterns();
 std::vector<SectionPattern> readInputSectionsList();
 InputSectionDescription *readInputSectionRules(StringRef FilePattern);
unsignedreadPhdrType();
 SortSectionPolicy readSortKind();
 SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
 SymbolAssignment *readAssignment(StringRef Tok);
voidreadSort();
 Expr readAssert();
 Expr readConstant();
 Expr getPageSize();

uint64_treadMemoryAssignment(StringRef, StringRef, StringRef);
 std::pair<uint32_t, uint32_t> readMemoryAttributes();

 Expr combine(StringRef Op, Expr L, Expr R);
 Expr readExpr();
 Expr readExpr1(Expr Lhs, int MinPrec);
 StringRef readParenLiteral();
 Expr readPrimary();
 Expr readTernary(Expr Cond);
 Expr readParenExpr();

// For parsing version script.
 std::vector<SymbolVersion> readVersionExtern();
voidreadAnonymousDeclaration();
voidreadVersionDeclaration(StringRef VerStr);

 std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
readSymbols();

// True if a script being read is in a subdirectory specified by -sysroot.
bool IsUnderSysroot;

// A set to detect an INCLUDE() cycle.
 StringSet<> Seen;
};
} // namespace

static StringRef unquote(StringRef S) {
if (S.startswith("\""))
return S.substr(1, S.size() - 2);
return S;
}

staticboolisUnderSysroot(StringRef Path) {
if (Config->Sysroot == "")
returnfalse;
for (; !Path.empty(); Path = sys::path::parent_path(Path))
if (sys::fs::equivalent(Config->Sysroot, Path))
returntrue;
returnfalse;
}

// Some operations only support one non absolute value. Move the
// absolute one to the right hand side for convenience.
staticvoidmoveAbsRight(ExprValue &A, ExprValue &B) {
if (A.Sec == nullptr || (A.ForceAbsolute && !B.isAbsolute()))
std::swap(A, B);
if (!B.isAbsolute())
error(A.Loc + ": at least one side of the expression must be absolute");
}

static ExprValue add(ExprValue A, ExprValue B) {
moveAbsRight(A, B);
return {A.Sec, A.ForceAbsolute, A.getSectionOffset() + B.getValue(), A.Loc};
}

static ExprValue sub(ExprValue A, ExprValue B) {
// The distance between two symbols in sections is absolute.
if (!A.isAbsolute() && !B.isAbsolute())
return A.getValue() - B.getValue();
return {A.Sec, false, A.getSectionOffset() - B.getValue(), A.Loc};
}

static ExprValue bitAnd(ExprValue A, ExprValue B) {
moveAbsRight(A, B);
return {A.Sec, A.ForceAbsolute,
 (A.getValue() & B.getValue()) - A.getSecAddr(), A.Loc};
}

static ExprValue bitOr(ExprValue A, ExprValue B) {
moveAbsRight(A, B);
return {A.Sec, A.ForceAbsolute,
 (A.getValue() | B.getValue()) - A.getSecAddr(), A.Loc};
}

voidScriptParser::readDynamicList() {
 Config->HasDynamicList = true;
expect("{");
 std::vector<SymbolVersion> Locals;
 std::vector<SymbolVersion> Globals;
std::tie(Locals, Globals) = readSymbols();
expect(";");

if (!atEOF()) {
setError("EOF expected, but got " + next());
return;
 }
if (!Locals.empty()) {
setError("\"local:\" scope not supported in --dynamic-list");
return;
 }

for (SymbolVersion V : Globals)
 Config->DynamicList.push_back(V);
}

voidScriptParser::readVersionScript() {
readVersionScriptCommand();
if (!atEOF())
setError("EOF expected, but got " + next());
}

voidScriptParser::readVersionScriptCommand() {
if (consume("{")) {
readAnonymousDeclaration();
return;
 }

while (!atEOF() && !errorCount() && peek() != "}") {
 StringRef VerStr = next();
if (VerStr == "{") {
setError("anonymous version definition is used in "
"combination with other version definitions");
return;
 }
expect("{");
readVersionDeclaration(VerStr);
 }
}

voidScriptParser::readVersion() {
expect("{");
readVersionScriptCommand();
expect("}");
}

voidScriptParser::readLinkerScript() {
while (!atEOF()) {
 StringRef Tok = next();
if (Tok == ";")
continue;

if (Tok == "ENTRY") {
readEntry();
 } elseif (Tok == "EXTERN") {
readExtern();
 } elseif (Tok == "GROUP") {
readGroup();
 } elseif (Tok == "INCLUDE") {
readInclude();
 } elseif (Tok == "INPUT") {
readInput();
 } elseif (Tok == "MEMORY") {
readMemory();
 } elseif (Tok == "OUTPUT") {
readOutput();
 } elseif (Tok == "OUTPUT_ARCH") {
readOutputArch();
 } elseif (Tok == "OUTPUT_FORMAT") {
readOutputFormat();
 } elseif (Tok == "PHDRS") {
readPhdrs();
 } elseif (Tok == "REGION_ALIAS") {
readRegionAlias();
 } elseif (Tok == "SEARCH_DIR") {
readSearchDir();
 } elseif (Tok == "SECTIONS") {
readSections();
 } elseif (Tok == "TARGET") {
readTarget();
 } elseif (Tok == "VERSION") {
readVersion();
 } elseif (SymbolAssignment *Cmd = readAssignment(Tok)) {
 Script->SectionCommands.push_back(Cmd);
 } else {
setError("unknown directive: " + Tok);
 }
 }
}

voidScriptParser::readDefsym(StringRef Name) {
if (errorCount())
return;
 Expr E = readExpr();
if (!atEOF())
setError("EOF expected, but got " + next());
 SymbolAssignment *Cmd = make<SymbolAssignment>(Name, E, getCurrentLocation());
 Script->SectionCommands.push_back(Cmd);
}

voidScriptParser::addFile(StringRef S) {
if (IsUnderSysroot && S.startswith("/")) {
 SmallString<128> PathData;
 StringRef Path = (Config->Sysroot + S).toStringRef(PathData);
if (sys::fs::exists(Path)) {
 Driver->addFile(Saver.save(Path), /*WithLOption=*/false);
return;
 }
 }

if (S.startswith("/")) {
 Driver->addFile(S, /*WithLOption=*/false);
 } elseif (S.startswith("=")) {
if (Config->Sysroot.empty())
 Driver->addFile(S.substr(1), /*WithLOption=*/false);
else
 Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)),
/*WithLOption=*/false);
 } elseif (S.startswith("-l")) {
 Driver->addLibrary(S.substr(2));
 } elseif (sys::fs::exists(S)) {
 Driver->addFile(S, /*WithLOption=*/false);
 } else {
if (Optional<std::string> Path = findFromSearchPaths(S))
 Driver->addFile(Saver.save(*Path), /*WithLOption=*/true);
else
setError("unable to find " + S);
 }
}

voidScriptParser::readAsNeeded() {
expect("(");
bool Orig = Config->AsNeeded;
 Config->AsNeeded = true;
while (!errorCount() && !consume(")"))
addFile(unquote(next()));
 Config->AsNeeded = Orig;
}

voidScriptParser::readEntry() {
// -e <symbol> takes predecence over ENTRY(<symbol>).
expect("(");
 StringRef Tok = next();
if (Config->Entry.empty())
 Config->Entry = Tok;
expect(")");
}

voidScriptParser::readExtern() {
expect("(");
while (!errorCount() && !consume(")"))
 Config->Undefined.push_back(unquote(next()));
}

voidScriptParser::readGroup() {
bool Orig = InputFile::IsInGroup;
 InputFile::IsInGroup = true;
readInput();
 InputFile::IsInGroup = Orig;
if (!Orig)
 ++InputFile::NextGroupId;
}

voidScriptParser::readInclude() {
 StringRef Tok = unquote(next());

if (!Seen.insert(Tok).second) {
setError("there is a cycle in linker script INCLUDEs");
return;
 }

if (Optional<std::string> Path = searchScript(Tok)) {
if (Optional<MemoryBufferRef> MB = readFile(*Path))
tokenize(*MB);
return;
 }
setError("cannot find linker script " + Tok);
}

voidScriptParser::readInput() {
expect("(");
while (!errorCount() && !consume(")")) {
if (consume("AS_NEEDED"))
readAsNeeded();
else
addFile(unquote(next()));
 }
}

voidScriptParser::readOutput() {
// -o <file> takes predecence over OUTPUT(<file>).
expect("(");
 StringRef Tok = next();
if (Config->OutputFile.empty())
 Config->OutputFile = unquote(Tok);
expect(")");
}

voidScriptParser::readOutputArch() {
// OUTPUT_ARCH is ignored for now.
expect("(");
while (!errorCount() && !consume(")"))
skip();
}

static std::pair<ELFKind, uint16_t> parseBfdName(StringRef S) {
return StringSwitch<std::pair<ELFKind, uint16_t>>(S)
 .Case("elf32-i386", {ELF32LEKind, EM_386})
 .Case("elf32-iamcu", {ELF32LEKind, EM_IAMCU})
 .Case("elf32-littlearm", {ELF32LEKind, EM_ARM})
 .Case("elf32-x86-64", {ELF32LEKind, EM_X86_64})
 .Case("elf64-aarch64", {ELF64LEKind, EM_AARCH64})
 .Case("elf64-littleaarch64", {ELF64LEKind, EM_AARCH64})
 .Case("elf32-powerpc", {ELF32BEKind, EM_PPC})
 .Case("elf64-powerpc", {ELF64BEKind, EM_PPC64})
 .Case("elf64-powerpcle", {ELF64LEKind, EM_PPC64})
 .Case("elf64-x86-64", {ELF64LEKind, EM_X86_64})
 .Cases("elf32-tradbigmips", "elf32-bigmips", {ELF32BEKind, EM_MIPS})
 .Case("elf32-ntradbigmips", {ELF32BEKind, EM_MIPS})
 .Case("elf32-tradlittlemips", {ELF32LEKind, EM_MIPS})
 .Case("elf32-ntradlittlemips", {ELF32LEKind, EM_MIPS})
 .Case("elf64-tradbigmips", {ELF64BEKind, EM_MIPS})
 .Case("elf64-tradlittlemips", {ELF64LEKind, EM_MIPS})
 .Case("elf32-littleriscv", {ELF32LEKind, EM_RISCV})
 .Case("elf64-littleriscv", {ELF64LEKind, EM_RISCV})
 .Default({ELFNoneKind, EM_NONE});
}

// Parse OUTPUT_FORMAT(bfdname) or OUTPUT_FORMAT(bfdname, big, little).
// Currently we ignore big and little parameters.
voidScriptParser::readOutputFormat() {
expect("(");

 StringRef Name = unquote(next());
 StringRef S = Name;
if (S.consume_back("-freebsd"))
 Config->OSABI = ELFOSABI_FREEBSD;

std::tie(Config->EKind, Config->EMachine) = parseBfdName(S);
if (Config->EMachine == EM_NONE)
setError("unknown output format name: " + Name);
if (S == "elf32-ntradlittlemips" || S == "elf32-ntradbigmips")
 Config->MipsN32Abi = true;

if (consume(")"))
return;
expect(",");
skip();
expect(",");
skip();
expect(")");
}

voidScriptParser::readPhdrs() {
expect("{");

while (!errorCount() && !consume("}")) {
 PhdrsCommand Cmd;
 Cmd.Name = next();
 Cmd.Type = readPhdrType();

while (!errorCount() && !consume(";")) {
if (consume("FILEHDR"))
 Cmd.HasFilehdr = true;
elseif (consume("PHDRS"))
 Cmd.HasPhdrs = true;
elseif (consume("AT"))
 Cmd.LMAExpr = readParenExpr();
elseif (consume("FLAGS"))
 Cmd.Flags = readParenExpr()().getValue();
else
setError("unexpected header attribute: " + next());
 }

 Script->PhdrsCommands.push_back(Cmd);
 }
}

voidScriptParser::readRegionAlias() {
expect("(");
 StringRef Alias = unquote(next());
expect(",");
 StringRef Name = next();
expect(")");

if (Script->MemoryRegions.count(Alias))
setError("redefinition of memory region '" + Alias + "'");
if (!Script->MemoryRegions.count(Name))
setError("memory region '" + Name + "' is not defined");
 Script->MemoryRegions.insert({Alias, Script->MemoryRegions[Name]});
}

voidScriptParser::readSearchDir() {
expect("(");
 StringRef Tok = next();
if (!Config->Nostdlib)
 Config->SearchPaths.push_back(unquote(Tok));
expect(")");
}

// This reads an overlay description. Overlays are used to describe output
// sections that use the same virtual memory range and normally would trigger
// linker's sections sanity check failures.
// https://sourceware.org/binutils/docs/ld/Overlay-Description.html#Overlay-Description
std::vector<BaseCommand *> ScriptParser::readOverlay() {
// VA and LMA expressions are optional, though for simplicity of
// implementation we assume they are not. That is what OVERLAY was designed
// for first of all: to allow sections with overlapping VAs at different LMAs.
 Expr AddrExpr = readExpr();
expect(":");
expect("AT");
 Expr LMAExpr = readParenExpr();
expect("{");

 std::vector<BaseCommand *> V;
 OutputSection *Prev = nullptr;
while (!errorCount() && !consume("}")) {
// VA is the same for all sections. The LMAs are consecutive in memory
// starting from the base load address specified.
 OutputSection *OS = readOverlaySectionDescription();
 OS->AddrExpr = AddrExpr;
if (Prev)
 OS->LMAExpr = [=] { return Prev->getLMA() + Prev->Size; };
else
 OS->LMAExpr = LMAExpr;
 V.push_back(OS);
 Prev = OS;
 }

// According to the specification, at the end of the overlay, the location
// counter should be equal to the overlay base address plus size of the
// largest section seen in the overlay.
// Here we want to create the Dot assignment command to achieve that.
 Expr MoveDot = [=] {
uint64_t Max = 0;
for (BaseCommand *Cmd : V)
 Max = std::max(Max, cast<OutputSection>(Cmd)->Size);
returnAddrExpr().getValue() + Max;
 };
 V.push_back(make<SymbolAssignment>(".", MoveDot, getCurrentLocation()));
return V;
}

voidScriptParser::readSections() {
 Script->HasSectionsCommand = true;

// -no-rosegment is used to avoid placing read only non-executable sections in
// their own segment. We do the same if SECTIONS command is present in linker
// script. See comment for computeFlags().
 Config->SingleRoRx = true;

expect("{");
 std::vector<BaseCommand *> V;
while (!errorCount() && !consume("}")) {
 StringRef Tok = next();
if (Tok == "OVERLAY") {
for (BaseCommand *Cmd : readOverlay())
 V.push_back(Cmd);
continue;
 } elseif (Tok == "INCLUDE") {
readInclude();
continue;
 }

if (BaseCommand *Cmd = readAssignment(Tok))
 V.push_back(Cmd);
else
 V.push_back(readOutputSectionDescription(Tok));
 }

if (!atEOF() && consume("INSERT")) {
 std::vector<BaseCommand *> *Dest = nullptr;
if (consume("AFTER"))
 Dest = &Script->InsertAfterCommands[next()];
elseif (consume("BEFORE"))
 Dest = &Script->InsertBeforeCommands[next()];
else
setError("expected AFTER/BEFORE, but got '" + next() + "'");
if (Dest)
 Dest->insert(Dest->end(), V.begin(), V.end());
return;
 }

 Script->SectionCommands.insert(Script->SectionCommands.end(), V.begin(),
 V.end());
}

voidScriptParser::readTarget() {
// TARGET(foo) is an alias for "--format foo". Unlike GNU linkers,
// we accept only a limited set of BFD names (i.e. "elf" or "binary")
// for --format. We recognize only /^elf/ and "binary" in the linker
// script as well.
expect("(");
 StringRef Tok = next();
expect(")");

if (Tok.startswith("elf"))
 Config->FormatBinary = false;
elseif (Tok == "binary")
 Config->FormatBinary = true;
else
setError("unknown target: " + Tok);
}

staticintprecedence(StringRef Op) {
return StringSwitch<int>(Op)
 .Cases("*", "/", "%", 8)
 .Cases("+", "-", 7)
 .Cases("<<", ">>", 6)
 .Cases("<", "<=", ">", ">=", "==", "!=", 5)
 .Case("&", 4)
 .Case("|", 3)
 .Case("&&", 2)
 .Case("||", 1)
 .Default(-1);
}

StringMatcher ScriptParser::readFilePatterns() {
 std::vector<StringRef> V;
while (!errorCount() && !consume(")"))
 V.push_back(next());
returnStringMatcher(V);
}

SortSectionPolicy ScriptParser::readSortKind() {
if (consume("SORT") || consume("SORT_BY_NAME"))
return SortSectionPolicy::Name;
if (consume("SORT_BY_ALIGNMENT"))
return SortSectionPolicy::Alignment;
if (consume("SORT_BY_INIT_PRIORITY"))
return SortSectionPolicy::Priority;
if (consume("SORT_NONE"))
return SortSectionPolicy::None;
return SortSectionPolicy::Default;
}

// Reads SECTIONS command contents in the following form:
//
// <contents> ::= <elem>*
// <elem> ::= <exclude>? <glob-pattern>
// <exclude> ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
//
// For example,
//
// *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
//
// is parsed as ".foo", ".bar" with "a.o", and ".baz" with "b.o".
// The semantics of that is section .foo in any file, section .bar in
// any file but a.o, and section .baz in any file but b.o.
std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
 std::vector<SectionPattern> Ret;
while (!errorCount() && peek() != ")") {
 StringMatcher ExcludeFilePat;
if (consume("EXCLUDE_FILE")) {
expect("(");
 ExcludeFilePat = readFilePatterns();
 }

 std::vector<StringRef> V;
while (!errorCount() && peek() != ")" && peek() != "EXCLUDE_FILE")
 V.push_back(unquote(next()));

if (!V.empty())
 Ret.push_back({std::move(ExcludeFilePat), StringMatcher(V)});
else
setError("section pattern is expected");
 }
return Ret;
}

// Reads contents of "SECTIONS" directive. That directive contains a
// list of glob patterns for input sections. The grammar is as follows.
//
// <patterns> ::= <section-list>
// | <sort> "(" <section-list> ")"
// | <sort> "(" <sort> "(" <section-list> ")" ")"
//
// <sort> ::= "SORT" | "SORT_BY_NAME" | "SORT_BY_ALIGNMENT"
// | "SORT_BY_INIT_PRIORITY" | "SORT_NONE"
//
// <section-list> is parsed by readInputSectionsList().
InputSectionDescription *
ScriptParser::readInputSectionRules(StringRef FilePattern) {
auto *Cmd = make<InputSectionDescription>(FilePattern);
expect("(");

while (!errorCount() && !consume(")")) {
 SortSectionPolicy Outer = readSortKind();
 SortSectionPolicy Inner = SortSectionPolicy::Default;
 std::vector<SectionPattern> V;
if (Outer != SortSectionPolicy::Default) {
expect("(");
 Inner = readSortKind();
if (Inner != SortSectionPolicy::Default) {
expect("(");
 V = readInputSectionsList();
expect(")");
 } else {
 V = readInputSectionsList();
 }
expect(")");
 } else {
 V = readInputSectionsList();
 }

for (SectionPattern &Pat : V) {
 Pat.SortInner = Inner;
 Pat.SortOuter = Outer;
 }

std::move(V.begin(), V.end(), std::back_inserter(Cmd->SectionPatterns));
 }
return Cmd;
}

InputSectionDescription *
ScriptParser::readInputSectionDescription(StringRef Tok) {
// Input section wildcard can be surrounded by KEEP.
// https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
if (Tok == "KEEP") {
expect("(");
 StringRef FilePattern = next();
 InputSectionDescription *Cmd = readInputSectionRules(FilePattern);
expect(")");
 Script->KeptSections.push_back(Cmd);
return Cmd;
 }
returnreadInputSectionRules(Tok);
}

voidScriptParser::readSort() {
expect("(");
expect("CONSTRUCTORS");
expect(")");
}

Expr ScriptParser::readAssert() {
expect("(");
 Expr E = readExpr();
expect(",");
 StringRef Msg = unquote(next());
expect(")");

return [=] {
if (!E().getValue())
error(Msg);
return Script->getDot();
 };
}

// Reads a FILL(expr) command. We handle the FILL command as an
// alias for =fillexp section attribute, which is different from
// what GNU linkers do.
// https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
std::array<uint8_t, 4> ScriptParser::readFill() {
expect("(");
 std::array<uint8_t, 4> V = parseFill(next());
expect(")");
return V;
}

// Tries to read the special directive for an output section definition which
// can be one of following: "(NOLOAD)", "(COPY)", "(INFO)" or "(OVERLAY)".
// Tok1 and Tok2 are next 2 tokens peeked. See comment for readSectionAddressType below.
boolScriptParser::readSectionDirective(OutputSection *Cmd, StringRef Tok1, StringRef Tok2) {
if (Tok1 != "(")
returnfalse;
if (Tok2 != "NOLOAD" && Tok2 != "COPY" && Tok2 != "INFO" && Tok2 != "OVERLAY")
returnfalse;

expect("(");
if (consume("NOLOAD")) {
 Cmd->Noload = true;
 } else {
skip(); // This is "COPY", "INFO" or "OVERLAY".
 Cmd->NonAlloc = true;
 }
expect(")");
returntrue;
}

// Reads an expression and/or the special directive for an output
// section definition. Directive is one of following: "(NOLOAD)",
// "(COPY)", "(INFO)" or "(OVERLAY)".
//
// An output section name can be followed by an address expression
// and/or directive. This grammar is not LL(1) because "(" can be
// interpreted as either the beginning of some expression or beginning
// of directive.
//
// https://sourceware.org/binutils/docs/ld/Output-Section-Address.html
// https://sourceware.org/binutils/docs/ld/Output-Section-Type.html
voidScriptParser::readSectionAddressType(OutputSection *Cmd) {
if (readSectionDirective(Cmd, peek(), peek2()))
return;

 Cmd->AddrExpr = readExpr();
if (peek() == "(" && !readSectionDirective(Cmd, "(", peek2()))
setError("unknown section directive: " + peek2());
}

static Expr checkAlignment(Expr E, std::string &Loc) {
return [=] {
uint64_t Alignment = std::max((uint64_t)1, E().getValue());
if (!isPowerOf2_64(Alignment)) {
error(Loc + ": alignment must be power of 2");
return (uint64_t)1; // Return a dummy value.
 }
return Alignment;
 };
}

OutputSection *ScriptParser::readOverlaySectionDescription() {
 OutputSection *Cmd =
 Script->createOutputSection(next(), getCurrentLocation());
 Cmd->InOverlay = true;
expect("{");
while (!errorCount() && !consume("}"))
 Cmd->SectionCommands.push_back(readInputSectionRules(next()));
 Cmd->Phdrs = readOutputSectionPhdrs();
return Cmd;
}

OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec) {
 OutputSection *Cmd =
 Script->createOutputSection(OutSec, getCurrentLocation());

size_t SymbolsReferenced = Script->ReferencedSymbols.size();

if (peek() != ":")
readSectionAddressType(Cmd);
expect(":");

 std::string Location = getCurrentLocation();
if (consume("AT"))
 Cmd->LMAExpr = readParenExpr();
if (consume("ALIGN"))
 Cmd->AlignExpr = checkAlignment(readParenExpr(), Location);
if (consume("SUBALIGN"))
 Cmd->SubalignExpr = checkAlignment(readParenExpr(), Location);

// Parse constraints.
if (consume("ONLY_IF_RO"))
 Cmd->Constraint = ConstraintKind::ReadOnly;
if (consume("ONLY_IF_RW"))
 Cmd->Constraint = ConstraintKind::ReadWrite;
expect("{");

while (!errorCount() && !consume("}")) {
 StringRef Tok = next();
if (Tok == ";") {
// Empty commands are allowed. Do nothing here.
 } elseif (SymbolAssignment *Assign = readAssignment(Tok)) {
 Cmd->SectionCommands.push_back(Assign);
 } elseif (ByteCommand *Data = readByteCommand(Tok)) {
 Cmd->SectionCommands.push_back(Data);
 } elseif (Tok == "CONSTRUCTORS") {
// CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
// by name. This is for very old file formats such as ECOFF/XCOFF.
// For ELF, we should ignore.
 } elseif (Tok == "FILL") {
 Cmd->Filler = readFill();
 } elseif (Tok == "SORT") {
readSort();
 } elseif (Tok == "INCLUDE") {
readInclude();
 } elseif (peek() == "(") {
 Cmd->SectionCommands.push_back(readInputSectionDescription(Tok));
 } else {
// We have a file name and no input sections description. It is not a
// commonly used syntax, but still acceptable. In that case, all sections
// from the file will be included.
auto *ISD = make<InputSectionDescription>(Tok);
 ISD->SectionPatterns.push_back({{}, StringMatcher({"*"})});
 Cmd->SectionCommands.push_back(ISD);
 }
 }

if (consume(">"))
 Cmd->MemoryRegionName = next();

if (consume("AT")) {
expect(">");
 Cmd->LMARegionName = next();
 }

if (Cmd->LMAExpr && !Cmd->LMARegionName.empty())
error("section can't have both LMA and a load region");

 Cmd->Phdrs = readOutputSectionPhdrs();

if (consume("="))
 Cmd->Filler = parseFill(next());
elseif (peek().startswith("="))
 Cmd->Filler = parseFill(next().drop_front());

// Consume optional comma following output section command.
consume(",");

if (Script->ReferencedSymbols.size() > SymbolsReferenced)
 Cmd->ExpressionsUseSymbols = true;
return Cmd;
}

// Parses a given string as a octal/decimal/hexadecimal number and
// returns it as a big-endian number. Used for `=<fillexp>`.
// https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
//
// When reading a hexstring, ld.bfd handles it as a blob of arbitrary
// size, while ld.gold always handles it as a 32-bit big-endian number.
// We are compatible with ld.gold because it's easier to implement.
std::array<uint8_t, 4> ScriptParser::parseFill(StringRef Tok) {
uint32_t V = 0;
if (!to_integer(Tok, V))
setError("invalid filler expression: " + Tok);

 std::array<uint8_t, 4> Buf;
write32be(Buf.data(), V);
return Buf;
}

SymbolAssignment *ScriptParser::readProvideHidden(bool Provide, bool Hidden) {
expect("(");
 SymbolAssignment *Cmd = readSymbolAssignment(next());
 Cmd->Provide = Provide;
 Cmd->Hidden = Hidden;
expect(")");
return Cmd;
}

SymbolAssignment *ScriptParser::readAssignment(StringRef Tok) {
// Assert expression returns Dot, so this is equal to ".=."
if (Tok == "ASSERT")
return make<SymbolAssignment>(".", readAssert(), getCurrentLocation());

size_t OldPos = Pos;
 SymbolAssignment *Cmd = nullptr;
if (peek() == "=" || peek() == "+=")
 Cmd = readSymbolAssignment(Tok);
elseif (Tok == "PROVIDE")
 Cmd = readProvideHidden(true, false);
elseif (Tok == "HIDDEN")
 Cmd = readProvideHidden(false, true);
elseif (Tok == "PROVIDE_HIDDEN")
 Cmd = readProvideHidden(true, true);

if (Cmd) {
 Cmd->CommandString =
 Tok.str() + "" +
llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, "");
expect(";");
 }
return Cmd;
}

SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef Name) {
 StringRef Op = next();
assert(Op == "=" || Op == "+=");
 Expr E = readExpr();
if (Op == "+=") {
 std::string Loc = getCurrentLocation();
 E = [=] { returnadd(Script->getSymbolValue(Name, Loc), E()); };
 }
return make<SymbolAssignment>(Name, E, getCurrentLocation());
}

// This is an operator-precedence parser to parse a linker
// script expression.
Expr ScriptParser::readExpr() {
// Our lexer is context-aware. Set the in-expression bit so that
// they apply different tokenization rules.
bool Orig = InExpr;
 InExpr = true;
 Expr E = readExpr1(readPrimary(), 0);
 InExpr = Orig;
return E;
}

Expr ScriptParser::combine(StringRef Op, Expr L, Expr R) {
if (Op == "+")
return [=] { returnadd(L(), R()); };
if (Op == "-")
return [=] { returnsub(L(), R()); };
if (Op == "*")
return [=] { returnL().getValue() * R().getValue(); };
if (Op == "/") {
 std::string Loc = getCurrentLocation();
return [=]() -> uint64_t {
if (uint64_t RV = R().getValue())
returnL().getValue() / RV;
error(Loc + ": division by zero");
return0;
 };
 }
if (Op == "%") {
 std::string Loc = getCurrentLocation();
return [=]() -> uint64_t {
if (uint64_t RV = R().getValue())
returnL().getValue() % RV;
error(Loc + ": modulo by zero");
return0;
 };
 }
if (Op == "<<")
return [=] { returnL().getValue() << R().getValue(); };
if (Op == ">>")
return [=] { returnL().getValue() >> R().getValue(); };
if (Op == "<")
return [=] { returnL().getValue() < R().getValue(); };
if (Op == ">")
return [=] { returnL().getValue() > R().getValue(); };
if (Op == ">=")
return [=] { returnL().getValue() >= R().getValue(); };
if (Op == "<=")
return [=] { returnL().getValue() <= R().getValue(); };
if (Op == "==")
return [=] { returnL().getValue() == R().getValue(); };
if (Op == "!=")
return [=] { returnL().getValue() != R().getValue(); };
if (Op == "||")