From b226c0a68fb89c074b5c5655e9469d692f71c988 Mon Sep 17 00:00:00 2001 From: Not Zed Date: Thu, 6 Jul 2000 05:03:57 +0000 Subject: Code for message threading. 2000-07-06 Not Zed * message-thread.[ch]: Code for message threading. svn path=/trunk/; revision=3916 --- mail/ChangeLog | 4 + mail/Makefile.am | 2 + mail/message-thread.c | 506 ++++++++++++++++++++++++++++++++++++++++++++++++++ mail/message-thread.h | 20 ++ 4 files changed, 532 insertions(+) create mode 100644 mail/message-thread.c create mode 100644 mail/message-thread.h (limited to 'mail') diff --git a/mail/ChangeLog b/mail/ChangeLog index dee175d84d..8169830a2b 100644 --- a/mail/ChangeLog +++ b/mail/ChangeLog @@ -1,3 +1,7 @@ +2000-07-06 Not Zed + + * message-thread.[ch]: Code for message threading. + 2000-07-05 Dan Winship * mail-identify.c (mail_identify_mime_part): Oops. My gnome-vfs diff --git a/mail/Makefile.am b/mail/Makefile.am index dce2a11a03..e92223bb5b 100644 --- a/mail/Makefile.am +++ b/mail/Makefile.am @@ -51,6 +51,8 @@ evolution_mail_SOURCES = \ main.c \ message-list.c \ message-list.h \ + message-thread.c \ + message-thread.h \ session.c \ mail.h diff --git a/mail/message-thread.c b/mail/message-thread.c new file mode 100644 index 0000000000..153cc75015 --- /dev/null +++ b/mail/message-thread.c @@ -0,0 +1,506 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* + * Copyright (C) 2000 Helix Code Inc. + * + * Authors: Michael Zucchi + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ + +#include "camel/camel.h" +#include +#include +#include +#include +#include +#include +#include + +#include "message-thread.h" + +#define d(x) + +int dump_tree(struct _container *c, int depth); + +static void +container_add_child(struct _container *node, struct _container *child) +{ + d(printf("\nAdding child %p to parent %p \n", child, node)); + child->next = node->child; + node->child = child; + child->parent = node; +} + +static void +container_unparent_child(struct _container *child) +{ + struct _container *c, *p = NULL, *last, *node; + + /* are we unparented? */ + if (child->parent == NULL) { + return; + } + + /* else remove child from its existing parent, and reparent */ + node = child->parent; + c = (struct _container *)&node->child; + d(printf("scanning children:\n")); + while (c->next) { + d(printf(" %p\n", c)); + if (c->next==child) { + d(printf("found node %p\n", child)); + c->next = c->next->next; + child->parent = NULL; + return; + } + c = c->next; + } + + printf("DAMN, we shouldn't be here!\n"); +} + +static void +container_parent_child(struct _container *parent, struct _container *child) +{ + struct _container *c, *p = NULL, *last, *node; + + /* are we already the right parent? */ + if (child->parent == parent) + return; + + /* are we unparented? */ + if (child->parent == NULL) { + container_add_child(parent, child); + return; + } + + /* else remove child from its existing parent, and reparent */ + node = child->parent; + c = (struct _container *)&node->child; + d(printf("scanning children:\n")); + while (c->next) { + d(printf(" %p\n", c)); + if (c->next==child) { + d(printf("found node %p\n", child)); + c->next = c->next->next; + child->parent = NULL; + container_add_child(parent, child); + return; + } + c = c->next; + } + + printf("DAMN, we shouldn't be here!\n"); +} + +static void +prune_empty(struct _container **cp) +{ + struct _container *child, *next, *nextc, *c, *lastc; + + /* yes, this is intentional */ + lastc = (struct _container *)cp; + while (lastc->next) { + c = lastc->next; + + d(printf("checking message %p %p (%s)\n", c, + c->message, c->message?c->message->message_id:"")); + if (c->message == NULL) { + if (c->child == NULL) { + d(printf("removing empty node\n")); + lastc->next = c->next; + continue; + } + if (c->parent || c->child->next==0) { + d(printf("promoting child\n")); + lastc->next = c->next; /* remove us */ + child = c->child; + while (child) { + next = child->next; + + child->parent = c->parent; + child->next = lastc->next; + lastc->next = child; + + child = next; + } + continue; + } + } + prune_empty(&c->child); + lastc = c; + } +} + +static void +hashloop(void *key, void *value, void *data) +{ + struct _container *c = value; + char *keystr = key; + struct _container *tail = data; + + if (c->parent == NULL) { + c->next = tail->next; + tail->next = c; + } +} + +static char * +get_root_subject(struct _container *c, int *re) +{ + char *s, *p; + struct _container *scan; + + s = NULL; + *re = FALSE; + if (c->message) + s = c->message->subject; + else { + /* one of the children will always have a message */ + scan = c->child; + while (scan) { + if (scan->message) { + s = scan->message->subject; + break; + } + scan = scan->next; + } + } + if (s != NULL) { + while (*s) { + char cc; + while (isspace(*s)) + s++; + if (s[0] == 0) + break; + if ((s[0] == 'r' || s[0]=='R') + && (s[1] == 'e' || s[1]=='E')) { + p = s+2; + while (ispunct(*p) || isdigit(*p) && *p != ':') + p++; + if (*p==':') { + *re = TRUE; + s = p+1; + } else + break; + } else + break; + } + if (*s) + return s; + } + return NULL; +} + +/* this is pretty slow, but not used often */ +static void +remove_node(struct _container **list, struct _container *node) +{ + struct _container *c; + + /* this is intentional, even if it looks funny */ + c = (struct _container *)list; + while (c->next) { + if (c->next == node) { + c->next = c->next->next; + break; + } + c = c->next; + } +} + +static void +group_root_set(struct _container **cp) +{ + GHashTable *subject_table = g_hash_table_new(g_str_hash, g_str_equal); + struct _container *c, *clast, *scan, *container; + char *s; + int re; + + /* gather subject lines */ + d(printf("gathering subject lines\n")); + clast = (struct _container *)cp; + c = clast->next; + while (c) { + c->root_subject = get_root_subject(c, &c->re); + if (c->root_subject) { + container = g_hash_table_lookup(subject_table, c->root_subject); + if (container == NULL + || (container->message == NULL && c->message) + || (container->re == TRUE && !c->re)) { + g_hash_table_insert(subject_table, c->root_subject, c); + } + } + c = c->next; + } + + /* merge common subjects? */ + clast = (struct _container *)cp; + while (clast->next) { + c = clast->next; + d(printf("checking %p %s\n", c, c->root_subject)); + if (c->root_subject + && (container = g_hash_table_lookup(subject_table, c->root_subject)) + && (container != c)) { + d(printf(" matching %p %s\n", container, container->root_subject)); + if (c->message == NULL && container->message == NULL) { + d(printf("merge containers children\n")); + /* steal the children from c onto container, and unlink c */ + scan = (struct _container *)&container->child; + while (scan->next) + scan = scan->next; + scan->next = c->child; + clast->next = c->next; + continue; + } if (c->message == NULL && container->message != NULL) { + d(printf("container is non-empty parent\n")); + remove_node(cp, container); + container_add_child(c, container); + } else if (c->message != NULL && container->message == NULL) { + d(printf("container is empty child\n")); + clast->next = c->next; + container_add_child(container, c); + continue; + } else if (c->re && !container->re) { + d(printf("container is re\n")); + clast->next = c->next; + container_add_child(container, c); + continue; + } else if (!c->re && container->re) { + d(printf("container is not re\n")); + remove_node(cp, container); + container_add_child(c, container); + } else { + d(printf("subjects are common %p and %p\n", c, container)); + + remove_node(cp, container); + + scan = g_malloc0(sizeof(*scan)); + scan->root_subject = c->root_subject; + scan->re = c->re && container->re; + scan->next = c->next; + clast->next = scan; + container_add_child(scan, c); + container_add_child(scan, container); + clast = scan; + g_hash_table_insert(subject_table, scan->root_subject, scan); + continue; + } + } + clast = c; + } + g_hash_table_destroy(subject_table); +} + +int +dump_tree(struct _container *c, int depth) +{ + char *p; + struct _container *child; + int count=0; + + p = alloca(depth*2+1); + memset(p, ' ', depth*2); + p[depth*2] = 0; + + while (c) { + if (c->message) { + printf("%s %p Subject: %s <%s>\n", p, c, c->message->subject, c->message->message_id); + count += 1; + } else { + printf("%s %p \n", p, c); + } + if (c->child) + count += dump_tree(c->child, depth+1); + c = c->next; + } + return count; +} + +void thread_messages_free(struct _container *head) +{ + printf("FIXME: Free message thread structure\n"); +} + +struct _container * +thread_messages(CamelMessageInfo **messages, int count) +{ + GHashTable *id_table; + int i, msgs; + struct _container *c, *p, *child, *head, *scan, *container; + struct _header_references *ref; + + id_table = g_hash_table_new(g_str_hash, g_str_equal); + for (i=0;imessage_id) { + d(printf("doing : %s\n", mi->message_id)); + c = g_hash_table_lookup(id_table, mi->message_id); + if (c) { + c->message = mi; + } else { + c = g_malloc0(sizeof(*c)); + c->message = mi; + g_hash_table_insert(id_table, mi->message_id, c); + } + container = c; + ref = mi->references; + p = NULL; + child = container; + head = NULL; + d(printf("referencfes: ")); + while (ref) { + d(printf(" %s\n", ref->id)); + if (ref->id == NULL) { + printf("FUCK!?\n"); + ref = ref->next; + continue; + } + d(printf("looking up reference: %s\n", ref->id)); + c = g_hash_table_lookup(id_table, ref->id); + if (c == NULL) { + d(printf("not found\n")); + c = g_malloc0(sizeof(*c)); + g_hash_table_insert(id_table, ref->id, c); + } + if (c!=child) { + container_parent_child(c, child); + } + child = c; + if (head == NULL) + head = c; + ref = ref->next; + } + d(printf("\n")); + } else { + printf("No message id???\n"); + /* ?? */ + } + } + + d(printf("\n\n")); + /* build a list of root messages (no parent) */ + head = NULL; + g_hash_table_foreach(id_table, hashloop, &head); + + g_hash_table_destroy(id_table); + + /* remove empty parent nodes */ + prune_empty(&head); + + /* find any siblings which missed out */ + group_root_set(&head); + + printf("finished\n"); + i = dump_tree(head, 0); + printf("%d count, %d msgs initially, %d items in tree\n", count, msgs, i); + + return head; +} + +#ifdef STANDALONE + +static char * +auth_callback(char *prompt, gboolean secret, + CamelService *service, char *item, + CamelException *ex) +{ + printf ("auth_callback called: %s\n", prompt); + return NULL; +} + +int +main (int argc, char**argv) +{ + CamelSession *session; + CamelException *ex; + CamelStore *store; + gchar *store_url = "mbox:///home/notzed/evolution/local/Inbox"; + CamelFolder *folder; + CamelMimeMessage *message; + GList *uid_list; + GPtrArray *summary; + + gtk_init (&argc, &argv); + camel_init (); + ex = camel_exception_new (); + + session = camel_session_new (auth_callback); + store = camel_session_get_store (session, store_url, ex); + if (camel_exception_get_id (ex)) { + printf ("Exception caught in camel_session_get_store\n" + "Full description : %s\n", camel_exception_get_description (ex)); + return -1; + } + + folder = camel_store_get_folder (store, "mbox", TRUE, ex); + if (camel_exception_get_id (ex)) { + printf ("Exception caught in camel_store_get_folder\n" + "Full description : %s\n", camel_exception_get_description (ex)); + return -1; + } + +#if 0 + camel_folder_open (folder, FOLDER_OPEN_RW, ex); + if (camel_exception_get_id (ex)) { + printf ("Exception caught when trying to open the folder\n" + "Full description : %s\n", camel_exception_get_description (ex)); + return -1; + } +#endif + + summary = camel_folder_get_summary(folder, ex); + thread_messages((CamelMessageInfo **)summary->pdata, summary->len); + + return 0; +} + +#endif + +/* + + msgid: d + references: a b c + + msgid: f + references: c d + + msgid: e + references: c + + a + \ + b + \ + c + \ + d + |\ + e f + */ +/* + lookup d + create new node d + child = d + loop on c b a + lookup node? + if no node, create node + add child to node + child = node + endloop + + */ diff --git a/mail/message-thread.h b/mail/message-thread.h new file mode 100644 index 0000000000..6c3eaad79a --- /dev/null +++ b/mail/message-thread.h @@ -0,0 +1,20 @@ +#ifndef _MESSAGE_THREAD_H +#define _MESSAGE_THREAD_H + +struct _container { + struct _container *next, + *parent, + *child; + CamelMessageInfo *message; + char *root_subject; /* cached root equivalent subject */ + int re; /* re version of subject? */ +}; + +struct _container *thread_messages(CamelMessageInfo **messages, int count); +void thread_messages_free(struct _container *); + +/* for debug only */ +int dump_tree(struct _container *c, int depth); + +#endif /* !_MESSAGE_THREAD_H */ + -- cgit v1.2.3