1 #ifndef GOOGLE_PROTOBUF_CONFORMANCE_FAILURE_LIST_TRIE_NODE_H__ 2 #define GOOGLE_PROTOBUF_CONFORMANCE_FAILURE_LIST_TRIE_NODE_H__ 3 4 #include <memory> 5 #include <string> 6 #include <vector> 7 8 #include "absl/status/status.h" 9 #include "absl/strings/string_view.h" 10 #include "absl/types/optional.h" 11 12 namespace google { 13 namespace protobuf { 14 15 // Each node represents a section of a test name (divided by '.'). One can 16 // imagine them as prefixes to search for a match. Once we hit a prefix that 17 // doesn't match, we can stop searching. Wildcards matching to any set of 18 // characters are supported. 19 // 20 // This is not a general trie implementation 21 // as pointed out by its name. It is only meant to only be used for conformance 22 // failure lists. 23 // 24 // Example of what the trie might look like in practice: 25 // 26 // (root) 27 // / | 28 // "Recommended" "Required" 29 // / | 30 // "Proto2" "*" 31 // / | | 32 // "JsonInput" "ProtobufInput" "JsonInput" 33 // 34 // 35 class FailureListTrieNode { 36 public: FailureListTrieNode()37 FailureListTrieNode() : data_("") {} FailureListTrieNode(absl::string_view data)38 explicit FailureListTrieNode(absl::string_view data) : data_(data) {} 39 40 // Will attempt to insert a test name into the trie returning 41 // absl::StatusCode::kAlreadyExists if the test name already exists or 42 // absl::StatusCode::kInvalidArgument if the test name contains invalid 43 // wildcards; otherwise, insertion is successful. 44 absl::Status Insert(absl::string_view test_name); 45 46 // Returns what it matched to if it matched anything, otherwise returns 47 // absl::nullopt 48 absl::optional<std::string> WalkDownMatch(absl::string_view test_name); 49 50 private: 51 absl::string_view data_; 52 std::vector<std::unique_ptr<FailureListTrieNode>> children_; 53 void InsertImpl(absl::string_view test_name); 54 }; 55 } // namespace protobuf 56 } // namespace google 57 58 #endif // GOOGLE_PROTOBUF_CONFORMANCE_FAILURE_LIST_TRIE_NODE_H__ 59