← Back to branch summary

~vtuson/scopecreator/twitter-template

« back to all changes in this revision

Viewing changes to src/go/src/code.google.com/p/go.tools/go/pointer/util.go

  • Committer: Victor Palau
  • Date: 2015-03-11 14:24:42 UTC
  • Revision ID: vtuson@gmail.com-20150311142442-f2pxp111c8ynv232
public release

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/go/src/code.google.com/p/go.tools/go/pointer/util.go
 
1
// Copyright 2013 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 pointer
 
6
 
 
7
import (
 
8
        "bytes"
 
9
        "fmt"
 
10
 
 
11
        "code.google.com/p/go.tools/go/types"
 
12
)
 
13
 
 
14
// CanPoint reports whether the type T is pointerlike,
 
15
// for the purposes of this analysis.
 
16
func CanPoint(T types.Type) bool {
 
17
        switch T := T.(type) {
 
18
        case *types.Named:
 
19
                if obj := T.Obj(); obj.Name() == "Value" && obj.Pkg().Path() == "reflect" {
 
20
                        return true // treat reflect.Value like interface{}
 
21
                }
 
22
                return CanPoint(T.Underlying())
 
23
 
 
24
        case *types.Pointer, *types.Interface, *types.Map, *types.Chan, *types.Signature, *types.Slice:
 
25
                return true
 
26
        }
 
27
 
 
28
        return false // array struct tuple builtin basic
 
29
}
 
30
 
 
31
// CanHaveDynamicTypes reports whether the type T can "hold" dynamic types,
 
32
// i.e. is an interface (incl. reflect.Type) or a reflect.Value.
 
33
//
 
34
func CanHaveDynamicTypes(T types.Type) bool {
 
35
        switch T := T.(type) {
 
36
        case *types.Named:
 
37
                if obj := T.Obj(); obj.Name() == "Value" && obj.Pkg().Path() == "reflect" {
 
38
                        return true // reflect.Value
 
39
                }
 
40
                return CanHaveDynamicTypes(T.Underlying())
 
41
        case *types.Interface:
 
42
                return true
 
43
        }
 
44
        return false
 
45
}
 
46
 
 
47
// isInterface reports whether T is an interface type.
 
48
func isInterface(T types.Type) bool {
 
49
        _, ok := T.Underlying().(*types.Interface)
 
50
        return ok
 
51
}
 
52
 
 
53
// mustDeref returns the element type of its argument, which must be a
 
54
// pointer; panic ensues otherwise.
 
55
func mustDeref(typ types.Type) types.Type {
 
56
        return typ.Underlying().(*types.Pointer).Elem()
 
57
}
 
58
 
 
59
// deref returns a pointer's element type; otherwise it returns typ.
 
60
func deref(typ types.Type) types.Type {
 
61
        if p, ok := typ.Underlying().(*types.Pointer); ok {
 
62
                return p.Elem()
 
63
        }
 
64
        return typ
 
65
}
 
66
 
 
67
// A fieldInfo describes one subelement (node) of the flattening-out
 
68
// of a type T: the subelement's type and its path from the root of T.
 
69
//
 
70
// For example, for this type:
 
71
//     type line struct{ points []struct{x, y int} }
 
72
// flatten() of the inner struct yields the following []fieldInfo:
 
73
//    struct{ x, y int }                      ""
 
74
//    int                                     ".x"
 
75
//    int                                     ".y"
 
76
// and flatten(line) yields:
 
77
//    struct{ points []struct{x, y int} }     ""
 
78
//    struct{ x, y int }                      ".points[*]"
 
79
//    int                                     ".points[*].x
 
80
//    int                                     ".points[*].y"
 
81
//
 
82
type fieldInfo struct {
 
83
        typ types.Type
 
84
 
 
85
        // op and tail describe the path to the element (e.g. ".a#2.b[*].c").
 
86
        op   interface{} // *Array: true; *Tuple: int; *Struct: *types.Var; *Named: nil
 
87
        tail *fieldInfo
 
88
}
 
89
 
 
90
// path returns a user-friendly string describing the subelement path.
 
91
//
 
92
func (fi *fieldInfo) path() string {
 
93
        var buf bytes.Buffer
 
94
        for p := fi; p != nil; p = p.tail {
 
95
                switch op := p.op.(type) {
 
96
                case bool:
 
97
                        fmt.Fprintf(&buf, "[*]")
 
98
                case int:
 
99
                        fmt.Fprintf(&buf, "#%d", op)
 
100
                case *types.Var:
 
101
                        fmt.Fprintf(&buf, ".%s", op.Name())
 
102
                }
 
103
        }
 
104
        return buf.String()
 
105
}
 
106
 
 
107
// flatten returns a list of directly contained fields in the preorder
 
108
// traversal of the type tree of t.  The resulting elements are all
 
