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