Source file src/pkg/text/template/parse/parse.go
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. 9 package parse 10 11 import ( 12 "bytes" 13 "fmt" 14 "runtime" 15 "strconv" 16 "unicode" 17 ) 18 19 // Tree is the representation of a single parsed template. 20 type Tree struct { 21 Name string // name of the template represented by the tree. 22 Root *ListNode // top-level root of the tree. 23 // Parsing only; cleared after parse. 24 funcs []map[string]interface{} 25 lex *lexer 26 token [2]item // two-token lookahead for parser. 27 peekCount int 28 vars []string // variables defined at the moment. 29 } 30 31 // Parse returns a map from template name to parse.Tree, created by parsing the 32 // templates described in the argument string. The top-level template will be 33 // given the specified name. If an error is encountered, parsing stops and an 34 // empty map is returned with the error. 35 func Parse(name, text, leftDelim, rightDelim string, funcs ...map[string]interface{}) (treeSet map[string]*Tree, err error) { 36 treeSet = make(map[string]*Tree) 37 _, err = New(name).Parse(text, leftDelim, rightDelim, treeSet, funcs...) 38 return 39 } 40 41 // next returns the next token. 42 func (t *Tree) next() item { 43 if t.peekCount > 0 { 44 t.peekCount-- 45 } else { 46 t.token[0] = t.lex.nextItem() 47 } 48 return t.token[t.peekCount] 49 } 50 51 // backup backs the input stream up one token. 52 func (t *Tree) backup() { 53 t.peekCount++ 54 } 55 56 // backup2 backs the input stream up two tokens 57 func (t *Tree) backup2(t1 item) { 58 t.token[1] = t1 59 t.peekCount = 2 60 } 61 62 // peek returns but does not consume the next token. 63 func (t *Tree) peek() item { 64 if t.peekCount > 0 { 65 return t.token[t.peekCount-1] 66 } 67 t.peekCount = 1 68 t.token[0] = t.lex.nextItem() 69 return t.token[0] 70 } 71 72 // Parsing. 73 74 // New allocates a new parse tree with the given name. 75 func New(name string, funcs ...map[string]interface{}) *Tree { 76 return &Tree{ 77 Name: name, 78 funcs: funcs, 79 } 80 } 81 82 // errorf formats the error and terminates processing. 83 func (t *Tree) errorf(format string, args ...interface{}) { 84 t.Root = nil 85 format = fmt.Sprintf("template: %s:%d: %s", t.Name, t.lex.lineNumber(), format) 86 panic(fmt.Errorf(format, args...)) 87 } 88 89 // error terminates processing. 90 func (t *Tree) error(err error) { 91 t.errorf("%s", err) 92 } 93 94 // expect consumes the next token and guarantees it has the required type. 95 func (t *Tree) expect(expected itemType, context string) item { 96 token := t.next() 97 if token.typ != expected { 98 t.errorf("expected %s in %s; got %s", expected, context, token) 99 } 100 return token 101 } 102 103 // expectEither consumes the next token and guarantees it has one of the required types. 104 func (t *Tree) expectOneOf(expected1, expected2 itemType, context string) item { 105 token := t.next() 106 if token.typ != expected1 && token.typ != expected2 { 107 t.errorf("expected %s or %s in %s; got %s", expected1, expected2, context, token) 108 } 109 return token 110 } 111 112 // unexpected complains about the token and terminates processing. 113 func (t *Tree) unexpected(token item, context string) { 114 t.errorf("unexpected %s in %s", token, context) 115 } 116 117 // recover is the handler that turns panics into returns from the top level of Parse. 118 func (t *Tree) recover(errp *error) { 119 e := recover() 120 if e != nil { 121 if _, ok := e.(runtime.Error); ok { 122 panic(e) 123 } 124 if t != nil { 125 t.stopParse() 126 } 127 *errp = e.(error) 128 } 129 return 130 } 131 132 // startParse initializes the parser, using the lexer. 133 func (t *Tree) startParse(funcs []map[string]interface{}, lex *lexer) { 134 t.Root = nil 135 t.lex = lex 136 t.vars = []string{"$"} 137 t.funcs = funcs 138 } 139 140 // stopParse terminates parsing. 141 func (t *Tree) stopParse() { 142 t.lex = nil 143 t.vars = nil 144 t.funcs = nil 145 } 146 147 // atEOF returns true if, possibly after spaces, we're at EOF. 148 func (t *Tree) atEOF() bool { 149 for { 150 token := t.peek() 151 switch token.typ { 152 case itemEOF: 153 return true 154 case itemText: 155 for _, r := range token.val { 156 if !unicode.IsSpace(r) { 157 return false 158 } 159 } 160 t.next() // skip spaces. 161 continue 162 } 163 break 164 } 165 return false 166 } 167 168 // Parse parses the template definition string to construct a representation of 169 // the template for execution. If either action delimiter string is empty, the 170 // default ("{{" or "}}") is used. Embedded template definitions are added to 171 // the treeSet map. 172 func (t *Tree) Parse(s, leftDelim, rightDelim string, treeSet map[string]*Tree, funcs ...map[string]interface{}) (tree *Tree, err error) { 173 defer t.recover(&err) 174 t.startParse(funcs, lex(t.Name, s, leftDelim, rightDelim)) 175 t.parse(treeSet) 176 t.add(treeSet) 177 t.stopParse() 178 return t, nil 179 } 180 181 // add adds tree to the treeSet. 182 func (t *Tree) add(treeSet map[string]*Tree) { 183 tree := treeSet[t.Name] 184 if tree == nil || IsEmptyTree(tree.Root) { 185 treeSet[t.Name] = t 186 return 187 } 188 if !IsEmptyTree(t.Root) { 189 t.errorf("template: multiple definition of template %q", t.Name) 190 } 191 } 192 193 // IsEmptyTree reports whether this tree (node) is empty of everything but space. 194 func IsEmptyTree(n Node) bool { 195 switch n := n.(type) { 196 case nil: 197 return true 198 case *ActionNode: 199 case *IfNode: 200 case *ListNode: 201 for _, node := range n.Nodes { 202 if !IsEmptyTree(node) { 203 return false 204 } 205 } 206 return true 207 case *RangeNode: 208 case *TemplateNode: 209 case *TextNode: 210 return len(bytes.TrimSpace(n.Text)) == 0 211 case *WithNode: 212 default: 213 panic("unknown node: " + n.String()) 214 } 215 return false 216 } 217 218 // parse is the top-level parser for a template, essentially the same 219 // as itemList except it also parses {{define}} actions. 220 // It runs to EOF. 221 func (t *Tree) parse(treeSet map[string]*Tree) (next Node) { 222 t.Root = newList() 223 for t.peek().typ != itemEOF { 224 if t.peek().typ == itemLeftDelim { 225 delim := t.next() 226 if t.next().typ == itemDefine { 227 newT := New("definition") // name will be updated once we know it. 228 newT.startParse(t.funcs, t.lex) 229 newT.parseDefinition(treeSet) 230 continue 231 } 232 t.backup2(delim) 233 } 234 n := t.textOrAction() 235 if n.Type() == nodeEnd { 236 t.errorf("unexpected %s", n) 237 } 238 t.Root.append(n) 239 } 240 return nil 241 } 242 243 // parseDefinition parses a {{define}} ... {{end}} template definition and 244 // installs the definition in the treeSet map. The "define" keyword has already 245 // been scanned. 246 func (t *Tree) parseDefinition(treeSet map[string]*Tree) { 247 const context = "define clause" 248 name := t.expectOneOf(itemString, itemRawString, context) 249 var err error 250 t.Name, err = strconv.Unquote(name.val) 251 if err != nil { 252 t.error(err) 253 } 254 t.expect(itemRightDelim, context) 255 var end Node 256 t.Root, end = t.itemList() 257 if end.Type() != nodeEnd { 258 t.errorf("unexpected %s in %s", end, context) 259 } 260 t.stopParse() 261 t.add(treeSet) 262 } 263 264 // itemList: 265 // textOrAction* 266 // Terminates at {{end}} or {{else}}, returned separately. 267 func (t *Tree) itemList() (list *ListNode, next Node) { 268 list = newList() 269 for t.peek().typ != itemEOF { 270 n := t.textOrAction() 271 switch n.Type() { 272 case nodeEnd, nodeElse: 273 return list, n 274 } 275 list.append(n) 276 } 277 t.errorf("unexpected EOF") 278 return 279 } 280 281 // textOrAction: 282 // text | action 283 func (t *Tree) textOrAction() Node { 284 switch token := t.next(); token.typ { 285 case itemText: 286 return newText(token.val) 287 case itemLeftDelim: 288 return t.action() 289 default: 290 t.unexpected(token, "input") 291 } 292 return nil 293 } 294 295 // Action: 296 // control 297 // command ("|" command)* 298 // Left delim is past. Now get actions. 299 // First word could be a keyword such as range. 300 func (t *Tree) action() (n Node) { 301 switch token := t.next(); token.typ { 302 case itemElse: 303 return t.elseControl() 304 case itemEnd: 305 return t.endControl() 306 case itemIf: 307 return t.ifControl() 308 case itemRange: 309 return t.rangeControl() 310 case itemTemplate: 311 return t.templateControl() 312 case itemWith: 313 return t.withControl() 314 } 315 t.backup() 316 // Do not pop variables; they persist until "end". 317 return newAction(t.lex.lineNumber(), t.pipeline("command")) 318 } 319 320 // Pipeline: 321 // field or command 322 // pipeline "|" pipeline 323 func (t *Tree) pipeline(context string) (pipe *PipeNode) { 324 var decl []*VariableNode 325 // Are there declarations? 326 for { 327 if v := t.peek(); v.typ == itemVariable { 328 t.next() 329 if next := t.peek(); next.typ == itemColonEquals || (next.typ == itemChar && next.val == ",") { 330 t.next() 331 variable := newVariable(v.val) 332 if len(variable.Ident) != 1 { 333 t.errorf("illegal variable in declaration: %s", v.val) 334 } 335 decl = append(decl, variable) 336 t.vars = append(t.vars, v.val) 337 if next.typ == itemChar && next.val == "," { 338 if context == "range" && len(decl) < 2 { 339 continue 340 } 341 t.errorf("too many declarations in %s", context) 342 } 343 } else { 344 t.backup2(v) 345 } 346 } 347 break 348 } 349 pipe = newPipeline(t.lex.lineNumber(), decl) 350 for { 351 switch token := t.next(); token.typ { 352 case itemRightDelim: 353 if len(pipe.Cmds) == 0 { 354 t.errorf("missing value for %s", context) 355 } 356 return 357 case itemBool, itemCharConstant, itemComplex, itemDot, itemField, itemIdentifier, 358 itemVariable, itemNumber, itemRawString, itemString: 359 t.backup() 360 pipe.append(t.command()) 361 default: 362 t.unexpected(token, context) 363 } 364 } 365 return 366 } 367 368 func (t *Tree) parseControl(context string) (lineNum int, pipe *PipeNode, list, elseList *ListNode) { 369 lineNum = t.lex.lineNumber() 370 defer t.popVars(len(t.vars)) 371 pipe = t.pipeline(context) 372 var next Node 373 list, next = t.itemList() 374 switch next.Type() { 375 case nodeEnd: //done 376 case nodeElse: 377 elseList, next = t.itemList() 378 if next.Type() != nodeEnd { 379 t.errorf("expected end; found %s", next) 380 } 381 elseList = elseList 382 } 383 return lineNum, pipe, list, elseList 384 } 385 386 // If: 387 // {{if pipeline}} itemList {{end}} 388 // {{if pipeline}} itemList {{else}} itemList {{end}} 389 // If keyword is past. 390 func (t *Tree) ifControl() Node { 391 return newIf(t.parseControl("if")) 392 } 393 394 // Range: 395 // {{range pipeline}} itemList {{end}} 396 // {{range pipeline}} itemList {{else}} itemList {{end}} 397 // Range keyword is past. 398 func (t *Tree) rangeControl() Node { 399 return newRange(t.parseControl("range")) 400 } 401 402 // With: 403 // {{with pipeline}} itemList {{end}} 404 // {{with pipeline}} itemList {{else}} itemList {{end}} 405 // If keyword is past. 406 func (t *Tree) withControl() Node { 407 return newWith(t.parseControl("with")) 408 } 409 410 // End: 411 // {{end}} 412 // End keyword is past. 413 func (t *Tree) endControl() Node { 414 t.expect(itemRightDelim, "end") 415 return newEnd() 416 } 417 418 // Else: 419 // {{else}} 420 // Else keyword is past. 421 func (t *Tree) elseControl() Node { 422 t.expect(itemRightDelim, "else") 423 return newElse(t.lex.lineNumber()) 424 } 425 426 // Template: 427 // {{template stringValue pipeline}} 428 // Template keyword is past. The name must be something that can evaluate 429 // to a string. 430 func (t *Tree) templateControl() Node { 431 var name string 432 switch token := t.next(); token.typ { 433 case itemString, itemRawString: 434 s, err := strconv.Unquote(token.val) 435 if err != nil { 436 t.error(err) 437 } 438 name = s 439 default: 440 t.unexpected(token, "template invocation") 441 } 442 var pipe *PipeNode 443 if t.next().typ != itemRightDelim { 444 t.backup() 445 // Do not pop variables; they persist until "end". 446 pipe = t.pipeline("template") 447 } 448 return newTemplate(t.lex.lineNumber(), name, pipe) 449 } 450 451 // command: 452 // space-separated arguments up to a pipeline character or right delimiter. 453 // we consume the pipe character but leave the right delim to terminate the action. 454 func (t *Tree) command() *CommandNode { 455 cmd := newCommand() 456 Loop: 457 for { 458 switch token := t.next(); token.typ { 459 case itemRightDelim: 460 t.backup() 461 break Loop 462 case itemPipe: 463 break Loop 464 case itemError: 465 t.errorf("%s", token.val) 466 case itemIdentifier: 467 if !t.hasFunction(token.val) { 468 t.errorf("function %q not defined", token.val) 469 } 470 cmd.append(NewIdentifier(token.val)) 471 case itemDot: 472 cmd.append(newDot()) 473 case itemVariable: 474 cmd.append(t.useVar(token.val)) 475 case itemField: 476 cmd.append(newField(token.val)) 477 case itemBool: 478 cmd.append(newBool(token.val == "true")) 479 case itemCharConstant, itemComplex, itemNumber: 480 number, err := newNumber(token.val, token.typ) 481 if err != nil { 482 t.error(err) 483 } 484 cmd.append(number) 485 case itemString, itemRawString: 486 s, err := strconv.Unquote(token.val) 487 if err != nil { 488 t.error(err) 489 } 490 cmd.append(newString(token.val, s)) 491 default: 492 t.unexpected(token, "command") 493 } 494 } 495 if len(cmd.Args) == 0 { 496 t.errorf("empty command") 497 } 498 return cmd 499 } 500 501 // hasFunction reports if a function name exists in the Tree's maps. 502 func (t *Tree) hasFunction(name string) bool { 503 for _, funcMap := range t.funcs { 504 if funcMap == nil { 505 continue 506 } 507 if funcMap[name] != nil { 508 return true 509 } 510 } 511 return false 512 } 513 514 // popVars trims the variable list to the specified length 515 func (t *Tree) popVars(n int) { 516 t.vars = t.vars[:n] 517 } 518 519 // useVar returns a node for a variable reference. It errors if the 520 // variable is not defined. 521 func (t *Tree) useVar(name string) Node { 522 v := newVariable(name) 523 for _, varName := range t.vars { 524 if varName == v.Ident[0] { 525 return v 526 } 527 } 528 t.errorf("undefined variable %q", v.Ident[0]) 529 return nil 530 }