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	"crypto/sha1"
20	"fmt"
21	"os"
22	"path/filepath"
23	"strconv"
24	"strings"
25	"sync"
26
27	"github.com/golang/glog"
28)
29
30type fileState int
31
32const (
33	fileExists fileState = iota
34	fileNotExists
35	fileInconsistent // Modified during kati is running.
36)
37
38type accessedMakefile struct {
39	Filename string
40	Hash     [sha1.Size]byte
41	State    fileState
42}
43
44type accessCache struct {
45	mu sync.Mutex
46	m  map[string]*accessedMakefile
47}
48
49func newAccessCache() *accessCache {
50	return &accessCache{
51		m: make(map[string]*accessedMakefile),
52	}
53}
54
55func (ac *accessCache) update(fn string, hash [sha1.Size]byte, st fileState) string {
56	if ac == nil {
57		return ""
58	}
59	ac.mu.Lock()
60	defer ac.mu.Unlock()
61	rm, present := ac.m[fn]
62	if present {
63		switch rm.State {
64		case fileExists:
65			if st != fileExists {
66				return fmt.Sprintf("%s was removed after the previous read", fn)
67			} else if !bytes.Equal(hash[:], rm.Hash[:]) {
68				ac.m[fn].State = fileInconsistent
69				return fmt.Sprintf("%s was modified after the previous read", fn)
70			}
71			return ""
72		case fileNotExists:
73			if st != fileNotExists {
74				ac.m[fn].State = fileInconsistent
75				return fmt.Sprintf("%s was created after the previous read", fn)
76			}
77		case fileInconsistent:
78			return ""
79		}
80		return ""
81	}
82	ac.m[fn] = &accessedMakefile{
83		Filename: fn,
84		Hash:     hash,
85		State:    st,
86	}
87	return ""
88}
89
90func (ac *accessCache) Slice() []*accessedMakefile {
91	if ac == nil {
92		return nil
93	}
94	ac.mu.Lock()
95	defer ac.mu.Unlock()
96	r := []*accessedMakefile{}
97	for _, v := range ac.m {
98		r = append(r, v)
99	}
100	return r
101}
102
103type evalResult struct {
104	vars        Vars
105	rules       []*rule
106	ruleVars    map[string]Vars
107	accessedMks []*accessedMakefile
108	exports     map[string]bool
109	vpaths      searchPaths
110}
111
112type srcpos struct {
113	filename string
114	lineno   int
115}
116
117func (p srcpos) String() string {
118	return fmt.Sprintf("%s:%d", p.filename, p.lineno)
119}
120
121// EvalError is an error in kati evaluation.
122type EvalError struct {
123	Filename string
124	Lineno   int
125	Err      error
126}
127
128func (e EvalError) Error() string {
129	return fmt.Sprintf("%s:%d: %v", e.Filename, e.Lineno, e.Err)
130}
131
132func (p srcpos) errorf(f string, args ...interface{}) error {
133	return EvalError{
134		Filename: p.filename,
135		Lineno:   p.lineno,
136		Err:      fmt.Errorf(f, args...),
137	}
138}
139
140func (p srcpos) error(err error) error {
141	if _, ok := err.(EvalError); ok {
142		return err
143	}
144	return EvalError{
145		Filename: p.filename,
146		Lineno:   p.lineno,
147		Err:      err,
148	}
149}
150
151// Evaluator manages makefile evaluation.
152type Evaluator struct {
153	paramVars    []tmpval // $1 => paramVars[1]
154	outVars      Vars
155	outRules     []*rule
156	outRuleVars  map[string]Vars
157	vars         Vars
158	lastRule     *rule
159	currentScope Vars
160	cache        *accessCache
161	exports      map[string]bool
162	vpaths       []vpath
163
164	avoidIO bool
165	hasIO   bool
166	// delayedOutputs are commands which should run at ninja-time
167	// (i.e., info, warning, and error).
168	delayedOutputs []string
169
170	srcpos
171}
172
173// NewEvaluator creates new Evaluator.
174func NewEvaluator(vars map[string]Var) *Evaluator {
175	return &Evaluator{
176		outVars:     make(Vars),
177		vars:        vars,
178		outRuleVars: make(map[string]Vars),
179		exports:     make(map[string]bool),
180	}
181}
182
183func (ev *Evaluator) args(buf *evalBuffer, args ...Value) ([][]byte, error) {
184	pos := make([]int, 0, len(args))
185	for _, arg := range args {
186		buf.resetSep()
187		err := arg.Eval(buf, ev)
188		if err != nil {
189			return nil, err
190		}
191		pos = append(pos, buf.Len())
192	}
193	v := buf.Bytes()
194	buf.args = buf.args[:0]
195	s := 0
196	for _, p := range pos {
197		buf.args = append(buf.args, v[s:p])
198		s = p
199	}
200	return buf.args, nil
201}
202
203func (ev *Evaluator) evalAssign(ast *assignAST) error {
204	ev.lastRule = nil
205	lhs, rhs, err := ev.evalAssignAST(ast)
206	if err != nil {
207		return err
208	}
209	if glog.V(1) {
210		glog.Infof("ASSIGN: %s=%q (flavor:%q)", lhs, rhs, rhs.Flavor())
211	}
212	if lhs == "" {
213		return ast.errorf("*** empty variable name.")
214	}
215	ev.outVars.Assign(lhs, rhs)
216	return nil
217}
218
219func (ev *Evaluator) evalAssignAST(ast *assignAST) (string, Var, error) {
220	ev.srcpos = ast.srcpos
221
222	var lhs string
223	switch v := ast.lhs.(type) {
224	case literal:
225		lhs = string(v)
226	case tmpval:
227		lhs = string(v)
228	default:
229		buf := newEbuf()
230		err := v.Eval(buf, ev)
231		if err != nil {
232			return "", nil, err
233		}
234		lhs = string(trimSpaceBytes(buf.Bytes()))
235		buf.release()
236	}
237	rhs, err := ast.evalRHS(ev, lhs)
238	if err != nil {
239		return "", nil, err
240	}
241	return lhs, rhs, nil
242}
243
244func (ev *Evaluator) setTargetSpecificVar(assign *assignAST, output string) error {
245	vars, present := ev.outRuleVars[output]
246	if !present {
247		vars = make(Vars)
248		ev.outRuleVars[output] = vars
249	}
250	ev.currentScope = vars
251	lhs, rhs, err := ev.evalAssignAST(assign)
252	if err != nil {
253		return err
254	}
255	if glog.V(1) {
256		glog.Infof("rule outputs:%q assign:%q%s%q (flavor:%q)", output, lhs, assign.op, rhs, rhs.Flavor())
257	}
258	vars.Assign(lhs, &targetSpecificVar{v: rhs, op: assign.op})
259	ev.currentScope = nil
260	return nil
261}
262
263func (ev *Evaluator) evalMaybeRule(ast *maybeRuleAST) error {
264	ev.lastRule = nil
265	ev.srcpos = ast.srcpos
266
267	if glog.V(1) {
268		glog.Infof("maybe rule %s: %q assign:%v", ev.srcpos, ast.expr, ast.assign)
269	}
270
271	abuf := newEbuf()
272	aexpr := toExpr(ast.expr)
273	var rhs expr
274	semi := ast.semi
275	for i, v := range aexpr {
276		var hashFound bool
277		var buf evalBuffer
278		buf.resetSep()
279		switch v.(type) {
280		case literal, tmpval:
281			s := v.String()
282			i := strings.Index(s, "#")
283			if i >= 0 {
284				hashFound = true
285				v = tmpval(trimRightSpaceBytes([]byte(s[:i])))
286			}
287		}
288		err := v.Eval(&buf, ev)
289		if err != nil {
290			return err
291		}
292		b := buf.Bytes()
293		if ast.isRule {
294			abuf.Write(b)
295			continue
296		}
297		eq := findLiteralChar(b, '=', 0, skipVar)
298		if eq >= 0 {
299			abuf.Write(b[:eq+1])
300			if eq+1 < len(b) {
301				rhs = append(rhs, tmpval(trimLeftSpaceBytes(b[eq+1:])))
302			}
303			if i+1 < len(aexpr) {
304				rhs = append(rhs, aexpr[i+1:]...)
305			}
306			if ast.semi != nil {
307				rhs = append(rhs, literal(';'))
308				sexpr, _, err := parseExpr(ast.semi, nil, parseOp{})
309				if err != nil {
310					return err
311				}
312				rhs = append(rhs, toExpr(sexpr)...)
313				semi = nil
314			}
315			break
316		}
317		abuf.Write(b)
318		if hashFound {
319			break
320		}
321	}
322
323	line := abuf.Bytes()
324	r := &rule{srcpos: ast.srcpos}
325	if glog.V(1) {
326		glog.Infof("rule? %s: %q assign:%v rhs:%s", r.srcpos, line, ast.assign, rhs)
327	}
328	assign, err := r.parse(line, ast.assign, rhs)
329	if err != nil {
330		ws := newWordScanner(line)
331		if ws.Scan() {
332			if string(ws.Bytes()) == "override" {
333				warnNoPrefix(ast.srcpos, "invalid `override' directive")
334				return nil
335			}
336		}
337		return ast.error(err)
338	}
339	abuf.release()
340	if glog.V(1) {
341		glog.Infof("rule %q assign:%v rhs:%v=> outputs:%q, inputs:%q", ast.expr, ast.assign, rhs, r.outputs, r.inputs)
342	}
343
344	// TODO: Pretty print.
345	// glog.V(1).Infof("RULE: %s=%s (%d commands)", lhs, rhs, len(cmds))
346
347	if assign != nil {
348		glog.V(1).Infof("target specific var: %#v", assign)
349		for _, output := range r.outputs {
350			ev.setTargetSpecificVar(assign, output)
351		}
352		for _, output := range r.outputPatterns {
353			ev.setTargetSpecificVar(assign, output.String())
354		}
355		return nil
356	}
357
358	if semi != nil {
359		r.cmds = append(r.cmds, string(semi))
360	}
361	if glog.V(1) {
362		glog.Infof("rule outputs:%q cmds:%q", r.outputs, r.cmds)
363	}
364	ev.lastRule = r
365	ev.outRules = append(ev.outRules, r)
366	return nil
367}
368
369func (ev *Evaluator) evalCommand(ast *commandAST) error {
370	ev.srcpos = ast.srcpos
371	if ev.lastRule == nil || ev.lastRule.outputs == nil {
372		// This could still be an assignment statement. See
373		// assign_after_tab.mk.
374		if strings.IndexByte(ast.cmd, '=') >= 0 {
375			line := trimLeftSpace(ast.cmd)
376			mk, err := parseMakefileString(line, ast.srcpos)
377			if err != nil {
378				return ast.errorf("parse failed: %q: %v", line, err)
379			}
380			if len(mk.stmts) >= 1 && mk.stmts[len(mk.stmts)-1].(*assignAST) != nil {
381				for _, stmt := range mk.stmts {
382					err = ev.eval(stmt)
383					if err != nil {
384						return err
385					}
386				}
387			}
388			return nil
389		}
390		// Or, a comment is OK.
391		if strings.TrimSpace(ast.cmd)[0] == '#' {
392			return nil
393		}
394		return ast.errorf("*** commands commence before first target.")
395	}
396	ev.lastRule.cmds = append(ev.lastRule.cmds, ast.cmd)
397	if ev.lastRule.cmdLineno == 0 {
398		ev.lastRule.cmdLineno = ast.lineno
399	}
400	return nil
401}
402
403func (ev *Evaluator) paramVar(name string) (Var, error) {
404	idx, err := strconv.ParseInt(name, 10, 32)
405	if err != nil {
406		return nil, fmt.Errorf("param: %s: %v", name, err)
407	}
408	i := int(idx)
409	if i < 0 || i >= len(ev.paramVars) {
410		return nil, fmt.Errorf("param: %s out of %d", name, len(ev.paramVars))
411	}
412	return &automaticVar{value: []byte(ev.paramVars[i])}, nil
413}
414
415// LookupVar looks up named variable.
416func (ev *Evaluator) LookupVar(name string) Var {
417	if ev.currentScope != nil {
418		v := ev.currentScope.Lookup(name)
419		if v.IsDefined() {
420			return v
421		}
422	}
423	v := ev.outVars.Lookup(name)
424	if v.IsDefined() {
425		return v
426	}
427	v, err := ev.paramVar(name)
428	if err == nil {
429		return v
430	}
431	return ev.vars.Lookup(name)
432}
433
434func (ev *Evaluator) lookupVarInCurrentScope(name string) Var {
435	if ev.currentScope != nil {
436		v := ev.currentScope.Lookup(name)
437		return v
438	}
439	v := ev.outVars.Lookup(name)
440	if v.IsDefined() {
441		return v
442	}
443	v, err := ev.paramVar(name)
444	if err == nil {
445		return v
446	}
447	return ev.vars.Lookup(name)
448}
449
450// EvaluateVar evaluates variable named name.
451// Only for a few special uses such as getting SHELL and handling
452// export/unexport.
453func (ev *Evaluator) EvaluateVar(name string) (string, error) {
454	var buf evalBuffer
455	buf.resetSep()
456	err := ev.LookupVar(name).Eval(&buf, ev)
457	if err != nil {
458		return "", err
459	}
460	return buf.String(), nil
461}
462
463func (ev *Evaluator) evalIncludeFile(fname string, mk makefile) error {
464	te := traceEvent.begin("include", literal(fname), traceEventMain)
465	defer func() {
466		traceEvent.end(te)
467	}()
468	var err error
469	makefileList := ev.outVars.Lookup("MAKEFILE_LIST")
470	makefileList, err = makefileList.Append(ev, mk.filename)
471	if err != nil {
472		return err
473	}
474	ev.outVars.Assign("MAKEFILE_LIST", makefileList)
475
476	for _, stmt := range mk.stmts {
477		err = ev.eval(stmt)
478		if err != nil {
479			return err
480		}
481	}
482	return nil
483}
484
485func (ev *Evaluator) evalInclude(ast *includeAST) error {
486	ev.lastRule = nil
487	ev.srcpos = ast.srcpos
488
489	glog.Infof("%s include %q", ev.srcpos, ast.expr)
490	v, _, err := parseExpr([]byte(ast.expr), nil, parseOp{})
491	if err != nil {
492		return ast.errorf("parse failed: %q: %v", ast.expr, err)
493	}
494	var buf evalBuffer
495	buf.resetSep()
496	err = v.Eval(&buf, ev)
497	if err != nil {
498		return ast.errorf("%v", err)
499	}
500	pats := splitSpaces(buf.String())
501	buf.Reset()
502
503	var files []string
504	for _, pat := range pats {
505		if strings.Contains(pat, "*") || strings.Contains(pat, "?") {
506			matched, err := filepath.Glob(pat)
507			if err != nil {
508				return ast.errorf("glob error: %s: %v", pat, err)
509			}
510			files = append(files, matched...)
511		} else {
512			files = append(files, pat)
513		}
514	}
515
516	for _, fn := range files {
517		fn = trimLeadingCurdir(fn)
518		if IgnoreOptionalInclude != "" && ast.op == "-include" && matchPattern(fn, IgnoreOptionalInclude) {
519			continue
520		}
521		mk, hash, err := makefileCache.parse(fn)
522		if os.IsNotExist(err) {
523			if ast.op == "include" {
524				return ev.errorf("%v\nNOTE: kati does not support generating missing makefiles", err)
525			}
526			msg := ev.cache.update(fn, hash, fileNotExists)
527			if msg != "" {
528				warn(ev.srcpos, "%s", msg)
529			}
530			continue
531		}
532		msg := ev.cache.update(fn, hash, fileExists)
533		if msg != "" {
534			warn(ev.srcpos, "%s", msg)
535		}
536		err = ev.evalIncludeFile(fn, mk)
537		if err != nil {
538			return err
539		}
540	}
541	return nil
542}
543
544func (ev *Evaluator) evalIf(iast *ifAST) error {
545	var isTrue bool
546	switch iast.op {
547	case "ifdef", "ifndef":
548		expr := iast.lhs
549		buf := newEbuf()
550		err := expr.Eval(buf, ev)
551		if err != nil {
552			return iast.errorf("%v\n expr:%s", err, expr)
553		}
554		v := ev.LookupVar(buf.String())
555		buf.Reset()
556		err = v.Eval(buf, ev)
557		if err != nil {
558			return iast.errorf("%v\n expr:%s=>%s", err, expr, v)
559		}
560		value := buf.String()
561		val := buf.Len()
562		buf.release()
563		isTrue = (val > 0) == (iast.op == "ifdef")
564		if glog.V(1) {
565			glog.Infof("%s lhs=%q value=%q => %t", iast.op, iast.lhs, value, isTrue)
566		}
567	case "ifeq", "ifneq":
568		lexpr := iast.lhs
569		rexpr := iast.rhs
570		buf := newEbuf()
571		params, err := ev.args(buf, lexpr, rexpr)
572		if err != nil {
573			return iast.errorf("%v\n (%s,%s)", err, lexpr, rexpr)
574		}
575		lhs := string(params[0])
576		rhs := string(params[1])
577		buf.release()
578		isTrue = (lhs == rhs) == (iast.op == "ifeq")
579		if glog.V(1) {
580			glog.Infof("%s lhs=%q %q rhs=%q %q => %t", iast.op, iast.lhs, lhs, iast.rhs, rhs, isTrue)
581		}
582	default:
583		return iast.errorf("unknown if statement: %q", iast.op)
584	}
585
586	var stmts []ast
587	if isTrue {
588		stmts = iast.trueStmts
589	} else {
590		stmts = iast.falseStmts
591	}
592	for _, stmt := range stmts {
593		err := ev.eval(stmt)
594		if err != nil {
595			return err
596		}
597	}
598	return nil
599}
600
601func (ev *Evaluator) evalExport(ast *exportAST) error {
602	ev.lastRule = nil
603	ev.srcpos = ast.srcpos
604
605	v, _, err := parseExpr(ast.expr, nil, parseOp{})
606	if err != nil {
607		return ast.errorf("failed to parse: %q: %v", string(ast.expr), err)
608	}
609	var buf evalBuffer
610	buf.resetSep()
611	err = v.Eval(&buf, ev)
612	if err != nil {
613		return ast.errorf("%v\n expr:%s", err, v)
614	}
615	if ast.hasEqual {
616		ev.exports[string(trimSpaceBytes(buf.Bytes()))] = ast.export
617	} else {
618		for _, n := range splitSpacesBytes(buf.Bytes()) {
619			ev.exports[string(n)] = ast.export
620		}
621	}
622	return nil
623}
624
625func (ev *Evaluator) evalVpath(ast *vpathAST) error {
626	ev.lastRule = nil
627	ev.srcpos = ast.srcpos
628
629	var ebuf evalBuffer
630	ebuf.resetSep()
631	err := ast.expr.Eval(&ebuf, ev)
632	if err != nil {
633		return ast.errorf("%v\n expr:%s", err, ast.expr)
634	}
635	ws := newWordScanner(ebuf.Bytes())
636	if !ws.Scan() {
637		ev.vpaths = nil
638		return nil
639	}
640	pat := string(ws.Bytes())
641	if !ws.Scan() {
642		vpaths := ev.vpaths
643		ev.vpaths = nil
644		for _, v := range vpaths {
645			if v.pattern == pat {
646				continue
647			}
648			ev.vpaths = append(ev.vpaths, v)
649		}
650		return nil
651	}
652	// The search path, DIRECTORIES, is a list of directories to be
653	// searched, separated by colons (semi-colons on MS-DOS and
654	// MS-Windows) or blanks, just like the search path used in the
655	// `VPATH' variable.
656	var dirs []string
657	for {
658		for _, dir := range bytes.Split(ws.Bytes(), []byte{':'}) {
659			dirs = append(dirs, string(dir))
660		}
661		if !ws.Scan() {
662			break
663		}
664	}
665	ev.vpaths = append(ev.vpaths, vpath{
666		pattern: pat,
667		dirs:    dirs,
668	})
669	return nil
670}
671
672func (ev *Evaluator) eval(stmt ast) error {
673	return stmt.eval(ev)
674}
675
676func eval(mk makefile, vars Vars, useCache bool) (er *evalResult, err error) {
677	ev := NewEvaluator(vars)
678	if useCache {
679		ev.cache = newAccessCache()
680	}
681
682	makefileList := vars.Lookup("MAKEFILE_LIST")
683	if !makefileList.IsDefined() {
684		makefileList = &simpleVar{value: []string{""}, origin: "file"}
685	}
686	makefileList, err = makefileList.Append(ev, mk.filename)
687	if err != nil {
688		return nil, err
689	}
690	ev.outVars.Assign("MAKEFILE_LIST", makefileList)
691
692	for _, stmt := range mk.stmts {
693		err = ev.eval(stmt)
694		if err != nil {
695			return nil, err
696		}
697	}
698
699	vpaths := searchPaths{
700		vpaths: ev.vpaths,
701	}
702	v, found := ev.outVars["VPATH"]
703	if found {
704		wb := newWbuf()
705		err := v.Eval(wb, ev)
706		if err != nil {
707			return nil, err
708		}
709		// In the 'VPATH' variable, directory names are separated
710		// by colons or blanks. (on windows, semi-colons)
711		for _, word := range wb.words {
712			for _, dir := range bytes.Split(word, []byte{':'}) {
713				vpaths.dirs = append(vpaths.dirs, string(dir))
714			}
715		}
716	}
717	glog.Infof("vpaths: %#v", vpaths)
718
719	return &evalResult{
720		vars:        ev.outVars,
721		rules:       ev.outRules,
722		ruleVars:    ev.outRuleVars,
723		accessedMks: ev.cache.Slice(),
724		exports:     ev.exports,
725		vpaths:      vpaths,
726	}, nil
727}
728