go/build/constraint: add parser for build tag constraint expressions

This package implements a parser for the new //go:build constraint lines.
The parser also handles // +build lines, to be able to process legacy files.

This will not be used in the standard library until Go 1.17,
but it seems worth publishing in Go 1.16 so that code that
needs to process both kinds of lines once Go 1.17 comes out
will be able to build using Go 1.16 as well.

For #41184. Design in https://golang.org/design/draft-gobuild.

Change-Id: I756c0de4081c5039e8b7397200e5274f223ab111
Reviewed-on: https://go-review.googlesource.com/c/go/+/240604
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Russ Cox <rsc@golang.org>
Trust: Jay Conrod <jayconrod@google.com>
Reviewed-by: Jay Conrod <jayconrod@google.com>

4 files changed, 896 insertions, 1 deletions

diff --git a/src/go/build/build_test.go b/src/go/build/build_test.go
index 5a3e9ee714..d8f264cac7 100644
--- a/src/go/build/build_test.go
+++ b/src/go/build/build_test.go
@@ -28,6 +28,7 @@ func TestMatch(t *testing.T) {
 	ctxt := Default
 	what := "default"
 	match := func(tag string, want map[string]bool) {
+		t.Helper()
 		m := make(map[string]bool)
 		if !ctxt.match(tag, m) {
 			t.Errorf("%s context should match %s, does not", what, tag)
@@ -37,6 +38,7 @@ func TestMatch(t *testing.T) {
 		}
 	}
 	nomatch := func(tag string, want map[string]bool) {
+		t.Helper()
 		m := make(map[string]bool)
 		if ctxt.match(tag, m) {
 			t.Errorf("%s context should NOT match %s, does", what, tag)
@@ -57,7 +59,6 @@ func TestMatch(t *testing.T) {
 	nomatch(runtime.GOOS+","+runtime.GOARCH+",!foo", map[string]bool{runtime.GOOS: true, runtime.GOARCH: true, "foo": true})
 	match(runtime.GOOS+","+runtime.GOARCH+",!bar", map[string]bool{runtime.GOOS: true, runtime.GOARCH: true, "bar": true})
 	nomatch(runtime.GOOS+","+runtime.GOARCH+",bar", map[string]bool{runtime.GOOS: true, runtime.GOARCH: true, "bar": true})
-	nomatch("!", map[string]bool{})
 }
 
 func TestDotSlashImport(t *testing.T) {
diff --git a/src/go/build/constraint/expr.go b/src/go/build/constraint/expr.go
new file mode 100644
index 0000000000..3b278702f8
--- /dev/null
+++ b/src/go/build/constraint/expr.go
@@ -0,0 +1,574 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package constraint implements parsing and evaluation of build constraint lines.
+// See https://golang.org/cmd/go/#hdr-Build_constraints for documentation about build constraints themselves.
+//
+// This package parses both the original “// +build” syntax and the “//go:build” syntax that will be added in Go 1.17.
+// The parser is being included in Go 1.16 to allow tools that need to process Go 1.17 source code
+// to still be built against the Go 1.16 release.
+// See https://golang.org/design/draft-gobuild for details about the “//go:build” syntax.
+package constraint
+
+import (
+	"errors"
+	"strings"
+	"unicode"
+	"unicode/utf8"
+)
+
+// An Expr is a build tag constraint expression.
+// The underlying concrete type is *AndExpr, *OrExpr, *NotExpr, or *TagExpr.
+type Expr interface {
+	// String returns the string form of the expression,
+	// using the boolean syntax used in //go:build lines.
+	String() string
+
+	// Eval reports whether the expression evaluates to true.
+	// It calls ok(tag) as needed to find out whether a given build tag
+	// is satisfied by the current build configuration.
+	Eval(ok func(tag string) bool) bool
+
+	// The presence of an isExpr method explicitly marks the type as an Expr.
+	// Only implementations in this package should be used as Exprs.
+	isExpr()
+}
+
+// A TagExpr is an Expr for the single tag Tag.
+type TagExpr struct {
+	Tag string // for example, “linux” or “cgo”
+}
+
+func (x *TagExpr) isExpr() {}
+
+func (x *TagExpr) Eval(ok func(tag string) bool) bool {
+	return ok(x.Tag)
+}
+
+func (x *TagExpr) String() string {
+	return x.Tag
+}
+
+func tag(tag string) Expr { return &TagExpr{tag} }
+
+// A NotExpr represents the expression !X (the negation of X).
+type NotExpr struct {
+	X Expr
+}
+
+func (x *NotExpr) isExpr() {}
+
+func (x *NotExpr) Eval(ok func(tag string) bool) bool {
+	return !x.X.Eval(ok)
+}
+
+func (x *NotExpr) String() string {
+	s := x.X.String()
+	switch x.X.(type) {
+	case *AndExpr, *OrExpr:
+		s = "(" + s + ")"
+	}
+	return "!" + s
+}
+
+func not(x Expr) Expr { return &NotExpr{x} }
+
+// An AndExpr represents the expression X && Y.
+type AndExpr struct {
+	X, Y Expr
+}
+
+func (x *AndExpr) isExpr() {}
+
+func (x *AndExpr) Eval(ok func(tag string) bool) bool {
+	// Note: Eval both, to make sure ok func observes all tags.
+	xok := x.X.Eval(ok)
+	yok := x.Y.Eval(ok)
+	return xok && yok
+}
+
+func (x *AndExpr) String() string {
+	return andArg(x.X) + " && " + andArg(x.Y)
+}
+
+func andArg(x Expr) string {
+	s := x.String()
+	if _, ok := x.(*OrExpr); ok {
+		s = "(" + s + ")"
+	}
+	return s
+}
+
+func and(x, y Expr) Expr {
+	return &AndExpr{x, y}
+}
+
+// An OrExpr represents the expression X || Y.
+type OrExpr struct {
+	X, Y Expr
+}
+
+func (x *OrExpr) isExpr() {}
+
+func (x *OrExpr) Eval(ok func(tag string) bool) bool {
+	// Note: Eval both, to make sure ok func observes all tags.
+	xok := x.X.Eval(ok)
+	yok := x.Y.Eval(ok)
+	return xok || yok
+}
+
+func (x *OrExpr) String() string {
+	return orArg(x.X) + " || " + orArg(x.Y)
+}
+
+func orArg(x Expr) string {
+	s := x.String()
+	if _, ok := x.(*AndExpr); ok {
+		s = "(" + s + ")"
+	}
+	return s
+}
+
+func or(x, y Expr) Expr {
+	return &OrExpr{x, y}
+}
+
+// A SyntaxError reports a syntax error in a parsed build expression.
+type SyntaxError struct {
+	Offset int    // byte offset in input where error was detected
+	Err    string // description of error
+}
+
+func (e *SyntaxError) Error() string {
+	return e.Err
+}
+
+var errNotConstraint = errors.New("not a build constraint")
+
+// Parse parses a single build constraint line of the form “//go:build ...” or “// +build ...”
+// and returns the corresponding boolean expression.
+func Parse(line string) (Expr, error) {
+	if text, ok := splitGoBuild(line); ok {
+		return parseExpr(text)
+	}
+	if text, ok := splitPlusBuild(line); ok {
+		return parsePlusBuildExpr(text), nil
+	}
+	return nil, errNotConstraint
+}
+
+// IsGoBuild reports whether the line of text is a “//go:build” constraint.
+// It only checks the prefix of the text, not that the expression itself parses.
+func IsGoBuild(line string) bool {
+	_, ok := splitGoBuild(line)
+	return ok
+}
+
+// splitGoBuild splits apart the leading //go:build prefix in line from the build expression itself.
+// It returns "", false if the input is not a //go:build line or if the input contains multiple lines.
+func splitGoBuild(line string) (expr string, ok bool) {
+	// A single trailing newline is OK; otherwise multiple lines are not.
+	if len(line) > 0 && line[len(line)-1] == '\n' {
+		line = line[:len(line)-1]
+	}
+	if strings.Contains(line, "\n") {
+		return "", false
+	}
+
+	if !strings.HasPrefix(line, "//go:build") {
+		return "", false
+	}
+
+	line = strings.TrimSpace(line)
+	line = line[len("//go:build"):]
+
+	// If strings.TrimSpace finds more to trim after removing the //go:build prefix,
+	// it means that the prefix was followed by a space, making this a //go:build line
+	// (as opposed to a //go:buildsomethingelse line).
+	// If line is empty, we had "//go:build" by itself, which also counts.
+	trim := strings.TrimSpace(line)
+	if len(line) == len(trim) && line != "" {
+		return "", false
+	}
+
+	return trim, true
+}
+
+// An exprParser holds state for parsing a build expression.
+type exprParser struct {
+	s string // input string
+	i int    // next read location in s
+
+	tok   string // last token read
+	isTag bool
+	pos   int // position (start) of last token
+}
+
+// parseExpr parses a boolean build tag expression.
+func parseExpr(text string) (x Expr, err error) {
+	defer func() {
+		if e := recover(); e != nil {
+			if e, ok := e.(*SyntaxError); ok {
+				err = e
+				return
+			}
+			panic(e) // unreachable unless parser has a bug
+		}
+	}()
+
+	p := &exprParser{s: text}
+	x = p.or()
+	if p.tok != "" {
+		panic(&SyntaxError{Offset: p.pos, Err: "unexpected token " + p.tok})
+	}
+	return x, nil
+}
+
+// or parses a sequence of || expressions.
+// On entry, the next input token has not yet been lexed.
+// On exit, the next input token has been lexed and is in p.tok.
+func (p *exprParser) or() Expr {
+	x := p.and()
+	for p.tok == "||" {
+		x = or(x, p.and())
+	}
+	return x
+}
+
+// and parses a sequence of && expressions.
+// On entry, the next input token has not yet been lexed.
+// On exit, the next input token has been lexed and is in p.tok.
+func (p *exprParser) and() Expr {
+	x := p.not()
+	for p.tok == "&&" {
+		x = and(x, p.not())
+	}
+	return x
+}
+
+// not parses a ! expression.
+// On entry, the next input token has not yet been lexed.
+// On exit, the next input token has been lexed and is in p.tok.
+func (p *exprParser) not() Expr {
+	p.lex()
+	if p.tok == "!" {
+		p.lex()
+		if p.tok == "!" {
+			panic(&SyntaxError{Offset: p.pos, Err: "double negation not allowed"})
+		}
+		return not(p.atom())
+	}
+	return p.atom()
+}
+
+// atom parses a tag or a parenthesized expression.
+// On entry, the next input token HAS been lexed.
+// On exit, the next input token has been lexed and is in p.tok.
+func (p *exprParser) atom() Expr {
+	// first token already in p.tok
+	if p.tok == "(" {
+		pos := p.pos
+		defer func() {
+			if e := recover(); e != nil {
+				if e, ok := e.(*SyntaxError); ok && e.Err == "unexpected end of expression" {
+					e.Err = "missing close paren"
+				}
+				panic(e)
+			}
+		}()
+		x := p.or()
+		if p.tok != ")" {
+			panic(&SyntaxError{Offset: pos, Err: "missing close paren"})
+		}
+		p.lex()
+		return x
+	}
+
+	if !p.isTag {
+		if p.tok == "" {
+			panic(&SyntaxError{Offset: p.pos, Err: "unexpected end of expression"})
+		}
+		panic(&SyntaxError{Offset: p.pos, Err: "unexpected token " + p.tok})
+	}
+	tok := p.tok
+	p.lex()
+	return tag(tok)
+}
+
+// lex finds and consumes the next token in the input stream.
+// On return, p.tok is set to the token text,
+// p.isTag reports whether the token was a tag,
+// and p.pos records the byte offset of the start of the token in the input stream.
+// If lex reaches the end of the input, p.tok is set to the empty string.
+// For any other syntax error, lex panics with a SyntaxError.
+func (p *exprParser) lex() {
+	p.isTag = false
+	for p.i < len(p.s) && (p.s[p.i] == ' ' || p.s[p.i] == '\t') {
+		p.i++
+	}
+	if p.i >= len(p.s) {
+		p.tok = ""
+		p.pos = p.i
+		return
+	}
+	switch p.s[p.i] {
+	case '(', ')', '!':
+		p.pos = p.i
+		p.i++
+		p.tok = p.s[p.pos:p.i]
+		return
+
+	case '&', '|':
+		if p.i+1 >= len(p.s) || p.s[p.i+1] != p.s[p.i] {
+			panic(&SyntaxError{Offset: p.i, Err: "invalid syntax at " + string(rune(p.s[p.i]))})
+		}
+		p.pos = p.i
+		p.i += 2
+		p.tok = p.s[p.pos:p.i]
+		return
+	}
+
+	tag := p.s[p.i:]
+	for i, c := range tag {
+		if !unicode.IsLetter(c) && !unicode.IsDigit(c) && c != '_' && c != '.' {
+			tag = tag[:i]
+			break
+		}
+	}
+	if tag == "" {
+		c, _ := utf8.DecodeRuneInString(p.s[p.i:])
+		panic(&SyntaxError{Offset: p.i, Err: "invalid syntax at " + string(c)})
+	}
+
+	p.pos = p.i
+	p.i += len(tag)
+	p.tok = p.s[p.pos:p.i]
+	p.isTag = true
+	return
+}
+
+// IsPlusBuild reports whether the line of text is a “// +build” constraint.
+// It only checks the prefix of the text, not that the expression itself parses.
+func IsPlusBuild(line string) bool {
+	_, ok := splitPlusBuild(line)
+	return ok
+}
+
+// splitGoBuild splits apart the leading //go:build prefix in line from the build expression itself.
+// It returns "", false if the input is not a //go:build line or if the input contains multiple lines.
+func splitPlusBuild(line string) (expr string, ok bool) {
+	// A single trailing newline is OK; otherwise multiple lines are not.
+	if len(line) > 0 && line[len(line)-1] == '\n' {
+		line = line[:len(line)-1]
+	}
+	if strings.Contains(line, "\n") {
+		return "", false
+	}
+
+	if !strings.HasPrefix(line, "//") {
+		return "", false
+	}
+	line = line[len("//"):]
+	// Note the space is optional; "//+build" is recognized too.
+	line = strings.TrimSpace(line)
+
+	if !strings.HasPrefix(line, "+build") {
+		return "", false
+	}
+	line = line[len("+build"):]
+
+	// If strings.TrimSpace finds more to trim after removing the +build prefix,
+	// it means that the prefix was followed by a space, making this a +build line
+	// (as opposed to a +buildsomethingelse line).
+	// If line is empty, we had "// +build" by itself, which also counts.
+	trim := strings.TrimSpace(line)
+	if len(line) == len(trim) && line != "" {
+		return "", false
+	}
+
+	return trim, true
+}
+
+// parsePlusBuildExpr parses a legacy build tag expression (as used with “// +build”).
+func parsePlusBuildExpr(text string) Expr {
+	var x Expr
+	for _, clause := range strings.Fields(text) {
+		var y Expr
+		for _, lit := range strings.Split(clause, ",") {
+			var z Expr
+			var neg bool
+			if strings.HasPrefix(lit, "!!") || lit == "!" {
+				z = tag("ignore")
+			} else {
+				if strings.HasPrefix(lit, "!") {
+					neg = true
+					lit = lit[len("!"):]
+				}
+				if isValidTag(lit) {
+					z = tag(lit)
+				} else {
+					z = tag("ignore")
+				}
+				if neg {
+					z = not(z)
+				}
+			}
+			if y == nil {
+				y = z
+			} else {
+				y = and(y, z)
+			}
+		}
+		if x == nil {
+			x = y
+		} else {
+			x = or(x, y)
+		}
+	}
+	return x
+}
+
+// isValidTag reports whether the word is a valid build tag.
+// Tags must be letters, digits, underscores or dots.
+// Unlike in Go identifiers, all digits are fine (e.g., "386").
+func isValidTag(word string) bool {
+	if word == "" {
+		return false
+	}
+	for _, c := range word {
+		if !unicode.IsLetter(c) && !unicode.IsDigit(c) && c != '_' && c != '.' {
+			return false
+		}
+	}
+	return true
+}
+
+var errComplex = errors.New("expression too complex for // +build lines")
+
+// PlusBuildLines returns a sequence of “// +build” lines that evaluate to the build expression x.
+// If the expression is too complex to convert directly to “// +build” lines, PlusBuildLines returns an error.
+func PlusBuildLines(x Expr) ([]string, error) {
+	// Push all NOTs to the expression leaves, so that //go:build !(x && y) can be treated as !x || !y.
+	// This rewrite is both efficient and commonly needed, so it's worth doing.
+	// Essentially all other possible rewrites are too expensive and too rarely needed.
+	x = pushNot(x, false)
+
+	// Split into AND of ORs of ANDs of literals (tag or NOT tag).
+	var split [][][]Expr
+	for _, or := range appendSplitAnd(nil, x) {
+		var ands [][]Expr
+		for _, and := range appendSplitOr(nil, or) {
+			var lits []Expr
+			for _, lit := range appendSplitAnd(nil, and) {
+				switch lit.(type) {
+				case *TagExpr, *NotExpr:
+					lits = append(lits, lit)
+				default:
+					return nil, errComplex
+				}
+			}
+			ands = append(ands, lits)
+		}
+		split = append(split, ands)
+	}
+
+	// If all the ORs have length 1 (no actual OR'ing going on),
+	// push the top-level ANDs to the bottom level, so that we get
+	// one // +build line instead of many.
+	maxOr := 0
+	for _, or := range split {
+		if maxOr < len(or) {
+			maxOr = len(or)
+		}
+	}
+	if maxOr == 1 {
+		var lits []Expr
+		for _, or := range split {
+			lits = append(lits, or[0]...)
+		}
+		split = [][][]Expr{{lits}}
+	}
+
+	// Prepare the +build lines.
+	var lines []string
+	for _, or := range split {
+		line := "// +build"
+		for _, and := range or {
+			clause := ""
+			for i, lit := range and {
+				if i > 0 {
+					clause += ","
+				}
+				clause += lit.String()
+			}
+			line += " " + clause
+		}
+		lines = append(lines, line)
+	}
+
+	return lines, nil
+}
+
+// pushNot applies DeMorgan's law to push negations down the expression,
+// so that only tags are negated in the result.
+// (It applies the rewrites !(X && Y) => (!X || !Y) and !(X || Y) => (!X && !Y).)
+func pushNot(x Expr, not bool) Expr {
+	switch x := x.(type) {
+	default:
+		// unreachable
+		return x
+	case *NotExpr:
+		if _, ok := x.X.(*TagExpr); ok && !not {
+			return x
+		}
+		return pushNot(x.X, !not)
+	case *TagExpr:
+		if not {
+			return &NotExpr{X: x}
+		}
+		return x
+	case *AndExpr:
+		x1 := pushNot(x.X, not)
+		y1 := pushNot(x.Y, not)
+		if not {
+			return or(x1, y1)
+		}
+		if x1 == x.X && y1 == x.Y {
+			return x
+		}
+		return and(x1, y1)
+	case *OrExpr:
+		x1 := pushNot(x.X, not)
+		y1 := pushNot(x.Y, not)
+		if not {
+			return and(x1, y1)
+		}
+		if x1 == x.X && y1 == x.Y {
+			return x
+		}
+		return or(x1, y1)
+	}
+}
+
+// appendSplitAnd appends x to list while splitting apart any top-level && expressions.
+// For example, appendSplitAnd({W}, X && Y && Z) = {W, X, Y, Z}.
+func appendSplitAnd(list []Expr, x Expr) []Expr {
+	if x, ok := x.(*AndExpr); ok {
+		list = appendSplitAnd(list, x.X)
+		list = appendSplitAnd(list, x.Y)
+		return list
+	}
+	return append(list, x)
+}
+
+// appendSplitOr appends x to list while splitting apart any top-level || expressions.
+// For example, appendSplitOr({W}, X || Y || Z) = {W, X, Y, Z}.
+func appendSplitOr(list []Expr, x Expr) []Expr {
+	if x, ok := x.(*OrExpr); ok {
+		list = appendSplitOr(list, x.X)
+		list = appendSplitOr(list, x.Y)
+		return list
+	}
+	return append(list, x)
+}
diff --git a/src/go/build/constraint/expr_test.go b/src/go/build/constraint/expr_test.go
new file mode 100644
index 0000000000..4979f8b5f2
--- /dev/null
+++ b/src/go/build/constraint/expr_test.go
@@ -0,0 +1,317 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package constraint
+
+import (
+	"fmt"
+	"reflect"
+	"strings"
+	"testing"
+)
+
+var exprStringTests = []struct {
+	x   Expr
+	out string
+}{
+	{
+		x:   tag("abc"),
+		out: "abc",
+	},
+	{
+		x:   not(tag("abc")),
+		out: "!abc",
+	},
+	{
+		x:   not(and(tag("abc"), tag("def"))),
+		out: "!(abc && def)",
+	},
+	{
+		x:   and(tag("abc"), or(tag("def"), tag("ghi"))),
+		out: "abc && (def || ghi)",
+	},
+	{
+		x:   or(and(tag("abc"), tag("def")), tag("ghi")),
+		out: "(abc && def) || ghi",
+	},
+}
+
+func TestExprString(t *testing.T) {
+	for i, tt := range exprStringTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			s := tt.x.String()
+			if s != tt.out {
+				t.Errorf("String() mismatch:\nhave %s\nwant %s", s, tt.out)
+			}
+		})
+	}
+}
+
+var lexTests = []struct {
+	in  string
+	out string
+}{
+	{"", ""},
+	{"x", "x"},
+	{"x.y", "x.y"},
+	{"x_y", "x_y"},
+	{"αx", "αx"},
+	{"αx²", "αx err: invalid syntax at ²"},
+	{"go1.2", "go1.2"},
+	{"x y", "x y"},
+	{"x!y", "x ! y"},
+	{"&&||!()xy yx ", "&& || ! ( ) xy yx"},
+	{"x~", "x err: invalid syntax at ~"},
+	{"x ~", "x err: invalid syntax at ~"},
+	{"x &", "x err: invalid syntax at &"},
+	{"x &y", "x err: invalid syntax at &"},
+}
+
+func TestLex(t *testing.T) {
+	for i, tt := range lexTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			p := &exprParser{s: tt.in}
+			out := ""
+			for {
+				tok, err := lexHelp(p)
+				if tok == "" && err == nil {
+					break
+				}
+				if out != "" {
+					out += " "
+				}
+				if err != nil {
+					out += "err: " + err.Error()
+					break
+				}
+				out += tok
+			}
+			if out != tt.out {
+				t.Errorf("lex(%q):\nhave %s\nwant %s", tt.in, out, tt.out)
+			}
+		})
+	}
+}
+
+func lexHelp(p *exprParser) (tok string, err error) {
+	defer func() {
+		if e := recover(); e != nil {
+			if e, ok := e.(*SyntaxError); ok {
+				err = e
+				return
+			}
+			panic(e)
+		}
+	}()
+
+	p.lex()
+	return p.tok, nil
+}
+
+var parseExprTests = []struct {
+	in string
+	x  Expr
+}{
+	{"x", tag("x")},
+	{"x&&y", and(tag("x"), tag("y"))},
+	{"x||y", or(tag("x"), tag("y"))},
+	{"(x)", tag("x")},
+	{"x||y&&z", or(tag("x"), and(tag("y"), tag("z")))},
+	{"x&&y||z", or(and(tag("x"), tag("y")), tag("z"))},
+	{"x&&(y||z)", and(tag("x"), or(tag("y"), tag("z")))},
+	{"(x||y)&&z", and(or(tag("x"), tag("y")), tag("z"))},
+	{"!(x&&y)", not(and(tag("x"), tag("y")))},
+}
+
+func TestParseExpr(t *testing.T) {
+	for i, tt := range parseExprTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			x, err := parseExpr(tt.in)
+			if err != nil {
+				t.Fatal(err)
+			}
+			if x.String() != tt.x.String() {
+				t.Errorf("parseExpr(%q):\nhave %s\nwant %s", tt.in, x, tt.x)
+			}
+		})
+	}
+}
+
+var parseExprErrorTests = []struct {
+	in  string
+	err error
+}{
+	{"x && ", &SyntaxError{Offset: 5, Err: "unexpected end of expression"}},
+	{"x && (", &SyntaxError{Offset: 6, Err: "missing close paren"}},
+	{"x && ||", &SyntaxError{Offset: 5, Err: "unexpected token ||"}},
+	{"x && !", &SyntaxError{Offset: 6, Err: "unexpected end of expression"}},
+	{"x && !!", &SyntaxError{Offset: 6, Err: "double negation not allowed"}},
+	{"x !", &SyntaxError{Offset: 2, Err: "unexpected token !"}},
+	{"x && (y", &SyntaxError{Offset: 5, Err: "missing close paren"}},
+}
+
+func TestParseError(t *testing.T) {
+	for i, tt := range parseExprErrorTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			x, err := parseExpr(tt.in)
+			if err == nil {
+				t.Fatalf("parseExpr(%q) = %v, want error", tt.in, x)
+			}
+			if !reflect.DeepEqual(err, tt.err) {
+				t.Fatalf("parseExpr(%q): wrong error:\nhave %#v\nwant %#v", tt.in, err, tt.err)
+			}
+		})
+	}
+}
+
+var exprEvalTests = []struct {
+	in   string
+	ok   bool
+	tags string
+}{
+	{"x", false, "x"},
+	{"x && y", false, "x y"},
+	{"x || y", false, "x y"},
+	{"!x && yes", true, "x yes"},
+	{"yes || y", true, "y yes"},
+}
+
+func TestExprEval(t *testing.T) {
+	for i, tt := range exprEvalTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			x, err := parseExpr(tt.in)
+			if err != nil {
+				t.Fatal(err)
+			}
+			tags := make(map[string]bool)
+			wantTags := make(map[string]bool)
+			for _, tag := range strings.Fields(tt.tags) {
+				wantTags[tag] = true
+			}
+			hasTag := func(tag string) bool {
+				tags[tag] = true
+				return tag == "yes"
+			}
+			ok := x.Eval(hasTag)
+			if ok != tt.ok || !reflect.DeepEqual(tags, wantTags) {
+				t.Errorf("Eval(%#q):\nhave ok=%v, tags=%v\nwant ok=%v, tags=%v",
+					tt.in, ok, tags, tt.ok, wantTags)
+			}
+		})
+	}
+}
+
+var parsePlusBuildExprTests = []struct {
+	in string
+	x  Expr
+}{
+	{"x", tag("x")},
+	{"x,y", and(tag("x"), tag("y"))},
+	{"x y", or(tag("x"), tag("y"))},
+	{"x y,z", or(tag("x"), and(tag("y"), tag("z")))},
+	{"x,y z", or(and(tag("x"), tag("y")), tag("z"))},
+	{"x,!y !z", or(and(tag("x"), not(tag("y"))), not(tag("z")))},
+	{"!! x", or(tag("ignore"), tag("x"))},
+	{"!!x", tag("ignore")},
+	{"!x", not(tag("x"))},
+	{"!", tag("ignore")},
+}
+
+func TestParsePlusBuildExpr(t *testing.T) {
+	for i, tt := range parsePlusBuildExprTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			x := parsePlusBuildExpr(tt.in)
+			if x.String() != tt.x.String() {
+				t.Errorf("parsePlusBuildExpr(%q):\nhave %v\nwant %v", tt.in, x, tt.x)
+			}
+		})
+	}
+}
+
+var constraintTests = []struct {
+	in  string
+	x   Expr
+	err error
+}{
+	{"//+build x y", or(tag("x"), tag("y")), nil},
+	{"// +build x y \n", or(tag("x"), tag("y")), nil},
+	{"// +build x y \n ", nil, errNotConstraint},
+	{"// +build x y \nmore", nil, errNotConstraint},
+	{" //+build x y", nil, errNotConstraint},
+
+	{"//go:build x && y", and(tag("x"), tag("y")), nil},
+	{"//go:build x && y\n", and(tag("x"), tag("y")), nil},
+	{"//go:build x && y\n ", nil, errNotConstraint},
+	{"//go:build x && y\nmore", nil, errNotConstraint},
+	{" //go:build x && y", nil, errNotConstraint},
+}
+
+func TestParse(t *testing.T) {
+	for i, tt := range constraintTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			x, err := Parse(tt.in)
+			if err != nil {
+				if tt.err == nil {
+					t.Errorf("Constraint(%q): unexpected error: %v", tt.in, err)
+				} else if tt.err != err {
+					t.Errorf("Constraint(%q): error %v, want %v", tt.in, err, tt.err)
+				}
+				return
+			}
+			if tt.err != nil {
+				t.Errorf("Constraint(%q) = %v, want error %v", tt.in, x, tt.err)
+				return
+			}
+			if x.String() != tt.x.String() {
+				t.Errorf("Constraint(%q):\nhave %v\nwant %v", tt.in, x, tt.x)
+			}
+		})
+	}
+}
+
+var plusBuildLinesTests = []struct {
+	in  string
+	out []string
+	err error
+}{
+	{"x", []string{"x"}, nil},
+	{"x && !y", []string{"x,!y"}, nil},
+	{"x || y", []string{"x y"}, nil},
+	{"x && (y || z)", []string{"x", "y z"}, nil},
+	{"!(x && y)", []string{"!x !y"}, nil},
+	{"x || (y && z)", []string{"x y,z"}, nil},
+	{"w && (x || (y && z))", []string{"w", "x y,z"}, nil},
+	{"v || (w && (x || (y && z)))", nil, errComplex},
+}
+
+func TestPlusBuildLines(t *testing.T) {
+	for i, tt := range plusBuildLinesTests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			x, err := parseExpr(tt.in)
+			if err != nil {
+				t.Fatal(err)
+			}
+			lines, err := PlusBuildLines(x)
+			if err != nil {
+				if tt.err == nil {
+					t.Errorf("PlusBuildLines(%q): unexpected error: %v", tt.in, err)
+				} else if tt.err != err {
+					t.Errorf("PlusBuildLines(%q): error %v, want %v", tt.in, err, tt.err)
+				}
+				return
+			}
+			if tt.err != nil {
+				t.Errorf("PlusBuildLines(%q) = %v, want error %v", tt.in, lines, tt.err)
+				return
+			}
+			var want []string
+			for _, line := range tt.out {
+				want = append(want, "// +build "+line)
+			}
+			if !reflect.DeepEqual(lines, want) {
+				t.Errorf("PlusBuildLines(%q):\nhave %q\nwant %q", tt.in, lines, want)
+			}
+		})
+	}
+}
diff --git a/src/go/build/deps_test.go b/src/go/build/deps_test.go
index aa651af718..99cd59e5b5 100644
--- a/src/go/build/deps_test.go
+++ b/src/go/build/deps_test.go
@@ -282,6 +282,9 @@ var depsRules = `
 	container/heap, go/constant, go/parser
 	< go/types;
 
+	FMT
+	< go/build/constraint;
+
 	go/doc, go/parser, internal/goroot, internal/goversion
 	< go/build;