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