1// Copyright 2017 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 parser
16
17import (
18	"errors"
19	"fmt"
20	"io"
21	"sort"
22	"text/scanner"
23)
24
25var errTooManyErrors = errors.New("too many errors")
26
27const maxErrors = 100
28
29type ParseError struct {
30	Err error
31	Pos scanner.Position
32}
33
34func (e *ParseError) Error() string {
35	return fmt.Sprintf("%s: %s", e.Pos, e.Err)
36}
37
38const builtinDollar = "__builtin_dollar"
39
40var builtinDollarName = SimpleMakeString(builtinDollar, NoPos)
41
42func (p *parser) Parse() ([]Node, []error) {
43	defer func() {
44		if r := recover(); r != nil {
45			if r == errTooManyErrors {
46				return
47			}
48			panic(r)
49		}
50	}()
51
52	p.parseLines()
53	p.accept(scanner.EOF)
54	p.nodes = append(p.nodes, p.comments...)
55	sort.Sort(byPosition(p.nodes))
56
57	return p.nodes, p.errors
58}
59
60type parser struct {
61	scanner  scanner.Scanner
62	tok      rune
63	errors   []error
64	comments []Node
65	nodes    []Node
66	lines    []int
67}
68
69func NewParser(filename string, r io.Reader) *parser {
70	p := &parser{}
71	p.lines = []int{0}
72	p.scanner.Init(r)
73	p.scanner.Error = func(sc *scanner.Scanner, msg string) {
74		p.errorf(msg)
75	}
76	p.scanner.Whitespace = 0
77	p.scanner.IsIdentRune = func(ch rune, i int) bool {
78		return ch > 0 && ch != ':' && ch != '#' && ch != '=' && ch != '+' && ch != '$' &&
79			ch != '\\' && ch != '(' && ch != ')' && ch != '{' && ch != '}' && ch != ';' &&
80			ch != '|' && ch != '?' && ch != '\r' && !isWhitespace(ch)
81	}
82	p.scanner.Mode = scanner.ScanIdents
83	p.scanner.Filename = filename
84	p.next()
85	return p
86}
87
88func (p *parser) Unpack(pos Pos) scanner.Position {
89	offset := int(pos)
90	line := sort.Search(len(p.lines), func(i int) bool { return p.lines[i] > offset }) - 1
91	return scanner.Position{
92		Filename: p.scanner.Filename,
93		Line:     line + 1,
94		Column:   offset - p.lines[line] + 1,
95		Offset:   offset,
96	}
97}
98
99func (p *parser) pos() Pos {
100	pos := p.scanner.Position
101	if !pos.IsValid() {
102		pos = p.scanner.Pos()
103	}
104	return Pos(pos.Offset)
105}
106
107func (p *parser) errorf(format string, args ...interface{}) {
108	err := &ParseError{
109		Err: fmt.Errorf(format, args...),
110		Pos: p.scanner.Position,
111	}
112	p.errors = append(p.errors, err)
113	if len(p.errors) >= maxErrors {
114		panic(errTooManyErrors)
115	}
116}
117
118func (p *parser) accept(toks ...rune) bool {
119	for _, tok := range toks {
120		if p.tok != tok {
121			p.errorf("expected %s, found %s", scanner.TokenString(tok),
122				scanner.TokenString(p.tok))
123			return false
124		}
125		p.next()
126	}
127	return true
128}
129
130func (p *parser) next() {
131	if p.tok != scanner.EOF {
132		p.tok = p.scanner.Scan()
133		for p.tok == '\r' {
134			p.tok = p.scanner.Scan()
135		}
136	}
137	if p.tok == '\n' {
138		p.lines = append(p.lines, p.scanner.Position.Offset+1)
139	}
140}
141
142func (p *parser) parseLines() {
143	for {
144		p.ignoreWhitespace()
145
146		if p.parseDirective() {
147			continue
148		}
149
150		ident := p.parseExpression('=', '?', ':', '#', '\n')
151
152		p.ignoreSpaces()
153
154		switch p.tok {
155		case '?':
156			p.accept('?')
157			if p.tok == '=' {
158				p.parseAssignment("?=", nil, ident)
159			} else {
160				p.errorf("expected = after ?")
161			}
162		case '+':
163			p.accept('+')
164			if p.tok == '=' {
165				p.parseAssignment("+=", nil, ident)
166			} else {
167				p.errorf("expected = after +")
168			}
169		case ':':
170			p.accept(':')
171			switch p.tok {
172			case '=':
173				p.parseAssignment(":=", nil, ident)
174			default:
175				p.parseRule(ident)
176			}
177		case '=':
178			p.parseAssignment("=", nil, ident)
179		case '#', '\n', scanner.EOF:
180			ident.TrimRightSpaces()
181			if v, ok := toVariable(ident); ok {
182				p.nodes = append(p.nodes, &v)
183			} else if !ident.Empty() {
184				p.errorf("expected directive, rule, or assignment after ident " + ident.Dump())
185			}
186			switch p.tok {
187			case scanner.EOF:
188				return
189			case '\n':
190				p.accept('\n')
191			case '#':
192				p.parseComment()
193			}
194		default:
195			p.errorf("expected assignment or rule definition, found %s\n",
196				p.scanner.TokenText())
197			return
198		}
199	}
200}
201
202func (p *parser) parseDirective() bool {
203	if p.tok != scanner.Ident || !isDirective(p.scanner.TokenText()) {
204		return false
205	}
206
207	d := p.scanner.TokenText()
208	pos := p.pos()
209	p.accept(scanner.Ident)
210	endPos := NoPos
211
212	expression := SimpleMakeString("", pos)
213
214	switch d {
215	case "endif", "endef":
216		// Nothing
217	case "else":
218		p.ignoreSpaces()
219		if p.tok != '\n' {
220			d = p.scanner.TokenText()
221			p.accept(scanner.Ident)
222			if d == "ifdef" || d == "ifndef" || d == "ifeq" || d == "ifneq" {
223				d = "el" + d
224				p.ignoreSpaces()
225				expression = p.parseExpression()
226			} else {
227				p.errorf("expected ifdef/ifndef/ifeq/ifneq, found %s", d)
228			}
229		}
230	case "define":
231		expression, endPos = p.parseDefine()
232	default:
233		p.ignoreSpaces()
234		expression = p.parseExpression()
235	}
236
237	p.nodes = append(p.nodes, &Directive{
238		NamePos: pos,
239		Name:    d,
240		Args:    expression,
241		EndPos:  endPos,
242	})
243	return true
244}
245
246func (p *parser) parseDefine() (*MakeString, Pos) {
247	value := SimpleMakeString("", p.pos())
248
249loop:
250	for {
251		switch p.tok {
252		case scanner.Ident:
253			value.appendString(p.scanner.TokenText())
254			if p.scanner.TokenText() == "endef" {
255				p.accept(scanner.Ident)
256				break loop
257			}
258			p.accept(scanner.Ident)
259		case '\\':
260			p.parseEscape()
261			switch p.tok {
262			case '\n':
263				value.appendString(" ")
264			case scanner.EOF:
265				p.errorf("expected escaped character, found %s",
266					scanner.TokenString(p.tok))
267				break loop
268			default:
269				value.appendString(`\` + string(p.tok))
270			}
271			p.accept(p.tok)
272		//TODO: handle variables inside defines?  result depends if
273		//define is used in make or rule context
274		//case '$':
275		//	variable := p.parseVariable()
276		//	value.appendVariable(variable)
277		case scanner.EOF:
278			p.errorf("unexpected EOF while looking for endef")
279			break loop
280		default:
281			value.appendString(p.scanner.TokenText())
282			p.accept(p.tok)
283		}
284	}
285
286	return value, p.pos()
287}
288
289func (p *parser) parseEscape() {
290	p.scanner.Mode = 0
291	p.accept('\\')
292	p.scanner.Mode = scanner.ScanIdents
293}
294
295func (p *parser) parseExpression(end ...rune) *MakeString {
296	value := SimpleMakeString("", p.pos())
297
298	endParen := false
299	for _, r := range end {
300		if r == ')' {
301			endParen = true
302		}
303	}
304	parens := 0
305
306loop:
307	for {
308		if endParen && parens > 0 && p.tok == ')' {
309			parens--
310			value.appendString(")")
311			p.accept(')')
312			continue
313		}
314
315		for _, r := range end {
316			if p.tok == r {
317				break loop
318			}
319		}
320
321		switch p.tok {
322		case '\n':
323			break loop
324		case scanner.Ident:
325			value.appendString(p.scanner.TokenText())
326			p.accept(scanner.Ident)
327		case '\\':
328			p.parseEscape()
329			switch p.tok {
330			case '\n':
331				value.appendString(" ")
332			case scanner.EOF:
333				p.errorf("expected escaped character, found %s",
334					scanner.TokenString(p.tok))
335				return value
336			default:
337				value.appendString(`\` + string(p.tok))
338			}
339			p.accept(p.tok)
340		case '#':
341			p.parseComment()
342			break loop
343		case '$':
344			var variable Variable
345			variable = p.parseVariable()
346			if variable.Name == builtinDollarName {
347				value.appendString("$")
348			} else {
349				value.appendVariable(variable)
350			}
351		case scanner.EOF:
352			break loop
353		case '(':
354			if endParen {
355				parens++
356			}
357			value.appendString("(")
358			p.accept('(')
359		default:
360			value.appendString(p.scanner.TokenText())
361			p.accept(p.tok)
362		}
363	}
364
365	if parens > 0 {
366		p.errorf("expected closing paren %s", value.Dump())
367	}
368	return value
369}
370
371func (p *parser) parseVariable() Variable {
372	pos := p.pos()
373	p.accept('$')
374	var name *MakeString
375	switch p.tok {
376	case '(':
377		return p.parseBracketedVariable('(', ')', pos)
378	case '{':
379		return p.parseBracketedVariable('{', '}', pos)
380	case '$':
381		name = builtinDollarName
382		p.accept(p.tok)
383	case scanner.EOF:
384		p.errorf("expected variable name, found %s",
385			scanner.TokenString(p.tok))
386	default:
387		name = p.parseExpression(variableNameEndRunes...)
388	}
389
390	return p.nameToVariable(name)
391}
392
393func (p *parser) parseBracketedVariable(start, end rune, pos Pos) Variable {
394	p.accept(start)
395	name := p.parseExpression(end)
396	p.accept(end)
397	return p.nameToVariable(name)
398}
399
400func (p *parser) nameToVariable(name *MakeString) Variable {
401	return Variable{
402		Name: name,
403	}
404}
405
406func (p *parser) parseRule(target *MakeString) {
407	prerequisites, newLine := p.parseRulePrerequisites(target)
408
409	recipe := ""
410	recipePos := p.pos()
411loop:
412	for {
413		if newLine {
414			if p.tok == '\t' {
415				p.accept('\t')
416				newLine = false
417				continue loop
418			} else if p.parseDirective() {
419				newLine = false
420				continue
421			} else {
422				break loop
423			}
424		}
425
426		newLine = false
427		switch p.tok {
428		case '\\':
429			p.parseEscape()
430			recipe += string(p.tok)
431			p.accept(p.tok)
432		case '\n':
433			newLine = true
434			recipe += "\n"
435			p.accept('\n')
436		case scanner.EOF:
437			break loop
438		default:
439			recipe += p.scanner.TokenText()
440			p.accept(p.tok)
441		}
442	}
443
444	if prerequisites != nil {
445		p.nodes = append(p.nodes, &Rule{
446			Target:        target,
447			Prerequisites: prerequisites,
448			Recipe:        recipe,
449			RecipePos:     recipePos,
450		})
451	}
452}
453
454func (p *parser) parseRulePrerequisites(target *MakeString) (*MakeString, bool) {
455	newLine := false
456
457	p.ignoreSpaces()
458
459	prerequisites := p.parseExpression('#', '\n', ';', ':', '=')
460
461	switch p.tok {
462	case '\n':
463		p.accept('\n')
464		newLine = true
465	case '#':
466		p.parseComment()
467		newLine = true
468	case ';':
469		p.accept(';')
470	case ':':
471		p.accept(':')
472		if p.tok == '=' {
473			p.parseAssignment(":=", target, prerequisites)
474			return nil, true
475		} else {
476			more := p.parseExpression('#', '\n', ';')
477			prerequisites.appendMakeString(more)
478		}
479	case '=':
480		p.parseAssignment("=", target, prerequisites)
481		return nil, true
482	case scanner.EOF:
483		// do nothing
484	default:
485		p.errorf("unexpected token %s after rule prerequisites", scanner.TokenString(p.tok))
486	}
487
488	return prerequisites, newLine
489}
490
491func (p *parser) parseComment() {
492	pos := p.pos()
493	p.accept('#')
494	comment := ""
495loop:
496	for {
497		switch p.tok {
498		case '\\':
499			p.parseEscape()
500			comment += "\\" + p.scanner.TokenText()
501			p.accept(p.tok)
502		case '\n':
503			p.accept('\n')
504			break loop
505		case scanner.EOF:
506			break loop
507		default:
508			comment += p.scanner.TokenText()
509			p.accept(p.tok)
510		}
511	}
512
513	p.comments = append(p.comments, &Comment{
514		CommentPos: pos,
515		Comment:    comment,
516	})
517}
518
519func (p *parser) parseAssignment(t string, target *MakeString, ident *MakeString) {
520	// The value of an assignment is everything including and after the first
521	// non-whitespace character after the = until the end of the logical line,
522	// which may included escaped newlines
523	p.accept('=')
524	value := p.parseExpression()
525	value.TrimLeftSpaces()
526	if ident.EndsWith('+') && t == "=" {
527		ident.TrimRightOne()
528		t = "+="
529	}
530
531	ident.TrimRightSpaces()
532
533	p.nodes = append(p.nodes, &Assignment{
534		Name:   ident,
535		Value:  value,
536		Target: target,
537		Type:   t,
538	})
539}
540
541type androidMkModule struct {
542	assignments map[string]string
543}
544
545type androidMkFile struct {
546	assignments map[string]string
547	modules     []androidMkModule
548	includes    []string
549}
550
551var directives = [...]string{
552	"define",
553	"else",
554	"endef",
555	"endif",
556	"export",
557	"ifdef",
558	"ifeq",
559	"ifndef",
560	"ifneq",
561	"include",
562	"-include",
563	"unexport",
564}
565
566var functions = [...]string{
567	"abspath",
568	"addprefix",
569	"addsuffix",
570	"basename",
571	"dir",
572	"notdir",
573	"subst",
574	"suffix",
575	"filter",
576	"filter-out",
577	"findstring",
578	"firstword",
579	"flavor",
580	"join",
581	"lastword",
582	"patsubst",
583	"realpath",
584	"shell",
585	"sort",
586	"strip",
587	"wildcard",
588	"word",
589	"wordlist",
590	"words",
591	"origin",
592	"foreach",
593	"call",
594	"info",
595	"error",
596	"warning",
597	"if",
598	"or",
599	"and",
600	"value",
601	"eval",
602	"file",
603}
604
605func init() {
606	sort.Strings(directives[:])
607	sort.Strings(functions[:])
608}
609
610func isDirective(s string) bool {
611	for _, d := range directives {
612		if s == d {
613			return true
614		} else if s < d {
615			return false
616		}
617	}
618	return false
619}
620
621func isFunctionName(s string) bool {
622	for _, f := range functions {
623		if s == f {
624			return true
625		} else if s < f {
626			return false
627		}
628	}
629	return false
630}
631
632func isWhitespace(ch rune) bool {
633	return ch == ' ' || ch == '\t' || ch == '\n'
634}
635
636func isValidVariableRune(ch rune) bool {
637	return ch != scanner.Ident && ch != ':' && ch != '=' && ch != '#'
638}
639
640var whitespaceRunes = []rune{' ', '\t', '\n'}
641var variableNameEndRunes = append([]rune{':', '=', '#', ')', '}'}, whitespaceRunes...)
642
643func (p *parser) ignoreSpaces() int {
644	skipped := 0
645	for p.tok == ' ' || p.tok == '\t' {
646		p.accept(p.tok)
647		skipped++
648	}
649	return skipped
650}
651
652func (p *parser) ignoreWhitespace() {
653	for isWhitespace(p.tok) {
654		p.accept(p.tok)
655	}
656}
657