+++ /dev/null
-package pattern
-
-import (
- "fmt"
- "go/ast"
- "go/token"
- "reflect"
-)
-
-type Pattern struct {
- Root Node
- // Relevant contains instances of ast.Node that could potentially
- // initiate a successful match of the pattern.
- Relevant []reflect.Type
-}
-
-func MustParse(s string) Pattern {
- p := &Parser{AllowTypeInfo: true}
- pat, err := p.Parse(s)
- if err != nil {
- panic(err)
- }
- return pat
-}
-
-func roots(node Node) []reflect.Type {
- switch node := node.(type) {
- case Or:
- var out []reflect.Type
- for _, el := range node.Nodes {
- out = append(out, roots(el)...)
- }
- return out
- case Not:
- return roots(node.Node)
- case Binding:
- return roots(node.Node)
- case Nil, nil:
- // this branch is reached via bindings
- return allTypes
- default:
- Ts, ok := nodeToASTTypes[reflect.TypeOf(node)]
- if !ok {
- panic(fmt.Sprintf("internal error: unhandled type %T", node))
- }
- return Ts
- }
-}
-
-var allTypes = []reflect.Type{
- reflect.TypeOf((*ast.RangeStmt)(nil)),
- reflect.TypeOf((*ast.AssignStmt)(nil)),
- reflect.TypeOf((*ast.IndexExpr)(nil)),
- reflect.TypeOf((*ast.Ident)(nil)),
- reflect.TypeOf((*ast.ValueSpec)(nil)),
- reflect.TypeOf((*ast.GenDecl)(nil)),
- reflect.TypeOf((*ast.BinaryExpr)(nil)),
- reflect.TypeOf((*ast.ForStmt)(nil)),
- reflect.TypeOf((*ast.ArrayType)(nil)),
- reflect.TypeOf((*ast.DeferStmt)(nil)),
- reflect.TypeOf((*ast.MapType)(nil)),
- reflect.TypeOf((*ast.ReturnStmt)(nil)),
- reflect.TypeOf((*ast.SliceExpr)(nil)),
- reflect.TypeOf((*ast.StarExpr)(nil)),
- reflect.TypeOf((*ast.UnaryExpr)(nil)),
- reflect.TypeOf((*ast.SendStmt)(nil)),
- reflect.TypeOf((*ast.SelectStmt)(nil)),
- reflect.TypeOf((*ast.ImportSpec)(nil)),
- reflect.TypeOf((*ast.IfStmt)(nil)),
- reflect.TypeOf((*ast.GoStmt)(nil)),
- reflect.TypeOf((*ast.Field)(nil)),
- reflect.TypeOf((*ast.SelectorExpr)(nil)),
- reflect.TypeOf((*ast.StructType)(nil)),
- reflect.TypeOf((*ast.KeyValueExpr)(nil)),
- reflect.TypeOf((*ast.FuncType)(nil)),
- reflect.TypeOf((*ast.FuncLit)(nil)),
- reflect.TypeOf((*ast.FuncDecl)(nil)),
- reflect.TypeOf((*ast.ChanType)(nil)),
- reflect.TypeOf((*ast.CallExpr)(nil)),
- reflect.TypeOf((*ast.CaseClause)(nil)),
- reflect.TypeOf((*ast.CommClause)(nil)),
- reflect.TypeOf((*ast.CompositeLit)(nil)),
- reflect.TypeOf((*ast.EmptyStmt)(nil)),
- reflect.TypeOf((*ast.SwitchStmt)(nil)),
- reflect.TypeOf((*ast.TypeSwitchStmt)(nil)),
- reflect.TypeOf((*ast.TypeAssertExpr)(nil)),
- reflect.TypeOf((*ast.TypeSpec)(nil)),
- reflect.TypeOf((*ast.InterfaceType)(nil)),
- reflect.TypeOf((*ast.BranchStmt)(nil)),
- reflect.TypeOf((*ast.IncDecStmt)(nil)),
- reflect.TypeOf((*ast.BasicLit)(nil)),
-}
-
-var nodeToASTTypes = map[reflect.Type][]reflect.Type{
- reflect.TypeOf(String("")): nil,
- reflect.TypeOf(Token(0)): nil,
- reflect.TypeOf(List{}): {reflect.TypeOf((*ast.BlockStmt)(nil)), reflect.TypeOf((*ast.FieldList)(nil))},
- reflect.TypeOf(Builtin{}): {reflect.TypeOf((*ast.Ident)(nil))},
- reflect.TypeOf(Object{}): {reflect.TypeOf((*ast.Ident)(nil))},
- reflect.TypeOf(Function{}): {reflect.TypeOf((*ast.Ident)(nil)), reflect.TypeOf((*ast.SelectorExpr)(nil))},
- reflect.TypeOf(Any{}): allTypes,
- reflect.TypeOf(RangeStmt{}): {reflect.TypeOf((*ast.RangeStmt)(nil))},
- reflect.TypeOf(AssignStmt{}): {reflect.TypeOf((*ast.AssignStmt)(nil))},
- reflect.TypeOf(IndexExpr{}): {reflect.TypeOf((*ast.IndexExpr)(nil))},
- reflect.TypeOf(Ident{}): {reflect.TypeOf((*ast.Ident)(nil))},
- reflect.TypeOf(ValueSpec{}): {reflect.TypeOf((*ast.ValueSpec)(nil))},
- reflect.TypeOf(GenDecl{}): {reflect.TypeOf((*ast.GenDecl)(nil))},
- reflect.TypeOf(BinaryExpr{}): {reflect.TypeOf((*ast.BinaryExpr)(nil))},
- reflect.TypeOf(ForStmt{}): {reflect.TypeOf((*ast.ForStmt)(nil))},
- reflect.TypeOf(ArrayType{}): {reflect.TypeOf((*ast.ArrayType)(nil))},
- reflect.TypeOf(DeferStmt{}): {reflect.TypeOf((*ast.DeferStmt)(nil))},
- reflect.TypeOf(MapType{}): {reflect.TypeOf((*ast.MapType)(nil))},
- reflect.TypeOf(ReturnStmt{}): {reflect.TypeOf((*ast.ReturnStmt)(nil))},
- reflect.TypeOf(SliceExpr{}): {reflect.TypeOf((*ast.SliceExpr)(nil))},
- reflect.TypeOf(StarExpr{}): {reflect.TypeOf((*ast.StarExpr)(nil))},
- reflect.TypeOf(UnaryExpr{}): {reflect.TypeOf((*ast.UnaryExpr)(nil))},
- reflect.TypeOf(SendStmt{}): {reflect.TypeOf((*ast.SendStmt)(nil))},
- reflect.TypeOf(SelectStmt{}): {reflect.TypeOf((*ast.SelectStmt)(nil))},
- reflect.TypeOf(ImportSpec{}): {reflect.TypeOf((*ast.ImportSpec)(nil))},
- reflect.TypeOf(IfStmt{}): {reflect.TypeOf((*ast.IfStmt)(nil))},
- reflect.TypeOf(GoStmt{}): {reflect.TypeOf((*ast.GoStmt)(nil))},
- reflect.TypeOf(Field{}): {reflect.TypeOf((*ast.Field)(nil))},
- reflect.TypeOf(SelectorExpr{}): {reflect.TypeOf((*ast.SelectorExpr)(nil))},
- reflect.TypeOf(StructType{}): {reflect.TypeOf((*ast.StructType)(nil))},
- reflect.TypeOf(KeyValueExpr{}): {reflect.TypeOf((*ast.KeyValueExpr)(nil))},
- reflect.TypeOf(FuncType{}): {reflect.TypeOf((*ast.FuncType)(nil))},
- reflect.TypeOf(FuncLit{}): {reflect.TypeOf((*ast.FuncLit)(nil))},
- reflect.TypeOf(FuncDecl{}): {reflect.TypeOf((*ast.FuncDecl)(nil))},
- reflect.TypeOf(ChanType{}): {reflect.TypeOf((*ast.ChanType)(nil))},
- reflect.TypeOf(CallExpr{}): {reflect.TypeOf((*ast.CallExpr)(nil))},
- reflect.TypeOf(CaseClause{}): {reflect.TypeOf((*ast.CaseClause)(nil))},
- reflect.TypeOf(CommClause{}): {reflect.TypeOf((*ast.CommClause)(nil))},
- reflect.TypeOf(CompositeLit{}): {reflect.TypeOf((*ast.CompositeLit)(nil))},
- reflect.TypeOf(EmptyStmt{}): {reflect.TypeOf((*ast.EmptyStmt)(nil))},
- reflect.TypeOf(SwitchStmt{}): {reflect.TypeOf((*ast.SwitchStmt)(nil))},
- reflect.TypeOf(TypeSwitchStmt{}): {reflect.TypeOf((*ast.TypeSwitchStmt)(nil))},
- reflect.TypeOf(TypeAssertExpr{}): {reflect.TypeOf((*ast.TypeAssertExpr)(nil))},
- reflect.TypeOf(TypeSpec{}): {reflect.TypeOf((*ast.TypeSpec)(nil))},
- reflect.TypeOf(InterfaceType{}): {reflect.TypeOf((*ast.InterfaceType)(nil))},
- reflect.TypeOf(BranchStmt{}): {reflect.TypeOf((*ast.BranchStmt)(nil))},
- reflect.TypeOf(IncDecStmt{}): {reflect.TypeOf((*ast.IncDecStmt)(nil))},
- reflect.TypeOf(BasicLit{}): {reflect.TypeOf((*ast.BasicLit)(nil))},
-}
-
-var requiresTypeInfo = map[string]bool{
- "Function": true,
- "Builtin": true,
- "Object": true,
-}
-
-type Parser struct {
- // Allow nodes that rely on type information
- AllowTypeInfo bool
-
- lex *lexer
- cur item
- last *item
- items chan item
-}
-
-func (p *Parser) Parse(s string) (Pattern, error) {
- p.cur = item{}
- p.last = nil
- p.items = nil
-
- fset := token.NewFileSet()
- p.lex = &lexer{
- f: fset.AddFile("<input>", -1, len(s)),
- input: s,
- items: make(chan item),
- }
- go p.lex.run()
- p.items = p.lex.items
- root, err := p.node()
- if err != nil {
- // drain lexer if parsing failed
- for range p.lex.items {
- }
- return Pattern{}, err
- }
- if item := <-p.lex.items; item.typ != itemEOF {
- return Pattern{}, fmt.Errorf("unexpected token %s after end of pattern", item.typ)
- }
- return Pattern{
- Root: root,
- Relevant: roots(root),
- }, nil
-}
-
-func (p *Parser) next() item {
- if p.last != nil {
- n := *p.last
- p.last = nil
- return n
- }
- var ok bool
- p.cur, ok = <-p.items
- if !ok {
- p.cur = item{typ: eof}
- }
- return p.cur
-}
-
-func (p *Parser) rewind() {
- p.last = &p.cur
-}
-
-func (p *Parser) peek() item {
- n := p.next()
- p.rewind()
- return n
-}
-
-func (p *Parser) accept(typ itemType) (item, bool) {
- n := p.next()
- if n.typ == typ {
- return n, true
- }
- p.rewind()
- return item{}, false
-}
-
-func (p *Parser) unexpectedToken(valid string) error {
- if p.cur.typ == itemError {
- return fmt.Errorf("error lexing input: %s", p.cur.val)
- }
- var got string
- switch p.cur.typ {
- case itemTypeName, itemVariable, itemString:
- got = p.cur.val
- default:
- got = "'" + p.cur.typ.String() + "'"
- }
-
- pos := p.lex.f.Position(token.Pos(p.cur.pos))
- return fmt.Errorf("%s: expected %s, found %s", pos, valid, got)
-}
-
-func (p *Parser) node() (Node, error) {
- if _, ok := p.accept(itemLeftParen); !ok {
- return nil, p.unexpectedToken("'('")
- }
- typ, ok := p.accept(itemTypeName)
- if !ok {
- return nil, p.unexpectedToken("Node type")
- }
-
- var objs []Node
- for {
- if _, ok := p.accept(itemRightParen); ok {
- break
- } else {
- p.rewind()
- obj, err := p.object()
- if err != nil {
- return nil, err
- }
- objs = append(objs, obj)
- }
- }
-
- return p.populateNode(typ.val, objs)
-}
-
-func populateNode(typ string, objs []Node, allowTypeInfo bool) (Node, error) {
- T, ok := structNodes[typ]
- if !ok {
- return nil, fmt.Errorf("unknown node %s", typ)
- }
-
- if !allowTypeInfo && requiresTypeInfo[typ] {
- return nil, fmt.Errorf("Node %s requires type information", typ)
- }
-
- pv := reflect.New(T)
- v := pv.Elem()
-
- if v.NumField() == 1 {
- f := v.Field(0)
- if f.Type().Kind() == reflect.Slice {
- // Variadic node
- f.Set(reflect.AppendSlice(f, reflect.ValueOf(objs)))
- return v.Interface().(Node), nil
- }
- }
- if len(objs) != v.NumField() {
- return nil, fmt.Errorf("tried to initialize node %s with %d values, expected %d", typ, len(objs), v.NumField())
- }
- for i := 0; i < v.NumField(); i++ {
- f := v.Field(i)
- if f.Kind() == reflect.String {
- if obj, ok := objs[i].(String); ok {
- f.Set(reflect.ValueOf(string(obj)))
- } else {
- return nil, fmt.Errorf("first argument of (Binding name node) must be string, but got %s", objs[i])
- }
- } else {
- f.Set(reflect.ValueOf(objs[i]))
- }
- }
- return v.Interface().(Node), nil
-}
-
-func (p *Parser) populateNode(typ string, objs []Node) (Node, error) {
- return populateNode(typ, objs, p.AllowTypeInfo)
-}
-
-var structNodes = map[string]reflect.Type{
- "Any": reflect.TypeOf(Any{}),
- "Ellipsis": reflect.TypeOf(Ellipsis{}),
- "List": reflect.TypeOf(List{}),
- "Binding": reflect.TypeOf(Binding{}),
- "RangeStmt": reflect.TypeOf(RangeStmt{}),
- "AssignStmt": reflect.TypeOf(AssignStmt{}),
- "IndexExpr": reflect.TypeOf(IndexExpr{}),
- "Ident": reflect.TypeOf(Ident{}),
- "Builtin": reflect.TypeOf(Builtin{}),
- "ValueSpec": reflect.TypeOf(ValueSpec{}),
- "GenDecl": reflect.TypeOf(GenDecl{}),
- "BinaryExpr": reflect.TypeOf(BinaryExpr{}),
- "ForStmt": reflect.TypeOf(ForStmt{}),
- "ArrayType": reflect.TypeOf(ArrayType{}),
- "DeferStmt": reflect.TypeOf(DeferStmt{}),
- "MapType": reflect.TypeOf(MapType{}),
- "ReturnStmt": reflect.TypeOf(ReturnStmt{}),
- "SliceExpr": reflect.TypeOf(SliceExpr{}),
- "StarExpr": reflect.TypeOf(StarExpr{}),
- "UnaryExpr": reflect.TypeOf(UnaryExpr{}),
- "SendStmt": reflect.TypeOf(SendStmt{}),
- "SelectStmt": reflect.TypeOf(SelectStmt{}),
- "ImportSpec": reflect.TypeOf(ImportSpec{}),
- "IfStmt": reflect.TypeOf(IfStmt{}),
- "GoStmt": reflect.TypeOf(GoStmt{}),
- "Field": reflect.TypeOf(Field{}),
- "SelectorExpr": reflect.TypeOf(SelectorExpr{}),
- "StructType": reflect.TypeOf(StructType{}),
- "KeyValueExpr": reflect.TypeOf(KeyValueExpr{}),
- "FuncType": reflect.TypeOf(FuncType{}),
- "FuncLit": reflect.TypeOf(FuncLit{}),
- "FuncDecl": reflect.TypeOf(FuncDecl{}),
- "ChanType": reflect.TypeOf(ChanType{}),
- "CallExpr": reflect.TypeOf(CallExpr{}),
- "CaseClause": reflect.TypeOf(CaseClause{}),
- "CommClause": reflect.TypeOf(CommClause{}),
- "CompositeLit": reflect.TypeOf(CompositeLit{}),
- "EmptyStmt": reflect.TypeOf(EmptyStmt{}),
- "SwitchStmt": reflect.TypeOf(SwitchStmt{}),
- "TypeSwitchStmt": reflect.TypeOf(TypeSwitchStmt{}),
- "TypeAssertExpr": reflect.TypeOf(TypeAssertExpr{}),
- "TypeSpec": reflect.TypeOf(TypeSpec{}),
- "InterfaceType": reflect.TypeOf(InterfaceType{}),
- "BranchStmt": reflect.TypeOf(BranchStmt{}),
- "IncDecStmt": reflect.TypeOf(IncDecStmt{}),
- "BasicLit": reflect.TypeOf(BasicLit{}),
- "Object": reflect.TypeOf(Object{}),
- "Function": reflect.TypeOf(Function{}),
- "Or": reflect.TypeOf(Or{}),
- "Not": reflect.TypeOf(Not{}),
-}
-
-func (p *Parser) object() (Node, error) {
- n := p.next()
- switch n.typ {
- case itemLeftParen:
- p.rewind()
- node, err := p.node()
- if err != nil {
- return node, err
- }
- if p.peek().typ == itemColon {
- p.next()
- tail, err := p.object()
- if err != nil {
- return node, err
- }
- return List{Head: node, Tail: tail}, nil
- }
- return node, nil
- case itemLeftBracket:
- p.rewind()
- return p.array()
- case itemVariable:
- v := n
- if v.val == "nil" {
- return Nil{}, nil
- }
- var b Binding
- if _, ok := p.accept(itemAt); ok {
- o, err := p.node()
- if err != nil {
- return nil, err
- }
- b = Binding{
- Name: v.val,
- Node: o,
- }
- } else {
- p.rewind()
- b = Binding{Name: v.val}
- }
- if p.peek().typ == itemColon {
- p.next()
- tail, err := p.object()
- if err != nil {
- return b, err
- }
- return List{Head: b, Tail: tail}, nil
- }
- return b, nil
- case itemBlank:
- return Any{}, nil
- case itemString:
- return String(n.val), nil
- default:
- return nil, p.unexpectedToken("object")
- }
-}
-
-func (p *Parser) array() (Node, error) {
- if _, ok := p.accept(itemLeftBracket); !ok {
- return nil, p.unexpectedToken("'['")
- }
-
- var objs []Node
- for {
- if _, ok := p.accept(itemRightBracket); ok {
- break
- } else {
- p.rewind()
- obj, err := p.object()
- if err != nil {
- return nil, err
- }
- objs = append(objs, obj)
- }
- }
-
- tail := List{}
- for i := len(objs) - 1; i >= 0; i-- {
- l := List{
- Head: objs[i],
- Tail: tail,
- }
- tail = l
- }
- return tail, nil
-}
-
-/*
-Node ::= itemLeftParen itemTypeName Object* itemRightParen
-Object ::= Node | Array | Binding | itemVariable | itemBlank | itemString
-Array := itemLeftBracket Object* itemRightBracket
-Array := Object itemColon Object
-Binding ::= itemVariable itemAt Node
-*/
projects / dotfiles / .git / blobdiff