morpheus-base

morpheus base system
git clone git://git.2f30.org/morpheus-base
Log | Files | Refs

expr.c (5740B)


      1 /* See LICENSE file for copyright and license details. */
      2 #include <inttypes.h>
      3 #include <limits.h>
      4 #include <regex.h>
      5 #include <stdint.h>
      6 #include <stdio.h>
      7 #include <stdlib.h>
      8 #include <string.h>
      9 
     10 #include "util.h"
     11 
     12 enum {
     13 	VAL = CHAR_MAX + 1, GE, LE, NE
     14 };
     15 
     16 typedef struct {
     17 	char *s;
     18 	intmax_t n;
     19 } Val;
     20 
     21 static void enan(Val);
     22 static void ezero(intmax_t);
     23 static void doop(int*, int**, Val*, Val**);
     24 static Val match(Val, Val);
     25 static int valcmp(Val, Val);
     26 static char *valstr(Val, char *, size_t);
     27 static int lex(char *);
     28 static int parse(char **, int);
     29 
     30 static size_t intlen;
     31 static Val lastval;
     32 
     33 static void
     34 enan(Val v)
     35 {
     36 	if (v.s)
     37 		enprintf(2, "syntax error: expected integer got `%s'\n", v.s);
     38 }
     39 
     40 static void
     41 ezero(intmax_t n)
     42 {
     43 	if (n == 0)
     44 		enprintf(2, "division by zero\n");
     45 }
     46 
     47 static void
     48 doop(int *op, int **opp, Val *val, Val **valp)
     49 {
     50 	Val ret, a, b;
     51 	int o;
     52 
     53 	/* For an operation, we need a valid operator
     54 	 * and two values on the stack */
     55 	if ((*opp)[-1] == '(')
     56 		enprintf(2, "syntax error: extra (\n");
     57 	if (*valp - val < 2)
     58 		enprintf(2, "syntax error: missing expression or extra operator\n");
     59 
     60 	a = (*valp)[-2];
     61 	b = (*valp)[-1];
     62 	o = (*opp)[-1];
     63 
     64 	switch (o) {
     65 	case '|':
     66 		if (a.s && *a.s) {
     67 			ret = (Val){ a.s, 0 };
     68 		} else if (!a.s && a.n) {
     69 			ret = (Val){ NULL, a.n };
     70 		} else if (b.s && *b.s) {
     71 			ret = (Val){ b.s, 0 };
     72 		} else {
     73 			ret = (Val){ NULL, b.n };
     74 		}
     75 		break;
     76 	case '&':
     77 		if (((a.s && *a.s) || a.n) &&
     78 		    ((b.s && *b.s) || b.n)) {
     79 			ret = a;
     80 		} else {
     81 			ret = (Val){ NULL, 0 };
     82 		}
     83 		break;
     84 	case '=': ret = (Val){ NULL, valcmp(a, b) == 0 }; break;
     85 	case '>': ret = (Val){ NULL, valcmp(a, b) >  0 }; break;
     86 	case GE : ret = (Val){ NULL, valcmp(a, b) >= 0 }; break;
     87 	case '<': ret = (Val){ NULL, valcmp(a, b) <  0 }; break;
     88 	case LE : ret = (Val){ NULL, valcmp(a, b) <= 0 }; break;
     89 	case NE : ret = (Val){ NULL, valcmp(a, b) != 0 }; break;
     90 
     91 	case '+': enan(a); enan(b); ret = (Val){ NULL, a.n + b.n }; break;
     92 	case '-': enan(a); enan(b); ret = (Val){ NULL, a.n - b.n }; break;
     93 	case '*': enan(a); enan(b); ret = (Val){ NULL, a.n * b.n }; break;
     94 	case '/': enan(a); enan(b); ezero(b.n); ret = (Val){ NULL, a.n / b.n }; break;
     95 	case '%': enan(a); enan(b); ezero(b.n); ret = (Val){ NULL, a.n % b.n }; break;
     96 
     97 	case ':': ret = match(a, b); break;
     98 	}
     99 
    100 	(*valp)[-2] = ret;
    101 	(*opp)--;
    102 	(*valp)--;
    103 }
    104 
    105 static Val
    106 match(Val vstr, Val vregx)
    107 {
    108 	intmax_t d;
    109 	char *anchreg, *ret, *p;
    110 	char buf1[intlen], buf2[intlen], *str, *regx;
    111 	regoff_t len;
    112 	regex_t re;
    113 	regmatch_t matches[2];
    114 
    115 	str = valstr(vstr, buf1, sizeof(buf1));
    116 	regx = valstr(vregx, buf2, sizeof(buf2));
    117 
    118 	anchreg = malloc(strlen(regx) + 2);
    119 	if (!anchreg)
    120 		enprintf(3, "malloc:");
    121 	snprintf(anchreg, strlen(regx) + 2, "^%s", regx);
    122 
    123 	enregcomp(3, &re, anchreg, 0);
    124 	free(anchreg);
    125 
    126 	if (regexec(&re, str, 2, matches, 0)) {
    127 		regfree(&re);
    128 		return (Val){ (re.re_nsub ? "" : NULL), 0 };
    129 	}
    130 
    131 	if (re.re_nsub) {
    132 		regfree(&re);
    133 		len = matches[1].rm_eo - matches[1].rm_so + 1;
    134 		ret = malloc(len);
    135 		if (!ret)
    136 			enprintf(3, "malloc:");
    137 		strlcpy(ret, str + matches[1].rm_so, len);
    138 		d = strtoimax(ret, &p, 10);
    139 		if (*ret && !*p) {
    140 			free(ret);
    141 			return (Val){ NULL, d };
    142 		}
    143 		return (Val){ ret, 0 };
    144 	}
    145 	regfree(&re);
    146 	return (Val){ NULL, matches[0].rm_eo - matches[0].rm_so };
    147 }
    148 
    149 
    150 
    151 static int
    152 valcmp(Val a, Val b)
    153 {
    154 	char buf1[intlen], buf2[intlen], *astr, *bstr;
    155 
    156 	astr = valstr(a, buf1, sizeof(buf1));
    157 	bstr = valstr(b, buf2, sizeof(buf2));
    158 
    159 	return strcmp(astr, bstr);
    160 }
    161 
    162 static char *
    163 valstr(Val val, char *buf, size_t bufsiz)
    164 {
    165 	if (val.s)
    166 		return val.s;
    167 	snprintf(buf, bufsiz, "%"PRIdMAX, val.n);
    168 	return buf;
    169 }
    170 
    171 static int
    172 lex(char *p)
    173 {
    174 	intmax_t d;
    175 	char *q, *ops = "|&=><+-*/%():";
    176 
    177 	/* clean integer */
    178 	d = strtoimax(p, &q, 10);
    179 	if (*p && !*q) {
    180 		lastval = (Val){ NULL, d };
    181 		return VAL;
    182 	}
    183 
    184 	/* one-char operand */
    185 	if (*p && !*(p+1) && strchr(ops, *p))
    186 		return *p;
    187 
    188 	/* two-char operand */
    189 	if (*p && *(p+1) == '=' && !*(p+2)) {
    190 		switch (*p) {
    191 		case '>':
    192 			return GE;
    193 		case '<':
    194 			return LE;
    195 		case '!':
    196 			return NE;
    197 		}
    198 	}
    199 
    200 	/* nothing matched, treat as string */
    201 	lastval = (Val){ p, 0 };
    202 	return VAL;
    203 }
    204 
    205 static int
    206 parse(char **expr, int exprlen)
    207 {
    208 	Val val[exprlen], *valp = val;
    209 	int op[exprlen], *opp = op;
    210 	int i, type, lasttype = 0;
    211 	char prec[] = {
    212 		[ 0 ] = 0, [VAL] = 0,
    213 		['|'] = 1,
    214 		['&'] = 2,
    215 		['='] = 3, ['>'] = 3, [GE] = 3, ['<'] = 3, [LE] = 3, [NE] = 3,
    216 		['+'] = 4, ['-'] = 4,
    217 		['*'] = 5, ['/'] = 5, ['%'] = 5,
    218 		[':'] = 6,
    219 	};
    220 
    221 	for (i = 0; i < exprlen; i++) {
    222 		type = lex(expr[i]);
    223 
    224 		switch (type) {
    225 		case VAL:
    226 			*valp++ = lastval;
    227 			break;
    228 		case '(':
    229 			*opp++ = '(';
    230 			break;
    231 		case ')':
    232 			if (lasttype == '(')
    233 				enprintf(2, "syntax error: empty ( )\n");
    234 			while (opp > op && opp[-1] != '(')
    235 				doop(op, &opp, val, &valp);
    236 			if (opp == op)
    237 				enprintf(2, "syntax error: extra )\n");
    238 			opp--;
    239 			break;
    240 		default :
    241 			if (prec[lasttype])
    242 				enprintf(2, "syntax error: extra operator\n");
    243 			while (opp > op && prec[opp[-1]] >= prec[type])
    244 				doop(op, &opp, val, &valp);
    245 			*opp++ = type;
    246 			break;
    247 		}
    248 		lasttype = type;
    249 	}
    250 	while (opp > op)
    251 		doop(op, &opp, val, &valp);
    252 
    253 	if (valp == val)
    254 		enprintf(2, "syntax error: missing expression\n");
    255 	if (valp - val > 1)
    256 		enprintf(2, "syntax error: extra expression\n");
    257 
    258 	valp--;
    259 	if (valp->s)
    260 		printf("%s\n", valp->s);
    261 	else
    262 		printf("%"PRIdMAX"\n", valp->n);
    263 
    264 	return (valp->s && *valp->s) || valp->n;
    265 }
    266 
    267 static void
    268 usage(void)
    269 {
    270 	eprintf("usage: %s EXPRESSION\n", argv0);
    271 }
    272 
    273 int
    274 main(int argc, char *argv[])
    275 {
    276 	intmax_t n = INTMAX_MIN;
    277 
    278 	/* Get the maximum number of digits (+ sign) */
    279 	for (intlen = (n < 0); n; n /= 10, ++intlen);
    280 
    281 	ARGBEGIN {
    282 	default:
    283 		usage();
    284 	} ARGEND;
    285 
    286 	return !parse(argv, argc);
    287 }