diff options
Diffstat (limited to 'test/buildtool/tree_structure/tree_structure.test.cpp')
| -rw-r--r-- | test/buildtool/tree_structure/tree_structure.test.cpp | 242 |
1 files changed, 241 insertions, 1 deletions
diff --git a/test/buildtool/tree_structure/tree_structure.test.cpp b/test/buildtool/tree_structure/tree_structure.test.cpp index e0656c69..8943d4a9 100644 --- a/test/buildtool/tree_structure/tree_structure.test.cpp +++ b/test/buildtool/tree_structure/tree_structure.test.cpp @@ -12,22 +12,37 @@ // See the License for the specific language governing permissions and // limitations under the License. +#include <algorithm> +#include <array> +#include <cstddef> #include <cstdint> #include <filesystem> +#include <functional> #include <memory> #include <optional> #include <string> +#include <unordered_map> +#include <vector> #include "catch2/catch_test_macros.hpp" #include "gsl/gsl" #include "src/buildtool/common/artifact_digest.hpp" +#include "src/buildtool/common/artifact_digest_factory.hpp" #include "src/buildtool/common/protocol_traits.hpp" #include "src/buildtool/crypto/hash_function.hpp" #include "src/buildtool/execution_api/bazel_msg/bazel_msg_factory.hpp" +#include "src/buildtool/file_system/file_system_manager.hpp" +#include "src/buildtool/file_system/git_repo.hpp" +#include "src/buildtool/file_system/object_type.hpp" #include "src/buildtool/storage/config.hpp" #include "src/buildtool/storage/garbage_collector.hpp" #include "src/buildtool/storage/storage.hpp" +#include "src/buildtool/tree_structure/compute_tree_structure.hpp" #include "src/buildtool/tree_structure/tree_structure_cache.hpp" +#include "src/utils/cpp/expected.hpp" +#include "src/utils/cpp/hash_combine.hpp" +#include "src/utils/cpp/hex_string.hpp" +#include "src/utils/cpp/path.hpp" #include "src/utils/cpp/tmp_dir.hpp" #include "test/utils/hermeticity/test_storage_config.hpp" #include "test/utils/large_objects/large_object_utils.hpp" @@ -37,7 +52,33 @@ namespace { Storage const& storage, std::uintmax_t entries) -> std::optional<ArtifactDigest>; -} + +[[nodiscard]] auto CreateComplexTestDirectory( + StorageConfig const& storage_config, + Storage const& storage) -> std::optional<ArtifactDigest>; + +[[nodiscard]] auto ValidateTreeStructure(ArtifactDigest const& digest, + Storage const& storage) -> bool; + +struct TreeEntryHasher { + [[nodiscard]] auto operator()( + GitRepo::TreeEntry const& entry) const noexcept -> std::size_t { + size_t seed{}; + hash_combine<std::string>(&seed, entry.name); + hash_combine<ObjectType>(&seed, entry.type); + return seed; + } +}; + +using TreeEntriesHitContainer = + std::unordered_map<GitRepo::TreeEntry, int, TreeEntryHasher>; + +[[nodiscard]] auto CountTreeEntries( + ArtifactDigest const& digest, + Storage const& storage, + gsl::not_null<TreeEntriesHitContainer*> const& container, + bool increment) -> bool; +} // namespace TEST_CASE("cache", "[tree_structure]") { auto const storage_config = TestStorageConfig::Create(); @@ -80,6 +121,41 @@ TEST_CASE("cache", "[tree_structure]") { CHECK(youngest.CAS().TreePath(*to_dir).has_value()); } +TEST_CASE("compute", "[tree_structure]") { + auto const storage_config = TestStorageConfig::Create(); + if (not ProtocolTraits::IsNative( + storage_config.Get().hash_function.GetType())) { + return; + } + + auto const storage = Storage::Create(&storage_config.Get()); + TreeStructureCache const ts_cache(&storage_config.Get()); + + auto const tree = CreateComplexTestDirectory(storage_config.Get(), storage); + REQUIRE(tree); + + auto const tree_structure = ComputeTreeStructure(*tree, storage, ts_cache); + REQUIRE(tree_structure); + + REQUIRE(ValidateTreeStructure(*tree_structure, storage)); + + TreeEntriesHitContainer container; + // Add recursively all TreeEntries of the source tree to the container, + // incrementing counters: + REQUIRE(CountTreeEntries(*tree, storage, &container, /*increment=*/true)); + // Add recursively all TreeEntries of the tree structure to the container, + // decrementing counters: + REQUIRE(CountTreeEntries( + *tree_structure, storage, &container, /*increment=*/false)); + + // All counters must be equal to 0, meaning all entries have been hit. + auto const all_hit_equally = + std::all_of(container.begin(), container.end(), [](auto const& p) { + return p.second == 0; + }); + REQUIRE(all_hit_equally); +} + namespace { [[nodiscard]] auto CreateDirectory(std::filesystem::path const& directory, Storage const& storage) { @@ -116,4 +192,168 @@ namespace { } return CreateDirectory(tree->GetPath(), storage); } + +[[nodiscard]] auto CreateComplexTestDirectory( + StorageConfig const& storage_config, + Storage const& storage) -> std::optional<ArtifactDigest> { + auto const test_dir = storage_config.CreateTypedTmpDir("tmp"); + auto head_temp_directory = TmpDir::Create(test_dir->GetPath() / "head_dir"); + auto const head_temp_dir_path = head_temp_directory->GetPath(); + // ├── exec_1 + // ├── file_1 + // ├── symlink_to_nested_dir_1_1 -> nested_dir_1 / nested_dir_1_1 + // ├── symlink_to_nested_dir_2_1 -> nested_dir_2 / nested_dir_2_1 + // ├── nested_dir_1 + // │ ├── ... + // │ ├── nested_dir_1_1 + // │ │ └── ... + // │ └── nested_dir_1_2 + // │ └── ... + // └── nested_dir_2 + // ├── ... + // ├── nested_dir_2_1 + // │ └── ... + // └── nested_dir_2_2 + // └── ... + static constexpr std::size_t kFileSize = 128; + auto const file_path = head_temp_dir_path / "file_1"; + if (not LargeObjectUtils::GenerateFile(file_path, kFileSize)) { + return std::nullopt; + } + + auto const exec_path = head_temp_dir_path / "exec_1"; + if (not LargeObjectUtils::GenerateFile(exec_path, + kFileSize, + /*is_executable =*/true)) { + return std::nullopt; + } + + std::array const directories = { + head_temp_dir_path / "nested_dir_1", + head_temp_dir_path / "nested_dir_1" / "nested_dir_1_1", + head_temp_dir_path / "nested_dir_1" / "nested_dir_1_2", + head_temp_dir_path / "nested_dir_2", + head_temp_dir_path / "nested_dir_2" / "nested_dir_2_1", + head_temp_dir_path / "nested_dir_2" / "nested_dir_2_2"}; + + static constexpr std::size_t kDirEntries = 16; + for (auto const& path : directories) { + if (not LargeObjectUtils::GenerateDirectory(path, kDirEntries)) { + return std::nullopt; + } + } + + // Create non-upwards symlinks in the top directory: + if (not FileSystemManager::CreateNonUpwardsSymlink( + std::filesystem::path("nested_dir_1") / "nested_dir_1_1", + head_temp_dir_path / "symlink_to_nested_dir_1_1") or + not FileSystemManager::CreateNonUpwardsSymlink( + std::filesystem::path("nested_dir_2") / "nested_dir_2_1", + head_temp_dir_path / "symlink_to_nested_dir_2_1")) { + return std::nullopt; + } + return CreateDirectory(head_temp_dir_path, storage); +} + +[[nodiscard]] auto ReadGitTree(Storage const& storage, + ArtifactDigest const& tree) + -> std::optional<GitRepo::tree_entries_t> { + auto const tree_path = storage.CAS().TreePath(tree); + if (not tree_path) { + return std::nullopt; + } + + auto const tree_content = FileSystemManager::ReadFile(*tree_path); + if (not tree_content) { + return std::nullopt; + } + + auto const check_symlinks = + [&storage](std::vector<ArtifactDigest> const& ids) { + return std::all_of( + ids.begin(), ids.end(), [&storage](auto const& id) -> bool { + auto path_to_symlink = + storage.CAS().BlobPath(id, /*is_executable=*/false); + if (not path_to_symlink) { + return false; + } + auto const content = + FileSystemManager::ReadFile(*path_to_symlink); + return content and PathIsNonUpwards(*content); + }); + }; + return GitRepo::ReadTreeData(*tree_content, + tree.hash(), + check_symlinks, + /*is_hex_id=*/true); +} + +[[nodiscard]] auto ValidateTreeStructure(ArtifactDigest const& digest, + Storage const& storage) -> bool { + auto tree_entries = ReadGitTree(storage, digest); + if (not tree_entries) { + return false; + } + + auto const empty_blob_hash = ArtifactDigest{}.hash(); + for (auto const& [raw_id, es] : *tree_entries) { + auto const hex_id = ToHexString(raw_id); + for (auto const& entry : es) { + switch (entry.type) { + case ObjectType::Tree: { + auto const git_digest = ArtifactDigestFactory::Create( + HashFunction::Type::GitSHA1, + hex_id, + /*size is unknown*/ 0, + IsTreeObject(entry.type)); + if (not git_digest or + not ValidateTreeStructure(*git_digest, storage)) { + return false; + } + } break; + default: { + if (hex_id != empty_blob_hash) { + return false; + } + } + } + } + } + return true; +} + +[[nodiscard]] auto CountTreeEntries( + ArtifactDigest const& digest, + Storage const& storage, + gsl::not_null<TreeEntriesHitContainer*> const& container, + bool increment) -> bool { + auto tree_entries = ReadGitTree(storage, digest); + if (not tree_entries) { + return false; + } + + auto const empty_blob_hash = + ArtifactDigestFactory::HashDataAs<ObjectType::File>( + storage.GetHashFunction(), std::string{}); + for (auto const& [raw_id, es] : *tree_entries) { + auto const hex_id = ToHexString(raw_id); + for (auto const& entry : es) { + if (IsTreeObject(entry.type)) { + auto const git_digest = + ArtifactDigestFactory::Create(HashFunction::Type::GitSHA1, + hex_id, + /*size is unknown*/ 0, + IsTreeObject(entry.type)); + if (not git_digest or + not CountTreeEntries( + *git_digest, storage, container, increment)) { + return false; + } + } + increment ? ++(*container)[entry] : --(*container)[entry]; + } + } + return true; +} + } // namespace |