[tracker/wip/carlosg/more-sparql-fixes: 8/9] libtracker-data: Fix negated property paths

[Carlos Garnacho <carlosg src gnome org>]

commit f1a328292d4ca2619c04beb5a901adcab50cfc11
Author: Carlos Garnacho <carlosg gnome org>
Date:   Sat Mar 26 20:27:11 2022 +0100

    libtracker-data: Fix negated property paths
    
    Fix some brokenness in dealing with the parse tree, and make the
    algebra actually equivalent to the spec. There were two rough points:
    
    - Negated inverse paths cannot be implemented on top of the inverse
      path implementation. "<a> !^:prop <b>" must match all properties
      from <b> to <a> that are not :prop.
    - The combination of inverse and regular paths in a negated path
      (e.g. "<a> !(:prop|^:prop) <b>") must intersect the inverse and
      regular paths separately and join those with an alternate '|' path.
    
    This makes negated property paths consistent with the definition
    at https://www.w3.org/TR/sparql11-query/#sparqlTranslatePathExpressions
    and following algebra.

 src/libtracker-data/tracker-sparql-types.c |   6 +-
 src/libtracker-data/tracker-sparql-types.h |   1 +
 src/libtracker-data/tracker-sparql.c       | 128 +++++++++++++++++++----------
 3 files changed, 91 insertions(+), 44 deletions(-)
---
diff --git a/src/libtracker-data/tracker-sparql-types.c b/src/libtracker-data/tracker-sparql-types.c
index 9211ddbf2..50ad62c05 100644
--- a/src/libtracker-data/tracker-sparql-types.c
+++ b/src/libtracker-data/tracker-sparql-types.c
@@ -560,7 +560,8 @@ tracker_path_element_property_new (TrackerPathOperator  op,
 
        g_return_val_if_fail (TRACKER_IS_PROPERTY (prop), NULL);
        g_return_val_if_fail (op == TRACKER_PATH_OPERATOR_NONE ||
-                             op == TRACKER_PATH_OPERATOR_NEGATED, NULL);
+                             op == TRACKER_PATH_OPERATOR_NEGATED ||
+                             op == TRACKER_PATH_OPERATOR_NEGATED_INVERSE, NULL);
 
        elem = g_new0 (TrackerPathElement, 1);
        elem->op = op;
@@ -631,6 +632,9 @@ tracker_path_element_set_unique_name (TrackerPathElement *elem,
        case TRACKER_PATH_OPERATOR_INTERSECTION:
                name = "intersect";
                break;
+       case TRACKER_PATH_OPERATOR_NEGATED_INVERSE:
+               name = "neg_inv";
+               break;
        default:
                g_assert_not_reached ();
        }
