commit 44aaa0b9491720601ab0e600badec6a04b66941e
parent 610c76f97cbccfd503c0b74882b5eabf1279517f
Author: Juan F. Meleiro <juan@juanmeleiro.mat.br>
Date: Thu, 11 Apr 2024 16:52:12 -0300
Add gardener module
Diffstat:
16 files changed, 681 insertions(+), 76 deletions(-)
diff --git a/coding/assoc.c b/coding/assoc.c
@@ -64,6 +64,25 @@ assoc_get(assoc* a, symbol s)
return get(a->cells, s);
}
+size_t
+get_amount_of_keys(assoc* a)
+{
+ size_t amount;
+ struct cell *c;
+ for (amount = 0, c = a->cells; c; c = c->next, amount++);
+ return amount;
+}
+
+symbol*
+get_keys(assoc* a)
+{
+ struct cell *c;
+ size_t i;
+ symbol *res = malloc(sizeof(symbol)*get_amount_of_keys(a));
+ for (i = 0, c = a->cells; c; res[i++] = c->key, c = c->next);
+ return res;
+}
+
void
free_cells(struct cell *c)
{
diff --git a/coding/assoc.h b/coding/assoc.h
@@ -10,3 +10,5 @@ assoc* new_assoc(void);
void* assoc_get(assoc*, symbol);
void assoc_set(assoc*, symbol, void*);
void free_assoc(assoc*);
+size_t get_amount_of_keys(assoc*);
+symbol* get_keys(assoc*);
diff --git a/coding/assoc.test.c b/coding/assoc.test.c
@@ -12,14 +12,66 @@ test_get_after_set_is_id()
assoc *a = new_assoc();
assoc_set(a, k, (void*)123);
- bool res = assoc_get(a, k) == (void*)123;
+ bool res = (assoc_get(a, k) == (void*)123);
free_assoc(a);
return res;
}
+bool
+test_amount_of_keys()
+{
+ symbol k = intern("k");
+ symbol l = intern("l");
+ symbol m = intern("m");
+ assoc *a = new_assoc();
+
+ assoc_set(a, k, (void*)1);
+ assoc_set(a, l, (void*)2);
+ assoc_set(a, m, (void*)3);
+
+ bool res = (get_amount_of_keys(a) == 3);
+
+ free_assoc(a);
+
+ return res;
+}
+
+bool
+test_keys()
+{
+ symbol k = intern("k");
+ symbol l = intern("l");
+ symbol m = intern("m");
+ assoc *a = new_assoc();
+
+ assoc_set(a, k, (void*)1);
+ assoc_set(a, l, (void*)2);
+ assoc_set(a, m, (void*)3);
+
+ symbol *keys = get_keys(a);
+ size_t num_keys = get_amount_of_keys(a);
+
+ bool res = true;
+ for (size_t i = 0; i < num_keys; i++) {
+ res &= (
+ keys[i] == k ||
+ keys[i] == l ||
+ keys[i] == m
+ );
+
+ res &= (assoc_get(a, keys[i]) != NULL);
+ }
+
+ free_assoc(a);
+
+ return res;
+}
+
int
main()
{
assert(test_get_after_set_is_id());
+ assert(test_amount_of_keys());
+ assert(test_keys());
return 0;
}
diff --git a/coding/gardener.c b/coding/gardener.c
@@ -0,0 +1,124 @@
+#include <assert.h>
+
+#include "gardener.h"
+
+#include "stack.h"
+#include "tree.h"
+#include "schema.h"
+
+struct gardener {
+ schema *top;
+ stack *treestack;
+ stack *schemastack;
+ bool error;
+};
+
+/* GETTERS */
+
+schema*
+get_top(gardener *g)
+{
+ return g->top;
+}
+
+tree*
+get_cur_tree(gardener *g)
+{
+ return peek(g->treestack);
+}
+
+schema*
+get_cur_schema(gardener *g)
+{
+ return peek(g->schemastack);
+}
+
+bool
+get_error(gardener *g)
+{
+ return g->error;
+}
+
+/* SETTERS */
+
+void
+set_error(gardener *g)
+{
+ g->error = true;
+}
+
+/* PUBLIC */
+
+gardener*
+new_gardener(schema* s)
+{
+ gardener *g = malloc(sizeof(gardener));
+ g->top = s;
+ g->error = false;
+ g->treestack = new_stack();
+ g->schemastack = new_stack();
+ push(g->schemastack, g->top);
+ return g;
+}
+
+
+void
+fill(gardener* g, symbol key, symbol value)
+{
+ tree *new = new_leaf(value);
+ set_subtree(get_cur_tree(g), key, new);
+}
+
+
+void
+sub(gardener* g, symbol key, symbol constructor)
+{
+
+ schema *cur_schema = get_cur_schema(g);
+ symbol head = get_head(get_cur_tree(g));
+ assert(has_key(cur_schema, head, key));
+ schema *sub_schema = get_subschema(cur_schema, head, key);
+ tree *new = new_node(constructor);
+
+ set_subtree(get_cur_tree(g), key, new);
+ push(g->schemastack, sub_schema);
+ push(g->treestack, new);
+}
+
+
+void
+start(gardener* g, symbol c)
+{
+ assert(is_empty(g->treestack));
+ tree *t = new_node(c);
+ push(g->treestack, t);
+}
+
+
+bool
+done(gardener* g)
+{
+ bool res = check(get_cur_schema(g), get_cur_tree(g));
+
+ if (res) {
+ if (!is_empty(g->treestack))
+ pop(g->treestack);
+ } else {
+ set_error(g);
+ }
+ return res;
+}
+
+/*
+void
+sup(gardener* g, symbol key, symbol constructor)
+{
+ if (at_ground(g)) {
+ tree *sup = new_node(constructor);
+ set(sup, key, get_cur_tree(g));
+ set_cur_tree(g, sup);
+ } else {
+ set_error(g);
+ }
+}
+*/
diff --git a/coding/gardener.c.wip b/coding/gardener.c.wip
@@ -1,64 +0,0 @@
-#include "gardener.h"
-
-#include "tree.h"
-#include "schema.h"
-
-struct gardener {
-};
-
-schema* get_schema (gardener *g);
-void set_schema (gardener *g, schema *s);
-schema* push_schema (gardener *g);
-schema* pop_schema (gardener *g);
-tree* get_tree (gardener *g);
-void set_tree (gardener *g, tree *t);
-tree* pop_tree (gardener *g);
-void push_tree (gardener *g);
-void set_error (gardener *g);
-bool at_ground (gardener *g);
-
-/* PUBLIC */
-
-gardener* new_gardener(schema*);
-
-void
-fill(gardener* g, symbol key, symbol value)
-{
- tree *new = new_leaf(value);
- set(get_cur_tree(g), key, new);
-}
-
-void
-sub(gardener* g, symbol key, symbol constructor)
-{
- tree *new = new_node(constructor);
- set(get_cur_tree(g), key, new);
- push_cur_tree(g);
- push_schema(g, get_subschema(peek_schema(g), key));
- set_cur_tree(g, new);
-}
-
-bool
-done(gardener* g)
-{
- schema *s = pop_schema(g);
- if (check(s, get_cur_tree(g))) {
- set_error(g);
- return false;
- } else {
- set_cur_tree(g, pop_tree(g));
- }
-}
-
-void
-sup(gardener* g, symbol key, symbol constructor)
-{
- if (at_ground(g)) {
- tree *sup = new_node(constructor);
- set(sup, key, get_cur_tree(g));
- set_cur_tree(g, sup);
- } else {
- set_error(g);
- }
-}
-
diff --git a/coding/gardener.h b/coding/gardener.h
@@ -4,8 +4,10 @@
typedef struct gardener gardener;
gardener* new_gardener(schema*);
+bool get_error(gardener*);
void fill(gardener*, symbol key, symbol value);
void sub(gardener*, symbol key, symbol constructor);
bool done(gardener*);
void sup(gardener*, symbol key, symbol constructor);
+void start(gardener*, symbol constructor);
diff --git a/coding/gardener.test.c b/coding/gardener.test.c
@@ -0,0 +1,158 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#include "symbol.h"
+#include "schema.h"
+#include "gardener.h"
+
+bool
+test_empty_constructor_success(void)
+{
+ bool res = true;
+
+ symbol c = intern("c");
+ schema *s = new_schema();
+ add_constructor(s, c);
+
+ gardener *g = new_gardener(s);
+ start(g, c);
+
+ res &= done(g);
+ res &= !get_error(g);
+
+ return res;
+}
+
+bool
+test_empty_constructor_empty_tree_fail(void)
+{
+ bool res = true;
+
+ symbol c = intern("c");
+ schema *s = new_schema();
+ add_constructor(s, c);
+ gardener *g = new_gardener(s);
+
+ res &= !done(g);
+ res &= get_error(g);
+ return res;
+}
+
+bool
+test_double_deep_schema_fail(void)
+{
+ bool res = true;
+
+ schema *s = new_schema();
+ symbol c = intern("c");
+ add_constructor(s, c);
+
+ schema *t = new_schema();
+ symbol d = intern("d");
+ add_constructor(t, d);
+
+ symbol k = intern("k");
+ assign_subschema(s, c, k, t);
+
+ gardener *g = new_gardener(s);
+ start(g, c);
+
+ res &= !done(g);
+ res &= get_error(g);
+
+ return res;
+}
+
+bool
+test_double_deep_schema_success(void)
+{
+ bool res = true;
+
+ symbol c = intern("c");
+ symbol d = intern("d");
+ symbol k = intern("k");
+
+ schema *s = new_schema();
+ add_constructor(s, c);
+
+ schema *t = new_schema();
+ add_constructor(t, d);
+
+ assign_subschema(s, c, k, t);
+
+ gardener *g = new_gardener(s);
+ start(g, c);
+ sub(g, k, d);
+
+ res &= done(g);
+ res &= !get_error(g);
+
+ return res;
+}
+
+bool
+test_triple_deep_schema_fail(void)
+{
+ bool res = true;
+
+ symbol c = intern("c");
+ symbol d = intern("d");
+ symbol k = intern("k");
+
+ schema *s = new_schema();
+ add_constructor(s, c);
+
+ schema *t = new_schema();
+ add_constructor(t, d);
+
+ assign_subschema(s, c, k, t);
+ assign_subschema(t, d, k, LEAF);
+
+ gardener *g = new_gardener(s);
+ start(g, c);
+ sub(g, k, d);
+
+ res &= !done(g);
+ res &= get_error(g);
+
+ return res;
+}
+
+bool
+test_triple_deep_schema_success(void)
+{
+ bool res = true;
+
+ schema *s = new_schema();
+ symbol c = intern("c");
+ add_constructor(s, c);
+
+ schema *t = new_schema();
+ symbol d = intern("d");
+ add_constructor(t, d);
+
+ symbol k = intern("k");
+ assign_subschema(s, c, k, t);
+ assign_subschema(t, d, k, LEAF);
+
+ gardener *g = new_gardener(s);
+ start(g, c);
+ sub(g, k, d);
+ fill(g, k, k);
+ res &= done(g);
+ res &= !get_error(g);
+
+ return res;
+}
+
+int main()
+{
+ assert(test_empty_constructor_success());
+ assert(test_empty_constructor_empty_tree_fail());
+ assert(test_double_deep_schema_fail());
+ assert(test_double_deep_schema_success());
+ assert(test_triple_deep_schema_fail());
+ assert(test_triple_deep_schema_success());
+ return 0;
+}
diff --git a/coding/schema.c b/coding/schema.c
@@ -0,0 +1,143 @@
+#include <assert.h>
+#include <stdio.h>
+
+#include "schema.h"
+
+#include "assoc.h"
+
+struct schema {
+ assoc *constructors;
+ bool (*checker)(tree*);
+};
+
+struct constructor {
+ assoc *subschemas;
+};
+
+typedef struct constructor constructor;
+
+/* CONSTRUCTORS */
+
+schema*
+new_schema(void)
+{
+ schema *s = malloc(sizeof(schema));
+ s->constructors = new_assoc();
+ s->checker = NULL;
+ return s;
+}
+
+struct schema _LEAF = { NULL };
+struct schema *LEAF = &_LEAF;
+
+constructor*
+new_constructor()
+{
+ constructor *c = malloc(sizeof(constructor));
+ c->subschemas = new_assoc();
+ return c;
+}
+
+
+/* GETTERS AND SETTERS */
+
+bool
+is_constructor(schema* s, symbol c)
+{
+ return assoc_get(s->constructors, c) != NULL;
+}
+
+constructor*
+get_constructor(schema* s, symbol c)
+{
+ assert(is_constructor(s, c));
+ return (constructor*) assoc_get(s->constructors, c);
+}
+
+schema*
+get_subschema(schema* s, symbol c, symbol k)
+{
+ assert(is_constructor(s, c));
+ return (schema*) assoc_get(get_constructor(s, c)->subschemas, k);
+}
+
+bool
+has_key(schema *s, symbol c, symbol k)
+{
+ assert(is_constructor(s, c));
+ return (assoc_get(get_constructor(s, c)->subschemas, k) != NULL);
+}
+
+bool
+takes_leaf(schema *s, symbol c, symbol k)
+{
+ assert(is_constructor(s, c));
+ return (assoc_get(get_constructor(s, c)->subschemas, k) == LEAF);
+}
+
+void
+set_check_function(schema* s, bool (*f)(tree*))
+{
+ s->checker = f;
+}
+
+bool (*get_check_function(schema* s))(tree*)
+{
+ return s->checker;
+}
+
+/* REST OF INTERFACE */
+
+void
+add_constructor(schema* s, symbol c)
+{
+ assert(!is_constructor(s, c));
+ constructor *sub = new_constructor();
+ assoc_set(s->constructors, c, sub);
+}
+
+void
+assign_subschema(schema* s, symbol c, symbol k, schema* sub)
+{
+ assert(is_constructor(s, c));
+ assoc_set(get_constructor(s, c)->subschemas, k, sub);
+}
+
+void
+mark_as_leaf(schema* s, symbol c, symbol k)
+{
+ assert(is_constructor(s, c));
+ assoc_set(get_constructor(s, c)->subschemas, k, LEAF);
+}
+
+bool
+check(schema* s, tree* t)
+{
+ if (!s) return true;
+ if (!t) return false;
+ if (s == LEAF && is_leaf(t)) return true;
+
+ bool good = true;
+ symbol head = get_head(t);
+
+ size_t lim = get_amount_of_keys(get_constructor(s, head)->subschemas);
+ symbol *keys = get_keys(get_constructor(s, head)->subschemas);
+
+ for (size_t i = 0; i < lim && good; i++) {
+ tree *subtree = get_subtree(t, keys[i]);
+ schema *subschema = get_subschema(s, head, keys[i]);
+ assert(subschema != NULL);
+
+ if (subtree)
+ good &= (check(subschema, get_subtree(t, keys[i])));
+ else
+ return false;
+ }
+
+ bool (*checker)(tree*) = get_check_function(s);
+ if (checker) good &= checker(t);
+
+ return good;
+}
+
+
diff --git a/coding/schema.h b/coding/schema.h
@@ -5,6 +5,23 @@
typedef struct schema schema;
+/* BUILDING */
schema* new_schema(void);
-schema* get_subschema(schema*, symbol);
+void add_constructor(schema*, symbol);
+void assign_subschema(schema*, symbol, symbol, schema*);
+void mark_as_leaf(schema*, symbol, symbol);
+void set_check_function(schema*, bool (*)(tree*));
+
+/* USING */
+schema* get_subschema(schema*, symbol, symbol);
+bool has_key(schema*, symbol, symbol);
+bool takes_leaf(schema*, symbol, symbol);
bool check(schema*, tree*);
+
+extern struct schema *LEAF;
+
+/* Guarantees:
+ - assign_subschema, get_subschema => id
+ Test:
+ - check tree
+ */
diff --git a/coding/schema.test.c b/coding/schema.test.c
@@ -0,0 +1,54 @@
+#include <stdbool.h>
+#include <assert.h>
+
+#include "schema.h"
+
+#include "symbol.h"
+#include "assoc.h"
+
+bool
+test_set_and_get_subschema(void)
+{
+ schema *s = new_schema();
+ schema *sub = new_schema();
+ symbol c = intern("c");
+ symbol a = intern("a");
+
+ add_constructor(s, c);
+ assign_subschema(s, c, a, sub);
+
+ return (get_subschema(s, c, a) == sub);
+}
+
+bool
+test_set_and_query_leaf(void)
+{
+ schema *s = new_schema();
+ symbol c = intern("c");
+ symbol a = intern("a");
+
+ add_constructor(s, c);
+ mark_as_leaf(s, c, a);
+
+ return takes_leaf(s, c, a);
+}
+
+bool
+test_leaf_exists(void)
+{
+ assert(LEAF != NULL);
+}
+
+bool
+test_check(void)
+{
+}
+
+int
+main()
+{
+ assert(test_set_and_get_subschema());
+ assert(test_set_and_query_leaf());
+ assert(test_leaf_exists());
+ return 0;
+}
diff --git a/coding/stack.c b/coding/stack.c
@@ -0,0 +1,50 @@
+#include <stdlib.h>
+#include <assert.h>
+
+#include "stack.h"
+
+struct stack {
+ size_t len;
+ size_t cap;
+ void **items;
+};
+
+stack*
+new_stack(void)
+{
+ stack *s = malloc(sizeof(stack));
+ s->len = 0;
+ s->cap = 1;
+ s->items = malloc(s->cap*sizeof(void*));
+ return s;
+}
+
+void
+push(stack* s, void* p)
+{
+ if (s->len == s->cap)
+ s->items = realloc(s->items, sizeof(void*) * (s->cap *= 2));
+ assert(s->items);
+
+ s->items[s->len++] = p;
+}
+
+void* pop(stack* s)
+{
+ return s->items[s->len--];
+}
+
+void*
+peek(stack* s)
+{
+ if (s->len > 0)
+ return s->items[s->len - 1];
+ else
+ return NULL;
+}
+
+bool
+is_empty(stack* s)
+{
+ return (s->len == 0);
+}
diff --git a/coding/stack.h b/coding/stack.h
@@ -0,0 +1,10 @@
+#include <stdbool.h>
+
+typedef struct stack stack;
+
+stack* new_stack(void);
+
+void* pop (stack* );
+void* peek (stack* );
+void push (stack*, void* );
+bool is_empty (stack* );
diff --git a/coding/stack.test.c b/coding/stack.test.c
@@ -0,0 +1,25 @@
+#include <stdbool.h>
+
+#include "stack.h"
+
+bool
+test_push_then_pop()
+{
+ stack *s = new_stack();
+ push(s, (void*)0x1);
+ return (pop(s) == (void*)0x1 && is_empty(s));
+}
+
+bool
+test_push_then_peek()
+{
+ stack *s = new_stack();
+ push(s, (void*)0x1);
+ return (peek(s) == (void*)0x1 && !is_empty(s));
+}
+
+int
+main()
+{
+ return 0;
+}
diff --git a/coding/test.sh b/coding/test.sh
@@ -2,11 +2,14 @@
src=$(ls *.c | grep -v '\.test\.c')
-for f in *.test.c
+for m in symbol assoc stack tree schema gardener
do
+ f=$m.test.c
out=$(basename $f .c)
- cc -fmax-errors=1 $f $src -o $out || exit 1
- ./$out
+ echo "Compiling $f..."
+ cc -g -fmax-errors=1 $f $src -o $out || exit 1
+ echo "Running $f..."
+ ./$out || break
+ rm $out
done
-
-rm *.test
+echo Done.
diff --git a/coding/tree.c b/coding/tree.c
@@ -1,4 +1,6 @@
#include <stdbool.h>
+#include <assert.h>
+
#include "assoc.h"
#include "tree.h"
@@ -46,3 +48,10 @@ get_subtree(tree* t, symbol k)
else
return NULL;
}
+
+symbol
+get_head(tree* t)
+{
+ assert(t != NULL);
+ return t->head;
+}
diff --git a/coding/tree.h b/coding/tree.h
@@ -2,11 +2,12 @@
typedef struct tree tree;
-tree* new_leaf (symbol);
-tree* new_node (symbol);
-void set_subtree (tree*, symbol, tree*);
-tree* get_subtree (tree*, symbol);
-bool is_leaf (tree*);
+tree* new_leaf (symbol);
+tree* new_node (symbol);
+void set_subtree (tree*, symbol, tree*);
+tree* get_subtree (tree*, symbol);
+bool is_leaf (tree*);
+symbol get_head (tree*);
/* Guarantees:
* - set(t, k, v), is_leaf(t) || get(t, k) == v;
