Mercurial > dovecot > core-2.2

changeset 9624:2558ba736207 HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Keep track of expunged messages' GUIDs and expose them via mailbox_get_expunges(). The message GUIDs are stored in expunge records to transaction log. Before doing the final expunge, Maildir and dbox verify that the GUID in expunge request matches the current actual GUID. The GUID is stored in 128 bit field. If the real GUID isn't 128 bit, the bits are taken from SHA1 of the GUID.
author Timo Sirainen <tss@iki.fi>
date Mon, 13 Jul 2009 22:24:27 -0400
parents 3da42dafa798
children e8b9f78d2b3c
files src/imap/imap-fetch.c src/lib-index/mail-index-sync-update.c src/lib-index/mail-index-sync.c src/lib-index/mail-index-transaction-export.c src/lib-index/mail-index-transaction-finish.c src/lib-index/mail-index-transaction-private.h src/lib-index/mail-index-transaction-update.c src/lib-index/mail-index-transaction-view.c src/lib-index/mail-index-transaction.c src/lib-index/mail-index-view-sync.c src/lib-index/mail-index.h src/lib-index/mail-transaction-log-append.c src/lib-index/mail-transaction-log-file.c src/lib-index/mail-transaction-log-view.c src/lib-index/mail-transaction-log.h src/lib-mail/mail-types.h src/lib-storage/index/dbox/dbox-file-fix.c src/lib-storage/index/dbox/dbox-file.c src/lib-storage/index/dbox/dbox-file.h src/lib-storage/index/dbox/dbox-map.c src/lib-storage/index/dbox/dbox-save.c src/lib-storage/index/dbox/dbox-storage-rebuild.c src/lib-storage/index/dbox/dbox-storage.c src/lib-storage/index/dbox/dbox-storage.h src/lib-storage/index/dbox/dbox-sync-file.c src/lib-storage/index/dbox/dbox-sync.c src/lib-storage/index/dbox/dbox-sync.h src/lib-storage/index/index-fetch.c src/lib-storage/index/index-mail.c src/lib-storage/index/index-storage.h src/lib-storage/index/index-sync-changes.c src/lib-storage/index/index-sync-changes.h src/lib-storage/index/maildir/maildir-sync-index.c src/lib-storage/index/mbox/mbox-sync.c src/lib-storage/mail-storage-private.h src/lib-storage/mail-storage.c src/lib-storage/mail-storage.h src/lib-storage/mail.c src/lib-storage/test-mailbox.c src/util/logview.c
diffstat 40 files changed, 586 insertions(+), 209 deletions(-) [+]
line wrap: on
line diff
--- a/src/imap/imap-fetch.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/imap/imap-fetch.c	Mon Jul 13 22:24:27 2009 -0400
@@ -255,6 +255,18 @@
 	return ret;
 }
 
+static void
+mailbox_expunge_to_range(const ARRAY_TYPE(mailbox_expunge_rec) *input,
+			 ARRAY_TYPE(seq_range) *output)
+{
+	const struct mailbox_expunge_rec *expunges;
+	unsigned int i, count;
+
+	expunges = array_get(input, &count);
+	for (i = 0; i < count; i++)
+		seq_range_array_add(output, 0, expunges[i].uid);
+}
+
 static int
 imap_fetch_send_vanished(struct imap_fetch_context *ctx)
 {
@@ -262,27 +274,32 @@
 	const struct mail_search_arg *modseqarg = uidarg->next;
 	const ARRAY_TYPE(seq_range) *uids = &uidarg->value.seqset;
 	uint64_t modseq = modseqarg->value.modseq->modseq;
-	ARRAY_TYPE(seq_range) expunges;
+	ARRAY_TYPE(mailbox_expunge_rec) expunges;
+	ARRAY_TYPE(seq_range) expunges_range;
 	string_t *str;
 	int ret = 0;
 
 	i_array_init(&expunges, array_count(uids));
-	if (!mailbox_get_expunged_uids(ctx->box, modseq, uids, &expunges)) {
+	i_array_init(&expunges_range, array_count(uids));
+	if (mailbox_get_expunges(ctx->box, modseq, uids, &expunges))
+		mailbox_expunge_to_range(&expunges, &expunges_range);
+	else {
 		/* return all expunged UIDs */
-		if (get_expunges_fallback(ctx, uids, &expunges) < 0) {
-			array_clear(&expunges);
+		if (get_expunges_fallback(ctx, uids, &expunges_range) < 0) {
+			array_clear(&expunges_range);
 			ret = -1;
 		}
 	}
-	if (array_count(&expunges) > 0) {
+	if (array_count(&expunges_range) > 0) {
 		str = str_new(default_pool, 128);
 		str_append(str, "* VANISHED (EARLIER) ");
-		imap_write_seq_range(str, &expunges);
+		imap_write_seq_range(str, &expunges_range);
 		str_append(str, "\r\n");
 		o_stream_send(ctx->client->output, str_data(str), str_len(str));
 		str_free(&str);
 	}
 	array_free(&expunges);
+	array_free(&expunges_range);
 	return ret;
 }
 
--- a/src/lib-index/mail-index-sync-update.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-sync-update.c	Mon Jul 13 22:24:27 2009 -0400
@@ -236,44 +236,36 @@
 	}
 }
 
-static int
-sync_expunge(const struct mail_transaction_expunge *e, unsigned int count,
-	     struct mail_index_sync_map_ctx *ctx)
+static void
+sync_expunge(struct mail_index_sync_map_ctx *ctx, uint32_t uid1, uint32_t uid2)
 {
 	struct mail_index_map *map = ctx->view->map;
 	struct mail_index_record *rec;
 	uint32_t seq_count, seq, seq1, seq2;
-	unsigned int i;
 
-	for (i = 0; i < count; i++, e++) {
-		if (!mail_index_lookup_seq_range(ctx->view, e->uid1, e->uid2,
-						 &seq1, &seq2)) {
-			/* everything expunged already */
-			continue;
-		}
+	if (!mail_index_lookup_seq_range(ctx->view, uid1, uid2, &seq1, &seq2)) {
+		/* everything expunged already */
+		return;
+	}
 
-		sync_expunge_call_handlers(ctx, seq1, seq2);
+	sync_expunge_call_handlers(ctx, seq1, seq2);
 
-		map = mail_index_sync_get_atomic_map(ctx);
-		for (seq = seq1; seq <= seq2; seq++) {
-			rec = MAIL_INDEX_MAP_IDX(map, seq-1);
-			mail_index_sync_header_update_counts(ctx, rec->uid,
-							     rec->flags, 0,
-							     FALSE);
-		}
+	map = mail_index_sync_get_atomic_map(ctx);
+	for (seq = seq1; seq <= seq2; seq++) {
+		rec = MAIL_INDEX_MAP_IDX(map, seq-1);
+		mail_index_sync_header_update_counts(ctx, rec->uid, rec->flags,
+						     0, FALSE);
+	}
 
-		/* @UNSAFE */
-		memmove(MAIL_INDEX_MAP_IDX(map, seq1-1),
-			MAIL_INDEX_MAP_IDX(map, seq2),
-			(map->rec_map->records_count - seq2) *
-			map->hdr.record_size);
+	/* @UNSAFE */
+	memmove(MAIL_INDEX_MAP_IDX(map, seq1-1),
+		MAIL_INDEX_MAP_IDX(map, seq2),
+		(map->rec_map->records_count - seq2) * map->hdr.record_size);
 
-		seq_count = seq2 - seq1 + 1;
-		map->rec_map->records_count -= seq_count;
-		map->hdr.messages_count -= seq_count;
-		mail_index_modseq_expunge(ctx->modseq_ctx, seq1, seq2);
-	}
-	return 1;
+	seq_count = seq2 - seq1 + 1;
+	map->rec_map->records_count -= seq_count;
+	map->hdr.messages_count -= seq_count;
+	mail_index_modseq_expunge(ctx->modseq_ctx, seq1, seq2);
 }
 
 void mail_index_sync_write_seq_update(struct mail_index_sync_map_ctx *ctx,
@@ -484,7 +476,21 @@
 			break;
 		}
 		end = CONST_PTR_OFFSET(data, hdr->size);
-		ret = sync_expunge(rec, end - rec, ctx);
+		for (; rec != end; rec++)
+			sync_expunge(ctx, rec->uid1, rec->uid2);
+		break;
+	}
+	case MAIL_TRANSACTION_EXPUNGE_GUID:
+	case MAIL_TRANSACTION_EXPUNGE_GUID|MAIL_TRANSACTION_EXPUNGE_PROT: {
+		const struct mail_transaction_expunge_guid *rec = data, *end;
+
+		if ((hdr->type & MAIL_TRANSACTION_EXTERNAL) == 0) {
+			/* this is simply a request for expunge */
+			break;
+		}
+		end = CONST_PTR_OFFSET(data, hdr->size);
+		for (; rec != end; rec++)
+			sync_expunge(ctx, rec->uid, rec->uid);
 		break;
 	}
 	case MAIL_TRANSACTION_FLAG_UPDATE: {
--- a/src/lib-index/mail-index-sync.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-sync.c	Mon Jul 13 22:24:27 2009 -0400
@@ -41,6 +41,17 @@
 	}
 }
 
