Improve performance of "Evaluate build tags as true and false" feature (#2058)
This PR provides an alternative way of implementing #1938 (i.e.
evaluating both `tag` and `!tag` as true when evaluating build
constraints).
The way it was implemented originally has exponential time complexity
with the number of provided build tags. This made gazelle unusable on
projects with a relatively large number of tags, as the run would never
end.
This implementation leverages the existing `dropNegationForIgnoredTags`
to manipulate the tag expression.
Fixes #1262 in a more efficient way than what #1938 implemented.
diff --git a/language/go/build_constraints.go b/language/go/build_constraints.go
index 8bae3ce..4d681aa 100644
--- a/language/go/build_constraints.go
+++ b/language/go/build_constraints.go
@@ -52,7 +52,7 @@
return nil, err
}
- return newBuildTags(x)
+ return newBuildTags(x), nil
}
var fullConstraint constraint.Expr
@@ -88,7 +88,7 @@
return nil, nil
}
- return newBuildTags(fullConstraint)
+ return newBuildTags(fullConstraint), nil
}
// buildTags represents the build tags specified in a file.
@@ -103,21 +103,14 @@
// newBuildTags will return a new buildTags structure with any
// ignored tags filtered out from the provided constraints.
-func newBuildTags(x constraint.Expr) (*buildTags, error) {
- modified, err := dropNegationForIgnoredTags(pushNot(x, false))
- if err != nil {
- return nil, err
- }
-
- rawTags, err := collectTags(modified)
- if err != nil {
- return nil, err
- }
+func newBuildTags(x constraint.Expr) *buildTags {
+ modified := dropNegationForIgnoredTags(pushNot(x, false), isDefaultIgnoredTag)
+ rawTags := collectTags(modified)
return &buildTags{
expr: modified,
rawTags: rawTags,
- }, nil
+ }
}
func (b *buildTags) tags() []string {
@@ -149,16 +142,16 @@
// without having to worry that the result will be negated later on. Ignored tags should always
// evaluate to true, regardless of whether they are negated or not leaving the final evaluation
// to happen at compile time by the compiler.
-func dropNegationForIgnoredTags(expr constraint.Expr) (constraint.Expr, error) {
+func dropNegationForIgnoredTags(expr constraint.Expr, isIgnoredTag func(tag string) bool) constraint.Expr {
if expr == nil {
- return nil, nil
+ return nil
}
switch x := expr.(type) {
case *constraint.TagExpr:
return &constraint.TagExpr{
Tag: x.Tag,
- }, nil
+ }
case *constraint.NotExpr:
var toRet constraint.Expr
@@ -168,58 +161,40 @@
Tag: tag.Tag,
}
} else {
- fixed, err := dropNegationForIgnoredTags(x.X)
- if err != nil {
- return nil, err
- }
+ fixed := dropNegationForIgnoredTags(x.X, isIgnoredTag)
toRet = &constraint.NotExpr{X: fixed}
}
- return toRet, nil
+ return toRet
case *constraint.AndExpr:
- a, err := dropNegationForIgnoredTags(x.X)
- if err != nil {
- return nil, err
- }
-
- b, err := dropNegationForIgnoredTags(x.Y)
- if err != nil {
- return nil, err
- }
+ a := dropNegationForIgnoredTags(x.X, isIgnoredTag)
+ b := dropNegationForIgnoredTags(x.Y, isIgnoredTag)
return &constraint.AndExpr{
X: a,
Y: b,
- }, nil
+ }
case *constraint.OrExpr:
- a, err := dropNegationForIgnoredTags(x.X)
- if err != nil {
- return nil, err
- }
-
- b, err := dropNegationForIgnoredTags(x.Y)
- if err != nil {
- return nil, err
- }
-
+ a := dropNegationForIgnoredTags(x.X, isIgnoredTag)
+ b := dropNegationForIgnoredTags(x.Y, isIgnoredTag)
return &constraint.OrExpr{
X: a,
Y: b,
- }, nil
+ }
default:
- return nil, fmt.Errorf("unknown constraint type: %T", x)
+ panic(fmt.Errorf("unknown constraint type: %T", x))
}
}
-// filterTags will traverse the provided constraint.Expr, recursively, and call
+// visitTags will traverse the provided constraint.Expr, recursively, and call
// the user provided ok func on concrete constraint.TagExpr structures. If the provided
// func returns true, the tag in question is kept, otherwise it is filtered out.
-func visitTags(expr constraint.Expr, visit func(string)) (err error) {
+func visitTags(expr constraint.Expr, visit func(string)) {
if expr == nil {
- return nil
+ return
}
switch x := expr.(type) {
@@ -227,37 +202,29 @@
visit(x.Tag)
case *constraint.NotExpr:
- err = visitTags(x.X, visit)
+ visitTags(x.X, visit)
case *constraint.AndExpr:
- err = visitTags(x.X, visit)
- if err == nil {
- err = visitTags(x.Y, visit)
- }
+ visitTags(x.X, visit)
+ visitTags(x.Y, visit)
case *constraint.OrExpr:
- err = visitTags(x.X, visit)
- if err == nil {
- err = visitTags(x.Y, visit)
- }
+ visitTags(x.X, visit)
+ visitTags(x.Y, visit)
default:
- return fmt.Errorf("unknown constraint type: %T", x)
+ panic(fmt.Errorf("unknown constraint type: %T", x))
}
return
}
-func collectTags(expr constraint.Expr) ([]string, error) {
+func collectTags(expr constraint.Expr) []string {
var tags []string
- err := visitTags(expr, func(tag string) {
+ visitTags(expr, func(tag string) {
tags = append(tags, tag)
})
- if err != nil {
- return nil, err
- }
-
- return tags, err
+ return tags
}
// cgoTagsAndOpts contains compile or link options which should only be applied
@@ -304,15 +271,15 @@
return nil, err
}
- return newBuildTags(x)
+ return newBuildTags(x), nil
}
-// isIgnoredTag returns whether the tag is "cgo", "purego", "race", "msan" or is a release tag.
+// isDefaultIgnoredTag returns whether the tag is "cgo", "purego", "race", "msan" or is a release tag.
// Release tags match the pattern "go[0-9]\.[0-9]+".
// Gazelle won't consider whether an ignored tag is satisfied when evaluating
// build constraints for a file and will instead defer to the compiler at compile
// time.
-func isIgnoredTag(tag string) bool {
+func isDefaultIgnoredTag(tag string) bool {
if tag == "cgo" || tag == "purego" || tag == "race" || tag == "msan" {
return true
}
diff --git a/language/go/build_constraints_test.go b/language/go/build_constraints_test.go
index fc31182..680b7ab 100644
--- a/language/go/build_constraints_test.go
+++ b/language/go/build_constraints_test.go
@@ -60,10 +60,7 @@
},
} {
t.Run(tc.desc, func(t *testing.T) {
- bt, err := newBuildTags(tc.input)
- if err != nil {
- t.Fatal(err)
- }
+ bt := newBuildTags(tc.input)
if diff := cmp.Diff(tc.want, bt.expr); diff != "" {
t.Errorf("(-want, +got): %s", diff)
}
diff --git a/language/go/config.go b/language/go/config.go
index 89ac3f4..ac7f089 100644
--- a/language/go/config.go
+++ b/language/go/config.go
@@ -41,16 +41,6 @@
var minimumRulesGoVersion = version.Version{0, 29, 0}
-type tagSet map[string]struct{}
-
-func (ts tagSet) clone() tagSet {
- c := make(tagSet, len(ts))
- for k, v := range ts {
- c[k] = v
- }
- return c
-}
-
// goConfig contains configuration values related to Go rules.
type goConfig struct {
// The name under which the rules_go repository can be referenced from the
@@ -63,7 +53,7 @@
// genericTags is a set of tags that Gazelle considers to be true. Set with
// -build_tags or # gazelle:build_tags. Some tags, like gc, are always on.
- genericTags []tagSet
+ genericTags map[string]bool
// prefix is a prefix of an import path, used to generate importpath
// attributes. Set with -go_prefix or # gazelle:prefix.
@@ -188,10 +178,12 @@
goProtoCompilers: defaultGoProtoCompilers,
goGrpcCompilers: defaultGoGrpcCompilers,
goGenerateProto: true,
- genericTags: []tagSet{
- {"gc": struct{}{}},
- },
}
+ if gc.genericTags == nil {
+ gc.genericTags = make(map[string]bool)
+ }
+ // Add default tags
+ gc.genericTags["gc"] = true
return gc
}
@@ -201,9 +193,9 @@
func (gc *goConfig) clone() *goConfig {
gcCopy := *gc
- gcCopy.genericTags = make([]tagSet, 0, len(gc.genericTags))
- for _, ts := range gc.genericTags {
- gcCopy.genericTags = append(gcCopy.genericTags, ts.clone())
+ gcCopy.genericTags = make(map[string]bool)
+ for k, v := range gc.genericTags {
+ gcCopy.genericTags[k] = v
}
gcCopy.goProtoCompilers = gc.goProtoCompilers[:len(gc.goProtoCompilers):len(gc.goProtoCompilers)]
gcCopy.goGrpcCompilers = gc.goGrpcCompilers[:len(gc.goGrpcCompilers):len(gc.goGrpcCompilers)]
@@ -221,13 +213,7 @@
if strings.HasPrefix(t, "!") {
return fmt.Errorf("build tags can't be negated: %s", t)
}
- var newSets []tagSet
- for _, ts := range gc.genericTags {
- c := ts.clone()
- c[t] = struct{}{}
- newSets = append(newSets, c)
- }
- gc.genericTags = append(gc.genericTags, newSets...)
+ gc.genericTags[t] = true
}
return nil
}
@@ -594,6 +580,7 @@
case "build_tags":
if err := gc.setBuildTags(d.Value); err != nil {
log.Print(err)
+ continue
}
case "go_generate_proto":
diff --git a/language/go/config_test.go b/language/go/config_test.go
index 3ac54d8..e239c11 100644
--- a/language/go/config_test.go
+++ b/language/go/config_test.go
@@ -59,21 +59,6 @@
return c, langs, cexts
}
-func newTagSet(tags ...string) tagSet {
- ts := make(tagSet)
- for _, t := range tags {
- ts[t] = struct{}{}
- }
- return ts
-}
-
-var expectedBuildTags = []tagSet{
- newTagSet("gc"),
- newTagSet("gc", "foo"),
- newTagSet("gc", "bar"),
- newTagSet("gc", "foo", "bar"),
-}
-
func TestCommandLine(t *testing.T) {
c, _, _ := testConfig(
t,
@@ -83,8 +68,10 @@
"-external=vendored",
"-repo_root=.")
gc := getGoConfig(c)
- if diff := cmp.Diff(expectedBuildTags, gc.genericTags); diff != "" {
- t.Errorf("(-want, +got): %s", diff)
+ for _, tag := range []string{"foo", "bar", "gc"} {
+ if !gc.genericTags[tag] {
+ t.Errorf("expected tag %q to be set", tag)
+ }
}
if gc.prefix != "example.com/repo" {
t.Errorf(`got prefix %q; want "example.com/repo"`, gc.prefix)
@@ -114,8 +101,10 @@
cext.Configure(c, "test", f)
}
gc := getGoConfig(c)
- if diff := cmp.Diff(expectedBuildTags, gc.genericTags); diff != "" {
- t.Errorf("(-want, +got): %s", diff)
+ for _, tag := range []string{"foo", "bar", "gc"} {
+ if !gc.genericTags[tag] {
+ t.Errorf("expected tag %q to be set", tag)
+ }
}
if gc.prefix != "y" {
t.Errorf(`got prefix %q; want "y"`, gc.prefix)
diff --git a/language/go/fileinfo.go b/language/go/fileinfo.go
index 1d5d7c9..a4c75f9 100644
--- a/language/go/fileinfo.go
+++ b/language/go/fileinfo.go
@@ -569,8 +569,19 @@
}
goConf := getGoConfig(c)
- checker := func(tag string, ts tagSet) bool {
- if isIgnoredTag(tag) {
+
+ if tags != nil {
+ // Treat provided generic tags as "ignored tags", meaning that both
+ // `tag` and `!tag` are considered true when evaluating build constraints
+ isIgnoredTag := func(tag string) bool {
+ return goConf.genericTags[tag]
+ }
+
+ tags = newBuildTags(dropNegationForIgnoredTags(tags.expr, isIgnoredTag))
+ }
+
+ checker := func(tag string) bool {
+ if isDefaultIgnoredTag(tag) {
return true
}
if _, ok := rule.KnownOSSet[tag]; ok || tag == "unix" {
@@ -585,19 +596,13 @@
return false
}
return arch == tag
+
}
- _, ok := ts[tag]
- return ok
+ return goConf.genericTags[tag]
}
- for _, ts := range goConf.genericTags {
- c := func(tag string) bool { return checker(tag, ts) }
- if tags.eval(c) && cgoTags.eval(c) {
- return true
- }
- }
- return false
+ return tags.eval(checker) && cgoTags.eval(checker)
}
// rulesGoSupportsOS returns whether the os tag is recognized by the version of
diff --git a/language/go/fileinfo_test.go b/language/go/fileinfo_test.go
index 6c89ac6..9aac4af 100644
--- a/language/go/fileinfo_test.go
+++ b/language/go/fileinfo_test.go
@@ -386,7 +386,7 @@
defer os.RemoveAll(dir)
for _, tc := range []struct {
desc string
- genericTags string
+ genericTags map[string]bool
os, arch, filename, content string
want bool
}{
@@ -466,12 +466,12 @@
want: false,
}, {
desc: "tags all satisfied",
- genericTags: "a,b",
+ genericTags: map[string]bool{"a": true, "b": true},
content: "// +build a,b\n\npackage foo",
want: true,
}, {
desc: "tags some satisfied",
- genericTags: "a",
+ genericTags: map[string]bool{"a": true},
content: "// +build a,b\n\npackage foo",
want: false,
}, {
@@ -480,7 +480,7 @@
want: true,
}, {
desc: "tag satisfied negated",
- genericTags: "a",
+ genericTags: map[string]bool{"a": true},
content: "// +build !a\n\npackage foo",
want: true,
}, {
@@ -489,27 +489,27 @@
want: false,
}, {
desc: "tag group and satisfied",
- genericTags: "foo,bar",
+ genericTags: map[string]bool{"foo": true, "bar": true},
content: "// +build foo,bar\n\npackage foo",
want: true,
}, {
desc: "tag group and unsatisfied",
- genericTags: "foo",
+ genericTags: map[string]bool{"foo": true},
content: "// +build foo,bar\n\npackage foo",
want: false,
}, {
desc: "tag line or satisfied",
- genericTags: "foo",
+ genericTags: map[string]bool{"foo": true},
content: "// +build foo bar\n\npackage foo",
want: true,
}, {
desc: "tag line or unsatisfied",
- genericTags: "foo",
+ genericTags: map[string]bool{"foo": true},
content: "// +build !foo bar\n\npackage foo",
want: true,
}, {
desc: "tag lines and satisfied",
- genericTags: "foo,bar",
+ genericTags: map[string]bool{"foo": true, "bar": true},
content: `
// +build foo
// +build bar
@@ -518,7 +518,7 @@
want: true,
}, {
desc: "tag lines and unsatisfied",
- genericTags: "foo",
+ genericTags: map[string]bool{"foo": true},
content: `
// +build foo
// +build bar
@@ -528,7 +528,7 @@
}, {
desc: "cgo tags satisfied",
os: "linux",
- genericTags: "foo",
+ genericTags: map[string]bool{"foo": true},
content: `
// +build foo
@@ -581,8 +581,9 @@
t.Run(tc.desc, func(t *testing.T) {
c, _, _ := testConfig(t)
gc := getGoConfig(c)
- if err := gc.setBuildTags(tc.genericTags); err != nil {
- t.Errorf("error setting build tags %q", tc.genericTags)
+ gc.genericTags = tc.genericTags
+ if gc.genericTags == nil {
+ gc.genericTags = map[string]bool{"gc": true}
}
filename := tc.filename
if filename == "" {
