lang/sql/sqlite/ext/fts3/fts3Int.h

   1 /*
   2 ** 2009 Nov 12
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 ******************************************************************************
  12 **
  13 */
  14
  15 #ifndef _FTSINT_H
  16 #define _FTSINT_H
  17
  18 #if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
  19 # define NDEBUG 1
  20 #endif
  21
  22 #include "sqlite3.h"
  23 #include "fts3_tokenizer.h"
  24 #include "fts3_hash.h"
  25
  26 /*
  27 ** This constant controls how often segments are merged. Once there are
  28 ** FTS3_MERGE_COUNT segments of level N, they are merged into a single
  29 ** segment of level N+1.
  30 */
  31 #define FTS3_MERGE_COUNT 16
  32
  33 /*
  34 ** This is the maximum amount of data (in bytes) to store in the
  35 ** Fts3Table.pendingTerms hash table. Normally, the hash table is
  36 ** populated as documents are inserted/updated/deleted in a transaction
  37 ** and used to create a new segment when the transaction is committed.
  38 ** However if this limit is reached midway through a transaction, a new
  39 ** segment is created and the hash table cleared immediately.
  40 */
  41 #define FTS3_MAX_PENDING_DATA (1*1024*1024)
  42
  43 /*
  44 ** Macro to return the number of elements in an array. SQLite has a
  45 ** similar macro called ArraySize(). Use a different name to avoid
  46 ** a collision when building an amalgamation with built-in FTS3.
  47 */
  48 #define SizeofArray(X) ((int)(sizeof(X)/sizeof(X[0])))
  49
  50 /*
  51 ** Maximum length of a varint encoded integer. The varint format is different
  52 ** from that used by SQLite, so the maximum length is 10, not 9.
  53 */
  54 #define FTS3_VARINT_MAX 10
  55
  56 /*
  57 ** The testcase() macro is only used by the amalgamation.  If undefined,
  58 ** make it a no-op.
  59 */
  60 #ifndef testcase
  61 # define testcase(X)
  62 #endif
  63
  64 /*
  65 ** Terminator values for position-lists and column-lists.
  66 */
  67 #define POS_COLUMN  (1)     /* Column-list terminator */
  68 #define POS_END     (0)     /* Position-list terminator */
  69
  70 /*
  71 ** This section provides definitions to allow the
  72 ** FTS3 extension to be compiled outside of the
  73 ** amalgamation.
  74 */
  75 #ifndef SQLITE_AMALGAMATION
  76 /*
  77 ** Macros indicating that conditional expressions are always true or
  78 ** false.
  79 */
  80 #ifdef SQLITE_COVERAGE_TEST
  81 # define ALWAYS(x) (1)
  82 # define NEVER(X)  (0)
  83 #else
  84 # define ALWAYS(x) (x)
  85 # define NEVER(X)  (x)
  86 #endif
  87
  88 /*
  89 ** Internal types used by SQLite.
  90 */
  91 typedef unsigned char u8;         /* 1-byte (or larger) unsigned integer */
  92 typedef short int i16;            /* 2-byte (or larger) signed integer */
  93 typedef unsigned int u32;         /* 4-byte unsigned integer */
  94 typedef sqlite3_uint64 u64;       /* 8-byte unsigned integer */
  95 /*
  96 ** Macro used to suppress compiler warnings for unused parameters.
  97 */
  98 #define UNUSED_PARAMETER(x) (void)(x)
  99 #endif
 100
 101 typedef struct Fts3Table Fts3Table;
 102 typedef struct Fts3Cursor Fts3Cursor;
 103 typedef struct Fts3Expr Fts3Expr;
 104 typedef struct Fts3Phrase Fts3Phrase;
 105 typedef struct Fts3PhraseToken Fts3PhraseToken;
 106
 107 typedef struct Fts3SegFilter Fts3SegFilter;
 108 typedef struct Fts3DeferredToken Fts3DeferredToken;
 109 typedef struct Fts3SegReader Fts3SegReader;
 110 typedef struct Fts3SegReaderCursor Fts3SegReaderCursor;
 111
 112 /*
 113 ** A connection to a fulltext index is an instance of the following
 114 ** structure. The xCreate and xConnect methods create an instance
 115 ** of this structure and xDestroy and xDisconnect free that instance.
 116 ** All other methods receive a pointer to the structure as one of their
 117 ** arguments.
 118 */
 119 struct Fts3Table {
 120   sqlite3_vtab base;              /* Base class used by SQLite core */
 121   sqlite3 *db;                    /* The database connection */
 122   const char *zDb;                /* logical database name */
 123   const char *zName;              /* virtual table name */
 124   int nColumn;                    /* number of named columns in virtual table */
 125   char **azColumn;                /* column names.  malloced */
 126   sqlite3_tokenizer *pTokenizer;  /* tokenizer for inserts and queries */
 127
 128   /* Precompiled statements used by the implementation. Each of these
 129   ** statements is run and reset within a single virtual table API call.
 130   */
 131   sqlite3_stmt *aStmt[24];
 132
 133   char *zReadExprlist;
 134   char *zWriteExprlist;
 135
 136   int nNodeSize;                  /* Soft limit for node size */
 137   u8 bHasStat;                    /* True if %_stat table exists */
 138   u8 bHasDocsize;                 /* True if %_docsize table exists */
 139   int nPgsz;                      /* Page size for host database */
 140   char *zSegmentsTbl;             /* Name of %_segments table */
 141   sqlite3_blob *pSegments;        /* Blob handle open on %_segments table */
 142
 143   /* The following hash table is used to buffer pending index updates during
 144   ** transactions. Variable nPendingData estimates the memory size of the
 145   ** pending data, including hash table overhead, but not malloc overhead.
 146   ** When nPendingData exceeds nMaxPendingData, the buffer is flushed
 147   ** automatically. Variable iPrevDocid is the docid of the most recently
 148   ** inserted record.
 149   */
 150   int nMaxPendingData;
 151   int nPendingData;
 152   sqlite_int64 iPrevDocid;
 153   Fts3Hash pendingTerms;
 154 };
 155
 156 /*
 157 ** When the core wants to read from the virtual table, it creates a
 158 ** virtual table cursor (an instance of the following structure) using
 159 ** the xOpen method. Cursors are destroyed using the xClose method.
 160 */
 161 struct Fts3Cursor {
 162   sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
 163   i16 eSearch;                    /* Search strategy (see below) */
 164   u8 isEof;                       /* True if at End Of Results */
 165   u8 isRequireSeek;               /* True if must seek pStmt to %_content row */
 166   sqlite3_stmt *pStmt;            /* Prepared statement in use by the cursor */
 167   Fts3Expr *pExpr;                /* Parsed MATCH query string */
 168   int nPhrase;                    /* Number of matchable phrases in query */
 169   Fts3DeferredToken *pDeferred;   /* Deferred search tokens, if any */
 170   sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
 171   char *pNextId;                  /* Pointer into the body of aDoclist */
 172   char *aDoclist;                 /* List of docids for full-text queries */
 173   int nDoclist;                   /* Size of buffer at aDoclist */
 174   int eEvalmode;                  /* An FTS3_EVAL_XX constant */
 175   int nRowAvg;                    /* Average size of database rows, in pages */
 176
 177   int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
 178   u32 *aMatchinfo;                /* Information about most recent match */
 179   int nMatchinfo;                 /* Number of elements in aMatchinfo[] */
 180   char *zMatchinfo;               /* Matchinfo specification */
 181 };
 182
 183 #define FTS3_EVAL_FILTER    0
 184 #define FTS3_EVAL_NEXT      1
 185 #define FTS3_EVAL_MATCHINFO 2
 186
 187 /*
 188 ** The Fts3Cursor.eSearch member is always set to one of the following.
 189 ** Actualy, Fts3Cursor.eSearch can be greater than or equal to
 190 ** FTS3_FULLTEXT_SEARCH.  If so, then Fts3Cursor.eSearch - 2 is the index
 191 ** of the column to be searched.  For example, in
 192 **
 193 **     CREATE VIRTUAL TABLE ex1 USING fts3(a,b,c,d);
 194 **     SELECT docid FROM ex1 WHERE b MATCH 'one two three';
 195 **
 196 ** Because the LHS of the MATCH operator is 2nd column "b",
 197 ** Fts3Cursor.eSearch will be set to FTS3_FULLTEXT_SEARCH+1.  (+0 for a,
 198 ** +1 for b, +2 for c, +3 for d.)  If the LHS of MATCH were "ex1"
 199 ** indicating that all columns should be searched,
 200 ** then eSearch would be set to FTS3_FULLTEXT_SEARCH+4.
 201 */
 202 #define FTS3_FULLSCAN_SEARCH 0    /* Linear scan of %_content table */
 203 #define FTS3_DOCID_SEARCH    1    /* Lookup by rowid on %_content table */
 204 #define FTS3_FULLTEXT_SEARCH 2    /* Full-text index search */
 205
 206 /*
 207 ** A "phrase" is a sequence of one or more tokens that must match in
 208 ** sequence.  A single token is the base case and the most common case.
 209 ** For a sequence of tokens contained in double-quotes (i.e. "one two three")
 210 ** nToken will be the number of tokens in the string.
 211 **
 212 ** The nDocMatch and nMatch variables contain data that may be used by the
 213 ** matchinfo() function. They are populated when the full-text index is
 214 ** queried for hits on the phrase. If one or more tokens in the phrase
 215 ** are deferred, the nDocMatch and nMatch variables are populated based
 216 ** on the assumption that the
 217 */
 218 struct Fts3PhraseToken {
 219   char *z;                        /* Text of the token */
 220   int n;                          /* Number of bytes in buffer z */
 221   int isPrefix;                   /* True if token ends with a "*" character */
 222   int bFulltext;                  /* True if full-text index was used */
 223   Fts3SegReaderCursor *pSegcsr;   /* Segment-reader for this token */
 224   Fts3DeferredToken *pDeferred;   /* Deferred token object for this token */
 225 };
 226
 227 struct Fts3Phrase {
 228   /* Variables populated by fts3_expr.c when parsing a MATCH expression */
 229   int nToken;                /* Number of tokens in the phrase */
 230   int iColumn;               /* Index of column this phrase must match */
 231   int isNot;                 /* Phrase prefixed by unary not (-) operator */
 232   Fts3PhraseToken aToken[1]; /* One entry for each token in the phrase */
 233 };
 234
 235 /*
 236 ** A tree of these objects forms the RHS of a MATCH operator.
 237 **
 238 ** If Fts3Expr.eType is either FTSQUERY_NEAR or FTSQUERY_PHRASE and isLoaded
 239 ** is true, then aDoclist points to a malloced buffer, size nDoclist bytes,
 240 ** containing the results of the NEAR or phrase query in FTS3 doclist
 241 ** format. As usual, the initial "Length" field found in doclists stored
 242 ** on disk is omitted from this buffer.
 243 **
 244 ** Variable pCurrent always points to the start of a docid field within
 245 ** aDoclist. Since the doclist is usually scanned in docid order, this can
 246 ** be used to accelerate seeking to the required docid within the doclist.
 247 */
 248 struct Fts3Expr {
 249   int eType;                 /* One of the FTSQUERY_XXX values defined below */
 250   int nNear;                 /* Valid if eType==FTSQUERY_NEAR */
 251   Fts3Expr *pParent;         /* pParent->pLeft==this or pParent->pRight==this */
 252   Fts3Expr *pLeft;           /* Left operand */
 253   Fts3Expr *pRight;          /* Right operand */
 254   Fts3Phrase *pPhrase;       /* Valid if eType==FTSQUERY_PHRASE */
 255
 256   int isLoaded;              /* True if aDoclist/nDoclist are initialized. */
 257   char *aDoclist;            /* Buffer containing doclist */
 258   int nDoclist;              /* Size of aDoclist in bytes */
 259
 260   sqlite3_int64 iCurrent;
 261   char *pCurrent;
 262 };
 263
 264 /*
 265 ** Candidate values for Fts3Query.eType. Note that the order of the first
 266 ** four values is in order of precedence when parsing expressions. For
 267 ** example, the following:
 268 **
 269 **   "a OR b AND c NOT d NEAR e"
 270 **
 271 ** is equivalent to:
 272 **
 273 **   "a OR (b AND (c NOT (d NEAR e)))"
 274 */
 275 #define FTSQUERY_NEAR   1
 276 #define FTSQUERY_NOT    2
 277 #define FTSQUERY_AND    3
 278 #define FTSQUERY_OR     4
 279 #define FTSQUERY_PHRASE 5
 280
 281
 282 /* fts3_write.c */
 283 int sqlite3Fts3UpdateMethod(sqlite3_vtab*,int,sqlite3_value**,sqlite3_int64*);
 284 int sqlite3Fts3PendingTermsFlush(Fts3Table *);
 285 void sqlite3Fts3PendingTermsClear(Fts3Table *);
 286 int sqlite3Fts3Optimize(Fts3Table *);
 287 int sqlite3Fts3SegReaderNew(int, sqlite3_int64,
 288   sqlite3_int64, sqlite3_int64, const char *, int, Fts3SegReader**);
 289 int sqlite3Fts3SegReaderPending(Fts3Table*,const char*,int,int,Fts3SegReader**);
 290 void sqlite3Fts3SegReaderFree(Fts3SegReader *);
 291 int sqlite3Fts3SegReaderCost(Fts3Cursor *, Fts3SegReader *, int *);
 292 int sqlite3Fts3AllSegdirs(Fts3Table*, int, sqlite3_stmt **);
 293 int sqlite3Fts3ReadLock(Fts3Table *);
 294 int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char **, int*);
 295
 296 int sqlite3Fts3SelectDoctotal(Fts3Table *, sqlite3_stmt **);
 297 int sqlite3Fts3SelectDocsize(Fts3Table *, sqlite3_int64, sqlite3_stmt **);
 298
 299 void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *);
 300 int sqlite3Fts3DeferToken(Fts3Cursor *, Fts3PhraseToken *, int);
 301 int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *);
 302 void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *);
 303 char *sqlite3Fts3DeferredDoclist(Fts3DeferredToken *, int *);
 304 void sqlite3Fts3SegmentsClose(Fts3Table *);
 305
 306 #define FTS3_SEGCURSOR_PENDING -1
 307 #define FTS3_SEGCURSOR_ALL     -2
 308
 309 int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3SegReaderCursor*, Fts3SegFilter*);
 310 int sqlite3Fts3SegReaderStep(Fts3Table *, Fts3SegReaderCursor *);
 311 void sqlite3Fts3SegReaderFinish(Fts3SegReaderCursor *);
 312 int sqlite3Fts3SegReaderCursor(
 313     Fts3Table *, int, const char *, int, int, int, Fts3SegReaderCursor *);
 314
 315 /* Flags allowed as part of the 4th argument to SegmentReaderIterate() */
 316 #define FTS3_SEGMENT_REQUIRE_POS   0x00000001
 317 #define FTS3_SEGMENT_IGNORE_EMPTY  0x00000002
 318 #define FTS3_SEGMENT_COLUMN_FILTER 0x00000004
 319 #define FTS3_SEGMENT_PREFIX        0x00000008
 320 #define FTS3_SEGMENT_SCAN          0x00000010
 321
 322 /* Type passed as 4th argument to SegmentReaderIterate() */
 323 struct Fts3SegFilter {
 324   const char *zTerm;
 325   int nTerm;
 326   int iCol;
 327   int flags;
 328 };
 329
 330 struct Fts3SegReaderCursor {
 331   /* Used internally by sqlite3Fts3SegReaderXXX() calls */
 332   Fts3SegReader **apSegment;      /* Array of Fts3SegReader objects */
 333   int nSegment;                   /* Size of apSegment array */
 334   int nAdvance;                   /* How many seg-readers to advance */
 335   Fts3SegFilter *pFilter;         /* Pointer to filter object */
 336   char *aBuffer;                  /* Buffer to merge doclists in */
 337   int nBuffer;                    /* Allocated size of aBuffer[] in bytes */
 338
 339   /* Cost of running this iterator. Used by fts3.c only. */
 340   int nCost;
 341
 342   /* Output values. Valid only after Fts3SegReaderStep() returns SQLITE_ROW. */
 343   char *zTerm;                    /* Pointer to term buffer */
 344   int nTerm;                      /* Size of zTerm in bytes */
 345   char *aDoclist;                 /* Pointer to doclist buffer */
 346   int nDoclist;                   /* Size of aDoclist[] in bytes */
 347 };
 348
 349 /* fts3.c */
 350 int sqlite3Fts3PutVarint(char *, sqlite3_int64);
 351 int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
 352 int sqlite3Fts3GetVarint32(const char *, int *);
 353 int sqlite3Fts3VarintLen(sqlite3_uint64);
 354 void sqlite3Fts3Dequote(char *);
 355
 356 char *sqlite3Fts3FindPositions(Fts3Expr *, sqlite3_int64, int);
 357 int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *, Fts3Expr *);
 358 int sqlite3Fts3ExprLoadFtDoclist(Fts3Cursor *, Fts3Expr *, char **, int *);
 359 int sqlite3Fts3ExprNearTrim(Fts3Expr *, Fts3Expr *, int);
 360
 361 /* fts3_tokenizer.c */
 362 const char *sqlite3Fts3NextToken(const char *, int *);
 363 int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
 364 int sqlite3Fts3InitTokenizer(Fts3Hash *pHash, const char *,
 365     sqlite3_tokenizer **, char **
 366 );
 367 int sqlite3Fts3IsIdChar(char);
 368
 369 /* fts3_snippet.c */
 370 void sqlite3Fts3Offsets(sqlite3_context*, Fts3Cursor*);
 371 void sqlite3Fts3Snippet(sqlite3_context *, Fts3Cursor *, const char *,
 372   const char *, const char *, int, int
 373 );
 374 void sqlite3Fts3Matchinfo(sqlite3_context *, Fts3Cursor *, const char *);
 375
 376 /* fts3_expr.c */
 377 int sqlite3Fts3ExprParse(sqlite3_tokenizer *,
 378   char **, int, int, const char *, int, Fts3Expr **
 379 );
 380 void sqlite3Fts3ExprFree(Fts3Expr *);
 381 #ifdef SQLITE_TEST
 382 int sqlite3Fts3ExprInitTestInterface(sqlite3 *db);
 383 #endif
 384
 385 /* fts3_aux.c */
 386 int sqlite3Fts3InitAux(sqlite3 *db);
 387
 388 #endif /* _FTSINT_H */