Debian Codegraph @

pattern/parser.go

raw
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 */