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.
5 // Package objectpath defines a naming scheme for types.Objects
6 // (that is, named entities in Go programs) relative to their enclosing
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.
16 // A single object may have multiple paths. In this example,
17 // type A struct{ X int }
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
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.
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:
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]
51 // All valid paths start with a package and end at an object
52 // and thus may be defined by the regular language:
54 // objectpath = PO (OT TT* TO)*
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.
67 // In the example below,
72 // f() (a string, b struct{ X int })
75 // field X has the path "T.UM0.RA1.F0",
76 // representing the following sequence of operations:
79 // .Type().Underlying().Method(0). f
80 // .Type().Results().At(1) b
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.
88 // object->type operators
89 opType = '.' // .Type() (Object)
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)
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)
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.
108 // The For function guarantees to return a path only for the following objects:
109 // - package-level types
110 // - exported package-level non-types
112 // - parameter and result variables
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.
117 // For does not return a path for predeclared names, imported package
118 // names, local names, and unexported package-level names (except
121 // Example: given this definition,
125 // type T interface {
126 // f() (a string, b struct{ X int })
129 // For(X) would return a path that denotes the following sequence of operations:
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)
136 // where p is the package (*types.Package) to which X belongs.
137 func For(obj types.Object) (Path, error) {
140 // This table lists the cases of interest.
149 // package-level accept
150 // func param/result accept
152 // struct field accept
154 // package-level accept
157 // package-level accept
158 // init functions reject
159 // concrete method accept
160 // interface method accept
162 // package-level accept
165 // The only accessible package-level objects are members of pkg itself.
167 // The cases are handled in four steps:
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.
174 // 1. reference to nil or builtin?
176 return "", fmt.Errorf("predeclared %s has no path", obj)
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)
187 return Path(obj.Name()), nil
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)
201 // - a field (obj.IsField())
202 // - a func parameter or result
204 // Sadly there is no way to distinguish
205 // a param/result from a local
206 // so we must proceed to the find.
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)
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.
222 // 4. Search the API for the path to the var (field/param/result) or method.
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)
234 continue // handle non-types in second pass
237 path := append(empty, name...)
238 path = append(path, opType)
244 if r := find(obj, T, path); r != nil {
248 // defined (named) type
249 if r := find(obj, T.Underlying(), append(path, opUnderlying)); r != nil {
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 {
262 // exported non-type (const, var, func)
263 if r := find(obj, o.Type(), append(path, opType)); r != nil {
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++ {
275 path2 := appendOpArg(path, opMethod, i)
277 return Path(path2), nil // found declared method
279 if r := find(obj, m.Type(), append(path2, opType)); r != nil {
286 return "", fmt.Errorf("can't find path for %v in %s", obj, pkg.Path())
289 func appendOpArg(path []byte, op byte, arg int) []byte {
290 path = append(path, op)
291 path = strconv.AppendInt(path, int64(arg), 10)
295 // find finds obj within type T, returning the path to it, or nil if not found.
296 func 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.
303 return find(obj, T.Elem(), append(path, opElem))
305 return find(obj, T.Elem(), append(path, opElem))
307 return find(obj, T.Elem(), append(path, opElem))
309 return find(obj, T.Elem(), append(path, opElem))
311 if r := find(obj, T.Key(), append(path, opKey)); r != nil {
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 {
319 return find(obj, T.Results(), append(path, opResults))
321 for i := 0; i < T.NumFields(); i++ {
323 path2 := appendOpArg(path, opField, i)
325 return path2 // found field var
327 if r := find(obj, f.Type(), append(path2, opType)); r != nil {
333 for i := 0; i < T.Len(); i++ {
335 path2 := appendOpArg(path, opAt, i)
337 return path2 // found param/result var
339 if r := find(obj, v.Type(), append(path2, opType)); r != nil {
344 case *types.Interface:
345 for i := 0; i < T.NumMethods(); i++ {
347 path2 := appendOpArg(path, opMethod, i)
349 return path2 // found interface method
351 if r := find(obj, m.Type(), append(path2, opType)); r != nil {
360 // Object returns the object denoted by path p within the package pkg.
361 func Object(pkg *types.Package, p Path) (types.Object, error) {
363 return nil, fmt.Errorf("empty path")
367 var pkgobj, suffix string
368 if dot := strings.IndexByte(pathstr, opType); dot < 0 {
371 pkgobj = pathstr[:dot]
372 suffix = pathstr[dot:] // suffix starts with "."
375 obj := pkg.Scope().Lookup(pkgobj)
377 return nil, fmt.Errorf("package %s does not contain %q", pkg.Path(), pkgobj)
380 // abstraction of *types.{Pointer,Slice,Array,Chan,Map}
381 type hasElem interface {
384 // abstraction of *types.{Interface,Named}
385 type hasMethods interface {
386 Method(int) *types.Func
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.
401 // Codes [AFM] have an integer operand.
404 case opAt, opField, opMethod:
405 rest := strings.TrimLeft(suffix, "0123456789")
406 numerals := suffix[:len(suffix)-len(rest)]
408 i, err := strconv.Atoi(numerals)
410 return nil, fmt.Errorf("invalid path: bad numeric operand %q for code %q", numerals, code)
416 // The suffix must end with a type->object operation.
418 return nil, fmt.Errorf("invalid path: ends with %q, want [AFMO]", code)
424 return nil, fmt.Errorf("invalid path: unexpected %q in type context", opType)
432 return nil, fmt.Errorf("invalid path: code %q in object context", code)
435 // Inv: t != nil, obj == nil
439 hasElem, ok := t.(hasElem) // Pointer, Slice, Array, Chan, Map
441 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want pointer, slice, array, chan or map)", code, t, t)
446 mapType, ok := t.(*types.Map)
448 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want map)", code, t, t)
453 sig, ok := t.(*types.Signature)
455 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want signature)", code, t, t)
460 sig, ok := t.(*types.Signature)
462 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want signature)", code, t, t)
467 named, ok := t.(*types.Named)
469 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want named)", code, t, t)
471 t = named.Underlying()
474 tuple, ok := t.(*types.Tuple)
476 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want tuple)", code, t, t)
478 if n := tuple.Len(); index >= n {
479 return nil, fmt.Errorf("tuple index %d out of range [0-%d)", index, n)
481 obj = tuple.At(index)
485 structType, ok := t.(*types.Struct)
487 return nil, fmt.Errorf("cannot apply %q to %s (got %T, want struct)", code, t, t)
489 if n := structType.NumFields(); index >= n {
490 return nil, fmt.Errorf("field index %d out of range [0-%d)", index, n)
492 obj = structType.Field(index)
496 hasMethods, ok := t.(hasMethods) // Interface or Named
498 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want interface or named)", code, t, t)
500 if n := hasMethods.NumMethods(); index >= n {
501 return nil, fmt.Errorf("method index %d out of range [0-%d)", index, n)
503 obj = hasMethods.Method(index)
507 named, ok := t.(*types.Named)
509 return nil, fmt.Errorf("cannot apply %q to %s (got %s, want named)", code, t, t)
515 return nil, fmt.Errorf("invalid path: unknown code %q", code)
519 if obj.Pkg() != pkg {
520 return nil, fmt.Errorf("path denotes %s, which belongs to a different package", obj)
523 return obj, nil // success