109
// scalars (basic types or pointerlike types), except for struct/array
 
110
// "identity" nodes, whose type is that of the aggregate.
 
111
//
 
112
// reflect.Value is considered pointerlike, similar to interface{}.
 
113
//
 
114
// Callers must not mutate the result.
 
115
//
 
116
func (a *analysis) flatten(t types.Type) []*fieldInfo {
 
117
        fl, ok := a.flattenMemo[t]
 
118
        if !ok {
 
119
                switch t := t.(type) {
 
120
                case *types.Named:
 
121
                        u := t.Underlying()
 
122
                        if isInterface(u) {
 
123
                                // Debuggability hack: don't remove
 
124
                                // the named type from interfaces as
 
125
                                // they're very verbose.
 
126
                                fl = append(fl, &fieldInfo{typ: t})
 
127
                        } else {
 
128
                                fl = a.flatten(u)
 
129
                        }
 
130
 
 
131
                case *types.Basic,
 
132
                        *types.Signature,
 
133
                        *types.Chan,
 
134
                        *types.Map,
 
135
                        *types.Interface,
 
136
                        *types.Slice,
 
137
                        *types.Pointer:
 
138
                        fl = append(fl, &fieldInfo{typ: t})
 
139
 
 
140
                case *types.Array:
 
141
                        fl = append(fl, &fieldInfo{typ: t}) // identity node
 
142
                        for _, fi := range a.flatten(t.Elem()) {
 
143
                                fl = append(fl, &fieldInfo{typ: fi.typ, op: true, tail: fi})
 
144
                        }
 
145
 
 
146
                case *types.Struct:
 
147
                        fl = append(fl, &fieldInfo{typ: t}) // identity node
 
148
                        for i, n := 0, t.NumFields(); i < n; i++ {
 
149
                                f := t.Field(i)
 
150
                                for _, fi := range a.flatten(f.Type()) {
 
151
                                        fl = append(fl, &fieldInfo{typ: fi.typ, op: f, tail: fi})
 
152
                                }
 
153
                        }
 
154
 
 
155
                case *types.Tuple:
 
156
                        // No identity node: tuples are never address-taken.
 
157
                        for i, n := 0, t.Len(); i < n; i++ {
 
158
                                f := t.At(i)
 
159
                                for _, fi := range a.flatten(f.Type()) {
 
160
                                        fl = append(fl, &fieldInfo{typ: fi.typ, op: i, tail: fi})
 
161
                                }
 
162
                        }
 
163
 
 
164
                default:
 
165
                        panic(t)
 
166
                }
 
167
 
 
168
                a.flattenMemo[t] = fl
 
169
        }
 
170
 
 
171
        return fl
 
172
}
 
173
 
 
174
// sizeof returns the number of pointerlike abstractions (nodes) in the type t.
 
175
func (a *analysis) sizeof(t types.Type) uint32 {
 
176
        return uint32(len(a.flatten(t)))
 
177
}
 
178
 
 
179
// shouldTrack reports whether object type T contains (recursively)
 
180
// any fields whose addresses should be tracked.
 
181
func (a *analysis) shouldTrack(T types.Type) bool {
 
182
        if a.track == trackAll {
 
183
                return true // fast path
 
184
        }
 
185
        track, ok := a.trackTypes[T]
 
186
        if !ok {
 
187
                a.trackTypes[T] = true // break cycles conservatively
 
188
                // NB: reflect.Value, reflect.Type are pre-populated to true.
 
189
                for _, fi := range a.flatten(T) {
 
190
                        switch ft := fi.typ.Underlying().(type) {
 
191
                        case *types.Interface, *types.Signature:
 
192
                                track = true // needed for callgraph
 
193
                        case *types.Basic:
 
194
                                // no-op
 
195
                        case *types.Chan:
 
196
                                track = a.track&trackChan != 0 || a.shouldTrack(ft.Elem())
 
197
                        case *types.Map:
 
198
                                track = a.track&trackMap != 0 || a.shouldTrack(ft.Key()) || a.shouldTrack(ft.Elem())
 
199
                        case *types.Slice:
 
200
                                track = a.track&trackSlice != 0 || a.shouldTrack(ft.Elem())
 
201
                        case *types.Pointer:
 
202
                                track = a.track&trackPtr != 0 || a.shouldTrack(ft.Elem())
 
203
                        case *types.Array, *types.Struct:
 
204
                                // No need to look at field types since they will follow (flattened).
 
205
                        default:
 
206
                                // Includes *types.Tuple, which are never address-taken.
 
207
                                panic(ft)
 
208
                        }
 
209
                        if track {
 
210
                                break
 
211
                        }
 
212
                }
 
213
                a.trackTypes[T] = track
 
214
                if !track && a.log != nil {
 
215
                        fmt.Fprintf(a.log, "Type not tracked: %s\n", T)
 
216
                }
 
217
        }
 
218
        return track
 
219
}
 
