summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore3
-rw-r--r--Makefile41
-rw-r--r--cmd/main.c115
-rw-r--r--src/leven.c331
-rw-r--r--src/leven.h57
-rw-r--r--src/log.h13
-rw-r--r--src/mat.h43
-rw-r--r--src/parse.c172
-rw-r--r--src/parse.h7
-rw-r--r--test/contrained.c281
-rw-r--r--test/leven.c109
-rw-r--r--test/parse.c114
12 files changed, 1286 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..6117644
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+compile_commands.json
+obj/
+/app
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..05ef562
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,41 @@
+SRC_DIR = src
+CMD_DIR = cmd
+TST_DIR = test
+
+OBJ_DIR = obj
+
+CMD_SRC = $(wildcard $(CMD_DIR)/*.c)
+CMD_OBJ = $(CMD_SRC:%=$(OBJ_DIR)/%.o)
+
+TST_SRC = $(wildcard $(TST_DIR)/*.c)
+TST_RUN = $(TST_SRC:$(TST_DIR)/%.c=$(OBJ_DIR)/test_runner/%)
+
+CC_SRC = $(wildcard $(SRC_DIR)/*.c)
+CC_OBJ = $(CC_SRC:%=$(OBJ_DIR)/%.o)
+
+CFLAGS = -Wall -I$(SRC_DIR)
+CFLAGS += -g
+LDFLAGS =
+
+$(OBJ_DIR)/%.c.o: %.c
+ @mkdir -p $(@D)
+ $(CC) $(CFLAGS) -o $@ -c $<
+
+app: $(CC_OBJ) $(CMD_OBJ)
+ @mkdir -p $(@D)
+ $(CC) $(LDFLAGS) $(CC_OBJ) $(CMD_OBJ) -o $@
+
+$(OBJ_DIR)/test_runner/%: $(OBJ_DIR)/$(TST_DIR)/%.c.o $(CC_OBJ)
+ @mkdir -p $(@D)
+ $(CC) $(LDFLAGS) $(CC_OBJ) $< -o $@
+
+.PHONY: test
+test: $(TST_RUN)
+ $(foreach var,$(TST_RUN),./$(var) &&) true
+
+.PHONY: all
+all: app $(TST_RUN)
+
+.PHONY: clean
+clean:
+ @$(RM) -rf obj/
diff --git a/cmd/main.c b/cmd/main.c
new file mode 100644
index 0000000..541d646
--- /dev/null
+++ b/cmd/main.c
@@ -0,0 +1,115 @@
+#include <assert.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <fcntl.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <sys/mman.h>
+
+#include "leven.h"
+#include "parse.h"
+
+int main(int argc, char **argv) {
+ int rc;
+ /* int fd = open("filename", O_RDONLY); */
+ /* int len = lseek(fd, 0, SEEK_END); */
+ /* void *data = mmap(0, len, PROT_READ, MAP_PRIVATE, fd, 0); */
+
+ char* a = "<root><a/><b></b></root>";
+ char* b = "<root><a><b/></a></root>";
+
+ struct Tree a_tree;
+ size_t *a_chunks;
+ rc = parse_string(a, &a_tree, &a_chunks);
+ if(rc != 0) return 1;
+ printf("%ld\n", a_tree.len);
+
+ struct Tree b_tree;
+ size_t *b_chunks;
+ rc = parse_string(b, &b_tree, &b_chunks);
+ if(rc != 0) return 1;
+ printf("%ld\n", b_tree.len);
+
+ DECL_MAT_DATA(cost, uint32_t, 4, 4,
+ 0, 2, 2, 2,
+ 2, 0, 1, 1,
+ 2, 1, 0, 1,
+ 2, 1, 1, 0,
+ );
+ printf("\n");
+ for(size_t y = 0; y < b_tree.len; y++) {
+ for(size_t x = 0; x < b_tree.adj.stride; x++) {
+ printf("%d ", *imat_nid(b_tree.adj, x, y));
+ }
+ printf("\n");
+ }
+ printf("\n");
+ printf("\n");
+ for(size_t y = 0; y < a_tree.len; y++) {
+ for(size_t x = 0; x < a_tree.adj.stride; x++) {
+ printf("%d ", *imat_nid(a_tree.adj, x, y));
+ }
+ printf("\n");
+ }
+ printf("\n");
+ /* mat_uint32_t cost = { */
+ /* .data = malloc(a_tree.len * b_tree.len * sizeof(uint32_t)), */
+ /* .stride = a_tree.len, */
+ /* }; */
+ /* assert(cost.data != NULL); */
+
+ mat_uint32_t cost_n = {
+ .data = malloc((a_tree.len+1) * (b_tree.len+1) * sizeof(uint32_t)),
+ .stride = a_tree.len+1,
+ };
+ assert(cost_n.data != NULL);
+
+ mat_uint32_t cost_f = {
+ .data = malloc((a_tree.len+1) * (b_tree.len+1) * sizeof(uint32_t)),
+ .stride = a_tree.len+1,
+ };
+ assert(cost_f.data != NULL);
+
+ mat_uint32_t cost_s = {
+ .data = malloc((a_tree.adj.stride+1) * (b_tree.adj.stride+1) * sizeof(uint32_t)),
+ .stride = a_tree.adj.stride+1,
+ };
+ assert(cost_s.data != NULL);
+
+ constrained_tree_distance(a_tree, b_tree, cost, cost_n, cost_f, cost_s);
+
+ printf("COST_F\n");
+ for(size_t y = 0; y < b_tree.len+1; y++) {
+ for(size_t x = 0; x < cost.stride; x++) {
+ printf("%d ", *imat_uint32_t(cost_f, x, y));
+ }
+ printf("\n");
+ }
+ printf("\n");
+ printf("COST_N\n");
+ for(size_t y = 0; y < b_tree.len+1; y++) {
+ for(size_t x = 0; x < cost.stride; x++) {
+ printf("%d ", *imat_uint32_t(cost_n, x, y));
+ }
+ printf("\n");
+ }
+ printf("\n");
+
+ printf("%d\n", *imat_uint32_t(cost_n, 1, 1));
+
+ DECL_MAT(alignment, uint32_t, 2, 2);
+ uint32_t adj_alignment[2] = {0, 0};
+ constrained_tree_alignment(
+ a_tree,
+ b_tree,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ adj_alignment,
+ alignment
+ );
+
+ printf("Hello sailor\n");
+ return 0;
+}
diff --git a/src/leven.c b/src/leven.c
new file mode 100644
index 0000000..9ed2ab3
--- /dev/null
+++ b/src/leven.c
@@ -0,0 +1,331 @@
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "leven.h"
+#include "log.h"
+
+#if 1
+#define debug2D(array, len) debug2D_impl(#array, array, len)
+static void debug2D_impl(char* name, mat_uint32_t mat, uint32_t len) {
+ logb("2D Array %s [%ldx%d]", name, mat.stride, len);
+ for(uint32_t y = 0; y < len; y++) {
+ lognl();
+ for(uint32_t x = 0; x < mat.stride; x++) {
+ logc("%03d ", *imat_uint32_t(mat, x, y));
+ }
+ }
+ loge();
+}
+#endif
+
+static inline int min(uint32_t a, uint32_t b) {
+ return (a < b) ? a : b;
+}
+
+void string_edit_distance(const nid *a, size_t la, const nid *b, size_t lb, const mat_uint32_t weight, mat_uint32_t cost) {
+ *imat_uint32_t(cost, 0, 0) = 0;
+
+ for (int i = 1; i <= la; i++) {
+ nid ac = a[i-1];
+ assert(ac != 0);
+ *imat_uint32_t(cost, i, 0) = *imat_uint32_t(cost, i-1, 0) + *imat_uint32_t(weight, ac, 0);
+ }
+
+ for (int i = 1; i <= lb; i++) {
+ nid bc = b[i-1];
+ assert(bc != 0);
+ *imat_uint32_t(cost, 0, i) = *imat_uint32_t(cost, 0, i-1) + *imat_uint32_t(weight, 0, bc);
+ }
+
+ for(int j = 1; j <= lb; j++) {
+ for(int i = 1; i <= la; i++) {
+ nid ac = a[i-1];
+ assert(ac != 0);
+ nid bc = b[j-1];
+ assert(bc != 0);
+
+ // Remove
+ *imat_uint32_t(cost, i, j) = *imat_uint32_t(cost, i-1, j ) + *imat_uint32_t(weight, ac, 0);
+ // Add
+ *imat_uint32_t(cost, i, j) = min(*imat_uint32_t(cost, i , j-1) + *imat_uint32_t(weight, 0, bc), *imat_uint32_t(cost, i, j));
+ // Replace
+ *imat_uint32_t(cost, i, j) = min(*imat_uint32_t(cost, i-1, j-1) + *imat_uint32_t(weight, ac, bc), *imat_uint32_t(cost, i, j));
+ }
+ }
+ debug2D(cost, lb+1);
+}
+
+void string_edit_alignment(const nid *a, size_t la, const nid *b, size_t lb, const mat_uint32_t weight, const mat_uint32_t cost, uint32_t *alignment) {
+ int i = la;
+ int j = lb;
+ while(j > 0) {
+ // The order of these operations dictate our preference if we have multiple equivalent answers
+ if(i == 0) {
+ // If we run out of characters the rest must be added
+ alignment[j-1] = -1;
+ j--;
+ } else if(*imat_uint32_t(cost, i, j) == *imat_uint32_t(cost, i-1, j-1) + *imat_uint32_t(weight, a[i-1], b[j-1])) {
+ alignment[j-1] = i-1;
+ i--;
+ j--;
+ } else if(*imat_uint32_t(cost, i, j) == *imat_uint32_t(cost, i-1, j) + *imat_uint32_t(weight, a[i-1], 0)) {
+ i--;
+ } else if(*imat_uint32_t(cost, i, j) == *imat_uint32_t(cost, i , j-1) + *imat_uint32_t(weight, 0, b[j-1])) {
+ alignment[j-1] = -1;
+ j--;
+ } else {
+ abort();
+ }
+ }
+}
+
+void constrained_tree_distance(
+ const struct Tree a,
+ const struct Tree b,
+ const mat_uint32_t cost, // The cost matrix to map a node from a (x-axis) to a node from b (y-axis)
+ mat_uint32_t cost_n, // The resulting computed cost matrixes node and forest. Size a.len x b.len
+ mat_uint32_t cost_f,
+ mat_uint32_t cost_s // Scratch space to calculate the edit distance between subtrees. Size a.adj.stride x b.adj.stride.
+) {
+ *imat_uint32_t(cost_n, 0, 0) = 0;
+ *imat_uint32_t(cost_f, 0, 0) = 0;
+
+ // Outer edges is creating/deleting the node
+ for(size_t i = a.len; i > 0; i--) {
+ *imat_uint32_t(cost_f, i, 0) = 0;
+ for(size_t j = 0; j < a.adj.stride && *imat_nid(a.adj, j, i-1) != 0; j++) {
+ *imat_uint32_t(cost_f, i, 0) += *imat_uint32_t(cost_n, *imat_nid(a.adj, j, i-1), 0);
+ }
+ *imat_uint32_t(cost_n, i, 0) = *imat_uint32_t(cost_f, i, 0) + *imat_uint32_t(cost, i, 0);
+ }
+
+ for(size_t i = b.len; i > 0; i--) {
+ *imat_uint32_t(cost_f, 0, i) = 0;
+ for(size_t j = 0; j < b.adj.stride && *imat_nid(b.adj, j, i-1) != 0; j++) {
+ *imat_uint32_t(cost_f, 0, i) += *imat_uint32_t(cost_n, 0, *imat_nid(b.adj, j, i-1));
+ }
+ *imat_uint32_t(cost_n, 0, i) = *imat_uint32_t(cost_f, 0, i) + *imat_uint32_t(cost, 0, i);
+ }
+
+ for(size_t j = b.len; j > 0; j--) {
+ size_t b_adj_len = 0;
+ while(b_adj_len < b.adj.stride && *imat_nid(b.adj, b_adj_len, j-1) != 0) b_adj_len++;
+
+ for(size_t i = a.len; i > 0; i--) {
+ size_t a_adj_len = 0;
+ while(a_adj_len < a.adj.stride && *imat_nid(a.adj, a_adj_len, i-1) != 0) a_adj_len++;
+
+ string_edit_distance(imat_nid(a.adj, 0, i-1), a_adj_len, imat_nid(b.adj, 0, j-1), b_adj_len, cost_n, cost_s);
+ uint32_t min_cost = *imat_uint32_t(cost_s, a_adj_len, b_adj_len);
+
+ if(a_adj_len > 0) {
+ uint32_t temp_min = UINT32_MAX;
+ for(uint32_t k = 0; k < a_adj_len; k++) {
+ uint32_t cost = *imat_uint32_t(cost_f, *imat_nid(a.adj, k, i-1), j) - *imat_uint32_t(cost_f, *imat_nid(a.adj, k, i-1), 0);
+ if(temp_min > cost)
+ temp_min = cost;
+ }
+ min_cost = min(min_cost, *imat_uint32_t(cost_f, i, 0) + temp_min);
+ }
+
+ if(b_adj_len > 0) {
+ uint32_t temp_min = UINT32_MAX;
+ for(uint32_t k = 0; k < b_adj_len; k++) {
+ uint32_t cost = *imat_uint32_t(cost_f, i, *imat_nid(b.adj, k, j-1)) - *imat_uint32_t(cost_f, 0, *imat_nid(b.adj, k, j-1));
+ if(temp_min > cost)
+ temp_min = cost;
+ }
+ min_cost = min(min_cost, *imat_uint32_t(cost_f, 0, j) + temp_min);
+ }
+
+ *imat_uint32_t(cost_f, i, j) = min_cost;
+
+ min_cost = *imat_uint32_t(cost_f, i, j) + *imat_uint32_t(cost, i, j);
+
+ if(a_adj_len > 0) {
+ uint32_t temp_min = UINT32_MAX;
+ for(uint32_t k = 0; k < a_adj_len; k++) {
+ uint32_t cost = *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), j) - *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), 0);
+ if(temp_min > cost)
+ temp_min = cost;
+ }
+ min_cost = min(min_cost, *imat_uint32_t(cost_n, i, 0) + temp_min);
+ }
+
+ if(b_adj_len > 0) {
+ uint32_t temp_min = UINT32_MAX;
+ for(uint32_t k = 0; k < b_adj_len; k++) {
+ uint32_t cost = *imat_uint32_t(cost_n, i, *imat_nid(b.adj, k, j-1)) - *imat_uint32_t(cost_n, 0, *imat_nid(a.adj, k, j-1));
+ if(temp_min > cost)
+ temp_min = cost;
+ }
+ min_cost = min(min_cost, *imat_uint32_t(cost_n, 0, j) + temp_min);
+ }
+
+ *imat_uint32_t(cost_n, i, j) = min_cost;
+ }
+ }
+}
+
+void constrained_tree_alignment (
+ const struct Tree a,
+ const struct Tree b,
+ const mat_uint32_t cost,
+ const mat_uint32_t cost_n, // The resulting computed cost matrixes node and forest. Size a.len x b.len
+ const mat_uint32_t cost_f,
+ mat_uint32_t cost_s,
+ uint32_t *adj_alignment,
+ mat_uint32_t alignment
+) {
+
+ mat_uint32_t to_compute = {
+ .data = malloc((2 * (a.len * b.len)) * sizeof(uint32_t)),
+ .stride = 2
+ };
+ *imat_uint32_t(to_compute, 0, 0) = 1;
+ *imat_uint32_t(to_compute, 1, 0) = 1;
+ size_t to_compute_head = 1;
+
+ while(to_compute_head > 0) {
+ to_compute_head--;
+ uint32_t i = *imat_uint32_t(to_compute, 0, to_compute_head);
+ uint32_t j = *imat_uint32_t(to_compute, 1, to_compute_head);
+
+ if(i == -1) {
+ size_t remain = 1;
+ size_t cursor = j-1;
+ while(remain > 0) {
+ log("ADD %ld", cursor);
+
+ size_t adj_len = 0;
+ while(adj_len < b.adj.stride && *imat_nid(b.adj, adj_len, cursor) != 0) adj_len++;
+ remain += adj_len;
+
+ cursor++;
+ remain--;
+ }
+ continue;
+ } else if(j == -1) {
+ size_t remain = 1;
+ size_t cursor = i-1;
+ while(remain > 0) {
+ log("REMOVE %ld", cursor);
+
+ size_t adj_len = 0;
+ while(adj_len < a.adj.stride && *imat_nid(a.adj, adj_len, cursor) != 0) adj_len++;
+ remain += adj_len;
+
+ cursor++;
+ remain--;
+ }
+ continue;
+ }
+
+ size_t a_adj_len = 0;
+ while(a_adj_len < a.adj.stride && *imat_nid(a.adj, a_adj_len, i-1) != 0) a_adj_len++;
+
+ size_t b_adj_len = 0;
+ while(b_adj_len < b.adj.stride && *imat_nid(b.adj, b_adj_len, j-1) != 0) b_adj_len++;
+
+ uint32_t min_cost_a = UINT32_MAX;
+ ssize_t min_a = -1;
+ if(a_adj_len > 0) {
+ for(uint32_t k = 0; k < a_adj_len; k++) {
+ uint32_t cost = *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), j) - *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), 0);
+ if(min_cost_a > cost) {
+ min_cost_a = cost;
+ min_a = k;
+ }
+ }
+ }
+
+ uint32_t min_cost_b = UINT32_MAX;
+ ssize_t min_b = -1;
+ if(b_adj_len > 0) {
+ for(uint32_t k = 0; k < b_adj_len; k++) {
+ uint32_t cost = *imat_uint32_t(cost_n, i, *imat_nid(b.adj, k, j-1)) - *imat_uint32_t(cost_n, 0, *imat_nid(b.adj, k, j-1));
+ if(min_cost_b > cost) {
+ min_cost_b = cost;
+ min_b = k;
+ }
+ }
+ }
+
+ if(*imat_uint32_t(cost_n, i, j) == *imat_uint32_t(cost_f, i, j) + *imat_uint32_t(cost, i, j)) {
+ log("MATCH %d %d", i, j);
+ // Compare the forests underneath this node
+ string_edit_distance(imat_nid(a.adj, 0, i-1), a_adj_len, imat_nid(b.adj, 0, j-1), b_adj_len, cost_n, cost_s);
+ assert(*imat_uint32_t(cost_s, a_adj_len, b_adj_len) == *imat_uint32_t(cost_f, i, j));
+ string_edit_alignment(imat_nid(a.adj, 0, i-1), a_adj_len, imat_nid(b.adj, 0, j-1), b_adj_len, cost_n, cost_s, adj_alignment);
+
+ ssize_t a_cursor = a_adj_len-1;
+ ssize_t b_cursor = b_adj_len-1;
+
+ while(b_cursor >= 0) {
+ if(adj_alignment[b_cursor] == -1) {
+ uint32_t *slot = imat_uint32_t(to_compute, 0, to_compute_head);
+ to_compute_head++;
+ slot[0] = -1;
+ slot[1] = *imat_nid(b.adj, b_cursor, j-1);
+
+ b_cursor--;
+ continue;
+ }
+
+ while(a_cursor > adj_alignment[b_cursor]) {
+ uint32_t *slot = imat_uint32_t(to_compute, 0, to_compute_head);
+ to_compute_head++;
+ slot[0] = *imat_nid(a.adj, a_cursor, i-1);
+ slot[1] = -1;
+ a_cursor--;
+
+ continue;
+ }
+
+ uint32_t *slot = imat_uint32_t(to_compute, 0, to_compute_head);
+ to_compute_head++;
+ slot[0] = *imat_nid(a.adj, a_cursor, i-1);
+ slot[1] = *imat_nid(b.adj, b_cursor, j-1);
+
+ b_cursor--;
+ a_cursor--;
+ }
+ } else if(a_adj_len > 0 && *imat_uint32_t(cost_n, i, j) == *imat_uint32_t(cost_n, i, 0) + min_cost_a) {
+ // Remove this node and replace it with one of its children
+ log("REMOVE %ld %ld", i, j);
+ for(size_t x = 0; x < a_adj_len; x++) {
+ uint32_t *slot = imat_uint32_t(to_compute, 0, to_compute_head);
+ to_compute_head++;
+ if(x == min_a) {
+ slot[0] = *imat_nid(a.adj, x, i-1);
+ slot[1] = -1;
+ } else {
+ slot[0] = *imat_nid(a.adj, x, i-1);
+ slot[1] = i;
+ }
+ }
+ } else if(b_adj_len > 0 && *imat_uint32_t(cost_n, i, j) == *imat_uint32_t(cost_n, 0, j) + min_cost_b) {
+ // Inject a node here, moving the current node (from a) into the child forest.
+ log("ADD %ld %ld", i, j);
+ for(size_t x = 0; x < b_adj_len; x++) {
+ uint32_t *slot = imat_uint32_t(to_compute, 0, to_compute_head);
+ to_compute_head++;
+ if(x == min_b) {
+ slot[0] = i;
+ slot[1] = *imat_nid(b.adj, x, j-1);
+ } else {
+ slot[0] = -1;
+ slot[1] = *imat_nid(b.adj, x, j-1);
+ }
+ }
+ } else {
+ abort();
+ }
+ }
+
+ log("END");
+ free(to_compute.data);
+}
diff --git a/src/leven.h b/src/leven.h
new file mode 100644
index 0000000..318eaab
--- /dev/null
+++ b/src/leven.h
@@ -0,0 +1,57 @@
+#pragma once
+
+#include <stddef.h>
+#include <stdint.h>
+
+#define MAT_TYPE uint32_t
+#include "mat.h"
+
+typedef struct {
+ uint32_t *data;
+ size_t stride[2];
+} mat3_uint32_t;
+
+static inline uint32_t* imat3_uint32_t(mat3_uint32_t mat, size_t x, size_t y, size_t z) {
+ assert(x >= 0);
+ assert(y >= 0 && y < mat.stride[0]);
+ assert(z >= 0 && z < mat.stride[1]);
+ return &mat.data[x + y*mat.stride[0] + z*(mat.stride[0]*mat.stride[1])];
+}
+#define DECL_MAT3(NAME, T, X, Y, Z) \
+ mat3_uint32_t NAME = { \
+ .data = (T[X * Y * Z]){}, \
+ .stride = {X, Y}, \
+ } \
+
+typedef uint16_t nid;
+
+#define MAT_TYPE nid
+#include "mat.h"
+
+void string_edit_distance(const nid *a, size_t la, const nid *b, size_t lb, const mat_uint32_t weight, mat_uint32_t cost);
+void string_edit_alignment(const nid *a, size_t la, const nid *b, size_t lb, const mat_uint32_t weight, const mat_uint32_t cost, uint32_t *alignment);
+
+struct Tree {
+ mat_nid adj;
+ size_t len;
+};
+
+void constrained_tree_distance(
+ struct Tree a,
+ struct Tree b,
+ mat_uint32_t cost,
+ mat_uint32_t cost_n,
+ mat_uint32_t cost_f,
+ mat_uint32_t cost_s
+);
+
+void constrained_tree_alignment(
+ const struct Tree a,
+ const struct Tree b,
+ const mat_uint32_t cost,
+ const mat_uint32_t cost_n,
+ const mat_uint32_t cost_f,
+ mat_uint32_t cost_s,
+ uint32_t *adj_alignment,
+ mat_uint32_t alignment
+);
diff --git a/src/log.h b/src/log.h
new file mode 100644
index 0000000..6954106
--- /dev/null
+++ b/src/log.h
@@ -0,0 +1,13 @@
+#pragma once
+
+#include <stdio.h>
+
+#define logb(FORMAT, ...) fprintf(stderr, "%s:%d: " FORMAT, __FILE__, __LINE__ __VA_OPT__(,) __VA_ARGS__)
+#define logc(FORMAT, ...) fprintf(stderr, FORMAT __VA_OPT__(,) __VA_ARGS__)
+#define lognl() fprintf(stderr, "\n")
+#define loge() lognl()
+
+#define log(FORMAT, ...) do { \
+ logb(FORMAT __VA_OPT__(,) __VA_ARGS__); \
+ loge(); \
+} while(0)
diff --git a/src/mat.h b/src/mat.h
new file mode 100644
index 0000000..2f116ea
--- /dev/null
+++ b/src/mat.h
@@ -0,0 +1,43 @@
+#ifndef MAT_TYPE
+#error MAT_TYPE must be defined
+#endif
+
+#include <stddef.h>
+#include <assert.h>
+
+#define PP_CONCAT1(x,y) x ## y
+#define PP_CONCAT(x,y) PP_CONCAT1(x,y)
+
+#ifndef MAT_H_SHARED
+#define MAT_H_SHARED
+
+#define DECL_MAT(NAME, TYPE, X, Y) \
+ PP_CONCAT(mat_, TYPE) NAME = { \
+ .data = (TYPE[X * Y]){}, \
+ .stride = X, \
+ }
+
+#define DECL_MAT_DATA(NAME, TYPE, X, Y, ...) \
+ PP_CONCAT(mat_, TYPE) NAME = { \
+ .data = (TYPE[X * Y]){__VA_ARGS__}, \
+ .stride = X, \
+ }
+
+#endif
+
+#define SELF_T PP_CONCAT(mat_, MAT_TYPE)
+#define F(NAME) PP_CONCAT(NAME##_, MAT_TYPE)
+
+typedef struct {
+ MAT_TYPE *data;
+ size_t stride;
+} SELF_T;
+
+static inline MAT_TYPE *F(imat)(SELF_T mat, size_t x, size_t y) {
+ assert(x >= 0 && x < mat.stride);
+ assert(y >= 0);
+ return &mat.data[x + y*mat.stride];
+}
+
+#undef SELF_T
+#undef MAT_TYPE
diff --git a/src/parse.c b/src/parse.c
new file mode 100644
index 0000000..6ab2007
--- /dev/null
+++ b/src/parse.c
@@ -0,0 +1,172 @@
+#include "parse.h"
+
+#include <stdbool.h>
+#include <assert.h>
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "log.h"
+
+enum ParsePhase {
+ PHASE_COUNT,
+ PHASE_BUILD,
+};
+
+struct ParseCtx {
+ char * const str;
+ char *cursor;
+ struct Tree *tree;
+ size_t tree_cursor;
+ size_t *chunks;
+
+ enum ParsePhase phase;
+};
+
+static uint64_t max(uint64_t a, uint64_t b) {
+ return a > b ? a : b;
+}
+
+static bool alnum(struct ParseCtx *ctx) {
+ return isalnum(ctx->cursor[0]);
+}
+
+static int read_STag(struct ParseCtx *ctx, bool *self_close, size_t nodeId) {
+ // Record start position of the tag
+ if (ctx->phase == PHASE_BUILD) {
+ ctx->chunks[nodeId] = ctx->cursor - ctx->str;
+ }
+
+ if(*ctx->cursor != '<') return 1;
+ ctx->cursor++;
+
+ while(isalnum(*ctx->cursor) || *ctx->cursor == ' ' || *ctx->cursor == '"' || *ctx->cursor == '=') ctx->cursor++;
+
+ // Check for self-closing tag
+ if(*ctx->cursor == '/') {
+ *self_close = true;
+ ctx->cursor++;
+ }
+
+ if(*ctx->cursor != '>') return 1;
+ ctx->cursor++;
+
+ return 0;
+}
+
+static int read_Element(struct ParseCtx *ctx, size_t nodeId);
+
+static int read_Content(struct ParseCtx *ctx, size_t nodeId) {
+ int err;
+ uint64_t children = 0;
+ while(true) {
+ if(ctx->cursor[0] == '<' && ctx->cursor[1] != '/') {
+ size_t childId = ctx->tree_cursor++;
+
+ err = read_Element(ctx, childId);
+ if(err != 0) return err;
+
+ if(ctx->phase == PHASE_BUILD)
+ *imat_nid(ctx->tree->adj, children, nodeId) = childId+1;
+
+ children++;
+ } else if(alnum(ctx)) {
+ ctx->cursor++;
+ } else {
+ break;
+ }
+ }
+
+ if(ctx->phase == PHASE_COUNT)
+ ctx->tree->adj.stride = max(ctx->tree->adj.stride, children);
+
+ if(ctx->phase == PHASE_BUILD) {
+ for(size_t i = children; i < ctx->tree->adj.stride; i++) {
+ *imat_nid(ctx->tree->adj, i, nodeId) = 0;
+ }
+ }
+
+ return 0;
+}
+
+static int read_ETag(struct ParseCtx *ctx) {
+ if(*ctx->cursor != '<') return 1;
+ ctx->cursor++;
+
+ if(*ctx->cursor != '/') return 1;
+ ctx->cursor++;
+
+ while(isalnum(*ctx->cursor)) ctx->cursor++;
+
+ if(*ctx->cursor != '>') return 1;
+ ctx->cursor++;
+
+ return 0;
+}
+
+static int read_Element(struct ParseCtx *ctx, size_t nodeId) {
+ int err;
+ bool self_close = false;
+
+ err = read_STag(ctx, &self_close, nodeId);
+ if(err != 0) return err;
+
+ if(!self_close) {
+ err = read_Content(ctx, nodeId);
+ if(err != 0) return err;
+ err = read_ETag(ctx);
+ if(err != 0) return err;
+ } else if(ctx->phase == PHASE_BUILD) {
+ for(size_t i = 0; i < ctx->tree->adj.stride; i++)
+ *imat_nid(ctx->tree->adj, i, nodeId) = 0;
+ }
+
+ if(ctx->phase == PHASE_COUNT) ctx->tree->len++;
+ return 0;
+}
+
+// This follows a 2 phase approach. First we size out the tree to figure out how
+// much data we are going to store. Then we allocate the space based on that
+// count pass before then doing a second pass in the BUILD phase which fill in
+// those data structures.
+int parse_string(char *str, struct Tree *tree, size_t **chunks) {
+ assert(chunks != NULL); // Chunks parameter is required
+
+ tree->adj.stride = 1;
+ tree->len = 0;
+ struct ParseCtx ctx = {
+ .str = str,
+ .cursor = str,
+ .tree = tree,
+ .tree_cursor = 1,
+ .phase = PHASE_COUNT,
+ };
+ int err;
+
+ err = read_Element(&ctx, 0);
+ if(err != 0) {
+ log("Parse error at %ld", ctx.cursor - ctx.str);
+ return err;
+ }
+
+ tree->adj.data = malloc(tree->len * tree->adj.stride * sizeof(*tree->adj.data));
+
+ // Allocate memory for chunks
+ *chunks = malloc(tree->len * sizeof(size_t));
+ if (*chunks == NULL) {
+ free(tree->adj.data);
+ return 1;
+ }
+
+ // Reset the context for the next phase
+ ctx.phase = PHASE_BUILD;
+ ctx.cursor = str;
+ ctx.tree_cursor = 1;
+ ctx.chunks = *chunks;
+
+ err = read_Element(&ctx, 0);
+ // The second phase we assume the tree is valid since it passed the first phase
+ assert(err == 0);
+
+ return 0;
+}
diff --git a/src/parse.h b/src/parse.h
new file mode 100644
index 0000000..516b171
--- /dev/null
+++ b/src/parse.h
@@ -0,0 +1,7 @@
+#include "leven.h"
+
+// Chunk offsets for each node in the tree
+// chunks[nodeId] = start position of the tag in the original string
+// The end position is implicitly the start of the next tag or the end of the string
+
+int parse_string(char *str, struct Tree *tree, size_t **chunks);
diff --git a/test/contrained.c b/test/contrained.c
new file mode 100644
index 0000000..1af01a8
--- /dev/null
+++ b/test/contrained.c
@@ -0,0 +1,281 @@
+#include "leven.h"
+
+#include "log.h"
+
+DECL_MAT3(no_trace, uint32_t, 0, 0, 0);
+
+int main(int argc, char **argv) {
+ log("Constrained edit tests");
+
+ {
+ struct Tree a = {
+ .adj = { .data = &(nid){0},
+ .stride = 1,
+ },
+ .len = 1,
+ };
+
+ struct Tree b = {
+ .adj = {
+ .data = &(nid){0},
+ .stride = 1,
+ },
+ .len = 1,
+ };
+
+ DECL_MAT_DATA(cost, uint32_t, 2, 2,
+ 0, 2,
+ 2, 1,
+ );
+ DECL_MAT(cost_n, uint32_t, 2, 2);
+ DECL_MAT(cost_f, uint32_t, 2, 2);
+ DECL_MAT(cost_s, uint32_t, 1, 1);
+
+ constrained_tree_distance(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s
+ );
+
+ if(*imat_uint32_t(cost_n, 1, 1) != 1) {
+ log("Test Fail");
+ return 1;
+ }
+
+ DECL_MAT(alignment, uint32_t, 2, 2);
+ uint32_t adj_alignment[2] = {0, 0};
+ constrained_tree_alignment(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ adj_alignment,
+ alignment
+ );
+ }
+
+ {
+ struct Tree a = {
+ .adj = {
+ .data = (nid[]){2, 0},
+ .stride = 1,
+ },
+ .len = 2,
+ };
+
+ struct Tree b = {
+ .adj = {
+ .data = &(nid){0},
+ .stride = 1,
+ },
+ .len = 1,
+ };
+
+ DECL_MAT_DATA(cost, uint32_t, 3, 2,
+ 0, 1, 2,
+ 2, 1, 1,
+ );
+ DECL_MAT(cost_n, uint32_t, 3, 2);
+ DECL_MAT(cost_f, uint32_t, 3, 2);
+ DECL_MAT(cost_s, uint32_t, 2, 2);
+
+ constrained_tree_distance(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s
+ );
+
+ if(*imat_uint32_t(cost_n, 1, 1) != 2) {
+ log("Test Fail");
+ return 1;
+ }
+
+ DECL_MAT(alignment, uint32_t, 3, 2);
+ uint32_t adj_alignment[2] = {0, 0};
+ constrained_tree_alignment(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ adj_alignment,
+ alignment
+ );
+ }
+
+ {
+ struct Tree a = {
+ .adj = {
+ .data = (nid[]){2, 0},
+ .stride = 1,
+ },
+ .len = 2,
+ };
+
+ struct Tree b = {
+ .adj = {
+ .data = (nid[]){2, 0},
+ .stride = 1,
+ },
+ .len = 2,
+ };
+
+ DECL_MAT_DATA(cost, uint32_t, 3, 3,
+ 0, 2, 2,
+ 2, 0, 2,
+ 2, 2, 0,
+ );
+ DECL_MAT(cost_n, uint32_t, 3, 3);
+ DECL_MAT(cost_f, uint32_t, 3, 3);
+ DECL_MAT(cost_s, uint32_t, 2, 2);
+
+ constrained_tree_distance(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s
+ );
+
+ if(*imat_uint32_t(cost_n, 1, 1) != 0) {
+ log("Test Fail");
+ return 1;
+ }
+
+ DECL_MAT(alignment, uint32_t, 2, 2);
+ uint32_t adj_alignment[2] = {0, 0};
+ constrained_tree_alignment(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ adj_alignment,
+ alignment
+ );
+ }
+
+ {
+ struct Tree a = {
+ .adj = {
+ .data = (nid[]){2, 3, 0, 0, 0, 0},
+ .stride = 2,
+ },
+ .len = 3,
+ };
+
+ struct Tree b = {
+ .adj = {
+ .data = (nid[]){2, 0, 3, 4, 0, 0, 0, 0},
+ .stride = 2,
+ },
+ .len = 4,
+ };
+
+ DECL_MAT_DATA(cost, uint32_t, 4, 5,
+ 2, 2, 2, 2,
+ 2, 2, 2, 2,
+ 2, 0, 2, 2,
+ 2, 2, 0, 2,
+ 2, 2, 2, 0,
+ );
+ DECL_MAT(cost_n, uint32_t, 4, 5);
+ DECL_MAT(cost_f, uint32_t, 4, 5);
+ DECL_MAT(cost_s, uint32_t, 3, 3);
+
+ constrained_tree_distance(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s
+ );
+
+ if(*imat_uint32_t(cost_n, 1, 1) != 2) {
+ log("Test Fail\n");
+ return 1;
+ }
+
+ DECL_MAT(alignment, uint32_t, 2, 2);
+ uint32_t adj_alignment[2] = {0, 0};
+ constrained_tree_alignment(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ adj_alignment,
+ alignment
+ );
+ }
+
+ {
+ struct Tree a = {
+ .adj = {
+ .data = (nid[]){2, 3, 0, 0, 0, 0},
+ .stride = 2,
+ },
+ .len = 3,
+ };
+
+ struct Tree b = {
+ .adj = {
+ .data = (nid[]){2, 3, 0},
+ .stride = 1,
+ },
+ .len = 3,
+ };
+
+ DECL_MAT_DATA(cost, uint32_t, 4, 4,
+ 0, 2, 2, 2,
+ 2, 0, 2, 2,
+ 2, 2, 0, 2,
+ 2, 2, 2, 0,
+ );
+ DECL_MAT(cost_n, uint32_t, 4, 4);
+ DECL_MAT(cost_f, uint32_t, 4, 4);
+ DECL_MAT(cost_s, uint32_t, 3, 2);
+
+ constrained_tree_distance(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s
+ );
+
+ if(*imat_uint32_t(cost_n, 1, 1) != 4) {
+ log("Test Fail\n");
+ return 1;
+ }
+
+ DECL_MAT(alignment, uint32_t, 2, 2);
+ uint32_t adj_alignment[2] = {0, 0};
+ constrained_tree_alignment(
+ a,
+ b,
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ adj_alignment,
+ alignment
+ );
+ }
+
+ return 0;
+}
diff --git a/test/leven.c b/test/leven.c
new file mode 100644
index 0000000..500d7d1
--- /dev/null
+++ b/test/leven.c
@@ -0,0 +1,109 @@
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "leven.h"
+#include "log.h"
+
+DECL_MAT(weight, uint32_t, 256, 256);
+
+static void simple_distance() {
+ for(uint32_t i = 0; i < 256 * 256; i++) {
+ weight.data[i] = 2;
+ }
+
+ for(uint32_t i = 1; i < 256; i++) {
+ // The identity values
+ *imat_uint32_t(weight, i, i) = 0;
+
+ // Adding a character
+ *imat_uint32_t(weight, i, 0) = 1;
+ // Removing a character
+ *imat_uint32_t(weight, 0, i) = 1;
+ }
+}
+
+static size_t nidlen(nid *a) {
+ size_t l = 0;
+ while(a[l] != 0) l++;
+ return l;
+}
+
+static uint32_t* run_leven(nid *a, nid *b) {
+ size_t la = nidlen(a);
+ size_t lb = nidlen(b);
+
+ mat_uint32_t dist = {
+ .data = malloc((la+1) * (lb+1) * sizeof(uint32_t)),
+ .stride = la+1,
+ };
+ uint32_t *alignment = malloc(lb * sizeof(uint32_t));
+
+ string_edit_distance(a, la, b, lb, weight, dist);
+ string_edit_alignment(a, la, b, lb, weight, dist, alignment);
+
+ free(dist.data);
+ return alignment;
+}
+
+int main(int argc, char **argv) {
+
+ log("Levenshtein tests");
+
+ // Initialize the weight with simple weights
+ simple_distance();
+ {
+ uint32_t* alignment = run_leven((nid[]){1, 0}, (nid[]){2, 0});
+ uint32_t expected[] = {
+ 0,
+ };
+ if(memcmp(alignment, expected, sizeof(expected)/sizeof(*expected)) != 0) {
+ return 1;
+ }
+ free(alignment);
+ }
+
+ {
+ uint32_t* alignment = run_leven((nid[]){1, 0}, (nid[]){2, 1, 0});
+ uint32_t expected[] = {
+ -1, 0,
+ };
+ if(memcmp(alignment, expected, sizeof(expected)/sizeof(*expected)) != 0) {
+ return 1;
+ }
+ free(alignment);
+ }
+
+ {
+ uint32_t* alignment = run_leven((nid[]){1, 2, 3, 3, 4, 5, 0}, (nid[]){7, 3, 3, 4, 5, 3, 8, 5, 0});
+ logb("Alignment: ");
+ for(size_t i = 0; i < 8; i++) {
+ logc("%d ", alignment[i]);
+ }
+ loge();
+ uint32_t expected[] = {
+ 1, 2, 3, 4, -1, -1, -1, 5,
+ };
+ if(memcmp(alignment, expected, sizeof(expected)) != 0) {
+ return 1;
+ }
+ free(alignment);
+ }
+
+ // Turning an 1 into 2 now costs 3
+ *imat_uint32_t(weight, 1, 2) = 3;
+ {
+ uint32_t* alignment = run_leven((nid[]){1, 0}, (nid[]){2, 0});
+ // So it prefers to remove the a an add a b
+ uint32_t expected[] = {
+ -1,
+ };
+ if(memcmp(alignment, expected, sizeof(expected)/sizeof(*expected)) != 0) {
+ return 1;
+ }
+ free(alignment);
+ }
+ // Reset the cost of 1 into 2
+ *imat_uint32_t(weight, 1, 2) = 2;
+}
diff --git a/test/parse.c b/test/parse.c
new file mode 100644
index 0000000..07dbbfa
--- /dev/null
+++ b/test/parse.c
@@ -0,0 +1,114 @@
+#include "parse.h"
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "log.h"
+
+#define fail() fail_impl(__LINE__);
+
+int fail_impl(int line) {
+ log("%d: Test fail!\n", line);
+ return 1;
+}
+
+int main(int argc, char **argv) {
+ printf("Parser Tests\n");
+
+ {
+ struct Tree a;
+ size_t *chunks = NULL;
+ if(parse_string("<root></root>", &a, &chunks) != 0) return fail();
+ if(a.adj.stride != 1) return fail();
+ if(a.len != 1) return fail();
+ nid expected[] = {
+ 0,
+ };
+ if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+
+ // Verify chunk offsets
+ if(chunks[0] != 0) return fail();
+
+ free(chunks);
+ free(a.adj.data);
+ }
+
+ {
+ struct Tree a;
+ size_t *chunks = NULL;
+ if(parse_string("<root><a></a><b></b></root>", &a, &chunks) != 0) return fail();
+ if(a.adj.stride != 2) return fail();
+ if(a.len != 3) return fail();
+ nid expected[] = {
+ 2, 3,
+ 0, 0,
+ 0, 0,
+ };
+ if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+
+ // Verify chunk offsets
+ if(chunks[0] != 0) return fail();
+ if(chunks[1] != 6) return fail();
+ if(chunks[2] != 13) return fail();
+
+ free(chunks);
+ free(a.adj.data);
+ }
+
+ {
+ struct Tree a;
+ size_t *chunks = NULL;
+ if(parse_string("<root><a><c></c></a><b></b></root>", &a, &chunks) != 0) return fail();
+ if(a.adj.stride != 2) return fail();
+ if(a.len != 4) return fail();
+ nid expected[] = {
+ 2, 4,
+ 3, 0,
+ 0, 0,
+ 0, 0,
+ };
+ if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+
+ // Verify chunk offsets
+ if(chunks[0] != 0) return fail();
+ if(chunks[1] != 6) return fail();
+ if(chunks[2] != 9) return fail();
+ if(chunks[3] != 20) return fail();
+
+ free(chunks);
+ free(a.adj.data);
+ }
+
+ // We forgot to close the open tag
+ {
+ struct Tree a;
+ size_t *chunks = NULL;
+ fflush(stdout);
+ if(parse_string("<root</root>", &a, &chunks) != 1) return fail();
+ fflush(stdout);
+ }
+
+ // Test self-closing tag
+ {
+ struct Tree a;
+ size_t *chunks = NULL;
+ fflush(stdout);
+ if(parse_string("<root><a /></root>", &a, &chunks) != 0) return fail();
+ if(a.adj.stride != 1) return fail();
+ if(a.len != 2) return fail();
+ nid expected[] = {
+ 2,
+ 0,
+ };
+ if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+
+ // Verify chunk offsets
+ if(chunks[0] != 0) return fail();
+ if(chunks[1] != 6) return fail();
+
+ free(chunks);
+ free(a.adj.data);
+ }
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-03 18:16:14 +0000