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 shouldMergeMatches := !opts.ChunkMatches
327 finalCands := d.gatherMatches(nextDoc, mt, known, shouldMergeMatches)
328
329 if opts.ChunkMatches {
330 fileMatch.ChunkMatches = cp.fillChunkMatches(finalCands, opts.NumContextLines, fileMatch.Language, opts.DebugScore)
331 } else {
332 fileMatch.LineMatches = cp.fillMatches(finalCands, opts.NumContextLines, fileMatch.Language, opts.DebugScore)
333 }
334
335 var tf map[string]int
336 if opts.UseBM25Scoring {
337 // For BM25 scoring, the calculation of the score is split in two parts. Here we
338 // calculate the term frequencies for the current document and update the
339 // document frequencies. Since we don't store document frequencies in the index,
340 // we have to defer the calculation of the final BM25 score to after the whole
341 // shard has been processed.
342 tf = calculateTermFrequency(finalCands, df)
343 } else {
344 // Use the standard, non-experimental scoring method by default
345 d.scoreFile(&fileMatch, nextDoc, mt, known, opts)
346 }
347
348 fileMatch.Branches = d.gatherBranches(nextDoc, mt, known)
349 sortMatchesByScore(fileMatch.LineMatches)
350 sortChunkMatchesByScore(fileMatch.ChunkMatches)
351 if opts.Whole {
352 fileMatch.Content = cp.data(false)
353 }
354
355 matchedChunkRanges := 0
356 for _, cm := range fileMatch.ChunkMatches {
357 matchedChunkRanges += len(cm.Ranges)
358 }
359
360 repoMatchCount += len(fileMatch.LineMatches)
361 repoMatchCount += matchedChunkRanges
362
363 if opts.UseBM25Scoring {
364 // Invariant: tfs[i] belongs to res.Files[i]
365 tfs = append(tfs, termFrequency{
366 doc: nextDoc,
367 tf: tf,
368 })
369 }
370 res.Files = append(res.Files, fileMatch)
371
372 res.Stats.MatchCount += len(fileMatch.LineMatches)
373 res.Stats.MatchCount += matchedChunkRanges
374 res.Stats.FileCount++
375 }
376
377 // Calculate BM25 score for all file matches in the shard. We assume that we
378 // have seen all documents containing any of the terms in the query so that df
379 // correctly reflects the document frequencies. This is true, for example, if
380 // all terms in the query are ORed together.
381 if opts.UseBM25Scoring {
382 d.scoreFilesUsingBM25(res.Files, tfs, df, opts)
383 }
384
385 for _, md := range d.repoMetaData {
386 r := md
387 addRepo(&res, &r)
388 for _, v := range r.SubRepoMap {
389 addRepo(&res, v)
390 }
391 }
392
393 // Update stats based on work done during document search.
394 updateMatchTreeStats(mt, &res.Stats)
395
396 res.Stats.MatchTreeSearch = timer.Elapsed()
397
398 return &res, nil
399}
400
401func addRepo(res *SearchResult, repo *Repository) {
402 if res.RepoURLs == nil {
403 res.RepoURLs = map[string]string{}
404 }
405 res.RepoURLs[repo.Name] = repo.FileURLTemplate
406
407 if res.LineFragments == nil {
408 res.LineFragments = map[string]string{}
409 }
410 res.LineFragments[repo.Name] = repo.LineFragmentTemplate
411}
412
413// Gather matches from this document. The matches are returned in document
414// order and are non-overlapping. All filename and content matches are
415// returned, with filename matches first.
416//
417// If `merge` is set, overlapping and adjacent matches will be merged
418// into a single match. Otherwise, overlapping matches will be removed,
419// but adjacent matches will remain.
420func (d *indexData) gatherMatches(nextDoc uint32, mt matchTree, known map[matchTree]bool, merge bool) []*candidateMatch {
421 var cands []*candidateMatch
422 visitMatches(mt, known, 1, func(mt matchTree, scoreWeight float64) {
423 if smt, ok := mt.(*substrMatchTree); ok {
424 cands = append(cands, setScoreWeight(scoreWeight, smt.current)...)
425 }
426 if rmt, ok := mt.(*regexpMatchTree); ok {
427 cands = append(cands, setScoreWeight(scoreWeight, rmt.found)...)
428 }
429 if rmt, ok := mt.(*wordMatchTree); ok {
430 cands = append(cands, setScoreWeight(scoreWeight, rmt.found)...)
431 }
432 if smt, ok := mt.(*symbolRegexpMatchTree); ok {
433 cands = append(cands, setScoreWeight(scoreWeight, smt.found)...)
434 }
435 })
436
437 // If we found no candidate matches at all, assume there must have been a match on filename.
438 if len(cands) == 0 {
439 nm := d.fileName(nextDoc)
440 return []*candidateMatch{{
441 caseSensitive: false,
442 fileName: true,
443 substrBytes: nm,
444 substrLowered: nm,
445 file: nextDoc,
446 runeOffset: 0,
447 byteOffset: 0,
448 byteMatchSz: uint32(len(nm)),
449 }}
450 }
451
452 sort.Sort((sortByOffsetSlice)(cands))
453 res := cands[:0]
454 mergeRun := 1
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 if merge {
470 // Merge adjacent candidates. This guarantees that the matches
471 // are non-overlapping.
472 lastEnd := last.byteOffset + last.byteMatchSz
473 end := c.byteOffset + c.byteMatchSz
474 if lastEnd >= c.byteOffset {
475 mergeRun++
476 // Average out the score across the merged candidates. Only do it if
477 // we are boosting to avoid floating point funkiness in the normal
478 // case.
479 if !(epsilonEqualsOne(last.scoreWeight) && epsilonEqualsOne(c.scoreWeight)) {
480 last.scoreWeight = ((last.scoreWeight * float64(mergeRun-1)) + c.scoreWeight) / float64(mergeRun)
481 }
482
483 // latest candidate goes further, update our end
484 if end > lastEnd {
485 last.byteMatchSz = end - last.byteOffset
486 }
487
488 continue
489 } else {
490 mergeRun = 1
491 }
492 } else {
493 // Remove overlapping candidates. This guarantees that the matches
494 // are non-overlapping, but also preserves expected match counts.
495 lastEnd := last.byteOffset + last.byteMatchSz
496 if lastEnd > c.byteOffset {
497 continue
498 }
499 }
500
501 res = append(res, c)
502 }
503 return res
504}
505
506type sortByOffsetSlice []*candidateMatch
507
508func (m sortByOffsetSlice) Len() int { return len(m) }
509func (m sortByOffsetSlice) Swap(i, j int) { m[i], m[j] = m[j], m[i] }
510func (m sortByOffsetSlice) Less(i, j int) bool {
511 // Sort all filename matches to the start
512 if m[i].fileName != m[j].fileName {
513 return m[i].fileName
514 }
515
516 if m[i].byteOffset == m[j].byteOffset { // tie break if same offset
517 // Prefer longer candidates if starting at same position
518 return m[i].byteMatchSz > m[j].byteMatchSz
519 }
520 return m[i].byteOffset < m[j].byteOffset
521}
522
523// setScoreWeight is a helper used by gatherMatches to set the weight based on
524// the score weight of the matchTree.
525func setScoreWeight(scoreWeight float64, cm []*candidateMatch) []*candidateMatch {
526 for _, m := range cm {
527 m.scoreWeight = scoreWeight
528 }
529 return cm
530}
531
532func (d *indexData) branchIndex(docID uint32) int {
533 mask := d.fileBranchMasks[docID]
534 idx := 0
535 for mask != 0 {
536 if mask&0x1 != 0 {
537 return idx
538 }
539 idx++
540 mask >>= 1
541 }
542 return -1
543}
544
545// gatherBranches returns a list of branch names taking into account any branch
546// filters in the query. If the query contains a branch filter, it returns all
547// branches containing the docID and matching the branch filter. Otherwise, it
548// returns all branches containing docID.
549func (d *indexData) gatherBranches(docID uint32, mt matchTree, known map[matchTree]bool) []string {
550 var mask uint64
551 visitMatchAtoms(mt, known, func(mt matchTree) {
552 bq, ok := mt.(*branchQueryMatchTree)
553 if !ok {
554 return
555 }
556
557 mask = mask | bq.branchMask()
558 })
559
560 if mask == 0 {
561 mask = d.fileBranchMasks[docID]
562 }
563
564 var branches []string
565 id := uint32(1)
566 branchNames := d.branchNames[d.repos[docID]]
567 for mask != 0 {
568 if mask&0x1 != 0 {
569 branches = append(branches, branchNames[uint(id)])
570 }
571 id <<= 1
572 mask >>= 1
573 }
574
575 return branches
576}
577
578func (d *indexData) List(ctx context.Context, q query.Q, opts *ListOptions) (rl *RepoList, err error) {
579 var include func(rle *RepoListEntry) bool
580
581 q = d.simplify(q)
582 if c, ok := q.(*query.Const); ok {
583 if !c.Value {
584 return &RepoList{}, nil
585 }
586 include = func(rle *RepoListEntry) bool {
587 return true
588 }
589 } else {
590 sr, err := d.Search(ctx, q, &SearchOptions{
591 ShardRepoMaxMatchCount: 1,
592 })
593 if err != nil {
594 return nil, err
595 }
596
597 foundRepos := make(map[string]struct{}, len(sr.Files))
598 for _, file := range sr.Files {
599 foundRepos[file.Repository] = struct{}{}
600 }
601
602 include = func(rle *RepoListEntry) bool {
603 _, ok := foundRepos[rle.Repository.Name]
604 return ok
605 }
606 }
607
608 var l RepoList
609
610 field, err := opts.GetField()
611 if err != nil {
612 return nil, err
613 }
614 switch field {
615 case RepoListFieldRepos:
616 l.Repos = make([]*RepoListEntry, 0, len(d.repoListEntry))
617 case RepoListFieldReposMap:
618 l.ReposMap = make(ReposMap, len(d.repoListEntry))
619 }
620
621 for i := range d.repoListEntry {
622 if d.repoMetaData[i].Tombstone {
623 continue
624 }
625 // 🚨 SECURITY: Skip documents that don't belong to the tenant. This check is
626 // necessary to prevent leaking data across tenants.
627 if !tenant.HasAccess(ctx, d.repoMetaData[i].TenantID) {
628 continue
629 }
630 rle := &d.repoListEntry[i]
631 if !include(rle) {
632 continue
633 }
634
635 l.Stats.Add(&rle.Stats)
636
637 // Backwards compat for when ID is missing
638 if rle.Repository.ID == 0 {
639 l.Repos = append(l.Repos, rle)
640 continue
641 }
642
643 switch field {
644 case RepoListFieldRepos:
645 l.Repos = append(l.Repos, rle)
646 case RepoListFieldReposMap:
647 l.ReposMap[rle.Repository.ID] = MinimalRepoListEntry{
648 HasSymbols: rle.Repository.HasSymbols,
649 Branches: rle.Repository.Branches,
650 IndexTimeUnix: rle.IndexMetadata.IndexTime.Unix(),
651 }
652 }
653
654 }
655
656 // Only one of these fields is populated and in all cases the size of that
657 // field is the number of Repos in this shard.
658 l.Stats.Repos = len(l.Repos) + len(l.ReposMap)
659
660 return &l, nil
661}
662
663// regexpToMatchTreeRecursive converts a regular expression to a matchTree mt. If
664// mt is equivalent to the input r, isEqual = true and the matchTree can be used
665// in place of the regex r. If singleLine = true, then the matchTree and all
666// its children only match terms on the same line. singleLine is used during
667// recursion to decide whether to return an andLineMatchTree (singleLine = true)
668// or a andMatchTree (singleLine = false).
669func (d *indexData) regexpToMatchTreeRecursive(r *syntax.Regexp, minTextSize int, fileName bool, caseSensitive bool) (mt matchTree, isEqual bool, singleLine bool, err error) {
670 // TODO - we could perhaps transform Begin/EndText in '\n'?
671 // TODO - we could perhaps transform CharClass in (OrQuery )
672 // if there are just a few runes, and part of a OpConcat?
673 switch r.Op {
674 case syntax.OpLiteral:
675 s := string(r.Rune)
676 if len(s) >= minTextSize {
677 ignoreCase := syntax.FoldCase == (r.Flags & syntax.FoldCase)
678 mt, err := d.newSubstringMatchTree(&query.Substring{Pattern: s, FileName: fileName, CaseSensitive: !ignoreCase && caseSensitive})
679 return mt, true, !strings.Contains(s, "\n"), err
680 }
681 case syntax.OpCapture:
682 return d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
683
684 case syntax.OpPlus:
685 return d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
686
687 case syntax.OpRepeat:
688 if r.Min == 1 {
689 return d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
690 } else if r.Min > 1 {
691 // (x){2,} can't be expressed precisely by the matchTree
692 mt, _, singleLine, err := d.regexpToMatchTreeRecursive(r.Sub[0], minTextSize, fileName, caseSensitive)
693 return mt, false, singleLine, err
694 }
695 case syntax.OpConcat, syntax.OpAlternate:
696 var qs []matchTree
697 isEq := true
698 singleLine = true
699 for _, sr := range r.Sub {
700 if sq, subIsEq, subSingleLine, err := d.regexpToMatchTreeRecursive(sr, minTextSize, fileName, caseSensitive); sq != nil {
701 if err != nil {
702 return nil, false, false, err
703 }
704 isEq = isEq && subIsEq
705 singleLine = singleLine && subSingleLine
706 qs = append(qs, sq)
707 }
708 }
709 if r.Op == syntax.OpConcat {
710 if len(qs) > 1 {
711 isEq = false
712 }
713 newQs := make([]matchTree, 0, len(qs))
714 for _, q := range qs {
715 if _, ok := q.(*bruteForceMatchTree); ok {
716 continue
717 }
718 newQs = append(newQs, q)
719 }
720 if len(newQs) == 1 {
721 return newQs[0], isEq, singleLine, nil
722 }
723 if len(newQs) == 0 {
724 return &bruteForceMatchTree{}, isEq, singleLine, nil
725 }
726 if singleLine {
727 return &andLineMatchTree{andMatchTree{children: newQs}}, isEq, singleLine, nil
728 }
729 return &andMatchTree{newQs}, isEq, singleLine, nil
730 }
731 for _, q := range qs {
732 if _, ok := q.(*bruteForceMatchTree); ok {
733 return q, isEq, false, nil
734 }
735 }
736 if len(qs) == 0 {
737 return &noMatchTree{Why: "const"}, isEq, false, nil
738 }
739 return &orMatchTree{qs}, isEq, false, nil
740 case syntax.OpStar:
741 if r.Sub[0].Op == syntax.OpAnyCharNotNL {
742 return &bruteForceMatchTree{}, false, true, nil
743 }
744 }
745 return &bruteForceMatchTree{}, false, false, nil
746}
747
748type timer struct {
749 last time.Time
750}
751
752func newTimer() *timer {
753 return &timer{
754 last: time.Now(),
755 }
756}
757
758func (t *timer) Elapsed() time.Duration {
759 now := time.Now()
760 d := now.Sub(t.last)
761 t.last = now
762 return d
763}