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"InputFiles.h"
#include"LinkerScript.h"
#include"OutputSections.h"
#include"ScriptLexer.h"
#include"SymbolTable.h"
#include"Symbols.h"
#include"Target.h"
#include"lld/Common/CommonLinkerContext.h"
#include"llvm/ADT/SmallString.h"
#include"llvm/ADT/StringRef.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/MathExtras.h"
#include"llvm/Support/Path.h"
#include"llvm/Support/SaveAndRestore.h"
#include"llvm/Support/TimeProfiler.h"
#include<cassert>
#include<limits>
#include<optional>
#include<vector>

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

namespace {
classScriptParserfinal : ScriptLexer {
public:
ScriptParser(Ctx &ctx, MemoryBufferRef mb) : ScriptLexer(ctx, mb), ctx(ctx) {}

voidreadLinkerScript();
voidreadVersionScript();
voidreadDynamicList();
voidreadDefsym();

private:
voidaddFile(StringRef path);

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

 StringRef readName();
 SymbolAssignment *readSymbolAssignment(StringRef name);
 ByteCommand *readByteCommand(StringRef tok);
 std::array<uint8_t, 4> readFill();
boolreadSectionDirective(OutputSection *cmd, StringRef tok);
voidreadSectionAddressType(OutputSection *cmd);
 OutputDesc *readOverlaySectionDescription();
 OutputDesc *readOutputSectionDescription(StringRef outSec);
 SmallVector<SectionCommand *, 0> readOverlay();
 SectionClassDesc *readSectionClassDescription();
 StringRef readSectionClassName();
 SmallVector<StringRef, 0> readOutputSectionPhdrs();
 std::pair<uint64_t, uint64_t> readInputSectionFlags();
 InputSectionDescription *readInputSectionDescription(StringRef tok);
 StringMatcher readFilePatterns();
 SmallVector<SectionPattern, 0> readInputSectionsList();
 InputSectionDescription *readInputSectionRules(StringRef filePattern,
uint64_t withFlags,
uint64_t withoutFlags);
unsignedreadPhdrType();
 SortSectionPolicy peekSortKind();
 SortSectionPolicy readSortKind();
 SymbolAssignment *readProvideHidden(bool provide, bool hidden);
 SymbolAssignment *readAssignment(StringRef tok);
voidreadSort();
 Expr readAssert();
 Expr readConstant();
 Expr getPageSize();

 Expr readMemoryAssignment(StringRef, StringRef, StringRef);
voidreadMemoryAttributes(uint32_t &flags, uint32_t &invFlags,
uint32_t &negFlags, uint32_t &negInvFlags);

 Expr combine(StringRef op, Expr l, Expr r);
 Expr readExpr();
 Expr readExpr1(Expr lhs, int minPrec);
 StringRef readParenName();
 Expr readPrimary();
 Expr readTernary(Expr cond);
 Expr readParenExpr();

// For parsing version script.
 SmallVector<SymbolVersion, 0> readVersionExtern();
voidreadAnonymousDeclaration();
voidreadVersionDeclaration(StringRef verStr);

 std::pair<SmallVector<SymbolVersion, 0>, SmallVector<SymbolVersion, 0>>
readSymbols();

 Ctx &ctx;

// If we are currently parsing a PROVIDE|PROVIDE_HIDDEN command,
// then this member is set to the PROVIDE symbol name.
 std::optional<llvm::StringRef> activeProvideSym;
};
} // namespace

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

// Some operations only support one non absolute value. Move the
// absolute one to the right hand side for convenience.
staticvoidmoveAbsRight(LinkerScript &s, ExprValue &a, ExprValue &b) {
if (a.sec == nullptr || (a.forceAbsolute && !b.isAbsolute()))
std::swap(a, b);
if (!b.isAbsolute())
 s.recordError(a.loc +
": at least one side of the expression must be absolute");
}

