1	//===- VirtualFileSystem.cpp - Virtual File System Layer ------------------===//
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 implements the VirtualFileSystem interface.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "llvm/Support/VirtualFileSystem.h"
14	#include "llvm/ADT/ArrayRef.h"
15	#include "llvm/ADT/DenseMap.h"
16	#include "llvm/ADT/IntrusiveRefCntPtr.h"
17	#include "llvm/ADT/STLExtras.h"
18	#include "llvm/ADT/SmallString.h"
19	#include "llvm/ADT/SmallVector.h"
20	#include "llvm/ADT/StringRef.h"
21	#include "llvm/ADT/StringSet.h"
22	#include "llvm/ADT/Twine.h"
23	#include "llvm/ADT/iterator_range.h"
24	#include "llvm/Config/llvm-config.h"
25	#include "llvm/Support/Casting.h"
26	#include "llvm/Support/Chrono.h"
27	#include "llvm/Support/Compiler.h"
28	#include "llvm/Support/Debug.h"
29	#include "llvm/Support/Errc.h"
30	#include "llvm/Support/ErrorHandling.h"
31	#include "llvm/Support/ErrorOr.h"
32	#include "llvm/Support/FileSystem.h"
33	#include "llvm/Support/FileSystem/UniqueID.h"
34	#include "llvm/Support/MemoryBuffer.h"
35	#include "llvm/Support/Path.h"
36	#include "llvm/Support/SMLoc.h"
37	#include "llvm/Support/SourceMgr.h"
38	#include "llvm/Support/YAMLParser.h"
39	#include "llvm/Support/raw_ostream.h"
40	#include <algorithm>
41	#include <atomic>
42	#include <cassert>
43	#include <cstdint>
44	#include <iterator>
45	#include <limits>
46	#include <map>
47	#include <memory>
48	#include <optional>
49	#include <string>
50	#include <system_error>
51	#include <utility>
52	#include <vector>
53
54	using namespace llvm;
55	using namespace llvm::vfs;
56
57	using llvm::sys::fs::file_t;
58	using llvm::sys::fs::file_status;
59	using llvm::sys::fs::file_type;
60	using llvm::sys::fs::kInvalidFile;
61	using llvm::sys::fs::perms;
62	using llvm::sys::fs::UniqueID;
63
64	Status::Status(const file_status &Status)
65	: UID(Status.getUniqueID()), MTime(Status.getLastModificationTime()),
66	User(Status.getUser()), Group(Status.getGroup()), Size(Status.getSize()),
67	Type(Status.type()), Perms(Status.permissions()) {}
68
69	Status::Status(const Twine &Name, UniqueID UID, sys::TimePoint<> MTime,
70	uint32_t User, uint32_t Group, uint64_t Size, file_type Type,
71	perms Perms)
72	: Name(Name.str()), UID(UID), MTime(MTime), User(User), Group(Group),
73	Size(Size), Type(Type), Perms(Perms) {}
74
75	Status Status::copyWithNewSize(const Status &In, uint64_t NewSize) {
76	return Status(In.getName(), In.getUniqueID(), In.getLastModificationTime(),
77	In.getUser(), In.getGroup(), NewSize, In.getType(),
78	In.getPermissions());
79	}
80
81	Status Status::copyWithNewName(const Status &In, const Twine &NewName) {
82	return Status(NewName, In.getUniqueID(), In.getLastModificationTime(),
83	In.getUser(), In.getGroup(), In.getSize(), In.getType(),
84	In.getPermissions());
85	}
86
87	Status Status::copyWithNewName(const file_status &In, const Twine &NewName) {
88	return Status(NewName, In.getUniqueID(), In.getLastModificationTime(),
89	In.getUser(), In.getGroup(), In.getSize(), In.type(),
90	In.permissions());
91	}
92
93	bool Status::equivalent(const Status &Other) const {
94	assert(isStatusKnown() && Other.isStatusKnown());
95	return getUniqueID() == Other.getUniqueID();
96	}
97
98	bool Status::isDirectory() const { return Type == file_type::directory_file; }
99
100	bool Status::isRegularFile() const { return Type == file_type::regular_file; }
101
102	bool Status::isOther() const {
103	return exists() && !isRegularFile() && !isDirectory() && !isSymlink();
104	}
105
106	bool Status::isSymlink() const { return Type == file_type::symlink_file; }
107
108	bool Status::isStatusKnown() const { return Type != file_type::status_error; }
109
110	bool Status::exists() const {
111	return isStatusKnown() && Type != file_type::file_not_found;
112	}
113
114	File::~File() = default;
115
116	FileSystem::~FileSystem() = default;
117
118	ErrorOr<std::unique_ptr<MemoryBuffer>>
119	FileSystem::getBufferForFile(const llvm::Twine &Name, int64_t FileSize,
120	bool RequiresNullTerminator, bool IsVolatile) {
121	auto F = openFileForRead(Path: Name);
122	if (!F)
123	return F.getError();
124
125	return (*F)->getBuffer(Name, FileSize, RequiresNullTerminator, IsVolatile);
126	}
127
128	std::error_code FileSystem::makeAbsolute(SmallVectorImpl<char> &Path) const {
129	if (llvm::sys::path::is_absolute(path: Path))
130	return {};
131
132	auto WorkingDir = getCurrentWorkingDirectory();
133	if (!WorkingDir)
134	return WorkingDir.getError();
135
136	llvm::sys::fs::make_absolute(current_directory: WorkingDir.get(), path&: Path);
137	return {};
138	}
139
140	std::error_code FileSystem::getRealPath(const Twine &Path,
141	SmallVectorImpl<char> &Output) const {
142	return errc::operation_not_permitted;
143	}
144
145	std::error_code FileSystem::isLocal(const Twine &Path, bool &Result) {
146	return errc::operation_not_permitted;
147	}
148
149	bool FileSystem::exists(const Twine &Path) {
150	auto Status = status(Path);
151	return Status && Status->exists();
152	}
153
154	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
155	void FileSystem::dump() const { print(OS&: dbgs(), Type: PrintType::RecursiveContents); }
156	#endif
157
158	#ifndef NDEBUG
159	static bool isTraversalComponent(StringRef Component) {
160	return Component.equals(RHS: "..") || Component.equals(RHS: ".");
161	}
162
163	static bool pathHasTraversal(StringRef Path) {
164	using namespace llvm::sys;
165
166	for (StringRef Comp : llvm::make_range(x: path::begin(path: Path), y: path::end(path: Path)))
167	if (isTraversalComponent(Component: Comp))
168	return true;
169	return false;
170	}
171	#endif
172
173	//===-----------------------------------------------------------------------===/
174	// RealFileSystem implementation
175	//===-----------------------------------------------------------------------===/
176
177	namespace {
178
179	/// Wrapper around a raw file descriptor.
180	class RealFile : public File {
181	friend class RealFileSystem;
182
183	file_t FD;
184	Status S;
185	std::string RealName;
186
187	RealFile(file_t RawFD, StringRef NewName, StringRef NewRealPathName)
188	: FD(RawFD), S(NewName, {}, {}, {}, {}, {},
189	llvm::sys::fs::file_type::status_error, {}),
190	RealName(NewRealPathName.str()) {
191	assert(FD != kInvalidFile && "Invalid or inactive file descriptor");
192	}
193
194	public:
195	~RealFile() override;
196
197	ErrorOr<Status> status() override;
198	ErrorOr<std::string> getName() override;
199	ErrorOr<std::unique_ptr<MemoryBuffer>> getBuffer(const Twine &Name,
200	int64_t FileSize,
201	bool RequiresNullTerminator,
202	bool IsVolatile) override;
203	std::error_code close() override;
204	void setPath(const Twine &Path) override;
205	};
206
207	} // namespace
208
209	RealFile::~RealFile() { close(); }
210
211	ErrorOr<Status> RealFile::status() {
212	assert(FD != kInvalidFile && "cannot stat closed file");
213	if (!S.isStatusKnown()) {
214	file_status RealStatus;
215	if (std::error_code EC = sys::fs::status(FD, Result&: RealStatus))
216	return EC;
217	S = Status::copyWithNewName(In: RealStatus, NewName: S.getName());
218	}
219	return S;
220	}
221
222	ErrorOr<std::string> RealFile::getName() {
223	return RealName.empty() ? S.getName().str() : RealName;
224	}
225
226	ErrorOr<std::unique_ptr<MemoryBuffer>>
227	RealFile::getBuffer(const Twine &Name, int64_t FileSize,
228	bool RequiresNullTerminator, bool IsVolatile) {
229	assert(FD != kInvalidFile && "cannot get buffer for closed file");
230	return MemoryBuffer::getOpenFile(FD, Filename: Name, FileSize, RequiresNullTerminator,
231	IsVolatile);
232	}
233
234	std::error_code RealFile::close() {
235	std::error_code EC = sys::fs::closeFile(F&: FD);
236	FD = kInvalidFile;
237	return EC;
238	}
239
240	void RealFile::setPath(const Twine &Path) {
241	RealName = Path.str();
242	if (auto Status = status())
243	S = Status.get().copyWithNewName(In: Status.get(), NewName: Path);
244	}
245
246	namespace {
247
248	/// A file system according to your operating system.
249	/// This may be linked to the process's working directory, or maintain its own.
250	///
251	/// Currently, its own working directory is emulated by storing the path and
252	/// sending absolute paths to llvm::sys::fs:: functions.
253	/// A more principled approach would be to push this down a level, modelling
254	/// the working dir as an llvm::sys::fs::WorkingDir or similar.
255	/// This would enable the use of openat()-style functions on some platforms.
256	class RealFileSystem : public FileSystem {
257	public:
258	explicit RealFileSystem(bool LinkCWDToProcess) {
259	if (!LinkCWDToProcess) {
260	SmallString<128> PWD, RealPWD;
261	if (std::error_code EC = llvm::sys::fs::current_path(result&: PWD))
262	WD = EC;
263	else if (llvm::sys::fs::real_path(path: PWD, output&: RealPWD))
264	WD = WorkingDirectory{.Specified: PWD, .Resolved: PWD};
265	else
266	WD = WorkingDirectory{.Specified: PWD, .Resolved: RealPWD};
267	}
268	}
269
270	ErrorOr<Status> status(const Twine &Path) override;
271	ErrorOr<std::unique_ptr<File>> openFileForRead(const Twine &Path) override;
272	directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override;
273
274	llvm::ErrorOr<std::string> getCurrentWorkingDirectory() const override;
275	std::error_code setCurrentWorkingDirectory(const Twine &Path) override;
276	std::error_code isLocal(const Twine &Path, bool &Result) override;
277	std::error_code getRealPath(const Twine &Path,
278	SmallVectorImpl<char> &Output) const override;
279
280	protected:
281	void printImpl(raw_ostream &OS, PrintType Type,
282	unsigned IndentLevel) const override;
283
284	private:
285	// If this FS has its own working dir, use it to make Path absolute.
286	// The returned twine is safe to use as long as both Storage and Path live.
287	Twine adjustPath(const Twine &Path, SmallVectorImpl<char> &Storage) const {
288	if (!WD || !*WD)
289	return Path;
290	Path.toVector(Out&: Storage);
291	sys::fs::make_absolute(current_directory: WD->get().Resolved, path&: Storage);
292	return Storage;
293	}
294
295	struct WorkingDirectory {
296	// The current working directory, without symlinks resolved. (echo $PWD).
297	SmallString<128> Specified;
298	// The current working directory, with links resolved. (readlink .).
299	SmallString<128> Resolved;
300	};
301	std::optional<llvm::ErrorOr<WorkingDirectory>> WD;
302	};
303
304	} // namespace
305
306	ErrorOr<Status> RealFileSystem::status(const Twine &Path) {
307	SmallString<256> Storage;
308	sys::fs::file_status RealStatus;
309	if (std::error_code EC =
310	sys::fs::status(path: adjustPath(Path, Storage), result&: RealStatus))
311	return EC;
312	return Status::copyWithNewName(In: RealStatus, NewName: Path);
313	}
314
315	ErrorOr<std::unique_ptr<File>>
316	RealFileSystem::openFileForRead(const Twine &Name) {
317	SmallString<256> RealName, Storage;
318	Expected<file_t> FDOrErr = sys::fs::openNativeFileForRead(
319	Name: adjustPath(Path: Name, Storage), Flags: sys::fs::OF_None, RealPath: &RealName);
320	if (!FDOrErr)
321	return errorToErrorCode(Err: FDOrErr.takeError());
322	return std::unique_ptr<File>(
323	new RealFile(*FDOrErr, Name.str(), RealName.str()));
324	}
325
326	llvm::ErrorOr<std::string> RealFileSystem::getCurrentWorkingDirectory() const {
327	if (WD && *WD)
328	return std::string(WD->get().Specified);
329	if (WD)
330	return WD->getError();
331
332	SmallString<128> Dir;
333	if (std::error_code EC = llvm::sys::fs::current_path(result&: Dir))
334	return EC;
335	return std::string(Dir);
336	}
337
338	std::error_code RealFileSystem::setCurrentWorkingDirectory(const Twine &Path) {
339	if (!WD)
340	return llvm::sys::fs::set_current_path(Path);
341
342	SmallString<128> Absolute, Resolved, Storage;
343	adjustPath(Path, Storage).toVector(Out&: Absolute);
344	bool IsDir;
345	if (auto Err = llvm::sys::fs::is_directory(path: Absolute, result&: IsDir))
346	return Err;
347	if (!IsDir)
348	return std::make_error_code(e: std::errc::not_a_directory);
349	if (auto Err = llvm::sys::fs::real_path(path: Absolute, output&: Resolved))
350	return Err;
351	WD = WorkingDirectory{.Specified: Absolute, .Resolved: Resolved};
352	return std::error_code();
353	}
354
355	std::error_code RealFileSystem::isLocal(const Twine &Path, bool &Result) {
356	SmallString<256> Storage;
357	return llvm::sys::fs::is_local(path: adjustPath(Path, Storage), result&: Result);
358	}
359
360	std::error_code
361	RealFileSystem::getRealPath(const Twine &Path,
362	SmallVectorImpl<char> &Output) const {
363	SmallString<256> Storage;
364	return llvm::sys::fs::real_path(path: adjustPath(Path, Storage), output&: Output);
365	}
366
367	void RealFileSystem::printImpl(raw_ostream &OS, PrintType Type,
368	unsigned IndentLevel) const {
369	printIndent(OS, IndentLevel);
370	OS << "RealFileSystem using ";
371	if (WD)
372	OS << "own";
373	else
374	OS << "process";
375	OS << " CWD\n";
376	}
377
378	IntrusiveRefCntPtr<FileSystem> vfs::getRealFileSystem() {
379	static IntrusiveRefCntPtr<FileSystem> FS(new RealFileSystem(true));
380	return FS;
381	}
382
383	std::unique_ptr<FileSystem> vfs::createPhysicalFileSystem() {
384	return std::make_unique<RealFileSystem>(args: false);
385	}
386
387	namespace {
388
389	class RealFSDirIter : public llvm::vfs::detail::DirIterImpl {
390	llvm::sys::fs::directory_iterator Iter;
391
392	public:
393	RealFSDirIter(const Twine &Path, std::error_code &EC) : Iter(Path, EC) {
394	if (Iter != llvm::sys::fs::directory_iterator())
395	CurrentEntry = directory_entry(Iter->path(), Iter->type());
396	}
397
398	std::error_code increment() override {
399	std::error_code EC;
400	Iter.increment(ec&: EC);
401	CurrentEntry = (Iter == llvm::sys::fs::directory_iterator())
402	? directory_entry()
403	: directory_entry(Iter->path(), Iter->type());
404	return EC;
405	}
406	};
407
408	} // namespace
409
410	directory_iterator RealFileSystem::dir_begin(const Twine &Dir,
411	std::error_code &EC) {
412	SmallString<128> Storage;
413	return directory_iterator(
414	std::make_shared<RealFSDirIter>(args: adjustPath(Path: Dir, Storage), args&: EC));
415	}
416
417	//===-----------------------------------------------------------------------===/
418	// OverlayFileSystem implementation
419	//===-----------------------------------------------------------------------===/
420
421	OverlayFileSystem::OverlayFileSystem(IntrusiveRefCntPtr<FileSystem> BaseFS) {
422	FSList.push_back(Elt: std::move(BaseFS));
423	}
424
425	void OverlayFileSystem::pushOverlay(IntrusiveRefCntPtr<FileSystem> FS) {
426	FSList.push_back(Elt: FS);
427	// Synchronize added file systems by duplicating the working directory from
428	// the first one in the list.
429	FS->setCurrentWorkingDirectory(getCurrentWorkingDirectory().get());
430	}
431
432	ErrorOr<Status> OverlayFileSystem::status(const Twine &Path) {
433	// FIXME: handle symlinks that cross file systems
434	for (iterator I = overlays_begin(), E = overlays_end(); I != E; ++I) {
435	ErrorOr<Status> Status = (*I)->status(Path);
436	if (Status || Status.getError() != llvm::errc::no_such_file_or_directory)
437	return Status;
438	}
439	return make_error_code(E: llvm::errc::no_such_file_or_directory);
440	}
441
442	ErrorOr<std::unique_ptr<File>>
443	OverlayFileSystem::openFileForRead(const llvm::Twine &Path) {
444	// FIXME: handle symlinks that cross file systems
445	for (iterator I = overlays_begin(), E = overlays_end(); I != E; ++I) {
446	auto Result = (*I)->openFileForRead(Path);
447	if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
448	return Result;
449	}
450	return make_error_code(E: llvm::errc::no_such_file_or_directory);
451	}
452
453	llvm::ErrorOr<std::string>
454	OverlayFileSystem::getCurrentWorkingDirectory() const {
455	// All file systems are synchronized, just take the first working directory.
456	return FSList.front()->getCurrentWorkingDirectory();
457	}
458
459	std::error_code
460	OverlayFileSystem::setCurrentWorkingDirectory(const Twine &Path) {
461	for (auto &FS : FSList)
462	if (std::error_code EC = FS->setCurrentWorkingDirectory(Path))
463	return EC;
464	return {};
465	}
466
467	std::error_code OverlayFileSystem::isLocal(const Twine &Path, bool &Result) {
468	for (auto &FS : FSList)
469	if (FS->exists(Path))
470	return FS->isLocal(Path, Result);
471	return errc::no_such_file_or_directory;
472	}
473
474	std::error_code
475	OverlayFileSystem::getRealPath(const Twine &Path,
476	SmallVectorImpl<char> &Output) const {
477	for (const auto &FS : FSList)
478	if (FS->exists(Path))
479	return FS->getRealPath(Path, Output);
480	return errc::no_such_file_or_directory;
481	}
482
483	void OverlayFileSystem::visitChildFileSystems(VisitCallbackTy Callback) {
484	for (IntrusiveRefCntPtr<FileSystem> FS : overlays_range()) {
485	Callback(*FS);
486	FS->visitChildFileSystems(Callback);
487	}
488	}
489
490	void OverlayFileSystem::printImpl(raw_ostream &OS, PrintType Type,
491	unsigned IndentLevel) const {
492	printIndent(OS, IndentLevel);
493	OS << "OverlayFileSystem\n";
494	if (Type == PrintType::Summary)
495	return;
496
497	if (Type == PrintType::Contents)
498	Type = PrintType::Summary;
499	for (const auto &FS : overlays_range())
500	FS->print(OS, Type, IndentLevel: IndentLevel + 1);
501	}
502
503	llvm::vfs::detail::DirIterImpl::~DirIterImpl() = default;
504
505	namespace {
506
507	/// Combines and deduplicates directory entries across multiple file systems.
508	class CombiningDirIterImpl : public llvm::vfs::detail::DirIterImpl {
509	using FileSystemPtr = llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>;
510
511	/// Iterators to combine, processed in reverse order.
512	SmallVector<directory_iterator, 8> IterList;
513	/// The iterator currently being traversed.
514	directory_iterator CurrentDirIter;
515	/// The set of names already returned as entries.
516	llvm::StringSet<> SeenNames;
517
518	/// Sets \c CurrentDirIter to the next iterator in the list, or leaves it as
519	/// is (at its end position) if we've already gone through them all.
520	std::error_code incrementIter(bool IsFirstTime) {
521	while (!IterList.empty()) {
522	CurrentDirIter = IterList.back();
523	IterList.pop_back();
524	if (CurrentDirIter != directory_iterator())
525	break; // found
526	}
527
528	if (IsFirstTime && CurrentDirIter == directory_iterator())
529	return errc::no_such_file_or_directory;
530	return {};
531	}
532
533	std::error_code incrementDirIter(bool IsFirstTime) {
534	assert((IsFirstTime || CurrentDirIter != directory_iterator()) &&
535	"incrementing past end");
536	std::error_code EC;
537	if (!IsFirstTime)
538	CurrentDirIter.increment(EC);
539	if (!EC && CurrentDirIter == directory_iterator())
540	EC = incrementIter(IsFirstTime);
541	return EC;
542	}
543
544	std::error_code incrementImpl(bool IsFirstTime) {
545	while (true) {
546	std::error_code EC = incrementDirIter(IsFirstTime);
547	if (EC || CurrentDirIter == directory_iterator()) {
548	CurrentEntry = directory_entry();
549	return EC;
550	}
551	CurrentEntry = *CurrentDirIter;
552	StringRef Name = llvm::sys::path::filename(path: CurrentEntry.path());
553	if (SeenNames.insert(key: Name).second)
554	return EC; // name not seen before
555	}
556	llvm_unreachable("returned above");
557	}
558
559	public:
560	CombiningDirIterImpl(ArrayRef<FileSystemPtr> FileSystems, std::string Dir,
561	std::error_code &EC) {
562	for (const auto &FS : FileSystems) {
563	std::error_code FEC;
564	directory_iterator Iter = FS->dir_begin(Dir, EC&: FEC);
565	if (FEC && FEC != errc::no_such_file_or_directory) {
566	EC = FEC;
567	return;
568	}
569	if (!FEC)
570	IterList.push_back(Elt: Iter);
571	}
572	EC = incrementImpl(IsFirstTime: true);
573	}
574
575	CombiningDirIterImpl(ArrayRef<directory_iterator> DirIters,
576	std::error_code &EC)
577	: IterList(DirIters.begin(), DirIters.end()) {
578	EC = incrementImpl(IsFirstTime: true);
579	}
580
581	std::error_code increment() override { return incrementImpl(IsFirstTime: false); }
582	};
583
584	} // namespace
585
586	directory_iterator OverlayFileSystem::dir_begin(const Twine &Dir,
587	std::error_code &EC) {
588	directory_iterator Combined = directory_iterator(
589	std::make_shared<CombiningDirIterImpl>(args&: FSList, args: Dir.str(), args&: EC));
590	if (EC)
591	return {};
592	return Combined;
593	}
594
595	void ProxyFileSystem::anchor() {}
596
597	namespace llvm {
598	namespace vfs {
599
600	namespace detail {
601
602	enum InMemoryNodeKind {
603	IME_File,
604	IME_Directory,
605	IME_HardLink,
606	IME_SymbolicLink,
607	};
608
609	/// The in memory file system is a tree of Nodes. Every node can either be a
610	/// file, symlink, hardlink or a directory.
611	class InMemoryNode {
612	InMemoryNodeKind Kind;
613	std::string FileName;
614
615	public:
616	InMemoryNode(llvm::StringRef FileName, InMemoryNodeKind Kind)
617	: Kind(Kind), FileName(std::string(llvm::sys::path::filename(path: FileName))) {
618	}
619	virtual ~InMemoryNode() = default;
620
621	/// Return the \p Status for this node. \p RequestedName should be the name
622	/// through which the caller referred to this node. It will override
623	/// \p Status::Name in the return value, to mimic the behavior of \p RealFile.
624	virtual Status getStatus(const Twine &RequestedName) const = 0;
625
626	/// Get the filename of this node (the name without the directory part).
627	StringRef getFileName() const { return FileName; }
628	InMemoryNodeKind getKind() const { return Kind; }
629	virtual std::string toString(unsigned Indent) const = 0;
630	};
631
632	class InMemoryFile : public InMemoryNode {
633	Status Stat;
634	std::unique_ptr<llvm::MemoryBuffer> Buffer;
635
636	public:
637	InMemoryFile(Status Stat, std::unique_ptr<llvm::MemoryBuffer> Buffer)
638	: InMemoryNode(Stat.getName(), IME_File), Stat(std::move(Stat)),
639	Buffer(std::move(Buffer)) {}
640
641	Status getStatus(const Twine &RequestedName) const override {
642	return Status::copyWithNewName(In: Stat, NewName: RequestedName);
643	}
644	llvm::MemoryBuffer *getBuffer() const { return Buffer.get(); }
645
646	std::string toString(unsigned Indent) const override {
647	return (std::string(Indent, ' ') + Stat.getName() + "\n").str();
648	}
649
650	static bool classof(const InMemoryNode *N) {
651	return N->getKind() == IME_File;
652	}
653	};
654
655	namespace {
656
657	class InMemoryHardLink : public InMemoryNode {
658	const InMemoryFile &ResolvedFile;
659
660	public:
661	InMemoryHardLink(StringRef Path, const InMemoryFile &ResolvedFile)
662	: InMemoryNode(Path, IME_HardLink), ResolvedFile(ResolvedFile) {}
663	const InMemoryFile &getResolvedFile() const { return ResolvedFile; }
664
665	Status getStatus(const Twine &RequestedName) const override {
666	return ResolvedFile.getStatus(RequestedName);
667	}
668
669	std::string toString(unsigned Indent) const override {
670	return std::string(Indent, ' ') + "HardLink to -> " +
671	ResolvedFile.toString(Indent: 0);
672	}
673
674	static bool classof(const InMemoryNode *N) {
675	return N->getKind() == IME_HardLink;
676	}
677	};
678
679	class InMemorySymbolicLink : public InMemoryNode {
680	std::string TargetPath;
681	Status Stat;
682
683	public:
684	InMemorySymbolicLink(StringRef Path, StringRef TargetPath, Status Stat)
685	: InMemoryNode(Path, IME_SymbolicLink), TargetPath(std::move(TargetPath)),
686	Stat(Stat) {}
687
688	std::string toString(unsigned Indent) const override {
689	return std::string(Indent, ' ') + "SymbolicLink to -> " + TargetPath;
690	}
691
692	Status getStatus(const Twine &RequestedName) const override {
693	return Status::copyWithNewName(In: Stat, NewName: RequestedName);
694	}
695
696	StringRef getTargetPath() const { return TargetPath; }
697
698	static bool classof(const InMemoryNode *N) {
699	return N->getKind() == IME_SymbolicLink;
700	}
701	};
702
703	/// Adapt a InMemoryFile for VFS' File interface. The goal is to make
704	/// \p InMemoryFileAdaptor mimic as much as possible the behavior of
705	/// \p RealFile.
706	class InMemoryFileAdaptor : public File {
707	const InMemoryFile &Node;
708	/// The name to use when returning a Status for this file.
709	std::string RequestedName;
710
711	public:
712	explicit InMemoryFileAdaptor(const InMemoryFile &Node,
713	std::string RequestedName)
714	: Node(Node), RequestedName(std::move(RequestedName)) {}
715
716	llvm::ErrorOr<Status> status() override {
717	return Node.getStatus(RequestedName);
718	}
719
720	llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
721	getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
722	bool IsVolatile) override {
723	llvm::MemoryBuffer *Buf = Node.getBuffer();
724	return llvm::MemoryBuffer::getMemBuffer(
725	InputData: Buf->getBuffer(), BufferName: Buf->getBufferIdentifier(), RequiresNullTerminator);
726	}
727
728	std::error_code close() override { return {}; }
729
730	void setPath(const Twine &Path) override { RequestedName = Path.str(); }
731	};
732	} // namespace
733
734	class InMemoryDirectory : public InMemoryNode {
735	Status Stat;
736	std::map<std::string, std::unique_ptr<InMemoryNode>> Entries;
737
738	public:
739	InMemoryDirectory(Status Stat)
740	: InMemoryNode(Stat.getName(), IME_Directory), Stat(std::move(Stat)) {}
741
742	/// Return the \p Status for this node. \p RequestedName should be the name
743	/// through which the caller referred to this node. It will override
744	/// \p Status::Name in the return value, to mimic the behavior of \p RealFile.
745	Status getStatus(const Twine &RequestedName) const override {
746	return Status::copyWithNewName(In: Stat, NewName: RequestedName);
747	}
748
749	UniqueID getUniqueID() const { return Stat.getUniqueID(); }
750
751	InMemoryNode *getChild(StringRef Name) const {
752	auto I = Entries.find(x: Name.str());
753	if (I != Entries.end())
754	return I->second.get();
755	return nullptr;
756	}
757
758	InMemoryNode *addChild(StringRef Name, std::unique_ptr<InMemoryNode> Child) {
759	return Entries.emplace(args&: Name, args: std::move(Child)).first->second.get();
760	}
761
762	using const_iterator = decltype(Entries)::const_iterator;
763
764	const_iterator begin() const { return Entries.begin(); }
765	const_iterator end() const { return Entries.end(); }
766
767	std::string toString(unsigned Indent) const override {
768	std::string Result =
769	(std::string(Indent, ' ') + Stat.getName() + "\n").str();
770	for (const auto &Entry : Entries)
771	Result += Entry.second->toString(Indent: Indent + 2);
772	return Result;
773	}
774
775	static bool classof(const InMemoryNode *N) {
776	return N->getKind() == IME_Directory;
777	}
778	};
779
780	} // namespace detail
781
782	// The UniqueID of in-memory files is derived from path and content.
783	// This avoids difficulties in creating exactly equivalent in-memory FSes,
784	// as often needed in multithreaded programs.
785	static sys::fs::UniqueID getUniqueID(hash_code Hash) {
786	return sys::fs::UniqueID(std::numeric_limits<uint64_t>::max(),
787	uint64_t(size_t(Hash)));
788	}
789	static sys::fs::UniqueID getFileID(sys::fs::UniqueID Parent,
790	llvm::StringRef Name,
791	llvm::StringRef Contents) {
792	return getUniqueID(Hash: llvm::hash_combine(args: Parent.getFile(), args: Name, args: Contents));
793	}
794	static sys::fs::UniqueID getDirectoryID(sys::fs::UniqueID Parent,
795	llvm::StringRef Name) {
796	return getUniqueID(Hash: llvm::hash_combine(args: Parent.getFile(), args: Name));
797	}
798
799	Status detail::NewInMemoryNodeInfo::makeStatus() const {
800	UniqueID UID =
801	(Type == sys::fs::file_type::directory_file)
802	? getDirectoryID(Parent: DirUID, Name)
803	: getFileID(Parent: DirUID, Name, Contents: Buffer ? Buffer->getBuffer() : "");
804
805	return Status(Path, UID, llvm::sys::toTimePoint(T: ModificationTime), User,
806	Group, Buffer ? Buffer->getBufferSize() : 0, Type, Perms);
807	}
808
809	InMemoryFileSystem::InMemoryFileSystem(bool UseNormalizedPaths)
810	: Root(new detail::InMemoryDirectory(
811	Status("", getDirectoryID(Parent: llvm::sys::fs::UniqueID(), Name: ""),
812	llvm::sys::TimePoint<>(), 0, 0, 0,
813	llvm::sys::fs::file_type::directory_file,
814	llvm::sys::fs::perms::all_all))),
815	UseNormalizedPaths(UseNormalizedPaths) {}
816
817	InMemoryFileSystem::~InMemoryFileSystem() = default;
818
819	std::string InMemoryFileSystem::toString() const {
820	return Root->toString(/*Indent=*/0);
821	}
822
823	bool InMemoryFileSystem::addFile(const Twine &P, time_t ModificationTime,
824	std::unique_ptr<llvm::MemoryBuffer> Buffer,
825	std::optional<uint32_t> User,
826	std::optional<uint32_t> Group,
827	std::optional<llvm::sys::fs::file_type> Type,
828	std::optional<llvm::sys::fs::perms> Perms,
829	MakeNodeFn MakeNode) {
830	SmallString<128> Path;
831	P.toVector(Out&: Path);
832
833	// Fix up relative paths. This just prepends the current working directory.
834	std::error_code EC = makeAbsolute(Path);
835	assert(!EC);
836	(void)EC;
837
838	if (useNormalizedPaths())
839	llvm::sys::path::remove_dots(path&: Path, /*remove_dot_dot=*/true);
840
841	if (Path.empty())
842	return false;
843
844	detail::InMemoryDirectory *Dir = Root.get();
845	auto I = llvm::sys::path::begin(path: Path), E = sys::path::end(path: Path);
846	const auto ResolvedUser = User.value_or(u: 0);
847	const auto ResolvedGroup = Group.value_or(u: 0);
848	const auto ResolvedType = Type.value_or(u: sys::fs::file_type::regular_file);
849	const auto ResolvedPerms = Perms.value_or(u: sys::fs::all_all);
850	// Any intermediate directories we create should be accessible by
851	// the owner, even if Perms says otherwise for the final path.
852	const auto NewDirectoryPerms = ResolvedPerms | sys::fs::owner_all;
853	while (true) {
854	StringRef Name = *I;
855	detail::InMemoryNode *Node = Dir->getChild(Name);
856	++I;
857	if (!Node) {
858	if (I == E) {
859	// End of the path.
860	Dir->addChild(
861	Name, Child: MakeNode({.DirUID: Dir->getUniqueID(), .Path: Path, .Name: Name, .ModificationTime: ModificationTime,
862	.Buffer: std::move(Buffer), .User: ResolvedUser, .Group: ResolvedGroup,
863	.Type: ResolvedType, .Perms: ResolvedPerms}));
864	return true;
865	}
866
867	// Create a new directory. Use the path up to here.
868	Status Stat(
869	StringRef(Path.str().begin(), Name.end() - Path.str().begin()),
870	getDirectoryID(Parent: Dir->getUniqueID(), Name),
871	llvm::sys::toTimePoint(T: ModificationTime), ResolvedUser, ResolvedGroup,
872	0, sys::fs::file_type::directory_file, NewDirectoryPerms);
873	Dir = cast<detail::InMemoryDirectory>(Val: Dir->addChild(
874	Name, Child: std::make_unique<detail::InMemoryDirectory>(args: std::move(Stat))));
875	continue;
876	}
877
878	if (auto *NewDir = dyn_cast<detail::InMemoryDirectory>(Val: Node)) {
879	Dir = NewDir;
880	} else {
881	assert((isa<detail::InMemoryFile>(Node) ||
882	isa<detail::InMemoryHardLink>(Node)) &&
883	"Must be either file, hardlink or directory!");
884
885	// Trying to insert a directory in place of a file.
886	if (I != E)
887	return false;
888
889	// Return false only if the new file is different from the existing one.
890	if (auto Link = dyn_cast<detail::InMemoryHardLink>(Val: Node)) {
891	return Link->getResolvedFile().getBuffer()->getBuffer() ==
892	Buffer->getBuffer();
893	}
894	return cast<detail::InMemoryFile>(Val: Node)->getBuffer()->getBuffer() ==
895	Buffer->getBuffer();
896	}
897	}
898	}
899
900	bool InMemoryFileSystem::addFile(const Twine &P, time_t ModificationTime,
901	std::unique_ptr<llvm::MemoryBuffer> Buffer,
902	std::optional<uint32_t> User,
903	std::optional<uint32_t> Group,
904	std::optional<llvm::sys::fs::file_type> Type,
905	std::optional<llvm::sys::fs::perms> Perms) {
906	return addFile(P, ModificationTime, Buffer: std::move(Buffer), User, Group, Type,
907	Perms,
908	MakeNode: [](detail::NewInMemoryNodeInfo NNI)
909	-> std::unique_ptr<detail::InMemoryNode> {
910	Status Stat = NNI.makeStatus();
911	if (Stat.getType() == sys::fs::file_type::directory_file)
912	return std::make_unique<detail::InMemoryDirectory>(args&: Stat);
913	return std::make_unique<detail::InMemoryFile>(
914	args&: Stat, args: std::move(NNI.Buffer));
915	});
916	}
917
918	bool InMemoryFileSystem::addFileNoOwn(
919	const Twine &P, time_t ModificationTime,
920	const llvm::MemoryBufferRef &Buffer, std::optional<uint32_t> User,
921	std::optional<uint32_t> Group, std::optional<llvm::sys::fs::file_type> Type,
922	std::optional<llvm::sys::fs::perms> Perms) {
923	return addFile(P, ModificationTime, Buffer: llvm::MemoryBuffer::getMemBuffer(Ref: Buffer),
924	User: std::move(User), Group: std::move(Group), Type: std::move(Type),
925	Perms: std::move(Perms),
926	MakeNode: [](detail::NewInMemoryNodeInfo NNI)
927	-> std::unique_ptr<detail::InMemoryNode> {
928	Status Stat = NNI.makeStatus();
929	if (Stat.getType() == sys::fs::file_type::directory_file)
930	return std::make_unique<detail::InMemoryDirectory>(args&: Stat);
931	return std::make_unique<detail::InMemoryFile>(
932	args&: Stat, args: std::move(NNI.Buffer));
933	});
934	}
935
936	detail::NamedNodeOrError
937	InMemoryFileSystem::lookupNode(const Twine &P, bool FollowFinalSymlink,
938	size_t SymlinkDepth) const {
939	SmallString<128> Path;
940	P.toVector(Out&: Path);
941
942	// Fix up relative paths. This just prepends the current working directory.
943	std::error_code EC = makeAbsolute(Path);
944	assert(!EC);
945	(void)EC;
946
947	if (useNormalizedPaths())
948	llvm::sys::path::remove_dots(path&: Path, /*remove_dot_dot=*/true);
949
950	const detail::InMemoryDirectory *Dir = Root.get();
951	if (Path.empty())
952	return detail::NamedNodeOrError(Path, Dir);
953
954	auto I = llvm::sys::path::begin(path: Path), E = llvm::sys::path::end(path: Path);
955	while (true) {
956	detail::InMemoryNode *Node = Dir->getChild(Name: *I);
957	++I;
958	if (!Node)
959	return errc::no_such_file_or_directory;
960
961	if (auto Symlink = dyn_cast<detail::InMemorySymbolicLink>(Val: Node)) {
962	// If we're at the end of the path, and we're not following through
963	// terminal symlinks, then we're done.
964	if (I == E && !FollowFinalSymlink)
965	return detail::NamedNodeOrError(Path, Symlink);
966
967	if (SymlinkDepth > InMemoryFileSystem::MaxSymlinkDepth)
968	return errc::no_such_file_or_directory;
969
970	SmallString<128> TargetPath = Symlink->getTargetPath();
971	if (std::error_code EC = makeAbsolute(Path&: TargetPath))
972	return EC;
973
974	// Keep going with the target. We always want to follow symlinks here
975	// because we're either at the end of a path that we want to follow, or
976	// not at the end of a path, in which case we need to follow the symlink
977	// regardless.
978	auto Target =
979	lookupNode(P: TargetPath, /*FollowFinalSymlink=*/true, SymlinkDepth: SymlinkDepth + 1);
980	if (!Target || I == E)
981	return Target;
982
983	if (!isa<detail::InMemoryDirectory>(Val: *Target))
984	return errc::no_such_file_or_directory;
985
986	// Otherwise, continue on the search in the symlinked directory.
987	Dir = cast<detail::InMemoryDirectory>(Val: *Target);
988	continue;
989	}
990
991	// Return the file if it's at the end of the path.
992	if (auto File = dyn_cast<detail::InMemoryFile>(Val: Node)) {
993	if (I == E)
994	return detail::NamedNodeOrError(Path, File);
995	return errc::no_such_file_or_directory;
996	}
997
998	// If Node is HardLink then return the resolved file.
999	if (auto File = dyn_cast<detail::InMemoryHardLink>(Val: Node)) {
1000	if (I == E)
1001	return detail::NamedNodeOrError(Path, &File->getResolvedFile());
1002	return errc::no_such_file_or_directory;
1003	}
1004	// Traverse directories.
1005	Dir = cast<detail::InMemoryDirectory>(Val: Node);
1006	if (I == E)
1007	return detail::NamedNodeOrError(Path, Dir);
1008	}
1009	}
1010
1011	bool InMemoryFileSystem::addHardLink(const Twine &NewLink,
1012	const Twine &Target) {
1013	auto NewLinkNode = lookupNode(P: NewLink, /*FollowFinalSymlink=*/false);
1014	// Whether symlinks in the hardlink target are followed is
1015	// implementation-defined in POSIX.
1016	// We're following symlinks here to be consistent with macOS.
1017	auto TargetNode = lookupNode(P: Target, /*FollowFinalSymlink=*/true);
1018	// FromPath must not have been added before. ToPath must have been added
1019	// before. Resolved ToPath must be a File.
1020	if (!TargetNode || NewLinkNode || !isa<detail::InMemoryFile>(Val: *TargetNode))
1021	return false;
1022	return addFile(P: NewLink, ModificationTime: 0, Buffer: nullptr, User: std::nullopt, Group: std::nullopt, Type: std::nullopt,
1023	Perms: std::nullopt, MakeNode: [&](detail::NewInMemoryNodeInfo NNI) {
1024	return std::make_unique<detail::InMemoryHardLink>(
1025	args: NNI.Path.str(),
1026	args: *cast<detail::InMemoryFile>(Val: *TargetNode));
1027	});
1028	}
1029
1030	bool InMemoryFileSystem::addSymbolicLink(
1031	const Twine &NewLink, const Twine &Target, time_t ModificationTime,
1032	std::optional<uint32_t> User, std::optional<uint32_t> Group,
1033	std::optional<llvm::sys::fs::perms> Perms) {
1034	auto NewLinkNode = lookupNode(P: NewLink, /*FollowFinalSymlink=*/false);
1035	if (NewLinkNode)
1036	return false;
1037
1038	SmallString<128> NewLinkStr, TargetStr;
1039	NewLink.toVector(Out&: NewLinkStr);
1040	Target.toVector(Out&: TargetStr);
1041
1042	return addFile(P: NewLinkStr, ModificationTime, Buffer: nullptr, User, Group,
1043	Type: sys::fs::file_type::symlink_file, Perms,
1044	MakeNode: [&](detail::NewInMemoryNodeInfo NNI) {
1045	return std::make_unique<detail::InMemorySymbolicLink>(
1046	args&: NewLinkStr, args&: TargetStr, args: NNI.makeStatus());
1047	});
1048	}
1049
1050	llvm::ErrorOr<Status> InMemoryFileSystem::status(const Twine &Path) {
1051	auto Node = lookupNode(P: Path, /*FollowFinalSymlink=*/true);
1052	if (Node)
1053	return (*Node)->getStatus(RequestedName: Path);
1054	return Node.getError();
1055	}
1056
1057	llvm::ErrorOr<std::unique_ptr<File>>
1058	InMemoryFileSystem::openFileForRead(const Twine &Path) {
1059	auto Node = lookupNode(P: Path,/*FollowFinalSymlink=*/true);
1060	if (!Node)
1061	return Node.getError();
1062
1063	// When we have a file provide a heap-allocated wrapper for the memory buffer
1064	// to match the ownership semantics for File.
1065	if (auto *F = dyn_cast<detail::InMemoryFile>(Val: *Node))
1066	return std::unique_ptr<File>(
1067	new detail::InMemoryFileAdaptor(*F, Path.str()));
1068
1069	// FIXME: errc::not_a_file?
1070	return make_error_code(E: llvm::errc::invalid_argument);
1071	}
1072
1073	/// Adaptor from InMemoryDir::iterator to directory_iterator.
1074	class InMemoryFileSystem::DirIterator : public llvm::vfs::detail::DirIterImpl {
1075	const InMemoryFileSystem *FS;
1076	detail::InMemoryDirectory::const_iterator I;
1077	detail::InMemoryDirectory::const_iterator E;
1078	std::string RequestedDirName;
1079
1080	void setCurrentEntry() {
1081	if (I != E) {
1082	SmallString<256> Path(RequestedDirName);
1083	llvm::sys::path::append(path&: Path, a: I->second->getFileName());
1084	sys::fs::file_type Type = sys::fs::file_type::type_unknown;
1085	switch (I->second->getKind()) {
1086	case detail::IME_File:
1087	case detail::IME_HardLink:
1088	Type = sys::fs::file_type::regular_file;
1089	break;
1090	case detail::IME_Directory:
1091	Type = sys::fs::file_type::directory_file;
1092	break;
1093	case detail::IME_SymbolicLink:
1094	if (auto SymlinkTarget =
1095	FS->lookupNode(P: Path, /*FollowFinalSymlink=*/true)) {
1096	Path = SymlinkTarget.getName();
1097	Type = (*SymlinkTarget)->getStatus(RequestedName: Path).getType();
1098	}
1099	break;
1100	}
1101	CurrentEntry = directory_entry(std::string(Path), Type);
1102	} else {
1103	// When we're at the end, make CurrentEntry invalid and DirIterImpl will
1104	// do the rest.
1105	CurrentEntry = directory_entry();
1106	}
1107	}
1108
1109	public:
1110	DirIterator() = default;
1111
1112	DirIterator(const InMemoryFileSystem *FS,
1113	const detail::InMemoryDirectory &Dir,
1114	std::string RequestedDirName)
1115	: FS(FS), I(Dir.begin()), E(Dir.end()),
1116	RequestedDirName(std::move(RequestedDirName)) {
1117	setCurrentEntry();
1118	}
1119
1120	std::error_code increment() override {
1121	++I;
1122	setCurrentEntry();
1123	return {};
1124	}
1125	};
1126
1127	directory_iterator InMemoryFileSystem::dir_begin(const Twine &Dir,
1128	std::error_code &EC) {
1129	auto Node = lookupNode(P: Dir, /*FollowFinalSymlink=*/true);
1130	if (!Node) {
1131	EC = Node.getError();
1132	return directory_iterator(std::make_shared<DirIterator>());
1133	}
1134
1135	if (auto *DirNode = dyn_cast<detail::InMemoryDirectory>(Val: *Node))
1136	return directory_iterator(
1137	std::make_shared<DirIterator>(args: this, args: *DirNode, args: Dir.str()));
1138
1139	EC = make_error_code(E: llvm::errc::not_a_directory);
1140	return directory_iterator(std::make_shared<DirIterator>());
1141	}
1142
1143	std::error_code InMemoryFileSystem::setCurrentWorkingDirectory(const Twine &P) {
1144	SmallString<128> Path;
1145	P.toVector(Out&: Path);
1146
1147	// Fix up relative paths. This just prepends the current working directory.
1148	std::error_code EC = makeAbsolute(Path);
1149	assert(!EC);
1150	(void)EC;
1151
1152	if (useNormalizedPaths())
1153	llvm::sys::path::remove_dots(path&: Path, /*remove_dot_dot=*/true);
1154
1155	if (!Path.empty())
1156	WorkingDirectory = std::string(Path);
1157	return {};
1158	}
1159
1160	std::error_code
1161	InMemoryFileSystem::getRealPath(const Twine &Path,
1162	SmallVectorImpl<char> &Output) const {
1163	auto CWD = getCurrentWorkingDirectory();
1164	if (!CWD || CWD->empty())
1165	return errc::operation_not_permitted;
1166	Path.toVector(Out&: Output);
1167	if (auto EC = makeAbsolute(Path&: Output))
1168	return EC;
1169	llvm::sys::path::remove_dots(path&: Output, /*remove_dot_dot=*/true);
1170	return {};
1171	}
1172
1173	std::error_code InMemoryFileSystem::isLocal(const Twine &Path, bool &Result) {
1174	Result = false;
1175	return {};
1176	}
1177
1178	void InMemoryFileSystem::printImpl(raw_ostream &OS, PrintType PrintContents,
1179	unsigned IndentLevel) const {
1180	printIndent(OS, IndentLevel);
1181	OS << "InMemoryFileSystem\n";
1182	}
1183
1184	} // namespace vfs
1185	} // namespace llvm
1186
1187	//===-----------------------------------------------------------------------===/
1188	// RedirectingFileSystem implementation
1189	//===-----------------------------------------------------------------------===/
1190
1191	namespace {
1192
1193	static llvm::sys::path::Style getExistingStyle(llvm::StringRef Path) {
1194	// Detect the path style in use by checking the first separator.
1195	llvm::sys::path::Style style = llvm::sys::path::Style::native;
1196	const size_t n = Path.find_first_of(Chars: "/\\");
1197	// Can't distinguish between posix and windows_slash here.
1198	if (n != static_cast<size_t>(-1))
1199	style = (Path[n] == '/') ? llvm::sys::path::Style::posix
1200	: llvm::sys::path::Style::windows_backslash;
1201	return style;
1202	}
1203
1204	/// Removes leading "./" as well as path components like ".." and ".".
1205	static llvm::SmallString<256> canonicalize(llvm::StringRef Path) {
1206	// First detect the path style in use by checking the first separator.
1207	llvm::sys::path::Style style = getExistingStyle(Path);
1208
1209	// Now remove the dots. Explicitly specifying the path style prevents the
1210	// direction of the slashes from changing.
1211	llvm::SmallString<256> result =
1212	llvm::sys::path::remove_leading_dotslash(path: Path, style);
1213	llvm::sys::path::remove_dots(path&: result, /*remove_dot_dot=*/true, style);
1214	return result;
1215	}
1216
1217	/// Whether the error and entry specify a file/directory that was not found.
1218	static bool isFileNotFound(std::error_code EC,
1219	RedirectingFileSystem::Entry *E = nullptr) {
1220	if (E && !isa<RedirectingFileSystem::DirectoryRemapEntry>(Val: E))
1221	return false;
1222	return EC == llvm::errc::no_such_file_or_directory;
1223	}
1224
1225	} // anonymous namespace
1226
1227
1228	RedirectingFileSystem::RedirectingFileSystem(IntrusiveRefCntPtr<FileSystem> FS)
1229	: ExternalFS(std::move(FS)) {
1230	if (ExternalFS)
1231	if (auto ExternalWorkingDirectory =
1232	ExternalFS->getCurrentWorkingDirectory()) {
1233	WorkingDirectory = *ExternalWorkingDirectory;
1234	}
1235	}
1236
1237	/// Directory iterator implementation for \c RedirectingFileSystem's
1238	/// directory entries.
1239	class llvm::vfs::RedirectingFSDirIterImpl
1240	: public llvm::vfs::detail::DirIterImpl {
1241	std::string Dir;
1242	RedirectingFileSystem::DirectoryEntry::iterator Current, End;
1243
1244	std::error_code incrementImpl(bool IsFirstTime) {
1245	assert((IsFirstTime || Current != End) && "cannot iterate past end");
1246	if (!IsFirstTime)
1247	++Current;
1248	if (Current != End) {
1249	SmallString<128> PathStr(Dir);
1250	llvm::sys::path::append(path&: PathStr, a: (*Current)->getName());
1251	sys::fs::file_type Type = sys::fs::file_type::type_unknown;
1252	switch ((*Current)->getKind()) {
1253	case RedirectingFileSystem::EK_Directory:
1254	[[fallthrough]];
1255	case RedirectingFileSystem::EK_DirectoryRemap:
1256	Type = sys::fs::file_type::directory_file;
1257	break;
1258	case RedirectingFileSystem::EK_File:
1259	Type = sys::fs::file_type::regular_file;
1260	break;
1261	}
1262	CurrentEntry = directory_entry(std::string(PathStr), Type);
1263	} else {
1264	CurrentEntry = directory_entry();
1265	}
1266	return {};
1267	};
1268
1269	public:
1270	RedirectingFSDirIterImpl(
1271	const Twine &Path, RedirectingFileSystem::DirectoryEntry::iterator Begin,
1272	RedirectingFileSystem::DirectoryEntry::iterator End, std::error_code &EC)
1273	: Dir(Path.str()), Current(Begin), End(End) {
1274	EC = incrementImpl(/*IsFirstTime=*/true);
1275	}
1276
1277	std::error_code increment() override {
1278	return incrementImpl(/*IsFirstTime=*/false);
1279	}
1280	};
1281
1282	namespace {
1283	/// Directory iterator implementation for \c RedirectingFileSystem's
1284	/// directory remap entries that maps the paths reported by the external
1285	/// file system's directory iterator back to the virtual directory's path.
1286	class RedirectingFSDirRemapIterImpl : public llvm::vfs::detail::DirIterImpl {
1287	std::string Dir;
1288	llvm::sys::path::Style DirStyle;
1289	llvm::vfs::directory_iterator ExternalIter;
1290
1291	public:
1292	RedirectingFSDirRemapIterImpl(std::string DirPath,
1293	llvm::vfs::directory_iterator ExtIter)
1294	: Dir(std::move(DirPath)), DirStyle(getExistingStyle(Path: Dir)),
1295	ExternalIter(ExtIter) {
1296	if (ExternalIter != llvm::vfs::directory_iterator())
1297	setCurrentEntry();
1298	}
1299
1300	void setCurrentEntry() {
1301	StringRef ExternalPath = ExternalIter->path();
1302	llvm::sys::path::Style ExternalStyle = getExistingStyle(Path: ExternalPath);
1303	StringRef File = llvm::sys::path::filename(path: ExternalPath, style: ExternalStyle);
1304
1305	SmallString<128> NewPath(Dir);
1306	llvm::sys::path::append(path&: NewPath, style: DirStyle, a: File);
1307
1308	CurrentEntry = directory_entry(std::string(NewPath), ExternalIter->type());
1309	}
1310
1311	std::error_code increment() override {
1312	std::error_code EC;
1313	ExternalIter.increment(EC);
1314	if (!EC && ExternalIter != llvm::vfs::directory_iterator())
1315	setCurrentEntry();
1316	else
1317	CurrentEntry = directory_entry();
1318	return EC;
1319	}
1320	};
1321	} // namespace
1322
1323	llvm::ErrorOr<std::string>
1324	RedirectingFileSystem::getCurrentWorkingDirectory() const {
1325	return WorkingDirectory;
1326	}
1327
1328	std::error_code
1329	RedirectingFileSystem::setCurrentWorkingDirectory(const Twine &Path) {
1330	// Don't change the working directory if the path doesn't exist.
1331	if (!exists(Path))
1332	return errc::no_such_file_or_directory;
1333
1334	SmallString<128> AbsolutePath;
1335	Path.toVector(Out&: AbsolutePath);
1336	if (std::error_code EC = makeAbsolute(Path&: AbsolutePath))
1337	return EC;
1338	WorkingDirectory = std::string(AbsolutePath);
1339	return {};
1340	}
1341
1342	std::error_code RedirectingFileSystem::isLocal(const Twine &Path_,
1343	bool &Result) {
1344	SmallString<256> Path;
1345	Path_.toVector(Out&: Path);
1346
1347	if (makeCanonical(Path))
1348	return {};
1349
1350	return ExternalFS->isLocal(Path, Result);
1351	}
1352
1353	std::error_code RedirectingFileSystem::makeAbsolute(SmallVectorImpl<char> &Path) const {
1354	// is_absolute(..., Style::windows_*) accepts paths with both slash types.
1355	if (llvm::sys::path::is_absolute(path: Path, style: llvm::sys::path::Style::posix) ||
1356	llvm::sys::path::is_absolute(path: Path,
1357	style: llvm::sys::path::Style::windows_backslash))
1358	// This covers windows absolute path with forward slash as well, as the
1359	// forward slashes are treated as path seperation in llvm::path
1360	// regardless of what path::Style is used.
1361	return {};
1362
1363	auto WorkingDir = getCurrentWorkingDirectory();
1364	if (!WorkingDir)
1365	return WorkingDir.getError();
1366
1367	return makeAbsolute(WorkingDir: WorkingDir.get(), Path);
1368	}
1369
1370	std::error_code
1371	RedirectingFileSystem::makeAbsolute(StringRef WorkingDir,
1372	SmallVectorImpl<char> &Path) const {
1373	// We can't use sys::fs::make_absolute because that assumes the path style
1374	// is native and there is no way to override that. Since we know WorkingDir
1375	// is absolute, we can use it to determine which style we actually have and
1376	// append Path ourselves.
1377	if (!WorkingDir.empty() &&
1378	!sys::path::is_absolute(path: WorkingDir, style: sys::path::Style::posix) &&
1379	!sys::path::is_absolute(path: WorkingDir,
1380	style: sys::path::Style::windows_backslash)) {
1381	return std::error_code();
1382	}
1383	sys::path::Style style = sys::path::Style::windows_backslash;
1384	if (sys::path::is_absolute(path: WorkingDir, style: sys::path::Style::posix)) {
1385	style = sys::path::Style::posix;
1386	} else {
1387	// Distinguish between windows_backslash and windows_slash; getExistingStyle
1388	// returns posix for a path with windows_slash.
1389	if (getExistingStyle(Path: WorkingDir) != sys::path::Style::windows_backslash)
1390	style = sys::path::Style::windows_slash;
1391	}
1392
1393	std::string Result = std::string(WorkingDir);
1394	StringRef Dir(Result);
1395	if (!Dir.ends_with(Suffix: sys::path::get_separator(style))) {
1396	Result += sys::path::get_separator(style);
1397	}
1398	// backslashes '\' are legit path charactors under POSIX. Windows APIs
1399	// like CreateFile accepts forward slashes '/' as path
1400	// separator (even when mixed with backslashes). Therefore,
1401	// `Path` should be directly appended to `WorkingDir` without converting
1402	// path separator.
1403	Result.append(s: Path.data(), n: Path.size());
1404	Path.assign(in_start: Result.begin(), in_end: Result.end());
1405
1406	return {};
1407	}
1408
1409	directory_iterator RedirectingFileSystem::dir_begin(const Twine &Dir,
1410	std::error_code &EC) {
1411	SmallString<256> Path;
1412	Dir.toVector(Out&: Path);
1413
1414	EC = makeCanonical(Path);
1415	if (EC)
1416	return {};
1417
1418	ErrorOr<RedirectingFileSystem::LookupResult> Result = lookupPath(Path);
1419	if (!Result) {
1420	if (Redirection != RedirectKind::RedirectOnly &&
1421	isFileNotFound(EC: Result.getError()))
1422	return ExternalFS->dir_begin(Dir: Path, EC);
1423
1424	EC = Result.getError();
1425	return {};
1426	}
1427
1428	// Use status to make sure the path exists and refers to a directory.
1429	ErrorOr<Status> S = status(CanonicalPath: Path, OriginalPath: Dir, Result: *Result);
1430	if (!S) {
1431	if (Redirection != RedirectKind::RedirectOnly &&
1432	isFileNotFound(EC: S.getError(), E: Result->E))
1433	return ExternalFS->dir_begin(Dir, EC);
1434
1435	EC = S.getError();
1436	return {};
1437	}
1438
1439	if (!S->isDirectory()) {
1440	EC = errc::not_a_directory;
1441	return {};
1442	}
1443
1444	// Create the appropriate directory iterator based on whether we found a
1445	// DirectoryRemapEntry or DirectoryEntry.
1446	directory_iterator RedirectIter;
1447	std::error_code RedirectEC;
1448	if (auto ExtRedirect = Result->getExternalRedirect()) {
1449	auto RE = cast<RedirectingFileSystem::RemapEntry>(Val: Result->E);
1450	RedirectIter = ExternalFS->dir_begin(Dir: *ExtRedirect, EC&: RedirectEC);
1451
1452	if (!RE->useExternalName(GlobalUseExternalName: UseExternalNames)) {
1453	// Update the paths in the results to use the virtual directory's path.
1454	RedirectIter =
1455	directory_iterator(std::make_shared<RedirectingFSDirRemapIterImpl>(
1456	args: std::string(Path), args&: RedirectIter));
1457	}
1458	} else {
1459	auto DE = cast<DirectoryEntry>(Val: Result->E);
1460	RedirectIter =
1461	directory_iterator(std::make_shared<RedirectingFSDirIterImpl>(
1462	args&: Path, args: DE->contents_begin(), args: DE->contents_end(), args&: RedirectEC));
1463	}
1464
1465	if (RedirectEC) {
1466	if (RedirectEC != errc::no_such_file_or_directory) {
1467	EC = RedirectEC;
1468	return {};
1469	}
1470	RedirectIter = {};
1471	}
1472
1473	if (Redirection == RedirectKind::RedirectOnly) {
1474	EC = RedirectEC;
1475	return RedirectIter;
1476	}
1477
1478	std::error_code ExternalEC;
1479	directory_iterator ExternalIter = ExternalFS->dir_begin(Dir: Path, EC&: ExternalEC);
1480	if (ExternalEC) {
1481	if (ExternalEC != errc::no_such_file_or_directory) {
1482	EC = ExternalEC;
1483	return {};
1484	}
1485	ExternalIter = {};
1486	}
1487
1488	SmallVector<directory_iterator, 2> Iters;
1489	switch (Redirection) {
1490	case RedirectKind::Fallthrough:
1491	Iters.push_back(Elt: ExternalIter);
1492	Iters.push_back(Elt: RedirectIter);
1493	break;
1494	case RedirectKind::Fallback:
1495	Iters.push_back(Elt: RedirectIter);
1496	Iters.push_back(Elt: ExternalIter);
1497	break;
1498	default:
1499	llvm_unreachable("unhandled RedirectKind");
1500	}
1501
1502	directory_iterator Combined{
1503	std::make_shared<CombiningDirIterImpl>(args&: Iters, args&: EC)};
1504	if (EC)
1505	return {};
1506	return Combined;
1507	}
1508
1509	void RedirectingFileSystem::setOverlayFileDir(StringRef Dir) {
1510	OverlayFileDir = Dir.str();
1511	}
1512
1513	StringRef RedirectingFileSystem::getOverlayFileDir() const {
1514	return OverlayFileDir;
1515	}
1516
1517	void RedirectingFileSystem::setFallthrough(bool Fallthrough) {
1518	if (Fallthrough) {
1519	Redirection = RedirectingFileSystem::RedirectKind::Fallthrough;
1520	} else {
1521	Redirection = RedirectingFileSystem::RedirectKind::RedirectOnly;
1522	}
1523	}
1524
1525	void RedirectingFileSystem::setRedirection(
1526	RedirectingFileSystem::RedirectKind Kind) {
1527	Redirection = Kind;
1528	}
1529
1530	std::vector<StringRef> RedirectingFileSystem::getRoots() const {
1531	std::vector<StringRef> R;
1532	R.reserve(n: Roots.size());
1533	for (const auto &Root : Roots)
1534	R.push_back(x: Root->getName());
1535	return R;
1536	}
1537
1538	void RedirectingFileSystem::printImpl(raw_ostream &OS, PrintType Type,
1539	unsigned IndentLevel) const {
1540	printIndent(OS, IndentLevel);
1541	OS << "RedirectingFileSystem (UseExternalNames: "
1542	<< (UseExternalNames ? "true" : "false") << ")\n";
1543	if (Type == PrintType::Summary)
1544	return;
1545
1546	for (const auto &Root : Roots)
1547	printEntry(OS, E: Root.get(), IndentLevel);
1548
1549	printIndent(OS, IndentLevel);
1550	OS << "ExternalFS:\n";
1551	ExternalFS->print(OS, Type: Type == PrintType::Contents ? PrintType::Summary : Type,
1552	IndentLevel: IndentLevel + 1);
1553	}
1554
1555	void RedirectingFileSystem::printEntry(raw_ostream &OS,
1556	RedirectingFileSystem::Entry *E,
1557	unsigned IndentLevel) const {
1558	printIndent(OS, IndentLevel);
1559	OS << "'" << E->getName() << "'";
1560
1561	switch (E->getKind()) {
1562	case EK_Directory: {
1563	auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Val: E);
1564
1565	OS << "\n";
1566	for (std::unique_ptr<Entry> &SubEntry :
1567	llvm::make_range(x: DE->contents_begin(), y: DE->contents_end()))
1568	printEntry(OS, E: SubEntry.get(), IndentLevel: IndentLevel + 1);
1569	break;
1570	}
1571	case EK_DirectoryRemap:
1572	case EK_File: {
1573	auto *RE = cast<RedirectingFileSystem::RemapEntry>(Val: E);
1574	OS << " -> '" << RE->getExternalContentsPath() << "'";
1575	switch (RE->getUseName()) {
1576	case NK_NotSet:
1577	break;
1578	case NK_External:
1579	OS << " (UseExternalName: true)";
1580	break;
1581	case NK_Virtual:
1582	OS << " (UseExternalName: false)";
1583	break;
1584	}
1585	OS << "\n";
1586	break;
1587	}
1588	}
1589	}
1590
1591	void RedirectingFileSystem::visitChildFileSystems(VisitCallbackTy Callback) {
1592	if (ExternalFS) {
1593	Callback(*ExternalFS);
1594	ExternalFS->visitChildFileSystems(Callback);
1595	}
1596	}
1597
1598	/// A helper class to hold the common YAML parsing state.
1599	class llvm::vfs::RedirectingFileSystemParser {
1600	yaml::Stream &Stream;
1601
1602	void error(yaml::Node *N, const Twine &Msg) { Stream.printError(N, Msg); }
1603
1604	// false on error
1605	bool parseScalarString(yaml::Node *N, StringRef &Result,
1606	SmallVectorImpl<char> &Storage) {
1607	const auto *S = dyn_cast<yaml::ScalarNode>(Val: N);
1608
1609	if (!S) {
1610	error(N, Msg: "expected string");
1611	return false;
1612	}
1613	Result = S->getValue(Storage);
1614	return true;
1615	}
1616
1617	// false on error
1618	bool parseScalarBool(yaml::Node *N, bool &Result) {
1619	SmallString<5> Storage;
1620	StringRef Value;
1621	if (!parseScalarString(N, Result&: Value, Storage))
1622	return false;
1623
1624	if (Value.equals_insensitive(RHS: "true") || Value.equals_insensitive(RHS: "on") ||
1625	Value.equals_insensitive(RHS: "yes") || Value == "1") {
1626	Result = true;
1627	return true;
1628	} else if (Value.equals_insensitive(RHS: "false") ||
1629	Value.equals_insensitive(RHS: "off") ||
1630	Value.equals_insensitive(RHS: "no") || Value == "0") {
1631	Result = false;
1632	return true;
1633	}
1634
1635	error(N, Msg: "expected boolean value");
1636	return false;
1637	}
1638
1639	std::optional<RedirectingFileSystem::RedirectKind>
1640	parseRedirectKind(yaml::Node *N) {
1641	SmallString<12> Storage;
1642	StringRef Value;
1643	if (!parseScalarString(N, Result&: Value, Storage))
1644	return std::nullopt;
1645
1646	if (Value.equals_insensitive(RHS: "fallthrough")) {
1647	return RedirectingFileSystem::RedirectKind::Fallthrough;
1648	} else if (Value.equals_insensitive(RHS: "fallback")) {
1649	return RedirectingFileSystem::RedirectKind::Fallback;
1650	} else if (Value.equals_insensitive(RHS: "redirect-only")) {
1651	return RedirectingFileSystem::RedirectKind::RedirectOnly;
1652	}
1653	return std::nullopt;
1654	}
1655
1656	std::optional<RedirectingFileSystem::RootRelativeKind>
1657	parseRootRelativeKind(yaml::Node *N) {
1658	SmallString<12> Storage;
1659	StringRef Value;
1660	if (!parseScalarString(N, Result&: Value, Storage))
1661	return std::nullopt;
1662	if (Value.equals_insensitive(RHS: "cwd")) {
1663	return RedirectingFileSystem::RootRelativeKind::CWD;
1664	} else if (Value.equals_insensitive(RHS: "overlay-dir")) {
1665	return RedirectingFileSystem::RootRelativeKind::OverlayDir;
1666	}
1667	return std::nullopt;
1668	}
1669
1670	struct KeyStatus {
1671	bool Required;
1672	bool Seen = false;
1673
1674	KeyStatus(bool Required = false) : Required(Required) {}
1675	};
1676
1677	using KeyStatusPair = std::pair<StringRef, KeyStatus>;
1678
1679	// false on error
1680	bool checkDuplicateOrUnknownKey(yaml::Node *KeyNode, StringRef Key,
1681	DenseMap<StringRef, KeyStatus> &Keys) {
1682	if (!Keys.count(Val: Key)) {
1683	error(N: KeyNode, Msg: "unknown key");
1684	return false;
1685	}
1686	KeyStatus &S = Keys[Key];
1687	if (S.Seen) {
1688	error(N: KeyNode, Msg: Twine("duplicate key '") + Key + "'");
1689	return false;
1690	}
1691	S.Seen = true;
1692	return true;
1693	}
1694
1695	// false on error
1696	bool checkMissingKeys(yaml::Node *Obj, DenseMap<StringRef, KeyStatus> &Keys) {
1697	for (const auto &I : Keys) {
1698	if (I.second.Required && !I.second.Seen) {
1699	error(N: Obj, Msg: Twine("missing key '") + I.first + "'");
1700	return false;
1701	}
1702	}
1703	return true;
1704	}
1705
1706	public:
1707	static RedirectingFileSystem::Entry *
1708	lookupOrCreateEntry(RedirectingFileSystem *FS, StringRef Name,
1709	RedirectingFileSystem::Entry *ParentEntry = nullptr) {
1710	if (!ParentEntry) { // Look for a existent root
1711	for (const auto &Root : FS->Roots) {
1712	if (Name.equals(RHS: Root->getName())) {
1713	ParentEntry = Root.get();
1714	return ParentEntry;
1715	}
1716	}
1717	} else { // Advance to the next component
1718	auto *DE = dyn_cast<RedirectingFileSystem::DirectoryEntry>(Val: ParentEntry);
1719	for (std::unique_ptr<RedirectingFileSystem::Entry> &Content :
1720	llvm::make_range(x: DE->contents_begin(), y: DE->contents_end())) {
1721	auto *DirContent =
1722	dyn_cast<RedirectingFileSystem::DirectoryEntry>(Val: Content.get());
1723	if (DirContent && Name.equals(RHS: Content->getName()))
1724	return DirContent;
1725	}
1726	}
1727
1728	// ... or create a new one
1729	std::unique_ptr<RedirectingFileSystem::Entry> E =
1730	std::make_unique<RedirectingFileSystem::DirectoryEntry>(
1731	args&: Name, args: Status("", getNextVirtualUniqueID(),
1732	std::chrono::system_clock::now(), 0, 0, 0,
1733	file_type::directory_file, sys::fs::all_all));
1734
1735	if (!ParentEntry) { // Add a new root to the overlay
1736	FS->Roots.push_back(x: std::move(E));
1737	ParentEntry = FS->Roots.back().get();
1738	return ParentEntry;
1739	}
1740
1741	auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Val: ParentEntry);
1742	DE->addContent(Content: std::move(E));
1743	return DE->getLastContent();
1744	}
1745
1746	private:
1747	void uniqueOverlayTree(RedirectingFileSystem *FS,
1748	RedirectingFileSystem::Entry *SrcE,
1749	RedirectingFileSystem::Entry *NewParentE = nullptr) {
1750	StringRef Name = SrcE->getName();
1751	switch (SrcE->getKind()) {
1752	case RedirectingFileSystem::EK_Directory: {
1753	auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Val: SrcE);
1754	// Empty directories could be present in the YAML as a way to
1755	// describe a file for a current directory after some of its subdir
1756	// is parsed. This only leads to redundant walks, ignore it.
1757	if (!Name.empty())
1758	NewParentE = lookupOrCreateEntry(FS, Name, ParentEntry: NewParentE);
1759	for (std::unique_ptr<RedirectingFileSystem::Entry> &SubEntry :
1760	llvm::make_range(x: DE->contents_begin(), y: DE->contents_end()))
1761	uniqueOverlayTree(FS, SrcE: SubEntry.get(), NewParentE);
1762	break;
1763	}
1764	case RedirectingFileSystem::EK_DirectoryRemap: {
1765	assert(NewParentE && "Parent entry must exist");
1766	auto *DR = cast<RedirectingFileSystem::DirectoryRemapEntry>(Val: SrcE);
1767	auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Val: NewParentE);
1768	DE->addContent(
1769	Content: std::make_unique<RedirectingFileSystem::DirectoryRemapEntry>(
1770	args&: Name, args: DR->getExternalContentsPath(), args: DR->getUseName()));
1771	break;
1772	}
1773	case RedirectingFileSystem::EK_File: {
1774	assert(NewParentE && "Parent entry must exist");
1775	auto *FE = cast<RedirectingFileSystem::FileEntry>(Val: SrcE);
1776	auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Val: NewParentE);
1777	DE->addContent(Content: std::make_unique<RedirectingFileSystem::FileEntry>(
1778	args&: Name, args: FE->getExternalContentsPath(), args: FE->getUseName()));
1779	break;
1780	}
1781	}
1782	}
1783
1784	std::unique_ptr<RedirectingFileSystem::Entry>
1785	parseEntry(yaml::Node *N, RedirectingFileSystem *FS, bool IsRootEntry) {
1786	auto *M = dyn_cast<yaml::MappingNode>(Val: N);
1787	if (!M) {
1788	error(N, Msg: "expected mapping node for file or directory entry");
1789	return nullptr;
1790	}
1791
1792	KeyStatusPair Fields[] = {
1793	KeyStatusPair("name", true),
1794	KeyStatusPair("type", true),
1795	KeyStatusPair("contents", false),
1796	KeyStatusPair("external-contents", false),
1797	KeyStatusPair("use-external-name", false),
1798	};
1799
1800	DenseMap<StringRef, KeyStatus> Keys(std::begin(arr&: Fields), std::end(arr&: Fields));
1801
1802	enum { CF_NotSet, CF_List, CF_External } ContentsField = CF_NotSet;
1803	std::vector<std::unique_ptr<RedirectingFileSystem::Entry>>
1804	EntryArrayContents;
1805	SmallString<256> ExternalContentsPath;
1806	SmallString<256> Name;
1807	yaml::Node *NameValueNode = nullptr;
1808	auto UseExternalName = RedirectingFileSystem::NK_NotSet;
1809	RedirectingFileSystem::EntryKind Kind;
1810
1811	for (auto &I : *M) {
1812	StringRef Key;
1813	// Reuse the buffer for key and value, since we don't look at key after
1814	// parsing value.
1815	SmallString<256> Buffer;
1816	if (!parseScalarString(N: I.getKey(), Result&: Key, Storage&: Buffer))
1817	return nullptr;
1818
1819	if (!checkDuplicateOrUnknownKey(KeyNode: I.getKey(), Key, Keys))
1820	return nullptr;
1821
1822	StringRef Value;
1823	if (Key == "name") {
1824	if (!parseScalarString(N: I.getValue(), Result&: Value, Storage&: Buffer))
1825	return nullptr;
1826
1827	NameValueNode = I.getValue();
1828	// Guarantee that old YAML files containing paths with ".." and "."
1829	// are properly canonicalized before read into the VFS.
1830	Name = canonicalize(Path: Value).str();
1831	} else if (Key == "type") {
1832	if (!parseScalarString(N: I.getValue(), Result&: Value, Storage&: Buffer))
1833	return nullptr;
1834	if (Value == "file")
1835	Kind = RedirectingFileSystem::EK_File;
1836	else if (Value == "directory")
1837	Kind = RedirectingFileSystem::EK_Directory;
1838	else if (Value == "directory-remap")
1839	Kind = RedirectingFileSystem::EK_DirectoryRemap;
1840	else {
1841	error(N: I.getValue(), Msg: "unknown value for 'type'");
1842	return nullptr;
1843	}
1844	} else if (Key == "contents") {
1845	if (ContentsField != CF_NotSet) {
1846	error(N: I.getKey(),
1847	Msg: "entry already has 'contents' or 'external-contents'");
1848	return nullptr;
1849	}
1850	ContentsField = CF_List;
1851	auto *Contents = dyn_cast<yaml::SequenceNode>(Val: I.getValue());
1852	if (!Contents) {
1853	// FIXME: this is only for directories, what about files?
1854	error(N: I.getValue(), Msg: "expected array");
1855	return nullptr;
1856	}
1857
1858	for (auto &I : *Contents) {
1859	if (std::unique_ptr<RedirectingFileSystem::Entry> E =
1860	parseEntry(N: &I, FS, /*IsRootEntry*/ false))
1861	EntryArrayContents.push_back(x: std::move(E));
1862	else
1863	return nullptr;
1864	}
1865	} else if (Key == "external-contents") {
1866	if (ContentsField != CF_NotSet) {
1867	error(N: I.getKey(),
1868	Msg: "entry already has 'contents' or 'external-contents'");
1869	return nullptr;
1870	}
1871	ContentsField = CF_External;
1872	if (!parseScalarString(N: I.getValue(), Result&: Value, Storage&: Buffer))
1873	return nullptr;
1874
1875	SmallString<256> FullPath;
1876	if (FS->IsRelativeOverlay) {
1877	FullPath = FS->getOverlayFileDir();
1878	assert(!FullPath.empty() &&
1879	"External contents prefix directory must exist");
1880	llvm::sys::path::append(path&: FullPath, a: Value);
1881	} else {
1882	FullPath = Value;
1883	}
1884
1885	// Guarantee that old YAML files containing paths with ".." and "."
1886	// are properly canonicalized before read into the VFS.
1887	FullPath = canonicalize(Path: FullPath);
1888	ExternalContentsPath = FullPath.str();
1889	} else if (Key == "use-external-name") {
1890	bool Val;
1891	if (!parseScalarBool(N: I.getValue(), Result&: Val))
1892	return nullptr;
1893	UseExternalName = Val ? RedirectingFileSystem::NK_External
1894	: RedirectingFileSystem::NK_Virtual;
1895	} else {
1896	llvm_unreachable("key missing from Keys");
1897	}
1898	}
1899
1900	if (Stream.failed())
1901	return nullptr;
1902
1903	// check for missing keys
1904	if (ContentsField == CF_NotSet) {
1905	error(N, Msg: "missing key 'contents' or 'external-contents'");
1906	return nullptr;
1907	}
1908	if (!checkMissingKeys(Obj: N, Keys))
1909	return nullptr;
1910
1911	// check invalid configuration
1912	if (Kind == RedirectingFileSystem::EK_Directory &&
1913	UseExternalName != RedirectingFileSystem::NK_NotSet) {
1914	error(N, Msg: "'use-external-name' is not supported for 'directory' entries");
1915	return nullptr;
1916	}
1917
1918	if (Kind == RedirectingFileSystem::EK_DirectoryRemap &&
1919	ContentsField == CF_List) {
1920	error(N, Msg: "'contents' is not supported for 'directory-remap' entries");
1921	return nullptr;
1922	}
1923
1924	sys::path::Style path_style = sys::path::Style::native;
1925	if (IsRootEntry) {
1926	// VFS root entries may be in either Posix or Windows style. Figure out
1927	// which style we have, and use it consistently.
1928	if (sys::path::is_absolute(path: Name, style: sys::path::Style::posix)) {
1929	path_style = sys::path::Style::posix;
1930	} else if (sys::path::is_absolute(path: Name,
1931	style: sys::path::Style::windows_backslash)) {
1932	path_style = sys::path::Style::windows_backslash;
1933	} else {
1934	// Relative VFS root entries are made absolute to either the overlay
1935	// directory, or the current working directory, then we can determine
1936	// the path style from that.
1937	std::error_code EC;
1938	if (FS->RootRelative ==
1939	RedirectingFileSystem::RootRelativeKind::OverlayDir) {
1940	StringRef FullPath = FS->getOverlayFileDir();
1941	assert(!FullPath.empty() && "Overlay file directory must exist");
1942	EC = FS->makeAbsolute(WorkingDir: FullPath, Path&: Name);
1943	Name = canonicalize(Path: Name);
1944	} else {
1945	EC = sys::fs::make_absolute(path&: Name);
1946	}
1947	if (EC) {
1948	assert(NameValueNode && "Name presence should be checked earlier");
1949	error(
1950	N: NameValueNode,
1951	Msg: "entry with relative path at the root level is not discoverable");
1952	return nullptr;
1953	}
1954	path_style = sys::path::is_absolute(path: Name, style: sys::path::Style::posix)
1955	? sys::path::Style::posix
1956	: sys::path::Style::windows_backslash;
1957	}
1958	// is::path::is_absolute(Name, sys::path::Style::windows_backslash) will
1959	// return true even if `Name` is using forward slashes. Distinguish
1960	// between windows_backslash and windows_slash.
1961	if (path_style == sys::path::Style::windows_backslash &&
1962	getExistingStyle(Path: Name) != sys::path::Style::windows_backslash)
1963	path_style = sys::path::Style::windows_slash;
1964	}
1965
1966	// Remove trailing slash(es), being careful not to remove the root path
1967	StringRef Trimmed = Name;
1968	size_t RootPathLen = sys::path::root_path(path: Trimmed, style: path_style).size();
1969	while (Trimmed.size() > RootPathLen &&
1970	sys::path::is_separator(value: Trimmed.back(), style: path_style))
1971	Trimmed = Trimmed.slice(Start: 0, End: Trimmed.size() - 1);
1972
1973	// Get the last component
1974	StringRef LastComponent = sys::path::filename(path: Trimmed, style: path_style);
1975
1976	std::unique_ptr<RedirectingFileSystem::Entry> Result;
1977	switch (Kind) {
1978	case RedirectingFileSystem::EK_File:
1979	Result = std::make_unique<RedirectingFileSystem::FileEntry>(
1980	args&: LastComponent, args: std::move(ExternalContentsPath), args&: UseExternalName);
1981	break;
1982	case RedirectingFileSystem::EK_DirectoryRemap:
1983	Result = std::make_unique<RedirectingFileSystem::DirectoryRemapEntry>(
1984	args&: LastComponent, args: std::move(ExternalContentsPath), args&: UseExternalName);
1985	break;
1986	case RedirectingFileSystem::EK_Directory:
1987	Result = std::make_unique<RedirectingFileSystem::DirectoryEntry>(
1988	args&: LastComponent, args: std::move(EntryArrayContents),
1989	args: Status("", getNextVirtualUniqueID(), std::chrono::system_clock::now(),
1990	0, 0, 0, file_type::directory_file, sys::fs::all_all));
1991	break;
1992	}
1993
1994	StringRef Parent = sys::path::parent_path(path: Trimmed, style: path_style);
1995	if (Parent.empty())
1996	return Result;
1997
1998	// if 'name' contains multiple components, create implicit directory entries
1999	for (sys::path::reverse_iterator I = sys::path::rbegin(path: Parent, style: path_style),
2000	E = sys::path::rend(path: Parent);
2001	I != E; ++I) {
2002	std::vector<std::unique_ptr<RedirectingFileSystem::Entry>> Entries;
2003	Entries.push_back(x: std::move(Result));
2004	Result = std::make_unique<RedirectingFileSystem::DirectoryEntry>(
2005	args: *I, args: std::move(Entries),
2006	args: Status("", getNextVirtualUniqueID(), std::chrono::system_clock::now(),
2007	0, 0, 0, file_type::directory_file, sys::fs::all_all));
2008	}
2009	return Result;
2010	}
2011
2012	public:
2013	RedirectingFileSystemParser(yaml::Stream &S) : Stream(S) {}
2014
2015	// false on error
2016	bool parse(yaml::Node *Root, RedirectingFileSystem *FS) {
2017	auto *Top = dyn_cast<yaml::MappingNode>(Val: Root);
2018	if (!Top) {
2019	error(N: Root, Msg: "expected mapping node");
2020	return false;
2021	}
2022
2023	KeyStatusPair Fields[] = {
2024	KeyStatusPair("version", true),
2025	KeyStatusPair("case-sensitive", false),
2026	KeyStatusPair("use-external-names", false),
2027	KeyStatusPair("root-relative", false),
2028	KeyStatusPair("overlay-relative", false),
2029	KeyStatusPair("fallthrough", false),
2030	KeyStatusPair("redirecting-with", false),
2031	KeyStatusPair("roots", true),
2032	};
2033
2034	DenseMap<StringRef, KeyStatus> Keys(std::begin(arr&: Fields), std::end(arr&: Fields));
2035	std::vector<std::unique_ptr<RedirectingFileSystem::Entry>> RootEntries;
2036
2037	// Parse configuration and 'roots'
2038	for (auto &I : *Top) {
2039	SmallString<10> KeyBuffer;
2040	StringRef Key;
2041	if (!parseScalarString(N: I.getKey(), Result&: Key, Storage&: KeyBuffer))
2042	return false;
2043
2044	if (!checkDuplicateOrUnknownKey(KeyNode: I.getKey(), Key, Keys))
2045	return false;
2046
2047	if (Key == "roots") {
2048	auto *Roots = dyn_cast<yaml::SequenceNode>(Val: I.getValue());
2049	if (!Roots) {
2050	error(N: I.getValue(), Msg: "expected array");
2051	return false;
2052	}
2053
2054	for (auto &I : *Roots) {
2055	if (std::unique_ptr<RedirectingFileSystem::Entry> E =
2056	parseEntry(N: &I, FS, /*IsRootEntry*/ true))
2057	RootEntries.push_back(x: std::move(E));
2058	else
2059	return false;
2060	}
2061	} else if (Key == "version") {
2062	StringRef VersionString;
2063	SmallString<4> Storage;
2064	if (!parseScalarString(N: I.getValue(), Result&: VersionString, Storage))
2065	return false;
2066	int Version;
2067	if (VersionString.getAsInteger<int>(Radix: 10, Result&: Version)) {
2068	error(N: I.getValue(), Msg: "expected integer");
2069	return false;
2070	}
2071	if (Version < 0) {
2072	error(N: I.getValue(), Msg: "invalid version number");
2073	return false;
2074	}
2075	if (Version != 0) {
2076	error(N: I.getValue(), Msg: "version mismatch, expected 0");
2077	return false;
2078	}
2079	} else if (Key == "case-sensitive") {
2080	if (!parseScalarBool(N: I.getValue(), Result&: FS->CaseSensitive))
2081	return false;
2082	} else if (Key == "overlay-relative") {
2083	if (!parseScalarBool(N: I.getValue(), Result&: FS->IsRelativeOverlay))
2084	return false;
2085	} else if (Key == "use-external-names") {
2086	if (!parseScalarBool(N: I.getValue(), Result&: FS->UseExternalNames))
2087	return false;
2088	} else if (Key == "fallthrough") {
2089	if (Keys["redirecting-with"].Seen) {
2090	error(N: I.getValue(),
2091	Msg: "'fallthrough' and 'redirecting-with' are mutually exclusive");
2092	return false;
2093	}
2094
2095	bool ShouldFallthrough = false;
2096	if (!parseScalarBool(N: I.getValue(), Result&: ShouldFallthrough))
2097	return false;
2098
2099	if (ShouldFallthrough) {
2100	FS->Redirection = RedirectingFileSystem::RedirectKind::Fallthrough;
2101	} else {
2102	FS->Redirection = RedirectingFileSystem::RedirectKind::RedirectOnly;
2103	}
2104	} else if (Key == "redirecting-with") {
2105	if (Keys["fallthrough"].Seen) {
2106	error(N: I.getValue(),
2107	Msg: "'fallthrough' and 'redirecting-with' are mutually exclusive");
2108	return false;
2109	}
2110
2111	if (auto Kind = parseRedirectKind(N: I.getValue())) {
2112	FS->Redirection = *Kind;
2113	} else {
2114	error(N: I.getValue(), Msg: "expected valid redirect kind");
2115	return false;
2116	}
2117	} else if (Key == "root-relative") {
2118	if (auto Kind = parseRootRelativeKind(N: I.getValue())) {
2119	FS->RootRelative = *Kind;
2120	} else {
2121	error(N: I.getValue(), Msg: "expected valid root-relative kind");
2122	return false;
2123	}
2124	} else {
2125	llvm_unreachable("key missing from Keys");
2126	}
2127	}
2128
2129	if (Stream.failed())
2130	return false;
2131
2132	if (!checkMissingKeys(Obj: Top, Keys))
2133	return false;
2134
2135	// Now that we sucessefully parsed the YAML file, canonicalize the internal
2136	// representation to a proper directory tree so that we can search faster
2137	// inside the VFS.
2138	for (auto &E : RootEntries)
2139	uniqueOverlayTree(FS, SrcE: E.get());
2140
2141	return true;
2142	}
2143	};
2144
2145	std::unique_ptr<RedirectingFileSystem>
2146	RedirectingFileSystem::create(std::unique_ptr<MemoryBuffer> Buffer,
2147	SourceMgr::DiagHandlerTy DiagHandler,
2148	StringRef YAMLFilePath, void *DiagContext,
2149	IntrusiveRefCntPtr<FileSystem> ExternalFS) {
2150	SourceMgr SM;
2151	yaml::Stream Stream(Buffer->getMemBufferRef(), SM);
2152
2153	SM.setDiagHandler(DH: DiagHandler, Ctx: DiagContext);
2154	yaml::document_iterator DI = Stream.begin();
2155	yaml::Node *Root = DI->getRoot();
2156	if (DI == Stream.end() || !Root) {
2157	SM.PrintMessage(Loc: SMLoc(), Kind: SourceMgr::DK_Error, Msg: "expected root node");
2158	return nullptr;
2159	}
2160
2161	RedirectingFileSystemParser P(Stream);
2162
2163	std::unique_ptr<RedirectingFileSystem> FS(
2164	new RedirectingFileSystem(ExternalFS));
2165
2166	if (!YAMLFilePath.empty()) {
2167	// Use the YAML path from -ivfsoverlay to compute the dir to be prefixed
2168	// to each 'external-contents' path.
2169	//
2170	// Example:
2171	// -ivfsoverlay dummy.cache/vfs/vfs.yaml
2172	// yields:
2173	// FS->OverlayFileDir => /<absolute_path_to>/dummy.cache/vfs
2174	//
2175	SmallString<256> OverlayAbsDir = sys::path::parent_path(path: YAMLFilePath);
2176	std::error_code EC = llvm::sys::fs::make_absolute(path&: OverlayAbsDir);
2177	assert(!EC && "Overlay dir final path must be absolute");
2178	(void)EC;
2179	FS->setOverlayFileDir(OverlayAbsDir);
2180	}
2181
2182	if (!P.parse(Root, FS: FS.get()))
2183	return nullptr;
2184
2185	return FS;
2186	}
2187
2188	std::unique_ptr<RedirectingFileSystem> RedirectingFileSystem::create(
2189	ArrayRef<std::pair<std::string, std::string>> RemappedFiles,
2190	bool UseExternalNames, FileSystem &ExternalFS) {
2191	std::unique_ptr<RedirectingFileSystem> FS(
2192	new RedirectingFileSystem(&ExternalFS));
2193	FS->UseExternalNames = UseExternalNames;
2194
2195	StringMap<RedirectingFileSystem::Entry *> Entries;
2196
2197	for (auto &Mapping : llvm::reverse(C&: RemappedFiles)) {
2198	SmallString<128> From = StringRef(Mapping.first);
2199	SmallString<128> To = StringRef(Mapping.second);
2200	{
2201	auto EC = ExternalFS.makeAbsolute(Path&: From);
2202	(void)EC;
2203	assert(!EC && "Could not make absolute path");
2204	}
2205
2206	// Check if we've already mapped this file. The first one we see (in the
2207	// reverse iteration) wins.
2208	RedirectingFileSystem::Entry *&ToEntry = Entries[From];
2209	if (ToEntry)
2210	continue;
2211
2212	// Add parent directories.
2213	RedirectingFileSystem::Entry *Parent = nullptr;
2214	StringRef FromDirectory = llvm::sys::path::parent_path(path: From);
2215	for (auto I = llvm::sys::path::begin(path: FromDirectory),
2216	E = llvm::sys::path::end(path: FromDirectory);
2217	I != E; ++I) {
2218	Parent = RedirectingFileSystemParser::lookupOrCreateEntry(FS: FS.get(), Name: *I,
2219	ParentEntry: Parent);
2220	}
2221	assert(Parent && "File without a directory?");
2222	{
2223	auto EC = ExternalFS.makeAbsolute(Path&: To);
2224	(void)EC;
2225	assert(!EC && "Could not make absolute path");
2226	}
2227
2228	// Add the file.
2229	auto NewFile = std::make_unique<RedirectingFileSystem::FileEntry>(
2230	args: llvm::sys::path::filename(path: From), args&: To,
2231	args: UseExternalNames ? RedirectingFileSystem::NK_External
2232	: RedirectingFileSystem::NK_Virtual);
2233	ToEntry = NewFile.get();
2234	cast<RedirectingFileSystem::DirectoryEntry>(Val: Parent)->addContent(
2235	Content: std::move(NewFile));
2236	}
2237
2238	return FS;
2239	}
2240
2241	RedirectingFileSystem::LookupResult::LookupResult(
2242	Entry *E, sys::path::const_iterator Start, sys::path::const_iterator End)
2243	: E(E) {
2244	assert(E != nullptr);
2245	// If the matched entry is a DirectoryRemapEntry, set ExternalRedirect to the
2246	// path of the directory it maps to in the external file system plus any
2247	// remaining path components in the provided iterator.
2248	if (auto *DRE = dyn_cast<RedirectingFileSystem::DirectoryRemapEntry>(Val: E)) {
2249	SmallString<256> Redirect(DRE->getExternalContentsPath());
2250	sys::path::append(path&: Redirect, begin: Start, end: End,
2251	style: getExistingStyle(Path: DRE->getExternalContentsPath()));
2252	ExternalRedirect = std::string(Redirect);
2253	}
2254	}
2255
2256	void RedirectingFileSystem::LookupResult::getPath(
2257	llvm::SmallVectorImpl<char> &Result) const {
2258	Result.clear();
2259	for (Entry *Parent : Parents)
2260	llvm::sys::path::append(path&: Result, a: Parent->getName());
2261	llvm::sys::path::append(path&: Result, a: E->getName());
2262	}
2263
2264	std::error_code
2265	RedirectingFileSystem::makeCanonical(SmallVectorImpl<char> &Path) const {
2266	if (std::error_code EC = makeAbsolute(Path))
2267	return EC;
2268
2269	llvm::SmallString<256> CanonicalPath =
2270	canonicalize(Path: StringRef(Path.data(), Path.size()));
2271	if (CanonicalPath.empty())
2272	return make_error_code(E: llvm::errc::invalid_argument);
2273
2274	Path.assign(in_start: CanonicalPath.begin(), in_end: CanonicalPath.end());
2275	return {};
2276	}
2277
2278	ErrorOr<RedirectingFileSystem::LookupResult>
2279	RedirectingFileSystem::lookupPath(StringRef Path) const {
2280	// RedirectOnly means the VFS is always used.
2281	if (UsageTrackingActive && Redirection == RedirectKind::RedirectOnly)
2282	HasBeenUsed = true;
2283
2284	sys::path::const_iterator Start = sys::path::begin(path: Path);
2285	sys::path::const_iterator End = sys::path::end(path: Path);
2286	llvm::SmallVector<Entry *, 32> Entries;
2287	for (const auto &Root : Roots) {
2288	ErrorOr<RedirectingFileSystem::LookupResult> Result =
2289	lookupPathImpl(Start, End, From: Root.get(), Entries);
2290	if (UsageTrackingActive && Result && isa<RemapEntry>(Val: Result->E))
2291	HasBeenUsed = true;
2292	if (Result || Result.getError() != llvm::errc::no_such_file_or_directory) {
2293	Result->Parents = std::move(Entries);
2294	return Result;
2295	}
2296	}
2297	return make_error_code(E: llvm::errc::no_such_file_or_directory);
2298	}
2299
2300	ErrorOr<RedirectingFileSystem::LookupResult>
2301	RedirectingFileSystem::lookupPathImpl(
2302	sys::path::const_iterator Start, sys::path::const_iterator End,
2303	RedirectingFileSystem::Entry *From,
2304	llvm::SmallVectorImpl<Entry *> &Entries) const {
2305	assert(!isTraversalComponent(*Start) &&
2306	!isTraversalComponent(From->getName()) &&
2307	"Paths should not contain traversal components");
2308
2309	StringRef FromName = From->getName();
2310
2311	// Forward the search to the next component in case this is an empty one.
2312	if (!FromName.empty()) {
2313	if (!pathComponentMatches(lhs: *Start, rhs: FromName))
2314	return make_error_code(E: llvm::errc::no_such_file_or_directory);
2315
2316	++Start;
2317
2318	if (Start == End) {
2319	// Match!
2320	return LookupResult(From, Start, End);
2321	}
2322	}
2323
2324	if (isa<RedirectingFileSystem::FileEntry>(Val: From))
2325	return make_error_code(E: llvm::errc::not_a_directory);
2326
2327	if (isa<RedirectingFileSystem::DirectoryRemapEntry>(Val: From))
2328	return LookupResult(From, Start, End);
2329
2330	auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Val: From);
2331	for (const std::unique_ptr<RedirectingFileSystem::Entry> &DirEntry :
2332	llvm::make_range(x: DE->contents_begin(), y: DE->contents_end())) {
2333	Entries.push_back(Elt: From);
2334	ErrorOr<RedirectingFileSystem::LookupResult> Result =
2335	lookupPathImpl(Start, End, From: DirEntry.get(), Entries);
2336	if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
2337	return Result;
2338	Entries.pop_back();
2339	}
2340
2341	return make_error_code(E: llvm::errc::no_such_file_or_directory);
2342	}
2343
2344	static Status getRedirectedFileStatus(const Twine &OriginalPath,
2345	bool UseExternalNames,
2346	Status ExternalStatus) {
2347	// The path has been mapped by some nested VFS and exposes an external path,
2348	// don't override it with the original path.
2349	if (ExternalStatus.ExposesExternalVFSPath)
2350	return ExternalStatus;
2351
2352	Status S = ExternalStatus;
2353	if (!UseExternalNames)
2354	S = Status::copyWithNewName(In: S, NewName: OriginalPath);
2355	else
2356	S.ExposesExternalVFSPath = true;
2357	return S;
2358	}
2359
2360	ErrorOr<Status> RedirectingFileSystem::status(
2361	const Twine &CanonicalPath, const Twine &OriginalPath,
2362	const RedirectingFileSystem::LookupResult &Result) {
2363	if (std::optional<StringRef> ExtRedirect = Result.getExternalRedirect()) {
2364	SmallString<256> CanonicalRemappedPath((*ExtRedirect).str());
2365	if (std::error_code EC = makeCanonical(Path&: CanonicalRemappedPath))
2366	return EC;
2367
2368	ErrorOr<Status> S = ExternalFS->status(Path: CanonicalRemappedPath);
2369	if (!S)
2370	return S;
2371	S = Status::copyWithNewName(In: *S, NewName: *ExtRedirect);
2372	auto *RE = cast<RedirectingFileSystem::RemapEntry>(Val: Result.E);
2373	return getRedirectedFileStatus(OriginalPath,
2374	UseExternalNames: RE->useExternalName(GlobalUseExternalName: UseExternalNames), ExternalStatus: *S);
2375	}
2376
2377	auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Val: Result.E);
2378	return Status::copyWithNewName(In: DE->getStatus(), NewName: CanonicalPath);
2379	}
2380
2381	ErrorOr<Status>
2382	RedirectingFileSystem::getExternalStatus(const Twine &CanonicalPath,
2383	const Twine &OriginalPath) const {
2384	auto Result = ExternalFS->status(Path: CanonicalPath);
2385
2386	// The path has been mapped by some nested VFS, don't override it with the
2387	// original path.
2388	if (!Result || Result->ExposesExternalVFSPath)
2389	return Result;
2390	return Status::copyWithNewName(In: Result.get(), NewName: OriginalPath);
2391	}
2392
2393	ErrorOr<Status> RedirectingFileSystem::status(const Twine &OriginalPath) {
2394	SmallString<256> CanonicalPath;
2395	OriginalPath.toVector(Out&: CanonicalPath);
2396
2397	if (std::error_code EC = makeCanonical(Path&: CanonicalPath))
2398	return EC;
2399
2400	if (Redirection == RedirectKind::Fallback) {
2401	// Attempt to find the original file first, only falling back to the
2402	// mapped file if that fails.
2403	ErrorOr<Status> S = getExternalStatus(CanonicalPath, OriginalPath);
2404	if (S)
2405	return S;
2406	}
2407
2408	ErrorOr<RedirectingFileSystem::LookupResult> Result =
2409	lookupPath(Path: CanonicalPath);
2410	if (!Result) {
2411	// Was not able to map file, fallthrough to using the original path if
2412	// that was the specified redirection type.
2413	if (Redirection == RedirectKind::Fallthrough &&
2414	isFileNotFound(EC: Result.getError()))
2415	return getExternalStatus(CanonicalPath, OriginalPath);
2416	return Result.getError();
2417	}
2418
2419	ErrorOr<Status> S = status(CanonicalPath, OriginalPath, Result: *Result);
2420	if (!S && Redirection == RedirectKind::Fallthrough &&
2421	isFileNotFound(EC: S.getError(), E: Result->E)) {
2422	// Mapped the file but it wasn't found in the underlying filesystem,
2423	// fallthrough to using the original path if that was the specified
2424	// redirection type.
2425	return getExternalStatus(CanonicalPath, OriginalPath);
2426	}
2427
2428	return S;
2429	}
2430
2431	namespace {
2432
2433	/// Provide a file wrapper with an overriden status.
2434	class FileWithFixedStatus : public File {
2435	std::unique_ptr<File> InnerFile;
2436	Status S;
2437
2438	public:
2439	FileWithFixedStatus(std::unique_ptr<File> InnerFile, Status S)
2440	: InnerFile(std::move(InnerFile)), S(std::move(S)) {}
2441
2442	ErrorOr<Status> status() override { return S; }
2443	ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
2444
2445	getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
2446	bool IsVolatile) override {
2447	return InnerFile->getBuffer(Name, FileSize, RequiresNullTerminator,
2448	IsVolatile);
2449	}
2450
2451	std::error_code close() override { return InnerFile->close(); }
2452
2453	void setPath(const Twine &Path) override { S = S.copyWithNewName(In: S, NewName: Path); }
2454	};
2455
2456	} // namespace
2457
2458	ErrorOr<std::unique_ptr<File>>
2459	File::getWithPath(ErrorOr<std::unique_ptr<File>> Result, const Twine &P) {
2460	// See \c getRedirectedFileStatus - don't update path if it's exposing an
2461	// external path.
2462	if (!Result || (*Result)->status()->ExposesExternalVFSPath)
2463	return Result;
2464
2465	ErrorOr<std::unique_ptr<File>> F = std::move(*Result);
2466	auto Name = F->get()->getName();
2467	if (Name && Name.get() != P.str())
2468	F->get()->setPath(P);
2469	return F;
2470	}
2471
2472	ErrorOr<std::unique_ptr<File>>
2473	RedirectingFileSystem::openFileForRead(const Twine &OriginalPath) {
2474	SmallString<256> CanonicalPath;
2475	OriginalPath.toVector(Out&: CanonicalPath);
2476
2477	if (std::error_code EC = makeCanonical(Path&: CanonicalPath))
2478	return EC;
2479
2480	if (Redirection == RedirectKind::Fallback) {
2481	// Attempt to find the original file first, only falling back to the
2482	// mapped file if that fails.
2483	auto F = File::getWithPath(Result: ExternalFS->openFileForRead(Path: CanonicalPath),
2484	P: OriginalPath);
2485	if (F)
2486	return F;
2487	}
2488
2489	ErrorOr<RedirectingFileSystem::LookupResult> Result =
2490	lookupPath(Path: CanonicalPath);
2491	if (!Result) {
2492	// Was not able to map file, fallthrough to using the original path if
2493	// that was the specified redirection type.
2494	if (Redirection == RedirectKind::Fallthrough &&
2495	isFileNotFound(EC: Result.getError()))
2496	return File::getWithPath(Result: ExternalFS->openFileForRead(Path: CanonicalPath),
2497	P: OriginalPath);
2498	return Result.getError();
2499	}
2500
2501	if (!Result->getExternalRedirect()) // FIXME: errc::not_a_file?
2502	return make_error_code(E: llvm::errc::invalid_argument);
2503
2504	StringRef ExtRedirect = *Result->getExternalRedirect();
2505	SmallString<256> CanonicalRemappedPath(ExtRedirect.str());
2506	if (std::error_code EC = makeCanonical(Path&: CanonicalRemappedPath))
2507	return EC;
2508
2509	auto *RE = cast<RedirectingFileSystem::RemapEntry>(Val: Result->E);
2510
2511	auto ExternalFile = File::getWithPath(
2512	Result: ExternalFS->openFileForRead(Path: CanonicalRemappedPath), P: ExtRedirect);
2513	if (!ExternalFile) {
2514	if (Redirection == RedirectKind::Fallthrough &&
2515	isFileNotFound(EC: ExternalFile.getError(), E: Result->E)) {
2516	// Mapped the file but it wasn't found in the underlying filesystem,
2517	// fallthrough to using the original path if that was the specified
2518	// redirection type.
2519	return File::getWithPath(Result: ExternalFS->openFileForRead(Path: CanonicalPath),
2520	P: OriginalPath);
2521	}
2522	return ExternalFile;
2523	}
2524
2525	auto ExternalStatus = (*ExternalFile)->status();
2526	if (!ExternalStatus)
2527	return ExternalStatus.getError();
2528
2529	// Otherwise, the file was successfully remapped. Mark it as such. Also
2530	// replace the underlying path if the external name is being used.
2531	Status S = getRedirectedFileStatus(
2532	OriginalPath, UseExternalNames: RE->useExternalName(GlobalUseExternalName: UseExternalNames), ExternalStatus: *ExternalStatus);
2533	return std::unique_ptr<File>(
2534	std::make_unique<FileWithFixedStatus>(args: std::move(*ExternalFile), args&: S));
2535	}
2536
2537	std::error_code
2538	RedirectingFileSystem::getRealPath(const Twine &OriginalPath,
2539	SmallVectorImpl<char> &Output) const {
2540	SmallString<256> CanonicalPath;
2541	OriginalPath.toVector(Out&: CanonicalPath);
2542
2543	if (std::error_code EC = makeCanonical(Path&: CanonicalPath))
2544	return EC;
2545
2546	if (Redirection == RedirectKind::Fallback) {
2547	// Attempt to find the original file first, only falling back to the
2548	// mapped file if that fails.
2549	std::error_code EC = ExternalFS->getRealPath(Path: CanonicalPath, Output);
2550	if (!EC)
2551	return EC;
2552	}
2553
2554	ErrorOr<RedirectingFileSystem::LookupResult> Result =
2555	lookupPath(Path: CanonicalPath);
2556	if (!Result) {
2557	// Was not able to map file, fallthrough to using the original path if
2558	// that was the specified redirection type.
2559	if (Redirection == RedirectKind::Fallthrough &&
2560	isFileNotFound(EC: Result.getError()))
2561	return ExternalFS->getRealPath(Path: CanonicalPath, Output);
2562	return Result.getError();
2563	}
2564
2565	// If we found FileEntry or DirectoryRemapEntry, look up the mapped
2566	// path in the external file system.
2567	if (auto ExtRedirect = Result->getExternalRedirect()) {
2568	auto P = ExternalFS->getRealPath(Path: *ExtRedirect, Output);
2569	if (P && Redirection == RedirectKind::Fallthrough &&
2570	isFileNotFound(EC: P, E: Result->E)) {
2571	// Mapped the file but it wasn't found in the underlying filesystem,
2572	// fallthrough to using the original path if that was the specified
2573	// redirection type.
2574	return ExternalFS->getRealPath(Path: CanonicalPath, Output);
2575	}
2576	return P;
2577	}
2578
2579	// We found a DirectoryEntry, which does not have a single external contents
2580	// path. Use the canonical virtual path.
2581	if (Redirection == RedirectKind::Fallthrough) {
2582	Result->getPath(Result&: Output);
2583	return {};
2584	}
2585	return llvm::errc::invalid_argument;
2586	}
2587
2588	std::unique_ptr<FileSystem>
2589	vfs::getVFSFromYAML(std::unique_ptr<MemoryBuffer> Buffer,
2590	SourceMgr::DiagHandlerTy DiagHandler,
2591	StringRef YAMLFilePath, void *DiagContext,
2592	IntrusiveRefCntPtr<FileSystem> ExternalFS) {
2593	return RedirectingFileSystem::create(Buffer: std::move(Buffer), DiagHandler,
2594	YAMLFilePath, DiagContext,
2595	ExternalFS: std::move(ExternalFS));
2596	}
2597
2598	static void getVFSEntries(RedirectingFileSystem::Entry *SrcE,
2599	SmallVectorImpl<StringRef> &Path,
2600	SmallVectorImpl<YAMLVFSEntry> &Entries) {
2601	auto Kind = SrcE->getKind();
2602	if (Kind == RedirectingFileSystem::EK_Directory) {
2603	auto *DE = dyn_cast<RedirectingFileSystem::DirectoryEntry>(Val: SrcE);
2604	assert(DE && "Must be a directory");
2605	for (std::unique_ptr<RedirectingFileSystem::Entry> &SubEntry :
2606	llvm::make_range(x: DE->contents_begin(), y: DE->contents_end())) {
2607	Path.push_back(Elt: SubEntry->getName());
2608	getVFSEntries(SrcE: SubEntry.get(), Path, Entries);
2609	Path.pop_back();
2610	}
2611	return;
2612	}
2613
2614	if (Kind == RedirectingFileSystem::EK_DirectoryRemap) {
2615	auto *DR = dyn_cast<RedirectingFileSystem::DirectoryRemapEntry>(Val: SrcE);
2616	assert(DR && "Must be a directory remap");
2617	SmallString<128> VPath;
2618	for (auto &Comp : Path)
2619	llvm::sys::path::append(path&: VPath, a: Comp);
2620	Entries.push_back(
2621	Elt: YAMLVFSEntry(VPath.c_str(), DR->getExternalContentsPath()));
2622	return;
2623	}
2624
2625	assert(Kind == RedirectingFileSystem::EK_File && "Must be a EK_File");
2626	auto *FE = dyn_cast<RedirectingFileSystem::FileEntry>(Val: SrcE);
2627	assert(FE && "Must be a file");
2628	SmallString<128> VPath;
2629	for (auto &Comp : Path)
2630	llvm::sys::path::append(path&: VPath, a: Comp);
2631	Entries.push_back(Elt: YAMLVFSEntry(VPath.c_str(), FE->getExternalContentsPath()));
2632	}
2633
2634	void vfs::collectVFSFromYAML(std::unique_ptr<MemoryBuffer> Buffer,
2635	SourceMgr::DiagHandlerTy DiagHandler,
2636	StringRef YAMLFilePath,
2637	SmallVectorImpl<YAMLVFSEntry> &CollectedEntries,
2638	void *DiagContext,
2639	IntrusiveRefCntPtr<FileSystem> ExternalFS) {
2640	std::unique_ptr<RedirectingFileSystem> VFS = RedirectingFileSystem::create(
2641	Buffer: std::move(Buffer), DiagHandler, YAMLFilePath, DiagContext,
2642	ExternalFS: std::move(ExternalFS));
2643	if (!VFS)
2644	return;
2645	ErrorOr<RedirectingFileSystem::LookupResult> RootResult =
2646	VFS->lookupPath(Path: "/");
2647	if (!RootResult)
2648	return;
2649	SmallVector<StringRef, 8> Components;
2650	Components.push_back(Elt: "/");
2651	getVFSEntries(SrcE: RootResult->E, Path&: Components, Entries&: CollectedEntries);
2652	}
2653
2654	UniqueID vfs::getNextVirtualUniqueID() {
2655	static std::atomic<unsigned> UID;
2656	unsigned ID = ++UID;
2657	// The following assumes that uint64_t max will never collide with a real
2658	// dev_t value from the OS.
2659	return UniqueID(std::numeric_limits<uint64_t>::max(), ID);
2660	}
2661
2662	void YAMLVFSWriter::addEntry(StringRef VirtualPath, StringRef RealPath,
2663	bool IsDirectory) {
2664	assert(sys::path::is_absolute(VirtualPath) && "virtual path not absolute");
2665	assert(sys::path::is_absolute(RealPath) && "real path not absolute");
2666	assert(!pathHasTraversal(VirtualPath) && "path traversal is not supported");
2667	Mappings.emplace_back(args&: VirtualPath, args&: RealPath, args&: IsDirectory);
2668	}
2669
2670	void YAMLVFSWriter::addFileMapping(StringRef VirtualPath, StringRef RealPath) {
2671	addEntry(VirtualPath, RealPath, /*IsDirectory=*/false);
2672	}
2673
2674	void YAMLVFSWriter::addDirectoryMapping(StringRef VirtualPath,
2675	StringRef RealPath) {
2676	addEntry(VirtualPath, RealPath, /*IsDirectory=*/true);
2677	}
2678
2679	namespace {
2680
2681	class JSONWriter {
2682	llvm::raw_ostream &OS;
2683	SmallVector<StringRef, 16> DirStack;
2684
2685	unsigned getDirIndent() { return 4 * DirStack.size(); }
2686	unsigned getFileIndent() { return 4 * (DirStack.size() + 1); }
2687	bool containedIn(StringRef Parent, StringRef Path);
2688	StringRef containedPart(StringRef Parent, StringRef Path);
2689	void startDirectory(StringRef Path);
2690	void endDirectory();
2691	void writeEntry(StringRef VPath, StringRef RPath);
2692
2693	public:
2694	JSONWriter(llvm::raw_ostream &OS) : OS(OS) {}
2695
2696	void write(ArrayRef<YAMLVFSEntry> Entries,
2697	std::optional<bool> UseExternalNames,
2698	std::optional<bool> IsCaseSensitive,
2699	std::optional<bool> IsOverlayRelative, StringRef OverlayDir);
2700	};
2701
2702	} // namespace
2703
2704	bool JSONWriter::containedIn(StringRef Parent, StringRef Path) {
2705	using namespace llvm::sys;
2706
2707	// Compare each path component.
2708	auto IParent = path::begin(path: Parent), EParent = path::end(path: Parent);
2709	for (auto IChild = path::begin(path: Path), EChild = path::end(path: Path);
2710	IParent != EParent && IChild != EChild; ++IParent, ++IChild) {
2711	if (*IParent != *IChild)
2712	return false;
2713	}
2714	// Have we exhausted the parent path?
2715	return IParent == EParent;
2716	}
2717
2718	StringRef JSONWriter::containedPart(StringRef Parent, StringRef Path) {
2719	assert(!Parent.empty());
2720	assert(containedIn(Parent, Path));
2721	return Path.slice(Start: Parent.size() + 1, End: StringRef::npos);
2722	}
2723
2724	void JSONWriter::startDirectory(StringRef Path) {
2725	StringRef Name =
2726	DirStack.empty() ? Path : containedPart(Parent: DirStack.back(), Path);
2727	DirStack.push_back(Elt: Path);
2728	unsigned Indent = getDirIndent();
2729	OS.indent(NumSpaces: Indent) << "{\n";
2730	OS.indent(NumSpaces: Indent + 2) << "'type': 'directory',\n";
2731	OS.indent(NumSpaces: Indent + 2) << "'name': \"" << llvm::yaml::escape(Input: Name) << "\",\n";
2732	OS.indent(NumSpaces: Indent + 2) << "'contents': [\n";
2733	}
2734
2735	void JSONWriter::endDirectory() {
2736	unsigned Indent = getDirIndent();
2737	OS.indent(NumSpaces: Indent + 2) << "]\n";
2738	OS.indent(NumSpaces: Indent) << "}";
2739
2740	DirStack.pop_back();
2741	}
2742
2743	void JSONWriter::writeEntry(StringRef VPath, StringRef RPath) {
2744	unsigned Indent = getFileIndent();
2745	OS.indent(NumSpaces: Indent) << "{\n";
2746	OS.indent(NumSpaces: Indent + 2) << "'type': 'file',\n";
2747	OS.indent(NumSpaces: Indent + 2) << "'name': \"" << llvm::yaml::escape(Input: VPath) << "\",\n";
2748	OS.indent(NumSpaces: Indent + 2) << "'external-contents': \""
2749	<< llvm::yaml::escape(Input: RPath) << "\"\n";
2750	OS.indent(NumSpaces: Indent) << "}";
2751	}
2752
2753	void JSONWriter::write(ArrayRef<YAMLVFSEntry> Entries,
2754	std::optional<bool> UseExternalNames,
2755	std::optional<bool> IsCaseSensitive,
2756	std::optional<bool> IsOverlayRelative,
2757	StringRef OverlayDir) {
2758	using namespace llvm::sys;
2759
2760	OS << "{\n"
2761	" 'version': 0,\n";
2762	if (IsCaseSensitive)
2763	OS << " 'case-sensitive': '" << (*IsCaseSensitive ? "true" : "false")
2764	<< "',\n";
2765	if (UseExternalNames)
2766	OS << " 'use-external-names': '" << (*UseExternalNames ? "true" : "false")
2767	<< "',\n";
2768	bool UseOverlayRelative = false;
2769	if (IsOverlayRelative) {
2770	UseOverlayRelative = *IsOverlayRelative;
2771	OS << " 'overlay-relative': '" << (UseOverlayRelative ? "true" : "false")
2772	<< "',\n";
2773	}
2774	OS << " 'roots': [\n";
2775
2776	if (!Entries.empty()) {
2777	const YAMLVFSEntry &Entry = Entries.front();
2778
2779	startDirectory(
2780	Path: Entry.IsDirectory ? Entry.VPath : path::parent_path(path: Entry.VPath)
2781	);
2782
2783	StringRef RPath = Entry.RPath;
2784	if (UseOverlayRelative) {
2785	assert(RPath.starts_with(OverlayDir) &&
2786	"Overlay dir must be contained in RPath");
2787	RPath = RPath.slice(Start: OverlayDir.size(), End: RPath.size());
2788	}
2789
2790	bool IsCurrentDirEmpty = true;
2791	if (!Entry.IsDirectory) {
2792	writeEntry(VPath: path::filename(path: Entry.VPath), RPath);
2793	IsCurrentDirEmpty = false;
2794	}
2795
2796	for (const auto &Entry : Entries.slice(N: 1)) {
2797	StringRef Dir =
2798	Entry.IsDirectory ? Entry.VPath : path::parent_path(path: Entry.VPath);
2799	if (Dir == DirStack.back()) {
2800	if (!IsCurrentDirEmpty) {
2801	OS << ",\n";
2802	}
2803	} else {
2804	bool IsDirPoppedFromStack = false;
2805	while (!DirStack.empty() && !containedIn(Parent: DirStack.back(), Path: Dir)) {
2806	OS << "\n";
2807	endDirectory();
2808	IsDirPoppedFromStack = true;
2809	}
2810	if (IsDirPoppedFromStack || !IsCurrentDirEmpty) {
2811	OS << ",\n";
2812	}
2813	startDirectory(Path: Dir);
2814	IsCurrentDirEmpty = true;
2815	}
2816	StringRef RPath = Entry.RPath;
2817	if (UseOverlayRelative) {
2818	assert(RPath.starts_with(OverlayDir) &&
2819	"Overlay dir must be contained in RPath");
2820	RPath = RPath.slice(Start: OverlayDir.size(), End: RPath.size());
2821	}
2822	if (!Entry.IsDirectory) {
2823	writeEntry(VPath: path::filename(path: Entry.VPath), RPath);
2824	IsCurrentDirEmpty = false;
2825	}
2826	}
2827
2828	while (!DirStack.empty()) {
2829	OS << "\n";
2830	endDirectory();
2831	}
2832	OS << "\n";
2833	}
2834
2835	OS << " ]\n"
2836	<< "}\n";
2837	}
2838
2839	void YAMLVFSWriter::write(llvm::raw_ostream &OS) {
2840	llvm::sort(C&: Mappings, Comp: [](const YAMLVFSEntry &LHS, const YAMLVFSEntry &RHS) {
2841	return LHS.VPath < RHS.VPath;
2842	});
2843
2844	JSONWriter(OS).write(Entries: Mappings, UseExternalNames, IsCaseSensitive,
2845	IsOverlayRelative, OverlayDir);
2846	}
2847
2848	vfs::recursive_directory_iterator::recursive_directory_iterator(
2849	FileSystem &FS_, const Twine &Path, std::error_code &EC)
2850	: FS(&FS_) {
2851	directory_iterator I = FS->dir_begin(Dir: Path, EC);
2852	if (I != directory_iterator()) {
2853	State = std::make_shared<detail::RecDirIterState>();
2854	State->Stack.push(x: I);
2855	}
2856	}
2857
2858	vfs::recursive_directory_iterator &
2859	recursive_directory_iterator::increment(std::error_code &EC) {
2860	assert(FS && State && !State->Stack.empty() && "incrementing past end");
2861	assert(!State->Stack.top()->path().empty() && "non-canonical end iterator");
2862	vfs::directory_iterator End;
2863
2864	if (State->HasNoPushRequest)
2865	State->HasNoPushRequest = false;
2866	else {
2867	if (State->Stack.top()->type() == sys::fs::file_type::directory_file) {
2868	vfs::directory_iterator I = FS->dir_begin(Dir: State->Stack.top()->path(), EC);
2869	if (I != End) {
2870	State->Stack.push(x: I);
2871	return *this;
2872	}
2873	}
2874	}
2875
2876	while (!State->Stack.empty() && State->Stack.top().increment(EC) == End)
2877	State->Stack.pop();
2878
2879	if (State->Stack.empty())
2880	State.reset(); // end iterator
2881
2882	return *this;
2883	}
2884
2885	const char FileSystem::ID = 0;
2886	const char OverlayFileSystem::ID = 0;
2887	const char ProxyFileSystem::ID = 0;
2888	const char InMemoryFileSystem::ID = 0;
2889	const char RedirectingFileSystem::ID = 0;
2890