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