| 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 ssa |
| 6 | |
| 7 | // This file defines a number of miscellaneous utility functions. |
| 8 | |
| 9 | import ( |
| 10 | "fmt" |
| 11 | "go/ast" |
| 12 | "go/token" |
| 13 | "go/types" |
| 14 | "io" |
| 15 | "os" |
| 16 | "sync" |
| 17 | |
| 18 | "golang.org/x/tools/go/ast/astutil" |
| 19 | "golang.org/x/tools/go/types/typeutil" |
| 20 | "golang.org/x/tools/internal/typeparams" |
| 21 | ) |
| 22 | |
| 23 | //// Sanity checking utilities |
| 24 | |
| 25 | // assert panics with the mesage msg if p is false. |
| 26 | // Avoid combining with expensive string formatting. |
| 27 | func assert(p bool, msg string) { |
| 28 | if !p { |
| 29 | panic(msg) |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | //// AST utilities |
| 34 | |
| 35 | func unparen(e ast.Expr) ast.Expr { return astutil.Unparen(e) } |
| 36 | |
| 37 | // isBlankIdent returns true iff e is an Ident with name "_". |
| 38 | // They have no associated types.Object, and thus no type. |
| 39 | func isBlankIdent(e ast.Expr) bool { |
| 40 | id, ok := e.(*ast.Ident) |
| 41 | return ok && id.Name == "_" |
| 42 | } |
| 43 | |
| 44 | //// Type utilities. Some of these belong in go/types. |
| 45 | |
| 46 | // isPointer returns true for types whose underlying type is a pointer. |
| 47 | func isPointer(typ types.Type) bool { |
| 48 | _, ok := typ.Underlying().(*types.Pointer) |
| 49 | return ok |
| 50 | } |
| 51 | |
| 52 | // isNonTypeParamInterface reports whether t is an interface type but not a type parameter. |
| 53 | func isNonTypeParamInterface(t types.Type) bool { |
| 54 | return !typeparams.IsTypeParam(t) && types.IsInterface(t) |
| 55 | } |
| 56 | |
| 57 | // isBasic reports whether t is a basic type. |
| 58 | func isBasic(t types.Type) bool { |
| 59 | _, ok := t.(*types.Basic) |
| 60 | return ok |
| 61 | } |
| 62 | |
| 63 | // isString reports whether t is exactly a string type. |
| 64 | func isString(t types.Type) bool { |
| 65 | return isBasic(t) && t.(*types.Basic).Info()&types.IsString != 0 |
| 66 | } |
| 67 | |
| 68 | // isByteSlice reports whether t is []byte. |
| 69 | func isByteSlice(t types.Type) bool { |
| 70 | if b, ok := t.(*types.Slice); ok { |
| 71 | e, _ := b.Elem().(*types.Basic) |
| 72 | return e != nil && e.Kind() == types.Byte |
| 73 | } |
| 74 | return false |
| 75 | } |
| 76 | |
| 77 | // isRuneSlice reports whether t is []rune. |
| 78 | func isRuneSlice(t types.Type) bool { |
| 79 | if b, ok := t.(*types.Slice); ok { |
| 80 | e, _ := b.Elem().(*types.Basic) |
| 81 | return e != nil && e.Kind() == types.Rune |
| 82 | } |
| 83 | return false |
| 84 | } |
| 85 | |
| 86 | // isBasicConvType returns true when a type set can be |
| 87 | // one side of a Convert operation. This is when: |
| 88 | // - All are basic, []byte, or []rune. |
| 89 | // - At least 1 is basic. |
| 90 | // - At most 1 is []byte or []rune. |
| 91 | func isBasicConvTypes(tset termList) bool { |
| 92 | basics := 0 |
| 93 | all := underIs(tset, func(t types.Type) bool { |
| 94 | if isBasic(t) { |
| 95 | basics++ |
| 96 | return true |
| 97 | } |
| 98 | return isByteSlice(t) || isRuneSlice(t) |
| 99 | }) |
| 100 | return all && basics >= 1 && tset.Len()-basics <= 1 |
| 101 | } |
| 102 | |
| 103 | // deref returns a pointer's element type; otherwise it returns typ. |
| 104 | func deref(typ types.Type) types.Type { |
| 105 | if p, ok := typ.Underlying().(*types.Pointer); ok { |
| 106 | return p.Elem() |
| 107 | } |
| 108 | return typ |
| 109 | } |
| 110 | |
| 111 | // recvType returns the receiver type of method obj. |
| 112 | func recvType(obj *types.Func) types.Type { |
| 113 | return obj.Type().(*types.Signature).Recv().Type() |
| 114 | } |
| 115 | |
| 116 | // isUntyped returns true for types that are untyped. |
| 117 | func isUntyped(typ types.Type) bool { |
| 118 | b, ok := typ.(*types.Basic) |
| 119 | return ok && b.Info()&types.IsUntyped != 0 |
| 120 | } |
| 121 | |
| 122 | // logStack prints the formatted "start" message to stderr and |
| 123 | // returns a closure that prints the corresponding "end" message. |
| 124 | // Call using 'defer logStack(...)()' to show builder stack on panic. |
| 125 | // Don't forget trailing parens! |
| 126 | func logStack(format string, args ...interface{}) func() { |
| 127 | msg := fmt.Sprintf(format, args...) |
| 128 | io.WriteString(os.Stderr, msg) |
| 129 | io.WriteString(os.Stderr, "\n") |
| 130 | return func() { |
| 131 | io.WriteString(os.Stderr, msg) |
| 132 | io.WriteString(os.Stderr, " end\n") |
| 133 | } |
| 134 | } |
| 135 | |
| 136 | // newVar creates a 'var' for use in a types.Tuple. |
| 137 | func newVar(name string, typ types.Type) *types.Var { |
| 138 | return types.NewParam(token.NoPos, nil, name, typ) |
| 139 | } |
| 140 | |
| 141 | // anonVar creates an anonymous 'var' for use in a types.Tuple. |
| 142 | func anonVar(typ types.Type) *types.Var { |
| 143 | return newVar("", typ) |
| 144 | } |
| 145 | |
| 146 | var lenResults = types.NewTuple(anonVar(tInt)) |
| 147 | |
| 148 | // makeLen returns the len builtin specialized to type func(T)int. |
| 149 | func makeLen(T types.Type) *Builtin { |
| 150 | lenParams := types.NewTuple(anonVar(T)) |
| 151 | return &Builtin{ |
| 152 | name: "len", |
| 153 | sig: types.NewSignature(nil, lenParams, lenResults, false), |
| 154 | } |
| 155 | } |
| 156 | |
| 157 | // nonbasicTypes returns a list containing all of the types T in ts that are non-basic. |
| 158 | func nonbasicTypes(ts []types.Type) []types.Type { |
| 159 | if len(ts) == 0 { |
| 160 | return nil |
| 161 | } |
| 162 | added := make(map[types.Type]bool) // additionally filter duplicates |
| 163 | var filtered []types.Type |
| 164 | for _, T := range ts { |
| 165 | if !isBasic(T) { |
| 166 | if !added[T] { |
| 167 | added[T] = true |
| 168 | filtered = append(filtered, T) |
| 169 | } |
| 170 | } |
| 171 | } |
| 172 | return filtered |
| 173 | } |
| 174 | |
| 175 | // receiverTypeArgs returns the type arguments to a function's reciever. |
| 176 | // Returns an empty list if obj does not have a reciever or its reciever does not have type arguments. |
| 177 | func receiverTypeArgs(obj *types.Func) []types.Type { |
| 178 | rtype := recvType(obj) |
| 179 | if rtype == nil { |
| 180 | return nil |
| 181 | } |
| 182 | if isPointer(rtype) { |
| 183 | rtype = rtype.(*types.Pointer).Elem() |
| 184 | } |
| 185 | named, ok := rtype.(*types.Named) |
| 186 | if !ok { |
| 187 | return nil |
| 188 | } |
| 189 | ts := typeparams.NamedTypeArgs(named) |
| 190 | if ts.Len() == 0 { |
| 191 | return nil |
| 192 | } |
| 193 | targs := make([]types.Type, ts.Len()) |
| 194 | for i := 0; i < ts.Len(); i++ { |
| 195 | targs[i] = ts.At(i) |
| 196 | } |
| 197 | return targs |
| 198 | } |
| 199 | |
| 200 | // recvAsFirstArg takes a method signature and returns a function |
| 201 | // signature with receiver as the first parameter. |
| 202 | func recvAsFirstArg(sig *types.Signature) *types.Signature { |
| 203 | params := make([]*types.Var, 0, 1+sig.Params().Len()) |
| 204 | params = append(params, sig.Recv()) |
| 205 | for i := 0; i < sig.Params().Len(); i++ { |
| 206 | params = append(params, sig.Params().At(i)) |
| 207 | } |
| 208 | return typeparams.NewSignatureType(nil, nil, nil, types.NewTuple(params...), sig.Results(), sig.Variadic()) |
| 209 | } |
| 210 | |
| 211 | // instance returns whether an expression is a simple or qualified identifier |
| 212 | // that is a generic instantiation. |
| 213 | func instance(info *types.Info, expr ast.Expr) bool { |
| 214 | // Compare the logic here against go/types.instantiatedIdent, |
| 215 | // which also handles *IndexExpr and *IndexListExpr. |
| 216 | var id *ast.Ident |
| 217 | switch x := expr.(type) { |
| 218 | case *ast.Ident: |
| 219 | id = x |
| 220 | case *ast.SelectorExpr: |
| 221 | id = x.Sel |
| 222 | default: |
| 223 | return false |
| 224 | } |
| 225 | _, ok := typeparams.GetInstances(info)[id] |
| 226 | return ok |
| 227 | } |
| 228 | |
| 229 | // instanceArgs returns the Instance[id].TypeArgs as a slice. |
| 230 | func instanceArgs(info *types.Info, id *ast.Ident) []types.Type { |
| 231 | targList := typeparams.GetInstances(info)[id].TypeArgs |
| 232 | if targList == nil { |
| 233 | return nil |
| 234 | } |
| 235 | |
| 236 | targs := make([]types.Type, targList.Len()) |
| 237 | for i, n := 0, targList.Len(); i < n; i++ { |
| 238 | targs[i] = targList.At(i) |
| 239 | } |
| 240 | return targs |
| 241 | } |
| 242 | |
| 243 | // Mapping of a type T to a canonical instance C s.t. types.Indentical(T, C). |
| 244 | // Thread-safe. |
| 245 | type canonizer struct { |
| 246 | mu sync.Mutex |
| 247 | types typeutil.Map // map from type to a canonical instance |
| 248 | lists typeListMap // map from a list of types to a canonical instance |
| 249 | } |
| 250 | |
| 251 | func newCanonizer() *canonizer { |
| 252 | c := &canonizer{} |
| 253 | h := typeutil.MakeHasher() |
| 254 | c.types.SetHasher(h) |
| 255 | c.lists.hasher = h |
| 256 | return c |
| 257 | } |
| 258 | |
| 259 | // List returns a canonical representative of a list of types. |
| 260 | // Representative of the empty list is nil. |
| 261 | func (c *canonizer) List(ts []types.Type) *typeList { |
| 262 | if len(ts) == 0 { |
| 263 | return nil |
| 264 | } |
| 265 | |
| 266 | c.mu.Lock() |
| 267 | defer c.mu.Unlock() |
| 268 | return c.lists.rep(ts) |
| 269 | } |
| 270 | |
| 271 | // Type returns a canonical representative of type T. |
| 272 | func (c *canonizer) Type(T types.Type) types.Type { |
| 273 | c.mu.Lock() |
| 274 | defer c.mu.Unlock() |
| 275 | |
| 276 | if r := c.types.At(T); r != nil { |
| 277 | return r.(types.Type) |
| 278 | } |
| 279 | c.types.Set(T, T) |
| 280 | return T |
| 281 | } |
| 282 | |
| 283 | // A type for representating an canonized list of types. |
| 284 | type typeList []types.Type |
| 285 | |
| 286 | func (l *typeList) identical(ts []types.Type) bool { |
| 287 | if l == nil { |
| 288 | return len(ts) == 0 |
| 289 | } |
| 290 | n := len(*l) |
| 291 | if len(ts) != n { |
| 292 | return false |
| 293 | } |
| 294 | for i, left := range *l { |
| 295 | right := ts[i] |
| 296 | if !types.Identical(left, right) { |
| 297 | return false |
| 298 | } |
| 299 | } |
| 300 | return true |
| 301 | } |
| 302 | |
| 303 | type typeListMap struct { |
| 304 | hasher typeutil.Hasher |
| 305 | buckets map[uint32][]*typeList |
| 306 | } |
| 307 | |
| 308 | // rep returns a canonical representative of a slice of types. |
| 309 | func (m *typeListMap) rep(ts []types.Type) *typeList { |
| 310 | if m == nil || len(ts) == 0 { |
| 311 | return nil |
| 312 | } |
| 313 | |
| 314 | if m.buckets == nil { |
| 315 | m.buckets = make(map[uint32][]*typeList) |
| 316 | } |
| 317 | |
| 318 | h := m.hash(ts) |
| 319 | bucket := m.buckets[h] |
| 320 | for _, l := range bucket { |
| 321 | if l.identical(ts) { |
| 322 | return l |
| 323 | } |
| 324 | } |
| 325 | |
| 326 | // not present. create a representative. |
| 327 | cp := make(typeList, len(ts)) |
| 328 | copy(cp, ts) |
| 329 | rep := &cp |
| 330 | |
| 331 | m.buckets[h] = append(bucket, rep) |
| 332 | return rep |
| 333 | } |
| 334 | |
| 335 | func (m *typeListMap) hash(ts []types.Type) uint32 { |
| 336 | if m == nil { |
| 337 | return 0 |
| 338 | } |
| 339 | // Some smallish prime far away from typeutil.Hash. |
| 340 | n := len(ts) |
| 341 | h := uint32(13619) + 2*uint32(n) |
| 342 | for i := 0; i < n; i++ { |
| 343 | h += 3 * m.hasher.Hash(ts[i]) |
| 344 | } |
| 345 | return h |
| 346 | } |
| 347 | |
| 348 | // instantiateMethod instantiates m with targs and returns a canonical representative for this method. |
| 349 | func (canon *canonizer) instantiateMethod(m *types.Func, targs []types.Type, ctxt *typeparams.Context) *types.Func { |
| 350 | recv := recvType(m) |
| 351 | if p, ok := recv.(*types.Pointer); ok { |
| 352 | recv = p.Elem() |
| 353 | } |
| 354 | named := recv.(*types.Named) |
| 355 | inst, err := typeparams.Instantiate(ctxt, typeparams.NamedTypeOrigin(named), targs, false) |
| 356 | if err != nil { |
| 357 | panic(err) |
| 358 | } |
| 359 | rep := canon.Type(inst) |
| 360 | obj, _, _ := types.LookupFieldOrMethod(rep, true, m.Pkg(), m.Name()) |
| 361 | return obj.(*types.Func) |
| 362 | } |
| 363 |
Members