diff --git a/src/libtracker-data/tracker-sparql-types.h b/src/libtracker-data/tracker-sparql-types.h
index 3829fd1d6..23bb06ea0 100644
--- a/src/libtracker-data/tracker-sparql-types.h
+++ b/src/libtracker-data/tracker-sparql-types.h
@@ -160,6 +160,7 @@ typedef enum {
        TRACKER_PATH_OPERATOR_ZEROORMORE,  /* * */
        TRACKER_PATH_OPERATOR_NEGATED,     /* ! */
        TRACKER_PATH_OPERATOR_INTERSECTION, /* Used for negated paths */
+       TRACKER_PATH_OPERATOR_NEGATED_INVERSE, /* !^, used for negated paths */
 } TrackerPathOperator;
 
 struct _TrackerPathElement {
diff --git a/src/libtracker-data/tracker-sparql.c b/src/libtracker-data/tracker-sparql.c
index d32005212..98cd0711e 100644
--- a/src/libtracker-data/tracker-sparql.c
+++ b/src/libtracker-data/tracker-sparql.c
@@ -1093,12 +1093,22 @@ _prepend_path_element (TrackerSparql      *sparql,
                                       path_elem->data.composite.child1->name);
                break;
        case TRACKER_PATH_OPERATOR_NEGATED:
-               _append_string_printf (sparql,
-                                      "\"%s\" (ID, value, graph, ID_type, value_type) AS "
-                                      "(SELECT subject AS ID, object AS value, graph, %d, object_type "
-                                      "FROM \"tracker_triples\" ",
-                                      path_elem->name,
-                                      TRACKER_PROPERTY_TYPE_RESOURCE);
+       case TRACKER_PATH_OPERATOR_NEGATED_INVERSE:
+               if (path_elem->op == TRACKER_PATH_OPERATOR_NEGATED) {
+                       _append_string_printf (sparql,
+                                              "\"%s\" (ID, value, graph, ID_type, value_type) AS "
+                                              "(SELECT subject AS ID, object_raw AS value, graph, %d, 
object_type "
+                                              "FROM \"tracker_triples\" ",
+                                              path_elem->name,
+                                              TRACKER_PROPERTY_TYPE_RESOURCE);
+               } else {
+                       _append_string_printf (sparql,
+                                              "\"%s\" (ID, value, graph, ID_type, value_type) AS "
+                                              "(SELECT object_raw AS ID, subject AS value, graph, 
object_type, %d "
+                                              "FROM \"tracker_triples\" ",
+                                              path_elem->name,
+                                              TRACKER_PROPERTY_TYPE_RESOURCE);
+               }
 
                if (!tracker_token_is_empty (&sparql->current_state->graph) &&
                    tracker_sparql_find_graph (sparql, tracker_token_get_idstring 
(&sparql->current_state->graph))) {
@@ -6928,6 +6938,45 @@ translate_PathPrimary (TrackerSparql  *sparql,
        return TRUE;
 }
 
+static TrackerPathElement *
+intersect_path_elements (TrackerSparql *sparql,
+                         GPtrArray     *path_elems)
+{
+       TrackerPathElement *elem;
+
+       if (path_elems->len == 0)
+               return NULL;
+
+       if (path_elems->len == 1)
+               return g_ptr_array_index (path_elems, 0);
+
+       if (path_elems->len > 1) {
+               guint i;
+
+               elem = tracker_path_element_operator_new (TRACKER_PATH_OPERATOR_INTERSECTION,
+                                                         tracker_token_get_idstring 
(&sparql->current_state->graph),
+                                                         g_ptr_array_index (path_elems, 0),
+                                                         g_ptr_array_index (path_elems, 1));
+               tracker_select_context_add_path_element (TRACKER_SELECT_CONTEXT (sparql->context),
+                                                        elem);
+               _prepend_path_element (sparql, elem);
+
+               for (i = 2; i < path_elems->len; i++) {
+                       TrackerPathElement *child;
+
+                       child = g_ptr_array_index (path_elems, i);
+                       elem = tracker_path_element_operator_new (TRACKER_PATH_OPERATOR_INTERSECTION,
+                                                                 tracker_token_get_idstring 
(&sparql->current_state->graph),
+                                                                 child, elem);
+                       tracker_select_context_add_path_element (TRACKER_SELECT_CONTEXT (sparql->context),
+                                                                elem);
+                       _prepend_path_element (sparql, elem);
+               }
+       }
+
+       return elem;
+}
+
 static gboolean
 translate_PathNegatedPropertySet (TrackerSparql  *sparql,
                                   GError        **error)
@@ -6939,45 +6988,47 @@ translate_PathNegatedPropertySet (TrackerSparql  *sparql,
        if (_check_in_rule (sparql, NAMED_RULE_PathOneInPropertySet))
                _call_rule (sparql, NAMED_RULE_PathOneInPropertySet, error);
        else if (_accept (sparql, RULE_TYPE_LITERAL, LITERAL_OPEN_PARENS)) {
-               GPtrArray *path_elems;
+               TrackerPathElement *negated, *negated_inverse;
+               GPtrArray *negated_elems, *negated_inverse_elems;
 
-               path_elems = g_ptr_array_new ();
+               negated_elems = g_ptr_array_new ();
+               negated_inverse_elems = g_ptr_array_new ();
 
-               _call_rule (sparql, NAMED_RULE_PathEltOrInverse, error);
-               g_ptr_array_add (path_elems, sparql->current_state->path);
+               _call_rule (sparql, NAMED_RULE_PathOneInPropertySet, error);
+               g_ptr_array_add (sparql->current_state->path->op == TRACKER_PATH_OPERATOR_NEGATED ?
+                                negated_elems : negated_inverse_elems,
+                                sparql->current_state->path);
 
-               while (_check_in_rule (sparql, NAMED_RULE_PathOneInPropertySet)) {
+               while (_accept (sparql, RULE_TYPE_LITERAL, LITERAL_PATH_ALTERNATIVE)) {
                        _call_rule (sparql, NAMED_RULE_PathOneInPropertySet, error);
-                       g_ptr_array_add (path_elems, sparql->current_state->path);
+                       g_ptr_array_add (sparql->current_state->path->op == TRACKER_PATH_OPERATOR_NEGATED ?
+                                        negated_elems : negated_inverse_elems,
+                                        sparql->current_state->path);
                }
 
-               if (path_elems->len > 1) {
-                       guint i;
+               negated = intersect_path_elements (sparql, negated_elems);
+               negated_inverse = intersect_path_elements (sparql, negated_inverse_elems);
 
-                       path_elem = tracker_path_element_operator_new (TRACKER_PATH_OPERATOR_INTERSECTION,
+               if (negated && negated_inverse) {
+                       path_elem = tracker_path_element_operator_new (TRACKER_PATH_OPERATOR_ALTERNATIVE,
                                                                       tracker_token_get_idstring 
(&sparql->current_state->graph),
-                                                                      g_ptr_array_index (path_elems, 0),
-                                                                      g_ptr_array_index (path_elems, 1));
+                                                                      negated, negated_inverse);
                        tracker_select_context_add_path_element (TRACKER_SELECT_CONTEXT (sparql->context),
                                                                 path_elem);
                        _prepend_path_element (sparql, path_elem);
-
-                       for (i = 2; i < path_elems->len; i++) {
-                               TrackerPathElement *child;
-
-                               child = g_ptr_array_index (path_elems, i);
-                               path_elem = tracker_path_element_operator_new 
(TRACKER_PATH_OPERATOR_INTERSECTION,
-                                                                              tracker_token_get_idstring 
(&sparql->current_state->graph),
-                                                                              child, path_elem);
-                               tracker_select_context_add_path_element (TRACKER_SELECT_CONTEXT 
(sparql->context),
-                                                                        path_elem);
-                               _prepend_path_element (sparql, path_elem);
-                       }
-
-                       sparql->current_state->path = path_elem;
+               } else if (negated) {
+                       path_elem = negated;
+               } else if (negated_inverse) {
+                       path_elem = negated_inverse;
+               } else {
+                       g_assert_not_reached ();
                }
 
+               sparql->current_state->path = path_elem;
+
                _expect (sparql, RULE_TYPE_LITERAL, LITERAL_CLOSE_PARENS);
+               g_ptr_array_unref (negated_elems);
+               g_ptr_array_unref (negated_inverse_elems);
        } else {
                g_assert_not_reached ();
        }
@@ -7024,7 +7075,9 @@ translate_PathOneInPropertySet (TrackerSparql  *sparql,
                                                                                 prop);
 
                if (!path_elem) {
-                       path_elem = tracker_path_element_property_new (TRACKER_PATH_OPERATOR_NEGATED,
+                       path_elem = tracker_path_element_property_new (inverse ?
+                                                                      TRACKER_PATH_OPERATOR_NEGATED_INVERSE :
+                                                                      TRACKER_PATH_OPERATOR_NEGATED,
                                                                       tracker_token_get_idstring 
(&sparql->current_state->graph),
                                                                       prop);
                        tracker_select_context_add_path_element (TRACKER_SELECT_CONTEXT (sparql->context),
@@ -7038,17 +7091,6 @@ translate_PathOneInPropertySet (TrackerSparql  *sparql,
                g_assert_not_reached ();
        }
 
-       if (inverse) {
-               path_elem = tracker_path_element_operator_new (TRACKER_PATH_OPERATOR_INVERSE,
-                                                              tracker_token_get_idstring 
(&sparql->current_state->graph),
-                                                              sparql->current_state->path,
-                                                              NULL);
-               tracker_select_context_add_path_element (TRACKER_SELECT_CONTEXT (sparql->context),
-                                                        path_elem);
-               _prepend_path_element (sparql, path_elem);
-               sparql->current_state->path = path_elem;
-       }
-
        return TRUE;
 }