git.sesse.net Git - plocate/blob - parse_trigrams.h

   1 #ifndef _PARSE_TRIGRAMS_H
   2 #define _PARSE_TRIGRAMS_H 1
   3
   4 #include "db.h"
   5
   6 #include <stdint.h>
   7 #include <string>
   8 #include <utility>
   9 #include <vector>
  10
  11 // One or more trigrams, with an implicit OR between them. For case-sensitive searches,
  12 // this is just e.g. “abc”, but for case-insensitive, it would be “abc OR abC or aBc ...” etc.
  13 struct TrigramDisjunction {
  14         unsigned index;  // For debugging only.
  15
  16         // The alternatives as determined by parse_trigrams().
  17         std::vector<uint32_t> trigram_alternatives;
  18
  19         // Like trigram_alternatives, but only the ones we've actually read from the
  20         // hash table (the non-existent ones are filtered out). The second member is
  21         // the length in bytes. Incomplete if remaining_trigrams_to_read > 0.
  22         std::vector<std::pair<Trigram, size_t>> read_trigrams;
  23
  24         // Sum of num_docids in all trigrams. This is usually a fairly good indicator
  25         // of the real number of docids, since there are few files that would have e.g.
  26         // both abc and abC in them (but of course, with multiple files in the same
  27         // docid block, it is far from unheard of).
  28         uint32_t max_num_docids;
  29
  30         // While reading posting lists: Holds the union of the posting lists read
  31         // so far. Once remaining_trigrams_to_read == 0 (all are read), will be taken
  32         // out and used for intersections against the other disjunctions.
  33         std::vector<uint32_t> docids;
  34
  35         // While looking up in the hash table (filling out read_trigrams): Number of
  36         // lookups in the hash table remaining. While reading actual posting lists
  37         // (filling out docids): Number of posting lists left to read.
  38         unsigned remaining_trigrams_to_read;
  39 };
  40
  41 // Take the given needle (search string) and break it down into a set of trigrams
  42 // (or trigram alternatives; see TrigramDisjunction) that must be present for the
  43 // string to match. (Note: They are not _sufficient_ for the string to match;
  44 // false positives might very well occur and must be weeded out later.)
  45 //
  46 // For the case-sensitive case, this is straightforward; just take every trigram
  47 // present in the needle and add them (e.g. abcd -> abc AND bcd).
  48 // For case-insensitivity, it's trickier; see the comments in the function.
  49 //
  50 // Note that our trigrams are on the basis of bytes, not Unicode code points.
  51 // This both simplifies table structure (everything is the same length), and
  52 // guards us against trigram explosion (imagine every combination of CJK characters
  53 // getting their own trigram).
  54 void parse_trigrams(const std::string &needle, bool ignore_case, std::vector<TrigramDisjunction> *trigram_groups);
  55
  56 static constexpr uint32_t WILDCARD_UNIGRAM = 0xFF000000;
  57 static constexpr uint32_t PREMATURE_END_UNIGRAM = 0xFF000001;
  58
  59 // Reads a unigram, taking into account escaping (\<foo> becomes <foo>).
  60 // Returns WILDCARD_UNIGRAM if there's an invalid unigram, ie., we found
  61 // a glob character (?, * or a [] group). Returns EOS_UNIGRAM if we went
  62 // past the end of the string, e.g., a string that ends in a backslash.
  63 // The second element is always the length.
  64 std::pair<uint32_t, size_t> read_unigram(const std::string &s, size_t start);
  65
  66 // Reads a trigram, ie., three calls to read_unigram(). Needs to start on a valid unigram.
  67 // Returns WILDCARD_UNIGRAM or PREMATURE_END_UNIGRAM of either of those occurred
  68 // during reading of the string.
  69 uint32_t read_trigram(const std::string &s, size_t start);
  70
  71 // For debugging.
  72 std::string print_td(const TrigramDisjunction &td);
  73 std::string print_trigram(uint32_t trgm);
  74
  75 #endif  // !defined(_PARSE_TRIGRAMS_H)