libgo/go/exp/datafmt/datafmt.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 /*      The datafmt package implements syntax-directed, type-driven formatting
   6         of arbitrary data structures. Formatting a data structure consists of
   7         two phases: first, a parser reads a format specification and builds a
   8         "compiled" format. Then, the format can be applied repeatedly to
   9         arbitrary values. Applying a format to a value evaluates to a []byte
  10         containing the formatted value bytes, or nil.
  11
  12         A format specification is a set of package declarations and format rules:
  13
  14                 Format      = [ Entry { ";" Entry } [ ";" ] ] .
  15                 Entry       = PackageDecl | FormatRule .
  16
  17         (The syntax of a format specification is presented in the same EBNF
  18         notation as used in the Go language specification. The syntax of white
  19         space, comments, identifiers, and string literals is the same as in Go.)
  20
  21         A package declaration binds a package name (such as 'ast') to a
  22         package import path (such as '"go/ast"'). Each package used (in
  23         a type name, see below) must be declared once before use.
  24
  25                 PackageDecl = PackageName ImportPath .
  26                 PackageName = identifier .
  27                 ImportPath  = string .
  28
  29         A format rule binds a rule name to a format expression. A rule name
  30         may be a type name or one of the special names 'default' or '/'.
  31         A type name may be the name of a predeclared type (for example, 'int',
  32         'float32', etc.), the package-qualified name of a user-defined type
  33         (for example, 'ast.MapType'), or an identifier indicating the structure
  34         of unnamed composite types ('array', 'chan', 'func', 'interface', 'map',
  35         or 'ptr'). Each rule must have a unique name; rules can be declared in
  36         any order.
  37
  38                 FormatRule  = RuleName "=" Expression .
  39                 RuleName    = TypeName | "default" | "/" .
  40                 TypeName    = [ PackageName "." ] identifier .
  41
  42         To format a value, the value's type name is used to select the format rule
  43         (there is an override mechanism, see below). The format expression of the
  44         selected rule specifies how the value is formatted. Each format expression,
  45         when applied to a value, evaluates to a byte sequence or nil.
  46
  47         In its most general form, a format expression is a list of alternatives,
  48         each of which is a sequence of operands:
  49
  50                 Expression  = [ Sequence ] { "|" [ Sequence ] } .
  51                 Sequence    = Operand { Operand } .
  52
  53         The formatted result produced by an expression is the result of the first
  54         alternative sequence that evaluates to a non-nil result; if there is no
  55         such alternative, the expression evaluates to nil. The result produced by
  56         an operand sequence is the concatenation of the results of its operands.
  57         If any operand in the sequence evaluates to nil, the entire sequence
  58         evaluates to nil.
  59
  60         There are five kinds of operands:
  61
  62                 Operand     = Literal | Field | Group | Option | Repetition .
  63
  64         Literals evaluate to themselves, with two substitutions. First,
  65         %-formats expand in the manner of fmt.Printf, with the current value
  66         passed as the parameter. Second, the current indentation (see below)
  67         is inserted after every newline or form feed character.
  68
  69                 Literal     = string .
  70
  71         This table shows string literals applied to the value 42 and the
  72         corresponding formatted result:
  73
  74                 "foo"       foo
  75                 "%x"        2a
  76                 "x = %d"    x = 42
  77                 "%#x = %d"  0x2a = 42
  78
  79         A field operand is a field name optionally followed by an alternate
  80         rule name. The field name may be an identifier or one of the special
  81         names @ or *.
  82
  83                 Field       = FieldName [ ":" RuleName ] .
  84                 FieldName   = identifier | "@" | "*" .
  85
  86         If the field name is an identifier, the current value must be a struct,
  87         and there must be a field with that name in the struct. The same lookup
  88         rules apply as in the Go language (for instance, the name of an anonymous
  89         field is the unqualified type name). The field name denotes the field
  90         value in the struct. If the field is not found, formatting is aborted
  91         and an error message is returned. (TODO consider changing the semantics
  92         such that if a field is not found, it evaluates to nil).
  93
  94         The special name '@' denotes the current value.
  95
  96         The meaning of the special name '*' depends on the type of the current
  97         value:
  98
  99                 array, slice types   array, slice element (inside {} only, see below)
 100                 interfaces           value stored in interface
 101                 pointers             value pointed to by pointer
 102
 103         (Implementation restriction: channel, function and map types are not
 104         supported due to missing reflection support).
 105
 106         Fields are evaluated as follows: If the field value is nil, or an array
 107         or slice element does not exist, the result is nil (see below for details
 108         on array/slice elements). If the value is not nil the field value is
 109         formatted (recursively) using the rule corresponding to its type name,
 110         or the alternate rule name, if given.
 111
 112         The following example shows a complete format specification for a
 113         struct 'myPackage.Point'. Assume the package
 114
 115                 package myPackage  // in directory myDir/myPackage
 116                 type Point struct {
 117                         name string;
 118                         x, y int;
 119                 }
 120
 121         Applying the format specification
 122
 123                 myPackage "myDir/myPackage";
 124                 int = "%d";
 125                 hexInt = "0x%x";
 126                 string = "---%s---";
 127                 myPackage.Point = name "{" x ", " y:hexInt "}";
 128
 129         to the value myPackage.Point{"foo", 3, 15} results in
 130
 131                 ---foo---{3, 0xf}
 132
 133         Finally, an operand may be a grouped, optional, or repeated expression.
 134         A grouped expression ("group") groups a more complex expression (body)
 135         so that it can be used in place of a single operand:
 136
 137                 Group       = "(" [ Indentation ">>" ] Body ")" .
 138                 Indentation = Expression .
 139                 Body        = Expression .
 140
 141         A group body may be prefixed by an indentation expression followed by '>>'.
 142         The indentation expression is applied to the current value like any other
 143         expression and the result, if not nil, is appended to the current indentation
 144         during the evaluation of the body (see also formatting state, below).
 145
 146         An optional expression ("option") is enclosed in '[]' brackets.
 147
 148                 Option      = "[" Body "]" .
 149
 150         An option evaluates to its body, except that if the body evaluates to nil,
 151         the option expression evaluates to an empty []byte. Thus an option's purpose
 152         is to protect the expression containing the option from a nil operand.
 153
 154         A repeated expression ("repetition") is enclosed in '{}' braces.
 155
 156                 Repetition  = "{" Body [ "/" Separator ] "}" .
 157                 Separator   = Expression .
 158
 159         A repeated expression is evaluated as follows: The body is evaluated
 160         repeatedly and its results are concatenated until the body evaluates
 161         to nil. The result of the repetition is the (possibly empty) concatenation,
 162         but it is never nil. An implicit index is supplied for the evaluation of
 163         the body: that index is used to address elements of arrays or slices. If
 164         the corresponding elements do not exist, the field denoting the element
 165         evaluates to nil (which in turn may terminate the repetition).
 166
 167         The body of a repetition may be followed by a '/' and a "separator"
 168         expression. If the separator is present, it is invoked between repetitions
 169         of the body.
 170
 171         The following example shows a complete format specification for formatting
 172         a slice of unnamed type. Applying the specification
 173
 174                 int = "%b";
 175                 array = { * / ", " };  // array is the type name for an unnamed slice
 176
 177         to the value '[]int{2, 3, 5, 7}' results in
 178
 179                 10, 11, 101, 111
 180
 181         Default rule: If a format rule named 'default' is present, it is used for
 182         formatting a value if no other rule was found. A common default rule is
 183
 184                 default = "%v"
 185
 186         to provide default formatting for basic types without having to specify
 187         a specific rule for each basic type.
 188
 189         Global separator rule: If a format rule named '/' is present, it is
 190         invoked with the current value between literals. If the separator
 191         expression evaluates to nil, it is ignored.
 192
 193         For instance, a global separator rule may be used to punctuate a sequence
 194         of values with commas. The rules:
 195
 196                 default = "%v";
 197                 / = ", ";
 198
 199         will format an argument list by printing each one in its default format,
 200         separated by a comma and a space.
 201 */
 202 package datafmt
 203
 204 import (
 205         "bytes"
 206         "fmt"
 207         "go/token"
 208         "io"
 209         "os"
 210         "reflect"
 211         "runtime"
 212 )
 213
 214
 215 // ----------------------------------------------------------------------------
 216 // Format representation
 217
 218 // Custom formatters implement the Formatter function type.
 219 // A formatter is invoked with the current formatting state, the
 220 // value to format, and the rule name under which the formatter
 221 // was installed (the same formatter function may be installed
 222 // under different names). The formatter may access the current state
 223 // to guide formatting and use State.Write to append to the state's
 224 // output.
 225 //
 226 // A formatter must return a boolean value indicating if it evaluated
 227 // to a non-nil value (true), or a nil value (false).
 228 //
 229 type Formatter func(state *State, value interface{}, ruleName string) bool
 230
 231
 232 // A FormatterMap is a set of custom formatters.
 233 // It maps a rule name to a formatter function.
 234 //
 235 type FormatterMap map[string]Formatter
 236
 237
 238 // A parsed format expression is built from the following nodes.
 239 //
 240 type (
 241         expr interface{}
 242
 243         alternatives []expr // x | y | z
 244
 245         sequence []expr // x y z
 246
 247         literal [][]byte // a list of string segments, possibly starting with '%'
 248
 249         field struct {
 250                 fieldName string // including "@", "*"
 251                 ruleName  string // "" if no rule name specified
 252         }
 253
 254         group struct {
 255                 indent, body expr // (indent >> body)
 256         }
 257
 258         option struct {
 259                 body expr // [body]
 260         }
 261
 262         repetition struct {
 263                 body, separator expr // {body / separator}
 264         }
 265
 266         custom struct {
 267                 ruleName string
 268                 fun      Formatter
 269         }
 270 )
 271
 272
 273 // A Format is the result of parsing a format specification.
 274 // The format may be applied repeatedly to format values.
 275 //
 276 type Format map[string]expr
 277
 278
 279 // ----------------------------------------------------------------------------
 280 // Formatting
 281
 282 // An application-specific environment may be provided to Format.Apply;
 283 // the environment is available inside custom formatters via State.Env().
 284 // Environments must implement copying; the Copy method must return an
 285 // complete copy of the receiver. This is necessary so that the formatter
 286 // can save and restore an environment (in case of an absent expression).
 287 //
 288 // If the Environment doesn't change during formatting (this is under
 289 // control of the custom formatters), the Copy function can simply return
 290 // the receiver, and thus can be very light-weight.
 291 //
 292 type Environment interface {
 293         Copy() Environment
 294 }
 295
 296
 297 // State represents the current formatting state.
 298 // It is provided as argument to custom formatters.
 299 //
 300 type State struct {
 301         fmt       Format         // format in use
 302         env       Environment    // user-supplied environment
 303         errors    chan os.Error  // not chan *Error (errors <- nil would be wrong!)
 304         hasOutput bool           // true after the first literal has been written
 305         indent    bytes.Buffer   // current indentation
 306         output    bytes.Buffer   // format output
 307         linePos   token.Position // position of line beginning (Column == 0)
 308         default_  expr           // possibly nil
 309         separator expr           // possibly nil
 310 }
 311
 312
 313 func newState(fmt Format, env Environment, errors chan os.Error) *State {
 314         s := new(State)
 315         s.fmt = fmt
 316         s.env = env
 317         s.errors = errors
 318         s.linePos = token.Position{Line: 1}
 319
 320         // if we have a default rule, cache it's expression for fast access
 321         if x, found := fmt["default"]; found {
 322                 s.default_ = x
 323         }
 324
 325         // if we have a global separator rule, cache it's expression for fast access
 326         if x, found := fmt["/"]; found {
 327                 s.separator = x
 328         }
 329
 330         return s
 331 }
 332
 333
 334 // Env returns the environment passed to Format.Apply.
 335 func (s *State) Env() interface{} { return s.env }
 336
 337
 338 // LinePos returns the position of the current line beginning
 339 // in the state's output buffer. Line numbers start at 1.
 340 //
 341 func (s *State) LinePos() token.Position { return s.linePos }
 342
 343
 344 // Pos returns the position of the next byte to be written to the
 345 // output buffer. Line numbers start at 1.
 346 //
 347 func (s *State) Pos() token.Position {
 348         offs := s.output.Len()
 349         return token.Position{Line: s.linePos.Line, Column: offs - s.linePos.Offset, Offset: offs}
 350 }
 351
 352
 353 // Write writes data to the output buffer, inserting the indentation
 354 // string after each newline or form feed character. It cannot return an error.
 355 //
 356 func (s *State) Write(data []byte) (int, os.Error) {
 357         n := 0
 358         i0 := 0
 359         for i, ch := range data {
 360                 if ch == '\n' || ch == '\f' {
 361                         // write text segment and indentation
 362                         n1, _ := s.output.Write(data[i0 : i+1])
 363                         n2, _ := s.output.Write(s.indent.Bytes())
 364                         n += n1 + n2
 365                         i0 = i + 1
 366                         s.linePos.Offset = s.output.Len()
 367                         s.linePos.Line++
 368                 }
 369         }
 370         n3, _ := s.output.Write(data[i0:])
 371         return n + n3, nil
 372 }
 373
 374
 375 type checkpoint struct {
 376         env       Environment
 377         hasOutput bool
 378         outputLen int
 379         linePos   token.Position
 380 }
 381
 382
 383 func (s *State) save() checkpoint {
 384         saved := checkpoint{nil, s.hasOutput, s.output.Len(), s.linePos}
 385         if s.env != nil {
 386                 saved.env = s.env.Copy()
 387         }
 388         return saved
 389 }
 390
 391
 392 func (s *State) restore(m checkpoint) {
 393         s.env = m.env
 394         s.output.Truncate(m.outputLen)
 395 }
 396
 397
 398 func (s *State) error(msg string) {
 399         s.errors <- os.NewError(msg)
 400         runtime.Goexit()
 401 }
 402
 403
 404 // TODO At the moment, unnamed types are simply mapped to the default
 405 //      names below. For instance, all unnamed arrays are mapped to
 406 //      'array' which is not really sufficient. Eventually one may want
 407 //      to be able to specify rules for say an unnamed slice of T.
 408 //
 409
 410 func typename(typ reflect.Type) string {
 411         switch typ.(type) {
 412         case *reflect.ArrayType:
 413                 return "array"
 414         case *reflect.SliceType:
 415                 return "array"
 416         case *reflect.ChanType:
 417                 return "chan"
 418         case *reflect.FuncType:
 419                 return "func"
 420         case *reflect.InterfaceType:
 421                 return "interface"
 422         case *reflect.MapType:
 423                 return "map"
 424         case *reflect.PtrType:
 425                 return "ptr"
 426         }
 427         return typ.String()
 428 }
 429
 430 func (s *State) getFormat(name string) expr {
 431         if fexpr, found := s.fmt[name]; found {
 432                 return fexpr
 433         }
 434
 435         if s.default_ != nil {
 436                 return s.default_
 437         }
 438
 439         s.error(fmt.Sprintf("no format rule for type: '%s'", name))
 440         return nil
 441 }
 442
 443
 444 // eval applies a format expression fexpr to a value. If the expression
 445 // evaluates internally to a non-nil []byte, that slice is appended to
 446 // the state's output buffer and eval returns true. Otherwise, eval
 447 // returns false and the state remains unchanged.
 448 //
 449 func (s *State) eval(fexpr expr, value reflect.Value, index int) bool {
 450         // an empty format expression always evaluates
 451         // to a non-nil (but empty) []byte
 452         if fexpr == nil {
 453                 return true
 454         }
 455
 456         switch t := fexpr.(type) {
 457         case alternatives:
 458                 // append the result of the first alternative that evaluates to
 459                 // a non-nil []byte to the state's output
 460                 mark := s.save()
 461                 for _, x := range t {
 462                         if s.eval(x, value, index) {
 463                                 return true
 464                         }
 465                         s.restore(mark)
 466                 }
 467                 return false
 468
 469         case sequence:
 470                 // append the result of all operands to the state's output
 471                 // unless a nil result is encountered
 472                 mark := s.save()
 473                 for _, x := range t {
 474                         if !s.eval(x, value, index) {
 475                                 s.restore(mark)
 476                                 return false
 477                         }
 478                 }
 479                 return true
 480
 481         case literal:
 482                 // write separator, if any
 483                 if s.hasOutput {
 484                         // not the first literal
 485                         if s.separator != nil {
 486                                 sep := s.separator // save current separator
 487                                 s.separator = nil  // and disable it (avoid recursion)
 488                                 mark := s.save()
 489                                 if !s.eval(sep, value, index) {
 490                                         s.restore(mark)
 491                                 }
 492                                 s.separator = sep // enable it again
 493                         }
 494                 }
 495                 s.hasOutput = true
 496                 // write literal segments
 497                 for _, lit := range t {
 498                         if len(lit) > 1 && lit[0] == '%' {
 499                                 // segment contains a %-format at the beginning
 500                                 if lit[1] == '%' {
 501                                         // "%%" is printed as a single "%"
 502                                         s.Write(lit[1:])
 503                                 } else {
 504                                         // use s instead of s.output to get indentation right
 505                                         fmt.Fprintf(s, string(lit), value.Interface())
 506                                 }
 507                         } else {
 508                                 // segment contains no %-formats
 509                                 s.Write(lit)
 510                         }
 511                 }
 512                 return true // a literal never evaluates to nil
 513
 514         case *field:
 515                 // determine field value
 516                 switch t.fieldName {
 517                 case "@":
 518                         // field value is current value
 519
 520                 case "*":
 521                         // indirection: operation is type-specific
 522                         switch v := value.(type) {
 523                         case *reflect.ArrayValue:
 524                                 if v.Len() <= index {
 525                                         return false
 526                                 }
 527                                 value = v.Elem(index)
 528
 529                         case *reflect.SliceValue:
 530                                 if v.IsNil() || v.Len() <= index {
 531                                         return false
 532                                 }
 533                                 value = v.Elem(index)
 534
 535                         case *reflect.MapValue:
 536                                 s.error("reflection support for maps incomplete")
 537
 538                         case *reflect.PtrValue:
 539                                 if v.IsNil() {
 540                                         return false
 541                                 }
 542                                 value = v.Elem()
 543
 544                         case *reflect.InterfaceValue:
 545                                 if v.IsNil() {
 546                                         return false
 547                                 }
 548                                 value = v.Elem()
 549
 550                         case *reflect.ChanValue:
 551                                 s.error("reflection support for chans incomplete")
 552
 553                         case *reflect.FuncValue:
 554                                 s.error("reflection support for funcs incomplete")
 555
 556                         default:
 557                                 s.error(fmt.Sprintf("error: * does not apply to `%s`", value.Type()))
 558                         }
 559
 560                 default:
 561                         // value is value of named field
 562                         var field reflect.Value
 563                         if sval, ok := value.(*reflect.StructValue); ok {
 564                                 field = sval.FieldByName(t.fieldName)
 565                                 if field == nil {
 566                                         // TODO consider just returning false in this case
 567                                         s.error(fmt.Sprintf("error: no field `%s` in `%s`", t.fieldName, value.Type()))
 568                                 }
 569                         }
 570                         value = field
 571                 }
 572
 573                 // determine rule
 574                 ruleName := t.ruleName
 575                 if ruleName == "" {
 576                         // no alternate rule name, value type determines rule
 577                         ruleName = typename(value.Type())
 578                 }
 579                 fexpr = s.getFormat(ruleName)
 580
 581                 mark := s.save()
 582                 if !s.eval(fexpr, value, index) {
 583                         s.restore(mark)
 584                         return false
 585                 }
 586                 return true
 587
 588         case *group:
 589                 // remember current indentation
 590                 indentLen := s.indent.Len()
 591
 592                 // update current indentation
 593                 mark := s.save()
 594                 s.eval(t.indent, value, index)
 595                 // if the indentation evaluates to nil, the state's output buffer
 596                 // didn't change - either way it's ok to append the difference to
 597                 // the current identation
 598                 s.indent.Write(s.output.Bytes()[mark.outputLen:s.output.Len()])
 599                 s.restore(mark)
 600
 601                 // format group body
 602                 mark = s.save()
 603                 b := true
 604                 if !s.eval(t.body, value, index) {
 605                         s.restore(mark)
 606                         b = false
 607                 }
 608
 609                 // reset indentation
 610                 s.indent.Truncate(indentLen)
 611                 return b
 612
 613         case *option:
 614                 // evaluate the body and append the result to the state's output
 615                 // buffer unless the result is nil
 616                 mark := s.save()
 617                 if !s.eval(t.body, value, 0) { // TODO is 0 index correct?
 618                         s.restore(mark)
 619                 }
 620                 return true // an option never evaluates to nil
 621
 622         case *repetition:
 623                 // evaluate the body and append the result to the state's output
 624                 // buffer until a result is nil
 625                 for i := 0; ; i++ {
 626                         mark := s.save()
 627                         // write separator, if any
 628                         if i > 0 && t.separator != nil {
 629                                 // nil result from separator is ignored
 630                                 mark := s.save()
 631                                 if !s.eval(t.separator, value, i) {
 632                                         s.restore(mark)
 633                                 }
 634                         }
 635                         if !s.eval(t.body, value, i) {
 636                                 s.restore(mark)
 637                                 break
 638                         }
 639                 }
 640                 return true // a repetition never evaluates to nil
 641
 642         case *custom:
 643                 // invoke the custom formatter to obtain the result
 644                 mark := s.save()
 645                 if !t.fun(s, value.Interface(), t.ruleName) {
 646                         s.restore(mark)
 647                         return false
 648                 }
 649                 return true
 650         }
 651
 652         panic("unreachable")
 653         return false
 654 }
 655
 656
 657 // Eval formats each argument according to the format
 658 // f and returns the resulting []byte and os.Error. If
 659 // an error occurred, the []byte contains the partially
 660 // formatted result. An environment env may be passed
 661 // in which is available in custom formatters through
 662 // the state parameter.
 663 //
 664 func (f Format) Eval(env Environment, args ...interface{}) ([]byte, os.Error) {
 665         if f == nil {
 666                 return nil, os.NewError("format is nil")
 667         }
 668
 669         errors := make(chan os.Error)
 670         s := newState(f, env, errors)
 671
 672         go func() {
 673                 for _, v := range args {
 674                         fld := reflect.NewValue(v)
 675                         if fld == nil {
 676                                 errors <- os.NewError("nil argument")
 677                                 return
 678                         }
 679                         mark := s.save()
 680                         if !s.eval(s.getFormat(typename(fld.Type())), fld, 0) { // TODO is 0 index correct?
 681                                 s.restore(mark)
 682                         }
 683                 }
 684                 errors <- nil // no errors
 685         }()
 686
 687         err := <-errors
 688         return s.output.Bytes(), err
 689 }
 690
 691
 692 // ----------------------------------------------------------------------------
 693 // Convenience functions
 694
 695 // Fprint formats each argument according to the format f
 696 // and writes to w. The result is the total number of bytes
 697 // written and an os.Error, if any.
 698 //
 699 func (f Format) Fprint(w io.Writer, env Environment, args ...interface{}) (int, os.Error) {
 700         data, err := f.Eval(env, args...)
 701         if err != nil {
 702                 // TODO should we print partial result in case of error?
 703                 return 0, err
 704         }
 705         return w.Write(data)
 706 }
 707
 708
 709 // Print formats each argument according to the format f
 710 // and writes to standard output. The result is the total
 711 // number of bytes written and an os.Error, if any.
 712 //
 713 func (f Format) Print(args ...interface{}) (int, os.Error) {
 714         return f.Fprint(os.Stdout, nil, args...)
 715 }
 716
 717
 718 // Sprint formats each argument according to the format f
 719 // and returns the resulting string. If an error occurs
 720 // during formatting, the result string contains the
 721 // partially formatted result followed by an error message.
 722 //
 723 func (f Format) Sprint(args ...interface{}) string {
 724         var buf bytes.Buffer
 725         _, err := f.Fprint(&buf, nil, args...)
 726         if err != nil {
 727                 var i interface{} = args
 728                 fmt.Fprintf(&buf, "--- Sprint(%s) failed: %v", fmt.Sprint(i), err)
 729         }
 730         return buf.String()
 731 }