dataflow

Documentation

Overview

Package dataflow provides data flow analyses that can be performed on a previously constructed control flow graph, including a reaching definitions analysis and a live variables analysis for local variables.

Index

• func LiveVars(cfg *cfg.CFG, info *loader.PackageInfo) (in, out map[ast.Stmt]map[*types.Var]struct{})
• func ReachingDefs(cfg *cfg.CFG, info *loader.PackageInfo) (in, out map[ast.Stmt]map[ast.Stmt]struct{})
• func ReferencedVars(stmts []ast.Stmt, info *loader.PackageInfo) (asgt, updt, decl, use map[*types.Var]struct{})

Examples

• LiveVars
• ReachingDefs

Functions

func LiveVars

func LiveVars(cfg *cfg.CFG, info *loader.PackageInfo) (in, out map[ast.Stmt]map[*types.Var]struct{})

LiveAt returns the in and out set of live variables for each block in a given control flow graph (cfg) in the context of a loader.Program, including the cfg.Entry and cfg.Exit nodes.

The traditional approach of holding the live variables at the exit node to the empty set has been deviated from in order to handle defers. The live variables in set of the cfg.Exit node will be set to the variables used in all cfg.Defers. No liveness is analyzed for the cfg.Defers themselves.

More formally:

IN[EXIT] = USE(each d in cfg.Defers)
OUT[EXIT] = {}

Example

package main

import (
	"go/ast"

	"golang.org/x/tools/go/loader"

	"github.com/godoctor/godoctor/analysis/cfg"
	"github.com/godoctor/godoctor/analysis/dataflow"
)

func main() {
	src := `
    package main

    import "fmt"

    func main() {
      a := 1
      b := 2
      c := 3
      a := b
      a, b := b, a
      c := a + b
    }
  `

	// use own loader config, this is just necessary
	var config loader.Config
	f, err := config.ParseFile("testing", src)
	if err != nil {
		return // probably don't proceed
	}
	config.CreateFromFiles("testing", f)
	prog, err := config.Load()
	if err != nil {
		return
	}

	funcOne := f.Decls[1].(*ast.FuncDecl)
	cfg := cfg.FromFunc(funcOne)
	in, out := dataflow.LiveVars(cfg, prog.Created[0])

	ast.Inspect(f, func(n ast.Node) bool {
		switch stmt := n.(type) {
		case ast.Stmt:
			_, _ = in[stmt], out[stmt]
			// do as you please
		}
		return true
	})
}

func ReachingDefs

func ReachingDefs(cfg *cfg.CFG, info *loader.PackageInfo) (in, out map[ast.Stmt]map[ast.Stmt]struct{})

ReachingDefs builds reaching definitions for a given control flow graph, returning the in and out sets in a map of stmts for each block (statement).

No nodes from the cfg.Defers list will be returned in the output of this function as they are disjoint from a cfg's blocks. For analyzing the statements in the cfg.Defers list, each defer should be treated as though it has the same in and out sets as the cfg.Exit node.

Example

package main

import (
	"fmt"
	"go/ast"

	"golang.org/x/tools/go/loader"

	"github.com/godoctor/godoctor/analysis/cfg"
	"github.com/godoctor/godoctor/analysis/dataflow"
)

func main() {
	src := `
    package main

    import "fmt"

    func main() {
      a := 1
      b := 2
      c := 3
      a := b
      a, b := b, a
      c := a + b
    }
  `

	// use own loader config, this is just necessary
	var config loader.Config
	f, err := config.ParseFile("testing", src)
	if err != nil {
		return // probably don't proceed
	}
	config.CreateFromFiles("testing", f)
	prog, err := config.Load()
	if err != nil {
		return
	}

	funcOne := f.Decls[1].(*ast.FuncDecl)
	c := cfg.FromFunc(funcOne)
	in, out := dataflow.ReachingDefs(c, prog.Created[0])

	ast.Inspect(f, func(n ast.Node) bool {
		switch stmt := n.(type) {
		case ast.Stmt:
			ins, _ := in[stmt], out[stmt]
			fmt.Println(len(ins))
			// do as you please
		}
		return true
	})
}

func ReferencedVars

func ReferencedVars(stmts []ast.Stmt, info *loader.PackageInfo) (asgt, updt, decl, use map[*types.Var]struct{})

ReferencedVars returns the sets of local variables that are defined or used within the given list of statements (based on syntax).