Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	libexec/tradcpp/eval.c	Lines:	0	319	0.0 %
Date:	2017-11-13	Branches:	0	265	0.0 %


/*-
 * 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();
		}
	}
	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;
		p->column += len;
		/* trailing whitespace is supposed to have been pruned */
		assert(expr[pos] != '\0');
		if (check_word(p, expr, pos, &len)) {
			pos += len;
			p->column += len;
			continue;
		}
		if (check_tokens_2(p, expr, pos)) {
			pos += 2;
			p->column += 2;
			continue;
		}
		if (check_tokens_1(p, expr, pos)) {
			pos++;
			p->column++;
			continue;
		}
		complain(p, "Invalid character %u in #if-expression",
			 (unsigned char)expr[pos]);
		complain_fail();
		pos++;
		p->column++;
	}
	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

	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;
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/*-
2			* Copyright (c) 2010 The NetBSD Foundation, Inc.
3			* All rights reserved.
4			*
5			* This code is derived from software contributed to The NetBSD Foundation
6			* by David A. Holland.
7			*
8			* Redistribution and use in source and binary forms, with or without
9			* modification, are permitted provided that the following conditions
10			* are met:
11			* 1. Redistributions of source code must retain the above copyright
12			* notice, this list of conditions and the following disclaimer.
13			* 2. Redistributions in binary form must reproduce the above copyright
14			* notice, this list of conditions and the following disclaimer in the
15			* documentation and/or other materials provided with the distribution.
16			*
17			* THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
18			* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
19			* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20			* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
21			* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22			* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23			* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24			* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25			* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26			* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27			* POSSIBILITY OF SUCH DAMAGE.
28			*/
29
30			#include <stdlib.h>
31			#include <string.h>
32			#include <limits.h>
33			#include <errno.h>
34
35			//#define DEBUG
36			#ifdef DEBUG
37			#include <stdio.h>
38			#endif
39
40			#include "utils.h"
41			#include "array.h"
42			#include "mode.h"
43			#include "place.h"
44			#include "eval.h"
45
46			/*
47			* e ::=
48			* e1 ? e2 : e3
49			* e1 \|\| e2
50			* e1 && e2
51			* e1 \| e2
52			* e1 ^ e2
53			* e1 & e2
54			* e1 == e2 \| e1 != e2
55			* e1 < e2 \| e1 <= e2 \| e1 > e2 \| e1 >= e2
56			* e1 << e2 \| e1 >> e2
57			* e1 + e2 \| e1 - e2
58			* e1 * e2 \| e1 / e2 \| e1 % e2
59			* !e \| ~e \| -e \| +e
60			* ( e ) \| ident
61			*/
62
63			enum tokens {
64			T_EOF, /* end of input */
65			T_VAL, /* value */
66			T_LPAREN, /* parens */
67			T_RPAREN,
68			T_PIPEPIPE, /* operators */
69			T_AMPAMP,
70			T_EQEQ,
71			T_BANGEQ,
72			T_LTEQ,
73			T_GTEQ,
74			T_LTLT,
75			T_GTGT,
76			T_QUES,
77			T_COLON,
78			T_PIPE,
79			T_CARET,
80			T_AMP,
81			T_LT,
82			T_GT,
83			T_PLUS,
84			T_MINUS,
85			T_STAR,
86			T_SLASH,
87			T_PCT,
88			T_BANG,
89			T_TILDE,
90			};
91
92			static const struct {
93			char c1, c2;
94			enum tokens tok;
95			} tokens_2[] = {
96			{ '\|', '\|', T_PIPEPIPE },
97			{ '&', '&', T_AMPAMP },
98			{ '=', '=', T_EQEQ },
99			{ '!', '=', T_BANGEQ },
100			{ '<', '=', T_LTEQ },
101			{ '>', '=', T_GTEQ },
102			{ '<', '<', T_LTLT },
103			{ '>', '>', T_GTGT },
104			};
105			static const unsigned num_tokens_2 = HOWMANY(tokens_2);
106
107			static const struct {
108			char c1;
109			enum tokens tok;
110			} tokens_1[] = {
111			{ '?', T_QUES },
112			{ ':', T_COLON },
113			{ '\|', T_PIPE },
114			{ '^', T_CARET },
115			{ '&', T_AMP },
116			{ '<', T_LT },
117			{ '>', T_GT },
118			{ '+', T_PLUS },
119			{ '-', T_MINUS },
120			{ '*', T_STAR },
121			{ '/', T_SLASH },
122			{ '%', T_PCT },
123			{ '!', T_BANG },
124			{ '~', T_TILDE },
125			{ '(', T_LPAREN },
126			{ ')', T_RPAREN },
127			};
128			static const unsigned num_tokens_1 = HOWMANY(tokens_1);
129
130			struct token {
131			struct place place;
132			enum tokens tok;
133			int val;
134			};
135			DECLARRAY(token, static UNUSED);
136			DEFARRAY(token, static);
137
138			static struct tokenarray tokens;
139
140			static
141			struct token *
142			token_create(const struct place *p, enum tokens tok, int val)
143			{
144			struct token *t;
145
146			t = domalloc(sizeof(*t));
147			t->place = *p;
148			t->tok = tok;
149			t->val = val;
150			return t;
151			}
152
153			static
154			void
155			token_destroy(struct token *t)
156			{
157			dofree(t, sizeof(*t));
158			}
159
160			DESTROYALL_ARRAY(token, );
161
162			#ifdef DEBUG
163			static
164			void
165			printtokens(void)
166			{
167			unsigned i, num;
168			struct token *t;
169
170			fprintf(stderr, "tokens:");
171			num = tokenarray_num(&tokens);
172			for (i=0; i<num; i++) {
173			t = tokenarray_get(&tokens, i);
174			switch (t->tok) {
175			case T_EOF: fprintf(stderr, " <eof>"); break;
176			case T_VAL: fprintf(stderr, " %d", t->val); break;
177			case T_LPAREN: fprintf(stderr, " ("); break;
178			case T_RPAREN: fprintf(stderr, " )"); break;
179			case T_PIPEPIPE: fprintf(stderr, " \|\|"); break;
180			case T_AMPAMP: fprintf(stderr, " &&"); break;
181			case T_EQEQ: fprintf(stderr, " =="); break;
182			case T_BANGEQ: fprintf(stderr, " !="); break;
183			case T_LTEQ: fprintf(stderr, " <="); break;
184			case T_GTEQ: fprintf(stderr, " >="); break;
185			case T_LTLT: fprintf(stderr, " <<"); break;
186			case T_GTGT: fprintf(stderr, " >>"); break;
187			case T_QUES: fprintf(stderr, " ?"); break;
188			case T_COLON: fprintf(stderr, " :"); break;
189			case T_PIPE: fprintf(stderr, " \|"); break;
190			case T_CARET: fprintf(stderr, " ^"); break;
191			case T_AMP: fprintf(stderr, " &"); break;
192			case T_LT: fprintf(stderr, " <"); break;
193			case T_GT: fprintf(stderr, " >"); break;
194			case T_PLUS: fprintf(stderr, " +"); break;
195			case T_MINUS: fprintf(stderr, " -"); break;
196			case T_STAR: fprintf(stderr, " *"); break;
197			case T_SLASH: fprintf(stderr, " /"); break;
198			case T_PCT: fprintf(stderr, " %%"); break;
199			case T_BANG: fprintf(stderr, " !"); break;
200			case T_TILDE: fprintf(stderr, " ~"); break;
201			}
202			}
203			fprintf(stderr, "\n");
204			}
205			#endif
206
207			static
208			bool
209			isuop(enum tokens tok)
210			{
211			switch (tok) {
212			case T_BANG:
213			case T_TILDE:
214			case T_MINUS:
215			case T_PLUS:
216			return true;
217			default:
218			break;
219			}
220			return false;
221			}
222
223			static
224			bool
225			isbop(enum tokens tok)
226			{
227			switch (tok) {
228			case T_EOF:
229			case T_VAL:
230			case T_LPAREN:
231			case T_RPAREN:
232			case T_COLON:
233			case T_QUES:
234			case T_BANG:
235			case T_TILDE:
236			return false;
237			default:
238			break;
239			}
240			return true;
241			}
242
243			static
244			bool
245			isop(enum tokens tok)
246			{
247			switch (tok) {
248			case T_EOF:
249			case T_VAL:
250			case T_LPAREN:
251			case T_RPAREN:
252			return false;
253			default:
254			break;
255			}
256			return true;
257			}
258
259			static
260			int
261			getprec(enum tokens tok)
262			{
263			switch (tok) {
264			case T_BANG: case T_TILDE: return -1;
265			case T_STAR: case T_SLASH: case T_PCT: return 0;
266			case T_PLUS: case T_MINUS: return 1;
267			case T_LTLT: case T_GTGT: return 2;
268			case T_LT: case T_LTEQ: case T_GT: case T_GTEQ: return 3;
269			case T_EQEQ: case T_BANGEQ: return 4;
270			case T_AMP: return 5;
271			case T_CARET: return 6;
272			case T_PIPE: return 7;
273			case T_AMPAMP: return 8;
274			case T_PIPEPIPE: return 9;
275			default: break;
276			}
277			return 10;
278			}
279
280			static
281			bool
282			looser(enum tokens t1, enum tokens t2)
283			{
284			return getprec(t1) >= getprec(t2);
285			}
286
287			static
288			int
289			eval_uop(enum tokens op, int val)
290			{
291			switch (op) {
292			case T_BANG: val = !val; break;
293			case T_TILDE: val = (int)~(unsigned)val; break;
294			case T_MINUS: val = -val; break;
295			case T_PLUS: break;
296			default: assert(0); break;
297			}
298			return val;
299			}
300
301			static
302			int
303			eval_bop(struct place *p, int lv, enum tokens op, int rv)
304			{
305			unsigned mask;
306
307			switch (op) {
308			case T_PIPEPIPE: return lv \|\| rv;
309			case T_AMPAMP: return lv && rv;
310			case T_PIPE: return (int)((unsigned)lv \| (unsigned)rv);
311			case T_CARET: return (int)((unsigned)lv ^ (unsigned)rv);
312			case T_AMP: return (int)((unsigned)lv & (unsigned)rv);
313			case T_EQEQ: return lv == rv;
314			case T_BANGEQ: return lv != rv;
315			case T_LT: return lv < rv;
316			case T_GT: return lv > rv;
317			case T_LTEQ: return lv <= rv;
318			case T_GTEQ: return lv >= rv;
319
320			case T_LTLT:
321			case T_GTGT:
322			if (rv < 0) {
323			complain(p, "Negative bit-shift");
324			complain_fail();
325			rv = 0;
326			}
327			if ((unsigned)rv >= CHAR_BIT * sizeof(unsigned)) {
328			complain(p, "Bit-shift farther than type width");
329			complain_fail();
330			rv = 0;
331			}
332			if (op == T_LTLT) {
333			return (int)((unsigned)lv << (unsigned)rv);
334			}
335			mask = ((unsigned)-1) << (CHAR_BIT * sizeof(unsigned) - rv);
336			lv = (int)(((unsigned)lv >> (unsigned)rv) \| mask);
337			return lv;
338
339			case T_MINUS:
340			if (rv == INT_MIN) {
341			if (lv == INT_MIN) {
342			return 0;
343			}
344			lv--;
345			rv++;
346			}
347			rv = -rv;
348			/* FALLTHROUGH */
349			case T_PLUS:
350			if (rv > 0 && lv > (INT_MAX - rv)) {
351			complain(p, "Integer overflow");
352			complain_fail();
353			return INT_MAX;
354			}
355			if (rv < 0 && lv < (INT_MIN - rv)) {
356			complain(p, "Integer underflow");
357			complain_fail();
358			return INT_MIN;
359			}
360			return lv + rv;
361
362			case T_STAR:
363			if (rv == 0) {
364			return 0;
365			}
366			if (rv == 1) {
367			return lv;
368			}
369			if (rv == -1 && lv == INT_MIN) {
370			lv++;
371			lv = -lv;
372			if (lv == INT_MAX) {
373			complain(p, "Integer overflow");
374			complain_fail();
375			return INT_MAX;
376			}
377			lv++;
378			return lv;
379			}
380			if (lv == INT_MIN && rv < 0) {
381			complain(p, "Integer overflow");
382			complain_fail();
383			return INT_MAX;
384			}
385			if (lv == INT_MIN && rv > 0) {
386			complain(p, "Integer underflow");
387			complain_fail();
388			return INT_MIN;
389			}
390			if (rv < 0) {
391			rv = -rv;
392			lv = -lv;
393			}
394			if (lv > 0 && lv > INT_MAX / rv) {
395			complain(p, "Integer overflow");
396			complain_fail();
397			return INT_MAX;
398			}
399			if (lv < 0 && lv < INT_MIN / rv) {
400			complain(p, "Integer underflow");
401			complain_fail();
402			return INT_MIN;
403			}
404			return lv * rv;
405
406			case T_SLASH:
407			if (rv == 0) {
408			complain(p, "Division by zero");
409			complain_fail();
410			return 0;
411			}
412			return lv / rv;
413
414			case T_PCT:
415			if (rv == 0) {
416			complain(p, "Modulus by zero");
417			complain_fail();
418			return 0;
419			}
420			return lv % rv;
421
422			default: assert(0); break;
423			}
424			return 0;
425			}
426
427			static
428			void
429			tryreduce(void)
430			{
431			unsigned num;
432			struct token t1, t2, t3, t4, t5, t6;
433
434			while (1) {
435			#ifdef DEBUG
436			printtokens();
437			#endif
438			num = tokenarray_num(&tokens);
439			t1 = (num >= 1) ? tokenarray_get(&tokens, num-1) : NULL;
440			t2 = (num >= 2) ? tokenarray_get(&tokens, num-2) : NULL;
441			t3 = (num >= 3) ? tokenarray_get(&tokens, num-3) : NULL;
442
443			if (num >= 3 &&
444			t3->tok == T_LPAREN &&
445			t2->tok == T_VAL &&
446			t1->tok == T_RPAREN) {
447			/* (x) -> x */
448			t2->place = t3->place;
449			token_destroy(t1);
450			token_destroy(t3);
451			tokenarray_remove(&tokens, num-1);
452			tokenarray_remove(&tokens, num-3);
453			continue;
454			}
455
456			if (num >= 2 &&
457			(num == 2 \|\| isop(t3->tok) \|\| t3->tok == T_LPAREN) &&
458			isuop(t2->tok) &&
459			t1->tok == T_VAL) {
460			/* unary operator */
461			t1->val = eval_uop(t2->tok, t1->val);
462			t1->place = t2->place;
463			token_destroy(t2);
464			tokenarray_remove(&tokens, num-2);
465			continue;
466			}
467			if (num >= 2 &&
468			(num == 2 \|\| isop(t3->tok) \|\| t3->tok == T_LPAREN) &&
469			t2->tok != T_LPAREN && t2->tok != T_VAL &&
470			t1->tok == T_VAL) {
471			complain(&t2->place, "Invalid unary operator");
472			complain_fail();
473			token_destroy(t2);
474			tokenarray_remove(&tokens, num-2);
475			continue;
476			}
477
478
479			t4 = (num >= 4) ? tokenarray_get(&tokens, num-4) : NULL;
480
481			if (num >= 4 &&
482			t4->tok == T_VAL &&
483			isbop(t3->tok) &&
484			t2->tok == T_VAL) {
485			/* binary operator */
486			if (looser(t1->tok, t3->tok)) {
487			t4->val = eval_bop(&t3->place,
488			t4->val, t3->tok, t2->val);
489			token_destroy(t2);
490			token_destroy(t3);
491			tokenarray_remove(&tokens, num-2);
492			tokenarray_remove(&tokens, num-3);
493			continue;
494			}
495			break;
496			}
497
498			t5 = (num >= 5) ? tokenarray_get(&tokens, num-5) : NULL;
499			t6 = (num >= 6) ? tokenarray_get(&tokens, num-6) : NULL;
500
501			if (num >= 6 &&
502			t6->tok == T_VAL &&
503			t5->tok == T_QUES &&
504			t4->tok == T_VAL &&
505			t3->tok == T_COLON &&
506			t2->tok == T_VAL &&
507			!isop(t1->tok)) {
508			/* conditional expression */
509			t6->val = t6->val ? t4->val : t2->val;
510			token_destroy(t2);
511			token_destroy(t3);
512			token_destroy(t4);
513			token_destroy(t5);
514			tokenarray_remove(&tokens, num-2);
515			tokenarray_remove(&tokens, num-3);
516			tokenarray_remove(&tokens, num-4);
517			tokenarray_remove(&tokens, num-5);
518			continue;
519			}
520
521			if (num >= 2 &&
522			t2->tok == T_LPAREN &&
523			t1->tok == T_RPAREN) {
524			complain(&t1->place, "Value expected within ()");
525			complain_fail();
526			t1->tok = T_VAL;
527			t1->val = 0;
528			token_destroy(t1);
529			tokenarray_remove(&tokens, num-1);
530			continue;
531			}
532
533			if (num >= 2 &&
534			t2->tok == T_VAL &&
535			t1->tok == T_VAL) {
536			complain(&t1->place, "Operator expected");
537			complain_fail();
538			token_destroy(t1);
539			tokenarray_remove(&tokens, num-1);
540			continue;
541			}
542
543			if (num >= 2 &&
544			isop(t2->tok) &&
545			t1->tok == T_EOF) {
546			complain(&t1->place, "Value expected after operator");
547			complain_fail();
548			token_destroy(t2);
549			tokenarray_remove(&tokens, num-2);
550			continue;
551			}
552
553			if (num == 2 &&
554			t2->tok == T_VAL &&
555			t1->tok == T_RPAREN) {
556			complain(&t1->place, "Excess right parenthesis");
557			complain_fail();
558			token_destroy(t1);
559			tokenarray_remove(&tokens, num-1);
560			continue;
561			}
562
563			if (num == 3 &&
564			t3->tok == T_LPAREN &&
565			t2->tok == T_VAL &&
566			t1->tok == T_EOF) {
567			complain(&t1->place, "Unclosed left parenthesis");
568			complain_fail();
569			token_destroy(t3);
570			tokenarray_remove(&tokens, num-3);
571			continue;
572			}
573
574			if (num == 2 &&
575			t2->tok == T_VAL &&
576			t1->tok == T_EOF) {
577			/* accepting state */
578			break;
579			}
580
581			if (num >= 1 &&
582			t1->tok == T_EOF) {
583			/* any other configuration at eof is an error */
584			complain(&t1->place, "Parse error");
585			complain_fail();
586			break;
587			}
588
589			/* otherwise, wait for more input */
590			break;
591			}
592			}
593
594			static
595			void
596			token(struct place *p, enum tokens tok, int val)
597			{
598			struct token *t;
599
600			t = token_create(p, tok, val);
601
602			tokenarray_add(&tokens, t, NULL);
603			tryreduce();
604			}
605
606			static
607			int
608			wordval(struct place p, char word)
609			{
610			unsigned long val;
611			char *t;
612
613			if (word[0] >= '0' && word[0] <= '9') {
614			errno = 0;
615			val = strtoul(word, &t, 0);
616			if (errno) {
617			complain(p, "Invalid integer constant");
618			complain_fail();
619			return 0;
620			}
621			while (t == 'U' \|\| t == 'L') {
622			t++;
623			}
624			if (*t != '\0') {
625			complain(p, "Trailing garbage after integer constant");
626			complain_fail();
627			return 0;
628			}
629			if (val > INT_MAX) {
630			complain(p, "Integer constant too large");
631			complain_fail();
632			return INT_MAX;
633			}
634			return val;
635			}
636
637			/* if it's a symbol, warn and substitute 0. */
638			if (warns.undef) {
639			complain(p, "Warning: value of undefined symbol %s is 0",
640			word);
641			if (mode.werror) {
642			complain_fail();
643			}
644			}
645			return 0;
646			}
647
648			static
649			bool
650			check_word(struct place p, char expr, size_t pos, size_t *len_ret)
651			{
652			size_t len;
653			int val;
654			char tmp;
655
656			if (!strchr(alnum, expr[pos])) {
657			return false;
658			}
659			len = strspn(expr + pos, alnum);
660			tmp = expr[pos + len];
661			expr[pos + len] = '\0';
662			val = wordval(p, expr + pos);
663			expr[pos + len] = tmp;
664			token(p, T_VAL, val);
665			*len_ret = len;
666			return true;
667			}
668
669			static
670			bool
671			check_tokens_2(struct place p, char expr, size_t pos)
672			{
673			unsigned i;
674
675			for (i=0; i<num_tokens_2; i++) {
676			if (expr[pos] == tokens_2[i].c1 &&
677			expr[pos+1] == tokens_2[i].c2) {
678			token(p, tokens_2[i].tok, 0);
679			return true;
680			}
681			}
682			return false;
683			}
684
685			static
686			bool
687			check_tokens_1(struct place p, char expr, size_t pos)
688			{
689			unsigned i;
690
691			for (i=0; i<num_tokens_1; i++) {
692			if (expr[pos] == tokens_1[i].c1) {
693			token(p, tokens_1[i].tok, 0);
694			return true;
695			}
696			}
697			return false;
698			}
699
700			static
701			void
702			tokenize(struct place p, char expr)
703			{
704			size_t pos, len;
705
706			pos = 0;
707			while (expr[pos] != '\0') {
708			len = strspn(expr+pos, ws);
709			pos += len;
710			p->column += len;
711			/* trailing whitespace is supposed to have been pruned */
712			assert(expr[pos] != '\0');
713			if (check_word(p, expr, pos, &len)) {
714			pos += len;
715			p->column += len;
716			continue;
717			}
718			if (check_tokens_2(p, expr, pos)) {
719			pos += 2;
720			p->column += 2;
721			continue;
722			}
723			if (check_tokens_1(p, expr, pos)) {
724			pos++;
725			p->column++;
726			continue;
727			}
728			complain(p, "Invalid character %u in #if-expression",
729			(unsigned char)expr[pos]);
730			complain_fail();
731			pos++;
732			p->column++;
733			}
734			token(p, T_EOF, 0);
735			}
736
737			bool
738			eval(struct place p, char expr)
739			{
740			struct token t1, t2;
741			unsigned num;
742			bool result;
743
744			#ifdef DEBUG
745			fprintf(stderr, "eval: %s\n", expr);
746			#endif
747
748			tokenarray_init(&tokens);
749			tokenize(p, expr);
750
751			result = false;
752			num = tokenarray_num(&tokens);
753			if (num == 2) {
754			t1 = tokenarray_get(&tokens, num-1);
755			t2 = tokenarray_get(&tokens, num-2);
756			if (t2->tok == T_VAL &&
757			t1->tok == T_EOF) {
758			result = t2->val != 0;
759			}
760			}
761
762			tokenarray_destroyall(&tokens);
763			tokenarray_cleanup(&tokens);
764			return result;
765			}