static ExprValue add(LinkerScript &s, ExprValue a, ExprValue b) {
moveAbsRight(s, 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(LinkerScript &s, ExprValue a, ExprValue b) {
moveAbsRight(s, a, b);
return {a.sec, a.forceAbsolute,
 (a.getValue() & b.getValue()) - a.getSecAddr(), a.loc};
}

static ExprValue bitXor(LinkerScript &s, ExprValue a, ExprValue b) {
moveAbsRight(s, a, b);
return {a.sec, a.forceAbsolute,
 (a.getValue() ^ b.getValue()) - a.getSecAddr(), a.loc};
}

static ExprValue bitOr(LinkerScript &s, ExprValue a, ExprValue b) {
moveAbsRight(s, a, b);
return {a.sec, a.forceAbsolute,
 (a.getValue() | b.getValue()) - a.getSecAddr(), a.loc};
}

voidScriptParser::readDynamicList() {
expect("{");
 SmallVector<SymbolVersion, 0> locals;
 SmallVector<SymbolVersion, 0> globals;
std::tie(locals, globals) = readSymbols();
expect(";");

 StringRef tok = peek();
if (tok.size()) {
setError("EOF expected, but got " + tok);
return;
 }
if (!locals.empty()) {
setError("\"local:\" scope not supported in --dynamic-list");
return;
 }

for (SymbolVersion v : globals)
 ctx.arg.dynamicList.push_back(v);
}

voidScriptParser::readVersionScript() {
readVersionScriptCommand();
 StringRef tok = peek();
if (tok.size())
setError("EOF expected, but got " + tok);
}

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

if (atEOF())
setError("unexpected EOF");
while (peek() != "}" && !atEOF()) {
 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 (atEOF())
break;
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 == "OVERWRITE_SECTIONS") {
readOverwriteSections();
 } 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 (tok == "NOCROSSREFS") {
readNoCrossRefs(/*to=*/false);
 } elseif (tok == "NOCROSSREFS_TO") {
readNoCrossRefs(/*to=*/true);
 } elseif (SymbolAssignment *cmd = readAssignment(tok)) {
 ctx.script->sectionCommands.push_back(cmd);
 } else {
setError("unknown directive: " + tok);
 }
 }
}

voidScriptParser::readDefsym() {
if (errCount(ctx))
return;
 SaveAndRestore saved(lexState, State::Expr);
 StringRef name = readName();
expect("=");
 Expr e = readExpr();
if (!atEOF())
setError("EOF expected, but got " + next());
auto *cmd = make<SymbolAssignment>(
 name, e, 0, getCurrentMB().getBufferIdentifier().str());
 ctx.script->sectionCommands.push_back(cmd);
}

voidScriptParser::readNoCrossRefs(bool to) {
expect("(");
 NoCrossRefCommand cmd{{}, to};
while (auto tok = till(")"))
 cmd.outputSections.push_back(unquote(tok));
if (cmd.outputSections.size() < 2)
Warn(ctx) << getCurrentLocation()
 << ": ignored with fewer than 2 output sections";
else
 ctx.script->noCrossRefs.push_back(std::move(cmd));
}

voidScriptParser::addFile(StringRef s) {
if (curBuf.isUnderSysroot && s.starts_with("/")) {
 SmallString<128> pathData;
 StringRef path = (ctx.arg.sysroot + s).toStringRef(pathData);
if (sys::fs::exists(path))
 ctx.driver.addFile(ctx.saver.save(path), /*withLOption=*/false);
else
setError("cannot find " + s + " inside " + ctx.arg.sysroot);
return;
 }

if (s.starts_with("/")) {
// Case 1: s is an absolute path. Just open it.
 ctx.driver.addFile(s, /*withLOption=*/false);
 } elseif (s.starts_with("=")) {
// Case 2: relative to the sysroot.
if (ctx.arg.sysroot.empty())
 ctx.driver.addFile(s.substr(1), /*withLOption=*/false);
else
 ctx.driver.addFile(ctx.saver.save(ctx.arg.sysroot + "/" + s.substr(1)),
/*withLOption=*/false);
 } elseif (s.starts_with("-l")) {
// Case 3: search in the list of library paths.
 ctx.driver.addLibrary(s.substr(2));
 } else {
// Case 4: s is a relative path. Search in the directory of the script file.
 std::string filename = std::string(getCurrentMB().getBufferIdentifier());
 StringRef directory = sys::path::parent_path(filename);
if (!directory.empty()) {
 SmallString<0> path(directory);
sys::path::append(path, s);
if (sys::fs::exists(path)) {
 ctx.driver.addFile(path, /*withLOption=*/false);
return;
 }
 }
// Then search in the current working directory.
if (sys::fs::exists(s)) {
 ctx.driver.addFile(s, /*withLOption=*/false);
 } else {
// Finally, search in the list of library paths.
if (std::optional<std::string> path = findFromSearchPaths(ctx, s))
 ctx.driver.addFile(ctx.saver.save(*path), /*withLOption=*/true);
else
setError("unable to find " + s);
 }
 }
}

