lib-storage/index/index-thread.c

	index-thread.c revision 5fa6399cfdf74f19851fb28bd654b944a62c0b0c
c25356d5978632df6203437e1953bcb29e0c736fTimo Sirainen/* Copyright (c) 2002-2010 Dovecot authors, see the included COPYING file */
c25356d5978632df6203437e1953bcb29e0c736fTimo Sirainen
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen/* doc/thread-refs.txt describes the incremental algorithm we use here. */
49e358eebea107aad9919dcc4bd88cee8519ba2eTimo Sirainen
49e358eebea107aad9919dcc4bd88cee8519ba2eTimo Sirainen#include "lib.h"
49e358eebea107aad9919dcc4bd88cee8519ba2eTimo Sirainen#include "array.h"
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen#include "bsearch-insert-pos.h"
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen#include "hash2.h"
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen#include "message-id.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include "mail-index-private.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include "mail-index-sync-private.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include "mail-search.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include "mail-search-build.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include "mailbox-search-result-private.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include "index-storage.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include "index-thread-private.h"
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen#include <stdlib.h>
7b29ccd796fc75af86f827192d2f8c0e8f0087bbTimo Sirainen
7b29ccd796fc75af86f827192d2f8c0e8f0087bbTimo Sirainen#define MAIL_THREAD_CONTEXT(obj) \
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen    MODULE_CONTEXT(obj, mail_thread_storage_module)
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainenstruct mail_thread_context {
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen    struct mailbox *box;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen    struct mailbox_transaction_context *t;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen    struct mail_index_strmap_view_sync *strmap_sync;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen
da2aa032ccfa8e7e4a4380ef738014549f4d2c2dTimo Sirainen    struct mail *tmp_mail;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen    struct mail_search_args *search_args;
7b29ccd796fc75af86f827192d2f8c0e8f0087bbTimo Sirainen    ARRAY_TYPE(seq_range) added_uids;
7b29ccd796fc75af86f827192d2f8c0e8f0087bbTimo Sirainen
7b29ccd796fc75af86f827192d2f8c0e8f0087bbTimo Sirainen    unsigned int failed:1;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen};
252db51b6c0a605163326b3ea5d09e9936ca3b29Timo Sirainen
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainenstruct mail_thread_mailbox {
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    union mailbox_module_context module_ctx;
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen    unsigned int next_msgid_idx;
e93184a9055c2530366dfe617e07199603c399ddMartti Rannanjärvi    struct mail_thread_cache *cache;
43834f87bf431198f986e86052a4f6e558fdb07dTimo Sirainen
43834f87bf431198f986e86052a4f6e558fdb07dTimo Sirainen    struct mail_index_strmap *strmap;
09801f106cd531a28b4e03ec665e44c421264560Timo Sirainen    struct mail_index_strmap_view *strmap_view;
09801f106cd531a28b4e03ec665e44c421264560Timo Sirainen    /* sorted by UID, ref_index */
09801f106cd531a28b4e03ec665e44c421264560Timo Sirainen    const ARRAY_TYPE(mail_index_strmap_rec) *msgid_map;
fe363b433b8038a69b55169da9dca27892ad7d18Timo Sirainen    const struct hash2_table *msgid_hash;
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen    /* set only temporarily while needed */
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch    struct mail_thread_context *ctx;
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch};
fe363b433b8038a69b55169da9dca27892ad7d18Timo Sirainen
212a34c06ff45952c008ae9eec387ced783de6cfPhil Carmodystatic MODULE_CONTEXT_DEFINE_INIT(mail_thread_storage_module,
212a34c06ff45952c008ae9eec387ced783de6cfPhil Carmody                  &mail_storage_module_register);
212a34c06ff45952c008ae9eec387ced783de6cfPhil Carmody
212a34c06ff45952c008ae9eec387ced783de6cfPhil Carmodystatic void mail_thread_clear(struct mail_thread_context *ctx);
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Boschstatic int
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Boschmail_strmap_rec_get_msgid(struct mail *mail,
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch              const struct mail_index_strmap_rec *rec,
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch              const char **msgid_r)
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch{
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch    const char *msgids = NULL, *msgid;
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch    unsigned int n = 0;
a9a928e40e3b691924c8e5e444e3e1a4320aa3bdStephan Bosch    int ret;
10c96a244935de4add8213ba0b894178dfb889a5Timo Sirainen
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen    if (!mail_set_uid(mail, rec->uid))
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen        return 0;
0c1835a90dd1dcedaeaedd1cd91672299cbeb5beTimo Sirainen
f4735bf7ec2019fdc730e9ebdb39e5a4ea580405Timo Sirainen    switch (rec->ref_index) {
f4735bf7ec2019fdc730e9ebdb39e5a4ea580405Timo Sirainen    case MAIL_THREAD_NODE_REF_MSGID:
f4735bf7ec2019fdc730e9ebdb39e5a4ea580405Timo Sirainen        /* Message-ID: header */
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        ret = mail_get_first_header(mail, HDR_MESSAGE_ID, &msgids);
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen        break;
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen    case MAIL_THREAD_NODE_REF_INREPLYTO:
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen        /* In-Reply-To: header */
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen        ret = mail_get_first_header(mail, HDR_IN_REPLY_TO, &msgids);
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen        break;
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen    default:
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen        /* References: header */
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainen        ret = mail_get_first_header(mail, HDR_REFERENCES, &msgids);
cd56a23e21f1df3f79648cf07e2f4385e2fadebbTimo Sirainen        n = rec->ref_index - MAIL_THREAD_NODE_REF_REFERENCES1;
cd56a23e21f1df3f79648cf07e2f4385e2fadebbTimo Sirainen        break;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    }
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen    if (ret < 0) {
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        if (mail->expunged) {
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen            /* treat it as if it didn't exist. trying to add it
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen               again will result in failure. */
1a0ece3e873e3864269ed7eaed957dc10c56d25fTimo Sirainen            return 0;
a10ed8c47534b4c6b6bf2711ccfe577e720a47b4Timo Sirainen        }
a10ed8c47534b4c6b6bf2711ccfe577e720a47b4Timo Sirainen        return -1;
1a0ece3e873e3864269ed7eaed957dc10c56d25fTimo Sirainen    }
1a0ece3e873e3864269ed7eaed957dc10c56d25fTimo Sirainen
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen    /* get the nth message-id */
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen    msgid = message_id_get_next(&msgids);
c28f6aa0b70af4811c9ace9114fe827c2f503455Timo Sirainen    if (msgid != NULL) {
1a0ece3e873e3864269ed7eaed957dc10c56d25fTimo Sirainen        for (; n > 0 && *msgids != '\0'; n--)
1a0ece3e873e3864269ed7eaed957dc10c56d25fTimo Sirainen            msgid = message_id_get_next(&msgids);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    }
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen    if (msgid == NULL) {
46ce4d9273e6df12ef1912bbdb1c8b84b104f394Timo Sirainen        /* shouldn't have happened */
46ce4d9273e6df12ef1912bbdb1c8b84b104f394Timo Sirainen        mail_storage_set_critical(mail->box->storage,
862ec874f9373e3e499e237d3b9f71fdf1413feeTimo Sirainen                      "Threading lost Message ID");
5af5137f6dc0c9f358b7813e941e26f7bd735b3aTimo Sirainen        return -1;
5af5137f6dc0c9f358b7813e941e26f7bd735b3aTimo Sirainen    }
5af5137f6dc0c9f358b7813e941e26f7bd735b3aTimo Sirainen    *msgid_r = msgid;
5af5137f6dc0c9f358b7813e941e26f7bd735b3aTimo Sirainen    return 1;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen}
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainen
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainenstatic bool
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainenmail_thread_hash_key_cmp(const char *key,
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen             const struct mail_index_strmap_rec *rec,
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen             void *context)
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen{
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    struct mail_thread_mailbox *tbox = context;
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen    struct mail_thread_context *ctx = tbox->ctx;
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen    const char *msgid;
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen    bool cmp_ret;
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen    int ret;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
71aed7ba87b5fd5e96e97a22d89ac025b883d60aTimo Sirainen    /* either a match or a collision, need to look closer */
71aed7ba87b5fd5e96e97a22d89ac025b883d60aTimo Sirainen    T_BEGIN {
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen        ret = mail_strmap_rec_get_msgid(ctx->tmp_mail, rec, &msgid);
71aed7ba87b5fd5e96e97a22d89ac025b883d60aTimo Sirainen        if (ret <= 0) {
19557f192d37cd54a1a090a8a26d9d47265e4413Aki Tuomi            if (ret < 0)
71aed7ba87b5fd5e96e97a22d89ac025b883d60aTimo Sirainen                ctx->failed = TRUE;
71aed7ba87b5fd5e96e97a22d89ac025b883d60aTimo Sirainen            cmp_ret = FALSE;
0a49b316fc729e5d57268ffa63c7122ac73f994cTimo Sirainen        } else {
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen            cmp_ret = strcmp(msgid, key) == 0;
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen        }
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen    } T_END;
463f6ea04af934a68facaca0ff089bc306de3f98Timo Sirainen    return cmp_ret;
463f6ea04af934a68facaca0ff089bc306de3f98Timo Sirainen}
463f6ea04af934a68facaca0ff089bc306de3f98Timo Sirainen
463f6ea04af934a68facaca0ff089bc306de3f98Timo Sirainenstatic int
0b6924ad1943fe5c6917fc49f675d8f316b0d939Timo Sirainenmail_thread_hash_rec_cmp(const struct mail_index_strmap_rec *rec1,
0b6924ad1943fe5c6917fc49f675d8f316b0d939Timo Sirainen             const struct mail_index_strmap_rec *rec2,
0b6924ad1943fe5c6917fc49f675d8f316b0d939Timo Sirainen             void *context)
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen{
e0fab14602b73ff590b2a9c5d9e67e2dfb5d1f9eTimo Sirainen    struct mail_thread_mailbox *tbox = context;
e0fab14602b73ff590b2a9c5d9e67e2dfb5d1f9eTimo Sirainen    struct mail_thread_context *ctx = tbox->ctx;
e0fab14602b73ff590b2a9c5d9e67e2dfb5d1f9eTimo Sirainen    const char *msgid1, *msgid2;
e0fab14602b73ff590b2a9c5d9e67e2dfb5d1f9eTimo Sirainen    int ret;
e0fab14602b73ff590b2a9c5d9e67e2dfb5d1f9eTimo Sirainen
e0fab14602b73ff590b2a9c5d9e67e2dfb5d1f9eTimo Sirainen    T_BEGIN {
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen        ret = mail_strmap_rec_get_msgid(ctx->tmp_mail, rec1, &msgid1);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        if (ret > 0) {
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen            msgid1 = t_strdup(msgid1);
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen            ret = mail_strmap_rec_get_msgid(ctx->tmp_mail, rec2,
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen                            &msgid2);
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen        }
87a6b7df39d6822a5a8289a62f32deabff9b75e4Timo Sirainen        ret = ret <= 0 ? -1 :
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen            strcmp(msgid1, msgid2) == 0;
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen    } T_END;
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen    return ret;
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen}
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainenstatic void mail_thread_strmap_remap(const uint32_t *idx_map,
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainen                     unsigned int old_count,
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen                     unsigned int new_count, void *context)
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen{
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen    struct mail_thread_mailbox *tbox = context;
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen    struct mail_thread_cache *cache = tbox->cache;
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen    ARRAY_TYPE(mail_thread_node) new_nodes;
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen    const struct mail_thread_node *old_nodes;
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainen    struct mail_thread_node *node;
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    unsigned int i, nodes_count, max, new_first_invalid, invalid_count;
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    if (cache->search_result == NULL)
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainen        return;
4106a25399703eb6cbb166dcbd5bb932cb2f7ad2Timo Sirainen
6a170d6d781094bdc75f027b6456dde160fbde39Timo Sirainen    if (new_count == 0) {
6a170d6d781094bdc75f027b6456dde160fbde39Timo Sirainen        /* strmap was reset, we'll need to rebuild thread */
6a170d6d781094bdc75f027b6456dde160fbde39Timo Sirainen        mailbox_search_result_free(&cache->search_result);
6a170d6d781094bdc75f027b6456dde160fbde39Timo Sirainen        return;
1bc075e2e4ed422f9590c95c3ae223422b97ce6aTimo Sirainen    }
923115fd382904fa13bb09bf307bf2835b52df60Timo Sirainen
923115fd382904fa13bb09bf307bf2835b52df60Timo Sirainen    invalid_count = cache->next_invalid_msgid_str_idx -
923115fd382904fa13bb09bf307bf2835b52df60Timo Sirainen        cache->first_invalid_msgid_str_idx;
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainen
89e195dfb5c4b0efd9b9f459771a4467674e5b1fTimo Sirainen    old_nodes = array_get(&cache->thread_nodes, &nodes_count);
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen    i_array_init(&new_nodes, new_count + invalid_count + 32);
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen    /* optimization: allocate all nodes initially */
89e195dfb5c4b0efd9b9f459771a4467674e5b1fTimo Sirainen    (void)array_idx_modifiable(&new_nodes, new_count-1);
a0b6b441fc679e562e79be0fb2819ffc24ab5b74Timo Sirainen
a0b6b441fc679e562e79be0fb2819ffc24ab5b74Timo Sirainen    /* renumber existing valid nodes. all existing records in old_nodes
89e195dfb5c4b0efd9b9f459771a4467674e5b1fTimo Sirainen       should also exist in idx_map since we've removed expunged messages
6f08b98ac63c25b747120d0c8f8e319b4e26ab0fTimo Sirainen       from the cache before committing the sync. */
6f08b98ac63c25b747120d0c8f8e319b4e26ab0fTimo Sirainen    max = I_MIN(I_MIN(old_count, nodes_count),
6f08b98ac63c25b747120d0c8f8e319b4e26ab0fTimo Sirainen            cache->first_invalid_msgid_str_idx);
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainen    for (i = 0; i < max; i++) {
6657aee0bb6c603b4ee5111388b93c1a8a9ad680Martti Rannanjärvi        if (idx_map[i] == 0) {
4106a25399703eb6cbb166dcbd5bb932cb2f7ad2Timo Sirainen            /* expunged record. */
4106a25399703eb6cbb166dcbd5bb932cb2f7ad2Timo Sirainen            i_assert(old_nodes[i].uid == 0);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        } else {
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen            node = array_idx_modifiable(&new_nodes, idx_map[i]);
4106a25399703eb6cbb166dcbd5bb932cb2f7ad2Timo Sirainen            *node = old_nodes[i];
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen            if (node->parent_idx != 0) {
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen                node->parent_idx = idx_map[node->parent_idx];
699fdc186f982f70d990820796eaa0f12133e27cTimo Sirainen                i_assert(node->parent_idx != 0);
699fdc186f982f70d990820796eaa0f12133e27cTimo Sirainen            }
699fdc186f982f70d990820796eaa0f12133e27cTimo Sirainen        }
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen    }
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    /* copy invalid nodes, if any. no other messages point to them,
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody       so this is safe. we still need to update their parent_idx
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody       pointers though. */
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    new_first_invalid = new_count + 1 +
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody        THREAD_INVALID_MSGID_STR_IDX_SKIP_COUNT;
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    for (i = 0; i < invalid_count; i++) {
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody        node = array_idx_modifiable(&new_nodes, new_first_invalid + i);
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody        *node = old_nodes[cache->first_invalid_msgid_str_idx + i];
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody        if (node->parent_idx != 0) {
573424407a2d3c1453638a643583a7cf10c129e1Phil Carmody            node->parent_idx = idx_map[node->parent_idx];
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody            i_assert(node->parent_idx != 0);
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody        }
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    }
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    cache->first_invalid_msgid_str_idx = new_first_invalid;
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    cache->next_invalid_msgid_str_idx = new_first_invalid + invalid_count;
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    /* replace the old nodes with the renumbered ones */
09142ea11662746ea07475b1a4f69a6a406fb996Phil Carmody    array_free(&cache->thread_nodes);
a215abacb2d2d1e1bcd475756aab809038ae4277Timo Sirainen    cache->thread_nodes = new_nodes;
a215abacb2d2d1e1bcd475756aab809038ae4277Timo Sirainen}
a215abacb2d2d1e1bcd475756aab809038ae4277Timo Sirainen
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainenstatic int thread_get_mail_header(struct mail *mail, const char *name,
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen                  const char **value_r)
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen{
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen    if (mail_get_first_header(mail, name, value_r) < 0) {
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen        if (!mail->expunged)
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen            return -1;
4c096615cb86a826fda377b87df22c579bfe5525Timo Sirainen
4c096615cb86a826fda377b87df22c579bfe5525Timo Sirainen        /* Message is expunged. Instead of failing the entire THREAD
4c096615cb86a826fda377b87df22c579bfe5525Timo Sirainen           command, just treat the header as nonexistent. */
4c096615cb86a826fda377b87df22c579bfe5525Timo Sirainen        *value_r = NULL;
4c096615cb86a826fda377b87df22c579bfe5525Timo Sirainen    }
4c096615cb86a826fda377b87df22c579bfe5525Timo Sirainen    return 0;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen}

