diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:51:24 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:51:24 +0000 |
commit | f7548d6d28c313cf80e6f3ef89aed16a19815df1 (patch) | |
tree | a3f6f2a3f247293bee59ecd28e8cd8ceb6ca064a /src/lib-storage/index/index-thread-finish.c | |
parent | Initial commit. (diff) | |
download | dovecot-upstream.tar.xz dovecot-upstream.zip |
Adding upstream version 1:2.3.19.1+dfsg1.upstream/1%2.3.19.1+dfsg1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/lib-storage/index/index-thread-finish.c | 682 |
1 files changed, 682 insertions, 0 deletions
diff --git a/src/lib-storage/index/index-thread-finish.c b/src/lib-storage/index/index-thread-finish.c new file mode 100644 index 0000000..42326b6 --- /dev/null +++ b/src/lib-storage/index/index-thread-finish.c @@ -0,0 +1,682 @@ +/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "hash.h" +#include "imap-base-subject.h" +#include "mail-storage-private.h" +#include "index-thread-private.h" + + +struct mail_thread_shadow_node { + uint32_t first_child_idx, next_sibling_idx; +}; + +struct mail_thread_root_node { + /* node.idx usually points to indexes from mail hash. However + REFERENCES step (5) may add temporary dummy roots. They use larger + index numbers than exist in the hash. */ + struct mail_thread_child_node node; + + /* Used temporarily by (5)(B) base subject gathering. + root_idx1 is node's index in roots[] array + 1. + parent_root_idx points to root_idx1, or 0 for root. */ + unsigned int root_idx1; + uint32_t parent_root_idx1; + + /* subject contained a Re: or Fwd: */ + bool reply_or_forward:1; + /* a dummy node */ + bool dummy:1; + /* ignore this node - it's a dummy without children */ + bool ignore:1; +}; + +struct thread_finish_context { + unsigned int refcount; + + struct mail *tmp_mail; + struct mail_thread_cache *cache; + + ARRAY(struct mail_thread_root_node) roots; + ARRAY(struct mail_thread_shadow_node) shadow_nodes; + unsigned int next_new_root_idx; + + bool use_sent_date:1; + bool return_seqs:1; +}; + +struct mail_thread_iterate_context { + struct thread_finish_context *ctx; + + ARRAY_TYPE(mail_thread_child_node) children; + unsigned int next_idx; + bool failed; +}; + +struct subject_gather_context { + struct thread_finish_context *ctx; + + pool_t subject_pool; + HASH_TABLE(char *, struct mail_thread_root_node *) subject_hash; +}; + +static void +add_base_subject(struct subject_gather_context *ctx, const char *subject, + struct mail_thread_root_node *node) +{ + struct mail_thread_root_node *hash_node; + char *hash_subject; + bool is_reply_or_forward; + + subject = imap_get_base_subject_cased(pool_datastack_create(), subject, + &is_reply_or_forward); + /* (ii) If the thread subject is empty, skip this message. */ + if (*subject == '\0') + return; + + /* (iii) Look up the message associated with the thread + subject in the subject table. */ + if (!hash_table_lookup_full(ctx->subject_hash, subject, &hash_subject, + &hash_node)) { + /* (iv) If there is no message in the subject table with the + thread subject, add the current message and the thread + subject to the subject table. */ + hash_subject = p_strdup(ctx->subject_pool, subject); + hash_table_insert(ctx->subject_hash, hash_subject, node); + } else { + /* Otherwise, if the message in the subject table is not a + dummy, AND either of the following criteria are true: + + The current message is a dummy, OR + + The message in the subject table is a reply or forward + and the current message is not. + + then replace the message in the subject table with the + current message. */ + if (!hash_node->dummy && + (node->dummy || + (hash_node->reply_or_forward && !is_reply_or_forward))) { + hash_node->parent_root_idx1 = node->root_idx1; + hash_table_update(ctx->subject_hash, hash_subject, node); + } else { + node->parent_root_idx1 = hash_node->root_idx1; + } + } + + node->reply_or_forward = is_reply_or_forward; +} + +static int mail_thread_child_node_cmp(const struct mail_thread_child_node *c1, + const struct mail_thread_child_node *c2) +{ + if (c1->sort_date < c2->sort_date) + return -1; + if (c1->sort_date > c2->sort_date) + return 1; + + if (c1->uid < c2->uid) + return -1; + if (c1->uid > c2->uid) + return 1; + return 0; +} + +static int mail_thread_root_node_cmp(const struct mail_thread_root_node *r1, + const struct mail_thread_root_node *r2) +{ + return mail_thread_child_node_cmp(&r1->node, &r2->node); +} + +static uint32_t +thread_lookup_existing(struct thread_finish_context *ctx, uint32_t idx) +{ + const struct mail_thread_node *node; + + node = array_idx(&ctx->cache->thread_nodes, idx); + i_assert(MAIL_THREAD_NODE_EXISTS(node)); + i_assert(node->uid != 0); + return node->uid; +} + +static void +thread_child_node_fill(struct thread_finish_context *ctx, + struct mail_thread_child_node *child) +{ + int tz; + + child->uid = thread_lookup_existing(ctx, child->idx); + + if (!mail_set_uid(ctx->tmp_mail, child->uid)) { + /* the UID should have existed. we would have rebuild + the thread tree otherwise. */ + i_unreached(); + } + + /* get sent date if we want to use it and if it's valid */ + if (!ctx->use_sent_date) + child->sort_date = 0; + else if (mail_get_date(ctx->tmp_mail, &child->sort_date, &tz) < 0) + child->sort_date = 0; + + if (child->sort_date == 0) { + /* fallback to received date */ + (void)mail_get_received_date(ctx->tmp_mail, &child->sort_date); + } +} + +static void +thread_sort_children(struct thread_finish_context *ctx, uint32_t parent_idx, + ARRAY_TYPE(mail_thread_child_node) *sorted_children) +{ + const struct mail_thread_shadow_node *shadows; + struct mail_thread_child_node child; + unsigned int count; + + i_zero(&child); + array_clear(sorted_children); + + /* add all child indexes to the array */ + shadows = array_get(&ctx->shadow_nodes, &count); + child.idx = shadows[parent_idx].first_child_idx; + i_assert(child.idx != 0); + if (shadows[child.idx].next_sibling_idx == 0) { + /* only child - don't bother setting sort date */ + child.uid = thread_lookup_existing(ctx, child.idx); + + array_push_back(sorted_children, &child); + return; + } + while (child.idx != 0) { + thread_child_node_fill(ctx, &child); + + array_push_back(sorted_children, &child); + child.idx = shadows[child.idx].next_sibling_idx; + } + + /* sort the children */ + array_sort(sorted_children, mail_thread_child_node_cmp); +} + +static void gather_base_subjects(struct thread_finish_context *ctx) +{ + struct subject_gather_context gather_ctx; + struct mail_thread_root_node *roots; + const char *subject; + unsigned int i, count; + ARRAY_TYPE(mail_thread_child_node) sorted_children; + const struct mail_thread_child_node *children; + uint32_t idx, uid; + + i_zero(&gather_ctx); + gather_ctx.ctx = ctx; + + roots = array_get_modifiable(&ctx->roots, &count); + if (count == 0) + return; + gather_ctx.subject_pool = + pool_alloconly_create(MEMPOOL_GROWING"base subjects", + nearest_power(count * 20)); + hash_table_create(&gather_ctx.subject_hash, gather_ctx.subject_pool, + count * 2, str_hash, strcmp); + + i_array_init(&sorted_children, 64); + for (i = 0; i < count; i++) { + roots[i].root_idx1 = i + 1; + if (!roots[i].dummy) + idx = roots[i].node.idx; + else if (!roots[i].ignore) { + /* find the oldest child */ + thread_sort_children(ctx, roots[i].node.idx, + &sorted_children); + children = array_front(&sorted_children); + idx = children[0].idx; + } else { + /* dummy without children */ + continue; + } + + uid = thread_lookup_existing(ctx, idx); + if (!mail_set_uid(ctx->tmp_mail, uid)) { + /* the UID should have existed. we would have rebuild + the thread tree otherwise. */ + i_unreached(); + } + if (mail_get_first_header(ctx->tmp_mail, HDR_SUBJECT, + &subject) > 0) T_BEGIN { + add_base_subject(&gather_ctx, subject, &roots[i]); + } T_END; + } + i_assert(roots[count-1].parent_root_idx1 <= count); + array_free(&sorted_children); + hash_table_destroy(&gather_ctx.subject_hash); + pool_unref(&gather_ctx.subject_pool); +} + +static void thread_add_shadow_child(struct thread_finish_context *ctx, + uint32_t parent_idx, uint32_t child_idx) +{ + struct mail_thread_shadow_node *parent_shadow, *child_shadow; + + parent_shadow = array_idx_get_space(&ctx->shadow_nodes, parent_idx); + child_shadow = array_idx_modifiable(&ctx->shadow_nodes, child_idx); + + child_shadow->next_sibling_idx = parent_shadow->first_child_idx; + parent_shadow->first_child_idx = child_idx; +} + +static void mail_thread_root_thread_merge(struct thread_finish_context *ctx, + struct mail_thread_root_node *cur) +{ + struct mail_thread_root_node *roots, *root, new_root; + struct mail_thread_shadow_node *shadows; + unsigned int count; + uint32_t idx, next_idx; + + i_assert(cur->parent_root_idx1 != 0); + + /* The highest parent is the same as the current message in the + subject table. */ + roots = array_get_modifiable(&ctx->roots, &count); + root = cur; + do { + i_assert(root->parent_root_idx1 <= count); + root = &roots[root->parent_root_idx1 - 1]; + } while (root->parent_root_idx1 != 0); + i_assert(!root->ignore); + + shadows = array_front_modifiable(&ctx->shadow_nodes); + if (cur->dummy) { + /* If both messages are dummies, append the current + message's children to the children of the message in + the subject table (the children of both messages + become siblings), and then delete the current message. */ + i_assert(root->dummy); + + idx = shadows[cur->node.idx].first_child_idx; + while (idx != 0) { + next_idx = shadows[idx].next_sibling_idx; + thread_add_shadow_child(ctx, root->node.idx, idx); + idx = next_idx; + } + + shadows[cur->node.idx].first_child_idx = 0; + cur->ignore = TRUE; + } else if (root->dummy || (cur->reply_or_forward && + !root->reply_or_forward)) { + /* a) If the message in the subject table is a dummy and the + current message is not, make the current message a + child of the message in the subject table (a sibling + of its children). + + b) If the current message is a reply or forward and the + message in the subject table is not, make the current + message a child of the message in the subject table (a + sibling of its children). */ + thread_add_shadow_child(ctx, root->node.idx, cur->node.idx); + cur->ignore = TRUE; + } else { + /* Otherwise, create a new dummy message and make both + the current message and the message in the subject + table children of the dummy. Then replace the message + in the subject table with the dummy message. */ + i_zero(&new_root); + new_root.root_idx1 = array_count(&ctx->roots) + 1; + new_root.node.idx = ctx->next_new_root_idx++; + new_root.dummy = TRUE; + + thread_add_shadow_child(ctx, new_root.node.idx, root->node.idx); + thread_add_shadow_child(ctx, new_root.node.idx, cur->node.idx); + + root->parent_root_idx1 = new_root.root_idx1; + root->ignore = TRUE; + cur->ignore = TRUE; + + /* append last, since it breaks root and cur pointers */ + array_push_back(&ctx->roots, &new_root); + + /* make sure all shadow indexes are accessible directly */ + (void)array_idx_modifiable(&ctx->shadow_nodes, + new_root.node.idx); + } +} + +static bool merge_subject_threads(struct thread_finish_context *ctx) +{ + struct mail_thread_root_node *roots; + unsigned int i, count; + bool changed = FALSE; + + roots = array_get_modifiable(&ctx->roots, &count); + for (i = 0; i < count; i++) { + if (roots[i].parent_root_idx1 != 0 && !roots[i].ignore) { + mail_thread_root_thread_merge(ctx, &roots[i]); + /* more roots may have been added */ + roots = array_front_modifiable(&ctx->roots); + changed = TRUE; + } + } + + return changed; +} + +static void sort_root_nodes(struct thread_finish_context *ctx) +{ + ARRAY_TYPE(mail_thread_child_node) sorted_children; + const struct mail_thread_child_node *children; + const struct mail_thread_shadow_node *shadows; + struct mail_thread_root_node *roots; + unsigned int i, count, child_count; + + i_array_init(&sorted_children, 64); + shadows = array_front(&ctx->shadow_nodes); + roots = array_get_modifiable(&ctx->roots, &count); + for (i = 0; i < count; i++) { + if (roots[i].ignore) + continue; + if (roots[i].dummy) { + /* sort by the first child */ + if (shadows[roots[i].node.idx].first_child_idx == 0) { + /* childless dummy node */ + roots[i].ignore = TRUE; + continue; + } + thread_sort_children(ctx, roots[i].node.idx, + &sorted_children); + children = array_get(&sorted_children, &child_count); + if (child_count == 1) { + /* only one child - deferred step (3). + promote the child to the root. */ + roots[i].node = children[0]; + thread_child_node_fill(ctx, &roots[i].node); + roots[i].dummy = FALSE; + } else { + roots[i].node.uid = children[0].uid; + roots[i].node.sort_date = children[0].sort_date; + } + } else { + thread_child_node_fill(ctx, &roots[i].node); + } + } + array_free(&sorted_children); + array_sort(&ctx->roots, mail_thread_root_node_cmp); +} + +static int mail_thread_root_node_idx_cmp(const void *key, const void *value) +{ + const uint32_t *idx = key; + const struct mail_thread_root_node *root = value; + + return *idx < root->node.idx ? -1 : + *idx > root->node.idx ? 1 : 0; +} + +static void sort_root_nodes_ref2(struct thread_finish_context *ctx, + uint32_t record_count) +{ + const struct mail_thread_node *node; + struct mail_thread_root_node *roots, *root; + struct mail_thread_child_node child; + const struct mail_thread_shadow_node *shadows; + unsigned int root_count; + uint32_t idx, parent_idx; + + roots = array_get_modifiable(&ctx->roots, &root_count); + + /* drop childless dummy nodes */ + shadows = array_front(&ctx->shadow_nodes); + for (idx = 1; idx < root_count; idx++) { + if (roots[idx].dummy && + shadows[roots[idx].node.idx].first_child_idx == 0) + roots[idx].ignore = TRUE; + } + + for (idx = 1; idx < record_count; idx++) { + node = array_idx(&ctx->cache->thread_nodes, idx); + if (!MAIL_THREAD_NODE_EXISTS(node)) + continue; + + child.idx = idx; + thread_child_node_fill(ctx, &child); + + parent_idx = idx; + while (node->parent_idx != 0) { + parent_idx = node->parent_idx; + node = array_idx(&ctx->cache->thread_nodes, + node->parent_idx); + } + root = bsearch(&parent_idx, roots, root_count, sizeof(*roots), + mail_thread_root_node_idx_cmp); + i_assert(root != NULL); + + if (root->node.sort_date < child.sort_date) + root->node.sort_date = child.sort_date; + } + array_sort(&ctx->roots, mail_thread_root_node_cmp); +} + +static void mail_thread_create_shadows(struct thread_finish_context *ctx, + uint32_t record_count) +{ + const struct mail_thread_node *node, *parent; + struct mail_thread_root_node root; + struct mail_thread_child_node child; + uint32_t idx, parent_idx; + + ctx->use_sent_date = FALSE; + + i_zero(&root); + i_zero(&child); + + /* We may see dummy messages without parents or children. We can't + free them since the nodes are in an array, but they may get reused + later so just leave them be. With the current algorithm when this + happens all the struct fields are always zero at that point, so + we don't even have to try to zero them. */ + for (idx = 1; idx < record_count; idx++) { + node = array_idx(&ctx->cache->thread_nodes, idx); + + if (node->parent_idx == 0) { + /* root node - add to roots list */ + root.node.idx = idx; + if (!MAIL_THREAD_NODE_EXISTS(node)) { + root.dummy = TRUE; + root.node.uid = 0; + } else { + root.dummy = FALSE; + root.node.uid = node->uid; + } + array_push_back(&ctx->roots, &root); + continue; + } + i_assert(node->parent_idx < record_count); + + if (!MAIL_THREAD_NODE_EXISTS(node)) { + /* dummy node */ + continue; + } + + /* Find the node's first non-dummy parent and add the + node as its child. If there are no non-dummy + parents, add it as the highest dummy's child. */ + parent_idx = node->parent_idx; + parent = array_idx(&ctx->cache->thread_nodes, parent_idx); + while (!MAIL_THREAD_NODE_EXISTS(parent) && + parent->parent_idx != 0) { + parent_idx = parent->parent_idx; + parent = array_idx(&ctx->cache->thread_nodes, + parent_idx); + } + thread_add_shadow_child(ctx, parent_idx, idx); + } +} + +static void mail_thread_finish(struct thread_finish_context *ctx, + enum mail_thread_type thread_type) +{ + unsigned int record_count = array_count(&ctx->cache->thread_nodes); + + ctx->next_new_root_idx = record_count + 1; + + /* (2) save root nodes and (3) remove dummy messages */ + i_array_init(&ctx->roots, I_MIN(128, record_count)); + i_array_init(&ctx->shadow_nodes, record_count); + /* make sure all shadow indexes are accessible directly. */ + (void)array_idx_get_space(&ctx->shadow_nodes, record_count); + + mail_thread_create_shadows(ctx, record_count); + + /* (4) */ + ctx->use_sent_date = TRUE; + switch (thread_type) { + case MAIL_THREAD_REFERENCES: + sort_root_nodes(ctx); + /* (5) Gather together messages under the root that have + the same base subject text. */ + gather_base_subjects(ctx); + /* (5.C) Merge threads with the same thread subject. */ + if (merge_subject_threads(ctx)) { + /* root ordering may have changed, sort them again. */ + sort_root_nodes(ctx); + } + break; + case MAIL_THREAD_REFS: + sort_root_nodes_ref2(ctx, record_count); + break; + default: + i_unreached(); + } +} + +static void +nodes_change_uids_to_seqs(struct mail_thread_iterate_context *iter, bool root) +{ + struct mail_thread_child_node *children; + struct mailbox *box = iter->ctx->tmp_mail->box; + unsigned int i, count; + uint32_t uid, seq; + + children = array_get_modifiable(&iter->children, &count); + for (i = 0; i < count; i++) { + uid = children[i].uid; + if (uid == 0) { + /* dummy root */ + if (root) + continue; + i_unreached(); + } else { + mailbox_get_seq_range(box, uid, uid, &seq, &seq); + i_assert(seq != 0); + } + children[i].uid = seq; + } +} + +static void +mail_thread_iterate_fill_root(struct mail_thread_iterate_context *iter) +{ + struct mail_thread_root_node *roots; + unsigned int i, count; + + roots = array_get_modifiable(&iter->ctx->roots, &count); + i_array_init(&iter->children, count); + for (i = 0; i < count; i++) { + if (!roots[i].ignore) { + if (roots[i].dummy) + roots[i].node.uid = 0; + array_push_back(&iter->children, &roots[i].node); + } + } +} + +static struct mail_thread_iterate_context * +mail_thread_iterate_children(struct mail_thread_iterate_context *parent_iter, + uint32_t parent_idx) +{ + struct mail_thread_iterate_context *child_iter; + + child_iter = i_new(struct mail_thread_iterate_context, 1); + child_iter->ctx = parent_iter->ctx; + child_iter->ctx->refcount++; + + i_array_init(&child_iter->children, 8); + struct event_reason *reason = event_reason_begin("mailbox:thread"); + thread_sort_children(child_iter->ctx, parent_idx, + &child_iter->children); + if (child_iter->ctx->return_seqs) + nodes_change_uids_to_seqs(child_iter, FALSE); + event_reason_end(&reason); + return child_iter; +} + +struct mail_thread_iterate_context * +mail_thread_iterate_init_full(struct mail_thread_cache *cache, + struct mail *tmp_mail, + enum mail_thread_type thread_type, + bool return_seqs) +{ + struct mail_thread_iterate_context *iter; + struct thread_finish_context *ctx; + + iter = i_new(struct mail_thread_iterate_context, 1); + ctx = iter->ctx = i_new(struct thread_finish_context, 1); + ctx->refcount = 1; + ctx->cache = cache; + ctx->tmp_mail = tmp_mail; + ctx->return_seqs = return_seqs; + + struct event_reason *reason = event_reason_begin("mailbox:thread"); + mail_thread_finish(ctx, thread_type); + + mail_thread_iterate_fill_root(iter); + if (return_seqs) + nodes_change_uids_to_seqs(iter, TRUE); + event_reason_end(&reason); + return iter; +} + +const struct mail_thread_child_node * +mail_thread_iterate_next(struct mail_thread_iterate_context *iter, + struct mail_thread_iterate_context **child_iter_r) +{ + const struct mail_thread_child_node *children, *child; + const struct mail_thread_shadow_node *shadow; + unsigned int count; + + children = array_get(&iter->children, &count); + if (iter->next_idx >= count) + return NULL; + + child = &children[iter->next_idx++]; + shadow = array_idx(&iter->ctx->shadow_nodes, child->idx); + *child_iter_r = shadow->first_child_idx == 0 ? NULL : + mail_thread_iterate_children(iter, child->idx); + if (child->uid == 0 && *child_iter_r == NULL) { + /* this is a dummy node without children, + there's no point in returning it */ + return mail_thread_iterate_next(iter, child_iter_r); + } + return child; +} + +unsigned int mail_thread_iterate_count(struct mail_thread_iterate_context *iter) +{ + return array_count(&iter->children); +} + +int mail_thread_iterate_deinit(struct mail_thread_iterate_context **_iter) +{ + struct mail_thread_iterate_context *iter = *_iter; + + *_iter = NULL; + + if (--iter->ctx->refcount == 0) { + array_free(&iter->ctx->roots); + array_free(&iter->ctx->shadow_nodes); + i_free(iter->ctx); + } + array_free(&iter->children); + i_free(iter); + return 0; +} |