Source file src/cmd/vendor/golang.org/x/tools/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	}
   628	

View as plain text