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.contentNgrams, 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 d.runeDocSections = unmarshalDocSections(blob, nil)
332
333 var runeOffsets, fileNameRuneOffsets []uint32
334
335 for sect, dest := range map[simpleSection]*[]uint32{
336 toc.subRepos: &d.subRepos,
337 toc.runeOffsets: &runeOffsets,
338 toc.nameRuneOffsets: &fileNameRuneOffsets,
339 toc.nameEndRunes: &d.fileNameEndRunes,
340 toc.fileEndRunes: &d.fileEndRunes,
341 } {
342 if blob, err := d.readSectionBlob(sect); err != nil {
343 return nil, err
344 } else {
345 *dest = fromSizedDeltas(blob, nil)
346 }
347 }
348
349 d.runeOffsets = makeRuneOffsetMap(runeOffsets)
350 d.fileNameRuneOffsets = makeRuneOffsetMap(fileNameRuneOffsets)
351
352 d.subRepoPaths = make([][]string, 0, len(d.repoMetaData))
353 for i := 0; i < len(d.repoMetaData); i++ {
354 keys := make([]string, 0, len(d.repoMetaData[i].SubRepoMap)+1)
355 keys = append(keys, "")
356 for k := range d.repoMetaData[i].SubRepoMap {
357 if k != "" {
358 keys = append(keys, k)
359 }
360 }
361 sort.Strings(keys)
362 d.subRepoPaths = append(d.subRepoPaths, keys)
363 }
364
365 d.languageMap = map[uint16]string{}
366 for k, v := range d.metaData.LanguageMap {
367 d.languageMap[v] = k
368 }
369
370 if err := d.verify(); err != nil {
371 return nil, err
372 }
373
374 // roc.ranks.sz = 0 indicates that we are reading a shard without ranks, in
375 // which case we skip reading the section and leave d.ranks = nil
376 if toc.ranks.sz > 0 {
377 err = d.readRanks(toc)
378 if err != nil {
379 return nil, err
380 }
381 }
382
383 if d.metaData.IndexFormatVersion >= 17 {
384 blob, err := d.readSectionBlob(toc.repos)
385 if err != nil {
386 return nil, err
387 }
388 d.repos = fromSizedDeltas16(blob, nil)
389 } else {
390 // every document is for repo index 0 (default value of uint16)
391 d.repos = make([]uint16, len(d.fileBranchMasks))
392 }
393
394 if err := d.calculateStats(); err != nil {
395 return nil, err
396 }
397
398 return &d, nil
399}
400
401func (r *reader) readMetadata(toc *indexTOC) ([]*Repository, *IndexMetadata, error) {
402 var md IndexMetadata
403 if err := r.readJSON(&md, &toc.metaData); err != nil {
404 return nil, nil, err
405 }
406
407 // Sourcegraph specific: we support mutating metadata via an additional
408 // ".meta" file. This is to support tombstoning. An additional benefit is we
409 // can update metadata (such as Rank and Name) without re-indexing content.
410 blob, err := os.ReadFile(r.r.Name() + ".meta")
411 if err != nil && !os.IsNotExist(err) {
412 return nil, &md, fmt.Errorf("failed to read meta file: %w", err)
413 }
414
415 if len(blob) == 0 {
416 blob, err = r.r.Read(toc.repoMetaData.off, toc.repoMetaData.sz)
417 if err != nil {
418 return nil, &md, err
419 }
420 }
421
422 var repos []*Repository
423 if md.IndexFormatVersion >= 17 {
424 if err := json.Unmarshal(blob, &repos); err != nil {
425 return nil, &md, err
426 }
427 } else {
428 repos = make([]*Repository, 1)
429 if err := json.Unmarshal(blob, &repos[0]); err != nil {
430 return nil, &md, err
431 }
432 }
433
434 if md.ID == "" {
435 if len(repos) == 0 {
436 return nil, nil, fmt.Errorf("len(repos)=0. Cannot backfill ID")
437 }
438 md.ID = backfillID(repos[0].Name)
439 }
440
441 return repos, &md, nil
442}
443
444const ngramEncoding = 8
445
446func (d *indexData) newBtreeIndex(ngramSec simpleSection, postings compoundSection) (btreeIndex, error) {
447 bi := btreeIndex{file: d.file}
448
449 textContent, err := d.readSectionBlob(ngramSec)
450 if err != nil {
451 return btreeIndex{}, err
452 }
453
454 // For 500k trigams we can expect approx 1000 leaf nodes (500k divided by
455 // half the bucketSize) and 20 nodes on level 2 (all but the rightmost
456 // inner nodes will have exactly v=50 children) plus a root node.
457 bt := newBtree(btreeOpts{bucketSize: btreeBucketSize, v: 50})
458 for i := 0; i < len(textContent); i += ngramEncoding {
459 ng := ngram(binary.BigEndian.Uint64(textContent[i : i+ngramEncoding]))
460 bt.insert(ng)
461 }
462 bt.freeze()
463
464 bi.bt = bt
465
466 // hold on to simple sections (8 bytes each)
467 bi.ngramSec = ngramSec
468 bi.postingIndex = postings.index
469
470 return bi, nil
471}
472
473func (d *indexData) verify() error {
474 // This is not an exhaustive check: the postings can easily
475 // generate OOB acccesses, and are expensive to check, but this lets us rule out
476 // other sources of OOB access.
477 n := len(d.fileNameIndex)
478 if n == 0 {
479 return nil
480 }
481
482 n--
483 for what, got := range map[string]int{
484 "boundaries": len(d.boundaries) - 1,
485 "branch masks": len(d.fileBranchMasks),
486 "doc section index": len(d.docSectionsIndex) - 1,
487 "newlines index": len(d.newlinesIndex) - 1,
488 } {
489 if got != n {
490 return fmt.Errorf("got %s %d, want %d", what, got, n)
491 }
492 }
493 return nil
494}
495
496func (d *indexData) readContents(i uint32) ([]byte, error) {
497 return d.readSectionBlob(simpleSection{
498 off: d.boundariesStart + d.boundaries[i],
499 sz: d.boundaries[i+1] - d.boundaries[i],
500 })
501}
502
503func (d *indexData) readContentSlice(off uint32, sz uint32) ([]byte, error) {
504 // TODO(hanwen): cap result if it is at the end of the content
505 // section.
506 return d.readSectionBlob(simpleSection{
507 off: d.boundariesStart + off,
508 sz: sz,
509 })
510}
511
512func (d *indexData) readNewlines(i uint32, buf []uint32) ([]uint32, uint32, error) {
513 sec := simpleSection{
514 off: d.newlinesStart + d.newlinesIndex[i],
515 sz: d.newlinesIndex[i+1] - d.newlinesIndex[i],
516 }
517 blob, err := d.readSectionBlob(sec)
518 if err != nil {
519 return nil, 0, err
520 }
521
522 return fromSizedDeltas(blob, buf), sec.sz, nil
523}
524
525func (d *indexData) readDocSections(i uint32, buf []DocumentSection) ([]DocumentSection, uint32, error) {
526 sec := simpleSection{
527 off: d.docSectionsStart + d.docSectionsIndex[i],
528 sz: d.docSectionsIndex[i+1] - d.docSectionsIndex[i],
529 }
530 blob, err := d.readSectionBlob(sec)
531 if err != nil {
532 return nil, 0, err
533 }
534
535 return unmarshalDocSections(blob, buf), sec.sz, nil
536}
537
538func (d *indexData) readRanks(toc *indexTOC) error {
539 blob, err := d.readSectionBlob(toc.ranks)
540 if err != nil {
541 return err
542 }
543
544 return decodeRanks(blob, &d.ranks)
545}
546
547// NewSearcher creates a Searcher for a single index file. Search
548// results coming from this searcher are valid only for the lifetime
549// of the Searcher itself, ie. []byte members should be copied into
550// fresh buffers if the result is to survive closing the shard.
551func NewSearcher(r IndexFile) (Searcher, error) {
552 rd := &reader{r: r}
553
554 var toc indexTOC
555 if err := rd.readTOC(&toc); err != nil {
556 return nil, err
557 }
558 indexData, err := rd.readIndexData(&toc)
559 if err != nil {
560 return nil, err
561 }
562 indexData.file = r
563 return indexData, nil
564}
565
566// ReadMetadata returns the metadata of index shard without reading
567// the index data. The IndexFile is not closed.
568func ReadMetadata(inf IndexFile) ([]*Repository, *IndexMetadata, error) {
569 rd := &reader{r: inf}
570 var toc indexTOC
571 if err := rd.readTOC(&toc); err != nil {
572 return nil, nil, err
573 }
574
575 return rd.readMetadata(&toc)
576}
577
578// ReadMetadataPathAlive is like ReadMetadataPath except that it only returns
579// alive repositories.
580func ReadMetadataPathAlive(p string) ([]*Repository, *IndexMetadata, error) {
581 repos, id, err := ReadMetadataPath(p)
582 if err != nil {
583 return nil, nil, err
584 }
585 alive := repos[:0]
586 for _, repo := range repos {
587 if !repo.Tombstone {
588 alive = append(alive, repo)
589 }
590 }
591 return alive, id, nil
592}
593
594// ReadMetadataPath returns the metadata of index shard at p without reading
595// the index data. ReadMetadataPath is a helper for ReadMetadata which opens
596// the IndexFile at p.
597func ReadMetadataPath(p string) ([]*Repository, *IndexMetadata, error) {
598 f, err := os.Open(p)
599 if err != nil {
600 return nil, nil, err
601 }
602 defer f.Close()
603
604 iFile, err := NewIndexFile(f)
605 if err != nil {
606 return nil, nil, err
607 }
608 defer iFile.Close()
609
610 return ReadMetadata(iFile)
611}
612
613// IndexFilePaths returns all paths for the IndexFile at filepath p that
614// exist. Note: if no files exist this will return an empty slice and nil
615// error.
616//
617// This is p and the ".meta" file for p.
618func IndexFilePaths(p string) ([]string, error) {
619 paths := []string{p, p + ".meta"}
620 exist := paths[:0]
621 for _, p := range paths {
622 if _, err := os.Stat(p); err == nil {
623 exist = append(exist, p)
624 } else if !os.IsNotExist(err) {
625 return nil, err
626 }
627 }
628 return exist, nil
629}
630
631func loadIndexData(r IndexFile) (*indexData, error) {
632 rd := &reader{r: r}
633
634 var toc indexTOC
635 if err := rd.readTOC(&toc); err != nil {
636 return nil, err
637 }
638 return rd.readIndexData(&toc)
639}
640
641// PrintNgramStats outputs a list of the form
642//
643// n_1 trigram_1
644// n_2 trigram_2
645// ...
646//
647// where n_i is the length of the postings list of trigram_i stored in r.
648func PrintNgramStats(r IndexFile) error {
649 id, err := loadIndexData(r)
650 if err != nil {
651 return err
652 }
653
654 var rNgram [3]rune
655 for ngram, ss := range id.contentNgrams.DumpMap() {
656 rNgram = ngramToRunes(ngram)
657 fmt.Printf("%d\t%q\n", ss.sz, string(rNgram[:]))
658 }
659 return nil
660}
661
662var crc64Table = crc64.MakeTable(crc64.ECMA)
663
664// backfillID returns a 20 char long sortable ID. The ID only depends on s. It
665// should only be used to set the ID of simple v16 shards on read.
666func backfillID(s string) string {
667 var id xid.ID
668
669 // Our timestamps are based on Unix time. Shards without IDs are assigned IDs
670 // based on the 0 epoch.
671 binary.BigEndian.PutUint32(id[:], 0)
672 binary.BigEndian.PutUint64(id[4:], crc64.Checksum([]byte(s), crc64Table))
673 return id.String()
674}