/*-
* Copyright (c) 2010 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by David A. Holland.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in the
*    documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/

#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>

//#define DEBUG
#ifdef DEBUG
#include <stdio.h>
#endif

#include "utils.h"
#include "array.h"
#include "mode.h"
#include "place.h"
#include "eval.h"

/*
* e ::=
*    e1 ? e2 : e3
*    e1 || e2
*    e1 && e2
*    e1 | e2
*    e1 ^ e2
*    e1 & e2
*    e1 == e2  |  e1 != e2
*    e1 < e2   |  e1 <= e2  |  e1 > e2  |  e1 >= e2
*    e1 << e2  |  e1 >> e2
*    e1 + e2   |  e1 - e2
*    e1 * e2   |  e1 / e2   |  e1 % e2
*    !e  |  ~e  |  -e  |  +e
*    ( e )  |  ident
*/

enum tokens {
       T_EOF,          /* end of input */
       T_VAL,          /* value */
       T_LPAREN,       /* parens */
       T_RPAREN,
       T_PIPEPIPE,     /* operators */
       T_AMPAMP,
       T_EQEQ,
       T_BANGEQ,
       T_LTEQ,
       T_GTEQ,
       T_LTLT,
       T_GTGT,
       T_QUES,
       T_COLON,
       T_PIPE,
       T_CARET,
       T_AMP,
       T_LT,
       T_GT,
       T_PLUS,
       T_MINUS,
       T_STAR,
       T_SLASH,
       T_PCT,
       T_BANG,
       T_TILDE,
};

static const struct {
       char c1, c2;
       enum tokens tok;
} tokens_2[] = {
       { '|', '|', T_PIPEPIPE },
       { '&', '&', T_AMPAMP },
       { '=', '=', T_EQEQ },
       { '!', '=', T_BANGEQ },
       { '<', '=', T_LTEQ },
       { '>', '=', T_GTEQ },
       { '<', '<', T_LTLT },
       { '>', '>', T_GTGT },
};
static const unsigned num_tokens_2 = HOWMANY(tokens_2);

static const struct {
       char c1;
       enum tokens tok;
} tokens_1[] = {
       { '?', T_QUES },
       { ':', T_COLON },
       { '|', T_PIPE },
       { '^', T_CARET },
       { '&', T_AMP },
       { '<', T_LT },
       { '>', T_GT },
       { '+', T_PLUS },
       { '-', T_MINUS },
       { '*', T_STAR },
       { '/', T_SLASH },
       { '%', T_PCT },
       { '!', T_BANG },
       { '~', T_TILDE },
       { '(', T_LPAREN },
       { ')', T_RPAREN },
};
static const unsigned num_tokens_1 = HOWMANY(tokens_1);

struct token {
       struct place place;
       enum tokens tok;
       int val;
};
DECLARRAY(token, static UNUSED);
DEFARRAY(token, static);

static struct tokenarray tokens;

static
struct token *
token_create(const struct place *p, enum tokens tok, int val)
{
       struct token *t;

       t = domalloc(sizeof(*t));
       t->place = *p;
       t->tok = tok;
       t->val = val;
       return t;
}

static
void
token_destroy(struct token *t)
{
       dofree(t, sizeof(*t));
}

DESTROYALL_ARRAY(token, );

