Import SQLite 3.10.2.

third_party/sqlite/src/ext/rtree/rtree.c

 /*
 ** 2001 September 15
 **
 ** The author disclaims copyright to this source code.  In place of
 ** a legal notice, here is a blessing:
 **
 **    May you do good and not evil.
 **    May you find forgiveness for yourself and forgive others.
 **    May you share freely, never taking more than you give.
 **
@@ skipping 333 matching lines @@
 /*
 ** An instance of this structure (in the form of a BLOB) is returned by
 ** the SQL functions that sqlite3_rtree_geometry_callback() and
 ** sqlite3_rtree_query_callback() create, and is read as the right-hand
 ** operand to the MATCH operator of an R-Tree.
 */
 struct RtreeMatchArg {
   u32 magic;                  /* Always RTREE_GEOMETRY_MAGIC */
   RtreeGeomCallback cb;       /* Info about the callback functions */
   int nParam;                 /* Number of parameters to the SQL function */
+  sqlite3_value **apSqlParam; /* Original SQL parameter values */
   RtreeDValue aParam[1];      /* Values for parameters to the SQL function */
 };
 
 #ifndef MAX
 # define MAX(x,y) ((x) < (y) ? (y) : (x))
 #endif
 #ifndef MIN
 # define MIN(x,y) ((x) > (y) ? (y) : (x))
 #endif
 
 /*
 ** Functions to deserialize a 16 bit integer, 32 bit real number and
 ** 64 bit integer. The deserialized value is returned.
 */
 static int readInt16(u8 *p){
   return (p[0]<<8) + p[1];
 }
 static void readCoord(u8 *p, RtreeCoord *pCoord){
-  u32 i = (
+  pCoord->u = (
     (((u32)p[0]) << 24) + 
     (((u32)p[1]) << 16) + 
     (((u32)p[2]) <<  8) + 
     (((u32)p[3]) <<  0)
   );
-  *(u32 *)pCoord = i;
 }
 static i64 readInt64(u8 *p){
   return (
     (((i64)p[0]) << 56) + 
     (((i64)p[1]) << 48) + 
     (((i64)p[2]) << 40) + 
     (((i64)p[3]) << 32) + 
     (((i64)p[4]) << 24) + 
     (((i64)p[5]) << 16) + 
     (((i64)p[6]) <<  8) + 
     (((i64)p[7]) <<  0)
   );
 }
 
 /*
 ** Functions to serialize a 16 bit integer, 32 bit real number and
 ** 64 bit integer. The value returned is the number of bytes written
 ** to the argument buffer (always 2, 4 and 8 respectively).
 */
 static int writeInt16(u8 *p, int i){
   p[0] = (i>> 8)&0xFF;
   p[1] = (i>> 0)&0xFF;
   return 2;
 }
 static int writeCoord(u8 *p, RtreeCoord *pCoord){
   u32 i;
   assert( sizeof(RtreeCoord)==4 );
   assert( sizeof(u32)==4 );
-  i = *(u32 *)pCoord;
+  i = pCoord->u;
   p[0] = (i>>24)&0xFF;
   p[1] = (i>>16)&0xFF;
   p[2] = (i>> 8)&0xFF;
   p[3] = (i>> 0)&0xFF;
   return 4;
 }
 static int writeInt64(u8 *p, i64 i){
   p[0] = (i>>56)&0xFF;
   p[1] = (i>>48)&0xFF;
   p[2] = (i>>40)&0xFF;
@@ skipping 310 matching lines @@
 ** Deserialize cell iCell of node pNode. Populate the structure pointed
 ** to by pCell with the results.
 */
 static void nodeGetCell(
   Rtree *pRtree,               /* The overall R-Tree */
   RtreeNode *pNode,            /* The node containing the cell to be read */
   int iCell,                   /* Index of the cell within the node */
   RtreeCell *pCell             /* OUT: Write the cell contents here */
 ){
   u8 *pData;
-  u8 *pEnd;
   RtreeCoord *pCoord;
+  int ii;
   pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
   pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
-  pEnd = pData + pRtree->nDim*8;
   pCoord = pCell->aCoord;
-  for(; pData<pEnd; pData+=4, pCoord++){
-    readCoord(pData, pCoord);
+  for(ii=0; ii<pRtree->nDim*2; ii++){
+    readCoord(&pData[ii*4], &pCoord[ii]);
   }
 }
 
 
 /* Forward declaration for the function that does the work of
 ** the virtual table module xCreate() and xConnect() methods.
 */
 static int rtreeInit(
   sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int
 );
@@ skipping 419 matching lines @@
     int nNew = pCur->nPointAlloc*2 + 8;
     pNew = sqlite3_realloc(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
     if( pNew==0 ) return 0;
     pCur->aPoint = pNew;
     pCur->nPointAlloc = nNew;
   }
   i = pCur->nPoint++;
   pNew = pCur->aPoint + i;
   pNew->rScore = rScore;
   pNew->iLevel = iLevel;
-  assert( iLevel>=0 && iLevel<=RTREE_MAX_DEPTH );
+  assert( iLevel<=RTREE_MAX_DEPTH );
   while( i>0 ){
     RtreeSearchPoint *pParent;
     j = (i-1)/2;
     pParent = pCur->aPoint + j;
     if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
     rtreeSearchPointSwap(pCur, j, i);
     i = j;
     pNew = pParent;
   }
   return pNew;
@@ skipping 281 matching lines @@
   RtreeMatchArg *pBlob;              /* BLOB returned by geometry function */
   sqlite3_rtree_query_info *pInfo;   /* Callback information */
   int nBlob;                         /* Size of the geometry function blob */
   int nExpected;                     /* Expected size of the BLOB */
 
   /* Check that value is actually a blob. */
   if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
 
   /* Check that the blob is roughly the right size. */
   nBlob = sqlite3_value_bytes(pValue);
-  if( nBlob<(int)sizeof(RtreeMatchArg) 
-   || ((nBlob-sizeof(RtreeMatchArg))%sizeof(RtreeDValue))!=0
-  ){
+  if( nBlob<(int)sizeof(RtreeMatchArg) ){
     return SQLITE_ERROR;
   }
 
   pInfo = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pInfo)+nBlob );
   if( !pInfo ) return SQLITE_NOMEM;
   memset(pInfo, 0, sizeof(*pInfo));
   pBlob = (RtreeMatchArg*)&pInfo[1];
 
   memcpy(pBlob, sqlite3_value_blob(pValue), nBlob);
   nExpected = (int)(sizeof(RtreeMatchArg) +
+                    pBlob->nParam*sizeof(sqlite3_value*) +
                     (pBlob->nParam-1)*sizeof(RtreeDValue));
   if( pBlob->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=nExpected ){
     sqlite3_free(pInfo);
     return SQLITE_ERROR;
   }
   pInfo->pContext = pBlob->cb.pContext;
   pInfo->nParam = pBlob->nParam;
   pInfo->aParam = pBlob->aParam;
+  pInfo->apSqlParam = pBlob->apSqlParam;
 
   if( pBlob->cb.xGeom ){
     pCons->u.xGeom = pBlob->cb.xGeom;
   }else{
     pCons->op = RTREE_QUERY;
     pCons->u.xQueryFunc = pBlob->cb.xQueryFunc;
   }
   pCons->pInfo = pInfo;
   return SQLITE_OK;
 }
@@ skipping 146 matching lines @@
 **   ----------------------
 **
 ** The second of each pair of bytes identifies the coordinate column
 ** to which the constraint applies. The leftmost coordinate column
 ** is 'a', the second from the left 'b' etc.
 */
 static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
   Rtree *pRtree = (Rtree*)tab;
   int rc = SQLITE_OK;
   int ii;
+  int bMatch = 0;                 /* True if there exists a MATCH constraint */
   i64 nRow;                       /* Estimated rows returned by this scan */
 
   int iIdx = 0;
   char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
   memset(zIdxStr, 0, sizeof(zIdxStr));
 
+  /* Check if there exists a MATCH constraint - even an unusable one. If there
+  ** is, do not consider the lookup-by-rowid plan as using such a plan would
+  ** require the VDBE to evaluate the MATCH constraint, which is not currently
+  ** possible. */
+  for(ii=0; ii<pIdxInfo->nConstraint; ii++){
+    if( pIdxInfo->aConstraint[ii].op==SQLITE_INDEX_CONSTRAINT_MATCH ){
+      bMatch = 1;
+    }
+  }
+
   assert( pIdxInfo->idxStr==0 );
   for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
     struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
 
-    if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
+    if( bMatch==0 && p->usable 
+     && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ 
+    ){
       /* We have an equality constraint on the rowid. Use strategy 1. */
       int jj;
       for(jj=0; jj<ii; jj++){
         pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
         pIdxInfo->aConstraintUsage[jj].omit = 0;
       }
       pIdxInfo->idxNum = 1;
       pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
       pIdxInfo->aConstraintUsage[jj].omit = 1;
 
@@ skipping 1104 matching lines @@
   sqlite_int64 *pRowid
 ){
   Rtree *pRtree = (Rtree *)pVtab;
   int rc = SQLITE_OK;
   RtreeCell cell;                 /* New cell to insert if nData>1 */
   int bHaveRowid = 0;             /* Set to 1 after new rowid is determined */
 
   rtreeReference(pRtree);
   assert(nData>=1);
 
+  cell.iRowid = 0;  /* Used only to suppress a compiler warning */
+
   /* Constraint handling. A write operation on an r-tree table may return
   ** SQLITE_CONSTRAINT for two reasons:
   **
   **   1. A duplicate rowid value, or
   **   2. The supplied data violates the "x2>=x1" constraint.
   **
   ** In the first case, if the conflict-handling mode is REPLACE, then
   ** the conflicting row can be removed before proceeding. In the second
   ** case, SQLITE_CONSTRAINT must be returned regardless of the
   ** conflict-handling mode specified by the user.
   */
   if( nData>1 ){
     int ii;
 
-    /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
-    assert( nData==(pRtree->nDim*2 + 3) );
+    /* Populate the cell.aCoord[] array. The first coordinate is azData[3].
+    **
+    ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
+    ** with "column" that are interpreted as table constraints.
+    ** Example:  CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
+    ** This problem was discovered after years of use, so we silently ignore
+    ** these kinds of misdeclared tables to avoid breaking any legacy.
+    */
+    assert( nData<=(pRtree->nDim*2 + 3) );
+
 #ifndef SQLITE_RTREE_INT_ONLY
     if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
-      for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+      for(ii=0; ii<nData-4; ii+=2){
         cell.aCoord[ii].f = rtreeValueDown(azData[ii+3]);
         cell.aCoord[ii+1].f = rtreeValueUp(azData[ii+4]);
         if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
           rc = SQLITE_CONSTRAINT;
           goto constraint;
         }
       }
     }else
 #endif
     {
-      for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+      for(ii=0; ii<nData-4; ii+=2){
         cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
         cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
         if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
           rc = SQLITE_CONSTRAINT;
           goto constraint;
         }
       }
     }
 
     /* If a rowid value was supplied, check if it is already present in 
@@ skipping 509 matching lines @@
 ** destructor for an RtreeGeomCallback objecct.  This routine is called when
 ** the corresponding SQL function is deleted.
 */
 static void rtreeFreeCallback(void *p){
   RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p;
   if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext);
   sqlite3_free(p);
 }
 
 /*
+** This routine frees the BLOB that is returned by geomCallback().
+*/
+static void rtreeMatchArgFree(void *pArg){
+  int i;
+  RtreeMatchArg *p = (RtreeMatchArg*)pArg;
+  for(i=0; i<p->nParam; i++){
+    sqlite3_value_free(p->apSqlParam[i]);
+  }
+  sqlite3_free(p);
+}
+
+/*
 ** Each call to sqlite3_rtree_geometry_callback() or
 ** sqlite3_rtree_query_callback() creates an ordinary SQLite
 ** scalar function that is implemented by this routine.
 **
 ** All this function does is construct an RtreeMatchArg object that
 ** contains the geometry-checking callback routines and a list of
 ** parameters to this function, then return that RtreeMatchArg object
 ** as a BLOB.
 **
 ** The R-Tree MATCH operator will read the returned BLOB, deserialize
 ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
 ** out which elements of the R-Tree should be returned by the query.
 */
 static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
   RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
   RtreeMatchArg *pBlob;
   int nBlob;
