/* expr -- evaluate expressions.
   Copyright (C) 1986, 1991 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */

/* Author: Mike Parker.

   This program evaluates expressions.  Each token (operator, operand,
   parenthesis) of the expression must be a seperate argument.  The
   parser used is a reasonably general one, though any incarnation of
   it is language-specific.  It is especially nice for expressions.

   The way it works is (parse_expr is special, parse_expr_1 is
   typical) follows.  Note that when the summary below speaks of a new
   node in this implementation no parse tree is needed; the node is
   evaluated immediately.  Note that one function can handle multiple
   operators all of equal precedence, provided they all associate
   ((x op x) op x).

	global token-list

	parse_expr ()
	while true
		lhs = parse_expr_1 ()
		if next-token = lowest-precendence-operator then
			advance token-list
			rhs = parse_expr_1 ()
			lhs = new-node (lhs, operator, rhs)
			continue while
		else if no more tokens then
			return lhs
		else
			syntax error (unrecognized operator)
		endif
	end while

	parse_expr_1 ()
	while true
		lhs = parse_expr_2 ()
		if next-token = second-lowest-precedence-operator then
			advance token-list
			rhs = parse_expr_1 ()
			lhs = new-node (lhs, operator, rhs)
			continue while
		else
			return lhs
		endif
	end while

	parse_expr_2 () similar, with a different operator
	parse_expr_3 () similar, with a different operator
	etc, until finally

	parse_expr_N ()
	if next-token is a left paren then
		advance token-list
		node = parse_expr () (the top parse_expr)
		check that next token is a right paren (syntax error if not)
		advance token-list
		return node
	else if next-token is a legal operand then
		advance token-list
		return new-leaf-node (operand)
	else
		syntax error (invalid operand)
	endif

   Define EVAL_TRACE to print an evaluation trace.  */

#include <stdio.h>
#include <ctype.h>
#include <sys/types.h>
#include <regex.h>
#include "system.h"

#define NEW(type) ((type *) xmalloc (sizeof (type)))
#define OLD(x) free ((char *) x)

/* the kinds of value we can have */
typedef enum
{
  integer,
  string
} TYPE;

/* a value is.... */
typedef struct
{
  TYPE type;			/* which kind */
  union
  {				/* the value itself */
    int i;
    char *s;
  } u;
} VALUE;

/* The arguments given to the program, minus the program name. */
char **args;

/* The name this program was run with. */
char *program_name;

VALUE *docolon ();
VALUE *eval ();
VALUE *int_value ();
VALUE *str_value ();
char *xstrdup ();
char *strstr ();
char *xmalloc ();
int isstring ();
int nextarg ();
int nomoreargs ();
int null ();
int toarith ();
void error ();
void freev ();
void printv ();
void tostring ();
void trace ();

void
main (argc, argv)
     int argc;
     char **argv;
{
  VALUE *v;

  program_name = argv[0];

  if (argc == 1)
    {
      fprintf (stderr, "Usage: %s expression...\n", argv[0]);
      exit (1);
    }
  args = argv + 1;

  v = eval ();
  if (!nomoreargs ())
    error (2, 0, "syntax error");
  printv (v);

  exit (null (v));
}

/* Return a VALUE for integer I. */
VALUE *
int_value (i)
     int i;
{
  VALUE *v;

  v = NEW (VALUE);
  v->type = integer;
  v->u.i = i;
  return (v);
}

/* Return a VALUE for string S. */
VALUE *
str_value (s)
     char *s;
{
  VALUE *v;

  v = NEW (VALUE);
  v->type = string;
  v->u.s = xstrdup (s);
  return (v);
}

/* Free VALUE V, including structure components. */
void
freev (v)
     VALUE *v;
{
  if (v->type == string)
    {
      free (v->u.s);
    }
  OLD (v);
}

/* Print VALUE V. */
void
printv (v)
     VALUE *v;
{
  switch (v->type)
    {
    case integer:
      printf ("%d\n", v->u.i);
      break;
    case string:
      printf ("%s\n", v->u.s);
      break;
    }
}

/* Return nonzero if V is a null-string or zero-number. */
int
null (v)
     VALUE *v;
{
  switch (v->type)
    {
    case integer:
      return (v->u.i == 0);
    case string:
      return (v->u.s[0] == '\0');
    }
}

/* Return nonzero if V is a string value. */
int
isstring (v)
     VALUE *v;
{
  return (v->type == string);
}