+static void mail_index_sync_add_expunge_guid(struct mail_index_sync_ctx *ctx)
+{
+	const struct mail_transaction_expunge_guid *e = ctx->data;
+	size_t i, size = ctx->hdr->size / sizeof(*e);
+
+	for (i = 0; i < size; i++) {
+		mail_index_expunge_guid(ctx->sync_trans, e[i].uid,
+					e[i].guid_128);
+	}
+}
+
 static void mail_index_sync_add_flag_update(struct mail_index_sync_ctx *ctx)
 {
 	const struct mail_transaction_flag_update *u = ctx->data;
@@ -129,6 +140,9 @@
 	case MAIL_TRANSACTION_EXPUNGE:
 		mail_index_sync_add_expunge(ctx);
 		break;
+	case MAIL_TRANSACTION_EXPUNGE_GUID:
+		mail_index_sync_add_expunge_guid(ctx);
+		break;
 	case MAIL_TRANSACTION_FLAG_UPDATE:
                 mail_index_sync_add_flag_update(ctx);
 		break;
@@ -512,6 +526,7 @@
 			   to be synced, but cache syncing relies on tail
 			   offsets being updated. */
 		case MAIL_TRANSACTION_EXPUNGE:
+		case MAIL_TRANSACTION_EXPUNGE_GUID:
 		case MAIL_TRANSACTION_FLAG_UPDATE:
 		case MAIL_TRANSACTION_KEYWORD_UPDATE:
 		case MAIL_TRANSACTION_KEYWORD_RESET:
@@ -550,11 +565,12 @@
 
 static void
 mail_index_sync_get_expunge(struct mail_index_sync_rec *rec,
-			    const struct mail_transaction_expunge *exp)
+			    const struct mail_transaction_expunge_guid *exp)
 {
 	rec->type = MAIL_INDEX_SYNC_TYPE_EXPUNGE;
-	rec->uid1 = exp->uid1;
-	rec->uid2 = exp->uid2;
+	rec->uid1 = exp->uid;
+	rec->uid2 = exp->uid;
+	memcpy(rec->guid_128, exp->guid_128, sizeof(rec->guid_128));
 }
 
 static void
@@ -605,6 +621,8 @@
 	/* FIXME: replace with a priority queue so we don't have to go
 	   through the whole list constantly. and remember to make sure that
 	   keyword resets are sent before adds! */
+	/* FIXME: pretty ugly to do this for expunges, which isn't even a
+	   seq_range. */
 	sync_list = array_get_modifiable(&ctx->sync_list, &count);
 	for (i = 0; i < count; i++) {
 		if (!array_is_created(sync_list[i].array) ||
@@ -641,7 +659,7 @@
 
 	if (sync_list[i].array == (void *)&sync_trans->expunges) {
 		mail_index_sync_get_expunge(sync_rec,
-			(const struct mail_transaction_expunge *)uid_range);
+			(const struct mail_transaction_expunge_guid *)uid_range);
 	} else if (sync_list[i].array == (void *)&sync_trans->updates) {
 		mail_index_sync_get_update(sync_rec,
 			(const struct mail_transaction_flag_update *)uid_range);
--- a/src/lib-index/mail-index-transaction-export.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-transaction-export.c	Mon Jul 13 22:24:27 2009 -0400
@@ -380,7 +380,7 @@
 		if ((t->flags & MAIL_INDEX_TRANSACTION_FLAG_EXTERNAL) != 0)
 			change_mask |= MAIL_INDEX_SYNC_TYPE_EXPUNGE;
 		log_append_buffer(&ctx, t->expunges.arr.buffer,
-				  MAIL_TRANSACTION_EXPUNGE);
+				  MAIL_TRANSACTION_EXPUNGE_GUID);
 	}
 
 	if (t->post_hdr_changed) {
--- a/src/lib-index/mail-index-transaction-finish.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-transaction-finish.c	Mon Jul 13 22:24:27 2009 -0400
@@ -6,6 +6,26 @@
 #include "mail-index-modseq.h"
 #include "mail-index-transaction-private.h"
 
+int mail_transaction_expunge_guid_cmp(const struct mail_transaction_expunge_guid *e1,
+				      const struct mail_transaction_expunge_guid *e2)
+{
+	if (e1->uid < e2->uid)
+		return -1;
+	else if (e1->uid > e2->uid)
+		return 1;
+	else
+		return 0;
+}
+
+void mail_index_transaction_sort_expunges(struct mail_index_transaction *t)
+{
+	if (!t->expunges_nonsorted)
+		return;
+
+	array_sort(&t->expunges, mail_transaction_expunge_guid_cmp);
+	t->expunges_nonsorted = FALSE;
+}
+
 static void
 ext_reset_update_atomic(struct mail_index_transaction *t,
 			uint32_t ext_id, uint32_t expected_reset_id)
@@ -312,6 +332,31 @@
 	}
 }
 
+static void expunges_convert_to_uids(struct mail_index_transaction *t)
+{
+	struct mail_transaction_expunge_guid *expunges;
+	unsigned int src, dest, count;
+
+	if (!array_is_created(&t->expunges))
+		return;
+
+	mail_index_transaction_sort_expunges(t);
+
+	expunges = array_get_modifiable(&t->expunges, &count);
+	if (count == 0)
+		return;
+
+	/* convert uids and drop duplicates */
+	expunges[0].uid = mail_index_transaction_get_uid(t, expunges[0].uid);
+	for (src = dest = 1; src < count; src++) {
+		expunges[dest].uid =
+			mail_index_transaction_get_uid(t, expunges[src].uid);
+		if (expunges[dest-1].uid != expunges[dest].uid)
+			dest++;
+	}
+	array_delete(&t->expunges, dest, count-dest);
+}
+
 static void
 mail_index_transaction_convert_to_uids(struct mail_index_transaction *t)
 {
@@ -330,8 +375,7 @@
 	}
 
         keyword_updates_convert_to_uids(t);
-
-	mail_index_convert_to_uid_ranges(t, &t->expunges);
+	expunges_convert_to_uids(t);
 	mail_index_convert_to_uid_ranges(t, (void *)&t->updates);
 	mail_index_convert_to_uid_ranges(t, &t->keyword_resets);
 }
--- a/src/lib-index/mail-index-transaction-private.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-transaction-private.h	Mon Jul 13 22:24:27 2009 -0400
@@ -37,14 +37,14 @@
 	struct mail_index_view *view;
 
 	/* NOTE: If you add anything new, remember to update
-	   mail_index_transaction_reset() to reset it. */
+	   mail_index_transaction_reset_v() to reset it. */
         ARRAY_DEFINE(appends, struct mail_index_record);
 	uint32_t first_new_seq, last_new_seq;
 	uint32_t highest_append_uid;
 	/* lowest/highest sequence that updates flags/keywords */
 	uint32_t min_flagupdate_seq, max_flagupdate_seq;
 
-	ARRAY_TYPE(seq_range) expunges;
+	ARRAY_DEFINE(expunges, struct mail_transaction_expunge_guid);
 	ARRAY_DEFINE(updates, struct mail_transaction_flag_update);
 	size_t last_update_idx;
 
@@ -77,6 +77,7 @@
 
 	unsigned int sync_transaction:1;
 	unsigned int appends_nonsorted:1;
+	unsigned int expunges_nonsorted:1;
 	unsigned int drop_unnecessary_flag_updates:1;
 	unsigned int pre_hdr_changed:1;
 	unsigned int post_hdr_changed:1;
@@ -104,6 +105,7 @@
 void mail_index_transaction_reset_v(struct mail_index_transaction *t);
 
 void mail_index_transaction_sort_appends(struct mail_index_transaction *t);
+void mail_index_transaction_sort_expunges(struct mail_index_transaction *t);
 uint32_t mail_index_transaction_get_next_uid(struct mail_index_transaction *t);
 void mail_index_transaction_set_log_updates(struct mail_index_transaction *t);
 void mail_index_update_day_headers(struct mail_index_transaction *t);
@@ -117,6 +119,8 @@
 int mail_index_transaction_finish(struct mail_index_transaction *t);
 void mail_index_transaction_export(struct mail_index_transaction *t,
 				   struct mail_transaction_log_append_ctx *append_ctx);
+int mail_transaction_expunge_guid_cmp(const struct mail_transaction_expunge_guid *e1,
+				      const struct mail_transaction_expunge_guid *e2);
 unsigned int
 mail_index_transaction_get_flag_update_pos(struct mail_index_transaction *t,
 					   unsigned int left_idx,
--- a/src/lib-index/mail-index-transaction-update.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-transaction-update.c	Mon Jul 13 22:24:27 2009 -0400
@@ -92,6 +92,7 @@
 	memset(t->post_hdr_mask, 0, sizeof(t->post_hdr_mask));
 
 	t->appends_nonsorted = FALSE;
+	t->expunges_nonsorted = FALSE;
 	t->drop_unnecessary_flag_updates = FALSE;
 	t->pre_hdr_changed = FALSE;
 	t->post_hdr_changed = FALSE;
@@ -273,6 +274,18 @@
 
 void mail_index_expunge(struct mail_index_transaction *t, uint32_t seq)
 {
+	static uint8_t null_guid[MAIL_GUID_128_SIZE] =
+		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+	mail_index_expunge_guid(t, seq, null_guid);
+}
+
+void mail_index_expunge_guid(struct mail_index_transaction *t, uint32_t seq,
+			     const uint8_t guid_128[MAIL_GUID_128_SIZE])
+{
+	const struct mail_transaction_expunge_guid *expunges;
+	struct mail_transaction_expunge_guid *expunge;
+	unsigned int count;
+
 	i_assert(seq > 0);
 	if (seq >= t->first_new_seq) {
 		/* we can handle only the last append. otherwise we'd have to
@@ -283,8 +296,18 @@
 	} else {
 		t->log_updates = TRUE;
 
-		/* expunges is a sorted array of {seq1, seq2, ..}, .. */
-		seq_range_array_add(&t->expunges, 128, seq);
+		/* ignore duplicates here. drop them when commiting. */
+		if (!array_is_created(&t->expunges))
+			i_array_init(&t->expunges, 64);
+		else if (!t->expunges_nonsorted) {
+			/* usually expunges are added in increasing order. */
+			expunges = array_get(&t->expunges, &count);
+			if (count > 0 && seq < expunges[count-1].uid)
+				t->expunges_nonsorted = TRUE;
+		}
+		expunge = array_append_space(&t->expunges);
+		expunge->uid = seq;
+		memcpy(expunge->guid_128, guid_128, sizeof(expunge->guid_128));
 	}
 }
 
--- a/src/lib-index/mail-index-transaction-view.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-transaction-view.c	Mon Jul 13 22:24:27 2009 -0400
@@ -124,8 +124,7 @@
 	rec = tview->super->lookup_full(view, seq, map_r, expunged_r);
 	rec = tview_apply_flag_updates(tview, rec, seq);
 
-	if (array_is_created(&tview->t->expunges) &&
-	    seq_range_exists(&tview->t->expunges, seq))
+	if (mail_index_transaction_is_expunged(tview->t, seq))
 		*expunged_r = TRUE;
 	return rec;
 }