+  int memErr = 0;
 
-  nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue);
+  nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue)
+           + nArg*sizeof(sqlite3_value*);
   pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
   if( !pBlob ){
     sqlite3_result_error_nomem(ctx);
   }else{
     int i;
     pBlob->magic = RTREE_GEOMETRY_MAGIC;
     pBlob->cb = pGeomCtx[0];
+    pBlob->apSqlParam = (sqlite3_value**)&pBlob->aParam[nArg];
     pBlob->nParam = nArg;
     for(i=0; i<nArg; i++){
+      pBlob->apSqlParam[i] = sqlite3_value_dup(aArg[i]);
+      if( pBlob->apSqlParam[i]==0 ) memErr = 1;
 #ifdef SQLITE_RTREE_INT_ONLY
       pBlob->aParam[i] = sqlite3_value_int64(aArg[i]);
 #else
       pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
 #endif
     }
-    sqlite3_result_blob(ctx, pBlob, nBlob, sqlite3_free);
+    if( memErr ){
+      sqlite3_result_error_nomem(ctx);
+      rtreeMatchArgFree(pBlob);
+    }else{
+      sqlite3_result_blob(ctx, pBlob, nBlob, rtreeMatchArgFree);
+    }
   }
 }
 
 /*
 ** Register a new geometry function for use with the r-tree MATCH operator.
 */
 int sqlite3_rtree_geometry_callback(
   sqlite3 *db,                  /* Register SQL function on this connection */
   const char *zGeom,            /* Name of the new SQL function */
   int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */
@@ skipping 46 matching lines @@
   sqlite3 *db,
   char **pzErrMsg,
   const sqlite3_api_routines *pApi
 ){
   SQLITE_EXTENSION_INIT2(pApi)
   return sqlite3RtreeInit(db);
 }
 #endif
 
 #endif