path: root/src/libtracker-data/tracker-sparql-query.vala

/*
 * Copyright (C) 2008-2010, Nokia
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 */

namespace Tracker.Sparql {
	enum VariableState {
		NONE,
		BOUND,
		OPTIONAL
	}

	enum UpdateType {
		DELETE,
		INSERT,
		UPDATE
	}

	// Represents a SQL table
	class DataTable : Object {
		public string sql_db_tablename; // as in db schema
		public string sql_query_tablename; // temp. name, generated
		public PredicateVariable predicate_variable;
	}

	abstract class DataBinding : Object {
		public PropertyType data_type;
		public DataTable table;
		public string sql_db_column_name;
		public string sql_expression {
			get {
				if (this._sql_expression == null && table != null) {
					this._sql_expression = "\"%s\".\"%s\"".printf (table.sql_query_tablename, sql_db_column_name);
				}
				return this._sql_expression;
			}
			set {
				this._sql_expression = value;
			}
		}
		string? _sql_expression;
		public string get_extra_sql_expression (string suffix) {
			return "\"%s\".\"%s:%s\"".printf (table.sql_query_tablename, sql_db_column_name, suffix);
		}
	}

	// Represents a mapping of a SPARQL literal to a SQL table and column
	class LiteralBinding : DataBinding {
		public bool is_fts_match;
		public string literal;
	}

	// Represents a mapping of a SPARQL variable to a SQL table and column
	class VariableBinding : DataBinding {
		public weak Variable variable;
		// Specified whether SQL column may contain NULL entries
		public bool maybe_null;
		public bool in_simple_optional;
		public Class? type;
	}

	class VariableBindingList : Object {
		public List<VariableBinding> list;
	}

	class Variable : Object {
		public string name { get; private set; }
		public int index { get; private set; }
		public string sql_expression { get; private set; }
		public VariableBinding binding;
		string sql_identifier;

		public Variable (string name, int index) {
			this.name = name;
			this.index = index;
			this.sql_identifier = "%d_u".printf (index);
			this.sql_expression = "\"%s\"".printf (sql_identifier);
		}

		public string get_extra_sql_expression (string suffix) {
			return "\"%s:%s\"".printf (sql_identifier, suffix);
		}

		public static bool equal (Variable a, Variable b) {
			return a.index == b.index;
		}

		public static uint hash (Variable variable) {
			return (uint) variable.index;
		}
	}

	class Context {
		public weak Query query;

		public Context? parent_context;
		// All SPARQL variables within a subgraph pattern (used by UNION)
		// value is VariableState
		public HashTable<Variable,int> var_set;

		public HashTable<string,Variable> var_map;
		// All selected SPARQL variables (used by compositional subqueries)
		public HashTable<Variable,int> select_var_set;

		// Variables used as predicates
		public HashTable<Variable,PredicateVariable> predicate_variable_map;

		public bool scalar_subquery;
		public bool need_binding_expression;

		public Context (Query query, Context? parent_context = null) {
			this.query = query;
			this.parent_context = parent_context;
			this.var_set = new HashTable<Variable,int>.full (Variable.hash, Variable.equal, g_object_unref, null);

			if (parent_context == null) {
				select_var_set = new HashTable<Variable,int>.full (Variable.hash, Variable.equal, g_object_unref, null);
				var_map = new HashTable<string,Variable>.full (str_hash, str_equal, g_free, g_object_unref);
				predicate_variable_map = new HashTable<Variable,PredicateVariable>.full (Variable.hash, Variable.equal, g_object_unref, g_object_unref);
			} else {
				select_var_set = parent_context.select_var_set;
				var_map = parent_context.var_map;
				predicate_variable_map = parent_context.predicate_variable_map;
			}
		}

		public Context.subquery (Query query, Context parent_context) {
			this.query = query;
			this.parent_context = parent_context;
			this.var_set = new HashTable<Variable,int>.full (Variable.hash, Variable.equal, g_object_unref, null);

			select_var_set = new HashTable<Variable,int>.full (Variable.hash, Variable.equal, g_object_unref, null);
			var_map = parent_context.var_map;
			predicate_variable_map = new HashTable<Variable,PredicateVariable>.full (Variable.hash, Variable.equal, g_object_unref, g_object_unref);
			scalar_subquery = true;
		}