voidScriptParser::readAsNeeded() {
expect("(");
bool orig = ctx.arg.asNeeded;
 ctx.arg.asNeeded = true;
while (auto tok = till(")"))
addFile(unquote(tok));
 ctx.arg.asNeeded = orig;
}

voidScriptParser::readEntry() {
// -e <symbol> takes predecence over ENTRY(<symbol>).
expect("(");
 StringRef name = readName();
if (ctx.arg.entry.empty())
 ctx.arg.entry = name;
expect(")");
}

voidScriptParser::readExtern() {
expect("(");
while (auto tok = till(")"))
 ctx.arg.undefined.push_back(unquote(tok));
}

voidScriptParser::readGroup() {
 SaveAndRestore saved(ctx.driver.isInGroup, true);
readInput();
if (!saved.get())
 ++ctx.driver.nextGroupId;
}

voidScriptParser::readInclude() {
 StringRef name = readName();
if (!activeFilenames.insert(name).second) {
setError("there is a cycle in linker script INCLUDEs");
return;
 }

if (std::optional<std::string> path = searchScript(ctx, name)) {
if (std::optional<MemoryBufferRef> mb = readFile(ctx, *path)) {
 buffers.push_back(curBuf);
 curBuf = Buffer(ctx, *mb);
 mbs.push_back(*mb);
 }
return;
 }
setError("cannot find linker script " + name);
}

voidScriptParser::readInput() {
expect("(");
while (auto tok = till(")")) {
if (tok == "AS_NEEDED")
readAsNeeded();
else
addFile(unquote(tok));
 }
}

voidScriptParser::readOutput() {
// -o <file> takes predecence over OUTPUT(<file>).
expect("(");
 StringRef name = readName();
if (ctx.arg.outputFile.empty())
 ctx.arg.outputFile = name;
expect(")");
}

voidScriptParser::readOutputArch() {
// OUTPUT_ARCH is ignored for now.
expect("(");
while (till(")"))
 ;
}

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-avr", {ELF32LEKind, EM_AVR})
 .Case("elf32-iamcu", {ELF32LEKind, EM_IAMCU})
 .Case("elf32-littlearm", {ELF32LEKind, EM_ARM})
 .Case("elf32-bigarm", {ELF32BEKind, EM_ARM})
 .Case("elf32-x86-64", {ELF32LEKind, EM_X86_64})
 .Case("elf64-aarch64", {ELF64LEKind, EM_AARCH64})
 .Case("elf64-littleaarch64", {ELF64LEKind, EM_AARCH64})
 .Case("elf64-bigaarch64", {ELF64BEKind, EM_AARCH64})
 .Case("elf32-powerpc", {ELF32BEKind, EM_PPC})
 .Case("elf32-powerpcle", {ELF32LEKind, 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})
 .Case("elf64-sparc", {ELF64BEKind, EM_SPARCV9})
 .Case("elf32-msp430", {ELF32LEKind, EM_MSP430})
 .Case("elf32-loongarch", {ELF32LEKind, EM_LOONGARCH})
 .Case("elf64-loongarch", {ELF64LEKind, EM_LOONGARCH})
 .Case("elf64-s390", {ELF64BEKind, EM_S390})
 .Cases("elf32-hexagon", "elf32-littlehexagon", {ELF32LEKind, EM_HEXAGON})
 .Default({ELFNoneKind, EM_NONE});
}

// Parse OUTPUT_FORMAT(bfdname) or OUTPUT_FORMAT(default, big, little). Choose
// big if -EB is specified, little if -EL is specified, or default if neither is
// specified.
voidScriptParser::readOutputFormat() {
expect("(");

 StringRef s = readName();
if (!consume(")")) {
expect(",");
 StringRef tmp = readName();
if (ctx.arg.optEB)
 s = tmp;
expect(",");
 tmp = readName();
if (ctx.arg.optEL)
 s = tmp;
consume(")");
 }
// If more than one OUTPUT_FORMAT is specified, only the first is checked.
if (!ctx.arg.bfdname.empty())
return;
 ctx.arg.bfdname = s;

if (s == "binary") {
 ctx.arg.oFormatBinary = true;
return;
 }

if (s.consume_back("-freebsd"))
 ctx.arg.osabi = ELFOSABI_FREEBSD;

std::tie(ctx.arg.ekind, ctx.arg.emachine) = parseBfdName(s);
if (ctx.arg.emachine == EM_NONE)
setError("unknown output format name: " + ctx.arg.bfdname);
if (s == "elf32-ntradlittlemips" || s == "elf32-ntradbigmips")
 ctx.arg.mipsN32Abi = true;
if (ctx.arg.emachine == EM_MSP430)
 ctx.arg.osabi = ELFOSABI_STANDALONE;
}

