1 #include "failure_list_trie_node.h" 2 3 #include <memory> 4 #include <string> 5 6 #include "absl/status/status.h" 7 #include "absl/strings/match.h" 8 #include "absl/strings/str_cat.h" 9 #include "absl/strings/str_format.h" 10 #include "absl/strings/str_split.h" 11 #include "absl/strings/string_view.h" 12 #include "absl/types/optional.h" 13 14 namespace google { 15 namespace protobuf { 16 Insert(absl::string_view test_name)17absl::Status FailureListTrieNode::Insert(absl::string_view test_name) { 18 auto result = WalkDownMatch(test_name); 19 if (result.has_value()) { 20 return absl::AlreadyExistsError( 21 absl::StrFormat("Test name %s already exists in the trie FROM %s", 22 test_name, result.value())); 23 } 24 25 auto sections = absl::StrSplit(test_name, '.'); 26 for (auto section : sections) { 27 if (absl::StrContains(section, '*') && section.length() > 1) { 28 return absl::InvalidArgumentError(absl::StrFormat( 29 "Test name %s contains invalid wildcard(s) (wildcards " 30 "must span the whole of a section)", 31 test_name)); 32 } 33 } 34 InsertImpl(test_name); 35 return absl::OkStatus(); 36 } 37 InsertImpl(absl::string_view test_name)38void FailureListTrieNode::InsertImpl(absl::string_view test_name) { 39 absl::string_view section = test_name.substr(0, test_name.find('.')); 40 41 // Extracted last section -> no more '.' -> test_name_copy will be equal to 42 // section 43 if (test_name == section) { 44 children_.push_back(std::make_unique<FailureListTrieNode>(section)); 45 return; 46 } 47 test_name = test_name.substr(section.length() + 1); 48 for (auto& child : children_) { 49 if (child->data_ == section) { 50 return child->InsertImpl(test_name); 51 } 52 } 53 // No match 54 children_.push_back(std::make_unique<FailureListTrieNode>(section)); 55 children_.back()->InsertImpl(test_name); 56 } 57 WalkDownMatch(absl::string_view test_name)58absl::optional<std::string> FailureListTrieNode::WalkDownMatch( 59 absl::string_view test_name) { 60 absl::string_view section = test_name.substr(0, test_name.find('.')); 61 // test_name cannot be overridden 62 absl::string_view to_match; 63 if (section != test_name) { 64 to_match = test_name.substr(section.length() + 1); 65 } 66 67 for (auto& child : children_) { 68 if (child->data_ == section || child->data_ == "*" || section == "*") { 69 absl::string_view appended = child->data_; 70 // Extracted last section -> no more '.' -> test_name will be 71 // equal to section 72 if (test_name == section) { 73 // Must match all the way to the bottom of the tree 74 if (child->children_.empty()) { 75 return std::string(appended); 76 } 77 } else { 78 auto result = child->WalkDownMatch(to_match); 79 if (result.has_value()) { 80 return absl::StrCat(appended, ".", result.value()); 81 } 82 } 83 } 84 } 85 // No match 86 return absl::nullopt; 87 } 88 } // namespace protobuf 89 } // namespace google 90