~lbnz/xr0

b50e55350616df4b81343cb6db7b489e30a713fe — Claude Betz 28 days ago 6fa96f5 master v0.16.0
feat: verify and help commands, cosmetics

issue: https://github.com/xr0-org/xr0/issues/45
M Makefile => Makefile +3 -3
@@ 2,7 2,6 @@
CC = gcc -g -Wreturn-type -std=gnu11
CFLAGS = -I include -Wall
VALGRIND = valgrind --fullpath-after=`pwd`/src/

LEX = lex
YACC = bison -yvd



@@ 184,9 183,10 @@ $(AST_OBJ): $(AST_DIR)/ast.c \
	$(AST_DIR)/type/type.h \
	$(AST_DIR)/literals.h \
	$(AST_DIR)/function/function.h \
	$(MATH_OBJ)
	$(MATH_OBJ) \
	$(GRAM_OBJ)
	@printf 'CC\t$@\n'
	@$(CC) $(CFLAGS) -I $(AST_DIR) -o $@ -c $(AST_DIR)/ast.c
	@$(CC) $(CFLAGS) -I $(BUILD_DIR) -I $(AST_DIR) -o $@ -c $(AST_DIR)/ast.c

$(MATH_OBJ): $(MATH_DIR)/math.c $(BUILD_DIR)
	@printf 'CC\t$@\n'

