dependencies.go 9.14 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
package transform

import (
	"bytes"
	"fmt"
	"go/ast"
	"io"
	"io/ioutil"
	"log"
	"os"
)

Hugo Moreau's avatar
Hugo Moreau committed
13
// Variable details according to a function scope.
14
type VarDetails struct {
Hugo Moreau's avatar
Hugo Moreau committed
15
16
	UsedStmt        []int         // Used Statements.
	VarDependencies []*ast.Object // Variables dependencies.
17
18
}

Hugo Moreau's avatar
Hugo Moreau committed
19
// Function details.
20
type FuncDetails struct {
Hugo Moreau's avatar
Hugo Moreau committed
21
22
23
24
	BodyStmt     []ast.Stmt                  // Functions Statements list.
	ToIgnoreStmt []int                       // To be ignored statements.
	Parameters   []*ast.Field                // Functions parameters.
	Variables    map[*ast.Object]*VarDetails // Variable Details map.
25
26
27
	Visited      bool
}

Hugo Moreau's avatar
Hugo Moreau committed
28
29
30
// Function informations, only used in the Pre traversal.
// This struct is only used in order to collect informations,
// once a statement is visited we store its informations in FuncDetails struct.
31
type FuncInfos struct {
Hugo Moreau's avatar
Hugo Moreau committed
32
33
34
35
	Body      *ast.BlockStmt // Function BlockStmt.
	Obj       *ast.Object    // Function Object.
	Index     int            // Current Statement Index.
	Variables []*ast.Object  // All used variables in current statement.
36
37
}

Hugo Moreau's avatar
Hugo Moreau committed
38
39
// Dependencies struct.
// It hold all our informations in the Pre and Post traversal.
40
type Dependencies struct {
Hugo Moreau's avatar
Hugo Moreau committed
41
42
43
	currentFunc FuncInfos                    // Current Function
	FuncsVar    map[*ast.Object]*FuncDetails // All functions informations.
	GlobalVar   []*ast.Object                // Global variables list.
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
}

func findObj(objList []*ast.Object, obj *ast.Object) bool {
	for _, val := range objList {
		if val == obj {
			return true
		}
	}
	return false
}

func (t *Dependencies) isGlobalVar(obj *ast.Object) bool {
	return findObj(t.GlobalVar, obj)
}

// Init all Dependencies stuct's map at the begining of the transform.
func (t *Dependencies) init(file *ast.File) {
	t.FuncsVar = make(map[*ast.Object]*FuncDetails)
	for _, val := range file.Scope.Objects {
		if val.Kind == ast.Var {
			t.GlobalVar = append(t.GlobalVar, val)
		} else if val.Kind == ast.Fun {
			t.FuncsVar[val] = &FuncDetails{
				ToIgnoreStmt: []int{},
				Variables:    make(map[*ast.Object]*VarDetails),
				Visited:      false,
			}
			switch decl := val.Decl.(type) {
			case *ast.FuncDecl:
				t.FuncsVar[val].Parameters = decl.Type.Params.List
				t.FuncsVar[val].BodyStmt = decl.Body.List
			}
		}
	}
}

func (infos *FuncInfos) getIndex() int {
	return infos.Index - 1
}

Hugo Moreau's avatar
Hugo Moreau committed
84
85
// Convert FuncInfos into FuncDetails once a statement has been visited.
// Variables dependencies are generated if they are in the same statement.
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
func (infos *FuncInfos) convert(funcsVar map[*ast.Object]*FuncDetails) {
	if len(infos.Variables) == 0 || infos.Index <= 0 || infos.Obj == nil {
		return
	}
	for _, val := range infos.Variables {
		if _, ok := funcsVar[infos.Obj].Variables[val]; !ok {
			funcsVar[infos.Obj].Variables[val] = &VarDetails{
				UsedStmt:        []int{},
				VarDependencies: []*ast.Object{},
			}
		}
		funcsVar[infos.Obj].Variables[val].UsedStmt =
			append(funcsVar[infos.Obj].Variables[val].UsedStmt, infos.getIndex())
		for _, toAdd := range infos.Variables {
			if toAdd != val &&
				!findObj(funcsVar[infos.Obj].Variables[val].VarDependencies, toAdd) {
				funcsVar[infos.Obj].Variables[val].VarDependencies =
					append(funcsVar[infos.Obj].Variables[val].VarDependencies, toAdd)
			}
		}
	}
}

