src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

lookup.go (4170B)

      1 // Copyright 2024 The Go Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style
      3 // license that can be found in the LICENSE file.
      4 
      5 package modindex
      6 
      7 import (
      8 	"slices"
      9 	"strconv"
     10 	"strings"
     11 
     12 	"golang.org/x/mod/module"
     13 )
     14 
     15 type Candidate struct {
     16 	PkgName    string
     17 	Name       string
     18 	Dir        string
     19 	ImportPath string
     20 	Type       LexType
     21 	Deprecated bool
     22 	// information for Funcs
     23 	Results int16   // how many results
     24 	Sig     []Field // arg names and types
     25 }
     26 
     27 type Field struct {
     28 	Arg, Type string
     29 }
     30 
     31 type LexType int8
     32 
     33 const (
     34 	Const LexType = iota
     35 	Var
     36 	Type
     37 	Func
     38 )
     39 
     40 // LookupAll only returns those Candidates whose import path
     41 // finds all the names.
     42 func (ix *Index) LookupAll(pkgName string, names ...string) map[string][]Candidate {
     43 	// this can be made faster when benchmarks show that it needs to be
     44 	names = uniquify(names)
     45 	byImpPath := make(map[string][]Candidate)
     46 	for _, nm := range names {
     47 		cands := ix.Lookup(pkgName, nm, false)
     48 		for _, c := range cands {
     49 			byImpPath[c.ImportPath] = append(byImpPath[c.ImportPath], c)
     50 		}
     51 	}
     52 	for k, v := range byImpPath {
     53 		if len(v) != len(names) {
     54 			delete(byImpPath, k)
     55 		}
     56 	}
     57 	return byImpPath
     58 }
     59 
     60 // remove duplicates
     61 func uniquify(in []string) []string {
     62 	if len(in) == 0 {
     63 		return in
     64 	}
     65 	in = slices.Clone(in)
     66 	slices.Sort(in)
     67 	return slices.Compact(in)
     68 }
     69 
     70 // Lookup finds all the symbols in the index with the given PkgName and name.
     71 // If prefix is true, it finds all of these with name as a prefix.
     72 func (ix *Index) Lookup(pkgName, name string, prefix bool) []Candidate {
     73 	loc, ok := slices.BinarySearchFunc(ix.Entries, pkgName, func(e Entry, pkg string) int {
     74 		return strings.Compare(e.PkgName, pkgName)
     75 	})
     76 	if !ok {
     77 		return nil // didn't find the package
     78 	}
     79 	var ans []Candidate
     80 	// loc is the first entry for this package name, but there may be several
     81 	for i := loc; i < len(ix.Entries); i++ {
     82 		e := ix.Entries[i]
     83 		if e.PkgName != pkgName {
     84 			break // end of sorted package names
     85 		}
     86 		nloc, ok := slices.BinarySearchFunc(e.Names, name, func(s string, name string) int {
     87 			if strings.HasPrefix(s, name) {
     88 				return 0
     89 			}
     90 			if s < name {
     91 				return -1
     92 			}
     93 			return 1
     94 		})
     95 		if !ok {
     96 			continue // didn't find the name, nor any symbols with name as a prefix
     97 		}
     98 		for j := nloc; j < len(e.Names); j++ {
     99 			nstr := e.Names[j]
    100 			// benchmarks show this makes a difference when there are a lot of Possibilities
    101 			flds := fastSplit(nstr)
    102 			if !(flds[0] == name || prefix && strings.HasPrefix(flds[0], name)) {
    103 				// past range of matching Names
    104 				break
    105 			}
    106 			if len(flds) < 2 {
    107 				continue // should never happen
    108 			}
    109 			impPath, err := module.UnescapePath(e.ImportPath)
    110 			if err != nil {
    111 				continue
    112 			}
    113 			px := Candidate{
    114 				PkgName:    pkgName,
    115 				Name:       flds[0],
    116 				Dir:        string(e.Dir),
    117 				ImportPath: impPath,
    118 				Type:       asLexType(flds[1][0]),
    119 				Deprecated: len(flds[1]) > 1 && flds[1][1] == 'D',
    120 			}
    121 			if px.Type == Func {
    122 				n, err := strconv.Atoi(flds[2])
    123 				if err != nil {
    124 					continue // should never happen
    125 				}
    126 				px.Results = int16(n)
    127 				if len(flds) >= 4 {
    128 					sig := strings.Split(flds[3], " ")
    129 					for i := range sig {
    130 						// $ cannot otherwise occur. removing the spaces
    131 						// almost works, but for chan struct{}, e.g.
    132 						sig[i] = strings.Replace(sig[i], "$", " ", -1)
    133 					}
    134 					px.Sig = toFields(sig)
    135 				}
    136 			}
    137 			ans = append(ans, px)
    138 		}
    139 	}
    140 	return ans
    141 }
    142 
    143 func toFields(sig []string) []Field {
    144 	ans := make([]Field, len(sig)/2)
    145 	for i := range ans {
    146 		ans[i] = Field{Arg: sig[2*i], Type: sig[2*i+1]}
    147 	}
    148 	return ans
    149 }
    150 
    151 // benchmarks show this is measurably better than strings.Split
    152 // split into first 4 fields separated by single space
    153 func fastSplit(x string) []string {
    154 	ans := make([]string, 0, 4)
    155 	nxt := 0
    156 	start := 0
    157 	for i := 0; i < len(x); i++ {
    158 		if x[i] != ' ' {
    159 			continue
    160 		}
    161 		ans = append(ans, x[start:i])
    162 		nxt++
    163 		start = i + 1
    164 		if nxt >= 3 {
    165 			break
    166 		}
    167 	}
    168 	ans = append(ans, x[start:])
    169 	return ans
    170 }
    171 
    172 func asLexType(c byte) LexType {
    173 	switch c {
    174 	case 'C':
    175 		return Const
    176 	case 'V':
    177 		return Var
    178 	case 'T':
    179 		return Type
    180 	case 'F':
    181 		return Func
    182 	}
    183 	return -1
    184 }