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[0]
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[0]
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[0]
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[0].logicModule.(*fooModule)
436	b := ctx.moduleGroupFromName("B", nil).modules[0].logicModule.(*barModule)
437	c := ctx.moduleGroupFromName("C", nil).modules[0].logicModule.(*barModule)
438	d := ctx.moduleGroupFromName("D", nil).modules[0].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