graph.go

     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 mvs
     6  
     7  import (
     8  	"fmt"
     9  
    10  	"golang.org/x/mod/module"
    11  )
    12  
    13  // Graph implements an incremental version of the MVS algorithm, with the
    14  // requirements pushed by the caller instead of pulled by the MVS traversal.
    15  type Graph struct {
    16  	cmp   func(v1, v2 string) int
    17  	roots []module.Version
    18  
    19  	required map[module.Version][]module.Version
    20  
    21  	isRoot   map[module.Version]bool // contains true for roots and false for reachable non-roots
    22  	selected map[string]string       // path → version
    23  }
    24  
    25  // NewGraph returns an incremental MVS graph containing only a set of root
    26  // dependencies and using the given max function for version strings.
    27  //
    28  // The caller must ensure that the root slice is not modified while the Graph
    29  // may be in use.
    30  func NewGraph(cmp func(v1, v2 string) int, roots []module.Version) *Graph {
    31  	g := &Graph{
    32  		cmp:      cmp,
    33  		roots:    roots[:len(roots):len(roots)],
    34  		required: make(map[module.Version][]module.Version),
    35  		isRoot:   make(map[module.Version]bool),
    36  		selected: make(map[string]string),
    37  	}
    38  
    39  	for _, m := range roots {
    40  		g.isRoot[m] = true
    41  		if g.cmp(g.Selected(m.Path), m.Version) < 0 {
    42  			g.selected[m.Path] = m.Version
    43  		}
    44  	}
    45  
    46  	return g
    47  }
    48  
    49  // Require adds the information that module m requires all modules in reqs.
    50  // The reqs slice must not be modified after it is passed to Require.
    51  //
    52  // m must be reachable by some existing chain of requirements from g's target,
    53  // and Require must not have been called for it already.
    54  //
    55  // If any of the modules in reqs has the same path as g's target,
    56  // the target must have higher precedence than the version in req.
    57  func (g *Graph) Require(m module.Version, reqs []module.Version) {
    58  	// To help catch disconnected-graph bugs, enforce that all required versions
    59  	// are actually reachable from the roots (and therefore should affect the
    60  	// selected versions of the modules they name).
    61  	if _, reachable := g.isRoot[m]; !reachable {
    62  		panic(fmt.Sprintf("%v is not reachable from any root", m))
    63  	}
    64  
    65  	// Truncate reqs to its capacity to avoid aliasing bugs if it is later
    66  	// returned from RequiredBy and appended to.
    67  	reqs = reqs[:len(reqs):len(reqs)]
    68  
    69  	if _, dup := g.required[m]; dup {
    70  		panic(fmt.Sprintf("requirements of %v have already been set", m))
    71  	}
    72  	g.required[m] = reqs
    73  
    74  	for _, dep := range reqs {
    75  		// Mark dep reachable, regardless of whether it is selected.
    76  		if _, ok := g.isRoot[dep]; !ok {
    77  			g.isRoot[dep] = false
    78  		}
    79  
    80  		if g.cmp(g.Selected(dep.Path), dep.Version) < 0 {
    81  			g.selected[dep.Path] = dep.Version
    82  		}
    83  	}
    84  }
    85  
    86  // RequiredBy returns the slice of requirements passed to Require for m, if any,
    87  // with its capacity reduced to its length.
    88  // If Require has not been called for m, RequiredBy(m) returns ok=false.
    89  //
    90  // The caller must not modify the returned slice, but may safely append to it
    91  // and may rely on it not to be modified.
    92  func (g *Graph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) {
    93  	reqs, ok = g.required[m]
    94  	return reqs, ok
    95  }
    96  
    97  // Selected returns the selected version of the given module path.
    98  //
    99  // If no version is selected, Selected returns version "none".
   100  func (g *Graph) Selected(path string) (version string) {
   101  	v, ok := g.selected[path]
   102  	if !ok {
   103  		return "none"
   104  	}
   105  	return v
   106  }
   107  
   108  // BuildList returns the selected versions of all modules present in the Graph,
   109  // beginning with the selected versions of each module path in the roots of g.
   110  //
   111  // The order of the remaining elements in the list is deterministic
   112  // but arbitrary.
   113  func (g *Graph) BuildList() []module.Version {
   114  	seenRoot := make(map[string]bool, len(g.roots))
   115  
   116  	var list []module.Version
   117  	for _, r := range g.roots {
   118  		if seenRoot[r.Path] {
   119  			// Multiple copies of the same root, with the same or different versions,
   120  			// are a bit of a degenerate case: we will take the transitive
   121  			// requirements of both roots into account, but only the higher one can
   122  			// possibly be selected. However — especially given that we need the
   123  			// seenRoot map for later anyway — it is simpler to support this
   124  			// degenerate case than to forbid it.
   125  			continue
   126  		}
   127  
   128  		if v := g.Selected(r.Path); v != "none" {
   129  			list = append(list, module.Version{Path: r.Path, Version: v})
   130  		}
   131  		seenRoot[r.Path] = true
   132  	}
   133  	uniqueRoots := list
   134  
   135  	for path, version := range g.selected {
   136  		if !seenRoot[path] {
   137  			list = append(list, module.Version{Path: path, Version: version})
   138  		}
   139  	}
   140  	module.Sort(list[len(uniqueRoots):])
   141  
   142  	return list
   143  }
   144  
   145  // WalkBreadthFirst invokes f once, in breadth-first order, for each module
   146  // version other than "none" that appears in the graph, regardless of whether
   147  // that version is selected.
   148  func (g *Graph) WalkBreadthFirst(f func(m module.Version)) {
   149  	var queue []module.Version
   150  	enqueued := make(map[module.Version]bool)
   151  	for _, m := range g.roots {
   152  		if m.Version != "none" {
   153  			queue = append(queue, m)
   154  			enqueued[m] = true
   155  		}
   156  	}
   157  
   158  	for len(queue) > 0 {
   159  		m := queue[0]
   160  		queue = queue[1:]
   161  
   162  		f(m)
   163  
   164  		reqs, _ := g.RequiredBy(m)
   165  		for _, r := range reqs {
   166  			if !enqueued[r] && r.Version != "none" {
   167  				queue = append(queue, r)
   168  				enqueued[r] = true
   169  			}
   170  		}
   171  	}
   172  }
   173  
   174  // FindPath reports a shortest requirement path starting at one of the roots of
   175  // the graph and ending at a module version m for which f(m) returns true, or
   176  // nil if no such path exists.
   177  func (g *Graph) FindPath(f func(module.Version) bool) []module.Version {
   178  	// firstRequires[a] = b means that in a breadth-first traversal of the
   179  	// requirement graph, the module version a was first required by b.
   180  	firstRequires := make(map[module.Version]module.Version)
   181  
   182  	queue := g.roots
   183  	for _, m := range g.roots {
   184  		firstRequires[m] = module.Version{}
   185  	}
   186  
   187  	for len(queue) > 0 {
   188  		m := queue[0]
   189  		queue = queue[1:]
   190  
   191  		if f(m) {
   192  			// Construct the path reversed (because we're starting from the far
   193  			// endpoint), then reverse it.
   194  			path := []module.Version{m}
   195  			for {
   196  				m = firstRequires[m]
   197  				if m.Path == "" {
   198  					break
   199  				}
   200  				path = append(path, m)
   201  			}
   202  
   203  			i, j := 0, len(path)-1
   204  			for i < j {
   205  				path[i], path[j] = path[j], path[i]
   206  				i++
   207  				j--
   208  			}
   209  
   210  			return path
   211  		}
   212  
   213  		reqs, _ := g.RequiredBy(m)
   214  		for _, r := range reqs {
   215  			if _, seen := firstRequires[r]; !seen {
   216  				queue = append(queue, r)
   217  				firstRequires[r] = m
   218  			}
   219  		}
   220  	}
   221  
   222  	return nil
   223  }
   224
View as plain text