Something went wrong. Try again.
Fast, indexed regexp search over large file trees
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679// Copyright 2011 The Go Authors. All rights reserved.// Use of this source code is governed by a BSD-style// license that can be found in the LICENSE file.
package index
// Index Format//// An index stored on disk has the format://// "csearch index 2\n"// list of roots// list of names// list of posting lists// name index// posting list index// trailer//// The list of roots and list of names are sorted (by Path.Cmp)// sequences of prefix-compressed paths. Each path is encoded// as a varint number of prefix bytes to copy from the previous// path, a varint number of suffix bytes that follow, and the// suffix bytes. For example, the two path sequnce// {"abcdef", "abcx"} is encoded as [0 6 abcdef 3 1 x].//// In the name list, every 16th name has a forced prefix// length of 0, so that random access is possible by starting// at one of these entries. The name index lists the offset// of every 16th name.//// The list of posting lists is a sequence of posting lists.// Each posting list has the form://// trigram [3]// deltas [v]...//// The trigram gives the 3 byte trigram that this list describes. The// delta list is a sequence of [γ-coded] deltas between file IDs,// ending with a zero delta. For example, the delta list [2,5,1,1,0]// encodes the file ID list 1, 6, 7, 8. The delta list [0] would// encode the empty file ID list, but empty posting lists are usually// not recorded at all. The list of posting lists ends with an entry// with trigram "\xff\xff\xff" and a delta list consisting a single zero.// In the γ-encoding, which cannot represent 0, 0 encodes as 31,// and all values v ≥ 31 encode as v+1.//// The indexes enable efficient random access to the lists.//// The name index is a sequence of 8-byte big-endian values listing the// byte offset in the name list where every 16th name begins.//// The posting list index is a sequence of index entries describing// each successive posting list. Each index entry has the form://// trigram [3]// file count [v]// offset [v]//// The file count and offset are varint-encoded, breaking random// access to the posting list index. To restore that, any index// entry that would otherwise cross a 256-byte boundary is preceded// by zeroed padding bytes up to the boundary. The overall index// is also zero-padded to a multiple of 256 bytes.// The offsets in each 256-byte chunk are delta-encoded starting// from a base offset of 0.//// Index entries are only written for the non-empty posting lists,// so finding the posting list for a specific trigram requires a// binary search over the posting list index. To find an entry// in the index for a given trigram, binary search on the 256-byte// sections to find the 256-byte entry where it would be,// and then linear search in the 256-byte section.//// In practice, the majority of the possible trigrams are never// seen, so omitting the missing ones represents a significant// storage savings.//// The trailer has the form://// offset of root list [8]// number of roots [8]// offset of name list [8]// number of names [8]// offset of posting lists [8]// number of posting lists [8]// offset of name index [8]// offset of posting list index [8]// "\ncsearch trlr 2\n"//// The code has never checked the index header, so version changes// must be made by modifying the trailer.// Old 32-bit Version//// An older 32-bit format had the following differences://// - The header was "csearch index 1\n".// - The trailer was "\ncsearch trailr\n".// - All the 8-byte values were 4-byte values.// - The root and names lists were not prefix-compressed nor// varint-delimited. Instead, they were as a sequence of// NUL-terminated paths, with a final empty path marking// the end of the list.// - The name index had an entry for every name, not every 16th name.// - The trailer did not contain "number of roots".// - The trailer did not contain "number of names".// - The posting list deltas were uvarint-coded instead of γ-coded.//// At the time of conversion, indexing Linux git at v6.9-9880-gdaa121128a2d// with the old index format had the following file region sizes://// 16 header// 22 path list// 5,082,088 name list// 147,703,290 posting lists// 337,656 name index// 4,636,335 posting list index// 36 trailer// -----------// 157,759,443 total//// The 64-bit version of this file had instead://// 16 header// 32 path list// 1,170,592 name list// 85,872,880 posting lists// 42,208 name index// 2,292,480 posting list index// 80 trailer// -----------// 89,378,288 total (including padding)//// Overall, the tighter encoding in the 64-bit-friendly version// yields a >40% reduction in index size.//// For an index of 1.6 TB of Go module zip files, the direct 64-bit// extension of the v1 index used 162 GB, while the tighter encodings// reduced the index to 84 GB://// name list: 28.6 GB -> 4.0 GB// posting lists: 132.7 GB -> 80.3 GB// name index: 1.1 GB -> 0.07 GB// posting index: 0.050 GB -> 0.016 GB//// [γ-coded]: https://en.wikipedia.org/wiki/Elias_gamma_coding
import ( "bytes" "encoding/binary" "fmt" "iter" "log" "os" "path/filepath" "runtime" "sort")
const ( magicV1 = "csearch index 1\n" magicV2 = "csearch index 2\n" trailerMagicV1 = "\ncsearch trailr\n" trailerMagicV2 = "\ncsearch trlr 2\n"
postBlockSize = 256 // posting index entries are packed into 256-byte blocks nameGroupSize = 16 // names are prefix-compressed in groups of 16
postIndexEntrySizeV1 = 3 + 4 + 4)
// An Index implements read-only access to a trigram index.type Index struct { Verbose bool name string data mmapData version int pathData int numPath int nameData int postData int nameIndex int numName int postIndex int numPost int numPostBlock int}
func (ix *Index) PrintStats() { fmt.Printf("%d path list (%d paths)\n", ix.nameData-ix.pathData, ix.numPath) fmt.Printf("%d name list (%d names)\n", ix.postData-ix.nameData, ix.numName) fmt.Printf("%d posting lists (%d trigrams)\n", ix.nameIndex-ix.postData, ix.numPost) fmt.Printf("%d name index\n", ix.postIndex-ix.nameIndex) fmt.Printf("%d posting index\n", ix.numPostBlock*postBlockSize)}
func Open(file string) *Index { mm := mmap(file) ix := &Index{name: file, data: mm} if len(mm.d) < len(trailerMagicV1) { ix.corrupt() }
magic := string(mm.d[len(mm.d)-len(trailerMagicV1):]) var n int switch magic { default: ix.corrupt()
case trailerMagicV1: ix.version = 1 n = len(mm.d) - len(trailerMagicV1) - 5*4 if n < 0 { ix.corrupt() } ix.pathData = ix.uint32(n) ix.nameData = ix.uint32(n + 4) ix.postData = ix.uint32(n + 8) ix.nameIndex = ix.uint32(n + 12) ix.postIndex = ix.uint32(n + 16) ix.numName = (ix.postIndex-ix.nameIndex)/4 - 1 ix.numPost = (n - ix.postIndex) / postIndexEntrySizeV1 ix.numPath = -1
case trailerMagicV2: ix.version = 2 n = len(mm.d) - len(trailerMagicV2) - 8*8 if n < 0 { ix.corrupt() } ix.pathData = ix.uint64(n) ix.numPath = ix.uint64(n + 1*8) ix.nameData = ix.uint64(n + 2*8) ix.numName = ix.uint64(n + 3*8) ix.postData = ix.uint64(n + 4*8) ix.numPost = ix.uint64(n + 5*8) ix.nameIndex = ix.uint64(n + 6*8) ix.postIndex = ix.uint64(n + 7*8) ix.numPostBlock = (n - ix.postIndex) / postBlockSize }
return ix}
// slice returns the slice of index data starting at the given byte offset.// If n >= 0, the slice must have length at least n and is truncated to length n.func (ix *Index) slice(off int, n int) []byte { if off < 0 { ix.corrupt() } if n < 0 { return ix.data.d[off:] } if off+n < off || off+n > len(ix.data.d) { ix.corrupt() } return ix.data.d[off : off+n]}
// uint32 returns the uint32 value at the given offset in the index data.func (ix *Index) uint32(off int) int { v := binary.BigEndian.Uint32(ix.slice(off, 4)) if int(v) < 0 { ix.corrupt() } return int(v)}
// uint64 returns the uint64 value at the given offset in the index data.func (ix *Index) uint64(off int) int { v := binary.BigEndian.Uint64(ix.slice(off, 8)) if int(v) < 0 || uint64(int(v)) != v { ix.corrupt() } return int(v)}
// Roots returns the list of indexed roots.func (ix *Index) Roots() *PathReader { return NewPathReader(ix.version, ix.slice(ix.pathData, ix.nameData-ix.pathData), ix.numPath)}
// Name returns the name corresponding to the given fileid.func (ix *Index) Name(fileid int) Path { return ix.NamesAt(fileid, fileid+1).Path()}
// NameAt returns a PathReader returning the names for// fileids in the range [min, max).func (ix *Index) NamesAt(min, max int) *PathReader { if min >= ix.numName { return NewPathReader(1, nil, 0) } limit := max - min var off int if ix.version == 1 { off = ix.uint32(ix.nameIndex + min*4) } else { off = ix.uint64(ix.nameIndex + min/nameGroupSize*8) limit += min % nameGroupSize } names := NewPathReader(ix.version, ix.slice(ix.nameData+off, ix.postData-(ix.nameData+off)), limit) if ix.version == 2 { for range min % nameGroupSize { names.Next() } } return names}
func (ix *Index) Names(lo, hi int) iter.Seq[Path] { r := ix.NamesAt(lo, hi) if r.Valid() { r.limit = hi - lo - 1 } return r.All()}
func (ix *Index) str(off int) []byte { str := ix.slice(off, -1) i := bytes.IndexByte(str, '\x00') if i < 0 { ix.corrupt() } return str[:i]}
// listAt returns the i'th posting index list entry.// It is only valid for version 1 indexes.func (ix *Index) postIndexEntry(i int) (trigram uint32, count, offset int) { if ix.version != 1 { panic("postIndexEntry misuse") } d := ix.slice(ix.postIndex+i*postIndexEntrySizeV1, postIndexEntrySizeV1) trigram = uint32(d[0])<<16 | uint32(d[1])<<8 | uint32(d[2]) if ix.version == 1 { count = int(binary.BigEndian.Uint32(d[3:])) offset = int(binary.BigEndian.Uint32(d[3+4:])) } else { count = int(binary.BigEndian.Uint64(d[3:])) offset = int(binary.BigEndian.Uint64(d[3+8:])) } if count < 0 || offset < 0 { ix.corrupt() } return}
func (ix *Index) findList(trigram uint32) (count, offset int) { if ix.version == 2 { return ix.findListV2(trigram) } // binary search d := ix.slice(ix.postIndex, ix.numPost*postIndexEntrySizeV1) i := sort.Search(ix.numPost, func(i int) bool { i *= postIndexEntrySizeV1 t := uint32(d[i])<<16 | uint32(d[i+1])<<8 | uint32(d[i+2]) return t >= trigram }) if i >= ix.numPost { return 0, 0 } t, count, offset := ix.postIndexEntry(i) if t != trigram { return 0, 0 } return count, offset}
func (ix *Index) findListV2(trigram uint32) (count, offset int) { // binary search to find first posting block too late for trigram b := ix.slice(ix.postIndex, ix.numPostBlock*postBlockSize) i := sort.Search(ix.numPostBlock, func(i int) bool { i *= postBlockSize t := uint32(b[i])<<16 | uint32(b[i+1])<<8 | uint32(b[i+2]) return t > trigram }) if i == 0 { return 0, 0 }
// walk block to find trigram b = b[(i-1)*postBlockSize : i*postBlockSize] for len(b) >= 3 { t := uint32(b[0])<<16 | uint32(b[1])<<8 | uint32(b[2]) if t == 0 { break } count, n1 := binary.Uvarint(b[3:]) if n1 < 0 { ix.corrupt() } o, n2 := binary.Uvarint(b[3+n1:]) if n2 < 0 { ix.corrupt() } offset += int(o) if t == trigram { return int(count), offset } b = b[3+n1+n2:] } return 0, 0}
type postReader struct { ix *Index count int offset int fileid int restrict []int delta deltaReader}
func (r *postReader) init(ix *Index, trigram uint32, restrict []int) { count, offset := ix.findList(trigram) if count == 0 { return } r.ix = ix r.count = count r.offset = offset r.fileid = -1 r.delta.init(r.ix, ix.slice(ix.postData+offset+3, -1)) r.restrict = restrict}
func (r *postReader) max() int { return int(r.count)}
func (r *postReader) next() bool { if r.ix == nil { return false } for r.count > 0 { r.count-- delta := r.delta.next() if delta <= 0 { r.ix.corrupt() } r.fileid += delta if r.restrict != nil { i := 0 for i < len(r.restrict) && r.restrict[i] < r.fileid { i++ } r.restrict = r.restrict[i:] if len(r.restrict) == 0 || r.restrict[0] != r.fileid { continue } } return true } // list should end with terminating 0 delta if r.delta.next() != 0 { r.ix.corrupt() } r.delta.clearBits() r.fileid = -1 return false}
type allPostReader struct { trigram uint32 fileid int is64 bool delta deltaReader}
func (r *allPostReader) init(ix *Index, data []byte) { r.delta.init(ix, data) r.trigram = invalidTrigram}
func (r *allPostReader) next() (postEntry, bool) { for { if r.trigram == invalidTrigram { d := r.delta.d if len(d) == 0 { return 0, false } if len(d) < 3 { log.Fatalf("internal error: invalid temporary file") } r.trigram = uint32(d[0])<<16 | uint32(d[1])<<8 | uint32(d[2]) d = d[3:] r.fileid = -1 r.delta.d = d } delta := r.delta.next() if delta == 0 { r.delta.clearBits() r.trigram = invalidTrigram continue } r.fileid += delta return makePostEntry(r.trigram, r.fileid), true }}
func (ix *Index) PostingList(trigram uint32) []int { return ix.postingList(trigram, nil)}
func (ix *Index) postingList(trigram uint32, restrict []int) []int { var r postReader r.init(ix, trigram, restrict) x := make([]int, 0, r.max()) for r.next() { x = append(x, r.fileid) } return x}
func (ix *Index) PostingAnd(list []int, trigram uint32) []int { return ix.postingAnd(list, trigram, nil)}
func (ix *Index) postingAnd(list []int, trigram uint32, restrict []int) []int { var r postReader r.init(ix, trigram, restrict) x := list[:0] i := 0 for r.next() { fileid := r.fileid for i < len(list) && list[i] < fileid { i++ } if i < len(list) && list[i] == fileid { x = append(x, fileid) i++ } } return x}
func (ix *Index) PostingOr(list []int, trigram uint32) []int { return ix.postingOr(list, trigram, nil)}
func (ix *Index) postingOr(list []int, trigram uint32, restrict []int) []int { var r postReader r.init(ix, trigram, restrict) x := make([]int, 0, len(list)+r.max()) i := 0 for r.next() { fileid := r.fileid for i < len(list) && list[i] < fileid { x = append(x, list[i]) i++ } x = append(x, fileid) if i < len(list) && list[i] == fileid { i++ } } x = append(x, list[i:]...) return x}
func (ix *Index) PostingQuery(q *Query) []int { return ix.postingQuery(q, nil)}
func (ix *Index) postingQuery(q *Query, restrict []int) (ret []int) { var list []int switch q.Op { case QNone: // nothing case QAll: if restrict != nil { return restrict } list = make([]int, ix.numName) for i := range list { list[i] = i } return list case QAnd: for _, t := range q.Trigram { tri := uint32(t[0])<<16 | uint32(t[1])<<8 | uint32(t[2]) if list == nil { list = ix.postingList(tri, restrict) } else { list = ix.postingAnd(list, tri, restrict) } if len(list) == 0 { return nil } } for _, sub := range q.Sub { if list == nil { list = restrict } list = ix.postingQuery(sub, list) if len(list) == 0 { return nil } } case QOr: for _, t := range q.Trigram { tri := uint32(t[0])<<16 | uint32(t[1])<<8 | uint32(t[2]) if list == nil { list = ix.postingList(tri, restrict) } else { list = ix.postingOr(list, tri, restrict) } } for _, sub := range q.Sub { list1 := ix.postingQuery(sub, restrict) list = mergeOr(list, list1) } } return list}
func mergeOr(l1, l2 []int) []int { var l []int i := 0 j := 0 for i < len(l1) || j < len(l2) { switch { case j == len(l2) || (i < len(l1) && l1[i] < l2[j]): l = append(l, l1[i]) i++ case i == len(l1) || (j < len(l2) && l1[i] > l2[j]): l = append(l, l2[j]) j++ case l1[i] == l2[j]: l = append(l, l1[i]) i++ j++ } } return l}
var panicOnCorrupt = true
func (ix *Index) corrupt() { if panicOnCorrupt { panic("corrupt index") } log.Fatal("corrupt index: remove " + ix.name)}
// An mmapData is mmap'ed read-only data from a file.type mmapData struct { f *os.File d []byte}
// mmap maps the given file into memory.func mmap(file string) mmapData { f, err := os.Open(file) if err != nil { log.Fatal(err) } return mmapFile(f)}
// TODO look in parent directories for index// TODO cindex -init
// File returns the name of the index file to use.// It is either $CSEARCHINDEX or $HOME/.csearchindex.func File() string { f := os.Getenv("CSEARCHINDEX") if f != "" { return f } var home string home = os.Getenv("HOME") if runtime.GOOS == "windows" && home == "" { home = os.Getenv("USERPROFILE") } return filepath.Clean(home + "/.csearchindex")}