voidScriptParser::readPhdrs() {
expect("{");
while (auto tok = till("}")) {
 PhdrsCommand cmd;
 cmd.name = tok;
 cmd.type = readPhdrType();

while (!errCount(ctx) && !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());
 }

 ctx.script->phdrsCommands.push_back(cmd);
 }
}

voidScriptParser::readRegionAlias() {
expect("(");
 StringRef alias = readName();
expect(",");
 StringRef name = readName();
expect(")");

if (ctx.script->memoryRegions.count(alias))
setError("redefinition of memory region '" + alias + "'");
if (!ctx.script->memoryRegions.count(name))
setError("memory region '" + name + "' is not defined");
 ctx.script->memoryRegions.insert({alias, ctx.script->memoryRegions[name]});
}

voidScriptParser::readSearchDir() {
expect("(");
 StringRef name = readName();
if (!ctx.arg.nostdlib)
 ctx.arg.searchPaths.push_back(name);
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
SmallVector<SectionCommand *, 0> ScriptParser::readOverlay() {
 Expr addrExpr;
if (!consume(":")) {
 addrExpr = readExpr();
expect(":");
 }
bool noCrossRefs = consume("NOCROSSREFS");
 Expr lmaExpr = consume("AT") ? readParenExpr() : Expr{};
expect("{");

 SmallVector<SectionCommand *, 0> v;
 OutputSection *prev = nullptr;
while (!errCount(ctx) && !consume("}")) {
// VA is the same for all sections. The LMAs are consecutive in memory
// starting from the base load address.
 OutputDesc *osd = readOverlaySectionDescription();
 osd->osec.addrExpr = addrExpr;
if (prev) {
 osd->osec.lmaExpr = [=] { return prev->getLMA() + prev->size; };
 } else {
 osd->osec.lmaExpr = lmaExpr;
// Use first section address for subsequent sections. Ensure the first
// section, even if empty, is not discarded.
 osd->osec.usedInExpression = true;
 addrExpr = [=]() -> ExprValue { return {&osd->osec, false, 0, ""}; };
 }
 v.push_back(osd);
 prev = &osd->osec;
 }
if (!v.empty())
static_cast<OutputDesc *>(v.front())->osec.firstInOverlay = true;
if (consume(">")) {
 StringRef regionName = readName();
for (SectionCommand *od : v)
static_cast<OutputDesc *>(od)->osec.memoryRegionName =
std::string(regionName);
 }
if (noCrossRefs) {
 NoCrossRefCommand cmd;
for (SectionCommand *od : v)
 cmd.outputSections.push_back(static_cast<OutputDesc *>(od)->osec.name);
 ctx.script->noCrossRefs.push_back(std::move(cmd));
 }

// 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 (SectionCommand *cmd : v)
 max = std::max(max, cast<OutputDesc>(cmd)->osec.size);
returnaddrExpr().getValue() + max;
 };
 v.push_back(make<SymbolAssignment>(".", moveDot, 0, getCurrentLocation()));
return v;
}

SectionClassDesc *ScriptParser::readSectionClassDescription() {
 StringRef name = readSectionClassName();
 SectionClassDesc *desc = make<SectionClassDesc>(name);
if (!ctx.script->sectionClasses.insert({CachedHashStringRef(name), desc})
 .second)
setError("section class '" + name + "' already defined");
expect("{");
while (auto tok = till("}")) {
if (tok == "(" || tok == ")") {
setError("expected filename pattern");
 } elseif (peek() == "(") {
 InputSectionDescription *isd = readInputSectionDescription(tok);
if (!isd->classRef.empty())
setError("section class '" + name + "' references class '" +
 isd->classRef + "'");
 desc->sc.commands.push_back(isd);
 }
 }
return desc;
}