static int
mail_thread_map_add_mail(struct mail_thread_context *ctx, struct mail *mail)
{
    const char *message_id, *in_reply_to, *references, *msgid;
    uint32_t ref_index;

    if (thread_get_mail_header(mail, HDR_MESSAGE_ID, &message_id) < 0 ||
        thread_get_mail_header(mail, HDR_REFERENCES, &references) < 0)
        return -1;

    /* add Message-ID: */
    msgid = message_id_get_next(&message_id);
    if (msgid != NULL) {
        mail_index_strmap_view_sync_add(ctx->strmap_sync, mail->uid,
                        MAIL_THREAD_NODE_REF_MSGID,
                        msgid);
    } else {
        mail_index_strmap_view_sync_add_unique(ctx->strmap_sync,
                    mail->uid, MAIL_THREAD_NODE_REF_MSGID);
    }

    /* add References: if there are any valid ones */
    msgid = message_id_get_next(&references);
    if (msgid != NULL) {
        ref_index = MAIL_THREAD_NODE_REF_REFERENCES1;
        do {
            mail_index_strmap_view_sync_add(ctx->strmap_sync,
                            mail->uid,
                            ref_index, msgid);
            ref_index++;
            msgid = message_id_get_next(&references);
        } while (msgid != NULL);
    } else {
        /* no References:, use In-Reply-To: */
        if (thread_get_mail_header(mail, HDR_IN_REPLY_TO,
                       &in_reply_to) < 0)
            return -1;

        msgid = message_id_get_next(&in_reply_to);
        if (msgid != NULL) {
            mail_index_strmap_view_sync_add(ctx->strmap_sync,
                mail->uid, MAIL_THREAD_NODE_REF_INREPLYTO,
                msgid);
        }
    }
    if (ctx->failed) {
        /* message-id lookup failed in hash compare */
        return -1;
    }
    return 0;
}

