main.go

Documentation: k8s.io/kubernetes/cmd/import-boss

     1  /*
     2  Copyright 2016 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  // import-boss enforces import restrictions in a given repository.
    18  package main
    19  
    20  import (
    21  	"flag"
    22  	"os"
    23  
    24  	"errors"
    25  	"fmt"
    26  	"path/filepath"
    27  	"regexp"
    28  	"sort"
    29  	"strings"
    30  	"time"
    31  
    32  	"github.com/spf13/pflag"
    33  	"golang.org/x/tools/go/packages"
    34  	"k8s.io/klog/v2"
    35  	"sigs.k8s.io/yaml"
    36  )
    37  
    38  const (
    39  	rulesFileName = ".import-restrictions"
    40  	goModFile     = "go.mod"
    41  )
    42  
    43  func main() {
    44  	klog.InitFlags(nil)
    45  	pflag.CommandLine.AddGoFlagSet(flag.CommandLine)
    46  	pflag.Parse()
    47  
    48  	pkgs, err := loadPkgs(pflag.Args()...)
    49  	if err != nil {
    50  		klog.Errorf("failed to load packages: %v", err)
    51  	}
    52  
    53  	pkgs = massage(pkgs)
    54  	boss := newBoss(pkgs)
    55  
    56  	var allErrs []error
    57  	for _, pkg := range pkgs {
    58  		if pkgErrs := boss.Verify(pkg); pkgErrs != nil {
    59  			allErrs = append(allErrs, pkgErrs...)
    60  		}
    61  	}
    62  
    63  	fail := false
    64  	for _, err := range allErrs {
    65  		if lister, ok := err.(interface{ Unwrap() []error }); ok {
    66  			for _, err := range lister.Unwrap() {
    67  				fmt.Printf("ERROR: %v\n", err)
    68  			}
    69  		} else {
    70  			fmt.Printf("ERROR: %v\n", err)
    71  		}
    72  		fail = true
    73  	}
    74  
    75  	if fail {
    76  		os.Exit(1)
    77  	}
    78  
    79  	klog.V(2).Info("Completed successfully.")
    80  }
    81  
    82  func loadPkgs(patterns ...string) ([]*packages.Package, error) {
    83  	cfg := packages.Config{
    84  		Mode: packages.NeedName | packages.NeedFiles | packages.NeedImports |
    85  			packages.NeedDeps | packages.NeedModule,
    86  		Tests: true,
    87  	}
    88  
    89  	klog.V(1).Infof("loading: %v", patterns)
    90  	tBefore := time.Now()
    91  	pkgs, err := packages.Load(&cfg, patterns...)
    92  	if err != nil {
    93  		return nil, err
    94  	}
    95  	klog.V(2).Infof("loaded %d pkg(s) in %v", len(pkgs), time.Since(tBefore))
    96  
    97  	var allErrs []error
    98  	for _, pkg := range pkgs {
    99  		var errs []error
   100  		for _, e := range pkg.Errors {
   101  			if e.Kind == packages.ListError || e.Kind == packages.ParseError {
   102  				errs = append(errs, e)
   103  			}
   104  		}
   105  		if len(errs) > 0 {
   106  			allErrs = append(allErrs, fmt.Errorf("error(s) in %q: %w", pkg.PkgPath, errors.Join(errs...)))
   107  		}
   108  	}
   109  	if len(allErrs) > 0 {
   110  		return nil, errors.Join(allErrs...)
   111  	}
   112  
   113  	return pkgs, nil
   114  }
   115  
   116  func massage(in []*packages.Package) []*packages.Package {
   117  	out := []*packages.Package{}
   118  
   119  	for _, pkg := range in {
   120  		klog.V(2).Infof("considering pkg: %q", pkg.PkgPath)
   121  
   122  		// Discard packages which represent the <pkg>.test result.  They don't seem
   123  		// to hold any interesting source info.
   124  		if strings.HasSuffix(pkg.PkgPath, ".test") {
   125  			klog.V(3).Infof("ignoring testbin pkg: %q", pkg.PkgPath)
   126  			continue
   127  		}
   128  
   129  		// Packages which end in "_test" have tests which use the special "_test"
   130  		// package suffix.  Packages which have test files must be tests.  Don't
   131  		// ask me, this is what packages.Load produces.
   132  		if strings.HasSuffix(pkg.PkgPath, "_test") || hasTestFiles(pkg.GoFiles) {
   133  			// NOTE: This syntax can be undone with unmassage().
   134  			pkg.PkgPath = strings.TrimSuffix(pkg.PkgPath, "_test") + " ((tests:" + pkg.Name + "))"
   135  			klog.V(3).Infof("renamed to: %q", pkg.PkgPath)
   136  		}
   137  		out = append(out, pkg)
   138  	}
   139  
   140  	return out
   141  }
   142  
   143  func unmassage(str string) string {
   144  	idx := strings.LastIndex(str, " ((")
   145  	if idx == -1 {
   146  		return str
   147  	}
   148  	return str[0:idx]
   149  }
   150  
   151  type ImportBoss struct {
   152  	// incomingImports holds all the packages importing the key.
   153  	incomingImports map[string][]string
   154  
   155  	// transitiveIncomingImports holds the transitive closure of
   156  	// incomingImports.
   157  	transitiveIncomingImports map[string][]string
   158  }
   159  
   160  func newBoss(pkgs []*packages.Package) *ImportBoss {
   161  	boss := &ImportBoss{
   162  		incomingImports:           map[string][]string{},
   163  		transitiveIncomingImports: map[string][]string{},
   164  	}
   165  
   166  	for _, pkg := range pkgs {
   167  		// Accumulate imports
   168  		for imp := range pkg.Imports {
   169  			boss.incomingImports[imp] = append(boss.incomingImports[imp], pkg.PkgPath)
   170  		}
   171  	}
   172  
   173  	boss.transitiveIncomingImports = transitiveClosure(boss.incomingImports)
   174  
   175  	return boss
   176  }
   177  
   178  func hasTestFiles(files []string) bool {
   179  	for _, f := range files {
   180  		if strings.HasSuffix(f, "_test.go") {
   181  			return true
   182  		}
   183  	}
   184  	return false
   185  }
   186  
   187  func (boss *ImportBoss) Verify(pkg *packages.Package) []error {
   188  	pkgDir := packageDir(pkg)
   189  	if pkgDir == "" {
   190  		// This Package has no usable files, e.g. only tests, which are modelled in
   191  		// a distinct Package.
   192  		return nil
   193  	}
   194  
   195  	restrictionFiles, err := recursiveRead(filepath.Join(pkgDir, rulesFileName))
   196  	if err != nil {
   197  		return []error{fmt.Errorf("error finding rules file: %w", err)}
   198  	}
   199  	if len(restrictionFiles) == 0 {
   200  		return nil
   201  	}
   202  
   203  	klog.V(2).Infof("verifying pkg %q (%s)", pkg.PkgPath, pkgDir)
   204  	var errs []error
   205  	errs = append(errs, boss.verifyRules(pkg, restrictionFiles)...)
   206  	errs = append(errs, boss.verifyInverseRules(pkg, restrictionFiles)...)
   207  	return errs
   208  }
   209  
   210  // packageDir tries to figure out the directory of the specified package.
   211  func packageDir(pkg *packages.Package) string {
   212  	if len(pkg.GoFiles) > 0 {
   213  		return filepath.Dir(pkg.GoFiles[0])
   214  	}
   215  	if len(pkg.IgnoredFiles) > 0 {
   216  		return filepath.Dir(pkg.IgnoredFiles[0])
   217  	}
   218  	return ""
   219  }
   220  
   221  type FileFormat struct {
   222  	Rules        []Rule
   223  	InverseRules []Rule
   224  
   225  	path string
   226  }
   227  
   228  // A single import restriction rule.
   229  type Rule struct {
   230  	// All import paths that match this regexp...
   231  	SelectorRegexp string
   232  	// ... must have one of these prefixes ...
   233  	AllowedPrefixes []string
   234  	// ... and must not have one of these prefixes.
   235  	ForbiddenPrefixes []string
   236  	// True if the rule is to be applied to transitive imports.
   237  	Transitive bool
   238  }
   239  
   240  // Disposition represents a decision or non-decision.
   241  type Disposition int
   242  
   243  const (
   244  	// DepForbidden means the dependency was explicitly forbidden by a rule.
   245  	DepForbidden Disposition = iota
   246  	// DepAllowed means the dependency was explicitly allowed by a rule.
   247  	DepAllowed
   248  	// DepAllowed means the dependency did not match any rule.
   249  	DepUnknown
   250  )
   251  
   252  // Evaluate considers this rule and decides if this dependency is allowed.
   253  func (r Rule) Evaluate(imp string) Disposition {
   254  	// To pass, an import muct be allowed and not forbidden.
   255  	// Check forbidden first.
   256  	for _, forbidden := range r.ForbiddenPrefixes {
   257  		klog.V(5).Infof("checking %q against forbidden prefix %q", imp, forbidden)
   258  		if hasPathPrefix(imp, forbidden) {
   259  			klog.V(5).Infof("this import of %q is forbidden", imp)
   260  			return DepForbidden
   261  		}
   262  	}
   263  	for _, allowed := range r.AllowedPrefixes {
   264  		klog.V(5).Infof("checking %q against allowed prefix %q", imp, allowed)
   265  		if hasPathPrefix(imp, allowed) {
   266  			klog.V(5).Infof("this import of %q is allowed", imp)
   267  			return DepAllowed
   268  		}
   269  	}
   270  	return DepUnknown
   271  }
   272  
   273  // recursiveRead collects all '.import-restriction' files, between the current directory,
   274  // and the module root.
   275  func recursiveRead(path string) ([]*FileFormat, error) {
   276  	restrictionFiles := make([]*FileFormat, 0)
   277  
   278  	for {
   279  		if _, err := os.Stat(path); err == nil {
   280  			rules, err := readFile(path)
   281  			if err != nil {
   282  				return nil, err
   283  			}
   284  
   285  			restrictionFiles = append(restrictionFiles, rules)
   286  		}
   287  
   288  		nextPath, removedDir := removeLastDir(path)
   289  		if nextPath == path || isGoModRoot(path) || removedDir == "src" {
   290  			break
   291  		}
   292  
   293  		path = nextPath
   294  	}
   295  
   296  	return restrictionFiles, nil
   297  }
   298  
   299  func readFile(path string) (*FileFormat, error) {
   300  	currentBytes, err := os.ReadFile(path)
   301  	if err != nil {
   302  		return nil, fmt.Errorf("couldn't read %v: %w", path, err)
   303  	}
   304  
   305  	var current FileFormat
   306  	err = yaml.Unmarshal(currentBytes, &current)
   307  	if err != nil {
   308  		return nil, fmt.Errorf("couldn't unmarshal %v: %w", path, err)
   309  	}
   310  	current.path = path
   311  	return &current, nil
   312  }
   313  
   314  // isGoModRoot checks if a directory is the root directory for a package
   315  // by checking for the existence of a 'go.mod' file in that directory.
   316  func isGoModRoot(path string) bool {
   317  	_, err := os.Stat(filepath.Join(filepath.Dir(path), goModFile))
   318  	return err == nil
   319  }
   320  
   321  // removeLastDir removes the last directory, but leaves the file name
   322  // unchanged. It returns the new path and the removed directory. So:
   323  // "a/b/c/file" -> ("a/b/file", "c")
   324  func removeLastDir(path string) (newPath, removedDir string) {
   325  	dir, file := filepath.Split(path)
   326  	dir = strings.TrimSuffix(dir, string(filepath.Separator))
   327  	return filepath.Join(filepath.Dir(dir), file), filepath.Base(dir)
   328  }
   329  
   330  func (boss *ImportBoss) verifyRules(pkg *packages.Package, restrictionFiles []*FileFormat) []error {
   331  	klog.V(3).Infof("verifying pkg %q rules", pkg.PkgPath)
   332  
   333  	// compile all Selector regex in all restriction files
   334  	selectors := make([][]*regexp.Regexp, len(restrictionFiles))
   335  	for i, restrictionFile := range restrictionFiles {
   336  		for _, r := range restrictionFile.Rules {
   337  			re, err := regexp.Compile(r.SelectorRegexp)
   338  			if err != nil {
   339  				return []error{
   340  					fmt.Errorf("regexp `%s` in file %q doesn't compile: %w", r.SelectorRegexp, restrictionFile.path, err),
   341  				}
   342  			}
   343  
   344  			selectors[i] = append(selectors[i], re)
   345  		}
   346  	}
   347  
   348  	realPkgPath := unmassage(pkg.PkgPath)
   349  
   350  	direct, indirect := transitiveImports(pkg)
   351  	isDirect := map[string]bool{}
   352  	for _, imp := range direct {
   353  		isDirect[imp] = true
   354  	}
   355  	relate := func(imp string) string {
   356  		if isDirect[imp] {
   357  			return "->"
   358  		}
   359  		return "-->"
   360  	}
   361  
   362  	var errs []error
   363  	for _, imp := range uniq(direct, indirect) {
   364  		if unmassage(imp) == realPkgPath {
   365  			// Tests in package "foo_test" depend on the test package for
   366  			// "foo" (if both exist in a giver directory).
   367  			continue
   368  		}
   369  		klog.V(4).Infof("considering import %q %s %q", pkg.PkgPath, relate(imp), imp)
   370  		matched := false
   371  		decided := false
   372  		for i, file := range restrictionFiles {
   373  			klog.V(4).Infof("rules file %s", file.path)
   374  			for j, rule := range file.Rules {
   375  				if !rule.Transitive && !isDirect[imp] {
   376  					continue
   377  				}
   378  				matching := selectors[i][j].MatchString(imp)
   379  				if !matching {
   380  					continue
   381  				}
   382  				matched = true
   383  				klog.V(6).Infof("selector %v matches %q", rule.SelectorRegexp, imp)
   384  
   385  				disp := rule.Evaluate(imp)
   386  				if disp == DepAllowed {
   387  					decided = true
   388  					break // no further rules, next file
   389  				} else if disp == DepForbidden {
   390  					errs = append(errs, fmt.Errorf("%q %s %q is forbidden by %s", pkg.PkgPath, relate(imp), imp, file.path))
   391  					decided = true
   392  					break // no further rules, next file
   393  				}
   394  			}
   395  			if decided {
   396  				break // no further files, next import
   397  			}
   398  		}
   399  		if matched && !decided {
   400  			klog.V(5).Infof("%q %s %q did not match any rule", pkg, relate(imp), imp)
   401  			errs = append(errs, fmt.Errorf("%q %s %q did not match any rule", pkg.PkgPath, relate(imp), imp))
   402  		}
   403  	}
   404  
   405  	if len(errs) > 0 {
   406  		return errs
   407  	}
   408  
   409  	return nil
   410  }
   411  
   412  func uniq(slices ...[]string) []string {
   413  	m := map[string]bool{}
   414  	for _, sl := range slices {
   415  		for _, str := range sl {
   416  			m[str] = true
   417  		}
   418  	}
   419  	ret := []string{}
   420  	for str := range m {
   421  		ret = append(ret, str)
   422  	}
   423  	sort.Strings(ret)
   424  	return ret
   425  }
   426  
   427  func hasPathPrefix(path, prefix string) bool {
   428  	if prefix == "" || path == prefix {
   429  		return true
   430  	}
   431  	if !strings.HasSuffix(path, string(filepath.Separator)) {
   432  		prefix += string(filepath.Separator)
   433  	}
   434  	return strings.HasPrefix(path, prefix)
   435  }
   436  
   437  func transitiveImports(pkg *packages.Package) ([]string, []string) {
   438  	direct := []string{}
   439  	indirect := []string{}
   440  	seen := map[string]bool{}
   441  	for _, imp := range pkg.Imports {
   442  		direct = append(direct, imp.PkgPath)
   443  		dfsImports(&indirect, seen, imp)
   444  	}
   445  	return direct, indirect
   446  }
   447  
   448  func dfsImports(dest *[]string, seen map[string]bool, p *packages.Package) {
   449  	for _, p2 := range p.Imports {
   450  		if seen[p2.PkgPath] {
   451  			continue
   452  		}
   453  		seen[p2.PkgPath] = true
   454  		*dest = append(*dest, p2.PkgPath)
   455  		dfsImports(dest, seen, p2)
   456  	}
   457  }
   458  
   459  // verifyInverseRules checks that all packages that import a package are allowed to import it.
   460  func (boss *ImportBoss) verifyInverseRules(pkg *packages.Package, restrictionFiles []*FileFormat) []error {
   461  	klog.V(3).Infof("verifying pkg %q inverse-rules", pkg.PkgPath)
   462  
   463  	// compile all Selector regex in all restriction files
   464  	selectors := make([][]*regexp.Regexp, len(restrictionFiles))
   465  	for i, restrictionFile := range restrictionFiles {
   466  		for _, r := range restrictionFile.InverseRules {
   467  			re, err := regexp.Compile(r.SelectorRegexp)
   468  			if err != nil {
   469  				return []error{
   470  					fmt.Errorf("regexp `%s` in file %q doesn't compile: %w", r.SelectorRegexp, restrictionFile.path, err),
   471  				}
   472  			}
   473  
   474  			selectors[i] = append(selectors[i], re)
   475  		}
   476  	}
   477  
   478  	realPkgPath := unmassage(pkg.PkgPath)
   479  
   480  	isDirect := map[string]bool{}
   481  	for _, imp := range boss.incomingImports[pkg.PkgPath] {
   482  		isDirect[imp] = true
   483  	}
   484  	relate := func(imp string) string {
   485  		if isDirect[imp] {
   486  			return "<-"
   487  		}
   488  		return "<--"
   489  	}
   490  
   491  	var errs []error
   492  	for _, imp := range boss.transitiveIncomingImports[pkg.PkgPath] {
   493  		if unmassage(imp) == realPkgPath {
   494  			// Tests in package "foo_test" depend on the test package for
   495  			// "foo" (if both exist in a giver directory).
   496  			continue
   497  		}
   498  		klog.V(4).Infof("considering import %q %s %q", pkg.PkgPath, relate(imp), imp)
   499  		matched := false
   500  		decided := false
   501  		for i, file := range restrictionFiles {
   502  			klog.V(4).Infof("rules file %s", file.path)
   503  			for j, rule := range file.InverseRules {
   504  				if !rule.Transitive && !isDirect[imp] {
   505  					continue
   506  				}
   507  				matching := selectors[i][j].MatchString(imp)
   508  				if !matching {
   509  					continue
   510  				}
   511  				matched = true
   512  				klog.V(6).Infof("selector %v matches %q", rule.SelectorRegexp, imp)
   513  
   514  				disp := rule.Evaluate(imp)
   515  				if disp == DepAllowed {
   516  					decided = true
   517  					break // no further rules, next file
   518  				} else if disp == DepForbidden {
   519  					errs = append(errs, fmt.Errorf("%q %s %q is forbidden by %s", pkg.PkgPath, relate(imp), imp, file.path))
   520  					decided = true
   521  					break // no further rules, next file
   522  				}
   523  			}
   524  			if decided {
   525  				break // no further files, next import
   526  			}
   527  		}
   528  		if matched && !decided {
   529  			klog.V(5).Infof("%q %s %q did not match any rule", pkg.PkgPath, relate(imp), imp)
   530  			errs = append(errs, fmt.Errorf("%q %s %q did not match any rule", pkg.PkgPath, relate(imp), imp))
   531  		}
   532  	}
   533  
   534  	if len(errs) > 0 {
   535  		return errs
   536  	}
   537  
   538  	return nil
   539  }
   540  
   541  func transitiveClosure(in map[string][]string) map[string][]string {
   542  	type edge struct {
   543  		from string
   544  		to   string
   545  	}
   546  
   547  	adj := make(map[edge]bool)
   548  	imports := make(map[string]struct{})
   549  	for from, tos := range in {
   550  		for _, to := range tos {
   551  			adj[edge{from, to}] = true
   552  			imports[to] = struct{}{}
   553  		}
   554  	}
   555  
   556  	// Warshal's algorithm
   557  	for k := range in {
   558  		for i := range in {
   559  			if !adj[edge{i, k}] {
   560  				continue
   561  			}
   562  			for j := range imports {
   563  				if adj[edge{i, j}] {
   564  					continue
   565  				}
   566  				if adj[edge{k, j}] {
   567  					adj[edge{i, j}] = true
   568  				}
   569  			}
   570  		}
   571  	}
   572  
   573  	out := make(map[string][]string, len(in))
   574  	for i := range in {
   575  		for j := range imports {
   576  			if adj[edge{i, j}] {
   577  				out[i] = append(out[i], j)
   578  			}
   579  		}
   580  
   581  		sort.Strings(out[i])
   582  	}
   583  
   584  	return out
   585  }
   586
View as plain text