		internal unowned Variable get_variable (string name) {
			unowned Variable result = this.var_map.lookup (name);
			if (result == null) {
				var variable = new Variable (name, ++query.last_var_index);
				this.var_map.insert (name, variable);

				result = variable;
			}
			return result;
		}
	}

	class SelectContext : Context {
		public PropertyType type;
		public PropertyType[] types = {};
		public string[] variable_names = {};

		public SelectContext (Query query, Context? parent_context = null) {
			base (query, parent_context);
		}

		public SelectContext.subquery (Query query, Context parent_context) {
			base.subquery (query, parent_context);
		}
	}

	class Solution {
		public HashTable<string,int> hash;
		public GenericArray<string> values;
		public int solution_index;

		public Solution () {
			this.hash = new HashTable<string,int> (str_hash, str_equal);
			this.values = new GenericArray<string> ();
		}

		public string? lookup (string variable_name) {
			int variable_index;
			if (!hash.lookup_extended (variable_name, null, out variable_index)) {
				return null;
			}
			return values[solution_index * hash.size () + variable_index];
		}
	}
}

public class Tracker.Sparql.Query : Object {
	SparqlScanner scanner;

	// token buffer
	TokenInfo[] tokens;
	// index of current token in buffer
	int index;
	// number of tokens in buffer
	int size;

	const int BUFFER_SIZE = 32;

	struct TokenInfo {
		public SparqlTokenType type;
		public SourceLocation begin;
		public SourceLocation end;
	}

	const string FN_NS = "http://www.w3.org/2005/xpath-functions#";

	string query_string;
	bool update_extensions;

	internal Expression expression;
	internal Pattern pattern;

	string current_graph;
	string current_subject;
	bool current_subject_is_var;
	string current_predicate;
	bool current_predicate_is_var;

	// SILENT => ignore (non-syntax) errors
	bool silent;

	HashTable<string,string> prefix_map;

	// All SPARQL literals
	internal List<LiteralBinding> bindings;

	internal Context context;

	int bnodeid = 0;
	// base UUID used for blank nodes
	uchar[] base_uuid;
	HashTable<string,string> blank_nodes;

	public Data.Manager manager;

	// Keep track of used SQL identifiers for SPARQL variables
	public int last_var_index;

	public bool no_cache { get; set; }

	public Query (Data.Manager manager, string query) {
		no_cache = false; /* Start with false, expression sets it */
		tokens = new TokenInfo[BUFFER_SIZE];
		prefix_map = new HashTable<string,string>.full (str_hash, str_equal, g_free, g_free);

		base_uuid = new uchar[16];
		uuid_generate (base_uuid);

		this.query_string = query;
		this.manager = manager;

		expression = new Expression (this);
		pattern = new Pattern (this);
	}

	public Query.update (Data.Manager manager, string query) {
		this (manager, query);
		this.update_extensions = true;
	}

	string get_uuid_for_name (uchar[] base_uuid, string name) {
		var checksum = new Checksum (ChecksumType.SHA1);
		// base UUID, unique per file
		checksum.update (base_uuid, 16);

		// node ID
		checksum.update ((uchar[]) name, -1);

		string sha1 = checksum.get_string ();

		// generate name based uuid
		return "urn:uuid:%.8s-%.4s-%.4s-%.4s-%.12s".printf (
			sha1, sha1.substring (8), sha1.substring (12), sha1.substring (16), sha1.substring (20));
	}

	internal string generate_bnodeid (string? user_bnodeid) {
		// user_bnodeid is NULL for anonymous nodes
		if (user_bnodeid == null) {
			return ":%d".printf (++bnodeid);
		} else {
			string uri = null;

			if (blank_nodes != null) {
				uri = blank_nodes.lookup (user_bnodeid);
				if (uri != null) {
					return uri;
				}
			}

			uri = get_uuid_for_name (base_uuid, user_bnodeid);

			if (blank_nodes != null) {
				var iface = manager.get_db_interface ();
				while (Data.query_resource_id (manager, iface, uri) > 0) {
					// uri collision, generate new UUID
					uchar[] new_base_uuid = new uchar[16];
					uuid_generate (new_base_uuid);
					uri = get_uuid_for_name (new_base_uuid, user_bnodeid);
				}

				blank_nodes.insert (user_bnodeid, uri);
			}

			return uri;
		}
	}

