Add static `Dataloader::search_for_game_path(fs::path)`

	Searches for Victoria 2 according to the supplied path
	If supplied path is empty, presumes Steam install according to platform environment variables
	If invalid supplied path, falls back to empty path behavior
	Supports Steam install on Windows, Mac, Linux, and FreeBSD
	Supports Windows registry

Update .clang-format categories to include lexy-vdf
Add Utility/ConstexprIntToStr.hpp

3 files changed, 499 insertions, 0 deletions

diff --git a/src/openvic-simulation/dataloader/Dataloader.cpp b/src/openvic-simulation/dataloader/Dataloader.cpp
index 6469b63..70164c3 100644
--- a/src/openvic-simulation/dataloader/Dataloader.cpp
+++ b/src/openvic-simulation/dataloader/Dataloader.cpp
@@ -1,16 +1,319 @@
 #include "Dataloader.hpp"
 
+#include <array>
+#include <cstdlib>
+#include <filesystem>
+#include <optional>
+#include <string_view>
+#include <system_error>
+#include <type_traits>
+#include <variant>
+
 #include <openvic-dataloader/csv/Parser.hpp>
 #include <openvic-dataloader/detail/CallbackOStream.hpp>
 #include <openvic-dataloader/v2script/Parser.hpp>
 
+#include <lexy-vdf/KeyValues.hpp>
+#include <lexy-vdf/Parser.hpp>
+
 #include "openvic-simulation/GameManager.hpp"
+#include "openvic-simulation/utility/ConstexprIntToStr.hpp"
 #include "openvic-simulation/utility/Logger.hpp"
 
+#ifdef _WIN32
+#include <Windows.h>
+#include "Dataloader_Windows.hpp"
+#endif
+
+#if defined(__APPLE__) && defined(__MACH__)
+#include <TargetConditionals.h>
+#endif
+
 using namespace OpenVic;
 using namespace OpenVic::NodeTools;
 using namespace ovdl;
 