#ifdef DEBUG
static
void
printtokens(void)
{
       unsigned i, num;
       struct token *t;

       fprintf(stderr, "tokens:");
       num = tokenarray_num(&tokens);
       for (i=0; i<num; i++) {
               t = tokenarray_get(&tokens, i);
               switch (t->tok) {
                   case T_EOF: fprintf(stderr, " <eof>"); break;
                   case T_VAL: fprintf(stderr, " %d", t->val); break;
                   case T_LPAREN: fprintf(stderr, " ("); break;
                   case T_RPAREN: fprintf(stderr, " )"); break;
                   case T_PIPEPIPE: fprintf(stderr, " ||"); break;
                   case T_AMPAMP: fprintf(stderr, " &&"); break;
                   case T_EQEQ: fprintf(stderr, " =="); break;
                   case T_BANGEQ: fprintf(stderr, " !="); break;
                   case T_LTEQ: fprintf(stderr, " <="); break;
                   case T_GTEQ: fprintf(stderr, " >="); break;
                   case T_LTLT: fprintf(stderr, " <<"); break;
                   case T_GTGT: fprintf(stderr, " >>"); break;
                   case T_QUES: fprintf(stderr, " ?"); break;
                   case T_COLON: fprintf(stderr, " :"); break;
                   case T_PIPE: fprintf(stderr, " |"); break;
                   case T_CARET: fprintf(stderr, " ^"); break;
                   case T_AMP: fprintf(stderr, " &"); break;
                   case T_LT: fprintf(stderr, " <"); break;
                   case T_GT: fprintf(stderr, " >"); break;
                   case T_PLUS: fprintf(stderr, " +"); break;
                   case T_MINUS: fprintf(stderr, " -"); break;
                   case T_STAR: fprintf(stderr, " *"); break;
                   case T_SLASH: fprintf(stderr, " /"); break;
                   case T_PCT: fprintf(stderr, " %%"); break;
                   case T_BANG: fprintf(stderr, " !"); break;
                   case T_TILDE: fprintf(stderr, " ~"); break;
               }
       }
       fprintf(stderr, "\n");
}
#endif

static
bool
isuop(enum tokens tok)
{
       switch (tok) {
           case T_BANG:
           case T_TILDE:
           case T_MINUS:
           case T_PLUS:
               return true;
           default:
               break;
       }
       return false;
}

static
bool
isbop(enum tokens tok)
{
       switch (tok) {
           case T_EOF:
           case T_VAL:
           case T_LPAREN:
           case T_RPAREN:
           case T_COLON:
           case T_QUES:
           case T_BANG:
           case T_TILDE:
               return false;
           default:
               break;
       }
       return true;
}

static
bool
isop(enum tokens tok)
{
       switch (tok) {
           case T_EOF:
           case T_VAL:
           case T_LPAREN:
           case T_RPAREN:
               return false;
           default:
               break;
       }
       return true;
}

static
int
getprec(enum tokens tok)
{
       switch (tok) {
           case T_BANG: case T_TILDE: return -1;
           case T_STAR: case T_SLASH: case T_PCT: return 0;
           case T_PLUS: case T_MINUS: return 1;
           case T_LTLT: case T_GTGT: return 2;
           case T_LT: case T_LTEQ: case T_GT: case T_GTEQ: return 3;
           case T_EQEQ: case T_BANGEQ: return 4;
           case T_AMP: return 5;
           case T_CARET: return 6;
           case T_PIPE: return 7;
           case T_AMPAMP: return 8;
           case T_PIPEPIPE: return 9;
           default: break;
       }
       return 10;
}

static
bool
looser(enum tokens t1, enum tokens t2)
{
       return getprec(t1) >= getprec(t2);
}

static
int
eval_uop(enum tokens op, int val)
{
       switch (op) {
           case T_BANG: val = !val; break;
           case T_TILDE: val = (int)~(unsigned)val; break;
           case T_MINUS: val = -val; break;
           case T_PLUS: break;
           default: assert(0); break;
       }
       return val;
}