/* Coerce V to a string value (can't fail). */
void
tostring (v)
     VALUE *v;
{
  char *temp;

  switch (v->type)
    {
    case integer:
      temp = xmalloc (4 * (sizeof (int) / sizeof (char)));
      sprintf (temp, "%d", v->u.i);
      v->u.s = temp;
      v->type = string;
      break;
    case string:
      break;
    }
}

/* Coerce V to an integer value.  Return 1 on success, 0 on failure. */
int
toarith (v)
     VALUE *v;
{
  int i;
  int neg;
  char *cp;

  switch (v->type)
    {
    case integer:
      return (1);
    case string:
      i = 0;
      cp = v->u.s;
      if (neg = (*cp == '-'))
	{
	  cp++;
	}
      for (; *cp; cp++)
	{
	  if (isdigit (*cp))
	    {
	      i = (i * 10) + (*cp - '0');
	    }
	  else
	    {
	      return (0);
	    }
	}
      free (v->u.s);
      v->u.i = i * (neg ? -1 : 1);
      v->type = integer;
      return (1);
    }
}

/* Return nonzero if the next token matches STR exactly.
   STR must not be NULL.  */
int
nextarg (str)
     char *str;
{
  if (*args == NULL)
    {
      return 0;
    }
  return (strcmp (*args, str) == 0);
}

/* Return nonzero if there no more tokens. */
int
nomoreargs ()
{
  return (*args == 0);
}

/* the comparison operator handling functions */
#define cmpf(name, rel)				\
int name (l, r) VALUE *l; VALUE *r;		\
{						\
  if (isstring (l) || isstring (r))		\
    {						\
       tostring (l);				\
       tostring (r);				\
       return strcmp (l->u.s, r->u.s) rel 0;	\
    }						\
 else						\
   return l->u.i rel r->u.i;			\
}

cmpf (less_than, <)
cmpf (less_equal, <=)
cmpf (equal, ==)
cmpf (not_equal, !=)
cmpf (greater_equal, >=)
cmpf (greater_than, >)

#undef cmpf

/* the arithmetic operator handling functions */
#define arithf(name, op)			\
int name (l, r) VALUE *l; VALUE *r;		\
{						\
  if (!toarith (l) || !toarith (r))		\
    error (2, 0, "non-numeric argument");	\
  return l->u.i op r->u.i;			\
}

arithf (plus, +)
arithf (minus, -)
arithf (multiply, *)
arithf (divide, /)
arithf (mod, %)

#undef arithf

#ifdef EVAL_TRACE
/* function to print evaluation trace and args remaining */
void
trace (fxn)
     char *fxn;
{
  char **a;

  printf ("%s:", fxn);
  for (a = args; *a; a++)
    {
      printf (" %s", *a);
    }
  putchar ('\n');
}

#endif

/* do the : operator.  SV is the VALUE for the lhs (the string), PV is the
    VALUE for the rhs (the pattern). */
VALUE *
docolon (sv, pv)
     VALUE *sv;
     VALUE *pv;
{
  VALUE *v;
  char *errmsg;
  struct re_pattern_buffer re_buffer;
  struct re_registers re_regs;
  int len;

  tostring (sv);
  tostring (pv);

  len = strlen (pv->u.s);
  re_buffer.allocated = 2 * len;
  re_buffer.buffer = xmalloc (re_buffer.allocated);
  re_buffer.translate = 0;
  errmsg = re_compile_pattern (pv->u.s, len, &re_buffer);
  if (errmsg)
    error (2, 0, "%s", errmsg);

  len = re_match (&re_buffer, sv->u.s, strlen (sv->u.s), 0, &re_regs);
  if (len >= 0)
    {
      /* Were \(...\) used? */
      if (re_buffer.re_nsub > 0) /* was (re_regs.start[1] >= 0) */
	{
	  sv->u.s[re_regs.end[1]] = '\0';
	  v = str_value (sv->u.s + re_regs.start[1]);
	}
      else
	{
	  v = int_value (len);
	}
    }
  else
    {
      /* match failed -- return right kind of null */
      if (strstr (pv->u.s, "\\("))
	{
	  v = str_value ("");
	}
      else
	{
	  v = int_value (0);
	}
    }
  free (re_buffer.buffer);
  return (v);
}

