14Srgrimes%{ 2139969Simp/*- 3223883Sse * Written by Pace Willisson (pace@blitz.com) 4295Sjtc * and placed in the public domain. 54Srgrimes * 6295Sjtc * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 7295Sjtc * 850471Speter * $FreeBSD$ 94Srgrimes */ 10468Sjtc 1162926Sse#include <sys/types.h> 1292979Swollman 1392979Swollman#include <ctype.h> 1492979Swollman#include <err.h> 1592979Swollman#include <errno.h> 1692979Swollman#include <inttypes.h> 1792979Swollman#include <limits.h> 1892979Swollman#include <locale.h> 194Srgrimes#include <stdio.h> 204Srgrimes#include <stdlib.h> 214Srgrimes#include <string.h> 2262926Sse#include <regex.h> 2392979Swollman#include <unistd.h> 24223883Sse 2592979Swollman/* 2692979Swollman * POSIX specifies a specific error code for syntax errors. We exit 2792979Swollman * with this code for all errors. 2892979Swollman */ 2992979Swollman#define ERR_EXIT 2 3092979Swollman 314Srgrimesenum valtype { 3212378Sjoerg integer, numeric_string, string 334Srgrimes} ; 3431Salm 354Srgrimesstruct val { 364Srgrimes enum valtype type; 374Srgrimes union { 384Srgrimes char *s; 3992979Swollman intmax_t i; 404Srgrimes } u; 4131Salm} ; 424Srgrimes 43223882Ssechar **av; 44223882Sseint nonposix; 45223883Ssestruct val *result; 464Srgrimes 47223881Ssevoid assert_to_integer(struct val *); 48223882Ssevoid assert_div(intmax_t, intmax_t); 49223882Ssevoid assert_minus(intmax_t, intmax_t, intmax_t); 50223882Ssevoid assert_plus(intmax_t, intmax_t, intmax_t); 51223882Ssevoid assert_times(intmax_t, intmax_t, intmax_t); 52223882Sseint compare_vals(struct val *, struct val *); 5390109Simpvoid free_value(struct val *); 54223881Sseint is_integer(const char *); 55223883Sseint is_string(struct val *); 5690109Simpint is_zero_or_null(struct val *); 5792979Swollmanstruct val *make_integer(intmax_t); 5890109Simpstruct val *make_str(const char *); 5990109Simpstruct val *op_and(struct val *, struct val *); 6090109Simpstruct val *op_colon(struct val *, struct val *); 6190109Simpstruct val *op_div(struct val *, struct val *); 6290109Simpstruct val *op_eq(struct val *, struct val *); 6390109Simpstruct val *op_ge(struct val *, struct val *); 6490109Simpstruct val *op_gt(struct val *, struct val *); 6590109Simpstruct val *op_le(struct val *, struct val *); 6690109Simpstruct val *op_lt(struct val *, struct val *); 6790109Simpstruct val *op_minus(struct val *, struct val *); 6890109Simpstruct val *op_ne(struct val *, struct val *); 6990109Simpstruct val *op_or(struct val *, struct val *); 7090109Simpstruct val *op_plus(struct val *, struct val *); 7190109Simpstruct val *op_rem(struct val *, struct val *); 7290109Simpstruct val *op_times(struct val *, struct val *); 73223881Sseint to_integer(struct val *); 7490109Simpvoid to_string(struct val *); 7590109Simpint yyerror(const char *); 7690109Simpint yylex(void); 77244117Sglebiusint yyparse(void); 7877244Skris 794Srgrimes%} 804Srgrimes 814Srgrimes%union 824Srgrimes{ 834Srgrimes struct val *val; 844Srgrimes} 854Srgrimes 864Srgrimes%left <val> '|' 874Srgrimes%left <val> '&' 884Srgrimes%left <val> '=' '>' '<' GE LE NE 894Srgrimes%left <val> '+' '-' 904Srgrimes%left <val> '*' '/' '%' 914Srgrimes%left <val> ':' 924Srgrimes 934Srgrimes%token <val> TOKEN 944Srgrimes%type <val> start expr 954Srgrimes 964Srgrimes%% 974Srgrimes 984Srgrimesstart: expr { result = $$; } 994Srgrimes 1004Srgrimesexpr: TOKEN 1014Srgrimes | '(' expr ')' { $$ = $2; } 102223883Sse | expr '|' expr { $$ = op_or($1, $3); } 103223883Sse | expr '&' expr { $$ = op_and($1, $3); } 104223883Sse | expr '=' expr { $$ = op_eq($1, $3); } 105223883Sse | expr '>' expr { $$ = op_gt($1, $3); } 106223883Sse | expr '<' expr { $$ = op_lt($1, $3); } 107223883Sse | expr GE expr { $$ = op_ge($1, $3); } 108223883Sse | expr LE expr { $$ = op_le($1, $3); } 109223883Sse | expr NE expr { $$ = op_ne($1, $3); } 110223883Sse | expr '+' expr { $$ = op_plus($1, $3); } 111223883Sse | expr '-' expr { $$ = op_minus($1, $3); } 112223883Sse | expr '*' expr { $$ = op_times($1, $3); } 113223883Sse | expr '/' expr { $$ = op_div($1, $3); } 114223883Sse | expr '%' expr { $$ = op_rem($1, $3); } 115223883Sse | expr ':' expr { $$ = op_colon($1, $3); } 1164Srgrimes ; 1174Srgrimes 1184Srgrimes%% 1194Srgrimes 1204Srgrimesstruct val * 12192979Swollmanmake_integer(intmax_t i) 1224Srgrimes{ 1234Srgrimes struct val *vp; 1244Srgrimes 125223883Sse vp = (struct val *)malloc(sizeof(*vp)); 126223883Sse if (vp == NULL) 12792979Swollman errx(ERR_EXIT, "malloc() failed"); 1284Srgrimes 1294Srgrimes vp->type = integer; 1304Srgrimes vp->u.i = i; 131223883Sse return (vp); 1324Srgrimes} 1334Srgrimes 1344Srgrimesstruct val * 13590109Simpmake_str(const char *s) 1364Srgrimes{ 1374Srgrimes struct val *vp; 1384Srgrimes 139223883Sse vp = (struct val *)malloc(sizeof(*vp)); 140223883Sse if (vp == NULL || ((vp->u.s = strdup(s)) == NULL)) 14192979Swollman errx(ERR_EXIT, "malloc() failed"); 1424Srgrimes 143223881Sse if (is_integer(s)) 144223881Sse vp->type = numeric_string; 14596367Swollman else 14692979Swollman vp->type = string; 1479909Sjoerg 148223883Sse return (vp); 1494Srgrimes} 1504Srgrimes 1514Srgrimesvoid 15290109Simpfree_value(struct val *vp) 1534Srgrimes{ 15412378Sjoerg if (vp->type == string || vp->type == numeric_string) 155223883Sse free(vp->u.s); 1564Srgrimes} 1574Srgrimes 158223881Sseint 15990109Simpto_integer(struct val *vp) 1604Srgrimes{ 16192979Swollman intmax_t i; 1624Srgrimes 163223881Sse /* we can only convert numeric_string to integer, here */ 164223881Sse if (vp->type == numeric_string) { 165223881Sse errno = 0; 16696367Swollman i = strtoimax(vp->u.s, (char **)NULL, 10); 167223881Sse /* just keep as numeric_string, if the conversion fails */ 168223881Sse if (errno != ERANGE) { 169223883Sse free(vp->u.s); 170223881Sse vp->u.i = i; 171223881Sse vp->type = integer; 172223881Sse } 17396367Swollman } 174223881Sse return (vp->type == integer); 175223881Sse} 17692979Swollman 177223881Ssevoid 178223881Sseassert_to_integer(struct val *vp) 179223881Sse{ 180223881Sse if (vp->type == string) 181223881Sse errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s); 182223881Sse if (!to_integer(vp)) 183223881Sse errx(ERR_EXIT, "operand too large: '%s'", vp->u.s); 1844Srgrimes} 1854Srgrimes 1864Srgrimesvoid 18790109Simpto_string(struct val *vp) 1884Srgrimes{ 1894Srgrimes char *tmp; 1904Srgrimes 19112378Sjoerg if (vp->type == string || vp->type == numeric_string) 1924Srgrimes return; 1934Srgrimes 19492979Swollman /* 19592979Swollman * log_10(x) ~= 0.3 * log_2(x). Rounding up gives the number 19692979Swollman * of digits; add one each for the sign and terminating null 19792979Swollman * character, respectively. 19892979Swollman */ 19992979Swollman#define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1) 20092979Swollman tmp = malloc(NDIGITS(vp->u.i)); 20192979Swollman if (tmp == NULL) 20292979Swollman errx(ERR_EXIT, "malloc() failed"); 2034Srgrimes 20492979Swollman sprintf(tmp, "%jd", vp->u.i); 2054Srgrimes vp->type = string; 2064Srgrimes vp->u.s = tmp; 2074Srgrimes} 2084Srgrimes 2094Srgrimesint 210223881Sseis_integer(const char *s) 211223881Sse{ 212223881Sse if (nonposix) { 213223881Sse if (*s == '\0') 214223881Sse return (1); 215223881Sse while (isspace((unsigned char)*s)) 216223881Sse s++; 217223881Sse } 218223881Sse if (*s == '-' || (nonposix && *s == '+')) 219223881Sse s++; 220223881Sse if (*s == '\0') 221223881Sse return (0); 222223881Sse while (isdigit((unsigned char)*s)) 223223881Sse s++; 224223881Sse return (*s == '\0'); 225223881Sse} 226223881Sse 227223881Sseint 228223883Sseis_string(struct val *vp) 2294Srgrimes{ 23012378Sjoerg /* only TRUE if this string is not a valid integer */ 2314Srgrimes return (vp->type == string); 2324Srgrimes} 2334Srgrimes 2344Srgrimesint 23590109Simpyylex(void) 2364Srgrimes{ 2374Srgrimes char *p; 2384Srgrimes 2394Srgrimes if (*av == NULL) 2404Srgrimes return (0); 2414Srgrimes 2424Srgrimes p = *av++; 2434Srgrimes 244223883Sse if (strlen(p) == 1) { 245223883Sse if (strchr("|&=<>+-*/%:()", *p)) 2464Srgrimes return (*p); 247223883Sse } else if (strlen(p) == 2 && p[1] == '=') { 2484Srgrimes switch (*p) { 2494Srgrimes case '>': return (GE); 2504Srgrimes case '<': return (LE); 2514Srgrimes case '!': return (NE); 2524Srgrimes } 2534Srgrimes } 2544Srgrimes 255223883Sse yylval.val = make_str(p); 2564Srgrimes return (TOKEN); 2574Srgrimes} 2584Srgrimes 2594Srgrimesint 26090109Simpis_zero_or_null(struct val *vp) 2614Srgrimes{ 262223883Sse if (vp->type == integer) 2634Srgrimes return (vp->u.i == 0); 264223883Sse 265223883Sse return (*vp->u.s == 0 || (to_integer(vp) && vp->u.i == 0)); 2664Srgrimes} 2674Srgrimes 26812378Sjoergint 26992979Swollmanmain(int argc, char *argv[]) 2704Srgrimes{ 27192979Swollman int c; 27292979Swollman 273223883Sse setlocale(LC_ALL, ""); 274106065Swollman if (getenv("EXPR_COMPAT") != NULL 275106065Swollman || check_utility_compat("expr")) { 27695278Swollman av = argv + 1; 277223881Sse nonposix = 1; 27895278Swollman } else { 279223883Sse while ((c = getopt(argc, argv, "e")) != -1) { 28095278Swollman switch (c) { 28196367Swollman case 'e': 282223881Sse nonposix = 1; 28396367Swollman break; 28495278Swollman default: 285223883Sse errx(ERR_EXIT, 28696367Swollman "usage: expr [-e] expression\n"); 28795278Swollman } 288223883Sse } 28995278Swollman av = argv + optind; 29095278Swollman } 291468Sjtc 29292979Swollman yyparse(); 2934Srgrimes 2944Srgrimes if (result->type == integer) 29592979Swollman printf("%jd\n", result->u.i); 2964Srgrimes else 29792979Swollman printf("%s\n", result->u.s); 2984Srgrimes 29992979Swollman return (is_zero_or_null(result)); 3004Srgrimes} 3014Srgrimes 3024Srgrimesint 30390109Simpyyerror(const char *s __unused) 3044Srgrimes{ 30592979Swollman errx(ERR_EXIT, "syntax error"); 3064Srgrimes} 3074Srgrimes 3084Srgrimesstruct val * 30990109Simpop_or(struct val *a, struct val *b) 3104Srgrimes{ 311223881Sse if (!is_zero_or_null(a)) { 312223881Sse free_value(b); 3134Srgrimes return (a); 3144Srgrimes } 315223881Sse free_value(a); 316223881Sse if (!is_zero_or_null(b)) 317223881Sse return (b); 318223881Sse free_value(b); 319223881Sse return (make_integer((intmax_t)0)); 3204Srgrimes} 321223881Sse 3224Srgrimesstruct val * 32390109Simpop_and(struct val *a, struct val *b) 3244Srgrimes{ 325223883Sse if (is_zero_or_null(a) || is_zero_or_null(b)) { 326223883Sse free_value(a); 327223883Sse free_value(b); 328223883Sse return (make_integer((intmax_t)0)); 3294Srgrimes } else { 330223883Sse free_value(b); 3314Srgrimes return (a); 3324Srgrimes } 3334Srgrimes} 3344Srgrimes 335223882Sseint 336223882Ssecompare_vals(struct val *a, struct val *b) 3374Srgrimes{ 338223882Sse int r; 3394Srgrimes 340223883Sse if (is_string(a) || is_string(b)) { 341223882Sse to_string(a); 342223882Sse to_string(b); 343223882Sse r = strcoll(a->u.s, b->u.s); 3444Srgrimes } else { 345223881Sse assert_to_integer(a); 346223881Sse assert_to_integer(b); 347223882Sse if (a->u.i > b->u.i) 348223882Sse r = 1; 349223882Sse else if (a->u.i < b->u.i) 350223882Sse r = -1; 351223882Sse else 352223882Sse r = 0; 3534Srgrimes } 3544Srgrimes 355223882Sse free_value(a); 356223882Sse free_value(b); 357223882Sse return (r); 3584Srgrimes} 3594Srgrimes 3604Srgrimesstruct val * 361223882Sseop_eq(struct val *a, struct val *b) 362223882Sse{ 363223882Sse return (make_integer((intmax_t)(compare_vals(a, b) == 0))); 364223882Sse} 365223882Sse 366223882Ssestruct val * 36790109Simpop_gt(struct val *a, struct val *b) 3684Srgrimes{ 369223882Sse return (make_integer((intmax_t)(compare_vals(a, b) > 0))); 3704Srgrimes} 3714Srgrimes 3724Srgrimesstruct val * 37390109Simpop_lt(struct val *a, struct val *b) 3744Srgrimes{ 375223882Sse return (make_integer((intmax_t)(compare_vals(a, b) < 0))); 3764Srgrimes} 3774Srgrimes 3784Srgrimesstruct val * 37990109Simpop_ge(struct val *a, struct val *b) 3804Srgrimes{ 381223882Sse return (make_integer((intmax_t)(compare_vals(a, b) >= 0))); 3824Srgrimes} 3834Srgrimes 3844Srgrimesstruct val * 38590109Simpop_le(struct val *a, struct val *b) 3864Srgrimes{ 387223882Sse return (make_integer((intmax_t)(compare_vals(a, b) <= 0))); 3884Srgrimes} 3894Srgrimes 3904Srgrimesstruct val * 39190109Simpop_ne(struct val *a, struct val *b) 3924Srgrimes{ 393223882Sse return (make_integer((intmax_t)(compare_vals(a, b) != 0))); 3944Srgrimes} 3954Srgrimes 396223882Ssevoid 397223882Sseassert_plus(intmax_t a, intmax_t b, intmax_t r) 39863755Sse{ 399223882Sse /* 400223882Sse * sum of two positive numbers must be positive, 401223882Sse * sum of two negative numbers must be negative 402223882Sse */ 403223882Sse if ((a > 0 && b > 0 && r <= 0) || 404223882Sse (a < 0 && b < 0 && r >= 0)) 405223882Sse errx(ERR_EXIT, "overflow"); 40663755Sse} 40763755Sse 4084Srgrimesstruct val * 40990109Simpop_plus(struct val *a, struct val *b) 4104Srgrimes{ 4114Srgrimes struct val *r; 4124Srgrimes 413223881Sse assert_to_integer(a); 414223881Sse assert_to_integer(b); 415223881Sse r = make_integer(a->u.i + b->u.i); 416223882Sse assert_plus(a->u.i, b->u.i, r->u.i); 4174Srgrimes 418223883Sse free_value(a); 419223883Sse free_value(b); 420223883Sse return (r); 4214Srgrimes} 42263755Sse 423223882Ssevoid 424223882Sseassert_minus(intmax_t a, intmax_t b, intmax_t r) 42563755Sse{ 42692979Swollman /* special case subtraction of INTMAX_MIN */ 427223882Sse if (b == INTMAX_MIN && a < 0) 428223882Sse errx(ERR_EXIT, "overflow"); 429223882Sse /* check addition of negative subtrahend */ 430223882Sse assert_plus(a, -b, r); 43163755Sse} 43263755Sse 4334Srgrimesstruct val * 43490109Simpop_minus(struct val *a, struct val *b) 4354Srgrimes{ 4364Srgrimes struct val *r; 4374Srgrimes 438223881Sse assert_to_integer(a); 439223881Sse assert_to_integer(b); 440223881Sse r = make_integer(a->u.i - b->u.i); 441223882Sse assert_minus(a->u.i, b->u.i, r->u.i); 4424Srgrimes 443223883Sse free_value(a); 444223883Sse free_value(b); 445223883Sse return (r); 4464Srgrimes} 44763755Sse 448223882Ssevoid 449223882Sseassert_times(intmax_t a, intmax_t b, intmax_t r) 45063755Sse{ 451223882Sse /* 452223882Sse * if first operand is 0, no overflow is possible, 453223882Sse * else result of division test must match second operand 454223882Sse */ 455223882Sse if (a != 0 && r / a != b) 456223882Sse errx(ERR_EXIT, "overflow"); 45763755Sse} 45863755Sse 4594Srgrimesstruct val * 46090109Simpop_times(struct val *a, struct val *b) 4614Srgrimes{ 4624Srgrimes struct val *r; 4634Srgrimes 464223881Sse assert_to_integer(a); 465223881Sse assert_to_integer(b); 466223881Sse r = make_integer(a->u.i * b->u.i); 467223882Sse assert_times(a->u.i, b->u.i, r->u.i); 4684Srgrimes 469223883Sse free_value(a); 470223883Sse free_value(b); 4714Srgrimes return (r); 4724Srgrimes} 47363755Sse 474223882Ssevoid 475223882Sseassert_div(intmax_t a, intmax_t b) 47663755Sse{ 477223882Sse if (b == 0) 478223882Sse errx(ERR_EXIT, "division by zero"); 47992979Swollman /* only INTMAX_MIN / -1 causes overflow */ 48092979Swollman if (a == INTMAX_MIN && b == -1) 481223882Sse errx(ERR_EXIT, "overflow"); 48263755Sse} 48363755Sse 4844Srgrimesstruct val * 48590109Simpop_div(struct val *a, struct val *b) 4864Srgrimes{ 4874Srgrimes struct val *r; 4884Srgrimes 489223881Sse assert_to_integer(a); 490223881Sse assert_to_integer(b); 491223882Sse /* assert based on operands only, not on result */ 492223882Sse assert_div(a->u.i, b->u.i); 493223881Sse r = make_integer(a->u.i / b->u.i); 4944Srgrimes 495223883Sse free_value(a); 496223883Sse free_value(b); 497223883Sse return (r); 4984Srgrimes} 499223883Sse 5004Srgrimesstruct val * 50190109Simpop_rem(struct val *a, struct val *b) 5024Srgrimes{ 5034Srgrimes struct val *r; 5044Srgrimes 505223881Sse assert_to_integer(a); 506223881Sse assert_to_integer(b); 507223882Sse /* pass a=1 to only check for div by zero */ 508223882Sse assert_div(1, b->u.i); 509223881Sse r = make_integer(a->u.i % b->u.i); 5104Srgrimes 511223883Sse free_value(a); 512223883Sse free_value(b); 513223883Sse return (r); 5144Srgrimes} 515223883Sse 5164Srgrimesstruct val * 51790109Simpop_colon(struct val *a, struct val *b) 5184Srgrimes{ 51931Salm regex_t rp; 520468Sjtc regmatch_t rm[2]; 52131Salm char errbuf[256]; 52231Salm int eval; 523181Sconklin struct val *v; 5244Srgrimes 525166813Sceri /* coerce both arguments to strings */ 526181Sconklin to_string(a); 527181Sconklin to_string(b); 528181Sconklin 52931Salm /* compile regular expression */ 530223883Sse if ((eval = regcomp(&rp, b->u.s, 0)) != 0) { 531223883Sse regerror(eval, &rp, errbuf, sizeof(errbuf)); 53292979Swollman errx(ERR_EXIT, "%s", errbuf); 5334Srgrimes } 5344Srgrimes 53531Salm /* compare string against pattern */ 536539Sjtc /* remember that patterns are anchored to the beginning of the line */ 537223883Sse if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) 53831Salm if (rm[1].rm_so >= 0) { 539295Sjtc *(a->u.s + rm[1].rm_eo) = '\0'; 540223883Sse v = make_str(a->u.s + rm[1].rm_so); 54131Salm 542223883Sse } else 543223883Sse v = make_integer((intmax_t)(rm[0].rm_eo - rm[0].rm_so)); 544223883Sse else 545223883Sse if (rp.re_nsub == 0) 546223883Sse v = make_integer((intmax_t)0); 547223883Sse else 548223883Sse v = make_str(""); 5494Srgrimes 55031Salm /* free arguments and pattern buffer */ 551223883Sse free_value(a); 552223883Sse free_value(b); 553223883Sse regfree(&rp); 55431Salm 555223883Sse return (v); 5564Srgrimes} 557