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