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	}