--- a/src/imap/cmd-store.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/imap/cmd-store.c	Sat Jun 21 07:43:54 2008 +0300
@@ -122,7 +122,7 @@
         struct mailbox_transaction_context *t;
 	struct mail *mail;
 	struct imap_store_context ctx;
-	ARRAY_TYPE(seq_range) modified_set = ARRAY_INIT;
+	ARRAY_TYPE(seq_range) modified_set, uids;
 	enum mailbox_transaction_flags flags = 0;
 	enum imap_sync_flags imap_sync_flags = 0;
 	const char *reply, *tagged_reply;
@@ -161,21 +161,30 @@
 
 	if (ctx.silent)
 		flags |= MAILBOX_TRANSACTION_FLAG_HIDE;
-	if (ctx.max_modseq < (uint64_t)-1)
+	if (ctx.max_modseq < (uint64_t)-1) {
+		/* update modseqs so we can check them early */
 		flags |= MAILBOX_TRANSACTION_FLAG_REFRESH;
+	}
 
 	t = mailbox_transaction_begin(client->mailbox, flags);
 	search_ctx = mailbox_search_init(t, search_args, NULL);
 	mail_search_args_unref(&search_args);
 
-	/* FIXME: UNCHANGEDSINCE should be atomic, but this requires support
-	   from mail-storage API. So for now we fake it. */
+	i_array_init(&modified_set, 64);
+	if (ctx.max_modseq < (uint32_t)-1) {
+		/* STORE UNCHANGEDSINCE is being used */
+		mailbox_transaction_set_max_modseq(t, ctx.max_modseq,
+						   &modified_set);
+	}
+
 	mail = mail_alloc(t, MAIL_FETCH_FLAGS, NULL);
 	while (mailbox_search_next(search_ctx, mail) > 0) {
 		if (ctx.max_modseq < (uint64_t)-1) {
+			/* check early so there's less work for transaction
+			   commit if something has to be cancelled */
 			if (mail_get_modseq(mail) > ctx.max_modseq) {
-				seq_range_array_add(&modified_set, 64,
-					cmd->uid ? mail->uid : mail->seq);
+				seq_range_array_add(&modified_set, 0,
+						    mail->seq);
 				continue;
 			}
 		}
@@ -188,17 +197,6 @@
 	}
 	mail_free(&mail);
 
-	if (!array_is_created(&modified_set))
-		tagged_reply = "OK Store completed.";
-	else {
-		str = str_new(cmd->pool, 256);
-		str_append(str, "OK [MODIFIED ");
-		imap_write_seq_range(str, &modified_set);
-		array_free(&modified_set);
-		str_append(str, "] Conditional store failed.");
-		tagged_reply = str_c(str);
-	}
-
 	if (ctx.keywords != NULL)
 		mailbox_keywords_free(client->mailbox, &ctx.keywords);
 
@@ -208,11 +206,30 @@
 	 else
 		ret = mailbox_transaction_commit(&t);
 	if (ret < 0) {
+		array_free(&modified_set);
 		client_send_storage_error(cmd,
 			mailbox_get_storage(client->mailbox));
 		return TRUE;
 	}
 
+	if (array_count(&modified_set) == 0)
+		tagged_reply = "OK Store completed.";
+	else {
+		if (cmd->uid) {
+			i_array_init(&uids, array_count(&modified_set)*2);
+			mailbox_get_uid_range(client->mailbox, &modified_set,
+					      &uids);
+			array_free(&modified_set);
+			modified_set = uids;
+		}
+		str = str_new(cmd->pool, 256);
+		str_append(str, "OK [MODIFIED ");
+		imap_write_seq_range(str, &modified_set);
+		str_append(str, "] Conditional store failed.");
+		tagged_reply = str_c(str);
+	}
+	array_free(&modified_set);
+
 	/* With UID STORE we have to return UID for the flags as well.
 	   Unfortunately we don't have the ability to separate those
 	   flag changes that were caused by UID STORE and those that

--- a/src/lib-index/mail-index-transaction-private.h	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-index/mail-index-transaction-private.h	Sat Jun 21 07:43:54 2008 +0300
@@ -37,6 +37,8 @@
 	   mail_index_transaction_reset() to reset it. */
         ARRAY_DEFINE(appends, struct mail_index_record);
 	uint32_t first_new_seq, last_new_seq;
+	/* lowest/highest sequence that updates flags/keywords */
+	uint32_t min_flagupdate_seq, max_flagupdate_seq;
 
 	ARRAY_TYPE(seq_range) expunges;
 	ARRAY_DEFINE(updates, struct mail_transaction_flag_update);