--- a/src/lib-index/mail-index-transaction.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-transaction.c	Mon Jul 13 22:24:27 2009 -0400
@@ -22,8 +22,17 @@
 bool mail_index_transaction_is_expunged(struct mail_index_transaction *t,
 					uint32_t seq)
 {
-	return array_is_created(&t->expunges) &&
-		seq_range_exists(&t->expunges, seq);
+	struct mail_transaction_expunge_guid key;
+
+	if (!array_is_created(&t->expunges))
+		return FALSE;
+
+	if (t->expunges_nonsorted)
+		mail_index_transaction_sort_expunges(t);
+
+	key.uid = seq;
+	return array_bsearch(&t->expunges, &key,
+			     mail_transaction_expunge_guid_cmp) != NULL;
 }
 
 void mail_index_transaction_ref(struct mail_index_transaction *t)
--- a/src/lib-index/mail-index-view-sync.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index-view-sync.c	Mon Jul 13 22:24:27 2009 -0400
@@ -123,6 +123,20 @@
 		seq_range_array_add_range(dest, src[i].seq1, src[i].seq2);
 }
 
+static void
+view_sync_add_expunge_guids(ARRAY_TYPE(seq_range) *dest,
+			    const struct mail_transaction_expunge_guid *src,
+			    size_t src_size)
+{
+	unsigned int i, src_count;
+
+	i_assert(src_size % sizeof(*src) == 0);
+
+	src_count = src_size / sizeof(*src);
+	for (i = 0; i < src_count; i++)
+		seq_range_array_add(dest, 0, src[i].uid);
+}
+
 static int
 view_sync_get_expunges(struct mail_index_view_sync_ctx *ctx,
 		       unsigned int *expunge_count_r)
@@ -139,14 +153,17 @@
 	mail_transaction_log_view_mark(view->log_view);
 	while ((ret = mail_transaction_log_view_next(view->log_view,
 						     &hdr, &data)) > 0) {
-		if ((hdr->type & MAIL_TRANSACTION_EXPUNGE) == 0)
-			continue;
 		if ((hdr->type & MAIL_TRANSACTION_EXTERNAL) == 0) {
-			/* this is simply a request for expunge */
+			/* skip expunge requests */
 			continue;
 		}
-
-		view_sync_add_expunge_range(&ctx->expunges, data, hdr->size);
+		if ((hdr->type & MAIL_TRANSACTION_EXPUNGE_GUID) != 0) {
+			view_sync_add_expunge_guids(&ctx->expunges,
+						    data, hdr->size);
+		} else if ((hdr->type & MAIL_TRANSACTION_EXPUNGE) != 0) {
+			view_sync_add_expunge_range(&ctx->expunges,
+						    data, hdr->size);
+		}
 	}
 	mail_transaction_log_view_rewind(view->log_view);
 
@@ -161,7 +178,7 @@
 	uint32_t seq1, seq2;
 
 	range_end = CONST_PTR_OFFSET(range, size);
