1	//===- ScriptParser.cpp ---------------------------------------------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// This file contains a recursive-descendent parser for linker scripts.
10	// Parsed results are stored to Config and Script global objects.
11	//
12	//===----------------------------------------------------------------------===//
13
14	#include "ScriptParser.h"
15	#include "Config.h"
16	#include "Driver.h"
17	#include "InputFiles.h"
18	#include "LinkerScript.h"
19	#include "OutputSections.h"
20	#include "ScriptLexer.h"
21	#include "SymbolTable.h"
22	#include "Symbols.h"
23	#include "Target.h"
24	#include "llvm/ADT/SmallString.h"
25	#include "llvm/ADT/StringRef.h"
26	#include "llvm/ADT/StringSwitch.h"
27	#include "llvm/BinaryFormat/ELF.h"
28	#include "llvm/Support/Casting.h"
29	#include "llvm/Support/ErrorHandling.h"
30	#include "llvm/Support/FileSystem.h"
31	#include "llvm/Support/MathExtras.h"
32	#include "llvm/Support/Path.h"
33	#include "llvm/Support/SaveAndRestore.h"
34	#include "llvm/Support/TimeProfiler.h"
35	#include <cassert>
36	#include <optional>
37	#include <vector>
38
39	using namespace llvm;
40	using namespace llvm::ELF;
41	using namespace llvm::support::endian;
42	using namespace lld;
43	using namespace lld::elf;
44
45	namespace {
46	class ScriptParser final : ScriptLexer {
47	public:
48	ScriptParser(Ctx &ctx, MemoryBufferRef mb) : ScriptLexer(ctx, mb), ctx(ctx) {}
49
50	void readLinkerScript();
51	void readVersionScript();
52	void readDynamicList();
53	void readDefsym();
54
55	private:
56	void addFile(StringRef path);
57
58	void readAsNeeded();
59	void readEntry();
60	void readExtern();
61	void readGroup();
62	void readInclude();
63	void readInput();
64	void readMemory();
65	void readOutput();
66	void readOutputArch();
67	void readOutputFormat();
68	void readOverwriteSections();
69	void readPhdrs();
70	void readRegionAlias();
71	void readSearchDir();
72	void readSections();
73	void readTarget();
74	void readVersion();
75	void readVersionScriptCommand();
76	void readNoCrossRefs(bool to);
77
78	StringRef readName();
79	SymbolAssignment *readSymbolAssignment(StringRef name);
80	ByteCommand *readByteCommand(StringRef tok);
81	std::array<uint8_t, 4> readFill();
82	bool readSectionDirective(OutputSection *cmd, StringRef tok);
83	void readSectionAddressType(OutputSection *cmd);
84	OutputDesc *readOverlaySectionDescription();
85	OutputDesc *readOutputSectionDescription(StringRef outSec);
86	SmallVector<SectionCommand *, 0> readOverlay();
87	SectionClassDesc *readSectionClassDescription();
88	StringRef readSectionClassName();
89	SmallVector<StringRef, 0> readOutputSectionPhdrs();
90	std::pair<uint64_t, uint64_t> readInputSectionFlags();
91	InputSectionDescription *readInputSectionDescription(StringRef tok);
92	StringMatcher readFilePatterns();
93	SmallVector<SectionPattern, 0> readInputSectionsList();
94	InputSectionDescription *readInputSectionRules(StringRef filePattern,
95	uint64_t withFlags,
96	uint64_t withoutFlags);
97	unsigned readPhdrType();
98	SortSectionPolicy peekSortKind();
99	SortSectionPolicy readSortKind();
100	SymbolAssignment *readProvideHidden(bool provide, bool hidden);
101	SymbolAssignment *readAssignment(StringRef tok);
102	void readSort();
103	Expr readAssert();
104	Expr readConstant();
105	Expr getPageSize();
106
107	Expr readMemoryAssignment(StringRef, StringRef, StringRef);
108	void readMemoryAttributes(uint32_t &flags, uint32_t &invFlags,
109	uint32_t &negFlags, uint32_t &negInvFlags);
110
111	Expr combine(StringRef op, Expr l, Expr r);
112	Expr readExpr();
113	Expr readExpr1(Expr lhs, int minPrec);
114	StringRef readParenName();
115	Expr readPrimary();
116	Expr readTernary(Expr cond);
117	Expr readParenExpr();
118
119	// For parsing version script.
120	SmallVector<SymbolVersion, 0> readVersionExtern();
121	void readAnonymousDeclaration();
122	void readVersionDeclaration(StringRef verStr);
123
124	std::pair<SmallVector<SymbolVersion, 0>, SmallVector<SymbolVersion, 0>>
125	readSymbols();
126
127	Ctx &ctx;
128
129	// If we are currently parsing a PROVIDE|PROVIDE_HIDDEN command,
130	// then this member is set to the PROVIDE symbol name.
131	std::optional<llvm::StringRef> activeProvideSym;
132	};
133	} // namespace
134
135	static StringRef unquote(StringRef s) {
136	if (s.starts_with(Prefix: "\""))
137	return s.substr(Start: 1, N: s.size() - 2);
138	return s;
139	}
140
141	// Some operations only support one non absolute value. Move the
142	// absolute one to the right hand side for convenience.
143	static void moveAbsRight(LinkerScript &s, ExprValue &a, ExprValue &b) {
144	if (a.sec == nullptr || (a.forceAbsolute && !b.isAbsolute()))
145	std::swap(a&: a, b&: b);
146	if (!b.isAbsolute())
147	s.recordError(msg: a.loc +
148	": at least one side of the expression must be absolute");
149	}
150
151	static ExprValue add(LinkerScript &s, ExprValue a, ExprValue b) {
152	moveAbsRight(s, a, b);
153	return {a.sec, a.forceAbsolute, a.getSectionOffset() + b.getValue(), a.loc};
154	}
155
156	static ExprValue sub(ExprValue a, ExprValue b) {
157	// The distance between two symbols in sections is absolute.
158	if (!a.isAbsolute() && !b.isAbsolute())
159	return a.getValue() - b.getValue();
160	return {a.sec, false, a.getSectionOffset() - b.getValue(), a.loc};
161	}
162
163	static ExprValue bitAnd(LinkerScript &s, ExprValue a, ExprValue b) {
164	moveAbsRight(s, a, b);
165	return {a.sec, a.forceAbsolute,
166	(a.getValue() & b.getValue()) - a.getSecAddr(), a.loc};
167	}
168
169	static ExprValue bitXor(LinkerScript &s, ExprValue a, ExprValue b) {
170	moveAbsRight(s, a, b);
171	return {a.sec, a.forceAbsolute,
172	(a.getValue() ^ b.getValue()) - a.getSecAddr(), a.loc};
173	}
174
175	static ExprValue bitOr(LinkerScript &s, ExprValue a, ExprValue b) {
176	moveAbsRight(s, a, b);
177	return {a.sec, a.forceAbsolute,
178	(a.getValue() | b.getValue()) - a.getSecAddr(), a.loc};
179	}
180
181	void ScriptParser::readDynamicList() {
182	expect(expect: "{");
183	SmallVector<SymbolVersion, 0> locals;
184	SmallVector<SymbolVersion, 0> globals;
185	std::tie(args&: locals, args&: globals) = readSymbols();
186	expect(expect: ";");
187
188	StringRef tok = peek();
189	if (tok.size()) {
190	setError("EOF expected, but got " + tok);
191	return;
192	}
193	if (!locals.empty()) {
194	setError("\"local:\" scope not supported in --dynamic-list");
195	return;
196	}
197
198	for (SymbolVersion v : globals)
199	ctx.arg.dynamicList.push_back(Elt: v);
200	}
201
202	void ScriptParser::readVersionScript() {
203	readVersionScriptCommand();
204	StringRef tok = peek();
205	if (tok.size())
206	setError("EOF expected, but got " + tok);
207	}
208
209	void ScriptParser::readVersionScriptCommand() {
210	if (consume(tok: "{")) {
211	readAnonymousDeclaration();
212	return;
213	}
214
215	if (atEOF())
216	setError("unexpected EOF");
217	while (peek() != "}" && !atEOF()) {
218	StringRef verStr = next();
219	if (verStr == "{") {
220	setError("anonymous version definition is used in "
221	"combination with other version definitions");
222	return;
223	}
224	expect(expect: "{");
225	readVersionDeclaration(verStr);
226	}
227	}
228
229	void ScriptParser::readVersion() {
230	expect(expect: "{");
231	readVersionScriptCommand();
232	expect(expect: "}");
233	}
234
235	void ScriptParser::readLinkerScript() {
236	while (!atEOF()) {
237	StringRef tok = next();
238	if (atEOF())
239	break;
240	if (tok == ";")
241	continue;
242
243	if (tok == "ENTRY") {
244	readEntry();
245	} else if (tok == "EXTERN") {
246	readExtern();
247	} else if (tok == "GROUP") {
248	readGroup();
249	} else if (tok == "INCLUDE") {
250	readInclude();
251	} else if (tok == "INPUT") {
252	readInput();
253	} else if (tok == "MEMORY") {
254	readMemory();
255	} else if (tok == "OUTPUT") {
256	readOutput();
257	} else if (tok == "OUTPUT_ARCH") {
258	readOutputArch();
259	} else if (tok == "OUTPUT_FORMAT") {
260	readOutputFormat();
261	} else if (tok == "OVERWRITE_SECTIONS") {
262	readOverwriteSections();
263	} else if (tok == "PHDRS") {
264	readPhdrs();
265	} else if (tok == "REGION_ALIAS") {
266	readRegionAlias();
267	} else if (tok == "SEARCH_DIR") {
268	readSearchDir();
269	} else if (tok == "SECTIONS") {
270	readSections();
271	} else if (tok == "TARGET") {
272	readTarget();
273	} else if (tok == "VERSION") {
274	readVersion();
275	} else if (tok == "NOCROSSREFS") {
276	readNoCrossRefs(/*to=*/false);
277	} else if (tok == "NOCROSSREFS_TO") {
278	readNoCrossRefs(/*to=*/true);
279	} else if (SymbolAssignment *cmd = readAssignment(tok)) {
280	ctx.script->sectionCommands.push_back(Elt: cmd);
281	} else {
282	setError("unknown directive: " + tok);
283	}
284	}
285	}
286
287	void ScriptParser::readDefsym() {
288	if (errCount(ctx))
289	return;
290	SaveAndRestore saved(lexState, State::Expr);
291	StringRef name = readName();
292	expect(expect: "=");
293	Expr e = readExpr();
294	if (!atEOF())
295	setError("EOF expected, but got " + next());
296	auto *cmd = make<SymbolAssignment>(
297	args&: name, args&: e, args: 0, args: getCurrentMB().getBufferIdentifier().str());
298	ctx.script->sectionCommands.push_back(Elt: cmd);
299	}
300
301	void ScriptParser::readNoCrossRefs(bool to) {
302	expect(expect: "(");
303	NoCrossRefCommand cmd{.outputSections: {}, .toFirst: to};
304	while (auto tok = till(tok: ")"))
305	cmd.outputSections.push_back(Elt: unquote(s: tok));
306	if (cmd.outputSections.size() < 2)
307	Warn(ctx) << getCurrentLocation()
308	<< ": ignored with fewer than 2 output sections";
309	else
310	ctx.script->noCrossRefs.push_back(Elt: std::move(cmd));
311	}
312
313	void ScriptParser::addFile(StringRef s) {
314	if (curBuf.isUnderSysroot && s.starts_with(Prefix: "/")) {
315	SmallString<128> pathData;
316	StringRef path = (ctx.arg.sysroot + s).toStringRef(Out&: pathData);
317	if (sys::fs::exists(Path: path))
318	ctx.driver.addFile(path: ctx.saver.save(S: path), /*withLOption=*/false);
319	else
320	setError("cannot find " + s + " inside " + ctx.arg.sysroot);
321	return;
322	}
323
324	if (s.starts_with(Prefix: "/")) {
325	// Case 1: s is an absolute path. Just open it.
326	ctx.driver.addFile(path: s, /*withLOption=*/false);
327	} else if (s.starts_with(Prefix: "=")) {
328	// Case 2: relative to the sysroot.
329	if (ctx.arg.sysroot.empty())
330	ctx.driver.addFile(path: s.substr(Start: 1), /*withLOption=*/false);
331	else
332	ctx.driver.addFile(path: ctx.saver.save(S: ctx.arg.sysroot + "/" + s.substr(Start: 1)),
333	/*withLOption=*/false);
334	} else if (s.starts_with(Prefix: "-l")) {
335	// Case 3: search in the list of library paths.
336	ctx.driver.addLibrary(name: s.substr(Start: 2));
337	} else {
338	// Case 4: s is a relative path. Search in the directory of the script file.
339	std::string filename = std::string(getCurrentMB().getBufferIdentifier());
340	StringRef directory = sys::path::parent_path(path: filename);
341	if (!directory.empty()) {
342	SmallString<0> path(directory);
343	sys::path::append(path, a: s);
344	if (sys::fs::exists(Path: path)) {
345	ctx.driver.addFile(path, /*withLOption=*/false);
346	return;
347	}
348	}
349	// Then search in the current working directory.
350	if (sys::fs::exists(Path: s)) {
351	ctx.driver.addFile(path: s, /*withLOption=*/false);
352	} else {
353	// Finally, search in the list of library paths.
354	if (std::optional<std::string> path = findFromSearchPaths(ctx, path: s))
355	ctx.driver.addFile(path: ctx.saver.save(S: *path), /*withLOption=*/true);
356	else
357	setError("unable to find " + s);
358	}
359	}
360	}
361
362	void ScriptParser::readAsNeeded() {
363	expect(expect: "(");
364	bool orig = ctx.arg.asNeeded;
365	ctx.arg.asNeeded = true;
366	while (auto tok = till(tok: ")"))
367	addFile(s: unquote(s: tok));
368	ctx.arg.asNeeded = orig;
369	}
370
371	void ScriptParser::readEntry() {
372	// -e <symbol> takes predecence over ENTRY(<symbol>).
373	expect(expect: "(");
374	StringRef name = readName();
375	if (ctx.arg.entry.empty())
376	ctx.arg.entry = name;
377	expect(expect: ")");
378	}
379
380	void ScriptParser::readExtern() {
381	expect(expect: "(");
382	while (auto tok = till(tok: ")"))
383	ctx.arg.undefined.push_back(Elt: unquote(s: tok));
384	}
385
386	void ScriptParser::readGroup() {
387	SaveAndRestore saved(ctx.driver.isInGroup, true);
388	readInput();
389	if (!saved.get())
390	++ctx.driver.nextGroupId;
391	}
392
393	void ScriptParser::readInclude() {
394	StringRef name = readName();
395	if (!activeFilenames.insert(V: name).second) {
396	setError("there is a cycle in linker script INCLUDEs");
397	return;
398	}
399
400	if (std::optional<std::string> path = searchScript(ctx, path: name)) {
401	if (std::optional<MemoryBufferRef> mb = readFile(ctx, path: *path)) {
402	buffers.push_back(Elt: curBuf);
403	curBuf = Buffer(ctx, *mb);
404	mbs.push_back(x: *mb);
405	}
406	return;
407	}
408	setError("cannot find linker script " + name);
409	}
410
411	void ScriptParser::readInput() {
412	expect(expect: "(");
413	while (auto tok = till(tok: ")")) {
414	if (tok == "AS_NEEDED")
415	readAsNeeded();
416	else
417	addFile(s: unquote(s: tok));
418	}
419	}
420
421	void ScriptParser::readOutput() {
422	// -o <file> takes predecence over OUTPUT(<file>).
423	expect(expect: "(");
424	StringRef name = readName();
425	if (ctx.arg.outputFile.empty())
426	ctx.arg.outputFile = name;
427	expect(expect: ")");
428	}
429
430	void ScriptParser::readOutputArch() {
431	// OUTPUT_ARCH is ignored for now.
432	expect(expect: "(");
433	while (till(tok: ")"))
434	;
435	}
436
437	static std::pair<ELFKind, uint16_t> parseBfdName(StringRef s) {
438	return StringSwitch<std::pair<ELFKind, uint16_t>>(s)
439	.Case(S: "elf32-i386", Value: {ELF32LEKind, EM_386})
440	.Case(S: "elf32-avr", Value: {ELF32LEKind, EM_AVR})
441	.Case(S: "elf32-iamcu", Value: {ELF32LEKind, EM_IAMCU})
442	.Case(S: "elf32-littlearm", Value: {ELF32LEKind, EM_ARM})
443	.Case(S: "elf32-bigarm", Value: {ELF32BEKind, EM_ARM})
444	.Case(S: "elf32-x86-64", Value: {ELF32LEKind, EM_X86_64})
445	.Case(S: "elf64-aarch64", Value: {ELF64LEKind, EM_AARCH64})
446	.Case(S: "elf64-littleaarch64", Value: {ELF64LEKind, EM_AARCH64})
447	.Case(S: "elf64-bigaarch64", Value: {ELF64BEKind, EM_AARCH64})
448	.Case(S: "elf32-powerpc", Value: {ELF32BEKind, EM_PPC})
449	.Case(S: "elf32-powerpcle", Value: {ELF32LEKind, EM_PPC})
450	.Case(S: "elf64-powerpc", Value: {ELF64BEKind, EM_PPC64})
451	.Case(S: "elf64-powerpcle", Value: {ELF64LEKind, EM_PPC64})
452	.Case(S: "elf64-x86-64", Value: {ELF64LEKind, EM_X86_64})
453	.Cases(S0: "elf32-tradbigmips", S1: "elf32-bigmips", Value: {ELF32BEKind, EM_MIPS})
454	.Case(S: "elf32-ntradbigmips", Value: {ELF32BEKind, EM_MIPS})
455	.Case(S: "elf32-tradlittlemips", Value: {ELF32LEKind, EM_MIPS})
456	.Case(S: "elf32-ntradlittlemips", Value: {ELF32LEKind, EM_MIPS})
457	.Case(S: "elf64-tradbigmips", Value: {ELF64BEKind, EM_MIPS})
458	.Case(S: "elf64-tradlittlemips", Value: {ELF64LEKind, EM_MIPS})
459	.Case(S: "elf32-littleriscv", Value: {ELF32LEKind, EM_RISCV})
460	.Case(S: "elf64-littleriscv", Value: {ELF64LEKind, EM_RISCV})
461	.Case(S: "elf64-sparc", Value: {ELF64BEKind, EM_SPARCV9})
462	.Case(S: "elf32-msp430", Value: {ELF32LEKind, EM_MSP430})
463	.Case(S: "elf32-loongarch", Value: {ELF32LEKind, EM_LOONGARCH})
464	.Case(S: "elf64-loongarch", Value: {ELF64LEKind, EM_LOONGARCH})
465	.Case(S: "elf64-s390", Value: {ELF64BEKind, EM_S390})
466	.Cases(S0: "elf32-hexagon", S1: "elf32-littlehexagon", Value: {ELF32LEKind, EM_HEXAGON})
467	.Default(Value: {ELFNoneKind, EM_NONE});
468	}
469
470	// Parse OUTPUT_FORMAT(bfdname) or OUTPUT_FORMAT(default, big, little). Choose
471	// big if -EB is specified, little if -EL is specified, or default if neither is
472	// specified.
473	void ScriptParser::readOutputFormat() {
474	expect(expect: "(");
475
476	StringRef s = readName();
477	if (!consume(tok: ")")) {
478	expect(expect: ",");
479	StringRef tmp = readName();
480	if (ctx.arg.optEB)
481	s = tmp;
482	expect(expect: ",");
483	tmp = readName();
484	if (ctx.arg.optEL)
485	s = tmp;
486	consume(tok: ")");
487	}
488	// If more than one OUTPUT_FORMAT is specified, only the first is checked.
489	if (!ctx.arg.bfdname.empty())
490	return;
491	ctx.arg.bfdname = s;
492
493	if (s == "binary") {
494	ctx.arg.oFormatBinary = true;
495	return;
496	}
497
498	if (s.consume_back(Suffix: "-freebsd"))
499	ctx.arg.osabi = ELFOSABI_FREEBSD;
500
501	std::tie(args&: ctx.arg.ekind, args&: ctx.arg.emachine) = parseBfdName(s);
502	if (ctx.arg.emachine == EM_NONE)
503	setError("unknown output format name: " + ctx.arg.bfdname);
504	if (s == "elf32-ntradlittlemips" || s == "elf32-ntradbigmips")
505	ctx.arg.mipsN32Abi = true;
506	if (ctx.arg.emachine == EM_MSP430)
507	ctx.arg.osabi = ELFOSABI_STANDALONE;
508	}
509
510	void ScriptParser::readPhdrs() {
511	expect(expect: "{");
512	while (auto tok = till(tok: "}")) {
513	PhdrsCommand cmd;
514	cmd.name = tok;
515	cmd.type = readPhdrType();
516
517	while (!errCount(ctx) && !consume(tok: ";")) {
518	if (consume(tok: "FILEHDR"))
519	cmd.hasFilehdr = true;
520	else if (consume(tok: "PHDRS"))
521	cmd.hasPhdrs = true;
522	else if (consume(tok: "AT"))
523	cmd.lmaExpr = readParenExpr();
524	else if (consume(tok: "FLAGS"))
525	cmd.flags = readParenExpr()().getValue();
526	else
527	setError("unexpected header attribute: " + next());
528	}
529
530	ctx.script->phdrsCommands.push_back(Elt: cmd);
531	}
532	}
533
534	void ScriptParser::readRegionAlias() {
535	expect(expect: "(");
536	StringRef alias = readName();
537	expect(expect: ",");
538	StringRef name = readName();
539	expect(expect: ")");
540
541	if (ctx.script->memoryRegions.count(Key: alias))
542	setError("redefinition of memory region '" + alias + "'");
543	if (!ctx.script->memoryRegions.count(Key: name))
544	setError("memory region '" + name + "' is not defined");
545	ctx.script->memoryRegions.insert(KV: {alias, ctx.script->memoryRegions[name]});
546	}
547
548	void ScriptParser::readSearchDir() {
549	expect(expect: "(");
550	StringRef name = readName();
551	if (!ctx.arg.nostdlib)
552	ctx.arg.searchPaths.push_back(Elt: name);
553	expect(expect: ")");
554	}
555
556	// This reads an overlay description. Overlays are used to describe output
557	// sections that use the same virtual memory range and normally would trigger
558	// linker's sections sanity check failures.
559	// https://sourceware.org/binutils/docs/ld/Overlay-Description.html#Overlay-Description
560	SmallVector<SectionCommand *, 0> ScriptParser::readOverlay() {
561	Expr addrExpr;
562	if (!consume(tok: ":")) {
563	addrExpr = readExpr();
564	expect(expect: ":");
565	}
566	bool noCrossRefs = consume(tok: "NOCROSSREFS");
567	Expr lmaExpr = consume(tok: "AT") ? readParenExpr() : Expr{};
568	expect(expect: "{");
569
570	SmallVector<SectionCommand *, 0> v;
571	OutputSection *prev = nullptr;
572	while (!errCount(ctx) && !consume(tok: "}")) {
573	// VA is the same for all sections. The LMAs are consecutive in memory
574	// starting from the base load address.
575	OutputDesc *osd = readOverlaySectionDescription();
576	osd->osec.addrExpr = addrExpr;
577	if (prev) {
578	osd->osec.lmaExpr = [=] { return prev->getLMA() + prev->size; };
579	} else {
580	osd->osec.lmaExpr = lmaExpr;
581	// Use first section address for subsequent sections. Ensure the first
582	// section, even if empty, is not discarded.
583	osd->osec.usedInExpression = true;
584	addrExpr = [=]() -> ExprValue { return {&osd->osec, false, 0, ""}; };
585	}
586	v.push_back(Elt: osd);
587	prev = &osd->osec;
588	}
589	if (!v.empty())
590	static_cast<OutputDesc *>(v.front())->osec.firstInOverlay = true;
591	if (consume(tok: ">")) {
592	StringRef regionName = readName();
593	for (SectionCommand *od : v)
594	static_cast<OutputDesc *>(od)->osec.memoryRegionName =
595	std::string(regionName);
596	}
597	if (noCrossRefs) {
598	NoCrossRefCommand cmd;
599	for (SectionCommand *od : v)
600	cmd.outputSections.push_back(Elt: static_cast<OutputDesc *>(od)->osec.name);
601	ctx.script->noCrossRefs.push_back(Elt: std::move(cmd));
602	}
603
604	// According to the specification, at the end of the overlay, the location
605	// counter should be equal to the overlay base address plus size of the
606	// largest section seen in the overlay.
607	// Here we want to create the Dot assignment command to achieve that.
608	Expr moveDot = [=] {
609	uint64_t max = 0;
610	for (SectionCommand *cmd : v)
611	max = std::max(a: max, b: cast<OutputDesc>(Val: cmd)->osec.size);
612	return addrExpr().getValue() + max;
613	};
614	v.push_back(Elt: make<SymbolAssignment>(args: ".", args&: moveDot, args: 0, args: getCurrentLocation()));
615	return v;
616	}
617
618	SectionClassDesc *ScriptParser::readSectionClassDescription() {
619	StringRef name = readSectionClassName();
620	SectionClassDesc *desc = make<SectionClassDesc>(args&: name);
621	if (!ctx.script->sectionClasses.insert(KV: {CachedHashStringRef(name), desc})
622	.second)
623	setError("section class '" + name + "' already defined");
624	expect(expect: "{");
625	while (auto tok = till(tok: "}")) {
626	if (tok == "(" || tok == ")") {
627	setError("expected filename pattern");
628	} else if (peek() == "(") {
629	InputSectionDescription *isd = readInputSectionDescription(tok);
630	if (!isd->classRef.empty())
631	setError("section class '" + name + "' references class '" +
632	isd->classRef + "'");
633	desc->sc.commands.push_back(Elt: isd);
634	}
635	}
636	return desc;
637	}
638
639	StringRef ScriptParser::readSectionClassName() {
640	expect(expect: "(");
641	StringRef name = unquote(s: next());
642	expect(expect: ")");
643	return name;
644	}
645
646	void ScriptParser::readOverwriteSections() {
647	expect(expect: "{");
648	while (auto tok = till(tok: "}"))
649	ctx.script->overwriteSections.push_back(Elt: readOutputSectionDescription(outSec: tok));
650	}
651
652	void ScriptParser::readSections() {
653	expect(expect: "{");
654	SmallVector<SectionCommand *, 0> v;
655	while (auto tok = till(tok: "}")) {
656	if (tok == "OVERLAY") {
657	for (SectionCommand *cmd : readOverlay())
658	v.push_back(Elt: cmd);
659	continue;
660	}
661	if (tok == "CLASS") {
662	v.push_back(Elt: readSectionClassDescription());
663	continue;
664	}
665	if (tok == "INCLUDE") {
666	readInclude();
667	continue;
668	}
669
670	if (SectionCommand *cmd = readAssignment(tok))
671	v.push_back(Elt: cmd);
672	else
673	v.push_back(Elt: readOutputSectionDescription(outSec: tok));
674	}
675
676	// If DATA_SEGMENT_RELRO_END is absent, for sections after DATA_SEGMENT_ALIGN,
677	// the relro fields should be cleared.
678	if (!ctx.script->seenRelroEnd)
679	for (SectionCommand *cmd : v)
680	if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
681	osd->osec.relro = false;
682
683	ctx.script->sectionCommands.insert(I: ctx.script->sectionCommands.end(),
684	From: v.begin(), To: v.end());
685
686	if (atEOF() || !consume(tok: "INSERT")) {
687	ctx.script->hasSectionsCommand = true;
688	return;
689	}
690
691	bool isAfter = false;
692	if (consume(tok: "AFTER"))
693	isAfter = true;
694	else if (!consume(tok: "BEFORE"))
695	setError("expected AFTER/BEFORE, but got '" + next() + "'");
696	StringRef where = readName();
697	SmallVector<StringRef, 0> names;
698	for (SectionCommand *cmd : v)
699	if (auto *os = dyn_cast<OutputDesc>(Val: cmd))
700	names.push_back(Elt: os->osec.name);
701	if (!names.empty())
702	ctx.script->insertCommands.push_back(Elt: {.names: std::move(names), .isAfter: isAfter, .where: where});
703	}
704
705	void ScriptParser::readTarget() {
706	// TARGET(foo) is an alias for "--format foo". Unlike GNU linkers,
707	// we accept only a limited set of BFD names (i.e. "elf" or "binary")
708	// for --format. We recognize only /^elf/ and "binary" in the linker
709	// script as well.
710	expect(expect: "(");
711	StringRef tok = readName();
712	expect(expect: ")");
713
714	if (tok.starts_with(Prefix: "elf"))
715	ctx.arg.formatBinary = false;
716	else if (tok == "binary")
717	ctx.arg.formatBinary = true;
718	else
719	setError("unknown target: " + tok);
720	}
721
722	static int precedence(StringRef op) {
723	return StringSwitch<int>(op)
724	.Cases(S0: "*", S1: "/", S2: "%", Value: 11)
725	.Cases(S0: "+", S1: "-", Value: 10)
726	.Cases(S0: "<<", S1: ">>", Value: 9)
727	.Cases(S0: "<", S1: "<=", S2: ">", S3: ">=", Value: 8)
728	.Cases(S0: "==", S1: "!=", Value: 7)
729	.Case(S: "&", Value: 6)
730	.Case(S: "^", Value: 5)
731	.Case(S: "|", Value: 4)
732	.Case(S: "&&", Value: 3)
733	.Case(S: "||", Value: 2)
734	.Case(S: "?", Value: 1)
735	.Default(Value: -1);
736	}
737
738	StringMatcher ScriptParser::readFilePatterns() {
739	StringMatcher Matcher;
740	while (auto tok = till(tok: ")"))
741	Matcher.addPattern(Matcher: SingleStringMatcher(tok));
742	return Matcher;
743	}
744
745	SortSectionPolicy ScriptParser::peekSortKind() {
746	return StringSwitch<SortSectionPolicy>(peek())
747	.Case(S: "REVERSE", Value: SortSectionPolicy::Reverse)
748	.Cases(S0: "SORT", S1: "SORT_BY_NAME", Value: SortSectionPolicy::Name)
749	.Case(S: "SORT_BY_ALIGNMENT", Value: SortSectionPolicy::Alignment)
750	.Case(S: "SORT_BY_INIT_PRIORITY", Value: SortSectionPolicy::Priority)
751	.Case(S: "SORT_NONE", Value: SortSectionPolicy::None)
752	.Default(Value: SortSectionPolicy::Default);
753	}
754
755	SortSectionPolicy ScriptParser::readSortKind() {
756	SortSectionPolicy ret = peekSortKind();
757	if (ret != SortSectionPolicy::Default)
758	skip();
759	return ret;
760	}
761
762	// Reads SECTIONS command contents in the following form:
763	//
764	// <contents> ::= <elem>*
765	// <elem> ::= <exclude>? <glob-pattern>
766	// <exclude> ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
767	//
768	// For example,
769	//
770	// *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
771	//
772	// is parsed as ".foo", ".bar" with "a.o", and ".baz" with "b.o".
773	// The semantics of that is section .foo in any file, section .bar in
774	// any file but a.o, and section .baz in any file but b.o.
775	SmallVector<SectionPattern, 0> ScriptParser::readInputSectionsList() {
776	SmallVector<SectionPattern, 0> ret;
777	while (!errCount(ctx) && peek() != ")") {
778	StringMatcher excludeFilePat;
779	if (consume(tok: "EXCLUDE_FILE")) {
780	expect(expect: "(");
781	excludeFilePat = readFilePatterns();
782	}
783
784	StringMatcher SectionMatcher;
785	// Break if the next token is ), EXCLUDE_FILE, or SORT*.
786	while (!errCount(ctx) && peekSortKind() == SortSectionPolicy::Default) {
787	StringRef s = peek();
788	if (s == ")" || s == "EXCLUDE_FILE")
789	break;
790	// Detect common mistakes when certain non-wildcard meta characters are
791	// used without a closing ')'.
792	if (!s.empty() && strchr(s: "(){}", c: s[0])) {
793	skip();
794	setError("section pattern is expected");
795	break;
796	}
797	SectionMatcher.addPattern(Matcher: readName());
798	}
799
800	if (!SectionMatcher.empty())
801	ret.push_back(Elt: {std::move(excludeFilePat), std::move(SectionMatcher)});
802	else if (excludeFilePat.empty())
803	break;
804	else
805	setError("section pattern is expected");
806	}
807	return ret;
808	}
809
810	// Reads contents of "SECTIONS" directive. That directive contains a
811	// list of glob patterns for input sections. The grammar is as follows.
812	//
813	// <patterns> ::= <section-list>
814	// | <sort> "(" <section-list> ")"
815	// | <sort> "(" <sort> "(" <section-list> ")" ")"
816	//
817	// <sort> ::= "SORT" | "SORT_BY_NAME" | "SORT_BY_ALIGNMENT"
818	// | "SORT_BY_INIT_PRIORITY" | "SORT_NONE"
819	//
820	// <section-list> is parsed by readInputSectionsList().
821	InputSectionDescription *
822	ScriptParser::readInputSectionRules(StringRef filePattern, uint64_t withFlags,
823	uint64_t withoutFlags) {
824	auto *cmd =
825	make<InputSectionDescription>(args&: filePattern, args&: withFlags, args&: withoutFlags);
826	expect(expect: "(");
827
828	while (peek() != ")" && !atEOF()) {
829	SortSectionPolicy outer = readSortKind();
830	SortSectionPolicy inner = SortSectionPolicy::Default;
831	SmallVector<SectionPattern, 0> v;
832	if (outer != SortSectionPolicy::Default) {
833	expect(expect: "(");
834	inner = readSortKind();
835	if (inner != SortSectionPolicy::Default) {
836	expect(expect: "(");
837	v = readInputSectionsList();
838	expect(expect: ")");
839	} else {
840	v = readInputSectionsList();
841	}
842	expect(expect: ")");
843	} else {
844	v = readInputSectionsList();
845	}
846
847	for (SectionPattern &pat : v) {
848	pat.sortInner = inner;
849	pat.sortOuter = outer;
850	}
851
852	std::move(first: v.begin(), last: v.end(), result: std::back_inserter(x&: cmd->sectionPatterns));
853	}
854	expect(expect: ")");
855	return cmd;
856	}
857
858	InputSectionDescription *
859	ScriptParser::readInputSectionDescription(StringRef tok) {
860	// Input section wildcard can be surrounded by KEEP.
861	// https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
862	uint64_t withFlags = 0;
863	uint64_t withoutFlags = 0;
864	if (tok == "KEEP") {
865	expect(expect: "(");
866	if (consume(tok: "INPUT_SECTION_FLAGS"))
867	std::tie(args&: withFlags, args&: withoutFlags) = readInputSectionFlags();
868
869	tok = next();
870	InputSectionDescription *cmd;
871	if (tok == "CLASS")
872	cmd = make<InputSectionDescription>(args: StringRef{}, args&: withFlags, args&: withoutFlags,
873	args: readSectionClassName());
874	else
875	cmd = readInputSectionRules(filePattern: tok, withFlags, withoutFlags);
876	expect(expect: ")");
877	ctx.script->keptSections.push_back(Elt: cmd);
878	return cmd;
879	}
880	if (tok == "INPUT_SECTION_FLAGS") {
881	std::tie(args&: withFlags, args&: withoutFlags) = readInputSectionFlags();
882	tok = next();
883	}
884	if (tok == "CLASS")
885	return make<InputSectionDescription>(args: StringRef{}, args&: withFlags, args&: withoutFlags,
886	args: readSectionClassName());
887	return readInputSectionRules(filePattern: tok, withFlags, withoutFlags);
888	}
889
890	void ScriptParser::readSort() {
891	expect(expect: "(");
892	expect(expect: "CONSTRUCTORS");
893	expect(expect: ")");
894	}
895
896	Expr ScriptParser::readAssert() {
897	expect(expect: "(");
898	Expr e = readExpr();
899	expect(expect: ",");
900	StringRef msg = readName();
901	expect(expect: ")");
902
903	return [=, s = ctx.script]() -> ExprValue {
904	if (!e().getValue())
905	s->recordError(msg);
906	return s->getDot();
907	};
908	}
909
910	#define ECase(X) \
911	{ #X, X }
912	constexpr std::pair<const char *, unsigned> typeMap[] = {
913	ECase(SHT_PROGBITS), ECase(SHT_NOTE), ECase(SHT_NOBITS),
914	ECase(SHT_INIT_ARRAY), ECase(SHT_FINI_ARRAY), ECase(SHT_PREINIT_ARRAY),
915	};
916	#undef ECase
917
918	// Tries to read the special directive for an output section definition which
919	// can be one of following: "(NOLOAD)", "(COPY)", "(INFO)", "(OVERLAY)", and
920	// "(TYPE=<value>)".
921	bool ScriptParser::readSectionDirective(OutputSection *cmd, StringRef tok) {
922	if (tok != "NOLOAD" && tok != "COPY" && tok != "INFO" && tok != "OVERLAY" &&
923	tok != "TYPE")
924	return false;
925
926	if (consume(tok: "NOLOAD")) {
927	cmd->type = SHT_NOBITS;
928	cmd->typeIsSet = true;
929	} else if (consume(tok: "TYPE")) {
930	expect(expect: "=");
931	StringRef value = peek();
932	auto it = llvm::find_if(Range: typeMap, P: [=](auto e) { return e.first == value; });
933	if (it != std::end(arr: typeMap)) {
934	// The value is a recognized literal SHT_*.
935	cmd->type = it->second;
936	skip();
937	} else if (value.starts_with(Prefix: "SHT_")) {
938	setError("unknown section type " + value);
939	} else {
940	// Otherwise, read an expression.
941	cmd->type = readExpr()().getValue();
942	}
943	cmd->typeIsSet = true;
944	} else {
945	skip(); // This is "COPY", "INFO" or "OVERLAY".
946	cmd->nonAlloc = true;
947	}
948	expect(expect: ")");
949	return true;
950	}
951
952	// Reads an expression and/or the special directive for an output
953	// section definition. Directive is one of following: "(NOLOAD)",
954	// "(COPY)", "(INFO)" or "(OVERLAY)".
955	//
956	// An output section name can be followed by an address expression
957	// and/or directive. This grammar is not LL(1) because "(" can be
958	// interpreted as either the beginning of some expression or beginning
959	// of directive.
960	//
961	// https://sourceware.org/binutils/docs/ld/Output-Section-Address.html
962	// https://sourceware.org/binutils/docs/ld/Output-Section-Type.html
963	void ScriptParser::readSectionAddressType(OutputSection *cmd) {
964	if (consume(tok: "(")) {
965	// Temporarily set lexState to support TYPE=<value> without spaces.
966	SaveAndRestore saved(lexState, State::Expr);
967	if (readSectionDirective(cmd, tok: peek()))
968	return;
969	cmd->addrExpr = readExpr();
970	expect(expect: ")");
971	} else {
972	cmd->addrExpr = readExpr();
973	}
974
975	if (consume(tok: "(")) {
976	SaveAndRestore saved(lexState, State::Expr);
977	StringRef tok = peek();
978	if (!readSectionDirective(cmd, tok))
979	setError("unknown section directive: " + tok);
980	}
981	}
982
983	static Expr checkAlignment(Ctx &ctx, Expr e, std::string &loc) {
984	return [=, &ctx] {
985	uint64_t alignment = std::max(a: (uint64_t)1, b: e().getValue());
986	if (!isPowerOf2_64(Value: alignment)) {
987	ErrAlways(ctx) << loc << ": alignment must be power of 2";
988	return (uint64_t)1; // Return a dummy value.
989	}
990	return alignment;
991	};
992	}
993
994	OutputDesc *ScriptParser::readOverlaySectionDescription() {
995	OutputDesc *osd =
996	ctx.script->createOutputSection(name: readName(), location: getCurrentLocation());
997	osd->osec.inOverlay = true;
998	expect(expect: "{");
999	while (auto tok = till(tok: "}"))
1000	osd->osec.commands.push_back(Elt: readInputSectionDescription(tok));
1001	osd->osec.phdrs = readOutputSectionPhdrs();
1002	return osd;
1003	}
1004
1005	OutputDesc *ScriptParser::readOutputSectionDescription(StringRef outSec) {
1006	OutputDesc *cmd =
1007	ctx.script->createOutputSection(name: unquote(s: outSec), location: getCurrentLocation());
1008	OutputSection *osec = &cmd->osec;
1009	// Maybe relro. Will reset to false if DATA_SEGMENT_RELRO_END is absent.
1010	osec->relro = ctx.script->seenDataAlign && !ctx.script->seenRelroEnd;
1011
1012	size_t symbolsReferenced = ctx.script->referencedSymbols.size();
1013
1014	if (peek() != ":")
1015	readSectionAddressType(cmd: osec);
1016	expect(expect: ":");
1017
1018	std::string location = getCurrentLocation();
1019	if (consume(tok: "AT"))
1020	osec->lmaExpr = readParenExpr();
1021	if (consume(tok: "ALIGN"))
1022	osec->alignExpr = checkAlignment(ctx, e: readParenExpr(), loc&: location);
1023	if (consume(tok: "SUBALIGN"))
1024	osec->subalignExpr = checkAlignment(ctx, e: readParenExpr(), loc&: location);
1025
1026	// Parse constraints.
1027	if (consume(tok: "ONLY_IF_RO"))
1028	osec->constraint = ConstraintKind::ReadOnly;
1029	if (consume(tok: "ONLY_IF_RW"))
1030	osec->constraint = ConstraintKind::ReadWrite;
1031	expect(expect: "{");
1032
1033	while (auto tok = till(tok: "}")) {
1034	if (tok == ";") {
1035	// Empty commands are allowed. Do nothing here.
1036	} else if (SymbolAssignment *assign = readAssignment(tok)) {
1037	osec->commands.push_back(Elt: assign);
1038	} else if (ByteCommand *data = readByteCommand(tok)) {
1039	osec->commands.push_back(Elt: data);
1040	} else if (tok == "CONSTRUCTORS") {
1041	// CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
1042	// by name. This is for very old file formats such as ECOFF/XCOFF.
1043	// For ELF, we should ignore.
1044	} else if (tok == "FILL") {
1045	// We handle the FILL command as an alias for =fillexp section attribute,
1046	// which is different from what GNU linkers do.
1047	// https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
1048	if (peek() != "(")
1049	setError("( expected, but got " + peek());
1050	osec->filler = readFill();
1051	} else if (tok == "SORT") {
1052	readSort();
1053	} else if (tok == "INCLUDE") {
1054	readInclude();
1055	} else if (tok == "(" || tok == ")") {
1056	setError("expected filename pattern");
1057	} else if (peek() == "(") {
1058	osec->commands.push_back(Elt: readInputSectionDescription(tok));
1059	} else {
1060	// We have a file name and no input sections description. It is not a
1061	// commonly used syntax, but still acceptable. In that case, all sections
1062	// from the file will be included.
1063	// FIXME: GNU ld permits INPUT_SECTION_FLAGS to be used here. We do not
1064	// handle this case here as it will already have been matched by the
1065	// case above.
1066	auto *isd = make<InputSectionDescription>(args&: tok);
1067	isd->sectionPatterns.push_back(Elt: {{}, StringMatcher("*")});
1068	osec->commands.push_back(Elt: isd);
1069	}
1070	}
1071
1072	if (consume(tok: ">"))
1073	osec->memoryRegionName = std::string(readName());
1074
1075	if (consume(tok: "AT")) {
1076	expect(expect: ">");
1077	osec->lmaRegionName = std::string(readName());
1078	}
1079
1080	if (osec->lmaExpr && !osec->lmaRegionName.empty())
1081	ErrAlways(ctx) << "section can't have both LMA and a load region";
1082
1083	osec->phdrs = readOutputSectionPhdrs();
1084
1085	if (peek() == "=" || peek().starts_with(Prefix: "=")) {
1086	lexState = State::Expr;
1087	consume(tok: "=");
1088	osec->filler = readFill();
1089	lexState = State::Script;
1090	}
1091
1092	// Consume optional comma following output section command.
1093	consume(tok: ",");
1094
1095	if (ctx.script->referencedSymbols.size() > symbolsReferenced)
1096	osec->expressionsUseSymbols = true;
1097	return cmd;
1098	}
1099
1100	// Reads a `=<fillexp>` expression and returns its value as a big-endian number.
1101	// https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
1102	// We do not support using symbols in such expressions.
1103	//
1104	// When reading a hexstring, ld.bfd handles it as a blob of arbitrary
1105	// size, while ld.gold always handles it as a 32-bit big-endian number.
1106	// We are compatible with ld.gold because it's easier to implement.
1107	// Also, we require that expressions with operators must be wrapped into
1108	// round brackets. We did it to resolve the ambiguity when parsing scripts like:
1109	// SECTIONS { .foo : { ... } =120+3 /DISCARD/ : { ... } }
1110	std::array<uint8_t, 4> ScriptParser::readFill() {
1111	uint64_t value = readPrimary()().val;
1112	if (value > UINT32_MAX)
1113	setError("filler expression result does not fit 32-bit: 0x" +
1114	Twine::utohexstr(Val: value));
1115
1116	std::array<uint8_t, 4> buf;
1117	write32be(P: buf.data(), V: (uint32_t)value);
1118	return buf;
1119	}
1120
1121	SymbolAssignment *ScriptParser::readProvideHidden(bool provide, bool hidden) {
1122	expect(expect: "(");
1123	StringRef name = readName(), eq = peek();
1124	if (eq != "=") {
1125	setError("= expected, but got " + next());
1126	while (till(tok: ")"))
1127	;
1128	return nullptr;
1129	}
1130	llvm::SaveAndRestore saveActiveProvideSym(activeProvideSym);
1131	if (provide)
1132	activeProvideSym = name;
1133	SymbolAssignment *cmd = readSymbolAssignment(name);
1134	cmd->provide = provide;
1135	cmd->hidden = hidden;
1136	expect(expect: ")");
1137	return cmd;
1138	}
1139
1140	// Replace whitespace sequence (including \n) with one single space. The output
1141	// is used by -Map.
1142	static void squeezeSpaces(std::string &str) {
1143	char prev = '\0';
1144	auto it = str.begin();
1145	for (char c : str)
1146	if (!isSpace(C: c) || (c = ' ') != prev)
1147	*it++ = prev = c;
1148	str.erase(first: it, last: str.end());
1149	}
1150
1151	SymbolAssignment *ScriptParser::readAssignment(StringRef tok) {
1152	// Assert expression returns Dot, so this is equal to ".=."
1153	if (tok == "ASSERT")
1154	return make<SymbolAssignment>(args: ".", args: readAssert(), args: 0, args: getCurrentLocation());
1155
1156	const char *oldS = prevTok.data();
1157	SymbolAssignment *cmd = nullptr;
1158	bool savedSeenRelroEnd = ctx.script->seenRelroEnd;
1159	const StringRef op = peek();
1160	{
1161	SaveAndRestore saved(lexState, State::Expr);
1162	if (op.starts_with(Prefix: "=")) {
1163	// Support = followed by an expression without whitespace.
1164	cmd = readSymbolAssignment(name: unquote(s: tok));
1165	} else if ((op.size() == 2 && op[1] == '=' && strchr(s: "+-*/&^|", c: op[0])) ||
1166	op == "<<=" || op == ">>=") {
1167	cmd = readSymbolAssignment(name: unquote(s: tok));
1168	} else if (tok == "PROVIDE") {
1169	cmd = readProvideHidden(provide: true, hidden: false);
1170	} else if (tok == "HIDDEN") {
1171	cmd = readProvideHidden(provide: false, hidden: true);
1172	} else if (tok == "PROVIDE_HIDDEN") {
1173	cmd = readProvideHidden(provide: true, hidden: true);
1174	}
1175	}
1176
1177	if (cmd) {
1178	cmd->dataSegmentRelroEnd = !savedSeenRelroEnd && ctx.script->seenRelroEnd;
1179	cmd->commandString = StringRef(oldS, curTok.data() - oldS).str();
1180	squeezeSpaces(str&: cmd->commandString);
1181	expect(expect: ";");
1182	}
1183	return cmd;
1184	}
1185
1186	StringRef ScriptParser::readName() { return unquote(s: next()); }
1187
1188	SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef name) {
1189	StringRef op = next();
1190	assert(op == "=" || op == "*=" || op == "/=" || op == "+=" || op == "-=" ||
1191	op == "&=" || op == "^=" || op == "|=" || op == "<<=" || op == ">>=");
1192	// Note: GNU ld does not support %=.
1193	Expr e = readExpr();
1194	if (op != "=") {
1195	std::string loc = getCurrentLocation();
1196	e = [=, s = ctx.script, c = op[0], &ctx = ctx]() -> ExprValue {
1197	ExprValue lhs = s->getSymbolValue(name, loc);
1198	switch (c) {
1199	case '*':
1200	return lhs.getValue() * e().getValue();
1201	case '/':
1202	if (uint64_t rv = e().getValue())
1203	return lhs.getValue() / rv;
1204	ErrAlways(ctx) << loc << ": division by zero";
1205	return 0;
1206	case '+':
1207	return add(s&: *s, a: lhs, b: e());
1208	case '-':
1209	return sub(a: lhs, b: e());
1210	case '<':
1211	return lhs.getValue() << e().getValue() % 64;
1212	case '>':
1213	return lhs.getValue() >> e().getValue() % 64;
1214	case '&':
1215	return lhs.getValue() & e().getValue();
1216	case '^':
1217	return lhs.getValue() ^ e().getValue();
1218	case '|':
1219	return lhs.getValue() | e().getValue();
1220	default:
1221	llvm_unreachable("");
1222	}
1223	};
1224	}
1225	return make<SymbolAssignment>(args&: name, args&: e, args: ctx.scriptSymOrderCounter++,
1226	args: getCurrentLocation());
1227	}
1228
1229	// This is an operator-precedence parser to parse a linker
1230	// script expression.
1231	Expr ScriptParser::readExpr() {
1232	// Our lexer is context-aware. Set the in-expression bit so that
1233	// they apply different tokenization rules.
1234	SaveAndRestore saved(lexState, State::Expr);
1235	Expr e = readExpr1(lhs: readPrimary(), minPrec: 0);
1236	return e;
1237	}
1238
1239	Expr ScriptParser::combine(StringRef op, Expr l, Expr r) {
1240	if (op == "+")
1241	return [=, s = ctx.script] { return add(s&: *s, a: l(), b: r()); };
1242	if (op == "-")
1243	return [=] { return sub(a: l(), b: r()); };
1244	if (op == "*")
1245	return [=] { return l().getValue() * r().getValue(); };
1246	if (op == "/") {
1247	std::string loc = getCurrentLocation();
1248	return [=, &ctx = ctx]() -> uint64_t {
1249	if (uint64_t rv = r().getValue())
1250	return l().getValue() / rv;
1251	ErrAlways(ctx) << loc << ": division by zero";
1252	return 0;
1253	};
1254	}
1255	if (op == "%") {
1256	std::string loc = getCurrentLocation();
1257	return [=, &ctx = ctx]() -> uint64_t {
1258	if (uint64_t rv = r().getValue())
1259	return l().getValue() % rv;
1260	ErrAlways(ctx) << loc << ": modulo by zero";
1261	return 0;
1262	};
1263	}
1264	if (op == "<<")
1265	return [=] { return l().getValue() << r().getValue() % 64; };
1266	if (op == ">>")
1267	return [=] { return l().getValue() >> r().getValue() % 64; };
1268	if (op == "<")
1269	return [=] { return l().getValue() < r().getValue(); };
1270	if (op == ">")
1271	return [=] { return l().getValue() > r().getValue(); };
1272	if (op == ">=")
1273	return [=] { return l().getValue() >= r().getValue(); };
1274	if (op == "<=")
1275	return [=] { return l().getValue() <= r().getValue(); };
1276	if (op == "==")
1277	return [=] { return l().getValue() == r().getValue(); };
1278	if (op == "!=")
1279	return [=] { return l().getValue() != r().getValue(); };
1280	if (op == "||")
1281	return [=] { return l().getValue() || r().getValue(); };
1282	if (op == "&&")
1283	return [=] { return l().getValue() && r().getValue(); };
1284	if (op == "&")
1285	return [=, s = ctx.script] { return bitAnd(s&: *s, a: l(), b: r()); };
1286	if (op == "^")
1287	return [=, s = ctx.script] { return bitXor(s&: *s, a: l(), b: r()); };
1288	if (op == "|")
1289	return [=, s = ctx.script] { return bitOr(s&: *s, a: l(), b: r()); };
1290	llvm_unreachable("invalid operator");
1291	}
1292
1293	// This is a part of the operator-precedence parser. This function
1294	// assumes that the remaining token stream starts with an operator.
1295	Expr ScriptParser::readExpr1(Expr lhs, int minPrec) {
1296	while (!atEOF() && !errCount(ctx)) {
1297	// Read an operator and an expression.
1298	StringRef op1 = peek();
1299	if (precedence(op: op1) < minPrec)
1300	break;
1301	skip();
1302	if (op1 == "?")
1303	return readTernary(cond: lhs);
1304	Expr rhs = readPrimary();
1305
1306	// Evaluate the remaining part of the expression first if the
1307	// next operator has greater precedence than the previous one.
1308	// For example, if we have read "+" and "3", and if the next
1309	// operator is "*", then we'll evaluate 3 * ... part first.
1310	while (!atEOF()) {
1311	StringRef op2 = peek();
1312	if (precedence(op: op2) <= precedence(op: op1))
1313	break;
1314	rhs = readExpr1(lhs: rhs, minPrec: precedence(op: op2));
1315	}
1316
1317	lhs = combine(op: op1, l: lhs, r: rhs);
1318	}
1319	return lhs;
1320	}
1321
1322	Expr ScriptParser::getPageSize() {
1323	std::string location = getCurrentLocation();
1324	return [=, &ctx = this->ctx]() -> uint64_t {
1325	if (ctx.target)
1326	return ctx.arg.commonPageSize;
1327	ErrAlways(ctx) << location << ": unable to calculate page size";
1328	return 4096; // Return a dummy value.
1329	};
1330	}
1331
1332	Expr ScriptParser::readConstant() {
1333	StringRef s = readParenName();
1334	if (s == "COMMONPAGESIZE")
1335	return getPageSize();
1336	if (s == "MAXPAGESIZE")
1337	return [&ctx = this->ctx] { return ctx.arg.maxPageSize; };
1338	setError("unknown constant: " + s);
1339	return [] { return 0; };
1340	}
1341
1342	// Parses Tok as an integer. It recognizes hexadecimal (prefixed with
1343	// "0x" or suffixed with "H") and decimal numbers. Decimal numbers may
1344	// have "K" (Ki) or "M" (Mi) suffixes.
1345	static std::optional<uint64_t> parseInt(StringRef tok) {
1346	// Hexadecimal
1347	uint64_t val;
1348	if (tok.starts_with_insensitive(Prefix: "0x")) {
1349	if (!to_integer(S: tok.substr(Start: 2), Num&: val, Base: 16))
1350	return std::nullopt;
1351	return val;
1352	}
1353	if (tok.ends_with_insensitive(Suffix: "H")) {
1354	if (!to_integer(S: tok.drop_back(), Num&: val, Base: 16))
1355	return std::nullopt;
1356	return val;
1357	}
1358
1359	// Decimal
1360	if (tok.ends_with_insensitive(Suffix: "K")) {
1361	if (!to_integer(S: tok.drop_back(), Num&: val, Base: 10))
1362	return std::nullopt;
1363	return val * 1024;
1364	}
1365	if (tok.ends_with_insensitive(Suffix: "M")) {
1366	if (!to_integer(S: tok.drop_back(), Num&: val, Base: 10))
1367	return std::nullopt;
1368	return val * 1024 * 1024;
1369	}
1370	if (!to_integer(S: tok, Num&: val, Base: 10))
1371	return std::nullopt;
1372	return val;
1373	}
1374
1375	ByteCommand *ScriptParser::readByteCommand(StringRef tok) {
1376	int size = StringSwitch<int>(tok)
1377	.Case(S: "BYTE", Value: 1)
1378	.Case(S: "SHORT", Value: 2)
1379	.Case(S: "LONG", Value: 4)
1380	.Case(S: "QUAD", Value: 8)
1381	.Default(Value: -1);
1382	if (size == -1)
1383	return nullptr;
1384
1385	const char *oldS = prevTok.data();
1386	Expr e = readParenExpr();
1387	std::string commandString = StringRef(oldS, curBuf.s.data() - oldS).str();
1388	squeezeSpaces(str&: commandString);
1389	return make<ByteCommand>(args&: e, args&: size, args: std::move(commandString));
1390	}
1391
1392	static std::optional<uint64_t> parseFlag(StringRef tok) {
1393	if (std::optional<uint64_t> asInt = parseInt(tok))
1394	return asInt;
1395	#define CASE_ENT(enum) #enum, ELF::enum
1396	return StringSwitch<std::optional<uint64_t>>(tok)
1397	.Case(CASE_ENT(SHF_WRITE))
1398	.Case(CASE_ENT(SHF_ALLOC))
1399	.Case(CASE_ENT(SHF_EXECINSTR))
1400	.Case(CASE_ENT(SHF_MERGE))
1401	.Case(CASE_ENT(SHF_STRINGS))
1402	.Case(CASE_ENT(SHF_INFO_LINK))
1403	.Case(CASE_ENT(SHF_LINK_ORDER))
1404	.Case(CASE_ENT(SHF_OS_NONCONFORMING))
1405	.Case(CASE_ENT(SHF_GROUP))
1406	.Case(CASE_ENT(SHF_TLS))
1407	.Case(CASE_ENT(SHF_COMPRESSED))
1408	.Case(CASE_ENT(SHF_EXCLUDE))
1409	.Case(CASE_ENT(SHF_ARM_PURECODE))
1410	.Case(CASE_ENT(SHF_AARCH64_PURECODE))
1411	.Default(Value: std::nullopt);
1412	#undef CASE_ENT
1413	}
1414
1415	// Reads the '(' <flags> ')' list of section flags in
1416	// INPUT_SECTION_FLAGS '(' <flags> ')' in the
1417	// following form:
1418	// <flags> ::= <flag>
1419	// | <flags> & flag
1420	// <flag> ::= Recognized Flag Name, or Integer value of flag.
1421	// If the first character of <flag> is a ! then this means without flag,
1422	// otherwise with flag.
1423	// Example: SHF_EXECINSTR & !SHF_WRITE means with flag SHF_EXECINSTR and
1424	// without flag SHF_WRITE.
1425	std::pair<uint64_t, uint64_t> ScriptParser::readInputSectionFlags() {
1426	uint64_t withFlags = 0;
1427	uint64_t withoutFlags = 0;
1428	expect(expect: "(");
1429	while (!errCount(ctx)) {
1430	StringRef tok = readName();
1431	bool without = tok.consume_front(Prefix: "!");
1432	if (std::optional<uint64_t> flag = parseFlag(tok)) {
1433	if (without)
1434	withoutFlags |= *flag;
1435	else
1436	withFlags |= *flag;
1437	} else {
1438	setError("unrecognised flag: " + tok);
1439	}
1440	if (consume(tok: ")"))
1441	break;
1442	if (!consume(tok: "&")) {
1443	next();
1444	setError("expected & or )");
1445	}
1446	}
1447	return std::make_pair(x&: withFlags, y&: withoutFlags);
1448	}
1449
1450	StringRef ScriptParser::readParenName() {
1451	expect(expect: "(");
1452	auto saved = std::exchange(obj&: lexState, new_val: State::Script);
1453	StringRef name = readName();
1454	lexState = saved;
1455	expect(expect: ")");
1456	return name;
1457	}
1458
1459	static void checkIfExists(LinkerScript &script, const OutputSection &osec,
1460	StringRef location) {
1461	if (osec.location.empty() && script.errorOnMissingSection)
1462	script.recordError(msg: location + ": undefined section " + osec.name);
1463	}
1464
1465	static bool isValidSymbolName(StringRef s) {
1466	auto valid = [](char c) {
1467	return isAlnum(C: c) || c == '$' || c == '.' || c == '_';
1468	};
1469	return !s.empty() && !isDigit(C: s[0]) && llvm::all_of(Range&: s, P: valid);
1470	}
1471
1472	Expr ScriptParser::readPrimary() {
1473	if (peek() == "(")
1474	return readParenExpr();
1475
1476	if (consume(tok: "~")) {
1477	Expr e = readPrimary();
1478	return [=] { return ~e().getValue(); };
1479	}
1480	if (consume(tok: "!")) {
1481	Expr e = readPrimary();
1482	return [=] { return !e().getValue(); };
1483	}
1484	if (consume(tok: "-")) {
1485	Expr e = readPrimary();
1486	return [=] { return -e().getValue(); };
1487	}
1488	if (consume(tok: "+"))
1489	return readPrimary();
1490
1491	StringRef tok = next();
1492	std::string location = getCurrentLocation();
1493
1494	// Built-in functions are parsed here.
1495	// https://sourceware.org/binutils/docs/ld/Builtin-Functions.html.
1496	if (tok == "ABSOLUTE") {
1497	Expr inner = readParenExpr();
1498	return [=] {
1499	ExprValue i = inner();
1500	i.forceAbsolute = true;
1501	return i;
1502	};
1503	}
1504	if (tok == "ADDR") {
1505	StringRef name = readParenName();
1506	OutputSection *osec = &ctx.script->getOrCreateOutputSection(name)->osec;
1507	osec->usedInExpression = true;
1508	return [=, s = ctx.script]() -> ExprValue {
1509	checkIfExists(script&: *s, osec: *osec, location);
1510	return {osec, false, 0, location};
1511	};
1512	}
1513	if (tok == "ALIGN") {
1514	expect(expect: "(");
1515	Expr e = readExpr();
1516	if (consume(tok: ")")) {
1517	e = checkAlignment(ctx, e, loc&: location);
1518	return [=, s = ctx.script] {
1519	return alignToPowerOf2(Value: s->getDot(), Align: e().getValue());
1520	};
1521	}
1522	expect(expect: ",");
1523	Expr e2 = checkAlignment(ctx, e: readExpr(), loc&: location);
1524	expect(expect: ")");
1525	return [=] {
1526	ExprValue v = e();
1527	v.alignment = e2().getValue();
1528	return v;
1529	};
1530	}
1531	if (tok == "ALIGNOF") {
1532	StringRef name = readParenName();
1533	OutputSection *osec = &ctx.script->getOrCreateOutputSection(name)->osec;
1534	return [=, s = ctx.script] {
1535	checkIfExists(script&: *s, osec: *osec, location);
1536	return osec->addralign;
1537	};
1538	}
1539	if (tok == "ASSERT")
1540	return readAssert();
1541	if (tok == "CONSTANT")
1542	return readConstant();
1543	if (tok == "DATA_SEGMENT_ALIGN") {
1544	expect(expect: "(");
1545	Expr e = readExpr();
1546	expect(expect: ",");
1547	readExpr();
1548	expect(expect: ")");
1549	ctx.script->seenDataAlign = true;
1550	return [=, s = ctx.script] {
1551	uint64_t align = std::max(a: uint64_t(1), b: e().getValue());
1552	return (s->getDot() + align - 1) & -align;
1553	};
1554	}
1555	if (tok == "DATA_SEGMENT_END") {
1556	expect(expect: "(");
1557	expect(expect: ".");
1558	expect(expect: ")");
1559	return [s = ctx.script] { return s->getDot(); };
1560	}
1561	if (tok == "DATA_SEGMENT_RELRO_END") {
1562	// GNU linkers implements more complicated logic to handle
1563	// DATA_SEGMENT_RELRO_END. We instead ignore the arguments and
1564	// just align to the next page boundary for simplicity.
1565	expect(expect: "(");
1566	readExpr();
1567	expect(expect: ",");
1568	readExpr();
1569	expect(expect: ")");
1570	ctx.script->seenRelroEnd = true;
1571	return [&ctx = this->ctx] {
1572	return alignToPowerOf2(Value: ctx.script->getDot(), Align: ctx.arg.maxPageSize);
1573	};
1574	}
1575	if (tok == "DEFINED") {
1576	StringRef name = readParenName();
1577	// Return 1 if s is defined. If the definition is only found in a linker
1578	// script, it must happen before this DEFINED.
1579	auto order = ctx.scriptSymOrderCounter++;
1580	return [=, &ctx = this->ctx] {
1581	Symbol *s = ctx.symtab->find(name);
1582	return s && s->isDefined() && ctx.scriptSymOrder.lookup(Val: s) < order ? 1
1583	: 0;
1584	};
1585	}
1586	if (tok == "LENGTH") {
1587	StringRef name = readParenName();
1588	if (ctx.script->memoryRegions.count(Key: name) == 0) {
1589	setError("memory region not defined: " + name);
1590	return [] { return 0; };
1591	}
1592	return ctx.script->memoryRegions[name]->length;
1593	}
1594	if (tok == "LOADADDR") {
1595	StringRef name = readParenName();
1596	OutputSection *osec = &ctx.script->getOrCreateOutputSection(name)->osec;
1597	osec->usedInExpression = true;
1598	return [=, s = ctx.script] {
1599	checkIfExists(script&: *s, osec: *osec, location);
1600	return osec->getLMA();
1601	};
1602	}
1603	if (tok == "LOG2CEIL") {
1604	expect(expect: "(");
1605	Expr a = readExpr();
1606	expect(expect: ")");
1607	return [=] {
1608	// LOG2CEIL(0) is defined to be 0.
1609	return llvm::Log2_64_Ceil(Value: std::max(a: a().getValue(), UINT64_C(1)));
1610	};
1611	}
1612	if (tok == "MAX" || tok == "MIN") {
1613	expect(expect: "(");
1614	Expr a = readExpr();
1615	expect(expect: ",");
1616	Expr b = readExpr();
1617	expect(expect: ")");
1618	if (tok == "MIN")
1619	return [=] { return std::min(a: a().getValue(), b: b().getValue()); };
1620	return [=] { return std::max(a: a().getValue(), b: b().getValue()); };
1621	}
1622	if (tok == "ORIGIN") {
1623	StringRef name = readParenName();
1624	if (ctx.script->memoryRegions.count(Key: name) == 0) {
1625	setError("memory region not defined: " + name);
1626	return [] { return 0; };
1627	}
1628	return ctx.script->memoryRegions[name]->origin;
1629	}
1630	if (tok == "SEGMENT_START") {
1631	expect(expect: "(");
1632	skip();
1633	expect(expect: ",");
1634	Expr e = readExpr();
1635	expect(expect: ")");
1636	return [=] { return e(); };
1637	}
1638	if (tok == "SIZEOF") {
1639	StringRef name = readParenName();
1640	OutputSection *cmd = &ctx.script->getOrCreateOutputSection(name)->osec;
1641	// Linker script does not create an output section if its content is empty.
1642	// We want to allow SIZEOF(.foo) where .foo is a section which happened to
1643	// be empty.
1644	return [=] { return cmd->size; };
1645	}
1646	if (tok == "SIZEOF_HEADERS")
1647	return [=, &ctx = ctx] { return elf::getHeaderSize(ctx); };
1648
1649	// Tok is the dot.
1650	if (tok == ".")
1651	return [=, s = ctx.script] { return s->getSymbolValue(name: tok, loc: location); };
1652
1653	// Tok is a literal number.
1654	if (std::optional<uint64_t> val = parseInt(tok))
1655	return [=] { return *val; };
1656
1657	// Tok is a symbol name.
1658	if (tok.starts_with(Prefix: "\""))
1659	tok = unquote(s: tok);
1660	else if (!isValidSymbolName(s: tok))
1661	setError("malformed number: " + tok);
1662	if (activeProvideSym)
1663	ctx.script->provideMap[*activeProvideSym].push_back(Elt: tok);
1664	else
1665	ctx.script->referencedSymbols.push_back(Elt: tok);
1666	return [=, s = ctx.script] { return s->getSymbolValue(name: tok, loc: location); };
1667	}
1668
1669	Expr ScriptParser::readTernary(Expr cond) {
1670	Expr l = readExpr();
1671	expect(expect: ":");
1672	Expr r = readExpr();
1673	return [=] { return cond().getValue() ? l() : r(); };
1674	}
1675
1676	Expr ScriptParser::readParenExpr() {
1677	expect(expect: "(");
1678	Expr e = readExpr();
1679	expect(expect: ")");
1680	return e;
1681	}
1682
1683	SmallVector<StringRef, 0> ScriptParser::readOutputSectionPhdrs() {
1684	SmallVector<StringRef, 0> phdrs;
1685	while (!errCount(ctx) && peek().starts_with(Prefix: ":")) {
1686	StringRef tok = next();
1687	phdrs.push_back(Elt: (tok.size() == 1) ? readName() : tok.substr(Start: 1));
1688	}
1689	return phdrs;
1690	}
1691
1692	// Read a program header type name. The next token must be a
1693	// name of a program header type or a constant (e.g. "0x3").
1694	unsigned ScriptParser::readPhdrType() {
1695	StringRef tok = next();
1696	if (std::optional<uint64_t> val = parseInt(tok))
1697	return *val;
1698
1699	unsigned ret = StringSwitch<unsigned>(tok)
1700	.Case(S: "PT_NULL", Value: PT_NULL)
1701	.Case(S: "PT_LOAD", Value: PT_LOAD)
1702	.Case(S: "PT_DYNAMIC", Value: PT_DYNAMIC)
1703	.Case(S: "PT_INTERP", Value: PT_INTERP)
1704	.Case(S: "PT_NOTE", Value: PT_NOTE)
1705	.Case(S: "PT_SHLIB", Value: PT_SHLIB)
1706	.Case(S: "PT_PHDR", Value: PT_PHDR)
1707	.Case(S: "PT_TLS", Value: PT_TLS)
1708	.Case(S: "PT_GNU_EH_FRAME", Value: PT_GNU_EH_FRAME)
1709	.Case(S: "PT_GNU_STACK", Value: PT_GNU_STACK)
1710	.Case(S: "PT_GNU_RELRO", Value: PT_GNU_RELRO)
1711	.Case(S: "PT_OPENBSD_MUTABLE", Value: PT_OPENBSD_MUTABLE)
1712	.Case(S: "PT_OPENBSD_RANDOMIZE", Value: PT_OPENBSD_RANDOMIZE)
1713	.Case(S: "PT_OPENBSD_SYSCALLS", Value: PT_OPENBSD_SYSCALLS)
1714	.Case(S: "PT_OPENBSD_WXNEEDED", Value: PT_OPENBSD_WXNEEDED)
1715	.Case(S: "PT_OPENBSD_BOOTDATA", Value: PT_OPENBSD_BOOTDATA)
1716	.Default(Value: -1);
1717
1718	if (ret == (unsigned)-1) {
1719	setError("invalid program header type: " + tok);
1720	return PT_NULL;
1721	}
1722	return ret;
1723	}
1724
1725	// Reads an anonymous version declaration.
1726	void ScriptParser::readAnonymousDeclaration() {
1727	SmallVector<SymbolVersion, 0> locals;
1728	SmallVector<SymbolVersion, 0> globals;
1729	std::tie(args&: locals, args&: globals) = readSymbols();
1730	for (const SymbolVersion &pat : locals)
1731	ctx.arg.versionDefinitions[VER_NDX_LOCAL].localPatterns.push_back(Elt: pat);
1732	for (const SymbolVersion &pat : globals)
1733	ctx.arg.versionDefinitions[VER_NDX_GLOBAL].nonLocalPatterns.push_back(Elt: pat);
1734
1735	expect(expect: ";");
1736	}
1737
1738	// Reads a non-anonymous version definition,
1739	// e.g. "VerStr { global: foo; bar; local: *; };".
1740	void ScriptParser::readVersionDeclaration(StringRef verStr) {
1741	// Read a symbol list.
1742	SmallVector<SymbolVersion, 0> locals;
1743	SmallVector<SymbolVersion, 0> globals;
1744	std::tie(args&: locals, args&: globals) = readSymbols();
1745
1746	// Create a new version definition and add that to the global symbols.
1747	VersionDefinition ver;
1748	ver.name = verStr;
1749	ver.nonLocalPatterns = std::move(globals);
1750	ver.localPatterns = std::move(locals);
1751	ver.id = ctx.arg.versionDefinitions.size();
1752	ctx.arg.versionDefinitions.push_back(Elt: ver);
1753
1754	// Each version may have a parent version. For example, "Ver2"
1755	// defined as "Ver2 { global: foo; local: *; } Ver1;" has "Ver1"
1756	// as a parent. This version hierarchy is, probably against your
1757	// instinct, purely for hint; the runtime doesn't care about it
1758	// at all. In LLD, we simply ignore it.
1759	if (next() != ";")
1760	expect(expect: ";");
1761	}
1762
1763	bool elf::hasWildcard(StringRef s) {
1764	return s.find_first_of(Chars: "?*[") != StringRef::npos;
1765	}
1766
1767	// Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
1768	std::pair<SmallVector<SymbolVersion, 0>, SmallVector<SymbolVersion, 0>>
1769	ScriptParser::readSymbols() {
1770	SmallVector<SymbolVersion, 0> locals;
1771	SmallVector<SymbolVersion, 0> globals;
1772	SmallVector<SymbolVersion, 0> *v = &globals;
1773
1774	while (auto tok = till(tok: "}")) {
1775	if (tok == "extern") {
1776	SmallVector<SymbolVersion, 0> ext = readVersionExtern();
1777	v->insert(I: v->end(), From: ext.begin(), To: ext.end());
1778	} else {
1779	if (tok == "local:" || (tok == "local" && consume(tok: ":"))) {
1780	v = &locals;
1781	continue;
1782	}
1783	if (tok == "global:" || (tok == "global" && consume(tok: ":"))) {
1784	v = &globals;
1785	continue;
1786	}
1787	v->push_back(Elt: {.name: unquote(s: tok), .isExternCpp: false, .hasWildcard: hasWildcard(s: tok)});
1788	}
1789	expect(expect: ";");
1790	}
1791	return {locals, globals};
1792	}
1793
1794	// Reads an "extern C++" directive, e.g.,
1795	// "extern "C++" { ns::*; "f(int, double)"; };"
1796	//
1797	// The last semicolon is optional. E.g. this is OK:
1798	// "extern "C++" { ns::*; "f(int, double)" };"
1799	SmallVector<SymbolVersion, 0> ScriptParser::readVersionExtern() {
1800	StringRef tok = next();
1801	bool isCXX = tok == "\"C++\"";
1802	if (!isCXX && tok != "\"C\"")
1803	setError("Unknown language");
1804	expect(expect: "{");
1805
1806	SmallVector<SymbolVersion, 0> ret;
1807	while (auto tok = till(tok: "}")) {
1808	ret.push_back(
1809	Elt: {.name: unquote(s: tok), .isExternCpp: isCXX, .hasWildcard: !tok.str.starts_with(Prefix: "\"") && hasWildcard(s: tok)});
1810	if (consume(tok: "}"))
1811	return ret;
1812	expect(expect: ";");
1813	}
1814	return ret;
1815	}
1816
1817	Expr ScriptParser::readMemoryAssignment(StringRef s1, StringRef s2,
1818	StringRef s3) {
1819	if (!consume(tok: s1) && !consume(tok: s2) && !consume(tok: s3)) {
1820	setError("expected one of: " + s1 + ", " + s2 + ", or " + s3);
1821	return [] { return 0; };
1822	}
1823	expect(expect: "=");
1824	return readExpr();
1825	}
1826
1827	// Parse the MEMORY command as specified in:
1828	// https://sourceware.org/binutils/docs/ld/MEMORY.html
1829	//
1830	// MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
1831	void ScriptParser::readMemory() {
1832	expect(expect: "{");
1833	while (auto tok = till(tok: "}")) {
1834	if (tok == "INCLUDE") {
1835	readInclude();
1836	continue;
1837	}
1838
1839	uint32_t flags = 0;
1840	uint32_t invFlags = 0;
1841	uint32_t negFlags = 0;
1842	uint32_t negInvFlags = 0;
1843	if (consume(tok: "(")) {
1844	readMemoryAttributes(flags, invFlags, negFlags, negInvFlags);
1845	expect(expect: ")");
1846	}
1847	expect(expect: ":");
1848
1849	Expr origin = readMemoryAssignment(s1: "ORIGIN", s2: "org", s3: "o");
1850	expect(expect: ",");
1851	Expr length = readMemoryAssignment(s1: "LENGTH", s2: "len", s3: "l");
1852
1853	// Add the memory region to the region map.
1854	MemoryRegion *mr = make<MemoryRegion>(args&: tok, args&: origin, args&: length, args&: flags, args&: invFlags,
1855	args&: negFlags, args&: negInvFlags);
1856	if (!ctx.script->memoryRegions.insert(KV: {tok, mr}).second)
1857	setError("region '" + tok + "' already defined");
1858	}
1859	}
1860
1861	// This function parses the attributes used to match against section
1862	// flags when placing output sections in a memory region. These flags
1863	// are only used when an explicit memory region name is not used.
1864	void ScriptParser::readMemoryAttributes(uint32_t &flags, uint32_t &invFlags,
1865	uint32_t &negFlags,
1866	uint32_t &negInvFlags) {
1867	bool invert = false;
1868
1869	for (char c : next().lower()) {
1870	if (c == '!') {
1871	invert = !invert;
1872	std::swap(a&: flags, b&: negFlags);
1873	std::swap(a&: invFlags, b&: negInvFlags);
1874	continue;
1875	}
1876	if (c == 'w')
1877	flags |= SHF_WRITE;
1878	else if (c == 'x')
1879	flags |= SHF_EXECINSTR;
1880	else if (c == 'a')
1881	flags |= SHF_ALLOC;
1882	else if (c == 'r')
1883	invFlags |= SHF_WRITE;
1884	else
1885	setError("invalid memory region attribute");
1886	}
1887
1888	if (invert) {
1889	std::swap(a&: flags, b&: negFlags);
1890	std::swap(a&: invFlags, b&: negInvFlags);
1891	}
1892	}
1893
1894	void elf::readLinkerScript(Ctx &ctx, MemoryBufferRef mb) {
1895	llvm::TimeTraceScope timeScope("Read linker script",
1896	mb.getBufferIdentifier());
1897	ScriptParser(ctx, mb).readLinkerScript();
1898	}
1899
1900	void elf::readVersionScript(Ctx &ctx, MemoryBufferRef mb) {
1901	llvm::TimeTraceScope timeScope("Read version script",
1902	mb.getBufferIdentifier());
1903	ScriptParser(ctx, mb).readVersionScript();
1904	}
1905
1906	void elf::readDynamicList(Ctx &ctx, MemoryBufferRef mb) {
1907	llvm::TimeTraceScope timeScope("Read dynamic list", mb.getBufferIdentifier());
1908	ScriptParser(ctx, mb).readDynamicList();
1909	}
1910
1911	void elf::readDefsym(Ctx &ctx, MemoryBufferRef mb) {
1912	ScriptParser(ctx, mb).readDefsym();
1913	}
1914