if( pNext->nList==0 ){
    pTrim->nList = 0;
  }else{
    int bEof = 0;
    int nTrail = nNear + (pNext->nToken-1) + 1;
    int nLead = nNear + (pTrim->nToken-1) + 1;

    InstanceList trail;
    InstanceList lead;
    InstanceList in;
    InstanceList out;

    fts5InstanceListInit(pNext->aList, pNext->nList, &trail);
    fts5InstanceListInit(pNext->aList, pNext->nList, &lead);
    fts5InstanceListInit(pTrim->aList, pTrim->nList, &in);
    fts5InstanceListInit(pTrim->aList, pTrim->nList, &out);
    fts5InstanceListNext(&trail);
    fts5InstanceListNext(&lead);
    fts5InstanceListNext(&in);

    while( bEof==0 ){
      if( fts5IsNear(&trail, &in, nTrail) 
       || fts5IsNear(&in, &lead, nLead)
      ){
        /* The current position is a match. Append an entry to the output
        ** and advance the input cursor. */
        fts5InstanceListAppend(&out, in.iCol, in.iWeight, in.iOff);
        bEof = fts5InstanceListNext(&in);
      }else{
        /* The current position is not a match. Advance one of the trailing,
        ** leading or input cursors. */
        if( fts5InstanceListEof(&trail)==0
         && (trail.iCol<in.iCol || trail.iOff>=in.iOff) 
        ){
          fts5InstanceListNext(&trail);
        }
        else if( fts5InstanceListEof(&lead)==0
         && (lead.iCol<in.iCol || lead.iOff<=in.iOff)
        ){
          fts5InstanceListNext(&trail);
        }else{
          bEof = fts5InstanceListNext(&in);
        }
      }
    }

    pTrim->nList = out.iList;

  if( pNext->nList==0 ){
    pTrim->nList = 0;
  }else{
    int bEof = 0;
    int nTrail = nNear + (pNext->nToken-1) + 1;
    int nLead = nNear + (pTrim->nToken-1) + 1;

    InstanceList near;

    InstanceList in;
    InstanceList out;

    fts5InstanceListInit(pNext->aList, pNext->nList, &near);

    fts5InstanceListInit(pTrim->aList, pTrim->nList, &in);
    fts5InstanceListInit(pTrim->aList, pTrim->nList, &out);
    fts5InstanceListNext(&near);

    fts5InstanceListNext(&in);

    while( bEof==0 ){
      if( fts5IsNear(&near, &in, nTrail) 
       || fts5IsNear(&in, &near, nLead)
      ){
        /* The current position is a match. Append an entry to the output
        ** and advance the input cursor. */
        fts5InstanceListAppend(&out, in.iCol, in.iWeight, in.iOff);
        bEof = fts5InstanceListNext(&in);
      }else{
        if( near.iCol<in.iCol || (near.iCol==in.iCol && near.iOff<in.iOff) ){
          bEof = fts5InstanceListNext(&near);
        }else if( near.iCol==in.iCol && near.iOff==in.iOff ){
          bEof = fts5InstanceListNext(&in);
          if( fts5IsNear(&near, &in, nTrail) ){
            fts5InstanceListAppend(&out, near.iCol, near.iWeight, near.iOff);
          }




        }else{
          bEof = fts5InstanceListNext(&in);
        }
      }
    }

    pTrim->nList = out.iList;

  9  {SELECT x FROM t1 WHERE t1 MATCH 'b+c+d NEAR/1 g+h'} {2 3}
  10 {SELECT x FROM t1 WHERE t1 MATCH 'a AND d'}          {1 2}
  11 {SELECT x FROM t1 WHERE t1 MATCH 'a OR d'}           {1 2 3 4}
  12 {SELECT x FROM t1 WHERE t1 MATCH 'a NOT d'}          {4}
} {
  do_execsql_test 3.$tn $stmt $res
}












finish_test

  9  {SELECT x FROM t1 WHERE t1 MATCH 'b+c+d NEAR/1 g+h'} {2 3}
  10 {SELECT x FROM t1 WHERE t1 MATCH 'a AND d'}          {1 2}
  11 {SELECT x FROM t1 WHERE t1 MATCH 'a OR d'}           {1 2 3 4}
  12 {SELECT x FROM t1 WHERE t1 MATCH 'a NOT d'}          {4}
} {
  do_execsql_test 3.$tn $stmt $res
}