StringRef ScriptParser::readSectionClassName() {
expect("(");
 StringRef name = unquote(next());
expect(")");
return name;
}

voidScriptParser::readOverwriteSections() {
expect("{");
while (auto tok = till("}"))
 ctx.script->overwriteSections.push_back(readOutputSectionDescription(tok));
}

voidScriptParser::readSections() {
expect("{");
 SmallVector<SectionCommand *, 0> v;
while (auto tok = till("}")) {
if (tok == "OVERLAY") {
for (SectionCommand *cmd : readOverlay())
 v.push_back(cmd);
continue;
 }
if (tok == "CLASS") {
 v.push_back(readSectionClassDescription());
continue;
 }
if (tok == "INCLUDE") {
readInclude();
continue;
 }

if (SectionCommand *cmd = readAssignment(tok))
 v.push_back(cmd);
else
 v.push_back(readOutputSectionDescription(tok));
 }

// If DATA_SEGMENT_RELRO_END is absent, for sections after DATA_SEGMENT_ALIGN,
// the relro fields should be cleared.
if (!ctx.script->seenRelroEnd)
for (SectionCommand *cmd : v)
if (auto *osd = dyn_cast<OutputDesc>(cmd))
 osd->osec.relro = false;

 ctx.script->sectionCommands.insert(ctx.script->sectionCommands.end(),
 v.begin(), v.end());

if (atEOF() || !consume("INSERT")) {
 ctx.script->hasSectionsCommand = true;
return;
 }

bool isAfter = false;
if (consume("AFTER"))
 isAfter = true;
elseif (!consume("BEFORE"))
setError("expected AFTER/BEFORE, but got '" + next() + "'");
 StringRef where = readName();
 SmallVector<StringRef, 0> names;
for (SectionCommand *cmd : v)
if (auto *os = dyn_cast<OutputDesc>(cmd))
 names.push_back(os->osec.name);
if (!names.empty())
 ctx.script->insertCommands.push_back({std::move(names), isAfter, where});
}

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 = readName();
expect(")");

if (tok.starts_with("elf"))
 ctx.arg.formatBinary = false;
elseif (tok == "binary")
 ctx.arg.formatBinary = true;
else
setError("unknown target: " + tok);
}

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

StringMatcher ScriptParser::readFilePatterns() {
 StringMatcher Matcher;
while (auto tok = till(")"))
 Matcher.addPattern(SingleStringMatcher(tok));
return Matcher;
}

SortSectionPolicy ScriptParser::peekSortKind() {
return StringSwitch<SortSectionPolicy>(peek())
 .Case("REVERSE", SortSectionPolicy::Reverse)
 .Cases("SORT", "SORT_BY_NAME", SortSectionPolicy::Name)
 .Case("SORT_BY_ALIGNMENT", SortSectionPolicy::Alignment)
 .Case("SORT_BY_INIT_PRIORITY", SortSectionPolicy::Priority)
 .Case("SORT_NONE", SortSectionPolicy::None)
 .Default(SortSectionPolicy::Default);
}

SortSectionPolicy ScriptParser::readSortKind() {
 SortSectionPolicy ret = peekSortKind();
if (ret != SortSectionPolicy::Default)
skip();
return ret;
}

// 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.
SmallVector<SectionPattern, 0> ScriptParser::readInputSectionsList() {
 SmallVector<SectionPattern, 0> ret;
while (!errCount(ctx) && peek() != ")") {
 StringMatcher excludeFilePat;
if (consume("EXCLUDE_FILE")) {
expect("(");
 excludeFilePat = readFilePatterns();
 }

 StringMatcher SectionMatcher;
// Break if the next token is ), EXCLUDE_FILE, or SORT*.
while (!errCount(ctx) && peekSortKind() == SortSectionPolicy::Default) {
 StringRef s = peek();
if (s == ")" || s == "EXCLUDE_FILE")
break;
// Detect common mistakes when certain non-wildcard meta characters are
// used without a closing ')'.
if (!s.empty() && strchr("(){}", s[0])) {
skip();
setError("section pattern is expected");
break;
 }
 SectionMatcher.addPattern(readName());
 }

if (!SectionMatcher.empty())
 ret.push_back({std::move(excludeFilePat), std::move(SectionMatcher)});
elseif (excludeFilePat.empty())
break;
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, uint64_t withFlags,
uint64_t withoutFlags) {
auto *cmd =
 make<InputSectionDescription>(filePattern, withFlags, withoutFlags);
expect("(");

while (peek() != ")" && !atEOF()) {
 SortSectionPolicy outer = readSortKind();
 SortSectionPolicy inner = SortSectionPolicy::Default;
 SmallVector<SectionPattern, 0> 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));
 }
