dependencyverifier.go

Documentation: k8s.io/kubernetes/cmd/dependencyverifier

     1  /*
     2  Copyright 2021 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  package main
    18  
    19  import (
    20  	"bytes"
    21  	"encoding/json"
    22  	"fmt"
    23  	"io/ioutil"
    24  	"log"
    25  	"os"
    26  	"os/exec"
    27  	"sort"
    28  	"strings"
    29  
    30  	"github.com/google/go-cmp/cmp"
    31  )
    32  
    33  type Unwanted struct {
    34  	// things we want to stop referencing
    35  	Spec UnwantedSpec `json:"spec"`
    36  	// status of our unwanted dependencies
    37  	Status UnwantedStatus `json:"status"`
    38  }
    39  
    40  type UnwantedSpec struct {
    41  	// module names we don't want to depend on, mapped to an optional message about why
    42  	UnwantedModules map[string]string `json:"unwantedModules"`
    43  }
    44  
    45  type UnwantedStatus struct {
    46  	// references to modules in the spec.unwantedModules list, based on `go mod graph` content.
    47  	// eliminating things from this list is good, and sometimes requires working with upstreams to do so.
    48  	UnwantedReferences map[string][]string `json:"unwantedReferences"`
    49  	// list of modules in the spec.unwantedModules list which are vendored
    50  	UnwantedVendored []string `json:"unwantedVendored"`
    51  }
    52  
    53  // runCommand runs the cmd and returns the combined stdout and stderr, or an
    54  // error if the command failed.
    55  func runCommand(cmd ...string) (string, error) {
    56  	return runCommandInDir("", cmd)
    57  }
    58  
    59  func runCommandInDir(dir string, cmd []string) (string, error) {
    60  	c := exec.Command(cmd[0], cmd[1:]...)
    61  	c.Dir = dir
    62  	output, err := c.CombinedOutput()
    63  	if err != nil {
    64  		return "", fmt.Errorf("failed to run %q: %s (%s)", strings.Join(cmd, " "), err, output)
    65  	}
    66  	return string(output), nil
    67  }
    68  
    69  func readFile(path string) (string, error) {
    70  	content, err := os.ReadFile(path)
    71  	// Convert []byte to string and print to screen
    72  	return string(content), err
    73  }
    74  
    75  func moduleInSlice(a module, list []module, matchVersion bool) bool {
    76  	for _, b := range list {
    77  		if b == a {
    78  			return true
    79  		}
    80  		if !matchVersion && b.name == a.name {
    81  			return true
    82  		}
    83  	}
    84  	return false
    85  }
    86  
    87  // converts `go mod graph` output modStr into a map of from->[]to references and the main module
    88  func convertToMap(modStr string) ([]module, map[module][]module) {
    89  	var (
    90  		mainModulesList = []module{}
    91  		mainModules     = map[module]bool{}
    92  	)
    93  	modMap := make(map[module][]module)
    94  	for _, line := range strings.Split(modStr, "\n") {
    95  		if len(line) == 0 {
    96  			continue
    97  		}
    98  		deps := strings.Split(line, " ")
    99  		if len(deps) == 2 {
   100  			first := parseModule(deps[0])
   101  			second := parseModule(deps[1])
   102  			if first.version == "" || first.version == "v0.0.0" {
   103  				if !mainModules[first] {
   104  					mainModules[first] = true
   105  					mainModulesList = append(mainModulesList, first)
   106  				}
   107  			}
   108  			modMap[first] = append(modMap[first], second)
   109  		} else {
   110  			// skip invalid line
   111  			log.Printf("!!!invalid line in mod.graph: %s", line)
   112  			continue
   113  		}
   114  	}
   115  	return mainModulesList, modMap
   116  }
   117  
   118  // difference returns a-b and b-a as sorted lists
   119  func difference(a, b []string) ([]string, []string) {
   120  	aMinusB := map[string]bool{}
   121  	bMinusA := map[string]bool{}
   122  	for _, dependency := range a {
   123  		aMinusB[dependency] = true
   124  	}
   125  	for _, dependency := range b {
   126  		if _, found := aMinusB[dependency]; found {
   127  			delete(aMinusB, dependency)
   128  		} else {
   129  			bMinusA[dependency] = true
   130  		}
   131  	}
   132  	aMinusBList := []string{}
   133  	bMinusAList := []string{}
   134  	for dependency := range aMinusB {
   135  		aMinusBList = append(aMinusBList, dependency)
   136  	}
   137  	for dependency := range bMinusA {
   138  		bMinusAList = append(bMinusAList, dependency)
   139  	}
   140  	sort.Strings(aMinusBList)
   141  	sort.Strings(bMinusAList)
   142  	return aMinusBList, bMinusAList
   143  }
   144  
   145  type module struct {
   146  	name    string
   147  	version string
   148  }
   149  
   150  func (m module) String() string {
   151  	if len(m.version) == 0 {
   152  		return m.name
   153  	}
   154  	return m.name + "@" + m.version
   155  }
   156  
   157  func parseModule(s string) module {
   158  	if !strings.Contains(s, "@") {
   159  		return module{name: s}
   160  	}
   161  	parts := strings.SplitN(s, "@", 2)
   162  	return module{name: parts[0], version: parts[1]}
   163  }
   164  
   165  // option1: dependencyverifier dependencies.json
   166  // it will run `go mod graph` and check it.
   167  func main() {
   168  	var modeGraphStr string
   169  	var err error
   170  	if len(os.Args) == 2 {
   171  		// run `go mod graph`
   172  		modeGraphStr, err = runCommand("go", "mod", "graph")
   173  		if err != nil {
   174  			log.Fatalf("Error running 'go mod graph': %s", err)
   175  		}
   176  	} else {
   177  		log.Fatalf("Usage: %s dependencies.json", os.Args[0])
   178  	}
   179  
   180  	dependenciesJSONPath := string(os.Args[1])
   181  	dependencies, err := readFile(dependenciesJSONPath)
   182  	if err != nil {
   183  		log.Fatalf("Error reading dependencies file %s: %s", dependencies, err)
   184  	}
   185  
   186  	// load Unwanted from json
   187  	configFromFile := &Unwanted{}
   188  	decoder := json.NewDecoder(bytes.NewBuffer([]byte(dependencies)))
   189  	decoder.DisallowUnknownFields()
   190  	if err := decoder.Decode(configFromFile); err != nil {
   191  		log.Fatalf("Error reading dependencies file %s: %s", dependenciesJSONPath, err)
   192  	}
   193  
   194  	// convert from `go mod graph` to main module and map of from->[]to references
   195  	mainModules, moduleGraph := convertToMap(modeGraphStr)
   196  
   197  	directDependencies := map[string]map[string]bool{}
   198  	for _, mainModule := range mainModules {
   199  		dir := ""
   200  		if mainModule.name != "k8s.io/kubernetes" {
   201  			dir = "staging/src/" + mainModule.name
   202  		}
   203  		listOutput, err := runCommandInDir(dir, []string{"go", "list", "-m", "-f", "{{if not .Indirect}}{{if not .Main}}{{.Path}}{{end}}{{end}}", "all"})
   204  		if err != nil {
   205  			log.Fatalf("Error running 'go list' for %s: %s", mainModule.name, err)
   206  		}
   207  		directDependencies[mainModule.name] = map[string]bool{}
   208  		for _, directDependency := range strings.Split(listOutput, "\n") {
   209  			directDependencies[mainModule.name][directDependency] = true
   210  		}
   211  	}
   212  
   213  	// gather the effective versions by looking at the versions required by the main modules
   214  	effectiveVersions := map[string]module{}
   215  	for _, mainModule := range mainModules {
   216  		for _, override := range moduleGraph[mainModule] {
   217  			if _, ok := effectiveVersions[override.name]; !ok {
   218  				effectiveVersions[override.name] = override
   219  			}
   220  		}
   221  	}
   222  
   223  	unwantedToReferencers := map[string][]module{}
   224  	for _, mainModule := range mainModules {
   225  		// visit to find unwanted modules still referenced from the main module
   226  		visit(func(m module, via []module) {
   227  			if _, unwanted := configFromFile.Spec.UnwantedModules[m.name]; unwanted {
   228  				// this is unwanted, store what is referencing it
   229  				referencer := via[len(via)-1]
   230  				if !moduleInSlice(referencer, unwantedToReferencers[m.name], false) {
   231  					// // uncomment to get a detailed tree of the path that referenced the unwanted dependency
   232  					//
   233  					// i := 0
   234  					// for _, v := range via {
   235  					// 	if v.version != "" && v.version != "v0.0.0" {
   236  					// 		fmt.Println(strings.Repeat("  ", i), v)
   237  					// 		i++
   238  					// 	}
   239  					// }
   240  					// if i > 0 {
   241  					// 	fmt.Println(strings.Repeat("  ", i+1), m)
   242  					// 	fmt.Println()
   243  					// }
   244  					unwantedToReferencers[m.name] = append(unwantedToReferencers[m.name], referencer)
   245  				}
   246  			}
   247  		}, mainModule, moduleGraph, effectiveVersions)
   248  	}
   249  
   250  	config := &Unwanted{}
   251  	config.Spec.UnwantedModules = configFromFile.Spec.UnwantedModules
   252  	for unwanted := range unwantedToReferencers {
   253  		if config.Status.UnwantedReferences == nil {
   254  			config.Status.UnwantedReferences = map[string][]string{}
   255  		}
   256  		sort.Slice(unwantedToReferencers[unwanted], func(i, j int) bool {
   257  			ri := unwantedToReferencers[unwanted][i]
   258  			rj := unwantedToReferencers[unwanted][j]
   259  			if ri.name != rj.name {
   260  				return ri.name < rj.name
   261  			}
   262  			return ri.version < rj.version
   263  		})
   264  		for _, referencer := range unwantedToReferencers[unwanted] {
   265  			// make sure any reference at all shows up as a non-nil status
   266  			if config.Status.UnwantedReferences == nil {
   267  				config.Status.UnwantedReferences[unwanted] = []string{}
   268  			}
   269  			// record specific names of versioned referents
   270  			if referencer.version != "" && referencer.version != "v0.0.0" {
   271  				config.Status.UnwantedReferences[unwanted] = append(config.Status.UnwantedReferences[unwanted], referencer.name)
   272  			} else if directDependencies[referencer.name][unwanted] {
   273  				config.Status.UnwantedReferences[unwanted] = append(config.Status.UnwantedReferences[unwanted], referencer.name)
   274  			}
   275  		}
   276  	}
   277  
   278  	vendorModulesTxt, err := ioutil.ReadFile("vendor/modules.txt")
   279  	if err != nil {
   280  		log.Fatal(err)
   281  	}
   282  	vendoredModules := map[string]bool{}
   283  	for _, l := range strings.Split(string(vendorModulesTxt), "\n") {
   284  		parts := strings.Split(l, " ")
   285  		if len(parts) == 3 && parts[0] == "#" && strings.HasPrefix(parts[2], "v") {
   286  			vendoredModules[parts[1]] = true
   287  		}
   288  	}
   289  	config.Status.UnwantedVendored = []string{}
   290  	for unwanted := range configFromFile.Spec.UnwantedModules {
   291  		if vendoredModules[unwanted] {
   292  			config.Status.UnwantedVendored = append(config.Status.UnwantedVendored, unwanted)
   293  		}
   294  	}
   295  	sort.Strings(config.Status.UnwantedVendored)
   296  
   297  	needUpdate := false
   298  
   299  	// Compare unwanted list from unwanted-dependencies.json with current status from `go mod graph`
   300  	expected, err := json.MarshalIndent(configFromFile.Status, "", "  ")
   301  	if err != nil {
   302  		log.Fatal(err)
   303  	}
   304  	actual, err := json.MarshalIndent(config.Status, "", "  ")
   305  	if err != nil {
   306  		log.Fatal(err)
   307  	}
   308  	if !bytes.Equal(expected, actual) {
   309  		log.Printf("Expected status of\n%s", string(expected))
   310  		log.Printf("Got status of\n%s", string(actual))
   311  		needUpdate = true
   312  		log.Print("Status diff:\n", cmp.Diff(expected, actual))
   313  	}
   314  	for expectedRef, expectedFrom := range configFromFile.Status.UnwantedReferences {
   315  		actualFrom, ok := config.Status.UnwantedReferences[expectedRef]
   316  		if !ok {
   317  			// disappeared entirely
   318  			log.Printf("Good news! Unwanted dependency %q is no longer referenced. Remove status.unwantedReferences[%q] in %s to ensure it doesn't get reintroduced.", expectedRef, expectedRef, dependenciesJSONPath)
   319  			needUpdate = true
   320  			continue
   321  		}
   322  		removedReferences, unwantedReferences := difference(expectedFrom, actualFrom)
   323  		if len(removedReferences) > 0 {
   324  			log.Printf("Good news! Unwanted module %q dropped the following dependants:", expectedRef)
   325  			for _, reference := range removedReferences {
   326  				log.Printf("   %s", reference)
   327  			}
   328  			log.Printf("!!! Remove those from status.unwantedReferences[%q] in %s to ensure they don't get reintroduced.", expectedRef, dependenciesJSONPath)
   329  			needUpdate = true
   330  		}
   331  		if len(unwantedReferences) > 0 {
   332  			log.Printf("Unwanted module %q marked in %s is referenced by new dependants:", expectedRef, dependenciesJSONPath)
   333  			for _, reference := range unwantedReferences {
   334  				log.Printf("   %s", reference)
   335  			}
   336  			log.Printf("!!! Avoid updating referencing modules to versions that reintroduce use of unwanted dependencies\n")
   337  			needUpdate = true
   338  		}
   339  	}
   340  	for actualRef, actualFrom := range config.Status.UnwantedReferences {
   341  		if _, expected := configFromFile.Status.UnwantedReferences[actualRef]; expected {
   342  			// expected, already ensured referencers were equal in the first loop
   343  			continue
   344  		}
   345  		log.Printf("Unwanted module %q marked in %s is referenced", actualRef, dependenciesJSONPath)
   346  		for _, reference := range actualFrom {
   347  			log.Printf("   %s", reference)
   348  		}
   349  		log.Printf("!!! Avoid updating referencing modules to versions that reintroduce use of unwanted dependencies\n")
   350  		needUpdate = true
   351  	}
   352  
   353  	removedVendored, addedVendored := difference(configFromFile.Status.UnwantedVendored, config.Status.UnwantedVendored)
   354  	if len(removedVendored) > 0 {
   355  		log.Printf("Good news! Unwanted modules are no longer vendered: %q", removedVendored)
   356  		log.Printf("!!! Remove those from status.unwantedVendored in %s to ensure they don't get reintroduced.", dependenciesJSONPath)
   357  		needUpdate = true
   358  	}
   359  	if len(addedVendored) > 0 {
   360  		log.Printf("Unwanted modules are newly vendored: %q", addedVendored)
   361  		log.Printf("!!! Avoid updates that increase vendoring of unwanted dependencies\n")
   362  		needUpdate = true
   363  	}
   364  
   365  	if needUpdate {
   366  		os.Exit(1)
   367  	}
   368  }
   369  
   370  func visit(visitor func(m module, via []module), main module, references map[module][]module, effectiveVersions map[string]module) {
   371  	doVisit(visitor, main, nil, map[module]bool{}, references, effectiveVersions)
   372  }
   373  
   374  func doVisit(visitor func(m module, via []module), from module, via []module, visited map[module]bool, references map[module][]module, effectiveVersions map[string]module) {
   375  	visitor(from, via)
   376  	via = append(via, from)
   377  	if visited[from] {
   378  		return
   379  	}
   380  	for _, to := range references[from] {
   381  		// switch to the effective version of this dependency
   382  		if override, ok := effectiveVersions[to.name]; ok {
   383  			to = override
   384  		}
   385  		// recurse unless we've already visited this module in this traversal
   386  		if !moduleInSlice(to, via, false) {
   387  			doVisit(visitor, to, via, visited, references, effectiveVersions)
   388  		}
   389  	}
   390  	visited[from] = true
   391  }
   392
View as plain text