Repository: LLNL/hatchet

Issue:
Match 1 or more (+) wildcard/quantifier doesn't work when starting a query
Kudos to @vanessalama09 for finding this.

When using the "+" wildcard/quantifier to start a query, the query system will fail to find any matches to the corresponding query node. This is due to the "match 1" part of the "match 1 or more" being captured by the `QueryMatcher._apply_impl` function.

Discussion:

Patch:
diff --git a/hatchet/query.py b/hatchet/query.py
index fda7a46..3c3a4c7 100644
--- a/hatchet/query.py
+++ b/hatchet/query.py
@@ -462,8 +462,11 @@ class QueryMatcher(AbstractQuery):
         if isinstance(wildcard_spec, int):
             for i in range(wildcard_spec):
                 self.query_pattern.append((".", filter_func))
+        elif wildcard_spec == "+":
+            self.query_pattern.append((".", filter_func))
+            self.query_pattern.append(("*", filter_func))
         else:
-            assert wildcard_spec == "." or wildcard_spec == "*" or wildcard_spec == "+"
+            assert wildcard_spec == "." or wildcard_spec == "*"
             self.query_pattern.append((wildcard_spec, filter_func))
 
     def _cache_node(self, gf, node):
@@ -531,42 +534,6 @@ class QueryMatcher(AbstractQuery):
                 return [[]]
             return None
 
