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