compiler/parse.go

   1 package compiler
   2
   3 import (
   4         "bytes"
   5         "encoding/hex"
   6         "fmt"
   7         "strconv"
   8         "unicode"
   9 )
  10
  11 // We have some function naming conventions.
  12 //
  13 // For terminals:
  14 //   scanX     takes buf and position, returns new position (and maybe a value)
  15 //   peekX     takes *parser, returns bool or string
  16 //   consumeX  takes *parser and maybe a required literal, maybe returns value
  17 //             also updates the parser position
  18 //
  19 // For nonterminals:
  20 //   parseX    takes *parser, returns AST node, updates parser position
  21
  22 type parser struct {
  23         buf []byte
  24         pos int
  25 }
  26
  27 func (p *parser) errorf(format string, args ...interface{}) {
  28         panic(parserErr{buf: p.buf, offset: p.pos, format: format, args: args})
  29 }
  30
  31 // parse is the main entry point to the parser
  32 func parse(buf []byte) (contracts []*Contract, err error) {
  33         defer func() {
  34                 if val := recover(); val != nil {
  35                         if e, ok := val.(parserErr); ok {
  36                                 err = e
  37                         } else {
  38                                 panic(val)
  39                         }
  40                 }
  41         }()
  42         p := &parser{buf: buf}
  43         contracts = parseContracts(p)
  44         return
  45 }
  46
  47 // parse functions
  48
  49 func parseContracts(p *parser) []*Contract {
  50         var result []*Contract
  51         for peekKeyword(p) == "contract" {
  52                 contract := parseContract(p)
  53                 result = append(result, contract)
  54         }
  55         return result
  56 }
  57
  58 // contract name(p1, p2: t1, p3: t2) locks value { ... }
  59 func parseContract(p *parser) *Contract {
  60         consumeKeyword(p, "contract")
  61         name := consumeIdentifier(p)
  62         params := parseParams(p)
  63         // locks amount of asset
  64         consumeKeyword(p, "locks")
  65         value := ValueInfo{}
  66         value.Amount = consumeIdentifier(p)
  67         consumeKeyword(p, "of")
  68         value.Asset = consumeIdentifier(p)
  69         consumeTok(p, "{")
  70         clauses := parseClauses(p)
  71         consumeTok(p, "}")
  72         return &Contract{Name: name, Params: params, Clauses: clauses, Value: value}
  73 }
  74
  75 // (p1, p2: t1, p3: t2)
  76 func parseParams(p *parser) []*Param {
  77         var params []*Param
  78         consumeTok(p, "(")
  79         first := true
  80         for !peekTok(p, ")") {
  81                 if first {
  82                         first = false
  83                 } else {
  84                         consumeTok(p, ",")
  85                 }
  86                 pt := parseParamsType(p)
  87                 params = append(params, pt...)
  88         }
  89         consumeTok(p, ")")
  90         return params
  91 }
  92
  93 func parseClauses(p *parser) []*Clause {
  94         var clauses []*Clause
  95         for !peekTok(p, "}") {
  96                 c := parseClause(p)
  97                 clauses = append(clauses, c)
  98         }
  99         return clauses
 100 }
 101
 102 func parseParamsType(p *parser) []*Param {
 103         firstName := consumeIdentifier(p)
 104         params := []*Param{&Param{Name: firstName}}
 105         for peekTok(p, ",") {
 106                 consumeTok(p, ",")
 107                 name := consumeIdentifier(p)
 108                 params = append(params, &Param{Name: name})
 109         }
 110         consumeTok(p, ":")
 111         typ := consumeIdentifier(p)
 112         for _, parm := range params {
 113                 if tdesc, ok := types[typ]; ok {
 114                         parm.Type = tdesc
 115                 } else {
 116                         p.errorf("unknown type %s", typ)
 117                 }
 118         }
 119         return params
 120 }
 121
 122 func parseClause(p *parser) *Clause {
 123         var c Clause
 124         consumeKeyword(p, "clause")
 125         c.Name = consumeIdentifier(p)
 126         c.Params = parseParams(p)
 127         consumeTok(p, "{")
 128         c.statements = parseStatements(p)
 129         consumeTok(p, "}")
 130         return &c
 131 }
 132
 133 func parseStatements(p *parser) []statement {
 134         var statements []statement
 135         for !peekTok(p, "}") {
 136                 s := parseStatement(p)
 137                 statements = append(statements, s)
 138         }
 139         return statements
 140 }
 141
 142 func parseStatement(p *parser) statement {
 143         switch peekKeyword(p) {
 144         case "if":
 145                 return parseIfStmt(p)
 146         case "define":
 147                 return parseDefineStmt(p)
 148         case "assign":
 149                 return parseAssignStmt(p)
 150         case "verify":
 151                 return parseVerifyStmt(p)
 152         case "lock":
 153                 return parseLockStmt(p)
 154         case "unlock":
 155                 return parseUnlockStmt(p)
 156         }
 157         panic(parseErr(p.buf, p.pos, "unknown keyword \"%s\"", peekKeyword(p)))
 158 }
 159
 160 func parseIfStmt(p *parser) *ifStatement {
 161         consumeKeyword(p, "if")
 162         condition := parseExpr(p)
 163         body := &IfStatmentBody{}
 164         consumeTok(p, "{")
 165         body.trueBody = parseStatements(p)
 166         consumeTok(p, "}")
 167         if peekKeyword(p) == "else" {
 168                 consumeKeyword(p, "else")
 169                 consumeTok(p, "{")
 170                 body.falseBody = parseStatements(p)
 171                 consumeTok(p, "}")
 172         }
 173         return &ifStatement{condition: condition, body: body}
 174 }
 175
 176 func parseDefineStmt(p *parser) *defineStatement {
 177         defineStat := &defineStatement{}
 178         consumeKeyword(p, "define")
 179         param := &Param{}
 180         param.Name = consumeIdentifier(p)
 181         consumeTok(p, ":")
 182         variableType := consumeIdentifier(p)
 183         if tdesc, ok := types[variableType]; ok {
 184                 param.Type = tdesc
 185         } else {
 186                 p.errorf("unknown type %s", variableType)
 187         }
 188         defineStat.variable = param
 189         if peekTok(p, "=") {
 190                 consumeTok(p, "=")
 191                 defineStat.expr = parseExpr(p)
 192         }
 193         return defineStat
 194 }
 195
 196 func parseAssignStmt(p *parser) *assignStatement {
 197         consumeKeyword(p, "assign")
 198         varName := consumeIdentifier(p)
 199         consumeTok(p, "=")
 200         expr := parseExpr(p)
 201         return &assignStatement{variable: &Param{Name: varName}, expr: expr}
 202 }
 203
 204 func parseVerifyStmt(p *parser) *verifyStatement {
 205         consumeKeyword(p, "verify")
 206         expr := parseExpr(p)
 207         return &verifyStatement{expr: expr}
 208 }
 209
 210 func parseLockStmt(p *parser) *lockStatement {
 211         consumeKeyword(p, "lock")
 212         lockedAmount := parseExpr(p)
 213         consumeKeyword(p, "of")
 214         lockedAsset := parseExpr(p)
 215         consumeKeyword(p, "with")
 216         program := parseExpr(p)
 217         return &lockStatement{lockedAmount: lockedAmount, lockedAsset: lockedAsset, program: program}
 218 }
 219
 220 func parseUnlockStmt(p *parser) *unlockStatement {
 221         consumeKeyword(p, "unlock")
 222         unlockedAmount := parseExpr(p)
 223         consumeKeyword(p, "of")
 224         unlockedAsset := parseExpr(p)
 225         return &unlockStatement{unlockedAmount: unlockedAmount, unlockedAsset: unlockedAsset}
 226 }
 227
 228 func parseExpr(p *parser) expression {
 229         // Uses the precedence-climbing algorithm
 230         // <https://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method>
 231         expr := parseUnaryExpr(p)
 232         expr2, pos := parseExprCont(p, expr, 0)
 233         if pos < 0 {
 234                 p.errorf("expected expression")
 235         }
 236         p.pos = pos
 237         return expr2
 238 }
 239
 240 func parseUnaryExpr(p *parser) expression {
 241         op, pos := scanUnaryOp(p.buf, p.pos)
 242         if pos < 0 {
 243                 return parseExpr2(p)
 244         }
 245         p.pos = pos
 246         expr := parseUnaryExpr(p)
 247         return &unaryExpr{op: op, expr: expr}
 248 }
 249
 250 func parseExprCont(p *parser, lhs expression, minPrecedence int) (expression, int) {
 251         for {
 252                 op, pos := scanBinaryOp(p.buf, p.pos)
 253                 if pos < 0 || op.precedence < minPrecedence {
 254                         break
 255                 }
 256                 p.pos = pos
 257
 258                 rhs := parseUnaryExpr(p)
 259
 260                 for {
 261                         op2, pos2 := scanBinaryOp(p.buf, p.pos)
 262                         if pos2 < 0 || op2.precedence <= op.precedence {
 263                                 break
 264                         }
 265                         rhs, p.pos = parseExprCont(p, rhs, op2.precedence)
 266                         if p.pos < 0 {
 267                                 return nil, -1 // or is this an error?
 268                         }
 269                 }
 270                 lhs = &binaryExpr{left: lhs, right: rhs, op: op}
 271         }
 272         return lhs, p.pos
 273 }
 274
 275 func parseExpr2(p *parser) expression {
 276         if expr, pos := scanLiteralExpr(p.buf, p.pos); pos >= 0 {
 277                 p.pos = pos
 278                 return expr
 279         }
 280         return parseExpr3(p)
 281 }
 282
 283 func parseExpr3(p *parser) expression {
 284         e := parseExpr4(p)
 285         if peekTok(p, "(") {
 286                 args := parseArgs(p)
 287                 return &callExpr{fn: e, args: args}
 288         }
 289         return e
 290 }
 291
 292 func parseExpr4(p *parser) expression {
 293         if peekTok(p, "(") {
 294                 consumeTok(p, "(")
 295                 e := parseExpr(p)
 296                 consumeTok(p, ")")
 297                 return e
 298         }
 299         if peekTok(p, "[") {
 300                 var elts []expression
 301                 consumeTok(p, "[")
 302                 first := true
 303                 for !peekTok(p, "]") {
 304                         if first {
 305                                 first = false
 306                         } else {
 307                                 consumeTok(p, ",")
 308                         }
 309                         e := parseExpr(p)
 310                         elts = append(elts, e)
 311                 }
 312                 consumeTok(p, "]")
 313                 return listExpr(elts)
 314         }
 315         name := consumeIdentifier(p)
 316         return varRef(name)
 317 }
 318
 319 func parseArgs(p *parser) []expression {
 320         var exprs []expression
 321         consumeTok(p, "(")
 322         first := true
 323         for !peekTok(p, ")") {
 324                 if first {
 325                         first = false
 326                 } else {
 327                         consumeTok(p, ",")
 328                 }
 329                 e := parseExpr(p)
 330                 exprs = append(exprs, e)
 331         }
 332         consumeTok(p, ")")
 333         return exprs
 334 }
 335
 336 // peek functions
 337
 338 func peekKeyword(p *parser) string {
 339         name, _ := scanIdentifier(p.buf, p.pos)
 340         return name
 341 }
 342
 343 func peekTok(p *parser, token string) bool {
 344         pos := scanTok(p.buf, p.pos, token)
 345         return pos >= 0
 346 }
 347
 348 // consume functions
 349
 350 var keywords = []string{
 351         "contract", "clause", "verify", "output", "return",
 352         "locks", "requires", "of", "lock", "with", "unlock",
 353 }
 354
 355 func consumeKeyword(p *parser, keyword string) {
 356         pos := scanKeyword(p.buf, p.pos, keyword)
 357         if pos < 0 {
 358                 p.errorf("expected keyword %s", keyword)
 359         }
 360         p.pos = pos
 361 }
 362
 363 func consumeIdentifier(p *parser) string {
 364         name, pos := scanIdentifier(p.buf, p.pos)
 365         if pos < 0 {
 366                 p.errorf("expected identifier")
 367         }
 368         p.pos = pos
 369         return name
 370 }
 371
 372 func consumeTok(p *parser, token string) {
 373         pos := scanTok(p.buf, p.pos, token)
 374         if pos < 0 {
 375                 p.errorf("expected %s token", token)
 376         }
 377         p.pos = pos
 378 }
 379
 380 // scan functions
 381
 382 func scanUnaryOp(buf []byte, offset int) (*unaryOp, int) {
 383         // Maximum munch. Make sure "-3" scans as ("-3"), not ("-", "3").
 384         if _, pos := scanIntLiteral(buf, offset); pos >= 0 {
 385                 return nil, -1
 386         }
 387         for _, op := range unaryOps {
 388                 newOffset := scanTok(buf, offset, op.op)
 389                 if newOffset >= 0 {
 390                         return &op, newOffset
 391                 }
 392         }
 393         return nil, -1
 394 }
 395
 396 func scanBinaryOp(buf []byte, offset int) (*binaryOp, int) {
 397         offset = skipWsAndComments(buf, offset)
 398         var (
 399                 found     *binaryOp
 400                 newOffset = -1
 401         )
 402         for i, op := range binaryOps {
 403                 offset2 := scanTok(buf, offset, op.op)
 404                 if offset2 >= 0 {
 405                         if found == nil || len(op.op) > len(found.op) {
 406                                 found = &binaryOps[i]
 407                                 newOffset = offset2
 408                         }
 409                 }
 410         }
 411         return found, newOffset
 412 }
 413
 414 // TODO(bobg): boolean literals?
 415 func scanLiteralExpr(buf []byte, offset int) (expression, int) {
 416         offset = skipWsAndComments(buf, offset)
 417         intliteral, newOffset := scanIntLiteral(buf, offset)
 418         if newOffset >= 0 {
 419                 return intliteral, newOffset
 420         }
 421         strliteral, newOffset := scanStrLiteral(buf, offset)
 422         if newOffset >= 0 {
 423                 return strliteral, newOffset
 424         }
 425         bytesliteral, newOffset := scanBytesLiteral(buf, offset) // 0x6c249a...
 426         if newOffset >= 0 {
 427                 return bytesliteral, newOffset
 428         }
 429         return nil, -1
 430 }
 431
 432 func scanIdentifier(buf []byte, offset int) (string, int) {
 433         offset = skipWsAndComments(buf, offset)
 434         i := offset
 435         for ; i < len(buf) && isIDChar(buf[i], i == offset); i++ {
 436         }
 437         if i == offset {
 438                 return "", -1
 439         }
 440         return string(buf[offset:i]), i
 441 }
 442
 443 func scanTok(buf []byte, offset int, s string) int {
 444         offset = skipWsAndComments(buf, offset)
 445         prefix := []byte(s)
 446         if bytes.HasPrefix(buf[offset:], prefix) {
 447                 return offset + len(prefix)
 448         }
 449         return -1
 450 }
 451
 452 func scanKeyword(buf []byte, offset int, keyword string) int {
 453         id, newOffset := scanIdentifier(buf, offset)
 454         if newOffset < 0 {
 455                 return -1
 456         }
 457         if id != keyword {
 458                 return -1
 459         }
 460         return newOffset
 461 }
 462
 463 func scanIntLiteral(buf []byte, offset int) (integerLiteral, int) {
 464         offset = skipWsAndComments(buf, offset)
 465         start := offset
 466         if offset < len(buf) && buf[offset] == '-' {
 467                 offset++
 468         }
 469         i := offset
 470         for ; i < len(buf) && unicode.IsDigit(rune(buf[i])); i++ {
 471                 // the literal is BytesLiteral when it starts with 0x/0X
 472                 if buf[i] == '0' && i < len(buf)-1 && (buf[i+1] == 'x' || buf[i+1] == 'X') {
 473                         return 0, -1
 474                 }
 475         }
 476         if i > offset {
 477                 n, err := strconv.ParseInt(string(buf[start:i]), 10, 64)
 478                 if err != nil {
 479                         return 0, -1
 480                 }
 481                 return integerLiteral(n), i
 482         }
 483         return 0, -1
 484 }
 485
 486 func scanStrLiteral(buf []byte, offset int) (bytesLiteral, int) {
 487         offset = skipWsAndComments(buf, offset)
 488         if offset >= len(buf) || buf[offset] != '\'' {
 489                 return bytesLiteral{}, -1
 490         }
 491         var byteBuf bytesLiteral
 492         for i := offset + 1; i < len(buf); i++ {
 493                 if buf[i] == '\'' {
 494                         return byteBuf, i + 1
 495                 }
 496                 if buf[i] == '\\' && i < len(buf)-1 {
 497                         if c, ok := scanEscape(buf[i+1]); ok {
 498                                 byteBuf = append(byteBuf, c)
 499                                 i++
 500                                 continue
 501                         }
 502                 }
 503                 byteBuf = append(byteBuf, buf[i])
 504         }
 505         panic(parseErr(buf, offset, "unterminated string literal"))
 506 }
 507
 508 func scanBytesLiteral(buf []byte, offset int) (bytesLiteral, int) {
 509         offset = skipWsAndComments(buf, offset)
 510         if offset+4 >= len(buf) {
 511                 return nil, -1
 512         }
 513         if buf[offset] != '0' || (buf[offset+1] != 'x' && buf[offset+1] != 'X') {
 514                 return nil, -1
 515         }
 516         if !isHexDigit(buf[offset+2]) || !isHexDigit(buf[offset+3]) {
 517                 return nil, -1
 518         }
 519         i := offset + 4
 520         for ; i < len(buf); i += 2 {
 521                 if i == len(buf)-1 {
 522                         panic(parseErr(buf, offset, "odd number of digits in hex literal"))
 523                 }
 524                 if !isHexDigit(buf[i]) {
 525                         break
 526                 }
 527                 if !isHexDigit(buf[i+1]) {
 528                         panic(parseErr(buf, offset, "odd number of digits in hex literal"))
 529                 }
 530         }
 531         decoded := make([]byte, hex.DecodedLen(i-(offset+2)))
 532         _, err := hex.Decode(decoded, buf[offset+2:i])
 533         if err != nil {
 534                 return bytesLiteral{}, -1
 535         }
 536         return bytesLiteral(decoded), i
 537 }
 538
 539 func skipWsAndComments(buf []byte, offset int) int {
 540         var inComment bool
 541         for ; offset < len(buf); offset++ {
 542                 c := buf[offset]
 543                 if inComment {
 544                         if c == '\n' {
 545                                 inComment = false
 546                         }
 547                 } else {
 548                         if c == '/' && offset < len(buf)-1 && buf[offset+1] == '/' {
 549                                 inComment = true
 550                                 offset++ // skip two chars instead of one
 551                         } else if !unicode.IsSpace(rune(c)) {
 552                                 break
 553                         }
 554                 }
 555         }
 556         return offset
 557 }
 558
 559 func isHexDigit(b byte) bool {
 560         return (b >= '0' && b <= '9') || (b >= 'a' && b <= 'f') || (b >= 'A' && b <= 'F')
 561 }
 562
 563 func isIDChar(c byte, initial bool) bool {
 564         if c >= 'a' && c <= 'z' {
 565                 return true
 566         }
 567         if c >= 'A' && c <= 'Z' {
 568                 return true
 569         }
 570         if c == '_' {
 571                 return true
 572         }
 573         if initial {
 574                 return false
 575         }
 576         return unicode.IsDigit(rune(c))
 577 }
 578
 579 type parserErr struct {
 580         buf    []byte
 581         offset int
 582         format string
 583         args   []interface{}
 584 }
 585
 586 func parseErr(buf []byte, offset int, format string, args ...interface{}) error {
 587         return parserErr{buf: buf, offset: offset, format: format, args: args}
 588 }
 589
 590 func (p parserErr) Error() string {
 591         // Lines start at 1, columns start at 0, like nature intended.
 592         line := 1
 593         col := 0
 594         for i := 0; i < p.offset; i++ {
 595                 if p.buf[i] == '\n' {
 596                         line++
 597                         col = 0
 598                 } else {
 599                         col++
 600                 }
 601         }
 602         args := []interface{}{line, col}
 603         args = append(args, p.args...)
 604         return fmt.Sprintf("line %d, col %d: "+p.format, args...)
 605 }
 606
 607 func scanEscape(c byte) (byte, bool) {
 608         escapeFlag := true
 609         switch c {
 610         case '\'', '"', '\\':
 611         case 'b':
 612                 c = '\b'
 613         case 'f':
 614                 c = '\f'
 615         case 'n':
 616                 c = '\n'
 617         case 'r':
 618                 c = '\r'
 619         case 't':
 620                 c = '\t'
 621         case 'v':
 622                 c = '\v'
 623         default:
 624                 escapeFlag = false
 625         }
 626         return c, escapeFlag
 627 }