--- a/src/dsync/dsync-brain.c	Wed Jul 15 18:29:58 2009 -0400
+++ b/src/dsync/dsync-brain.c	Wed Jul 15 18:31:59 2009 -0400
@@ -3,6 +3,7 @@
 #include "lib.h"
 #include "array.h"
 #include "hash.h"
+#include "hex-binary.h"
 #include "master-service.h"
 #include "dsync-worker.h"
 #include "dsync-brain-private.h"
@@ -216,48 +217,91 @@
 		dsync_worker_msg_update_metadata(brain->dest_worker, src_msg);
 }
 
+static const char *
+get_guid_128_str(const char *guid, unsigned char *dest, unsigned int dest_len)
+{
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
+	buffer_t guid_128_buf;
+
+	buffer_create_data(&guid_128_buf, dest, dest_len);
+	mail_generate_guid_128_hash(guid, guid_128);
+	binary_to_hex_append(&guid_128_buf, guid_128, sizeof(guid_128));
+	buffer_append_c(&guid_128_buf, '\0');
+	return guid_128_buf.data;
+}
+
 static int dsync_brain_msg_sync_pair(struct dsync_brain_mailbox_sync *sync)
 {
 	struct dsync_message *src_msg = &sync->src_msg_iter->msg;
 	struct dsync_message *dest_msg = &sync->dest_msg_iter->msg;
 	struct dsync_mailbox *const *boxp;
 	struct dsync_brain_uid_conflict *conflict;
+	const char *src_guid, *dest_guid;
+	unsigned char guid_128_data[MAIL_GUID_128_SIZE * 2 + 1];
+	bool src_expunged, dest_expunged;
+
+	src_expunged = (src_msg->flags & DSYNC_MAIL_FLAG_EXPUNGED) != 0;
+	dest_expunged = (dest_msg->flags & DSYNC_MAIL_FLAG_EXPUNGED) != 0;
+
+	if (src_expunged) {
+		src_guid = src_msg->guid;
+		dest_guid = get_guid_128_str(dest_msg->guid, guid_128_data,
+					     sizeof(guid_128_data));
+	} else if (dest_expunged) {
+		src_guid = get_guid_128_str(src_msg->guid, guid_128_data,
+					    sizeof(guid_128_data));
+		dest_guid = dest_msg->guid;
+	} else {
+		src_guid = src_msg->guid;
+		dest_guid = dest_msg->guid;
+	}
 
 	if (src_msg->uid < dest_msg->uid) {
 		/* message has been expunged from dest. ignore it, unless
 		   we're in uid-conflict mode. */
-		if (sync->uid_conflict)
+		if (sync->uid_conflict && !src_expunged)
 			dsync_brain_msg_sync_save_source(sync);
 		src_msg->guid = NULL;
+		return 0;
 	} else if (src_msg->uid > dest_msg->uid) {
 		/* message has been expunged from src. expunge it from dest
 		   too, unless we're in uid-conflict mode. */
-		if (!sync->uid_conflict) {
+		if (!sync->uid_conflict && !dest_expunged) {
 			dsync_worker_msg_expunge(sync->brain->dest_worker,
 						 dest_msg->uid);
 		}
 		dest_msg->guid = NULL;
-	} else if (strcmp(src_msg->guid, dest_msg->guid) == 0) {
-		/* message exists, sync metadata */
-		dsync_brain_msg_sync_existing(sync->brain, src_msg, dest_msg);
-		src_msg->guid = NULL;
-		dest_msg->guid = NULL;
-	} else {
-		/* UID conflict. change UID in destination */
+		return 0;
+	}
+
+	/* UIDs match, but do GUIDs? */
+	if (strcmp(src_guid, dest_guid) != 0) {
+		/* UID conflict. give new UIDs to messages in both src and
+		   dest (if they're not expunged already) */
 		sync->uid_conflict = TRUE;
-		conflict = array_append_space(&sync->uid_conflicts);
-		conflict->mailbox_idx = sync->src_msg_iter->mailbox_idx;
-		conflict->uid = dest_msg->uid;
-
-		/* give new UID for the source message message too. */
-		boxp = array_idx(&sync->brain->src_mailbox_list->mailboxes,
-				 conflict->mailbox_idx);
-		src_msg->uid = (*boxp)->uid_next++;
-
-		dsync_brain_msg_sync_save_source(sync);
-		src_msg->guid = NULL;
-		dest_msg->guid = NULL;
+		if (!dest_expunged) {
+			conflict = array_append_space(&sync->uid_conflicts);
+			conflict->mailbox_idx = sync->src_msg_iter->mailbox_idx;
+			conflict->uid = dest_msg->uid;
+		}
+		if (!src_expunged) {
+			boxp = array_idx(&sync->brain->src_mailbox_list->mailboxes,
+					 conflict->mailbox_idx);
+			src_msg->uid = (*boxp)->uid_next++;
+			dsync_brain_msg_sync_save_source(sync);
+		}
+	} else if (dest_expunged) {
+		/* message expunged from destination, we can skip this. */
+	} else if (src_expunged) {
+		/* message expunged from source, expunge from destination too */
+		dsync_worker_msg_expunge(sync->brain->dest_worker,
+					 dest_msg->uid);
+	} else {
+		/* message exists in both source and dest, sync metadata */
+		dsync_brain_msg_sync_existing(sync->brain, src_msg, dest_msg);
 	}
+	src_msg->guid = NULL;
+	dest_msg->guid = NULL;
 	return 0;
 }
 

--- a/src/dsync/dsync-data.h	Wed Jul 15 18:29:58 2009 -0400
+++ b/src/dsync/dsync-data.h	Wed Jul 15 18:31:59 2009 -0400
@@ -15,6 +15,11 @@
 	uint64_t highest_modseq;
 };
 
