Add seeds of edi

6 files changed, 464 insertions, 0 deletions

diff --git a/bin/edi/.gitignore b/bin/edi/.gitignore
new file mode 100644
index 00000000..c76928a8
--- /dev/null
+++ b/bin/edi/.gitignore
@@ -0,0 +1,4 @@
+*.o
+*.t
+edi
+tags
diff --git a/bin/edi/Makefile b/bin/edi/Makefile
new file mode 100644
index 00000000..2d9128c0
--- /dev/null
+++ b/bin/edi/Makefile
@@ -0,0 +1,30 @@
+CFLAGS += -Wall -Wextra -Wpedantic
+LDLIBS = -lcursesw
+
+OBJS += buffer.o
+OBJS += log.o
+OBJS += table.o
+
+TESTS += buffer.t
+TESTS += table.t
+
+all: tags edi test
+
+tags: *.h *.c
+	ctags -w *.h *.c
+
+edi: $(OBJS)
+	$(CC) $(LDFLAGS) $(OBJS) $(LDLIBS) -o $@
+
+$(OBJS): edi.h
+
+test: $(TESTS)
+	set -e; $(TESTS:%=./%;)
+
+.SUFFIXES: .t
+
+.c.t:
+	$(CC) $(CFLAGS) -DTEST $(LDFLAGS) $< $(LDLIBS) -o $@
+
+clean:
+	rm -f tags edi $(OBJS) $(TESTS)
diff --git a/bin/edi/buffer.c b/bin/edi/buffer.c
new file mode 100644
index 00000000..cefd0a5e
--- /dev/null
+++ b/bin/edi/buffer.c
@@ -0,0 +1,145 @@
+/* Copyright (C) 2018  June McEnroe <june@causal.agency>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <err.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sysexits.h>
+#include <wchar.h>
+
+#include "edi.h"
+
+static struct Block *blockAlloc(struct Block *prev, size_t cap) {
+	size_t size = sizeof(struct Block) + sizeof(wchar_t) * cap;
+	struct Block *block = malloc(size);
+	if (!block) err(EX_OSERR, "malloc");
+	block->prev = prev;
+	return block;
+}
+
+struct Buffer bufferAlloc(size_t cap) {
+	struct Block *block = blockAlloc(NULL, cap);
+	return (struct Buffer) {
+		.cap = cap,
+		.len = 0,
+		.slice = { block->chars, 0 },
+		.block = block,
+	};
+}
+
+void bufferFree(struct Buffer *buf) {
+	struct Block *prev;
+	for (struct Block *it = buf->block; it; it = prev) {
+		prev = it->prev;
+		free(it);
+	}
+}
+
+void bufferInsert(struct Buffer *buf) {
+	buf->slice.ptr = &buf->block->chars[buf->len];
+	buf->slice.len = 0;
+}
+
+void bufferAppend(struct Buffer *buf, wchar_t ch) {
+	if (buf->len == buf->cap) {
+		if (buf->slice.len == buf->cap) buf->cap *= 2;
+		struct Block *block = blockAlloc(buf->block, buf->cap);
+		memcpy(block->chars, buf->slice.ptr, sizeof(wchar_t) * buf->slice.len);
+		buf->len = buf->slice.len;
+		buf->slice.ptr = block->chars;
+		buf->block = block;
+	}
+	buf->block->chars[buf->len++] = ch;
+	buf->slice.len++;
+}
+
+wchar_t *bufferDest(struct Buffer *buf, size_t len) {
+	if (buf->len + len > buf->cap) {
+		while (len > buf->cap) buf->cap *= 2;
+		buf->block = blockAlloc(buf->block, buf->cap);
+		buf->len = 0;
+	}
+	wchar_t *ptr = &buf->block->chars[buf->len];
+	buf->slice.ptr = ptr;
+	buf->slice.len = len;
+	buf->len += len;
+	return ptr;
+}
+
+#ifdef TEST
+#include <assert.h>
+
+int main() {
+	struct Buffer buf = bufferAlloc(6);
+
+	bufferInsert(&buf);
+	bufferAppend(&buf, L'A');
+	bufferAppend(&buf, L'B');
+	assert(!wcsncmp(L"AB", buf.slice.ptr, buf.slice.len));
+
+	bufferInsert(&buf);
+	bufferAppend(&buf, L'C');
+	bufferAppend(&buf, L'D');
+	assert(!wcsncmp(L"CD", buf.slice.ptr, buf.slice.len));
+
+	bufferInsert(&buf);
+	bufferAppend(&buf, L'E');
+	bufferAppend(&buf, L'F');
+	bufferAppend(&buf, L'G');
+	bufferAppend(&buf, L'H');
+	assert(!wcsncmp(L"EFGH", buf.slice.ptr, buf.slice.len));
+
+	bufferFree(&buf);
+
+	buf = bufferAlloc(4);
+	bufferInsert(&buf);
+	bufferAppend(&buf, L'A');
+	bufferAppend(&buf, L'B');
+	bufferAppend(&buf, L'C');
+	bufferAppend(&buf, L'D');
+	bufferAppend(&buf, L'E');
+	bufferAppend(&buf, L'F');
+	assert(!wcsncmp(L"ABCDEF", buf.slice.ptr, buf.slice.len));
+	bufferFree(&buf);
+
+	buf = bufferAlloc(4);
+
+	wchar_t *dest = bufferDest(&buf, 2);
+	dest[0] = L'A';
+	dest[1] = L'B';
+	assert(!wcsncmp(L"AB", buf.slice.ptr, buf.slice.len));
+
+	dest = bufferDest(&buf, 3);
+	dest[0] = L'C';
+	dest[1] = L'D';
+	dest[2] = L'E';
+	assert(!wcsncmp(L"CDE", buf.slice.ptr, buf.slice.len));
+
+	bufferFree(&buf);
+
+	buf = bufferAlloc(4);
+	dest = bufferDest(&buf, 6);
+	dest[0] = L'A';
+	dest[1] = L'B';
+	dest[2] = L'C';
+	dest[3] = L'D';
+	dest[4] = L'E';
+	dest[5] = L'F';
+	assert(!wcsncmp(L"ABCDEF", buf.slice.ptr, buf.slice.len));
+	bufferFree(&buf);
+}
+
+#endif
diff --git a/bin/edi/edi.h b/bin/edi/edi.h
new file mode 100644
index 00000000..ced4f4a9
--- /dev/null
+++ b/bin/edi/edi.h
@@ -0,0 +1,86 @@
+/* Copyright (C) 2018  June McEnroe <june@causal.agency>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdlib.h>
+#include <wchar.h>
+
+struct Span {
+	size_t at, to;
+};
+
+static inline struct Span spanNext(struct Span span, size_t len) {
+	return (struct Span) { span.to, span.to + len };
+}
+
+struct Slice {
+	const wchar_t *ptr;
+	size_t len;
+};
+
+struct Buffer {
+	size_t cap;
+	size_t len;
+	struct Slice slice;
+	struct Block {
+		struct Block *prev;
+		wchar_t chars[];
+	} *block;
+};
+
+struct Buffer bufferAlloc(size_t cap);
+void bufferFree(struct Buffer *buf);
+void bufferInsert(struct Buffer *buf);
+void bufferAppend(struct Buffer *buf, wchar_t ch);
+wchar_t *bufferDest(struct Buffer *buf, size_t len);
+
+struct Table {
+	size_t len;
+	struct Slice slices[];
+};
+
+struct Table *tableInsert(const struct Table *prev, size_t at, struct Slice slice);
+struct Table *tableDelete(const struct Table *prev, struct Span del);
+
+struct Log {
+	size_t cap;
+	size_t len;
+	size_t index;
+	struct State {
+		struct Table *table;
+		size_t prev;
+		size_t next;
+	} *states;
+};
+
+struct Log logAlloc(size_t cap);
+void logFree(struct Log *log);
+void logPush(struct Log *log, struct Table *table);
+
+static inline struct Table *logTable(struct Log *log) {
+	return log->states[log->index].table;
+}
+static inline void logPrev(struct Log *log) {
+	log->index = log->states[log->index].prev;
+}
+static inline void logNext(struct Log *log) {
+	log->index = log->states[log->index].next;
+}
+static inline void logBack(struct Log *log) {
+	if (log->index) log->index--;
+}
+static inline void logFore(struct Log *log) {
+	if (log->index + 1 < log->len) log->index++;
+}
diff --git a/bin/edi/log.c b/bin/edi/log.c
new file mode 100644
index 00000000..b0bd117e
--- /dev/null
+++ b/bin/edi/log.c
@@ -0,0 +1,63 @@
+/* Copyright (C) 2018  June McEnroe <june@causal.agency>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <assert.h>
+#include <err.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <sysexits.h>
+
+#include "edi.h"
+
+struct Log logAlloc(size_t cap) {
+	assert(cap);
+	struct State *states = malloc(sizeof(*states) * cap);
+	if (!states) err(EX_OSERR, "malloc");
+	states[0] = (struct State) {
+		.table = NULL,
+		.prev = 0,
+		.next = 0,
+	};
+	return (struct Log) {
+		.cap = cap,
+		.len = 1,
+		.index = 0,
+		.states = states,
+	};
+}
+
+void logFree(struct Log *log) {
+	for (size_t i = 0; i < log->len; ++i) {
+		free(log->states[i].table);
+	}
+	free(log->states);
+}
+
+void logPush(struct Log *log, struct Table *table) {
+	if (log->len == log->cap) {
+		log->cap *= 2;
+		log->states = realloc(log->states, sizeof(*log->states) * log->cap);
+		if (!log->states) err(EX_OSERR, "realloc");
+	}
+	size_t next = log->len++;
+	log->states[next] = (struct State) {
+		.table = table,
+		.prev = log->index,
+		.next = next,
+	};
+	log->states[log->index].next = next;
+	log->index = next;
+}
diff --git a/bin/edi/table.c b/bin/edi/table.c
new file mode 100644
index 00000000..ad8f1f9d
--- /dev/null
+++ b/bin/edi/table.c
@@ -0,0 +1,136 @@
+/* Copyright (C) 2018  June McEnroe <june@causal.agency>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <err.h>
+#include <stdlib.h>
+#include <sysexits.h>
+#include <wchar.h>
+
+#include "edi.h"
+
+static struct Table *alloc(size_t cap) {
+	size_t size = sizeof(struct Table) + sizeof(struct Slice) * cap;
+	struct Table *table = malloc(size);
+	if (!table) err(EX_OSERR, "malloc");
+	table->len = 0;
+	return table;
+}
+
+struct Table *tableInsert(const struct Table *prev, size_t at, struct Slice slice) {
+	if (!prev || !prev->len) {
+		struct Table *next = alloc(1);
+		next->slices[next->len++] = slice;
+		return next;
+	}
+
+	struct Table *next = alloc(prev->len + 2);
+	struct Span span = { 0, 0 };
+	for (size_t i = 0; i < prev->len; ++i) {
+		span = spanNext(span, prev->slices[i].len);
+		if (span.at == at) {
+			next->slices[next->len++] = slice;
+			next->slices[next->len++] = prev->slices[i];
+		} else if (span.at < at && span.to > at) {
+			next->slices[next->len++] = (struct Slice) {
+				prev->slices[i].ptr,
+				at - span.at,
+			};
+			next->slices[next->len++] = slice;
+			next->slices[next->len++] = (struct Slice) {
+				&prev->slices[i].ptr[at - span.at],
+				prev->slices[i].len - (at - span.at),
+			};
+		} else {
+			next->slices[next->len++] = prev->slices[i];
+		}
+	}
+	if (span.to == at) {
+		next->slices[next->len++] = slice;
+	}
+	return next;
+}
+
+struct Table *tableDelete(const struct Table *prev, struct Span del) {
+	if (!prev || !prev->len) return alloc(0);
+
+	struct Table *next = alloc(prev->len + 1);
+	struct Span span = { 0, 0 };
+	for (size_t i = 0; i < prev->len; ++i) {
+		span = spanNext(span, prev->slices[i].len);
+		if (span.at >= del.at && span.to <= del.to) {
+			(void)prev->slices[i];
+		} else if (span.at < del.at && span.to > del.to) {
+			next->slices[next->len++] = (struct Slice) {
+				prev->slices[i].ptr,
+				del.at - span.at,
+			};
+			next->slices[next->len++] = (struct Slice) {
+				&prev->slices[i].ptr[del.to - span.at],
+				prev->slices[i].len - (del.to - span.at),
+			};
+		} else if (span.at < del.at && span.to > del.at) {
+			next->slices[next->len++] = (struct Slice) {
+				prev->slices[i].ptr,
+				del.at - span.at,
+			};
+		} else if (span.at < del.to && span.to > del.to) {
+			next->slices[next->len++] = (struct Slice) {
+				&prev->slices[i].ptr[del.to - span.at],
+				prev->slices[i].len - (del.to - span.at),
+			};
+		} else {
+			next->slices[next->len++] = prev->slices[i];
+		}
+	}
+	return next;
+}
+
+#ifdef TEST
+#include <assert.h>
+
+static struct Span span(size_t at, size_t to) {
+	return (struct Span) { at, to };
+}
+
+static struct Slice slice(const wchar_t *str) {
+	return (struct Slice) { str, wcslen(str) };
+}
+
+static int eq(const struct Table *table, const wchar_t *str) {
+	for (size_t i = 0; i < table->len; ++i) {
+		if (wcsncmp(str, table->slices[i].ptr, table->slices[i].len)) {
+			return 0;
+		}
+		str = &str[table->slices[i].len];
+	}
+	return 1;
+}
+
+int main() {
+	struct Table *abc = tableInsert(NULL, 0, slice(L"ABC"));
+	assert(eq(abc, L"ABC"));
+
+	assert(eq(tableInsert(abc, 0, slice(L"D")), L"DABC"));
+	assert(eq(tableInsert(abc, 3, slice(L"D")), L"ABCD"));
+	assert(eq(tableInsert(abc, 1, slice(L"D")), L"ADBC"));
+
+	assert(eq(tableDelete(abc, span(0, 1)), L"BC"));
+	assert(eq(tableDelete(abc, span(2, 3)), L"AB"));
+	assert(eq(tableDelete(abc, span(1, 2)), L"AC"));
+	assert(eq(tableDelete(abc, span(0, 3)), L""));
+}
+
+#endif