static int mail_thread_index_map_build(struct mail_thread_context *ctx)
{
    static const char *wanted_headers[] = {
        HDR_MESSAGE_ID, HDR_IN_REPLY_TO, HDR_REFERENCES,
        NULL
    };
    struct mail_thread_mailbox *tbox = MAIL_THREAD_CONTEXT(ctx->box);
    struct mail_search_args *search_args;
    struct mail_search_context *search_ctx;
    struct mail *mail;
    struct mail_private *pmail;
    uint32_t last_uid, seq1, seq2;
    int ret = 0;

    if (tbox->strmap_view == NULL) {
        /* first time we're threading this mailbox */
        tbox->strmap_view =
            mail_index_strmap_view_open(tbox->strmap,
                            ctx->box->view,
                            mail_thread_hash_key_cmp,
                            mail_thread_hash_rec_cmp,
                            mail_thread_strmap_remap,
                            tbox, &tbox->msgid_map,
                            &tbox->msgid_hash);
    }

    ctx->tmp_mail = mail_alloc(ctx->t, 0, NULL);
    pmail = (struct mail_private *)ctx->tmp_mail;
    pmail->extra_wanted_headers =
        mailbox_header_lookup_init(ctx->box, wanted_headers);

    /* add all missing UIDs */
    ctx->strmap_sync = mail_index_strmap_view_sync_init(tbox->strmap_view,
                                &last_uid);
    mailbox_get_seq_range(ctx->box, last_uid + 1, (uint32_t)-1,
                  &seq1, &seq2);
    if (seq1 == 0) {
        /* nothing is missing */
        mail_index_strmap_view_sync_commit(&ctx->strmap_sync);
        return 0;
    }

    search_args = mail_search_build_init();
    mail_search_build_add_seqset(search_args, seq1, seq2);
    search_ctx = mailbox_search_init(ctx->t, search_args, NULL);

    mail = mail_alloc(ctx->t, 0, NULL);
    pmail = (struct mail_private *)mail;
    pmail->extra_wanted_headers =
        mailbox_header_lookup_init(ctx->box, wanted_headers);

    while (mailbox_search_next(search_ctx, mail)) {
        if (mail_thread_map_add_mail(ctx, mail) < 0) {
            ret = -1;
            break;
        }
    }
    mailbox_header_lookup_unref(&pmail->extra_wanted_headers);
    mail_free(&mail);
    if (mailbox_search_deinit(&search_ctx) < 0)
        ret = -1;

    if (ret < 0)
        mail_index_strmap_view_sync_rollback(&ctx->strmap_sync);
    else
        mail_index_strmap_view_sync_commit(&ctx->strmap_sync);
    return ret;
}

