1 files changed, 100 insertions, 0 deletions
diff --git a/prism/line_offset_list.c b/prism/line_offset_list.c
new file mode 100644
index 0000000000..ce217ebd3f
--- /dev/null
+++ b/prism/line_offset_list.c
@@ -0,0 +1,100 @@
+#include "prism/compiler/align.h"
+#include "prism/internal/line_offset_list.h"
+#include "prism/internal/arena.h"
+
+#include <assert.h>
+#include <string.h>
+
+/**
+ * Initialize a new line offset list with the given capacity.
+ */
+void
+pm_line_offset_list_init(pm_arena_t *arena, pm_line_offset_list_t *list, size_t capacity) {
+    list->offsets = (uint32_t *) pm_arena_alloc(arena, capacity * sizeof(uint32_t), PRISM_ALIGNOF(uint32_t));
+
+    // The first line always has offset 0.
+    list->offsets[0] = 0;
+    list->size = 1;
+    list->capacity = capacity;
+}
+
+/**
+ * Clear out the newlines that have been appended to the list.
+ */
+void
+pm_line_offset_list_clear(pm_line_offset_list_t *list) {
+    list->size = 1;
+}
+
+/**
+ * Append a new offset to the newline list (slow path: resize and store).
+ */
+void
+pm_line_offset_list_append_slow(pm_arena_t *arena, pm_line_offset_list_t *list, uint32_t cursor) {
+    size_t new_capacity = (list->capacity * 3) / 2;
+    uint32_t *new_offsets = (uint32_t *) pm_arena_alloc(arena, new_capacity * sizeof(uint32_t), PRISM_ALIGNOF(uint32_t));
+
+    memcpy(new_offsets, list->offsets, list->size * sizeof(uint32_t));
+
+    list->offsets = new_offsets;
+    list->capacity = new_capacity;
+
+    assert(list->size == 0 || cursor > list->offsets[list->size - 1]);
+    list->offsets[list->size++] = cursor;
+}
+
+/**
+ * Returns the line of the given offset. If the offset is not in the list, the
+ * line of the closest offset less than the given offset is returned.
+ */
+int32_t
+pm_line_offset_list_line(const pm_line_offset_list_t *list, uint32_t cursor, int32_t start_line) {
+    size_t left = 0;
+    size_t right = list->size - 1;
+
+    while (left <= right) {
+        size_t mid = left + (right - left) / 2;
+
+        if (list->offsets[mid] == cursor) {
+            return ((int32_t) mid) + start_line;
+        }
+
+        if (list->offsets[mid] < cursor) {
+            left = mid + 1;
+        } else {
+            right = mid - 1;
+        }
+    }
+
+    return ((int32_t) left) + start_line - 1;
+}
+
+/**
+ * Returns the line and column of the given offset. If the offset is not in the
+ * list, the line and column of the closest offset less than the given offset
+ * are returned.
+ */
+pm_line_column_t
+pm_line_offset_list_line_column(const pm_line_offset_list_t *list, uint32_t cursor, int32_t start_line) {
+    size_t left = 0;
+    size_t right = list->size - 1;
+
+    while (left <= right) {
+        size_t mid = left + (right - left) / 2;
+
+        if (list->offsets[mid] == cursor) {
+            return ((pm_line_column_t) { ((int32_t) mid) + start_line, 0 });
+        }
+
+        if (list->offsets[mid] < cursor) {
+            left = mid + 1;
+        } else {
+            right = mid - 1;
+        }
+    }
+
+    return ((pm_line_column_t) {
+        .line = ((int32_t) left) + start_line - 1,
+        .column = cursor - list->offsets[left - 1]
+    });
+}