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 "encoding/binary"
19 "encoding/json"
20 "fmt"
21 "hash/crc64"
22 "log"
23 "os"
24 "sort"
25
26 "github.com/rs/xid"
27)
28
29// IndexFile is a file suitable for concurrent read access. For performance
30// reasons, it allows a mmap'd implementation.
31type IndexFile interface {
32 Read(off uint32, sz uint32) ([]byte, error)
33 Size() (uint32, error)
34 Close()
35 Name() string
36}
37
38// reader is a stateful file
39type reader struct {
40 r IndexFile
41 off uint32
42}
43
44func (r *reader) seek(off uint32) {
45 r.off = off
46}
47
48func (r *reader) U32() (uint32, error) {
49 b, err := r.r.Read(r.off, 4)
50 r.off += 4
51 if err != nil {
52 return 0, err
53 }
54 return binary.BigEndian.Uint32(b), nil
55}
56
57func (r *reader) U64() (uint64, error) {
58 b, err := r.r.Read(r.off, 8)
59 r.off += 8
60 if err != nil {
61 return 0, err
62 }
63 return binary.BigEndian.Uint64(b), nil
64}
65
66func (r *reader) ReadByte() (byte, error) {
67 b, err := r.r.Read(r.off, 1)
68 r.off += 1
69 if err != nil {
70 return 0, err
71 }
72 return b[0], nil
73}
74
75func (r *reader) Varint() (uint64, error) {
76 v, err := binary.ReadUvarint(r)
77 if err != nil {
78 return 0, err
79 }
80 return v, nil
81}
82
83func (r *reader) Str() (string, error) {
84 slen, err := r.Varint()
85 if err != nil {
86 return "", err
87 }
88 b, err := r.r.Read(r.off, uint32(slen))
89 if err != nil {
90 return "", err
91 }
92 r.off += uint32(slen)
93 return string(b), nil
94}
95
96func (r *reader) readTOC(toc *indexTOC) error {
97 sz, err := r.r.Size()
98 if err != nil {
99 return err
100 }
101 r.off = sz - 8
102
103 var tocSection simpleSection
104 if err := tocSection.read(r); err != nil {
105 return err
106 }
107
108 r.seek(tocSection.off)
109
110 sectionCount, err := r.U32()
111 if err != nil {
112 return err
113 }
114
115 if sectionCount == 0 {
116 // tagged sections are indicated by a 0 sectionCount,
117 // and then a list of string-tagged type-indicated sections.
118 secs := toc.sectionsTagged()
119 for r.off < tocSection.off+tocSection.sz {
120 tag, err := r.Str()
121 if err != nil {
122 return err
123 }
124 kind, err := r.Varint()
125 if err != nil {
126 return err
127 }
128 sec := secs[tag]
129 if sec != nil && sec.kind() == sectionKind(kind) {
130 // happy path
131 if err := sec.read(r); err != nil {
132 return err
133 }
134 continue
135 }
136 // error case: skip over unknown section
137 if sec == nil {
138 log.Printf("file %s TOC has unknown section %q", r.r.Name(), tag)
139 } else {
140 return fmt.Errorf("file %s TOC section %q expects kind %d, got kind %d", r.r.Name(), tag,
141 kind, sec.kind())
142 }
143 if kind == 0 {
144 if err := (&simpleSection{}).read(r); err != nil {
145 return err
146 }
147 } else if kind == 1 {
148 if err := (&compoundSection{}).read(r); err != nil {
149 return err
150 }
151 }
152 }
153 } else {
154 // TODO: Remove this branch when ReaderMinFeatureVersion >= 10
155
156 secs := toc.sections()
157
158 if len(secs) != int(sectionCount) {
159 secs = toc.sectionsNext()
160 }
161
162 if len(secs) != int(sectionCount) {
163 return fmt.Errorf("section count mismatch: got %d want %d", sectionCount, len(secs))
164 }
165
166 for _, s := range secs {
167 if err := s.read(r); err != nil {
168 return err
169 }
170 }
171 }
172 return nil
173}
174
175func (r *indexData) readSectionBlob(sec simpleSection) ([]byte, error) {
176 return r.file.Read(sec.off, sec.sz)
177}
178
179func readSectionU32(f IndexFile, sec simpleSection) ([]uint32, error) {
180 if sec.sz%4 != 0 {
181 return nil, fmt.Errorf("barf: section size %% 4 != 0: sz %d ", sec.sz)
182 }
183 blob, err := f.Read(sec.off, sec.sz)
184 if err != nil {
185 return nil, err
186 }
187 arr := make([]uint32, 0, len(blob)/4)
188 for len(blob) > 0 {
189 arr = append(arr, binary.BigEndian.Uint32(blob))
190 blob = blob[4:]
191 }
192 return arr, nil
193}
194
195func readSectionU64(f IndexFile, sec simpleSection) ([]uint64, error) {
196 if sec.sz%8 != 0 {
197 return nil, fmt.Errorf("barf: section size %% 8 != 0: sz %d ", sec.sz)
198 }
199 blob, err := f.Read(sec.off, sec.sz)
200 if err != nil {
201 return nil, err
202 }
203 arr := make([]uint64, 0, len(blob)/8)
204 for len(blob) > 0 {
205 arr = append(arr, binary.BigEndian.Uint64(blob))
206 blob = blob[8:]
207 }
208 return arr, nil
209}
210
211func (r *reader) readJSON(data interface{}, sec *simpleSection) error {
212 blob, err := r.r.Read(sec.off, sec.sz)
213 if err != nil {
214 return err
215 }
216
217 return json.Unmarshal(blob, data)
218}
219
220// canReadVersion returns checks if zoekt can read in md. If it can't a
221// non-nil error is returned.
222func canReadVersion(md *IndexMetadata) bool {
223 // Backwards compatible with v16
224 return md.IndexFormatVersion == IndexFormatVersion || md.IndexFormatVersion == NextIndexFormatVersion
225}
226
227func (r *reader) readIndexData(toc *indexTOC) (*indexData, error) {
228 d := indexData{
229 file: r.r,
230 branchIDs: []map[string]uint{},
231 branchNames: []map[uint]string{},
232 }
233
234 repos, md, err := r.readMetadata(toc)
235 if md != nil && !canReadVersion(md) {
236 return nil, fmt.Errorf("file is v%d, want v%d", md.IndexFormatVersion, IndexFormatVersion)
237 } else if err != nil {
238 return nil, err
239 }
240
241 d.metaData = *md
242 d.repoMetaData = make([]Repository, 0, len(repos))
243 for _, r := range repos {
244 d.repoMetaData = append(d.repoMetaData, *r)
245 }
246
247 if d.metaData.IndexFeatureVersion < ReadMinFeatureVersion {
248 return nil, fmt.Errorf("file is feature version %d, want feature version >= %d", d.metaData.IndexFeatureVersion, ReadMinFeatureVersion)
249 }
250
251 if d.metaData.IndexMinReaderVersion > FeatureVersion {
252 return nil, fmt.Errorf("file needs read feature version >= %d, have read feature version %d", d.metaData.IndexMinReaderVersion, FeatureVersion)
253 }
254
255 d.boundariesStart = toc.fileContents.data.off
256 d.boundaries = toc.fileContents.relativeIndex()
257 d.newlinesStart = toc.newlines.data.off
258 d.newlinesIndex = toc.newlines.relativeIndex()
259 d.docSectionsStart = toc.fileSections.data.off
260 d.docSectionsIndex = toc.fileSections.relativeIndex()
261
262 d.symbols.symKindIndex = toc.symbolKindMap.relativeIndex()
263 d.fileEndSymbol, err = readSectionU32(d.file, toc.fileEndSymbol)
264 if err != nil {
265 return nil, err
266 }
267
268 // Call readSectionBlob on each section key, and store the result in
269 // the blob value.
270 for sect, blob := range map[simpleSection]*[]byte{
271 toc.symbolMap.index: &d.symbols.symIndex,
272 toc.symbolMap.data: &d.symbols.symContent,
273 toc.symbolKindMap.data: &d.symbols.symKindContent,
274 toc.symbolMetaData: &d.symbols.symMetaData,
275 } {
276 if *blob, err = d.readSectionBlob(sect); err != nil {
277 return nil, err
278 }
279 }
280
281 d.checksums, err = d.readSectionBlob(toc.contentChecksums)
282 if err != nil {
283 return nil, err
284 }
285
286 d.languages, err = d.readSectionBlob(toc.languages)
287 if err != nil {
288 return nil, err
289 }
290
291 d.ngrams, err = d.newBtreeIndex(toc.ngramText, toc.postings)
292 if err != nil {
293 return nil, err
294 }
295
296 d.fileBranchMasks, err = readSectionU64(d.file, toc.branchMasks)
297 if err != nil {
298 return nil, err
299 }
300
301 d.fileNameContent, err = d.readSectionBlob(toc.fileNames.data)
302 if err != nil {
303 return nil, err
304 }
305
306 d.fileNameIndex = toc.fileNames.relativeIndex()
307
308 d.fileNameNgrams, err = d.newBtreeIndex(toc.nameNgramText, toc.namePostings)
309 if err != nil {
310 return nil, err
311 }
312
313 for _, md := range d.repoMetaData {
314 repoBranchIDs := make(map[string]uint, len(md.Branches))
315 repoBranchNames := make(map[uint]string, len(md.Branches))
316 for j, br := range md.Branches {
317 id := uint(1) << uint(j)
318 repoBranchIDs[br.Name] = id
319 repoBranchNames[id] = br.Name
320 }
321 d.branchIDs = append(d.branchIDs, repoBranchIDs)
322 d.branchNames = append(d.branchNames, repoBranchNames)
323 d.rawConfigMasks = append(d.rawConfigMasks, encodeRawConfig(md.RawConfig))
324 }
325
326 blob, err := d.readSectionBlob(toc.runeDocSections)
327 if err != nil {
328 return nil, err
329 }
330
331 if os.Getenv("ZOEKT_ENABLE_LAZY_DOC_SECTIONS") != "" {
332 d.runeDocSectionsRaw = blob
333 } else {
334 d.runeDocSections = unmarshalDocSections(blob, nil)
335 }
336
337 var runeOffsets, fileNameRuneOffsets []uint32
338
339 for sect, dest := range map[simpleSection]*[]uint32{
340 toc.subRepos: &d.subRepos,
341 toc.runeOffsets: &runeOffsets,
342 toc.nameRuneOffsets: &fileNameRuneOffsets,
343 toc.nameEndRunes: &d.fileNameEndRunes,
344 toc.fileEndRunes: &d.fileEndRunes,
345 } {
346 if blob, err := d.readSectionBlob(sect); err != nil {
347 return nil, err
348 } else {
349 *dest = fromSizedDeltas(blob, nil)
350 }
351 }
352
353 d.runeOffsets = makeRuneOffsetMap(runeOffsets)
354 d.fileNameRuneOffsets = makeRuneOffsetMap(fileNameRuneOffsets)
355
356 d.subRepoPaths = make([][]string, 0, len(d.repoMetaData))
357 for i := 0; i < len(d.repoMetaData); i++ {
358 keys := make([]string, 0, len(d.repoMetaData[i].SubRepoMap)+1)
359 keys = append(keys, "")
360 for k := range d.repoMetaData[i].SubRepoMap {
361 if k != "" {
362 keys = append(keys, k)
363 }
364 }
365 sort.Strings(keys)
366 d.subRepoPaths = append(d.subRepoPaths, keys)
367 }
368
369 d.languageMap = map[uint16]string{}
370 for k, v := range d.metaData.LanguageMap {
371 d.languageMap[v] = k
372 }
373
374 if err := d.verify(); err != nil {
375 return nil, err
376 }
377
378 // roc.ranks.sz = 0 indicates that we are reading a shard without ranks, in
379 // which case we skip reading the section and leave d.ranks = nil
380 if toc.ranks.sz > 0 {
381 err = d.readRanks(toc)
382 if err != nil {
383 return nil, err
384 }
385 }
386
387 if d.metaData.IndexFormatVersion >= 17 {
388 blob, err := d.readSectionBlob(toc.repos)
389 if err != nil {
390 return nil, err
391 }
392 d.repos = fromSizedDeltas16(blob, nil)
393 } else {
394 // every document is for repo index 0 (default value of uint16)
395 d.repos = make([]uint16, len(d.fileBranchMasks))
396 }
397
398 if err := d.calculateStats(); err != nil {
399 return nil, err
400 }
401
402 return &d, nil
403}
404
405func (r *reader) readMetadata(toc *indexTOC) ([]*Repository, *IndexMetadata, error) {
406 var md IndexMetadata
407 if err := r.readJSON(&md, &toc.metaData); err != nil {
408 return nil, nil, err
409 }
410
411 // Sourcegraph specific: we support mutating metadata via an additional
412 // ".meta" file. This is to support tombstoning. An additional benefit is we
413 // can update metadata (such as Rank and Name) without re-indexing content.
414 blob, err := os.ReadFile(r.r.Name() + ".meta")
415 if err != nil && !os.IsNotExist(err) {
416 return nil, &md, fmt.Errorf("failed to read meta file: %w", err)
417 }
418
419 if len(blob) == 0 {
420 blob, err = r.r.Read(toc.repoMetaData.off, toc.repoMetaData.sz)
421 if err != nil {
422 return nil, &md, err
423 }
424 }
425
426 var repos []*Repository
427 if md.IndexFormatVersion >= 17 {
428 if err := json.Unmarshal(blob, &repos); err != nil {
429 return nil, &md, err
430 }
431 } else {
432 repos = make([]*Repository, 1)
433 if err := json.Unmarshal(blob, &repos[0]); err != nil {
434 return nil, &md, err
435 }
436 }
437
438 if md.ID == "" {
439 if len(repos) == 0 {
440 return nil, nil, fmt.Errorf("len(repos)=0. Cannot backfill ID")
441 }
442 md.ID = backfillID(repos[0].Name)
443 }
444
445 return repos, &md, nil
446}
447
448const ngramEncoding = 8
449
450func (d *indexData) newBtreeIndex(ngramSec simpleSection, postings compoundSection) (btreeIndex, error) {
451 bi := btreeIndex{file: d.file}
452
453 textContent, err := d.readSectionBlob(ngramSec)
454 if err != nil {
455 return btreeIndex{}, err
456 }
457
458 // For 500k trigams we can expect approx 1000 leaf nodes (500k divided by
459 // half the bucketSize) and 20 nodes on level 2 (all but the rightmost
460 // inner nodes will have exactly v=50 children) plus a root node.
461 bt := newBtree(btreeOpts{bucketSize: btreeBucketSize, v: 50})
462 for i := 0; i < len(textContent); i += ngramEncoding {
463 ng := ngram(binary.BigEndian.Uint64(textContent[i : i+ngramEncoding]))
464 bt.insert(ng)
465 }
466 bt.freeze()
467
468 bi.bt = bt
469
470 // hold on to simple sections (8 bytes each)
471 bi.ngramSec = ngramSec
472 bi.postingIndex = postings.index
473
474 return bi, nil
475}
476
477func (d *indexData) verify() error {
478 // This is not an exhaustive check: the postings can easily
479 // generate OOB acccesses, and are expensive to check, but this lets us rule out
480 // other sources of OOB access.
481 n := len(d.fileNameIndex)
482 if n == 0 {
483 return nil
484 }
485
486 n--
487 for what, got := range map[string]int{
488 "boundaries": len(d.boundaries) - 1,
489 "branch masks": len(d.fileBranchMasks),
490 "doc section index": len(d.docSectionsIndex) - 1,
491 "newlines index": len(d.newlinesIndex) - 1,
492 } {
493 if got != n {
494 return fmt.Errorf("got %s %d, want %d", what, got, n)
495 }
496 }
497 return nil
498}
499
500func (d *indexData) readContents(i uint32) ([]byte, error) {
501 return d.readSectionBlob(simpleSection{
502 off: d.boundariesStart + d.boundaries[i],
503 sz: d.boundaries[i+1] - d.boundaries[i],
504 })
505}
506
507func (d *indexData) readContentSlice(off uint32, sz uint32) ([]byte, error) {
508 // TODO(hanwen): cap result if it is at the end of the content
509 // section.
510 return d.readSectionBlob(simpleSection{
511 off: d.boundariesStart + off,
512 sz: sz,
513 })
514}
515
516func (d *indexData) readNewlines(i uint32, buf []uint32) ([]uint32, uint32, error) {
517 sec := simpleSection{
518 off: d.newlinesStart + d.newlinesIndex[i],
519 sz: d.newlinesIndex[i+1] - d.newlinesIndex[i],
520 }
521 blob, err := d.readSectionBlob(sec)
522 if err != nil {
523 return nil, 0, err
524 }
525
526 return fromSizedDeltas(blob, buf), sec.sz, nil
527}
528
529func (d *indexData) readDocSections(i uint32, buf []DocumentSection) ([]DocumentSection, uint32, error) {
530 sec := simpleSection{
531 off: d.docSectionsStart + d.docSectionsIndex[i],
532 sz: d.docSectionsIndex[i+1] - d.docSectionsIndex[i],
533 }
534 blob, err := d.readSectionBlob(sec)
535 if err != nil {
536 return nil, 0, err
537 }
538
539 return unmarshalDocSections(blob, buf), sec.sz, nil
540}
541
542func (d *indexData) readRanks(toc *indexTOC) error {
543 blob, err := d.readSectionBlob(toc.ranks)
544 if err != nil {
545 return err
546 }
547
548 return decodeRanks(blob, &d.ranks)
549}
550
551// NewSearcher creates a Searcher for a single index file. Search
552// results coming from this searcher are valid only for the lifetime
553// of the Searcher itself, ie. []byte members should be copied into
554// fresh buffers if the result is to survive closing the shard.
555func NewSearcher(r IndexFile) (Searcher, error) {
556 rd := &reader{r: r}
557
558 var toc indexTOC
559 if err := rd.readTOC(&toc); err != nil {
560 return nil, err
561 }
562 indexData, err := rd.readIndexData(&toc)
563 if err != nil {
564 return nil, err
565 }
566 indexData.file = r
567 return indexData, nil
568}
569
570// ReadMetadata returns the metadata of index shard without reading
571// the index data. The IndexFile is not closed.
572func ReadMetadata(inf IndexFile) ([]*Repository, *IndexMetadata, error) {
573 rd := &reader{r: inf}
574 var toc indexTOC
575 if err := rd.readTOC(&toc); err != nil {
576 return nil, nil, err
577 }
578
579 return rd.readMetadata(&toc)
580}
581
582// ReadMetadataPathAlive is like ReadMetadataPath except that it only returns
583// alive repositories.
584func ReadMetadataPathAlive(p string) ([]*Repository, *IndexMetadata, error) {
585 repos, id, err := ReadMetadataPath(p)
586 if err != nil {
587 return nil, nil, err
588 }
589 alive := repos[:0]
590 for _, repo := range repos {
591 if !repo.Tombstone {
592 alive = append(alive, repo)
593 }
594 }
595 return alive, id, nil
596}
597
598// ReadMetadataPath returns the metadata of index shard at p without reading
599// the index data. ReadMetadataPath is a helper for ReadMetadata which opens
600// the IndexFile at p.
601func ReadMetadataPath(p string) ([]*Repository, *IndexMetadata, error) {
602 f, err := os.Open(p)
603 if err != nil {
604 return nil, nil, err
605 }
606 defer f.Close()
607
608 iFile, err := NewIndexFile(f)
609 if err != nil {
610 return nil, nil, err
611 }
612 defer iFile.Close()
613
614 return ReadMetadata(iFile)
615}
616
617// IndexFilePaths returns all paths for the IndexFile at filepath p that
618// exist. Note: if no files exist this will return an empty slice and nil
619// error.
620//
621// This is p and the ".meta" file for p.
622func IndexFilePaths(p string) ([]string, error) {
623 paths := []string{p, p + ".meta"}
624 exist := paths[:0]
625 for _, p := range paths {
626 if _, err := os.Stat(p); err == nil {
627 exist = append(exist, p)
628 } else if !os.IsNotExist(err) {
629 return nil, err
630 }
631 }
632 return exist, nil
633}
634
635func loadIndexData(r IndexFile) (*indexData, error) {
636 rd := &reader{r: r}
637
638 var toc indexTOC
639 if err := rd.readTOC(&toc); err != nil {
640 return nil, err
641 }
642 return rd.readIndexData(&toc)
643}
644
645// PrintNgramStats outputs a list of the form
646//
647// n_1 trigram_1
648// n_2 trigram_2
649// ...
650//
651// where n_i is the length of the postings list of trigram_i stored in r.
652func PrintNgramStats(r IndexFile) error {
653 id, err := loadIndexData(r)
654 if err != nil {
655 return err
656 }
657
658 var rNgram [3]rune
659 for ngram, ss := range id.ngrams.DumpMap() {
660 rNgram = ngramToRunes(ngram)
661 fmt.Printf("%d\t%q\n", ss.sz, string(rNgram[:]))
662 }
663 return nil
664}
665
666var crc64Table = crc64.MakeTable(crc64.ECMA)
667
668// backfillID returns a 20 char long sortable ID. The ID only depends on s. It
669// should only be used to set the ID of simple v16 shards on read.
670func backfillID(s string) string {
671 var id xid.ID
672
673 // Our timestamps are based on Unix time. Shards without IDs are assigned IDs
674 // based on the 0 epoch.
675 binary.BigEndian.PutUint32(id[:], 0)
676 binary.BigEndian.PutUint64(id[4:], crc64.Checksum([]byte(s), crc64Table))
677 return id.String()
678}