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