static
int
eval_bop(struct place *p, int lv, enum tokens op, int rv)
{
       unsigned mask;

       switch (op) {
           case T_PIPEPIPE: return lv || rv;
           case T_AMPAMP:   return lv && rv;
           case T_PIPE:     return (int)((unsigned)lv | (unsigned)rv);
           case T_CARET:    return (int)((unsigned)lv ^ (unsigned)rv);
           case T_AMP:      return (int)((unsigned)lv & (unsigned)rv);
           case T_EQEQ:     return lv == rv;
           case T_BANGEQ:   return lv != rv;
           case T_LT:       return lv < rv;
           case T_GT:       return lv > rv;
           case T_LTEQ:     return lv <= rv;
           case T_GTEQ:     return lv >= rv;

           case T_LTLT:
           case T_GTGT:
               if (rv < 0) {
                       complain(p, "Negative bit-shift");
                       complain_fail();
                       rv = 0;
               }
               if ((unsigned)rv >= CHAR_BIT * sizeof(unsigned)) {
                       complain(p, "Bit-shift farther than type width");
                       complain_fail();
                       rv = 0;
               }
               if (op == T_LTLT) {
                       return (int)((unsigned)lv << (unsigned)rv);
               }
               mask = ((unsigned)-1) << (CHAR_BIT * sizeof(unsigned) - rv);
               lv = (int)(((unsigned)lv >> (unsigned)rv) | mask);
               return lv;

           case T_MINUS:
               if (rv == INT_MIN) {
                       if (lv == INT_MIN) {
                               return 0;
                       }
                       lv--;
                       rv++;
               }
               rv = -rv;
               /* FALLTHROUGH */
           case T_PLUS:
               if (rv > 0 && lv > (INT_MAX - rv)) {
                       complain(p, "Integer overflow");
                       complain_fail();
                       return INT_MAX;
               }
               if (rv < 0 && lv < (INT_MIN - rv)) {
                       complain(p, "Integer underflow");
                       complain_fail();
                       return INT_MIN;
               }
               return lv + rv;

           case T_STAR:
               if (rv == 0) {
                       return 0;
               }
               if (rv == 1) {
                       return lv;
               }
               if (rv == -1 && lv == INT_MIN) {
                       lv++;
                       lv = -lv;
                       if (lv == INT_MAX) {
                               complain(p, "Integer overflow");
                               complain_fail();
                               return INT_MAX;
                       }
                       lv++;
                       return lv;
               }
               if (lv == INT_MIN && rv < 0) {
                       complain(p, "Integer overflow");
                       complain_fail();
                       return INT_MAX;
               }
               if (lv == INT_MIN && rv > 0) {
                       complain(p, "Integer underflow");
                       complain_fail();
                       return INT_MIN;
               }
               if (rv < 0) {
                       rv = -rv;
                       lv = -lv;
               }
               if (lv > 0 && lv > INT_MAX / rv) {
                       complain(p, "Integer overflow");
                       complain_fail();
                       return INT_MAX;
               }
               if (lv < 0 && lv < INT_MIN / rv) {
                       complain(p, "Integer underflow");
                       complain_fail();
                       return INT_MIN;
               }
               return lv * rv;

           case T_SLASH:
               if (rv == 0) {
                       complain(p, "Division by zero");
                       complain_fail();
                       return 0;
               }
               return lv / rv;

           case T_PCT:
               if (rv == 0) {
                       complain(p, "Modulus by zero");
                       complain_fail();
                       return 0;
               }
               return lv % rv;

           default: assert(0); break;
       }
       return 0;
}

