libgo/go/old/template/parse.go

   1 // Copyright 2009 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 // Code to parse a template.
   6
   7 package template
   8
   9 import (
  10         "fmt"
  11         "io"
  12         "io/ioutil"
  13         "os"
  14         "reflect"
  15         "strconv"
  16         "strings"
  17         "unicode"
  18         "utf8"
  19 )
  20
  21 // Errors returned during parsing and execution.  Users may extract the information and reformat
  22 // if they desire.
  23 type Error struct {
  24         Line int
  25         Msg  string
  26 }
  27
  28 func (e *Error) String() string { return fmt.Sprintf("line %d: %s", e.Line, e.Msg) }
  29
  30 // checkError is a deferred function to turn a panic with type *Error into a plain error return.
  31 // Other panics are unexpected and so are re-enabled.
  32 func checkError(error *os.Error) {
  33         if v := recover(); v != nil {
  34                 if e, ok := v.(*Error); ok {
  35                         *error = e
  36                 } else {
  37                         // runtime errors should crash
  38                         panic(v)
  39                 }
  40         }
  41 }
  42
  43 // Most of the literals are aces.
  44 var lbrace = []byte{'{'}
  45 var rbrace = []byte{'}'}
  46 var space = []byte{' '}
  47 var tab = []byte{'\t'}
  48
  49 // The various types of "tokens", which are plain text or (usually) brace-delimited descriptors
  50 const (
  51         tokAlternates = iota
  52         tokComment
  53         tokEnd
  54         tokLiteral
  55         tokOr
  56         tokRepeated
  57         tokSection
  58         tokText
  59         tokVariable
  60 )
  61
  62 // FormatterMap is the type describing the mapping from formatter
  63 // names to the functions that implement them.
  64 type FormatterMap map[string]func(io.Writer, string, ...interface{})
  65
  66 // Built-in formatters.
  67 var builtins = FormatterMap{
  68         "html": HTMLFormatter,
  69         "str":  StringFormatter,
  70         "":     StringFormatter,
  71 }
  72
  73 // The parsed state of a template is a vector of xxxElement structs.
  74 // Sections have line numbers so errors can be reported better during execution.
  75
  76 // Plain text.
  77 type textElement struct {
  78         text []byte
  79 }
  80
  81 // A literal such as .meta-left or .meta-right
  82 type literalElement struct {
  83         text []byte
  84 }
  85
  86 // A variable invocation to be evaluated
  87 type variableElement struct {
  88         linenum int
  89         args    []interface{} // The fields and literals in the invocation.
  90         fmts    []string      // Names of formatters to apply. len(fmts) > 0
  91 }
  92
  93 // A variableElement arg to be evaluated as a field name
  94 type fieldName string
  95
  96 // A .section block, possibly with a .or
  97 type sectionElement struct {
  98         linenum int    // of .section itself
  99         field   string // cursor field for this block
 100         start   int    // first element
 101         or      int    // first element of .or block
 102         end     int    // one beyond last element
 103 }
 104
 105 // A .repeated block, possibly with a .or and a .alternates
 106 type repeatedElement struct {
 107         sectionElement     // It has the same structure...
 108         altstart       int // ... except for alternates
 109         altend         int
 110 }
 111
 112 // Template is the type that represents a template definition.
 113 // It is unchanged after parsing.
 114 type Template struct {
 115         fmap FormatterMap // formatters for variables
 116         // Used during parsing:
 117         ldelim, rdelim []byte // delimiters; default {}
 118         buf            []byte // input text to process
 119         p              int    // position in buf
 120         linenum        int    // position in input
 121         // Parsed results:
 122         elems []interface{}
 123 }
 124
 125 // New creates a new template with the specified formatter map (which
 126 // may be nil) to define auxiliary functions for formatting variables.
 127 func New(fmap FormatterMap) *Template {
 128         t := new(Template)
 129         t.fmap = fmap
 130         t.ldelim = lbrace
 131         t.rdelim = rbrace
 132         t.elems = make([]interface{}, 0, 16)
 133         return t
 134 }
 135
 136 // Report error and stop executing.  The line number must be provided explicitly.
 137 func (t *Template) execError(st *state, line int, err string, args ...interface{}) {
 138         panic(&Error{line, fmt.Sprintf(err, args...)})
 139 }
 140
 141 // Report error, panic to terminate parsing.
 142 // The line number comes from the template state.
 143 func (t *Template) parseError(err string, args ...interface{}) {
 144         panic(&Error{t.linenum, fmt.Sprintf(err, args...)})
 145 }
 146
 147 // Is this an exported - upper case - name?
 148 func isExported(name string) bool {
 149         rune, _ := utf8.DecodeRuneInString(name)
 150         return unicode.IsUpper(rune)
 151 }
 152
 153 // -- Lexical analysis
 154
 155 // Is c a space character?
 156 func isSpace(c uint8) bool { return c == ' ' || c == '\t' || c == '\r' || c == '\n' }
 157
 158 // Safely, does s[n:n+len(t)] == t?
 159 func equal(s []byte, n int, t []byte) bool {
 160         b := s[n:]
 161         if len(t) > len(b) { // not enough space left for a match.
 162                 return false
 163         }
 164         for i, c := range t {
 165                 if c != b[i] {
 166                         return false
 167                 }
 168         }
 169         return true
 170 }
 171
 172 // isQuote returns true if c is a string- or character-delimiting quote character.
 173 func isQuote(c byte) bool {
 174         return c == '"' || c == '`' || c == '\''
 175 }
 176
 177 // endQuote returns the end quote index for the quoted string that
 178 // starts at n, or -1 if no matching end quote is found before the end
 179 // of the line.
 180 func endQuote(s []byte, n int) int {
 181         quote := s[n]
 182         for n++; n < len(s); n++ {
 183                 switch s[n] {
 184                 case '\\':
 185                         if quote == '"' || quote == '\'' {
 186                                 n++
 187                         }
 188                 case '\n':
 189                         return -1
 190                 case quote:
 191                         return n
 192                 }
 193         }
 194         return -1
 195 }
 196
 197 // nextItem returns the next item from the input buffer.  If the returned
 198 // item is empty, we are at EOF.  The item will be either a
 199 // delimited string or a non-empty string between delimited
 200 // strings. Tokens stop at (but include, if plain text) a newline.
 201 // Action tokens on a line by themselves drop any space on
 202 // either side, up to and including the newline.
 203 func (t *Template) nextItem() []byte {
 204         startOfLine := t.p == 0 || t.buf[t.p-1] == '\n'
 205         start := t.p
 206         var i int
 207         newline := func() {
 208                 t.linenum++
 209                 i++
 210         }
 211         // Leading space up to but not including newline
 212         for i = start; i < len(t.buf); i++ {
 213                 if t.buf[i] == '\n' || !isSpace(t.buf[i]) {
 214                         break
 215                 }
 216         }
 217         leadingSpace := i > start
 218         // What's left is nothing, newline, delimited string, or plain text
 219         switch {
 220         case i == len(t.buf):
 221                 // EOF; nothing to do
 222         case t.buf[i] == '\n':
 223                 newline()
 224         case equal(t.buf, i, t.ldelim):
 225                 left := i         // Start of left delimiter.
 226                 right := -1       // Will be (immediately after) right delimiter.
 227                 haveText := false // Delimiters contain text.
 228                 i += len(t.ldelim)
 229                 // Find the end of the action.
 230                 for ; i < len(t.buf); i++ {
 231                         if t.buf[i] == '\n' {
 232                                 break
 233                         }
 234                         if isQuote(t.buf[i]) {
 235                                 i = endQuote(t.buf, i)
 236                                 if i == -1 {
 237                                         t.parseError("unmatched quote")
 238                                         return nil
 239                                 }
 240                                 continue
 241                         }
 242                         if equal(t.buf, i, t.rdelim) {
 243                                 i += len(t.rdelim)
 244                                 right = i
 245                                 break
 246                         }
 247                         haveText = true
 248                 }
 249                 if right < 0 {
 250                         t.parseError("unmatched opening delimiter")
 251                         return nil
 252                 }
 253                 // Is this a special action (starts with '.' or '#') and the only thing on the line?
 254                 if startOfLine && haveText {
 255                         firstChar := t.buf[left+len(t.ldelim)]
 256                         if firstChar == '.' || firstChar == '#' {
 257                                 // It's special and the first thing on the line. Is it the last?
 258                                 for j := right; j < len(t.buf) && isSpace(t.buf[j]); j++ {
 259                                         if t.buf[j] == '\n' {
 260                                                 // Yes it is. Drop the surrounding space and return the {.foo}
 261                                                 t.linenum++
 262                                                 t.p = j + 1
 263                                                 return t.buf[left:right]
 264                                         }
 265                                 }
 266                         }
 267                 }
 268                 // No it's not. If there's leading space, return that.
 269                 if leadingSpace {
 270                         // not trimming space: return leading space if there is some.
 271                         t.p = left
 272                         return t.buf[start:left]
 273                 }
 274                 // Return the word, leave the trailing space.
 275                 start = left
 276                 break
 277         default:
 278                 for ; i < len(t.buf); i++ {
 279                         if t.buf[i] == '\n' {
 280                                 newline()
 281                                 break
 282                         }
 283                         if equal(t.buf, i, t.ldelim) {
 284                                 break
 285                         }
 286                 }
 287         }
 288         item := t.buf[start:i]
 289         t.p = i
 290         return item
 291 }
 292
 293 // Turn a byte array into a space-split array of strings,
 294 // taking into account quoted strings.
 295 func words(buf []byte) []string {
 296         s := make([]string, 0, 5)
 297         for i := 0; i < len(buf); {
 298                 // One word per loop
 299                 for i < len(buf) && isSpace(buf[i]) {
 300                         i++
 301                 }
 302                 if i == len(buf) {
 303                         break
 304                 }
 305                 // Got a word
 306                 start := i
 307                 if isQuote(buf[i]) {
 308                         i = endQuote(buf, i)
 309                         if i < 0 {
 310                                 i = len(buf)
 311                         } else {
 312                                 i++
 313                         }
 314                 }
 315                 // Even with quotes, break on space only.  This handles input
 316                 // such as {""|} and catches quoting mistakes.
 317                 for i < len(buf) && !isSpace(buf[i]) {
 318                         i++
 319                 }
 320                 s = append(s, string(buf[start:i]))
 321         }
 322         return s
 323 }
 324
 325 // Analyze an item and return its token type and, if it's an action item, an array of
 326 // its constituent words.
 327 func (t *Template) analyze(item []byte) (tok int, w []string) {
 328         // item is known to be non-empty
 329         if !equal(item, 0, t.ldelim) { // doesn't start with left delimiter
 330                 tok = tokText
 331                 return
 332         }
 333         if !equal(item, len(item)-len(t.rdelim), t.rdelim) { // doesn't end with right delimiter
 334                 t.parseError("internal error: unmatched opening delimiter") // lexing should prevent this
 335                 return
 336         }
 337         if len(item) <= len(t.ldelim)+len(t.rdelim) { // no contents
 338                 t.parseError("empty directive")
 339                 return
 340         }
 341         // Comment
 342         if item[len(t.ldelim)] == '#' {
 343                 tok = tokComment
 344                 return
 345         }
 346         // Split into words
 347         w = words(item[len(t.ldelim) : len(item)-len(t.rdelim)]) // drop final delimiter
 348         if len(w) == 0 {
 349                 t.parseError("empty directive")
 350                 return
 351         }
 352         first := w[0]
 353         if first[0] != '.' {
 354                 tok = tokVariable
 355                 return
 356         }
 357         if len(first) > 1 && first[1] >= '0' && first[1] <= '9' {
 358                 // Must be a float.
 359                 tok = tokVariable
 360                 return
 361         }
 362         switch first {
 363         case ".meta-left", ".meta-right", ".space", ".tab":
 364                 tok = tokLiteral
 365                 return
 366         case ".or":
 367                 tok = tokOr
 368                 return
 369         case ".end":
 370                 tok = tokEnd
 371                 return
 372         case ".section":
 373                 if len(w) != 2 {
 374                         t.parseError("incorrect fields for .section: %s", item)
 375                         return
 376                 }
 377                 tok = tokSection
 378                 return
 379         case ".repeated":
 380                 if len(w) != 3 || w[1] != "section" {
 381                         t.parseError("incorrect fields for .repeated: %s", item)
 382                         return
 383                 }
 384                 tok = tokRepeated
 385                 return
 386         case ".alternates":
 387                 if len(w) != 2 || w[1] != "with" {
 388                         t.parseError("incorrect fields for .alternates: %s", item)
 389                         return
 390                 }
 391                 tok = tokAlternates
 392                 return
 393         }
 394         t.parseError("bad directive: %s", item)
 395         return
 396 }
 397
 398 // formatter returns the Formatter with the given name in the Template, or nil if none exists.
 399 func (t *Template) formatter(name string) func(io.Writer, string, ...interface{}) {
 400         if t.fmap != nil {
 401                 if fn := t.fmap[name]; fn != nil {
 402                         return fn
 403                 }
 404         }
 405         return builtins[name]
 406 }
 407
 408 // -- Parsing
 409
 410 // newVariable allocates a new variable-evaluation element.
 411 func (t *Template) newVariable(words []string) *variableElement {
 412         formatters := extractFormatters(words)
 413         args := make([]interface{}, len(words))
 414
 415         // Build argument list, processing any literals
 416         for i, word := range words {
 417                 var lerr os.Error
 418                 switch word[0] {
 419                 case '"', '`', '\'':
 420                         v, err := strconv.Unquote(word)
 421                         if err == nil && word[0] == '\'' {
 422                                 args[i] = []int(v)[0]
 423                         } else {
 424                                 args[i], lerr = v, err
 425                         }
 426
 427                 case '.', '+', '-', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
 428                         v, err := strconv.Btoi64(word, 0)
 429                         if err == nil {
 430                                 args[i] = v
 431                         } else {
 432                                 v, err := strconv.Atof64(word)
 433                                 args[i], lerr = v, err
 434                         }
 435
 436                 default:
 437                         args[i] = fieldName(word)
 438                 }
 439                 if lerr != nil {
 440                         t.parseError("invalid literal: %q: %s", word, lerr)
 441                 }
 442         }
 443
 444         // We could remember the function address here and avoid the lookup later,
 445         // but it's more dynamic to let the user change the map contents underfoot.
 446         // We do require the name to be present, though.
 447
 448         // Is it in user-supplied map?
 449         for _, f := range formatters {
 450                 if t.formatter(f) == nil {
 451                         t.parseError("unknown formatter: %q", f)
 452                 }
 453         }
 454
 455         return &variableElement{t.linenum, args, formatters}
 456 }
 457
 458 // extractFormatters extracts a list of formatters from words.
 459 // After the final space-separated argument in a variable, formatters may be
 460 // specified separated by pipe symbols. For example: {a b c|d|e}
 461 // The words parameter still has the formatters joined by '|' in the last word.
 462 // extractFormatters splits formatters, replaces the last word with the content
 463 // found before the first '|' within it, and returns the formatters obtained.
 464 // If no formatters are found in words, the default formatter is returned.
 465 func extractFormatters(words []string) (formatters []string) {
 466         // "" is the default formatter.
 467         formatters = []string{""}
 468         if len(words) == 0 {
 469                 return
 470         }
 471         var bar int
 472         lastWord := words[len(words)-1]
 473         if isQuote(lastWord[0]) {
 474                 end := endQuote([]byte(lastWord), 0)
 475                 if end < 0 || end+1 == len(lastWord) || lastWord[end+1] != '|' {
 476                         return
 477                 }
 478                 bar = end + 1
 479         } else {
 480                 bar = strings.IndexRune(lastWord, '|')
 481                 if bar < 0 {
 482                         return
 483                 }
 484         }
 485         words[len(words)-1] = lastWord[0:bar]
 486         formatters = strings.Split(lastWord[bar+1:], "|")
 487         return
 488 }
 489
 490 // Grab the next item.  If it's simple, just append it to the template.
 491 // Otherwise return its details.
 492 func (t *Template) parseSimple(item []byte) (done bool, tok int, w []string) {
 493         tok, w = t.analyze(item)
 494         done = true // assume for simplicity
 495         switch tok {
 496         case tokComment:
 497                 return
 498         case tokText:
 499                 t.elems = append(t.elems, &textElement{item})
 500                 return
 501         case tokLiteral:
 502                 switch w[0] {
 503                 case ".meta-left":
 504                         t.elems = append(t.elems, &literalElement{t.ldelim})
 505                 case ".meta-right":
 506                         t.elems = append(t.elems, &literalElement{t.rdelim})
 507                 case ".space":
 508                         t.elems = append(t.elems, &literalElement{space})
 509                 case ".tab":
 510                         t.elems = append(t.elems, &literalElement{tab})
 511                 default:
 512                         t.parseError("internal error: unknown literal: %s", w[0])
 513                 }
 514                 return
 515         case tokVariable:
 516                 t.elems = append(t.elems, t.newVariable(w))
 517                 return
 518         }
 519         return false, tok, w
 520 }
 521
 522 // parseRepeated and parseSection are mutually recursive
 523
 524 func (t *Template) parseRepeated(words []string) *repeatedElement {
 525         r := new(repeatedElement)
 526         t.elems = append(t.elems, r)
 527         r.linenum = t.linenum
 528         r.field = words[2]
 529         // Scan section, collecting true and false (.or) blocks.
 530         r.start = len(t.elems)
 531         r.or = -1
 532         r.altstart = -1
 533         r.altend = -1
 534 Loop:
 535         for {
 536                 item := t.nextItem()
 537                 if len(item) == 0 {
 538                         t.parseError("missing .end for .repeated section")
 539                         break
 540                 }
 541                 done, tok, w := t.parseSimple(item)
 542                 if done {
 543                         continue
 544                 }
 545                 switch tok {
 546                 case tokEnd:
 547                         break Loop
 548                 case tokOr:
 549                         if r.or >= 0 {
 550                                 t.parseError("extra .or in .repeated section")
 551                                 break Loop
 552                         }
 553                         r.altend = len(t.elems)
 554                         r.or = len(t.elems)
 555                 case tokSection:
 556                         t.parseSection(w)
 557                 case tokRepeated:
 558                         t.parseRepeated(w)
 559                 case tokAlternates:
 560                         if r.altstart >= 0 {
 561                                 t.parseError("extra .alternates in .repeated section")
 562                                 break Loop
 563                         }
 564                         if r.or >= 0 {
 565                                 t.parseError(".alternates inside .or block in .repeated section")
 566                                 break Loop
 567                         }
 568                         r.altstart = len(t.elems)
 569                 default:
 570                         t.parseError("internal error: unknown repeated section item: %s", item)
 571                         break Loop
 572                 }
 573         }
 574         if r.altend < 0 {
 575                 r.altend = len(t.elems)
 576         }
 577         r.end = len(t.elems)
 578         return r
 579 }
 580
 581 func (t *Template) parseSection(words []string) *sectionElement {
 582         s := new(sectionElement)
 583         t.elems = append(t.elems, s)
 584         s.linenum = t.linenum
 585         s.field = words[1]
 586         // Scan section, collecting true and false (.or) blocks.
 587         s.start = len(t.elems)
 588         s.or = -1
 589 Loop:
 590         for {
 591                 item := t.nextItem()
 592                 if len(item) == 0 {
 593                         t.parseError("missing .end for .section")
 594                         break
 595                 }
 596                 done, tok, w := t.parseSimple(item)
 597                 if done {
 598                         continue
 599                 }
 600                 switch tok {
 601                 case tokEnd:
 602                         break Loop
 603                 case tokOr:
 604                         if s.or >= 0 {
 605                                 t.parseError("extra .or in .section")
 606                                 break Loop
 607                         }
 608                         s.or = len(t.elems)
 609                 case tokSection:
 610                         t.parseSection(w)
 611                 case tokRepeated:
 612                         t.parseRepeated(w)
 613                 case tokAlternates:
 614                         t.parseError(".alternates not in .repeated")
 615                 default:
 616                         t.parseError("internal error: unknown section item: %s", item)
 617                 }
 618         }
 619         s.end = len(t.elems)
 620         return s
 621 }
 622
 623 func (t *Template) parse() {
 624         for {
 625                 item := t.nextItem()
 626                 if len(item) == 0 {
 627                         break
 628                 }
 629                 done, tok, w := t.parseSimple(item)
 630                 if done {
 631                         continue
 632                 }
 633                 switch tok {
 634                 case tokOr, tokEnd, tokAlternates:
 635                         t.parseError("unexpected %s", w[0])
 636                 case tokSection:
 637                         t.parseSection(w)
 638                 case tokRepeated:
 639                         t.parseRepeated(w)
 640                 default:
 641                         t.parseError("internal error: bad directive in parse: %s", item)
 642                 }
 643         }
 644 }
 645
 646 // -- Execution
 647
 648 // -- Public interface
 649
 650 // Parse initializes a Template by parsing its definition.  The string
 651 // s contains the template text.  If any errors occur, Parse returns
 652 // the error.
 653 func (t *Template) Parse(s string) (err os.Error) {
 654         if t.elems == nil {
 655                 return &Error{1, "template not allocated with New"}
 656         }
 657         if !validDelim(t.ldelim) || !validDelim(t.rdelim) {
 658                 return &Error{1, fmt.Sprintf("bad delimiter strings %q %q", t.ldelim, t.rdelim)}
 659         }
 660         defer checkError(&err)
 661         t.buf = []byte(s)
 662         t.p = 0
 663         t.linenum = 1
 664         t.parse()
 665         return nil
 666 }
 667
 668 // ParseFile is like Parse but reads the template definition from the
 669 // named file.
 670 func (t *Template) ParseFile(filename string) (err os.Error) {
 671         b, err := ioutil.ReadFile(filename)
 672         if err != nil {
 673                 return err
 674         }
 675         return t.Parse(string(b))
 676 }
 677
 678 // Execute applies a parsed template to the specified data object,
 679 // generating output to wr.
 680 func (t *Template) Execute(wr io.Writer, data interface{}) (err os.Error) {
 681         // Extract the driver data.
 682         val := reflect.ValueOf(data)
 683         defer checkError(&err)
 684         t.p = 0
 685         t.execute(0, len(t.elems), &state{parent: nil, data: val, wr: wr})
 686         return nil
 687 }
 688
 689 // SetDelims sets the left and right delimiters for operations in the
 690 // template.  They are validated during parsing.  They could be
 691 // validated here but it's better to keep the routine simple.  The
 692 // delimiters are very rarely invalid and Parse has the necessary
 693 // error-handling interface already.
 694 func (t *Template) SetDelims(left, right string) {
 695         t.ldelim = []byte(left)
 696         t.rdelim = []byte(right)
 697 }
 698
 699 // Parse creates a Template with default parameters (such as {} for
 700 // metacharacters).  The string s contains the template text while
 701 // the formatter map fmap, which may be nil, defines auxiliary functions
 702 // for formatting variables.  The template is returned. If any errors
 703 // occur, err will be non-nil.
 704 func Parse(s string, fmap FormatterMap) (t *Template, err os.Error) {
 705         t = New(fmap)
 706         err = t.Parse(s)
 707         if err != nil {
 708                 t = nil
 709         }
 710         return
 711 }
 712
 713 // ParseFile is a wrapper function that creates a Template with default
 714 // parameters (such as {} for metacharacters).  The filename identifies
 715 // a file containing the template text, while the formatter map fmap, which
 716 // may be nil, defines auxiliary functions for formatting variables.
 717 // The template is returned. If any errors occur, err will be non-nil.
 718 func ParseFile(filename string, fmap FormatterMap) (t *Template, err os.Error) {
 719         b, err := ioutil.ReadFile(filename)
 720         if err != nil {
 721                 return nil, err
 722         }
 723         return Parse(string(b), fmap)
 724 }
 725
 726 // MustParse is like Parse but panics if the template cannot be parsed.
 727 func MustParse(s string, fmap FormatterMap) *Template {
 728         t, err := Parse(s, fmap)
 729         if err != nil {
 730                 panic("template.MustParse error: " + err.String())
 731         }
 732         return t
 733 }
 734
 735 // MustParseFile is like ParseFile but panics if the file cannot be read
 736 // or the template cannot be parsed.
 737 func MustParseFile(filename string, fmap FormatterMap) *Template {
 738         b, err := ioutil.ReadFile(filename)
 739         if err != nil {
 740                 panic("template.MustParseFile error: " + err.String())
 741         }
 742         return MustParse(string(b), fmap)
 743 }