	internal bool next () throws Sparql.Error {
		index = (index + 1) % BUFFER_SIZE;
		size--;
		if (size <= 0) {
			SourceLocation begin, end;
			SparqlTokenType type = scanner.read_token (out begin, out end);
			tokens[index].type = type;
			tokens[index].begin = begin;
			tokens[index].end = end;
			size = 1;
		}
		return (tokens[index].type != SparqlTokenType.EOF);
	}

	internal SparqlTokenType current () {
		return tokens[index].type;
	}

	internal SparqlTokenType last () {
		int last_index = (index + BUFFER_SIZE - 1) % BUFFER_SIZE;
		return tokens[last_index].type;
	}

	internal bool accept (SparqlTokenType type) throws Sparql.Error {
		if (current () == type) {
			next ();
			return true;
		}
		return false;
	}

	internal Sparql.Error get_error (string msg) {
		return new Sparql.Error.PARSE ("%d.%d: syntax error, %s".printf (tokens[index].begin.line, tokens[index].begin.column, msg));
	}

	internal Sparql.Error get_internal_error (string msg) {
		return new Sparql.Error.INTERNAL ("%d.%d: %s".printf (tokens[index].begin.line, tokens[index].begin.column, msg));
	}

	internal bool expect (SparqlTokenType type) throws Sparql.Error {
		if (accept (type)) {
			return true;
		}

		throw get_error ("expected %s".printf (type.to_string ()));
	}

	internal SourceLocation get_location () {
		return tokens[index].begin;
	}

	internal void set_location (SourceLocation location) {
		scanner.seek (location);
		size = 0;
		index = 0;
		try {
			next ();
		} catch (Sparql.Error e) {
			// this should never happen as this is the second time we scan this token
			critical ("internal error: next in set_location failed");
		}
	}

	internal string get_last_string (int strip = 0) {
		int last_index = (index + BUFFER_SIZE - 1) % BUFFER_SIZE;
		return ((string) (tokens[last_index].begin.pos + strip)).substring (0, (int) (tokens[last_index].end.pos - tokens[last_index].begin.pos - 2 * strip));
	}

	void parse_prologue () throws Sparql.Error {
		if (accept (SparqlTokenType.BASE)) {
			expect (SparqlTokenType.IRI_REF);
		}
		while (accept (SparqlTokenType.PREFIX)) {
			string ns = "";
			if (accept (SparqlTokenType.PN_PREFIX)) {
				ns = get_last_string ();
			}
			expect (SparqlTokenType.COLON);
			expect (SparqlTokenType.IRI_REF);
			string uri = get_last_string (1);
			prefix_map.insert (ns, uri);
		}
	}

	void prepare_execute () throws DBInterfaceError, Sparql.Error, DateError {
		assert (!update_extensions);

		scanner = new SparqlScanner ((char*) query_string, (long) query_string.length);
		next ();

		// declare fn prefix for XPath functions
		prefix_map.insert ("fn", FN_NS);
		var ontologies = manager.get_ontologies ();

		foreach (Namespace ns in ontologies.get_namespaces ()) {
			if (ns.prefix == null) {
				critical ("Namespace does not specify a prefix: %s", ns.uri);
				continue;
			}
			prefix_map.insert (ns.prefix, ns.uri);
		}

		parse_prologue ();
	}


	public DBCursor? execute_cursor () throws DBInterfaceError, Sparql.Error, DateError {

		prepare_execute ();

		switch (current ()) {
		case SparqlTokenType.SELECT:
			return execute_select_cursor ();
		case SparqlTokenType.CONSTRUCT:
			throw get_internal_error ("CONSTRUCT is not supported");
		case SparqlTokenType.DESCRIBE:
			throw get_internal_error ("DESCRIBE is not supported");
		case SparqlTokenType.ASK:
			return execute_ask_cursor ();
		case SparqlTokenType.INSERT:
		case SparqlTokenType.DELETE:
		case SparqlTokenType.DROP:
			throw get_error ("INSERT and DELETE are not supported in query mode");
		default:
			throw get_error ("expected SELECT or ASK");
		}
	}

