Source file src/go/build/constraint/expr.go

     1  // Copyright 2020 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package constraint implements parsing and evaluation of build constraint lines.
     6  // See https://golang.org/cmd/go/#hdr-Build_constraints for documentation about build constraints themselves.
     7  //
     8  // This package parses both the original “// +build” syntax and the “//go:build” syntax that was added in Go 1.17.
     9  // See https://golang.org/design/draft-gobuild for details about the “//go:build” syntax.
    10  package constraint
    11  
    12  import (
    13  	"errors"
    14  	"strings"
    15  	"unicode"
    16  	"unicode/utf8"
    17  )
    18  
    19  // An Expr is a build tag constraint expression.
    20  // The underlying concrete type is *[AndExpr], *[OrExpr], *[NotExpr], or *[TagExpr].
    21  type Expr interface {
    22  	// String returns the string form of the expression,
    23  	// using the boolean syntax used in //go:build lines.
    24  	String() string
    25  
    26  	// Eval reports whether the expression evaluates to true.
    27  	// It calls ok(tag) as needed to find out whether a given build tag
    28  	// is satisfied by the current build configuration.
    29  	Eval(ok func(tag string) bool) bool
    30  
    31  	// The presence of an isExpr method explicitly marks the type as an Expr.
    32  	// Only implementations in this package should be used as Exprs.
    33  	isExpr()
    34  }
    35  
    36  // A TagExpr is an [Expr] for the single tag Tag.
    37  type TagExpr struct {
    38  	Tag string // for example, “linux” or cgo”
    39  }
    40  
    41  func (x *TagExpr) isExpr() {}
    42  
    43  func (x *TagExpr) Eval(ok func(tag string) bool) bool {
    44  	return ok(x.Tag)
    45  }
    46  
    47  func (x *TagExpr) String() string {
    48  	return x.Tag
    49  }
    50  
    51  func tag(tag string) Expr { return &TagExpr{tag} }
    52  
    53  // A NotExpr represents the expression !X (the negation of X).
    54  type NotExpr struct {
    55  	X Expr
    56  }
    57  
    58  func (x *NotExpr) isExpr() {}
    59  
    60  func (x *NotExpr) Eval(ok func(tag string) bool) bool {
    61  	return !x.X.Eval(ok)
    62  }
    63  
    64  func (x *NotExpr) String() string {
    65  	s := x.X.String()
    66  	switch x.X.(type) {
    67  	case *AndExpr, *OrExpr:
    68  		s = "(" + s + ")"
    69  	}
    70  	return "!" + s
    71  }
    72  
    73  func not(x Expr) Expr { return &NotExpr{x} }
    74  
    75  // An AndExpr represents the expression X && Y.
    76  type AndExpr struct {
    77  	X, Y Expr
    78  }
    79  
    80  func (x *AndExpr) isExpr() {}
    81  
    82  func (x *AndExpr) Eval(ok func(tag string) bool) bool {
    83  	// Note: Eval both, to make sure ok func observes all tags.
    84  	xok := x.X.Eval(ok)
    85  	yok := x.Y.Eval(ok)
    86  	return xok && yok
    87  }
    88  
    89  func (x *AndExpr) String() string {
    90  	return andArg(x.X) + " && " + andArg(x.Y)
    91  }
    92  
    93  func andArg(x Expr) string {
    94  	s := x.String()
    95  	if _, ok := x.(*OrExpr); ok {
    96  		s = "(" + s + ")"
    97  	}
    98  	return s
    99  }
   100  
   101  func and(x, y Expr) Expr {
   102  	return &AndExpr{x, y}
   103  }
   104  
   105  // An OrExpr represents the expression X || Y.
   106  type OrExpr struct {
   107  	X, Y Expr
   108  }
   109  
   110  func (x *OrExpr) isExpr() {}
   111  
   112  func (x *OrExpr) Eval(ok func(tag string) bool) bool {
   113  	// Note: Eval both, to make sure ok func observes all tags.
   114  	xok := x.X.Eval(ok)
   115  	yok := x.Y.Eval(ok)
   116  	return xok || yok
   117  }
   118  
   119  func (x *OrExpr) String() string {
   120  	return orArg(x.X) + " || " + orArg(x.Y)
   121  }
   122  
   123  func orArg(x Expr) string {
   124  	s := x.String()
   125  	if _, ok := x.(*AndExpr); ok {
   126  		s = "(" + s + ")"
   127  	}
   128  	return s
   129  }
   130  
   131  func or(x, y Expr) Expr {
   132  	return &OrExpr{x, y}
   133  }
   134  
   135  // A SyntaxError reports a syntax error in a parsed build expression.
   136  type SyntaxError struct {
   137  	Offset int    // byte offset in input where error was detected
   138  	Err    string // description of error
   139  }
   140  
   141  func (e *SyntaxError) Error() string {
   142  	return e.Err
   143  }
   144  
   145  var errNotConstraint = errors.New("not a build constraint")
   146  
   147  // Parse parses a single build constraint line of the form “//go:build ...” or “// +build ...”
   148  // and returns the corresponding boolean expression.
   149  func Parse(line string) (Expr, error) {
   150  	if text, ok := splitGoBuild(line); ok {
   151  		return parseExpr(text)
   152  	}
   153  	if text, ok := splitPlusBuild(line); ok {
   154  		return parsePlusBuildExpr(text), nil
   155  	}
   156  	return nil, errNotConstraint
   157  }
   158  
   159  // IsGoBuild reports whether the line of text is a “//go:build” constraint.
   160  // It only checks the prefix of the text, not that the expression itself parses.
   161  func IsGoBuild(line string) bool {
   162  	_, ok := splitGoBuild(line)
   163  	return ok
   164  }
   165  
   166  // splitGoBuild splits apart the leading //go:build prefix in line from the build expression itself.
   167  // It returns "", false if the input is not a //go:build line or if the input contains multiple lines.
   168  func splitGoBuild(line string) (expr string, ok bool) {
   169  	// A single trailing newline is OK; otherwise multiple lines are not.
   170  	if len(line) > 0 && line[len(line)-1] == '\n' {
   171  		line = line[:len(line)-1]
   172  	}
   173  	if strings.Contains(line, "\n") {
   174  		return "", false
   175  	}
   176  
   177  	if !strings.HasPrefix(line, "//go:build") {
   178  		return "", false
   179  	}
   180  
   181  	line = strings.TrimSpace(line)
   182  	line = line[len("//go:build"):]
   183  
   184  	// If strings.TrimSpace finds more to trim after removing the //go:build prefix,
   185  	// it means that the prefix was followed by a space, making this a //go:build line
   186  	// (as opposed to a //go:buildsomethingelse line).
   187  	// If line is empty, we had "//go:build" by itself, which also counts.
   188  	trim := strings.TrimSpace(line)
   189  	if len(line) == len(trim) && line != "" {
   190  		return "", false
   191  	}
   192  
   193  	return trim, true
   194  }
   195  
   196  // An exprParser holds state for parsing a build expression.
   197  type exprParser struct {
   198  	s string // input string
   199  	i int    // next read location in s
   200  
   201  	tok   string // last token read
   202  	isTag bool
   203  	pos   int // position (start) of last token
   204  }
   205  
   206  // parseExpr parses a boolean build tag expression.
   207  func parseExpr(text string) (x Expr, err error) {
   208  	defer func() {
   209  		if e := recover(); e != nil {
   210  			if e, ok := e.(*SyntaxError); ok {
   211  				err = e
   212  				return
   213  			}
   214  			panic(e) // unreachable unless parser has a bug
   215  		}
   216  	}()
   217  
   218  	p := &exprParser{s: text}
   219  	x = p.or()
   220  	if p.tok != "" {
   221  		panic(&SyntaxError{Offset: p.pos, Err: "unexpected token " + p.tok})
   222  	}
   223  	return x, nil
   224  }
   225  
   226  // or parses a sequence of || expressions.
   227  // On entry, the next input token has not yet been lexed.
   228  // On exit, the next input token has been lexed and is in p.tok.
   229  func (p *exprParser) or() Expr {
   230  	x := p.and()
   231  	for p.tok == "||" {
   232  		x = or(x, p.and())
   233  	}
   234  	return x
   235  }
   236  
   237  // and parses a sequence of && expressions.
   238  // On entry, the next input token has not yet been lexed.
   239  // On exit, the next input token has been lexed and is in p.tok.
   240  func (p *exprParser) and() Expr {
   241  	x := p.not()
   242  	for p.tok == "&&" {
   243  		x = and(x, p.not())
   244  	}
   245  	return x
   246  }
   247  
   248  // not parses a ! expression.
   249  // On entry, the next input token has not yet been lexed.
   250  // On exit, the next input token has been lexed and is in p.tok.
   251  func (p *exprParser) not() Expr {
   252  	p.lex()
   253  	if p.tok == "!" {
   254  		p.lex()
   255  		if p.tok == "!" {
   256  			panic(&SyntaxError{Offset: p.pos, Err: "double negation not allowed"})
   257  		}
   258  		return not(p.atom())
   259  	}
   260  	return p.atom()
   261  }
   262  
   263  // atom parses a tag or a parenthesized expression.
   264  // On entry, the next input token HAS been lexed.
   265  // On exit, the next input token has been lexed and is in p.tok.
   266  func (p *exprParser) atom() Expr {
   267  	// first token already in p.tok
   268  	if p.tok == "(" {
   269  		pos := p.pos
   270  		defer func() {
   271  			if e := recover(); e != nil {
   272  				if e, ok := e.(*SyntaxError); ok && e.Err == "unexpected end of expression" {
   273  					e.Err = "missing close paren"
   274  				}
   275  				panic(e)
   276  			}
   277  		}()
   278  		x := p.or()
   279  		if p.tok != ")" {
   280  			panic(&SyntaxError{Offset: pos, Err: "missing close paren"})
   281  		}
   282  		p.lex()
   283  		return x
   284  	}
   285  
   286  	if !p.isTag {
   287  		if p.tok == "" {
   288  			panic(&SyntaxError{Offset: p.pos, Err: "unexpected end of expression"})
   289  		}
   290  		panic(&SyntaxError{Offset: p.pos, Err: "unexpected token " + p.tok})
   291  	}
   292  	tok := p.tok
   293  	p.lex()
   294  	return tag(tok)
   295  }
   296  
   297  // lex finds and consumes the next token in the input stream.
   298  // On return, p.tok is set to the token text,
   299  // p.isTag reports whether the token was a tag,
   300  // and p.pos records the byte offset of the start of the token in the input stream.
   301  // If lex reaches the end of the input, p.tok is set to the empty string.
   302  // For any other syntax error, lex panics with a SyntaxError.
   303  func (p *exprParser) lex() {
   304  	p.isTag = false
   305  	for p.i < len(p.s) && (p.s[p.i] == ' ' || p.s[p.i] == '\t') {
   306  		p.i++
   307  	}
   308  	if p.i >= len(p.s) {
   309  		p.tok = ""
   310  		p.pos = p.i
   311  		return
   312  	}
   313  	switch p.s[p.i] {
   314  	case '(', ')', '!':
   315  		p.pos = p.i
   316  		p.i++
   317  		p.tok = p.s[p.pos:p.i]
   318  		return
   319  
   320  	case '&', '|':
   321  		if p.i+1 >= len(p.s) || p.s[p.i+1] != p.s[p.i] {
   322  			panic(&SyntaxError{Offset: p.i, Err: "invalid syntax at " + string(rune(p.s[p.i]))})
   323  		}
   324  		p.pos = p.i
   325  		p.i += 2
   326  		p.tok = p.s[p.pos:p.i]
   327  		return
   328  	}
   329  
   330  	tag := p.s[p.i:]
   331  	for i, c := range tag {
   332  		if !unicode.IsLetter(c) && !unicode.IsDigit(c) && c != '_' && c != '.' {
   333  			tag = tag[:i]
   334  			break
   335  		}
   336  	}
   337  	if tag == "" {
   338  		c, _ := utf8.DecodeRuneInString(p.s[p.i:])
   339  		panic(&SyntaxError{Offset: p.i, Err: "invalid syntax at " + string(c)})
   340  	}
   341  
   342  	p.pos = p.i
   343  	p.i += len(tag)
   344  	p.tok = p.s[p.pos:p.i]
   345  	p.isTag = true
   346  }
   347  
   348  // IsPlusBuild reports whether the line of text is a “// +build” constraint.
   349  // It only checks the prefix of the text, not that the expression itself parses.
   350  func IsPlusBuild(line string) bool {
   351  	_, ok := splitPlusBuild(line)
   352  	return ok
   353  }
   354  
   355  // splitPlusBuild splits apart the leading // +build prefix in line from the build expression itself.
   356  // It returns "", false if the input is not a // +build line or if the input contains multiple lines.
   357  func splitPlusBuild(line string) (expr string, ok bool) {
   358  	// A single trailing newline is OK; otherwise multiple lines are not.
   359  	if len(line) > 0 && line[len(line)-1] == '\n' {
   360  		line = line[:len(line)-1]
   361  	}
   362  	if strings.Contains(line, "\n") {
   363  		return "", false
   364  	}
   365  
   366  	if !strings.HasPrefix(line, "//") {
   367  		return "", false
   368  	}
   369  	line = line[len("//"):]
   370  	// Note the space is optional; "//+build" is recognized too.
   371  	line = strings.TrimSpace(line)
   372  
   373  	if !strings.HasPrefix(line, "+build") {
   374  		return "", false
   375  	}
   376  	line = line[len("+build"):]
   377  
   378  	// If strings.TrimSpace finds more to trim after removing the +build prefix,
   379  	// it means that the prefix was followed by a space, making this a +build line
   380  	// (as opposed to a +buildsomethingelse line).
   381  	// If line is empty, we had "// +build" by itself, which also counts.
   382  	trim := strings.TrimSpace(line)
   383  	if len(line) == len(trim) && line != "" {
   384  		return "", false
   385  	}
   386  
   387  	return trim, true
   388  }
   389  
   390  // parsePlusBuildExpr parses a legacy build tag expression (as used with “// +build”).
   391  func parsePlusBuildExpr(text string) Expr {
   392  	var x Expr
   393  	for _, clause := range strings.Fields(text) {
   394  		var y Expr
   395  		for _, lit := range strings.Split(clause, ",") {
   396  			var z Expr
   397  			var neg bool
   398  			if strings.HasPrefix(lit, "!!") || lit == "!" {
   399  				z = tag("ignore")
   400  			} else {
   401  				if strings.HasPrefix(lit, "!") {
   402  					neg = true
   403  					lit = lit[len("!"):]
   404  				}
   405  				if isValidTag(lit) {
   406  					z = tag(lit)
   407  				} else {
   408  					z = tag("ignore")
   409  				}
   410  				if neg {
   411  					z = not(z)
   412  				}
   413  			}
   414  			if y == nil {
   415  				y = z
   416  			} else {
   417  				y = and(y, z)
   418  			}
   419  		}
   420  		if x == nil {
   421  			x = y
   422  		} else {
   423  			x = or(x, y)
   424  		}
   425  	}
   426  	if x == nil {
   427  		x = tag("ignore")
   428  	}
   429  	return x
   430  }
   431  
   432  // isValidTag reports whether the word is a valid build tag.
   433  // Tags must be letters, digits, underscores or dots.
   434  // Unlike in Go identifiers, all digits are fine (e.g., "386").
   435  func isValidTag(word string) bool {
   436  	if word == "" {
   437  		return false
   438  	}
   439  	for _, c := range word {
   440  		if !unicode.IsLetter(c) && !unicode.IsDigit(c) && c != '_' && c != '.' {
   441  			return false
   442  		}
   443  	}
   444  	return true
   445  }
   446  
   447  var errComplex = errors.New("expression too complex for // +build lines")
   448  
   449  // PlusBuildLines returns a sequence of “// +build” lines that evaluate to the build expression x.
   450  // If the expression is too complex to convert directly to “// +build” lines, PlusBuildLines returns an error.
   451  func PlusBuildLines(x Expr) ([]string, error) {
   452  	// Push all NOTs to the expression leaves, so that //go:build !(x && y) can be treated as !x || !y.
   453  	// This rewrite is both efficient and commonly needed, so it's worth doing.
   454  	// Essentially all other possible rewrites are too expensive and too rarely needed.
   455  	x = pushNot(x, false)
   456  
   457  	// Split into AND of ORs of ANDs of literals (tag or NOT tag).
   458  	var split [][][]Expr
   459  	for _, or := range appendSplitAnd(nil, x) {
   460  		var ands [][]Expr
   461  		for _, and := range appendSplitOr(nil, or) {
   462  			var lits []Expr
   463  			for _, lit := range appendSplitAnd(nil, and) {
   464  				switch lit.(type) {
   465  				case *TagExpr, *NotExpr:
   466  					lits = append(lits, lit)
   467  				default:
   468  					return nil, errComplex
   469  				}
   470  			}
   471  			ands = append(ands, lits)
   472  		}
   473  		split = append(split, ands)
   474  	}
   475  
   476  	// If all the ORs have length 1 (no actual OR'ing going on),
   477  	// push the top-level ANDs to the bottom level, so that we get
   478  	// one // +build line instead of many.
   479  	maxOr := 0
   480  	for _, or := range split {
   481  		if maxOr < len(or) {
   482  			maxOr = len(or)
   483  		}
   484  	}
   485  	if maxOr == 1 {
   486  		var lits []Expr
   487  		for _, or := range split {
   488  			lits = append(lits, or[0]...)
   489  		}
   490  		split = [][][]Expr{{lits}}
   491  	}
   492  
   493  	// Prepare the +build lines.
   494  	var lines []string
   495  	for _, or := range split {
   496  		line := "// +build"
   497  		for _, and := range or {
   498  			clause := ""
   499  			for i, lit := range and {
   500  				if i > 0 {
   501  					clause += ","
   502  				}
   503  				clause += lit.String()
   504  			}
   505  			line += " " + clause
   506  		}
   507  		lines = append(lines, line)
   508  	}
   509  
   510  	return lines, nil
   511  }
   512  
   513  // pushNot applies DeMorgan's law to push negations down the expression,
   514  // so that only tags are negated in the result.
   515  // (It applies the rewrites !(X && Y) => (!X || !Y) and !(X || Y) => (!X && !Y).)
   516  func pushNot(x Expr, not bool) Expr {
   517  	switch x := x.(type) {
   518  	default:
   519  		// unreachable
   520  		return x
   521  	case *NotExpr:
   522  		if _, ok := x.X.(*TagExpr); ok && !not {
   523  			return x
   524  		}
   525  		return pushNot(x.X, !not)
   526  	case *TagExpr:
   527  		if not {
   528  			return &NotExpr{X: x}
   529  		}
   530  		return x
   531  	case *AndExpr:
   532  		x1 := pushNot(x.X, not)
   533  		y1 := pushNot(x.Y, not)
   534  		if not {
   535  			return or(x1, y1)
   536  		}
   537  		if x1 == x.X && y1 == x.Y {
   538  			return x
   539  		}
   540  		return and(x1, y1)
   541  	case *OrExpr:
   542  		x1 := pushNot(x.X, not)
   543  		y1 := pushNot(x.Y, not)
   544  		if not {
   545  			return and(x1, y1)
   546  		}
   547  		if x1 == x.X && y1 == x.Y {
   548  			return x
   549  		}
   550  		return or(x1, y1)
   551  	}
   552  }
   553  
   554  // appendSplitAnd appends x to list while splitting apart any top-level && expressions.
   555  // For example, appendSplitAnd({W}, X && Y && Z) = {W, X, Y, Z}.
   556  func appendSplitAnd(list []Expr, x Expr) []Expr {
   557  	if x, ok := x.(*AndExpr); ok {
   558  		list = appendSplitAnd(list, x.X)
   559  		list = appendSplitAnd(list, x.Y)
   560  		return list
   561  	}
   562  	return append(list, x)
   563  }
   564  
   565  // appendSplitOr appends x to list while splitting apart any top-level || expressions.
   566  // For example, appendSplitOr({W}, X || Y || Z) = {W, X, Y, Z}.
   567  func appendSplitOr(list []Expr, x Expr) []Expr {
   568  	if x, ok := x.(*OrExpr); ok {
   569  		list = appendSplitOr(list, x.X)
   570  		list = appendSplitOr(list, x.Y)
   571  		return list
   572  	}
   573  	return append(list, x)
   574  }
   575  

View as plain text