AryaWu/sqlite
0
1# 2009 January 12#3# The author disclaims copyright to this source code. In place of4# 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. The12# focus of this script is testing the part of the FTS3 expression13# parser that rebalances large expressions.14#15# $Id: fts3expr2.test,v 1.2 2009/06/05 17:09:12 drh Exp $16#17 18set testdir [file dirname $argv0]19source $testdir/tester.tcl20source $testdir/malloc_common.tcl21set ::testprefix fts3expr322 23# If SQLITE_ENABLE_FTS3 is defined, omit this file.24ifcapable !fts3 {25 finish_test26 return27}28 29set sqlite_fts3_enable_parentheses 130 31proc 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}41proc test_fts3expr2 {expr} {42 strip_phrase_data [43 db one {SELECT fts3_exprtest_rebalance('simple', $expr, 'a', 'b', 'c')}44 ]45}46 47proc balanced_exprtree_structure {nEntry} {48 set L [list]49 for {set i 1} {$i <= $nEntry} {incr i} {50 lappend L xxx51 }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 $N61 }62 return [lindex $L 0]63}64 65proc 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}" query72 }73 return $query74}75 76proc random_tree_structure {nEntry bParen op} {77 set query xxx78 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 $query91}92 93proc 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 query97 }98 return $query99}100 101proc 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 query105 }106 return $query107}108 109proc 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])" query113 }114 return $query115}116 117proc balanced_andor_tree {nEntry} {118 set tree [balanced_exprtree_structure $nEntry]119 set node "{[balanced_and_tree $nEntry]}"120 regsub -all AND $node OR node121 regsub -all xxx $tree $node tree122 return $tree123}124 125if 1 {126 127# Test that queries like "1 AND 2 AND 3 AND 4..." are transformed to 128# balanced trees by FTS.129#130for {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#138for {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#146for {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#154for {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#162for {set i 65} {$i < 70} {incr i} {163 do_test 3.$i {164 list [catch {test_fts3expr2 [random_andor_query $i]} msg] $msg165 } {1 {Error parsing expression}}166}167 168# This also exceeds the depth limit. 169#170 171do_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] $msg177} {1 {Error parsing expression}}178do_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 186proc 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 195do_test 4.2 {196 list [catch {test_fts3expr2 [create_toggle_tree 17]} msg] $msg197} {1 {Error parsing expression}}198 199set query [random_andor_query 12]200set result [balanced_andor_tree 12]201do_faultsim_test fts3expr3-fault-1 -faults oom-* -body {202 test_fts3expr2 $::query203} -test {204 faultsim_test_result [list 0 $::result]205}206 207}208 209#-------------------------------------------------------------------210 211foreach {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 $expr234 } $res235}236 237set sqlite_fts3_enable_parentheses 0238finish_test239