/ Check-in [d6130cd2]
Login

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

Overview
Comment:Add tests cases and fix minor issues in the rtreecheck() function.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:d6130cd226c0ca95e02f0cbabfdc27071acdcf83e0d0cb0eaa47d992479ed9a1
User & Date: dan 2017-10-25 18:17:24
Context
2017-10-25
19:18
Fix the sqlite3_dbpage virtual table so that it can read and write from any attached database. check-in: d4f893e1 user: drh tags: trunk
18:17
Add tests cases and fix minor issues in the rtreecheck() function. check-in: d6130cd2 user: dan tags: trunk
18:01
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: 7d264980 user: mistachkin tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

3655
3656
3657
3658
3659
3660
3661



3662

3663
3664
3665
3666
3667
3668
3669
....
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
....
3825
3826
3827
3828
3829
3830
3831








3832
3833
3834
3835
3836
3837
3838
....
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
....
3941
3942
3943
3944
3945
3946
3947

3948
3949
3950
3951
3952

3953
3954
3955
3956
3957
3958
3959
....
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
  char *z;
  sqlite3_stmt *pRet = 0;

  va_start(ap, zFmt);
  z = sqlite3_vmprintf(zFmt, ap);

  if( pCheck->rc==SQLITE_OK ){



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

  }

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

................................................................................
  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;

................................................................................
            , 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;
................................................................................
      }
      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 */
................................................................................
      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 */
................................................................................
    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);
  }







>
>
>
|
>







 







|









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


<
<
>
>







 







>
>
>
>
>
>
>
>







 







|
|
|
|
|

|
|
|
|
|
|
|
>







<
>
>
>
>
>
>
>
|
<








|

|








>
>
>
>
|







 







>
|
|
|
|
|
>







 







|







3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
....
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
....
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
....
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
....
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
....
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
  char *z;
  sqlite3_stmt *pRet = 0;

  va_start(ap, zFmt);
  z = sqlite3_vmprintf(zFmt, ap);

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

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

................................................................................
  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);
}

/*
** Argument pCell points to an array of coordinates stored on an rtree page.
** This function checks that the coordinates are internally consistent (no
** x1>x2 conditions) and adds an error message to the RtreeCheck object
** if they are not.
**
** Additionally, if pParent is not NULL, then it is assumed to point to
** the array of coordinates on the parent page that bound the page 
** containing pCell. In this case it is also verified that the two
** sets of coordinates are mutually consistent and an error message added
** to the RtreeCheck object if they are not.
*/
static void rtreeCheckCellCoord(
  RtreeCheck *pCheck, 


  i64 iNode,                      /* Node id to use in error messages */
  int iCell,                      /* Cell number to use in error messages */
  u8 *pCell,                      /* Pointer to cell coordinates */
  u8 *pParent                     /* Pointer to parent coordinates */
){
  RtreeCoord c1, c2;
  RtreeCoord p1, p2;
  int i;

................................................................................
            , i, iCell, iNode
        );
      }
    }
  }
}

/*
** Run rtreecheck() checks on node iNode, which is at depth iDepth within
** the r-tree structure. Argument aParent points to the array of coordinates
** that bound node iNode on the parent node.
**
** If any problems are discovered, an error message is appended to the
** report accumulated in the RtreeCheck object.
*/
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;
................................................................................
      }
      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
        );
      }else{
        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);
  }
}


/*
** The second argument to this function must be either "_rowid" or
** "_parent". This function checks that the number of entries in the
** %_rowid or %_parent table is exactly nExpect. If not, it adds
** an error message to the report in the RtreeCheck object indicated
** by the first argument.
*/
static void rtreeCheckCount(RtreeCheck *pCheck, const char *zTbl, i64 nExpect){

  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!=nExpect ){
          rtreeCheckAppendMsg(pCheck, "Wrong number of entries in %%%s table"
              " - expected %lld, actual %lld" , zTbl, nExpect, nActual
          );
        }
      }
      pCheck->rc = sqlite3_finalize(pCount);
    }
  }
}

/*
** This function does the bulk of the work for the rtree integrity-check.
** It is called by rtreecheck(), which is the SQL function implementation.
*/
static int rtreeCheckTable(
  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 */
................................................................................
      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.nDim>=1 ){
    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 */
................................................................................
    const char *zTab;
    if( nArg==1 ){
      zTab = zDb;
      zDb = "main";
    }else{
      zTab = (const char*)sqlite3_value_text(apArg[1]);
    }
    rc = rtreeCheckTable(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);
  }

Changes to ext/rtree/rtreecheck.test.

30
31
32
33
34
35
36






37
38
39
40
41
42
43
..
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
..
97
98
99
100
101
102
103
104
105
106
107
108
109
110





111




































112
113
  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);
................................................................................

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(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








>
>
>
>
>
>







 







<







 







<






>
>
>
>
>

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


30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
..
87
88
89
90
91
92
93

94
95
96
97
98
99
100
...
102
103
104
105
106
107
108

109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
  set b [lindex $L $i1]

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

  binary format I* $L
}

proc set_int32 {blob idx val} {
  binary scan $blob I* L
  lset L $idx $val
  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);
................................................................................

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(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}


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}

do_execsql_test 3.2 {
  BEGIN;
    UPDATE r2_node SET data = X'123456';
    SELECT rtreecheck('r2')!="ok";
} {1}

do_execsql_test 3.3 {
  ROLLBACK;
  UPDATE r2_node SET data = X'00001234';
  SELECT rtreecheck('r2')!="ok";
} {1}

do_execsql_test 4.0 {
  CREATE TABLE notanrtree(i);
  SELECT rtreecheck('notanrtree');
} {{Schema corrupt or not an rtree}}

#-------------------------------------------------------------------------
#
reset_db
db func set_int32 set_int32
do_execsql_test 5.0 {
  CREATE VIRTUAL TABLE r3 USING rtree_i32(id, x1, x2, y1, y2);
  WITH x(i) AS (
    SELECT 1 UNION ALL SELECT i+1 FROM x WHERE i<1000
  )
  INSERT INTO r3 SELECT i, i, i, i, i FROM x;
}
do_execsql_test 5.1 {
  BEGIN;
    UPDATE r3_node SET data = set_int32(data, 3, 5000);
    UPDATE r3_node SET data = set_int32(data, 4, 5000);
    SELECT rtreecheck('r3')=='ok'
} 0
do_execsql_test 5.2 {
  ROLLBACK;
  BEGIN;
    UPDATE r3_node SET data = set_int32(data, 3, 0);
    UPDATE r3_node SET data = set_int32(data, 4, 0);
    SELECT rtreecheck('r3')=='ok'
} 0

finish_test