static int msgid_map_cmp(const void *key, const void *value)
{
    const uint32_t *uid = key;
    const struct mail_index_strmap_rec *rec = value;

    return *uid < rec->uid ? -1 :
        (*uid > rec->uid ? 1 : 0);
}

static bool mail_thread_cache_update_removes(struct mail_thread_mailbox *tbox,
                         ARRAY_TYPE(seq_range) *added_uids)
{
    struct mail_thread_cache *cache = tbox->cache;
    ARRAY_TYPE(seq_range) removed_uids;
    const struct seq_range *uids;
    const struct mail_index_strmap_rec *msgid_map;
    unsigned int i, j, idx, map_count, uid_count;
    uint32_t uid;

    t_array_init(&removed_uids, 64);
    mailbox_search_result_sync(cache->search_result,
                   &removed_uids, added_uids);

    /* first check that we're not inserting any messages in the middle */
    uids = array_get(added_uids, &uid_count);
    if (uid_count > 0 && uids[0].seq1 <= cache->last_uid)
        return FALSE;

    /* next remove messages so we'll see early if we have to rebuild.
       we expect to find all removed UIDs from msgid_map that are <= max
       UID in msgid_map */
    msgid_map = array_get(tbox->msgid_map, &map_count);
    uids = array_get(&removed_uids, &uid_count);
    for (i = j = 0; i < uid_count; i++) {
        /* find and remove from the map */
        bsearch_insert_pos(&uids[i].seq1, &msgid_map[j], map_count - j,
                   sizeof(*msgid_map), msgid_map_cmp, &idx);
        j += idx;
        if (j == map_count) {
            /* all removals after this are about messages we never
               even added to the cache */
            i_assert(uids[i].seq1 > cache->last_uid);
            break;
        }
        while (j > 0 && msgid_map[j-1].uid == msgid_map[j].uid)
            j--;

        /* remove the messages from cache */
        for (uid = uids[i].seq1; uid <= uids[i].seq2; uid++) {
            if (j == map_count) {
                i_assert(uid > cache->last_uid);
                break;
            }
            i_assert(msgid_map[j].uid == uid);
            if (!mail_thread_remove(cache, msgid_map + j, &j))
                return FALSE;
        }
    }
    return TRUE;
}

