/ Check-in [dde0bb3e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add SQL scalar function rtreecheck() to the rtree module. For running checks to ensure the shadow tables used by an rtree virtual table are internally consistent.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-integrity-check
Files: files | file ages | folders
SHA3-256:dde0bb3eab1316c3247b1755594527ca70955aab4ad4907190731f7ec092b327
User & Date: dan 2017-10-25 16:38:34
Context
2017-10-25
18:00
Fix compilation issue (C99-ism) seen with MSVC. Closed-Leaf check-in: 61870b42 user: mistachkin tags: rtree-integrity-check
16:38
Add SQL scalar function rtreecheck() to the rtree module. For running checks to ensure the shadow tables used by an rtree virtual table are internally consistent. check-in: dde0bb3e user: dan tags: rtree-integrity-check
16:14
Do not reference the ioctl() system call in the unix backend unless it is actually needed by the Batch Atomic Write extension. This should allow the build to work on VxWorks. check-in: adfa7ed2 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
....
3603
3604
3605
3606
3607
3608
3609



































































































































































































































































































































































































































3610
3611
3612
3613
3614
3615
3616
....
3617
3618
3619
3620
3621
3622
3623



3624
3625
3626
3627
3628
3629
3630
#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
#define RTREE_MAXCELLS 51

/*
** The smallest possible node-size is (512-64)==448 bytes. And the largest
** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
** Therefore all non-root nodes must contain at least 3 entries. Since 
** 2^40 is greater than 2^64, an r-tree structure always has a depth of
** 40 or less.
*/
#define RTREE_MAX_DEPTH 40


/*
** Number of entries in the cursor RtreeNode cache.  The first entry is
................................................................................
  ){
    sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); 
  }else{
    u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
    sqlite3_result_int(ctx, readInt16(zBlob));
  }
}




































































































































































































































































































































































































































/*
** Register the r-tree module with database handle db. This creates the
** virtual table module "rtree" and the debugging/analysis scalar 
** function "rtreenode".
*/
int sqlite3RtreeInit(sqlite3 *db){
................................................................................
  const int utf8 = SQLITE_UTF8;
  int rc;

  rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
  }



  if( rc==SQLITE_OK ){
#ifdef SQLITE_RTREE_INT_ONLY
    void *c = (void *)RTREE_COORD_INT32;
#else
    void *c = (void *)RTREE_COORD_REAL32;
#endif
    rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>
>
>







205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
....
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
....
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
#define RTREE_MAXCELLS 51

/*
** The smallest possible node-size is (512-64)==448 bytes. And the largest
** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
** Therefore all non-root nodes must contain at least 3 entries. Since 
** 3^40 is greater than 2^64, an r-tree structure always has a depth of
** 40 or less.
*/
#define RTREE_MAX_DEPTH 40


/*
** Number of entries in the cursor RtreeNode cache.  The first entry is
................................................................................
  ){
    sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); 
  }else{
    u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
    sqlite3_result_int(ctx, readInt16(zBlob));
  }
}

/*
** Context object passed between the various routines that make up the
** implementation of integrity-check function rtreecheck().
*/
typedef struct RtreeCheck RtreeCheck;
struct RtreeCheck {
  sqlite3 *db;                    /* Database handle */
  const char *zDb;                /* Database containing rtree table */
  const char *zTab;               /* Name of rtree table */
  int bInt;                       /* True for rtree_i32 table */
  int nDim;                       /* Number of dimensions for this rtree tbl */
  sqlite3_stmt *pGetNode;         /* Statement used to retrieve nodes */
  sqlite3_stmt *aCheckMapping[2]; /* Statements to query %_parent/%_rowid */
  int nLeaf;                      /* Number of leaf cells in table */
  int nNonLeaf;                   /* Number of non-leaf cells in table */
  int rc;                         /* Return code */
  char *zReport;                  /* Message to report */
  int nErr;                       /* Number of lines in zReport */
};

#define RTREE_CHECK_MAX_ERROR 100

/*
** Reset SQL statement pStmt. If the sqlite3_reset() call returns an error,
** and RtreeCheck.rc==SQLITE_OK, set RtreeCheck.rc to the error code.
*/
static void rtreeCheckReset(RtreeCheck *pCheck, sqlite3_stmt *pStmt){
  int rc = sqlite3_reset(pStmt);
  if( pCheck->rc==SQLITE_OK ) pCheck->rc = rc;
}

/*
** The second and subsequent arguments to this function are a format string
** and printf style arguments. This function formats the string and attempts
** to compile it as an SQL statement.
**
** If successful, a pointer to the new SQL statement is returned. Otherwise,
** NULL is returned and an error code left in RtreeCheck.rc.
*/
static sqlite3_stmt *rtreeCheckPrepare(
  RtreeCheck *pCheck,             /* RtreeCheck object */
  const char *zFmt, ...           /* Format string and trailing args */
){
  va_list ap;
  va_start(ap, zFmt);
  char *z = sqlite3_vmprintf(zFmt, ap);
  sqlite3_stmt *pRet = 0;

  if( pCheck->rc==SQLITE_OK ){
    pCheck->rc = sqlite3_prepare_v2(pCheck->db, z, -1, &pRet, 0);
  }

  sqlite3_free(z);
  va_end(ap);
  return pRet;
}

/*
** The second and subsequent arguments to this function are a printf()
** style format string and arguments. This function formats the string and
** appends it to the report being accumuated in pCheck.
*/
static void rtreeCheckAppendMsg(RtreeCheck *pCheck, const char *zFmt, ...){
  va_list ap;
  va_start(ap, zFmt);
  if( pCheck->rc==SQLITE_OK && pCheck->nErr<RTREE_CHECK_MAX_ERROR ){
    char *z = sqlite3_vmprintf(zFmt, ap);
    if( z==0 ){
      pCheck->rc = SQLITE_NOMEM;
    }else{
      pCheck->zReport = sqlite3_mprintf("%z%s%z", 
          pCheck->zReport, (pCheck->zReport ? "\n" : ""), z
      );
      if( pCheck->zReport==0 ){
        pCheck->rc = SQLITE_NOMEM;
      }
    }
    pCheck->nErr++;
  }
  va_end(ap);
}

/*
** This function is a no-op if there is already an error code stored
** in the RtreeCheck object indicated by the first argument. NULL is
** returned in this case.
**
** Otherwise, the contents of rtree table node iNode are loaded from
** the database and copied into a buffer obtained from sqlite3_malloc().
** If no error occurs, a pointer to the buffer is returned and (*pnNode)
** is set to the size of the buffer in bytes.
**
** Or, if an error does occur, NULL is returned and an error code left
** in the RtreeCheck object. The final value of *pnNode is undefined in
** this case.
*/
static u8 *rtreeCheckGetNode(RtreeCheck *pCheck, i64 iNode, int *pnNode){
  u8 *pRet = 0;                   /* Return value */

  assert( pCheck->rc==SQLITE_OK );
  if( pCheck->pGetNode==0 ){
    pCheck->pGetNode = rtreeCheckPrepare(pCheck,
        "SELECT data FROM %Q.'%q_node' WHERE nodeno=?", 
        pCheck->zDb, pCheck->zTab
    );
  }

  if( pCheck->rc==SQLITE_OK ){
    sqlite3_bind_int64(pCheck->pGetNode, 1, iNode);
    if( sqlite3_step(pCheck->pGetNode)==SQLITE_ROW ){
      int nNode = sqlite3_column_bytes(pCheck->pGetNode, 0);
      const u8 *pNode = (const u8*)sqlite3_column_blob(pCheck->pGetNode, 0);
      pRet = sqlite3_malloc(nNode);
      if( pRet==0 ){
        pCheck->rc = SQLITE_NOMEM;
      }else{
        memcpy(pRet, pNode, nNode);
        *pnNode = nNode;
      }
    }
    rtreeCheckReset(pCheck, pCheck->pGetNode);
    if( pCheck->rc==SQLITE_OK && pRet==0 ){
      rtreeCheckAppendMsg(pCheck, "Node %lld missing from database", iNode);
    }
  }

  return pRet;
}

/*
** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
** (if bLeaf==1) table contains a specified entry. The schemas of the
** two tables are:
**
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
**
** In both cases, this function checks that there exists an entry with
** IPK value iKey and the second column set to iVal.
**
*/
static void rtreeCheckMapping(
  RtreeCheck *pCheck,             /* RtreeCheck object */
  int bLeaf,                      /* True for a leaf cell, false for interior */
  i64 iKey,                       /* Key for mapping */
  i64 iVal                        /* Expected value for mapping */
){
  int rc;
  sqlite3_stmt *pStmt;
  const char *azSql[2] = {
    "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?",
    "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?"
  };

  assert( bLeaf==0 || bLeaf==1 );
  if( pCheck->aCheckMapping[bLeaf]==0 ){
    pCheck->aCheckMapping[bLeaf] = rtreeCheckPrepare(pCheck,
        azSql[bLeaf], pCheck->zDb, pCheck->zTab
    );
  }
  if( pCheck->rc!=SQLITE_OK ) return;

  pStmt = pCheck->aCheckMapping[bLeaf];
  sqlite3_bind_int64(pStmt, 1, iKey);
  rc = sqlite3_step(pStmt);
  if( rc==SQLITE_DONE ){
    rtreeCheckAppendMsg(pCheck, "Mapping (%lld -> %lld) missing from %s table",
        iKey, iVal, (bLeaf ? "%_rowid" : "%_parent")
    );
  }else if( rc==SQLITE_ROW ){
    i64 ii = sqlite3_column_int64(pStmt, 0);
   if( ii!=iVal ){
      rtreeCheckAppendMsg(pCheck, 
          "Found (%lld -> %lld) in %s table, expected (%lld -> %lld)",
          iKey, ii, (bLeaf ? "%_rowid" : "%_parent"), iKey, iVal
      );
    }
  }
  rtreeCheckReset(pCheck, pStmt);
}

static void rtreeCheckCellCoord(
  RtreeCheck *pCheck, 
  i64 iNode,
  int iCell,
  u8 *pCell,                      /* Pointer to cell coordinates */
  u8 *pParent                     /* Pointer to parent coordinates */
){
  RtreeCoord c1, c2;
  RtreeCoord p1, p2;
  int i;

  for(i=0; i<pCheck->nDim; i++){
    readCoord(&pCell[4*2*i], &c1);
    readCoord(&pCell[4*(2*i + 1)], &c2);

    /* printf("%e, %e\n", c1.u.f, c2.u.f); */
    if( pCheck->bInt ? c1.i>c2.i : c1.f>c2.f ){
      rtreeCheckAppendMsg(pCheck, 
          "Dimension %d of cell %d on node %lld is corrupt", i, iCell, iNode
      );
    }

    if( pParent ){
      readCoord(&pParent[4*2*i], &p1);
      readCoord(&pParent[4*(2*i + 1)], &p2);

      if( (pCheck->bInt ? c1.i<p1.i : c1.f<p1.f) 
       || (pCheck->bInt ? c2.i>p2.i : c2.f>p2.f)
      ){
        rtreeCheckAppendMsg(pCheck, 
            "Dimension %d of cell %d on node %lld is corrupt relative to parent"
            , i, iCell, iNode
        );
      }
    }
  }
}

static void rtreeCheckNode(
  RtreeCheck *pCheck,
  int iDepth,                     /* Depth of iNode (0==leaf) */
  u8 *aParent,                    /* Buffer containing parent coords */
  i64 iNode                       /* Node to check */
){
  u8 *aNode = 0;
  int nNode = 0;

  assert( iNode==1 || aParent!=0 );
  assert( pCheck->nDim>0 );

  aNode = rtreeCheckGetNode(pCheck, iNode, &nNode);
  if( aNode ){
    if( nNode<4 ){
      rtreeCheckAppendMsg(pCheck, 
          "Node %lld is too small (%d bytes)", iNode, nNode
      );
    }else{
      int nCell;                  /* Number of cells on page */
      int i;                      /* Used to iterate through cells */
      if( aParent==0 ){
        iDepth = readInt16(aNode);
        if( iDepth>RTREE_MAX_DEPTH ){
          rtreeCheckAppendMsg(pCheck, "Rtree depth out of range (%d)", iDepth);
          sqlite3_free(aNode);
          return;
        }
      }
      nCell = readInt16(&aNode[2]);
      if( (4 + nCell*(8 + pCheck->nDim*2*4))>nNode ){
        rtreeCheckAppendMsg(pCheck, 
            "Node %lld is too small for cell count of %d (%d bytes)", 
            iNode, nCell, nNode
        );
      }
      for(i=0; i<nCell; i++){
        u8 *pCell = &aNode[4 + i*(8 + pCheck->nDim*2*4)];
        i64 iVal = readInt64(pCell);
        rtreeCheckCellCoord(pCheck, iNode, i, &pCell[8], aParent);

        if( iDepth>0 ){
          rtreeCheckMapping(pCheck, 0, iVal, iNode);
          rtreeCheckNode(pCheck, iDepth-1, &pCell[8], iVal);
          pCheck->nNonLeaf++;
        }else{
          rtreeCheckMapping(pCheck, 1, iVal, iNode);
          pCheck->nLeaf++;
        }
      }
    }
    sqlite3_free(aNode);
  }
}

static void rtreeCheckCount(
  RtreeCheck *pCheck, const char *zTbl, i64 nExpected
){
  if( pCheck->rc==SQLITE_OK ){
    sqlite3_stmt *pCount;
    pCount = rtreeCheckPrepare(pCheck, "SELECT count(*) FROM %Q.'%q%s'",
        pCheck->zDb, pCheck->zTab, zTbl
    );
    if( pCount ){
      if( sqlite3_step(pCount)==SQLITE_ROW ){
        i64 nActual = sqlite3_column_int64(pCount, 0);
        if( nActual!=nExpected ){
          rtreeCheckAppendMsg(pCheck, "Wrong number of entries in %%%s table"
              " - expected %lld, actual %lld" , zTbl, nExpected, nActual
          );
        }
      }
      pCheck->rc = sqlite3_finalize(pCount);
    }
  }
}

static int rtreeCheck(
  sqlite3 *db,                    /* Database handle to access db through */
  const char *zDb,                /* Name of db ("main", "temp" etc.) */
  const char *zTab,               /* Name of rtree table to check */
  char **pzReport                 /* OUT: sqlite3_malloc'd report text */
){
  RtreeCheck check;               /* Common context for various routines */
  sqlite3_stmt *pStmt = 0;        /* Used to find column count of rtree table */
  int bEnd = 0;                   /* True if transaction should be closed */

  /* Initialize the context object */
  memset(&check, 0, sizeof(check));
  check.db = db;
  check.zDb = zDb;
  check.zTab = zTab;

  /* If there is not already an open transaction, open one now. This is
  ** to ensure that the queries run as part of this integrity-check operate
  ** on a consistent snapshot.  */
  if( sqlite3_get_autocommit(db) ){
    check.rc = sqlite3_exec(db, "BEGIN", 0, 0, 0);
    bEnd = 1;
  }

  /* Find number of dimensions in the rtree table. */
  pStmt = rtreeCheckPrepare(&check, "SELECT * FROM %Q.%Q", zDb, zTab);
  if( pStmt ){
    int rc;
    check.nDim = (sqlite3_column_count(pStmt) - 1) / 2;
    if( check.nDim<1 ){
      rtreeCheckAppendMsg(&check, "Schema corrupt or not an rtree");
    }else if( SQLITE_ROW==sqlite3_step(pStmt) ){
      check.bInt = (sqlite3_column_type(pStmt, 1)==SQLITE_INTEGER);
    }
    rc = sqlite3_finalize(pStmt);
    if( rc!=SQLITE_CORRUPT ) check.rc = rc;
  }

  /* Do the actual integrity-check */
  if( check.rc==SQLITE_OK ){
    rtreeCheckNode(&check, 0, 0, 1);
  }
  rtreeCheckCount(&check, "_rowid", check.nLeaf);
  rtreeCheckCount(&check, "_parent", check.nNonLeaf);

  /* Finalize SQL statements used by the integrity-check */
  sqlite3_finalize(check.pGetNode);
  sqlite3_finalize(check.aCheckMapping[0]);
  sqlite3_finalize(check.aCheckMapping[1]);

  /* If one was opened, close the transaction */
  if( bEnd ){
    int rc = sqlite3_exec(db, "END", 0, 0, 0);
    if( check.rc==SQLITE_OK ) check.rc = rc;
  }
  *pzReport = check.zReport;
  return check.rc;
}

/*
** Usage:
**
**   rtreecheck(<rtree-table>);
**   rtreecheck(<database>, <rtree-table>);
**
** Invoking this SQL function runs an integrity-check on the named rtree
** table. The integrity-check verifies the following:
**
**   1. For each cell in the r-tree structure (%_node table), that:
**
**       a) for each dimension, (coord1 <= coord2).
**
**       b) unless the cell is on the root node, that the cell is bounded
**          by the parent cell on the parent node.
**
**       c) for leaf nodes, that there is an entry in the %_rowid 
**          table corresponding to the cell's rowid value that 
**          points to the correct node.
**
**       d) for cells on non-leaf nodes, that there is an entry in the 
**          %_parent table mapping from the cell's child node to the
**          node that it resides on.
**
**   2. That there are the same number of entries in the %_rowid table
**      as there are leaf cells in the r-tree structure, and that there
**      is a leaf cell that corresponds to each entry in the %_rowid table.
**
**   3. That there are the same number of entries in the %_parent table
**      as there are non-leaf cells in the r-tree structure, and that 
**      there is a non-leaf cell that corresponds to each entry in the 
**      %_parent table.
*/
static void rtreecheck(
  sqlite3_context *ctx, 
  int nArg, 
  sqlite3_value **apArg
){
  if( nArg!=1 && nArg!=2 ){
    sqlite3_result_error(ctx, 
        "wrong number of arguments to function rtreecheck()", -1
    );
  }else{
    int rc;
    char *zReport = 0;
    const char *zDb = (const char*)sqlite3_value_text(apArg[0]);
    const char *zTab;
    if( nArg==1 ){
      zTab = zDb;
      zDb = "main";
    }else{
      zTab = (const char*)sqlite3_value_text(apArg[1]);
    }
    rc = rtreeCheck(sqlite3_context_db_handle(ctx), zDb, zTab, &zReport);
    if( rc==SQLITE_OK ){
      sqlite3_result_text(ctx, zReport ? zReport : "ok", -1, SQLITE_TRANSIENT);
    }else{
      sqlite3_result_error_code(ctx, rc);
    }
    sqlite3_free(zReport);
  }
}


/*
** Register the r-tree module with database handle db. This creates the
** virtual table module "rtree" and the debugging/analysis scalar 
** function "rtreenode".
*/
int sqlite3RtreeInit(sqlite3 *db){
................................................................................
  const int utf8 = SQLITE_UTF8;
  int rc;

  rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
  }
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "rtreecheck", -1, utf8, 0,rtreecheck, 0,0);
  }
  if( rc==SQLITE_OK ){
#ifdef SQLITE_RTREE_INT_ONLY
    void *c = (void *)RTREE_COORD_INT32;
#else
    void *c = (void *)RTREE_COORD_REAL32;
#endif
    rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);

