| // 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/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, ", ")) |
| } |