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