parser.go 12 KB

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