@@ -59,6 +61,9 @@
 		     struct mail_index_transaction_keyword_update);
 	ARRAY_TYPE(seq_range) keyword_resets;
 
+	uint64_t max_modseq;
+	ARRAY_TYPE(seq_range) *conflict_seqs;
+
         struct mail_cache_transaction_ctx *cache_trans_ctx;
 
 	/* Module-specific contexts. */
@@ -92,6 +97,8 @@
 
 void mail_index_transaction_sort_appends(struct mail_index_transaction *t);
 uint32_t mail_index_transaction_get_next_uid(struct mail_index_transaction *t);
+void mail_index_transaction_convert_to_uids(struct mail_index_transaction *t);
+void mail_index_transaction_check_conflicts(struct mail_index_transaction *t);
 
 bool mail_index_seq_array_lookup(const ARRAY_TYPE(seq_array) *array,
 				 uint32_t seq, unsigned int *idx_r);

--- a/src/lib-index/mail-index-transaction.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-index/mail-index-transaction.c	Sat Jun 21 07:43:54 2008 +0300
@@ -10,6 +10,7 @@
 #include "bsearch-insert-pos.h"
 #include "seq-range-array.h"
 #include "mail-index-view-private.h"
+#include "mail-index-modseq.h"
 #include "mail-transaction-log.h"
 #include "mail-cache-private.h"
 #include "mail-index-transaction-private.h"
@@ -83,6 +84,8 @@
 	t->first_new_seq = mail_index_view_get_messages_count(t->view)+1;
 	t->last_new_seq = 0;
 	t->last_update_idx = 0;
+	t->min_flagupdate_seq = 0;
+	t->max_flagupdate_seq = 0;
 
 	memset(t->pre_hdr_mask, 0, sizeof(t->pre_hdr_mask));
 	memset(t->post_hdr_mask, 0, sizeof(t->post_hdr_mask));
@@ -300,8 +303,7 @@
 	}
 }
 
-static int
-mail_index_transaction_convert_to_uids(struct mail_index_transaction *t)
+void mail_index_transaction_convert_to_uids(struct mail_index_transaction *t)
 {
 	ARRAY_TYPE(seq_array) *updates;
 	unsigned int i, count;
@@ -317,7 +319,6 @@
 	mail_index_convert_to_uid_ranges(t, &t->expunges);
 	mail_index_convert_to_uid_ranges(t, (void *)&t->updates);
 	mail_index_convert_to_uid_ranges(t, &t->keyword_resets);
-	return 0;
 }
 
 struct uid_map {
@@ -584,12 +585,7 @@
 		mail_index_update_day_headers(t);
 	}
 
-	if (mail_index_transaction_convert_to_uids(t) < 0)
-		ret = -1;
-	else {
-		ret = mail_transaction_log_append(t, log_file_seq_r,
-						  log_file_offset_r);
-	}
+	ret = mail_transaction_log_append(t, log_file_seq_r, log_file_offset_r);
 
 	if (ret == 0 && !t->view->index->syncing) {
 		/* if we're committing a normal transaction, we want to
@@ -772,6 +768,20 @@
 	}
 }
 
+static void update_minmax_flagupdate_seq(struct mail_index_transaction *t,
+					 uint32_t seq1, uint32_t seq2)
+{
+	if (t->min_flagupdate_seq == 0) {
+		t->min_flagupdate_seq = seq1;
+		t->max_flagupdate_seq = seq2;
+	} else {
+		if (t->min_flagupdate_seq > seq1)
+			t->min_flagupdate_seq = seq1;
+		if (t->max_flagupdate_seq < seq2)
+			t->max_flagupdate_seq = seq2;
+	}
+}
+
 static bool
 mail_transaction_update_want_add(struct mail_index_transaction *t,
 				 const struct mail_transaction_flag_update *u)
@@ -792,17 +802,15 @@
 	return FALSE;
 }
 
-static void
-mail_index_insert_flag_update(struct mail_index_transaction *t,
-			      struct mail_transaction_flag_update u,
-			      uint32_t left_idx, uint32_t right_idx)
+static uint32_t
+mail_index_find_update_insert_pos(struct mail_index_transaction *t,
+				  unsigned int left_idx, unsigned int right_idx,
+				  uint32_t seq)
 {
-	struct mail_transaction_flag_update *updates, tmp_update;
-	unsigned int count;
-	uint32_t idx, move;
+	const struct mail_transaction_flag_update *updates;
+	unsigned int idx, count;
 
-	updates = array_get_modifiable(&t->updates, &count);
-
+	updates = array_get(&t->updates, &count);
 	i_assert(left_idx <= right_idx && right_idx <= count);
 
 	/* find the first update with either overlapping range,
@@ -811,15 +819,28 @@
 	while (left_idx < right_idx) {
 		idx = (left_idx + right_idx) / 2;
 
-		if (updates[idx].uid2 < u.uid1)
+		if (updates[idx].uid2 < seq)
 			left_idx = idx+1;
-		else if (updates[idx].uid1 > u.uid1)
+		else if (updates[idx].uid1 > seq)
 			right_idx = idx;
 		else
 			break;
 	}
-	if (idx < count && updates[idx].uid2 < u.uid1)
+	if (idx < count && updates[idx].uid2 < seq)
 		idx++;
+	return idx;
+}
+
+static void
+mail_index_insert_flag_update(struct mail_index_transaction *t,
+			      struct mail_transaction_flag_update u,
+			      unsigned int idx)
+{
+	struct mail_transaction_flag_update *updates, tmp_update;
+	unsigned int count;
+	uint32_t move;
+
+	updates = array_get_modifiable(&t->updates, &count);
 
 	/* overlapping ranges, split/merge them */
 	i_assert(idx == 0 || updates[idx-1].uid2 < u.uid1);
@@ -930,8 +951,9 @@
 {
 	struct mail_index_record *rec;
 	struct mail_transaction_flag_update u, *last_update;
-	unsigned int first_idx, count;
+	unsigned int idx, first_idx, count;
 
+	update_minmax_flagupdate_seq(t, seq1, seq2);
 	if (seq2 >= t->first_new_seq) {
 		/* updates for appended messages, modify them directly */
 		uint32_t seq;
@@ -1013,7 +1035,9 @@
 			first_idx = 0;
 			count = t->last_update_idx + 1;
 		}
-		mail_index_insert_flag_update(t, u, first_idx, count);
+		idx = mail_index_find_update_insert_pos(t, first_idx, count,
+							u.uid1);
+		mail_index_insert_flag_update(t, u, idx);
 	}
 }
 