	public Variant? execute_update (bool blank) throws GLib.Error {
		Variant result = null;
		assert (update_extensions);

		scanner = new SparqlScanner ((char*) query_string, (long) query_string.length);
		next ();

		// declare fn prefix for XPath functions
		prefix_map.insert ("fn", FN_NS);
		var ontologies = manager.get_ontologies ();

		foreach (Namespace ns in ontologies.get_namespaces ()) {
			if (ns.prefix == null) {
				critical ("Namespace does not specify a prefix: %s", ns.uri);
				continue;
			}
			prefix_map.insert (ns.prefix, ns.uri);
		}

		parse_prologue ();

		// SPARQL update supports multiple operations in a single query
		VariantBuilder? ublank_nodes = null;

		if (blank) {
			ublank_nodes = new VariantBuilder ((VariantType) "aaa{ss}");
		}

		while (current () != SparqlTokenType.EOF) {
			switch (current ()) {
			case SparqlTokenType.WITH:
			case SparqlTokenType.INSERT:
			case SparqlTokenType.DELETE:
				if (blank) {
					ublank_nodes.open ((VariantType) "aa{ss}");
					execute_insert_delete (ublank_nodes);
					ublank_nodes.close ();
				} else {
					execute_insert_delete (null);
				}
				break;
			case SparqlTokenType.DROP:
				throw get_internal_error ("DROP GRAPH is not supported");
			case SparqlTokenType.SELECT:
			case SparqlTokenType.CONSTRUCT:
			case SparqlTokenType.DESCRIBE:
			case SparqlTokenType.ASK:
				throw get_error ("SELECT, CONSTRUCT, DESCRIBE, and ASK are not supported in update mode");
			default:
				throw get_error ("expected INSERT or DELETE");
			}

			// semicolon is used to separate multiple operations in the current SPARQL Update draft
			// keep it optional for now to reatin backward compatibility
			accept (SparqlTokenType.SEMICOLON);
		}

		if (blank) {
			result = ublank_nodes.end ();
		}

		return result;
	}

	DBStatement prepare_for_exec (DBInterface iface, string sql) throws DBInterfaceError, Sparql.Error, DateError {
		var stmt = iface.create_statement (no_cache ? DBStatementCacheType.NONE : DBStatementCacheType.SELECT, "%s", sql);

		// set literals specified in query
		int i = 0;
		foreach (LiteralBinding binding in bindings) {
			if (binding.data_type == PropertyType.BOOLEAN) {
				if (binding.literal == "true" || binding.literal == "1") {
					stmt.bind_int (i, 1);
				} else if (binding.literal == "false" || binding.literal == "0") {
					stmt.bind_int (i, 0);
				} else {
					throw new Sparql.Error.TYPE ("`%s' is not a valid boolean".printf (binding.literal));
				}
			} else if (binding.data_type == PropertyType.DATE) {
				stmt.bind_int (i, (int) string_to_date (binding.literal + "T00:00:00Z", null));
			} else if (binding.data_type == PropertyType.DATETIME) {
				stmt.bind_double (i, string_to_date (binding.literal, null));
			} else if (binding.data_type == PropertyType.INTEGER) {
				stmt.bind_int (i, int.parse (binding.literal));
			} else {
				stmt.bind_text (i, binding.literal);
			}
			i++;
		}

		return stmt;
	}

	DBCursor? exec_sql_cursor (DBInterface iface, string sql, PropertyType[]? types, string[]? variable_names) throws DBInterfaceError, Sparql.Error, DateError {
		var stmt = prepare_for_exec (iface, sql);

		return stmt.start_sparql_cursor (types, variable_names);
	}

	string get_select_query (out SelectContext context) throws DBInterfaceError, Sparql.Error, DateError {
		// SELECT query

		// build SQL
		var sql = new StringBuilder ();
		context = pattern.translate_select (sql);

		expect (SparqlTokenType.EOF);

		return sql.str;
	}

	DBCursor? execute_select_cursor () throws DBInterfaceError, Sparql.Error, DateError {
		SelectContext context;
		string sql = get_select_query (out context);
		var iface = manager.get_db_interface ();

		return exec_sql_cursor (iface, sql, context.types, context.variable_names);
	}

