1
2
3
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
531
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