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