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.
7 // This file defines utilities for working with source positions.
16 // PathEnclosingInterval returns the node that encloses the source
17 // interval [start, end), and all its ancestors up to the AST root.
19 // The definition of "enclosing" used by this function considers
20 // additional whitespace abutting a node to be enclosed by it.
23 // z := x + y // add them
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
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").
36 // If start==end, the 1-char interval following start is used instead.
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].
44 // z := x + y // add them
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.
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.
59 // Postcondition: path is never nil; it always contains at least 'root'.
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
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)
72 // fmt.Printf("visit(%T, %d, %d)\n", node, nodePos, nodeEnd) // debugging
74 // Intersect [start, end) with interval of node.
82 // Find sole child that contains [start, end).
83 children := childrenOf(node)
85 for i, child := range children {
86 // [childPos, childEnd) is unaugmented interval of child.
87 childPos := child.Pos()
88 childEnd := child.End()
90 // [augPos, augEnd) is whitespace-augmented interval of child.
94 augPos = children[i-1].End() // start of preceding whitespace
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
102 augEnd = nextChildPos // end of following whitespace
105 // fmt.Printf("\tchild %d: [%d..%d)\tcontains interval [%d..%d)?\n",
106 // i, augPos, augEnd, start, end) // debugging
108 // Does augmented child strictly contain [start, end)?
109 if augPos <= start && end <= augEnd {
110 _, isToken := child.(tokenNode)
111 return isToken || visit(child)
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 {
122 // No single child contained [start, end),
123 // so node is the result. Is it exact?
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
133 return false // inexact: overlaps multiple children
137 start, end = end, start
140 if start < root.End() && end > root.Pos() {
142 end = start + 1 // empty interval => interval of size 1
147 for i, l := 0, len(path); i < l/2; i++ {
148 path[i], path[l-1-i] = path[l-1-i], path[i]
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)
160 // tokenNode is a dummy implementation of ast.Node for a single token.
161 // They are used transiently by PathEnclosingInterval but never escape
164 type tokenNode struct {
169 func (n tokenNode) Pos() token.Pos {
173 func (n tokenNode) End() token.Pos {
177 func tok(pos token.Pos, len int) ast.Node {
178 return tokenNode{pos, pos + token.Pos(len)}
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.
185 func childrenOf(n ast.Node) []ast.Node {
186 var children []ast.Node
188 // First add nodes for all true subtrees.
189 ast.Inspect(n, func(node ast.Node) bool {
190 if node == n { // push n
193 if node != nil { // push child
194 children = append(children, node)
196 return false // no recursion
199 // Then add fake Nodes for bare tokens.
200 switch n := n.(type) {
202 children = append(children,
203 tok(n.Lbrack, len("[")),
204 tok(n.Elt.End(), len("]")))
206 case *ast.AssignStmt:
207 children = append(children,
208 tok(n.TokPos, len(n.Tok.String())))
211 children = append(children,
212 tok(n.ValuePos, len(n.Value)))
214 case *ast.BinaryExpr:
215 children = append(children, tok(n.OpPos, len(n.Op.String())))
218 children = append(children,
219 tok(n.Lbrace, len("{")),
220 tok(n.Rbrace, len("}")))
222 case *ast.BranchStmt:
223 children = append(children,
224 tok(n.TokPos, len(n.Tok.String())))
227 children = append(children,
228 tok(n.Lparen, len("(")),
229 tok(n.Rparen, len(")")))
231 children = append(children, tok(n.Ellipsis, len("...")))
234 case *ast.CaseClause:
236 children = append(children,
237 tok(n.Case, len("default")))
239 children = append(children,
240 tok(n.Case, len("case")))
242 children = append(children, tok(n.Colon, len(":")))
247 children = append(children, tok(n.Begin, len("<-chan")))
249 children = append(children, tok(n.Begin, len("chan<-")))
250 case ast.RECV | ast.SEND:
251 children = append(children, tok(n.Begin, len("chan")))
254 case *ast.CommClause:
256 children = append(children,
257 tok(n.Case, len("default")))
259 children = append(children,
260 tok(n.Case, len("case")))
262 children = append(children, tok(n.Colon, len(":")))
267 case *ast.CommentGroup:
270 case *ast.CompositeLit:
271 children = append(children,
272 tok(n.Lbrace, len("{")),
273 tok(n.Rbrace, len("{")))
279 children = append(children,
280 tok(n.Defer, len("defer")))
283 children = append(children,
284 tok(n.Ellipsis, len("...")))
293 // TODO(adonovan): Field.{Doc,Comment,Tag}?
296 children = append(children,
297 tok(n.Opening, len("(")),
298 tok(n.Closing, len(")")))
302 children = append(children,
303 tok(n.Package, len("package")))
306 children = append(children,
307 tok(n.For, len("for")))
310 // TODO(adonovan): FuncDecl.Comment?
312 // Uniquely, FuncDecl breaks the invariant that
313 // preorder traversal yields tokens in lexical order:
314 // in fact, FuncDecl.Recv precedes FuncDecl.Type.Func.
316 // As a workaround, we inline the case for FuncType
317 // here and order things correctly.
319 children = nil // discard ast.Walk(FuncDecl) info subtrees
320 children = append(children, tok(n.Type.Func, len("func")))
322 children = append(children, n.Recv)
324 children = append(children, n.Name)
325 if n.Type.Params != nil {
326 children = append(children, n.Type.Params)
328 if n.Type.Results != nil {
329 children = append(children, n.Type.Results)
332 children = append(children, n.Body)
340 children = append(children,
341 tok(n.Func, len("func")))
345 children = append(children,
346 tok(n.TokPos, len(n.Tok.String())))
348 children = append(children,
349 tok(n.Lparen, len("(")),
350 tok(n.Rparen, len(")")))
354 children = append(children,
355 tok(n.Go, len("go")))
358 children = append(children,
359 tok(n.NamePos, len(n.Name)))
362 children = append(children,
363 tok(n.If, len("if")))
365 case *ast.ImportSpec:
366 // TODO(adonovan): ImportSpec.{Doc,EndPos}?
368 case *ast.IncDecStmt:
369 children = append(children,
370 tok(n.TokPos, len(n.Tok.String())))
373 children = append(children,
374 tok(n.Lbrack, len("{")),
375 tok(n.Rbrack, len("}")))
377 case *ast.InterfaceType:
378 children = append(children,
379 tok(n.Interface, len("interface")))
381 case *ast.KeyValueExpr:
382 children = append(children,
383 tok(n.Colon, len(":")))
385 case *ast.LabeledStmt:
386 children = append(children,
387 tok(n.Colon, len(":")))
390 children = append(children,
391 tok(n.Map, len("map")))
394 children = append(children,
395 tok(n.Lparen, len("(")),
396 tok(n.Rparen, len(")")))
399 children = append(children,
400 tok(n.For, len("for")),
401 tok(n.TokPos, len(n.Tok.String())))
403 case *ast.ReturnStmt:
404 children = append(children,
405 tok(n.Return, len("return")))
407 case *ast.SelectStmt:
408 children = append(children,
409 tok(n.Select, len("select")))
411 case *ast.SelectorExpr:
415 children = append(children,
416 tok(n.Arrow, len("<-")))
419 children = append(children,
420 tok(n.Lbrack, len("[")),
421 tok(n.Rbrack, len("]")))
424 children = append(children, tok(n.Star, len("*")))
426 case *ast.StructType:
427 children = append(children, tok(n.Struct, len("struct")))
429 case *ast.SwitchStmt:
430 children = append(children, tok(n.Switch, len("switch")))
432 case *ast.TypeAssertExpr:
433 children = append(children,
434 tok(n.Lparen-1, len(".")),
435 tok(n.Lparen, len("(")),
436 tok(n.Rparen, len(")")))
439 // TODO(adonovan): TypeSpec.{Doc,Comment}?
441 case *ast.TypeSwitchStmt:
442 children = append(children, tok(n.Switch, len("switch")))
445 children = append(children, tok(n.OpPos, len(n.Op.String())))
448 // TODO(adonovan): ValueSpec.{Doc,Comment}?
450 case *ast.BadDecl, *ast.BadExpr, *ast.BadStmt:
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
458 sort.Sort(byPos(children))
463 type byPos []ast.Node
465 func (sl byPos) Len() int {
468 func (sl byPos) Less(i, j int) bool {
469 return sl[i].Pos() < sl[j].Pos()
471 func (sl byPos) Swap(i, j int) {
472 sl[i], sl[j] = sl[j], sl[i]
475 // NodeDescription returns a description of the concrete type of n suitable
476 // for a user interface.
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.
482 func NodeDescription(n ast.Node) string {
483 switch n := n.(type) {
486 case *ast.AssignStmt:
489 return "bad declaration"
491 return "bad expression"
493 return "bad statement"
495 return "basic literal"
496 case *ast.BinaryExpr:
497 return fmt.Sprintf("binary %s operation", n.Op)
500 case *ast.BranchStmt:
503 return "break statement"
505 return "continue statement"
507 return "goto statement"
508 case token.FALLTHROUGH:
509 return "fall-through statement"
512 if len(n.Args) == 1 && !n.Ellipsis.IsValid() {
513 return "function call (or conversion)"
515 return "function call"
516 case *ast.CaseClause:
519 return "channel type"
520 case *ast.CommClause:
521 return "communication clause"
524 case *ast.CommentGroup:
525 return "comment group"
526 case *ast.CompositeLit:
527 return "composite literal"
529 return NodeDescription(n.Decl) + " statement"
531 return "defer statement"
535 return "empty statement"
537 return "expression statement"
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"
547 return "field/method/parameter list"
553 return "function declaration"
555 return "function literal"
557 return "function type"
561 return "import declaration"
563 return "constant declaration"
565 return "type declaration"
567 return "variable declaration"
570 return "go statement"
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"
581 return "decrement statement"
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"
595 return "parenthesized " + NodeDescription(n.X)
598 case *ast.ReturnStmt:
599 return "return statement"
600 case *ast.SelectStmt:
601 return "select statement"
602 case *ast.SelectorExpr:
605 return "channel send"
607 return "slice expression"
609 return "*-operation" // load/store expr or pointer type
610 case *ast.StructType:
612 case *ast.SwitchStmt:
613 return "switch statement"
614 case *ast.TypeAssertExpr:
615 return "type assertion"
617 return "type specification"
618 case *ast.TypeSwitchStmt:
621 return fmt.Sprintf("unary %s operation", n.Op)
623 return "value specification"
626 panic(fmt.Sprintf("unexpected node type: %T", n))