1 /* Copyright 2018 The Bazel Authors. All rights reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 */ 15 16 package resolve 17 18 import ( 19 "log" 20 21 "github.com/bazelbuild/bazel-gazelle/config" 22 "github.com/bazelbuild/bazel-gazelle/label" 23 "github.com/bazelbuild/bazel-gazelle/repo" 24 "github.com/bazelbuild/bazel-gazelle/rule" 25 ) 26 27 // ImportSpec describes a library to be imported. Imp is an import string for 28 // the library. Lang is the language in which the import string appears (this 29 // should match Resolver.Name). 30 type ImportSpec struct { 31 Lang, Imp string 32 } 33 34 // Resolver is an interface that language extensions can implement to resolve 35 // dependencies in rules they generate. 36 type Resolver interface { 37 // Name returns the name of the language. This should be a prefix of the 38 // kinds of rules generated by the language, e.g., "go" for the Go extension 39 // since it generates "go_library" rules. 40 Name() string 41 42 // Imports returns a list of ImportSpecs that can be used to import the rule 43 // r. This is used to populate RuleIndex. 44 // 45 // If nil is returned, the rule will not be indexed. If any non-nil slice is 46 // returned, including an empty slice, the rule will be indexed. 47 Imports(c *config.Config, r *rule.Rule, f *rule.File) []ImportSpec 48 49 // Embeds returns a list of labels of rules that the given rule embeds. If 50 // a rule is embedded by another importable rule of the same language, only 51 // the embedding rule will be indexed. The embedding rule will inherit 52 // the imports of the embedded rule. 53 Embeds(r *rule.Rule, from label.Label) []label.Label 54 55 // Resolve translates imported libraries for a given rule into Bazel 56 // dependencies. Information about imported libraries is returned for each 57 // rule generated by language.GenerateRules in 58 // language.GenerateResult.Imports. Resolve generates a "deps" attribute (or 59 // the appropriate language-specific equivalent) for each import according to 60 // language-specific rules and heuristics. 61 Resolve(c *config.Config, ix *RuleIndex, rc *repo.RemoteCache, r *rule.Rule, imports interface{}, from label.Label) 62 } 63 64 // CrossResolver is an interface that language extensions can implement to provide 65 // custom dependency resolution logic for other languages. 66 type CrossResolver interface { 67 // CrossResolve attempts to resolve an import string to a rule for languages 68 // other than the implementing extension. lang is the langauge of the rule 69 // with the dependency. 70 CrossResolve(c *config.Config, ix *RuleIndex, imp ImportSpec, lang string) []FindResult 71 } 72 73 // RuleIndex is a table of rules in a workspace, indexed by label and by 74 // import path. Used by Resolver to map import paths to labels. 75 type RuleIndex struct { 76 rules []*ruleRecord 77 labelMap map[label.Label]*ruleRecord 78 importMap map[ImportSpec][]*ruleRecord 79 mrslv func(r *rule.Rule, pkgRel string) Resolver 80 crossResolvers []CrossResolver 81 } 82 83 // ruleRecord contains information about a rule relevant to import indexing. 84 type ruleRecord struct { 85 rule *rule.Rule 86 label label.Label 87 file *rule.File 88 89 // importedAs is a list of ImportSpecs by which this rule may be imported. 90 // Used to build a map from ImportSpecs to ruleRecords. 91 importedAs []ImportSpec 92 93 // embeds is the transitive closure of labels for rules that this rule embeds 94 // (as determined by the Embeds method). This only includes rules in the same 95 // language (i.e., it includes a go_library embedding a go_proto_library, but 96 // not a go_proto_library embedding a proto_library). 97 embeds []label.Label 98 99 // embedded indicates whether another rule of the same language embeds this 100 // rule. Embedded rules should not be indexed. 101 embedded bool 102 103 didCollectEmbeds bool 104 105 // lang records the language that this import is relevant for. 106 // Due to the presence of mapped kinds, it's otherwise 107 // impossible to know the underlying builtin rule type for an 108 // arbitrary import. 109 lang string 110 } 111 112 // NewRuleIndex creates a new index. 113 // 114 // kindToResolver is a map from rule kinds (for example, "go_library") to 115 // Resolvers that support those kinds. 116 func NewRuleIndex(mrslv func(r *rule.Rule, pkgRel string) Resolver, exts ...interface{}) *RuleIndex { 117 var crossResolvers []CrossResolver 118 for _, e := range exts { 119 if cr, ok := e.(CrossResolver); ok { 120 crossResolvers = append(crossResolvers, cr) 121 } 122 } 123 return &RuleIndex{ 124 labelMap: make(map[label.Label]*ruleRecord), 125 mrslv: mrslv, 126 crossResolvers: crossResolvers, 127 } 128 } 129 130 // AddRule adds a rule r to the index. The rule will only be indexed if there 131 // is a known resolver for the rule's kind and Resolver.Imports returns a 132 // non-nil slice. 133 // 134 // AddRule may only be called before Finish. 135 func (ix *RuleIndex) AddRule(c *config.Config, r *rule.Rule, f *rule.File) { 136 var lang string 137 var imps []ImportSpec 138 if rslv := ix.mrslv(r, f.Pkg); rslv != nil { 139 lang = rslv.Name() 140 if passesLanguageFilter(c.Langs, lang) { 141 imps = rslv.Imports(c, r, f) 142 } 143 } 144 // If imps == nil, the rule is not importable. If imps is the empty slice, 145 // it may still be importable if it embeds importable libraries. 146 if imps == nil { 147 return 148 } 149 150 record := &ruleRecord{ 151 rule: r, 152 label: label.New(c.RepoName, f.Pkg, r.Name()), 153 file: f, 154 importedAs: imps, 155 lang: lang, 156 } 157 if _, ok := ix.labelMap[record.label]; ok { 158 log.Printf("multiple rules found with label %s", record.label) 159 return 160 } 161 ix.rules = append(ix.rules, record) 162 ix.labelMap[record.label] = record 163 } 164 165 // Finish constructs the import index and performs any other necessary indexing 166 // actions after all rules have been added. This step is necessary because 167 // a rule may be indexed differently based on what rules are added later. 168 // 169 // Finish must be called after all AddRule calls and before any 170 // FindRulesByImport calls. 171 func (ix *RuleIndex) Finish() { 172 for _, r := range ix.rules { 173 ix.collectEmbeds(r) 174 } 175 ix.buildImportIndex() 176 } 177 178 func (ix *RuleIndex) collectEmbeds(r *ruleRecord) { 179 if r.didCollectEmbeds { 180 return 181 } 182 resolver := ix.mrslv(r.rule, r.file.Pkg) 183 r.didCollectEmbeds = true 184 embedLabels := resolver.Embeds(r.rule, r.label) 185 r.embeds = embedLabels 186 for _, e := range embedLabels { 187 er, ok := ix.findRuleByLabel(e, r.label) 188 if !ok { 189 continue 190 } 191 ix.collectEmbeds(er) 192 erResolver := ix.mrslv(er.rule, er.file.Pkg) 193 if resolver.Name() == erResolver.Name() { 194 er.embedded = true 195 r.embeds = append(r.embeds, er.embeds...) 196 } 197 r.importedAs = append(r.importedAs, er.importedAs...) 198 } 199 } 200 201 // buildImportIndex constructs the map used by FindRulesByImport. 202 func (ix *RuleIndex) buildImportIndex() { 203 ix.importMap = make(map[ImportSpec][]*ruleRecord) 204 for _, r := range ix.rules { 205 if r.embedded { 206 continue 207 } 208 indexed := make(map[ImportSpec]bool) 209 for _, imp := range r.importedAs { 210 if indexed[imp] { 211 continue 212 } 213 indexed[imp] = true 214 ix.importMap[imp] = append(ix.importMap[imp], r) 215 } 216 } 217 } 218 219 func (ix *RuleIndex) findRuleByLabel(label label.Label, from label.Label) (*ruleRecord, bool) { 220 label = label.Abs(from.Repo, from.Pkg) 221 r, ok := ix.labelMap[label] 222 return r, ok 223 } 224 225 type FindResult struct { 226 // Label is the absolute label (including repository and package name) for 227 // a matched rule. 228 Label label.Label 229 230 // Embeds is the transitive closure of labels for rules that the matched 231 // rule embeds. It may contains duplicates and does not include the label 232 // for the rule itself. 233 Embeds []label.Label 234 } 235 236 // FindRulesByImport attempts to resolve an import string to a rule record. 237 // imp is the import to resolve (which includes the target language). lang is 238 // the language of the rule with the dependency (for example, in 239 // go_proto_library, imp will have ProtoLang and lang will be GoLang). 240 // from is the rule which is doing the dependency. This is used to check 241 // vendoring visibility and to check for self-imports. 242 // 243 // FindRulesByImport returns a list of rules, since any number of rules may 244 // provide the same import. Callers may need to resolve ambiguities using 245 // language-specific heuristics. 246 // 247 // DEPRECATED: use FindRulesByImportWithConfig instead 248 func (ix *RuleIndex) FindRulesByImport(imp ImportSpec, lang string) []FindResult { 249 matches := ix.importMap[imp] 250 results := make([]FindResult, 0, len(matches)) 251 for _, m := range matches { 252 if m.lang != lang { 253 continue 254 } 255 results = append(results, FindResult{ 256 Label: m.label, 257 Embeds: m.embeds, 258 }) 259 } 260 return results 261 } 262 263 // FindRulesByImportWithConfig attempts to resolve an import to a rule first by 264 // checking the rule index, then if no matches are found any registered 265 // CrossResolve implementations are called. 266 func (ix *RuleIndex) FindRulesByImportWithConfig(c *config.Config, imp ImportSpec, lang string) []FindResult { 267 results := ix.FindRulesByImport(imp, lang) 268 if len(results) > 0 { 269 return results 270 } 271 for _, cr := range ix.crossResolvers { 272 results = append(results, cr.CrossResolve(c, ix, imp, lang)...) 273 } 274 return results 275 } 276 277 // IsSelfImport returns true if the result's label matches the given label 278 // or the result's rule transitively embeds the rule with the given label. 279 // Self imports cause cyclic dependencies, so the caller may want to omit 280 // the dependency or report an error. 281 func (r FindResult) IsSelfImport(from label.Label) bool { 282 if from.Equal(r.Label) { 283 return true 284 } 285 for _, e := range r.Embeds { 286 if from.Equal(e) { 287 return true 288 } 289 } 290 return false 291 } 292 293 // passesLanguageFilter returns true if the filter is empty (disabled) or if the 294 // given language name appears in it. 295 func passesLanguageFilter(langFilter []string, langName string) bool { 296 if len(langFilter) == 0 { 297 return true 298 } 299 for _, l := range langFilter { 300 if l == langName { 301 return true 302 } 303 } 304 return false 305 } 306