fork of https://github.com/sourcegraph/zoekt
1// Copyright 2016 Google Inc. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package index
16
17import (
18 "context"
19 "fmt"
20 "log"
21 "regexp/syntax"
22 "sort"
23 "strings"
24 "time"
25
26 enry_data "github.com/go-enry/go-enry/v2/data"
27 "github.com/grafana/regexp"
28 "github.com/sourcegraph/zoekt"
29 "github.com/sourcegraph/zoekt/internal/tenant"
30 "github.com/sourcegraph/zoekt/query"
31)
32
33// simplifyMultiRepo takes a query and a predicate. It returns Const(true) if all
34// repository names fulfill the predicate, Const(false) if none of them do, and q
35// otherwise.
36func (d *indexData) simplifyMultiRepo(q query.Q, predicate func(*zoekt.Repository) bool) query.Q {
37 count := 0
38 alive := len(d.repoMetaData)
39 for i := range d.repoMetaData {
40 if d.repoMetaData[i].Tombstone {
41 alive--
42 } else if predicate(&d.repoMetaData[i]) {
43 count++
44 }
45 }
46 if count == alive {
47 return &query.Const{Value: true}
48 }
49 if count > 0 {
50 return q
51 }
52 return &query.Const{Value: false}
53}
54
55func (d *indexData) simplify(in query.Q) query.Q {
56 eval := query.Map(in, func(q query.Q) query.Q {
57 switch r := q.(type) {
58 case *query.Repo:
59 return d.simplifyMultiRepo(q, func(repo *zoekt.Repository) bool {
60 return r.Regexp.MatchString(repo.Name)
61 })
62 case *query.RepoRegexp:
63 return d.simplifyMultiRepo(q, func(repo *zoekt.Repository) bool {
64 return r.Regexp.MatchString(repo.Name)
65 })
66 case *query.BranchesRepos:
67 for i := range d.repoMetaData {
68 for _, br := range r.List {
69 if br.Repos.Contains(d.repoMetaData[i].ID) {
70 return q
71 }
72 }
73 }
74 return &query.Const{Value: false}
75 case *query.RepoSet:
76 return d.simplifyMultiRepo(q, func(repo *zoekt.Repository) bool {
77 return r.Set[repo.Name]
78 })
79 case query.RawConfig:
80 return d.simplifyMultiRepo(q, func(repo *zoekt.Repository) bool { return uint8(r)&encodeRawConfig(repo.RawConfig) == uint8(r) })
81 case *query.RepoIDs:
82 return d.simplifyMultiRepo(q, func(repo *zoekt.Repository) bool {
83 return r.Repos.Contains(repo.ID)
84 })
85 case *query.Language:
86 _, has := d.metaData.LanguageMap[r.Language]
87 if !has && d.metaData.IndexFeatureVersion < 12 {
88 // For index files that haven't been re-indexed by go-enry,
89 // fall back to file-based matching and continue even if this
90 // repo doesn't have the specific language present.
91 extsForLang := enry_data.ExtensionsByLanguage[r.Language]
92 if extsForLang != nil {
93 extFrags := make([]string, 0, len(extsForLang))
94 for _, ext := range extsForLang {
95 extFrags = append(extFrags, regexp.QuoteMeta(ext))
96 }
97 if len(extFrags) > 0 {
98 pattern := fmt.Sprintf("(?i)(%s)$", strings.Join(extFrags, "|"))
99 // inlined copy of query.regexpQuery
100 re, err := syntax.Parse(pattern, syntax.Perl)
101 if err != nil {
102 return &query.Const{Value: false}
103 }
104 if re.Op == syntax.OpLiteral {
105 return &query.Substring{
106 Pattern: string(re.Rune),
107 FileName: true,
108 }
109 }
110 return &query.Regexp{
111 Regexp: re,
112 FileName: true,
113 }
114 }
115 }
116 }
117 if !has {
118 return &query.Const{Value: false}
119 }
120 }
121 return q
122 })
123 return query.Simplify(eval)
124}
125
126func (d *indexData) Search(ctx context.Context, q query.Q, opts *zoekt.SearchOptions) (sr *zoekt.SearchResult, err error) {
127 timer := newTimer()
128
129 copyOpts := *opts
130 opts = ©Opts
131 opts.SetDefaults()
132
133 var res zoekt.SearchResult
134 if len(d.fileNameIndex) == 0 {
135 return &res, nil
136 }
137
138 select {
139 case <-ctx.Done():
140 res.Stats.ShardsSkipped++
141 return &res, nil
142 default:
143 }
144
145 q = d.simplify(q)
146 if c, ok := q.(*query.Const); ok && !c.Value {
147 return &res, nil
148 }
149
150 if opts.EstimateDocCount {
151 res.Stats.ShardFilesConsidered = len(d.fileBranchMasks)
152 return &res, nil
153 }
154
155 q = query.Map(q, query.ExpandFileContent)
156
157 mt, err := d.newMatchTree(q, matchTreeOpt{})
158 if err != nil {
159 return nil, err
160 }
161
162 // Capture the costs of construction before pruning
163 updateMatchTreeStats(mt, &res.Stats)
164
165 mt, err = pruneMatchTree(mt)
166 if err != nil {
167 return nil, err
168 }
169 res.Stats.MatchTreeConstruction = timer.Elapsed()
170 if mt == nil {
171 res.Stats.ShardsSkippedFilter++
172 return &res, nil
173 }
174
175 res.Stats.ShardsScanned++
176
177 cp := &contentProvider{
178 id: d,
179 stats: &res.Stats,
180 }
181
182 // Track the number of documents found in a repository for
183 // ShardRepoMaxMatchCount
184 var (
185 lastRepoID uint16
186 repoMatchCount int
187 )
188
189 docCount := uint32(len(d.fileBranchMasks))
190 lastDoc := int(-1)
191
192 // document frequency per term
193 df := make(termDocumentFrequency)
194
195 // term frequency per file index
196 var tfs []termFrequency
197
198nextFileMatch:
199 for {
200 canceled := false
201 select {
202 case <-ctx.Done():
203 canceled = true
204 default:
205 }
206
207 nextDoc := mt.nextDoc()
208 if int(nextDoc) <= lastDoc {
209 nextDoc = uint32(lastDoc + 1)
210 }
211
212 for ; nextDoc < docCount; nextDoc++ {
213 repoID := d.repos[nextDoc]
214 repoMetadata := &d.repoMetaData[repoID]
215
216 // Skip tombstoned repositories
217 if repoMetadata.Tombstone {
218 continue
219 }
220
221 // 🚨 SECURITY: Skip documents that don't belong to the tenant. This check is
222 // necessary to prevent leaking data across tenants.
223 if !tenant.HasAccess(ctx, repoMetadata.TenantID) {
224 continue
225 }
226
227 // Skip documents that are tombstoned
228 if len(repoMetadata.FileTombstones) > 0 {
229 if _, tombstoned := repoMetadata.FileTombstones[string(d.fileName(nextDoc))]; tombstoned {
230 continue
231 }
232 }
233
234 // Skip documents over ShardRepoMaxMatchCount if specified.
235 if opts.ShardRepoMaxMatchCount > 0 {
236 if repoMatchCount >= opts.ShardRepoMaxMatchCount && repoID == lastRepoID {
237 res.Stats.FilesSkipped++
238 continue
239 }
240 }
241
242 break
243 }
244
245 if nextDoc >= docCount {
246 break
247 }
248
249 lastDoc = int(nextDoc)
250
251 // We track lastRepoID for ShardRepoMaxMatchCount
252 if lastRepoID != d.repos[nextDoc] {
253 lastRepoID = d.repos[nextDoc]
254 repoMatchCount = 0
255 }
256
257 if canceled || (res.Stats.MatchCount >= opts.ShardMaxMatchCount && opts.ShardMaxMatchCount > 0) {
258 res.Stats.FilesSkipped += int(docCount - nextDoc)
259 break
260 }
261
262 res.Stats.FilesConsidered++
263 mt.prepare(nextDoc)
264
265 cp.setDocument(nextDoc)
266
267 known := make(map[matchTree]bool)
268 md := d.repoMetaData[d.repos[nextDoc]]
269
270 for cost := costMin; cost <= costMax; cost++ {
271 switch evalMatchTree(cp, cost, known, mt) {
272 case matchesRequiresHigherCost:
273 if cost == costMax {
274 log.Panicf("did not decide. Repo %s, doc %d, known %v",
275 md.Name, nextDoc, known)
276 }
277 case matchesFound:
278 // could short-circuit now, but we want to run higher costs to
279 // potentially find higher ranked matches.
280 case matchesNone:
281 continue nextFileMatch
282 }
283 }
284
285 fileMatch := zoekt.FileMatch{
286 Repository: md.Name,
287 RepositoryID: md.ID,
288 RepositoryPriority: md.GetPriority(),
289 FileName: string(d.fileName(nextDoc)),
290 Checksum: d.getChecksum(nextDoc),
291 Language: d.languageMap[d.getLanguage(nextDoc)],
292 }
293
294 if s := d.subRepos[nextDoc]; s > 0 {
295 if s >= uint32(len(d.subRepoPaths[d.repos[nextDoc]])) {
296 log.Panicf("corrupt index: subrepo %d beyond %v", s, d.subRepoPaths)
297 }
298 path := d.subRepoPaths[d.repos[nextDoc]][s]
299 fileMatch.SubRepositoryPath = path
300 sr := md.SubRepoMap[path]
301 fileMatch.SubRepositoryName = sr.Name
302 if idx := d.branchIndex(nextDoc); idx >= 0 {
303 fileMatch.Version = sr.Branches[idx].Version
304 }
305 } else {
306 idx := d.branchIndex(nextDoc)
307 if idx >= 0 {
308 fileMatch.Version = md.Branches[idx].Version
309 }
310 }
311
312 // Important invariant for performance: finalCands is sorted by offset and
313 // non-overlapping. gatherMatches respects this invariant and all later
314 // transformations respect this.
315 finalCands := d.gatherMatches(nextDoc, mt, known)
316
317 if opts.ChunkMatches {
318 fileMatch.ChunkMatches = cp.fillChunkMatches(finalCands, opts.NumContextLines, fileMatch.Language, opts)
319 } else {
320 fileMatch.LineMatches = cp.fillMatches(finalCands, opts.NumContextLines, fileMatch.Language, opts)
321 }
322
323 var tf map[string]int
324 if opts.UseBM25Scoring {
325 // For BM25 scoring, the calculation of the score is split in two parts. Here we
326 // calculate the term frequencies for the current document and update the
327 // document frequencies. Since we don't store document frequencies in the index,
328 // we have to defer the calculation of the final BM25 score to after the whole
329 // shard has been processed.
330 tf = cp.calculateTermFrequency(finalCands, df)
331 } else {
332 // Use the standard, non-experimental scoring method by default
333 d.scoreFile(&fileMatch, nextDoc, mt, known, opts)
334 }
335
336 fileMatch.Branches = d.gatherBranches(nextDoc, mt, known)
337 sortMatchesByScore(fileMatch.LineMatches)
338 sortChunkMatchesByScore(fileMatch.ChunkMatches)
339 if opts.Whole {
340 fileMatch.Content = cp.data(false)
341 }
342
343 matchedChunkRanges := 0
344 for _, cm := range fileMatch.ChunkMatches {
345 matchedChunkRanges += len(cm.Ranges)
346 }
347
348 repoMatchCount += len(fileMatch.LineMatches)
349 repoMatchCount += matchedChunkRanges
350
351 if opts.UseBM25Scoring {
352 // Invariant: tfs[i] belongs to res.Files[i]
353 tfs = append(tfs, termFrequency{
354 doc: nextDoc,
355 tf: tf,
356 })
357 }
358 res.Files = append(res.Files, fileMatch)
359
360 res.Stats.MatchCount += len(fileMatch.LineMatches)
361 res.Stats.MatchCount += matchedChunkRanges
362 res.Stats.FileCount++
363 }
364
365 // Calculate BM25 score for all file matches in the shard. We assume that we
366 // have seen all documents containing any of the terms in the query so that df
367 // correctly reflects the document frequencies. This is true, for example, if
368 // all terms in the query are ORed together.
369 if opts.UseBM25Scoring {
370 d.scoreFilesUsingBM25(res.Files, tfs, df, opts)
371 }
372
373 for _, md := range d.repoMetaData {
374 r := md
375 addRepo(&res, &r)
376 for _, v := range r.SubRepoMap {
377 addRepo(&res, v)
378 }
379 }
380
381 // Update stats based on work done during document search.
382 updateMatchTreeStats(mt, &res.Stats)
383
384 res.Stats.MatchTreeSearch = timer.Elapsed()
385
386 return &res, nil
387}
388
389func addRepo(res *zoekt.SearchResult, repo *zoekt.Repository) {
390 if res.RepoURLs == nil {
391 res.RepoURLs = map[string]string{}
392 }
393 res.RepoURLs[repo.Name] = repo.FileURLTemplate
394
395 if res.LineFragments == nil {
396 res.LineFragments = map[string]string{}
397 }
398 res.LineFragments[repo.Name] = repo.LineFragmentTemplate
399}
400
401// Gather matches from this document. The matches are returned in document
402// order and are non-overlapping. All filename and content matches are
403// returned, with filename matches first.
404//
405// If `merge` is set, overlapping and adjacent matches will be merged
406// into a single index. Otherwise, overlapping matches will be removed,
407// but adjacent matches will remain.
408func (d *indexData) gatherMatches(nextDoc uint32, mt matchTree, known map[matchTree]bool) []*candidateMatch {
409 var cands []*candidateMatch
410 visitMatches(mt, known, 1, func(mt matchTree, scoreWeight float64) {
411 if smt, ok := mt.(*substrMatchTree); ok {
412 cands = append(cands, setScoreWeight(scoreWeight, smt.current)...)
413 }
414 if rmt, ok := mt.(*regexpMatchTree); ok {
415 cands = append(cands, setScoreWeight(scoreWeight, rmt.found)...)
416 }
417 if rmt, ok := mt.(*wordMatchTree); ok {
418 cands = append(cands, setScoreWeight(scoreWeight, rmt.found)...)
419 }
420 if smt, ok := mt.(*symbolRegexpMatchTree); ok {
421 cands = append(cands, setScoreWeight(scoreWeight, smt.found)...)
422 }
423 })
424
425 // If we found no candidate matches at all, assume there must have been a match on filename.
426 if len(cands) == 0 {
427 nm := d.fileName(nextDoc)
428 return []*candidateMatch{{
429 caseSensitive: false,
430 fileName: true,
431 substrBytes: nm,
432 substrLowered: nm,
433 file: nextDoc,
434 runeOffset: 0,
435 byteOffset: 0,
436 byteMatchSz: uint32(len(nm)),
437 }}
438 }
439
440 // Remove overlapping candidates. This guarantees that the matches
441 // are non-overlapping, but also preserves expected match counts.
442 sort.Sort((sortByOffsetSlice)(cands))
443 res := cands[:0]
444 for i, c := range cands {
445 if i == 0 {
446 res = append(res, c)
447 continue
448 }
449
450 last := res[len(res)-1]
451
452 // Never compare filename and content matches
453 if last.fileName != c.fileName {
454 res = append(res, c)
455 continue
456 }
457
458 // Only add the match if its range doesn't overlap
459 lastEnd := last.byteOffset + last.byteMatchSz
460 if lastEnd <= c.byteOffset {
461 res = append(res, c)
462 continue
463 }
464 }
465 return res
466}
467
468type sortByOffsetSlice []*candidateMatch
469
470func (m sortByOffsetSlice) Len() int { return len(m) }
471func (m sortByOffsetSlice) Swap(i, j int) { m[i], m[j] = m[j], m[i] }
472func (m sortByOffsetSlice) Less(i, j int) bool {
473 // Sort all filename matches to the start
474 if m[i].fileName != m[j].fileName {
475 return m[i].fileName
476 }
477
478 if m[i].byteOffset == m[j].byteOffset { // tie break if same offset
479 // Prefer longer candidates if starting at same position
480 return m[i].byteMatchSz > m[j].byteMatchSz
481 }
482 return m[i].byteOffset < m[j].byteOffset
483}
484
485// setScoreWeight is a helper used by gatherMatches to set the weight based on
486// the score weight of the matchTree.
487func setScoreWeight(scoreWeight float64, cm []*candidateMatch) []*candidateMatch {
488 for _, m := range cm {
489 m.scoreWeight = scoreWeight
490 }
491 return cm
492}
493
494func (d *indexData) branchIndex(docID uint32) int {
495 mask := d.fileBranchMasks[docID]
496 idx := 0
497 for mask != 0 {
498 if mask&0x1 != 0 {
499 return idx
500 }
501 idx++
502 mask >>= 1
503 }
504 return -1
505}
506
507// gatherBranches returns a list of branch names taking into account any branch
508// filters in the query. If the query contains a branch filter, it returns all
509// branches containing the docID and matching the branch filter. Otherwise, it
510// returns all branches containing docID.
511func (d *indexData) gatherBranches(docID uint32, mt matchTree, known map[matchTree]bool) []string {
512 var mask uint64
513 visitMatchAtoms(mt, known, func(mt matchTree) {
514 bq, ok := mt.(*branchQueryMatchTree)
515 if !ok {
516 return
517 }
518
519 mask = mask | bq.branchMask()
520 })
521
522 if mask == 0 {
523 mask = d.fileBranchMasks[docID]
524 }
525
526 var branches []string
527 id := uint32(1)
528 branchNames := d.branchNames[d.repos[docID]]
529 for mask != 0 {
530 if mask&0x1 != 0 {
531 branches = append(branches, branchNames[uint(id)])
532 }
533 id <<= 1
534 mask >>= 1
535 }
536
537 return branches
538}
539
540func (d *indexData) List(ctx context.Context, q query.Q, opts *zoekt.ListOptions) (rl *zoekt.RepoList, err error) {
541 var include func(rle *zoekt.RepoListEntry) bool
542
543 q = d.simplify(q)
544 if c, ok := q.(*query.Const); ok {
545 if !c.Value {
546 return &zoekt.RepoList{}, nil
547 }
548 include = func(rle *zoekt.RepoListEntry) bool {
549 return true
550 }
551 } else {
552 sr, err := d.Search(ctx, q, &zoekt.SearchOptions{
553 ShardRepoMaxMatchCount: 1,
554 })
555 if err != nil {
556 return nil, err
557 }
558
559 foundRepos := make(map[string]struct{}, len(sr.Files))
560 for _, file := range sr.Files {
561 foundRepos[file.Repository] = struct{}{}
562 }
563
564 include = func(rle *zoekt.RepoListEntry) bool {
565 _, ok := foundRepos[rle.Repository.Name]
566 return ok
567 }
568 }
569
570 var l zoekt.RepoList
571
572 field, err := opts.GetField()
573 if err != nil {
574 return nil, err
575 }
576 switch field {
577 case zoekt.RepoListFieldRepos:
578 l.Repos = make([]*zoekt.RepoListEntry, 0, len(d.repoListEntry))
579 case zoekt.RepoListFieldReposMap:
580 l.ReposMap = make(zoekt.ReposMap, len(d.repoListEntry))
581 }
582
583 for i := range d.repoListEntry {
584 if d.repoMetaData[i].Tombstone {
585 continue
586 }
587 // 🚨 SECURITY: Skip documents that don't belong to the tenant. This check is
588 // necessary to prevent leaking data across tenants.
589 if !tenant.HasAccess(ctx, d.repoMetaData[i].TenantID) {
590 continue
591 }
592 rle := &d.repoListEntry[i]
593 if !include(rle) {
594 continue
595 }
596
597 l.Stats.Add(&rle.Stats)
598
599 // Backwards compat for when ID is missing
600 if rle.Repository.ID == 0 {
601 l.Repos = append(l.Repos, rle)
602 continue
603 }
604
605 switch field {
606 case zoekt.RepoListFieldRepos:
607 l.Repos = append(l.Repos, rle)
608 case zoekt.RepoListFieldReposMap:
609 l.ReposMap[rle.Repository.ID] = zoekt.MinimalRepoListEntry{
610 HasSymbols: rle.Repository.HasSymbols,
611 Branches: rle.Repository.Branches,
612 IndexTimeUnix: rle.IndexMetadata.IndexTime.Unix(),
613 }
614 }
615
616 }
617
618 // Only one of these fields is populated and in all cases the size of that
619 // field is the number of Repos in this shard.
620 l.Stats.Repos = len(l.Repos) + len(l.ReposMap)
621
622 return &l, nil
623}
624
625// regexpToMatchTreeRecursive converts a regular expression to a matchTree mt. If
626// mt is equivalent to the input r, isEqual = true and the matchTree can be used
627// in place of the regex r. If singleLine = true, then the matchTree and all
628// its children only match terms on the same line. singleLine is used during
629// recursion to decide whether to return an andLineMatchTree (singleLine = true)
630// or a andMatchTree (singleLine = false).
631func (d *indexData) regexpToMatchTreeRecursive(r *syntax.Regexp, minTextSize int, fileName bool, caseSensitive bool) (mt matchTree, isEqual bool, singleLine bool, err error) {
632 // TODO - we could perhaps transform Begin/EndText in '\n'?
633 // TODO - we could perhaps transform CharClass in (OrQuery )
634 // if there are just a few runes, and part of a OpConcat?
635 switch r.Op {
636 case syntax.OpLiteral:
637 s := string(r.Rune)
638 if len(s) >= minTextSize {
639 ignoreCase := syntax.FoldCase == (r.Flags & syntax.FoldCase)
640 mt, err := d.newSubstringMatchTree(&query.Substring{Pattern: s, FileName: fileName, CaseSensitive: !ignoreCase && caseSensitive})
641 return mt, true, !strings.Contains(s, "\n"), err
642 }
643 case syntax.OpCapture:
644 return d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
645
646 case syntax.OpPlus:
647 return d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
648
649 case syntax.OpRepeat:
650 if r.Min == 1 {
651 return d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
652 } else if r.Min > 1 {
653 // (x){2,} can't be expressed precisely by the matchTree
654 mt, _, singleLine, err := d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
655 return mt, false, singleLine, err
656 }
657 case syntax.OpConcat, syntax.OpAlternate:
658 var qs []matchTree
659 isEq := true
660 singleLine = true
661 for _, sr := range r.Sub {
662 if sq, subIsEq, subSingleLine, err := d.regexpToMatchTreeRecursive(sr, minTextSize, fileName, caseSensitive); sq != nil {
663 if err != nil {
664 return nil, false, false, err
665 }
666 isEq = isEq && subIsEq
667 singleLine = singleLine && subSingleLine
668 qs = append(qs, sq)
669 }
670 }
671 if r.Op == syntax.OpConcat {
672 if len(qs) > 1 {
673 isEq = false
674 }
675 newQs := make([]matchTree, 0, len(qs))
676 for _, q := range qs {
677 if _, ok := q.(*bruteForceMatchTree); ok {
678 continue
679 }
680 newQs = append(newQs, q)
681 }
682 if len(newQs) == 1 {
683 return newQs[0], isEq, singleLine, nil
684 }
685 if len(newQs) == 0 {
686 return &bruteForceMatchTree{}, isEq, singleLine, nil
687 }
688 if singleLine {
689 return &andLineMatchTree{andMatchTree{children: newQs}}, isEq, singleLine, nil
690 }
691 return &andMatchTree{newQs}, isEq, singleLine, nil
692 }
693 for _, q := range qs {
694 if _, ok := q.(*bruteForceMatchTree); ok {
695 return q, isEq, false, nil
696 }
697 }
698 if len(qs) == 0 {
699 return &noMatchTree{Why: "const"}, isEq, false, nil
700 }
701 return &orMatchTree{qs}, isEq, false, nil
702 case syntax.OpStar:
703 if r.Sub[0].Op == syntax.OpAnyCharNotNL {
704 return &bruteForceMatchTree{}, false, true, nil
705 }
706 }
707 return &bruteForceMatchTree{}, false, false, nil
708}
709
710type timer struct {
711 last time.Time
712}
713
714func newTimer() *timer {
715 return &timer{
716 last: time.Now(),
717 }
718}
719
720func (t *timer) Elapsed() time.Duration {
721 now := time.Now()
722 d := now.Sub(t.last)
723 t.last = now
724 return d
725}