Initial bootstrapping

12 files changed, 339 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..80dce25
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,5 @@
+.cache/
+build/
+
+tags
+compile_commands.json
diff --git a/inc/log.h b/inc/log.h
new file mode 100644
index 0000000..335320f
--- /dev/null
+++ b/inc/log.h
@@ -0,0 +1,11 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_LOG_H
+#define SHARING_LOG_H
+
+void debug(const char *format, ...);
+void debug_enable(int enable);
+void fatal(const char *format, ...) __attribute__((noreturn));
+
+#endif
diff --git a/inc/parse.h b/inc/parse.h
new file mode 100644
index 0000000..451647f
--- /dev/null
+++ b/inc/parse.h
@@ -0,0 +1,11 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_PARSE_H
+#define SHARING_PARSE_H
+
+#include <term.h>
+
+struct term *parse_blc(char **term);
+
+#endif
diff --git a/inc/term.h b/inc/term.h
new file mode 100644
index 0000000..0dd472f
--- /dev/null
+++ b/inc/term.h
@@ -0,0 +1,33 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_TERM_H
+#define SHARING_TERM_H
+
+#include <stddef.h>
+
+typedef enum { INV, ABS, APP, VAR } term_type_t;
+
+struct term {
+	term_type_t type;
+	size_t refs;
+	size_t depth;
+	union {
+		struct {
+			struct term *term;
+		} abs;
+		struct {
+			struct term *lhs;
+			struct term *rhs;
+		} app;
+		struct {
+			size_t index;
+		} var;
+	} u;
+};
+
+struct term *term_new(term_type_t type);
+void term_free(struct term *term);
+void term_print(struct term *term);
+
+#endif
diff --git a/license b/license
new file mode 100644
index 0000000..90586b4
--- /dev/null
+++ b/license
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2023 Marvin Borner
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/makefile b/makefile
new file mode 100644
index 0000000..404d7bf
--- /dev/null
+++ b/makefile
@@ -0,0 +1,51 @@
+# Copyright (c) 2022, Marvin Borner <dev@marvinborner.de>
+# SPDX-License-Identifier: MIT
+
+CC = gcc
+TG = ctags
+
+BUILD = ${CURDIR}/build
+SRC = ${CURDIR}/src
+INC = ${CURDIR}/inc
+SRCS = $(wildcard $(SRC)/*.c) $(wildcard $(SRC)/*/*.c)
+OBJS = $(patsubst $(SRC)/%.c, $(BUILD)/%.o, $(SRCS))
+
+CFLAGS_DEBUG = -Wno-error -g -O0 -Wno-unused -fsanitize=address,undefined,leak
+CFLAGS_WARNINGS = -Wall -Wextra -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -pedantic -Wno-switch-enum -Wframe-larger-than=512 -Wstack-usage=1024
+CFLAGS = $(CFLAGS_WARNINGS) -std=c99 -Ofast -I$(INC) -lm
+
+ifdef DEBUG # TODO: Somehow clean automagically
+CFLAGS += $(CFLAGS_DEBUG)
+endif
+
+ifeq ($(PREFIX),)
+    PREFIX := /usr/local
+endif
+
+all: compile
+
+full: all sync
+
+compile: $(BUILD) $(OBJS) $(BUILD)/sharing
+
+clean:
+	@rm -rf $(BUILD)/*
+
+install:
+	@install -m 755 $(BUILD)/sharing $(DESTDIR)$(PREFIX)/bin/
+
+sync: # Ugly hack
+	@$(MAKE) $(BUILD)/sharing --always-make --dry-run | grep -wE 'gcc|g\+\+' | grep -w '\-c' | jq -nR '[inputs|{directory:".", command:., file: match(" [^ ]+$$").string[1:]}]' >compile_commands.json
+	@$(TG) -R --exclude=.git --exclude=build .
+
+$(BUILD)/%.o: $(SRC)/%.c
+	@mkdir -p $(@D)
+	@$(CC) -c -o $@ $(CFLAGS) $<
+
+$(BUILD)/sharing: $(OBJS)
+	@$(CC) -o $@ $(CFLAGS) $^
+
+.PHONY: all compile clean sync
+
+$(BUILD):
+	@mkdir -p $@
diff --git a/readme.md b/readme.md
new file mode 100644
index 0000000..d48ae96
--- /dev/null
+++ b/readme.md
@@ -0,0 +1,8 @@
+# Sharing equality
+
+An implementation of the algorithms presented in \[0\].
+
+\[0\]: Condoluci, Andrea, Beniamino Accattoli, and Claudio Sacerdoti
+Coen. "Sharing equality is linear." Proceedings of the 21st
+International Symposium on Principles and Practice of Declarative
+Programming. 2019.
diff --git a/src/log.c b/src/log.c
new file mode 100644
index 0000000..a34c8e8
--- /dev/null
+++ b/src/log.c
@@ -0,0 +1,40 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <stdio.h>
+#include <stdarg.h>
+#include <stdlib.h>
+
+#include <log.h>
+
+static int debug_enabled = 0;
+
+void debug(const char *format, ...)
+{
+	if (!debug_enabled)
+		return;
+
+	fprintf(stderr, "[DEBUG] ");
+
+	va_list ap;
+	va_start(ap, format);
+	vfprintf(stderr, format, ap);
+	va_end(ap);
+}
+
+void debug_enable(int enable)
+{
+	debug_enabled = enable;
+}
+
+void fatal(const char *format, ...)
+{
+	fprintf(stderr, "[FATAL] ");
+
+	va_list ap;
+	va_start(ap, format);
+	vfprintf(stderr, format, ap);
+	va_end(ap);
+
+	abort();
+}
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..de74288
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,60 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+
+#include <parse.h>
+#include <log.h>
+
+static char *read_file(FILE *f)
+{
+	fseek(f, 0, SEEK_END);
+	long fsize = ftell(f);
+	fseek(f, 0, SEEK_SET);
+
+	char *string = malloc(fsize + 1);
+	if (!string)
+		fatal("out of memory!\n");
+	int ret = fread(string, fsize, 1, f);
+
+	if (ret != 1) {
+		free(string);
+		fatal("can't read file: %s\n", strerror(errno));
+	}
+
+	string[fsize] = 0;
+	return string;
+}
+
+static char *read_path(const char *path)
+{
+	debug("reading from %s\n", path);
+	FILE *f = fopen(path, "rb");
+	if (!f)
+		fatal("can't open file %s: %s\n", path, strerror(errno));
+	char *string = read_file(f);
+	fclose(f);
+	return string;
+}
+
+int main(int argc, char *argv[])
+{
+	debug_enable(1);
+	if (argc != 2)
+		fatal("usage: %s <file>\n", argc ? argv[0] : "sharing");
+
+	char *term = read_path(argv[1]);
+
+	char *orig_term = term;
+	struct term *parsed = parse_blc(&term);
+	free(orig_term);
+
+	term_print(parsed);
+	fprintf(stderr, "\n");
+
+	term_free(parsed);
+	return 0;
+}
diff --git a/src/parse.c b/src/parse.c
new file mode 100644
index 0000000..18dfffe
--- /dev/null
+++ b/src/parse.c
@@ -0,0 +1,37 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <stdlib.h>
+
+#include <parse.h>
+#include <log.h>
+
+struct term *parse_blc(char **term)
+{
+	if (!**term) {
+		fatal("invalid parsing state!\n");
+	} else if (**term == '0' && *(*term + 1) == '0') {
+		(*term) += 2;
+		struct term *new = term_new(ABS);
+		new->u.abs.term = parse_blc(term);
+		return new;
+	} else if (**term == '0' && *(*term + 1) == '1') {
+		(*term) += 2;
+		struct term *new = term_new(APP);
+		new->u.app.lhs = parse_blc(term);
+		new->u.app.rhs = parse_blc(term);
+		return new;
+	} else if (**term == '1') {
+		const char *cur = *term;
+		while (**term == '1')
+			(*term)++;
+		int index = *term - cur - 1;
+		(*term)++;
+		struct term *new = term_new(VAR);
+		new->u.var.index = index;
+		return new;
+	} else {
+		(*term)++;
+		return parse_blc(term);
+	}
+}
diff --git a/src/term.c b/src/term.c
new file mode 100644
index 0000000..aa7c17b
--- /dev/null
+++ b/src/term.c
@@ -0,0 +1,61 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+
+#include <log.h>
+#include <term.h>
+
+struct term *term_new(term_type_t type)
+{
+	struct term *term = malloc(sizeof(*term));
+	if (!term)
+		fatal("out of memory!\n");
+	term->type = type;
+	return term;
+}
+
+void term_free(struct term *term)
+{
+	switch (term->type) {
+	case ABS:
+		term_free(term->u.abs.term);
+		free(term);
+		break;
+	case APP:
+		term_free(term->u.app.lhs);
+		term_free(term->u.app.rhs);
+		free(term);
+		break;
+	case VAR:
+		free(term);
+		break;
+	default:
+		fatal("invalid type %d\n", term->type);
+	}
+}
+
+void term_print(struct term *term)
+{
+	switch (term->type) {
+	case ABS:
+		fprintf(stderr, "[");
+		term_print(term->u.abs.term);
+		fprintf(stderr, "]");
+		break;
+	case APP:
+		fprintf(stderr, "(");
+		term_print(term->u.app.lhs);
+		fprintf(stderr, " ");
+		term_print(term->u.app.rhs);
+		fprintf(stderr, ")");
+		break;
+	case VAR:
+		fprintf(stderr, "%ld", term->u.var.index);
+		break;
+	default:
+		fatal("invalid type %d\n", term->type);
+	}
+}
diff --git a/test.blc b/test.blc
new file mode 100644
index 0000000..05c2b00
--- /dev/null
+++ b/test.blc
@@ -0,0 +1 @@
+000100100000110