	string get_ask_query () throws DBInterfaceError, Sparql.Error, DateError {
		// ASK query

		var pattern_sql = new StringBuilder ();

		// build SQL
		var sql = new StringBuilder ();
		sql.append ("SELECT CASE EXISTS ( ");

		expect (SparqlTokenType.ASK);

		accept (SparqlTokenType.WHERE);

		context = pattern.translate_group_graph_pattern (pattern_sql);

		// select from results of WHERE clause
		sql.append (pattern_sql.str);
		sql.append (" ) WHEN 1 THEN 'true' WHEN 0 THEN 'false' ELSE NULL END");

		if (accept (SparqlTokenType.GROUP) || accept (SparqlTokenType.ORDER) ||
		    accept (SparqlTokenType.OFFSET) || accept (SparqlTokenType.LIMIT)) {
			throw get_error ("invalid use of %s in ASK".printf (last().to_string()));
		}

		expect (SparqlTokenType.EOF);

		context = context.parent_context;

		return sql.str;
	}

	DBCursor? execute_ask_cursor () throws DBInterfaceError, Sparql.Error, DateError {
		var iface = manager.get_db_interface ();
		return exec_sql_cursor (iface, get_ask_query (), new PropertyType[] { PropertyType.BOOLEAN }, new string[] { "result" });
	}

	private void parse_from_or_into_param () throws Sparql.Error {
		if (accept (SparqlTokenType.IRI_REF)) {
			current_graph = get_last_string (1);
		} else if (accept (SparqlTokenType.PN_PREFIX)) {
			string ns = get_last_string ();
			expect (SparqlTokenType.COLON);
			current_graph = resolve_prefixed_name (ns, get_last_string ().substring (1));
		} else {
			expect (SparqlTokenType.COLON);
			current_graph = resolve_prefixed_name ("", get_last_string ().substring (1));
		}
	}