do_execsql_test 4.0 {
  CREATE TABLE t2(docid PRIMARY KEY, a, b, c);
  CREATE INDEX i2 ON t2 USING fts5();
  INSERT INTO t2 VALUES(136895, 'qkfl my qkfl krag gw', NULL, NULL);
}

breakpoint
do_execsql_test 4.1 {
  SELECT docid FROM t2 WHERE t2 MATCH 'qkfl NEAR/2 gw';
} {136895}

finish_test

# 2009 December 03
#
#    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.
#
#***********************************************************************
#
# Brute force (random data) tests for fts5.
#

#-------------------------------------------------------------------------
#
# The FTS3 tests implemented in this file focus on testing that FTS3
# returns the correct set of documents for various types of full-text
# query. This is done using pseudo-randomly generated data and queries.
# The expected result of each query is calculated using Tcl code.
#
#   1. The database is initialized to contain a single table with three
#      columns. 100 rows are inserted into the table. Each of the three
#      values in each row is a document consisting of between 0 and 100
#      terms. Terms are selected from a vocabulary of $G(nVocab) terms.
#
#   2. The following is performed 100 times:
#
#      a. A row is inserted into the database. The row contents are 
#         generated as in step 1. The docid is a pseudo-randomly selected
#         value between 0 and 1000000.
# 
#      b. A psuedo-randomly selected row is updated. One of its columns is
#         set to contain a new document generated in the same way as the
#         documents in step 1.
# 
#      c. A psuedo-randomly selected row is deleted.
# 
#      d. For each of several types of fts3 queries, 10 SELECT queries
#         of the form:
# 
#           SELECT docid FROM <tbl> WHERE <tbl> MATCH '<query>'
# 
#         are evaluated. The results are compared to those calculated by
#         Tcl code in this file. The patterns used for the different query
#         types are:
# 
#           1.  query = <term>
#           2.  query = <prefix>
#           3.  query = "<term> <term>"
#           4.  query = "<term> <term> <term>"
#           5.  query = "<prefix> <prefix> <prefix>"
#           6.  query = <term> NEAR <term>
#           7.  query = <term> NEAR/11 <term> NEAR/11 <term>
#           8.  query = <term> OR <term>
#           9.  query = <term> NOT <term>
#           10. query = <term> AND <term>
#           11. query = <term> NEAR <term> OR <term> NEAR <term>
#           12. query = <term> NEAR <term> NOT <term> NEAR <term>
#           13. query = <term> NEAR <term> AND <term> NEAR <term>
# 
#         where <term> is a term psuedo-randomly selected from the vocabulary
#         and prefix is the first 2 characters of such a term followed by
#         a "*" character.
#     
#      Every second iteration, steps (a) through (d) above are performed
#      within a single transaction. This forces the queries in (d) to
#      read data from both the database and the in-memory hash table
#      that caches the full-text index entries created by steps (a), (b)
#      and (c) until the transaction is committed.
#
# The procedure above is run 5 times, using advisory fts3 node sizes of 50,
# 500, 1000 and 2000 bytes.
#
# After the test using an advisory node-size of 50, an OOM test is run using
# the database. This test is similar to step (d) above, except that it tests
# the effects of transient and persistent OOM conditions encountered while
# executing each query.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# If this build does not include FTS3, skip the tests in this file.
#
#ifcapable !fts3 { finish_test ; return }
source $testdir/fts3_common.tcl
source $testdir/malloc_common.tcl

