1// Copyright 2018 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 objectpath defines a naming scheme for types.Objects 6// (that is, named entities in Go programs) relative to their enclosing 7// package. 8// 9// Type-checker objects are canonical, so they are usually identified by 10// their address in memory (a pointer), but a pointer has meaning only 11// within one address space. By contrast, objectpath names allow the 12// identity of an object to be sent from one program to another, 13// establishing a correspondence between types.Object variables that are 14// distinct but logically equivalent. 15// 16// A single object may have multiple paths. In this example, 17// type A struct{ X int } 18// type B A 19// the field X has two paths due to its membership of both A and B. 20// The For(obj) function always returns one of these paths, arbitrarily 21// but consistently. 22package objectpath 23 24import ( 25 "fmt" 26 "strconv" 27 "strings" 28 29 "go/types" 30) 31 32// A Path is an opaque name that identifies a types.Object 33// relative to its package. Conceptually, the name consists of a 34// sequence of destructuring operations applied to the package scope 35// to obtain the original object. 36// The name does not include the package itself. 37type Path string 38 39// Encoding 40// 41// An object path is a textual and (with training) human-readable encoding 42// of a sequence of destructuring operators, starting from a types.Package. 43// The sequences represent a path through the package/object/type graph. 44// We classify these operators by their type: 45// 46// PO package->object Package.Scope.Lookup 47// OT object->type Object.Type 48// TT type->type Type.{Elem,Key,Params,Results,Underlying} [EKPRU] 49// TO type->object Type.{At,Field,Method,Obj} [AFMO] 50// 51// All valid paths start with a package and end at an object 52// and thus may be defined by the regular language: 53// 54// objectpath = PO (OT TT* TO)* 55// 56// The concrete encoding follows directly: 57// - The only PO operator is Package.Scope.Lookup, which requires an identifier. 58// - The only OT operator is Object.Type, 59// which we encode as '.' because dot cannot appear in an identifier. 60// - The TT operators are encoded as [EKPRU]. 61// - The OT operators are encoded as [AFMO]; 62// three of these (At,Field,Method) require an integer operand, 63// which is encoded as a string of decimal digits. 64// These indices are stable across different representations 65// of the same package, even source and export data. 66// 67// In the example below, 68// 69// package p 70// 71// type T interface { 72// f() (a string, b struct{ X int }) 73// } 74// 75// field X has the path "T.UM0.RA1.F0", 76// representing the following sequence of operations: 77// 78// p.Lookup("T") T 79// .Type().Underlying().Method(0). f 80// .Type().Results().At(1) b 81// .Type().Field(0) X 82// 83// The encoding is not maximally compact---every R or P is 84// followed by an A, for example---but this simplifies the 85// encoder and decoder. 86// 87const ( 88 // object->type operators 89 opType = '.' // .Type() (Object) 90 91 // type->type operators 92 opElem = 'E' // .Elem() (Pointer, Slice, Array, Chan, Map) 93 opKey = 'K' // .Key() (Map) 94 opParams = 'P' // .Params() (Signature) 95 opResults = 'R' // .Results() (Signature) 96 opUnderlying = 'U' // .Underlying() (Named) 97 98 // type->object operators 99 opAt = 'A' // .At(i) (Tuple) 100 opField = 'F' // .Field(i) (Struct) 101 opMethod = 'M' // .Method(i) (Named or Interface; not Struct: "promoted" names are ignored) 102 opObj = 'O' // .Obj() (Named) 103) 104 105// The For function returns the path to an object relative to its package, 106// or an error if the object is not accessible from the package's Scope. 107// 108// The For function guarantees to return a path only for the following objects: 109// - package-level types 110// - exported package-level non-types 111// - methods 112// - parameter and result variables 113// - struct fields 114// These objects are sufficient to define the API of their package. 115// The objects described by a package's export data are drawn from this set. 116// 117// For does not return a path for predeclared names, imported package 118// names, local names, and unexported package-level names (except 119// types). 120// 121// Example: given this definition, 122// 123// package p 124// 125// type T interface { 126// f() (a string, b struct{ X int }) 127// } 128// 129// For(X) would return a path that denotes the following sequence of operations: 130// 131// p.Scope().Lookup("T") (TypeName T) 132// .Type().Underlying().Method(0). (method Func f) 133// .Type().Results().At(1) (field Var b) 134// .Type().Field(0) (field Var X) 135// 136// where p is the package (*types.Package) to which X belongs. 137func For(obj types.Object) (Path, error) { 138 pkg := obj.Pkg() 139 140 // This table lists the cases of interest. 141 // 142 // Object Action 143 // ------ ------ 144 // nil reject 145 // builtin reject 146 // pkgname reject 147 // label reject 148 // var 149 // package-level accept 150 // func param/result accept 151 // local reject 152 // struct field accept 153 // const 154 // package-level accept 155 // local reject 156 // func 157 // package-level accept 158 // init functions reject 159 // concrete method accept 160 // interface method accept 161 // type 162 // package-level accept 163 // local reject 164 // 165 // The only accessible package-level objects are members of pkg itself. 166 // 167 // The cases are handled in four steps: 168 // 169 // 1. reject nil and builtin 170 // 2. accept package-level objects 171 // 3. reject obviously invalid objects 172 // 4. search the API for the path to the param/result/field/method. 173 174 // 1. reference to nil or builtin? 175 if pkg == nil { 176 return "", fmt.Errorf("predeclared %s has no path", obj) 177 } 178 scope := pkg.Scope() 179 180 // 2. package-level object? 181 if scope.Lookup(obj.Name()) == obj { 182 // Only exported objects (and non-exported types) have a path. 183 // Non-exported types may be referenced by other objects. 184 if _, ok := obj.(*types.TypeName); !ok && !obj.Exported() { 185 return "", fmt.Errorf("no path for non-exported %v", obj) 186 } 187 return Path(obj.Name()), nil 188 } 189 190 // 3. Not a package-level object. 191 // Reject obviously non-viable cases. 192 switch obj := obj.(type) { 193 case *types.Const, // Only package-level constants have a path. 194 *types.TypeName, // Only package-level types have a path. 195 *types.Label, // Labels are function-local. 196 *types.PkgName: // PkgNames are file-local. 197 return "", fmt.Errorf("no path for %v", obj) 198 199 case *types.Var: 200 // Could be: 201 // - a field (obj.IsField()) 202 // - a func parameter or result 203 // - a local var. 204 // Sadly there is no way to distinguish 205 // a param/result from a local 206 // so we must proceed to the find. 207 208 case *types.Func: 209 // A func, if not package-level, must be a method. 210 if recv := obj.Type().(*types.Signature).Recv(); recv == nil { 211 return "", fmt.Errorf("func is not a method: %v", obj) 212 } 213 // TODO(adonovan): opt: if the method is concrete, 214 // do a specialized version of the rest of this function so 215 // that it's O(1) not O(|scope|). Basically 'find' is needed 216 // only for struct fields and interface methods. 217 218 default: 219 panic(obj) 220 } 221 222 // 4. Search the API for the path to the var (field/param/result) or method. 223 224 // First inspect package-level named types. 225 // In the presence of path aliases, these give 226 // the best paths because non-types may 227 // refer to types, but not the reverse. 228 empty := make([]byte, 0, 48) // initial space 229 names := scope.Names() 230 for _, name := range names { 231 o := scope.Lookup(name) 232 tname, ok := o.(*types.TypeName) 233 if !ok { 234 continue // handle non-types in second pass 235 } 236 237 path := append(empty, name...) 238 path = append(path, opType) 239 240 T := o.Type() 241 242 if tname.IsAlias() { 243 // type alias 244 if r := find(obj, T, path); r != nil { 245 return Path(r), nil 246 } 247 } else { 248 // defined (named) type 249 if r := find(obj, T.Underlying(), append(path, opUnderlying)); r != nil { 250 return Path(r), nil 251 } 252 } 253 } 254 255 // Then inspect everything else: 256 // non-types, and declared methods of defined types. 257 for _, name := range names { 258 o := scope.Lookup(name) 259 path := append(empty, name...) 260 if _, ok := o.(*types.TypeName); !ok { 261 if o.Exported() { 262 // exported non-type (const, var, func) 263 if r := find(obj, o.Type(), append(path, opType)); r != nil { 264 return Path(r), nil 265 } 266 } 267 continue 268 } 269 270 // Inspect declared methods of defined types. 271 if T, ok := o.Type().(*types.Named); ok { 272 path = append(path, opType) 273 for i := 0; i < T.NumMethods(); i++ { 274 m := T.Method(i) 275 path2 := appendOpArg(path, opMethod, i) 276 if m == obj { 277 return Path(path2), nil // found declared method 278 } 279 if r := find(obj, m.Type(), append(path2, opType)); r != nil { 280 return Path(r), nil 281 } 282 } 283 } 284 } 285 286 return "", fmt.Errorf("can't find path for %v in %s", obj, pkg.Path()) 287} 288 289func appendOpArg(path []byte, op byte, arg int) []byte { 290 path = append(path, op) 291 path = strconv.AppendInt(path, int64(arg), 10) 292 return path 293} 294 295// find finds obj within type T, returning the path to it, or nil if not found. 296func find(obj types.Object, T types.Type, path []byte) []byte { 297 switch T := T.(type) { 298 case *types.Basic, *types.Named: 299 // Named types belonging to pkg were handled already, 300 // so T must belong to another package. No path. 301 return nil 302 case *types.Pointer: 303 return find(obj, T.Elem(), append(path, opElem)) 304 case *types.Slice: 305 return find(obj, T.Elem(), append(path, opElem)) 306 case *types.Array: 307 return find(obj, T.Elem(), append(path, opElem)) 308 case *types.Chan: 309 return find(obj, T.Elem(), append(path, opElem)) 310 case *types.Map: 311 if r := find(obj, T.Key(), append(path, opKey)); r != nil { 312 return r 313 } 314 return find(obj, T.Elem(), append(path, opElem)) 315 case *types.Signature: 316 if r := find(obj, T.Params(), append(path, opParams)); r != nil { 317 return r 318 } 319 return find(obj, T.Results(), append(path, opResults)) 320 case *types.Struct: 321 for i := 0; i < T.NumFields(); i++ { 322 f := T.Field(i) 323 path2 := appendOpArg(path, opField, i) 324 if f == obj { 325 return path2 // found field var 326 } 327 if r := find(obj, f.Type(), append(path2, opType)); r != nil { 328 return r 329 } 330 } 331 return nil 332 case *types.Tuple: 333 for i := 0; i < T.Len(); i++ { 334 v := T.At(i) 335 path2 := appendOpArg(path, opAt, i) 336 if v == obj { 337 return path2 // found param/result var 338 } 339 if r := find(obj, v.Type(), append(path2, opType)); r != nil { 340 return r 341 } 342 } 343 return nil 344 case *types.Interface: 345 for i := 0; i < T.NumMethods(); i++ { 346 m := T.Method(i) 347 path2 := appendOpArg(path, opMethod, i) 348 if m == obj { 349 return path2 // found interface method 350 } 351 if r := find(obj, m.Type(), append(path2, opType)); r != nil { 352 return r 353 } 354 } 355 return nil 356 } 357 panic(T) 358} 359 360// Object returns the object denoted by path p within the package pkg. 361func Object(pkg *types.Package, p Path) (types.Object, error) { 362 if p == "" { 363 return nil, fmt.Errorf("empty path") 364 } 365 366 pathstr := string(p) 367 var pkgobj, suffix string 368 if dot := strings.IndexByte(pathstr, opType); dot < 0 { 369 pkgobj = pathstr 370 } else { 371 pkgobj = pathstr[:dot] 372 suffix = pathstr[dot:] // suffix starts with "." 373 } 374 375 obj := pkg.Scope().Lookup(pkgobj) 376 if obj == nil { 377 return nil, fmt.Errorf("package %s does not contain %q", pkg.Path(), pkgobj) 378 } 379 380 // abstraction of *types.{Pointer,Slice,Array,Chan,Map} 381 type hasElem interface { 382 Elem() types.Type 383 } 384 // abstraction of *types.{Interface,Named} 385 type hasMethods interface { 386 Method(int) *types.Func 387 NumMethods() int 388 } 389 390 // The loop state is the pair (t, obj), 391 // exactly one of which is non-nil, initially obj. 392 // All suffixes start with '.' (the only object->type operation), 393 // followed by optional type->type operations, 394 // then a type->object operation. 395 // The cycle then repeats. 396 var t types.Type 397 for suffix != "" { 398 code := suffix[0] 399 suffix = suffix[1:] 400 401 // Codes [AFM] have an integer operand. 402 var index int 403 switch code { 404 case opAt, opField, opMethod: 405 rest := strings.TrimLeft(suffix, "0123456789") 406 numerals := suffix[:len(suffix)-len(rest)] 407 suffix = rest 408 i, err := strconv.Atoi(numerals) 409 if err != nil { 410 return nil, fmt.Errorf("invalid path: bad numeric operand %q for code %q", numerals, code) 411 } 412 index = int(i) 413 case opObj: 414 // no operand 415 default: 416 // The suffix must end with a type->object operation. 417 if suffix == "" { 418 return nil, fmt.Errorf("invalid path: ends with %q, want [AFMO]", code) 419 } 420 } 421 422 if code == opType { 423 if t != nil { 424 return nil, fmt.Errorf("invalid path: unexpected %q in type context", opType) 425 } 426 t = obj.Type() 427 obj = nil 428 continue 429 } 430 431 if t == nil { 432 return nil, fmt.Errorf("invalid path: code %q in object context", code) 433 } 434 435 // Inv: t != nil, obj == nil 436 437 switch code { 438 case opElem: 439 hasElem, ok := t.(hasElem) // Pointer, Slice, Array, Chan, Map 440 if !ok { 441 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want pointer, slice, array, chan or map)", code, t, t) 442 } 443 t = hasElem.Elem() 444 445 case opKey: 446 mapType, ok := t.(*types.Map) 447 if !ok { 448 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want map)", code, t, t) 449 } 450 t = mapType.Key() 451 452 case opParams: 453 sig, ok := t.(*types.Signature) 454 if !ok { 455 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want signature)", code, t, t) 456 } 457 t = sig.Params() 458 459 case opResults: 460 sig, ok := t.(*types.Signature) 461 if !ok { 462 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want signature)", code, t, t) 463 } 464 t = sig.Results() 465 466 case opUnderlying: 467 named, ok := t.(*types.Named) 468 if !ok { 469 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want named)", code, t, t) 470 } 471 t = named.Underlying() 472 473 case opAt: 474 tuple, ok := t.(*types.Tuple) 475 if !ok { 476 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want tuple)", code, t, t) 477 } 478 if n := tuple.Len(); index >= n { 479 return nil, fmt.Errorf("tuple index %d out of range [0-%d)", index, n) 480 } 481 obj = tuple.At(index) 482 t = nil 483 484 case opField: 485 structType, ok := t.(*types.Struct) 486 if !ok { 487 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want struct)", code, t, t) 488 } 489 if n := structType.NumFields(); index >= n { 490 return nil, fmt.Errorf("field index %d out of range [0-%d)", index, n) 491 } 492 obj = structType.Field(index) 493 t = nil 494 495 case opMethod: 496 hasMethods, ok := t.(hasMethods) // Interface or Named 497 if !ok { 498 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want interface or named)", code, t, t) 499 } 500 if n := hasMethods.NumMethods(); index >= n { 501 return nil, fmt.Errorf("method index %d out of range [0-%d)", index, n) 502 } 503 obj = hasMethods.Method(index) 504 t = nil 505 506 case opObj: 507 named, ok := t.(*types.Named) 508 if !ok { 509 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want named)", code, t, t) 510 } 511 obj = named.Obj() 512 t = nil 513 514 default: 515 return nil, fmt.Errorf("invalid path: unknown code %q", code) 516 } 517 } 518 519 if obj.Pkg() != pkg { 520 return nil, fmt.Errorf("path denotes %s, which belongs to a different package", obj) 521 } 522 523 return obj, nil // success 524} 525