1// Copyright 2016 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 bootstrap
16
17import (
18	"bytes"
19	"fmt"
20	"hash/fnv"
21	"io"
22	"path/filepath"
23	"strconv"
24	"strings"
25
26	"github.com/google/blueprint"
27	"github.com/google/blueprint/pathtools"
28)
29
30// This file supports globbing source files in Blueprints files.
31//
32// The build.ninja file needs to be regenerated any time a file matching the glob is added
33// or removed.  The naive solution is to have the build.ninja file depend on all the
34// traversed directories, but this will cause the regeneration step to run every time a
35// non-matching file is added to a traversed directory, including backup files created by
36// editors.
37//
38// The solution implemented here optimizes out regenerations when the directory modifications
39// don't match the glob by having the build.ninja file depend on an intermedate file that
40// is only updated when a file matching the glob is added or removed.  The intermediate file
41// depends on the traversed directories via a depfile.  The depfile is used to avoid build
42// errors if a directory is deleted - a direct dependency on the deleted directory would result
43// in a build failure with a "missing and no known rule to make it" error.
44
45var (
46	globCmd = filepath.Join(miniBootstrapDir, "bpglob")
47
48	// globRule rule traverses directories to produce a list of files that match $glob
49	// and writes it to $out if it has changed, and writes the directories to $out.d
50	GlobRule = pctx.StaticRule("GlobRule",
51		blueprint.RuleParams{
52			Command: fmt.Sprintf(`%s -o $out -v %d $args`,
53				globCmd, pathtools.BPGlobArgumentVersion),
54			CommandDeps: []string{globCmd},
55			Description: "glob",
56
57			Restat:  true,
58			Deps:    blueprint.DepsGCC,
59			Depfile: "$out.d",
60		},
61		"args")
62)
63
64// GlobFileContext is the subset of ModuleContext and SingletonContext needed by GlobFile
65type GlobFileContext interface {
66	Config() interface{}
67	Build(pctx blueprint.PackageContext, params blueprint.BuildParams)
68}
69
70// GlobFile creates a rule to write to fileListFile a list of the files that match the specified
71// pattern but do not match any of the patterns specified in excludes.  The file will include
72// appropriate dependencies to regenerate the file if and only if the list of matching files has
73// changed.
74func GlobFile(ctx GlobFileContext, pattern string, excludes []string, fileListFile string) {
75	args := `-p "` + pattern + `"`
76	if len(excludes) > 0 {
77		args += " " + joinWithPrefixAndQuote(excludes, "-e ")
78	}
79	ctx.Build(pctx, blueprint.BuildParams{
80		Rule:    GlobRule,
81		Outputs: []string{fileListFile},
82		Args: map[string]string{
83			"args": args,
84		},
85		Description: "glob " + pattern,
86	})
87}
88
89// multipleGlobFilesRule creates a rule to write to fileListFile a list of the files that match the specified
90// pattern but do not match any of the patterns specified in excludes.  The file will include
91// appropriate dependencies to regenerate the file if and only if the list of matching files has
92// changed.
93func multipleGlobFilesRule(ctx GlobFileContext, fileListFile string, shard int, globs pathtools.MultipleGlobResults) {
94	args := strings.Builder{}
95
96	for i, glob := range globs {
97		if i != 0 {
98			args.WriteString(" ")
99		}
100		args.WriteString(`-p "`)
101		args.WriteString(glob.Pattern)
102		args.WriteString(`"`)
103		for _, exclude := range glob.Excludes {
104			args.WriteString(` -e "`)
105			args.WriteString(exclude)
106			args.WriteString(`"`)
107		}
108	}
109
110	ctx.Build(pctx, blueprint.BuildParams{
111		Rule:    GlobRule,
112		Outputs: []string{fileListFile},
113		Args: map[string]string{
114			"args": args.String(),
115		},
116		Description: fmt.Sprintf("regenerate globs shard %d of %d", shard, numGlobBuckets),
117	})
118}
119
120func joinWithPrefixAndQuote(strs []string, prefix string) string {
121	if len(strs) == 0 {
122		return ""
123	}
124
125	if len(strs) == 1 {
126		return prefix + `"` + strs[0] + `"`
127	}
128
129	n := len(" ") * (len(strs) - 1)
130	for _, s := range strs {
131		n += len(prefix) + len(s) + len(`""`)
132	}
133
134	ret := make([]byte, 0, n)
135	for i, s := range strs {
136		if i != 0 {
137			ret = append(ret, ' ')
138		}
139		ret = append(ret, prefix...)
140		ret = append(ret, '"')
141		ret = append(ret, s...)
142		ret = append(ret, '"')
143	}
144	return string(ret)
145}
146
147// globSingleton collects any glob patterns that were seen by Context and writes out rules to
148// re-evaluate them whenever the contents of the searched directories change, and retrigger the
149// primary builder if the results change.
150type globSingleton struct {
151	config     *Config
152	globLister func() pathtools.MultipleGlobResults
153	writeRule  bool
154}
155
156func globSingletonFactory(config *Config, ctx *blueprint.Context) func() blueprint.Singleton {
157	return func() blueprint.Singleton {
158		return &globSingleton{
159			config:     config,
160			globLister: ctx.Globs,
161		}
162	}
163}
164
165func (s *globSingleton) GenerateBuildActions(ctx blueprint.SingletonContext) {
166	// Sort the list of globs into buckets.  A hash function is used instead of sharding so that
167	// adding a new glob doesn't force rerunning all the buckets by shifting them all by 1.
168	globBuckets := make([]pathtools.MultipleGlobResults, numGlobBuckets)
169	for _, g := range s.globLister() {
170		bucket := globToBucket(g)
171		globBuckets[bucket] = append(globBuckets[bucket], g)
172	}
173
174	// The directory for the intermediates needs to be different for bootstrap and the primary
175	// builder.
176	globsDir := globsDir(ctx.Config().(BootstrapConfig), s.config.stage)
177
178	for i, globs := range globBuckets {
179		fileListFile := filepath.Join(globsDir, strconv.Itoa(i))
180
181		if s.writeRule {
182			// Called from generateGlobNinjaFile.  Write out the file list to disk, and add a ninja
183			// rule to run bpglob if any of the dependencies (usually directories that contain
184			// globbed files) have changed.  The file list produced by bpglob should match exactly
185			// with the file written here so that restat can prevent rerunning the primary builder.
186			//
187			// We need to write the file list here so that it has an older modified date
188			// than the build.ninja (otherwise we'd run the primary builder twice on
189			// every new glob)
190			//
191			// We don't need to write the depfile because we're guaranteed that ninja
192			// will run the command at least once (to record it into the ninja_log), so
193			// the depfile will be loaded from that execution.
194			err := pathtools.WriteFileIfChanged(absolutePath(fileListFile), globs.FileList(), 0666)
195			if err != nil {
196				panic(fmt.Errorf("error writing %s: %s", fileListFile, err))
197			}
198
199			// Write out the ninja rule to run bpglob.
200			multipleGlobFilesRule(ctx, fileListFile, i, globs)
201		} else {
202			// Called from the main Context, make build.ninja depend on the fileListFile.
203			ctx.AddNinjaFileDeps(fileListFile)
204		}
205	}
206}
207
208func generateGlobNinjaFile(bootstrapConfig *Config, config interface{},
209	globLister func() pathtools.MultipleGlobResults) ([]byte, []error) {
210
211	ctx := blueprint.NewContext()
212	ctx.RegisterSingletonType("glob", func() blueprint.Singleton {
213		return &globSingleton{
214			config:     bootstrapConfig,
215			globLister: globLister,
216			writeRule:  true,
217		}
218	})
219
220	extraDeps, errs := ctx.ResolveDependencies(config)
221	if len(extraDeps) > 0 {
222		return nil, []error{fmt.Errorf("shouldn't have extra deps")}
223	}
224	if len(errs) > 0 {
225		return nil, errs
226	}
227
228	extraDeps, errs = ctx.PrepareBuildActions(config)
229	if len(extraDeps) > 0 {
230		return nil, []error{fmt.Errorf("shouldn't have extra deps")}
231	}
232	if len(errs) > 0 {
233		return nil, errs
234	}
235
236	buf := bytes.NewBuffer(nil)
237	err := ctx.WriteBuildFile(buf)
238	if err != nil {
239		return nil, []error{err}
240	}
241
242	return buf.Bytes(), nil
243}
244
245// globsDir returns a different directory to store glob intermediates for the bootstrap and
246// primary builder executions.
247func globsDir(config BootstrapConfig, stage Stage) string {
248	buildDir := config.BuildDir()
249	if stage == StageMain {
250		return filepath.Join(buildDir, mainSubDir, "globs")
251	} else {
252		return filepath.Join(buildDir, bootstrapSubDir, "globs")
253	}
254}
255
256// GlobFileListFiles returns the list of sharded glob file list files for the main stage.
257func GlobFileListFiles(config BootstrapConfig) []string {
258	globsDir := globsDir(config, StageMain)
259	var fileListFiles []string
260	for i := 0; i < numGlobBuckets; i++ {
261		fileListFiles = append(fileListFiles, filepath.Join(globsDir, strconv.Itoa(i)))
262	}
263	return fileListFiles
264}
265
266const numGlobBuckets = 1024
267
268// globToBucket converts a pathtools.GlobResult into a hashed bucket number in the range
269// [0, numGlobBuckets).
270func globToBucket(g pathtools.GlobResult) int {
271	hash := fnv.New32a()
272	io.WriteString(hash, g.Pattern)
273	for _, e := range g.Excludes {
274		io.WriteString(hash, e)
275	}
276	return int(hash.Sum32() % numGlobBuckets)
277}
278