Adding upstream version 1:2.3.21+dfsg1.upstream/1%2.3.21+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 921 insertions, 0 deletions

diff --git a/src/lib-storage/mail-search-args-simplify.c b/src/lib-storage/mail-search-args-simplify.c
new file mode 100644
index 0000000..e6490b5
--- /dev/null
+++ b/src/lib-storage/mail-search-args-simplify.c
@@ -0,0 +1,921 @@
+/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "hash.h"
+#include "mail-search.h"
+
+struct mail_search_simplify_prev_arg {
+	struct {
+		enum mail_search_arg_type type;
+		enum mail_search_arg_flag search_flags;
+		enum mail_search_date_type date_type;
+		enum mail_flags mail_flags;
+		bool match_not;
+		bool fuzzy;
+	} bin_mask;
+	const char *hdr_field_name_mask;
+	const char *str_mask;
+
+	struct mail_search_arg *prev_arg;
+};
+
+struct mail_search_simplify_ctx {
+	pool_t pool;
+	/* arg mask => prev_arg */
+	HASH_TABLE(struct mail_search_simplify_prev_arg *,
+		   struct mail_search_simplify_prev_arg *) prev_args;
+	bool parent_and;
+	bool removals;
+	bool initialized;
+};
+
+static int
+mail_search_simplify_prev_arg_cmp(const struct mail_search_simplify_prev_arg *arg1,
+				  const struct mail_search_simplify_prev_arg *arg2)
+{
+	int ret;
+
+	ret = memcmp(&arg1->bin_mask, &arg2->bin_mask, sizeof(arg1->bin_mask));
+	if (ret == 0)
+		ret = null_strcmp(arg1->hdr_field_name_mask, arg2->hdr_field_name_mask);
+	if (ret == 0)
+		ret = null_strcmp(arg1->str_mask, arg2->str_mask);
+	return ret;
+}
+
+static unsigned int
+mail_search_simplify_prev_arg_hash(const struct mail_search_simplify_prev_arg *arg)
+{
+	unsigned int hash;
+
+	hash = mem_hash(&arg->bin_mask, sizeof(arg->bin_mask));
+	if (arg->hdr_field_name_mask != NULL)
+		hash ^= str_hash(arg->hdr_field_name_mask);
+	if (arg->str_mask != NULL)
+		hash ^= str_hash(arg->str_mask);
+	return hash;
+}
+
+static void mail_search_arg_get_base_mask(const struct mail_search_arg *arg,
+					  struct mail_search_simplify_prev_arg *mask_r)
+{
+	i_zero(mask_r);
+	mask_r->bin_mask.type = arg->type;
+	mask_r->bin_mask.fuzzy = arg->fuzzy;
+	mask_r->bin_mask.search_flags = arg->value.search_flags;
+}
+
+static struct mail_search_arg **
+mail_search_args_simplify_get_prev_argp(struct mail_search_simplify_ctx *ctx,
+					const struct mail_search_simplify_prev_arg *mask)
+{
+	struct mail_search_simplify_prev_arg *prev_arg;
+
+	prev_arg = hash_table_lookup(ctx->prev_args, mask);
+	if (prev_arg == NULL) {
+		prev_arg = p_new(ctx->pool, struct mail_search_simplify_prev_arg, 1);
+		prev_arg->bin_mask = mask->bin_mask;
+		prev_arg->hdr_field_name_mask =
+			p_strdup(ctx->pool, mask->hdr_field_name_mask);
+		prev_arg->str_mask =
+			p_strdup(ctx->pool, mask->str_mask);
+		hash_table_insert(ctx->prev_args, prev_arg, prev_arg);
+	}
+	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 (ctx->initialized)
+		mail_search_arg_one_deinit(args);
+
+	if ((*prev_argp)->match_not != args->match_not) {
+		/* a && !a = 0 */
+		if (ctx->initialized)
+			mail_search_arg_one_deinit(*prev_argp);
+		(*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)
+{
+	struct mail_search_simplify_prev_arg mask;
+
+	mail_search_arg_get_base_mask(args, &mask);
+	mask.bin_mask.mail_flags = args->value.flags;
+	return mail_search_args_merge_mask(ctx, args, &mask);
+}
+
+static bool
+mail_search_args_merge_keywords(struct mail_search_simplify_ctx *ctx,
+				struct mail_search_arg *args)
+{
+	struct mail_search_simplify_prev_arg mask;
+
+	mail_search_arg_get_base_mask(args, &mask);
+	mask.str_mask = args->value.str;
+	return mail_search_args_merge_mask(ctx, args, &mask);
+}
+
+static void mail_search_args_simplify_set(struct mail_search_arg *args)
+{
+	const struct seq_range *seqset;
+	unsigned int count;
+
+	if (args->match_not) {
+		/* invert the set to drop the NOT. Note that (uint32_t)-1
+		   matches the last existing mail, which we don't know at this
+		   point. lib-imap/imap-seqset.c has similar code that
+		   disallows using (uint32_t)-1 as a real UID. */
+		if (seq_range_exists(&args->value.seqset, (uint32_t)-1))
+			return;
+		args->match_not = FALSE;
+		seq_range_array_invert(&args->value.seqset, 1, (uint32_t)-2);
+	}
+	seqset = array_get(&args->value.seqset, &count);
+	if (count == 1 && seqset->seq1 == 1 && seqset->seq2 >= (uint32_t)-2) {
+		/* 1:* is the same as ALL. */
+		args->type = SEARCH_ALL;
+	} else if (count == 0) {
+		/* empty set is the same as NOT ALL. this is mainly coming
+		   from mail_search_args_merge_set() intersection. */
+		args->type = SEARCH_ALL;
+		args->match_not = TRUE;
+	}
+}
+
+static bool mail_search_args_merge_set(struct mail_search_simplify_ctx *ctx,
+				       struct mail_search_arg *args)
+{
+	struct mail_search_simplify_prev_arg mask;
+	struct mail_search_arg **prev_argp;
+
+	if (args->match_not) {
+		/* "*" used - can't simplify it */
+		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) {
+		*prev_argp = args;
+		return FALSE;
+	} else if (ctx->parent_and) {
+		seq_range_array_intersect(&(*prev_argp)->value.seqset,
+					  &args->value.seqset);
+		return TRUE;
+	} else {
+		seq_range_array_merge(&(*prev_argp)->value.seqset,
+				      &args->value.seqset);
+		return TRUE;
+	}
+}
+
+static bool mail_search_args_merge_time(struct mail_search_simplify_ctx *ctx,
+					struct mail_search_arg *args)
+{
+	struct mail_search_simplify_prev_arg mask;
+	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);
+
+	if (*prev_argp == NULL) {
+		*prev_argp = args;
+		return FALSE;
+	}
+
+	prev_arg = *prev_argp;
+	switch (args->type) {
+	case SEARCH_BEFORE:
+		if (ctx->parent_and) {
+			if (prev_arg->value.time < args->value.time) {
+				/* prev_arg < 5 AND arg < 10 */
+			} else {
+				/* prev_arg < 10 AND arg < 5 */
+				prev_arg->value.time = args->value.time;
+			}
+		} else {
+			if (prev_arg->value.time < args->value.time) {
+				/* prev_arg < 5 OR arg < 10 */
+				prev_arg->value.time = args->value.time;
+			} else {
+				/* prev_arg < 10 OR arg < 5 */
+			}
+		}
+		return TRUE;
+	case SEARCH_ON:
+		if (prev_arg->value.time == args->value.time)
+			return TRUE;
+		return FALSE;
+	case SEARCH_SINCE:
+		if (ctx->parent_and) {
+			if (prev_arg->value.time < args->value.time) {
+				/* prev_arg >= 5 AND arg >= 10 */
+				prev_arg->value.time = args->value.time;
+			} else {
+				/* prev_arg >= 10 AND arg >= 5 */
+			}
+		} else {
+			if (prev_arg->value.time < args->value.time) {
+				/* prev_arg >= 5 OR arg >= 10 */
+			} else {
+				/* prev_arg >= 10 OR arg >= 5 */
+				prev_arg->value.time = args->value.time;
+			}
+		}
+		return TRUE;
+	default:
+		break;
+	}
+	return FALSE;
+}
+
+static bool mail_search_args_merge_size(struct mail_search_simplify_ctx *ctx,
+					struct mail_search_arg *args)
+{
+	struct mail_search_simplify_prev_arg mask;
+	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) {
+		*prev_argp = args;
+		return FALSE;
+	}
+
+	prev_arg = *prev_argp;
+	switch (args->type) {
+	case SEARCH_SMALLER:
+		if (ctx->parent_and) {
+			if (prev_arg->value.size < args->value.size) {
+				/* prev_arg < 5 AND arg < 10 */
+			} else {
+				/* prev_arg < 10 AND arg < 5 */
+				prev_arg->value.size = args->value.size;
+			}
+		} else {
+			if (prev_arg->value.size < args->value.size) {
+				/* prev_arg < 5 OR arg < 10 */
+				prev_arg->value.size = args->value.size;
+			} else {
+				/* prev_arg < 10 OR arg < 5 */
+			}
+		}
+		return TRUE;
+	case SEARCH_LARGER:
+		if (ctx->parent_and) {
+			if (prev_arg->value.size < args->value.size) {
+				/* prev_arg >= 5 AND arg >= 10 */
+				prev_arg->value.size = args->value.size;
+			} else {
+				/* prev_arg >= 10 AND arg >= 5 */
+			}
+		} else {
+			if (prev_arg->value.size < args->value.size) {
+				/* prev_arg >= 5 OR arg >= 10 */
+			} else {
+				/* prev_arg >= 10 OR arg >= 5 */
+				prev_arg->value.size = args->value.size;
+			}
+		}
+		return TRUE;
+	default:
+		break;
+	}
+	return FALSE;
+}
+
+static bool mail_search_args_merge_text(struct mail_search_simplify_ctx *ctx,
+					struct mail_search_arg *args)
+{
+	struct mail_search_simplify_prev_arg mask;
+
+	mail_search_arg_get_base_mask(args, &mask);
+	mask.hdr_field_name_mask = args->hdr_field_name;
+	mask.str_mask = args->value.str;
+	return mail_search_args_merge_mask(ctx, args, &mask);
+}
+
+static bool
+mail_search_args_have_equal(const struct mail_search_arg *args,
+			    const struct mail_search_arg *wanted_arg)
+{
+	const struct mail_search_arg *arg;
+
+	for (arg = args; arg != NULL; arg = arg->next) {
+		if (mail_search_arg_one_equals(arg, wanted_arg))
+			return TRUE;
+	}
+	return FALSE;
+}
+
+static bool
+mail_search_args_remove_equal(struct mail_search_args *all_args,
+			      struct mail_search_arg **argsp,
+			      const struct mail_search_arg *wanted_arg,
+			      bool check_subs)
+{
+	struct mail_search_arg **argp;
+	bool found = FALSE;
+
+	for (argp = argsp; (*argp) != NULL; ) {
+		if (mail_search_arg_one_equals(*argp, wanted_arg)) {
+			if (all_args->init_refcount > 0)
+				mail_search_arg_one_deinit(*argp);
+			*argp = (*argp)->next;
+			found = TRUE;
+		} else if (check_subs) {
+			i_assert((*argp)->type == SEARCH_SUB ||
+				 (*argp)->type == SEARCH_OR);
+			if (!mail_search_args_remove_equal(all_args, &(*argp)->value.subargs, wanted_arg, FALSE)) {
+				/* we already verified that this should have
+				   existed. */
+				i_unreached();
+			}
+			if ((*argp)->value.subargs == NULL)
+				*argp = (*argp)->next;
+			else
+				argp = &(*argp)->next;
+			found = TRUE;
+		} else {
+			argp = &(*argp)->next;
+		}
+	}
+	return found;
+}
+
+static bool
+mail_search_args_have_all_equal(struct mail_search_arg *parent_arg,
+				const struct mail_search_arg *wanted_args)
+{
+	const struct mail_search_arg *arg;
+
+	i_assert(parent_arg->type == SEARCH_SUB ||
+		 parent_arg->type == SEARCH_OR);
+
+	for (arg = wanted_args; arg != NULL; arg = arg->next) {
+		if (!mail_search_args_have_equal(parent_arg->value.subargs, arg))
+			return FALSE;
+	}
+	return TRUE;
+}
+
+/* Absorptive Law - This law enables a reduction in a complicated expression to
+   a simpler one by absorbing like terms.
+
+   A + (A.B) =  (A.1) + (A.B)  = A(1 + B)  = A  (OR Absorption Law)
+   A(A + B)  = (A + 0).(A + B) = A + (0.B) = A  (AND Absorption Law)
+
+   Cases with multiple shared terms (duals appy as well)
+
+   A + B + (A.C) + (B.C) = (A + (A.C)) + (B + B.C))  (apply law to sides of external sum))
+                         = A + B
+   A + B + (A.B.C) = (A + (A.(B.C))) + B 	     (X = B.C)
+                   = (A + (A.(X)) + B                (apply law to X)
+		   = A + B
+*/
+static bool
+mail_search_args_simplify_drop_redundant_args(struct mail_search_args *all_args,
+					      struct mail_search_arg **argsp,
+					      bool and_arg)
+{
+	if (*argsp == NULL || (*argsp)->next == NULL)
+		return FALSE;
+
+	struct mail_search_arg *arg, **argp;
+	enum mail_search_arg_type child_subargs_type;
+	bool changed = FALSE;
+
+	ARRAY(const struct mail_search_arg *) candidates;
+	t_array_init(&candidates, 1);
+
+	child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
+	for (arg = *argsp; arg != NULL; arg = arg->next) {
+		if (arg->type == child_subargs_type) {
+			const struct mail_search_arg *entry = arg->value.subargs;
+			if (entry == NULL ||
+			    array_lsearch(&candidates, &entry,
+			    		  mail_search_arg_equals_p) != NULL)
+				continue;
+			array_push_back(&candidates, &entry);
+		} else {
+			struct mail_search_arg *copy = t_new(struct mail_search_arg, 1);
+			*copy = *arg;
+			copy->next = NULL;
+			const struct mail_search_arg *entry = copy;
+			array_push_back(&candidates, &entry);
+		}
+	}
+
+	const struct mail_search_arg *candidate;
+	array_foreach_elem(&candidates, candidate) {
+		/* if there are any args that include the candidate - EXCEPT the
+		   one that originally contained it - drop the arg, since it is
+		   redundant. (non-SUB duplicates are dropped elsewhere.) */
+		for (argp = argsp; *argp != NULL; ) {
+			if (*argp != candidate &&
+			   (*argp)->type == child_subargs_type &&
+			   (*argp)->value.subargs != candidate &&
+			   mail_search_args_have_all_equal(*argp, candidate)) {
+				if (all_args->init_refcount > 0)
+					mail_search_arg_one_deinit(*argp);
+				*argp = (*argp)->next;
+				changed = TRUE;
+			} else {
+				argp = &(*argp)->next;
+			}
+		}
+	}
+	return changed;
+}
+
+static bool
+mail_search_args_simplify_extract_common(struct mail_search_args *all_args,
+					 struct mail_search_arg **argsp,
+					 pool_t pool, bool and_arg)
+{
+	/* Simple SUB example:
+	   (a AND b) OR (a AND c) -> a AND (b OR c)
+
+	   More complicated example:
+	   (c1 AND c2 AND u1 AND u2) OR (c1 AND c2 AND u3 AND u4) ->
+	   c1 AND c2 AND ((u1 AND u2) OR (u3 AND u4))
+
+	   Similarly for ORs:
+	   (a OR b) AND (a OR c) -> a OR (b AND c)
+
+	   (c1 OR c2 OR u1 OR u2) AND (c1 OR c2 OR u3 OR u4) ->
+	   c1 OR c2 OR ((u1 OR u2) AND (u3 OR u4))
+
+	*/
+	struct mail_search_arg *arg, *sub_arg, *sub_next;
+	struct mail_search_arg *new_arg, *child_arg, *common_args = NULL;
+	enum mail_search_arg_type child_subargs_type;
+
+	if (*argsp == NULL || (*argsp)->next == NULL) {
+		/* single arg, nothing to extract */
+		return FALSE;
+	}
+
+	child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
+
+	/* find the first arg with child_subargs_type */
+	for (arg = *argsp; arg != NULL; arg = arg->next) {
+		if (arg->type == child_subargs_type)
+			break;
+	}
+	if (arg == NULL)
+		return FALSE;
+
+	for (sub_arg = arg->value.subargs; sub_arg != NULL; sub_arg = sub_next) {
+		sub_next = sub_arg->next;
+
+		/* check if sub_arg is found from all the args */
+		for (arg = *argsp; arg != NULL; arg = arg->next) {
+			if (mail_search_arg_one_equals(arg, sub_arg)) {
+				/* the whole arg matches */
+			} else if (arg->type == child_subargs_type &&
+				   mail_search_args_have_equal(arg->value.subargs, sub_arg)) {
+				/* exists as subarg */
+			} else {
+				break;
+			}
+		}
+		if (arg != NULL)
+			continue;
+
+		/* extract the arg and put it to common_args */
+		mail_search_args_remove_equal(all_args, argsp, sub_arg, TRUE);
+		sub_arg->next = common_args;
+		common_args = sub_arg;
+	}
+	if (common_args == NULL)
+		return FALSE;
+
+	/* replace all the original args with a single new SUB/OR arg */
+	new_arg = p_new(pool, struct mail_search_arg, 1);
+	new_arg->type = child_subargs_type;
+	if (*argsp == NULL) {
+		/* there are only common args */
+		new_arg->value.subargs = common_args;
+	} else {
+		/* replace OR arg with AND(OR(non_common_args), common_args)
+		   or
+		   replace AND arg with OR(AND(non_common_args), common_args) */
+		child_arg = p_new(pool, struct mail_search_arg, 1);
+		child_arg->type = and_arg ? SEARCH_SUB : SEARCH_OR;
+		child_arg->value.subargs = *argsp;
+		child_arg->next = common_args;
+		new_arg->value.subargs = child_arg;
+	}
+	*argsp = new_arg;
+	return TRUE;
+}
+
+static bool mail_search_args_nils_removable(enum mail_search_arg_type type) {
+	switch(type) {
+		case SEARCH_FLAGS:
+		case SEARCH_KEYWORDS:
+		case SEARCH_BEFORE:
+		case SEARCH_ON:
+		case SEARCH_SINCE:
+		case SEARCH_SMALLER:
+		case SEARCH_LARGER:
+		case SEARCH_GUID:
+		case SEARCH_MAILBOX:
+		case SEARCH_MAILBOX_GUID:
+		case SEARCH_MAILBOX_GLOB:
+		case SEARCH_MODSEQ:
+		case SEARCH_REAL_UID:
+		case SEARCH_SEQSET:
+		case SEARCH_UIDSET:
+		case SEARCH_MIMEPART:
+		case SEARCH_SAVEDATESUPPORTED:
+			/* these want NILs to become NOT ALL */
+			return FALSE;
+
+		case SEARCH_ALL:
+		case SEARCH_NIL:
+		case SEARCH_HEADER:
+		case SEARCH_HEADER_ADDRESS:
+		case SEARCH_HEADER_COMPRESS_LWSP:
+		case SEARCH_BODY:
+		case SEARCH_TEXT:
+			/* these allow to remove NILs */
+			return TRUE;
+
+		case SEARCH_INTHREAD:
+		case SEARCH_SUB:
+		case SEARCH_OR:
+			/* these are handled in the caller as they need
+			   insight on the tree under that expression */
+			i_unreached();
+
+		default:
+			i_unreached();
+	}
+}
+
+static bool
+mail_search_args_handle_nils(struct mail_search_arg **argsp, bool *remove_nils_r) {
+	/* allow_remove + deny_remove + NILs count = args count */
+	int allow_remove = 0;
+	int deny_remove = 0;
+	bool changed = FALSE;
+
+	for (struct mail_search_arg *arg = *argsp; arg != NULL; arg = arg->next) {
+
+		switch(arg->type) {
+			case SEARCH_INTHREAD:
+			case SEARCH_SUB:
+			case SEARCH_OR: {
+				bool term_remove_nils;
+				if (mail_search_args_handle_nils(
+					&arg->value.subargs, &term_remove_nils))
+					changed = TRUE;
+
+				if (arg->value.subargs == NULL)
+					arg->type = SEARCH_NIL;
+				else if (term_remove_nils)
+				 	allow_remove++;
+				else
+					deny_remove++;
+				break;
+			}
+
+			case SEARCH_NIL:
+				break;
+
+			default:
+				if (mail_search_args_nils_removable(arg->type))
+					allow_remove++;
+				else
+					deny_remove++;
+		}
+	}
+
+	/* The NILs can be removed if either:
+	   (a) no other terms deny the removal
+	   (b) or at least one other term allows the removal
+	   otherwise, they are replaced with NOT ALL
+
+	   [DENY, NIL]        -> [DENY, NOT ALL] -- NIL replaced with NOT ALL
+	   [DENY, ALLOW, NIL] -> [DENY ALLOW]    -- NIL removed
+	   [ALLOW, NIL]       -> [ALLOW]         -- NIL removed
+	   [NIL]	      -> []              -- NIL removed */
+	bool remove_nils = deny_remove == 0 || allow_remove > 0;
+	if (remove_nils_r != NULL) *remove_nils_r = remove_nils;
+
+	while (*argsp != NULL) {
+		bool is_nil = (*argsp)->type == SEARCH_NIL;
+		if (is_nil && remove_nils) {
+			changed = TRUE;
+			*argsp = (*argsp)->next;
+		} else if (is_nil) {
+			changed = TRUE;
+			(*argsp)->type = SEARCH_ALL;
+			(*argsp)->match_not = TRUE;
+			argsp = &(*argsp)->next;
+		} else {
+			argsp = &(*argsp)->next;
+		}
+	}
+
+	return changed;
+}
+
+static bool
+mail_search_args_simplify_sub(struct mail_search_args *all_args, pool_t pool,
+			      struct mail_search_arg **argsp, bool parent_and)
+{
+	struct mail_search_simplify_ctx ctx;
+	struct mail_search_arg *sub, **all_argsp = argsp;
+	bool merged;
+
+	i_zero(&ctx);
+	ctx.initialized = all_args->init_refcount > 0;
+	ctx.parent_and = parent_and;
+	ctx.pool = pool_alloconly_create("mail search args simplify", 1024);
+	hash_table_create(&ctx.prev_args, ctx.pool, 0,
+			  mail_search_simplify_prev_arg_hash,
+			  mail_search_simplify_prev_arg_cmp);
+
+	while (*argsp != NULL) {
+		struct mail_search_arg *args = *argsp;
+
+		if (args->match_not && (args->type == SEARCH_SUB ||
+					args->type == SEARCH_OR)) {
+			/* neg(p and q and ..) == neg(p) or neg(q) or ..
+			   neg(p or q or ..) == neg(p) and neg(q) and .. */
+			args->type = args->type == SEARCH_SUB ?
+				SEARCH_OR : SEARCH_SUB;
+			args->match_not = FALSE;
+			sub = args->value.subargs;
+			do {
+				sub->match_not = !sub->match_not;
+				sub = sub->next;
+			} while (sub != NULL);
+		}
+
+		if ((args->type == SEARCH_SUB && parent_and) ||
+		    (args->type == SEARCH_OR && !parent_and) ||
+		    ((args->type == SEARCH_SUB || args->type == SEARCH_OR) &&
+		     args->value.subargs->next == NULL)) {
+			/* p and (q and ..) == p and q and ..
+			   p or (q or ..) == p or q or ..
+			   (p) = p */
+			sub = args->value.subargs;
+			for (; sub->next != NULL; sub = sub->next) ;
+			sub->next = args->next;
+			*args = *args->value.subargs;
+			ctx.removals = TRUE;
+			continue;
+		}
+
+		if (args->type == SEARCH_SUB ||
+		    args->type == SEARCH_OR ||
+		    args->type == SEARCH_INTHREAD) {
+			i_assert(!args->match_not);
+
+			if (args->type != SEARCH_INTHREAD) {
+				bool and_arg = args->type == SEARCH_SUB;
+
+				if (mail_search_args_simplify_drop_redundant_args(all_args, &args->value.subargs, and_arg))
+					ctx.removals = TRUE;
+				if (mail_search_args_simplify_extract_common(all_args, &args->value.subargs, pool, and_arg))
+					ctx.removals = TRUE;
+			}
+			if (mail_search_args_simplify_sub(all_args, pool, &args->value.subargs,
+							  args->type != SEARCH_OR))
+				ctx.removals = TRUE;
+		}
+		if (args->type == SEARCH_SEQSET ||
+		    args->type == SEARCH_UIDSET)
+			mail_search_args_simplify_set(args);
+
+		/* try to merge arguments */
+		merged = FALSE;
+		switch (args->type) {
+		case SEARCH_ALL: {
+			if (*all_argsp == args && args->next == NULL) {
+				/* this arg has no siblings - no merging */
+				break;
+			}
+			if ((parent_and && !args->match_not) ||
+			    (!parent_and && args->match_not)) {
+				/* .. AND ALL ..
+				   .. OR NOT ALL ..
+				   This arg is irrelevant -> drop */
+				merged = TRUE;
+				break;
+			}
+			/* .. AND NOT ALL ..
+			   .. OR ALL ..
+			   The other args are irrelevant -> drop them */
+			*all_argsp = args;
+			args->next = NULL;
+			ctx.removals = TRUE;
+			break;
+		}
+		case SEARCH_FLAGS:
+			merged = mail_search_args_merge_flags(&ctx, args);
+			break;
+		case SEARCH_KEYWORDS:
+			merged = mail_search_args_merge_keywords(&ctx, args);
+			break;
+		case SEARCH_SEQSET:
+		case SEARCH_UIDSET:
+			merged = mail_search_args_merge_set(&ctx, args);
+			break;
+		case SEARCH_BEFORE:
+		case SEARCH_ON:
+		case SEARCH_SINCE:
+			merged = mail_search_args_merge_time(&ctx, args);
+			break;
+		case SEARCH_SMALLER:
+		case SEARCH_LARGER:
+			merged = mail_search_args_merge_size(&ctx, args);
+			break;
+		case SEARCH_BODY:
+		case SEARCH_TEXT:
+			if (args->value.str[0] == '\0') {
+				/* BODY "" and TEXT "" matches everything */
+				args->type = SEARCH_ALL;
+				ctx.removals = TRUE;
+				break;
+			}
+			/* fall through */
+		case SEARCH_HEADER:
+		case SEARCH_HEADER_ADDRESS:
+		case SEARCH_HEADER_COMPRESS_LWSP:
+			merged = mail_search_args_merge_text(&ctx, args);
+			break;
+		default:
+			break;
+		}
+		if (merged) {
+			*argsp = args->next;
+			ctx.removals = TRUE;
+			continue;
+		}
+
+		argsp = &args->next;
+	}
+	hash_table_destroy(&ctx.prev_args);
+	pool_unref(&ctx.pool);
+	return ctx.removals;
+}
+
+static bool
+mail_search_args_simplify_merge_flags(struct mail_search_arg **argsp,
+				      bool parent_and)
+{
+	struct mail_search_arg *prev_flags = NULL;
+	bool removals = FALSE;
+
+	while (*argsp != NULL) {
+		struct mail_search_arg *args = *argsp;
+
+		if (args->type == SEARCH_SUB ||
+		    args->type == SEARCH_OR ||
+		    args->type == SEARCH_INTHREAD) {
+			if (mail_search_args_simplify_merge_flags(&args->value.subargs,
+								  args->type != SEARCH_OR))
+				removals = TRUE;
+		} else if (args->type != SEARCH_FLAGS) {
+			/* ignore non-flags */
+		} else if (!((!args->match_not && parent_and) ||
+			   (args->match_not && !parent_and))) {
+			/* can't merge these flags args */
+		} else if (prev_flags == NULL) {
+			/* first flags arg */
+			prev_flags = args;
+		} else {
+			/* merge to previous arg */
+			prev_flags->value.flags |= args->value.flags;
+			*argsp = args->next;
+			removals = TRUE;
+			continue;
+		}
+		argsp = &args->next;
+	}
+	return removals;
+}
+
+static bool
+mail_search_args_unnest_inthreads(struct mail_search_args *args,
+				  struct mail_search_arg **argp,
+				  bool parent_inthreads, bool parent_and)
+{
+	struct mail_search_arg *arg, *thread_arg, *or_arg;
+	bool child_inthreads = FALSE, non_inthreads = FALSE;
+
+	for (arg = *argp; arg != NULL; arg = arg->next) {
+		switch (arg->type) {
+		case SEARCH_SUB:
+		case SEARCH_OR:
+			if (!mail_search_args_unnest_inthreads(args,
+					&arg->value.subargs, parent_inthreads,
+					arg->type != SEARCH_OR)) {
+				arg->result = 1;
+				child_inthreads = TRUE;
+			} else {
+				arg->result = 0;
+				non_inthreads = TRUE;
+			}
+			break;
+		case SEARCH_INTHREAD:
+			if (mail_search_args_unnest_inthreads(args,
+					&arg->value.subargs, TRUE, TRUE)) {
+				/* children converted to SEARCH_INTHREADs */
+				arg->type = SEARCH_SUB;
+			}
+			args->have_inthreads = TRUE;
+			arg->result = 1;
+			child_inthreads = TRUE;
+			break;
+		default:
+			arg->result = 0;
+			non_inthreads = TRUE;
+			break;
+		}
+	}
+
+	if (!parent_inthreads || !child_inthreads || !non_inthreads)
+		return FALSE;
+
+	/* put all non-INTHREADs under a single INTHREAD */
+	thread_arg = p_new(args->pool, struct mail_search_arg, 1);
+	thread_arg->type = SEARCH_INTHREAD;
+
+	while (*argp != NULL) {
+		arg = *argp;
+		argp = &(*argp)->next;
+
+		if (arg->result == 0) {
+			/* not an INTHREAD or a SUB/OR with only INTHREADs */
+			arg->next = thread_arg->value.subargs;
+			thread_arg->value.subargs = arg;
+		}
+	}
+	if (!parent_and) {
+		/* We want to OR the args */
+		or_arg = p_new(args->pool, struct mail_search_arg, 1);
+		or_arg->type = SEARCH_OR;
+		or_arg->value.subargs = thread_arg->value.subargs;
+		thread_arg->value.subargs = or_arg;
+	}
+	return TRUE;
+}
+
+void mail_search_args_simplify(struct mail_search_args *args)
+{
+	args->simplified = TRUE;
+
+	bool removals = mail_search_args_handle_nils(&args->args, NULL);
+	if (mail_search_args_simplify_sub(args, args->pool, &args->args, TRUE))
+		removals = TRUE;
+	if (mail_search_args_unnest_inthreads(args, &args->args,
+					      FALSE, TRUE)) {
+		/* we may have added some extra SUBs that could be dropped */
+		if (mail_search_args_simplify_sub(args, args->pool, &args->args, TRUE))
+			removals = TRUE;
+	}
+	do {
+		if (mail_search_args_simplify_drop_redundant_args(args, &args->args, TRUE))
+			removals = TRUE;
+		if (mail_search_args_simplify_extract_common(args, &args->args, args->pool, TRUE))
+			removals = TRUE;
+		if (removals)
+			removals = mail_search_args_simplify_sub(args, args->pool, &args->args, TRUE);
+		/* do the flag merging into a single arg only at the end.
+		   up until then they're treated as any other search args,
+		   which simplifies their handling. after the flags merging is
+		   done, further simplifications are still possible. */
+		if (mail_search_args_simplify_merge_flags(&args->args, TRUE))
+			removals = TRUE;
+	} while (removals);
+}