SQLite

  2 asdfghjkl
  3 hello_world
} {
  do_execsql_test 1.$tn.1 "
    CREATE VIRTUAL TABLE $nm USING rtree(a,b,c,d,e);
  "

  # EVIDENCE-OF: R-33789-46762 The content of an R*Tree index is actually
  # stored in three ordinary SQLite tables with names derived from the
  # name of the R*Tree.
  #
  # EVIDENCE-OF: R-39849-06566 This is their schema: CREATE TABLE
  # %_node(nodeno INTEGER PRIMARY KEY, data) CREATE TABLE %_parent(nodeno
  # INTEGER PRIMARY KEY, parentnode) CREATE TABLE %_rowid(rowid INTEGER
  # PRIMARY KEY, nodeno)
  #
  # EVIDENCE-OF: R-07489-10051 The "%" in the name of each shadow table is
  # replaced by the name of the R*Tree virtual table. So, if the name of
  # the R*Tree table is "xyz" then the three shadow tables would be
  # "xyz_node", "xyz_parent", and "xyz_rowid".
  do_execsql_test 1.$tn.2 {
    SELECT sql FROM sqlite_schema WHERE name!=$nm ORDER BY 1

# 2021 September 13
#
# 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.
#
#***********************************************************************
#
# The focus of this file is testing the r-tree 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
set testprefix rtreedoc3

ifcapable !rtree {
  finish_test
  return
}


# This command assumes that the argument is a node blob for a 2 dimensional
# i32 r-tree table. It decodes and returns a list of cells from the node
# as a list. Each cell is itself a list of the following form:
#
#    {$rowid $minX $maxX $minY $maxY}
#
# For internal (non-leaf) nodes, the rowid is replaced by the child node
# number.
#
proc rnode_cells {aData} {
  set nDim 2

  set nData [string length $aData]
  set nBytePerCell [expr (8 + 2*$nDim*4)]
  binary scan [string range $aData 2 3] S nCell

  set res [list]
  for {set i 0} {$i < $nCell} {incr i} {
    set iOff [expr $i*$nBytePerCell+4]
    set cell [string range $aData $iOff [expr $iOff+$nBytePerCell-1]]
    binary scan $cell WIIII rowid x1 x2 y1 y2
    lappend res [list $rowid $x1 $x2 $y1 $y2]
  }

  return $res
}

# Interpret the first two bytes of the blob passed as the only parameter
# as a 16-bit big-endian integer and return the value. If this blob is
# the root node of an r-tree, this value is the height of the tree.
#
proc rnode_height {aData} {
  binary scan [string range $aData 0 1] S nHeight
  return $nHeight
}

# Return a blob containing node iNode of r-tree "rt".
#
proc rt_node_get {iNode} {
  db one { SELECT data FROM rt_node WHERE nodeno=$iNode }
}


#--------------------------------------------------------------
# API:
#
#    pq_init 
#      Initialize a new test.
#
#    pq_test_callback
#      Invoked each time the xQueryCallback function is called. This Tcl
#      command checks that the arguments that SQLite passed to xQueryCallback
#      are as expected.
#
#    pq_test_row
#      Invoked each time a row is returned. Checks that the row returned
#      was predicted by the documentation.
#
# DATA STRUCTURE:
#    The priority queue is stored as a Tcl list. The order of elements in 
#    the list is unimportant - it is just used as a set here. Each element
#    in the priority queue is itself a list. The first element is the
#    priority value for the entry (a real). Following this is a list of
#    key-value pairs that make up the entries fields.
#
proc pq_init {} {
  global Q 
  set Q(pri_queue)  [list]

  set nHeight [rnode_height [rt_node_get 1]]
  set nCell [llength [rnode_cells [rt_node_get 1]]]

  # EVIDENCE-OF: R-54708-13595 An R*Tree query is initialized by making
  # the root node the only entry in a priority queue sorted by rScore.
  lappend Q(pri_queue) [list 0.0 [list \
    iLevel [expr $nHeight+1] \
    iChild 1                 \
    iCurrent   0             \
  ]]
}

proc pq_extract {} {
  global Q
  if {[llength $Q(pri_queue)]==0} {
    error "priority queue is empty!"
  }

  # Find the priority queue entry with the lowest score.
  #
  # EVIDENCE-OF: R-47257-47871 Smaller scores are processed first.
  set iBest 0
  set rBestScore [lindex $Q(pri_queue) 0 0]
  for {set ii 1} {$ii < [llength $Q(pri_queue)]} {incr ii} {
    set rScore [expr [lindex $Q(pri_queue) $ii 0]]
    if {$rScore<$rBestScore} {
      set rBestScore $rScore
      set iBest $ii
    }
  }

  # Extract the entry with the lowest score from the queue and return it. 
  #
  # EVIDENCE-OF: R-60002-49798 The query proceeds by extracting the entry
  # from the priority queue that has the lowest score.
  set ret [lindex $Q(pri_queue) $iBest]
  set Q(pri_queue) [lreplace $Q(pri_queue) $iBest $iBest]

  return $ret
}

proc pq_new_entry {rScore iLevel cell} {
  global Q

  set rowid_name "iChild"
  if {$iLevel==0} { set rowid_name "iRowid" }

  set kv [list]
  lappend kv aCoord [lrange $cell 1 end]
  lappend kv iLevel $iLevel

  if {$iLevel==0} {
    lappend kv iRowid [lindex $cell 0]
  } else {
    lappend kv iChild [lindex $cell 0]
    lappend kv iCurrent 0
  }

  lappend Q(pri_queue) [list $rScore $kv]
}

proc pq_test_callback {L res} {
  #pq_debug "pq_test_callback $L -> $res"
  global Q

  array set G $L    ;# "Got" - as in stuff passed to xQuery

  # EVIDENCE-OF: R-65127-42665 If the extracted priority queue entry is a
  # node (a subtree), then the next child of that node is passed to the
  # xQueryFunc callback.
  #
  # If it had been a leaf, the row should have been returned, instead of
  # xQueryCallback being called on a child - as is happening here.
  foreach {rParentScore parent} [pq_extract] {}
  array set P $parent ;# "Parent" - as in parent of expected cell
  if {$P(iLevel)==0} { error "query callback mismatch (1)" }
  set child_node [rnode_cells [rt_node_get $P(iChild)]]
  set expected_cell [lindex $child_node $P(iCurrent)]
  set expected_coords [lrange $expected_cell 1 end]
  if {[llength $expected_coords] != [llength $G(aCoord)]} {
  puts [array get P]
  puts "E: $expected_coords  G: $G(aCoord)"
    error "coordinate mismatch in query callback (1)"
  }
  foreach a [lrange $expected_cell 1 end] b $G(aCoord) {
    if {$a!=$b} { error "coordinate mismatch in query callback (2)" }
  }

  # Check level is as expected
  #
  if {$G(iLevel) != $P(iLevel)-1} {
    error "iLevel mismatch in query callback (1)"
  }

  # Unless the callback returned NOT_WITHIN, add the entry to the priority
  # queue.
  #
  # EVIDENCE-OF: R-28754-35153 Those subelements for which the xQueryFunc
  # callback sets eWithin to PARTLY_WITHIN or FULLY_WITHIN are added to
  # the priority queue using the score supplied by the callback.
  #
  # EVIDENCE-OF: R-08681-45277 Subelements that return NOT_WITHIN are
  # discarded.
  set r [lindex $res 0]
  set rScore [lindex $res 1]
  if {$r!="fully" && $r!="partly" && $r!="not"} {
    error "unknown result: $r - expected \"fully\", \"partly\" or \"not\""
  }
  if {$r!="not"} {
    pq_new_entry $rScore [expr $P(iLevel)-1] $expected_cell
  }

  # EVIDENCE-OF: R-07194-63805 If the node has more children then it is
  # returned to the priority queue. Otherwise it is discarded.
  incr P(iCurrent)
  if {$P(iCurrent)<[llength $child_node]} {
    lappend Q(pri_queue) [list $rParentScore [array get P]]
  }
}

proc pq_test_result {id x1 x2 y1 y2} {
  #pq_debug "pq_test_result $id $x1 $x2 $y1 $y2"
  foreach {rScore next} [pq_extract] {}

  # The extracted entry must be a leaf (otherwise, xQueryCallback would
  # have been called on the extracted entries children instead of just
  # returning the data).
  #
  # EVIDENCE-OF: R-13214-54017 If that entry is a leaf (meaning that it is
  # an actual R*Tree entry and not a subtree) then that entry is returned
  # as one row of the query result.
  array set N $next
  if {$N(iLevel)!=0} { error "result row mismatch (1)" }

  if {$x1!=[lindex $N(aCoord) 0] || $x2!=[lindex $N(aCoord) 1]
   || $y1!=[lindex $N(aCoord) 2] || $y2!=[lindex $N(aCoord) 3]
  } {
    if {$N(iLevel)!=0} { error "result row mismatch (2)" }
  }

  if {$id!=$N(iRowid)} { error "result row mismatch (3)" }
}

proc pq_done {} {
  global Q
  # EVIDENCE-OF: R-57438-45968 The query runs until the priority queue is
  # empty.
  if {[llength $Q(pri_queue)]>0} {
    error "priority queue is not empty!"
  }
}

proc pq_debug {caption} {
  global Q

  puts "**** $caption ****"
  set i 0
  foreach q [lsort -real -index 0 $Q(pri_queue)] { 
    puts "PQ $i: $q" 
    incr i
  }
}

#--------------------------------------------------------------

proc box_query {a} {
  set res [list fully [expr rand()]]
  pq_test_callback $a $res
  return $res
}

register_box_query db box_query

do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE rt USING rtree_i32(id,  x1,x2,  y1,y2);
  WITH s(i) AS (
    SELECT 0 UNION ALL SELECT i+1 FROM s WHERE i<64
  )
  INSERT INTO rt SELECT NULL, a.i, a.i+1, b.i, b.i+1 FROM s a, s b;
}

proc box_query {a} {
  set res [list fully [expr rand()]]
  pq_test_callback $a $res
  return $res
}

pq_init
db eval { SELECT id, x1,x2, y1,y2 FROM rt WHERE id MATCH qbox() } {
  pq_test_result $id $x1 $x2 $y1 $y2
}
pq_done

finish_test

#ifdef SQLITE_ENABLE_RTREE

typedef struct BoxGeomCtx BoxGeomCtx;
struct BoxGeomCtx {
  Tcl_Interp *interp;
  Tcl_Obj *pScript;
};

typedef struct BoxQueryCtx BoxQueryCtx;
struct BoxQueryCtx {
  Tcl_Interp *interp;
  Tcl_Obj *pScript;
};

static void testDelUser(void *pCtx){
  BoxGeomCtx *p = (BoxGeomCtx*)pCtx;
  Tcl_EvalObjEx(p->interp, p->pScript, 0);
  Tcl_DecrRefCount(p->pScript);
  sqlite3_free(p);
}

# EVIDENCE-OF: R-00693-36727 The legacy xGeom callback is invoked with
# four arguments.

# EVIDENCE-OF: R-50437-53270 The first argument is a pointer to an
# sqlite3_rtree_geometry structure which provides information about how
# the SQL function was invoked.





# EVIDENCE-OF: R-00090-24248 The third argument, aCoord[], is an array
# of nCoord coordinates that defines a bounding box to be tested.

# EVIDENCE-OF: R-28207-40885 The last argument is a pointer into which
# the callback result should be written.

*/

  sqlite3_rtree_geometry_callback(db, "box", box_geom, (void*)pCtx);

  sqlite3_snprintf(64, aPtr, "%p", (void*)pCtx);
  Tcl_SetObjResult(interp, Tcl_NewStringObj(aPtr, -1));
  return TCL_OK;
}

