1// Copyright 2015 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 kati
16
17import (
18	"bytes"
19	"fmt"
20	"os"
21	"path/filepath"
22	"regexp"
23	"runtime"
24	"sort"
25	"strings"
26	"time"
27
28	"github.com/golang/glog"
29)
30
31type nodeState int
32
33const (
34	nodeInit    nodeState = iota // not visited
35	nodeVisit                    // visited
36	nodeFile                     // visited & file exists
37	nodeAlias                    // visited & alias for other target
38	nodeMissing                  // visited & no target for this output
39	nodeBuild                    // visited & build emitted
40)
41
42func (s nodeState) String() string {
43	switch s {
44	case nodeInit:
45		return "node-init"
46	case nodeVisit:
47		return "node-visit"
48	case nodeFile:
49		return "node-file"
50	case nodeAlias:
51		return "node-alias"
52	case nodeMissing:
53		return "node-missing"
54	case nodeBuild:
55		return "node-build"
56	default:
57		return fmt.Sprintf("node-unknown[%d]", int(s))
58	}
59}
60
61// NinjaGenerator generates ninja build files from DepGraph.
62type NinjaGenerator struct {
63	// Args is original arguments to generate the ninja file.
64	Args []string
65	// Suffix is suffix for generated files.
66	Suffix string
67	// GomaDir is goma directory.  If empty, goma will not be used.
68	GomaDir string
69	// DetectAndroidEcho detects echo as description.
70	DetectAndroidEcho bool
71
72	f       *os.File
73	nodes   []*DepNode
74	exports map[string]bool
75
76	ctx *execContext
77
78	ruleID     int
79	done       map[string]nodeState
80}
81
82func (n *NinjaGenerator) init(g *DepGraph) {
83	g.resolveVPATH()
84	n.nodes = g.nodes
85	n.exports = g.exports
86	n.ctx = newExecContext(g.vars, g.vpaths, true)
87	n.done = make(map[string]nodeState)
88}
89
90func getDepfileImpl(ss string) (string, error) {
91	tss := ss + " "
92	if (!strings.Contains(tss, " -MD ") && !strings.Contains(tss, " -MMD ")) || !strings.Contains(tss, " -c ") {
93		return "", nil
94	}
95
96	mfIndex := strings.Index(ss, " -MF ")
97	if mfIndex >= 0 {
98		mf := trimLeftSpace(ss[mfIndex+4:])
99		if strings.Index(mf, " -MF ") >= 0 {
100			return "", fmt.Errorf("Multiple output file candidates in %s", ss)
101		}
102		mfEndIndex := strings.IndexAny(mf, " \t\n")
103		if mfEndIndex >= 0 {
104			mf = mf[:mfEndIndex]
105		}
106
107		return mf, nil
108	}
109
110	outIndex := strings.Index(ss, " -o ")
111	if outIndex < 0 {
112		return "", fmt.Errorf("Cannot find the depfile in %s", ss)
113	}
114	out := trimLeftSpace(ss[outIndex+4:])
115	if strings.Index(out, " -o ") >= 0 {
116		return "", fmt.Errorf("Multiple output file candidates in %s", ss)
117	}
118	outEndIndex := strings.IndexAny(out, " \t\n")
119	if outEndIndex >= 0 {
120		out = out[:outEndIndex]
121	}
122	return stripExt(out) + ".d", nil
123}
124
125// getDepfile gets depfile from cmdline, and returns cmdline and depfile.
126func getDepfile(cmdline string) (string, string, error) {
127	// A hack for Android - llvm-rs-cc seems not to emit a dep file.
128	if strings.Contains(cmdline, "bin/llvm-rs-cc ") {
129		return cmdline, "", nil
130	}
131
132	depfile, err := getDepfileImpl(cmdline)
133	if depfile == "" || err != nil {
134		return cmdline, depfile, err
135	}
136
137	// A hack for Makefiles generated by automake.
138	mvCmd := "(mv -f " + depfile + " "
139	if i := strings.LastIndex(cmdline, mvCmd); i >= 0 {
140		rest := cmdline[i+len(mvCmd):]
141		ei := strings.IndexByte(rest, ')')
142		if ei < 0 {
143			return cmdline, "", fmt.Errorf("unbalanced parenthes? %s", cmdline)
144		}
145		cmdline = cmdline[:i] + "(cp -f " + depfile + " " + rest
146		return cmdline, depfile, nil
147	}
148
149	// A hack for Android to get .P files instead of .d.
150	p := stripExt(depfile) + ".P"
151	if strings.Contains(cmdline, p) {
152		rmfCmd := "; rm -f " + depfile
153		ncmdline := strings.Replace(cmdline, rmfCmd, "", 1)
154		if ncmdline == cmdline {
155			return cmdline, "", fmt.Errorf("cannot find removal of .d file: %s", cmdline)
156		}
157		return ncmdline, p, nil
158	}
159
160	// A hack for Android. For .s files, GCC does not use
161	// C preprocessor, so it ignores -MF flag.
162	as := "/" + stripExt(filepath.Base(depfile)) + ".s"
163	if strings.Contains(cmdline, as) {
164		return cmdline, "", nil
165	}
166
167	cmdline += fmt.Sprintf(" && cp %s %s.tmp", depfile, depfile)
168	depfile += ".tmp"
169	return cmdline, depfile, nil
170}
171
172func trimTailingSlash(s string) string {
173	if s == "" {
174		return s
175	}
176	if s[len(s)-1] != '\\' {
177		return s
178	}
179	// drop single trailing slash - multiline_arg.mk
180	if len(s) > 2 && s[len(s)-2] != '\\' {
181		return s[:len(s)-1]
182	}
183	// preserve two trailing slash - escaped_backslash.mk
184	return s
185}
186
187func stripShellComment(s string) string {
188	if strings.IndexByte(s, '#') < 0 {
189		// Fast path.
190		return s
191	}
192	// set space as an initial value so the leading comment will be
193	// stripped out.
194	lastch := rune(' ')
195	var escape bool
196	var quote rune
197	var skip rune
198	var cmdsubst []rune
199	var buf bytes.Buffer
200Loop:
201	for _, c := range s {
202		if skip != 0 {
203			if skip != c {
204				continue Loop
205			}
206			if len(cmdsubst) > 0 && cmdsubst[len(cmdsubst)-1] == skip {
207				cmdsubst = cmdsubst[:len(cmdsubst)-1]
208			}
209			skip = 0
210		}
211		if quote != 0 {
212			if quote == c && (quote == '\'' || !escape) {
213				quote = 0
214			}
215		} else if !escape {
216			if c == '#' && isWhitespace(lastch) {
217				if len(cmdsubst) == 0 {
218					// strip comment until the end of line.
219					skip = '\n'
220					continue Loop
221				}
222				// strip comment until the end of command subst.
223				skip = cmdsubst[len(cmdsubst)-1]
224				continue Loop
225			} else if c == '\'' || c == '"' {
226				quote = c
227			} else if lastch == '$' && c == '(' {
228				cmdsubst = append(cmdsubst, ')')
229			} else if c == '`' {
230				cmdsubst = append(cmdsubst, '`')
231			}
232		}
233		if escape {
234			escape = false
235		} else if c == '\\' {
236			escape = true
237		} else {
238			escape = false
239		}
240		lastch = c
241		buf.WriteRune(c)
242	}
243	return buf.String()
244}
245
246var ccRE = regexp.MustCompile(`^prebuilts/(gcc|clang)/.*(gcc|g\+\+|clang|clang\+\+) .* ?-c `)
247
248func gomaCmdForAndroidCompileCmd(cmd string) (string, bool) {
249	i := strings.Index(cmd, " ")
250	if i < 0 {
251		return cmd, false
252	}
253	driver := cmd[:i]
254	if strings.HasSuffix(driver, "ccache") {
255		return gomaCmdForAndroidCompileCmd(cmd[i+1:])
256	}
257	return cmd, ccRE.MatchString(cmd)
258}
259
260func descriptionFromCmd(cmd string) (string, bool) {
261	if !strings.HasPrefix(cmd, "echo") || !isWhitespace(rune(cmd[4])) {
262		return "", false
263	}
264	echoarg := cmd[5:]
265
266	// strip outer quotes, and fail if it is not a single echo command.
267	var buf bytes.Buffer
268	var escape bool
269	var quote rune
270	for _, c := range echoarg {
271		if escape {
272			escape = false
273			buf.WriteRune(c)
274			continue
275		}
276		if c == '\\' {
277			escape = true
278			buf.WriteRune(c)
279			continue
280		}
281		if quote != 0 {
282			if c == quote {
283				quote = 0
284				continue
285			}
286			buf.WriteRune(c)
287			continue
288		}
289		switch c {
290		case '\'', '"', '`':
291			quote = c
292		case '<', '>', '&', '|', ';':
293			return "", false
294		default:
295			buf.WriteRune(c)
296		}
297	}
298	return buf.String(), true
299}
300
301func (n *NinjaGenerator) genShellScript(runners []runner) (cmd string, desc string, useLocalPool bool) {
302	const defaultDesc = "build $out"
303	var useGomacc bool
304	var buf bytes.Buffer
305	for i, r := range runners {
306		if i > 0 {
307			if runners[i-1].ignoreError {
308				buf.WriteString(" ; ")
309			} else {
310				buf.WriteString(" && ")
311			}
312		}
313		cmd := trimTailingSlash(r.cmd)
314		cmd = stripShellComment(cmd)
315		cmd = trimLeftSpace(cmd)
316		cmd = strings.Replace(cmd, "\\\n\t", "", -1)
317		cmd = strings.Replace(cmd, "\\\n", "", -1)
318		cmd = strings.TrimRight(cmd, " \t\n;")
319		cmd = escapeNinja(cmd)
320		if cmd == "" {
321			cmd = "true"
322		}
323		glog.V(2).Infof("cmd %q=>%q", r.cmd, cmd)
324		if n.GomaDir != "" {
325			rcmd, ok := gomaCmdForAndroidCompileCmd(cmd)
326			if ok {
327				cmd = fmt.Sprintf("%s/gomacc %s", n.GomaDir, rcmd)
328				useGomacc = true
329			}
330		}
331		if n.DetectAndroidEcho && desc == "" {
332			d, ok := descriptionFromCmd(cmd)
333			if ok {
334				desc = d
335				cmd = "true"
336			}
337		}
338		needsSubShell := i > 0 || len(runners) > 1
339		if cmd[0] == '(' {
340			needsSubShell = false
341		}
342
343		if needsSubShell {
344			buf.WriteByte('(')
345		}
346		buf.WriteString(cmd)
347		if i == len(runners)-1 && r.ignoreError {
348			buf.WriteString(" ; true")
349		}
350		if needsSubShell {
351			buf.WriteByte(')')
352		}
353	}
354	if desc == "" {
355		desc = defaultDesc
356	}
357	return buf.String(), desc, n.GomaDir != "" && !useGomacc
358}
359
360func (n *NinjaGenerator) genRuleName() string {
361	ruleName := fmt.Sprintf("rule%d", n.ruleID)
362	n.ruleID++
363	return ruleName
364}
365
366func (n *NinjaGenerator) emitBuild(output, rule, inputs, orderOnlys string) {
367	fmt.Fprintf(n.f, "build %s: %s", escapeBuildTarget(output), rule)
368	if inputs != "" {
369		fmt.Fprintf(n.f, " %s", inputs)
370	}
371	if orderOnlys != "" {
372		fmt.Fprintf(n.f, " || %s", orderOnlys)
373	}
374}
375
376func escapeBuildTarget(s string) string {
377	i := strings.IndexAny(s, "$: \\")
378	if i < 0 {
379		return s
380	}
381	// unescapeInput only "\ ", "\=" unescape as " ", "=".
382	// TODO(ukai): which char should unescape, which should not here?
383	var esc rune
384	var buf bytes.Buffer
385	for _, c := range s {
386		switch c {
387		case '\\':
388			esc = c
389			continue
390		case '$', ':', ' ':
391			esc = 0
392			buf.WriteByte('$')
393		}
394		if esc != 0 {
395			buf.WriteRune(esc)
396			esc = 0
397		}
398		buf.WriteRune(c)
399	}
400	if esc != 0 {
401		buf.WriteRune(esc)
402	}
403	return buf.String()
404}
405
406func (n *NinjaGenerator) dependency(node *DepNode) (string, string) {
407	var deps []string
408	seen := make(map[string]bool)
409	for _, d := range node.Deps {
410		t := escapeBuildTarget(d.Output)
411		if seen[t] {
412			continue
413		}
414		deps = append(deps, t)
415		seen[t] = true
416	}
417	var orderOnlys []string
418	for _, d := range node.OrderOnlys {
419		t := escapeBuildTarget(d.Output)
420		if seen[t] {
421			continue
422		}
423		orderOnlys = append(orderOnlys, t)
424		seen[t] = true
425	}
426	return strings.Join(deps, " "), strings.Join(orderOnlys, " ")
427}
428
429func escapeNinja(s string) string {
430	return strings.Replace(s, "$", "$$", -1)
431}
432
433func escapeShell(s string) string {
434	i := strings.IndexAny(s, "$`!\\\"")
435	if i < 0 {
436		return s
437	}
438	var buf bytes.Buffer
439	var lastDollar bool
440	for _, c := range s {
441		switch c {
442		case '$':
443			if lastDollar {
444				buf.WriteRune(c)
445				lastDollar = false
446				continue
447			}
448			buf.WriteString(`\$`)
449			lastDollar = true
450			continue
451		case '`', '"', '!', '\\':
452			buf.WriteByte('\\')
453		}
454		buf.WriteRune(c)
455		lastDollar = false
456	}
457	return buf.String()
458}
459
460func (n *NinjaGenerator) ninjaVars(s string, nv [][]string, esc func(string) string) string {
461	for _, v := range nv {
462		k, v := v[0], v[1]
463		if v == "" {
464			continue
465		}
466		if strings.Contains(v, "/./") || strings.Contains(v, "/../") || strings.Contains(v, "$") {
467			// ninja will normalize paths (/./, /../), so keep it as is
468			// ninja will emit quoted string for $
469			continue
470		}
471		if esc != nil {
472			v = esc(v)
473		}
474		s = strings.Replace(s, v, k, -1)
475	}
476	return s
477}
478
479func (n *NinjaGenerator) emitNode(node *DepNode) error {
480	output := node.Output
481	if _, found := n.done[output]; found {
482		return nil
483	}
484	n.done[output] = nodeVisit
485
486	if len(node.Cmds) == 0 && len(node.Deps) == 0 && len(node.OrderOnlys) == 0 && !node.IsPhony {
487		if _, ok := n.ctx.vpaths.exists(output); ok {
488			n.done[output] = nodeFile
489			return nil
490		}
491		o := filepath.Clean(output)
492		if o != output {
493			// if normalized target has been done, it marks as alias.
494			if s, found := n.done[o]; found {
495				glog.V(1).Infof("node %s=%s => %s=alias", o, s, node.Output)
496				n.done[output] = nodeAlias
497				return nil
498			}
499		}
500		if node.Filename == "" {
501			n.done[output] = nodeMissing
502		}
503		return nil
504	}
505
506	runners, _, err := createRunners(n.ctx, node)
507	if err != nil {
508		return err
509	}
510	ruleName := "phony"
511	useLocalPool := false
512	inputs, orderOnlys := n.dependency(node)
513	if len(runners) > 0 {
514		ruleName = n.genRuleName()
515		fmt.Fprintf(n.f, "\n# rule for %q\n", node.Output)
516		fmt.Fprintf(n.f, "rule %s\n", ruleName)
517
518		ss, desc, ulp := n.genShellScript(runners)
519		if ulp {
520			useLocalPool = true
521		}
522		fmt.Fprintf(n.f, " description = %s\n", desc)
523		cmdline, depfile, err := getDepfile(ss)
524		if err != nil {
525			return err
526		}
527		if depfile != "" {
528			fmt.Fprintf(n.f, " depfile = %s\n", depfile)
529			fmt.Fprintf(n.f, " deps = gcc\n")
530		}
531		nv := [][]string{
532			[]string{"${in}", inputs},
533			[]string{"${out}", escapeNinja(output)},
534		}
535		// It seems Linux is OK with ~130kB.
536		// TODO: Find this number automatically.
537		ArgLenLimit := 100 * 1000
538		if len(cmdline) > ArgLenLimit {
539			fmt.Fprintf(n.f, " rspfile = $out.rsp\n")
540			cmdline = n.ninjaVars(cmdline, nv, nil)
541			fmt.Fprintf(n.f, " rspfile_content = %s\n", cmdline)
542			fmt.Fprintf(n.f, " command = %s $out.rsp\n", n.ctx.shell)
543		} else {
544			cmdline = escapeShell(cmdline)
545			cmdline = n.ninjaVars(cmdline, nv, escapeShell)
546			fmt.Fprintf(n.f, " command = %s -c \"%s\"\n", n.ctx.shell, cmdline)
547		}
548	}
549	n.emitBuild(output, ruleName, inputs, orderOnlys)
550	if useLocalPool {
551		fmt.Fprintf(n.f, " pool = local_pool\n")
552	}
553	fmt.Fprintf(n.f, "\n")
554	n.done[output] = nodeBuild
555
556	for _, d := range node.Deps {
557		err := n.emitNode(d)
558		if err != nil {
559			return err
560		}
561		glog.V(1).Infof("node %s dep node %q %s", node.Output, d.Output, n.done[d.Output])
562	}
563	for _, d := range node.OrderOnlys {
564		err := n.emitNode(d)
565		if err != nil {
566			return err
567		}
568		glog.V(1).Infof("node %s order node %q %s", node.Output, d.Output, n.done[d.Output])
569	}
570	return nil
571}
572
573func (n *NinjaGenerator) emitRegenRules() error {
574	if len(n.Args) == 0 {
575		return nil
576	}
577	mkfiles, err := n.ctx.ev.EvaluateVar("MAKEFILE_LIST")
578	if err != nil {
579		return err
580	}
581	fmt.Fprintf(n.f, `
582rule regen_ninja
583 description = Regenerate ninja files due to dependency
584 generator=1
585 command=%s
586`, strings.Join(n.Args, " "))
587	fmt.Fprintf(n.f, "build %s: regen_ninja %s", n.ninjaName(), mkfiles)
588	// TODO: Add dependencies to directories read by $(wildcard) or
589	// $(shell find).
590	if len(usedEnvs) > 0 {
591		fmt.Fprintf(n.f, " %s", n.envlistName())
592	}
593	fmt.Fprintf(n.f, "\n\n")
594	return nil
595}
596
597func (n *NinjaGenerator) shName() string {
598	return fmt.Sprintf("ninja%s.sh", n.Suffix)
599}
600
601func (n *NinjaGenerator) ninjaName() string {
602	return fmt.Sprintf("build%s.ninja", n.Suffix)
603}
604
605func (n *NinjaGenerator) envlistName() string {
606	return fmt.Sprintf(".kati_env%s", n.Suffix)
607}
608
609func (n *NinjaGenerator) generateEnvlist() (err error) {
610	f, err := os.Create(n.envlistName())
611	if err != nil {
612		return err
613	}
614	defer func() {
615		cerr := f.Close()
616		if err == nil {
617			err = cerr
618		}
619	}()
620	for k := range usedEnvs {
621		v, err := n.ctx.ev.EvaluateVar(k)
622		if err != nil {
623			return err
624		}
625		fmt.Fprintf(f, "%q=%q\n", k, v)
626	}
627	return nil
628}
629
630func (n *NinjaGenerator) generateShell() (err error) {
631	f, err := os.Create(n.shName())
632	if err != nil {
633		return err
634	}
635	defer func() {
636		cerr := f.Close()
637		if err == nil {
638			err = cerr
639		}
640	}()
641
642	fmt.Fprintf(f, "#!/bin/bash\n")
643	fmt.Fprintf(f, "# Generated by kati %s\n", gitVersion)
644	fmt.Fprintln(f)
645	fmt.Fprintln(f, `cd $(dirname "$0")`)
646	if n.Suffix != "" {
647		fmt.Fprintf(f, "if [ -f %s ]; then\n export $(cat %s)\nfi\n", n.envlistName(), n.envlistName())
648	}
649	for name, export := range n.exports {
650		// export "a b"=c will error on bash
651		// bash: export `a b=c': not a valid identifier
652		if strings.ContainsAny(name, " \t\n\r") {
653			glog.V(1).Infof("ignore export %q (export:%t)", name, export)
654			continue
655		}
656		if export {
657			v, err := n.ctx.ev.EvaluateVar(name)
658			if err != nil {
659				return err
660			}
661			fmt.Fprintf(f, "export %q=%q\n", name, v)
662		} else {
663			fmt.Fprintf(f, "unset %q\n", name)
664		}
665	}
666	if n.GomaDir == "" {
667		fmt.Fprintf(f, `exec ninja -f %s "$@"`+"\n", n.ninjaName())
668	} else {
669		fmt.Fprintf(f, `exec ninja -f %s -j500 "$@"`+"\n", n.ninjaName())
670	}
671
672	return f.Chmod(0755)
673}
674
675func (n *NinjaGenerator) generateNinja(defaultTarget string) (err error) {
676	f, err := os.Create(n.ninjaName())
677	if err != nil {
678		return err
679	}
680	defer func() {
681		cerr := f.Close()
682		if err == nil {
683			err = cerr
684		}
685	}()
686
687	n.f = f
688	fmt.Fprintf(n.f, "# Generated by kati %s\n", gitVersion)
689	fmt.Fprintf(n.f, "\n")
690
691	if len(usedEnvs) > 0 {
692		fmt.Fprintln(n.f, "# Environment variables used:")
693		var names []string
694		for name := range usedEnvs {
695			names = append(names, name)
696		}
697		sort.Strings(names)
698		for _, name := range names {
699			v, err := n.ctx.ev.EvaluateVar(name)
700			if err != nil {
701				return err
702			}
703			fmt.Fprintf(n.f, "# %q=%q\n", name, v)
704		}
705		fmt.Fprintf(n.f, "\n")
706	}
707
708	if n.GomaDir != "" {
709		fmt.Fprintf(n.f, "pool local_pool\n")
710		fmt.Fprintf(n.f, " depth = %d\n\n", runtime.NumCPU())
711	}
712
713	err = n.emitRegenRules()
714	if err != nil {
715		return err
716	}
717
718	// defining $out for $@ and $in for $^ here doesn't work well,
719	// because these texts will be processed in escapeShell...
720	for _, node := range n.nodes {
721		err := n.emitNode(node)
722		if err != nil {
723			return err
724		}
725		glog.V(1).Infof("node %q %s", node.Output, n.done[node.Output])
726	}
727
728	// emit phony targets for visited nodes that are
729	//  - not existing file
730	//  - not alias for other targets.
731	var nodes []string
732	for node, state := range n.done {
733		if state != nodeVisit {
734			continue
735		}
736		nodes = append(nodes, node)
737	}
738	if len(nodes) > 0 {
739		fmt.Fprintln(n.f)
740		sort.Strings(nodes)
741		for _, node := range nodes {
742			n.emitBuild(node, "phony", "", "")
743			fmt.Fprintln(n.f)
744			n.done[node] = nodeBuild
745		}
746	}
747
748	// emit default if the target was emitted.
749	if defaultTarget != "" && n.done[defaultTarget] == nodeBuild {
750		fmt.Fprintf(n.f, "\ndefault %s\n", escapeNinja(defaultTarget))
751	}
752	return nil
753}
754
755// Save generates build.ninja from DepGraph.
756func (n *NinjaGenerator) Save(g *DepGraph, name string, targets []string) error {
757	startTime := time.Now()
758	n.init(g)
759	err := n.generateEnvlist()
760	if err != nil {
761		return err
762	}
763	err = n.generateShell()
764	if err != nil {
765		return err
766	}
767	var defaultTarget string
768	if len(targets) == 0 && len(g.nodes) > 0 {
769		defaultTarget = g.nodes[0].Output
770	}
771	err = n.generateNinja(defaultTarget)
772	if err != nil {
773		return err
774	}
775	logStats("generate ninja time: %q", time.Since(startTime))
776	return nil
777}
778