androidmk/parser/parser.go - platform/build/soong - Git at Google

 // Copyright 2017 Google Inc. All rights reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 package parser

 import (
 	"errors"
 	"fmt"
 	"io"
 	"sort"
 	"text/scanner"
 )

 var errTooManyErrors = errors.New("too many errors")

 const maxErrors = 100

 type ParseError struct {
 	Err error
 	Pos scanner.Position
 }

 func (e *ParseError) Error() string {
 	return fmt.Sprintf("%s: %s", e.Pos, e.Err)
 }

 const builtinDollar = "__builtin_dollar"

 var builtinDollarName = SimpleMakeString(builtinDollar, NoPos)

 func (p *parser) Parse() ([]Node, []error) {
 	defer func() {
 		if r := recover(); r != nil {
 			if r == errTooManyErrors {
 				return
 			}
 			panic(r)
 		}
 	}()

 	p.parseLines()
 	p.accept(scanner.EOF)
 	p.nodes = append(p.nodes, p.comments...)
 	sort.Sort(byPosition(p.nodes))

 	return p.nodes, p.errors
 }

 type parser struct {
 	scanner  scanner.Scanner
 	tok      rune
 	errors   []error
 	comments []Node
 	nodes    []Node
 	lines    []int
 }

 func NewParser(filename string, r io.Reader) *parser {
 	p := &parser{}
 	p.lines = []int{0}
 	p.scanner.Init(r)
 	p.scanner.Error = func(sc *scanner.Scanner, msg string) {
 		p.errorf(msg)
 	}
 	p.scanner.Whitespace = 0
 	p.scanner.IsIdentRune = func(ch rune, i int) bool {
 		return ch > 0 && ch != ':' && ch != '#' && ch != '=' && ch != '+' && ch != '$' &&
 			ch != '\\' && ch != '(' && ch != ')' && ch != '{' && ch != '}' && ch != ';' &&
 			ch != '|' && ch != '?' && ch != '\r' && !isWhitespace(ch)
 	}
 	p.scanner.Mode = scanner.ScanIdents
 	p.scanner.Filename = filename
 	p.next()
 	return p
 }

 func (p *parser) Unpack(pos Pos) scanner.Position {
 	offset := int(pos)
 	line := sort.Search(len(p.lines), func(i int) bool { return p.lines[i] > offset }) - 1
 	return scanner.Position{
 		Filename: p.scanner.Filename,
 		Line:     line + 1,
 		Column:   offset - p.lines[line] + 1,
 		Offset:   offset,
 	}
 }

 func (p *parser) pos() Pos {
 	pos := p.scanner.Position
 	if !pos.IsValid() {
 		pos = p.scanner.Pos()
 	}
 	return Pos(pos.Offset)
 }

 func (p *parser) errorf(format string, args ...interface{}) {
 	err := &ParseError{
 		Err: fmt.Errorf(format, args...),
 		Pos: p.scanner.Position,
 	}
 	p.errors = append(p.errors, err)
 	if len(p.errors) >= maxErrors {
 		panic(errTooManyErrors)
 	}
 }

 func (p *parser) accept(toks ...rune) bool {
 	for _, tok := range toks {
 		if p.tok != tok {
 			p.errorf("expected %s, found %s", scanner.TokenString(tok),
 				scanner.TokenString(p.tok))
 			return false
 		}
 		p.next()
 	}
 	return true
 }

 func (p *parser) next() {
 	if p.tok != scanner.EOF {
 		p.tok = p.scanner.Scan()
 		for p.tok == '\r' {
 			p.tok = p.scanner.Scan()
 		}
 	}
 	if p.tok == '\n' {
 		p.lines = append(p.lines, p.scanner.Position.Offset+1)
 	}
 }

 func (p *parser) parseLines() {
 	for {
 		p.ignoreWhitespace()

 		if p.parseDirective() {
 			continue
 		}

 		ident := p.parseExpression('=', '?', ':', '#', '\n')

 		p.ignoreSpaces()

 		switch p.tok {
 		case '?':
 			p.accept('?')
 			if p.tok == '=' {
 				p.parseAssignment("?=", nil, ident)
 			} else {
 				p.errorf("expected = after ?")
 			}
 		case '+':
 			p.accept('+')
 			if p.tok == '=' {
 				p.parseAssignment("+=", nil, ident)
 			} else {
 				p.errorf("expected = after +")
 			}
 		case ':':
 			p.accept(':')
 			switch p.tok {
 			case '=':
 				p.parseAssignment(":=", nil, ident)
 			default:
 				p.parseRule(ident)
 			}
 		case '=':
 			p.parseAssignment("=", nil, ident)
 		case '#', '\n', scanner.EOF:
 			ident.TrimRightSpaces()
 			if v, ok := toVariable(ident); ok {
 				p.nodes = append(p.nodes, &v)
 			} else if !ident.Empty() {
 				p.errorf("expected directive, rule, or assignment after ident " + ident.Dump())
 			}
 			switch p.tok {
 			case scanner.EOF:
 				return
 			case '\n':
 				p.accept('\n')
 			case '#':
 				p.parseComment()
 			}
 		default:
 			p.errorf("expected assignment or rule definition, found %s\n",
 				p.scanner.TokenText())
 			return
 		}
 	}
 }

 func (p *parser) parseDirective() bool {
 	if p.tok != scanner.Ident || !isDirective(p.scanner.TokenText()) {
 		return false
 	}

 	d := p.scanner.TokenText()
 	pos := p.pos()
 	p.accept(scanner.Ident)
 	endPos := NoPos

 	expression := SimpleMakeString("", pos)

 	switch d {
 	case "endif", "endef":
 		// Nothing
 	case "else":
 		p.ignoreSpaces()
 		if p.tok != '\n' && p.tok != '#' {
 			d = p.scanner.TokenText()
 			p.accept(scanner.Ident)
 			if d == "ifdef" || d == "ifndef" || d == "ifeq" || d == "ifneq" {
 				d = "el" + d
 				p.ignoreSpaces()
 				expression = p.parseExpression()
 				expression.TrimRightSpaces()
 			} else {
 				p.errorf("expected ifdef/ifndef/ifeq/ifneq, found %s", d)
 			}
 		}
 	case "define":
 		expression, endPos = p.parseDefine()
 	default:
 		p.ignoreSpaces()
 		expression = p.parseExpression()
 	}

 	p.nodes = append(p.nodes, &Directive{
 		NamePos: pos,
 		Name:    d,
 		Args:    expression,
 		EndPos:  endPos,
 	})
 	return true
 }

 func (p *parser) parseDefine() (*MakeString, Pos) {
 	value := SimpleMakeString("", p.pos())

 loop:
 	for {
 		switch p.tok {
 		case scanner.Ident:
 			value.appendString(p.scanner.TokenText())
 			if p.scanner.TokenText() == "endef" {
 				p.accept(scanner.Ident)
 				break loop
 			}
 			p.accept(scanner.Ident)
 		case '\\':
 			p.parseEscape()
 			switch p.tok {
 			case '\n':
 				value.appendString(" ")
 			case scanner.EOF:
 				p.errorf("expected escaped character, found %s",
 					scanner.TokenString(p.tok))
 				break loop
 			default:
 				value.appendString(`\` + string(p.tok))
 			}
 			p.accept(p.tok)
 		//TODO: handle variables inside defines?  result depends if
 		//define is used in make or rule context
 		//case '$':
 		//	variable := p.parseVariable()
 		//	value.appendVariable(variable)
 		case scanner.EOF:
 			p.errorf("unexpected EOF while looking for endef")
 			break loop
 		default:
 			value.appendString(p.scanner.TokenText())
 			p.accept(p.tok)
 		}
 	}

 	return value, p.pos()
 }

 func (p *parser) parseEscape() {
 	p.scanner.Mode = 0
 	p.accept('\\')
 	p.scanner.Mode = scanner.ScanIdents
 }

 func (p *parser) parseExpression(end ...rune) *MakeString {
 	value := SimpleMakeString("", p.pos())

 	endParen := false
 	for _, r := range end {
 		if r == ')' {
 			endParen = true
 		}
 	}
 	parens := 0

 loop:
 	for {
 		if endParen && parens > 0 && p.tok == ')' {
 			parens--
 			value.appendString(")")
 			p.accept(')')
 			continue
 		}

 		for _, r := range end {
 			if p.tok == r {
 				break loop
 			}
 		}

 		switch p.tok {
 		case '\n':
 			break loop
 		case scanner.Ident:
 			value.appendString(p.scanner.TokenText())
 			p.accept(scanner.Ident)
 		case '\\':
 			p.parseEscape()
 			switch p.tok {
 			case '\n':
 				value.appendString(" ")
 			case scanner.EOF:
 				p.errorf("expected escaped character, found %s",
 					scanner.TokenString(p.tok))
 				return value
 			default:
 				value.appendString(`\` + string(p.tok))
 			}
 			p.accept(p.tok)
 		case '#':
 			p.parseComment()
 			break loop
 		case '$':
 			var variable Variable
 			variable = p.parseVariable()
 			if variable.Name == builtinDollarName {
 				value.appendString("$")
 			} else {
 				value.appendVariable(variable)
 			}
 		case scanner.EOF:
 			break loop
 		case '(':
 			if endParen {
 				parens++
 			}
 			value.appendString("(")
 			p.accept('(')
 		default:
 			value.appendString(p.scanner.TokenText())
 			p.accept(p.tok)
 		}
 	}

 	if parens > 0 {
 		p.errorf("expected closing paren %s", value.Dump())
 	}
 	return value
 }

 func (p *parser) parseVariable() Variable {
 	pos := p.pos()
 	p.accept('$')
 	var name *MakeString
 	switch p.tok {
 	case '(':
 		return p.parseBracketedVariable('(', ')', pos)
 	case '{':
 		return p.parseBracketedVariable('{', '}', pos)
 	case '$':
 		name = builtinDollarName
 		p.accept(p.tok)
 	case scanner.EOF:
 		p.errorf("expected variable name, found %s",
 			scanner.TokenString(p.tok))
 	default:
 		name = p.parseExpression(variableNameEndRunes...)
 	}

 	return p.nameToVariable(name)
 }

 func (p *parser) parseBracketedVariable(start, end rune, pos Pos) Variable {
 	p.accept(start)
 	name := p.parseExpression(end)
 	p.accept(end)
 	return p.nameToVariable(name)
 }

 func (p *parser) nameToVariable(name *MakeString) Variable {
 	return Variable{
 		Name: name,
 	}
 }

 func (p *parser) parseRule(target *MakeString) {
 	prerequisites, newLine := p.parseRulePrerequisites(target)

 	recipe := ""
 	recipePos := p.pos()
 loop:
 	for {
 		if newLine {
 			if p.tok == '\t' {
 				p.accept('\t')
 				newLine = false
 				continue loop
 			} else if p.parseDirective() {
 				newLine = false
 				continue
 			} else {
 				break loop
 			}
 		}

 		newLine = false
 		switch p.tok {
 		case '\\':
 			p.parseEscape()
 			recipe += string(p.tok)
 			p.accept(p.tok)
 		case '\n':
 			newLine = true
 			recipe += "\n"
 			p.accept('\n')
 		case scanner.EOF:
 			break loop
 		default:
 			recipe += p.scanner.TokenText()
 			p.accept(p.tok)
 		}
 	}

 	if prerequisites != nil {
 		p.nodes = append(p.nodes, &Rule{
 			Target:        target,
 			Prerequisites: prerequisites,
 			Recipe:        recipe,
 			RecipePos:     recipePos,
 		})
 	}
 }

 func (p *parser) parseRulePrerequisites(target *MakeString) (*MakeString, bool) {
 	newLine := false

 	p.ignoreSpaces()

 	prerequisites := p.parseExpression('#', '\n', ';', ':', '=')

 	switch p.tok {
 	case '\n':
 		p.accept('\n')
 		newLine = true
 	case '#':
 		p.parseComment()
 		newLine = true
 	case ';':
 		p.accept(';')
 	case ':':
 		p.accept(':')
 		if p.tok == '=' {
 			p.parseAssignment(":=", target, prerequisites)
 			return nil, true
 		} else {
 			more := p.parseExpression('#', '\n', ';')
 			prerequisites.appendMakeString(more)
 		}
 	case '=':
 		p.parseAssignment("=", target, prerequisites)
 		return nil, true
 	case scanner.EOF:
 		// do nothing
 	default:
 		p.errorf("unexpected token %s after rule prerequisites", scanner.TokenString(p.tok))
 	}

 	return prerequisites, newLine
 }

 func (p *parser) parseComment() {
 	pos := p.pos()
 	p.accept('#')
 	comment := ""
 loop:
 	for {
 		switch p.tok {
 		case '\\':
 			p.parseEscape()
 			comment += "\\" + p.scanner.TokenText()
 			p.accept(p.tok)
 		case '\n':
 			p.accept('\n')
 			break loop
 		case scanner.EOF:
 			break loop
 		default:
 			comment += p.scanner.TokenText()
 			p.accept(p.tok)
 		}
 	}

 	p.comments = append(p.comments, &Comment{
 		CommentPos: pos,
 		Comment:    comment,
 	})
 }

 func (p *parser) parseAssignment(t string, target *MakeString, ident *MakeString) {
 	// The value of an assignment is everything including and after the first
 	// non-whitespace character after the = until the end of the logical line,
 	// which may included escaped newlines
 	p.accept('=')
 	value := p.parseExpression()
 	value.TrimLeftSpaces()
 	if ident.EndsWith('+') && t == "=" {
 		ident.TrimRightOne()
 		t = "+="
 	}

 	ident.TrimRightSpaces()

 	p.nodes = append(p.nodes, &Assignment{
 		Name:   ident,
 		Value:  value,
 		Target: target,
 		Type:   t,
 	})
 }

 type androidMkModule struct {
 	assignments map[string]string
 }

 type androidMkFile struct {
 	assignments map[string]string
 	modules     []androidMkModule
 	includes    []string
 }

 var directives = [...]string{
 	"define",
 	"else",
 	"endef",
 	"endif",
 	"export",
 	"ifdef",
 	"ifeq",
 	"ifndef",
 	"ifneq",
 	"include",
 	"-include",
 	"unexport",
 }

 var functions = [...]string{
 	"abspath",
 	"addprefix",
 	"addsuffix",
 	"basename",
 	"dir",
 	"notdir",
 	"subst",
 	"suffix",
 	"filter",
 	"filter-out",
 	"findstring",
 	"firstword",
 	"flavor",
 	"join",
 	"lastword",
 	"patsubst",
 	"realpath",
 	"shell",
 	"sort",
 	"strip",
 	"wildcard",
 	"word",
 	"wordlist",
 	"words",
 	"origin",
 	"foreach",
 	"call",
 	"info",
 	"error",
 	"warning",
 	"if",
 	"or",
 	"and",
 	"value",
 	"eval",
 	"file",
 }

 func init() {
 	sort.Strings(directives[:])
 	sort.Strings(functions[:])
 }

 func isDirective(s string) bool {
 	for _, d := range directives {
 		if s == d {
 			return true
 		} else if s < d {
 			return false
 		}
 	}
 	return false
 }

 func isFunctionName(s string) bool {
 	for _, f := range functions {
 		if s == f {
 			return true
 		} else if s < f {
 			return false
 		}
 	}
 	return false
 }

 func isWhitespace(ch rune) bool {
 	return ch == ' ' || ch == '\t' || ch == '\n'
 }

 func isValidVariableRune(ch rune) bool {
 	return ch != scanner.Ident && ch != ':' && ch != '=' && ch != '#'
 }

 var whitespaceRunes = []rune{' ', '\t', '\n'}
 var variableNameEndRunes = append([]rune{':', '=', '#', ')', '}'}, whitespaceRunes...)

 func (p *parser) ignoreSpaces() int {
 	skipped := 0
 	for p.tok == ' ' || p.tok == '\t' {
 		p.accept(p.tok)
 		skipped++
 	}
 	return skipped
 }

 func (p *parser) ignoreWhitespace() {
 	for isWhitespace(p.tok) {
 		p.accept(p.tok)
 	}
 }
	// Copyright 2017 Google Inc. All rights reserved.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	package parser

	import (
	"errors"
	"fmt"
	"io"
	"sort"
	"text/scanner"
	)

	var errTooManyErrors = errors.New("too many errors")

	const maxErrors = 100

	type ParseError struct {
	Err error
	Pos scanner.Position
	}

	func (e *ParseError) Error() string {
	return fmt.Sprintf("%s: %s", e.Pos, e.Err)
	}

	const builtinDollar = "__builtin_dollar"

	var builtinDollarName = SimpleMakeString(builtinDollar, NoPos)

	func (p *parser) Parse() ([]Node, []error) {
	defer func() {
	if r := recover(); r != nil {
	if r == errTooManyErrors {
	return
	}
	panic(r)
	}
	}()

	p.parseLines()
	p.accept(scanner.EOF)
	p.nodes = append(p.nodes, p.comments...)
	sort.Sort(byPosition(p.nodes))

	return p.nodes, p.errors
	}

	type parser struct {
	scanner scanner.Scanner
	tok rune
	errors []error
	comments []Node
	nodes []Node
	lines []int
	}

	func NewParser(filename string, r io.Reader) *parser {
	p := &parser{}
	p.lines = []int{0}
	p.scanner.Init(r)
	p.scanner.Error = func(sc *scanner.Scanner, msg string) {
	p.errorf(msg)
	}
	p.scanner.Whitespace = 0
	p.scanner.IsIdentRune = func(ch rune, i int) bool {
	return ch > 0 && ch != ':' && ch != '#' && ch != '=' && ch != '+' && ch != '$' &&
	ch != '\\' && ch != '(' && ch != ')' && ch != '{' && ch != '}' && ch != ';' &&
	ch != '\|' && ch != '?' && ch != '\r' && !isWhitespace(ch)
	}
	p.scanner.Mode = scanner.ScanIdents
	p.scanner.Filename = filename
	p.next()
	return p
	}

	func (p *parser) Unpack(pos Pos) scanner.Position {
	offset := int(pos)
	line := sort.Search(len(p.lines), func(i int) bool { return p.lines[i] > offset }) - 1
	return scanner.Position{
	Filename: p.scanner.Filename,
	Line: line + 1,
	Column: offset - p.lines[line] + 1,
	Offset: offset,
	}
	}

	func (p *parser) pos() Pos {
	pos := p.scanner.Position
	if !pos.IsValid() {
	pos = p.scanner.Pos()
	}
	return Pos(pos.Offset)
	}

	func (p *parser) errorf(format string, args ...interface{}) {
	err := &ParseError{
	Err: fmt.Errorf(format, args...),
	Pos: p.scanner.Position,
	}
	p.errors = append(p.errors, err)
	if len(p.errors) >= maxErrors {
	panic(errTooManyErrors)
	}
	}

	func (p *parser) accept(toks ...rune) bool {
	for _, tok := range toks {
	if p.tok != tok {
	p.errorf("expected %s, found %s", scanner.TokenString(tok),
	scanner.TokenString(p.tok))
	return false
	}
	p.next()
	}
	return true
	}

	func (p *parser) next() {
	if p.tok != scanner.EOF {
	p.tok = p.scanner.Scan()
	for p.tok == '\r' {
	p.tok = p.scanner.Scan()
	}
	}
	if p.tok == '\n' {
	p.lines = append(p.lines, p.scanner.Position.Offset+1)
	}
	}

	func (p *parser) parseLines() {
	for {
	p.ignoreWhitespace()

	if p.parseDirective() {
	continue
	}

	ident := p.parseExpression('=', '?', ':', '#', '\n')

	p.ignoreSpaces()

	switch p.tok {
	case '?':
	p.accept('?')
	if p.tok == '=' {
	p.parseAssignment("?=", nil, ident)
	} else {
	p.errorf("expected = after ?")
	}
	case '+':
	p.accept('+')
	if p.tok == '=' {
	p.parseAssignment("+=", nil, ident)
	} else {
	p.errorf("expected = after +")
	}
	case ':':
	p.accept(':')
	switch p.tok {
	case '=':
	p.parseAssignment(":=", nil, ident)
	default:
	p.parseRule(ident)
	}
	case '=':
	p.parseAssignment("=", nil, ident)
	case '#', '\n', scanner.EOF:
	ident.TrimRightSpaces()
	if v, ok := toVariable(ident); ok {
	p.nodes = append(p.nodes, &v)
	} else if !ident.Empty() {
	p.errorf("expected directive, rule, or assignment after ident " + ident.Dump())
	}
	switch p.tok {
	case scanner.EOF:
	return
	case '\n':
	p.accept('\n')
	case '#':
	p.parseComment()
	}
	default:
	p.errorf("expected assignment or rule definition, found %s\n",
	p.scanner.TokenText())
	return
	}
	}
	}

	func (p *parser) parseDirective() bool {
	if p.tok != scanner.Ident \|\| !isDirective(p.scanner.TokenText()) {
	return false
	}

	d := p.scanner.TokenText()
	pos := p.pos()
	p.accept(scanner.Ident)
	endPos := NoPos

	expression := SimpleMakeString("", pos)

	switch d {
	case "endif", "endef":
	// Nothing
	case "else":
	p.ignoreSpaces()
	if p.tok != '\n' && p.tok != '#' {
	d = p.scanner.TokenText()
	p.accept(scanner.Ident)
	if d == "ifdef" \|\| d == "ifndef" \|\| d == "ifeq" \|\| d == "ifneq" {
	d = "el" + d
	p.ignoreSpaces()
	expression = p.parseExpression()
	expression.TrimRightSpaces()
	} else {
	p.errorf("expected ifdef/ifndef/ifeq/ifneq, found %s", d)
	}
	}
	case "define":
	expression, endPos = p.parseDefine()
	default:
	p.ignoreSpaces()
	expression = p.parseExpression()
	}

	p.nodes = append(p.nodes, &Directive{
	NamePos: pos,
	Name: d,
	Args: expression,
	EndPos: endPos,
	})
	return true
	}

	func (p parser) parseDefine() (MakeString, Pos) {
	value := SimpleMakeString("", p.pos())

	loop:
	for {
	switch p.tok {
	case scanner.Ident:
	value.appendString(p.scanner.TokenText())
	if p.scanner.TokenText() == "endef" {
	p.accept(scanner.Ident)
	break loop
	}
	p.accept(scanner.Ident)
	case '\\':
	p.parseEscape()
	switch p.tok {
	case '\n':
	value.appendString(" ")
	case scanner.EOF:
	p.errorf("expected escaped character, found %s",
	scanner.TokenString(p.tok))
	break loop
	default:
	value.appendString(`\` + string(p.tok))
	}
	p.accept(p.tok)
	//TODO: handle variables inside defines? result depends if
	//define is used in make or rule context
	//case '$':
	// variable := p.parseVariable()
	// value.appendVariable(variable)
	case scanner.EOF:
	p.errorf("unexpected EOF while looking for endef")
	break loop
	default:
	value.appendString(p.scanner.TokenText())
	p.accept(p.tok)
	}
	}

	return value, p.pos()
	}

	func (p *parser) parseEscape() {
	p.scanner.Mode = 0
	p.accept('\\')
	p.scanner.Mode = scanner.ScanIdents
	}

	func (p parser) parseExpression(end ...rune) MakeString {
	value := SimpleMakeString("", p.pos())

	endParen := false
	for _, r := range end {
	if r == ')' {
	endParen = true
	}
	}
	parens := 0

	loop:
	for {
	if endParen && parens > 0 && p.tok == ')' {
	parens--
	value.appendString(")")
	p.accept(')')
	continue
	}

	for _, r := range end {
	if p.tok == r {
	break loop
	}
	}

	switch p.tok {
	case '\n':
	break loop
	case scanner.Ident:
	value.appendString(p.scanner.TokenText())
	p.accept(scanner.Ident)
	case '\\':
	p.parseEscape()
	switch p.tok {
	case '\n':
	value.appendString(" ")
	case scanner.EOF:
	p.errorf("expected escaped character, found %s",
	scanner.TokenString(p.tok))
	return value
	default:
	value.appendString(`\` + string(p.tok))
	}
	p.accept(p.tok)
	case '#':
	p.parseComment()
	break loop
	case '$':
	var variable Variable
	variable = p.parseVariable()
	if variable.Name == builtinDollarName {
	value.appendString("$")
	} else {
	value.appendVariable(variable)
	}
	case scanner.EOF:
	break loop
	case '(':
	if endParen {
	parens++
	}
	value.appendString("(")
	p.accept('(')
	default:
	value.appendString(p.scanner.TokenText())
	p.accept(p.tok)
	}
	}

	if parens > 0 {
	p.errorf("expected closing paren %s", value.Dump())
	}
	return value
	}

	func (p *parser) parseVariable() Variable {
	pos := p.pos()
	p.accept('$')
	var name *MakeString
	switch p.tok {
	case '(':
	return p.parseBracketedVariable('(', ')', pos)
	case '{':
	return p.parseBracketedVariable('{', '}', pos)
	case '$':
	name = builtinDollarName
	p.accept(p.tok)
	case scanner.EOF:
	p.errorf("expected variable name, found %s",
	scanner.TokenString(p.tok))
	default:
	name = p.parseExpression(variableNameEndRunes...)
	}

	return p.nameToVariable(name)
	}

	func (p *parser) parseBracketedVariable(start, end rune, pos Pos) Variable {
	p.accept(start)
	name := p.parseExpression(end)
	p.accept(end)
	return p.nameToVariable(name)
	}

	func (p parser) nameToVariable(name MakeString) Variable {
	return Variable{
	Name: name,
	}
	}

	func (p parser) parseRule(target MakeString) {
	prerequisites, newLine := p.parseRulePrerequisites(target)

	recipe := ""
	recipePos := p.pos()
	loop:
	for {
	if newLine {
	if p.tok == '\t' {
	p.accept('\t')
	newLine = false
	continue loop
	} else if p.parseDirective() {
	newLine = false
	continue
	} else {
	break loop
	}
	}

	newLine = false
	switch p.tok {
	case '\\':
	p.parseEscape()
	recipe += string(p.tok)
	p.accept(p.tok)
	case '\n':
	newLine = true
	recipe += "\n"
	p.accept('\n')
	case scanner.EOF:
	break loop
	default:
	recipe += p.scanner.TokenText()
	p.accept(p.tok)
	}
	}

	if prerequisites != nil {
	p.nodes = append(p.nodes, &Rule{
	Target: target,
	Prerequisites: prerequisites,
	Recipe: recipe,
	RecipePos: recipePos,
	})
	}
	}

	func (p parser) parseRulePrerequisites(target MakeString) (*MakeString, bool) {
	newLine := false

	p.ignoreSpaces()

	prerequisites := p.parseExpression('#', '\n', ';', ':', '=')

	switch p.tok {
	case '\n':
	p.accept('\n')
	newLine = true
	case '#':
	p.parseComment()
	newLine = true
	case ';':
	p.accept(';')
	case ':':
	p.accept(':')
	if p.tok == '=' {
	p.parseAssignment(":=", target, prerequisites)
	return nil, true
	} else {
	more := p.parseExpression('#', '\n', ';')
	prerequisites.appendMakeString(more)
	}
	case '=':
	p.parseAssignment("=", target, prerequisites)
	return nil, true
	case scanner.EOF:
	// do nothing
	default:
	p.errorf("unexpected token %s after rule prerequisites", scanner.TokenString(p.tok))
	}

	return prerequisites, newLine
	}

	func (p *parser) parseComment() {
	pos := p.pos()
	p.accept('#')
	comment := ""
	loop:
	for {
	switch p.tok {
	case '\\':
	p.parseEscape()
	comment += "\\" + p.scanner.TokenText()
	p.accept(p.tok)
	case '\n':
	p.accept('\n')
	break loop
	case scanner.EOF:
	break loop
	default:
	comment += p.scanner.TokenText()
	p.accept(p.tok)
	}
	}

	p.comments = append(p.comments, &Comment{
	CommentPos: pos,
	Comment: comment,
	})
	}

	func (p parser) parseAssignment(t string, target MakeString, ident *MakeString) {
	// The value of an assignment is everything including and after the first
	// non-whitespace character after the = until the end of the logical line,
	// which may included escaped newlines
	p.accept('=')
	value := p.parseExpression()
	value.TrimLeftSpaces()
	if ident.EndsWith('+') && t == "=" {
	ident.TrimRightOne()
	t = "+="
	}

	ident.TrimRightSpaces()

	p.nodes = append(p.nodes, &Assignment{
	Name: ident,
	Value: value,
	Target: target,
	Type: t,
	})
	}

	type androidMkModule struct {
	assignments map[string]string
	}

	type androidMkFile struct {
	assignments map[string]string
	modules []androidMkModule
	includes []string
	}

	var directives = [...]string{
	"define",
	"else",
	"endef",
	"endif",
	"export",
	"ifdef",
	"ifeq",
	"ifndef",
	"ifneq",
	"include",
	"-include",
	"unexport",
	}

	var functions = [...]string{
	"abspath",
	"addprefix",
	"addsuffix",
	"basename",
	"dir",
	"notdir",
	"subst",
	"suffix",
	"filter",
	"filter-out",
	"findstring",
	"firstword",
	"flavor",
	"join",
	"lastword",
	"patsubst",
	"realpath",
	"shell",
	"sort",
	"strip",
	"wildcard",
	"word",
	"wordlist",
	"words",
	"origin",
	"foreach",
	"call",
	"info",
	"error",
	"warning",
	"if",
	"or",
	"and",
	"value",
	"eval",
	"file",
	}

	func init() {
	sort.Strings(directives[:])
	sort.Strings(functions[:])
	}

	func isDirective(s string) bool {
	for _, d := range directives {
	if s == d {
	return true
	} else if s < d {
	return false
	}
	}
	return false
	}

	func isFunctionName(s string) bool {
	for _, f := range functions {
	if s == f {
	return true
	} else if s < f {
	return false
	}
	}
	return false
	}

	func isWhitespace(ch rune) bool {
	return ch == ' ' \|\| ch == '\t' \|\| ch == '\n'
	}

	func isValidVariableRune(ch rune) bool {
	return ch != scanner.Ident && ch != ':' && ch != '=' && ch != '#'
	}

	var whitespaceRunes = []rune{' ', '\t', '\n'}
	var variableNameEndRunes = append([]rune{':', '=', '#', ')', '}'}, whitespaceRunes...)

	func (p *parser) ignoreSpaces() int {
	skipped := 0
	for p.tok == ' ' \|\| p.tok == '\t' {
	p.accept(p.tok)
	skipped++
	}
	return skipped
	}

	func (p *parser) ignoreWhitespace() {
	for isWhitespace(p.tok) {
	p.accept(p.tok)
	}
	}