blob: 9d2026f3603097198f2cc5bc2a6839b671ed0405 [file] [log] [blame]
// Copyright 2023 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 typerefs
import (
"fmt"
"math/bits"
"sort"
"strings"
"sync"
"golang.org/x/tools/gopls/internal/lsp/cache/metadata"
)
// PackageIndex stores common data to enable efficient representation of
// references and package sets.
type PackageIndex struct {
// For now, PackageIndex just indexes package ids, to save space and allow for
// faster unions via sparse int vectors.
mu sync.Mutex
ids []metadata.PackageID
m map[metadata.PackageID]IndexID
}
// NewPackageIndex creates a new PackageIndex instance for use in building
// reference and package sets.
func NewPackageIndex() *PackageIndex {
return &PackageIndex{
m: make(map[metadata.PackageID]IndexID),
}
}
// IndexID returns the packageIdx referencing id, creating one if id is not yet
// tracked by the receiver.
func (index *PackageIndex) IndexID(id metadata.PackageID) IndexID {
index.mu.Lock()
defer index.mu.Unlock()
if i, ok := index.m[id]; ok {
return i
}
i := IndexID(len(index.ids))
index.m[id] = i
index.ids = append(index.ids, id)
return i
}
// PackageID returns the PackageID for idx.
//
// idx must have been created by this PackageIndex instance.
func (index *PackageIndex) PackageID(idx IndexID) metadata.PackageID {
index.mu.Lock()
defer index.mu.Unlock()
return index.ids[idx]
}
// A PackageSet is a set of metadata.PackageIDs, optimized for inuse memory
// footprint and efficient union operations.
type PackageSet struct {
// PackageSet is a sparse int vector of package indexes from parent.
parent *PackageIndex
sparse map[int]blockType // high bits in key, set of low bits in value
}
type blockType = uint // type of each sparse vector element
const blockSize = bits.UintSize
// NewSet creates a new PackageSet bound to this PackageIndex instance.
//
// PackageSets may only be combined with other PackageSets from the same
// instance.
func (index *PackageIndex) NewSet() *PackageSet {
return &PackageSet{
parent: index,
sparse: make(map[int]blockType),
}
}
// DeclaringPackage returns the ID of the symbol's declaring package.
// The package index must be the one used during decoding.
func (index *PackageIndex) DeclaringPackage(sym Symbol) metadata.PackageID {
return index.PackageID(sym.Package)
}
// Add records a new element in the package set, for the provided package ID.
func (s *PackageSet) AddPackage(id metadata.PackageID) {
s.Add(s.parent.IndexID(id))
}
// Add records a new element in the package set.
// It is the caller's responsibility to ensure that idx was created with the
// same PackageIndex as the PackageSet.
func (s *PackageSet) Add(idx IndexID) {
i := int(idx)
s.sparse[i/blockSize] |= 1 << (i % blockSize)
}
// Union records all elements from other into the receiver, mutating the
// receiver set but not the argument set. The receiver must not be nil, but the
// argument set may be nil.
//
// Precondition: both package sets were created with the same PackageIndex.
func (s *PackageSet) Union(other *PackageSet) {
if other == nil {
return // e.g. unsafe
}
if other.parent != s.parent {
panic("other set is from a different PackageIndex instance")
}
for k, v := range other.sparse {
if v0 := s.sparse[k]; v0 != v {
s.sparse[k] = v0 | v
}
}
}
// Contains reports whether id is contained in the receiver set.
func (s *PackageSet) Contains(id metadata.PackageID) bool {
i := int(s.parent.IndexID(id))
return s.sparse[i/blockSize]&(1<<(i%blockSize)) != 0
}
// Elems calls f for each element of the set in ascending order.
func (s *PackageSet) Elems(f func(IndexID)) {
blockIndexes := make([]int, 0, len(s.sparse))
for k := range s.sparse {
blockIndexes = append(blockIndexes, k)
}
sort.Ints(blockIndexes)
for _, i := range blockIndexes {
v := s.sparse[i]
for b := 0; b < blockSize; b++ {
if (v & (1 << b)) != 0 {
f(IndexID(i*blockSize + b))
}
}
}
}
// String returns a human-readable representation of the set: {A, B, ...}.
func (s *PackageSet) String() string {
var ids []string
s.Elems(func(id IndexID) {
ids = append(ids, string(s.parent.PackageID(id)))
})
return fmt.Sprintf("{%s}", strings.Join(ids, ", "))
}