...

Source file src/cmd/go/internal/mvs/mvs_test.go

Documentation: cmd/go/internal/mvs

     1  // Copyright 2018 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  	"reflect"
    10  	"strings"
    11  	"testing"
    12  
    13  	"golang.org/x/mod/module"
    14  )
    15  
    16  var tests = `
    17  # Scenario from blog.
    18  name: blog
    19  A: B1 C2
    20  B1: D3
    21  C1: D2
    22  C2: D4
    23  C3: D5
    24  C4: G1
    25  D2: E1
    26  D3: E2
    27  D4: E2 F1
    28  D5: E2
    29  G1: C4
    30  A2: B1 C4 D4
    31  build A:       A B1 C2 D4 E2 F1
    32  upgrade* A:    A B1 C4 D5 E2 F1 G1
    33  upgrade A C4:  A B1 C4 D4 E2 F1 G1
    34  build A2:     A2 B1 C4 D4 E2 F1 G1
    35  downgrade A2 D2: A2 C4 D2 E2 F1 G1
    36  
    37  name: trim
    38  A: B1 C2
    39  B1: D3
    40  C2: B2
    41  B2:
    42  build A: A B2 C2 D3
    43  
    44  # Cross-dependency between D and E.
    45  # No matter how it arises, should get result of merging all build lists via max,
    46  # which leads to including both D2 and E2.
    47  
    48  name: cross1
    49  A: B C
    50  B: D1
    51  C: D2
    52  D1: E2
    53  D2: E1
    54  build A: A B C D2 E2
    55  
    56  name: cross1V
    57  A: B2 C D2 E1
    58  B1:
    59  B2: D1
    60  C: D2
    61  D1: E2
    62  D2: E1
    63  build A: A B2 C D2 E2
    64  
    65  name: cross1U
    66  A: B1 C
    67  B1:
    68  B2: D1
    69  C: D2
    70  D1: E2
    71  D2: E1
    72  build A:      A B1 C D2 E1
    73  upgrade A B2: A B2 C D2 E2
    74  
    75  name: cross1R
    76  A: B C
    77  B: D2
    78  C: D1
    79  D1: E2
    80  D2: E1
    81  build A: A B C D2 E2
    82  
    83  name: cross1X
    84  A: B C
    85  B: D1 E2
    86  C: D2
    87  D1: E2
    88  D2: E1
    89  build A: A B C D2 E2
    90  
    91  name: cross2
    92  A: B D2
    93  B: D1
    94  D1: E2
    95  D2: E1
    96  build A: A B D2 E2
    97  
    98  name: cross2X
    99  A: B D2
   100  B: D1 E2
   101  C: D2
   102  D1: E2
   103  D2: E1
   104  build A: A B D2 E2
   105  
   106  name: cross3
   107  A: B D2 E1
   108  B: D1
   109  D1: E2
   110  D2: E1
   111  build A: A B D2 E2
   112  
   113  name: cross3X
   114  A: B D2 E1
   115  B: D1 E2
   116  D1: E2
   117  D2: E1
   118  build A: A B D2 E2
   119  
   120  # Should not get E2 here, because B has been updated
   121  # not to depend on D1 anymore.
   122  name: cross4
   123  A1: B1 D2
   124  A2: B2 D2
   125  B1: D1
   126  B2: D2
   127  D1: E2
   128  D2: E1
   129  build A1: A1 B1 D2 E2
   130  build A2: A2 B2 D2 E1
   131  
   132  # But the upgrade from A1 preserves the E2 dep explicitly.
   133  upgrade A1 B2: A1 B2 D2 E2
   134  upgradereq A1 B2: B2 E2
   135  
   136  name: cross5
   137  A: D1
   138  D1: E2
   139  D2: E1
   140  build A:       A D1 E2
   141  upgrade* A:    A D2 E2
   142  upgrade A D2:  A D2 E2
   143  upgradereq A D2: D2 E2
   144  
   145  name: cross6
   146  A: D2
   147  D1: E2
   148  D2: E1
   149  build A:      A D2 E1
   150  upgrade* A:   A D2 E2
   151  upgrade A E2: A D2 E2
   152  
   153  name: cross7
   154  A: B C
   155  B: D1
   156  C: E1
   157  D1: E2
   158  E1: D2
   159  build A: A B C D2 E2
   160  
   161  # golang.org/issue/31248:
   162  # Even though we select X2, the requirement on I1
   163  # via X1 should be preserved.
   164  name: cross8
   165  M: A1 B1
   166  A1: X1
   167  B1: X2
   168  X1: I1
   169  X2:
   170  build M: M A1 B1 I1 X2
   171  
   172  # Upgrade from B1 to B2 should not drop the transitive dep on D.
   173  name: drop
   174  A: B1 C1
   175  B1: D1
   176  B2:
   177  C2:
   178  D2:
   179  build A:    A B1 C1 D1
   180  upgrade* A: A B2 C2 D2
   181  
   182  name: simplify
   183  A: B1 C1
   184  B1: C2
   185  C1: D1
   186  C2:
   187  build A: A B1 C2 D1
   188  
   189  name: up1
   190  A: B1 C1
   191  B1:
   192  B2:
   193  B3:
   194  B4:
   195  B5.hidden:
   196  C2:
   197  C3:
   198  build A:    A B1 C1
   199  upgrade* A: A B4 C3
   200  
   201  name: up2
   202  A: B5.hidden C1
   203  B1:
   204  B2:
   205  B3:
   206  B4:
   207  B5.hidden:
   208  C2:
   209  C3:
   210  build A:    A B5.hidden C1
   211  upgrade* A: A B5.hidden C3
   212  
   213  name: down1
   214  A: B2
   215  B1: C1
   216  B2: C2
   217  build A:        A B2 C2
   218  downgrade A C1: A B1 C1
   219  
   220  name: down2
   221  A: B2 E2
   222  B1:
   223  B2: C2 F2
   224  C1:
   225  D1:
   226  C2: D2 E2
   227  D2: B2
   228  E2: D2
   229  E1:
   230  F1:
   231  build A:        A B2 C2 D2 E2 F2
   232  downgrade A F1: A B1 C1 D1 E1 F1
   233  
   234  # https://research.swtch.com/vgo-mvs#algorithm_4:
   235  # “[D]owngrades are constrained to only downgrade packages, not also upgrade
   236  # them; if an upgrade before downgrade is needed, the user must ask for it
   237  # explicitly.”
   238  #
   239  # Here, downgrading B2 to B1 upgrades C1 to C2, and C2 does not depend on D2.
   240  # However, C2 would be an upgrade — not a downgrade — so B1 must also be
   241  # rejected.
   242  name: downcross1
   243  A: B2 C1
   244  B1: C2
   245  B2: C1
   246  C1: D2
   247  C2:
   248  D1:
   249  D2:
   250  build A:        A B2 C1 D2
   251  downgrade A D1: A       D1
   252  
   253  # https://research.swtch.com/vgo-mvs#algorithm_4:
   254  # “Unlike upgrades, downgrades must work by removing requirements, not adding
   255  # them.”
   256  #
   257  # However, downgrading a requirement may introduce a new requirement on a
   258  # previously-unrequired module. If each dependency's requirements are complete
   259  # (“tidy”), that can't change the behavior of any other package whose version is
   260  # not also being downgraded, so we should allow it.
   261  name: downcross2
   262  A: B2
   263  B1: C1
   264  B2: D2
   265  C1:
   266  D1:
   267  D2:
   268  build A:        A B2    D2
   269  downgrade A D1: A B1 C1 D1
   270  
   271  name: downcycle
   272  A: A B2
   273  B2: A
   274  B1:
   275  build A:        A B2
   276  downgrade A B1: A B1
   277  
   278  # Both B3 and C2 require D2.
   279  # If we downgrade D to D1, then in isolation B3 would downgrade to B1,
   280  # because B2 is hidden — B1 is the next-highest version that is not hidden.
   281  # However, if we downgrade D, we will also downgrade C to C1.
   282  # And C1 requires B2.hidden, and B2.hidden also meets our requirements:
   283  # it is compatible with D1 and a strict downgrade from B3.
   284  #
   285  # Since neither the initial nor the final build list includes B1,
   286  # and the nothing in the final downgraded build list requires E at all,
   287  # no dependency on E1 (required by only B1) should be introduced.
   288  #
   289  name: downhiddenartifact
   290  A: B3 C2
   291  A1: B3
   292  B1: E1
   293  B2.hidden:
   294  B3: D2
   295  C1: B2.hidden
   296  C2: D2
   297  D1:
   298  D2:
   299  build A1: A1 B3 D2
   300  downgrade A1 D1: A1 B1 D1 E1
   301  build A: A B3 C2 D2
   302  downgrade A D1: A B2.hidden C1 D1
   303  
   304  # Both B3 and C3 require D2.
   305  # If we downgrade D to D1, then in isolation B3 would downgrade to B1,
   306  # and C3 would downgrade to C1.
   307  # But C1 requires B2.hidden, and B1 requires C2.hidden, so we can't
   308  # downgrade to either of those without pulling the other back up a little.
   309  #
   310  # B2.hidden and C2.hidden are both compatible with D1, so that still
   311  # meets our requirements — but then we're in an odd state in which
   312  # B and C have both been downgraded to hidden versions, without any
   313  # remaining requirements to explain how those hidden versions got there.
   314  #
   315  # TODO(bcmills): Would it be better to force downgrades to land on non-hidden
   316  # versions?
   317  # In this case, that would remove the dependencies on B and C entirely.
   318  #
   319  name: downhiddencross
   320  A: B3 C3
   321  B1: C2.hidden
   322  B2.hidden:
   323  B3: D2
   324  C1: B2.hidden
   325  C2.hidden:
   326  C3: D2
   327  D1:
   328  D2:
   329  build A: A B3 C3 D2
   330  downgrade A D1: A B2.hidden C2.hidden D1
   331  
   332  # golang.org/issue/25542.
   333  name: noprev1
   334  A: B4 C2
   335  B2.hidden:
   336  C2:
   337  build A:               A B4        C2
   338  downgrade A B2.hidden: A B2.hidden C2
   339  
   340  name: noprev2
   341  A: B4 C2
   342  B2.hidden:
   343  B1:
   344  C2:
   345  build A:               A B4        C2
   346  downgrade A B2.hidden: A B2.hidden C2
   347  
   348  name: noprev3
   349  A: B4 C2
   350  B3:
   351  B2.hidden:
   352  C2:
   353  build A:               A B4        C2
   354  downgrade A B2.hidden: A B2.hidden C2
   355  
   356  # Cycles involving the target.
   357  
   358  # The target must be the newest version of itself.
   359  name: cycle1
   360  A: B1
   361  B1: A1
   362  B2: A2
   363  B3: A3
   364  build A:      A B1
   365  upgrade A B2: A B2
   366  upgrade* A:   A B3
   367  
   368  # golang.org/issue/29773:
   369  # Requirements of older versions of the target
   370  # must be carried over.
   371  name: cycle2
   372  A: B1
   373  A1: C1
   374  A2: D1
   375  B1: A1
   376  B2: A2
   377  C1: A2
   378  C2:
   379  D2:
   380  build A:    A B1 C1 D1
   381  upgrade* A: A B2 C2 D2
   382  
   383  # Cycles with multiple possible solutions.
   384  # (golang.org/issue/34086)
   385  name: cycle3
   386  M: A1 C2
   387  A1: B1
   388  B1: C1
   389  B2: C2
   390  C1:
   391  C2: B2
   392  build M: M A1 B2 C2
   393  req M:     A1 B2
   394  req M A:   A1 B2
   395  req M C:   A1 C2
   396  
   397  # Requirement minimization.
   398  
   399  name: req1
   400  A: B1 C1 D1 E1 F1
   401  B1: C1 E1 F1
   402  req A:   B1    D1
   403  req A C: B1 C1 D1
   404  
   405  name: req2
   406  A: G1 H1
   407  G1: H1
   408  H1: G1
   409  req A:   G1
   410  req A G: G1
   411  req A H: H1
   412  
   413  name: req3
   414  M: A1 B1
   415  A1: X1
   416  B1: X2
   417  X1: I1
   418  X2:
   419  req M: A1 B1
   420  
   421  name: reqnone
   422  M: Anone B1 D1 E1
   423  B1: Cnone D1
   424  E1: Fnone
   425  build M: M B1 D1 E1
   426  req M:     B1    E1
   427  
   428  name: reqdup
   429  M: A1 B1
   430  A1: B1
   431  B1:
   432  req M A A: A1
   433  
   434  name: reqcross
   435  M: A1 B1 C1
   436  A1: B1 C1
   437  B1: C1
   438  C1:
   439  req M A B: A1 B1
   440  `
   441  
   442  func Test(t *testing.T) {
   443  	var (
   444  		name string
   445  		reqs reqsMap
   446  		fns  []func(*testing.T)
   447  	)
   448  	flush := func() {
   449  		if name != "" {
   450  			t.Run(name, func(t *testing.T) {
   451  				for _, fn := range fns {
   452  					fn(t)
   453  				}
   454  				if len(fns) == 0 {
   455  					t.Errorf("no functions tested")
   456  				}
   457  			})
   458  		}
   459  	}
   460  	m := func(s string) module.Version {
   461  		return module.Version{Path: s[:1], Version: s[1:]}
   462  	}
   463  	ms := func(list []string) []module.Version {
   464  		var mlist []module.Version
   465  		for _, s := range list {
   466  			mlist = append(mlist, m(s))
   467  		}
   468  		return mlist
   469  	}
   470  	checkList := func(t *testing.T, desc string, list []module.Version, err error, val string) {
   471  		if err != nil {
   472  			t.Fatalf("%s: %v", desc, err)
   473  		}
   474  		vs := ms(strings.Fields(val))
   475  		if !reflect.DeepEqual(list, vs) {
   476  			t.Errorf("%s = %v, want %v", desc, list, vs)
   477  		}
   478  	}
   479  
   480  	for _, line := range strings.Split(tests, "\n") {
   481  		line = strings.TrimSpace(line)
   482  		if strings.HasPrefix(line, "#") || line == "" {
   483  			continue
   484  		}
   485  		i := strings.Index(line, ":")
   486  		if i < 0 {
   487  			t.Fatalf("missing colon: %q", line)
   488  		}
   489  		key := strings.TrimSpace(line[:i])
   490  		val := strings.TrimSpace(line[i+1:])
   491  		if key == "" {
   492  			t.Fatalf("missing key: %q", line)
   493  		}
   494  		kf := strings.Fields(key)
   495  		switch kf[0] {
   496  		case "name":
   497  			if len(kf) != 1 {
   498  				t.Fatalf("name takes no arguments: %q", line)
   499  			}
   500  			flush()
   501  			reqs = make(reqsMap)
   502  			fns = nil
   503  			name = val
   504  			continue
   505  		case "build":
   506  			if len(kf) != 2 {
   507  				t.Fatalf("build takes one argument: %q", line)
   508  			}
   509  			fns = append(fns, func(t *testing.T) {
   510  				list, err := BuildList([]module.Version{m(kf[1])}, reqs)
   511  				checkList(t, key, list, err, val)
   512  			})
   513  			continue
   514  		case "upgrade*":
   515  			if len(kf) != 2 {
   516  				t.Fatalf("upgrade* takes one argument: %q", line)
   517  			}
   518  			fns = append(fns, func(t *testing.T) {
   519  				list, err := UpgradeAll(m(kf[1]), reqs)
   520  				checkList(t, key, list, err, val)
   521  			})
   522  			continue
   523  		case "upgradereq":
   524  			if len(kf) < 2 {
   525  				t.Fatalf("upgrade takes at least one argument: %q", line)
   526  			}
   527  			fns = append(fns, func(t *testing.T) {
   528  				list, err := Upgrade(m(kf[1]), reqs, ms(kf[2:])...)
   529  				if err == nil {
   530  					// Copy the reqs map, but substitute the upgraded requirements in
   531  					// place of the target's original requirements.
   532  					upReqs := make(reqsMap, len(reqs))
   533  					for m, r := range reqs {
   534  						upReqs[m] = r
   535  					}
   536  					upReqs[m(kf[1])] = list
   537  
   538  					list, err = Req(m(kf[1]), nil, upReqs)
   539  				}
   540  				checkList(t, key, list, err, val)
   541  			})
   542  			continue
   543  		case "upgrade":
   544  			if len(kf) < 2 {
   545  				t.Fatalf("upgrade takes at least one argument: %q", line)
   546  			}
   547  			fns = append(fns, func(t *testing.T) {
   548  				list, err := Upgrade(m(kf[1]), reqs, ms(kf[2:])...)
   549  				checkList(t, key, list, err, val)
   550  			})
   551  			continue
   552  		case "downgrade":
   553  			if len(kf) < 2 {
   554  				t.Fatalf("downgrade takes at least one argument: %q", line)
   555  			}
   556  			fns = append(fns, func(t *testing.T) {
   557  				list, err := Downgrade(m(kf[1]), reqs, ms(kf[1:])...)
   558  				checkList(t, key, list, err, val)
   559  			})
   560  			continue
   561  		case "req":
   562  			if len(kf) < 2 {
   563  				t.Fatalf("req takes at least one argument: %q", line)
   564  			}
   565  			fns = append(fns, func(t *testing.T) {
   566  				list, err := Req(m(kf[1]), kf[2:], reqs)
   567  				checkList(t, key, list, err, val)
   568  			})
   569  			continue
   570  		}
   571  		if len(kf) == 1 && 'A' <= key[0] && key[0] <= 'Z' {
   572  			var rs []module.Version
   573  			for _, f := range strings.Fields(val) {
   574  				r := m(f)
   575  				if reqs[r] == nil {
   576  					reqs[r] = []module.Version{}
   577  				}
   578  				rs = append(rs, r)
   579  			}
   580  			reqs[m(key)] = rs
   581  			continue
   582  		}
   583  		t.Fatalf("bad line: %q", line)
   584  	}
   585  	flush()
   586  }
   587  
   588  type reqsMap map[module.Version][]module.Version
   589  
   590  func (r reqsMap) Max(_, v1, v2 string) string {
   591  	if v1 == "none" || v2 == "" {
   592  		return v2
   593  	}
   594  	if v2 == "none" || v1 == "" {
   595  		return v1
   596  	}
   597  	if v1 < v2 {
   598  		return v2
   599  	}
   600  	return v1
   601  }
   602  
   603  func (r reqsMap) Upgrade(m module.Version) (module.Version, error) {
   604  	u := module.Version{Version: "none"}
   605  	for k := range r {
   606  		if k.Path == m.Path && r.Max(k.Path, u.Version, k.Version) == k.Version && !strings.HasSuffix(k.Version, ".hidden") {
   607  			u = k
   608  		}
   609  	}
   610  	if u.Path == "" {
   611  		return module.Version{}, fmt.Errorf("missing module: %v", module.Version{Path: m.Path})
   612  	}
   613  	return u, nil
   614  }
   615  
   616  func (r reqsMap) Previous(m module.Version) (module.Version, error) {
   617  	var p module.Version
   618  	for k := range r {
   619  		if k.Path == m.Path && p.Version < k.Version && k.Version < m.Version && !strings.HasSuffix(k.Version, ".hidden") {
   620  			p = k
   621  		}
   622  	}
   623  	if p.Path == "" {
   624  		return module.Version{Path: m.Path, Version: "none"}, nil
   625  	}
   626  	return p, nil
   627  }
   628  
   629  func (r reqsMap) Required(m module.Version) ([]module.Version, error) {
   630  	rr, ok := r[m]
   631  	if !ok {
   632  		return nil, fmt.Errorf("missing module: %v", m)
   633  	}
   634  	return rr, nil
   635  }
   636  

View as plain text