1
2
3
4
5
6
7
8
9 package parse
10
11 import (
12 "bytes"
13 "fmt"
14 "runtime"
15 "strconv"
16 "strings"
17 )
18
19
20 type Tree struct {
21 Name string
22 ParseName string
23 Root *ListNode
24 text string
25
26 funcs []map[string]interface{}
27 lex *lexer
28 token [3]item
29 peekCount int
30 vars []string
31 treeSet map[string]*Tree
32 }
33
34
35 func (t *Tree) Copy() *Tree {
36 if t == nil {
37 return nil
38 }
39 return &Tree{
40 Name: t.Name,
41 ParseName: t.ParseName,
42 Root: t.Root.CopyList(),
43 text: t.text,
44 }
45 }
46
47
48
49
50
51 func Parse(name, text, leftDelim, rightDelim string, funcs ...map[string]interface{}) (map[string]*Tree, error) {
52 treeSet := make(map[string]*Tree)
53 t := New(name)
54 t.text = text
55 _, err := t.Parse(text, leftDelim, rightDelim, treeSet, funcs...)
56 return treeSet, err
57 }
58
59
60 func (t *Tree) next() item {
61 if t.peekCount > 0 {
62 t.peekCount--
63 } else {
64 t.token[0] = t.lex.nextItem()
65 }
66 return t.token[t.peekCount]
67 }
68
69
70 func (t *Tree) backup() {
71 t.peekCount++
72 }
73
74
75
76 func (t *Tree) backup2(t1 item) {
77 t.token[1] = t1
78 t.peekCount = 2
79 }
80
81
82
83 func (t *Tree) backup3(t2, t1 item) {
84 t.token[1] = t1
85 t.token[2] = t2
86 t.peekCount = 3
87 }
88
89
90 func (t *Tree) peek() item {
91 if t.peekCount > 0 {
92 return t.token[t.peekCount-1]
93 }
94 t.peekCount = 1
95 t.token[0] = t.lex.nextItem()
96 return t.token[0]
97 }
98
99
100 func (t *Tree) nextNonSpace() (token item) {
101 for {
102 token = t.next()
103 if token.typ != itemSpace {
104 break
105 }
106 }
107 return token
108 }
109
110
111 func (t *Tree) peekNonSpace() item {
112 token := t.nextNonSpace()
113 t.backup()
114 return token
115 }
116
117
118
119
120 func New(name string, funcs ...map[string]interface{}) *Tree {
121 return &Tree{
122 Name: name,
123 funcs: funcs,
124 }
125 }
126
127
128
129
130 func (t *Tree) ErrorContext(n Node) (location, context string) {
131 pos := int(n.Position())
132 tree := n.tree()
133 if tree == nil {
134 tree = t
135 }
136 text := tree.text[:pos]
137 byteNum := strings.LastIndex(text, "\n")
138 if byteNum == -1 {
139 byteNum = pos
140 } else {
141 byteNum++
142 byteNum = pos - byteNum
143 }
144 lineNum := 1 + strings.Count(text, "\n")
145 context = n.String()
146 return fmt.Sprintf("%s:%d:%d", tree.ParseName, lineNum, byteNum), context
147 }
148
149
150 func (t *Tree) errorf(format string, args ...interface{}) {
151 t.Root = nil
152 format = fmt.Sprintf("template: %s:%d: %s", t.ParseName, t.token[0].line, format)
153 panic(fmt.Errorf(format, args...))
154 }
155
156
157 func (t *Tree) error(err error) {
158 t.errorf("%s", err)
159 }
160
161
162 func (t *Tree) expect(expected itemType, context string) item {
163 token := t.nextNonSpace()
164 if token.typ != expected {
165 t.unexpected(token, context)
166 }
167 return token
168 }
169
170
171 func (t *Tree) expectOneOf(expected1, expected2 itemType, context string) item {
172 token := t.nextNonSpace()
173 if token.typ != expected1 && token.typ != expected2 {
174 t.unexpected(token, context)
175 }
176 return token
177 }
178
179
180 func (t *Tree) unexpected(token item, context string) {
181 t.errorf("unexpected %s in %s", token, context)
182 }
183
184
185 func (t *Tree) recover(errp *error) {
186 e := recover()
187 if e != nil {
188 if _, ok := e.(runtime.Error); ok {
189 panic(e)
190 }
191 if t != nil {
192 t.lex.drain()
193 t.stopParse()
194 }
195 *errp = e.(error)
196 }
197 }
198
199
200 func (t *Tree) startParse(funcs []map[string]interface{}, lex *lexer, treeSet map[string]*Tree) {
201 t.Root = nil
202 t.lex = lex
203 t.vars = []string{"$"}
204 t.funcs = funcs
205 t.treeSet = treeSet
206 }
207
208
209 func (t *Tree) stopParse() {
210 t.lex = nil
211 t.vars = nil
212 t.funcs = nil
213 t.treeSet = nil
214 }
215
216
217
218
219
220 func (t *Tree) Parse(text, leftDelim, rightDelim string, treeSet map[string]*Tree, funcs ...map[string]interface{}) (tree *Tree, err error) {
221 defer t.recover(&err)
222 t.ParseName = t.Name
223 t.startParse(funcs, lex(t.Name, text, leftDelim, rightDelim), treeSet)
224 t.text = text
225 t.parse()
226 t.add()
227 t.stopParse()
228 return t, nil
229 }
230
231
232 func (t *Tree) add() {
233 tree := t.treeSet[t.Name]
234 if tree == nil || IsEmptyTree(tree.Root) {
235 t.treeSet[t.Name] = t
236 return
237 }
238 if !IsEmptyTree(t.Root) {
239 t.errorf("template: multiple definition of template %q", t.Name)
240 }
241 }
242
243
244 func IsEmptyTree(n Node) bool {
245 switch n := n.(type) {
246 case nil:
247 return true
248 case *ActionNode:
249 case *IfNode:
250 case *ListNode:
251 for _, node := range n.Nodes {
252 if !IsEmptyTree(node) {
253 return false
254 }
255 }
256 return true
257 case *RangeNode:
258 case *TemplateNode:
259 case *TextNode:
260 return len(bytes.TrimSpace(n.Text)) == 0
261 case *WithNode:
262 default:
263 panic("unknown node: " + n.String())
264 }
265 return false
266 }
267
268
269
270
271 func (t *Tree) parse() {
272 t.Root = t.newList(t.peek().pos)
273 for t.peek().typ != itemEOF {
274 if t.peek().typ == itemLeftDelim {
275 delim := t.next()
276 if t.nextNonSpace().typ == itemDefine {
277 newT := New("definition")
278 newT.text = t.text
279 newT.ParseName = t.ParseName
280 newT.startParse(t.funcs, t.lex, t.treeSet)
281 newT.parseDefinition()
282 continue
283 }
284 t.backup2(delim)
285 }
286 switch n := t.textOrAction(); n.Type() {
287 case nodeEnd, nodeElse:
288 t.errorf("unexpected %s", n)
289 default:
290 t.Root.append(n)
291 }
292 }
293 }
294
295
296
297
298 func (t *Tree) parseDefinition() {
299 const context = "define clause"
300 name := t.expectOneOf(itemString, itemRawString, context)
301 var err error
302 t.Name, err = strconv.Unquote(name.val)
303 if err != nil {
304 t.error(err)
305 }
306 t.expect(itemRightDelim, context)
307 var end Node
308 t.Root, end = t.itemList()
309 if end.Type() != nodeEnd {
310 t.errorf("unexpected %s in %s", end, context)
311 }
312 t.add()
313 t.stopParse()
314 }
315
316
317
318
319 func (t *Tree) itemList() (list *ListNode, next Node) {
320 list = t.newList(t.peekNonSpace().pos)
321 for t.peekNonSpace().typ != itemEOF {
322 n := t.textOrAction()
323 switch n.Type() {
324 case nodeEnd, nodeElse:
325 return list, n
326 }
327 list.append(n)
328 }
329 t.errorf("unexpected EOF")
330 return
331 }
332
333
334
335 func (t *Tree) textOrAction() Node {
336 switch token := t.nextNonSpace(); token.typ {
337 case itemText:
338 return t.newText(token.pos, token.val)
339 case itemLeftDelim:
340 return t.action()
341 default:
342 t.unexpected(token, "input")
343 }
344 return nil
345 }
346
347
348
349
350
351
352 func (t *Tree) action() (n Node) {
353 switch token := t.nextNonSpace(); token.typ {
354 case itemBlock:
355 return t.blockControl()
356 case itemElse:
357 return t.elseControl()
358 case itemEnd:
359 return t.endControl()
360 case itemIf:
361 return t.ifControl()
362 case itemRange:
363 return t.rangeControl()
364 case itemTemplate:
365 return t.templateControl()
366 case itemWith:
367 return t.withControl()
368 }
369 t.backup()
370 token := t.peek()
371
372 return t.newAction(token.pos, token.line, t.pipeline("command"))
373 }
374
375
376
377 func (t *Tree) pipeline(context string) (pipe *PipeNode) {
378 token := t.peekNonSpace()
379 pipe = t.newPipeline(token.pos, token.line, nil)
380
381 decls:
382 if v := t.peekNonSpace(); v.typ == itemVariable {
383 t.next()
384
385
386
387
388 tokenAfterVariable := t.peek()
389 next := t.peekNonSpace()
390 switch {
391 case next.typ == itemAssign, next.typ == itemDeclare:
392 pipe.IsAssign = next.typ == itemAssign
393 t.nextNonSpace()
394 pipe.Decl = append(pipe.Decl, t.newVariable(v.pos, v.val))
395 t.vars = append(t.vars, v.val)
396 case next.typ == itemChar && next.val == ",":
397 t.nextNonSpace()
398 pipe.Decl = append(pipe.Decl, t.newVariable(v.pos, v.val))
399 t.vars = append(t.vars, v.val)
400 if context == "range" && len(pipe.Decl) < 2 {
401 switch t.peekNonSpace().typ {
402 case itemVariable, itemRightDelim, itemRightParen:
403
404 goto decls
405 default:
406 t.errorf("range can only initialize variables")
407 }
408 }
409 t.errorf("too many declarations in %s", context)
410 case tokenAfterVariable.typ == itemSpace:
411 t.backup3(v, tokenAfterVariable)
412 default:
413 t.backup2(v)
414 }
415 }
416 for {
417 switch token := t.nextNonSpace(); token.typ {
418 case itemRightDelim, itemRightParen:
419
420 t.checkPipeline(pipe, context)
421 if token.typ == itemRightParen {
422 t.backup()
423 }
424 return
425 case itemBool, itemCharConstant, itemComplex, itemDot, itemField, itemIdentifier,
426 itemNumber, itemNil, itemRawString, itemString, itemVariable, itemLeftParen:
427 t.backup()
428 pipe.append(t.command())
429 default:
430 t.unexpected(token, context)
431 }
432 }
433 }
434
435 func (t *Tree) checkPipeline(pipe *PipeNode, context string) {
436
437 if len(pipe.Cmds) == 0 {
438 t.errorf("missing value for %s", context)
439 }
440
441 for i, c := range pipe.Cmds[1:] {
442 switch c.Args[0].Type() {
443 case NodeBool, NodeDot, NodeNil, NodeNumber, NodeString:
444
445 t.errorf("non executable command in pipeline stage %d", i+2)
446 }
447 }
448 }
449
450 func (t *Tree) parseControl(allowElseIf bool, context string) (pos Pos, line int, pipe *PipeNode, list, elseList *ListNode) {
451 defer t.popVars(len(t.vars))
452 pipe = t.pipeline(context)
453 var next Node
454 list, next = t.itemList()
455 switch next.Type() {
456 case nodeEnd:
457 case nodeElse:
458 if allowElseIf {
459
460
461
462
463
464
465
466
467 if t.peek().typ == itemIf {
468 t.next()
469 elseList = t.newList(next.Position())
470 elseList.append(t.ifControl())
471
472 break
473 }
474 }
475 elseList, next = t.itemList()
476 if next.Type() != nodeEnd {
477 t.errorf("expected end; found %s", next)
478 }
479 }
480 return pipe.Position(), pipe.Line, pipe, list, elseList
481 }
482
483
484
485
486
487 func (t *Tree) ifControl() Node {
488 return t.newIf(t.parseControl(true, "if"))
489 }
490
491
492
493
494
495 func (t *Tree) rangeControl() Node {
496 return t.newRange(t.parseControl(false, "range"))
497 }
498
499
500
501
502
503 func (t *Tree) withControl() Node {
504 return t.newWith(t.parseControl(false, "with"))
505 }
506
507
508
509
510 func (t *Tree) endControl() Node {
511 return t.newEnd(t.expect(itemRightDelim, "end").pos)
512 }
513
514
515
516
517 func (t *Tree) elseControl() Node {
518
519 peek := t.peekNonSpace()
520 if peek.typ == itemIf {
521
522 return t.newElse(peek.pos, peek.line)
523 }
524 token := t.expect(itemRightDelim, "else")
525 return t.newElse(token.pos, token.line)
526 }
527
528
529
530
531
532
533 func (t *Tree) blockControl() Node {
534 const context = "block clause"
535
536 token := t.nextNonSpace()
537 name := t.parseTemplateName(token, context)
538 pipe := t.pipeline(context)
539
540 block := New(name)
541 block.text = t.text
542 block.ParseName = t.ParseName
543 block.startParse(t.funcs, t.lex, t.treeSet)
544 var end Node
545 block.Root, end = block.itemList()
546 if end.Type() != nodeEnd {
547 t.errorf("unexpected %s in %s", end, context)
548 }
549 block.add()
550 block.stopParse()
551
552 return t.newTemplate(token.pos, token.line, name, pipe)
553 }
554
555
556
557
558
559 func (t *Tree) templateControl() Node {
560 const context = "template clause"
561 token := t.nextNonSpace()
562 name := t.parseTemplateName(token, context)
563 var pipe *PipeNode
564 if t.nextNonSpace().typ != itemRightDelim {
565 t.backup()
566
567 pipe = t.pipeline(context)
568 }
569 return t.newTemplate(token.pos, token.line, name, pipe)
570 }
571
572 func (t *Tree) parseTemplateName(token item, context string) (name string) {
573 switch token.typ {
574 case itemString, itemRawString:
575 s, err := strconv.Unquote(token.val)
576 if err != nil {
577 t.error(err)
578 }
579 name = s
580 default:
581 t.unexpected(token, context)
582 }
583 return
584 }
585
586
587
588
589
590 func (t *Tree) command() *CommandNode {
591 cmd := t.newCommand(t.peekNonSpace().pos)
592 for {
593 t.peekNonSpace()
594 operand := t.operand()
595 if operand != nil {
596 cmd.append(operand)
597 }
598 switch token := t.next(); token.typ {
599 case itemSpace:
600 continue
601 case itemError:
602 t.errorf("%s", token.val)
603 case itemRightDelim, itemRightParen:
604 t.backup()
605 case itemPipe:
606 default:
607 t.errorf("unexpected %s in operand", token)
608 }
609 break
610 }
611 if len(cmd.Args) == 0 {
612 t.errorf("empty command")
613 }
614 return cmd
615 }
616
617
618
619
620
621
622 func (t *Tree) operand() Node {
623 node := t.term()
624 if node == nil {
625 return nil
626 }
627 if t.peek().typ == itemField {
628 chain := t.newChain(t.peek().pos, node)
629 for t.peek().typ == itemField {
630 chain.Add(t.next().val)
631 }
632
633
634
635
636
637 switch node.Type() {
638 case NodeField:
639 node = t.newField(chain.Position(), chain.String())
640 case NodeVariable:
641 node = t.newVariable(chain.Position(), chain.String())
642 case NodeBool, NodeString, NodeNumber, NodeNil, NodeDot:
643 t.errorf("unexpected . after term %q", node.String())
644 default:
645 node = chain
646 }
647 }
648 return node
649 }
650
651
652
653
654
655
656
657
658
659
660 func (t *Tree) term() Node {
661 switch token := t.nextNonSpace(); token.typ {
662 case itemError:
663 t.errorf("%s", token.val)
664 case itemIdentifier:
665 if !t.hasFunction(token.val) {
666 t.errorf("function %q not defined", token.val)
667 }
668 return NewIdentifier(token.val).SetTree(t).SetPos(token.pos)
669 case itemDot:
670 return t.newDot(token.pos)
671 case itemNil:
672 return t.newNil(token.pos)
673 case itemVariable:
674 return t.useVar(token.pos, token.val)
675 case itemField:
676 return t.newField(token.pos, token.val)
677 case itemBool:
678 return t.newBool(token.pos, token.val == "true")
679 case itemCharConstant, itemComplex, itemNumber:
680 number, err := t.newNumber(token.pos, token.val, token.typ)
681 if err != nil {
682 t.error(err)
683 }
684 return number
685 case itemLeftParen:
686 pipe := t.pipeline("parenthesized pipeline")
687 if token := t.next(); token.typ != itemRightParen {
688 t.errorf("unclosed right paren: unexpected %s", token)
689 }
690 return pipe
691 case itemString, itemRawString:
692 s, err := strconv.Unquote(token.val)
693 if err != nil {
694 t.error(err)
695 }
696 return t.newString(token.pos, token.val, s)
697 }
698 t.backup()
699 return nil
700 }
701
702
703 func (t *Tree) hasFunction(name string) bool {
704 for _, funcMap := range t.funcs {
705 if funcMap == nil {
706 continue
707 }
708 if funcMap[name] != nil {
709 return true
710 }
711 }
712 return false
713 }
714
715
716 func (t *Tree) popVars(n int) {
717 t.vars = t.vars[:n]
718 }
719
720
721
722 func (t *Tree) useVar(pos Pos, name string) Node {
723 v := t.newVariable(pos, name)
724 for _, varName := range t.vars {
725 if varName == v.Ident[0] {
726 return v
727 }
728 }
729 t.errorf("undefined variable %q", v.Ident[0])
730 return nil
731 }
732
View as plain text