1# 2007 May 10
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#
12# $Id: fuzz_common.tcl,v 1.2 2009/01/05 19:36:30 drh Exp $
13
14proc fuzz {TemplateList} {
15  set n [llength $TemplateList]
16  set i [expr {int(rand()*$n)}]
17  set r [uplevel 1 subst -novar [list [lindex $TemplateList $i]]]
18
19  string map {"\n" " "} $r
20}
21
22# Fuzzy generation primitives:
23#
24#     Literal
25#     UnaryOp
26#     BinaryOp
27#     Expr
28#     Table
29#     Select
30#     Insert
31#
32
33# Returns a string representing an SQL literal.
34#
35proc Literal {} {
36  set TemplateList {
37    456 0 -456 1 -1
38    2147483648 2147483647 2147483649 -2147483647 -2147483648 -2147483649
39    'The' 'first' 'experiments' 'in' 'hardware' 'fault' 'injection'
40    zeroblob(1000)
41    NULL
42    56.1 -56.1
43    123456789.1234567899
44  }
45  fuzz $TemplateList
46}
47
48# Returns a string containing an SQL unary operator (e.g. "+" or "NOT").
49#
50proc UnaryOp {} {
51  set TemplateList {+ - NOT ~}
52  fuzz $TemplateList
53}
54
55# Returns a string containing an SQL binary operator (e.g. "*" or "/").
56#
57proc BinaryOp {} {
58  set TemplateList {
59    || * / % + - << >> & | < <= > >= = == != <> AND OR
60    LIKE GLOB {NOT LIKE}
61  }
62  fuzz $TemplateList
63}
64
65# Return the complete text of an SQL expression.
66#
67set ::ExprDepth 0
68proc Expr { {c {}} } {
69  incr ::ExprDepth
70
71  set TemplateList [concat $c $c $c {[Literal]}]
72  if {$::ExprDepth < 3} {
73    lappend TemplateList \
74      {[Expr $c] [BinaryOp] [Expr $c]}                              \
75      {[UnaryOp] [Expr $c]}                                         \
76      {[Expr $c] ISNULL}                                            \
77      {[Expr $c] NOTNULL}                                           \
78      {CAST([Expr $c] AS blob)}                                     \
79      {CAST([Expr $c] AS text)}                                     \
80      {CAST([Expr $c] AS integer)}                                  \
81      {CAST([Expr $c] AS real)}                                     \
82      {abs([Expr])}                                                 \
83      {coalesce([Expr], [Expr])}                                    \
84      {hex([Expr])}                                                 \
85      {length([Expr])}                                              \
86      {lower([Expr])}                                               \
87      {upper([Expr])}                                               \
88      {quote([Expr])}                                               \
89      {random()}                                                    \
90      {randomblob(min(max([Expr],1), 500))}                         \
91      {typeof([Expr])}                                              \
92      {substr([Expr],[Expr],[Expr])}                                \
93      {CASE WHEN [Expr $c] THEN [Expr $c] ELSE [Expr $c] END}       \
94      {[Literal]} {[Literal]} {[Literal]}                           \
95      {[Literal]} {[Literal]} {[Literal]}                           \
96      {[Literal]} {[Literal]} {[Literal]}                           \
97      {[Literal]} {[Literal]} {[Literal]}
98  }
99  if {$::SelectDepth < 4} {
100    lappend TemplateList \
101      {([Select 1])}                       \
102      {[Expr $c] IN ([Select 1])}          \
103      {[Expr $c] NOT IN ([Select 1])}      \
104      {EXISTS ([Select 1])}                \
105  }
106  set res [fuzz $TemplateList]
107  incr ::ExprDepth -1
108  return $res
109}
110
111# Return a valid table name.
112#
113set ::TableList [list]
114proc Table {} {
115  set TemplateList [concat sqlite_master $::TableList]
116  fuzz $TemplateList
117}
118
119# Return one of:
120#
121#     "SELECT DISTINCT", "SELECT ALL" or "SELECT"
122#
123proc SelectKw {} {
124  set TemplateList {
125    "SELECT DISTINCT"
126    "SELECT ALL"
127    "SELECT"
128  }
129  fuzz $TemplateList
130}
131
132# Return a result set for a SELECT statement.
133#
134proc ResultSet {{nRes 0} {c ""}} {
135  if {$nRes == 0} {
136    set nRes [expr {rand()*2 + 1}]
137  }
138
139  set aRes [list]
140  for {set ii 0} {$ii < $nRes} {incr ii} {
141    lappend aRes [Expr $c]
142  }
143
144  join $aRes ", "
145}
146
147set ::SelectDepth 0
148set ::ColumnList [list]
149proc SimpleSelect {{nRes 0}} {
150
151  set TemplateList {
152      {[SelectKw] [ResultSet $nRes]}
153  }
154
155  # The ::SelectDepth variable contains the number of ancestor SELECT
156  # statements (i.e. for a top level SELECT it is set to 0, for a
157  # sub-select 1, for a sub-select of a sub-select 2 etc.).
158  #
159  # If this is already greater than 3, do not generate a complicated
160  # SELECT statement. This tends to cause parser stack overflow (too
161  # boring to bother with).
162  #
163  if {$::SelectDepth < 4} {
164    lappend TemplateList \
165        {[SelectKw] [ResultSet $nRes $::ColumnList] FROM ([Select])}     \
166        {[SelectKw] [ResultSet $nRes] FROM ([Select])}                   \
167        {[SelectKw] [ResultSet $nRes $::ColumnList] FROM [Table]}        \
168        {
169             [SelectKw] [ResultSet $nRes $::ColumnList]
170             FROM ([Select])
171             GROUP BY [Expr]
172             HAVING [Expr]
173        }                                                                \
174
175    if {0 == $nRes} {
176      lappend TemplateList                                               \
177          {[SelectKw] * FROM ([Select])}                                 \
178          {[SelectKw] * FROM [Table]}                                    \
179          {[SelectKw] * FROM [Table] WHERE [Expr $::ColumnList]}         \
180          {
181             [SelectKw] *
182             FROM [Table],[Table] AS t2
183             WHERE [Expr $::ColumnList]
184          } {
185             [SelectKw] *
186             FROM [Table] LEFT OUTER JOIN [Table] AS t2
187             ON [Expr $::ColumnList]
188             WHERE [Expr $::ColumnList]
189          }
190    }
191  }
192
193  fuzz $TemplateList
194}
195
196# Return a SELECT statement.
197#
198# If boolean parameter $isExpr is set to true, make sure the
199# returned SELECT statement returns a single column of data.
200#
201proc Select {{nMulti 0}} {
202  set TemplateList {
203    {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]}
204    {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]}
205    {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]}
206    {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]} {[SimpleSelect $nMulti]}
207    {[SimpleSelect $nMulti] ORDER BY [Expr] DESC}
208    {[SimpleSelect $nMulti] ORDER BY [Expr] ASC}
209    {[SimpleSelect $nMulti] ORDER BY [Expr] ASC, [Expr] DESC}
210    {[SimpleSelect $nMulti] ORDER BY [Expr] LIMIT [Expr] OFFSET [Expr]}
211  }
212
213  if {$::SelectDepth < 4} {
214    if {$nMulti == 0} {
215      set nMulti [expr {(rand()*2)+1}]
216    }
217    lappend TemplateList                                             \
218        {[SimpleSelect $nMulti] UNION     [Select $nMulti]}          \
219        {[SimpleSelect $nMulti] UNION ALL [Select $nMulti]}          \
220        {[SimpleSelect $nMulti] EXCEPT    [Select $nMulti]}          \
221        {[SimpleSelect $nMulti] INTERSECT [Select $nMulti]}
222  }
223
224  incr ::SelectDepth
225  set res [fuzz $TemplateList]
226  incr ::SelectDepth -1
227  set res
228}
229
230# Generate and return a fuzzy INSERT statement.
231#
232proc Insert {} {
233  set TemplateList {
234      {INSERT INTO [Table] VALUES([Expr], [Expr], [Expr]);}
235      {INSERT INTO [Table] VALUES([Expr], [Expr], [Expr], [Expr]);}
236      {INSERT INTO [Table] VALUES([Expr], [Expr]);}
237  }
238  fuzz $TemplateList
239}
240
241proc Column {} {
242  fuzz $::ColumnList
243}
244
245# Generate and return a fuzzy UPDATE statement.
246#
247proc Update {} {
248  set TemplateList {
249    {UPDATE [Table]
250     SET [Column] = [Expr $::ColumnList]
251     WHERE [Expr $::ColumnList]}
252  }
253  fuzz $TemplateList
254}
255
256proc Delete {} {
257  set TemplateList {
258    {DELETE FROM [Table] WHERE [Expr $::ColumnList]}
259  }
260  fuzz $TemplateList
261}
262
263proc Statement {} {
264  set TemplateList {
265    {[Update]}
266    {[Insert]}
267    {[Select]}
268    {[Delete]}
269  }
270  fuzz $TemplateList
271}
272
273# Return an identifier. This just chooses randomly from a fixed set
274# of strings.
275proc Identifier {} {
276  set TemplateList {
277    This just chooses randomly a fixed
278    We would also thank the developers
279    for their analysis Samba
280  }
281  fuzz $TemplateList
282}
283
284proc Check {} {
285  # Use a large value for $::SelectDepth, because sub-selects are
286  # not allowed in expressions used by CHECK constraints.
287  #
288  set sd $::SelectDepth
289  set ::SelectDepth 500
290  set TemplateList {
291    {}
292    {CHECK ([Expr])}
293  }
294  set res [fuzz $TemplateList]
295  set ::SelectDepth $sd
296  set res
297}
298
299proc Coltype {} {
300  set TemplateList {
301    {INTEGER PRIMARY KEY}
302    {VARCHAR [Check]}
303    {PRIMARY KEY}
304  }
305  fuzz $TemplateList
306}
307
308proc DropTable {} {
309  set TemplateList {
310    {DROP TABLE IF EXISTS [Identifier]}
311  }
312  fuzz $TemplateList
313}
314
315proc CreateView {} {
316  set TemplateList {
317    {CREATE VIEW [Identifier] AS [Select]}
318  }
319  fuzz $TemplateList
320}
321proc DropView {} {
322  set TemplateList {
323    {DROP VIEW IF EXISTS [Identifier]}
324  }
325  fuzz $TemplateList
326}
327
328proc CreateTable {} {
329  set TemplateList {
330    {CREATE TABLE [Identifier]([Identifier] [Coltype], [Identifier] [Coltype])}
331    {CREATE TEMP TABLE [Identifier]([Identifier] [Coltype])}
332  }
333  fuzz $TemplateList
334}
335
336proc CreateOrDropTableOrView {} {
337  set TemplateList {
338    {[CreateTable]}
339    {[DropTable]}
340    {[CreateView]}
341    {[DropView]}
342  }
343  fuzz $TemplateList
344}
345
346########################################################################
347
348set ::log [open fuzzy.log w]
349
350#
351# Usage: do_fuzzy_test <testname> ?<options>?
352#
353#     -template
354#     -errorlist
355#     -repeats
356#
357proc do_fuzzy_test {testname args} {
358  set ::fuzzyopts(-errorlist) [list]
359  set ::fuzzyopts(-repeats) $::REPEATS
360  array set ::fuzzyopts $args
361
362  lappend ::fuzzyopts(-errorlist) {parser stack overflow}
363  lappend ::fuzzyopts(-errorlist) {ORDER BY}
364  lappend ::fuzzyopts(-errorlist) {GROUP BY}
365  lappend ::fuzzyopts(-errorlist) {datatype mismatch}
366
367  for {set ii 0} {$ii < $::fuzzyopts(-repeats)} {incr ii} {
368    do_test ${testname}.$ii {
369      set ::sql [subst $::fuzzyopts(-template)]
370      puts $::log $::sql
371      flush $::log
372      set rc [catch {execsql $::sql} msg]
373      set e 1
374      if {$rc} {
375        set e 0
376        foreach error $::fuzzyopts(-errorlist) {
377          if {[string first $error $msg]>=0} {
378            set e 1
379            break
380          }
381        }
382      }
383      if {$e == 0} {
384        puts ""
385        puts $::sql
386        puts $msg
387      }
388      set e
389    } {1}
390  }
391}
392