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