1// Copyright 2019 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
5package cache
6
7import (
8	"context"
9	"crypto/sha256"
10	"fmt"
11	"go/ast"
12	"go/token"
13	"go/types"
14	"html/template"
15	"io/ioutil"
16	"os"
17	"reflect"
18	"sort"
19	"strconv"
20	"sync"
21	"sync/atomic"
22	"time"
23
24	"golang.org/x/tools/internal/event"
25	"golang.org/x/tools/internal/gocommand"
26	"golang.org/x/tools/internal/lsp/debug/tag"
27	"golang.org/x/tools/internal/lsp/source"
28	"golang.org/x/tools/internal/memoize"
29	"golang.org/x/tools/internal/span"
30)
31
32func New(options func(*source.Options)) *Cache {
33	index := atomic.AddInt64(&cacheIndex, 1)
34	c := &Cache{
35		id:          strconv.FormatInt(index, 10),
36		fset:        token.NewFileSet(),
37		options:     options,
38		fileContent: map[span.URI]*fileHandle{},
39	}
40	return c
41}
42
43type Cache struct {
44	id      string
45	fset    *token.FileSet
46	options func(*source.Options)
47
48	store memoize.Store
49
50	fileMu      sync.Mutex
51	fileContent map[span.URI]*fileHandle
52}
53
54type fileHandle struct {
55	modTime time.Time
56	uri     span.URI
57	bytes   []byte
58	hash    string
59	err     error
60
61	// size is the file length as reported by Stat, for the purpose of
62	// invalidation. Probably we could just use len(bytes), but this is done
63	// defensively in case the definition of file size in the file system
64	// differs.
65	size int64
66}
67
68func (h *fileHandle) Saved() bool {
69	return true
70}
71
72func (c *Cache) GetFile(ctx context.Context, uri span.URI) (source.FileHandle, error) {
73	return c.getFile(ctx, uri)
74}
75
76func (c *Cache) getFile(ctx context.Context, uri span.URI) (*fileHandle, error) {
77	fi, statErr := os.Stat(uri.Filename())
78	if statErr != nil {
79		return &fileHandle{
80			err: statErr,
81			uri: uri,
82		}, nil
83	}
84
85	c.fileMu.Lock()
86	fh, ok := c.fileContent[uri]
87	c.fileMu.Unlock()
88
89	// Check mtime and file size to infer whether the file has changed. This is
90	// an imperfect heuristic. Notably on some real systems (such as WSL) the
91	// filesystem clock resolution can be large -- 1/64s was observed. Therefore
92	// it's quite possible for multiple file modifications to occur within a
93	// single logical 'tick'. This can leave the cache in an incorrect state, but
94	// unfortunately we can't afford to pay the price of reading the actual file
95	// content here. Or to be more precise, reading would be a risky change and
96	// we don't know if we can afford it.
97	//
98	// We check file size in an attempt to reduce the probability of false cache
99	// hits.
100	if ok && fh.modTime.Equal(fi.ModTime()) && fh.size == fi.Size() {
101		return fh, nil
102	}
103
104	fh, err := readFile(ctx, uri, fi)
105	if err != nil {
106		return nil, err
107	}
108	c.fileMu.Lock()
109	c.fileContent[uri] = fh
110	c.fileMu.Unlock()
111	return fh, nil
112}
113
114// ioLimit limits the number of parallel file reads per process.
115var ioLimit = make(chan struct{}, 128)
116
117func readFile(ctx context.Context, uri span.URI, fi os.FileInfo) (*fileHandle, error) {
118	select {
119	case ioLimit <- struct{}{}:
120	case <-ctx.Done():
121		return nil, ctx.Err()
122	}
123	defer func() { <-ioLimit }()
124
125	ctx, done := event.Start(ctx, "cache.readFile", tag.File.Of(uri.Filename()))
126	_ = ctx
127	defer done()
128
129	data, err := ioutil.ReadFile(uri.Filename())
130	if err != nil {
131		return &fileHandle{
132			modTime: fi.ModTime(),
133			size:    fi.Size(),
134			err:     err,
135		}, nil
136	}
137	return &fileHandle{
138		modTime: fi.ModTime(),
139		size:    fi.Size(),
140		uri:     uri,
141		bytes:   data,
142		hash:    hashContents(data),
143	}, nil
144}
145
146func (c *Cache) NewSession(ctx context.Context) *Session {
147	index := atomic.AddInt64(&sessionIndex, 1)
148	options := source.DefaultOptions().Clone()
149	if c.options != nil {
150		c.options(options)
151	}
152	s := &Session{
153		cache:       c,
154		id:          strconv.FormatInt(index, 10),
155		options:     options,
156		overlays:    make(map[span.URI]*overlay),
157		gocmdRunner: &gocommand.Runner{},
158	}
159	event.Log(ctx, "New session", KeyCreateSession.Of(s))
160	return s
161}
162
163func (c *Cache) FileSet() *token.FileSet {
164	return c.fset
165}
166
167func (h *fileHandle) URI() span.URI {
168	return h.uri
169}
170
171func (h *fileHandle) Kind() source.FileKind {
172	return source.DetectLanguage("", h.uri.Filename())
173}
174
175func (h *fileHandle) Hash() string {
176	return h.hash
177}
178
179func (h *fileHandle) FileIdentity() source.FileIdentity {
180	return source.FileIdentity{
181		URI:  h.uri,
182		Hash: h.hash,
183		Kind: h.Kind(),
184	}
185}
186
187func (h *fileHandle) Read() ([]byte, error) {
188	return h.bytes, h.err
189}
190
191func hashContents(contents []byte) string {
192	return fmt.Sprintf("%x", sha256.Sum256(contents))
193}
194
195var cacheIndex, sessionIndex, viewIndex int64
196
197func (c *Cache) ID() string                     { return c.id }
198func (c *Cache) MemStats() map[reflect.Type]int { return c.store.Stats() }
199
200type packageStat struct {
201	id        packageID
202	mode      source.ParseMode
203	file      int64
204	ast       int64
205	types     int64
206	typesInfo int64
207	total     int64
208}
209
210func (c *Cache) PackageStats(withNames bool) template.HTML {
211	var packageStats []packageStat
212	c.store.DebugOnlyIterate(func(k, v interface{}) {
213		switch k.(type) {
214		case packageHandleKey:
215			v := v.(*packageData)
216			if v.pkg == nil {
217				break
218			}
219			var typsCost, typInfoCost int64
220			if v.pkg.types != nil {
221				typsCost = typesCost(v.pkg.types.Scope())
222			}
223			if v.pkg.typesInfo != nil {
224				typInfoCost = typesInfoCost(v.pkg.typesInfo)
225			}
226			stat := packageStat{
227				id:        v.pkg.m.id,
228				mode:      v.pkg.mode,
229				types:     typsCost,
230				typesInfo: typInfoCost,
231			}
232			for _, f := range v.pkg.compiledGoFiles {
233				stat.file += int64(len(f.Src))
234				stat.ast += astCost(f.File)
235			}
236			stat.total = stat.file + stat.ast + stat.types + stat.typesInfo
237			packageStats = append(packageStats, stat)
238		}
239	})
240	var totalCost int64
241	for _, stat := range packageStats {
242		totalCost += stat.total
243	}
244	sort.Slice(packageStats, func(i, j int) bool {
245		return packageStats[i].total > packageStats[j].total
246	})
247	html := "<table><thead><td>Name</td><td>total = file + ast + types + types info</td></thead>\n"
248	human := func(n int64) string {
249		return fmt.Sprintf("%.2f", float64(n)/(1024*1024))
250	}
251	var printedCost int64
252	for _, stat := range packageStats {
253		name := stat.id
254		if !withNames {
255			name = "-"
256		}
257		html += fmt.Sprintf("<tr><td>%v (%v)</td><td>%v = %v + %v + %v + %v</td></tr>\n", name, stat.mode,
258			human(stat.total), human(stat.file), human(stat.ast), human(stat.types), human(stat.typesInfo))
259		printedCost += stat.total
260		if float64(printedCost) > float64(totalCost)*.9 {
261			break
262		}
263	}
264	html += "</table>\n"
265	return template.HTML(html)
266}
267
268func astCost(f *ast.File) int64 {
269	if f == nil {
270		return 0
271	}
272	var count int64
273	ast.Inspect(f, func(_ ast.Node) bool {
274		count += 32 // nodes are pretty small.
275		return true
276	})
277	return count
278}
279
280func typesCost(scope *types.Scope) int64 {
281	cost := 64 + int64(scope.Len())*128 // types.object looks pretty big
282	for i := 0; i < scope.NumChildren(); i++ {
283		cost += typesCost(scope.Child(i))
284	}
285	return cost
286}
287
288func typesInfoCost(info *types.Info) int64 {
289	// Most of these refer to existing objects, with the exception of InitOrder, Selections, and Types.
290	cost := 24*len(info.Defs) +
291		32*len(info.Implicits) +
292		256*len(info.InitOrder) + // these are big, but there aren't many of them.
293		32*len(info.Scopes) +
294		128*len(info.Selections) + // wild guess
295		128*len(info.Types) + // wild guess
296		32*len(info.Uses)
297	return int64(cost)
298}
299