static
void
tryreduce(void)
{
       unsigned num;
       struct token *t1, *t2, *t3, *t4, *t5, *t6;

       while (1) {
#ifdef DEBUG
               printtokens();
#endif
               num = tokenarray_num(&tokens);
               t1 = (num >= 1) ? tokenarray_get(&tokens, num-1) : NULL;
               t2 = (num >= 2) ? tokenarray_get(&tokens, num-2) : NULL;
               t3 = (num >= 3) ? tokenarray_get(&tokens, num-3) : NULL;

               if (num >= 3 &&
                   t3->tok == T_LPAREN &&
                   t2->tok == T_VAL &&
                   t1->tok == T_RPAREN) {
                       /* (x) -> x */
                       t2->place = t3->place;
                       token_destroy(t1);
                       token_destroy(t3);
                       tokenarray_remove(&tokens, num-1);
                       tokenarray_remove(&tokens, num-3);
                       continue;
               }

               if (num >= 2 &&
                   (num == 2 || isop(t3->tok) || t3->tok == T_LPAREN) &&
                   isuop(t2->tok) &&
                   t1->tok == T_VAL) {
                       /* unary operator */
                       t1->val = eval_uop(t2->tok, t1->val);
                       t1->place = t2->place;
                       token_destroy(t2);
                       tokenarray_remove(&tokens, num-2);
                       continue;
               }
               if (num >= 2 &&
                   (num == 2 || isop(t3->tok) || t3->tok == T_LPAREN) &&
                   t2->tok != T_LPAREN && t2->tok != T_VAL &&
                   t1->tok == T_VAL) {
                       complain(&t2->place, "Invalid unary operator");
                       complain_fail();
                       token_destroy(t2);
                       tokenarray_remove(&tokens, num-2);
                       continue;
               }


               t4 = (num >= 4) ? tokenarray_get(&tokens, num-4) : NULL;

               if (num >= 4 &&
                   t4->tok == T_VAL &&
                   isbop(t3->tok) &&
                   t2->tok == T_VAL) {
                       /* binary operator */
                       if (looser(t1->tok, t3->tok)) {
                               t4->val = eval_bop(&t3->place,
                                                  t4->val, t3->tok, t2->val);
                               token_destroy(t2);
                               token_destroy(t3);
                               tokenarray_remove(&tokens, num-2);
                               tokenarray_remove(&tokens, num-3);
                               continue;
                       }
                       break;
               }

               t5 = (num >= 5) ? tokenarray_get(&tokens, num-5) : NULL;
               t6 = (num >= 6) ? tokenarray_get(&tokens, num-6) : NULL;

               if (num >= 6 &&
                   t6->tok == T_VAL &&
                   t5->tok == T_QUES &&
                   t4->tok == T_VAL &&
                   t3->tok == T_COLON &&
                   t2->tok == T_VAL &&
                   !isop(t1->tok)) {
                       /* conditional expression */
                       t6->val = t6->val ? t4->val : t2->val;
                       token_destroy(t2);
                       token_destroy(t3);
                       token_destroy(t4);
                       token_destroy(t5);
                       tokenarray_remove(&tokens, num-2);
                       tokenarray_remove(&tokens, num-3);
                       tokenarray_remove(&tokens, num-4);
                       tokenarray_remove(&tokens, num-5);
                       continue;
               }

               if (num >= 2 &&
                   t2->tok == T_LPAREN &&
                   t1->tok == T_RPAREN) {
                       complain(&t1->place, "Value expected within ()");
                       complain_fail();
                       t1->tok = T_VAL;
                       t1->val = 0;
                       token_destroy(t1);
                       tokenarray_remove(&tokens, num-1);
                       continue;
               }

               if (num >= 2 &&
                   t2->tok == T_VAL &&
                   t1->tok == T_VAL) {
                       complain(&t1->place, "Operator expected");
                       complain_fail();
                       token_destroy(t1);
                       tokenarray_remove(&tokens, num-1);
                       continue;
               }

               if (num >= 2 &&
                   isop(t2->tok) &&
                   t1->tok == T_EOF) {
                       complain(&t1->place, "Value expected after operator");
                       complain_fail();
                       token_destroy(t2);
                       tokenarray_remove(&tokens, num-2);
                       continue;
               }

               if (num == 2 &&
                   t2->tok == T_VAL &&
                   t1->tok == T_RPAREN) {
                       complain(&t1->place, "Excess right parenthesis");
                       complain_fail();
                       token_destroy(t1);
                       tokenarray_remove(&tokens, num-1);
                       continue;
               }

               if (num == 3 &&
                   t3->tok == T_LPAREN &&
                   t2->tok == T_VAL &&
                   t1->tok == T_EOF) {
                       complain(&t1->place, "Unclosed left parenthesis");
                       complain_fail();
                       token_destroy(t3);
                       tokenarray_remove(&tokens, num-3);
                       continue;
               }

               if (num == 2 &&
                   t2->tok == T_VAL &&
                   t1->tok == T_EOF) {
                       /* accepting state */
                       break;
               }

               if (num >= 1 &&
                   t1->tok == T_EOF) {
                       /* any other configuration at eof is an error */
                       complain(&t1->place, "Parse error");
                       complain_fail();
                       break;
               }

               /* otherwise, wait for more input */
               break;
       }
}