Changes to ext/rtree/rtree1.test.

515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
    set res(1) {1 {UNIQUE constraint failed: t1.idx}}
    set res(2) {1 {rtree constraint failed: t1.(x1<=x2)}}

    do_catchsql_test $testname.1 $sql $res($error)
    do_test $testname.2 [list sql_uses_stmt db $sql] $uses
    do_execsql_test $testname.3 { SELECT * FROM t1 ORDER BY idx } $data

    do_test $testname.4 { rtree_check db t1 } 0
    db close
  }
}

#-------------------------------------------------------------------------
# Test that bug [d2889096e7bdeac6d] has been fixed.
#







|







515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
    set res(1) {1 {UNIQUE constraint failed: t1.idx}}
    set res(2) {1 {rtree constraint failed: t1.(x1<=x2)}}

    do_catchsql_test $testname.1 $sql $res($error)
    do_test $testname.2 [list sql_uses_stmt db $sql] $uses
    do_execsql_test $testname.3 { SELECT * FROM t1 ORDER BY idx } $data

    do_rtree_integrity_test $testname.4 t1
    db close
  }
}

#-------------------------------------------------------------------------
# Test that bug [d2889096e7bdeac6d] has been fixed.
#

Changes to ext/rtree/rtree2.test.

77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
...
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
      if {$rc != 1} {
        puts $t1
        puts $t2
      }
      set rc
    } {1}
  
    do_test rtree2-$module.$nDim.3 {
      rtree_check db t1
    } 0
  
    set OPS [list < > <= >= =]
    for {set ii 0} {$ii < $::NSELECT} {incr ii} {
      do_test rtree2-$module.$nDim.4.$ii.1 {
        set where [list]
        foreach look_three_dots! {. . .} {
          set colidx [expr int(rand()*($nDim*2+1))-1]
................................................................................
        set rc [expr {$t1 eq $t2}]
        if {$rc != 1} {
          puts $t1
          puts $t2
        }
        set rc
      } {1}
      do_test rtree2-$module.$nDim.5.$ii.2 {
        rtree_check db t1
      } {0}
    }
  
    do_test rtree2-$module.$nDim.6 {
      execsql {
        DROP TABLE t1;
        DROP TABLE t2;
      }
    } {}
  }
}