set G(nVocab) 100

set nVocab 100
set lVocab [list]

expr srand(0)

# Generate a vocabulary of nVocab words. Each word is between 2 and 4 
# characters long.
#
set lChar {a b c d e f g h i j k l m n o p q r s t u v w x y z}
for {set i 0} {$i < $nVocab} {incr i} {
  set len [expr int(rand()*3)+2]
  set    word [lindex $lChar [expr int(rand()*26)]]
  append word [lindex $lChar [expr int(rand()*26)]]
  if {$len>2} { append word [lindex $lChar [expr int(rand()*26)]] }
  if {$len>3} { append word [lindex $lChar [expr int(rand()*26)]] }
  lappend lVocab $word
}

proc random_term {} {
  lindex $::lVocab [expr {int(rand()*$::nVocab)}]
}

# Return a document consisting of $nWord arbitrarily selected terms
# from the $::lVocab list.
#
proc generate_doc {nWord} {
  set doc [list]
  for {set i 0} {$i < $nWord} {incr i} {
    lappend doc [random_term]
  }
  return $doc
}



# Primitives to update the table.
#
unset -nocomplain t1
proc insert_row {docid} {
  set a [generate_doc [expr int((rand()*100))]]
  set b [generate_doc [expr int((rand()*100))]]
  set c [generate_doc [expr int((rand()*100))]]
  execsql { INSERT INTO t1(docid, a, b, c) VALUES($docid, $a, $b, $c) }
  set ::t1($docid) [list $a $b $c]
}
proc delete_row {docid} {
  execsql { DELETE FROM t1 WHERE docid = $docid }
  catch {unset ::t1($docid)}
}
proc update_row {docid} {
  set cols {a b c}
  set iCol [expr int(rand()*3)]
  set doc  [generate_doc [expr int((rand()*100))]]
  lset ::t1($docid) $iCol $doc
  execsql "UPDATE t1 SET [lindex $cols $iCol] = \$doc WHERE docid = \$docid"
}

proc simple_phrase {zPrefix} {
  set ret [list]

  set reg [string map {* {[^ ]*}} $zPrefix]
  set reg " $reg "

  foreach key [lsort -integer [array names ::t1]] {
    set value $::t1($key)
    set cnt [list]
    foreach col $value {
      if {[regexp $reg " $col "]} { lappend ret $key ; break }
    }
  }

  #lsort -uniq -integer $ret
  set ret
}

# This [proc] is used to test the FTS3 matchinfo() function.
# 
proc simple_token_matchinfo {zToken bDesc} {

  set nDoc(0) 0
  set nDoc(1) 0
  set nDoc(2) 0
  set nHit(0) 0
  set nHit(1) 0
  set nHit(2) 0

  set dir -inc
  if {$bDesc} { set dir -dec }

  foreach key [array names ::t1] {
    set value $::t1($key)
    set a($key) [list]
    foreach i {0 1 2} col $value {
      set hit [llength [lsearch -all $col $zToken]]
      lappend a($key) $hit
      incr nHit($i) $hit
      if {$hit>0} { incr nDoc($i) }
    }
  }

  set ret [list]
  foreach docid [lsort -integer $dir [array names a]] {
    if { [lindex [lsort -integer $a($docid)] end] } {
      set matchinfo [list 1 3]
      foreach i {0 1 2} hit $a($docid) {
        lappend matchinfo $hit $nHit($i) $nDoc($i)
      }
      lappend ret $docid $matchinfo
    }
  }

  set ret
} 

proc simple_near {termlist nNear} {
  set ret [list]

  foreach {key value} [array get ::t1] {
    foreach v $value {

      set l [lsearch -exact -all $v [lindex $termlist 0]]
      foreach T [lrange $termlist 1 end] {
        set l2 [list]
        foreach i $l {
          set iStart [expr $i - $nNear - 1]
          set iEnd [expr $i + $nNear + 1]
          if {$iStart < 0} {set iStart 0}
          foreach i2 [lsearch -exact -all [lrange $v $iStart $iEnd] $T] {
            incr i2 $iStart
            if {$i2 != $i} { lappend l2 $i2 } 
          }
        }
        set l [lsort -uniq -integer $l2]
      }

      if {[llength $l]} {
#puts "MATCH($key): $v"
        lappend ret $key
      } 
    }
  }

  lsort -unique -integer $ret
}

