1
2#pragma ident	"%Z%%M%	%I%	%E% SMI"
3
4# 2001 September 15
5#
6# The author disclaims copyright to this source code.  In place of
7# a legal notice, here is a blessing:
8#
9#    May you do good and not evil.
10#    May you find forgiveness for yourself and forgive others.
11#    May you share freely, never taking more than you give.
12#
13#***********************************************************************
14# This file implements regression tests for SQLite library.  The
15# focus of this script is btree database backend
16#
17# $Id: btree2.test,v 1.10 2002/02/19 13:39:23 drh Exp $
18
19
20set testdir [file dirname $argv0]
21source $testdir/tester.tcl
22
23if {[info commands btree_open]!=""} {
24
25# Create a new database file containing no entries.  The database should
26# contain 5 tables:
27#
28#     2   The descriptor table
29#     3   The foreground table
30#     4   The background table
31#     5   The long key table
32#     6   The long data table
33#
34# An explanation for what all these tables are used for is provided below.
35#
36do_test btree2-1.1 {
37  expr srand(1)
38  file delete -force test2.bt
39  file delete -force test2.bt-journal
40  set ::b [btree_open test2.bt]
41  btree_begin_transaction $::b
42  btree_create_table $::b
43} {3}
44do_test btree2-1.2 {
45  btree_create_table $::b
46} {4}
47do_test btree2-1.3 {
48  btree_create_table $::b
49} {5}
50do_test btree2-1.4 {
51  btree_create_table $::b
52} {6}
53do_test btree2-1.5 {
54  set ::c2 [btree_cursor $::b 2 1]
55  btree_insert $::c2 {one} {1}
56  btree_delete $::c2
57  btree_close_cursor $::c2
58  btree_commit $::b
59  btree_integrity_check $::b 2 3 4 5 6
60} {}
61
62# This test module works by making lots of pseudo-random changes to a
63# database while simultaneously maintaining an invariant on that database.
64# Periodically, the script does a sanity check on the database and verifies
65# that the invariant is satisfied.
66#
67# The invariant is as follows:
68#
69#   1.  The descriptor table always contains 2 enters.  An entry keyed by
70#       "N" is the number of elements in the foreground and background tables
71#       combined.  The entry keyed by "L" is the number of digits in the keys
72#       for foreground and background tables.
73#
74#   2.  The union of the foreground an background tables consists of N entries
75#       where each entry an L-digit key.  (Actually, some keys can be longer
76#       than L characters, but they always start with L digits.)  The keys
77#       cover all integers between 1 and N.  Whenever an entry is added to
78#       the foreground it is removed form the background and vice versa.
79#
80#   3.  Some entries in the foreground and background tables have keys that
81#       begin with an L-digit number but are followed by additional characters.
82#       For each such entry there is a corresponding entry in the long key
83#       table.  The long key table entry has a key which is just the L-digit
84#       number and data which is the length of the key in the foreground and
85#       background tables.
86#
87#   4.  The data for both foreground and background entries is usually a
88#       short string.  But some entries have long data strings.  For each
89#       such entries there is an entry in the long data type.  The key to
90#       long data table is an L-digit number.  (The extension on long keys
91#       is omitted.)  The data is the number of charaters in the data of the
92#       foreground or background entry.
93#
94# The following function builds a database that satisfies all of the above
95# invariants.
96#
97proc build_db {N L} {
98  for {set i 2} {$i<=6} {incr i} {
99    catch {btree_close_cursor [set ::c$i]}
100    btree_clear_table $::b $i
101    set ::c$i [btree_cursor $::b $i 1]
102  }
103  btree_insert $::c2 N $N
104  btree_insert $::c2 L $L
105  set format %0${L}d
106  for {set i 1} {$i<=$N} {incr i} {
107    set key [format $format $i]
108    set data $key
109    btree_insert $::c3 $key $data
110  }
111}
112
113# Given a base key number and a length, construct the full text of the key
114# or data.
115#
116proc make_payload {keynum L len} {
117  set key [format %0${L}d $keynum]
118  set r $key
119  set i 1
120  while {[string length $r]<$len} {
121    append r " ($i) $key"
122    incr i
123  }
124  return [string range $r 0 [expr {$len-1}]]
125}
126
127# Verify the invariants on the database.  Return an empty string on
128# success or an error message if something is amiss.
129#
130proc check_invariants {} {
131  set ck [btree_integrity_check $::b 2 3 4 5 6]
132  if {$ck!=""} {
133    puts "\n*** SANITY:\n$ck"
134    exit
135    return $ck
136  }
137  btree_move_to $::c3 {}
138  btree_move_to $::c4 {}
139  btree_move_to $::c2 N
140  set N [btree_data $::c2]
141  btree_move_to $::c2 L
142  set L [btree_data $::c2]
143  set LM1 [expr {$L-1}]
144  for {set i 1} {$i<=$N} {incr i} {
145    set key [btree_key $::c3]
146    if {[scan $key %d k]<1} {set k 0}
147    if {$k!=$i} {
148      set key [btree_key $::c4]
149      if {[scan $key %d k]<1} {set k 0}
150      if {$k!=$i} {
151        # puts "MISSING $i"
152        # puts {Page 3:}; btree_page_dump $::b 3
153        # puts {Page 4:}; btree_page_dump $::b 4
154        # exit
155        return "Key $i is missing from both foreground and background"
156      }
157      set data [btree_data $::c4]
158      btree_next $::c4
159    } else {
160      set data [btree_data $::c3]
161      btree_next $::c3
162    }
163    set skey [string range $key 0 $LM1]
164    if {[btree_move_to $::c5 $skey]==0} {
165      set keylen [btree_data $::c5]
166    } else {
167      set keylen $L
168    }
169    if {[string length $key]!=$keylen} {
170      return "Key $i is the wrong size.\
171              Is \"$key\" but should be \"[make_payload $k $L $keylen]\""
172    }
173    if {[make_payload $k $L $keylen]!=$key} {
174      return "Key $i has an invalid extension"
175    }
176    if {[btree_move_to $::c6 $skey]==0} {
177      set datalen [btree_data $::c6]
178    } else {
179      set datalen $L
180    }
181    if {[string length $data]!=$datalen} {
182      return "Data for $i is the wrong size.\
183              Is [string length $data] but should be $datalen"
184    }
185    if {[make_payload $k $L $datalen]!=$data} {
186      return "Entry $i has an incorrect data"
187    }
188  }
189}
190
191# Make random changes to the database such that each change preserves
192# the invariants.  The number of changes is $n*N where N is the parameter
193# from the descriptor table.  Each changes begins with a random key.
194# the entry with that key is put in the foreground table with probability
195# $I and it is put in background with probability (1.0-$I).  It gets
196# a long key with probability $K and long data with probability $D.
197#
198set chngcnt 0
199proc random_changes {n I K D} {
200  btree_move_to $::c2 N
201  set N [btree_data $::c2]
202  btree_move_to $::c2 L
203  set L [btree_data $::c2]
204  set LM1 [expr {$L-1}]
205  set total [expr {int($N*$n)}]
206  set format %0${L}d
207  for {set i 0} {$i<$total} {incr i} {
208    set k [expr {int(rand()*$N)+1}]
209    set insert [expr {rand()<=$I}]
210    set longkey [expr {rand()<=$K}]
211    set longdata [expr {rand()<=$D}]
212    # incr ::chngcnt
213    # if {$::chngcnt==251} {btree_tree_dump $::b 3}
214    # puts "CHANGE $::chngcnt: $k $insert $longkey $longdata"
215    if {$longkey} {
216      set x [expr {rand()}]
217      set keylen [expr {int($x*$x*$x*$x*3000)+10}]
218    } else {
219      set keylen $L
220    }
221    set key [make_payload $k $L $keylen]
222    if {$longdata} {
223      set x [expr {rand()}]
224      set datalen [expr {int($x*$x*$x*$x*3000)+10}]
225    } else {
226      set datalen $L
227    }
228    set data [make_payload $k $L $datalen]
229    set basekey [format $format $k]
230    if {[set c [btree_move_to $::c3 $basekey]]==0} {
231      btree_delete $::c3
232    } else {
233      if {$c<0} {btree_next $::c3}
234      if {[string match $basekey* [btree_key $::c3]]} {
235        btree_delete $::c3
236      }
237    }
238    if {[set c [btree_move_to $::c4 $basekey]]==0} {
239      btree_delete $::c4
240    } else {
241      if {$c<0} {btree_next $::c4}
242      if {[string match $basekey* [btree_key $::c4]]} {
243        btree_delete $::c4
244      }
245    }
246    if {[scan [btree_key $::c4] %d kx]<1} {set kx -1}
247    if {$kx==$k} {
248      btree_delete $::c4
249    }
250    if {$insert} {
251      btree_insert $::c3 $key $data
252    } else {
253      btree_insert $::c4 $key $data
254    }
255    if {$longkey} {
256      btree_insert $::c5 $basekey $keylen
257    } elseif {[btree_move_to $::c5 $basekey]==0} {
258      btree_delete $::c5
259    }
260    if {$longdata} {
261      btree_insert $::c6 $basekey $datalen
262    } elseif {[btree_move_to $::c6 $basekey]==0} {
263      btree_delete $::c6
264    }
265    # set ck [btree_integrity_check $::b 2 3 4 5 6]
266    # if {$ck!=""} {
267    #   puts "\nSANITY CHECK FAILED!\n$ck"
268    #   exit
269    # }
270    # puts "PAGE 3:"; btree_page_dump $::b 3
271    # puts "PAGE 4:"; btree_page_dump $::b 4
272  }
273}
274
275# Repeat this test sequence on database of various sizes
276#
277set testno 2
278foreach {N L} {
279  10 2
280  50 2
281  200 3
282  2000 5
283} {
284  puts "**** N=$N L=$L ****"
285  set hash [md5file test2.bt]
286  do_test btree2-$testno.1 [subst -nocommands {
287    set ::c2 [btree_cursor $::b 2 1]
288    set ::c3 [btree_cursor $::b 3 1]
289    set ::c4 [btree_cursor $::b 4 1]
290    set ::c5 [btree_cursor $::b 5 1]
291    set ::c6 [btree_cursor $::b 6 1]
292    btree_begin_transaction $::b
293    build_db $N $L
294    check_invariants
295  }] {}
296  do_test btree2-$testno.2 {
297    btree_close_cursor $::c2
298    btree_close_cursor $::c3
299    btree_close_cursor $::c4
300    btree_close_cursor $::c5
301    btree_close_cursor $::c6
302    btree_rollback $::b
303    md5file test2.bt
304  } $hash
305  do_test btree2-$testno.3 [subst -nocommands {
306    btree_begin_transaction $::b
307    set ::c2 [btree_cursor $::b 2 1]
308    set ::c3 [btree_cursor $::b 3 1]
309    set ::c4 [btree_cursor $::b 4 1]
310    set ::c5 [btree_cursor $::b 5 1]
311    set ::c6 [btree_cursor $::b 6 1]
312    build_db $N $L
313    check_invariants
314  }] {}
315  do_test btree2-$testno.4 {
316    btree_commit $::b
317    check_invariants
318  } {}
319  do_test btree2-$testno.5  {
320    lindex [btree_pager_stats $::b] 1
321  } {6}
322  do_test btree2-$testno.6  {
323    btree_close_cursor $::c2
324    btree_close_cursor $::c3
325    btree_close_cursor $::c4
326    btree_close_cursor $::c5
327    btree_close_cursor $::c6
328    lindex [btree_pager_stats $::b] 1
329  } {0}
330  do_test btree2-$testno.7 {
331    btree_close $::b
332  } {}
333after 100
334  # For each database size, run various changes tests.
335  #
336  set num2 1
337  foreach {n I K D} {
338    0.5 0.5 0.1 0.1
339    1.0 0.2 0.1 0.1
340    1.0 0.8 0.1 0.1
341    2.0 0.0 0.1 0.1
342    2.0 1.0 0.1 0.1
343    2.0 0.0 0.0 0.0
344    2.0 1.0 0.0 0.0
345  } {
346    set testid btree2-$testno.8.$num2
347    set hash [md5file test2.bt]
348    do_test $testid.0 {
349      set ::b [btree_open test2.bt]
350      set ::c2 [btree_cursor $::b 2 1]
351      set ::c3 [btree_cursor $::b 3 1]
352      set ::c4 [btree_cursor $::b 4 1]
353      set ::c5 [btree_cursor $::b 5 1]
354      set ::c6 [btree_cursor $::b 6 1]
355      check_invariants
356    } {}
357    set cnt 6
358    for {set i 2} {$i<=6} {incr i} {
359      if {[lindex [btree_cursor_dump [set ::c$i]] 0]!=$i} {incr cnt}
360    }
361    do_test $testid.1 {
362      btree_begin_transaction $::b
363      lindex [btree_pager_stats $::b] 1
364    } $cnt
365    # exec cp test2.bt test2.bt.bu1
366    do_test $testid.2 [subst {
367      random_changes $n $I $K $D
368    }] {}
369    do_test $testid.3 {
370      check_invariants
371    } {}
372    do_test $testid.4 {
373      btree_close_cursor $::c2
374      btree_close_cursor $::c3
375      btree_close_cursor $::c4
376      btree_close_cursor $::c5
377      btree_close_cursor $::c6
378      btree_rollback $::b
379      md5file test2.bt
380    } $hash
381    # exec cp test2.bt test2.bt.bu2
382    btree_begin_transaction $::b
383    set ::c2 [btree_cursor $::b 2 1]
384    set ::c3 [btree_cursor $::b 3 1]
385    set ::c4 [btree_cursor $::b 4 1]
386    set ::c5 [btree_cursor $::b 5 1]
387    set ::c6 [btree_cursor $::b 6 1]
388    do_test $testid.5 [subst {
389      random_changes $n $I $K $D
390    }] {}
391    do_test $testid.6 {
392      check_invariants
393    } {}
394    do_test $testid.7 {
395      btree_commit $::b
396      check_invariants
397    } {}
398    set hash [md5file test2.bt]
399    do_test $testid.8 {
400      btree_close_cursor $::c2
401      btree_close_cursor $::c3
402      btree_close_cursor $::c4
403      btree_close_cursor $::c5
404      btree_close_cursor $::c6
405      lindex [btree_pager_stats $::b] 1
406    } {0}
407    do_test $testid.9 {
408      btree_close $::b
409      set ::b [btree_open test2.bt]
410      set ::c2 [btree_cursor $::b 2 1]
411      set ::c3 [btree_cursor $::b 3 1]
412      set ::c4 [btree_cursor $::b 4 1]
413      set ::c5 [btree_cursor $::b 5 1]
414      set ::c6 [btree_cursor $::b 6 1]
415      check_invariants
416    } {}
417    do_test $testid.10 {
418      btree_close_cursor $::c2
419      btree_close_cursor $::c3
420      btree_close_cursor $::c4
421      btree_close_cursor $::c5
422      btree_close_cursor $::c6
423      lindex [btree_pager_stats $::b] 1
424    } {0}
425    do_test $testid.11 {
426      btree_close $::b
427    } {}
428    incr num2
429  }
430  incr testno
431  set ::b [btree_open test2.bt]
432}
433
434# Testing is complete.  Shut everything down.
435#
436do_test btree-999.1 {
437  lindex [btree_pager_stats $::b] 1
438} {0}
439do_test btree-999.2 {
440  btree_close $::b
441} {}
442do_test btree-999.3 {
443  file delete -force test2.bt
444  file exists test2.bt-journal
445} {0}
446
447} ;# end if( not mem: and has pager_open command );
448
449finish_test
450