[vcpkg] Make Filesystem::remove_all faster #7570

I added benchmarks to measure how fast the parallel remove_all code was
-- it turns out, about 3x slower than stdfs::remove_all. Since this was
the case, I removed all of the parallelism and rewrote it serially, and
ended up about 30% faster than stdfs::remove_all (in addition to
supporting symlinks).

In addition, I did the following three orthogonal changes:
  - simplified the work queue, basing it on Billy O'Neal's idea
  - Fix warnings on older versions of compilers in tests, by splitting
    the pragmas out of pch.h.
  - Ran clang-format on some files

In fixing up remove_all, the following changes were made:
  - On Windows, regular symlinks and directory symlinks are distinct;
    as an example, to remove directory symlinks (and junctions, for that
    matter), one must use RemoveDirectory. Only on Windows, I added new
    `file_type` and `file_status` types, with `file_type` including a new
    `directory_symlink` enumerator, and `file_status` being exactly the
    same as the old one except using the new `file_type`. On Unix, I
    didn't make that change since they don't make a distinction.
  - I added new `symlink_status` and `status` functions which use the
    new `file_status` on Windows.
  - I made `Filesystem::exists` call `fs::exists(status(p))`, as opposed
    to the old version which called `stdfs::exists` directly.
  - Added benchmarks to `vcpkg-test/files.cpp`. They test the
    performance of `remove_all` on small directories (~20 files), with
    symlinks and without, and on large directories (~2000 files), with
    symlinks and without.

1 files changed, 157 insertions, 37 deletions

diff --git a/toolsrc/src/vcpkg-test/files.cpp b/toolsrc/src/vcpkg-test/files.cpp
index ff0176a93..a2faf455c 100644
--- a/toolsrc/src/vcpkg-test/files.cpp
+++ b/toolsrc/src/vcpkg-test/files.cpp
@@ -9,29 +9,63 @@
 
 #include <vector>
 