static int box_query(sqlite3_rtree_query_info *pInfo){
  const char *azParentWithin[] = {"not", "partly", "fully", 0};
  BoxQueryCtx *pCtx = (BoxQueryCtx*)pInfo->pContext;
  Tcl_Interp *interp = pCtx->interp;
  Tcl_Obj *pEval;
  Tcl_Obj *pArg;
  Tcl_Obj *pTmp = 0;
  int rc;
  int ii;

  pEval = Tcl_DuplicateObj(pCtx->pScript);
  Tcl_IncrRefCount(pEval);
  pArg = Tcl_NewObj();
  Tcl_IncrRefCount(pArg);

  /* aParam[] */
  pTmp = Tcl_NewObj();
  Tcl_IncrRefCount(pTmp);
  for(ii=0; ii<pInfo->nParam; ii++){
    Tcl_Obj *p = Tcl_NewDoubleObj(pInfo->aParam[ii]);
    Tcl_ListObjAppendElement(interp, pTmp, p);
  }
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("aParam", -1));
  Tcl_ListObjAppendElement(interp, pArg, pTmp);
  Tcl_DecrRefCount(pTmp);

  /* aCoord[] */
  pTmp = Tcl_NewObj();
  Tcl_IncrRefCount(pTmp);
  for(ii=0; ii<pInfo->nCoord; ii++){
    Tcl_Obj *p = Tcl_NewDoubleObj(pInfo->aCoord[ii]);
    Tcl_ListObjAppendElement(interp, pTmp, p);
  }
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("aCoord", -1));
  Tcl_ListObjAppendElement(interp, pArg, pTmp);
  Tcl_DecrRefCount(pTmp);

  /* anQueue[] */
  pTmp = Tcl_NewObj();
  Tcl_IncrRefCount(pTmp);
  for(ii=0; ii<=pInfo->mxLevel; ii++){
    Tcl_Obj *p = Tcl_NewIntObj((int)pInfo->anQueue[ii]);
    Tcl_ListObjAppendElement(interp, pTmp, p);
  }
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("anQueue", -1));
  Tcl_ListObjAppendElement(interp, pArg, pTmp);
  Tcl_DecrRefCount(pTmp);
  
  /* iLevel */
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("iLevel", -1));
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewIntObj(pInfo->iLevel));

  /* mxLevel */
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("mxLevel", -1));
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewIntObj(pInfo->mxLevel));

  /* iRowid */
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("iRowid", -1));
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewWideIntObj(pInfo->iRowid));

  /* rParentScore */
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("rParentScore", -1));
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewDoubleObj(pInfo->rParentScore));

  /* eParentWithin */
  assert( pInfo->eParentWithin==0 
       || pInfo->eParentWithin==1 
       || pInfo->eParentWithin==2 
  );
  Tcl_ListObjAppendElement(interp, pArg, Tcl_NewStringObj("eParentWithin", -1));
  Tcl_ListObjAppendElement(interp, pArg, 
      Tcl_NewStringObj(azParentWithin[pInfo->eParentWithin], -1)
  );

  Tcl_ListObjAppendElement(interp, pEval, pArg);
  rc = Tcl_EvalObjEx(interp, pEval, 0) ? SQLITE_ERROR : SQLITE_OK;

  if( rc==SQLITE_OK ){
    double rScore = 0.0;
    int nObj = 0;
    int eP = 0;
    Tcl_Obj **aObj = 0;
    Tcl_Obj *pRes = Tcl_GetObjResult(interp);

    if( Tcl_ListObjGetElements(interp, pRes, &nObj, &aObj) 
     || nObj!=2 
     || Tcl_GetDoubleFromObj(interp, aObj[1], &rScore)
     || Tcl_GetIndexFromObj(interp, aObj[0], azParentWithin, "value", 0, &eP)
    ){
      rc = SQLITE_ERROR;
    }else{
      pInfo->rScore = rScore;
      pInfo->eParentWithin = eP;
    }
  }

  Tcl_DecrRefCount(pArg);
  Tcl_DecrRefCount(pEval);
  return rc;
}