static void mail_thread_cache_update_adds(struct mail_thread_mailbox *tbox,
                      ARRAY_TYPE(seq_range) *added_uids)
{
    struct mail_thread_cache *cache = tbox->cache;
    const struct seq_range *uids;
    const struct mail_index_strmap_rec *msgid_map;
    unsigned int i, j, map_count, uid_count;
    uint32_t uid;

    /* everything removed successfully, add the new messages. all of them
       should already be in msgid_map. */
    uids = array_get(added_uids, &uid_count);
    if (uid_count == 0)
        return;

    (void)array_bsearch_insert_pos(tbox->msgid_map, &uids[0].seq1,
                       msgid_map_cmp, &j);
    msgid_map = array_get(tbox->msgid_map, &map_count);
    i_assert(j < map_count);
    while (j > 0 && msgid_map[j-1].uid == msgid_map[j].uid)
        j--;

    for (i = 0; i < uid_count; i++) {
        for (uid = uids[i].seq1; uid <= uids[i].seq2; uid++) {
            while (j < map_count && msgid_map[j].uid < uid)
                j++;
            i_assert(j < map_count && msgid_map[j].uid == uid);
            mail_thread_add(cache, msgid_map+j, &j);
        }
    }
}

static void
mail_thread_cache_fix_invalid_indexes(struct mail_thread_mailbox *tbox)
{
    struct mail_thread_cache *cache = tbox->cache;
    uint32_t highest_idx, new_first_idx, count;

    highest_idx = mail_index_strmap_view_get_highest_idx(tbox->strmap_view);
    new_first_idx = highest_idx + 1 +
        THREAD_INVALID_MSGID_STR_IDX_SKIP_COUNT;
    count = cache->next_invalid_msgid_str_idx -
        cache->first_invalid_msgid_str_idx;

    if (count == 0) {
        /* there are no invalid indexes yet, we can update the first
           invalid index position to delay conflicts. */
        cache->first_invalid_msgid_str_idx =
            cache->next_invalid_msgid_str_idx = new_first_idx;
    } else if (highest_idx >= cache->first_invalid_msgid_str_idx) {
        /* conflict - move the invalid indexes forward */
        array_copy(&cache->thread_nodes.arr, new_first_idx,
               &cache->thread_nodes.arr,
               cache->first_invalid_msgid_str_idx, count);
        cache->first_invalid_msgid_str_idx = new_first_idx;
        cache->next_invalid_msgid_str_idx = new_first_idx + count;
    }
}

