toys/pending/expr.c

   1 /* expr.c - evaluate expression
   2  *
   3  * Copyright 2013 Daniel Verkamp <daniel@drv.nu>
   4  *
   5  * http://pubs.opengroup.org/onlinepubs/9699919799/utilities/expr.html
   6  *
   7  * The web standard is incomplete (precedence grouping missing), see:
   8  * http://permalink.gmane.org/gmane.comp.standards.posix.austin.general/10141
   9
  10 USE_EXPR(NEWTOY(expr, NULL, TOYFLAG_USR|TOYFLAG_BIN))
  11
  12 config EXPR
  13   bool "expr"
  14   default n
  15   help
  16     usage: expr ARG1 OPERATOR ARG2...
  17
  18     Evaluate expression and print result. For example, "expr 1 + 2".
  19
  20     The supported operators are (grouped from highest to lowest priority):
  21
  22       ( )    :    * / %    + -    != <= < >= > =    &    |
  23
  24     Each constant and operator must be a separate command line argument.
  25     All operators are infix, meaning they expect a constant (or expression
  26     that resolves to a constant) on each side of the operator. Operators of
  27     the same priority (within each group above) are evaluated left to right.
  28     Parentheses may be used (as separate arguments) to elevate the priority
  29     of expressions.
  30
  31     Calling expr from a command shell requires a lot of \( or '*' escaping
  32     to avoid interpreting shell control characters.
  33
  34     The & and | operators are logical (not bitwise) and may operate on
  35     strings (a blank string is "false"). Comparison operators may also
  36     operate on strings (alphabetical sort).
  37
  38     Constants may be strings or integers. Comparison, logical, and regex
  39     operators may operate on strings (a blank string is "false"), other
  40     operators require integers.
  41 */
  42
  43 // TODO: int overflow checking
  44
  45 #define FOR_expr
  46 #include "toys.h"
  47
  48
  49 GLOBALS(
  50   int argidx;
  51 )
  52
  53 // Scalar value.
  54 // If s is NULL, the value is an integer (i).
  55 // If s is not NULL, the value is a string (s).
  56 struct value {
  57   char *s;
  58   long long i;
  59 };
  60
  61 // check if v is the integer 0 or the empty string
  62 static int is_zero(struct value *v)
  63 {
  64   return v->s ? !*v->s : !v->i;
  65 }
  66
  67 static char *num_to_str(long long num)
  68 {
  69   static char num_buf[21];
  70   snprintf(num_buf, sizeof(num_buf), "%lld", num);
  71   return num_buf;
  72 }
  73
  74 static int cmp(struct value *lhs, struct value *rhs)
  75 {
  76   if (lhs->s || rhs->s) {
  77     // at least one operand is a string
  78     char *ls = lhs->s ? lhs->s : num_to_str(lhs->i);
  79     char *rs = rhs->s ? rhs->s : num_to_str(rhs->i);
  80     return strcmp(ls, rs);
  81   } else return lhs->i - rhs->i;
  82 }
  83
  84 static void re(struct value *lhs, struct value *rhs)
  85 {
  86   regex_t rp;
  87   regmatch_t rm[2];
  88
  89   xregcomp(&rp, rhs->s, 0);
  90   if (!regexec(&rp, lhs->s, 2, rm, 0) && rm[0].rm_so == 0) {
  91     if (rp.re_nsub > 0 && rm[1].rm_so >= 0)
  92       lhs->s = xmprintf("%.*s", rm[1].rm_eo - rm[1].rm_so, lhs->s+rm[1].rm_so);
  93     else {
  94       lhs->i = rm[0].rm_eo;
  95       lhs->s = 0;
  96     }
  97   } else {
  98     if (!rp.re_nsub) {
  99       lhs->i = 0;
 100       lhs->s = 0;
 101     } else lhs->s = "";
 102   }
 103 }
 104
 105 static void mod(struct value *lhs, struct value *rhs)
 106 {
 107   if (lhs->s || rhs->s) error_exit("non-integer argument");
 108   if (is_zero(rhs)) error_exit("division by zero");
 109   lhs->i %= rhs->i;
 110 }
 111
 112 static void divi(struct value *lhs, struct value *rhs)
 113 {
 114   if (lhs->s || rhs->s) error_exit("non-integer argument");
 115   if (is_zero(rhs)) error_exit("division by zero");
 116   lhs->i /= rhs->i;
 117 }
 118
 119 static void mul(struct value *lhs, struct value *rhs)
 120 {
 121   if (lhs->s || rhs->s) error_exit("non-integer argument");
 122   lhs->i *= rhs->i;
 123 }
 124
 125 static void sub(struct value *lhs, struct value *rhs)
 126 {
 127   if (lhs->s || rhs->s) error_exit("non-integer argument");
 128   lhs->i -= rhs->i;
 129 }
 130
 131 static void add(struct value *lhs, struct value *rhs)
 132 {
 133   if (lhs->s || rhs->s) error_exit("non-integer argument");
 134   lhs->i += rhs->i;
 135 }
 136
 137 static void ne(struct value *lhs, struct value *rhs)
 138 {
 139   lhs->i = cmp(lhs, rhs) != 0;
 140   lhs->s = NULL;
 141 }
 142
 143 static void lte(struct value *lhs, struct value *rhs)
 144 {
 145   lhs->i = cmp(lhs, rhs) <= 0;
 146   lhs->s = NULL;
 147 }
 148
 149 static void lt(struct value *lhs, struct value *rhs)
 150 {
 151   lhs->i = cmp(lhs, rhs) < 0;
 152   lhs->s = NULL;
 153 }
 154
 155 static void gte(struct value *lhs, struct value *rhs)
 156 {
 157   lhs->i = cmp(lhs, rhs) >= 0;
 158   lhs->s = NULL;
 159 }
 160
 161 static void gt(struct value *lhs, struct value *rhs)
 162 {
 163   lhs->i = cmp(lhs, rhs) > 0;
 164   lhs->s = NULL;
 165 }
 166
 167 static void eq(struct value *lhs, struct value *rhs)
 168 {
 169   lhs->i = !cmp(lhs, rhs);
 170   lhs->s = NULL;
 171 }
 172
 173 static void and(struct value *lhs, struct value *rhs)
 174 {
 175   if (is_zero(lhs) || is_zero(rhs)) {
 176     lhs->i = 0;
 177     lhs->s = NULL;
 178   }
 179 }
 180
 181 static void or(struct value *lhs, struct value *rhs)
 182 {
 183   if (is_zero(lhs)) *lhs = *rhs;
 184 }
 185
 186 static void get_value(struct value *v)
 187 {
 188   char *endp, *arg;
 189
 190   if (TT.argidx == toys.optc) {
 191     v->i = 0;
 192     v->s = ""; // signal end of expression
 193     return;
 194   }
 195
 196 //  can't happen, the increment is after the == test
 197 //  if (TT.argidx >= toys.optc) error_exit("syntax error");
 198
 199   arg = toys.optargs[TT.argidx++];
 200
 201   v->i = strtoll(arg, &endp, 10);
 202   v->s = *endp ? arg : NULL;
 203 }
 204
 205 // check if v matches a token, and consume it if so
 206 static int match(struct value *v, char *tok)
 207 {
 208   if (v->s && !strcmp(v->s, tok)) {
 209     get_value(v);
 210     return 1;
 211   }
 212
 213   return 0;
 214 }
 215
 216 // operators in order of increasing precedence
 217 static struct op {
 218   char *tok;
 219
 220   // calculate "lhs op rhs" (e.g. lhs + rhs) and store result in lhs
 221   void (*calc)(struct value *lhs, struct value *rhs);
 222 } ops[] = {
 223   {"|",   or  }, {"&",   and }, {"=",   eq  }, {"==",  eq  }, {">",   gt  },
 224   {">=",  gte }, {"<",   lt  }, {"<=",  lte }, {"!=",  ne  }, {"+",   add },
 225   {"-",   sub }, {"*",   mul }, {"/",   divi}, {"%",   mod }, {":",   re  },
 226   {"(",   NULL}, // special case - must be last
 227 };
 228
 229 // "|,&,= ==> >=< <= !=,+-,*/%,:"
 230
 231 static void parse_op(struct value *lhs, struct value *tok, struct op *op)
 232 {
 233   if (!op) op = ops;
 234
 235   // special case parsing for parentheses
 236   if (*op->tok == '(') {
 237     if (match(tok, "(")) {
 238       parse_op(lhs, tok, 0);
 239       if (!match(tok, ")")) error_exit("syntax error"); // missing closing paren
 240     } else {
 241       // tok is a string or integer - return it and get the next token
 242       *lhs = *tok;
 243       get_value(tok);
 244     }
 245
 246     return;
 247   }
 248
 249   parse_op(lhs, tok, op + 1);
 250   while (match(tok, op->tok)) {
 251     struct value rhs;
 252     parse_op(&rhs, tok, op + 1);
 253     if (rhs.s && !*rhs.s) error_exit("syntax error"); // premature end of expression
 254     op->calc(lhs, &rhs);
 255   }
 256 }
 257
 258 void expr_main(void)
 259 {
 260   struct value tok, ret = {0};
 261
 262   toys.exitval = 2; // if exiting early, indicate invalid expression
 263
 264   TT.argidx = 0;
 265
 266   get_value(&tok); // warm up the parser with the initial value
 267   parse_op(&ret, &tok, 0);
 268
 269   // final token should be end of expression
 270   if (!tok.s || *tok.s) error_exit("syntax error");
 271
 272   if (ret.s) printf("%s\n", ret.s);
 273   else printf("%lld\n", ret.i);
 274
 275   exit(is_zero(&ret));
 276 }