initial remove-in-parallel

doesn't actually do parallel remove yet

4 files changed, 194 insertions, 16 deletions

diff --git a/toolsrc/include/vcpkg/base/rng.h b/toolsrc/include/vcpkg/base/rng.h
new file mode 100644
index 000000000..1bcab05b3
--- /dev/null
+++ b/toolsrc/include/vcpkg/base/rng.h
@@ -0,0 +1,96 @@
+#pragma once
+
+#include <cstdint>
+#include <limits>
+#include <random>
+
+namespace vcpkg {
+
+    /*
+        NOTE(ubsan): taken from the xoshiro paper
+        initialized from random_device by default
+        actual code is copied from wikipedia, since I wrote that code
+    */
+    struct splitmix64_engine {
+        splitmix64_engine() noexcept;
+
+        constexpr splitmix64_engine(std::uint64_t seed) noexcept
+            : state(seed) {}
+
+        constexpr std::uint64_t operator()() noexcept {
+            state += 0x9E3779B97F4A7C15;
+
+            std::uint64_t result = state;
+            result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
+            result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
+
+            return result ^ (result >> 31);
+        }
+
+        constexpr std::uint64_t max() const noexcept {
+            return std::numeric_limits<std::uint64_t>::max();
+        }
+
+        constexpr std::uint64_t min() const noexcept {
+            return std::numeric_limits<std::uint64_t>::min();
+        }
+
+    private:
+        std::uint64_t state;
+    };
+
+    // Sebastian Vigna's xorshift-based xoshiro xoshiro256** engine
+    // fast and really good
+    // uses the splitmix64_engine to initialize state
+    struct xoshiro256ss_engine {
+        // splitmix64_engine will be initialized with random_device
+        xoshiro256ss_engine() noexcept {
+            splitmix64_engine sm64{};
+
+            for (std::uint64_t& s : this->state) {
+                s = sm64();
+            }
+        }
+
+        constexpr xoshiro256ss_engine(std::uint64_t seed) noexcept : state() {
+            splitmix64_engine sm64{seed};
+
+            for (std::uint64_t& s : this->state) {
+                s = sm64();
+            }
+        }
+
+        constexpr std::uint64_t operator()() noexcept {
+            std::uint64_t const result = rol(state[1] * 5, 7) * 9;
+
+            std::uint64_t const t = state[1] << 17;
+
+            // state[i] = state[i] ^ state[i + 4 mod 4]
+            state[2] ^= state[0];
+            state[3] ^= state[1];
+            state[1] ^= state[2];
+            state[0] ^= state[3];
+
+            state[2] ^= t;
+            state[3] ^= rol(state[3], 45);
+
+            return result;
+        }
+
+        constexpr std::uint64_t max() const noexcept {
+            return std::numeric_limits<std::uint64_t>::max();
+        }
+
+        constexpr std::uint64_t min() const noexcept {
+            return std::numeric_limits<std::uint64_t>::min();
+        }
+    private:
+        // rotate left
+        constexpr std::uint64_t rol(std::uint64_t x, int k) {
+            return (x << k) | (x >> (64 - k));
+        }
+
+        std::uint64_t state[4];
+    };
+
+}
diff --git a/toolsrc/include/vcpkg/base/strings.h b/toolsrc/include/vcpkg/base/strings.h
index d553d1d41..423ea2096 100644
--- a/toolsrc/include/vcpkg/base/strings.h
+++ b/toolsrc/include/vcpkg/base/strings.h
@@ -184,4 +184,36 @@ namespace vcpkg::Strings
     const char* search(StringView haystack, StringView needle);
 
     bool contains(StringView haystack, StringView needle);
+
+    // base 64 encoding with URL and filesafe alphabet (base64url)
+    // based on IETF RFC 4648
+    // ignores padding, since one implicitly knows the length from the size of x
+    template <class Integral>
+    std::string b64url_encode(Integral x) {
+        static_assert(std::is_integral_v<Integral>);
+        auto value = static_cast<std::make_unsigned_t<Integral>>(x);
+
+        // 64 values, plus the implicit \0
+        constexpr static char map[0x41] =
+            /*     0123456789ABCDEF */
+            /*0*/ "ABCDEFGHIJKLMNOP"
+            /*1*/ "QRSTUVWXYZabcdef"
+            /*2*/ "ghijklmnopqrstuv"
+            /*3*/ "wxyz0123456789-_"
+        ;
+
+        constexpr static std::make_unsigned_t<Integral> mask = 0x3F;
+        constexpr static int shift = 5;
+
+        std::string result;
+        // reserve ceiling(number of bits / 3)
+        result.reserve((sizeof(value) * 8 + 2) / 3);
+
+        while (value != 0) {
+            char mapped_value = map[value & mask];
+            result.push_back(mapped_value);
+        }
+
+        return result;
+    }
 }
