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