1// Copyright 2014 Google Inc. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package blueprint
16
17import (
18	"bytes"
19	"errors"
20	"fmt"
21	"reflect"
22	"strings"
23	"sync"
24	"testing"
25	"time"
26
27	"github.com/google/blueprint/parser"
28)
29
30type Walker interface {
31	Walk() bool
32}
33
34func walkDependencyGraph(ctx *Context, topModule *moduleInfo, allowDuplicates bool) (string, string) {
35	var outputDown string
36	var outputUp string
37	ctx.walkDeps(topModule, allowDuplicates,
38		func(dep depInfo, parent *moduleInfo) bool {
39			outputDown += ctx.ModuleName(dep.module.logicModule)
40			if tag, ok := dep.tag.(walkerDepsTag); ok {
41				if !tag.follow {
42					return false
43				}
44			}
45			if dep.module.logicModule.(Walker).Walk() {
46				return true
47			}
48
49			return false
50		},
51		func(dep depInfo, parent *moduleInfo) {
52			outputUp += ctx.ModuleName(dep.module.logicModule)
53		})
54	return outputDown, outputUp
55}
56
57type depsProvider interface {
58	Deps() []string
59	IgnoreDeps() []string
60}
61
62type fooModule struct {
63	SimpleName
64	properties struct {
65		Deps         []string
66		Ignored_deps []string
67		Foo          string
68	}
69}
70
71func newFooModule() (Module, []interface{}) {
72	m := &fooModule{}
73	return m, []interface{}{&m.properties, &m.SimpleName.Properties}
74}
75
76func (f *fooModule) GenerateBuildActions(ModuleContext) {
77}
78
79func (f *fooModule) Deps() []string {
80	return f.properties.Deps
81}
82
83func (f *fooModule) IgnoreDeps() []string {
84	return f.properties.Ignored_deps
85}
86
87func (f *fooModule) Foo() string {
88	return f.properties.Foo
89}
90
91func (f *fooModule) Walk() bool {
92	return true
93}
94
95type barModule struct {
96	SimpleName
97	properties struct {
98		Deps         []string
99		Ignored_deps []string
100		Bar          bool
101	}
102}
103
104func newBarModule() (Module, []interface{}) {
105	m := &barModule{}
106	return m, []interface{}{&m.properties, &m.SimpleName.Properties}
107}
108
109func (b *barModule) Deps() []string {
110	return b.properties.Deps
111}
112
113func (b *barModule) IgnoreDeps() []string {
114	return b.properties.Ignored_deps
115}
116
117func (b *barModule) GenerateBuildActions(ModuleContext) {
118}
119
120func (b *barModule) Bar() bool {
121	return b.properties.Bar
122}
123
124func (b *barModule) Walk() bool {
125	return false
126}
127
128type walkerDepsTag struct {
129	BaseDependencyTag
130	// True if the dependency should be followed, false otherwise.
131	follow bool
132}
133
134func depsMutator(mctx BottomUpMutatorContext) {
135	if m, ok := mctx.Module().(depsProvider); ok {
136		mctx.AddDependency(mctx.Module(), walkerDepsTag{follow: false}, m.IgnoreDeps()...)
137		mctx.AddDependency(mctx.Module(), walkerDepsTag{follow: true}, m.Deps()...)
138	}
139}
140
141func TestContextParse(t *testing.T) {
142	ctx := NewContext()
143	ctx.RegisterModuleType("foo_module", newFooModule)
144	ctx.RegisterModuleType("bar_module", newBarModule)
145
146	r := bytes.NewBufferString(`
147		foo_module {
148	        name: "MyFooModule",
149			deps: ["MyBarModule"],
150		}
151
152		bar_module {
153	        name: "MyBarModule",
154		}
155	`)
156
157	_, _, errs := ctx.parseOne(".", "Blueprint", r, parser.NewScope(nil), nil)
158	if len(errs) > 0 {
159		t.Errorf("unexpected parse errors:")
160		for _, err := range errs {
161			t.Errorf("  %s", err)
162		}
163		t.FailNow()
164	}
165
166	_, errs = ctx.ResolveDependencies(nil)
167	if len(errs) > 0 {
168		t.Errorf("unexpected dep errors:")
169		for _, err := range errs {
170			t.Errorf("  %s", err)
171		}
172		t.FailNow()
173	}
174}
175
176// |===B---D       - represents a non-walkable edge
177// A               = represents a walkable edge
178// |===C===E---G
179//     |       |   A should not be visited because it's the root node.
180//     |===F===|   B, D and E should not be walked.
181func TestWalkDeps(t *testing.T) {
182	ctx := NewContext()
183	ctx.MockFileSystem(map[string][]byte{
184		"Blueprints": []byte(`
185			foo_module {
186			    name: "A",
187			    deps: ["B", "C"],
188			}
189
190			bar_module {
191			    name: "B",
192			    deps: ["D"],
193			}
194
195			foo_module {
196			    name: "C",
197			    deps: ["E", "F"],
198			}
199
200			foo_module {
201			    name: "D",
202			}
203
204			bar_module {
205			    name: "E",
206			    deps: ["G"],
207			}
208
209			foo_module {
210			    name: "F",
211			    deps: ["G"],
212			}
213
214			foo_module {
215			    name: "G",
216			}
217		`),
218	})
219
220	ctx.RegisterModuleType("foo_module", newFooModule)
221	ctx.RegisterModuleType("bar_module", newBarModule)
222	ctx.RegisterBottomUpMutator("deps", depsMutator)
223	_, errs := ctx.ParseBlueprintsFiles("Blueprints", nil)
224	if len(errs) > 0 {
225		t.Errorf("unexpected parse errors:")
226		for _, err := range errs {
227			t.Errorf("  %s", err)
228		}
229		t.FailNow()
230	}
231
232	_, errs = ctx.ResolveDependencies(nil)
233	if len(errs) > 0 {
234		t.Errorf("unexpected dep errors:")
235		for _, err := range errs {
236			t.Errorf("  %s", err)
237		}
238		t.FailNow()
239	}
240
241	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
242	outputDown, outputUp := walkDependencyGraph(ctx, topModule, false)
243	if outputDown != "BCEFG" {
244		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: BCEFG", outputDown)
245	}
246	if outputUp != "BEGFC" {
247		t.Errorf("unexpected walkDeps behaviour: %s\nup should be: BEGFC", outputUp)
248	}
249}
250
251// |===B---D           - represents a non-walkable edge
252// A                   = represents a walkable edge
253// |===C===E===\       A should not be visited because it's the root node.
254//     |       |       B, D should not be walked.
255//     |===F===G===H   G should be visited multiple times
256//         \===/       H should only be visited once
257func TestWalkDepsDuplicates(t *testing.T) {
258	ctx := NewContext()
259	ctx.MockFileSystem(map[string][]byte{
260		"Blueprints": []byte(`
261			foo_module {
262			    name: "A",
263			    deps: ["B", "C"],
264			}
265
266			bar_module {
267			    name: "B",
268			    deps: ["D"],
269			}
270
271			foo_module {
272			    name: "C",
273			    deps: ["E", "F"],
274			}
275
276			foo_module {
277			    name: "D",
278			}
279
280			foo_module {
281			    name: "E",
282			    deps: ["G"],
283			}
284
285			foo_module {
286			    name: "F",
287			    deps: ["G", "G"],
288			}
289
290			foo_module {
291			    name: "G",
292				deps: ["H"],
293			}
294
295			foo_module {
296			    name: "H",
297			}
298		`),
299	})
300
301	ctx.RegisterModuleType("foo_module", newFooModule)
302	ctx.RegisterModuleType("bar_module", newBarModule)
303	ctx.RegisterBottomUpMutator("deps", depsMutator)
304	_, errs := ctx.ParseBlueprintsFiles("Blueprints", nil)
305	if len(errs) > 0 {
306		t.Errorf("unexpected parse errors:")
307		for _, err := range errs {
308			t.Errorf("  %s", err)
309		}
310		t.FailNow()
311	}
312
313	_, errs = ctx.ResolveDependencies(nil)
314	if len(errs) > 0 {
315		t.Errorf("unexpected dep errors:")
316		for _, err := range errs {
317			t.Errorf("  %s", err)
318		}
319		t.FailNow()
320	}
321
322	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
323	outputDown, outputUp := walkDependencyGraph(ctx, topModule, true)
324	if outputDown != "BCEGHFGG" {
325		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: BCEGHFGG", outputDown)
326	}
327	if outputUp != "BHGEGGFC" {
328		t.Errorf("unexpected walkDeps behaviour: %s\nup should be: BHGEGGFC", outputUp)
329	}
330}
331
332//                     - represents a non-walkable edge
333// A                   = represents a walkable edge
334// |===B-------\       A should not be visited because it's the root node.
335//     |       |       B -> D should not be walked.
336//     |===C===D===E   B -> C -> D -> E should be walked
337func TestWalkDepsDuplicates_IgnoreFirstPath(t *testing.T) {
338	ctx := NewContext()
339	ctx.MockFileSystem(map[string][]byte{
340		"Blueprints": []byte(`
341			foo_module {
342			    name: "A",
343			    deps: ["B"],
344			}
345
346			foo_module {
347			    name: "B",
348			    deps: ["C"],
349			    ignored_deps: ["D"],
350			}
351
352			foo_module {
353			    name: "C",
354			    deps: ["D"],
355			}
356
357			foo_module {
358			    name: "D",
359			    deps: ["E"],
360			}
361
362			foo_module {
363			    name: "E",
364			}
365		`),
366	})
367
368	ctx.RegisterModuleType("foo_module", newFooModule)
369	ctx.RegisterModuleType("bar_module", newBarModule)
370	ctx.RegisterBottomUpMutator("deps", depsMutator)
371	_, errs := ctx.ParseBlueprintsFiles("Blueprints", nil)
372	if len(errs) > 0 {
373		t.Errorf("unexpected parse errors:")
374		for _, err := range errs {
375			t.Errorf("  %s", err)
376		}
377		t.FailNow()
378	}
379
380	_, errs = ctx.ResolveDependencies(nil)
381	if len(errs) > 0 {
382		t.Errorf("unexpected dep errors:")
383		for _, err := range errs {
384			t.Errorf("  %s", err)
385		}
386		t.FailNow()
387	}
388
389	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
390	outputDown, outputUp := walkDependencyGraph(ctx, topModule, true)
391	expectedDown := "BDCDE"
392	if outputDown != expectedDown {
393		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: %s", outputDown, expectedDown)
394	}
395	expectedUp := "DEDCB"
396	if outputUp != expectedUp {
397		t.Errorf("unexpected walkDeps behaviour: %s\nup should be: %s", outputUp, expectedUp)
398	}
399}
400
401func TestCreateModule(t *testing.T) {
402	ctx := newContext()
403	ctx.MockFileSystem(map[string][]byte{
404		"Blueprints": []byte(`
405			foo_module {
406			    name: "A",
407			    deps: ["B", "C"],
408			}
409		`),
410	})
411
412	ctx.RegisterTopDownMutator("create", createTestMutator)
413	ctx.RegisterBottomUpMutator("deps", depsMutator)
414
415	ctx.RegisterModuleType("foo_module", newFooModule)
416	ctx.RegisterModuleType("bar_module", newBarModule)
417	_, errs := ctx.ParseBlueprintsFiles("Blueprints", nil)
418	if len(errs) > 0 {
419		t.Errorf("unexpected parse errors:")
420		for _, err := range errs {
421			t.Errorf("  %s", err)
422		}
423		t.FailNow()
424	}
425
426	_, errs = ctx.ResolveDependencies(nil)
427	if len(errs) > 0 {
428		t.Errorf("unexpected dep errors:")
429		for _, err := range errs {
430			t.Errorf("  %s", err)
431		}
432		t.FailNow()
433	}
434
435	a := ctx.moduleGroupFromName("A", nil).modules.firstModule().logicModule.(*fooModule)
436	b := ctx.moduleGroupFromName("B", nil).modules.firstModule().logicModule.(*barModule)
437	c := ctx.moduleGroupFromName("C", nil).modules.firstModule().logicModule.(*barModule)
438	d := ctx.moduleGroupFromName("D", nil).modules.firstModule().logicModule.(*fooModule)
439
440	checkDeps := func(m Module, expected string) {
441		var deps []string
442		ctx.VisitDirectDeps(m, func(m Module) {
443			deps = append(deps, ctx.ModuleName(m))
444		})
445		got := strings.Join(deps, ",")
446		if got != expected {
447			t.Errorf("unexpected %q dependencies, got %q expected %q",
448				ctx.ModuleName(m), got, expected)
449		}
450	}
451
452	checkDeps(a, "B,C")
453	checkDeps(b, "D")
454	checkDeps(c, "D")
455	checkDeps(d, "")
456}
457
458func createTestMutator(ctx TopDownMutatorContext) {
459	type props struct {
460		Name string
461		Deps []string
462	}
463
464	ctx.CreateModule(newBarModule, &props{
465		Name: "B",
466		Deps: []string{"D"},
467	})
468
469	ctx.CreateModule(newBarModule, &props{
470		Name: "C",
471		Deps: []string{"D"},
472	})
473
474	ctx.CreateModule(newFooModule, &props{
475		Name: "D",
476	})
477}
478
479func TestWalkFileOrder(t *testing.T) {
480	// Run the test once to see how long it normally takes
481	start := time.Now()
482	doTestWalkFileOrder(t, time.Duration(0))
483	duration := time.Since(start)
484
485	// Run the test again, but put enough of a sleep into each visitor to detect ordering
486	// problems if they exist
487	doTestWalkFileOrder(t, duration)
488}
489
490// test that WalkBlueprintsFiles calls asyncVisitor in the right order
491func doTestWalkFileOrder(t *testing.T, sleepDuration time.Duration) {
492	// setup mock context
493	ctx := newContext()
494	mockFiles := map[string][]byte{
495		"Blueprints": []byte(`
496			sample_module {
497			    name: "a",
498			}
499		`),
500		"dir1/Blueprints": []byte(`
501			sample_module {
502			    name: "b",
503			}
504		`),
505		"dir1/dir2/Blueprints": []byte(`
506			sample_module {
507			    name: "c",
508			}
509		`),
510	}
511	ctx.MockFileSystem(mockFiles)
512
513	// prepare to monitor the visit order
514	visitOrder := []string{}
515	visitLock := sync.Mutex{}
516	correctVisitOrder := []string{"Blueprints", "dir1/Blueprints", "dir1/dir2/Blueprints"}
517
518	// sleep longer when processing the earlier files
519	chooseSleepDuration := func(fileName string) (duration time.Duration) {
520		duration = time.Duration(0)
521		for i := len(correctVisitOrder) - 1; i >= 0; i-- {
522			if fileName == correctVisitOrder[i] {
523				return duration
524			}
525			duration = duration + sleepDuration
526		}
527		panic("unrecognized file name " + fileName)
528	}
529
530	visitor := func(file *parser.File) {
531		time.Sleep(chooseSleepDuration(file.Name))
532		visitLock.Lock()
533		defer visitLock.Unlock()
534		visitOrder = append(visitOrder, file.Name)
535	}
536	keys := []string{"Blueprints", "dir1/Blueprints", "dir1/dir2/Blueprints"}
537
538	// visit the blueprints files
539	ctx.WalkBlueprintsFiles(".", keys, visitor)
540
541	// check the order
542	if !reflect.DeepEqual(visitOrder, correctVisitOrder) {
543		t.Errorf("Incorrect visit order; expected %v, got %v", correctVisitOrder, visitOrder)
544	}
545}
546
547// test that WalkBlueprintsFiles reports syntax errors
548func TestWalkingWithSyntaxError(t *testing.T) {
549	// setup mock context
550	ctx := newContext()
551	mockFiles := map[string][]byte{
552		"Blueprints": []byte(`
553			sample_module {
554			    name: "a" "b",
555			}
556		`),
557		"dir1/Blueprints": []byte(`
558			sample_module {
559			    name: "b",
560		`),
561		"dir1/dir2/Blueprints": []byte(`
562			sample_module {
563			    name: "c",
564			}
565		`),
566	}
567	ctx.MockFileSystem(mockFiles)
568
569	keys := []string{"Blueprints", "dir1/Blueprints", "dir1/dir2/Blueprints"}
570
571	// visit the blueprints files
572	_, errs := ctx.WalkBlueprintsFiles(".", keys, func(file *parser.File) {})
573
574	expectedErrs := []error{
575		errors.New(`Blueprints:3:18: expected "}", found String`),
576		errors.New(`dir1/Blueprints:4:3: expected "}", found EOF`),
577	}
578	if fmt.Sprintf("%s", expectedErrs) != fmt.Sprintf("%s", errs) {
579		t.Errorf("Incorrect errors; expected:\n%s\ngot:\n%s", expectedErrs, errs)
580	}
581
582}
583
584func TestParseFailsForModuleWithoutName(t *testing.T) {
585	ctx := NewContext()
586	ctx.MockFileSystem(map[string][]byte{
587		"Blueprints": []byte(`
588			foo_module {
589			    name: "A",
590			}
591
592			bar_module {
593			    deps: ["A"],
594			}
595		`),
596	})
597	ctx.RegisterModuleType("foo_module", newFooModule)
598	ctx.RegisterModuleType("bar_module", newBarModule)
599
600	_, errs := ctx.ParseBlueprintsFiles("Blueprints", nil)
601
602	expectedErrs := []error{
603		errors.New(`Blueprints:6:4: property 'name' is missing from a module`),
604	}
605	if fmt.Sprintf("%s", expectedErrs) != fmt.Sprintf("%s", errs) {
606		t.Errorf("Incorrect errors; expected:\n%s\ngot:\n%s", expectedErrs, errs)
607	}
608}
609
610func Test_findVariant(t *testing.T) {
611	module := &moduleInfo{
612		variant: variant{
613			name: "normal_local",
614			variations: variationMap{
615				"normal": "normal",
616				"local":  "local",
617			},
618			dependencyVariations: variationMap{
619				"normal": "normal",
620			},
621		},
622	}
623
624	type alias struct {
625		variant variant
626		target  int
627	}
628
629	makeDependencyGroup := func(in ...interface{}) *moduleGroup {
630		group := &moduleGroup{
631			name: "dep",
632		}
633		for _, x := range in {
634			switch m := x.(type) {
635			case *moduleInfo:
636				m.group = group
637				group.modules = append(group.modules, m)
638			case alias:
639				// aliases may need to target modules that haven't been processed
640				// yet, put an empty alias in for now.
641				group.modules = append(group.modules, nil)
642			default:
643				t.Fatalf("unexpected type %T", x)
644			}
645		}
646
647		for i, x := range in {
648			switch m := x.(type) {
649			case *moduleInfo:
650				// already added in the first pass
651			case alias:
652				group.modules[i] = &moduleAlias{
653					variant: m.variant,
654					target:  group.modules[m.target].moduleOrAliasTarget(),
655				}
656			default:
657				t.Fatalf("unexpected type %T", x)
658			}
659		}
660
661		return group
662	}
663
664	tests := []struct {
665		name         string
666		possibleDeps *moduleGroup
667		variations   []Variation
668		far          bool
669		reverse      bool
670		want         string
671	}{
672		{
673			name: "AddVariationDependencies(nil)",
674			// A dependency that matches the non-local variations of the module
675			possibleDeps: makeDependencyGroup(
676				&moduleInfo{
677					variant: variant{
678						name: "normal",
679						variations: variationMap{
680							"normal": "normal",
681						},
682					},
683				},
684			),
685			variations: nil,
686			far:        false,
687			reverse:    false,
688			want:       "normal",
689		},
690		{
691			name: "AddVariationDependencies(nil) to alias",
692			// A dependency with an alias that matches the non-local variations of the module
693			possibleDeps: makeDependencyGroup(
694				alias{
695					variant: variant{
696						name: "normal",
697						variations: variationMap{
698							"normal": "normal",
699						},
700					},
701					target: 1,
702				},
703				&moduleInfo{
704					variant: variant{
705						name: "normal_a",
706						variations: variationMap{
707							"normal": "normal",
708							"a":      "a",
709						},
710					},
711				},
712			),
713			variations: nil,
714			far:        false,
715			reverse:    false,
716			want:       "normal_a",
717		},
718		{
719			name: "AddVariationDependencies(a)",
720			// A dependency with local variations
721			possibleDeps: makeDependencyGroup(
722				&moduleInfo{
723					variant: variant{
724						name: "normal_a",
725						variations: variationMap{
726							"normal": "normal",
727							"a":      "a",
728						},
729					},
730				},
731			),
732			variations: []Variation{{"a", "a"}},
733			far:        false,
734			reverse:    false,
735			want:       "normal_a",
736		},
737		{
738			name: "AddFarVariationDependencies(far)",
739			// A dependency with far variations
740			possibleDeps: makeDependencyGroup(
741				&moduleInfo{
742					variant: variant{
743						name:       "",
744						variations: nil,
745					},
746				},
747				&moduleInfo{
748					variant: variant{
749						name: "far",
750						variations: variationMap{
751							"far": "far",
752						},
753					},
754				},
755			),
756			variations: []Variation{{"far", "far"}},
757			far:        true,
758			reverse:    false,
759			want:       "far",
760		},
761		{
762			name: "AddFarVariationDependencies(far) to alias",
763			// A dependency with far variations and aliases
764			possibleDeps: makeDependencyGroup(
765				alias{
766					variant: variant{
767						name: "far",
768						variations: variationMap{
769							"far": "far",
770						},
771					},
772					target: 2,
773				},
774				&moduleInfo{
775					variant: variant{
776						name: "far_a",
777						variations: variationMap{
778							"far": "far",
779							"a":   "a",
780						},
781					},
782				},
783				&moduleInfo{
784					variant: variant{
785						name: "far_b",
786						variations: variationMap{
787							"far": "far",
788							"b":   "b",
789						},
790					},
791				},
792			),
793			variations: []Variation{{"far", "far"}},
794			far:        true,
795			reverse:    false,
796			want:       "far_b",
797		},
798		{
799			name: "AddFarVariationDependencies(far, b) to missing",
800			// A dependency with far variations and aliases
801			possibleDeps: makeDependencyGroup(
802				alias{
803					variant: variant{
804						name: "far",
805						variations: variationMap{
806							"far": "far",
807						},
808					},
809					target: 1,
810				},
811				&moduleInfo{
812					variant: variant{
813						name: "far_a",
814						variations: variationMap{
815							"far": "far",
816							"a":   "a",
817						},
818					},
819				},
820			),
821			variations: []Variation{{"far", "far"}, {"a", "b"}},
822			far:        true,
823			reverse:    false,
824			want:       "nil",
825		},
826	}
827	for _, tt := range tests {
828		t.Run(tt.name, func(t *testing.T) {
829			got, _ := findVariant(module, tt.possibleDeps, tt.variations, tt.far, tt.reverse)
830			if g, w := got == nil, tt.want == "nil"; g != w {
831				t.Fatalf("findVariant() got = %v, want %v", got, tt.want)
832			}
833			if got != nil {
834				if g, w := got.String(), fmt.Sprintf("module %q variant %q", "dep", tt.want); g != w {
835					t.Errorf("findVariant() got = %v, want %v", g, w)
836				}
837			}
838		})
839	}
840}
841
842func Test_parallelVisit(t *testing.T) {
843	addDep := func(from, to *moduleInfo) {
844		from.directDeps = append(from.directDeps, depInfo{to, nil})
845		from.forwardDeps = append(from.forwardDeps, to)
846		to.reverseDeps = append(to.reverseDeps, from)
847	}
848
849	create := func(name string) *moduleInfo {
850		m := &moduleInfo{
851			group: &moduleGroup{
852				name: name,
853			},
854		}
855		m.group.modules = modulesOrAliases{m}
856		return m
857	}
858	moduleA := create("A")
859	moduleB := create("B")
860	moduleC := create("C")
861	moduleD := create("D")
862	moduleE := create("E")
863	moduleF := create("F")
864	moduleG := create("G")
865
866	// A depends on B, B depends on C.  Nothing depends on D through G, and they don't depend on
867	// anything.
868	addDep(moduleA, moduleB)
869	addDep(moduleB, moduleC)
870
871	t.Run("no modules", func(t *testing.T) {
872		errs := parallelVisit(nil, bottomUpVisitorImpl{}, 1,
873			func(module *moduleInfo, pause chan<- pauseSpec) bool {
874				panic("unexpected call to visitor")
875			})
876		if errs != nil {
877			t.Errorf("expected no errors, got %q", errs)
878		}
879	})
880	t.Run("bottom up", func(t *testing.T) {
881		order := ""
882		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 1,
883			func(module *moduleInfo, pause chan<- pauseSpec) bool {
884				order += module.group.name
885				return false
886			})
887		if errs != nil {
888			t.Errorf("expected no errors, got %q", errs)
889		}
890		if g, w := order, "CBA"; g != w {
891			t.Errorf("expected order %q, got %q", w, g)
892		}
893	})
894	t.Run("pause", func(t *testing.T) {
895		order := ""
896		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 1,
897			func(module *moduleInfo, pause chan<- pauseSpec) bool {
898				if module == moduleC {
899					// Pause module C on module D
900					unpause := make(chan struct{})
901					pause <- pauseSpec{moduleC, moduleD, unpause}
902					<-unpause
903				}
904				order += module.group.name
905				return false
906			})
907		if errs != nil {
908			t.Errorf("expected no errors, got %q", errs)
909		}
910		if g, w := order, "DCBA"; g != w {
911			t.Errorf("expected order %q, got %q", w, g)
912		}
913	})
914	t.Run("cancel", func(t *testing.T) {
915		order := ""
916		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 1,
917			func(module *moduleInfo, pause chan<- pauseSpec) bool {
918				order += module.group.name
919				// Cancel in module B
920				return module == moduleB
921			})
922		if errs != nil {
923			t.Errorf("expected no errors, got %q", errs)
924		}
925		if g, w := order, "CB"; g != w {
926			t.Errorf("expected order %q, got %q", w, g)
927		}
928	})
929	t.Run("pause and cancel", func(t *testing.T) {
930		order := ""
931		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 1,
932			func(module *moduleInfo, pause chan<- pauseSpec) bool {
933				if module == moduleC {
934					// Pause module C on module D
935					unpause := make(chan struct{})
936					pause <- pauseSpec{moduleC, moduleD, unpause}
937					<-unpause
938				}
939				order += module.group.name
940				// Cancel in module D
941				return module == moduleD
942			})
943		if errs != nil {
944			t.Errorf("expected no errors, got %q", errs)
945		}
946		if g, w := order, "D"; g != w {
947			t.Errorf("expected order %q, got %q", w, g)
948		}
949	})
950	t.Run("parallel", func(t *testing.T) {
951		order := ""
952		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
953			func(module *moduleInfo, pause chan<- pauseSpec) bool {
954				order += module.group.name
955				return false
956			})
957		if errs != nil {
958			t.Errorf("expected no errors, got %q", errs)
959		}
960		if g, w := order, "CBA"; g != w {
961			t.Errorf("expected order %q, got %q", w, g)
962		}
963	})
964	t.Run("pause existing", func(t *testing.T) {
965		order := ""
966		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
967			func(module *moduleInfo, pause chan<- pauseSpec) bool {
968				if module == moduleA {
969					// Pause module A on module B (an existing dependency)
970					unpause := make(chan struct{})
971					pause <- pauseSpec{moduleA, moduleB, unpause}
972					<-unpause
973				}
974				order += module.group.name
975				return false
976			})
977		if errs != nil {
978			t.Errorf("expected no errors, got %q", errs)
979		}
980		if g, w := order, "CBA"; g != w {
981			t.Errorf("expected order %q, got %q", w, g)
982		}
983	})
984	t.Run("cycle", func(t *testing.T) {
985		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
986			func(module *moduleInfo, pause chan<- pauseSpec) bool {
987				if module == moduleC {
988					// Pause module C on module A (a dependency cycle)
989					unpause := make(chan struct{})
990					pause <- pauseSpec{moduleC, moduleA, unpause}
991					<-unpause
992				}
993				return false
994			})
995		want := []string{
996			`encountered dependency cycle`,
997			`module "C" depends on module "A"`,
998			`module "A" depends on module "B"`,
999			`module "B" depends on module "C"`,
1000		}
1001		for i := range want {
1002			if len(errs) <= i {
1003				t.Errorf("missing error %s", want[i])
1004			} else if !strings.Contains(errs[i].Error(), want[i]) {
1005				t.Errorf("expected error %s, got %s", want[i], errs[i])
1006			}
1007		}
1008		if len(errs) > len(want) {
1009			for _, err := range errs[len(want):] {
1010				t.Errorf("unexpected error %s", err.Error())
1011			}
1012		}
1013	})
1014	t.Run("pause cycle", func(t *testing.T) {
1015		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 3,
1016			func(module *moduleInfo, pause chan<- pauseSpec) bool {
1017				if module == moduleC {
1018					// Pause module C on module D
1019					unpause := make(chan struct{})
1020					pause <- pauseSpec{moduleC, moduleD, unpause}
1021					<-unpause
1022				}
1023				if module == moduleD {
1024					// Pause module D on module C (a pause cycle)
1025					unpause := make(chan struct{})
1026					pause <- pauseSpec{moduleD, moduleC, unpause}
1027					<-unpause
1028				}
1029				return false
1030			})
1031		want := []string{
1032			`encountered dependency cycle`,
1033			`module "D" depends on module "C"`,
1034			`module "C" depends on module "D"`,
1035		}
1036		for i := range want {
1037			if len(errs) <= i {
1038				t.Errorf("missing error %s", want[i])
1039			} else if !strings.Contains(errs[i].Error(), want[i]) {
1040				t.Errorf("expected error %s, got %s", want[i], errs[i])
1041			}
1042		}
1043		if len(errs) > len(want) {
1044			for _, err := range errs[len(want):] {
1045				t.Errorf("unexpected error %s", err.Error())
1046			}
1047		}
1048	})
1049	t.Run("pause cycle with deps", func(t *testing.T) {
1050		pauseDeps := map[*moduleInfo]*moduleInfo{
1051			// F and G form a pause cycle
1052			moduleF: moduleG,
1053			moduleG: moduleF,
1054			// D depends on E which depends on the pause cycle, making E the first alphabetical
1055			// entry in pauseMap, which is not part of the cycle.
1056			moduleD: moduleE,
1057			moduleE: moduleF,
1058		}
1059		errs := parallelVisit([]*moduleInfo{moduleD, moduleE, moduleF, moduleG}, bottomUpVisitorImpl{}, 4,
1060			func(module *moduleInfo, pause chan<- pauseSpec) bool {
1061				if dep, ok := pauseDeps[module]; ok {
1062					unpause := make(chan struct{})
1063					pause <- pauseSpec{module, dep, unpause}
1064					<-unpause
1065				}
1066				return false
1067			})
1068		want := []string{
1069			`encountered dependency cycle`,
1070			`module "G" depends on module "F"`,
1071			`module "F" depends on module "G"`,
1072		}
1073		for i := range want {
1074			if len(errs) <= i {
1075				t.Errorf("missing error %s", want[i])
1076			} else if !strings.Contains(errs[i].Error(), want[i]) {
1077				t.Errorf("expected error %s, got %s", want[i], errs[i])
1078			}
1079		}
1080		if len(errs) > len(want) {
1081			for _, err := range errs[len(want):] {
1082				t.Errorf("unexpected error %s", err.Error())
1083			}
1084		}
1085	})
1086}
1087