Repository: protocolbuffers/protobuf (language: python)

Issue:
Fix failure list trie behavior
There was no mechanism to recognize test names as prefix of another. Although it seems hard to see where this might occur in practice, this is the way that a trie **should** behave. In other words, this behavior should be here just in case. 

The current behavior is that if someone were to insert "Recommended.Proto2.Whatever" and "Recommended.Proto2" to the trie and tried to match "Recommended.Proto2", then it would return false when it should return true. Although this example is not good on a practical sense (why would we ever have a test name like "Recommended.Proto2"...), I can imagine a test name being a derivative of a general case: "Recommended.Proto2.General" and "Recommended.Proto2.General.Specific". Maybe we shouldn't ever have a naming convention like that
; but since there's no standard/enforced naming convention, there's no way to say if we want this behavior or not. 

There might be some debate of whether or not to consider these prefixes as duplicates, but I'm not completely sure. We might be able to further enforce naming convention in that "no new test name should be a prefix of another". 

Let me know what you  think whoever reviews this!


Discussion / hints:

Fix patch:
diff --git a/conformance/failure_list_trie_node.cc b/conformance/failure_list_trie_node.cc
index 95e27d6b5e6b..de2c67aff690 100644
--- a/conformance/failure_list_trie_node.cc
+++ b/conformance/failure_list_trie_node.cc
@@ -38,27 +38,37 @@ absl::Status FailureListTrieNode::Insert(absl::string_view test_name) {
 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);
+  bool is_last_section = test_name == section;
+
+  // test_name cannot be overwritten
+  absl::string_view test_name_rest =
+      is_last_section ? "" : test_name.substr(section.length() + 1);
   for (auto& child : children_) {
     if (child->data_ == section) {
-      return child->InsertImpl(test_name);
+      if (is_last_section) {
+        // Extracted last section -> no more '.' -> test_name will be equal to
+        // section
+        child->is_test_name_ = true;
+      } else {
+        child->InsertImpl(test_name_rest);
+      }
+      return;
     }
   }
+
   // No match
   children_.push_back(std::make_unique<FailureListTrieNode>(section));
-  children_.back()->InsertImpl(test_name);
+  if (is_last_section) {
+    children_.back()->is_test_name_ = true;
+    return;
+  }
+  children_.back()->InsertImpl(test_name_rest);
 }
 
 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
+  // test_name cannot be overwritten
   absl::string_view to_match;
   if (section != test_name) {
     to_match = test_name.substr(section.length() + 1);
@@ -70,8 +80,7 @@ absl::optional<std::string> FailureListTrieNode::WalkDownMatch(
       // 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()) {
+        if (child->is_test_name_) {
           return std::string(appended);
         }
       } else {
diff --git a/conformance/failure_list_trie_node.h b/conformance/failure_list_trie_node.h
index 2c7409d04e7d..7efaa5e6150b 100644
--- a/conformance/failure_list_trie_node.h
+++ b/conformance/failure_list_trie_node.h
@@ -35,7 +35,8 @@ namespace protobuf {
 class FailureListTrieNode {
  public:
   FailureListTrieNode() : data_("") {}
-  explicit FailureListTrieNode(absl::string_view data) : data_(data) {}
+  explicit FailureListTrieNode(absl::string_view data)
+      : data_(data), is_test_name_(false) {}
 
   // Will attempt to insert a test name into the trie returning
   // absl::StatusCode::kAlreadyExists if the test name already exists or
@@ -50,6 +51,7 @@ class FailureListTrieNode {
  private:
   absl::string_view data_;
   std::vector<std::unique_ptr<FailureListTrieNode>> children_;
+  bool is_test_name_;
   void InsertImpl(absl::string_view test_name);
 };
 }  // namespace protobuf


Test patch:
diff --git a/conformance/failure_list_trie_node_test.cc b/conformance/failure_list_trie_node_test.cc
index 2dedaa48122c..7611d4d52bc2 100644
--- a/conformance/failure_list_trie_node_test.cc
+++ b/conformance/failure_list_trie_node_test.cc
@@ -1,7 +1,5 @@
 #include "failure_list_trie_node.h"
 
-#include <memory>
-
 #include <gmock/gmock.h>
 #include <gtest/gtest.h>
 #include "absl/status/status.h"
@@ -121,5 +119,23 @@ TEST(FailureListTrieTest, InsertInvalidWildcardFails) {
               StatusIs(absl::StatusCode::kInvalidArgument,
                        HasSubstr("invalid wildcard")));
 }
+
+TEST(FailureListTrieTest, PrefixMarkedAsTestNameRecognizedWithoutWildcards) {
+  auto root_ = std::make_unique<FailureListTrieNode>("dummy");
+  ASSERT_OK(root_->Insert("Recommended.Proto2.ProtobufInput.World"));
+
+  ASSERT_OK(root_->Insert("Recommended.Proto2"));
+  EXPECT_THAT(root_->WalkDownMatch("Recommended.Proto2"),
+              Optional(Eq("Recommended.Proto2")));
+}
+
+TEST(FailureListTrieTest, PrefixMarkedAsTestNameRecognizedWithWildcards) {
+  auto root_ = std::make_unique<FailureListTrieNode>("dummy");
+  ASSERT_OK(root_->Insert("Recommended.*.*.*"));
+
+  ASSERT_OK(root_->Insert("Recommended.*.*"));
+  EXPECT_THAT(root_->WalkDownMatch("Recommended.*.Hello"),
+              Optional(Eq("Recommended.*.*")));
+}
 }  // namespace protobuf
 }  // namespace google