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