diff options
| -rw-r--r-- | inc/build.h | 4 | ||||
| -rw-r--r-- | inc/parse.h | 1 | ||||
| -rw-r--r-- | inc/print.h | 2 | ||||
| -rw-r--r-- | inc/tree.h | 1 | ||||
| -rw-r--r-- | makefile | 5 | ||||
| -rw-r--r-- | options.ggo | 9 | ||||
| -rw-r--r-- | src/.gitignore | 1 | ||||
| -rw-r--r-- | src/build.c | 84 | ||||
| -rw-r--r-- | src/main.c | 43 | ||||
| -rw-r--r-- | src/parse.c | 12 | ||||
| -rw-r--r-- | src/print.c | 14 | ||||
| -rw-r--r-- | src/tree.c | 94 |
12 files changed, 132 insertions, 138 deletions
diff --git a/inc/build.h b/inc/build.h index fe41e11..4e9d634 100644 --- a/inc/build.h +++ b/inc/build.h @@ -5,8 +5,8 @@ #define BLOC_BUILD_H #include <spec.h> -#include <term.h> +#include <tree.h> -void write_bloc(struct term *term, const char *path); +void write_bloc(struct list *table, const char *path); #endif diff --git a/inc/parse.h b/inc/parse.h index c8cafed..2071f65 100644 --- a/inc/parse.h +++ b/inc/parse.h @@ -12,7 +12,6 @@ struct bloc_parsed { size_t length; struct term **entries; - struct term *term; }; struct term *parse_blc(const char *term); diff --git a/inc/print.h b/inc/print.h index 9885f57..30f67d4 100644 --- a/inc/print.h +++ b/inc/print.h @@ -5,8 +5,10 @@ #define BLOC_PRINT_H #include <term.h> +#include <parse.h> void print_bruijn(struct term *term); void print_blc(struct term *term); +void print_bloc(struct bloc_parsed *bloc); #endif @@ -42,5 +42,6 @@ struct list { }; struct list *tree_merge_duplicates(struct term *term); +void tree_destroy(struct list *table); #endif @@ -22,7 +22,10 @@ ifeq ($(PREFIX),) PREFIX := /usr/local endif -all: compile sync +all: genopts compile sync + +genopts: + @gengetopt -i ${CURDIR}/options.ggo -G --output-dir=$(SRC) compile: $(BUILD) $(OBJS) $(BUILD)/bloc diff --git a/options.ggo b/options.ggo new file mode 100644 index 0000000..ec082f3 --- /dev/null +++ b/options.ggo @@ -0,0 +1,9 @@ +package "BLoC" +version "1.0" +purpose "Tool for converting to/from BLC and BLoC" + +option "input" i "input file" string required +option "output" o "output file" default="out.bloc" string optional +option "from-blc" b "convert from BLC to BLoC" flag on +option "from-bloc" B "convert from BLoC to BLC" flag off +option "dump" d "dump bloc file" dependon="from-bloc" flag off diff --git a/src/.gitignore b/src/.gitignore new file mode 100644 index 0000000..888d678 --- /dev/null +++ b/src/.gitignore @@ -0,0 +1 @@ +cmdline.* diff --git a/src/build.c b/src/build.c index d415c29..7867e31 100644 --- a/src/build.c +++ b/src/build.c @@ -22,95 +22,65 @@ static void write_bit(char val, FILE *file, char *byte, int *bit) (*bit)++; } -static void rec_write_bblc(struct term *term, FILE *file, char *byte, int *bit) +static void rec_write_bblc(struct tree *tree, FILE *file, char *byte, int *bit) { - switch (term->type) { + switch (tree->type) { case ABS: write_bit(0, file, byte, bit); write_bit(0, file, byte, bit); - rec_write_bblc(term->u.abs.term, file, byte, bit); + rec_write_bblc(tree->u.abs.term, file, byte, bit); break; case APP: write_bit(0, file, byte, bit); write_bit(1, file, byte, bit); - rec_write_bblc(term->u.app.lhs, file, byte, bit); - rec_write_bblc(term->u.app.rhs, file, byte, bit); + write_bit(0, file, byte, bit); + rec_write_bblc(tree->u.app.lhs, file, byte, bit); + rec_write_bblc(tree->u.app.rhs, file, byte, bit); break; case VAR: - for (int i = 0; i <= term->u.var.index; i++) + for (int i = 0; i <= tree->u.var.index; i++) write_bit(1, file, byte, bit); write_bit(0, file, byte, bit); break; + case REF: + write_bit(0, file, byte, bit); + write_bit(1, file, byte, bit); + write_bit(1, file, byte, bit); + + // TODO: The bit-order of encoded shorts is kinda arbitrary + short ref = tree->u.ref.index; + for (int i = 0; i < 16; i++) + write_bit((ref >> i) & 1, file, byte, bit); + break; default: - fprintf(stderr, "Invalid type %d\n", term->type); + fprintf(stderr, "invalid type %d\n", tree->type); } } // writes bit-encoded blc into file -static void write_bblc(struct term *term, FILE *file) +static void write_bblc(struct tree *tree, FILE *file) { char byte = 0; int bit = 0; - rec_write_bblc(term, file, &byte, &bit); + rec_write_bblc(tree, file, &byte, &bit); if (bit) // flush final fwrite(&byte, 1, 1, file); } -void write_bloc(struct term *term, const char *path) +void write_bloc(struct list *table, const char *path) { - (void)term; // TODO - - // example data - short length = 2; - struct term *M = parse_blc("0000000001100111100111100111100111011110"); - struct term *N = parse_blc("00000000011001111001111001100111011110"); + short length = table->val; FILE *file = fopen(path, "wb"); fwrite(BLOC_IDENTIFIER, BLOC_IDENTIFIER_LENGTH, 1, file); fwrite(&length, 2, 1, file); - write_bblc(M, file); - write_bblc(N, file); - - // TODO - char byte = 0; - int bit = 0; - write_bit(0, file, &byte, &bit); - write_bit(0, file, &byte, &bit); - write_bit(0, file, &byte, &bit); - write_bit(1, file, &byte, &bit); - write_bit(0, file, &byte, &bit); - write_bit(1, file, &byte, &bit); - write_bit(0, file, &byte, &bit); - write_bit(1, file, &byte, &bit); - write_bit(1, file, &byte, &bit); - - for (int i = 0; i < 16; i++) - write_bit(0, file, &byte, &bit); - - write_bit(0, file, &byte, &bit); - write_bit(0, file, &byte, &bit); - write_bit(1, file, &byte, &bit); - - for (int i = 0; i < 16; i++) - write_bit(0, file, &byte, &bit); - - write_bit(1, file, &byte, &bit); - - for (int i = 0; i < 16; i++) - write_bit(0, file, &byte, &bit); - - write_bit(1, file, &byte, &bit); - - for (int i = 0; i < 16; i++) - write_bit(0, file, &byte, &bit); - - if (bit) // flush final - fwrite(&byte, 1, 1, file); + struct list *iterator = table; + while (iterator) { + write_bblc(iterator->data, file); + iterator = iterator->next; + } fclose(file); - - free_term(M); - free_term(N); } @@ -13,6 +13,9 @@ #include <build.h> #include <free.h> +// automatically generated using gengetopt +#include "cmdline.h" + #define BUF_SIZE 1024 static char *read_stdin(void) { @@ -70,33 +73,39 @@ static char *read_file(const char *path) int main(int argc, char **argv) { - if (argc < 2) { - fprintf(stderr, "Invalid arguments\n"); - return 1; - } + struct gengetopt_args_info args; + if (cmdline_parser(argc, argv, &args)) + exit(1); char *input; - if (argv[1][0] == '-') { + if (args.input_arg[0] == '-') { input = read_stdin(); } else { - input = read_file(argv[1]); + input = read_file(args.input_arg); } if (!input) return 1; - struct term *parsed = parse_blc(input); - print_bruijn(parsed); - - tree_merge_duplicates(parsed); - - /* write_bloc(0, "test.bloc"); */ - /* const char *input = read_file("test.bloc"); */ - /* struct bloc_parsed *bloc = parse_bloc(input); */ - /* struct term *term = from_bloc(bloc); */ - /* print_blc(term); */ + if (args.from_blc_flag && !args.from_bloc_flag) { + struct term *parsed = parse_blc(input); + struct list *table = tree_merge_duplicates(parsed); + write_bloc(table, args.output_arg); + tree_destroy(table); + free_term(parsed); + free(input); + return 0; + } - /* free_term(term); // TODO: Fix sharing user-after-free */ + if (args.from_bloc_flag) { + struct bloc_parsed *bloc = parse_bloc(input); + if (args.dump_flag) + print_bloc(bloc); + printf("%d\n", bloc->length); + // TODO: Write file as BLC + free(input); + free_bloc(bloc); + } return 0; } diff --git a/src/parse.c b/src/parse.c index 5233354..ff01bf0 100644 --- a/src/parse.c +++ b/src/parse.c @@ -56,7 +56,7 @@ static struct term *parse_bloc_bblc(const char *term, size_t *bit) (*bit) += 2; res = new_term(ABS); res->u.abs.term = parse_bloc_bblc(term, bit); - } else if (!BIT_AT(*bit) && BIT_AT(*bit + 1) && !BIT_AT(*bit)) { + } else if (!BIT_AT(*bit) && BIT_AT(*bit + 1) && !BIT_AT(*bit + 2)) { (*bit) += 3; res = new_term(APP); res->u.app.lhs = parse_bloc_bblc(term, bit); @@ -68,14 +68,15 @@ static struct term *parse_bloc_bblc(const char *term, size_t *bit) res = new_term(VAR); res->u.var.index = *bit - cur - 1; (*bit)++; - } else if (!BIT_AT(*bit) && BIT_AT(*bit + 1) && BIT_AT(*bit)) { + } else if (!BIT_AT(*bit) && BIT_AT(*bit + 1) && BIT_AT(*bit + 2)) { (*bit) += 3; res = new_term(REF); short index = 0; - for (int i = 0; i < 16; i++) + for (int i = 0; i < 16; i++) { index |= (BIT_AT(*bit) >> (7 - (*bit % 8))) << i; + (*bit) += 1; + } res->u.ref.index = index; - (*bit) += 16; } else { (*bit)++; res = parse_bloc_bblc(term, bit); @@ -137,5 +138,6 @@ static struct term *rec_bloc(struct term *term, struct bloc_parsed *bloc) struct term *from_bloc(struct bloc_parsed *bloc) { - return rec_bloc(bloc->term, bloc); + struct term *last = bloc->entries[bloc->length - 1]; + return rec_bloc(last, bloc); } diff --git a/src/print.c b/src/print.c index 425aedb..d6636c5 100644 --- a/src/print.c +++ b/src/print.c @@ -49,6 +49,18 @@ void print_blc(struct term *term) printf("0"); break; default: - fprintf(stderr, "Invalid type %d\n", term->type); + fprintf(stderr, "invalid type %d\n", term->type); + } +} + +void print_bloc(struct bloc_parsed *bloc) +{ + printf("\n=== START BLOC ===\n"); + printf("| number of entries: %ld\n", bloc->length); + for (size_t i = 0; i < bloc->length; i++) { + printf("| entry %ld: ", i); + print_bruijn(bloc->entries[i]); + printf("\n"); } + printf("=== END BLOC ===\n\n"); } @@ -157,35 +157,9 @@ static struct tree *build_tree(struct term *term, void **set) free(element); // already exists, not needed (*handle)->list = list_add((*handle)->list, tree); - fprintf(stderr, "found suitable duplicate! %x %d\n", tree->hash, - tree->size); return tree; } -static struct term *tree_to_term(struct tree *tree) -{ - struct term *term = new_term(tree->type); - - switch (tree->type) { - case ABS: - term->u.abs.term = tree_to_term(tree->u.abs.term); - break; - case APP: - term->u.app.lhs = tree_to_term(tree->u.app.lhs); - term->u.app.rhs = tree_to_term(tree->u.app.rhs); - break; - case VAR: - term->u.var.index = tree->u.var.index; - break; - case REF: - term->u.ref.index = tree->u.ref.index; - break; - default: - fprintf(stderr, "invalid type %d\n", term->type); - } - return term; -} - static struct tree *clone_tree_root(struct tree *tree) { struct tree *new = malloc(sizeof(*new)); @@ -230,15 +204,15 @@ static void invalidate_tree(struct tree *tree) } } -static void free_tree(struct tree *tree) +static void free_tree(struct tree *tree, int ref_only) { switch (tree->type) { case ABS: - free_tree(tree->u.abs.term); + free_tree(tree->u.abs.term, ref_only); break; case APP: - free_tree(tree->u.app.lhs); - free_tree(tree->u.app.rhs); + free_tree(tree->u.app.lhs, ref_only); + free_tree(tree->u.app.rhs, ref_only); break; case VAR: break; @@ -249,7 +223,7 @@ static void free_tree(struct tree *tree) return; } - if (FREEABLE_TREE(tree)) + if (!ref_only || (ref_only && FREEABLE_TREE(tree))) free(tree); } @@ -257,11 +231,11 @@ static void ref_invalidated_tree(struct tree *tree) { switch (tree->type) { case ABS: - free_tree(tree->u.abs.term); + free_tree(tree->u.abs.term, 1); break; case APP: - free_tree(tree->u.app.lhs); - free_tree(tree->u.app.rhs); + free_tree(tree->u.app.lhs, 1); + free_tree(tree->u.app.rhs, 1); break; case VAR: break; @@ -276,6 +250,24 @@ static void ref_invalidated_tree(struct tree *tree) } } +static void free_prioritized_list(struct list *list) +{ + struct list *iterator = list; + while (iterator) { + struct list *temp = iterator->next; + + struct list *subiter = iterator->data; + while (subiter) { + struct list *subtemp = subiter->next; + free(subiter); + subiter = subtemp; + } + + free(iterator); + iterator = temp; + } +} + struct list *tree_merge_duplicates(struct term *term) { void *set = 0; @@ -305,11 +297,7 @@ struct list *tree_merge_duplicates(struct term *term) struct list *list = iterator->data; struct tree *head = list->data; - print_bruijn(tree_to_term(head)); - printf("\n%x: %d\n\n", head->hash, list->val); - - if (head->state != VALIDATED_TREE) { - printf("skipping invalidated: %x\n", head->hash); + if (head->state != VALIDATED_TREE) { // skip invalidated iterator = iterator->next; continue; } @@ -334,30 +322,28 @@ struct list *tree_merge_duplicates(struct term *term) iterator = iterator->next; } - printf("\n---\n"); - + // destroy invalidated list and replace reffed subtrees iterator = invalidated; while (iterator) { - struct tree *huh = iterator->data; - printf("%x %d\n", huh->hash, huh->state); - print_bruijn(tree_to_term(huh)); - printf("\n"); ref_invalidated_tree(iterator->data); struct list *temp = iterator->next; free(iterator); iterator = temp; } - printf("\n---\n"); + // destroy prioritized list + free_prioritized_list(prioritized); - iterator = final; + return final; +} + +void tree_destroy(struct list *table) +{ + struct list *iterator = table; while (iterator) { - struct tree *huh = iterator->data; - struct term *foo = tree_to_term(huh); - print_bruijn(foo); - printf("\n%x\n\n", huh->hash); - iterator = iterator->next; + free_tree(iterator->data, 0); + struct list *temp = iterator->next; + free(iterator); + iterator = temp; } - - return final; } |