src/lib-storage/mail-search-args-simplify.c

	mail-search-args-simplify.c revision 1270cb6b6139001b0a89f595ad0868b1f3a0af45
2e37d45867d081db150ab78dad303b9077aea24fTimo Sirainen/* Copyright (c) 2002-2017 Dovecot authors, see the included COPYING file */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
46552a931924c2d743f045e95b08c3ce6beda91aTimo Sirainen#include "lib.h"
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen#include "array.h"
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen#include "hash.h"
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen#include "mail-search.h"
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstruct mail_search_simplify_prev_arg {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        enum mail_search_arg_type type;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        enum mail_search_arg_flag search_flags;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        enum mail_search_date_type date_type;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        enum mail_flags mail_flags;
53dfcefa9440a49d703e49193819a79be99c9ba6Timo Sirainen        bool match_not;
2ef0e8ee48c9683f7bd6698798efa3328e4322d1Timo Sirainen        bool fuzzy;
53dfcefa9440a49d703e49193819a79be99c9ba6Timo Sirainen    } bin_mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    const char *hdr_field_name_mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    const char *str_mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen    struct mail_search_arg *prev_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen};
660b99a7059824676b2b8d6f79b8e15d47df25a2Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstruct mail_search_simplify_ctx {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    pool_t pool;
2e78f05b11df23ec2731afaf8f19d5b5240cb29fTimo Sirainen    /* arg mask => prev_arg */
2e78f05b11df23ec2731afaf8f19d5b5240cb29fTimo Sirainen    HASH_TABLE(struct mail_search_simplify_prev_arg *,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen           struct mail_search_simplify_prev_arg *) prev_args;
d1e7425048c61d71f41f737ba947687198842dc2Timo Sirainen    bool parent_and;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    bool removals;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    bool initialized;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen};
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic int
660b99a7059824676b2b8d6f79b8e15d47df25a2Timo Sirainenmail_search_simplify_prev_arg_cmp(const struct mail_search_simplify_prev_arg *arg1,
660b99a7059824676b2b8d6f79b8e15d47df25a2Timo Sirainen                  const struct mail_search_simplify_prev_arg *arg2)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    int ret;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    ret = memcmp(&arg1->bin_mask, &arg2->bin_mask, sizeof(arg1->bin_mask));
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen    if (ret == 0)
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen        ret = null_strcmp(arg1->hdr_field_name_mask, arg2->hdr_field_name_mask);
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen    if (ret == 0)
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen        ret = null_strcmp(arg1->str_mask, arg2->str_mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return ret;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic unsigned int
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_simplify_prev_arg_hash(const struct mail_search_simplify_prev_arg *arg)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    unsigned int hash;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    hash = mem_hash(&arg->bin_mask, sizeof(arg->bin_mask));
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (arg->hdr_field_name_mask != NULL)
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen        hash ^= str_hash(arg->hdr_field_name_mask);
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen    if (arg->str_mask != NULL)
b9c76fe9d9ca194816606342da1ddbd9be6bc8abTimo Sirainen        hash ^= str_hash(arg->str_mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return hash;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic void mail_search_arg_get_base_mask(const struct mail_search_arg *arg,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                      struct mail_search_simplify_prev_arg *mask_r)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    i_zero(mask_r);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask_r->bin_mask.type = arg->type;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask_r->bin_mask.fuzzy = arg->fuzzy;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask_r->bin_mask.search_flags = arg->value.search_flags;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic struct mail_search_arg **
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_args_simplify_get_prev_argp(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                    const struct mail_search_simplify_prev_arg *mask)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_simplify_prev_arg *prev_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    prev_arg = hash_table_lookup(ctx->prev_args, mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (prev_arg == NULL) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        prev_arg = p_new(ctx->pool, struct mail_search_simplify_prev_arg, 1);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        prev_arg->bin_mask = mask->bin_mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        prev_arg->hdr_field_name_mask =
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            p_strdup(ctx->pool, mask->hdr_field_name_mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        prev_arg->str_mask =
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            p_strdup(ctx->pool, mask->str_mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        hash_table_insert(ctx->prev_args, prev_arg, prev_arg);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return &prev_arg->prev_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_args_merge_mask(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                struct mail_search_arg *args,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                const struct mail_search_simplify_prev_arg *mask)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_arg **prev_argp;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, mask);
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen    if (*prev_argp == NULL) {
6303191abcb37164f435ccdc56e9dbddf1288851Timo Sirainen        *prev_argp = args;
6303191abcb37164f435ccdc56e9dbddf1288851Timo Sirainen        return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (ctx->initialized)
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen        mail_search_arg_one_deinit(args);
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen    if ((*prev_argp)->match_not != args->match_not) {
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen        /* a && !a = 0 */
5a250816ffc4cc5db203f9410ea99b6601c7b91aTimo Sirainen        if (ctx->initialized)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            mail_search_arg_one_deinit(*prev_argp);
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen        (*prev_argp)->type = SEARCH_ALL;
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen        (*prev_argp)->match_not = ctx->parent_and;
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen    }
1bf5c6c20f3d51f13d3240cfb46e471074c86276Timo Sirainen    /* duplicate keyword. */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e5acc283bf030b0b5c79ca4e52d315c516a299faPascal Volkstatic bool mail_search_args_merge_flags(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                     struct mail_search_arg *args)
2e2a1d720ed53490e8e5c5031e773d395bd5683dTimo Sirainen{
5a250816ffc4cc5db203f9410ea99b6601c7b91aTimo Sirainen    struct mail_search_simplify_prev_arg mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask.bin_mask.mail_flags = args->value.flags;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return mail_search_args_merge_mask(ctx, args, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_args_merge_keywords(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                struct mail_search_arg *args)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_simplify_prev_arg mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask.str_mask = args->value.str;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return mail_search_args_merge_mask(ctx, args, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic void mail_search_args_simplify_set(struct mail_search_arg *args)
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen{
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen    const struct seq_range *seqset;
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen    unsigned int count;
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen    if (args->match_not) {
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen        /* invert the set to drop the NOT. Note that (uint32_t)-1
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen           matches the last existing mail, which we don't know at this
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen           point. lib-imap/imap-seqset.c has similar code that
b8afdaa1bffe2f27cd4b02bf3bfbd2d297c8e648Timo Sirainen           disallows using (uint32_t)-1 as a real UID. */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (seq_range_exists(&args->value.seqset, (uint32_t)-1))
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            return;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        args->match_not = FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        seq_range_array_invert(&args->value.seqset, 1, (uint32_t)-2);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    seqset = array_get(&args->value.seqset, &count);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (count == 1 && seqset->seq1 == 1 && seqset->seq2 >= (uint32_t)-2) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        /* 1:* is the same as ALL. */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        args->type = SEARCH_ALL;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    } else if (count == 0) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        /* empty set is the same as NOT ALL. this is mainly coming
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen           from mail_search_args_merge_set() intersection. */
ec23e16ed879e289d12c6e1a5f9745dd3979004aTimo Sirainen        args->type = SEARCH_ALL;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        args->match_not = TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool mail_search_args_merge_set(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                       struct mail_search_arg *args)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_simplify_prev_arg mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_arg **prev_argp;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (args->match_not) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        /* "*" used - can't simplify it */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask.bin_mask.match_not = args->match_not;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (*prev_argp == NULL) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        *prev_argp = args;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    } else if (ctx->parent_and) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        seq_range_array_intersect(&(*prev_argp)->value.seqset,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                      &args->value.seqset);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    } else {
53dfcefa9440a49d703e49193819a79be99c9ba6Timo Sirainen        seq_range_array_merge(&(*prev_argp)->value.seqset,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                      &args->value.seqset);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool mail_search_args_merge_time(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                    struct mail_search_arg *args)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
660b99a7059824676b2b8d6f79b8e15d47df25a2Timo Sirainen    struct mail_search_simplify_prev_arg mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_arg **prev_argp, *prev_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen    mail_search_arg_get_base_mask(args, &mask);
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen    mask.bin_mask.match_not = args->match_not;
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen    mask.bin_mask.date_type = args->value.date_type;
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen    if (*prev_argp == NULL) {
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen        *prev_argp = args;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    prev_arg = *prev_argp;
77f1da4b5e2b800197d8db548235497d5e9d6a4fTimo Sirainen    switch (args->type) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    case SEARCH_BEFORE:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (ctx->parent_and) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            if (prev_arg->value.time < args->value.time) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg < 5 AND arg < 10 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg < 10 AND arg < 5 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                prev_arg->value.time = args->value.time;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            if (prev_arg->value.time < args->value.time) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg < 5 OR arg < 10 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                prev_arg->value.time = args->value.time;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg < 10 OR arg < 5 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    case SEARCH_ON:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (prev_arg->value.time == args->value.time)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    case SEARCH_SINCE:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (ctx->parent_and) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            if (prev_arg->value.time < args->value.time) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg >= 5 AND arg >= 10 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                prev_arg->value.time = args->value.time;
18f1bbf05980d3c53ecae81b62574212f0891522Timo Sirainen            } else {
77f1da4b5e2b800197d8db548235497d5e9d6a4fTimo Sirainen                /* prev_arg >= 10 AND arg >= 5 */
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen            }
77f1da4b5e2b800197d8db548235497d5e9d6a4fTimo Sirainen        } else {
18f1bbf05980d3c53ecae81b62574212f0891522Timo Sirainen            if (prev_arg->value.time < args->value.time) {
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen                /* prev_arg >= 5 OR arg >= 10 */
75e46142d8fbac811df8f2ca58d9a2f48a75d65fTimo Sirainen            } else {
77f1da4b5e2b800197d8db548235497d5e9d6a4fTimo Sirainen                /* prev_arg >= 10 OR arg >= 5 */
18f1bbf05980d3c53ecae81b62574212f0891522Timo Sirainen                prev_arg->value.time = args->value.time;
18f1bbf05980d3c53ecae81b62574212f0891522Timo Sirainen            }
18f1bbf05980d3c53ecae81b62574212f0891522Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    default:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        break;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool mail_search_args_merge_size(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                    struct mail_search_arg *args)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_simplify_prev_arg mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_arg **prev_argp, *prev_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen    mask.bin_mask.match_not = args->match_not;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (*prev_argp == NULL) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        *prev_argp = args;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    prev_arg = *prev_argp;
53dfcefa9440a49d703e49193819a79be99c9ba6Timo Sirainen    switch (args->type) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    case SEARCH_SMALLER:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (ctx->parent_and) {
04b7dc631f33bf61f273138c679da9bd0910fb6dTimo Sirainen            if (prev_arg->value.size < args->value.size) {
04b7dc631f33bf61f273138c679da9bd0910fb6dTimo Sirainen                /* prev_arg < 5 AND arg < 10 */
04b7dc631f33bf61f273138c679da9bd0910fb6dTimo Sirainen            } else {
04b7dc631f33bf61f273138c679da9bd0910fb6dTimo Sirainen                /* prev_arg < 10 AND arg < 5 */
04b7dc631f33bf61f273138c679da9bd0910fb6dTimo Sirainen                prev_arg->value.size = args->value.size;
04b7dc631f33bf61f273138c679da9bd0910fb6dTimo Sirainen            }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            if (prev_arg->value.size < args->value.size) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg < 5 OR arg < 10 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                prev_arg->value.size = args->value.size;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg < 10 OR arg < 5 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    case SEARCH_LARGER:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (ctx->parent_and) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            if (prev_arg->value.size < args->value.size) {
53dfcefa9440a49d703e49193819a79be99c9ba6Timo Sirainen                /* prev_arg >= 5 AND arg >= 10 */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                prev_arg->value.size = args->value.size;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* prev_arg >= 10 AND arg >= 5 */
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen            }
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen        } else {
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen            if (prev_arg->value.size < args->value.size) {
2ef0e8ee48c9683f7bd6698798efa3328e4322d1Timo Sirainen                /* prev_arg >= 5 OR arg >= 10 */
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen            } else {
6303191abcb37164f435ccdc56e9dbddf1288851Timo Sirainen                /* prev_arg >= 10 OR arg >= 5 */
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen                prev_arg->value.size = args->value.size;
2598b2f36365b52d9754b9348a5be29569293e46Timo Sirainen            }
2ef0e8ee48c9683f7bd6698798efa3328e4322d1Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        return TRUE;
53dfcefa9440a49d703e49193819a79be99c9ba6Timo Sirainen    default:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        break;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool mail_search_args_merge_text(struct mail_search_simplify_ctx *ctx,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                    struct mail_search_arg *args)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_simplify_prev_arg mask;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask.hdr_field_name_mask = args->hdr_field_name;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    mask.str_mask = args->value.str;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return mail_search_args_merge_mask(ctx, args, &mask);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_args_have_equal(const struct mail_search_arg *args,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                const struct mail_search_arg *wanted_arg)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    const struct mail_search_arg *arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    for (arg = args; arg != NULL; arg = arg->next) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (mail_search_arg_one_equals(arg, wanted_arg))
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
660b99a7059824676b2b8d6f79b8e15d47df25a2Timo Sirainen    return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_args_remove_equal(struct mail_search_args *all_args,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                  struct mail_search_arg **argsp,
decb23442f9e6cd5c4845a9cb162029b8c6d5f0fTimo Sirainen                  const struct mail_search_arg *wanted_arg,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                  bool check_subs)
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen{
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen    struct mail_search_arg **argp;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen    bool found = FALSE;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen    for (argp = argsp; (*argp) != NULL; ) {
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen        if (mail_search_arg_one_equals(*argp, wanted_arg)) {
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            if (all_args->init_refcount > 0)
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen                mail_search_arg_one_deinit(*argp);
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            *argp = (*argp)->next;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            found = TRUE;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen        } else if (check_subs) {
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            i_assert((*argp)->type == SEARCH_SUB ||
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen                 (*argp)->type == SEARCH_OR);
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            if (!mail_search_args_remove_equal(all_args, &(*argp)->value.subargs, wanted_arg, FALSE)) {
decb23442f9e6cd5c4845a9cb162029b8c6d5f0fTimo Sirainen                /* we already verified that this should have
decb23442f9e6cd5c4845a9cb162029b8c6d5f0fTimo Sirainen                   existed. */
7fa573e6ea36024f618492e7d3649a69c1b41028Timo Sirainen                i_unreached();
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            }
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            if ((*argp)->value.subargs == NULL)
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen                *argp = (*argp)->next;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            else
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen                argp = &(*argp)->next;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            found = TRUE;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen        } else {
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            argp = &(*argp)->next;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen        }
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return found;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen}
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainenstatic bool
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainenmail_search_args_have_all_equal(struct mail_search_arg *parent_arg,
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen                const struct mail_search_arg *wanted_args)
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen{
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen    const struct mail_search_arg *arg;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen    i_assert(parent_arg->type == SEARCH_SUB ||
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen         parent_arg->type == SEARCH_OR);
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    for (arg = wanted_args; arg != NULL; arg = arg->next) {
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen        if (!mail_search_args_have_equal(parent_arg->value.subargs, arg))
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            return FALSE;
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen    }
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen    return TRUE;
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen}
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainenstatic unsigned int
8bb360f9e5de1c25e4f875205bb06e8bf15dae14Timo Sirainenmail_search_args_count(const struct mail_search_arg *args)
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen{
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen    unsigned int count;
6998ca95b4947c90647ac5d4794ebd6311acada2Timo Sirainen
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen    for (count = 0; args != NULL; count++)
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen        args = args->next;
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen    return count;
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen}
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainenstatic bool
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainenmail_search_args_simplify_drop_redundant_args(struct mail_search_args *all_args,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                          struct mail_search_arg **argsp,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                          bool and_arg)
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen{
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    struct mail_search_arg *arg, **argp, one_arg, *lowest_arg = NULL;
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    enum mail_search_arg_type child_subargs_type;
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    unsigned int count, lowest_count = UINT_MAX;
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    bool ret = FALSE;
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    if (*argsp == NULL)
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen        return FALSE;
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    /* find the arg which has the lowest number of child args */
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen    for (arg = *argsp; arg != NULL; arg = arg->next) {
4c6ddf2491104f917d00e6900e833e80ea02c7b6Timo Sirainen        if (arg->type != child_subargs_type) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            one_arg = *arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            one_arg.next = NULL;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            lowest_arg = &one_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            break;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        count = mail_search_args_count(arg->value.subargs);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (count < lowest_count) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            lowest_arg = arg->value.subargs;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            lowest_count = count;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    i_assert(lowest_arg != NULL);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    /* if there are any args that include lowest_arg, drop the arg since
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       it's redundant. (non-SUB duplicates are dropped elsewhere.) */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    for (argp = argsp; *argp != NULL; ) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (*argp != lowest_arg && (*argp)->type == child_subargs_type &&
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            (*argp)->value.subargs != lowest_arg &&
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            mail_search_args_have_all_equal(*argp, lowest_arg)) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            if (all_args->init_refcount > 0)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                mail_search_arg_one_deinit(*argp);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            *argp = (*argp)->next;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            ret = TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            argp = &(*argp)->next;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return ret;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_args_simplify_extract_common(struct mail_search_args *all_args,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                     struct mail_search_arg **argsp,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                     pool_t pool, bool and_arg)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    /* Simple SUB example:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       (a AND b) OR (a AND c) -> a AND (b OR c)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       More complicated example:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       (c1 AND c2 AND u1 AND u2) OR (c1 AND c2 AND u3 AND u4) ->
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       c1 AND c2 AND ((u1 AND u2) OR (u3 AND u4))
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       Similarly for ORs:
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       (a OR b) AND (a OR c) -> a OR (b AND c)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
660b99a7059824676b2b8d6f79b8e15d47df25a2Timo Sirainen       (c1 OR c2 OR u1 OR u2) AND (c1 OR c2 OR u3 OR u4) ->
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen       c1 OR c2 OR ((u1 OR u2) AND (u3 OR u4))
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen    */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_arg *arg, *sub_arg, *sub_next;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_arg *new_arg, *child_arg, *common_args = NULL;
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen    enum mail_search_arg_type child_subargs_type;
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (*argsp == NULL || (*argsp)->next == NULL) {
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen        /* single arg, nothing to extract */
0348172a5278d1f5aa2440f30346c390ddc17318Timo Sirainen        return FALSE;
0348172a5278d1f5aa2440f30346c390ddc17318Timo Sirainen    }
cb2c44f33d9d48f58e4c5e42ba2526a0c100218aTimo Sirainen
0348172a5278d1f5aa2440f30346c390ddc17318Timo Sirainen    child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
0348172a5278d1f5aa2440f30346c390ddc17318Timo Sirainen
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen    /* find the first arg with child_subargs_type */
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen    for (arg = *argsp; arg != NULL; arg = arg->next) {
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen        if (arg->type == child_subargs_type)
7a23d586f07ec376e28e8f6f3f3392a4ac8b83bbTimo Sirainen            break;
3b22894b8805b186c73d8b754001e8d7e944be85Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    if (arg == NULL)
46ec792dd4ccf6c34706c4774228301fafde6aa9Timo Sirainen        return FALSE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    for (sub_arg = arg->value.subargs; sub_arg != NULL; sub_arg = sub_next) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        sub_next = sub_arg->next;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
decb23442f9e6cd5c4845a9cb162029b8c6d5f0fTimo Sirainen        /* check if sub_arg is found from all the args */
decb23442f9e6cd5c4845a9cb162029b8c6d5f0fTimo Sirainen        for (arg = *argsp; arg != NULL; arg = arg->next) {
a75907609d7c410c9e17beedfafbf28b4439fa8aTimo Sirainen            if (mail_search_arg_one_equals(arg, sub_arg)) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* the whole arg matches */
6998ca95b4947c90647ac5d4794ebd6311acada2Timo Sirainen            } else if (arg->type == child_subargs_type &&
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                   mail_search_args_have_equal(arg->value.subargs, sub_arg)) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                /* exists as subarg */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                break;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        }
ec23e16ed879e289d12c6e1a5f9745dd3979004aTimo Sirainen        if (arg != NULL)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            continue;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        /* extract the arg and put it to common_args */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        mail_search_args_remove_equal(all_args, argsp, sub_arg, TRUE);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        sub_arg->next = common_args;
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen        common_args = sub_arg;
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen    }
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen    if (common_args == NULL)
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen        return FALSE;
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen    /* replace all the original args with a single new SUB/OR arg */
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen    new_arg = p_new(pool, struct mail_search_arg, 1);
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen    new_arg->type = child_subargs_type;
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen    if (*argsp == NULL) {
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen        /* there are only common args */
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen        new_arg->value.subargs = common_args;
d3a7d023b47d2a137f01109e7b38702dca3f11d3Timo Sirainen    } else {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        /* replace OR arg with AND(OR(non_common_args), common_args)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen           or
5a250816ffc4cc5db203f9410ea99b6601c7b91aTimo Sirainen           replace AND arg with OR(AND(non_common_args), common_args) */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        child_arg = p_new(pool, struct mail_search_arg, 1);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        child_arg->type = and_arg ? SEARCH_SUB : SEARCH_OR;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        child_arg->value.subargs = *argsp;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        child_arg->next = common_args;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        new_arg->value.subargs = child_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    *argsp = new_arg;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    return TRUE;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen}
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenstatic bool
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainenmail_search_args_simplify_sub(struct mail_search_args *all_args, pool_t pool,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                  struct mail_search_arg **argsp, bool parent_and)
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen{
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_simplify_ctx ctx;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    struct mail_search_arg *sub, **all_argsp = argsp;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    bool merged;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    i_zero(&ctx);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    ctx.initialized = all_args->init_refcount > 0;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    ctx.parent_and = parent_and;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    ctx.pool = pool_alloconly_create("mail search args simplify", 1024);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    hash_table_create(&ctx.prev_args, ctx.pool, 0,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen              mail_search_simplify_prev_arg_hash,
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen              mail_search_simplify_prev_arg_cmp);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen    while (*argsp != NULL) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        struct mail_search_arg *args = *argsp;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if (args->match_not && (args->type == SEARCH_SUB ||
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                    args->type == SEARCH_OR)) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            /* neg(p and q and ..) == neg(p) or neg(q) or ..
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen               neg(p or q or ..) == neg(p) and neg(q) and .. */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            args->type = args->type == SEARCH_SUB ?
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen                SEARCH_OR : SEARCH_SUB;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            args->match_not = FALSE;
80e461e945dd4d5b0d08535413176cf1756e8523Timo Sirainen            sub = args->value.subargs;
80e461e945dd4d5b0d08535413176cf1756e8523Timo Sirainen            do {
80e461e945dd4d5b0d08535413176cf1756e8523Timo Sirainen                sub->match_not = !sub->match_not;
80e461e945dd4d5b0d08535413176cf1756e8523Timo Sirainen                sub = sub->next;
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            } while (sub != NULL);
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        }
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen        if ((args->type == SEARCH_SUB && parent_and) ||
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            (args->type == SEARCH_OR && !parent_and) ||
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            ((args->type == SEARCH_SUB || args->type == SEARCH_OR) &&
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen             args->value.subargs->next == NULL)) {
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            /* p and (q and ..) == p and q and ..
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen               p or (q or ..) == p or q or ..
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen               (p) = p */
e248fe370c4047cee921a91b48edc37944ab0526Timo Sirainen            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)
{
    bool removals;

    args->simplified = TRUE;

    removals = mail_search_args_simplify_sub(args, args->pool, &args->args, 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);
}