diff options
Diffstat (limited to 'src/cmd/vendor/golang.org/x/tools/internal')
5 files changed, 139 insertions, 875 deletions
diff --git a/src/cmd/vendor/golang.org/x/tools/internal/analysisinternal/analysis.go b/src/cmd/vendor/golang.org/x/tools/internal/analysisinternal/analysis.go index 78ee2c06be..e32152ac22 100644 --- a/src/cmd/vendor/golang.org/x/tools/internal/analysisinternal/analysis.go +++ b/src/cmd/vendor/golang.org/x/tools/internal/analysisinternal/analysis.go @@ -11,10 +11,7 @@ import ( "go/ast" "go/token" "go/types" - "strings" - - "golang.org/x/tools/go/ast/astutil" - "golang.org/x/tools/internal/lsp/fuzzy" + "strconv" ) // Flag to gate diagnostics for fuzz tests in 1.18. @@ -37,7 +34,7 @@ func TypeErrorEndPos(fset *token.FileSet, src []byte, start token.Pos) token.Pos return end } -func ZeroValue(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Type) ast.Expr { +func ZeroValue(f *ast.File, pkg *types.Package, typ types.Type) ast.Expr { under := typ if n, ok := typ.(*types.Named); ok { under = n.Underlying() @@ -57,7 +54,7 @@ func ZeroValue(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.T case *types.Chan, *types.Interface, *types.Map, *types.Pointer, *types.Signature, *types.Slice, *types.Array: return ast.NewIdent("nil") case *types.Struct: - texpr := TypeExpr(fset, f, pkg, typ) // typ because we want the name here. + texpr := TypeExpr(f, pkg, typ) // typ because we want the name here. if texpr == nil { return nil } @@ -81,7 +78,7 @@ func IsZeroValue(expr ast.Expr) bool { } } -func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Type) ast.Expr { +func TypeExpr(f *ast.File, pkg *types.Package, typ types.Type) ast.Expr { switch t := typ.(type) { case *types.Basic: switch t.Kind() { @@ -91,7 +88,7 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty return ast.NewIdent(t.Name()) } case *types.Pointer: - x := TypeExpr(fset, f, pkg, t.Elem()) + x := TypeExpr(f, pkg, t.Elem()) if x == nil { return nil } @@ -100,7 +97,7 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty X: x, } case *types.Array: - elt := TypeExpr(fset, f, pkg, t.Elem()) + elt := TypeExpr(f, pkg, t.Elem()) if elt == nil { return nil } @@ -112,7 +109,7 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty Elt: elt, } case *types.Slice: - elt := TypeExpr(fset, f, pkg, t.Elem()) + elt := TypeExpr(f, pkg, t.Elem()) if elt == nil { return nil } @@ -120,8 +117,8 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty Elt: elt, } case *types.Map: - key := TypeExpr(fset, f, pkg, t.Key()) - value := TypeExpr(fset, f, pkg, t.Elem()) + key := TypeExpr(f, pkg, t.Key()) + value := TypeExpr(f, pkg, t.Elem()) if key == nil || value == nil { return nil } @@ -134,7 +131,7 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty if t.Dir() == types.SendRecv { dir = ast.SEND | ast.RECV } - value := TypeExpr(fset, f, pkg, t.Elem()) + value := TypeExpr(f, pkg, t.Elem()) if value == nil { return nil } @@ -145,7 +142,7 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty case *types.Signature: var params []*ast.Field for i := 0; i < t.Params().Len(); i++ { - p := TypeExpr(fset, f, pkg, t.Params().At(i).Type()) + p := TypeExpr(f, pkg, t.Params().At(i).Type()) if p == nil { return nil } @@ -160,7 +157,7 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty } var returns []*ast.Field for i := 0; i < t.Results().Len(); i++ { - r := TypeExpr(fset, f, pkg, t.Results().At(i).Type()) + r := TypeExpr(f, pkg, t.Results().At(i).Type()) if r == nil { return nil } @@ -184,13 +181,12 @@ func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Ty return ast.NewIdent(t.Obj().Name()) } pkgName := t.Obj().Pkg().Name() + // If the file already imports the package under another name, use that. - for _, group := range astutil.Imports(fset, f) { - for _, cand := range group { - if strings.Trim(cand.Path.Value, `"`) == t.Obj().Pkg().Path() { - if cand.Name != nil && cand.Name.Name != "" { - pkgName = cand.Name.Name - } + for _, cand := range f.Imports { + if path, _ := strconv.Unquote(cand.Path.Value); path == t.Obj().Pkg().Path() { + if cand.Name != nil && cand.Name.Name != "" { + pkgName = cand.Name.Name } } } @@ -399,30 +395,3 @@ func equivalentTypes(want, got types.Type) bool { } return types.AssignableTo(want, got) } - -// FindBestMatch employs fuzzy matching to evaluate the similarity of each given identifier to the -// given pattern. We return the identifier whose name is most similar to the pattern. -func FindBestMatch(pattern string, idents []*ast.Ident) ast.Expr { - fuzz := fuzzy.NewMatcher(pattern) - var bestFuzz ast.Expr - highScore := float32(0) // minimum score is 0 (no match) - for _, ident := range idents { - // TODO: Improve scoring algorithm. - score := fuzz.Score(ident.Name) - if score > highScore { - highScore = score - bestFuzz = ident - } else if score == 0 { - // Order matters in the fuzzy matching algorithm. If we find no match - // when matching the target to the identifier, try matching the identifier - // to the target. - revFuzz := fuzzy.NewMatcher(ident.Name) - revScore := revFuzz.Score(pattern) - if revScore > highScore { - highScore = revScore - bestFuzz = ident - } - } - } - return bestFuzz -} diff --git a/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/input.go b/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/input.go deleted file mode 100644 index c1038163f1..0000000000 --- a/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/input.go +++ /dev/null @@ -1,183 +0,0 @@ -// Copyright 2019 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package fuzzy - -import ( - "unicode" -) - -// RuneRole specifies the role of a rune in the context of an input. -type RuneRole byte - -const ( - // RNone specifies a rune without any role in the input (i.e., whitespace/non-ASCII). - RNone RuneRole = iota - // RSep specifies a rune with the role of segment separator. - RSep - // RTail specifies a rune which is a lower-case tail in a word in the input. - RTail - // RUCTail specifies a rune which is an upper-case tail in a word in the input. - RUCTail - // RHead specifies a rune which is the first character in a word in the input. - RHead -) - -// RuneRoles detects the roles of each byte rune in an input string and stores it in the output -// slice. The rune role depends on the input type. Stops when it parsed all the runes in the string -// or when it filled the output. If output is nil, then it gets created. -func RuneRoles(candidate []byte, reuse []RuneRole) []RuneRole { - var output []RuneRole - if cap(reuse) < len(candidate) { - output = make([]RuneRole, 0, len(candidate)) - } else { - output = reuse[:0] - } - - prev, prev2 := rtNone, rtNone - for i := 0; i < len(candidate); i++ { - r := rune(candidate[i]) - - role := RNone - - curr := rtLower - if candidate[i] <= unicode.MaxASCII { - curr = runeType(rt[candidate[i]] - '0') - } - - if curr == rtLower { - if prev == rtNone || prev == rtPunct { - role = RHead - } else { - role = RTail - } - } else if curr == rtUpper { - role = RHead - - if prev == rtUpper { - // This and previous characters are both upper case. - - if i+1 == len(candidate) { - // This is last character, previous was also uppercase -> this is UCTail - // i.e., (current char is C): aBC / BC / ABC - role = RUCTail - } - } - } else if curr == rtPunct { - switch r { - case '.', ':': - role = RSep - } - } - if curr != rtLower { - if i > 1 && output[i-1] == RHead && prev2 == rtUpper && (output[i-2] == RHead || output[i-2] == RUCTail) { - // The previous two characters were uppercase. The current one is not a lower case, so the - // previous one can't be a HEAD. Make it a UCTail. - // i.e., (last char is current char - B must be a UCTail): ABC / ZABC / AB. - output[i-1] = RUCTail - } - } - - output = append(output, role) - prev2 = prev - prev = curr - } - return output -} - -type runeType byte - -const ( - rtNone runeType = iota - rtPunct - rtLower - rtUpper -) - -const rt = "00000000000000000000000000000000000000000000001122222222221000000333333333333333333333333330000002222222222222222222222222200000" - -// LastSegment returns the substring representing the last segment from the input, where each -// byte has an associated RuneRole in the roles slice. This makes sense only for inputs of Symbol -// or Filename type. -func LastSegment(input string, roles []RuneRole) string { - // Exclude ending separators. - end := len(input) - 1 - for end >= 0 && roles[end] == RSep { - end-- - } - if end < 0 { - return "" - } - - start := end - 1 - for start >= 0 && roles[start] != RSep { - start-- - } - - return input[start+1 : end+1] -} - -// fromChunks copies string chunks into the given buffer. -func fromChunks(chunks []string, buffer []byte) []byte { - ii := 0 - for _, chunk := range chunks { - for i := 0; i < len(chunk); i++ { - if ii >= cap(buffer) { - break - } - buffer[ii] = chunk[i] - ii++ - } - } - return buffer[:ii] -} - -// toLower transforms the input string to lower case, which is stored in the output byte slice. -// The lower casing considers only ASCII values - non ASCII values are left unmodified. -// Stops when parsed all input or when it filled the output slice. If output is nil, then it gets -// created. -func toLower(input []byte, reuse []byte) []byte { - output := reuse - if cap(reuse) < len(input) { - output = make([]byte, len(input)) - } - - for i := 0; i < len(input); i++ { - r := rune(input[i]) - if input[i] <= unicode.MaxASCII { - if 'A' <= r && r <= 'Z' { - r += 'a' - 'A' - } - } - output[i] = byte(r) - } - return output[:len(input)] -} - -// WordConsumer defines a consumer for a word delimited by the [start,end) byte offsets in an input -// (start is inclusive, end is exclusive). -type WordConsumer func(start, end int) - -// Words find word delimiters in an input based on its bytes' mappings to rune roles. The offset -// delimiters for each word are fed to the provided consumer function. -func Words(roles []RuneRole, consume WordConsumer) { - var wordStart int - for i, r := range roles { - switch r { - case RUCTail, RTail: - case RHead, RNone, RSep: - if i != wordStart { - consume(wordStart, i) - } - wordStart = i - if r != RHead { - // Skip this character. - wordStart = i + 1 - } - } - } - if wordStart != len(roles) { - consume(wordStart, len(roles)) - } -} diff --git a/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/matcher.go b/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/matcher.go deleted file mode 100644 index 265cdcf160..0000000000 --- a/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/matcher.go +++ /dev/null @@ -1,407 +0,0 @@ -// Copyright 2019 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Package fuzzy implements a fuzzy matching algorithm. -package fuzzy - -import ( - "bytes" - "fmt" -) - -const ( - // MaxInputSize is the maximum size of the input scored against the fuzzy matcher. Longer inputs - // will be truncated to this size. - MaxInputSize = 127 - // MaxPatternSize is the maximum size of the pattern used to construct the fuzzy matcher. Longer - // inputs are truncated to this size. - MaxPatternSize = 63 -) - -type scoreVal int - -func (s scoreVal) val() int { - return int(s) >> 1 -} - -func (s scoreVal) prevK() int { - return int(s) & 1 -} - -func score(val int, prevK int /*0 or 1*/) scoreVal { - return scoreVal(val<<1 + prevK) -} - -// Matcher implements a fuzzy matching algorithm for scoring candidates against a pattern. -// The matcher does not support parallel usage. -type Matcher struct { - pattern string - patternLower []byte // lower-case version of the pattern - patternShort []byte // first characters of the pattern - caseSensitive bool // set if the pattern is mix-cased - - patternRoles []RuneRole // the role of each character in the pattern - roles []RuneRole // the role of each character in the tested string - - scores [MaxInputSize + 1][MaxPatternSize + 1][2]scoreVal - - scoreScale float32 - - lastCandidateLen int // in bytes - lastCandidateMatched bool - - // Reusable buffers to avoid allocating for every candidate. - // - inputBuf stores the concatenated input chunks - // - lowerBuf stores the last candidate in lower-case - // - rolesBuf stores the calculated roles for each rune in the last - // candidate. - inputBuf [MaxInputSize]byte - lowerBuf [MaxInputSize]byte - rolesBuf [MaxInputSize]RuneRole -} - -func (m *Matcher) bestK(i, j int) int { - if m.scores[i][j][0].val() < m.scores[i][j][1].val() { - return 1 - } - return 0 -} - -// NewMatcher returns a new fuzzy matcher for scoring candidates against the provided pattern. -func NewMatcher(pattern string) *Matcher { - if len(pattern) > MaxPatternSize { - pattern = pattern[:MaxPatternSize] - } - - m := &Matcher{ - pattern: pattern, - patternLower: toLower([]byte(pattern), nil), - } - - for i, c := range m.patternLower { - if pattern[i] != c { - m.caseSensitive = true - break - } - } - - if len(pattern) > 3 { - m.patternShort = m.patternLower[:3] - } else { - m.patternShort = m.patternLower - } - - m.patternRoles = RuneRoles([]byte(pattern), nil) - - if len(pattern) > 0 { - maxCharScore := 4 - m.scoreScale = 1 / float32(maxCharScore*len(pattern)) - } - - return m -} - -// Score returns the score returned by matching the candidate to the pattern. -// This is not designed for parallel use. Multiple candidates must be scored sequentially. -// Returns a score between 0 and 1 (0 - no match, 1 - perfect match). -func (m *Matcher) Score(candidate string) float32 { - return m.ScoreChunks([]string{candidate}) -} - -func (m *Matcher) ScoreChunks(chunks []string) float32 { - candidate := fromChunks(chunks, m.inputBuf[:]) - if len(candidate) > MaxInputSize { - candidate = candidate[:MaxInputSize] - } - lower := toLower(candidate, m.lowerBuf[:]) - m.lastCandidateLen = len(candidate) - - if len(m.pattern) == 0 { - // Empty patterns perfectly match candidates. - return 1 - } - - if m.match(candidate, lower) { - sc := m.computeScore(candidate, lower) - if sc > minScore/2 && !m.poorMatch() { - m.lastCandidateMatched = true - if len(m.pattern) == len(candidate) { - // Perfect match. - return 1 - } - - if sc < 0 { - sc = 0 - } - normalizedScore := float32(sc) * m.scoreScale - if normalizedScore > 1 { - normalizedScore = 1 - } - - return normalizedScore - } - } - - m.lastCandidateMatched = false - return 0 -} - -const minScore = -10000 - -// MatchedRanges returns matches ranges for the last scored string as a flattened array of -// [begin, end) byte offset pairs. -func (m *Matcher) MatchedRanges() []int { - if len(m.pattern) == 0 || !m.lastCandidateMatched { - return nil - } - i, j := m.lastCandidateLen, len(m.pattern) - if m.scores[i][j][0].val() < minScore/2 && m.scores[i][j][1].val() < minScore/2 { - return nil - } - - var ret []int - k := m.bestK(i, j) - for i > 0 { - take := (k == 1) - k = m.scores[i][j][k].prevK() - if take { - if len(ret) == 0 || ret[len(ret)-1] != i { - ret = append(ret, i) - ret = append(ret, i-1) - } else { - ret[len(ret)-1] = i - 1 - } - j-- - } - i-- - } - // Reverse slice. - for i := 0; i < len(ret)/2; i++ { - ret[i], ret[len(ret)-1-i] = ret[len(ret)-1-i], ret[i] - } - return ret -} - -func (m *Matcher) match(candidate []byte, candidateLower []byte) bool { - i, j := 0, 0 - for ; i < len(candidateLower) && j < len(m.patternLower); i++ { - if candidateLower[i] == m.patternLower[j] { - j++ - } - } - if j != len(m.patternLower) { - return false - } - - // The input passes the simple test against pattern, so it is time to classify its characters. - // Character roles are used below to find the last segment. - m.roles = RuneRoles(candidate, m.rolesBuf[:]) - - return true -} - -func (m *Matcher) computeScore(candidate []byte, candidateLower []byte) int { - pattLen, candLen := len(m.pattern), len(candidate) - - for j := 0; j <= len(m.pattern); j++ { - m.scores[0][j][0] = minScore << 1 - m.scores[0][j][1] = minScore << 1 - } - m.scores[0][0][0] = score(0, 0) // Start with 0. - - segmentsLeft, lastSegStart := 1, 0 - for i := 0; i < candLen; i++ { - if m.roles[i] == RSep { - segmentsLeft++ - lastSegStart = i + 1 - } - } - - // A per-character bonus for a consecutive match. - consecutiveBonus := 2 - wordIdx := 0 // Word count within segment. - for i := 1; i <= candLen; i++ { - - role := m.roles[i-1] - isHead := role == RHead - - if isHead { - wordIdx++ - } else if role == RSep && segmentsLeft > 1 { - wordIdx = 0 - segmentsLeft-- - } - - var skipPenalty int - if i == 1 || (i-1) == lastSegStart { - // Skipping the start of first or last segment. - skipPenalty++ - } - - for j := 0; j <= pattLen; j++ { - // By default, we don't have a match. Fill in the skip data. - m.scores[i][j][1] = minScore << 1 - - // Compute the skip score. - k := 0 - if m.scores[i-1][j][0].val() < m.scores[i-1][j][1].val() { - k = 1 - } - - skipScore := m.scores[i-1][j][k].val() - // Do not penalize missing characters after the last matched segment. - if j != pattLen { - skipScore -= skipPenalty - } - m.scores[i][j][0] = score(skipScore, k) - - if j == 0 || candidateLower[i-1] != m.patternLower[j-1] { - // Not a match. - continue - } - pRole := m.patternRoles[j-1] - - if role == RTail && pRole == RHead { - if j > 1 { - // Not a match: a head in the pattern matches a tail character in the candidate. - continue - } - // Special treatment for the first character of the pattern. We allow - // matches in the middle of a word if they are long enough, at least - // min(3, pattern.length) characters. - if !bytes.HasPrefix(candidateLower[i-1:], m.patternShort) { - continue - } - } - - // Compute the char score. - var charScore int - // Bonus 1: the char is in the candidate's last segment. - if segmentsLeft <= 1 { - charScore++ - } - // Bonus 2: Case match or a Head in the pattern aligns with one in the word. - // Single-case patterns lack segmentation signals and we assume any character - // can be a head of a segment. - if candidate[i-1] == m.pattern[j-1] || role == RHead && (!m.caseSensitive || pRole == RHead) { - charScore++ - } - - // Penalty 1: pattern char is Head, candidate char is Tail. - if role == RTail && pRole == RHead { - charScore-- - } - // Penalty 2: first pattern character matched in the middle of a word. - if j == 1 && role == RTail { - charScore -= 4 - } - - // Third dimension encodes whether there is a gap between the previous match and the current - // one. - for k := 0; k < 2; k++ { - sc := m.scores[i-1][j-1][k].val() + charScore - - isConsecutive := k == 1 || i-1 == 0 || i-1 == lastSegStart - if isConsecutive { - // Bonus 3: a consecutive match. First character match also gets a bonus to - // ensure prefix final match score normalizes to 1.0. - // Logically, this is a part of charScore, but we have to compute it here because it - // only applies for consecutive matches (k == 1). - sc += consecutiveBonus - } - if k == 0 { - // Penalty 3: Matching inside a segment (and previous char wasn't matched). Penalize for the lack - // of alignment. - if role == RTail || role == RUCTail { - sc -= 3 - } - } - - if sc > m.scores[i][j][1].val() { - m.scores[i][j][1] = score(sc, k) - } - } - } - } - - result := m.scores[len(candidate)][len(m.pattern)][m.bestK(len(candidate), len(m.pattern))].val() - - return result -} - -// ScoreTable returns the score table computed for the provided candidate. Used only for debugging. -func (m *Matcher) ScoreTable(candidate string) string { - var buf bytes.Buffer - - var line1, line2, separator bytes.Buffer - line1.WriteString("\t") - line2.WriteString("\t") - for j := 0; j < len(m.pattern); j++ { - line1.WriteString(fmt.Sprintf("%c\t\t", m.pattern[j])) - separator.WriteString("----------------") - } - - buf.WriteString(line1.String()) - buf.WriteString("\n") - buf.WriteString(separator.String()) - buf.WriteString("\n") - - for i := 1; i <= len(candidate); i++ { - line1.Reset() - line2.Reset() - - line1.WriteString(fmt.Sprintf("%c\t", candidate[i-1])) - line2.WriteString("\t") - - for j := 1; j <= len(m.pattern); j++ { - line1.WriteString(fmt.Sprintf("M%6d(%c)\t", m.scores[i][j][0].val(), dir(m.scores[i][j][0].prevK()))) - line2.WriteString(fmt.Sprintf("H%6d(%c)\t", m.scores[i][j][1].val(), dir(m.scores[i][j][1].prevK()))) - } - buf.WriteString(line1.String()) - buf.WriteString("\n") - buf.WriteString(line2.String()) - buf.WriteString("\n") - buf.WriteString(separator.String()) - buf.WriteString("\n") - } - - return buf.String() -} - -func dir(prevK int) rune { - if prevK == 0 { - return 'M' - } - return 'H' -} - -func (m *Matcher) poorMatch() bool { - if len(m.pattern) < 2 { - return false - } - - i, j := m.lastCandidateLen, len(m.pattern) - k := m.bestK(i, j) - - var counter, len int - for i > 0 { - take := (k == 1) - k = m.scores[i][j][k].prevK() - if take { - len++ - if k == 0 && len < 3 && m.roles[i-1] == RTail { - // Short match in the middle of a word - counter++ - if counter > 1 { - return true - } - } - j-- - } else { - len = 0 - } - i-- - } - return false -} diff --git a/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/symbol.go b/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/symbol.go deleted file mode 100644 index 073a4cd101..0000000000 --- a/src/cmd/vendor/golang.org/x/tools/internal/lsp/fuzzy/symbol.go +++ /dev/null @@ -1,237 +0,0 @@ -// Copyright 2021 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package fuzzy - -import ( - "unicode" -) - -// SymbolMatcher implements a fuzzy matching algorithm optimized for Go symbols -// of the form: -// -// example.com/path/to/package.object.field -// -// Knowing that we are matching symbols like this allows us to make the -// following optimizations: -// - We can incorporate right-to-left relevance directly into the score -// calculation. -// - We can match from right to left, discarding leading bytes if the input is -// too long. -// - We just take the right-most match without losing too much precision. This -// allows us to use an O(n) algorithm. -// - We can operate directly on chunked strings; in many cases we will -// be storing the package path and/or package name separately from the -// symbol or identifiers, so doing this avoids allocating strings. -// - We can return the index of the right-most match, allowing us to trim -// irrelevant qualification. -// -// This implementation is experimental, serving as a reference fast algorithm -// to compare to the fuzzy algorithm implemented by Matcher. -type SymbolMatcher struct { - // Using buffers of length 256 is both a reasonable size for most qualified - // symbols, and makes it easy to avoid bounds checks by using uint8 indexes. - pattern [256]rune - patternLen uint8 - inputBuffer [256]rune // avoid allocating when considering chunks - roles [256]uint32 // which roles does a rune play (word start, etc.) - segments [256]uint8 // how many segments from the right is each rune -} - -const ( - segmentStart uint32 = 1 << iota - wordStart - separator -) - -// NewSymbolMatcher creates a SymbolMatcher that may be used to match the given -// search pattern. -// -// Currently this matcher only accepts case-insensitive fuzzy patterns. -// -// An empty pattern matches no input. -func NewSymbolMatcher(pattern string) *SymbolMatcher { - m := &SymbolMatcher{} - for _, p := range pattern { - m.pattern[m.patternLen] = unicode.ToLower(p) - m.patternLen++ - if m.patternLen == 255 || int(m.patternLen) == len(pattern) { - // break at 255 so that we can represent patternLen with a uint8. - break - } - } - return m -} - -// Match looks for the right-most match of the search pattern within the symbol -// represented by concatenating the given chunks, returning its offset and -// score. -// -// If a match is found, the first return value will hold the absolute byte -// offset within all chunks for the start of the symbol. In other words, the -// index of the match within strings.Join(chunks, ""). If no match is found, -// the first return value will be -1. -// -// The second return value will be the score of the match, which is always -// between 0 and 1, inclusive. A score of 0 indicates no match. -func (m *SymbolMatcher) Match(chunks []string) (int, float64) { - // Explicit behavior for an empty pattern. - // - // As a minor optimization, this also avoids nilness checks later on, since - // the compiler can prove that m != nil. - if m.patternLen == 0 { - return -1, 0 - } - - // First phase: populate the input buffer with lower-cased runes. - // - // We could also check for a forward match here, but since we'd have to write - // the entire input anyway this has negligible impact on performance. - - var ( - inputLen = uint8(0) - modifiers = wordStart | segmentStart - ) - -input: - for _, chunk := range chunks { - for _, r := range chunk { - if r == '.' || r == '/' { - modifiers |= separator - } - // optimization: avoid calls to unicode.ToLower, which can't be inlined. - l := r - if r <= unicode.MaxASCII { - if 'A' <= r && r <= 'Z' { - l = r + 'a' - 'A' - } - } else { - l = unicode.ToLower(r) - } - if l != r { - modifiers |= wordStart - } - m.inputBuffer[inputLen] = l - m.roles[inputLen] = modifiers - inputLen++ - if m.roles[inputLen-1]&separator != 0 { - modifiers = wordStart | segmentStart - } else { - modifiers = 0 - } - // TODO: we should prefer the right-most input if it overflows, rather - // than the left-most as we're doing here. - if inputLen == 255 { - break input - } - } - } - - // Second phase: find the right-most match, and count segments from the - // right. - - var ( - pi = uint8(m.patternLen - 1) // pattern index - p = m.pattern[pi] // pattern rune - start = -1 // start offset of match - rseg = uint8(0) - ) - const maxSeg = 3 // maximum number of segments from the right to count, for scoring purposes. - - for ii := inputLen - 1; ; ii-- { - r := m.inputBuffer[ii] - if rseg < maxSeg && m.roles[ii]&separator != 0 { - rseg++ - } - m.segments[ii] = rseg - if p == r { - if pi == 0 { - start = int(ii) - break - } - pi-- - p = m.pattern[pi] - } - // Don't check ii >= 0 in the loop condition: ii is a uint8. - if ii == 0 { - break - } - } - - if start < 0 { - // no match: skip scoring - return -1, 0 - } - - // Third phase: find the shortest match, and compute the score. - - // Score is the average score for each character. - // - // A character score is the multiple of: - // 1. 1.0 if the character starts a segment, .8 if the character start a - // mid-segment word, otherwise 0.6. This carries over to immediately - // following characters. - // 2. For the final character match, the multiplier from (1) is reduced to - // .8 if the next character in the input is a mid-segment word, or 0.6 if - // the next character in the input is not a word or segment start. This - // ensures that we favor whole-word or whole-segment matches over prefix - // matches. - // 3. 1.0 if the character is part of the last segment, otherwise - // 1.0-.2*<segments from the right>, with a max segment count of 3. - // - // This is a very naive algorithm, but it is fast. There's lots of prior art - // here, and we should leverage it. For example, we could explicitly consider - // character distance, and exact matches of words or segments. - // - // Also note that this might not actually find the highest scoring match, as - // doing so could require a non-linear algorithm, depending on how the score - // is calculated. - - pi = 0 - p = m.pattern[pi] - - const ( - segStreak = 1.0 - wordStreak = 0.8 - noStreak = 0.6 - perSegment = 0.2 // we count at most 3 segments above - ) - - streakBonus := noStreak - totScore := 0.0 - for ii := uint8(start); ii < inputLen; ii++ { - r := m.inputBuffer[ii] - if r == p { - pi++ - p = m.pattern[pi] - // Note: this could be optimized with some bit operations. - switch { - case m.roles[ii]&segmentStart != 0 && segStreak > streakBonus: - streakBonus = segStreak - case m.roles[ii]&wordStart != 0 && wordStreak > streakBonus: - streakBonus = wordStreak - } - finalChar := pi >= m.patternLen - // finalCost := 1.0 - if finalChar && streakBonus > noStreak { - switch { - case ii == inputLen-1 || m.roles[ii+1]&segmentStart != 0: - // Full segment: no reduction - case m.roles[ii+1]&wordStart != 0: - streakBonus = wordStreak - default: - streakBonus = noStreak - } - } - totScore += streakBonus * (1.0 - float64(m.segments[ii])*perSegment) - if finalChar { - break - } - } else { - streakBonus = noStreak - } - } - - return start, totScore / float64(m.patternLen) -} diff --git a/src/cmd/vendor/golang.org/x/tools/internal/typeparams/coretype.go b/src/cmd/vendor/golang.org/x/tools/internal/typeparams/coretype.go new file mode 100644 index 0000000000..993135ec90 --- /dev/null +++ b/src/cmd/vendor/golang.org/x/tools/internal/typeparams/coretype.go @@ -0,0 +1,122 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package typeparams + +import ( + "go/types" +) + +// CoreType returns the core type of T or nil if T does not have a core type. +// +// See https://go.dev/ref/spec#Core_types for the definition of a core type. +func CoreType(T types.Type) types.Type { + U := T.Underlying() + if _, ok := U.(*types.Interface); !ok { + return U // for non-interface types, + } + + terms, err := _NormalTerms(U) + if len(terms) == 0 || err != nil { + // len(terms) -> empty type set of interface. + // err != nil => U is invalid, exceeds complexity bounds, or has an empty type set. + return nil // no core type. + } + + U = terms[0].Type().Underlying() + var identical int // i in [0,identical) => Identical(U, terms[i].Type().Underlying()) + for identical = 1; identical < len(terms); identical++ { + if !types.Identical(U, terms[identical].Type().Underlying()) { + break + } + } + + if identical == len(terms) { + // https://go.dev/ref/spec#Core_types + // "There is a single type U which is the underlying type of all types in the type set of T" + return U + } + ch, ok := U.(*types.Chan) + if !ok { + return nil // no core type as identical < len(terms) and U is not a channel. + } + // https://go.dev/ref/spec#Core_types + // "the type chan E if T contains only bidirectional channels, or the type chan<- E or + // <-chan E depending on the direction of the directional channels present." + for chans := identical; chans < len(terms); chans++ { + curr, ok := terms[chans].Type().Underlying().(*types.Chan) + if !ok { + return nil + } + if !types.Identical(ch.Elem(), curr.Elem()) { + return nil // channel elements are not identical. + } + if ch.Dir() == types.SendRecv { + // ch is bidirectional. We can safely always use curr's direction. + ch = curr + } else if curr.Dir() != types.SendRecv && ch.Dir() != curr.Dir() { + // ch and curr are not bidirectional and not the same direction. + return nil + } + } + return ch +} + +// _NormalTerms returns a slice of terms representing the normalized structural +// type restrictions of a type, if any. +// +// For all types other than *types.TypeParam, *types.Interface, and +// *types.Union, this is just a single term with Tilde() == false and +// Type() == typ. For *types.TypeParam, *types.Interface, and *types.Union, see +// below. +// +// Structural type restrictions of a type parameter are created via +// non-interface types embedded in its constraint interface (directly, or via a +// chain of interface embeddings). For example, in the declaration type +// T[P interface{~int; m()}] int the structural restriction of the type +// parameter P is ~int. +// +// With interface embedding and unions, the specification of structural type +// restrictions may be arbitrarily complex. For example, consider the +// following: +// +// type A interface{ ~string|~[]byte } +// +// type B interface{ int|string } +// +// type C interface { ~string|~int } +// +// type T[P interface{ A|B; C }] int +// +// In this example, the structural type restriction of P is ~string|int: A|B +// expands to ~string|~[]byte|int|string, which reduces to ~string|~[]byte|int, +// which when intersected with C (~string|~int) yields ~string|int. +// +// _NormalTerms computes these expansions and reductions, producing a +// "normalized" form of the embeddings. A structural restriction is normalized +// if it is a single union containing no interface terms, and is minimal in the +// sense that removing any term changes the set of types satisfying the +// constraint. It is left as a proof for the reader that, modulo sorting, there +// is exactly one such normalized form. +// +// Because the minimal representation always takes this form, _NormalTerms +// returns a slice of tilde terms corresponding to the terms of the union in +// the normalized structural restriction. An error is returned if the type is +// invalid, exceeds complexity bounds, or has an empty type set. In the latter +// case, _NormalTerms returns ErrEmptyTypeSet. +// +// _NormalTerms makes no guarantees about the order of terms, except that it +// is deterministic. +func _NormalTerms(typ types.Type) ([]*Term, error) { + switch typ := typ.(type) { + case *TypeParam: + return StructuralTerms(typ) + case *Union: + return UnionTermSet(typ) + case *types.Interface: + return InterfaceTermSet(typ) + default: + return []*Term{NewTerm(false, typ)}, nil + } +} |