Rewrite grammar to implement operator precedence without using %right or %prec.

Arithmetic operator should now behave as expeted and tests can now be written
without superfluous parenthesis, for example:

syscall:select:entry
/($1 == 0) || (pid == $1)/
{
}

Can now be written:

syscall:select:entry
/$1 == 0 || pid == $1/
{
}

While here improve filter debugging support.

5 files changed, 179 insertions, 90 deletions

diff --git a/usr.sbin/btrace/TODO b/usr.sbin/btrace/TODO
index c38454e7afe..aad8a6657f4 100644
--- a/usr.sbin/btrace/TODO
+++ b/usr.sbin/btrace/TODO
@@ -12,6 +12,5 @@ Missing language features:
 
 Improvements:
 
-- implement arithmetic operator precedence
 - rewrite stmt_printf() to not use strings internally
 - look at collision in map hash
diff --git a/usr.sbin/btrace/bt_parse.y b/usr.sbin/btrace/bt_parse.y
index b079c8b4a17..2a7ac72f38b 100644
--- a/usr.sbin/btrace/bt_parse.y
+++ b/usr.sbin/btrace/bt_parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bt_parse.y,v 1.35 2021/08/30 11:57:45 mpi Exp $	*/
+/*	$OpenBSD: bt_parse.y,v 1.36 2021/08/31 08:39:26 mpi Exp $	*/
 
 /*
  * Copyright (c) 2019-2021 Martin Pieuchot <mpi@openbsd.org>
@@ -56,6 +56,9 @@ SLIST_HEAD(, bt_var)	 g_variables;
 /* List of local variables, cleaned for each new rule. */
 SLIST_HEAD(, bt_var)	l_variables;
 
+struct bt_arg 		g_nullba = BA_INITIALIZER(0, B_AT_LONG);
+struct bt_arg		g_maxba = BA_INITIALIZER(LONG_MAX, B_AT_LONG);
+
 struct bt_rule	*br_new(struct bt_probe *, struct bt_filter *, struct bt_stmt *,
 		     enum bt_rtype);
 struct bt_probe	*bp_new(const char *, const char *, const char *, int32_t);
@@ -124,13 +127,8 @@ static int pflag;
 %type	<v.probe>	probe pname
 %type	<v.filter>	filter
 %type	<v.stmt>	action stmt stmtlist
-%type	<v.arg>		expr vargs mentry mexpr pargs term
-
-%right	'='
-%nonassoc OP_EQ OP_NE OP_LE OP_LT OP_GE OP_GT OP_LAND OP_LOR
-%left	'&' '|'
-%left	'+' '-'
-%left	'/' '*'
+%type	<v.arg>		pat vargs mentry mpat pargs
+%type	<v.arg>		expr term fterm factor
 %%
 
 grammar	: /* empty */
@@ -165,64 +163,80 @@ lvar	: '$' STRING			{ $$ = $2; }
 mentry	: gvar '[' vargs ']'		{ $$ = bm_find($1, $3); }
 	;
 
-mexpr	: MOP0 '(' ')'			{ $$ = ba_new(NULL, $1); }
-	| MOP1 '(' expr ')'		{ $$ = ba_new($3, $1); }
+mpat	: MOP0 '(' ')'			{ $$ = ba_new(NULL, $1); }
+	| MOP1 '(' pat ')'		{ $$ = ba_new($3, $1); }
+	| pat
+	;
+
+pat	: CSTRING			{ $$ = ba_new($1, B_AT_STR); }
 	| expr
 	;
 
-expr	: CSTRING			{ $$ = ba_new($1, B_AT_STR); }
+filter	: /* empty */			{ $$ = NULL; }
+	| '/' expr ENDFILT		{ $$ = bc_new(NULL, B_AT_OP_NE, $2); }
+	;
+
+/*
+ * Give higher precedence to:
+ *  1. && and ||
+ *  2. ==, !=, <<, <, >=, >, +, =, &, ^, |
+ *  3. * and /
+ */
+expr	: expr OP_LAND term	{ $$ = ba_op(B_AT_OP_LAND, $1, $3); }
+	| expr OP_LOR term	{ $$ = ba_op(B_AT_OP_LOR, $1, $3); }
 	| term
 	;
 
