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