@@ -1416,6 +1440,8 @@
 	i_assert(keywords->count > 0 || modify_type == MODIFY_REPLACE);
 	i_assert(keywords->index == t->view->index);
 
+	update_minmax_flagupdate_seq(t, seq, seq);
+
 	if (!array_is_created(&t->keyword_updates) && keywords->count > 0) {
 		uint32_t max_idx = keywords->idx[keywords->count-1];
 
@@ -1486,6 +1512,107 @@
 	t->reset = TRUE;
 }
 
+void mail_index_transaction_set_max_modseq(struct mail_index_transaction *t,
+					   uint64_t max_modseq,
+					   ARRAY_TYPE(seq_range) *seqs)
+{
+	i_assert(array_is_created(seqs));
+
+	t->max_modseq = max_modseq;
+	t->conflict_seqs = seqs;
+}
+
+static bool
+mail_index_update_cancel_array(ARRAY_TYPE(seq_range) *array, uint32_t seq)
+{
+	if (array_is_created(array)) {
+		if (seq_range_array_remove(array, seq)) {
+			if (array_count(array) == 0)
+				array_free(array);
+			return TRUE;
+		}
+	}
+	return FALSE;
+}
+
+static bool
+mail_index_update_cancel(struct mail_index_transaction *t, uint32_t seq)
+{
+	struct mail_index_transaction_keyword_update *kw;
+	struct mail_transaction_flag_update *updates, tmp_update;
+	unsigned int i, count;
+	bool ret, have_kw_changes = FALSE;
+
+	ret = mail_index_update_cancel_array(&t->keyword_resets, seq);
+	if (array_is_created(&t->keyword_updates)) {
+		kw = array_get_modifiable(&t->keyword_updates, &count);
+		for (i = 0; i < count; i++) {
+			if (mail_index_update_cancel_array(&kw[i].add_seq, seq))
+				ret = TRUE;
+			if (mail_index_update_cancel_array(&kw[i].remove_seq,
+							   seq))
+				ret = TRUE;
+			if (array_is_created(&kw[i].add_seq) ||
+			    array_is_created(&kw[i].remove_seq))
+				have_kw_changes = TRUE;
+		}
+		if (!have_kw_changes)
+			array_free(&t->keyword_updates);
+	}
+
+	if (!array_is_created(&t->updates))
+		return ret;
+
+	updates = array_get_modifiable(&t->updates, &count);
+	i = mail_index_find_update_insert_pos(t, 0, count, seq);
+	if (i < count && updates[i].uid1 <= seq && updates[i].uid2 >= seq) {
+		/* exists */
+		ret = TRUE;
+		if (updates[i].uid1 == seq && updates[i].uid2 == seq) {
+			if (count > 1)
+				array_delete(&t->updates, i, 1);
+			else
+				array_free(&t->updates);
+		} else if (updates[i].uid1 == seq)
+			updates[i].uid1++;
+		else if (updates[i].uid2 == seq)
+			updates[i].uid2--;
+		else {
+			/* need to split it in two */
+			tmp_update = updates[i];
+			tmp_update.uid1 = seq+1;
+			updates[i].uid2 = seq-1;
+			array_insert(&t->updates, i + 1, &tmp_update, 1);
+		}
+	}
+	return ret;
+}
+
+void mail_index_transaction_check_conflicts(struct mail_index_transaction *t)
+{
+	uint32_t seq;
+
+	i_assert(t->max_modseq != 0);
+	i_assert(t->conflict_seqs != NULL);
+
+	if (t->max_modseq == mail_index_modseq_get_highest(t->view)) {
+		/* no conflicts possible */
+		return;
+	}
+	if (t->min_flagupdate_seq == 0) {
+		/* no flag updates */
+		return;
+	}
+
+	for (seq = t->min_flagupdate_seq; seq <= t->max_flagupdate_seq; seq++) {
+		if (mail_index_modseq_lookup(t->view, seq) > t->max_modseq) {
+			if (mail_index_update_cancel(t, seq))
+				seq_range_array_add(t->conflict_seqs, 0, seq);
+		}
+	}
+	t->log_updates = mail_index_transaction_has_changes(t);
+}
+
 struct mail_index_transaction_vfuncs trans_vfuncs = {
 	mail_index_transaction_commit_v,
 	mail_index_transaction_rollback_v

--- a/src/lib-index/mail-index.h	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-index/mail-index.h	Sat Jun 21 07:43:54 2008 +0300
@@ -229,6 +229,12 @@
 void mail_index_transaction_rollback(struct mail_index_transaction **t);
 /* Discard all changes in the transaction. */
 void mail_index_transaction_reset(struct mail_index_transaction *t);
+/* When committing transaction, drop flag/keyword updates for messages whose
+   mdoseq is larger than max_modseq. Save those messages' sequences to the
+   given array. */
+void mail_index_transaction_set_max_modseq(struct mail_index_transaction *t,
+					   uint64_t max_modseq,
+					   ARRAY_TYPE(seq_range) *seqs);
 
 /* Returns the view transaction was created for. */
 struct mail_index_view *

--- a/src/lib-index/mail-transaction-log-append.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-index/mail-transaction-log-append.c	Sat Jun 21 07:43:54 2008 +0300
@@ -576,17 +576,22 @@
 			return -1;
 	}
 
