--- a/src/lib-index/mail-index-sync-update.c	Thu Aug 13 12:40:19 2009 -0400
+++ b/src/lib-index/mail-index-sync-update.c	Thu Aug 13 14:50:41 2009 -0400
@@ -236,44 +236,81 @@
 	}
 }
 
-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;
+
+	if (!mail_index_lookup_seq_range(ctx->view, uid1, uid2, &seq1, &seq2)) {
+		/* everything expunged already */
+		return;
+	}
+
+	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);
+	}
 
-	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;
-		}
+	/* @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);
 
-		sync_expunge_call_handlers(ctx, seq1, seq2);
+	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);
+}
+
+static void *sync_append_record(struct mail_index_map *map)
+{
+	size_t append_pos;
+	void *ret;
 
-		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);
-		}
+	append_pos = map->rec_map->records_count * map->hdr.record_size;
+	ret = buffer_get_space_unsafe(map->rec_map->buffer, append_pos,
+				      map->hdr.record_size);
+	map->rec_map->records =
+		buffer_get_modifiable_data(map->rec_map->buffer, NULL);
+	return ret;
+}
+
+static void sync_uid_update(struct mail_index_sync_map_ctx *ctx,
+			    uint32_t old_uid, uint32_t new_uid)
+{
+	struct mail_index_map *map;
+	struct mail_index_record *rec;
+	uint32_t old_seq;
+	void *dest;
 
-		/* @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);
+	if (new_uid < ctx->view->map->hdr.next_uid) {
+		/* uid update is no longer possible */
+		return;
+	}
+
+	if (!mail_index_lookup_seq(ctx->view, old_uid, &old_seq))
+		return;
 
-		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;
+	map = mail_index_sync_get_atomic_map(ctx);
+	map->hdr.next_uid = new_uid+1;
+	map->rec_map->last_appended_uid = new_uid;
+
+	/* add the new record */
+	dest = sync_append_record(map);
+	rec = MAIL_INDEX_MAP_IDX(map, old_seq-1);
+	rec->uid = new_uid;
+	memcpy(dest, rec, map->hdr.record_size);
+
+	/* @UNSAFE: remove the old record */
+	memmove(rec, PTR_OFFSET(rec, map->hdr.record_size),
+		(map->rec_map->records_count + 1 - old_seq) *
+		map->hdr.record_size);
 }
 
 void mail_index_sync_write_seq_update(struct mail_index_sync_map_ctx *ctx,
@@ -296,7 +333,6 @@
 	const struct mail_index_record *old_rec;
 	enum mail_flags new_flags;
 	void *dest;
-	size_t append_pos;
 
 	if (rec->uid < map->hdr.next_uid) {
 		mail_index_sync_set_corrupted(ctx,
@@ -322,12 +358,7 @@
 	} else {
 		/* don't rely on buffer->used being at the correct position.
 		   at least expunges can move it */
-		append_pos = map->rec_map->records_count * map->hdr.record_size;
-		dest = buffer_get_space_unsafe(map->rec_map->buffer, append_pos,
-					       map->hdr.record_size);
-		map->rec_map->records =
-			buffer_get_modifiable_data(map->rec_map->buffer, NULL);
-
+		dest = sync_append_record(map);
 		memcpy(dest, rec, sizeof(*rec));
 		memset(PTR_OFFSET(dest, sizeof(*rec)), 0,
 		       map->hdr.record_size - sizeof(*rec));
@@ -484,7 +515,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: {
@@ -642,6 +687,19 @@
 		ret = mail_index_sync_keywords_reset(ctx, hdr, rec);
 		break;
 	}
+	case MAIL_TRANSACTION_UID_UPDATE: {
+		const struct mail_transaction_uid_update *rec = data, *end;
+
+		end = CONST_PTR_OFFSET(data, hdr->size);
+		for (rec = data; rec < end; rec++)
+			sync_uid_update(ctx, rec->old_uid, rec->new_uid);
+		break;
+	}
+	case MAIL_TRANSACTION_MODSEQ_UPDATE: {
+		/* just ignore modseq updates. they're not so hugely
+		   important. */
+		break;
+	}
 	default:
 		mail_index_sync_set_corrupted(ctx,
 			"Unknown transaction record type 0x%x",

--- a/src/lib-index/mail-index-sync.c	Thu Aug 13 12:40:19 2009 -0400
+++ b/src/lib-index/mail-index-sync.c	Thu Aug 13 14:50:41 2009 -0400
@@ -41,6 +41,16 @@
 	}
 }
 
+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(ctx->sync_trans, e[i].uid);
+}
+
+
 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 +139,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;
@@ -509,6 +522,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:

--- a/src/lib-index/mail-index-view-sync.c	Thu Aug 13 12:40:19 2009 -0400
+++ b/src/lib-index/mail-index-view-sync.c	Thu Aug 13 14:50:41 2009 -0400
@@ -42,71 +42,6 @@
 };
 
 static int
