propagation_test.go

Documentation: golang.org/x/tools/go/callgraph/vta

     1  // Copyright 2021 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 vta
     6  
     7  import (
     8  	"go/token"
     9  	"go/types"
    10  	"reflect"
    11  	"sort"
    12  	"strings"
    13  	"testing"
    14  	"unsafe"
    15  
    16  	"golang.org/x/tools/go/ssa"
    17  
    18  	"golang.org/x/tools/go/types/typeutil"
    19  )
    20  
    21  // val is a test data structure for creating ssa.Value
    22  // outside of the ssa package. Needed for manual creation
    23  // of vta graph nodes in testing.
    24  type val struct {
    25  	name string
    26  	typ  types.Type
    27  }
    28  
    29  func (v val) String() string {
    30  	return v.name
    31  }
    32  
    33  func (v val) Name() string {
    34  	return v.name
    35  }
    36  
    37  func (v val) Type() types.Type {
    38  	return v.typ
    39  }
    40  
    41  func (v val) Parent() *ssa.Function {
    42  	return nil
    43  }
    44  
    45  func (v val) Referrers() *[]ssa.Instruction {
    46  	return nil
    47  }
    48  
    49  func (v val) Pos() token.Pos {
    50  	return token.NoPos
    51  }
    52  
    53  // newLocal creates a new local node with ssa.Value
    54  // named `name` and type `t`.
    55  func newLocal(name string, t types.Type) local {
    56  	return local{val: val{name: name, typ: t}}
    57  }
    58  
    59  // newNamedType creates a bogus type named `name`.
    60  func newNamedType(name string) *types.Named {
    61  	return types.NewNamed(types.NewTypeName(token.NoPos, nil, name, nil), types.Universe.Lookup("int").Type(), nil)
    62  }
    63  
    64  // sccString is a utility for stringifying `nodeToScc`. Every
    65  // scc is represented as a string where string representation
    66  // of scc nodes are sorted and concatenated using `;`.
    67  func sccString(nodeToScc map[node]int) []string {
    68  	sccs := make(map[int][]node)
    69  	for n, id := range nodeToScc {
    70  		sccs[id] = append(sccs[id], n)
    71  	}
    72  
    73  	var sccsStr []string
    74  	for _, scc := range sccs {
    75  		var nodesStr []string
    76  		for _, node := range scc {
    77  			nodesStr = append(nodesStr, node.String())
    78  		}
    79  		sort.Strings(nodesStr)
    80  		sccsStr = append(sccsStr, strings.Join(nodesStr, ";"))
    81  	}
    82  	return sccsStr
    83  }
    84  
    85  // nodeToTypeString is testing utility for stringifying results
    86  // of type propagation: propTypeMap `pMap` is converted to a map
    87  // from node strings to a string consisting of type stringifications
    88  // concatenated with `;`. We stringify reachable type information
    89  // that also has an accompanying function by the function name.
    90  func nodeToTypeString(pMap propTypeMap) map[string]string {
    91  	// Convert propType to a string. If propType has
    92  	// an attached function, return the function name.
    93  	// Otherwise, return the type name.
    94  	propTypeString := func(p propType) string {
    95  		if p.f != nil {
    96  			return p.f.Name()
    97  		}
    98  		return p.typ.String()
    99  	}
   100  
   101  	nodeToTypeStr := make(map[string]string)
   102  	for node := range pMap.nodeToScc {
   103  		var propStrings []string
   104  		for _, prop := range pMap.propTypes(node) {
   105  			propStrings = append(propStrings, propTypeString(prop))
   106  		}
   107  		sort.Strings(propStrings)
   108  		nodeToTypeStr[node.String()] = strings.Join(propStrings, ";")
   109  	}
   110  
   111  	return nodeToTypeStr
   112  }
   113  
   114  // sccEqual compares two sets of SCC stringifications.
   115  func sccEqual(sccs1 []string, sccs2 []string) bool {
   116  	if len(sccs1) != len(sccs2) {
   117  		return false
   118  	}
   119  	sort.Strings(sccs1)
   120  	sort.Strings(sccs2)
   121  	return reflect.DeepEqual(sccs1, sccs2)
   122  }
   123  
   124  // isRevTopSorted checks if sccs of `g` are sorted in reverse
   125  // topological order:
   126  //
   127  //	for every edge x -> y in g, nodeToScc[x] > nodeToScc[y]
   128  func isRevTopSorted(g vtaGraph, nodeToScc map[node]int) bool {
   129  	for n, succs := range g {
   130  		for s := range succs {
   131  			if nodeToScc[n] < nodeToScc[s] {
   132  				return false
   133  			}
   134  		}
   135  	}
   136  	return true
   137  }
   138  
   139  // setName sets name of the function `f` to `name`
   140  // using reflection since setting the name otherwise
   141  // is only possible within the ssa package.
   142  func setName(f *ssa.Function, name string) {
   143  	fi := reflect.ValueOf(f).Elem().FieldByName("name")
   144  	fi = reflect.NewAt(fi.Type(), unsafe.Pointer(fi.UnsafeAddr())).Elem()
   145  	fi.SetString(name)
   146  }
   147  
   148  // testSuite produces a named set of graphs as follows, where
   149  // parentheses contain node types and F nodes stand for function
   150  // nodes whose content is function named F:
   151  //
   152  //	 no-cycles:
   153  //		t0 (A) -> t1 (B) -> t2 (C)
   154  //
   155  //	 trivial-cycle:
   156  //	     <--------    <--------
   157  //	     |       |    |       |
   158  //	     t0 (A) ->    t1 (B) ->
   159  //
   160  //	 circle-cycle:
   161  //		t0 (A) -> t1 (A) -> t2 (B)
   162  //	     |                   |
   163  //	     <--------------------
   164  //
   165  //	 fully-connected:
   166  //		t0 (A) <-> t1 (B)
   167  //	          \    /
   168  //	           t2(C)
   169  //
   170  //	 subsumed-scc:
   171  //		t0 (A) -> t1 (B) -> t2(B) -> t3 (A)
   172  //	     |          |         |        |
   173  //	     |          <---------         |
   174  //	     <-----------------------------
   175  //
   176  //	 more-realistic:
   177  //	     <--------
   178  //	     |        |
   179  //	     t0 (A) -->
   180  //	                           ---------->
   181  //	                          |           |
   182  //	     t1 (A) -> t2 (B) -> F1 -> F2 -> F3 -> F4
   183  //	      |        |          |           |
   184  //	       <-------           <------------
   185  func testSuite() map[string]vtaGraph {
   186  	a := newNamedType("A")
   187  	b := newNamedType("B")
   188  	c := newNamedType("C")
   189  	sig := types.NewSignature(nil, types.NewTuple(), types.NewTuple(), false)
   190  
   191  	f1 := &ssa.Function{Signature: sig}
   192  	setName(f1, "F1")
   193  	f2 := &ssa.Function{Signature: sig}
   194  	setName(f2, "F2")
   195  	f3 := &ssa.Function{Signature: sig}
   196  	setName(f3, "F3")
   197  	f4 := &ssa.Function{Signature: sig}
   198  	setName(f4, "F4")
   199  
   200  	graphs := make(map[string]vtaGraph)
   201  	graphs["no-cycles"] = map[node]map[node]bool{
   202  		newLocal("t0", a): {newLocal("t1", b): true},
   203  		newLocal("t1", b): {newLocal("t2", c): true},
   204  	}
   205  
   206  	graphs["trivial-cycle"] = map[node]map[node]bool{
   207  		newLocal("t0", a): {newLocal("t0", a): true},
   208  		newLocal("t1", b): {newLocal("t1", b): true},
   209  	}
   210  
   211  	graphs["circle-cycle"] = map[node]map[node]bool{
   212  		newLocal("t0", a): {newLocal("t1", a): true},
   213  		newLocal("t1", a): {newLocal("t2", b): true},
   214  		newLocal("t2", b): {newLocal("t0", a): true},
   215  	}
   216  
   217  	graphs["fully-connected"] = map[node]map[node]bool{
   218  		newLocal("t0", a): {newLocal("t1", b): true, newLocal("t2", c): true},
   219  		newLocal("t1", b): {newLocal("t0", a): true, newLocal("t2", c): true},
   220  		newLocal("t2", c): {newLocal("t0", a): true, newLocal("t1", b): true},
   221  	}
   222  
   223  	graphs["subsumed-scc"] = map[node]map[node]bool{
   224  		newLocal("t0", a): {newLocal("t1", b): true},
   225  		newLocal("t1", b): {newLocal("t2", b): true},
   226  		newLocal("t2", b): {newLocal("t1", b): true, newLocal("t3", a): true},
   227  		newLocal("t3", a): {newLocal("t0", a): true},
   228  	}
   229  
   230  	graphs["more-realistic"] = map[node]map[node]bool{
   231  		newLocal("t0", a): {newLocal("t0", a): true},
   232  		newLocal("t1", a): {newLocal("t2", b): true},
   233  		newLocal("t2", b): {newLocal("t1", a): true, function{f1}: true},
   234  		function{f1}:      {function{f2}: true, function{f3}: true},
   235  		function{f2}:      {function{f3}: true},
   236  		function{f3}:      {function{f1}: true, function{f4}: true},
   237  	}
   238  
   239  	return graphs
   240  }
   241  
   242  func TestSCC(t *testing.T) {
   243  	suite := testSuite()
   244  	for _, test := range []struct {
   245  		name  string
   246  		graph vtaGraph
   247  		want  []string
   248  	}{
   249  		// No cycles results in three separate SCCs: {t0}	{t1}	{t2}
   250  		{name: "no-cycles", graph: suite["no-cycles"], want: []string{"Local(t0)", "Local(t1)", "Local(t2)"}},
   251  		// The two trivial self-loop cycles results in: {t0}	{t1}
   252  		{name: "trivial-cycle", graph: suite["trivial-cycle"], want: []string{"Local(t0)", "Local(t1)"}},
   253  		// The circle cycle produce a single SCC: {t0, t1, t2}
   254  		{name: "circle-cycle", graph: suite["circle-cycle"], want: []string{"Local(t0);Local(t1);Local(t2)"}},
   255  		// Similar holds for fully connected SCC: {t0, t1, t2}
   256  		{name: "fully-connected", graph: suite["fully-connected"], want: []string{"Local(t0);Local(t1);Local(t2)"}},
   257  		// Subsumed SCC also has a single SCC: {t0, t1, t2, t3}
   258  		{name: "subsumed-scc", graph: suite["subsumed-scc"], want: []string{"Local(t0);Local(t1);Local(t2);Local(t3)"}},
   259  		// The more realistic example has the following SCCs: {t0}	{t1, t2}	{F1, F2, F3}	{F4}
   260  		{name: "more-realistic", graph: suite["more-realistic"], want: []string{"Local(t0)", "Local(t1);Local(t2)", "Function(F1);Function(F2);Function(F3)", "Function(F4)"}},
   261  	} {
   262  		sccs, _ := scc(test.graph)
   263  		if got := sccString(sccs); !sccEqual(test.want, got) {
   264  			t.Errorf("want %v for graph %v; got %v", test.want, test.name, got)
   265  		}
   266  		if !isRevTopSorted(test.graph, sccs) {
   267  			t.Errorf("%v not topologically sorted", test.name)
   268  		}
   269  	}
   270  }
   271  
   272  func TestPropagation(t *testing.T) {
   273  	suite := testSuite()
   274  	var canon typeutil.Map
   275  	for _, test := range []struct {
   276  		name  string
   277  		graph vtaGraph
   278  		want  map[string]string
   279  	}{
   280  		// No cycles graph pushes type information forward.
   281  		{name: "no-cycles", graph: suite["no-cycles"],
   282  			want: map[string]string{
   283  				"Local(t0)": "A",
   284  				"Local(t1)": "A;B",
   285  				"Local(t2)": "A;B;C",
   286  			},
   287  		},
   288  		// No interesting type flow in trivial cycle graph.
   289  		{name: "trivial-cycle", graph: suite["trivial-cycle"],
   290  			want: map[string]string{
   291  				"Local(t0)": "A",
   292  				"Local(t1)": "B",
   293  			},
   294  		},
   295  		// Circle cycle makes type A and B get propagated everywhere.
   296  		{name: "circle-cycle", graph: suite["circle-cycle"],
   297  			want: map[string]string{
   298  				"Local(t0)": "A;B",
   299  				"Local(t1)": "A;B",
   300  				"Local(t2)": "A;B",
   301  			},
   302  		},
   303  		// Similarly for fully connected graph.
   304  		{name: "fully-connected", graph: suite["fully-connected"],
   305  			want: map[string]string{
   306  				"Local(t0)": "A;B;C",
   307  				"Local(t1)": "A;B;C",
   308  				"Local(t2)": "A;B;C",
   309  			},
   310  		},
   311  		// The outer loop of subsumed-scc pushes A an B through the graph.
   312  		{name: "subsumed-scc", graph: suite["subsumed-scc"],
   313  			want: map[string]string{
   314  				"Local(t0)": "A;B",
   315  				"Local(t1)": "A;B",
   316  				"Local(t2)": "A;B",
   317  				"Local(t3)": "A;B",
   318  			},
   319  		},
   320  		// More realistic graph has a more fine grained flow.
   321  		{name: "more-realistic", graph: suite["more-realistic"],
   322  			want: map[string]string{
   323  				"Local(t0)":    "A",
   324  				"Local(t1)":    "A;B",
   325  				"Local(t2)":    "A;B",
   326  				"Function(F1)": "A;B;F1;F2;F3",
   327  				"Function(F2)": "A;B;F1;F2;F3",
   328  				"Function(F3)": "A;B;F1;F2;F3",
   329  				"Function(F4)": "A;B;F1;F2;F3;F4",
   330  			},
   331  		},
   332  	} {
   333  		if got := nodeToTypeString(propagate(test.graph, &canon)); !reflect.DeepEqual(got, test.want) {
   334  			t.Errorf("want %v for graph %v; got %v", test.want, test.name, got)
   335  		}
   336  	}
   337  }
   338
View as plain text