-filter	: /* empty */			{ $$ = NULL; }
-	| '/' term ENDFILT		{ $$ = bc_new(NULL, B_AT_OP_NE, $2); }
+term	: term OP_EQ fterm	{ $$ = ba_op(B_AT_OP_EQ, $1, $3); }
+	| term OP_NE fterm	{ $$ = ba_op(B_AT_OP_NE, $1, $3); }
+	| term OP_LE fterm	{ $$ = ba_op(B_AT_OP_LE, $1, $3); }
+	| term OP_LT fterm	{ $$ = ba_op(B_AT_OP_LT, $1, $3); }
+	| term OP_GE fterm	{ $$ = ba_op(B_AT_OP_GE, $1, $3); }
+	| term OP_GT fterm	{ $$ = ba_op(B_AT_OP_GT, $1, $3); }
+	| term '+' fterm	{ $$ = ba_op(B_AT_OP_PLUS, $1, $3); }
+	| term '-' fterm	{ $$ = ba_op(B_AT_OP_MINUS, $1, $3); }
+	| term '&' fterm	{ $$ = ba_op(B_AT_OP_BAND, $1, $3); }
+	| term '^' fterm	{ $$ = ba_op(B_AT_OP_XOR, $1, $3); }
+	| term '|' fterm	{ $$ = ba_op(B_AT_OP_BOR, $1, $3); }
+	| fterm
+	;
+
+fterm	: fterm '*' factor	{ $$ = ba_op(B_AT_OP_MULT, $1, $3); }
+	| fterm '/' factor	{ $$ = ba_op(B_AT_OP_DIVIDE, $1, $3); }
+	| factor
 	;
 
-term	: '(' term ')'			{ $$ = $2; }
-	| term OP_EQ term		{ $$ = ba_op(B_AT_OP_EQ, $1, $3); }
-	| term OP_NE term		{ $$ = ba_op(B_AT_OP_NE, $1, $3); }
-	| term OP_LE term		{ $$ = ba_op(B_AT_OP_LE, $1, $3); }
-	| term OP_LT term		{ $$ = ba_op(B_AT_OP_LT, $1, $3); }
-	| term OP_GE term		{ $$ = ba_op(B_AT_OP_GE, $1, $3); }
-	| term OP_GT term		{ $$ = ba_op(B_AT_OP_GT, $1, $3); }
-	| term OP_LAND term		{ $$ = ba_op(B_AT_OP_LAND, $1, $3); }
-	| term OP_LOR term		{ $$ = ba_op(B_AT_OP_LOR, $1, $3); }
-	| term '+' term			{ $$ = ba_op(B_AT_OP_PLUS, $1, $3); }
-	| term '-' term			{ $$ = ba_op(B_AT_OP_MINUS, $1, $3); }
-	| term '*' term			{ $$ = ba_op(B_AT_OP_MULT, $1, $3); }
-	| term '/' term			{ $$ = ba_op(B_AT_OP_DIVIDE, $1, $3); }
-	| term '&' term			{ $$ = ba_op(B_AT_OP_BAND, $1, $3); }
-	| term '|' term			{ $$ = ba_op(B_AT_OP_BOR, $1, $3); }
-	| staticv			{ $$ = ba_new($1, B_AT_LONG); }
-	| BUILTIN			{ $$ = ba_new(NULL, $1); }
-	| lvar				{ $$ = bl_find($1); }
-	| gvar				{ $$ = bg_find($1); }
+factor : '(' expr ')'		{ $$ = $2; }
+	| staticv		{ $$ = ba_new($1, B_AT_LONG); }
+	| BUILTIN		{ $$ = ba_new(NULL, $1); }
+	| lvar			{ $$ = bl_find($1); }
+	| gvar			{ $$ = bg_find($1); }
 	| mentry
 	;
 
 
-vargs	: expr
-	| vargs ',' expr	{ $$ = ba_append($1, $3); }
+vargs	: pat
+	| vargs ',' pat			{ $$ = ba_append($1, $3); }
 	;
 
-pargs	: term
-	| gvar ',' expr		{ $$ = ba_append(bg_find($1), $3); }
+pargs	: expr
+	| gvar ',' pat			{ $$ = ba_append(bg_find($1), $3); }
 	;
 
 NL	: /* empty */ | '\n'
 		;
 
 stmt	: ';' NL			{ $$ = NULL; }
