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