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