From bdbce6fe3c647616d22867bbc82e011c91231dd3 Mon Sep 17 00:00:00 2001 From: pommicket Date: Mon, 7 Aug 2023 06:50:42 -0400 Subject: robust find seems to be working --- ds.h | 57 ++++++++++++++++++++++++--- find.c | 139 ++++++++++++++++++++++++++++++++++++++++++++++++++++------------- main.c | 3 -- ted.h | 4 ++ 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; -- cgit v1.2.3