Yusuf X
MBED port of https://github.com/ys1382/filagree . The only change is adding #define MBED
Revision 0:1a89e28dea91, committed 2012-05-30
- Comitter:
- yusufx
- Date:
- Wed May 30 21:13:01 2012 +0000
- Commit message:
Changed in this revision
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/compile.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,1379 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+#include <ctype.h>
+#include <errno.h>
+
+#include "util.h"
+#include "struct.h"
+#include "serial.h"
+#include "compile.h"
+#include "vm.h"
+#include "variable.h"
+
+#define TAG "compile"
+#define ERROR_LEX "Lexigraphical error"
+#define ERROR_PARSE "Parsological error"
+#define ERROR_TOKEN "Unknown token"
+#define QUOTE '\''
+#define ESCAPE '\\'
+#define ESCAPED_NEWLINE 'n'
+#define ESCAPED_TAB 't'
+#define ESCAPED_QUOTE '\''
+
+uint32_t line;
+struct array* lex_list;
+struct map *imports = NULL;
+struct byte_array *read_file(const struct byte_array *filename);
+
+// token ///////////////////////////////////////////////////////////////////
+
+ enum Lexeme {
+ LEX_NONE,
+ LEX_IMPORT,
+ LEX_LEFT_COMMENT,
+ LEX_RIGHT_COMMENT,
+ LEX_PLUS,
+ LEX_MINUS,
+ LEX_TIMES,
+ LEX_DIVIDE,
+ LEX_MODULO,
+ LEX_AND,
+ LEX_OR,
+ LEX_NOT,
+ LEX_BAND,
+ LEX_BOR,
+ LEX_INVERSE,
+ LEX_XOR,
+ LEX_LSHIFT,
+ LEX_RSHIFT,
+ LEX_GREATER,
+ LEX_LESSER,
+ LEX_SAME,
+ LEX_SET,
+ LEX_DIFFERENT,
+ LEX_COMMA,
+ LEX_PERIOD,
+ LEX_COLON,
+ LEX_LINE_COMMENT,
+ LEX_LEFTHESIS,
+ LEX_RIGHTHESIS,
+ LEX_LEFTSQUARE,
+ LEX_RIGHTSQUARE,
+ LEX_LEFTSTACHE,
+ LEX_RIGHTSTACHE,
+ LEX_IDENTIFIER,
+ LEX_STRING,
+ LEX_INTEGER,
+ LEX_TRUE,
+ LEX_FALSE,
+ LEX_IF,
+ LEX_THEN,
+ LEX_ELSE,
+ LEX_END,
+ LEX_WHILE,
+ LEX_FOR,
+ LEX_IN,
+ LEX_WHERE,
+ LEX_FUNCTION,
+ LEX_RETURN,
+ LEX_TRY,
+ LEX_CATCH,
+ LEX_THROW,
+ LEX_DO,
+ };
+
+struct token {
+ enum Lexeme lexeme;
+ uint32_t number;
+ struct byte_array *string;
+ uint32_t at_line;
+};
+
+struct number_string lexemes[] = {
+ {LEX_IMPORT, "import"},
+ {LEX_LEFT_COMMENT, "/*"},
+ {LEX_RIGHT_COMMENT, "*/"},
+ {LEX_LINE_COMMENT, "#"},
+ {LEX_PLUS, "+"},
+ {LEX_MINUS, "-"},
+ {LEX_TIMES, "*"},
+ {LEX_DIVIDE, "/"},
+ {LEX_MODULO, "%"},
+ {LEX_BAND, "&"},
+ {LEX_BOR, "|"},
+ {LEX_INVERSE, "~"},
+ {LEX_XOR, "^"},
+ {LEX_RSHIFT, ">>"},
+ {LEX_LSHIFT, "<<"},
+ {LEX_AND, "and"},
+ {LEX_OR, "or"},
+ {LEX_NOT, "not"},
+ {LEX_GREATER, ">"},
+ {LEX_LESSER, "<"},
+ {LEX_SAME, "=="},
+ {LEX_SET, "="},
+ {LEX_DIFFERENT, "!="},
+ {LEX_COMMA, ","},
+ {LEX_PERIOD, "."},
+ {LEX_COLON, ":"},
+ {LEX_LEFTHESIS, "("},
+ {LEX_RIGHTHESIS, ")"},
+ {LEX_LEFTSQUARE, "["},
+ {LEX_RIGHTSQUARE, "]"},
+ {LEX_LEFTSTACHE, "{"},
+ {LEX_RIGHTSTACHE, "}"},
+ {LEX_TRUE, "true"},
+ {LEX_FALSE, "false"},
+ {LEX_IF, "if"},
+ {LEX_THEN, "then"},
+ {LEX_ELSE, "else"},
+ {LEX_END, "end"},
+ {LEX_WHILE, "while"},
+ {LEX_FUNCTION, "function"},
+ {LEX_FOR, "for"},
+ {LEX_IN, "in"},
+ {LEX_WHERE, "where"},
+ {LEX_RETURN, "return"},
+ {LEX_TRY, "try"},
+ {LEX_CATCH, "catch"},
+ {LEX_THROW, "throw"},
+ {LEX_DO, "do"}
+};
+
+const char* lexeme_to_string(enum Lexeme lexeme)
+{
+ switch (lexeme) {
+ case LEX_IDENTIFIER: return "id";
+ case LEX_STRING: return "string";
+ case LEX_INTEGER: return "number";
+ default:
+ return NUM_TO_STRING(lexemes, lexeme);
+ }
+}
+
+// display ////////////////////////////////////////////////////////////////////
+
+#ifdef DEBUG
+
+void display_token(struct token *token, int depth) {
+ assert_message(depth < 10, "kablooie!");
+ char* indent = (char*)malloc(sizeof(char)*(depth+1));
+ int i;
+ for (i=0; i<depth; i++)
+ indent[i] = '\t';
+ indent[i] = 0;
+ DEBUGPRINT("%s%d ", indent, token->lexeme);
+
+ switch (token->lexeme) {
+ case LEX_NONE: break;
+ case LEX_INTEGER: DEBUGPRINT("%u", token->number); break;
+ case LEX_STRING:
+ case LEX_IDENTIFIER: {
+ char* s = byte_array_to_string(token->string);
+ DEBUGPRINT("%s:%s", lexeme_to_string(token->lexeme), s);
+ free(s);
+ } break;
+ case LEX_FUNCTION:
+ DEBUGPRINT("fdecl");
+ break;
+ default:
+ DEBUGPRINT("%s", lexeme_to_string(token->lexeme));
+ break;
+ }
+ DEBUGPRINT("\n");
+ free(indent);
+}
+
+void display_lex_list() {
+ int i, n = lex_list->length;
+ for (i=0; i<n; i++) {
+ DEBUGPRINT("\t%d: ", i);
+ display_token((struct token*)array_get(lex_list,i), 0);
+ }
+}
+
+#endif
+
+// lex /////////////////////////////////////////////////////////////////////
+
+struct array* lex(struct byte_array *binput);
+
+struct token *token_new(enum Lexeme lexeme, int at_line) {
+ struct token *t = (struct token*)malloc(sizeof(struct token));
+ t->lexeme = lexeme;
+ t->string = NULL;
+ t->number = 0;
+ t->at_line = line;
+ return t;
+}
+
+struct token *insert_token(enum Lexeme lexeme) {
+ struct token *token = token_new(lexeme, line);
+ array_add(lex_list, token);
+ return token;
+}
+
+int insert_token_number(const char *input, int i) {
+ struct token *token = insert_token(LEX_INTEGER);
+ token->number = atoi(&input[i]);
+ //while (isdigit(input[i++]));
+ for (; isdigit(input[i]); i++);
+ return i;
+}
+
+bool isiden(char c)
+{
+ return isalnum(c) || (c=='_');
+}
+
+bool isKeyword(int n)
+{
+ for (int c,i=0; (c = lexemes[n].chars[i]); i++)
+ if (!isalpha(c))
+ return false;
+ return true;
+}
+
+int insert_token_string(enum Lexeme lexeme, const char* input, int i)
+{
+ struct byte_array *string = byte_array_new();
+ while ((lexeme==LEX_IDENTIFIER && isiden(input[i])) ||
+ (lexeme==LEX_STRING && input[i] != QUOTE)) {
+ uint8_t c = input[i++];
+ //DEBUGPRINT("@%d c=%3d %c\n", i, c, c);
+ if (c == ESCAPE) {
+ c = input[i++];
+ switch (c) {
+ case ESCAPED_NEWLINE: c = '\n'; break;
+ case ESCAPED_TAB: c = '\t'; break;
+ case ESCAPED_QUOTE: c = '\''; break;
+ default:
+ return (VOID_INT)exit_message("unknown escape");
+ }
+ }
+ byte_array_add_byte(string, c);
+ }
+
+ int end = i + (lexeme==LEX_STRING);
+ struct token *token = token_new(lexeme, line);
+ token->string = string;
+ array_add(lex_list, token);
+ //display_token(token, 0);
+ return end;
+}
+
+int insert_lexeme(int index) {
+ struct number_string sn = lexemes[index];
+ insert_token((enum Lexeme)sn.number);
+ return strlen(sn.chars);
+}
+
+int import(const char* input, int i)
+{
+ i += strlen(lexeme_to_string(LEX_IMPORT));
+ while (isspace(input[i++]));
+ struct byte_array *path = byte_array_new();
+ while (!isspace(input[i]) && input[i]!=QUOTE)
+ byte_array_add_byte(path, input[i++]);
+ byte_array_append(path, byte_array_from_string(EXTENSION_SRC));
+
+ if (!map_has(imports, path)) {
+ map_insert(imports, path, NULL);
+ struct byte_array *imported = read_file(path);
+ lex(imported);
+ }
+
+ return i+1;
+}
+
+struct array* lex(struct byte_array *binput)
+{
+ lex_list = array_new();
+ imports = map_new();
+ int i=0,j;
+ char c;
+ line = 1;
+
+ const char* input = byte_array_to_string(binput);
+ const char* right_comment = lexeme_to_string(LEX_RIGHT_COMMENT);
+ int right_comment_len = strlen(right_comment);
+
+lexmore:
+ while (i < binput->length) {
+
+ for (j=0; j<ARRAY_LEN(lexemes); j++) {
+
+ char* lexstr = lexemes[j].chars;
+
+ if (!strncmp(&input[i], lexstr, strlen(lexstr))) {
+
+ if (isKeyword(j) && i<binput->length-1 && isalpha(input[i+strlen(lexemes[j].chars)])) {
+ //DEBUGPRINT("%s is a keyword, %c is alpha\n", lexemes[j].chars, input[i+strlen(lexemes[j].chars)]);
+ continue; // just an identifier
+ }
+ enum Lexeme lexeme = (enum Lexeme)lexemes[j].number;
+
+ if (lexeme == LEX_LEFT_COMMENT) { // start comment with /*
+ while (strncmp(&input[i], right_comment, right_comment_len))
+ if (input[i++] == '\n')
+ line++;
+ i += right_comment_len;
+ } else if (lexeme == LEX_LINE_COMMENT) { // start line comment with #
+ while (input[i++] != '\n');
+ line++;
+ } else if (lexeme == LEX_IMPORT)
+ i = import(input, i);
+ else {
+ //DEBUGPRINT("lexeme=%d\n",lexeme);
+ i += insert_lexeme(j);
+ }
+ goto lexmore;
+ }
+ }
+
+ c = input[i];
+
+ if (isdigit(c)) i = insert_token_number(input,i);
+ else if (isiden(c)) i = insert_token_string(LEX_IDENTIFIER, input, i);
+ else if (c == '\n') { line++; i++; }
+ else if (isspace(c)) i++;
+ else if (c=='\'') i = insert_token_string(LEX_STRING, input, i+1);
+ else
+ return (struct array*)exit_message(ERROR_LEX);
+ }
+#ifdef DEBUG
+// display_lex_list();
+#endif
+ return lex_list;
+}
+
+/* parse ///////////////////////////////////////////////////////////////////
+
+BNF:
+
+<statements> --> ( <assignment> | <fcall> | <ifthenelse> | <loop> | <rejoinder> | <iterloop> | <trycatch> | <throw> )*
+<trycatch> --> LEX_TRY <statements> LEX_CATCH <variable> <statements> LEX_END
+<throw> --> LEX_THROW <expression>
+<assignment> --> <destination>, LEX_SET <source>,
+<destination> --> <variable> | ( <expression> <member> )
+<source> --> <expression>
+
+<ifthenelse> --> IF <expression> THEN <statements>
+ ( ELSE IF <expression> THEN <statements> )*
+ ( ELSE <statements>)? LEX_END
+<loop> --> WHILE <expression> LEX_DO <statements> LEX_END
+
+<iterator> --> LEX_FOR LEX_IDENTIFIER LEX_IN <expression> ( LEX_WHERE <expression> )?
+<iterloop> --> <iterator> LEX_DO <statements> LEX_END
+<comprehension> --> LEX_LEFTSQUARE <expression> <iterator> LEX_RIGHTSQUARE
+
+<rejoinder> --> LEX_RETURN <source>,
+<fdecl> --> FUNCTION LEX_LEFTHESIS <variable>, LEX_RIGHTHESIS <statements> LEX_END
+<fcall> --> <expression> <call>
+<call> --> LEX_LEFTHESIS <source>, LEX_RIGHTHESIS
+
+<expression> --> <exp2> ( ( LEX_SAME | LEX_DIFFERENT | LEX_GREATER | LEX_LESSER ) <exp2> )?
+<exp2> --> <exp3> ( ( LEX_PLUS | LEX_MINUS ) <exp3> )*
+<exp3> --> <exp4> ( ( LEX_PLUS | LEX_MINUS | LEX_TIMES | LEX_DIVIDE | LEX_MODULO |
+ LEX_BAND | LEX_BOR | LEX_XOR | LEX_LSHIFT | LEX_RSHIFT) <exp3> )*
+<exp4> --> (LEX_NOT | LEX_MINUS | LEX_INVERSE)? <exp5>
+<exp5> --> <exp6> ( <call> | <member> )*
+<exp6> --> ( LEX_LEFTTHESIS <expression> LEX_RIGHTTHESIS ) | <atom>
+<atom> --> LEX_IDENTIFIER | <float> | <integer> | <boolean> | <table> | <comprehension> | <fdecl>
+
+<variable> --> LEX_IDENTIFIER
+<boolean> --> LEX_TRUE | LEX_FALSE
+<floater> --> LEX_INTEGER LEX_PERIOD LEX_INTEGER
+<string> --> LEX_STRING
+<table> --> LEX_LEFTSQUARE <element>, LEX_RIGHTSQUARE
+<element> --> <expression> ( LEX_COLON <expression> )?
+<member> --> ( LEX_LEFTSQUARE <expression> LEX_RIGHTSQUARE ) | ( LEX_PERIOD LEX_STRING )
+
+*///////////////////////////////////////////////////////////////////////////
+
+ enum Nonterminal {
+ SYMBOL_STATEMENTS,
+ SYMBOL_ASSIGNMENT,
+ SYMBOL_SOURCE,
+ SYMBOL_DESTINATION,
+ SYMBOL_IF_THEN_ELSE,
+ SYMBOL_LOOP,
+ SYMBOL_EXPRESSION,
+ SYMBOL_INTEGER,
+ SYMBOL_FLOAT,
+ SYMBOL_STRING,
+ SYMBOL_VARIABLE,
+ SYMBOL_TABLE,
+ SYMBOL_PAIR,
+ SYMBOL_FDECL,
+ SYMBOL_FCALL,
+ SYMBOL_MEMBER,
+ SYMBOL_RETURN,
+ SYMBOL_BOOLEAN,
+ SYMBOL_NIL,
+ SYMBOL_ITERATOR,
+ SYMBOL_ITERLOOP,
+ SYMBOL_COMPREHENSION,
+ SYMBOL_TRYCATCH,
+ SYMBOL_THROW,
+ } nonterminal;
+
+struct symbol {
+ enum Nonterminal nonterminal;
+ const struct token *token;
+ struct array* list;
+ struct symbol *index, *value;
+ float floater;
+ bool lhs;
+};
+
+struct number_string nonterminals[] = {
+ {SYMBOL_STATEMENTS, "statements"},
+ {SYMBOL_ASSIGNMENT, "assignment"},
+ {SYMBOL_SOURCE, "source"},
+ {SYMBOL_DESTINATION, "destination"},
+ {SYMBOL_IF_THEN_ELSE, "if-then-else"},
+ {SYMBOL_LOOP, "loop"},
+ {SYMBOL_EXPRESSION, "expression"},
+ {SYMBOL_INTEGER, "integer"},
+ {SYMBOL_FLOAT, "float"},
+ {SYMBOL_STRING, "string"},
+ {SYMBOL_VARIABLE, "variable"},
+ {SYMBOL_TABLE, "table"},
+ {SYMBOL_PAIR, "pair"},
+ {SYMBOL_FDECL, "fdecl"},
+ {SYMBOL_FCALL, "fcall"},
+ {SYMBOL_MEMBER, "member"},
+ {SYMBOL_RETURN, "return"},
+ {SYMBOL_BOOLEAN, "boolean"},
+ {SYMBOL_NIL, "nil"},
+ {SYMBOL_ITERATOR, "iterator"},
+ {SYMBOL_ITERLOOP, "iterloop"},
+ {SYMBOL_COMPREHENSION, "comprehension"},
+ {SYMBOL_TRYCATCH, "try-catch"},
+ {SYMBOL_THROW, "throw"},
+};
+
+struct array* parse_list;
+uint32_t parse_index;
+struct symbol *expression();
+struct symbol *statements();
+struct symbol *comprehension();
+
+struct symbol *symbol_new(enum Nonterminal nonterminal)
+{
+ // DEBUGPRINT("symbol_new %s\n", NUM_TO_STRING(nonterminals, ARRAY_LEN(nonterminals), nonterminal));
+ struct symbol *s = (struct symbol*)malloc(sizeof(struct symbol));
+ s->nonterminal = nonterminal;
+ s->list = array_new();
+ s->index = s->value = NULL;
+ s->lhs = false;
+ return s;
+}
+
+struct symbol *symbol_add(struct symbol *s, struct symbol *t)
+{
+ null_check(s);
+ if (!t)
+ return NULL;
+ //DEBUGPRINT("symbol_add %s\n", nonterminals[t->nonterminal]);
+ array_add(s->list, t);
+ return s;
+}
+
+#ifdef DEBUG
+
+void display_symbol(const struct symbol *symbol, int depth)
+{
+ // null_check(symbol);
+ if (!symbol)
+ return;
+ assert_message(depth < 100, "kablooie!");
+ char* indent = (char*)malloc(sizeof(char)*(depth+1));
+ int i;
+ for (i=0; i<depth; i++)
+ indent[i] = '\t';
+ indent[i] = 0;
+ DEBUGPRINT("%s%d %s", indent, symbol->nonterminal, NUM_TO_STRING(nonterminals, symbol->nonterminal));
+
+ switch (symbol->nonterminal) {
+ case SYMBOL_INTEGER:
+ DEBUGPRINT(": %u\n", symbol->token->number);
+ break;
+ case SYMBOL_FLOAT:
+ DEBUGPRINT(": %f\n", symbol->floater);
+ break;
+ case SYMBOL_VARIABLE: {
+ char* s = byte_array_to_string(symbol->token->string);
+ DEBUGPRINT(": '%s (%s)'\n", s, symbol->lhs ? "lhs":"rhs");
+ free(s);
+ } break;
+ case SYMBOL_STRING: {
+ char* s = byte_array_to_string(symbol->token->string);
+ DEBUGPRINT(": '%s'\n", s);
+ free(s);
+ } break;
+ case SYMBOL_EXPRESSION:
+ DEBUGPRINT(" %s\n", lexeme_to_string(symbol->token->lexeme));
+ break;
+ case SYMBOL_TRYCATCH:
+ DEBUGPRINT("try\n");
+ display_symbol(symbol->index, depth);
+ DEBUGPRINT("catch %s\n", byte_array_to_string(symbol->token->string));
+ display_symbol(symbol->value, depth);
+ break;
+ default:
+ DEBUGPRINT("\n");
+ depth++;
+ display_symbol(symbol->index, depth);
+ display_symbol(symbol->value, depth);
+ depth--;
+ break;
+ }
+
+ const struct array *list = symbol->list;
+ if (list && list->length) {
+ DEBUGPRINT("%s\tlist:\n", indent);
+ depth++;
+ for (int k=0; k<list->length; k++) {
+ const struct symbol *item = array_get(list, k);
+ display_symbol(item, depth);
+ }
+ }
+
+ free(indent);
+}
+
+#endif
+
+#define LOOKAHEAD (lookahead(0))
+#define FETCH_OR_QUIT(x) if (!fetch(x)) return NULL;
+#define OR_ERROR(x) { exit_message("missing %s at line %d", NUM_TO_STRING(lexemes, x), line); return NULL; }
+#define FETCH_OR_ERROR(x) if (!fetch(x)) OR_ERROR(x);
+
+
+enum Lexeme lookahead(int n) {
+ if (parse_index + n >= parse_list->length)
+ return LEX_NONE;
+ struct token *token = (struct token*)parse_list->data[parse_index+n];
+ assert_message(token!=0, ERROR_NULL);
+ return token->lexeme;
+}
+
+struct token *fetch(enum Lexeme lexeme) {
+ if (parse_index >= parse_list->length)
+ return NULL;
+ struct token *token = (struct token*)parse_list->data[parse_index];
+ if (token->lexeme != lexeme) {
+ //DEBUGPRINT("fetched %s instead of %s at %d\n", lexeme_to_string(token->lexeme), lexeme_to_string(lexeme), parse_index);
+ return NULL;
+ }
+ //DEBUGPRINT("fetched %s at %d\n", lexeme_to_string(lexeme), parse_index);
+ // display_token(token, 0);
+
+ parse_index++;
+ return token;
+}
+
+typedef struct symbol*(Parsnip)();
+
+struct symbol *one_of(Parsnip *p, ...) {
+ uint32_t start = parse_index;
+ struct symbol *t = NULL;
+ va_list argp;
+ va_start(argp, p);
+ for (;
+ p && !(t=p());
+ p = va_arg(argp, Parsnip*))
+ parse_index=start;
+ va_end(argp);
+ return t;
+}
+
+struct token *fetch_lookahead(enum Lexeme lexeme, ...) {
+ struct token *t=NULL;
+ va_list argp;
+ va_start(argp, lexeme);
+
+ for (; lexeme; lexeme = (enum Lexeme)va_arg(argp, int)) {
+ if (LOOKAHEAD == lexeme) {
+ t = fetch(lexeme);
+ break;
+ }
+ }
+ va_end(argp);
+ return t;
+}
+
+struct symbol *symbol_fetch(enum Nonterminal n, enum Lexeme goal, ...)
+{
+ if (parse_index >= parse_list->length)
+ return NULL;
+ struct token *token = (struct token*)parse_list->data[parse_index];
+ assert_message(token!=0, ERROR_NULL);
+ enum Lexeme lexeme = token->lexeme;
+
+ struct symbol *symbol = NULL;
+
+ va_list argp;
+ va_start(argp, goal);
+
+ for (; goal; goal = (enum Lexeme)va_arg(argp, int)) {
+ if (lexeme == goal) {
+
+ symbol = symbol_new(n);
+ symbol->token = token;
+ // DEBUGPRINT("fetched %s at %d\n", lexeme_to_string(lexeme), parse_index);
+ // display_token(token, 0);
+
+ parse_index++;
+ break;
+ }
+ }
+ va_end(argp);
+ return symbol;
+}
+
+struct symbol *symbol_adds(struct symbol *s, struct symbol *child, ...) {
+ va_list argp;
+ va_start(argp, child);
+ for (; child; child = va_arg(argp, struct symbol*))
+ array_add(s->list, child);
+ va_end(argp);
+ return s;
+
+}
+
+// <x>, --> ( <x> ( LEX_COMMA <x> )* )?
+// e.g. a list of zero or more <x>, separated by commas
+struct symbol *repeated(enum Nonterminal nonterminal, Parsnip *p)
+{
+ struct symbol *r, *s = symbol_new(nonterminal);
+ do {
+ if (!(r=p()))
+ break;
+ symbol_add(s, r);
+ } while (fetch(LEX_COMMA));
+ return s;
+}
+
+//////////////////////////////// BNFs
+
+
+// <destination> --> <variable> | ( <expression> <member> )
+struct symbol *destination()
+{
+ struct symbol *e = expression();
+ if (!e ||
+ (e->nonterminal != SYMBOL_MEMBER &&
+ e->nonterminal != SYMBOL_VARIABLE))
+ return NULL;
+ e->lhs = true;
+ return e;
+};
+
+//<variable> --> LEX_IDENTIFIER
+struct symbol *variable()
+{
+ return symbol_fetch(SYMBOL_VARIABLE, LEX_IDENTIFIER, NULL);
+}
+
+
+// <fdecl> --> FUNCTION LEX_LEFTHESIS <variable>, LEX_RIGHTHESIS <statements> LEX_END
+struct symbol *fdecl()
+{
+ FETCH_OR_QUIT(LEX_FUNCTION)
+ FETCH_OR_ERROR(LEX_LEFTHESIS);
+ struct symbol *s = symbol_new(SYMBOL_FDECL);
+ s->index = repeated(SYMBOL_DESTINATION, &destination);
+ FETCH_OR_ERROR(LEX_RIGHTHESIS)
+ s->value = statements();
+ //DEBUGPRINT("fdecl: %d statements\n", s->value->list->length);
+ //DEBUGPRINT("lookahead=%s\n", NUM_TO_STRING(lexemes, LOOKAHEAD));
+ FETCH_OR_ERROR(LEX_END);
+ return s;
+}
+
+// <element> --> <expression> ( LEX_COLON <expression> )?
+struct symbol *element()
+{
+ struct symbol *e = expression();
+ if (fetch(LEX_COLON)) { // i.e. x:y
+ struct symbol *p = symbol_new(SYMBOL_PAIR);
+ p->index = e;
+ p->value = expression();
+ return p;
+ } else {
+// p->index = symbol_new(SYMBOL_NIL);
+ return e;
+ }
+}
+
+// <table> --> LEX_LEFTSQUARE <element>, LEX_RIGHTSQUARE
+struct symbol *table() {
+ //return list(SYMBOL_TABLE, LEX_LEFTSQUARE, LEX_RIGHTSQUARE, LEX_COLON);
+ FETCH_OR_QUIT(LEX_LEFTSQUARE);
+ struct symbol *s = repeated(SYMBOL_TABLE, &element);
+ FETCH_OR_ERROR(LEX_RIGHTSQUARE);
+ return s;
+}
+
+struct symbol *integer()
+{
+ // DEBUGPRINT("integer\n");
+ struct token *t = fetch(LEX_INTEGER);
+ if (!t)
+ return NULL;
+ struct symbol *s = symbol_new(SYMBOL_INTEGER);
+ s->token = t;
+ return s;
+}
+
+struct symbol *boolean()
+{
+ struct token *t = fetch_lookahead(LEX_TRUE, LEX_FALSE, NULL);
+ if (!t)
+ return NULL;
+ struct symbol *s = symbol_new(SYMBOL_BOOLEAN);
+ s->token = t;
+ return s;
+}
+
+struct symbol *floater()
+{
+ // DEBUGPRINT("floater\n");
+ struct token *t = fetch(LEX_INTEGER);
+ if (!t)
+ return NULL;
+ FETCH_OR_QUIT(LEX_PERIOD);
+ struct token *u = fetch(LEX_INTEGER);
+
+ float decimal = u->number;
+ while (decimal > 1)
+ decimal /= 10;
+
+ struct symbol *s = symbol_new(SYMBOL_FLOAT);
+ s->floater = t->number + decimal;
+ return s;
+}
+
+// <string> --> LEX_STRING
+struct symbol *string()
+{
+ struct token *t = fetch(LEX_STRING);
+ if (!t)
+ return NULL;
+ struct symbol *s = symbol_new(SYMBOL_STRING);
+ s->token = t;
+ return s;
+}
+
+// <atom> --> LEX_IDENTIFIER | <float> | <integer> | <boolean> | <table> | <comprehension> | <fdecl>
+struct symbol *atom()
+{
+ return one_of(&variable, &string, &floater, &integer, &boolean, &comprehension, &table, &fdecl, NULL);
+}
+
+// <exp5> --> ( LEX_LEFTTHESIS <expression> LEX_RIGHTTHESIS ) | <atom>
+struct symbol *exp5()
+{
+ if (fetch(LEX_LEFTHESIS)) {
+ struct symbol *s = expression();
+ fetch(LEX_RIGHTHESIS);
+ return s;
+ }
+ return atom();
+}
+
+// <member> --> ( LEX_LEFTSQUARE <expression> LEX_RIGHTSQUARE ) | ( LEX_PERIOD LEX_STRING )
+struct symbol *member()
+{
+ struct symbol *m = symbol_new(SYMBOL_MEMBER);
+
+ if (fetch(LEX_PERIOD)) {
+ m->index = variable();
+ m->index->nonterminal = SYMBOL_STRING;
+ }
+ else {
+ FETCH_OR_QUIT(LEX_LEFTSQUARE);
+ m->index = expression();
+ FETCH_OR_QUIT(LEX_RIGHTSQUARE);
+ }
+ return m;
+}
+
+// <call> --> LEX_LEFTHESIS <source>, LEX_RIGHTHESIS
+struct symbol *call()
+{
+ struct symbol *s = symbol_new(SYMBOL_FCALL);
+ FETCH_OR_QUIT(LEX_LEFTHESIS);
+ s->index = repeated(SYMBOL_SOURCE, &expression); // arguments
+ FETCH_OR_ERROR(LEX_RIGHTHESIS);
+ return s;
+}
+
+// <fcall> --> <expression> <call>
+struct symbol *fcall()
+{
+ struct symbol *e = expression();
+ return (e && e->nonterminal == SYMBOL_FCALL) ? e : NULL;
+}
+
+// <exp4> --> <exp5> ( <call> | member )*
+struct symbol *exp4()
+{
+ struct symbol *g, *f;
+ f = exp5();
+ while (f && (g = one_of(&call, &member, NULL))) {
+ g->value = f;
+ f = g;
+ }
+ return f;
+}
+
+// <exp3> --> (NOT | LEX_MINUS)? <exp4>
+struct symbol *exp3()
+{
+ struct symbol *e;
+ if ((e = symbol_fetch(SYMBOL_EXPRESSION, LEX_MINUS, LEX_NOT, NULL)))
+ return symbol_add(e, exp3());
+ return exp4();
+}
+
+// <exp2> --> (<exp3> ( ( LEX_PLUS | LEX_MINUS | LEX_TIMES | LEX_DIVIDE | MODULO ))* <exp3>
+struct symbol *expTwo()
+{
+ struct symbol *e, *f;
+ e = exp3();
+ while ((f = symbol_fetch(SYMBOL_EXPRESSION, LEX_PLUS, LEX_MINUS, LEX_TIMES, LEX_DIVIDE, LEX_MODULO, NULL)))
+ e = symbol_adds(f, e, exp3(), NULL);
+ return e;
+}
+
+// <expression> --> <exp2> ( ( LEX_SAME | LEX_DIFFERENT | LEX_GREATER | LEX_LESSER ) <exp2> )?
+struct symbol *expression()
+{
+ struct symbol *f, *e = expTwo();
+ while ((f = symbol_fetch(SYMBOL_EXPRESSION, LEX_SAME, LEX_DIFFERENT, LEX_GREATER, LEX_LESSER, NULL)))
+ e = symbol_adds(f, e, expTwo(), NULL);
+ return e;
+}
+
+// <assignment> --> <destination>, LEX_SET <source>,
+struct symbol *assignment()
+{
+ struct symbol *d = repeated(SYMBOL_DESTINATION, &destination);
+ FETCH_OR_QUIT(LEX_SET);
+ struct symbol *s = symbol_new(SYMBOL_ASSIGNMENT);
+ s->value = repeated(SYMBOL_SOURCE, expression);
+ s->index = d;
+ return s;
+}
+
+/* <ifthenelse> --> IF <expression>
+ THEN <statements>
+ (ELSE IF <expression> THEN <statements>)*
+ (ELSE <statements>)?
+ END */
+struct symbol *ifthenelse()
+{
+ FETCH_OR_QUIT(LEX_IF);
+ struct symbol *f = symbol_new(SYMBOL_IF_THEN_ELSE);
+ symbol_add(f, expression());
+ fetch(LEX_THEN);
+ symbol_add(f, statements());
+
+ while (lookahead(0) == LEX_ELSE && lookahead(1) == LEX_IF) {
+ fetch(LEX_ELSE);
+ fetch(LEX_IF);
+ symbol_add(f, expression());
+ fetch(LEX_THEN);
+ symbol_add(f, statements());
+ }
+
+ if (fetch_lookahead(LEX_ELSE))
+ symbol_add(f, statements());
+ fetch(LEX_END);
+ return f;
+}
+
+// <loop> --> WHILE <expression> <statements> END
+struct symbol *loop()
+{
+ FETCH_OR_QUIT(LEX_WHILE);
+ struct symbol *s = symbol_new(SYMBOL_LOOP);
+ s->index = expression();
+ s->value = statements();
+ FETCH_OR_ERROR(LEX_END);
+ return s;
+}
+
+// <iterator> --> LEX_FOR LEX_IDENTIFIER LEX_IN <expression> ( LEX_WHERE <expression> )?
+struct symbol *iterator()
+{
+ FETCH_OR_QUIT(LEX_FOR);
+ const struct token *t = fetch(LEX_IDENTIFIER);
+ struct symbol *s = symbol_new(SYMBOL_ITERATOR);
+ s->token = t;
+
+ FETCH_OR_ERROR(LEX_IN);
+ s->value = expression();
+ if (fetch_lookahead(LEX_WHERE))
+ s->index = expression();
+ return s;
+}
+
+// <comprehension> --> LEX_LEFTSQUARE <expression> <iterator> LEX_RIGHTSQUARE
+struct symbol *comprehension()
+{
+ // DEBUGPRINT("comprehension\n");
+ FETCH_OR_QUIT(LEX_LEFTSQUARE);
+ struct symbol *s = symbol_new(SYMBOL_COMPREHENSION);
+ s->value = expression();
+ s->index = iterator();
+ if (!s->index)
+ return NULL;
+ FETCH_OR_ERROR(LEX_RIGHTSQUARE);
+ return s;
+}
+
+// <iterloop> --> <iterator> <statements> LEX_END
+struct symbol *iterloop()
+{
+ struct symbol *i = iterator();
+ if (!i)
+ return NULL;
+ struct symbol *s = symbol_new(SYMBOL_ITERLOOP);
+ s->index = i;
+ s->value = statements();
+ FETCH_OR_ERROR(LEX_END);
+ return s;
+}
+
+// <rejoinder> --> // LEX_RETURN <expression>
+struct symbol *rejoinder()
+{
+ FETCH_OR_QUIT(LEX_RETURN);
+ return repeated(SYMBOL_RETURN, &expression); // return values
+}
+
+// <trycatch> --> LEX_TRY <statements> LEX_CATCH <destination> <statements> LEX_END
+struct symbol *trycatch()
+{
+ FETCH_OR_QUIT(LEX_TRY);
+ struct symbol *s = symbol_new(SYMBOL_TRYCATCH);
+ s->index = statements();
+ FETCH_OR_ERROR(LEX_CATCH);
+ if (!(s->token = fetch(LEX_IDENTIFIER)))
+ OR_ERROR(LEX_IDENTIFIER);
+ s->lhs = true;
+ s->value = statements();
+ FETCH_OR_ERROR(LEX_END);
+ return s;
+}
+
+// <throw> --> LEX_THROW <expression>
+struct symbol *thrower()
+{
+ FETCH_OR_QUIT(LEX_THROW);
+ struct symbol *s = symbol_new(SYMBOL_THROW);
+ s->value = expression();
+ return s;
+}
+
+struct symbol *strings_and_variables()
+{
+ struct array *sav = array_new();
+ while ((array_add(sav, variable()) || array_add(sav, string())));
+ return (struct symbol*)sav;
+}
+
+// <statements> --> ( <assignment> | <fcall> | <ifthenelse> | <loop> | <rejoinder> | <iterloop> ) *
+struct symbol *statements()
+{
+ struct symbol *s = symbol_new(SYMBOL_STATEMENTS);
+ struct symbol *t;
+ while ((t = one_of(&assignment, &fcall, &ifthenelse, &loop, &rejoinder, &iterloop, &trycatch, &thrower, NULL)))
+ symbol_add(s, t);
+ return s;
+}
+
+struct symbol *parse(struct array *list, uint32_t index)
+{
+ DEBUGPRINT("parse:\n");
+ assert_message(list!=0, ERROR_NULL);
+ assert_message(index<list->length, ERROR_INDEX);
+
+ parse_list = list;
+ parse_index = index;
+
+ struct symbol *p = statements();
+#ifdef DEBUG
+ display_symbol(p, 1);
+#endif
+ return p;
+}
+
+
+// generate ////////////////////////////////////////////////////////////////
+
+struct byte_array *generate_code(struct byte_array *code, struct symbol *root);
+
+void generate_step(struct byte_array *code, int count, int action,...)
+{
+ byte_array_add_byte(code, action);
+
+ va_list argp;
+ uint8_t parameter;
+ for(va_start(argp, action); --count;) {
+ parameter = va_arg(argp, int);
+ byte_array_add_byte(code, (uint8_t)parameter);
+ }
+ va_end(argp);
+}
+
+void generate_items(struct byte_array *code, const struct symbol* root)
+{
+ const struct array *items = root->list;
+ uint32_t num_items = items->length;
+
+ for (int i=0; i<num_items; i++) {
+ struct symbol *item = (struct symbol*)array_get(items, i);
+ generate_code(code, item);
+ }
+}
+
+void generate_items_then_op(struct byte_array *code, enum Opcode opcode, const struct symbol* root)
+{
+ generate_items(code, root);
+ generate_step(code, 1, opcode);
+ serial_encode_int(code, 0, root->list->length);
+}
+
+void generate_statements(struct byte_array *code, struct symbol *root) {
+ if (root)
+ generate_items(code, root);
+}
+
+void generate_return(struct byte_array *code, struct symbol *root) {
+ generate_items_then_op(code, VM_RET, root);
+}
+
+void generate_nil(struct byte_array *code, struct symbol *root) {
+ generate_step(code, 1, VM_NIL);
+}
+
+static void generate_jump(struct byte_array *code, int32_t offset) {
+ generate_step(code, 1, VM_JMP);
+ serial_encode_int(code, 0, offset);
+}
+
+void generate_list(struct byte_array *code, struct symbol *root) {
+ generate_items_then_op(code, VM_LST, root);
+}
+
+void generate_float(struct byte_array *code, struct symbol *root)
+{
+ generate_step(code, 1, VM_FLT);
+ serial_encode_float(code, 0, root->floater);
+}
+
+void generate_integer(struct byte_array *code, struct symbol *root) {
+ generate_step(code, 1, VM_INT);
+ serial_encode_int(code, 0, root->token->number);
+}
+
+void generate_string(struct byte_array *code, struct symbol *root) {
+ generate_step(code, 1, VM_STR);
+ serial_encode_string(code, 0, root->token->string);
+}
+
+void generate_source(struct byte_array *code, struct symbol *root) {
+ generate_items_then_op(code, VM_SRC, root);
+}
+
+void generate_destination(struct byte_array *code, struct symbol *root)
+{
+ generate_items(code, root);
+ generate_step(code, 1, VM_DST);
+}
+
+void generate_assignment(struct byte_array *code, struct symbol *root)
+{
+ generate_code(code, root->value);
+ generate_code(code, root->index);
+}
+
+void generate_variable(struct byte_array *code, struct symbol *root)
+{
+ generate_step(code, 1, root->lhs ? VM_SET : VM_VAR);
+ serial_encode_string(code, 0, root->token->string);
+}
+
+void generate_boolean(struct byte_array *code, struct symbol *root) {
+ uint32_t value = 0;
+ switch (root->token->lexeme) {
+ case LEX_TRUE: value = 1; break;
+ case LEX_FALSE: value = 0; break;
+ default: exit_message("bad boolean value"); return;
+ }
+ generate_step(code, 1, VM_BOOL);
+ serial_encode_int(code, 0, value);
+}
+
+void generate_fdecl(struct byte_array *code, struct symbol *root)
+{
+ struct byte_array *f = byte_array_new();
+ generate_code(f, root->index);
+ generate_code(f, root->value);
+ generate_step(code, 1, VM_FNC);
+ serial_encode_string(code, 0, f);
+}
+
+void generate_pair(struct byte_array *code, struct symbol *root)
+{
+ generate_code(code, root->index);
+ generate_code(code, root->value);
+ generate_step(code, 2, VM_MAP, 1);
+}
+
+void generate_member(struct byte_array *code, struct symbol *root)
+{
+ generate_code(code, root->index); // array_get(root->branches, INDEX));
+ generate_code(code, root->value); // array_get(root->branches, ITERABLE));
+
+ enum Opcode op = root->lhs ? VM_PUT : VM_GET;
+ generate_step(code, 1, op);
+}
+
+void generate_fcall(struct byte_array *code, struct symbol *root)
+{
+ generate_code(code, root->index); // arguments
+
+ if (root->value->nonterminal == SYMBOL_MEMBER) {
+ generate_code(code, root->value->index);
+ generate_code(code, root->value->value);
+ generate_step(code, 1, VM_MET);
+ } else {
+ generate_code(code, root->value); // function
+ generate_step(code, 1, VM_CAL);
+ }
+}
+
+void generate_math(struct byte_array *code, struct symbol *root)
+{
+ enum Lexeme lexeme = root->token->lexeme;
+ generate_statements(code, root);
+ enum Opcode op = VM_NIL;
+ switch (lexeme) {
+ case LEX_PLUS: op = VM_ADD; break;
+ case LEX_MINUS: op = VM_SUB; break;
+ case LEX_TIMES: op = VM_MUL; break;
+ case LEX_DIVIDE: op = VM_DIV; break;
+ case LEX_MODULO: op = VM_MOD; break;
+ case LEX_AND: op = VM_AND; break;
+ case LEX_OR: op = VM_OR; break;
+ case LEX_NOT: op = VM_NOT; break;
+ case LEX_SAME: op = VM_EQU; break;
+ case LEX_DIFFERENT: op = VM_NEQ; break;
+ case LEX_GREATER: op = VM_GTN; break;
+ case LEX_LESSER: op = VM_LTN; break;
+ default: exit_message("bad math lexeme"); break;
+ }
+ generate_step(code, 1, op);
+}
+
+void generate_ifthenelse(struct byte_array *code, struct symbol *root)
+{
+ struct array *gotos = array_new(); // for skipping to end of elseifs, if one is true
+
+ for (int i=0; i<root->list->length; i+=2) {
+
+ // then
+ struct symbol *thn = (struct symbol*)array_get(root->list, i+1);
+ assert_message(thn->nonterminal == SYMBOL_STATEMENTS, "branch syntax error");
+ struct byte_array *thn_code = byte_array_new();
+ generate_code(thn_code, thn);
+ generate_jump(thn_code, 0); // jump to end
+
+ // if
+ struct symbol *iff = (struct symbol*)array_get(root->list, i);
+ generate_code(code, iff);
+ generate_step(code, 2, VM_IFF, thn_code->length);
+ byte_array_append(code, thn_code);
+ array_add(gotos, (void*)(VOID_INT)(code->length-1));
+
+ // else
+ if (root->list->length > i+2) {
+ struct symbol *els = (struct symbol*)array_get(root->list, i+2);
+ if (els->nonterminal == SYMBOL_STATEMENTS) {
+ assert_message(root->list->length == i+3, "else should be the last branch");
+ generate_code(code, els);
+ break;
+ }
+ }
+ }
+
+ // go back and fill in where to jump to the end of if-then-elseif-else when done
+ for (int j=0; j<gotos->length; j++) {
+ VOID_INT g = (VOID_INT)array_get(gotos, j);
+ code->data[g] = code->length - g;
+ }
+}
+
+void generate_loop(struct byte_array *code, struct symbol *root)
+{
+ struct byte_array *ifa = byte_array_new();
+ generate_code(ifa, root->index);
+
+ struct byte_array *b = byte_array_new();
+ generate_code(b, root->value);
+
+ struct byte_array *thn = byte_array_new();
+ generate_step(thn, 1, VM_IFF);
+ serial_encode_int(thn, 0, b->length + 2);
+
+ struct byte_array *while_a_do_b = byte_array_concatenate(4, code, ifa, thn, b);
+ byte_array_append(code, while_a_do_b);
+ int32_t loop_length = ifa->length + thn->length + b->length;
+ generate_jump(code, -loop_length-1);
+}
+
+// <iterator> --> LEX_FOR LEX_IDENTIFIER LEX_IN <expression> ( LEX_WHERE <expression> )?
+void generate_iterator(struct byte_array *code, struct symbol *root, enum Opcode op)
+{
+ struct symbol *ator = root->index;
+ generate_code(code, ator->value); // IN b
+ generate_step(code, 1, op); // iterator or comprehension
+ serial_encode_string(code, 0, ator->token->string); // FOR a
+
+ if (ator->index) { // WHERE c
+ struct byte_array *where = byte_array_new();
+ generate_code(where, ator->index);
+ serial_encode_string(code, 0, where);
+ }
+ else
+ generate_nil(code, NULL);
+
+ struct byte_array *what = byte_array_new();
+ generate_code(what, root->value);
+ serial_encode_string(code, 0, what); // DO d
+}
+
+// <iterloop> --> <iterator> <statements> LEX_END
+void generate_iterloop(struct byte_array *code, struct symbol *root) {
+ generate_iterator(code, root, VM_ITR);
+}
+
+// <comprehension> --> LEX_LEFTSQUARE <expression> <iterator> LEX_RIGHTSQUARE
+void generate_comprehension(struct byte_array *code, struct symbol *root) {
+ generate_iterator(code, root, VM_COM);
+}
+
+// <trycatch> --> LEX_TRY <statements> LEX_CATCH <variable> <statements> LEX_END
+void generate_trycatch(struct byte_array *code, struct symbol *root)
+{
+ struct byte_array *trial = generate_code(NULL, root->index);
+
+ generate_step(code, 1, VM_TRY);
+ serial_encode_string(code, 0, trial);
+
+ serial_encode_string(code, 0, root->token->string);
+ struct byte_array *catcher = generate_code(NULL, root->value);
+ serial_encode_string(code, 0, catcher);
+}
+
+void generate_throw(struct byte_array *code, struct symbol *root)
+{
+ generate_code(code, root->value);
+ generate_step(code, 1, VM_TRO);
+}
+
+typedef void(generator)(struct byte_array*, struct symbol*);
+
+struct byte_array *generate_code(struct byte_array *code, struct symbol *root)
+{
+ if (!root)
+ return NULL;
+ generator *g = NULL;
+
+ //DEBUGPRINT("generate_code %s\n", nonterminals[root->nonterminal]);
+ switch(root->nonterminal) {
+ case SYMBOL_NIL: g = generate_nil; break;
+ case SYMBOL_PAIR: g = generate_pair; break;
+ case SYMBOL_LOOP: g = generate_loop; break;
+ case SYMBOL_FDECL: g = generate_fdecl; break;
+ case SYMBOL_TABLE: g = generate_list; break;
+ case SYMBOL_FCALL: g = generate_fcall; break;
+ case SYMBOL_FLOAT: g = generate_float; break;
+ case SYMBOL_MEMBER: g = generate_member; break;
+ case SYMBOL_RETURN: g = generate_return; break;
+ case SYMBOL_SOURCE: g = generate_source; break;
+ case SYMBOL_STRING: g = generate_string; break;
+ case SYMBOL_INTEGER: g = generate_integer; break;
+ case SYMBOL_BOOLEAN: g = generate_boolean; break;
+ case SYMBOL_ITERLOOP: g = generate_iterloop; break;
+ case SYMBOL_VARIABLE: g = generate_variable; break;
+ case SYMBOL_STATEMENTS: g = generate_statements; break;
+ case SYMBOL_ASSIGNMENT: g = generate_assignment; break;
+ case SYMBOL_EXPRESSION: g = generate_math; break;
+ case SYMBOL_DESTINATION: g = generate_destination; break;
+ case SYMBOL_IF_THEN_ELSE: g = generate_ifthenelse; break;
+ case SYMBOL_COMPREHENSION: g = generate_comprehension; break;
+ case SYMBOL_TRYCATCH: g = generate_trycatch; break;
+ case SYMBOL_THROW: g = generate_throw; break;
+ default:
+ return (struct byte_array*)exit_message(ERROR_TOKEN);
+ }
+
+ if (!code)
+ code = byte_array_new();
+ if (g)
+ g(code, root);
+ return code;
+}
+
+struct byte_array *generate_program(struct symbol *root)
+{
+ DEBUGPRINT("generate:\n");
+ struct byte_array *code = byte_array_new();
+ generate_code(code, root);
+ struct byte_array *program = serial_encode_int(0, 0, code->length);
+ byte_array_append(program, code);
+#ifdef DEBUG
+ display_program(program);
+#endif
+ return program;
+}
+
+// build ///////////////////////////////////////////////////////////////////
+
+struct byte_array *build_string(const struct byte_array *input) {
+ assert_message(input, ERROR_NULL);
+ struct byte_array *input_copy = byte_array_copy(input);
+ DEBUGPRINT("lex %d:\n", input_copy->length);
+ struct array* list = lex(input_copy);
+ struct symbol *tree = parse(list, 0);
+
+ return generate_program(tree);
+}
+
+struct byte_array *build_file(const struct byte_array* filename)
+{
+ struct byte_array *input = read_file(filename);
+ return build_string(input);
+}
+
+void compile_file(const char* str)
+{
+ struct byte_array *filename = byte_array_from_string(str);
+ struct byte_array *program = build_file(filename);
+ struct byte_array *dotfg = byte_array_from_string(EXTENSION_SRC);
+ struct byte_array *dotfgbc = byte_array_from_string(EXTENSION_BC);
+ int offset = byte_array_find(filename, dotfg, 0);
+ assert_message(offset > 0, "invalid source file name");
+ byte_array_replace(filename, dotfgbc, offset, dotfg->length);
+ write_file(filename, program);
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compile.h Wed May 30 21:13:01 2012 +0000 @@ -0,0 +1,12 @@ +#ifndef COMPILE_H + +#include "vm.h" + +#define EXTENSION_SRC ".fg" +#define EXTENSION_BC ".fgbc" + +struct byte_array *build_string(const struct byte_array *input); +struct byte_array *build_file(const struct byte_array* filename); +void compile_file(const char* str); + +#endif // COMPILE_H
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/interpret.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,100 @@
+//
+// interpret.c
+// filagree
+//
+
+#include "vm.h"
+#include "compile.h"
+#include "interpret.h"
+
+#define FG_MAX_INPUT 256
+#define ERROR_USAGE "usage: filagree [file]"
+
+
+void yield(struct Context *context) {
+#ifdef DEBUG
+ struct stack *stack = context->rhs;
+ struct variable *f = stack_pop(stack);
+ struct byte_array *result = f->str;
+ byte_array_append(result, byte_array_from_string(": "));
+ while (!stack_empty(stack)) {
+ struct variable *v = stack_pop(stack);
+ byte_array_append(result, variable_value(context, v));
+ }
+ DEBUGPRINT("%s\n", byte_array_to_string(result));
+#endif
+}
+
+struct variable *repl()
+{
+ char stdinput[FG_MAX_INPUT];
+ struct variable *v = NULL;
+ struct Context *context = vm_init();
+
+ for (;;) {
+ fflush(stdin);
+ stdinput[0] = 0;
+ if (!fgets(stdinput, FG_MAX_INPUT, stdin)) {
+ if (feof(stdin))
+ return 0;
+ if (ferror(stdin))
+ //return errno;
+ return variable_new_err(context, "unknown error reading stdin");
+ }
+ if ((v = interpret_string(stdinput, &yield)))
+ return v;
+ }
+}
+
+struct variable *interpret_file(const struct byte_array *filename, bridge *callback)
+{
+ struct byte_array *program = build_file(filename);
+ return execute(program, false, callback);
+}
+
+struct variable *execute_file(const struct byte_array* filename, bridge *callback)
+{
+ struct byte_array *program = read_file(filename);
+ return execute(program, false, callback);
+}
+
+struct variable *run_file(const char* str, bridge *callback)
+{
+ struct byte_array *filename = byte_array_from_string(str);
+ struct byte_array *dotfgbc = byte_array_from_string(EXTENSION_BC);
+ int fgbc = byte_array_find(filename, dotfgbc, 0);
+ if (fgbc > 0)
+ return execute_file(filename, callback);
+ struct byte_array *dotfg = byte_array_from_string(EXTENSION_SRC);
+ int fg = byte_array_find(filename, dotfg, 0);
+ if (fg > 0)
+ return interpret_file(filename, callback);
+ return (struct variable*)exit_message("invalid file name");
+}
+
+struct variable *interpret_string(const char *str, bridge *callback)
+{
+ struct variable *e;
+ struct byte_array *input = byte_array_from_string(str);
+ struct byte_array *program = build_string(input);
+ if (program && (e = execute(program, true, callback)) && (e->type == VAR_ERR))
+ printf("%s\n", byte_array_to_string(e->str));
+ return NULL;
+}
+
+#ifdef CLI
+int main (int argc, char** argv)
+{
+ struct variable *v = NULL;
+ switch (argc) {
+ case 1: v = repl(); break;
+ case 2: v = run_file(argv[1], &yield); break;
+ case 3: compile_file(argv[1]); break;
+ default: exit_message(ERROR_USAGE); break;
+ }
+ if (v && v->type==VAR_ERR)
+ log_print("%s\n", variable_value_str(NULL, v));
+ return v && v->type == VAR_ERR;
+}
+#endif // EXECUTABLE
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/interpret.h Wed May 30 21:13:01 2012 +0000 @@ -0,0 +1,12 @@ +// +// interpret.h +// filagree +// + +#ifndef INTERPRET_H +#define INTERPRET_H + +struct variable *interpret_file(const struct byte_array *filename, bridge *callback); +struct variable *interpret_string(const char *str, bridge *callback); + +#endif // INTERPRET_H
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/serial.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,213 @@
+/*
+ * serial.c
+ *
+ * stream serialization - serialies and deserializes byte_array and calls-back on each element
+ */
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+
+#include "serial.h"
+#include "struct.h"
+#include "vm.h"
+#include "util.h"
+
+// functions ///////////////////////////////////////////////////////////////
+
+// tells how many bytes are needed to encode this value
+uint8_t encode_int_size(int32_t value)
+{
+ uint8_t i;
+ value = (value >= 0 ? value : -value) >> 6;
+ for (i=1; value; i++, value >>=7);
+ return i;
+}
+
+struct byte_array *encode_int(struct byte_array *buf, int32_t value)
+{
+ if (!buf)
+ buf = byte_array_new();
+ uint8_t growth = encode_int_size(value);
+ byte_array_resize(buf, buf->length + growth);
+ bool neg = value < 0;
+ value = abs(value);
+ uint8_t byte = (value & 0x3F) | ((value >= 0x40) ? 0x80 : 0) | (neg ? 0x40 : 0);
+ *buf->current++ = byte;
+ value >>= 6;
+ while (value) {
+ byte = (value & 0x7F) | ((value >= 0x80) ? 0x80 : 0);
+ *buf->current++ = byte;
+ value >>= 7;
+ }
+ return buf;
+}
+
+struct byte_array* serial_encode_int(struct byte_array* buf, int32_t key, int32_t value) {
+ if (!buf)
+ buf = byte_array_new();
+ if (key)
+ encode_int(buf, key<<2 | SERIAL_INT);
+ encode_int(buf, value);
+ return buf;
+}
+
+int32_t serial_decode_int(struct byte_array* buf)
+{
+ bool neg = *buf->current & 0x40;
+ int32_t ret = *buf->current & 0x3F;
+ int bitpos = 6;
+ while ((*buf->current++ & 0x80) && (bitpos < (sizeof(int32_t)*8))) {
+ ret |= (*buf->current & 0x7F) << bitpos;
+ bitpos += 7;
+ }
+ return neg ? -ret : ret;
+}
+
+float serial_decode_float(struct byte_array* buf)
+{
+ float f;
+ uint8_t *uf = (uint8_t*)&f;
+ for (int i=4; i; i--) {
+ *uf = *buf->current;
+ uf++;
+ buf->current++;
+ }
+ //DEBUGPRINT("serial_decode_float %f\n", f);
+ return f;
+}
+
+struct byte_array* serial_decode_string(struct byte_array* buf)
+{
+ null_check(buf);
+ int32_t len = serial_decode_int(buf);
+ assert_message(len>=0, "negative malloc");
+ struct byte_array* ba = byte_array_new_size(len);
+ ba->data = ba->current = (uint8_t*)malloc(len);
+ null_check(ba->data);
+ memcpy(ba->data, buf->current, len);
+ buf->current += len;
+ return ba;
+}
+
+void serial_decode(struct byte_array* buf, serial_element se, const void* extra)
+{
+// DEBUGPRINT("serial_decode %d %x<%x?\n", buf->size, buf->current, buf->data + buf->size);
+ while (buf->current < buf->data + buf->length)
+ {
+ // get key and wire type
+ int32_t keyWire = serial_decode_int(buf);
+ struct key_value_pair pair = {
+ .key = keyWire >> 2,
+ .wire_type = (enum serial_type)(keyWire & 0x03)
+ };
+// DEBUGPRINT("serial_decode %d:%d\n", pair.key, pair.wire_type);
+
+ // get data
+ switch(pair.wire_type) {
+ case SERIAL_INT: /* int */
+ pair.value.integer = serial_decode_int(buf);
+ break;
+ case SERIAL_FLOAT:
+ pair.value.floater = serial_decode_float(buf);
+ case SERIAL_STRING: /* bytes */
+ pair.value.bytes = serial_decode_string(buf);
+ break;
+ case SERIAL_ARRAY:
+ break;
+ default:
+ DEBUGPRINT("serial_decode ?\n");
+ break;
+ }
+ if (se(&pair, buf, extra)) {
+// DEBUGPRINT("serial_decode: break\n");
+ break;
+ }
+ }
+// DEBUGPRINT("serial_decode done\n");
+}
+
+// assume little endian
+struct byte_array *encode_float(struct byte_array *buf, float f)
+{
+ assert_message(sizeof(float)==4, "bad float size");
+ uint8_t *uf = (uint8_t*)&f;
+ for (int i=4; i; i--) {
+ byte_array_add_byte(buf, *uf);
+ uf++;
+ }
+ return buf;
+}
+
+struct byte_array* serial_encode_float(struct byte_array* buf, int32_t key, float value) {
+ if (!buf)
+ buf = byte_array_new();
+ if (key)
+ encode_int(buf, key<<2 | SERIAL_FLOAT);
+ encode_float(buf, value);
+ return buf;
+}
+
+uint8_t serial_encode_string_size(int32_t key, const struct byte_array* string) {
+ if (!string)
+ return 0;
+ return (key ? encode_int_size(key) : 0) +
+ encode_int_size(string->length) +
+ string->length;
+}
+
+struct byte_array* serial_encode_string(struct byte_array* buf, int32_t key, const struct byte_array* bytes)
+{
+ if (!bytes)
+ return buf;
+ if (!buf)
+ buf = byte_array_new();
+
+ if (key)
+ encode_int(buf, key<<2 | SERIAL_STRING);
+ encode_int(buf, bytes->length);
+ byte_array_resize(buf, buf->length + bytes->length);
+ memcpy(buf->current, bytes->data, bytes->length);
+
+ buf->current = buf->data + buf->length;
+ return buf;
+}
+
+struct byte_array* serial_encode_array(struct byte_array* buf, int32_t key, int32_t count) {
+ if (!buf) buf = byte_array_new();
+ encode_int(buf, key<<2 | SERIAL_ARRAY);
+ encode_int(buf, count);
+ return buf;
+}
+
+#ifdef DEBUG
+
+bool display_serial(const struct key_value_pair* kvp) {
+ DEBUGPRINT("serialElementDebug %d:\t", kvp->key);
+ char* str;
+
+ switch (kvp->wire_type) {
+ case SERIAL_ERROR:
+ DEBUGPRINT("error %d\n", kvp->value.serialError);
+ break;
+ case SERIAL_INT:
+ DEBUGPRINT("int %d\n", kvp->value.integer);
+ break;
+ case SERIAL_FLOAT:
+ DEBUGPRINT("float %f\n", kvp->value.floater)
+ case SERIAL_STRING:
+ str = (char*)malloc(kvp->value.bytes->length + 1);
+ memcpy(str, kvp->value.bytes->data, kvp->value.bytes->length);
+ str[kvp->value.bytes->length] = 0;
+ DEBUGPRINT("bytes %s\n", str);
+ break;
+ case SERIAL_ARRAY:
+ DEBUGPRINT("array\n");
+ break;
+ }
+ return true;
+}
+
+#endif // DEBUG
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/serial.h Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,68 @@
+/* serial.h
+ *
+ * [de]serialization API
+ */
+
+#ifndef SERIAL_H
+#define SERIAL_H
+
+
+#include <stdint.h>
+#include "struct.h"
+
+
+enum serial_type {
+ SERIAL_ERROR,
+ SERIAL_INT,
+ SERIAL_FLOAT,
+ SERIAL_STRING,
+ SERIAL_ARRAY,
+};
+
+
+struct key_value_pair
+{
+ int32_t key;
+
+ enum serial_type wire_type;
+
+ union {
+
+ int32_t integer;
+ float floater;
+ struct byte_array* bytes;
+ enum {
+ SOMETHING_HAS_GONE_HORRIBLY_WRONG,
+ } serialError;
+
+ } value;
+};
+
+
+typedef bool (serial_element)(const struct key_value_pair*,
+ struct byte_array* bytes,
+ const void* extra);
+bool serial_element_debug(const struct key_value_pair* kvp);
+
+struct byte_array* serial_encode_int(struct byte_array* buf,
+ int32_t key,
+ int32_t value);
+
+struct byte_array *serial_encode_float(struct byte_array *buf,
+ int32_t key,
+ float value);
+
+struct byte_array* serial_encode_string(struct byte_array* buf,
+ int32_t key,
+ const struct byte_array* string);
+void serial_decode(struct byte_array* buf,
+ serial_element* se,
+ const void* extra);
+
+int32_t serial_decode_int(struct byte_array* buf);
+
+float serial_decode_float(struct byte_array* buf);
+
+struct byte_array* serial_decode_string(struct byte_array* buf);
+
+#endif // SERIAL_H
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/struct.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,516 @@
+/* struct.c
+ *
+ * implements array, byte_array, lifo and map
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+#include <assert.h>
+#include <ctype.h>
+
+#include "vm.h"
+#include "struct.h"
+#include "util.h"
+
+#define BYTE_ARRAY_MAX_LEN 10000
+#define ERROR_BYTE_ARRAY_LEN "byte array too long"
+
+
+// array ///////////////////////////////////////////////////////////////////
+
+struct array *array_new() {
+ return array_new_size(0);
+}
+
+struct array *array_new_size(uint32_t size) {
+ struct array *a = (struct array*)malloc(sizeof(struct array));
+ a->data = a->current = NULL;
+ a->length = 0;
+ return a;
+}
+
+void array_del(struct array *a) {
+ for (int i=0; i<a->length; i++)
+ free(array_get(a, i));
+ free(a->data);
+ free(a);
+}
+
+void array_resize(struct array *a, uint32_t length) {
+ a->data = (void**)realloc(a->data, length * sizeof(void*));
+ null_check(a->data);
+ memset(&a->data[a->length], 0, length-a->length);
+ a->length = length;
+}
+
+uint32_t array_add(struct array *a, void *datum) {
+ a->data = (void**)realloc(a->data, (a->length+1) * sizeof(void*));
+ a->data[a->length++] = datum;
+ return a->length-1;
+}
+
+void array_insert(struct array *a, uint32_t index, void *datum)
+{
+ a->data = (void**)realloc(a->data, (a->length+1) * sizeof(void*));
+ uint32_t i;
+ for (i=a->length; i>index; i--)
+ a->data[i] = a->data[i-1];
+ a->data[i] = datum;
+ a->length++;
+}
+
+void* array_get(const struct array *a, uint32_t index) {
+ assert_message(a && index < a->length, ERROR_INDEX);
+ //DEBUGPRINT("array_get %d = %x\n", index, a->data[index]);
+ return a->data[index];
+}
+
+void array_set(struct array *a, uint32_t index, void* datum) {
+ null_check(a);
+ null_check(datum);
+ if (a->length <= index)
+ array_resize(a, index+1);
+ //DEBUGPRINT("array_set %d %x\n", index, datum);
+ a->data[index] = datum;
+}
+
+void *list_remove(void *data, uint32_t *end, uint32_t start, int32_t length, size_t width)
+{
+ null_check(data);
+ null_check(end);
+ length = length < 0 ? *end - start : length;
+ assert_message(start < *end && start+length <= *end, "index out of bounds");
+
+ memmove((uint8_t*)data+start*width, (uint8_t*)data+(start+length)*width, (*end-start-length)*width);
+ *end -= (uint32_t)length;
+ return realloc(data, *end * width);
+}
+
+void array_remove(struct array *self, uint32_t start, int32_t length) {
+ self->data = (void**)list_remove(self->data, &self->length, start, length, sizeof(void*));
+}
+
+struct array *array_copy(const struct array* original) {
+ if (!original)
+ return NULL;
+ struct array* copy = (struct array*)malloc(sizeof(struct array));
+ copy->data = (void**)malloc(original->length);
+ memcpy(copy->data, original->data, original->length);
+ copy->length = original->length;
+ copy->current = copy->data + (original->current - original->data);
+ return copy;
+}
+
+struct array *array_part(struct array *within, uint32_t start, uint32_t length)
+{
+ struct array *p = array_copy(within);
+ array_remove(p, start+length, within->length-start-length);
+ array_remove(p, 0, start);
+ return p;
+}
+
+void array_append(struct array *a, const struct array* b)
+{
+ null_check(a);
+ null_check(b);
+ array_resize(a, a->length + b->length);
+ memcpy(&a->data[a->length], b->data, b->length);
+ a->current = a->data + a->length;
+}
+
+// byte_array ///////////////////////////////////////////////////////////////
+
+struct byte_array *byte_array_new() {
+ struct byte_array* ba = (struct byte_array*)malloc(sizeof(struct byte_array));
+ ba->data = ba->current = 0;
+ ba->length = 0;
+ return ba;
+}
+
+void byte_array_del(struct byte_array* ba) {
+ if (ba->data)
+ free(ba->data);
+ free(ba);
+}
+
+struct byte_array *byte_array_new_size(uint32_t size) {
+ struct byte_array* ba = (struct byte_array*)malloc(sizeof(struct byte_array));
+ ba->data = ba->current = (uint8_t*)malloc(size);
+ ba->length = size;
+ return ba;
+}
+
+void byte_array_resize(struct byte_array* ba, uint32_t size) {
+ assert_message(ba->current >= ba->data, "byte_array corrupt");
+ uint32_t delta = ba->current - ba->data;
+ ba->data = (uint8_t*)realloc(ba->data, size);
+ assert(ba->data);
+ ba->current = ba->data + delta;
+ ba->length = size;
+}
+
+bool byte_array_equals(const struct byte_array *a, const struct byte_array* b) {
+ if (a==b)
+ return true;
+ if (!a != !b) // one is null and the other is not
+ return false;
+ if (a->length != b->length)
+ return false;
+
+ int i;
+ for (i = 0; i<a->length; i++)
+ if (a->data[i] != b->data[i])
+ return false;
+ return true;
+}
+
+struct byte_array *byte_array_copy(const struct byte_array* original) {
+ if (!original)
+ return NULL;
+ struct byte_array* copy = (struct byte_array*)malloc(sizeof(struct byte_array));
+ copy->data = (uint8_t*)malloc(original->length);
+ memcpy(copy->data, original->data, original->length);
+ copy->length = original->length;
+ copy->current = copy->data + (original->current - original->data);
+ return copy;
+}
+
+void byte_array_append(struct byte_array *a, const struct byte_array* b) {
+ null_check(a);
+ null_check(b);
+ uint32_t offset = a->length;
+ byte_array_resize(a, a->length + b->length);
+ memcpy(&a->data[offset], b->data, b->length);
+ a->current = a->data + a->length;
+}
+
+void byte_array_remove(struct byte_array *self, uint32_t start, int32_t length) {
+ self->data = (uint8_t*)list_remove(self->data, &self->length, start, length, sizeof(uint8_t));
+}
+
+struct byte_array *byte_array_part(struct byte_array *within, uint32_t start, uint32_t length)
+{
+ struct byte_array *p = byte_array_copy(within);
+ byte_array_remove(p, start+length, within->length-start-length);
+ byte_array_remove(p, 0, start);
+ return p;
+}
+
+struct byte_array *byte_array_from_string(const char* str)
+{
+ int len = strlen(str);
+ struct byte_array* ba = byte_array_new_size(len);
+ memcpy(ba->data, str, len);
+ return ba;
+}
+
+char* byte_array_to_string(const struct byte_array* ba)
+{
+ int len = ba->length;
+ char* s = (char*)malloc(len+1);
+ memcpy(s, ba->data, len);
+ s[len] = 0;
+ return s;
+}
+
+void byte_array_reset(struct byte_array* ba) {
+ ba->current = ba->data;
+}
+
+struct byte_array *byte_array_concatenate(int n, const struct byte_array* ba, ...)
+{
+ struct byte_array* result = byte_array_copy(ba);
+
+ va_list argp;
+ for(va_start(argp, ba); --n;) {
+ struct byte_array* parameter = va_arg(argp, struct byte_array* );
+ if (!parameter)
+ continue;
+ assert_message(result->length + parameter->length < BYTE_ARRAY_MAX_LEN, ERROR_BYTE_ARRAY_LEN);
+ byte_array_append(result, parameter);
+ }
+
+ va_end(argp);
+
+ if (result)
+ result->current = result->data + result->length;
+ return result;
+}
+
+struct byte_array *byte_array_add_byte(struct byte_array *a, uint8_t b) {
+ byte_array_resize(a, a->length+1);
+ a->current = a->data + a->length;
+ a->data[a->length-1] = b;
+ return a;
+}
+
+void byte_array_print(const char* text, const struct byte_array* ba) {
+ int offset = ba->current-ba->data;
+ if (text)
+ printf("%s @%d\n", text, offset);
+ for (int i=0; i<ba->length; i++)
+ printf("\t%s%d\n", i==offset?">":" ", ba->data[i]);
+}
+
+int32_t byte_array_find(struct byte_array *within, struct byte_array *sought, uint32_t start)
+{
+ null_check(within);
+ null_check(sought);
+
+ uint32_t ws = within->length;
+ uint32_t ss = sought->length;
+ assert_message(start < within->length, "out of bounds");
+
+ uint8_t *wd = within->data;
+ uint8_t *sd = sought->data;
+ for (int32_t i=start; i<ws-ss+1; i++)
+ if (!memcmp(wd + i, sd, ss))
+ return i;
+
+ return -1;
+}
+
+struct byte_array *byte_array_replace(struct byte_array *within, struct byte_array *replacement, uint32_t start, int32_t length)
+{
+ null_check(within);
+ null_check(replacement);
+ uint32_t ws = within->length;
+ assert_message(start < ws, "index out of bounds");
+ if (length < 0)
+ length = ws - start;
+
+ int32_t new_length = within->length - length + replacement->length;
+ struct byte_array *replaced = byte_array_new_size(new_length);
+
+ memcpy(replaced->data, within->data, start);
+ memcpy(replaced->data + start, replacement->data, replacement->length);
+ memcpy(replaced->data + start + replacement->length, within->data + start + length, within->length - start - length);
+
+ return replaced;
+}
+
+
+// stack ////////////////////////////////////////////////////////////////////
+
+struct stack* stack_new() {
+ return (struct stack*)calloc(sizeof(struct stack), 1);
+}
+
+struct stack_node* stack_node_new() {
+ return (struct stack_node*)calloc(sizeof(struct stack_node), 1);
+}
+
+void stack_push(struct stack* stack, void* data)
+{
+ null_check(data);
+ if (!stack->head)
+ stack->head = stack->tail = stack_node_new();
+ else {
+ struct stack_node* old_head = stack->head;
+ stack->head = stack_node_new();
+ null_check(stack->head);
+ stack->head->next = old_head;
+ }
+ stack->head->data = data;
+}
+
+void* stack_pop(struct stack* stack)
+{
+ if (!stack->head)
+ return NULL;
+ void* data = stack->head->data;
+ stack->head = stack->head->next;
+ null_check(data);
+ return data;
+}
+
+void* stack_peek(const struct stack* stack, uint8_t index)
+{
+ null_check(stack);
+ struct stack_node*p = stack->head;
+ for (; index && p; index--, p=p->next);
+ return p ? p->data : NULL;
+}
+
+bool stack_empty(const struct stack* stack)
+{
+ null_check(stack);
+ return stack->head == NULL;// && stack->tail == NULL;
+}
+
+// map /////////////////////////////////////////////////////////////////////
+
+static size_t def_hash_func(const struct byte_array* key)
+{
+ size_t hash = 0;
+ int i = 0;
+ for (i = 0; i<key->length; i++)
+ hash += key->data[i];
+ return hash;
+}
+
+struct map* map_new()
+{
+ struct map* m;
+ if (!(m =(struct map*)malloc(sizeof(struct map)))) return NULL;
+ m->size = 16;
+ m->hash_func = def_hash_func;
+
+ if (!(m->nodes = (struct hash_node**)calloc(m->size, sizeof(struct hash_node*)))) {
+ free(m);
+ return NULL;
+ }
+
+ return m;
+}
+
+void map_del(struct map* m)
+{
+ DEBUGPRINT("map_destroy\n");
+ size_t n;
+ struct hash_node *node, *oldnode;
+
+ for(n = 0; n<m->size; ++n) {
+ node = m->nodes[n];
+ while (node) {
+ byte_array_del(node->key);
+ oldnode = node;
+ node = node->next;
+ free(oldnode);
+ }
+ }
+ free(m->nodes);
+ free(m);
+}
+
+int map_insert(struct map* m, const struct byte_array* key, void *data)
+{
+ struct hash_node *node;
+ size_t hash = m->hash_func(key) % m->size;
+
+ node = m->nodes[hash];
+ while (node) {
+ if (byte_array_equals(node->key, key)) {
+ node->data = data;
+ return 0;
+ }
+ node = node->next;
+ }
+
+ if (!(node = (struct hash_node*)malloc(sizeof(struct hash_node))))
+ return -1;
+ if (!(node->key = byte_array_copy(key))) {
+ free(node);
+ return -1;
+ }
+ node->data = data;
+ node->next = m->nodes[hash];
+ m->nodes[hash] = node;
+
+ return 0;
+}
+
+struct array* map_keys(const struct map* m) {
+ struct array *a = array_new();
+ for (int i=0; i<m->size; i++)
+ for (const struct hash_node* n = m->nodes[i]; n; n=n->next)
+ if (n->data)
+ array_add(a, n->key);
+ return a;
+}
+
+struct array* map_values(const struct map* m) {
+ struct array *a = array_new();
+ for (int i=0; i<m->size; i++)
+ for (const struct hash_node* n = m->nodes[i]; n; n=n->next)
+ if (n->data)
+ array_add(a, n->data);
+ return a;
+}
+
+int map_remove(struct map* m, const struct byte_array* key)
+{
+ struct hash_node *node, *prevnode = NULL;
+ size_t hash = m->hash_func(key)%m->size;
+
+ node = m->nodes[hash];
+ while(node) {
+ if (byte_array_equals(node->key, key)) {
+ byte_array_del(node->key);
+ if (prevnode) prevnode->next = node->next;
+ else m->nodes[hash] = node->next;
+ free(node);
+ return 0;
+ }
+ prevnode = node;
+ node = node->next;
+ }
+ return -1;
+}
+
+bool map_has(const struct map* m, const struct byte_array* key) {
+ struct hash_node *node;
+ size_t hash = m->hash_func(key) % m->size;
+ node = m->nodes[hash];
+ while (node) {
+ if (byte_array_equals(node->key, key))
+ return true;
+ node = node->next;
+ }
+ return false;
+}
+
+void *map_get(const struct map* m, const struct byte_array* key)
+{
+ struct hash_node *node;
+ size_t hash = m->hash_func(key) % m->size;
+ node = m->nodes[hash];
+ while (node) {
+ if (byte_array_equals(node->key, key))
+ return node->data;
+ node = node->next;
+ }
+ return NULL;
+}
+
+int map_resize(struct map* m, size_t size)
+{
+ DEBUGPRINT("map_resize\n");
+ struct map newtbl;
+ size_t n;
+ struct hash_node *node,*next;
+
+ newtbl.size = size;
+ newtbl.hash_func = m->hash_func;
+
+ if (!(newtbl.nodes = (struct hash_node**)calloc(size, sizeof(struct hash_node*))))
+ return -1;
+
+ for(n = 0; n<m->size; ++n) {
+ for(node = m->nodes[n]; node; node = next) {
+ next = node->next;
+ map_insert(&newtbl, node->key, node->data);
+ map_remove(m, node->key);
+
+ }
+ }
+
+ free(m->nodes);
+ m->size = newtbl.size;
+ m->nodes = newtbl.nodes;
+
+ return 0;
+}
+
+// in case of intersection, a wins
+void map_update(struct map *a, const struct map *b)
+{
+ const struct array *keys = map_keys(b);
+ for (int i=0; i<keys->length; i++) {
+ const struct byte_array *key = (const struct byte_array*)array_get(keys, i);
+ if (!map_has(a, key))
+ map_insert(a, key, map_get(b, key));
+ }
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/struct.h Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,108 @@
+/* struct.h
+ *
+ * APIs for array, byte_array, [f|l]ifo and map
+ */
+
+#ifndef STRUCT_H
+#define STRUCT_H
+
+
+#include <inttypes.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+
+#define ERROR_INDEX "index out of bounds"
+#define ERROR_NULL "null pointer"
+
+
+// array ///////////////////////////////////////////////////////////////////
+
+struct array {
+ void **data, **current;
+ uint32_t length;
+};
+
+struct array *array_new();
+void array_del(struct array *a);
+struct array *array_new_size(uint32_t size);
+void array_resize(struct array *a, uint32_t length);
+uint32_t array_add(struct array *a , void *datum);
+void array_insert(struct array *a, uint32_t index, void *datam);
+void* array_get(const struct array *a, uint32_t index);
+void array_set(struct array *a, uint32_t index, void *datum);
+void array_remove(struct array *a, uint32_t start, int32_t length);
+struct array *array_part(struct array *within, uint32_t start, uint32_t length);
+void array_append(struct array *a, const struct array* b);
+
+// byte_array ///////////////////////////////////////////////////////////////
+
+struct byte_array {
+ uint8_t *data, *current;
+ uint32_t length;
+};
+
+struct byte_array *byte_array_new();
+struct byte_array *byte_array_new_size(uint32_t size);
+void byte_array_append(struct byte_array *a, const struct byte_array* b);
+struct byte_array *byte_array_from_string(const char* str);
+char* byte_array_to_string(const struct byte_array* ba);
+void byte_array_del(struct byte_array* ba);
+struct byte_array *byte_array_copy(const struct byte_array* original);
+struct byte_array *byte_array_add_byte(struct byte_array *a, uint8_t b);
+void byte_array_reset(struct byte_array* ba);
+void byte_array_resize(struct byte_array* ba, uint32_t size);
+bool byte_array_equals(const struct byte_array *a, const struct byte_array* b);
+struct byte_array *byte_array_concatenate(int n, const struct byte_array* ba, ...);
+void byte_array_print(const char* text, const struct byte_array* ba);
+int32_t byte_array_find(struct byte_array *within, struct byte_array *sought, uint32_t start);
+struct byte_array *byte_array_part(struct byte_array *within, uint32_t start, uint32_t length);
+void byte_array_remove(struct byte_array *within, uint32_t start, int32_t length);
+struct byte_array *byte_array_replace(struct byte_array *within, struct byte_array *replacement, uint32_t start, int32_t length);
+
+// stack ////////////////////////////////////////////////////////////////////
+
+struct stack_node {
+ void* data;
+ struct stack_node* next;
+};
+
+struct stack {
+ struct stack_node* head;
+ struct stack_node* tail;
+};
+
+struct stack* stack_new();
+struct stack_node* stack_node_new();
+void fifo_push(struct stack* fifo, void* data);
+void stack_push(struct stack* stack, void* data);
+void* stack_pop(struct stack* stack);
+void* stack_peek(const struct stack* stack, uint8_t index);
+bool stack_empty(const struct stack* stack);
+
+// map /////////////////////////////////////////////////////////////////////
+
+struct hash_node {
+ struct byte_array *key;
+ void *data;
+ struct hash_node *next;
+};
+
+struct map {
+ size_t size;
+ struct hash_node **nodes;
+ size_t (*hash_func)(const struct byte_array*);
+};
+
+struct map* map_new();
+void map_del(struct map* map);
+int map_insert(struct map* map, const struct byte_array *key, void *data);
+int map_remove(struct map* map, const struct byte_array *key);
+void *map_get(const struct map* map, const struct byte_array *key);
+bool map_has(const struct map* map, const struct byte_array *key);
+int map_resize(struct map* map, size_t size);
+struct array* map_keys(const struct map* m);
+struct array* map_values(const struct map* m);
+void map_update(struct map *a, const struct map *b);
+
+#endif // STRUCT_H
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sys.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,430 @@
+#include "serial.h"
+#include "sys.h"
+#include "struct.h"
+#include "variable.h"
+#include "vm.h"
+#include "util.h"
+#include <stdio.h>
+#include <string.h>
+
+// system functions
+
+void sys_callback2c(struct Context *context)
+{
+ stack_pop(context->rhs); // self
+ context->callback2c(context);
+}
+
+void sys_print(struct Context *context)
+{
+ stack_pop(context->rhs); // self
+ struct variable *v;
+ while ((v = (struct variable*)stack_pop(context->rhs)))
+ printf("%s\n", variable_value_str(context, v));
+}
+
+void sys_save(struct Context *context)
+{
+ stack_pop(context->rhs); // self
+ struct variable *v = (struct variable*)stack_pop(context->rhs);
+ struct variable *path = (struct variable*)stack_pop(context->rhs);
+ variable_save(context, v, path);
+}
+
+void sys_load(struct Context *context)
+{
+ stack_pop(context->rhs); // self
+ struct variable *path = (struct variable*)stack_pop(context->rhs);
+ struct variable *v = variable_load(context, path);
+
+ if (v)
+ stack_push(context->operand_stack, v);
+}
+
+void sys_rm(struct Context *context)
+{
+ stack_pop(context->rhs); // self
+ struct variable *path = (struct variable*)(struct variable*)stack_pop(context->rhs);
+ remove(byte_array_to_string(path->str));
+}
+
+struct string_func builtin_funcs[] = {
+ {"yield", (bridge*)&sys_callback2c},
+ {"print", (bridge*)&sys_print},
+ {"save", (bridge*)&sys_save},
+ {"load", (bridge*)(bridge*)&sys_load},
+ {"remove", (bridge*)&sys_rm},
+};
+
+struct variable *func_map(struct Context *context)
+{
+ struct map *map = map_new();
+ for (int i=0; i<ARRAY_LEN(builtin_funcs); i++) {
+ struct byte_array *name = byte_array_from_string(builtin_funcs[i].name);
+ struct variable *value = variable_new_c(context, builtin_funcs[i].func);
+ map_insert(map, name, value);
+ }
+ return variable_new_map(context, map);
+}
+
+// built-in member functions
+
+#define FNC_STRING "string"
+#define FNC_LIST "list"
+#define FNC_TYPE "type"
+#define FNC_LENGTH "length"
+#define FNC_KEYS "keys"
+#define FNC_VALUES "values"
+#define FNC_SERIALIZE "serialize"
+#define FNC_DESERIALIZE "deserialize"
+#define FNC_SORT "sort"
+#define FNC_FIND "find"
+#define FNC_REPLACE "replace"
+#define FNC_PART "part"
+#define FNC_REMOVE "remove"
+#define FNC_INSERT "insert"
+
+struct variable *comparator = NULL;
+
+int (compar)(struct Context *context, const void *a, const void *b)
+{
+ struct variable *av = *(struct variable**)a;
+ struct variable *bv = *(struct variable**)b;
+
+ if (comparator) {
+
+ assert_message(comparator->type == VAR_FNC, "non-function comparator");
+ stack_push(context->rhs, av);
+ stack_push(context->rhs, bv);
+ byte_array_reset(comparator->str);
+ stack_push(context->operand_stack, comparator);
+ vm_call(context);
+
+ struct variable *result = (struct variable*)stack_pop(context->rhs);
+ assert_message(result->type == VAR_INT, "non-integer comparison result");
+ return result->integer;
+
+ } else {
+
+ enum VarType at = av->type;
+ enum VarType bt = bv->type;
+
+ if (at == VAR_INT && bt == VAR_INT) {
+ // DEBUGPRINT("compare %p:%d to %p:%d : %d\n", av, av->integer, bv, bv->integer, av->integer - bv->integer);
+ return av->integer - bv->integer;
+ } else
+ DEBUGPRINT("can't compare %s to %s\n", var_type_str(at), var_type_str(bt));
+
+ vm_exit_message(context, "incompatible types for comparison");
+ return 0;
+ }
+}
+
+int testarr[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
+//int testarr[] = { 2,1 };
+int len = sizeof(testarr)/sizeof(testarr[0]);
+
+void heapset(size_t width, void *base0, uint32_t index0, void *base1, uint32_t index1) {
+ uint8_t *p0 = (uint8_t*)base0 + index0 * width;
+ uint8_t *p1 = (uint8_t*)base1 + index1 * width;
+ while (width--)
+ *(p0 + width) = *(p1 + width);
+}
+
+int heapcmp(struct Context *context,
+ int (*compar)(struct Context *, const void *, const void *),
+ size_t width, void *base0, uint32_t index0, void *base1, uint32_t index1) {
+ uint8_t *p0 = (uint8_t*)base0 + index0 * width;
+ uint8_t *p1 = (uint8_t*)base1 + index1 * width;
+ return compar(context, p0, p1);
+}
+
+int heapsortfg(struct Context *context,
+ void *base, size_t nel, size_t width,
+ int (*compar)(struct Context *, const void *, const void *))
+{
+ void *t = malloc(width); // the temporary value
+ unsigned int n = nel, parent = nel/2, index, child; // heap indexes
+ for (;;) { // loop until array is sorted
+ if (parent > 0) { // first stage - Sorting the heap
+ heapset(width, t, 0, base, --parent);
+ } else { // second stage - Extracting elements in-place
+ if (!--n) { // make the heap smaller
+ free(t);
+ return 0; // When the heap is empty, we are done
+ }
+ heapset(width, t, 0, base, n);
+ heapset(width, base, n, base, 0);
+ }
+ // insert operation - pushing t down the heap to replace the parent
+ index = parent; // start at the parent index
+ child = index * 2 + 1; // get its left child index
+ while (child < n) {
+ if (child + 1 < n && // choose the largest child
+ heapcmp(context, compar, width, base, child+1, base, child) > 0) {
+ child++; // right child exists and is bigger
+ }
+ // is the largest child larger than the entry?
+ if (heapcmp(context, compar, width, base, child, t, 0) > 0) {
+ heapset(width, base, index, base, child);
+ index = child; // move index to the child
+ child = index * 2 + 1; // get the left child and go around again
+ } else
+ break; // t's place is found
+ }
+ // store the temporary value at its new location
+ heapset(width, base, index, t, 0);
+ }
+}
+
+void cfnc_sort(struct Context *context)
+{
+ struct variable *self = (struct variable*)stack_pop(context->rhs);
+ assert_message(self->type == VAR_LST, "sorting a non-list");
+ comparator = (struct variable*)stack_pop(context->rhs);
+
+ int num_items = self->list->length;
+
+ int success = heapsortfg(context, self->list->data, num_items, sizeof(struct variable*), &compar);
+ assert_message(!success, "error sorting");
+}
+
+struct variable *variable_part(struct Context *context, struct variable *self, uint32_t start, int32_t length)
+{
+ null_check(self);
+ switch (self->type) {
+ case VAR_STR: {
+ struct byte_array *str = byte_array_part(self->str, start, length);
+ return variable_new_str(context, str);
+ }
+ case VAR_LST: {
+ struct array *list = array_part(self->list, start, length);
+ return variable_new_list(context, list);
+ }
+ default:
+ return (struct variable*)exit_message("bad part type");
+ }
+}
+
+void variable_remove(struct variable *self, uint32_t start, int32_t length)
+{
+ null_check(self);
+ switch (self->type) {
+ case VAR_STR:
+ byte_array_remove(self->str, start, length);
+ break;
+ case VAR_LST:
+ array_remove(self->list, start, length);
+ break;
+ default:
+ exit_message("bad remove type");
+ }
+}
+
+struct variable *variable_concatenate(struct Context *context, int n, const struct variable* v, ...)
+{
+ struct variable* result = variable_copy(context, v);
+
+ va_list argp;
+ for(va_start(argp, v); --n;) {
+ struct variable* parameter = va_arg(argp, struct variable* );
+ if (!parameter)
+ continue;
+ else if (!result)
+ result = variable_copy(context, parameter);
+ else switch (result->type) {
+ case VAR_STR: byte_array_append(result->str, parameter->str); break;
+ case VAR_LST: array_append(result->list, parameter->list); break;
+ default: return (struct variable*)exit_message("bad concat type");
+ }
+ }
+
+ va_end(argp);
+ return result;
+}
+
+void cfnc_chop(struct Context *context, bool part)
+{
+ struct variable *self = (struct variable*)stack_pop(context->rhs);
+ struct variable *start = (struct variable*)stack_pop(context->rhs);
+ struct variable *length = (struct variable*)stack_pop(context->rhs);
+ assert_message(start->type == VAR_INT, "non-integer index");
+ assert_message(length->type == VAR_INT, "non-integer length");
+ int32_t beginning = start->integer;
+ int32_t foraslongas = length->integer;
+
+ struct variable *result = variable_copy(context, self);
+ if (part)
+ result = variable_part(context, result, beginning, foraslongas);
+ else
+ variable_remove(result, beginning, foraslongas);
+ stack_push(context->operand_stack, result);
+}
+
+static inline void cfnc_part(struct Context *context) {
+ cfnc_chop(context, true);
+}
+
+static inline void cfnc_remove(struct Context *context) {
+ cfnc_chop(context, false);
+}
+
+void cfnc_find(struct Context *context)
+{
+ struct variable *self = (struct variable*)stack_pop(context->rhs);
+ struct variable *sought = (struct variable*)stack_pop(context->rhs);
+ struct variable *start = (struct variable*)stack_pop(context->rhs);
+
+ null_check(self);
+ null_check(sought);
+ assert_message(self->type == VAR_STR, "searching in a non-list");
+ assert_message(sought->type == VAR_STR, "searching for a non-list");
+ if (start) assert_message(start->type == VAR_INT, "non-integer index");
+
+ int32_t beginning = start ? start->integer : 0;
+ int32_t index = byte_array_find(self->str, sought->str, beginning);
+ struct variable *result = variable_new_int(context, index);
+ stack_push(context->operand_stack, result);
+}
+
+void cfnc_insert(struct Context *context)
+{
+ struct variable *self = (struct variable*)stack_pop(context->rhs);
+ struct variable *start = (struct variable*)stack_pop(context->rhs);
+ struct variable *insertion = (struct variable*)stack_pop(context->rhs);
+ assert_message(start->type == VAR_INT, "non-integer index");
+ assert_message(insertion && insertion->type == self->type, "insertion doesn't match destination");
+
+ int32_t position = start->integer;
+ struct variable *first = variable_part(context, variable_copy(context, self), 0, position);
+ struct variable *second = variable_part(context, variable_copy(context, self), position, -1);
+ struct variable *joined = variable_concatenate(context, 3, first, self, second);
+ stack_push(context->operand_stack, joined);
+}
+
+// a b c
+// <sought> <replacement> [<start>]
+// <start> <length> <replacement>
+void replace(struct Context *context)
+{
+ struct variable *self = (struct variable*)stack_pop(context->rhs);
+ struct variable *a = (struct variable*)stack_pop(context->rhs);
+ struct variable *b = (struct variable*)stack_pop(context->rhs);
+ struct variable *c = (struct variable*)stack_pop(context->rhs);
+
+ null_check(self);
+ null_check(b);
+ assert_message(self->type == VAR_STR, "searching in a non-string");
+
+ int32_t where = 0;
+ struct byte_array *replaced = self->str;
+
+ if (a->type == VAR_STR) { // find a, replace with b
+
+ assert_message(b->type == VAR_STR, "non-string replacement");
+
+ if (c) { // replace first match after index b
+
+ assert_message(c->type == VAR_INT, "non-integer index");
+ uint32_t found = byte_array_find(self->str, a->str, c->integer);
+ replaced = byte_array_replace(self->str, b->str, found, b->str->length);
+
+ } else for(;;) { // replace all
+
+ if ((where = byte_array_find(self->str, a->str, where)) < 0)
+ break;
+ replaced = byte_array_replace(replaced, b->str, where++, a->str->length);
+ }
+
+ } else if (a->type == VAR_INT ) { // replace at index a, length b, insert c
+
+ assert_message(a || a->type == VAR_INT, "non-integer count");
+ assert_message(b || b->type == VAR_INT, "non-integer start");
+ replaced = byte_array_replace(self->str, c->str, a->integer, b->integer);
+
+ } else exit_message("replacement is not a string");
+
+ null_check(replaced);
+ struct variable *result = variable_new_str(context, replaced);
+ stack_push(context->operand_stack, result);
+}
+
+
+struct variable *builtin_method(struct Context *context,
+ struct variable *indexable,
+ const struct variable *index)
+{
+ enum VarType it = indexable->type;
+ const char *idxstr = byte_array_to_string(index->str);
+
+ if (!strcmp(idxstr, FNC_LENGTH))
+ return variable_new_int(context, indexable->list->length);
+ if (!strcmp(idxstr, FNC_TYPE)) {
+ const char *typestr = var_type_str(it);
+ return variable_new_str(context, byte_array_from_string(typestr));
+ }
+
+ if (!strcmp(idxstr, FNC_STRING))
+ return variable_new_str(context, variable_value(context, indexable));
+
+ if (!strcmp(idxstr, FNC_LIST))
+ return variable_new_list(context, indexable->list);
+
+ if (!strcmp(idxstr, FNC_KEYS)) {
+ assert_message(it == VAR_LST || it == VAR_MAP, "keys are only for map or list");
+
+ struct variable *v = variable_new_list(context, array_new());
+ if (indexable->map) {
+ const struct array *a = map_keys(indexable->map);
+ for (int i=0; i<a->length; i++) {
+ struct variable *u = variable_new_str(context, (struct byte_array*)array_get(a, i));
+ array_add(v->list, u);
+ }
+ }
+ return v;
+ }
+
+ if (!strcmp(idxstr, FNC_VALUES)) {
+ assert_message(it == VAR_LST || it == VAR_MAP, "values are only for map or list");
+ if (!indexable->map)
+ return variable_new_list(context, array_new());
+ else
+ return variable_new_list(context, (struct array*)map_values(indexable->map));
+ }
+
+ if (!strcmp(idxstr, FNC_SERIALIZE)) {
+ struct byte_array *bits = variable_serialize(context, 0, indexable);
+ return variable_new_str(context, bits);
+ }
+
+ if (!strcmp(idxstr, FNC_DESERIALIZE)) {
+ struct byte_array *bits = indexable->str;
+ byte_array_reset(bits);
+ struct variable *d = variable_deserialize(context, bits);
+ return d;
+ }
+
+ if (!strcmp(idxstr, FNC_SORT)) {
+ assert_message(indexable->type == VAR_LST, "sorting non-list");
+ return variable_new_c(context, &cfnc_sort);
+ }
+
+ if (!strcmp(idxstr, FNC_FIND)) {
+ assert_message(indexable->type == VAR_STR, "searching in non-string");
+ return variable_new_c(context, &cfnc_find);
+ }
+
+ if (!strcmp(idxstr, FNC_PART))
+ return variable_new_c(context, &cfnc_part);
+
+ if (!strcmp(idxstr, FNC_REMOVE))
+ return variable_new_c(context, &cfnc_remove);
+
+ if (!strcmp(idxstr, FNC_INSERT))
+ return variable_new_c(context, &cfnc_insert);
+
+ if (!strcmp(idxstr, FNC_REPLACE))
+ return variable_new_c(context, &replace);
+
+ return NULL;
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sys.h Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,23 @@
+#ifndef SYS_H
+#define SYS_H
+
+#include "vm.h"
+
+void print();
+void save();
+void load();
+void rm();
+
+struct string_func
+{
+ const char* name;
+ bridge* func;
+};
+
+struct variable *func_map(struct Context *context);
+
+struct variable *builtin_method(struct Context *context,
+ struct variable *indexable,
+ const struct variable *index);
+
+#endif // SYS_H
\ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/util.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,203 @@
+#include "struct.h"
+#include "util.h"
+#include <string.h>
+#include <stdarg.h>
+
+#ifdef ANDROID
+#include <android/log.h>
+#define TAG "filagree"
+#endif
+
+#ifdef MBED
+
+#include "mbed.h"
+
+static Serial usbTxRx(USBTX, USBRX);
+
+size_t strnlen(char *s, size_t maxlen)
+{
+ size_t i;
+ for (i= 0; i<maxlen && *s; i++, s++);
+ return i;
+}
+
+char *strnstr(const char *s, const char *find, size_t slen)
+{
+ char c, sc;
+ size_t len;
+
+ if ((c = *find++) != '\0') {
+ len = strlen(find);
+ do {
+ do {
+ if (slen-- < 1 || (sc = *s++) == '\0')
+ return (NULL);
+ } while (sc != c);
+ if (len > slen)
+ return (NULL);
+ } while (strncmp(s, find, len) != 0);
+ s--;
+ }
+ return ((char *)s);
+}
+
+#endif // MBED
+
+
+#define MESSAGE_MAX 100
+
+void log_print(const char *format, ...)
+{
+ static char log_message[MESSAGE_MAX+1] = "";
+ char one_line[MESSAGE_MAX];
+
+ char *newline;
+ va_list list;
+ va_start(list, format);
+ const char *message = make_message(format, list);
+ va_end(list);
+ size_t log_len = strnlen(log_message, MESSAGE_MAX);
+ strncat(log_message, message, MESSAGE_MAX - log_len);
+ log_len = strnlen(log_message, MESSAGE_MAX);
+ if (log_len == MESSAGE_MAX)
+ log_message[MESSAGE_MAX-1] = '\n';
+ if (!(newline = strnstr(log_message, "\n", MESSAGE_MAX)))
+ return;
+ size_t line_len = newline - log_message;
+ memcpy(one_line, log_message, line_len);
+ one_line[line_len] = 0;
+
+#ifdef ANDROID
+ __android_log_write(ANDROID_LOG_ERROR, TAG, one_line);
+#elifdef IOS
+ NSLog(@"%s", one_line);
+#elifdef MBED
+ usbTxRx.printf("%s\n", one_line);
+#else
+ printf("%s\n", one_line);
+#endif
+
+ memmove(log_message, newline+1, log_len-line_len);
+}
+
+const char *make_message(const char *format, va_list ap)
+{
+ static char message[MESSAGE_MAX];
+ vsnprintf(message, MESSAGE_MAX, format, ap);
+ return message;
+}
+
+void exit_message2(const char *format, va_list list)
+{
+ const char *message = make_message(format, list);
+ log_print("%s\n", message);
+ va_end(list);
+ exit(1);
+}
+
+void assert_message(bool assertion, const char *format, ...)
+{
+ if (assertion)
+ return;
+ va_list list;
+ va_start(list, format);
+ exit_message2(format, list);
+}
+
+void *exit_message(const char *format, ...)
+{
+ va_list list;
+ va_start(list, format);
+ exit_message2(format, list);
+ return NULL;
+}
+
+void null_check(const void *pointer) {
+ if (!pointer)
+ exit_message("null pointer");
+}
+
+const char* num_to_string(const struct number_string *ns, int num_items, int num)
+{
+ for (int i=0; i<num_items; i++) // reverse lookup nonterminal string
+ if (num == ns[i].number)
+ return ns[i].chars;
+ exit_message("num not found");
+ return NULL;
+}
+
+// file
+
+#define INPUT_MAX_LEN 10000
+#define ERROR_BIG "Input file is too big"
+
+
+long fsize(FILE* file) {
+ if (!fseek(file, 0, SEEK_END)) {
+ long size = ftell(file);
+ if (size >= 0 && !fseek(file, 0, SEEK_SET))
+ return size;
+ }
+ return -1;
+}
+
+struct byte_array *read_file(const struct byte_array *filename_ba)
+{
+ FILE * file;
+ size_t read;
+ uint8_t *str;
+ long size;
+
+ const char* filename_str = byte_array_to_string(filename_ba);
+
+ if (!(file = fopen(filename_str, "rb")))
+ exit_message(ERROR_FOPEN);
+ if ((size = fsize(file)) < 0)
+ exit_message(ERROR_FSIZE);
+ else if (size > INPUT_MAX_LEN)
+ exit_message(ERROR_BIG);
+ if (!(str = (uint8_t*)malloc((size_t)size)))// + 1)))
+ exit_message(ERROR_ALLOC);
+
+ read = fread(str, 1, (size_t)size, file);
+ if (feof(file) || ferror(file))
+ exit_message(ERROR_FREAD);
+
+ if (fclose(file))
+ exit_message(ERROR_FCLOSE);
+
+ struct byte_array* ba = byte_array_new_size(read);
+ ba->data = str;
+ byte_array_reset(ba);
+ return ba;
+}
+
+int write_byte_array(struct byte_array* ba, FILE* file) {
+ uint16_t len = ba->length;
+ int n = fwrite(ba->data, 1, len, file);
+ return len - n;
+}
+
+int write_file(const struct byte_array* filename, struct byte_array* bytes)
+{
+ const char *fname = byte_array_to_string(filename);
+ FILE* file = fopen(fname, "w");
+ if (!file) {
+ DEBUGPRINT("could not open file %s\n", fname);
+ return -1;
+ }
+
+ int r = fwrite(bytes->data, 1, bytes->length, file);
+ DEBUGPRINT("\twrote %d bytes\n", r);
+ int s = fclose(file);
+ return (r<0) || s;
+}
+
+char* build_path(const char* dir, const char* name)
+{
+ int dirlen = dir ? strlen(dir) : 0;
+ char* path = (char*)malloc(dirlen + 1 + strlen(name));
+ const char* slash = (dir && dirlen && (dir[dirlen] != '/')) ? "/" : "";
+ sprintf(path, "%s%s%s", dir ? dir : "", slash, name);
+ return path;
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/util.h Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,65 @@
+#ifndef UTIL_H
+#define UTIL_H
+
+#include <stdbool.h>
+#include <setjmp.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+#ifdef __LP64__
+#define VOID_INT int64_t
+#define VOID_FLT long double
+#else
+#define VOID_INT int32_t
+#define VOID_FLT double)(int32_t
+#endif
+
+#define MBED
+#ifdef MBED
+#pragma diag_suppress 1293 // suppress squeamish warning of "assignment in condition"
+#endif
+
+#define ARRAY_LEN(x) (sizeof x / sizeof *x)
+#define ITOA_LEN 19 // enough for 64-bit integer
+
+extern jmp_buf trying;
+const char *make_message(const char *fmt, va_list ap);
+void assert_message(bool assertion, const char *format, ...);
+void *exit_message(const char *format, ...);
+void null_check(const void* p);
+void log_print(const char *format, ...);
+
+#ifdef DEBUG
+#define DEBUGPRINT(...) log_print( __VA_ARGS__ );
+#else
+#define DEBUGPRINT(...) {};
+#endif // #ifdef DEBUG
+
+// file
+
+#define ERROR_FSIZE "Could not get length of file"
+#define ERROR_FOPEN "Could not open file"
+#define ERROR_FREAD "Could not read file"
+#define ERROR_FCLOSE "Could not close file"
+
+struct byte_array *read_file(const struct byte_array *filename);
+int write_file(const struct byte_array* filename, struct byte_array* bytes);
+long fsize(FILE* file);
+
+struct number_string {
+ uint8_t number;
+ char* chars;
+};
+
+const char* num_to_string(const struct number_string *ns, int num_items, int num);
+#define NUM_TO_STRING(ns, num) num_to_string(ns, ARRAY_LEN(ns), num)
+
+// error messages
+
+#define ERROR_ALLOC "Could not allocate memory"
+
+
+
+#endif // UTIL_H
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/variable.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,334 @@
+#include <string.h>
+/*#include <stdio.h>
+#include <signal.h>
+#include <stdarg.h>
+#include <time.h>
+#include "util.h"
+#include "sys.h"
+*/
+#include "vm.h"
+#include "struct.h"
+#include "serial.h"
+#include "variable.h"
+#include "util.h"
+
+#define ERROR_VAR_TYPE "type error"
+#define VAR_MAX 100
+
+const struct number_string var_types[] = {
+ {VAR_NIL, "nil"},
+ {VAR_INT, "integer"},
+ {VAR_BOOL, "boolean"},
+ {VAR_FLT, "float"},
+ {VAR_STR, "string"},
+ {VAR_LST, "list"},
+ {VAR_FNC, "function"},
+ {VAR_MAP, "map"},
+ {VAR_ERR, "error"},
+ {VAR_C, "c-function"},
+};
+
+const char *var_type_str(enum VarType vt)
+{
+ return NUM_TO_STRING(var_types, vt);
+}
+
+struct variable* variable_new(struct Context *context, enum VarType type)
+{
+ null_check(context);
+ if (context->num_vars++ > VAR_MAX)
+ garbage_collect(context);
+ struct variable* v = (struct variable*)malloc(sizeof(struct variable));
+ v->type = type;
+ v->map = NULL;
+ v->marked = false;
+ return v;
+}
+
+struct variable* variable_new_err(struct Context *context, const char* message)
+{
+ null_check(context);
+ struct variable *v = variable_new(context, VAR_ERR);
+ v->str = byte_array_from_string(message);
+ return v;
+}
+
+struct variable* variable_new_nil(struct Context *context)
+{
+ null_check(context);
+ return variable_new(context, VAR_NIL);
+}
+
+struct variable* variable_new_int(struct Context *context, int32_t i)
+{
+ null_check(context);
+ struct variable *v = variable_new(context, VAR_INT);
+ v->integer = i;
+ return v;
+}
+
+struct variable* variable_new_bool(struct Context *context, bool b)
+{
+ null_check(context);
+ struct variable *v = variable_new(context, VAR_BOOL);
+ v->boolean = b;
+ return v;
+}
+
+void variable_del(struct Context *context, struct variable *v)
+{
+ null_check(context);
+ context->num_vars--;
+ switch (v->type) {
+ case VAR_INT:
+ case VAR_FLT:
+ case VAR_MAP:
+ break;
+ case VAR_STR:
+ case VAR_FNC:
+ byte_array_del(v->str);
+ break;
+ case VAR_LST:
+ for (int i=0; i<v->list->length; i++)
+ variable_del(context, (struct variable*)array_get(v->list, i));
+ break;
+ default:
+ vm_exit_message(context, "bad var type");
+ break;
+ }
+ if (v->map) {
+ struct array *keys = map_keys(v->map);
+ struct array *values = map_values(v->map);
+ for (int i=0; i<keys->length; i++) {
+ byte_array_del((struct byte_array*)array_get(keys, i));
+ variable_del(context, (struct variable*)array_get(values, i));
+ }
+ array_del(keys);
+ array_del(values);
+ map_del(v->map);
+ }
+ free(v);
+}
+
+struct variable* variable_new_float(struct Context *context, float f)
+{
+ null_check(context);
+ //DEBUGPRINT("new float %f\n", f);
+ struct variable *v = variable_new(context, VAR_FLT);
+ v->floater = f;
+ return v;
+}
+
+struct variable *variable_new_str(struct Context *context, struct byte_array *str) {
+ struct variable *v = variable_new(context, VAR_STR);
+ v->str = str;
+ return v;
+}
+
+struct variable *variable_new_fnc(struct Context *context, struct byte_array *fnc) {
+ struct variable *v = variable_new(context, VAR_FNC);
+ v->str = fnc;
+ return v;
+}
+
+struct variable *variable_new_list(struct Context *context, struct array *list) {
+ struct variable *v = variable_new(context, VAR_LST);
+ v->list = list ? list : array_new();
+ return v;
+}
+
+struct variable *variable_new_map(struct Context *context, struct map *map) {
+ struct variable *v = variable_new(context, VAR_MAP);
+ v->map = map;
+ return v;
+}
+
+struct variable *variable_new_c(struct Context *context, bridge *cfnc) {
+ struct variable *v = variable_new(context, VAR_C);
+ v->cfnc = cfnc;
+ return v;
+}
+
+const char *variable_value_str(struct Context *context, const struct variable* v)
+{
+ null_check(v);
+ char* str = (char*)malloc(100);
+ struct array* list = v->list;
+
+ enum VarType vt = (enum VarType)v->type;
+ switch (vt) {
+ case VAR_NIL: sprintf(str, "nil"); break;
+ case VAR_INT: sprintf(str, "%d", v->integer); break;
+ case VAR_BOOL: sprintf(str, "%s", v->boolean ? "true" : "false"); break;
+ case VAR_FLT: sprintf(str, "%f", v->floater); break;
+ case VAR_STR: sprintf(str, "%s", byte_array_to_string(v->str)); break;
+ case VAR_FNC: sprintf(str, "f(%dB)", v->str->length); break;
+ case VAR_C: sprintf(str, "c-function"); break;
+ case VAR_MAP: break;
+ case VAR_LST: {
+ strcpy(str, "[");
+ vm_null_check(context, list);
+ for (int i=0; i<list->length; i++) {
+ struct variable* element = (struct variable*)array_get(list, i);
+ vm_null_check(context, element);
+ const char *q = (element->type == VAR_STR || element->type == VAR_FNC) ? "'" : "";
+ const char *c = i ? "," : "";
+ const char *estr = variable_value_str(context, element);
+ sprintf(str, "%s%s%s%s%s", str, c, q, estr, q);
+ }
+ } break;
+ case VAR_ERR:
+ strcpy(str, byte_array_to_string(v->str));
+ break;
+ default:
+ vm_exit_message(context, ERROR_VAR_TYPE);
+ break;
+ }
+
+ if (v->map) {
+ const struct array *a = map_keys(v->map);
+ const struct array *b = map_values(v->map);
+
+ if (vt != VAR_LST)
+ strcat(str, "[");
+ else if (v->list->length && a->length)
+ strcat(str, ",");
+ for (int i=0; i<a->length; i++) {
+ if (i)
+ strcat(str, ",");
+ strcat(str, "'");
+ strcat(str, byte_array_to_string((struct byte_array*)array_get(a,i)));
+ strcat(str, "'");
+ strcat(str, ":");
+ const struct variable *biv = (const struct variable*)array_get(b,i);
+ const char *bistr = variable_value_str(context, biv);
+ strcat(str, bistr);
+ }
+ strcat(str, "]");
+ }
+ else if (vt == VAR_LST)
+ strcat(str, "]");
+
+ return str;
+}
+
+struct byte_array *variable_value(struct Context *c, const struct variable *v) {
+ const char *str = variable_value_str(c, v);
+ return byte_array_from_string(str);
+}
+
+
+
+struct variable *variable_pop(struct Context *context)
+{
+ null_check(context);
+ struct variable *v = (struct variable*)stack_pop(context->operand_stack);
+ //DEBUGPRINT("\nvariable_pop\n");// %s\n", variable_value(v));
+ // print_operand_stack();
+ return v;
+}
+
+void variable_push(struct Context *context, struct variable *v)
+{
+ null_check(context);
+ stack_push(context->operand_stack, v);
+ //DEBUGPRINT("\nvariable_push\n");
+ //print_operand_stack();
+}
+
+struct byte_array *variable_serialize(struct Context *context,
+ struct byte_array *bits,
+ const struct variable *in)
+{
+ null_check(context);
+ //DEBUGPRINT("\tserialize:%s\n", variable_value(in));
+ if (!bits)
+ bits = byte_array_new();
+ serial_encode_int(bits, 0, in->type);
+ switch (in->type) {
+ case VAR_INT: serial_encode_int(bits, 0, in->integer); break;
+ case VAR_FLT: serial_encode_float(bits, 0, in->floater); break;
+ case VAR_STR:
+ case VAR_FNC: serial_encode_string(bits, 0, in->str); break;
+ case VAR_LST: {
+ serial_encode_int(bits, 0, in->list->length);
+ for (int i=0; i<in->list->length; i++)
+ variable_serialize(context, bits, (const struct variable*)array_get(in->list, i));
+ if (in->map) {
+ const struct array *keys = map_keys(in->map);
+ const struct array *values = map_values(in->map);
+ serial_encode_int(bits, 0, keys->length);
+ for (int i=0; i<keys->length; i++) {
+ serial_encode_string(bits, 0, (const struct byte_array*)array_get(keys, i));
+ variable_serialize(context, bits, (const struct variable*)array_get(values, i));
+ }
+ } else
+ serial_encode_int(bits, 0, 0);
+ } break;
+ case VAR_MAP: break;
+ default: vm_exit_message(context, "bad var type"); break;
+ }
+
+ //DEBUGPRINT("in: %s\n", variable_value(in));
+ //byte_array_print("serialized: ", bits);
+ return bits;
+}
+
+struct variable *variable_deserialize(struct Context *context, struct byte_array *bits)
+{
+ null_check(context);
+ enum VarType vt = (enum VarType)serial_decode_int(bits);
+ switch (vt) {
+ case VAR_NIL: return variable_new_nil(context);
+ case VAR_INT: return variable_new_int(context, serial_decode_int(bits));
+ case VAR_FLT: return variable_new_float(context, serial_decode_float(bits));
+ case VAR_FNC: return variable_new_fnc(context, serial_decode_string(bits));
+ case VAR_STR: return variable_new_str(context, serial_decode_string(bits));
+ case VAR_LST: {
+ uint32_t size = serial_decode_int(bits);
+ struct array *list = array_new_size(size);
+ while (size--)
+ array_add(list, variable_deserialize(context, bits));
+ struct variable *out = variable_new_list(context, list);
+
+ uint32_t map_length = serial_decode_int(bits);
+ if (map_length) {
+ out->map = map_new();
+ for (int i=0; i<map_length; i++) {
+ struct byte_array *key = serial_decode_string(bits);
+ struct variable *value = variable_deserialize(context, bits);
+ map_insert(out->map, key, value);
+ }
+ }
+ return out;
+ }
+ default:
+ vm_exit_message(context, "bad var type");
+ return NULL;
+ }
+}
+
+int variable_save(struct Context *context,
+ const struct variable *v,
+ const struct variable *path)
+{
+ vm_null_check(context, v);
+ vm_null_check(context, path);
+
+ struct byte_array *bytes = byte_array_new();
+ variable_serialize(context, bytes, v);
+ return write_file(path->str, bytes);
+}
+
+struct variable *variable_load(struct Context *context, const struct variable *path)
+{
+ null_check(context);
+ vm_null_check(context, path);
+
+ struct byte_array *file_bytes = read_file(path->str);
+ if (!file_bytes)
+ return NULL;
+ struct variable *v = variable_deserialize(context, file_bytes);
+ return v;
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/variable.h Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,63 @@
+#ifndef VARIABLE_H
+#define VARIABLE_H
+
+//#include "vm.h"
+
+enum VarType {
+ VAR_NIL,
+ VAR_INT,
+ VAR_FLT,
+ VAR_BOOL,
+ VAR_STR,
+ VAR_FNC,
+ VAR_LST,
+ VAR_MAP,
+ VAR_ERR,
+ VAR_C,
+};
+
+typedef struct Context *context_p; // forward declaration
+typedef void(bridge)(context_p context);
+
+struct variable {
+ const struct byte_array* name;
+ enum VarType type;
+ uint8_t marked;
+ union {
+ struct byte_array* str;
+ struct array *list;
+ int32_t integer;
+ float floater;
+ bool boolean;
+ void(*cfnc)(context_p); // i.e., bridge
+ };
+ struct map *map;
+};
+
+struct variable* variable_new(struct Context *context, enum VarType type);
+void variable_del(struct Context *context, struct variable *v);
+struct byte_array* variable_value(struct Context *context, const struct variable* v);
+const char* variable_value_str(struct Context *context, const struct variable* v);
+struct byte_array *variable_serialize(struct Context *context, struct byte_array *bits,
+ const struct variable *in);
+struct variable *variable_deserialize(struct Context *context, struct byte_array *str);
+extern int variable_save(struct Context *context, const struct variable* v, const struct variable* path);
+extern struct variable *variable_load(struct Context *context, const struct variable* path);
+
+struct variable* variable_new_bool(struct Context *context, bool b);
+struct variable *variable_new_err(struct Context *context, const char* message);
+struct variable *variable_new_c(struct Context *context, bridge *cfnc);
+struct variable *variable_new_int(struct Context *context, int32_t i);
+struct variable *variable_new_nil(struct Context *context);
+struct variable *variable_new_map(struct Context *context, struct map *map);
+struct variable *variable_new_float(struct Context *context, float f);
+struct variable *variable_new_str(struct Context *context, struct byte_array *str);
+struct variable *variable_new_fnc(struct Context *context, struct byte_array *fnc);
+struct variable *variable_new_list(struct Context *context, struct array *list);
+struct variable* variable_copy(struct Context *context, const struct variable* v);
+struct variable *variable_pop(struct Context *context);
+void variable_push(struct Context *context, struct variable *v);
+
+const char *var_type_str(enum VarType vt);
+
+#endif // VARIABLE_H
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/vm.c Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,1108 @@
+#include <stdio.h>
+#include <signal.h>
+#include <string.h>
+#include <stdarg.h>
+#include <time.h>
+#include "util.h"
+#include "serial.h"
+#include "vm.h"
+#include "variable.h"
+#include "sys.h"
+
+#define VM_NAME "vm"
+
+struct variable *run(struct Context *context, struct byte_array *program, bool in_context);
+struct variable *rhs_pop(struct Context *context);
+static void dst(struct Context *context);
+void src_size(struct Context *context, int32_t size);
+void display_code(struct Context *context, struct byte_array *code);
+
+
+#ifdef DEBUG
+
+#define VM_DEBUGPRINT(...) DEBUGPRINT(__VA_ARGS__ ); if (!context->runtime) return;
+
+void print_operand_stack();
+
+#define INDENT context->indent++;
+#define UNDENT context->indent--;
+
+#else // not DEBUG
+
+#define INDENT
+#define UNDENT
+
+#define VM_DEBUGPRINT(...)
+
+#endif // not DEBUG
+
+
+// assertions //////////////////////////////////////////////////////////////
+
+jmp_buf trying;
+
+static void vm_exit() {
+ longjmp(trying, 1);
+}
+
+void set_error(struct Context *context, const char *format, va_list list)
+{
+ if (!context)
+ return;
+ null_check(format);
+ const char *message = make_message(format, list);
+ context->error = variable_new_err(context, message);
+}
+
+void *vm_exit_message(struct Context *context, const char *format, ...)
+{
+ // make error variable
+ va_list list;
+ va_start(list, format);
+ set_error(context, format, list);
+ va_end(list);
+
+ vm_exit();
+ return NULL;
+}
+
+void vm_assert(struct Context *context, bool assertion, const char *format, ...)
+{
+ if (!assertion) {
+
+ // make error variable
+ va_list list;
+ va_start(list, format);
+ set_error(context, format, list);
+ va_end(list);
+
+ vm_exit();
+ }
+}
+
+void vm_null_check(struct Context *context, const void* p) {
+ vm_assert(context, p, "null pointer");
+}
+
+// state ///////////////////////////////////////////////////////////////////
+
+struct program_state {
+ // struct byte_array *code;
+ struct map *named_variables;
+ struct array *all_variables;
+ uint32_t pc;
+};
+
+struct program_state *program_state_new(struct Context *context)
+{
+ null_check(context);
+ struct program_state *state = (struct program_state*)malloc(sizeof(struct program_state));
+ state->named_variables = map_new();
+ state->all_variables = array_new();
+ stack_push(context->program_stack, state);
+ return state;
+}
+
+struct Context *vm_init()
+{
+ struct Context *context = (struct Context*)malloc(sizeof(struct Context));
+ null_check(context);
+ context->program_stack = stack_new();
+ context->operand_stack = stack_new();
+ context->vm_exception = NULL;
+ context->runtime = true;
+ context->num_vars = 0;
+ context->rhs = stack_new();
+
+ struct variable *vm_var = func_map(context);
+ context->vm_state = program_state_new(context);
+ map_insert(context->vm_state->named_variables, byte_array_from_string(VM_NAME), vm_var);
+
+ return context;
+}
+
+// garbage collection //////////////////////////////////////////////////////
+
+void mark(struct Context *context, struct variable *root)
+{
+ null_check(context);
+ if (root->map) {
+ const struct array *values = map_values(root->map);
+ for (int i=0; values && i<values->length; i++)
+ mark(context, (struct variable*)array_get(values, i));
+ }
+
+ root->marked = true;
+ switch (root->type) {
+ case VAR_INT:
+ case VAR_FLT:
+ case VAR_STR:
+ case VAR_FNC:
+ case VAR_MAP:
+ break;
+ case VAR_LST:
+ for (int i=0; i<root->list->length; i++)
+ mark(context, (struct variable*)array_get(root->list, i));
+ break;
+ default:
+ vm_exit_message(context, "bad var type");
+ break;
+ }
+}
+
+void sweep(struct Context *context, struct variable *root)
+{
+ null_check(context);
+ struct program_state *state = (struct program_state*)stack_peek(context->program_stack, 0);
+ struct array *vars = state->all_variables;
+ for (int i=0; i<vars->length; i++) {
+ struct variable *v = (struct variable*)array_get(vars, i);
+ if (!v->marked)
+ variable_del(context, v);
+ else
+ v->marked = false;
+ }
+}
+
+void garbage_collect(struct Context *context)
+{
+ null_check(context);
+ struct program_state *state = (struct program_state*)stack_peek(context->program_stack, 0);
+ struct array *vars = state->all_variables;
+ for (int i=0; i<vars->length; i++) {
+ struct variable *v = (struct variable*)array_get(vars, i);
+ mark(context, v);
+ sweep(context, v);
+ }
+}
+
+// display /////////////////////////////////////////////////////////////////
+
+#ifdef DEBUG
+
+const struct number_string opcodes[] = {
+ {VM_NIL, "NIL"},
+ {VM_INT, "INT"},
+ {VM_BOOL, "BUL"},
+ {VM_FLT, "FLT"},
+ {VM_STR, "STR"},
+ {VM_VAR, "VAR"},
+ {VM_FNC, "FNC"},
+ {VM_SRC, "SRC"},
+ {VM_LST, "LST"},
+ {VM_DST, "DST"},
+ {VM_MAP, "MAP"},
+ {VM_GET, "GET"},
+ {VM_PUT, "PUT"},
+ {VM_ADD, "ADD"},
+ {VM_SUB, "SUB"},
+ {VM_MUL, "MUL"},
+ {VM_DIV, "DIV"},
+ {VM_MOD, "MOD"},
+ {VM_AND, "AND"},
+ {VM_OR, "ORR"},
+ {VM_NOT, "NOT"},
+ {VM_NEG, "NEG"},
+ {VM_EQU, "EQU"},
+ {VM_NEQ, "NEQ"},
+ {VM_GTN, "GTN"},
+ {VM_LTN, "LTN"},
+ {VM_IFF, "IFF"},
+ {VM_JMP, "JMP"},
+ {VM_CAL, "CAL"},
+ {VM_MET, "MET"},
+ {VM_RET, "RET"},
+ {VM_ITR, "ITR"},
+ {VM_COM, "COM"},
+ {VM_TRY, "TRY"},
+};
+
+void print_operand_stack(struct Context *context)
+{
+ null_check(context);
+ struct variable *operand;
+ for (int i=0; (operand = stack_peek(context->operand_stack, i)); i++)
+ DEBUGPRINT("\t%s\n", variable_value_str(context, operand));
+}
+
+const char* indentation(struct Context *context)
+{
+ null_check(context);
+ static char str[100];
+ int tab = 0;
+ while (tab < context->indent)
+ str[tab++] = '\t';
+ str[tab] = 0;
+ return (const char*)str;
+}
+
+static void display_program_counter(struct Context *context, const struct byte_array *program)
+{
+ null_check(context);
+ DEBUGPRINT("%s%2ld:%3d ", indentation(context), program->current-program->data, *program->current);
+}
+
+void display_code(struct Context *context, struct byte_array *code)
+{
+ null_check(context);
+ bool was_running = context->runtime;
+ context->runtime = false;
+
+ INDENT
+ run(context, code, false);
+ UNDENT
+
+ context->runtime = was_running;
+}
+
+void display_program(struct byte_array *program)
+{
+ struct Context *context = vm_init();
+
+ INDENT
+ DEBUGPRINT("%sprogram bytes:\n", indentation(context));
+
+ INDENT
+ for (int i=0; i<program->length; i++)
+ DEBUGPRINT("%s%2d:%3d\n", indentation(context), i, program->data[i]);
+ UNDENT
+
+ DEBUGPRINT("%sprogram instructions:\n", indentation(context));
+ byte_array_reset(program);
+ struct byte_array* code = serial_decode_string(program);
+
+ display_code(context, code);
+
+ UNDENT
+ UNDENT
+}
+
+#else // not DEBUG
+
+void display_code(struct Context *context, struct byte_array *code) {}
+const char* indentation(struct Context *context) { return ""; }
+
+#endif // DEBUG
+
+// instruction implementations /////////////////////////////////////////////
+
+void src_size(struct Context *context, int32_t size)
+{
+ null_check(context);
+ if (size > 1)
+ while (stack_peek(context->rhs,1))
+ stack_pop(context->rhs);
+ else if (!stack_empty(context->rhs))
+ return;
+
+ while (size--)
+ stack_push(context->rhs, variable_pop(context));
+}
+
+static void src(struct Context *context, enum Opcode op, struct byte_array *program)
+{
+ null_check(context);
+ int32_t size = serial_decode_int(program);
+ VM_DEBUGPRINT("%s %d\n", NUM_TO_STRING(opcodes, op), size);
+ src_size(context, size);
+}
+
+void vm_call(struct Context *context)
+{
+ null_check(context);
+ // get the function pointer from the stack
+ struct variable *func = variable_pop(context);
+ INDENT
+
+ // call the function
+ switch (func->type) {
+ case VAR_FNC:
+ run(context, func->str, false);
+ break;
+ case VAR_C:
+ func->cfnc(context);
+ break;
+ default:
+ vm_exit_message(context, "not a function");
+ break;
+ }
+ UNDENT
+}
+
+static inline void func_call(struct Context *context)
+{
+ null_check(context);
+ VM_DEBUGPRINT("VM_CAL\n");
+ vm_call(context);
+}
+
+static void push_list(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ int32_t num_items = serial_decode_int(program);
+ DEBUGPRINT("LST %d", num_items);
+ if (!context->runtime)
+ VM_DEBUGPRINT("\n");
+ struct array *items = array_new();
+ struct map *map = map_new();
+
+ while (num_items--) {
+ struct variable* v = variable_pop(context);
+ if (v->type == VAR_MAP)
+ map_update(map, v->map); // mapped values are stored in the map, not list
+ else
+ array_insert(items, 0, v);
+ }
+ struct variable *list = variable_new_list(context, items);
+ list->map = map;
+ DEBUGPRINT(": %s\n", variable_value_str(context, list));
+ variable_push(context, list);
+}
+
+static void push_map(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ int32_t num_items = serial_decode_int(program);
+ DEBUGPRINT("MAP %d", num_items);
+ if (!context->runtime)
+ VM_DEBUGPRINT("\n");
+ struct map *map = map_new();
+ while (num_items--) {
+ struct variable* value = variable_pop(context);
+ struct variable* key = variable_pop(context);
+ assert_message(key->type==VAR_STR, "non-string map index");
+ map_insert(map, key->str, value);
+ }
+ struct variable *v = variable_new_map(context, map);
+ DEBUGPRINT(": %s\n", variable_value_str(context, v));
+ variable_push(context, v);
+}
+
+struct variable* variable_set(struct Context *context, struct variable *u, const struct variable* v)
+{
+ null_check(context);
+ vm_null_check(context, u);
+ vm_null_check(context, v);
+ switch (v->type) {
+ case VAR_NIL: break;
+ case VAR_INT: u->integer = v->integer; break;
+ case VAR_FLT: u->floater = v->floater; break;
+ case VAR_FNC:
+ case VAR_STR: u->str = byte_array_copy(v->str); break;
+ case VAR_LST:
+ u->list = v->list;
+ u->list->current = u->list->data; break;
+ default:
+ vm_exit_message(context, "bad var type");
+ break;
+ }
+ if (v->type == VAR_STR)
+ u->str = byte_array_copy(v->str);
+ u->map = v->map;
+ return u;
+}
+
+struct variable* variable_copy(struct Context *context, const struct variable* v)
+{
+ null_check(context);
+ vm_null_check(context, v);
+ struct variable *u = variable_new(context, (enum VarType)v->type);
+ variable_set(context, u, v);
+ return u;
+}
+
+
+// run /////////////////////////////////////////////////////////////////////
+
+static struct variable *list_get_int(struct Context *context,
+ const struct variable *indexable,
+ const struct variable *index)
+{
+ null_check(context);
+ null_check(indexable);
+ null_check(index);
+
+ uint32_t n = index->integer;
+ enum VarType it = (enum VarType)indexable->type;
+ switch (it) {
+ case VAR_LST:
+ return (struct variable*)array_get(indexable->list, n);
+ case VAR_STR: {
+ vm_assert(context, n<indexable->str->length, "index out of bounds");
+ char *str = (char*)malloc(2);
+ sprintf(str, "%c", indexable->str->data[n]);
+ return variable_new_str(context, byte_array_from_string(str));
+ }
+ default:
+ vm_exit_message(context, "indexing non-indexable");
+ return NULL;
+ }
+}
+
+void lookup(struct Context *context, struct variable *indexable, struct variable *index)
+{
+ null_check(context);
+ if (!context->runtime)
+ VM_DEBUGPRINT("GET\n");
+
+ struct variable *item=0;
+
+ switch (index->type) {
+ case VAR_INT:
+ item = list_get_int(context, indexable, index);
+ break;
+ case VAR_STR:
+ if (indexable->map)
+ item = (struct variable*)map_get(indexable->map, index->str);
+ if (!item)
+ item = builtin_method(context, indexable, index);
+ assert_message(item, "did not find member");
+ break;
+ default:
+ vm_exit_message(context, "bad index type");
+ break;
+ }
+ DEBUGPRINT("%s\n", variable_value_str(context, item));
+ variable_push(context, item);
+}
+
+static void list_get(struct Context *context)
+{
+ null_check(context);
+ DEBUGPRINT("GET ");
+ if (!context->runtime)
+ VM_DEBUGPRINT("\n");
+ struct variable *indexable, *index;
+ indexable = variable_pop(context);
+ index = variable_pop(context);
+ lookup(context, indexable, index);
+}
+
+static void method(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ DEBUGPRINT("MET ");
+ if (!context->runtime)
+ VM_DEBUGPRINT("\n");
+ struct variable *indexable, *index;
+ indexable = variable_pop(context);
+ index = variable_pop(context);
+ lookup(context, indexable, index);
+ stack_push(context->rhs, indexable);
+ vm_call(context);
+}
+
+
+static int32_t jump(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ null_check(program);
+ uint8_t *start = program->current;
+ int32_t offset = serial_decode_int(program);
+ DEBUGPRINT("JMP %d\n", offset);
+ if (!context->runtime)
+ return 0;
+
+ return offset - (program->current - start);
+}
+
+bool test_operand(struct Context *context)
+{
+ null_check(context);
+ struct variable* v = variable_pop(context);
+ bool indeed = false;
+ switch (v->type) {
+ case VAR_NIL: indeed = false; break;
+ case VAR_BOOL: indeed = v->boolean; break;
+ case VAR_INT: indeed = v->integer; break;
+ default:
+ vm_exit_message(context, "bad iff operand");
+ break;
+ }
+ return indeed;
+}
+
+static int32_t iff(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ null_check(program);
+ int32_t offset = serial_decode_int(program);
+ DEBUGPRINT("IF %d\n", offset);
+ if (!context->runtime)
+ return 0;
+ return test_operand(context) ? 0 : (VOID_INT)offset;
+}
+
+static void push_nil(struct Context *context)
+{
+ null_check(context);
+ struct variable* var = variable_new_nil(context);
+ VM_DEBUGPRINT("NIL\n");
+ variable_push(context, var);
+}
+
+static void push_int(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ null_check(program);
+ int32_t num = serial_decode_int(program);
+ VM_DEBUGPRINT("INT %d\n", num);
+ struct variable* var = variable_new_int(context, num);
+ variable_push(context, var);
+}
+
+static void push_bool(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ null_check(program);
+ int32_t num = serial_decode_int(program);
+ VM_DEBUGPRINT("BOOL %d\n", num);
+ struct variable* var = variable_new_bool(context, num);
+ variable_push(context, var);
+}
+
+static void push_float(struct Context *context, struct byte_array *program)
+{
+ null_check(context);
+ null_check(program);
+ float num = serial_decode_float(program);
+ VM_DEBUGPRINT("FLT %f\n", num);
+ struct variable* var = variable_new_float(context, num);
+ variable_push(context, var);
+}
+
+struct variable *find_var(struct Context *context, const struct byte_array *name)
+{
+ null_check(context);
+ null_check(name);
+ const struct program_state *state = (const struct program_state*)stack_peek(context->program_stack, 0);
+ struct map *var_map = state->named_variables;
+ struct variable *v = (struct variable*)map_get(var_map, name);
+ //DEBUGPRINT("find_var(%s) in %p,%p = %p\n", byte_array_to_string(name), state, var_map, v);
+ if (!v)
+ v = (struct variable*)map_get(context->vm_state->named_variables, name);
+ return v;
+}
+
+static void push_var(struct Context *context, struct byte_array *program)
+{
+ struct byte_array* name = serial_decode_string(program);
+ VM_DEBUGPRINT("VAR %s\n", byte_array_to_string(name));
+ struct variable *v = find_var(context, name);
+ vm_assert(context, v, "variable %s not found", byte_array_to_string(name));
+ variable_push(context, v);
+}
+
+static void push_str(struct Context *context, struct byte_array *program)
+{
+ struct byte_array* str = serial_decode_string(program);
+ VM_DEBUGPRINT("STR '%s'\n", byte_array_to_string(str));
+ struct variable* v = variable_new_str(context, str);
+ variable_push(context, v);
+}
+
+static void push_fnc(struct Context *context, struct byte_array *program)
+{
+ uint32_t fcodelen = serial_decode_int(program);
+ struct byte_array* fbody = byte_array_new_size(fcodelen);
+ memcpy(fbody->data, program->current, fcodelen);
+
+ DEBUGPRINT("FNC %u\n", fcodelen);
+ display_code(context, fbody);
+
+ if (context->runtime) {
+ struct variable* var = variable_new_fnc(context, (struct byte_array*)fbody);
+ variable_push(context, var);
+ }
+
+ program->current += fcodelen;
+}
+
+void set_named_variable(struct Context *context,
+ struct program_state *state,
+ const struct byte_array *name,
+ const struct variable *value)
+{
+ if (!state)
+ state = (struct program_state*)stack_peek(context->program_stack, 0);
+ struct map *var_map = state->named_variables;
+ struct variable *to_var = find_var(context, name);
+
+ if (!to_var) { // new variable
+ to_var = variable_copy(context, value);
+ to_var->name = byte_array_copy(name);
+ } else
+ variable_set(context, to_var, value);
+
+ map_insert(var_map, name, to_var);
+
+ //DEBUGPRINT(" (SET %s to %s in {%p,%p,%p})\n", byte_array_to_string(name), variable_value(to_var), state, var_map, to_var);
+}
+
+struct variable *rhs_pop(struct Context *context)
+{
+ struct variable *value = (struct variable*)stack_pop(context->rhs);
+ if (!value)
+ value = variable_new_nil(context);
+ return value;
+}
+
+static void set(struct Context *context, struct program_state *state, struct byte_array *program)
+{
+ null_check(context);
+ struct byte_array *name = serial_decode_string(program); // destination variable name
+ if (!context->runtime)
+ VM_DEBUGPRINT("SET %s\n", byte_array_to_string(name));
+
+ struct variable *value = rhs_pop(context);
+ DEBUGPRINT("SET %s to %s\n", byte_array_to_string(name), variable_value_str(context, value));
+ set_named_variable(context, state, name, value); // set the variable to the value
+}
+
+static void dst(struct Context *context)
+{
+ VM_DEBUGPRINT("DST\n");
+ while (!stack_empty(context->rhs))
+ stack_pop(context->rhs);
+}
+
+static void list_put(struct Context *context)
+{
+ DEBUGPRINT("PUT");
+ if (!context->runtime)
+ VM_DEBUGPRINT("\n");
+ struct variable* recipient = variable_pop(context);
+ struct variable* key = variable_pop(context);
+ struct variable *value = rhs_pop(context);
+
+ switch (key->type) {
+ case VAR_INT:
+ switch (recipient->type) {
+ case VAR_LST:
+ array_set(recipient->list, key->integer, value);
+ break;
+ case VAR_STR:
+ ((uint8_t*)recipient->str)[key->integer] = (uint8_t)value->integer;
+ break;
+ default:
+ vm_exit_message(context, "indexing non-indexable");
+ } break;
+ case VAR_STR:
+ if (!recipient->map)
+ recipient->map = map_new();
+ map_insert(recipient->map, key->str, value);
+ break;
+ default:
+ vm_exit_message(context, "bad index type");
+ break;
+ }
+ DEBUGPRINT(": %s\n", variable_value_str(context, recipient));
+}
+
+static struct variable *binary_op_int(struct Context *context,
+ enum Opcode op,
+ const struct variable *u,
+ const struct variable *v)
+{
+ int32_t m = u->integer;
+ int32_t n = v->integer;
+ int32_t i;
+ switch (op) {
+ case VM_MUL: i = m * n; break;
+ case VM_DIV: i = m / n; break;
+ case VM_ADD: i = m + n; break;
+ case VM_SUB: i = m - n; break;
+ case VM_AND: i = m && n; break;
+ case VM_EQU: i = m == n; break;
+ case VM_OR: i = m || n; break;
+ case VM_GTN: i = m > n; break;
+ case VM_LTN: i = m < n; break;
+ case VM_BND: i = m & n; break;
+ case VM_BOR: i = m | n; break;
+ case VM_MOD: i = m % n; break;
+ case VM_XOR: i = m ^ n; break;
+ case VM_RSF: i = m >> n; break;
+ case VM_LSF: i = m << n; break;
+
+ default:
+ return (struct variable*)vm_exit_message(context, "bad math int operator");
+ }
+ return variable_new_int(context, i);
+}
+
+static struct variable *binary_op_float(struct Context *context,
+ enum Opcode op,
+ const struct variable *u,
+ const struct variable *v)
+{
+ float m = u->floater;
+ float n = v->floater;
+ float f = 0;
+ switch (op) {
+ case VM_MUL: f = m * n; break;
+ case VM_DIV: f = m / n; break;
+ case VM_ADD: f = m + n; break;
+ case VM_SUB: f = m - n; break;
+ case VM_NEQ: f = m != n; break;
+ case VM_GTN: return variable_new_int(context, n > m);
+ case VM_LTN: return variable_new_int(context, n < m);
+ default:
+ return (struct variable*)vm_exit_message(context, "bad math float operator");
+ }
+ return variable_new_float(context, f);
+}
+
+static bool is_num(enum VarType vt) {
+ return vt == VAR_INT || vt == VAR_FLT;
+}
+
+static struct variable *binary_op_str(struct Context *context,
+ enum Opcode op,
+ const struct variable *u,
+ const struct variable *v)
+{
+ null_check(context);
+ struct variable *w = NULL;
+ struct byte_array *ustr = variable_value(context, u);
+ struct byte_array *vstr = variable_value(context, v);
+
+ switch (op) {
+ case VM_ADD: w = variable_new_str(context, byte_array_concatenate(2, vstr, ustr)); break;
+ case VM_EQU: w = variable_new_int(context, byte_array_equals(ustr, vstr)); break;
+ default:
+ return (struct variable*)vm_exit_message(context, "unknown string operation");
+ }
+ return w;
+}
+
+static bool variable_compare(struct Context *context,
+ const struct variable *u,
+ const struct variable *v)
+{
+ null_check(context);
+ if (!u != !v)
+ return false;
+ enum VarType ut = (enum VarType)u->type;
+ enum VarType vt = (enum VarType)v->type;
+
+ if (ut != vt)
+ return false;
+
+ switch (ut) {
+ case VAR_LST:
+ if (u->list->length != v->list->length)
+ return false;
+ for (int i=0; i<u->list->length; i++) {
+ struct variable *ui = (struct variable*)array_get(u->list, i);
+ struct variable *vi = (struct variable*)array_get(v->list, i);
+ if (!variable_compare(context, ui, vi))
+ return false;
+ }
+ // for list, check the map too
+ case VAR_MAP: {
+ struct array *keys = map_keys(u->map);
+ for (int i=0; i<keys->length; i++) {
+ struct byte_array *key = (struct byte_array*)array_get(keys, i);
+ struct variable *uvalue = (struct variable*)map_get(u->map, key);
+ struct variable *vvalue = (struct variable*)map_get(v->map, key);
+ if (!variable_compare(context, uvalue, vvalue))
+ return false;
+ }
+ return true; }
+ case VAR_INT:
+ return u->integer == v->integer;
+ case VAR_FLT:
+ return u->floater == v->floater;
+ case VAR_STR:
+ return byte_array_equals(u->str, v->str);
+ default:
+ return (bool)vm_exit_message(context, "bad comparison");
+ }
+}
+
+static struct variable *binary_op_lst(struct Context *context,
+ enum Opcode op,
+ const struct variable *u,
+ const struct variable *v)
+{
+ null_check(context);
+ vm_assert(context, u->type==VAR_LST && v->type==VAR_LST, "list op with non-lists");
+ struct variable *w = NULL;
+
+ switch (op) {
+ case VM_ADD:
+ w = variable_copy(context, v);
+ for (int i=0; i<u->list->length; i++)
+ array_add(w->list, array_get(u->list, i));
+ map_update(w->map, u->map);
+ break;
+ default:
+ return (struct variable*)vm_exit_message(context, "unknown string operation");
+ }
+
+ return w;
+}
+
+static void binary_op(struct Context *context, enum Opcode op)
+{
+ null_check(context);
+ if (!context->runtime)
+ VM_DEBUGPRINT("%s\n", NUM_TO_STRING(opcodes, op));
+
+ const struct variable *u = variable_pop(context);
+ const struct variable *v = variable_pop(context);
+ struct variable *w;
+
+ if (op == VM_EQU) {
+ bool same = variable_compare(context, u, v);
+ w = variable_new_int(context, same);
+ } else {
+
+ enum VarType ut = (enum VarType)u->type;
+ enum VarType vt = (enum VarType)v->type;
+ bool floater = (ut == VAR_FLT && is_num(vt)) || (vt == VAR_FLT && is_num(ut));
+
+ if (vt == VAR_STR || ut == VAR_STR) w = binary_op_str(context, op, u, v);
+ else if (floater) w = binary_op_float(context, op, u, v);
+ else if (ut == VAR_INT && vt == VAR_INT) w = binary_op_int(context, op, v, u);
+ else if (vt == VAR_LST) w = binary_op_lst(context, op, u, v);
+ else
+ vm_exit_message(context, "unknown binary op");
+ }
+
+ variable_push(context, w);
+
+ DEBUGPRINT("%s(%s,%s) = %s\n",
+ NUM_TO_STRING(opcodes, op),
+ variable_value_str(context, v),
+ variable_value_str(context, u),
+ variable_value_str(context, w));
+}
+
+static void unary_op(struct Context *context, enum Opcode op)
+{
+ null_check(context);
+ if (!context->runtime)
+ VM_DEBUGPRINT("%s\n", NUM_TO_STRING(opcodes, op));
+
+ struct variable *v = (struct variable*)variable_pop(context);
+ struct variable *result = NULL;
+
+ switch (v->type) {
+ case VAR_NIL:
+ {
+ switch (op) {
+ case VM_NEG: result = variable_new_nil(context); break;
+ case VM_NOT: result = variable_new_bool(context, true); break;
+ default: vm_exit_message(context, "bad math operator"); break;
+ }
+ } break;
+ case VAR_INT: {
+ int32_t n = v->integer;
+ switch (op) {
+ case VM_NEG: result = variable_new_int(context, -n); break;
+ case VM_NOT: result = variable_new_bool(context, !n); break;
+ case VM_INV: result = variable_new_int(context, ~n); break;
+ default: vm_exit_message(context, "bad math operator"); break;
+ }
+ } break;
+ default:
+ vm_exit_message(context, "bad math type");
+ break;
+ }
+
+ variable_push(context, result);
+
+ DEBUGPRINT("%s(%s) = %s\n",
+ NUM_TO_STRING(opcodes, op),
+ variable_value_str(context, v),
+ variable_value_str(context, result));
+}
+
+// FOR who IN what WHERE where DO how
+static void iterate(struct Context *context,
+ enum Opcode op,
+ struct program_state *state,
+ struct byte_array *program)
+{
+ null_check(context);
+ struct byte_array *who = serial_decode_string(program);
+ struct byte_array *where = serial_decode_string(program);
+ struct byte_array *how = serial_decode_string(program);
+
+#ifdef DEBUG
+ DEBUGPRINT("%s %s\n",
+ NUM_TO_STRING(opcodes, op),
+ byte_array_to_string(who));
+ if (!context->runtime) {
+ if (where) {
+ DEBUGPRINT("%s\tWHERE\n", indentation(context));
+ display_code(context, where);
+ }
+ DEBUGPRINT("%s\tDO\n", indentation(context));
+ display_code(context, how);
+ return;
+ }
+#endif
+
+ bool comprehending = (op == VM_COM);
+ struct variable *result = comprehending ? variable_new_list(context, NULL) : NULL;
+
+ struct variable *what = variable_pop(context);
+ for (int i=0; i<what->list->length; i++) {
+
+ struct variable *that = (struct variable*)array_get(what->list, i);
+ set_named_variable(context, state, who, that);
+
+ byte_array_reset(where);
+ byte_array_reset(how);
+ run(context, where, true);
+ if (test_operand(context)) {
+
+ run(context, how, true);
+
+ if (comprehending) {
+ struct variable *item = (struct variable*)stack_pop(context->operand_stack);
+ array_add(result->list, item);
+ }
+ }
+ }
+
+ if (comprehending)
+ stack_push(context->operand_stack, result);
+}
+
+static inline void vm_trycatch(struct Context *context, struct byte_array *program)
+{
+ struct byte_array *trial = serial_decode_string(program);
+ DEBUGPRINT("TRY %d\n", trial->length);
+ display_code(context, trial);
+ struct byte_array *name = serial_decode_string(program);
+ struct byte_array *catcher = serial_decode_string(program);
+ DEBUGPRINT("%sCATCH %s %d\n", indentation(context), byte_array_to_string(name), catcher->length);
+ display_code(context, catcher);
+ if (!context->runtime)
+ return;
+
+ run(context, trial, true);
+ if (context->vm_exception) {
+ set_named_variable(context, NULL, name, context->vm_exception);
+ context->vm_exception = NULL;
+ run(context, catcher, true);
+ }
+}
+
+struct variable *run(struct Context *context, struct byte_array *program, bool in_context)
+{
+ null_check(context);
+ struct program_state *state = NULL;
+ program->current = program->data;
+ if (context->runtime) {
+ if (in_context)
+ state = (struct program_state*)stack_peek(context->program_stack, 0);
+ else
+ state = program_state_new(context);
+ }
+ //DEBUGPRINT("run %d %d %p\n", runtime, context, state);
+ //DEBUGPRINT("\t%p < %p + %d? %s\n", program->current, program->data, program->length, program->current < program->data + program->length ? "yes":"no");
+
+ while (program->current < program->data + program->length) {
+ enum Opcode inst = (enum Opcode)*program->current;
+#ifdef DEBUG
+ display_program_counter(context, program);
+#endif
+ program->current++; // increment past the instruction
+
+ if (inst == VM_RET) {
+ src(context, inst, program);
+ break;
+ } else if (inst == VM_TRO) {
+ DEBUGPRINT("THROW\n");
+ if (context->runtime) {
+ context->vm_exception = (struct variable*)stack_pop(context->operand_stack);
+ break;
+ } else
+ continue;
+ }
+
+ int32_t pc_offset = 0;
+
+ switch (inst) {
+ case VM_MUL:
+ case VM_DIV:
+ case VM_ADD:
+ case VM_SUB:
+ case VM_AND:
+ case VM_EQU:
+ case VM_NEQ:
+ case VM_GTN:
+ case VM_LTN:
+ case VM_BND:
+ case VM_BOR:
+ case VM_MOD:
+ case VM_XOR:
+ case VM_INV:
+ case VM_RSF:
+ case VM_LSF:
+ case VM_OR: binary_op(context, inst); break;
+ case VM_NEG:
+ case VM_NOT: unary_op(context, inst); break;
+ case VM_SRC: src(context, inst, program); break;
+ case VM_DST: dst(context); break;
+ case VM_SET: set(context, state, program); break;
+ case VM_JMP: pc_offset = jump(context, program); break;
+ case VM_IFF: pc_offset = iff(context, program); break;
+ case VM_CAL: func_call(context); break;
+ case VM_LST: push_list(context, program); break;
+ case VM_MAP: push_map(context, program); break;
+ case VM_GET: list_get(context); break;
+ case VM_PUT: list_put(context); break;
+ case VM_NIL: push_nil(context); break;
+ case VM_INT: push_int(context, program); break;
+ case VM_FLT: push_float(context, program); break;
+ case VM_BOOL: push_bool(context, program); break;
+ case VM_STR: push_str(context, program); break;
+ case VM_VAR: push_var(context, program); break;
+ case VM_FNC: push_fnc(context, program); break;
+ case VM_MET: method(context, program); break;
+ case VM_COM:
+ case VM_ITR: iterate(context, inst, state, program); break;
+ case VM_TRY: vm_trycatch(context, program); break;
+ default:
+ return (struct variable*)vm_exit_message(context, ERROR_OPCODE);
+ }
+ program->current += pc_offset;
+ }
+
+ //DEBUGPRINT("run done %d %d %p\n", runtime, context, state);
+ if (!context->runtime)
+ return NULL;
+ if (!in_context)
+ stack_pop(context->program_stack);
+ return (struct variable*)stack_peek(context->operand_stack, 0);
+}
+
+struct variable *execute(struct byte_array *program,
+ bool in_context,
+ bridge *callback_to_c)
+{
+ null_check(program);
+ DEBUGPRINT("execute:\n");
+ struct Context *context = vm_init();
+ context->callback2c = callback_to_c;
+ vm_assert(context, program!=0 && program->data!=0, ERROR_NULL);
+ byte_array_reset(program);
+ struct byte_array* code = serial_decode_string(program);
+
+#ifdef DEBUG
+ context->indent = 1;
+#endif
+
+ struct variable *v;
+ if (!setjmp(trying))
+ v = run(context, code, in_context);
+ else
+ v = context->error;
+
+ return v;
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/vm.h Wed May 30 21:13:01 2012 +0000
@@ -0,0 +1,88 @@
+#ifndef VM_H
+#define VM_H
+
+
+#include <stdint.h>
+#include <inttypes.h>
+#include "struct.h"
+#include "util.h"
+#include "variable.h"
+
+#define ERROR_NULL "null pointer"
+#define ERROR_INDEX "index out of bounds"
+
+struct Context {
+ struct program_state *vm_state;
+ struct stack *program_stack;
+ struct stack *operand_stack;
+ struct stack *rhs;
+ struct variable *vm_exception;
+ bridge *callback2c;
+ bool runtime;
+ uint32_t num_vars;
+ struct variable* error;
+ uint8_t indent;
+};
+
+enum Opcode {
+ VM_NIL, // push nil
+ VM_INT, // push an integer
+ VM_FLT, // push a float
+ VM_BOOL,// push a boolean
+ VM_STR, // push a string
+ VM_VAR, // push a variable
+ VM_FNC, // push a function
+ VM_DST, // done with assignment
+ VM_SET, // set a variable
+ VM_SRC, // push a set of values
+ VM_LST, // push a list
+ VM_MAP, // push a map
+ VM_GET, // get an item from a list or map
+ VM_PUT, // put an item in a list or map
+ VM_ADD, // add two values
+ VM_SUB, // subtract two values
+ VM_MUL, // multiply two values
+ VM_DIV, // divide two values
+ VM_MOD, // modulo
+ VM_BND, // bitwise and
+ VM_BOR, // bitwise or
+ VM_INV, // bitwise inverse
+ VM_XOR, // xor
+ VM_LSF, // left shift
+ VM_RSF, // right shift
+ VM_NEG, // arithmetic negate a value
+ VM_NOT, // boolean negate a value
+ VM_EQU, // compare
+ VM_NEQ, // diff
+ VM_GTN, // greater than
+ VM_LTN, // less than
+ VM_AND, // logical and
+ VM_OR, // logical or
+ VM_IFF, // if then
+ VM_JMP, // jump the program counter
+ VM_CAL, // call a function
+ VM_MET, // call an object method
+ VM_RET, // return from a function,
+ VM_ITR, // iteration loop
+ VM_COM, // comprehension
+ VM_TRY, // try.catch
+ VM_TRO, // throw
+};
+
+#define ERROR_OPCODE "unknown opcode"
+
+#ifdef DEBUG
+void display_program(struct byte_array* program);
+#endif
+struct Context *vm_init();
+struct variable *execute(struct byte_array *program,
+ bool in_context,
+ bridge *callback_to_c);
+void garbage_collect(struct Context *context);
+
+void vm_call(struct Context *context);
+void *vm_exit_message(struct Context *context, const char *format, ...);
+void vm_null_check(struct Context *context, const void* p);
+void vm_assert(struct Context *context, bool assertion, const char *format, ...);
+
+#endif // VM_H