expect(")");
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
uint64_t withFlags = 0;
uint64_t withoutFlags = 0;
if (tok == "KEEP") {
expect("(");
if (consume("INPUT_SECTION_FLAGS"))
std::tie(withFlags, withoutFlags) = readInputSectionFlags();

 tok = next();
 InputSectionDescription *cmd;
if (tok == "CLASS")
 cmd = make<InputSectionDescription>(StringRef{}, withFlags, withoutFlags,
readSectionClassName());
else
 cmd = readInputSectionRules(tok, withFlags, withoutFlags);
expect(")");
 ctx.script->keptSections.push_back(cmd);
return cmd;
 }
if (tok == "INPUT_SECTION_FLAGS") {
std::tie(withFlags, withoutFlags) = readInputSectionFlags();
 tok = next();
 }
if (tok == "CLASS")
return make<InputSectionDescription>(StringRef{}, withFlags, withoutFlags,
readSectionClassName());
returnreadInputSectionRules(tok, withFlags, withoutFlags);
}

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

Expr ScriptParser::readAssert() {
expect("(");
 Expr e = readExpr();
expect(",");
 StringRef msg = readName();
expect(")");

return [=, s = ctx.script, &ctx = ctx]() -> ExprValue {
if (!e().getValue())
Err(ctx) << msg;
return s->getDot();
 };
}

#defineECase(X) \
 { #X, X }
constexpr std::pair<constchar *, unsigned> typeMap[] = {
ECase(SHT_PROGBITS), ECase(SHT_NOTE), ECase(SHT_NOBITS),
ECase(SHT_INIT_ARRAY), ECase(SHT_FINI_ARRAY), ECase(SHT_PREINIT_ARRAY),
};
#undef ECase

// Tries to read the special directive for an output section definition which
// can be one of following: "(NOLOAD)", "(COPY)", "(INFO)", "(OVERLAY)", and
// "(TYPE=<value>)".
boolScriptParser::readSectionDirective(OutputSection *cmd, StringRef tok) {
if (tok != "NOLOAD" && tok != "COPY" && tok != "INFO" && tok != "OVERLAY" &&
 tok != "TYPE")
returnfalse;

if (consume("NOLOAD")) {
 cmd->type = SHT_NOBITS;
 cmd->typeIsSet = true;
 } elseif (consume("TYPE")) {
expect("=");
 StringRef value = peek();
auto it = llvm::find_if(typeMap, [=](auto e) { return e.first == value; });
if (it != std::end(typeMap)) {
// The value is a recognized literal SHT_*.
 cmd->type = it->second;
skip();
 } elseif (value.starts_with("SHT_")) {
setError("unknown section type " + value);
 } else {
// Otherwise, read an expression.
 cmd->type = readExpr()().getValue();
 }
 cmd->typeIsSet = 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 (consume("(")) {
// Temporarily set lexState to support TYPE=<value> without spaces.
 SaveAndRestore saved(lexState, State::Expr);
if (readSectionDirective(cmd, peek()))
return;
 cmd->addrExpr = readExpr();
expect(")");
 } else {
 cmd->addrExpr = readExpr();
 }

if (consume("(")) {
 SaveAndRestore saved(lexState, State::Expr);
 StringRef tok = peek();
if (!readSectionDirective(cmd, tok))
setError("unknown section directive: " + tok);
 }
}

static Expr checkAlignment(Ctx &ctx, Expr e, std::string &loc) {
return [=, &ctx] {
uint64_t alignment = std::max((uint64_t)1, e().getValue());
if (!isPowerOf2_64(alignment)) {
ErrAlways(ctx) << loc << ": alignment must be power of 2";
return (uint64_t)1; // Return a dummy value.
 }
return alignment;
 };
}

OutputDesc *ScriptParser::readOverlaySectionDescription() {
 OutputDesc *osd =
 ctx.script->createOutputSection(readName(), getCurrentLocation());
 osd->osec.inOverlay = true;
expect("{");