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// Parse nodes. 6 7package parse 8 9import ( 10 "bytes" 11 "fmt" 12 "strconv" 13 "strings" 14) 15 16var textFormat = "%s" // Changed to "%q" in tests for better error messages. 17 18// A Node is an element in the parse tree. The interface is trivial. 19// The interface contains an unexported method so that only 20// types local to this package can satisfy it. 21type Node interface { 22 Type() NodeType 23 String() string 24 // Copy does a deep copy of the Node and all its components. 25 // To avoid type assertions, some XxxNodes also have specialized 26 // CopyXxx methods that return *XxxNode. 27 Copy() Node 28 Position() Pos // byte position of start of node in full original input string 29 // Make sure only functions in this package can create Nodes. 30 unexported() 31} 32 33// NodeType identifies the type of a parse tree node. 34type NodeType int 35 36// Pos represents a byte position in the original input text from which 37// this template was parsed. 38type Pos int 39 40func (p Pos) Position() Pos { 41 return p 42} 43 44// unexported keeps Node implementations local to the package. 45// All implementations embed Pos, so this takes care of it. 46func (Pos) unexported() { 47} 48 49// Type returns itself and provides an easy default implementation 50// for embedding in a Node. Embedded in all non-trivial Nodes. 51func (t NodeType) Type() NodeType { 52 return t 53} 54 55const ( 56 NodeText NodeType = iota // Plain text. 57 NodeAction // A non-control action such as a field evaluation. 58 NodeBool // A boolean constant. 59 NodeChain // A sequence of field accesses. 60 NodeCommand // An element of a pipeline. 61 NodeDot // The cursor, dot. 62 nodeElse // An else action. Not added to tree. 63 nodeEnd // An end action. Not added to tree. 64 NodeField // A field or method name. 65 NodeIdentifier // An identifier; always a function name. 66 NodeIf // An if action. 67 NodeList // A list of Nodes. 68 NodeNil // An untyped nil constant. 69 NodeNumber // A numerical constant. 70 NodePipe // A pipeline of commands. 71 NodeRange // A range action. 72 NodeString // A string constant. 73 NodeTemplate // A template invocation action. 74 NodeVariable // A $ variable. 75 NodeWith // A with action. 76) 77 78// Nodes. 79 80// ListNode holds a sequence of nodes. 81type ListNode struct { 82 NodeType 83 Pos 84 Nodes []Node // The element nodes in lexical order. 85} 86 87func newList(pos Pos) *ListNode { 88 return &ListNode{NodeType: NodeList, Pos: pos} 89} 90 91func (l *ListNode) append(n Node) { 92 l.Nodes = append(l.Nodes, n) 93} 94 95func (l *ListNode) String() string { 96 b := new(bytes.Buffer) 97 for _, n := range l.Nodes { 98 fmt.Fprint(b, n) 99 } 100 return b.String() 101} 102 103func (l *ListNode) CopyList() *ListNode { 104 if l == nil { 105 return l 106 } 107 n := newList(l.Pos) 108 for _, elem := range l.Nodes { 109 n.append(elem.Copy()) 110 } 111 return n 112} 113 114func (l *ListNode) Copy() Node { 115 return l.CopyList() 116} 117 118// TextNode holds plain text. 119type TextNode struct { 120 NodeType 121 Pos 122 Text []byte // The text; may span newlines. 123} 124 125func newText(pos Pos, text string) *TextNode { 126 return &TextNode{NodeType: NodeText, Pos: pos, Text: []byte(text)} 127} 128 129func (t *TextNode) String() string { 130 return fmt.Sprintf(textFormat, t.Text) 131} 132 133func (t *TextNode) Copy() Node { 134 return &TextNode{NodeType: NodeText, Text: append([]byte{}, t.Text...)} 135} 136 137// PipeNode holds a pipeline with optional declaration 138type PipeNode struct { 139 NodeType 140 Pos 141 Line int // The line number in the input (deprecated; kept for compatibility) 142 Decl []*VariableNode // Variable declarations in lexical order. 143 Cmds []*CommandNode // The commands in lexical order. 144} 145 146func newPipeline(pos Pos, line int, decl []*VariableNode) *PipeNode { 147 return &PipeNode{NodeType: NodePipe, Pos: pos, Line: line, Decl: decl} 148} 149 150func (p *PipeNode) append(command *CommandNode) { 151 p.Cmds = append(p.Cmds, command) 152} 153 154func (p *PipeNode) String() string { 155 s := "" 156 if len(p.Decl) > 0 { 157 for i, v := range p.Decl { 158 if i > 0 { 159 s += ", " 160 } 161 s += v.String() 162 } 163 s += " := " 164 } 165 for i, c := range p.Cmds { 166 if i > 0 { 167 s += " | " 168 } 169 s += c.String() 170 } 171 return s 172} 173 174func (p *PipeNode) CopyPipe() *PipeNode { 175 if p == nil { 176 return p 177 } 178 var decl []*VariableNode 179 for _, d := range p.Decl { 180 decl = append(decl, d.Copy().(*VariableNode)) 181 } 182 n := newPipeline(p.Pos, p.Line, decl) 183 for _, c := range p.Cmds { 184 n.append(c.Copy().(*CommandNode)) 185 } 186 return n 187} 188 189func (p *PipeNode) Copy() Node { 190 return p.CopyPipe() 191} 192 193// ActionNode holds an action (something bounded by delimiters). 194// Control actions have their own nodes; ActionNode represents simple 195// ones such as field evaluations and parenthesized pipelines. 196type ActionNode struct { 197 NodeType 198 Pos 199 Line int // The line number in the input (deprecated; kept for compatibility) 200 Pipe *PipeNode // The pipeline in the action. 201} 202 203func newAction(pos Pos, line int, pipe *PipeNode) *ActionNode { 204 return &ActionNode{NodeType: NodeAction, Pos: pos, Line: line, Pipe: pipe} 205} 206 207func (a *ActionNode) String() string { 208 return fmt.Sprintf("{{%s}}", a.Pipe) 209 210} 211 212func (a *ActionNode) Copy() Node { 213 return newAction(a.Pos, a.Line, a.Pipe.CopyPipe()) 214 215} 216 217// CommandNode holds a command (a pipeline inside an evaluating action). 218type CommandNode struct { 219 NodeType 220 Pos 221 Args []Node // Arguments in lexical order: Identifier, field, or constant. 222} 223 224func newCommand(pos Pos) *CommandNode { 225 return &CommandNode{NodeType: NodeCommand, Pos: pos} 226} 227 228func (c *CommandNode) append(arg Node) { 229 c.Args = append(c.Args, arg) 230} 231 232func (c *CommandNode) String() string { 233 s := "" 234 for i, arg := range c.Args { 235 if i > 0 { 236 s += " " 237 } 238 if arg, ok := arg.(*PipeNode); ok { 239 s += "(" + arg.String() + ")" 240 continue 241 } 242 s += arg.String() 243 } 244 return s 245} 246 247func (c *CommandNode) Copy() Node { 248 if c == nil { 249 return c 250 } 251 n := newCommand(c.Pos) 252 for _, c := range c.Args { 253 n.append(c.Copy()) 254 } 255 return n 256} 257 258// IdentifierNode holds an identifier. 259type IdentifierNode struct { 260 NodeType 261 Pos 262 Ident string // The identifier's name. 263} 264 265// NewIdentifier returns a new IdentifierNode with the given identifier name. 266func NewIdentifier(ident string) *IdentifierNode { 267 return &IdentifierNode{NodeType: NodeIdentifier, Ident: ident} 268} 269 270// SetPos sets the position. NewIdentifier is a public method so we can't modify its signature. 271// Chained for convenience. 272// TODO: fix one day? 273func (i *IdentifierNode) SetPos(pos Pos) *IdentifierNode { 274 i.Pos = pos 275 return i 276} 277 278func (i *IdentifierNode) String() string { 279 return i.Ident 280} 281 282func (i *IdentifierNode) Copy() Node { 283 return NewIdentifier(i.Ident).SetPos(i.Pos) 284} 285 286// VariableNode holds a list of variable names, possibly with chained field 287// accesses. The dollar sign is part of the (first) name. 288type VariableNode struct { 289 NodeType 290 Pos 291 Ident []string // Variable name and fields in lexical order. 292} 293 294func newVariable(pos Pos, ident string) *VariableNode { 295 return &VariableNode{NodeType: NodeVariable, Pos: pos, Ident: strings.Split(ident, ".")} 296} 297 298func (v *VariableNode) String() string { 299 s := "" 300 for i, id := range v.Ident { 301 if i > 0 { 302 s += "." 303 } 304 s += id 305 } 306 return s 307} 308 309func (v *VariableNode) Copy() Node { 310 return &VariableNode{NodeType: NodeVariable, Pos: v.Pos, Ident: append([]string{}, v.Ident...)} 311} 312 313// DotNode holds the special identifier '.'. 314type DotNode struct { 315 Pos 316} 317 318func newDot(pos Pos) *DotNode { 319 return &DotNode{Pos: pos} 320} 321 322func (d *DotNode) Type() NodeType { 323 return NodeDot 324} 325 326func (d *DotNode) String() string { 327 return "." 328} 329 330func (d *DotNode) Copy() Node { 331 return newDot(d.Pos) 332} 333 334// NilNode holds the special identifier 'nil' representing an untyped nil constant. 335type NilNode struct { 336 Pos 337} 338 339func newNil(pos Pos) *NilNode { 340 return &NilNode{Pos: pos} 341} 342 343func (n *NilNode) Type() NodeType { 344 return NodeNil 345} 346 347func (n *NilNode) String() string { 348 return "nil" 349} 350 351func (n *NilNode) Copy() Node { 352 return newNil(n.Pos) 353} 354 355// FieldNode holds a field (identifier starting with '.'). 356// The names may be chained ('.x.y'). 357// The period is dropped from each ident. 358type FieldNode struct { 359 NodeType 360 Pos 361 Ident []string // The identifiers in lexical order. 362} 363 364func newField(pos Pos, ident string) *FieldNode { 365 return &FieldNode{NodeType: NodeField, Pos: pos, Ident: strings.Split(ident[1:], ".")} // [1:] to drop leading period 366} 367 368func (f *FieldNode) String() string { 369 s := "" 370 for _, id := range f.Ident { 371 s += "." + id 372 } 373 return s 374} 375 376func (f *FieldNode) Copy() Node { 377 return &FieldNode{NodeType: NodeField, Pos: f.Pos, Ident: append([]string{}, f.Ident...)} 378} 379 380// ChainNode holds a term followed by a chain of field accesses (identifier starting with '.'). 381// The names may be chained ('.x.y'). 382// The periods are dropped from each ident. 383type ChainNode struct { 384 NodeType 385 Pos 386 Node Node 387 Field []string // The identifiers in lexical order. 388} 389 390func newChain(pos Pos, node Node) *ChainNode { 391 return &ChainNode{NodeType: NodeChain, Pos: pos, Node: node} 392} 393 394// Add adds the named field (which should start with a period) to the end of the chain. 395func (c *ChainNode) Add(field string) { 396 if len(field) == 0 || field[0] != '.' { 397 panic("no dot in field") 398 } 399 field = field[1:] // Remove leading dot. 400 if field == "" { 401 panic("empty field") 402 } 403 c.Field = append(c.Field, field) 404} 405 406func (c *ChainNode) String() string { 407 s := c.Node.String() 408 if _, ok := c.Node.(*PipeNode); ok { 409 s = "(" + s + ")" 410 } 411 for _, field := range c.Field { 412 s += "." + field 413 } 414 return s 415} 416 417func (c *ChainNode) Copy() Node { 418 return &ChainNode{NodeType: NodeChain, Pos: c.Pos, Node: c.Node, Field: append([]string{}, c.Field...)} 419} 420 421// BoolNode holds a boolean constant. 422type BoolNode struct { 423 NodeType 424 Pos 425 True bool // The value of the boolean constant. 426} 427 428func newBool(pos Pos, true bool) *BoolNode { 429 return &BoolNode{NodeType: NodeBool, Pos: pos, True: true} 430} 431 432func (b *BoolNode) String() string { 433 if b.True { 434 return "true" 435 } 436 return "false" 437} 438 439func (b *BoolNode) Copy() Node { 440 return newBool(b.Pos, b.True) 441} 442 443// NumberNode holds a number: signed or unsigned integer, float, or complex. 444// The value is parsed and stored under all the types that can represent the value. 445// This simulates in a small amount of code the behavior of Go's ideal constants. 446type NumberNode struct { 447 NodeType 448 Pos 449 IsInt bool // Number has an integral value. 450 IsUint bool // Number has an unsigned integral value. 451 IsFloat bool // Number has a floating-point value. 452 IsComplex bool // Number is complex. 453 Int64 int64 // The signed integer value. 454 Uint64 uint64 // The unsigned integer value. 455 Float64 float64 // The floating-point value. 456 Complex128 complex128 // The complex value. 457 Text string // The original textual representation from the input. 458} 459 460func newNumber(pos Pos, text string, typ itemType) (*NumberNode, error) { 461 n := &NumberNode{NodeType: NodeNumber, Pos: pos, Text: text} 462 switch typ { 463 case itemCharConstant: 464 rune, _, tail, err := strconv.UnquoteChar(text[1:], text[0]) 465 if err != nil { 466 return nil, err 467 } 468 if tail != "'" { 469 return nil, fmt.Errorf("malformed character constant: %s", text) 470 } 471 n.Int64 = int64(rune) 472 n.IsInt = true 473 n.Uint64 = uint64(rune) 474 n.IsUint = true 475 n.Float64 = float64(rune) // odd but those are the rules. 476 n.IsFloat = true 477 return n, nil 478 case itemComplex: 479 // fmt.Sscan can parse the pair, so let it do the work. 480 if _, err := fmt.Sscan(text, &n.Complex128); err != nil { 481 return nil, err 482 } 483 n.IsComplex = true 484 n.simplifyComplex() 485 return n, nil 486 } 487 // Imaginary constants can only be complex unless they are zero. 488 if len(text) > 0 && text[len(text)-1] == 'i' { 489 f, err := strconv.ParseFloat(text[:len(text)-1], 64) 490 if err == nil { 491 n.IsComplex = true 492 n.Complex128 = complex(0, f) 493 n.simplifyComplex() 494 return n, nil 495 } 496 } 497 // Do integer test first so we get 0x123 etc. 498 u, err := strconv.ParseUint(text, 0, 64) // will fail for -0; fixed below. 499 if err == nil { 500 n.IsUint = true 501 n.Uint64 = u 502 } 503 i, err := strconv.ParseInt(text, 0, 64) 504 if err == nil { 505 n.IsInt = true 506 n.Int64 = i 507 if i == 0 { 508 n.IsUint = true // in case of -0. 509 n.Uint64 = u 510 } 511 } 512 // If an integer extraction succeeded, promote the float. 513 if n.IsInt { 514 n.IsFloat = true 515 n.Float64 = float64(n.Int64) 516 } else if n.IsUint { 517 n.IsFloat = true 518 n.Float64 = float64(n.Uint64) 519 } else { 520 f, err := strconv.ParseFloat(text, 64) 521 if err == nil { 522 n.IsFloat = true 523 n.Float64 = f 524 // If a floating-point extraction succeeded, extract the int if needed. 525 if !n.IsInt && float64(int64(f)) == f { 526 n.IsInt = true 527 n.Int64 = int64(f) 528 } 529 if !n.IsUint && float64(uint64(f)) == f { 530 n.IsUint = true 531 n.Uint64 = uint64(f) 532 } 533 } 534 } 535 if !n.IsInt && !n.IsUint && !n.IsFloat { 536 return nil, fmt.Errorf("illegal number syntax: %q", text) 537 } 538 return n, nil 539} 540 541// simplifyComplex pulls out any other types that are represented by the complex number. 542// These all require that the imaginary part be zero. 543func (n *NumberNode) simplifyComplex() { 544 n.IsFloat = imag(n.Complex128) == 0 545 if n.IsFloat { 546 n.Float64 = real(n.Complex128) 547 n.IsInt = float64(int64(n.Float64)) == n.Float64 548 if n.IsInt { 549 n.Int64 = int64(n.Float64) 550 } 551 n.IsUint = float64(uint64(n.Float64)) == n.Float64 552 if n.IsUint { 553 n.Uint64 = uint64(n.Float64) 554 } 555 } 556} 557 558func (n *NumberNode) String() string { 559 return n.Text 560} 561 562func (n *NumberNode) Copy() Node { 563 nn := new(NumberNode) 564 *nn = *n // Easy, fast, correct. 565 return nn 566} 567 568// StringNode holds a string constant. The value has been "unquoted". 569type StringNode struct { 570 NodeType 571 Pos 572 Quoted string // The original text of the string, with quotes. 573 Text string // The string, after quote processing. 574} 575 576func newString(pos Pos, orig, text string) *StringNode { 577 return &StringNode{NodeType: NodeString, Pos: pos, Quoted: orig, Text: text} 578} 579 580func (s *StringNode) String() string { 581 return s.Quoted 582} 583 584func (s *StringNode) Copy() Node { 585 return newString(s.Pos, s.Quoted, s.Text) 586} 587 588// endNode represents an {{end}} action. 589// It does not appear in the final parse tree. 590type endNode struct { 591 Pos 592} 593 594func newEnd(pos Pos) *endNode { 595 return &endNode{Pos: pos} 596} 597 598func (e *endNode) Type() NodeType { 599 return nodeEnd 600} 601 602func (e *endNode) String() string { 603 return "{{end}}" 604} 605 606func (e *endNode) Copy() Node { 607 return newEnd(e.Pos) 608} 609 610// elseNode represents an {{else}} action. Does not appear in the final tree. 611type elseNode struct { 612 NodeType 613 Pos 614 Line int // The line number in the input (deprecated; kept for compatibility) 615} 616 617func newElse(pos Pos, line int) *elseNode { 618 return &elseNode{NodeType: nodeElse, Pos: pos, Line: line} 619} 620 621func (e *elseNode) Type() NodeType { 622 return nodeElse 623} 624 625func (e *elseNode) String() string { 626 return "{{else}}" 627} 628 629func (e *elseNode) Copy() Node { 630 return newElse(e.Pos, e.Line) 631} 632 633// BranchNode is the common representation of if, range, and with. 634type BranchNode struct { 635 NodeType 636 Pos 637 Line int // The line number in the input (deprecated; kept for compatibility) 638 Pipe *PipeNode // The pipeline to be evaluated. 639 List *ListNode // What to execute if the value is non-empty. 640 ElseList *ListNode // What to execute if the value is empty (nil if absent). 641} 642 643func (b *BranchNode) String() string { 644 name := "" 645 switch b.NodeType { 646 case NodeIf: 647 name = "if" 648 case NodeRange: 649 name = "range" 650 case NodeWith: 651 name = "with" 652 default: 653 panic("unknown branch type") 654 } 655 if b.ElseList != nil { 656 return fmt.Sprintf("{{%s %s}}%s{{else}}%s{{end}}", name, b.Pipe, b.List, b.ElseList) 657 } 658 return fmt.Sprintf("{{%s %s}}%s{{end}}", name, b.Pipe, b.List) 659} 660 661// IfNode represents an {{if}} action and its commands. 662type IfNode struct { 663 BranchNode 664} 665 666func newIf(pos Pos, line int, pipe *PipeNode, list, elseList *ListNode) *IfNode { 667 return &IfNode{BranchNode{NodeType: NodeIf, Pos: pos, Line: line, Pipe: pipe, List: list, ElseList: elseList}} 668} 669 670func (i *IfNode) Copy() Node { 671 return newIf(i.Pos, i.Line, i.Pipe.CopyPipe(), i.List.CopyList(), i.ElseList.CopyList()) 672} 673 674// RangeNode represents a {{range}} action and its commands. 675type RangeNode struct { 676 BranchNode 677} 678 679func newRange(pos Pos, line int, pipe *PipeNode, list, elseList *ListNode) *RangeNode { 680 return &RangeNode{BranchNode{NodeType: NodeRange, Pos: pos, Line: line, Pipe: pipe, List: list, ElseList: elseList}} 681} 682 683func (r *RangeNode) Copy() Node { 684 return newRange(r.Pos, r.Line, r.Pipe.CopyPipe(), r.List.CopyList(), r.ElseList.CopyList()) 685} 686 687// WithNode represents a {{with}} action and its commands. 688type WithNode struct { 689 BranchNode 690} 691 692func newWith(pos Pos, line int, pipe *PipeNode, list, elseList *ListNode) *WithNode { 693 return &WithNode{BranchNode{NodeType: NodeWith, Pos: pos, Line: line, Pipe: pipe, List: list, ElseList: elseList}} 694} 695 696func (w *WithNode) Copy() Node { 697 return newWith(w.Pos, w.Line, w.Pipe.CopyPipe(), w.List.CopyList(), w.ElseList.CopyList()) 698} 699 700// TemplateNode represents a {{template}} action. 701type TemplateNode struct { 702 NodeType 703 Pos 704 Line int // The line number in the input (deprecated; kept for compatibility) 705 Name string // The name of the template (unquoted). 706 Pipe *PipeNode // The command to evaluate as dot for the template. 707} 708 709func newTemplate(pos Pos, line int, name string, pipe *PipeNode) *TemplateNode { 710 return &TemplateNode{NodeType: NodeTemplate, Line: line, Pos: pos, Name: name, Pipe: pipe} 711} 712 713func (t *TemplateNode) String() string { 714 if t.Pipe == nil { 715 return fmt.Sprintf("{{template %q}}", t.Name) 716 } 717 return fmt.Sprintf("{{template %q %s}}", t.Name, t.Pipe) 718} 719 720func (t *TemplateNode) Copy() Node { 721 return newTemplate(t.Pos, t.Line, t.Name, t.Pipe.CopyPipe()) 722} 723