-	for (; range < range_end; range++) {
+	for (; range != range_end; range++) {
 		if (mail_index_lookup_seq_range(view, range->seq1, range->seq2,
 						&seq1, &seq2))
 			return TRUE;
@@ -169,6 +186,22 @@
 	return FALSE;
 }
 
+static bool
+have_existing_guid_expunge(struct mail_index_view *view,
+			   const struct mail_transaction_expunge_guid *expunges,
+			   size_t size)
+{
+	const struct mail_transaction_expunge_guid *expunges_end;
+	uint32_t seq;
+
+	expunges_end = CONST_PTR_OFFSET(expunges, size);
+	for (; expunges != expunges_end; expunges++) {
+		if (mail_index_lookup_seq(view, expunges->uid, &seq))
+			return TRUE;
+	}
+	return FALSE;
+}
+
 static bool view_sync_have_expunges(struct mail_index_view *view)
 {
 	const struct mail_transaction_header *hdr;
@@ -180,17 +213,22 @@
 
 	while ((ret = mail_transaction_log_view_next(view->log_view,
 						     &hdr, &data)) > 0) {
-		if ((hdr->type & MAIL_TRANSACTION_EXPUNGE) == 0)
-			continue;
 		if ((hdr->type & MAIL_TRANSACTION_EXTERNAL) == 0) {
-			/* this is simply a request for expunge */
+			/* skip expunge requests */
 			continue;
 		}
-
-		/* we have an expunge. see if it still exists. */
-		if (have_existing_expunges(view, data, hdr->size)) {
-			have_expunges = TRUE;
-			break;
+		if ((hdr->type & MAIL_TRANSACTION_EXPUNGE_GUID) != 0) {
+			/* we have an expunge. see if it still exists. */
+			if (have_existing_expunges(view, data, hdr->size)) {
+				have_expunges = TRUE;
+				break;
+			}
+		} else if ((hdr->type & MAIL_TRANSACTION_EXPUNGE) != 0) {
+			/* we have an expunge. see if it still exists. */
+			if (have_existing_guid_expunge(view, data, hdr->size)) {
+				have_expunges = TRUE;
+				break;
+			}
 		}
 	}
 
@@ -616,7 +654,8 @@
 	mail_transaction_log_view_get_prev_pos(view->log_view, &seq, &offset);
 	next_offset = offset + sizeof(*hdr) + hdr->size;
 
-	if ((hdr->type & MAIL_TRANSACTION_EXPUNGE) != 0 &&
+	if ((hdr->type & (MAIL_TRANSACTION_EXPUNGE |
+			  MAIL_TRANSACTION_EXPUNGE_GUID)) != 0 &&
 	    (hdr->type & MAIL_TRANSACTION_EXTERNAL) != 0) {
 		if ((ctx->flags & MAIL_INDEX_VIEW_SYNC_FLAG_NOEXPUNGES) != 0) {
 			i_assert(!LOG_IS_BEFORE(seq, offset,
@@ -688,10 +727,13 @@
 	/* Apply transaction to view's mapping if needed (meaning we
 	   didn't just re-map the view to head mapping). */
 	if (ctx->sync_map_update && !synced_to_map) {
-		if ((hdr->type & MAIL_TRANSACTION_EXPUNGE) == 0) T_BEGIN {
-			ret = mail_index_sync_record(&ctx->sync_map_ctx,
-						     hdr, ctx->data);
-		} T_END;
+		if ((hdr->type & (MAIL_TRANSACTION_EXPUNGE |
+				  MAIL_TRANSACTION_EXPUNGE_GUID)) == 0) {
+			T_BEGIN {
+				ret = mail_index_sync_record(&ctx->sync_map_ctx,
+							     hdr, ctx->data);
+			} T_END;
+		}
 		if (ret < 0)
 			return -1;
 	}
--- a/src/lib-index/mail-index.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-index.h	Mon Jul 13 22:24:27 2009 -0400
@@ -165,6 +165,9 @@
 
 	/* MAIL_INDEX_SYNC_TYPE_KEYWORD_ADD, .._REMOVE: */
 	unsigned int keyword_idx;
+
+	/* MAIL_INDEX_SYNC_TYPE_EXPUNGE: */
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
 };
 
 enum mail_index_view_sync_type {
@@ -400,6 +403,9 @@
 /* Expunge record from index. Note that this doesn't affect sequence numbers
    until transaction is committed and mailbox is synced. */
 void mail_index_expunge(struct mail_index_transaction *t, uint32_t seq);
+/* Like mail_index_expunge(), but also write message GUID to transaction log. */
+void mail_index_expunge_guid(struct mail_index_transaction *t, uint32_t seq,
+			     const uint8_t guid_128[MAIL_GUID_128_SIZE]);
 /* Update flags in index. */
 void mail_index_update_flags(struct mail_index_transaction *t, uint32_t seq,
 			     enum modify_type modify_type,
--- a/src/lib-index/mail-transaction-log-append.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-transaction-log-append.c	Mon Jul 13 22:24:27 2009 -0400
@@ -20,7 +20,8 @@
 
 	memset(&hdr, 0, sizeof(hdr));
 	hdr.type = type;
-	if (type == MAIL_TRANSACTION_EXPUNGE)
+	if (type == MAIL_TRANSACTION_EXPUNGE ||
+	    type == MAIL_TRANSACTION_EXPUNGE_GUID)
 		hdr.type |= MAIL_TRANSACTION_EXPUNGE_PROT;
 	if (ctx->external)
 		hdr.type |= MAIL_TRANSACTION_EXTERNAL;
--- a/src/lib-index/mail-transaction-log-file.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-transaction-log-file.c	Mon Jul 13 22:24:27 2009 -0400
@@ -822,6 +822,7 @@
 
 	switch (hdr->type & MAIL_TRANSACTION_TYPE_MASK) {
 	case MAIL_TRANSACTION_EXPUNGE | MAIL_TRANSACTION_EXPUNGE_PROT:
+	case MAIL_TRANSACTION_EXPUNGE_GUID | MAIL_TRANSACTION_EXPUNGE_PROT:
 		if ((hdr->type & MAIL_TRANSACTION_EXTERNAL) == 0) {
 			/* ignore expunge requests */
 			break;
--- a/src/lib-index/mail-transaction-log-view.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-transaction-log-view.c	Mon Jul 13 22:24:27 2009 -0400
@@ -417,6 +417,15 @@
 		}
 		rec_type &= ~MAIL_TRANSACTION_EXPUNGE_PROT;
 	}
+	if ((hdr->type & MAIL_TRANSACTION_EXPUNGE_GUID) != 0) {
+		if (rec_type != (MAIL_TRANSACTION_EXPUNGE_GUID |
+				 MAIL_TRANSACTION_EXPUNGE_PROT)) {
+			mail_transaction_log_file_set_corrupted(file,
+				"expunge guid record missing protection mask");
+			return FALSE;
+		}
+		rec_type &= ~MAIL_TRANSACTION_EXPUNGE_PROT;
+	}
 
 	if (rec_size == 0) {
 		mail_transaction_log_file_set_corrupted(file,
@@ -441,6 +450,13 @@
 		array_create_from_buffer(&uids, &uid_buf,
 			sizeof(struct mail_transaction_expunge));
 		break;
+	case MAIL_TRANSACTION_EXPUNGE_GUID:
+		if ((rec_size % sizeof(struct mail_transaction_expunge_guid)) != 0) {
+			mail_transaction_log_file_set_corrupted(file,
+				"Invalid expunge guid record size");
+			ret = FALSE;
+		}
+		break;
 	case MAIL_TRANSACTION_FLAG_UPDATE:
 		buffer_create_const_data(&uid_buf, data, rec_size);
 		array_create_from_buffer(&uids, &uid_buf,
@@ -615,7 +631,9 @@
 
 	/* drop expunge protection */
 	if ((hdr->type & MAIL_TRANSACTION_TYPE_MASK) ==
-	    (MAIL_TRANSACTION_EXPUNGE | MAIL_TRANSACTION_EXPUNGE_PROT))
+	    (MAIL_TRANSACTION_EXPUNGE | MAIL_TRANSACTION_EXPUNGE_PROT) ||
+	    (hdr->type & MAIL_TRANSACTION_TYPE_MASK) ==
+	    (MAIL_TRANSACTION_EXPUNGE_GUID | MAIL_TRANSACTION_EXPUNGE_PROT))
 		view->tmp_hdr.type = hdr->type & ~MAIL_TRANSACTION_EXPUNGE_PROT;
 	else
 		view->tmp_hdr.type = hdr->type;
--- a/src/lib-index/mail-transaction-log.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-index/mail-transaction-log.h	Mon Jul 13 22:24:27 2009 -0400
@@ -1,8 +1,7 @@
 #ifndef MAIL_TRANSACTION_LOG_H
 #define MAIL_TRANSACTION_LOG_H
 
-struct mail_index;
-struct mail_index_transaction;
+#include "mail-index.h"
 
 #define MAIL_TRANSACTION_LOG_SUFFIX ".log"
 
@@ -39,6 +38,7 @@
 	MAIL_TRANSACTION_KEYWORD_UPDATE		= 0x00000400,
 	MAIL_TRANSACTION_KEYWORD_RESET		= 0x00000800,
 	MAIL_TRANSACTION_EXT_ATOMIC_INC		= 0x00001000,
+	MAIL_TRANSACTION_EXPUNGE_GUID		= 0x00002000,
 
 	MAIL_TRANSACTION_TYPE_MASK		= 0x0000ffff,
 
@@ -49,7 +49,7 @@
 
 	/* since we'll expunge mails based on data read from transaction log,
 	   try to avoid the possibility of corrupted transaction log expunging
-	   messages. this value is ORed to the actual MAIL_TRANSACTION_EXPUNGE
+	   messages. this value is ORed to the actual MAIL_TRANSACTION_EXPUNGE*
 	   flag. if it's not present, assume corrupted log. */
 	MAIL_TRANSACTION_EXPUNGE_PROT		= 0x0000cd90,
 
@@ -65,6 +65,10 @@
 struct mail_transaction_expunge {
 	uint32_t uid1, uid2;
 };
+struct mail_transaction_expunge_guid {
+	uint32_t uid;
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
+};
 
 struct mail_transaction_flag_update {
 	uint32_t uid1, uid2;
--- a/src/lib-mail/mail-types.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-mail/mail-types.h	Mon Jul 13 22:24:27 2009 -0400
@@ -1,6 +1,8 @@
 #ifndef MAIL_TYPES_H
 #define MAIL_TYPES_H
 
+#define MAIL_GUID_128_SIZE 16
+
 enum mail_flags {
 	MAIL_ANSWERED	= 0x01,
 	MAIL_FLAGGED	= 0x02,
--- a/src/lib-storage/index/dbox/dbox-file-fix.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-file-fix.c	Mon Jul 13 22:24:27 2009 -0400
@@ -165,7 +165,7 @@
 	bool pre, write_header, have_guid;
 	struct message_size body;
 	struct istream *body_input;
-	uint8_t guid_128[16];
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
 	int ret;
 
 	i_stream_seek(file->input, 0);
--- a/src/lib-storage/index/dbox/dbox-file.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-file.c	Mon Jul 13 22:24:27 2009 -0400
@@ -12,7 +12,6 @@
 #include "mkdir-parents.h"
 #include "fdatasync-path.h"
 #include "eacces-error.h"
-#include "sha1.h"
 #include "str.h"
 #include "dbox-storage.h"
 #include "dbox-file.h"
@@ -1029,23 +1028,3 @@
 		sizeof(dbox_msg_hdr->message_size_hex));
 	dbox_msg_hdr->save_lf = '\n';
 }
-
-void dbox_get_guid_128(const char *input, buffer_t *output)
-{
-	unsigned char sha1_sum[SHA1_RESULTLEN];
-
-	buffer_set_used_size(output, 0);
-	if (strlen(input) != DBOX_GUID_BIN_LEN*2 ||
-	    hex_to_binary(input, output) < 0 ||
-	    output->used != DBOX_GUID_BIN_LEN) {
-		/* not 128bit hex. use a hash of it instead. */
-		buffer_set_used_size(output, 0);
-		sha1_get_digest(input, strlen(input), sha1_sum);
-#if SHA1_RESULTLEN < DBOX_GUID_BIN_LEN
-#  error not possible
-#endif
-		buffer_append(output,
-			      sha1_sum + SHA1_RESULTLEN - DBOX_GUID_BIN_LEN,
-			      DBOX_GUID_BIN_LEN);
-	}
-}
--- a/src/lib-storage/index/dbox/dbox-file.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-file.h	Mon Jul 13 22:24:27 2009 -0400
@@ -206,6 +206,5 @@
 int dbox_file_header_write(struct dbox_file *file, struct ostream *output);
 int dbox_file_read_mail_header(struct dbox_file *file, uoff_t *physical_size_r);
 int dbox_file_metadata_skip_header(struct dbox_file *file);
-void dbox_get_guid_128(const char *input, buffer_t *output);
 
 #endif
--- a/src/lib-storage/index/dbox/dbox-map.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-map.c	Mon Jul 13 22:24:27 2009 -0400
@@ -504,7 +504,7 @@
 			      const ARRAY_TYPE(uint32_t) *map_uids, int diff)
 {
 	struct dbox_map *map = ctx->map;
-	const uint32_t *uids;
+	const uint32_t *uidp;
 	unsigned int i, count;
 	const void *data;
 	uint32_t seq;
@@ -514,13 +514,14 @@
 	if (ctx->trans == NULL)
 		return -1;
 
-	uids = array_get(map_uids, &count);
+	count = array_count(map_uids);
 	for (i = 0; i < count; i++) {
-		if (!mail_index_lookup_seq(map->view, uids[i], &seq)) {
+		uidp = array_idx(map_uids, i);
+		if (!mail_index_lookup_seq(map->view, *uidp, &seq)) {
 			/* we can't refresh map here since view has a
 			   transaction open. */
 			dbox_map_set_corrupted(map,
-				"refcount update lost map_uid=%u", uids[i]);
+				"refcount update lost map_uid=%u", *uidp);
 			return -1;
 		}
 		mail_index_lookup_ext(map->view, seq, map->ref_ext_id,
--- a/src/lib-storage/index/dbox/dbox-save.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-save.c	Mon Jul 13 22:24:27 2009 -0400
@@ -174,10 +174,9 @@
 static void dbox_save_write_metadata(struct dbox_save_context *ctx)
 {
 	struct dbox_metadata_header metadata_hdr;
-	uint8_t guid_128[16];
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
 	const char *guid;
 	string_t *str;
-	buffer_t *guid_buf;
 	uoff_t vsize;
 
 	memset(&metadata_hdr, 0, sizeof(metadata_hdr));
@@ -195,16 +194,10 @@
 	str_printfa(str, "%c%llx\n", DBOX_METADATA_VIRTUAL_SIZE,
 		    (unsigned long long)vsize);
 
-	/* we can use user-given GUID if
-	   a) we're not saving to a multi-file,
-	   b) it's 128 bit hex-encoded */
 	guid = ctx->ctx.guid;
-	if (ctx->ctx.guid != NULL && ctx->cur_file->single_mbox == NULL) {
-		guid_buf = buffer_create_dynamic(pool_datastack_create(),
-						 sizeof(guid_128));
-		dbox_get_guid_128(guid, guid_buf);
-		memcpy(guid_128, guid_buf->data, sizeof(guid_128));
-	} else {
+	if (ctx->ctx.guid != NULL)
+		mail_generate_guid_128_hash(guid, guid_128);
+	else {
 		mail_generate_guid_128(guid_128);
 		guid = binary_to_hex(guid_128, sizeof(guid_128));
 	}
--- a/src/lib-storage/index/dbox/dbox-storage-rebuild.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-storage-rebuild.c	Mon Jul 13 22:24:27 2009 -0400
@@ -17,7 +17,7 @@
 #include <unistd.h>
 
 struct dbox_rebuild_msg {
-	uint8_t guid_128[DBOX_GUID_BIN_LEN];
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
 	uint32_t file_id;
 	uint32_t offset;
 	uint32_t size;
@@ -60,7 +60,7 @@
         const uint8_t *s = p;
 	unsigned int i, g, h = 0;
 
-	for (i = 0; i < DBOX_GUID_BIN_LEN; i++) {
+	for (i = 0; i < MAIL_GUID_128_SIZE; i++) {
 		h = (h << 4) + s[i];
 		if ((g = h & 0xf0000000UL)) {
 			h = h ^ (g >> 24);
@@ -72,7 +72,7 @@
 
 static int guid_cmp(const void *p1, const void *p2)
 {
-	return memcmp(p1, p2, DBOX_GUID_BIN_LEN);
+	return memcmp(p1, p2, MAIL_GUID_128_SIZE);
 }
 
 static struct dbox_storage_rebuild_context *
@@ -133,7 +133,6 @@
 	const char *fname, *guid;
 	struct dbox_rebuild_msg *rec;
 	uint32_t file_id;
-	buffer_t *guid_buf;
 	uoff_t offset, prev_offset, size;
 	bool last, expunged, first, fixed = FALSE;
 	int ret = 0;
@@ -154,9 +153,6 @@
 		ctx->msgs_unsorted = TRUE;
 	ctx->prev_file_id = file_id;
 
-	guid_buf = buffer_create_dynamic(pool_datastack_create(),
-					 DBOX_GUID_BIN_LEN);
-
 	file = dbox_file_init_multi(ctx->storage, file_id);
 	prev_offset = 0;
 	dbox_file_seek_rewind(file);
@@ -198,16 +194,15 @@
 			ret = 0;
 			break;
 		}
-		dbox_get_guid_128(guid, guid_buf);
 
 		rec = p_new(ctx->pool, struct dbox_rebuild_msg, 1);
 		rec->file_id = file_id;
 		rec->offset = offset;
 		rec->size = file->input->v_offset - offset;
-		memcpy(rec->guid_128, guid_buf->data, sizeof(rec->guid_128));
+		mail_generate_guid_128_hash(guid, rec->guid_128);
 		array_append(&ctx->msgs, &rec, 1);
 
-		if (hash_table_lookup(ctx->guid_hash, guid_buf->data) != NULL) {
+		if (hash_table_lookup(ctx->guid_hash, rec->guid_128) != NULL) {
 			/* duplicate. save this as a refcount=0 to map,
 			   so it will eventually be deleted. */
 			rec->seen_zero_ref_in_map = TRUE;
--- a/src/lib-storage/index/dbox/dbox-storage.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-storage.c	Mon Jul 13 22:24:27 2009 -0400
@@ -176,7 +176,7 @@
 					sizeof(struct dbox_index_header), 0, 0);
 	mbox->guid_ext_id =
 		mail_index_ext_register(mbox->ibox.index, "guid",
-					0, DBOX_GUID_BIN_LEN, 1);
+					0, MAIL_GUID_128_SIZE, 1);
 
 	mbox->maildir_uidlist = maildir_uidlist_init_readonly(&mbox->ibox);
 	return &mbox->ibox.box;
--- a/src/lib-storage/index/dbox/dbox-storage.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-storage.h	Mon Jul 13 22:24:27 2009 -0400
@@ -20,7 +20,6 @@
 #define DBOX_MAIL_FILE_MULTI_FORMAT DBOX_MAIL_FILE_MULTI_PREFIX"%u"
 #define DBOX_MAIL_FILE_UID_FORMAT DBOX_MAIL_FILE_UID_PREFIX"%u"
 #define DBOX_MAIL_FILE_BROKEN_COPY_SUFFIX ".broken"
-#define DBOX_GUID_BIN_LEN (128/8)
 
 /* How often to scan for stale temp files (based on dir's atime) */
 #define DBOX_TMP_SCAN_SECS (8*60*60)
--- a/src/lib-storage/index/dbox/dbox-sync-file.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-sync-file.c	Mon Jul 13 22:24:27 2009 -0400
@@ -5,6 +5,7 @@
 #include "istream.h"
 #include "ostream.h"
 #include "str.h"
+#include "hex-binary.h"
 #include "dbox-storage.h"
 #include "dbox-file.h"
 #include "dbox-map.h"
@@ -268,22 +269,62 @@
 	}
 }
 
+static int
+dbox_sync_verify_expunge_guid(struct dbox_sync_context *ctx,
+			      const struct dbox_sync_expunge *expunge)
+{
+	const void *data;
+	uint32_t uid;
+
+	mail_index_lookup_uid(ctx->sync_view, expunge->seq, &uid);
+	mail_index_lookup_ext(ctx->sync_view, expunge->seq,
+			      ctx->mbox->guid_ext_id, &data, NULL);
+	if (mail_guid_128_is_empty(expunge->guid_128) ||
+	    memcmp(data, expunge->guid_128, MAIL_GUID_128_SIZE) == 0)
+		return 0;
+
+	mail_storage_set_critical(&ctx->mbox->storage->storage,
+		"Mailbox %s: Expunged GUID mismatch for UID %u: %s vs %s",
+		ctx->mbox->ibox.box.vname, uid,
+		binary_to_hex(data, MAIL_GUID_128_SIZE),
+		binary_to_hex(expunge->guid_128, MAIL_GUID_128_SIZE));
+	return -1;
+}
+
+static int
+dbox_sync_verify_expunge_guids(struct dbox_sync_context *ctx,
+			       const struct dbox_sync_file_entry *entry)
+{
+	const struct dbox_sync_expunge *expunges;
+	unsigned int i, count;
+
+	expunges = array_get(&entry->expunges, &count);
+	for (i = 0; i < count; i++) {
+		if (dbox_sync_verify_expunge_guid(ctx, &expunges[i]) < 0)
+			return -1;
+	}
+	return 0;
+}
+
 static void
 dbox_sync_mark_expunges(struct dbox_sync_context *ctx,
-			const ARRAY_TYPE(seq_range) *seqs)
+			const struct dbox_sync_file_entry *entry)
 {
 	struct mailbox *box = &ctx->mbox->ibox.box;
-	struct seq_range_iter iter;
-	unsigned int i;
-	uint32_t seq, uid;
+	const struct dbox_sync_expunge *expunges;
+	unsigned int i, count;
+	const void *data;
+	uint32_t uid;
 
-	seq_range_array_iter_init(&iter, seqs); i = 0;
-	while (seq_range_array_iter_nth(&iter, i++, &seq)) {
-		mail_index_expunge(ctx->trans, seq);
-		if (box->v.sync_notify != NULL) {
-			mail_index_lookup_uid(ctx->sync_view, seq, &uid);
+	expunges = array_get(&entry->expunges, &count);
+	for (i = 0; i < count; i++) {
+		mail_index_lookup_uid(ctx->sync_view, expunges[i].seq, &uid);
+		mail_index_lookup_ext(ctx->sync_view, expunges[i].seq,
+				      ctx->mbox->guid_ext_id, &data, NULL);
+		mail_index_expunge_guid(ctx->trans, expunges[i].seq, data);
+
+		if (box->v.sync_notify != NULL)
 			box->v.sync_notify(box, uid, MAILBOX_SYNC_TYPE_EXPUNGE);
-		}
 	}
 }
 
@@ -297,14 +338,17 @@
 	file = entry->file_id != 0 ?
 		dbox_file_init_multi(mbox->storage, entry->file_id) :
 		dbox_file_init_single(mbox, entry->uid);
-	if (!array_is_created(&entry->expunge_map_uids)) {
+	if (!array_is_created(&entry->expunges)) {
 		/* no expunges - we want to move it */
 		dbox_sync_file_move_if_needed(file, entry);
+	} else if (dbox_sync_verify_expunge_guids(ctx, entry) < 0) {
+		/* guid mismatches, see if index rebuilding helps */
+		ret = 0;
 	} else if (entry->uid != 0) {
 		/* single-message file, we can unlink it */
 		if ((ret = dbox_sync_file_unlink(file)) == 0) {
 			/* file was lost, delete it */
-			dbox_sync_mark_expunges(ctx, &entry->expunge_seqs);
+			dbox_sync_mark_expunges(ctx, entry);
 			ret = 1;
 		}
 	} else {
@@ -314,10 +358,10 @@
 							   FALSE);
 		}
 		if (dbox_map_update_refcounts(ctx->map_trans,
-					      &entry->expunge_map_uids, -1) < 0)
+					(void *)&entry->expunges, -1) < 0)
 			ret = -1;
 		else
-			dbox_sync_mark_expunges(ctx, &entry->expunge_seqs);
+			dbox_sync_mark_expunges(ctx, entry);
 	}
 	dbox_file_unref(&file);
 	return ret;
--- a/src/lib-storage/index/dbox/dbox-sync.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-sync.c	Mon Jul 13 22:24:27 2009 -0400
@@ -40,6 +40,7 @@
 			     uint32_t seq)
 {
 	struct dbox_sync_file_entry *entry, lookup_entry;
+	struct dbox_sync_expunge *expunge;
 	uint32_t map_uid;
 	uoff_t offset;
 	int ret;
@@ -75,14 +76,16 @@
 	}
 
 	if (sync_rec->type == MAIL_INDEX_SYNC_TYPE_EXPUNGE) {
-		if (!array_is_created(&entry->expunge_map_uids)) {
-			p_array_init(&entry->expunge_map_uids, ctx->pool,
-				     lookup_entry.uid != 0 ? 1 : 3);
-			p_array_init(&entry->expunge_seqs, ctx->pool,
+		if (!array_is_created(&entry->expunges)) {
+			p_array_init(&entry->expunges, ctx->pool,
 				     lookup_entry.uid != 0 ? 1 : 3);
 		}
-		seq_range_array_add(&entry->expunge_seqs, 0, seq);
-		array_append(&entry->expunge_map_uids, &map_uid, 1);
+
+		expunge = array_append_space(&entry->expunges);
+		expunge->map_uid = map_uid;
+		expunge->seq = seq;
+		memcpy(expunge->guid_128, sync_rec->guid_128,
+		       sizeof(expunge->guid_128));
 		if (entry->file_id != 0)
 			ctx->have_storage_expunges = TRUE;
 	} else {
--- a/src/lib-storage/index/dbox/dbox-sync.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/dbox/dbox-sync.h	Mon Jul 13 22:24:27 2009 -0400
@@ -11,13 +11,20 @@
 	DBOX_SYNC_FLAG_NO_PURGE		= 0x08
 };
 
+struct dbox_sync_expunge {
+	/* keep map_uid first, so we can just cast it to
+	   dbox_map_update_refcounts() */
+	uint32_t map_uid;
+	uint32_t seq;
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
+};
+
 struct dbox_sync_file_entry {
 	uint32_t uid, file_id;
 
 	unsigned int move_from_alt:1;
 	unsigned int move_to_alt:1;
-	ARRAY_TYPE(seq_range) expunge_seqs;
-	ARRAY_TYPE(uint32_t) expunge_map_uids;
+	ARRAY_DEFINE(expunges, struct dbox_sync_expunge);
 };
 
 struct dbox_sync_context {
--- a/src/lib-storage/index/index-fetch.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/index-fetch.c	Mon Jul 13 22:24:27 2009 -0400
@@ -39,23 +39,59 @@
 	}
 }
 
-bool index_storage_get_expunged_uids(struct mailbox *box, uint64_t modseq,
-				     const ARRAY_TYPE(seq_range) *uids,
-				     ARRAY_TYPE(seq_range) *expunged_uids)
+static void
+add_expunges(ARRAY_TYPE(mailbox_expunge_rec) *expunges,
+	     const struct mail_transaction_expunge *src, size_t src_size,
+	     const ARRAY_TYPE(seq_range) *uids_filter)
+{
+	const struct mail_transaction_expunge *end;
+	struct mailbox_expunge_rec *expunge;
+	uint32_t uid;
+
+	end = src + src_size / sizeof(*src);
+	for (; src != end; src++) {
+		for (uid = src->uid1; uid < src->uid2; uid++) {
+			if (seq_range_exists(uids_filter, uid)) {
+				expunge = array_append_space(expunges);
+				expunge->uid = uid;
+			}
+		}
+	}
+}
+
+static void
+add_guid_expunges(ARRAY_TYPE(mailbox_expunge_rec) *expunges,
+		  const struct mail_transaction_expunge_guid *src,
+		  size_t src_size, const ARRAY_TYPE(seq_range) *uids_filter)
+{
+	const struct mail_transaction_expunge_guid *end;
+	struct mailbox_expunge_rec *expunge;
+
+	end = src + src_size / sizeof(*src);
+	for (; src != end; src++) {
+		if (seq_range_exists(uids_filter, src->uid)) {
+			expunge = array_append_space(expunges);
+			expunge->uid = src->uid;
+			memcpy(expunge->guid_128, src->guid_128,
+			       sizeof(expunge->guid_128));
+		}
+	}
+}
+
+bool index_storage_get_expunged_uids(struct mailbox *box, uint64_t prev_modseq,
+				     const ARRAY_TYPE(seq_range) *uids_filter,
+				     ARRAY_TYPE(mailbox_expunge_rec) *expunges)
 {
 #define EXPUNGE_MASK (MAIL_TRANSACTION_EXPUNGE | MAIL_TRANSACTION_EXTERNAL)
 	struct index_mailbox *ibox = (struct index_mailbox *)box;
 	struct mail_transaction_log_view *log_view;
 	const struct mail_transaction_header *thdr;
-	const struct mail_transaction_expunge *rec, *end;
-	const struct seq_range *uid_range;
-	unsigned int count;
 	const void *tdata;
-	uint32_t log_seq, min_uid, max_uid;
+	uint32_t log_seq;
 	uoff_t log_offset;
 	bool reset;
 
-	if (!mail_index_modseq_get_next_log_offset(ibox->view, modseq,
+	if (!mail_index_modseq_get_next_log_offset(ibox->view, prev_modseq,
 						   &log_seq, &log_offset))
 		return FALSE;
 	if (log_seq > ibox->view->log_file_head_seq ||
@@ -74,28 +110,22 @@
 		return FALSE;
 	}
 
-	/* do only minimal range checks while adding the UIDs. */
-	uid_range = array_get(uids, &count);
-	i_assert(count > 0);
-	min_uid = uid_range[0].seq1;
-	max_uid = uid_range[count-1].seq2;
-
 	while (mail_transaction_log_view_next(log_view, &thdr, &tdata) > 0) {
-		if ((thdr->type & EXPUNGE_MASK) != EXPUNGE_MASK)
+		if ((thdr->type & MAIL_TRANSACTION_EXTERNAL) == 0) {
+			/* skip expunge requests */
 			continue;
-
-		rec = tdata;
-		end = rec + thdr->size / sizeof(*rec);
-		for (; rec != end; rec++) {
-			if (!(rec->uid1 > max_uid || rec->uid2 < min_uid)) {
-				seq_range_array_add_range(expunged_uids,
-							  rec->uid1, rec->uid2);
-			}
+		}
+		switch (thdr->type) {
+		case MAIL_TRANSACTION_EXPUNGE:
+			add_expunges(expunges, tdata, thdr->size, uids_filter);
+			break;
+		case MAIL_TRANSACTION_EXPUNGE_GUID:
+			add_guid_expunges(expunges, tdata, thdr->size,
+					  uids_filter);
+			break;
 		}
 	}
 
-	/* remove UIDs not in the wanted UIDs range */
-	seq_range_array_intersect(expunged_uids, uids);
 	mail_transaction_log_view_close(&log_view);
 	return TRUE;
 }
--- a/src/lib-storage/index/index-mail.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/index-mail.c	Mon Jul 13 22:24:27 2009 -0400
@@ -1446,8 +1446,16 @@
 void index_mail_expunge(struct mail *mail)
 {
 	struct index_mail *imail = (struct index_mail *)mail;
+	const char *value;
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
 
-	mail_index_expunge(imail->trans->trans, mail->seq);
+	if (mail_get_special(mail, MAIL_FETCH_GUID, &value) < 0)
+		mail_index_expunge(imail->trans->trans, mail->seq);
+	else {
+		mail_generate_guid_128_hash(value, guid_128);
+		mail_index_expunge_guid(imail->trans->trans,
+					mail->seq, guid_128);
+	}
 }
 
 void index_mail_set_cache_corrupted(struct mail *mail,
--- a/src/lib-storage/index/index-storage.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/index-storage.h	Mon Jul 13 22:24:27 2009 -0400
@@ -146,9 +146,9 @@
 void index_storage_get_uid_range(struct mailbox *box,
 				 const ARRAY_TYPE(seq_range) *seqs,
 				 ARRAY_TYPE(seq_range) *uids);
-bool index_storage_get_expunged_uids(struct mailbox *box, uint64_t modseq,
-				     const ARRAY_TYPE(seq_range) *uids,
-				     ARRAY_TYPE(seq_range) *expunged_uids);
+bool index_storage_get_expunged_uids(struct mailbox *box, uint64_t prev_modseq,
+				     const ARRAY_TYPE(seq_range) *uids_filter,
+				     ARRAY_TYPE(mailbox_expunge_rec) *expunges);
 
 struct mailbox_header_lookup_ctx *
 index_header_lookup_init(struct mailbox *box, const char *const headers[]);
--- a/src/lib-storage/index/index-sync-changes.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/index-sync-changes.c	Mon Jul 13 22:24:27 2009 -0400
@@ -73,21 +73,26 @@
 
 static bool
 index_sync_changes_have_expunges(struct index_sync_changes_context *ctx,
-				 unsigned int count)
+				 unsigned int count,
+				 uint8_t expunged_guid_128[MAIL_GUID_128_SIZE])
 {
 	const struct mail_index_sync_rec *syncs;
 	unsigned int i;
 
 	syncs = array_idx(&ctx->syncs, 0);
 	for (i = 0; i < count; i++) {
-		if (syncs[i].type == MAIL_INDEX_SYNC_TYPE_EXPUNGE)
+		if (syncs[i].type == MAIL_INDEX_SYNC_TYPE_EXPUNGE) {
+			memcpy(expunged_guid_128, syncs[i].guid_128,
+			       MAIL_GUID_128_SIZE);
 			return TRUE;
+		}
 	}
 	return FALSE;
 }
 
 void index_sync_changes_read(struct index_sync_changes_context *ctx,
-			     uint32_t uid, bool *sync_expunge_r)
+			     uint32_t uid, bool *sync_expunge_r,
+			     uint8_t expunged_guid_128[MAIL_GUID_128_SIZE])
 {
 	struct mail_index_sync_rec *sync_rec = &ctx->sync_rec;
 	uint32_t seq1, seq2;
@@ -103,8 +108,11 @@
 		    sync_rec->type != MAIL_INDEX_SYNC_TYPE_APPEND) {
 			array_append(&ctx->syncs, sync_rec, 1);
 
-			if (sync_rec->type == MAIL_INDEX_SYNC_TYPE_EXPUNGE)
+			if (sync_rec->type == MAIL_INDEX_SYNC_TYPE_EXPUNGE) {
 				*sync_expunge_r = TRUE;
+				memcpy(expunged_guid_128, sync_rec->guid_128,
+				       MAIL_GUID_128_SIZE);
+			}
 		}
 
 		if (!mail_index_sync_next(ctx->index_sync_ctx, sync_rec)) {
@@ -145,7 +153,8 @@
 
 	if (!*sync_expunge_r && orig_count > 0) {
 		*sync_expunge_r =
-			index_sync_changes_have_expunges(ctx, orig_count);
+			index_sync_changes_have_expunges(ctx, orig_count,
+							 expunged_guid_128);
 	}
 }
 
--- a/src/lib-storage/index/index-sync-changes.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/index-sync-changes.h	Mon Jul 13 22:24:27 2009 -0400
@@ -14,7 +14,8 @@
 				  uint32_t last_uid);
 
 void index_sync_changes_read(struct index_sync_changes_context *ctx,
-			     uint32_t uid, bool *sync_expunge_r);
+			     uint32_t uid, bool *sync_expunge_r,
+			     uint8_t expunged_guid_128[MAIL_GUID_128_SIZE]);
 bool index_sync_changes_have(struct index_sync_changes_context *ctx);
 uint32_t
 index_sync_changes_get_next_uid(struct index_sync_changes_context *ctx);
--- a/src/lib-storage/index/maildir/maildir-sync-index.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/maildir/maildir-sync-index.c	Mon Jul 13 22:24:27 2009 -0400
@@ -3,6 +3,7 @@
 #include "lib.h"
 #include "ioloop.h"
 #include "array.h"
+#include "hex-binary.h"
 #include "maildir-storage.h"
 #include "index-sync-changes.h"
 #include "maildir-uidlist.h"
@@ -39,6 +40,54 @@
 	return ctx->keywords_sync_ctx;
 }
 
+static void
+maildir_index_expunge(struct maildir_index_sync_context *ctx, uint32_t seq)
+{
+	enum maildir_uidlist_rec_flag flags;
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
+	const char *fname;
+	uint32_t uid;
+
+	mail_index_lookup_uid(ctx->view, seq, &uid);
+	if (maildir_uidlist_lookup(ctx->mbox->uidlist, uid,
+				   &flags, &fname) <= 0)
+		memset(guid_128, 0, sizeof(guid_128));
+	else T_BEGIN {
+		mail_generate_guid_128_hash(t_strcut(fname, ':'),
+					    guid_128);
+	} T_END;
+
+	mail_index_expunge_guid(ctx->trans, ctx->seq, guid_128);
+}
+
+static bool
+maildir_expunge_is_valid_guid(struct maildir_index_sync_context *ctx,
+			      const char *filename,
+			      uint8_t expunged_guid_128[MAIL_GUID_128_SIZE])
+{
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
+
+	if (mail_guid_128_is_empty(expunged_guid_128)) {
+		/* no GUID associated with expunge */
+		return TRUE;
+	}
+
+	T_BEGIN {
+		mail_generate_guid_128_hash(t_strcut(filename, ':'),
+					    guid_128);
+	} T_END;
+
+	if (memcmp(guid_128, expunged_guid_128, sizeof(guid_128)) == 0)
+		return TRUE;
+
+	mail_storage_set_critical(&ctx->mbox->storage->storage,
+		"Mailbox %s: Expunged GUID mismatch for UID %u: %s vs %s",
+		ctx->mbox->ibox.box.vname, ctx->uid,
+		binary_to_hex(guid_128, sizeof(guid_128)),
+		binary_to_hex(expunged_guid_128, MAIL_GUID_128_SIZE));
+	return FALSE;
+}
+
 static int maildir_expunge(struct maildir_mailbox *mbox, const char *path,
 			   struct maildir_index_sync_context *ctx)
 {
@@ -49,7 +98,6 @@
 			box->v.sync_notify(box, ctx->uid,
 					   MAILBOX_SYNC_TYPE_EXPUNGE);
 		}
-		mail_index_expunge(ctx->trans, ctx->seq);
 		ctx->changed = TRUE;
 		return 1;
 	}
@@ -401,6 +449,7 @@
 	int ret = 0;
 	time_t time_before_sync;
 	struct stat st;
+	uint8_t expunged_guid_128[MAIL_GUID_128_SIZE];
 	bool expunged, full_rescan = FALSE;
 
 	i_assert(!mbox->syncing_commit);
@@ -485,7 +534,7 @@
 		rec = mail_index_lookup(view, seq);
 		if (uid > rec->uid) {
 			/* expunged */
-			mail_index_expunge(trans, seq);
+			maildir_index_expunge(ctx, seq);
 			goto again;
 		}
 
@@ -497,12 +546,16 @@
 			continue;
 		}
 
-		index_sync_changes_read(ctx->sync_changes, rec->uid, &expunged);
+		index_sync_changes_read(ctx->sync_changes, rec->uid, &expunged,
+					expunged_guid_128);
 		if (expunged) {
+			if (!maildir_expunge_is_valid_guid(ctx, filename,
+							   expunged_guid_128))
+				continue;
 			if (maildir_file_do(mbox, ctx->uid,
 					    maildir_expunge, ctx) >= 0) {
 				/* successful expunge */
-				mail_index_expunge(trans, seq);
+				maildir_index_expunge(ctx, seq);
 			}
 			if ((++changes % MAILDIR_SLOW_MOVE_COUNT) == 0)
 				maildir_sync_notify(ctx->maildir_sync_ctx);
@@ -551,7 +604,7 @@
 	if (!partial) {
 		/* expunge the rest */
 		for (seq++; seq <= hdr->messages_count; seq++)
-			mail_index_expunge(trans, seq);
+			maildir_index_expunge(ctx, seq);
 	}
 
 	/* add \Recent flags. use updated view so it contains newly
--- a/src/lib-storage/index/mbox/mbox-sync.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/index/mbox/mbox-sync.c	Mon Jul 13 22:24:27 2009 -0400
@@ -169,12 +169,15 @@
 static void mbox_sync_read_index_syncs(struct mbox_sync_context *sync_ctx,
 				       uint32_t uid, bool *sync_expunge_r)
 {
+	uint8_t expunged_guid_128[MAIL_GUID_128_SIZE];
+
 	if (uid == 0 || sync_ctx->index_reset) {
 		/* nothing for this or the future ones */
 		uid = (uint32_t)-1;
 	}
 
-	index_sync_changes_read(sync_ctx->sync_changes, uid, sync_expunge_r);
+	index_sync_changes_read(sync_ctx->sync_changes, uid, sync_expunge_r,
+				expunged_guid_128);
 	if (sync_ctx->mbox->ibox.backend_readonly) {
 		/* we can't expunge anything from read-only mboxes */
 		*sync_expunge_r = FALSE;
--- a/src/lib-storage/mail-storage-private.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/mail-storage-private.h	Mon Jul 13 22:24:27 2009 -0400
@@ -163,9 +163,9 @@
 	void (*get_uid_range)(struct mailbox *box,
 			      const ARRAY_TYPE(seq_range) *seqs,
 			      ARRAY_TYPE(seq_range) *uids);
-	bool (*get_expunged_uids)(struct mailbox *box, uint64_t modseq,
-				  const ARRAY_TYPE(seq_range) *uids,
-				  ARRAY_TYPE(seq_range) *expunged_uids);
+	bool (*get_expunges)(struct mailbox *box, uint64_t prev_modseq,
+			     const ARRAY_TYPE(seq_range) *uids_filter,
+			     ARRAY_TYPE(mailbox_expunge_rec) *expunges);
 	bool (*get_virtual_uid)(struct mailbox *box,
 				const char *backend_mailbox,
 				uint32_t backend_uidvalidity,
@@ -428,10 +428,13 @@
 bool mail_storage_set_error_from_errno(struct mail_storage *storage);
 
 const char *mail_generate_guid_string(void);
-void mail_generate_guid_128(uint8_t guid[16]);
+void mail_generate_guid_128(uint8_t guid[MAIL_GUID_128_SIZE]);
+void mail_generate_guid_128_hash(const char *input,
+				 uint8_t guid[MAIL_GUID_128_SIZE]);
 int mail_set_aborted(struct mail *mail);
 void mail_set_expunged(struct mail *mail);
 void mailbox_set_deleted(struct mailbox *box);
+bool mail_guid_128_is_empty(const uint8_t guid_128[MAIL_GUID_128_SIZE]);
 bool mailbox_guid_is_empty(const uint8_t guid[MAILBOX_GUID_SIZE]);
 
 #endif
--- a/src/lib-storage/mail-storage.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/mail-storage.c	Mon Jul 13 22:24:27 2009 -0400
@@ -709,11 +709,12 @@
 	box->v.get_uid_range(box, seqs, uids);
 }
 
-bool mailbox_get_expunged_uids(struct mailbox *box, uint64_t modseq,
-			       const ARRAY_TYPE(seq_range) *uids,
-			       ARRAY_TYPE(seq_range) *expunged_uids)
+bool mailbox_get_expunges(struct mailbox *box, uint64_t prev_modseq,
+			  const ARRAY_TYPE(seq_range) *uids_filter,
+			  ARRAY_TYPE(mailbox_expunge_rec) *expunges)
 {
-	return box->v.get_expunged_uids(box, modseq, uids, expunged_uids);
+	return box->v.get_expunges(box, prev_modseq,
+				   uids_filter, expunges);
 }
 
 bool mailbox_get_virtual_uid(struct mailbox *box, const char *backend_mailbox,
@@ -1072,13 +1073,18 @@
 	box->mailbox_deleted = TRUE;
 }
 
-bool mailbox_guid_is_empty(const uint8_t guid[MAILBOX_GUID_SIZE])
+bool mail_guid_128_is_empty(const uint8_t guid_128[MAIL_GUID_128_SIZE])
 {
 	unsigned int i;
 
 	for (i = 0; i < MAILBOX_GUID_SIZE; i++) {
-		if (guid[i] != 0)
+		if (guid_128[i] != 0)
 			return FALSE;
 	}
 	return TRUE;
 }
+
+bool mailbox_guid_is_empty(const uint8_t guid[MAILBOX_GUID_SIZE])
+{
+	return mail_guid_128_is_empty(guid);
+}
--- a/src/lib-storage/mail-storage.h	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/mail-storage.h	Mon Jul 13 22:24:27 2009 -0400
@@ -170,7 +170,7 @@
 struct mailbox;
 struct mailbox_transaction_context;
 
-#define MAILBOX_GUID_SIZE 16
+#define MAILBOX_GUID_SIZE MAIL_GUID_128_SIZE
 struct mailbox_status {
 	uint32_t messages;
 	uint32_t recent;
@@ -204,6 +204,15 @@
 	enum mailbox_sync_type type;
 };
 
+struct mailbox_expunge_rec {
+	/* IMAP UID */
+	uint32_t uid;
+	/* 128 bit GUID. If the actual GUID has a different size, this
+	   contains last bits of its SHA1 sum. */
+	uint8_t guid_128[MAIL_GUID_128_SIZE];
+};
+ARRAY_DEFINE_TYPE(mailbox_expunge_rec, struct mailbox_expunge_rec);
+
 enum mail_lookup_abort {
 	/* Perform everything no matter what it takes */
 	MAIL_LOOKUP_ABORT_NEVER = 0,
@@ -424,12 +433,13 @@
 void mailbox_get_uid_range(struct mailbox *box,
 			   const ARRAY_TYPE(seq_range) *seqs,
 			   ARRAY_TYPE(seq_range) *uids);
-/* Get list of UIDs expunged after modseq and within the given range.
-   UIDs that have been expunged after the last mailbox sync aren't returned.
-   Returns TRUE if ok, FALSE if modseq is lower than we can check for. */
-bool mailbox_get_expunged_uids(struct mailbox *box, uint64_t modseq,
-			       const ARRAY_TYPE(seq_range) *uids,
-			       ARRAY_TYPE(seq_range) *expunged_uids);
+/* Get list of messages' that have been expunged after prev_modseq and that
+   exist in uids_filter range. UIDs that have been expunged after the last
+   mailbox sync aren't returned. Returns TRUE if ok, FALSE if modseq is lower
+   than we can check for (but expunged_uids is still set as best as it can). */
+bool mailbox_get_expunges(struct mailbox *box, uint64_t prev_modseq,
+			  const ARRAY_TYPE(seq_range) *uids_filter,
+			  ARRAY_TYPE(mailbox_expunge_rec) *expunges);
 /* If box is a virtual mailbox, look up UID for the given backend message.
    Returns TRUE if found, FALSE if not. */
 bool mailbox_get_virtual_uid(struct mailbox *box, const char *backend_mailbox,
--- a/src/lib-storage/mail.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/mail.c	Mon Jul 13 22:24:27 2009 -0400
@@ -2,7 +2,10 @@
 
 #include "lib.h"
 #include "ioloop.h"
+#include "buffer.h"
+#include "hex-binary.h"
 #include "crc32.h"
+#include "sha1.h"
 #include "hostpid.h"
 #include "mail-storage-private.h"
 
@@ -237,7 +240,7 @@
 			       pid, my_hostname);
 }
 
-void mail_generate_guid_128(uint8_t guid[16])
+void mail_generate_guid_128(uint8_t guid[MAIL_GUID_128_SIZE])
 {
 	static struct timespec ts = { 0, 0 };
 	static uint8_t guid_static[8];
@@ -276,3 +279,25 @@
 	guid[7] = (ts.tv_sec & 0xff000000) >> 24;
 	memcpy(guid + 8, guid_static, 8);
 }
+
+void mail_generate_guid_128_hash(const char *input,
+				 uint8_t guid[MAIL_GUID_128_SIZE])
+{
+	unsigned char sha1_sum[SHA1_RESULTLEN];
+	buffer_t buf;
+
+	buffer_create_data(&buf, guid, MAIL_GUID_128_SIZE);
+	if (strlen(input) != MAIL_GUID_128_SIZE*2 ||
+	    hex_to_binary(input, &buf) < 0 ||
+	    buf.used != MAIL_GUID_128_SIZE) {
+		/* not 128bit hex. use a hash of it instead. */
+		buffer_set_used_size(&buf, 0);
+		sha1_get_digest(input, strlen(input), sha1_sum);
+#if SHA1_RESULTLEN < DBOX_GUID_BIN_LEN
+#  error not possible
+#endif
+		buffer_append(&buf,
+			      sha1_sum + SHA1_RESULTLEN - MAIL_GUID_128_SIZE,
+			      MAIL_GUID_128_SIZE);
+	}
+}
--- a/src/lib-storage/test-mailbox.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/lib-storage/test-mailbox.c	Mon Jul 13 22:24:27 2009 -0400
@@ -192,9 +192,9 @@
 
 static bool
 test_mailbox_get_expunged_uids(struct mailbox *box ATTR_UNUSED,
-			       uint64_t modseq ATTR_UNUSED,
-			       const ARRAY_TYPE(seq_range) *uids ATTR_UNUSED,
-			       ARRAY_TYPE(seq_range) *expunged_uids ATTR_UNUSED)
+			       uint64_t prev_modseq ATTR_UNUSED,
+			       const ARRAY_TYPE(seq_range) *uids_filter ATTR_UNUSED,
+			       ARRAY_TYPE(mailbox_expunge_rec) *expunges ATTR_UNUSED)
 {
 	return FALSE;
 }
--- a/src/util/logview.c	Mon Jul 13 21:11:05 2009 -0400
+++ b/src/util/logview.c	Mon Jul 13 22:24:27 2009 -0400
@@ -1,6 +1,7 @@
 /* Copyright (c) 2007-2009 Dovecot authors, see the included COPYING file */
 
 #include "lib.h"
+#include "hex-binary.h"
 #include "mail-index-private.h"
 #include "mail-transaction-log.h"
 
@@ -54,6 +55,7 @@
 {
 	switch (hdr->type & MAIL_TRANSACTION_TYPE_MASK) {
 	case MAIL_TRANSACTION_EXPUNGE | MAIL_TRANSACTION_EXPUNGE_PROT:
+	case MAIL_TRANSACTION_EXPUNGE_GUID | MAIL_TRANSACTION_EXPUNGE_PROT:
 		if ((hdr->type & MAIL_TRANSACTION_EXTERNAL) == 0) {
 			/* ignore expunge requests */
 			break;
@@ -75,6 +77,9 @@
 	case MAIL_TRANSACTION_EXPUNGE|MAIL_TRANSACTION_EXPUNGE_PROT:
 		name = "expunge";
 		break;
+	case MAIL_TRANSACTION_EXPUNGE_GUID|MAIL_TRANSACTION_EXPUNGE_PROT:
+		name = "expunge-guid";
+		break;
 	case MAIL_TRANSACTION_APPEND:
 		name = "append";
 		break;
@@ -248,6 +253,16 @@
 		printf("\n");
 		break;
 	}
+	case MAIL_TRANSACTION_EXPUNGE_GUID|MAIL_TRANSACTION_EXPUNGE_PROT: {
+		const struct mail_transaction_expunge_guid *exp = data;
+
+		for (; size > 0; size -= sizeof(*exp), exp++) {
+			printf(" - %u (guid ", exp->uid);
+			print_data(exp->guid_128, sizeof(exp->guid_128));
+			printf(")\n");
+		}
+		break;
+	}
 	case MAIL_TRANSACTION_APPEND: {
 		const struct mail_index_record *rec = data;