Merge tag 'debian/0.34.2-1' into debian/bullseye-backports

notmuch release 0.34.2-1 for unstable (sid) [dgit]

[dgit distro=debian no-split --quilt=linear]

14 files changed, 1023 insertions, 106 deletions

diff --git a/lib/Makefile.local b/lib/Makefile.local
index e2d4b91d..1378a74b 100644
--- a/lib/Makefile.local
+++ b/lib/Makefile.local
@@ -63,7 +63,8 @@ libnotmuch_cxx_srcs =		\
 	$(dir)/features.cc	\
 	$(dir)/prefix.cc	\
 	$(dir)/open.cc		\
-	$(dir)/init.cc
+	$(dir)/init.cc		\
+	$(dir)/parse-sexp.cc
 
 libnotmuch_modules := $(libnotmuch_c_srcs:.c=.o) $(libnotmuch_cxx_srcs:.cc=.o)
 
diff --git a/lib/built-with.c b/lib/built-with.c
index 0c70010b..89958e12 100644
--- a/lib/built-with.c
+++ b/lib/built-with.c
@@ -32,6 +32,8 @@ notmuch_built_with (const char *name)
 	return HAVE_XAPIAN_DB_RETRY_LOCK;
     } else if (STRNCMP_LITERAL (name, "session_key") == 0) {
 	return true;
+    } else if (STRNCMP_LITERAL (name, "sexpr_query") == 0) {
+	return HAVE_SFSEXP;
     } else {
 	return false;
     }
diff --git a/lib/config.cc b/lib/config.cc
index 8775b00a..e502858d 100644
--- a/lib/config.cc
+++ b/lib/config.cc
@@ -259,7 +259,15 @@ _notmuch_config_load_from_database (notmuch_database_t *notmuch)
 
     for (; notmuch_config_list_valid (list); notmuch_config_list_move_to_next (list)) {
 	const char *key = notmuch_config_list_key (list);
-	char *normalized_val = _expand_path (list, key, notmuch_config_list_value (list));
+	char *normalized_val = NULL;
+
+	/* If we opened from a given path, do not overwrite it */
+	if (strcmp (key, "database.path") == 0 &&
+	    (notmuch->params & NOTMUCH_PARAM_DATABASE) &&
+	    notmuch->xapian_db)
+	    continue;
+
+	normalized_val = _expand_path (list, key, notmuch_config_list_value (list));
 	_notmuch_string_map_append (notmuch->config, key, normalized_val);
 	talloc_free (normalized_val);
     }
@@ -432,6 +440,13 @@ _notmuch_config_load_from_file (notmuch_database_t *notmuch,
 		status = NOTMUCH_STATUS_FILE_ERROR;
 		goto DONE;
 	    }
+
+	    /* If we opened from a given path, do not overwrite it */
+	    if (strcmp (absolute_key, "database.path") == 0 &&
+		(notmuch->params & NOTMUCH_PARAM_DATABASE) &&
+		notmuch->xapian_db)
+		continue;
+
 	    normalized_val = _expand_path (notmuch, absolute_key, val);
 	    _notmuch_string_map_set (notmuch->config, absolute_key, normalized_val);
 	    g_free (val);
diff --git a/lib/database-private.h b/lib/database-private.h
index 9706c17e..8dd77281 100644
--- a/lib/database-private.h
+++ b/lib/database-private.h
@@ -40,6 +40,10 @@
 
 #include <xapian.h>
 