-	| gvar '=' expr			{ $$ = bg_store($1, $3); }
-	| lvar '=' expr			{ $$ = bl_store($1, $3); }
-	| gvar '[' vargs ']' '=' mexpr	{ $$ = bm_insert($1, $3, $6); }
+	| gvar '=' pat			{ $$ = bg_store($1, $3); }
+	| lvar '=' pat			{ $$ = bl_store($1, $3); }
+	| gvar '[' vargs ']' '=' mpat	{ $$ = bm_insert($1, $3, $6); }
 	| FUNCN '(' vargs ')'		{ $$ = bs_new($1, $3, NULL); }
-	| FUNC1 '(' expr ')'		{ $$ = bs_new($1, $3, NULL); }
+	| FUNC1 '(' pat ')'		{ $$ = bs_new($1, $3, NULL); }
 	| FUNC0 '(' ')'			{ $$ = bs_new($1, NULL, NULL); }
 	| F_DELETE '(' mentry ')'	{ $$ = bm_op($1, $3, NULL); }
 	| F_PRINT '(' pargs ')'		{ $$ = bs_new($1, $3, NULL); }
-	| gvar '=' OP1 '(' expr ')'	{ $$ = bh_inc($1, $5, NULL); }
-	| gvar '=' OP4 '(' expr ',' vargs ')'	{ $$ = bh_inc($1, $5, $7); }
+	| gvar '=' OP1 '(' pat ')'	{ $$ = bh_inc($1, $5, NULL); }
+	| gvar '=' OP4 '(' pat ',' vargs ')'	{ $$ = bh_inc($1, $5, $7); }
 	;
 
 stmtlist: stmt
diff --git a/usr.sbin/btrace/bt_parser.h b/usr.sbin/btrace/bt_parser.h
index 67481456a59..ec77e345e1e 100644
--- a/usr.sbin/btrace/bt_parser.h
+++ b/usr.sbin/btrace/bt_parser.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bt_parser.h,v 1.17 2021/08/30 11:57:45 mpi Exp $	*/
+/*	$OpenBSD: bt_parser.h,v 1.18 2021/08/31 08:39:26 mpi Exp $	*/
 
 /*
  * Copyright (c) 2019-2021 Martin Pieuchot <mpi@openbsd.org>
@@ -156,6 +156,7 @@ struct bt_arg {
 		B_AT_OP_MULT,
 		B_AT_OP_DIVIDE,
 		B_AT_OP_BAND,
+		B_AT_OP_XOR,
 		B_AT_OP_BOR,
 		B_AT_OP_EQ,
 		B_AT_OP_NE,
@@ -198,6 +199,8 @@ struct bt_stmt {
 
 extern struct bt_ruleq	 g_rules;	/* Successfully parsed rules. */
 extern int		 g_nprobes;	/* # of probes to attach */
+extern struct bt_arg 	 g_nullba;
+extern struct bt_arg	 g_maxba;
 
 int			 btparse(const char *, size_t, const char *, int);
 
diff --git a/usr.sbin/btrace/btrace.c b/usr.sbin/btrace/btrace.c
index 785a4ed7c69..bd63c77c17d 100644
--- a/usr.sbin/btrace/btrace.c
+++ b/usr.sbin/btrace/btrace.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: btrace.c,v 1.39 2021/08/30 11:57:45 mpi Exp $ */
+/*	$OpenBSD: btrace.c,v 1.40 2021/08/31 08:39:26 mpi Exp $ */
 
 /*
  * Copyright (c) 2019 - 2020 Martin Pieuchot <mpi@openbsd.org>
@@ -104,6 +104,8 @@ __dead void		 xabort(const char *, ...);
 void			 debug(const char *, ...);
 void			 debugx(const char *, ...);
 const char		*debug_rule_name(struct bt_rule *);
+void			 debug_dump_term(struct bt_arg *);
+void			 debug_dump_expr(struct bt_arg *);
 void			 debug_dump_filter(struct bt_rule *);
 
 struct dtioc_probe_info	*dt_dtpis;	/* array of available probes */