220
 
 
221
// offsetOf returns the (abstract) offset of field index within struct
 
222
// or tuple typ.
 
223
func (a *analysis) offsetOf(typ types.Type, index int) uint32 {
 
224
        var offset uint32
 
225
        switch t := typ.Underlying().(type) {
 
226
        case *types.Tuple:
 
227
                for i := 0; i < index; i++ {
 
228
                        offset += a.sizeof(t.At(i).Type())
 
229
                }
 
230
        case *types.Struct:
 
231
                offset++ // the node for the struct itself
 
232
                for i := 0; i < index; i++ {
 
233
                        offset += a.sizeof(t.Field(i).Type())
 
234
                }
 
235
        default:
 
236
                panic(fmt.Sprintf("offsetOf(%s : %T)", typ, typ))
 
237
        }
 
238
        return offset
 
239
}
 
240
 
 
241
// sliceToArray returns the type representing the arrays to which
 
242
// slice type slice points.
 
243
func sliceToArray(slice types.Type) *types.Array {
 
244
        return types.NewArray(slice.Underlying().(*types.Slice).Elem(), 1)
 
245
}
 
246
 
 
247
// Node set -------------------------------------------------------------------
 
248
 
 
249
// NB, mutator methods are attached to *nodeset.
 
250
// nodeset may be a reference, but its address matters!
 
251
type nodeset map[nodeid]struct{}
 
252
 
 
253
// ---- Accessors ----
 
254
 
 
255
func (ns nodeset) String() string {
 
256
        var buf bytes.Buffer
 
257
        buf.WriteRune('{')
 
258
        var sep string
 
259
        for n := range ns {
 
260
                fmt.Fprintf(&buf, "%sn%d", sep, n)
 
261
                sep = ", "
 
262
        }
 
263
        buf.WriteRune('}')
 
264
        return buf.String()
 
265
}
 
266
 
 
267
// diff returns the set-difference x - y.  nil => empty.
 
268
//
 
269
// TODO(adonovan): opt: extremely inefficient.  BDDs do this in
 
270
// constant time.  Sparse bitvectors are linear but very fast.
 
271
func (x nodeset) diff(y nodeset) nodeset {
 
272
        var z nodeset
 
273
        for k := range x {
 
274
                if _, ok := y[k]; !ok {
 
275
                        z.add(k)
 
276
                }
 
277
        }
 
278
        return z
 
279
}
 
280
 
 
281
// clone() returns an unaliased copy of x.
 
282
func (x nodeset) clone() nodeset {
 
283
        return x.diff(nil)
 
284
}
 
285
 
 
286
// ---- Mutators ----
 
287
 
 
288
func (ns *nodeset) add(n nodeid) bool {
 
289
        sz := len(*ns)
 
290
        if *ns == nil {
 
291
                *ns = make(nodeset)
 
292
        }
 
293
        (*ns)[n] = struct{}{}
 
294
        return len(*ns) > sz
 
295
}
 
296
 
 
297
func (x *nodeset) addAll(y nodeset) bool {
 
298
        if y == nil {
 
299
                return false
 
300
        }
 
301
        sz := len(*x)
 
302
        if *x == nil {
 
303
                *x = make(nodeset)
 
304
        }
 
305
        for n := range y {
 
306
                (*x)[n] = struct{}{}
 
307
        }
 
308
        return len(*x) > sz
 
309
}
 
310
 
 
311
// Constraint set -------------------------------------------------------------
 
312
 
 
313
type constraintset map[constraint]struct{}
 
314
 
 
315
func (cs *constraintset) add(c constraint) bool {
 
316
        sz := len(*cs)
 
317
        if *cs == nil {
 
318
                *cs = make(constraintset)
 
319
        }
 
320
        (*cs)[c] = struct{}{}
 
321
        return len(*cs) > sz
 
322
}
 
323
 
 
324
// Worklist -------------------------------------------------------------------
 
325
 
 
326
const empty nodeid = 1<<32 - 1
 
327
 
 
328
type worklist interface {
 
329
        add(nodeid)   // Adds a node to the set
 
330
        take() nodeid // Takes a node from the set and returns it, or empty
 
331
}
 
332
 
 
333
// Simple nondeterministic worklist based on a built-in map.
 
334
type mapWorklist struct {
 
335
        set nodeset
 
336
}
 
337
 
 
338
func (w *mapWorklist) add(n nodeid) {
 
339
        w.set[n] = struct{}{}
 
340
}
 
341
 
 
342
func (w *mapWorklist) take() nodeid {
 
343
        for k := range w.set {
 
344
                delete(w.set, k)
 
345
                return k
 
346
        }
 
347
        return empty
 
348
}
 
349
 
 
350
func makeMapWorklist() worklist {
 
351
        return &mapWorklist{make(nodeset)}
 
352
}