From 15a32f06839819cbbf6f40dccc5189c66379bcc0 Mon Sep 17 00:00:00 2001
From: Ori Bernstein <ori@eigenstate.org>
Date: Sun, 19 Apr 2020 11:15:13 -0700
Subject: [PATCH] fix cpp operator associativity

We used to treat all operators as right associative,
which means that we would evaluate them incorrecty.
For example, '2 - 1 + 1' would evaluate as '2 - (1 + 2)',
instead of '(2 - 1) + 1'.

This adds an assoc parameter to struct pri, and then uses
it to decide how to evaluate operators.
---
 sys/src/cmd/cpp/eval.c | 114 ++++++++++++++++-------------------------
 1 file changed, 43 insertions(+), 71 deletions(-)

diff --git a/sys/src/cmd/cpp/eval.c b/sys/src/cmd/cpp/eval.c
index 83d12e00b..8a6fe0645 100644
--- a/sys/src/cmd/cpp/eval.c
+++ b/sys/src/cmd/cpp/eval.c
@@ -15,80 +15,52 @@ struct value {
 };
 
 /* conversion types */
-#define	RELAT	1
-#define	ARITH	2
-#define	LOGIC	3
-#define	SPCL	4
-#define	SHIFT	5
-#define	UNARY	6
+enum {
+	NONE,
+	RELAT,
+	ARITH,
+	LOGIC,
+	SPCL,
+	SHIFT,
+	UNARY
+};
 
 /* operator priority, arity, and conversion type, indexed by tokentype */
 const struct pri {
 	char	pri;
+	char	assoc;
 	char	arity;
 	char	ctype;
 } priority[] = {
-	[END]		{ 0, 0, 0 },
-	[UNCLASS]	{ 0, 0, 0 },
-	[NAME]		{ 0, 0, 0 },
-	[NUMBER]	{ 0, 0, 0 },
-	[STRING]	{ 0, 0, 0 },
-	[CCON]		{ 0, 0, 0 },
-	[NL]		{ 0, 0, 0 },
-	[WS]		{ 0, 0, 0 },
-	[DSHARP]	{ 0, 0, 0 },
-	[EQ]		{ 11, 2, RELAT },
-	[NEQ]		{ 11, 2, RELAT },
-	[LEQ]		{ 12, 2, RELAT },
-	[GEQ]		{ 12, 2, RELAT },
-	[LSH]		{ 13, 2, SHIFT },
-	[RSH]		{ 13, 2, SHIFT },
-	[LAND]		{ 7, 2, LOGIC },
-	[LOR]		{ 6, 2, LOGIC },
-	[PPLUS]		{ 0, 0, 0 },
-	[MMINUS]	{ 0, 0, 0 },
-	[ARROW]		{ 0, 0, 0 },
-	[SBRA]		{ 0, 0, 0 },
-	[SKET]		{ 0, 0, 0 },
-	[LP]		{ 3, 0, 0 },
-	[RP]		{ 3, 0, 0 },
-	[DOT]		{ 0, 0, 0 },
-	[AND]		{ 10, 2, ARITH },
-	[STAR]		{ 15, 2, ARITH },
-	[PLUS]		{ 14, 2, ARITH },
-	[MINUS]		{ 14, 2, ARITH },
-	[TILDE]		{ 16, 1, UNARY },
-	[NOT]		{ 16, 1, UNARY },
-	[SLASH]		{ 15, 2, ARITH },
-	[PCT]		{ 15, 2, ARITH },
-	[LT]		{ 12, 2, RELAT },
-	[GT]		{ 12, 2, RELAT },
-	[CIRC]		{ 9, 2, ARITH },
-	[OR]		{ 8, 2, ARITH },
-	[QUEST]		{ 5, 2, SPCL },
-	[COLON]		{ 5, 2, SPCL },
-	[ASGN]		{ 0, 0, 0 },
-	[COMMA]		{ 4, 2, 0 },
-	[XCOMMA]	{ 4, 2, 0 },
-	[SHARP]		{ 0, 0, 0 },
-	[SEMIC]		{ 0, 0, 0 },
-	[CBRA]		{ 0, 0, 0 },
-	[CKET]		{ 0, 0, 0 },
-	[ASPLUS]	{ 0, 0, 0 },
- 	[ASMINUS]	{ 0, 0, 0 },
- 	[ASSTAR]	{ 0, 0, 0 },
- 	[ASSLASH]	{ 0, 0, 0 },
- 	[ASPCT]		{ 0, 0, 0 },
- 	[ASCIRC]	{ 0, 0, 0 },
- 	[ASLSH]		{ 0, 0, 0 },
-	[ASRSH]		{ 0, 0, 0 },
- 	[ASOR]		{ 0, 0, 0 },
- 	[ASAND]		{ 0, 0, 0 },
-	[ELLIPS]	{ 0, 0, 0 },
-	[DSHARP1]	{ 0, 0, 0 },
-	[NAME1]		{ 0, 0, 0 },
-	[DEFINED]	{ 16, 1, UNARY },
-	[UMINUS]	{ 16, 0, UNARY },
+	[END]		{ 0, 0, 0, 0 },
+	[EQ]		{ 11, 0, 2, RELAT },
+	[NEQ]		{ 11, 0, 2, RELAT },
+	[LEQ]		{ 12, 0, 2, RELAT },
+	[GEQ]		{ 12, 0, 2, RELAT },
+	[LSH]		{ 13, 0, 2, SHIFT },
+	[RSH]		{ 13, 0, 2, SHIFT },
+	[LAND]		{ 7, 0, 2, LOGIC },
+	[LOR]		{ 6, 0, 2, LOGIC },
+	[LP]		{ 3, 1, 0, 0 },
+	[RP]		{ 3, 1, 0, 0 },
+	[AND]		{ 10, 0, 2, ARITH },
+	[STAR]		{ 15, 0, 2, ARITH },
+	[PLUS]		{ 14, 0, 2, ARITH },
+	[MINUS]		{ 14, 0, 2, ARITH },
+	[TILDE]		{ 16, 0, 1, UNARY },
+	[NOT]		{ 16, 0, 1, UNARY },
+	[SLASH]		{ 15, 0, 2, ARITH },
+	[PCT]		{ 15, 0, 2, ARITH },
+	[LT]		{ 12, 0, 2, RELAT },
+	[GT]		{ 12, 0, 2, RELAT },
+	[CIRC]		{ 9, 0, 2, ARITH },
+	[OR]		{ 8, 0, 2, ARITH },
+	[QUEST]		{ 5, 1, 2, SPCL },
+	[COLON]		{ 5, 1, 2, SPCL },
+	[COMMA]		{ 4, 0, 2, 0 },
+	[XCOMMA]	{ 4, 0, 2, 0 },
+	[DEFINED]	{ 16, 0, 1, UNARY },
+	[UMINUS]	{ 16, 0, 0, UNARY },
 };
 
 int	evalop(struct pri);
