cmd/bpa-operator/vendor/k8s.io/gengo/parser/parse.go

   1 /*
   2 Copyright 2015 The Kubernetes Authors.
   3
   4 Licensed under the Apache License, Version 2.0 (the "License");
   5 you may not use this file except in compliance with the License.
   6 You may obtain a copy of the License at
   7
   8     http://www.apache.org/licenses/LICENSE-2.0
   9
  10 Unless required by applicable law or agreed to in writing, software
  11 distributed under the License is distributed on an "AS IS" BASIS,
  12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 See the License for the specific language governing permissions and
  14 limitations under the License.
  15 */
  16
  17 package parser
  18
  19 import (
  20         "fmt"
  21         "go/ast"
  22         "go/build"
  23         "go/parser"
  24         "go/token"
  25         tc "go/types"
  26         "io/ioutil"
  27         "os"
  28         "os/exec"
  29         "path"
  30         "path/filepath"
  31         "sort"
  32         "strings"
  33
  34         "k8s.io/gengo/types"
  35         "k8s.io/klog"
  36 )
  37
  38 // This clarifies when a pkg path has been canonicalized.
  39 type importPathString string
  40
  41 // Builder lets you add all the go files in all the packages that you care
  42 // about, then constructs the type source data.
  43 type Builder struct {
  44         context *build.Context
  45
  46         // Map of package names to more canonical information about the package.
  47         // This might hold the same value for multiple names, e.g. if someone
  48         // referenced ./pkg/name or in the case of vendoring, which canonicalizes
  49         // differently that what humans would type.
  50         buildPackages map[string]*build.Package
  51
  52         fset *token.FileSet
  53         // map of package path to list of parsed files
  54         parsed map[importPathString][]parsedFile
  55         // map of package path to absolute path (to prevent overlap)
  56         absPaths map[importPathString]string
  57
  58         // Set by typeCheckPackage(), used by importPackage() and friends.
  59         typeCheckedPackages map[importPathString]*tc.Package
  60
  61         // Map of package path to whether the user requested it or it was from
  62         // an import.
  63         userRequested map[importPathString]bool
  64
  65         // All comments from everywhere in every parsed file.
  66         endLineToCommentGroup map[fileLine]*ast.CommentGroup
  67
  68         // map of package to list of packages it imports.
  69         importGraph map[importPathString]map[string]struct{}
  70 }
  71
  72 // parsedFile is for tracking files with name
  73 type parsedFile struct {
  74         name string
  75         file *ast.File
  76 }
  77
  78 // key type for finding comments.
  79 type fileLine struct {
  80         file string
  81         line int
  82 }
  83
  84 // New constructs a new builder.
  85 func New() *Builder {
  86         c := build.Default
  87         if c.GOROOT == "" {
  88                 if p, err := exec.Command("which", "go").CombinedOutput(); err == nil {
  89                         // The returned string will have some/path/bin/go, so remove the last two elements.
  90                         c.GOROOT = filepath.Dir(filepath.Dir(strings.Trim(string(p), "\n")))
  91                 } else {
  92                         klog.Warningf("Warning: $GOROOT not set, and unable to run `which go` to find it: %v\n", err)
  93                 }
  94         }
  95         // Force this to off, since we don't properly parse CGo.  All symbols must
  96         // have non-CGo equivalents.
  97         c.CgoEnabled = false
  98         return &Builder{
  99                 context:               &c,
 100                 buildPackages:         map[string]*build.Package{},
 101                 typeCheckedPackages:   map[importPathString]*tc.Package{},
 102                 fset:                  token.NewFileSet(),
 103                 parsed:                map[importPathString][]parsedFile{},
 104                 absPaths:              map[importPathString]string{},
 105                 userRequested:         map[importPathString]bool{},
 106                 endLineToCommentGroup: map[fileLine]*ast.CommentGroup{},
 107                 importGraph:           map[importPathString]map[string]struct{}{},
 108         }
 109 }
 110
 111 // AddBuildTags adds the specified build tags to the parse context.
 112 func (b *Builder) AddBuildTags(tags ...string) {
 113         b.context.BuildTags = append(b.context.BuildTags, tags...)
 114 }
 115
 116 // Get package information from the go/build package. Automatically excludes
 117 // e.g. test files and files for other platforms-- there is quite a bit of
 118 // logic of that nature in the build package.
 119 func (b *Builder) importBuildPackage(dir string) (*build.Package, error) {
 120         if buildPkg, ok := b.buildPackages[dir]; ok {
 121                 return buildPkg, nil
 122         }
 123         // This validates the `package foo // github.com/bar/foo` comments.
 124         buildPkg, err := b.importWithMode(dir, build.ImportComment)
 125         if err != nil {
 126                 if _, ok := err.(*build.NoGoError); !ok {
 127                         return nil, fmt.Errorf("unable to import %q: %v", dir, err)
 128                 }
 129         }
 130         if buildPkg == nil {
 131                 // Might be an empty directory. Try to just find the dir.
 132                 buildPkg, err = b.importWithMode(dir, build.FindOnly)
 133                 if err != nil {
 134                         return nil, err
 135                 }
 136         }
 137
 138         // Remember it under the user-provided name.
 139         klog.V(5).Infof("saving buildPackage %s", dir)
 140         b.buildPackages[dir] = buildPkg
 141         canonicalPackage := canonicalizeImportPath(buildPkg.ImportPath)
 142         if dir != string(canonicalPackage) {
 143                 // Since `dir` is not the canonical name, see if we knew it under another name.
 144                 if buildPkg, ok := b.buildPackages[string(canonicalPackage)]; ok {
 145                         return buildPkg, nil
 146                 }
 147                 // Must be new, save it under the canonical name, too.
 148                 klog.V(5).Infof("saving buildPackage %s", canonicalPackage)
 149                 b.buildPackages[string(canonicalPackage)] = buildPkg
 150         }
 151
 152         return buildPkg, nil
 153 }
 154
 155 // AddFileForTest adds a file to the set, without verifying that the provided
 156 // pkg actually exists on disk. The pkg must be of the form "canonical/pkg/path"
 157 // and the path must be the absolute path to the file.  Because this bypasses
 158 // the normal recursive finding of package dependencies (on disk), test should
 159 // sort their test files topologically first, so all deps are resolved by the
 160 // time we need them.
 161 func (b *Builder) AddFileForTest(pkg string, path string, src []byte) error {
 162         if err := b.addFile(importPathString(pkg), path, src, true); err != nil {
 163                 return err
 164         }
 165         if _, err := b.typeCheckPackage(importPathString(pkg)); err != nil {
 166                 return err
 167         }
 168         return nil
 169 }
 170
 171 // addFile adds a file to the set. The pkgPath must be of the form
 172 // "canonical/pkg/path" and the path must be the absolute path to the file. A
 173 // flag indicates whether this file was user-requested or just from following
 174 // the import graph.
 175 func (b *Builder) addFile(pkgPath importPathString, path string, src []byte, userRequested bool) error {
 176         for _, p := range b.parsed[pkgPath] {
 177                 if path == p.name {
 178                         klog.V(5).Infof("addFile %s %s already parsed, skipping", pkgPath, path)
 179                         return nil
 180                 }
 181         }
 182         klog.V(6).Infof("addFile %s %s", pkgPath, path)
 183         p, err := parser.ParseFile(b.fset, path, src, parser.DeclarationErrors|parser.ParseComments)
 184         if err != nil {
 185                 return err
 186         }
 187
 188         // This is redundant with addDir, but some tests call AddFileForTest, which
 189         // call into here without calling addDir.
 190         b.userRequested[pkgPath] = userRequested || b.userRequested[pkgPath]
 191
 192         b.parsed[pkgPath] = append(b.parsed[pkgPath], parsedFile{path, p})
 193         for _, c := range p.Comments {
 194                 position := b.fset.Position(c.End())
 195                 b.endLineToCommentGroup[fileLine{position.Filename, position.Line}] = c
 196         }
 197
 198         // We have to get the packages from this specific file, in case the
 199         // user added individual files instead of entire directories.
 200         if b.importGraph[pkgPath] == nil {
 201                 b.importGraph[pkgPath] = map[string]struct{}{}
 202         }
 203         for _, im := range p.Imports {
 204                 importedPath := strings.Trim(im.Path.Value, `"`)
 205                 b.importGraph[pkgPath][importedPath] = struct{}{}
 206         }
 207         return nil
 208 }
 209
 210 // AddDir adds an entire directory, scanning it for go files. 'dir' should have
 211 // a single go package in it. GOPATH, GOROOT, and the location of your go
 212 // binary (`which go`) will all be searched if dir doesn't literally resolve.
 213 func (b *Builder) AddDir(dir string) error {
 214         _, err := b.importPackage(dir, true)
 215         return err
 216 }
 217
 218 // AddDirRecursive is just like AddDir, but it also recursively adds
 219 // subdirectories; it returns an error only if the path couldn't be resolved;
 220 // any directories recursed into without go source are ignored.
 221 func (b *Builder) AddDirRecursive(dir string) error {
 222         // Add the root.
 223         if _, err := b.importPackage(dir, true); err != nil {
 224                 klog.Warningf("Ignoring directory %v: %v", dir, err)
 225         }
 226
 227         // filepath.Walk includes the root dir, but we already did that, so we'll
 228         // remove that prefix and rebuild a package import path.
 229         prefix := b.buildPackages[dir].Dir
 230         fn := func(filePath string, info os.FileInfo, err error) error {
 231                 if info != nil && info.IsDir() {
 232                         rel := filepath.ToSlash(strings.TrimPrefix(filePath, prefix))
 233                         if rel != "" {
 234                                 // Make a pkg path.
 235                                 pkg := path.Join(string(canonicalizeImportPath(b.buildPackages[dir].ImportPath)), rel)
 236
 237                                 // Add it.
 238                                 if _, err := b.importPackage(pkg, true); err != nil {
 239                                         klog.Warningf("Ignoring child directory %v: %v", pkg, err)
 240                                 }
 241                         }
 242                 }
 243                 return nil
 244         }
 245         if err := filepath.Walk(b.buildPackages[dir].Dir, fn); err != nil {
 246                 return err
 247         }
 248         return nil
 249 }
 250
 251 // AddDirTo adds an entire directory to a given Universe. Unlike AddDir, this
 252 // processes the package immediately, which makes it safe to use from within a
 253 // generator (rather than just at init time. 'dir' must be a single go package.
 254 // GOPATH, GOROOT, and the location of your go binary (`which go`) will all be
 255 // searched if dir doesn't literally resolve.
 256 // Deprecated. Please use AddDirectoryTo.
 257 func (b *Builder) AddDirTo(dir string, u *types.Universe) error {
 258         // We want all types from this package, as if they were directly added
 259         // by the user.  They WERE added by the user, in effect.
 260         if _, err := b.importPackage(dir, true); err != nil {
 261                 return err
 262         }
 263         return b.findTypesIn(canonicalizeImportPath(b.buildPackages[dir].ImportPath), u)
 264 }
 265
 266 // AddDirectoryTo adds an entire directory to a given Universe. Unlike AddDir,
 267 // this processes the package immediately, which makes it safe to use from
 268 // within a generator (rather than just at init time. 'dir' must be a single go
 269 // package. GOPATH, GOROOT, and the location of your go binary (`which go`)
 270 // will all be searched if dir doesn't literally resolve.
 271 func (b *Builder) AddDirectoryTo(dir string, u *types.Universe) (*types.Package, error) {
 272         // We want all types from this package, as if they were directly added
 273         // by the user.  They WERE added by the user, in effect.
 274         if _, err := b.importPackage(dir, true); err != nil {
 275                 return nil, err
 276         }
 277         path := canonicalizeImportPath(b.buildPackages[dir].ImportPath)
 278         if err := b.findTypesIn(path, u); err != nil {
 279                 return nil, err
 280         }
 281         return u.Package(string(path)), nil
 282 }
 283
 284 // The implementation of AddDir. A flag indicates whether this directory was
 285 // user-requested or just from following the import graph.
 286 func (b *Builder) addDir(dir string, userRequested bool) error {
 287         klog.V(5).Infof("addDir %s", dir)
 288         buildPkg, err := b.importBuildPackage(dir)
 289         if err != nil {
 290                 return err
 291         }
 292         canonicalPackage := canonicalizeImportPath(buildPkg.ImportPath)
 293         pkgPath := canonicalPackage
 294         if dir != string(canonicalPackage) {
 295                 klog.V(5).Infof("addDir %s, canonical path is %s", dir, pkgPath)
 296         }
 297
 298         // Sanity check the pkg dir has not changed.
 299         if prev, found := b.absPaths[pkgPath]; found {
 300                 if buildPkg.Dir != prev {
 301                         return fmt.Errorf("package %q (%s) previously resolved to %s", pkgPath, buildPkg.Dir, prev)
 302                 }
 303         } else {
 304                 b.absPaths[pkgPath] = buildPkg.Dir
 305         }
 306
 307         for _, n := range buildPkg.GoFiles {
 308                 if !strings.HasSuffix(n, ".go") {
 309                         continue
 310                 }
 311                 absPath := filepath.Join(buildPkg.Dir, n)
 312                 data, err := ioutil.ReadFile(absPath)
 313                 if err != nil {
 314                         return fmt.Errorf("while loading %q: %v", absPath, err)
 315                 }
 316                 err = b.addFile(pkgPath, absPath, data, userRequested)
 317                 if err != nil {
 318                         return fmt.Errorf("while parsing %q: %v", absPath, err)
 319                 }
 320         }
 321         return nil
 322 }
 323
 324 // importPackage is a function that will be called by the type check package when it
 325 // needs to import a go package. 'path' is the import path.
 326 func (b *Builder) importPackage(dir string, userRequested bool) (*tc.Package, error) {
 327         klog.V(5).Infof("importPackage %s", dir)
 328         var pkgPath = importPathString(dir)
 329
 330         // Get the canonical path if we can.
 331         if buildPkg := b.buildPackages[dir]; buildPkg != nil {
 332                 canonicalPackage := canonicalizeImportPath(buildPkg.ImportPath)
 333                 klog.V(5).Infof("importPackage %s, canonical path is %s", dir, canonicalPackage)
 334                 pkgPath = canonicalPackage
 335         }
 336
 337         // If we have not seen this before, process it now.
 338         ignoreError := false
 339         if _, found := b.parsed[pkgPath]; !found {
 340                 // Ignore errors in paths that we're importing solely because
 341                 // they're referenced by other packages.
 342                 ignoreError = true
 343
 344                 // Add it.
 345                 if err := b.addDir(dir, userRequested); err != nil {
 346                         return nil, err
 347                 }
 348
 349                 // Get the canonical path now that it has been added.
 350                 if buildPkg := b.buildPackages[dir]; buildPkg != nil {
 351                         canonicalPackage := canonicalizeImportPath(buildPkg.ImportPath)
 352                         klog.V(5).Infof("importPackage %s, canonical path is %s", dir, canonicalPackage)
 353                         pkgPath = canonicalPackage
 354                 }
 355         }
 356
 357         // If it was previously known, just check that the user-requestedness hasn't
 358         // changed.
 359         b.userRequested[pkgPath] = userRequested || b.userRequested[pkgPath]
 360
 361         // Run the type checker.  We may end up doing this to pkgs that are already
 362         // done, or are in the queue to be done later, but it will short-circuit,
 363         // and we can't miss pkgs that are only depended on.
 364         pkg, err := b.typeCheckPackage(pkgPath)
 365         if err != nil {
 366                 switch {
 367                 case ignoreError && pkg != nil:
 368                         klog.V(2).Infof("type checking encountered some issues in %q, but ignoring.\n", pkgPath)
 369                 case !ignoreError && pkg != nil:
 370                         klog.V(2).Infof("type checking encountered some errors in %q\n", pkgPath)
 371                         return nil, err
 372                 default:
 373                         return nil, err
 374                 }
 375         }
 376
 377         return pkg, nil
 378 }
 379
 380 type importAdapter struct {
 381         b *Builder
 382 }
 383
 384 func (a importAdapter) Import(path string) (*tc.Package, error) {
 385         return a.b.importPackage(path, false)
 386 }
 387
 388 // typeCheckPackage will attempt to return the package even if there are some
 389 // errors, so you may check whether the package is nil or not even if you get
 390 // an error.
 391 func (b *Builder) typeCheckPackage(pkgPath importPathString) (*tc.Package, error) {
 392         klog.V(5).Infof("typeCheckPackage %s", pkgPath)
 393         if pkg, ok := b.typeCheckedPackages[pkgPath]; ok {
 394                 if pkg != nil {
 395                         klog.V(6).Infof("typeCheckPackage %s already done", pkgPath)
 396                         return pkg, nil
 397                 }
 398                 // We store a nil right before starting work on a package. So
 399                 // if we get here and it's present and nil, that means there's
 400                 // another invocation of this function on the call stack
 401                 // already processing this package.
 402                 return nil, fmt.Errorf("circular dependency for %q", pkgPath)
 403         }
 404         parsedFiles, ok := b.parsed[pkgPath]
 405         if !ok {
 406                 return nil, fmt.Errorf("No files for pkg %q", pkgPath)
 407         }
 408         files := make([]*ast.File, len(parsedFiles))
 409         for i := range parsedFiles {
 410                 files[i] = parsedFiles[i].file
 411         }
 412         b.typeCheckedPackages[pkgPath] = nil
 413         c := tc.Config{
 414                 IgnoreFuncBodies: true,
 415                 // Note that importAdapter can call b.importPackage which calls this
 416                 // method. So there can't be cycles in the import graph.
 417                 Importer: importAdapter{b},
 418                 Error: func(err error) {
 419                         klog.V(2).Infof("type checker: %v\n", err)
 420                 },
 421         }
 422         pkg, err := c.Check(string(pkgPath), b.fset, files, nil)
 423         b.typeCheckedPackages[pkgPath] = pkg // record the result whether or not there was an error
 424         return pkg, err
 425 }
 426
 427 // FindPackages fetches a list of the user-imported packages.
 428 // Note that you need to call b.FindTypes() first.
 429 func (b *Builder) FindPackages() []string {
 430         // Iterate packages in a predictable order.
 431         pkgPaths := []string{}
 432         for k := range b.typeCheckedPackages {
 433                 pkgPaths = append(pkgPaths, string(k))
 434         }
 435         sort.Strings(pkgPaths)
 436
 437         result := []string{}
 438         for _, pkgPath := range pkgPaths {
 439                 if b.userRequested[importPathString(pkgPath)] {
 440                         // Since walkType is recursive, all types that are in packages that
 441                         // were directly mentioned will be included.  We don't need to
 442                         // include all types in all transitive packages, though.
 443                         result = append(result, pkgPath)
 444                 }
 445         }
 446         return result
 447 }
 448
 449 // FindTypes finalizes the package imports, and searches through all the
 450 // packages for types.
 451 func (b *Builder) FindTypes() (types.Universe, error) {
 452         // Take a snapshot of pkgs to iterate, since this will recursively mutate
 453         // b.parsed. Iterate in a predictable order.
 454         pkgPaths := []string{}
 455         for pkgPath := range b.parsed {
 456                 pkgPaths = append(pkgPaths, string(pkgPath))
 457         }
 458         sort.Strings(pkgPaths)
 459
 460         u := types.Universe{}
 461         for _, pkgPath := range pkgPaths {
 462                 if err := b.findTypesIn(importPathString(pkgPath), &u); err != nil {
 463                         return nil, err
 464                 }
 465         }
 466         return u, nil
 467 }
 468
 469 // findTypesIn finalizes the package import and searches through the package
 470 // for types.
 471 func (b *Builder) findTypesIn(pkgPath importPathString, u *types.Universe) error {
 472         klog.V(5).Infof("findTypesIn %s", pkgPath)
 473         pkg := b.typeCheckedPackages[pkgPath]
 474         if pkg == nil {
 475                 return fmt.Errorf("findTypesIn(%s): package is not known", pkgPath)
 476         }
 477         if !b.userRequested[pkgPath] {
 478                 // Since walkType is recursive, all types that the
 479                 // packages they asked for depend on will be included.
 480                 // But we don't need to include all types in all
 481                 // *packages* they depend on.
 482                 klog.V(5).Infof("findTypesIn %s: package is not user requested", pkgPath)
 483                 return nil
 484         }
 485
 486         // We're keeping this package.  This call will create the record.
 487         u.Package(string(pkgPath)).Name = pkg.Name()
 488         u.Package(string(pkgPath)).Path = pkg.Path()
 489         u.Package(string(pkgPath)).SourcePath = b.absPaths[pkgPath]
 490
 491         for _, f := range b.parsed[pkgPath] {
 492                 if _, fileName := filepath.Split(f.name); fileName == "doc.go" {
 493                         tp := u.Package(string(pkgPath))
 494                         // findTypesIn might be called multiple times. Clean up tp.Comments
 495                         // to avoid repeatedly fill same comments to it.
 496                         tp.Comments = []string{}
 497                         for i := range f.file.Comments {
 498                                 tp.Comments = append(tp.Comments, splitLines(f.file.Comments[i].Text())...)
 499                         }
 500                         if f.file.Doc != nil {
 501                                 tp.DocComments = splitLines(f.file.Doc.Text())
 502                         }
 503                 }
 504         }
 505
 506         s := pkg.Scope()
 507         for _, n := range s.Names() {
 508                 obj := s.Lookup(n)
 509                 tn, ok := obj.(*tc.TypeName)
 510                 if ok {
 511                         t := b.walkType(*u, nil, tn.Type())
 512                         c1 := b.priorCommentLines(obj.Pos(), 1)
 513                         // c1.Text() is safe if c1 is nil
 514                         t.CommentLines = splitLines(c1.Text())
 515                         if c1 == nil {
 516                                 t.SecondClosestCommentLines = splitLines(b.priorCommentLines(obj.Pos(), 2).Text())
 517                         } else {
 518                                 t.SecondClosestCommentLines = splitLines(b.priorCommentLines(c1.List[0].Slash, 2).Text())
 519                         }
 520                 }
 521                 tf, ok := obj.(*tc.Func)
 522                 // We only care about functions, not concrete/abstract methods.
 523                 if ok && tf.Type() != nil && tf.Type().(*tc.Signature).Recv() == nil {
 524                         t := b.addFunction(*u, nil, tf)
 525                         c1 := b.priorCommentLines(obj.Pos(), 1)
 526                         // c1.Text() is safe if c1 is nil
 527                         t.CommentLines = splitLines(c1.Text())
 528                         if c1 == nil {
 529                                 t.SecondClosestCommentLines = splitLines(b.priorCommentLines(obj.Pos(), 2).Text())
 530                         } else {
 531                                 t.SecondClosestCommentLines = splitLines(b.priorCommentLines(c1.List[0].Slash, 2).Text())
 532                         }
 533                 }
 534                 tv, ok := obj.(*tc.Var)
 535                 if ok && !tv.IsField() {
 536                         b.addVariable(*u, nil, tv)
 537                 }
 538         }
 539
 540         importedPkgs := []string{}
 541         for k := range b.importGraph[pkgPath] {
 542                 importedPkgs = append(importedPkgs, string(k))
 543         }
 544         sort.Strings(importedPkgs)
 545         for _, p := range importedPkgs {
 546                 u.AddImports(string(pkgPath), p)
 547         }
 548         return nil
 549 }
 550
 551 func (b *Builder) importWithMode(dir string, mode build.ImportMode) (*build.Package, error) {
 552         // This is a bit of a hack.  The srcDir argument to Import() should
 553         // properly be the dir of the file which depends on the package to be
 554         // imported, so that vendoring can work properly and local paths can
 555         // resolve.  We assume that there is only one level of vendoring, and that
 556         // the CWD is inside the GOPATH, so this should be safe. Nobody should be
 557         // using local (relative) paths except on the CLI, so CWD is also
 558         // sufficient.
 559         cwd, err := os.Getwd()
 560         if err != nil {
 561                 return nil, fmt.Errorf("unable to get current directory: %v", err)
 562         }
 563         buildPkg, err := b.context.Import(dir, cwd, mode)
 564         if err != nil {
 565                 return nil, err
 566         }
 567         return buildPkg, nil
 568 }
 569
 570 // if there's a comment on the line `lines` before pos, return its text, otherwise "".
 571 func (b *Builder) priorCommentLines(pos token.Pos, lines int) *ast.CommentGroup {
 572         position := b.fset.Position(pos)
 573         key := fileLine{position.Filename, position.Line - lines}
 574         return b.endLineToCommentGroup[key]
 575 }
 576
 577 func splitLines(str string) []string {
 578         return strings.Split(strings.TrimRight(str, "\n"), "\n")
 579 }
 580
 581 func tcFuncNameToName(in string) types.Name {
 582         name := strings.TrimPrefix(in, "func ")
 583         nameParts := strings.Split(name, "(")
 584         return tcNameToName(nameParts[0])
 585 }
 586
 587 func tcVarNameToName(in string) types.Name {
 588         nameParts := strings.Split(in, " ")
 589         // nameParts[0] is "var".
 590         // nameParts[2:] is the type of the variable, we ignore it for now.
 591         return tcNameToName(nameParts[1])
 592 }
 593
 594 func tcNameToName(in string) types.Name {
 595         // Detect anonymous type names. (These may have '.' characters because
 596         // embedded types may have packages, so we detect them specially.)
 597         if strings.HasPrefix(in, "struct{") ||
 598                 strings.HasPrefix(in, "<-chan") ||
 599                 strings.HasPrefix(in, "chan<-") ||
 600                 strings.HasPrefix(in, "chan ") ||
 601                 strings.HasPrefix(in, "func(") ||
 602                 strings.HasPrefix(in, "*") ||
 603                 strings.HasPrefix(in, "map[") ||
 604                 strings.HasPrefix(in, "[") {
 605                 return types.Name{Name: in}
 606         }
 607
 608         // Otherwise, if there are '.' characters present, the name has a
 609         // package path in front.
 610         nameParts := strings.Split(in, ".")
 611         name := types.Name{Name: in}
 612         if n := len(nameParts); n >= 2 {
 613                 // The final "." is the name of the type--previous ones must
 614                 // have been in the package path.
 615                 name.Package, name.Name = strings.Join(nameParts[:n-1], "."), nameParts[n-1]
 616         }
 617         return name
 618 }
 619
 620 func (b *Builder) convertSignature(u types.Universe, t *tc.Signature) *types.Signature {
 621         signature := &types.Signature{}
 622         for i := 0; i < t.Params().Len(); i++ {
 623                 signature.Parameters = append(signature.Parameters, b.walkType(u, nil, t.Params().At(i).Type()))
 624         }
 625         for i := 0; i < t.Results().Len(); i++ {
 626                 signature.Results = append(signature.Results, b.walkType(u, nil, t.Results().At(i).Type()))
 627         }
 628         if r := t.Recv(); r != nil {
 629                 signature.Receiver = b.walkType(u, nil, r.Type())
 630         }
 631         signature.Variadic = t.Variadic()
 632         return signature
 633 }
 634
 635 // walkType adds the type, and any necessary child types.
 636 func (b *Builder) walkType(u types.Universe, useName *types.Name, in tc.Type) *types.Type {
 637         // Most of the cases are underlying types of the named type.
 638         name := tcNameToName(in.String())
 639         if useName != nil {
 640                 name = *useName
 641         }
 642
 643         switch t := in.(type) {
 644         case *tc.Struct:
 645                 out := u.Type(name)
 646                 if out.Kind != types.Unknown {
 647                         return out
 648                 }
 649                 out.Kind = types.Struct
 650                 for i := 0; i < t.NumFields(); i++ {
 651                         f := t.Field(i)
 652                         m := types.Member{
 653                                 Name:         f.Name(),
 654                                 Embedded:     f.Anonymous(),
 655                                 Tags:         t.Tag(i),
 656                                 Type:         b.walkType(u, nil, f.Type()),
 657                                 CommentLines: splitLines(b.priorCommentLines(f.Pos(), 1).Text()),
 658                         }
 659                         out.Members = append(out.Members, m)
 660                 }
 661                 return out
 662         case *tc.Map:
 663                 out := u.Type(name)
 664                 if out.Kind != types.Unknown {
 665                         return out
 666                 }
 667                 out.Kind = types.Map
 668                 out.Elem = b.walkType(u, nil, t.Elem())
 669                 out.Key = b.walkType(u, nil, t.Key())
 670                 return out
 671         case *tc.Pointer:
 672                 out := u.Type(name)
 673                 if out.Kind != types.Unknown {
 674                         return out
 675                 }
 676                 out.Kind = types.Pointer
 677                 out.Elem = b.walkType(u, nil, t.Elem())
 678                 return out
 679         case *tc.Slice:
 680                 out := u.Type(name)
 681                 if out.Kind != types.Unknown {
 682                         return out
 683                 }
 684                 out.Kind = types.Slice
 685                 out.Elem = b.walkType(u, nil, t.Elem())
 686                 return out
 687         case *tc.Array:
 688                 out := u.Type(name)
 689                 if out.Kind != types.Unknown {
 690                         return out
 691                 }
 692                 out.Kind = types.Array
 693                 out.Elem = b.walkType(u, nil, t.Elem())
 694                 // TODO: need to store array length, otherwise raw type name
 695                 // cannot be properly written.
 696                 return out
 697         case *tc.Chan:
 698                 out := u.Type(name)
 699                 if out.Kind != types.Unknown {
 700                         return out
 701                 }
 702                 out.Kind = types.Chan
 703                 out.Elem = b.walkType(u, nil, t.Elem())
 704                 // TODO: need to store direction, otherwise raw type name
 705                 // cannot be properly written.
 706                 return out
 707         case *tc.Basic:
 708                 out := u.Type(types.Name{
 709                         Package: "",
 710                         Name:    t.Name(),
 711                 })
 712                 if out.Kind != types.Unknown {
 713                         return out
 714                 }
 715                 out.Kind = types.Unsupported
 716                 return out
 717         case *tc.Signature:
 718                 out := u.Type(name)
 719                 if out.Kind != types.Unknown {
 720                         return out
 721                 }
 722                 out.Kind = types.Func
 723                 out.Signature = b.convertSignature(u, t)
 724                 return out
 725         case *tc.Interface:
 726                 out := u.Type(name)
 727                 if out.Kind != types.Unknown {
 728                         return out
 729                 }
 730                 out.Kind = types.Interface
 731                 t.Complete()
 732                 for i := 0; i < t.NumMethods(); i++ {
 733                         if out.Methods == nil {
 734                                 out.Methods = map[string]*types.Type{}
 735                         }
 736                         out.Methods[t.Method(i).Name()] = b.walkType(u, nil, t.Method(i).Type())
 737                 }
 738                 return out
 739         case *tc.Named:
 740                 var out *types.Type
 741                 switch t.Underlying().(type) {
 742                 case *tc.Named, *tc.Basic, *tc.Map, *tc.Slice:
 743                         name := tcNameToName(t.String())
 744                         out = u.Type(name)
 745                         if out.Kind != types.Unknown {
 746                                 return out
 747                         }
 748                         out.Kind = types.Alias
 749                         out.Underlying = b.walkType(u, nil, t.Underlying())
 750                 default:
 751                         // tc package makes everything "named" with an
 752                         // underlying anonymous type--we remove that annoying
 753                         // "feature" for users. This flattens those types
 754                         // together.
 755                         name := tcNameToName(t.String())
 756                         if out := u.Type(name); out.Kind != types.Unknown {
 757                                 return out // short circuit if we've already made this.
 758                         }
 759                         out = b.walkType(u, &name, t.Underlying())
 760                 }
 761                 // If the underlying type didn't already add methods, add them.
 762                 // (Interface types will have already added methods.)
 763                 if len(out.Methods) == 0 {
 764                         for i := 0; i < t.NumMethods(); i++ {
 765                                 if out.Methods == nil {
 766                                         out.Methods = map[string]*types.Type{}
 767                                 }
 768                                 out.Methods[t.Method(i).Name()] = b.walkType(u, nil, t.Method(i).Type())
 769                         }
 770                 }
 771                 return out
 772         default:
 773                 out := u.Type(name)
 774                 if out.Kind != types.Unknown {
 775                         return out
 776                 }
 777                 out.Kind = types.Unsupported
 778                 klog.Warningf("Making unsupported type entry %q for: %#v\n", out, t)
 779                 return out
 780         }
 781 }
 782
 783 func (b *Builder) addFunction(u types.Universe, useName *types.Name, in *tc.Func) *types.Type {
 784         name := tcFuncNameToName(in.String())
 785         if useName != nil {
 786                 name = *useName
 787         }
 788         out := u.Function(name)
 789         out.Kind = types.DeclarationOf
 790         out.Underlying = b.walkType(u, nil, in.Type())
 791         return out
 792 }
 793
 794 func (b *Builder) addVariable(u types.Universe, useName *types.Name, in *tc.Var) *types.Type {
 795         name := tcVarNameToName(in.String())
 796         if useName != nil {
 797                 name = *useName
 798         }
 799         out := u.Variable(name)
 800         out.Kind = types.DeclarationOf
 801         out.Underlying = b.walkType(u, nil, in.Type())
 802         return out
 803 }
 804
 805 // canonicalizeImportPath takes an import path and returns the actual package.
 806 // It doesn't support nested vendoring.
 807 func canonicalizeImportPath(importPath string) importPathString {
 808         if !strings.Contains(importPath, "/vendor/") {
 809                 return importPathString(importPath)
 810         }
 811
 812         return importPathString(importPath[strings.Index(importPath, "/vendor/")+len("/vendor/"):])
 813 }