Hugo Moreau's avatar
Hugo Moreau committed
109
110
111
// Register all our variables in funcsVar using convert function,
// and increment our index to go to next statement.
// If the given index is incorect, it return false, true otherwise.
112
113
114
115
116
117
118
119
120
121
122
func (infos *FuncInfos) registerVariables(funcsVar map[*ast.Object]*FuncDetails, node ast.Node) bool {
	if infos.Index < len(infos.Body.List) &&
		node == infos.Body.List[infos.Index] {
		infos.convert(funcsVar)
		infos.Index++
		infos.Variables = []*ast.Object{}
		return true
	}
	return false
}

Hugo Moreau's avatar
Hugo Moreau committed
123
// Init all Func Informations as it is the beginning of the function.
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
func (infos *FuncInfos) init(funcDecl *ast.FuncDecl) {
	infos.Obj = funcDecl.Name.Obj
	infos.Body = funcDecl.Body
	infos.Index = 0
	infos.Variables = []*ast.Object{}
}

// Pre traversal applies the transformation.
func (t *Dependencies) Pre(meta *Meta, v *Visitor) bool {
	c := v.Cursor()
	if t.currentFunc.Obj != nil {
		t.currentFunc.registerVariables(t.FuncsVar, c.Node())
	}
	switch node := c.Node().(type) {
	case *ast.File:
		t.init(node)
	case *ast.FuncDecl:
		t.FuncsVar[node.Name.Obj].Visited = true
		t.currentFunc.convert(t.FuncsVar)
		t.currentFunc.init(node)
	case *ast.GenDecl:
		switch c.Parent().(type) {
		case *ast.File:
			t.currentFunc.Body = nil
			t.currentFunc.Obj = nil
		}
	case *ast.Ident:
		if t.currentFunc.Obj == nil {
			return true
		}
		if node.Obj != nil && !findObj(t.currentFunc.Variables, node.Obj) {
			if node.Obj.Kind == ast.Var {
				t.currentFunc.Variables = append(t.currentFunc.Variables, node.Obj)
			}
		}
	}
	return true
}

// Post traversal applies the transformation.
func (t *Dependencies) Post(meta *Meta, v *Visitor) bool {
	c := v.Cursor()
	switch c.Node().(type) {
	case *ast.File:
		if t.currentFunc.Obj != nil {
			t.currentFunc.convert(t.FuncsVar)
		}
		redirectFuncOutput("main.dot", t.PrintGraph)
		fmt.Println("All infomations are stored in `main.dot` file, you may use GraphViz:")
		fmt.Println("  dot -Tpng main.dot -o main.png")
		fmt.Println("Further informations here:")
		t.Print()
	}
	return true
}

// Temporary function to redirect stdout.
func redirectFuncOutput(filename string, fun func()) {
	old := os.Stdout
	r, w, _ := os.Pipe()
	os.Stdout = w
	fun()
	outC := make(chan string)
	go func() {
		var buf bytes.Buffer
		io.Copy(&buf, r)
		outC <- buf.String()
	}()

	w.Close()
	os.Stdout = old
	out := <-outC
	err := ioutil.WriteFile(filename, []byte(out), 0644)
	if err != nil {
		log.Fatal(err)
	}
}

// Print all Dependencies informations, debug purpose only.
func (t *Dependencies) Print() {
	fmt.Println("Global variables:")
	for _, val := range t.GlobalVar {
		fmt.Printf(" - Name: %s, Address: %p\n", val.Name, val)
	}
	fmt.Println("Functions informations:")
	for key, val := range t.FuncsVar {
		fmt.Println(" - Name:", key.Name)
		fmt.Println("   - Nb Statements:", len(val.BodyStmt))
		fmt.Println("   - Parameters:")
		for _, value := range val.Parameters {
			for _, name := range value.Names {
				fmt.Printf("     - Name: %s, Address: %p\n", name.Obj.Name, name.Obj)
			}
		}
		fmt.Println("   - Variables:")
		for key2, val2 := range val.Variables {
			fmt.Printf("     - Name: %s, Address: %p\n", key2.Name, key2)
			fmt.Println("       - Used Statements: ", val2.UsedStmt, "Ratio:", len(val2.UsedStmt), "/", len(val.BodyStmt))
			fmt.Println("       - Variables dependencies:")
			for _, value := range val2.VarDependencies {
				fmt.Printf("         - Name: %s, Address: %p\n", value.Name, value)
			}
		}
	}
}

