+++ /dev/null
-// Copyright 2016 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 cfg constructs a simple control-flow graph (CFG) of the
-// statements and expressions within a single function.
-//
-// Use cfg.New to construct the CFG for a function body.
-//
-// The blocks of the CFG contain all the function's non-control
-// statements. The CFG does not contain control statements such as If,
-// Switch, Select, and Branch, but does contain their subexpressions.
-// For example, this source code:
-//
-// if x := f(); x != nil {
-// T()
-// } else {
-// F()
-// }
-//
-// produces this CFG:
-//
-// 1: x := f()
-// x != nil
-// succs: 2, 3
-// 2: T()
-// succs: 4
-// 3: F()
-// succs: 4
-// 4:
-//
-// The CFG does contain Return statements; even implicit returns are
-// materialized (at the position of the function's closing brace).
-//
-// The CFG does not record conditions associated with conditional branch
-// edges, nor the short-circuit semantics of the && and || operators,
-// nor abnormal control flow caused by panic. If you need this
-// information, use golang.org/x/tools/go/ssa instead.
-//
-package cfg
-
-import (
- "bytes"
- "fmt"
- "go/ast"
- "go/format"
- "go/token"
-)
-
-// A CFG represents the control-flow graph of a single function.
-//
-// The entry point is Blocks[0]; there may be multiple return blocks.
-type CFG struct {
- Blocks []*Block // block[0] is entry; order otherwise undefined
-}
-
-// A Block represents a basic block: a list of statements and
-// expressions that are always evaluated sequentially.
-//
-// A block may have 0-2 successors: zero for a return block or a block
-// that calls a function such as panic that never returns; one for a
-// normal (jump) block; and two for a conditional (if) block.
-type Block struct {
- Nodes []ast.Node // statements, expressions, and ValueSpecs
- Succs []*Block // successor nodes in the graph
- Index int32 // index within CFG.Blocks
- Live bool // block is reachable from entry
-
- comment string // for debugging
- succs2 [2]*Block // underlying array for Succs
-}
-
-// New returns a new control-flow graph for the specified function body,
-// which must be non-nil.
-//
-// The CFG builder calls mayReturn to determine whether a given function
-// call may return. For example, calls to panic, os.Exit, and log.Fatal
-// do not return, so the builder can remove infeasible graph edges
-// following such calls. The builder calls mayReturn only for a
-// CallExpr beneath an ExprStmt.
-func New(body *ast.BlockStmt, mayReturn func(*ast.CallExpr) bool) *CFG {
- b := builder{
- mayReturn: mayReturn,
- cfg: new(CFG),
- }
- b.current = b.newBlock("entry")
- b.stmt(body)
-
- // Compute liveness (reachability from entry point), breadth-first.
- q := make([]*Block, 0, len(b.cfg.Blocks))
- q = append(q, b.cfg.Blocks[0]) // entry point
- for len(q) > 0 {
- b := q[len(q)-1]
- q = q[:len(q)-1]
-
- if !b.Live {
- b.Live = true
- q = append(q, b.Succs...)
- }
- }
-
- // Does control fall off the end of the function's body?
- // Make implicit return explicit.
- if b.current != nil && b.current.Live {
- b.add(&ast.ReturnStmt{
- Return: body.End() - 1,
- })
- }
-
- return b.cfg
-}
-
-func (b *Block) String() string {
- return fmt.Sprintf("block %d (%s)", b.Index, b.comment)
-}
-
-// Return returns the return statement at the end of this block if present, nil otherwise.
-func (b *Block) Return() (ret *ast.ReturnStmt) {
- if len(b.Nodes) > 0 {
- ret, _ = b.Nodes[len(b.Nodes)-1].(*ast.ReturnStmt)
- }
- return
-}
-
-// Format formats the control-flow graph for ease of debugging.
-func (g *CFG) Format(fset *token.FileSet) string {
- var buf bytes.Buffer
- for _, b := range g.Blocks {
- fmt.Fprintf(&buf, ".%d: # %s\n", b.Index, b.comment)
- for _, n := range b.Nodes {
- fmt.Fprintf(&buf, "\t%s\n", formatNode(fset, n))
- }
- if len(b.Succs) > 0 {
- fmt.Fprintf(&buf, "\tsuccs:")
- for _, succ := range b.Succs {
- fmt.Fprintf(&buf, " %d", succ.Index)
- }
- buf.WriteByte('\n')
- }
- buf.WriteByte('\n')
- }
- return buf.String()
-}
-
-func formatNode(fset *token.FileSet, n ast.Node) string {
- var buf bytes.Buffer
- format.Node(&buf, fset, n)
- // Indent secondary lines by a tab.
- return string(bytes.Replace(buf.Bytes(), []byte("\n"), []byte("\n\t"), -1))
-}
projects / dotfiles / .git / blobdiff