--- a/src/lib-storage/mail-search-args-simplify.c	Thu Apr 13 14:05:55 2017 +0300
+++ b/src/lib-storage/mail-search-args-simplify.c	Thu Apr 13 15:09:19 2017 +0300
@@ -60,7 +60,6 @@
 {
 	i_zero(mask_r);
 	mask_r->bin_mask.type = arg->type;
-	mask_r->bin_mask.match_not = arg->match_not;
 	mask_r->bin_mask.fuzzy = arg->fuzzy;
 	mask_r->bin_mask.search_flags = arg->value.search_flags;
 }
@@ -84,6 +83,27 @@
 	return &prev_arg->prev_arg;
 }
 
+static bool
+mail_search_args_merge_mask(struct mail_search_simplify_ctx *ctx,
+			    struct mail_search_arg *args,
+			    const struct mail_search_simplify_prev_arg *mask)
+{
+	struct mail_search_arg **prev_argp;
+
+	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, mask);
+	if (*prev_argp == NULL) {
+		*prev_argp = args;
+		return FALSE;
+	}
+	if ((*prev_argp)->match_not != args->match_not) {
+		/* a && !a = 0 */
+		(*prev_argp)->type = SEARCH_ALL;
+		(*prev_argp)->match_not = ctx->parent_and;
+	}
+	/* duplicate keyword. */
+	return TRUE;
+}
+
 static bool mail_search_args_merge_flags(struct mail_search_simplify_ctx *ctx,
 					 struct mail_search_arg *args)
 {
@@ -95,6 +115,7 @@
 		return FALSE;
 
 	mail_search_arg_get_base_mask(args, &mask);
+	mask.bin_mask.match_not = args->match_not;
 	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
 
 	if (*prev_argp == NULL) {
@@ -111,18 +132,10 @@
 				struct mail_search_arg *args)
 {
 	struct mail_search_simplify_prev_arg mask;
-	struct mail_search_arg **prev_argp;
 
 	mail_search_arg_get_base_mask(args, &mask);
 	mask.str_mask = args->value.str;
-	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
-
-	if (*prev_argp == NULL) {
-		*prev_argp = args;
-		return FALSE;
-	}
-	/* duplicate keyword. */
-	return TRUE;
+	return mail_search_args_merge_mask(ctx, args, &mask);
 }
 
 static void mail_search_args_simplify_set(struct mail_search_arg *args)
@@ -164,6 +177,7 @@
 	}
 
 	mail_search_arg_get_base_mask(args, &mask);
+	mask.bin_mask.match_not = args->match_not;
 	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
 
 	if (*prev_argp == NULL) {
@@ -187,6 +201,7 @@
 	struct mail_search_arg **prev_argp, *prev_arg;
 
 	mail_search_arg_get_base_mask(args, &mask);
+	mask.bin_mask.match_not = args->match_not;
 	mask.bin_mask.date_type = args->value.date_type;
 	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
 
@@ -248,6 +263,7 @@
 	struct mail_search_arg **prev_argp, *prev_arg;
 
 	mail_search_arg_get_base_mask(args, &mask);
+	mask.bin_mask.match_not = args->match_not;
 	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
 
 	if (*prev_argp == NULL) {
@@ -301,19 +317,11 @@
 					struct mail_search_arg *args)
 {
 	struct mail_search_simplify_prev_arg mask;
-	struct mail_search_arg **prev_argp;
 
 	mail_search_arg_get_base_mask(args, &mask);
 	mask.hdr_field_name_mask = args->hdr_field_name;
 	mask.str_mask = args->value.str;
-	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
-
-	if (*prev_argp == NULL) {
-		*prev_argp = args;
-		return FALSE;
-	}
-	/* duplicate search word. */
-	return TRUE;
+	return mail_search_args_merge_mask(ctx, args, &mask);
 }
 
 static bool

--- a/src/lib-storage/test-mail-search-args-simplify.c	Thu Apr 13 14:05:55 2017 +0300
+++ b/src/lib-storage/test-mail-search-args-simplify.c	Thu Apr 13 15:09:19 2017 +0300
@@ -59,6 +59,8 @@
 	{ "OR NOT KEYWORD foo NOT KEYWORD bar", "(OR NOT KEYWORD foo NOT KEYWORD bar)" },
 
 	{ "KEYWORD foo KEYWORD foo", "KEYWORD foo" },
+	{ "KEYWORD foo NOT KEYWORD foo", "NOT ALL" },
+	{ "OR KEYWORD foo NOT KEYWORD foo", "ALL" },
 	{ "OR KEYWORD foo KEYWORD foo", "KEYWORD foo" },
 	{ "NOT KEYWORD foo NOT KEYWORD foo", "NOT KEYWORD foo" },
 
@@ -125,17 +127,26 @@
 	{ "LARGER 3 NOT LARGER 1 LARGER 2", "LARGER 3 NOT LARGER 1" },
 
 	{ "SUBJECT foo SUBJECT foo", "SUBJECT foo" },
+	{ "SUBJECT foo NOT SUBJECT foo", "NOT ALL" },
+	{ "OR SUBJECT foo NOT SUBJECT foo", "ALL" },
 	{ "SUBJECT foo SUBJECT foob", "SUBJECT foo SUBJECT foob" },
 	{ "OR SUBJECT foo SUBJECT foo", "SUBJECT foo" },
 	{ "FROM foo FROM foo", "FROM foo" },
+	{ "FROM foo NOT FROM foo", "NOT ALL" },
+	{ "OR FROM foo NOT FROM foo", "ALL" },
 	{ "FROM foo FROM bar", "FROM foo FROM bar" },
 	{ "FROM foo TO foo", "FROM foo TO foo" },
 
 	{ "TEXT foo TEXT foo", "TEXT foo" },
 	{ "TEXT foo TEXT foob", "TEXT foo TEXT foob" },
 	{ "OR TEXT foo TEXT foo", "TEXT foo" },
-	{ "TEXT foo NOT TEXT foo TEXT foo NOT TEXT foo", "TEXT foo NOT TEXT foo" },
+	{ "OR NOT TEXT foo TEXT foo", "ALL" },
+	{ "OR TEXT foo NOT TEXT foo", "ALL" },
+	{ "TEXT foo NOT TEXT foo", "NOT ALL" },
+	{ "NOT TEXT foo TEXT foo", "NOT ALL" },
 	{ "BODY foo BODY foo", "BODY foo" },
+	{ "BODY foo NOT BODY foo", "NOT ALL" },
+	{ "OR BODY foo NOT BODY foo", "ALL" },
 	{ "OR BODY foo BODY foo", "BODY foo" },
 	{ "TEXT foo BODY foo", "TEXT foo BODY foo" },
 	{ "OR ( TEXT foo OR TEXT foo TEXT foo ) ( TEXT foo ( TEXT foo ) )", "TEXT foo" },