-    def _match_1_or_more(self, gf, node, wcard_idx):
-        """Process a "+" wildcard in the query on a subgraph.
-
-        Arguments:
-            gf (GraphFrame): the GraphFrame being queried.
-            node (Node): the node being queried against the "+" wildcard.
-            wcard_idx (int): the index associated with the "+" wildcard query.
-
-        Returns:
-            (list): a list of lists representing the paths rooted at "node" that match the "+" wildcard and/or the next query node. Will return None if there is no match for the "+" wildcard or the next query node.
-        """
-        # Cache the node if it's not already cached
-        if node._hatchet_nid not in self.search_cache:
-            self._cache_node(gf, node)
-        # If the current node doesn't match the "+" wildcard, return None.
-        if wcard_idx not in self.search_cache[node._hatchet_nid]:
-            return None
-        # Since a query can't end on a wildcard, return None if the
-        # current node has no children.
-        if len(node.children) == 0:
-            return None
-        # Use _match_0_or_more to collect all additional wildcard matches.
-        matches = []
-        for child in sorted(node.children, key=traversal_order):
-            sub_match = self._match_0_or_more(gf, child, wcard_idx)
-            if sub_match is not None:
-                matches.extend(sub_match)
-        # Since _match_0_or_more will capture the query node that follows
-        # the wildcard, if no paths were retrieved from that function,
-        # the pattern does not continue after the "+" wildcard. Thus,
-        # since a pattern cannot end on a wildcard, the function
-        # returns None.
-        if len(matches) == 0:
-            return None
-        return [[node] + m for m in matches]
-
     def _match_1(self, gf, node, idx):
         """Process a "." wildcard in the query on a subgraph.
 
@@ -606,10 +573,7 @@ class QueryMatcher(AbstractQuery):
         assert isinstance(pattern_root, Node)
         # Starting query node
         pattern_idx = match_idx + 1
-        if (
-            self.query_pattern[match_idx][0] == "*"
-            or self.query_pattern[match_idx][0] == "+"
-        ):
+        if self.query_pattern[match_idx][0] == "*":
             pattern_idx = 0
         # Starting matching pattern
         matches = [[pattern_root]]
@@ -639,19 +603,9 @@ class QueryMatcher(AbstractQuery):
                                 sub_match.append(s)
                             else:
                                 sub_match.extend(s)
-                elif wcard == "+":
-                    if len(m[-1].children) == 0:
-                        sub_match.append(None)
-                    else:
-                        for child in sorted(m[-1].children, key=traversal_order):
-                            s = self._match_1_or_more(gf, child, pattern_idx)
-                            if s is None:
-                                sub_match.append(s)
-                            else:
-                                sub_match.extend(s)
                 else:
                     raise InvalidQueryFilter(
-                        'Query wildcards must be one of ".", "*", or "+"'
+                        'Query wildcards must (internally) be one of "." or "*"'
                     )
                 # Merge the next part of the match path with the
                 # existing part.


Test patch:
diff --git a/hatchet/tests/query.py b/hatchet/tests/query.py
index 96bc1a0..5feb52f 100644
--- a/hatchet/tests/query.py
+++ b/hatchet/tests/query.py
@@ -75,12 +75,17 @@ def test_construct_high_level_api():
     assert query2.query_pattern[3][0] == "."
 
     assert query3.query_pattern[0][0] == "."
-    assert query3.query_pattern[1][0] == "+"
+    assert query3.query_pattern[1][0] == "."
+    assert query3.query_pattern[2][0] == "*"
     assert not query3.query_pattern[1][1](mock_node_mpi)
     assert not query3.query_pattern[1][1](mock_node_ibv)
     assert query3.query_pattern[1][1](mock_node_time_true)
     assert not query3.query_pattern[1][1](mock_node_time_false)
-    assert query3.query_pattern[2][0] == "."
+    assert not query3.query_pattern[2][1](mock_node_mpi)
+    assert not query3.query_pattern[2][1](mock_node_ibv)
+    assert query3.query_pattern[2][1](mock_node_time_true)
+    assert not query3.query_pattern[2][1](mock_node_time_false)
+    assert query3.query_pattern[3][0] == "."
 
     assert query4.query_pattern[0][0] == "."
     assert query4.query_pattern[1][0] == "."
@@ -175,12 +180,17 @@ def test_construct_low_level_api():
         filter_func=ibv_filter
     )
     assert query.query_pattern[0][0] == "."
-    assert query.query_pattern[1][0] == "+"
+    assert query.query_pattern[1][0] == "."
+    assert query.query_pattern[2][0] == "*"
     assert not query.query_pattern[1][1](mock_node_mpi)
     assert not query.query_pattern[1][1](mock_node_ibv)
     assert query.query_pattern[1][1](mock_node_time_true)
     assert not query.query_pattern[1][1](mock_node_time_false)
-    assert query.query_pattern[2][0] == "."
+    assert not query.query_pattern[2][1](mock_node_mpi)
+    assert not query.query_pattern[2][1](mock_node_ibv)
+    assert query.query_pattern[2][1](mock_node_time_true)
+    assert not query.query_pattern[2][1](mock_node_time_false)
+    assert query.query_pattern[3][0] == "."
 
     query.match(filter_func=mpi_filter).rel(3, time_eq_filter).rel(
         filter_func=ibv_filter
@@ -214,7 +224,8 @@ def test_node_caching(mock_graph_literal):
 
     assert 0 in query.search_cache[node._hatchet_nid]
     assert 1 in query.search_cache[node._hatchet_nid]
-    assert 2 not in query.search_cache[node._hatchet_nid]
+    assert 2 in query.search_cache[node._hatchet_nid]
+    assert 3 not in query.search_cache[node._hatchet_nid]
 
 
 def test_match_0_or_more_wildcard(mock_graph_literal):
@@ -247,45 +258,6 @@ def test_match_0_or_more_wildcard(mock_graph_literal):
     assert query._match_0_or_more(gf, none_node, 1) is None
 
 
-def test_match_1_or_more_wildcard(mock_graph_literal):
-    path = [
-        {"name": "qux"},
-        ("+", {"time (inc)": "> 10"}),
-        {"name": "gr[a-z]+", "time (inc)": "<= 10"},
-    ]
-    gf = GraphFrame.from_literal(mock_graph_literal)
-    node = gf.graph.roots[0].children[1]
-    none_node = gf.graph.roots[0].children[2].children[0].children[1].children[0]
-
-    correct_paths = [
-        [
-            node.children[0],
-            node.children[0].children[0],
-            node.children[0].children[0].children[0],
-        ],
-        [node.children[0], node.children[0].children[0]],
-    ]
-
-    query = QueryMatcher(path)
-    matched_paths = []
-    for child in sorted(node.children, key=traversal_order):
-        match = query._match_1_or_more(gf, child, 1)
-        if match is not None:
-            matched_paths.extend(match)
-
-    assert matched_paths == correct_paths
-    assert query._match_1_or_more(gf, none_node, 1) is None
-
-    zero_match_path = [
-        {"name": "qux"},
-        ("+", {"time (inc)": "> 50"}),
-        {"name": "gr[a-z]+", "time (inc)": "<= 10"},
-    ]
-    zero_match_node = gf.graph.roots[0].children[0]
-    query = QueryMatcher(zero_match_path)
-    assert query._match_1_or_more(gf, zero_match_node, 1) is None
-
-
 def test_match_1(mock_graph_literal):
     gf = GraphFrame.from_literal(mock_graph_literal)
     path = [
@@ -462,6 +434,36 @@ def test_apply(mock_graph_literal):
     query = QueryMatcher(path)
     assert query.apply(gf) == []
 
+    # Test a former edge case with the + quantifier/wildcard
+    match = [
+        [gf.graph.roots[0].children[0], gf.graph.roots[0].children[0].children[0]],
+        [
+            gf.graph.roots[0].children[1].children[0].children[0].children[0],
+            gf.graph.roots[0]
+            .children[1]
+            .children[0]
+            .children[0]
+            .children[0]
+            .children[0],
+        ],
+        [
+            gf.graph.roots[1].children[0],
+            gf.graph.roots[1].children[0].children[0],
+        ],
+        [
+            gf.graph.roots[0]
+            .children[2]
+            .children[0]
+            .children[1]
+            .children[0]
+            .children[0],
+        ],
+    ]
+    match = list(set().union(*match))
+    path = [("+", {"name": "ba.*"})]
+    query = QueryMatcher(path)
+    assert sorted(query.apply(gf)) == sorted(match)
+
 
 def test_apply_indices(calc_pi_hpct_db):
     gf = GraphFrame.from_hpctoolkit(str(calc_pi_hpct_db))
@@ -885,12 +887,17 @@ def test_construct_cypher_api():
     assert query2.query_pattern[3][0] == "."
 
     assert query3.query_pattern[0][0] == "."
-    assert query3.query_pattern[1][0] == "+"
+    assert query3.query_pattern[1][0] == "."
+    assert query3.query_pattern[2][0] == "*"
     assert not query3.query_pattern[1][1](mock_node_mpi)
     assert not query3.query_pattern[1][1](mock_node_ibv)
     assert query3.query_pattern[1][1](mock_node_time_true)
     assert not query3.query_pattern[1][1](mock_node_time_false)
-    assert query3.query_pattern[2][0] == "."
+    assert not query3.query_pattern[2][1](mock_node_mpi)
+    assert not query3.query_pattern[2][1](mock_node_ibv)
+    assert query3.query_pattern[2][1](mock_node_time_true)
+    assert not query3.query_pattern[2][1](mock_node_time_false)
+    assert query3.query_pattern[3][0] == "."
 
     assert query4.query_pattern[0][0] == "."
     assert query4.query_pattern[1][0] == "."