1// Copyright 2011 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package parse builds parse trees for templates as defined by text/template 6// and html/template. Clients should use those packages to construct templates 7// rather than this one, which provides shared internal data structures not 8// intended for general use. 9package parse 10 11import ( 12 "bytes" 13 "fmt" 14 "runtime" 15 "strconv" 16 "strings" 17) 18 19// Tree is the representation of a single parsed template. 20type Tree struct { 21 Name string // name of the template represented by the tree. 22 ParseName string // name of the top-level template during parsing, for error messages. 23 Root *ListNode // top-level root of the tree. 24 text string // text parsed to create the template (or its parent) 25 // Parsing only; cleared after parse. 26 funcs []map[string]interface{} 27 lex *lexer 28 token [3]item // three-token lookahead for parser. 29 peekCount int 30 vars []string // variables defined at the moment. 31} 32 33// Copy returns a copy of the Tree. Any parsing state is discarded. 34func (t *Tree) Copy() *Tree { 35 if t == nil { 36 return nil 37 } 38 return &Tree{ 39 Name: t.Name, 40 ParseName: t.ParseName, 41 Root: t.Root.CopyList(), 42 text: t.text, 43 } 44} 45 46// Parse returns a map from template name to parse.Tree, created by parsing the 47// templates described in the argument string. The top-level template will be 48// given the specified name. If an error is encountered, parsing stops and an 49// empty map is returned with the error. 50func Parse(name, text, leftDelim, rightDelim string, funcs ...map[string]interface{}) (treeSet map[string]*Tree, err error) { 51 treeSet = make(map[string]*Tree) 52 t := New(name) 53 t.text = text 54 _, err = t.Parse(text, leftDelim, rightDelim, treeSet, funcs...) 55 return 56} 57 58// next returns the next token. 59func (t *Tree) next() item { 60 if t.peekCount > 0 { 61 t.peekCount-- 62 } else { 63 t.token[0] = t.lex.nextItem() 64 } 65 return t.token[t.peekCount] 66} 67 68// backup backs the input stream up one token. 69func (t *Tree) backup() { 70 t.peekCount++ 71} 72 73// backup2 backs the input stream up two tokens. 74// The zeroth token is already there. 75func (t *Tree) backup2(t1 item) { 76 t.token[1] = t1 77 t.peekCount = 2 78} 79 80// backup3 backs the input stream up three tokens 81// The zeroth token is already there. 82func (t *Tree) backup3(t2, t1 item) { // Reverse order: we're pushing back. 83 t.token[1] = t1 84 t.token[2] = t2 85 t.peekCount = 3 86} 87 88// peek returns but does not consume the next token. 89func (t *Tree) peek() item { 90 if t.peekCount > 0 { 91 return t.token[t.peekCount-1] 92 } 93 t.peekCount = 1 94 t.token[0] = t.lex.nextItem() 95 return t.token[0] 96} 97 98// nextNonSpace returns the next non-space token. 99func (t *Tree) nextNonSpace() (token item) { 100 for { 101 token = t.next() 102 if token.typ != itemSpace { 103 break 104 } 105 } 106 return token 107} 108 109// peekNonSpace returns but does not consume the next non-space token. 110func (t *Tree) peekNonSpace() (token item) { 111 for { 112 token = t.next() 113 if token.typ != itemSpace { 114 break 115 } 116 } 117 t.backup() 118 return token 119} 120 121// Parsing. 122 123// New allocates a new parse tree with the given name. 124func New(name string, funcs ...map[string]interface{}) *Tree { 125 return &Tree{ 126 Name: name, 127 funcs: funcs, 128 } 129} 130 131// ErrorContext returns a textual representation of the location of the node in the input text. 132// The receiver is only used when the node does not have a pointer to the tree inside, 133// which can occur in old code. 134func (t *Tree) ErrorContext(n Node) (location, context string) { 135 pos := int(n.Position()) 136 tree := n.tree() 137 if tree == nil { 138 tree = t 139 } 140 text := tree.text[:pos] 141 byteNum := strings.LastIndex(text, "\n") 142 if byteNum == -1 { 143 byteNum = pos // On first line. 144 } else { 145 byteNum++ // After the newline. 146 byteNum = pos - byteNum 147 } 148 lineNum := 1 + strings.Count(text, "\n") 149 context = n.String() 150 if len(context) > 20 { 151 context = fmt.Sprintf("%.20s...", context) 152 } 153 return fmt.Sprintf("%s:%d:%d", tree.ParseName, lineNum, byteNum), context 154} 155 156// errorf formats the error and terminates processing. 157func (t *Tree) errorf(format string, args ...interface{}) { 158 t.Root = nil 159 format = fmt.Sprintf("template: %s:%d: %s", t.ParseName, t.lex.lineNumber(), format) 160 panic(fmt.Errorf(format, args...)) 161} 162 163// error terminates processing. 164func (t *Tree) error(err error) { 165 t.errorf("%s", err) 166} 167 168// expect consumes the next token and guarantees it has the required type. 169func (t *Tree) expect(expected itemType, context string) item { 170 token := t.nextNonSpace() 171 if token.typ != expected { 172 t.unexpected(token, context) 173 } 174 return token 175} 176 177// expectOneOf consumes the next token and guarantees it has one of the required types. 178func (t *Tree) expectOneOf(expected1, expected2 itemType, context string) item { 179 token := t.nextNonSpace() 180 if token.typ != expected1 && token.typ != expected2 { 181 t.unexpected(token, context) 182 } 183 return token 184} 185 186// unexpected complains about the token and terminates processing. 187func (t *Tree) unexpected(token item, context string) { 188 t.errorf("unexpected %s in %s", token, context) 189} 190 191// recover is the handler that turns panics into returns from the top level of Parse. 192func (t *Tree) recover(errp *error) { 193 e := recover() 194 if e != nil { 195 if _, ok := e.(runtime.Error); ok { 196 panic(e) 197 } 198 if t != nil { 199 t.stopParse() 200 } 201 *errp = e.(error) 202 } 203 return 204} 205 206// startParse initializes the parser, using the lexer. 207func (t *Tree) startParse(funcs []map[string]interface{}, lex *lexer) { 208 t.Root = nil 209 t.lex = lex 210 t.vars = []string{"$"} 211 t.funcs = funcs 212} 213 214// stopParse terminates parsing. 215func (t *Tree) stopParse() { 216 t.lex = nil 217 t.vars = nil 218 t.funcs = nil 219} 220 221// Parse parses the template definition string to construct a representation of 222// the template for execution. If either action delimiter string is empty, the 223// default ("{{" or "}}") is used. Embedded template definitions are added to 224// the treeSet map. 225func (t *Tree) Parse(text, leftDelim, rightDelim string, treeSet map[string]*Tree, funcs ...map[string]interface{}) (tree *Tree, err error) { 226 defer t.recover(&err) 227 t.ParseName = t.Name 228 t.startParse(funcs, lex(t.Name, text, leftDelim, rightDelim)) 229 t.text = text 230 t.parse(treeSet) 231 t.add(treeSet) 232 t.stopParse() 233 return t, nil 234} 235 236// add adds tree to the treeSet. 237func (t *Tree) add(treeSet map[string]*Tree) { 238 tree := treeSet[t.Name] 239 if tree == nil || IsEmptyTree(tree.Root) { 240 treeSet[t.Name] = t 241 return 242 } 243 if !IsEmptyTree(t.Root) { 244 t.errorf("template: multiple definition of template %q", t.Name) 245 } 246} 247 248// IsEmptyTree reports whether this tree (node) is empty of everything but space. 249func IsEmptyTree(n Node) bool { 250 switch n := n.(type) { 251 case nil: 252 return true 253 case *ActionNode: 254 case *IfNode: 255 case *ListNode: 256 for _, node := range n.Nodes { 257 if !IsEmptyTree(node) { 258 return false 259 } 260 } 261 return true 262 case *RangeNode: 263 case *TemplateNode: 264 case *TextNode: 265 return len(bytes.TrimSpace(n.Text)) == 0 266 case *WithNode: 267 default: 268 panic("unknown node: " + n.String()) 269 } 270 return false 271} 272 273// parse is the top-level parser for a template, essentially the same 274// as itemList except it also parses {{define}} actions. 275// It runs to EOF. 276func (t *Tree) parse(treeSet map[string]*Tree) (next Node) { 277 t.Root = t.newList(t.peek().pos) 278 for t.peek().typ != itemEOF { 279 if t.peek().typ == itemLeftDelim { 280 delim := t.next() 281 if t.nextNonSpace().typ == itemDefine { 282 newT := New("definition") // name will be updated once we know it. 283 newT.text = t.text 284 newT.ParseName = t.ParseName 285 newT.startParse(t.funcs, t.lex) 286 newT.parseDefinition(treeSet) 287 continue 288 } 289 t.backup2(delim) 290 } 291 n := t.textOrAction() 292 if n.Type() == nodeEnd { 293 t.errorf("unexpected %s", n) 294 } 295 t.Root.append(n) 296 } 297 return nil 298} 299 300// parseDefinition parses a {{define}} ... {{end}} template definition and 301// installs the definition in the treeSet map. The "define" keyword has already 302// been scanned. 303func (t *Tree) parseDefinition(treeSet map[string]*Tree) { 304 const context = "define clause" 305 name := t.expectOneOf(itemString, itemRawString, context) 306 var err error 307 t.Name, err = strconv.Unquote(name.val) 308 if err != nil { 309 t.error(err) 310 } 311 t.expect(itemRightDelim, context) 312 var end Node 313 t.Root, end = t.itemList() 314 if end.Type() != nodeEnd { 315 t.errorf("unexpected %s in %s", end, context) 316 } 317 t.add(treeSet) 318 t.stopParse() 319} 320 321// itemList: 322// textOrAction* 323// Terminates at {{end}} or {{else}}, returned separately. 324func (t *Tree) itemList() (list *ListNode, next Node) { 325 list = t.newList(t.peekNonSpace().pos) 326 for t.peekNonSpace().typ != itemEOF { 327 n := t.textOrAction() 328 switch n.Type() { 329 case nodeEnd, nodeElse: 330 return list, n 331 } 332 list.append(n) 333 } 334 t.errorf("unexpected EOF") 335 return 336} 337 338// textOrAction: 339// text | action 340func (t *Tree) textOrAction() Node { 341 switch token := t.nextNonSpace(); token.typ { 342 case itemElideNewline: 343 return t.elideNewline() 344 case itemText: 345 return t.newText(token.pos, token.val) 346 case itemLeftDelim: 347 return t.action() 348 default: 349 t.unexpected(token, "input") 350 } 351 return nil 352} 353 354// elideNewline: 355// Remove newlines trailing rightDelim if \\ is present. 356func (t *Tree) elideNewline() Node { 357 token := t.peek() 358 if token.typ != itemText { 359 t.unexpected(token, "input") 360 return nil 361 } 362 363 t.next() 364 stripped := strings.TrimLeft(token.val, "\n\r") 365 diff := len(token.val) - len(stripped) 366 if diff > 0 { 367 // This is a bit nasty. We mutate the token in-place to remove 368 // preceding newlines. 369 token.pos += Pos(diff) 370 token.val = stripped 371 } 372 return t.newText(token.pos, token.val) 373} 374 375// Action: 376// control 377// command ("|" command)* 378// Left delim is past. Now get actions. 379// First word could be a keyword such as range. 380func (t *Tree) action() (n Node) { 381 switch token := t.nextNonSpace(); token.typ { 382 case itemElse: 383 return t.elseControl() 384 case itemEnd: 385 return t.endControl() 386 case itemIf: 387 return t.ifControl() 388 case itemRange: 389 return t.rangeControl() 390 case itemTemplate: 391 return t.templateControl() 392 case itemWith: 393 return t.withControl() 394 } 395 t.backup() 396 // Do not pop variables; they persist until "end". 397 return t.newAction(t.peek().pos, t.lex.lineNumber(), t.pipeline("command")) 398} 399 400// Pipeline: 401// declarations? command ('|' command)* 402func (t *Tree) pipeline(context string) (pipe *PipeNode) { 403 var decl []*VariableNode 404 pos := t.peekNonSpace().pos 405 // Are there declarations? 406 for { 407 if v := t.peekNonSpace(); v.typ == itemVariable { 408 t.next() 409 // Since space is a token, we need 3-token look-ahead here in the worst case: 410 // in "$x foo" we need to read "foo" (as opposed to ":=") to know that $x is an 411 // argument variable rather than a declaration. So remember the token 412 // adjacent to the variable so we can push it back if necessary. 413 tokenAfterVariable := t.peek() 414 if next := t.peekNonSpace(); next.typ == itemColonEquals || (next.typ == itemChar && next.val == ",") { 415 t.nextNonSpace() 416 variable := t.newVariable(v.pos, v.val) 417 decl = append(decl, variable) 418 t.vars = append(t.vars, v.val) 419 if next.typ == itemChar && next.val == "," { 420 if context == "range" && len(decl) < 2 { 421 continue 422 } 423 t.errorf("too many declarations in %s", context) 424 } 425 } else if tokenAfterVariable.typ == itemSpace { 426 t.backup3(v, tokenAfterVariable) 427 } else { 428 t.backup2(v) 429 } 430 } 431 break 432 } 433 pipe = t.newPipeline(pos, t.lex.lineNumber(), decl) 434 for { 435 switch token := t.nextNonSpace(); token.typ { 436 case itemRightDelim, itemRightParen: 437 if len(pipe.Cmds) == 0 { 438 t.errorf("missing value for %s", context) 439 } 440 if token.typ == itemRightParen { 441 t.backup() 442 } 443 return 444 case itemBool, itemCharConstant, itemComplex, itemDot, itemField, itemIdentifier, 445 itemNumber, itemNil, itemRawString, itemString, itemVariable, itemLeftParen: 446 t.backup() 447 pipe.append(t.command()) 448 default: 449 t.unexpected(token, context) 450 } 451 } 452} 453 454func (t *Tree) parseControl(allowElseIf bool, context string) (pos Pos, line int, pipe *PipeNode, list, elseList *ListNode) { 455 defer t.popVars(len(t.vars)) 456 line = t.lex.lineNumber() 457 pipe = t.pipeline(context) 458 var next Node 459 list, next = t.itemList() 460 switch next.Type() { 461 case nodeEnd: //done 462 case nodeElse: 463 if allowElseIf { 464 // Special case for "else if". If the "else" is followed immediately by an "if", 465 // the elseControl will have left the "if" token pending. Treat 466 // {{if a}}_{{else if b}}_{{end}} 467 // as 468 // {{if a}}_{{else}}{{if b}}_{{end}}{{end}}. 469 // To do this, parse the if as usual and stop at it {{end}}; the subsequent{{end}} 470 // is assumed. This technique works even for long if-else-if chains. 471 // TODO: Should we allow else-if in with and range? 472 if t.peek().typ == itemIf { 473 t.next() // Consume the "if" token. 474 elseList = t.newList(next.Position()) 475 elseList.append(t.ifControl()) 476 // Do not consume the next item - only one {{end}} required. 477 break 478 } 479 } 480 elseList, next = t.itemList() 481 if next.Type() != nodeEnd { 482 t.errorf("expected end; found %s", next) 483 } 484 } 485 return pipe.Position(), line, pipe, list, elseList 486} 487 488// If: 489// {{if pipeline}} itemList {{end}} 490// {{if pipeline}} itemList {{else}} itemList {{end}} 491// If keyword is past. 492func (t *Tree) ifControl() Node { 493 return t.newIf(t.parseControl(true, "if")) 494} 495 496// Range: 497// {{range pipeline}} itemList {{end}} 498// {{range pipeline}} itemList {{else}} itemList {{end}} 499// Range keyword is past. 500func (t *Tree) rangeControl() Node { 501 return t.newRange(t.parseControl(false, "range")) 502} 503 504// With: 505// {{with pipeline}} itemList {{end}} 506// {{with pipeline}} itemList {{else}} itemList {{end}} 507// If keyword is past. 508func (t *Tree) withControl() Node { 509 return t.newWith(t.parseControl(false, "with")) 510} 511 512// End: 513// {{end}} 514// End keyword is past. 515func (t *Tree) endControl() Node { 516 return t.newEnd(t.expect(itemRightDelim, "end").pos) 517} 518 519// Else: 520// {{else}} 521// Else keyword is past. 522func (t *Tree) elseControl() Node { 523 // Special case for "else if". 524 peek := t.peekNonSpace() 525 if peek.typ == itemIf { 526 // We see "{{else if ... " but in effect rewrite it to {{else}}{{if ... ". 527 return t.newElse(peek.pos, t.lex.lineNumber()) 528 } 529 return t.newElse(t.expect(itemRightDelim, "else").pos, t.lex.lineNumber()) 530} 531 532// Template: 533// {{template stringValue pipeline}} 534// Template keyword is past. The name must be something that can evaluate 535// to a string. 536func (t *Tree) templateControl() Node { 537 var name string 538 token := t.nextNonSpace() 539 switch token.typ { 540 case itemString, itemRawString: 541 s, err := strconv.Unquote(token.val) 542 if err != nil { 543 t.error(err) 544 } 545 name = s 546 default: 547 t.unexpected(token, "template invocation") 548 } 549 var pipe *PipeNode 550 if t.nextNonSpace().typ != itemRightDelim { 551 t.backup() 552 // Do not pop variables; they persist until "end". 553 pipe = t.pipeline("template") 554 } 555 return t.newTemplate(token.pos, t.lex.lineNumber(), name, pipe) 556} 557 558// command: 559// operand (space operand)* 560// space-separated arguments up to a pipeline character or right delimiter. 561// we consume the pipe character but leave the right delim to terminate the action. 562func (t *Tree) command() *CommandNode { 563 cmd := t.newCommand(t.peekNonSpace().pos) 564 for { 565 t.peekNonSpace() // skip leading spaces. 566 operand := t.operand() 567 if operand != nil { 568 cmd.append(operand) 569 } 570 switch token := t.next(); token.typ { 571 case itemSpace: 572 continue 573 case itemError: 574 t.errorf("%s", token.val) 575 case itemRightDelim, itemRightParen: 576 t.backup() 577 case itemPipe: 578 default: 579 t.errorf("unexpected %s in operand; missing space?", token) 580 } 581 break 582 } 583 if len(cmd.Args) == 0 { 584 t.errorf("empty command") 585 } 586 return cmd 587} 588 589// operand: 590// term .Field* 591// An operand is a space-separated component of a command, 592// a term possibly followed by field accesses. 593// A nil return means the next item is not an operand. 594func (t *Tree) operand() Node { 595 node := t.term() 596 if node == nil { 597 return nil 598 } 599 if t.peek().typ == itemField { 600 chain := t.newChain(t.peek().pos, node) 601 for t.peek().typ == itemField { 602 chain.Add(t.next().val) 603 } 604 // Compatibility with original API: If the term is of type NodeField 605 // or NodeVariable, just put more fields on the original. 606 // Otherwise, keep the Chain node. 607 // TODO: Switch to Chains always when we can. 608 switch node.Type() { 609 case NodeField: 610 node = t.newField(chain.Position(), chain.String()) 611 case NodeVariable: 612 node = t.newVariable(chain.Position(), chain.String()) 613 default: 614 node = chain 615 } 616 } 617 return node 618} 619 620// term: 621// literal (number, string, nil, boolean) 622// function (identifier) 623// . 624// .Field 625// $ 626// '(' pipeline ')' 627// A term is a simple "expression". 628// A nil return means the next item is not a term. 629func (t *Tree) term() Node { 630 switch token := t.nextNonSpace(); token.typ { 631 case itemError: 632 t.errorf("%s", token.val) 633 case itemIdentifier: 634 if !t.hasFunction(token.val) { 635 t.errorf("function %q not defined", token.val) 636 } 637 return NewIdentifier(token.val).SetTree(t).SetPos(token.pos) 638 case itemDot: 639 return t.newDot(token.pos) 640 case itemNil: 641 return t.newNil(token.pos) 642 case itemVariable: 643 return t.useVar(token.pos, token.val) 644 case itemField: 645 return t.newField(token.pos, token.val) 646 case itemBool: 647 return t.newBool(token.pos, token.val == "true") 648 case itemCharConstant, itemComplex, itemNumber: 649 number, err := t.newNumber(token.pos, token.val, token.typ) 650 if err != nil { 651 t.error(err) 652 } 653 return number 654 case itemLeftParen: 655 pipe := t.pipeline("parenthesized pipeline") 656 if token := t.next(); token.typ != itemRightParen { 657 t.errorf("unclosed right paren: unexpected %s", token) 658 } 659 return pipe 660 case itemString, itemRawString: 661 s, err := strconv.Unquote(token.val) 662 if err != nil { 663 t.error(err) 664 } 665 return t.newString(token.pos, token.val, s) 666 } 667 t.backup() 668 return nil 669} 670 671// hasFunction reports if a function name exists in the Tree's maps. 672func (t *Tree) hasFunction(name string) bool { 673 for _, funcMap := range t.funcs { 674 if funcMap == nil { 675 continue 676 } 677 if funcMap[name] != nil { 678 return true 679 } 680 } 681 return false 682} 683 684// popVars trims the variable list to the specified length 685func (t *Tree) popVars(n int) { 686 t.vars = t.vars[:n] 687} 688 689// useVar returns a node for a variable reference. It errors if the 690// variable is not defined. 691func (t *Tree) useVar(pos Pos, name string) Node { 692 v := t.newVariable(pos, name) 693 for _, varName := range t.vars { 694 if varName == v.Ident[0] { 695 return v 696 } 697 } 698 t.errorf("undefined variable %q", v.Ident[0]) 699 return nil 700} 701