static
void
token(struct place *p, enum tokens tok, int val)
{
       struct token *t;

       t = token_create(p, tok, val);

       tokenarray_add(&tokens, t, NULL);
       tryreduce();
}

static
int
wordval(struct place *p, char *word)
{
       unsigned long val;
       char *t;

       if (word[0] >= '0' && word[0] <= '9') {
               errno = 0;
               val = strtoul(word, &t, 0);
               if (errno) {
                       complain(p, "Invalid integer constant");
                       complain_fail();
                       return 0;
               }
               while (*t == 'U' || *t == 'L') {
                       t++;
               }
               if (*t != '\0') {
                       complain(p, "Trailing garbage after integer constant");
                       complain_fail();
                       return 0;
               }
               if (val > INT_MAX) {
                       complain(p, "Integer constant too large");
                       complain_fail();
                       return INT_MAX;
               }
               return val;
       }

       /* if it's a symbol, warn and substitute 0. */
       if (warns.undef) {
               complain(p, "Warning: value of undefined symbol %s is 0",
                        word);
               if (mode.werror) {
                       complain_fail();
               }
       }
       debuglog(p, "Undefined symbol %s; substituting 0", word);
       return 0;
}

static
bool
check_word(struct place *p, char *expr, size_t pos, size_t *len_ret)
{
       size_t len;
       int val;
       char tmp;

       if (!strchr(alnum, expr[pos])) {
               return false;
       }
       len = strspn(expr + pos, alnum);
       tmp = expr[pos + len];
       expr[pos + len] = '\0';
       val = wordval(p, expr + pos);
       expr[pos + len] = tmp;
       token(p, T_VAL, val);
       *len_ret = len;
       return true;
}

static
bool
check_tokens_2(struct place *p, char *expr, size_t pos)
{
       unsigned i;

       for (i=0; i<num_tokens_2; i++) {
               if (expr[pos] == tokens_2[i].c1 &&
                   expr[pos+1] == tokens_2[i].c2) {
                       token(p, tokens_2[i].tok, 0);
                       return true;
               }
       }
       return false;
}

static
bool
check_tokens_1(struct place *p, char *expr, size_t pos)
{
       unsigned i;

       for (i=0; i<num_tokens_1; i++) {
               if (expr[pos] == tokens_1[i].c1) {
                       token(p, tokens_1[i].tok, 0);
                       return true;
               }
       }
       return false;
}

static
void
tokenize(struct place *p, char *expr)
{
       size_t pos, len;

       pos = 0;
       while (expr[pos] != '\0') {
               len = strspn(expr+pos, ws);
               pos += len;
               place_addcolumns(p, len);
               /* trailing whitespace is supposed to have been pruned */
               assert(expr[pos] != '\0');
               if (check_word(p, expr, pos, &len)) {
                       pos += len;
                       place_addcolumns(p, len);
                       continue;
               }
               if (check_tokens_2(p, expr, pos)) {
                       pos += 2;
                       place_addcolumns(p, 2);
                       continue;
               }
               if (check_tokens_1(p, expr, pos)) {
                       pos++;
                       place_addcolumns(p, 1);
                       continue;
               }
               complain(p, "Invalid character %u in #if-expression",
                        (unsigned char)expr[pos]);
               complain_fail();
               pos++;
               place_addcolumns(p, 1);
       }
       token(p, T_EOF, 0);
}

bool
eval(struct place *p, char *expr)
{
       struct token *t1, *t2;
       unsigned num;
       bool result;

#ifdef DEBUG
       fprintf(stderr, "eval: %s\n", expr);
#endif
       debuglog(p, "eval: %s", expr);

       tokenarray_init(&tokens);
       tokenize(p, expr);

       result = false;
       num = tokenarray_num(&tokens);
       if (num == 2) {
               t1 = tokenarray_get(&tokens, num-1);
               t2 = tokenarray_get(&tokens, num-2);
               if (t2->tok == T_VAL &&
                   t1->tok == T_EOF) {
                       result = t2->val != 0;
               }
       }

       tokenarray_destroyall(&tokens);
       tokenarray_cleanup(&tokens);
       return result;
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.