	void execute_insert_delete (VariantBuilder? update_blank_nodes) throws GLib.Error {
		bool blank = true;

		// DELETE and/or INSERT

		if (accept (SparqlTokenType.WITH)) {
			parse_from_or_into_param ();
		} else {
			current_graph = null;
		}

		SourceLocation? delete_location = null;
		SourceLocation? insert_location = null;
		bool insert_is_update = false;
		bool delete_where = false;
		bool data = false;

		var data_update = manager.get_data ();

		// Sparql 1.1 defines deletes/inserts as a single
		// operation with the syntax:
		//   [DELETE {...}] [INSERT {...}] WHERE {...}

		if (accept (SparqlTokenType.DELETE)) {
			blank = false;

			// SILENT => ignore (non-syntax) errors
			silent = accept (SparqlTokenType.SILENT);

			if (current_graph == null && accept (SparqlTokenType.FROM)) {
				parse_from_or_into_param ();
			}

			if (current_graph == null && accept (SparqlTokenType.DATA)) {
				// INSERT/DELETE DATA are simpler variants
				// that don't support variables
				data = true;
			} else if (accept (SparqlTokenType.WHERE)) {
				// DELETE WHERE is a short form where the pattern
				// is also used as the template for deletion
				delete_where = true;
			}

			delete_location = get_location ();

			if (!data && !delete_where) {
				skip_braces ();
			}
		}

		if (!data && !delete_where && accept (SparqlTokenType.INSERT)) {
			if (accept (SparqlTokenType.OR)) {
				expect (SparqlTokenType.REPLACE);
				insert_is_update = true;
			}

			if (!insert_is_update) {
				// SILENT => ignore (non-syntax) errors
				silent = accept (SparqlTokenType.SILENT);
			}

			if (current_graph == null && accept (SparqlTokenType.INTO)) {
				parse_from_or_into_param ();
			}

			if (current_graph == null && accept (SparqlTokenType.DATA)) {
				// INSERT/DELETE DATA are simpler variants
				// that don't support variables
				data = true;
			}

			if (current () != SparqlTokenType.OPEN_BRACE) {
				throw get_error ("Expected '{' beginning a quad data/pattern block");
			}

			insert_location = get_location ();

			if (!data) {
				skip_braces ();
			}
		}

		var pattern_sql = new StringBuilder ();

		var sql = new StringBuilder ();

		if (!data) {
			if (delete_where || accept (SparqlTokenType.WHERE)) {
				pattern.current_graph = current_graph;
				context = pattern.translate_group_graph_pattern (pattern_sql);
				pattern.current_graph = null;
			} else {
				context = new Context (this);

				pattern_sql.append ("SELECT 1");
			}
		} else {
			// WHERE pattern not supported for INSERT/DELETE DATA,
			// nor unbound values in the quad data.
			if (quad_data_unbound_var_count () > 0) {
				throw get_error ("INSERT/DELETE DATA do not allow unbound values");
			}

			context = new Context (this);

			pattern_sql.append ("SELECT 1");
		}

		var after_where = get_location ();

		var solution = new Solution ();

		// build SQL
		sql.append ("SELECT ");
		int var_idx = 0;
		foreach (var variable in context.var_set.get_keys ()) {
			if (var_idx > 0) {
				sql.append (", ");
			}

			if (variable.binding == null) {
				throw get_error ("use of undefined variable `%s'".printf (variable.name));
			}
			Expression.append_expression_as_string (sql, variable.sql_expression, variable.binding.data_type);

			solution.hash.insert (variable.name, var_idx++);
		}

		if (var_idx == 0) {
			sql.append ("1");
		}

		// select from results of WHERE clause
		sql.append (" FROM (");
		sql.append (pattern_sql.str);
		sql.append (")");

		var iface = manager.get_writable_db_interface ();
		var cursor = exec_sql_cursor (iface, sql.str, null, null);

		int n_solutions = 0;
		while (cursor.next ()) {
			// get values of all variables to be bound
			for (var_idx = 0; var_idx < solution.hash.size (); var_idx++) {
				solution.values.add (cursor.get_string (var_idx));
			}
			n_solutions++;
		}

		cursor = null;

		// Iterate over all solutions twice
		// First handle deletes
		if (delete_location != null) {
			for (int i = 0; i < n_solutions; i++) {
				solution.solution_index = i;
				set_location (delete_location);
				parse_construct_triples_block (solution, UpdateType.DELETE);
				data_update.update_buffer_might_flush ();
			}

			// Force flush on delete/insert operations,
			// so the elements are already removed at
			// the time of insertion.
			if (insert_location != null)
				data_update.update_buffer_flush ();
		}

		// Then handle inserts/updates
		if (insert_location != null) {
			for (int i = 0; i < n_solutions; i++) {
				uuid_generate (base_uuid);
				blank_nodes = new HashTable<string,string>.full (str_hash, str_equal, g_free, g_free);
				solution.solution_index = i;

				set_location (insert_location);
				parse_construct_triples_block (solution,
							       insert_is_update ?
							       UpdateType.UPDATE :
							       UpdateType.INSERT);

				if (blank && update_blank_nodes != null) {
					update_blank_nodes.add_value (blank_nodes);
				}

				data_update.update_buffer_might_flush ();
			}
		}

		solution = null;

		if (!data) {
			// reset location to the end of the update
			set_location (after_where);
		}

		// ensure possible WHERE clause in next part gets the correct results
		data_update.update_buffer_flush ();
		bindings = null;

		context = context.parent_context;
	}

	internal string resolve_prefixed_name (string prefix, string local_name) throws Sparql.Error {
		string ns = prefix_map.lookup (prefix);
		if (ns == null) {
			throw get_error ("use of undefined prefix `%s'".printf (prefix));
		}
		return ns + local_name;
	}

	int quad_data_unbound_var_count () throws Sparql.Error {
		SourceLocation current_pos = get_location ();
		int n_braces = 1;
		int n_unbound = 0;

		expect (SparqlTokenType.OPEN_BRACE);
		while (n_braces > 0) {
			if (accept (SparqlTokenType.OPEN_BRACE)) {
				n_braces++;
			} else if (accept (SparqlTokenType.CLOSE_BRACE)) {
				n_braces--;
			} else if (current () == SparqlTokenType.EOF) {
				throw get_error ("unexpected end of query, expected }");
			} else {
				if (current () == SparqlTokenType.VAR)
					n_unbound++;
				// ignore everything else
				next ();
			}
		}

		set_location (current_pos);
		return n_unbound;
	}