# The following three procs:
# 
#   setup_not A B
#   setup_or  A B
#   setup_and A B
#
# each take two arguments. Both arguments must be lists of integer values
# sorted by value. The return value is the list produced by evaluating
# the equivalent of "A op B", where op is the FTS3 operator NOT, OR or
# AND.
#
proc setop_not {A B} {
  foreach b $B { set n($b) {} }
  set ret [list]
  foreach a $A { if {![info exists n($a)]} {lappend ret $a} }
  return $ret
}
proc setop_or {A B} {
  lsort -integer -uniq [concat $A $B]
}
proc setop_and {A B} {
  foreach b $B { set n($b) {} }
  set ret [list]
  foreach a $A { if {[info exists n($a)]} {lappend ret $a} }
  return $ret
}

proc mit {blob} {
  set scan(littleEndian) i*
  set scan(bigEndian) I*
  binary scan $blob $scan($::tcl_platform(byteOrder)) r
  return $r
}
db func mit mit
set sqlite_fts3_enable_parentheses 1

proc do_orderbydocid_test {tn sql res} {
  uplevel [list do_select_test $tn.asc "$sql ORDER BY docid ASC" $res]
  uplevel [list do_select_test $tn.desc "$sql ORDER BY docid DESC" \
    [lsort -int -dec $res]
  ]
}

#-------------------------------------------------------------------------
#
set NUM_TRIALS 10
catch { array unset ::t1 }

# Create the fts5 table. Populate it (and the Tcl array) with 100 rows.
#
db transaction {
  execsql {
    DROP TABLE IF EXISTS t1;
    CREATE TABLE t1(docid PRIMARY KEY, a, b, c);
    CREATE INDEX i1 ON t1 USING fts5();
  }
  for {set i 0} {$i < 100} {incr i} { insert_row $i }
}

