• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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' && p.tok != '#' {
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				expression.TrimRightSpaces()
227			} else {
228				p.errorf("expected ifdef/ifndef/ifeq/ifneq, found %s", d)
229			}
230		}
231	case "define":
232		expression, endPos = p.parseDefine()
233	default:
234		p.ignoreSpaces()
235		expression = p.parseExpression('#')
236	}
237
238	p.nodes = append(p.nodes, &Directive{
239		NamePos: pos,
240		Name:    d,
241		Args:    expression,
242		EndPos:  endPos,
243	})
244	return true
245}
246
247func (p *parser) parseDefine() (*MakeString, Pos) {
248	value := SimpleMakeString("", p.pos())
249
250loop:
251	for {
252		switch p.tok {
253		case scanner.Ident:
254			value.appendString(p.scanner.TokenText())
255			if p.scanner.TokenText() == "endef" {
256				p.accept(scanner.Ident)
257				break loop
258			}
259			p.accept(scanner.Ident)
260		case '\\':
261			p.parseEscape()
262			switch p.tok {
263			case '\n':
264				value.appendString(" ")
265			case scanner.EOF:
266				p.errorf("expected escaped character, found %s",
267					scanner.TokenString(p.tok))
268				break loop
269			default:
270				value.appendString(`\` + string(p.tok))
271			}
272			p.accept(p.tok)
273		//TODO: handle variables inside defines?  result depends if
274		//define is used in make or rule context
275		//case '$':
276		//	variable := p.parseVariable()
277		//	value.appendVariable(variable)
278		case scanner.EOF:
279			p.errorf("unexpected EOF while looking for endef")
280			break loop
281		default:
282			value.appendString(p.scanner.TokenText())
283			p.accept(p.tok)
284		}
285	}
286
287	return value, p.pos()
288}
289
290func (p *parser) parseEscape() {
291	p.scanner.Mode = 0
292	p.accept('\\')
293	p.scanner.Mode = scanner.ScanIdents
294}
295
296func (p *parser) parseExpression(end ...rune) *MakeString {
297	value := SimpleMakeString("", p.pos())
298
299	endParen := false
300	for _, r := range end {
301		if r == ')' {
302			endParen = true
303		}
304	}
305	parens := 0
306
307loop:
308	for {
309		if endParen && parens > 0 && p.tok == ')' {
310			parens--
311			value.appendString(")")
312			p.accept(')')
313			continue
314		}
315
316		for _, r := range end {
317			if p.tok == r {
318				break loop
319			}
320		}
321
322		switch p.tok {
323		case '\n':
324			break loop
325		case scanner.Ident:
326			value.appendString(p.scanner.TokenText())
327			p.accept(scanner.Ident)
328		case '\\':
329			p.parseEscape()
330			switch p.tok {
331			case '\n':
332				value.appendString(" ")
333			case scanner.EOF:
334				p.errorf("expected escaped character, found %s",
335					scanner.TokenString(p.tok))
336				return value
337			default:
338				value.appendString(`\` + string(p.tok))
339			}
340			p.accept(p.tok)
341		case '$':
342			var variable Variable
343			variable = p.parseVariable()
344			if variable.Name == builtinDollarName {
345				value.appendString("$")
346			} else {
347				value.appendVariable(variable)
348			}
349		case scanner.EOF:
350			break loop
351		case '(':
352			if endParen {
353				parens++
354			}
355			value.appendString("(")
356			p.accept('(')
357		default:
358			value.appendString(p.scanner.TokenText())
359			p.accept(p.tok)
360		}
361	}
362
363	if parens > 0 {
364		p.errorf("expected closing paren %s", value.Dump())
365	}
366	return value
367}
368
369func (p *parser) parseVariable() Variable {
370	pos := p.pos()
371	p.accept('$')
372	var name *MakeString
373	switch p.tok {
374	case '(':
375		return p.parseBracketedVariable('(', ')', pos)
376	case '{':
377		return p.parseBracketedVariable('{', '}', pos)
378	case '$':
379		name = builtinDollarName
380		p.accept(p.tok)
381	case scanner.EOF:
382		p.errorf("expected variable name, found %s",
383			scanner.TokenString(p.tok))
384	default:
385		name = p.parseExpression(variableNameEndRunes...)
386	}
387
388	return p.nameToVariable(name)
389}
390
391func (p *parser) parseBracketedVariable(start, end rune, pos Pos) Variable {
392	p.accept(start)
393	name := p.parseExpression(end)
394	p.accept(end)
395	return p.nameToVariable(name)
396}
397
398func (p *parser) nameToVariable(name *MakeString) Variable {
399	return Variable{
400		Name: name,
401	}
402}
403
404func (p *parser) parseRule(target *MakeString) {
405	prerequisites, newLine := p.parseRulePrerequisites(target)
406
407	recipe := ""
408	recipePos := p.pos()
409loop:
410	for {
411		if newLine {
412			if p.tok == '\t' {
413				p.accept('\t')
414				newLine = false
415				continue loop
416			} else if p.parseDirective() {
417				newLine = false
418				continue
419			} else {
420				break loop
421			}
422		}
423
424		newLine = false
425		switch p.tok {
426		case '\\':
427			p.parseEscape()
428			recipe += string(p.tok)
429			p.accept(p.tok)
430		case '\n':
431			newLine = true
432			recipe += "\n"
433			p.accept('\n')
434		case scanner.EOF:
435			break loop
436		default:
437			recipe += p.scanner.TokenText()
438			p.accept(p.tok)
439		}
440	}
441
442	if prerequisites != nil {
443		p.nodes = append(p.nodes, &Rule{
444			Target:        target,
445			Prerequisites: prerequisites,
446			Recipe:        recipe,
447			RecipePos:     recipePos,
448		})
449	}
450}
451
452func (p *parser) parseRulePrerequisites(target *MakeString) (*MakeString, bool) {
453	newLine := false
454
455	p.ignoreSpaces()
456
457	prerequisites := p.parseExpression('#', '\n', ';', ':', '=')
458
459	switch p.tok {
460	case '\n':
461		p.accept('\n')
462		newLine = true
463	case '#':
464		p.parseComment()
465		newLine = true
466	case ';':
467		p.accept(';')
468	case ':':
469		p.accept(':')
470		if p.tok == '=' {
471			p.parseAssignment(":=", target, prerequisites)
472			return nil, true
473		} else {
474			more := p.parseExpression('#', '\n', ';')
475			prerequisites.appendMakeString(more)
476		}
477	case '=':
478		p.parseAssignment("=", target, prerequisites)
479		return nil, true
480	case scanner.EOF:
481		// do nothing
482	default:
483		p.errorf("unexpected token %s after rule prerequisites", scanner.TokenString(p.tok))
484	}
485
486	return prerequisites, newLine
487}
488
489func (p *parser) parseComment() {
490	pos := p.pos()
491	p.accept('#')
492	comment := ""
493loop:
494	for {
495		switch p.tok {
496		case '\\':
497			p.parseEscape()
498			comment += "\\" + p.scanner.TokenText()
499			p.accept(p.tok)
500		case '\n':
501			p.accept('\n')
502			break loop
503		case scanner.EOF:
504			break loop
505		default:
506			comment += p.scanner.TokenText()
507			p.accept(p.tok)
508		}
509	}
510
511	p.comments = append(p.comments, &Comment{
512		CommentPos: pos,
513		Comment:    comment,
514	})
515}
516
517func (p *parser) parseAssignment(t string, target *MakeString, ident *MakeString) {
518	// The value of an assignment is everything including and after the first
519	// non-whitespace character after the = until the end of the logical line,
520	// which may included escaped newlines
521	p.accept('=')
522	value := p.parseExpression('#')
523	value.TrimLeftSpaces()
524	if ident.EndsWith('+') && t == "=" {
525		ident.TrimRightOne()
526		t = "+="
527	}
528
529	ident.TrimRightSpaces()
530
531	p.nodes = append(p.nodes, &Assignment{
532		Name:   ident,
533		Value:  value,
534		Target: target,
535		Type:   t,
536	})
537}
538
539type androidMkModule struct {
540	assignments map[string]string
541}
542
543type androidMkFile struct {
544	assignments map[string]string
545	modules     []androidMkModule
546	includes    []string
547}
548
549var directives = [...]string{
550	"define",
551	"else",
552	"endef",
553	"endif",
554	"export",
555	"ifdef",
556	"ifeq",
557	"ifndef",
558	"ifneq",
559	"include",
560	"-include",
561	"unexport",
562}
563
564var functions = [...]string{
565	"abspath",
566	"addprefix",
567	"addsuffix",
568	"basename",
569	"dir",
570	"notdir",
571	"subst",
572	"suffix",
573	"filter",
574	"filter-out",
575	"findstring",
576	"firstword",
577	"flavor",
578	"join",
579	"lastword",
580	"patsubst",
581	"realpath",
582	"shell",
583	"sort",
584	"strip",
585	"wildcard",
586	"word",
587	"wordlist",
588	"words",
589	"origin",
590	"foreach",
591	"call",
592	"info",
593	"error",
594	"warning",
595	"if",
596	"or",
597	"and",
598	"value",
599	"eval",
600	"file",
601}
602
603func init() {
604	sort.Strings(directives[:])
605	sort.Strings(functions[:])
606}
607
608func isDirective(s string) bool {
609	for _, d := range directives {
610		if s == d {
611			return true
612		} else if s < d {
613			return false
614		}
615	}
616	return false
617}
618
619func isFunctionName(s string) bool {
620	for _, f := range functions {
621		if s == f {
622			return true
623		} else if s < f {
624			return false
625		}
626	}
627	return false
628}
629
630func isWhitespace(ch rune) bool {
631	return ch == ' ' || ch == '\t' || ch == '\n'
632}
633
634func isValidVariableRune(ch rune) bool {
635	return ch != scanner.Ident && ch != ':' && ch != '=' && ch != '#'
636}
637
638var whitespaceRunes = []rune{' ', '\t', '\n'}
639var variableNameEndRunes = append([]rune{':', '=', '#', ')', '}'}, whitespaceRunes...)
640
641func (p *parser) ignoreSpaces() int {
642	skipped := 0
643	for p.tok == ' ' || p.tok == '\t' {
644		p.accept(p.tok)
645		skipped++
646	}
647	return skipped
648}
649
650func (p *parser) ignoreWhitespace() {
651	for isWhitespace(p.tok) {
652		p.accept(p.tok)
653	}
654}
655