	void skip_braces () throws Sparql.Error {
		expect (SparqlTokenType.OPEN_BRACE);
		int n_braces = 1;
		while (n_braces > 0) {
			if (accept (SparqlTokenType.OPEN_BRACE)) {
				n_braces++;
			} else if (accept (SparqlTokenType.CLOSE_BRACE)) {
				n_braces--;
			} else if (current () == SparqlTokenType.EOF) {
				throw get_error ("unexpected end of query, expected }");
			} else {
				// ignore everything else
				next ();
			}
		}
	}

	void parse_construct_triples_block (Solution var_value_map, UpdateType type) throws Sparql.Error, DateError {
		expect (SparqlTokenType.OPEN_BRACE);

		while (current () != SparqlTokenType.CLOSE_BRACE) {
			bool is_null = false;

			if (accept (SparqlTokenType.GRAPH)) {
				var old_graph = current_graph;
				current_graph = parse_construct_var_or_term (var_value_map, type, out is_null);

				if (is_null) {
					throw get_error ("'null' not supported for graph");
				}

				expect (SparqlTokenType.OPEN_BRACE);

				while (current () != SparqlTokenType.CLOSE_BRACE) {
					current_subject = parse_construct_var_or_term (var_value_map, type, out is_null);

					if (is_null) {
						throw get_error ("'null' not supported for subject");
					}

					parse_construct_property_list_not_empty (var_value_map, type);
					if (!accept (SparqlTokenType.DOT)) {
						// no triples following
						break;
					}
				}

				expect (SparqlTokenType.CLOSE_BRACE);

				current_graph = old_graph;

				accept (SparqlTokenType.DOT);
			} else {
				current_subject = parse_construct_var_or_term (var_value_map, type, out is_null);

				if (is_null) {
					throw get_error ("'null' not supported for subject");
				}

				parse_construct_property_list_not_empty (var_value_map, type);
				if (!accept (SparqlTokenType.DOT) && current () != SparqlTokenType.GRAPH) {
					// neither GRAPH nor triples following
					break;
				}
			}
		}

		expect (SparqlTokenType.CLOSE_BRACE);
	}

	bool anon_blank_node_open = false;

	string? parse_construct_var_or_term (Solution var_value_map, UpdateType type, out bool is_null) throws Sparql.Error, DateError {
		string result = "";
		is_null = false;
		if (current () == SparqlTokenType.VAR) {
			next ();
			result = var_value_map.lookup (get_last_string ().substring (1));
		} else if (current () == SparqlTokenType.IRI_REF) {
			next ();
			result = get_last_string (1);
		} else if (current () == SparqlTokenType.PN_PREFIX) {
			// prefixed name with namespace foo:bar
			next ();
			string ns = get_last_string ();
			expect (SparqlTokenType.COLON);
			result = resolve_prefixed_name (ns, get_last_string ().substring (1));
		} else if (current () == SparqlTokenType.COLON) {
			// prefixed name without namespace :bar
			next ();
			result = resolve_prefixed_name ("", get_last_string ().substring (1));
		} else if (accept (SparqlTokenType.BLANK_NODE)) {
			// _:foo
			expect (SparqlTokenType.COLON);
			result = generate_bnodeid (get_last_string ().substring (1));
		} else if (current () == SparqlTokenType.MINUS) {
			next ();
			if (current () == SparqlTokenType.INTEGER ||
			    current () == SparqlTokenType.DECIMAL ||
			    current () == SparqlTokenType.DOUBLE) {
				next ();
				result = "-" + get_last_string ();
			} else {
				throw get_error ("expected variable or term");
			}
		} else if (current () == SparqlTokenType.INTEGER) {
			next ();
			result = get_last_string ();
		} else if (current () == SparqlTokenType.NULL) {
			next ();
			result = "null";
			is_null = true;
		} else if (current () == SparqlTokenType.DECIMAL) {
			next ();
			result = get_last_string ();
		} else if (current () == SparqlTokenType.DOUBLE) {
			next ();
			result = get_last_string ();
		} else if (current () == SparqlTokenType.TRUE) {
			next ();
			result = "true";
		} else if (current () == SparqlTokenType.FALSE) {
			next ();
			result = "false";
		} else if (current () == SparqlTokenType.STRING_LITERAL1) {
			result = expression.parse_string_literal ();
		} else if (current () == SparqlTokenType.STRING_LITERAL2) {
			result = expression.parse_string_literal ();
		} else if (current () == SparqlTokenType.STRING_LITERAL_LONG1) {
			result = expression.parse_string_literal ();
		} else if (current () == SparqlTokenType.STRING_LITERAL_LONG2) {
			result = expression.parse_string_literal ();
		} else if (current () == SparqlTokenType.OPEN_BRACKET) {

			if (anon_blank_node_open) {
				throw get_error ("no support for nested anonymous blank nodes");
			}

			anon_blank_node_open = true;
			next ();

			result = generate_bnodeid (null);

			string old_subject = current_subject;
			bool old_subject_is_var = current_subject_is_var;

			current_subject = result;
			parse_construct_property_list_not_empty (var_value_map, type);
			expect (SparqlTokenType.CLOSE_BRACKET);
			anon_blank_node_open = false;

			current_subject = old_subject;
			current_subject_is_var = old_subject_is_var;
		} else {
			throw get_error ("expected variable or term");
		}
		return result;
	}

