bosun-monitor · annettejanewilson · Feb 25, 2020 · Feb 26, 2020
diff --git a/cmd/bosun/expr/parse/node.go b/cmd/bosun/expr/parse/node.go
@@ -352,8 +352,63 @@ func newBinary(operator item, arg1, arg2 Node) *BinaryNode {
 	return &BinaryNode{NodeType: NodeBinary, Pos: operator.pos, Args: [2]Node{arg1, arg2}, Operator: operator, OpStr: operator.val}
 }
 
+var binaryPrecedence = map[itemType]int{
+	itemPow: 1,
+
+	itemMult: 2,
+	itemDiv:  2,
+	itemMod:  2,
+
+	itemPlus:  3,
+	itemMinus: 3,
+
+	itemEq:        4,
+	itemNotEq:     4,
+	itemGreater:   4,
+	itemGreaterEq: 4,
+	itemLess:      4,
+	itemLessEq:    4,
+
+	itemAnd: 5,
+
+	itemOr: 6,
+}
+
+type operatorSide int
+
+const (
+	left operatorSide = iota
+	right
+)
+
+func (b *BinaryNode) doesChildNeedParens(child Node, childSide operatorSide) bool {
+	if child.Type() != NodeBinary {
+		return false
+	}
+	parentPrecedence := binaryPrecedence[b.Operator.typ]
+	childPrecedence := binaryPrecedence[child.(*BinaryNode).Operator.typ]
+	childOperatorBindsTighter := childPrecedence < parentPrecedence
+	childOperatorBindsWeaker := childPrecedence > parentPrecedence
+	if childOperatorBindsTighter {
+		return false
+	}
+	if childOperatorBindsWeaker {
+		return true
+	}
+	isLeftAssociative := true // Currently all Bosun binary operators are left associative
+	return (childSide == left) != isLeftAssociative
+}
+
 func (b *BinaryNode) String() string {
-	return fmt.Sprintf("%s %s %s", b.Args[0], b.Operator.val, b.Args[1])
+	leftChild := b.Args[0].String()
+	rightChild := b.Args[1].String()
+	if b.doesChildNeedParens(b.Args[0], left) {
+		leftChild = fmt.Sprintf("(%s)", leftChild)
+	}
+	if b.doesChildNeedParens(b.Args[1], right) {
+		rightChild = fmt.Sprintf("(%s)", rightChild)
+	}
+	return fmt.Sprintf("%s %s %s", leftChild, b.Operator.val, rightChild)
 }
 
 func (b *BinaryNode) StringAST() string {
@@ -423,7 +478,11 @@ func newUnary(operator item, arg Node) *UnaryNode {
 }
 
 func (u *UnaryNode) String() string {
-	return fmt.Sprintf("%s%s", u.Operator.val, u.Arg)
+	child := u.Arg.String()
+	if u.Arg.Type() == NodeBinary {
+		child = fmt.Sprintf("(%s)", child)
+	}
+	return fmt.Sprintf("%s%s", u.Operator.val, child)
 }
 
 func (u *UnaryNode) StringAST() string {

diff --git a/cmd/bosun/expr/parse/node_test.go b/cmd/bosun/expr/parse/node_test.go
@@ -0,0 +1,71 @@
+package parse
+
+import (
+	"testing"
+)
+
+type nodeTest struct {
+	name   string
+	input  string
+	result string
+}
+
+var nodeTests = []nodeTest{
+	// Test that expressions are serialised with the necessary
+	// parentheses. Since binary expressions need to be aware of
+	// the relative precedence of child expressions, we test trees
+	// where the root operator is of equal precedence, one level
+	// higher, and one level lower.
+
+	// Lowest precedence: ||
+	{"binary parens || over ||", "(0 || 1) || (1 || 0)", "0 || 1 || (1 || 0)"},
+	{"binary parens || over &&", "(0 && 1) || (1 && 0)", "0 && 1 || 1 && 0"},
+	{"binary parens && over ||", "(0 || 1) && (1 || 0)", "(0 || 1) && (1 || 0)"},
+	// Higher precedence: &&
+	{"binary parens && over &&", "(0 && 1) && (1 && 0)", "0 && 1 && (1 && 0)"},
+	{"binary parens && over >=", "(0 >= 1) && (1 >= 0)", "0 >= 1 && 1 >= 0"},
+	{"binary parens >= over &&", "(0 && 1) >= (1 && 0)", "(0 && 1) >= (1 && 0)"},
+	// Higher precedence: >=
+	{"binary parens >= over >=", "(0 >= 1) >= (1 >= 0)", "0 >= 1 >= (1 >= 0)"},
+	{"binary parens >= over +", "(0 + 1) >= (1 + 0)", "0 + 1 >= 1 + 0"},
+	{"binary parens + over >=", "(0 >= 1) + (1 >= 0)", "(0 >= 1) + (1 >= 0)"},
+	// Higher precedence: +
+	{"binary parens + over +", "(0 + 1) + (1 + 0)", "0 + 1 + (1 + 0)"},
+	{"binary parens + over *", "(0 * 1) + (1 * 0)", "0 * 1 + 1 * 0"},
+	{"binary parens * over +", "(0 + 1) * (1 + 0)", "(0 + 1) * (1 + 0)"},
+	// Higher precedence: **
+	{"binary parens + over +", "(0 + 1) + (1 + 0)", "0 + 1 + (1 + 0)"},
+	{"binary parens + over **", "(0 ** 1) + (1 ** 0)", "0 ** 1 + 1 ** 0"},
+	{"binary parens ** over +", "(0 + 1) ** (1 + 0)", "(0 + 1) ** (1 + 0)"},
+
+	{"unary parens ! around binary op", "!(0 && 1)", "!(0 && 1)"},
+	{"unary parens ! alone", "!(0)", "!0"},
+
+	{"unary parens - around binary op", "-(1 ** 1)", "-(1 ** 1)"},
+	{"unary parens - alone", "-(1)", "-1"},
+
+	// This might be a surprise! Some languages make exponentiation higher
+	// precedence than negation, but our unary operators always take
+	// higher precedence than exponentiation, so .String() will not
+	// reproduce these redundant parens.
+	{"unary parens - inside **", "(-1) ** 1", "-1 ** 1"},
+}
+
+func TestNodeString(t *testing.T) {
+	textFormat = "%q"
+	defer func() { textFormat = "%s" }()
+	for _, test := range nodeTests {
+		tmpl := New(nil)
+		err := tmpl.Parse(test.input, builtins)
+		if err != nil {
+			t.Errorf("%q: unexpected error: %v", test.name, err)
+			continue
+		} else {
+			var result string
+			result = tmpl.Root.String()
+			if result != test.result {
+				t.Errorf("%s=(%q): got\n\t%v\nexpected\n\t%v", test.name, test.input, result, test.result)
+			}
+		}
+	}
+}
diff --git a/cmd/bosun/expr/parse/parse_test.go b/cmd/bosun/expr/parse/parse_test.go
@@ -104,7 +104,8 @@ var parseTests = []parseTest{
 	{"expression", "1+2*3/4-5 && !2|| -4", noError, "1 + 2 * 3 / 4 - 5 && !2 || -4"},
 	{"expression with func", `avg(q("q", "1m"))>=0.7&&avg(q("q", "1m"))!=3-0x8`, noError,
 		`avg(q("q", "1m")) >= 0.7 && avg(q("q", "1m")) != 3 - 0x8`},
-	{"func types", `avg(q("q", "1m"))>avg(q("q", "1m"))+avg(q("q", "1m"))`, noError, `avg(q("q", "1m")) > avg(q("q", "1m")) + avg(q("q", "1m"))`},
+	{"func types", `avg(q("q", "1m"))>avg(q("q", "1m"))+avg(q("q", "1m"))`, noError,
+		`avg(q("q", "1m")) > avg(q("q", "1m")) + avg(q("q", "1m"))`},
 	{"series compare", `q("q", "1m")>0`, noError, `q("q", "1m") > 0`},
 	{"unary series", `!q("q", "1m")`, noError, `!q("q", "1m")`},
 	{"expr in func", `forecastlr(q("q", "1m"), -1)`, noError, `forecastlr(q("q", "1m"), -1)`},
@@ -116,6 +117,15 @@ var parseTests = []parseTest{
 	{"bad type", `band("q", "1h", "1m", "8")`, hasError, ""},
 	{"wrong number args", `avg(q("q", "1m"), "1m", 1)`, hasError, ""},
 	{"2 series math", `band(q("q", "1m"))+band(q("q", "1m"))`, hasError, ""},
+	// Parentheses.
+	{"redundant parens", "(5)", noError, "5"},
+	{"redundant nested parens", "(((5)))", noError, "5"},
+	{"redundant unary parens", "-(5)", noError, "-5"},
+	{"necessary unary parens", "-(5 + 3)", noError, "-(5 + 3)"},
+	{"redundant assoc parens", "(10 - 5) - 2", noError, "10 - 5 - 2"},
+	{"necessary assoc parens", "10 - (5 - 2)", noError, "10 - (5 - 2)"},
+	{"redundant precedence parens", "10 + (5 * 2)", noError, "10 + 5 * 2"},
+	{"necessary precedence parens", "(10 + 5) * 2", noError, "(10 + 5) * 2"},
 }
 
 func TestParse(t *testing.T) {