From b8dddc0f7dda0c7daaca4076218e84982916abeb Mon Sep 17 00:00:00 2001 From: mar77i Date: Mon, 18 Nov 2024 17:08:51 +0100 Subject: [PATCH] initial commit --- .gitignore | 2 + Makefile | 11 +++ global.mk | 35 ++++++++++ growable.c | 40 +++++++++++ growable.h | 22 ++++++ parser.c | 114 ++++++++++++++++++++++++++++++ parser.h | 9 +++ runtime.c | 194 +++++++++++++++++++++++++++++++++++++++++++++++++++ runtime.h | 13 ++++ shitscript.c | 68 ++++++++++++++++++ shitscript.h | 36 ++++++++++ 11 files changed, 544 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 global.mk create mode 100644 growable.c create mode 100644 growable.h create mode 100644 parser.c create mode 100644 parser.h create mode 100644 runtime.c create mode 100644 runtime.h create mode 100644 shitscript.c create mode 100644 shitscript.h diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..df58ea5 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +*.o +shitscript diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..75f67d3 --- /dev/null +++ b/Makefile @@ -0,0 +1,11 @@ + +CFLAGS += -D_DEFAULT_SOURCE $(DEV_CFLAGS) +LDFLAGS += $(DEV_LDFLAGS) + +all: shitscript + +shitscript: shitscript.o growable.o parser.o runtime.o + +include global.mk + +.PHONY: all diff --git a/global.mk b/global.mk new file mode 100644 index 0000000..92175d8 --- /dev/null +++ b/global.mk @@ -0,0 +1,35 @@ + +# global.mk +# +# Copyright (c) 2017, mar77i +# +# This software may be modified and distributed under the terms +# of the ISC license. See the LICENSE file for details. + +# useful compiler flags; thanks xavier roche @ httrack blog + +CFLAGS += -std=c99 -pipe -fvisibility=hidden -Wall -Wextra -Wformat \ + -Wformat-security -Wreturn-type -Wpointer-arith -Winit-self \ + -Wsign-compare -Wmultichar -Wuninitialized -Werror -funroll-loops \ + -funswitch-loops -pedantic + +SHARED_CFLAGS = -fPIC -fvisibility=default + +LDFLAGS += -Wl,-z,relro,-z,now,-O1,--as-needed,--no-undefined \ + -Wl,--build-id=sha1,--no-allow-shlib-undefined -rdynamic + +VALGRIND_FLAGS = --trace-children=yes --leak-check=full --track-origins=yes \ + --show-leak-kinds=all + +LINK = $(CC) $(LDFLAGS) $> $^ $(LOADLIBES) $(LDLIBS) $(LDADD) -o $@ +LINK_SHARED = \ + $(CC) $(LDFLAGS) $> $^ $(LOADLIBES) $(LDLIBS) $(LDADD) -shared -o $@ + +vg: + valgrind $(VALGRIND_FLAGS) $(ARGS) + +DEV_CFLAGS = -Og -g +PROD_CFLAGS = -O3 +PROD_LDFLAGS = -Wl,--discard-all + +.PHONY: vg diff --git a/growable.c b/growable.c new file mode 100644 index 0000000..3a0decf --- /dev/null +++ b/growable.c @@ -0,0 +1,40 @@ + +// growable.c + +#include + +#include "growable.h" + +#define ROUND_UP_TO_POW2(v) do { \ + v--; \ + v |= v >> 1; \ + v |= v >> 2; \ + v |= v >> 4; \ + v |= v >> 8; \ + v |= v >> 16; \ + v |= v >> 32; \ + v++; \ +} while(0) + +int growable_grow(struct growable *g, size_t len) { + void *np; + if (len < g->allo) + return 0; + if (g->allo == 0) + g->allo = 8; + else { + ROUND_UP_TO_POW2(len); + g->allo = len; + } + np = realloc(g->data, g->allo * g->item_size); + if (np == NULL) { + perror("realloc"); + return -1; + } + g->data = np; + return 0; +} + +void growable_cleanup(struct growable *g) { + free(g->data); +} diff --git a/growable.h b/growable.h new file mode 100644 index 0000000..b5e9f89 --- /dev/null +++ b/growable.h @@ -0,0 +1,22 @@ + +// growable.h + +#ifndef GROWABLE_H +#define GROWABLE_H + +#include + +struct growable { + size_t item_size, len, allo; + void *data; +}; + +#define EMPTY_GROWABLE(is) \ + ((struct growable){ .item_size = (is), .len = 0, .allo = 0, .data = NULL }) + +int growable_grow(struct growable *g, size_t len); +void growable_cleanup(struct growable *g); + +#define GROWABLE_AT(g, t, i) ((t*)(g).data)[i] + +#endif // GROWABLE_H diff --git a/parser.c b/parser.c new file mode 100644 index 0000000..a0fe82f --- /dev/null +++ b/parser.c @@ -0,0 +1,114 @@ + +// parser.c + +#include +#include +#include + +#include "growable.h" +#include "shitscript.h" +#include "parser.h" + +static inline int read_number(struct ast_item *ai) { + int c; + intmax_t new_value; + while (isdigit(c = getc(stdin))) { + new_value = ai->u.i * 10 + c - '0'; + if (new_value / 10 != ai->u.i) { + fprintf(stderr, "Error: Overflow.\n"); + return -1; + } + ai->u.i = new_value; + } + ungetc(c, stdin); + return 0; +} + +static inline int read_ident_or_keyword(int c, struct ast_item *ai) { + struct growable s = EMPTY_GROWABLE(1); + do { + if (growable_grow(&s, s.len + 1) < 0) + return -1; + ((char*)s.data)[s.len++] = c; + c = getc(stdin); + } while (isalnum(c) || c == '_'); + ungetc(c, stdin); + if (growable_grow(&s, s.len + 1) < 0) + return -1; + ((char*)s.data)[s.len++] = '\0'; + if (strcasecmp(s.data, "goto") == 0) { + ai->type = AST_ITEM_GOTO; + growable_cleanup(&s); + return 0; + } + ai->type = AST_ITEM_IDENT; + ai->u.s = s.data; + return 0; +} + +int parse_input(struct growable *ast_items, struct growable *markers) { + int c; + struct ast_item ai; + while ((c = getc(stdin)) != EOF) { + memset(&ai.u, 0, sizeof ai.u); + switch (c) { + case '+': + ai.type = AST_ITEM_PLUS; + goto add_item; + case '-': + ai.type = AST_ITEM_MINUS; + goto add_item; + case '=': + ai.type = AST_ITEM_ASSIGN; + goto add_item; + case ';': + ai.type = AST_ITEM_SEMICOLON; + goto add_item; + case ':': + if (ast_items->len == 0 || ( + (struct ast_item*)ast_items->data + )[ast_items->len - 1].type != AST_ITEM_IDENT) { + fprintf(stderr, "Error: Identifier expected before ':'\n"); + return -1; + } + if (growable_grow(markers, markers->len + 1) < 0) + return -1; + GROWABLE_AT( + *markers, struct ast_marker, markers->len++ + ) = (struct ast_marker){ + GROWABLE_AT(*ast_items, struct ast_item, --ast_items->len).u.s, + ast_items->len, + }; + continue; + case '*': + ai.type = AST_ITEM_MULTIPLY; + goto add_item; + case '/': + ai.type = AST_ITEM_DIVIDE; + goto add_item; + } + if (isdigit(c)) { + ai.type = AST_ITEM_INT; + ai.u.i = c - '0'; + if (read_number(&ai) < 0) + return -1; + goto add_item; + } else if (isalpha(c) || c == '_') { + if (read_ident_or_keyword(c, &ai) < 0) + return -1; + goto add_item; + } else if (isspace(c)) + continue; + fprintf(stderr, "Error: invalid input: '%c' (0x%02x)\n", c, c & 0xff); + return -1; +add_item: + if (growable_grow(ast_items, ast_items->len + 1) < 0) + return -1; + memcpy(&((struct ast_item*)ast_items->data)[ast_items->len++], &ai, sizeof ai); + } + if (ferror(stdin)) { + fprintf(stderr, "Error: read error.\n"); + return -1; + } + return 0; +} diff --git a/parser.h b/parser.h new file mode 100644 index 0000000..c1d4806 --- /dev/null +++ b/parser.h @@ -0,0 +1,9 @@ + +// parser.h + +#ifndef PARSER_H +#define PARSER_H + +int parse_input(struct growable *ast_items, struct growable *markers); + +#endif // PARSER_H diff --git a/runtime.c b/runtime.c new file mode 100644 index 0000000..17fd532 --- /dev/null +++ b/runtime.c @@ -0,0 +1,194 @@ + +// runtime.c + +#include +#include + +#include "growable.h" +#include "runtime.h" + +struct scope_value { + enum value_type { + VALUE_TYPE_INT, + } type; + union { + intmax_t i; + } u; +}; + +struct scope_item { + char *name; + struct scope_value value; +}; + +enum evaluate_until { + UNTIL_SEMICOLON, +}; + +static inline int maybe_resolve_int( + struct growable *scope, + struct growable markers, + intmax_t *result, + struct ast_item ai +) { + size_t i; + if (ai.type == AST_ITEM_INT) { + *result = ai.u.i; + return 0; + } else if (ai.type != AST_ITEM_IDENT) { + fprintf(stderr, "Error: expected literal or identifier.\n"); + return -1; + } + for (i = 0; i < scope->len; i++) + if (strcmp(((struct scope_item*)scope->data)[i].name, ai.u.s) == 0) + goto found_in_scope; + for (i = 0; i < markers.len; i++) + if (strcmp(((struct ast_marker*)markers.data)[i].name, ai.u.s) == 0) { + *result = ((struct ast_marker*)markers.data)[i].pos; + return 0; + } + fprintf(stderr, "Error: unknown identifier: '%s'\n", ai.u.s); + return -1; +found_in_scope: + if (((struct scope_item*)scope->data)[i].value.type != VALUE_TYPE_INT) { + fprintf(stderr, "Error: invalid type: '%s'\n", ai.u.s); + return -1; + } + *result = ((struct scope_item*)scope->data)[i].value.u.i; + return 0; +} + +static inline int evaluate_arith( + struct growable ast_items, + size_t *stmt, + enum evaluate_until until, + intmax_t *result, + struct growable *scope, + struct growable markers +) { + intmax_t accu = 0, other = 0; + if (maybe_resolve_int(scope, markers, &accu, ((struct ast_item*)ast_items.data)[*stmt]) < 0) + return -1; + (*stmt)++; + if (until == UNTIL_SEMICOLON && ((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_SEMICOLON) + goto done; + for (;;) { + if (*stmt + 1 >= ast_items.len) { + switch (until) { + case UNTIL_SEMICOLON: + fprintf(stderr, "Error: semicolon expected.\n"); + break; + } + return -1; + } + if (((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_PLUS) { + if (maybe_resolve_int(scope, markers, &other, ((struct ast_item*)ast_items.data)[*stmt + 1]) < 0) + return -1; + (*stmt) += 2; + accu += other; + } else if (((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_MINUS) { + if (maybe_resolve_int(scope, markers, &other, ((struct ast_item*)ast_items.data)[*stmt + 1]) < 0) + return -1; + (*stmt) += 2; + accu -= other; + } else if (((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_MULTIPLY) { + if (maybe_resolve_int(scope, markers, &other, ((struct ast_item*)ast_items.data)[*stmt + 1]) < 0) + return -1; + (*stmt) += 2; + accu *= other; + } else if (((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_DIVIDE) { + if (maybe_resolve_int(scope, markers, &other, ((struct ast_item*)ast_items.data)[*stmt + 1]) < 0) + return -1; + (*stmt) += 2; + accu /= other; + } else { + fprintf(stderr, "Error: unknown operator: "); + ast_item_dump(((struct ast_item*)ast_items.data)[*stmt], stderr); + fputc('\n', stderr); + return -1; + } + if ( + until == UNTIL_SEMICOLON + && ((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_SEMICOLON + ) + goto done; + } +done: + *result = accu; + return 0; +} + +static inline int assign_value( + struct growable *scope, char *name, struct scope_value value +) { + size_t i; + printf("assigning %s value %"PRIdMAX"\n", name, value.u.i); + for (i = 0; i < scope->len; i++) { + if (strcmp(((struct scope_item*)scope->data)[i].name, name) == 0) { + ((struct scope_item*)scope->data)[i].value = value; + return 0; + } + } + if (growable_grow(scope, scope->len + 1) < 0) + return -1; + ((struct scope_item*)scope->data)[scope->len++] = (struct scope_item){ + name, value + }; + return 0; +} + +int evaluate_statement( + const struct growable ast_items, + const struct growable markers, + size_t *stmt, + struct growable *scope +) { + size_t tmp; + struct scope_value value = { .type = VALUE_TYPE_INT }; + if ( + ((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_IDENT + && *stmt + 1 < ast_items.len + && ((struct ast_item*)ast_items.data)[*stmt + 1].type == AST_ITEM_ASSIGN + ) { + tmp = *stmt; + *stmt += 2; + if ( + evaluate_arith( + ast_items, stmt, UNTIL_SEMICOLON, &value.u.i, scope, markers + ) < 0 + ) + return -1; + (*stmt)++; + if (assign_value(scope, ((struct ast_item*)ast_items.data)[tmp].u.s, value) < 0) + return -1; + } else if (((struct ast_item*)ast_items.data)[*stmt].type == AST_ITEM_GOTO) { + (*stmt)++; + if ( + evaluate_arith( + ast_items, stmt, UNTIL_SEMICOLON, &value.u.i, scope, markers + ) < 0 + ) + return -1; + *stmt = value.u.i; + printf("goto %zu\n", *stmt); + } else { + fprintf(stderr, "Error: canot execute: "); + ast_item_dump(((struct ast_item*)ast_items.data)[*stmt], stderr); + fputc('\n', stderr); + return -1; + } + return 0; +} + +int run_ast_items(const struct growable ast_items, const struct growable markers) { + struct growable scope = EMPTY_GROWABLE(sizeof (struct scope_item)); + size_t stmt = 0; + int ret = -1; + while (stmt < ast_items.len) + if (evaluate_statement(ast_items, markers, &stmt, &scope) < 0) + goto error; + ret = 0; +error: + growable_cleanup(&scope); + return ret; +} diff --git a/runtime.h b/runtime.h new file mode 100644 index 0000000..8ee99d8 --- /dev/null +++ b/runtime.h @@ -0,0 +1,13 @@ + +// runtime.h + +#ifndef RUNTIME_H +#define RUNTIME_H + +#include + +#include "shitscript.h" + +int run_ast_items(struct growable ast_items, struct growable markers); + +#endif // RUNTIME_H diff --git a/shitscript.c b/shitscript.c new file mode 100644 index 0000000..212869c --- /dev/null +++ b/shitscript.c @@ -0,0 +1,68 @@ + +// shitscript.c + +#include + +#include "growable.h" +#include "parser.h" +#include "runtime.h" +#include "shitscript.h" + +void ast_item_dump(const struct ast_item ai, FILE *fh) { + switch (ai.type) { + case AST_ITEM_PLUS: + fprintf(fh, "AST_ITEM_PLUS"); + break; + case AST_ITEM_MINUS: + fprintf(fh, "AST_ITEM_MINUS"); + break; + case AST_ITEM_INT: + fprintf(fh, "AST_ITEM_INT %"PRIdMAX, ai.u.i); + break; + case AST_ITEM_ASSIGN: + fprintf(fh, "AST_ITEM_ASSIGN"); + break; + case AST_ITEM_EQUALS: + fprintf(fh, "AST_ITEM_EQUALS"); + break; + case AST_ITEM_IDENT: + fprintf(fh, "AST_ITEM_IDENT \"%s\"", ai.u.s); + break; + case AST_ITEM_SEMICOLON: + fprintf(fh, "AST_ITEM_SEMICOLON"); + break; + case AST_ITEM_MULTIPLY: + fprintf(fh, "AST_ITEM_MULTIPLY"); + break; + case AST_ITEM_DIVIDE: + fprintf(fh, "AST_ITEM_DIVIDE"); + break; + default: + fprintf(fh, "ast_item_type UNKNOWN(%d)", ai.type); + } +} + +void ast_item_cleanup(struct ast_item ai) { + if (ai.type == AST_ITEM_IDENT) + free(ai.u.s); +} + +int main(void) { + size_t i; + struct growable ast_items = EMPTY_GROWABLE(sizeof (struct ast_item)); + struct growable markers = EMPTY_GROWABLE(sizeof (struct ast_marker)); + int ret = EXIT_FAILURE; + if (parse_input(&ast_items, &markers) < 0) + goto error; + if (run_ast_items(ast_items, markers) < 0) + goto error; + ret = EXIT_SUCCESS; +error: + for (i = 0; i < ast_items.len; i++) + ast_item_cleanup(((struct ast_item*)ast_items.data)[i]); + for (i = 0; i < markers.len; i++) + free(((struct ast_marker*)markers.data)[i].name); + growable_cleanup(&ast_items); + growable_cleanup(&markers); + return ret; +} diff --git a/shitscript.h b/shitscript.h new file mode 100644 index 0000000..55f619a --- /dev/null +++ b/shitscript.h @@ -0,0 +1,36 @@ + +// shitscript.h + +#ifndef SHITSCRIPT_H +#define SHITSCRIPT_H + +#include +#include + +struct ast_item { + enum ast_item_type { + AST_ITEM_PLUS, + AST_ITEM_MINUS, + AST_ITEM_INT, + AST_ITEM_ASSIGN, + AST_ITEM_EQUALS, + AST_ITEM_IDENT, + AST_ITEM_SEMICOLON, + AST_ITEM_GOTO, + AST_ITEM_MULTIPLY, + AST_ITEM_DIVIDE, + } type; + union { + intmax_t i; + char *s; + } u; +}; + +struct ast_marker { + char *name; + size_t pos; +}; + +void ast_item_dump(const struct ast_item ai, FILE *fh); + +#endif // SHITSCRIPT_H -- 2.47.0