From 6bb4da5fab94d2ed3d093b996674fd1cc28eda2f Mon Sep 17 00:00:00 2001 From: pommicket Date: Thu, 22 Dec 2022 16:27:06 -0500 Subject: document IDs instead of documents --- arr.c | 263 ----------------------------------------- autocomplete.c | 2 +- buffer.c | 2 +- ds.c | 333 ++++++++++++++++++++++++++++++++++++++++++++++++++++ lsp-write-request.c | 15 ++- lsp.c | 29 +++-- lsp.h | 16 ++- main.c | 5 +- util.c | 156 ++++++++++++++++-------- 9 files changed, 481 insertions(+), 340 deletions(-) delete mode 100644 arr.c create mode 100644 ds.c diff --git a/arr.c b/arr.c deleted file mode 100644 index 402420f..0000000 --- a/arr.c +++ /dev/null @@ -1,263 +0,0 @@ -#ifndef ARR_C_ -#define ARR_C_ - -// functions in this file suffixed with _ are not meant to be used outside here, unless you -// know what you're doing - -// IMPORTANT NOTE: If you are using this with structures containing `long double`s, do -// #define ARR_LONG_DOUBLE -// before including this file -// ( otherwise the long doubles will not be aligned. -// this does mean that arrays waste 8 bytes of memory. -// which isnt important unless you're making a lot of arrays.) - -#include -typedef union { - long num; - void *ptr; - void (*fnptr)(void); -#ifdef ARR_LONG_DOUBLE - long -#endif - double flt; -} ArrMaxAlign; -#if __STDC_VERSION__ < 199901L && !defined inline -#define inline -#endif - - -typedef struct { - u32 len; - u32 cap; - ArrMaxAlign data[]; -} ArrHeader; - -// watch out! do not call this function if arr is NULL. -static inline ArrHeader *arr_hdr_(void *arr) { - return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data)); -} - -static inline u32 arr_len(const void *arr) { - return arr ? arr_hdr_((void*)arr)->len : 0; -} - -static inline u32 arr_cap(void *arr) { - return arr ? arr_hdr_(arr)->cap : 0; -} - -static inline 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) { - if (arr) { - ArrHeader *hdr = arr_hdr_(arr); - if (hdr->len >= hdr->cap) { - u32 new_capacity = hdr->cap * 2; - ArrHeader *old_hdr = hdr; - hdr = (ArrHeader *)realloc(old_hdr, sizeof(ArrHeader) + new_capacity * member_size); - if (hdr) { - hdr->cap = new_capacity; - } else { - free(old_hdr); - return NULL; - } - } - return hdr->data; - } else { - // create a new array - u32 initial_capacity = 2; // allocate enough space for two members - ArrHeader *ret = (ArrHeader *)calloc(1, sizeof(ArrHeader) + initial_capacity * member_size); - if (ret) { - ret->cap = initial_capacity; - return ret->data; - } else { - return NULL; - } - } -} - -static inline void *arr_add_ptr_(void **arr, size_t member_size) { - u8 *ret; - *arr = arr_grow1_(*arr, member_size); - if (*arr) { - ret = (u8 *)*arr + member_size * (arr_hdr_(*arr)->len++); - memset(ret, 0, member_size); - } else { - ret = NULL; - } - return ret; -} - -static void arr_reserve_(void **arr, size_t member_size, size_t n) { - if (n >= U32_MAX-1) { - // too big; free arr. - if (*arr) free(arr_hdr_(*arr)); - *arr = NULL; - } - - if (!*arr) { - // create a new array with capacity n+1 - // why n+1? i dont know i wrote this a while ago - ArrHeader *hdr = calloc(1, sizeof(ArrHeader) + (n+1) * member_size); - if (hdr) { - hdr->cap = (u32)n+1; - *arr = hdr->data; - } - } else { - // increase capacity of array - ArrHeader *hdr = arr_hdr_(*arr); - u32 curr_cap = hdr->cap; - if (n > curr_cap) { - ArrHeader *old_hdr = hdr; - while (n > curr_cap) { - if (curr_cap < U32_MAX/2) - curr_cap *= 2; - else - curr_cap = U32_MAX; - } - hdr = realloc(hdr, sizeof(ArrHeader) + curr_cap * member_size); - if (hdr) { - hdr->cap = curr_cap; - } else { - // growing failed - free(old_hdr); - *arr = NULL; - return; - } - } - *arr = hdr->data; - } -} - -static void arr_set_len_(void **arr, size_t member_size, size_t n) { - arr_reserve_(arr, member_size, n); - if (*arr) { - ArrHeader *hdr = arr_hdr_(*arr); - if (n > hdr->len) { - // zero new elements - memset((char *)hdr->data + hdr->len * member_size, 0, (n - hdr->len) * member_size); - } - hdr->len = (u32)n; - } -} - -static void *arr_remove_(void *arr, size_t member_size, size_t index) { - ArrHeader *hdr = arr_hdr_(arr); - assert(index < hdr->len); - memmove((char *)arr + index * member_size, (char *)arr + (index+1) * member_size, (hdr->len - (index+1)) * member_size); - if (--hdr->len == 0) { - free(hdr); - return NULL; - } else { - return arr; - } -} - -#ifdef __cplusplus -#define arr_cast_typeof(a) (decltype(a)) -#elif defined __GNUC__ -#define arr_cast_typeof(a) (__typeof__(a)) -#else -#define arr_cast_typeof(a) -#endif - -#define arr__join2(a,b) a##b -#define arr__join(a,b) arr__join2(a,b) // macro used internally - -// if the array is not NULL, free it and set it to NULL -#define arr_free(a) do { if (a) { free(arr_hdr_(a)); (a) = NULL; } } while (0) -// a nice alias -#define arr_clear(a) arr_free(a) -// add an item to the array - if allocation fails, the array will be freed and set to NULL. -// (how this works: if we can successfully grow the array, increase the length and add the item.) -#define arr_add(a, x) do { if (((a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)))) ((a)[arr_hdr_(a)->len++] = (x)); } while (0) -// like arr_add, but instead of passing it the value, it returns a pointer to the value. returns NULL if allocation failed. -// the added item will be zero-initialized. -#define arr_addp(a) arr_cast_typeof(a) arr_add_ptr_((void **)&(a), sizeof *(a)) -// set the length of `a` to `n`, increasing the capacity if necessary. -// the newly-added elements are zero-initialized. -#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_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) -#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) -#define arr_foreach_ptr_end(a, type, var, end) type *end = (a) + arr_len(a); \ - for (type *var = (a); var != end; ++var) -// Iterate through each element of the array, setting var to a pointer to the element. -// You can't use this like, e.g.: -// if (something) -// arr_foreach_ptr(a, int, i); -// You'll get an error. You will need to use braces because it expands to multiple statements. -// (we need to name the end pointer something unique, which is why there's that arr__join thing -// we can't just declare it inside the for loop, because type could be something like char *.) -#define arr_foreach_ptr(a, type, var) arr_foreach_ptr_end(a, type, var, arr__join(_foreach_end,__LINE__)) - -#define arr_reverse(a, type) do { \ - u64 _i, _len = arr_len(a); \ - for (_i = 0; 2*_i < _len; ++_i) { \ - type *_x = &(a)[_i]; \ - type *_y = &(a)[_len-1-_i]; \ - type _tmp; \ - _tmp = *_x; \ - *_x = *_y; \ - *_y = _tmp; \ - } \ - } while (0) - -// Ensure that enough space is allocated for n elements. -#define arr_reserve(a, n) arr_reserve_((void **)&(a), sizeof *(a), (n)) -// Similar to arr_reserve, but also sets the length of the array to n. -#define arr_set_len(a, n) arr_set_len_((void **)&(a), sizeof *(a), (n)) - -#if 0 -static void arrcstr_append_strn_(char **a, char const *s, size_t s_len) { - size_t curr_len = arr_len(*a); - size_t new_len = curr_len + s_len; - arr_reserve(*a, new_len + 1); - arr_set_len(*a, new_len); - memcpy(*a + curr_len, s, s_len); - (*a)[curr_len + s_len] = '\0'; -} - -static void arrcstr_shrink_(char **a, u32 new_len) { - ArrHeader *hdr = arr_hdr_(*a); - assert(hdr->cap > new_len); - hdr->len = new_len; - (*a)[new_len] = '\0'; -} - -// append to a C-string array -#define arrcstr_append_str(a, s) arrcstr_append_strn_(&(a), (s), strlen(s)) -// take at most n bytes from s -#define arrcstr_append_strn(a, s, n) arrcstr_append_strn_(&(a), (s), (n)) -// make the string smaller -#define arrcstr_shrink(a, n) arrcstr_shrink_(&(a), (n)) -#endif - -#ifndef NDEBUG -static void arr_test(void) { - u32 *arr = NULL; - u32 i; - assert(arr_len(arr) == 0); - for (i = 0; i < 10000; ++i) { - arr_add(arr, i*i); - } - assert(arr_len(arr) == 10000); - arr_remove_last(arr); - assert(arr_len(arr) == 9999); - for (i = 0; i < arr_len(arr); ++i) - assert(arr[i] == i*i); - while (arr_len(arr)) - arr_remove_last(arr); - assert(arr_len(arr) == 0); -} -#endif - -#endif // ARR_C_ diff --git a/autocomplete.c b/autocomplete.c index 9aa945d..2d1574e 100644 --- a/autocomplete.c +++ b/autocomplete.c @@ -91,7 +91,7 @@ static void autocomplete_find_completions(Ted *ted) { }; request.data.completion = (LSPRequestCompletion) { .position = { - .document = str_dup(buffer->filename), + .document = lsp_document_id(lsp, buffer->filename), .pos = buffer_pos_to_lsp(buffer, pos) } }; diff --git a/buffer.c b/buffer.c index 008de6b..183341f 100644 --- a/buffer.c +++ b/buffer.c @@ -2186,7 +2186,7 @@ Status buffer_load_file(TextBuffer *buffer, char const *filename) { LSPRequest request = {.type = LSP_REQUEST_DID_OPEN}; LSPRequestDidOpen *open = &request.data.open; open->file_contents = (char *)file_contents; - open->document = str_dup(filename); + open->document = lsp_document_id(lsp, filename); open->language = buffer_language(buffer); lsp_send_request(lsp, &request); file_contents = NULL; // don't free diff --git a/ds.c b/ds.c new file mode 100644 index 0000000..ef4a1b4 --- /dev/null +++ b/ds.c @@ -0,0 +1,333 @@ +/* VARIOUS DATA STRUCTURES +- dynamic array +- string builder +- string hash table +*/ + + +// functions in this file suffixed with _ are not meant to be used outside here, unless you +// know what you're doing + +// IMPORTANT NOTE: If you are using this with structures containing `long double`s, do +// #define ARR_LONG_DOUBLE +// before including this file +// ( otherwise the long doubles will not be aligned. +// this does mean that arrays waste 8 bytes of memory. +// which isnt important unless you're making a lot of arrays.) + +#include +typedef union { + long num; + void *ptr; + void (*fnptr)(void); +#ifdef ARR_LONG_DOUBLE + long +#endif + double flt; +} ArrMaxAlign; +#if __STDC_VERSION__ < 199901L && !defined inline +#define inline +#endif + + +typedef struct { + u32 len; + u32 cap; + ArrMaxAlign data[]; +} ArrHeader; + +// watch out! do not call this function if arr is NULL. +static inline ArrHeader *arr_hdr_(void *arr) { + return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data)); +} + +static inline u32 arr_len(const void *arr) { + return arr ? arr_hdr_((void*)arr)->len : 0; +} + +static inline u32 arr_cap(void *arr) { + return arr ? arr_hdr_(arr)->cap : 0; +} + +static inline 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) { + if (arr) { + ArrHeader *hdr = arr_hdr_(arr); + if (hdr->len >= hdr->cap) { + u32 new_capacity = hdr->cap * 2; + ArrHeader *old_hdr = hdr; + hdr = (ArrHeader *)realloc(old_hdr, sizeof(ArrHeader) + new_capacity * member_size); + if (hdr) { + hdr->cap = new_capacity; + } else { + free(old_hdr); + return NULL; + } + } + return hdr->data; + } else { + // create a new array + u32 initial_capacity = 2; // allocate enough space for two members + ArrHeader *ret = (ArrHeader *)calloc(1, sizeof(ArrHeader) + initial_capacity * member_size); + if (ret) { + ret->cap = initial_capacity; + return ret->data; + } else { + return NULL; + } + } +} + +static inline void *arr_add_ptr_(void **arr, size_t member_size) { + u8 *ret; + *arr = arr_grow1_(*arr, member_size); + if (*arr) { + ret = (u8 *)*arr + member_size * (arr_hdr_(*arr)->len++); + memset(ret, 0, member_size); + } else { + ret = NULL; + } + return ret; +} + +static void arr_reserve_(void **arr, size_t member_size, size_t n) { + if (n >= U32_MAX-1) { + // too big; free arr. + if (*arr) free(arr_hdr_(*arr)); + *arr = NULL; + } + + if (!*arr) { + // create a new array with capacity n+1 + // why n+1? i dont know i wrote this a while ago + ArrHeader *hdr = calloc(1, sizeof(ArrHeader) + (n+1) * member_size); + if (hdr) { + hdr->cap = (u32)n+1; + *arr = hdr->data; + } + } else { + // increase capacity of array + ArrHeader *hdr = arr_hdr_(*arr); + u32 curr_cap = hdr->cap; + if (n > curr_cap) { + ArrHeader *old_hdr = hdr; + while (n > curr_cap) { + if (curr_cap < U32_MAX/2) + curr_cap *= 2; + else + curr_cap = U32_MAX; + } + hdr = realloc(hdr, sizeof(ArrHeader) + curr_cap * member_size); + if (hdr) { + hdr->cap = curr_cap; + } else { + // growing failed + free(old_hdr); + *arr = NULL; + return; + } + } + *arr = hdr->data; + } +} + +static void arr_set_len_(void **arr, size_t member_size, size_t n) { + arr_reserve_(arr, member_size, n); + if (*arr) { + ArrHeader *hdr = arr_hdr_(*arr); + if (n > hdr->len) { + // zero new elements + memset((char *)hdr->data + hdr->len * member_size, 0, (n - hdr->len) * member_size); + } + hdr->len = (u32)n; + } +} + +static void *arr_remove_(void *arr, size_t member_size, size_t index) { + ArrHeader *hdr = arr_hdr_(arr); + assert(index < hdr->len); + memmove((char *)arr + index * member_size, (char *)arr + (index+1) * member_size, (hdr->len - (index+1)) * member_size); + if (--hdr->len == 0) { + free(hdr); + return NULL; + } else { + return arr; + } +} + +#ifdef __cplusplus +#define arr_cast_typeof(a) (decltype(a)) +#elif defined __GNUC__ +#define arr_cast_typeof(a) (__typeof__(a)) +#else +#define arr_cast_typeof(a) +#endif + +#define arr__join2(a,b) a##b +#define arr__join(a,b) arr__join2(a,b) // macro used internally + +// if the array is not NULL, free it and set it to NULL +#define arr_free(a) do { if (a) { free(arr_hdr_(a)); (a) = NULL; } } while (0) +// a nice alias +#define arr_clear(a) arr_free(a) +// add an item to the array - if allocation fails, the array will be freed and set to NULL. +// (how this works: if we can successfully grow the array, increase the length and add the item.) +#define arr_add(a, x) do { if (((a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)))) ((a)[arr_hdr_(a)->len++] = (x)); } while (0) +// like arr_add, but instead of passing it the value, it returns a pointer to the value. returns NULL if allocation failed. +// the added item will be zero-initialized. +#define arr_addp(a) arr_cast_typeof(a) arr_add_ptr_((void **)&(a), sizeof *(a)) +// set the length of `a` to `n`, increasing the capacity if necessary. +// the newly-added elements are zero-initialized. +#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_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) +#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) +#define arr_foreach_ptr_end(a, type, var, end) type *end = (a) + arr_len(a); \ + for (type *var = (a); var != end; ++var) +// Iterate through each element of the array, setting var to a pointer to the element. +// You can't use this like, e.g.: +// if (something) +// arr_foreach_ptr(a, int, i); +// You'll get an error. You will need to use braces because it expands to multiple statements. +// (we need to name the end pointer something unique, which is why there's that arr__join thing +// we can't just declare it inside the for loop, because type could be something like char *.) +#define arr_foreach_ptr(a, type, var) arr_foreach_ptr_end(a, type, var, arr__join(_foreach_end,__LINE__)) + +#define arr_reverse(a, type) do { \ + u64 _i, _len = arr_len(a); \ + for (_i = 0; 2*_i < _len; ++_i) { \ + type *_x = &(a)[_i]; \ + type *_y = &(a)[_len-1-_i]; \ + type _tmp; \ + _tmp = *_x; \ + *_x = *_y; \ + *_y = _tmp; \ + } \ + } while (0) + +// Ensure that enough space is allocated for n elements. +#define arr_reserve(a, n) arr_reserve_((void **)&(a), sizeof *(a), (n)) +// Similar to arr_reserve, but also sets the length of the array to n. +#define arr_set_len(a, n) arr_set_len_((void **)&(a), sizeof *(a), (n)) + +#if 0 +static void arrcstr_append_strn_(char **a, char const *s, size_t s_len) { + size_t curr_len = arr_len(*a); + size_t new_len = curr_len + s_len; + arr_reserve(*a, new_len + 1); + arr_set_len(*a, new_len); + memcpy(*a + curr_len, s, s_len); + (*a)[curr_len + s_len] = '\0'; +} + +static void arrcstr_shrink_(char **a, u32 new_len) { + ArrHeader *hdr = arr_hdr_(*a); + assert(hdr->cap > new_len); + hdr->len = new_len; + (*a)[new_len] = '\0'; +} + +// append to a C-string array +#define arrcstr_append_str(a, s) arrcstr_append_strn_(&(a), (s), strlen(s)) +// take at most n bytes from s +#define arrcstr_append_strn(a, s, n) arrcstr_append_strn_(&(a), (s), (n)) +// make the string smaller +#define arrcstr_shrink(a, n) arrcstr_shrink_(&(a), (n)) +#endif + +#ifndef NDEBUG +static void arr_test(void) { + u32 *arr = NULL; + u32 i; + assert(arr_len(arr) == 0); + for (i = 0; i < 10000; ++i) { + arr_add(arr, i*i); + } + assert(arr_len(arr) == 10000); + arr_remove_last(arr); + assert(arr_len(arr) == 9999); + for (i = 0; i < arr_len(arr); ++i) + assert(arr[i] == i*i); + while (arr_len(arr)) + arr_remove_last(arr); + assert(arr_len(arr) == 0); +} +#endif + +typedef struct { + // dynamic array, including a null byte. + char *str; +} StrBuilder; + +void str_builder_create(StrBuilder *builder) { + memset(builder, 0, sizeof *builder); + arr_add(builder->str, 0); +} + +StrBuilder str_builder_new(void) { + StrBuilder ret = {0}; + str_builder_create(&ret); + return ret; +} + +void str_builder_free(StrBuilder *builder) { + arr_free(builder->str); +} + +void str_builder_clear(StrBuilder *builder) { + str_builder_free(builder); + str_builder_create(builder); +} + +void str_builder_append(StrBuilder *builder, const char *s) { + assert(builder->str); + + size_t s_len = strlen(s); + size_t prev_size = arr_len(builder->str); + size_t prev_len = prev_size - 1; // null terminator + // note: this zeroes the newly created elements, so we have a new null terminator + arr_set_len(builder->str, prev_size + s_len); + // -1 for null terminator + memcpy(builder->str + prev_len, s, s_len); +} + +void str_builder_appendf(StrBuilder *builder, PRINTF_FORMAT_STRING const char *fmt, ...) ATTRIBUTE_PRINTF(2, 3); +void str_builder_appendf(StrBuilder *builder, const char *fmt, ...) { + // idk if you can always just pass NULL to vsnprintf + va_list args; + char fakebuf[2] = {0}; + va_start(args, fmt); + int ret = vsnprintf(fakebuf, 1, fmt, args); + va_end(args); + + if (ret < 0) return; // bad format or something + u32 n = (u32)ret; + + size_t prev_size = arr_len(builder->str); + size_t prev_len = prev_size - 1; // null terminator + arr_set_len(builder->str, prev_size + n); + va_start(args, fmt); + vsnprintf(builder->str + prev_len, n + 1, fmt, args); + va_end(args); +} + +// append n null bytes. +void str_builder_append_null(StrBuilder *builder, size_t n) { + arr_set_len(builder->str, arr_len(builder->str) + n); +} + +u32 str_builder_len(StrBuilder *builder) { + assert(builder->str); + return arr_len(builder->str) - 1; +} + diff --git a/lsp-write-request.c b/lsp-write-request.c index de314aa..e5d671d 100644 --- a/lsp-write-request.c +++ b/lsp-write-request.c @@ -33,12 +33,14 @@ static const char *lsp_language_id(Language lang) { typedef struct { + LSP *lsp; StrBuilder builder; bool is_first; } JSONWriter; -static JSONWriter json_writer_new(void) { +static JSONWriter json_writer_new(LSP *lsp) { return (JSONWriter){ + .lsp = lsp, .builder = str_builder_new(), .is_first = true }; @@ -118,15 +120,16 @@ static void write_key_string(JSONWriter *o, const char *key, const char *s) { write_string(o, s); } -static void write_file_uri(JSONWriter *o, const char *path) { - char *escaped_path = json_escape(path); +static void write_file_uri(JSONWriter *o, DocumentID document) { + // @OPTIM : could store escaped document paths instead of document paths + char *escaped_path = json_escape(o->lsp->document_paths[document]); str_builder_appendf(&o->builder, "\"file:///%s\"", escaped_path); free(escaped_path); } -static void write_key_file_uri(JSONWriter *o, const char *key, const char *path) { +static void write_key_file_uri(JSONWriter *o, const char *key, DocumentID document) { write_key(o, key); - write_file_uri(o, path); + write_file_uri(o, document); } static void write_position(JSONWriter *o, LSPPosition position) { @@ -199,7 +202,7 @@ static bool request_type_is_notification(LSPRequestType type) { } static void write_request(LSP *lsp, LSPRequest *request) { - JSONWriter writer = json_writer_new(); + JSONWriter writer = json_writer_new(lsp); JSONWriter *o = &writer; u32 max_header_size = 64; diff --git a/lsp.c b/lsp.c index d7f0574..8913e87 100644 --- a/lsp.c +++ b/lsp.c @@ -20,10 +20,6 @@ bool lsp_get_error(LSP *lsp, char *error, size_t error_size, bool clear) { } while (0) -static void lsp_document_position_free(LSPDocumentPosition *position) { - free(position->document); -} - static void lsp_document_change_event_free(LSPDocumentChangeEvent *event) { free(event->text); } @@ -35,14 +31,10 @@ static void lsp_request_free(LSPRequest *r) { case LSP_REQUEST_INITIALIZED: case LSP_REQUEST_SHUTDOWN: case LSP_REQUEST_EXIT: + case LSP_REQUEST_COMPLETION: break; - case LSP_REQUEST_COMPLETION: { - LSPRequestCompletion *completion = &r->data.completion; - lsp_document_position_free(&completion->position); - } break; case LSP_REQUEST_DID_OPEN: { LSPRequestDidOpen *open = &r->data.open; - free(open->document); free(open->file_contents); } break; case LSP_REQUEST_SHOW_MESSAGE: @@ -53,7 +45,6 @@ static void lsp_request_free(LSPRequest *r) { LSPRequestDidChange *c = &r->data.change; arr_foreach_ptr(c->changes, LSPDocumentChangeEvent, event) lsp_document_change_event_free(event); - free(c->document); arr_free(c->changes); } break; } @@ -586,6 +577,17 @@ static int lsp_communication_thread(void *data) { return 0; } +u32 lsp_document_id(LSP *lsp, const char *path) { + u32 *value = str_hash_table_get(&lsp->document_ids, path); + if (!value) { + u32 id = arr_len(lsp->document_paths); + value = str_hash_table_insert(&lsp->document_ids, path); + *value = id; + arr_add(lsp->document_paths, str_dup(path)); + } + return *value; +} + bool lsp_create(LSP *lsp, const char *analyzer_command) { ProcessSettings settings = { .stdin_blocking = true, @@ -601,6 +603,7 @@ bool lsp_create(LSP *lsp, const char *analyzer_command) { // this is a small request, so it shouldn't be a problem. write_request(lsp, &initialize); + str_hash_table_create(&lsp->document_ids, sizeof(u32)); lsp->quit_sem = SDL_CreateSemaphore(0); lsp->messages_mutex = SDL_CreateMutex(); lsp->requests_mutex = SDL_CreateMutex(); @@ -628,6 +631,10 @@ void lsp_free(LSP *lsp) { SDL_DestroySemaphore(lsp->quit_sem); process_kill(&lsp->process); arr_free(lsp->received_data); + str_hash_table_clear(&lsp->document_ids); + for (size_t i = 0; i < arr_len(lsp->document_paths); ++i) + free(lsp->document_paths[i]); + arr_clear(lsp->document_paths); arr_foreach_ptr(lsp->messages, LSPMessage, message) { lsp_message_free(message); } @@ -638,7 +645,7 @@ void lsp_document_changed(LSP *lsp, const char *document, LSPDocumentChangeEvent // @TODO(optimization, eventually): batch changes (using the contentChanges array) LSPRequest request = {.type = LSP_REQUEST_DID_CHANGE}; LSPRequestDidChange *c = &request.data.change; - c->document = str_dup(document); + c->document = lsp_document_id(lsp, document); arr_add(c->changes, change); lsp_send_request(lsp, &request); } diff --git a/lsp.h b/lsp.h index 6245623..09cb0b0 100644 --- a/lsp.h +++ b/lsp.h @@ -7,6 +7,8 @@ // (if the server never sends a response) // - TESTING: make rust-analyzer-slow (waits 10s before sending response) +typedef u32 DocumentID; + typedef enum { LSP_REQUEST, LSP_RESPONSE @@ -45,10 +47,8 @@ typedef enum { } LSPRequestType; typedef struct { - // buffer language Language language; - // freed by lsp_request_free - char *document; + DocumentID document; // freed by lsp_request_free char *file_contents; } LSPRequestDidOpen; @@ -61,7 +61,7 @@ typedef struct { } LSPDocumentChangeEvent; typedef struct { - char *document; + DocumentID document; LSPDocumentChangeEvent *changes; // dynamic array } LSPRequestDidChange; @@ -79,8 +79,7 @@ typedef struct { } LSPRequestMessage; typedef struct { - // freed by lsp_request_free - char *document; + DocumentID document; LSPPosition pos; } LSPDocumentPosition; @@ -166,6 +165,10 @@ typedef struct { typedef struct LSP { Process process; u32 request_id; + StrHashTable document_ids; // values are u32. they are indices into document_filenames. + // this is a dynamic array which just keeps growing. + // but the user isn't gonna open millions of files so it's fine. + char **document_paths; LSPMessage *messages; SDL_mutex *messages_mutex; LSPRequest *requests_client2server; @@ -194,6 +197,7 @@ typedef struct LSP { // you can set error = NULL, error_size = 0, clear = true to just clear the error bool lsp_get_error(LSP *lsp, char *error, size_t error_size, bool clear); void lsp_message_free(LSPMessage *message); +u32 lsp_document_id(LSP *lsp, const char *path); void lsp_send_request(LSP *lsp, const LSPRequest *request); const char *lsp_response_string(const LSPResponse *response, LSPString string); bool lsp_create(LSP *lsp, const char *analyzer_command); diff --git a/main.c b/main.c index 20e3e57..f0321ee 100644 --- a/main.c +++ b/main.c @@ -1,6 +1,7 @@ /* @TODO: - send didClose +- LSP setting - scroll through completions - figure out under which circumstances backspace should close completions - rename buffer->filename to buffer->path @@ -60,7 +61,7 @@ no_warn_end #endif #include "unicode.h" -#include "arr.c" +#include "ds.c" #include "util.c" #if _WIN32 @@ -315,7 +316,7 @@ int main(int argc, char **argv) { LSPRequest test_req = {.type = LSP_REQUEST_COMPLETION}; test_req.data.completion = (LSPRequestCompletion){ .position = { - .document = str_dup("/p/test-lsp/src/main.rs"), + .document = lsp_document_id(&lsp, "/p/test-lsp/src/main.rs"), .pos = { .line = 2, .character = 2, diff --git a/util.c b/util.c index 7bff5c4..e973674 100644 --- a/util.c +++ b/util.c @@ -378,70 +378,126 @@ static bool copy_file(char const *src, char const *dst) { return success; } + +static uint64_t str_hash(char const *str, size_t len) { + uint64_t hash = 0; + char const *p = str, *end = str + len; + for (; p < end; ++p) { + hash = ((hash * 1664737020647550361 + 123843) << 8) + 2918635993572506131*(uint64_t)*p; + } + return hash; +} + typedef struct { - // dynamic array, including a null byte. char *str; -} StrBuilder; + size_t len; + uint64_t data[]; +} StrHashTableSlot; + +typedef StrHashTableSlot *StrHashTableSlotPtr; -void str_builder_create(StrBuilder *builder) { - memset(builder, 0, sizeof *builder); - arr_add(builder->str, 0); +typedef struct { + StrHashTableSlot **slots; + size_t data_size; + size_t nentries; /* # of filled slots */ +} StrHashTable; + +static inline void str_hash_table_create(StrHashTable *t, size_t data_size) { + t->slots = NULL; + t->data_size = data_size; + t->nentries = 0; +} + +static StrHashTableSlot **str_hash_table_slot_get(StrHashTableSlot **slots, char const *s, size_t s_len, size_t i) { + StrHashTableSlot **slot; + size_t slots_cap = arr_len(slots); + while (1) { + assert(i < slots_cap); + slot = &slots[i]; + if (!*slot) break; + if (s && (*slot)->str && + s_len == (*slot)->len && memcmp(s, (*slot)->str, s_len) == 0) + break; + i = (i+1) % slots_cap; + } + return slot; +} + +static void str_hash_table_grow(StrHashTable *t) { + size_t slots_cap = arr_len(t->slots); + if (slots_cap <= 2 * t->nentries) { + StrHashTableSlot **new_slots = NULL; + size_t new_slots_cap = slots_cap * 2 + 10; + arr_set_len(new_slots, new_slots_cap); + memset(new_slots, 0, new_slots_cap * sizeof *new_slots); + arr_foreach_ptr(t->slots, StrHashTableSlotPtr, slotp) { + StrHashTableSlot *slot = *slotp; + if (slot) { + uint64_t new_hash = str_hash(slot->str, slot->len); + StrHashTableSlot **new_slot = str_hash_table_slot_get(new_slots, slot->str, slot->len, new_hash % new_slots_cap); + *new_slot = slot; + } + } + arr_clear(t->slots); + t->slots = new_slots; + } } -StrBuilder str_builder_new(void) { - StrBuilder ret = {0}; - str_builder_create(&ret); - return ret; +static inline size_t str_hash_table_slot_size(StrHashTable *t) { + return sizeof(StrHashTableSlot) + ((t->data_size + sizeof(uint64_t) - 1) / sizeof(uint64_t)) * sizeof(uint64_t); +} + +static StrHashTableSlot *str_hash_table_insert_(StrHashTable *t, char const *str, size_t len) { + size_t slots_cap; + uint64_t hash; + StrHashTableSlot **slot; + str_hash_table_grow(t); + slots_cap = arr_len(t->slots); + hash = str_hash(str, len); + slot = str_hash_table_slot_get(t->slots, str, len, hash % slots_cap); + if (!*slot) { + *slot = calloc(1, str_hash_table_slot_size(t)); + char *s = (*slot)->str = calloc(1, len + 1); + memcpy(s, str, len); + (*slot)->len = len; + ++t->nentries; + } + return *slot; } -void str_builder_free(StrBuilder *builder) { - arr_free(builder->str); +// does NOT check for a null byte. +static inline void *str_hash_table_insert_with_len(StrHashTable *t, char const *str, size_t len) { + return str_hash_table_insert_(t, str, len)->data; } -void str_builder_clear(StrBuilder *builder) { - str_builder_free(builder); - str_builder_create(builder); +static inline void *str_hash_table_insert(StrHashTable *t, char const *str) { + return str_hash_table_insert_(t, str, strlen(str))->data; } -void str_builder_append(StrBuilder *builder, const char *s) { - assert(builder->str); - - size_t s_len = strlen(s); - size_t prev_size = arr_len(builder->str); - size_t prev_len = prev_size - 1; // null terminator - // note: this zeroes the newly created elements, so we have a new null terminator - arr_set_len(builder->str, prev_size + s_len); - // -1 for null terminator - memcpy(builder->str + prev_len, s, s_len); -} - -void str_builder_appendf(StrBuilder *builder, PRINTF_FORMAT_STRING const char *fmt, ...) ATTRIBUTE_PRINTF(2, 3); -void str_builder_appendf(StrBuilder *builder, const char *fmt, ...) { - // idk if you can always just pass NULL to vsnprintf - va_list args; - char fakebuf[2] = {0}; - va_start(args, fmt); - int ret = vsnprintf(fakebuf, 1, fmt, args); - va_end(args); - - if (ret < 0) return; // bad format or something - u32 n = (u32)ret; - - size_t prev_size = arr_len(builder->str); - size_t prev_len = prev_size - 1; // null terminator - arr_set_len(builder->str, prev_size + n); - va_start(args, fmt); - vsnprintf(builder->str + prev_len, n + 1, fmt, args); - va_end(args); +static void str_hash_table_clear(StrHashTable *t) { + arr_foreach_ptr(t->slots, StrHashTableSlotPtr, slotp) { + if (*slotp) { + free((*slotp)->str); + } + free(*slotp); + } + arr_clear(t->slots); + t->nentries = 0; } -// append n null bytes. -void str_builder_append_null(StrBuilder *builder, size_t n) { - arr_set_len(builder->str, arr_len(builder->str) + n); +static StrHashTableSlot *str_hash_table_get_(StrHashTable *t, char const *str, size_t len) { + size_t nslots = arr_len(t->slots), slot_index; + if (!nslots) return NULL; + slot_index = str_hash(str, len) % arr_len(t->slots); + return *str_hash_table_slot_get(t->slots, str, len, slot_index); } -u32 str_builder_len(StrBuilder *builder) { - assert(builder->str); - return arr_len(builder->str) - 1; +static inline void *str_hash_table_get_with_len(StrHashTable *t, char const *str, size_t len) { + StrHashTableSlot *slot = str_hash_table_get_(t, str, len); + if (!slot) return NULL; + return slot->data; } +static inline void *str_hash_table_get(StrHashTable *t, char const *str) { + return str_hash_table_get_with_len(t, str, strlen(str)); +} -- cgit v1.2.3