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 if 1 {
 126
 127 # Test that queries like "1 AND 2 AND 3 AND 4..." are transformed to
 128 # balanced trees by FTS.
 129 #
 130 for {set i 1} {$i < 100} {incr i} {
 131   do_test 1.$i {
 132     test_fts3expr2 [random_and_query $i]
 133   } [balanced_and_tree $i]
 134 }
 135
 136 # Same again, except with parenthesis inserted at arbitrary points.
 137 #
 138 for {set i 1} {$i < 100} {incr i} {
 139   do_test 2.$i {
 140     test_fts3expr2 [random_and_query $i 1]
 141   } [balanced_and_tree $i]
 142 }
 143
 144 # Now attempt to balance two AND trees joined by an OR.
 145 #
 146 for {set i 1} {$i < 100} {incr i} {
 147   do_test 3.$i {
 148     test_fts3expr2 "[random_and_query $i 1] OR [random_and_query $i 1]"
 149   } [list OR [balanced_and_tree $i] [balanced_and_tree $i]]
 150 }
 151
 152 # Try trees of AND nodes with leaves that are themselves trees of OR nodes.
 153 #
 154 for {set i 2} {$i < 64} {incr i 4} {
 155   do_test 3.$i {
 156     test_fts3expr2 [random_andor_query $i]
 157   } [balanced_andor_tree $i]
 158 }
 159
 160 # These exceed the depth limit.
 161 #
 162 for {set i 65} {$i < 70} {incr i} {
 163   do_test 3.$i {
 164     list [catch {test_fts3expr2 [random_andor_query $i]} msg] $msg
 165   } {1 {Error parsing expression}}
 166 }
 167
 168 # This also exceeds the depth limit.
 169 #
 170
 171 do_test 4.1.1 {
 172   set q "1"
 173   for {set i 2} {$i < 5000} {incr i} {
 174     append q " AND $i"
 175   }
 176   list [catch {test_fts3expr2 $q} msg] $msg
 177 } {1 {Error parsing expression}}
 178 do_test 4.1.2 {
 179   set q "1"
 180   for {set i 2} {$i < 4000} {incr i} {
 181     append q " AND $i"
 182   }
 183   catch {test_fts3expr2 $q}
 184 } {0}
 185
 186 proc create_toggle_tree {nDepth} {
 187   if {$nDepth == 0} { return xxx }
 188   set nNew [expr $nDepth-1]
 189   if {$nDepth % 2} {
 190     return "([create_toggle_tree $nNew]) OR ([create_toggle_tree $nNew])"
 191   }
 192   return "([create_toggle_tree $nNew]) AND ([create_toggle_tree $nNew])"
 193 }
 194
 195 do_test 4.2 {
 196   list [catch {test_fts3expr2 [create_toggle_tree 17]} msg] $msg
 197 } {1 {Error parsing expression}}
 198
 199 set query [random_andor_query 12]
 200 set result [balanced_andor_tree 12]
 201 do_faultsim_test fts3expr3-fault-1 -faults oom-* -body {
 202   test_fts3expr2 $::query
 203 } -test {
 204   faultsim_test_result [list 0 $::result]
 205 }
 206
 207 }
 208
 209 #-------------------------------------------------------------------
 210
 211 foreach {tn expr res} {
 212   1 {1 OR 2 OR 3 OR 4}           {OR {OR {P 1} {P 2}} {OR {P 3} {P 4}}}
 213   2 {1 OR (2 AND 3 AND 4 AND 5)}
 214     {OR {P 1} {AND {AND {P 2} {P 3}} {AND {P 4} {P 5}}}}
 215   3 {(2 AND 3 AND 4 AND 5) OR 1}
 216     {OR {AND {AND {P 2} {P 3}} {AND {P 4} {P 5}}} {P 1}}
 217
 218   4 {1 AND (2 OR 3 OR 4 OR 5)}
 219     {AND {P 1} {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}}}
 220   5 {(2 OR 3 OR 4 OR 5) AND 1}
 221     {AND {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}} {P 1}}
 222
 223   6 {(2 OR 3 OR 4 OR 5) NOT 1}
 224     {NOT {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}} {P 1}}
 225
 226   7 {1 NOT (2 OR 3 OR 4 OR 5)}
 227     {NOT {P 1} {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}}}
 228
 229   8 {(1 OR 2 OR 3 OR 4) NOT (5 AND 6 AND 7 AND 8)}
 230     {NOT {OR {OR {P 1} {P 2}} {OR {P 3} {P 4}}} {AND {AND {P 5} {P 6}} {AND {P 7} {P 8}}}}
 231 } {
 232   do_test 5.1.$tn {
 233     test_fts3expr2 $expr
 234   } $res
 235 }
 236
 237 set sqlite_fts3_enable_parentheses 0
 238 finish_test