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

1 files changed, 66 insertions, 2 deletions

diff --git a/src/libtracker-data/tracker-sparql.c b/src/libtracker-data/tracker-sparql.c
index bcdcd52e7..314863169 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, *vars;
+
+	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);
+
+	vars = g_hash_table_get_keys (cur_context->variable_set);
+	cur = tracker_sparql_swap_builder (sparql, pre);
+	append_subquery_select_vars (sparql, cur_context, vars);
+	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, ")) ");
+		g_list_free (intersection);
+	} else {
+		cur = tracker_sparql_swap_builder (sparql, post);
+		_append_string (sparql, ") EXCEPT ");
+		append_subquery_select_vars (sparql, context, vars);
+
+		tracker_sparql_swap_builder (sparql, cur);
+		_append_string (sparql, ") ");
+	}
+
+	g_list_free (vars);
 
 	return TRUE;
 }