+/* dsync_worker_msg_iter_next() returns also all expunged messages from
+   the end of mailbox with this flag set. The GUIDs are 128 bit GUIDs saved
+   to transaction log (mail_generate_guid_128_hash()). */
+#define DSYNC_MAIL_FLAG_EXPUNGED 0x10000000
+
 struct dsync_message {
 	const char *guid;
 	uint32_t uid;

--- a/src/dsync/dsync-proxy.c	Wed Jul 15 18:29:58 2009 -0400
+++ b/src/dsync/dsync-proxy.c	Wed Jul 15 18:31:59 2009 -0400
@@ -18,7 +18,9 @@
 	str_tabescape_write(str, msg->guid);
 	str_printfa(str, "\t%u\t%llu\t", msg->uid,
 		    (unsigned long long)msg->modseq);
-	imap_write_flags(str, msg->flags & ~MAIL_RECENT, msg->keywords);
+	if ((msg->flags & DSYNC_MAIL_FLAG_EXPUNGED) != 0)
+		str_append(str, "\\dsync-expunged ");
+	imap_write_flags(str, msg->flags & MAIL_FLAGS_NONRECENT, msg->keywords);
 	str_printfa(str, "\t%ld", (long)msg->save_date);
 }
 
@@ -31,15 +33,17 @@
 
 	msg_r->flags = 0;
 	p_array_init(&keywords, pool, 16);
