requirements.go

Documentation: cuelang.org/go/internal/mod/modrequirements

     1  package modrequirements
     2  
     3  import (
     4  	"context"
     5  	"fmt"
     6  	"runtime"
     7  	"slices"
     8  	"sync"
     9  	"sync/atomic"
    10  
    11  	"cuelang.org/go/internal/mod/mvs"
    12  	"cuelang.org/go/internal/mod/semver"
    13  	"cuelang.org/go/internal/par"
    14  	"cuelang.org/go/mod/module"
    15  )
    16  
    17  type majorVersionDefault struct {
    18  	version          string
    19  	explicitDefault  bool
    20  	ambiguousDefault bool
    21  }
    22  
    23  // Requirements holds a set of module requirements. It does not
    24  // initially load the full module graph, as that can be expensive.
    25  // Instead the [Registry.Graph] method can be used to lazily construct
    26  // that.
    27  type Requirements struct {
    28  	registry          Registry
    29  	mainModuleVersion module.Version
    30  
    31  	// rootModules is the set of root modules of the graph, sorted and capped to
    32  	// length. It may contain duplicates, and may contain multiple versions for a
    33  	// given module path. The root modules are the main module's direct requirements.
    34  	rootModules    []module.Version
    35  	maxRootVersion map[string]string
    36  
    37  	// origDefaultMajorVersions holds the original passed to New.
    38  	origDefaultMajorVersions map[string]string
    39  
    40  	// defaultMajorVersions is derived from the above information,
    41  	// also holding modules that have a default due to being unique
    42  	// in the roots.
    43  	defaultMajorVersions map[string]majorVersionDefault
    44  
    45  	graphOnce sync.Once // guards writes to (but not reads from) graph
    46  	graph     atomic.Pointer[cachedGraph]
    47  }
    48  
    49  // Registry holds the contents of a registry. It's expected that this will
    50  // cache any results that it returns.
    51  type Registry interface {
    52  	Requirements(ctx context.Context, m module.Version) ([]module.Version, error)
    53  }
    54  
    55  // A cachedGraph is a non-nil *ModuleGraph, together with any error discovered
    56  // while loading that graph.
    57  type cachedGraph struct {
    58  	mg  *ModuleGraph
    59  	err error // If err is non-nil, mg may be incomplete (but must still be non-nil).
    60  }
    61  
    62  // NewRequirements returns a new requirement set with the given root modules.
    63  // The dependencies of the roots will be loaded lazily from the given
    64  // Registry value at the first call to the Graph method.
    65  //
    66  // The rootModules slice must be sorted according to [module.Sort].
    67  //
    68  // The defaultMajorVersions slice holds the default major version for (major-version-less)
    69  // mdule paths, if any have been specified. For example {"foo.com/bar": "v0"} specifies
    70  // that the default major version for the module `foo.com/bar` is `v0`.
    71  //
    72  // The caller must not modify rootModules or defaultMajorVersions after passing
    73  // them to NewRequirements.
    74  func NewRequirements(mainModulePath string, reg Registry, rootModules []module.Version, defaultMajorVersions map[string]string) *Requirements {
    75  	mainModuleVersion := module.MustNewVersion(mainModulePath, "")
    76  	// TODO add direct, so we can tell which modules are directly used by the
    77  	// main module.
    78  	for i, v := range rootModules {
    79  		if v.Path() == mainModulePath {
    80  			panic(fmt.Sprintf("NewRequirements called with untrimmed build list: rootModules[%v] is a main module", i))
    81  		}
    82  		if !v.IsValid() {
    83  			panic("NewRequirements with invalid zero version")
    84  		}
    85  	}
    86  	rs := &Requirements{
    87  		registry:          reg,
    88  		mainModuleVersion: mainModuleVersion,
    89  		rootModules:       rootModules,
    90  		maxRootVersion:    make(map[string]string, len(rootModules)),
    91  	}
    92  	for i, m := range rootModules {
    93  		if i > 0 {
    94  			prev := rootModules[i-1]
    95  			if prev.Path() > m.Path() || (prev.Path() == m.Path() && semver.Compare(prev.Version(), m.Version()) > 0) {
    96  				panic(fmt.Sprintf("NewRequirements called with unsorted roots: %v", rootModules))
    97  			}
    98  		}
    99  		if v, ok := rs.maxRootVersion[m.Path()]; !ok || semver.Compare(v, m.Version()) < 0 {
   100  			rs.maxRootVersion[m.Path()] = m.Version()
   101  		}
   102  	}
   103  	rs.initDefaultMajorVersions(defaultMajorVersions)
   104  	return rs
   105  }
   106  
   107  // WithDefaultMajorVersions returns rs but with the given default major versions.
   108  // The caller should not modify the map after calling this method.
   109  func (rs *Requirements) WithDefaultMajorVersions(defaults map[string]string) *Requirements {
   110  	rs1 := &Requirements{
   111  		registry:          rs.registry,
   112  		mainModuleVersion: rs.mainModuleVersion,
   113  		rootModules:       rs.rootModules,
   114  		maxRootVersion:    rs.maxRootVersion,
   115  	}
   116  	// Initialize graph and graphOnce in rs1 to mimic their state in rs.
   117  	// We can't copy the sync.Once, so if it's already triggered, we'll
   118  	// run the Once with a no-op function to get the same effect.
   119  	rs1.graph.Store(rs.graph.Load())
   120  	if rs1.GraphIsLoaded() {
   121  		rs1.graphOnce.Do(func() {})
   122  	}
   123  	rs1.initDefaultMajorVersions(defaults)
   124  	return rs1
   125  }
   126  
   127  func (rs *Requirements) initDefaultMajorVersions(defaultMajorVersions map[string]string) {
   128  	rs.origDefaultMajorVersions = defaultMajorVersions
   129  	rs.defaultMajorVersions = make(map[string]majorVersionDefault)
   130  	for mpath, v := range defaultMajorVersions {
   131  		if _, _, ok := module.SplitPathVersion(mpath); ok {
   132  			panic(fmt.Sprintf("NewRequirements called with major version in defaultMajorVersions %q", mpath))
   133  		}
   134  		if semver.Major(v) != v {
   135  			panic(fmt.Sprintf("NewRequirements called with invalid major version %q for module %q", v, mpath))
   136  		}
   137  		rs.defaultMajorVersions[mpath] = majorVersionDefault{
   138  			version:         v,
   139  			explicitDefault: true,
   140  		}
   141  	}
   142  	// Add defaults for all modules that have exactly one major version
   143  	// and no existing default.
   144  	for _, m := range rs.rootModules {
   145  		if m.IsLocal() {
   146  			continue
   147  		}
   148  		mpath := m.BasePath()
   149  		d, ok := rs.defaultMajorVersions[mpath]
   150  		if !ok {
   151  			rs.defaultMajorVersions[mpath] = majorVersionDefault{
   152  				version: semver.Major(m.Version()),
   153  			}
   154  			continue
   155  		}
   156  		if d.explicitDefault {
   157  			continue
   158  		}
   159  		d.ambiguousDefault = true
   160  		rs.defaultMajorVersions[mpath] = d
   161  	}
   162  }
   163  
   164  // RootSelected returns the version of the root dependency with the given module
   165  // path, or the zero module.Version and ok=false if the module is not a root
   166  // dependency.
   167  func (rs *Requirements) RootSelected(mpath string) (version string, ok bool) {
   168  	if mpath == rs.mainModuleVersion.Path() {
   169  		return "", true
   170  	}
   171  	if v, ok := rs.maxRootVersion[mpath]; ok {
   172  		return v, true
   173  	}
   174  	return "", false
   175  }
   176  
   177  // DefaultMajorVersions returns the defaults that the requirements was
   178  // created with. The returned map should not be modified.
   179  func (rs *Requirements) DefaultMajorVersions() map[string]string {
   180  	return rs.origDefaultMajorVersions
   181  }
   182  
   183  type MajorVersionDefaultStatus byte
   184  
   185  const (
   186  	ExplicitDefault MajorVersionDefaultStatus = iota
   187  	NonExplicitDefault
   188  	NoDefault
   189  	AmbiguousDefault
   190  )
   191  
   192  // DefaultMajorVersion returns the default major version for the given
   193  // module path (which should not itself contain a major version).
   194  //
   195  //	It also returns information about the default.
   196  func (rs *Requirements) DefaultMajorVersion(mpath string) (string, MajorVersionDefaultStatus) {
   197  	d, ok := rs.defaultMajorVersions[mpath]
   198  	switch {
   199  	case !ok:
   200  		return "", NoDefault
   201  	case d.ambiguousDefault:
   202  		return "", AmbiguousDefault
   203  	case d.explicitDefault:
   204  		return d.version, ExplicitDefault
   205  	default:
   206  		return d.version, NonExplicitDefault
   207  	}
   208  }
   209  
   210  // rootModules returns the set of root modules of the graph, sorted and capped to
   211  // length. It may contain duplicates, and may contain multiple versions for a
   212  // given module path.
   213  func (rs *Requirements) RootModules() []module.Version {
   214  	return slices.Clip(rs.rootModules)
   215  }
   216  
   217  // Graph returns the graph of module requirements loaded from the current
   218  // root modules (as reported by RootModules).
   219  //
   220  // Graph always makes a best effort to load the requirement graph despite any
   221  // errors, and always returns a non-nil *ModuleGraph.
   222  //
   223  // If the requirements of any relevant module fail to load, Graph also
   224  // returns a non-nil error of type *mvs.BuildListError.
   225  func (rs *Requirements) Graph(ctx context.Context) (*ModuleGraph, error) {
   226  	rs.graphOnce.Do(func() {
   227  		mg, mgErr := rs.readModGraph(ctx)
   228  		rs.graph.Store(&cachedGraph{mg, mgErr})
   229  	})
   230  	cached := rs.graph.Load()
   231  	return cached.mg, cached.err
   232  }
   233  
   234  // GraphIsLoaded reports whether Graph has been called previously.
   235  func (rs *Requirements) GraphIsLoaded() bool {
   236  	return rs.graph.Load() != nil
   237  }
   238  
   239  // A ModuleGraph represents the complete graph of module dependencies
   240  // of a main module.
   241  //
   242  // If the main module supports module graph pruning, the graph does not include
   243  // transitive dependencies of non-root (implicit) dependencies.
   244  type ModuleGraph struct {
   245  	g *mvs.Graph[module.Version]
   246  
   247  	buildListOnce sync.Once
   248  	buildList     []module.Version
   249  }
   250  
   251  // cueModSummary returns a summary of the cue.mod/module.cue file for module m,
   252  // taking into account any replacements for m, exclusions of its dependencies,
   253  // and/or vendoring.
   254  //
   255  // m must be a version in the module graph, reachable from the Target module.
   256  // cueModSummary must not be called for the Target module
   257  // itself, as its requirements may change.
   258  //
   259  // The caller must not modify the returned summary.
   260  func (rs *Requirements) cueModSummary(ctx context.Context, m module.Version) (*modFileSummary, error) {
   261  	require, err := rs.registry.Requirements(ctx, m)
   262  	if err != nil {
   263  		return nil, err
   264  	}
   265  	// TODO account for replacements, exclusions, etc.
   266  	return &modFileSummary{
   267  		module:  m,
   268  		require: require,
   269  	}, nil
   270  }
   271  
   272  type modFileSummary struct {
   273  	module  module.Version
   274  	require []module.Version
   275  }
   276  
   277  // readModGraph reads and returns the module dependency graph starting at the
   278  // given roots.
   279  //
   280  // readModGraph does not attempt to diagnose or update inconsistent roots.
   281  func (rs *Requirements) readModGraph(ctx context.Context) (*ModuleGraph, error) {
   282  	var (
   283  		mu       sync.Mutex // guards mg.g and hasError during loading
   284  		hasError bool
   285  		mg       = &ModuleGraph{
   286  			g: mvs.NewGraph[module.Version](module.Versions{}, cmpVersion, []module.Version{rs.mainModuleVersion}),
   287  		}
   288  	)
   289  
   290  	mg.g.Require(rs.mainModuleVersion, rs.rootModules)
   291  
   292  	var (
   293  		loadQueue = par.NewQueue(runtime.GOMAXPROCS(0))
   294  		loading   sync.Map // module.Version → nil; the set of modules that have been or are being loaded
   295  		loadCache par.ErrCache[module.Version, *modFileSummary]
   296  	)
   297  
   298  	// loadOne synchronously loads the explicit requirements for module m.
   299  	// It does not load the transitive requirements of m.
   300  	loadOne := func(m module.Version) (*modFileSummary, error) {
   301  		return loadCache.Do(m, func() (*modFileSummary, error) {
   302  			summary, err := rs.cueModSummary(ctx, m)
   303  
   304  			mu.Lock()
   305  			if err == nil {
   306  				mg.g.Require(m, summary.require)
   307  			} else {
   308  				hasError = true
   309  			}
   310  			mu.Unlock()
   311  
   312  			return summary, err
   313  		})
   314  	}
   315  
   316  	for _, m := range rs.rootModules {
   317  		m := m
   318  		if !m.IsValid() {
   319  			panic("root module version is invalid")
   320  		}
   321  		if m.IsLocal() || m.Version() == "none" {
   322  			continue
   323  		}
   324  
   325  		if _, dup := loading.LoadOrStore(m, nil); dup {
   326  			// m has already been enqueued for loading. Since unpruned loading may
   327  			// follow cycles in the requirement graph, we need to return early
   328  			// to avoid making the load queue infinitely long.
   329  			continue
   330  		}
   331  
   332  		loadQueue.Add(func() {
   333  			loadOne(m)
   334  			// If there's an error, findError will report it later.
   335  		})
   336  	}
   337  	<-loadQueue.Idle()
   338  
   339  	if hasError {
   340  		return mg, mg.findError(&loadCache)
   341  	}
   342  	return mg, nil
   343  }
   344  
   345  // RequiredBy returns the dependencies required by module m in the graph,
   346  // or ok=false if module m's dependencies are pruned out.
   347  //
   348  // The caller must not modify the returned slice, but may safely append to it
   349  // and may rely on it not to be modified.
   350  func (mg *ModuleGraph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) {
   351  	return mg.g.RequiredBy(m)
   352  }
   353  
   354  // Selected returns the selected version of the module with the given path.
   355  //
   356  // If no version is selected, Selected returns version "none".
   357  func (mg *ModuleGraph) Selected(path string) (version string) {
   358  	return mg.g.Selected(path)
   359  }
   360  
   361  // WalkBreadthFirst invokes f once, in breadth-first order, for each module
   362  // version other than "none" that appears in the graph, regardless of whether
   363  // that version is selected.
   364  func (mg *ModuleGraph) WalkBreadthFirst(f func(m module.Version)) {
   365  	mg.g.WalkBreadthFirst(f)
   366  }
   367  
   368  // BuildList returns the selected versions of all modules present in the graph,
   369  // beginning with the main modules.
   370  //
   371  // The order of the remaining elements in the list is deterministic
   372  // but arbitrary.
   373  //
   374  // The caller must not modify the returned list, but may safely append to it
   375  // and may rely on it not to be modified.
   376  func (mg *ModuleGraph) BuildList() []module.Version {
   377  	mg.buildListOnce.Do(func() {
   378  		mg.buildList = slices.Clip(mg.g.BuildList())
   379  	})
   380  	return mg.buildList
   381  }
   382  
   383  func (mg *ModuleGraph) findError(loadCache *par.ErrCache[module.Version, *modFileSummary]) error {
   384  	errStack := mg.g.FindPath(func(m module.Version) bool {
   385  		_, err := loadCache.Get(m)
   386  		return err != nil && err != par.ErrCacheEntryNotFound
   387  	})
   388  	if len(errStack) > 0 {
   389  		// TODO it seems that this stack can never be more than one
   390  		// element long, becasuse readModGraph never goes more
   391  		// than one depth level below the root requirements.
   392  		// Given that the top of the stack will always be the main
   393  		// module and that BuildListError elides the first element
   394  		// in this case, is it really worth using FindPath?
   395  		_, err := loadCache.Get(errStack[len(errStack)-1])
   396  		var noUpgrade func(from, to module.Version) bool
   397  		return mvs.NewBuildListError[module.Version](err, errStack, module.Versions{}, noUpgrade)
   398  	}
   399  
   400  	return nil
   401  }
   402  
   403  // cmpVersion implements the comparison for versions in the module loader.
   404  //
   405  // It is consistent with semver.Compare except that as a special case,
   406  // the version "" is considered higher than all other versions.
   407  // The main module (also known as the target) has no version and must be chosen
   408  // over other versions of the same module in the module dependency graph.
   409  func cmpVersion(v1, v2 string) int {
   410  	if v2 == "" {
   411  		if v1 == "" {
   412  			return 0
   413  		}
   414  		return -1
   415  	}
   416  	if v1 == "" {
   417  		return 1
   418  	}
   419  	return semver.Compare(v1, v2)
   420  }
   421
View as plain text