blob: fa9435783c4703155a06a3a3f9b0d56ae54e92d8 [file] [log] [blame]
/*******************************************************************************
* Copyright (c) 2007 Wind River Systems, Inc. and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* Wind River Systems - initial API and implementation
*******************************************************************************/
/*
* Expression evaluation library.
*/
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "mdep.h"
#include "myalloc.h"
#include "exceptions.h"
#include "expressions.h"
#define STR_POOL_SIZE 1024
struct StringValue {
struct StringValue * next;
char buf[1];
};
typedef struct StringValue StringValue;
#define SY_LEQ 256
#define SY_GEQ 257
#define SY_EQU 258
#define SY_NEQ 259
#define SY_AND 260
#define SY_OR 261
#define SY_SHL 262
#define SY_SHR 263
#define SY_VAL 264
#define SY_ID 265
#define SY_REF 266
#define SY_DEC 267
#define SY_INC 268
#define SY_A_SUB 269
#define SY_A_ADD 270
#define SY_A_SHL 271
#define SY_A_SHR 272
#define SY_A_OR 273
#define SY_A_XOR 274
#define SY_A_AND 275
#define SY_A_MUL 276
#define SY_A_DIV 277
#define SY_A_MOD 278
static ExpressionContext * expr_ctx = NULL;
static char * text = NULL;
static int text_pos = 0;
static int text_ch = 0;
static int text_sy = 0;
static Value text_val;
static char text_error[256];
static char str_pool[STR_POOL_SIZE];
static int str_pool_cnt = 0;
static StringValue * str_alloc_list = NULL;
static char * alloc_str(int len) {
if (str_pool_cnt + len < STR_POOL_SIZE) {
char * s = str_pool + str_pool_cnt;
str_pool_cnt += len + 1;
return s;
}
else {
StringValue * s = (StringValue *)loc_alloc(sizeof(StringValue) + len);
s->next = str_alloc_list;
str_alloc_list = s;
return s->buf;
}
}
void string_value(Value * v, char * str) {
memset(v, 0, sizeof(Value));
v->type = VALUE_STR;
if (str != NULL) {
int len = strlen(str);
v->str = alloc_str(len);
memcpy(v->str, str, len + 1);
}
}
static void error(int no, char * msg) {
snprintf(text_error, sizeof(text_error),
"Expression evaluation error: %s, text pos %d", msg, text_pos);
exception(no);
}
static void next_ch(void) {
text_ch = (unsigned char)text[text_pos];
if (text_ch != 0) text_pos++;
}
static int next_hex(void) {
int ch = text_ch;
next_ch();
if (ch >= '0' && ch <= '9') return ch - '0';
if (ch >= 'A' && ch <= 'F') return ch - 'A' + 10;
if (ch >= 'a' && ch <= 'f') return ch - 'a' + 10;
error(ERR_INV_EXPRESSION, "Invalid hexadecimal number");
return 0;
}
static int next_oct(void) {
int ch = text_ch;
next_ch();
if (ch >= '0' && ch <= '7') return ch - '0';
error(ERR_INV_EXPRESSION, "Invalid octal number");
return 0;
}
static int next_dec(void) {
int ch = text_ch;
next_ch();
if (ch >= '0' && ch <= '9') return ch - '0';
error(ERR_INV_EXPRESSION, "Invalid decimal number");
return 0;
}
static int next_char_val(void) {
int n = 0;
if (text_ch == '\\') {
next_ch();
switch (text_ch) {
case 'n' : n = '\n'; break;
case 't' : n = '\t'; break;
case 'v' : n = '\v'; break;
case 'b' : n = '\b'; break;
case 'r' : n = '\r'; break;
case 'f' : n = '\f'; break;
case 'a' : n = '\a'; break;
case '\\': n = '\\'; break;
case '\'': n = '\''; break;
case '"' : n = '"'; break;
case 'x' :
next_ch();
n = next_hex() << 8;
n |= next_hex() << 4;
n |= next_hex();
return n;
case '0' :
case '1' :
case '2' :
case '3' :
n = next_oct() << 6;
n |= next_oct() << 3;
n |= next_oct();
return n;
default :
n = text_ch;
break;
}
}
else {
n = text_ch;
}
next_ch();
return n;
}
static int is_name_character(int ch) {
if (ch >= 'A' && ch <= 'Z') return 1;
if (ch >= 'a' && ch <= 'z') return 1;
if (ch >= '0' && ch <= '9') return 1;
if (ch == '_') return 1;
if (ch == '$') return 1;
if (ch == '@') return 1;
return 0;
}
static void next_sy(void) {
for (;;) {
int ch = text_ch;
next_ch();
switch (ch) {
case 0:
text_sy = 0;
return;
case ' ':
case '\r':
case '\n':
case '\t':
continue;
case '(':
case ')':
case '{':
case '}':
case '~':
case '[':
case ']':
case ';':
case ':':
case '?':
case ',':
case '.':
text_sy = ch;
return;
case '-':
if (text_ch == '>') {
next_ch();
text_sy = SY_REF;
return;
}
if (text_ch == '-') {
next_ch();
text_sy = SY_DEC;
return;
}
if (text_ch == '=') {
next_ch();
text_sy = SY_A_SUB;
return;
}
text_sy = ch;
return;
case '+':
if (text_ch == '+') {
next_ch();
text_sy = SY_INC;
return;
}
if (text_ch == '=') {
next_ch();
text_sy = SY_A_ADD;
return;
}
text_sy = ch;
return;
case '<':
if (text_ch == '<') {
next_ch();
if (text_ch == '=') {
next_ch();
text_sy = SY_A_SHL;
return;
}
text_sy = SY_SHL;
return;
}
if (text_ch == '=') {
next_ch();
text_sy = SY_LEQ;
return;
}
text_sy = ch;
return;
case '>':
if (text_ch == '>') {
next_ch();
if (text_ch == '=') {
next_ch();
text_sy = SY_A_SHR;
return;
}
text_sy = SY_SHR;
return;
}
if (text_ch == '=') {
next_ch();
text_sy = SY_GEQ;
return;
}
text_sy = ch;
return;
case '=':
if (text_ch == '=') {
next_ch();
text_sy = SY_EQU;
return;
}
text_sy = ch;
return;
case '!':
if (text_ch == '=') {
next_ch();
text_sy = SY_NEQ;
return;
}
text_sy = ch;
return;
case '&':
if (text_ch == '&') {
next_ch();
text_sy = SY_AND;
return;
}
if (text_ch == '=') {
next_ch();
text_sy = SY_A_AND;
return;
}
text_sy = ch;
return;
case '|':
if (text_ch == '|') {
next_ch();
text_sy = SY_OR;
return;
}
if (text_ch == '=') {
next_ch();
text_sy = SY_A_OR;
return;
}
text_sy = ch;
return;
case '*':
if (text_ch == '=') {
next_ch();
text_sy = SY_A_MUL;
return;
}
text_sy = ch;
return;
case '/':
if (text_ch == '|') {
next_ch();
text_sy = SY_A_DIV;
return;
}
text_sy = ch;
return;
case '%':
if (text_ch == '|') {
next_ch();
text_sy = SY_A_MOD;
return;
}
text_sy = ch;
return;
case '^':
if (text_ch == '=') {
next_ch();
text_sy = SY_A_XOR;
return;
}
text_sy = ch;
return;
case '\'':
text_val.type = VALUE_UNS;
text_val.str = NULL;
text_val.value = next_char_val();
if (text_ch != '\'') error(ERR_INV_EXPRESSION, "Missing 'single quote'");
next_ch();
text_sy = SY_VAL;
return;
case '"':
{
int len = 0;
int cnt = 0;
int pos = text_pos;
while (text_ch != '"') {
next_char_val();
len++;
}
text_val.type = VALUE_STR;
text_val.value = 0;
text_val.str = alloc_str(len);
text_pos = pos - 1;
next_ch();
while (text_ch != '"') {
text_val.str[cnt++] = next_char_val();
}
assert(cnt == len);
text_val.str[cnt] = 0;
next_ch();
text_sy = SY_VAL;
}
return;
case '0':
if (text_ch == 'x') {
next_ch();
text_val.type = VALUE_UNS;
text_val.str = NULL;
text_val.value = 0;
while (text_ch >= '0' && text_ch <= '9' ||
text_ch >= 'A' && text_ch <= 'F' ||
text_ch >= 'a' && text_ch <= 'f') {
text_val.value = (text_val.value << 4) | next_hex();
}
}
else {
text_val.type = VALUE_INT;
text_val.str = NULL;
text_val.value = 0;
while (text_ch >= '0' && text_ch <= '7') {
text_val.value = (text_val.value << 3) | next_oct();
}
}
text_sy = SY_VAL;
return;
default:
if (ch >= '0' && ch <= '9') {
text_val.type = VALUE_INT;
text_val.str = NULL;
text_val.value = ch - '0';
while (text_ch >= '0' && text_ch <= '9') {
text_val.value = (text_val.value * 10) + next_dec();
}
text_sy = SY_VAL;
return;
}
if (is_name_character(ch)) {
int len = 1;
int cnt = 0;
int pos = text_pos - 1;
while (is_name_character(text_ch)) {
len++;
next_ch();
}
text_val.type = VALUE_STR;
text_val.value = 0;
text_val.str = alloc_str(len);
text_pos = pos - 1;
next_ch();
while (is_name_character(text_ch)) {
text_val.str[cnt++] = text_ch;
next_ch();
}
assert(cnt == len);
text_val.str[cnt] = 0;
text_sy = SY_ID;
return;
}
error(ERR_INV_EXPRESSION, "Illegal character");
break;
}
}
}
static int to_boolean(Value * v) {
if (v == NULL) return 0;
switch (v->type) {
case VALUE_INT: return v->value != 0;
case VALUE_UNS: return v->value != 0;
case VALUE_STR: return v->str != NULL;
default: assert(0);
}
return 0;
}
static int to_int(Value * v) {
if (v == NULL) return 0;
switch (v->type) {
case VALUE_INT: return v->value;
case VALUE_UNS: return v->value;
case VALUE_STR: return v->str != NULL;
default: assert(0);
}
return 0;
}
static unsigned to_uns(Value * v) {
if (v == NULL) return 0;
switch (v->type) {
case VALUE_INT: return (unsigned)v->value;
case VALUE_UNS: return (unsigned)v->value;
case VALUE_STR: return v->str != NULL;
default: assert(0);
}
return 0;
}
static void expression(Value * v);
static void primary_expression(Value * v) {
if (text_sy == '(') {
next_sy();
expression(v);
if (text_sy != ')') error(ERR_INV_EXPRESSION, "Missing ')'");
next_sy();
}
else if (text_sy == SY_VAL) {
if (v) *v = text_val;
next_sy();
}
else if (text_sy == SY_ID) {
errno = 0;
if (expr_ctx->identifier == NULL || expr_ctx->identifier(text_val.str, v)) {
char msg[256];
int err = ERR_INV_EXPRESSION;
if (errno != 0) {
err = errno;
snprintf(msg, sizeof(msg), "Can't evaluate '%s': %d %s",
text_val.str, err, errno_to_str(err));
}
else {
snprintf(msg, sizeof(msg), "Undeclared identifier '%s'", text_val.str);
}
error(err, msg);
}
next_sy();
}
else {
error(ERR_INV_EXPRESSION, "Syntax error");
}
}
static void postfix_expression(Value * v) {
// TODO: postfix_expression()
primary_expression(v);
}
static void unary_expression(Value * v) {
// TODO: unary_expression()
postfix_expression(v);
}
static void cast_expression(Value * v) {
// TODO: cast_expression()
unary_expression(v);
}
static void multiplicative_expression(Value * v) {
cast_expression(v);
while (text_sy == '*' || text_sy == '/' || text_sy == '%') {
Value x;
int sy = text_sy;
next_sy();
cast_expression(v ? &x : NULL);
if (v) {
if (v->type == VALUE_STR || x.type == VALUE_STR) {
error(ERR_INV_EXPRESSION, "Operation is not applicable to string");
}
if (sy != '*' && x.value == 0) {
error(ERR_INV_EXPRESSION, "Dividing by zero");
}
if (v->type == VALUE_UNS || x.type == VALUE_UNS) {
switch (sy) {
case '*': v->value = to_uns(v) * to_uns(&x); break;
case '/': v->value = to_uns(v) / to_uns(&x); break;
case '%': v->value = to_uns(v) % to_uns(&x); break;
}
v->type = VALUE_UNS;
}
else {
switch (sy) {
case '*': v->value = to_int(v) * to_int(&x); break;
case '/': v->value = to_int(v) / to_int(&x); break;
case '%': v->value = to_int(v) % to_int(&x); break;
}
v->type = VALUE_INT;
}
}
}
}
static void additive_expression(Value * v) {
multiplicative_expression(v);
while (text_sy == '+' || text_sy == '-') {
Value x;
int sy = text_sy;
next_sy();
multiplicative_expression(v ? &x : NULL);
if (v) {
if (v->type == VALUE_STR && x.type == VALUE_STR) {
char * s;
if (sy != '+') error(ERR_INV_EXPRESSION, "Operation is not applicable to string");
if (v->str == NULL) {
v->str = x.str;
}
else if (x.str != NULL) {
s = alloc_str(strlen(v->str) + strlen(x.str));
strcpy(s, v->str);
strcat(s, x.str);
v->str = s;
}
}
else if (v->type == VALUE_STR || x.type == VALUE_STR) {
error(ERR_INV_EXPRESSION, "Operation is not applicable to string");
}
else if (v->type == VALUE_UNS || x.type == VALUE_UNS) {
switch (sy) {
case '+': v->value = to_uns(v) + to_uns(&x); break;
case '-': v->value = to_uns(v) - to_uns(&x); break;
}
v->type = VALUE_UNS;
}
else {
switch (sy) {
case '+': v->value = to_int(v) + to_int(&x); break;
case '-': v->value = to_int(v) - to_int(&x); break;
}
v->type = VALUE_INT;
}
}
}
}
static void shift_expression(Value * v) {
additive_expression(v);
while (text_sy == SY_SHL || text_sy == SY_SHR) {
Value x;
int sy = text_sy;
next_sy();
additive_expression(v ? &x : NULL);
if (v) {
if (v->type == VALUE_STR || x.type == VALUE_STR) {
error(ERR_INV_EXPRESSION, "Integral types expected");
}
if (x.type == VALUE_INT && to_int(&x) < 0) {
if (v->type == VALUE_UNS) {
switch (sy) {
case SY_SHL: v->value = to_uns(v) >> -to_int(&x); break;
case SY_SHR: v->value = to_uns(v) << -to_int(&x); break;
}
}
else {
switch (sy) {
case SY_SHL: v->value = to_int(v) >> -to_int(&x); break;
case SY_SHR: v->value = to_int(v) << -to_int(&x); break;
}
}
}
else {
if (v->type == VALUE_UNS) {
switch (sy) {
case SY_SHL: v->value = to_uns(v) << to_uns(&x); break;
case SY_SHR: v->value = to_uns(v) >> to_uns(&x); break;
}
}
else {
switch (sy) {
case SY_SHL: v->value = to_int(v) << to_uns(&x); break;
case SY_SHR: v->value = to_int(v) >> to_uns(&x); break;
}
}
}
}
}
}
static void relational_expression(Value * v) {
shift_expression(v);
while (text_sy == '<' || text_sy == '>' || text_sy == SY_LEQ || text_sy == SY_GEQ) {
Value x;
int sy = text_sy;
next_sy();
shift_expression(v ? &x : NULL);
if (v) {
if (v->type == VALUE_STR && x.type == VALUE_STR) {
int n = 0;
if (v->str == NULL && x.str == NULL) n = 0;
else if (v->str == NULL) n = -1;
else if (x.str == NULL) n = 1;
else n = strcmp(v->str, x.str);
switch (sy) {
case '<': v->value = n < 0; break;
case '>': v->value = n > 0; break;
case SY_LEQ: v->value = n <= 0; break;
case SY_GEQ: v->value = n >= 0; break;
}
}
else if (v->type == VALUE_UNS || x.type == VALUE_UNS) {
switch (sy) {
case '<': v->value = to_uns(v) < to_uns(&x); break;
case '>': v->value = to_uns(v) > to_uns(&x); break;
case SY_LEQ: v->value = to_uns(v) <= to_uns(&x); break;
case SY_GEQ: v->value = to_uns(v) >= to_uns(&x); break;
}
}
else {
switch (sy) {
case '<': v->value = to_int(v) < to_int(&x); break;
case '>': v->value = to_int(v) > to_int(&x); break;
case SY_LEQ: v->value = to_int(v) <= to_int(&x); break;
case SY_GEQ: v->value = to_int(v) >= to_int(&x); break;
}
}
v->str = NULL;
v->type = VALUE_INT;
}
}
}
static void equality_expression(Value * v) {
relational_expression(v);
while (text_sy == SY_EQU || text_sy == SY_NEQ) {
Value x;
int sy = text_sy;
next_sy();
relational_expression(v ? &x : NULL);
if (v) {
if (v->type == VALUE_STR && x.type == VALUE_STR) {
if (v->str == NULL && x.str == NULL) v->value = 1;
else if (v->str == NULL || x.str == NULL) v->value = 0;
else v->value = strcmp(v->str, x.str) == 0;
}
else {
v->value = to_int(v) == to_int(&x);
}
v->str = NULL;
v->type = VALUE_INT;
if (sy == SY_NEQ) v->value = !v->value;
}
}
}
static void and_expression(Value * v) {
equality_expression(v);
while (text_sy == '&') {
Value x;
next_sy();
equality_expression(v ? &x : NULL);
if (v) {
v->value = to_int(v) & to_int(&x);
v->str = NULL;
v->type = v->type == VALUE_UNS || x.type == VALUE_UNS ? VALUE_UNS : VALUE_INT;
}
}
}
static void exclusive_or_expression(Value * v) {
and_expression(v);
while (text_sy == '^') {
Value x;
next_sy();
and_expression(v ? &x : NULL);
if (v) {
v->value = to_int(v) ^ to_int(&x);
v->str = NULL;
v->type = v->type == VALUE_UNS || x.type == VALUE_UNS ? VALUE_UNS : VALUE_INT;
}
}
}
static void inclusive_or_expression(Value * v) {
exclusive_or_expression(v);
while (text_sy == '|') {
Value x;
next_sy();
exclusive_or_expression(v ? &x : NULL);
if (v) {
v->value = to_int(v) | to_int(&x);
v->str = NULL;
v->type = v->type == VALUE_UNS || x.type == VALUE_UNS ? VALUE_UNS : VALUE_INT;
}
}
}
static void logical_and_expression(Value * v) {
inclusive_or_expression(v);
while (text_sy == SY_AND) {
Value x;
int b = to_boolean(v);
next_sy();
inclusive_or_expression(v && b ? &x : NULL);
if (v && b) *v = x;
}
}
static void logical_or_expression(Value * v) {
logical_and_expression(v);
while (text_sy == SY_OR) {
Value x;
int b = to_boolean(v);
next_sy();
logical_and_expression(v && !b ? &x : NULL);
if (v && !b) *v = x;
}
}
static void conditional_expression(Value * v) {
logical_or_expression(v);
if (text_sy == '?') {
Value x;
Value y;
int b = to_boolean(v);
next_sy();
expression(v && b ? &x : NULL);
if (text_sy != ':') error(ERR_INV_EXPRESSION, "Missing ':'");
next_sy();
conditional_expression(v && !b ? &y : NULL);
if (v) *v = b ? x : y;
}
}
static void expression(Value * v) {
// TODO: assignments in expressions
conditional_expression(v);
}
int evaluate_expression(ExpressionContext * ctx, char * s, Value * v) {
int r = 0;
Trap trap;
if (set_trap(&trap)) {
expr_ctx = ctx;
text_error[0] = 0;
text_val.str = NULL;
str_pool_cnt = 0;
while (str_alloc_list != NULL) {
StringValue * str = str_alloc_list;
str_alloc_list = str->next;
loc_free(str);
}
text = s;
text_pos = 0;
next_ch();
next_sy();
expression(v);
if (text_sy != 0) error(ERR_INV_EXPRESSION, "Illegal characters at the end of expression");
clear_trap(&trap);
}
else {
errno = trap.error;
r = -1;
}
return r;
}
char * get_expression_error_msg(void) {
if (text_error[0] == 0) return NULL;
return text_error;
}
void ini_expression_library(void) {
#ifndef NDEBUG
Value v;
ExpressionContext ctx = { NULL, NULL };
assert(evaluate_expression(&ctx, "0", &v) == 0);
assert(v.type == VALUE_INT && v.value == 0 && v.str == NULL);
assert(evaluate_expression(&ctx, "0.", &v) != 0);
assert(evaluate_expression(&ctx, "2 * 2", &v) == 0);
assert(v.type == VALUE_INT && v.value == 4 && v.str == NULL);
assert(evaluate_expression(&ctx, "1 ? 2 : 3", &v) == 0);
assert(v.type == VALUE_INT && v.value == 2 && v.str == NULL);
assert(evaluate_expression(&ctx, "0 ? 2 : 3", &v) == 0);
assert(v.type == VALUE_INT && v.value == 3 && v.str == NULL);
assert(evaluate_expression(&ctx, "(1?2:3) == 2 && (0?2:3) == 3", &v) == 0);
assert(v.type == VALUE_INT && v.value == 1 && v.str == NULL);
assert(evaluate_expression(&ctx, "(1?2:3) != 2 || (0?2:3) != 3", &v) == 0);
assert(v.type == VALUE_INT && v.value == 0 && v.str == NULL);
assert(evaluate_expression(&ctx, "5>2 && 4<6", &v) == 0);
assert(v.type == VALUE_INT && v.value == 1 && v.str == NULL);
assert(evaluate_expression(&ctx, "5<=2 || 4>=6", &v) == 0);
assert(v.type == VALUE_INT && v.value == 0 && v.str == NULL);
assert(evaluate_expression(&ctx, "((5*2+7-1)/2)>>1==4 && 1<<3==8 && 5%2==1", &v) == 0);
assert(v.type == VALUE_INT && v.value == 1 && v.str == NULL);
assert(evaluate_expression(&ctx, "\042ABC\042 + \042DEF\042 == \042ABCDEF\042", &v) == 0);
assert(v.type == VALUE_INT && v.value == 1 && v.str == NULL);
#endif
}