finish_test







|
<
<







 







|
<
<












77
78
79
80
81
82
83
84


85
86
87
88
89
90
91
...
127
128
129
130
131
132
133
134


135
136
137
138
139
140
141
142
143
144
145
146
      if {$rc != 1} {
        puts $t1
        puts $t2
      }
      set rc
    } {1}
  
    do_rtree_integrity_test rtree2-$module.$nDim.3 t1


  
    set OPS [list < > <= >= =]
    for {set ii 0} {$ii < $::NSELECT} {incr ii} {
      do_test rtree2-$module.$nDim.4.$ii.1 {
        set where [list]
        foreach look_three_dots! {. . .} {
          set colidx [expr int(rand()*($nDim*2+1))-1]
................................................................................
        set rc [expr {$t1 eq $t2}]
        if {$rc != 1} {
          puts $t1
          puts $t2
        }
        set rc
      } {1}
      do_rtree_integrity_test rtree2-$module.$nDim.5.$ii.2 t1


    }
  
    do_test rtree2-$module.$nDim.6 {
      execsql {
        DROP TABLE t1;
        DROP TABLE t2;
      }
    } {}
  }
}

finish_test

Changes to ext/rtree/rtree4.test.

11
12
13
14
15
16
17

18
19
20
21
22
23
24
...
242
243
244
245
246
247
248

