• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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	"fmt"
19	"path/filepath"
20	"sort"
21	"strings"
22
23	"github.com/golang/glog"
24)
25
26// DepNode represents a makefile rule for an output.
27type DepNode struct {
28	Output             string
29	Cmds               []string
30	Deps               []*DepNode
31	OrderOnlys         []*DepNode
32	Parents            []*DepNode
33	HasRule            bool
34	IsPhony            bool
35	ActualInputs       []string
36	TargetSpecificVars Vars
37	Filename           string
38	Lineno             int
39}
40
41func (n *DepNode) String() string {
42	return fmt.Sprintf("Dep{output=%s cmds=%d deps=%d orders=%d hasRule=%t phony=%t filename=%s lineno=%d}",
43		n.Output, len(n.Cmds), len(n.Deps), len(n.OrderOnlys), n.HasRule, n.IsPhony, n.Filename, n.Lineno)
44}
45
46type depBuilder struct {
47	rules    map[string]*rule
48	ruleVars map[string]Vars
49
50	implicitRules *ruleTrie
51
52	suffixRules map[string][]*rule
53	firstRule   *rule
54	vars        Vars
55	ev          *Evaluator
56	vpaths      searchPaths
57	done        map[string]*DepNode
58	phony       map[string]bool
59
60	trace                         []string
61	nodeCnt                       int
62	pickExplicitRuleCnt           int
63	pickImplicitRuleCnt           int
64	pickSuffixRuleCnt             int
65	pickExplicitRuleWithoutCmdCnt int
66}
67
68type ruleTrieEntry struct {
69	rule   *rule
70	suffix string
71}
72
73type ruleTrie struct {
74	rules    []ruleTrieEntry
75	children map[byte]*ruleTrie
76}
77
78func newRuleTrie() *ruleTrie {
79	return &ruleTrie{
80		children: make(map[byte]*ruleTrie),
81	}
82}
83
84func (rt *ruleTrie) add(name string, r *rule) {
85	glog.V(1).Infof("rule trie: add %q %v %s", name, r.outputPatterns[0], r)
86	if name == "" || name[0] == '%' {
87		glog.V(1).Infof("rule trie: add entry %q %v %s", name, r.outputPatterns[0], r)
88		rt.rules = append(rt.rules, ruleTrieEntry{
89			rule:   r,
90			suffix: name,
91		})
92		return
93	}
94	c, found := rt.children[name[0]]
95	if !found {
96		c = newRuleTrie()
97		rt.children[name[0]] = c
98	}
99	c.add(name[1:], r)
100}
101
102func (rt *ruleTrie) lookup(name string) []*rule {
103	glog.V(1).Infof("rule trie: lookup %q", name)
104	if rt == nil {
105		return nil
106	}
107	var rules []*rule
108	for _, entry := range rt.rules {
109		if (entry.suffix == "" && name == "") || strings.HasSuffix(name, entry.suffix[1:]) {
110			rules = append(rules, entry.rule)
111		}
112	}
113	if name == "" {
114		return rules
115	}
116	rules = append(rules, rt.children[name[0]].lookup(name[1:])...)
117	glog.V(1).Infof("rule trie: lookup %q => %v", name, rules)
118	return rules
119}
120
121func (rt *ruleTrie) size() int {
122	if rt == nil {
123		return 0
124	}
125	size := len(rt.rules)
126	for _, c := range rt.children {
127		size += c.size()
128	}
129	return size
130}
131
132func replaceSuffix(s string, newsuf string) string {
133	// TODO: Factor out the logic around suffix rules and use
134	// it from substitution references.
135	// http://www.gnu.org/software/make/manual/make.html#Substitution-Refs
136	return fmt.Sprintf("%s.%s", stripExt(s), newsuf)
137}
138
139func (db *depBuilder) exists(target string) bool {
140	_, present := db.rules[target]
141	if present {
142		return true
143	}
144	if db.phony[target] {
145		return true
146	}
147	_, ok := db.vpaths.exists(target)
148	return ok
149}
150
151func (db *depBuilder) canPickImplicitRule(r *rule, output string) bool {
152	outputPattern := r.outputPatterns[0]
153	if !outputPattern.match(output) {
154		return false
155	}
156	for _, input := range r.inputs {
157		input = outputPattern.subst(input, output)
158		if !db.exists(input) {
159			return false
160		}
161	}
162	return true
163}
164
165func (db *depBuilder) mergeImplicitRuleVars(outputs []string, vars Vars) Vars {
166	if len(outputs) != 1 {
167		// TODO(ukai): should return error?
168		panic(fmt.Sprintf("FIXME: Implicit rule should have only one output but %q", outputs))
169	}
170	glog.V(1).Infof("merge? %q", db.ruleVars)
171	glog.V(1).Infof("merge? %q", outputs[0])
172	ivars, present := db.ruleVars[outputs[0]]
173	if !present {
174		return vars
175	}
176	if vars == nil {
177		return ivars
178	}
179	glog.V(1).Info("merge!")
180	v := make(Vars)
181	v.Merge(ivars)
182	v.Merge(vars)
183	return v
184}
185
186func (db *depBuilder) pickRule(output string) (*rule, Vars, bool) {
187	r, present := db.rules[output]
188	vars := db.ruleVars[output]
189	if present {
190		db.pickExplicitRuleCnt++
191		if len(r.cmds) > 0 {
192			return r, vars, true
193		}
194		// If none of the explicit rules for a target has commands,
195		// then `make' searches for an applicable implicit rule to
196		// find some commands.
197		db.pickExplicitRuleWithoutCmdCnt++
198	}
199
200	irules := db.implicitRules.lookup(output)
201	for i := len(irules) - 1; i >= 0; i-- {
202		irule := irules[i]
203		if !db.canPickImplicitRule(irule, output) {
204			glog.Infof("ignore implicit rule %q %s", output, irule)
205			continue
206		}
207		glog.Infof("pick implicit rule %q => %q %s", output, irule.outputPatterns, irule)
208		db.pickImplicitRuleCnt++
209		if r != nil {
210			ir := &rule{}
211			*ir = *r
212			ir.outputPatterns = irule.outputPatterns
213			// implicit rule's prerequisites will be used for $<
214			ir.inputs = append(irule.inputs, ir.inputs...)
215			ir.cmds = irule.cmds
216			// TODO(ukai): filename, lineno?
217			ir.cmdLineno = irule.cmdLineno
218			return ir, vars, true
219		}
220		if vars != nil {
221			var outputs []string
222			for _, op := range irule.outputPatterns {
223				outputs = append(outputs, op.String())
224			}
225			vars = db.mergeImplicitRuleVars(outputs, vars)
226		}
227		// TODO(ukai): check len(irule.cmd) ?
228		return irule, vars, true
229	}
230
231	outputSuffix := filepath.Ext(output)
232	if !strings.HasPrefix(outputSuffix, ".") {
233		return r, vars, r != nil
234	}
235	rules, present := db.suffixRules[outputSuffix[1:]]
236	if !present {
237		return r, vars, r != nil
238	}
239	for _, irule := range rules {
240		if len(irule.inputs) != 1 {
241			// TODO(ukai): should return error?
242			panic(fmt.Sprintf("FIXME: unexpected number of input for a suffix rule (%d)", len(irule.inputs)))
243		}
244		if !db.exists(replaceSuffix(output, irule.inputs[0])) {
245			continue
246		}
247		db.pickSuffixRuleCnt++
248		if r != nil {
249			sr := &rule{}
250			*sr = *r
251			// TODO(ukai): input order is correct?
252			sr.inputs = append([]string{replaceSuffix(output, irule.inputs[0])}, r.inputs...)
253			sr.cmds = irule.cmds
254			// TODO(ukai): filename, lineno?
255			sr.cmdLineno = irule.cmdLineno
256			return sr, vars, true
257		}
258		if vars != nil {
259			vars = db.mergeImplicitRuleVars(irule.outputs, vars)
260		}
261		// TODO(ukai): check len(irule.cmd) ?
262		return irule, vars, true
263	}
264	return r, vars, r != nil
265}
266
267func expandInputs(rule *rule, output string) []string {
268	var inputs []string
269	for _, input := range rule.inputs {
270		if len(rule.outputPatterns) > 0 {
271			if len(rule.outputPatterns) != 1 {
272				panic(fmt.Sprintf("FIXME: multiple output pattern is not supported yet"))
273			}
274			input = intern(rule.outputPatterns[0].subst(input, output))
275		} else if rule.isSuffixRule {
276			input = intern(replaceSuffix(output, input))
277		}
278		inputs = append(inputs, input)
279	}
280	return inputs
281}
282
283func (db *depBuilder) buildPlan(output string, neededBy string, tsvs Vars) (*DepNode, error) {
284	glog.V(1).Infof("Evaluating command: %s", output)
285	db.nodeCnt++
286	if db.nodeCnt%100 == 0 {
287		db.reportStats()
288	}
289
290	if n, present := db.done[output]; present {
291		return n, nil
292	}
293
294	n := &DepNode{Output: output, IsPhony: db.phony[output]}
295	db.done[output] = n
296
297	// create depnode for phony targets?
298	rule, vars, present := db.pickRule(output)
299	if !present {
300		return n, nil
301	}
302
303	var restores []func()
304	if vars != nil {
305		for name, v := range vars {
306			// TODO: Consider not updating db.vars.
307			tsv := v.(*targetSpecificVar)
308			restores = append(restores, db.vars.save(name))
309			restores = append(restores, tsvs.save(name))
310			switch tsv.op {
311			case ":=", "=":
312				db.vars[name] = tsv
313				tsvs[name] = v
314			case "+=":
315				oldVar, present := db.vars[name]
316				if !present || oldVar.String() == "" {
317					db.vars[name] = tsv
318				} else {
319					var err error
320					v, err = oldVar.AppendVar(db.ev, tsv)
321					if err != nil {
322						return nil, err
323					}
324					db.vars[name] = v
325				}
326				tsvs[name] = v
327			case "?=":
328				if _, present := db.vars[name]; !present {
329					db.vars[name] = tsv
330					tsvs[name] = v
331				}
332			}
333		}
334		defer func() {
335			for _, restore := range restores {
336				restore()
337			}
338		}()
339	}
340
341	inputs := expandInputs(rule, output)
342	glog.Infof("Evaluating command: %s inputs:%q => %q", output, rule.inputs, inputs)
343	for _, input := range inputs {
344		db.trace = append(db.trace, input)
345		ni, err := db.buildPlan(input, output, tsvs)
346		db.trace = db.trace[0 : len(db.trace)-1]
347		if err != nil {
348			return nil, err
349		}
350		if ni != nil {
351			n.Deps = append(n.Deps, ni)
352			ni.Parents = append(ni.Parents, n)
353		}
354	}
355
356	for _, input := range rule.orderOnlyInputs {
357		db.trace = append(db.trace, input)
358		ni, err := db.buildPlan(input, output, tsvs)
359		db.trace = db.trace[0 : len(db.trace)-1]
360		if err != nil {
361			return nil, err
362		}
363		if n != nil {
364			n.OrderOnlys = append(n.OrderOnlys, ni)
365			ni.Parents = append(ni.Parents, n)
366		}
367	}
368
369	n.HasRule = true
370	n.Cmds = rule.cmds
371	n.ActualInputs = inputs
372	n.TargetSpecificVars = make(Vars)
373	for k, v := range tsvs {
374		if glog.V(1) {
375			glog.Infof("output=%s tsv %s=%s", output, k, v)
376		}
377		n.TargetSpecificVars[k] = v
378	}
379	n.Filename = rule.filename
380	if len(rule.cmds) > 0 {
381		if rule.cmdLineno > 0 {
382			n.Lineno = rule.cmdLineno
383		} else {
384			n.Lineno = rule.lineno
385		}
386	}
387	return n, nil
388}
389
390func (db *depBuilder) populateSuffixRule(r *rule, output string) bool {
391	if len(output) == 0 || output[0] != '.' {
392		return false
393	}
394	rest := output[1:]
395	dotIndex := strings.IndexByte(rest, '.')
396	// If there is only a single dot or the third dot, this is not a
397	// suffix rule.
398	if dotIndex < 0 || strings.IndexByte(rest[dotIndex+1:], '.') >= 0 {
399		return false
400	}
401
402	// This is a suffix rule.
403	inputSuffix := rest[:dotIndex]
404	outputSuffix := rest[dotIndex+1:]
405	sr := &rule{}
406	*sr = *r
407	sr.inputs = []string{inputSuffix}
408	sr.isSuffixRule = true
409	db.suffixRules[outputSuffix] = append([]*rule{sr}, db.suffixRules[outputSuffix]...)
410	return true
411}
412
413func mergeRules(oldRule, r *rule, output string, isSuffixRule bool) (*rule, error) {
414	if oldRule.isDoubleColon != r.isDoubleColon {
415		return nil, r.errorf("*** target file %q has both : and :: entries.", output)
416	}
417	if len(oldRule.cmds) > 0 && len(r.cmds) > 0 && !isSuffixRule && !r.isDoubleColon {
418		warn(r.cmdpos(), "overriding commands for target %q", output)
419		warn(oldRule.cmdpos(), "ignoring old commands for target %q", output)
420	}
421
422	mr := &rule{}
423	*mr = *r
424	if r.isDoubleColon {
425		mr.cmds = append(oldRule.cmds, mr.cmds...)
426	} else if len(oldRule.cmds) > 0 && len(r.cmds) == 0 {
427		mr.cmds = oldRule.cmds
428	}
429	// If the latter rule has a command (regardless of the
430	// commands in oldRule), inputs in the latter rule has a
431	// priority.
432	if len(r.cmds) > 0 {
433		mr.inputs = append(mr.inputs, oldRule.inputs...)
434		mr.orderOnlyInputs = append(mr.orderOnlyInputs, oldRule.orderOnlyInputs...)
435	} else {
436		mr.inputs = append(oldRule.inputs, mr.inputs...)
437		mr.orderOnlyInputs = append(oldRule.orderOnlyInputs, mr.orderOnlyInputs...)
438	}
439	mr.outputPatterns = append(mr.outputPatterns, oldRule.outputPatterns...)
440	return mr, nil
441}
442
443// expandPattern expands static pattern (target: target-pattern: prereq-pattern).
444
445func expandPattern(r *rule) []*rule {
446	if len(r.outputs) == 0 {
447		return []*rule{r}
448	}
449	if len(r.outputPatterns) != 1 {
450		return []*rule{r}
451	}
452	var rules []*rule
453	pat := r.outputPatterns[0]
454	for _, output := range r.outputs {
455		nr := new(rule)
456		*nr = *r
457		nr.outputs = []string{output}
458		nr.outputPatterns = nil
459		nr.inputs = nil
460		for _, input := range r.inputs {
461			nr.inputs = append(nr.inputs, intern(pat.subst(input, output)))
462		}
463		rules = append(rules, nr)
464	}
465	glog.V(1).Infof("expand static pattern: outputs=%q inputs=%q -> %q", r.outputs, r.inputs, rules)
466	return rules
467}
468
469func (db *depBuilder) populateExplicitRule(r *rule) error {
470	// It seems rules with no outputs are siliently ignored.
471	if len(r.outputs) == 0 {
472		return nil
473	}
474	for _, output := range r.outputs {
475		output = trimLeadingCurdir(output)
476
477		isSuffixRule := db.populateSuffixRule(r, output)
478
479		if oldRule, present := db.rules[output]; present {
480			mr, err := mergeRules(oldRule, r, output, isSuffixRule)
481			if err != nil {
482				return err
483			}
484			db.rules[output] = mr
485		} else {
486			db.rules[output] = r
487			if db.firstRule == nil && !strings.HasPrefix(output, ".") {
488				db.firstRule = r
489			}
490		}
491	}
492	return nil
493}
494
495func (db *depBuilder) populateImplicitRule(r *rule) {
496	for _, outputPattern := range r.outputPatterns {
497		ir := &rule{}
498		*ir = *r
499		ir.outputPatterns = []pattern{outputPattern}
500		db.implicitRules.add(outputPattern.String(), ir)
501	}
502}
503
504func (db *depBuilder) populateRules(er *evalResult) error {
505	for _, r := range er.rules {
506		for i, input := range r.inputs {
507			r.inputs[i] = trimLeadingCurdir(input)
508		}
509		for i, orderOnlyInput := range r.orderOnlyInputs {
510			r.orderOnlyInputs[i] = trimLeadingCurdir(orderOnlyInput)
511		}
512		for _, r := range expandPattern(r) {
513			err := db.populateExplicitRule(r)
514			if err != nil {
515				return err
516			}
517			if len(r.outputs) == 0 {
518				db.populateImplicitRule(r)
519			}
520		}
521	}
522	return nil
523}
524
525func (db *depBuilder) reportStats() {
526	if !PeriodicStatsFlag {
527		return
528	}
529
530	logStats("node=%d explicit=%d implicit=%d suffix=%d explicitWOCmd=%d",
531		db.nodeCnt, db.pickExplicitRuleCnt, db.pickImplicitRuleCnt, db.pickSuffixRuleCnt, db.pickExplicitRuleWithoutCmdCnt)
532	if len(db.trace) > 1 {
533		logStats("trace=%q", db.trace)
534	}
535}
536
537func newDepBuilder(er *evalResult, vars Vars) (*depBuilder, error) {
538	db := &depBuilder{
539		rules:         make(map[string]*rule),
540		ruleVars:      er.ruleVars,
541		implicitRules: newRuleTrie(),
542		suffixRules:   make(map[string][]*rule),
543		vars:          vars,
544		ev:            NewEvaluator(vars),
545		vpaths:        er.vpaths,
546		done:          make(map[string]*DepNode),
547		phony:         make(map[string]bool),
548	}
549
550	err := db.populateRules(er)
551	if err != nil {
552		return nil, err
553	}
554	rule, present := db.rules[".PHONY"]
555	if present {
556		for _, input := range rule.inputs {
557			db.phony[input] = true
558		}
559	}
560	return db, nil
561}
562
563func (db *depBuilder) Eval(targets []string) ([]*DepNode, error) {
564	if len(targets) == 0 {
565		if db.firstRule == nil {
566			return nil, fmt.Errorf("*** No targets.")
567		}
568		targets = append(targets, db.firstRule.outputs[0])
569		var phonys []string
570		for t := range db.phony {
571			phonys = append(phonys, t)
572		}
573		sort.Strings(phonys)
574		targets = append(targets, phonys...)
575	}
576
577	if StatsFlag {
578		logStats("%d variables", len(db.vars))
579		logStats("%d explicit rules", len(db.rules))
580		logStats("%d implicit rules", db.implicitRules.size())
581		logStats("%d suffix rules", len(db.suffixRules))
582		logStats("%d dirs %d files", fsCache.dirs(), fsCache.files())
583	}
584
585	var nodes []*DepNode
586	for _, target := range targets {
587		db.trace = []string{target}
588		n, err := db.buildPlan(target, "", make(Vars))
589		if err != nil {
590			return nil, err
591		}
592		nodes = append(nodes, n)
593	}
594	db.reportStats()
595	return nodes, nil
596}
597