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