static void box_query_destroy(void *p){
  BoxQueryCtx *pCtx = (BoxQueryCtx*)p;
  Tcl_DecrRefCount(pCtx->pScript);
  ckfree(pCtx);
}

static int SQLITE_TCLAPI register_box_query(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  extern int getDbPointer(Tcl_Interp*, const char*, sqlite3**);
  extern const char *sqlite3ErrName(int);
  sqlite3 *db;
  BoxQueryCtx *pCtx;

  if( objc!=3 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB SCRIPT");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;

  pCtx = (BoxQueryCtx*)ckalloc(sizeof(BoxQueryCtx*));
  pCtx->interp = interp;
  pCtx->pScript = Tcl_DuplicateObj(objv[2]);
  Tcl_IncrRefCount(pCtx->pScript);

  sqlite3_rtree_query_callback(
      db, "qbox", box_query, (void*)pCtx, box_query_destroy
  );

  Tcl_ResetResult(interp);
  return TCL_OK;
}
#endif /* SQLITE_ENABLE_RTREE */


int Sqlitetestrtreedoc_Init(Tcl_Interp *interp){
#ifdef SQLITE_ENABLE_RTREE
  Tcl_CreateObjCommand(interp, "register_box_geom", register_box_geom, 0, 0);
  Tcl_CreateObjCommand(interp, "register_box_query", register_box_query, 0, 0);
#endif /* SQLITE_ENABLE_RTREE */
  return TCL_OK;
}