[tracker/wip/carlosg/fix-minus: 1/2] libtracker-data: Fix MINUS support

[Carlos Garnacho <carlosg src gnome org>]

commit 228c109e7d69151061f1b1f4580e53f5f2762817
Author: Carlos Garnacho <carlosg gnome org>
Date:   Fri Mar 6 19:59:41 2020 +0100

    libtracker-data: Fix MINUS support
    
    We used to implement MINUS through sqlite's EXCEPT, which requires
    SELECTS on both sides of the operation to have the same variables in
    the same order.
    
    This restriction is a bit inconvenient to us, since we need to cater
    for full/partial/empty variable set matching. It is not feasible to
    make all combinations go through the EXCEPT restrictions.
    
    Instead, make MINUS use SQLite row values syntax feature
    (https://sqlite.org/rowvalue.html), in order to match full and partial
    variable set matches the same way.
    
    The use of EXCEPT is now relegated to situations where variables on left
    and right side do not intersect (e.g. { ?a ?b ?c } MINUS { ?x ?y ?x }),
    and purely out of convenience.
    
    It is worth noting that variables only defined on the right hand side
    do not propagate outside of it (eg. cannot be queried in the upper SELECT).
    
    Closes: https://gitlab.gnome.org/GNOME/tracker/issues/190

 src/libtracker-data/tracker-sparql.c | 68 ++++++++++++++++++++++++++++++++++--
 1 file changed, 66 insertions(+), 2 deletions(-)
---
diff --git a/src/libtracker-data/tracker-sparql.c b/src/libtracker-data/tracker-sparql.c
index bcdcd52e7..51fe37acb 100644
--- a/src/libtracker-data/tracker-sparql.c
+++ b/src/libtracker-data/tracker-sparql.c
@@ -5005,16 +5005,80 @@ append_subquery_select_vars (TrackerSparql  *sparql,
        _append_string (sparql, "FROM (");
 }
 
+static GList *
+intersect_var_set (GHashTable *ht1,
+                  GHashTable *ht2)
+{
+       GHashTableIter iter;
+       GList *intersection = NULL;
+       gpointer key;
+
+       g_hash_table_iter_init (&iter, ht1);
+
+       while (g_hash_table_iter_next (&iter, &key, NULL)) {
+               if (g_hash_table_contains (ht2, key))
+                       intersection = g_list_prepend (intersection, key);
+       }
+
+       return intersection;
+}
+
+
 static gboolean
 translate_MinusGraphPattern (TrackerSparql  *sparql,
                              GError        **error)
 {
+       TrackerStringBuilder *pre, *post, *cur;
+       TrackerContext *cur_context, *context;
+       GList *intersection, *l;
+
+       cur_context = sparql->current_state.context;
+
        /* MinusGraphPattern ::= 'MINUS' GroupGraphPattern
         */
        _expect (sparql, RULE_TYPE_LITERAL, LITERAL_MINUS);
-       _prepend_string (sparql, "SELECT * FROM (");
-       _append_string (sparql, ") EXCEPT ");
+
+       pre = _prepend_placeholder (sparql);
+       post = _append_placeholder (sparql);
+
+       context = tracker_context_new ();
+       tracker_sparql_push_context (sparql, context);
        _call_rule (sparql, NAMED_RULE_GroupGraphPattern, error);
+       tracker_sparql_pop_context (sparql, FALSE);
+
+       intersection = intersect_var_set (cur_context->variable_set, context->variable_set);
+
+       cur = tracker_sparql_swap_builder (sparql, pre);
+       append_subquery_select_vars (sparql, cur_context, intersection);
+       tracker_sparql_swap_builder (sparql, cur);
+
+       if (intersection) {
+               cur = tracker_sparql_swap_builder (sparql, post);
+               _append_string (sparql, ") WHERE (");
+               for (l = intersection; l; l = l->next) {
+                       if (l != intersection)
+                               _append_string (sparql, ", ");
+                       _append_string_printf (sparql, "%s ",
+                                              tracker_variable_get_sql_expression (l->data));
+               }
+
+               _append_string (sparql, ") NOT IN (");
+               append_subquery_select_vars (sparql, context, intersection);
+
+               tracker_sparql_swap_builder (sparql, cur);
+               _append_string (sparql, ")) ");
+       } else {
+               GList *vars;
+
+               cur = tracker_sparql_swap_builder (sparql, post);
+               _append_string (sparql, ") EXCEPT ");
+               vars = g_hash_table_get_keys (cur_context->variable_set);
+               append_subquery_select_vars (sparql, context, vars);
+               g_list_free (vars);
+
+               tracker_sparql_swap_builder (sparql, cur);
+               _append_string (sparql, ") ");
+       }
 
        return TRUE;
 }