+// Windows and Mac by default act like case insensitive filesystems
+constexpr bool path_equals(std::string_view lhs, std::string_view rhs) {
+#if defined(_WIN32) || (defined(__APPLE__) && defined(__MACH__))
+	constexpr auto ichar_equals = [](unsigned char l, unsigned char r) {
+		return std::tolower(l) == std::tolower(r);
+	};
+	return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), ichar_equals);
+#else
+	return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+#endif
+}
+
+template<typename LT, typename RT>
+constexpr bool filename_equals(const LT& lhs, const RT& rhs) {
+	std::string_view left, right;
+	if constexpr (std::same_as<LT, std::filesystem::path>)
+		left = lhs.filename().string();
+	else left = lhs;
+
+	if constexpr (std::same_as<RT, std::filesystem::path>)
+		right = rhs.filename().string();
+	else right = rhs;
+
+	return path_equals(left, right);
+}
+
+fs::path _search_for_game_path(fs::path hint_path = {}) {
+	// Apparently max amount of steam libraries is 8, if incorrect please correct it to the correct max amount
+	constexpr int max_amount_of_steam_libraries = 8;
+	constexpr std::string_view Victoria_2_folder = "Victoria 2";
+	constexpr std::string_view v2_game_exe = "v2game.exe";
+	constexpr std::string_view steamapps = "steamapps";
+	constexpr std::string_view libraryfolders = "libraryfolders.vdf";
+	constexpr std::string_view vic2_appmanifest = "appmanifest_42960.acf";
+	constexpr std::string_view common_folder = "common";
+
+	std::error_code error_code;
+
+	// Don't waste time trying to search for Victoria 2 when supplied a valid looking Victoria 2 game directory
+	if (filename_equals(Victoria_2_folder, hint_path)) {
+		if (fs::is_regular_file(hint_path / v2_game_exe, error_code))
+			return hint_path;
+	}
+
+	const bool hint_path_was_empty = hint_path.empty();
+	if (hint_path_was_empty) {
+#if defined(_WIN32)
+		static const fs::path registry_path = Windows::ReadRegValue<char>(HKEY_LOCAL_MACHINE, "SOFTWARE\\WOW6432Node\\Paradox Interactive\\Victoria 2", "path");
+
+		if (!registry_path.empty())
+			return registry_path;
+
+		#pragma warning(push)
+		#pragma warning(disable: 4996)
+		static const fs::path prog_files = std::string(std::getenv("ProgramFiles"));
+		hint_path = prog_files / "Steam";
+		if (!fs::is_directory(hint_path, error_code)) {
+			static const fs::path prog_files_x86 = std::string(std::getenv("ProgramFiles(x86)"));
+			hint_path = prog_files_x86 / "Steam";
+			if (!fs::is_directory(hint_path, error_code)) {
+				Logger::warning("Could not find path for Steam installation on Windows.");
+				return "";
+			}
+		}
+		#pragma warning(pop)
+// Cannot support Android
+// Only FreeBSD currently unofficially supports emulating Linux
+#elif (defined(__linux__) && !defined(__ANDROID__)) || defined(__FreeBSD__)
+		static const fs::path home = std::getenv("HOME");
+		hint_path = home / ".steam" / "steam";
+		if (fs::is_symlink(hint_path, error_code))
+			hint_path = fs::read_symlink(hint_path, error_code);
+		else if (!fs::is_directory(hint_path, error_code)) {
+			hint_path = home / ".local" / "share" / "Steam";
+			if (!fs::is_directory(hint_path, error_code)) {
+#ifdef __FreeBSD__
+				Logger::warning("Could not find path for Steam installation on FreeBSD.");
+#else
+				Logger::warning("Could not find path for Steam installation on Linux.");
+#endif
+				return "";
+			}
+		}
+// Support only Mac, cannot support iOS
+#elif (defined(__APPLE__) && defined(__MACH__)) && TARGET_OS_MAC == 1
+		static const fs::path home = std::getenv("HOME");
+		hint_path = home / "Library" / "Application Support" / "Steam";
+		if (!fs::is_directory(hint_path, error_code)) {
+			Logger::warning("Could not find path for Steam installation on Mac.");
+			return "";
+		}
+// All platforms that reach this point do not seem to even have unofficial Steam support
+#else
+		Logger::warning("Could not find path for Steam installation on unsupported platform.");
+#endif
+	}
+
+	// Could not determine Steam install on platform
+	if (hint_path.empty()) return "";
+
+	// Supplied path was useless, ignore hint_path
+	if (!hint_path_was_empty && !fs::exists(hint_path, error_code))
+		return _search_for_game_path();
+
+	// Steam Library's directory that will contain Victoria 2
+	fs::path vic2_steam_lib_directory;
+	fs::path current_path = hint_path;
+
+	// If hinted path is directory that contains steamapps
+	bool is_steamapps = false;
+	if (fs::is_directory(current_path / steamapps, error_code)) {
+		current_path /= steamapps;
+		is_steamapps = true;
+	}
+
+	// If hinted path is steamapps directory
+	bool is_libraryfolders_vdf = false;
+	if (is_steamapps || (filename_equals(steamapps, current_path) && fs::is_directory(current_path, error_code))) {
+		current_path /= libraryfolders;
+		is_libraryfolders_vdf = true;
+	}
+
+	bool vic2_install_confirmed = false;
+	// if current_path is not a regular file, this is a non-default Steam Library, skip this parser evaluation
+	if (fs::is_regular_file(current_path, error_code) && (is_libraryfolders_vdf || filename_equals(libraryfolders, current_path))) {
+		lexy_vdf::Parser parser;
+
+		std::string buffer;
+		auto error_log_stream = detail::CallbackStream {
+			[](void const* s, std::streamsize n, void* user_data) -> std::streamsize {
+				if (s != nullptr && n > 0 && user_data != nullptr) {
+					static_cast<std::string*>(user_data)->append(static_cast<char const*>(s), n);
+					return n;
+				} else {
+					Logger::warning("Invalid input to parser error log callback: ", s, " / ", n, " / ", user_data);
+					return 0;
+				}
+			},
+			&buffer
+		};
+		parser.set_error_log_to(error_log_stream);
+
+		parser.load_from_file(current_path);
+		if (!parser.parse()) {
+			// Could not find or load libraryfolders.vdf, report error as warning
+			if (!buffer.empty())
+				Logger::warning _(buffer);
+			return "";
+		}
+		std::optional current_node = *(parser.get_key_values());
+
+		// check "libraryfolders" list
+		auto it = current_node.value().find("libraryfolders");
+		if (it == current_node.value().end()) {
+			Logger::warning("Expected libraryfolders.vdf to contain a libraryfolders key.");
+			return "";
+		}
+
+		static constexpr auto visit_node = [](auto&& arg) -> std::optional<lexy_vdf::KeyValues> {
+			using T = std::decay_t<decltype(arg)>;
+			if constexpr (std::is_same_v<T, lexy_vdf::KeyValues>) {
+				return arg;
+			} else {
+				return std::nullopt;
+			}
+		};
+
+		current_node = std::visit(visit_node, it->second);
+
+		if (!current_node.has_value()) {
+			Logger::warning("Expected libraryfolders.vdf's libraryfolders key to be a KeyValue dictionary.");
+			return "";
+		}
+
+		// Array of strings contain "0" to std::to_string(max_amount_of_steam_libraries - 1)
+		static constexpr auto library_indexes = OpenVic::ConstexprIntToStr::make_itosv_array<max_amount_of_steam_libraries>();
+
+		for (const auto& index : library_indexes) {
+			decltype(current_node) node = std::nullopt;
+
+			auto it = current_node.value().find(index);
+			if (it != current_node.value().end()) {
+				node = std::visit(visit_node, it->second);
+			}
+
+			// check "apps" list
+			decltype(node) apps_node = std::nullopt;
+			if (node.has_value()) {
+				it = node.value().find("apps");
+				if (it != node.value().end()) {
+					apps_node = std::visit(visit_node, it->second);
+				}
+			}
+
+			bool lib_contains_victoria_2 = false;
+			if (apps_node.has_value()) {
+				lib_contains_victoria_2 = apps_node.value().find("42960") != node.value().end();
+			}
+
+			if (lib_contains_victoria_2) {
+				it = node.value().find("path");
+				if (it != node.value().end()) {
+					vic2_steam_lib_directory = std::visit(
+						[](auto&& arg) -> std::string_view {
+							using T = std::decay_t<decltype(arg)>;
+							if constexpr (std::is_same_v<T, std::string>) {
+								return arg;
+							} else {
+								return "";
+							}
+						},
+						it->second
+					);
+					vic2_install_confirmed = true;
+					break;
+				}
+			}
+		}
+
+		if (vic2_steam_lib_directory.empty()) {
+			Logger::info("Steam installation appears not to contain Victoria 2.");
+			return "";
+		}
+	}
+
+	// If current_path points to steamapps/libraryfolders.vdf
+	if (vic2_steam_lib_directory.empty()) {
+		if (is_libraryfolders_vdf || filename_equals(libraryfolders, current_path)) {
+			vic2_steam_lib_directory = current_path.parent_path() / vic2_appmanifest;
+		} else if (filename_equals(vic2_appmanifest, current_path)) {
+			vic2_steam_lib_directory = current_path;
+		}
+	}
+
+	// If we could not confirm Victoria 2 was installed via the default Steam installation
+	bool is_common_folder = false;
+	if (!vic2_install_confirmed) {
+		auto parser = lexy_vdf::Parser::from_file(vic2_steam_lib_directory);
+		if (!parser.parse()) {
+			// Could not find or load appmanifest_42960.acf, report error as warning
+			for(auto& error : parser.get_errors()) {
+				Logger::warning(error.message);
+			}
+			return "";
+		}
+
+		// we can pretty much assume the Victoria 2 directory on Steam is valid from here
+		vic2_steam_lib_directory /= common_folder;
+		is_common_folder = true;
+	} else if (fs::is_directory(vic2_steam_lib_directory / steamapps, error_code)) {
+		vic2_steam_lib_directory /= fs::path(steamapps) / common_folder;
+		is_common_folder = true;
+	}
+
+	bool is_Victoria_2_folder = false;
+	if ((is_common_folder || filename_equals(common_folder, vic2_steam_lib_directory)) &&
+		fs::is_directory(vic2_steam_lib_directory, error_code)) {
+		vic2_steam_lib_directory /= Victoria_2_folder;
+		is_Victoria_2_folder = true;
+	}
+	if ((is_Victoria_2_folder || filename_equals(Victoria_2_folder, vic2_steam_lib_directory)) &&
+		fs::is_regular_file(vic2_steam_lib_directory / v2_game_exe, error_code)) {
+		return vic2_steam_lib_directory;
+	}
+
+	// Hail Mary check ignoring the hint_path
+	if (!hint_path_was_empty)
+		return _search_for_game_path();
+
+	Logger::warning("Could not find Victoria 2 game path, this requires manually supplying one.");
+	return ""; // The supplied path fits literally none of the criteria
+}
+
+fs::path Dataloader::search_for_game_path(fs::path hint_path) {
+	auto it = _cached_paths.find(hint_path);
+	if (it != _cached_paths.end())
+		return it->second;
+
+	return _cached_paths[hint_path] = _search_for_game_path(hint_path);
+}
+
 bool Dataloader::set_roots(path_vector_t new_roots) {
 	if (!roots.empty()) {
 		Logger::error("Overriding existing dataloader roots!");
diff --git a/src/openvic-simulation/dataloader/Dataloader.hpp b/src/openvic-simulation/dataloader/Dataloader.hpp
index 9d28132..705da00 100644
--- a/src/openvic-simulation/dataloader/Dataloader.hpp
+++ b/src/openvic-simulation/dataloader/Dataloader.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <filesystem>
+#include <unordered_map>
 
 #include <openvic-dataloader/csv/Parser.hpp>
 #include <openvic-dataloader/v2script/Parser.hpp>
@@ -31,6 +32,25 @@ namespace OpenVic {
 
 		Dataloader() = default;
 
+		/// @brief Searches for the Victoria 2 install directory
+		///
+		/// @param hint_path A path to indicate a hint to assist in searching for the Victoria 2 install directory
+		///	Supports being supplied:
+		///		1. A valid Victoria 2 game directory (Victoria 2 directory that contains a v2game.exe file)
+		///		2. An Empty path: assumes a common Steam install structure per platform.
+		///			2b. If Windows, returns "HKEY_LOCAL_MACHINE\SOFTWARE\WOW6432Node\Paradox Interactive\Victoria 2" "path" registry value
+		///			2c. If registry value returns an empty string, performs Steam checks below
+		///		3. A path to a root Steam install. (eg: C:\Program Files(x86)\Steam, ~/.steam/steam)
+		///		4. A path to a root Steam steamapps directory. (eg: C:\Program Files(x86)\Steam\steamapps, ~/.steam/steam/steamapps)
+		///		5. A path to the root Steam libraryfolders.vdf, commonly in the root Steam steamapps directory.
+		///		6. A path to the Steam library directory that contains Victoria 2.
+		///		7. A path to a Steam library's steamapps directory that contains Victoria 2.
+		///		8. A path to a Steam library's steamapps/common directory that contains Victoria 2.
+		///		9. If any of these checks don't resolve to a valid Victoria 2 game directory when supplied a non-empty hint_path, performs empty path behavior.
+		/// @return fs::path The root directory of a valid Victoria 2 install, or an empty path.
+		///
+		static fs::path search_for_game_path(fs::path hint_path = {});
+
 		/* In reverse-load order, so base defines first and final loaded mod last */
 		bool set_roots(path_vector_t new_roots);
 
@@ -55,5 +75,19 @@ namespace OpenVic {
 		/* Args: key, locale, localisation */
 		using localisation_callback_t = NodeTools::callback_t<std::string_view, locale_t, std::string_view>;
 		bool load_localisation_files(localisation_callback_t callback, fs::path const& localisation_dir = "localisation");
+
+	private:
+		struct fshash
+		{
+			size_t operator()(const std::filesystem::path& p) const noexcept {
+				return std::filesystem::hash_value(p);
+			}
+		};
+
+		using hint_path_t = fs::path;
+		using game_path_t = fs::path;
+		inline static std::unordered_map<hint_path_t, game_path_t, fshash> _cached_paths;
 	};
 }
+
+
diff --git a/src/openvic-simulation/dataloader/Dataloader_Windows.hpp b/src/openvic-simulation/dataloader/Dataloader_Windows.hpp
new file mode 100644
index 0000000..f4abbb6
--- /dev/null
+++ b/src/openvic-simulation/dataloader/Dataloader_Windows.hpp
@@ -0,0 +1,162 @@
+#pragma once
+
+#include <concepts>
+#pragma comment(lib, "advapi32.lib")
+
+#include <string>
+#include <string_view>
+
+#include <Windows.h>
+
+namespace OpenVic::Windows {
+	inline std::wstring convert(std::string_view as) {
+		// deal with trivial case of empty string
+		if (as.empty()) return std::wstring();
+
+		// determine required length of new string
+		size_t length = ::MultiByteToWideChar(CP_UTF8, 0, as.data(), (int)as.length(), 0, 0);
+
+		// construct new string of required length
+		std::wstring ret(length, L'\0');
+
+		// convert old string to new string
+		::MultiByteToWideChar(CP_UTF8, 0, as.data(), (int)as.length(), &ret[0], (int)ret.length());
+
+		// return new string ( compiler should optimize this away )
+		return ret;
+	}
+
+	inline std::string convert(std::wstring_view as) {
+		// deal with trivial case of empty string
+		if (as.empty()) return std::string();
+
+		// determine required length of new string
+		size_t length = ::WideCharToMultiByte(CP_UTF8, 0, as.data(), (int)as.length(), 0, 0, NULL, NULL);
+
+		// construct new string of required length
+		std::string ret(length, '\0');
+
+		// convert old string to new string
+		::WideCharToMultiByte(CP_UTF8, 0, as.data(), (int)as.length(), &ret[0], (int)ret.length(), NULL, NULL);
+
+		// return new string ( compiler should optimize this away )
+		return ret;
+	}
+
+	template<typename T, typename... U>
+	concept any_of = (std::same_as<T, U> || ...);
+
+	template<typename T>
+	concept either_char_type = any_of<T, char, wchar_t>;
+
+	template<typename T>
+	concept has_data = requires(T t) {
+		{ t.data() } -> std::convertible_to<const typename T::value_type*>;
+	};
+
+	class RegistryKey {
+	public:
+		RegistryKey(HKEY key_handle)
+			: _key_handle(key_handle) {
+		}
+
+		template<either_char_type CHAR_T, either_char_type CHAR_T2>
+		RegistryKey(HKEY parent_key_handle, std::basic_string_view<CHAR_T> child_key_name, std::basic_string_view<CHAR_T2> value_name) {
+			open_key(parent_key_handle, child_key_name);
+			query_key(value_name);
+		}
+
+		~RegistryKey() {
+			close_key();
+		}
+
+		bool is_open() const {
+			return _key_handle != nullptr;
+		}
+
+		std::wstring_view value() const {
+			return _value;
+		}
+
+		template<either_char_type CHAR_T>
+		LSTATUS open_key(HKEY parent_key_handle, std::basic_string_view<CHAR_T> key_path) {
+			if (is_open())
+				close_key();
+			if constexpr (std::is_same_v<CHAR_T, char>)
+				return RegOpenKeyExW(parent_key_handle, convert(key_path).data(), REG_NONE, KEY_READ, &_key_handle);
+			else
+				return RegOpenKeyExW(parent_key_handle, key_path.data(), REG_NONE, KEY_READ, &_key_handle);
+		}
+
+		bool is_predefined() const {
+			return (_key_handle == HKEY_CURRENT_USER) ||
+				   (_key_handle == HKEY_LOCAL_MACHINE) ||
+				   (_key_handle == HKEY_CLASSES_ROOT) ||
+				   (_key_handle == HKEY_CURRENT_CONFIG) ||
+				   (_key_handle == HKEY_CURRENT_USER_LOCAL_SETTINGS) ||
+				   (_key_handle == HKEY_PERFORMANCE_DATA) ||
+				   (_key_handle == HKEY_PERFORMANCE_NLSTEXT) ||
+				   (_key_handle == HKEY_PERFORMANCE_TEXT) ||
+				   (_key_handle == HKEY_USERS);
+		}
+
+		LSTATUS close_key() {
+			if (!is_open() || is_predefined())
+				return ERROR_SUCCESS;
+			auto result = RegCloseKey(_key_handle);
+			_key_handle = nullptr;
+			return result;
+		}
+
+		template<either_char_type CHAR_T>
+		LSTATUS query_key(std::basic_string_view<CHAR_T> value_name) {
+			DWORD data_size;
+			DWORD type;
+
+			const auto& wide_value = [&value_name]() -> has_data auto {
+				if constexpr (std::is_same_v<CHAR_T, char>) {
+					return convert(value_name);
+				} else {
+					return value_name;
+				}
+			}();
+
+			auto result = RegQueryValueExW(_key_handle, wide_value.data(), NULL, &type, NULL, &data_size);
+			if (result != ERROR_SUCCESS || type != REG_SZ) {
+				close_key();
+				return result;
+			}
+			_value = std::wstring(data_size / sizeof(wchar_t), L'\0');
+			result = RegQueryValueExW(_key_handle, wide_value.data(), NULL, NULL, reinterpret_cast<LPBYTE>(_value.data()), &data_size);
+			close_key();
+
+			std::size_t first_null = _value.find_first_of(L'\0');
+			if (first_null != std::string::npos)
+				_value.resize(first_null);
+
+			return result;
+		}
+
+	private:
+		HKEY _key_handle = nullptr;
+		std::wstring _value;
+	};
+
+	template<either_char_type RCHAR_T, either_char_type CHAR_T, either_char_type CHAR_T2>
+	std::basic_string<RCHAR_T> ReadRegValue(HKEY root, std::basic_string_view<CHAR_T> key, std::basic_string_view<CHAR_T2> name) {
+		RegistryKey registry_key(root, key, name);
+		if constexpr (std::is_same_v<RCHAR_T, char>) {
+			return convert(registry_key.value());
+		} else {
+			return registry_key.value();
+		}
+	}
+
+	template<either_char_type RCHAR_T, either_char_type CHAR_T, either_char_type CHAR_T2>
+	std::basic_string<RCHAR_T> ReadRegValue(HKEY root, const CHAR_T* key, const CHAR_T2* name) {
+		auto key_sv = std::basic_string_view(key);
+		auto name_sv = std::basic_string_view(name);
+
+		return ReadRegValue<RCHAR_T>(root, key_sv, name_sv);
+	}
+}
\ No newline at end of file