diff --git a/toolsrc/src/vcpkg/base/files.cpp b/toolsrc/src/vcpkg/base/files.cpp
index 5099795e9..d0926bb4c 100644
--- a/toolsrc/src/vcpkg/base/files.cpp
+++ b/toolsrc/src/vcpkg/base/files.cpp
@@ -1,6 +1,7 @@
 #include "pch.h"
 
 #include <vcpkg/base/files.h>
+#include <vcpkg/base/rng.h>
 #include <vcpkg/base/system.debug.h>
 #include <vcpkg/base/system.h>
 #include <vcpkg/base/system.print.h>
@@ -256,26 +257,61 @@ namespace vcpkg::Files
         virtual bool remove(const fs::path& path, std::error_code& ec) override { return fs::stdfs::remove(path, ec); }
         virtual std::uintmax_t remove_all(const fs::path& path, std::error_code& ec) override
         {
-            // Working around the currently buggy remove_all()
-            std::uintmax_t out = fs::stdfs::remove_all(path, ec);
+            /*
+                does not use the std::filesystem call since it is buggy, and can
+                have spurious errors before VS 2017 update 6, and on later versions
+                (as well as on macOS and Linux), this is just as fast and will have
+                fewer spurious errors due to locks.
+            */
+            struct recursive {
+                const fs::path& tmp_directory;
+                std::error_code& ec;
+                xoshiro256ss_engine& rng;
+
+                void operator()(const fs::path& current) const {
+                    const auto type = fs::stdfs::symlink_status(current, ec).type();
+                    if (ec) return;
+
+                    const auto tmp_name = Strings::b64url_encode(rng());
+                    const auto tmp_path = tmp_directory / tmp_name;
+
+                    switch (type) {
+                    case fs::file_type::directory: {
+                        fs::stdfs::rename(current, tmp_path, ec);
+                        if (ec) return;
+                        for (const auto& entry : fs::stdfs::directory_iterator(tmp_path)) {
+                            (*this)(entry);
+                        }
+                        fs::stdfs::remove(tmp_path, ec);
+                    } break;
+                    case fs::file_type::symlink:
+                    case fs::file_type::regular: {
+                        fs::stdfs::rename(current, tmp_path, ec);
+                        fs::stdfs::remove(current, ec);
+                    } break;
+                    case fs::file_type::not_found: return;
+                    case fs::file_type::none: {
+                        Checks::exit_with_message(VCPKG_LINE_INFO, "Error occurred when evaluating file type of file: %s", current);
+                    }
+                    default: {
+                        Checks::exit_with_message(VCPKG_LINE_INFO, "Attempted to delete special file: %s", current);
+                    }
+                    }
+                }
+            };
 
-            for (int i = 0; i < 5 && this->exists(path); i++)
-            {
-                using namespace std::chrono_literals;
-                std::this_thread::sleep_for(i * 100ms);
-                out += fs::stdfs::remove_all(path, ec);
-            }
+            auto const real_path = fs::stdfs::absolute(path);
 
-            if (this->exists(path))
-            {
-                System::print2(
-                    System::Color::warning,
-                    "Some files in ",
-                    path.u8string(),
-                    " were unable to be removed. Close any editors operating in this directory and retry.\n");
+            if (! real_path.has_parent_path()) {
+                Checks::exit_with_message(VCPKG_LINE_INFO, "Attempted to remove_all the base directory");
             }
 
-            return out;
+            // thoughts: is this fine? or should we do something different?
+            // maybe a temporary directory?
+            auto const base_path = real_path.parent_path();
+
+            xoshiro256ss_engine rng{};
+            recursive{base_path, ec, rng}(real_path);
         }
         virtual bool exists(const fs::path& path) const override { return fs::stdfs::exists(path); }
         virtual bool is_directory(const fs::path& path) const override { return fs::stdfs::is_directory(path); }
diff --git a/toolsrc/src/vcpkg/base/rng.cpp b/toolsrc/src/vcpkg/base/rng.cpp
new file mode 100644
index 000000000..9fe2ea3b4
--- /dev/null
+++ b/toolsrc/src/vcpkg/base/rng.cpp
@@ -0,0 +1,14 @@
+#include <base/rng.h>
+
+namespace vcpkg {
+    namespace {
+        std::random_device system_entropy{};
+    }
+
+    splitmix64_engine::splitmix64_engine() {
+        std::uint64_t top_half = system_entropy();
+        std::uint64_t bottom_half = system_entropy();
+
+        state = (top_half << 32) | bottom_half;
+    }
+}