robust find seems to be working

4 files changed, 167 insertions, 36 deletions

diff --git a/ds.h b/ds.h
index dde3496..ffdfec8 100644
--- a/ds.h
+++ b/ds.h
@@ -85,12 +85,17 @@ static unsigned arr_lenu(void *arr) {
 	return (unsigned)arr_len(arr);
 }
 
-// grow array to fit one more member
-static void *arr_grow1_(void *arr, size_t member_size) {
+// grow array to fit `count` more members
+static void *arr_grow_(void *arr, size_t member_size, size_t count) {
 	if (arr) {
 		ArrHeader *hdr = arr_hdr_(arr);
-		if (hdr->len >= hdr->cap) {
-			u32 new_capacity = hdr->cap * 2;
+		if (hdr->len + count > hdr->cap) {
+			if ((u64)hdr->len + (u64)count >= U32_MAX / 2) {
+				// array too large
+				free(hdr);
+				return NULL;
+			}
+			u32 new_capacity = (u32)(hdr->len + count) * 2;
 			ArrHeader *old_hdr = hdr;
 			hdr = (ArrHeader *)realloc(old_hdr, sizeof(ArrHeader) + new_capacity * member_size);
 			if (hdr) {
@@ -103,7 +108,11 @@ static void *arr_grow1_(void *arr, size_t member_size) {
 		return hdr->data;
 	} else {
 		// create a new array
-		u32 initial_capacity = 2; // allocate enough space for two members
+		if (count >= U32_MAX / 2) {
+			// array too large
+			return NULL;
+		}
+		u32 initial_capacity = (u32)(count + 1);
 		ArrHeader *ret = (ArrHeader *)calloc(1, sizeof(ArrHeader) + initial_capacity * member_size);
 		if (ret) {
 			ret->cap = initial_capacity;
@@ -114,6 +123,11 @@ static void *arr_grow1_(void *arr, size_t member_size) {
 	}
 }
 
+// grow array to fit one more member
+static void *arr_grow1_(void *arr, size_t member_size) {
+	return arr_grow_(arr, member_size, 1);
+}
+
 static void *arr_add_ptr_(void **arr, size_t member_size) {
 	u8 *ret;
 	*arr = arr_grow1_(*arr, member_size);
@@ -194,6 +208,36 @@ static void *arr_remove_(void *arr, size_t member_size, size_t index) {
 	}
 }
 
+static void *arr_remove_multiple_(void *arr, size_t member_size, size_t index, size_t count) {
+	ArrHeader *hdr = arr_hdr_(arr);
+	assert(index < hdr->len);
+	memmove((char *)arr + index * member_size,
+		(char *)arr + (index + count) * member_size,
+		(hdr->len - (index + count)) * member_size);
+	hdr->len -= count;
+	if (hdr->len == 0) {
+		free(hdr);
+		return NULL;
+	} else {
+		return arr;
+	}
+}
+
+static void *arr_insert_multiple_(void *arr, size_t member_size, size_t index, size_t count) {
+	if (count == 0) return arr;
+	
+	arr = arr_grow_(arr, member_size, count);
+	if (!arr) return NULL;
+	
+	ArrHeader *hdr = arr_hdr_(arr);
+	memmove((char *)arr + (index + count) * member_size,
+		(char *)arr + index * member_size,
+		arr_len(arr) * member_size);
+	memset((char *)arr + index * member_size, 0, count * member_size);
+	hdr->len += (u32)count;
+	return arr;
+}
+
 static void *arr_copy_(const void *arr, size_t member_size) {
 	void *new_arr = NULL;
 	arr_set_len_(&new_arr, member_size, arr_len(arr));
@@ -225,10 +269,13 @@ static void *arr_copy_(const void *arr, size_t member_size) {
 #define arr_qsort(a, cmp) qsort((a), arr_len(a), sizeof *(a), (cmp))
 #define arr_remove_last(a) do { assert(a); if (--arr_hdr_(a)->len == 0) arr_free(a); } while (0)
 #define arr_remove(a, i) (void)((a) = arr_remove_((a), sizeof *(a), (i)))
+#define arr_remove_multiple(a, i, n) (void)((a) = arr_remove_multiple_((a), sizeof *(a), (i), (n)))
 #define arr_insert(a, i, x) do { u32 _index = (i); (a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)); \
 	if (a) { memmove((a) + _index + 1, (a) + _index, (arr_len(a) - _index) * sizeof *(a));\
 	(a)[_index] = x; \
 	++arr_hdr_(a)->len; } } while (0)
+/// insert `n` zeroed elements at index `i`
+#define arr_insert_multiple(a, i, n) (void)((a) = arr_insert_multiple_((a), sizeof *(a), (i), (n)))
 #define arr_pop_last(a) ((a)[--arr_hdr_(a)->len])
 #define arr_size_in_bytes(a) (arr_len(a) * sizeof *(a))
 #define arr_lastp(a) ((a) ? &(a)[arr_len(a)-1] : NULL)
diff --git a/find.c b/find.c
index 046cef1..43e11cd 100644
--- a/find.c
+++ b/find.c
@@ -25,22 +25,6 @@ TextBuffer *find_search_buffer(Ted *ted) {
 	return ted->prev_active_buffer;
 }
 
-static void find_edit_notify(void *context, TextBuffer *buffer, const EditInfo *info) {
-	(void)context;
-	Ted *ted = buffer->ted;
-	if (!ted->find) {
-		return;
-	}
-	if (buffer != find_search_buffer(ted))
-		return;
-	
-	// TODO: update find result locations
-//	printf("%s %u\n",buffer_get_path(buffer),info->newlines_inserted);
-}
-
-void find_init(Ted *ted) {
-	ted_add_edit_notify(ted, find_edit_notify, NULL);
-}
 
 
 static void ted_error_from_pcre2_error(Ted *ted, int err) {
@@ -146,6 +130,17 @@ static WarnUnusedResult bool find_match(Ted *ted, BufferPos *pos, u32 *match_sta
 	}
 }
 
+static void find_search_line(Ted *ted, u32 line, FindResult **results) {
+	u32 match_start=0, match_end=0;
+	BufferPos pos = {.line = line, .index = 0};
+	while (find_match(ted, &pos, &match_start, &match_end, +1)) {
+		BufferPos match_start_pos = {.line = pos.line, .index = match_start};
+		BufferPos match_end_pos = {.line = pos.line, .index = match_end};
+		FindResult result = {match_start_pos, match_end_pos};
+		arr_add(*results, result);
+	}
+}
+
 // check if the search term needs to be recompiled
 void find_update(Ted *ted, bool force) {
 	TextBuffer *find_buffer = &ted->find_buffer;
@@ -161,22 +156,20 @@ void find_update(Ted *ted, bool force) {
 	find_free_pattern(ted);
 
 	if (find_compile_pattern(ted)) {
-		BufferPos pos = buffer_pos_start_of_file(buffer);
 		BufferPos best_scroll_candidate = {U32_MAX, U32_MAX};
 		BufferPos cursor_pos = buffer->cursor_pos;
 		// find all matches
-		for (u32 nsearches = 0; nsearches < buffer->nlines; ++nsearches) {
-			u32 match_start, match_end;
-			while (find_match(ted, &pos, &match_start, &match_end, +1)) {
-				BufferPos match_start_pos = {.line = pos.line, .index = match_start};
-				BufferPos match_end_pos = {.line = pos.line, .index = match_end};
-				FindResult result = {match_start_pos, match_end_pos};
-				arr_add(ted->find_results, result);
-				if (best_scroll_candidate.line == U32_MAX 
-				|| (buffer_pos_cmp(best_scroll_candidate, cursor_pos) < 0 && buffer_pos_cmp(match_start_pos, cursor_pos) >= 0))
-					best_scroll_candidate = match_start_pos;
-			}
+		arr_clear(ted->find_results);
+		for (u32 line = 0; line < buffer->nlines; ++line) {
+			find_search_line(ted, line, &ted->find_results);
+		}
+		
+		arr_foreach_ptr(ted->find_results, FindResult, res) {
+			if (best_scroll_candidate.line == U32_MAX 
+			|| (buffer_pos_cmp(best_scroll_candidate, cursor_pos) < 0 && buffer_pos_cmp(res->start, cursor_pos) >= 0))
+				best_scroll_candidate = res->start;
 		}
+		
 		find_buffer->modified = false;
 		if (best_scroll_candidate.line != U32_MAX) // scroll to first match (if there is one)
 			buffer_scroll_to_pos(buffer, best_scroll_candidate);
@@ -491,3 +484,93 @@ void find_close(Ted *ted) {
 	ted_switch_to_buffer(ted, find_search_buffer(ted));
 	find_free_pattern(ted);
 }
+
+// index of first result with at least this line number
+static u32 find_first_result_with_line(Ted *ted, u32 line) {
+	u32 lo = 0;
+	u32 hi = arr_len(ted->find_results);
+	if (hi == 0) {
+		return 0;
+	}
+	// all find results come before this line
+	if (ted->find_results[hi - 1].start.line < line)
+		return hi;
+	
+	while (lo + 1 < hi) {
+		u32 mid = (lo + hi) / 2;
+		u32 mid_line = ted->find_results[mid].start.line;
+		if (mid_line >= line && mid > 0 && ted->find_results[mid - 1].start.line < line)
+			return mid;
+		if (line > mid_line) {
+			lo = mid + 1;
+		} else {
+			hi = mid;
+		}
+	}
+	return lo;
+}
+
+// update search results for the given range of lines
+static void find_research_lines(Ted *ted, u32 line0, u32 line1) {
+	FindResult *new_results = NULL;
+	for (u32 l = line0; l <= line1; ++l) {
+		find_search_line(ted, l, &new_results);
+	}
+	u32 i0 = find_first_result_with_line(ted, line0);
+	u32 i1 = find_first_result_with_line(ted, line1 + 1);
+	i32 diff = (i32)arr_len(new_results) - (i32)(i1 - i0);
+	if (diff < 0) {
+		arr_remove_multiple(ted->find_results, i0, (u32)-diff);
+	} else if (diff > 0) {
+		arr_insert_multiple(ted->find_results, i0, (u32)diff);
+	}
+	memcpy(&ted->find_results[i0], new_results, arr_len(new_results) * sizeof *new_results);
+}
+		
+static void find_edit_notify(void *context, TextBuffer *buffer, const EditInfo *info) {
+	(void)context;
+	Ted *ted = buffer->ted;
+	if (!ted->find) {
+		return;
+	}
+	if (buffer != find_search_buffer(ted))
+		return;
+	
+	const u32 line = info->pos.line;
+	
+	if (info->chars_inserted) {
+		const u32 newlines_inserted = info->newlines_inserted;
+		
+		if (newlines_inserted) {
+			// update line numbers for find results after insertion.
+			arr_foreach_ptr(ted->find_results, FindResult, res) {
+				if (res->start.line > line) {
+					res->start.line += newlines_inserted;
+					res->end.line += newlines_inserted;
+				}
+			}
+		}
+		
+		find_research_lines(ted, line, line + newlines_inserted);
+		
+	} else if (info->chars_deleted) {
+		const u32 newlines_deleted = info->newlines_deleted;
+		
+		if (newlines_deleted) {
+			// update line numbers for find results after deletion.
+			arr_foreach_ptr(ted->find_results, FindResult, res) {
+				if (res->start.line >= line + newlines_deleted) {
+					res->start.line -= newlines_deleted;
+					res->end.line -= newlines_deleted;
+				}
+			}
+			
+		}
+		
+		find_research_lines(ted, line, line);
+	}
+}
+
+void find_init(Ted *ted) {
+	ted_add_edit_notify(ted, find_edit_notify, NULL);
+}
diff --git a/main.c b/main.c
index 3dd4fe5..40dc1c8 100644
--- a/main.c
+++ b/main.c
@@ -1,7 +1,4 @@
 /*
-TODO:
-- robust find (results shouldn't move around when you type things)
-
 FUTURE FEATURES:
 - autodetect indentation (tabs vs spaces)
 - config variables
diff --git a/ted.h b/ted.h
index 66e8c04..0551eb2 100644
--- a/ted.h
+++ b/ted.h
@@ -288,8 +288,12 @@ typedef struct {
 	/// position where the edit took place
 	BufferPos pos;
 	/// number of characters (unicode codepoints, including newlines) deleted
+	///
+	/// if this is non-zero, \ref chars_inserted will be zero.
 	u32 chars_deleted;
 	/// number of characters (unicode codepoints, including newlines) inserted
+	///
+	/// if this is non-zero, \ref chars_deleted will be zero.
 	u32 chars_inserted;
 	/// number of newlines deleted
 	u32 newlines_deleted;