| // Copyright 2022 The Fuchsia Authors |
| // |
| // Use of this source code is governed by a MIT-style |
| // license that can be found in the LICENSE file or at |
| // https://opensource.org/licenses/MIT |
| |
| #include <lib/devicetree/devicetree.h> |
| #include <lib/stdcompat/span.h> |
| |
| #include <array> |
| #include <memory> |
| #include <string_view> |
| #include <type_traits> |
| |
| #include <zxtest/zxtest.h> |
| |
| namespace { |
| |
| using Comparison = devicetree::NodePath::Comparison; |
| |
| auto as_bytes = [](auto& val) { |
| using byte_type = std::conditional_t<std::is_const_v<std::remove_reference_t<decltype(val)>>, |
| const uint8_t, uint8_t>; |
| return cpp20::span<byte_type>(reinterpret_cast<byte_type*>(&val), sizeof(val)); |
| }; |
| |
| auto append = [](auto& vec, auto&& other) { vec.insert(vec.end(), other.begin(), other.end()); }; |
| |
| uint32_t AsBigEndian(uint32_t val) { |
| auto bytes = as_bytes(val); |
| return static_cast<uint32_t>(bytes[0]) << 24 | static_cast<uint32_t>(bytes[1]) << 16 | |
| static_cast<uint32_t>(bytes[2]) << 8 | static_cast<uint32_t>(bytes[3]); |
| } |
| |
| struct AliasContext { |
| devicetree::Properties properties() { |
| return devicetree::Properties( |
| {property_block.data(), property_block.size()}, |
| std::string_view(reinterpret_cast<const char*>(string_block.data()), string_block.size())); |
| } |
| |
| void Add(std::string_view alias, std::string_view absolute_path) { |
| constexpr std::array<uint8_t, sizeof(uint32_t) - 1> kPadding = {}; |
| |
| uint32_t name_off = AsBigEndian(static_cast<uint32_t>(string_block.size())); |
| // String must be null terminated. |
| append(string_block, alias); |
| string_block.push_back('\0'); |
| |
| // Add the null terminator. |
| uint32_t len = static_cast<uint32_t>(absolute_path.size()) + 1; |
| cpp20::span<const uint8_t> padding; |
| if (auto remainder = len % sizeof(uint32_t); remainder != 0) { |
| padding = cpp20::span(kPadding).subspan(0, sizeof(uint32_t) - remainder); |
| } |
| len = AsBigEndian(len); |
| |
| if (!property_block.empty()) { |
| const uint32_t kFdtPropToken = AsBigEndian(0x00000003); |
| append(property_block, as_bytes(kFdtPropToken)); |
| } |
| append(property_block, as_bytes(len)); |
| append(property_block, as_bytes(name_off)); |
| append(property_block, absolute_path); |
| property_block.push_back('\0'); |
| append(property_block, padding); |
| } |
| |
| std::vector<uint8_t> property_block; |
| std::vector<uint8_t> string_block; |
| }; |
| |
| std::vector<std::string_view> ConvertPath(std::string_view path) { |
| ZX_ASSERT(!path.empty()); |
| |
| std::vector<std::string_view> components; |
| while (!path.empty()) { |
| size_t component_end = path.find('/'); |
| components.push_back(path.substr(0, component_end)); |
| path.remove_prefix(component_end != std::string_view::npos ? component_end : path.size()); |
| if (!path.empty()) { |
| // remove '/' |
| path.remove_prefix(1); |
| } |
| } |
| return components; |
| } |
| |
| struct NodePathHelper { |
| NodePathHelper() = default; |
| NodePathHelper(const NodePathHelper&) = delete; |
| NodePathHelper(NodePathHelper&&) = default; |
| ~NodePathHelper() { |
| while (!path.is_empty()) { |
| // The pointers will get released as part of nodes destructor. |
| std::ignore = path.pop_back(); |
| } |
| } |
| |
| std::vector<std::unique_ptr<devicetree::Node>> nodes; |
| devicetree::NodePath path; |
| }; |
| |
| NodePathHelper ConvertToNodePath(std::string_view path) { |
| NodePathHelper path_helper; |
| auto components = ConvertPath(path); |
| for (auto component : components) { |
| path_helper.nodes.push_back(std::make_unique<devicetree::Node>(component)); |
| path_helper.path.push_back(path_helper.nodes.back().get()); |
| } |
| |
| return path_helper; |
| } |
| |
| auto ToResolvedPath(std::string_view path, |
| std::optional<devicetree::Properties> aliases = std::nullopt) { |
| devicetree::PropertyDecoder decoder(nullptr, devicetree::Properties(), aliases); |
| auto resolved = decoder.ResolvePath(path); |
| ZX_ASSERT(resolved.is_ok()); |
| return resolved.value(); |
| } |
| |
| TEST(NodePathTest, AbsolutePathMismatchSameLength) { |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C/D"); |
| std::string_view target_path = "/A/B/E/D"; |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_EQ(Comparison::kMismatch, node_path.CompareWith(target_path)); |
| } |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B"); |
| std::string_view target_path = "/A/C/E/D"; |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_EQ(Comparison::kMismatch, node_path.CompareWith(target_path)); |
| } |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/C/E/D"); |
| std::string_view target_path = "/A/B"; |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_EQ(Comparison::kMismatch, node_path.CompareWith(target_path)); |
| } |
| } |
| |
| TEST(NodePathTest, AbsolutePathMatch) { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C/D"); |
| std::string_view target_path = "/A/B/C/D"; |
| |
| EXPECT_EQ(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_EQ(Comparison::kEqual, node_path.CompareWith(target_path)); |
| } |
| |
| TEST(NodePathTest, AbsolutePathAncestor) { |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/"); |
| std::string_view target_path = "/A/B/C/D"; |
| |
| EXPECT_TRUE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsParentOf(target_path)); |
| EXPECT_EQ(Comparison::kIndirectAncestor, node_path.CompareWith(target_path)); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| } |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B"); |
| std::string_view target_path = "/A/B/C/D"; |
| |
| EXPECT_TRUE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsParentOf(target_path)); |
| EXPECT_EQ(Comparison::kIndirectAncestor, node_path.CompareWith(target_path)); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| } |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C"); |
| std::string_view target_path = "/A/B/C/D"; |
| |
| EXPECT_TRUE(node_path.IsAncestorOf(target_path)); |
| EXPECT_TRUE(node_path.IsParentOf(target_path)); |
| EXPECT_EQ(Comparison::kParent, node_path.CompareWith(target_path)); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| } |
| { |
| // A path is never an ancestor of itself. |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C"); |
| std::string_view target_path = "/A/B/C"; |
| |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsParentOf(target_path)); |
| } |
| } |
| |
| TEST(NodePathTest, AbsolutePathDescendent) { |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C/D"); |
| std::string_view target_path = "/"; |
| |
| EXPECT_TRUE(node_path.IsDescendentOf(target_path)); |
| EXPECT_FALSE(node_path.IsChildOf(target_path)); |
| EXPECT_EQ(Comparison::kIndirectDescendent, node_path.CompareWith(target_path)); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| } |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C/D"); |
| std::string_view target_path = "/A/B"; |
| |
| EXPECT_TRUE(node_path.IsDescendentOf(target_path)); |
| EXPECT_FALSE(node_path.IsChildOf(target_path)); |
| EXPECT_EQ(Comparison::kIndirectDescendent, node_path.CompareWith(target_path)); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| } |
| { |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C/D"); |
| std::string_view target_path = "/A/B/C"; |
| |
| EXPECT_TRUE(node_path.IsDescendentOf(target_path)); |
| EXPECT_TRUE(node_path.IsChildOf(target_path)); |
| EXPECT_EQ(Comparison::kChild, node_path.CompareWith(target_path)); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| } |
| { |
| // A path is never a descendent of itself. |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C"); |
| std::string_view target_path = "/A/B/C"; |
| |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_FALSE(node_path.IsChildOf(target_path)); |
| } |
| } |
| |
| TEST(NodePathTest, AliasedPathMismatch) { |
| AliasContext aliases; |
| aliases.Add("alias", "/A/B/D"); |
| |
| { // Stem mismatch with non empty leaf. |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C/D"); |
| auto target_path = ToResolvedPath("alias/D", aliases.properties()); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_EQ(Comparison::kMismatch, node_path.CompareWith(target_path)); |
| } |
| { // Stem mismatch with empty leaf |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C/D"); |
| auto target_path = ToResolvedPath("alias", aliases.properties()); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_EQ(Comparison::kMismatch, node_path.CompareWith(target_path)); |
| } |
| { // Stem match left mismatch. |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/D/D"); |
| auto target_path = ToResolvedPath("alias/C", aliases.properties()); |
| |
| EXPECT_NE(target_path, node_path); |
| EXPECT_FALSE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsDescendentOf(target_path)); |
| EXPECT_EQ(Comparison::kMismatch, node_path.CompareWith(target_path)); |
| } |
| } |
| |
| TEST(NodePathTest, AliasedPathAncestor) { |
| AliasContext aliases; |
| aliases.Add("alias", "/A/B/D"); |
| |
| { // Root is ancestor of every node. |
| auto [nodes, node_path] = ConvertToNodePath("/"); |
| auto target_path = ToResolvedPath("alias", aliases.properties()); |
| |
| EXPECT_TRUE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsParentOf(target_path)); |
| EXPECT_EQ(Comparison::kIndirectAncestor, node_path.CompareWith(target_path)); |
| } |
| |
| { // Ancestor of stem Empty leaf |
| auto [nodes, node_path] = ConvertToNodePath("/A/B"); |
| auto target_path = ToResolvedPath("alias", aliases.properties()); |
| |
| EXPECT_TRUE(node_path.IsAncestorOf(target_path)); |
| EXPECT_TRUE(node_path.IsParentOf(target_path)); |
| EXPECT_EQ(Comparison::kParent, node_path.CompareWith(target_path)); |
| } |
| |
| { // Ancestor of stem non empty leaf |
| auto [nodes, node_path] = ConvertToNodePath("/A/B"); |
| auto target_path = ToResolvedPath("alias/C", aliases.properties()); |
| |
| EXPECT_TRUE(node_path.IsAncestorOf(target_path)); |
| EXPECT_FALSE(node_path.IsParentOf(target_path)); |
| EXPECT_EQ(Comparison::kIndirectAncestor, node_path.CompareWith(target_path)); |
| } |
| |
| { // Ancestor of leaf (stem matches) |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/D"); |
| auto target_path = ToResolvedPath("alias/C", aliases.properties()); |
| |
| EXPECT_TRUE(node_path.IsAncestorOf(target_path)); |
| EXPECT_TRUE(node_path.IsParentOf(target_path)); |
| EXPECT_EQ(Comparison::kParent, node_path.CompareWith(target_path)); |
| } |
| } |
| |
| TEST(NodePathTest, AliasedPathDescendent) { |
| AliasContext aliases; |
| aliases.Add("alias", "/A"); |
| |
| { // Current node is descendant of the alias. |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C"); |
| auto target_path = ToResolvedPath("alias", aliases.properties()); |
| |
| EXPECT_TRUE(node_path.IsDescendentOf(target_path)); |
| EXPECT_FALSE(node_path.IsChildOf(target_path)); |
| EXPECT_EQ(Comparison::kIndirectDescendent, node_path.CompareWith(target_path)); |
| } |
| |
| { // Current Node is descendant of the alias with the leaf. |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C"); |
| auto target_path = ToResolvedPath("alias/B", aliases.properties()); |
| |
| EXPECT_TRUE(node_path.IsDescendentOf(target_path)); |
| EXPECT_TRUE(node_path.IsChildOf(target_path)); |
| EXPECT_EQ(Comparison::kChild, node_path.CompareWith(target_path)); |
| } |
| } |
| |
| TEST(NodePathTest, AliasedPathMatches) { |
| AliasContext aliases; |
| aliases.Add("alias", "/A"); |
| |
| { // Stem only match |
| auto [nodes, node_path] = ConvertToNodePath("/A"); |
| auto target_path = ToResolvedPath("alias", aliases.properties()); |
| |
| EXPECT_EQ(target_path, node_path); |
| EXPECT_EQ(Comparison::kEqual, node_path.CompareWith(target_path)); |
| } |
| |
| { // Stem and leaf match |
| auto [nodes, node_path] = ConvertToNodePath("/A/B/C"); |
| auto target_path = ToResolvedPath("alias/B/C", aliases.properties()); |
| |
| EXPECT_EQ(target_path, node_path); |
| EXPECT_EQ(Comparison::kEqual, node_path.CompareWith(target_path)); |
| } |
| } |
| |
| } // namespace |