cfg.go

     1  // Copyright 2016 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 cfg constructs a simple control-flow graph (CFG) of the
     6  // statements and expressions within a single function.
     7  //
     8  // Use cfg.New to construct the CFG for a function body.
     9  //
    10  // The blocks of the CFG contain all the function's non-control
    11  // statements.  The CFG does not contain control statements such as If,
    12  // Switch, Select, and Branch, but does contain their subexpressions.
    13  // For example, this source code:
    14  //
    15  //	if x := f(); x != nil {
    16  //		T()
    17  //	} else {
    18  //		F()
    19  //	}
    20  //
    21  // produces this CFG:
    22  //
    23  //    1:  x := f()
    24  //        x != nil
    25  //        succs: 2, 3
    26  //    2:  T()
    27  //        succs: 4
    28  //    3:  F()
    29  //        succs: 4
    30  //    4:
    31  //
    32  // The CFG does contain Return statements; even implicit returns are
    33  // materialized (at the position of the function's closing brace).
    34  //
    35  // The CFG does not record conditions associated with conditional branch
    36  // edges, nor the short-circuit semantics of the && and || operators,
    37  // nor abnormal control flow caused by panic.  If you need this
    38  // information, use golang.org/x/tools/go/ssa instead.
    39  //
    40  package cfg
    41  
    42  import (
    43  	"bytes"
    44  	"fmt"
    45  	"go/ast"
    46  	"go/format"
    47  	"go/token"
    48  )
    49  
    50  // A CFG represents the control-flow graph of a single function.
    51  //
    52  // The entry point is Blocks[0]; there may be multiple return blocks.
    53  type CFG struct {
    54  	Blocks []*Block // block[0] is entry; order otherwise undefined
    55  }
    56  
    57  // A Block represents a basic block: a list of statements and
    58  // expressions that are always evaluated sequentially.
    59  //
    60  // A block may have 0-2 successors: zero for a return block or a block
    61  // that calls a function such as panic that never returns; one for a
    62  // normal (jump) block; and two for a conditional (if) block.
    63  type Block struct {
    64  	Nodes []ast.Node // statements, expressions, and ValueSpecs
    65  	Succs []*Block   // successor nodes in the graph
    66  	Index int32      // index within CFG.Blocks
    67  	Live  bool       // block is reachable from entry
    68  
    69  	comment string    // for debugging
    70  	succs2  [2]*Block // underlying array for Succs
    71  }
    72  
    73  // New returns a new control-flow graph for the specified function body,
    74  // which must be non-nil.
    75  //
    76  // The CFG builder calls mayReturn to determine whether a given function
    77  // call may return.  For example, calls to panic, os.Exit, and log.Fatal
    78  // do not return, so the builder can remove infeasible graph edges
    79  // following such calls.  The builder calls mayReturn only for a
    80  // CallExpr beneath an ExprStmt.
    81  func New(body *ast.BlockStmt, mayReturn func(*ast.CallExpr) bool) *CFG {
    82  	b := builder{
    83  		mayReturn: mayReturn,
    84  		cfg:       new(CFG),
    85  	}
    86  	b.current = b.newBlock("entry")
    87  	b.stmt(body)
    88  
    89  	// Compute liveness (reachability from entry point), breadth-first.
    90  	q := make([]*Block, 0, len(b.cfg.Blocks))
    91  	q = append(q, b.cfg.Blocks[0]) // entry point
    92  	for len(q) > 0 {
    93  		b := q[len(q)-1]
    94  		q = q[:len(q)-1]
    95  
    96  		if !b.Live {
    97  			b.Live = true
    98  			q = append(q, b.Succs...)
    99  		}
   100  	}
   101  
   102  	// Does control fall off the end of the function's body?
   103  	// Make implicit return explicit.
   104  	if b.current != nil && b.current.Live {
   105  		b.add(&ast.ReturnStmt{
   106  			Return: body.End() - 1,
   107  		})
   108  	}
   109  
   110  	return b.cfg
   111  }
   112  
   113  func (b *Block) String() string {
   114  	return fmt.Sprintf("block %d (%s)", b.Index, b.comment)
   115  }
   116  
   117  // Return returns the return statement at the end of this block if present, nil otherwise.
   118  func (b *Block) Return() (ret *ast.ReturnStmt) {
   119  	if len(b.Nodes) > 0 {
   120  		ret, _ = b.Nodes[len(b.Nodes)-1].(*ast.ReturnStmt)
   121  	}
   122  	return
   123  }
   124  
   125  // Format formats the control-flow graph for ease of debugging.
   126  func (g *CFG) Format(fset *token.FileSet) string {
   127  	var buf bytes.Buffer
   128  	for _, b := range g.Blocks {
   129  		fmt.Fprintf(&buf, ".%d: # %s\n", b.Index, b.comment)
   130  		for _, n := range b.Nodes {
   131  			fmt.Fprintf(&buf, "\t%s\n", formatNode(fset, n))
   132  		}
   133  		if len(b.Succs) > 0 {
   134  			fmt.Fprintf(&buf, "\tsuccs:")
   135  			for _, succ := range b.Succs {
   136  				fmt.Fprintf(&buf, " %d", succ.Index)
   137  			}
   138  			buf.WriteByte('\n')
   139  		}
   140  		buf.WriteByte('\n')
   141  	}
   142  	return buf.String()
   143  }
   144  
   145  func formatNode(fset *token.FileSet, n ast.Node) string {
   146  	var buf bytes.Buffer
   147  	format.Node(&buf, fset, n)
   148  	// Indent secondary lines by a tab.
   149  	return string(bytes.Replace(buf.Bytes(), []byte("\n"), []byte("\n\t"), -1))
   150  }
   151
View as plain text