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	"hash/fnv"
22	"reflect"
23	"strconv"
24	"strings"
25	"sync"
26	"testing"
27	"time"
28
29	"github.com/google/blueprint/parser"
30)
31
32type Walker interface {
33	Walk() bool
34}
35
36func walkDependencyGraph(ctx *Context, topModule *moduleInfo, allowDuplicates bool) (string, string) {
37	var outputDown string
38	var outputUp string
39	ctx.walkDeps(topModule, allowDuplicates,
40		func(dep depInfo, parent *moduleInfo) bool {
41			outputDown += ctx.ModuleName(dep.module.logicModule)
42			if tag, ok := dep.tag.(walkerDepsTag); ok {
43				if !tag.follow {
44					return false
45				}
46			}
47			if dep.module.logicModule.(Walker).Walk() {
48				return true
49			}
50
51			return false
52		},
53		func(dep depInfo, parent *moduleInfo) {
54			outputUp += ctx.ModuleName(dep.module.logicModule)
55		})
56	return outputDown, outputUp
57}
58
59type depsProvider interface {
60	Deps() []string
61	IgnoreDeps() []string
62}
63
64type fooModule struct {
65	SimpleName
66	properties struct {
67		Deps         []string
68		Ignored_deps []string
69		Foo          string
70	}
71}
72
73func newFooModule() (Module, []interface{}) {
74	m := &fooModule{}
75	return m, []interface{}{&m.properties, &m.SimpleName.Properties}
76}
77
78func (f *fooModule) GenerateBuildActions(ModuleContext) {
79}
80
81func (f *fooModule) Deps() []string {
82	return f.properties.Deps
83}
84
85func (f *fooModule) IgnoreDeps() []string {
86	return f.properties.Ignored_deps
87}
88
89func (f *fooModule) Foo() string {
90	return f.properties.Foo
91}
92
93func (f *fooModule) Walk() bool {
94	return true
95}
96
97type barModule struct {
98	SimpleName
99	properties struct {
100		Deps         []string
101		Ignored_deps []string
102		Bar          bool
103	}
104}
105
106func newBarModule() (Module, []interface{}) {
107	m := &barModule{}
108	return m, []interface{}{&m.properties, &m.SimpleName.Properties}
109}
110
111func (b *barModule) Deps() []string {
112	return b.properties.Deps
113}
114
115func (b *barModule) IgnoreDeps() []string {
116	return b.properties.Ignored_deps
117}
118
119func (b *barModule) GenerateBuildActions(ModuleContext) {
120}
121
122func (b *barModule) Bar() bool {
123	return b.properties.Bar
124}
125
126func (b *barModule) Walk() bool {
127	return false
128}
129
130type walkerDepsTag struct {
131	BaseDependencyTag
132	// True if the dependency should be followed, false otherwise.
133	follow bool
134}
135
136func depsMutator(mctx BottomUpMutatorContext) {
137	if m, ok := mctx.Module().(depsProvider); ok {
138		mctx.AddDependency(mctx.Module(), walkerDepsTag{follow: false}, m.IgnoreDeps()...)
139		mctx.AddDependency(mctx.Module(), walkerDepsTag{follow: true}, m.Deps()...)
140	}
141}
142
143func TestContextParse(t *testing.T) {
144	ctx := NewContext()
145	ctx.RegisterModuleType("foo_module", newFooModule)
146	ctx.RegisterModuleType("bar_module", newBarModule)
147
148	r := bytes.NewBufferString(`
149		foo_module {
150	        name: "MyFooModule",
151			deps: ["MyBarModule"],
152		}
153
154		bar_module {
155	        name: "MyBarModule",
156		}
157	`)
158
159	_, _, errs := ctx.parseOne(".", "Blueprint", r, parser.NewScope(nil), nil)
160	if len(errs) > 0 {
161		t.Errorf("unexpected parse errors:")
162		for _, err := range errs {
163			t.Errorf("  %s", err)
164		}
165		t.FailNow()
166	}
167
168	_, errs = ctx.ResolveDependencies(nil)
169	if len(errs) > 0 {
170		t.Errorf("unexpected dep errors:")
171		for _, err := range errs {
172			t.Errorf("  %s", err)
173		}
174		t.FailNow()
175	}
176}
177
178// > |===B---D       - represents a non-walkable edge
179// > A               = represents a walkable edge
180// > |===C===E---G
181// >     |       |   A should not be visited because it's the root node.
182// >     |===F===|   B, D and E should not be walked.
183func TestWalkDeps(t *testing.T) {
184	ctx := NewContext()
185	ctx.MockFileSystem(map[string][]byte{
186		"Android.bp": []byte(`
187			foo_module {
188			    name: "A",
189			    deps: ["B", "C"],
190			}
191
192			bar_module {
193			    name: "B",
194			    deps: ["D"],
195			}
196
197			foo_module {
198			    name: "C",
199			    deps: ["E", "F"],
200			}
201
202			foo_module {
203			    name: "D",
204			}
205
206			bar_module {
207			    name: "E",
208			    deps: ["G"],
209			}
210
211			foo_module {
212			    name: "F",
213			    deps: ["G"],
214			}
215
216			foo_module {
217			    name: "G",
218			}
219		`),
220	})
221
222	ctx.RegisterModuleType("foo_module", newFooModule)
223	ctx.RegisterModuleType("bar_module", newBarModule)
224	ctx.RegisterBottomUpMutator("deps", depsMutator)
225	_, errs := ctx.ParseBlueprintsFiles("Android.bp", nil)
226	if len(errs) > 0 {
227		t.Errorf("unexpected parse errors:")
228		for _, err := range errs {
229			t.Errorf("  %s", err)
230		}
231		t.FailNow()
232	}
233
234	_, errs = ctx.ResolveDependencies(nil)
235	if len(errs) > 0 {
236		t.Errorf("unexpected dep errors:")
237		for _, err := range errs {
238			t.Errorf("  %s", err)
239		}
240		t.FailNow()
241	}
242
243	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
244	outputDown, outputUp := walkDependencyGraph(ctx, topModule, false)
245	if outputDown != "BCEFG" {
246		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: BCEFG", outputDown)
247	}
248	if outputUp != "BEGFC" {
249		t.Errorf("unexpected walkDeps behaviour: %s\nup should be: BEGFC", outputUp)
250	}
251}
252
253// > |===B---D           - represents a non-walkable edge
254// > A                   = represents a walkable edge
255// > |===C===E===\       A should not be visited because it's the root node.
256// >     |       |       B, D should not be walked.
257// >     |===F===G===H   G should be visited multiple times
258// >         \===/       H should only be visited once
259func TestWalkDepsDuplicates(t *testing.T) {
260	ctx := NewContext()
261	ctx.MockFileSystem(map[string][]byte{
262		"Android.bp": []byte(`
263			foo_module {
264			    name: "A",
265			    deps: ["B", "C"],
266			}
267
268			bar_module {
269			    name: "B",
270			    deps: ["D"],
271			}
272
273			foo_module {
274			    name: "C",
275			    deps: ["E", "F"],
276			}
277
278			foo_module {
279			    name: "D",
280			}
281
282			foo_module {
283			    name: "E",
284			    deps: ["G"],
285			}
286
287			foo_module {
288			    name: "F",
289			    deps: ["G", "G"],
290			}
291
292			foo_module {
293			    name: "G",
294				deps: ["H"],
295			}
296
297			foo_module {
298			    name: "H",
299			}
300		`),
301	})
302
303	ctx.RegisterModuleType("foo_module", newFooModule)
304	ctx.RegisterModuleType("bar_module", newBarModule)
305	ctx.RegisterBottomUpMutator("deps", depsMutator)
306	_, errs := ctx.ParseBlueprintsFiles("Android.bp", nil)
307	if len(errs) > 0 {
308		t.Errorf("unexpected parse errors:")
309		for _, err := range errs {
310			t.Errorf("  %s", err)
311		}
312		t.FailNow()
313	}
314
315	_, errs = ctx.ResolveDependencies(nil)
316	if len(errs) > 0 {
317		t.Errorf("unexpected dep errors:")
318		for _, err := range errs {
319			t.Errorf("  %s", err)
320		}
321		t.FailNow()
322	}
323
324	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
325	outputDown, outputUp := walkDependencyGraph(ctx, topModule, true)
326	if outputDown != "BCEGHFGG" {
327		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: BCEGHFGG", outputDown)
328	}
329	if outputUp != "BHGEGGFC" {
330		t.Errorf("unexpected walkDeps behaviour: %s\nup should be: BHGEGGFC", outputUp)
331	}
332}
333
334// >                     - represents a non-walkable edge
335// > A                   = represents a walkable edge
336// > |===B-------\       A should not be visited because it's the root node.
337// >     |       |       B -> D should not be walked.
338// >     |===C===D===E   B -> C -> D -> E should be walked
339func TestWalkDepsDuplicates_IgnoreFirstPath(t *testing.T) {
340	ctx := NewContext()
341	ctx.MockFileSystem(map[string][]byte{
342		"Android.bp": []byte(`
343			foo_module {
344			    name: "A",
345			    deps: ["B"],
346			}
347
348			foo_module {
349			    name: "B",
350			    deps: ["C"],
351			    ignored_deps: ["D"],
352			}
353
354			foo_module {
355			    name: "C",
356			    deps: ["D"],
357			}
358
359			foo_module {
360			    name: "D",
361			    deps: ["E"],
362			}
363
364			foo_module {
365			    name: "E",
366			}
367		`),
368	})
369
370	ctx.RegisterModuleType("foo_module", newFooModule)
371	ctx.RegisterModuleType("bar_module", newBarModule)
372	ctx.RegisterBottomUpMutator("deps", depsMutator)
373	_, errs := ctx.ParseBlueprintsFiles("Android.bp", nil)
374	if len(errs) > 0 {
375		t.Errorf("unexpected parse errors:")
376		for _, err := range errs {
377			t.Errorf("  %s", err)
378		}
379		t.FailNow()
380	}
381
382	_, errs = ctx.ResolveDependencies(nil)
383	if len(errs) > 0 {
384		t.Errorf("unexpected dep errors:")
385		for _, err := range errs {
386			t.Errorf("  %s", err)
387		}
388		t.FailNow()
389	}
390
391	topModule := ctx.moduleGroupFromName("A", nil).modules.firstModule()
392	outputDown, outputUp := walkDependencyGraph(ctx, topModule, true)
393	expectedDown := "BDCDE"
394	if outputDown != expectedDown {
395		t.Errorf("unexpected walkDeps behaviour: %s\ndown should be: %s", outputDown, expectedDown)
396	}
397	expectedUp := "DEDCB"
398	if outputUp != expectedUp {
399		t.Errorf("unexpected walkDeps behaviour: %s\nup should be: %s", outputUp, expectedUp)
400	}
401}
402
403func TestCreateModule(t *testing.T) {
404	ctx := newContext()
405	ctx.MockFileSystem(map[string][]byte{
406		"Android.bp": []byte(`
407			foo_module {
408			    name: "A",
409			    deps: ["B", "C"],
410			}
411		`),
412	})
413
414	ctx.RegisterTopDownMutator("create", createTestMutator)
415	ctx.RegisterBottomUpMutator("deps", depsMutator)
416
417	ctx.RegisterModuleType("foo_module", newFooModule)
418	ctx.RegisterModuleType("bar_module", newBarModule)
419	_, errs := ctx.ParseBlueprintsFiles("Android.bp", nil)
420	if len(errs) > 0 {
421		t.Errorf("unexpected parse errors:")
422		for _, err := range errs {
423			t.Errorf("  %s", err)
424		}
425		t.FailNow()
426	}
427
428	_, errs = ctx.ResolveDependencies(nil)
429	if len(errs) > 0 {
430		t.Errorf("unexpected dep errors:")
431		for _, err := range errs {
432			t.Errorf("  %s", err)
433		}
434		t.FailNow()
435	}
436
437	a := ctx.moduleGroupFromName("A", nil).modules.firstModule().logicModule.(*fooModule)
438	b := ctx.moduleGroupFromName("B", nil).modules.firstModule().logicModule.(*barModule)
439	c := ctx.moduleGroupFromName("C", nil).modules.firstModule().logicModule.(*barModule)
440	d := ctx.moduleGroupFromName("D", nil).modules.firstModule().logicModule.(*fooModule)
441
442	checkDeps := func(m Module, expected string) {
443		var deps []string
444		ctx.VisitDirectDeps(m, func(m Module) {
445			deps = append(deps, ctx.ModuleName(m))
446		})
447		got := strings.Join(deps, ",")
448		if got != expected {
449			t.Errorf("unexpected %q dependencies, got %q expected %q",
450				ctx.ModuleName(m), got, expected)
451		}
452	}
453
454	checkDeps(a, "B,C")
455	checkDeps(b, "D")
456	checkDeps(c, "D")
457	checkDeps(d, "")
458}
459
460func createTestMutator(ctx TopDownMutatorContext) {
461	type props struct {
462		Name string
463		Deps []string
464	}
465
466	ctx.CreateModule(newBarModule, "new_bar", &props{
467		Name: "B",
468		Deps: []string{"D"},
469	})
470
471	ctx.CreateModule(newBarModule, "new_bar", &props{
472		Name: "C",
473		Deps: []string{"D"},
474	})
475
476	ctx.CreateModule(newFooModule, "new_foo", &props{
477		Name: "D",
478	})
479}
480
481func TestWalkFileOrder(t *testing.T) {
482	// Run the test once to see how long it normally takes
483	start := time.Now()
484	doTestWalkFileOrder(t, time.Duration(0))
485	duration := time.Since(start)
486
487	// Run the test again, but put enough of a sleep into each visitor to detect ordering
488	// problems if they exist
489	doTestWalkFileOrder(t, duration)
490}
491
492// test that WalkBlueprintsFiles calls asyncVisitor in the right order
493func doTestWalkFileOrder(t *testing.T, sleepDuration time.Duration) {
494	// setup mock context
495	ctx := newContext()
496	mockFiles := map[string][]byte{
497		"Android.bp": []byte(`
498			sample_module {
499			    name: "a",
500			}
501		`),
502		"dir1/Android.bp": []byte(`
503			sample_module {
504			    name: "b",
505			}
506		`),
507		"dir1/dir2/Android.bp": []byte(`
508			sample_module {
509			    name: "c",
510			}
511		`),
512	}
513	ctx.MockFileSystem(mockFiles)
514
515	// prepare to monitor the visit order
516	visitOrder := []string{}
517	visitLock := sync.Mutex{}
518	correctVisitOrder := []string{"Android.bp", "dir1/Android.bp", "dir1/dir2/Android.bp"}
519
520	// sleep longer when processing the earlier files
521	chooseSleepDuration := func(fileName string) (duration time.Duration) {
522		duration = time.Duration(0)
523		for i := len(correctVisitOrder) - 1; i >= 0; i-- {
524			if fileName == correctVisitOrder[i] {
525				return duration
526			}
527			duration = duration + sleepDuration
528		}
529		panic("unrecognized file name " + fileName)
530	}
531
532	visitor := func(file *parser.File) {
533		time.Sleep(chooseSleepDuration(file.Name))
534		visitLock.Lock()
535		defer visitLock.Unlock()
536		visitOrder = append(visitOrder, file.Name)
537	}
538	keys := []string{"Android.bp", "dir1/Android.bp", "dir1/dir2/Android.bp"}
539
540	// visit the blueprints files
541	ctx.WalkBlueprintsFiles(".", keys, visitor)
542
543	// check the order
544	if !reflect.DeepEqual(visitOrder, correctVisitOrder) {
545		t.Errorf("Incorrect visit order; expected %v, got %v", correctVisitOrder, visitOrder)
546	}
547}
548
549// test that WalkBlueprintsFiles reports syntax errors
550func TestWalkingWithSyntaxError(t *testing.T) {
551	// setup mock context
552	ctx := newContext()
553	mockFiles := map[string][]byte{
554		"Android.bp": []byte(`
555			sample_module {
556			    name: "a" "b",
557			}
558		`),
559		"dir1/Android.bp": []byte(`
560			sample_module {
561			    name: "b",
562		`),
563		"dir1/dir2/Android.bp": []byte(`
564			sample_module {
565			    name: "c",
566			}
567		`),
568	}
569	ctx.MockFileSystem(mockFiles)
570
571	keys := []string{"Android.bp", "dir1/Android.bp", "dir1/dir2/Android.bp"}
572
573	// visit the blueprints files
574	_, errs := ctx.WalkBlueprintsFiles(".", keys, func(file *parser.File) {})
575
576	expectedErrs := []error{
577		errors.New(`Android.bp:3:18: expected "}", found String`),
578		errors.New(`dir1/Android.bp:4:3: expected "}", found EOF`),
579	}
580	if fmt.Sprintf("%s", expectedErrs) != fmt.Sprintf("%s", errs) {
581		t.Errorf("Incorrect errors; expected:\n%s\ngot:\n%s", expectedErrs, errs)
582	}
583
584}
585
586func TestParseFailsForModuleWithoutName(t *testing.T) {
587	ctx := NewContext()
588	ctx.MockFileSystem(map[string][]byte{
589		"Android.bp": []byte(`
590			foo_module {
591			    name: "A",
592			}
593
594			bar_module {
595			    deps: ["A"],
596			}
597		`),
598	})
599	ctx.RegisterModuleType("foo_module", newFooModule)
600	ctx.RegisterModuleType("bar_module", newBarModule)
601
602	_, errs := ctx.ParseBlueprintsFiles("Android.bp", nil)
603
604	expectedErrs := []error{
605		errors.New(`Android.bp:6:4: property 'name' is missing from a module`),
606	}
607	if fmt.Sprintf("%s", expectedErrs) != fmt.Sprintf("%s", errs) {
608		t.Errorf("Incorrect errors; expected:\n%s\ngot:\n%s", expectedErrs, errs)
609	}
610}
611
612func Test_findVariant(t *testing.T) {
613	module := &moduleInfo{
614		variant: variant{
615			name: "normal_local",
616			variations: variationMap{
617				"normal": "normal",
618				"local":  "local",
619			},
620			dependencyVariations: variationMap{
621				"normal": "normal",
622			},
623		},
624	}
625
626	type alias struct {
627		variant variant
628		target  int
629	}
630
631	makeDependencyGroup := func(in ...interface{}) *moduleGroup {
632		group := &moduleGroup{
633			name: "dep",
634		}
635		for _, x := range in {
636			switch m := x.(type) {
637			case *moduleInfo:
638				m.group = group
639				group.modules = append(group.modules, m)
640			case alias:
641				// aliases may need to target modules that haven't been processed
642				// yet, put an empty alias in for now.
643				group.modules = append(group.modules, nil)
644			default:
645				t.Fatalf("unexpected type %T", x)
646			}
647		}
648
649		for i, x := range in {
650			switch m := x.(type) {
651			case *moduleInfo:
652				// already added in the first pass
653			case alias:
654				group.modules[i] = &moduleAlias{
655					variant: m.variant,
656					target:  group.modules[m.target].moduleOrAliasTarget(),
657				}
658			default:
659				t.Fatalf("unexpected type %T", x)
660			}
661		}
662
663		return group
664	}
665
666	tests := []struct {
667		name         string
668		possibleDeps *moduleGroup
669		variations   []Variation
670		far          bool
671		reverse      bool
672		want         string
673	}{
674		{
675			name: "AddVariationDependencies(nil)",
676			// A dependency that matches the non-local variations of the module
677			possibleDeps: makeDependencyGroup(
678				&moduleInfo{
679					variant: variant{
680						name: "normal",
681						variations: variationMap{
682							"normal": "normal",
683						},
684					},
685				},
686			),
687			variations: nil,
688			far:        false,
689			reverse:    false,
690			want:       "normal",
691		},
692		{
693			name: "AddVariationDependencies(nil) to alias",
694			// A dependency with an alias that matches the non-local variations of the module
695			possibleDeps: makeDependencyGroup(
696				alias{
697					variant: variant{
698						name: "normal",
699						variations: variationMap{
700							"normal": "normal",
701						},
702					},
703					target: 1,
704				},
705				&moduleInfo{
706					variant: variant{
707						name: "normal_a",
708						variations: variationMap{
709							"normal": "normal",
710							"a":      "a",
711						},
712					},
713				},
714			),
715			variations: nil,
716			far:        false,
717			reverse:    false,
718			want:       "normal_a",
719		},
720		{
721			name: "AddVariationDependencies(a)",
722			// A dependency with local variations
723			possibleDeps: makeDependencyGroup(
724				&moduleInfo{
725					variant: variant{
726						name: "normal_a",
727						variations: variationMap{
728							"normal": "normal",
729							"a":      "a",
730						},
731					},
732				},
733			),
734			variations: []Variation{{"a", "a"}},
735			far:        false,
736			reverse:    false,
737			want:       "normal_a",
738		},
739		{
740			name: "AddFarVariationDependencies(far)",
741			// A dependency with far variations
742			possibleDeps: makeDependencyGroup(
743				&moduleInfo{
744					variant: variant{
745						name:       "",
746						variations: nil,
747					},
748				},
749				&moduleInfo{
750					variant: variant{
751						name: "far",
752						variations: variationMap{
753							"far": "far",
754						},
755					},
756				},
757			),
758			variations: []Variation{{"far", "far"}},
759			far:        true,
760			reverse:    false,
761			want:       "far",
762		},
763		{
764			name: "AddFarVariationDependencies(far) to alias",
765			// A dependency with far variations and aliases
766			possibleDeps: makeDependencyGroup(
767				alias{
768					variant: variant{
769						name: "far",
770						variations: variationMap{
771							"far": "far",
772						},
773					},
774					target: 2,
775				},
776				&moduleInfo{
777					variant: variant{
778						name: "far_a",
779						variations: variationMap{
780							"far": "far",
781							"a":   "a",
782						},
783					},
784				},
785				&moduleInfo{
786					variant: variant{
787						name: "far_b",
788						variations: variationMap{
789							"far": "far",
790							"b":   "b",
791						},
792					},
793				},
794			),
795			variations: []Variation{{"far", "far"}},
796			far:        true,
797			reverse:    false,
798			want:       "far_b",
799		},
800		{
801			name: "AddFarVariationDependencies(far, b) to missing",
802			// A dependency with far variations and aliases
803			possibleDeps: makeDependencyGroup(
804				alias{
805					variant: variant{
806						name: "far",
807						variations: variationMap{
808							"far": "far",
809						},
810					},
811					target: 1,
812				},
813				&moduleInfo{
814					variant: variant{
815						name: "far_a",
816						variations: variationMap{
817							"far": "far",
818							"a":   "a",
819						},
820					},
821				},
822			),
823			variations: []Variation{{"far", "far"}, {"a", "b"}},
824			far:        true,
825			reverse:    false,
826			want:       "nil",
827		},
828	}
829	for _, tt := range tests {
830		t.Run(tt.name, func(t *testing.T) {
831			ctx := NewContext()
832			got, _ := ctx.findVariant(module, nil, tt.possibleDeps, tt.variations, tt.far, tt.reverse)
833			if g, w := got == nil, tt.want == "nil"; g != w {
834				t.Fatalf("findVariant() got = %v, want %v", got, tt.want)
835			}
836			if got != nil {
837				if g, w := got.String(), fmt.Sprintf("module %q variant %q", "dep", tt.want); g != w {
838					t.Errorf("findVariant() got = %v, want %v", g, w)
839				}
840			}
841		})
842	}
843}
844
845func Test_parallelVisit(t *testing.T) {
846	addDep := func(from, to *moduleInfo) {
847		from.directDeps = append(from.directDeps, depInfo{to, nil})
848		from.forwardDeps = append(from.forwardDeps, to)
849		to.reverseDeps = append(to.reverseDeps, from)
850	}
851
852	create := func(name string) *moduleInfo {
853		m := &moduleInfo{
854			group: &moduleGroup{
855				name: name,
856			},
857		}
858		m.group.modules = modulesOrAliases{m}
859		return m
860	}
861	moduleA := create("A")
862	moduleB := create("B")
863	moduleC := create("C")
864	moduleD := create("D")
865	moduleE := create("E")
866	moduleF := create("F")
867	moduleG := create("G")
868
869	// A depends on B, B depends on C.  Nothing depends on D through G, and they don't depend on
870	// anything.
871	addDep(moduleA, moduleB)
872	addDep(moduleB, moduleC)
873
874	t.Run("no modules", func(t *testing.T) {
875		errs := parallelVisit(nil, bottomUpVisitorImpl{}, 1,
876			func(module *moduleInfo, pause chan<- pauseSpec) bool {
877				panic("unexpected call to visitor")
878			})
879		if errs != nil {
880			t.Errorf("expected no errors, got %q", errs)
881		}
882	})
883	t.Run("bottom up", func(t *testing.T) {
884		order := ""
885		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 1,
886			func(module *moduleInfo, pause chan<- pauseSpec) bool {
887				order += module.group.name
888				return false
889			})
890		if errs != nil {
891			t.Errorf("expected no errors, got %q", errs)
892		}
893		if g, w := order, "CBA"; g != w {
894			t.Errorf("expected order %q, got %q", w, g)
895		}
896	})
897	t.Run("pause", func(t *testing.T) {
898		order := ""
899		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 1,
900			func(module *moduleInfo, pause chan<- pauseSpec) bool {
901				if module == moduleC {
902					// Pause module C on module D
903					unpause := make(chan struct{})
904					pause <- pauseSpec{moduleC, moduleD, unpause}
905					<-unpause
906				}
907				order += module.group.name
908				return false
909			})
910		if errs != nil {
911			t.Errorf("expected no errors, got %q", errs)
912		}
913		if g, w := order, "DCBA"; g != w {
914			t.Errorf("expected order %q, got %q", w, g)
915		}
916	})
917	t.Run("cancel", func(t *testing.T) {
918		order := ""
919		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 1,
920			func(module *moduleInfo, pause chan<- pauseSpec) bool {
921				order += module.group.name
922				// Cancel in module B
923				return module == moduleB
924			})
925		if errs != nil {
926			t.Errorf("expected no errors, got %q", errs)
927		}
928		if g, w := order, "CB"; g != w {
929			t.Errorf("expected order %q, got %q", w, g)
930		}
931	})
932	t.Run("pause and cancel", func(t *testing.T) {
933		order := ""
934		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 1,
935			func(module *moduleInfo, pause chan<- pauseSpec) bool {
936				if module == moduleC {
937					// Pause module C on module D
938					unpause := make(chan struct{})
939					pause <- pauseSpec{moduleC, moduleD, unpause}
940					<-unpause
941				}
942				order += module.group.name
943				// Cancel in module D
944				return module == moduleD
945			})
946		if errs != nil {
947			t.Errorf("expected no errors, got %q", errs)
948		}
949		if g, w := order, "D"; g != w {
950			t.Errorf("expected order %q, got %q", w, g)
951		}
952	})
953	t.Run("parallel", func(t *testing.T) {
954		order := ""
955		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
956			func(module *moduleInfo, pause chan<- pauseSpec) bool {
957				order += module.group.name
958				return false
959			})
960		if errs != nil {
961			t.Errorf("expected no errors, got %q", errs)
962		}
963		if g, w := order, "CBA"; g != w {
964			t.Errorf("expected order %q, got %q", w, g)
965		}
966	})
967	t.Run("pause existing", func(t *testing.T) {
968		order := ""
969		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
970			func(module *moduleInfo, pause chan<- pauseSpec) bool {
971				if module == moduleA {
972					// Pause module A on module B (an existing dependency)
973					unpause := make(chan struct{})
974					pause <- pauseSpec{moduleA, moduleB, unpause}
975					<-unpause
976				}
977				order += module.group.name
978				return false
979			})
980		if errs != nil {
981			t.Errorf("expected no errors, got %q", errs)
982		}
983		if g, w := order, "CBA"; g != w {
984			t.Errorf("expected order %q, got %q", w, g)
985		}
986	})
987	t.Run("cycle", func(t *testing.T) {
988		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC}, bottomUpVisitorImpl{}, 3,
989			func(module *moduleInfo, pause chan<- pauseSpec) bool {
990				if module == moduleC {
991					// Pause module C on module A (a dependency cycle)
992					unpause := make(chan struct{})
993					pause <- pauseSpec{moduleC, moduleA, unpause}
994					<-unpause
995				}
996				return false
997			})
998		want := []string{
999			`encountered dependency cycle`,
1000			`module "C" depends on module "A"`,
1001			`module "A" depends on module "B"`,
1002			`module "B" depends on module "C"`,
1003		}
1004		for i := range want {
1005			if len(errs) <= i {
1006				t.Errorf("missing error %s", want[i])
1007			} else if !strings.Contains(errs[i].Error(), want[i]) {
1008				t.Errorf("expected error %s, got %s", want[i], errs[i])
1009			}
1010		}
1011		if len(errs) > len(want) {
1012			for _, err := range errs[len(want):] {
1013				t.Errorf("unexpected error %s", err.Error())
1014			}
1015		}
1016	})
1017	t.Run("pause cycle", func(t *testing.T) {
1018		errs := parallelVisit([]*moduleInfo{moduleA, moduleB, moduleC, moduleD}, bottomUpVisitorImpl{}, 3,
1019			func(module *moduleInfo, pause chan<- pauseSpec) bool {
1020				if module == moduleC {
1021					// Pause module C on module D
1022					unpause := make(chan struct{})
1023					pause <- pauseSpec{moduleC, moduleD, unpause}
1024					<-unpause
1025				}
1026				if module == moduleD {
1027					// Pause module D on module C (a pause cycle)
1028					unpause := make(chan struct{})
1029					pause <- pauseSpec{moduleD, moduleC, unpause}
1030					<-unpause
1031				}
1032				return false
1033			})
1034		want := []string{
1035			`encountered dependency cycle`,
1036			`module "D" depends on module "C"`,
1037			`module "C" depends on module "D"`,
1038		}
1039		for i := range want {
1040			if len(errs) <= i {
1041				t.Errorf("missing error %s", want[i])
1042			} else if !strings.Contains(errs[i].Error(), want[i]) {
1043				t.Errorf("expected error %s, got %s", want[i], errs[i])
1044			}
1045		}
1046		if len(errs) > len(want) {
1047			for _, err := range errs[len(want):] {
1048				t.Errorf("unexpected error %s", err.Error())
1049			}
1050		}
1051	})
1052	t.Run("pause cycle with deps", func(t *testing.T) {
1053		pauseDeps := map[*moduleInfo]*moduleInfo{
1054			// F and G form a pause cycle
1055			moduleF: moduleG,
1056			moduleG: moduleF,
1057			// D depends on E which depends on the pause cycle, making E the first alphabetical
1058			// entry in pauseMap, which is not part of the cycle.
1059			moduleD: moduleE,
1060			moduleE: moduleF,
1061		}
1062		errs := parallelVisit([]*moduleInfo{moduleD, moduleE, moduleF, moduleG}, bottomUpVisitorImpl{}, 4,
1063			func(module *moduleInfo, pause chan<- pauseSpec) bool {
1064				if dep, ok := pauseDeps[module]; ok {
1065					unpause := make(chan struct{})
1066					pause <- pauseSpec{module, dep, unpause}
1067					<-unpause
1068				}
1069				return false
1070			})
1071		want := []string{
1072			`encountered dependency cycle`,
1073			`module "G" depends on module "F"`,
1074			`module "F" depends on module "G"`,
1075		}
1076		for i := range want {
1077			if len(errs) <= i {
1078				t.Errorf("missing error %s", want[i])
1079			} else if !strings.Contains(errs[i].Error(), want[i]) {
1080				t.Errorf("expected error %s, got %s", want[i], errs[i])
1081			}
1082		}
1083		if len(errs) > len(want) {
1084			for _, err := range errs[len(want):] {
1085				t.Errorf("unexpected error %s", err.Error())
1086			}
1087		}
1088	})
1089}
1090
1091func TestDeduplicateOrderOnlyDeps(t *testing.T) {
1092	b := func(output string, inputs []string, orderOnlyDeps []string) *buildDef {
1093		return &buildDef{
1094			OutputStrings:    []string{output},
1095			InputStrings:     inputs,
1096			OrderOnlyStrings: orderOnlyDeps,
1097		}
1098	}
1099	m := func(bs ...*buildDef) *moduleInfo {
1100		return &moduleInfo{actionDefs: localBuildActions{buildDefs: bs}}
1101	}
1102	type testcase struct {
1103		modules        []*moduleInfo
1104		expectedPhonys []*buildDef
1105		conversions    map[string][]string
1106	}
1107	fnvHash := func(s string) string {
1108		hash := fnv.New64a()
1109		hash.Write([]byte(s))
1110		return strconv.FormatUint(hash.Sum64(), 16)
1111	}
1112	testCases := []testcase{{
1113		modules: []*moduleInfo{
1114			m(b("A", nil, []string{"d"})),
1115			m(b("B", nil, []string{"d"})),
1116		},
1117		expectedPhonys: []*buildDef{
1118			b("dedup-"+fnvHash("d"), []string{"d"}, nil),
1119		},
1120		conversions: map[string][]string{
1121			"A": []string{"dedup-" + fnvHash("d")},
1122			"B": []string{"dedup-" + fnvHash("d")},
1123		},
1124	}, {
1125		modules: []*moduleInfo{
1126			m(b("A", nil, []string{"a"})),
1127			m(b("B", nil, []string{"b"})),
1128		},
1129	}, {
1130		modules: []*moduleInfo{
1131			m(b("A", nil, []string{"a"})),
1132			m(b("B", nil, []string{"b"})),
1133			m(b("C", nil, []string{"a"})),
1134		},
1135		expectedPhonys: []*buildDef{b("dedup-"+fnvHash("a"), []string{"a"}, nil)},
1136		conversions: map[string][]string{
1137			"A": []string{"dedup-" + fnvHash("a")},
1138			"B": []string{"b"},
1139			"C": []string{"dedup-" + fnvHash("a")},
1140		},
1141	}, {
1142		modules: []*moduleInfo{
1143			m(b("A", nil, []string{"a", "b"}),
1144				b("B", nil, []string{"a", "b"})),
1145			m(b("C", nil, []string{"a", "c"}),
1146				b("D", nil, []string{"a", "c"})),
1147		},
1148		expectedPhonys: []*buildDef{
1149			b("dedup-"+fnvHash("ab"), []string{"a", "b"}, nil),
1150			b("dedup-"+fnvHash("ac"), []string{"a", "c"}, nil)},
1151		conversions: map[string][]string{
1152			"A": []string{"dedup-" + fnvHash("ab")},
1153			"B": []string{"dedup-" + fnvHash("ab")},
1154			"C": []string{"dedup-" + fnvHash("ac")},
1155			"D": []string{"dedup-" + fnvHash("ac")},
1156		},
1157	}}
1158	for index, tc := range testCases {
1159		t.Run(fmt.Sprintf("TestCase-%d", index), func(t *testing.T) {
1160			ctx := NewContext()
1161			actualPhonys := ctx.deduplicateOrderOnlyDeps(tc.modules)
1162			if len(actualPhonys.variables) != 0 {
1163				t.Errorf("No variables expected but found %v", actualPhonys.variables)
1164			}
1165			if len(actualPhonys.rules) != 0 {
1166				t.Errorf("No rules expected but found %v", actualPhonys.rules)
1167			}
1168			if e, a := len(tc.expectedPhonys), len(actualPhonys.buildDefs); e != a {
1169				t.Errorf("Expected %d build statements but got %d", e, a)
1170			}
1171			for i := 0; i < len(tc.expectedPhonys); i++ {
1172				a := actualPhonys.buildDefs[i]
1173				e := tc.expectedPhonys[i]
1174				if !reflect.DeepEqual(e.Outputs, a.Outputs) {
1175					t.Errorf("phonys expected %v but actualPhonys %v", e.Outputs, a.Outputs)
1176				}
1177				if !reflect.DeepEqual(e.Inputs, a.Inputs) {
1178					t.Errorf("phonys expected %v but actualPhonys %v", e.Inputs, a.Inputs)
1179				}
1180			}
1181			find := func(k string) *buildDef {
1182				for _, m := range tc.modules {
1183					for _, b := range m.actionDefs.buildDefs {
1184						if reflect.DeepEqual(b.OutputStrings, []string{k}) {
1185							return b
1186						}
1187					}
1188				}
1189				return nil
1190			}
1191			for k, conversion := range tc.conversions {
1192				actual := find(k)
1193				if actual == nil {
1194					t.Errorf("Couldn't find %s", k)
1195				}
1196				if !reflect.DeepEqual(actual.OrderOnlyStrings, conversion) {
1197					t.Errorf("expected %s.OrderOnly = %v but got %v", k, conversion, actual.OrderOnly)
1198				}
1199			}
1200		})
1201	}
1202}
1203
1204func TestSourceRootDirAllowed(t *testing.T) {
1205	type pathCase struct {
1206		path           string
1207		decidingPrefix string
1208		allowed        bool
1209	}
1210	testcases := []struct {
1211		desc      string
1212		rootDirs  []string
1213		pathCases []pathCase
1214	}{
1215		{
1216			desc: "simple case",
1217			rootDirs: []string{
1218				"a",
1219				"b/c/d",
1220				"-c",
1221				"-d/c/a",
1222				"c/some_single_file",
1223			},
1224			pathCases: []pathCase{
1225				{
1226					path:           "a",
1227					decidingPrefix: "a",
1228					allowed:        true,
1229				},
1230				{
1231					path:           "a/b/c",
1232					decidingPrefix: "a",
1233					allowed:        true,
1234				},
1235				{
1236					path:           "b",
1237					decidingPrefix: "",
1238					allowed:        true,
1239				},
1240				{
1241					path:           "b/c/d/a",
1242					decidingPrefix: "b/c/d",
1243					allowed:        true,
1244				},
1245				{
1246					path:           "c",
1247					decidingPrefix: "c",
1248					allowed:        false,
1249				},
1250				{
1251					path:           "c/a/b",
1252					decidingPrefix: "c",
1253					allowed:        false,
1254				},
1255				{
1256					path:           "c/some_single_file",
1257					decidingPrefix: "c/some_single_file",
1258					allowed:        true,
1259				},
1260				{
1261					path:           "d/c/a/abc",
1262					decidingPrefix: "d/c/a",
1263					allowed:        false,
1264				},
1265			},
1266		},
1267		{
1268			desc: "root directory order matters",
1269			rootDirs: []string{
1270				"-a",
1271				"a/c/some_allowed_file",
1272				"a/b/d/some_allowed_file",
1273				"a/b",
1274				"a/c",
1275				"-a/b/d",
1276			},
1277			pathCases: []pathCase{
1278				{
1279					path:           "a",
1280					decidingPrefix: "a",
1281					allowed:        false,
1282				},
1283				{
1284					path:           "a/some_disallowed_file",
1285					decidingPrefix: "a",
1286					allowed:        false,
1287				},
1288				{
1289					path:           "a/c/some_allowed_file",
1290					decidingPrefix: "a/c/some_allowed_file",
1291					allowed:        true,
1292				},
1293				{
1294					path:           "a/b/d/some_allowed_file",
1295					decidingPrefix: "a/b/d/some_allowed_file",
1296					allowed:        true,
1297				},
1298				{
1299					path:           "a/b/c",
1300					decidingPrefix: "a/b",
1301					allowed:        true,
1302				},
1303				{
1304					path:           "a/b/c/some_allowed_file",
1305					decidingPrefix: "a/b",
1306					allowed:        true,
1307				},
1308				{
1309					path:           "a/b/d",
1310					decidingPrefix: "a/b/d",
1311					allowed:        false,
1312				},
1313			},
1314		},
1315	}
1316	for _, tc := range testcases {
1317		dirs := SourceRootDirs{}
1318		dirs.Add(tc.rootDirs...)
1319		for _, pc := range tc.pathCases {
1320			t.Run(fmt.Sprintf("%s: %s", tc.desc, pc.path), func(t *testing.T) {
1321				allowed, decidingPrefix := dirs.SourceRootDirAllowed(pc.path)
1322				if allowed != pc.allowed {
1323					if pc.allowed {
1324						t.Errorf("expected path %q to be allowed, but was not; root allowlist: %q", pc.path, tc.rootDirs)
1325					} else {
1326						t.Errorf("path %q was allowed unexpectedly; root allowlist: %q", pc.path, tc.rootDirs)
1327					}
1328				}
1329				if decidingPrefix != pc.decidingPrefix {
1330					t.Errorf("expected decidingPrefix to be %q, but got %q", pc.decidingPrefix, decidingPrefix)
1331				}
1332			})
1333		}
1334	}
1335}
1336
1337func TestSourceRootDirs(t *testing.T) {
1338	root_foo_bp := `
1339	foo_module {
1340		name: "foo",
1341		deps: ["foo_dir1", "foo_dir_ignored_special_case"],
1342	}
1343	`
1344	dir1_foo_bp := `
1345	foo_module {
1346		name: "foo_dir1",
1347		deps: ["foo_dir_ignored"],
1348	}
1349	`
1350	dir_ignored_foo_bp := `
1351	foo_module {
1352		name: "foo_dir_ignored",
1353	}
1354	`
1355	dir_ignored_special_case_foo_bp := `
1356	foo_module {
1357		name: "foo_dir_ignored_special_case",
1358	}
1359	`
1360	mockFs := map[string][]byte{
1361		"Android.bp":                          []byte(root_foo_bp),
1362		"dir1/Android.bp":                     []byte(dir1_foo_bp),
1363		"dir_ignored/Android.bp":              []byte(dir_ignored_foo_bp),
1364		"dir_ignored/special_case/Android.bp": []byte(dir_ignored_special_case_foo_bp),
1365	}
1366	fileList := []string{}
1367	for f := range mockFs {
1368		fileList = append(fileList, f)
1369	}
1370	testCases := []struct {
1371		sourceRootDirs       []string
1372		expectedModuleDefs   []string
1373		unexpectedModuleDefs []string
1374		expectedErrs         []string
1375	}{
1376		{
1377			sourceRootDirs: []string{},
1378			expectedModuleDefs: []string{
1379				"foo",
1380				"foo_dir1",
1381				"foo_dir_ignored",
1382				"foo_dir_ignored_special_case",
1383			},
1384		},
1385		{
1386			sourceRootDirs: []string{"-", ""},
1387			unexpectedModuleDefs: []string{
1388				"foo",
1389				"foo_dir1",
1390				"foo_dir_ignored",
1391				"foo_dir_ignored_special_case",
1392			},
1393		},
1394		{
1395			sourceRootDirs: []string{"-"},
1396			unexpectedModuleDefs: []string{
1397				"foo",
1398				"foo_dir1",
1399				"foo_dir_ignored",
1400				"foo_dir_ignored_special_case",
1401			},
1402		},
1403		{
1404			sourceRootDirs: []string{"dir1"},
1405			expectedModuleDefs: []string{
1406				"foo",
1407				"foo_dir1",
1408				"foo_dir_ignored",
1409				"foo_dir_ignored_special_case",
1410			},
1411		},
1412		{
1413			sourceRootDirs: []string{"-dir1"},
1414			expectedModuleDefs: []string{
1415				"foo",
1416				"foo_dir_ignored",
1417				"foo_dir_ignored_special_case",
1418			},
1419			unexpectedModuleDefs: []string{
1420				"foo_dir1",
1421			},
1422			expectedErrs: []string{
1423				`Android.bp:2:2: module "foo" depends on skipped module "foo_dir1"; "foo_dir1" was defined in files(s) [dir1/Android.bp], but was skipped for reason(s) ["dir1/Android.bp" is a descendant of "dir1", and that path prefix was not included in PRODUCT_SOURCE_ROOT_DIRS]`,
1424			},
1425		},
1426		{
1427			sourceRootDirs: []string{"-", "dir1"},
1428			expectedModuleDefs: []string{
1429				"foo_dir1",
1430			},
1431			unexpectedModuleDefs: []string{
1432				"foo",
1433				"foo_dir_ignored",
1434				"foo_dir_ignored_special_case",
1435			},
1436			expectedErrs: []string{
1437				`dir1/Android.bp:2:2: module "foo_dir1" depends on skipped module "foo_dir_ignored"; "foo_dir_ignored" was defined in files(s) [dir_ignored/Android.bp], but was skipped for reason(s) ["dir_ignored/Android.bp" is a descendant of "", and that path prefix was not included in PRODUCT_SOURCE_ROOT_DIRS]`,
1438			},
1439		},
1440		{
1441			sourceRootDirs: []string{"-", "dir1", "dir_ignored/special_case/Android.bp"},
1442			expectedModuleDefs: []string{
1443				"foo_dir1",
1444				"foo_dir_ignored_special_case",
1445			},
1446			unexpectedModuleDefs: []string{
1447				"foo",
1448				"foo_dir_ignored",
1449			},
1450			expectedErrs: []string{
1451				"dir1/Android.bp:2:2: module \"foo_dir1\" depends on skipped module \"foo_dir_ignored\"; \"foo_dir_ignored\" was defined in files(s) [dir_ignored/Android.bp], but was skipped for reason(s) [\"dir_ignored/Android.bp\" is a descendant of \"\", and that path prefix was not included in PRODUCT_SOURCE_ROOT_DIRS]",
1452			},
1453		},
1454	}
1455	for _, tc := range testCases {
1456		t.Run(fmt.Sprintf(`source root dirs are %q`, tc.sourceRootDirs), func(t *testing.T) {
1457			ctx := NewContext()
1458			ctx.MockFileSystem(mockFs)
1459			ctx.RegisterModuleType("foo_module", newFooModule)
1460			ctx.RegisterBottomUpMutator("deps", depsMutator)
1461			ctx.AddSourceRootDirs(tc.sourceRootDirs...)
1462			ctx.ParseFileList(".", fileList, nil)
1463			_, actualErrs := ctx.ResolveDependencies(nil)
1464
1465			stringErrs := []string(nil)
1466			for _, err := range actualErrs {
1467				stringErrs = append(stringErrs, err.Error())
1468			}
1469			if !reflect.DeepEqual(tc.expectedErrs, stringErrs) {
1470				t.Errorf("expected to find errors %v; got %v", tc.expectedErrs, stringErrs)
1471			}
1472			for _, modName := range tc.expectedModuleDefs {
1473				allMods := ctx.moduleGroupFromName(modName, nil)
1474				if allMods == nil || len(allMods.modules) != 1 {
1475					mods := modulesOrAliases{}
1476					if allMods != nil {
1477						mods = allMods.modules
1478					}
1479					t.Errorf("expected to find one definition for module %q, but got %v", modName, mods)
1480				}
1481			}
1482
1483			for _, modName := range tc.unexpectedModuleDefs {
1484				allMods := ctx.moduleGroupFromName(modName, nil)
1485				if allMods != nil {
1486					t.Errorf("expected to find no definitions for module %q, but got %v", modName, allMods.modules)
1487				}
1488			}
1489		})
1490	}
1491}
1492