249
250
251
#
# Randomized test cases for the rtree extension.
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

................................................................................
    }
    set where "WHERE [join [scramble $where] { AND }]"
    do_test rtree4-$nDim.2.$i.8 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
  }


}

finish_test







>







 







>



11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
243
244
245
246
247
248
249
250
251
252
253
#
# Randomized test cases for the rtree extension.
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

................................................................................
    }
    set where "WHERE [join [scramble $where] { AND }]"
    do_test rtree4-$nDim.2.$i.8 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
  }

  do_rtree_integrity_test rtree4-$nDim.3 rx
}

finish_test

Changes to ext/rtree/rtree5.test.

12
13
14
15
16
17
18

19
20
21
22
23
24
25
..
72
73
74
75
76
77
78

79
80
# The focus of this file is testing the r-tree extension when it is
# configured to store values as 32 bit integers.
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

................................................................................
do_test rtree5-1.13 { 
  execsql { 
    SELECT * FROM t1 WHERE 
        x1=2147483643 AND x2=2147483647 AND 
        y1=-2147483648 AND y2=-2147483643
  }
} {2 2147483643 2147483647 -2147483648 -2147483643}


finish_test







>







 







>


12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
..
73
74
75
76
77
78
79
80
81
82
# The focus of this file is testing the r-tree extension when it is
# configured to store values as 32 bit integers.
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

................................................................................
do_test rtree5-1.13 { 
  execsql { 
    SELECT * FROM t1 WHERE 
        x1=2147483643 AND x2=2147483647 AND 
        y1=-2147483648 AND y2=-2147483643
  }
} {2 2147483643 2147483647 -2147483648 -2147483643}
do_rtree_integrity_test rtree5-1.14 t1

finish_test

Changes to ext/rtree/rtree7.test.

13
14
15
16
17
18
19

20
21
22
23
24
25
26
..
62
63
64
65
66
67
68
69


70
# database page-size is modified. At one point (3.6.22), this was causing
# malfunctions.
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl

ifcapable !rtree||!vacuum {
  finish_test
  return
}

................................................................................
do_test rtree7-1.5 {
  execsql_intout { 
    PRAGMA page_size = 512;
    VACUUM;
    SELECT sum(x1), sum(x2), sum(y1), sum(y2) FROM rt
  }
} {51 102 153 204}



finish_test







>







 








>
>

13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
..
63
64
65
66
67
68
69
70
71
72
73
# database page-size is modified. At one point (3.6.22), this was causing
# malfunctions.
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl

ifcapable !rtree||!vacuum {
  finish_test
  return
}

................................................................................
do_test rtree7-1.5 {
  execsql_intout { 
    PRAGMA page_size = 512;
    VACUUM;
    SELECT sum(x1), sum(x2), sum(y1), sum(y2) FROM rt
  }
} {51 102 153 204}

do_rtree_integrity_test rtree7-1.6 rt

finish_test

Changes to ext/rtree/rtree8.test.

10
11
12
13
14
15
16

17
18
19
20
21
22
23
..
60
61
62
63
64
65
66

67
68
69
70
71
72
73
...
154
155
156
157
158
159
160

161
162
163
164
165
166
167

168
169
170
#***********************************************************************
# 
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

#-------------------------------------------------------------------------
# The following block of tests - rtree8-1.* - feature reading and writing
# an r-tree table while there exist open cursors on it.
#
................................................................................
do_test rtree8-1.2.2 { nested_select 1 } {51}

# This test runs many SELECT queries simultaneously against a large 
# table, causing a collision in the hash-table used to store r-tree 
# nodes internally.
#
populate_t1 1500

do_execsql_test rtree8-1.3.1 { SELECT max(nodeno) FROM t1_node } {164}
do_test rtree8-1.3.2 {
  set rowids [execsql {SELECT min(rowid) FROM t1_rowid GROUP BY nodeno}]
  set stmt_list [list]
  foreach row $rowids {
    set stmt [sqlite3_prepare db "SELECT * FROM t1 WHERE id = $row" -1 tail]
    sqlite3_step $stmt
................................................................................
    execsql { INSERT INTO t2 VALUES($i, 100, 101) }
  }
  for {set i 100} {$i < 200} {incr i} {
    execsql { INSERT INTO t2 VALUES($i, 1000, 1001) }
  }
  execsql COMMIT
} {}

