#include "expr.h" #include static int bounded(int64_t value) { return value >= -EX_VALUE_LIMIT && value <= EX_VALUE_LIMIT; } static ex_status lookup(const ex_node *node, const ex_binding *bindings, size_t count, int64_t *value) { size_t i; for (i = 0; i < count; ++i) { if (bindings[i].name && !strcmp(node->name, bindings[i].name)) { if (bindings[i].value < -1000000000 || bindings[i].value > 1000000000) return EX_ARGUMENT; *value = bindings[i].value; return EX_OK; } } return EX_UNBOUND; } static ex_status checked_add(int64_t left, int64_t right, int64_t *out) { int64_t result = left + right; if (!bounded(result)) return EX_ARITH; *out = result; return EX_OK; } static ex_status checked_sub(int64_t left, int64_t right, int64_t *out) { int64_t result = left - right; if (!bounded(result)) return EX_ARITH; *out = result; return EX_OK; } static ex_status checked_mul(int64_t left, int64_t right, int64_t *out) { int64_t a = left < 0 ? -left : left; int64_t b = right < 0 ? -right : right; if (a && b > EX_VALUE_LIMIT / a) return EX_ARITH; *out = left * right; return EX_OK; } static ex_status evaluate_node(const ex_node *node, const ex_binding *bindings, size_t count, int64_t *out) { int64_t values[EX_MAX_CHILDREN]; int64_t value; size_t i; ex_status status; if (node->kind == EX_NUMBER) { *out = node->number; return EX_OK; } if (node->kind == EX_VARIABLE) return lookup(node, bindings, count, out); for (i = 0; i < node->arity; ++i) { status = evaluate_node(node->child[i], bindings, count, &values[i]); if (status != EX_OK) return status; } switch (node->kind) { case EX_ADD: return checked_add(values[0], values[1], out); case EX_SUB: return checked_sub(values[0], values[1], out); case EX_MUL: return checked_mul(values[0], values[1], out); case EX_MIN: *out = values[0] < values[1] ? values[0] : values[1]; return EX_OK; case EX_MAX: *out = values[0] > values[1] ? values[0] : values[1]; return EX_OK; case EX_NEG: *out = -values[0]; return EX_OK; case EX_ABS: *out = values[0] < 0 ? -values[0] : values[0]; return EX_OK; case EX_SUM: value = 0; for (i = 0; i < node->arity; ++i) { status = checked_add(value, values[i], &value); if (status != EX_OK) return status; } *out = value; return EX_OK; default: return EX_ARGUMENT; } } static int valid_binding_name(const char *name) { size_t i; if (!name || name[0] < 'a' || name[0] > 'z') return 0; for (i = 1; name[i]; ++i) { unsigned char c = (unsigned char)name[i]; if (i == EX_NAME_SIZE - 1 || !((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') || c == '_')) return 0; } return 1; } ex_status ex_evaluate(const ex_tree *tree, const ex_binding *bindings, size_t count, int64_t *out) { size_t i, j; int64_t result; ex_status status; if (!tree || !out || (!bindings && count) || count > 64) return EX_ARGUMENT; for (i = 0; i < count; ++i) { if (!valid_binding_name(bindings[i].name) || bindings[i].value < -1000000000 || bindings[i].value > 1000000000) return EX_ARGUMENT; for (j = 0; j < i; ++j) { if (!strcmp(bindings[i].name, bindings[j].name)) return EX_ARGUMENT; } } if (!tree->root) { *out = 0; return EX_OK; } status = evaluate_node(tree->root, bindings, count, &result); if (status == EX_OK) *out = result; return status; }