.config/coc/extensions/coc-go-data/tools/pkg/mod/honnef.co/go/tools@v0.0.1-2020.1.5/pattern/parser.go

   1 package pattern
   2
   3 import (
   4         "fmt"
   5         "go/ast"
   6         "go/token"
   7         "reflect"
   8 )
   9
  10 type Pattern struct {
  11         Root Node
  12         // Relevant contains instances of ast.Node that could potentially
  13         // initiate a successful match of the pattern.
  14         Relevant []reflect.Type
  15 }
  16
  17 func MustParse(s string) Pattern {
  18         p := &Parser{AllowTypeInfo: true}
  19         pat, err := p.Parse(s)
  20         if err != nil {
  21                 panic(err)
  22         }
  23         return pat
  24 }
  25
  26 func roots(node Node) []reflect.Type {
  27         switch node := node.(type) {
  28         case Or:
  29                 var out []reflect.Type
  30                 for _, el := range node.Nodes {
  31                         out = append(out, roots(el)...)
  32                 }
  33                 return out
  34         case Not:
  35                 return roots(node.Node)
  36         case Binding:
  37                 return roots(node.Node)
  38         case Nil, nil:
  39                 // this branch is reached via bindings
  40                 return allTypes
  41         default:
  42                 Ts, ok := nodeToASTTypes[reflect.TypeOf(node)]
  43                 if !ok {
  44                         panic(fmt.Sprintf("internal error: unhandled type %T", node))
  45                 }
  46                 return Ts
  47         }
  48 }
  49
  50 var allTypes = []reflect.Type{
  51         reflect.TypeOf((*ast.RangeStmt)(nil)),
  52         reflect.TypeOf((*ast.AssignStmt)(nil)),
  53         reflect.TypeOf((*ast.IndexExpr)(nil)),
  54         reflect.TypeOf((*ast.Ident)(nil)),
  55         reflect.TypeOf((*ast.ValueSpec)(nil)),
  56         reflect.TypeOf((*ast.GenDecl)(nil)),
  57         reflect.TypeOf((*ast.BinaryExpr)(nil)),
  58         reflect.TypeOf((*ast.ForStmt)(nil)),
  59         reflect.TypeOf((*ast.ArrayType)(nil)),
  60         reflect.TypeOf((*ast.DeferStmt)(nil)),
  61         reflect.TypeOf((*ast.MapType)(nil)),
  62         reflect.TypeOf((*ast.ReturnStmt)(nil)),
  63         reflect.TypeOf((*ast.SliceExpr)(nil)),
  64         reflect.TypeOf((*ast.StarExpr)(nil)),
  65         reflect.TypeOf((*ast.UnaryExpr)(nil)),
  66         reflect.TypeOf((*ast.SendStmt)(nil)),
  67         reflect.TypeOf((*ast.SelectStmt)(nil)),
  68         reflect.TypeOf((*ast.ImportSpec)(nil)),
  69         reflect.TypeOf((*ast.IfStmt)(nil)),
  70         reflect.TypeOf((*ast.GoStmt)(nil)),
  71         reflect.TypeOf((*ast.Field)(nil)),
  72         reflect.TypeOf((*ast.SelectorExpr)(nil)),
  73         reflect.TypeOf((*ast.StructType)(nil)),
  74         reflect.TypeOf((*ast.KeyValueExpr)(nil)),
  75         reflect.TypeOf((*ast.FuncType)(nil)),
  76         reflect.TypeOf((*ast.FuncLit)(nil)),
  77         reflect.TypeOf((*ast.FuncDecl)(nil)),
  78         reflect.TypeOf((*ast.ChanType)(nil)),
  79         reflect.TypeOf((*ast.CallExpr)(nil)),
  80         reflect.TypeOf((*ast.CaseClause)(nil)),
  81         reflect.TypeOf((*ast.CommClause)(nil)),
  82         reflect.TypeOf((*ast.CompositeLit)(nil)),
  83         reflect.TypeOf((*ast.EmptyStmt)(nil)),
  84         reflect.TypeOf((*ast.SwitchStmt)(nil)),
  85         reflect.TypeOf((*ast.TypeSwitchStmt)(nil)),
  86         reflect.TypeOf((*ast.TypeAssertExpr)(nil)),
  87         reflect.TypeOf((*ast.TypeSpec)(nil)),
  88         reflect.TypeOf((*ast.InterfaceType)(nil)),
  89         reflect.TypeOf((*ast.BranchStmt)(nil)),
  90         reflect.TypeOf((*ast.IncDecStmt)(nil)),
  91         reflect.TypeOf((*ast.BasicLit)(nil)),
  92 }
  93
  94 var nodeToASTTypes = map[reflect.Type][]reflect.Type{
  95         reflect.TypeOf(String("")):       nil,
  96         reflect.TypeOf(Token(0)):         nil,
  97         reflect.TypeOf(List{}):           {reflect.TypeOf((*ast.BlockStmt)(nil)), reflect.TypeOf((*ast.FieldList)(nil))},
  98         reflect.TypeOf(Builtin{}):        {reflect.TypeOf((*ast.Ident)(nil))},
  99         reflect.TypeOf(Object{}):         {reflect.TypeOf((*ast.Ident)(nil))},
 100         reflect.TypeOf(Function{}):       {reflect.TypeOf((*ast.Ident)(nil)), reflect.TypeOf((*ast.SelectorExpr)(nil))},
 101         reflect.TypeOf(Any{}):            allTypes,
 102         reflect.TypeOf(RangeStmt{}):      {reflect.TypeOf((*ast.RangeStmt)(nil))},
 103         reflect.TypeOf(AssignStmt{}):     {reflect.TypeOf((*ast.AssignStmt)(nil))},
 104         reflect.TypeOf(IndexExpr{}):      {reflect.TypeOf((*ast.IndexExpr)(nil))},
 105         reflect.TypeOf(Ident{}):          {reflect.TypeOf((*ast.Ident)(nil))},
 106         reflect.TypeOf(ValueSpec{}):      {reflect.TypeOf((*ast.ValueSpec)(nil))},
 107         reflect.TypeOf(GenDecl{}):        {reflect.TypeOf((*ast.GenDecl)(nil))},
 108         reflect.TypeOf(BinaryExpr{}):     {reflect.TypeOf((*ast.BinaryExpr)(nil))},
 109         reflect.TypeOf(ForStmt{}):        {reflect.TypeOf((*ast.ForStmt)(nil))},
 110         reflect.TypeOf(ArrayType{}):      {reflect.TypeOf((*ast.ArrayType)(nil))},
 111         reflect.TypeOf(DeferStmt{}):      {reflect.TypeOf((*ast.DeferStmt)(nil))},
 112         reflect.TypeOf(MapType{}):        {reflect.TypeOf((*ast.MapType)(nil))},
 113         reflect.TypeOf(ReturnStmt{}):     {reflect.TypeOf((*ast.ReturnStmt)(nil))},
 114         reflect.TypeOf(SliceExpr{}):      {reflect.TypeOf((*ast.SliceExpr)(nil))},
 115         reflect.TypeOf(StarExpr{}):       {reflect.TypeOf((*ast.StarExpr)(nil))},
 116         reflect.TypeOf(UnaryExpr{}):      {reflect.TypeOf((*ast.UnaryExpr)(nil))},
 117         reflect.TypeOf(SendStmt{}):       {reflect.TypeOf((*ast.SendStmt)(nil))},
 118         reflect.TypeOf(SelectStmt{}):     {reflect.TypeOf((*ast.SelectStmt)(nil))},
 119         reflect.TypeOf(ImportSpec{}):     {reflect.TypeOf((*ast.ImportSpec)(nil))},
 120         reflect.TypeOf(IfStmt{}):         {reflect.TypeOf((*ast.IfStmt)(nil))},
 121         reflect.TypeOf(GoStmt{}):         {reflect.TypeOf((*ast.GoStmt)(nil))},
 122         reflect.TypeOf(Field{}):          {reflect.TypeOf((*ast.Field)(nil))},
 123         reflect.TypeOf(SelectorExpr{}):   {reflect.TypeOf((*ast.SelectorExpr)(nil))},
 124         reflect.TypeOf(StructType{}):     {reflect.TypeOf((*ast.StructType)(nil))},
 125         reflect.TypeOf(KeyValueExpr{}):   {reflect.TypeOf((*ast.KeyValueExpr)(nil))},
 126         reflect.TypeOf(FuncType{}):       {reflect.TypeOf((*ast.FuncType)(nil))},
 127         reflect.TypeOf(FuncLit{}):        {reflect.TypeOf((*ast.FuncLit)(nil))},
 128         reflect.TypeOf(FuncDecl{}):       {reflect.TypeOf((*ast.FuncDecl)(nil))},
 129         reflect.TypeOf(ChanType{}):       {reflect.TypeOf((*ast.ChanType)(nil))},
 130         reflect.TypeOf(CallExpr{}):       {reflect.TypeOf((*ast.CallExpr)(nil))},
 131         reflect.TypeOf(CaseClause{}):     {reflect.TypeOf((*ast.CaseClause)(nil))},
 132         reflect.TypeOf(CommClause{}):     {reflect.TypeOf((*ast.CommClause)(nil))},
 133         reflect.TypeOf(CompositeLit{}):   {reflect.TypeOf((*ast.CompositeLit)(nil))},
 134         reflect.TypeOf(EmptyStmt{}):      {reflect.TypeOf((*ast.EmptyStmt)(nil))},
 135         reflect.TypeOf(SwitchStmt{}):     {reflect.TypeOf((*ast.SwitchStmt)(nil))},
 136         reflect.TypeOf(TypeSwitchStmt{}): {reflect.TypeOf((*ast.TypeSwitchStmt)(nil))},
 137         reflect.TypeOf(TypeAssertExpr{}): {reflect.TypeOf((*ast.TypeAssertExpr)(nil))},
 138         reflect.TypeOf(TypeSpec{}):       {reflect.TypeOf((*ast.TypeSpec)(nil))},
 139         reflect.TypeOf(InterfaceType{}):  {reflect.TypeOf((*ast.InterfaceType)(nil))},
 140         reflect.TypeOf(BranchStmt{}):     {reflect.TypeOf((*ast.BranchStmt)(nil))},
 141         reflect.TypeOf(IncDecStmt{}):     {reflect.TypeOf((*ast.IncDecStmt)(nil))},
 142         reflect.TypeOf(BasicLit{}):       {reflect.TypeOf((*ast.BasicLit)(nil))},
 143 }
 144
 145 var requiresTypeInfo = map[string]bool{
 146         "Function": true,
 147         "Builtin":  true,
 148         "Object":   true,
 149 }
 150
 151 type Parser struct {
 152         // Allow nodes that rely on type information
 153         AllowTypeInfo bool
 154
 155         lex   *lexer
 156         cur   item
 157         last  *item
 158         items chan item
 159 }
 160
 161 func (p *Parser) Parse(s string) (Pattern, error) {
 162         p.cur = item{}
 163         p.last = nil
 164         p.items = nil
 165
 166         fset := token.NewFileSet()
 167         p.lex = &lexer{
 168                 f:     fset.AddFile("<input>", -1, len(s)),
 169                 input: s,
 170                 items: make(chan item),
 171         }
 172         go p.lex.run()
 173         p.items = p.lex.items
 174         root, err := p.node()
 175         if err != nil {
 176                 // drain lexer if parsing failed
 177                 for range p.lex.items {
 178                 }
 179                 return Pattern{}, err
 180         }
 181         if item := <-p.lex.items; item.typ != itemEOF {
 182                 return Pattern{}, fmt.Errorf("unexpected token %s after end of pattern", item.typ)
 183         }
 184         return Pattern{
 185                 Root:     root,
 186                 Relevant: roots(root),
 187         }, nil
 188 }
 189
 190 func (p *Parser) next() item {
 191         if p.last != nil {
 192                 n := *p.last
 193                 p.last = nil
 194                 return n
 195         }
 196         var ok bool
 197         p.cur, ok = <-p.items
 198         if !ok {
 199                 p.cur = item{typ: eof}
 200         }
 201         return p.cur
 202 }
 203
 204 func (p *Parser) rewind() {
 205         p.last = &p.cur
 206 }
 207
 208 func (p *Parser) peek() item {
 209         n := p.next()
 210         p.rewind()
 211         return n
 212 }
 213
 214 func (p *Parser) accept(typ itemType) (item, bool) {
 215         n := p.next()
 216         if n.typ == typ {
 217                 return n, true
 218         }
 219         p.rewind()
 220         return item{}, false
 221 }
 222
 223 func (p *Parser) unexpectedToken(valid string) error {
 224         if p.cur.typ == itemError {
 225                 return fmt.Errorf("error lexing input: %s", p.cur.val)
 226         }
 227         var got string
 228         switch p.cur.typ {
 229         case itemTypeName, itemVariable, itemString:
 230                 got = p.cur.val
 231         default:
 232                 got = "'" + p.cur.typ.String() + "'"
 233         }
 234
 235         pos := p.lex.f.Position(token.Pos(p.cur.pos))
 236         return fmt.Errorf("%s: expected %s, found %s", pos, valid, got)
 237 }
 238
 239 func (p *Parser) node() (Node, error) {
 240         if _, ok := p.accept(itemLeftParen); !ok {
 241                 return nil, p.unexpectedToken("'('")
 242         }
 243         typ, ok := p.accept(itemTypeName)
 244         if !ok {
 245                 return nil, p.unexpectedToken("Node type")
 246         }
 247
 248         var objs []Node
 249         for {
 250                 if _, ok := p.accept(itemRightParen); ok {
 251                         break
 252                 } else {
 253                         p.rewind()
 254                         obj, err := p.object()
 255                         if err != nil {
 256                                 return nil, err
 257                         }
 258                         objs = append(objs, obj)
 259                 }
 260         }
 261
 262         return p.populateNode(typ.val, objs)
 263 }
 264
 265 func populateNode(typ string, objs []Node, allowTypeInfo bool) (Node, error) {
 266         T, ok := structNodes[typ]
 267         if !ok {
 268                 return nil, fmt.Errorf("unknown node %s", typ)
 269         }
 270
 271         if !allowTypeInfo && requiresTypeInfo[typ] {
 272                 return nil, fmt.Errorf("Node %s requires type information", typ)
 273         }
 274
 275         pv := reflect.New(T)
 276         v := pv.Elem()
 277
 278         if v.NumField() == 1 {
 279                 f := v.Field(0)
 280                 if f.Type().Kind() == reflect.Slice {
 281                         // Variadic node
 282                         f.Set(reflect.AppendSlice(f, reflect.ValueOf(objs)))
 283                         return v.Interface().(Node), nil
 284                 }
 285         }
 286         if len(objs) != v.NumField() {
 287                 return nil, fmt.Errorf("tried to initialize node %s with %d values, expected %d", typ, len(objs), v.NumField())
 288         }
 289         for i := 0; i < v.NumField(); i++ {
 290                 f := v.Field(i)
 291                 if f.Kind() == reflect.String {
 292                         if obj, ok := objs[i].(String); ok {
 293                                 f.Set(reflect.ValueOf(string(obj)))
 294                         } else {
 295                                 return nil, fmt.Errorf("first argument of (Binding name node) must be string, but got %s", objs[i])
 296                         }
 297                 } else {
 298                         f.Set(reflect.ValueOf(objs[i]))
 299                 }
 300         }
 301         return v.Interface().(Node), nil
 302 }
 303
 304 func (p *Parser) populateNode(typ string, objs []Node) (Node, error) {
 305         return populateNode(typ, objs, p.AllowTypeInfo)
 306 }
 307
 308 var structNodes = map[string]reflect.Type{
 309         "Any":            reflect.TypeOf(Any{}),
 310         "Ellipsis":       reflect.TypeOf(Ellipsis{}),
 311         "List":           reflect.TypeOf(List{}),
 312         "Binding":        reflect.TypeOf(Binding{}),
 313         "RangeStmt":      reflect.TypeOf(RangeStmt{}),
 314         "AssignStmt":     reflect.TypeOf(AssignStmt{}),
 315         "IndexExpr":      reflect.TypeOf(IndexExpr{}),
 316         "Ident":          reflect.TypeOf(Ident{}),
 317         "Builtin":        reflect.TypeOf(Builtin{}),
 318         "ValueSpec":      reflect.TypeOf(ValueSpec{}),
 319         "GenDecl":        reflect.TypeOf(GenDecl{}),
 320         "BinaryExpr":     reflect.TypeOf(BinaryExpr{}),
 321         "ForStmt":        reflect.TypeOf(ForStmt{}),
 322         "ArrayType":      reflect.TypeOf(ArrayType{}),
 323         "DeferStmt":      reflect.TypeOf(DeferStmt{}),
 324         "MapType":        reflect.TypeOf(MapType{}),
 325         "ReturnStmt":     reflect.TypeOf(ReturnStmt{}),
 326         "SliceExpr":      reflect.TypeOf(SliceExpr{}),
 327         "StarExpr":       reflect.TypeOf(StarExpr{}),
 328         "UnaryExpr":      reflect.TypeOf(UnaryExpr{}),
 329         "SendStmt":       reflect.TypeOf(SendStmt{}),
 330         "SelectStmt":     reflect.TypeOf(SelectStmt{}),
 331         "ImportSpec":     reflect.TypeOf(ImportSpec{}),
 332         "IfStmt":         reflect.TypeOf(IfStmt{}),
 333         "GoStmt":         reflect.TypeOf(GoStmt{}),
 334         "Field":          reflect.TypeOf(Field{}),
 335         "SelectorExpr":   reflect.TypeOf(SelectorExpr{}),
 336         "StructType":     reflect.TypeOf(StructType{}),
 337         "KeyValueExpr":   reflect.TypeOf(KeyValueExpr{}),
 338         "FuncType":       reflect.TypeOf(FuncType{}),
 339         "FuncLit":        reflect.TypeOf(FuncLit{}),
 340         "FuncDecl":       reflect.TypeOf(FuncDecl{}),
 341         "ChanType":       reflect.TypeOf(ChanType{}),
 342         "CallExpr":       reflect.TypeOf(CallExpr{}),
 343         "CaseClause":     reflect.TypeOf(CaseClause{}),
 344         "CommClause":     reflect.TypeOf(CommClause{}),
 345         "CompositeLit":   reflect.TypeOf(CompositeLit{}),
 346         "EmptyStmt":      reflect.TypeOf(EmptyStmt{}),
 347         "SwitchStmt":     reflect.TypeOf(SwitchStmt{}),
 348         "TypeSwitchStmt": reflect.TypeOf(TypeSwitchStmt{}),
 349         "TypeAssertExpr": reflect.TypeOf(TypeAssertExpr{}),
 350         "TypeSpec":       reflect.TypeOf(TypeSpec{}),
 351         "InterfaceType":  reflect.TypeOf(InterfaceType{}),
 352         "BranchStmt":     reflect.TypeOf(BranchStmt{}),
 353         "IncDecStmt":     reflect.TypeOf(IncDecStmt{}),
 354         "BasicLit":       reflect.TypeOf(BasicLit{}),
 355         "Object":         reflect.TypeOf(Object{}),
 356         "Function":       reflect.TypeOf(Function{}),
 357         "Or":             reflect.TypeOf(Or{}),
 358         "Not":            reflect.TypeOf(Not{}),
 359 }
 360
 361 func (p *Parser) object() (Node, error) {
 362         n := p.next()
 363         switch n.typ {
 364         case itemLeftParen:
 365                 p.rewind()
 366                 node, err := p.node()
 367                 if err != nil {
 368                         return node, err
 369                 }
 370                 if p.peek().typ == itemColon {
 371                         p.next()
 372                         tail, err := p.object()
 373                         if err != nil {
 374                                 return node, err
 375                         }
 376                         return List{Head: node, Tail: tail}, nil
 377                 }
 378                 return node, nil
 379         case itemLeftBracket:
 380                 p.rewind()
 381                 return p.array()
 382         case itemVariable:
 383                 v := n
 384                 if v.val == "nil" {
 385                         return Nil{}, nil
 386                 }
 387                 var b Binding
 388                 if _, ok := p.accept(itemAt); ok {
 389                         o, err := p.node()
 390                         if err != nil {
 391                                 return nil, err
 392                         }
 393                         b = Binding{
 394                                 Name: v.val,
 395                                 Node: o,
 396                         }
 397                 } else {
 398                         p.rewind()
 399                         b = Binding{Name: v.val}
 400                 }
 401                 if p.peek().typ == itemColon {
 402                         p.next()
 403                         tail, err := p.object()
 404                         if err != nil {
 405                                 return b, err
 406                         }
 407                         return List{Head: b, Tail: tail}, nil
 408                 }
 409                 return b, nil
 410         case itemBlank:
 411                 return Any{}, nil
 412         case itemString:
 413                 return String(n.val), nil
 414         default:
 415                 return nil, p.unexpectedToken("object")
 416         }
 417 }
 418
 419 func (p *Parser) array() (Node, error) {
 420         if _, ok := p.accept(itemLeftBracket); !ok {
 421                 return nil, p.unexpectedToken("'['")
 422         }
 423
 424         var objs []Node
 425         for {
 426                 if _, ok := p.accept(itemRightBracket); ok {
 427                         break
 428                 } else {
 429                         p.rewind()
 430                         obj, err := p.object()
 431                         if err != nil {
 432                                 return nil, err
 433                         }
 434                         objs = append(objs, obj)
 435                 }
 436         }
 437
 438         tail := List{}
 439         for i := len(objs) - 1; i >= 0; i-- {
 440                 l := List{
 441                         Head: objs[i],
 442                         Tail: tail,
 443                 }
 444                 tail = l
 445         }
 446         return tail, nil
 447 }
 448
 449 /*
 450 Node ::= itemLeftParen itemTypeName Object* itemRightParen
 451 Object ::= Node | Array | Binding | itemVariable | itemBlank | itemString
 452 Array := itemLeftBracket Object* itemRightBracket
 453 Array := Object itemColon Object
 454 Binding ::= itemVariable itemAt Node
 455 */