@@ -98,6 +70,7 @@ enum toktype ops[NSTAK], *op;
 
 /*
  * Evaluate an #if #elif #ifdef #ifndef line.  trp->tp points to the keyword.
+ * Using shunting yard algorithm.
  */
 vlong
 eval(Tokenrow *trp, int kw)
@@ -121,7 +94,6 @@ eval(Tokenrow *trp, int kw)
 	kwdefined->val = NAME;
 	vp = vals;
 	op = ops;
-	*op++ = END;
 	for (rand=0, tp = trp->bp+ntok; tp < trp->lp; tp++) {
 		switch(tp->type) {
 		case WS:
@@ -211,7 +183,7 @@ eval(Tokenrow *trp, int kw)
 		goto syntax;
 	if (evalop(priority[END])!=0)
 		return 0;
-	if (op!=&ops[1] || vp!=&vals[1]) {
+	if (op!=ops || vp!=&vals[1]) {
 		error(ERROR, "Botch in #if/#elif");
 		return 0;
 	}
@@ -219,7 +191,7 @@ eval(Tokenrow *trp, int kw)
 		error(ERROR, "Undefined expression value");
 	return vals[0].val;
 syntax:
-	error(ERROR, "Syntax error in #if/#elif");
+	error(ERROR, "Syntax xx error in #if/#elif");
 	return 0;
 fullstakdeveloper:
 	error(ERROR, "Out of stack space evaluating #if");
@@ -235,7 +207,7 @@ evalop(struct pri pri)
 
 	rv2=0;
 	rtype=0;
-	while (pri.pri < priority[op[-1]].pri) {
+	while (op != ops && pri.pri + pri.assoc <= priority[op[-1]].pri) {
 		oper = *--op;
 		if (priority[oper].arity==2) {
 			v2 = *--vp;
-- 
2.44.0