-	if (array_is_created(&t->ext_reset_atomic)) {
+	if (array_is_created(&t->ext_reset_atomic) || t->max_modseq != 0) {
 		if (mail_index_map(t->view->index,
 				   MAIL_INDEX_SYNC_HANDLER_HEAD) <= 0)
 			return -1;
+	}
+	if (array_is_created(&t->ext_reset_atomic))
 		transaction_update_atomic_reset_ids(t);
-
-		if (!TRANSACTION_HAS_CHANGES(t)) {
-			/* we aborted the ext changes, nothing else to do */
-			return 0;
-		}
+	if (t->max_modseq != 0)
+		mail_index_transaction_check_conflicts(t);
+	if (!TRANSACTION_HAS_CHANGES(t)) {
+		/* we aborted all changes, nothing else to do */
+		return 0;
 	}
+	/* finally convert all sequences to UIDs before we write them,
+	   but after we've checked and removed conflicts */
+	mail_index_transaction_convert_to_uids(t);
 
 	file = log->head;
 

--- a/src/lib-storage/index/cydir/cydir-storage.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/index/cydir/cydir-storage.c	Sat Jun 21 07:43:54 2008 +0300
@@ -433,6 +433,7 @@
 		index_transaction_begin,
 		index_transaction_commit,
 		index_transaction_rollback,
+		index_transaction_set_max_modseq,
 		index_keywords_create,
 		index_keywords_free,
 		index_storage_get_seq_range,

--- a/src/lib-storage/index/dbox/dbox-storage.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/index/dbox/dbox-storage.c	Sat Jun 21 07:43:54 2008 +0300
@@ -693,6 +693,7 @@
 		index_transaction_begin,
 		index_transaction_commit,
 		index_transaction_rollback,
+		index_transaction_set_max_modseq,
 		index_keywords_create,
 		index_keywords_free,
 		index_storage_get_seq_range,

--- a/src/lib-storage/index/index-storage.h	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/index/index-storage.h	Sat Jun 21 07:43:54 2008 +0300
@@ -176,6 +176,9 @@
 				    uint32_t *log_file_seq_r,
 				    uoff_t *log_file_offset_r);
 void index_transaction_finish_rollback(struct index_transaction_context *t);
