parser.go (20490B)
1 package pattern 2 3 import ( 4 "errors" 5 "fmt" 6 "go/ast" 7 "go/token" 8 "iter" 9 "reflect" 10 "strings" 11 ) 12 13 type Pattern struct { 14 Root Node 15 // EntryNodes contains instances of ast.Node that could potentially 16 // initiate a successful match of the pattern. 17 EntryNodes []ast.Node 18 19 // SymbolsPattern is a pattern consisting or Any, Or, And, and IndexSymbol, 20 // that can be used to implement fast rejection of whole packages using 21 // typeindex. 22 SymbolsPattern Node 23 24 // If non-empty, all possible candidate nodes for this pattern can be found 25 // by finding all call expressions for this list of symbols. 26 RootCallSymbols []IndexSymbol 27 28 // Mapping from binding index to binding name 29 Bindings []string 30 } 31 32 func MustParse(s string) Pattern { 33 p := &Parser{AllowTypeInfo: true} 34 pat, err := p.Parse(s) 35 if err != nil { 36 panic(err) 37 } 38 return pat 39 } 40 41 func symbolToIndexSymbol(name string) IndexSymbol { 42 if len(name) == 0 { 43 return IndexSymbol{} 44 } 45 if name[0] == '(' { 46 end := strings.IndexAny(name, ")") 47 // Ensure there's a ), and also that there are at least two more 48 // characters after it, for a dot and an identifier. 49 if end == -1 || end > len(name)-2 { 50 return IndexSymbol{} 51 } 52 pathAndType := strings.TrimPrefix(name[1:end], "*") 53 dot := strings.LastIndex(pathAndType, ".") 54 if dot == -1 { 55 return IndexSymbol{} 56 } 57 path := pathAndType[:dot] 58 typ := pathAndType[dot+1:] 59 ident := name[end+2:] 60 return IndexSymbol{path, typ, ident} 61 } else { 62 dot := strings.LastIndex(name, ".") 63 if dot == -1 { 64 return IndexSymbol{"", "", name} 65 } 66 path := name[:dot] 67 ident := name[dot+1:] 68 return IndexSymbol{path, "", ident} 69 } 70 } 71 72 func collectSymbols(node Node, inSymbol bool) Node { 73 and := func(c Node, out *And) { 74 switch cc := c.(type) { 75 case And: 76 out.Nodes = append(out.Nodes, cc.Nodes...) 77 case Any: 78 case nil: 79 default: 80 out.Nodes = append(out.Nodes, c) 81 } 82 } 83 84 switch node := node.(type) { 85 case Or: 86 s := Or{} 87 for _, el := range node.Nodes { 88 c := collectSymbols(el, inSymbol) 89 switch cc := c.(type) { 90 case Or: 91 s.Nodes = append(s.Nodes, cc.Nodes...) 92 case Any: 93 return Any{} 94 case nil: 95 default: 96 s.Nodes = append(s.Nodes, c) 97 } 98 } 99 switch len(s.Nodes) { 100 case 0: 101 return nil 102 case 1: 103 return s.Nodes[0] 104 default: 105 return s 106 } 107 case Not, Token, nil: 108 return Any{} 109 case Symbol: 110 return collectSymbols(node.Name, true) 111 case String: 112 if !inSymbol { 113 return Any{} 114 } 115 // In logically correct patterns, all Strings that are children of 116 // Symbols describe the names of symbols. 117 return symbolToIndexSymbol(string(node)) 118 case Binding: 119 return collectSymbols(node.Node, inSymbol) 120 case Any: 121 return Any{} 122 case List: 123 var out And 124 and(collectSymbols(node.Head, inSymbol), &out) 125 and(collectSymbols(node.Tail, inSymbol), &out) 126 switch len(out.Nodes) { 127 case 0: 128 return Any{} 129 case 1: 130 return out.Nodes[0] 131 default: 132 return out 133 } 134 default: 135 var out And 136 rv := reflect.ValueOf(node) 137 for i := range rv.NumField() { 138 c := collectSymbols(rv.Field(i).Interface().(Node), inSymbol) 139 and(c, &out) 140 } 141 switch len(out.Nodes) { 142 case 0: 143 return Any{} 144 case 1: 145 return out.Nodes[0] 146 default: 147 return out 148 } 149 } 150 } 151 152 func collectRootCallSymbols(node Node) []IndexSymbol { 153 root, ok := node.(CallExpr) 154 if !ok { 155 return nil 156 } 157 158 var names []String 159 var handleSymName func(name Node) bool 160 handleSymName = func(name Node) bool { 161 switch name := name.(type) { 162 case String: 163 names = append(names, name) 164 case Or: 165 for _, node := range name.Nodes { 166 if name, ok := node.(String); ok { 167 names = append(names, name) 168 } else { 169 return false 170 } 171 } 172 case Binding: 173 return handleSymName(name.Node) 174 default: 175 return false 176 } 177 return true 178 } 179 var handleRootFun func(node Node) bool 180 handleRootFun = func(node Node) bool { 181 switch fun := node.(type) { 182 case Binding: 183 return handleRootFun(fun.Node) 184 case Symbol: 185 return handleSymName(fun.Name) 186 case Or: 187 for _, node := range fun.Nodes { 188 if sym, ok := node.(Symbol); !ok || !handleSymName(sym.Name) { 189 return false 190 } 191 } 192 return true 193 default: 194 return false 195 } 196 } 197 if !handleRootFun(root.Fun) { 198 return nil 199 } 200 201 out := make([]IndexSymbol, len(names)) 202 for i, name := range names { 203 out[i] = symbolToIndexSymbol(string(name)) 204 } 205 return out 206 } 207 208 func collectEntryNodes(node Node, m map[reflect.Type]struct{}) { 209 switch node := node.(type) { 210 case Or: 211 for _, el := range node.Nodes { 212 collectEntryNodes(el, m) 213 } 214 case Not: 215 collectEntryNodes(node.Node, m) 216 case Binding: 217 collectEntryNodes(node.Node, m) 218 case Nil, nil: 219 // this branch is reached via bindings 220 for _, T := range allTypes { 221 m[T] = struct{}{} 222 } 223 default: 224 Ts, ok := nodeToASTTypes[reflect.TypeOf(node)] 225 if !ok { 226 panic(fmt.Sprintf("internal error: unhandled type %T", node)) 227 } 228 for _, T := range Ts { 229 m[T] = struct{}{} 230 } 231 } 232 } 233 234 var allTypes = []reflect.Type{ 235 reflect.TypeFor[*ast.RangeStmt](), 236 reflect.TypeFor[*ast.AssignStmt](), 237 reflect.TypeFor[*ast.IndexExpr](), 238 reflect.TypeFor[*ast.Ident](), 239 reflect.TypeFor[*ast.ValueSpec](), 240 reflect.TypeFor[*ast.GenDecl](), 241 reflect.TypeFor[*ast.BinaryExpr](), 242 reflect.TypeFor[*ast.ForStmt](), 243 reflect.TypeFor[*ast.ArrayType](), 244 reflect.TypeFor[*ast.DeferStmt](), 245 reflect.TypeFor[*ast.MapType](), 246 reflect.TypeFor[*ast.ReturnStmt](), 247 reflect.TypeFor[*ast.SliceExpr](), 248 reflect.TypeFor[*ast.StarExpr](), 249 reflect.TypeFor[*ast.UnaryExpr](), 250 reflect.TypeFor[*ast.SendStmt](), 251 reflect.TypeFor[*ast.SelectStmt](), 252 reflect.TypeFor[*ast.ImportSpec](), 253 reflect.TypeFor[*ast.IfStmt](), 254 reflect.TypeFor[*ast.GoStmt](), 255 reflect.TypeFor[*ast.Field](), 256 reflect.TypeFor[*ast.SelectorExpr](), 257 reflect.TypeFor[*ast.StructType](), 258 reflect.TypeFor[*ast.KeyValueExpr](), 259 reflect.TypeFor[*ast.FuncType](), 260 reflect.TypeFor[*ast.FuncLit](), 261 reflect.TypeFor[*ast.FuncDecl](), 262 reflect.TypeFor[*ast.ChanType](), 263 reflect.TypeFor[*ast.CallExpr](), 264 reflect.TypeFor[*ast.CaseClause](), 265 reflect.TypeFor[*ast.CommClause](), 266 reflect.TypeFor[*ast.CompositeLit](), 267 reflect.TypeFor[*ast.EmptyStmt](), 268 reflect.TypeFor[*ast.SwitchStmt](), 269 reflect.TypeFor[*ast.TypeSwitchStmt](), 270 reflect.TypeFor[*ast.TypeAssertExpr](), 271 reflect.TypeFor[*ast.TypeSpec](), 272 reflect.TypeFor[*ast.InterfaceType](), 273 reflect.TypeFor[*ast.BranchStmt](), 274 reflect.TypeFor[*ast.IncDecStmt](), 275 reflect.TypeFor[*ast.BasicLit](), 276 } 277 278 var nodeToASTTypes = map[reflect.Type][]reflect.Type{ 279 reflect.TypeFor[String](): nil, 280 reflect.TypeFor[Token](): nil, 281 reflect.TypeFor[List](): {reflect.TypeFor[*ast.BlockStmt](), reflect.TypeFor[*ast.FieldList]()}, 282 reflect.TypeFor[Builtin](): {reflect.TypeFor[*ast.Ident]()}, 283 reflect.TypeFor[Object](): {reflect.TypeFor[*ast.Ident]()}, 284 reflect.TypeFor[Symbol](): {reflect.TypeFor[*ast.Ident](), reflect.TypeFor[*ast.SelectorExpr]()}, 285 reflect.TypeFor[Any](): allTypes, 286 reflect.TypeFor[RangeStmt](): {reflect.TypeFor[*ast.RangeStmt]()}, 287 reflect.TypeFor[AssignStmt](): {reflect.TypeFor[*ast.AssignStmt]()}, 288 reflect.TypeFor[IndexExpr](): {reflect.TypeFor[*ast.IndexExpr]()}, 289 reflect.TypeFor[Ident](): {reflect.TypeFor[*ast.Ident]()}, 290 reflect.TypeFor[ValueSpec](): {reflect.TypeFor[*ast.ValueSpec]()}, 291 reflect.TypeFor[GenDecl](): {reflect.TypeFor[*ast.GenDecl]()}, 292 reflect.TypeFor[BinaryExpr](): {reflect.TypeFor[*ast.BinaryExpr]()}, 293 reflect.TypeFor[ForStmt](): {reflect.TypeFor[*ast.ForStmt]()}, 294 reflect.TypeFor[ArrayType](): {reflect.TypeFor[*ast.ArrayType]()}, 295 reflect.TypeFor[DeferStmt](): {reflect.TypeFor[*ast.DeferStmt]()}, 296 reflect.TypeFor[MapType](): {reflect.TypeFor[*ast.MapType]()}, 297 reflect.TypeFor[ReturnStmt](): {reflect.TypeFor[*ast.ReturnStmt]()}, 298 reflect.TypeFor[SliceExpr](): {reflect.TypeFor[*ast.SliceExpr]()}, 299 reflect.TypeFor[StarExpr](): {reflect.TypeFor[*ast.StarExpr]()}, 300 reflect.TypeFor[UnaryExpr](): {reflect.TypeFor[*ast.UnaryExpr]()}, 301 reflect.TypeFor[SendStmt](): {reflect.TypeFor[*ast.SendStmt]()}, 302 reflect.TypeFor[SelectStmt](): {reflect.TypeFor[*ast.SelectStmt]()}, 303 reflect.TypeFor[ImportSpec](): {reflect.TypeFor[*ast.ImportSpec]()}, 304 reflect.TypeFor[IfStmt](): {reflect.TypeFor[*ast.IfStmt]()}, 305 reflect.TypeFor[GoStmt](): {reflect.TypeFor[*ast.GoStmt]()}, 306 reflect.TypeFor[Field](): {reflect.TypeFor[*ast.Field]()}, 307 reflect.TypeFor[SelectorExpr](): {reflect.TypeFor[*ast.SelectorExpr]()}, 308 reflect.TypeFor[StructType](): {reflect.TypeFor[*ast.StructType]()}, 309 reflect.TypeFor[KeyValueExpr](): {reflect.TypeFor[*ast.KeyValueExpr]()}, 310 reflect.TypeFor[FuncType](): {reflect.TypeFor[*ast.FuncType]()}, 311 reflect.TypeFor[FuncLit](): {reflect.TypeFor[*ast.FuncLit]()}, 312 reflect.TypeFor[FuncDecl](): {reflect.TypeFor[*ast.FuncDecl]()}, 313 reflect.TypeFor[ChanType](): {reflect.TypeFor[*ast.ChanType]()}, 314 reflect.TypeFor[CallExpr](): {reflect.TypeFor[*ast.CallExpr]()}, 315 reflect.TypeFor[CaseClause](): {reflect.TypeFor[*ast.CaseClause]()}, 316 reflect.TypeFor[CommClause](): {reflect.TypeFor[*ast.CommClause]()}, 317 reflect.TypeFor[CompositeLit](): {reflect.TypeFor[*ast.CompositeLit]()}, 318 reflect.TypeFor[EmptyStmt](): {reflect.TypeFor[*ast.EmptyStmt]()}, 319 reflect.TypeFor[SwitchStmt](): {reflect.TypeFor[*ast.SwitchStmt]()}, 320 reflect.TypeFor[TypeSwitchStmt](): {reflect.TypeFor[*ast.TypeSwitchStmt]()}, 321 reflect.TypeFor[TypeAssertExpr](): {reflect.TypeFor[*ast.TypeAssertExpr]()}, 322 reflect.TypeFor[TypeSpec](): {reflect.TypeFor[*ast.TypeSpec]()}, 323 reflect.TypeFor[InterfaceType](): {reflect.TypeFor[*ast.InterfaceType]()}, 324 reflect.TypeFor[BranchStmt](): {reflect.TypeFor[*ast.BranchStmt]()}, 325 reflect.TypeFor[IncDecStmt](): {reflect.TypeFor[*ast.IncDecStmt]()}, 326 reflect.TypeFor[BasicLit](): {reflect.TypeFor[*ast.BasicLit]()}, 327 reflect.TypeFor[IntegerLiteral](): {reflect.TypeFor[*ast.BasicLit](), reflect.TypeFor[*ast.UnaryExpr]()}, 328 reflect.TypeFor[TrulyConstantExpression](): allTypes, // this is an over-approximation, which is fine 329 } 330 331 var requiresTypeInfo = map[string]bool{ 332 "Symbol": true, 333 "Builtin": true, 334 "Object": true, 335 "IntegerLiteral": true, 336 "TrulyConstantExpression": true, 337 } 338 339 type Parser struct { 340 // Allow nodes that rely on type information 341 AllowTypeInfo bool 342 343 f *token.File 344 cur item 345 last *item 346 nextItem func() (item, bool) 347 348 bindings map[string]int 349 } 350 351 func (p *Parser) bindingIndex(name string) int { 352 if p.bindings == nil { 353 p.bindings = map[string]int{} 354 } 355 if idx, ok := p.bindings[name]; ok { 356 return idx 357 } 358 idx := len(p.bindings) 359 p.bindings[name] = idx 360 return idx 361 } 362 363 func (p *Parser) Parse(s string) (Pattern, error) { 364 f := token.NewFileSet().AddFile("<input>", -1, len(s)) 365 366 // Run the lexer iterator as a coroutine. 367 // The parser will call 'next' to consume each item. 368 // After the parser returns, we must call 'stop' to 369 // terminate the coroutine. 370 next, stop := iter.Pull(lex(f, s)) 371 defer stop() 372 373 p.cur = item{} 374 p.last = nil 375 p.f = f 376 p.nextItem = next 377 378 // Parse. 379 root, err := p.node() 380 if err != nil { 381 return Pattern{}, err 382 } 383 // Consume final EOF token. 384 if item, ok := next(); !ok || item.typ != itemEOF { 385 return Pattern{}, fmt.Errorf("unexpected token %s after end of pattern", item.typ) 386 } 387 388 if len(p.bindings) > 64 { 389 return Pattern{}, errors.New("encountered more than 64 bindings") 390 } 391 392 bindings := make([]string, len(p.bindings)) 393 for name, idx := range p.bindings { 394 bindings[idx] = name 395 } 396 397 _, isSymbol := root.(Symbol) 398 sym := collectSymbols(root, isSymbol) 399 rootSyms := collectRootCallSymbols(root) 400 relevantMap := map[reflect.Type]struct{}{} 401 collectEntryNodes(root, relevantMap) 402 relevantNodes := make([]ast.Node, 0, len(relevantMap)) 403 for k := range relevantMap { 404 relevantNodes = append(relevantNodes, reflect.Zero(k).Interface().(ast.Node)) 405 } 406 return Pattern{ 407 Root: root, 408 EntryNodes: relevantNodes, 409 SymbolsPattern: sym, 410 RootCallSymbols: rootSyms, 411 Bindings: bindings, 412 }, nil 413 } 414 415 func (p *Parser) next() item { 416 if p.last != nil { 417 n := *p.last 418 p.last = nil 419 return n 420 } 421 var ok bool 422 p.cur, ok = p.nextItem() 423 if !ok { 424 p.cur = item{typ: eof} 425 } 426 return p.cur 427 } 428 429 func (p *Parser) rewind() { 430 p.last = &p.cur 431 } 432 433 func (p *Parser) peek() item { 434 n := p.next() 435 p.rewind() 436 return n 437 } 438 439 func (p *Parser) accept(typ itemType) (item, bool) { 440 n := p.next() 441 if n.typ == typ { 442 return n, true 443 } 444 p.rewind() 445 return item{}, false 446 } 447 448 func (p *Parser) unexpectedToken(valid string) error { 449 if p.cur.typ == itemError { 450 return fmt.Errorf("error lexing input: %s", p.cur.val) 451 } 452 var got string 453 switch p.cur.typ { 454 case itemTypeName, itemVariable, itemString: 455 got = p.cur.val 456 default: 457 got = "'" + p.cur.typ.String() + "'" 458 } 459 460 pos := p.f.Position(token.Pos(p.cur.pos)) 461 return fmt.Errorf("%s: expected %s, found %s", pos, valid, got) 462 } 463 464 func (p *Parser) node() (Node, error) { 465 if _, ok := p.accept(itemLeftParen); !ok { 466 return nil, p.unexpectedToken("'('") 467 } 468 typ, ok := p.accept(itemTypeName) 469 if !ok { 470 return nil, p.unexpectedToken("Node type") 471 } 472 473 var objs []Node 474 for { 475 if _, ok := p.accept(itemRightParen); ok { 476 break 477 } else { 478 p.rewind() 479 obj, err := p.object() 480 if err != nil { 481 return nil, err 482 } 483 objs = append(objs, obj) 484 } 485 } 486 487 node, err := p.populateNode(typ.val, objs) 488 if err != nil { 489 return nil, err 490 } 491 if node, ok := node.(Binding); ok { 492 node.idx = p.bindingIndex(node.Name) 493 } 494 return node, nil 495 } 496 497 func populateNode(typ string, objs []Node, allowTypeInfo bool) (Node, error) { 498 T, ok := structNodes[typ] 499 if !ok { 500 return nil, fmt.Errorf("unknown node %s", typ) 501 } 502 503 if !allowTypeInfo && requiresTypeInfo[typ] { 504 return nil, fmt.Errorf("Node %s requires type information", typ) 505 } 506 507 pv := reflect.New(T) 508 v := pv.Elem() 509 510 if v.NumField() == 1 { 511 f := v.Field(0) 512 if f.Type().Kind() == reflect.Slice { 513 // Variadic node 514 f.Set(reflect.AppendSlice(f, reflect.ValueOf(objs))) 515 return v.Interface().(Node), nil 516 } 517 } 518 519 n := -1 520 for i := 0; i < T.NumField(); i++ { 521 if !T.Field(i).IsExported() { 522 break 523 } 524 n = i 525 } 526 527 if len(objs) != n+1 { 528 return nil, fmt.Errorf("tried to initialize node %s with %d values, expected %d", typ, len(objs), n+1) 529 } 530 531 for i := 0; i < v.NumField(); i++ { 532 if !T.Field(i).IsExported() { 533 break 534 } 535 f := v.Field(i) 536 if f.Kind() == reflect.String { 537 if obj, ok := objs[i].(String); ok { 538 f.Set(reflect.ValueOf(string(obj))) 539 } else { 540 return nil, fmt.Errorf("first argument of (Binding name node) must be string, but got %s", objs[i]) 541 } 542 } else { 543 f.Set(reflect.ValueOf(objs[i])) 544 } 545 } 546 return v.Interface().(Node), nil 547 } 548 549 func (p *Parser) populateNode(typ string, objs []Node) (Node, error) { 550 return populateNode(typ, objs, p.AllowTypeInfo) 551 } 552 553 var structNodes = map[string]reflect.Type{ 554 "Any": reflect.TypeFor[Any](), 555 "Ellipsis": reflect.TypeFor[Ellipsis](), 556 "List": reflect.TypeFor[List](), 557 "Binding": reflect.TypeFor[Binding](), 558 "RangeStmt": reflect.TypeFor[RangeStmt](), 559 "AssignStmt": reflect.TypeFor[AssignStmt](), 560 "IndexExpr": reflect.TypeFor[IndexExpr](), 561 "Ident": reflect.TypeFor[Ident](), 562 "Builtin": reflect.TypeFor[Builtin](), 563 "ValueSpec": reflect.TypeFor[ValueSpec](), 564 "GenDecl": reflect.TypeFor[GenDecl](), 565 "BinaryExpr": reflect.TypeFor[BinaryExpr](), 566 "ForStmt": reflect.TypeFor[ForStmt](), 567 "ArrayType": reflect.TypeFor[ArrayType](), 568 "DeferStmt": reflect.TypeFor[DeferStmt](), 569 "MapType": reflect.TypeFor[MapType](), 570 "ReturnStmt": reflect.TypeFor[ReturnStmt](), 571 "SliceExpr": reflect.TypeFor[SliceExpr](), 572 "StarExpr": reflect.TypeFor[StarExpr](), 573 "UnaryExpr": reflect.TypeFor[UnaryExpr](), 574 "SendStmt": reflect.TypeFor[SendStmt](), 575 "SelectStmt": reflect.TypeFor[SelectStmt](), 576 "ImportSpec": reflect.TypeFor[ImportSpec](), 577 "IfStmt": reflect.TypeFor[IfStmt](), 578 "GoStmt": reflect.TypeFor[GoStmt](), 579 "Field": reflect.TypeFor[Field](), 580 "SelectorExpr": reflect.TypeFor[SelectorExpr](), 581 "StructType": reflect.TypeFor[StructType](), 582 "KeyValueExpr": reflect.TypeFor[KeyValueExpr](), 583 "FuncType": reflect.TypeFor[FuncType](), 584 "FuncLit": reflect.TypeFor[FuncLit](), 585 "FuncDecl": reflect.TypeFor[FuncDecl](), 586 "ChanType": reflect.TypeFor[ChanType](), 587 "CallExpr": reflect.TypeFor[CallExpr](), 588 "CaseClause": reflect.TypeFor[CaseClause](), 589 "CommClause": reflect.TypeFor[CommClause](), 590 "CompositeLit": reflect.TypeFor[CompositeLit](), 591 "EmptyStmt": reflect.TypeFor[EmptyStmt](), 592 "SwitchStmt": reflect.TypeFor[SwitchStmt](), 593 "TypeSwitchStmt": reflect.TypeFor[TypeSwitchStmt](), 594 "TypeAssertExpr": reflect.TypeFor[TypeAssertExpr](), 595 "TypeSpec": reflect.TypeFor[TypeSpec](), 596 "InterfaceType": reflect.TypeFor[InterfaceType](), 597 "BranchStmt": reflect.TypeFor[BranchStmt](), 598 "IncDecStmt": reflect.TypeFor[IncDecStmt](), 599 "BasicLit": reflect.TypeFor[BasicLit](), 600 "Object": reflect.TypeFor[Object](), 601 "Symbol": reflect.TypeFor[Symbol](), 602 "Or": reflect.TypeFor[Or](), 603 "Not": reflect.TypeFor[Not](), 604 "IntegerLiteral": reflect.TypeFor[IntegerLiteral](), 605 "TrulyConstantExpression": reflect.TypeFor[TrulyConstantExpression](), 606 } 607 608 func (p *Parser) object() (Node, error) { 609 n := p.next() 610 switch n.typ { 611 case itemLeftParen: 612 p.rewind() 613 node, err := p.node() 614 if err != nil { 615 return node, err 616 } 617 if p.peek().typ == itemColon { 618 p.next() 619 tail, err := p.object() 620 if err != nil { 621 return node, err 622 } 623 return List{Head: node, Tail: tail}, nil 624 } 625 return node, nil 626 case itemLeftBracket: 627 p.rewind() 628 return p.array() 629 case itemVariable: 630 v := n 631 if v.val == "nil" { 632 return Nil{}, nil 633 } 634 var b Binding 635 if _, ok := p.accept(itemAt); ok { 636 o, err := p.node() 637 if err != nil { 638 return nil, err 639 } 640 b = Binding{ 641 Name: v.val, 642 Node: o, 643 idx: p.bindingIndex(v.val), 644 } 645 } else { 646 p.rewind() 647 b = Binding{ 648 Name: v.val, 649 idx: p.bindingIndex(v.val), 650 } 651 } 652 if p.peek().typ == itemColon { 653 p.next() 654 tail, err := p.object() 655 if err != nil { 656 return b, err 657 } 658 return List{Head: b, Tail: tail}, nil 659 } 660 return b, nil 661 case itemBlank: 662 if p.peek().typ == itemColon { 663 p.next() 664 tail, err := p.object() 665 if err != nil { 666 return Any{}, err 667 } 668 return List{Head: Any{}, Tail: tail}, nil 669 } 670 return Any{}, nil 671 case itemString: 672 return String(n.val), nil 673 default: 674 return nil, p.unexpectedToken("object") 675 } 676 } 677 678 func (p *Parser) array() (Node, error) { 679 if _, ok := p.accept(itemLeftBracket); !ok { 680 return nil, p.unexpectedToken("'['") 681 } 682 683 var objs []Node 684 for { 685 if _, ok := p.accept(itemRightBracket); ok { 686 break 687 } else { 688 p.rewind() 689 obj, err := p.object() 690 if err != nil { 691 return nil, err 692 } 693 objs = append(objs, obj) 694 } 695 } 696 697 tail := List{} 698 for i := len(objs) - 1; i >= 0; i-- { 699 l := List{ 700 Head: objs[i], 701 Tail: tail, 702 } 703 tail = l 704 } 705 return tail, nil 706 } 707 708 /* 709 Node ::= itemLeftParen itemTypeName Object* itemRightParen 710 Object ::= Node | Array | Binding | itemVariable | itemBlank | itemString 711 Array := itemLeftBracket Object* itemRightBracket 712 Array := Object itemColon Object 713 Binding ::= itemVariable itemAt Node 714 */