@@ -867,15 +869,15 @@ stmt_store(struct bt_stmt *bs, struct dt_evt *dtev)
 bool
 stmt_test(struct bt_stmt *bs, struct dt_evt *dtev)
 {
-	struct bt_arg *bop;
+	struct bt_arg *ba;
 
 	if (bs == NULL)
 		return true;
 
 	assert(bs->bs_var == NULL);
-	bop = SLIST_FIRST(&bs->bs_args);
+	ba = SLIST_FIRST(&bs->bs_args);
 
-	return baexpr2long(bop, dtev) != 0;
+	return baexpr2long(ba, dtev) != 0;
 }
 
 /*
@@ -1022,73 +1024,75 @@ long
 baexpr2long(struct bt_arg *ba, struct dt_evt *dtev)
 {
 	static long recursions;
-	struct bt_arg *a, *b;
-	long first, second, result;
+	struct bt_arg *lhs, *rhs;
+	long lval, rval, result;
 
 	if (++recursions >= __MAXOPERANDS)
 		errx(1, "too many operands (>%d) in expression", __MAXOPERANDS);
 
-	a = ba->ba_value;
-	first = ba2long(a, dtev);
+	lhs = ba->ba_value;
+	rhs = SLIST_NEXT(lhs, ba_next);
 
-	b = SLIST_NEXT(a, ba_next);
-
-	if (b == NULL) {
-		second = 0;
+	lval = ba2long(lhs, dtev);
+	if (rhs == NULL) {
+		rval = 0;
 	} else {
-		assert(SLIST_NEXT(b, ba_next) == NULL);
-		second = ba2long(b, dtev);
+		assert(SLIST_NEXT(rhs, ba_next) == NULL);
+		rval = ba2long(rhs, dtev);
 	}
 
 	switch (ba->ba_type) {
 	case B_AT_OP_PLUS:
-		result = first + second;
+		result = lval + rval;
 		break;
 	case B_AT_OP_MINUS:
-		result = first - second;
+		result = lval - rval;
 		break;
 	case B_AT_OP_MULT:
-		result = first * second;
+		result = lval * rval;
 		break;
 	case B_AT_OP_DIVIDE:
-		result = first / second;
+		result = lval / rval;
 		break;
 	case B_AT_OP_BAND:
-		result = first & second;
+		result = lval & rval;
+		break;
+	case B_AT_OP_XOR:
+		result = lval ^ rval;
 		break;
 	case B_AT_OP_BOR:
-		result = first | second;
+		result = lval | rval;
 		break;
 	case B_AT_OP_EQ:
-		result = (first == second);
+		result = (lval == rval);
 		break;
 	case B_AT_OP_NE:
-		result = (first != second);
+		result = (lval != rval);
 		break;
 	case B_AT_OP_LE:
-		result = (first <= second);
+		result = (lval <= rval);
 		break;
 	case B_AT_OP_LT:
-		result = (first < second);
+		result = (lval < rval);
 		break;
 	case B_AT_OP_GE:
-		result = (first >= second);
+		result = (lval >= rval);
 		break;
 	case B_AT_OP_GT:
-		result = (first > second);
+		result = (lval > rval);
 		break;
 	case B_AT_OP_LAND:
-		result = (first && second);
+		result = (lval && rval);
 		break;
 	case B_AT_OP_LOR:
-		result = (first || second);
+		result = (lval || rval);
 		break;
 	default:
 		xabort("unsuported operation %d", ba->ba_type);
 	}
 
-	debug("ba=%p '%ld %s %ld = %ld'\n", ba, first, ba_name(ba), second,
-	   result);
+	debug("ba=%p eval '%ld %s %ld = %d'\n", ba, lval, ba_name(ba),
+	   rval, result);
 
 	--recursions;
 
@@ -1106,6 +1110,40 @@ ba_name(struct bt_arg *ba)
 		return "pid";
 	case B_AT_BI_TID:
 		return "tid";
+	case B_AT_BI_COMM:
+		return "comm";
+	case B_AT_BI_CPU:
+		return "cpu";
+	case B_AT_BI_NSECS:
+		return "nsecs";
+	case B_AT_BI_KSTACK:
+		return "kstack";
+	case B_AT_BI_USTACK:
+		return "ustack";
+	case B_AT_BI_ARG0:
+		return "arg0";
+	case B_AT_BI_ARG1:
+		return "arg1";
+	case B_AT_BI_ARG2:
+		return "arg2";
+	case B_AT_BI_ARG3:
+		return "arg3";
+	case B_AT_BI_ARG4:
+		return "arg4";
+	case B_AT_BI_ARG5:
+		return "arg5";
+	case B_AT_BI_ARG6:
+		return "arg6";
+	case B_AT_BI_ARG7:
+		return "arg7";
+	case B_AT_BI_ARG8:
+		return "arg8";
+	case B_AT_BI_ARG9:
+		return "arg9";
+	case B_AT_BI_ARGS:
+		return "args";
+	case B_AT_BI_RETVAL:
+		return "retval";
 	case B_AT_OP_PLUS:
 		return "+";
 	case B_AT_OP_MINUS:
@@ -1116,6 +1154,8 @@ ba_name(struct bt_arg *ba)
 		return "/";
 	case B_AT_OP_BAND:
 		return "&";
+	case B_AT_OP_XOR:
+		return "^";
 	case B_AT_OP_BOR:
 		return "|";
 	case B_AT_OP_EQ:
@@ -1394,20 +1434,56 @@ debugx(const char *fmt, ...)
 }
 
 void
-debug_dump_filter(struct bt_rule *r)
+debug_dump_term(struct bt_arg *ba)
 {
-	if (r->br_filter != NULL) {
-		struct bt_stmt *bs = r->br_filter->bf_condition;
-		struct bt_arg *bop = SLIST_FIRST(&bs->bs_args);
-		struct bt_arg *a, *b;
+	switch (ba->ba_type) {
+	case B_AT_LONG:
+		debugx("%s", ba2str(ba, NULL));
+		break;
+	case B_AT_OP_PLUS ... B_AT_OP_LOR:
+		debug_dump_expr(ba);
+		break;
+	default:
+		debugx("%s", ba_name(ba));
+	}
+}
 
-		a = bop->ba_value;
-		b = SLIST_NEXT(a, ba_next);
+void
+debug_dump_expr(struct bt_arg *ba)
+{
+	struct bt_arg *lhs, *rhs;
+
+	lhs = ba->ba_value;
+	rhs = SLIST_NEXT(lhs, ba_next);
+
+	/* Left */
+	debug_dump_term(lhs);
+
+	/* Right */
+	if (rhs != NULL) {
+		debugx(" %s ", ba_name(ba));
+		debug_dump_term(rhs);
+	} else {
+		if (ba->ba_type != B_AT_OP_NE)
+			debugx(" %s NULL", ba_name(ba));
+	}
+}
 
