+++ /dev/null
-// Copyright 2013 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package astutil
-
-// This file defines utilities for working with source positions.
-
-import (
- "fmt"
- "go/ast"
- "go/token"
- "sort"
-)
-
-// PathEnclosingInterval returns the node that encloses the source
-// interval [start, end), and all its ancestors up to the AST root.
-//
-// The definition of "enclosing" used by this function considers
-// additional whitespace abutting a node to be enclosed by it.
-// In this example:
-//
-// z := x + y // add them
-// <-A->
-// <----B----->
-//
-// the ast.BinaryExpr(+) node is considered to enclose interval B
-// even though its [Pos()..End()) is actually only interval A.
-// This behaviour makes user interfaces more tolerant of imperfect
-// input.
-//
-// This function treats tokens as nodes, though they are not included
-// in the result. e.g. PathEnclosingInterval("+") returns the
-// enclosing ast.BinaryExpr("x + y").
-//
-// If start==end, the 1-char interval following start is used instead.
-//
-// The 'exact' result is true if the interval contains only path[0]
-// and perhaps some adjacent whitespace. It is false if the interval
-// overlaps multiple children of path[0], or if it contains only
-// interior whitespace of path[0].
-// In this example:
-//
-// z := x + y // add them
-// <--C--> <---E-->
-// ^
-// D
-//
-// intervals C, D and E are inexact. C is contained by the
-// z-assignment statement, because it spans three of its children (:=,
-// x, +). So too is the 1-char interval D, because it contains only
-// interior whitespace of the assignment. E is considered interior
-// whitespace of the BlockStmt containing the assignment.
-//
-// Precondition: [start, end) both lie within the same file as root.
-// TODO(adonovan): return (nil, false) in this case and remove precond.
-// Requires FileSet; see loader.tokenFileContainsPos.
-//
-// Postcondition: path is never nil; it always contains at least 'root'.
-//
-func PathEnclosingInterval(root *ast.File, start, end token.Pos) (path []ast.Node, exact bool) {
- // fmt.Printf("EnclosingInterval %d %d\n", start, end) // debugging
-
- // Precondition: node.[Pos..End) and adjoining whitespace contain [start, end).
- var visit func(node ast.Node) bool
- visit = func(node ast.Node) bool {
- path = append(path, node)
-
- nodePos := node.Pos()
- nodeEnd := node.End()
-
- // fmt.Printf("visit(%T, %d, %d)\n", node, nodePos, nodeEnd) // debugging
-
- // Intersect [start, end) with interval of node.
- if start < nodePos {
- start = nodePos
- }
- if end > nodeEnd {
- end = nodeEnd
- }
-
- // Find sole child that contains [start, end).
- children := childrenOf(node)
- l := len(children)
- for i, child := range children {
- // [childPos, childEnd) is unaugmented interval of child.
- childPos := child.Pos()
- childEnd := child.End()
-
- // [augPos, augEnd) is whitespace-augmented interval of child.
- augPos := childPos
- augEnd := childEnd
- if i > 0 {
- augPos = children[i-1].End() // start of preceding whitespace
- }
- if i < l-1 {
- nextChildPos := children[i+1].Pos()
- // Does [start, end) lie between child and next child?
- if start >= augEnd && end <= nextChildPos {
- return false // inexact match
- }
- augEnd = nextChildPos // end of following whitespace
- }
-
- // fmt.Printf("\tchild %d: [%d..%d)\tcontains interval [%d..%d)?\n",
- // i, augPos, augEnd, start, end) // debugging
-
- // Does augmented child strictly contain [start, end)?
- if augPos <= start && end <= augEnd {
- _, isToken := child.(tokenNode)
- return isToken || visit(child)
- }
-
- // Does [start, end) overlap multiple children?
- // i.e. left-augmented child contains start
- // but LR-augmented child does not contain end.
- if start < childEnd && end > augEnd {
- break
- }
- }
-
- // No single child contained [start, end),
- // so node is the result. Is it exact?
-
- // (It's tempting to put this condition before the
- // child loop, but it gives the wrong result in the
- // case where a node (e.g. ExprStmt) and its sole
- // child have equal intervals.)
- if start == nodePos && end == nodeEnd {
- return true // exact match
- }
-
- return false // inexact: overlaps multiple children
- }
-
- if start > end {
- start, end = end, start
- }
-
- if start < root.End() && end > root.Pos() {
- if start == end {
- end = start + 1 // empty interval => interval of size 1
- }
- exact = visit(root)
-
- // Reverse the path:
- for i, l := 0, len(path); i < l/2; i++ {
- path[i], path[l-1-i] = path[l-1-i], path[i]
- }
- } else {
- // Selection lies within whitespace preceding the
- // first (or following the last) declaration in the file.
- // The result nonetheless always includes the ast.File.
- path = append(path, root)
- }
-
- return
-}
-
-// tokenNode is a dummy implementation of ast.Node for a single token.
-// They are used transiently by PathEnclosingInterval but never escape
-// this package.
-//
-type tokenNode struct {
- pos token.Pos
- end token.Pos
-}
-
-func (n tokenNode) Pos() token.Pos {
- return n.pos
-}
-
-func (n tokenNode) End() token.Pos {
- return n.end
-}
-
-func tok(pos token.Pos, len int) ast.Node {
- return tokenNode{pos, pos + token.Pos(len)}
-}
-
-// childrenOf returns the direct non-nil children of ast.Node n.
-// It may include fake ast.Node implementations for bare tokens.
-// it is not safe to call (e.g.) ast.Walk on such nodes.
-//
-func childrenOf(n ast.Node) []ast.Node {
- var children []ast.Node
-
- // First add nodes for all true subtrees.
- ast.Inspect(n, func(node ast.Node) bool {
- if node == n { // push n
- return true // recur
- }
- if node != nil { // push child
- children = append(children, node)
- }
- return false // no recursion
- })
-
- // Then add fake Nodes for bare tokens.
- switch n := n.(type) {
- case *ast.ArrayType:
- children = append(children,
- tok(n.Lbrack, len("[")),
- tok(n.Elt.End(), len("]")))
-
- case *ast.AssignStmt:
- children = append(children,
- tok(n.TokPos, len(n.Tok.String())))
-
- case *ast.BasicLit:
- children = append(children,
- tok(n.ValuePos, len(n.Value)))
-
- case *ast.BinaryExpr:
- children = append(children, tok(n.OpPos, len(n.Op.String())))
-
- case *ast.BlockStmt:
- children = append(children,
- tok(n.Lbrace, len("{")),
- tok(n.Rbrace, len("}")))
-
- case *ast.BranchStmt:
- children = append(children,
- tok(n.TokPos, len(n.Tok.String())))
-
- case *ast.CallExpr:
- children = append(children,
- tok(n.Lparen, len("(")),
- tok(n.Rparen, len(")")))
- if n.Ellipsis != 0 {
- children = append(children, tok(n.Ellipsis, len("...")))
- }
-
- case *ast.CaseClause:
- if n.List == nil {
- children = append(children,
- tok(n.Case, len("default")))
- } else {
- children = append(children,
- tok(n.Case, len("case")))
- }
- children = append(children, tok(n.Colon, len(":")))
-
- case *ast.ChanType:
- switch n.Dir {
- case ast.RECV:
- children = append(children, tok(n.Begin, len("<-chan")))
- case ast.SEND:
- children = append(children, tok(n.Begin, len("chan<-")))
- case ast.RECV | ast.SEND:
- children = append(children, tok(n.Begin, len("chan")))
- }
-
- case *ast.CommClause:
- if n.Comm == nil {
- children = append(children,
- tok(n.Case, len("default")))
- } else {
- children = append(children,
- tok(n.Case, len("case")))
- }
- children = append(children, tok(n.Colon, len(":")))
-
- case *ast.Comment:
- // nop
-
- case *ast.CommentGroup:
- // nop
-
- case *ast.CompositeLit:
- children = append(children,
- tok(n.Lbrace, len("{")),
- tok(n.Rbrace, len("{")))
-
- case *ast.DeclStmt:
- // nop
-
- case *ast.DeferStmt:
- children = append(children,
- tok(n.Defer, len("defer")))
-
- case *ast.Ellipsis:
- children = append(children,
- tok(n.Ellipsis, len("...")))
-
- case *ast.EmptyStmt:
- // nop
-
- case *ast.ExprStmt:
- // nop
-
- case *ast.Field:
- // TODO(adonovan): Field.{Doc,Comment,Tag}?
-
- case *ast.FieldList:
- children = append(children,
- tok(n.Opening, len("(")),
- tok(n.Closing, len(")")))
-
- case *ast.File:
- // TODO test: Doc
- children = append(children,
- tok(n.Package, len("package")))
-
- case *ast.ForStmt:
- children = append(children,
- tok(n.For, len("for")))
-
- case *ast.FuncDecl:
- // TODO(adonovan): FuncDecl.Comment?
-
- // Uniquely, FuncDecl breaks the invariant that
- // preorder traversal yields tokens in lexical order:
- // in fact, FuncDecl.Recv precedes FuncDecl.Type.Func.
- //
- // As a workaround, we inline the case for FuncType
- // here and order things correctly.
- //
- children = nil // discard ast.Walk(FuncDecl) info subtrees
- children = append(children, tok(n.Type.Func, len("func")))
- if n.Recv != nil {
- children = append(children, n.Recv)
- }
- children = append(children, n.Name)
- if n.Type.Params != nil {
- children = append(children, n.Type.Params)
- }
- if n.Type.Results != nil {
- children = append(children, n.Type.Results)
- }
- if n.Body != nil {
- children = append(children, n.Body)
- }
-
- case *ast.FuncLit:
- // nop
-
- case *ast.FuncType:
- if n.Func != 0 {
- children = append(children,
- tok(n.Func, len("func")))
- }
-
- case *ast.GenDecl:
- children = append(children,
- tok(n.TokPos, len(n.Tok.String())))
- if n.Lparen != 0 {
- children = append(children,
- tok(n.Lparen, len("(")),
- tok(n.Rparen, len(")")))
- }
-
- case *ast.GoStmt:
- children = append(children,
- tok(n.Go, len("go")))
-
- case *ast.Ident:
- children = append(children,
- tok(n.NamePos, len(n.Name)))
-
- case *ast.IfStmt:
- children = append(children,
- tok(n.If, len("if")))
-
- case *ast.ImportSpec:
- // TODO(adonovan): ImportSpec.{Doc,EndPos}?
-
- case *ast.IncDecStmt:
- children = append(children,
- tok(n.TokPos, len(n.Tok.String())))
-
- case *ast.IndexExpr:
- children = append(children,
- tok(n.Lbrack, len("{")),
- tok(n.Rbrack, len("}")))
-
- case *ast.InterfaceType:
- children = append(children,
- tok(n.Interface, len("interface")))
-
- case *ast.KeyValueExpr:
- children = append(children,
- tok(n.Colon, len(":")))
-
- case *ast.LabeledStmt:
- children = append(children,
- tok(n.Colon, len(":")))
-
- case *ast.MapType:
- children = append(children,
- tok(n.Map, len("map")))
-
- case *ast.ParenExpr:
- children = append(children,
- tok(n.Lparen, len("(")),
- tok(n.Rparen, len(")")))
-
- case *ast.RangeStmt:
- children = append(children,
- tok(n.For, len("for")),
- tok(n.TokPos, len(n.Tok.String())))
-
- case *ast.ReturnStmt:
- children = append(children,
- tok(n.Return, len("return")))
-
- case *ast.SelectStmt:
- children = append(children,
- tok(n.Select, len("select")))
-
- case *ast.SelectorExpr:
- // nop
-
- case *ast.SendStmt:
- children = append(children,
- tok(n.Arrow, len("<-")))
-
- case *ast.SliceExpr:
- children = append(children,
- tok(n.Lbrack, len("[")),
- tok(n.Rbrack, len("]")))
-
- case *ast.StarExpr:
- children = append(children, tok(n.Star, len("*")))
-
- case *ast.StructType:
- children = append(children, tok(n.Struct, len("struct")))
-
- case *ast.SwitchStmt:
- children = append(children, tok(n.Switch, len("switch")))
-
- case *ast.TypeAssertExpr:
- children = append(children,
- tok(n.Lparen-1, len(".")),
- tok(n.Lparen, len("(")),
- tok(n.Rparen, len(")")))
-
- case *ast.TypeSpec:
- // TODO(adonovan): TypeSpec.{Doc,Comment}?
-
- case *ast.TypeSwitchStmt:
- children = append(children, tok(n.Switch, len("switch")))
-
- case *ast.UnaryExpr:
- children = append(children, tok(n.OpPos, len(n.Op.String())))
-
- case *ast.ValueSpec:
- // TODO(adonovan): ValueSpec.{Doc,Comment}?
-
- case *ast.BadDecl, *ast.BadExpr, *ast.BadStmt:
- // nop
- }
-
- // TODO(adonovan): opt: merge the logic of ast.Inspect() into
- // the switch above so we can make interleaved callbacks for
- // both Nodes and Tokens in the right order and avoid the need
- // to sort.
- sort.Sort(byPos(children))
-
- return children
-}
-
-type byPos []ast.Node
-
-func (sl byPos) Len() int {
- return len(sl)
-}
-func (sl byPos) Less(i, j int) bool {
- return sl[i].Pos() < sl[j].Pos()
-}
-func (sl byPos) Swap(i, j int) {
- sl[i], sl[j] = sl[j], sl[i]
-}
-
-// NodeDescription returns a description of the concrete type of n suitable
-// for a user interface.
-//
-// TODO(adonovan): in some cases (e.g. Field, FieldList, Ident,
-// StarExpr) we could be much more specific given the path to the AST
-// root. Perhaps we should do that.
-//
-func NodeDescription(n ast.Node) string {
- switch n := n.(type) {
- case *ast.ArrayType:
- return "array type"
- case *ast.AssignStmt:
- return "assignment"
- case *ast.BadDecl:
- return "bad declaration"
- case *ast.BadExpr:
- return "bad expression"
- case *ast.BadStmt:
- return "bad statement"
- case *ast.BasicLit:
- return "basic literal"
- case *ast.BinaryExpr:
- return fmt.Sprintf("binary %s operation", n.Op)
- case *ast.BlockStmt:
- return "block"
- case *ast.BranchStmt:
- switch n.Tok {
- case token.BREAK:
- return "break statement"
- case token.CONTINUE:
- return "continue statement"
- case token.GOTO:
- return "goto statement"
- case token.FALLTHROUGH:
- return "fall-through statement"
- }
- case *ast.CallExpr:
- if len(n.Args) == 1 && !n.Ellipsis.IsValid() {
- return "function call (or conversion)"
- }
- return "function call"
- case *ast.CaseClause:
- return "case clause"
- case *ast.ChanType:
- return "channel type"
- case *ast.CommClause:
- return "communication clause"
- case *ast.Comment:
- return "comment"
- case *ast.CommentGroup:
- return "comment group"
- case *ast.CompositeLit:
- return "composite literal"
- case *ast.DeclStmt:
- return NodeDescription(n.Decl) + " statement"
- case *ast.DeferStmt:
- return "defer statement"
- case *ast.Ellipsis:
- return "ellipsis"
- case *ast.EmptyStmt:
- return "empty statement"
- case *ast.ExprStmt:
- return "expression statement"
- case *ast.Field:
- // Can be any of these:
- // struct {x, y int} -- struct field(s)
- // struct {T} -- anon struct field
- // interface {I} -- interface embedding
- // interface {f()} -- interface method
- // func (A) func(B) C -- receiver, param(s), result(s)
- return "field/method/parameter"
- case *ast.FieldList:
- return "field/method/parameter list"
- case *ast.File:
- return "source file"
- case *ast.ForStmt:
- return "for loop"
- case *ast.FuncDecl:
- return "function declaration"
- case *ast.FuncLit:
- return "function literal"
- case *ast.FuncType:
- return "function type"
- case *ast.GenDecl:
- switch n.Tok {
- case token.IMPORT:
- return "import declaration"
- case token.CONST:
- return "constant declaration"
- case token.TYPE:
- return "type declaration"
- case token.VAR:
- return "variable declaration"
- }
- case *ast.GoStmt:
- return "go statement"
- case *ast.Ident:
- return "identifier"
- case *ast.IfStmt:
- return "if statement"
- case *ast.ImportSpec:
- return "import specification"
- case *ast.IncDecStmt:
- if n.Tok == token.INC {
- return "increment statement"
- }
- return "decrement statement"
- case *ast.IndexExpr:
- return "index expression"
- case *ast.InterfaceType:
- return "interface type"
- case *ast.KeyValueExpr:
- return "key/value association"
- case *ast.LabeledStmt:
- return "statement label"
- case *ast.MapType:
- return "map type"
- case *ast.Package:
- return "package"
- case *ast.ParenExpr:
- return "parenthesized " + NodeDescription(n.X)
- case *ast.RangeStmt:
- return "range loop"
- case *ast.ReturnStmt:
- return "return statement"
- case *ast.SelectStmt:
- return "select statement"
- case *ast.SelectorExpr:
- return "selector"
- case *ast.SendStmt:
- return "channel send"
- case *ast.SliceExpr:
- return "slice expression"
- case *ast.StarExpr:
- return "*-operation" // load/store expr or pointer type
- case *ast.StructType:
- return "struct type"
- case *ast.SwitchStmt:
- return "switch statement"
- case *ast.TypeAssertExpr:
- return "type assertion"
- case *ast.TypeSpec:
- return "type specification"
- case *ast.TypeSwitchStmt:
- return "type switch"
- case *ast.UnaryExpr:
- return fmt.Sprintf("unary %s operation", n.Op)
- case *ast.ValueSpec:
- return "value specification"
-
- }
- panic(fmt.Sprintf("unexpected node type: %T", n))
-}
projects / dotfiles / .git / blobdiff