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); 7777244Skris 784Srgrimes%} 794Srgrimes 804Srgrimes%union 814Srgrimes{ 824Srgrimes struct val *val; 834Srgrimes} 844Srgrimes 854Srgrimes%left <val> '|' 864Srgrimes%left <val> '&' 874Srgrimes%left <val> '=' '>' '<' GE LE NE 884Srgrimes%left <val> '+' '-' 894Srgrimes%left <val> '*' '/' '%' 904Srgrimes%left <val> ':' 914Srgrimes 924Srgrimes%token <val> TOKEN 934Srgrimes%type <val> start expr 944Srgrimes 954Srgrimes%% 964Srgrimes 974Srgrimesstart: expr { result = $$; } 984Srgrimes 994Srgrimesexpr: TOKEN 1004Srgrimes | '(' expr ')' { $$ = $2; } 101223883Sse | expr '|' expr { $$ = op_or($1, $3); } 102223883Sse | expr '&' expr { $$ = op_and($1, $3); } 103223883Sse | expr '=' expr { $$ = op_eq($1, $3); } 104223883Sse | expr '>' expr { $$ = op_gt($1, $3); } 105223883Sse | expr '<' expr { $$ = op_lt($1, $3); } 106223883Sse | expr GE expr { $$ = op_ge($1, $3); } 107223883Sse | expr LE expr { $$ = op_le($1, $3); } 108223883Sse | expr NE expr { $$ = op_ne($1, $3); } 109223883Sse | expr '+' expr { $$ = op_plus($1, $3); } 110223883Sse | expr '-' expr { $$ = op_minus($1, $3); } 111223883Sse | expr '*' expr { $$ = op_times($1, $3); } 112223883Sse | expr '/' expr { $$ = op_div($1, $3); } 113223883Sse | expr '%' expr { $$ = op_rem($1, $3); } 114223883Sse | expr ':' expr { $$ = op_colon($1, $3); } 1154Srgrimes ; 1164Srgrimes 1174Srgrimes%% 1184Srgrimes 1194Srgrimesstruct val * 12092979Swollmanmake_integer(intmax_t i) 1214Srgrimes{ 1224Srgrimes struct val *vp; 1234Srgrimes 124223883Sse vp = (struct val *)malloc(sizeof(*vp)); 125223883Sse if (vp == NULL) 12692979Swollman errx(ERR_EXIT, "malloc() failed"); 1274Srgrimes 1284Srgrimes vp->type = integer; 1294Srgrimes vp->u.i = i; 130223883Sse return (vp); 1314Srgrimes} 1324Srgrimes 1334Srgrimesstruct val * 13490109Simpmake_str(const char *s) 1354Srgrimes{ 1364Srgrimes struct val *vp; 1374Srgrimes 138223883Sse vp = (struct val *)malloc(sizeof(*vp)); 139223883Sse if (vp == NULL || ((vp->u.s = strdup(s)) == NULL)) 14092979Swollman errx(ERR_EXIT, "malloc() failed"); 1414Srgrimes 142223881Sse if (is_integer(s)) 143223881Sse vp->type = numeric_string; 14496367Swollman else 14592979Swollman vp->type = string; 1469909Sjoerg 147223883Sse return (vp); 1484Srgrimes} 1494Srgrimes 1504Srgrimesvoid 15190109Simpfree_value(struct val *vp) 1524Srgrimes{ 15312378Sjoerg if (vp->type == string || vp->type == numeric_string) 154223883Sse free(vp->u.s); 1554Srgrimes} 1564Srgrimes 157223881Sseint 15890109Simpto_integer(struct val *vp) 1594Srgrimes{ 16092979Swollman intmax_t i; 1614Srgrimes 162223881Sse /* we can only convert numeric_string to integer, here */ 163223881Sse if (vp->type == numeric_string) { 164223881Sse errno = 0; 16596367Swollman i = strtoimax(vp->u.s, (char **)NULL, 10); 166223881Sse /* just keep as numeric_string, if the conversion fails */ 167223881Sse if (errno != ERANGE) { 168223883Sse free(vp->u.s); 169223881Sse vp->u.i = i; 170223881Sse vp->type = integer; 171223881Sse } 17296367Swollman } 173223881Sse return (vp->type == integer); 174223881Sse} 17592979Swollman 176223881Ssevoid 177223881Sseassert_to_integer(struct val *vp) 178223881Sse{ 179223881Sse if (vp->type == string) 180223881Sse errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s); 181223881Sse if (!to_integer(vp)) 182223881Sse errx(ERR_EXIT, "operand too large: '%s'", vp->u.s); 1834Srgrimes} 1844Srgrimes 1854Srgrimesvoid 18690109Simpto_string(struct val *vp) 1874Srgrimes{ 1884Srgrimes char *tmp; 1894Srgrimes 19012378Sjoerg if (vp->type == string || vp->type == numeric_string) 1914Srgrimes return; 1924Srgrimes 19392979Swollman /* 19492979Swollman * log_10(x) ~= 0.3 * log_2(x). Rounding up gives the number 19592979Swollman * of digits; add one each for the sign and terminating null 19692979Swollman * character, respectively. 19792979Swollman */ 19892979Swollman#define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1) 19992979Swollman tmp = malloc(NDIGITS(vp->u.i)); 20092979Swollman if (tmp == NULL) 20192979Swollman errx(ERR_EXIT, "malloc() failed"); 2024Srgrimes 20392979Swollman sprintf(tmp, "%jd", vp->u.i); 2044Srgrimes vp->type = string; 2054Srgrimes vp->u.s = tmp; 2064Srgrimes} 2074Srgrimes 2084Srgrimesint 209223881Sseis_integer(const char *s) 210223881Sse{ 211223881Sse if (nonposix) { 212223881Sse if (*s == '\0') 213223881Sse return (1); 214223881Sse while (isspace((unsigned char)*s)) 215223881Sse s++; 216223881Sse } 217223881Sse if (*s == '-' || (nonposix && *s == '+')) 218223881Sse s++; 219223881Sse if (*s == '\0') 220223881Sse return (0); 221223881Sse while (isdigit((unsigned char)*s)) 222223881Sse s++; 223223881Sse return (*s == '\0'); 224223881Sse} 225223881Sse 226223881Sseint 227223883Sseis_string(struct val *vp) 2284Srgrimes{ 22912378Sjoerg /* only TRUE if this string is not a valid integer */ 2304Srgrimes return (vp->type == string); 2314Srgrimes} 2324Srgrimes 2334Srgrimesint 23490109Simpyylex(void) 2354Srgrimes{ 2364Srgrimes char *p; 2374Srgrimes 2384Srgrimes if (*av == NULL) 2394Srgrimes return (0); 2404Srgrimes 2414Srgrimes p = *av++; 2424Srgrimes 243223883Sse if (strlen(p) == 1) { 244223883Sse if (strchr("|&=<>+-*/%:()", *p)) 2454Srgrimes return (*p); 246223883Sse } else if (strlen(p) == 2 && p[1] == '=') { 2474Srgrimes switch (*p) { 2484Srgrimes case '>': return (GE); 2494Srgrimes case '<': return (LE); 2504Srgrimes case '!': return (NE); 2514Srgrimes } 2524Srgrimes } 2534Srgrimes 254223883Sse yylval.val = make_str(p); 2554Srgrimes return (TOKEN); 2564Srgrimes} 2574Srgrimes 2584Srgrimesint 25990109Simpis_zero_or_null(struct val *vp) 2604Srgrimes{ 261223883Sse if (vp->type == integer) 2624Srgrimes return (vp->u.i == 0); 263223883Sse 264223883Sse return (*vp->u.s == 0 || (to_integer(vp) && vp->u.i == 0)); 2654Srgrimes} 2664Srgrimes 26712378Sjoergint 26892979Swollmanmain(int argc, char *argv[]) 2694Srgrimes{ 27092979Swollman int c; 27192979Swollman 272223883Sse setlocale(LC_ALL, ""); 273106065Swollman if (getenv("EXPR_COMPAT") != NULL 274106065Swollman || check_utility_compat("expr")) { 27595278Swollman av = argv + 1; 276223881Sse nonposix = 1; 27795278Swollman } else { 278223883Sse while ((c = getopt(argc, argv, "e")) != -1) { 27995278Swollman switch (c) { 28096367Swollman case 'e': 281223881Sse nonposix = 1; 28296367Swollman break; 28395278Swollman default: 284223883Sse errx(ERR_EXIT, 28596367Swollman "usage: expr [-e] expression\n"); 28695278Swollman } 287223883Sse } 28895278Swollman av = argv + optind; 28995278Swollman } 290468Sjtc 29192979Swollman yyparse(); 2924Srgrimes 2934Srgrimes if (result->type == integer) 29492979Swollman printf("%jd\n", result->u.i); 2954Srgrimes else 29692979Swollman printf("%s\n", result->u.s); 2974Srgrimes 29892979Swollman return (is_zero_or_null(result)); 2994Srgrimes} 3004Srgrimes 3014Srgrimesint 30290109Simpyyerror(const char *s __unused) 3034Srgrimes{ 30492979Swollman errx(ERR_EXIT, "syntax error"); 3054Srgrimes} 3064Srgrimes 3074Srgrimesstruct val * 30890109Simpop_or(struct val *a, struct val *b) 3094Srgrimes{ 310223881Sse if (!is_zero_or_null(a)) { 311223881Sse free_value(b); 3124Srgrimes return (a); 3134Srgrimes } 314223881Sse free_value(a); 315223881Sse if (!is_zero_or_null(b)) 316223881Sse return (b); 317223881Sse free_value(b); 318223881Sse return (make_integer((intmax_t)0)); 3194Srgrimes} 320223881Sse 3214Srgrimesstruct val * 32290109Simpop_and(struct val *a, struct val *b) 3234Srgrimes{ 324223883Sse if (is_zero_or_null(a) || is_zero_or_null(b)) { 325223883Sse free_value(a); 326223883Sse free_value(b); 327223883Sse return (make_integer((intmax_t)0)); 3284Srgrimes } else { 329223883Sse free_value(b); 3304Srgrimes return (a); 3314Srgrimes } 3324Srgrimes} 3334Srgrimes 334223882Sseint 335223882Ssecompare_vals(struct val *a, struct val *b) 3364Srgrimes{ 337223882Sse int r; 3384Srgrimes 339223883Sse if (is_string(a) || is_string(b)) { 340223882Sse to_string(a); 341223882Sse to_string(b); 342223882Sse r = strcoll(a->u.s, b->u.s); 3434Srgrimes } else { 344223881Sse assert_to_integer(a); 345223881Sse assert_to_integer(b); 346223882Sse if (a->u.i > b->u.i) 347223882Sse r = 1; 348223882Sse else if (a->u.i < b->u.i) 349223882Sse r = -1; 350223882Sse else 351223882Sse r = 0; 3524Srgrimes } 3534Srgrimes 354223882Sse free_value(a); 355223882Sse free_value(b); 356223882Sse return (r); 3574Srgrimes} 3584Srgrimes 3594Srgrimesstruct val * 360223882Sseop_eq(struct val *a, struct val *b) 361223882Sse{ 362223882Sse return (make_integer((intmax_t)(compare_vals(a, b) == 0))); 363223882Sse} 364223882Sse 365223882Ssestruct val * 36690109Simpop_gt(struct val *a, struct val *b) 3674Srgrimes{ 368223882Sse return (make_integer((intmax_t)(compare_vals(a, b) > 0))); 3694Srgrimes} 3704Srgrimes 3714Srgrimesstruct val * 37290109Simpop_lt(struct val *a, struct val *b) 3734Srgrimes{ 374223882Sse return (make_integer((intmax_t)(compare_vals(a, b) < 0))); 3754Srgrimes} 3764Srgrimes 3774Srgrimesstruct val * 37890109Simpop_ge(struct val *a, struct val *b) 3794Srgrimes{ 380223882Sse return (make_integer((intmax_t)(compare_vals(a, b) >= 0))); 3814Srgrimes} 3824Srgrimes 3834Srgrimesstruct val * 38490109Simpop_le(struct val *a, struct val *b) 3854Srgrimes{ 386223882Sse return (make_integer((intmax_t)(compare_vals(a, b) <= 0))); 3874Srgrimes} 3884Srgrimes 3894Srgrimesstruct val * 39090109Simpop_ne(struct val *a, struct val *b) 3914Srgrimes{ 392223882Sse return (make_integer((intmax_t)(compare_vals(a, b) != 0))); 3934Srgrimes} 3944Srgrimes 395223882Ssevoid 396223882Sseassert_plus(intmax_t a, intmax_t b, intmax_t r) 39763755Sse{ 398223882Sse /* 399223882Sse * sum of two positive numbers must be positive, 400223882Sse * sum of two negative numbers must be negative 401223882Sse */ 402223882Sse if ((a > 0 && b > 0 && r <= 0) || 403223882Sse (a < 0 && b < 0 && r >= 0)) 404223882Sse errx(ERR_EXIT, "overflow"); 40563755Sse} 40663755Sse 4074Srgrimesstruct val * 40890109Simpop_plus(struct val *a, struct val *b) 4094Srgrimes{ 4104Srgrimes struct val *r; 4114Srgrimes 412223881Sse assert_to_integer(a); 413223881Sse assert_to_integer(b); 414223881Sse r = make_integer(a->u.i + b->u.i); 415223882Sse assert_plus(a->u.i, b->u.i, r->u.i); 4164Srgrimes 417223883Sse free_value(a); 418223883Sse free_value(b); 419223883Sse return (r); 4204Srgrimes} 42163755Sse 422223882Ssevoid 423223882Sseassert_minus(intmax_t a, intmax_t b, intmax_t r) 42463755Sse{ 42592979Swollman /* special case subtraction of INTMAX_MIN */ 426223882Sse if (b == INTMAX_MIN && a < 0) 427223882Sse errx(ERR_EXIT, "overflow"); 428223882Sse /* check addition of negative subtrahend */ 429223882Sse assert_plus(a, -b, r); 43063755Sse} 43163755Sse 4324Srgrimesstruct val * 43390109Simpop_minus(struct val *a, struct val *b) 4344Srgrimes{ 4354Srgrimes struct val *r; 4364Srgrimes 437223881Sse assert_to_integer(a); 438223881Sse assert_to_integer(b); 439223881Sse r = make_integer(a->u.i - b->u.i); 440223882Sse assert_minus(a->u.i, b->u.i, r->u.i); 4414Srgrimes 442223883Sse free_value(a); 443223883Sse free_value(b); 444223883Sse return (r); 4454Srgrimes} 44663755Sse 447223882Ssevoid 448223882Sseassert_times(intmax_t a, intmax_t b, intmax_t r) 44963755Sse{ 450223882Sse /* 451223882Sse * if first operand is 0, no overflow is possible, 452223882Sse * else result of division test must match second operand 453223882Sse */ 454223882Sse if (a != 0 && r / a != b) 455223882Sse errx(ERR_EXIT, "overflow"); 45663755Sse} 45763755Sse 4584Srgrimesstruct val * 45990109Simpop_times(struct val *a, struct val *b) 4604Srgrimes{ 4614Srgrimes struct val *r; 4624Srgrimes 463223881Sse assert_to_integer(a); 464223881Sse assert_to_integer(b); 465223881Sse r = make_integer(a->u.i * b->u.i); 466223882Sse assert_times(a->u.i, b->u.i, r->u.i); 4674Srgrimes 468223883Sse free_value(a); 469223883Sse free_value(b); 4704Srgrimes return (r); 4714Srgrimes} 47263755Sse 473223882Ssevoid 474223882Sseassert_div(intmax_t a, intmax_t b) 47563755Sse{ 476223882Sse if (b == 0) 477223882Sse errx(ERR_EXIT, "division by zero"); 47892979Swollman /* only INTMAX_MIN / -1 causes overflow */ 47992979Swollman if (a == INTMAX_MIN && b == -1) 480223882Sse errx(ERR_EXIT, "overflow"); 48163755Sse} 48263755Sse 4834Srgrimesstruct val * 48490109Simpop_div(struct val *a, struct val *b) 4854Srgrimes{ 4864Srgrimes struct val *r; 4874Srgrimes 488223881Sse assert_to_integer(a); 489223881Sse assert_to_integer(b); 490223882Sse /* assert based on operands only, not on result */ 491223882Sse assert_div(a->u.i, b->u.i); 492223881Sse r = make_integer(a->u.i / b->u.i); 4934Srgrimes 494223883Sse free_value(a); 495223883Sse free_value(b); 496223883Sse return (r); 4974Srgrimes} 498223883Sse 4994Srgrimesstruct val * 50090109Simpop_rem(struct val *a, struct val *b) 5014Srgrimes{ 5024Srgrimes struct val *r; 5034Srgrimes 504223881Sse assert_to_integer(a); 505223881Sse assert_to_integer(b); 506223882Sse /* pass a=1 to only check for div by zero */ 507223882Sse assert_div(1, b->u.i); 508223881Sse r = make_integer(a->u.i % b->u.i); 5094Srgrimes 510223883Sse free_value(a); 511223883Sse free_value(b); 512223883Sse return (r); 5134Srgrimes} 514223883Sse 5154Srgrimesstruct val * 51690109Simpop_colon(struct val *a, struct val *b) 5174Srgrimes{ 51831Salm regex_t rp; 519468Sjtc regmatch_t rm[2]; 52031Salm char errbuf[256]; 52131Salm int eval; 522181Sconklin struct val *v; 5234Srgrimes 524166813Sceri /* coerce both arguments to strings */ 525181Sconklin to_string(a); 526181Sconklin to_string(b); 527181Sconklin 52831Salm /* compile regular expression */ 529223883Sse if ((eval = regcomp(&rp, b->u.s, 0)) != 0) { 530223883Sse regerror(eval, &rp, errbuf, sizeof(errbuf)); 53192979Swollman errx(ERR_EXIT, "%s", errbuf); 5324Srgrimes } 5334Srgrimes 53431Salm /* compare string against pattern */ 535539Sjtc /* remember that patterns are anchored to the beginning of the line */ 536223883Sse if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) 53731Salm if (rm[1].rm_so >= 0) { 538295Sjtc *(a->u.s + rm[1].rm_eo) = '\0'; 539223883Sse v = make_str(a->u.s + rm[1].rm_so); 54031Salm 541223883Sse } else 542233137Seadler v = make_integer((intmax_t)(rm[0].rm_eo)); 543223883Sse else 544223883Sse if (rp.re_nsub == 0) 545223883Sse v = make_integer((intmax_t)0); 546223883Sse else 547223883Sse v = make_str(""); 5484Srgrimes 54931Salm /* free arguments and pattern buffer */ 550223883Sse free_value(a); 551223883Sse free_value(b); 552223883Sse regfree(&rp); 55331Salm 554223883Sse return (v); 5554Srgrimes} 556