.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/ast/astutil/enclosing.go

   1 // Copyright 2013 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package astutil
   6
   7 // This file defines utilities for working with source positions.
   8
   9 import (
  10         "fmt"
  11         "go/ast"
  12         "go/token"
  13         "sort"
  14 )
  15
  16 // PathEnclosingInterval returns the node that encloses the source
  17 // interval [start, end), and all its ancestors up to the AST root.
  18 //
  19 // The definition of "enclosing" used by this function considers
  20 // additional whitespace abutting a node to be enclosed by it.
  21 // In this example:
  22 //
  23 //              z := x + y // add them
  24 //                   <-A->
  25 //                  <----B----->
  26 //
  27 // the ast.BinaryExpr(+) node is considered to enclose interval B
  28 // even though its [Pos()..End()) is actually only interval A.
  29 // This behaviour makes user interfaces more tolerant of imperfect
  30 // input.
  31 //
  32 // This function treats tokens as nodes, though they are not included
  33 // in the result. e.g. PathEnclosingInterval("+") returns the
  34 // enclosing ast.BinaryExpr("x + y").
  35 //
  36 // If start==end, the 1-char interval following start is used instead.
  37 //
  38 // The 'exact' result is true if the interval contains only path[0]
  39 // and perhaps some adjacent whitespace.  It is false if the interval
  40 // overlaps multiple children of path[0], or if it contains only
  41 // interior whitespace of path[0].
  42 // In this example:
  43 //
  44 //              z := x + y // add them
  45 //                <--C-->     <---E-->
  46 //                  ^
  47 //                  D
  48 //
  49 // intervals C, D and E are inexact.  C is contained by the
  50 // z-assignment statement, because it spans three of its children (:=,
  51 // x, +).  So too is the 1-char interval D, because it contains only
  52 // interior whitespace of the assignment.  E is considered interior
  53 // whitespace of the BlockStmt containing the assignment.
  54 //
  55 // Precondition: [start, end) both lie within the same file as root.
  56 // TODO(adonovan): return (nil, false) in this case and remove precond.
  57 // Requires FileSet; see loader.tokenFileContainsPos.
  58 //
  59 // Postcondition: path is never nil; it always contains at least 'root'.
  60 //
  61 func PathEnclosingInterval(root *ast.File, start, end token.Pos) (path []ast.Node, exact bool) {
  62         // fmt.Printf("EnclosingInterval %d %d\n", start, end) // debugging
  63
  64         // Precondition: node.[Pos..End) and adjoining whitespace contain [start, end).
  65         var visit func(node ast.Node) bool
  66         visit = func(node ast.Node) bool {
  67                 path = append(path, node)
  68
  69                 nodePos := node.Pos()
  70                 nodeEnd := node.End()
  71
  72                 // fmt.Printf("visit(%T, %d, %d)\n", node, nodePos, nodeEnd) // debugging
  73
  74                 // Intersect [start, end) with interval of node.
  75                 if start < nodePos {
  76                         start = nodePos
  77                 }
  78                 if end > nodeEnd {
  79                         end = nodeEnd
  80                 }
  81
  82                 // Find sole child that contains [start, end).
  83                 children := childrenOf(node)
  84                 l := len(children)
  85                 for i, child := range children {
  86                         // [childPos, childEnd) is unaugmented interval of child.
  87                         childPos := child.Pos()
  88                         childEnd := child.End()
  89
  90                         // [augPos, augEnd) is whitespace-augmented interval of child.
  91                         augPos := childPos
  92                         augEnd := childEnd
  93                         if i > 0 {
  94                                 augPos = children[i-1].End() // start of preceding whitespace
  95                         }
  96                         if i < l-1 {
  97                                 nextChildPos := children[i+1].Pos()
  98                                 // Does [start, end) lie between child and next child?
  99                                 if start >= augEnd && end <= nextChildPos {
 100                                         return false // inexact match
 101                                 }
 102                                 augEnd = nextChildPos // end of following whitespace
 103                         }
 104
 105                         // fmt.Printf("\tchild %d: [%d..%d)\tcontains interval [%d..%d)?\n",
 106                         //      i, augPos, augEnd, start, end) // debugging
 107
 108                         // Does augmented child strictly contain [start, end)?
 109                         if augPos <= start && end <= augEnd {
 110                                 _, isToken := child.(tokenNode)
 111                                 return isToken || visit(child)
 112                         }
 113
 114                         // Does [start, end) overlap multiple children?
 115                         // i.e. left-augmented child contains start
 116                         // but LR-augmented child does not contain end.
 117                         if start < childEnd && end > augEnd {
 118                                 break
 119                         }
 120                 }
 121
 122                 // No single child contained [start, end),
 123                 // so node is the result.  Is it exact?
 124
 125                 // (It's tempting to put this condition before the
 126                 // child loop, but it gives the wrong result in the
 127                 // case where a node (e.g. ExprStmt) and its sole
 128                 // child have equal intervals.)
 129                 if start == nodePos && end == nodeEnd {
 130                         return true // exact match
 131                 }
 132
 133                 return false // inexact: overlaps multiple children
 134         }
 135
 136         if start > end {
 137                 start, end = end, start
 138         }
 139
 140         if start < root.End() && end > root.Pos() {
 141                 if start == end {
 142                         end = start + 1 // empty interval => interval of size 1
 143                 }
 144                 exact = visit(root)
 145
 146                 // Reverse the path:
 147                 for i, l := 0, len(path); i < l/2; i++ {
 148                         path[i], path[l-1-i] = path[l-1-i], path[i]
 149                 }
 150         } else {
 151                 // Selection lies within whitespace preceding the
 152                 // first (or following the last) declaration in the file.
 153                 // The result nonetheless always includes the ast.File.
 154                 path = append(path, root)
 155         }
 156
 157         return
 158 }
 159
 160 // tokenNode is a dummy implementation of ast.Node for a single token.
 161 // They are used transiently by PathEnclosingInterval but never escape
 162 // this package.
 163 //
 164 type tokenNode struct {
 165         pos token.Pos
 166         end token.Pos
 167 }
 168
 169 func (n tokenNode) Pos() token.Pos {
 170         return n.pos
 171 }
 172
 173 func (n tokenNode) End() token.Pos {
 174         return n.end
 175 }
 176
 177 func tok(pos token.Pos, len int) ast.Node {
 178         return tokenNode{pos, pos + token.Pos(len)}
 179 }
 180
 181 // childrenOf returns the direct non-nil children of ast.Node n.
 182 // It may include fake ast.Node implementations for bare tokens.
 183 // it is not safe to call (e.g.) ast.Walk on such nodes.
 184 //
 185 func childrenOf(n ast.Node) []ast.Node {
 186         var children []ast.Node
 187
 188         // First add nodes for all true subtrees.
 189         ast.Inspect(n, func(node ast.Node) bool {
 190                 if node == n { // push n
 191                         return true // recur
 192                 }
 193                 if node != nil { // push child
 194                         children = append(children, node)
 195                 }
 196                 return false // no recursion
 197         })
 198
 199         // Then add fake Nodes for bare tokens.
 200         switch n := n.(type) {
 201         case *ast.ArrayType:
 202                 children = append(children,
 203                         tok(n.Lbrack, len("[")),
 204                         tok(n.Elt.End(), len("]")))
 205
 206         case *ast.AssignStmt:
 207                 children = append(children,
 208                         tok(n.TokPos, len(n.Tok.String())))
 209
 210         case *ast.BasicLit:
 211                 children = append(children,
 212                         tok(n.ValuePos, len(n.Value)))
 213
 214         case *ast.BinaryExpr:
 215                 children = append(children, tok(n.OpPos, len(n.Op.String())))
 216
 217         case *ast.BlockStmt:
 218                 children = append(children,
 219                         tok(n.Lbrace, len("{")),
 220                         tok(n.Rbrace, len("}")))
 221
 222         case *ast.BranchStmt:
 223                 children = append(children,
 224                         tok(n.TokPos, len(n.Tok.String())))
 225
 226         case *ast.CallExpr:
 227                 children = append(children,
 228                         tok(n.Lparen, len("(")),
 229                         tok(n.Rparen, len(")")))
 230                 if n.Ellipsis != 0 {
 231                         children = append(children, tok(n.Ellipsis, len("...")))
 232                 }
 233
 234         case *ast.CaseClause:
 235                 if n.List == nil {
 236                         children = append(children,
 237                                 tok(n.Case, len("default")))
 238                 } else {
 239                         children = append(children,
 240                                 tok(n.Case, len("case")))
 241                 }
 242                 children = append(children, tok(n.Colon, len(":")))
 243
 244         case *ast.ChanType:
 245                 switch n.Dir {
 246                 case ast.RECV:
 247                         children = append(children, tok(n.Begin, len("<-chan")))
 248                 case ast.SEND:
 249                         children = append(children, tok(n.Begin, len("chan<-")))
 250                 case ast.RECV | ast.SEND:
 251                         children = append(children, tok(n.Begin, len("chan")))
 252                 }
 253
 254         case *ast.CommClause:
 255                 if n.Comm == nil {
 256                         children = append(children,
 257                                 tok(n.Case, len("default")))
 258                 } else {
 259                         children = append(children,
 260                                 tok(n.Case, len("case")))
 261                 }
 262                 children = append(children, tok(n.Colon, len(":")))
 263
 264         case *ast.Comment:
 265                 // nop
 266
 267         case *ast.CommentGroup:
 268                 // nop
 269
 270         case *ast.CompositeLit:
 271                 children = append(children,
 272                         tok(n.Lbrace, len("{")),
 273                         tok(n.Rbrace, len("{")))
 274
 275         case *ast.DeclStmt:
 276                 // nop
 277
 278         case *ast.DeferStmt:
 279                 children = append(children,
 280                         tok(n.Defer, len("defer")))
 281
 282         case *ast.Ellipsis:
 283                 children = append(children,
 284                         tok(n.Ellipsis, len("...")))
 285
 286         case *ast.EmptyStmt:
 287                 // nop
 288
 289         case *ast.ExprStmt:
 290                 // nop
 291
 292         case *ast.Field:
 293                 // TODO(adonovan): Field.{Doc,Comment,Tag}?
 294
 295         case *ast.FieldList:
 296                 children = append(children,
 297                         tok(n.Opening, len("(")),
 298                         tok(n.Closing, len(")")))
 299
 300         case *ast.File:
 301                 // TODO test: Doc
 302                 children = append(children,
 303                         tok(n.Package, len("package")))
 304
 305         case *ast.ForStmt:
 306                 children = append(children,
 307                         tok(n.For, len("for")))
 308
 309         case *ast.FuncDecl:
 310                 // TODO(adonovan): FuncDecl.Comment?
 311
 312                 // Uniquely, FuncDecl breaks the invariant that
 313                 // preorder traversal yields tokens in lexical order:
 314                 // in fact, FuncDecl.Recv precedes FuncDecl.Type.Func.
 315                 //
 316                 // As a workaround, we inline the case for FuncType
 317                 // here and order things correctly.
 318                 //
 319                 children = nil // discard ast.Walk(FuncDecl) info subtrees
 320                 children = append(children, tok(n.Type.Func, len("func")))
 321                 if n.Recv != nil {
 322                         children = append(children, n.Recv)
 323                 }
 324                 children = append(children, n.Name)
 325                 if n.Type.Params != nil {
 326                         children = append(children, n.Type.Params)
 327                 }
 328                 if n.Type.Results != nil {
 329                         children = append(children, n.Type.Results)
 330                 }
 331                 if n.Body != nil {
 332                         children = append(children, n.Body)
 333                 }
 334
 335         case *ast.FuncLit:
 336                 // nop
 337
 338         case *ast.FuncType:
 339                 if n.Func != 0 {
 340                         children = append(children,
 341                                 tok(n.Func, len("func")))
 342                 }
 343
 344         case *ast.GenDecl:
 345                 children = append(children,
 346                         tok(n.TokPos, len(n.Tok.String())))
 347                 if n.Lparen != 0 {
 348                         children = append(children,
 349                                 tok(n.Lparen, len("(")),
 350                                 tok(n.Rparen, len(")")))
 351                 }
 352
 353         case *ast.GoStmt:
 354                 children = append(children,
 355                         tok(n.Go, len("go")))
 356
 357         case *ast.Ident:
 358                 children = append(children,
 359                         tok(n.NamePos, len(n.Name)))
 360
 361         case *ast.IfStmt:
 362                 children = append(children,
 363                         tok(n.If, len("if")))
 364
 365         case *ast.ImportSpec:
 366                 // TODO(adonovan): ImportSpec.{Doc,EndPos}?
 367
 368         case *ast.IncDecStmt:
 369                 children = append(children,
 370                         tok(n.TokPos, len(n.Tok.String())))
 371
 372         case *ast.IndexExpr:
 373                 children = append(children,
 374                         tok(n.Lbrack, len("{")),
 375                         tok(n.Rbrack, len("}")))
 376
 377         case *ast.InterfaceType:
 378                 children = append(children,
 379                         tok(n.Interface, len("interface")))
 380
 381         case *ast.KeyValueExpr:
 382                 children = append(children,
 383                         tok(n.Colon, len(":")))
 384
 385         case *ast.LabeledStmt:
 386                 children = append(children,
 387                         tok(n.Colon, len(":")))
 388
 389         case *ast.MapType:
 390                 children = append(children,
 391                         tok(n.Map, len("map")))
 392
 393         case *ast.ParenExpr:
 394                 children = append(children,
 395                         tok(n.Lparen, len("(")),
 396                         tok(n.Rparen, len(")")))
 397
 398         case *ast.RangeStmt:
 399                 children = append(children,
 400                         tok(n.For, len("for")),
 401                         tok(n.TokPos, len(n.Tok.String())))
 402
 403         case *ast.ReturnStmt:
 404                 children = append(children,
 405                         tok(n.Return, len("return")))
 406
 407         case *ast.SelectStmt:
 408                 children = append(children,
 409                         tok(n.Select, len("select")))
 410
 411         case *ast.SelectorExpr:
 412                 // nop
 413
 414         case *ast.SendStmt:
 415                 children = append(children,
 416                         tok(n.Arrow, len("<-")))
 417
 418         case *ast.SliceExpr:
 419                 children = append(children,
 420                         tok(n.Lbrack, len("[")),
 421                         tok(n.Rbrack, len("]")))
 422
 423         case *ast.StarExpr:
 424                 children = append(children, tok(n.Star, len("*")))
 425
 426         case *ast.StructType:
 427                 children = append(children, tok(n.Struct, len("struct")))
 428
 429         case *ast.SwitchStmt:
 430                 children = append(children, tok(n.Switch, len("switch")))
 431
 432         case *ast.TypeAssertExpr:
 433                 children = append(children,
 434                         tok(n.Lparen-1, len(".")),
 435                         tok(n.Lparen, len("(")),
 436                         tok(n.Rparen, len(")")))
 437
 438         case *ast.TypeSpec:
 439                 // TODO(adonovan): TypeSpec.{Doc,Comment}?
 440
 441         case *ast.TypeSwitchStmt:
 442                 children = append(children, tok(n.Switch, len("switch")))
 443
 444         case *ast.UnaryExpr:
 445                 children = append(children, tok(n.OpPos, len(n.Op.String())))
 446
 447         case *ast.ValueSpec:
 448                 // TODO(adonovan): ValueSpec.{Doc,Comment}?
 449
 450         case *ast.BadDecl, *ast.BadExpr, *ast.BadStmt:
 451                 // nop
 452         }
 453
 454         // TODO(adonovan): opt: merge the logic of ast.Inspect() into
 455         // the switch above so we can make interleaved callbacks for
 456         // both Nodes and Tokens in the right order and avoid the need
 457         // to sort.
 458         sort.Sort(byPos(children))
 459
 460         return children
 461 }
 462
 463 type byPos []ast.Node
 464
 465 func (sl byPos) Len() int {
 466         return len(sl)
 467 }
 468 func (sl byPos) Less(i, j int) bool {
 469         return sl[i].Pos() < sl[j].Pos()
 470 }
 471 func (sl byPos) Swap(i, j int) {
 472         sl[i], sl[j] = sl[j], sl[i]
 473 }
 474
 475 // NodeDescription returns a description of the concrete type of n suitable
 476 // for a user interface.
 477 //
 478 // TODO(adonovan): in some cases (e.g. Field, FieldList, Ident,
 479 // StarExpr) we could be much more specific given the path to the AST
 480 // root.  Perhaps we should do that.
 481 //
 482 func NodeDescription(n ast.Node) string {
 483         switch n := n.(type) {
 484         case *ast.ArrayType:
 485                 return "array type"
 486         case *ast.AssignStmt:
 487                 return "assignment"
 488         case *ast.BadDecl:
 489                 return "bad declaration"
 490         case *ast.BadExpr:
 491                 return "bad expression"
 492         case *ast.BadStmt:
 493                 return "bad statement"
 494         case *ast.BasicLit:
 495                 return "basic literal"
 496         case *ast.BinaryExpr:
 497                 return fmt.Sprintf("binary %s operation", n.Op)
 498         case *ast.BlockStmt:
 499                 return "block"
 500         case *ast.BranchStmt:
 501                 switch n.Tok {
 502                 case token.BREAK:
 503                         return "break statement"
 504                 case token.CONTINUE:
 505                         return "continue statement"
 506                 case token.GOTO:
 507                         return "goto statement"
 508                 case token.FALLTHROUGH:
 509                         return "fall-through statement"
 510                 }
 511         case *ast.CallExpr:
 512                 if len(n.Args) == 1 && !n.Ellipsis.IsValid() {
 513                         return "function call (or conversion)"
 514                 }
 515                 return "function call"
 516         case *ast.CaseClause:
 517                 return "case clause"
 518         case *ast.ChanType:
 519                 return "channel type"
 520         case *ast.CommClause:
 521                 return "communication clause"
 522         case *ast.Comment:
 523                 return "comment"
 524         case *ast.CommentGroup:
 525                 return "comment group"
 526         case *ast.CompositeLit:
 527                 return "composite literal"
 528         case *ast.DeclStmt:
 529                 return NodeDescription(n.Decl) + " statement"
 530         case *ast.DeferStmt:
 531                 return "defer statement"
 532         case *ast.Ellipsis:
 533                 return "ellipsis"
 534         case *ast.EmptyStmt:
 535                 return "empty statement"
 536         case *ast.ExprStmt:
 537                 return "expression statement"
 538         case *ast.Field:
 539                 // Can be any of these:
 540                 // struct {x, y int}  -- struct field(s)
 541                 // struct {T}         -- anon struct field
 542                 // interface {I}      -- interface embedding
 543                 // interface {f()}    -- interface method
 544                 // func (A) func(B) C -- receiver, param(s), result(s)
 545                 return "field/method/parameter"
 546         case *ast.FieldList:
 547                 return "field/method/parameter list"
 548         case *ast.File:
 549                 return "source file"
 550         case *ast.ForStmt:
 551                 return "for loop"
 552         case *ast.FuncDecl:
 553                 return "function declaration"
 554         case *ast.FuncLit:
 555                 return "function literal"
 556         case *ast.FuncType:
 557                 return "function type"
 558         case *ast.GenDecl:
 559                 switch n.Tok {
 560                 case token.IMPORT:
 561                         return "import declaration"
 562                 case token.CONST:
 563                         return "constant declaration"
 564                 case token.TYPE:
 565                         return "type declaration"
 566                 case token.VAR:
 567                         return "variable declaration"
 568                 }
 569         case *ast.GoStmt:
 570                 return "go statement"
 571         case *ast.Ident:
 572                 return "identifier"
 573         case *ast.IfStmt:
 574                 return "if statement"
 575         case *ast.ImportSpec:
 576                 return "import specification"
 577         case *ast.IncDecStmt:
 578                 if n.Tok == token.INC {
 579                         return "increment statement"
 580                 }
 581                 return "decrement statement"
 582         case *ast.IndexExpr:
 583                 return "index expression"
 584         case *ast.InterfaceType:
 585                 return "interface type"
 586         case *ast.KeyValueExpr:
 587                 return "key/value association"
 588         case *ast.LabeledStmt:
 589                 return "statement label"
 590         case *ast.MapType:
 591                 return "map type"
 592         case *ast.Package:
 593                 return "package"
 594         case *ast.ParenExpr:
 595                 return "parenthesized " + NodeDescription(n.X)
 596         case *ast.RangeStmt:
 597                 return "range loop"
 598         case *ast.ReturnStmt:
 599                 return "return statement"
 600         case *ast.SelectStmt:
 601                 return "select statement"
 602         case *ast.SelectorExpr:
 603                 return "selector"
 604         case *ast.SendStmt:
 605                 return "channel send"
 606         case *ast.SliceExpr:
 607                 return "slice expression"
 608         case *ast.StarExpr:
 609                 return "*-operation" // load/store expr or pointer type
 610         case *ast.StructType:
 611                 return "struct type"
 612         case *ast.SwitchStmt:
 613                 return "switch statement"
 614         case *ast.TypeAssertExpr:
 615                 return "type assertion"
 616         case *ast.TypeSpec:
 617                 return "type specification"
 618         case *ast.TypeSwitchStmt:
 619                 return "type switch"
 620         case *ast.UnaryExpr:
 621                 return fmt.Sprintf("unary %s operation", n.Op)
 622         case *ast.ValueSpec:
 623                 return "value specification"
 624
 625         }
 626         panic(fmt.Sprintf("unexpected node type: %T", n))
 627 }