+#if HAVE_SFSEXP
+#include <sexp.h>
+#endif
+
 /* Bit masks for _notmuch_database::features.  Features are named,
  * independent aspects of the database schema.
  *
@@ -186,6 +190,39 @@ operator& (notmuch_field_flag_t a, notmuch_field_flag_t b)
 				    Xapian::QueryParser::FLAG_WILDCARD | \
 				    Xapian::QueryParser::FLAG_PURE_NOT)
 
+/*
+ * Which parameters were explicit when the database was opened */
+typedef enum {
+    NOTMUCH_PARAM_NONE		= 0,
+    NOTMUCH_PARAM_DATABASE	= 1 << 0,
+    NOTMUCH_PARAM_CONFIG	= 1 << 1,
+    NOTMUCH_PARAM_PROFILE	= 1 << 2,
+} notmuch_open_param_t;
+
+/*
+ * define bitwise operators to hide casts */
+
+inline notmuch_open_param_t
+operator| (notmuch_open_param_t a, notmuch_open_param_t b)
+{
+    return static_cast<notmuch_open_param_t>(
+	static_cast<unsigned>(a) | static_cast<unsigned>(b));
+}
+
+inline notmuch_open_param_t&
+operator|= (notmuch_open_param_t &a, notmuch_open_param_t b)
+{
+    a = a | b;
+    return a;
+}
+
+inline notmuch_open_param_t
+operator& (notmuch_open_param_t a, notmuch_open_param_t b)
+{
+    return static_cast<notmuch_open_param_t>(
+	static_cast<unsigned>(a) & static_cast<unsigned>(b));
+}
+
 struct _notmuch_database {
     bool exception_reported;
 
@@ -232,6 +269,7 @@ struct _notmuch_database {
      */
     unsigned long view;
     Xapian::QueryParser *query_parser;
+    Xapian::Stem *stemmer;
     Xapian::TermGenerator *term_gen;
     Xapian::RangeProcessor *value_range_processor;
     Xapian::RangeProcessor *date_range_processor;
@@ -244,6 +282,9 @@ struct _notmuch_database {
 
     /* Cached and possibly overridden configuration */
     notmuch_string_map_t *config;
+
+    /* Track what parameters were specified when opening */
+    notmuch_open_param_t params;
 };
 
 /* Prior to database version 3, features were implied by the database
@@ -300,4 +341,38 @@ _notmuch_database_setup_standard_query_fields (notmuch_database_t *notmuch);
 notmuch_status_t
 _notmuch_database_setup_user_query_fields (notmuch_database_t *notmuch);
 
+#if __cplusplus
+/* query.cc */
+notmuch_status_t
+_notmuch_query_string_to_xapian_query (notmuch_database_t *notmuch,
+				       std::string query_string,
+				       Xapian::Query &output,
+				       std::string &msg);
+/* parse-sexp.cc */
+notmuch_status_t
+_notmuch_sexp_string_to_xapian_query (notmuch_database_t *notmuch, const char *querystr,
+				      Xapian::Query &output);
+
+notmuch_status_t
+_notmuch_query_expand (notmuch_database_t *notmuch, const char *field, Xapian::Query subquery,
+		       Xapian::Query &output, std::string &msg);
+
+/* regexp-fields.cc */
+notmuch_status_t
+_notmuch_regexp_to_query (notmuch_database_t *notmuch, Xapian::valueno slot, std::string field,
+			  std::string regexp_str,
+			  Xapian::Query &output, std::string &msg);
+
+/* thread-fp.cc */
+notmuch_status_t
+_notmuch_query_name_to_query (notmuch_database_t *notmuch, const std::string name,
+			      Xapian::Query &output);
+
+#if HAVE_SFSEXP
+/* parse-sexp.cc */
+notmuch_status_t
+_notmuch_sexp_string_to_xapian_query (notmuch_database_t *notmuch, const char *querystr,
+				      Xapian::Query &output);
+#endif
+#endif
 #endif
diff --git a/lib/database.cc b/lib/database.cc
index 31794900..7eb0de79 100644
--- a/lib/database.cc
+++ b/lib/database.cc
@@ -309,6 +309,8 @@ notmuch_status_to_string (notmuch_status_t status)
 	return "No database found";
     case NOTMUCH_STATUS_DATABASE_EXISTS:
 	return "Database exists, not recreated";
+    case NOTMUCH_STATUS_BAD_QUERY_SYNTAX:
+	return "Syntax error in query";
     default:
     case NOTMUCH_STATUS_LAST_STATUS:
 	return "Unknown error status value";
diff --git a/lib/message-file.c b/lib/message-file.c
index 647ccf3a..68f646a4 100644
--- a/lib/message-file.c
+++ b/lib/message-file.c
@@ -291,11 +291,16 @@ _notmuch_message_file_get_header (notmuch_message_file_t *message,
     if (value)
 	return value;
 
-    if (strcasecmp (header, "received") == 0) {
+    if (strcasecmp (header, "received") == 0 ||
+	strcasecmp (header, "delivered-to") == 0) {
 	/*
-	 * The Received: header is special. We concatenate all
-	 * instances of the header as we use this when analyzing the
-	 * path the mail has taken from sender to recipient.
+	 * The Received: header is special. We concatenate all instances of the
+	 * header as we use this when analyzing the path the mail has taken
+	 * from sender to recipient.
+	 *
+	 * Similarly, multiple instances of Delivered-To may be present. We
+	 * concatenate them so the one with highest priority may be picked (eg.
+	 * primary_email before other_email).
 	 */
 	decoded = _notmuch_message_file_get_combined_header (message, header);
     } else {
diff --git a/lib/notmuch.h b/lib/notmuch.h
index ef11ed1b..5c5a024e 100644
--- a/lib/notmuch.h
+++ b/lib/notmuch.h
@@ -58,7 +58,7 @@ NOTMUCH_BEGIN_DECLS
  * version in Makefile.local.
  */
 #define LIBNOTMUCH_MAJOR_VERSION        5
-#define LIBNOTMUCH_MINOR_VERSION        4
+#define LIBNOTMUCH_MINOR_VERSION        5
 #define LIBNOTMUCH_MICRO_VERSION        0
 
 
@@ -221,6 +221,10 @@ typedef enum _notmuch_status {
      */
     NOTMUCH_STATUS_DATABASE_EXISTS,
     /**
+     * Syntax error in query
+     */
+    NOTMUCH_STATUS_BAD_QUERY_SYNTAX,
+    /**
      * Not an actual status value. Just a way to find out how many
      * valid status values there are.
      */
@@ -429,6 +433,8 @@ notmuch_database_open_verbose (const char *path,
  * @retval NOTMUCH_STATUS_NULL_POINTER: The given \a database
  * argument is NULL.
  *
+ * @retval NOTMUCH_STATUS_NO_CONFIG: No config file was found. Fatal.
+ *
  * @retval NOTMUCH_STATUS_OUT_OF_MEMORY: Out of memory.
  *
  * @retval NOTMUCH_STATUS_FILE_ERROR: An error occurred trying to open the
@@ -454,6 +460,9 @@ notmuch_database_open_with_config (const char *database_path,
  *
  * For description of arguments, @see notmuch_database_open_with_config
  *
+ * For errors other then NO_DATABASE and NO_CONFIG, *database is set to
+ * NULL.
+ *
  * @retval NOTMUCH_STATUS_SUCCESS: Successfully loaded configuration.
  *
  * @retval NOTMUCH_STATUS_NO_CONFIG: No config file was loaded. Not fatal.
@@ -485,6 +494,9 @@ notmuch_database_load_config (const char *database_path,
  *
  * For description of arguments, @see notmuch_database_open_with_config
  *
+ * In case of any failure, this function returns an error status and
+ * sets *database to NULL.
+ *
  * @retval NOTMUCH_STATUS_SUCCESS: Successfully created the database.
  *
  * @retval NOTMUCH_STATUS_DATABASE_EXISTS: Database already exists, not created
@@ -961,6 +973,16 @@ notmuch_query_t *
 notmuch_query_create (notmuch_database_t *database,
 		      const char *query_string);
 
+typedef enum {
+    NOTMUCH_QUERY_SYNTAX_XAPIAN,
+    NOTMUCH_QUERY_SYNTAX_SEXP
+} notmuch_query_syntax_t;
+
+notmuch_status_t
+notmuch_query_create_with_syntax (notmuch_database_t *database,
+				  const char *query_string,
+				  notmuch_query_syntax_t syntax,
+				  notmuch_query_t **output);
 /**
  * Sort values for notmuch_query_set_sort.
  */
diff --git a/lib/open.cc b/lib/open.cc
index 280ffee3..a942383b 100644
--- a/lib/open.cc
+++ b/lib/open.cc
@@ -247,7 +247,7 @@ _choose_database_path (void *ctx,
 }
 
 static notmuch_database_t *
-_alloc_notmuch ()
+_alloc_notmuch (const char *database_path, const char *config_path, const char *profile)
 {
     notmuch_database_t *notmuch;
 
@@ -263,6 +263,15 @@ _alloc_notmuch ()
     notmuch->transaction_count = 0;
     notmuch->transaction_threshold = 0;
     notmuch->view = 1;
+
+    notmuch->params = NOTMUCH_PARAM_NONE;
+    if (database_path)
+	notmuch->params |= NOTMUCH_PARAM_DATABASE;
+    if (config_path)
+	notmuch->params |= NOTMUCH_PARAM_CONFIG;
+    if (profile)
+	notmuch->params |= NOTMUCH_PARAM_PROFILE;
+
     return notmuch;
 }
 
@@ -396,8 +405,6 @@ _finish_open (notmuch_database_t *notmuch,
 				     "       has a newer database format version (%u) than supported by this\n"
 				     "       version of notmuch (%u).\n",
 				     database_path, version, NOTMUCH_DATABASE_VERSION));
-	    notmuch_database_destroy (notmuch);
-	    notmuch = NULL;
 	    status = NOTMUCH_STATUS_FILE_ERROR;
 	    goto DONE;
 	}
@@ -414,8 +421,6 @@ _finish_open (notmuch_database_t *notmuch,
 				     "       requires features (%s)\n"
 				     "       not supported by this version of notmuch.\n",
 				     database_path, incompat_features));
-	    notmuch_database_destroy (notmuch);
-	    notmuch = NULL;
 	    status = NOTMUCH_STATUS_FILE_ERROR;
 	    goto DONE;
 	}
@@ -432,7 +437,8 @@ _finish_open (notmuch_database_t *notmuch,
 									      "lastmod:");
 	notmuch->query_parser->set_default_op (Xapian::Query::OP_AND);
 	notmuch->query_parser->set_database (*notmuch->xapian_db);
-	notmuch->query_parser->set_stemmer (Xapian::Stem ("english"));
+	notmuch->stemmer = new Xapian::Stem ("english");
+	notmuch->query_parser->set_stemmer (*notmuch->stemmer);
 	notmuch->query_parser->set_stemming_strategy (Xapian::QueryParser::STEM_SOME);
 	notmuch->query_parser->add_rangeprocessor (notmuch->value_range_processor);
 	notmuch->query_parser->add_rangeprocessor (notmuch->date_range_processor);
@@ -488,8 +494,6 @@ _finish_open (notmuch_database_t *notmuch,
     } catch (const Xapian::Error &error) {
 	IGNORE_RESULT (asprintf (&message, "A Xapian exception occurred opening database: %s\n",
 				 error.get_msg ().c_str ()));
-	notmuch_database_destroy (notmuch);
-	notmuch = NULL;
 	status = NOTMUCH_STATUS_XAPIAN_EXCEPTION;
     }
   DONE:
@@ -515,7 +519,7 @@ notmuch_database_open_with_config (const char *database_path,
 
     _notmuch_init ();
 
-    notmuch = _alloc_notmuch ();
+    notmuch = _alloc_notmuch (database_path, config_path, profile);
     if (! notmuch) {
 	status = NOTMUCH_STATUS_OUT_OF_MEMORY;
 	goto DONE;
@@ -558,10 +562,13 @@ notmuch_database_open_with_config (const char *database_path,
 	    free (message);
     }
 
+    if (status && notmuch) {
+	notmuch_database_destroy (notmuch);
+	notmuch = NULL;
+    }
+
     if (database)
 	*database = notmuch;
-    else
-	talloc_free (notmuch);
 
     if (notmuch)
 	notmuch->open = true;
@@ -612,7 +619,7 @@ notmuch_database_create_with_config (const char *database_path,
 
     _notmuch_init ();
 
-    notmuch = _alloc_notmuch ();
+    notmuch = _alloc_notmuch (database_path, config_path, profile);
     if (! notmuch) {
 	status = NOTMUCH_STATUS_OUT_OF_MEMORY;
 	goto DONE;
@@ -716,10 +723,16 @@ notmuch_database_create_with_config (const char *database_path,
 	else
 	    free (message);
     }
+    if (status && notmuch) {
+	notmuch_database_destroy (notmuch);
+	notmuch = NULL;
+    }
+
     if (database)
 	*database = notmuch;
-    else
-	talloc_free (notmuch);
+
+    if (notmuch)
+	notmuch->open = true;
     return status;
 }
 
@@ -808,7 +821,7 @@ notmuch_database_load_config (const char *database_path,
 
     _notmuch_init ();
 
-    notmuch = _alloc_notmuch ();
+    notmuch = _alloc_notmuch (database_path, config_path, profile);
     if (! notmuch) {
 	status = NOTMUCH_STATUS_OUT_OF_MEMORY;
 	goto DONE;
@@ -867,6 +880,13 @@ notmuch_database_load_config (const char *database_path,
     if (status_string)
 	*status_string = message;
 
+    if (status &&
+	status != NOTMUCH_STATUS_NO_DATABASE
+	&& status != NOTMUCH_STATUS_NO_CONFIG) {
+	notmuch_database_destroy (notmuch);
+	notmuch = NULL;
+    }
+
     if (database)
 	*database = notmuch;
 
diff --git a/lib/parse-sexp.cc b/lib/parse-sexp.cc
new file mode 100644
index 00000000..356c32ea
--- /dev/null
+++ b/lib/parse-sexp.cc
@@ -0,0 +1,587 @@
+#include "database-private.h"
+
+#if HAVE_SFSEXP
+#include "sexp.h"
+#include "unicode-util.h"
+
+/* _sexp is used for file scope symbols to avoid clashing with
+ * definitions from sexp.h */
+
+/* sexp_binding structs attach name to a sexp and a defining
+ * context. The latter allows lazy evaluation of parameters whose
+ * definition contains other parameters.  Lazy evaluation is needed
+ * because a primary goal of macros is to change the parent field for
+ * a sexp.
+ */
+
+typedef struct sexp_binding {
+    const char *name;
+    const sexp_t *sx;
+    const struct sexp_binding *context;
+    const struct sexp_binding *next;
+} _sexp_binding_t;
+
+typedef enum {
+    SEXP_FLAG_NONE	= 0,
+    SEXP_FLAG_FIELD	= 1 << 0,
+    SEXP_FLAG_BOOLEAN	= 1 << 1,
+    SEXP_FLAG_SINGLE	= 1 << 2,
+    SEXP_FLAG_WILDCARD	= 1 << 3,
+    SEXP_FLAG_REGEX	= 1 << 4,
+    SEXP_FLAG_DO_REGEX	= 1 << 5,
+    SEXP_FLAG_EXPAND	= 1 << 6,
+    SEXP_FLAG_DO_EXPAND = 1 << 7,
+    SEXP_FLAG_ORPHAN	= 1 << 8,
+} _sexp_flag_t;
+
+/*
+ * define bitwise operators to hide casts */
+
+inline _sexp_flag_t
+operator| (_sexp_flag_t a, _sexp_flag_t b)
+{
+    return static_cast<_sexp_flag_t>(
+	static_cast<unsigned>(a) | static_cast<unsigned>(b));
+}
+
+inline _sexp_flag_t
+operator& (_sexp_flag_t a, _sexp_flag_t b)
+{
+    return static_cast<_sexp_flag_t>(
+	static_cast<unsigned>(a) & static_cast<unsigned>(b));
+}
+
+typedef struct  {
+    const char *name;
+    Xapian::Query::op xapian_op;
+    Xapian::Query initial;
+    _sexp_flag_t flags;
+} _sexp_prefix_t;
+
+static _sexp_prefix_t prefixes[] =
+{
+    { "and",            Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_NONE },
+    { "attachment",     Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_WILDCARD | SEXP_FLAG_EXPAND },
+    { "body",           Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD },
+    { "from",           Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX | SEXP_FLAG_EXPAND },
+    { "folder",         Xapian::Query::OP_OR,           Xapian::Query::MatchNothing,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX | SEXP_FLAG_EXPAND },
+    { "id",             Xapian::Query::OP_OR,           Xapian::Query::MatchNothing,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX },
+    { "infix",          Xapian::Query::OP_INVALID,      Xapian::Query::MatchAll,
+      SEXP_FLAG_SINGLE | SEXP_FLAG_ORPHAN },
+    { "is",             Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX | SEXP_FLAG_EXPAND },
+    { "matching",       Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_DO_EXPAND },
+    { "mid",            Xapian::Query::OP_OR,           Xapian::Query::MatchNothing,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX },
+    { "mimetype",       Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_WILDCARD | SEXP_FLAG_EXPAND },
+    { "not",            Xapian::Query::OP_AND_NOT,      Xapian::Query::MatchAll,
+      SEXP_FLAG_NONE },
+    { "of",             Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_DO_EXPAND },
+    { "or",             Xapian::Query::OP_OR,           Xapian::Query::MatchNothing,
+      SEXP_FLAG_NONE },
+    { "path",           Xapian::Query::OP_OR,           Xapian::Query::MatchNothing,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX },
+    { "property",       Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX | SEXP_FLAG_EXPAND },
+    { "query",          Xapian::Query::OP_INVALID,      Xapian::Query::MatchNothing,
+      SEXP_FLAG_SINGLE | SEXP_FLAG_ORPHAN },
+    { "regex",          Xapian::Query::OP_INVALID,      Xapian::Query::MatchAll,
+      SEXP_FLAG_SINGLE | SEXP_FLAG_DO_REGEX },
+    { "rx",             Xapian::Query::OP_INVALID,      Xapian::Query::MatchAll,
+      SEXP_FLAG_SINGLE | SEXP_FLAG_DO_REGEX },
+    { "starts-with",    Xapian::Query::OP_WILDCARD,     Xapian::Query::MatchAll,
+      SEXP_FLAG_SINGLE },
+    { "subject",        Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX | SEXP_FLAG_EXPAND },
+    { "tag",            Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX | SEXP_FLAG_EXPAND },
+    { "thread",         Xapian::Query::OP_OR,           Xapian::Query::MatchNothing,
+      SEXP_FLAG_FIELD | SEXP_FLAG_BOOLEAN | SEXP_FLAG_WILDCARD | SEXP_FLAG_REGEX | SEXP_FLAG_EXPAND },
+    { "to",             Xapian::Query::OP_AND,          Xapian::Query::MatchAll,
+      SEXP_FLAG_FIELD | SEXP_FLAG_WILDCARD | SEXP_FLAG_EXPAND },
+    { }
+};
+
+static notmuch_status_t _sexp_to_xapian_query (notmuch_database_t *notmuch,
+					       const _sexp_prefix_t *parent,
+					       const _sexp_binding_t *env,
+					       const sexp_t *sx,
+					       Xapian::Query &output);
+
+static notmuch_status_t
+_sexp_combine_query (notmuch_database_t *notmuch,
+		     const _sexp_prefix_t *parent,
+		     const _sexp_binding_t *env,
+		     Xapian::Query::op operation,
+		     Xapian::Query left,
+		     const sexp_t *sx,
+		     Xapian::Query &output)
+{
+    Xapian::Query subquery;
+
+    notmuch_status_t status;
+
+    /* if we run out elements, return accumulator */
+
+    if (! sx) {
+	output = left;
+	return NOTMUCH_STATUS_SUCCESS;
+    }
+
+    status = _sexp_to_xapian_query (notmuch, parent, env, sx, subquery);
+    if (status)
+	return status;
+
+    return _sexp_combine_query (notmuch,
+				parent,
+				env,
+				operation,
+				Xapian::Query (operation, left, subquery),
+				sx->next, output);
+}
+
+static notmuch_status_t
+_sexp_parse_phrase (std::string term_prefix, const char *phrase, Xapian::Query &output)
+{
+    Xapian::Utf8Iterator p (phrase);
+    Xapian::Utf8Iterator end;
+    std::vector<std::string> terms;
+
+    while (p != end) {
+	Xapian::Utf8Iterator start;
+	while (p != end && ! Xapian::Unicode::is_wordchar (*p))
+	    p++;
+
+	if (p == end)
+	    break;
+
+	start = p;
+
+	while (p != end && Xapian::Unicode::is_wordchar (*p))
+	    p++;
+
+	if (p != start) {
+	    std::string word (start, p);
+	    word = Xapian::Unicode::tolower (word);
+	    terms.push_back (term_prefix + word);
+	}
+    }
+    output = Xapian::Query (Xapian::Query::OP_PHRASE, terms.begin (), terms.end ());
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
+static notmuch_status_t
+_sexp_parse_wildcard (notmuch_database_t *notmuch,
+		      const _sexp_prefix_t *parent,
+		      unused(const _sexp_binding_t *env),
+		      std::string match,
+		      Xapian::Query &output)
+{
+
+    std::string term_prefix = parent ? _notmuch_database_prefix (notmuch, parent->name) : "";
+
+    if (parent && ! (parent->flags & SEXP_FLAG_WILDCARD)) {
+	_notmuch_database_log (notmuch, "'%s' does not support wildcard queries\n", parent->name);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    output = Xapian::Query (Xapian::Query::OP_WILDCARD,
+			    term_prefix + Xapian::Unicode::tolower (match));
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
+static notmuch_status_t
+_sexp_parse_one_term (notmuch_database_t *notmuch, std::string term_prefix, const sexp_t *sx,
+		      Xapian::Query &output)
+{
+    Xapian::Stem stem = *(notmuch->stemmer);
+
+    if (sx->aty == SEXP_BASIC && unicode_word_utf8 (sx->val)) {
+	std::string term = Xapian::Unicode::tolower (sx->val);
+
+	output = Xapian::Query ("Z" + term_prefix + stem (term));
+	return NOTMUCH_STATUS_SUCCESS;
+    } else {
+	return _sexp_parse_phrase (term_prefix, sx->val, output);
+    }
+
+}
+
+notmuch_status_t
+_sexp_parse_regex (notmuch_database_t *notmuch,
+		   const _sexp_prefix_t *prefix, const _sexp_prefix_t *parent,
+		   unused(const _sexp_binding_t *env),
+		   std::string val, Xapian::Query &output)
+{
+    if (! parent) {
+	_notmuch_database_log (notmuch, "illegal '%s' outside field\n",
+			       prefix->name);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    if (! (parent->flags & SEXP_FLAG_REGEX)) {
+	_notmuch_database_log (notmuch, "'%s' not supported in field '%s'\n",
+			       prefix->name, parent->name);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    std::string msg; /* ignored */
+
+    return _notmuch_regexp_to_query (notmuch, Xapian::BAD_VALUENO, parent->name,
+				     val, output, msg);
+}
+
+
+static notmuch_status_t
+_sexp_expand_query (notmuch_database_t *notmuch,
+		    const _sexp_prefix_t *prefix, const _sexp_prefix_t *parent,
+		    unused(const _sexp_binding_t *env), const sexp_t *sx, Xapian::Query &output)
+{
+    Xapian::Query subquery;
+    notmuch_status_t status;
+    std::string msg;
+
+    if (! (parent->flags & SEXP_FLAG_EXPAND)) {
+	_notmuch_database_log (notmuch, "'%s' unsupported inside '%s'\n", prefix->name, parent->name);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    status = _sexp_combine_query (notmuch, NULL, NULL, prefix->xapian_op, prefix->initial, sx,
+				  subquery);
+    if (status)
+	return status;
+
+    status = _notmuch_query_expand (notmuch, parent->name, subquery, output, msg);
+    if (status) {
+	_notmuch_database_log (notmuch, "error expanding query %s\n", msg.c_str ());
+    }
+    return status;
+}
+
+static notmuch_status_t
+_sexp_parse_infix (notmuch_database_t *notmuch, const sexp_t *sx, Xapian::Query &output)
+{
+    try {
+	output = notmuch->query_parser->parse_query (sx->val, NOTMUCH_QUERY_PARSER_FLAGS);
+    } catch (const Xapian::QueryParserError &error) {
+	_notmuch_database_log (notmuch, "Syntax error in infix query: %s\n", sx->val);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    } catch (const Xapian::Error &error) {
+	if (! notmuch->exception_reported) {
+	    _notmuch_database_log (notmuch,
+				   "A Xapian exception occurred parsing query: %s\n",
+				   error.get_msg ().c_str ());
+	    _notmuch_database_log_append (notmuch,
+					  "Query string was: %s\n",
+					  sx->val);
+	    notmuch->exception_reported = true;
+	    return NOTMUCH_STATUS_XAPIAN_EXCEPTION;
+	}
+    }
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
+static notmuch_status_t
+_sexp_parse_header (notmuch_database_t *notmuch, const _sexp_prefix_t *parent,
+		    const _sexp_binding_t *env, const sexp_t *sx, Xapian::Query &output)
+{
+    _sexp_prefix_t user_prefix;
+
+    user_prefix.name = sx->list->val;
+    user_prefix.flags = SEXP_FLAG_FIELD | SEXP_FLAG_WILDCARD;
+
+    if (parent) {
+	_notmuch_database_log (notmuch, "nested field: '%s' inside '%s'\n",
+			       sx->list->val, parent->name);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    parent = &user_prefix;
+
+    return _sexp_combine_query (notmuch, parent, env, Xapian::Query::OP_AND, Xapian::Query::MatchAll,
+				sx->list->next, output);
+}
+
+static _sexp_binding_t *
+_sexp_bind (void *ctx, const _sexp_binding_t *env, const char *name, const sexp_t *sx, const
+	    _sexp_binding_t *context)
+{
+    _sexp_binding_t *binding = talloc (ctx, _sexp_binding_t);
+
+    binding->name = talloc_strdup (ctx, name);
+    binding->sx = sx;
+    binding->context = context;
+    binding->next = env;
+    return binding;
+}
+
+static notmuch_status_t
+maybe_apply_macro (notmuch_database_t *notmuch, const _sexp_prefix_t *parent,
+		   const _sexp_binding_t *env, const sexp_t *sx, const sexp_t *args,
+		   Xapian::Query &output)
+{
+    const sexp_t *params, *param, *arg, *body;
+    void *local = talloc_new (notmuch);
+    _sexp_binding_t *new_env = NULL;
+    notmuch_status_t status = NOTMUCH_STATUS_SUCCESS;
+
+    if (sx->list->ty != SEXP_VALUE || strcmp (sx->list->val, "macro") != 0) {
+	status = NOTMUCH_STATUS_IGNORED;
+	goto DONE;
+    }
+
+    params = sx->list->next;
+
+    if (! params || (params->ty != SEXP_LIST)) {
+	_notmuch_database_log (notmuch, "missing (possibly empty) list of arguments to macro\n");
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    body = params->next;
+
+    if (! body) {
+	_notmuch_database_log (notmuch, "missing body of macro\n");
+	status = NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+	goto DONE;
+    }
+
+    for (param = params->list, arg = args;
+	 param && arg;
+	 param = param->next, arg = arg->next) {
+	if (param->ty != SEXP_VALUE || param->aty != SEXP_BASIC) {
+	    _notmuch_database_log (notmuch, "macro parameters must be unquoted atoms\n");
+	    status = NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+	    goto DONE;
+	}
+	new_env = _sexp_bind (local, new_env, param->val, arg, env);
+    }
+
+    if (param && ! arg) {
+	_notmuch_database_log (notmuch, "too few arguments to macro\n");
+	status = NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+	goto DONE;
+    }
+
+    if (! param && arg) {
+	_notmuch_database_log (notmuch, "too many arguments to macro\n");
+	status = NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+	goto DONE;
+    }
+
+    status = _sexp_to_xapian_query (notmuch, parent, new_env, body, output);
+
+  DONE:
+    if (local)
+	talloc_free (local);
+
+    return status;
+}
+
+static notmuch_status_t
+maybe_saved_squery (notmuch_database_t *notmuch, const _sexp_prefix_t *parent,
+		    const _sexp_binding_t *env, const sexp_t *sx, Xapian::Query &output)
+{
+    char *key;
+    char *expansion = NULL;
+    notmuch_status_t status;
+    sexp_t *saved_sexp;
+    void *local = talloc_new (notmuch);
+    char *buf;
+
+    key = talloc_asprintf (local, "squery.%s", sx->list->val);
+    if (! key) {
+	status = NOTMUCH_STATUS_OUT_OF_MEMORY;
+	goto DONE;
+    }
+
+    status = notmuch_database_get_config (notmuch, key, &expansion);
+    if (status)
+	goto DONE;
+    if (EMPTY_STRING (expansion)) {
+	status = NOTMUCH_STATUS_IGNORED;
+	goto DONE;
+    }
+
+    buf = talloc_strdup (local, expansion);
+    /* XXX TODO: free this memory */
+    saved_sexp = parse_sexp (buf, strlen (expansion));
+    if (! saved_sexp) {
+	_notmuch_database_log (notmuch, "invalid saved s-expression query: '%s'\n", expansion);
+	status = NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+	goto DONE;
+    }
+
+    status = maybe_apply_macro (notmuch, parent, env, saved_sexp, sx->list->next, output);
+    if (status == NOTMUCH_STATUS_IGNORED)
+	status =  _sexp_to_xapian_query (notmuch, parent, env, saved_sexp, output);
+
+  DONE:
+    if (local)
+	talloc_free (local);
+
+    return status;
+}
+
+static notmuch_status_t
+_sexp_expand_param (notmuch_database_t *notmuch, const _sexp_prefix_t *parent,
+		    const _sexp_binding_t *env, const char *name,
+		    Xapian::Query &output)
+{
+    for (; env; env = env->next) {
+	if (strcmp (name, env->name) == 0) {
+	    return _sexp_to_xapian_query (notmuch, parent, env->context, env->sx,
+					  output);
+	}
+    }
+    _notmuch_database_log (notmuch, "undefined parameter %s\n", name);
+    return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+}
+
+/* Here we expect the s-expression to be a proper list, with first
+ * element defining and operation, or as a special case the empty
+ * list */
+
+static notmuch_status_t
+_sexp_to_xapian_query (notmuch_database_t *notmuch, const _sexp_prefix_t *parent,
+		       const _sexp_binding_t *env, const sexp_t *sx, Xapian::Query &output)
+{
+    notmuch_status_t status;
+
+    if (sx->ty == SEXP_VALUE && sx->aty == SEXP_BASIC && sx->val[0] == ',') {
+	return _sexp_expand_param (notmuch, parent, env, sx->val + 1, output);
+    }
+
+    if (sx->ty == SEXP_VALUE) {
+	std::string term_prefix = parent ? _notmuch_database_prefix (notmuch, parent->name) : "";
+
+	if (sx->aty == SEXP_BASIC && strcmp (sx->val, "*") == 0) {
+	    return _sexp_parse_wildcard (notmuch, parent, env, "", output);
+	}
+
+	if (parent && (parent->flags & SEXP_FLAG_BOOLEAN)) {
+	    output = Xapian::Query (term_prefix + sx->val);
+	    return NOTMUCH_STATUS_SUCCESS;
+	}
+
+	if (parent) {
+	    return _sexp_parse_one_term (notmuch, term_prefix, sx, output);
+	} else {
+	    Xapian::Query accumulator;
+	    for (_sexp_prefix_t *prefix = prefixes; prefix->name; prefix++) {
+		if (prefix->flags & SEXP_FLAG_FIELD) {
+		    Xapian::Query subquery;
+		    term_prefix = _notmuch_database_prefix (notmuch, prefix->name);
+		    status = _sexp_parse_one_term (notmuch, term_prefix, sx, subquery);
+		    if (status)
+			return status;
+		    accumulator = Xapian::Query (Xapian::Query::OP_OR, accumulator, subquery);
+		}
+	    }
+	    output = accumulator;
+	    return NOTMUCH_STATUS_SUCCESS;
+	}
+    }
+
+    /* Empty list */
+    if (! sx->list) {
+	output = Xapian::Query::MatchAll;
+	return NOTMUCH_STATUS_SUCCESS;
+    }
+
+    if (sx->list->ty == SEXP_LIST) {
+	_notmuch_database_log (notmuch, "unexpected list in field/operation position\n",
+			       sx->list->val);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    status = maybe_saved_squery (notmuch, parent, env, sx, output);
+    if (status != NOTMUCH_STATUS_IGNORED)
+	return status;
+
+    /* Check for user defined field */
+    if (_notmuch_string_map_get (notmuch->user_prefix, sx->list->val)) {
+	return _sexp_parse_header (notmuch, parent, env, sx, output);
+    }
+
+    if (strcmp (sx->list->val, "macro") == 0) {
+	_notmuch_database_log (notmuch, "macro definition not permitted here\n");
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    for (_sexp_prefix_t *prefix = prefixes; prefix && prefix->name; prefix++) {
+	if (strcmp (prefix->name, sx->list->val) == 0) {
+	    if (prefix->flags & SEXP_FLAG_FIELD) {
+		if (parent) {
+		    _notmuch_database_log (notmuch, "nested field: '%s' inside '%s'\n",
+					   prefix->name, parent->name);
+		    return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+		}
+		parent = prefix;
+	    }
+
+	    if (parent && (prefix->flags & SEXP_FLAG_ORPHAN)) {
+		_notmuch_database_log (notmuch, "'%s' not supported inside '%s'\n",
+				       prefix->name, parent->name);
+		return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+	    }
+
+	    if ((prefix->flags & SEXP_FLAG_SINGLE) &&
+		(! sx->list->next || sx->list->next->next || sx->list->next->ty != SEXP_VALUE)) {
+		_notmuch_database_log (notmuch, "'%s' expects single atom as argument\n",
+				       prefix->name);
+		return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+	    }
+
+	    if (strcmp (prefix->name, "infix") == 0) {
+		return _sexp_parse_infix (notmuch, sx->list->next, output);
+	    }
+
+	    if (strcmp (prefix->name, "query") == 0) {
+		return _notmuch_query_name_to_query (notmuch, sx->list->next->val, output);
+	    }
+
+	    if (prefix->xapian_op == Xapian::Query::OP_WILDCARD)
+		return _sexp_parse_wildcard (notmuch, parent, env, sx->list->next->val, output);
+
+	    if (prefix->flags & SEXP_FLAG_DO_REGEX) {
+		return _sexp_parse_regex (notmuch, prefix, parent, env, sx->list->next->val, output);
+	    }
+
+	    if (prefix->flags & SEXP_FLAG_DO_EXPAND) {
+		return _sexp_expand_query (notmuch, prefix, parent, env, sx->list->next, output);
+	    }
+
+	    return _sexp_combine_query (notmuch, parent, env, prefix->xapian_op, prefix->initial,
+					sx->list->next, output);
+	}
+    }
+
+    _notmuch_database_log (notmuch, "unknown prefix '%s'\n", sx->list->val);
+    return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+}
+
+notmuch_status_t
+_notmuch_sexp_string_to_xapian_query (notmuch_database_t *notmuch, const char *querystr,
+				      Xapian::Query &output)
+{
+    const sexp_t *sx = NULL;
+    char *buf = talloc_strdup (notmuch, querystr);
+
+    sx = parse_sexp (buf, strlen (querystr));
+    if (! sx) {
+	_notmuch_database_log (notmuch, "invalid s-expression: '%s'\n", querystr);
+	return NOTMUCH_STATUS_BAD_QUERY_SYNTAX;
+    }
+
+    return _sexp_to_xapian_query (notmuch, NULL, NULL, sx, output);
+}
+#endif
diff --git a/lib/query-fp.cc b/lib/query-fp.cc
index b980b7f0..75b1d875 100644
--- a/lib/query-fp.cc
+++ b/lib/query-fp.cc
@@ -24,17 +24,33 @@
 #include "query-fp.h"
 #include <iostream>
 
-Xapian::Query
-QueryFieldProcessor::operator() (const std::string & name)
+notmuch_status_t
+_notmuch_query_name_to_query (notmuch_database_t *notmuch, const std::string name,
+			      Xapian::Query &output)
 {
     std::string key = "query." + name;
     char *expansion;
     notmuch_status_t status;
 
     status = notmuch_database_get_config (notmuch, key.c_str (), &expansion);
+    if (status)
+	return status;
+
+    output = notmuch->query_parser->parse_query (expansion, NOTMUCH_QUERY_PARSER_FLAGS);
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
+Xapian::Query
+QueryFieldProcessor::operator() (const std::string & name)
+{
+    notmuch_status_t status;
+    Xapian::Query output;
+
+    status = _notmuch_query_name_to_query (notmuch, name, output);
     if (status) {
 	throw Xapian::QueryParserError ("error looking up key" + name);
     }
 
-    return parser.parse_query (expansion, NOTMUCH_QUERY_PARSER_FLAGS);
+    return output;
+
 }
diff --git a/lib/query.cc b/lib/query.cc
index 792aba21..b0937fcc 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -30,6 +30,7 @@ struct _notmuch_query {
     notmuch_string_list_t *exclude_terms;
     notmuch_exclude_t omit_excluded;
     bool parsed;
+    notmuch_query_syntax_t syntax;
     Xapian::Query xapian_query;
     std::set<std::string> terms;
 };
@@ -84,9 +85,9 @@ _notmuch_query_destructor (notmuch_query_t *query)
     return 0;
 }
 
-notmuch_query_t *
-notmuch_query_create (notmuch_database_t *notmuch,
-		      const char *query_string)
+static notmuch_query_t *
+_notmuch_query_constructor (notmuch_database_t *notmuch,
+			    const char *query_string)
 {
     notmuch_query_t *query;
 
@@ -105,7 +106,10 @@ notmuch_query_create (notmuch_database_t *notmuch,
 
     query->notmuch = notmuch;
 
-    query->query_string = talloc_strdup (query, query_string);
+    if (query_string)
+	query->query_string = talloc_strdup (query, query_string);
+    else
+	query->query_string = NULL;
 
     query->sort = NOTMUCH_SORT_NEWEST_FIRST;
 
@@ -116,44 +120,144 @@ notmuch_query_create (notmuch_database_t *notmuch,
     return query;
 }
 
-static notmuch_status_t
-_notmuch_query_ensure_parsed (notmuch_query_t *query)
+notmuch_query_t *
+notmuch_query_create (notmuch_database_t *notmuch,
+		      const char *query_string)
 {
-    if (query->parsed)
-	return NOTMUCH_STATUS_SUCCESS;
 
-    try {
-	query->xapian_query =
-	    query->notmuch->query_parser->
-	    parse_query (query->query_string, NOTMUCH_QUERY_PARSER_FLAGS);
+    notmuch_query_t *query;
+    notmuch_status_t status;
 
-	/* Xapian doesn't support skip_to on terms from a query since
-	 *  they are unordered, so cache a copy of all terms in
-	 *  something searchable.
-	 */
+    status = notmuch_query_create_with_syntax (notmuch, query_string,
+					       NOTMUCH_QUERY_SYNTAX_XAPIAN,
+					       &query);
+    if (status)
+	return NULL;
+
+    return query;
+}
+
+notmuch_status_t
+notmuch_query_create_with_syntax (notmuch_database_t *notmuch,
+				  const char *query_string,
+				  notmuch_query_syntax_t syntax,
+				  notmuch_query_t **output)
+{
+
+    notmuch_query_t *query;
+
+    if (! output)
+	return NOTMUCH_STATUS_NULL_POINTER;
 
-	for (Xapian::TermIterator t = query->xapian_query.get_terms_begin ();
-	     t != query->xapian_query.get_terms_end (); ++t)
-	    query->terms.insert (*t);
+    query = _notmuch_query_constructor (notmuch, query_string);
+    if (! query)
+	return NOTMUCH_STATUS_OUT_OF_MEMORY;
+
+    if (syntax == NOTMUCH_QUERY_SYNTAX_SEXP && ! HAVE_SFSEXP) {
+	_notmuch_database_log (notmuch, "sexp query parser not available");
+	return NOTMUCH_STATUS_ILLEGAL_ARGUMENT;
+    }
 
-	query->parsed = true;
+    query->syntax = syntax;
 
+    *output = query;
+
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
+static void
+_notmuch_query_cache_terms (notmuch_query_t *query)
+{
+    /* Xapian doesn't support skip_to on terms from a query since
+     *  they are unordered, so cache a copy of all terms in
+     *  something searchable.
+     */
+
+    for (Xapian::TermIterator t = query->xapian_query.get_terms_begin ();
+	 t != query->xapian_query.get_terms_end (); ++t)
+	query->terms.insert (*t);
+}
+
+notmuch_status_t
+_notmuch_query_string_to_xapian_query (notmuch_database_t *notmuch,
+				       std::string query_string,
+				       Xapian::Query &output,
+				       std::string &msg)
+{
+    try {
+	if (query_string == "" || query_string == "*") {
+	    output = Xapian::Query::MatchAll;
+	} else {
+	    output =
+		notmuch->query_parser->
+		parse_query (query_string, NOTMUCH_QUERY_PARSER_FLAGS);
+	}
     } catch (const Xapian::Error &error) {
-	if (! query->notmuch->exception_reported) {
-	    _notmuch_database_log (query->notmuch,
+	if (! notmuch->exception_reported) {
+	    _notmuch_database_log (notmuch,
 				   "A Xapian exception occurred parsing query: %s\n",
 				   error.get_msg ().c_str ());
-	    _notmuch_database_log_append (query->notmuch,
+	    _notmuch_database_log_append (notmuch,
 					  "Query string was: %s\n",
-					  query->query_string);
-	    query->notmuch->exception_reported = true;
+					  query_string.c_str ());
+	    notmuch->exception_reported = true;
 	}
 
+	msg = error.get_msg ();
 	return NOTMUCH_STATUS_XAPIAN_EXCEPTION;
     }
     return NOTMUCH_STATUS_SUCCESS;
 }
 
+static notmuch_status_t
+_notmuch_query_ensure_parsed_xapian (notmuch_query_t *query)
+{
+    notmuch_status_t status;
+    std::string msg; /* ignored */
+
+    status =  _notmuch_query_string_to_xapian_query (query->notmuch, query->query_string,
+						     query->xapian_query, msg);
+    if (status)
+	return status;
+
+    query->parsed = true;
+
+    _notmuch_query_cache_terms (query);
+
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
+static notmuch_status_t
+_notmuch_query_ensure_parsed_sexpr (notmuch_query_t *query)
+{
+    notmuch_status_t status;
+
+    if (query->parsed)
+	return NOTMUCH_STATUS_SUCCESS;
+
+    status = _notmuch_sexp_string_to_xapian_query (query->notmuch, query->query_string,
+						   query->xapian_query);
+    if (status)
+	return status;
+
+    _notmuch_query_cache_terms (query);
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
+static notmuch_status_t
+_notmuch_query_ensure_parsed (notmuch_query_t *query)
+{
+    if (query->parsed)
+	return NOTMUCH_STATUS_SUCCESS;
+
+#if HAVE_SFSEXP
+    if (query->syntax == NOTMUCH_QUERY_SYNTAX_SEXP)
+	return _notmuch_query_ensure_parsed_sexpr (query);
+#endif
+
+    return _notmuch_query_ensure_parsed_xapian (query);
+}
+
 const char *
 notmuch_query_get_query_string (const notmuch_query_t *query)
 {
@@ -249,7 +353,6 @@ _notmuch_query_search_documents (notmuch_query_t *query,
 				 notmuch_messages_t **out)
 {
     notmuch_database_t *notmuch = query->notmuch;
-    const char *query_string = query->query_string;
     notmuch_mset_messages_t *messages;
     notmuch_status_t status;
 
@@ -279,13 +382,9 @@ _notmuch_query_search_documents (notmuch_query_t *query,
 	Xapian::MSet mset;
 	Xapian::MSetIterator iterator;
 
-	if (strcmp (query_string, "") == 0 ||
-	    strcmp (query_string, "*") == 0) {
-	    final_query = mail_query;
-	} else {
-	    final_query = Xapian::Query (Xapian::Query::OP_AND,
-					 mail_query, query->xapian_query);
-	}
+	final_query = Xapian::Query (Xapian::Query::OP_AND,
+				     mail_query, query->xapian_query);
+
 	messages->base.excluded_doc_ids = NULL;
 
 	if ((query->omit_excluded != NOTMUCH_EXCLUDE_FALSE) && (query->exclude_terms)) {
@@ -606,7 +705,6 @@ notmuch_status_t
 _notmuch_query_count_documents (notmuch_query_t *query, const char *type, unsigned *count_out)
 {
     notmuch_database_t *notmuch = query->notmuch;
-    const char *query_string = query->query_string;
     Xapian::doccount count = 0;
     notmuch_status_t status;
 
@@ -622,13 +720,8 @@ _notmuch_query_count_documents (notmuch_query_t *query, const char *type, unsign
 	Xapian::Query final_query, exclude_query;
 	Xapian::MSet mset;
 
-	if (strcmp (query_string, "") == 0 ||
-	    strcmp (query_string, "*") == 0) {
-	    final_query = mail_query;
-	} else {
-	    final_query = Xapian::Query (Xapian::Query::OP_AND,
-					 mail_query, query->xapian_query);
-	}
+	final_query = Xapian::Query (Xapian::Query::OP_AND,
+				     mail_query, query->xapian_query);
 
 	exclude_query = _notmuch_exclude_tags (query);
 
@@ -728,3 +821,51 @@ notmuch_query_get_database (const notmuch_query_t *query)
 {
     return query->notmuch;
 }
+
+notmuch_status_t
+_notmuch_query_expand (notmuch_database_t *notmuch, const char *field, Xapian::Query subquery,
+		       Xapian::Query &output, std::string &msg)
+{
+    std::set<std::string> terms;
+    const std::string term_prefix =  _find_prefix (field);
+
+    if (_debug_query ()) {
+	fprintf (stderr, "Expanding subquery:\n%s\n",
+		 subquery.get_description ().c_str ());
+    }
+
+    try {
+	Xapian::Enquire enquire (*notmuch->xapian_db);
+	Xapian::MSet mset;
+
+	enquire.set_weighting_scheme (Xapian::BoolWeight ());
+	enquire.set_query (subquery);
+
+	mset = enquire.get_mset (0, notmuch->xapian_db->get_doccount ());
+
+	for (Xapian::MSetIterator iterator = mset.begin (); iterator != mset.end (); iterator++) {
+	    Xapian::docid doc_id = *iterator;
+	    Xapian::Document doc = notmuch->xapian_db->get_document (doc_id);
+	    Xapian::TermIterator i = doc.termlist_begin ();
+
+	    for (i.skip_to (term_prefix);
+		 i != doc.termlist_end () && ((*i).rfind (term_prefix, 0) == 0); i++) {
+		terms.insert (*i);
+	    }
+	}
+	output = Xapian::Query (Xapian::Query::OP_OR, terms.begin (), terms.end ());
+	if (_debug_query ()) {
+	    fprintf (stderr, "Expanded query:\n%s\n",
+		     subquery.get_description ().c_str ());
+	}
+
+    } catch (const Xapian::Error &error) {
+	_notmuch_database_log (notmuch,
+			       "A Xapian exception occurred expanding query: %s\n",
+			       error.get_msg ().c_str ());
+	msg = error.get_msg ();
+	return NOTMUCH_STATUS_XAPIAN_EXCEPTION;
+    }
+
+    return NOTMUCH_STATUS_SUCCESS;
+}
diff --git a/lib/regexp-fields.cc b/lib/regexp-fields.cc
index 0feb50e5..c6d9d94f 100644
--- a/lib/regexp-fields.cc
+++ b/lib/regexp-fields.cc
@@ -26,27 +26,32 @@
 #include "notmuch-private.h"
 #include "database-private.h"
 
-static void
-compile_regex (regex_t &regexp, const char *str)
+notmuch_status_t
+compile_regex (regex_t &regexp, const char *str, std::string &msg)
 {
     int err = regcomp (&regexp, str, REG_EXTENDED | REG_NOSUB);
 
     if (err != 0) {
 	size_t len = regerror (err, &regexp, NULL, 0);
 	char *buffer = new char[len];
-	std::string msg = "Regexp error: ";
+	msg = "Regexp error: ";
 	(void) regerror (err, &regexp, buffer, len);
 	msg.append (buffer, len);
 	delete[] buffer;
 
-	throw Xapian::QueryParserError (msg);
+	return NOTMUCH_STATUS_ILLEGAL_ARGUMENT;
     }
+    return NOTMUCH_STATUS_SUCCESS;
 }
 
 RegexpPostingSource::RegexpPostingSource (Xapian::valueno slot, const std::string &regexp)
     : slot_ (slot)
 {
-    compile_regex (regexp_, regexp.c_str ());
+    std::string msg;
+    notmuch_status_t status = compile_regex (regexp_, regexp.c_str (), msg);
+
+    if (status)
+	throw Xapian::QueryParserError (msg);
 }
 
 RegexpPostingSource::~RegexpPostingSource ()
@@ -141,18 +146,54 @@ _find_slot (std::string prefix)
 	return Xapian::BAD_VALUENO;
 }
 
-RegexpFieldProcessor::RegexpFieldProcessor (std::string prefix,
+RegexpFieldProcessor::RegexpFieldProcessor (std::string field_,
 					    notmuch_field_flag_t options_,
 					    Xapian::QueryParser &parser_,
 					    notmuch_database_t *notmuch_)
-    : slot (_find_slot (prefix)),
-    term_prefix (_find_prefix (prefix.c_str ())),
+    : slot (_find_slot (field_)),
+    field (field_),
+    term_prefix (_find_prefix (field_.c_str ())),
     options (options_),
     parser (parser_),
     notmuch (notmuch_)
 {
 };
 
+notmuch_status_t
+_notmuch_regexp_to_query (notmuch_database_t *notmuch, Xapian::valueno slot, std::string field,
+			  std::string regexp_str,
+			  Xapian::Query &output, std::string &msg)
+{
+    regex_t regexp;
+    notmuch_status_t status;
+
+    status = compile_regex (regexp, regexp_str.c_str (), msg);
+    if (status) {
+	_notmuch_database_log_append (notmuch, "error compiling regex %s", msg.c_str ());
+	return status;
+    }
+
+    if (slot == Xapian::BAD_VALUENO)
+	slot = _find_slot (field);
+
+    if (slot == Xapian::BAD_VALUENO) {
+	std::string term_prefix = _find_prefix (field.c_str ());
+	std::vector<std::string> terms;
+
+	for (Xapian::TermIterator it = notmuch->xapian_db->allterms_begin (term_prefix);
+	     it != notmuch->xapian_db->allterms_end (); ++it) {
+	    if (regexec (&regexp, (*it).c_str () + term_prefix.size (),
+			 0, NULL, 0) == 0)
+		terms.push_back (*it);
+	}
+	output = Xapian::Query (Xapian::Query::OP_OR, terms.begin (), terms.end ());
+    } else {
+	RegexpPostingSource *postings = new RegexpPostingSource (slot, regexp_str);
+	output = Xapian::Query (postings->release ());
+    }
+    return NOTMUCH_STATUS_SUCCESS;
+}
+
 Xapian::Query
 RegexpFieldProcessor::operator() (const std::string & str)
 {
@@ -168,23 +209,15 @@ RegexpFieldProcessor::operator() (const std::string & str)
 
     if (str.at (0) == '/') {
 	if (str.length () > 1 && str.at (str.size () - 1) == '/') {
+	    Xapian::Query query;
 	    std::string regexp_str = str.substr (1, str.size () - 2);
-	    if (slot != Xapian::BAD_VALUENO) {
-		RegexpPostingSource *postings = new RegexpPostingSource (slot, regexp_str);
-		return Xapian::Query (postings->release ());
-	    } else {
-		std::vector<std::string> terms;
-		regex_t regexp;
+	    std::string msg;
+	    notmuch_status_t status;
 
-		compile_regex (regexp, regexp_str.c_str ());
-		for (Xapian::TermIterator it = notmuch->xapian_db->allterms_begin (term_prefix);
-		     it != notmuch->xapian_db->allterms_end (); ++it) {
-		    if (regexec (&regexp, (*it).c_str () + term_prefix.size (),
-				 0, NULL, 0) == 0)
-			terms.push_back (*it);
-		}
-		return Xapian::Query (Xapian::Query::OP_OR, terms.begin (), terms.end ());
-	    }
+	    status = _notmuch_regexp_to_query (notmuch, slot, field, regexp_str, query, msg);
+	    if (status)
+		throw Xapian::QueryParserError (msg);
+	    return query;
 	} else {
 	    throw Xapian::QueryParserError ("unmatched regex delimiter in '" + str + "'");
 	}
diff --git a/lib/regexp-fields.h b/lib/regexp-fields.h
index a8cca243..9c871de7 100644
--- a/lib/regexp-fields.h
+++ b/lib/regexp-fields.h
@@ -30,6 +30,11 @@
 #include "database-private.h"
 #include "notmuch-private.h"
 
+notmuch_status_t
+_notmuch_regex_to_query (notmuch_database_t *notmuch, Xapian::valueno slot, std::string field,
+			 std::string regexp_str,
+			 Xapian::Query &output, std::string &msg);
+
 /* A posting source that returns documents where a value matches a
  * regexp.
  */
@@ -64,6 +69,7 @@ public:
 class RegexpFieldProcessor : public Xapian::FieldProcessor {
 protected:
     Xapian::valueno slot;
+    std::string field;
     std::string term_prefix;
     notmuch_field_flag_t options;
     Xapian::QueryParser &parser;
diff --git a/lib/thread-fp.cc b/lib/thread-fp.cc
index 06708ef2..3aa9c423 100644
--- a/lib/thread-fp.cc
+++ b/lib/thread-fp.cc
@@ -34,28 +34,20 @@ ThreadFieldProcessor::operator() (const std::string & str)
 	if (str.size () <= 1 || str.at (str.size () - 1) != '}') {
 	    throw Xapian::QueryParserError ("missing } in '" + str + "'");
 	} else {
+	    Xapian::Query subquery;
+	    Xapian::Query query;
+	    std::string msg;
 	    std::string subquery_str = str.substr (1, str.size () - 2);
-	    notmuch_query_t *subquery = notmuch_query_create (notmuch, subquery_str.c_str ());
-	    notmuch_messages_t *messages;
-	    std::set<std::string> terms;
 
-	    if (! subquery)
-		throw Xapian::QueryParserError ("failed to create subquery for '" + subquery_str +
-						"'");
+	    status = _notmuch_query_string_to_xapian_query (notmuch, subquery_str, subquery, msg);
+	    if (status)
+		throw Xapian::QueryParserError (msg);
 
-	    status = notmuch_query_search_messages (subquery, &messages);
+	    status = _notmuch_query_expand (notmuch, "thread", subquery, query, msg);
 	    if (status)
-		throw Xapian::QueryParserError ("failed to search messages for '" + subquery_str +
-						"'");
+		throw Xapian::QueryParserError (msg);
 
-	    for (; notmuch_messages_valid (messages); notmuch_messages_move_to_next (messages)) {
-		std::string term = thread_prefix;
-		notmuch_message_t *message;
-		message = notmuch_messages_get (messages);
-		term += _notmuch_message_get_thread_id_only (message);
-		terms.insert (term);
-	    }
-	    return Xapian::Query (Xapian::Query::OP_OR, terms.begin (), terms.end ());
+	    return query;
 	}
     } else {
 	/* literal thread id */