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  // also, each block records the control statement (Block.Stmt) that
    14  // gave rise to it and its relationship (Block.Kind) to that statement.
    15  //
    16  // For example, this source code:
    17  //
    18  //	if x := f(); x != nil {
    19  //		T()
    20  //	} else {
    21  //		F()
    22  //	}
    23  //
    24  // produces this CFG:
    25  //
    26  //	1:  x := f()		Body
    27  //	    x != nil
    28  //	    succs: 2, 3
    29  //	2:  T()			IfThen
    30  //	    succs: 4
    31  //	3:  F()			IfElse
    32  //	    succs: 4
    33  //	4:			IfDone
    34  //
    35  // The CFG does contain Return statements; even implicit returns are
    36  // materialized (at the position of the function's closing brace).
    37  //
    38  // The CFG does not record conditions associated with conditional branch
    39  // edges, nor the short-circuit semantics of the && and || operators,
    40  // nor abnormal control flow caused by panic.  If you need this
    41  // information, use golang.org/x/tools/go/ssa instead.
    42  package cfg
    43  
    44  import (
    45  	"bytes"
    46  	"fmt"
    47  	"go/ast"
    48  	"go/format"
    49  	"go/token"
    50  )
    51  
    52  // A CFG represents the control-flow graph of a single function.
    53  //
    54  // The entry point is Blocks[0]; there may be multiple return blocks.
    55  type CFG struct {
    56  	fset   *token.FileSet
    57  	Blocks []*Block // block[0] is entry; order otherwise undefined
    58  }
    59  
    60  // A Block represents a basic block: a list of statements and
    61  // expressions that are always evaluated sequentially.
    62  //
    63  // A block may have 0-2 successors: zero for a return block or a block
    64  // that calls a function such as panic that never returns; one for a
    65  // normal (jump) block; and two for a conditional (if) block.
    66  type Block struct {
    67  	Nodes []ast.Node // statements, expressions, and ValueSpecs
    68  	Succs []*Block   // successor nodes in the graph
    69  	Index int32      // index within CFG.Blocks
    70  	Live  bool       // block is reachable from entry
    71  	Kind  BlockKind  // block kind
    72  	Stmt  ast.Stmt   // statement that gave rise to this block (see BlockKind for details)
    73  
    74  	succs2 [2]*Block // underlying array for Succs
    75  }
    76  
    77  // A BlockKind identifies the purpose of a block.
    78  // It also determines the possible types of its Stmt field.
    79  type BlockKind uint8
    80  
    81  const (
    82  	KindInvalid BlockKind = iota // Stmt=nil
    83  
    84  	KindUnreachable     // unreachable block after {Branch,Return}Stmt / no-return call ExprStmt
    85  	KindBody            // function body BlockStmt
    86  	KindForBody         // body of ForStmt
    87  	KindForDone         // block after ForStmt
    88  	KindForLoop         // head of ForStmt
    89  	KindForPost         // post condition of ForStmt
    90  	KindIfDone          // block after IfStmt
    91  	KindIfElse          // else block of IfStmt
    92  	KindIfThen          // then block of IfStmt
    93  	KindLabel           // labeled block of BranchStmt (Stmt may be nil for dangling label)
    94  	KindRangeBody       // body of RangeStmt
    95  	KindRangeDone       // block after RangeStmt
    96  	KindRangeLoop       // head of RangeStmt
    97  	KindSelectCaseBody  // body of SelectStmt
    98  	KindSelectDone      // block after SelectStmt
    99  	KindSelectAfterCase // block after a CommClause
   100  	KindSwitchCaseBody  // body of CaseClause
   101  	KindSwitchDone      // block after {Type.}SwitchStmt
   102  	KindSwitchNextCase  // secondary expression of a multi-expression CaseClause
   103  )
   104  
   105  func (kind BlockKind) String() string {
   106  	return [...]string{
   107  		KindInvalid:         "Invalid",
   108  		KindUnreachable:     "Unreachable",
   109  		KindBody:            "Body",
   110  		KindForBody:         "ForBody",
   111  		KindForDone:         "ForDone",
   112  		KindForLoop:         "ForLoop",
   113  		KindForPost:         "ForPost",
   114  		KindIfDone:          "IfDone",
   115  		KindIfElse:          "IfElse",
   116  		KindIfThen:          "IfThen",
   117  		KindLabel:           "Label",
   118  		KindRangeBody:       "RangeBody",
   119  		KindRangeDone:       "RangeDone",
   120  		KindRangeLoop:       "RangeLoop",
   121  		KindSelectCaseBody:  "SelectCaseBody",
   122  		KindSelectDone:      "SelectDone",
   123  		KindSelectAfterCase: "SelectAfterCase",
   124  		KindSwitchCaseBody:  "SwitchCaseBody",
   125  		KindSwitchDone:      "SwitchDone",
   126  		KindSwitchNextCase:  "SwitchNextCase",
   127  	}[kind]
   128  }
   129  
   130  // New returns a new control-flow graph for the specified function body,
   131  // which must be non-nil.
   132  //
   133  // The CFG builder calls mayReturn to determine whether a given function
   134  // call may return.  For example, calls to panic, os.Exit, and log.Fatal
   135  // do not return, so the builder can remove infeasible graph edges
   136  // following such calls.  The builder calls mayReturn only for a
   137  // CallExpr beneath an ExprStmt.
   138  func New(body *ast.BlockStmt, mayReturn func(*ast.CallExpr) bool) *CFG {
   139  	b := builder{
   140  		mayReturn: mayReturn,
   141  		cfg:       new(CFG),
   142  	}
   143  	b.current = b.newBlock(KindBody, body)
   144  	b.stmt(body)
   145  
   146  	// Compute liveness (reachability from entry point), breadth-first.
   147  	q := make([]*Block, 0, len(b.cfg.Blocks))
   148  	q = append(q, b.cfg.Blocks[0]) // entry point
   149  	for len(q) > 0 {
   150  		b := q[len(q)-1]
   151  		q = q[:len(q)-1]
   152  
   153  		if !b.Live {
   154  			b.Live = true
   155  			q = append(q, b.Succs...)
   156  		}
   157  	}
   158  
   159  	// Does control fall off the end of the function's body?
   160  	// Make implicit return explicit.
   161  	if b.current != nil && b.current.Live {
   162  		b.add(&ast.ReturnStmt{
   163  			Return: body.End() - 1,
   164  		})
   165  	}
   166  
   167  	return b.cfg
   168  }
   169  
   170  func (b *Block) String() string {
   171  	return fmt.Sprintf("block %d (%s)", b.Index, b.comment(nil))
   172  }
   173  
   174  func (b *Block) comment(fset *token.FileSet) string {
   175  	s := b.Kind.String()
   176  	if fset != nil && b.Stmt != nil {
   177  		s = fmt.Sprintf("%s@L%d", s, fset.Position(b.Stmt.Pos()).Line)
   178  	}
   179  	return s
   180  }
   181  
   182  // Return returns the return statement at the end of this block if present, nil
   183  // otherwise.
   184  //
   185  // When control falls off the end of the function, the ReturnStmt is synthetic
   186  // and its [ast.Node.End] position may be beyond the end of the file.
   187  func (b *Block) Return() (ret *ast.ReturnStmt) {
   188  	if len(b.Nodes) > 0 {
   189  		ret, _ = b.Nodes[len(b.Nodes)-1].(*ast.ReturnStmt)
   190  	}
   191  	return
   192  }
   193  
   194  // Format formats the control-flow graph for ease of debugging.
   195  func (g *CFG) Format(fset *token.FileSet) string {
   196  	var buf bytes.Buffer
   197  	for _, b := range g.Blocks {
   198  		fmt.Fprintf(&buf, ".%d: # %s\n", b.Index, b.comment(fset))
   199  		for _, n := range b.Nodes {
   200  			fmt.Fprintf(&buf, "\t%s\n", formatNode(fset, n))
   201  		}
   202  		if len(b.Succs) > 0 {
   203  			fmt.Fprintf(&buf, "\tsuccs:")
   204  			for _, succ := range b.Succs {
   205  				fmt.Fprintf(&buf, " %d", succ.Index)
   206  			}
   207  			buf.WriteByte('\n')
   208  		}
   209  		buf.WriteByte('\n')
   210  	}
   211  	return buf.String()
   212  }
   213  
   214  // Dot returns the control-flow graph in the [Dot graph description language].
   215  // Use a command such as 'dot -Tsvg' to render it in a form viewable in a browser.
   216  // This method is provided as a debugging aid; the details of the
   217  // output are unspecified and may change.
   218  //
   219  // [Dot graph description language]: https://en.wikipedia.org/wiki/DOT_(graph_description_language)
   220  func (g *CFG) Dot(fset *token.FileSet) string {
   221  	var buf bytes.Buffer
   222  	buf.WriteString("digraph CFG {\n")
   223  	buf.WriteString("  node [shape=box];\n")
   224  	for _, b := range g.Blocks {
   225  		// node label
   226  		var text bytes.Buffer
   227  		text.WriteString(b.comment(fset))
   228  		for _, n := range b.Nodes {
   229  			fmt.Fprintf(&text, "\n%s", formatNode(fset, n))
   230  		}
   231  
   232  		// node and edges
   233  		fmt.Fprintf(&buf, "  n%d [label=%q];\n", b.Index, &text)
   234  		for _, succ := range b.Succs {
   235  			fmt.Fprintf(&buf, "  n%d -> n%d;\n", b.Index, succ.Index)
   236  		}
   237  	}
   238  	buf.WriteString("}\n")
   239  	return buf.String()
   240  }
   241  
   242  func formatNode(fset *token.FileSet, n ast.Node) string {
   243  	var buf bytes.Buffer
   244  	format.Node(&buf, fset, n)
   245  	// Indent secondary lines by a tab.
   246  	return string(bytes.Replace(buf.Bytes(), []byte("\n"), []byte("\n\t"), -1))
   247  }
   248
View as plain text