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 "bytes"
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 []byte // for example, “linux” or “cgo”
43 }
44 45 func (x *TagExpr) isExpr() {}
46 47 func (x *TagExpr) Eval(ok func(tag []byte) 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 []byte) 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 []byte) 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 []byte) 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) []byte {
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 []byte) 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) []byte {
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 []byte // 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 []byte) (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 []byte) 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 []byte) (expr []byte, 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 bytes.Contains(line, "\n") {
178 return "", false
179 }
180 181 if !bytes.HasPrefix(line, "//go:build") {
182 return "", false
183 }
184 185 line = bytes.TrimSpace(line)
186 line = line[len("//go:build"):]
187 188 // If bytes.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 := bytes.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 []byte // input string
203 i int // next read location in s
204 205 tok []byte // 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 []byte) (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 " + p.s[p.i:p.i+1]})
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 " + []byte(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 []byte) 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 []byte) (expr []byte, 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 bytes.Contains(line, "\n") {
373 return "", false
374 }
375 376 if !bytes.HasPrefix(line, "//") {
377 return "", false
378 }
379 line = line[len("//"):]
380 // Note the space is optional; "//+build" is recognized too.
381 line = bytes.TrimSpace(line)
382 383 if !bytes.HasPrefix(line, "+build") {
384 return "", false
385 }
386 line = line[len("+build"):]
387 388 // If bytes.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 := bytes.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 []byte) (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 bytes.Fields(text) {
410 var y Expr
411 for _, lit := range bytes.Split(clause, ",") {
412 var z Expr
413 var neg bool
414 if bytes.HasPrefix(lit, "!!") || lit == "!" {
415 z = tag("ignore")
416 } else {
417 if bytes.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 []byte) 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) ([][]byte, 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 [][]byte
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