	void parse_construct_property_list_not_empty (Solution var_value_map, UpdateType type) throws Sparql.Error, DateError {
		while (true) {
			var old_predicate = current_predicate;

			current_predicate = null;
			if (current () == SparqlTokenType.VAR) {
				current_predicate_is_var = true;
				next ();
				current_predicate = var_value_map.lookup (get_last_string ().substring (1));
			} else if (current () == SparqlTokenType.IRI_REF) {
				next ();
				current_predicate = get_last_string (1);
			} else if (current () == SparqlTokenType.PN_PREFIX) {
				next ();
				string ns = get_last_string ();
				expect (SparqlTokenType.COLON);
				current_predicate = resolve_prefixed_name (ns, get_last_string ().substring (1));
			} else if (current () == SparqlTokenType.COLON) {
				next ();
				current_predicate = resolve_prefixed_name ("", get_last_string ().substring (1));
			} else if (current () == SparqlTokenType.A) {
				next ();
				current_predicate = "http://www.w3.org/1999/02/22-rdf-syntax-ns#type";
			} else {
				throw get_error ("expected non-empty property list");
			}
			parse_construct_object_list (var_value_map, type);

			current_predicate = old_predicate;

			if (accept (SparqlTokenType.SEMICOLON)) {
				continue;
			}
			break;
		}
	}

	void parse_construct_object_list (Solution var_value_map, UpdateType type) throws Sparql.Error, DateError {
		while (true) {
			parse_construct_object (var_value_map, type);
			if (accept (SparqlTokenType.COMMA)) {
				continue;
			}
			break;
		}
	}

	void parse_construct_object (Solution var_value_map, UpdateType type) throws Sparql.Error, DateError {
		bool is_null = false;
		string object = parse_construct_var_or_term (var_value_map, type, out is_null);
		var data = manager.get_data ();
		if (current_subject == null || current_predicate == null || object == null) {
			// the SPARQL specification says that triples containing unbound variables
			// should be excluded from the output RDF graph of CONSTRUCT
			return;
		}
		try {
			if (type == UpdateType.UPDATE) {
				// update triple in database
				data.update_statement (current_graph, current_subject, current_predicate, is_null ? null : object);
			} else if (type == UpdateType.DELETE) {
				// delete triple from database
				if (is_null) {
					throw get_error ("'null' not supported in this mode");
				}
				data.delete_statement (current_graph, current_subject, current_predicate, object);
			} else if (type == UpdateType.INSERT) {
				// insert triple into database
				if (is_null) {
					throw get_error ("'null' not supported in this mode");
				}
				data.insert_statement (current_graph, current_subject, current_predicate, object);
			}
		} catch (Sparql.Error e) {
			if (!silent) {
				throw e;
			}
		} catch (DateError e) {
			if (!silent) {
				throw new Sparql.Error.TYPE (e.message);
			}
		}
	}

	[CCode (cname = "uuid_generate")]
	public extern static void uuid_generate ([CCode (array_length = false)] uchar[] uuid);
}