bash - ast.go
1 // Package bash implements a bash tokeniser and AST.
2 package bash // import "vimagination.zapto.org/bash"
3
4 import (
5 "vimagination.zapto.org/parser"
6 )
7
8 // Parse parses Bash input into AST.
9 func Parse(t Tokeniser) (*File, error) {
10 p, err := newBashParser(t)
11 if err != nil {
12 return nil, err
13 }
14
15 f := new(File)
16 if err = f.parse(p); err != nil {
17 return nil, err
18 }
19
20 return f, nil
21 }
22
23 // Parse parses Bash input into AST.
24 type File struct {
25 Statements []Statement
26 Tokens Tokens
27 }
28
29 func (f *File) parse(p *bashParser) error {
30 q := p.NewGoal()
31
32 for q.AcceptRunAllWhitespace() != parser.TokenDone {
33 p.AcceptRunAllWhitespace()
34
35 q = p.NewGoal()
36
37 var s Statement
38
39 if err := s.parse(q, true); err != nil {
40 return p.Error("File", err)
41 }
42
43 f.Statements = append(f.Statements, s)
44
45 p.Score(q)
46
47 q = p.NewGoal()
48 }
49
50 f.Tokens = p.ToTokens()
51
52 return nil
53 }
54
55 type LogicalOperator uint8
56
57 const (
58 LogicalOperatorNone LogicalOperator = iota
59 LogicalOperatorAnd
60 LogicalOperatorOr
61 )
62
63 type JobControl uint8
64
65 const (
66 JobControlForeground JobControl = iota
67 JobControlBackground
68 )
69
70 type Statement struct {
71 Pipeline Pipeline
72 LogicalOperator LogicalOperator
73 LogicalExpression *Statement
74 JobControl JobControl
75 Tokens
76 }
77
78 func (s *Statement) parse(b *bashParser, first bool) error {
79 c := b.NewGoal()
80
81 if err := s.Pipeline.parse(c); err != nil {
82 return b.Error("Statement", err)
83 }
84
85 b.Score(c)
86
87 c = b.NewGoal()
88
89 c.AcceptRunWhitespace()
90
91 if c.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "&&"}) {
92 s.LogicalOperator = LogicalOperatorAnd
93 } else if c.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "||"}) {
94 s.LogicalOperator = LogicalOperatorOr
95 }
96
97 if s.LogicalOperator != LogicalOperatorNone {
98 c.AcceptRunWhitespace()
99 b.Score(c)
100
101 c = b.NewGoal()
102 s.LogicalExpression = new(Statement)
103
104 if err := s.LogicalExpression.parse(c, false); err != nil {
105 return b.Error("Statement", err)
106 }
107
108 b.Score(c)
109 }
110
111 if first {
112 c = b.NewGoal()
113
114 c.AcceptRunWhitespace()
115
116 if c.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "&"}) {
117 s.JobControl = JobControlBackground
118
119 b.Score(c)
120 } else if c.AcceptToken(parser.Token{Type: TokenPunctuator, Data: ";"}) {
121 b.Score(c)
122 } else if tk := c.Peek().Type; tk != TokenLineTerminator && tk != parser.TokenDone {
123 return c.Error("Statement", ErrInvalidEndOfStatement)
124 }
125 }
126
127 s.Tokens = b.ToTokens()
128
129 return nil
130 }
131
132 type PipelineTime uint8
133
134 const (
135 PipelineTimeNone PipelineTime = iota
136 PipelineTimeBash
137 PipelineTimePosix
138 )
139
140 type Pipeline struct {
141 PipelineTime
142 Not bool
143 Command Command
144 Pipeline *Pipeline
145 Tokens Tokens
146 }
147
148 func (p *Pipeline) parse(b *bashParser) error {
149 if b.AcceptToken(parser.Token{Type: TokenWord, Data: "time"}) {
150 b.AcceptRunWhitespace()
151
152 if b.AcceptToken(parser.Token{Type: TokenWord, Data: "-p"}) {
153 p.PipelineTime = PipelineTimePosix
154 } else {
155 p.PipelineTime = PipelineTimeBash
156 }
157
158 b.AcceptRunWhitespace()
159 }
160
161 if p.Not = b.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "!"}); p.Not {
162 b.AcceptRunWhitespace()
163 }
164
165 c := b.NewGoal()
166
167 if err := p.Command.parse(c); err != nil {
168 return b.Error("Pipeline", err)
169 }
170
171 b.Score(c)
172
173 c = b.NewGoal()
174
175 c.AcceptRunWhitespace()
176
177 if c.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "|"}) {
178 c.AcceptRunWhitespace()
179 b.Score(c)
180
181 c = b.NewGoal()
182 p.Pipeline = new(Pipeline)
183
184 if err := p.Pipeline.parse(c); err != nil {
185 return b.Error("Pipeline", err)
186 }
187
188 b.Score(c)
189 }
190
191 p.Tokens = b.ToTokens()
192
193 return nil
194 }
195
196 type Command struct {
197 Vars []Assignment
198 Redirections []Redirection
199 Words []Word
200 Tokens Tokens
201 }
202
203 func (c *Command) parse(b *bashParser) error {
204 for {
205 d := b.NewGoal()
206
207 if b.Peek().Type == TokenIdentifierAssign {
208 var a Assignment
209
210 if err := a.parse(d); err != nil {
211 return b.Error("Command", err)
212 }
213
214 c.Vars = append(c.Vars, a)
215 } else if isRedirection(b) {
216 var r Redirection
217
218 if err := r.parse(d); err != nil {
219 return b.Error("Command", err)
220 }
221
222 c.Redirections = append(c.Redirections, r)
223 } else {
224 break
225 }
226
227 b.Score(d)
228 b.AcceptRunWhitespace()
229 }
230
231 for nextIsWordPart(b) {
232 d := b.NewGoal()
233
234 if isRedirection(b) {
235 var r Redirection
236
237 if err := r.parse(d); err != nil {
238 return b.Error("Command", err)
239 }
240
241 c.Redirections = append(c.Redirections, r)
242 } else {
243 var w Word
244
245 if err := w.parse(d); err != nil {
246 return b.Error("Command", err)
247 }
248
249 c.Words = append(c.Words, w)
250 }
251
252 b.Score(d)
253 }
254
255 c.Tokens = b.ToTokens()
256
257 return nil
258 }
259
260 func isRedirection(b *bashParser) bool {
261 c := b.NewGoal()
262
263 if c.Accept(TokenNumberLiteral, TokenBraceWord) {
264 if c.Accept(TokenPunctuator) {
265 switch c.GetLastToken().Data {
266 case "<", ">", ">|", ">>", "<<", "<<-", "<<<", "<&", ">&", "<>":
267 return true
268 }
269 }
270 } else if c.Accept(TokenPunctuator) {
271 switch c.GetLastToken().Data {
272 case "<", ">", ">|", ">>", "<<", "<<-", "<<<", "<&", ">&", "<>", "&>", "&>>":
273 return true
274 }
275 }
276
277 return false
278 }
279
280 type AssignmentType uint8
281
282 const (
283 AssignmentAssign AssignmentType = iota
284 AssignmentAppend
285 )
286
287 type Assignment struct {
288 Identifier Paramater
289 Assignment AssignmentType
290 Value Value
291 Tokens Tokens
292 }
293
294 func (a *Assignment) parse(b *bashParser) error {
295 c := b.NewGoal()
296
297 if err := a.Identifier.parse(c); err != nil {
298 return b.Error("Assignment", err)
299 }
300
301 b.Score(c)
302
303 if b.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "="}) {
304 a.Assignment = AssignmentAssign
305 } else if b.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "+="}) {
306 a.Assignment = AssignmentAppend
307 } else {
308 return b.Error("Assignment", ErrInvalidAssignment)
309 }
310
311 c = b.NewGoal()
312
313 if err := a.Value.parse(c); err != nil {
314 return b.Error("Assignment", err)
315 }
316
317 b.Score(c)
318
319 a.Tokens = b.ToTokens()
320
321 return nil
322 }
323
324 type Paramater struct {
325 Identifier *Token
326 Subscript *Word
327 Tokens Tokens
328 }
329
330 func (p *Paramater) parse(b *bashParser) error {
331 b.Next()
332
333 p.Identifier = b.GetLastToken()
334
335 if b.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "["}) {
336 b.AcceptRunAllWhitespace()
337
338 c := b.NewGoal()
339 p.Subscript = new(Word)
340
341 if err := p.Subscript.parse(c); err != nil {
342 return b.Error("Parameter", err)
343 }
344
345 b.Score(c)
346 b.AcceptRunAllWhitespace()
347
348 if b.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "]"}) {
349 return b.Error("Parameter", ErrMissingClosingBracket)
350 }
351 }
352
353 p.Tokens = b.ToTokens()
354
355 return nil
356 }
357
358 type Value struct {
359 Word *Word
360 Array []Word
361 Tokens Tokens
362 }
363
364 func (v *Value) parse(b *bashParser) error {
365 if b.AcceptToken(parser.Token{Type: TokenPunctuator, Data: "("}) {
366 b.AcceptRunAllWhitespace()
367
368 for b.AcceptToken(parser.Token{Type: TokenPunctuator, Data: ")"}) {
369 c := b.NewGoal()
370
371 var w Word
372
373 if err := w.parse(c); err != nil {
374 return b.Error("Value", err)
375 }
376
377 b.Score(c)
378 b.AcceptRunAllWhitespace()
379 }
380 } else {
381 c := b.NewGoal()
382 v.Word = new(Word)
383
384 if err := v.Word.parse(c); err != nil {
385 return b.Error("Value", err)
386 }
387
388 b.Score(c)
389 }
390
391 v.Tokens = b.ToTokens()
392
393 return nil
394 }
395
396 type Word struct {
397 Parts []WordPart
398 Tokens Tokens
399 }
400
401 func (w *Word) parse(b *bashParser) error {
402 for nextIsWordPart(b) {
403 c := b.NewGoal()
404
405 var wp WordPart
406
407 if err := wp.parse(c); err != nil {
408 return b.Error("Word", err)
409 }
410
411 w.Parts = append(w.Parts, wp)
412
413 b.Score(b)
414 }
415
416 w.Tokens = b.ToTokens()
417
418 return nil
419 }
420
421 func nextIsWordPart(b *bashParser) bool {
422 switch tk := b.Peek(); tk.Type {
423 case TokenWhitespace, TokenLineTerminator, TokenComment:
424 return false
425 case TokenPunctuator:
426 switch tk.Data {
427 case "$(", "${", "`":
428 return true
429 }
430
431 return false
432 }
433
434 return true
435 }
436
437 type WordPart struct {
438 Part *Token
439 Parameter *Parameter
440 CommandSubstitution *CommandSubstitution
441 ArithmeticExpansion *ArithmeticExpansion
442 Tokens Tokens
443 }
444
445 func (w *WordPart) parse(b *bashParser) error {
446 c := b.NewGoal()
447
448 switch tk := b.Peek(); {
449 case tk == parser.Token{Type: TokenPunctuator, Data: "${"}:
450 w.Parameter = new(Parameter)
451
452 if err := w.Parameter.parse(c); err != nil {
453 return b.Error("WordPart", err)
454 }
455 case tk == parser.Token{Type: TokenPunctuator, Data: "$("}:
456 w.ArithmeticExpansion = new(ArithmeticExpansion)
457
458 if err := w.ArithmeticExpansion.parse(c); err != nil {
459 return b.Error("WordPart", err)
460 }
461 case tk == parser.Token{Type: TokenPunctuator, Data: "$("}, tk.Type == TokenOpenBacktick:
462 w.CommandSubstitution = new(CommandSubstitution)
463
464 if err := w.CommandSubstitution.parse(c); err != nil {
465 return b.Error("WordPart", err)
466 }
467 default:
468 b.Next()
469
470 w.Part = b.GetLastToken()
471 }
472
473 b.Score(c)
474
475 w.Tokens = b.ToTokens()
476
477 return nil
478 }
479
480 type Parameter struct{}
481
482 func (p *Parameter) parse(b *bashParser) error {
483 return nil
484 }
485
486 type SubstitutionType uint8
487
488 const (
489 SubstitutionNew SubstitutionType = iota
490 SubstitutionBacktick
491 )
492
493 type CommandSubstitution struct {
494 SubstitutionType SubstitutionType
495 Command File
496 Tokens Tokens
497 }
498
499 func (cs *CommandSubstitution) parse(b *bashParser) error {
500 end := parser.Token{Type: TokenPunctuator, Data: ")"}
501
502 if tk := b.Next(); tk.Type != TokenOpenBacktick {
503 cs.SubstitutionType = SubstitutionBacktick
504 end = parser.Token{Type: TokenCloseBacktick, Data: tk.Data}
505 }
506
507 b.AcceptRunWhitespace()
508
509 c := b.NewGoal()
510 c.StopAt = &end
511
512 if err := cs.Command.parse(c); err != nil {
513 return err
514 }
515
516 b.Score(c)
517
518 cs.Tokens = b.ToTokens()
519
520 return nil
521 }
522
523 type Redirection struct {
524 Input *Token
525 Redirector *Token
526 Output Word
527 Tokens Tokens
528 }
529
530 func (r *Redirection) parse(b *bashParser) error {
531 if b.Accept(TokenNumberLiteral, TokenBraceWord) {
532 r.Input = b.GetLastToken()
533 }
534
535 b.Accept(TokenPunctuator)
536
537 r.Redirector = b.GetLastToken()
538
539 b.AcceptRunWhitespace()
540
541 c := b.NewGoal()
542
543 if err := r.Output.parse(c); err != nil {
544 return b.Error("Redirection", err)
545 }
546
547 b.Score(c)
548
549 r.Tokens = b.ToTokens()
550
551 return nil
552 }
553
554 func (r *Redirection) isHeredoc() bool {
555 return r.Redirector != nil && (r.Redirector.Data == "<<" || r.Redirector.Data == "<<-")
556 }
557
558 type ArithmeticExpansion struct{}
559
560 func (a *ArithmeticExpansion) parse(b *bashParser) error {
561 return nil
562 }
563