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	for _, name := range scope.Names() {
230		o := scope.Lookup(name)
231		tname, ok := o.(*types.TypeName)
232		if !ok {
233			continue // handle non-types in second pass
234		}
235
236		path := append(empty, name...)
237		path = append(path, opType)
238
239		T := o.Type()
240
241		if tname.IsAlias() {
242			// type alias
243			if r := find(obj, T, path); r != nil {
244				return Path(r), nil
245			}
246		} else {
247			// defined (named) type
248			if r := find(obj, T.Underlying(), append(path, opUnderlying)); r != nil {
249				return Path(r), nil
250			}
251		}
252	}
253
254	// Then inspect everything else:
255	// non-types, and declared methods of defined types.
256	for _, name := range scope.Names() {
257		o := scope.Lookup(name)
258		path := append(empty, name...)
259		if _, ok := o.(*types.TypeName); !ok {
260			if o.Exported() {
261				// exported non-type (const, var, func)
262				if r := find(obj, o.Type(), append(path, opType)); r != nil {
263					return Path(r), nil
264				}
265			}
266			continue
267		}
268
269		// Inspect declared methods of defined types.
270		if T, ok := o.Type().(*types.Named); ok {
271			path = append(path, opType)
272			for i := 0; i < T.NumMethods(); i++ {
273				m := T.Method(i)
274				path2 := appendOpArg(path, opMethod, i)
275				if m == obj {
276					return Path(path2), nil // found declared method
277				}
278				if r := find(obj, m.Type(), append(path2, opType)); r != nil {
279					return Path(r), nil
280				}
281			}
282		}
283	}
284
285	return "", fmt.Errorf("can't find path for %v in %s", obj, pkg.Path())
286}
287
288func appendOpArg(path []byte, op byte, arg int) []byte {
289	path = append(path, op)
290	path = strconv.AppendInt(path, int64(arg), 10)
291	return path
292}
293
294// find finds obj within type T, returning the path to it, or nil if not found.
295func find(obj types.Object, T types.Type, path []byte) []byte {
296	switch T := T.(type) {
297	case *types.Basic, *types.Named:
298		// Named types belonging to pkg were handled already,
299		// so T must belong to another package. No path.
300		return nil
301	case *types.Pointer:
302		return find(obj, T.Elem(), append(path, opElem))
303	case *types.Slice:
304		return find(obj, T.Elem(), append(path, opElem))
305	case *types.Array:
306		return find(obj, T.Elem(), append(path, opElem))
307	case *types.Chan:
308		return find(obj, T.Elem(), append(path, opElem))
309	case *types.Map:
310		if r := find(obj, T.Key(), append(path, opKey)); r != nil {
311			return r
312		}
313		return find(obj, T.Elem(), append(path, opElem))
314	case *types.Signature:
315		if r := find(obj, T.Params(), append(path, opParams)); r != nil {
316			return r
317		}
318		return find(obj, T.Results(), append(path, opResults))
319	case *types.Struct:
320		for i := 0; i < T.NumFields(); i++ {
321			f := T.Field(i)
322			path2 := appendOpArg(path, opField, i)
323			if f == obj {
324				return path2 // found field var
325			}
326			if r := find(obj, f.Type(), append(path2, opType)); r != nil {
327				return r
328			}
329		}
330		return nil
331	case *types.Tuple:
332		for i := 0; i < T.Len(); i++ {
333			v := T.At(i)
334			path2 := appendOpArg(path, opAt, i)
335			if v == obj {
336				return path2 // found param/result var
337			}
338			if r := find(obj, v.Type(), append(path2, opType)); r != nil {
339				return r
340			}
341		}
342		return nil
343	case *types.Interface:
344		for i := 0; i < T.NumMethods(); i++ {
345			m := T.Method(i)
346			path2 := appendOpArg(path, opMethod, i)
347			if m == obj {
348				return path2 // found interface method
349			}
350			if r := find(obj, m.Type(), append(path2, opType)); r != nil {
351				return r
352			}
353		}
354		return nil
355	}
356	panic(T)
357}
358
359// Object returns the object denoted by path p within the package pkg.
360func Object(pkg *types.Package, p Path) (types.Object, error) {
361	if p == "" {
362		return nil, fmt.Errorf("empty path")
363	}
364
365	pathstr := string(p)
366	var pkgobj, suffix string
367	if dot := strings.IndexByte(pathstr, opType); dot < 0 {
368		pkgobj = pathstr
369	} else {
370		pkgobj = pathstr[:dot]
371		suffix = pathstr[dot:] // suffix starts with "."
372	}
373
374	obj := pkg.Scope().Lookup(pkgobj)
375	if obj == nil {
376		return nil, fmt.Errorf("package %s does not contain %q", pkg.Path(), pkgobj)
377	}
378
379	// abtraction of *types.{Pointer,Slice,Array,Chan,Map}
380	type hasElem interface {
381		Elem() types.Type
382	}
383	// abstraction of *types.{Interface,Named}
384	type hasMethods interface {
385		Method(int) *types.Func
386		NumMethods() int
387	}
388
389	// The loop state is the pair (t, obj),
390	// exactly one of which is non-nil, initially obj.
391	// All suffixes start with '.' (the only object->type operation),
392	// followed by optional type->type operations,
393	// then a type->object operation.
394	// The cycle then repeats.
395	var t types.Type
396	for suffix != "" {
397		code := suffix[0]
398		suffix = suffix[1:]
399
400		// Codes [AFM] have an integer operand.
401		var index int
402		switch code {
403		case opAt, opField, opMethod:
404			rest := strings.TrimLeft(suffix, "0123456789")
405			numerals := suffix[:len(suffix)-len(rest)]
406			suffix = rest
407			i, err := strconv.Atoi(numerals)
408			if err != nil {
409				return nil, fmt.Errorf("invalid path: bad numeric operand %q for code %q", numerals, code)
410			}
411			index = int(i)
412		case opObj:
413			// no operand
414		default:
415			// The suffix must end with a type->object operation.
416			if suffix == "" {
417				return nil, fmt.Errorf("invalid path: ends with %q, want [AFMO]", code)
418			}
419		}
420
421		if code == opType {
422			if t != nil {
423				return nil, fmt.Errorf("invalid path: unexpected %q in type context", opType)
424			}
425			t = obj.Type()
426			obj = nil
427			continue
428		}
429
430		if t == nil {
431			return nil, fmt.Errorf("invalid path: code %q in object context", code)
432		}
433
434		// Inv: t != nil, obj == nil
435
436		switch code {
437		case opElem:
438			hasElem, ok := t.(hasElem) // Pointer, Slice, Array, Chan, Map
439			if !ok {
440				return nil, fmt.Errorf("cannot apply %q to %s (got %T, want pointer, slice, array, chan or map)", code, t, t)
441			}
442			t = hasElem.Elem()
443
444		case opKey:
445			mapType, ok := t.(*types.Map)
446			if !ok {
447				return nil, fmt.Errorf("cannot apply %q to %s (got %T, want map)", code, t, t)
448			}
449			t = mapType.Key()
450
451		case opParams:
452			sig, ok := t.(*types.Signature)
453			if !ok {
454				return nil, fmt.Errorf("cannot apply %q to %s (got %T, want signature)", code, t, t)
455			}
456			t = sig.Params()
457
458		case opResults:
459			sig, ok := t.(*types.Signature)
460			if !ok {
461				return nil, fmt.Errorf("cannot apply %q to %s (got %T, want signature)", code, t, t)
462			}
463			t = sig.Results()
464
465		case opUnderlying:
466			named, ok := t.(*types.Named)
467			if !ok {
468				return nil, fmt.Errorf("cannot apply %q to %s (got %s, want named)", code, t, t)
469			}
470			t = named.Underlying()
471
472		case opAt:
473			tuple, ok := t.(*types.Tuple)
474			if !ok {
475				return nil, fmt.Errorf("cannot apply %q to %s (got %s, want tuple)", code, t, t)
476			}
477			if n := tuple.Len(); index >= n {
478				return nil, fmt.Errorf("tuple index %d out of range [0-%d)", index, n)
479			}
480			obj = tuple.At(index)
481			t = nil
482
483		case opField:
484			structType, ok := t.(*types.Struct)
485			if !ok {
486				return nil, fmt.Errorf("cannot apply %q to %s (got %T, want struct)", code, t, t)
487			}
488			if n := structType.NumFields(); index >= n {
489				return nil, fmt.Errorf("field index %d out of range [0-%d)", index, n)
490			}
491			obj = structType.Field(index)
492			t = nil
493
494		case opMethod:
495			hasMethods, ok := t.(hasMethods) // Interface or Named
496			if !ok {
497				return nil, fmt.Errorf("cannot apply %q to %s (got %s, want interface or named)", code, t, t)
498			}
499			if n := hasMethods.NumMethods(); index >= n {
500				return nil, fmt.Errorf("method index %d out of range [0-%d)", index, n)
501			}
502			obj = hasMethods.Method(index)
503			t = nil
504
505		case opObj:
506			named, ok := t.(*types.Named)
507			if !ok {
508				return nil, fmt.Errorf("cannot apply %q to %s (got %s, want named)", code, t, t)
509			}
510			obj = named.Obj()
511			t = nil
512
513		default:
514			return nil, fmt.Errorf("invalid path: unknown code %q", code)
515		}
516	}
517
518	if obj.Pkg() != pkg {
519		return nil, fmt.Errorf("path denotes %s, which belongs to a different package", obj)
520	}
521
522	return obj, nil // success
523}
524