gotypes: a tutorial on go/types, the Go type checker Better late than never. Change-Id: Iedd3aaa9dc3eb40b79b7430ed2d69e2d4f87dc86 Reviewed-on: https://go-review.googlesource.com/17388 Reviewed-by: Robert Griesemer <gri@golang.org>
diff --git a/gotypes/Makefile b/gotypes/Makefile new file mode 100644 index 0000000..b7eb3d9 --- /dev/null +++ b/gotypes/Makefile
@@ -0,0 +1,12 @@ + +all: README.md + +README.md: go-types.md weave.go $(wildcard */*.go) + go run weave.go go-types.md >README.md + +# This is for previewing using github. +# $HOME/markdown must be a github client. +test: README.md + cp README.md $$HOME/markdown/ + (cd $$HOME/markdown/ && git commit -m . README.md && git push) +
diff --git a/gotypes/README.md b/gotypes/README.md new file mode 100644 index 0000000..d551420 --- /dev/null +++ b/gotypes/README.md
@@ -0,0 +1,2530 @@ +<!-- Autogenerated by weave; DO NOT EDIT --> + +# `go/types`: The Go Type Checker + +This document is maintained by Alan Donovan `adonovan@google.com`. + +[October 2015 GothamGo talk on go/types](https://docs.google.com/presentation/d/13OvHYozAUBeISPRoLgG7kMBuja1NsU1D_mMlmbaYojk/view) + + +# Contents + +1. [Introduction](#introduction) +1. [An Example](#an-example) +1. [Objects](#objects) +1. [Identifier Resolution](#identifier-resolution) +1. [Scopes](#scopes) +1. [Initialization Order](#initialization-order) +1. [Types](#types) + 1. [Basic types](#basic-types) + 1. [Simple Composite Types](#simple-composite-types) + 1. [Struct Types](#struct-types) + 1. [Tuple Types](#tuple-types) + 1. [Function and Method Types](#function-and-method-types) + 1. [Named Types](#named-types) + 1. [Interface Types](#interface-types) + 1. [TypeAndValue](#typeandvalue) +1. [Selections](#selections) +1. [Ids](#ids) +1. [Method Sets](#method-sets) +1. [Constants](#constants) +1. [Size and Alignment](#size-and-alignment) +1. [Imports](#imports) +1. [Formatting support](#formatting-support) +1. [Getting from A to B](#getting-from-a-to-b) + +# Introduction + + +The [`go/types` package]('https://golang.org/pkg/go/types) is a +type-checker for Go programs, designed by Robert Griesemer. +Measured by lines of code and by API surface area, it is one of the +most complex packages in Go's standard library, and using it requires +a firm grasp of the structure of Go programs. +This tutorial will help you find your bearings. +It comes with several example programs that you can obtain with `go get` and play with. +We assume you are a proficient Go programmer who wants to build tools +to analyze or manipulate Go programs and that you have some knowledge +of how a typical compiler works. + + + +The `go/types` package became part of Go's standard library in Go 1.5. +Prior to that, it was located at +[`golang.org/x/tools/go/types`](https://godoc.org/golang.org/x/tools/go/types), +though that package will be deleted one month after the release +of Go 1.6 in early 2016. + + + +The type checker complements several existing +standard packages for analyzing Go programs. +We've listed them below. + + + → go/types + go/constant + go/parser + go/ast + go/scanner + go/token + + +Starting at the bottom, the +[`go/token` package](http://golang.org/pkg/go/token) +defines the lexical tokens of Go. +The [`go/scanner` package](http://golang.org/pkg/go/scanner) tokenizes an input stream and records +file position information for use in diagnostics +or for file surgery in a refactoring tool. +The [`go/ast` package](http://golang.org/pkg/go/ast) +defines the data types of the abstract syntax tree (AST). +The [`go/parser` package](http://golang.org/pkg/go/parser) +provides a robust recursive-descent parser that constructs the AST. +And [`go/constant`](http://golang.org/pkg/go/constant) +provides representations and arithmetic operations for the values of compile-time +constant expressions, as we'll see in +[Constants](#constants). + + + +The [`golang.org/x/tools/go/loader` package](https://godoc.org/golang.org/x/tools/go/loader) +from the `x/tools` repository is a client of the type +checker that loads, parses, and type-checks a complete Go program from +source code. +We use it in some of our examples and you may find it useful too. +(Please note that until March 2016, the +`golang.org/x/tools/...` packages will continue to depend on the +old `golang.org/x/tools/go/types` package, not on the +new standard `go/types` package. The two are almost identical.) + + + +The Go type checker does three main things. +First, for every name in the program, it determines which declaration +the name refers to; this is known as _identifier resolution_. +Second, for every expression in the program, it determines what type +that expression has, or reports an error if the expression has no +type, or has an inappropriate type for its context; this is known as +_type deduction_. +Third, for every constant expression in the program, it determines the +value of that constant; this is known as _constant evaluation_. + + + +Superficially, it appears that these three processes could be done +sequentially, in the order above, but perhaps surprisingly, they must +be done together. +For example, the value of a constant may depend on the type of an +expression due to operators like `unsafe.Sizeof`. +Conversely, the type of an expression may depend on the value of a +constant, since array types contain constants. +As a result, type deduction and constant evaluation must be done +together. + + + +As another example, we cannot resolve the identifier `k` in the composite +literal `T{k: 0}` until we know whether `T` is a struct type. +If it is, then `k` must be found among `T`'s fields. +If not, then `k` is an ordinary reference +to a constant or variable in the lexical environment. +Consequently, identifier resolution and type deduction are also +inseparable in the general case. + + + +Nonetheless, the three processes of identifier resolution, type +deduction, and constant evaluation can be separated for the purpose of +explanation. + + +# An Example + + +The code below shows the most basic use of the type checker to check +the _hello, world_ program, supplied as a string. +Later examples will be variations on this one, and we'll often omit +boilerplate details such as parsing. +To check out and build the examples, +run `go get github.com/golang/example/gotypes/...`. + + + // go get github.com/golang/example/gotypes/pkginfo + +``` +package main + +import ( + "fmt" + "go/ast" + "go/importer" + "go/parser" + "go/token" + "go/types" + "log" +) + +const hello = `package main + +import "fmt" + +func main() { + fmt.Println("Hello, world") +}` + +func main() { + fset := token.NewFileSet() + + // Parse the input string, []byte, or io.Reader, + // recording position information in fset. + // ParseFile returns an *ast.File, a syntax tree. + f, err := parser.ParseFile(fset, "hello.go", hello, 0) + if err != nil { + log.Fatal(err) // parse error + } + + // A Config controls various options of the type checker. + // The defaults work fine except for one setting: + // we must specify how to deal with imports. + conf := types.Config{Importer: importer.Default()} + + // Type-check the package containing only file f. + // Check returns a *types.Package. + pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, nil) + if err != nil { + log.Fatal(err) // type error + } + + fmt.Printf("Package %q\n", pkg.Path()) + fmt.Printf("Name: %s\n", pkg.Name()) + fmt.Printf("Imports: %s\n", pkg.Imports()) + fmt.Printf("Scope: %s\n", pkg.Scope()) +} +``` + + +First, the program creates a +[`token.FileSet`](http://golang.org/pkg/go/token/#FileSet). +To avoid the need to store file names and line and column +numbers in every node of the syntax tree, the `go/token` package +provides `FileSet`, a data structure that stores this information +compactly for a sequence of files. +A `FileSet` records each file name only once, and records +only the byte offsets of each newline, allowing a position within +any file to be identified using a small integer called a +`token.Pos`. +Many tools create a single `FileSet` at startup. +Any part of the program that needs to convert a `token.Pos` into +an intelligible location---as part of an error message, for +instance---must have access to the `FileSet`. + + + +Second, the program parses the input string. +More realistic packages contain several source files, so the parsing +step must be repeated for each one, or better still, done in parallel. +Third, it creates a `Config` that specifies type-checking options. +Since the _hello, world_ program uses imports, we must indicate +how to locate the imported packages. +Here we use `importer.Default()`, which loads compiler-generated +export data, but we'll explore alternatives in [Imports](#imports). + + + +Fourth, the program calls `Check`. +This creates a `Package` whose path is `"cmd/hello"`, and +type-checks each of the specified files---just one in this example. +The final (nil) argument is a pointer to an optional `Info` +struct that returns additional deductions from the type checker; more +on that later. +`Check` returns a `Package` even when it also returns an error. +The type checker is robust to ill-formed input, +and goes to great lengths to report accurate +partial information even in the vicinity of syntax or type errors. +`Package` has this definition: + + + type Package struct{ ... } + func (*Package) Path() string + func (*Package) Name() string + func (*Package) Scope() *Scope + func (*Package) Imports() []*Package + + +Finally, the program prints the attributes of the package, shown below. +(The hexadecimal number may vary from one run to the next.) + + +``` +$ go build github.com/golang/example/gotypes/pkginfo +$ ./pkginfo +Package "cmd/hello" +Name: main +Imports: [package fmt ("fmt")] +Scope: package "cmd/hello" scope 0x820533590 { +. func cmd/hello.main() +} +``` + + +A package's `Path`, such as `"encoding/json"`, is the string +by which import declarations identify it. +It is unique within a `$GOPATH` workspace, +and for published packages it must be globally unique. + + +A package's `Name` is the identifier in the `package` +declaration of each source file within the package, such as `json`. +The type checker reports an error if not all the package declarations in +the package agree. +The package name determines how the package is known when it is +imported into a file (unless a renaming import is used), +but is otherwise not visible to a program. + + +`Scope` returns the package's [_lexical block_](#scopes), +which provides access to all the named entities or +[_objects_](#objects) declared at package level. +`Imports` returns the set of packages directly imported by this +one, and may be useful for computing dependencies +([Initialization Order](#initialization_order)). + + + +# Objects + + +The task of identifier resolution is to map every identifier in the +syntax tree, that is, every `ast.Ident`, to an object. +For our purposes, an _object_ is a named entity created by a +declaration, such as a `var`, `type`, or `func` +declaration. +(This is different from the everyday meaning of object in +object-oriented programming.) + + + +Objects are represented by the `Object` interface, shown below: + + + type Object interface { + Name() string // package local object name + Exported() bool // reports whether the name starts with a capital letter + Type() Type // object type + Pos() token.Pos // position of object identifier in declaration + + Parent() *Scope // scope in which this object is declared + Pkg() *Package // nil for objects in the Universe scope and labels + Id() string // object id (see Ids section below) + } + + +The first four methods are straightforward; we'll explain the other +three later. +`Name` returns the objects's name---an identifier. +`Exported` is a convenience method that reports whether the first +letter of `Name` is a capital, indicating that the object may be +visible from outside the package. +It's a shorthand for `ast.IsExported(obj.Name())`. +`Type` returns the object's type; we'll come back to that in +[Types](#types). + + + +`Pos` returns the source position of the object's declaring identifier. +To make sense of a `token.Pos`, we need to call the +`(*token.FileSet).Position` method, which returns a struct with +individual fields for the file name, line number, column, and byte +offset, though usually we just call its `String` method: + + + fmt.Fprintln(fset.Position(obj.Pos())) // "hello.go:10:6" + + +Not all objects carry position information. +Since the file format for compiler export data ([Imports](#imports)) +does not record position information, calling `Pos` on an object +imported from such a file returns zero, also known as +`token.NoPos`. + + + +There are eight kinds of objects in the Go type checker. +Most familiar are the kinds that can be declared at package level: +constants, variables, functions, and types. +Less familiar are statement labels, imported package names +(such as `json` in a file containing an `import "encoding/json"` +declaration), built-in functions (such as `append` and +`len`), and the pre-declared `nil`. +The eight types shown below are the only concrete types that satisfy +the `Object` interface. +In other words, `Object` is a _discriminated union_ of 8 +possible types, and we commonly use a type switch to distinguish them. + + + Object = *Func // function, concrete method, or abstract method + | *Var // variable, parameter, result, or struct field + | *Const // constant + | *TypeName // named type (except for predeclared ones) + | *Label // statement label + | *PkgName // package name, e.g. json after import "encoding/json" + | *Builtin // predeclared function such as append or len + | *Nil // predeclared nil + + +`Object`s are canonical. +That is, two `Object`s `x` and `y` denote the same +entity if and only if `x==y`. +Object identity is significant, and objects are routinely compared by +the addresses of the underlying pointers. +Although a package-level object is uniquely identified by its name +and enclosing package, for other objects there is no simple way to +obtain a string that uniquely identifies it. + + + +The `Parent` method returns the `Scope` (lexical block) in +which the object was declared; we'll come back to this in +[Scopes](#scopes). +Fields and methods are not found in the lexical environment, so +their objects have no `Parent`. + + + +The `Pkg` method returns the `Package` to which this object +belongs, even for objects not declared at package level. +Only predeclared objects have no package. +The `Id` method will be explained in [Ids](#ids). + + + +Not all methods make sense for each kind of object. For instance, +the last four kinds above have no meaningful `Type` method. +And some kinds of object have methods in addition to those required by the +`Object` interface: + + + func (*Func) Scope() *Scope + func (*Var) Anonymous() bool + func (*Var) IsField() bool + func (*Const) Val() constant.Value + func (*PkgName) Imported() *Package + + +`(*Func).Scope` returns the [lexical block](#scopes) +containing the function's parameters, results, +and other local declarations. +`(*Var).IsField` distinguishes struct fields from ordinary +variables, and `(*Var).Anonymous` discriminates named fields like +the one in `struct{T T}` from anonymous fields like the one in `struct{T}`. +`(*Const).Val` returns the value of a named [constant](#constants). + + + +`(*PkgName).Imported` returns the package (for instance, +`encoding/json`) denoted by a given import name such as `json`. +Each time a package is imported, a new `PkgName` object is +created, usually with the same name as the `Package` it +denotes, but not always, as in the case of a renaming import. +`PkgName`s are objects, but `Package`s are not. +We'll look more closely at this in [Imports](#imports). + + + +All relationships between the syntax trees (`ast.Node`s) and type +checker data structures such as `Object`s and `Type`s are +stored in mappings outside the syntax tree itself. +Be aware that the `go/ast` package also defines a type called +`Object` that resembles---and predates---the type checker's +`Object`, and that `ast.Object`s are held directly by +identifiers in the AST. +They are created by the parser, which has a necessarily limited view +of the package, so the information they represent is at best partial and +in some cases wrong, as in the `T{k: 0}` example mentioned above. +If you are using the type checker, there is no reason to use the older +`ast.Object` mechanism. + + + +# Identifier Resolution + + +Identifier resolution computes the relationship between +identifiers and objects. +Its results are recorded in the `Info` struct optionally passed +to `Check`. +The fields related to identifier resolution are shown below. + + + type Info struct { + Defs map[*ast.Ident]Object + Uses map[*ast.Ident]Object + Implicits map[ast.Node]Object + Selections map[*ast.SelectorExpr]*Selection + Scopes map[ast.Node]*Scope + ... + } + + +Since not all facts computed by the type checker are needed by every +client, the API lets clients control which components of the result +should be recorded and which discarded: only fields that hold a +non-nil map will be populated during the call to `Check`. + + + +The two fields of type `map[*ast.Ident]Object` are the most important: +`Defs` records _declaring_ identifiers and +`Uses` records _referring_ identifiers. +In the example below, the comments indicate which identifiers are of +which kind. + + + var x int // def of x, use of int + fmt.Println(x) // uses of fmt, Println, and x + type T struct{U} // def of T, use of U (type), def of U (field) + + +The final line above illustrates why we don't combine `Defs` and +`Uses` into one map. +In the anonymous field declaration `struct{U}`, the +identifier `U` is both a use of the type `U` (a +`TypeName`) and a definition of the anonymous field (a +`Var`). + + + +The function below prints the location of each referring and defining +identifier in the input program, and the object it refers to. + + + // go get github.com/golang/example/gotypes/defsuses + +``` +func PrintDefsUses(fset *token.FileSet, files ...*ast.File) error { + conf := types.Config{Importer: importer.Default()} + info := &types.Info{ + Defs: make(map[*ast.Ident]types.Object), + Uses: make(map[*ast.Ident]types.Object), + } + _, err := conf.Check("hello", fset, files, info) + if err != nil { + return err // type error + } + + for id, obj := range info.Defs { + fmt.Printf("%s: %q defines %v\n", + fset.Position(id.Pos()), id.Name, obj) + } + for id, obj := range info.Uses { + fmt.Printf("%s: %q uses %v\n", + fset.Position(id.Pos()), id.Name, obj) + } + return nil +} +``` + + +Let's use the _hello, world_ program again as the input: + + + // go get github.com/golang/example/gotypes/hello + +``` +package main + +import "fmt" + +func main() { + fmt.Println("Hello, 世界") +} +``` + + +This is what it prints: + + +``` +$ go build github.com/golang/example/gotypes/defsuses +$ ./defsuses +hello.go:1:9: "main" defines <nil> +hello.go:5:6: "main" defines func hello.main() +hello.go:6:9: "fmt" uses package fmt +hello.go:6:13: "Println" uses func fmt.Println(a ...interface{}) (n int, err error) +``` + + +Notice that the `Defs` mapping may contain nil entries in a few +cases. +The first line of output reports that the package identifier +`main` is present in the `Defs` mapping, but has no +associated object. + + + +The `Implicits` mapping handles two cases of the syntax in +which an `Object` is declared without an `ast.Ident`, namely type +switches and import declarations. +<!-- +A third case: an anonymous function parameter or result variable. +These objects are returned by Signature.Param and Signature.Result. +--> +In the type switch below, which declares a local variable `y`, +the type of `y` is different in each case of the switch: + + + switch y := x.(type) { + case int: + fmt.Printf("%d", y) + case string: + fmt.Printf("%q", y) + default: + fmt.Print(y) + } + + +To represent this, for each single-type case, the type checker creates +a separate `Var` object for `y` with the appropriate type, +and `Implicits` maps each `ast.CaseClause` to the `Var` +for that case. +The `default` case, the `nil` case, and cases with more than one +type all use the regular `Var` object that is associated with the +identifier `y`, which is found in the `Defs` mapping. + + + +The import declaration below defines the name `json` without an +`ast.Ident`: + + + import "encoding/json" + + +`Implicits` maps this `ast.ImportSpec` to the `PkgName` +object named `json` that it implicitly declares. + + + +The `Selections` mapping, of type +`map[*ast.SelectorExpr]*Selection`, records the meaning of each +expression of the form _`expr`_`.f`, where _`expr`_ is +an expression or type and `f` is the name of a field or method. +These expressions, called _selections_, are represented by +`ast.SelectorExpr` nodes in the AST. +We'll talk more about the `Selection` type in [Selections](#selections). + + + +Not all `ast.SelectorExpr` nodes represent selections. +Expressions like `fmt.Println`, in which a package name precedes +the dot, are _qualified identifiers_. +They do not appear in the `Selections` mapping, but their +constituent identifiers (such as `fmt` and `Println`) both +appear in `Uses`. + + + +Referring identifiers that are not part of an `ast.SelectorExpr` +are _lexical references_. +That is, they are resolved to an object by searching for the +innermost enclosing lexical declaration of that name. +We'll see how that search works in the next section. + + +# Scopes + + +The `Scope` type is a mapping from names to objects. + + + type Scope struct{ ... } + + func (s *Scope) Names() []string + func (s *Scope) Lookup(name string) Object + + +`Names` returns the set of names in the mapping, in sorted order. +(It is not a simple accessor though, so call it sparingly.) +The `Lookup ` method returns the object for a given name, so we +can print all the entries or _bindings_ in a scope like this: + + + for _, name := range scope.Names() { + fmt.Println(scope.Lookup(name)) + } + + +The _scope_ of a declaration of a name is the region of +program source in which a reference to the name resolves to that +declaration. That is, scope is a property of a declaration. +However, in the `go/types` API, the `Scope` type represents +a _lexical block_, which is one component of the lexical +environment. +Consider the _hello, world_ program again: + + + package main + + import "fmt" + + func main() { + const message = "hello, world" + fmt.Println(message) + } + + +There are four lexical blocks in this program. +The outermost one is the _universe block_, which maps the +pre-declared names like `int`, `true`, and `append` to +their objects---a `TypeName`, a `Const`, and a +`Builtin`, respectively. +The universe block is represented by the global variable +`Universe`, of type `*Scope`, although it's logically a +constant so you shouldn't modify it. + + + +Next is the _package block_, which maps `"main"` to the +`main` function. +Following that is the _file block_, which maps `"fmt"` to +the `PkgName` object for this import of the `fmt` package. +And finally, the innermost block is that of function `main`, a +local block, which contains the declaration of `message`, a `Const`. +The `main` function is trivial, but many functions contain +several blocks since each `if`, `for`, `switch`, +`case`, or `select` statement creates at least one +additional block. +Local blocks nest to arbitrary depths. + + + +The structure of the lexical environment thus forms a tree, with the +universe block at the root, the package blocks beneath it, the file +blocks beneath them, and then any number of local blocks beneath the +files. +The following methods of `Scope` make this tree structure +accessible and navigable: + + + func (s *Scope) Parent() *Scope + func (s *Scope) NumChildren() int + func (s *Scope) Child(i int) *Scope + + +`Parent` lets us walk up the tree, and `Child` +lets us walk down it. +Note that although the `Parent` of every package `Scope` is +`Universe`, `Universe` has no children. +This asymmetry is a consequence of using a global variable to hold +`Universe`. + + + +To obtain the universe block, we use the `Universe` global variable. +To obtain the lexical block of a `Package`, we call its +`Scope` method. +To obtain the scope of a file (`*ast.File`), or any smaller piece +of syntax such as an `*ast.IfStmt`, we consult the `Scopes` +mapping in the `Info` struct, which maps each block-creating +syntax node to its block. +The lexical block of a named function or method can also be obtained +by calling its `(*Func).Scope` method. + + +<!-- +TODO: explain explicit and implicit blocks +TODO: explain Dot imports. +TODO: explain that Func blocks are associated with FuncType (not FuncDecl or FuncLit) +--> + + +To look up a name in the lexical environment, we must search the tree +of lexical blocks, starting at a particular `Scope` and walking +up to the root until a declaration of the name is found. +For convenience, the `LookupParent` method does this, returning +not just the object, if found, but also the `Scope` in which it was +declared, which may be an ancestor of the initial one: + + + func (s *Scope) LookupParent(name string, pos token.Pos) (*Scope, Object) + + +The `pos` parameter determines the position in the source code at +which the name should be resolved. +The effective lexical environment is different at each point in the +block because it depends on which local declarations appear +before or after that point. +(We'll see an illustration in a moment.) + + + +`Scope` has several other methods relating to source positions: + + + func (s *Scope) Pos() token.Pos + func (s *Scope) End() token.Pos + func (s *Scope) Contains(pos token.Pos) bool + func (s *Scope) Innermost(pos token.Pos) *Scope + + +`Pos` and `End` report the `Scope`'s start and end +position which, for explicit blocks, are coincident with its curly +braces. +`Contains` is a convenience method that reports whether a +position lies in this interval. +`Innermost` returns the innermost scope containing the specified +position, which may be a child or other descendent of the initial +scope. + + + +These features are useful for tools that wish to resolve names or +evaluate constant expressions as if they had appeared at a particular +point within the program. +The next example program finds all the comments in the input, +treating the contents of each one as a name. It looks up each name in +the environment at the position of the comment, and prints what it +finds. +Observe that the `ParseComments` flag directs the parser to +preserve comments in the input. + + + // go get github.com/golang/example/gotypes/lookup + +``` +func main() { + fset := token.NewFileSet() + f, err := parser.ParseFile(fset, "hello.go", hello, parser.ParseComments) + if err != nil { + log.Fatal(err) // parse error + } + + conf := types.Config{Importer: importer.Default()} + pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, nil) + if err != nil { + log.Fatal(err) // type error + } + + // Each comment contains a name. + // Look up that name in the innermost scope enclosing the comment. + for _, comment := range f.Comments { + pos := comment.Pos() + name := strings.TrimSpace(comment.Text()) + fmt.Printf("At %s,\t%q = ", fset.Position(pos), name) + inner := pkg.Scope().Innermost(pos) + if _, obj := inner.LookupParent(name, pos); obj != nil { + fmt.Println(obj) + } else { + fmt.Println("not found") + } + } +} +``` + + +The expression `pkg.Scope().Innermost(pos)` finds the innermost +`Scope` that encloses the comment, and `LookupParent(name, pos)` +does a name lookup at a specific position in that lexical block. + + + +A typical input is shown below. +The first comment causes a lookup of `"append"` in the file block. +The second comment looks up `"fmt"` in the `main` function's block, +and so on. + + +``` +const hello = ` +package main + +import "fmt" + +// append +func main() { + // fmt + fmt.Println("Hello, world") + // main + main, x := 1, 2 + // main + print(main, x) + // x +} +// x +` +``` + + +Here's the output: + + +``` +$ go build github.com/golang/example/gotypes/lookup +$ ./lookup +At hello.go:6:1, "append" = builtin append +At hello.go:8:9, "fmt" = package fmt +At hello.go:10:9, "main" = func cmd/hello.main() +At hello.go:12:9, "main" = var main int +At hello.go:14:9, "x" = var x int +At hello.go:16:1, "x" = not found +``` + + +Notice how the two lookups of `main` return different results, +even though they occur in the same block, because one precedes the +declaration of the local variable named `main` and the other +follows it. +Also notice that there are two lookups of the name `x` but only +the first one, in the function block, succeeds. + + + +Download the program and modify both the input program and +the set of comments to get a better feel for how name resolution works. + + + +The table below summarizes which kinds of object may be declared at +each level of the tree of lexical blocks. + + + Universe File Package Local + Builtin ✔ + Nil ✔ + Const ✔ ✔ ✔ + TypeName ✔ ✔ ✔ + Func ✔ + Var ✔ ✔ + PkgName ✔ + Label ✔ + +# Initialization Order + + +In the course of identifier resolution, the type checker constructs a +graph of references among declarations of package-level variables and +functions. +The type checker reports an error if the initializer expression for a +variable refers to that variable, whether directly or indirectly. + + + +The reference graph determines the initialization order of the +package-level variables, as required by the Go spec, using a +breadth-first algorithm. +First, variables in the graph with no successors are removed, sorted +into the order in which they appear in the source code, then added +to a list. This creates more variables that have no successors. +The process repeats until they have all been removed. + + + +The result is available in the `InitOrder` field of the +`Info` struct, whose type is `[]Initializer`. + + + type Info struct { + ... + InitOrder []Initializer + ... + } + + type Initializer struct { + Lhs []*Var // var Lhs = Rhs + Rhs ast.Expr + } + + +Each element of the list represents a single initializer expression +that must be executed, and the variables to which it is assigned. +The variables may number zero, one, or more, as in these examples: + + + var _ io.Writer = new(bytes.Buffer) + var rx = regexp.MustCompile("^b(an)*a$") + var cwd, cwdErr = os.Getwd() + + +This process governs the initialization order of variables within a +package. +Across packages, dependencies must be initialized first, although the +order among them is not specified. +That is, any topological order of the import graph will do. +The `(*Package).Imports` method returns the set of direct +dependencies of a package, in an unspecified order. + + +# Types + + +The main job of the type checker is, of course, to deduce the type +of each expression and to report type errors. +Like `Object`, `Type` is an interface type used as a +discriminated union of several concrete types but, unlike +`Object`, `Type` has very few methods because types have +little in common with each other. +Here is the interface: + + + type Type interface { + Underlying() Type + } + + +And here are the eleven concrete types that satisfy it: + + + Type = *Basic + | *Pointer + | *Array + | *Slice + | *Map + | *Chan + | *Struct + | *Tuple + | *Signature + | *Named + | *Interface + + +With the exception of `Named` types, instances of `Type` are +not canonical. +That is, it is usually a mistake to compare types using `t1==t2` +since this equivalence is not the same as the +[type identity relation](https://golang.org/ref/spec#Type_identity) +defined by the Go spec. +Use this function instead: + + + func Identical(t1, t2 Type) bool + + +For the same reason, you should not use a `Type` as a key in a map. +The [`golang.org/x/tools/go/types/typeutil` package](https://godoc.org/golang.org/x/tools/go/types/typeutil) +provides a map keyed by types that uses the correct +equivalence relation. + + +The Go spec defines three relations over types. +[_Assignability_](https://golang.org/ref/spec#Assignability) +governs which pairs of types may appear on the +left- and right-hand side of an assignment, including implicit +assignments such as function calls, map and channel operations, and so +on. +[_Comparability_](https://golang.org/ref/spec#Comparison_operators) +determines which types may appear in a comparison `x==y` or a +switch case or may be used as a map key. +[_Convertibility_](https://golang.org/ref/spec#Conversions) +governs which pairs of types are allowed in a conversion operation +`T(v)`. +You can query these relations with the following predicate functions: + + + func AssignableTo(V, T Type) bool + func Comparable(T Type) bool + func ConvertibleTo(V, T Type) bool + + +Let's take a look at each kind of type. + + +## Basic types + + +`Basic` represents all types that are not composed from simpler +types. +This is essentially the set of underlying types that a constant expression is +permitted to have--strings, booleans, and numbers---but it also +includes `unsafe.Pointer` and untyped nil. + + + type Basic struct{...} + func (*Basic) Kind() BasicKind + func (*Basic) Name() string + func (*Basic) Info() BasicInfo + + +The `Kind` method returns an "enum" value that indicates which +basic type this is. +The kinds `Bool`, `String`, `Int16`, and so on, +represent the corresponding predeclared boolean, string, or numeric +types. +There are two synonyms: `Byte` is equivalent to `Uint8` +and `Rune` is equivalent to `Int32`. +The kind `UnsafePointer` represents `unsafe.Pointer`. +The kinds `UntypedBool`, `UntypedInt` and so on represent +the six kinds of "untyped" constant types: boolean, integer, rune, +float, complex, and string. +The kind `UntypedNil` represents the type of the predeclared +`nil` value. +And the kind `Invalid` indicates the invalid type, which is used +for expressions containing errors, or for objects without types, like +`Label`, `Builtin`, or `PkgName`. + + + +The `Name` method returns the name of the type, such as +`"float64"`, and the `Info` method returns a bitfield that +encodes information about the type, such as whether it is signed or +unsigned, integer or floating point, real or complex. + + + +`Typ` is a table of canonical basic types, indexed by +kind, so `Typ[String]` returns the `*Basic` that represents +`string`, for instance. +Like `Universe`, `Typ` is logically a constant, so don't +modify it. + + + +A few minor subtleties: +According to the Go spec, pre-declared types such as `int` are +named types for the purposes of assignability, even though the type +checker does not represent them using `Named`. +And `unsafe.Pointer` is a pointer type for the purpose of +determining whether the receiver type of a method is legal, even +though the type checker does not represet it using `Pointer`. + + + +The "untyped" types are usually only ascribed to constant expressions, +but there is one exception. +A comparison `x==y` has type "untyped bool", so the result of +this expression may be assigned to a variable of type `bool` or +any other named boolean type. + + + +## Simple Composite Types + + +The types `Pointer`, `Array`, `Slice`, `Map`, +and `Chan` are pretty self-explanatory. +All have an `Elem` method that returns the element type `T` +for a pointer `*T`, an array `[n]T`, a slice `[]T`, a +map `map[K]T`, or a channel `chan T`. +This should feel familiar if you've used the `reflect.Value` API. + + + +In addition, the `*Map`, `*Chan`, and `*Array` types +have accessor methods that return their key type, direction, and +length, respectively: + + + func (*Map) Key() Type + func (*Chan) Dir() ChanDir // = Send | Recv | SendRecv + func (*Array) Len() int64 + + + +## Struct Types + + +A struct type has an ordered list of fields and a corresponding +ordered list of field tags. + + + type Struct struct{ ... } + func (*Struct) NumFields() int + func (*Struct) Field(i int) *Var + func (*Struct) Tag(i int) string + + +Each field is a `Var` object whose `IsField` method returns true. +Field objects have no `Parent` scope, because they are +resolved through selections, not through the lexical environment. + + + +Thanks to embedding, the expression `new(S).f` may be a shorthand +for a longer expression such as `new(S).d.e.f`, but in the +representation of `Struct` types, these field selection +operations are explicit. +That is, the set of fields of struct type `S` does not include `f`. +An anonymous field is represented like a regular field, but its +`Anonymous` method returns true. + + + +One subtlety is relevent to tools that generate documentation. +When analyzing a declaration such as this, + + + type T struct{x int} + + +it may be tempting to consider the `Var` object for field `x` as if it +had the name `"T.x"`, but beware: field objects do not have +canonical names and there is no way to obtain the name `"T"` +from the `Var` for `x`. +That's because several types may have the same underlying struct type, +as in this code: + + + type T struct{x int} + type U T + + +Here, the `Var` for field `x` belongs equally to `T` +and to `U`, and short of inspecting source positions or walking +the AST---neither of which is possible for objects loaded from compiler +export data---it is not possible to ascertain that `x` was declared as +part of `T`. +The type checker computes the exact same data structures given this input: + + + type T U + type U struct{x int} + + +A similar issue applies to the methods of named interface types. + + +## Tuple Types + + +Like a struct, a tuple type has an ordered list of fields, and fields +may be named. + + + type Tuple struct{ ... } + func (*Tuple) Len() int + func (*Tuple) At(i int) *Var + + +Although tuples are not the type of any variable in Go, they are +the type of some expressions, such as the right-hand sides of these +assignments: + + + v, ok = m[key] + v, ok = <-ch + v, ok = x.(T) + f, err = os.Open(filename) + + +Tuples also represent the types of the parameter list and the result +list of a function, as we will see. + + + +Since empty tuples are common, the nil `*Tuple` pointer is a valid empty tuple. + + + +## Function and Method Types + + +The types of functions and methods are represented by a `Signature`, +which has a tuple of parameter types and a tuple of result types. + + + type Signature struct{ ... } + func (*Signature) Recv() *Var + func (*Signature) Params() *Tuple + func (*Signature) Results() *Tuple + func (*Signature) Variadic() bool + + +Variadic functions such as `fmt.Println` have the `Variadic` +flag set. +The final parameter of such functions is always a slice, or in the +special case of certain calls to `append`, a string. + + + +A `Signature` for a method, whether concrete or abstract, has a +non-nil receiver parameter, `Recv`. +The type of the receiver is usually a named type or a pointer to a named type, +but it may be an unnamed struct or interface type in some cases. +Method types are rather second-class: they are only used for the +`Func` objects created by method declarations, and no Go +expression has a method type. +When printing a method type, the receiver does not appear, and the +`Identical` predicate ignores the receiver. + + + +The types of `Builtin` objects like `append` cannot be +expressed as a `Signature` since those types require parametric +polymorphism. +`Builtin` objects are thus ascribed the `Invalid` basic type. +However, the type of each _call_ to a built-in function has a specific +and expressible Go type. +These types are recorded during type checking for later use +([TypeAndValue](#typeandvalue)). + + + +## Named Types + + +A type declaration creates a `TypeName` object, and the type of +that object is a `Named`. +These two entities, an object and a type, are distinct but closely +related, and they exist in one-to-one correpondence. + + + type Named struct{ ... } + func (*Named) NumMethods() int + func (*Named) Method(i int) *Func + func (*Named) Obj() *TypeName + func (*Named) Underlying() Type + + +The `Named` type's `Obj` method returns the `TypeName` object, which +provides the name, position, and other properties of the declaration. +Conversely, the `TypeName` object's `Type` method returns the `Named` type. + + + +The `NumMethods` and `Method` methods enumerate the declared +methods associated with this `Named` type (or a pointer to it), +in the order they were declared. +However, due to the subtleties of anonymous fields and the difference +between value and pointer receivers, a named type may have more or fewer +methods than this list. We'll return to this in [Method Sets](#method_sets). + + + +Every `Type` has an `Underlying` method, but for all of them +except `*Named`, it is simply the identity function. +For a named type, `Underlying` returns its underlying type, which +is always an unnamed type. +Thus `Underlying` returns `int` for both `T` and +`U` below. + + + type T int + type U T + + +Clients of the type checker often use type assertions or type switches +with a `Type` operand. +When doing so, it is often necessary to switch on the type that +_underlies_ the type of interest, and failure to do so may be a +bug. + +This is a common pattern: + + + // handle types of composite literal + switch u := t.Underlying().(type) { + case *Struct: // ... + case *Map: // ... + case *Array, *Slice: // ... + default: + panic("impossible") + } + +## Interface Types + + +Interface types are represented by `Interface`. + + + type Interface struct{ ... } + func (*Interface) Empty() bool + func (*Interface) NumMethods() int + func (*Interface) Method(i int) *Func + func (*Interface) NumEmbeddeds() int + func (*Interface) Embedded(i int) *Named + func (*Interface) NumExplicitMethods() int + func (*Interface) ExplicitMethod(i int) *Func + + +Syntactically, an interface type has a list of explicitly declared +methods (`ExplicitMethod`), and a list of embedded named +interface types (`Embedded`), but many clients care only about +the complete set of methods, which can be enumerated via +`Method`. +All three lists are ordered by name. +Since the empty interface is an important special case, the +`Empty` predicate provides a shorthand for `NumMethods() == +0`. + + + +As with the fields of structs (see above), the methods of interfaces +may belong equally to more than one interface type. +The `Func` object for method `f` in the code below is shared +by `I` and `J`: + + + type I interface { f() } + type J I + + +Because the difference between interface (abstract) and +non-interface (concrete) types is so important in Go, the +`IsInterface` predicate is provided for convenience. + + + func IsInterface(Type) bool + + +The type checker provides three utility methods relating to interface +satisfaction: + + + func Implements(V Type, T *Interface) bool + func AssertableTo(V *Interface, T Type) bool + func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) + + +The `Implements` predicate reports whether a type satisifies an +interface type. +`MissingMethod` is like `Implements`, but instead of +returning false, it explains why a type does not satisfy the +interface, for use in diagnostics. + + + +`AssertableTo` reports whether a type assertion `v.(T)` is legal. +If `T` is a concrete type that doesn't have all the methods of +interface `v`, then the type assertion is not legal, as in this example: + + + // error: io.Writer is not assertible to int + func f(w io.Writer) int { return w.(int) } + + + +## TypeAndValue + + +The type checker records the type of each expression in another field +of the `Info` struct, namely `Types`: + + + type Info struct { + ... + Types map[ast.Expr]TypeAndValue + } + + +No entry is recorded for identifiers since the `Defs` and +`Uses` maps provide more information about them. +Also, no entry is recorded for pseudo-expressions like +`*ast.KeyValuePair` or `*ast.Ellipsis`. + + + +The value of the `Types` map is a `TypeAndValue`, which +(unsurprisingly) holds the `Type` and value of the expression, and in +addition, its _mode_. +The mode is opaque, but has predicates to answer questions such as: +Does this expression denote a value or a type? Does this value have an +address? Does this expression appear on the left-hand side of an +assignment? Does this expression appear in a context that expects two +results? +The comments in the code below give examples of expressions that +satisfy each predicate. + + + type TypeAndValue struct { + Type Type + Value constant.Value // for constant expressions only + ... + } + + func (TypeAndValue) IsVoid() bool // e.g. "main()" + func (TypeAndValue) IsType() bool // e.g. "*os.File" + func (TypeAndValue) IsBuiltin() bool // e.g. "len(x)" + func (TypeAndValue) IsValue() bool // e.g. "*os.Stdout" + func (TypeAndValue) IsNil() bool // e.g. "nil" + func (TypeAndValue) Addressable() bool // e.g. "a[i]" but not "f()", "m[key]" + func (TypeAndValue) Assignable() bool // e.g. "a[i]", "m[key]" + func (TypeAndValue) HasOk() bool // e.g. "<-ch", "m[key]" + + +The statement below inspects every expression within the AST of a single +type-checked file and prints its type, value, and mode: + + + // go get github.com/golang/example/gotypes/typeandvalue + +``` +// f is a parsed, type-checked *ast.File. +ast.Inspect(f, func(n ast.Node) bool { + if expr, ok := n.(ast.Expr); ok { + if tv, ok := info.Types[expr]; ok { + fmt.Printf("%-24s\tmode: %s\n", nodeString(expr), mode(tv)) + fmt.Printf("\t\t\t\ttype: %v\n", tv.Type) + if tv.Value != nil { + fmt.Printf("\t\t\t\tvalue: %v\n", tv.Value) + } + } + } + return true +}) +``` + + +It makes use of these two helper functions, which are not shown: + + + // nodeString formats a syntax tree in the style of gofmt. + func nodeString(n ast.Node) string + + // mode returns a string describing the mode of an expression. + func mode(tv types.TypeAndValue) string + + +Given this input: + + +``` +const input = ` +package main + +var m = make(map[string]int) + +func main() { + v, ok := m["hello, " + "world"] + print(rune(v), ok) +} +` +``` + + +the program prints: + + +``` +$ go build github.com/golang/example/gotypes/typeandvalue +$ ./typeandvalue +make(map[string]int) mode: value + type: map[string]int +make mode: builtin + type: func(map[string]int) map[string]int +map[string]int mode: type + type: map[string]int +m["hello"] mode: value,assignable,ok + type: (int, bool) +m mode: value,addressable,assignable + type: map[string]int +"hello, " + "world" mode: value + type: string + value: "hello, world" +"hello, " mode: value + type: untyped string + value: "hello, " +"world" mode: value + type: untyped string + value: "world" +print(rune(v), ok) mode: void + type: () +print mode: builtin + type: func(rune, bool) +rune(v) mode: value + type: rune +rune mode: type + type: rune +...more not shown... +``` + + +Notice that the identifiers for the built-ins `make` and +`print` have types that are specific to the particular calls in +which they appear. +Also notice `m["hello"]` has a 2-tuple type `(int, bool)` +and that it is assignable, but unlike the variable `m`, it is not +addressable. + + + +Download the example and vary the inputs and see what the program prints. + + + +Here's another example, adapted from the `govet` static checking tool. +It checks for accidental uses of a method value `x.f` when a +call `x.f()` was intended; +comparing a method `x.f` against nil is a common mistake. + + + // go get github.com/golang/example/gotypes/nilfunc + +``` +// CheckNilFuncComparison reports unintended comparisons +// of functions against nil, e.g., "if x.Method == nil {". +func CheckNilFuncComparison(info *types.Info, n ast.Node) { + e, ok := n.(*ast.BinaryExpr) + if !ok { + return // not a binary operation + } + if e.Op != token.EQL && e.Op != token.NEQ { + return // not a comparison + } + + // If this is a comparison against nil, find the other operand. + var other ast.Expr + if info.Types[e.X].IsNil() { + other = e.Y + } else if info.Types[e.Y].IsNil() { + other = e.X + } else { + return // not a comparison against nil + } + + // Find the object. + var obj types.Object + switch v := other.(type) { + case *ast.Ident: + obj = info.Uses[v] + case *ast.SelectorExpr: + obj = info.Uses[v.Sel] + default: + return // not an identifier or selection + } + + if _, ok := obj.(*types.Func); !ok { + return // not a function or method + } + + fmt.Printf("%s: comparison of function %v %v nil is always %v\n", + fset.Position(e.Pos()), obj.Name(), e.Op, e.Op == token.NEQ) +} +``` + + +Given this input, + + +``` +const input = `package main + +import "bytes" + +func main() { + var buf bytes.Buffer + if buf.Bytes == nil && bytes.Repeat != nil && main == nil { + // ... + } +} +` +``` + + +the program reports these errors: + + +``` +$ go build github.com/golang/example/gotypes/nilfunc +$ ./nilfunc +input.go:7:5: comparison of function Bytes == nil is always false +input.go:7:25: comparison of function Repeat != nil is always true +input.go:7:48: comparison of function main == nil is always false +``` + +# Selections + + +A _selection_ is an expression _`expr`_`.f` in which +`f` denotes either a struct field or a method. +A selection is resolved not by looking for a name in the lexical +environment, but by looking within a _type_. +The type checker ascertains the meaning of each selection in the +package---a surprisingly tricky business---and records it in the +`Selections` mapping of the `Info` struct, whose values are +of type `Selection`: + + + type Selection struct{ ... } + func (s *Selection) Kind() SelectionKind // = FieldVal | MethodVal | MethodExpr + func (s *Selection) Recv() Type + func (s *Selection) Obj() Object + func (s *Selection) Type() Type + func (s *Selection) Index() []int + func (s *Selection) Indirect() bool + + +The `Kind` method discriminates between the three (legal) kinds +of selections, as indicated by the comments below. + + + type T struct{Field int} + func (T) Method() {} + var v T + + // Kind Type + var _ = v.Field // FieldVal int + var _ = v.Method // MethodVal func() + var _ = T.Method // MethodExpr func(T) + + +Because of embedding, a selection may denote more than one field or +method, in which case it is ambiguous, and no `Selection` is +recorded for it. + + + +The `Obj` method returns the `Object` for the selected field +(`*Var`) or method (`*Func`). +Due to embedding, the object may belong to a different type than that +of the receiver expression _`expr`_. +The `Type` method returns the type of the selection. For a field +selection, this is the type of the field, but for method selections, +the result is a function type that is not the same as the type of the +method. +For a `MethodVal`, the receiver parameter is dropped, and +for a `MethodExpr`, the receiver parameter becomes a regular +parameter, as shown in the example above. + + + +The `Index` and `Indirect` methods report information about +implicit operations occurring during the selection that a compiler +would need to know about. +Because of embedding, a selection _`expr`_`.f` may be +shorthand for a sequence containing several implicit field selections, +_`expr`_`.d.e.f`, and `Index` reports the complete +sequence. +And because of automatic pointer dereferencing during struct field +accesses and method calls, a selection may imply one or more indirect +loads from memory; `Indirect` reports whether this occurs. + + + +Clients of the type checker can call `LookupFieldOrMethod` to +look up a name within a type, as if by a selection. +This function has an intimidating signature, but conceptually it +accepts just a `Type` and a name, and returns a `Selection`: + + + func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) \ + (obj Object, index []int, indirect bool) + + +The result is not actually a `Selection`, but it contains the +three main components of one: `Obj`, `Index`, +and `Indirect`. + + + +The `addressable` flag should be set if the receiver is a +_variable_ of type `T`, since in a method selection on a +variable, an implicit address-of operation (`&`) may occur. +The flag indicates whether the methods of type `*T` should be +considered during the lookup. + + + +(You may wonder why this parameter is necessary. Couldn't clients +instead call `LookupFieldOrMethod` on the pointer type `*T` +if the receiver is a `T` variable? The answer is that if +`T` is an interface type, the type `*T` has no methods at +all.) + + + +The final two parameters of `LookupFieldOrMethod` are `(pkg +*Package, name string)`. +Together they specify the name of the field or method to look up. +This brings us to `Id`s. + + + +# Ids + + +`LookupFieldOrMethod`'s need for a `Package` parameter +is a subtle consequence of the +[_Uniqueness of identifiers_](https://golang.org/ref/spec#Uniqueness_of_identifiers) +section in the Go spec: "Two +identifiers are different if they are spelled differently, or if they +appear in different packages and are not exported." +In practical terms, this means that a type may have have two methods +(or two fields, or one of each) both named `f` so long as those +methods are defined in different packages, as in this example: + + + package a + type A int + func (A) f() + + package b + type B int + func (B) f() + + package c + import ( "a"; "b" ) + type C struct{a.A; b.B} // C has two methods called f + + +The type `c.C` has two methods named `f`, but there is +no ambiguity because the two `f`s are distinct +identifiers---think of them as `fᵃ` and `fᵇ`. +For an exported method, this situation _would_ be ambiguous +because there is no distinction between `Fᵃ` and `Fᵇ`; there +is only `F`. + + + +Despite having two methods called `f`, neither of them can be +called from within package `c` because `c` has no way to +identify them. +Within `c`, `f` is the identifier `fᶜ`, and +type `C` has no method of that name. +But if we pass an instance of `C` to code in package `a` +and call its `f` method via an interface, `fᵃ` is called. + + + +The practical consequence for tool builders is that any time you need +to look up a field or method by name, or construct a map of fields and/or +methods keyed by name, it is not sufficient to use the object's name +as a key. +Instead, you must call the `Object.Id` method, which returns +a string that incorporates the object name, and for unexported +objects, the package path too. +There is also a standalone function `Id` that combines a name and +the package path in the same way: + + + func Id(pkg *Package, name string) string + + +This distinction applies to selections _`expr`_`.f`, but not +to lexical references `x` because for unexported identifiers, +declarations and references always appear in the same package. + + + +Fun fact: the `reflect.StructField` type records both the +`Name` and the `PkgPath` strings for the same reason. +The `FieldByName` methods of `reflect.Value` and +`reflect.Type` match field names without regard to the package. +If there is more than one match, they return an invalid value. + + + + +# Method Sets + + +The _method set_ of a type is the set of methods that can be +called on any value of that type. +(A variable of type `T` has access to all the methods of type +`*T` as well, due to the implicit address-of operation during +method calls, but those extra methods are not part of the method set +of `T`.) + + + +Clients can request the method set of a type `T` by calling +`NewMethodSet(T)`: + + + type MethodSet struct{ ... } + func NewMethodSet(T Type) *MethodSet + func (s *MethodSet) Len() int + func (s *MethodSet) At(i int) *Selection + func (s *MethodSet) Lookup(pkg *Package, name string) *Selection + + +The `Len` and `At` methods access a a list of +`Selections`, all of kind `MethodVal`, ordered by `Id`. +The `Lookup` function allows lookup of a single method by +name (and package path, as explained in the previous section). + + + +`NewMethodSet` can be expensive, so for applications that compute +method sets repeatedly, `golang.org/x/tools/go/types/typeutil` +provides a `MethodSetCache` type that records previous results. +If you only need a single method, don't construct the +`MethodSet` at all; it's cheaper to use +`LookupFieldOrMethod`. + + + +The next program generates a boilerplate +declaration of a new concrete type that satisifies an existing +interface. +Here's an example: + + +``` +$ ./skeleton io ReadWriteCloser buffer +// *buffer implements io.ReadWriteCloser. +type buffer struct{} +func (b *buffer) Close() error { + panic("unimplemented") +} +func (b *buffer) Read(p []byte) (n int, err error) { + panic("unimplemented") +} +func (b *buffer) Write(p []byte) (n int, err error) { + panic("unimplemented") +} +``` + + +The three arguments are the package and the name of the existing +interface type, and the name of the new concrete type. +The `main` function (not shown) loads the specified package and +calls `PrintSkeleton` with the remaining two arguments: + + + // go get github.com/golang/example/gotypes/skeleton + +``` +func PrintSkeleton(pkg *types.Package, ifacename, concname string) error { + obj := pkg.Scope().Lookup(ifacename) + if obj == nil { + return fmt.Errorf("%s.%s not found", pkg.Path(), ifacename) + } + if _, ok := obj.(*types.TypeName); !ok { + return fmt.Errorf("%v is not a named type", obj) + } + iface, ok := obj.Type().Underlying().(*types.Interface) + if !ok { + return fmt.Errorf("type %v is a %T, not an interface", + obj, obj.Type().Underlying()) + } + // Use first letter of type name as receiver parameter. + if !isValidIdentifier(concname) { + return fmt.Errorf("invalid concrete type name: %q", concname) + } + r, _ := utf8.DecodeRuneInString(concname) + + fmt.Printf("// *%s implements %s.%s.\n", concname, pkg.Path(), ifacename) + fmt.Printf("type %s struct{}\n", concname) + mset := types.NewMethodSet(iface) + for i := 0; i < mset.Len(); i++ { + meth := mset.At(i).Obj() + sig := types.TypeString(meth.Type(), (*types.Package).Name) + fmt.Printf("func (%c *%s) %s%s {\n\tpanic(\"unimplemented\")\n}\n", + r, concname, meth.Name(), + strings.TrimPrefix(sig, "func")) + } + return nil +} +``` + + +First, `PrintSkeleton` locates the package-level named interface +type, handling various error cases. +Then it chooses the name for the receiver of the new methods: the +first letter of the concrete type. +Finally, it iterates over the method set of the interface, printing +the corresponding concrete method declarations. + + + +There's a subtlety in the declaration of `sig`, which is the +string form of the method signature. +We could have obtained this string from `meth.Type().String()`, +but this would cause any named types within it to be formatted with +the complete package path, for instance +`net/http.ResponseWriter`, which is informative in diagnostics +but not legal Go syntax. +The `TypeString` function (explained in [Formatting Values](#formatting-values)) allows the +caller to control how packages are printed. +Passing `(*types.Package).Name` causes only the package name +`http` to be printed, not the complete path. +Here's another example that illustrates it: + + +``` +$ ./skeleton net/http Handler myHandler +// *myHandler implements net/http.Handler. +type myHandler struct{} +func (m *myHandler) ServeHTTP(http.ResponseWriter, *http.Request) { + panic("unimplemented") +} +``` + + +The following program inspects all pairs of package-level named types +in `pkg`, and reports the types that satisfy each interface type. + + + // go get github.com/golang/example/gotypes/implements + +``` +// Find all named types at package level. +var allNamed []*types.Named +for _, name := range pkg.Scope().Names() { + if obj, ok := pkg.Scope().Lookup(name).(*types.TypeName); ok { + allNamed = append(allNamed, obj.Type().(*types.Named)) + } +} + +// Test assignability of all distinct pairs of +// named types (T, U) where U is an interface. +for _, T := range allNamed { + for _, U := range allNamed { + if T == U || !types.IsInterface(U) { + continue + } + if types.AssignableTo(T, U) { + fmt.Printf("%s satisfies %s\n", T, U) + } else if !types.IsInterface(T) && + types.AssignableTo(types.NewPointer(T), U) { + fmt.Printf("%s satisfies %s\n", types.NewPointer(T), U) + } + } +} +``` + + +Given this input, + + + // go get github.com/golang/example/gotypes/implements + +``` +const input = `package main + +type A struct{} +func (*A) f() + +type B int +func (B) f() +func (*B) g() + +type I interface { f() } +type J interface { g() } +` +``` + + +the program prints: + + +``` +$ go build github.com/golang/example/gotypes/implements +$ ./implements +*hello.A satisfies hello.I +hello.B satisfies hello.I +*hello.B satisfies hello.J +``` + + +Notice that the method set of `B` does not include `g`, but +the method set of `*B` does. +That's why we needed the second assignability check, using the pointer +type `types.NewPointer(T)`. + + + +# Constants + + +A constant expression is one whose value is guaranteed to be computed at +compile time. +Constant expressions may appear in types, specifically as the length +of an array type such as `[16]byte`, so one of the jobs of the +type checker is to compute the value of each constant expression. + + + +As we saw in the `typeandvalue` example, the type checker records +the value of each constant expression like `"Hello, " + "world"`, +storing it in the `Value` field of the `TypeAndValue` struct. +Constants are represented using the `Value` interface from the +`go/constant` package. + + + package constant // go/constant + + type Value interface { + Kind() Kind + } + + type Kind int // one of Unknown, Bool, String, Int, Float, Complex + + +The interface has only one method, for discriminating the various +kinds of constants, but the package provides many functions for +inspecting a value of a known kind, + + + // Accessors + func BoolVal(x Value) bool + func Float32Val(x Value) (float32, bool) + func Float64Val(x Value) (float64, bool) + func Int64Val(x Value) (int64, bool) + func StringVal(x Value) string + func Uint64Val(x Value) (uint64, bool) + func Bytes(x Value) []byte + func BitLen(x Value) int + func Sign(x Value) int + + +for performing arithmetic on values, + + + // Operations + func Compare(x Value, op token.Token, y Value) bool + func UnaryOp(op token.Token, y Value, prec uint) Value + func BinaryOp(x Value, op token.Token, y Value) Value + func Shift(x Value, op token.Token, s uint) Value + func Denom(x Value) Value + func Num(x Value) Value + func Real(x Value) Value + func Imag(x Value) Value + + +and for constructing new values: + + + // Constructors + func MakeBool(b bool) Value + func MakeFloat64(x float64) Value + func MakeFromBytes(bytes []byte) Value + func MakeFromLiteral(lit string, tok token.Token, prec uint) Value + func MakeImag(x Value) Value + func MakeInt64(x int64) Value + func MakeString(s string) Value + func MakeUint64(x uint64) Value + func MakeUnknown() Value + + +All numeric `Value`s, whether integer or floating-point, signed or +unsigned, or real or complex, are represented more precisely than the +ordinary Go types like `int64` and `float64`. +Internally, the `go/constant` package uses multi-precision data types +like `Int`, `Rat`, and `Float` from the `math/big` package so that +`Values` and their arithmetic operations are accurate to at least 256 +bits, as required by the Go specification. + + +<!-- TODO example --> + + +# Size and Alignment + + +Because the calls `unsafe.Sizeof(v)`, `unsafe.Alignof(v)`, +and `unsafe.Offsetof(v.f)` are all constant expressions, the type +checker must be able to compute the memory layout of any value +`v`. + + + +By default, the type checker uses the same layout algorithm as the Go +1.5 `gc` compiler targeting `amd64`. +Clients can configure the type checker to use a different algorithm by +providing an instance of the `types.Sizes` interface in the +`types.Config` struct: + + + package types + + type Sizes interface { + Alignof(T Type) int64 + Offsetsof(fields []*Var) []int64 + Sizeof(T Type) int64 + } + + + +For common changes, like reducing the word size to 32 bits, clients +can use an instance of `StdSizes`: + + + type StdSizes struct { + WordSize int64 + MaxAlign int64 + } + + +This type has two basic size and alignment parameters from which it +derives all the other values using common assumptions. +For example, pointers, functions, maps, and channels fit in one word, +strings and interfaces require two words, and slices need three. +The default behaviour is equivalent to `StdSizes{8, 8}`. +For more esoteric layout changes, you'll need to write a new +implementation of the `Sizes` interface. + + + +The `hugeparam` program below prints all function parameters and +results whose size exceeds a threshold. +By default, the threshold is 48 bytes, but you can set it via the +`-bytes` command-line flag. +Such a tool could help identify inefficient parameter passing in your +programs. + + + // go get github.com/golang/example/gotypes/hugeparam + +``` +var bytesFlag = flag.Int("bytes", 48, "maximum parameter size in bytes") + +var sizeof = (&types.StdSizes{8, 8}).Sizeof // the sizeof function + +func PrintHugeParams(fset *token.FileSet, info *types.Info, files []*ast.File) { + checkTuple := func(descr string, tuple *types.Tuple) { + for i := 0; i < tuple.Len(); i++ { + v := tuple.At(i) + if sz := sizeof(v.Type()); sz > int64(*bytesFlag) { + fmt.Printf("%s: %q %s: %s = %d bytes\n", + fset.Position(v.Pos()), + v.Name(), descr, v.Type(), sz) + } + } + } + checkSig := func(sig *types.Signature) { + checkTuple("parameter", sig.Params()) + checkTuple("result", sig.Results()) + } + for _, file := range files { + ast.Inspect(file, func(n ast.Node) bool { + switch n := n.(type) { + case *ast.FuncDecl: + checkSig(info.Defs[n.Name].Type().(*types.Signature)) + case *ast.FuncLit: + checkSig(info.Types[n.Type].Type.(*types.Signature)) + } + return true + }) + } +} +``` + + +As before, `Inspect` applies a function to every node in the AST. +The function cares about two kinds of nodes: declarations of named +functions and methods (`*ast.FuncDecl`) and function literals +(`*ast.FuncLit`). +Observe the two cases' different logic to obtain the type of each +function. + + + +Here's a typical invocation on the standard `encoding/xml` package. +It reports a number of places where the 7-word +[`StartElement` type](https://godoc.org/encoding/xml#StartElement) +is copied. + + +``` +% ./hugeparam encoding/xml +/go/src/encoding/xml/marshal.go:167:50: "start" parameter: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/marshal.go:734:97: "" result: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/marshal.go:761:51: "start" parameter: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/marshal.go:781:68: "start" parameter: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/xml.go:72:30: "" result: encoding/xml.StartElement = 56 bytes +``` + +# Imports + + +The type checker's `Check` function processes a slice of parsed +files (`[]*ast.File`) that make up one package. +When the type checker encounters an import declaration, it needs the +type information for the objects in the imported package. +It gets it by calling the `Import` method of the `Importer` +interface shown below, an instance of which must be provided by the +`Config`. +This separation of concerns relieves the type checker from having to +know any of the details of Go workspace organization, `GOPATH`, +compiler file formats, and so on. + + + type Importer interface { + Import(path string) (*Package, error) + } + + +Most of our examples used the simplest `Importer` implementation, +`importer.Default()`, provided by the `go/importer` package. +This importer looks in `$GOROOT` and `$GOPATH` for `.a` +files written by the compiler (`gc` or `gccgo`) +that was used to build the program. +In addition to object code, these files contain _export data_, +that is, a description of all the objects declared by the package, and +also of any objects from other packages that were referred to indirectly. +Because export data includes information about dependencies, the type +checker need load at most one file per import, instead of one per +transitive dependency. + + + +Compiler export data is compact and efficient to locate, load, and +parse, but it has several shortcomings. +First, it does not contain position information for imported +objects, reducing the quality of certain diagnostic messages. +Second, it does not contain complete syntax trees nor semantic information +about the contents of function bodies, so it is not suitable for +interprocedural analyses. +Third, compiler object data may be stale. Nothing detects or ensures +that the object files are more recent than the source files from which +they were derived. +Generally, object data for standard packages is likely to be +up-to-date, but for user packages, it depends on how recently the user +ran a `go install` or `go build -i` command. + + + +The [`golang.org/tools/x/go/loader` package](https://godoc.org/golang.org/x/tools/go/loader) +provides an alternative `Importer` that addresses +some of these problems. +It loads a complete program from source, performing +[`cgo`](https://golang.org/cmd/cgo/cgo) preprocessing if +necessary, followed by parsing and type-checking. +It loads independent packages in parallel to hide I/O latency, and +detects and reports import cycles. +For each package, it provides the `types.Package` containing the +package's lexical environment, the list of `ast.File` syntax +trees for each file in the package, the `types.Info` containing +type information for each syntax node, and a list of type errors +associated with that package. +(Please be aware that the `go/loader` package's API is likely to +change before it finally stabilizes.) + + + +The `doc` program below demonstrates a simple use of the loader. +It is a rudimentary implementation of `go doc` that prints the type, +methods, and documentation of the package-level object specified on +the command line. +Here's an example: + + +``` +$ ./doc net/http File +type net/http.File interface{Readdir(count int) ([]os.FileInfo, error); Seek(offset int64, whence int) (int64, error); Stat() (os.FileInfo, error); io.Closer; io.Reader} +/go/src/io/io.go:92:2: method (net/http.File) Close() error +/go/src/io/io.go:71:2: method (net/http.File) Read(p []byte) (n int, err error) +/go/src/net/http/fs.go:65:2: method (net/http.File) Readdir(count int) ([]os.FileInfo, error) +/go/src/net/http/fs.go:66:2: method (net/http.File) Seek(offset int64, whence int) (int64, error) +/go/src/net/http/fs.go:67:2: method (net/http.File) Stat() (os.FileInfo, error) + + A File is returned by a FileSystem's Open method and can be +served by the FileServer implementation. + +The methods should behave the same as those on an *os.File. +``` + + +Observe that it prints the correct location of each method +declaration, even though, due to embedding, some of +`http.File`'s methods were declared in another package. +Here's the first part of the program, showing how to load an entire +program starting from the single package, `pkgpath`: + + + // go get github.com/golang/example/gotypes/doc + +``` +pkgpath, name := os.Args[1], os.Args[2] + +// The loader loads a complete Go program from source code. +conf := loader.Config{ParserMode: parser.ParseComments} +conf.Import(pkgpath) +lprog, err := conf.Load() +if err != nil { + log.Fatal(err) // load error +} + +// Find the package and package-level object. +pkg := lprog.Package(pkgpath).Pkg +obj := pkg.Scope().Lookup(name) +if obj == nil { + log.Fatalf("%s.%s not found", pkg.Path(), name) +} +``` + + +Notice that we instructed the parser to retain comments during parsing. +The rest of the program prints the output: + + + // go get github.com/golang/example/gotypes/doc + +``` +// Print the object and its methods (incl. location of definition). +fmt.Println(obj) +for _, sel := range typeutil.IntuitiveMethodSet(obj.Type(), nil) { + fmt.Printf("%s: %s\n", lprog.Fset.Position(sel.Obj().Pos()), sel) +} + +// Find the path from the root of the AST to the object's position. +// Walk up to the enclosing ast.Decl for the doc comment. +_, path, _ := lprog.PathEnclosingInterval(obj.Pos(), obj.Pos()) +for _, n := range path { + switch n := n.(type) { + case *ast.GenDecl: + fmt.Println("\n", n.Doc.Text()) + return + case *ast.FuncDecl: + fmt.Println("\n", n.Doc.Text()) + return + } +} +``` + + +We used `IntuitiveMethodSet` to compute the method set, instead +of `NewMethodSet`. +The result of this convenience function, which is intended for use in +user interfaces, includes methods of `*T` as well as those of +`T`, since that matches most users' intuition about the method +set of a type. +(Our example, `http.File`, didn't illustrate the difference, but try +running it on a type with both value and pointer methods.) + + + +Also notice `PathEnclosingInterval`, which finds the set of AST +nodes that enclose a particular point, in this case, the object's +declaring identifier. +By walking up with path, we find the enclosing declaration, to which +the documentation is attached. + + + +# Formatting support + + +All types that satisfy `Type` or `Object` define a +`String` method that formats the type or object in a readable +notation. `Selection` also provides a `String` method. +All package-level objects within these data structures are +printed with the complete package path, as in these examples: + + + []encoding/json.Marshaler // a *Slice type + encoding/json.Marshal // a *Func object + (*encoding/json.Encoder).Encode // a *Func object (method) + func (enc *encoding/json.Encoder) Encode(v interface{}) error // a method *Signature + func NewEncoder(w io.Writer) *encoding/json.Encoder // a function *Signature + + +This notation is unambiguous, but it is not legal Go syntax. +Also, package paths may be long, and the same package path may appear +many times in a single string, for instance, when formatting a +function of several parameters. +Because these strings often form part of a tool's user interface---as +with the diagnostic messages of `hugeparam` or the code generated +by `skeleton`---many clients want more control over the +formatting of package names. + + + +The `go/types` package provides these alternatives to the +`String` methods: + + + func ObjectString(obj Object, qf Qualifier) string + func TypeString(typ Type, qf Qualifier) string + func SelectionString(s *Selection, qf Qualifier) string + + type Qualifier func(*Package) string + + +The `TypeString`, `ObjectString`, and `SelectionString` +functions are like the `String` methods of the respective types, +but they accept an additional argument, a `Qualifier`. + + + +A `Qualifier` is a client-provided function that determines how a +package name is rendered as a string. +If it is nil, the default behavior is to print the package's +path, just like the `String` methods do. +If a caller passes `(*Package).Name` as the qualifier, that is, a +function that accepts a package and returns its `Name`, then +objects are qualified only by the package name. +The above examples would look like this: + + + []json.Marshaler + json.Marshal + (*json.Encoder).Encode + func (enc *json.Encoder) Encode(v interface{}) error + func NewEncoder(w io.Writer) *json.Encoder + + +Often when a tool prints some output, it is implicitly in the +context of a particular package, perhaps one specified by the +command line or HTTP request. +In that case, it is more natural to omit the package qualification +altogether for objects belonging to that package, but to qualify all +other objects by their package's path. +That's what the `RelativeTo(pkg)` qualifier does: + + + func RelativeTo(pkg *Package) Qualifier + + +The examples below show how `json.NewEncoder` would be printed +using three qualifiers, each relative to a different package: + + + // RelativeTo "encoding/json": + func NewEncoder(w io.Writer) *Encoder + + // RelativeTo "io": + func NewEncoder(w Writer) *encoding/json.Encoder + + // RelativeTo any other package: + func NewEncoder(w io.Writer) *encoding/json.Encoder + + +Another qualifier that may be relevant to refactoring tools (but is +not currently provided by the type checker) is one that renders each +package name using the locally appropriate name within a given source +file. +Its behavior would depend on the set of import declarations, including +renaming imports, within that source file. + + + +# Getting from A to B + + +The type checker and its related packages represent many aspects of a +Go program in many different ways, and analysis tools must often map +between them. +For instance, a named entity may be identified by its `Object`; +by its declaring identifier (`ast.Ident`) or by any referring +identifier; by its declaring `ast.Node`; by the position +(`token.Pos`) of any those nodes; or by the filename and +line/column number (or byte offset) of those `token.Pos` values. + + + +In this section, we'll list solutions to a number of common problems +of the form "I have an A; I need the corresponding B". + + + +To map **from a `token.Pos` to an `ast.Node`**, call the +helper function +[`astutil.PathEnclosingInterval`](https://godoc.org/golang.org/x/tools/go/ast/astutil#PathEnclosingInterval). +It returns the enclosing `ast.Node`, and all its ancestors up to +the root of the file. +You must know which file `*ast.File` the `token.Pos` belongs to. +Alternatively, you can search an entire program loaded by the +`loader` package, using +[`(*loader.Program).PathEnclosingInterval`](https://godoc.org/golang.org/x/tools/go/loader#Program.PathEnclosingInterval). + + + +To map **from an `Object` to its declaring syntax**, call +`Pos` to get its position, then use `PathEnclosingInterval` as before. +This approach is suitable for a one-off query. For repeated use, it +may be more efficient to visit the syntax tree and construct the +mapping between declarations and objects. + + + +To map **from an `ast.Ident` to the `Object`** it refers to (or +declares), consult the `Uses` or `Defs` map for the +package, as shown in [Identifier Resolution](#identifier_resolution). + + + +To map **from an `Object` to its documentation**, find the +object's declaration, and look at the attached `Doc` field. +You must have set the parser's `ParseComments` flag. +See the `doc` example in [Imports](#imports).
diff --git a/gotypes/defsuses/main.go b/gotypes/defsuses/main.go new file mode 100644 index 0000000..608c529 --- /dev/null +++ b/gotypes/defsuses/main.go
@@ -0,0 +1,68 @@ +package main + +import ( + "fmt" + "go/ast" + "go/importer" + "go/parser" + "go/token" + "go/types" + "log" +) + +const hello = `package main + +import "fmt" + +func main() { + fmt.Println("Hello, world") +} +` + +//!+ +func PrintDefsUses(fset *token.FileSet, files ...*ast.File) error { + conf := types.Config{Importer: importer.Default()} + info := &types.Info{ + Defs: make(map[*ast.Ident]types.Object), + Uses: make(map[*ast.Ident]types.Object), + } + _, err := conf.Check("hello", fset, files, info) + if err != nil { + return err // type error + } + + for id, obj := range info.Defs { + fmt.Printf("%s: %q defines %v\n", + fset.Position(id.Pos()), id.Name, obj) + } + for id, obj := range info.Uses { + fmt.Printf("%s: %q uses %v\n", + fset.Position(id.Pos()), id.Name, obj) + } + return nil +} + +//!- + +func main() { + // Parse one file. + fset := token.NewFileSet() + f, err := parser.ParseFile(fset, "hello.go", hello, 0) + if err != nil { + log.Fatal(err) // parse error + } + if err := PrintDefsUses(fset, f); err != nil { + log.Fatal(err) // type error + } +} + +/* +//!+output +$ go build github.com/golang/example/gotypes/defsuses +$ ./defsuses +hello.go:1:9: "main" defines <nil> +hello.go:5:6: "main" defines func hello.main() +hello.go:6:9: "fmt" uses package fmt +hello.go:6:13: "Println" uses func fmt.Println(a ...interface{}) (n int, err error) +//!-output +*/
diff --git a/gotypes/doc/main.go b/gotypes/doc/main.go new file mode 100644 index 0000000..3140f47 --- /dev/null +++ b/gotypes/doc/main.go
@@ -0,0 +1,77 @@ +// The doc command prints the doc comment of a package-level object. +package main + +import ( + "fmt" + "go/ast" + "go/parser" + "log" + "os" + + // TODO: these will use std go/types after Feb 2016 + "golang.org/x/tools/go/loader" + "golang.org/x/tools/go/types/typeutil" +) + +func main() { + if len(os.Args) != 3 { + log.Fatal("Usage: doc <package> <object>") + } + //!+part1 + pkgpath, name := os.Args[1], os.Args[2] + + // The loader loads a complete Go program from source code. + conf := loader.Config{ParserMode: parser.ParseComments} + conf.Import(pkgpath) + lprog, err := conf.Load() + if err != nil { + log.Fatal(err) // load error + } + + // Find the package and package-level object. + pkg := lprog.Package(pkgpath).Pkg + obj := pkg.Scope().Lookup(name) + if obj == nil { + log.Fatalf("%s.%s not found", pkg.Path(), name) + } + //!-part1 + //!+part2 + + // Print the object and its methods (incl. location of definition). + fmt.Println(obj) + for _, sel := range typeutil.IntuitiveMethodSet(obj.Type(), nil) { + fmt.Printf("%s: %s\n", lprog.Fset.Position(sel.Obj().Pos()), sel) + } + + // Find the path from the root of the AST to the object's position. + // Walk up to the enclosing ast.Decl for the doc comment. + _, path, _ := lprog.PathEnclosingInterval(obj.Pos(), obj.Pos()) + for _, n := range path { + switch n := n.(type) { + case *ast.GenDecl: + fmt.Println("\n", n.Doc.Text()) + return + case *ast.FuncDecl: + fmt.Println("\n", n.Doc.Text()) + return + } + } + //!-part2 +} + +/* +//!+output +$ ./doc net/http File +type net/http.File interface{Readdir(count int) ([]os.FileInfo, error); Seek(offset int64, whence int) (int64, error); Stat() (os.FileInfo, error); io.Closer; io.Reader} +/go/src/io/io.go:92:2: method (net/http.File) Close() error +/go/src/io/io.go:71:2: method (net/http.File) Read(p []byte) (n int, err error) +/go/src/net/http/fs.go:65:2: method (net/http.File) Readdir(count int) ([]os.FileInfo, error) +/go/src/net/http/fs.go:66:2: method (net/http.File) Seek(offset int64, whence int) (int64, error) +/go/src/net/http/fs.go:67:2: method (net/http.File) Stat() (os.FileInfo, error) + + A File is returned by a FileSystem's Open method and can be +served by the FileServer implementation. + +The methods should behave the same as those on an *os.File. +//!-output +*/
diff --git a/gotypes/go-types.md b/gotypes/go-types.md new file mode 100644 index 0000000..a00b0fd --- /dev/null +++ b/gotypes/go-types.md
@@ -0,0 +1,2035 @@ + +# `go/types`: The Go Type Checker + +This document is maintained by Alan Donovan `adonovan@google.com`. + +[October 2015 GothamGo talk on go/types](https://docs.google.com/presentation/d/13OvHYozAUBeISPRoLgG7kMBuja1NsU1D_mMlmbaYojk/view) + + +# Contents + +%toc + +# Introduction + + +The [`go/types` package]('https://golang.org/pkg/go/types) is a +type-checker for Go programs, designed by Robert Griesemer. +Measured by lines of code and by API surface area, it is one of the +most complex packages in Go's standard library, and using it requires +a firm grasp of the structure of Go programs. +This tutorial will help you find your bearings. +It comes with several example programs that you can obtain with `go get` and play with. +We assume you are a proficient Go programmer who wants to build tools +to analyze or manipulate Go programs and that you have some knowledge +of how a typical compiler works. + + + +The `go/types` package became part of Go's standard library in Go 1.5. +Prior to that, it was located at +[`golang.org/x/tools/go/types`](https://godoc.org/golang.org/x/tools/go/types), +though that package will be deleted one month after the release +of Go 1.6 in early 2016. + + + +The type checker complements several existing +standard packages for analyzing Go programs. +We've listed them below. + + + → go/types + go/constant + go/parser + go/ast + go/scanner + go/token + + +Starting at the bottom, the +[`go/token` package](http://golang.org/pkg/go/token) +defines the lexical tokens of Go. +The [`go/scanner` package](http://golang.org/pkg/go/scanner) tokenizes an input stream and records +file position information for use in diagnostics +or for file surgery in a refactoring tool. +The [`go/ast` package](http://golang.org/pkg/go/ast) +defines the data types of the abstract syntax tree (AST). +The [`go/parser` package](http://golang.org/pkg/go/parser) +provides a robust recursive-descent parser that constructs the AST. +And [`go/constant`](http://golang.org/pkg/go/constant) +provides representations and arithmetic operations for the values of compile-time +constant expressions, as we'll see in +[Constants](#constants). + + + +The [`golang.org/x/tools/go/loader` package](https://godoc.org/golang.org/x/tools/go/loader) +from the `x/tools` repository is a client of the type +checker that loads, parses, and type-checks a complete Go program from +source code. +We use it in some of our examples and you may find it useful too. +(Please note that until March 2016, the +`golang.org/x/tools/...` packages will continue to depend on the +old `golang.org/x/tools/go/types` package, not on the +new standard `go/types` package. The two are almost identical.) + + + +The Go type checker does three main things. +First, for every name in the program, it determines which declaration +the name refers to; this is known as _identifier resolution_. +Second, for every expression in the program, it determines what type +that expression has, or reports an error if the expression has no +type, or has an inappropriate type for its context; this is known as +_type deduction_. +Third, for every constant expression in the program, it determines the +value of that constant; this is known as _constant evaluation_. + + + +Superficially, it appears that these three processes could be done +sequentially, in the order above, but perhaps surprisingly, they must +be done together. +For example, the value of a constant may depend on the type of an +expression due to operators like `unsafe.Sizeof`. +Conversely, the type of an expression may depend on the value of a +constant, since array types contain constants. +As a result, type deduction and constant evaluation must be done +together. + + + +As another example, we cannot resolve the identifier `k` in the composite +literal `T{k: 0}` until we know whether `T` is a struct type. +If it is, then `k` must be found among `T`'s fields. +If not, then `k` is an ordinary reference +to a constant or variable in the lexical environment. +Consequently, identifier resolution and type deduction are also +inseparable in the general case. + + + +Nonetheless, the three processes of identifier resolution, type +deduction, and constant evaluation can be separated for the purpose of +explanation. + + +# An Example + + +The code below shows the most basic use of the type checker to check +the _hello, world_ program, supplied as a string. +Later examples will be variations on this one, and we'll often omit +boilerplate details such as parsing. +To check out and build the examples, +run `go get github.com/golang/example/gotypes/...`. + + +%include pkginfo/main.go + + +First, the program creates a +[`token.FileSet`](http://golang.org/pkg/go/token/#FileSet). +To avoid the need to store file names and line and column +numbers in every node of the syntax tree, the `go/token` package +provides `FileSet`, a data structure that stores this information +compactly for a sequence of files. +A `FileSet` records each file name only once, and records +only the byte offsets of each newline, allowing a position within +any file to be identified using a small integer called a +`token.Pos`. +Many tools create a single `FileSet` at startup. +Any part of the program that needs to convert a `token.Pos` into +an intelligible location---as part of an error message, for +instance---must have access to the `FileSet`. + + + +Second, the program parses the input string. +More realistic packages contain several source files, so the parsing +step must be repeated for each one, or better still, done in parallel. +Third, it creates a `Config` that specifies type-checking options. +Since the _hello, world_ program uses imports, we must indicate +how to locate the imported packages. +Here we use `importer.Default()`, which loads compiler-generated +export data, but we'll explore alternatives in [Imports](#imports). + + + +Fourth, the program calls `Check`. +This creates a `Package` whose path is `"cmd/hello"`, and +type-checks each of the specified files---just one in this example. +The final (nil) argument is a pointer to an optional `Info` +struct that returns additional deductions from the type checker; more +on that later. +`Check` returns a `Package` even when it also returns an error. +The type checker is robust to ill-formed input, +and goes to great lengths to report accurate +partial information even in the vicinity of syntax or type errors. +`Package` has this definition: + + + type Package struct{ ... } + func (*Package) Path() string + func (*Package) Name() string + func (*Package) Scope() *Scope + func (*Package) Imports() []*Package + + +Finally, the program prints the attributes of the package, shown below. +(The hexadecimal number may vary from one run to the next.) + + +%include pkginfo/main.go output - + + +A package's `Path`, such as `"encoding/json"`, is the string +by which import declarations identify it. +It is unique within a `$GOPATH` workspace, +and for published packages it must be globally unique. + + +A package's `Name` is the identifier in the `package` +declaration of each source file within the package, such as `json`. +The type checker reports an error if not all the package declarations in +the package agree. +The package name determines how the package is known when it is +imported into a file (unless a renaming import is used), +but is otherwise not visible to a program. + + +`Scope` returns the package's [_lexical block_](#scopes), +which provides access to all the named entities or +[_objects_](#objects) declared at package level. +`Imports` returns the set of packages directly imported by this +one, and may be useful for computing dependencies +([Initialization Order](#initialization_order)). + + + +# Objects + + +The task of identifier resolution is to map every identifier in the +syntax tree, that is, every `ast.Ident`, to an object. +For our purposes, an _object_ is a named entity created by a +declaration, such as a `var`, `type`, or `func` +declaration. +(This is different from the everyday meaning of object in +object-oriented programming.) + + + +Objects are represented by the `Object` interface, shown below: + + + type Object interface { + Name() string // package local object name + Exported() bool // reports whether the name starts with a capital letter + Type() Type // object type + Pos() token.Pos // position of object identifier in declaration + + Parent() *Scope // scope in which this object is declared + Pkg() *Package // nil for objects in the Universe scope and labels + Id() string // object id (see Ids section below) + } + + +The first four methods are straightforward; we'll explain the other +three later. +`Name` returns the objects's name---an identifier. +`Exported` is a convenience method that reports whether the first +letter of `Name` is a capital, indicating that the object may be +visible from outside the package. +It's a shorthand for `ast.IsExported(obj.Name())`. +`Type` returns the object's type; we'll come back to that in +[Types](#types). + + + +`Pos` returns the source position of the object's declaring identifier. +To make sense of a `token.Pos`, we need to call the +`(*token.FileSet).Position` method, which returns a struct with +individual fields for the file name, line number, column, and byte +offset, though usually we just call its `String` method: + + + fmt.Fprintln(fset.Position(obj.Pos())) // "hello.go:10:6" + + +Not all objects carry position information. +Since the file format for compiler export data ([Imports](#imports)) +does not record position information, calling `Pos` on an object +imported from such a file returns zero, also known as +`token.NoPos`. + + + +There are eight kinds of objects in the Go type checker. +Most familiar are the kinds that can be declared at package level: +constants, variables, functions, and types. +Less familiar are statement labels, imported package names +(such as `json` in a file containing an `import "encoding/json"` +declaration), built-in functions (such as `append` and +`len`), and the pre-declared `nil`. +The eight types shown below are the only concrete types that satisfy +the `Object` interface. +In other words, `Object` is a _discriminated union_ of 8 +possible types, and we commonly use a type switch to distinguish them. + + + Object = *Func // function, concrete method, or abstract method + | *Var // variable, parameter, result, or struct field + | *Const // constant + | *TypeName // named type (except for predeclared ones) + | *Label // statement label + | *PkgName // package name, e.g. json after import "encoding/json" + | *Builtin // predeclared function such as append or len + | *Nil // predeclared nil + + +`Object`s are canonical. +That is, two `Object`s `x` and `y` denote the same +entity if and only if `x==y`. +Object identity is significant, and objects are routinely compared by +the addresses of the underlying pointers. +Although a package-level object is uniquely identified by its name +and enclosing package, for other objects there is no simple way to +obtain a string that uniquely identifies it. + + + +The `Parent` method returns the `Scope` (lexical block) in +which the object was declared; we'll come back to this in +[Scopes](#scopes). +Fields and methods are not found in the lexical environment, so +their objects have no `Parent`. + + + +The `Pkg` method returns the `Package` to which this object +belongs, even for objects not declared at package level. +Only predeclared objects have no package. +The `Id` method will be explained in [Ids](#ids). + + + +Not all methods make sense for each kind of object. For instance, +the last four kinds above have no meaningful `Type` method. +And some kinds of object have methods in addition to those required by the +`Object` interface: + + + func (*Func) Scope() *Scope + func (*Var) Anonymous() bool + func (*Var) IsField() bool + func (*Const) Val() constant.Value + func (*PkgName) Imported() *Package + + +`(*Func).Scope` returns the [lexical block](#scopes) +containing the function's parameters, results, +and other local declarations. +`(*Var).IsField` distinguishes struct fields from ordinary +variables, and `(*Var).Anonymous` discriminates named fields like +the one in `struct{T T}` from anonymous fields like the one in `struct{T}`. +`(*Const).Val` returns the value of a named [constant](#constants). + + + +`(*PkgName).Imported` returns the package (for instance, +`encoding/json`) denoted by a given import name such as `json`. +Each time a package is imported, a new `PkgName` object is +created, usually with the same name as the `Package` it +denotes, but not always, as in the case of a renaming import. +`PkgName`s are objects, but `Package`s are not. +We'll look more closely at this in [Imports](#imports). + + + +All relationships between the syntax trees (`ast.Node`s) and type +checker data structures such as `Object`s and `Type`s are +stored in mappings outside the syntax tree itself. +Be aware that the `go/ast` package also defines a type called +`Object` that resembles---and predates---the type checker's +`Object`, and that `ast.Object`s are held directly by +identifiers in the AST. +They are created by the parser, which has a necessarily limited view +of the package, so the information they represent is at best partial and +in some cases wrong, as in the `T{k: 0}` example mentioned above. +If you are using the type checker, there is no reason to use the older +`ast.Object` mechanism. + + + +# Identifier Resolution + + +Identifier resolution computes the relationship between +identifiers and objects. +Its results are recorded in the `Info` struct optionally passed +to `Check`. +The fields related to identifier resolution are shown below. + + + type Info struct { + Defs map[*ast.Ident]Object + Uses map[*ast.Ident]Object + Implicits map[ast.Node]Object + Selections map[*ast.SelectorExpr]*Selection + Scopes map[ast.Node]*Scope + ... + } + + +Since not all facts computed by the type checker are needed by every +client, the API lets clients control which components of the result +should be recorded and which discarded: only fields that hold a +non-nil map will be populated during the call to `Check`. + + + +The two fields of type `map[*ast.Ident]Object` are the most important: +`Defs` records _declaring_ identifiers and +`Uses` records _referring_ identifiers. +In the example below, the comments indicate which identifiers are of +which kind. + + + var x int // def of x, use of int + fmt.Println(x) // uses of fmt, Println, and x + type T struct{U} // def of T, use of U (type), def of U (field) + + +The final line above illustrates why we don't combine `Defs` and +`Uses` into one map. +In the anonymous field declaration `struct{U}`, the +identifier `U` is both a use of the type `U` (a +`TypeName`) and a definition of the anonymous field (a +`Var`). + + + +The function below prints the location of each referring and defining +identifier in the input program, and the object it refers to. + + +%include defsuses/main.go + + +Let's use the _hello, world_ program again as the input: + + +%include hello/hello.go + + +This is what it prints: + + +%include defsuses/main.go output - + + +Notice that the `Defs` mapping may contain nil entries in a few +cases. +The first line of output reports that the package identifier +`main` is present in the `Defs` mapping, but has no +associated object. + + + +The `Implicits` mapping handles two cases of the syntax in +which an `Object` is declared without an `ast.Ident`, namely type +switches and import declarations. +<!-- +A third case: an anonymous function parameter or result variable. +These objects are returned by Signature.Param and Signature.Result. +--> +In the type switch below, which declares a local variable `y`, +the type of `y` is different in each case of the switch: + + + switch y := x.(type) { + case int: + fmt.Printf("%d", y) + case string: + fmt.Printf("%q", y) + default: + fmt.Print(y) + } + + +To represent this, for each single-type case, the type checker creates +a separate `Var` object for `y` with the appropriate type, +and `Implicits` maps each `ast.CaseClause` to the `Var` +for that case. +The `default` case, the `nil` case, and cases with more than one +type all use the regular `Var` object that is associated with the +identifier `y`, which is found in the `Defs` mapping. + + + +The import declaration below defines the name `json` without an +`ast.Ident`: + + + import "encoding/json" + + +`Implicits` maps this `ast.ImportSpec` to the `PkgName` +object named `json` that it implicitly declares. + + + +The `Selections` mapping, of type +`map[*ast.SelectorExpr]*Selection`, records the meaning of each +expression of the form _`expr`_`.f`, where _`expr`_ is +an expression or type and `f` is the name of a field or method. +These expressions, called _selections_, are represented by +`ast.SelectorExpr` nodes in the AST. +We'll talk more about the `Selection` type in [Selections](#selections). + + + +Not all `ast.SelectorExpr` nodes represent selections. +Expressions like `fmt.Println`, in which a package name precedes +the dot, are _qualified identifiers_. +They do not appear in the `Selections` mapping, but their +constituent identifiers (such as `fmt` and `Println`) both +appear in `Uses`. + + + +Referring identifiers that are not part of an `ast.SelectorExpr` +are _lexical references_. +That is, they are resolved to an object by searching for the +innermost enclosing lexical declaration of that name. +We'll see how that search works in the next section. + + +# Scopes + + +The `Scope` type is a mapping from names to objects. + + + type Scope struct{ ... } + + func (s *Scope) Names() []string + func (s *Scope) Lookup(name string) Object + + +`Names` returns the set of names in the mapping, in sorted order. +(It is not a simple accessor though, so call it sparingly.) +The `Lookup ` method returns the object for a given name, so we +can print all the entries or _bindings_ in a scope like this: + + + for _, name := range scope.Names() { + fmt.Println(scope.Lookup(name)) + } + + +The _scope_ of a declaration of a name is the region of +program source in which a reference to the name resolves to that +declaration. That is, scope is a property of a declaration. +However, in the `go/types` API, the `Scope` type represents +a _lexical block_, which is one component of the lexical +environment. +Consider the _hello, world_ program again: + + + package main + + import "fmt" + + func main() { + const message = "hello, world" + fmt.Println(message) + } + + +There are four lexical blocks in this program. +The outermost one is the _universe block_, which maps the +pre-declared names like `int`, `true`, and `append` to +their objects---a `TypeName`, a `Const`, and a +`Builtin`, respectively. +The universe block is represented by the global variable +`Universe`, of type `*Scope`, although it's logically a +constant so you shouldn't modify it. + + + +Next is the _package block_, which maps `"main"` to the +`main` function. +Following that is the _file block_, which maps `"fmt"` to +the `PkgName` object for this import of the `fmt` package. +And finally, the innermost block is that of function `main`, a +local block, which contains the declaration of `message`, a `Const`. +The `main` function is trivial, but many functions contain +several blocks since each `if`, `for`, `switch`, +`case`, or `select` statement creates at least one +additional block. +Local blocks nest to arbitrary depths. + + + +The structure of the lexical environment thus forms a tree, with the +universe block at the root, the package blocks beneath it, the file +blocks beneath them, and then any number of local blocks beneath the +files. +The following methods of `Scope` make this tree structure +accessible and navigable: + + + func (s *Scope) Parent() *Scope + func (s *Scope) NumChildren() int + func (s *Scope) Child(i int) *Scope + + +`Parent` lets us walk up the tree, and `Child` +lets us walk down it. +Note that although the `Parent` of every package `Scope` is +`Universe`, `Universe` has no children. +This asymmetry is a consequence of using a global variable to hold +`Universe`. + + + +To obtain the universe block, we use the `Universe` global variable. +To obtain the lexical block of a `Package`, we call its +`Scope` method. +To obtain the scope of a file (`*ast.File`), or any smaller piece +of syntax such as an `*ast.IfStmt`, we consult the `Scopes` +mapping in the `Info` struct, which maps each block-creating +syntax node to its block. +The lexical block of a named function or method can also be obtained +by calling its `(*Func).Scope` method. + + +<!-- +TODO: explain explicit and implicit blocks +TODO: explain Dot imports. +TODO: explain that Func blocks are associated with FuncType (not FuncDecl or FuncLit) +--> + + +To look up a name in the lexical environment, we must search the tree +of lexical blocks, starting at a particular `Scope` and walking +up to the root until a declaration of the name is found. +For convenience, the `LookupParent` method does this, returning +not just the object, if found, but also the `Scope` in which it was +declared, which may be an ancestor of the initial one: + + + func (s *Scope) LookupParent(name string, pos token.Pos) (*Scope, Object) + + +The `pos` parameter determines the position in the source code at +which the name should be resolved. +The effective lexical environment is different at each point in the +block because it depends on which local declarations appear +before or after that point. +(We'll see an illustration in a moment.) + + + +`Scope` has several other methods relating to source positions: + + + func (s *Scope) Pos() token.Pos + func (s *Scope) End() token.Pos + func (s *Scope) Contains(pos token.Pos) bool + func (s *Scope) Innermost(pos token.Pos) *Scope + + +`Pos` and `End` report the `Scope`'s start and end +position which, for explicit blocks, are coincident with its curly +braces. +`Contains` is a convenience method that reports whether a +position lies in this interval. +`Innermost` returns the innermost scope containing the specified +position, which may be a child or other descendent of the initial +scope. + + + +These features are useful for tools that wish to resolve names or +evaluate constant expressions as if they had appeared at a particular +point within the program. +The next example program finds all the comments in the input, +treating the contents of each one as a name. It looks up each name in +the environment at the position of the comment, and prints what it +finds. +Observe that the `ParseComments` flag directs the parser to +preserve comments in the input. + + +%include lookup/lookup.go main + + +The expression `pkg.Scope().Innermost(pos)` finds the innermost +`Scope` that encloses the comment, and `LookupParent(name, pos)` +does a name lookup at a specific position in that lexical block. + + + +A typical input is shown below. +The first comment causes a lookup of `"append"` in the file block. +The second comment looks up `"fmt"` in the `main` function's block, +and so on. + + +%include lookup/lookup.go input - + + +Here's the output: + + +%include lookup/lookup.go output - + + +Notice how the two lookups of `main` return different results, +even though they occur in the same block, because one precedes the +declaration of the local variable named `main` and the other +follows it. +Also notice that there are two lookups of the name `x` but only +the first one, in the function block, succeeds. + + + +Download the program and modify both the input program and +the set of comments to get a better feel for how name resolution works. + + + +The table below summarizes which kinds of object may be declared at +each level of the tree of lexical blocks. + + + Universe File Package Local + Builtin ✔ + Nil ✔ + Const ✔ ✔ ✔ + TypeName ✔ ✔ ✔ + Func ✔ + Var ✔ ✔ + PkgName ✔ + Label ✔ + +# Initialization Order + + +In the course of identifier resolution, the type checker constructs a +graph of references among declarations of package-level variables and +functions. +The type checker reports an error if the initializer expression for a +variable refers to that variable, whether directly or indirectly. + + + +The reference graph determines the initialization order of the +package-level variables, as required by the Go spec, using a +breadth-first algorithm. +First, variables in the graph with no successors are removed, sorted +into the order in which they appear in the source code, then added +to a list. This creates more variables that have no successors. +The process repeats until they have all been removed. + + + +The result is available in the `InitOrder` field of the +`Info` struct, whose type is `[]Initializer`. + + + type Info struct { + ... + InitOrder []Initializer + ... + } + + type Initializer struct { + Lhs []*Var // var Lhs = Rhs + Rhs ast.Expr + } + + +Each element of the list represents a single initializer expression +that must be executed, and the variables to which it is assigned. +The variables may number zero, one, or more, as in these examples: + + + var _ io.Writer = new(bytes.Buffer) + var rx = regexp.MustCompile("^b(an)*a$") + var cwd, cwdErr = os.Getwd() + + +This process governs the initialization order of variables within a +package. +Across packages, dependencies must be initialized first, although the +order among them is not specified. +That is, any topological order of the import graph will do. +The `(*Package).Imports` method returns the set of direct +dependencies of a package, in an unspecified order. + + +# Types + + +The main job of the type checker is, of course, to deduce the type +of each expression and to report type errors. +Like `Object`, `Type` is an interface type used as a +discriminated union of several concrete types but, unlike +`Object`, `Type` has very few methods because types have +little in common with each other. +Here is the interface: + + + type Type interface { + Underlying() Type + } + + +And here are the eleven concrete types that satisfy it: + + + Type = *Basic + | *Pointer + | *Array + | *Slice + | *Map + | *Chan + | *Struct + | *Tuple + | *Signature + | *Named + | *Interface + + +With the exception of `Named` types, instances of `Type` are +not canonical. +That is, it is usually a mistake to compare types using `t1==t2` +since this equivalence is not the same as the +[type identity relation](https://golang.org/ref/spec#Type_identity) +defined by the Go spec. +Use this function instead: + + + func Identical(t1, t2 Type) bool + + +For the same reason, you should not use a `Type` as a key in a map. +The [`golang.org/x/tools/go/types/typeutil` package](https://godoc.org/golang.org/x/tools/go/types/typeutil) +provides a map keyed by types that uses the correct +equivalence relation. + + +The Go spec defines three relations over types. +[_Assignability_](https://golang.org/ref/spec#Assignability) +governs which pairs of types may appear on the +left- and right-hand side of an assignment, including implicit +assignments such as function calls, map and channel operations, and so +on. +[_Comparability_](https://golang.org/ref/spec#Comparison_operators) +determines which types may appear in a comparison `x==y` or a +switch case or may be used as a map key. +[_Convertibility_](https://golang.org/ref/spec#Conversions) +governs which pairs of types are allowed in a conversion operation +`T(v)`. +You can query these relations with the following predicate functions: + + + func AssignableTo(V, T Type) bool + func Comparable(T Type) bool + func ConvertibleTo(V, T Type) bool + + +Let's take a look at each kind of type. + + +## Basic types + + +`Basic` represents all types that are not composed from simpler +types. +This is essentially the set of underlying types that a constant expression is +permitted to have--strings, booleans, and numbers---but it also +includes `unsafe.Pointer` and untyped nil. + + + type Basic struct{...} + func (*Basic) Kind() BasicKind + func (*Basic) Name() string + func (*Basic) Info() BasicInfo + + +The `Kind` method returns an "enum" value that indicates which +basic type this is. +The kinds `Bool`, `String`, `Int16`, and so on, +represent the corresponding predeclared boolean, string, or numeric +types. +There are two synonyms: `Byte` is equivalent to `Uint8` +and `Rune` is equivalent to `Int32`. +The kind `UnsafePointer` represents `unsafe.Pointer`. +The kinds `UntypedBool`, `UntypedInt` and so on represent +the six kinds of "untyped" constant types: boolean, integer, rune, +float, complex, and string. +The kind `UntypedNil` represents the type of the predeclared +`nil` value. +And the kind `Invalid` indicates the invalid type, which is used +for expressions containing errors, or for objects without types, like +`Label`, `Builtin`, or `PkgName`. + + + +The `Name` method returns the name of the type, such as +`"float64"`, and the `Info` method returns a bitfield that +encodes information about the type, such as whether it is signed or +unsigned, integer or floating point, real or complex. + + + +`Typ` is a table of canonical basic types, indexed by +kind, so `Typ[String]` returns the `*Basic` that represents +`string`, for instance. +Like `Universe`, `Typ` is logically a constant, so don't +modify it. + + + +A few minor subtleties: +According to the Go spec, pre-declared types such as `int` are +named types for the purposes of assignability, even though the type +checker does not represent them using `Named`. +And `unsafe.Pointer` is a pointer type for the purpose of +determining whether the receiver type of a method is legal, even +though the type checker does not represet it using `Pointer`. + + + +The "untyped" types are usually only ascribed to constant expressions, +but there is one exception. +A comparison `x==y` has type "untyped bool", so the result of +this expression may be assigned to a variable of type `bool` or +any other named boolean type. + + + +## Simple Composite Types + + +The types `Pointer`, `Array`, `Slice`, `Map`, +and `Chan` are pretty self-explanatory. +All have an `Elem` method that returns the element type `T` +for a pointer `*T`, an array `[n]T`, a slice `[]T`, a +map `map[K]T`, or a channel `chan T`. +This should feel familiar if you've used the `reflect.Value` API. + + + +In addition, the `*Map`, `*Chan`, and `*Array` types +have accessor methods that return their key type, direction, and +length, respectively: + + + func (*Map) Key() Type + func (*Chan) Dir() ChanDir // = Send | Recv | SendRecv + func (*Array) Len() int64 + + + +## Struct Types + + +A struct type has an ordered list of fields and a corresponding +ordered list of field tags. + + + type Struct struct{ ... } + func (*Struct) NumFields() int + func (*Struct) Field(i int) *Var + func (*Struct) Tag(i int) string + + +Each field is a `Var` object whose `IsField` method returns true. +Field objects have no `Parent` scope, because they are +resolved through selections, not through the lexical environment. + + + +Thanks to embedding, the expression `new(S).f` may be a shorthand +for a longer expression such as `new(S).d.e.f`, but in the +representation of `Struct` types, these field selection +operations are explicit. +That is, the set of fields of struct type `S` does not include `f`. +An anonymous field is represented like a regular field, but its +`Anonymous` method returns true. + + + +One subtlety is relevent to tools that generate documentation. +When analyzing a declaration such as this, + + + type T struct{x int} + + +it may be tempting to consider the `Var` object for field `x` as if it +had the name `"T.x"`, but beware: field objects do not have +canonical names and there is no way to obtain the name `"T"` +from the `Var` for `x`. +That's because several types may have the same underlying struct type, +as in this code: + + + type T struct{x int} + type U T + + +Here, the `Var` for field `x` belongs equally to `T` +and to `U`, and short of inspecting source positions or walking +the AST---neither of which is possible for objects loaded from compiler +export data---it is not possible to ascertain that `x` was declared as +part of `T`. +The type checker computes the exact same data structures given this input: + + + type T U + type U struct{x int} + + +A similar issue applies to the methods of named interface types. + + +## Tuple Types + + +Like a struct, a tuple type has an ordered list of fields, and fields +may be named. + + + type Tuple struct{ ... } + func (*Tuple) Len() int + func (*Tuple) At(i int) *Var + + +Although tuples are not the type of any variable in Go, they are +the type of some expressions, such as the right-hand sides of these +assignments: + + + v, ok = m[key] + v, ok = <-ch + v, ok = x.(T) + f, err = os.Open(filename) + + +Tuples also represent the types of the parameter list and the result +list of a function, as we will see. + + + +Since empty tuples are common, the nil `*Tuple` pointer is a valid empty tuple. + + + +## Function and Method Types + + +The types of functions and methods are represented by a `Signature`, +which has a tuple of parameter types and a tuple of result types. + + + type Signature struct{ ... } + func (*Signature) Recv() *Var + func (*Signature) Params() *Tuple + func (*Signature) Results() *Tuple + func (*Signature) Variadic() bool + + +Variadic functions such as `fmt.Println` have the `Variadic` +flag set. +The final parameter of such functions is always a slice, or in the +special case of certain calls to `append`, a string. + + + +A `Signature` for a method, whether concrete or abstract, has a +non-nil receiver parameter, `Recv`. +The type of the receiver is usually a named type or a pointer to a named type, +but it may be an unnamed struct or interface type in some cases. +Method types are rather second-class: they are only used for the +`Func` objects created by method declarations, and no Go +expression has a method type. +When printing a method type, the receiver does not appear, and the +`Identical` predicate ignores the receiver. + + + +The types of `Builtin` objects like `append` cannot be +expressed as a `Signature` since those types require parametric +polymorphism. +`Builtin` objects are thus ascribed the `Invalid` basic type. +However, the type of each _call_ to a built-in function has a specific +and expressible Go type. +These types are recorded during type checking for later use +([TypeAndValue](#typeandvalue)). + + + +## Named Types + + +A type declaration creates a `TypeName` object, and the type of +that object is a `Named`. +These two entities, an object and a type, are distinct but closely +related, and they exist in one-to-one correpondence. + + + type Named struct{ ... } + func (*Named) NumMethods() int + func (*Named) Method(i int) *Func + func (*Named) Obj() *TypeName + func (*Named) Underlying() Type + + +The `Named` type's `Obj` method returns the `TypeName` object, which +provides the name, position, and other properties of the declaration. +Conversely, the `TypeName` object's `Type` method returns the `Named` type. + + + +The `NumMethods` and `Method` methods enumerate the declared +methods associated with this `Named` type (or a pointer to it), +in the order they were declared. +However, due to the subtleties of anonymous fields and the difference +between value and pointer receivers, a named type may have more or fewer +methods than this list. We'll return to this in [Method Sets](#method_sets). + + + +Every `Type` has an `Underlying` method, but for all of them +except `*Named`, it is simply the identity function. +For a named type, `Underlying` returns its underlying type, which +is always an unnamed type. +Thus `Underlying` returns `int` for both `T` and +`U` below. + + + type T int + type U T + + +Clients of the type checker often use type assertions or type switches +with a `Type` operand. +When doing so, it is often necessary to switch on the type that +_underlies_ the type of interest, and failure to do so may be a +bug. + +This is a common pattern: + + + // handle types of composite literal + switch u := t.Underlying().(type) { + case *Struct: // ... + case *Map: // ... + case *Array, *Slice: // ... + default: + panic("impossible") + } + +## Interface Types + + +Interface types are represented by `Interface`. + + + type Interface struct{ ... } + func (*Interface) Empty() bool + func (*Interface) NumMethods() int + func (*Interface) Method(i int) *Func + func (*Interface) NumEmbeddeds() int + func (*Interface) Embedded(i int) *Named + func (*Interface) NumExplicitMethods() int + func (*Interface) ExplicitMethod(i int) *Func + + +Syntactically, an interface type has a list of explicitly declared +methods (`ExplicitMethod`), and a list of embedded named +interface types (`Embedded`), but many clients care only about +the complete set of methods, which can be enumerated via +`Method`. +All three lists are ordered by name. +Since the empty interface is an important special case, the +`Empty` predicate provides a shorthand for `NumMethods() == +0`. + + + +As with the fields of structs (see above), the methods of interfaces +may belong equally to more than one interface type. +The `Func` object for method `f` in the code below is shared +by `I` and `J`: + + + type I interface { f() } + type J I + + +Because the difference between interface (abstract) and +non-interface (concrete) types is so important in Go, the +`IsInterface` predicate is provided for convenience. + + + func IsInterface(Type) bool + + +The type checker provides three utility methods relating to interface +satisfaction: + + + func Implements(V Type, T *Interface) bool + func AssertableTo(V *Interface, T Type) bool + func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) + + +The `Implements` predicate reports whether a type satisifies an +interface type. +`MissingMethod` is like `Implements`, but instead of +returning false, it explains why a type does not satisfy the +interface, for use in diagnostics. + + + +`AssertableTo` reports whether a type assertion `v.(T)` is legal. +If `T` is a concrete type that doesn't have all the methods of +interface `v`, then the type assertion is not legal, as in this example: + + + // error: io.Writer is not assertible to int + func f(w io.Writer) int { return w.(int) } + + + +## TypeAndValue + + +The type checker records the type of each expression in another field +of the `Info` struct, namely `Types`: + + + type Info struct { + ... + Types map[ast.Expr]TypeAndValue + } + + +No entry is recorded for identifiers since the `Defs` and +`Uses` maps provide more information about them. +Also, no entry is recorded for pseudo-expressions like +`*ast.KeyValuePair` or `*ast.Ellipsis`. + + + +The value of the `Types` map is a `TypeAndValue`, which +(unsurprisingly) holds the `Type` and value of the expression, and in +addition, its _mode_. +The mode is opaque, but has predicates to answer questions such as: +Does this expression denote a value or a type? Does this value have an +address? Does this expression appear on the left-hand side of an +assignment? Does this expression appear in a context that expects two +results? +The comments in the code below give examples of expressions that +satisfy each predicate. + + + type TypeAndValue struct { + Type Type + Value constant.Value // for constant expressions only + ... + } + + func (TypeAndValue) IsVoid() bool // e.g. "main()" + func (TypeAndValue) IsType() bool // e.g. "*os.File" + func (TypeAndValue) IsBuiltin() bool // e.g. "len(x)" + func (TypeAndValue) IsValue() bool // e.g. "*os.Stdout" + func (TypeAndValue) IsNil() bool // e.g. "nil" + func (TypeAndValue) Addressable() bool // e.g. "a[i]" but not "f()", "m[key]" + func (TypeAndValue) Assignable() bool // e.g. "a[i]", "m[key]" + func (TypeAndValue) HasOk() bool // e.g. "<-ch", "m[key]" + + +The statement below inspects every expression within the AST of a single +type-checked file and prints its type, value, and mode: + + +%include typeandvalue/main.go inspect + + +It makes use of these two helper functions, which are not shown: + + + // nodeString formats a syntax tree in the style of gofmt. + func nodeString(n ast.Node) string + + // mode returns a string describing the mode of an expression. + func mode(tv types.TypeAndValue) string + + +Given this input: + + +%include typeandvalue/main.go input - + + +the program prints: + + +%include typeandvalue/main.go output - + + +Notice that the identifiers for the built-ins `make` and +`print` have types that are specific to the particular calls in +which they appear. +Also notice `m["hello"]` has a 2-tuple type `(int, bool)` +and that it is assignable, but unlike the variable `m`, it is not +addressable. + + + +Download the example and vary the inputs and see what the program prints. + + + +Here's another example, adapted from the `govet` static checking tool. +It checks for accidental uses of a method value `x.f` when a +call `x.f()` was intended; +comparing a method `x.f` against nil is a common mistake. + + +%include nilfunc/main.go + + +Given this input, + + +%include nilfunc/main.go input - + + +the program reports these errors: + + +%include nilfunc/main.go output - + +# Selections + + +A _selection_ is an expression _`expr`_`.f` in which +`f` denotes either a struct field or a method. +A selection is resolved not by looking for a name in the lexical +environment, but by looking within a _type_. +The type checker ascertains the meaning of each selection in the +package---a surprisingly tricky business---and records it in the +`Selections` mapping of the `Info` struct, whose values are +of type `Selection`: + + + type Selection struct{ ... } + func (s *Selection) Kind() SelectionKind // = FieldVal | MethodVal | MethodExpr + func (s *Selection) Recv() Type + func (s *Selection) Obj() Object + func (s *Selection) Type() Type + func (s *Selection) Index() []int + func (s *Selection) Indirect() bool + + +The `Kind` method discriminates between the three (legal) kinds +of selections, as indicated by the comments below. + + + type T struct{Field int} + func (T) Method() {} + var v T + + // Kind Type + var _ = v.Field // FieldVal int + var _ = v.Method // MethodVal func() + var _ = T.Method // MethodExpr func(T) + + +Because of embedding, a selection may denote more than one field or +method, in which case it is ambiguous, and no `Selection` is +recorded for it. + + + +The `Obj` method returns the `Object` for the selected field +(`*Var`) or method (`*Func`). +Due to embedding, the object may belong to a different type than that +of the receiver expression _`expr`_. +The `Type` method returns the type of the selection. For a field +selection, this is the type of the field, but for method selections, +the result is a function type that is not the same as the type of the +method. +For a `MethodVal`, the receiver parameter is dropped, and +for a `MethodExpr`, the receiver parameter becomes a regular +parameter, as shown in the example above. + + + +The `Index` and `Indirect` methods report information about +implicit operations occurring during the selection that a compiler +would need to know about. +Because of embedding, a selection _`expr`_`.f` may be +shorthand for a sequence containing several implicit field selections, +_`expr`_`.d.e.f`, and `Index` reports the complete +sequence. +And because of automatic pointer dereferencing during struct field +accesses and method calls, a selection may imply one or more indirect +loads from memory; `Indirect` reports whether this occurs. + + + +Clients of the type checker can call `LookupFieldOrMethod` to +look up a name within a type, as if by a selection. +This function has an intimidating signature, but conceptually it +accepts just a `Type` and a name, and returns a `Selection`: + + + func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) \ + (obj Object, index []int, indirect bool) + + +The result is not actually a `Selection`, but it contains the +three main components of one: `Obj`, `Index`, +and `Indirect`. + + + +The `addressable` flag should be set if the receiver is a +_variable_ of type `T`, since in a method selection on a +variable, an implicit address-of operation (`&`) may occur. +The flag indicates whether the methods of type `*T` should be +considered during the lookup. + + + +(You may wonder why this parameter is necessary. Couldn't clients +instead call `LookupFieldOrMethod` on the pointer type `*T` +if the receiver is a `T` variable? The answer is that if +`T` is an interface type, the type `*T` has no methods at +all.) + + + +The final two parameters of `LookupFieldOrMethod` are `(pkg +*Package, name string)`. +Together they specify the name of the field or method to look up. +This brings us to `Id`s. + + + +# Ids + + +`LookupFieldOrMethod`'s need for a `Package` parameter +is a subtle consequence of the +[_Uniqueness of identifiers_](https://golang.org/ref/spec#Uniqueness_of_identifiers) +section in the Go spec: "Two +identifiers are different if they are spelled differently, or if they +appear in different packages and are not exported." +In practical terms, this means that a type may have have two methods +(or two fields, or one of each) both named `f` so long as those +methods are defined in different packages, as in this example: + + + package a + type A int + func (A) f() + + package b + type B int + func (B) f() + + package c + import ( "a"; "b" ) + type C struct{a.A; b.B} // C has two methods called f + + +The type `c.C` has two methods named `f`, but there is +no ambiguity because the two `f`s are distinct +identifiers---think of them as `fᵃ` and `fᵇ`. +For an exported method, this situation _would_ be ambiguous +because there is no distinction between `Fᵃ` and `Fᵇ`; there +is only `F`. + + + +Despite having two methods called `f`, neither of them can be +called from within package `c` because `c` has no way to +identify them. +Within `c`, `f` is the identifier `fᶜ`, and +type `C` has no method of that name. +But if we pass an instance of `C` to code in package `a` +and call its `f` method via an interface, `fᵃ` is called. + + + +The practical consequence for tool builders is that any time you need +to look up a field or method by name, or construct a map of fields and/or +methods keyed by name, it is not sufficient to use the object's name +as a key. +Instead, you must call the `Object.Id` method, which returns +a string that incorporates the object name, and for unexported +objects, the package path too. +There is also a standalone function `Id` that combines a name and +the package path in the same way: + + + func Id(pkg *Package, name string) string + + +This distinction applies to selections _`expr`_`.f`, but not +to lexical references `x` because for unexported identifiers, +declarations and references always appear in the same package. + + + +Fun fact: the `reflect.StructField` type records both the +`Name` and the `PkgPath` strings for the same reason. +The `FieldByName` methods of `reflect.Value` and +`reflect.Type` match field names without regard to the package. +If there is more than one match, they return an invalid value. + + + + +# Method Sets + + +The _method set_ of a type is the set of methods that can be +called on any value of that type. +(A variable of type `T` has access to all the methods of type +`*T` as well, due to the implicit address-of operation during +method calls, but those extra methods are not part of the method set +of `T`.) + + + +Clients can request the method set of a type `T` by calling +`NewMethodSet(T)`: + + + type MethodSet struct{ ... } + func NewMethodSet(T Type) *MethodSet + func (s *MethodSet) Len() int + func (s *MethodSet) At(i int) *Selection + func (s *MethodSet) Lookup(pkg *Package, name string) *Selection + + +The `Len` and `At` methods access a a list of +`Selections`, all of kind `MethodVal`, ordered by `Id`. +The `Lookup` function allows lookup of a single method by +name (and package path, as explained in the previous section). + + + +`NewMethodSet` can be expensive, so for applications that compute +method sets repeatedly, `golang.org/x/tools/go/types/typeutil` +provides a `MethodSetCache` type that records previous results. +If you only need a single method, don't construct the +`MethodSet` at all; it's cheaper to use +`LookupFieldOrMethod`. + + + +The next program generates a boilerplate +declaration of a new concrete type that satisifies an existing +interface. +Here's an example: + + +%include skeleton/main.go output1 - + + +The three arguments are the package and the name of the existing +interface type, and the name of the new concrete type. +The `main` function (not shown) loads the specified package and +calls `PrintSkeleton` with the remaining two arguments: + + +%include skeleton/main.go + + +First, `PrintSkeleton` locates the package-level named interface +type, handling various error cases. +Then it chooses the name for the receiver of the new methods: the +first letter of the concrete type. +Finally, it iterates over the method set of the interface, printing +the corresponding concrete method declarations. + + + +There's a subtlety in the declaration of `sig`, which is the +string form of the method signature. +We could have obtained this string from `meth.Type().String()`, +but this would cause any named types within it to be formatted with +the complete package path, for instance +`net/http.ResponseWriter`, which is informative in diagnostics +but not legal Go syntax. +The `TypeString` function (explained in [Formatting Values](#formatting-values)) allows the +caller to control how packages are printed. +Passing `(*types.Package).Name` causes only the package name +`http` to be printed, not the complete path. +Here's another example that illustrates it: + + +%include skeleton/main.go output2 - + + +The following program inspects all pairs of package-level named types +in `pkg`, and reports the types that satisfy each interface type. + + +%include implements/main.go implements + + +Given this input, + + +%include implements/main.go input + + +the program prints: + + +%include implements/main.go output - + + +Notice that the method set of `B` does not include `g`, but +the method set of `*B` does. +That's why we needed the second assignability check, using the pointer +type `types.NewPointer(T)`. + + + +# Constants + + +A constant expression is one whose value is guaranteed to be computed at +compile time. +Constant expressions may appear in types, specifically as the length +of an array type such as `[16]byte`, so one of the jobs of the +type checker is to compute the value of each constant expression. + + + +As we saw in the `typeandvalue` example, the type checker records +the value of each constant expression like `"Hello, " + "world"`, +storing it in the `Value` field of the `TypeAndValue` struct. +Constants are represented using the `Value` interface from the +`go/constant` package. + + + package constant // go/constant + + type Value interface { + Kind() Kind + } + + type Kind int // one of Unknown, Bool, String, Int, Float, Complex + + +The interface has only one method, for discriminating the various +kinds of constants, but the package provides many functions for +inspecting a value of a known kind, + + + // Accessors + func BoolVal(x Value) bool + func Float32Val(x Value) (float32, bool) + func Float64Val(x Value) (float64, bool) + func Int64Val(x Value) (int64, bool) + func StringVal(x Value) string + func Uint64Val(x Value) (uint64, bool) + func Bytes(x Value) []byte + func BitLen(x Value) int + func Sign(x Value) int + + +for performing arithmetic on values, + + + // Operations + func Compare(x Value, op token.Token, y Value) bool + func UnaryOp(op token.Token, y Value, prec uint) Value + func BinaryOp(x Value, op token.Token, y Value) Value + func Shift(x Value, op token.Token, s uint) Value + func Denom(x Value) Value + func Num(x Value) Value + func Real(x Value) Value + func Imag(x Value) Value + + +and for constructing new values: + + + // Constructors + func MakeBool(b bool) Value + func MakeFloat64(x float64) Value + func MakeFromBytes(bytes []byte) Value + func MakeFromLiteral(lit string, tok token.Token, prec uint) Value + func MakeImag(x Value) Value + func MakeInt64(x int64) Value + func MakeString(s string) Value + func MakeUint64(x uint64) Value + func MakeUnknown() Value + + +All numeric `Value`s, whether integer or floating-point, signed or +unsigned, or real or complex, are represented more precisely than the +ordinary Go types like `int64` and `float64`. +Internally, the `go/constant` package uses multi-precision data types +like `Int`, `Rat`, and `Float` from the `math/big` package so that +`Values` and their arithmetic operations are accurate to at least 256 +bits, as required by the Go specification. + + +<!-- TODO example --> + + +# Size and Alignment + + +Because the calls `unsafe.Sizeof(v)`, `unsafe.Alignof(v)`, +and `unsafe.Offsetof(v.f)` are all constant expressions, the type +checker must be able to compute the memory layout of any value +`v`. + + + +By default, the type checker uses the same layout algorithm as the Go +1.5 `gc` compiler targeting `amd64`. +Clients can configure the type checker to use a different algorithm by +providing an instance of the `types.Sizes` interface in the +`types.Config` struct: + + + package types + + type Sizes interface { + Alignof(T Type) int64 + Offsetsof(fields []*Var) []int64 + Sizeof(T Type) int64 + } + + + +For common changes, like reducing the word size to 32 bits, clients +can use an instance of `StdSizes`: + + + type StdSizes struct { + WordSize int64 + MaxAlign int64 + } + + +This type has two basic size and alignment parameters from which it +derives all the other values using common assumptions. +For example, pointers, functions, maps, and channels fit in one word, +strings and interfaces require two words, and slices need three. +The default behaviour is equivalent to `StdSizes{8, 8}`. +For more esoteric layout changes, you'll need to write a new +implementation of the `Sizes` interface. + + + +The `hugeparam` program below prints all function parameters and +results whose size exceeds a threshold. +By default, the threshold is 48 bytes, but you can set it via the +`-bytes` command-line flag. +Such a tool could help identify inefficient parameter passing in your +programs. + + +%include hugeparam/main.go + + +As before, `Inspect` applies a function to every node in the AST. +The function cares about two kinds of nodes: declarations of named +functions and methods (`*ast.FuncDecl`) and function literals +(`*ast.FuncLit`). +Observe the two cases' different logic to obtain the type of each +function. + + + +Here's a typical invocation on the standard `encoding/xml` package. +It reports a number of places where the 7-word +[`StartElement` type](https://godoc.org/encoding/xml#StartElement) +is copied. + + +%include hugeparam/main.go output - + +# Imports + + +The type checker's `Check` function processes a slice of parsed +files (`[]*ast.File`) that make up one package. +When the type checker encounters an import declaration, it needs the +type information for the objects in the imported package. +It gets it by calling the `Import` method of the `Importer` +interface shown below, an instance of which must be provided by the +`Config`. +This separation of concerns relieves the type checker from having to +know any of the details of Go workspace organization, `GOPATH`, +compiler file formats, and so on. + + + type Importer interface { + Import(path string) (*Package, error) + } + + +Most of our examples used the simplest `Importer` implementation, +`importer.Default()`, provided by the `go/importer` package. +This importer looks in `$GOROOT` and `$GOPATH` for `.a` +files written by the compiler (`gc` or `gccgo`) +that was used to build the program. +In addition to object code, these files contain _export data_, +that is, a description of all the objects declared by the package, and +also of any objects from other packages that were referred to indirectly. +Because export data includes information about dependencies, the type +checker need load at most one file per import, instead of one per +transitive dependency. + + + +Compiler export data is compact and efficient to locate, load, and +parse, but it has several shortcomings. +First, it does not contain position information for imported +objects, reducing the quality of certain diagnostic messages. +Second, it does not contain complete syntax trees nor semantic information +about the contents of function bodies, so it is not suitable for +interprocedural analyses. +Third, compiler object data may be stale. Nothing detects or ensures +that the object files are more recent than the source files from which +they were derived. +Generally, object data for standard packages is likely to be +up-to-date, but for user packages, it depends on how recently the user +ran a `go install` or `go build -i` command. + + + +The [`golang.org/tools/x/go/loader` package](https://godoc.org/golang.org/x/tools/go/loader) +provides an alternative `Importer` that addresses +some of these problems. +It loads a complete program from source, performing +[`cgo`](https://golang.org/cmd/cgo/cgo) preprocessing if +necessary, followed by parsing and type-checking. +It loads independent packages in parallel to hide I/O latency, and +detects and reports import cycles. +For each package, it provides the `types.Package` containing the +package's lexical environment, the list of `ast.File` syntax +trees for each file in the package, the `types.Info` containing +type information for each syntax node, and a list of type errors +associated with that package. +(Please be aware that the `go/loader` package's API is likely to +change before it finally stabilizes.) + + + +The `doc` program below demonstrates a simple use of the loader. +It is a rudimentary implementation of `go doc` that prints the type, +methods, and documentation of the package-level object specified on +the command line. +Here's an example: + + +%include doc/main.go output - + + +Observe that it prints the correct location of each method +declaration, even though, due to embedding, some of +`http.File`'s methods were declared in another package. +Here's the first part of the program, showing how to load an entire +program starting from the single package, `pkgpath`: + + +%include doc/main.go part1 + + +Notice that we instructed the parser to retain comments during parsing. +The rest of the program prints the output: + + +%include doc/main.go part2 + + +We used `IntuitiveMethodSet` to compute the method set, instead +of `NewMethodSet`. +The result of this convenience function, which is intended for use in +user interfaces, includes methods of `*T` as well as those of +`T`, since that matches most users' intuition about the method +set of a type. +(Our example, `http.File`, didn't illustrate the difference, but try +running it on a type with both value and pointer methods.) + + + +Also notice `PathEnclosingInterval`, which finds the set of AST +nodes that enclose a particular point, in this case, the object's +declaring identifier. +By walking up with path, we find the enclosing declaration, to which +the documentation is attached. + + + +# Formatting support + + +All types that satisfy `Type` or `Object` define a +`String` method that formats the type or object in a readable +notation. `Selection` also provides a `String` method. +All package-level objects within these data structures are +printed with the complete package path, as in these examples: + + + []encoding/json.Marshaler // a *Slice type + encoding/json.Marshal // a *Func object + (*encoding/json.Encoder).Encode // a *Func object (method) + func (enc *encoding/json.Encoder) Encode(v interface{}) error // a method *Signature + func NewEncoder(w io.Writer) *encoding/json.Encoder // a function *Signature + + +This notation is unambiguous, but it is not legal Go syntax. +Also, package paths may be long, and the same package path may appear +many times in a single string, for instance, when formatting a +function of several parameters. +Because these strings often form part of a tool's user interface---as +with the diagnostic messages of `hugeparam` or the code generated +by `skeleton`---many clients want more control over the +formatting of package names. + + + +The `go/types` package provides these alternatives to the +`String` methods: + + + func ObjectString(obj Object, qf Qualifier) string + func TypeString(typ Type, qf Qualifier) string + func SelectionString(s *Selection, qf Qualifier) string + + type Qualifier func(*Package) string + + +The `TypeString`, `ObjectString`, and `SelectionString` +functions are like the `String` methods of the respective types, +but they accept an additional argument, a `Qualifier`. + + + +A `Qualifier` is a client-provided function that determines how a +package name is rendered as a string. +If it is nil, the default behavior is to print the package's +path, just like the `String` methods do. +If a caller passes `(*Package).Name` as the qualifier, that is, a +function that accepts a package and returns its `Name`, then +objects are qualified only by the package name. +The above examples would look like this: + + + []json.Marshaler + json.Marshal + (*json.Encoder).Encode + func (enc *json.Encoder) Encode(v interface{}) error + func NewEncoder(w io.Writer) *json.Encoder + + +Often when a tool prints some output, it is implicitly in the +context of a particular package, perhaps one specified by the +command line or HTTP request. +In that case, it is more natural to omit the package qualification +altogether for objects belonging to that package, but to qualify all +other objects by their package's path. +That's what the `RelativeTo(pkg)` qualifier does: + + + func RelativeTo(pkg *Package) Qualifier + + +The examples below show how `json.NewEncoder` would be printed +using three qualifiers, each relative to a different package: + + + // RelativeTo "encoding/json": + func NewEncoder(w io.Writer) *Encoder + + // RelativeTo "io": + func NewEncoder(w Writer) *encoding/json.Encoder + + // RelativeTo any other package: + func NewEncoder(w io.Writer) *encoding/json.Encoder + + +Another qualifier that may be relevant to refactoring tools (but is +not currently provided by the type checker) is one that renders each +package name using the locally appropriate name within a given source +file. +Its behavior would depend on the set of import declarations, including +renaming imports, within that source file. + + + +# Getting from A to B + + +The type checker and its related packages represent many aspects of a +Go program in many different ways, and analysis tools must often map +between them. +For instance, a named entity may be identified by its `Object`; +by its declaring identifier (`ast.Ident`) or by any referring +identifier; by its declaring `ast.Node`; by the position +(`token.Pos`) of any those nodes; or by the filename and +line/column number (or byte offset) of those `token.Pos` values. + + + +In this section, we'll list solutions to a number of common problems +of the form "I have an A; I need the corresponding B". + + + +To map **from a `token.Pos` to an `ast.Node`**, call the +helper function +[`astutil.PathEnclosingInterval`](https://godoc.org/golang.org/x/tools/go/ast/astutil#PathEnclosingInterval). +It returns the enclosing `ast.Node`, and all its ancestors up to +the root of the file. +You must know which file `*ast.File` the `token.Pos` belongs to. +Alternatively, you can search an entire program loaded by the +`loader` package, using +[`(*loader.Program).PathEnclosingInterval`](https://godoc.org/golang.org/x/tools/go/loader#Program.PathEnclosingInterval). + + + +To map **from an `Object` to its declaring syntax**, call +`Pos` to get its position, then use `PathEnclosingInterval` as before. +This approach is suitable for a one-off query. For repeated use, it +may be more efficient to visit the syntax tree and construct the +mapping between declarations and objects. + + + +To map **from an `ast.Ident` to the `Object`** it refers to (or +declares), consult the `Uses` or `Defs` map for the +package, as shown in [Identifier Resolution](#identifier_resolution). + + + +To map **from an `Object` to its documentation**, find the +object's declaration, and look at the attached `Doc` field. +You must have set the parser's `ParseComments` flag. +See the `doc` example in [Imports](#imports).
diff --git a/gotypes/hello/hello.go b/gotypes/hello/hello.go new file mode 100644 index 0000000..01a2862 --- /dev/null +++ b/gotypes/hello/hello.go
@@ -0,0 +1,10 @@ +//!+ +package main + +import "fmt" + +func main() { + fmt.Println("Hello, 世界") +} + +//!-
diff --git a/gotypes/hugeparam/main.go b/gotypes/hugeparam/main.go new file mode 100644 index 0000000..ba62aaa --- /dev/null +++ b/gotypes/hugeparam/main.go
@@ -0,0 +1,81 @@ +// The hugeparam command identifies by-value parameters that are larger than n bytes. +// +// Example: +// $ ./hugeparams encoding/xml +package main + +import ( + "flag" + "fmt" + "go/ast" + "go/token" + "log" + + "golang.org/x/tools/go/loader" + "golang.org/x/tools/go/types" // TODO: will use std go/types after Mar 2016 +) + +//!+ +var bytesFlag = flag.Int("bytes", 48, "maximum parameter size in bytes") + +var sizeof = (&types.StdSizes{8, 8}).Sizeof // the sizeof function + +func PrintHugeParams(fset *token.FileSet, info *types.Info, files []*ast.File) { + checkTuple := func(descr string, tuple *types.Tuple) { + for i := 0; i < tuple.Len(); i++ { + v := tuple.At(i) + if sz := sizeof(v.Type()); sz > int64(*bytesFlag) { + fmt.Printf("%s: %q %s: %s = %d bytes\n", + fset.Position(v.Pos()), + v.Name(), descr, v.Type(), sz) + } + } + } + checkSig := func(sig *types.Signature) { + checkTuple("parameter", sig.Params()) + checkTuple("result", sig.Results()) + } + for _, file := range files { + ast.Inspect(file, func(n ast.Node) bool { + switch n := n.(type) { + case *ast.FuncDecl: + checkSig(info.Defs[n.Name].Type().(*types.Signature)) + case *ast.FuncLit: + checkSig(info.Types[n.Type].Type.(*types.Signature)) + } + return true + }) + } +} + +//!- + +func main() { + flag.Parse() + + // The loader loads a complete Go program from source code. + var conf loader.Config + _, err := conf.FromArgs(flag.Args(), false) + if err != nil { + log.Fatal(err) // command syntax error + } + lprog, err := conf.Load() + if err != nil { + log.Fatal(err) // load error + } + + for _, info := range lprog.InitialPackages() { + PrintHugeParams(lprog.Fset, &info.Info, info.Files) + } +} + +/* +//!+output +% ./hugeparam encoding/xml +/go/src/encoding/xml/marshal.go:167:50: "start" parameter: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/marshal.go:734:97: "" result: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/marshal.go:761:51: "start" parameter: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/marshal.go:781:68: "start" parameter: encoding/xml.StartElement = 56 bytes +/go/src/encoding/xml/xml.go:72:30: "" result: encoding/xml.StartElement = 56 bytes +//!-output +*/
diff --git a/gotypes/implements/main.go b/gotypes/implements/main.go new file mode 100644 index 0000000..d7e5701 --- /dev/null +++ b/gotypes/implements/main.go
@@ -0,0 +1,77 @@ +package main + +import ( + "fmt" + "go/ast" + "go/importer" + "go/parser" + "go/token" + "go/types" + "log" +) + +//!+input +const input = `package main + +type A struct{} +func (*A) f() + +type B int +func (B) f() +func (*B) g() + +type I interface { f() } +type J interface { g() } +` + +//!-input + +func main() { + // Parse one file. + fset := token.NewFileSet() + f, err := parser.ParseFile(fset, "input.go", input, 0) + if err != nil { + log.Fatal(err) // parse error + } + conf := types.Config{Importer: importer.Default()} + pkg, err := conf.Check("hello", fset, []*ast.File{f}, nil) + if err != nil { + log.Fatal(err) // type error + } + + //!+implements + // Find all named types at package level. + var allNamed []*types.Named + for _, name := range pkg.Scope().Names() { + if obj, ok := pkg.Scope().Lookup(name).(*types.TypeName); ok { + allNamed = append(allNamed, obj.Type().(*types.Named)) + } + } + + // Test assignability of all distinct pairs of + // named types (T, U) where U is an interface. + for _, T := range allNamed { + for _, U := range allNamed { + if T == U || !types.IsInterface(U) { + continue + } + if types.AssignableTo(T, U) { + fmt.Printf("%s satisfies %s\n", T, U) + } else if !types.IsInterface(T) && + types.AssignableTo(types.NewPointer(T), U) { + fmt.Printf("%s satisfies %s\n", types.NewPointer(T), U) + } + } + } + //!-implements +} + +/* +//!+output +$ go build github.com/golang/example/gotypes/implements +$ ./implements +*hello.A satisfies hello.I +hello.B satisfies hello.I +*hello.B satisfies hello.J +//!-output +*/
diff --git a/gotypes/lookup/lookup.go b/gotypes/lookup/lookup.go new file mode 100644 index 0000000..9bdc97d --- /dev/null +++ b/gotypes/lookup/lookup.go
@@ -0,0 +1,77 @@ +package main + +import ( + "fmt" + "go/ast" + "go/importer" + "go/parser" + "go/token" + "go/types" + "log" + "strings" +) + +//!+input +const hello = ` +package main + +import "fmt" + +// append +func main() { + // fmt + fmt.Println("Hello, world") + // main + main, x := 1, 2 + // main + print(main, x) + // x +} +// x +` + +//!-input + +//!+main +func main() { + fset := token.NewFileSet() + f, err := parser.ParseFile(fset, "hello.go", hello, parser.ParseComments) + if err != nil { + log.Fatal(err) // parse error + } + + conf := types.Config{Importer: importer.Default()} + pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, nil) + if err != nil { + log.Fatal(err) // type error + } + + // Each comment contains a name. + // Look up that name in the innermost scope enclosing the comment. + for _, comment := range f.Comments { + pos := comment.Pos() + name := strings.TrimSpace(comment.Text()) + fmt.Printf("At %s,\t%q = ", fset.Position(pos), name) + inner := pkg.Scope().Innermost(pos) + if _, obj := inner.LookupParent(name, pos); obj != nil { + fmt.Println(obj) + } else { + fmt.Println("not found") + } + } +} + +//!-main + +/* +//!+output +$ go build github.com/golang/example/gotypes/lookup +$ ./lookup +At hello.go:6:1, "append" = builtin append +At hello.go:8:9, "fmt" = package fmt +At hello.go:10:9, "main" = func cmd/hello.main() +At hello.go:12:9, "main" = var main int +At hello.go:14:9, "x" = var x int +At hello.go:16:1, "x" = not found +//!-output +*/
diff --git a/gotypes/nilfunc/main.go b/gotypes/nilfunc/main.go new file mode 100644 index 0000000..da4b79b --- /dev/null +++ b/gotypes/nilfunc/main.go
@@ -0,0 +1,104 @@ +package main + +import ( + "fmt" + "go/ast" + "go/importer" + "go/parser" + "go/token" + "go/types" + "log" +) + +//!+input +const input = `package main + +import "bytes" + +func main() { + var buf bytes.Buffer + if buf.Bytes == nil && bytes.Repeat != nil && main == nil { + // ... + } +} +` + +//!-input + +var fset = token.NewFileSet() + +func main() { + f, err := parser.ParseFile(fset, "input.go", input, 0) + if err != nil { + log.Fatal(err) // parse error + } + conf := types.Config{Importer: importer.Default()} + info := &types.Info{ + Defs: make(map[*ast.Ident]types.Object), + Uses: make(map[*ast.Ident]types.Object), + Types: make(map[ast.Expr]types.TypeAndValue), + } + if _, err = conf.Check("cmd/hello", fset, []*ast.File{f}, info); err != nil { + log.Fatal(err) // type error + } + + ast.Inspect(f, func(n ast.Node) bool { + if n != nil { + CheckNilFuncComparison(info, n) + } + return true + }) +} + +//!+ +// CheckNilFuncComparison reports unintended comparisons +// of functions against nil, e.g., "if x.Method == nil {". +func CheckNilFuncComparison(info *types.Info, n ast.Node) { + e, ok := n.(*ast.BinaryExpr) + if !ok { + return // not a binary operation + } + if e.Op != token.EQL && e.Op != token.NEQ { + return // not a comparison + } + + // If this is a comparison against nil, find the other operand. + var other ast.Expr + if info.Types[e.X].IsNil() { + other = e.Y + } else if info.Types[e.Y].IsNil() { + other = e.X + } else { + return // not a comparison against nil + } + + // Find the object. + var obj types.Object + switch v := other.(type) { + case *ast.Ident: + obj = info.Uses[v] + case *ast.SelectorExpr: + obj = info.Uses[v.Sel] + default: + return // not an identifier or selection + } + + if _, ok := obj.(*types.Func); !ok { + return // not a function or method + } + + fmt.Printf("%s: comparison of function %v %v nil is always %v\n", + fset.Position(e.Pos()), obj.Name(), e.Op, e.Op == token.NEQ) +} + +//!- + +/* +//!+output +$ go build github.com/golang/example/gotypes/nilfunc +$ ./nilfunc +input.go:7:5: comparison of function Bytes == nil is always false +input.go:7:25: comparison of function Repeat != nil is always true +input.go:7:48: comparison of function main == nil is always false +//!-output +*/
diff --git a/gotypes/pkginfo/main.go b/gotypes/pkginfo/main.go new file mode 100644 index 0000000..3050f80 --- /dev/null +++ b/gotypes/pkginfo/main.go
@@ -0,0 +1,64 @@ +//!+ +package main + +import ( + "fmt" + "go/ast" + "go/importer" + "go/parser" + "go/token" + "go/types" + "log" +) + +const hello = `package main + +import "fmt" + +func main() { + fmt.Println("Hello, world") +}` + +func main() { + fset := token.NewFileSet() + + // Parse the input string, []byte, or io.Reader, + // recording position information in fset. + // ParseFile returns an *ast.File, a syntax tree. + f, err := parser.ParseFile(fset, "hello.go", hello, 0) + if err != nil { + log.Fatal(err) // parse error + } + + // A Config controls various options of the type checker. + // The defaults work fine except for one setting: + // we must specify how to deal with imports. + conf := types.Config{Importer: importer.Default()} + + // Type-check the package containing only file f. + // Check returns a *types.Package. + pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, nil) + if err != nil { + log.Fatal(err) // type error + } + + fmt.Printf("Package %q\n", pkg.Path()) + fmt.Printf("Name: %s\n", pkg.Name()) + fmt.Printf("Imports: %s\n", pkg.Imports()) + fmt.Printf("Scope: %s\n", pkg.Scope()) +} + +//!- + +/* +//!+output +$ go build github.com/golang/example/gotypes/pkginfo +$ ./pkginfo +Package "cmd/hello" +Name: main +Imports: [package fmt ("fmt")] +Scope: package "cmd/hello" scope 0x820533590 { +. func cmd/hello.main() +} +//!-output +*/
diff --git a/gotypes/skeleton/main.go b/gotypes/skeleton/main.go new file mode 100644 index 0000000..1d8ed14 --- /dev/null +++ b/gotypes/skeleton/main.go
@@ -0,0 +1,115 @@ +// The skeleton command prints the boilerplate for a concrete type +// that implements the specified interface type. +// +// Example: +// $ ./skeleton io ReadWriteCloser buffer +// // *buffer implements io.ReadWriteCloser. +// type buffer struct{ /* ... */ } +// func (b *buffer) Close() error { panic("unimplemented") } +// func (b *buffer) Read(p []byte) (n int, err error) { panic("unimplemented") } +// func (b *buffer) Write(p []byte) (n int, err error) { panic("unimplemented") } +package main + +import ( + "fmt" + "log" + "os" + "strings" + "unicode" + "unicode/utf8" + + "golang.org/x/tools/go/loader" + "golang.org/x/tools/go/types" // TODO: will use std go/types after Feb 2016 +) + +const usage = "Usage: skeleton <package> <interface> <concrete>" + +//!+ +func PrintSkeleton(pkg *types.Package, ifacename, concname string) error { + obj := pkg.Scope().Lookup(ifacename) + if obj == nil { + return fmt.Errorf("%s.%s not found", pkg.Path(), ifacename) + } + if _, ok := obj.(*types.TypeName); !ok { + return fmt.Errorf("%v is not a named type", obj) + } + iface, ok := obj.Type().Underlying().(*types.Interface) + if !ok { + return fmt.Errorf("type %v is a %T, not an interface", + obj, obj.Type().Underlying()) + } + // Use first letter of type name as receiver parameter. + if !isValidIdentifier(concname) { + return fmt.Errorf("invalid concrete type name: %q", concname) + } + r, _ := utf8.DecodeRuneInString(concname) + + fmt.Printf("// *%s implements %s.%s.\n", concname, pkg.Path(), ifacename) + fmt.Printf("type %s struct{}\n", concname) + mset := types.NewMethodSet(iface) + for i := 0; i < mset.Len(); i++ { + meth := mset.At(i).Obj() + sig := types.TypeString(meth.Type(), (*types.Package).Name) + fmt.Printf("func (%c *%s) %s%s {\n\tpanic(\"unimplemented\")\n}\n", + r, concname, meth.Name(), + strings.TrimPrefix(sig, "func")) + } + return nil +} + +//!- + +func isValidIdentifier(id string) bool { + for i, r := range id { + if !unicode.IsLetter(r) && + !(i > 0 && unicode.IsDigit(r)) { + return false + } + } + return id != "" +} + +func main() { + if len(os.Args) != 4 { + log.Fatal(usage) + } + pkgpath, ifacename, concname := os.Args[1], os.Args[2], os.Args[3] + + // The loader loads a complete Go program from source code. + var conf loader.Config + conf.Import(pkgpath) + lprog, err := conf.Load() + if err != nil { + log.Fatal(err) // load error + } + pkg := lprog.Package(pkgpath).Pkg + if err := PrintSkeleton(pkg, ifacename, concname); err != nil { + log.Fatal(err) + } +} + +/* +//!+output1 +$ ./skeleton io ReadWriteCloser buffer +// *buffer implements io.ReadWriteCloser. +type buffer struct{} +func (b *buffer) Close() error { + panic("unimplemented") +} +func (b *buffer) Read(p []byte) (n int, err error) { + panic("unimplemented") +} +func (b *buffer) Write(p []byte) (n int, err error) { + panic("unimplemented") +} +//!-output1 + +//!+output2 +$ ./skeleton net/http Handler myHandler +// *myHandler implements net/http.Handler. +type myHandler struct{} +func (m *myHandler) ServeHTTP(http.ResponseWriter, *http.Request) { + panic("unimplemented") +} +//!-output2 +*/
diff --git a/gotypes/typeandvalue/main.go b/gotypes/typeandvalue/main.go new file mode 100644 index 0000000..96b7bf0 --- /dev/null +++ b/gotypes/typeandvalue/main.go
@@ -0,0 +1,130 @@ +package main + +import ( + "bytes" + "fmt" + "go/ast" + "go/format" + "go/importer" + "go/parser" + "go/token" + "go/types" + "log" +) + +//!+input +const input = ` +package main + +var m = make(map[string]int) + +func main() { + v, ok := m["hello, " + "world"] + print(rune(v), ok) +} +` + +//!-input + +var fset = token.NewFileSet() + +func main() { + f, err := parser.ParseFile(fset, "hello.go", input, 0) + if err != nil { + log.Fatal(err) // parse error + } + + conf := types.Config{Importer: importer.Default()} + info := &types.Info{Types: make(map[ast.Expr]types.TypeAndValue)} + if _, err := conf.Check("cmd/hello", fset, []*ast.File{f}, info); err != nil { + log.Fatal(err) // type error + } + + //!+inspect + // f is a parsed, type-checked *ast.File. + ast.Inspect(f, func(n ast.Node) bool { + if expr, ok := n.(ast.Expr); ok { + if tv, ok := info.Types[expr]; ok { + fmt.Printf("%-24s\tmode: %s\n", nodeString(expr), mode(tv)) + fmt.Printf("\t\t\t\ttype: %v\n", tv.Type) + if tv.Value != nil { + fmt.Printf("\t\t\t\tvalue: %v\n", tv.Value) + } + } + } + return true + }) + //!-inspect +} + +// nodeString formats a syntax tree in the style of gofmt. +func nodeString(n ast.Node) string { + var buf bytes.Buffer + format.Node(&buf, fset, n) + return buf.String() +} + +// mode returns a string describing the mode of an expression. +func mode(tv types.TypeAndValue) string { + s := "" + if tv.IsVoid() { + s += ",void" + } + if tv.IsType() { + s += ",type" + } + if tv.IsBuiltin() { + s += ",builtin" + } + if tv.IsValue() { + s += ",value" + } + if tv.IsNil() { + s += ",nil" + } + if tv.Addressable() { + s += ",addressable" + } + if tv.Assignable() { + s += ",assignable" + } + if tv.HasOk() { + s += ",ok" + } + return s[1:] +} + +/* +//!+output +$ go build github.com/golang/example/gotypes/typeandvalue +$ ./typeandvalue +make(map[string]int) mode: value + type: map[string]int +make mode: builtin + type: func(map[string]int) map[string]int +map[string]int mode: type + type: map[string]int +m["hello"] mode: value,assignable,ok + type: (int, bool) +m mode: value,addressable,assignable + type: map[string]int +"hello, " + "world" mode: value + type: string + value: "hello, world" +"hello, " mode: value + type: untyped string + value: "hello, " +"world" mode: value + type: untyped string + value: "world" +print(rune(v), ok) mode: void + type: () +print mode: builtin + type: func(rune, bool) +rune(v) mode: value + type: rune +rune mode: type + type: rune +...more not shown... +//!-output +*/
diff --git a/gotypes/weave.go b/gotypes/weave.go new file mode 100644 index 0000000..770bda2 --- /dev/null +++ b/gotypes/weave.go
@@ -0,0 +1,191 @@ +// The weave command is a simple preprocessor for markdown files. +// It builds a table of contents and processes %include directives. +// +// Example usage: +// $ go run weave.go go-types.md > README.md +package main + +import ( + "bufio" + "bytes" + "fmt" + "log" + "os" + "path/filepath" + "regexp" + "strings" +) + +func main() { + log.SetFlags(0) + log.SetPrefix("weave: ") + if len(os.Args) != 2 { + log.Fatal("usage: weave input.md\n") + } + + f, err := os.Open(os.Args[1]) + if err != nil { + log.Fatal(err) + } + defer f.Close() + + fmt.Println("<!-- Autogenerated by weave; DO NOT EDIT -->") + + // Pass 1. + var toc []string + in := bufio.NewScanner(f) + for in.Scan() { + line := in.Text() + if line == "" || (line[0] != '#' && line[0] != '%') { + continue + } + line = strings.TrimSpace(line) + if line == "%toc" { + toc = nil + } else if strings.HasPrefix(line, "# ") || strings.HasPrefix(line, "## ") { + words := strings.Fields(line) + depth := len(words[0]) + words = words[1:] + text := strings.Join(words, " ") + for i := range words { + words[i] = strings.ToLower(words[i]) + } + line = fmt.Sprintf("%s1. [%s](#%s)", + strings.Repeat("\t", depth-1), text, strings.Join(words, "-")) + toc = append(toc, line) + } + } + + // Pass 2. + if _, err := f.Seek(0, os.SEEK_SET); err != nil { + log.Fatalf("can't rewind input: %v", err) + } + in = bufio.NewScanner(f) + for in.Scan() { + line := in.Text() + switch { + case strings.HasPrefix(line, "%toc"): // ToC + for _, h := range toc { + fmt.Println(h) + } + case strings.HasPrefix(line, "%include"): + words := strings.Fields(line) + if len(words) < 2 { + log.Fatal(line) + } + filename := words[1] + + // Show caption unless '-' follows. + if len(words) < 4 || words[3] != "-" { + fmt.Printf(" // go get github.com/golang/example/gotypes/%s\n\n", + filepath.Dir(filename)) + } + + section := "" + if len(words) > 2 { + section = words[2] + } + s, err := include(filename, section) + if err != nil { + log.Fatal(err) + } + fmt.Println("```") + fmt.Println(cleanListing(s)) // TODO(adonovan): escape /^```/ in s + fmt.Println("```") + default: + fmt.Println(line) + } + + } +} + +// include processes an included file, and returns the included text. +// Only lines between those matching !+tag and !-tag will be returned. +// This is true even if tag=="". +func include(file, tag string) (string, error) { + f, err := os.Open(file) + if err != nil { + return "", err + } + defer f.Close() + + startre, err := regexp.Compile("!\\+" + tag + "$") + if err != nil { + return "", err + } + endre, err := regexp.Compile("!\\-" + tag + "$") + if err != nil { + return "", err + } + + var text bytes.Buffer + in := bufio.NewScanner(f) + var on bool + for in.Scan() { + line := in.Text() + switch { + case startre.MatchString(line): + on = true + case endre.MatchString(line): + on = false + case on: + text.WriteByte('\t') + text.WriteString(line) + text.WriteByte('\n') + } + } + if text.Len() == 0 { + return "", fmt.Errorf("no lines of %s matched tag %q", file, tag) + } + return text.String(), nil +} + +func isBlank(line string) bool { return strings.TrimSpace(line) == "" } + +func indented(line string) bool { + return strings.HasPrefix(line, " ") || strings.HasPrefix(line, "\t") +} + +// cleanListing removes entirely blank leading and trailing lines from +// text, and removes n leading tabs. +func cleanListing(text string) string { + lines := strings.Split(text, "\n") + + // remove minimum number of leading tabs from all non-blank lines + tabs := 999 + for i, line := range lines { + if strings.TrimSpace(line) == "" { + lines[i] = "" + } else { + if n := leadingTabs(line); n < tabs { + tabs = n + } + } + } + for i, line := range lines { + if line != "" { + line := line[tabs:] + lines[i] = line // remove leading tabs + } + } + + // remove leading blank lines + for len(lines) > 0 && lines[0] == "" { + lines = lines[1:] + } + // remove trailing blank lines + for len(lines) > 0 && lines[len(lines)-1] == "" { + lines = lines[:len(lines)-1] + } + return strings.Join(lines, "\n") +} + +func leadingTabs(s string) int { + var i int + for i = 0; i < len(s); i++ { + if s[i] != '\t' { + break + } + } + return i +}