Hugo Moreau's avatar
Hugo Moreau committed
230
// Output a GraphViz graph.
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
func (t *Dependencies) PrintGraph() {
	indent := &Indent{}
	fmt.Println("graph G {")
	fmt.Printf("%*s%s\n", indent.indent().N, "", "label=\"package main\";")
	fmt.Printf("%*s%s\n", indent.N, "", "compound=true;")

	// Global variables
	fmt.Printf("%*s%s\n", indent.N, "", "subgraph cluster_0 {")
	fmt.Printf("%*s%s\n", indent.indent().N, "", "label=\"global variables\"")
	fmt.Printf("%*s%s\n", indent.N, "", "color=blue")
	for _, val := range t.GlobalVar {
		fmt.Printf("%*s%#p[label=\"%s\"]\n", indent.N, "", val, val.Name)
	}
	fmt.Printf("%*s%s\n", indent.unindent().N, "", "}")

	// Function variables
	cluster := 1
	double := []Pair{}
	for key, val := range t.FuncsVar {
		fmt.Printf("%*ssubgraph cluster_%d {\n", indent.N, "", cluster)
		fmt.Printf("%*slabel=\"%s\"\n", indent.indent().N, "", "func "+key.Name)
		fmt.Printf("%*s%s\n", indent.N, "", "color=lightgray")
		fmt.Printf("%*s%s\n", indent.N, "", "func_"+key.Name+"[style=invis,shape=point]")
		for _, value := range val.Parameters {
			for _, name := range value.Names {
				fmt.Printf("%*s%#p[label=\"%s\"]\n", indent.N, "", name.Obj, name.Obj.Name)
			}
		}
		for key2, val2 := range val.Variables {
			fmt.Printf("%*s%#p[label=\"%s\"]\n", indent.N, "", key2, key2.Name)
			x := fmt.Sprintf("%#p", key2)
			if len(val2.VarDependencies) == 0 && t.isGlobalVar(key2) {
				if !findPair(double, Pair{x, x, key.Name}) {
					fmt.Printf("%*s%#p -- %s[color=indigo,lhead=\"cluster_%d\"]\n", indent.N, "", key2, "func_"+key.Name, cluster)
					double = append(double, Pair{x, x, key.Name})
				}
			}
			for _, value := range val2.VarDependencies {
				y := fmt.Sprintf("%#p", value)
				if !findPair(double, Pair{x, y, key.Name}) {
					if t.isGlobalVar(key2) && t.isGlobalVar(value) {
						fmt.Printf("%*s%#p -- %#p[label=\"%s\",color=indigo,fontcolor=indigo]\n", indent.N, "", key2, value, "func "+key.Name)
					} else {
						fmt.Printf("%*s%#p -- %#p[color=indigo]\n", indent.N, "", key2, value)
					}
					double = append(double, Pair{x, y, key.Name})
				}
			}
		}
		fmt.Printf("%*s}\n", indent.unindent().N, "")
		cluster++
	}
	fmt.Println("}")
}

type Pair struct {
	x, y, z string
}

func findPair(pairList []Pair, pair Pair) bool {
	for _, val := range pairList {
		if val.x == pair.x && val.y == pair.y && pair.z == val.z {
			return true
		} else if val.y == pair.x && val.x == pair.y && pair.z == val.z {
			return true
		}
	}
	return false
}

type Indent struct {
	N int
}

func (i *Indent) indent() *Indent {
	i.N += 4
	return i
}

func (i *Indent) unindent() *Indent {
	if i.N <= 0 {
		i.N = 0
		return i
	}
	i.N -= 4
	return i
}