static void mail_thread_cache_sync_remove(struct mail_thread_mailbox *tbox,
                      struct mail_thread_context *ctx)
{
    struct mail_thread_cache *cache = tbox->cache;

    if (cache->search_result == NULL)
        return;

    if (mail_search_args_equal(ctx->search_args,
                   cache->search_result->search_args)) {
        t_array_init(&ctx->added_uids, 64);
        if (mail_thread_cache_update_removes(tbox, &ctx->added_uids)) {
            /* successfully updated the cache */
            return;
        }
    }
    /* failed to use the cache, rebuild */
    mailbox_search_result_free(&cache->search_result);
}

static void mail_thread_cache_sync_add(struct mail_thread_mailbox *tbox,
                       struct mail_thread_context *ctx,
                       struct mail_search_context *search_ctx)
{
    struct mail_thread_cache *cache = tbox->cache;
    struct mail *mail;
    const struct mail_index_strmap_rec *msgid_map;
    unsigned int i, count;

    mail_thread_cache_fix_invalid_indexes(tbox);

    if (cache->search_result != NULL) {
        /* we already checked at sync_remove that we can use this
           search result. */
        mail_thread_cache_update_adds(tbox, &ctx->added_uids);
        return;
    }

    cache->last_uid = 0;
    cache->first_invalid_msgid_str_idx = cache->next_invalid_msgid_str_idx =
        mail_index_strmap_view_get_highest_idx(tbox->strmap_view) + 1 +
        THREAD_INVALID_MSGID_STR_IDX_SKIP_COUNT;
    array_clear(&cache->thread_nodes);