do_test rtree8-5.3 {
  execsql BEGIN
  for {set i 0} {$i < 200} {incr i} {
    execsql { DELETE FROM t2 WHERE id = $i }
  }
  execsql COMMIT
} {}



finish_test







>







 







>







 







>
|






>



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
..
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
...
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#***********************************************************************
# 
#

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

#-------------------------------------------------------------------------
# The following block of tests - rtree8-1.* - feature reading and writing
# an r-tree table while there exist open cursors on it.
#
................................................................................
do_test rtree8-1.2.2 { nested_select 1 } {51}

# This test runs many SELECT queries simultaneously against a large 
# table, causing a collision in the hash-table used to store r-tree 
# nodes internally.
#
populate_t1 1500
do_rtree_integrity_test rtree8-1.3.0 t1
do_execsql_test rtree8-1.3.1 { SELECT max(nodeno) FROM t1_node } {164}
do_test rtree8-1.3.2 {
  set rowids [execsql {SELECT min(rowid) FROM t1_rowid GROUP BY nodeno}]
  set stmt_list [list]
  foreach row $rowids {
    set stmt [sqlite3_prepare db "SELECT * FROM t1 WHERE id = $row" -1 tail]
    sqlite3_step $stmt
................................................................................
    execsql { INSERT INTO t2 VALUES($i, 100, 101) }
  }
  for {set i 100} {$i < 200} {incr i} {
    execsql { INSERT INTO t2 VALUES($i, 1000, 1001) }
  }
  execsql COMMIT
} {}
do_rtree_integrity_test rtree8-5.3 t2
do_test rtree8-5.4 {
  execsql BEGIN
  for {set i 0} {$i < 200} {incr i} {
    execsql { DELETE FROM t2 WHERE id = $i }
  }
  execsql COMMIT
} {}
do_rtree_integrity_test rtree8-5.5 t2


finish_test

Changes to ext/rtree/rtree9.test.

11
12
13
14
15
16
17

18
19
20
21
22
23
24
..
38
39
40
41
42
43
44

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

62
63
64
65
66
67
68
...
117
118
119
120
121
122
123

124
125
# This file contains tests for the r-tree module. Specifically, it tests
# that custom r-tree queries (geometry callbacks) work.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }
ifcapable rtree_int_only { finish_test; return }

register_cube_geom db

do_execsql_test rtree9-1.1 {
................................................................................

for {set i 0} {$i < 1000} {incr i} {
  set x [expr $i%10]
  set y [expr ($i/10)%10]
  set z [expr ($i/100)%10]
  execsql { INSERT INTO rt VALUES($i, $x, $x+1, $y, $y+1, $z, $z+1) }
}

do_execsql_test rtree9-2.1 {
  SELECT id FROM rt WHERE id MATCH cube(2.5, 2.5, 2.5, 1, 1, 1) ORDER BY id;
} {222 223 232 233 322 323 332 333}
do_execsql_test rtree9-2.2 {
  SELECT id FROM rt WHERE id MATCH cube(5.5, 5.5, 5.5, 1, 1, 1) ORDER BY id;
} {555 556 565 566 655 656 665 666}


do_execsql_test rtree9-3.1 {
  CREATE VIRTUAL TABLE rt32 USING rtree_i32(id, x1, x2, y1, y2, z1, z2);
} {} 
for {set i 0} {$i < 1000} {incr i} {
  set x [expr $i%10]
  set y [expr ($i/10)%10]
  set z [expr ($i/100)%10]
  execsql { INSERT INTO rt32 VALUES($i, $x, $x+1, $y, $y+1, $z, $z+1) }
}

do_execsql_test rtree9-3.2 {
  SELECT id FROM rt32 WHERE id MATCH cube(3, 3, 3, 1, 1, 1) ORDER BY id;
} {222 223 224 232 233 234 242 243 244 322 323 324 332 333 334 342 343 344 422 423 424 432 433 434 442 443 444}
do_execsql_test rtree9-3.3 {
  SELECT id FROM rt32 WHERE id MATCH cube(5.5, 5.5, 5.5, 1, 1, 1) ORDER BY id;
} {555 556 565 566 655 656 665 666}

................................................................................
  SELECT id FROM rt2 WHERE id MATCH circle(0.0, 0.0, 2.0);
} {1 2 3 4 13 14 15 16 17}

do_execsql_test rtree9-5.3 {
  UPDATE rt2 SET xmin=xmin+5, ymin=ymin+5, xmax=xmax+5, ymax=ymax+5;
  SELECT id FROM rt2 WHERE id MATCH circle(5.0, 5.0, 2.0);
} {1 2 3 4 13 14 15 16 17}


finish_test







>







 







>








|








>







 







>


11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
..
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
...
120
121
122
123
124
125
126
127
128
129
# This file contains tests for the r-tree module. Specifically, it tests
# that custom r-tree queries (geometry callbacks) work.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }
ifcapable rtree_int_only { finish_test; return }

register_cube_geom db

do_execsql_test rtree9-1.1 {
................................................................................

for {set i 0} {$i < 1000} {incr i} {
  set x [expr $i%10]
  set y [expr ($i/10)%10]
  set z [expr ($i/100)%10]
  execsql { INSERT INTO rt VALUES($i, $x, $x+1, $y, $y+1, $z, $z+1) }
}
do_rtree_integrity_test rtree9-2.0 rt
do_execsql_test rtree9-2.1 {
  SELECT id FROM rt WHERE id MATCH cube(2.5, 2.5, 2.5, 1, 1, 1) ORDER BY id;
} {222 223 232 233 322 323 332 333}
do_execsql_test rtree9-2.2 {
  SELECT id FROM rt WHERE id MATCH cube(5.5, 5.5, 5.5, 1, 1, 1) ORDER BY id;
} {555 556 565 566 655 656 665 666}


do_execsql_test rtree9-3.0 {
  CREATE VIRTUAL TABLE rt32 USING rtree_i32(id, x1, x2, y1, y2, z1, z2);
} {} 
for {set i 0} {$i < 1000} {incr i} {
  set x [expr $i%10]
  set y [expr ($i/10)%10]
  set z [expr ($i/100)%10]
  execsql { INSERT INTO rt32 VALUES($i, $x, $x+1, $y, $y+1, $z, $z+1) }
}
do_rtree_integrity_test rtree9-3.1 rt32
do_execsql_test rtree9-3.2 {
  SELECT id FROM rt32 WHERE id MATCH cube(3, 3, 3, 1, 1, 1) ORDER BY id;
} {222 223 224 232 233 234 242 243 244 322 323 324 332 333 334 342 343 344 422 423 424 432 433 434 442 443 444}
do_execsql_test rtree9-3.3 {
  SELECT id FROM rt32 WHERE id MATCH cube(5.5, 5.5, 5.5, 1, 1, 1) ORDER BY id;
} {555 556 565 566 655 656 665 666}

................................................................................
  SELECT id FROM rt2 WHERE id MATCH circle(0.0, 0.0, 2.0);
} {1 2 3 4 13 14 15 16 17}

