# HG changeset patch
# User Timo Sirainen <timo.sirainen@dovecot.fi>
# Date 1481212246 -7200
# Node ID ff92e16346c9890b3c20f1770ad64f5f057e9354
# Parent  1be2f1e78975392f52ff4dac95d6add525261fff
lib: Fix seq_range_array_invert() when input contains 2^32-1

This caused next_min_seq to be wrapped to 0, which was handled wrong later
on.

Fixes:
Panic: file mail-index-map.c: line 549 (mail_index_map_lookup_seq_range): assertion failed: (first_uid > 0)

diff -r 1be2f1e78975 -r ff92e16346c9 src/lib/seq-range-array.c
--- a/src/lib/seq-range-array.c	Wed Dec 07 00:14:08 2016 +0200
+++ b/src/lib/seq-range-array.c	Thu Dec 08 17:50:46 2016 +0200
@@ -427,7 +427,7 @@
 {
 	struct seq_range *range, value;
 	unsigned int i, count;
-	uint32_t next_min_seq;
+	uint32_t prev_min_seq;
 
 	if (array_is_created(array))
 		range = array_get_modifiable(array, &count);
@@ -454,16 +454,25 @@
 	}
 
 	for (i = 0; i < count; ) {
-		next_min_seq = range[i].seq2 + 1;
-		if (range[i].seq1 == min_seq) {
+		prev_min_seq = min_seq;
+		min_seq = range[i].seq2;
+		if (range[i].seq1 == prev_min_seq) {
 			array_delete(array, i, 1);
 			range = array_get_modifiable(array, &count);
 		} else {
 			range[i].seq2 = range[i].seq1 - 1;
-			range[i].seq1 = min_seq;
+			range[i].seq1 = prev_min_seq;
 			i++;
 		}
-		min_seq = next_min_seq;
+		if (min_seq >= max_seq) {
+			/* max_seq is reached. the rest of the array should be
+			   empty. we'll return here, because min_seq++ may
+			   wrap to 0. */
+			i_assert(min_seq == max_seq);
+			i_assert(i == count);
+			return;
+		}
+		min_seq++;
 	}
 	if (min_seq <= max_seq) {
 		value.seq1 = min_seq;
diff -r 1be2f1e78975 -r ff92e16346c9 src/lib/test-seq-range-array.c
--- a/src/lib/test-seq-range-array.c	Wed Dec 07 00:14:08 2016 +0200
+++ b/src/lib/test-seq-range-array.c	Thu Dec 08 17:50:46 2016 +0200
@@ -170,6 +170,7 @@
 	static const unsigned int input[] = {
 		1, 2, 3, 4, 5, UINT_MAX,
 		2, 3, 4, UINT_MAX,
+		3, 4, 5, UINT_MAX,
 		1, 2, 4, 5, UINT_MAX,
 		1, 3, 5, UINT_MAX,
 		1, UINT_MAX,
@@ -207,6 +208,57 @@
 	}
 }
 
+static void test_seq_range_array_invert_edges(void)
+{
+	const struct {
+		int64_t a_seq1, a_seq2, b_seq1, b_seq2;
+		int64_t resa_seq1, resa_seq2, resb_seq1, resb_seq2;
+	} tests[] = {
+		{ -1, -1, -1, -1,
+		  0, 0xffffffff, -1, -1 },
+		{ 0, 0xffffffff, -1, -1,
+		  -1, -1, -1, -1 },
+		{ 0, 0xfffffffe, -1, -1,
+		  0xffffffff, 0xffffffff, -1, -1 },
+		{ 1, 0xfffffffe, -1, -1,
+		  0, 0, 0xffffffff, 0xffffffff },
+		{ 1, 0xffffffff, -1, -1,
+		  0, 0, -1, -1 },
+		{ 0, 0, 0xffffffff, 0xffffffff,
+		  1, 0xfffffffe, -1, -1 },
+		{ 0xffffffff, 0xffffffff, -1, -1,
+		  0, 0xfffffffe, -1, -1 },
+	};
+	ARRAY_TYPE(seq_range) range = ARRAY_INIT;
+	const struct seq_range *result;
+	unsigned int count;
+
+	test_begin("seq_range_array_invert() edges");
+	for (unsigned int i = 0; i < N_ELEMENTS(tests); i++) T_BEGIN {
+		t_array_init(&range, 10);
+		if (tests[i].a_seq1 != -1)
+			seq_range_array_add_range(&range, tests[i].a_seq1, tests[i].a_seq2);
+		if (tests[i].b_seq1 != -1)
+			seq_range_array_add_range(&range, tests[i].b_seq1, tests[i].b_seq2);
+		seq_range_array_invert(&range, 0, 0xffffffff);
+
+		result = array_get(&range, &count);
+		if (tests[i].resa_seq1 == -1)
+			test_assert_idx(count == 0, i);
+		else {
+			test_assert(result[0].seq1 == tests[i].resa_seq1);
+			test_assert(result[0].seq2 == tests[i].resa_seq2);
+			if (tests[i].resb_seq1 == -1)
+				test_assert_idx(count == 1, i);
+			else {
+				test_assert(result[1].seq1 == tests[i].resb_seq1);
+				test_assert(result[1].seq2 == tests[i].resb_seq2);
+			}
+		}
+	} T_END;
+	test_end();
+}
+
 static void test_seq_range_create(ARRAY_TYPE(seq_range) *array, uint8_t byte)
 {
 	unsigned int i;
@@ -245,6 +297,7 @@
 	test_seq_range_array_add_merge();
 	test_seq_range_array_remove_nth();
 	test_seq_range_array_invert();
+	test_seq_range_array_invert_edges();
 	test_seq_range_array_have_common();
 	test_seq_range_array_random();
 }