summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore1
-rw-r--r--cmd/main.c64
-rw-r--r--src/leven.c14
-rw-r--r--src/parse.c10
-rw-r--r--test/parse.c36
5 files changed, 109 insertions, 16 deletions
diff --git a/.gitignore b/.gitignore
index 6117644..f720882 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
compile_commands.json
obj/
/app
+/.cache
diff --git a/cmd/main.c b/cmd/main.c
index 541d646..4e4c42d 100644
--- a/cmd/main.c
+++ b/cmd/main.c
@@ -3,39 +3,70 @@
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
+#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include "leven.h"
#include "parse.h"
+#include "log.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;
+ {
+ int fd = open("/Users/delusional/Documents/xmldiff/file_a.xml", O_RDONLY);
+ int len = lseek(fd, 0, SEEK_END);
+ a = mmap(0, len, PROT_READ, MAP_PRIVATE, fd, 0);
+ }
+
+ char* b;
+ {
+ int fd = open("/Users/delusional/Documents/xmldiff/file_b.xml", O_RDONLY);
+ int len = lseek(fd, 0, SEEK_END);
+ b = mmap(0, len, PROT_READ, MAP_PRIVATE, fd, 0);
+ }
- char* a = "<root><a/><b></b></root>";
- char* b = "<root><a><b/></a></root>";
+ /* char* a = "<root><a/><b></b></root>"; */
+ /* char* b = "<root><a><b/></a></root>"; */
+ log("Parse a");
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);
+ log("Tree a size %ld", a_tree.len);
+ log("Parse b");
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);
+ log("Tree b size %ld", 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,
+ DECL_MAT_DATA(cost, uint32_t, 5, 5,
+ 0, 2, 2, 2, 2,
+ 2, 1, 1, 1, 1,
+ 2, 1, 1, 1, 1,
+ 2, 1, 1, 0, 1,
+ 2, 1, 1, 1, 1
);
+ for(size_t j = 0; j < 4; j++) {
+ size_t b_tag_end = b_chunks[j];
+ while(b[b_tag_end] != '>') b_tag_end++;
+ for(size_t i = 0; i < 4; i++) {
+ size_t a_tag_end = a_chunks[i];
+ while(a[a_tag_end] != '>') a_tag_end++;
+ log("%ld, %ld", i, j);
+
+ size_t a_len = a_tag_end - a_chunks[i];
+ size_t b_len = b_tag_end - b_chunks[j];
+ log("B: %ld, A: %ld", b_len, a_len);
+ log("A: %.*s, B: %.*s", (int)a_len, a + a_chunks[i], (int)b_len, b + b_chunks[j]);
+
+ *imat_uint32_t(cost, i+1, j+1) = !(a_len == b_len && memcmp(a + a_chunks[i], b + b_chunks[j], a_len) == 0) * 1;
+ }
+ }
printf("\n");
for(size_t y = 0; y < b_tree.len; y++) {
for(size_t x = 0; x < b_tree.adj.stride; x++) {
@@ -52,6 +83,15 @@ int main(int argc, char **argv) {
printf("\n");
}
printf("\n");
+
+ logb("2D Array %s [%ldx%d]", "cost", cost.stride, 5);
+ for(uint32_t y = 0; y < 5; y++) {
+ lognl();
+ for(uint32_t x = 0; x < cost.stride; x++) {
+ logc("%03d ", *imat_uint32_t(cost, x, y));
+ }
+ }
+ loge();
/* mat_uint32_t cost = { */
/* .data = malloc(a_tree.len * b_tree.len * sizeof(uint32_t)), */
/* .stride = a_tree.len, */
diff --git a/src/leven.c b/src/leven.c
index 9ed2ab3..f060929 100644
--- a/src/leven.c
+++ b/src/leven.c
@@ -176,8 +176,10 @@ void constrained_tree_alignment (
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,
+ // Scratch space
mat_uint32_t cost_s,
uint32_t *adj_alignment,
+
mat_uint32_t alignment
) {
@@ -198,7 +200,7 @@ void constrained_tree_alignment (
size_t remain = 1;
size_t cursor = j-1;
while(remain > 0) {
- log("ADD %ld", cursor);
+ log("ADD %ld", cursor+1);
size_t adj_len = 0;
while(adj_len < b.adj.stride && *imat_nid(b.adj, adj_len, cursor) != 0) adj_len++;
@@ -212,7 +214,7 @@ void constrained_tree_alignment (
size_t remain = 1;
size_t cursor = i-1;
while(remain > 0) {
- log("REMOVE %ld", cursor);
+ log("REMOVE %ld", cursor+1);
size_t adj_len = 0;
while(adj_len < a.adj.stride && *imat_nid(a.adj, adj_len, cursor) != 0) adj_len++;
@@ -293,6 +295,14 @@ void constrained_tree_alignment (
b_cursor--;
a_cursor--;
}
+
+ while(a_cursor >= 0) {
+ 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--;
+ }
} 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);
diff --git a/src/parse.c b/src/parse.c
index 6ab2007..31a93a6 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -5,6 +5,7 @@
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
+#include <string.h>
#include "log.h"
@@ -31,6 +32,10 @@ static bool alnum(struct ParseCtx *ctx) {
return isalnum(ctx->cursor[0]);
}
+static bool wspace(struct ParseCtx *ctx) {
+ return strchr(" \n\t", ctx->cursor[0]) != NULL;
+}
+
static int read_STag(struct ParseCtx *ctx, bool *self_close, size_t nodeId) {
// Record start position of the tag
if (ctx->phase == PHASE_BUILD) {
@@ -40,7 +45,8 @@ static int read_STag(struct ParseCtx *ctx, bool *self_close, size_t nodeId) {
if(*ctx->cursor != '<') return 1;
ctx->cursor++;
- while(isalnum(*ctx->cursor) || *ctx->cursor == ' ' || *ctx->cursor == '"' || *ctx->cursor == '=') ctx->cursor++;
+ // @COMP Does xml allow all whitespace in the tag?
+ while(alnum(ctx) || *ctx->cursor == ' ' || *ctx->cursor == '"' || *ctx->cursor == '=') ctx->cursor++;
// Check for self-closing tag
if(*ctx->cursor == '/') {
@@ -70,7 +76,7 @@ static int read_Content(struct ParseCtx *ctx, size_t nodeId) {
*imat_nid(ctx->tree->adj, children, nodeId) = childId+1;
children++;
- } else if(alnum(ctx)) {
+ } else if(alnum(ctx) || wspace(ctx)) {
ctx->cursor++;
} else {
break;
diff --git a/test/parse.c b/test/parse.c
index 07dbbfa..328bfd3 100644
--- a/test/parse.c
+++ b/test/parse.c
@@ -36,6 +36,42 @@ int main(int argc, char **argv) {
{
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>\n</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();
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-03 18:17:04 +0000