    mail = mail_alloc(ctx->t, 0, NULL);

    cache->search_result =
        mailbox_search_result_save(search_ctx,
            MAILBOX_SEARCH_RESULT_FLAG_UPDATE |
            MAILBOX_SEARCH_RESULT_FLAG_QUEUE_SYNC);

    msgid_map = array_get(tbox->msgid_map, &count);
    /* we're relying on the array being zero-terminated (outside used
       count - kind of kludgy) */
    i_assert(msgid_map[count].uid == 0);
    i = 0;
    while (i < count && mailbox_search_next(search_ctx, mail)) {
        while (msgid_map[i].uid < mail->uid)
            i++;
        i_assert(i < count);
        mail_thread_add(cache, msgid_map+i, &i);
    }
    mail_free(&mail);
}

int mail_thread_init(struct mailbox *box, struct mail_search_args *args,
             struct mail_thread_context **ctx_r)
{
    struct mail_thread_mailbox *tbox = MAIL_THREAD_CONTEXT(box);
    struct mail_thread_context *ctx;
    struct mail_search_context *search_ctx;
    int ret;

    i_assert(tbox->ctx == NULL);

    if (args != NULL)
        mail_search_args_ref(args);
    else {
        args = mail_search_build_init();
        mail_search_build_add_all(args);
        mail_search_args_init(args, box, FALSE, NULL);
    }