-	for (args = t_strsplit(str, " "); *args != NULL; args++) {
-		if (**args == '\\') {
+	for (args = t_strsplit_spaces(str, " "); *args != NULL; args++) {
+		if (**args != '\\') {
+			kw = p_strdup(pool, *args);
+			array_append(&keywords, &kw, 1);
+		} else if (strcasecmp(*args, "\\dsync-expunged") == 0) {
+			msg_r->flags |= DSYNC_MAIL_FLAG_EXPUNGED;
+		} else {
 			flag = imap_parse_system_flag(*args);
 			if (flag == 0)
 				return -1;
 			msg_r->flags |= flag;
-		} else {
-			kw = p_strdup(pool, *args);
-			array_append(&keywords, &kw, 1);
 		}
 	}
 	(void)array_append_space(&keywords);

--- a/src/dsync/dsync-worker-local.c	Wed Jul 15 18:29:58 2009 -0400
+++ b/src/dsync/dsync-worker-local.c	Wed Jul 15 18:31:59 2009 -0400
@@ -4,6 +4,7 @@
 #include "array.h"
 #include "aqueue.h"
 #include "hash.h"
+#include "str.h"
 #include "hex-binary.h"
 #include "istream.h"
 #include "mail-user.h"
@@ -24,6 +25,11 @@
 
 	struct mail_search_context *search_ctx;
 	struct mail *mail;
+
+	string_t *tmp_guid_str;
+	ARRAY_TYPE(mailbox_expunge_rec) expunges;
+	unsigned int expunge_idx;
+	unsigned int expunges_set:1;
 };
 
 struct local_dsync_mailbox {
@@ -327,6 +333,7 @@
 	struct mailbox *box = iter->mail->box;
 	struct mailbox_transaction_context *trans = iter->mail->transaction;
 
+	iter->expunges_set = FALSE;
 	mail_free(&iter->mail);
 	if (mailbox_search_deinit(&iter->search_ctx) < 0) {
 		struct mail_storage *storage =
@@ -356,10 +363,59 @@
 		memcpy(iter->mailboxes[i].guid, &mailboxes[i],
 		       sizeof(iter->mailboxes[i].guid));
 	}
+	i_array_init(&iter->expunges, 32);
+	iter->tmp_guid_str = str_new(default_pool, MAIL_GUID_128_SIZE * 2 + 1);
 	(void)iter_local_mailbox_open(iter);
 	return &iter->iter;
 }
 
+static bool
+iter_local_mailbox_next_expunge(struct local_dsync_worker_msg_iter *iter,
+				uint32_t prev_uid, struct dsync_message *msg_r)
+{
+	struct mailbox *box = iter->mail->box;
+	struct mailbox_status status;
+	const struct mailbox_expunge_rec *expunges;
+	unsigned int count;
+
+	if (iter->expunges_set) {
+		expunges = array_get(&iter->expunges, &count);
+		if (iter->expunge_idx == count)
+			return FALSE;
+
+		memset(msg_r, 0, sizeof(*msg_r));
+		str_truncate(iter->tmp_guid_str, 0);
+		binary_to_hex_append(iter->tmp_guid_str,
+				     expunges[iter->expunge_idx].guid_128,
+				     MAIL_GUID_128_SIZE);
+		msg_r->guid = str_c(iter->tmp_guid_str);
+		msg_r->uid = expunges[iter->expunge_idx].uid;
+		iter->expunge_idx++;
+		return TRUE;
+	}
+
+	iter->expunge_idx = 0;
+	array_clear(&iter->expunges);
+	iter->expunges_set = TRUE;
+
+	mailbox_get_status(box, STATUS_UIDNEXT, &status);
+	if (prev_uid + 1 >= status.uidnext) {
+		/* no expunged messages at the end of mailbox */
+		return FALSE;
+	}
+
+	T_BEGIN {
+		ARRAY_TYPE(seq_range) uids_filter;
+
+		t_array_init(&uids_filter, 1);
+		seq_range_array_add_range(&uids_filter, prev_uid + 1,
+					  status.uidnext - 1);
+		(void)mailbox_get_expunges(box, 0, &uids_filter,
+					   &iter->expunges);
+	} T_END;
+	return iter_local_mailbox_next_expunge(iter, prev_uid, msg_r);
+}
+
 static int
 local_worker_msg_iter_next(struct dsync_worker_msg_iter *_iter,
 			   unsigned int *mailbox_idx_r,
@@ -368,12 +424,18 @@
 	struct local_dsync_worker_msg_iter *iter =
 		(struct local_dsync_worker_msg_iter *)_iter;
 	const char *guid;
+	uint32_t prev_uid;
 
 	if (_iter->failed || iter->search_ctx == NULL)
 		return -1;
 
+	prev_uid = iter->mail->uid;
 	switch (mailbox_search_next(iter->search_ctx, iter->mail)) {
 	case 0:
+		if (iter_local_mailbox_next_expunge(iter, prev_uid, msg_r)) {
+			*mailbox_idx_r = iter->mailbox_idx;
+			return 1;
+		}
 		iter_local_mailbox_close(iter);
 		iter->mailbox_idx++;
 		if (iter_local_mailbox_open(iter) < 0)
@@ -417,6 +479,8 @@
 
 	if (iter->mail != NULL)
 		iter_local_mailbox_close(iter);
+	array_free(&iter->expunges);
+	str_free(&iter->tmp_guid_str);
 	i_free(iter->mailboxes);
 	i_free(iter);
 	return ret;

--- a/src/dsync/dsync-worker.h	Wed Jul 15 18:29:58 2009 -0400
+++ b/src/dsync/dsync-worker.h	Wed Jul 15 18:31:59 2009 -0400
@@ -52,9 +52,11 @@
 dsync_worker_msg_iter_init(struct dsync_worker *worker,
 			   const mailbox_guid_t mailboxes[],
 			   unsigned int mailbox_count);
-/* Get the next available message. mailbox_idx_r contains the mailbox's index
-   in mailbox_guids[] array given to _iter_init(). Returns 1 if ok, 0 if
-   waiting for more data, -1 if there are no more messages. */
+/* Get the next available message. Also returns all expunged messages from
+   the end of mailbox (if next_uid-1 message exists, nothing is returned).
+   mailbox_idx_r contains the mailbox's index in mailbox_guids[] array given
+   to _iter_init(). Returns 1 if ok, 0 if waiting for more data, -1 if there
+   are no more messages. */
 int dsync_worker_msg_iter_next(struct dsync_worker_msg_iter *iter,
 			       unsigned int *mailbox_idx_r,
 			       struct dsync_message *msg_r);

--- a/src/dsync/test-dsync-brain.c	Wed Jul 15 18:29:58 2009 -0400
+++ b/src/dsync/test-dsync-brain.c	Wed Jul 15 18:31:59 2009 -0400
@@ -2,6 +2,7 @@
 
 #include "lib.h"
 #include "array.h"
+#include "sha1.h"
 #include "master-service.h"
 #include "dsync-brain-private.h"
 #include "test-common.h"
@@ -44,12 +45,14 @@
 static struct dsync_message box3_src_msgs[] = {
 	{ "guid1", 1, MAIL_FLAGGED, NULL, 5454, 273850 },
 	{ "guid5", 5, 0, NULL, 331, 38701233 },
+	{ "b75c81f2b3a4c9f84f24851c37acedee", 6, DSYNC_MAIL_FLAG_EXPUNGED, NULL, 331, 38701233 },
 	{ NULL, 0, 0, NULL, 0, 0 }
 };
 static struct dsync_message box3_dest_msgs[] = {
 	{ "guid1", 1, MAIL_FLAGGED, NULL, 5454, 273850 },
 	{ "guid8", 3, 0, NULL, 330, 2424 },
 	{ "guid5", 5, 0, NULL, 1, 38701233 },
+	{ "guid6", 6, 0, NULL, 333, 6482 },
 	{ "guid7", 7, 0, NULL, 333, 6482 },
 	{ NULL, 0, 0, NULL, 0, 0 }
 };
@@ -79,6 +82,15 @@
 {
 }
 
+void mail_generate_guid_128_hash(const char *guid,
+				 uint8_t guid_128[MAIL_GUID_128_SIZE])
+{
+	unsigned char sha1_sum[SHA1_RESULTLEN];
+
+	sha1_get_digest(guid, strlen(guid), sha1_sum);
+	memcpy(guid_128, sha1_sum, MAIL_GUID_128_SIZE);
+}
+
 static bool mailbox_find(const char *name, unsigned int *idx_r)
 {
 	unsigned int i;
@@ -198,6 +210,11 @@
 					   MAILBOX_GUID_SIZE) == 0);
 			test_assert(event->msg.uid == box->dest_msgs[j].uid);
 			j++; event++;
+		} else if (box->src_msgs[i].flags == DSYNC_MAIL_FLAG_EXPUNGED) {
+			/* message expunged from end of mailbox */
+			test_assert(event->type == LAST_MSG_TYPE_EXPUNGE);
+			test_assert(event->msg.uid == box->dest_msgs[j].uid);
+			i++; j++; event++;
 		} else if (box->src_msgs[i].modseq > box->dest_msgs[j].modseq ||
 			   box->src_msgs[i].flags != box->dest_msgs[j].flags ||
 			   !dsync_keyword_list_equals(box->src_msgs[i].keywords,
@@ -385,6 +402,8 @@
 	{ "guid3", 3, 0, NULL, 1, 1 },
 	{ "guid5", 5, 0, NULL, 1, 1 },
 	{ "guidy", 6, 0, NULL, 1, 1 },
+	{ "67ddfe2125de633c56e033b57c897018", 7, DSYNC_MAIL_FLAG_EXPUNGED, NULL, 1, 1 },
+	{ "guidz", 8, DSYNC_MAIL_FLAG_EXPUNGED, NULL, 1, 1 },
 	{ NULL, 0, 0, NULL, 0, 0 }
 };
 static struct dsync_message conflict_dest_msgs[] = {
@@ -393,6 +412,8 @@
 	{ "guidx", 3, 0, NULL, 1, 1 },
 	{ "guid4", 4, 0, NULL, 1, 1 },
 	{ "guid5", 5, 0, NULL, 1, 1 },
+	{ "guid7", 7, 0, NULL, 1, 1 },
+	{ "guid8", 8, 0, NULL, 1, 1 },
 	{ NULL, 0, 0, NULL, 0, 0 }
 };
 
@@ -415,6 +436,10 @@
 	test_assert(event.msg.uid == 2);
 
 	test_assert(test_dsync_worker_next_msg_event(dest_test_worker, &event));
+	test_assert(event.type == LAST_MSG_TYPE_EXPUNGE);
+	test_assert(event.msg.uid == 7);
+
+	test_assert(test_dsync_worker_next_msg_event(dest_test_worker, &event));
 	test_assert(event.type == LAST_MSG_TYPE_SAVE);
 	test_assert(event.msg.uid == 4321);
 	test_assert(strcmp(event.msg.guid, "guid3") == 0);
@@ -428,6 +453,12 @@
 	test_assert(event.type == LAST_MSG_TYPE_UPDATE_UID);
 	test_assert(event.msg.uid == 3);
 
+	test_assert(test_dsync_worker_next_msg_event(dest_test_worker, &event));
+	test_assert(event.type == LAST_MSG_TYPE_UPDATE_UID);
+	test_assert(event.msg.uid == 8);
+
+	test_assert(!test_dsync_worker_next_msg_event(dest_test_worker, &event));
+
 	while (test_dsync_worker_next_box_event(dest_test_worker, &box_event) &&
 	       box_event.type == LAST_BOX_TYPE_SELECT) ;
 
@@ -435,6 +466,9 @@
 	test_assert(box_event.box.uid_next == 4322);
 	test_assert(box_event.box.uid_validity == 1234567890);
 	test_assert(box_event.box.highest_modseq == 888);
+
+	while (test_dsync_worker_next_box_event(dest_test_worker, &box_event))
+		test_assert(box_event.type == LAST_BOX_TYPE_SELECT);
 }
 
 static void test_dsync_brain_uid_conflict(void)

--- a/src/dsync/test-dsync-proxy.c	Wed Jul 15 18:29:58 2009 -0400
+++ b/src/dsync/test-dsync-proxy.c	Wed Jul 15 18:31:59 2009 -0400
@@ -34,6 +34,22 @@
 					   &msg_out, &error) == 0);
 	test_assert(dsync_messages_equal(&msg_in, &msg_out));
 
+	/* expunged flag */
+	msg_in.flags = DSYNC_MAIL_FLAG_EXPUNGED;
+	str_truncate(str, 0);
+	dsync_proxy_msg_export(str, &msg_in);
+	test_assert(dsync_proxy_msg_import(pool, str_c(str),
+					   &msg_out, &error) == 0);
+	test_assert(dsync_messages_equal(&msg_in, &msg_out));
+
+	/* expunged flag and another flag */
+	msg_in.flags = DSYNC_MAIL_FLAG_EXPUNGED | MAIL_DRAFT;
+	str_truncate(str, 0);
+	dsync_proxy_msg_export(str, &msg_in);
+	test_assert(dsync_proxy_msg_import(pool, str_c(str),
+					   &msg_out, &error) == 0);
+	test_assert(dsync_messages_equal(&msg_in, &msg_out));
+
 	/* all flags, some keywords */
 	msg_in.flags = MAIL_FLAGS_MASK;
 	msg_in.keywords = test_keywords;