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

	mail-search-args-simplify.c revision 7000810786f2959f02cd6d2f4151a9eb61ff5db8
5f5870385cff47efd2f58e7892f251cf13761528Timo Sirainen/* Copyright (c) 2002-2015 Dovecot authors, see the included COPYING file */
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen#include "lib.h"
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen#include "mail-search.h"
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
472369cba85d9f7c995dda60e7cd01d78b4a960aTimo Sirainenstruct mail_search_simplify_ctx {
e28fa207d1a097fa6e4a867f74ee0761472ef1ceTimo Sirainen    struct mail_search_arg *prev_flags, *prev_not_flags;
37847ec8eaec9ad55c9df10ae109efe7b37ac573Timo Sirainen    struct mail_search_arg *prev_seqset, *prev_not_seqset;
bd4e36a8cd7257cca7d1434c49a1e343ed7c5100Timo Sirainen    struct mail_search_arg *prev_uidset, *prev_not_uidset;
adb6413686e52e00dded4932babcc08ff041876bTimo Sirainen    bool removals;
b1f37113a5760bee842c5a7678bb5fa6f5bd8b60Timo Sirainen};
1c1cecd3dfaf71b0c9499b044023e631841e88aaTimo Sirainen
94d8e51119003d2bc5a100c663f90141f297385dTimo Sirainenstatic bool mail_search_args_merge_flags(struct mail_search_simplify_ctx *ctx,
e28fa207d1a097fa6e4a867f74ee0761472ef1ceTimo Sirainen                     struct mail_search_arg *args)
37847ec8eaec9ad55c9df10ae109efe7b37ac573Timo Sirainen{
ef50336eefcb9ba99f73c6af37420eaf8857a39bTimo Sirainen    struct mail_search_arg **prev_argp;
13d98ffa534f2e7d04a832c9d0153fc9c568b878Timo Sirainen
13d98ffa534f2e7d04a832c9d0153fc9c568b878Timo Sirainen    prev_argp = !args->match_not ? &ctx->prev_flags : &ctx->prev_not_flags;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen    if (*prev_argp == NULL) {
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        *prev_argp = args;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        return FALSE;
dc5606fb66d30a659459446b6ca1a8b4f1146052Timo Sirainen    } else {
5694eeb99b69dea8033ca77ad69743c6b4871370Timo Sirainen        (*prev_argp)->value.flags |= args->value.flags;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        return TRUE;
5694eeb99b69dea8033ca77ad69743c6b4871370Timo Sirainen    }
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen}
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainenstatic bool mail_search_args_merge_set(struct mail_search_simplify_ctx *ctx,
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                       struct mail_search_arg *args)
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen{
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen    struct mail_search_arg **prev_argp;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen    if (args->type == SEARCH_SEQSET) {
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        prev_argp = !args->match_not ? &ctx->prev_seqset :
8e371a3ce32bd64288786855b8ce0cb63f19f7d1Timo Sirainen            &ctx->prev_not_seqset;
220e21750948941dc6e33b8f11b552fa21d7f81eTimo Sirainen    } else {
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        prev_argp = !args->match_not ? &ctx->prev_uidset :
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            &ctx->prev_not_uidset;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen    }
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen    if (*prev_argp == NULL) {
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen        *prev_argp = args;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen        return FALSE;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen    } else {
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen        seq_range_array_merge(&(*prev_argp)->value.seqset,
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen                      &args->value.seqset);
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen        return TRUE;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen    }
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen}
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainenstatic bool
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainenmail_search_args_simplify_sub(struct mailbox *box,
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                  struct mail_search_arg *args, bool parent_and)
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen{
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen    struct mail_search_simplify_ctx ctx;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen    struct mail_search_arg *sub, *prev_arg = NULL;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen    memset(&ctx, 0, sizeof(ctx));
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen    while (args != NULL) {
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        if (args->match_not && (args->type == SEARCH_SUB ||
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                    args->type == SEARCH_OR)) {
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            /* neg(p and q and ..) == neg(p) or neg(q) or ..
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen               neg(p or q or ..) == neg(p) and neg(q) and .. */
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            args->type = args->type == SEARCH_SUB ?
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                SEARCH_OR : SEARCH_SUB;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            args->match_not = FALSE;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen            sub = args->value.subargs;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen            do {
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen                sub->match_not = !sub->match_not;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen                sub = sub->next;
8a0ad174adb1eb5108511b90e97f4e5f9089b0eeTimo Sirainen            } while (sub != NULL);
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        }
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        if ((args->type == SEARCH_SUB && parent_and) ||
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            (args->type == SEARCH_OR && !parent_and) ||
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            ((args->type == SEARCH_SUB || args->type == SEARCH_OR) &&
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen             args->value.subargs->next == NULL)) {
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            /* p and (q and ..) == p and q and ..
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen               p or (q or ..) == p or q or ..
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen               (p) = p */
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            sub = args->value.subargs;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            for (; sub->next != NULL; sub = sub->next) ;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            sub->next = args->next;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            *args = *args->value.subargs;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            continue;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        }
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen        if (args->type == SEARCH_SUB ||
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen            args->type == SEARCH_OR ||
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen            args->type == SEARCH_INTHREAD) {
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen            if (mail_search_args_simplify_sub(box, args->value.subargs,
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen                              args->type != SEARCH_OR))
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen                ctx.removals = TRUE;
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen        }
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen        if ((!args->match_not && parent_and) ||
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen            (args->match_not && !parent_and)) {
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen            /* try to merge arguments */
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen            bool merged;
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            switch (args->type) {
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            case SEARCH_FLAGS:
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen                merged = mail_search_args_merge_flags(&ctx, args);
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen                break;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            case SEARCH_SEQSET:
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            case SEARCH_UIDSET:
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                merged = mail_search_args_merge_set(&ctx, args);
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                break;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            case SEARCH_BEFORE:
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen            default:
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen                merged = FALSE;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                break;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            }
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            if (merged) {
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                prev_arg->next = args->next;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                args = args->next;
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen                ctx.removals = TRUE;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen                continue;
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen            }
a27e065f1a1f91c7fbdf7c2ea1c387441af0cbb3Timo Sirainen        }
1701e3f91107051b1704721bf1dc1e32491faaf9Timo Sirainen
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen        prev_arg = args;
63e207529879438e9f4412d97cdc34bdc82a3702Timo Sirainen        args = args->next;
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen    }
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen    return ctx.removals;
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen}
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainenstatic bool
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainenmail_search_args_unnest_inthreads(struct mail_search_args *args,
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen                  struct mail_search_arg **argp,
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen                  bool parent_inthreads, bool parent_and)
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen{
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen    struct mail_search_arg *arg, *thread_arg, *or_arg;
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen    bool child_inthreads = FALSE, non_inthreads = FALSE;
a24519c36d5f8fa22f58b2c693ba547e8d175a54Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    for (arg = *argp; arg != NULL; arg = arg->next) {
1701e3f91107051b1704721bf1dc1e32491faaf9Timo Sirainen        switch (arg->type) {
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        case SEARCH_SUB:
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        case SEARCH_OR:
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            if (!mail_search_args_unnest_inthreads(args,
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                    &arg->value.subargs, parent_inthreads,
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                    arg->type != SEARCH_OR)) {
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                arg->result = 1;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                child_inthreads = TRUE;
3fe67ec75ccae1230bb9eb9f16affc48377f6441Timo Sirainen            } else {
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                arg->result = 0;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen                non_inthreads = TRUE;
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen            }
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen            break;
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen        case SEARCH_INTHREAD:
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen            if (mail_search_args_unnest_inthreads(args,
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen                    &arg->value.subargs, TRUE, TRUE)) {
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen                /* children converted to SEARCH_INTHREADs */
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen                arg->type = SEARCH_SUB;
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen            }
2a6dcd984104fed84bed8795ccdfabb20e41ce52Timo Sirainen            args->have_inthreads = TRUE;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            arg->result = 1;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            child_inthreads = TRUE;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            break;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        default:
5214b67a7dabab87da74e04bb8b227f94b95bce4Timo Sirainen            arg->result = 0;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            non_inthreads = TRUE;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen            break;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        }
27586e4785d56aeb76e1fd96af8db799688dc64aTimo Sirainen    }
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
5214b67a7dabab87da74e04bb8b227f94b95bce4Timo Sirainen    if (!parent_inthreads || !child_inthreads || !non_inthreads)
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        return FALSE;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    /* put all non-INTHREADs under a single INTHREAD */
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    thread_arg = p_new(args->pool, struct mail_search_arg, 1);
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    thread_arg->type = SEARCH_INTHREAD;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    while (*argp != NULL) {
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        arg = *argp;
1c1cecd3dfaf71b0c9499b044023e631841e88aaTimo Sirainen        argp = &(*argp)->next;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        if (arg->result == 0) {
7920a47321690c932ffd4d286cd16b4048d22d41Timo Sirainen            /* not an INTHREAD or a SUB/OR with only INTHREADs */
e5acc283bf030b0b5c79ca4e52d315c516a299faPascal Volk            arg->next = thread_arg->value.subargs;
e5acc283bf030b0b5c79ca4e52d315c516a299faPascal Volk            thread_arg->value.subargs = arg;
e5acc283bf030b0b5c79ca4e52d315c516a299faPascal Volk        }
e5acc283bf030b0b5c79ca4e52d315c516a299faPascal Volk    }
e5acc283bf030b0b5c79ca4e52d315c516a299faPascal Volk    if (!parent_and) {
e5acc283bf030b0b5c79ca4e52d315c516a299faPascal Volk        /* We want to OR the args */
7920a47321690c932ffd4d286cd16b4048d22d41Timo Sirainen        or_arg = p_new(args->pool, struct mail_search_arg, 1);
7920a47321690c932ffd4d286cd16b4048d22d41Timo Sirainen        or_arg->type = SEARCH_OR;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen        or_arg->value.subargs = thread_arg->value.subargs;
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen        thread_arg->value.subargs = or_arg;
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen    }
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen    return TRUE;
db8b0a3f74a20528d66a3c4be7df920e5c4554c2Timo Sirainen}
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
5666a3d6a7ea89362b8d9e8b39b15424cd9d6388Timo Sirainenvoid mail_search_args_simplify(struct mail_search_args *args)
1701e3f91107051b1704721bf1dc1e32491faaf9Timo Sirainen{
1701e3f91107051b1704721bf1dc1e32491faaf9Timo Sirainen    bool removals;
1701e3f91107051b1704721bf1dc1e32491faaf9Timo Sirainen
b365bd121cdc87f63e1dd47c5085a27091118e00Timo Sirainen    args->simplified = TRUE;
94b0ff77495c3ed14bdd4b5d7ae1eb37e8c9efb5Timo Sirainen
adb6413686e52e00dded4932babcc08ff041876bTimo Sirainen    removals = mail_search_args_simplify_sub(args->box, args->args, TRUE);
adb6413686e52e00dded4932babcc08ff041876bTimo Sirainen    if (mail_search_args_unnest_inthreads(args, &args->args,
adb6413686e52e00dded4932babcc08ff041876bTimo Sirainen                          FALSE, TRUE)) {
adb6413686e52e00dded4932babcc08ff041876bTimo Sirainen        /* we may have added some extra SUBs that could be dropped */
adb6413686e52e00dded4932babcc08ff041876bTimo Sirainen        mail_search_args_simplify_sub(args->box, args->args, TRUE);
9abf5be0962538e1f6f5c73c838ff677341da0c9Timo Sirainen    }
94b0ff77495c3ed14bdd4b5d7ae1eb37e8c9efb5Timo Sirainen    if (removals)
94b0ff77495c3ed14bdd4b5d7ae1eb37e8c9efb5Timo Sirainen        mail_search_args_simplify_sub(args->box, args->args, TRUE);
94b0ff77495c3ed14bdd4b5d7ae1eb37e8c9efb5Timo Sirainen}
94b0ff77495c3ed14bdd4b5d7ae1eb37e8c9efb5Timo Sirainen