    ctx = i_new(struct mail_thread_context, 1);
    ctx->box = box;
    ctx->search_args = args;
    ctx->t = mailbox_transaction_begin(ctx->box, 0);
    /* perform search first, so we don't break if there are INTHREAD keys */
    search_ctx = mailbox_search_init(ctx->t, args, NULL);

    tbox->ctx = ctx;

    mail_thread_cache_sync_remove(tbox, ctx);
    ret = mail_thread_index_map_build(ctx) < 0;
    if (ret == 0)
        mail_thread_cache_sync_add(tbox, ctx, search_ctx);
    if (mailbox_search_deinit(&search_ctx) < 0)
        ret = -1;

    if (ret < 0) {
        mail_thread_deinit(&ctx);
        return -1;
    } else {
        memset(&ctx->added_uids, 0, sizeof(ctx->added_uids));
        *ctx_r = ctx;
        return 0;
    }
}

static void mail_thread_clear(struct mail_thread_context *ctx)
{
    struct mail_private *pmail = (struct mail_private *)ctx->tmp_mail;

    mailbox_header_lookup_unref(&pmail->extra_wanted_headers);
    mail_free(&ctx->tmp_mail);
    (void)mailbox_transaction_commit(&ctx->t);
}

void mail_thread_deinit(struct mail_thread_context **_ctx)
{
    struct mail_thread_context *ctx = *_ctx;
    struct mail_thread_mailbox *tbox = MAIL_THREAD_CONTEXT(ctx->box);

    *_ctx = NULL;

    mail_thread_clear(ctx);
    mail_search_args_unref(&ctx->search_args);
    tbox->ctx = NULL;
    i_free(ctx);
}

struct mail_thread_iterate_context *
mail_thread_iterate_init(struct mail_thread_context *ctx,
             enum mail_thread_type thread_type, bool write_seqs)
{
    struct mail_thread_mailbox *tbox = MAIL_THREAD_CONTEXT(ctx->box);

    return mail_thread_iterate_init_full(tbox->cache, ctx->tmp_mail,
                         thread_type, write_seqs);
}

static void mail_thread_mailbox_close(struct mailbox *box)
{
    struct mail_thread_mailbox *tbox = MAIL_THREAD_CONTEXT(box);

    i_assert(tbox->ctx == NULL);

    if (tbox->strmap_view != NULL)
        mail_index_strmap_view_close(&tbox->strmap_view);
    if (tbox->cache->search_result != NULL)
        mailbox_search_result_free(&tbox->cache->search_result);
    tbox->module_ctx.super.close(box);
}

static void mail_thread_mailbox_free(struct mailbox *box)
{
    struct mail_thread_mailbox *tbox = MAIL_THREAD_CONTEXT(box);

    mail_index_strmap_deinit(&tbox->strmap);
    tbox->module_ctx.super.free(box);

    array_free(&tbox->cache->thread_nodes);
    i_free(tbox->cache);
    i_free(tbox);
}

void index_thread_mailbox_opened(struct mailbox *box)
{
    struct mail_thread_mailbox *tbox = MAIL_THREAD_CONTEXT(box);

    if (tbox != NULL) {
        /* mailbox was already opened+closed once. */
        return;
    }

    tbox = i_new(struct mail_thread_mailbox, 1);
    tbox->module_ctx.super = box->v;
    box->v.close = mail_thread_mailbox_close;
    box->v.free = mail_thread_mailbox_free;

    tbox->strmap = mail_index_strmap_init(box->index,
                          MAIL_THREAD_INDEX_SUFFIX);
    tbox->next_msgid_idx = 1;

    tbox->cache = i_new(struct mail_thread_cache, 1);
    i_array_init(&tbox->cache->thread_nodes, 128);

    MODULE_CONTEXT_SET(box, mail_thread_storage_module, tbox);
}