third_party/sqlite/sqlite-src-3080704/test/fts3expr3.test

   1 # 2009 January 1
   2 #
   3 # The author disclaims copyright to this source code.  In place of
   4 # a legal notice, here is a blessing:
   5 #
   6 #    May you do good and not evil.
   7 #    May you find forgiveness for yourself and forgive others.
   8 #    May you share freely, never taking more than you give.
   9 #
  10 #*************************************************************************
  11 # This file implements regression tests for SQLite library.  The
  12 # focus of this script is testing the part of the FTS3 expression
  13 # parser that rebalances large expressions.
  14 #
  15 # $Id: fts3expr2.test,v 1.2 2009/06/05 17:09:12 drh Exp $
  16 #
  17
  18 set testdir [file dirname $argv0]
  19 source $testdir/tester.tcl
  20 source $testdir/malloc_common.tcl
  21 set ::testprefix fts3expr3
  22
  23 # If SQLITE_ENABLE_FTS3 is defined, omit this file.
  24 ifcapable !fts3 {
  25   finish_test
  26   return
  27 }
  28
  29 set sqlite_fts3_enable_parentheses 1
  30
  31 proc strip_phrase_data {L} {
  32   if {[lindex $L 0] eq "PHRASE"} {
  33     return [list P [lrange $L 3 end]]
  34   }
  35   return [list \
  36     [lindex $L 0] \
  37     [strip_phrase_data [lindex $L 1]] \
  38     [strip_phrase_data [lindex $L 2]] \
  39   ]
  40 }
  41 proc test_fts3expr2 {expr} {
  42   strip_phrase_data [
  43     db one {SELECT fts3_exprtest_rebalance('simple', $expr, 'a', 'b', 'c')}
  44   ]
  45 }
  46
  47 proc balanced_exprtree_structure {nEntry} {
  48   set L [list]
  49   for {set i 1} {$i <= $nEntry} {incr i} {
  50     lappend L xxx
  51   }
  52   while {[llength $L] > 1} {
  53     set N [list]
  54     if {[llength $L] % 2} {
  55       foreach {a b} [lrange $L 0 end-1] { lappend N [list AND $a $b] }
  56       lappend N [lindex $L end]
  57     } else {
  58       foreach {a b} $L { lappend N [list AND $a $b] }
  59     }
  60     set L $N
  61   }
  62   return [lindex $L 0]
  63 }
  64
  65 proc balanced_and_tree {nEntry} {
  66   set query [balanced_exprtree_structure $nEntry]
  67   if {$query == "xxx"} {
  68     return "P 1"
  69   }
  70   for {set i 1} {$i <= $nEntry} {incr i} {
  71     regsub xxx $query "{P $i}" query
  72   }
  73   return $query
  74 }
  75
  76 proc random_tree_structure {nEntry bParen op} {
  77   set query xxx
  78   for {set i 1} {$i < $nEntry} {incr i} {
  79     set x1 [expr int(rand()*4.0)]
  80     set x2 [expr int(rand()*2.0)]
  81     if {$x1==0 && $bParen} {
  82       set query "($query)"
  83     }
  84     if {$x2} {
  85       set query "xxx $op $query"
  86     } else {
  87       set query "$query $op xxx"
  88     }
  89   }
  90   return $query
  91 }
  92
  93 proc random_and_query {nEntry {bParen 0}} {
  94   set query [random_tree_structure $nEntry $bParen AND]
  95   for {set i 1} {$i <= $nEntry} {incr i} {
  96     regsub xxx $query $i query
  97   }
  98   return $query
  99 }
 100
 101 proc random_or_query {nEntry} {
 102   set query [random_tree_structure $nEntry 1 OR]
 103   for {set i 1} {$i <= $nEntry} {incr i} {
 104     regsub xxx $query $i query
 105   }
 106   return $query
 107 }
 108
 109 proc random_andor_query {nEntry} {
 110   set query [random_tree_structure $nEntry 1 AND]
 111   for {set i 1} {$i <= $nEntry} {incr i} {
 112     regsub xxx $query "([random_or_query $nEntry])" query
 113   }
 114   return $query
 115 }
 116
 117 proc balanced_andor_tree {nEntry} {
 118   set tree [balanced_exprtree_structure $nEntry]
 119   set node "{[balanced_and_tree $nEntry]}"
 120   regsub -all AND $node OR node
 121   regsub -all xxx $tree $node tree
 122   return $tree
 123 }
 124
 125 # Test that queries like "1 AND 2 AND 3 AND 4..." are transformed to
 126 # balanced trees by FTS.
 127 #
 128 for {set i 1} {$i < 100} {incr i} {
 129   do_test 1.$i {
 130     test_fts3expr2 [random_and_query $i]
 131   } [balanced_and_tree $i]
 132 }
 133
 134 # Same again, except with parenthesis inserted at arbitrary points.
 135 #
 136 for {set i 1} {$i < 100} {incr i} {
 137   do_test 2.$i {
 138     test_fts3expr2 [random_and_query $i 1]
 139   } [balanced_and_tree $i]
 140 }
 141
 142 # Now attempt to balance two AND trees joined by an OR.
 143 #
 144 for {set i 1} {$i < 100} {incr i} {
 145   do_test 3.$i {
 146     test_fts3expr2 "[random_and_query $i 1] OR [random_and_query $i 1]"
 147   } [list OR [balanced_and_tree $i] [balanced_and_tree $i]]
 148 }
 149
 150 # Try trees of AND nodes with leaves that are themselves trees of OR nodes.
 151 #
 152 for {set i 2} {$i < 64} {incr i 4} {
 153   do_test 3.$i {
 154     test_fts3expr2 [random_andor_query $i]
 155   } [balanced_andor_tree $i]
 156 }
 157
 158 # These exceed the depth limit.
 159 #
 160 for {set i 65} {$i < 70} {incr i} {
 161   do_test 3.$i {
 162     list [catch {test_fts3expr2 [random_andor_query $i]} msg] $msg
 163   } {1 {Error parsing expression}}
 164 }
 165
 166 # This also exceeds the depth limit.
 167 #
 168
 169 do_test 4.1.1 {
 170   set q "1"
 171   for {set i 2} {$i < 5000} {incr i} {
 172     append q " AND $i"
 173   }
 174   list [catch {test_fts3expr2 $q} msg] $msg
 175 } {1 {Error parsing expression}}
 176 do_test 4.1.2 {
 177   set q "1"
 178   for {set i 2} {$i < 4000} {incr i} {
 179     append q " AND $i"
 180   }
 181   catch {test_fts3expr2 $q}
 182 } {0}
 183
 184 proc create_toggle_tree {nDepth} {
 185   if {$nDepth == 0} { return xxx }
 186   set nNew [expr $nDepth-1]
 187   if {$nDepth % 2} {
 188     return "([create_toggle_tree $nNew]) OR ([create_toggle_tree $nNew])"
 189   }
 190   return "([create_toggle_tree $nNew]) AND ([create_toggle_tree $nNew])"
 191 }
 192
 193 do_test 4.2 {
 194   list [catch {test_fts3expr2 [create_toggle_tree 17]} msg] $msg
 195 } {1 {Error parsing expression}}
 196
 197 set query [random_andor_query 12]
 198 set result [balanced_andor_tree 12]
 199 do_faultsim_test fts3expr3-fault-1 -faults oom-* -body {
 200   test_fts3expr2 $::query
 201 } -test {
 202   faultsim_test_result [list 0 $::result]
 203 }
 204
 205 set sqlite_fts3_enable_parentheses 0
 206 finish_test