M README.md => README.md +1 -2
@@ 26,13 26,12 @@ small.
Reach out via email to
[Claude](mailto:betz@xr0.dev) or
[Amisi](mailto:a@xr0.dev) or DM us on the
[Xr0 Zulip](https://xr0.zulipchat.com/login) if you're interested in this.
[Xr0 Discord](https://discord.com/invite/yfx69tbhxQ) if you're interested in this.

We are currently not accepting pull requests due to the early stage of Xr0.
However, if you have a serious proposal for how we can improve Xr0 you can
[make an issue](https://github.com/xr0-org/xr0/issues/new) to explain it.


## License

This project is distributed under the terms of the Apache 2.0 open source license.

M include/lex.h => include/lex.h +1 -0
@@ 32,6 32,7 @@ lexememarker_destroy(struct lexememarker *);
char *
lexememarker_str(struct lexememarker *);

extern struct ast_expr *YACC_PARSED_EXPR;
extern struct ast *root;
extern struct map *table;


M include/path.h => include/path.h +3 -0
@@ 29,6 29,9 @@ struct error *
path_next(struct path *);

struct error *
path_verify(struct path *, struct ast_expr *);

struct error *
path_setbreakpoint(struct path *);

struct lexememarker *

M include/state.h => include/state.h +3 -0
@@ 184,6 184,9 @@ state_writeregister(struct state *, struct value *);
void
state_clearregister(struct state *);

bool
state_insetup(struct state *);

void
state_initsetup(struct state *s, int frameid);


M src/ast/breakpoint.c => src/ast/breakpoint.c +2 -8
@@ 29,16 29,10 @@ char *
breakpoint_list()
{
	struct strbuilder *b = strbuilder_create();
	strbuilder_printf(b, "Num\tType\tEnabled\tReached\tWhat\n");
	strbuilder_printf(b, "Num\tLine\n");
	for (int i = 0; i < breakpoint_count; i++) {
		struct breakpoint bp = breakpoints[i];
		strbuilder_printf( b,
			"%d\tbreak\t%s\t%s\t%s\n",
			i,
			bp.enabled ? dynamic_str("y") : dynamic_str("n"),
			bp.reached ? dynamic_str("y") : dynamic_str("n"),
			breakpoint_str(bp)
		);
		strbuilder_printf(b, "%d\t%s\n", i, breakpoint_str(bp));
	}
	return strbuilder_build(b);
}

M src/ast/expr/verify.c => src/ast/expr/verify.c +16 -0
@@ 20,6 20,9 @@ static bool
expr_unary_decide(struct ast_expr *expr, struct state *state);

static bool
expr_identifier_decide(struct ast_expr *expr, struct state *state);

static bool
expr_isdeallocand_decide(struct ast_expr *expr, struct state *state);

static bool


@@ 31,6 34,8 @@ ast_expr_decide(struct ast_expr *expr, struct state *state)
	switch (ast_expr_kind(expr)) {
	case EXPR_CONSTANT:
		return (bool) ast_expr_as_constant(expr);
	case EXPR_IDENTIFIER:
		return expr_identifier_decide(expr, state);
	case EXPR_UNARY:
		return expr_unary_decide(expr, state);
	case EXPR_ISDEALLOCAND:


@@ 55,6 60,17 @@ expr_unary_decide(struct ast_expr *expr, struct state *state)
}

static bool
expr_identifier_decide(struct ast_expr *expr, struct state *state)
{
	struct ast_expr *prop = ast_expr_binary_create(
		ast_expr_copy(expr), BINARY_OP_NE, ast_expr_constant_create(0)
	);
	bool res = ast_expr_decide(prop, state);
	ast_expr_destroy(prop);
	return res;
}

static bool
unary_rangedecide(struct ast_expr *expr, struct ast_expr *lw,
		struct ast_expr *up, struct state *);


M src/ast/function/function.c => src/ast/function/function.c +204 -18
@@ 4,6 4,8 @@
#include <string.h>
#include <ctype.h>

#include "gram_util.h"
#include "gram.tab.h"
#include "ast.h"
#include "lex.h"
#include "function.h"


@@ 238,9 240,11 @@ ast_function_debug(struct ast_function *f, struct externals *ext)
}

enum command_kind {
	COMMAND_HELP,
	COMMAND_STEP,
	COMMAND_NEXT,
	COMMAND_CONTINUE,
	COMMAND_VERIFY,
	COMMAND_QUIT,
	COMMAND_BREAKPOINT_SET,
	COMMAND_BREAKPOINT_LIST,


@@ 276,21 280,26 @@ command_destroy(struct command *cmd)
	free(cmd);
}


bool should_continue = false;

static struct command *
getcmd();

static struct error *
command_continue(struct path *);
command_continue_exec(struct path *);

static struct error *
command_verify_exec(struct path *, struct command *);

static struct ast_expr *
command_arg_toexpr(struct command *);

static struct error *
next_command(struct path *p)
{
	if (should_continue) {
		should_continue = false;
		return command_continue(p);
		return command_continue_exec(p);
	}
	struct command *cmd = getcmd();
	switch (cmd->kind) {


@@ 298,10 307,13 @@ next_command(struct path *p)
		return path_step(p);
	case COMMAND_NEXT:
		return path_next(p);	
	case COMMAND_VERIFY:
		return command_verify_exec(p, cmd);
	case COMMAND_CONTINUE:
		return command_continue(p);
		return command_continue_exec(p);
	case COMMAND_QUIT:
		exit(0);
	case COMMAND_HELP:
	case COMMAND_BREAKPOINT_SET:
	case COMMAND_BREAKPOINT_LIST:
		return NULL;


@@ 310,9 322,8 @@ next_command(struct path *p)
	}
}


static struct error *
command_continue(struct path *p)
command_continue_exec(struct path *p)
{
	while (!path_atend(p)) {
		struct error *err = path_step(p);


@@ 328,6 339,46 @@ command_continue(struct path *p)
	return NULL;
}

static struct error *
command_verify_exec(struct path *p, struct command *cmd)
{
	struct error *err = path_verify(p, command_arg_toexpr(cmd));
	if (err) {
		d_printf("false: %s\n", error_str(err));
	} else {
		d_printf("true\n");
	}
	return NULL;
}

struct ast_expr *YACC_PARSED_EXPR;

int
yyparse();

static struct ast_expr *
command_arg_toexpr(struct command *c)
{
	extern FILE *yyin;
	extern int LEX_START_TOKEN;

	char *str = string_arr_s(c->args)[0];
	yyin = fmemopen(str, strlen(str), "r"); // Open the buffer for read/write
	if (!yyin) {
		fprintf(stderr, "error opening memory file\n");
		exit(EXIT_FAILURE);
	}

	/* lex and parse */
	LEX_START_TOKEN = START_EXPR;
	lex_begin();
	yyparse();
	yylex_destroy();
	/* lex_finish(); */

	return ast_expr_copy(YACC_PARSED_EXPR);
}


/* getcmd() */



@@ 349,8 400,8 @@ getcmd()
	char cmd[MAX_COMMANDLEN];
	char args[MAX_ARGSLEN];
	if (!fgets(line, MAX_LINELEN, stdin)) {
		fprintf(stderr, "error: cannot read\n");
		return getcmd();
		fprintf(stderr, "error: cannot read line\n");
		exit(EXIT_FAILURE);
	}
	char *space = strchr(line, ' ');
	if (space == NULL) {


@@ 368,6 419,12 @@ getcmd()
	}
}

static struct command *
command_create_help();

static bool
command_ishelp(char *cmd);

static bool
command_isstep(char *cmd);



@@ 383,7 440,9 @@ command_isquit(char *cmd);
static struct command *
process_command(char *cmd)
{
	if (command_isstep(cmd)) {
	if (command_ishelp(cmd)) {
		return command_create_help(COMMAND_HELP);
	} else if (command_isstep(cmd)) {
		return command_create(COMMAND_STEP);
	} else if (command_isnext(cmd)) {
		return command_create(COMMAND_NEXT);


@@ 392,12 451,30 @@ process_command(char *cmd)
	} else if (command_isquit(cmd)) {
		return command_create(COMMAND_QUIT);
	} else {
		fprintf(stderr, "unknown command `%s'\n", cmd);
		d_printf("unknown command `%s'\n", cmd);
		return getcmd();
	}
}

static bool
command_ishelp(char *cmd)
{
	return strcmp(cmd, "h") == 0 || strcmp(cmd, "help") == 0;
}

static struct command *
command_create_help()
{
	d_printf("List of commands:\n");
	d_printf("step -- Step to next logical statement.\n");
	d_printf("next -- Step over.\n");
	d_printf("break -- Set breakpoint.\n");
	d_printf("continue -- Step until breakpoint, error or end.\n");
	d_printf("quit -- Quit.\n\n");
	return command_create(COMMAND_HELP);
}

static bool
command_isstep(char *cmd)
{
	return strcmp(cmd, "s") == 0 || strcmp(cmd, "step") == 0;


@@ 424,24 501,39 @@ command_isquit(char *cmd)
static struct string_arr *
args_tokenise(char *args);

static struct command *
command_help(struct string_arr *args);

static bool
command_isbreak(char *cmd);

static struct command *
command_break(struct string_arr *args);

static bool
command_isverify(char *cmd);

static struct command *
command_verify(char *arg);

static struct command *
process_commandwithargs(char *cmd, char *args)
{
	struct string_arr *args_tk = args_tokenise(args);
	struct string_arr *args_tk = args_tokenise(dynamic_str(args));
	if (args_tk == NULL) {
		fprintf(stderr, "invalid command args: %s\n", args);
		return getcmd();
	}
	if (command_isbreak(cmd)) {
	if (command_ishelp(cmd)) {
		return command_help(args_tk);
	} else if (command_isbreak(cmd)) {
		return command_break(args_tk);	
	} else if (command_isverify(cmd)) {
		return command_verify(args);
	} else {
		d_printf("unknown command `%s'\n", cmd);
		return getcmd();
	}
	assert(false);
}

static struct string_arr *


@@ 457,6 549,88 @@ args_tokenise(char *args)
	return arg_arr;
}

static void
command_help_step();

static void
command_help_next();

static void
command_help_continue();

static void
command_help_break();

static void
command_help_quit();

static struct command *
command_help(struct string_arr *args)
{
	if (string_arr_n(args) != 1) {
		d_printf("`help' expects single argument\n");
		return getcmd();
	}
	char *arg = string_arr_s(args)[0];
	if (command_isstep(arg)) {
		command_help_step();
	} else if (command_isnext(arg)) {
		command_help_next();
	} else if (command_iscontinue(arg)) {
		command_help_continue();
	} else if (command_isbreak(arg)) {
		command_help_break();
	} else if (command_isquit(arg)) {
		command_help_quit();
	} else {
		d_printf("`help' received unknown argument\n");
		return getcmd();
	}
	return command_create(COMMAND_HELP);
}

static void
command_help_step()
{
	d_printf("Step to the next logical statement, entering\n");
	d_printf("the current one when appropriate.\n");
	d_printf("Usage: s(tep)\n\n");
}

static void
command_help_next()
{
	d_printf("Step over the current statement.\n");
	d_printf("Usage: n(ext)\n\n");
}

static void
command_help_continue()
{
	d_printf("Step until breakpoint, error or end.\n");
	d_printf("Usage: c(ontinue)\n\n");
}

static void
command_help_break()
{
	d_printf("break -- Set breakpoint.\n");
	d_printf("Usage: b(reak) [LINE_NUMBER]\n\n");

	d_printf("list -- List all breakpoints.\n");
	d_printf("Usage: b(reak) list\n\n");

	d_printf("Note: Currently breakpoints can only be\n");
	d_printf("set on statements.\n\n");
}

static void
command_help_quit()
{
	d_printf("Quit.\n");
	d_printf("Usage: q(uit)\n");
}

static bool
command_isbreak(char *cmd)
{


@@ 493,7 667,6 @@ command_break(struct string_arr *args)
	}
}


static bool
isint(const char *str) {
	if (str == NULL || *str == '\0') {


@@ 529,8 702,7 @@ break_set(char *arg)
	int linenum = atoi(arg);
	struct error *err = breakpoint_set("", linenum);
	if (err) {
		fprintf(stderr, "could not set breakpoint: %s", error_str(err));
		return getcmd();
		d_printf("could not set breakpoint: %s", error_str(err));
	}
	return command_create(COMMAND_BREAKPOINT_SET);
}


@@ 556,11 728,25 @@ break_argsplit(char *arg)
	return split;
}

static bool
command_isverify(char *cmd)
{
	return strcmp(cmd, "v") == 0 || strcmp(cmd, "verify") == 0;
}

static struct command *
command_verify(char *arg)
{
	struct string_arr *sarr = string_arr_create();
	string_arr_append(sarr, dynamic_str(arg));
	return command_create_withargs(COMMAND_VERIFY, sarr);
}

static struct command *
break_list()
{
	printf("%s\n", breakpoint_list());
	return getcmd();
	d_printf("%s\n", breakpoint_list());
	return command_create(COMMAND_BREAKPOINT_LIST);
}

static struct error *

M src/ast/gram.y => src/ast/gram.y +10 -1
@@ 100,7 100,7 @@ variable_array_create(struct ast_variable *v)
%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR SOME GOTO CONTINUE BREAK RETURN
%token TK_ALLOC TK_DEALLOC TK_CLUMP

%start translation_unit
%token START_AST START_EXPR

%union {
	char *string;


@@ 187,8 187,17 @@ variable_array_create(struct ast_variable *v)
%type <variable> parameter_declaration struct_declaration
%type <variable_array> declaration_list parameter_list parameter_type_list
%type <variable_array> struct_declaration_list

%start start

%%

start
	: START_AST translation_unit
	| START_EXPR expression
		{ YACC_PARSED_EXPR = $2; }
	;

primary_expression
	: identifier
		{ $$ = ast_expr_identifier_create($1); }

M src/ast/lex.l => src/ast/lex.l +11 -0
@@ 28,6 28,17 @@ check_type();
%}

%%

%{
	extern int LEX_START_TOKEN;
	if (LEX_START_TOKEN) {
		int t = LEX_START_TOKEN;
		LEX_START_TOKEN = 0;
		return t;
	}
%}


"#"			{ preproc(); }
"/*"			{ comment(); }
".malloc"		{ count(); return(TK_ALLOC); }

M src/ast/stmt/verify.c => src/ast/stmt/verify.c +3 -1
@@ 170,6 170,8 @@ iter_empty(struct ast_stmt *stmt, struct state *state);
static struct error *
stmt_iter_verify(struct ast_stmt *stmt, struct state *state)
{
	assert(false);

	/* check for empty sets */
	if (iter_empty(stmt, state)) {
		return NULL;


@@ 519,7 521,7 @@ labelled_absexec(struct ast_stmt *stmt, struct state *state)
		return error_printf("setup preconditions must be decidable");
	}
	struct ast_block *b = ast_stmt_labelled_as_block(stmt);	
	struct frame *setup_frame = frame_block_create(
	struct frame *setup_frame = frame_setup_create(
		dynamic_str("setup"),
		b,
		state_next_execmode(state)

M src/main.c => src/main.c +35 -2
@@ 195,8 195,6 @@ preprocess(char *infile, struct string_arr *includedirs)
	return tmp;
}

struct ast *root;

static bool
verifyproto(struct ast_function *f, int n, struct ast_externdecl **decl);



@@ 232,6 230,9 @@ pass0(struct ast *root, struct externals *ext)
	}
}

static void
debugger_summary();

static struct error *
handle_debug(struct ast_function *, struct externals *, bool debug);



@@ 239,6 240,10 @@ void
pass1(struct ast *root, struct externals *ext, bool debug)
{
	struct error *err;
	if (debug) {
		debugger_summary();
	}

	for (int i = 0; i < root->n; i++) {
		struct ast_externdecl *decl = root->decl[i];
		if (!ast_externdecl_isfunction(decl)) {


@@ 258,6 263,29 @@ pass1(struct ast *root, struct externals *ext, bool debug)
	}
}

static void
debugger_summary()
{
	d_printf("0db: The Xr0 Static Debugger for C\n");
	d_printf("Copyright (C) 2024 Xr0\n");
	d_printf("License Apache 2.0\n\n");

	d_printf("A static debugger is the compile-time analogue of\n");
	d_printf("runtime debuggers like GDB. Runtime debuggers\n");
	d_printf("require you to execute a program in order to\n");
	d_printf("analyse it, but 0db shows line-by-line the state\n");
	d_printf("of a C program on the basis of the semantics of\n");
	d_printf("the language alone.\n\n");

	d_printf("This matters because at runtime we interact with a\n");
	d_printf("very tiny subset of a program’s possible\n");
	d_printf("behaviours. In the state supplied by 0db you see\n");
	d_printf("at once what applies to all possible executions\n");
	d_printf("of a program.\n\n");

	d_printf("For help, type \"help\".\n\n\n");
}

static struct error *
handle_debug(struct ast_function *f, struct externals *ext, bool debug)
{


@@ 354,6 382,10 @@ proto_defisvalid(struct ast_function *proto, struct ast_function *def)
	return false;
}

struct ast *root;

int LEX_START_TOKEN;

static int
verify(struct config *c);



@@ 391,6 423,7 @@ verify(struct config *c)
	yyin = preprocess(c->infile, c->includedirs);

	/* lex and parse */
	LEX_START_TOKEN = START_AST;
	lex_begin();
	yyparse();
	yylex_destroy();

M src/path/path.c => src/path/path.c +40 -10
@@ 130,8 130,9 @@ char *
path_abstract_str(struct path *p)
{
	struct strbuilder *b = strbuilder_create();
	bool insetup = state_insetup(p->abstract);
	strbuilder_printf(
		b, "mode: %s\n", state_execmode_str(state_execmode(p->abstract))
		b, "phase:\t%s\n\n", insetup ? "SETUP (ABSTRACT)" : state_execmode_str(state_execmode(p->abstract))
	);
	strbuilder_printf(b, "text:\n%s\n", state_programtext(p->abstract));
	strbuilder_printf(b, "%s\n", state_str(p->abstract));


@@ 142,8 143,9 @@ char *
path_actual_str(struct path *p)
{
	struct strbuilder *b = strbuilder_create();
	bool insetup = state_insetup(p->actual);
	strbuilder_printf(
		b, "mode: %s\n", state_execmode_str(state_execmode(p->actual))
		b, "phase:\t%s\n\n", insetup ? "SETUP (ACTUAL)" : state_execmode_str(state_execmode(p->actual))
	);
	strbuilder_printf(b, "text:\n%s\n", state_programtext(p->actual));
	strbuilder_printf(b, "%s\n", state_str(p->actual));


@@ 253,7 255,7 @@ path_step_abstract(struct path *p, bool print)
{	
	if (state_atend(p->abstract) && state_frameid(p->abstract) == 0) {
		p->path_state = PATH_STATE_HALFWAY;
		return path_step(p);
		return NULL;
	}

	struct error *err = state_step(p->abstract);


@@ 350,8 352,6 @@ split_name(char *name, struct ast_expr *assumption)
	return strbuilder_build(b);
}



static struct error *
path_init_actual(struct path *p)
{


@@ 386,7 386,7 @@ path_step_actual(struct path *p, bool print)
{	
	if (state_atend(p->actual) && state_frameid(p->actual) == 0) {
		p->path_state = PATH_STATE_AUDIT;
		return path_step(p);
		return NULL;
	}

	struct error *err = state_step(p->actual);


@@ 442,7 442,7 @@ path_step_split(struct path *p)
static struct error *
branch_step(struct path *parent, struct path *branch)
{
	d_printf("branch: %d\n", parent->branch_index);
	v_printf("branch: %d\n", parent->branch_index);
	if (path_atend(branch)) {
		path_nextbranch(parent);
		return NULL;


@@ 489,7 489,7 @@ path_next_abstract(struct path *p)
{
	if (state_atend(p->abstract) && state_frameid(p->abstract) == 0) {
		p->path_state = PATH_STATE_HALFWAY;
		return path_step(p);
		return NULL;
	}
	struct error *err = state_next(p->abstract);
	if (!err) {


@@ 508,7 508,7 @@ path_next_actual(struct path *p)
{
	if (state_atend(p->actual) && state_frameid(p->actual) == 0) {
		p->path_state = PATH_STATE_AUDIT;
		return path_step(p);
		return NULL;
	}
	struct error *err = state_next(p->actual);
	if (!err) {


@@ 540,7 540,7 @@ path_next_split(struct path *p)
static struct error *
branch_next(struct path *parent, struct path *branch)
{
	d_printf("branch: %d\n", parent->branch_index);
	v_printf("branch: %d\n", parent->branch_index);
	if (path_atend(branch)) {
		path_nextbranch(parent);
		return NULL;


@@ 548,6 548,36 @@ branch_next(struct path *parent, struct path *branch)
	return path_next(branch);
}

static struct error *
path_split_verify(struct path *, struct ast_expr *);

struct error *
path_verify(struct path *p, struct ast_expr *expr)
{
	switch(p->path_state) {
	case PATH_STATE_ABSTRACT:
		return ast_stmt_verify(ast_stmt_create_expr(NULL, expr), p->abstract);
	case PATH_STATE_ACTUAL:
		return ast_stmt_verify(ast_stmt_create_expr(NULL, expr), p->actual);	
	case PATH_STATE_SPLIT:
		return path_split_verify(p, expr);
	case PATH_STATE_UNINIT:
	case PATH_STATE_HALFWAY:
	case PATH_STATE_AUDIT:
	case PATH_STATE_ATEND:
		return NULL;
	default:
		assert(false);
	}
}

static struct error *
path_split_verify(struct path *p, struct ast_expr *expr)
{
	struct path *branch = p->paths->paths[p->branch_index];
	return path_verify(branch, expr);
}

static struct lexememarker *
path_split_lexememarker(struct path *);


M src/state/program.c => src/state/program.c +1 -1
@@ 100,7 100,7 @@ program_render(struct program *p)
		strbuilder_printf(b, "%s", ast_block_render(p->b, p->index, false));
		break;
	case PROGRAM_COUNTER_ATEND:
		strbuilder_printf(b, "\t<end of frame>");
		strbuilder_printf(b, "\t<end of frame>\n");
		break;
	default:
		assert(false);

M src/state/state.c => src/state/state.c +2 -2
@@ 106,7 106,7 @@ state_str(struct state *state)
	free(static_mem);
	if (state->reg) {
		char *ret = value_str(state->reg);
		strbuilder_printf(b, "return: <%s>\n\n", ret);
		strbuilder_printf(b, "return:\t<%s>\n\n", ret);
		free(ret);
	}
	char *vconst = vconst_str(state->vconst, "\t");


@@ 143,7 143,7 @@ state_islinear(struct state *s)
	return stack_islinear(s->stack);
}

static bool
bool
state_insetup(struct state *s)
{
	return stack_insetup(s->stack);