expr.y revision 223883
19313Ssos%{ 29313Ssos/*- 39313Ssos * Written by Pace Willisson (pace@blitz.com) 49313Ssos * and placed in the public domain. 59313Ssos * 69313Ssos * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 79313Ssos * 89313Ssos * $FreeBSD: head/bin/expr/expr.y 223883 2011-07-09 12:20:15Z se $ 914331Speter */ 109313Ssos 119313Ssos#include <sys/types.h> 129313Ssos 139313Ssos#include <ctype.h> 149313Ssos#include <err.h> 1597748Sschweikh#include <errno.h> 169313Ssos#include <inttypes.h> 179313Ssos#include <limits.h> 189313Ssos#include <locale.h> 199313Ssos#include <stdio.h> 209313Ssos#include <stdlib.h> 219313Ssos#include <string.h> 229313Ssos#include <regex.h> 239313Ssos#include <unistd.h> 249313Ssos 259313Ssos/* 269313Ssos * POSIX specifies a specific error code for syntax errors. We exit 279313Ssos * with this code for all errors. 289313Ssos */ 29116173Sobrien#define ERR_EXIT 2 30116173Sobrien 31116173Sobrienenum valtype { 32101189Srwatson integer, numeric_string, string 3349842Smarcel} ; 349313Ssos 35102954Sbdestruct val { 3676166Smarkm enum valtype type; 3776166Smarkm union { 3891385Srobert char *s; 3912458Sbde intmax_t i; 40114216Skan } u; 4176166Smarkm} ; 42101189Srwatson 43102954Sbdechar **av; 449313Ssosint nonposix; 459313Ssosstruct val *result; 4676166Smarkm 479313Ssosvoid assert_to_integer(struct val *); 4876166Smarkmvoid assert_div(intmax_t, intmax_t); 4972538Sjlemonvoid assert_minus(intmax_t, intmax_t, intmax_t); 509313Ssosvoid assert_plus(intmax_t, intmax_t, intmax_t); 5176166Smarkmvoid assert_times(intmax_t, intmax_t, intmax_t); 529313Ssosint compare_vals(struct val *, struct val *); 53102814Siedowsevoid free_value(struct val *); 5412458Sbdeint is_integer(const char *); 5576166Smarkmint is_string(struct val *); 56102954Sbdeint is_zero_or_null(struct val *); 5776166Smarkmstruct val *make_integer(intmax_t); 5880180Spirzykstruct val *make_str(const char *); 599313Ssosstruct val *op_and(struct val *, struct val *); 609313Ssosstruct val *op_colon(struct val *, struct val *); 619313Ssosstruct val *op_div(struct val *, struct val *); 6212652Sbdestruct val *op_eq(struct val *, struct val *); 6312689Speterstruct val *op_ge(struct val *, struct val *); 6412458Sbdestruct val *op_gt(struct val *, struct val *); 6512689Speterstruct val *op_le(struct val *, struct val *); 6612842Sbdestruct val *op_lt(struct val *, struct val *); 6780180Spirzykstruct val *op_minus(struct val *, struct val *); 6880180Spirzykstruct val *op_ne(struct val *, struct val *); 6912458Sbdestruct val *op_or(struct val *, struct val *); 7049849Smarcelstruct val *op_plus(struct val *, struct val *); 7149849Smarcelstruct val *op_rem(struct val *, struct val *); 7264909Smarcelstruct val *op_times(struct val *, struct val *); 7368583Smarcelint to_integer(struct val *); 74102954Sbdevoid to_string(struct val *); 7564909Smarcelint yyerror(const char *); 7664909Smarcelint yylex(void); 7764909Smarcelint yyparse(void); 7868201Sobrien 7968201Sobrien%} 8068201Sobrien 8151793Smarcel%union 8251793Smarcel{ 8368201Sobrien struct val *val; 8451793Smarcel} 8568201Sobrien 8683221Smarcel%left <val> '|' 8783221Smarcel%left <val> '&' 8883221Smarcel%left <val> '=' '>' '<' GE LE NE 8983221Smarcel%left <val> '+' '-' 9049626Smarcel%left <val> '*' '/' '%' 9168201Sobrien%left <val> ':' 9249626Smarcel 9383221Smarcel%token <val> TOKEN 9483221Smarcel%type <val> start expr 9583221Smarcel 9683221Smarcel%% 9783221Smarcel 9883221Smarcelstart: expr { result = $$; } 9983221Smarcel 10083221Smarcelexpr: TOKEN 10183221Smarcel | '(' expr ')' { $$ = $2; } 10283221Smarcel | expr '|' expr { $$ = op_or($1, $3); } 10383221Smarcel | expr '&' expr { $$ = op_and($1, $3); } 10480180Spirzyk | expr '=' expr { $$ = op_eq($1, $3); } 10568201Sobrien | expr '>' expr { $$ = op_gt($1, $3); } 1069313Ssos | expr '<' expr { $$ = op_lt($1, $3); } 10783366Sjulian | expr GE expr { $$ = op_ge($1, $3); } 10880180Spirzyk | expr LE expr { $$ = op_le($1, $3); } 10983221Smarcel | expr NE expr { $$ = op_ne($1, $3); } 11083221Smarcel | expr '+' expr { $$ = op_plus($1, $3); } 11183221Smarcel | expr '-' expr { $$ = op_minus($1, $3); } 11283221Smarcel | expr '*' expr { $$ = op_times($1, $3); } 11380180Spirzyk | expr '/' expr { $$ = op_div($1, $3); } 11483221Smarcel | expr '%' expr { $$ = op_rem($1, $3); } 11583221Smarcel | expr ':' expr { $$ = op_colon($1, $3); } 11683221Smarcel ; 11783221Smarcel 11883221Smarcel%% 11983221Smarcel 12083221Smarcelstruct val * 12183221Smarcelmake_integer(intmax_t i) 12283221Smarcel{ 12383221Smarcel struct val *vp; 12483221Smarcel 12583221Smarcel vp = (struct val *)malloc(sizeof(*vp)); 12683221Smarcel if (vp == NULL) 12783221Smarcel errx(ERR_EXIT, "malloc() failed"); 12883221Smarcel 12983221Smarcel vp->type = integer; 13080180Spirzyk vp->u.i = i; 13183221Smarcel return (vp); 13283221Smarcel} 13383221Smarcel 13480180Spirzykstruct val * 13583221Smarcelmake_str(const char *s) 13683221Smarcel{ 13780180Spirzyk struct val *vp; 13883221Smarcel 13983221Smarcel vp = (struct val *)malloc(sizeof(*vp)); 14083221Smarcel if (vp == NULL || ((vp->u.s = strdup(s)) == NULL)) 14183221Smarcel errx(ERR_EXIT, "malloc() failed"); 14283221Smarcel 14380180Spirzyk if (is_integer(s)) 14483221Smarcel vp->type = numeric_string; 14583221Smarcel else 14680180Spirzyk vp->type = string; 14783221Smarcel 14883221Smarcel return (vp); 14983221Smarcel} 15083221Smarcel 15183221Smarcelvoid 15283221Smarcelfree_value(struct val *vp) 15383221Smarcel{ 15480180Spirzyk if (vp->type == string || vp->type == numeric_string) 15583221Smarcel free(vp->u.s); 15680180Spirzyk} 157111797Sdes 15880180Spirzykint 15980180Spirzykto_integer(struct val *vp) 16080180Spirzyk{ 16180180Spirzyk intmax_t i; 16280180Spirzyk 16383366Sjulian /* we can only convert numeric_string to integer, here */ 1649313Ssos if (vp->type == numeric_string) { 16583221Smarcel errno = 0; 16683221Smarcel i = strtoimax(vp->u.s, (char **)NULL, 10); 167113613Sjhb /* just keep as numeric_string, if the conversion fails */ 1689313Ssos if (errno != ERANGE) { 1699313Ssos free(vp->u.s); 17072543Sjlemon vp->u.i = i; 17172543Sjlemon vp->type = integer; 1729313Ssos } 17383221Smarcel } 17483221Smarcel return (vp->type == integer); 17583221Smarcel} 17683221Smarcel 17783221Smarcelvoid 17883221Smarcelassert_to_integer(struct val *vp) 17983221Smarcel{ 18083221Smarcel if (vp->type == string) 181113613Sjhb errx(ERR_EXIT, "not a decimal number: '%s'", vp->u.s); 182113613Sjhb if (!to_integer(vp)) 183113613Sjhb errx(ERR_EXIT, "operand too large: '%s'", vp->u.s); 18483221Smarcel} 18583221Smarcel 186113613Sjhbvoid 18783221Smarcelto_string(struct val *vp) 188113613Sjhb{ 189113613Sjhb char *tmp; 19083221Smarcel 19183221Smarcel if (vp->type == string || vp->type == numeric_string) 192113613Sjhb return; 193113613Sjhb 19483221Smarcel /* 19583221Smarcel * log_10(x) ~= 0.3 * log_2(x). Rounding up gives the number 19683221Smarcel * of digits; add one each for the sign and terminating null 19783221Smarcel * character, respectively. 19883366Sjulian */ 19983221Smarcel#define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1) 20083221Smarcel tmp = malloc(NDIGITS(vp->u.i)); 2019313Ssos if (tmp == NULL) 20268201Sobrien errx(ERR_EXIT, "malloc() failed"); 2039313Ssos 2049313Ssos sprintf(tmp, "%jd", vp->u.i); 20583366Sjulian vp->type = string; 2069313Ssos vp->u.s = tmp; 20783366Sjulian} 20883221Smarcel 20983221Smarcelint 21083221Smarcelis_integer(const char *s) 21183221Smarcel{ 2129313Ssos if (nonposix) { 2139313Ssos if (*s == '\0') 21472543Sjlemon return (1); 21572543Sjlemon while (isspace((unsigned char)*s)) 2169313Ssos s++; 21783221Smarcel } 21883221Smarcel if (*s == '-' || (nonposix && *s == '+')) 21983221Smarcel s++; 22083366Sjulian if (*s == '\0') 22183366Sjulian return (0); 22283221Smarcel while (isdigit((unsigned char)*s)) 22383366Sjulian s++; 2249313Ssos return (*s == '\0'); 22583221Smarcel} 2269313Ssos 2279313Ssosint 2289313Ssosis_string(struct val *vp) 22983366Sjulian{ 2309313Ssos /* only TRUE if this string is not a valid integer */ 23183221Smarcel return (vp->type == string); 23283221Smarcel} 23383221Smarcel 23483221Smarcelint 23583221Smarcelyylex(void) 23683221Smarcel{ 23783221Smarcel char *p; 23883221Smarcel 239102814Siedowse if (*av == NULL) 24083221Smarcel return (0); 24183221Smarcel 2429313Ssos p = *av++; 243102814Siedowse 24414331Speter if (strlen(p) == 1) { 2459313Ssos if (strchr("|&=<>+-*/%:()", *p)) 24672543Sjlemon return (*p); 247102814Siedowse } else if (strlen(p) == 2 && p[1] == '=') { 2489313Ssos switch (*p) { 2499313Ssos case '>': return (GE); 25083221Smarcel case '<': return (LE); 25183221Smarcel case '!': return (NE); 25283221Smarcel } 25314114Speter } 25495130Srwatson 255101189Srwatson yylval.val = make_str(p); 25695130Srwatson return (TOKEN); 25795130Srwatson} 258102814Siedowse 25983221Smarcelint 260102814Siedowseis_zero_or_null(struct val *vp) 26183221Smarcel{ 26283221Smarcel if (vp->type == integer) 2639313Ssos return (vp->u.i == 0); 26483221Smarcel 26583221Smarcel return (*vp->u.s == 0 || (to_integer(vp) && vp->u.i == 0)); 26683221Smarcel} 26783221Smarcel 26883221Smarcelint 26983221Smarcelmain(int argc, char *argv[]) 27083221Smarcel{ 27183221Smarcel int c; 27283221Smarcel 27383221Smarcel setlocale(LC_ALL, ""); 2749313Ssos if (getenv("EXPR_COMPAT") != NULL 27583221Smarcel || check_utility_compat("expr")) { 27683221Smarcel av = argv + 1; 27783221Smarcel nonposix = 1; 27883221Smarcel } else { 27914114Speter while ((c = getopt(argc, argv, "e")) != -1) { 28083221Smarcel switch (c) { 28183221Smarcel case 'e': 28283221Smarcel nonposix = 1; 28383221Smarcel break; 28483221Smarcel default: 2859313Ssos errx(ERR_EXIT, 28683221Smarcel "usage: expr [-e] expression\n"); 28791406Sjhb } 28883221Smarcel } 28983221Smarcel av = argv + optind; 2909313Ssos } 29183221Smarcel 29283221Smarcel yyparse(); 29383221Smarcel 29483221Smarcel if (result->type == integer) 29583221Smarcel printf("%jd\n", result->u.i); 2969313Ssos else 29783221Smarcel printf("%s\n", result->u.s); 29883221Smarcel 29983221Smarcel return (is_zero_or_null(result)); 30083221Smarcel} 30183221Smarcel 3029313Ssosint 30383221Smarcelyyerror(const char *s __unused) 30491406Sjhb{ 30583221Smarcel errx(ERR_EXIT, "syntax error"); 30683221Smarcel} 3079313Ssos 30898209Srwatsonstruct val * 30998209Srwatsonop_or(struct val *a, struct val *b) 31098209Srwatson{ 31198209Srwatson if (!is_zero_or_null(a)) { 312101189Srwatson free_value(b); 313101189Srwatson return (a); 314101189Srwatson } 315101189Srwatson free_value(a); 316101189Srwatson if (!is_zero_or_null(b)) 31791406Sjhb return (b); 31883221Smarcel free_value(b); 31983221Smarcel return (make_integer((intmax_t)0)); 3209313Ssos} 321103941Sjeff 322103941Sjeffstruct val * 323103941Sjeffop_and(struct val *a, struct val *b) 32483221Smarcel{ 32583221Smarcel if (is_zero_or_null(a) || is_zero_or_null(b)) { 32683221Smarcel free_value(a); 327103941Sjeff free_value(b); 32883366Sjulian return (make_integer((intmax_t)0)); 32911163Sjulian } else { 33083221Smarcel free_value(b); 33183221Smarcel return (a); 3329313Ssos } 33383221Smarcel} 33483221Smarcel 33583221Smarcelint 33683221Smarcelcompare_vals(struct val *a, struct val *b) 33783221Smarcel{ 3389313Ssos int r; 33983221Smarcel 34083221Smarcel if (is_string(a) || is_string(b)) { 34183221Smarcel to_string(a); 34214114Speter to_string(b); 34383221Smarcel r = strcoll(a->u.s, b->u.s); 34483221Smarcel } else { 34583221Smarcel assert_to_integer(a); 34683221Smarcel assert_to_integer(b); 34783221Smarcel if (a->u.i > b->u.i) 34883221Smarcel r = 1; 34983221Smarcel else if (a->u.i < b->u.i) 35083221Smarcel r = -1; 35183221Smarcel else 35283221Smarcel r = 0; 35383221Smarcel } 35483221Smarcel 3559313Ssos free_value(a); 35683221Smarcel free_value(b); 35714114Speter return (r); 35883221Smarcel} 35983221Smarcel 36083221Smarcelstruct val * 36183221Smarcelop_eq(struct val *a, struct val *b) 36283221Smarcel{ 36314114Speter return (make_integer((intmax_t)(compare_vals(a, b) == 0))); 36483221Smarcel} 36583221Smarcel 36683221Smarcelstruct val * 36783221Smarcelop_gt(struct val *a, struct val *b) 36883221Smarcel{ 36914114Speter return (make_integer((intmax_t)(compare_vals(a, b) > 0))); 37083366Sjulian} 37183221Smarcel 37270061Sjhbstruct val * 37383221Smarcelop_lt(struct val *a, struct val *b) 37483221Smarcel{ 37583221Smarcel return (make_integer((intmax_t)(compare_vals(a, b) < 0))); 37683221Smarcel} 37783221Smarcel 37884783Spsstruct val * 37983366Sjulianop_ge(struct val *a, struct val *b) 38083366Sjulian{ 38183221Smarcel return (make_integer((intmax_t)(compare_vals(a, b) >= 0))); 38283221Smarcel} 38383221Smarcel 38414114Speterstruct val * 385101308Sjeffop_le(struct val *a, struct val *b) 38683221Smarcel{ 387101308Sjeff return (make_integer((intmax_t)(compare_vals(a, b) <= 0))); 38814114Speter} 38983221Smarcel 39083221Smarcelstruct val * 39183221Smarcelop_ne(struct val *a, struct val *b) 39283221Smarcel{ 39383221Smarcel return (make_integer((intmax_t)(compare_vals(a, b) != 0))); 39483221Smarcel} 3959313Ssos 39683221Smarcelvoid 3979313Ssosassert_plus(intmax_t a, intmax_t b, intmax_t r) 39883221Smarcel{ 39914114Speter /* 40083221Smarcel * sum of two positive numbers must be positive, 40183221Smarcel * sum of two negative numbers must be negative 40214114Speter */ 40383221Smarcel if ((a > 0 && b > 0 && r <= 0) || 40483366Sjulian (a < 0 && b < 0 && r >= 0)) 40583366Sjulian errx(ERR_EXIT, "overflow"); 40683221Smarcel} 40783221Smarcel 40883221Smarcelstruct val * 4099313Ssosop_plus(struct val *a, struct val *b) 41083221Smarcel{ 41183221Smarcel struct val *r; 41283221Smarcel 41383221Smarcel assert_to_integer(a); 41483221Smarcel assert_to_integer(b); 41583221Smarcel r = make_integer(a->u.i + b->u.i); 41683221Smarcel assert_plus(a->u.i, b->u.i, r->u.i); 4179313Ssos 41883221Smarcel free_value(a); 419111797Sdes free_value(b); 420111797Sdes return (r); 4219313Ssos} 42283221Smarcel 42383221Smarcelvoid 42483221Smarcelassert_minus(intmax_t a, intmax_t b, intmax_t r) 4259313Ssos{ 42683221Smarcel /* special case subtraction of INTMAX_MIN */ 42783221Smarcel if (b == INTMAX_MIN && a < 0) 42883221Smarcel errx(ERR_EXIT, "overflow"); 4299313Ssos /* check addition of negative subtrahend */ 43083221Smarcel assert_plus(a, -b, r); 4319313Ssos} 43283221Smarcel 43383221Smarcelstruct val * 43483221Smarcelop_minus(struct val *a, struct val *b) 43583221Smarcel{ 43683221Smarcel struct val *r; 43714114Speter 43883221Smarcel assert_to_integer(a); 43983221Smarcel assert_to_integer(b); 44083221Smarcel r = make_integer(a->u.i - b->u.i); 44183221Smarcel assert_minus(a->u.i, b->u.i, r->u.i); 44283366Sjulian 44383221Smarcel free_value(a); 44483221Smarcel free_value(b); 44583221Smarcel return (r); 44683221Smarcel} 44783221Smarcel 4489313Ssosvoid 44983221Smarcelassert_times(intmax_t a, intmax_t b, intmax_t r) 45083221Smarcel{ 4519313Ssos /* 45283221Smarcel * if first operand is 0, no overflow is possible, 45383221Smarcel * else result of division test must match second operand 45483221Smarcel */ 45583221Smarcel if (a != 0 && r / a != b) 45614114Speter errx(ERR_EXIT, "overflow"); 45783221Smarcel} 45883366Sjulian 45983366Sjulianstruct val * 46083221Smarcelop_times(struct val *a, struct val *b) 46183221Smarcel{ 46283221Smarcel struct val *r; 46314114Speter 46414114Speter assert_to_integer(a); 46583221Smarcel assert_to_integer(b); 46683221Smarcel r = make_integer(a->u.i * b->u.i); 46783366Sjulian assert_times(a->u.i, b->u.i, r->u.i); 46814114Speter 46983221Smarcel free_value(a); 47083221Smarcel free_value(b); 47183221Smarcel return (r); 47283221Smarcel} 47314114Speter 47483221Smarcelvoid 4759313Ssosassert_div(intmax_t a, intmax_t b) 4769313Ssos{ 4779313Ssos if (b == 0) 47883366Sjulian errx(ERR_EXIT, "division by zero"); 47914331Speter /* only INTMAX_MIN / -1 causes overflow */ 48083221Smarcel if (a == INTMAX_MIN && b == -1) 48183221Smarcel errx(ERR_EXIT, "overflow"); 48214331Speter} 4839313Ssos 48483221Smarcelstruct val * 48583221Smarcelop_div(struct val *a, struct val *b) 48683221Smarcel{ 48783221Smarcel struct val *r; 4889313Ssos 48914331Speter assert_to_integer(a); 49083221Smarcel assert_to_integer(b); 49183221Smarcel /* assert based on operands only, not on result */ 49283221Smarcel assert_div(a->u.i, b->u.i); 49383221Smarcel r = make_integer(a->u.i / b->u.i); 49483221Smarcel 495111797Sdes free_value(a); 49683221Smarcel free_value(b); 49714331Speter return (r); 49883221Smarcel} 49983221Smarcel 50083221Smarcelstruct val * 50114331Speterop_rem(struct val *a, struct val *b) 50283221Smarcel{ 50383221Smarcel struct val *r; 50483221Smarcel 50583221Smarcel assert_to_integer(a); 50683221Smarcel assert_to_integer(b); 50783221Smarcel /* pass a=1 to only check for div by zero */ 50883221Smarcel assert_div(1, b->u.i); 50983221Smarcel r = make_integer(a->u.i % b->u.i); 51083221Smarcel 51183221Smarcel free_value(a); 51283221Smarcel free_value(b); 51383221Smarcel return (r); 51483221Smarcel} 51583221Smarcel 51683221Smarcelstruct val * 51783221Smarcelop_colon(struct val *a, struct val *b) 518102814Siedowse{ 519102814Siedowse regex_t rp; 520102814Siedowse regmatch_t rm[2]; 52114331Speter char errbuf[256]; 522102814Siedowse int eval; 523102814Siedowse struct val *v; 524102814Siedowse 52514331Speter /* coerce both arguments to strings */ 52683221Smarcel to_string(a); 52772543Sjlemon to_string(b); 52814331Speter 52983221Smarcel /* compile regular expression */ 53083221Smarcel if ((eval = regcomp(&rp, b->u.s, 0)) != 0) { 53183221Smarcel regerror(eval, &rp, errbuf, sizeof(errbuf)); 53283221Smarcel errx(ERR_EXIT, "%s", errbuf); 53383221Smarcel } 53483221Smarcel 53583221Smarcel /* compare string against pattern */ 53683221Smarcel /* remember that patterns are anchored to the beginning of the line */ 53783221Smarcel if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) 53814331Speter if (rm[1].rm_so >= 0) { 53983221Smarcel *(a->u.s + rm[1].rm_eo) = '\0'; 54083366Sjulian v = make_str(a->u.s + rm[1].rm_so); 54183221Smarcel 54283221Smarcel } else 54383221Smarcel v = make_integer((intmax_t)(rm[0].rm_eo - rm[0].rm_so)); 54483221Smarcel else 54583221Smarcel if (rp.re_nsub == 0) 54683221Smarcel v = make_integer((intmax_t)0); 54783221Smarcel else 54883221Smarcel v = make_str(""); 54983221Smarcel 55083221Smarcel /* free arguments and pattern buffer */ 55183221Smarcel free_value(a); 55283221Smarcel free_value(b); 55383221Smarcel regfree(&rp); 55414331Speter 55583221Smarcel return (v); 55683221Smarcel} 55783221Smarcel