do_execsql_test rtree9-5.3 {
  UPDATE rt2 SET xmin=xmin+5, ymin=ymin+5, xmax=xmax+5, ymax=ymax+5;
  SELECT id FROM rt2 WHERE id MATCH circle(5.0, 5.0, 2.0);
} {1 2 3 4 13 14 15 16 17}
do_rtree_integrity_test rtree9-5.4 rt2

finish_test

Changes to ext/rtree/rtreeA.test.

104
105
106
107
108
109
110






111
112
113
114
115
116
117
...
152
153
154
155
156
157
158




159
160
161
162
163
164
165
...
172
173
174
175
176
177
178






179
180
181
182
183
184
185
...
198
199
200
201
202
203
204




205
206
207
208
209
210
211
212
213
214
215
216
217




218
219
220
221
222
223
224
...
229
230
231
232
233
234
235
236
237

do_corruption_tests rtreeA-1.1 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
}







do_execsql_test  rtreeA-1.2.0 { DROP TABLE t1_node } {}
do_corruption_tests rtreeA-1.2 -error "database disk image is malformed" {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
}
................................................................................
do_test rtreeA-3.1.0.1 { set_tree_depth t1 } {1}
do_test rtreeA-3.1.0.2 { set_tree_depth t1 3 } {3}
do_corruption_tests rtreeA-3.1 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
}





do_test rtreeA-3.2.0 { set_tree_depth t1 1000 } {1000}
do_corruption_tests rtreeA-3.2 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
}
................................................................................
} {65535}
do_corruption_tests rtreeA-3.3 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
}







#-------------------------------------------------------------------------
# Set the "number of entries" field on some nodes incorrectly.
#
create_t1
populate_t1
do_test rtreeA-4.1.0 { 
  set_entry_count t1 1 4000
................................................................................
create_t1
populate_t1
do_execsql_test rtreeA-5.1.0 { DELETE FROM t1_parent } {}
do_corruption_tests rtreeA-5.1 {
  1   "DELETE FROM t1 WHERE rowid = 5"
  2   "DELETE FROM t1"
}





#-------------------------------------------------------------------------
# Add some bad entries to the %_parent table.
#
create_t1
populate_t1
do_execsql_test rtreeA-6.1.0 { 
  UPDATE t1_parent set parentnode = parentnode+1
} {}
do_corruption_tests rtreeA-6.1 {
  1   "DELETE FROM t1 WHERE rowid = 5"
  2   "UPDATE t1 SET x1=x1+1, x2=x2+1"
}





#-------------------------------------------------------------------------
# Truncated blobs in the _node table.
#
create_t1
populate_t1
sqlite3 db test.db
................................................................................
  SELECT * FROM t1 WHERE x1>0 AND x1<100 AND x2>0 AND x2<100;
} {1 {undersize RTree blobs in "t1_node"}}
do_test rtreeA-7.120 {
  sqlite3_extended_errcode db
} {SQLITE_CORRUPT_VTAB}



finish_test








>
>
>
>
>
>







 







>
>
>
>







 







>
>
>
>
>
>







 







>
>
>
>













>
>
>
>







 







<

>
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
...
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
...
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
...
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
...
253
254
255
256
257
258
259

260
261
do_corruption_tests rtreeA-1.1 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
}

do_execsql_test rtreeA-1.1.1 {
  SELECT rtreecheck('main', 't1')
} {{Node 1 missing from database
Wrong number of entries in %_rowid table - expected 0, actual 500
Wrong number of entries in %_parent table - expected 0, actual 23}}

do_execsql_test  rtreeA-1.2.0 { DROP TABLE t1_node } {}
do_corruption_tests rtreeA-1.2 -error "database disk image is malformed" {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
}
................................................................................
do_test rtreeA-3.1.0.1 { set_tree_depth t1 } {1}
do_test rtreeA-3.1.0.2 { set_tree_depth t1 3 } {3}
do_corruption_tests rtreeA-3.1 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
}

do_execsql_test rtreeA-3.1.0.3 {
  SELECT rtreecheck('main', 't1')!="ok"
} {1}

do_test rtreeA-3.2.0 { set_tree_depth t1 1000 } {1000}
do_corruption_tests rtreeA-3.2 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
}
................................................................................
} {65535}
do_corruption_tests rtreeA-3.3 {
  1   "SELECT * FROM t1"
  2   "SELECT * FROM t1 WHERE rowid=5"
  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
}

do_execsql_test rtreeA-3.3.3.4 {
  SELECT rtreecheck('main', 't1')
} {{Rtree depth out of range (65535)
Wrong number of entries in %_rowid table - expected 0, actual 499
Wrong number of entries in %_parent table - expected 0, actual 23}}

#-------------------------------------------------------------------------
# Set the "number of entries" field on some nodes incorrectly.
#
create_t1
populate_t1
do_test rtreeA-4.1.0 { 
  set_entry_count t1 1 4000
................................................................................
create_t1
populate_t1
do_execsql_test rtreeA-5.1.0 { DELETE FROM t1_parent } {}
do_corruption_tests rtreeA-5.1 {
  1   "DELETE FROM t1 WHERE rowid = 5"
  2   "DELETE FROM t1"
}

do_execsql_test rtreeA-5.2 {
  SELECT rtreecheck('main', 't1')!="ok"
} {1}

#-------------------------------------------------------------------------
# Add some bad entries to the %_parent table.
#
create_t1
populate_t1
do_execsql_test rtreeA-6.1.0 { 
  UPDATE t1_parent set parentnode = parentnode+1
} {}
do_corruption_tests rtreeA-6.1 {
  1   "DELETE FROM t1 WHERE rowid = 5"
  2   "UPDATE t1 SET x1=x1+1, x2=x2+1"
}

do_execsql_test rtreeA-6.2 {
  SELECT rtreecheck('main', 't1')!="ok"
} {1}

#-------------------------------------------------------------------------
# Truncated blobs in the _node table.
#
create_t1
populate_t1
sqlite3 db test.db
................................................................................
  SELECT * FROM t1 WHERE x1>0 AND x1<100 AND x2>0 AND x2<100;
} {1 {undersize RTree blobs in "t1_node"}}
do_test rtreeA-7.120 {
  sqlite3_extended_errcode db
} {SQLITE_CORRUPT_VTAB}



finish_test

Changes to ext/rtree/rtreeB.test.

11
12
13
14
15
16
17

18
19
20
21
22
23
24
..
39
40
41
42
43
44
45
46


47
# Make sure the rtreenode() testing function can handle entries with
# 64-bit rowids.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

