From 9fefd0267aa6e0cd72d5ec0733e2c044af0aca32 Mon Sep 17 00:00:00 2001 From: Justin Bogner Date: Wed, 21 May 2014 22:46:51 +0000 Subject: [PATCH] VirtualFileSystem: Fix a few directory traversal bugs in VFSWriter There are a couple of issues with writing VFS maps that are awkward to fix within the current mutually recursive approach. Instead, replace the algorithm with an iterative version that uses an explicit stack of directories. Includes tests for cases the old approach was tripping on. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@209332 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Basic/VirtualFileSystem.h | 24 ++-- lib/Basic/VirtualFileSystem.cpp | 173 +++++++++++++----------- unittests/libclang/LibclangTest.cpp | 68 ++++++++++ 3 files changed, 168 insertions(+), 97 deletions(-) diff --git a/include/clang/Basic/VirtualFileSystem.h b/include/clang/Basic/VirtualFileSystem.h index e4582c8028..978e0408da 100644 --- a/include/clang/Basic/VirtualFileSystem.h +++ b/include/clang/Basic/VirtualFileSystem.h @@ -168,25 +168,17 @@ getVFSFromYAML(llvm::MemoryBuffer *Buffer, void *DiagContext = nullptr, IntrusiveRefCntPtr ExternalFS = getRealFileSystem()); +struct YAMLVFSEntry { + template YAMLVFSEntry(T1 &&VPath, T2 &&RPath) + : VPath(std::forward(VPath)), RPath(std::forward(RPath)) {} + std::string VPath; + std::string RPath; +}; + class YAMLVFSWriter { - struct MapEntry { - template MapEntry(T1 &&VPath, T2 &&RPath) - : VPath(std::forward(VPath)), RPath(std::forward(RPath)) {} - std::string VPath; - std::string RPath; - }; - std::vector Mappings; + std::vector Mappings; Optional IsCaseSensitive; - llvm::ArrayRef printDirNodes(llvm::raw_ostream &OS, - llvm::ArrayRef Entries, - StringRef ParentPath, unsigned Indent); - llvm::ArrayRef printContents(llvm::raw_ostream &OS, - llvm::ArrayRef Entries, - unsigned Indent); - bool containedIn(StringRef Parent, StringRef Path); - StringRef containedPart(StringRef Parent, StringRef Path); - public: YAMLVFSWriter() {} void addFileMapping(StringRef VirtualPath, StringRef RealPath); diff --git a/lib/Basic/VirtualFileSystem.cpp b/lib/Basic/VirtualFileSystem.cpp index 077370dcf4..c89b071a77 100644 --- a/lib/Basic/VirtualFileSystem.cpp +++ b/lib/Basic/VirtualFileSystem.cpp @@ -862,72 +862,25 @@ void YAMLVFSWriter::addFileMapping(StringRef VirtualPath, StringRef RealPath) { Mappings.emplace_back(VirtualPath, RealPath); } -ArrayRef -YAMLVFSWriter::printDirNodes(llvm::raw_ostream &OS, ArrayRef Entries, - StringRef ParentPath, unsigned Indent) { - while (!Entries.empty()) { - const MapEntry &Entry = Entries.front(); - OS.indent(Indent) << "{\n"; - Indent += 2; - OS.indent(Indent) << "'type': 'directory',\n"; - StringRef DirName = - containedPart(ParentPath, sys::path::parent_path(Entry.VPath)); - OS.indent(Indent) - << "'name': \"" << llvm::yaml::escape(DirName) << "\",\n"; - OS.indent(Indent) << "'contents': [\n"; - Entries = printContents(OS, Entries, Indent + 2); - OS.indent(Indent) << "]\n"; - Indent -= 2; - OS.indent(Indent) << '}'; - if (Entries.empty()) { - OS << '\n'; - break; - } - StringRef NextVPath = Entries.front().VPath; - if (!containedIn(ParentPath, NextVPath)) { - OS << '\n'; - break; - } - OS << ",\n"; - } - return Entries; -} +namespace { +class JSONWriter { + llvm::raw_ostream &OS; + SmallVector DirStack; + inline unsigned getDirIndent() { return 4 * DirStack.size(); } + inline unsigned getFileIndent() { return 4 * (DirStack.size() + 1); } + bool containedIn(StringRef Parent, StringRef Path); + StringRef containedPart(StringRef Parent, StringRef Path); + void startDirectory(StringRef Path); + void endDirectory(); + void writeEntry(StringRef VPath, StringRef RPath); -ArrayRef -YAMLVFSWriter::printContents(llvm::raw_ostream &OS, ArrayRef Entries, - unsigned Indent) { - using namespace llvm::sys; - while (!Entries.empty()) { - const MapEntry &Entry = Entries.front(); - Entries = Entries.slice(1); - StringRef ParentPath = path::parent_path(Entry.VPath); - StringRef VName = path::filename(Entry.VPath); - OS.indent(Indent) << "{\n"; - Indent += 2; - OS.indent(Indent) << "'type': 'file',\n"; - OS.indent(Indent) << "'name': \"" << llvm::yaml::escape(VName) << "\",\n"; - OS.indent(Indent) << "'external-contents': \"" - << llvm::yaml::escape(Entry.RPath) << "\"\n"; - Indent -= 2; - OS.indent(Indent) << '}'; - if (Entries.empty()) { - OS << '\n'; - break; - } - StringRef NextVPath = Entries.front().VPath; - if (!containedIn(ParentPath, NextVPath)) { - OS << '\n'; - break; - } - OS << ",\n"; - if (path::parent_path(NextVPath) != ParentPath) { - Entries = printDirNodes(OS, Entries, ParentPath, Indent); - } - } - return Entries; +public: + JSONWriter(llvm::raw_ostream &OS) : OS(OS) {} + void write(ArrayRef Entries, Optional IsCaseSensitive); +}; } -bool YAMLVFSWriter::containedIn(StringRef Parent, StringRef Path) { +bool JSONWriter::containedIn(StringRef Parent, StringRef Path) { using namespace llvm::sys; // Compare each path component. auto IParent = path::begin(Parent), EParent = path::end(Parent); @@ -940,31 +893,89 @@ bool YAMLVFSWriter::containedIn(StringRef Parent, StringRef Path) { return IParent == EParent; } -StringRef YAMLVFSWriter::containedPart(StringRef Parent, StringRef Path) { +StringRef JSONWriter::containedPart(StringRef Parent, StringRef Path) { + assert(!Parent.empty()); assert(containedIn(Parent, Path)); - if (Parent.empty()) - return Path; return Path.slice(Parent.size() + 1, StringRef::npos); } -void YAMLVFSWriter::write(llvm::raw_ostream &OS) { - std::sort(Mappings.begin(), Mappings.end(), - [](const MapEntry &LHS, const MapEntry &RHS) { - return LHS.VPath < RHS.VPath; - }); +void JSONWriter::startDirectory(StringRef Path) { + StringRef Name = + DirStack.empty() ? Path : containedPart(DirStack.back(), Path); + DirStack.push_back(Path); + unsigned Indent = getDirIndent(); + OS.indent(Indent) << "{\n"; + OS.indent(Indent + 2) << "'type': 'directory',\n"; + OS.indent(Indent + 2) << "'name': \"" << llvm::yaml::escape(Name) << "\",\n"; + OS.indent(Indent + 2) << "'contents': [\n"; +} + +void JSONWriter::endDirectory() { + unsigned Indent = getDirIndent(); + OS.indent(Indent + 2) << "]\n"; + OS.indent(Indent) << "}"; + + DirStack.pop_back(); +} + +void JSONWriter::writeEntry(StringRef VPath, StringRef RPath) { + unsigned Indent = getFileIndent(); + OS.indent(Indent) << "{\n"; + OS.indent(Indent + 2) << "'type': 'file',\n"; + OS.indent(Indent + 2) << "'name': \"" << llvm::yaml::escape(VPath) << "\",\n"; + OS.indent(Indent + 2) << "'external-contents': \"" + << llvm::yaml::escape(RPath) << "\"\n"; + OS.indent(Indent) << "}"; +} + +void JSONWriter::write(ArrayRef Entries, + Optional IsCaseSensitive) { + using namespace llvm::sys; OS << "{\n" " 'version': 0,\n"; - if (IsCaseSensitive.hasValue()) { - OS << " 'case-sensitive': '"; - if (IsCaseSensitive.getValue()) - OS << "true"; - else - OS << "false"; - OS << "',\n"; - } + if (IsCaseSensitive.hasValue()) + OS << " 'case-sensitive': '" + << (IsCaseSensitive.getValue() ? "true" : "false") << "',\n"; OS << " 'roots': [\n"; - printDirNodes(OS, Mappings, "", 4); - OS << " ]\n" + + if (Entries.empty()) + return; + + const YAMLVFSEntry &Entry = Entries.front(); + startDirectory(path::parent_path(Entry.VPath)); + writeEntry(path::filename(Entry.VPath), Entry.RPath); + + for (const auto &Entry : Entries.slice(1)) { + StringRef Dir = path::parent_path(Entry.VPath); + if (Dir == DirStack.back()) + OS << ",\n"; + else { + while (!DirStack.empty() && !containedIn(DirStack.back(), Dir)) { + OS << "\n"; + endDirectory(); + } + OS << ",\n"; + startDirectory(Dir); + } + writeEntry(path::filename(Entry.VPath), Entry.RPath); + } + + while (!DirStack.empty()) { + OS << "\n"; + endDirectory(); + } + + OS << "\n" + << " ]\n" << "}\n"; } + +void YAMLVFSWriter::write(llvm::raw_ostream &OS) { + std::sort(Mappings.begin(), Mappings.end(), + [](const YAMLVFSEntry &LHS, const YAMLVFSEntry &RHS) { + return LHS.VPath < RHS.VPath; + }); + + JSONWriter(OS).write(Mappings, IsCaseSensitive); +} diff --git a/unittests/libclang/LibclangTest.cpp b/unittests/libclang/LibclangTest.cpp index a4c560bde4..213222c6cf 100644 --- a/unittests/libclang/LibclangTest.cpp +++ b/unittests/libclang/LibclangTest.cpp @@ -240,6 +240,74 @@ TEST(libclang, VirtualFileOverlay_SharedPrefix) { T.map("/path/foobarbaz.h", "/real/foobarbaz.h"); } +TEST(libclang, VirtualFileOverlay_AdjacentDirectory) { + const char *contents = + "{\n" + " 'version': 0,\n" + " 'roots': [\n" + " {\n" + " 'type': 'directory',\n" + " 'name': \"/path/dir1\",\n" + " 'contents': [\n" + " {\n" + " 'type': 'file',\n" + " 'name': \"foo.h\",\n" + " 'external-contents': \"/real/foo.h\"\n" + " },\n" + " {\n" + " 'type': 'directory',\n" + " 'name': \"subdir\",\n" + " 'contents': [\n" + " {\n" + " 'type': 'file',\n" + " 'name': \"bar.h\",\n" + " 'external-contents': \"/real/bar.h\"\n" + " }\n" + " ]\n" + " }\n" + " ]\n" + " },\n" + " {\n" + " 'type': 'directory',\n" + " 'name': \"/path/dir2\",\n" + " 'contents': [\n" + " {\n" + " 'type': 'file',\n" + " 'name': \"baz.h\",\n" + " 'external-contents': \"/real/baz.h\"\n" + " }\n" + " ]\n" + " }\n" + " ]\n" + "}\n"; + TestVFO T(contents); + T.map("/path/dir1/foo.h", "/real/foo.h"); + T.map("/path/dir1/subdir/bar.h", "/real/bar.h"); + T.map("/path/dir2/baz.h", "/real/baz.h"); +} + +TEST(libclang, VirtualFileOverlay_TopLevel) { + const char *contents = + "{\n" + " 'version': 0,\n" + " 'roots': [\n" + " {\n" + " 'type': 'directory',\n" + " 'name': \"/\",\n" + " 'contents': [\n" + " {\n" + " 'type': 'file',\n" + " 'name': \"foo.h\",\n" + " 'external-contents': \"/real/foo.h\"\n" + " }\n" + " ]\n" + " }\n" + " ]\n" + "}\n"; + TestVFO T(contents); + T.map("/foo.h", "/real/foo.h"); +} + TEST(libclang, ModuleMapDescriptor) { const char *Contents = "framework module TestFrame {\n" -- 2.40.0