-using vcpkg::Test::SYMLINKS_ALLOWED;
-using vcpkg::Test::TEMPORARY_DIRECTORY;
+using vcpkg::Test::AllowSymlinks;
+using vcpkg::Test::base_temporary_directory;
+using vcpkg::Test::can_create_symlinks;
+
+#define CHECK_EC_ON_FILE(file, ec)                                                                                     \
+    do                                                                                                                 \
+    {                                                                                                                  \
+        if (ec)                                                                                                        \
+        {                                                                                                              \
+            FAIL(file << ": " << ec.message());                                                                        \
+        }                                                                                                              \
+    } while (0)
 
 namespace
 {
-    using uid = std::uniform_int_distribution<std::uint64_t>;
+    using uid_t = std::uniform_int_distribution<std::uint64_t>;
+    using urbg_t = std::mt19937_64;
 
-    std::mt19937_64 get_urbg(std::uint64_t index)
+    urbg_t get_urbg(std::uint64_t index)
     {
         // smallest prime > 2**63 - 1
-        return std::mt19937_64{index + 9223372036854775837ULL};
+        return urbg_t{index + 9223372036854775837ULL};
     }
 
-    std::string get_random_filename(std::mt19937_64& urbg) { return vcpkg::Strings::b32_encode(uid{}(urbg)); }
+    std::string get_random_filename(urbg_t& urbg) { return vcpkg::Strings::b32_encode(uid_t{}(urbg)); }
 
-    void create_directory_tree(std::mt19937_64& urbg,
+    struct MaxDepth
+    {
+        std::uint64_t i;
+        explicit MaxDepth(std::uint64_t i) : i(i) {}
+        operator uint64_t() const { return i; }
+    };
+
+    struct Width
+    {
+        std::uint64_t i;
+        explicit Width(std::uint64_t i) : i(i) {}
+        operator uint64_t() const { return i; }
+    };
+
+    struct CurrentDepth
+    {
+        std::uint64_t i;
+        explicit CurrentDepth(std::uint64_t i) : i(i) {}
+        operator uint64_t() const { return i; }
+        CurrentDepth incremented() const { return CurrentDepth{i + 1}; }
+    };
+
+    void create_directory_tree(urbg_t& urbg,
                                vcpkg::Files::Filesystem& fs,
-                               std::uint64_t depth,
-                               const fs::path& base)
+                               const fs::path& base,
+                               MaxDepth max_depth,
+                               AllowSymlinks allow_symlinks = AllowSymlinks::Yes,
+                               Width width = Width{5},
+                               CurrentDepth current_depth = CurrentDepth{0})
     {
         std::random_device rd;
-        constexpr std::uint64_t max_depth = 5;
-        constexpr std::uint64_t width = 5;
 
         // we want ~70% of our "files" to be directories, and then a third
         // each of the remaining ~30% to be regular files, directory symlinks,
@@ -42,18 +76,24 @@ namespace
         constexpr std::uint64_t regular_symlink_tag = 8;
         constexpr std::uint64_t directory_symlink_tag = 9;
 
+        allow_symlinks = AllowSymlinks{allow_symlinks && can_create_symlinks()};
+
         // if we're at the max depth, we only want to build non-directories
         std::uint64_t file_type;
-        if (depth < max_depth)
+        if (current_depth >= max_depth)
+        {
+            file_type = uid_t{regular_file_tag, directory_symlink_tag}(urbg);
+        }
+        else if (current_depth < 2)
         {
-            file_type = uid{directory_min_tag, regular_symlink_tag}(urbg);
+            file_type = directory_min_tag;
         }
         else
         {
-            file_type = uid{regular_file_tag, regular_symlink_tag}(urbg);
+            file_type = uid_t{directory_min_tag, regular_symlink_tag}(urbg);
         }
 
-        if (!SYMLINKS_ALLOWED && file_type > regular_file_tag)
+        if (!allow_symlinks && file_type > regular_file_tag)
         {
             file_type = regular_file_tag;
         }
@@ -62,14 +102,20 @@ namespace
         if (file_type <= directory_max_tag)
         {
             fs.create_directory(base, ec);
-            if (ec) {
-                INFO("File that failed: " << base);
-                REQUIRE_FALSE(ec);
+            if (ec)
+            {
+                CHECK_EC_ON_FILE(base, ec);
             }
 
             for (int i = 0; i < width; ++i)
             {
-                create_directory_tree(urbg, fs, depth + 1, base / get_random_filename(urbg));
+                create_directory_tree(urbg,
+                                      fs,
+                                      base / get_random_filename(urbg),
+                                      max_depth,
+                                      allow_symlinks,
+                                      width,
+                                      current_depth.incremented());
             }
         }
         else if (file_type == regular_file_tag)
@@ -80,19 +126,34 @@ namespace
         else if (file_type == regular_symlink_tag)
         {
             // regular symlink
-            fs.write_contents(base, "", ec);
-            REQUIRE_FALSE(ec);
             auto base_link = base;
-            base_link.replace_filename(base.filename().u8string() + "-link");
-            vcpkg::Test::create_symlink(base, base_link, ec);
+            base_link.replace_filename(base.filename().u8string() + "-orig");
+            fs.write_contents(base_link, "", ec);
+            CHECK_EC_ON_FILE(base_link, ec);
+            vcpkg::Test::create_symlink(base_link, base, ec);
         }
         else // type == directory_symlink_tag
         {
             // directory symlink
-            vcpkg::Test::create_directory_symlink(base / "..", base, ec);
+            auto parent = base;
+            parent.remove_filename();
+            vcpkg::Test::create_directory_symlink(parent, base, ec);
         }
 
-        REQUIRE_FALSE(ec);
+        CHECK_EC_ON_FILE(base, ec);
+        REQUIRE(fs::exists(fs.symlink_status(base, ec)));
+        CHECK_EC_ON_FILE(base, ec);
+    }
+
+    vcpkg::Files::Filesystem& setup(urbg_t& urbg)
+    {
+        auto& fs = vcpkg::Files::get_real_filesystem();
+
+        std::error_code ec;
+        fs.create_directory(base_temporary_directory(), ec);
+        CHECK_EC_ON_FILE(base_temporary_directory(), ec);
+
+        return fs;
     }
 }
 
@@ -100,24 +161,83 @@ TEST_CASE ("remove all", "[files]")
 {
     auto urbg = get_urbg(0);
 
-    fs::path temp_dir = TEMPORARY_DIRECTORY / get_random_filename(urbg);
+    auto& fs = setup(urbg);
 
-    auto& fs = vcpkg::Files::get_real_filesystem();
+    fs::path temp_dir = base_temporary_directory() / get_random_filename(urbg);
+    INFO("temp dir is: " << temp_dir);
+
+    create_directory_tree(urbg, fs, temp_dir, MaxDepth{5});
 
     std::error_code ec;
-    fs.create_directory(TEMPORARY_DIRECTORY, ec);
+    fs::path fp;
+    fs.remove_all(temp_dir, ec, fp);
+    CHECK_EC_ON_FILE(fp, ec);
 
-    REQUIRE_FALSE(ec);
+    REQUIRE_FALSE(fs.exists(temp_dir, ec));
+    CHECK_EC_ON_FILE(temp_dir, ec);
+}
 
-    INFO("temp dir is: " << temp_dir);
+#if defined(CATCH_CONFIG_ENABLE_BENCHMARKING)
+TEST_CASE ("remove all -- benchmarks", "[files][!benchmark]")
+{
+    auto urbg = get_urbg(1);
+    auto& fs = setup(urbg);
 
-    create_directory_tree(urbg, fs, 0, temp_dir);
+    struct
+    {
+        urbg_t& urbg;
+        vcpkg::Files::Filesystem& fs;
 
-    fs::path fp;
-    fs.remove_all(temp_dir, ec, fp);
-    if (ec) {
-        FAIL("remove_all failure on file: " << fp);
-    }
+        void operator()(Catch::Benchmark::Chronometer& meter, MaxDepth max_depth, AllowSymlinks allow_symlinks) const
+        {
+            std::vector<fs::path> temp_dirs;
+            temp_dirs.resize(meter.runs());
+
+            std::generate(begin(temp_dirs), end(temp_dirs), [&] {
+                fs::path temp_dir = base_temporary_directory() / get_random_filename(urbg);
+                create_directory_tree(urbg, fs, temp_dir, max_depth, allow_symlinks);
+                return temp_dir;
+            });
+
+            meter.measure([&](int run) {
+                std::error_code ec;
+                fs::path fp;
+                const auto& temp_dir = temp_dirs[run];
+
+                fs.remove_all(temp_dir, ec, fp);
+                CHECK_EC_ON_FILE(fp, ec);
+            });
+
+            for (const auto& dir : temp_dirs)
+            {
+                std::error_code ec;
+                REQUIRE_FALSE(fs.exists(dir, ec));
+                CHECK_EC_ON_FILE(dir, ec);
+            }
+        }
+    } do_benchmark = {urbg, fs};
+
+    BENCHMARK_ADVANCED("small directory, no symlinks")(Catch::Benchmark::Chronometer meter)
+    {
+        do_benchmark(meter, MaxDepth{2}, AllowSymlinks::No);
+    };
+
+    BENCHMARK_ADVANCED("large directory, no symlinks")(Catch::Benchmark::Chronometer meter)
+    {
+        do_benchmark(meter, MaxDepth{5}, AllowSymlinks::No);
+    };
 
-    REQUIRE_FALSE(fs.exists(temp_dir));
+    if (can_create_symlinks())
+    {
+        BENCHMARK_ADVANCED("small directory, symlinks")(Catch::Benchmark::Chronometer meter)
+        {
+            do_benchmark(meter, MaxDepth{2}, AllowSymlinks::Yes);
+        };
+
+        BENCHMARK_ADVANCED("large directory, symlinks")(Catch::Benchmark::Chronometer meter)
+        {
+            do_benchmark(meter, MaxDepth{5}, AllowSymlinks::Yes);
+        };
+    }
 }
+#endif