-		debugx(" / %s %s %s /", ba_name(a), ba_name(bop),
-		    (b != NULL) ? ba_name(b) : "NULL");
+void
+debug_dump_filter(struct bt_rule *r)
+{
+	struct bt_stmt *bs;
+
+	if (r->br_filter == NULL) {
+		debugx("\n");
+		return;
 	}
-	debugx("\n");
+
+	bs = r->br_filter->bf_condition;
+
+	debugx(" /");
+	debug_dump_expr(SLIST_FIRST(&bs->bs_args));
+	debugx("/\n");
 }
 
 const char *
diff --git a/usr.sbin/btrace/map.c b/usr.sbin/btrace/map.c
index 85e675d94f4..1313b19465b 100644
--- a/usr.sbin/btrace/map.c
+++ b/usr.sbin/btrace/map.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: map.c,v 1.12 2021/01/21 13:19:25 mpi Exp $ */
+/*	$OpenBSD: map.c,v 1.13 2021/08/31 08:39:26 mpi Exp $ */
 
 /*
  * Copyright (c) 2020 Martin Pieuchot <mpi@openbsd.org>
@@ -178,9 +178,6 @@ map_insert(struct map *map, const char *key, struct bt_arg *bval,
 	return map;
 }
 
-static struct bt_arg nullba = BA_INITIALIZER(0, B_AT_LONG);
-static struct bt_arg maxba = BA_INITIALIZER(LONG_MAX, B_AT_LONG);
-
 /* Print at most `top' entries of the map ordered by value. */
 void
 map_print(struct map *map, size_t top, const char *name)
@@ -192,10 +189,10 @@ map_print(struct map *map, size_t top, const char *name)
 	if (map == NULL)
 		return;
 
-	bprev = &maxba;
+	bprev = &g_maxba;
 	for (i = 0; i < top; i++) {
 		mcur = NULL;
-		bhigh = &nullba;
+		bhigh = &g_nullba;
 		RB_FOREACH(mep, map, map) {
 			if (bacmp(mep->mval, bhigh) >= 0 &&
 			    bacmp(mep->mval, bprev) < 0 &&