document IDs instead of documents

8 files changed, 221 insertions, 80 deletions

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/arr.c b/ds.c
index 402420f..ef4a1b4 100644
--- a/arr.c
+++ b/ds.c
@@ -1,5 +1,9 @@
-#ifndef ARR_C_
-#define ARR_C_
+/* 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
@@ -260,4 +264,70 @@ static void arr_test(void) {
 }
 #endif
 
-#endif // ARR_C_
+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));
+}