for {set iTest 1} {$iTest <= $NUM_TRIALS} {incr iTest} {
  catchsql COMMIT

  set DO_MALLOC_TEST 0
  set nRep 10
  # if {$iTest==100 && $nodesize==50} { 
    # set DO_MALLOC_TEST 1 
    # set nRep 2
  # }

  set ::testprefix fts5rnd-1.$iTest

  # Delete one row, update one row and insert one row.
  #
  set rows [array names ::t1]
  set nRow [llength $rows]
  set iUpdate [lindex $rows [expr {int(rand()*$nRow)}]]
  set iDelete $iUpdate
  while {$iDelete == $iUpdate} {
    set iDelete [lindex $rows [expr {int(rand()*$nRow)}]]
  }
  set iInsert $iUpdate
  while {[info exists ::t1($iInsert)]} {
    set iInsert [expr {int(rand()*1000000)}]
  }
  execsql BEGIN
    insert_row $iInsert
    update_row $iUpdate
    delete_row $iDelete
  if {0==($iTest%2)} { execsql COMMIT }

  if {0==($iTest%2)} { 
    #do_test 0 { fts3_integrity_check t1 } ok 
  }

  # Pick 10 terms from the vocabulary. Check that the results of querying
  # the database for the set of documents containing each of these terms
  # is the same as the result obtained by scanning the contents of the Tcl 
  # array for each term.
  #
  for {set i 0} {$i < 10} {incr i} {
    set term [random_term]
    do_orderbydocid_test 1.$i.asc {
      SELECT docid FROM t1 WHERE t1 MATCH $term
    } [simple_phrase $term]
    do_orderbydocid_test 1.$i.desc {
      SELECT docid FROM t1 WHERE t1 MATCH $term
    } [simple_phrase $term]
  }

  # This time, use the first two characters of each term as a term prefix
  # to query for. Test that querying the Tcl array produces the same results
  # as querying the FTS3 table for the prefix.
  #

puts "todo: prefix query support"
#  for {set i 0} {$i < $nRep} {incr i} {
#    set prefix [string range [random_term] 0 end-1]
#    set match "${prefix}*"
#    do_orderbydocid_test 2.$i {
#      SELECT docid FROM t1 WHERE t1 MATCH $match
#    } [simple_phrase $match]
#  }

  # Similar to the above, except for phrase queries.
  #
  for {set i 0} {$i < $nRep} {incr i} {
    set term [list [random_term] [random_term]]
    set match "\"$term\""
    do_orderbydocid_test 3.$i {
      SELECT docid FROM t1 WHERE t1 MATCH $match
    } [simple_phrase $term]
  }

  # Three word phrases.
  #
  for {set i 0} {$i < $nRep} {incr i} {
    set term [list [random_term] [random_term] [random_term]]
    set match "\"$term\""
    do_orderbydocid_test 4.$i {
      SELECT docid FROM t1 WHERE t1 MATCH $match
    } [simple_phrase $term]
  }

  # Three word phrases made up of term-prefixes.
  #
puts "todo: prefix query support"
#  for {set i 0} {$i < $nRep} {incr i} {
#    set    query "[string range [random_term] 0 end-1]* "
#    append query "[string range [random_term] 0 end-1]* "
#    append query "[string range [random_term] 0 end-1]*"
#
#    set match "\"$query\""
#    do_orderbydocid_test 5.$i {
#      SELECT docid FROM t1 WHERE t1 MATCH $match
#    } [simple_phrase $query]
#  }

  # A NEAR query with terms as the arguments:
  #
  #     ... MATCH '$term1 NEAR $term2' ...
  #
  for {set i 0} {$i < $nRep} {incr i} {
    set terms [list [random_term] [random_term]]
    set match [join $terms " NEAR "]
    do_orderbydocid_test 6.$i {
      SELECT docid FROM t1 WHERE t1 MATCH $match 
    } [simple_near $terms 10]
  }

  # A 3-way NEAR query with terms as the arguments.
  #
  for {set i 0} {$i < $nRep} {incr i} {
    set terms [list [random_term] [random_term] [random_term]]
    set nNear 11
    set match [join $terms " NEAR/$nNear "]
    do_orderbydocid_test 7.$i {
      SELECT docid FROM t1 WHERE t1 MATCH $match
    } [simple_near $terms $nNear]
  }
  
  # Set operations on simple term queries.
  #
  foreach {tn op proc} {
    8  OR  setop_or
    9  NOT setop_not
    10 AND setop_and
  } {
    for {set i 0} {$i < $nRep} {incr i} {
      set term1 [random_term]
      set term2 [random_term]
      set match "$term1 $op $term2"
      do_orderbydocid_test $tn.$i {
        SELECT docid FROM t1 WHERE t1 MATCH $match
      } [$proc [simple_phrase $term1] [simple_phrase $term2]]
    }
  }
 
  # Set operations on NEAR queries.
  #
  foreach {tn op proc} {
    11 OR  setop_or
    12 NOT setop_not
    13 AND setop_and
  } {
    for {set i 0} {$i < $nRep} {incr i} {
      set term1 [random_term]
      set term2 [random_term]
      set term3 [random_term]
      set term4 [random_term]
      set match "$term1 NEAR $term2 $op $term3 NEAR $term4"
      do_orderbydocid_test $tn.$i {
        SELECT docid FROM t1 WHERE t1 MATCH $match
      } [$proc                                  \
          [simple_near [list $term1 $term2] 10] \
          [simple_near [list $term3 $term4] 10]
        ]
    }
  }

  catchsql COMMIT
}

finish_test