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
10USE_EXPR(NEWTOY(expr, NULL, TOYFLAG_USR|TOYFLAG_BIN))
11
12config 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
49GLOBALS(
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).
56struct value {
57  char *s;
58  long long i;
59};
60
61// check if v is the integer 0 or the empty string
62static int is_zero(struct value *v)
63{
64  return v->s ? !*v->s : !v->i;
65}
66
67static 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
74static 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
84static 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
105static 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
112static 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
119static 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
125static 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
131static 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
137static void ne(struct value *lhs, struct value *rhs)
138{
139  lhs->i = cmp(lhs, rhs) != 0;
140  lhs->s = NULL;
141}
142
143static void lte(struct value *lhs, struct value *rhs)
144{
145  lhs->i = cmp(lhs, rhs) <= 0;
146  lhs->s = NULL;
147}
148
149static void lt(struct value *lhs, struct value *rhs)
150{
151  lhs->i = cmp(lhs, rhs) < 0;
152  lhs->s = NULL;
153}
154
155static void gte(struct value *lhs, struct value *rhs)
156{
157  lhs->i = cmp(lhs, rhs) >= 0;
158  lhs->s = NULL;
159}
160
161static void gt(struct value *lhs, struct value *rhs)
162{
163  lhs->i = cmp(lhs, rhs) > 0;
164  lhs->s = NULL;
165}
166
167static void eq(struct value *lhs, struct value *rhs)
168{
169  lhs->i = !cmp(lhs, rhs);
170  lhs->s = NULL;
171}
172
173static 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
181static void or(struct value *lhs, struct value *rhs)
182{
183  if (is_zero(lhs)) *lhs = *rhs;
184}
185
186static 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
206static 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
217static 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
231static 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
258void 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}
277