ifcapable rtree_int_only {
  do_test rtreeB-1.1-intonly {
    db eval {
      CREATE VIRTUAL TABLE t1 USING rtree(ii, x0, y0, x1, y1);
................................................................................
      INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
      INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
      INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
      SELECT rtreenode(2, data) FROM t1_node;
    }
  } {{{1073741824 0 0 100 100} {2147483646 0 0 200 200} {4294967296 0 0 300 300} {8589934592 20 20 150 150} {9223372036854775807 150 150 400 400}}}
}



finish_test







>







 








>
>

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
..
40
41
42
43
44
45
46
47
48
49
50
# Make sure the rtreenode() testing function can handle entries with
# 64-bit rowids.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

ifcapable rtree_int_only {
  do_test rtreeB-1.1-intonly {
    db eval {
      CREATE VIRTUAL TABLE t1 USING rtree(ii, x0, y0, x1, y1);
................................................................................
      INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
      INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
      INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
      SELECT rtreenode(2, data) FROM t1_node;
    }
  } {{{1073741824 0 0 100 100} {2147483646 0 0 200 200} {4294967296 0 0 300 300} {8589934592 20 20 150 150} {9223372036854775807 150 150 400 400}}}
}

do_rtree_integrity_test rtreeB-1.2 t1

finish_test

Changes to ext/rtree/rtreeC.test.

11
12
13
14
15
16
17

18
19
20
21
22
23
24
...
176
177
178
179
180
181
182

183
184
185
186
187
188
189
# Make sure the rtreenode() testing function can handle entries with
# 64-bit rowids.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }
set testprefix rtreeC

do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE r_tree USING rtree(id, min_x, max_x, min_y, max_y);
  CREATE TABLE t(x, y);
................................................................................
  INSERT INTO t1(x) SELECT x+64 FROM t1;  -- 128
  INSERT INTO t1(x) SELECT x+128 FROM t1; -- 256
  INSERT INTO t1(x) SELECT x+256 FROM t1; -- 512
  INSERT INTO t1(x) SELECT x+512 FROM t1; --1024

  INSERT INTO rt SELECT x, x, x+1 FROM t1 WHERE x<=5;
}


# First test a query with no ANALYZE data at all. The outer loop is
# real table "t1".
#
do_eqp_test 5.2 {
  SELECT * FROM t1, rt WHERE x==id;
} {







>







 







>







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
# Make sure the rtreenode() testing function can handle entries with
# 64-bit rowids.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }
set testprefix rtreeC

do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE r_tree USING rtree(id, min_x, max_x, min_y, max_y);
  CREATE TABLE t(x, y);
................................................................................
  INSERT INTO t1(x) SELECT x+64 FROM t1;  -- 128
  INSERT INTO t1(x) SELECT x+128 FROM t1; -- 256
  INSERT INTO t1(x) SELECT x+256 FROM t1; -- 512
  INSERT INTO t1(x) SELECT x+512 FROM t1; --1024

  INSERT INTO rt SELECT x, x, x+1 FROM t1 WHERE x<=5;
}
do_rtree_integrity_test 5.1.1 rt

# First test a query with no ANALYZE data at all. The outer loop is
# real table "t1".
#
do_eqp_test 5.2 {
  SELECT * FROM t1, rt WHERE x==id;
} {

Changes to ext/rtree/rtreeE.test.

11
12
13
14
15
16
17

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
..
43
44
45
46
47
48
49

50
51
52
53
54
55
56
...
107
108
109
110
111
112
113

114
115
116
117
118
119
120
# This file contains tests for the r-tree module. Specifically, it tests
# that new-style custom r-tree queries (geometry callbacks) work.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }
ifcapable rtree_int_only { finish_test; return }


#-------------------------------------------------------------------------
# Test the example 2d "circle" geometry callback.
#
register_circle_geom db

do_execsql_test rtreeE-1.1 {
  PRAGMA page_size=512;
  CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1);
  
  /* A tight pattern of small boxes near 0,0 */
  WITH RECURSIVE
    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
................................................................................

  /* A looser pattern of larger boxes near 0, 200 */
  WITH RECURSIVE
    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
  INSERT INTO rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
} {}


# Queries against each of the three clusters */
do_execsql_test rtreeE-1.1 {
  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id;
} {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24}
do_execsql_test rtreeE-1.1x {
  SELECT id FROM rt1 WHERE id MATCH Qcircle('x:0 y:0 r:50.0 e:3') ORDER BY id;
................................................................................
    db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)}
  }
  db eval {
    INSERT INTO rt2 SELECT * FROM t2;
    COMMIT;
  }
} {}


for {set i 1} {$i<=200} {incr i} {
  set dx [expr {int(rand()*100)}]
  set dy [expr {int(rand()*100)}]
  set x0 [expr {int(rand()*(10000 - $dx))}]
  set x1 [expr {$x0+$dx}]
  set y0 [expr {int(rand()*(10000 - $dy))}]







>










|







 







>







 







>







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
..
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
...
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# This file contains tests for the r-tree module. Specifically, it tests
# that new-style custom r-tree queries (geometry callbacks) work.
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }
ifcapable rtree_int_only { finish_test; return }


#-------------------------------------------------------------------------
# Test the example 2d "circle" geometry callback.
#
register_circle_geom db

do_execsql_test rtreeE-1.0.0 {
  PRAGMA page_size=512;
  CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1);
  
  /* A tight pattern of small boxes near 0,0 */
  WITH RECURSIVE
    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
................................................................................

  /* A looser pattern of larger boxes near 0, 200 */
  WITH RECURSIVE
    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
  INSERT INTO rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
} {}
do_rtree_integrity_test rtreeE-1.0.1 rt1

# Queries against each of the three clusters */
do_execsql_test rtreeE-1.1 {
  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id;
} {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24}
do_execsql_test rtreeE-1.1x {
  SELECT id FROM rt1 WHERE id MATCH Qcircle('x:0 y:0 r:50.0 e:3') ORDER BY id;
................................................................................
    db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)}
  }
  db eval {
    INSERT INTO rt2 SELECT * FROM t2;
    COMMIT;
  }
} {}
do_rtree_integrity_test rtreeE-2.1.1 rt2

