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

	mail-search-args-simplify.c revision 9432496e6b190b839622a391a15788c41e5d95d3
76b43e4417bab52e913da39b5f5bc2a130d3f149Timo Sirainen/* Copyright (c) 2002-2016 Dovecot authors, see the included COPYING file */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen#include "lib.h"
b44650b0f48a4b5f0dc240ed836833a00b643b9fTimo Sirainen#include "array.h"
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen#include "hash.h"
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen#include "mail-search.h"
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstruct mail_search_simplify_prev_arg {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        enum mail_search_arg_type type;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        enum mail_search_arg_flag search_flags;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        enum mail_search_date_type date_type;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        bool match_not;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        bool fuzzy;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    } bin_mask;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    const char *hdr_field_name_mask;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    const char *str_mask;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_arg *prev_arg;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen};
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstruct mail_search_simplify_ctx {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    pool_t pool;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    /* arg mask => prev_arg */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    HASH_TABLE(struct mail_search_simplify_prev_arg *,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen           struct mail_search_simplify_prev_arg *) prev_args;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    bool parent_and;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    bool removals;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen};
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstatic int
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenmail_search_simplify_prev_arg_cmp(const struct mail_search_simplify_prev_arg *arg1,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                  const struct mail_search_simplify_prev_arg *arg2)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    int ret;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    ret = memcmp(&arg1->bin_mask, &arg2->bin_mask, sizeof(arg1->bin_mask));
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (ret == 0)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        ret = null_strcmp(arg1->hdr_field_name_mask, arg2->hdr_field_name_mask);
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen    if (ret == 0)
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        ret = null_strcmp(arg1->str_mask, arg2->str_mask);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return ret;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstatic unsigned int
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenmail_search_simplify_prev_arg_hash(const struct mail_search_simplify_prev_arg *arg)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    unsigned int hash;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    hash = mem_hash(&arg->bin_mask, sizeof(arg->bin_mask));
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (arg->hdr_field_name_mask != NULL)
9398c0935613ba038cf2275ff66c43b25092cfd0Timo Sirainen        hash ^= str_hash(arg->hdr_field_name_mask);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (arg->str_mask != NULL)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        hash ^= str_hash(arg->str_mask);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return hash;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainenstatic void mail_search_arg_get_base_mask(const struct mail_search_arg *arg,
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen                      struct mail_search_simplify_prev_arg *mask_r)
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen{
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen    memset(mask_r, 0, sizeof(*mask_r));
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen    mask_r->bin_mask.type = arg->type;
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen    mask_r->bin_mask.match_not = arg->match_not;
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen    mask_r->bin_mask.fuzzy = arg->fuzzy;
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen    mask_r->bin_mask.search_flags = arg->value.search_flags;
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen}
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainen
7569ab8537418b7fc369265f26595b0ef9e4cb35Timo Sirainenstatic struct mail_search_arg **
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenmail_search_args_simplify_get_prev_argp(struct mail_search_simplify_ctx *ctx,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                    const struct mail_search_simplify_prev_arg *mask)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_simplify_prev_arg *prev_arg;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen    prev_arg = hash_table_lookup(ctx->prev_args, mask);
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen    if (prev_arg == NULL) {
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen        prev_arg = p_new(ctx->pool, struct mail_search_simplify_prev_arg, 1);
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen        prev_arg->bin_mask = mask->bin_mask;
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen        prev_arg->hdr_field_name_mask =
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen            p_strdup(ctx->pool, mask->hdr_field_name_mask);
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen        prev_arg->str_mask =
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen            p_strdup(ctx->pool, mask->str_mask);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        hash_table_insert(ctx->prev_args, prev_arg, prev_arg);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return &prev_arg->prev_arg;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstatic bool mail_search_args_merge_flags(struct mail_search_simplify_ctx *ctx,
47bb4a7615c85f212f061499f04f121d6d625387Timo Sirainen                     struct mail_search_arg *args)
47bb4a7615c85f212f061499f04f121d6d625387Timo Sirainen{
47bb4a7615c85f212f061499f04f121d6d625387Timo Sirainen    struct mail_search_simplify_prev_arg mask;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_arg **prev_argp;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (!((!args->match_not && ctx->parent_and) ||
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen          (args->match_not && !ctx->parent_and)))
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen        return FALSE;
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen    mail_search_arg_get_base_mask(args, &mask);
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen    if (*prev_argp == NULL) {
3d370bb6763ac4af4a0d143ad7c93300d5ddff89Timo Sirainen        *prev_argp = args;
3d370bb6763ac4af4a0d143ad7c93300d5ddff89Timo Sirainen        return FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    } else {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        (*prev_argp)->value.flags |= args->value.flags;
ce89e2964b6bc4925d2dd690417200a110d041c5Timo Sirainen        return TRUE;
d89def103cc172eac305e0fb733e89f11dae40b5Timo Sirainen    }
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen}
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainenstatic void mail_search_args_simplify_set(struct mail_search_arg *args)
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen{
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen    const struct seq_range *seqset;
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen    unsigned int count;
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen    if (args->match_not) {
5d4855d7b4dcffb6975ed8e3c9c376dac74e5c8aTimo Sirainen        /* invert the set to drop the NOT */
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen        args->match_not = FALSE;
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen        seq_range_array_invert(&args->value.seqset, 1, (uint32_t)-1);
fc8d5f0ac909cca77840538e8beef98a8d40c21cTimo Sirainen    }
5d4855d7b4dcffb6975ed8e3c9c376dac74e5c8aTimo Sirainen    seqset = array_get(&args->value.seqset, &count);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (count == 1 && seqset->seq1 == 1 && seqset->seq2 == (uint32_t)-1) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        /* 1:* is the same as ALL. */
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen        args->type = SEARCH_ALL;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen    } else if (count == 0) {
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen        /* empty set is the same as NOT ALL. this is mainly coming
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen           from mail_search_args_merge_set() intersection. */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        args->type = SEARCH_ALL;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        args->match_not = TRUE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstatic bool mail_search_args_merge_set(struct mail_search_simplify_ctx *ctx,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                       struct mail_search_arg *args)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen    struct mail_search_simplify_prev_arg mask;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_arg **prev_argp;
8eb94c5190ba09bb6f6f068eec7bf96750f08d1dTimo Sirainen
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    i_assert(!args->match_not);
8eb94c5190ba09bb6f6f068eec7bf96750f08d1dTimo Sirainen
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    if (*prev_argp == NULL) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        *prev_argp = args;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        return FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    } else if (ctx->parent_and) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        seq_range_array_intersect(&(*prev_argp)->value.seqset,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                      &args->value.seqset);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return TRUE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    } else {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        seq_range_array_merge(&(*prev_argp)->value.seqset,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                      &args->value.seqset);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return TRUE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen}
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainenstatic bool mail_search_args_merge_time(struct mail_search_simplify_ctx *ctx,
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen                    struct mail_search_arg *args)
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen{
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen    struct mail_search_simplify_prev_arg mask;
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen    struct mail_search_arg **prev_argp, *prev_arg;
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen    mask.bin_mask.date_type = args->value.date_type;
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen    if (*prev_argp == NULL) {
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen        *prev_argp = args;
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen        return FALSE;
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen    }
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen
8eb94c5190ba09bb6f6f068eec7bf96750f08d1dTimo Sirainen    prev_arg = *prev_argp;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen    switch (args->type) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    case SEARCH_BEFORE:
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        if (ctx->parent_and) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            if (prev_arg->value.time < args->value.time) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen                /* prev_arg < 5 AND arg < 10 */
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen            } else {
adc409a7ac9689d3baf811712ad5a5432cab2d87Timo Sirainen                /* prev_arg < 10 AND arg < 5 */
b321df9603081896b70ec44635af96d674a9839aTimo Sirainen                prev_arg->value.time = args->value.time;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        } else {
f968e62caa52a8924bd05ebf76ff515b5c18e17bTimo Sirainen            if (prev_arg->value.time < args->value.time) {
b44650b0f48a4b5f0dc240ed836833a00b643b9fTimo Sirainen                /* prev_arg < 5 OR arg < 10 */
b44650b0f48a4b5f0dc240ed836833a00b643b9fTimo Sirainen                prev_arg->value.time = args->value.time;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            } else {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                /* prev_arg < 10 OR arg < 5 */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return TRUE;
47bb4a7615c85f212f061499f04f121d6d625387Timo Sirainen    case SEARCH_ON:
47bb4a7615c85f212f061499f04f121d6d625387Timo Sirainen        if (prev_arg->value.time == args->value.time)
47bb4a7615c85f212f061499f04f121d6d625387Timo Sirainen            return TRUE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    case SEARCH_SINCE:
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        if (ctx->parent_and) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            if (prev_arg->value.time < args->value.time) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                /* prev_arg >= 5 AND arg >= 10 */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                prev_arg->value.time = args->value.time;
b44650b0f48a4b5f0dc240ed836833a00b643b9fTimo Sirainen            } else {
b44650b0f48a4b5f0dc240ed836833a00b643b9fTimo Sirainen                /* prev_arg >= 10 AND arg >= 5 */
b44650b0f48a4b5f0dc240ed836833a00b643b9fTimo Sirainen            }
b44650b0f48a4b5f0dc240ed836833a00b643b9fTimo Sirainen        } else {
137ea7ca34005345aa2304a940149b7f3774d727Timo Sirainen            if (prev_arg->value.time < args->value.time) {
137ea7ca34005345aa2304a940149b7f3774d727Timo Sirainen                /* prev_arg >= 5 OR arg >= 10 */
137ea7ca34005345aa2304a940149b7f3774d727Timo Sirainen            } else {
137ea7ca34005345aa2304a940149b7f3774d727Timo Sirainen                /* prev_arg >= 10 OR arg >= 5 */
137ea7ca34005345aa2304a940149b7f3774d727Timo Sirainen                prev_arg->value.time = args->value.time;
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen            }
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen        }
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen        return TRUE;
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen    default:
4376643cd2c7110e752c09f838f2c4eee6ed8ac6Timo Sirainen        break;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainenstatic bool mail_search_args_merge_size(struct mail_search_simplify_ctx *ctx,
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen                    struct mail_search_arg *args)
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen{
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_simplify_prev_arg mask;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_arg **prev_argp, *prev_arg;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (*prev_argp == NULL) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        *prev_argp = args;
a8e132559a7ebe54c8269d79ce29fa3338c76199Timo Sirainen        return FALSE;
e2a700d0628e395d64cbcef4b5b4510816bf51c4Timo Sirainen    }
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen
e2a700d0628e395d64cbcef4b5b4510816bf51c4Timo Sirainen    prev_arg = *prev_argp;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    switch (args->type) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    case SEARCH_SMALLER:
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        if (ctx->parent_and) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            if (prev_arg->value.size < args->value.size) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen                /* prev_arg < 5 AND arg < 10 */
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            } else {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                /* prev_arg < 10 AND arg < 5 */
a8e132559a7ebe54c8269d79ce29fa3338c76199Timo Sirainen                prev_arg->value.size = args->value.size;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        } else {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            if (prev_arg->value.size < args->value.size) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                /* prev_arg < 5 OR arg < 10 */
a8e132559a7ebe54c8269d79ce29fa3338c76199Timo Sirainen                prev_arg->value.size = args->value.size;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            } else {
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen                /* prev_arg < 10 OR arg < 5 */
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen            }
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        }
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen        return TRUE;
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen    case SEARCH_LARGER:
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen        if (ctx->parent_and) {
e2a700d0628e395d64cbcef4b5b4510816bf51c4Timo Sirainen            if (prev_arg->value.size < args->value.size) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen                /* prev_arg >= 5 AND arg >= 10 */
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen                prev_arg->value.size = args->value.size;
e2a700d0628e395d64cbcef4b5b4510816bf51c4Timo Sirainen            } else {
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen                /* prev_arg >= 10 AND arg >= 5 */
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            }
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        } else {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            if (prev_arg->value.size < args->value.size) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen                /* prev_arg >= 5 OR arg >= 10 */
43358fffb1d9f3091fd94895e0ac4643c50e2388Timo Sirainen            } else {
43358fffb1d9f3091fd94895e0ac4643c50e2388Timo Sirainen                /* prev_arg >= 10 OR arg >= 5 */
43358fffb1d9f3091fd94895e0ac4643c50e2388Timo Sirainen                prev_arg->value.size = args->value.size;
43358fffb1d9f3091fd94895e0ac4643c50e2388Timo Sirainen            }
43358fffb1d9f3091fd94895e0ac4643c50e2388Timo Sirainen        }
43358fffb1d9f3091fd94895e0ac4643c50e2388Timo Sirainen        return TRUE;
25ee72451d16374ed27fdbf829f4ec756c778352Timo Sirainen    default:
a3dd97fb6d92a89c3de0597fed2d4b044c7aeb84Timo Sirainen        break;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return FALSE;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen}
484e12acec34f16e5a8adc001e23ae48f1dda8c7Timo Sirainen
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainenstatic bool mail_search_args_merge_text(struct mail_search_simplify_ctx *ctx,
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                    struct mail_search_arg *args)
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen{
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    struct mail_search_simplify_prev_arg mask;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    struct mail_search_arg **prev_argp;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen
484e12acec34f16e5a8adc001e23ae48f1dda8c7Timo Sirainen    mail_search_arg_get_base_mask(args, &mask);
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    mask.hdr_field_name_mask = args->hdr_field_name;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    mask.str_mask = args->value.str;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    if (*prev_argp == NULL) {
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen        *prev_argp = args;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen        return FALSE;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    }
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    /* duplicate search word. */
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    return TRUE;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen}
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainenstatic bool
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainenmail_search_args_have_equal(const struct mail_search_arg *args,
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                const struct mail_search_arg *wanted_arg)
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen{
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    const struct mail_search_arg *arg;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    for (arg = args; arg != NULL; arg = arg->next) {
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen        if (mail_search_arg_one_equals(arg, wanted_arg))
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            return TRUE;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    }
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    return FALSE;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen}
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainenstatic bool
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainenmail_search_args_remove_equal(struct mail_search_arg **argsp,
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                  const struct mail_search_arg *wanted_arg,
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                  bool check_subs)
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen{
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    struct mail_search_arg **argp;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    bool found = FALSE;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    for (argp = argsp; (*argp) != NULL; ) {
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen        if (mail_search_arg_one_equals(*argp, wanted_arg)) {
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            *argp = (*argp)->next;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            found = TRUE;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen        } else if (check_subs) {
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            i_assert((*argp)->type == SEARCH_SUB ||
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                 (*argp)->type == SEARCH_OR);
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            if (!mail_search_args_remove_equal(&(*argp)->value.subargs, wanted_arg, FALSE)) {
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                /* we already verified that this should have
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                   existed. */
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                i_unreached();
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            }
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            if ((*argp)->value.subargs == NULL)
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen                *argp = (*argp)->next;
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen            else
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                argp = &(*argp)->next;
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen            found = TRUE;
137ea7ca34005345aa2304a940149b7f3774d727Timo Sirainen        } else {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            argp = &(*argp)->next;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        }
6fabfb7bbfd88d0c1de66981e52850f26067623bTimo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return found;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
6fabfb7bbfd88d0c1de66981e52850f26067623bTimo Sirainen
6fabfb7bbfd88d0c1de66981e52850f26067623bTimo Sirainenstatic bool
6fabfb7bbfd88d0c1de66981e52850f26067623bTimo Sirainenmail_search_args_have_all_equal(struct mail_search_arg *parent_arg,
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen                const struct mail_search_arg *wanted_args)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen    const struct mail_search_arg *arg;
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen    i_assert(parent_arg->type == SEARCH_SUB ||
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen         parent_arg->type == SEARCH_OR);
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen    for (arg = wanted_args; arg != NULL; arg = arg->next) {
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen        if (!mail_search_args_have_equal(parent_arg->value.subargs, arg))
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen            return FALSE;
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen    }
137ea7ca34005345aa2304a940149b7f3774d727Timo Sirainen    return TRUE;
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen}
0f39a57760d93cddbce3ca43096d78e0fe2f42fdTimo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstatic unsigned int
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenmail_search_args_count(const struct mail_search_arg *args)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen    unsigned int count;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen    for (count = 0; args != NULL; count++)
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        args = args->next;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return count;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstatic bool
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenmail_search_args_simplify_drop_redundant_args(struct mail_search_arg **argsp,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                          bool and_arg)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_arg *arg, **argp, one_arg, *lowest_arg = NULL;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    enum mail_search_arg_type child_subargs_type;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    unsigned int count, lowest_count = UINT_MAX;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    bool ret = FALSE;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    if (*argsp == NULL)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen    /* find the arg which has the lowest number of child args */
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen    for (arg = *argsp; arg != NULL; arg = arg->next) {
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen        if (arg->type != child_subargs_type) {
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen            one_arg = *arg;
70c181da837ed85fc5b0426c010b65609bda5329Timo Sirainen            one_arg.next = NULL;
bd354c19cb93c07ade79477674328a54146ea332Timo Sirainen            lowest_arg = &one_arg;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            break;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        }
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        count = mail_search_args_count(arg->value.subargs);
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        if (count < lowest_count) {
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            lowest_arg = arg->value.subargs;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen            lowest_count = count;
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen        }
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen    }
b42f37ae6f65ed986315b6885568d32115e589b1Timo Sirainen    i_assert(lowest_arg != NULL);
e9503210d3521a6833ed62dc332fc42ffb0e7a13Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    /* if there are any args that include lowest_arg, drop the arg since
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen       it's redundant. (non-SUB duplicates are dropped elsewhere.) */
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen    for (argp = argsp; *argp != NULL; ) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        if (*argp != lowest_arg && (*argp)->type == child_subargs_type &&
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            (*argp)->value.subargs != lowest_arg &&
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            mail_search_args_have_all_equal(*argp, lowest_arg)) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            *argp = (*argp)->next;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            ret = TRUE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        } else {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            argp = &(*argp)->next;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return ret;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen}
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenstatic bool
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenmail_search_args_simplify_extract_common(struct mail_search_arg **argsp,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                     pool_t pool, bool and_arg)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen    /* Simple SUB example:
35136dd2baf8dc30e4e754294ed81ff48e8c1e64Timo Sirainen       (a AND b) OR (a AND c) -> a AND (b OR c)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen       More complicated example:
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen       (c1 AND c2 AND u1 AND u2) OR (c1 AND c2 AND u3 AND u4) ->
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen       c1 AND c2 AND ((u1 AND u2) OR (u3 AND u4))
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen       Similarly for ORs:
2cfe9983ce7a6280636ee12beccc2e865111967bTimo Sirainen       (a OR b) AND (a OR c) -> a OR (b AND c)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen       (c1 OR c2 OR u1 OR u2) AND (c1 OR c2 OR u3 OR u4) ->
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen       c1 OR c2 OR ((u1 OR u2) AND (u3 OR u4))
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_arg *arg, *sub_arg, *sub_next;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    struct mail_search_arg *new_arg, *child_arg, *common_args = NULL;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    enum mail_search_arg_type child_subargs_type;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen    if (*argsp == NULL || (*argsp)->next == NULL) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        /* single arg, nothing to extract */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    /* find the first arg with child_subargs_type */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    for (arg = *argsp; arg != NULL; arg = arg->next) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        if (arg->type == child_subargs_type)
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen            break;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (arg == NULL)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return FALSE;
19e8adccba16ff419f5675b1575358c2956dce83Timo Sirainen
eddd9bf1a1369aea4a2715f6be1137da6d17d293Timo Sirainen    for (sub_arg = arg->value.subargs; sub_arg != NULL; sub_arg = sub_next) {
19e8adccba16ff419f5675b1575358c2956dce83Timo Sirainen        sub_next = sub_arg->next;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        /* check if sub_arg is found from all the args */
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        for (arg = *argsp; arg != NULL; arg = arg->next) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            if (mail_search_arg_one_equals(arg, sub_arg)) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                /* the whole arg matches */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            } else if (arg->type == child_subargs_type &&
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen                   mail_search_args_have_equal(arg->value.subargs, sub_arg)) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                /* exists as subarg */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            } else {
2cfe9983ce7a6280636ee12beccc2e865111967bTimo Sirainen                break;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        }
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        if (arg != NULL)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            continue;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        /* extract the arg and put it to common_args */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        mail_search_args_remove_equal(argsp, sub_arg, TRUE);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        sub_arg->next = common_args;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        common_args = sub_arg;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    if (common_args == NULL)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        return FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    /* replace all the original args with a single new SUB/OR arg */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    new_arg = p_new(pool, struct mail_search_arg, 1);
2cfe9983ce7a6280636ee12beccc2e865111967bTimo Sirainen    new_arg->type = child_subargs_type;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    if (*argsp == NULL) {
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen        /* there are only common args */
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        new_arg->value.subargs = common_args;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    } else {
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen        /* replace OR arg with AND(OR(non_common_args), common_args)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen           or
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen           replace AND arg with OR(AND(non_common_args), common_args) */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        child_arg = p_new(pool, struct mail_search_arg, 1);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        child_arg->type = and_arg ? SEARCH_SUB : SEARCH_OR;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        child_arg->value.subargs = *argsp;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        child_arg->next = common_args;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        new_arg->value.subargs = child_arg;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    *argsp = new_arg;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    return TRUE;
2526d52441ef368215ab6bf04fd0356d3b09d235Timo Sirainen}
2526d52441ef368215ab6bf04fd0356d3b09d235Timo Sirainen
93fa87cf1a96c4f279ec4f5c311820313ba12c34Timo Sirainenstatic bool
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainenmail_search_args_simplify_sub(struct mailbox *box, pool_t pool,
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                  struct mail_search_arg **argsp, bool parent_and)
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen{
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    struct mail_search_simplify_ctx ctx;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    struct mail_search_arg *sub, **all_argsp = argsp;
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen    bool merged;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    memset(&ctx, 0, sizeof(ctx));
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    ctx.parent_and = parent_and;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen    ctx.pool = pool_alloconly_create("mail search args simplify", 1024);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    hash_table_create(&ctx.prev_args, ctx.pool, 0,
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen              mail_search_simplify_prev_arg_hash,
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen              mail_search_simplify_prev_arg_cmp);
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen    while (*argsp != NULL) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        struct mail_search_arg *args = *argsp;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        if (args->match_not && (args->type == SEARCH_SUB ||
c1ebcdad1b4d950eb22219704dd9d64a89d0568fTimo Sirainen                    args->type == SEARCH_OR)) {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            /* neg(p and q and ..) == neg(p) or neg(q) or ..
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen               neg(p or q or ..) == neg(p) and neg(q) and .. */
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            args->type = args->type == SEARCH_SUB ?
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen                SEARCH_OR : SEARCH_SUB;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen            args->match_not = FALSE;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            sub = args->value.subargs;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            do {
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                sub->match_not = !sub->match_not;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen                sub = sub->next;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            } while (sub != NULL);
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        if ((args->type == SEARCH_SUB && parent_and) ||
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            (args->type == SEARCH_OR && !parent_and) ||
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen            ((args->type == SEARCH_SUB || args->type == SEARCH_OR) &&
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen             args->value.subargs->next == NULL)) {
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen            /* p and (q and ..) == p and q and ..
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen               p or (q or ..) == p or q or ..
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen               (p) = p */
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen            sub = args->value.subargs;
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen            for (; sub->next != NULL; sub = sub->next) ;
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen            sub->next = args->next;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen            *args = *args->value.subargs;
82f53ea81671bcc7b9bf24a34b04a4ba2752efd3Timo Sirainen            ctx.removals = TRUE;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen            continue;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        }
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen
2e29e4797a48d78d669821722bdb54fd0a1d3b94Timo Sirainen        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(&args->value.subargs, and_arg))
                    ctx.removals = TRUE;
                if (mail_search_args_simplify_extract_common(&args->value.subargs, pool, and_arg))
                    ctx.removals = TRUE;
            }
            if (mail_search_args_simplify_sub(box, 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_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_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->box, 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->box, args->pool, &args->args, TRUE))
            removals = TRUE;
    }
    for (;;) {
        if (mail_search_args_simplify_drop_redundant_args(&args->args, TRUE))
            removals = TRUE;
        if (mail_search_args_simplify_extract_common(&args->args, args->pool, TRUE))
            removals = TRUE;
        if (!removals)
            break;
        removals = mail_search_args_simplify_sub(args->box, args->pool, &args->args, TRUE);
    }
}