/* eval6 -- handles bare operands and ( expr ) syntax */
VALUE *
eval6 ()
{
  VALUE *v;
  VALUE *eval ();

#ifdef EVAL_TRACE
  trace ("eval6");
#endif
  if (nextarg ("("))
    {
      args++;
      v = eval ();
      if (!nextarg (")"))
	{
	  error (2, 0, "syntax error");
	}
      args++;
      return (v);
    }
  else if (nextarg (")"))
    {
      error (2, 0, "syntax error");
    }
  else
    {
      v = str_value (*args++);
      (void) toarith (v);
      return (v);
    }
}

/* eval5 -- handles : operator (pattern matching).  Calls ``docolon'' to do
    the real work. */
VALUE *
eval5 ()
{
  VALUE *l;
  VALUE *r;
  VALUE *v;

#ifdef EVAL_TRACE
  trace ("eval5");
#endif
  l = eval6 ();
  while (1)
    {
      if (nextarg (":"))
	{
	  args++;
	  r = eval6 ();
	  v = docolon (l, r);
	  freev (l);
	  freev (r);
	  l = v;
	}
      else
	{
	  return (l);
	}
    }
}

/* eval4 -- handles *, /, % operators */
VALUE *
eval4 ()
{
  VALUE *l;
  VALUE *r;
  int (*fxn) ();
  int val;

#ifdef EVAL_TRACE
  trace ("eval4");
#endif
  l = eval5 ();
  while (1)
    {
      fxn = 0;
      if (nextarg ("*"))
	{
	  fxn = multiply;
	}
      else if (nextarg ("/"))
	{
	  fxn = divide;
	}
      else if (nextarg ("%"))
	{
	  fxn = mod;
	}
      if (fxn)
	{
	  args++;
	  r = eval5 ();
	  val = (*fxn) (l, r);
	  freev (l);
	  freev (r);
	  l = int_value (val);
	}
      else
	{
	  return (l);
	}
    }
}

/* eval3 -- handles +, - operators */
VALUE *
eval3 ()
{
  VALUE *l;
  VALUE *r;
  int (*fxn) ();
  int val;

#ifdef EVAL_TRACE
  trace ("eval3");
#endif
  l = eval4 ();
  while (1)
    {
      fxn = 0;
      if (nextarg ("+"))
	{
	  fxn = plus;
	}
      else if (nextarg ("-"))
	{
	  fxn = minus;
	}
      if (fxn)
	{
	  args++;
	  r = eval4 ();
	  val = (*fxn) (l, r);
	  freev (l);
	  freev (r);
	  l = int_value (val);
	}
      else
	{
	  return (l);
	}
    }
}

/* eval2 -- handles comparisons */
VALUE *
eval2 ()
{
  VALUE *l;
  VALUE *r;
  int (*fxn) ();
  int val;

#ifdef EVAL_TRACE
  trace ("eval2");
#endif
  l = eval3 ();
  while (1)
    {
      fxn = 0;
      if (nextarg ("<"))
	{
	  fxn = less_than;
	}
      else if (nextarg ("<="))
	{
	  fxn = less_equal;
	}
      else if (nextarg ("="))
	{
	  fxn = equal;
	}
      else if (nextarg ("!="))
	{
	  fxn = not_equal;
	}
      else if (nextarg (">="))
	{
	  fxn = greater_equal;
	}
      else if (nextarg (">"))
	{
	  fxn = greater_than;
	}
      if (fxn)
	{
	  args++;
	  r = eval3 ();
	  val = (*fxn) (l, r);
	  freev (l);
	  freev (r);
	  l = int_value (val);
	}
      else
	{
	  return (l);
	}
    }
}

/* eval1 -- handles & */
VALUE *
eval1 ()
{
  VALUE *l;
  VALUE *r;

#ifdef EVAL_TRACE
  trace ("eval1");
#endif
  l = eval2 ();
  while (1)
    {
      if (nextarg ("&"))
	{
	  args++;
	  r = eval2 ();
	  if (null (l) || null (r))
	    {
	      freev (l);
	      freev (r);
	      l = int_value (0);
	    }
	  else
	    {
	      freev (r);
	    }
	}
      else
	{
	  return (l);
	}
    }
}

/* eval -- handles | */
VALUE *
eval ()
{
  VALUE *l;
  VALUE *r;

#ifdef EVAL_TRACE
  trace ("eval");
#endif
  l = eval1 ();
  while (1)
    {
      if (nextarg ("|"))
	{
	  args++;
	  r = eval1 ();
	  if (null (l))
	    {
	      freev (l);
	      l = r;
	    }
	  else
	    {
	      freev (r);
	    }
	}
      else
	{
	  return (l);
	}
    }
}