for {set i 1} {$i<=200} {incr i} {
  set dx [expr {int(rand()*100)}]
  set dy [expr {int(rand()*100)}]
  set x0 [expr {int(rand()*(10000 - $dx))}]
  set x1 [expr {$x0+$dx}]
  set y0 [expr {int(rand()*(10000 - $dy))}]

Changes to ext/rtree/rtreeF.test.

24
25
26
27
28
29
30

31
32
33
34
35
36
37
..
73
74
75
76
77
78
79
80


81
#     END;
#     DELETE FROM t2 WHERE y=1;
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

do_execsql_test rtreeF-1.1 {
  CREATE TABLE t1(x);
  CREATE TABLE t2(y);
  CREATE VIRTUAL TABLE t3 USING rtree(a,b,c);
................................................................................
do_execsql_test rtreeF-1.5 {
  DELETE FROM t2 WHERE y=2;

  SELECT a FROM t3 ORDER BY a;
  SELECT '|';
  SELECT y FROM t2 ORDER BY y;
} {1 4 5 | 1 4}



finish_test







>







 








>
>

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
..
74
75
76
77
78
79
80
81
82
83
84
#     END;
#     DELETE FROM t2 WHERE y=1;
# 

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

do_execsql_test rtreeF-1.1 {
  CREATE TABLE t1(x);
  CREATE TABLE t2(y);
  CREATE VIRTUAL TABLE t3 USING rtree(a,b,c);
................................................................................
do_execsql_test rtreeF-1.5 {
  DELETE FROM t2 WHERE y=2;

  SELECT a FROM t3 ORDER BY a;
  SELECT '|';
  SELECT y FROM t2 ORDER BY y;
} {1 4 5 | 1 4}

do_rtree_integrity_test rtreeF-1.6 t3

finish_test

Changes to ext/rtree/rtreeG.test.

11
12
13
14
15
16
17

18
19
20
21
22
23
24
..
33
34
35
36
37
38
39

40
41
42
43
44
45
46
# This file contains tests for the r-tree module.
#
# Verify that no invalid SQL is run during initialization

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 

source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

db close
sqlite3_shutdown
test_sqlite3_log [list lappend ::log]
set ::log [list]
................................................................................
  set ::log
} {}

do_execsql_test rtreeG-1.2 {
  INSERT INTO t1 VALUES(1,10,15,5,23),(2,20,21,5,23),(3,10,15,20,30);
  SELECT id from t1 WHERE x0>8 AND x1<16 AND y0>2 AND y1<25;
} {1}

do_test rtreeG-1.2log {
  set ::log
} {}

db close
sqlite3 db test.db
do_execsql_test rtreeG-1.3 {







>







 







>







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
..
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# This file contains tests for the r-tree module.
#
# Verify that no invalid SQL is run during initialization

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

db close
sqlite3_shutdown
test_sqlite3_log [list lappend ::log]
set ::log [list]
................................................................................
  set ::log
} {}

do_execsql_test rtreeG-1.2 {
  INSERT INTO t1 VALUES(1,10,15,5,23),(2,20,21,5,23),(3,10,15,20,30);
  SELECT id from t1 WHERE x0>8 AND x1<16 AND y0>2 AND y1<25;
} {1}
do_rtree_integrity_test rtreeG-1.2.integrity t1
do_test rtreeG-1.2log {
  set ::log
} {}

db close
sqlite3 db test.db
do_execsql_test rtreeG-1.3 {

Changes to ext/rtree/rtree_util.tcl.

186
187
188
189
190
191
192





  set ret
}

proc rtree_treedump {db zTab} {
  set d [rtree_depth $db $zTab]
  rtree_nodetreedump $db $zTab "" $d 1
}












>
>
>
>
>
186
187
188
189
190
191
192
193
194
195
196
197
  set ret
}

proc rtree_treedump {db zTab} {
  set d [rtree_depth $db $zTab]
  rtree_nodetreedump $db $zTab "" $d 1
}

proc do_rtree_integrity_test {tn tbl} {
  uplevel [list do_execsql_test $tn "SELECT rtreecheck('$tbl')" ok]
}

Added ext/rtree/rtreecheck.test.



































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# 2017 August 17
#
# 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.
#
#***********************************************************************
#
#


if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source $testdir/tester.tcl
set testprefix rtreecheck

ifcapable !rtree {
  finish_test
  return
}

proc swap_int32 {blob i0 i1} {
  binary scan $blob I* L

  set a [lindex $L $i0]
  set b [lindex $L $i1]

  lset L $i0 $b
  lset L $i1 $a

  binary format I* $L
}

do_catchsql_test 1.0 {
  SELECT rtreecheck();
} {1 {wrong number of arguments to function rtreecheck()}}

do_catchsql_test 1.1 {
  SELECT rtreecheck(0,0,0);
} {1 {wrong number of arguments to function rtreecheck()}}


proc setup_simple_db {{module rtree}} {
  reset_db
  db func swap_int32 swap_int32
  execsql "
    CREATE VIRTUAL TABLE r1 USING $module (id, x1, x2, y1, y2);
    INSERT INTO r1 VALUES(1,  5, 5, 5, 5);  --  3
    INSERT INTO r1 VALUES(2,  6, 6, 6, 6);  --  9
    INSERT INTO r1 VALUES(3,  7, 7, 7, 7);  -- 15
    INSERT INTO r1 VALUES(4,  8, 8, 8, 8);  -- 21
    INSERT INTO r1 VALUES(5,  9, 9, 9, 9);  -- 27
  "
}

setup_simple_db
do_execsql_test 2.1 { 
  SELECT rtreecheck('r1') 
} {ok}

do_execsql_test 2.2 {
  UPDATE r1_node SET data = swap_int32(data, 3, 9);
  UPDATE r1_node SET data = swap_int32(data, 23, 29);
}

do_execsql_test 2.3 { 
  SELECT rtreecheck('r1') 
} {{Dimension 0 of cell 0 on node 1 is corrupt
Dimension 1 of cell 3 on node 1 is corrupt}}

setup_simple_db
do_execsql_test 2.4 {
  DELETE FROM r1_rowid WHERE rowid = 3;
  SELECT rtreecheck('r1') 
} {{Mapping (3 -> 1) missing from %_rowid table
Wrong number of entries in %_rowid table - expected 5, actual 4}}

setup_simple_db
do_execsql_test 2.5 {
  UPDATE r1_rowid SET nodeno=2 WHERE rowid=3;
  SELECT rtreecheck('r1') 
} {{Found (3 -> 2) in %_rowid table, expected (3 -> 1)}}

################
reset_db
do_execsql_test 3.0 { 
  CREATE VIRTUAL TABLE r1 USING rtree_i32(id, x1, x2);
  INSERT INTO r1 VALUES(1, 0x7FFFFFFF*-1, 0x7FFFFFFF);
  INSERT INTO r1 VALUES(2, 0x7FFFFFFF*-1, 5);
  INSERT INTO r1 VALUES(3, -5, 5);
  INSERT INTO r1 VALUES(4, 5, 0x11111111);
  INSERT INTO r1 VALUES(5, 5, 0x00800000);
  INSERT INTO r1 VALUES(6, 5, 0x00008000);
  INSERT INTO r1 VALUES(7, 5, 0x00000080);
  INSERT INTO r1 VALUES(8, 5, 0x40490fdb);
  INSERT INTO r1 VALUES(9, 0x7f800000, 0x7f900000);
  SELECT rtreecheck('r1') 
} {ok}

breakpoint
do_execsql_test 3.1 { 
  CREATE VIRTUAL TABLE r2 USING rtree_i32(id, x1, x2);
  INSERT INTO r2 VALUES(2, -1*(1<<31), -1*(1<<31)+5);
  SELECT rtreecheck('r2') 
} {ok}


finish_test