-mail_transaction_log_sort_expunges(ARRAY_TYPE(seq_range) *expunges,
-				   const struct seq_range *src, size_t src_size)
-{
-	/* Note that all the sequences are actually still UIDs at this point */
-	const struct seq_range *src_end;
-	struct seq_range *dest, new_exp;
-	unsigned int first, i, dest_count;
-
-	i_assert(src_size % sizeof(*src) == 0);
-
-	/* @UNSAFE */
-	dest = array_get_modifiable(expunges, &dest_count);
-	if (dest_count == 0) {
-		array_append(expunges, src, src_size / sizeof(*src));
-		return 0;
-	}
-
-	src_end = CONST_PTR_OFFSET(src, src_size);
-	for (i = 0; src != src_end; src++) {
-		/* src[] must be sorted. */
-		if (src->seq1 > src->seq2 ||
-		    (src+1 != src_end && src->seq2 >= src[1].seq1))
-			return -1;
-
-		for (; i < dest_count; i++) {
-			if (src->seq1 < dest[i].seq1)
-				break;
-		}
-
-		new_exp = *src;
-
-		first = i;
-		while (i < dest_count && src->seq2 >= dest[i].seq1-1) {
-			/* we can/must merge with next record */
-			if (new_exp.seq2 < dest[i].seq2)
-				new_exp.seq2 = dest[i].seq2;
-			i++;
-		}
-
-		if (first > 0 && new_exp.seq1 <= dest[first-1].seq2+1) {
-			/* continue previous record */
-			if (dest[first-1].seq2 < new_exp.seq2)
-				dest[first-1].seq2 = new_exp.seq2;
-		} else if (i == first) {
-			array_insert(expunges, i, &new_exp, 1);
-			i++; first++;
-
-			dest = array_get_modifiable(expunges, &dest_count);
-		} else {
-			/* use next record */
-			dest[first] = new_exp;
-			first++;
-		}
-
-		if (i > first) {
-			array_delete(expunges, first, i - first);
-
-			dest = array_get_modifiable(expunges, &dest_count);
-			i = first;
-		}
-	}
-	return 0;
-}
-
-static int
 view_sync_set_log_view_range(struct mail_index_view *view, bool sync_expunges,
 			     bool *reset_r)
 {
@@ -175,6 +110,33 @@
 	return expunge_count;
 }
 
+static void
+view_sync_add_expunge_range(ARRAY_TYPE(seq_range) *dest,
+			    const struct seq_range *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_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)
@@ -190,18 +152,16 @@
 	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;
 		}
-
-		if (mail_transaction_log_sort_expunges(&ctx->expunges, data,
-						       hdr->size) < 0) {
-			mail_transaction_log_view_set_corrupted(view->log_view,
-				"Corrupted expunge record");
-			return -1;
+		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);
@@ -225,6 +185,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;
@@ -236,17 +212,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;
+			}
 		}
 	}
 
@@ -672,7 +653,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,
@@ -744,10 +726,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-transaction-log-file.c	Thu Aug 13 12:40:19 2009 -0400
+++ b/src/lib-index/mail-transaction-log-file.c	Thu Aug 13 14:50:41 2009 -0400
@@ -820,6 +820,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;
@@ -828,6 +829,7 @@
 	case MAIL_TRANSACTION_FLAG_UPDATE:
 	case MAIL_TRANSACTION_KEYWORD_UPDATE:
 	case MAIL_TRANSACTION_KEYWORD_RESET:
+	case MAIL_TRANSACTION_UID_UPDATE:
 		/* these changes increase modseq */
 		return TRUE;
 	}

--- a/src/lib-index/mail-transaction-log-view.c	Thu Aug 13 12:40:19 2009 -0400
+++ b/src/lib-index/mail-transaction-log-view.c	Thu Aug 13 14:50:41 2009 -0400
@@ -446,6 +446,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,
@@ -471,6 +480,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:
 		uid_buf = buffer_create_const_data(pool_datastack_create(),
 						   data, rec_size);
@@ -646,7 +662,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	Thu Aug 13 12:40:19 2009 -0400
+++ b/src/lib-index/mail-transaction-log.h	Thu Aug 13 14:50:41 2009 -0400
@@ -38,6 +38,9 @@
 	MAIL_TRANSACTION_EXT_REC_UPDATE		= 0x00000200,
 	MAIL_TRANSACTION_KEYWORD_UPDATE		= 0x00000400,
 	MAIL_TRANSACTION_KEYWORD_RESET		= 0x00000800,
+	MAIL_TRANSACTION_EXPUNGE_GUID		= 0x00002000,
+	MAIL_TRANSACTION_UID_UPDATE		= 0x00004000,
+	MAIL_TRANSACTION_MODSEQ_UPDATE		= 0x00008000,
 
 	MAIL_TRANSACTION_TYPE_MASK		= 0x0000ffff,
 
@@ -60,10 +63,27 @@
 	uint32_t type; /* enum mail_transaction_type */
 };
 
+struct mail_transaction_uid_update {
+	uint32_t old_uid, new_uid;
+};
+
+struct mail_transaction_modseq_update {
+	uint32_t uid;
+	/* don't use uint64_t here. it adds extra 32 bits of paddiong and also
+	   causes problems with CPUs that require alignment */
+	uint32_t modseq_low32;
+	uint32_t modseq_high32;
+};
+
 struct mail_transaction_expunge {
 	uint32_t uid1, uid2;
 };
 
+struct mail_transaction_expunge_guid {
+	uint32_t uid;
+	uint8_t guid_128[16];
+};
+
 struct mail_transaction_flag_update {
 	uint32_t uid1, uid2;
 	uint8_t add_flags;