+void index_transaction_set_max_modseq(struct mailbox_transaction_context *_t,
+				      uint64_t max_modseq,
+				      ARRAY_TYPE(seq_range) *seqs);
 
 struct mailbox_transaction_context *
 index_transaction_begin(struct mailbox *box,

--- a/src/lib-storage/index/index-transaction.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/index/index-transaction.c	Sat Jun 21 07:43:54 2008 +0300
@@ -116,3 +116,13 @@
 
 	mail_index_transaction_rollback(&itrans);
 }
+
+void index_transaction_set_max_modseq(struct mailbox_transaction_context *_t,
+				      uint64_t max_modseq,
+				      ARRAY_TYPE(seq_range) *seqs)
+{
+	struct index_transaction_context *t =
+		(struct index_transaction_context *)_t;
+
+	mail_index_transaction_set_max_modseq(t->trans, max_modseq, seqs);
+}

--- a/src/lib-storage/index/maildir/maildir-storage.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/index/maildir/maildir-storage.c	Sat Jun 21 07:43:54 2008 +0300
@@ -1037,6 +1037,7 @@
 		index_transaction_begin,
 		index_transaction_commit,
 		index_transaction_rollback,
+		index_transaction_set_max_modseq,
 		index_keywords_create,
 		index_keywords_free,
 		index_storage_get_seq_range,

--- a/src/lib-storage/index/mbox/mbox-storage.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/index/mbox/mbox-storage.c	Sat Jun 21 07:43:54 2008 +0300
@@ -994,6 +994,7 @@
 		index_transaction_begin,
 		index_transaction_commit,
 		index_transaction_rollback,
+		index_transaction_set_max_modseq,
 		index_keywords_create,
 		index_keywords_free,
 		index_storage_get_seq_range,

--- a/src/lib-storage/index/raw/raw-storage.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/index/raw/raw-storage.c	Sat Jun 21 07:43:54 2008 +0300
@@ -289,6 +289,7 @@
 		index_transaction_begin,
 		index_transaction_commit,
 		index_transaction_rollback,
+		index_transaction_set_max_modseq,
 		index_keywords_create,
 		index_keywords_free,
 		index_storage_get_seq_range,

--- a/src/lib-storage/mail-storage-private.h	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/mail-storage-private.h	Sat Jun 21 07:43:54 2008 +0300
@@ -118,6 +118,9 @@
 				  uint32_t *first_saved_uid_r,
 				  uint32_t *last_saved_uid_r);
 	void (*transaction_rollback)(struct mailbox_transaction_context *t);
+	void (*transaction_set_max_modseq)(struct mailbox_transaction_context *t,
+					   uint64_t max_modseq,
+					   ARRAY_TYPE(seq_range) *seqs);
 
 	int (*keywords_create)(struct mailbox *box,
 			       const char *const keywords[],

--- a/src/lib-storage/mail-storage.c	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/mail-storage.c	Sat Jun 21 07:43:54 2008 +0300
@@ -760,6 +760,13 @@
 	return box->transaction_count;
 }
 
+void mailbox_transaction_set_max_modseq(struct mailbox_transaction_context *t,
+					uint64_t max_modseq,
+					ARRAY_TYPE(seq_range) *seqs)
+{
+	t->box->v.transaction_set_max_modseq(t, max_modseq, seqs);
+}
+
 struct mailbox *
 mailbox_transaction_get_mailbox(const struct mailbox_transaction_context *t)
 {

--- a/src/lib-storage/mail-storage.h	Fri Jun 20 10:41:44 2008 +0300
+++ b/src/lib-storage/mail-storage.h	Sat Jun 21 07:43:54 2008 +0300
@@ -360,6 +360,12 @@
 void mailbox_transaction_rollback(struct mailbox_transaction_context **t);
 /* Return the number of active transactions for the mailbox. */
 unsigned int mailbox_transaction_get_count(const struct mailbox *box) ATTR_PURE;
+/* When committing transaction, drop flag/keyword updates for messages whose
+   mdoseq is larger than max_modseq. Save those messages' sequences to the
+   given array. */
+void mailbox_transaction_set_max_modseq(struct mailbox_transaction_context *t,
+					uint64_t max_modseq,
+					ARRAY_TYPE(seq_range) *seqs);
 
 struct mailbox *
 mailbox_transaction_get_mailbox(const struct mailbox_transaction_context *t)