[tools] internal/excfg: expression-level CFG package
Austin Clements (Gerrit)
Austin Clements has uploaded the change for review![]( "Open in Gerrit")
Austin Clements would like Alan Donovan to review this change.
Commit message
internal/excfg: expression-level CFG package
This new package builds on the cfg package, but builds an
expression-level control flow graph that captures control flow for
call expressions and short-circuit operators.
Change diff
diff --git a/internal/excfg/excfg.go b/internal/excfg/excfg.go
new file mode 100644
index 0000000..9283622
--- /dev/null
+++ b/internal/excfg/excfg.go
@@ -0,0 +1,400 @@
+// Copyright 2026 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 excfg
+
+import (
+ "go/ast"
+ "go/token"
+ "iter"
+ "slices"
+ "sync"
+
+ "golang.org/x/tools/go/cfg"
+)
+
+// ExCFG is a control flow graph over [ast.Node]s, including control flow within
+// expressions. Beyond the statement-level control flow represented by
+// [cfg.CFG], this graph contains a separate block for every statement, every
+// call (even within an expression), and for each branch of short-circuiting
+// operators.
+//
+// ExCFG implements graph.CompactGraph.
+type ExCFG struct {
+ Blocks []*ExBlock
+
+ subexprs struct {
+ once sync.Once
+ m [][]*ExBlock // Indexed by ExBlock.Index
+ }
+}
+
+// NumNodes returns the number of blocks in c.
+func (c *ExCFG) NumNodes() int {
+ return len(c.Blocks)
+}
+
+// All yields the indexes of all blocks in c. This is simply the sequence [0, NumNodes()).
+func (c *ExCFG) All() iter.Seq[int] {
+ return func(yield func(int) bool) {
+ for i := range c.Blocks {
+ if !yield(i) {
+ break
+ }
+ }
+ }
+}
+
+// Out yields the indexes of the successors of block.
+func (c *ExCFG) Out(block int) iter.Seq2[int, int] {
+ return func(yield func(int, int) bool) {
+ for i, succ := range c.Blocks[block].Succs {
+ if !yield(i, int(succ.Index)) {
+ break
+ }
+ }
+ }
+}
+
+type ExBlock struct {
+ Kind ExKind
+
+ // Node is a statement, expression, or ast.ValueSpec.
+ //
+ // An expression may contain sub-expressions computed in preceding blocks of
+ // type ExKindBool and ExKindCall. Each sub-expression block is used by
+ // exactly one other block, though that block may not be an immediate
+ // successor. All sub-expressions must be used at the end of an ExKindStmt
+ // or ExKindIf block. A sub-expression block will have a lower Index than
+ // the block that consumes the sub-expression.
+ Node ast.Node
+
+ // Succs is a list of successor nodes. The length and interpretation of this
+ // depends on Kind.
+ Succs []*ExBlock
+
+ // Use is set to the block that consumes the value of this sub-expression
+ // block. Only set for ExKindSubExpr and ExKindBool.
+ Use *ExBlock
+
+ // Index is the index of this block in ExCFG.Blocks.
+ Index int32
+
+ // CFGBlock is the index of the cfg.Block this expression block was derived
+ // from.
+ CFGBlock int32
+
+ succs [2]*ExBlock // Storage for Succs
+}
+
+type ExKind int8
+
+//go:generate stringer -type ExKind .
+
+const (
+ ExKindInvalid ExKind = iota
+
+ // An ExKindStmt ExBlock is a statement, expression, or ValueSpec with no
+ // value. It has 0 or 1 successors. It consumes any preceding sub-expression
+ // values.
+ ExKindStmt
+
+ // An ExKindIf ExBlock is a boolean-typed expression that branches to one of
+ // two successors. Like ExKindStmt, it consumes any preceding
+ // sub-expressions. Successor 0 is the true branch and successor 1 is the
+ // false branch.
+ ExKindIf
+
+ // An ExKindSubExpr ExBlock is a sub-expression whose value is used as part
+ // of another ExBlock. It has exactly one successor.
+ ExKindSubExpr
+
+ // An ExKindBool ExBlock is a sub-expression whose value is used as part of
+ // another ExBlock, like ExKindSubExpr, but it branches to two successors
+ // based on the value of the sub-expression. Successor 0 is the true branch
+ // and successor 1 is the false branch.
+ ExKindBool
+)
+
+func New(cfg *cfg.CFG) *ExCFG {
+ eb := builder{
+ entry: make([]*ExBlock, len(cfg.Blocks)),
+ }
+
+ // Allocate "placeholder" ExBlocks for each cfg.Block. We often need to
+ // record a successor that hasn't yet been converted to an ExBlock, so we
+ // use these placeholders for this and resolve them at the end.
+ placeholders := make([]ExBlock, len(cfg.Blocks))
+ for cfgi := range placeholders {
+ placeholders[cfgi].CFGBlock = int32(cfgi)
+ placeholders[cfgi].Index = -1 // Indicates a placeholder
+ eb.entry[cfgi] = &placeholders[cfgi]
+ }
+
+ // Convert each cfg.Block into one or more ExBlocks.
+ for cfgi := len(cfg.Blocks) - 1; cfgi >= 0; cfgi-- {
+ cfgb := cfg.Blocks[cfgi]
+ if cfgb.Live {
+ eb.visitBlock(cfgb)
+ }
+ }
+
+ // Put blocks in forward order.
+ eb.assertReverse()
+ slices.Reverse(eb.blocks)
+ for i, b := range eb.blocks {
+ b.Index = int32(i)
+ }
+
+ // Resolve placeholder blocks.
+ for _, b := range eb.blocks {
+ for i, succ := range b.Succs {
+ if succ.Index == -1 {
+ b.Succs[i] = eb.entry[succ.CFGBlock]
+ }
+ }
+ }
+
+ return &ExCFG{Blocks: eb.blocks}
+}
+
+// Subexprs returns the preceding sub-expression blocks consumed by b. This is
+// the inverse of [ExBlock.Use]. The slice is in ast.Inspect order for b.Node.
+func (g *ExCFG) Subexprs(b *ExBlock) []*ExBlock {
+ g.subexprs.once.Do(func() {
+ // Count how many back-references we need.
+ n := make([]int, 1+len(g.Blocks))
+ for _, b := range g.Blocks {
+ if b.Use != nil {
+ n[1+b.Use.Index]++
+ }
+ }
+ // Convert n from a count to an index.
+ for i := 1; i < len(n); i++ {
+ n[i] += n[i-1]
+ }
+ // Allocate a single block and slice it up.
+ allSubexprs := make([]*ExBlock, n[len(n)-1])
+ g.subexprs.m = make([][]*ExBlock, len(g.Blocks))
+ for i := range g.subexprs.m {
+ g.subexprs.m[i] = allSubexprs[n[i]:n[i+1]]
+ }
+ // Collect back-references.
+ for _, b := range g.Blocks {
+ if b.Use != nil {
+ allSubexprs[n[b.Use.Index]] = b
+ n[b.Use.Index]++
+ }
+ }
+ })
+ return g.subexprs.m[b.Index]
+}
+
+type builder struct {
+ blocks []*ExBlock
+
+ // Map from cfg.Block.Index to the entry ExBlock. Initially, this is
+ // populated with placeholder blocks that can be used in ExBlock.Succs. Once
+ // all blocks have been visited, they should all be replaced with actual
+ // ExBlocks, and NewExCFG will replace references to the placeholders.
+ entry []*ExBlock
+
+ // cfgBlock is the cfg.Block we're currently translating.
+ cfgBlock *cfg.Block
+
+ // For the most part, we build the block list in reverse so that successors
+ // are almost always already available. However, at the bottom of the
+ // recursive process we use ast.Inspect, we forces us to build it in forward
+ // order. Hence, we track whether we're in "reverse" or "forward" mode and
+ // when we exit forward mode, we reverse the forward part of the block list.
+ // Finally, at the very end of traversal, we reverse the entire block list
+ // into forward order. We never enter reverse mode from forward mode, so all
+ // remains linear time with simple tracking.
+
+ // forwardStart is in the index into blocks of the start of a forward region.
+ forwardStart int
+ // forwardDepth is the recursive depth of forward regions.
+ forwardDepth int
+}
+
+func (eb *builder) assertReverse() {
+ if eb.forwardDepth != 0 {
+ panic("unexpected reverse operation in forward region")
+ }
+}
+
+func (eb *builder) enterForward() {
+ if eb.forwardDepth == 0 {
+ eb.forwardStart = len(eb.blocks)
+ }
+ eb.forwardDepth++
+}
+
+func (eb *builder) exitForward() {
+ eb.forwardDepth--
+ if eb.forwardDepth == 0 {
+ // Put forward region into reverse order.
+ slices.Reverse(eb.blocks[eb.forwardStart:])
+ }
+}
+
+func (eb *builder) visitBlock(cb *cfg.Block) {
+ eb.cfgBlock = cb
+
+ var next *ExBlock
+ if len(cb.Succs) > 0 {
+ next = eb.entry[cb.Succs[0].Index]
+ }
+ isIf := len(cb.Succs) == 2
+ for ni := len(cb.Nodes) - 1; ni >= 0; ni-- {
+ eb.assertReverse()
+ node := cb.Nodes[ni]
+
+ if isIf {
+ next = eb.visitCond(node.(ast.Expr), next, eb.entry[cb.Succs[1].Index])
+ isIf = false
+ } else {
+ nodeEntry, nodeExit := eb.visitNode(ExKindStmt, node)
+ if next != nil {
+ nodeExit.Succs = nodeExit.succs[:1]
+ nodeExit.Succs[0] = next
+ }
+ next = nodeEntry
+ }
+ }
+
+ eb.entry[cb.Index] = next
+}
+
+// visitNode traverses a statement or expression node. It creates a sub-graph of
+// one or more blocks to compute root and returns the entry and exit blocks of
+// that subgraph. The type of the exit block is set to kind. The caller must set
+// the successors of the exit block.
+func (eb *builder) visitNode(kind ExKind, root ast.Node) (entry, exit *ExBlock) {
+ eb.enterForward()
+ defer eb.exitForward()
+
+ entryI := len(eb.blocks)
+ block := &ExBlock{Kind: kind, Node: root, CFGBlock: eb.cfgBlock.Index}
+
+ preds := make([]**ExBlock, 0, 3)
+ // link connects a subgraph of blocks by connecting the previous exit block
+ // to entry and recording the new exit block's successors that should be set
+ // to the next entry block. This is necessary because we're processing
+ // nodes in forward order here, so successors must be back-patched.
+ link := func(entry *ExBlock, exitSuccs ...**ExBlock) {
+ for _, pred := range preds {
+ *pred = entry
+ }
+ preds = append(preds[:0], exitSuccs...)
+ }
+
+ // Traverse root in pre-order, stopping at any sub-expressions that affect
+ // control flow to create blocks for those sub-expressions.
+ ast.Inspect(root, func(n ast.Node) bool {
+ switch n := n.(type) {
+ case *ast.FuncLit:
+ // The body of the function literal is not part of the control flow.
+ return false
+
+ case *ast.BinaryExpr:
+ switch n.Op {
+ case token.LAND:
+ xin, xout := eb.visitNode(ExKindBool, n.X)
+ yin, yout := eb.visitNode(ExKindSubExpr, n.Y)
+
+ xout.Use, yout.Use = block, block
+
+ xout.Succs = xout.succs[:2]
+ xout.Succs[0] = yin // If true, evaluate Y.
+
+ yout.Succs = yout.succs[:1]
+
+ // x && y will produce:
+ //
+ // x
+ // / \
+ // y \
+ // \ /
+ // (x && y)
+ link(xin, &xout.succs[1], &yout.succs[0])
+
+ return false
+
+ case token.LOR:
+ xin, xout := eb.visitNode(ExKindBool, n.X)
+ yin, yout := eb.visitNode(ExKindSubExpr, n.Y)
+
+ xout.Use, yout.Use = block, block
+
+ xout.Succs = xout.succs[:2]
+ xout.Succs[1] = yin // If false, evaluate Y.
+
+ yout.Succs = yout.succs[:1]
+
+ link(xin, &xout.succs[0], &yout.succs[0])
+
+ return false
+ }
+
+ case *ast.CallExpr:
+ // f() + g() + h() has an AST like
+ //
+ // +
+ // / \
+ // f() \
+ // +
+ // / \
+ // g() h()
+ //
+ // Because of the traversal order, we'll produce a linkage like
+ //
+ // f() => g() => h() => root +
+ if n != root {
+ in, out := eb.visitNode(ExKindSubExpr, n)
+ out.Use = block
+ out.Succs = out.succs[:1]
+ link(in, &out.succs[0])
+ return false
+ }
+ }
+ return true
+ })
+
+ link(block)
+ eb.blocks = append(eb.blocks, block)
+ return eb.blocks[entryI], block
+}
+
+func (eb *builder) visitCond(n ast.Expr, tSucc, fSucc *ExBlock) (entry *ExBlock) {
+ eb.assertReverse()
+
+ switch n := n.(type) {
+ case *ast.ParenExpr:
+ return eb.visitCond(n.X, tSucc, fSucc)
+
+ case *ast.UnaryExpr:
+ if n.Op == token.NOT {
+ return eb.visitCond(n.X, fSucc, tSucc)
+ }
+
+ case *ast.BinaryExpr:
+ switch n.Op {
+ case token.LAND:
+ y := eb.visitCond(n.Y, tSucc, fSucc)
+ x := eb.visitCond(n.X, y, fSucc)
+ return x
+ case token.LOR:
+ y := eb.visitCond(n.Y, tSucc, fSucc)
+ x := eb.visitCond(n.X, tSucc, y)
+ return x
+ }
+ }
+
+ entry, exit := eb.visitNode(ExKindIf, n)
+ exit.Succs = exit.succs[:2]
+ exit.Succs[0] = tSucc
+ exit.Succs[1] = fSucc
+ return entry
+}
diff --git a/internal/excfg/excfg_test.go b/internal/excfg/excfg_test.go
new file mode 100644
index 0000000..79af000
--- /dev/null
+++ b/internal/excfg/excfg_test.go
@@ -0,0 +1,106 @@
+// Copyright 2026 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 excfg
+
+import (
+ "bytes"
+ "flag"
+ "go/ast"
+ "go/parser"
+ "go/token"
+ "os"
+ "path/filepath"
+ "strings"
+ "testing"
+
+ "golang.org/x/tools/go/cfg"
+ "golang.org/x/tools/txtar"
+)
+
+var update = flag.Bool("update", false, "update expected output")
+
+func TestExCFG(t *testing.T) {
+ files, err := filepath.Glob("testdata/*.txt")
+ if err != nil {
+ t.Fatal(err)
+ }
+ if len(files) == 0 {
+ t.Fatal("no test files found in testdata/")
+ }
+
+ for _, file := range files {
+ t.Run(filepath.Base(file), func(t *testing.T) {
+ data, err := os.ReadFile(file)
+ if err != nil {
+ t.Fatal(err)
+ }
+ ar := txtar.Parse(data)
+ var src, want []byte
+ for _, f := range ar.Files {
+ switch f.Name {
+ case "src.go":
+ src = f.Data
+ case "want":
+ want = bytes.TrimSpace(f.Data)
+ }
+ }
+
+ if src == nil {
+ t.Fatal("missing src.go in test file")
+ }
+
+ fset := token.NewFileSet()
+ f, err := parser.ParseFile(fset, "src.go", src, 0)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ // Find function body.
+ var body *ast.BlockStmt
+ for _, decl := range f.Decls {
+ if fd, ok := decl.(*ast.FuncDecl); ok && fd.Name.Name == "main" {
+ body = fd.Body
+ break
+ }
+ }
+
+ if body == nil {
+ t.Fatal("no main function found")
+ }
+
+ c := cfg.New(body, func(call *ast.CallExpr) bool { return true })
+ ec := New(c)
+ got := strings.TrimSpace(ec.Format(fset))
+
+ if *update {
+ found := false
+ for i := range ar.Files {
+ if ar.Files[i].Name == "want" {
+ ar.Files[i].Data = []byte(got)
+ found = true
+ break
+ }
+ }
+ if !found {
+ ar.Files = append(ar.Files, txtar.File{
+ Name: "want",
+ Data: []byte(got),
+ })
+ }
+ if err := os.WriteFile(file, txtar.Format(ar), 0644); err != nil {
+ t.Fatal(err)
+ }
+ return
+ }
+
+ if want == nil {
+ t.Logf("Output for %s:\n%s", file, got)
+ t.Errorf("missing expected output")
+ } else if got != string(want) {
+ t.Errorf("mismatch:\ngot:\n%s\nwant:\n%s", got, want)
+ }
+ })
+ }
+}
diff --git a/internal/excfg/exkind_string.go b/internal/excfg/exkind_string.go
new file mode 100644
index 0000000..2db0b78
--- /dev/null
+++ b/internal/excfg/exkind_string.go
@@ -0,0 +1,28 @@
+// Code generated by "stringer -type ExKind ."; DO NOT EDIT.
+
+package excfg
+
+import "strconv"
+
+func _() {
+ // An "invalid array index" compiler error signifies that the constant values have changed.
+ // Re-run the stringer command to generate them again.
+ var x [1]struct{}
+ _ = x[ExKindInvalid-0]
+ _ = x[ExKindStmt-1]
+ _ = x[ExKindIf-2]
+ _ = x[ExKindSubExpr-3]
+ _ = x[ExKindBool-4]
+}
+
+const _ExKind_name = "ExKindInvalidExKindStmtExKindIfExKindSubExprExKindBool"
+
+var _ExKind_index = [...]uint8{0, 13, 23, 31, 44, 54}
+
+func (i ExKind) String() string {
+ idx := int(i) - 0
+ if i < 0 || idx >= len(_ExKind_index)-1 {
+ return "ExKind(" + strconv.FormatInt(int64(i), 10) + ")"
+ }
+ return _ExKind_name[_ExKind_index[idx]:_ExKind_index[idx+1]]
+}
diff --git a/internal/excfg/format.go b/internal/excfg/format.go
new file mode 100644
index 0000000..80eb855
--- /dev/null
+++ b/internal/excfg/format.go
@@ -0,0 +1,86 @@
+// Copyright 2026 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 excfg
+
+import (
+ "bytes"
+ "fmt"
+ "go/ast"
+ "go/format"
+ "go/token"
+ "strings"
+
+ "golang.org/x/tools/go/ast/astutil"
+)
+
+// Format formats the control-flow graph for ease of debugging.
+func (cfg *ExCFG) Format(fset *token.FileSet) string {
+ var buf strings.Builder
+ for _, b := range cfg.Blocks {
+ fmt.Fprintf(&buf, "%s: %s, CFG block .%d\n", b, b.Kind, b.CFGBlock)
+ fmt.Fprintf(&buf, "\t%s\n", formatBlockNode(fset, b, cfg))
+ if len(b.Succs) > 0 {
+ fmt.Fprintf(&buf, "\tsuccs:")
+ for _, succ := range b.Succs {
+ fmt.Fprintf(&buf, " %s", succ)
+ }
+ buf.WriteByte('\n')
+ }
+ buf.WriteByte('\n')
+ }
+ return buf.String()
+}
+
+func (b *ExBlock) String() string {
+ return fmt.Sprintf("B%d", b.Index)
+}
+
+func formatBlockNode(fset *token.FileSet, b *ExBlock, cfg *ExCFG) string {
+ // Temporarily replace sub-expressions with their block names.
+ subs := cfg.Subexprs(b)
+ subMap := make(map[ast.Node]*ExBlock)
+ for _, sub := range subs {
+ subMap[sub.Node] = sub
+ }
+
+ // We use astutil.Apply to replace nodes. This modifies the AST in place,
+ // so we have to be careful to undo our changes.
+ //
+ // Note that we don't need to worry about the parent pointers in Apply
+ // because we're just replacing expressions with identifiers.
+
+ // replacements maps the original node to the replacement node so we can undo.
+ replacements := make(map[ast.Node]ast.Node)
+
+ // Apply replacement.
+ n := b.Node
+ astutil.Apply(n, func(c *astutil.Cursor) bool {
+ node := c.Node()
+ if sub, ok := subMap[node]; ok {
+ id := &ast.Ident{Name: sub.String()}
+ c.Replace(id)
+ replacements[id] = node
+ return false // Don't traverse into sub-expression.
+ }
+ return true
+ }, nil)
+
+ // Format.
+ var buf bytes.Buffer
+ format.Node(&buf, fset, n)
+ res := string(bytes.Replace(buf.Bytes(), []byte("\n"), []byte("\n\t"), -1))
+
+ // Undo replacement.
+ astutil.Apply(n, func(c *astutil.Cursor) bool {
+ node := c.Node()
+ if original, ok := replacements[node]; ok {
+ c.Replace(original)
+ return false
+ }
+ return true
+ }, nil)
+
+ return res
+}
diff --git a/internal/excfg/testdata/backedge.txt b/internal/excfg/testdata/backedge.txt
new file mode 100644
index 0000000..343523f
--- /dev/null
+++ b/internal/excfg/testdata/backedge.txt
@@ -0,0 +1,25 @@
+-- src.go --
+package main
+var x bool
+func main() {
+l:
+ print()
+ if x {
+ goto l
+ }
+}
+-- want --
+B0: ExKindSubExpr, CFG block .1
+ print()
+ succs: B1
+
+B1: ExKindStmt, CFG block .1
+ B0
+ succs: B2
+
+B2: ExKindIf, CFG block .1
+ x
+ succs: B0 B3
+
+B3: ExKindStmt, CFG block .3
+ return
diff --git a/internal/excfg/testdata/call_nested.txt b/internal/excfg/testdata/call_nested.txt
new file mode 100644
index 0000000..3ccb918
--- /dev/null
+++ b/internal/excfg/testdata/call_nested.txt
@@ -0,0 +1,27 @@
+-- src.go --
+package p
+func f(int) int
+func g() int
+func main() {
+ x := f(g())
+ _ = x
+}
+-- want --
+B0: ExKindSubExpr, CFG block .0
+ g()
+ succs: B1
+
+B1: ExKindSubExpr, CFG block .0
+ f(B0)
+ succs: B2
+
+B2: ExKindStmt, CFG block .0
+ x := B1
+ succs: B3
+
+B3: ExKindStmt, CFG block .0
+ _ = x
+ succs: B4
+
+B4: ExKindStmt, CFG block .0
+ return
diff --git a/internal/excfg/testdata/call_seq.txt b/internal/excfg/testdata/call_seq.txt
new file mode 100644
index 0000000..07f3587
--- /dev/null
+++ b/internal/excfg/testdata/call_seq.txt
@@ -0,0 +1,27 @@
+-- src.go --
+package main
+func f() int
+func g() int
+func h() int
+func main() {
+ _ = f() + g() + h()
+}
+-- want --
+B0: ExKindSubExpr, CFG block .0
+ f()
+ succs: B1
+
+B1: ExKindSubExpr, CFG block .0
+ g()
+ succs: B2
+
+B2: ExKindSubExpr, CFG block .0
+ h()
+ succs: B3
+
+B3: ExKindStmt, CFG block .0
+ _ = B0 + B1 + B2
+ succs: B4
+
+B4: ExKindStmt, CFG block .0
+ return
diff --git a/internal/excfg/testdata/expr.txt b/internal/excfg/testdata/expr.txt
new file mode 100644
index 0000000..d8d4e82
--- /dev/null
+++ b/internal/excfg/testdata/expr.txt
@@ -0,0 +1,35 @@
+-- src.go --
+package main
+func f() bool
+func g() bool
+func main() {
+ _ = f() && g()
+ _ = f() || g()
+}
+-- want --
+B0: ExKindBool, CFG block .0
+ f()
+ succs: B1 B2
+
+B1: ExKindSubExpr, CFG block .0
+ g()
+ succs: B2
+
+B2: ExKindStmt, CFG block .0
+ _ = B0 && B1
+ succs: B3
+
+B3: ExKindBool, CFG block .0
+ f()
+ succs: B5 B4
+
+B4: ExKindSubExpr, CFG block .0
+ g()
+ succs: B5
+
+B5: ExKindStmt, CFG block .0
+ _ = B3 || B4
+ succs: B6
+
+B6: ExKindStmt, CFG block .0
+ return
diff --git a/internal/excfg/testdata/funclit.txt b/internal/excfg/testdata/funclit.txt
new file mode 100644
index 0000000..573e29f
--- /dev/null
+++ b/internal/excfg/testdata/funclit.txt
@@ -0,0 +1,21 @@
+-- src.go --
+package main
+func main() {
+ f := func() { print() }
+ f()
+}
+-- want --
+B0: ExKindStmt, CFG block .0
+ f := func() { print() }
+ succs: B1
+
+B1: ExKindSubExpr, CFG block .0
+ f()
+ succs: B2
+
+B2: ExKindStmt, CFG block .0
+ B1
+ succs: B3
+
+B3: ExKindStmt, CFG block .0
+ return
diff --git a/internal/excfg/testdata/if_and.txt b/internal/excfg/testdata/if_and.txt
new file mode 100644
index 0000000..057eb19
--- /dev/null
+++ b/internal/excfg/testdata/if_and.txt
@@ -0,0 +1,29 @@
+-- src.go --
+package p
+func f() bool
+func g() bool
+func main() {
+ // The unary not should be reflected directly in the control flow.
+ if !f() && g() {
+ print()
+ }
+}
+-- want --
+B0: ExKindIf, CFG block .0
+ f()
+ succs: B4 B1
+
+B1: ExKindIf, CFG block .0
+ g()
+ succs: B2 B4
+
+B2: ExKindSubExpr, CFG block .1
+ print()
+ succs: B3
+
+B3: ExKindStmt, CFG block .1
+ B2
+ succs: B4
+
+B4: ExKindStmt, CFG block .2
+ return
diff --git a/internal/excfg/testdata/if_or.txt b/internal/excfg/testdata/if_or.txt
new file mode 100644
index 0000000..b1dd811
--- /dev/null
+++ b/internal/excfg/testdata/if_or.txt
@@ -0,0 +1,29 @@
+-- src.go --
+package p
+func f() bool
+func g() bool
+func main() {
+ // The unary not should be reflected directly in the control flow.
+ if !(f() || g()) {
+ print()
+ }
+}
+-- want --
+B0: ExKindIf, CFG block .0
+ f()
+ succs: B4 B1
+
+B1: ExKindIf, CFG block .0
+ g()
+ succs: B4 B2
+
+B2: ExKindSubExpr, CFG block .1
+ print()
+ succs: B3
+
+B3: ExKindStmt, CFG block .1
+ B2
+ succs: B4
+
+B4: ExKindStmt, CFG block .2
+ return
Change information
- A internal/excfg/excfg.go
- A internal/excfg/excfg_test.go
- A internal/excfg/exkind_string.go
- A internal/excfg/format.go
- A internal/excfg/testdata/backedge.txt
- A internal/excfg/testdata/call_nested.txt
- A internal/excfg/testdata/call_seq.txt
- A internal/excfg/testdata/expr.txt
- A internal/excfg/testdata/funclit.txt
- A internal/excfg/testdata/if_and.txt
- A internal/excfg/testdata/if_or.txt
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 11 comments![]( "Open in Gerrit")
I think we should revisit the existing go/cfg package so that it provides this functionality, either by moving this new code into that package, or by melding the two into something better. (It needn't block this CL.) There are very few dependencies on the go/cfg API so it wouldn't be hard to do a v2 and get rid of the v1 package.
type ExCFG struct {CFG
(ex is already in the package name)
ditto Block
// All yields the indexes of all blocks in c. This is simply the sequence [0, NumNodes()).I wonder why this is needed over `range c.NumNodes()`.
...
Ah, it's to implement the Graph interface. I think it might be clearer if we rename the Graph.All iterator as Graph.Nodes since a graph is more than just a collection of nodes, unlikes most things with an All method.
for cfgi := range placeholders {i
(all these `cfg`s are harder to follow)
for cfgi := len(cfg.Blocks) - 1; cfgi >= 0; cfgi-- {Any particular reason we work backwards?
for cfgi := len(cfg.Blocks) - 1; cfgi >= 0; cfgi-- {i
case *ast.UnaryExpr:
if n.Op == token.NOT {
return eb.visitCond(n.X, fSucc, tSucc)
}
case *ast.BinaryExpr:
switch n.Op {
case token.LAND:
y := eb.visitCond(n.Y, tSucc, fSucc)
x := eb.visitCond(n.X, y, fSucc)
return x
case token.LOR:
y := eb.visitCond(n.Y, tSucc, fSucc)
x := eb.visitCond(n.X, tSucc, y)
return x
}
}
Presumably these optimizations mean that the nodes for (x), x&&y, x||y are melted away and never appear in the ExCFG, much as some control-flow statements don't appear in the regular cfg. That seems worth documenting.
// We use astutil.Apply to replace nodes. This modifies the AST in place,
// so we have to be careful to undo our changes.In the analysis framework, the syntax trees are borrowed so you're not allowed to mutate them, even temporarily; there are likely to be other goroutines concurrently reading them.
You would have to do something like a preemptive astutil.Clone (which is expensive, but presumably this is just for debugging).
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 11 comments![]( "Open in Gerrit")
This is a building block for the
package excfgAustin ClementsDoc comment?
Done
type ExCFG struct {CFG
(ex is already in the package name)
ditto Block
Done
var _ Graph[int] = (*ExCFG)(nil)
I had avoided actually importing internal/graph in this package to reduce coupling, but maybe that was a false economy.
// All yields the indexes of all blocks in c. This is simply the sequence [0, NumNodes()).I wonder why this is needed over `range c.NumNodes()`.
...
Ah, it's to implement the Graph interface. I think it might be clearer if we rename the Graph.All iterator as Graph.Nodes since a graph is more than just a collection of nodes, unlikes most things with an All method.
Done
for cfgi := range placeholders {i
(all these `cfg`s are harder to follow)
Done
for cfgi := len(cfg.Blocks) - 1; cfgi >= 0; cfgi-- {Austin Clementsi
Done
for cfgi := len(cfg.Blocks) - 1; cfgi >= 0; cfgi-- {Any particular reason we work backwards?
Added a comment:
// We do this backwards so that successor blocks are usually already visited
// and we can link them up eagerly.
cfgb := cfg.Blocks[cfgi]Austin Clementsb
Done
case *ast.UnaryExpr:
if n.Op == token.NOT {
return eb.visitCond(n.X, fSucc, tSucc)
}
case *ast.BinaryExpr:
switch n.Op {
case token.LAND:
y := eb.visitCond(n.Y, tSucc, fSucc)
x := eb.visitCond(n.X, y, fSucc)
return x
case token.LOR:
y := eb.visitCond(n.Y, tSucc, fSucc)
x := eb.visitCond(n.X, tSucc, y)
return x
}
}
Presumably these optimizations mean that the nodes for (x), x&&y, x||y are melted away and never appear in the ExCFG, much as some control-flow statements don't appear in the regular cfg. That seems worth documenting.
True. Added to the CFG type doc.
// We use astutil.Apply to replace nodes. This modifies the AST in place,
// so we have to be careful to undo our changes.In the analysis framework, the syntax trees are borrowed so you're not allowed to mutate them, even temporarily; there are likely to be other goroutines concurrently reading them.
You would have to do something like a preemptive astutil.Clone (which is expensive, but presumably this is just for debugging).
Darn, I was hoping I could get away with this!
It's not clear to me how to use astutil.Clone for this because subMap will still be indexed by the pre-Clone Nodes, but astutil.Apply will run over the post-Clone nodes. I could get around that if astutil.Clone returned a mapping, or if astutil.Apply passed an inspector.Cursor that would let me replicate the path in the pre-Clone AST, or if there was some way to use inspector.Cursor to directly mutate an AST.
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 3 comments![]( "Open in Gerrit")
Austin Clementsvar _ Graph[int] = (*ExCFG)(nil)
I had avoided actually importing internal/graph in this package to reduce coupling, but maybe that was a false economy.
Ah, got it; I respect that.
func (cfg *ExCFG) Format(fset *token.FileSet) string {It might be worth making the ExCFG constructor to accept a FileSet. I wish for debugging convenience I had done this with both CFG and Inspector since they both handle ast.Nodes, but unfortunately it's too late to make it a required field now.
Then this could be a String method.
// We use astutil.Apply to replace nodes. This modifies the AST in place,
// so we have to be careful to undo our changes.Austin ClementsIn the analysis framework, the syntax trees are borrowed so you're not allowed to mutate them, even temporarily; there are likely to be other goroutines concurrently reading them.
You would have to do something like a preemptive astutil.Clone (which is expensive, but presumably this is just for debugging).
Darn, I was hoping I could get away with this!
It's not clear to me how to use astutil.Clone for this because subMap will still be indexed by the pre-Clone Nodes, but astutil.Apply will run over the post-Clone nodes. I could get around that if astutil.Clone returned a mapping, or if astutil.Apply passed an inspector.Cursor that would let me replicate the path in the pre-Clone AST, or if there was some way to use inspector.Cursor to directly mutate an AST.
I agree this is unfortunately tricker than it should be, but I think this clumsy solution should be workable:
1. use ast.Inspect to visit the original tree in preorder, appending each node to a list. If a node is present in subMap, return false so that its subtrees are skipped.
2. clone the tree.
3. Visit the new tree using Apply, counting nodes as they are encountered. These numbers are indices into list from step 1, thus mapping each new node to its corresponding old one. If the old node is present in subMap, replace it.
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 2 comments![]( "Open in Gerrit")
It might be worth making the ExCFG constructor to accept a FileSet. I wish for debugging convenience I had done this with both CFG and Inspector since they both handle ast.Nodes, but unfortunately it's too late to make it a required field now.
Then this could be a String method.
Done
// We use astutil.Apply to replace nodes. This modifies the AST in place,
// so we have to be careful to undo our changes.Austin ClementsIn the analysis framework, the syntax trees are borrowed so you're not allowed to mutate them, even temporarily; there are likely to be other goroutines concurrently reading them.
You would have to do something like a preemptive astutil.Clone (which is expensive, but presumably this is just for debugging).
Alan DonovanDarn, I was hoping I could get away with this!
It's not clear to me how to use astutil.Clone for this because subMap will still be indexed by the pre-Clone Nodes, but astutil.Apply will run over the post-Clone nodes. I could get around that if astutil.Clone returned a mapping, or if astutil.Apply passed an inspector.Cursor that would let me replicate the path in the pre-Clone AST, or if there was some way to use inspector.Cursor to directly mutate an AST.
I agree this is unfortunately tricker than it should be, but I think this clumsy solution should be workable:
1. use ast.Inspect to visit the original tree in preorder, appending each node to a list. If a node is present in subMap, return false so that its subtrees are skipped.
2. clone the tree.
3. Visit the new tree using Apply, counting nodes as they are encountered. These numbers are indices into list from step 1, thus mapping each new node to its corresponding old one. If the old node is present in subMap, replace it.
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan voted and added 2 comments![]( "Open in Gerrit")
Votes added by Alan Donovan
| Code-Review | +2 |
2 comments
func formatBlockNode(b *Block, cfg *CFG) string {cfg should come first since it is "less variable" than b.
// We use astutil.Apply to replace nodes. This modifies the AST in place,
// so we have to be careful to undo our changes.Austin ClementsIn the analysis framework, the syntax trees are borrowed so you're not allowed to mutate them, even temporarily; there are likely to be other goroutines concurrently reading them.
You would have to do something like a preemptive astutil.Clone (which is expensive, but presumably this is just for debugging).
Alan DonovanDarn, I was hoping I could get away with this!
It's not clear to me how to use astutil.Clone for this because subMap will still be indexed by the pre-Clone Nodes, but astutil.Apply will run over the post-Clone nodes. I could get around that if astutil.Clone returned a mapping, or if astutil.Apply passed an inspector.Cursor that would let me replicate the path in the pre-Clone AST, or if there was some way to use inspector.Cursor to directly mutate an AST.
Austin ClementsI agree this is unfortunately tricker than it should be, but I think this clumsy solution should be workable:
1. use ast.Inspect to visit the original tree in preorder, appending each node to a list. If a node is present in subMap, return false so that its subtrees are skipped.
2. clone the tree.
3. Visit the new tree using Apply, counting nodes as they are encountered. These numbers are indices into list from step 1, thus mapping each new node to its corresponding old one. If the old node is present in subMap, replace it.
Done
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 2 comments![]( "Open in Gerrit")
cfg should come first since it is "less variable" than b.
Done
// We use astutil.Apply to replace nodes. This modifies the AST in place,
// so we have to be careful to undo our changes.Austin ClementsIn the analysis framework, the syntax trees are borrowed so you're not allowed to mutate them, even temporarily; there are likely to be other goroutines concurrently reading them.
You would have to do something like a preemptive astutil.Clone (which is expensive, but presumably this is just for debugging).
Alan DonovanDarn, I was hoping I could get away with this!
It's not clear to me how to use astutil.Clone for this because subMap will still be indexed by the pre-Clone Nodes, but astutil.Apply will run over the post-Clone nodes. I could get around that if astutil.Clone returned a mapping, or if astutil.Apply passed an inspector.Cursor that would let me replicate the path in the pre-Clone AST, or if there was some way to use inspector.Cursor to directly mutate an AST.
Austin ClementsI agree this is unfortunately tricker than it should be, but I think this clumsy solution should be workable:
1. use ast.Inspect to visit the original tree in preorder, appending each node to a list. If a node is present in subMap, return false so that its subtrees are skipped.
2. clone the tree.
3. Visit the new tree using Apply, counting nodes as they are encountered. These numbers are indices into list from step 1, thus mapping each new node to its corresponding old one. If the old node is present in subMap, replace it.
Alan DonovanDone
That was quick, and the code is very neat.
Thanks, but I shouldn't be working this late. 😄
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements uploaded new patchset![]( "Open in Gerrit")
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan voted and added 1 comment![]( "Open in Gerrit")
Votes added by Alan Donovan
| Code-Review | +2 |
1 comment
// We use astutil.Apply to replace nodes. This modifies the AST in place,
// so we have to be careful to undo our changes.Austin ClementsIn the analysis framework, the syntax trees are borrowed so you're not allowed to mutate them, even temporarily; there are likely to be other goroutines concurrently reading them.
You would have to do something like a preemptive astutil.Clone (which is expensive, but presumably this is just for debugging).
Alan DonovanDarn, I was hoping I could get away with this!
It's not clear to me how to use astutil.Clone for this because subMap will still be indexed by the pre-Clone Nodes, but astutil.Apply will run over the post-Clone nodes. I could get around that if astutil.Clone returned a mapping, or if astutil.Apply passed an inspector.Cursor that would let me replicate the path in the pre-Clone AST, or if there was some way to use inspector.Cursor to directly mutate an AST.
Austin ClementsI agree this is unfortunately tricker than it should be, but I think this clumsy solution should be workable:
1. use ast.Inspect to visit the original tree in preorder, appending each node to a list. If a node is present in subMap, return false so that its subtrees are skipped.
2. clone the tree.
3. Visit the new tree using Apply, counting nodes as they are encountered. These numbers are indices into list from step 1, thus mapping each new node to its corresponding old one. If the old node is present in subMap, replace it.
Alan DonovanDone
Austin ClementsThat was quick, and the code is very neat.
Thanks, but I shouldn't be working this late. 😄
At least you're writing code instead of playing Gerrit browser tab whackamole. ;-)
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |